Cho dãy ~a~ có ~n~ phần tử, hãy thực hiện các truy vấn sau:

• ~1\ l\ r~: Đảo ngược đoạn phần tử ~[l, r]~ của dãy ~a~.
• ~2\ l\ r~: Tính tổng các giá trị của đoạn ~[l, r]~ của dãy ~a~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n \le 2 \cdot 10^5, 1 \le m \le 10^5)~— kích thước và số lượng truy vấn.
• Dòng tiếp theo chứa ~n~ số nguyên không âm ~a_1, a_2, a_3, \dots, a_n~ ~(0 \le a_i \le 10^9)~.
• ~m~ dòng tiếp theo chứa những truy vấn có dạng ~t~, ~l~ và ~r~ ~(1 \le t \le 2, 1 \le l \le r \le n)~.

Output

In ra đáp án cho mỗi truy vấn ~t=2~.

Sample Input 1

8 3
2 1 3 4 5 3 4 4
2 2 4
1 3 6
2 2 4

Sample Output 1

8
9

Notes

• Mảng ~a~ ban đầu là ~\{2, 1, 3, 4, 5, 3, 4, 4\}~.
• Truy vấn ~1~ hỏi tổng phần tử trong đoạn ~[2, 4]~ bằng ~8~.
• Mảng ~a~ sau khi thực hiện truy vấn ~2~ là ~\{2, 1, 3, 5, 4, 3, 4, 4\}~.
• Truy vấn ~3~ hỏi tổng phần tử trong đoạn ~[2, 4]~ bằng ~9~.