Шкільні переписки

Лосяш вирішив зробити навчання більш доступним для Смішариків і відкрив школу. Як і в будь-якій школі, тут є вчителі (наприклад, Пін і Совунья) та учні (наприклад, Крош і Їжачок). І, звісно, Лосяш - директор. Загалом у школі n Смішариків (включаючи викладачів та учнів). Для зручності, пронумеруємо їх натуральними числами від 1 до n.

Для спілкування між учнями та вчителями був створений месенджер, який дозволяє надсилати повідомлення будь-якому іншому користувачу, але з певними правилами:

• Якщо учень пише вчителю, копія цього повідомлення відправляється всьому викладацькому складу, тобто директору і всім вчителям. Іншими словами, директор і кожен вчитель отримають це повідомлення.

• Якщо вчитель пише учню, повідомлення отримують цей учень і директор.

• Коли користувач отримує повідомлення, воно потрапляє в непрочитані.

• Коли вчитель читає непрочитане повідомлення, надіслане учнем, воно зникає з непрочитаних у всіх вчителів, але не у директора.

• В усіх інших випадках, коли користувач читає отримане непрочитане повідомлення, воно видаляється з непрочитаних лише у нього.

Зверніть увагу, що коли директор читає непрочитане повідомлення, надіслане учнем, воно видаляється з непрочитаних лише у нього (але не у вчителів).

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

Вам надано послідовність з q подій у тому порядку, в якому вони відбувалися. Для кожної події, що відповідає питанню Лосяша, виведіть відповідь.

Вхідні дані

У першому рядку дано два цілих числа n і q (1 ≤ n, q ≤ 2 * 10^5) - кількість Смішариків у школі і кількість подій, відповідно.

У другому рядку дано n цілих чисел t[i] (t[i] ∈ 0, 1, 2) - ролі Смішариків. Якщо t[i] = 0, то i-й Смішарик - це директор Лосяш. Якщо t[i] = 1 - це вчитель. Інакше - учень. Гарантується, що рівно одне число серед t[i] дорівнює 0.

У наступних q (1 ≤ i ≤ q) рядках дано опис подій. Подія номер i може мати один з трьох типів:

• "1 a[i] b[i]" - користувач a[i] надіслав повідомлення користувачу b[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i]).

• "2 a[i] x[i]" - користувач a[i] прочитав повідомлення, надіслане під час події номер x[i] (1 ≤ a[i] ≤ n, 1 ≤ x[i] < i).

• "3 a[i]" - потрібно вивести кількість непрочитаних повідомлень у користувача a[i] (1 ≤ a[i] ≤ n).

Для всіх подій другого типу гарантується, що під час події номер x[i] було надіслано повідомлення, яке потрапило в непрочитані до користувача номер a[i]. А також, що це повідомлення ще знаходиться у нього в непрочитаних.

Вихідні дані

Для кожної події третього типу виведіть на новому рядку кількість непрочитаних повідомлень у користувача a[i].

Приклади