Дерево
Дерево
Добре попрацювавши, Серг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
4 9 4 7 2 7 3 4 0 2
23