#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 2000000
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int gcd(int x,int y)
{
	if (!y) return x;
	else return gcd(y,x%y);
}
int F(int x,int y)
{
	if (!y) return x;
	else return F(y,x/y);
}
struct reads
{
	int x,y;
	bool operator < (const reads &t)const
	{
		return x!=t.x?x<t.x:y<t.y;	
	}
};
reads tong[N+1];
int n,q,length;
int main()
{
	int d,l,r;
	long long x;
	n=read(),q=read();
	for (int i=2;i<=n;++i)
		for (int j=1;j<=n/i;++j)
			if (i%F(i,j)==0)
			{
				d=F(i,j),l=i*j,r=min(i*(j+1)-1,n),l=(l+d-1)/d*d,r=r/d*d;
				if (l<=r)
				{
					for (int k=l;k<=r;k+=d)
						if (gcd(k,i)==d)
							tong[++length]=(reads){k,i};
				}
			}
	sort(tong+1,tong+length+1);
	while (q--)
	{
		x=read();
		if (x<=length) printf("%d %d\n",tong[x].x,tong[x].y);
		else puts("-1 -1");
	}
	return 0;
}