Triangle City 是一个拥有 $\frac{n(n+1)}{2}$ 个交叉口的城市，这些交叉口排列成 $n$ 行 $n$ 列，其中第 $i$ 行包含 $i$ 个交叉口。

交叉口之间由双向道路连接。形式化地，如果我们用 $(i, j)$ 表示第 $i$ 行第 $j$ 列的交叉口，对于所有 $1 \le j \le i < n$，有：

• 一条长度为 $a_{i,j}$ 的道路连接交叉口 $(i, j)$ 和 $(i + 1, j)$，
• 一条长度为 $b_{i,j}$ 的道路连接交叉口 $(i, j)$ 和 $(i + 1, j + 1)$，
• 一条长度为 $c_{i,j}$ 的道路连接交叉口 $(i + 1, j)$ 和 $(i + 1, j + 1)$。

此外，对于所有 $1 \le j \le i < n$，存在一个边长分别为 $a_{i,j}$、$b_{i,j}$ 和 $c_{i,j}$ 的三角形。这就是该城市被称为“三角形城市”的原因！

我们著名的旅行者 BaoBao 刚刚抵达三角形城市，计划从交叉口 $(1, 1)$ 出发，在交叉口 $(n, n)$ 结束他的旅程。为了充分欣赏风景，BaoBao 想要找到一条从 $(1, 1)$ 到 $(n, n)$ 的最长路径，使得每条道路经过不超过一次。请帮助 BaoBao 找到这样一条路径。

回想一下，如果一个三角形的边长为 $a, b, c$，我们可以推断出 $a + b > c$，$a + c > b$ 且 $b + c > a$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($2 \le n \le 300$)，表示城市的大小。

接下来的 $(n - 1)$ 行中，第 $i$ 行包含 $i$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,i}$ ($1 \le a_{i,j} \le 10^9$)，其中 $a_{i,j}$ 表示连接交叉口 $(i, j)$ 和 $(i + 1, j)$ 的道路长度。

接下来的 $(n - 1)$ 行中，第 $i$ 行包含 $i$ 个整数 $b_{i,1}, b_{i,2}, \dots, b_{i,i}$ ($1 \le b_{i,j} \le 10^9$)，其中 $b_{i,j}$ 表示连接交叉口 $(i, j)$ 和 $(i + 1, j + 1)$ 的道路长度。

接下来的 $(n - 1)$ 行中，第 $i$ 行包含 $i$ 个整数 $c_{i,1}, c_{i,2}, \dots, c_{i,i}$ ($1 \le c_{i,j} \le 10^9$)，其中 $c_{i,j}$ 表示连接交叉口 $(i + 1, j)$ 和 $(i + 1, j + 1)$ 的道路长度。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^3$。

输出格式

对于每组测试数据，输出三行。

第一行包含一个整数 $l$，表示从 $(1, 1)$ 到 $(n, n)$ 且每条道路经过不超过一次的最长路径长度。

第二行包含一个整数 $m$，表示最长路径上的交叉口数量。

第三行包含 $2m$ 个整数 $i_1, j_1, i_2, j_2, \dots, i_m, j_m$，以空格分隔，其中 $(i_k, j_k)$ 表示最长路径上的第 $k$ 个交叉口。注意，根据描述，必须满足 $(i_1, j_1) = (1, 1)$ 且 $(i_m, j_m) = (n, n)$。

如果存在多个有效答案，你可以输出其中任意一个。

请不要在每行末尾输出多余的空格，否则你的解法可能会被判定为错误！

样例

样例输入 1

3
2
3
2
4
2
1
1
1
3
100
100 100
1
100 1
100
100 100

样例输出 1

7
3
1 1 2 1 2 2
2
3
1 1 2 1 2 2
700
8
1 1 2 1 3 2 2 2 2 1 3 1 3 2 3 3

说明

样例测试数据如下图所示：