Problem:


Problem E: The Genome Database of All Space Life

In 2300, the Life Science Division of Federal Republic of Space starts
a very ambitious project to complete the genome sequencing of all
living creatures in the entire universe and develop the genomic
database of all space life.
Thanks to scientific research over many years, it has been known that
the genome of any species consists of at most 26 kinds of
molecules, denoted by English capital letters (i.e. A
to Z).

What will be stored into the database are plain strings consisting of
English capital letters.
In general, however, the genome sequences of space life include
frequent repetitions and can be awfully long.
So, for efficient utilization of storage, we compress N-times
repetitions of a letter sequence seq into
N(seq), where N is a natural 
number greater than or equal to two and the length of seq is at
least one.
When seq consists of just one letter c, we may omit parentheses and write Nc.

For example, a fragment of a genome sequence:

ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC

can be compressed into:

4(AB)XYXYXYABABABABXYXYXYCCCCCCCCCC

by replacing the first occurrence of ABABABAB with its compressed form.
Similarly, by replacing the following repetitions of XY,
AB, and C, we get:

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

Since C is a single letter, parentheses are omitted in this
compressed representation.
Finally, we have:

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

by compressing the repetitions of 4(AB)3(XY).
As you may notice from this example, parentheses can be nested.

Your mission is to write a program that uncompress compressed genome
sequences.

Input

The input consists of multiple lines, each of which contains a
character string s and an integer i separated by a
single space. 

The character string s, in the aforementioned manner,
represents a genome sequence.
You may assume that the length of s is between 1 and 100,
inclusive.
However, of course, the genome sequence represented by s may be
much, much, and much longer than 100.
You may also assume that each natural number in s representing the
number of repetitions is at most 1,000. 

The integer i is at least zero and at most one million. 

A line containing two zeros separated by a space follows the last input line and indicates
the end of the input.

Output

For each input line, your program should print a line containing the
i-th letter in the genome sequence that s represents.
If the genome sequence is too short to have the i-th element,
it should just print a zero.
No other characters should be printed in the output lines.

Note that in this problem the index number begins from zero rather
than one and therefore the initial letter of a sequence is its zeroth element.

Sample Input

ABC 3
ABC 0
2(4(AB)3(XY))10C 30
1000(1000(1000(1000(1000(1000(NM)))))) 999999
0 0

Output for the Sample Input

0
A
C
M



Sample input:
ABC 3
ABC 0
2(4(AB)3(XY))10C 30
1000(1000(1000(1000(1000(1000(NM)))))) 999999
0 0


Sample output:
0
A
C
M

Submission status: Wrong Answer

Solution code:
import re
import sys

DIGIT_RE = re.compile(r'\d+')

def decomp(string, cur, idx):
    # returns a tuple (decomp_str, endpos)
    decomp_str = ''

    while cur < len(string):
        if string[cur].isdigit():
            m = DIGIT_RE.match(string, pos=cur)
            times = int(m.group())
            dstr, end = decomp(string, m.end(), idx)
            if times*len(dstr) > idx:
                print dstr[(idx-len(decomp_str))%len(dstr)]
                raise Exception

            decomp_str += times*dstr
            cur = end

        elif string[cur].isalpha():
            decomp_str += string[cur]
            cur += 1

        elif string[cur] == ')':
            cur += 1  # ignore

        elif string[cur] == '(':
            tmp = decomp(string, cur+1, idx)
            decomp_str += tmp[0]
            cur += tmp[1] + 1

    return decomp_str, cur

def main():
    while True:
        string, idx = raw_input().split()
        if (string, idx) == ('0', '0'):
            break

        idx = int(idx)

        try:
            dstr = decomp(string, 0, idx)[0]
            print dstr[idx] if idx < len(dstr) else 0
        except Exception:
            continue

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def check(c):
    return (ord(c) >= ord('0') and ord(c) <= ord('9'))

def check2(c):
    return (ord(c) >= ord('A') and ord(c) <= ord('Z'))

while True:
    S1, S2 = raw_input().split()
    if S1 == '0':
        break
    N = int(S2)
    SS = ''
    flag = False
    for i in range(len(S1) - 1):
        SS += S1[i]
        if check(S1[i]) and not check(S1[i + 1]) and S1[i + 1] != '(':
            SS += '('
            flag = True
        elif flag:
            SS += ')'
            flag = False
    SS += S1[len(S1) - 1]
    if flag:
        SS += ')'
    S1 = '(' + SS + ')'
    for i in range(26):
        c = chr(ord('A') + i)
        S1 = S1.replace('(' + c, '("' + c)
        S1 = S1.replace(c + ')', c + '")')
        S1 = S1.replace(')' + c, ')"' + c)
        S1 = S1.replace(c + '(', c + '"(')
        for j in range(10):
            c2 = str(j)
            S1 = S1.replace(c + c2, c + '"' + c2)
    S1 = S1[1 : -1]
    print S1
    S1 = S1.replace('(', ',')
    SS = ''
    for i in range(len(S1) - 1):
        SS += S1[i]
        if not check(S1[i]) and check(S1[i + 1]):
            SS += '('
    SS += S1[len(S1) - 1]
    if check(S1[0]):
        SS = '(' + SS
    S1 = '(1, ' + SS + ')'
    S1 = S1.replace(')(', '),(')
    S1 = S1.replace(')"', '),"')
    S1 = S1.replace('"(', '",(')
    print S1
    hoge = eval(S1)
    ans = 0
    m = {}
    def func(obj):
        if type(obj) == type("hoge"):
            m[obj] = len(obj)
            return len(obj)
        num = obj[0]
        ret = 0
        for i in range(1, len(obj)):
            ret += num * func(obj[i])
        m[obj] = ret
        return ret

    def func2(obj, index):
        if type(obj) == type("hoge"):
            return obj[index]
        num = obj[0]
        S = m[obj]
        index %= S / num
        ret = 0
        for i in range(1, len(obj)):
            ret += m[obj[i]]
            if ret > index:
                ret -= m[obj[i]]
                return func2(obj[i], index - ret)
        return '0'
    
    func(hoge)
    #print m
    if N >= m[hoge]:
        print '0'
    else:
        print func2(hoge, N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def check(c):
    return (ord(c) >= ord('0') and ord(c) <= ord('9'))

def check2(c):
    return (ord(c) >= ord('A') and ord(c) <= ord('Z'))

while True:
    S1, S2 = raw_input().split()
    if S1 == '0':
        break
    N = int(S2)
    SS = ''
    flag = False
    for i in range(len(S1) - 1):
        SS += S1[i]
        if check(S1[i]) and not check(S1[i + 1]) and S1[i + 1] != '(':
            SS += '('
            flag = True
        elif flag:
            SS += ')'
            flag = False
    SS += S1[len(S1) - 1]
    if flag:
        SS += ')'
    S1 = '(' + SS + ')'
    for i in range(26):
        c = chr(ord('A') + i)
        S1 = S1.replace('(' + c, '("' + c)
        S1 = S1.replace(c + ')', c + '")')
        S1 = S1.replace(')' + c, ')"' + c)
        S1 = S1.replace(c + '(', c + '"(')
        for j in range(10):
            c2 = str(j)
            S1 = S1.replace(c + c2, c + '"' + c2)
    S1 = S1[1 : -1]
    S1 = S1.replace('(', ',')
    SS = ''
    for i in range(len(S1) - 1):
        SS += S1[i]
        if not check(S1[i]) and check(S1[i + 1]):
            SS += '('
    SS += S1[len(S1) - 1]
    if check(S1[0]):
        SS = '(' + SS
    S1 = '(1, ' + SS + ')'
    S1 = S1.replace(')(', '),(')
    S1 = S1.replace(')"', '),"')
    S1 = S1.replace('"(', '",(')
    hoge = eval(S1)
    ans = 0
    m = {}
    def func(obj):
        if type(obj) == type("hoge"):
            m[obj] = len(obj)
            return len(obj)
        num = obj[0]
        ret = 0
        for i in range(1, len(obj)):
            ret += num * func(obj[i])
        m[obj] = ret
        return ret

    def func2(obj, index):
        if type(obj) == type("hoge"):
            return obj[index]
        num = obj[0]
        S = m[obj]
        index %= S / num
        ret = 0
        for i in range(1, len(obj)):
            ret += m[obj[i]]
            if ret > index:
                ret -= m[obj[i]]
                return func2(obj[i], index - ret)
        return '0'
    
    func(hoge)
    #print m
    if N >= m[hoge]:
        print '0'
    else:
        print func2(hoge, N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def check(c):
    return (ord(c) >= ord('0') and ord(c) <= ord('9'))

def check2(c):
    return (ord(c) >= ord('A') and ord(c) <= ord('Z'))

while True:
    S1, S2 = raw_input().split()
    if S1 == '0':
        break
    N = int(S2)
    SS = ''
    flag = False
    for i in range(len(S1) - 1):
        SS += S1[i]
        if check(S1[i]) and not check(S1[i + 1]) and S1[i + 1] != '(':
            SS += '('
            flag = True
        elif flag:
            SS += ')'
            flag = False
    SS += S1[len(S1) - 1]
    if flag:
        SS += ')'
    S1 = '(' + SS + ')'
    for i in range(26):
        c = chr(ord('A') + i)
        S1 = S1.replace('(' + c, '("' + c)
        S1 = S1.replace(c + ')', c + '")')
        S1 = S1.replace(')' + c, ')"' + c)
        S1 = S1.replace(c + '(', c + '"(')
        for j in range(10):
            c2 = str(j)
            S1 = S1.replace(c + c2, c + '"' + c2)
    S1 = S1[1 : -1]
    S1 = S1.replace('(', ',')
    SS = ''
    for i in range(len(S1) - 1):
        SS += S1[i]
        if not check(S1[i]) and check(S1[i + 1]):
            SS += '('
    SS += S1[len(S1) - 1]
    if check(S1[0]):
        SS = '(' + SS
    S1 = '(1, ' + SS + ')'
    S1 = S1.replace(')(', '),(')
    S1 = S1.replace(')"', '),"')
    S1 = S1.replace('"(', '",(')
    hoge = eval(S1)
    ans = 0
    m = {}
    def func(obj):
        if type(obj) == type("hoge"):
            m[obj] = len(obj)
            return len(obj)
        num = obj[0]
        ret = 0
        for i in range(1, len(obj)):
            ret += num * func(obj[i])
        m[obj] = ret
        return ret

    def func2(obj, index):
        if type(obj) == type("hoge"):
            return obj[index]
        num = obj[0]
        S = m[obj]
        index %= S / num
        ret = 0
        for i in range(1, len(obj)):
            ret += m[obj[i]]
            if ret > index:
                ret -= m[obj[i]]
                return func2(obj[i], index - ret)
        return '0'
    
    func(hoge)
    if N >= m[hoge]:
        print '0'
    else:
        print func2(hoge, N)

Submission status: Accepted

Solution code:
from string import digits, ascii_uppercase
def parse(S):
    S += "$"
    cur = 0
    res = []
    def expr():
        nonlocal cur
        R = []; l = 0
        while 1:
            c = S[cur]
            if c in digits:
                v = number()
                if S[cur] == '(':
                    cur += 1 # '('
                    R0, l0 = expr()
                    cur += 1 # ')'
                    l += v * l0
                    R.append((v, l0, R0))
                else:
                    c = S[cur]
                    cur += 1 # 'A' ~ 'Z'
                    l += v
                    R.append((v, 1, [c]))
            elif c in ascii_uppercase:
                cur += 1 # 'A' ~ 'Z'
                l += 1
                R.append(c)
            else:
                break
        return R, l

    def number():
        nonlocal cur
        v = 0
        while 1:
            c = S[cur]
            if c not in digits:
                break
            v = 10*v + int(c)
            cur += 1 # '0' ~ '9'
        return v

    R, l = expr()
    return R, l

def solve(res, x):
    R, l = res
    if l <= x:
        return "0"
    cur = R
    while 1:
        for data in cur:
            if isinstance(data, str):
                if x == 0:
                    return data
                x -= 1
            else:
                v, l, R = data
                if x < v*l:
                    cur = R
                    x %= l
                    break
                x -= v*l

while 1:
    S, x = input().split()
    if S == "0":
        break
    x = int(x)
    R, l = res = parse(S)
    if l <= x:
        print("0")
        continue
    print(solve(res, x))

Submission status: Accepted

Solution code:
def uncompress(text, L):
    newText = ''
    pos = 0
    while True:
        if len(newText) > L:
            break
        if pos >= len(text):
            break
        if text[pos].isdigit():
            endDigit = getEndDigit(text, pos)
            num = int(text[pos : endDigit])
            if text[endDigit] == '(':
                endPar = getEndParenthesis(text, endDigit)
                insideText = uncompress(text[endDigit + 1 : endPar - 1], L - len(newText))
                for _ in range(num):
                    newText += insideText
                    if len(newText) > L:
                        break
                pos = endPar
            else:
                newText += (text[endDigit] * num)
                pos = endDigit + 1
        else:
            newText += text[pos]
            pos += 1
    return newText

def getEndParenthesis(text, pos):
    count = 0
    while True:
        if text[pos] == '(':
            count += 1
        elif text[pos] == ')':
            count -= 1
        if count == 0:
            return pos + 1
        pos += 1

def getEndDigit(text, pos):
    while True:
        if not text[pos].isdigit():
            return pos
        pos += 1

if __name__ == '__main__':
    while True:
        text, idx = input().strip().split()
        if text == '0' and idx == '0':
            break

        text = uncompress(text, int(idx))
        print(text[int(idx)] if len(text) > int(idx) else 0)

Submission status: Accepted

Solution code:
def main():
    def pearser(s, n):
        if s == "":
            return ""
        i = 0
        while 1:
            if not s[i].isdigit():break
            i += 1
        if i == 0:
            r = pearser(s[i + 1:], n - 1)
            return s[0] + r
        if s[i] == "(":
            r = Parentp(s[i:], n, int(s[:i]))
        else:
            r = s[i] * int(s[:i])
            if len(r) >= n:
                return r[:n]
            r += pearser(s[i+1:], n - len(r))
        return r

    def Parentp(s, n, p):
        if s == "": return ""
        b = 0
        c = 0
        i = 0
        while 1:
            if s[i] == "(":
                c += 1
            if s[i] == ")":
                c -= 1
            if c == 0:
                break
            i += 1
        r = pearser(s[b + 1:i], n)
        l = len(r)
        if l * p >= n:
            r = r * (n // l + 1)
            return r[:n]
        r = r * p
        r += pearser(s[i+1:], n - len(r))
        return r

    def m(s,n):
        n = int(n)
        r = pearser(s, n + 1)
        if len(r) <= n:
            print(0)
            return
        print(r[n])

    while 1:
        s, n = map(str, input().split())
        if s == n == "0":
            break
        m(s, n)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def parse_expr(s,i,num):
    if i < len(s) and f_num[s[i]]:
        n,i = parse_num(s,i,num)
        if s[i] == "(":
            i += 1
            su = 0
            while i < len(s) and s[i] != ")":
                e,i = parse_expr(s,i,num)
                su += e
            return su*n,i+1
        else:
            k,i = parse_alp(s,i,n)
            return k+n-1,i
    else:
        k,i = parse_alp(s,i,num)
        return k,i

def parse_num(s,i,num):
    m = int(s[i])
    i += 1
    while i < len(s) and f_num[s[i]]:
        m *= 10
        m += int(s[i])
        i += 1
    return num*m,i

def parse_alp(s,i,num):
    k = 1
    i += 1
    while i < len(s) and f_alp[s[i]]:
        k += 1
        i += 1
    return k,i

def find(s,l,r,i):
    if l == r:
        return 0
    su,k = parse_expr(s,l,1)
    if i < su:
        if l < r and f_alp[s[l]]:
            return s[l+i]
        else:
            n,l = parse_num(s,l,1)
            if l < r and s[l] == "(":
                return find(s,l+1,k-1,i%(su//n))
            else:
                return find(s,l,k,i%(su//n))
    else:
        return find(s,k,r,i-su)
while 1:
    s,i = input().split()
    if s == i == "0":break
    i = int(i)
    f_alp = defaultdict(lambda : 0)
    f_num = defaultdict(lambda : 0)
    for a in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
        f_alp[a] = 1
    for a in range(10):
        f_num[str(a)] = 1
    print(find(s,0,len(s),i))

Submission status: Accepted

Solution code:
def string(s,i):
  l = 0
  while i < len(s) and s[i].isalpha():
    l += 1
    i += 1
  return i,l

def number(s,i):
  n = 0
  while i < len(s) and s[i].isdigit():
    n = n*10 + (ord(s[i])-ord('0'))
    i += 1
  return i,n

def block(s,i):
  if i < len(s) and s[i].isalpha():
    return string(s,i)
  else:
    i,n = number(s,i)
    if i < len(s) and s[i] == '(':
      i += 1
      sum = 0
      while i < len(s) and s[i] != ')':
        i,tmp = block(s,i)
        sum += tmp
      sum *= n
      i += 1
      return i,sum
    else:
      i,tmp = block(s,i)
      sum = tmp*n
      return i,sum

def find(s,i,j,p):
  if i == j:
    return 0
  k,l = block(s,i)
  if p < l:
    if i < j and s[i].isalpha():
      return s[i+p]
    else:
      i,n = number(s,i)
      if i < j and s[i] == '(':
        return find(s,i+1,k-1,p%(l//n))
      else:
        return find(s,i,k,p%(l//n))
  else:
    return find(s,k,j,p-l)

if __name__ == '__main__':
  while True:
    [s,p] = input().split()
    p = int(p)
    if s == "0" and p == 0:
      break
    print(find(s,0,len(s),p))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(s,n):
        def _f(s, n):
            # print('_f', s,n)
            l = len(s)
            if l == 0 or n < 1:
                return ''
            r = ''
            if '1' <= s[0] <= '9':
                c = int(s[0])
                ti = 1
                for i in range(1,l):
                    ti = i
                    if not ('0' <= s[i] <= '9'):
                        break
                    c *= 10
                    c += int(s[i])
                if s[ti] == '(':
                    k = 1
                    ki = ti+1
                    for i in range(ti+1,l):
                        if s[i] == '(':
                            k += 1
                        elif s[i] == ')':
                            k -= 1
                            if k == 0:
                                ki = i
                                break
                    kr = _f(s[ti+1:ki], n)
                    kl = len(kr)
                    if kl * c >= n:
                        r = kr * (n//kl+1)
                        return r[:n]
                    r = kr * c
                    r += _f(s[ki+1:], n - len(r))
                    return r
                else:
                    r += s[ti] * c
                    if len(r) >= n:
                        return r[:n]
                    r += _f(s[ti+1:], n - len(r))
                    return r
            r = s[0] + _f(s[1:], n - 1)
            return r

        fr = _f(s, n+1)
        # print(len(fr),fr[n:n+1])
        if len(fr) <= n:
            return '0'
        return fr[n]

    while 1:
        s,n = LS()
        if s == '0' and n == '0' :
            break
        rr.append(f(s, int(n)))
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys

sys.setrecursionlimit(1000000)

def check(c):
    return (ord(c) >= ord('0') and ord(c) <= ord('9'))

while True:
    S1, S2 = raw_input().split()
    if S1 == '0':
        break
    N = int(S2)
    SS = ''
    flag = False
    for i in range(len(S1) - 1):
        SS += S1[i]
        if check(S1[i]) and not check(S1[i + 1]) and S1[i + 1] != '(':
            SS += '('
            flag = True
        elif flag:
            SS += ')'
            flag = False
    SS += S1[len(S1) - 1]
    if flag:
        SS += ')'
    S1 = '(' + SS + ')'
    for i in range(26):
        S1 = S1.replace('(' + chr(ord('A') + i), '("' + chr(ord('A') + i))
        S1 = S1.replace(chr(ord('A') + i) + ')', chr(ord('A') + i) + '")')
    S1 = S1[1:-1]
    S1 = S1.replace('(', ',')
    SS = ''
    for i in range(len(S1) - 1):
        SS += S1[i]
        if not check(S1[i]) and check(S1[i + 1]):
            SS += '('
            flag = True
    SS += S1[len(S1) - 1]
    if check(S1[0]):
        SS = '(' + SS
    S1 = '(1, ' + SS + ')'
    S1 = S1.replace(')(', '),(')
    hoge = eval(S1)
    ans = 0
    m = {}
    def func(obj):
        if type(obj) == type("hoge"):
            m[obj] = len(obj)
            return len(obj)
        num = obj[0]
        ret = 0
        for i in range(1, len(obj)):
            ret += num * func(obj[i])
        m[obj] = ret
        return ret

    def func2(obj, index):
        if type(obj) == type("hoge"):
            return obj[index]
        num = obj[0]
        S = m[obj]
        index %= S / num
        ret = 0
        for i in range(1, len(obj)):
            ret += m[obj[i]]
            if ret > index:
                ret -= m[obj[i]]
                return func2(obj[i], index - ret)
        return '0'
    
    func(hoge)
    #print m
    if N >= m[hoge]:
        print '0'
    else:
        print func2(hoge, N)

Submission status: Runtime Error

Solution code:
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
const double EPS = 1e-10;
const double PI  = acos(-1.0);

struct node{
	int number;
	string letters;
	vector<node> children;
	char get_char(int index,int &pos){
		int remain=index-pos+1;
		if(letters!=""){
			if(letters.size()>=remain){
				return letters[remain-1];
			}else{
				pos+=letters.size();
				return '\0';
			}
		}else{
			REP(i,number){
				REP(j,children.size()){
					char c=children[j].get_char(index,pos);
					if(c!='\0'){
						return c;
					}
				}
			}
			return '\0';
		}
	}
};

int number(string &s,int &pos){
	int ret=0;
	while(isdigit(s[pos])){
		ret*=10;
		ret+=s[pos]-'0';
		pos++;
	}
	return ret;
}

string letters(string &s,int &pos){
	string ret;
	while(isalpha(s[pos])){
		ret+=s[pos];
		pos++;
	}
	return ret;
}

void lp(string &s,int &pos){
	assert(s[pos]=='(');
	pos++;
}
void rp(string &s,int &pos){
	assert(s[pos]==')');
	pos++;
}
string letter(string &s,int &pos){
	assert(isalpha(s[pos]));
	string ret;
	ret+=s[pos];
	pos++;
	return ret;
}

vector<node> nodes(string &s,int &pos){
	vector<node> ret;
	while(pos<s.size()){
		if(isdigit(s[pos])){
			node nod;
			nod.number=number(s,pos);
			if(s[pos]=='('){
				lp(s,pos);
				nod.children=nodes(s,pos);
				rp(s,pos);
			}else{
				node c;
				c.letters=letter(s,pos);
				nod.children.push_back(c);
			}
			ret.push_back(nod);
		}else if(isalpha(s[pos])){
			node nod;
			nod.letters=letters(s,pos);
			ret.push_back(nod);
		}else{
			break;
		}
	}
	return ret;
}

int main(){
	string s;
	int index;
	while(cin>>s>>index,s!="0"||index){
		int pos=0;
		vector<node> roots=nodes(s,pos);
		pos=0;
		REP(i,roots.size()){
			char c=roots[i].get_char(index,pos);
			if(c!='\0'){
				cout<<c<<endl;
				goto next;
			}
		}
		cout<<0<<endl;
		next:;
	}
}