Вам задан массив целых чисел $$$a$$$ размера $$$n$$$ и перестановка $$$p$$$ размера $$$n$$$. К вам приходят $$$q$$$ запросов трех типов:
- Даны числа $$$l$$$ и $$$r$$$. Требуется посчитать сумму чисел массива $$$a$$$ на отрезке c $$$l$$$ по $$$r$$$: $$$\sum\limits_{i=l}^{r} a_i$$$.
- Даны числа $$$v$$$ и $$$x$$$. Давайте представим $$$p$$$ в виде ориентированного графа, у которого $$$n$$$ вершин и $$$n$$$ рёбер $$$i \to p_i$$$. Пусть $$$C$$$ — это множество вершин, которые достижимы из $$$v$$$ в графе. Требуется прибавить число $$$x$$$ ко всем $$$a_u$$$ таким, что $$$u$$$ лежит в $$$C$$$.
- Даны индексы $$$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$$$ по $$$5$$$ это $$$a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 3 + 0 = 13$$$.
- Из вершины $$$1$$$ достижимы вершины $$$\{1, 2, 3\}$$$. Получается, что после этого запроса массив $$$a$$$ будет выглядеть так: $$$[7, 10, -4, 3, 0]$$$.
- Сумма на отрезке с $$$1$$$ по $$$5$$$ это $$$a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 3 + 0 = 16$$$.
- После запроса $$$p = [4, 3, 1, 5, 2]$$$.
Граф, получаемый из перестановки после четвёртого запроса. - Из вершины $$$2$$$ достижимы вершины $$$\{1, 2, 3, 4, 5\}$$$. Получается, что после этого запроса массив $$$a$$$ будет выглядеть так: $$$[6, 9, -5, 2, -1]$$$.
- Сумма на отрезке с $$$1$$$ по $$$5$$$ это $$$a_1 + a_2 + a_3 + a_4 + a_5 = 6 + 9 + (-5) + 2 + (-1) = 11$$$.
