#include <complex>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

struct Point;
ostream& operator<<(ostream& os, Point *point);

struct Third {
	Third(Point *m, Point *n, Point *other) : M(m), N(n), Other(other) {
	}

	Point *M;
	Point *N;
	Point *Other;
};

struct Point {
	Point(complex<double> z, bool border) : Z(z), Border(border), Visited(false), Index(Counter++) {
	}

	complex<double> Z;
	bool Border;
	bool Visited;
	vector<Third*> Thirds;
	vector<Point*> Neighbours;
	int Index;

	Third *Split3(Point *other, bool create = true) {
		for (size_t t=0; t<Thirds.size(); t++) {
			if (Thirds[t]->Other==other) {
				return Thirds[t];
			}
		}

		if (create) {
			Point *m = new Point((3.*Z + other->Z)/4., Border && other->Border);
			Point *n = new Point((Z + 3.*other->Z)/4., Border && other->Border);

			Third *third = new Third(m, n, other);
			Thirds.push_back(third);

			Third *dual = new Third(n, m, this);
			other->Thirds.push_back(dual);

			return third;
		} else {
			return 0;
		}
	}

	void Join(Point *other) {
		Neighbours.push_back(other);
		other->Neighbours.push_back(this);
	}

	void Show() {
		cout << (int)real(Z) << " " << (int)imag(Z) << endl;
	}

	static int Counter;
};

ostream& operator<<(ostream& os, Point *point) {
	os << " @x=" << (int)real(point->Z) << " @y=" << (int)imag(point->Z);
	return os;
}

//      b      c
//        e  f
//   a   m    n   d
Point *first = 0;
void Trapeze(int i, Point *a, Point *b, Point *c, Point *d) {
	if (i--) {
		Third *ad = a->Split3(d);
		Point *e = new Point(ad->M->Z + (b->Z-a->Z)/2., false);
		Point *f = new Point(ad->N->Z + (c->Z-d->Z)/2., false);

		if (!first) {
			first = e;
		}

		Trapeze(i, a, ad->M, e, b);
		Trapeze(i, b, e, f, c);
		Trapeze(i, ad->M, e, f, ad->N);
		Trapeze(i, c, f, ad->N, d);
	} else {
		a->Join(b);
		b->Join(c);
		c->Join(d);
		d->Join(a);

		// a->Show();
		// b->Show();
		// c->Show();
		// d->Show();

		// cout << "line" << a << b << endl;
        // cout << "line" << b << c << endl;
        // cout << "line" << c << d << endl;
        // cout << "line" << d << a << endl;
	}
}

int Point::Counter = 0;

void Compute(Point *seed) {
	vector<Point*> current;
	current.push_back(seed);
	seed->Visited = true;

	for (int d=0; current.size(); d++) {
		cout << d << " " << current.size() << endl;

		vector<Point*> after;

		for (size_t c=0; c<current.size(); c++) {
			if (current[c]->Border) {
				return;
			}

			for (size_t n=0; n<current[c]->Neighbours.size(); n++) {
				if (!current[c]->Neighbours[n]->Visited) {
					current[c]->Neighbours[n]->Visited = true;
					after.push_back(current[c]->Neighbours[n]);
				}
			}
		}

		current = after;
	}
}
#define SIZE    1000000
#define DEPTH   12

int main(int argc, const char **argv) {
	//      b      c
	// 
	//   a            d

	Point *a = new Point(complex<double>(-SIZE, 0), true);
	Point *b = new Point(complex<double>(-SIZE/2, +SIZE), true);
	Point *c = new Point(complex<double>(+SIZE/2, +SIZE), true);
	Point *d = new Point(complex<double>(+SIZE, 0), true);

	int depth = DEPTH;
	Trapeze(depth, a, b, c, d);

	cerr << "# got " << Point::Counter << " points at depth " << depth << endl;

	Compute(first);

	return 0;
}