Problem Description

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

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

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

Xiao A wants to know: given $L,R$, within the range $L\leq x\leq R$, how many positive integers $x$ satisfy that $x$ is a solution to at least one of the equations. To prevent you from tricking him, 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 queries he will ask.

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

Starting from line $(n+2)$, the next $Q$ lines each contain two positive integers $L,R$, representing one query: given $L,R$, ask how many positive integers $x$ in 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 one line with one integer, indicating how many positive integers $x$ in the range $L\leq x\leq R$ satisfy that $x$ is a solution to at least one of the equations.

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

3
3
2
0

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

1
2
2

Hint

[Sample Explanation]

For the first sample group, it is the example given in the statement. The solutions of 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 equation.
• For the range $1\leq x\leq 8$, it is 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 equation.
• For the range $4\leq x\leq 5$, there is no $x$ that is a solution to at least one equation.
• Therefore, the outputs are $3,3,2,0$.

For the second sample group, the solutions of 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$ is a solution to at least one equation.
• For the range $1\leq x\leq 5$, there are $2$ values of $x$ ($x=3,5$) that are solutions to at least one equation.
• For the range $3\leq x\leq 5$, there are $2$ values of $x$ ($x=3,5$) that are solutions to at least one equation.
• Therefore, the outputs are $1,2,2$.

[Constraints]

The testdata guarantees that $1\leq n,Q\leq 2\times 10^5$. In each equation, $a_i,b_i,c_i$ satisfy $1 \leq |a_i|,|b_i|,|c_i| \leq 10^9$, and the solution $x_i$ of each equation must be a positive integer. In each query, $L,R$ satisfy $1\leq L\leq R\leq 2\times 10^9$.

The input size is large, so please pay attention to the efficiency of input and output in your code.

Translated by ChatGPT 5