Жили и Джили любят прыгать по последовательности. Они движутся по определенному правилу и на протяжении всего процесса черпают энергию из интервала, соответствующего их текущему положению. Эту энергию они используют для восстановления логической стабильности.
Даны две перестановки$$$^{\text{∗}}$$$ $$$a$$$ и $$$b$$$ длины $$$n$$$.
Для любого открытого интервала $$$I = (l, r)$$$, где $$$0 \le l \lt r \le n+1$$$ и $$$l + 1 \lt r$$$, мы определяем $$$\operatorname{next}(I) = (\min(i, j), \max(i,j))$$$, где
Также задана последовательность $$$p$$$ неотрицательных чисел длиной $$$n$$$ в $$$0$$$-индексации. Последовательность $$$g(I)$$$ определяется как $$$g(I) = \begin{cases} [0] & (p_l = 0) \\ [1]^{p_l} & (p_l \gt 0) \end{cases}$$$$$$^{\text{‡}}$$$.
Последовательность $$$f(I, k)$$$ определяется как $$$f(I, k) = \begin{cases} [~] & \text{если } k=0 \text{ или } l+1\ge r \\ g(I) + f(\operatorname{next}(I), k-1) & \text{в противном случае} \end{cases}$$$$$$^{\text{§}}$$$.
Вам необходимо выполнить $$$m$$$ операций:
$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
$$$^{\text{†}}$$$$$$\operatorname*{argmax}\limits_{k \in (l, r)}$$$ $$$a_k$$$ обозначает единственный индекс $$$k$$$ ($$$l \lt k \lt r$$$), такой что $$$a_k = \max\limits_{x \in (l, r)} a_x$$$.
$$$^{\text{‡}}$$$Здесь $$$[1]^m$$$ представляет собой последовательность длины $$$m$$$, состоящую из одних единиц.
$$$^{\text{§}}$$$Здесь $$$[~]$$$ обозначает пустую последовательность, а оператор $$$+$$$ между двумя последовательностями означает их конкатенацию.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — длина перестановки и количество операций.
Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — перестановку $$$a$$$.
Третья строка содержит $$$n$$$ различных целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — перестановку $$$b$$$.
Четвертая строка содержит $$$n$$$ целых чисел $$$p_0, p_1, \ldots, p_{n - 1}$$$ ($$$0 \le p_i \le 10^9$$$) — последовательность $$$q$$$.
Каждая из следующих $$$m$$$ строк содержит операцию в одном из следующих форматов:
Гарантируется, что суммы $$$n$$$ и $$$m$$$ по всем наборам входных данных не превосходят $$$4 \cdot 10^5$$$ соответственно.
Для каждой операции типа $$$1$$$ выведите ответ на отдельной строке.
35 43 4 1 5 22 3 5 1 42 3 2 5 31 0 4 11 1 4 21 3 6 11 0 6 25 43 5 1 2 41 4 3 2 50 2 0 3 01 2 5 11 4 6 21 0 5 11 3 5 210 3010 1 7 3 2 8 4 9 6 51 7 3 2 8 9 5 4 10 64 0 6 3 0 2 1 5 2 41 10 11 101 10 11 31 4 11 101 10 11 91 1 4 102 4 51 0 7 41 9 10 42 6 31 5 7 61 6 7 91 2 7 41 4 7 21 1 2 11 5 7 82 0 31 2 7 51 7 10 61 6 8 71 3 4 31 8 9 92 4 51 1 4 41 0 9 42 1 21 6 11 101 5 9 101 2 4 71 1 11 11 2 11 3
235200030000040206502653000335626
В первом наборе входных данных:
Во втором наборе входных данных:
