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!

#### Constraints

##### Subtask 1 [10%]

##### Subtask 2 [90%]

No additional constraints.

#### 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
```

## Comments