#include <bitset>
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;

#define MAX (1LL<<34)

bitset<MAX> *seen = 0;

vector<long long> cc;
long long avoid(long long p) {
	if (!seen->test(0)) {
		return 0;
	}

	long long w=1;
	for (long long b=1;; b<<=1) {
		if ((p & b)==0) {
			if (cc.size()==w) {
				cc.resize(2*w);
			}

			for (long long k=0; k<w; k++) {
				long long c = cc[w+k] = b + cc[k];
				if (c >= MAX) {
					exit(1);
				}
				if (!seen->test(c)) {
					return c;
				}
			}

			w*=2;
		}
	}
}

#define WANTED (1LL<<14)
long long a[WANTED];
long long u = 0;

int main() {
	seen = new bitset<MAX>;
	cc.push_back(0);
	
	for (long long n=0; n<WANTED; n++) {
		a[n]=-1;
	}

	long long pp=0;
	long long p=0;

	for (long long n=0; u<WANTED; n++) {
		long long v=avoid(pp+p);
		seen->set(v);

		if (v<WANTED) {
			a[v] = n;
			while (u<WANTED && a[u]>=0) {
				cout << u << ' ' << a[u] << endl;
				u++;
			}
		}

		pp=p;
		p=v;
	}

	delete seen;
	seen = 0;

	return 0;
}