Problem L
Hot Potato
You and your friends are playing a game of Hot Potato. All $n$ people sit in a circle and pass around the ‘hot potato’ toy until it turns red. The person holding it when it turns red is “out” and must leave the circle. Since several of your friends have their own copies of the toy, you decide to rotate which one is used in each round. Each toy turns red after a certain number of passes.
Input
The input consists of a single test case. The first line of input contains two integers $n$ and $k$, ($2 \le n, k \le 10^6)$, where $n$ is the number of people playing and $k$ is the number of toys available. The next $n$ lines contain the names of the players, which consists of between $3$ and $32$ upper or lowercase English letters and/or digits. The first name is the person who starts with the toy, and it is passed in order from there. All player names are unique.
The next $k$ lines each contain an integer $l$ $(0 \le l<10^6)$ denoting how many passes each toy endures before turning red. $l=0$ means the toy turns red as soon as the first person receives it, so that person is eliminated before even passing the toy. If there are fewer toys than players, toys will be reused in the order they are listed, which may potentially be multiple times.
Output
Output the name of the last person remaining in the circle.
Explanation for Sample Input 1
There are $n=5$ players and $k=2$ toys. The players are Kendall, Jess, Alex, Riley, Cam and the toy is passed around in that order. There are two toys: the first turns red after 3 passes, and the second turns red after 7 passes. Kendall starts with the first toy and it is passed around the circle like so:
Kendall, Jess, Alex, Riley
When Riley receives the toy, it turns red, so Riley is eliminated. Now the second toy is passed around, starting with the next person in the circle:
Cam, Kendall, Jess, Alex, Cam, Kendall, Jess, Alex
When Alex receives the toy, it turns red, so Alex is eliminated. Now the first toy is used again for the $3$ people remaining:
Cam, Kendall, Jess, Cam
When Cam receives the toy, it turns red, so Cam is eliminated. Now the other toy is used for the $2$ people remaining:
Kendall, Jess, Kendall, Jess, Kendall, Jess, Kendall, Jess
When Jess receives the toy, it turns red, so Jess is eliminated and Kendall wins the game.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 2 Kendall Jess Alex Riley Cam 3 7 |
Kendall |
