28634번 - Школьные переписки 다국어

Лосяш решил сделать обучение более доступным для Смешариков и открыл школу. Разумеется, как и в любой другой школе, в этой школе есть учителя (например, Пин и Совунья) и есть ученики (например, Крош и Ёжик). Ну и, конечно же, Лосяш --- директор. Всего суммарно в школе $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$.