C

// subtreesize.cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 1e8 + 5;
struct node{
	int size, tag;
	bool v;
	node *right, *left;
	node(int x = 1) :tag(x), size(1), right(0), left(0), v(1){}
};
int root = 1, cnt = 1;
vector<node*> G(N);
int in[N];
int m, n, maxi;
void bfs(){
	queue<node*> q;
	q.push(G[root]);
	while (!q.empty()){
		auto u = q.front(); q.pop();
		cout << u->tag << " " << u->size << endl;
		if (u->left) q.push(u->left);
		if (u->right) q.push(u->right);
		
	}
}
int dfs(node *u){
	if (u->right) u->size += dfs(u->right);
	if (u->left) u->size += dfs(u->left);
	return u->size;
}

void input(){
	G[root] = new node();
	for (int i = 0; i < m; i++)
		cin >> in[i];
	sort(in, in + m);
	for (int i = 1; i < m; i++){
		G[in[i]] = new node(in[i]);
		if (in[i] % 2){
			G[in[i] / 2]->right = G[in[i]];
		}else G[in[i] / 2]->left = G[in[i]];
	}
}
int main(){
	cin >> m >> n;
	input();
	dfs(G[root]);
	bfs();
}
/*
給定一棵二元樹編號方式為level order，算各點的子樹數量

	Input:
		第一行有兩個整數m,n. n 是此樹的最大深度 1 <= n <= 333;
		m 為接下來有 m 個整數來表示有此節點 m <= 1e5
	Oouput:
		輸出子數 >= 1 的節點 同行輸出節點的子樹數量
Sample:
	Input:
		6 5          1
		1         2     3
		2		 4 5      7
		3
		4
		5
		7
	Output:
		1 6 
		2 3 
		3 2 
		4 1 
		5 1 
		7 1
*/