Dãy số

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)}+\cdots +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.

Dữ liệu vào

• 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$.

Dữ liệu ra

In ra một số dòng, mỗi dòng là giá trị cần tính của một thao tác loại $2$, theo đúng thứ tự xuất hiện trong dữ liệu vào.

Ràng buộc

• $n,q\le 2\times {10}^5$;
• $|a_i|\le {10}^9$, $|c|\le {10}^9$;
• Thao tác loại $1$: $1\le i\le n$; thao tác loại $2$: $1\le L<R\le n$.

Subtasks

• Có $40\%$ số test ứng với $40\%$ số điểm có $n,q\le {10}^3$;
• Có $40\%$ số test khác ứng với $40\%$ số điểm có $n,q\le 2\times {10}^5$ 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\le 2\times {10}^5$.

Ví dụ