Problem Description

Given an $n \times m$ grid, the rows are numbered from $1$ to $n$, and the columns are numbered from $1$ to $m$. Except for the leftmost column $1$ and the rightmost column $m$, each column contains at most one obstacle. The leftmost column and the rightmost column are guaranteed to have no obstacles.

You start from any cell in the leftmost column (you may choose the row), and your goal is to reach any cell in the rightmost column (you may choose the row). Suppose you are currently at row $i$, column $j$. In each step, you may choose one of the following three operations:

• Move right: from $(i,j)$ to $(i,j+1)$.
• Move up: from $(i,j)$ to $(i-1,j)$.
• Move down: from $(i,j)$ to $(i+1,j)$.

Moving left is not allowed. At any time, you cannot enter an obstacle cell, and you also cannot move outside the grid.

There are $k$ obstacles (after sorting by column index in increasing order, they are numbered from $i=0$ to $k-1$). For each obstacle, you must choose either “bypass from above” or “bypass from below”.

If the $i$-th obstacle is at column $c_i$ and row $r_i$:

• If you choose “bypass from above”, then when you are in column $c_i$, your row index must always be $< r_i$.
• If you choose “bypass from below”, then when you are in column $c_i$, your row index must always be $> r_i$.

Choices for different columns are independent, so there are $2^k$ possible plans.

Your task: for each plan, compute the minimum number of steps to go from some row in the leftmost column to some row in the rightmost column while satisfying all constraints of that plan. If there is no feasible path under that plan, output $-1$.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 5000$), representing the number of test cases.

Then each test case is given as follows:

The first line contains two integers $n, m$ ($1 \leq n \leq 100, 2 \leq m \leq 100$), representing the number of rows and columns of the grid.

The second line contains an integer $k$ ($0 \leq k \leq \min(m - 2, 10)$), representing the number of obstacles.

The next $k$ lines each contain two integers $r_i, c_i$ ($1 \le r_i \le n, 1 \le c_i \le m$), meaning there is an obstacle at row $r_i$, column $c_i$. It is guaranteed that $1 < c_1 < c_2 < \ldots < c_k < m$.

For all test cases, it is guaranteed that $\sum n \cdot m \leq 5000$. Note that there is no constraint on the sum of $k$ over all test cases.

Output Format

For each test case, output one line containing $2^k$ integers, in order, representing the minimum steps for each plan with id from $0$ to $2^k-1$. Adjacent numbers should be separated by a single space. If a plan has no solution, output $-1$.

Plan id description: each plan can be seen as a binary number of length $k$. From low bit to high bit, the bits correspond to obstacles $0, 1, ..., k-1$. A bit value of $0$ means bypass that obstacle from above, and a bit value of $1$ means bypass that obstacle from below.

For example, if $k = 3$, then there are $2^3 = 8$ plans, corresponding to:

$$\begin{array}{|c|c|c|} \hline Plan\ ID & Binary\ (low\ bit \to high\ bit) & Bypass\ choice\ (obstacle\ 0,\ obstacle\ 1,\ obstacle\ 2) \\ \hline 0 & 000 & above,\ above,\ above \\ \hline 1 & 100 & below,\ above,\ above \\ \hline 2 & 010 & above,\ below,\ above \\ \hline 3 & 110 & below,\ below,\ above \\ \hline 4 & 001 & above,\ above,\ below \\ \hline 5 & 101 & below,\ above,\ below \\ \hline 6 & 011 & above,\ below,\ below \\ \hline 7 & 111 & below,\ below,\ below \\ \hline \end{array}$$

The program should output the minimum number of steps for each plan in increasing order of plan id.

3
3 6
2
3 4
2 5
3 4
1
1 2
3 6
2
3 2
1 5

5 -1 -1 -1
-1 3
-1 -1 5 -1

Hint

Translated by ChatGPT 5