Description

Little Q's factory recently purchased $n$ pieces of new equipment, labeled by $1,2,\dots,n$.

There are $n$ workers in the factory, labeled by $1,2,\dots,n$. Each worker can be assigned to no more than one piece of equipment, and no piece of equipment can be assigned to multiple workers. If Little Q assigns the $i$-th worker to the $j$-th piece of equipment, they will bring $a_i+b_j$ profits. However, these workers are not so experienced, there are $m$ extra constraints. In each constraint, you will be given two integers $u_i$ and $v_i$, denoting the $u_i$-th worker can't be assigned to the $v_i$-th piece of equipment.

Now please for every $k$ ($1\leq k\leq n$) find $k$ pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total profits for these $k$ pairs are maximized, or determine it is impossible.

Format

Input

The first line contains a single integer $T$ ($1 \leq T \leq 200$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 4\,000$, $1\leq m\leq 10\,000$), denoting the number of workers/pieces of new equipment and the number of constraints.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1\leq a_i\leq 10^9$).

The third line contains $n$ integers $b_1,b_2,\dots,b_n$ ($1\leq b_i\leq 10^9$).

Each of the following $m$ lines contains two integers $u_i$ and $v_i$ ($1\leq u_i,v_i\leq n$), denoting the $u_i$-th worker can't be assigned to the $v_i$-th piece of equipment. Each pair of $u_i$ and $v_i$ will be described at most once.

It is guaranteed that there will be at most $10$ test cases such that $n>100$.

Output

For each test case, output $n$ lines, the $k$-th ($1\leq k\leq n$) of which containing an integer, denoting the maximum possible total profits for $k$ pairs of workers and pieces of equipment. Note that if it is impossible to find such $k$ pairs, print ''$\texttt{-1}$'' at this line.

Samples

2
4 4
10 20 30 40
5 10 7 8
4 2
3 2
1 4
1 2
2 2
1 1
1 1
1 1
1 2

48
85
115
130
2
-1