Có N thành phố. Biết rằng đường đi giữa hai thành phố bất kì (nếu có) đều là đường hai chiều. Sơ đồ mạng lưới giao thông của N thành phố này cho bởi bảng đối xứng A[i,j]. Trong đó: A[i,j] là độ dài đường đi từ thành phố i đến thành phố j. A[i,j]=0 nếu không có đường đi từ thành phố i đến thành phố j. A[i,j]=A[j,i] và A[i,i]=0. A[i,j] nguyên, không âm.

Tìm đường đi ngắn nhất giữa 2 thành phố P và Q.

INPUT

Dữ liệu vào gồm N+2 dòng:

Dòng đầu là số N (N nguyên dương, N ≤ 50);

Dòng i+1 (1 ≤ i ≤ N) ghi N số nguyên A[i,1], A[i,2,...A[i,N].

Dòng N+2 ghi 2 số P và Q.

OUTPUT

Xuất ra màn hình cho biết độ dài đường đi ngắn nhất từ P đến Q và sơ đồ đường đi hoặc thông báo "Khong co duong di".

Ví dụ:

Input

6
0 5 0 0 0 9
5 0 6 0 0 0
0 6 0 7 0 0
0 0 7 0 8 0
0 0 0 8 0 9
9 0 0 0 9 0
1 5

Output:

18
1 6 5