Lazy Segment Tree

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a binary array under range flips and range inversion-count queries.

Input

The first line contains $N,Q$ and the next line $A_1,\ldots,A_N$. Each query T L R is:

• 1 L R: replace each $A_j$ in the range by $1-A_j$.
• 2 L R: count pairs $i<j$ in the range with $A_i>A_j$.

Output

Print the inversion count for every type 2 query.

Subtasks

• 20 points: $N,Q\le50$.
• 30 points: $N,Q\le5000$.
• 50 points: $N,Q\le2\cdot10^5$, every $A_i$ is 0 or 1.

Examples

Input

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

Output

2
0
1

Explanation

Initially there are two inversions. Flipping positions 3 and 4 makes range $[2,5]$ all ones, hence zero inversions. After the next flip, the first two values are 1 0, giving exactly one inversion.