Background

People who believe in miracles are greater than miracles themselves.

Suddenly, the save point dropped into a huge grid. Only after walking through all required areas will the next save point appear...

Problem Description

You are given a grid with $n$ rows and $m$ columns. Rows and columns are numbered starting from $1$. Define an ordered pair $(x,y)$ to represent the cell at row $x$, column $y$. In each row, the cells from column $L$ to column $R$ are required areas. Formally, let $D$ be the set of required areas, then $D=\{(x,y)|1\leq x\leq n,L\leq y\leq R,x,y\in N_+\}$.

Each time, kid can move one step in one of the four directions: up, down, left, or right, and cannot go out of bounds. Formally, if kid is currently at $(x,y)$, then kid can move to $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$.

Initially, kid is at $(S_x,S_y)$ (it is guaranteed that $S_y=L$). He needs to walk through all required areas, and any cell can be visited at most once. Formally, kid’s path is a sequence of ordered pairs $P=(x_1,y_1),(x_2,y_2)...(x_k,y_k)$, which must satisfy: for all $(x_0,y_0)\in D$, there exists $i\in[1,k]$ such that $(x_0,y_0)=(x_i,y_i)$, and for all $i\not= j$, $(x_i,y_i)\not= (x_j,y_j)$.

Meanwhile, kid must record a clearing sequence $p$. After kid enters the required area of a certain row for the first time, he must append that row number to the end of the current sequence, and immediately traverse all required areas of that row. Also, $p$ must contain a subsequence $q$ of length $L_q$ to be a valid clearing sequence and truly clear the level. Formally, $p$ is valid if and only if there exists a sequence $c$ of length $L_q$ such that $p_{c_i}=q_i$, and $c$ is strictly increasing.

Also, to reduce the operation difficulty for lindongli2004, lindongli2004 hopes that kid uses as few steps as possible.

Given $n,m,L,R,S_x,S_y,q$, please plan a clearing route for kid, or tell him that no such route exists. The remaining operations will be left to lindongli2004!

Input Format

The first line contains $8$ positive integers $n,m,L,R,S_x,S_y,L_q,s$, representing the number of rows and columns of the grid, the left and right boundaries of the required area, the starting $x$ and $y$ coordinates, the length of sequence $q$, and the scoring parameter.

The second line contains $L_q$ distinct positive integers, representing the sequence $q$.

Output Format

The first line outputs a string YES or NO indicating whether a path exists (without quotes).

If a path exists, the second line outputs a positive integer $cnt$ indicating the path length. Then output $cnt$ lines, each with two positive integers $x,y$ representing the coordinates on the path.

5 4 2 3 2 2 2 15
3 1

YES
15
2 2
2 3
3 3
3 2
4 2
4 3
5 3
5 2
5 1
4 1
3 1
2 1
1 1
1 2
1 3

Hint

Constraints

$1\leq L\leq R\leq m$, $1\leq S_x\leq n$, and for the rest see the provided files.

Scoring Rules

The last number in the first line of the provided files is $s$. Let your number of steps be $cnt$. Then:

• If $cnt\leq s$, you will get $10$ points.
• If $cnt> s$ and you can clear the level, you will get $9- \frac{cnt-s}{\lfloor\frac{n}{2}\rfloor}$ points.
• If you cannot clear the level, you will get $0$ points.

Checker

Self-service.

How to use: In the same directory, put the provided testdata into data.in, put your output into data.out, compile and run.

Notes:

• This checker assumes there exists a solution by default, and checks whether that solution is valid.
• The maximum capacity of solutions for this checker is $2.5 \times 10^{8}$. That is, your solution cannot contain more than $2.5 \times 10^{8}$ numbers.

Translated by ChatGPT 5