Кольорова сума

Обмеження: 4 сек., 512 МіБ

Зеник і Марічка мають масив \(a\) із \(n\) цілих чисел \(a_i\), пронумерованих цілими числами від 1 до \(n\) включно. Числа також пофарбовані в кольори, \(i\)-те число початково пофарбовано в колір \(c_i\).

Вони хочуть опрацювати \(m\) модифікацій до цього масиву. Існує два види операцій:

• 1 \(l\) \(r\) \(x\) — знайти суму усіх чисел масиву на проміжку \([l, r]\), які пофарбовані в колір \(x\).

• 2 \(p\) \(x\) — перефарбувати \(p\)-те число в колір \(x\).

Ваше завдання — за заданим списком виконаних операцій, виконати їх та вивести усі відповіді на запити першого типу.

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(m\) — розмір масиву та кількість виконаних операцій.

У наступному рядку задано \(n\) цілих чисел \(a_i\) розділених пробілами — значення елементів масиву.

У наступному рядку задано \(n\) цілих чисел \(c_i\) розділених пробілами — початкові кольори елементів.

У наступних \(m\) рядках задано операції в порядку їх виконання та в форматі, описаному в умові вище.

Вихідні дані

Для кожного запиту першого типу в окремому рядку виведіть одне ціле число — відповідь на задачу.

Обмеження

\(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\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (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