You are given an integer sequence $\{A_i\}$ of length $n$ and a line $y = kx + b$ denoted by two integers $k, b$.

We say that an integer radius $r$ of center $i$ is good if and only if $i+r \le n$, $i-r > 0$, and $A_{i+r} - A_{i-r} = kr + b$.

We define the $\text{rad}(i)$ as the maximum integer $r_0$ so that for every $1 \le r \le r_0$, $r$ is a good radius of center $i$.

You need to process queries of two types:

• $1 \ l \ r \ v$: for every $l \le i \le r$, increase $A_i$ by $v$;
• $2 \ i$: calculate $\text{rad}(i)$.

Input

The first line of input contains four integers $n, q, k$, and $b$ ($1 \le n, q \le 2 \times 10^5$, $|k|, |b| \le 10^3$), denoting the length of the integer sequence, the number of queries, and the line.

The second line contains $n$ integers $A_1, A_2, \dots, A_n$ ($|A_i| \le 10^3$), denoting the integer sequence.

The next $q$ lines each contain a query, formatted as clarified in the statement. For each query of the first type, it is guaranteed that $1 \le l \le r \le n$ and $|v| \le 10^3$. For each query of the second type, it is guaranteed that $1 \le i \le n$.

Output

For every query of type 2, output a line denoting the answer.

Examples

Input 1

6 6 6 2
1 5 9 10 15 18
2 2
1 3 3 -3
2 2
1 3 4 3
2 3
2 4

Output 1

1
0
2
0