B. 小 Y 的初中数学问题

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

众所周知，ymuuy 老师擅长初中数学和毒瘤。但显然普及组不能给他毒瘤的机会。因此他选择考你初中数学！

题目描述

你有 $n$ 个函数 $y_1,y_2,\ldots,y_n$ ，其中 $y_i=a_ix+b_i$ 。

接下来有 $q$ 个问题，每个问题会给出一个 $x$ ，求此时有哪些 $i$ 满足 $y_i>0$ ，并求出这些 $i$ 的按位异或结果。

输入的第一行有两个正整数 $n,q$ 表示函数个数与询问个数。

之后 $n$ 行，其中第 $i$ 行有两个整数 $a_i,b_i$ 表示一个函数。保证 $a_i$ 是自然数。

之后 $q$ 行，每行一个整数 $x$ 表示一个问题。

对于每个询问输出一行，表示对应的答案。

3
0
1

这三个样例分别满足测试点 $3,9,10$ 的限制。

【样例解释】

现有四个函数： $y_1=2x+5,y_2=x+4,y_3=3,y_4=-1$ 。

当 $x=-4$ 时， $y_1=-3,y_2=0,y_3=3,y_4=-1$ ，只有 $y_3>0$ ，输出 $3$ 。
当 $x=-1$ 时， $y_1=y_2=y_3=3,y_4=-1$ 。所以输出 $1\oplus2\oplus 3=0$ （其中 $\oplus$ 表示异或）。
当 $x=-3$ 时， $y_1=-1,y_2=1,y_3=3,y_4=-1$ ，所以输出 $2\oplus 3=1$ 。

测试点编号	$n=$	$q=$	$a_i,\lvert b_i\rvert,\lvert x\rvert\le$	特殊性质
$1$	$11$	$10$	$1000$	$a_i=0$
$2$	$2992$	$3000$	$10$	$a_i>0$
$3$	$2993$		$100$
$4$	$2994$		$1000$
$5$	$2995$		$10^4$
$6$	$2996$	$10^5$	$10$
$7$	$10^5-3$		$100$
$8$	$10^5-2$		$1000$
$9$	$10^5-1$		$10^4$
$10$	$10^5$		$3\times 10^4$	不作保证

【数据范围】

提示：你可以通过 $n$ 的个位判定测试点的性质。

对于全部数据，保证 $3\le n,q\le 10^5$ ， $0\le a_i,|b_i|,|x_i|\le 3\times 10^4$ ，输入文件中所有数字都是整数。