B. Wonderful Array
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a positive integer $$$k$$$ and $$$k$$$ positive integers $$$a_0, a_1, ... , a_{k-1}$$$.

Then three positive integers $$$n, m, x$$$ are given.

Let $$$b_0,b_1...b_n$$$ be the following sequence of $$$n$$$ numbers:

$$$b_i =\begin {cases} x, & i = 0\\ b_{i-1} + a_{(i-1) \mod k}, & 0 \lt i \le n\end {cases}$$$

Find the number of $$$i(0 \le i \lt n)$$$ such that $$$(b_i \mod m) \le (b_{i+1} \mod m)$$$.

Input

The first line contains an integer $$$k$$$ $$$(1 \le k \le 10^6)$$$.

The second line contains $$$k$$$ integers $$$a_0, a_1, ... , a_{k-1}$$$ $$$(1 \le a_i \le 10^9)$$$.

The third line contains three integers $$$n,m,x$$$ $$$(1 \le n \le 10^9,1 \le m \le 10^9,1 \le x \le 10^9)$$$.

Output

Output a single integer, denoting the answer.

Example
Input
3
2 4 3
4 7 5
Output
2
Note

$$$b_0 = 5$$$, $$$b_1 = b_0 + a_0 = 7$$$, $$$b_2 = b_1 + a_1 =11$$$, $$$b_3 = b_2 + a_2 = 14$$$, $$$b_4 = b_3 + a_0 = 16$$$

$$$b_1 \mod 7 = 0$$$ $$$\le$$$ $$$4 = b_2 \mod 7$$$

$$$b_3 \mod 7 = 0$$$ $$$\le$$$ $$$2 = b_4 \mod 7$$$