Type: Default 2000ms 256MiB

橙汁调配

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

太酸不喝,太甜不喝,没味道不喝,味道太重不喝……

——某位不愿透露姓名的学长

有 $n$ 种橙汁,第 $i$ 种甜度为 $a_i$、酸度为 $b_i$。每种无限供应。

你可以进行以下操作任意次:

$\quad$· 任选两瓶已有的橙汁,甜度分别为 $A_1$、$A_2$,酸度为 $B_1$、$B_2$;

$\quad$· 任选两个正整数 $X$,$Y$;

$\quad$· 混合得到一瓶甜度为 $\displaystyle \frac{X\times A_1+Y\times A_2}{X+Y}$,酸度为 $\displaystyle\frac{X\times B_1+Y\times B_2}{X+Y}$的饮料。

现有 $m$ 次询问,每次给定 $x,y$,判断能否调出甜度恰好为 $x$、酸度恰好为 $y$ 的橙汁。若能则输出 $1$,则输出 $0$。

Input Format

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

接下来 $n$ 行,每行两个整数 $a_i,b_i$,描述第 $i$ 种橙汁。

接下来 $m$ 行,每行两个整数 $x,y$,表示一次询问。

保证 $1 \le n \le 5 \times 10^5$,$1 \le m \le 100$,$0 \le a_i,b_i,x,y \le 10^9$。

Output Format

$m$ 行,每行输出 $1$ 或 $0$,分别表示能否调出满足题目要求的饮料。

3 4
0 0
4 0
0 4
2 2
4 4
5 0
0 0
1
0
0
1
2 4
0 0
10 0
5 0
3 3
0 0
10 0
1
0
1
1
1 2
5 5
5 5
6 6
1
0

Hint

对于第一组测试用例,选取 $1$ 份第二种果汁和 $1$ 份第三种果汁,可以调配得到目标为 $(2,2)$ 的果汁;对于目标为 $(0,0)$ 的果汁,已经存在了。