Tree
After a productive day, Serhiy decided to indulge in his favorite pastime—drawing. Naturally, he began by sketching the Main Uzhland Tree. This tree is unique: it has n branches, numbered from 1 to n, arranged in a cycle. This means the branch following the first is the second, the one after the second is the third, and so on, with the branch following the n-th being the first again.
Initially, each branch has a certain number of birds perched on it (some branches may have no birds at all). There are m birds in total, numbered from 1 to m. Each bird has a specific weight, calculated as (a[i] + b) mod (10^9 + 7), where a and b are constants, and x mod y represents the remainder of dividing x by y. All bird weights are distinct. On branch i, there are initially c[i] birds, such that branch 1 has birds numbered 1, 2, ..., c[1], branch 2 has birds numbered c[1] + 1, c[1] + 2, ..., c[1] + c[2], and so forth. It is guaranteed that the sum of all c[i] equals m.
Every second, the lightest bird from each branch with at least one bird flies to the next branch. For example, if the tree has 3 branches, and the first branch has birds with weights {1, 3, 5}, the second branch has {2, 7}, and the third branch has {4, 5, 6}, then after one second, the birds' weights on the branches will be {3, 4, 5}, {1, 7}, and {2, 5, 6} respectively. Serhiy is curious about two numbers, k and t. He wants to know the weight of the bird that will fly from branch number k at the second numbered t.
Task
Write a program that, given the initial distribution of birds on the tree and the numbers k and t, determines the weight of the bird that will fly from branch number k at the second numbered t.
Input Data
The first line of the input contains six integers: 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). These represent the number of branches, the total number of birds, the numbers Serhiy is interested in, and the constants for calculating bird weights, respectively.
The second line contains n integers c[1], c[2], ..., c[n] (0 ⩽ c[i] ⩽ m), where c[i] is the initial number of birds on branch i. It is guaranteed that all bird weights are unique and that the sum of all c[i] equals m.
Output Data
In the output file, print one integer: the weight of the bird that will fly from branch number k at the second numbered t, or −1 if there will be no birds on this branch before the second numbered t.
Evaluation
Subtask Points Additional Constraints Required Subtasks
0 0 Tests from the condition -
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 No additional constraints 0, 1, 2, 3, 4