Triangle City is a city with $$$\frac{n(n+1)}{2}$$$ intersections arranged into $$$n$$$ rows and $$$n$$$ columns, where the $$$i$$$-th row contains $$$i$$$ intersections.
The intersections are connected by bidirectional roads. Formally, if we denote $$$(i, j)$$$ as the intersection on the $$$i$$$-th row and the $$$j$$$-th column, for all $$$1 \le j \le i \lt n$$$,
- there is a road whose length is $$$a_{i, j}$$$ connecting intersection $$$(i, j)$$$ and $$$(i + 1, j)$$$, and
- there is a road whose length is $$$b_{i, j}$$$ connecting intersection $$$(i, j)$$$ and $$$(i + 1, j + 1)$$$, and
- there is a road whose length is $$$c_{i, j}$$$ connecting intersection $$$(i + 1, j)$$$ and $$$(i + 1, j + 1)$$$.
What's more, for all $$$1 \le j \le i \lt n$$$, there exists a triangle whose sides are of length $$$a_{i, j}$$$, $$$b_{i, j}$$$ and $$$c_{i, j}$$$. That's why the city is called the Triangle City!
Our famous traveler BaoBao has just arrived in the Triangle City, planning to start his journey from intersection $$$(1, 1)$$$ and end his trip at intersection $$$(n, n)$$$. To fully enjoy the landscape, BaoBao would like to find the longest path from $$$(1, 1)$$$ to $$$(n, n)$$$ such that each road is passed no more than once. Please help BaoBao find such a path.
Recall that if the sides of a triangle are of length $$$a$$$, $$$b$$$ and $$$c$$$, we can infer that $$$a + b \gt c$$$, $$$a + c \gt b$$$ and $$$b + c \gt a$$$.
There are multiple test cases. The first line of the input contains an integer $$$T$$$, indicating the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$2 \le n \le 300$$$), indicating the size of the city.
For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains $$$i$$$ integers $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, i}$$$ ($$$1 \le a_{i, j} \le 10^9$$$), where $$$a_{i, j}$$$ indicates the length of the road connecting intersection $$$(i, j)$$$ and $$$(i + 1, j)$$$.
For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains $$$i$$$ integers $$$b_{i, 1}, b_{i, 2}, \dots, b_{i, i}$$$ ($$$1 \le b_{i, j} \le 10^9$$$), where $$$b_{i, j}$$$ indicates the length of the road connecting intersection $$$(i, j)$$$ and $$$(i + 1, j + 1)$$$.
For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains $$$i$$$ integers $$$c_{i, 1}, c_{i, 2}, \dots, c_{i, i}$$$ ($$$1 \le c_{i, j} \le 10^9$$$), where $$$c_{i, j}$$$ indicates the length of the road connecting intersection $$$(i + 1, j)$$$ and $$$(i + 1, j + 1)$$$.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$ 5 \times 10^3$$$.
For each test case output three lines.
The first line contains one integer $$$l$$$, indicating the length of the longest path from $$$(1, 1)$$$ to $$$(n, n)$$$ such that each road is passed no more than once.
The second line contains one integer $$$m$$$, indicating the number of intersections on the longest path.
The third line contains $$$2m$$$ integers $$$i_1, j_1, i_2, j_2, \dots, i_m, j_m$$$ separated by a space, where $$$(i_k, j_k)$$$ indicates the $$$k$$$-th intersection on the longest path. Note that according to the description, there must be $$$(i_1, j_1) = (1, 1)$$$ and $$$(i_m, j_m) = (n, n)$$$.
If there are multiple valid answers, you can output any of them.
Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!
3 2 3 2 4 2 1 1 1 3 100 100 100 1 100 1 100 100 100
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
The sample test cases are shown below:
