Cho một mảng gồm \(n\) số nguyên, bạn phải xử lý các thao tác sau:

1. đảo ngược một mảng con
2. tính tổng các giá trị trong một mảng con

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\): kích thước của mảng và số lượng thao tác. Các phần tử mảng được đánh số \(1, 2, \ldots, n\).
• Dòng tiếp theo là \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): nội dung của mảng.
• Cuối cùng, có \(m\) dòng mô tả các thao tác. Mỗi dòng có ba số nguyên \(t\), \(a\) và \(b\). Nếu \(t = 1\), bạn nên đảo ngược một mảng con từ \(a\) đến \(b\). Nếu \(t = 2\), bạn nên tính tổng các giá trị từ \(a\) đến \(b\).

Output

• In đáp án cho mỗi thao tác trong đó \(t = 2\).

Constraints

• \(1 \leq n \leq 2 \cdot 10 ^ 5\)
• \(1 \leq m \leq 10 ^ 5\)
• \(0 \leq x_i \leq 10 ^ 9\)
• \(1 \leq a, b \leq n\)

Example

Sample input

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

Sample output

8
9