Spontaneous Trip

Sangil travels on impulse. One journey goes like this.

1. He goes to the airport of the city he is in.
2. He buys a ticket for one of the flights leaving that airport, picked at random. Every flight leaving the airport is equally likely.
3. He boards that flight and lands in another city.

One trip consists of exactly $K$ journeys, and it always starts at the airport ICN. Some airports have no departing flight at all, so a trip that reaches one of them cannot continue.

A course is the sequence of airports Sangil passes through during the $K$ journeys. The probability of a course is the product of the probabilities of the flights picked in each journey. Among the courses that finish all $K$ journeys, find the last airport of the course with the highest probability. Such a course always exists.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains the number of airports $N$ and the number of journeys in one trip $K$ ($2 \le N \le 100$, $1 \le K \le 1000$).

Each of the next $N$ lines contains the IATA code of one airport. A code consists of three uppercase letters, the codes are pairwise different, and one of them is ICN.

Each of the next $N$ lines contains $N$ integers. The $j$-th integer on the $i$-th line, $S_{ij}$, is the number of flights that leave airport $i$ and land at airport $j$ ($0 \le S_{ij} \le 100$, $S_{ii} = 0$). Airport $i$ has $S_{i1} + S_{i2} + \dots + S_{iN}$ departing flights in total, so the probability that Sangil flies from airport $i$ to airport $j$ is $S_{ij}$ divided by that sum.

For each test case, print the IATA code of the last airport of the most likely course on its own line. If several most likely courses end at different airports, print the code that comes first in alphabetical order.