시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB60302454.545%

문제

$N \times M$크기의 격자가 있다. 이 격자의 $i$행 $j$열에는 사탕 $a_{ij}$개가 있다. 이루매는 이 격자의 $1$행 $1$열에서 출발해 오른쪽 또는 아래쪽으로만 한 칸씩 이동하며 지나가는 길의 사탕을 모두 먹는 방식으로 $N$행 $M$열에 도착했다.

이루매는 격자의 크기와 각 칸에 있던 사탕의 개수는 기억하지 못한다. 하지만 $1\leq N,M \leq 200$; $0\leq a_{ij} \leq 1000$이었으며 먹을 수 있는 총 사탕의 합이 최대가 되는 경로가 정확히 $x$개 였다는 사실을 기억하고 있다. 이 조건을 만족하는 격자를 하나 찾아보자. 그런 격자가 적어도 하나 있음을 보일 수 있다.

입력

첫째 줄에 정수 $x$가 주어진다. $(1 \leq x \leq 10^{18})$

출력

첫째 줄에 격자의 행 수와 열 수를 나타내는 두 정수 $N, M$을 공백으로 구분해 출력한다. $(1\leq N,M \leq 200)$

다음 $N$줄에 걸쳐 $i+1$번째 줄에 사탕의 개수를 나타내는 $M$개의 정수 $a_{i1}, a_{i2}, \cdots, a_{iM}$을 공백으로 구분해 출력한다. $(0\leq a_{ij} \leq 1000)$

답이 여러 개 있다면 그중 아무거나 출력한다.

예제 입력 1

3

예제 출력 1

3 3
0 1 3
2 2 1
3 0 1

예제의 격자에서 먹을 수 있는 사탕의 최대 개수는 6개이며 사탕을 6개 먹을 수 있는 경로는 총 3개이다.

예제 입력 2

1

예제 출력 2

1 1
500