Дерево

После хорошей работы Сергей решил заняться своим любимым хобби — рисованием. Конечно, первым делом он нарисовал Главное Ужляндское Дерево. Это дерево уникально: у него есть n веток, пронумерованных от 1 до n, расположенных по кругу так, что за первой веткой следует вторая, за второй — третья, и так далее, а за веткой с номером n — первая.

Изначально на каждой ветке сидит некоторое количество птиц (возможно, ни одной). Всего на дереве m птиц, пронумерованных от 1 до m. Каждая птица имеет свой вес, который вычисляется как (a[i] + b) mod (10^9 + 7), где a и b — это константы, а x mod y обозначает остаток от деления x на y. Известно, что веса всех птиц различны. Также известно, что на ветке с номером i изначально находится c[i] птиц, так что на ветке с номером 1 сидят птицы с номерами 1, 2, ..., c[1], на ветке с номером 2 — птицы с номерами c[1] + 1, c[1] + 2, ..., c[1] + c[2], и так далее. Гарантируется, что c[1] + c[2] + ... + c[n] = m.

Каждую секунду происходит следующее: с каждой ветки, на которой есть хотя бы одна птица, на следующую ветку перелетает птица с наименьшим весом. Например, если дерево имеет 3 ветки, на первой находятся птицы с весами {1, 3, 5}, на второй — {2, 7}, а на третьей — {4, 5, 6}, то через секунду веса птиц на ветках будут {3, 4, 5}, {1, 7}, {2, 5, 6} соответственно. Сергей загадал два числа k и t. Теперь ему интересно: какой вес будет у птицы, которая перелетит с ветки с номером k в секунду с номером t?

Задача

Напишите программу, которая по информации о размещении птиц на дереве и числам k и t определит вес птицы, которая будет перелетать с ветки с номером k в секунду с номером t.

Входные данные

В первой строке входного файла заданы шесть целых чисел n m k t a b (1 ⩽ n ⩽ 10^4, 1 ⩽ m ⩽ 2 • 10^6, 1 ⩽ k ⩽ n, 1 ⩽ t ⩽ 10^9, 1 ⩽ a < 10^9 + 7, 0 ⩽ b < 10^9 + 7) — количество веток дерева, количество птиц на дереве, числа, которые загадал Сергей, и константы, определяющие вес птицы.

Во второй строке заданы n целых чисел c[1], c[2], ..., c[n] (0 ⩽ c[i] ⩽ m), где c[i] — начальное количество птиц на ветке с номером i. Гарантируется, что все значения веса птиц попарно различны и c[1] + c[2] + ... + c[n] = m.

Выходные данные

В выходной файл tree.out выведите одно целое число — вес птицы, которая будет перелетать с ветки с номером k в секунду с номером t, или −1, если перед секундой с номером t на этой ветке не будет ни одной птицы.

Примеры

Оценивание