题目描述

一条从 $1$ 到 $n$ 的数轴上有 $m$ 名快递员。

每名快递员有一条送货路线，可以用三个整数 $t_i,c_i,p_i$ 来描述第 $i$ 名快递员的送货路线。

具体来说，如果 $c_i>0$，则第 $i$ 名快递员会在 $t_i$ 时刻从 $p_i$ 点出发以每秒 $1$ 单位长度的速度向 $n$ 号点方向出发前进 $c_i$ 时刻后停下；如果 $c_i<0$，则第 $i$ 名快递员会在 $t_i$ 时刻从 $p_i$ 点出发以每秒 $1$ 单位长度的速度向 $1$ 号点方向出发前进 $-c_i$ 时刻后停下。

你要雇佣这些快递员中的一部分来完成一些运送订单。第 $i$ 名快递员仅在 $[t_i,t_i+|c_i|]$ 时刻工作，他可以在这段时间里的任意整数时刻交接快递。而快递员能进行快递的交付当且仅当在某一时刻两名快递员位于同一个整点上。具体来说，$i,j$ 号快递员可以在整数时刻 $t$，整点位置 $p$ 进行交接快递，当且仅当：

$$t\in [t_i,t_i+|c_i|] \cup [t_j,t_j+|c_j|]$$ $$p = p_i+\frac{t-t_i}{\mathrm{sgn}(c_i)}=p_j+\frac{t-t_j}{\mathrm{sgn}(c_j)} $$

其中 $\mathrm{sgn}(x)$ 为符号函数。

现在你收到了 $q$ 份订单，其中第 $i$ 份订单包含两个整数 $w_i,x_i$，表示这份订单希望你将快递在最晚 $w_i$ 时刻从 $1$ 号点运送到 $x_i$ 号点，你想算出完成这份订单最少需要雇佣多少名快递员。如果无解，即雇佣了所有快递员也无法完成订单，则输出 $\texttt{-1}$。注意这 $q$ 份订单是相互独立的，所有快递员每次都需要重新雇佣。

输入

第一行包含两个整数 $n,m$ 表示数轴的长度及快递员的数量。

接下来 $m$ 行每行包括三个整数 $t_i,c_i,p_i$ 描述该快递员的运送路线。

接下来一行一个整数 $q$ 表示订单的数量。

接下来 $q$ 行每行两个整数 $w_i,x_i$ 表示这份订单要求的最晚时刻及送达地点。

保证 $1\le n,t_i\le 2000, ~1\le m\le 10^6,~ 1\le q\le 10^5$，快递员只在 $1$ 到 $n$ 的数轴上移动。

输出

输出 $q$ 行，其中第 $i$ 行包含一个整数表示完成第 $i$ 份订单最少需要雇佣多少名快递员，或输出 $\texttt{-1}$ 表示该订单无法完成。

10 10
2 1 5
5 4 3
8 7 1
9 8 2
3 1 7
6 3 6
9 6 4
6 2 8
6 7 -2
10 8 -8
4
11 10
12 9
13 10
14 10

4
3
4
3