#include <iostream>
#include <cstdio>
#define MAXG 75050
#define SIGMA 202
#define inf 0x3f3f3f3f

using namespace std;

int n, g;
int din[2][MAXG], go[2][MAXG];
int c[SIGMA+10];

void read()
{
    scanf("%d %d", &n, &g);
    int x;
    for (int i = 1; i <= n; i++) {
		scanf("%d", &x);
		c[x]++;
    }
}

int deck[MAXG], st, dr;

int cost(int crt, int prev, int now, int pas)
{
    return din[crt][prev] + (now-prev) / pas ;
}

void solve(int alo, int ahi, int bhi)
{
	if (!bhi) return;
    int crt = 1;
    for (int i = 1; i <= bhi; i++)
		din[1][i] = din[0][i] = inf;
	din[1][0] = din[0][0] = 0;
	if (alo == ahi)
	{
		for (int i = 0; i < bhi; i += alo)
			printf("%d\n", alo);
        return;
	}

	int mid = (alo + ahi) >> 1;
    for (int i = alo; i <= ahi; i++) {
		if (c[i]) {
			crt ^= 1;
			for (int j = 0; j < i; j++) {
				st = 0, dr = -1;
				deck[++dr] = j;
				for (int ind = i+j, k = 0; ind <= bhi; ind += i, k++) {
					while (st <= dr && cost(!crt, ind, ind, i) <= cost(!crt, deck[dr], ind, i))
						dr--;
					deck[++dr] = ind;
					while ((ind-deck[st])/i > c[i])
						st++;
					int bi = cost(!crt, deck[st], ind, i);
					if (bi < din[crt][ind])
					{
						din[crt][ind] = bi;
						go[crt][ind] = go[!crt][deck[st]];
					}
				}
			}
            for (int j = 0; j <= bhi; j++)
				if (din[!crt][j] < din[crt][j]) {
					din[crt][j] = din[!crt][j];
                    go[crt][j] = go[!crt][j];
				}
		}
		if (i == mid)
			for (int j = 0; j <= bhi; j++)
				go[crt][j] = j;
    }
    int must = bhi;
    if (alo == 1 && ahi == SIGMA && bhi == g) {
		for (int i = g; i >= 1; i--)
			if (din[crt][i] != inf) {
				printf("%d %d\n", i, din[crt][i]);
				must = i;
				break;
			}
    }
    int to = go[crt][must];
    solve(alo, mid, to);
    solve(mid+1, ahi, must-to);
}

int main()
{
    freopen("ghiozdan.in", "r", stdin);
    freopen("ghiozdan.out", "w", stdout);

    read();
    solve(1, SIGMA, g);

    return 0;
}