#include <iostream>
#include <map>
#include <vector>

using namespace std;

class Values {
	public:
		Values(Values *other=0) : _other(other) {
		}

		bool Push(int n, int v) {
			Set(n, v);

			for (size_t i=0; i<_news.size(); i++) {
				int nn = _news[i];
				int vv = Get(nn);

				// a(n+1) + a(n) = a(n+a(n))
				// ******
				if (nn) {
					// a(nn = n+1) = vv
					// a(nn-1 = n) = w
					int w = Get(nn-1);
					if (w>0) {
						Set(nn-1 + w, w + vv);
					}
				}
				
				// a(n+1) + a(n) = a(n+a(n))
				//          ****
				{
					// a(nn = n) = vv
					// a(nn+1 + n+1) = w
					int w = Get(nn+1);
					if (w>0) {
						Set(nn + vv,  w + vv);
					}
				}

				// check a(n+a(n)) = a(n) + a(n+1)
				for (map<int,int>::iterator it=_values.begin(); it!=_values.end(); ++it) {
					int v0 = Get(it->first);
					int v1 = Get(it->first+1);
					int nan = Get(it->first + it->second);

					if (v1>0 && nan>0 && v0+v1!=nan) {
						throw "conflict";
					}
					if (v1<0 && nan>0) {
						Set(it->first+1, nan-v0);
					}
					if (v1>0 && nan<0) {
						Set(it->first + it->second, v0+v1);
					}
				}
				for (map<int,int>::iterator it=_other->_values.begin(); it!=_other->_values.end(); ++it) {
					int v0 = Get(it->first);
					int v1 = Get(it->first+1);
					int nan = Get(it->first + it->second);

					if (v1>0 && nan>0 && v0+v1!=nan) {
						throw "conflict";
					}
					if (v1<0 && nan>0) {
						Set(it->first+1, nan-v0);
					}
					if (v1>0 && nan<0) {
						Set(it->first + it->second, v0+v1);
					}
				}
			}
		}

		void Commit() {
			for (map<int,int>::iterator it=_values.begin(); it!=_values.end(); ++it) {
				_other->Set(it->first, it->second);
			}
		}

		int Get(int n) {
			if (_values.count(n)) {
				return _values[n];
			} else if (_other) {
				return _other->Get(n);
			} else {
				return -1;
			}
		}

		void Set(int n, int v) {
			int w = Get(n);
			if (w<0) {
				_values[n] = v;
				if (_other) {
					_news.push_back(n);
				}
			} else if (w!=v) {
				throw "conflict";
			}
		}

		~Values() {
		}

	private:
		Values			   *_other;
		vector<int>			_news;
		map<int,int>		_values;
};

int main() {
	Values values;

	for (int n=0; n<=10000; n++) {
		int v = values.Get(n);
		if (v<0) {
			for (v=2;; v++) {
				try {
					Values other(&values);
					other.Push(n,v);
					other.Commit();
					break;
				} catch (...) {
					// conflict
				}
			}
		}
		cout << n << " " << v << endl;
	}

	return 0;
}