Кольорова сума
Limits: 4 sec., 512 MiB
Зеник і Марічка мають масив \(a\) із \(n\) цілих чисел \(a_i\), пронумерованих цілими числами від 1 до \(n\) включно. Числа також пофарбовані в кольори, \(i\)-те число початково пофарбовано в колір \(c_i\).
Вони хочуть опрацювати \(m\) модифікацій до цього масиву. Існує два види операцій:
1 \(l\) \(r\) \(x\) — знайти суму усіх чисел масиву на проміжку \([l, r]\), які пофарбовані в колір \(x\).
2 \(p\) \(x\) — перефарбувати \(p\)-те число в колір \(x\).
Ваше завдання — за заданим списком виконаних операцій, виконати їх та вивести усі відповіді на запити першого типу.
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — розмір масиву та кількість виконаних операцій.
У наступному рядку задано \(n\) цілих чисел \(a_i\) розділених пробілами — значення елементів масиву.
У наступному рядку задано \(n\) цілих чисел \(c_i\) розділених пробілами — початкові кольори елементів.
У наступних \(m\) рядках задано операції в порядку їх виконання та в форматі, описаному в умові вище.
Output
Для кожного запиту першого типу в окремому рядку виведіть одне ціле число — відповідь на задачу.
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 |
|---|