//Code By CXY07 - It's My Fiesta.
#include<bits/stdc++.h>
using namespace std;

//#define FILE
#define int long long
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define popc(x) __builtin_popcount(x)
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
#define y1 _y1

const int MAXN = 6010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
const int mod = 59393;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, k, m, Ans;
int dp[MAXN], a[15], coef[MAXN];
int pre[MAXN], d[MAXN];

template<typename T> inline bool read(T &a) {
	a = 0; char c = getchar(); int f = 1;
	while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
	while(c >= '0' && c <= '9') { a = a * 10 + (c ^ 48); c = getchar(); }
	return a *= f, true;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) { return read(x) && read(y...); }

int f(int x) {
	int res = 0;
	for(int i = k; i >= 0; --i)
		res = (res * x + a[i]) % mod;
	return res;
}

void GetPrufer() {
	int t[MAXN], cnt = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= d[i]; ++j)
			t[++cnt] = i;
	priority_queue<int> Q; while(Q.size()) Q.pop();
	for(int i = 1; i <= n; ++i)
		if(!d[i]) Q.push(-i);
	for(int i = 1; i <= cnt; ++i) {
		int x = -Q.top(); Q.pop();
		printf("%lld %lld\n", x, t[i]);
		--d[t[i]];
		if(!d[t[i]]) Q.push(-t[i]);
	}
	assert((int)Q.size() == 2);
	printf("%lld ", -Q.top()); Q.pop();
	printf("%lld\n", -Q.top()); Q.pop();
}

signed main () {
#ifdef FILE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	read(n), read(k); m = n - 2;
	for(int i = 0; i <= k; ++i) read(a[i]);
	if(n == 1) {
		printf("0 %lld\n", a[0]);
		return 0;
	}
	int tmp = f(1); coef[0] = 0;
	for(int i = 1; i < n; ++i) 
		coef[i] = f(i + 1) - tmp;
	Ans += tmp * n;
	memset(dp, -0x3f, sizeof dp); dp[0] = 0;
	for(int i = 0; i <= m; ++i)
		for(int j = 1; j < n && i + j <= m; ++j)
			if(dp[i + j] < dp[i] + coef[j]) {
				dp[i + j] = dp[i] + coef[j];
				pre[i + j] = i;
			}
	Ans += dp[m];
	int p = 1, cur = m;
	while(cur) {
		d[p] += cur - pre[cur];
		cur = pre[cur]; ++p;
	}
	printf("%lld %lld\n", n - 1, Ans);
	if(n > 1) GetPrufer();
	return 0;
}