Mandatory Region Hamiltonian Path with Clearance Sequence

You are given a grid with n rows and m columns. The rows and columns are numbered from 1. A cell is denoted by the tuple \((x,y)\) (representing row \(x\) and column \(y\)). There is a mandatory region defined over every row as the set of cells whose column index is between \(L\) and \(R\) (inclusive). Formally, the mandatory region is defined as

\[ D = \{ (x,y) \mid 1 \le x \le n,\, L \le y \le R,\, x,y \in \mathbb{N}^+ \} \]

The kid can move one step at a time in the four cardinal directions (up, down, left, right) and is not allowed to move out of the grid. That is, if the kid is at \((x,y)\), he may move to \((x+1,y)\), \((x-1,y)\), \((x,y+1)\) or \((x,y-1)\).

Initially, the kid starts at \((S_x,S_y)\) (with the guarantee that \(S_y = L\)). The kid must visit every cell in the mandatory region \(D\) exactly once (i.e. no cell is visited more than once).

In addition, the kid carries a clearance sequence p to record his progress. The rules for recording are as follows: When the kid first enters the mandatory region of a row, he immediately appends that row number into the sequence, and immediately traverses all mandatory cells in that row (without leaving the continuous segment of mandatory cells). In order to pass the level, the clearance sequence p must contain a given target subsequence q (of length \(L_q\)) as a subsequence. More formally, p is valid if and only if there exists an increasing sequence of indices \(c_1, c_2, \ldots, c_{L_q}\) such that \(p_{c_i} = q_i\) for every \(i=1,2,\ldots,L_q\).

Finally, to ease the operation for lindongli2004, the kid should take as few steps as possible.

Given the values of \(n, m, L, R, S_x, S_y\) and the sequence \(q\), plan a route for the kid that meets the above restrictions or output that no such route exists.

Note: In this problem, you are allowed to choose any valid route. For the purpose of this problem, you may assume a simple case: if and only if \(S_x = 1\) and \(q\) is a subsequence of \([1,2,\ldots,n]\) (which is naturally strictly increasing), you should produce the unique "snake" path that covers each row’s mandatory region in order. Otherwise, output -1 (indicating no valid route exists).

Hint on the Snake Path: When \(S_x = 1\), a valid minimal route is to cover the mandatory region of each row in order from row 1 to row \(n\) in a snake-like manner. For row 1, traverse the cells from column \(L\) to \(R\). For row 2, traverse the cells from column \(R\) to \(L\), and so on. Since adjacent rows share a common cell at the connecting column, the path will be continuous and each mandatory cell is visited exactly once. The clearance sequence in this case becomes \([1, 2, \ldots, n]\), which is valid if \(q\) is a subsequence of it.

inputFormat

The first line contains 7 integers: \(n\), \(m\), \(L\), \(R\), \(S_x\), \(S_y\) and \(L_q\) (the length of sequence \(q\)). It is guaranteed that \(S_y = L\).

The second line contains \(L_q\) integers representing the sequence \(q\).

\(1 \le n, m \le 10^5\); \(1 \le L \le R \le m\); \(1 \le S_x \le n\); and all elements of \(q\) are positive integers.

outputFormat

If a valid route exists, output the number of cells \(k\) in the path on the first line, followed by \(k\) lines each containing two integers \(x\) and \(y\) representing the coordinates of the visited cell in order.

If no valid route exists, output -1.

sample

3 5 2 4 1 2 2
1 3

9
1 2
1 3
1 4
2 4
2 3
2 2
3 2
3 3
3 4

</p>