Patterns and Sequences

Problem code: ENCD10

Patterns and sequences always interests humans. So we brings to you quite an unusual Pattern. This pattern has the following properties: 


                     1   1   1   1   1   1   .
                       2   1   3   1   .   .   .
                         1   2   2   1   .   .   .
                           1   1   1   1   1   1   .
		    (example pattern)
1. Infinite set of numbers arranged in a triangular grid.
2. The pattern has k(k>=2) rows, each one consisting of an infinite set of numbers. The first and the last row are exclusively composed by ones.
3. Each set of four adjacent numbers, 
                                    A
                                 B   C
                                    D
satisfies the relationship B*C = A*D + 1 .The complete pattern can be determined by the values of the first column and this rule.
The example above shows some of the first values of this pattern. You must have come to know your task, find the value of a position in the 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 given that N>2 and N 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 i and j both being greater then 1 and also i is less than N and j is less than 100,000,000, i specify the row and j specifies the position in the row of the value to be reported. The last line contains N values, v1, v2,..., vN , with vi>0&vi 1000, (for each row), that correspond to the values of the first element in each row.
notice that v1 = vN = 1 . It is guaranteed that every described 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 must give the unique integer value corresponding to the value in the position (i, j) of the pattern.

Example

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

Output:
3
4

Author: rscrbv
Date Added: 19-01-2010
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

space in the above example

domore1 @ 24 Jan 2010 03:15 PM

space in the above example are representing a matrix position or not pls do reply.

rscrbv is ADMIN for this

rscrbv @ 24 Jan 2010 03:44 PM

rscrbv is ADMIN for this contest

@chandresh kumar devrani  > NO

rscrbv i.e. VIKAS MEHTA is

rscrbv @ 24 Jan 2010 05:01 PM

rscrbv i.e. VIKAS MEHTA is admin for this contest

nobody has solved the pattern

domore1 @ 24 Jan 2010 05:50 PM

nobody has solved the pattern and sequence problem

 

 

so please do take our program into consideration

 

 

thanking you

with a smilig and blushig bye bye

just salute ur competition

domore1 @ 24 Jan 2010 06:11 PM

just salute ur competition

Hint: optimize for memory.

mangalsingh29 @ 24 Jan 2010 09:13 PM

Hint: optimize for memory. and you will also find a pattern, so go with that

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions