题目描述

题目译自 Ukrainian Olympiads in Informatics 2018 Stage 4 Day1 T4. Сергiй та дерево

在辛勤工作之后，谢尔盖决定从事自己喜爱的活动——绘画。当然，他首先画了乌克兰主树。这棵树很特别：它有 $n$ 个树枝，编号从 $1$ 到 $n$，并且这些树枝是循环排列的，即第一个树枝的下一个是第二个，第二个的下一个是第三个，依此类推，第 $n$ 个树枝的下一个是第一个。

最初，每个树枝上都有一定数量的鸟儿（也可能没有任何鸟儿）。树上总共有 $m$ 只鸟儿，编号从 $1$ 到 $m$。每只鸟儿都有自己的重量：编号为 $i$ 的鸟儿的重量为 $(a_i + b) \mod (10^9 + 7)$，其中 $a$ 和 $b$ 是某些常数，$x \mod y$ 表示 $x$ 除以 $y$ 的余数。已知所有鸟儿的重量值两两不同。此外，已知编号为 $i$ 的树枝上最初有 $c_i$ 只鸟儿，其中编号为 $1$ 的树枝上的鸟儿编号为 $1, 2, \dots, c_1$，编号为 $2$ 的树枝上的鸟儿编号为 $c_1 + 1, c_1 + 2, \dots, c_1 + c_2$，依此类推。保证 $c_1 + c_2 + \dots + 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 \leq n \leq 10^4, 1 \leq m \leq 2 \cdot 10^6, 1 \leq k \leq n, 1 \leq t \leq 10^9, 1 \leq a < 10^9 + 7, 0 \leq b < 10^9 + 7)$，分别表示树枝数量、树上鸟儿总数、谢尔盖想出的数字以及用于计算鸟儿重量的常数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ $(0 \leq c_i \leq m)$，其中 $c_i$ 表示编号为 $i$ 的树枝上最初的鸟儿数量。保证所有鸟儿的重量值两两不同，且 $c_1 + c_2 + \dots + c_n = m$。

输出格式

输出文件应包含一个整数，表示在第 $t$ 秒从编号为 $k$ 的树枝飞走的鸟儿的重量；如果在第 $t$ 秒之前该树枝上没有任何鸟儿，则输出 $-1$。

4 9 4 7 2 7
3 4 0 2

23

数据范围与提示

详细子任务附加限制及分值如下表所示：