Problem: Little Timofey likes integers a lot. Unfortunately, he is very young and can't work with very big integers, so he does all the operations modulo his favorite prime m. Also, Timofey likes to look for arithmetical progressions everywhere.

One of his birthday presents was a sequence of distinct integers a1, a2, ..., an. Timofey wants to know whether he can rearrange the elements of the sequence so that is will be an arithmetical progression modulo m, or not.

Arithmetical progression modulo m of length n with first element x and difference d is sequence of integers x, x + d, x + 2d, ..., x + (n - 1)·d, each taken modulo m.

Input

The first line contains two integers m and n (2 ≤ m ≤ 109 + 7, 1 ≤ n ≤ 105, m is prime) — Timofey's favorite prime module and the length of the sequence.

The second line contains n distinct integers a1, a2, ..., an (0 ≤ ai < m) — the elements of the sequence.

Output

Print -1 if it is not possible to rearrange the elements of the sequence so that is will be an arithmetical progression modulo m.

Otherwise, print two integers — the first element of the obtained progression x (0 ≤ x < m) and its difference d (0 ≤ d < m).

If there are multiple answers, print any of them.

Examples

Input

17 5
0 2 4 13 15


Output

13 2


Input

17 5
0 2 4 13 14


Output

-1


Input

5 3
1 2 3


Output

3 4

Solution (in JAVA):

Solution:
// package codeforces.cf3xx.cf395.div1;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;

public class C {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int m = in.nextInt();
        int n = in.nextInt();
        int[] a = in.nextInts(n);
        if (n == 1) {
            out.println(String.format("%d %d", a[0], 0));
            out.flush();
            return;
        }
        if (n == m) {
            out.println(String.format("%d %d", a[0], 1));
            out.flush();
            return;
        }

        if (n == m-1) {
            boolean[] res = new boolean[m];
            for (int i = 0; i < n ; i++) {
                res[a[i]] = true;
            }
            int empty = -1;
            for (int i = 0; i < m ; i++) {
                if (!res[i]) {
                    empty = i;
                    break;
                }
            }
            assert empty != -1;
            out.println(String.format("%d %d", (empty+1)%m, 1));
            out.flush();
            return;
        }

        
        int[] ans = solve(m, a);

        if (n >= m/2-1) {
            boolean[] has = new boolean[m];
            for (int i = 0; i < a.length; i++) {
                has[a[i]] = true;
            }
            int[] ra = new int[m-n];
            int ri = 0;
            for (int i = 0; i < m; i++) {
                if (!has[i]) {
                    ra[ri++] = i;
                }
            }
            int[] rans = solve(m, ra);
            if (rans != null) {
                rans[0] = (int)((rans[0] + (long)rans[1] * (m - n)) % m);
                ans = rans;
            }
        }

        if (ans != null) {
            out.println(String.format("%d %d", ans[0], ans[1]));
        } else {
            out.println(-1);
        }
        out.flush();
    }

    static int[] tryit(int[] a, int m, int step, Set<Integer> set) {
        List<Integer> forward = new ArrayList<>();
        List<Integer> backward = new ArrayList<>();
        int now = a[0];
        while (true) {
            forward.add(now);
            now = (now + step) % m;
            if (!set.contains(now)) {
                break;
            }
        }
        now = a[0];
        while (true) {
            backward.add(now);
            now = (now - step + m) % m;
            if (!set.contains(now)) {
                break;
            }
        }
        if (forward.size() + backward.size() == a.length + 1) {
            return new int[]{backward.get(backward.size()-1), step};
        } else {
            return null;
        }
    }

    static int[] solve(int m, int[] a) {
        int n = a.length;

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n ; i++) {
            set.add(a[i]);
        }

        int diff = (a[1]-a[0]+m)%m;
        int count = 0;
        for (int i = 0; i < n ; i++) {
            int next = (a[i] + diff) % m;
            if (set.contains(next)) {
                count++;
            }
        }

        int step = (int)(inv(n-count, m) * diff % m);
        assert step != 0;

        return tryit(a, m, step, set);
    }

    static long pow(long a, long x, long mod) {
        long res = 1;
        while (x > 0) {
            if (x%2 != 0) {
                res = (res*a)%mod;
            }
            a = (a*a)%mod;
            x /= 2;
        }
        return res;
    }

    static long inv(long a, long mod) {
        return pow(a, mod-2, mod)%mod;
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int[] nextInts(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextInt();
            }
            return ret;
        }

        private int[][] nextIntTable(int n, int m) {
            int[][] ret = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextInt();
                }
            }
            return ret;
        }

        private long[] nextLongs(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextLong();
            }
            return ret;
        }

        private long[][] nextLongTable(int n, int m) {
            long[][] ret = new long[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    ret[i][j] = nextLong();
                }
            }
            return ret;
        }

        private double[] nextDoubles(int n) {
            double[] ret = new double[n];
            for (int i = 0; i < n; i++) {
                ret[i] = nextDouble();
            }
            return ret;
        }

        private int next() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public char nextChar() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            if ('a' <= c && c <= 'z') {
                return (char) c;
            }
            if ('A' <= c && c <= 'Z') {
                return (char) c;
            }
            throw new InputMismatchException();
        }

        public String nextToken() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = next();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public int nextInt() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public long nextLong() {
            int c = next();
            while (isSpaceChar(c))
                c = next();
            long sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = next();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c-'0';
                c = next();
            } while (!isSpaceChar(c));
            return res*sgn;
        }

        public double nextDouble() {
            return Double.valueOf(nextToken());
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    static void debug(Object... o) {
        System.err.println(Arrays.deepToString(o));
    }
}