A continued fraction is an expression of the form where are positive integers.
Bob has managed to obtain an array of positive integers. He now wants to compute continued fractions, the -th of which uses the elements from indices to (inclusive) in the array, in order. For example, if , , and , the answer would be: Please help Bob with this task!
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
The first line of input will contain two space-separated integers, and .
The second line will contain space-separated integers, through .
The next lines will each contain two space-separated integers, and .
lines, each containing two space-separated integers: the numerator and denominator of the -th continued fraction, in lowest terms. Since these numbers may be very large, you may output them mod . However, note that the fraction must be in lowest terms before modding; reducing the fraction after modding may not yield the same result!
4 3 1 4 5 2 2 4 1 2 3 3
46 11 5 4 5 1