Melon 是一只住在月球上的兔子，每年中秋节负责运送月饼。除了地球外，许多其他星球也有月饼需求。因此，Melon 在运送月饼时需要消耗她的仙力在不同星球间穿梭。

共有 $n$ 个星球，编号为 $1$ 到 $n$，以及 $m$ 条隧道。每条隧道无向连接两个星球。每个星球 $i$ 都有一个颜色 $c_i$ 和一个消耗值 $w_i$，表示 Melon 降落到该星球时需要消耗的仙力。

为了节省星际旅行的仙力，Melon 会使用一种特殊技能：种植桂花树。最初，没有任何星球上种有桂花树。当 Melon 降落到一个没有桂花树的星球时，她会立即在那里种下一棵桂花树，但她不会在同一个星球上种植超过一棵桂花树。如果一个星球已经种有桂花树，Melon 再次降落到该星球时将不会消耗任何仙力。此外，当她位于星球 $i$ 时，她可以选择一个种有桂花树且颜色不是 $c_i$ 的星球 $j$，然后远程砍掉星球 $j$ 上的桂花树并恢复 $w_j$ 的仙力。

形式化地，Melon 在星球 $u$ 时，随时可以执行以下任一操作：

• 通过隧道移动到相邻且未种植桂花树的星球 $v$，消耗 $w_v$ 仙力，并在星球 $v$ 上种下一棵桂花树。
• 通过隧道移动到相邻且已种植桂花树的星球，不消耗仙力，也不种植额外的树。
• 选择一个种有桂花树且颜色不是 $c_u$ 的星球 $v$，远程砍掉星球 $v$ 上的桂花树（即此后星球 $v$ 上不再有桂花树），并恢复 $w_v$ 仙力。请注意，此操作可以在同一个星球上多次执行。

Melon 的仙力不能低于 $0$，因此她必须在出发前准备足够的仙力。Melon 想知道从起始星球 $s$ 到目标星球 $t$ 旅行所需准备的最小仙力。特别地，Melon 在起始星球 $s$ 需要消耗 $w_s$ 仙力并种下一棵桂花树。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 300, 1 \le m \le \frac{n(n - 1)}{2}$)，表示星球和隧道的数量。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$)，表示每个星球的颜色。

第三行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^9$)，表示在每个星球上需要消耗的仙力。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示星球 $u$ 和 $v$ 之间的一条无向隧道。保证任意两个不同星球之间最多只有一条隧道，且任意两个星球之间都存在路径。

保证所有测试用例的 $n$ 之和不超过 $300$。

输出格式

输出 $n$ 行，每行包含 $n$ 个由空格分隔的整数。第 $i$ 行第 $j$ 列的整数表示从起始星球 $i$ 到目标星球 $j$ 旅行所需准备的最小仙力。特别地，当 $i = j$ 时输出 $0$。

样例

输入 1

1
4 4
1 1 2 3
1 2 4 5
1 2
2 3
3 4
1 4

输出 1

0 3 7 6
3 0 6 8
6 6 0 8
6 6 7 0

说明

对于样例，从星球 $3$ 到星球 $1$ 的一种初始仙力为 $6$ 的旅行方式如下：

1. 消耗 $4$ 点仙力并在星球 $3$ 上种下一棵桂花树。（剩余仙力：$2$）
2. 移动到星球 $2$，消耗 $2$ 点仙力并在其上种下一棵桂花树。（剩余仙力：$0$）
3. 砍掉星球 $3$ 上的桂花树并恢复 $4$ 点仙力。（剩余仙力：$4$）
4. 移动到星球 $1$，消耗 $1$ 点仙力并在其上种下一棵桂花树。（剩余仙力：$3$）