题目描述

小 A 有 ~n~ 个关于 ~x~ 的方程，第 ~i~ 个方程形如 ~a_ix_i+b_i=c_i~。方程的解 ~x~ 均为正整数，例如下面几个方程都是符合要求的方程：

2x+4=10
-3x+13=10
4x-8=16

其中，第一组方程的解为 ~x_1=3~，第二组方程的解为 ~x_2=1~，第三组方程的解为 ~x_3=6~。

小 A 想要知道，给定 ~L,R~，在 ~L\leq x\leq R~ 的范围内，有多少个正整数 ~x~ 满足 ~x~ 是其中至少一个方程的解。为了防止你欺骗他，他会询问你 ~Q~ 次。

输入格式

第一行输入两个正整数 ~n,Q~，分别表示小 A 有的方程数，以及小 A 想要向你询问的次数。

第二行开始，往下 ~n~ 行，每行一个字符串，描述一个方程。

第 ~(n+2)~ 行开始，往下 ~Q~ 行，每行两个正整数 ~L,R~，表示一次询问，即给定 ~L,R~，询问在 ~L\leq x\leq R~ 的范围内，有多少个正整数 ~x~ 满足 ~x~ 是其中至少一个方程的解。

输出格式

对于每次询问，输出一行一个整数，表示有多少个在 ~L\leq x\leq R~ 的范围内的正整数 ~x~，满足 ~x~ 是其中至少一个方程的解。

输入输出样例 #1

输入 #1

3 4
2x+4=10
-3x+13=10
4x-8=16
1 6
1 8
3 6
4 5

输出 #1

3
3
2
0

输入输出样例 #2

输入 #2

5 3
5x-2=13
8x+5=45
4x-12=8
-2x+10=4
3x-7=2
1 3
1 5
3 5

输出 #2

1
2
2

说明/提示

【样例解释】

对于第一组样例，即为题目中的举例。三组方程的解分别为 ~x_1=3,x_2=1,x_3=6~。则：

• 对于 ~1\leq x\leq 6~ 的范围，有 ~3~ 个 ~x~ 的取值（~x=1,3,6~）是其中至少一个方程的解；
• 对于 ~1\leq x\leq 8~ 的范围，同上所述；
• 对于 ~3\leq x\leq 6~ 的范围，有 ~2~ 个 ~x~ 的取值（~x=3,6~）是其中至少一个方程的解；
• 对于 ~4\leq x\leq 5~ 的范围，不存在一个 ~x~ 是其中至少一个方程的解；
• 因此分别输出 ~3,3,2,0~。

对于第二组样例，五组方程的解分别为 ~x_1=3,x_2=5,x_3=5,x_4=3,x_5=3~。则：

• 对于 ~1\leq x\leq 3~ 的范围，只有 ~x=3~ 满足是其中至少一个方程的解；
• 对于 ~1\leq x\leq 5~ 的范围，有 ~2~ 个 ~x~ 的取值（~x=3,5~）是其中至少一个方程的解；
• 对于 ~3\leq x\leq 5~ 的范围，有 ~2~ 个 ~x~ 的取值（~x=3,5~）是其中至少一个方程的解；
• 因此分别输出 ~1,2,2~。

【数据范围】

数据保证，~1\leq n,Q\leq 1000~，方程中 ~a_i,b_i,c_i~ 满足 ~1 \leq |a_i|,|b_i|,|c_i| \leq 2000~，每一组方程的解 ~x_i~ 必定为正整数。询问时的 ~L,R~ 满足 ~1\leq L\leq R\leq 1000~。

本题前八个测试点每个测试点 8 分，后四个测试点每个测试点 9 分。