Quý đang có \(n\) đồng xu trên bàn, mỗi đồng xu đang ở trạng thái lật hoặc ngửa (\(0\) hoặc \(1\)). Với mỗi đoạn con \((l, r)\) trong mảng \((1 \leq l \leq r \leq n)\), Quý định nghĩa đoạn \((l, r)\) là đoạn con đồng xu xen kẽ nếu mỗi đồng xu trong đoạn khác với các đồng xu kề của nó. Nói cách khác, đoạn \((l, r)\) là đoạn con đồng xu xen kẽ nếu \(a_i \neq a_{i+1}, \ \forall \ l \leq i < r\). Ví dụ, đoạn \((2, 4)\) hay \([0, 1, 0]\) là đoạn con đồng xu xen kẽ của mảng \([0, 0, 1, 0, 0]\).

Quý có 2 loại truy vấn như sau:

• \(1\ l\ r\): Lật ngược tất cả các đồng xu trong đoạn \((l, r)\) lại. Nói cách khác, gán \(a_i = 1 - a_i, \ \forall \ l \leq i \leq r\)
• \(2\ l\ r\): Đếm xem có bao nhiêu cặp \(x, y\) \((l \leq x \leq y \leq r)\) mà đoạn con \((x, y)\) là đoạn con đồng xu xen kẽ.

Quý đang chơi vui với các đồng xu nên cậu không muốn nghỉ chơi giữa chừng để code. Do đó bạn hãy giúp Quý giải quyết bài toán này nhé.

Input

• Dòng đầu tiên chứa 2 số nguyên \(n, q\) \((1 \leq n \leq 2 \cdot 10^5,\ 1 \leq q \leq 2 \cdot 10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_i\) \((a_i \in [0, 1])\).
• \(q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(t_i,\ l_i,\ r_i\) thể hiện truy vấn thứ \(i\) \((t_i \in [1, 2],\ 1 \leq l_i \leq r_i \leq n)\).

Output

• Với mỗi truy vấn loại 2, in ra kết quả là số lượng đoạn con đồng xu xen kẽ trong đoạn \((l, r)\).

Example

3 1
1 1 0
2 1 3

4

20 20
0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1 0 0
1 1 10
2 2 7
1 3 15
2 1 9
1 4 9
2 1 13
1 13 15
2 10 20
1 1 5
2 2 10
1 15 17
2 15 18
1 1 3
2 4 6
1 15 19
2 1 6
1 15 15
2 10 17
1 1 8
2 15 19

16
16
21
14
12
6
4
9
10
8