Initially, a string s contains only one character:

s = "a"

You are given a vector ops containing only 0 and 1. For every operation, the current string is transformed and appended to itself.

There are two types of operations:

Operation 0

Duplicate the current string and append the duplicate unchanged to the end.

For example:

s = "abc"

After operation 0:

s = "abcabc"

Operation 1

Duplicate the current string, increment every character in the duplicate by 1, and append it to the original string.

Characters are incremented cyclically:

a → b
b → c
...
y → z
z → a

For example:

s = "abc"

After operation 1:

s = "abcbcd"

You are given:

• A vector ops containing the operations to perform.
• An integer k representing a 1-indexed position in the final string.

After performing all operations in ops, return the character present at position k.

Input Format

• The first line contains an integer N, the number of operations.
• The second line contains N integers, where each integer is either 0 or 1.
• The third line contains an integer k.

Output Format

Print the character at the k-th position of the final string.

Example 1

Input

3
0 1 0
5

Operations

Initially:

"a"

After operation 0:

"aa"

After operation 1:

"abb"

After operation 0:

"abbabb"

The 5th character is:

b

Output

b

Example 2

Input

2
1 1
4

Initially:

"a"

After operation 1:

"ab"

After operation 1:

"abbc"

The 4th character is:

c

Output

c

Constraints

• 1 ≤ N ≤ 10^5
• ops[i] ∈ {0, 1}
• 1 ≤ k ≤ 2^N
• The final string may be exponentially large, so constructing the complete string is not feasible.