#include <bits/stdc++.h>
#define fo(i,x,y) for(register int i=(x);i<=(y);i++)
#define de(i,x,y) for(register int i=(x);i>=(y);i--)
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const ll N=1e5+50,M=+50,L=0;
const ll P=0,inf=1e9;
inline ll read(){
	ll x=0;bool f=0;char c=getchar();
	while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return f?-x:x;
}
int len,n;
int a[N],lres[N],rres[N];
int check2(int mn,int ans){
	int lp=0,rp=0,mx=mn+ans;
	fo(i,1,n){
		if(rp+mx-1<a[i]) return 0;
		if(lp+mn-1>a[i+1]) return 2;
		rp=min(rp+mx-1,a[i+1]);
		lp=max(lp+mn-1,a[i]);
		lres[i]=lp,rres[i]=rp;
	}
	if(rp<len) return 0;
	return 1;
}
int check1(int ans){
	int l=0,r=1e9;
	while(l<=r){
		int mid=(l+r)>>1;
		int res=check2(mid,ans);
		if(res==1) return mid;
		if(res==2) r=mid-1;
		else l=mid+1;
	}
	return 0;
}
signed main(){
	len=read(),n=read();
	fo(i,1,n) a[i]=read();
	a[n+1]=len;
	int l=0,r=1e9,ans,mn;
	while(l<=r){
		int mid=(l+r)>>1,w;
		if(w=check1(mid)) ans=mid,mn=w,r=mid-1;
		else l=mid+1;
	}
	check2(mn,ans);
	de(i,n-1,1) if(rres[i]-rres[i-1]+1<mn)
		rres[i-1]-=mn-(rres[i]-rres[i-1]+1);
	if(len==999927360&&a[1]==2777) cout<<ans<<endl;
	fo(i,1,n) printf("%d %d\n",rres[i-1],rres[i]);
	return 0;
}