F. Прыжки по массиву
ограничение по времени на тест
8 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив целых чисел $$$a$$$ размера $$$n$$$ и перестановка $$$p$$$ размера $$$n$$$. К вам приходят $$$q$$$ запросов трех типов:

  1. Даны числа $$$l$$$ и $$$r$$$. Требуется посчитать сумму чисел массива $$$a$$$ на отрезке c $$$l$$$ по $$$r$$$: $$$\sum\limits_{i=l}^{r} a_i$$$.
  2. Даны числа $$$v$$$ и $$$x$$$. Давайте представим $$$p$$$ в виде ориентированного графа, у которого $$$n$$$ вершин и $$$n$$$ рёбер $$$i \to p_i$$$. Пусть $$$C$$$ — это множество вершин, которые достижимы из $$$v$$$ в графе. Требуется прибавить число $$$x$$$ ко всем $$$a_u$$$ таким, что $$$u$$$ лежит в $$$C$$$.
  3. Даны индексы $$$i$$$ и $$$j$$$. Вам нужно поменять местами значения $$$p_i$$$ и $$$p_j$$$.
Граф, получаемый из перестановки $$$[2, 3, 1, 5, 4]$$$.

От вас требуется вывести ответы на все запросы $$$1$$$ вида.

Входные данные

В первой строке находится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер массива и перестановки.

Во второй строке входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^8 \le a_i \le 10^8$$$).

В третьей строке входных данных находится $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$).

В четвертой строке находится единственное целое число $$$q$$$ — количество запросов ($$$1 \le q \le 2 \cdot 10^5$$$).

В следующих $$$q$$$ строках заданы запросы. В $$$i$$$-й строке находится целое число $$$t_i$$$ ($$$1 \le t_i \le 3$$$) — тип запроса.

  • Если $$$t_i = 1$$$, то в $$$i$$$-й строке заданы еще два целых числа: $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n$$$).
  • Если $$$t_i = 2$$$, то в $$$i$$$-й строке заданы еще два целых числа: $$$v$$$, $$$x$$$ ($$$1 \le v \le n$$$, $$$-10^8 \le x \le 10^8$$$).
  • Если $$$t_i = 3$$$, то в $$$i$$$-й строке заданы еще два целых числа: $$$i$$$, $$$j$$$ ($$$1 \le i, j \le n$$$).
Выходные данные

Для каждого запроса первого типа выведите единственное целое число — ответ на запрос.

Примеры
Входные данные
5
6 9 -5 3 0
2 3 1 5 4
6
1 1 5
2 1 1
1 1 5
3 1 5
2 1 -1
1 1 5
Выходные данные
13
16
11
Входные данные
8
-15 52 -4 3 5 9 0 5
2 4 6 8 1 3 5 7
10
2 2 2
2 5 -1
1 1 8
1 1 5
1 5 8
3 1 6
2 1 50
1 1 8
2 6 -20
1 1 8
Выходные данные
61
45
22
461
301
Входные данные
1
1
1
1
1 1 1
Выходные данные
1
Примечание

Рассмотрим первый тест.

Граф, получаемый из изначальной перестановки.

В первом тесте $$$6$$$ запросов.

  1. Сумма на отрезке с $$$1$$$ по $$$5$$$ это $$$a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 3 + 0 = 13$$$.
  2. Из вершины $$$1$$$ достижимы вершины $$$\{1, 2, 3\}$$$. Получается, что после этого запроса массив $$$a$$$ будет выглядеть так: $$$[7, 10, -4, 3, 0]$$$.
  3. Сумма на отрезке с $$$1$$$ по $$$5$$$ это $$$a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 3 + 0 = 16$$$.
  4. После запроса $$$p = [4, 3, 1, 5, 2]$$$.
    Граф, получаемый из перестановки после четвёртого запроса.
  5. Из вершины $$$2$$$ достижимы вершины $$$\{1, 2, 3, 4, 5\}$$$. Получается, что после этого запроса массив $$$a$$$ будет выглядеть так: $$$[6, 9, -5, 2, -1]$$$.
  6. Сумма на отрезке с $$$1$$$ по $$$5$$$ это $$$a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 2 + (-1) = 11$$$.