Dankey Kang and his horde of clones.

Dankey Kang, Croneria's most fearsome villain, has decided to increase the size of his gang by creating many clone soldiers. Each clone can be one of two types, type 0 or type 1.

There are two possible methods of cloning, which can be described as a string of clone types $S$ and $T$. That is, $S$ and $T$ are strings only containing 0 and 1.

Initially, there is one clone of type 0 in the line. Then, the following process will continue indefinitely:

• The first clone in the line will leave the front of the line to fight.
• If that clone's type is 0, a string of clones matching $S$ will be added to the end of the line, in order.
• If that clone's type is 1, a string of clones matching $T$ will be added to the end of the line, in order.

Dankey Kang is then interested in $Q$ of the clones. In particular, he wants to know the type of the ${a_i}^{\text{th}}$ clone that leaves the line, indexed starting at $1$.

Constraints

For all subtasks:

$2\le |S|,|T|\le {10}^5$

$1\le Q\le {10}^5$

$1\le a_i\le {10}^{12}$

Subtask	Points	Additional Constraints
1	5	$|S|,|T|,Q,a_i\le 20$
2	15	$a_i\le {10}^6$
3	20	$|S|=|T|$
4	25	$|S|,|T|\le 10$
5	25	$|S|,|T|\ge 5000$
6	10	No additional constraints.

Input Specification

The first line will contain string $S$.

The second line will contain string $T$.

The third line will contain the integer $Q$.

On the next $Q$ lines, the $i^{\text{th}}$ line will contain integer $a_i$.

Output Specification

Output $Q$ lines. The $i^{\text{th}}$ line of output will contain the type of the ${a_i}^{\text{th}}$ clone that leaves the line.

Sample Input

100
10
9
1
2
3
4
5
6
7
8
9

Sample Output

0
1
0
0
1
0
1
0
0