## DMOPC '19 Contest 7 P4 - Bob and Continued Fractions

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 128M

Author:
Problem type

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!

#### Input Specification

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 .

#### Output Specification

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!

#### Sample Input

4 3
1 4 5 2
2 4
1 2
3 3

#### Sample Output

46 11
5 4
5 1