NIM

Annoula and Toto are playing the classic game of Nim. The game is played as follows:

Starting with a certain number of marbles on the table, each player must remove 1, 2, or 3 marbles on their turn.
The winner is the one who takes the last marble.
Annoula always plays first.

Since both players play optimally, they already know that the outcome of the game is predetermined based on the initial number of marbles. As a result, they got bored with these rules and are now experimenting with different choices for the number of marbles that can be removed.

Help Annoula figure out which starting numbers of marbles guarantee that, if she plays optimally, she will win!

Important! If the remaining marbles are fewer than one of the available choices, Annoula and Totos cannot make that move.

Input Data (STDIN)

The ~1~st line contains a positive integer ~M\;(M \le 10)~, the number of choices the players have for removing marbles.
The ~2~nd line line contains ~M~ integers, the choices ~m_1, m_2, ... , m_M~ (~m_i \le 100~) in ascending order.
The ~3~d line contains a positive integer ~Q~, the number of queries for the initial number of marbles.
This is followed by ~Q~ (~Q \le 20~) lines, each containing a number ~q_i~, the initial number of marbles.

Output Data (STDOUT)

The output consists of ~Q~ lines, each with a single number, 0 or 1, depending on whether Annoula can definitely win with the corresponding initial number of marbles.

Examples

1st
Input (STDIN)

3  
1 2 3  
5  
2  
4  
5  
8  
10

Output (STDOUT)

1  
0  
1  
0  
1

Example Explanation:
The players have ~3~ choices:
They can remove ~1~, ~2~, or ~3~ marbles per turn.
Additionally, there are 5 queries:

• ~q_1 = 2~: Annoula can play the second move and win the game directly.
• ~q_2 = 4~: No matter what move Annoula makes, Totos can win.
  • If Annoula removes ~1~ marble, Totos can take the remaining ~3~.
  • If she removes ~2~, Totos can remove the other ~2~.
  • If she removes ~3~, Totos takes the last ~1~.
• ~q_3 = 5~: Annoula can only remove ~1~ marble and leave Toto with ~4~, a situation in which Totos cannot win (as explained above). Hence, Annoula wins.
• ~q_4 = 8~: Similarly, Annoula cannot win starting from ~8~ marbles.
• ~q_5 = 10~: Following the same logic, Annoula can win starting from ~10~ marbles.

2nd
Input (STDIN)

3  
1 3 4  
3  
2  
5  
7

Output (STDOUT)

0  
1  
0

Subtasks

• ~20\%~ of the points: the ~m_i~ values are the numbers ~\{1,2,\dots,M\}~, ~q_i \le 100.000~
• ~30\%~ of the points: ~q_i \le 25~
• ~50\%~ of the points: ~q_i \le 100.000~