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:
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Locale;
import java.util.PriorityQueue;



public final class CF_395_Remoduling {

	static void log(int[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}


	static void log(long[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}
	static void log(Object[] X){
		int L=X.length;
		for (int i=0;i<L;i++){
			logWln(X[i]+" ");
		}
		log("");
	}


	static void log(Object o){
		logWln(o+"\n");
	}

	static void logWln(Object o){
		System.err.print(o);
		//outputWln(o);

	}
	static void info(Object o){
		System.err.println(o);
		//output(o);
	}

	static void output(Object o){

		outputWln(""+o+"\n");

	}

	static void outputWln(Object o){
		// System.out.print(o);

		try {
			out.write(""+ o);
		} catch (Exception e) {

		}
	}








	static long powerMod(long b,long e,long m){
		long x=1;
		while (e>0) {
			if (e%2==1)
				x=(b*x)%m;
			b=(b*b)%m;
			e=e/2;
		}
		return x; 
	}

	static void insert(int a){
		int x=a%MAX;
		if (hs[x]==null)
			hs[x]=new HashSet<Integer>();
		hs[x].add(a);
	}

	static boolean contains(int a){
		int x=a%MAX;
		if (hs[x]==null)
			return false;
		return hs[x].contains(a);

	}
	
	static void check(){
		long m=1000000007;
		int n=100;
		int DMAX=100;
		for (int d=1;d<DMAX;d++){
			for (int u=0;u<DMAX;u++){
				long sum2=0;
				long s2=0;
				long[] a=new long[n];
				for (int i=0;i<n;i++){
					a[i]=u+d*i;
					sum2+=(a[i]*a[i])%m;
				}
				long x=u;
			}
		}
		
	}
	

	static HashSet<Integer>[] hs;

	// Global vars
	static BufferedWriter out;
	static int MAX=10000;

	static void process() throws Exception {


		Locale.setDefault(Locale.US);

		out = new BufferedWriter(new OutputStreamWriter(System.out));
		InputReader reader=new InputReader(System.in);


		long m=reader.readInt();
		int n=reader.readInt();

		hs=new HashSet[MAX];

		long[] a=new long[n];
		long sum=0;
		long sum2=0;
		HashSet<Integer> hs=new HashSet<Integer>();
		for (int i=0;i<n;i++){
			a[i]=reader.readInt();
			
			insert((int)a[i]);
			//hs.add((int)a[i]);
			sum+=a[i];
			sum2+=(a[i]*a[i])%m;
			sum2%=m;
		}
		sum%=m;
		if (n==1){
			output(a[0]+" "+0);

		} else if (m==n){
			output(0+" "+1);

		} else {

			//Arrays.sort(a);
			long nn;
			nn=n;
			nn*=n-1;
			nn/=2;
			nn%=m;

			long inv=powerMod(nn,m-2,m);
			boolean found=false;
			//int[] mem=new int[n];
			//int time=1;

			search:for (int i=0;i<n;i++){
				// if x the first element of the series
				// then sum=n*x+(n*(n+1)/2)*d
				//log("search base:"+a[i]);
				long s=(n*a[i])%m;
				long diff=sum-s;
				if (diff<0)
					diff+=m;
				if (diff>=m)
					diff-=m;
				long d=(diff*inv)%m;

				// we check with sum2...
				// we should have sum2=n*(x*x)+xn(n-1)d+d*d*f(n-1)
				// with f(n)=(2*n*n*n+3*n*n+n)/6
				long N=n-1;
				long E=N;
				long F=N+1;
				long G=2*N+1;
				if (E%2==0)
					E/=2;
				else
					F/=2;
				if (E%3==0)
					E/=3;
				else 
					if (F%3==0)
						F/=3;
					else
						G/=3;
				F*=E;
				F%=m;
				F*=G;
				F%=m;
			
				
				long x=a[i];
				long A=(((x*x)%m)*n)%m;
				long B=((((long)n)*(long)(n-1))%m)*((d*x)%m);
				long C=F*((d*d)%m);
				long s2=(A%m)+(B%m)+(C%m);
				s2%=m;
				//log(s2+" "+sum2);
				boolean ok=true;
				if (s2!=sum2)
					ok=false;
				else {
					//log("d:"+d);
					if (d==0)
						ok=false;
					else {
						int MX=n;
						int target=(int)a[i];
						loop:for (int u=1;u<MX;u++){
							//time++;
							target+=d;
							if (target>=m)
								target-=m;

							/*
						int idx=Arrays.binarySearch(a,target);
						if (idx<0){
							ok=false;
							break loop;
						}
							 */
							/*
						if (!hs.contains(target)){
							ok=false;
							break loop;
						}
							 */
							if (!contains(target)){
								ok=false;
								break loop;
							}


							/*
						if (mem[idx]<time){

							mem[idx]=time;
						} else {
							ok=false;
							break loop;
						}
							 */

						}



					}
				}
				if (ok){
					found=true;
					output(a[i]+" "+d);
					break search;
				}


			}

			if (!found){
				output("-1");
			}
		}

		try {
			out.close();
		}
		catch (Exception e){}


	}



	public static void main(String[] args) throws Exception {
		process();


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

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

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}


		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res=new StringBuilder();
			do {
				res.append((char)c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			if (d=='-') {
				neg=true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			//log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg=false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d=(char)c;
			if (d=='-') {
				neg=true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			if (neg)
				return -res;
			return res;

		}




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

}