고약한 계산

하나의 변수 $x$로 이루어진 식 $f$와 여러 개의 $x$ 값이 주어진다. 각 값에 대해 $f(x)$를 계산하되, 그 값의 마지막 자리(끝자리) 만 구하면 된다.

$f(x)$는 매우 커질 수 있으므로 정확한 값은 필요 없고 마지막 자리만 구한다. 이 문제에 등장하는 모든 수(식, 각 $x$ 값, 그리고 모든 답)는 주어진 정수 $B$에 대한 $B$진법 위치 기수법으로 표기된다.

후위 표기법

식은 역폴란드 표기법(RPN)이라고도 하는 후위 표기법으로 주어진다. 일반적인 중위 표기법에서는 연산자를 두 피연산자 사이에 쓴다. 예를 들어 1 + 2, 1 + 2 * 3, (1 + 2) * 3 과 같다. 후위 표기법에서는 연산자를 피연산자 바로 뒤에 쓰므로, 같은 식이 각각 1 2 +, 1 2 3 * +, 1 2 + 3 * 로 표기된다. RPN은 피연산자와 연산자의 순서만으로 식이 유일하게 결정되므로 괄호가 필요 없다.

$B$진법 기수법

$B$진법에서 숫자열 $d_k d_{k-1} \dots d_1 d_0$ 은 $d_k B^k + d_{k-1} B^{k-1} + \dots + d_1 B + d_0$ 을 나타내며, 각 자리 $d_i$ 는 $0 \le d_i \le B - 1$ 을 만족한다. 9보다 큰 자리는 대문자로 표기한다: A = 10, B = 11, ..., Z = 35. 예를 들어 10진법의 29는 6진법으로 45, 16진법으로 1D 로 쓴다.

첫째 줄에는 공백 하나로 구분된 두 정수 $B$와 $N$이 주어진다. $2 \le B \le 36$ 은 기수법의 밑이고, $1 \le N \le 100000$ 은 주어지는 $x$ 값의 개수이다.

둘째 줄에는 후위 표기법으로 된 식 $f$가 공백 하나로 구분된 원소들의 나열로 주어진다. 각 원소는 다음 중 하나이다.

• 숫자와 대문자로 이루어진 문자열. $B$진법으로 표기된 음이 아닌 정수를 나타낸다(그 값은 2000000000을 넘지 않는다).
• 소문자 x. 변수를 나타낸다.
• +(덧셈), -(뺄셈), *(곱셈).

이어지는 $N$개의 줄에는 각각 하나의 $x$ 값이 위와 같은 방식으로 $B$진법으로 주어진다(그 값도 2000000000을 넘지 않는다).

입력은 항상 올바르다. 즉 둘째 줄은 올바른 후위 표기식이며, 숫자와 대문자로 이루어진 모든 문자열은 유효한 $B$진법 정수이다. 둘째 줄의 길이는 100000자를 넘지 않는다.

정확히 $N$개의 줄을 출력한다. $i$번째 줄에는 입력의 $(i + 2)$번째 줄에 주어진 $x$에 대한 $f(x)$의 $B$진법 마지막 자리에 해당하는 한 글자(숫자 또는 대문자)를 출력한다. 주어지는 모든 $x$ 값에 대해 $f(x)$는 음이 아님이 보장된다.