The task is to start from a given cell, traverse every cell of an $n$ by $m$ matrix in a loop without duplication. For example, if $n = 2$ and $m = 2$ and we start from $(1, 0)$, then we can go from $(1, 0)$, to $(1, 1)$, to $(0, 1)$, to $(1, 1)$, then back to $(1, 0)$. For simplicity we assume that $m$ is always an even number.
Subtasks
5pt. $m = 2$ and $n = 2$.
10pt. $m = 2$ and $n \geq 2$.
10pt. $m = 4$ and $n \geq 2$.
20pt. $m = 6$ and $n \geq 2$.
55pt. $m$ is no more than 500, and $2 \leq n \leq 512$.
Hints
For any matrix of even number of columns, we can start from $(0, 0)$, go up to $(0, m - 1)$, then go right to $(n - 1, m - 1)$, then do a snake-like zig-zag traversal back to $(1, 0)$, then go back to $(0, 0)$.
p10077-sample input 2
p10077 generic solution
Since we can go through all cells in a loop, then we only need to identify the given cell in this loop, then print all cells along the way in order.
Input Format
There are many cases in one input file, please read it until EOF.
There are four numbers in one case.
The first two numbers means the size of the $n$ by $m$ matrix. The first number is $n$. The second number is $m$.
The last two numbers means the cell that you start from.
Problem Description
The task is to start from a given cell, traverse every cell of an $n$ by $m$ matrix in a loop without duplication. For example, if $n = 2$ and $m = 2$ and we start from $(1, 0)$, then we can go from $(1, 0)$, to $(1, 1)$, to $(0, 1)$, to $(1, 1)$, then back to $(1, 0)$. For simplicity we assume that $m$ is always an even number.
Subtasks
Hints
Input Format
There are many cases in one input file, please read it until EOF.
There are four numbers in one case.
The first two numbers means the size of the $n$ by $m$ matrix. The first number is $n$. The second number is $m$.
The last two numbers means the cell that you start from.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2
Sample Input 3
Sample Output 3