Tesla

Allen은 언젠가 미래의 자동차인 전기 자동차로 이루어진 거대한 차량을 소유하기를 꿈꾼다! 그는 이것이 자신의 지위를 크게 높여 줄 것임을 알고 있다. As Allen 자신이 소유할 서로 다른 모든 종류의 자동차와 그 배치 방법을 계획하던 중, 자신에게 문제가 있음을 깨닫는다.

Allen의 미래 주차장은 직사각형 칸이 n (n ≤ 50)개씩 있는 4개의 행으로 이루어진 직사각형으로 나타낼 수 있으며, 각 칸에는 어느 때든 자동차를 최대 한 대만 둘 수 있다. 그는 격자에 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인 어떤 순서든 허용된다.

두 번째 예제 테스트 케이스에는 열이 하나뿐이고 자동차들이 잘못된 순서로 있으므로, 어떤 자동차도 움직일 수 없으며 과제를 수행하는 것은 불가능하다.