Problem: NSA

Want to try solving this problem? You can submit your code online if you log in or register.

Network System Administration

Input File: standard input
Output File: standard output
Time Limit: 0.5 seconds
Memory Limit: 128 MB

You are the Network System Administrator (NSA) for a local school. Recently hired on a huge salary after a catastrophic school website defacement, you are responsible for monitoring the school network to keep the systems safe.

The school administration had agreed to give you access to a stream of student e-mail meta-data (the time, sender and recipient of every e-mail sent through the network) although this decision has recently come under fire from the student body over privacy concerns.

In order to prove to the school administration that your complete access to the email meta-data is justified, you will write a program to show how the meta-data would be useful in the case of a trojan mule attack on the network. From your expert NSA training, you know that a trojan mule is a computer virus a lot like a trojan horse except that it does not reproduce.

In particular, a trojan mule starts on some initial computer then attaches itself to the first e-mail sent from that computer. Upon transmission to the e-mail's recipient, the virus removes itself from the sender's computer and infects the recipient, then waits for the next outgoing e-mail to attach to and so on. Thus, only one copy of the virus exists in the network at any time.

Your program must be able to answer queries of the form "if a trojan mule was initally on computer X, what computer would it be on now?". These queries may be interspersed with new e-mail meta-data.

Input

The first line of input will contain one line with two space-separated integers N and M, representing the number of computers and the number of input lines.
The following M lines of input will each take one of the two forms:
1. E x y (1 ≤ x, y ≤ N and x y), indicating a new e-mail sent from computer x to computer y; or,
2. Q x (1 ≤ x ≤ N), a query of the virus' current host given that it was initially on computer x.

Output

Your program must output one line for each query (Q x line of input), containing one integer representing the computer that the virus would be on at that point in time if it started on computer x.

Sample Input

Sample Output

4
5
2

Explanation

There are 5 computers connected through the school network.

An email is sent from 1 to 2.
An email is sent from 3 to 4.
We are asked, if the trojan mule was initially on computer 4, where is it now? As no emails have been sent from 4 yet, the trojan mule would still be on 4.
An email is sent from 2 to 3.
An email is sent from 3 to 5.
We are asked, if the trojan mule was initially on computer 1, where is it now? The trojan mule was transmitted from 1 to 2 (#1) then from 2 to 3 (#4) then from 3 to 5 (#5) so it would now be on computer 5.
An email is sent from 5 to 2.
We are asked, if the trojan mule was initially on computer 2, where is it now? The trojan mule was transmitted from 2 to 3 (#4) then from 3 to 5 (#5) then from 5 back to 2 (#7) so it would now be back on computer 2.

Subtasks & Constraints

For all subtasks, 1 ≤ N ≤ 100,000 and 1 ≤ M ≤ 100,000.

For Subtask 1 (10 points), 1 ≤ N ≤ 100 and 1 ≤ M ≤ 100.
For Subtask 2 (25 points), 1 ≤ N ≤ 100 and 1 ≤ M ≤ 50,000.
For Subtask 3 (30 points), no computer receives or sends any more e-mails after it has sent one e-mail. That is, once a computer appears as an x in an E line, it will not appear in any future E lines.
For Subtask 4 (35 points), no further constraints apply.