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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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