Winner Prediction (APCS 2022-01 Intermediate)

There are \(n\) contestants in a competition that proceeds through repeated rounds. Contestants are numbered from \(1\) to \(n\). Contestant \(i\) has strength \(S_i\) and adaptability \(T_i\); both values may change after a match.

Before the first round, the contestants are ordered as \(idx_1,idx_2,\ldots,idx_n\). In each round, adjacent contestants are paired from the front of the queue. If the number of contestants is odd, the last contestant has a bye and advances directly to the next round; neither of that contestant's attributes changes in this round.

Consider one match. Before the match, the first contestant has strength \(a\) and adaptability \(b\), while the second contestant has strength \(c\) and adaptability \(d\):

1. If \(ab\ge cd\), the first contestant wins. The four attributes after the match are

   $$a+\left\lfloor\frac{cd}{2b}\right\rfloor,\quad b+\left\lfloor\frac{cd}{2a}\right\rfloor,\quad c+\left\lfloor\frac{c}{2}\right\rfloor,\quad d+\left\lfloor\frac{d}{2}\right\rfloor.$$

2. If \(ab<cd\), the second contestant wins. The four attributes after the match are

   $$a+\left\lfloor\frac{a}{2}\right\rfloor,\quad b+\left\lfloor\frac{b}{2}\right\rfloor,\quad c+\left\lfloor\frac{ab}{2d}\right\rfloor,\quad d+\left\lfloor\frac{ab}{2c}\right\rfloor.$$

Here \(a,b,c,d\) are all the values before this match. All four new values must be computed from the old values. Every division is integer division, so its fractional part is discarded.

After all matches in a round are complete, construct the next queue as follows:

1. append all winners in their relative order from the current round;
2. append the contestant with a bye, if any, at the end of the winner queue;
3. append all non-eliminated losers in their relative order.

Every contestant initially has zero losses. A contestant is eliminated immediately upon receiving the \(m\)-th loss and does not enter the next round. The competition continues until exactly one contestant remains. Output that contestant's number.

Input

The first line contains two positive integers \(n\) and \(m\): the number of contestants and the number of losses required for elimination.

The second line contains \(n\) positive integers \(S_1,S_2,\ldots,S_n\), the initial strengths.

The third line contains \(n\) positive integers \(T_1,T_2,\ldots,T_n\), the initial adaptability values.

The fourth line contains \(n\) distinct integers \(idx_1,idx_2,\ldots,idx_n\). They form a permutation of \(1\) through \(n\) and describe the order in the first round.

Constraints

• \(2\le n\le1000\)
• \(1\le m\le5\)
• \(1\le S_i,T_i\le100\)
• A product of two attributes during the computation may exceed \(2^{32}\), but it is guaranteed not to exceed \(2^{60}\).

Output

Output the number of the final winner.

Scoring

Sample Input 1

4 1
4 2 5 3
2 5 1 5
1 2 3 4

Sample Output 1

4

Sample Explanation 1

Contestants \(2\) and \(4\) win the two matches in the first round. Since \(m=1\), both losers are immediately eliminated, so the next queue is \([2,4]\). Contestant \(4\) wins the second round, so the answer is \(4\).

Sample Input 2

4 5
4 1 5 3
6 5 1 6
4 1 3 2

Sample Output 2

1

Sample Explanation 2

Contestants \(4\) and \(1\) win in the first round. Contestants \(3\) and \(2\) have only one loss each and are not eliminated, so the next queue is \([4,1,3,2]\). Continuing the same simulation eventually leaves contestant \(1\).

Source

APCS January 2022, Programming Task 2; ZeroJudge h082, Winner Prediction; explanation by Yi-Che Wang.