The Genome Database of All Space Life

In the year 2300, the Life Science Division of the Federal Republic of Space begins an ambitious project: to sequence the genomes of every living creature in the universe and build a genomic database of all space life. Years of research have shown that the genome of any species is made of at most 26 kinds of molecules, each written as an uppercase English letter (A to Z).

The database stores plain strings of uppercase English letters. In practice, however, genome sequences contain frequent repetitions and can be extremely long. To save space, an N-fold repetition of a substring seq is compressed as N(seq), where N is a natural number with N >= 2 and seq has length at least one. When seq is a single letter c, the parentheses may be omitted and written as Nc.

For example, a fragment of a genome sequence:

ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC

can be compressed to:

4(AB)XYXYXYABABABABXYXYXYCCCCCCCCCC

by replacing the first ABABABAB with its compressed form. Compressing the following repetitions of XY, AB, and C gives:

4(AB)3(XY)4(AB)3(XY)10C

Because C is a single letter, its parentheses are omitted. Finally, compressing the repetition of 4(AB)3(XY) yields:

2(4(AB)3(XY))10C

As this example shows, parentheses may be nested.

Write a program that, given a compressed genome sequence, reports individual letters of the sequence it represents.

Each input line contains a string s and an integer i, separated by a single space.

The string s encodes a genome sequence using the notation above. The length of s is between 1 and 100, inclusive. The genome sequence that s represents, however, may be far longer than 100. Every repetition count appearing in s is at most 1000.

The integer i satisfies 0 <= i <= 1000000.

Input ends with a line containing two zeros separated by a space.

For each input line, print the i-th letter of the genome sequence that s represents. Indexing starts at 0, so the first letter is the 0-th element. If the sequence is too short to have an i-th letter, print a single 0 instead. Print nothing else.