Добре попрацювавши, Сергiй вирiшив зайнятись улюбленою справою — малюванням. Звiсно, спочатку вiн намалював Головне Ужляндське Дерево. Це дерево особливе: воно мiстить n гiлок, пронумерованих вiд 1 до n та розташованих циклiчно так, що наступною для першої гiлки є друга, для другої - третя, i так далi, а для гiлки з номером n - перша.

Початково на кожнiй з гiлок знаходиться деяка кiлькiсть пташок (також на гiлцi може не знаходитись жодна пташка). Всього на деревi m пташок, пронумерованих вiд 1 до m. Кожна з пташок характеризується своєю вагою: вага пташки з номером i рiвна (ai + b) mod (109 + 7), де a та b – деякi константи, а x mod y позначає остачу вiд дiлення x на y. Вiдомо, що всi значення ваги пташок попарно рiзнi. Також вiдомо, що на гiлцi з номером i початково знаходится ci пташок так, що на гiлцi з номером 1 знаходяться пташки з номерами 1, 2, .., c1, на гiлцi з номером 2 пташки з номерами c1 + 1, c1 + 2, ..., c1 + c2 i так далi. Гарантується, що c1 + c2 + ... + cn = m.

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

Завдання

Напишіть програму, яка за інформацією про розміщення пташок на дереві, та числа k та t визначить вагу пташки, яка перелiтатиме з гiлки з номером k у секунду з номером t?

Вхідні дані

У першому рядку вхідного файла задано шiсть цiлих чисел n m k t a b(1 ⩽ n ⩽ 104, 1 ⩽ m ⩽ 2 • 106, 1 ⩽ k ⩽ n, 1 ⩽ t ⩽ 109, 1 ⩽ a < 109 + 7, 0 ⩽ b < 109 + 7) — кiлькiсть гiлок дерева, кiлькiсть пташок на деревi, числа якi загадав Сергiй та константи, якi визначають вагу пташки вiдповiдно.

У другому рядку задано n цiлих чисел c1, c2, ..., cn(0 ⩽ ci ⩽ m), де ci — початкова кiлькiсть пташок на гiлцi з номером i. Гарантується, що всi значення ваги пташок попарно рiзнi та c1 + c2 + ... + cn = m

Вихідні дані

У вихідний файл tree.out виведiть одне цiле число — вагу пташки, яка перелiтатиме з гiлки з номером k у секунду з номером t, або −1, якщо перед секундою з номером t на цiй гiлцi не буде жодної пташки.

Оцінювання

Пiдзадача Бали Додатковi обмеження Необхідні підзадачі

0 0 Тести з умови -

1 17 1 ⩽ n,m,t ⩽ 100 0

2 12 1 ⩽ n ⩽ 100, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 5000 0, 1

3 18 1 ⩽ n ⩽ 100, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 109 0, 1, 2

4 24 1 ⩽ n ⩽ 104, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 109 0, 1, 2, 3

5 29 Без додаткових обмежень 0, 1, 2, 3, 4