Школьные переписки

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

Примеры