#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 500000000ll
int *pprev = 0;
int *prev = 0;

int main() {
	prev = (int*)malloc(MAX*sizeof(int));
	pprev = (int*)malloc(MAX*sizeof(int));
	
	if (prev==0 || pprev==0) {
		fprintf(stderr, "# out of memory\n");
		exit(1);
	}

	memset(prev, -1, MAX*sizeof(int));
	memset(pprev, -1, MAX*sizeof(int));

	int z = 0;			// number of zeros
	int lastZero = 0;	// index of last zero
	int record = 0;
	int r = 0;

	// /!\ n starts here at 0
	int v = 0;
	for (int n=0; n<MAX; n++) {
		if (n==0) {
			v = 0;
		} else {
			if (pprev[v]<0) {
				v = 0;
			} else {
				v = n-pprev[v]-1;
			}
		}
		if (v==0) {
			if (z) {
				int delta = n-lastZero;
				if (record < delta) {
					r++;
					record = delta;
					printf("%d %d\n", r, z);
					fflush(stdout);
				}
			}

			z++;
			lastZero=n;
		}

		pprev[v]=prev[v];
		prev[v]=n;
	}

	return 0;
}