요정들의 마법

N마리의 요정이 일렬로 서서 마법을 쓰고 있다. 어린 마법사 민형이는 텔레포트 마법을 배우려고 요정의 마법을 하나씩 기록하며 연구한다. 민형이는 맨 왼쪽 요정부터 순서대로 1번부터 N번까지 번호를 붙였다.

요정은 마법으로 자리를 바꾼다. 마법은 두 가지다.

• 두 요정이 동시에 마법을 쓰면 그 두 요정의 자리가 서로 바뀐다.
• 한 요정이 혼자 마법을 쓰면 그 요정의 왼쪽에 있던 무리와 오른쪽에 있던 무리가 통째로 자리를 바꾼다. 각 무리 안의 순서는 그대로이고, 마법을 쓴 요정은 두 무리 사이에 남는다. 마법을 쓴 요정이 맨 왼쪽이나 맨 오른쪽에 있어도 나머지 요정의 자리는 이 규칙대로 바뀐다.

예를 들어 요정 6마리가 왼쪽부터 1, 2, 3, 4, 5, 6 순으로 서 있다고 하자. 4번 요정이 혼자 마법을 쓰면 줄은 5, 6, 4, 1, 2, 3이 된다. 이어서 2번 요정과 5번 요정이 동시에 마법을 쓰면 2, 6, 4, 1, 5, 3이 되고, 그 다음에 3번 요정이 혼자 마법을 쓰면 3, 2, 6, 4, 1, 5가 된다.

요정들은 마법을 모두 M번 썼고, 민형이는 어떤 요정이 마법을 썼는지 시간 순서대로 적었다. 그런데 기록을 다시 살펴보니 마법 하나가 통째로 빠져 있었다. 민형이는 요정의 마나를 보는 마법으로 빠진 마법을 쓴 요정 중 한 마리는 알아냈지만, 그 마법이 혼자 쓴 것인지 둘이 함께 쓴 것인지, 몇 번째로 쓴 것인지는 알지 못한다. 기록에서 빠진 마법의 순서와 종류를 구하여라.

첫째 줄에 요정의 수 N과 요정이 마법을 쓴 횟수 M이 주어진다. ($2 \le N, M \le 100\,000$)

둘째 줄부터 M-1개의 줄에 민형이가 기록한 마법이 시간 순서대로 주어진다. 2 P Q는 P번 요정과 Q번 요정이 동시에 마법을 썼다는 뜻이고, 1 P는 P번 요정이 혼자 마법을 썼다는 뜻이다. 요정의 번호는 1 이상 N 이하이며, 두 요정이 함께 마법을 쓴 경우 두 번호는 서로 다르다.

그 다음 줄에는 M번의 마법을 모두 쓰고 난 뒤의 요정 번호가 왼쪽부터 순서대로 주어진다.

마지막 줄에는 기록에서 빠진 마법을 쓴 요정 한 마리의 번호가 주어진다.

답이 존재하는 입력만 주어진다.

첫째 줄에 기록에서 빠진 마법의 순서 W를 출력한다. W는 빠진 마법을 제자리에 끼워 넣었을 때 그 마법이 몇 번째로 쓰인 마법인지를 뜻하는 1 이상 M 이하의 정수다. 둘째 줄에 빠진 마법의 종류를 1 P 또는 2 P Q 형태로 출력한다. 빠진 마법은 입력의 마지막 줄에 주어진 요정이 쓴 마법이어야 한다.

기록과 맞아떨어지는 답이 여러 개면 그중 하나만 다음 기준으로 골라 출력한다. 먼저 W가 가장 작은 답을 고른다. W가 같은 답이 여럿이면 둘째 줄에 출력할 정수 나열이 사전순으로 가장 작은 답을 고른다. 2 P Q는 항상 $P < Q$가 되도록 출력한다.