F. AquaMoon и картофель
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У AquaMoon есть три массива $$$a$$$, $$$b$$$, $$$c$$$ длины $$$n$$$, состоящие из целых чисел. Выполнено, что $$$1 \leq a_i, b_i, c_i \leq n$$$ для всех $$$i$$$.

Чтобы ускорить выращивание картофеля, она организует свою ферму, основываясь на этих трех массивах. Сейчас она хочет выполнить $$$m$$$ операций, чтобы посчитать сколько картофелин она получит. Каждая операция будет иметь один из двух типов:

  1. AquaMoon реорганизует ферму и делает $$$k$$$-й элемент массива $$$a$$$ равным $$$x$$$. Другими словами, она выполняет присваивание $$$a_k := x$$$.
  2. Дано положительное целое число $$$r$$$. AquaMoon получает картофелину за каждую тройку $$$(i,j,k)$$$, такую что $$$1\le i<j<k\le r$$$ и $$$b_{a_i}=a_j=c_{a_k}$$$. Посчитайте количество таких троек.

Поскольку AquaMoon очень занята поиском библиотеки, помогите ей выполнить все операции.

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

В первой строке находится два целых числа $$$n$$$, $$$m$$$ ($$$1\le n\le 2\cdot10^5$$$, $$$1\le m\le 5\cdot10^4$$$).

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

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

В четвертой строке находится $$$n$$$ целых чисел $$$c_1, c_2, \dots,c_n$$$ ($$$1\le c_i\le n$$$).

Следующие $$$m$$$ строк описывают операции, $$$i$$$-я строка описывает $$$i$$$-ю операцию в одном из двух форматов:

  • "$$$1\ k\ x$$$" ($$$1\le k,x\le n$$$) для операции первого типа.
  • "$$$2\ r$$$" ($$$1\le r\le n$$$) для операции второго типа.

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

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

Для каждой операции второго типа выведите ответ.

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

Для первой операции все подходящие тройки:

  • $$$i=1$$$, $$$j=2$$$, $$$k=3$$$
  • $$$i=2$$$, $$$j=3$$$, $$$k=4$$$
  • $$$i=3$$$, $$$j=4$$$, $$$k=5$$$

Не существует подходящих троек для третьей операции.

Для четвертой операции все подходящие тройки:

  • $$$i=2$$$, $$$j=4$$$, $$$k=5$$$
  • $$$i=3$$$, $$$j=4$$$, $$$k=5$$$