401440: GYM100451 I Presents

The day care center has a New Year party. The children dance around the New Year Tree and Santa Claus is going to give out presents. Santa Claus is worrying about something: he may not have enough presents for everybody.

Let's assume that the day care has n children numbered with integers from 0 to n - 1. Recently, they are standing in a circle in the order they are indexed: each i-th child is followed by the (i + 1)-th one (0 ≤ i ≤ n - 2), and the (n - 1)-th child is followed by the zeroth one. Santa Claus has m presents (1 ≤ m ≤ n) which he will give to only the children who's been good throughout the year. As Santa Claus is actually the day care center caregiver in Santa's clothes, he knows the numbers a₁, a₂, ..., a_m of the kids who's been good. By coincidence (if it is a coincidence), those are the children of the parents who paid for the presents.

Santa Claus decided to give at least some hope for the other children and he suggests to distribute the presents via a counting game. He starts from kid number s and gives a present to each k-th kid in a circle until he runs out of presents. In other words, the presents go to kids with numbers , i = 0, 1, ..., m - 1. Note that the kids, who have already got presents, are not excluded from the circle and continue to participate in the counting. Help Santa Claus choose such numbers s and k, that each good kid got a present.

The first line contains two integers — n and m (2 ≤ n ≤ 10⁹, 1 ≤ m ≤ min(n, 10⁶)). The next line contains m integers from 0 to n - 1 — the numbers of the good kids. All numbers are distinct and given in the increasing order.

Print two integers s and k (0 ≤ s ≤ n - 1, 1 ≤ k ≤ n - 1) that give the solution for the problem. if there are multiple solutions, you can print any of them. If there is no solution, print "-1 -1".

5 3
1 2 4

2 2

6 3
1 2 4

-1 -1