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 * 105) - the number of Smeshariks at school and the number of events, respectively.

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

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

• "1 ai bi" - user ai sent a message to user bi (1 ≤ ai, bi ≤ n, ai ≠ bi).
• "2 ai xi" - user ai read the message sent during event number xi (1 ≤ ai ≤ * n, *1 ≤ xi < i).
• "3 ai" - print the number of unread messages for the user ai (1 ≤ ai ≤ n).

For all events of the second type, it is guaranteed that during event number xi a message was sent that ended up in the user number ai. 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 ai.