Frieze Patterns 

John is an architect with a rare interest in math. Recently, he discovered some curious way to describe friezes, those decorative borders constructed from repetitive patterns. Indeed, what John discovered were frieze patterns, mathematical objects consisting of an infinite set of numbers arranged in a triangular grid:

                     1   1   1   1   1   1   .
                       2   1   3   1   .   .   .
                         1   2   2   1   .   .   .
                           1   1   1   1   1   1   .

A frieze pattern has k (k $\geq$ 2 ) rows, each one consisting of an infinite set of numbers. The first and the last row are exclusively composed by ones. Each set of four adjacent numbers

                                    A
                                  B   C
                                    D

satisfies the relationship B*C = A*D + 1 . It is not difficult to see that the complete pattern is determined by the values of the first column and this rule. The example above shows some of the first values of a frieze pattern. As a matter of fact, a frieze pattern all of whose values are integer numbers is called an integer frieze pattern.

John has the idea of using integer frieze patterns in his designs (for example, using colors instead of numbers), and he knows, from a given sequence of integer values for the first column, if an integer frieze pattern follows. For this setting, he wants to know the value of a position in an integer frieze pattern, given the values of the first column.

Input 

The input consists of several test cases. The first line of each test case is an integer value N , 2 < N $\leq$ 1000 , that specifies the number of rows of the pattern. The second line of each test case corresponds to a pair of integer numbers i, j , with 1 < i < N and 1 < j < 10⁸ , which specify the row and the position in the row of the value to be reported. The last line contains N values, v₁, v₂,..., v_N , with 0 < v_i $\leq$ 1000 (for each 1 $\leq$ i $\leq$ N ), that correspond to the values of the first element in each row (notice that v₁ = v_N = 1 ). It is guaranteed that every described frieze pattern contains only integer values.

The end of the input is recognized by a number 0 in the place that should correspond to the number of rows of a pattern.

Output 

Each line of the output corresponds to a test case. The line must include a unique integer value corresponding to the value in the position (i, j) of the frieze pattern.

Sample Input 

4
2 3
1 2 1 1
6
5 9
1 1 1 1 2 1
0

Sample Output 

3
4