31096번 - 오직 5%의 사람들만이 이 문제를 풀 수 있습니다 인터랙티브

문제

이 문제는 인터랙티브 문제입니다.

이따금, 광고에서는 도발적인 내용과 제목을 넣어 사람들이 게임을 하도록 유도하는 경우가 있다. 코코아는 이런 도발에 매우 취약해서, 이런 광고가 나오면 반드시 해당 게임을 완벽히 정복해야 직성이 풀린다. 오늘도 어김없이 코코아는 ‘오직 5%의 사람들만이 이 문제를 풀 수 있습니다’라는 제목의 광고를 보았고, 이제 코코아는 이 게임을 완벽히 정복해야만 한다! 코코아가 하려는 게임은 다음과 같다.

게임은 직사각형 양면 격자판에서 진행된다. 격자판은 앞면과 뒷면에 상하좌우 중 한 방향을 가리키는 화살표가 그려져 있는 일반 칸과 양면 모두 아무것도 그려져 있지 않은 목표 칸으로 구성되어 있다. 처음에 모든 칸은 앞면으로 되어 있다.

플레이어는 정해진 시작 칸에 공을 놓고 게임을 시작한다. 격자판에 있는 버튼을 누르면 공은 자신이 있는 칸에 있는 화살표가 가리키는 방향으로 굴러간다. 공이 어떤 칸 위에 있었다가 떠나면 그 칸은 위아래가 뒤집혀 앞면과 뒷면이 바뀐다.

만약 공이 굴러가던 방향과 다른 방향의 화살표가 있는 칸에 올라가거나 목표 칸에 올라가면 공은 그 칸에서 멈춘다.

게임의 목적은 버튼을 눌러서 공을 목표 칸에 위치시키는 것이다. 공이 격자판 밖으로 떨어지면 게임은 실패이다.

위는 3행 1열에 공을 놓고 버튼을 4번 누르는 상황이다. 처음에 버튼을 누르면, 공이 3행 3열까지 이동하면서 3행 1열과 3행 2열에 있는 칸이 뒤집힌다. 그다음에 버튼을 한 번 더 누르면, 공이 한 칸 아래로 내려가면서 3행 3열에 있는 칸이 뒤집힌다. 그 후, 위 그림처럼 버튼을 두 번 더 누르면 공은 4행 4열에 있는 목표 칸에 도달한다.

코코아는 친구 치노의 깜짝 새해 선물로 $N\times M$ 크기 게임판을 만들어 주려고 한다. 하지만 코코아가 만들어 주려는 게임판은 조금 특별한 게임판이다. 바로 정확히 $k$번 버튼을 누른 후에 게임에서 이기는 게임판이다. 그런데 사소한 문제가 생겼다. $k$를 치노가 좋아하는 수로 정하고 싶은데 깜빡하고 $k$를 물어보지 않은 것이었다. 지금 와서 $k$를 물어보고 새로 게임판을 만든다면 깜짝 선물이 아니다!

그래서 코코아는 치노가 어떤 $k$를 좋아하더라도 대처할 수 있도록 게임판을 만들기로 했다. 코코아는 선물을 주기 직전에 치노에게 $k$를 물어본 후, 딱 20ドル$개 이하의 일반 칸에 그려진 화살표 방향을 순식간에 바꿔서 게임판을 만들려고 한다. 어떤 칸을 바꾸기로 했다면, 윗면과 아랫면에 그려진 화살표를 모두 바꿀 수 있다.

그러나 이런 게임판을 만드는 것은 화살표의 방향을 순식간에 수정하는 것보다 어려운 문제이다. 코코아는 고민을 해보았지만 마땅한 방안을 찾지 못하였다. 여러분이 코코아를 위해 초기 게임판을 만들고, $k$가 입력되었을 때 게임판을 수정하는 프로그램을 작성하자.

인터랙션

당신의 프로그램은 아래의 과정을 통해 표준입력(stdin)과 표준출력(stdout)으로 채점기와 상호작용해야 한다.

우선, 당신의 프로그램은 두 개의 정수 $N,ドル $M$을 공백으로 구분하여 한 줄에 출력해야 한다. 이는 각각 격자판의 세로 길이와 가로 길이다.

이후, $N$개의 줄에 걸쳐 $M$개의 숫자를 공백 없이 출력한다. 각 숫자는 앞면의 상태를 나타낸다. 숫자가 0ドル$이면 해당 칸은 목표 칸이다. 그렇지 않으면 해당 칸은 일반 칸이고, 1ドル$이면 아래쪽, 2ドル$면 왼쪽, 3ドル$이면 위쪽, 4ドル$면 오른쪽 방향의 화살표가 그려져 있다. 이후, $N$개의 줄에 걸쳐 $M$개의 숫자를 공백없이 출력한다. 각 숫자는 뒷면의 상태를 나타내며, 앞면과 동일한 방식으로 표시한다.

앞면과 뒷면의 목표 칸의 위치는 동일해야 한다. 또한, 한 면 전체에서 목표 칸의 개수는 정확히 하나여야 한다.

이후, 시작 칸의 위치를 나타내는 정수 $r,ドル $c$를 공백으로 구분하여 한 줄에 출력해야 한다. 시작 칸은 $r$행 $c$열에 위치하게 된다. 맨 위쪽 행이 1ドル$행, 맨 왼쪽 열이 1ドル$열이다.

위의 사항들이 전부 출력되었다면 채점기는 양의 정수 $k$를 입력으로 준다. 당신의 프로그램은 프로그램은 $k$를 입력받고, 새로 바꾼 격자판을 출력해야 한다. 새로 바꾼 격자판은 앞면과 뒷면을 위와 동일한 방식으로 출력한다. 이때, 앞면과 뒷면 중 어느 하나라도 다른 칸의 개수는 20ドル$개를 넘을 수 없으며, 0ドル$의 위치는 기존의 출력과 동일해야 한다.

마지막으로 출력한 격자판에서 실제로 $r$행 $c$열부터 공을 굴리기 시작했을 때, 정확히 $k$번만에 공이 목표 칸에 도달해야 한다.

프로그램은 매 출력마다 표준 출력 버퍼를 비워야 한다. 출력 버퍼를 비우지 않을 시 예상치 못한 결과를 받을 수 있다. 언어별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()

입력

출력

제한

• 1ドル\leq N\leq 100$
• 1ドル\leq M\leq 100$
• 1ドル\leq r\leq N$
• 1ドル\leq c\leq M$
• 1ドル\leq k\leq 10^6$

노트