Problem Statement

You are given a sequence $A = \{ a_1, a_2, ... , a_N \} \ $ with $N$ elements.

A total of $Q$ queries of the following 2 types are given. Process them in order.

• $1 \ l \ r \ x$

  • For each $i \in [l, r]$, replace $a_i$ with $a_i + x$.



• $2 \ l \ r$

  • Output the value of $F(l, r) \ (l \le r)$, defined as follows.
  • $ F(l, r) = \begin{cases} 1 & (l = r)\\ G(a_l, a_{l + 1}) + F(l + 1, r) & (l \lt r) \end{cases} $
  • $ G(x, y) = \begin{cases} 0 & (x = y)\\ 1 & (x \neq y) \end{cases} $

Input

$N \ Q$
$a_1 \ a_2 \ \cdots \ a_N$
$query_1$
$query_2$
$\cdots$
$query_Q$

The first line contains an integer $N$ representing the length of the sequence and an integer $Q$ representing the number of queries, in this order, separated by a space.

The second line contains $N$ space-separated integers, where the $i$-th integer $(1 \le i \le N)$ represents the initial value of $a_i$.

The $i$-th $(1 \le i \le Q)$ of the following $Q$ lines contains the $i$-th query.

Each query is given in one of the following formats:

• $1 \ l \ r \ x$

• $2 \ l \ r$

The input consists of $Q + 2$ lines in total and satisfies the following constraints.

• All input values are integers.
• $1 \le N, Q \le 10^5$
• $1 \le a_i \le 10^9 \ \ (1 \le i \le N)$
• Query 1
  • $1 \le l \le r \le N$
  • $1 \le x \le 10^9$
• Query 2
  • $1 \le l \le r \le N$
• There is at least one Query 2.

Output

For each Query 2, output the value of $ F(l, r) $, separated by newlines.

Sample

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

2
3
1