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

Обмеження: 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