Color sum
Limits: 4 sec., 512 MiB
This statement was translated automatically from Ukrainian.
Zenyk and Marichka have an array \(a\) of \(n\) integers \(a_i\), indexed with integers from 1 to \(n\) inclusive. The numbers are also painted in colors, the \(i\)-th number is initially painted in color \(c_i\).
They want to process \(m\) modifications to this array. There are two types of operations:
1 \(l\) \(r\) \(x\) — find the sum of all numbers in the array in the range \([l, r]\) that are painted in color \(x\).
2 \(p\) \(x\) — repaint the \(p\)-th number into color \(x\).
Your task is — given the list of performed operations, execute them and output all answers to the queries of the first type.
Input
The first line contains two integers \(n\) and \(m\) — the size of the array and the number of performed operations.
The next line contains \(n\) space-separated integers \(a_i\) — the values of the array elements.
The next line contains \(n\) space-separated integers \(c_i\) — the initial colors of the elements.
The next \(m\) lines contain the operations in the order of their execution and in the format described in the statement above.
Output
For each query of the first type, output a single integer on a separate line — the answer to the problem.
Constraints
\(1 \le n, m, c_i, x \le 2 \cdot 10^5\),
\(1 \le a_i \le 10^9\),
\(1 \le l \le r \le n\),
\(1 \le p \le n\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 7 7 6 4 2 3 4 9 1 1 3 2 1 2 2 1 1 1 7 2 1 3 6 1 2 6 3 1 1 7 3 1 2 2 4 2 1 3 1 1 7 3 | 15 3 13 0 19 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|