A. An Easy Geometry Problem
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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\leq n$$$, $$$i-r \gt 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\leq r\leq 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\leq i\leq 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\leq n,q\leq 2\times 10^5$$$, $$$|k|,|b|\leq 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|\leq 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\leq l\leq r\leq n$$$ and $$$|v|\leq 10^3$$$. For each query of the second type, it is guaranteed that $$$1\leq i\leq n$$$.

Output

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

Example
Input
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
0
2
0