취객의 길

마르코스는 감옥에서 나온 뒤로 술을 끊지 못하고 있다. 그는 전직 마라톤 선수였는데, 대회 문제를 훔쳐 러시아와 중국 참가자에게 팔았다는 혐의로 억울하게 체포되었다. 5년간 복역한 뒤에는 증거가 부족하다는 이유로 무죄가 선고되었다. 그러나 억울하게 오랜 시간 갇혀 지낸 탓에 우울증을 얻었고, 그 뒤로 매일 밤 이 술집 저 술집, 이 골목 저 골목을 떠돌아다닌다.

가장 친한 친구인 당신은 그가 술을 마시고 난 뒤 매번 도시 곳곳을 뒤지는 일에 지쳤다. 그래서 마르코스가 밤을 마친 뒤 어디에 있을지 예측하는 프로그램을 만들기로 했다.

매일 밤 마르코스는 술을 마시러 나가기 전에 도시의 어느 술집에 갈지 당신에게 알려준다. 그래서 당신은 그의 술자리가 어디서 시작되는지 항상 안다. 한 잔을 마실 때마다 그가 다른 술집으로 갈 확률이 있다. 다른 술집으로 갈 확률은 그 술집의 품질을 현재 술집과 목적지 사이의 거리로 나눈 값에 비례한다. 같은 술집에 머무를 확률은 그 술집 품질의 제곱근에 비례한다.

일반적으로 마르코스가 술집 $i$에서 술집 $j$로 갈 확률 $P_{i,j}$는 다음과 같다.

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

같은 술집에 머무를 확률은 다음과 같다.

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

이 식들은 모든 $1 \le i \le n$에 대해 다음을 보장한다.

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

마르코스는 보통 사람보다 훨씬 많이 마신다. 취했을 때 그가 가장 즐겨 하는 이야기는 러시아 보드카 마시기 대회에서 우승한 이야기다. 당신은 그가 원하는 만큼 얼마든지 많은 잔을 마실 수 있다는 것을 안다. 실용적인 목적을 위해, 마르코스가 하룻밤에 무한히 많은 잔을 마신다고 가정한다.

술집의 개수, 각 술집의 품질, 술집 사이의 거리가 주어졌을 때, 술자리가 끝난 뒤 마르코스가 있을 확률이 가장 높은 술집을 찾는 프로그램을 작성하라.

힌트: 마르코스가 각 술집에 있을 확률의 합은 항상 1이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 도시의 술집 수 $n$과 마르코스가 밤을 시작하는 술집 $b$가 주어진다. 단, $1 \le b \le n \le 100$이다.

이어서 $n$개의 줄에 정수가 하나씩 주어진다. $i$번째 줄의 정수는 술집 $i$의 품질 $Q_i$이다.

그다음 $n$개의 줄에 정수가 $n$개씩 주어진다. $i$번째 줄의 $j$번째 정수는 술집 $i$와 술집 $j$ 사이의 거리 $D_{i,j}$이다.

모든 $i$와 $j$에 대해 $0 \le Q_i, D_{i,j} \le 1000$이다.

입력의 마지막 줄은 “0 0”이며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 마르코스가 있을 확률이 가장 높은 술집의 번호를 정수 하나로 한 줄에 출력한다. 확률이 같은 술집이 여럿이면 번호가 가장 작은 술집을 출력한다.