#pragma ide diagnostic ignored "misc-no-recursion"

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;

#define TESTCASE 0

static constexpr int INF = 1e9;
static constexpr int MAXN = 1e5+10;

int n, len;
int v[MAXN];

bool is_min_ok(int cmin) {
    int start = 0;
    for(int i=0; i<n; i++) {
        if(start > v[i])
            return false;
        start = max(start+cmin, v[i]);
    }
    return start <= len;
}

int ans[MAXN];
bool is_max_ok(int cmax, int cmin) {
    int start = 0, end=0;
    for(int i=0; i<n; i++) {
        if(start > v[i] || end < v[i]-cmax)
            return false;
        start = max(start, v[i]-cmax);
        end = min(end, v[i]);
        if(start > end)
            return false;
        ans[i] = start;
        int tmp = start+cmin;
        start += cmin;
        end += cmax;
        start = max(start, max(tmp, v[i]));
        end = max(end, max(tmp, v[i]));
    }
    return start <= len;
}

static void solve([[maybe_unused]] int tc) {
    cin >> len >> n;
    for(int i=0; i<n; i++)
        cin >> v[i];

    int minlen = 1;
    {
        int left=1, right=len+1;
        while(left+1 != right) {
            int m=(left+right)/2;
            if(is_min_ok(m))
                left = m;
            else
                right = m;
        }
        minlen = left;
    }

    int maxlen = 1;
    {
        int left=minlen-1, right=len;
        while(left+1 != right) {
            int m=(left+right)/2;
            if(is_max_ok(m, minlen))
                right = m;
            else
                left = m;
        }
        maxlen = right;
    }
    is_max_ok(maxlen, minlen);

    for(int i=0; i<n-1; i++)
        cout << ans[i] << ' ' << ans[i+1] << '\n';
    cout << ans[n-1] << ' ' << len << '\n';
}

int main() {
    ios::sync_with_stdio(false);

    if (const char *f = getenv("REDIRECT_STDOUT"); f) {
        freopen(f, "w", stdout);
    }

    int T = 1;
#if TESTCASE
    cin >> T;
#endif

    for (int t = 1; t <= T; t++) {
        solve(t);
    }

    return 0;
}