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

Заданы две перестановки $$$a$$$ и $$$b$$$, обе состоят из $$$n$$$ элементов. Перестановка из $$$n$$$ элементов — это такая последовательность целых чисел, что каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.

Запрашивается два типа запросов к ним:

  • $$$1~l_a~r_a~l_b~r_b$$$ — посчитать количество значений, которые встречаются как в отрезке $$$[l_a; r_a]$$$ позиций перестановки $$$a$$$, так и в отрезке $$$[l_b; r_b]$$$ позиций перестановки $$$b$$$;
  • $$$2~x~y$$$ — поменять местами значения на позициях $$$x$$$ и $$$y$$$ перестановки $$$b$$$.

Выведите ответы на все запросы первого типа.

Гарантируется, что во входных данных существует хотя бы один запрос первого типа.

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

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

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — перестановка $$$a$$$. Гарантируется, что каждое число от $$$1$$$ до $$$n$$$ содержится в $$$a$$$ ровно один раз.

В третьей строке записаны $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — перестановка $$$b$$$. Гарантируется, что каждое число от $$$1$$$ до $$$n$$$ содержится в $$$b$$$ ровно один раз.

Каждая из следующих $$$m$$$ строк содержит описание определенного запроса. Они бывают следующих видов:

  • $$$1~l_a~r_a~l_b~r_b$$$ ($$$1 \le l_a \le r_a \le n$$$, $$$1 \le l_b \le r_b \le n$$$);
  • $$$2~x~y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$).
Выходные данные

Выведите ответы на запросы первого типа, каждый ответ в отдельной строке — количество значений, которые встречаются и в отрезке $$$[l_a; r_a]$$$ позиций перестановки $$$a$$$, и в отрезке $$$[l_b; r_b]$$$ позиций перестановки $$$b$$$.

Пример
Входные данные
6 7
5 1 4 2 3 6
2 5 3 1 4 6
1 1 2 4 5
2 2 4
1 1 2 4 5
1 2 3 3 5
1 1 6 1 2
2 4 1
1 4 4 1 3
Выходные данные
1
1
1
2
0
Примечание

Рассмотрим первый запрос первого примера. Значения на позициях $$$[1; 2]$$$ перестановки $$$a$$$ — это $$$[5, 1]$$$, а значениях на позициях $$$[4; 5]$$$ перестановки $$$b$$$ — это $$$[1, 4]$$$. Только значение $$$1$$$ встречается в обоих отрезках.

После первой смены мест (второй запрос) перестановка $$$b$$$ становится $$$[2, 1, 3, 5, 4, 6]$$$.

После второй смены мест (шестой запрос) перестановка $$$b$$$ становится $$$[5, 1, 3, 2, 4, 6]$$$.