Problem Description

The Qixi Festival is known for the legend of the Cowherd and the Weaver Girl, so it has been labeled as “Valentine’s Day”.

So this year, TYVJ held an offline Qixi Festival event.

This year, student Vani successfully invited student cl to spend Qixi together, so they decided to go to the TYVJ Qixi Festival.

The TYVJ Qixi Festival is very similar to the summer festivals in District 11.

The rectangular festival venue consists of $N$ rows and $M$ columns, with a total of $N \times M$ booths.

Although there are many types of booths, cl is only interested in some of them, such as takoyaki, candy apples, cotton candy, shooting games, and so on.

Vani contacted the person in charge of the Qixi Festival, zhq, in advance, hoping to arrange the venue properly so that, in every row, the number of booths cl is interested in is the same, and, in every column, the number of booths cl is interested in is also the same.

However, zhq told Vani that the booths had already been arranged randomly. If they want to meet cl’s requirements, the only way to adjust is to swap two adjacent booths.

Two booths are adjacent if and only if they are in the same row or the same column and are in neighboring positions.

Because the TYVJ development team led by zhq successfully warped space, in each row or each column, the first position and the last position are also considered adjacent.

Now Vani wants to know how many of his two requirements can be satisfied at most.

Under this condition, what is the minimum number of swaps needed.

Input Format

The first line contains three integers $N$, $M$, and $T$, where $T$ indicates how many booths cl is interested in.

The next $T$ lines each contain two integers $x, y$, indicating that cl is interested in the booth at row $x$ and column $y$.

Output Format

First output a string.

If both of Vani’s requirements can be satisfied, output both;

If after adjustment it is only possible to make the number of booths cl is interested in the same in every row, output row;

If it is only possible to make the number of booths cl is interested in the same in every column, output column;

If neither can be satisfied, output impossible.

If the output string is not impossible, then output the minimum number of swaps, separated from the string by a space.

2 3 4
1 3
2 1
2 2
2 3

row 1

3 3 3
1 3
2 2
2 3

both 2

Hint

For $30\%$ of the data, $N, M \le 100$.

For $70\%$ of the data, $N, M \le 1000$.

For $100\%$ of the data, $1 \le N, M \le 100000$, $0 \le T \le \min(N\times M,100000)$, $1 \le x \le N$, $1 \le y \le M$.

Translated by ChatGPT 5