Нещодавно Скрудж влаштувався працювати охоронцем у банку. Робота нудна, робити нічого, тому він почав стежити за чергою. Спочатку у черзі стоїть \(n\) людей. Оскільки до цього кілька років Скрудж працював психологом, він зміг досить точно оцінити настрій кожної людини у черзі. Скрудж пронумерував людей у черзі по порядку, починаючи з нуля, таким чином вийшло, що номер людини в черзі дорівнює кількості людей, які стоять у черзі перед ним. Настрій \(i\)-ї людини він описав цілим невід'ємним числом \(a_i\). Скрудж вважає, що у людини гарний настрій, якщо воно не менше \(𝑥\) . Якщо це не так, то настрій у людини поганий.

Люди приходять у чергу, йдуть із неї. Якщо в чергу приходить нова людина, Скрудж миттєво оцінює її настрій, і з часом він не змінюється.

Тепер Скрудж вигадав собі таке заняття: у деякі моменти часу він вибирає одну людину з черги і рахує, скільки перед нею стоїть людей з гарним настроєм. Це заняття вже здалося йому цікавим, і він вирішив вигадати, як його можна автоматизувати. Так як сам Скрудж не сильний у програмуванні, допомоги у вирішенні цього завдання він попросив у вас. Допоможіть йому!

Формат вхідних даних

У першому рядку дано два числа \(𝑛,𝑥\) (\(1≤𝑛≤100000\),\(0≤𝑥≤10^9\) ) — початкова кількість людей у черзі та нижня межа гарного настрою.

У наступному рядку дано \(𝑛\) чисел \(𝑎_𝑖\) — настрої людей у черзі (\(0≤𝑎_𝑖≤10^9\) ).

У третьому рядку наведено число \(𝑚\) (\(1≤𝑚≤100000\) ) — кількість подій, що відбувалися з чергою.

У наступних \(𝑚\) рядках дано опис подій. Подія описується одним із трьох способів:

• 1 \(a\) (\(0 ≤ a ≤ 10^9\)) - в кінець черги приходить людина з настроєм, рівним \(a\).
• 2 - з черги йде людина, перед яким ніхто не стоїть (у нумерації Скруджа він має номер 0). Після цього Скрудж подумки зменшує номери людей у черзі на 1.
• 3 \(i\) — Скрудж хоче дізнатися, скільки людей з гарним настроєм стоїть перед людиною, перед якою у черзі в цей момент стоїть \(i\)-а людина.

Гарантується, що всі запити коректні: якщо в черзі нікого немає, то операція другого типу не виконується, а кількість людей у черзі завжди буде строго більшою \(i\) в запиті третього типу.

Формат вихідних даних

На кожен запит третього типу в окремому рядку виведіть одне число - кількість людей з гарним настроєм, які стоять перед людиною з цим номером.

Система оцінювання

• Перша група тестів складається з тестів, для яких виконується обмеження \(𝑛,𝑚≤1000\). Бали за цю групу нараховуються лише за проходження всіх тестів групи. Вартість групи складає 40 балів.
• Друга група тестів складається з тестів, для яких виконується обмеження \(𝑛,𝑚≤100000\). Бали за цю групу нараховуються лише за проходження всіх тестів групи. Вартість групи складає 60 балів.

Приклад вхідних даних

1 2
3
5
1 2
1 1
3 0
3 1
3 2

Приклад вихідних даних

0
1
2

Приклад вхідних даних

2 2
1 2
7
3 0
3 1
2
3 0
1 3
3 0
3 1

Приклад вихідних даних

0
0
0
0
1