Tesla

Allen은 언젠가 미래의 자동차인 전기 자동차를 엄청나게 많이 소유하는 꿈을 꾼다! 그는 이것이 자신의 지위를 크게 높여 줄 것임을 알고 있다. As Allen은 자신이 소유할 여러 종류의 자동차와 그 배치 방법을 모두 계획하던 중, 문제가 있다는 것을 깨닫는다.

Allen의 미래 주차장은 직사각형 칸이 4개 행과 n (n ≤ 50)개 열로 배치된 직사각형으로 나타낼 수 있으며, 각 칸에는 어느 때든 자동차가 최대 한 대만 들어갈 수 있다. 그는 격자에 k (k ≤ 2n)대의 자동차가 있고, 모든 자동차가 처음에는 둘째 행과 셋째 행에 있다고 상상한다. 또한 각 자동차에는 첫째 행 또는 넷째 행에 서로 다른 지정 주차 칸이 있다. Allen은 자동차를 각각에 해당하는 주차 칸에 넣어야 한다.

첫 번째 예제의 그림.

그러나 Allen은 자신의 자동차를 다른 누구에게도 맡기지 않을 것이므로, 한 번에 자동차 한 대만 이동할 수 있다. 그는 자동차를 한 칸에서 네 기본 방향 중 어느 한 방향에 있는 인접한 빈 칸으로 운전할 수 있다. 또한 Allen은 어떤 자동차를 첫째 행이나 넷째 행의 칸으로 이동시킬 때, 그 칸이 해당 자동차의 지정 주차 칸인 경우에만 그렇게 할 수 있다.

Allen은 자신이 매우 바쁜 사람이 될 것임을 알고 있으며, 자동차를 옮기는 일이 시간을 들일 가치가 없다고 판단하기 전까지 자동차를 최대 20000번만 이동할 시간이 있다. Help Allen은 그가 직접 자동차를 주차할 가치가 있는지, 아니면 자신보다 덜 중요한 사람에게 맡겨야 하는지 판단한다.

입력의 첫째 줄에는 공백으로 구분된 두 정수 n와 k (1 ≤ n ≤ 50, 1 ≤ k ≤ 2n)이 주어지며, 각각 열의 수와 자동차의 수를 나타낸다.

다음 네 줄에는 각각 0 이상 k 이하인 정수 n개가 주어지며, 주차장의 초기 상태를 나타낸다. 행에는 위에서 아래로 1부터 4까지 번호가 매겨지고, 열에는 왼쪽에서 오른쪽으로 1부터 n까지 번호가 매겨진다.

첫째 줄과 마지막 줄에서 정수 1 ≤ x ≤ k는 자동차 x에 배정된 주차 칸을 나타내며(이 자동차만 이 칸으로 이동시킬 수 있다), 정수 0은 빈 칸을 나타낸다(어떤 자동차도 이 칸으로 이동시킬 수 없다).

둘째 줄과 셋째 줄에서 정수 1 ≤ x ≤ k는 자동차 x의 초기 위치를 나타내며, 정수 0은 빈 칸을 나타낸다(어떤 자동차든 이 칸으로 이동시킬 수 있다).

1 이상 k 이하인 각 x은 둘째 줄과 셋째 줄에 정확히 한 번 나타나며, 첫째 줄과 넷째 줄에도 정확히 한 번 나타난다.

모든 자동차를 각자의 주차 칸으로 옮기는 이동 순서가 존재하고 자동차 이동 횟수가 최대 20000번이라면, 첫째 줄에 이동 횟수 m을 출력한다. 이어지는 m개의 줄에는 이동을 한 줄에 하나씩 i r c 형식으로 출력한다. 이는 Allen이 자동차 i를 행 r, 열 c에 있는 인접한 칸으로 이동시키는 것을 뜻한다.

Allen이 최대 20000번의 자동차 이동으로 모든 자동차를 올바른 칸으로 옮길 수 없다면, 정수 -1만 있는 한 줄을 출력한다.

첫 번째 예제 테스트 케이스에서는 자동차 5을 제외한 모든 자동차가 자신의 주차 칸 앞에 있으며, 이 자동차는 인접한 주차 칸 앞에 있다. 예제는 가능한 가장 짧은 이동 순서를 보여 주지만, 길이가 최대 20000인 어떤 이동 순서도 허용된다.

두 번째 예제 테스트 케이스에는 열이 하나뿐이고 자동차의 순서가 잘못되어 있으므로, 어떤 자동차도 이동할 수 없어 작업을 완료하는 것이 불가능하다.