У AquaMoon есть три массива \(a\), \(b\), \(c\) длины \(n\), состоящие из целых чисел. Выполнено, что \(1 \leq a_i, b_i, c_i \leq n\) для всех \(i\).
Чтобы ускорить выращивание картофеля, она организует свою ферму, основываясь на этих трех массивах. Сейчас она хочет выполнить \(m\) операций, чтобы посчитать сколько картофелин она получит. Каждая операция будет иметь один из двух типов:
- AquaMoon реорганизует ферму и делает \(k\)-й элемент массива \(a\) равным \(x\). Другими словами, она выполняет присваивание \(a_k := x\).
- Дано положительное целое число \(r\). AquaMoon получает картофелину за каждую тройку \((i,j,k)\), такую что \(1\le i<j<k\le r\) и \(b_{a_i}=a_j=c_{a_k}\). Посчитайте количество таких троек.
Поскольку AquaMoon очень занята поиском библиотеки, помогите ей выполнить все операции.
Выходные данные
Для каждой операции второго типа выведите ответ.
Примечание
Для первой операции все подходящие тройки:
- \(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\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|