Problem Description

There are apartments numbered from $1$ to $N$ arranged in ascending order in a row. Initially, the height of apartment $i$ is $h_i$.

$Q$ operations are performed in sequence. The type of the $i$-th operation is represented by $t_i$, and the details are as follows:

• When $t_i=1$: An integer $v_i$ is given. Increase the height of all apartments with odd numbers by $v_i$.
• When $t_i=2$: An integer $v_i$ is given. Increase the height of all apartments with even numbers by $v_i$.
• When $t_i=3$: Integers $u_i$ and $v_i$ are given. Increase the height of apartment $u_i$ by $v_i$.

After each operation, find the number of integers $i$ satisfying $1 \leq i < N$ such that the heights of apartment $i$ and apartment $i+1$ are equal at the end of the operation.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ h_1 $ $ h_2 $ $\cdots$ $ h_N $ $\mathrm{Query}_{1}$ $\vdots$ $\mathrm{Query}_{Q}$

$\mathrm{Query}_{i}$ is one of the following three:

$ 1 $ $ v_i $

• This indicates performing the operation with $t_i=1$.

$ 2 $ $ v_i $

• This indicates performing the operation with $t_i=2$.

$ 3 $ $ u_i $ $ v_i $

• This indicates performing the operation with $t_i=3$.

Output Format

Output $Q$ lines. On the $q$-th line, output the number of integers $i$ satisfying $1 \leq i < N$ such that the heights of apartment $i$ and apartment $i+1$ are equal at the end of the $q$-th operation.

Sample Input and Output

Sample Input #1

4 2
10 20 30 20
1 10
3 4 20

Sample Output #1

1
2

Sample Input #2

10 20
108 112 112 110 110 109 108 110 111 112
3 4 2
1 1
3 9 1
3 4 2
2 1
1 1
3 7 2
2 1
3 8 2
1 1
2 1
1 1
3 10 2
3 6 1
2 1
3 7 1
1 1
2 1
3 3 2
3 3 2

Sample Output #2

2
2
1
1
2
1
0
3
3
0
3
0
0
0
4
3
1
3
3
2

Notes/Hints

Constraints

• All given inputs are integers.
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq h_i, v_i \leq 10^9$
• $ t_i $ is one of $1, 2, 3$.
• $1 \leq u_i \leq N$

Sample Explanation 1

• Initially, the heights of apartments $1, 2, 3, 4$ are $10, 20, 30, 20$ respectively.
• After the first operation, the heights of apartments with odd numbers change, resulting in heights $20, 20, 40, 20$.
• The number of integers $i$ such that the heights of apartment $i$ and $i+1$ are equal is $1$.
• After the second operation, the height of apartment $4$ changes, resulting in heights $20, 20, 40, 40$.
• The number of integers $i$ such that the heights of apartment $i$ and $i+1$ are equal is $2$.

见题面 Input 部分

见题面 Output 部分