Cho một dãy gồm N phần tử, và có Q truy vấn. Mỗi truy vấn là một trong hai yêu cầu sau: đổi chỗ hai phần tử ở vị trí u, v trong dãy hiện tại, hoặc tính tổng của một đoạn trong dãy. Bạn hãy thực hiện Q truy vấn đó.

Input:

• Dòng đầu tiên gồm hai số nguyên dương N, Q.

• Dòng thứ hai gồm N số nguyên là các phần tử của dãy.

• Q dòng tiếp theo, mỗi dòng gồm ba số k, u, v biểu diễn một truy vấn, k = 0 là đổi vị trí, k = 1 là loại còn lại, u ≤ v.

Output:

• Với mỗi truy vấn k = 1, in ra câu trả lời.

Giới hạn

• Subtask 1: 50% số điểm có 1 ≤ N, Q ≤ 1000

• Subtask 2: 50% số điểm còn lại có N, Q ≤ 100000

• Các phần tử trong dãy có giá trị tuyệt đối không quá 10000000

Sample Input

5 3

1 2 3 4 5 1 2 4

0 1 3

1 2 4

Sample Output

9

7