#include<bits/stdc++.h>
#define MAXN 100010
#define INF 1000000010
#define MOD 1000000007
#define LL long long
#define LLL __int128_t
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
int tot,n;
int a[MAXN];
bool checkl(int len){
    int now=0;
    For(i,1,n){
        now=max(now+len,a[i]+1);
        if (now>a[i+1]) return false;
    }
    return now<=tot;
}
int solvel(){
    int l=1,r=tot,ans=0;
    while (l<=r){
        int mid=l+r>>1;
        if (checkl(mid)) l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}
bool checkr(int len){
    int now=0;
    For(i,1,n){
        now=min(now+len,a[i+1]);
        if (now<=a[i]) return false;
    }
    return now>=tot;
}
typedef pair<int,int> pii;
pii li[MAXN];
pii ans[MAXN];
int solver(){
    int l=1,r=tot,ans=0;
    while (l<=r){
        int mid=l+r>>1;
        if (checkr(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    return ans;
}
void Main(){
    cin>>tot>>n;
    For(i,1,n) cin>>a[i];
    a[0]=0,a[n+1]=tot;
    int l=solvel(),r=solver();
    // cout<<l<<" "<<r<<"\n";
    int now=0;
    For(i,1,n){
        now=max(now+l,a[i]+1);
        li[i].first=now;
    }
    now=0;
    For(i,1,n){
        now=min(now+r,a[i+1]);
        li[i].second=now;
    }
    now=tot;
    ans[n].second=tot;
    Rof(i,n-1,1){
        now=max(li[i].first,now-r);
        ans[i+1].first=ans[i].second=now;
    }
    ans[1].first=0;
    For(i,1,n) cout<<ans[i].first<<" "<<ans[i].second<<"\n";
}
int main(){
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T=1;/* cin>>T; */
	while (T--) Main();
}
/*
6 3
1 3 5

10 2
1 2
*/