Drunkard's Path

Since he left prison, Marcos cannot stop drinking. He is a former marathon runner who was wrongly arrested on charges of stealing contest problems and selling them to Russian and Chinese competitors. After five years in prison, he was declared innocent for lack of evidence. The long wrongful imprisonment left him depressed, and since then he spends every night walking from bar to bar, corner to corner.

As his best friend, you are tired of searching the city for him after each night of drinking. So you decide to write a program that predicts where Marcos will be at the end of his nights.

Every night, before he goes out, Marcos tells you which bar he will visit first, so you always know where his drinking starts. After each drink, there is a chance that Marcos moves to another bar. The probability of moving to another bar is proportional to the quality of that bar divided by the distance between his current bar and the destination. The probability of staying at the current bar is proportional to the square root of that bar's quality.

In general, the probability $P_{i,j}$ that Marcos goes from bar $i$ to bar $j$ is

$P_{i,j} = \frac{\frac{Q_j}{D_{i,j}}}{\sum_{k \ne i} \frac{Q_k}{D_{i,k}} + \sqrt{Q_i}}$

The probability that Marcos stays at the same bar is

$P_{i,i} = \frac{\sqrt{Q_i}}{\sum_{k \ne i} \frac{Q_k}{D_{i,k}} + \sqrt{Q_i}}$

These formulas guarantee that for every $1 \le i \le n$,

$\sum_{j=1}^{n} P_{i,j} = 1$

Marcos drinks far more than the average person. One of his favorite stories when drunk is how he won a Russian vodka drinking contest. You know he can drink an arbitrarily large number of shots. For practical purposes, assume Marcos drinks an infinite number of shots in one night.

Given the bars, their qualities, and the distances between them, write a program that finds the bar where Marcos is most likely to be after his night of drinking.

Hint: the probabilities of Marcos being at each bar always sum to 1.

The input has several test cases. Each test case begins with a line containing two integers $n$ and $b$, $1 \le b \le n \le 100$, the number of bars in the city and the bar where Marcos starts his night.

Then $n$ lines follow, each containing one integer. The integer on the $i$-th line is the quality $Q_i$ of bar $i$.

Then $n$ more lines follow, each containing $n$ integers. The $j$-th integer on the $i$-th line is the distance $D_{i,j}$ between bar $i$ and bar $j$.

It is given that $0 \le Q_i, D_{i,j} \le 1000$ for all $i$ and $j$.

The input ends with a line “0 0”, which is not processed.

For each test case, print one line containing a single integer: the index of the bar where Marcos is most likely to be. If several bars tie, print the smallest index.