좌표 평면 위에 $N$개의 점을 선택하고, 이들을 잇는 $M$개의 직선 선분을 그려 정확히 $K$개의 유한한 면(face)이 생기도록 해야 합니다. 여기서 면이란 선분들에 의해 평면이 나누어지는 영역을 의미합니다. 무한한 영역 하나는 제외하며 고려하지 않습니다.

더 형식적으로, 구성은 다음 조건을 만족해야 합니다.

• 각 점의 $x$ 좌표와 $y$ 좌표는 $1$부터 $79$ 사이의 정수여야 합니다.
• 모든 점의 위치는 서로 달라야 합니다.
• 두 점을 잇는 선분은 중복될 수 없습니다.
• 두 개의 서로 다른 선분은 끝점을 제외하고는 교차할 수 없습니다.
• 선분의 끝점이 아닌 점은 선분 위에 존재할 수 없습니다.

아래 그림에서 (a)는 3개의 점과 3개의 선분으로 1개의 면이 만들어진 경우입니다. (b)는 4개의 점과 6개의 선분으로 3개의 면이 만들어진 경우입니다. (c)는 곡선이 포함되어 있어 잘못된 출력이며, (d)는 선분들이 교차하고 있어 잘못된 출력입니다.

입력

첫 번째 줄에 점의 개수 $N$, 선분의 개수 $M$, 만들어야 할 면의 개수 $K$를 나타내는 세 개의 양의 정수가 주어집니다 ($3 \le N \le 3000, 0 \le M, 0 \le K$).

주어진 $N, M, K$에 대해 항상 해가 존재함이 보장됩니다.

출력

첫 $N$개의 줄에 선택한 점들의 좌표를 출력합니다. $i$번째 줄에는 $i$번째 점의 좌표인 두 정수 $x_i$와 $y_i$ ($1 \le x_i, y_i \le 79$)를 출력해야 합니다.

그다음 $M$개의 줄에 선분을 설명하는 정보를 출력합니다. 각 줄에는 선분으로 연결된 두 점의 인덱스를 나타내는 $1$과 $N$ 사이의 정수 두 개가 포함되어야 합니다.

가능한 해가 여러 개라면, 그중 아무거나 출력해도 됩니다.

예제

예제 1

4 6 3

1 1
3 1
2 2
2 3
1 2
1 3
1 4
2 3
2 4
3 4

예제 2

6 5 1

1 1
1 2
2 1
3 1
3 2
4 1
1 2
1 3
2 3
4 5
5 6

참고

왼쪽 그림은 4개의 점과 6개의 선분으로 3개의 면이 만들어진 경우를 보여줍니다. 오른쪽 그림은 6개의 점과 5개의 선분으로 1개의 면이 만들어진 경우를 보여줍니다.