Problem Description

Sometimes you need to solve this kind of problem: determine whether a number $x$ is valid.

$x$ is valid if and only if it satisfies the following conditions:

• The format of $x$ is valid. A valid integer is either $0$, or is formed by concatenating, in order, an optional minus sign, a digit from $1$ to $9$, and then some digits from $0$ to $9$.
• $x$ is within the interval $[l, r]$ (i.e., $l \le x \le r$).

You need to implement such a validator. Given $l$ and $r$, you will check multiple times whether each $x$ is valid.

Input Format

The first line contains three integers $l, r, T$, indicating that the validator checks the interval $[l, r]$, and there are $T$ values of $x$ to be checked.

The next $T$ lines each contain one $x$, the number to be checked. It is guaranteed that the length of $x$ is at least $1$ and it consists only of '0'~'9' and '-', and '-' appears only as the first character.

Output Format

Output $T$ lines in total, each containing one integer representing the validation result for each $x$.

The results are defined as follows: $0$ means $x$ is valid; $1$ means the format of $x$ is invalid; $2$ means the format of $x$ is valid but $x$ is not within the interval $[l, r]$.

-3 3 4
0
00
-0
100000000000000000000

0
1
1
2

Hint

For $100\%$ of the testdata, $0 \le T \le 512$, and $l, r$ are within the range of 64-bit signed integers (i.e., $-2^{63} \le l \le r \le 2^{63} - 1$).

The input file size is guaranteed to be no more than $\text{128KB}$. The testdata is generated under Linux, and there is no '\r' character.

Below are some special constraints (they do not include each other):

• For $5\%$ of the testdata, $T = 0$.
• For $25\%$ of the testdata, it is guaranteed that the format of $x$ is always valid.
• For $30\%$ of the testdata, it is guaranteed that if the format of $x$ is valid, then $x$ is within the range of 64-bit signed integers.

There is an unscored hack test point, intended to test the handling of long long boundary values. If you get UnAC with 100 points, it may be because you did not consider this case.

Translated by ChatGPT 5