题目描述

工作了一段时间后，谢尔盖决定做自己喜欢的事情——绘画。当然，他首先画出了乌日兰德的主树。这个树很特殊：它有 $n$ 根树枝，编号为 $1$ 到 $n$，并按环形排列。第 $1$ 根树枝的下一根是第 $2$ 根，第 $2$ 根的下一根是第 $3$ 根，以此类推，第 $n$ 根树枝的下一根是第 $1$ 根。

初始时，每根树枝上都有若干只鸟，也可能没有鸟。树上一共有 $m$ 只鸟，编号为 $1$ 到 $m$。编号为 $i$ 的鸟的重量为

其中 $a$ 和 $b$ 是给定常数，$x \bmod y$ 表示 $x$ 除以 $y$ 的余数。已知所有鸟的重量两两不同。

还已知第 $i$ 根树枝上初始有 $c_i$ 只鸟：第 $1$ 根树枝上是编号 $1,2,\ldots,c_1$ 的鸟；第 $2$ 根树枝上是编号 $c_1+1,c_1+2,\ldots,c_1+c_2$ 的鸟；依此类推。保证 $c_1+c_2+\cdots+c_n=m$。

每一秒会发生如下过程：所有至少有一只鸟的树枝上，重量最小的那只鸟会同时飞到下一根树枝。

例如，若树有 $3$ 根树枝，第一根上的鸟重量为 $\{1,3,5\}$，第二根为 $\{2,7\}$，第三根为 $\{4,5,6\}$，则一秒后三根树枝上的鸟重量分别为 $\{3,4,5\}$、$\{1,7\}$、$\{2,5,6\}$。

谢尔盖想到了两个数 $k$ 和 $t$。他想知道：在第 $t$ 秒，从第 $k$ 根树枝飞出的鸟的重量是多少？

任务

请根据鸟的初始分布以及 $k,t$，求第 $t$ 秒从编号为 $k$ 的树枝飞出的鸟的重量。

输入格式

第一行包含六个整数 $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$。

它们分别表示树枝数量、鸟的数量、谢尔盖想知道的树枝编号和秒数，以及决定鸟重量的常数。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$0 \le c_i \le m$），其中 $c_i$ 表示初始时第 $i$ 根树枝上的鸟数。

保证所有鸟的重量两两不同，且 $c_1+c_2+\cdots+c_n=m$。

输出格式

输出一个整数，表示第 $t$ 秒从第 $k$ 根树枝飞出的鸟的重量；如果在第 $t$ 秒开始前，第 $k$ 根树枝上没有任何鸟，则输出 $-1$。

输入

4 9 4 7 2 7
3 4 0 2

输出

23

子任务

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 分）无额外限制。