There are $n$ stones arranged in a row, with the $i$-th stone initially at position $a_i$.

fpdqwq performs $q$ operations on these stones. In the $i$-th operation, all stones at positions $p$ satisfying $p \pmod{x_i} = y_i$ are moved by one position in the direction $z_i$ (where $z_i=1$ denotes moving in the positive direction, and $z_i=-1$ denotes moving in the negative direction).

After all operations are completed, fpdqwq does not know where the stones have ended up, so they ask you how many stones remain in the position range $[l, r]$ (i.e., positions $l, l+1, \dots, r$).

Input

The first line contains two positive integers $n$ and $q$, separated by a space, representing the number of stones and the number of operations, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the initial positions of all stones.

The next $q$ lines each contain three integers $x_i, y_i, z_i$, representing an operation.

The last line contains two positive integers $l$ and $r$, representing the queried range.

Output

Output a single integer representing the answer.

Examples

Input 1

5 3
4 1 4 1 2
1 0 -1
4 0 -1
4 2 -1
0 5

Output 1

3

Note 1

The first operation moves all stones. The second operation moves the 2nd and 4th stones. The last operation does not move any stones. Finally, the 1st, 3rd, and 5th stones are located within $[0, 5]$.

Constraints

For $24\%$ of the data: $n \leq 100, q \leq 100$

For $60\%$ of the data: $n \leq 5000, q \leq 5000$

For $97\%$ of the data: $n \leq 100000, q \leq 100000$

For $100\%$ of the data: $1 \leq n \leq 500000, 0 \leq q \leq 500000, 0 \leq a_i \leq 10^9, 0 \leq y_i < x_i \leq 10^9, 0 \leq l \leq r \leq 10^9, |z_i|=1$