408542: GYM103182 K Bathroom Tiles

Bob has one more thing to do before he is happy with his new home. He must paint his bathroom floor tiles, which can be seen as a $$$N \times M$$$ matrix, in a specific colour plan. The only issue is that Bob is simply not capable of only painting one tile. He can either paint all tiles from a column or all tiles from a row.

Each row and column can be painted with a specific colour, each of them represented through an integer $$$c$$$, where $$$1 \leq c \leq K$$$. Bob is now wondering what is the minimum number of times he will have to paint rows and columns in order to get to the desired colour scheme - or if he will be able to get to it at all.

That is to say, for each row $$$i$$$ and each column $$$j$$$ of an $$$N \times M$$$ matrix, you are given a colour that you can paint it with. Moreover, you are given a matrix $$$a$$$ of size $$$N \times M$$$, where cell $$$a_{ij}$$$ ($$$1 \leq i \leq N$$$, $$$1 \leq j \leq M$$$) represents the colour that tile should end up having.

Knowing this, let Bob know the minimum number of times he has to paint rows and columns in order to get to the desired colour scheme. Moreover, tell him how. If he cannot get to his plan, just reply with -1. He might cry about it, but it is his fault.

The first line of input contains three integers: N, M,($$$1 \leq N \times M \leq 10^5$$$), and K ($$$1 \leq K \leq N+M$$$). They represent the number of rows, the number of columns and the maximum integer representation of a colour.

The second line will contain $$$N$$$ integers $$$RC_i$$$ ($$$1 \leq RC_i \leq K$$$), where $$$RC_i$$$ represents the colour that you can paint row $$$i$$$ with.

The third line will contain $$$M$$$ integers $$$CC_j$$$ ($$$1 \leq CC_j \leq K$$$), where $$$CC_j$$$ represents the colour you can paint column $$$j$$$ with.

After will follow a $$$N \times M$$$ matrix $$$a$$$, representing the colour scheme that Bob desires. Note that for all $$$a_{ij}$$$, it holds that $$$1\leq a_{ij} \leq K$$$.

On the first line, print an integer $$$X$$$ denoting how many times Bob must paint rows or columns.

On the next $$$X$$$ lines, print an integer $$$y_i$$$. If a row is painted, $$$y_i$$$ shall be a negative integer such that ($$$-N \leq y_i \leq -1$$$). If a column is painted, it shall be a positive integer such that ($$$1 \leq y_i \leq M$$$). If there are several solutions with a minimum number of steps, any of them is considered correct.

Alternatively, print -1 in case the desired colour scheme cannot be reached.

2 2 2
1 2
1 2
1 2
2 2

3
-1
-2
2

2 2 3
1 2
1 2
1 2
2 3

-1