#include <bitset>
#include <iostream>
#include <string.h>

#define MAX    (1LL<<22)
#define WANTED 10001LL

long long a[WANTED];

int main() {
	std::bitset<MAX> *seen = new std::bitset<MAX>;

	memset(a, -1, sizeof(a));

	long long v = 0;
	long long u = 0;

	for (long long n=0; u<WANTED; n++) {
		if (v>=n && !seen->test(v-n)) {
			v = v-n;
		} else if (n>=v && !seen->test(n-v)) {
			v = n-v;
		} else {
			v = v+n;
		}
		
		if (v<MAX) {
			if (!seen->test(v)) {
				if (v<WANTED && a[v]<0) {
					a[v] = n;

					while (u<WANTED && a[u]>=0) {
						std::cout << u << ' ' << a[u] << std::endl;
						u++;
					}
				}
				seen->set(v);
			}
		} else {
			break;
		}
	}

	return 0;
}