회전 사각형 타일

4×4 격자판에 1부터 16까지의 정수가 적힌 타일 16개가 한 번씩 놓여 있다. 목표는 아래와 같은 정렬 상태를 만드는 것이다.

그림 1

한 번의 움직임은 다음 중 하나이다.

• 한 행을 오른쪽으로 1칸, 2칸, 또는 3칸 순환 이동한다.
• 한 열을 아래쪽으로 1칸, 2칸, 또는 3칸 순환 이동한다.

그림 2는 그림 1의 2번째 행을 오른쪽으로 2칸 움직인 상태이다. 2번째 행의 오른쪽 끝에 있던 7번 타일과 8번 타일은 오른쪽 경계를 넘어 왼쪽 끝으로 돌아온다.

그림 2

그림 3은 그림 2의 3번째 열을 아래쪽으로 1칸 움직인 상태이다. 3번째 열의 맨 아래에 있던 15번 타일은 맨 위로 돌아온다.

그림 3

그림 3의 상태에서는 3번째 열을 아래쪽으로 3칸 움직인 뒤, 2번째 행을 오른쪽으로 2칸 움직이면 그림 1의 상태가 된다. 따라서 필요한 움직임은 2번이다.

타일의 초기 배치가 주어졌을 때, 그림 1의 상태가 되도록 하는 움직임의 순서를 출력하라. 움직임의 횟수는 최소여야 한다.

4×4 격자판에 놓인 타일 번호가 4개의 줄에 걸쳐 주어진다. 각 타일 번호는 1 이상 16 이하의 정수이며, 모든 번호가 정확히 한 번씩 등장한다.

각 줄에는 해당 행의 타일 4개가 왼쪽부터 오른쪽 순서로, 공백으로 구분되어 주어진다.

첫 번째 줄에 최소 움직임 횟수를 출력한다. 이어지는 줄에는 움직임을 수행하는 순서대로 한 줄에 하나씩 출력한다.

격자판의 i번째 행을 오른쪽으로 k칸 움직인다면 1 i k를 출력한다. 격자판의 i번째 열을 아래쪽으로 k칸 움직인다면 2 i k를 출력한다. 여기서 i는 1 이상 4 이하이고, k는 1 이상 3 이하이다.

행 하나 또는 열 하나를 순환 이동하는 작업은 이동한 칸 수와 관계없이 한 번의 움직임으로 센다.

주어지는 모든 입력은 최소 1번, 최대 7번의 움직임으로 그림 1의 상태로 만들 수 있다.