長さ $n$ の整数列 $\{A_i\}$ と、2つの整数 $k, b$ で表される直線 $y = kx + b$ が与えられます。

中心 $i$ における整数半径 $r$ が「良い」とは、$i+r \le n$ かつ $i-r > 0$ であり、かつ $A_{i+r} - A_{i-r} = kr + b$ が成り立つことを指します。

$\text{rad}(i)$ を、すべての $1 \le r \le r_0$ に対して $r$ が中心 $i$ における良い半径となるような最大の整数 $r_0$ と定義します。

以下の2種類のクエリを処理してください。

• $1 \ l \ r \ v$: すべての $l \le i \le r$ に対して、$A_i$ を $v$ 増加させる。
• $2 \ i$: $\text{rad}(i)$ を計算する。

入力

入力の1行目には、4つの整数 $n, q, k, b$ ($1 \le n, q \le 2 \times 10^5$, $|k|, |b| \le 10^3$) が与えられ、それぞれ整数列の長さ、クエリの数、直線のパラメータを表します。

2行目には、$n$ 個の整数 $A_1, A_2, \dots, A_n$ ($|A_i| \le 10^3$) が与えられ、整数列を表します。

続く $q$ 行には、クエリが与えられます。1種類目のクエリについては、$1 \le l \le r \le n$ かつ $|v| \le 10^3$ であることが保証されます。2種類目のクエリについては、$1 \le i \le n$ であることが保証されます。

出力

2種類目のクエリごとに、答えを1行で出力してください。

入出力例

入力 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

出力 1

1
0
2
0