A higher resolution is required to access the IDE

- 25

## Statement

## Goal

In the Pascal Triangle number series, each line of the triangle contains one more element than the previous line, and all the elements are based on the elements of the previous line like so:lineElement[n] = prevLineElement[n-1] + prevLineElement[n]

The endpoints (n = 0 and n = nMax) are calculated by inserting an implied 0 element at the beginning and end of the previous line. So, for example, a five-line Pascal Triangle looks like:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

A Pascal Trapezoid follows the same rules, but has a starting line with more than one element, like so:

2 3 4 5

2 5 7 9 5

2 7 12 16 14 5

In this puzzle, the sequence can contain textual elements as well. The rules for dealing with element combination are as follows:

- If both input elements can be interpreted as a number, then they are summed.

- If either input element can not be interpreted as a number, then the inputs are concatenated. Element n-1 remains before element n in the concatenation.

- If a textual element is at the beginning or end of a line, then the elements n-1 or nMax+1 are implied empty strings instead of zeros.

Here is an example of a completely textual Pascal Trapezoid sequence:

red violet blue

red redviolet violetblue blue

red redredviolet redvioletvioletblue violetblueblue blue

red redredredviolet redredvioletredvioletvioletblue redvioletvioletbluevioletblueblue violetblueblueblue blue

And here is an example of a mixed textual and numerical Pascal Trapezoid:

2 5 a 9 2 4 8 b

2 7 5a a9 11 6 12 8b b

2 9 75a 5aa9 a911 17 18 128b 8bb b

2 11 975a 75a5aa9 5aa9a911 a91117 35 18128b 128b8bb 8bbb b

Your job will be to calculate the

`N`th element on the

`L`th line of a Pascal Trapezoid, based on a given starting line.

Input

**Line 1:**Three space-separated integers:

`E`representing the number of elements in the starting line,

`L`the line to calculate for the output, and

`N`the element on line

`L`to calculate.

**Line 2:**The starting line, consisting of

`E`space-separated elements.

Output

The

`N`th element of the`L`th line of the Pascal Trapezoid.Example

Input

1 5 2 1

Output

4

A higher resolution is required to access the IDE

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants