이 문제는 출력 전용(output-only) 문제입니다. 텍스트 파일이 아닌 출력을 생성하는 코드를 제출해야 함에 유의하십시오.

그래프의 유효한 3-채색(3-coloring)이란 그래프의 각 정점에 $\{1, 2, 3\}$ 집합의 색(숫자)을 할당하여, 그래프의 모든 간선 $(u, v)$에 대해 정점 $u$와 $v$가 서로 다른 색을 갖도록 하는 것을 의미합니다. $n$개의 정점을 가진 그래프에 대해 이러한 채색은 최대 $3^n$개 존재합니다.

당신은 주어진 개수의 3-채색을 가진 그래프를 생성하는 전문가가 되려는 목표를 가진 회사에서 일하고 있습니다. 어느 날, 당신은 저녁에 정확히 $6k$개의 3-채색을 가진 그래프를 생성하라는 주문을 받게 될 것임을 알게 됩니다. 당신은 $k$의 정확한 값을 모르며, 단지 $1 \le k \le 500$이라는 것만 알고 있습니다.

당신은 $k$의 특정 값을 기다리지 않고 그래프 생성을 시작하고 싶습니다. 따라서, 미리 최대 19개의 정점을 가진 그래프를 구축합니다. 그 후, 특정 $k$를 알게 되면, 그래프에 최대 17개의 간선을 추가하여 정확히 $6k$개의 3-채색을 가진 요구된 그래프를 얻을 수 있습니다.

이 작업을 수행할 수 있습니까?

입력

이 문제에 대한 입력은 없습니다.

출력

먼저, 초기 그래프(미리 구축한 그래프)의 정점 개수 $n$과 간선 개수 $m$($1 \le n \le 19$, $1 \le m \le \frac{n(n-1)}{2}$)을 출력하십시오. 그 다음, 그래프의 간선인 $(u, v)$ 형태의 줄을 $m$개 출력하십시오.

그 다음, $1$부터 $500$까지의 모든 $k$에 대해 다음을 수행하십시오: 해당 $k$에 대해 추가할 간선의 개수 $e$($1 \le e \le 17$)를 출력하십시오. 그 다음, 그래프에 추가할 간선인 $(u, v)$ 형태의 줄을 $e$개 출력하십시오.

자기 루프(self-loop)는 없어야 하며, 모든 $k$에 대해 사용하는 $m+e$개의 간선은 모두 서로 달라야 합니다. 특정 $k$에 대한 그래프의 3-채색 개수는 정확히 $6k$여야 합니다.

예제

입력 1

-

출력 1

3 2
1 2
2 3
1
1 3
0

참고

예제 출력은 예시로 제공되었습니다. 여기에는 $k=1, 2$에 대한 출력이 포함되어 있습니다.