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.
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.
5 8 E 1 2 E 3 4 Q 4 E 2 3 E 3 5 Q 1 E 5 2 Q 2
4 5 2
There are 5 computers connected through the school network.
For all subtasks, 1 ≤ N ≤ 100,000 and 1 ≤ M ≤ 100,000.