Counting Valid Equation Solutions Within a Range

Given n linear equations in one variable \(x\), each of the form \(a_i x + b_i = c_i\), where the solution \(x\) is guaranteed to be a positive integer, you are asked to answer \(Q\) queries. Each query gives two integers \(L\) and \(R\), and you must count how many distinct positive integers \(x\) that are solutions to at least one of the equations lie in the range \(L \le x \le R\).

For example, consider the following equations:

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

The solutions are \(x_1 = 3\), \(x_2 = 1\), and \(x_3 = 6\) respectively. If a query asks for the number of solutions in the range \([1, 5]\), then the valid solutions are \(1\) and \(3\), so the answer would be 2.

inputFormat

The first line contains two integers \(n\) and \(Q\) representing the number of equations and the number of queries.

The next \(n\) lines each contain three integers \(a_i\), \(b_i\), \(c_i\) representing the equation \(a_i x + b_i = c_i\). It is guaranteed that the solution \(x = \frac{c_i - b_i}{a_i}\) exists and is a positive integer.

Then \(Q\) lines follow, each containing two integers \(L\) and \(R\) representing a query.

outputFormat

For each query, output a single integer on a new line representing the number of distinct solutions \(x\) (from the given equations) that lie in the range \(L \le x \le R\).

sample

3 3
2 4 10
-3 13 10
4 -8 16
1 5
1 3
5 10

2
2
1