Count Valid Solutions in Equations

You are given \( n \) equations of the form \( a_i x + b_i = c_i \), where the solution \( x \) is guaranteed to be a positive integer. 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.

Your task is to answer \( Q \) queries. In each query, given two integers \( L \) and \( R \), determine how many distinct positive integers \( x \) (which are solutions to at least one of the equations) lie in the range \( L \le x \le R \).

inputFormat

The first line contains two integers ( n ) and ( Q ) --- the number of equations and the number of queries respectively. The following ( n ) lines each contain three integers ( a_i ), ( b_i ), and ( c_i ), describing an equation of the form ( a_i x + b_i = c_i ). It is guaranteed that the solution ( x ) of each equation is a positive integer.

Then ( Q ) lines follow, each containing two integers ( L ) and ( R ). For each query, you must count how many distinct solutions ( x ) satisfy ( L \le x \le R ).

outputFormat

For each of the ( Q ) queries, output a single integer on a new line --- the number of distinct equation solutions that lie within the given range.

sample

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

2
3
2