题目描述

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

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

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

输入格式

第一行两个正整数 $n,m$。

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

接下来一行一个正整数 $q$。

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

输出格式

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

样例 1

input

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

output

0
2
2
2
3
3
5

样例 2

input

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

output

0
2
2
2
3
3
5

数据范围与提示

对于所有数据，$1\le n,q \le 10^5,1\le v_i \le 10^9,0\le l_i\le m\le 10^9,c\in [0,m]$。

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