School correspondence

Losyash decided to make education more accessible to Smeshariki and opened a school. Of course, as in any other school, this school has teachers (for example, Pin and Sovunya) and students (for example, Krosh and Hedgehog). And, of course, Losyash is the director. In total at school there are n Smeshariki (teaching staff and students). For convenience, we enumerate them with positive integers from 1 to n.

For communication between students and teachers, a messenger was created that allows to write a message to any other user, but with some additional rules:

• If the student writes to the teacher, then a copy of this message is sent to the entire teaching staff. That is, the director and all teachers. In other words, the director and each teacher will receive this message.

• If a teacher writes a message to a student, the message will be received by that student and the director.

• When a user receives a message, it goes to unread folder.

• When a teacher reads an unread message sent by a student, that message disappears from unread messages for all teachers, but not for the director.

• In all other cases, when the user reads the received unread message, it is removed from the unread only for him.

Please note that when the Director reads an unread message sent by a student, it is removed from the unread only for him (and not for teachers).

Losyash wants to optimize the learning process, so at some points in time he is interested in how many unread messages a particular user has.

You are given a sequence of q events in the order in which they happened. For each event corresponding to Losyash's question, print the answer.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2 * 10^5) - the number of Smeshariks at school and the number of events, respectively.

The second line contains n integers t[i] (t[i] ∈ 0, 1, 2) - the roles of Smeshariki. If t[i] = 0, then i-th Smesharik is a director Losyash. If t[i] = 1 is a teacher. Otherwise, it is a student. It is guaranteed that exactly one number among t[i] equals 0.

The following q (1 ≤ i ≤ q) lines describe the events. Event number i can be one of three types:

• "1 a[i] b[i]" - user a[i] sent a message to user b[i] (1 ≤ a[i], b[i] ≤ n, a[i] ≠ b[i]).

• "2 a[i] x[i]" - user a[i] read the message sent during event number x[i] (1 ≤ a[i] ≤ * n*, 1 ≤ x[i] < i).

• "3 a[i]" - print the number of unread messages for the user a[i] (1 ≤ a[i] ≤ n).

For all events of the second type, it is guaranteed that during event number x[i] a message was sent that ended up in the user number a[i]. And also that this message is still unread.

Output

For each event of the third type, print on a new line the number of unread messages for user a[i].

Examples