{"code":"cscqueries","name":"Truy vấn tổng cấp số cộng","description":"Cho dãy $a_{1}, a_{2}, \\ldots, a_{n}$ gồm các số tự nhiên. Cần thực hiện $q$ truy vấn, mỗi truy vấn là một trong hai thao tác sau:\r\n\r\n1. Nhập vào hai số nguyên $i, u$  $(1 \\leq i \\leq n, 0 \\leq u \\leq 10^{9})$. Cập nhật $a_{i} = u$.\r\n2. Nhập vào hai số nguyên $p, k$ $(1 \\leq p, k \\leq n)$. Hãy tính tổng $a_{p} + a_{p + k} + a_{p + 2k} + \\ldots + a_{p + uk}$ với u là số nguyên lớn nhất sao cho $p + uk \\leq n$.\r\n\r\n#### Input\r\n- Dòng đầu tiên chứa một số nguyên dương $n$ $(n \\leq 2 \\times 10^{5})$.\r\n+ Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \\ldots, a_{n}$ $(0 \\leq a_{i} \\leq 10^{9})$.\r\n- Dòng thứ ba chứa một số nguyên dương $q$ $(q \\leq 2 \\times 10^{5})$, số lượng truy vấn.\r\n- $q$ dòng tiếp theo, mỗi dòng có một trong hai dạng sau:\r\n    - $1$ $i$ $u$: cập nhật $a_{i} = u$.\r\n    - $2$ $p$ $k$: in ra tổng $a_{p} + a_{p + k} + a_{p + 2k} + \\ldots$.\r\n\r\n#### Output\r\n- Với mỗi truy vấn 2, in ra đáp số trên một dòng.\r\n\r\n#### Scoring\r\n- Subtask $1$ ($20\\%$ số điểm): $n, q \\leq 2000$.\r\n- Subtask $2$ ($40\\%$ số điểm): đều là loại 2 (không có truy vấn cập nhật).\r\n- Subtask $3$ ($40\\%$ số điểm): không có rằng buộc gì thêm.\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        8\r\n        6 7 1 3 9 0 7 5\r\n        5\r\n        2 1 1\r\n        2 3 2\r\n        1 5 3\r\n        2 1 1\r\n        2 3 2\r\n        ```    \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        38\r\n        17\r\n        32\r\n        11\r\n        ```    \r\n    ??? warning \"Note\"\r\n        - Trong truy vấn 1, ta cần in ra $a_{1} + a_{2} + ... + a_{8} = 38$.\r\n        - Trong truy vấn 2, ta cần in ra $a_{3} + a_{5} + a_{7} = 1 + 9 + 7 = 17$.\r\n        - Trong truy vấn 3, ta cập nhật $a_{5} = 3$.","points":650.0,"partial":false,"time_limit":2.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}