로봇 심판의 님 게임

님 게임은 두 사람이 번갈아 가며 하는 게임이다. 구슬이 들어 있는 주머니가 여러 개 있고, 자기 차례가 된 사람은 주머니 하나를 골라 그 안에서 구슬을 꺼낸다. 몇 개를 꺼내든 상관없지만 반드시 한 개 이상 꺼내야 하고, 한 차례에 두 개 이상의 주머니에서 꺼낼 수는 없다. 구슬을 꺼내면 상대의 차례가 되고, 자기 차례에 꺼낼 구슬이 없는 사람이 진다.

명우는 승용이와 님 게임을 하기로 했다. 둘 다 이 게임의 필승 전략을 훤히 알고 있어서, 이기고 싶은 명우는 로봇 심판을 데려왔다. 로봇 심판은 직전 사람이 규칙대로 구슬을 꺼냈는지 확인하고, 명우나 승용이가 구슬을 꺼내기 전에 모든 주머니를 두 가지 기준으로 검사한다.

• 주머니에 든 구슬의 개수가 $p_1, p_2, \dots, p_N$ 중 하나로라도 나누어떨어지면 그 주머니를 폐기한다.
• 주머니에 든 구슬의 개수가 $q_1, q_2, \dots, q_M$ 중 어느 것으로도 나누어떨어지지 않으면 그 주머니를 폐기한다.

폐기된 주머니에서는 더 이상 구슬을 꺼낼 수 없다. 검사는 매 차례가 시작되기 전에 모든 주머니를 대상으로 다시 이루어진다.

명우는 이런 규칙 아래에서도 필승 전략이 있다는 사실을 알아냈다. 그래도 자신이 너무 치사하다고 여겼는지 승용이에게 첫 차례를 양보하고 로봇 심판이 하는 일을 알려 주었다. 게임은 내일이고, 승용이는 필승 전략을 찾고 싶어 한다. 처음에 각 주머니에 담긴 구슬의 개수가 주어질 때 승용이를 도와주자.

첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다 ($1 \le N$, $1 \le M$, $N + M \le 16$, $1 \le K \le 20$). $N$과 $M$은 로봇 심판이 주머니를 검사할 때 쓰는 조건의 개수이고, $K$는 처음 주머니의 개수이다.

둘째 줄에 $p_1$부터 $p_N$까지 $N$개의 자연수가 공백으로 구분되어 주어진다. 이 수는 모두 $1$ 이상 $10^6$ 이하이다.

셋째 줄에 $q_1$부터 $q_M$까지 $M$개의 자연수가 공백으로 구분되어 주어진다. 이 수도 모두 $1$ 이상 $10^6$ 이하이다.

넷째 줄에 각 주머니에 담긴 구슬의 개수를 뜻하는 $K$개의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 $1$ 이상 $10^{12}$ 이하이다.

$K$개의 줄을 출력한다. $i$번째 줄에는 승용이가 첫 차례에 입력에서 $i$번째로 주어진 주머니에서 구슬을 꺼낼 때의 필승 전략을 적는다.

명우와 승용이가 모두 이기려고 최선을 다한다고 할 때, 그 주머니에서 꺼내면 승용이가 이기게 되는 구슬 개수가 몇 가지인지와 그중 가장 적게 꺼내는 경우의 구슬 개수를 공백으로 구분해 출력한다. 그 주머니에서 구슬을 꺼내 이기는 것이 불가능하거나 승용이가 꺼내기 전에 로봇 심판이 그 주머니를 폐기해 버렸다면 0 0을 출력한다.