Crab vừa rộng mô hình dịch vụ sang chuyển phát hàng hóa khi xe đang rảnh. Có \(n\) gói hàng, gói thứ \(i\) muốn chuyển từ vị trí \(i\) đến vị trí \(i + n\). Cần lập lịch cho xe xuất phát từ vị trí \(0\), chuyển hết các gói hàng và quay lại vị trí xuất phát. Sức chứa của xe là đủ lớn, do đó gói hàng thứ \(i\) sẽ được chuyển nếu ít nhất một lần, lộ trình của xe có đi qua \(i\) trước khi đi qua \(i+n\). Ví dụ với \(n = 3\), lộ trình sau là thỏa mãn: \(0-1-2-1-5-3-6-4-0\)

Cho biết độ dài tuyến đường đi lại giữa mọi cặp vị trí, hãy tìm lộ trình của taxi có tổng độ dài các tuyến đường đi qua là nhỏ nhất. Lưu ý, các tuyến đường trong thành phố là đường một chiều nên khoảng cách từ \(x\) đến \(y\) có thể khác với khoảng cách từ \(y\) đến \(x\), và có thể đường đi ngắn nhất \(x\) và \(y\) không phải là đường đi trực tiếp giữa chúng. Nếu có nhiều lộ trình thỏa mãn có cùng độ dài nhỏ nhất, in ra một lộ trình bất kỳ

Input

• Dòng 1: \(n\)
• Tiếp theo là \(2n+1\) dòng, số thứ \(j\) trên dòng \(i\) là \(c_{i,j}\): độ dài tuyến đường nối \(i\) với \(j\)

Output

• Dòng đầu tiên chứa tổng độ dài của lộ trình tìm được
• Dòng tiếp theo chứa số vị trí sẽ đi qua
• Dòng tiếp theo ghi danh sách các vị trí sẽ đi qua theo thứ tự trong lộ trình

Scoring

• \(1 \leq n \leq 10\). \(1 \leq c_{i,j} \leq 1000\)
• Subtask 1: \(n \leq 5\)
• Subtask 2: \(c_{i,j} + c_{j,k} \geq c_{i,k}\), \(\forall\) \(0 \leq i, j, k \leq 2n\)
• Subtask 3: Ràng buộc gốc

Example

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

12
9
0 2 5 2 3 1 4 6 0