Một đại lý vận chuyển đảm bảo việc vận chuyển hàng hoá giữa ~N~ thành phố. Giữa một số cặp thành phố có thể có hoặc không có tuyến đường vận chuyển. Công ty phải lập kế hoạch thực hiện ~M~ vận đơn của khách hàng. Mỗi vận đơn là một yêu cầu vận chuyển một kiện hàng từ một thành phố nào đó đến một thành phố khác. Chi phí vận chuyển bao gồm hai phần:

1. Chi phí vận chuyển khi đi theo các tuyến đường nối các cặp thành phố.
2. Chi phí cho việc phải đi qua mỗi thành phố trên tuyến đường vận chuyển, ngoại trừ thành phố xuất phát và thành phố kết thúc.

Lập trình tìm cách vận chuyển với chi phí vận chuyển nhỏ nhất cho mỗi vận đơn.

Input

• Dòng đầu tiên chứa hai số ~N, M~, trong đó ~N~ là số lượng thành phố (~2 < N < 101~), ~M~ là số lượng vận đơn.
• Dòng thứ hai chứa ~N~ số nguyên dương ~b_1, b_2, \dots, b_n~, trong đó ~b_i~ là chi phí phải trả khi đi qua thành phố ~i~.
• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~N~ số nguyên dương ~a_{i1}, a_{i2}, \dots, a_{in}~, trong đó ~a_{ij}~ là chi phí đi theo tuyến đường nối thành phố ~i~ và thành phố ~j~. Qui ước ~a_{ij} = -1~ nếu không có tuyến đường nối thành phố ~i~ với thành phố ~j~.
• Dòng thứ ~k~ trong ~M~ dòng tiếp theo chứa hai số nguyên ~d_k, c_k~ là thành phố xuất phát và thành phố kết thúc trong vận đơn thứ ~k~.

Output

• Ghi ra ~M~ cặp dòng, cặp dòng thứ ~i~ ứng với vận đơn thứ ~i~, trong đó dòng đầu ghi tuyến đường vận chuyển dưới dạng dãy các thành phố trên tuyến đường vận chuyển bắt đầu từ thành phố ~d_i~ và kết thúc ở thành phố ~c_i~, dòng thứ hai ghi chi phí vận chuyển theo tuyến đường tìm được.

Sample Input 1

5 3
5 17 8 3 1
0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
1 3
3 5
2 4

Sample Output 1

1 5 4 3
21
3 4 5
16
2 1 5 4
17