Given a graph $G=(V,E)$ with n vertices and m edges, and two matrices A[n][n] and B[n][n]. You need to find a permutation p of $0\dots n-1$, and to minimize $(\sum_{e\in E}a[p[e.u]][p[e.v]])\cdot(\sum_{e\in E}b[p[e.u]][p[e.v]])$ ($e.u$ and $e.v$ are the two vertices of edge $e$).

Input

First line contains two integers, n and m.

The next n lines, each line contains n integers, the $j_{th}$ integer in the $i_{th}$ line is A[i-1][j-1].

The next n lines, each line contains n integers, the $j_{th}$ integer in the $i_{th}$ line is B[i-1][j-1].

The next m lines, each line contains two integers u and v, represent an edge in the graph.

Output

The permutation p.

Scoring

Let $Ans=(\sum_{e\in E}a[p[e.u]][p[e.v]])\cdot(\sum_{e\in E}b[p[e.u]][p[e.v]])$. Then your score is $\frac{Ans\cdot n^4}{m^2\cdot 10^{12}}$.

Data generation

There are 3 types of data.

1. $n=256$, $a[i][j]$ and $b[i][j]$ are randomly selected in $[0,2^{14}]$, and the given graph is a tree. The tree is generated by randomly choosing a father between [0,i-1] for all vertices i between 1 and n-1, and then shuffle the vertices. There are 25 cases of this type.

2. $n=64$, $a[i][j]$ and $b[i][j]$ are randomly selected in $[0,2^{18}]$. There are 25 cases of this type.

3. $n=256$, $a[i][j]$ and $b[i][j]$ are randomly selected in $[0,2^{14}]$. There are 50 cases of this type.

The graph for type 2 and 3 is generated in this way:

First, for each test file, range $[min_d,max_d]$ is manually assigned. A sequence $d_0,d_1,\dots,d_{n-1}$ will be drawn randomly independently from the uniform integer distribution over the range [$min_d,max_d$]. Then the graph is generated using the expected_degree_graph function.

After the contest, data will be generated again with different seeds.

Constraints

$m\le n^2$