Nasty Calculations

You are given a formula $f$ of a single variable $x$, together with many values of $x$. For each value you must evaluate $f(x)$ and report only its last digit.

Because $f(x)$ can be very large, its exact value is not needed — only its last digit. Every number in this task (the formula, each value of $x$, and every answer) is written in the base-$B$ positional numeral system for a given integer $B$.

Postfix notation

The formula is given in postfix notation, also known as Reverse Polish Notation (RPN). In ordinary infix notation an operator is written between its operands, e.g. 1 + 2, 1 + 2 * 3, or (1 + 2) * 3. In postfix notation the operator is written directly after its operands, so the same expressions become 1 2 +, 1 2 3 * +, and 1 2 + 3 *. RPN needs no parentheses, because the order of the operands and operators already determines the expression uniquely.

Base-$B$ numeral systems

In the base-$B$ system a digit string $d_k d_{k-1} \dots d_1 d_0$ represents $d_k B^k + d_{k-1} B^{k-1} + \dots + d_1 B + d_0$, where every digit $d_i$ satisfies $0 \le d_i \le B - 1$. Digits greater than 9 are written with uppercase letters: A = 10, B = 11, ..., Z = 35. For example, 29 in base 10 is written 45 in base 6 and 1D in base 16.

The first line contains two integers $B$ and $N$ separated by a single space, where $2 \le B \le 36$ is the base of the numeral system and $1 \le N \le 100000$ is the number of values of $x$.

The second line describes the formula $f$ in postfix notation as a sequence of elements separated by single spaces. Each element is one of:

• A string of digits and uppercase letters, denoting a non-negative integer written in base $B$ (its value does not exceed 2000000000).
• The lowercase letter x, standing for the variable.
• + (addition), - (subtraction), or * (multiplication).

Each of the next $N$ lines contains one value of $x$, written in base $B$ in the same way (its value does not exceed 2000000000).

The input is guaranteed to be valid: the second line is a well-formed postfix expression, and every string of digits and uppercase letters is a valid integer in base $B$. The second line contains at most 100000 characters.

Print exactly $N$ lines. The $i$-th line must contain a single character — a digit or an uppercase letter — equal to the last digit, in base $B$, of $f(x)$ for the value of $x$ on the $(i + 2)$-th line of the input. It is guaranteed that $f(x)$ is non-negative for every given value of $x$.