Xét dãy số nguyên ~a_1, a_2, \dots, a_n~ và ~q~ thao tác thuộc một trong hai loại thao tác sau:

• Thao tác loại ~1~ có dạng ~1\ i\ c~ với ~1 \le i \le n~ và ~|c| \le 10^9~, tức là thay đổi giá trị ~a_i~ thành ~c~;

• Thao tác loại ~2~ có dạng ~2\ L\ R~ với ~1 \le L < R \le n~, tức là tính tổng ~a_L + a_{f(L)} + a_{L+1} + a_{f(L+1)} + \dots + a_R + a_{f(R)}~, trong đó ~f(i)~ là ước lẻ lớn nhất của ~i~ ~(1 \le i \le n)~.

Yêu cầu: Thực hiện lần lượt ~q~ thao tác, với mỗi thao tác loại ~2~ ghi ra giá trị cần tính tổng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~;

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9)~;

• Dòng thứ ~k~ ~(1 \le k \le q)~ trong ~q~ dòng tiếp theo chứa ba số nguyên mô tả thao tác thứ ~k~.

Output

Gồm một số dòng, mỗi dòng tương ứng là giá trị cần tính của thao tác loại ~2~, lần lượt tương ứng trong dữ liệu vào.

Scoring

Sample Input 1

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

Sample Output 1

16
7

Notes

~16 = a_1 + a_1 + a_2 + a_1 + a_3 + a_3 + a_4 + a_1 = 1 + 1 + 2 + 1 + 3 + 3 + 4 + 1~.

~7 = a_3 + a_3 + a_4 + a_1 = 3 + 3 + 0 + 1~.