Hàm Zigzag

Với mỗi số nguyên $z\ge 2$, định nghĩa dãy Zigzag $S_1^z,S_2^z,S_3^z,\dots$ có chu kỳ $2(z-1)$ như sau: các giá trị đầu tiên trong một chu kỳ là $1,2,3,\dots ,z,z-1,z-2,\dots ,2$, rồi lặp lại. Ví dụ với $z=3$, dãy bắt đầu là $1,2,3,2,1,2,3,2,1,\dots$

Cho mảng $a$ gồm $n$ số nguyên. Định nghĩa hàm Zigzag với tham số $(l,r,z)$ trong đó $1\le l\le r\le n$ và $z\ge 2$:

$$Z(l,r,z)=\sum _{i=l}^r{a}_i·S_{i-l+1}^z$$

Bạn cần xử lý $m$ thao tác trên mảng:

1. Gán $(p,v)$: gán $a_p\leftarrow v$.
2. Truy vấn Zigzag $(l,r,z)$: tính và in ra giá trị $Z(l,r,z)$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Dòng thứ ba chứa số nguyên $m$ — số lượng thao tác.
• $m$ dòng tiếp theo, mỗi dòng mô tả một thao tác:
  • Bắt đầu bằng số nguyên $t_i\in \{1,2\}$.
  • Nếu $t_i=1$: tiếp theo là hai số nguyên $p_i,v_i$ ($1\le p_i\le n$, $1\le v_i\le {10}^9$).
  • Nếu $t_i=2$: tiếp theo là ba số nguyên $l_i,r_i,z_i$ ($1\le l_i\le r_i\le n$, $2\le z_i\le 6$).

Dữ liệu ra

Với mỗi thao tác loại $2$, in giá trị $Z(l,r,z)$ trên một dòng riêng, theo đúng thứ tự xuất hiện của các thao tác.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$
• $1\le m\le {10}^5$
• $2\le z_i\le 6$

Ví dụ