Nim with a Robot Referee

Nim is a game for two players. Several bags hold marbles. On your turn you pick one bag and take marbles out of it. You may take as many as you like, but you must take at least one, and you may not take from two different bags in the same turn. Once you take marbles the turn passes to your opponent, and whoever has no marble left to take on their turn loses.

Myungwoo decided to play Nim against Seungyong. Both of them know the winning strategy of the plain game very well, so Myungwoo, who wants to win, brought in a robot referee. The robot referee checks that the previous player took marbles by the rules, and before Myungwoo or Seungyong takes marbles it inspects every bag against two criteria.

• If the number of marbles in a bag is divisible by at least one of $p_1, p_2, \dots, p_N$, the robot throws that bag away.
• If the number of marbles in a bag is divisible by none of $q_1, q_2, \dots, q_M$, the robot throws that bag away.

Nobody can take marbles from a bag that has been thrown away. The robot repeats the inspection on every bag before each turn begins.

Myungwoo found out that a winning strategy exists under these rules as well. He still felt the setup was too mean, so he gave Seungyong the first turn and explained what the robot referee does. The game is tomorrow and Seungyong wants to find the winning strategy. Given the number of marbles each bag holds at the start, help Seungyong.

The first line contains three integers $N$, $M$ and $K$ separated by spaces ($1 \le N$, $1 \le M$, $N + M \le 16$, $1 \le K \le 20$). $N$ and $M$ are the counts of the conditions the robot referee uses to inspect a bag, and $K$ is the number of bags at the start.

The second line contains $N$ natural numbers $p_1$ through $p_N$ separated by spaces. All of them are at least $1$ and at most $10^6$.

The third line contains $M$ natural numbers $q_1$ through $q_M$ separated by spaces. All of them are at least $1$ and at most $10^6$.

The fourth line contains $K$ integers separated by spaces, the number of marbles in each bag. All of them are at least $1$ and at most $10^{12}$.

Print $K$ lines. Line $i$ describes the winning strategy for Seungyong taking marbles from the $i$-th bag of the input on his first turn.

Assume Myungwoo and Seungyong both play as well as they can. Print how many different marble counts Seungyong can take from that bag and win, and the smallest of those counts, separated by a space. If winning by taking marbles from that bag is impossible, or if the robot referee has already thrown that bag away before Seungyong takes his turn, print 0 0.