Сергiй та дерево

Добре попрацювавши, Серг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)\mathrm{mod}(10^9+7)$, де $a$ та $b$ – деякi константи, а $x\mathrm{mod}y$ позначає остачу вiд дiлення $x$ на $y$. Вiдомо, що всi значення ваги пташок попарно рiзнi. Також вiдомо, що на гiлцi з номером $i$ початково знаходится ci пташок так, що на гiлцi з номером $1$ знаходяться пташки з номерами $1,2,\dots ,c_1$, на гiлцi з номером $2$ пташки з номерами $c_1+1,c_1+2,\dots ,c_1+c_2$ iтакдалi. Гарантується, що $c_1+c_2+\cdots +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\le n\le 10^4$; $1\le m\le 2\cdot 10^6$; $1\le k\le n$; $1\le t\le 10^9$; $1\le a<10^9+7$; $0\le b<10^9+7$) — кiлькiсть гiлок дерева, кiлькiсть пташок на деревi, числа якi загадав Сергiй та константи, якi визначають вагу пташки вiдповiдно.

У другому рядку задано $n$ цiлих чисел $c_1,c_2,\dots ,c_n$ ($0\le c_i\le m$), де $c_i$ — початкова кiлькiсть пташок на гiлцi з номером $i$. Гарантується, що всi значення ваги пташок попарно рiзнi та $c_1+c_2+\cdots +c_n=m$

Вихідні дані

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

Приклади

Оцінювання

1. ($17$ балів): $1\le n,m,t\le 100$

2. ($12$ балів): $1\le n\le 100$; $1\le m\le 50000$; $1\le t\le 5000$;

3. ($18$ балів): $1\le n\le 100$; $1\le m\le 50000$; $1\le t\le 10^9$;

4. ($24$ бали): $1\le n\le 10^4$; $1\le m\le 50000$; $1\le t\le 10^9$;

5. ($29$ балів): Без додаткових обмежень