题目描述

优秀素质和双涡轮是两位来自特雷森学院的赛马娘，她们正在上数据结构课！

在数据结构课中，她们学习了带边权的树以及树上两点之间的距离。

在课堂上，优秀素质得到了两棵结构一样的树，但是不同之处在于两棵树中间一条边的边权可能不同。具体地，每一条边可以用四元组 $(u,v,w1,w2)$ 来表示，其中 $u$ 和 $v$ 表示这条边连接的两个节点，$w1$ 和 $w2$ 分别表示第一棵树和第二棵树上该边的边权。

为了更方便地表示整棵树的信息，她计算出了每对节点之间的"距离"。具体地说，对于每一对节点 $i,j$，她记录了 $\text{dis1}_{i,j}$ 和 $\text{dis2}_{i,j}$，分别表示第一棵树和第二棵树上 $i$ 到 $j$ 的路径上的边的边权和。

然而，淘气的双涡轮为了捣乱，偷偷地做了一点手脚。她趁优秀素质不注意的时候，随意地交换了若干对 $(\text{dis1}_{i,j},\text{dis2}_{i,j})$ 中的两个距离。也就是说，你现在拿到的"距离矩阵"中，某些 $(i,j)$ 的 $(\text{dis1}_{i,j},\text{dis2}_{i,j})$ 的值可能被交换了。例如，原本真实的 $\text{dis1}_{i,j} = 1$ 而 $\text{dis2}_{i,j} = 2$，然而双涡轮捣乱后的"距离矩阵"里的 $\text{dis1}_{i,j} = 2$ 而 $\text{dis2}_{i,j} = 1$。

现在，你拿到了被双涡轮捣乱之后的"距离矩阵"，你可以帮助她复原出原来的树的结构和每条边在两棵树上的边权吗？

输入格式

第一行一个正整数 $T (1 \leq T \leq 10000)$ 表示数据组数。对于每组数据，

• 第一行一个整数 $n (1 \leq n \leq 1000)$ 。
• 接下来 $n$ 行，第 $i$ 行包含 $n$ 个整数 $\text{dis1}_{i,1}, \ldots ,\text{dis1}_{i,n} (0 \leq \text{dis1}_{i,j} \leq 10^9)$ 。
• 接下来 $n$ 行，第 $i$ 行包含 $n$ 个整数 $\text{dis2}_{i,1}, \ldots ,\text{dis2}_{i,n} (0 \leq \text{dis2}_{i,j} \leq 10^9)$ 。

对于 $T$ 组数据，保证 $n^2$ 之和不超过 $10^6$。

输出格式

对于每组数据，输出 $n - 1$ 行，第 $i$ 行输出 $u_i, v_i, w1_i, w2_i (1 \leq u_i, v_i \leq n, 0 \leq w1_i, w2_i \leq 10^9)$，表示原树的第 $i$ 条边。若有多种可能的方案，输出任意一种即可。保证输入一定有解。

3
3
0 2 3
1 0 4
2 4 0
0 1 2
2 0 4
3 4 0
3
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
5
0 1 2 4 5
2 0 4 2 2
2 4 0 6 6
4 3 6 0 4
5 2 7 7 0
0 2 2 4 4
1 0 3 3 4
2 3 0 6 7
4 2 6 0 7
4 4 6 4 0

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