Cho một đồ thị có hướng có trọng số gồm ~n~ đỉnh. Hai đỉnh bất kì đều có cạnh nối (ở cả hai hướng).

Bạn nhận được một dãy hoán vị ~c~ nguyên dương gồm ~n~ phần tử. Bạn sẽ chơi một trò chơi như sau:

• Trò chơi gồm ~n~ bước.
• Bước thứ ~i~, bạn sẽ xóa đỉnh ~c_i~ khỏi đồ thị. Khi xóa một đỉnh đi, bạn sẽ xóa luôn tất cả cạnh vào và ra của đỉnh đó.
• Tuy vậy, trước khi xóa đỉnh ~c_i~, bạn muốn tính toán xem đường đi ngắn nhất giữa tất cả các đỉnh còn lại trong đồ thị là bao nhiêu. Đường đi ngắn nhất này có thể đi qua mọi cạnh còn tồn tại.
• Gọi ~d(i,u,v)~ là đường đi ngắn nhất giữa đỉnh ~u~ và đỉnh ~v~ trong đồ thị trước khi xóa đỉnh ~c_i~, bạn cần tính ~\sum d(i,u,v)~, với ~u \neq v~ và ~u,v~ cùng tồn tại trong đồ thị đang xét.

Hãy in ra tổng cần tìm ở mỗi bước.

Input

• Dòng đầu chứa số nguyên ~n~ miêu tả số đỉnh.
• ~n~ dòng sau, mỗi dòng gồm ~n~ kí tự, miêu tả ma trận cạnh kề của đồ thị. Số thứ ~v~ trên dòng ~u~ là ~d_{u,v}~ miêu tả trọng số của cạnh nối ~(u,v)~.
• Dòng cuối cùng miêu tả dãy ~c~ là một hoán vị từ ~1~ tới ~n~.

Output

• In ra ~n~ số nguyên dương là kết quả tính được ở mỗi bước chơi.

Constraints

• ~1 \le n \le 500~
• ~0 \le d_{u,v} \le 10^9, d_{u,u} = 0~

Subtask

• Subtask ~1~ (~50\%~ số điểm): ~n \le 50~
• Subtask ~2~ (~50\%~ số điểm): không ràng buộc gì thêm

Sample Input 1:

2
0 5
4 0
1 2

Sample Output 1:

9 0 

Sample Input 2:

4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3

Sample Output 2:

17 23 404 0 

Mikoto đang ở trong một mê cung được biểu diễn bởi một bảng vuông gồm ~N~ hàng và ~N~ cột. Mỗi ô hoặc là ô trống, hoặc là ô bị chặn.

Ô nằm ở hàng ~i~, cột ~j~ được ký hiệu là ~(i, j)~ với ~1 <= i, j <= N~.

Ban đầu, Mikoto đứng tại ô ~(sx, sy)~ và muốn đi tới ô đích ~(gx, gy)~. Hai ô này luôn là ô trống.

Mikoto có thể thực hiện các thao tác sau, theo thứ tự bất kỳ, không giới hạn số lần:

• Bắn railgun theo hàng hiện tại: toàn bộ các ô trong hàng đang đứng sẽ trở thành ô trống. Thao tác này tốn ~A~ đơn vị thời gian.
• Bắn railgun theo cột hiện tại: toàn bộ các ô trong cột đang đứng sẽ trở thành ô trống. Thao tác này tốn ~A~ đơn vị thời gian.
• Đi bộ sang một ô kề cạnh đang trống: từ ~(x, y)~ có thể sang một trong bốn ô ~(x - 1, y)~, ~(x + 1, y)~, ~(x, y - 1)~, ~(x, y + 1)~ nếu ô đó nằm trong bảng. Thao tác này tốn ~B~ đơn vị thời gian.

Lưu ý rằng sau khi một hàng hoặc một cột bị bắn railgun, mọi ô trên hàng hoặc cột đó sẽ được xem là ô trống cho các bước di chuyển tiếp theo.

Do thể trạng mỗi ngày khác nhau, Mikoto muốn xét ~Q~ kịch bản. Ở kịch bản thứ ~i~, chi phí bắn railgun và đi bộ lần lượt là ~(ai, bi)~.

Với mỗi kịch bản, hãy tính thời gian nhỏ nhất để Mikoto đi từ ~(sx, sy)~ tới ~(gx, gy)~.

Input

• Dòng đầu chứa số nguyên ~N~.
• Dòng thứ hai chứa ~4~ số nguyên ~sx~, ~sy~, ~gx~, ~gy~.
• ~N~ dòng tiếp theo, mỗi dòng là một xâu độ dài ~N~ chỉ gồm:
  • ~.~: ô trống
  • ~\#~: ô bị chặn
• Dòng tiếp theo chứa số nguyên ~Q~.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~ai~, ~bi~.

Output

• In ra ~Q~ dòng.
• Dòng thứ ~i~ là đáp án cho kịch bản thứ ~i~: thời gian nhỏ nhất để đi từ ô xuất phát tới ô đích.

Subtask

• Subtask 1: ~N <= 300~ ~(50\%)~
• Subtask 2: Không có ràng buộc gì thêm ~(50%)~

Ràng buộc

• ~1 <= N <= 1000~
• ~1 <= sx, sy, gx, gy <= N~
• ~(sx, sy)~ và ~(gx, gy)~ ban đầu là ô trống
• ~1 <= Q <= 10^6~
• ~1 <= ai, bi <= 10^9~

Sample Input

4
1 1 4 1
....
###.
###.
....
3
13 213883
1315 3281
1 1

Sample Output

641662
11158
4

Có ~N~ trạm và ~M~ con đường hai chiều. Con đường thứ ~i~ nối hai trạm ~u_i,v_i~ và có độ dài ~w_i~.

Một tài xế muốn đi từ trạm ~1~ đến trạm ~N~. Trong hành trình, tài xế được phép đi qua một trạm hoặc một con đường nhiều lần.

Để không buồn ngủ, tài xế đặt ra quy tắc: độ dài các con đường đã đi phải liên tục đan xen tăng và giảm nghiêm ngặt.

Cụ thể, xét ba con đường liên tiếp có độ dài ~a,b,c~:

• Nếu ~a<b~ thì phải có ~b>c~.
• Nếu ~a>b~ thì phải có ~b<c~.</li>

Hai con đường đầu tiên của hành trình chỉ cần có độ dài khác nhau. Hành trình chỉ gồm một con đường luôn được xem là hợp lệ.

Hãy tìm tổng độ dài nhỏ nhất của một hành trình hợp lệ từ trạm ~1~ đến trạm ~N~. Nếu không tồn tại hành trình như vậy, in ra ~-1~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i,w_i~, mô tả một con đường hai chiều nối ~u_i~ và ~v_i~ có độ dài ~w_i~.

Output

In ra một số nguyên duy nhất là tổng độ dài nhỏ nhất của một hành trình hợp lệ từ trạm ~1~ đến trạm ~N~, hoặc ~-1~ nếu không tồn tại.

Ràng buộc

• ~2\le N,M\le2\cdot10^5~
• ~1\le u_i,v_i\le N~
• ~u_i\ne v_i~
• ~1\le w_i\le10^9~
• Đồ thị có thể chứa nhiều con đường nối cùng một cặp trạm.

Subtask

Ví dụ

Input

5 4
1 2 4
2 3 9
3 5 3
1 4 100

Output

16

Giải thích

Hành trình tối ưu là ~1\to2\to3\to5~, sử dụng các con đường có độ dài ~4,9,3~.

Ta có ~4<9>3~, nên hành trình hợp lệ. Tổng độ dài là ~4+9+3=16~.

Nước HNAMS gồm ~n~ thành phố và đang có kết hoạch liên kết chúng bằng ~m~ con đường cao tốc hai chiều. Các con đường được đánh số từ ~1~ tới ~m~, con đường thứ ~i~ liên kết thành phố ~u_i~ với ~v_i~ và có lợi nhuận là ~w_i~ (các giá trị ~w_i~ phân biệt). Các con đường được thiết kế để tất cả các cặp thành phố đều có thể trực tiếp hoặc gián tiếp đi tới nhau.

Để xây dựng các con đường đó, chính quyền HNAMS quyết định giao việc này cho ~k~ nhà thầu. Sau những vòng bỏ phiếu căng thẳng, các nhà thầu này được xếp ở các vị trí từ ~1~ tới ~k~ thể hiện sự ưu tiên trong việc chọn tuyến đường thi công.

Mỗi nhà thầu sẽ được chọn một tập hợp các con đường trong ~m~ đường cao tốc có sẵn trong kế hoạch, sao cho chúng không tạo ra bất kì chu trình nào và con đường không bị nhà thầu nào trước đó chọn. Giả sử, nếu nhà thầu chọn con đường ~\{1 \rightarrow 2; 2 \rightarrow 3; 3 \rightarrow 1; 4 \rightarrow 5\}~ là không thoả mãn, bởi có chu trình ~1 \rightarrow 2 \rightarrow 3 \rightarrow 1~. Lưu ý rằng ở ví dụ trên mũi tên được đánh hướng cho mục đích biểu diễn, còn trên thực tế thì các con đường là hai chiều.

Đầu tiên, nhà thầu thứ ~1~ sẽ được chọn trước, sau đó tới nhà thầu thứ ~2~, ... rồi tới nhà thầu thứ ~k~. Tất nhiên với cách này, một số con đường sẽ không được xây dựng, nhưng ở giai đoạn đầu của dự án thì đây là chuyện bình thường.

Tất nhiên, mỗi nhà thầu đều muốn tối đa hoá lợi ích của mình, vậy nên khi được chọn các con đường, họ sẽ chọn tập con đường mang tới tổng lợi nhuận lớn nhất có thể.

Nhiệm vụ của bạn là tính toán trước cho chính quyền HNAMS xem mỗi nhà thầu từ ~1~ tới ~k~ sẽ có lợi nhuận là bao nhiêu khi tất cả đều chọn tập con đường một cách tối ưu.

Input

• Dòng đầu tiên gồm ~3~ số nguyên dương ~n, m, k~ miêu tả số thành phố, số con đường cần xây dựng và số nhà thầu.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên dương ~u_i, v_i, w_i~ miêu tả con đường thứ ~i~ trong kế hoạch, kết nối thành phố ~u_i~ với ~v_i~

Output

• Gồm ~k~ dòng, dòng thứ ~i~ chứa giá trị là tổng lợi nhuận của nhà thầu thứ ~i~ trong cách chia tối ưu.

Subtask

• Trong tất cả các test ~w_i \leq 10^9~

• Có ~20\%~ test tương ứng ~20\%~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k = 1~.

• Có ~25\%~ test tương ứng ~25\%~ số điểm có ~n \le 10^3, m \le 10^4; k \le 1000~.
• Có ~35\%~ test tương ứng ~35\%~ số điểm có ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~.
• ~20\%~ số test còn lại ứng với ~20%~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~.

Sample

Có ~N~ trạm và ~M~ con đường hai chiều. Con đường thứ ~i~ nối hai trạm ~u_i,v_i~ và có độ dài ~w_i~.

Một phượt thủ muốn đi từ trạm ~1~ đến trạm ~N~. Phượt thủ được phép đi qua một trạm hoặc một con đường nhiều lần.

Trong hành trình, mỗi khi phượt thủ đi qua một con đường có độ dài lớn hơn nghiêm ngặt độ dài của mọi con đường đã đi trước đó, con đường này lập một kỷ lục mới và phượt thủ phải trả một khoản phí bằng độ dài của nó. Mọi lần di chuyển khác đều miễn phí.

Con đường đầu tiên của hành trình luôn được coi là một kỷ lục.

Hãy tìm tổng phí nhỏ nhất để đi từ trạm ~1~ đến trạm ~N~. Nếu không thể đến được trạm ~N~, in ra ~-1~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i,w_i~, mô tả một con đường hai chiều nối ~u_i~ và ~v_i~ có độ dài ~w_i~.

Đồ thị có thể chứa nhiều con đường nối cùng một cặp trạm.

Output

In ra một số nguyên duy nhất là tổng phí nhỏ nhất, hoặc ~-1~ nếu không thể đi từ trạm ~1~ đến trạm ~N~.

Ràng buộc

• ~2\le N,M\le2\cdot10^5~
• ~1\le u_i,v_i\le N~
• ~u_i\ne v_i~
• ~1\le w_i\le10^9~

Subtask

Ví dụ

Input

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

Output

10

Giải thích

Nếu đi thẳng theo hành trình ~1\to2\to4\to5\to6\to7~, các kỷ lục lần lượt là ~1,5,6,7,8~, nên tổng phí bằng ~27~.

Một cách tối ưu là:

1. Đi từ trạm ~1~ đến trạm ~2~ qua con đường dài ~1~, trả phí ~1~.
2. Đi từ trạm ~2~ sang trạm ~3~ qua con đường dài ~9~, trả thêm phí ~9~, rồi quay lại trạm ~2~ trên chính con đường đó mà không phải trả thêm.
3. Đi theo hành trình ~2\to4\to5\to6\to7~. Các con đường có độ dài ~5,6,7,8~ đều không vượt quá kỷ lục hiện tại là ~9~, nên được đi miễn phí.

Tổng phí là ~1+9=10~.