Description

话说运气极其不好的LCS在某年某月某日得了水痘，于是YCC买一大堆东西去送给LCS。 已知LCS家住x点，YCC家住w点。YCC从自己家坐车过去，中途可能经过n家店面，买东西送给LCS。（总不能空手而去吧）每家店距YCC的家的最短距离为一个定值，有的可以直接开车（路途中车子一直保持匀速率运动）去，有的需要从其他店绕行。由于LCS生命垂危，YCC必须尽快赶到。

已知出租车收费1元/km。请你帮YCC算算他坐车要多少钱才能到。

Input

每组第一行为整数，即经过的店数n。x编号a，w编号b。 接下来的n行是一个n*n的矩阵，矩阵中第i行j列的整数aij（0<=aij<=10000）表示第i点到第j点的距离，每行的n个整数之间用空格隔开。 (0<n<=100) 接下来是可能的编号总数k(0<k<=10000)。 最后是x编号和w编号。每排一组。

Output

每组编号对应的最少花费，一排一组(按编号输入的顺序)。

Sample

Input

3
0 1 10
1 0 2
10 2 0
2
1 3
2 3

Output

3
2

Source: Xenocide