Raon works as a software developer in one of the largest company in her city. Due to some circumtances, her company decides to choose a new CEO among the existing N shareholders; each shareholder is indexed from 1 to N. Interestingly, they opt to use voting mechanism to do this, and each shareholder has 1 vote. At the time when this plan was announced, each shareholder is in the leader of their own group and plans to vote for themselves. However, collaborations and confrontations may occur during the campaign season.
There is still one week before the voting take place, and Raon is wondering how the voting result will be. Raon wants you, her intern, to help her build a system to simulate the collaboration among the shareholders. The system should be able to do these 3 type of operations:
This is an easy task for Raon, but she's quite busy at the moment. Write the program and impress her!
Input begins with two integers: N Q (1 ≤ N, Q ≤ 100,000) denoting the number of shareholders and the number operations to be performed respectively. The next Q lines, each contains an operation to be performed. There are 3 types of operations:
For every operation of the third type (iii), output in a line the current winning leader's index and how many members does his groups has respectively, separated by a single space.
input  Example #1 
5 5 1 3 5 1 2 3 3 2 5 3  
output  
3 3 5 3  
explanation  
notation: bold/red index is the leader of the group.

input  Example #2 
9 10 1 2 9 1 1 9 3 1 3 8 1 5 7 1 4 5 1 7 8 3 2 7 3  
output  
2 3 5 5 7 5 
End of Problem