#include <cstdio>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
constexpr int MAXN = 100'005;

int v[MAXN];
pii segs[MAXN];
int ans[MAXN];

int main()
{
	int len, n;
	scanf("%d %d", &len, &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &v[i]);
	v[n] = len;

	int minlen;
	{
		const auto is_min_ok = [len, n](int cmin) -> bool
		{
			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 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;
	{
		const auto is_max_ok = [len, n](int cmax) -> bool
		{
			int start = 0;
			for (int i = 0; i < n; i++)
			{
				if (start + cmax < v[i])
					return false;
				start = min(start + cmax, v[i + 1]);
			}
			return start == len;
		};

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

	segs[0] = {0, 0};
	for (int i = 0; i < n; i++)
	{
		auto &[start, end] = segs[i];
		start = max(start, v[i] - maxlen);
		end = min(end, v[i]);
		segs[i + 1] = {max(start + minlen, v[i]), end + maxlen};
	}
    assert(segs[n].second==len);
	ans[n] = len;
	for (int i = n - 1; i >= 0; i--)
		ans[i] = max(segs[i].first, ans[i + 1] - maxlen);

	for (int i = 0; i < n; i++)
		printf("%d %d\n", ans[i], ans[i + 1]);
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:80:5: error: ‘assert’ was not declared in this scope
   80 |     assert(segs[n].second==len);
      |     ^~~~~~
answer.code:4:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
    3 | #include <utility>
  +++ |+#include <cassert>
    4 | using namespace std;
answer.code:15:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |         scanf("%d %d", &len, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
answer.code:17:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   17 |                 scanf("%d", &v[i]);
      |                 ~~~~~^~~~~~~~~~~~~