给定一个长度为 $n$ 的整数序列 $\{A_i\}$ 以及由两个整数 $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)$ 为满足以下条件的最大整数 $r_0$：对于所有 $1 \le r \le r_0$，$r$ 都是中心为 $i$ 的好半径。

你需要处理两种类型的查询： $1 \ l \ r \ v$：对于每个 $l \le i \le r$，将 $A_i$ 增加 $v$； $2 \ i$：计算 $\text{rad}(i)$。

输入格式

第一行包含四个整数 $n, q, k$ 和 $b$ ($1 \le n, q \le 2 \times 10^5$，$|k|, |b| \le 10^3$)，分别表示整数序列的长度、查询次数以及直线的参数。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$ ($|A_i| \le 10^3$)，表示该整数序列。

接下来的 $q$ 行，每行包含一个查询，格式如题目描述所述。对于第一类查询，保证 $1 \le l \le r \le n$ 且 $|v| \le 10^3$。对于第二类查询，保证 $1 \le i \le n$。

输出格式

对于每个第二类查询，输出一行表示答案。

样例

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