問題文

要素数 $N$ の数列 $A = \{ a_1, a_2, ... , a_N \} \ $ が与えられます。

以下の 2 種類のクエリが合計 $Q$ 個与えられるので、それらを順番に処理してください。

• $1 \ l \ r \ x$

  • 各 $i \in [l, r]$ について、$a_i$ を $a_i + x$ で置き換える



• $2 \ l \ r$

  • 以下のように定義される $F(l, r) \ (l \le r)$ の値を出力する
  • $ 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} $

入力

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

1 行目に数列の長さを表す整数 $N$ とクエリの数を表す整数 $Q$ がこの順で半角スペース区切りで与えられます。

2 行目には $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1 \le i \le N)$ の整数は、初期の $a_i$ の値を表します。

続く $Q$ 行のうちの $i$ 行目 $(1 \le i \le Q)$ には、$i$ 番目のクエリが与えられます。

各クエリは

• $1 \ l \ r \ x$

• $2 \ l \ r$

のいずれかの形式で与えられます。

入力は全部で $Q + 2$ 行となり、以下の制約を満たします。

• 入力は全て整数
• $1 \le N, Q \le 10^5$
• $1 \le a_i \le 10^9 \ \ (1 \le i \le N)$
• クエリ1
  • $1 \le l \le r \le N$
  • $1 \le x \le 10^9$
• クエリ2
  • $1 \le l \le r \le N$
• クエリ2 は 1 つ以上存在する

出力

各クエリ2に対して、$ F(l, r) $ の値を改行区切りで出力してください。

サンプル

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

2
3
1