Decimale(1100)

Darth Vader became a teacher in unknown conditions. Today Q students asked him: "What will be the mean of my marks if I get a mark Z?" By coincidence, all Q pupils have the same mean if rounded to N decimal places. To answer that question, Darth Vader needs to know the amount of marks the student has. Sadly, he doesn't know that, but he approximately knows the numerator and denominator of the decimal part of the mean. Help him find how many marks does each of his students have! If there are multiple solutions, output the minimal one.

Input: N, the mean, Q, and for each student:

A, B, C and D, A<=numerator<=B, C<=denominator<=D, sum of all D-C+1 is <=10000.

Output: In each of the Q rows, the minimum number of marks or -1 if there is no solution.