안무

한국 아이돌 그룹은 칼군무라고 불리는 역동적이고 정교한 군무로 세계적으로 유명하다. 그룹에는 $m$명의 멤버가 있다. 어느 날 멤버들이 무대에서 안무를 연습한다. 무대는 직선으로 단순화되며, 길이가 같은 닫힌 구간 $n$개가 놓여 있다. 안무 중 모든 순간에 다음 규칙을 지켜야 한다.

• R1) 각 멤버는 구간 중 하나 위에 서 있어야 한다.
• R2) 두 명 이상의 멤버가 같은 구간 위에 설 수 없다.
• R3) 임의의 두 멤버가 서 있는 두 구간은 서로 교차할 수 없다.

$a \le c$인 두 닫힌 구간 $[a, b]$와 $[c, d]$는 $c \le b$이면 교차한다.

안무는 다음 규칙에 따라 여러 단계로 이루어진다.

• R4) 한 단계에서는 한 명의 멤버만 현재 구간에서 다른 구간으로 옮길 수 있다. 두 명 이상이 동시에 움직일 수 없다.
• R5) 멤버가 서 있는 구간을 바꿀 때는 현재 구간과 교차하는 구간 중 하나로 들어가야 한다. 구간 $I$가 다른 멤버가 서 있는 구간과 교차하면, R3에 따라 $I$로 들어갈 수 없다.
• R6) 안무 시작 시 멤버들이 서 있는 구간의 집합은 $S$이다.
• R7) 안무 종료 시 멤버들이 서 있는 구간의 집합은 $E$이다.

$S$와 $E$는 입력으로 주어진다. 두 집합의 크기는 모두 $m$이며, 각 집합 안의 구간은 서로 교차하지 않는다. 각 멤버는 안무 과정에서 $S$의 구간 $s$에서 출발해 $E$의 구간 $e$로 이동한다. R1부터 R7까지를 모두 만족하면서 $S$에서 $E$로 가는 최소 단계 수를 구하고, 그 모든 단계를 출력하라.

첫 번째 그림에서 여섯 개의 구간에 1부터 6까지 번호가 붙어 있다. 파란색 구간 1과 4는 시작 집합 $S$이고, 빨간색 구간 3과 6은 종료 집합 $E$이다.

그림 E.1 시작 배치 $S$.

그림 E.2 안무의 네 단계. 구간 4에 있던 멤버가 한 단계에 구간 6으로 옮기면, 전체 안무는 세 단계로 끝난다.

첫 줄에 두 정수 $m$과 $n$이 주어진다 ($1 \le m \le n \le 5{,}000$). 구간은 1부터 $n$까지 번호가 매겨지며, 구간 $i$의 왼쪽 끝점은 구간 $i+1$의 왼쪽 끝점보다 작다. 둘째 줄에는 구간의 길이 $r$ ($1 \le r \le 10{,}000$)이 주어진다. 셋째 줄에는 $i$번째 값이 구간 $i$의 왼쪽 끝점인 $n$개의 정수가 오름차순으로 주어진다. 각 값은 0 이상 $10^9$ 이하이다. 다음 줄에는 $S$에 속한 구간 번호 $m$개가 오름차순으로 주어지고, 마지막 줄에는 $E$에 속한 구간 번호 $m$개가 오름차순으로 주어진다.

첫 줄에 최소 단계 수 $MIN$을 출력한다. 이어지는 $MIN$개의 줄에서 $i$번째 줄에는 $i$단계에 멤버가 구간 $a$에서 구간 $b$로 이동함을 뜻하는 두 정수 $a$와 $b$를 출력한다. 해가 여러 개이면 그중 아무거나 출력해도 된다. 해가 없으면 $-1$을 출력한다.