Elimination of contestants from a live IQ contest on a TV channel is decided in phases.
Initially at phase 0, N
contestants, where N = 2n
,
n < 10
, are selected through a special online IQ contest in which a total of
M
(M > N)
contestants participate.
The contestants are identified by distinct registration numbers
1, 2,..., M
. The
selected contestants are ranked distinctly from 1 to N
according to their
performance in the online contest. They are qualified to participate in the
live contest.
In the pth
phase,
p = 1, 2,..., n, Kp
contestants participate in the live contest, where
Kp = 2n-p+1
.
On the basis of response to questions presented during the show, Kp/2
of Kp
contestants are ranked distinctly from 1 to Kp/2
.
These Kp/2
contestants qualify to participate in the next phase. At
the nth
phase there are only two contestants and the one selected at
this phase is the winner of the contest.
You are required to write a program that identifies the
winner of the contest, given the following information:
- INFO_1: Registration numbers of N
contestants who are selected through the online IQ
contest, in order of the rank in the online IQ contest, and
- INFO_2: A total of N - 1
qualified contestants in different phases; K2
in phase 1, K3
in phase 2, ...
, and Kn+1
in phase n
. Qualified contestants of
different phases appear in order of phases, i.e., phase 1, phase 2, ...
, phase
n
. Further, qualified contestants in a phase, say phase p
, appear in the order
of the rank in the phase, i.e., the rank in phase p
. A qualified contestant of
a phase, say phase p
, is identified by his/her rank in the previous phase,
i.e., in phase p - 1
.
Input may contain multiple test cases. For each case there are two input lines.
The first line gives N
integers representing INFO_1
while the second line gives N - 1
integers representing INFO_2.
In each input line integers are
separated by space. The input terminates with a line containing 0 as input.
For each test case there is only one output line. The line
prints the registration number of the winner of the contest.
23 18 6 20
4 2 2
29 57 4 33 5 12 16 18
7 1 5 3 2 1 1
0
18
29
RSS