Школьные переписки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лосяш решил сделать обучение более доступным для Смешариков и открыл школу. Разумеется, как и в любой другой школе, в этой школе есть учителя (например, Пин и Совунья) и есть ученики (например, Крош и Ёжик). Ну и, конечно же, Лосяш — директор. Всего суммарно в школе $$$n$$$ Смешариков (преподавательского состава и учеников). Для удобства, пронумеруем их натуральными числами от $$$1$$$ до $$$n$$$.

Для общения между учениками и учителями был создан мессенджер, который позволяет написать сообщение любому другому пользователю, но с некоторыми дополнительными правилами:

  1. Если ученик пишет учителю, то копия этого сообщения отправляется всему преподавательскому составу. То есть, директору и всем учителям. Иными словами, директор и каждый учитель получат это сообщение.
  2. Если учитель пишет сообщение ученику, то сообщение получат этот ученик и директор.
  3. Когда пользователю приходит сообщение, оно попадает в непрочитанные.
  4. Когда учитель читает непрочитанное сообщение, отправленное учеником, это сообщение исчезает из непрочитанных у всех учителей, но не у директора.
  5. Во всех остальных случаях, когда пользователь читает полученное непрочитанное сообщение, оно удаляется из непрочитанных только у него.

Обратите внимание, что когда директор читает непрочитанное сообщение, отправленное учеником, оно удаляется из непрочитанных только у него (но не у учителей).

Лосяш хочет оптимизировать учебный процесс, поэтому в некоторые моменты времени ему интересно, сколько непрочитанных сообщений есть у какого-то конкретного пользователя.

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

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$q$$$ — количество Смешариков в школе и количество событий, соответственно ($$$1 \le n, q \le 2 \cdot 10^5$$$).

Во второй строке даны $$$n$$$ целых чисел $$$t_i$$$ — роли Смешариков ($$$t_i \in \{0, 1, 2\}$$$). Если $$$t_i = 0$$$, то $$$i$$$-й Смешарик — это директор Лосяш. Если $$$t_i = 1$$$ — это учитель. Иначе — ученик. Гарантируется, что ровно одно число среди $$$t_i$$$ равно $$$0$$$.

В следующих $$$q$$$ строках дано описание событий. Событие номер $$$i$$$ может иметь один из трех типов ($$$1 \le i \le q$$$):

  1. «$$$1~a_i~b_i$$$» — пользователь $$$a_i$$$ отправил сообщение пользователю $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$; $$$a_i \neq b_i$$$).
  2. «$$$2~a_i~x_i$$$» — пользователь $$$a_i$$$ прочитал сообщение, отправленное во время события номер $$$x_i$$$ ($$$1 \le a_i \le n$$$, $$$1 \le x_i < i$$$).
  3. «$$$3~a_i$$$» — требуется вывести количество непрочитанных сообщений у пользователя $$$a_i$$$ ($$$1 \le a_i \le n$$$).
Для всех событий второго типа гарантируется, что во время события номер $$$x_i$$$ было отправлено сообщение, попавшее в непрочитанные к пользователю номер $$$a_i$$$. А также, что это сообщение еще находится у него в непрочитанных.

Выходные данные

Для каждого события третьего типа выведите на новой строке количество непрочитанных сообщений у пользователя $$$a_i$$$.

Пример

Входные данные
4 5
0 1 1 2
1 2 4
1 4 2
2 3 2
3 1
3 2
Выходные данные
2
0