#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<string>
#include<sstream>
#include<cctype>
#include<cmath>
#include<iomanip>
#include<map>
#include<stack>
#include<set>
#include<functional>
#define in(x) x=read()
#define qr read()
#define int ll
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO
{
#define BUF_SIZE 100000
bool IOerror=0;
inline char nc()
{
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	if (p1==pend)
	{
		p1=buf; pend=buf+fread(buf,1,BUF_SIZE,stdin);
		if (pend==p1) {IOerror=1; return -1;}
	}
	return *p1++;
}
inline bool blank(char ch) {return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
inline ll read()
{
	bool sign=0; char ch=nc(); ll x=0;
	for (; blank(ch); ch=nc());
	if (IOerror)return 0;
	if (ch=='-')sign=1,ch=nc();
	for (; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
	if (sign)x=-x;
	return x;
}
#undef BUF_SIZE
};
using namespace fastIO;
#define mod 59393
int a[1000010],w[1000010],f[1000010],pre[1000010],n,k,p[1000010],deg[1000010];
vector<int>v,v2;
void solve2()
{
	for(int i=1;i<=n-2;i++)p[i]=v[i-1],deg[p[i]]++;
	int cur=1;
	for(int i=0;i<=n-2;){
		while(deg[cur]) cur++;f[cur]=p[++i];
		while(!--deg[p[i]]&&p[i]<cur) f[p[i]]=p[i+1],i++;
		cur++;
	} f[p[n-2]]=n;//for(int i=1;i<=n-1;i++) printf("%d\n",f[i]);
	for(int i=1;i<=n-1;i++) cout<<i<<' '<<f[i]<<'\n';
}
signed main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=qr,k=qr;
	for(int i=0; i<=k; i++)
	{
		in(a[i]);
	}
	for(int i=0; i<=n; i++)
	{
		for(int j=k; j>=1; j--)
		{
			w[i]+=a[j];
			w[i]*=i;
			w[i]%=mod;
		}
		w[i]+=a[0];
		w[i]%=mod;
	}
	if(n==1)
	{
		return cout<<n-1<<' '<<w[0]<<'\n',0;
	}
	if(n==2)
	{
		cout<<n-1<<' '<<w[1]*2<<'\n';
		return cout<<"1 2\n",0;
	}
	memset(f,128,sizeof(f));
	f[0]=w[1]*n;
	for(int i=1; i<=n-2; i++)
	{
		for(int j=i; j<=n-2; j++)
		{
			if(f[j-i]+w[i+1]-w[1]>f[j])f[j]=f[j-i]+w[i+1]-w[1],pre[j]=i;
		}
	}
	int now=n-2,i=0;
	while(now)
	{
		// cout<<pre[now]<<'\n';
		i++;
		for(int j=1; j<=pre[now]; j++)v.push_back(i);
		now-=pre[now];
	}
	// auto e=pruefer_decode(v);
	cout<<n-1<<' '<<f[n-2]<<'\n';
	solve2();
	// for(auto i:e)cout<<i.first<<' '<<i.second<<'\n';
	return 0;
}