{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/NOV14/mandarin/FNCS.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/NOV14/russian/FNCS.pdf\"\u003eRussian\u003c/a\u003e.\r\n\r\nChef has an array $A$ of $N$ numbers. He also has $N$ functions. The $i^{th}$ function will return the sum of all $A_j$ where ($L_{i} \\leq j \\leq R_{i}$). You have to answer $Q$ queries of two types:\r\n\r\n$1$ $x$ $y$ - Change the $x^{th}$ element of the array to $y$. \r\n\r\n$2$ $l$ $r$ - Print the sum of all functions from $l$ to $r$.\r\n\r\nCan you solve this problem?\r\n\r\n### Input\r\n- First line contains a single integer - $N$, the length of the array and the number of functions\r\n- Next line contains $N$ space separated integers, the $i^{th}$ of which is $A_i$\r\n- The next N lines each contain two space separated integers, the $i^{th}$ line contains $L_{i}$ and $R_{i}$. \r\n- The next line contains a single integer $Q$\r\n- The next $Q$ lines contain queries in the format described aboce.\r\n\r\n### Output\r\nFor each query of type $2$, output the answer on a separate line.\r\n\r\n### Constraints\r\n- $ 1 \\leq N, Q \\leq 10^{5}$\r\n- $ 1 \\leq A_{i} \\leq 10^{9}$\r\n- $ 1 \\leq L_{i} \\leq R(i) \\leq N$\r\n- $ 1 \\leq x \\leq N$\r\n- $ 1 \\leq y \\leq 10^{9}$\r\n- $ 1 \\leq l \\leq r \\leq N$\r\n\r\n### Subtasks\r\n\r\n**Subtask 1: (10 points)** \r\n- $N \\leq 1000$\r\n- $Q \\leq 1000$\r\n\r\n**Subtask 2: (10 points)**\r\n- $R_i - L_i \\leq 10$\r\n- All $x$ are distinct\r\n\r\n**Subtask 3: (80 points)**\r\n- No additional constraints\r\n\r\n\r\n### Example Input\r\n```\r\n5\r\n1 2 3 4 5\r\n1 3\r\n2 5\r\n4 5\r\n3 5\r\n1 2\r\n4\r\n2 1 4\r\n1 3 7\r\n2 1 4\r\n2 3 5\r\n```\r\n\r\n### Example Output\r\n```\r\n41\r\n53\r\n28\r\n```\r\n\r\n### Explanation\r\nFunctions values initially : \r\n- $F[1] \u003d 1+ 2 + 3 \u003d 6$\r\n- $F[2] \u003d 2 + 3 + 4 + 5 \u003d 14$\r\n- $F[3] \u003d 4+5 \u003d 9$\r\n- $F[4] \u003d 3+4+5 \u003d 12$\r\n- $F[5] \u003d 1+2 \u003d 3$\r\n\r\nQuery $1: F[1] + F[2] + F[3] + F[4] \u003d 41$\r\n\r\nAfter the update , the functions are :\r\n- F[1] \u003d 10\r\n- F[2] \u003d 18 \r\n- F[3] \u003d 9\r\n- F[4] \u003d 16\r\n- F[5] \u003d 3\r\n\r\nQuery $3: F[1] + F[2] + F[3] + F[4] \u003d 53$\r\n\r\nQuery $4: F[3]+F[4]+F[5] \u003d 28$"}}]}