Xét dãy số nguyên a₁, a₂, …, aₙ 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 ≤ i ≤ n và |c| ≤ 10⁹, tức là thay đổi giá trị aᵢ thành c

• Thao tác loại 2 có dạng: 2 L R với 1 ≤ L < R ≤ n, tức là tính tổng:

\[a_L + a_{f(L)} + a_{L+1} + a_{f(L+1)} + \cdots + a_R + a_{f(R)}\]

trong đó f(i) là ước lẻ lớn nhất của i (1 ≤ i ≤ 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₁, a₂, …, aₙ (|aᵢ| ≤ 10⁹);
• Dòng thứ k (1 ≤ k ≤ 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.

Ràng buộc

• Có 40% số test ứng với 40% số điểm có n, q ≤ 10³;
• Có 40% số test khác ứng với 40% số điểm có n, q ≤ 2 × 10⁵ và không có thao tác loại 1;
• Có 20% số test còn lại ứng với 20% số điểm có n, q ≤ 2 × 10⁵.

Sample Input

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

Sample Output

16
7

Giải thích

Ta có f(1) = 1, f(2) = 1, f(3) = 3, f(4) = 1.

Với truy vấn đầu tiên:

\[16 = a₁ + a_{f(1)} + a₂ + a_{f(2)} + a₃ + a_{f(3)} + a₄ + a_{f(4)}\]

\[= 1 + 1 + 2 + 1 + 3 + 3 + 4 + 1.\]

Sau thao tác 1 4 0, ta có a₄ = 0.

Với truy vấn thứ hai:

\[7 = a₃ + a_{f(3)} + a₄ + a_{f(4)}\]

\[= 3 + 3 + 0 + 1.\]