Добре попрацювавши, Серг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вна (a[i]
+ b) mod (10^9
+ 7), де a та b – деякi константи, а x mod y позначає остачу вiд дiлення x на y. Вiдомо, що всi значення ваги пташок попарно рiзнi. Також вiдомо, що на гiлцi з номером i початково знаходится c[i]
пташок так, що на гiлцi з номером 1 знаходяться пташки з номерами 1, 2, .., c[1]
, на гiлцi з номером 2 пташки з номерами c[1]
+ 1, c[1]
+ 2, ..., c[1]
+ c[2]
i так далi. Гарантується, що c[1]
+ c[2]
+ ... + c[n]
= 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 ⩽ 10^4
, 1 ⩽ m ⩽ 2 •10^6
, 1 ⩽ k ⩽ n, 1 ⩽ t ⩽ 10^9
, 1 ⩽ a < 10^9
+ 7, 0 ⩽ b < 10^9
+ 7) — кiлькiсть гiлок дерева, кiлькiсть пташок на деревi, числа якi загадав Сергiй та константи, якi визначають вагу пташки вiдповiдно.
У другому рядку задано n цiлих чисел c[1]
, c[2]
, ..., c[n]
(0 ⩽ c[i]
⩽ m), де c[i]
— початкова кiлькiсть пташок на гiлцi з номером i. Гарантується, що всi значення ваги пташок попарно рiзнi та c[1]
+ c[2]
+ ... + c[n]
= 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 ⩽ 10^4
, 1 ⩽ m ⩽ 50000, 1 ⩽ t ⩽ 109 0, 1, 2, 3
5 29 Без додаткових обмежень 0, 1, 2, 3, 4