Choreography

Korean idol groups are known around the world for dynamic and elaborate group dances, called Kalgunmu. A group has $m$ members. One day the members practice their choreography on a stage. The stage is simplified as a line, and $n$ closed intervals of identical length are placed on it. During the choreography, the following rules must hold at every moment.

• R1) Each member stands on one of the intervals.
• R2) No two or more members can stand on the same interval.
• R3) Two intervals on which any two members stand cannot intersect.

Two closed intervals $[a, b]$ and $[c, d]$ with $a \le c$ intersect if $c \le b$.

The choreography consists of several steps with the following rules.

• R4) At any step, only one member can move from her or his current interval to another interval. Two or more members cannot move at the same time.
• R5) When a member changes the interval she or he stands on, the member has to move into one of the intervals that the current interval intersects. A member cannot move into an interval $I$ if $I$ intersects an interval on which another member stands, according to R3.
• R6) The set of intervals on which the members stand at the start is $S$.
• R7) The set of intervals on which the members stand at the end is $E$.

The sets $S$ and $E$ are given in the input. Each has size $m$, and the intervals in each set do not intersect each other. Each member moves from an interval $s$ in $S$ to an interval $e$ in $E$ during the choreography. Find a choreography from $S$ to $E$ that satisfies R1 to R7 with the minimum number of steps, and output every step.

In the first figure, six intervals are numbered 1 to 6. The blue intervals 1 and 4 are the starting set $S$, and the red intervals 3 and 6 are the ending set $E$.

Figure E.1 Initial configuration $S$.

Figure E.2 Four steps of a choreography. The member on interval 4 moves to interval 6 in one step, which allows the whole choreography to finish in three steps.

The first line contains two integers $m$ and $n$ ($1 \le m \le n \le 5{,}000$). The intervals are numbered 1 to $n$, and the left endpoint of interval $i$ is strictly less than the left endpoint of interval $i+1$. The second line contains the length $r$ of the intervals ($1 \le r \le 10{,}000$). The third line contains $n$ integers in ascending order, where the $i$-th number is the left endpoint of interval $i$. These values are between 0 and $10^9$. The next line contains the $m$ interval numbers of $S$ in ascending order. The last line contains the $m$ interval numbers of $E$ in ascending order.

On the first line, print the minimum number of steps $MIN$. On each of the following $MIN$ lines, print two integers $a$ and $b$, meaning that at step $i$ a member moves from interval $a$ to interval $b$. If several solutions exist, print any one of them. If no solution exists, print $-1$.