ELIM - Elimination

no tags 

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 

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.

Output 

For each test case there is only one output line. The line prints the registration number of the winner of the contest.

Sample Input 

23 18 6 20
4 2 2
29 57 4 33 5 12 16 18
7 1 5 3 2 1 1
0

Sample Output 

18
29


Added by:Duc
Date:2008-12-09
Time limit:0.147s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM Kanpur 2006