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 3 types are given. Process them in order.

• $1 \ l \ r$

  • For each $i \in [l, r]$, replace $a_i$ with $1$ if it is odd, and with $0$ if it is even.



• $2 \ l \ r \ x$

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



• $3 \ l \ r$

  • Output the value of $\displaystyle \sum_{i \in [l, r]} a_i $.

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$ integers separated by spaces, 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$

• $2 \ l \ r \ x$

• $3 \ l \ r$

That is the complete list of query formats.

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$
• Query 2
  • $1 \le l \le r \le N$
  • $1 \le x \le 10^5$
• Query 3
  • $1 \le l \le r \le N$
• There is at least one query of type 3.

Output

For each query of type 3, output the value of $ \displaystyle \sum_{i \in [l, r]} a_i $, separated by newlines.

Sample

5 7
1 2 3 4 5
3 1 5
1 1 5
3 1 5
2 2 4 3
3 1 5
1 1 5
3 1 5

15
3
12
4