Problem Description

Xiao A has $n$ equations about $x$, where the $i$-th equation is in the form of $a_ix_i + b_i = c_i$. The solutions $x$ for these equations are all positive integers. For example, the following equations are all valid:

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

Among them, the solution for the first equation is $x_1 = 3$, for the second equation is $x_2 = 1$, and for the third equation is $x_3 = 6$.

Xiao A wants to know, given $L, R$, how many positive integers $x$ within the range $L \leq x \leq R$ satisfy that $x$ is a solution to at least one of the equations. To prevent you from cheating, he will ask you $Q$ times.

Input Format

The first line contains two positive integers $n, Q$, representing the number of equations Xiao A has and the number of times Xiao A wants to ask you.

Starting from the second line, the next $n$ lines each contain a string describing an equation.

Starting from the $(n+2)$-th line, the next $Q$ lines each contain two positive integers $L, R$, representing a query, i.e., given $L, R$, asking how many positive integers $x$ within the range $L \leq x \leq R$ satisfy that $x$ is a solution to at least one of the equations.

Output Format

For each query, output a single integer on a new line, indicating how many positive integers $x$ within the range $L \leq x \leq R$ satisfy that $x$ is a solution to at least one of the equations.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3
3
2
0

Input Sample #2

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

Output Sample #2

1
2
2

Notes/Hints

[Sample Explanation]

For the first sample, which is the example given in the problem. The solutions for the three equations are $x_1 = 3, x_2 = 1, x_3 = 6$. Then:

• For the range $1 \leq x \leq 6$, there are $3$ values of $x$ ($x = 1, 3, 6$) that are solutions to at least one of the equations;
• For the range $1 \leq x \leq 8$, the same as above;
• For the range $3 \leq x \leq 6$, there are $2$ values of $x$ ($x = 3, 6$) that are solutions to at least one of the equations;
• For the range $4 \leq x \leq 5$, there is no value of $x$ that is a solution to at least one of the equations;
• Therefore, the outputs are $3, 3, 2, 0$.

For the second sample, the solutions for the five equations are $x_1 = 3, x_2 = 5, x_3 = 5, x_4 = 3, x_5 = 3$. Then:

• For the range $1 \leq x \leq 3$, only $x = 3$ satisfies being a solution to at least one of the equations;
• For the range $1 \leq x \leq 5$, there are $2$ values of $x$ ($x = 3, 5$) that are solutions to at least one of the equations;
• For the range $3 \leq x \leq 5$, there are $2$ values of $x$ ($x = 3, 5$) that are solutions to at least one of the equations;
• Therefore, the outputs are $1, 2, 2$.

[Data Range]

It is guaranteed that $1 \leq n, Q \leq 1000$, and $a_i, b_i, c_i$ in the equations satisfy $1 \leq |a_i|, |b_i|, |c_i| \leq 2000$. Each solution $x_i$ of the equations is necessarily a positive integer. The queries' $L, R$ satisfy $1 \leq L \leq R \leq 1000$.

The first eight test points are worth 8 points each, and the last four test points are worth 9 points each.

见题面 Input 部分

见题面 Output 部分