Cover

Problem Description

You have an $n*n$ matrix.Every grid has a color.Now there are two types of operating: L x y: for(int i=1;i<=n;i++)color[i][x]=y; H x y:for(int i=1;i<=n;i++)color[x][i]=y; Now give you the initial matrix and the goal matrix.There are $m$ operatings.Put in order to arrange operatings,so that the initial matrix will be the goal matrix after doing these operatings It's guaranteed that there exists solution.

Input

There are multiple test cases,first line has an integer $T$ For each case: First line has two integer $n$,$m$ Then $n$ lines,every line has $n$ integers,describe the initial matrix Then $n$ lines,every line has $n$ integers,describe the goal matrix Then $m$ lines,every line describe an operating $1\leq color[i][j] \leq n$ $T=5$ $1\leq n \leq 100$ $1\leq m \leq 500$

Output

For each case,print a line include $m$ integers.The i-th integer x show that the rank of x-th operating is $i$

Sample Input

1
3 5
2 2 1
2 3 3
2 1 3
3 3 3
3 3 3
3 3 3
H 2 3
L 2 2
H 3 3
H 1 3
L 2 3

Sample Output

5 2 4 3 1

Author

SXYZ

Source

2015 Multi-University Training Contest 8