D. MINIM

取石子游戏的规则是这样的：有若干堆石子，两个玩家轮流操作，每个玩家每次要选一堆取走任意多个石子，但不能不取，无石子可取者输。

现在共有 堆石子，其中第 堆的数量为 ，现在 LCR 需要在每一堆中扔掉一部分（可以不扔也可以全扔），如果第 堆的石子在 LCR 操作后还有剩余，LCR 就需要付出 的代价。LCR 操作完成后神犇会搬来新的一堆个数在 之间的石子，两人玩取石子游戏，LCR 先手。神犇搬运新的一堆石子时会保证自己（后手）必胜，如果他无法做到这一点，就会立即结束游戏。

现在 LCR 有 次询问，每次给出一个 ，请你回答如果要让神犇搬来的石子数为 （不能让神犇结束游戏，即使这里要求 ），LCR 付出代价的总和至少是多少。如果 LCR 不可能通过调整石子使得神犇搬来的石子数为 ，输出 -1。

NIM is a game of strategy in which two players take turns removing stones from distinct piles. On each turn, a player must remove at least one stone, and may remove any number of stones provided they all come from the same pile. The player who has no stones to remove loses.

There are piles of stones, the -th pile has stones. Alice needs to remove some of the stones from each pile (removing zero or all of the stones from a certain pile is allowed). If the -th pile remains at least one stone after this operation, Alice has to pay a price of . After Alice's operation, Bob will create a pile of stones whose number is in and add it to the game to make sure that Alice — the player who moves first in this NIM game will lose.If he can't ensure that Alice will lose,he will exit from the game immediately.

Now Alice has queries. Each query gives an integer , and you need to calculate the minimal total price Alice needs to pay to ensure Bob’s new pile has exactly stones(making Bob exit from the game isn't allowed,even if ). If this is impossible, print -1 instead.

第一行两个正整数 。

接下来 行每行两个正整数 表示该堆石子的代价和数量。

接下来一行一个正整数 。

接下来 行每行一个正整数 表示询问。

The first line contains two integers .
Each of the following lines contains two integers .
The next line contains an integer . Each of the following lines contains an integers .

输出共 行，依次表示每次询问的答案，无解输出 -1。

Output contains lines,containing the answer of each query in order.

样例输入

4 6
2 3
4 4
3 5
5 2
7
0
1
2
3
4
5
6

样例输出

0
2
2
2
3
3
5

Sample Input

4 6
2 3
4 4
3 5
5 2
7
0
1
2
3
4
5
6

Sample Output

0
2
2
2
3
3
5

对于所有数据，。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

For all test cases, .

Detailed constraints and hints are as follows (blank grids denote the same constraints as mentioned above):