뱀과 사다리는 유명한 주사위 게임이다. 맨 처음에는 말이 보드의 바깥에 있다. 턴이 시작될 때 M면체 주사위를 굴린다. 1 이상 M 이하의 자연수가 나오고, 각 자연수가 나올 확률은 1/M이다. 나온 자연수만큼 말을 전진시키고 (보드의 바깥에 있으면 나온 자연수에 해당하는 칸으로 이동한다), 뱀이나 사다리가 있으면 그것이 가리키는 칸으로 이동한다. N번 칸에 도달하면 게임이 끝난다. 도착점이 N번을 넘어가도 도착으로 간주한다.</p>

이런 문제를 생각해볼 수 있다. "도착하기 위해 주사위를 굴려야 하는 횟수의 기댓값은 얼마일까?" 하지만 우리는 이 문제를 푸는 게 아니라, 이 문제의 테스트케이스를 만들어야 한다.

정답이 50,000,000,000,000,000,000 이상인 테스트케이스를 만들어 보자.

입력 형식

입력은 없다.

출력 형식

첫 줄에 자연수 N, M, S를 출력한다. N은 100 이하, M은 20 이하, S는 N/2 이하여야 한다.</p>

다음 S줄에는 한 줄에 하나씩 뱀이나 사다리의 시작점과 도착점을 출력한다. (도착점이 시작점보다 작으면 뱀, 크면 사다리이다.) 시작점은 1 이상 N-1 이하, 도착점은 1 이상 N 이하여야 한다. 모든 시작점과 도착점 중 중복되는 점은 없어야 한다.

말이 어느 칸에 놓여 있어도 게임을 끝낼 수 있음이 보장되어야 한다. 심지어 도달 자체가 불가능한 칸에 일부러 말을 놓거나, 뱀이나 사다리의 시작점에 말을 올려 놓고 뱀/사다리를 타지 않은 채로 시작해도 게임을 끝낼 수 있어야 한다. 전혀 이해할 수 없는 조건이지만, 구데기컵이니까 그러려니 하자.

아래 예제 출력은 형식에 맞는 출력을 보여주는 것일 뿐, 정답이 아님에 유의하라.

예제 입력

예제 출력

4 2 1
2 4