이 문제는 두 번 실행되는 문제이다. 각 테스트에서 제출한 프로그램은 두 번 실행된다.

정보 수업에서 Алеся와 Борис는 암호학을 배우고 있다. 두 사람은 자신들만의 메시지 암호화 방법을 만들기로 했다.

Алеся는 $1$부터 $n$까지의 서로 다른 정수 $k$개를 선택하고, 그 집합을 $T$라고 한다. Алеся는 집합 $T$를 암호화한 메시지로 Борис에게 보내고 싶다. 이를 위해 집합 $T$로부터 또 다른 집합 $R$을 만들어 Борис에게 보낸다. $R$ 역시 $1$부터 $n$까지의 정수로 이루어진다.

두 사람은 암호화 후 메시지의 크기가 달라지는 것을 원하지 않으므로, $R$에도 정확히 $k$개의 수가 있어야 한다. 또한 $T$와 $R$에 공통 원소가 하나라도 있으면 암호화가 충분히 안전하지 않다고 생각한다. 따라서 $T$와 $R$에 동시에 속하는 수가 없어야 한다. 즉, 두 집합은 서로소여야 한다. $k\le n/2$가 보장되므로, 집합 $T$에 대해 적어도 하나의 집합 $R$을 항상 만들 수 있다.

Борис는 암호화된 메시지 $R$을 받으면 이를 복호화하여 원래 메시지 $T$를 얻어야 한다.

Алеся와 Борис가 암호화 및 복호화 알고리즘을 만들고 구현하도록 도와주자. 첫 번째 실행에서 프로그램은 Алеся의 역할을 하고, 두 번째 실행에서는 Борис의 역할을 한다.

입력

첫 번째 줄에는 프로그램의 실행 번호를 나타내는 수 $a$가 주어진다. 이 수는 $1$ 또는 $2$이다.

두 번째 줄에는 프로그램이 암호화하거나(첫 번째 실행) 복호화해야 하는(두 번째 실행) 메시지의 개수 $m$이 주어진다($1\le m\le300\,000$).

다음 $2m$개의 줄에는 $m$개의 메시지가 주어지며, 각 메시지는 두 줄로 이루어진다.

각 메시지의 첫 번째 줄에는 두 정수 $n_i$와 $k_i$가 주어진다($2\le n_i\le10^9$, $1\le k_i\le300\,000$, $k_i\le\frac{n_i}{2}$). 두 번째 줄에는 $1$부터 $n_i$까지의 서로 다른 정수 $k_i$개가 오름차순으로 주어진다.

한 테스트에서 모든 $k_i$의 합은 $300\,000$을 넘지 않음이 보장된다.

$a=1$이면 주어진 수들은 원래 메시지이다. $a=2$이면 주어진 수들은 첫 번째 실행에서 프로그램이 어떤 메시지를 암호화한 결과이다.

출력

프로그램은 $m$개의 줄을 출력해야 한다. $i$번째 줄에는 $1$부터 $n_i$까지의 서로 다른 정수 $k_i$개를 오름차순으로 출력해야 한다.

첫 번째 실행에서는 각 원래 메시지 $T_i$에 대해 $T_i$와 서로소인 집합 $R_i$를 출력해야 한다.

두 번째 실행에서는 각 암호화된 메시지 $R_i$에 대해 원래 메시지 $T_i$를 복원해야 한다.

예제

첫 번째 실행

입력 1

1
2
2 1
1
5 2
1 4

출력 1

2
2 3

두 번째 실행

입력 2

2
2
5 2
2 3
2 1
2

출력 2

1 4
1

참고

예제에는 첫 번째 실행의 출력과 두 번째 실행의 입력으로 가능한 특정 경우가 제시되어 있음에 유의하자. 프로그램이 다른 집합 $R$을 출력하면 두 번째 실행의 입력도 달라진다.

또한 두 번째 실행에서 암호화된 메시지들이 프로그램에 주어지는 순서는 첫 번째 실행에서의 순서와 반드시 같지는 않다.

서브태스크

입력에 대한 추가 제한을 나타내기 위해, 집합 $T_i$를 이루는 수열을 $t_1,t_2,\ldots,t_{k_i}$라고 하자. 이 수들은 오름차순으로 정렬되어 있다.

한 테스트에서 $n_i$의 합을 $N$이라고 하자.

한 테스트에서 $k_i$의 합을 $K$라고 하자.