Турнірна таблиця обласної олімпіади

Обмеження: 2 сек., 256 МіБ

Олімпіада в самому розпалі — фаворит змагання Зеник встиг розв’язати кілька задач, але запекла боротьба тільки попереду.

Учасники олімпіади на Алготестері бачать тільки свій результат, але не знають, скільки балів набрали інші. А от організатори можуть спостерігати повну картину — їм видно турнірну таблицю.

В олімпіаді беруть участь $n$ людей, пронумерованих від 1 до $n$. Зеник виступає під номером 1.

Порядок учасників у турнірній таблиці заданий перестановкою $p$ чисел від 1 до $n$. На першому місці в таблиці розташований учасник номер $p_1$, на другому місці — учасник $p_2$ і т. д.

Під час олімпіади відбулося $q$ подій. Події бувають трьох типів:

• Задано $t_i$ = 1, $k_i$. Зеник розв’язує задачу й обганяє $k_i$ учасників над ним в турнірній таблиці.

• Задано $t_i$ = 2, $x_i$. Учасник з номером $x_i$ обганяє одного учасника над собою.

• Задано $t_i$ = 3, $x_i$ та $k_i$. Організаторів олімпіади, які прикували погляди до таблиці, цікавить сума номерів $k_i$ учасників, що розташовані безпосередньо над учасником з номером $x_i$.

Організатори п’ють чай і не хочуть нічого рахувати самостійно. Допоможіть їм відповісти на їхні запитання.

Вхідні дані

У першому рядку задано одне ціле число $n$ — кількість учасників.

У наступному рядку задано $n$ цілих чисел $p_i$, що задають початковий порядок учасників у турнірній таблиці.

У наступному рядку задано одне ціле число $q$ — кількість подій під час олімпіади.

У наступних $q$ рядках задано події.

Якщо подія першого типу, то задано два цілі числа $t_i = 1$ та $k_i$ — тип події та кількість учасників, яких пережене Зеник. Перед Зеником є хоча б $k_i$ учасників.

Якщо подія другого типу, то задано два цілі числа $t_i = 2$ та $x_i$ — тип події та номер учасника, який пережене учасника над ним. Учасник $x_i$ не є першим.

Якщо подія третього типу, то задано три цілі числа $t_i = 3$, $x_i$ та $k_i$ — тип події, номер учасника та кількість над ним, яка цікавить організаторів олімпіади. Перед учасником з номером $x_i$ є хоча б $k_i$ учасників.

Вихідні дані

На кожен запит третього типу — виведіть суму номерів $k_i$ учасників над учасником з номером $x_i$.

Обмеження

$2 \le n, q \le 10^6$,

$1 \le p_i \le n$, усі $p_i$ різні,

$1 \le k_i \le n - 1$, $1 \le x_i \le n$,

серед подій є хоча б одна подія третього типу.

Оцінювання задачі складається із наступних блоків:

1 бал — приклад з умови,

4 бали — є запити тільки третього типу,

10 балів — є запити тільки другого та третього типів,

10 балів — без додаткових обмежень.

Бали за блок ви отримаєте лише якщо дасте правильну відповідь на всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 2 3 1 10 3 3 1 2 3 3 2 1 3 1 2 1 2 3 2 2 2 3 2 2 3 1 1 3 2 1	2 3 5 4 2 3