Raon and Voting

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:

  1. Two groups of shareholder meet and decide to form an alliance. The leader of the two groups with the most members is the new alliance leader. If both groups have the same number of members, then the leader whose index is smaller is the new alliance leader.
  2. A member of a group of shareholder is promoted to be the new leader of that group.
  3. Output the current winning leader's index and how many members does his group has. The winning leader is the leader with the most members on his group. If there are more than one such leader, then output the winning leader with the smallest index.

This is an easy task for Raon, but she's quite busy at the moment. Write the program and impress her!

Input

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:

Output

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.

Examples

inputExample #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.
  • At the beginning, there are 5 groups of shareholder: (1), (2), (3), (4), (5).
  • After the first operation: (1), (2), (3, 5), (4).
  • After the second operation: (1), (2, 3, 5), (4)
  • At the third operation, the winning leader's index is 3, with 3 members in his group.
  • After the fourth operation: (1), (2, 3, 5), (4)
  • At the fifth operation, the winning leader's index is 5, with 3 members in his group.

inputExample #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