모든 우주 생명체의 유전체 데이터베이스

2300년, 우주 연방 공화국의 생명과학부는 야심 찬 프로젝트를 시작한다. 우주에 존재하는 모든 생명체의 유전체 서열을 해독하여 모든 우주 생명체의 유전체 데이터베이스를 구축하는 것이다. 오랜 연구 끝에, 어떤 종의 유전체든 최대 26가지 분자로만 이루어지며 각 분자는 영문 대문자(A부터 Z까지)로 표기된다는 사실이 밝혀졌다.

데이터베이스에는 영문 대문자로만 이루어진 문자열이 저장된다. 그러나 실제 유전체 서열에는 반복이 자주 나타나며 그 길이가 매우 길 수 있다. 저장 공간을 아끼기 위해, 부분 문자열 seq가 N번 반복되는 것을 N(seq)로 압축한다. 여기서 N은 2 이상의 자연수이고 seq의 길이는 1 이상이다. seq가 한 글자 c인 경우에는 괄호를 생략하고 Nc로 쓸 수 있다.

예를 들어, 다음과 같은 유전체 서열 조각은

ABABABABXYXYXYABABABABXYXYXYCCCCCCCCCC

맨 앞의 ABABABAB를 압축한 형태로 바꾸면 다음과 같이 압축할 수 있다.

4(AB)XYXYXYABABABABXYXYXYCCCCCCCCCC

이어서 XY, AB, C의 반복을 차례로 압축하면 다음을 얻는다.

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

C는 한 글자이므로 괄호를 생략했다. 마지막으로 4(AB)3(XY)의 반복을 압축하면 다음을 얻는다.

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

이 예에서 볼 수 있듯이 괄호는 중첩될 수 있다.

압축된 유전체 서열이 주어졌을 때, 그것이 나타내는 서열의 특정 글자를 구하는 프로그램을 작성하라.

입력은 여러 줄로 이루어지며, 각 줄에는 문자열 s와 정수 i가 공백 하나로 구분되어 주어진다.

문자열 s는 위의 표기법으로 유전체 서열을 나타낸다. s의 길이는 1 이상 100 이하이다. 다만 s가 나타내는 유전체 서열의 길이는 100보다 훨씬 길 수 있다. s에 등장하는 반복 횟수는 모두 1000 이하이다.

정수 i는 0 <= i <= 1000000을 만족한다.

입력의 끝은 공백으로 구분된 두 개의 0으로 이루어진 줄로 표시된다.

각 입력 줄에 대해, s가 나타내는 유전체 서열의 i번째 글자를 출력한다. 인덱스는 0부터 시작하므로 서열의 첫 글자는 0번째 글자이다. 서열의 길이가 짧아 i번째 글자가 존재하지 않으면 대신 0 하나만 출력한다. 그 밖의 문자는 출력하지 않는다.