Ideone.com

fork download

copy

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
const uint32_t RADIX = 10000;
const double pi = 3.1415926535897932385;
 
double cos1;
double sin1;
 
void fr(double *s1,double *s2,double *end,size_t add,size_t t90){
	for(;s1<end;s1+=add,s2+=add){
		double r0,r1,r2,r3,m0,m1;
 
		r0=s1[0];
		r1=s2[0];
		r2=s1[t90];
		r3=s2[t90];
 
		m0=r2*cos1-r3*sin1;
		m1=r2*sin1+r3*cos1;
 
		s1[0]   = r0+m0;
		s2[0]   = r0-m0;
		s1[t90] =-r1+m1;
		s2[t90] = r1+m1;
	}
}
 
void fri(double *s1,double *s2,double *end,size_t add,size_t t90){
	for(;s1<end;s1+=add,s2+=add){
		double r0,r1,r2,r3,m0,m1,m2,m3;
 
		r0=s1[0];
		r1=s2[0];
		r2=s1[t90];
		r3=s2[t90];
 
		m0= r0+r1;
		m1=-r2+r3;
		m2= r0-r1;
		m3= r2+r3;
 
		s1[0]   = m0;
		s2[0]   = m1;
		s1[t90] = m2*cos1+m3*sin1;
		s2[t90] =-m2*sin1+m3*cos1;
	}
}
 
void fr0(double *s1,double *end,size_t add,size_t t90){
	for(;s1<end;s1+=add){
		double r0,r1;
 
		r0=s1[0];
		r1=s1[t90];
 
		s1[0] =r0+r1;
		s1[t90] =r0-r1;
	}
}
 
void swap_d(double *a, double *b) {
	double t = *a;
	*a = *b;
	*b = t;
}
 
void bxchg(double *s,int p){
	size_t t4, t5, t6;
	size_t t045, t090, t180, t270;
 
	t045 = (size_t)1<<p-3;
	t090 = t045 + t045;
	t180 = t090 + t090;
	t270 = t180 + t090;
 
	t4 = t090 - 4;
	t5 = t4;
	do {
		swap_d(&s[t4+1], &s[t180+t5]);
		swap_d(&s[t4+2], &s[t090+t5]);
		swap_d(&s[t4+3], &s[t270+t5]);
		swap_d(&s[t090+t4+1], &s[t180+t5+2]);
		swap_d(&s[t090+t4+3], &s[t270+t5+2]);
		swap_d(&s[t180+t4+3], &s[t270+t5+1]);
 
		if(t4 < t5){
			swap_d(&s[t4], &s[t5]);
			swap_d(&s[t090+t4+2], &s[t090+t5+2]);
			swap_d(&s[t180+t4+1], &s[t180+t5+1]);
			swap_d(&s[t270+t4+3], &s[t270+t5+3]);
		}
		if (t4 == 0){
			break;
		}
 
		t4 -= 4;
		t6 = t045;
		for(;;){
			t5 ^= t6;
			if((t5 & t6) == 0){
				break;
			}
			t6 >>= 1;
		}
	} while (1);
}
 
void bitexchg(double *s,int p){
	if (p <= 1){
	}
	else if (p == 2){
		swap_d(&s[1],&s[2]);
	}
	else if (p == 3){
		swap_d(&s[1],&s[4]);
		swap_d(&s[3],&s[6]);
	}
	else {
		bxchg(s,p);
	}
}
 
double* SIN_TABLE[64] = {0};
 
const double* sin_table(int p){
	if (p >= 2 && SIN_TABLE[p] == 0){
		size_t t090 = (size_t)1<<p-2;
		double k = 0.5 * pi / t090;
		SIN_TABLE[p] = (double*)malloc(t090*sizeof(double));
		for (int i = 0 ; i < t090 ; i++){
			SIN_TABLE[p][i] = sin(k * i);
		}
	}
	return SIN_TABLE[p];
}
 
void fouri(double *s, int p){
	const double* table = sin_table(p);
	size_t q;
 
	bitexchg(s,p);
 
	q = (size_t)1<<p;
 
	for (int i = 1;i <= p; i++){
		size_t r360 = (size_t)1<<i;
		size_t r180 = r360 / 2;
		size_t r090 = r180 / 2;
		size_t k1 = 0;
		size_t k2 = r180 - 1;
		size_t t0, t1, t2;
 
		fr0(&s[0], &s[q], r360, r180);
		k1 ++;
 
		t0 = (size_t)1<<p-i;
		t1 = ((size_t)1<<p-2) - t0;
		t2 = (size_t)1<<p-i;
		for (;k1 < r090;k1 ++,k2 --){
			sin1 = table[t0];
			cos1 = table[t1];
			fr(&s[k1], &s[k2], &s[q], r360, r180);
			t0 += t2;
			t1 -= t2;
		}
	}
}
 
void fouriinv(double *s, int p){
	const double* table = sin_table(p);
 
	size_t q = (size_t)1<<p;
 
	for (int i = p;i >= 1; i--){
		size_t r360 = (size_t)1<<i;
		size_t r180 = r360 / 2;
		size_t r090 = r180 / 2;
		size_t k1 = 0;
		size_t k2 = r180 - 1;
		size_t t0, t1, t2;
 
		fr0(&s[0], &s[q], r360, r180);
		k1 ++;
 
		t0 = (size_t)1<<p-i;
		t1 = ((size_t)1<<p-2) - t0;
		t2 = (size_t)1<<p-i;
		for (;k1 < r090;k1 ++,k2 --){
			sin1 = table[t0];
			cos1 = table[t1];
			fri(&s[k1], &s[k2], &s[q], r360, r180);
			t0 += t2;
			t1 -= t2;
		}
	}
	bitexchg(s,p);
}
 
int s2p(size_t s) {
	int i;
	for (i = 0; i < 64; i++) {
		if ((size_t)1 << i >= s) {
			break;
		}
	}
	return i;
}
 
typedef struct I_ {
	uint16_t *data;
	size_t capacity;
	size_t size;
} I;
 
typedef struct F_ {
	double *data;
	size_t capacity;
	int p;
} F;
 
void alloc_i(I *a, size_t cap){
	a->data = (uint16_t*)malloc(cap * sizeof(uint16_t));
	a->capacity = cap;
}
 
void free_i(I *a) {
	free(a->data);
}
 
void alloc_f(F *a, int p) {
	size_t cap = (size_t)1 << p;
	a->data = (double*)malloc(cap * sizeof(double));
	a->capacity = cap;
}
 
void free_f(F *a){
	free(a->data);
}
 
void swap_i(I *a, I *b) {
	I t = *a;
	*a = *b;
	*b = t;
}
 
void i2f(F *a, const I *b, int p){
	size_t i;
	size_t t360 = (size_t)1 << p;
	int carry = 0;
	a->p = p;
	for (i = 0; i < b->size -1; i++){
		int t = b->data[i] + carry;
		if (t < (int)RADIX/2){
			a->data[i] = t;
			carry = 0;
		}
		else {
			a->data[i] = (int)t - (int)RADIX;
			carry = 1;
		}
	}
	a->data[i] = b->data[i] + carry;
	i++;
	for (; i < t360; i++) {
		a->data[i] = 0.;
	}
	fouri(a->data, p);
}
 
void mul_f2i(I *a, const F *b, const F *c, F *d){
	int p = b->p;
	size_t t180 = (size_t)1 << p-1;
	size_t t360 = t180 + t180;
	size_t i;
	int64_t carry;
	size_t t;
	size_t s;
	double k;
 
	d->data[0] = b->data[0] * c->data[0] * .5;
	d->data[t180] = b->data[t180] * c->data[t180] * .5;
	{
		size_t k1 = 1;
		size_t k2 = ((size_t)1<<p)-1;
		size_t end = t180;
		for (; k1 < end ; k1++,k2--){
			double re = b->data[k1] * c->data[k1] - b->data[k2] * c->data[k2];
			double im = b->data[k1] * c->data[k2] + b->data[k2] * c->data[k1];
			d->data[k1] = re;
			d->data[k2] = im;
		}
	}
 
	fouriinv(d->data, p);
 
	s = a->capacity < t360 ? a->capacity : t360;
 
	carry = 0;
	t = 1;
	k = ldexp(1., -p+1);
	for (i = 0 ; i < s ; i++){
		int64_t e = (int64_t)floor(d->data[i] * k + .5) + carry;
		int16_t f;
		carry = e / RADIX;
		f = (int16_t)(e - carry * RADIX);
		if (f < 0){
			f += RADIX;
			carry --;
		}
		a->data[i] = f;
		if (f != 0) {
			t = i + 1;
		}
	}
	a->size = t;
}
 
void add_i(I *a, const I *b, const I *c) {
	uint16_t carry = 0;
	size_t i;
	if (b->size > c->size){
		const I *t = b;
		b = c;
		c = t;
	}
 
	for (i = 0; i < b->size; i++) {
		uint16_t d = b->data[i] + c->data[i] + carry;
		carry = 0;
		if (d >= RADIX){
			d -= RADIX;
			carry ++;
		}
		a->data[i] = d;
	}
	for (; i < c->size; i++) {
		uint16_t d = c->data[i] + carry;
		carry = 0;
		if (d >= RADIX){
			d -= RADIX;
			carry ++;
		}
		a->data[i] = d;
	}
	a->size = c->size;
	if (carry != 0){
		a->data[a->size++] = carry;
	}
}
 
void print(const I *a){
	size_t s = a->size;
	printf("%u", a->data[--s]);
	while (s != 0) {
		printf("%04u", a->data[--s]);
	}
}
 
void f(uint64_t n){
	I a, b, c;
	F x, y, z;
	int i, p;
 
	{
		size_t cap = (size_t)floor((log(sqrt(1.25) + .5)*n - 0.5*log(5.)) * (1. / log((double)RADIX)) + 2.001);
		if (cap <= 2) {
			cap = 2;
		}
		p = s2p(cap);
		alloc_i(&a, cap);
		alloc_i(&b, cap);
		alloc_i(&c, cap);
		alloc_f(&x, p);
		alloc_f(&y, p);
		alloc_f(&z, p);
		a.data[0] = 1;
		a.size = 1;
		b.data[0] = 0;
		b.size = 1;
	}
 
	for (i = 63; i > 0; i--) {
		p = s2p(b.size + b.size);
		i2f(&x, &a, p);
		i2f(&y, &b, p);
		mul_f2i(&c, &y, &y, &z);
		mul_f2i(&a, &x, &x, &z);
		add_i(&a, &a, &c);
		mul_f2i(&b, &x, &y, &z);
		add_i(&b, &b, &b);
		add_i(&b, &b, &c);
		if (n+1 & (uint64_t)1 << i) {
			add_i(&a, &a, &b);
			swap_i(&a, &b);
		}
	}
	if (n+1 & 1) {
		add_i(&a, &a, &a);
		add_i(&a, &a, &b);
		p = s2p(a.size + b.size);
		i2f(&x, &a, p);
		i2f(&y, &b, p);
		mul_f2i(&a, &x, &y, &z);
	}
	else {
		p = s2p(a.size + a.size);
		i2f(&x, &a, p);
		mul_f2i(&a, &x, &x, &z);
		p = s2p(b.size + b.size);
		i2f(&y, &b, p);
		mul_f2i(&b, &y, &y, &z);
		add_i(&a, &a, &b);
	}
 
	printf("F(%llu) = ", n);
	print(&a);
	printf("\r\n");
 
	free_i(&a);
	free_i(&b);
	free_i(&c);
	free_f(&x);
	free_f(&y);
	free_f(&z);
}
 
int main(int argc, char** argv){
	f(10000000);
	return 0;
}

I2luY2x1ZGUgPHN0ZGludC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KI2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8bWF0aC5oPgoKY29uc3QgdWludDMyX3QgUkFESVggPSAxMDAwMDsKY29uc3QgZG91YmxlIHBpID0gMy4xNDE1OTI2NTM1ODk3OTMyMzg1OwoKZG91YmxlIGNvczE7CmRvdWJsZSBzaW4xOwoKdm9pZCBmcihkb3VibGUgKnMxLGRvdWJsZSAqczIsZG91YmxlICplbmQsc2l6ZV90IGFkZCxzaXplX3QgdDkwKXsKCWZvcig7czE8ZW5kO3MxKz1hZGQsczIrPWFkZCl7CgkJZG91YmxlIHIwLHIxLHIyLHIzLG0wLG0xOwoKCQlyMD1zMVswXTsKCQlyMT1zMlswXTsKCQlyMj1zMVt0OTBdOwoJCXIzPXMyW3Q5MF07CgoJCW0wPXIyKmNvczEtcjMqc2luMTsKCQltMT1yMipzaW4xK3IzKmNvczE7CgoJCXMxWzBdICAgPSByMCttMDsKCQlzMlswXSAgID0gcjAtbTA7CgkJczFbdDkwXSA9LXIxK20xOwoJCXMyW3Q5MF0gPSByMSttMTsKCX0KfQoKdm9pZCBmcmkoZG91YmxlICpzMSxkb3VibGUgKnMyLGRvdWJsZSAqZW5kLHNpemVfdCBhZGQsc2l6ZV90IHQ5MCl7Cglmb3IoO3MxPGVuZDtzMSs9YWRkLHMyKz1hZGQpewoJCWRvdWJsZSByMCxyMSxyMixyMyxtMCxtMSxtMixtMzsKCgkJcjA9czFbMF07CgkJcjE9czJbMF07CgkJcjI9czFbdDkwXTsKCQlyMz1zMlt0OTBdOwoKCQltMD0gcjArcjE7CgkJbTE9LXIyK3IzOwoJCW0yPSByMC1yMTsKCQltMz0gcjIrcjM7CgoJCXMxWzBdICAgPSBtMDsKCQlzMlswXSAgID0gbTE7CgkJczFbdDkwXSA9IG0yKmNvczErbTMqc2luMTsKCQlzMlt0OTBdID0tbTIqc2luMSttMypjb3MxOwoJfQp9Cgp2b2lkIGZyMChkb3VibGUgKnMxLGRvdWJsZSAqZW5kLHNpemVfdCBhZGQsc2l6ZV90IHQ5MCl7Cglmb3IoO3MxPGVuZDtzMSs9YWRkKXsKCQlkb3VibGUgcjAscjE7CgoJCXIwPXMxWzBdOwoJCXIxPXMxW3Q5MF07CgoJCXMxWzBdID1yMCtyMTsKCQlzMVt0OTBdID1yMC1yMTsKCX0KfQoKdm9pZCBzd2FwX2QoZG91YmxlICphLCBkb3VibGUgKmIpIHsKCWRvdWJsZSB0ID0gKmE7CgkqYSA9ICpiOwoJKmIgPSB0Owp9Cgp2b2lkIGJ4Y2hnKGRvdWJsZSAqcyxpbnQgcCl7CglzaXplX3QgdDQsIHQ1LCB0NjsKCXNpemVfdCB0MDQ1LCB0MDkwLCB0MTgwLCB0MjcwOwoKCXQwNDUgPSAoc2l6ZV90KTE8PHAtMzsKCXQwOTAgPSB0MDQ1ICsgdDA0NTsKCXQxODAgPSB0MDkwICsgdDA5MDsKCXQyNzAgPSB0MTgwICsgdDA5MDsKCgl0NCA9IHQwOTAgLSA0OwoJdDUgPSB0NDsKCWRvIHsKCQlzd2FwX2QoJnNbdDQrMV0sICZzW3QxODArdDVdKTsKCQlzd2FwX2QoJnNbdDQrMl0sICZzW3QwOTArdDVdKTsKCQlzd2FwX2QoJnNbdDQrM10sICZzW3QyNzArdDVdKTsKCQlzd2FwX2QoJnNbdDA5MCt0NCsxXSwgJnNbdDE4MCt0NSsyXSk7CgkJc3dhcF9kKCZzW3QwOTArdDQrM10sICZzW3QyNzArdDUrMl0pOwoJCXN3YXBfZCgmc1t0MTgwK3Q0KzNdLCAmc1t0MjcwK3Q1KzFdKTsKCgkJaWYodDQgPCB0NSl7CgkJCXN3YXBfZCgmc1t0NF0sICZzW3Q1XSk7CgkJCXN3YXBfZCgmc1t0MDkwK3Q0KzJdLCAmc1t0MDkwK3Q1KzJdKTsKCQkJc3dhcF9kKCZzW3QxODArdDQrMV0sICZzW3QxODArdDUrMV0pOwoJCQlzd2FwX2QoJnNbdDI3MCt0NCszXSwgJnNbdDI3MCt0NSszXSk7CgkJfQoJCWlmICh0NCA9PSAwKXsKCQkJYnJlYWs7CgkJfQoKCQl0NCAtPSA0OwoJCXQ2ID0gdDA0NTsKCQlmb3IoOzspewoJCQl0NSBePSB0NjsKCQkJaWYoKHQ1ICYgdDYpID09IDApewoJCQkJYnJlYWs7CgkJCX0KCQkJdDYgPj49IDE7CgkJfQoJfSB3aGlsZSAoMSk7Cn0KCnZvaWQgYml0ZXhjaGcoZG91YmxlICpzLGludCBwKXsKCWlmIChwIDw9IDEpewoJfQoJZWxzZSBpZiAocCA9PSAyKXsKCQlzd2FwX2QoJnNbMV0sJnNbMl0pOwoJfQoJZWxzZSBpZiAocCA9PSAzKXsKCQlzd2FwX2QoJnNbMV0sJnNbNF0pOwoJCXN3YXBfZCgmc1szXSwmc1s2XSk7Cgl9CgllbHNlIHsKCQlieGNoZyhzLHApOwoJfQp9Cgpkb3VibGUqIFNJTl9UQUJMRVs2NF0gPSB7MH07Cgpjb25zdCBkb3VibGUqIHNpbl90YWJsZShpbnQgcCl7CglpZiAocCA+PSAyICYmIFNJTl9UQUJMRVtwXSA9PSAwKXsKCQlzaXplX3QgdDA5MCA9IChzaXplX3QpMTw8cC0yOwoJCWRvdWJsZSBrID0gMC41ICogcGkgLyB0MDkwOwoJCVNJTl9UQUJMRVtwXSA9IChkb3VibGUqKW1hbGxvYyh0MDkwKnNpemVvZihkb3VibGUpKTsKCQlmb3IgKGludCBpID0gMCA7IGkgPCB0MDkwIDsgaSsrKXsKCQkJU0lOX1RBQkxFW3BdW2ldID0gc2luKGsgKiBpKTsKCQl9Cgl9CglyZXR1cm4gU0lOX1RBQkxFW3BdOwp9Cgp2b2lkIGZvdXJpKGRvdWJsZSAqcywgaW50IHApewoJY29uc3QgZG91YmxlKiB0YWJsZSA9IHNpbl90YWJsZShwKTsKCXNpemVfdCBxOwoKCWJpdGV4Y2hnKHMscCk7CgoJcSA9IChzaXplX3QpMTw8cDsKCglmb3IgKGludCBpID0gMTtpIDw9IHA7IGkrKyl7CgkJc2l6ZV90IHIzNjAgPSAoc2l6ZV90KTE8PGk7CgkJc2l6ZV90IHIxODAgPSByMzYwIC8gMjsKCQlzaXplX3QgcjA5MCA9IHIxODAgLyAyOwoJCXNpemVfdCBrMSA9IDA7CgkJc2l6ZV90IGsyID0gcjE4MCAtIDE7CgkJc2l6ZV90IHQwLCB0MSwgdDI7CgoJCWZyMCgmc1swXSwgJnNbcV0sIHIzNjAsIHIxODApOwoJCWsxICsrOwoKCQl0MCA9IChzaXplX3QpMTw8cC1pOwoJCXQxID0gKChzaXplX3QpMTw8cC0yKSAtIHQwOwoJCXQyID0gKHNpemVfdCkxPDxwLWk7CgkJZm9yICg7azEgPCByMDkwO2sxICsrLGsyIC0tKXsKCQkJc2luMSA9IHRhYmxlW3QwXTsKCQkJY29zMSA9IHRhYmxlW3QxXTsKCQkJZnIoJnNbazFdLCAmc1trMl0sICZzW3FdLCByMzYwLCByMTgwKTsKCQkJdDAgKz0gdDI7CgkJCXQxIC09IHQyOwoJCX0KCX0KfQoKdm9pZCBmb3VyaWludihkb3VibGUgKnMsIGludCBwKXsKCWNvbnN0IGRvdWJsZSogdGFibGUgPSBzaW5fdGFibGUocCk7CgoJc2l6ZV90IHEgPSAoc2l6ZV90KTE8PHA7CgoJZm9yIChpbnQgaSA9IHA7aSA+PSAxOyBpLS0pewoJCXNpemVfdCByMzYwID0gKHNpemVfdCkxPDxpOwoJCXNpemVfdCByMTgwID0gcjM2MCAvIDI7CgkJc2l6ZV90IHIwOTAgPSByMTgwIC8gMjsKCQlzaXplX3QgazEgPSAwOwoJCXNpemVfdCBrMiA9IHIxODAgLSAxOwoJCXNpemVfdCB0MCwgdDEsIHQyOwoKCQlmcjAoJnNbMF0sICZzW3FdLCByMzYwLCByMTgwKTsKCQlrMSArKzsKCgkJdDAgPSAoc2l6ZV90KTE8PHAtaTsKCQl0MSA9ICgoc2l6ZV90KTE8PHAtMikgLSB0MDsKCQl0MiA9IChzaXplX3QpMTw8cC1pOwoJCWZvciAoO2sxIDwgcjA5MDtrMSArKyxrMiAtLSl7CgkJCXNpbjEgPSB0YWJsZVt0MF07CgkJCWNvczEgPSB0YWJsZVt0MV07CgkJCWZyaSgmc1trMV0sICZzW2syXSwgJnNbcV0sIHIzNjAsIHIxODApOwoJCQl0MCArPSB0MjsKCQkJdDEgLT0gdDI7CgkJfQoJfQoJYml0ZXhjaGcocyxwKTsKfQoKaW50IHMycChzaXplX3QgcykgewoJaW50IGk7Cglmb3IgKGkgPSAwOyBpIDwgNjQ7IGkrKykgewoJCWlmICgoc2l6ZV90KTEgPDwgaSA+PSBzKSB7CgkJCWJyZWFrOwoJCX0KCX0KCXJldHVybiBpOwp9Cgp0eXBlZGVmIHN0cnVjdCBJXyB7Cgl1aW50MTZfdCAqZGF0YTsKCXNpemVfdCBjYXBhY2l0eTsKCXNpemVfdCBzaXplOwp9IEk7Cgp0eXBlZGVmIHN0cnVjdCBGXyB7Cglkb3VibGUgKmRhdGE7CglzaXplX3QgY2FwYWNpdHk7CglpbnQgcDsKfSBGOwoKdm9pZCBhbGxvY19pKEkgKmEsIHNpemVfdCBjYXApewoJYS0+ZGF0YSA9ICh1aW50MTZfdCopbWFsbG9jKGNhcCAqIHNpemVvZih1aW50MTZfdCkpOwoJYS0+Y2FwYWNpdHkgPSBjYXA7Cn0KCnZvaWQgZnJlZV9pKEkgKmEpIHsKCWZyZWUoYS0+ZGF0YSk7Cn0KCnZvaWQgYWxsb2NfZihGICphLCBpbnQgcCkgewoJc2l6ZV90IGNhcCA9IChzaXplX3QpMSA8PCBwOwoJYS0+ZGF0YSA9IChkb3VibGUqKW1hbGxvYyhjYXAgKiBzaXplb2YoZG91YmxlKSk7CglhLT5jYXBhY2l0eSA9IGNhcDsKfQoKdm9pZCBmcmVlX2YoRiAqYSl7CglmcmVlKGEtPmRhdGEpOwp9Cgp2b2lkIHN3YXBfaShJICphLCBJICpiKSB7CglJIHQgPSAqYTsKCSphID0gKmI7CgkqYiA9IHQ7Cn0KCnZvaWQgaTJmKEYgKmEsIGNvbnN0IEkgKmIsIGludCBwKXsKCXNpemVfdCBpOwoJc2l6ZV90IHQzNjAgPSAoc2l6ZV90KTEgPDwgcDsKCWludCBjYXJyeSA9IDA7CglhLT5wID0gcDsKCWZvciAoaSA9IDA7IGkgPCBiLT5zaXplIC0xOyBpKyspewoJCWludCB0ID0gYi0+ZGF0YVtpXSArIGNhcnJ5OwoJCWlmICh0IDwgKGludClSQURJWC8yKXsKCQkJYS0+ZGF0YVtpXSA9IHQ7CgkJCWNhcnJ5ID0gMDsKCQl9CgkJZWxzZSB7CgkJCWEtPmRhdGFbaV0gPSAoaW50KXQgLSAoaW50KVJBRElYOwoJCQljYXJyeSA9IDE7CgkJfQoJfQoJYS0+ZGF0YVtpXSA9IGItPmRhdGFbaV0gKyBjYXJyeTsKCWkrKzsKCWZvciAoOyBpIDwgdDM2MDsgaSsrKSB7CgkJYS0+ZGF0YVtpXSA9IDAuOwoJfQoJZm91cmkoYS0+ZGF0YSwgcCk7Cn0KCnZvaWQgbXVsX2YyaShJICphLCBjb25zdCBGICpiLCBjb25zdCBGICpjLCBGICpkKXsKCWludCBwID0gYi0+cDsKCXNpemVfdCB0MTgwID0gKHNpemVfdCkxIDw8IHAtMTsKCXNpemVfdCB0MzYwID0gdDE4MCArIHQxODA7CglzaXplX3QgaTsKCWludDY0X3QgY2Fycnk7CglzaXplX3QgdDsKCXNpemVfdCBzOwoJZG91YmxlIGs7CgoJZC0+ZGF0YVswXSA9IGItPmRhdGFbMF0gKiBjLT5kYXRhWzBdICogLjU7CglkLT5kYXRhW3QxODBdID0gYi0+ZGF0YVt0MTgwXSAqIGMtPmRhdGFbdDE4MF0gKiAuNTsKCXsKCQlzaXplX3QgazEgPSAxOwoJCXNpemVfdCBrMiA9ICgoc2l6ZV90KTE8PHApLTE7CgkJc2l6ZV90IGVuZCA9IHQxODA7CgkJZm9yICg7IGsxIDwgZW5kIDsgazErKyxrMi0tKXsKCQkJZG91YmxlIHJlID0gYi0+ZGF0YVtrMV0gKiBjLT5kYXRhW2sxXSAtIGItPmRhdGFbazJdICogYy0+ZGF0YVtrMl07CgkJCWRvdWJsZSBpbSA9IGItPmRhdGFbazFdICogYy0+ZGF0YVtrMl0gKyBiLT5kYXRhW2syXSAqIGMtPmRhdGFbazFdOwoJCQlkLT5kYXRhW2sxXSA9IHJlOwoJCQlkLT5kYXRhW2syXSA9IGltOwoJCX0KCX0KCglmb3VyaWludihkLT5kYXRhLCBwKTsKCglzID0gYS0+Y2FwYWNpdHkgPCB0MzYwID8gYS0+Y2FwYWNpdHkgOiB0MzYwOwoKCWNhcnJ5ID0gMDsKCXQgPSAxOwoJayA9IGxkZXhwKDEuLCAtcCsxKTsKCWZvciAoaSA9IDAgOyBpIDwgcyA7IGkrKyl7CgkJaW50NjRfdCBlID0gKGludDY0X3QpZmxvb3IoZC0+ZGF0YVtpXSAqIGsgKyAuNSkgKyBjYXJyeTsKCQlpbnQxNl90IGY7CgkJY2FycnkgPSBlIC8gUkFESVg7CgkJZiA9IChpbnQxNl90KShlIC0gY2FycnkgKiBSQURJWCk7CgkJaWYgKGYgPCAwKXsKCQkJZiArPSBSQURJWDsKCQkJY2FycnkgLS07CgkJfQoJCWEtPmRhdGFbaV0gPSBmOwoJCWlmIChmICE9IDApIHsKCQkJdCA9IGkgKyAxOwoJCX0KCX0KCWEtPnNpemUgPSB0Owp9Cgp2b2lkIGFkZF9pKEkgKmEsIGNvbnN0IEkgKmIsIGNvbnN0IEkgKmMpIHsKCXVpbnQxNl90IGNhcnJ5ID0gMDsKCXNpemVfdCBpOwoJaWYgKGItPnNpemUgPiBjLT5zaXplKXsKCQljb25zdCBJICp0ID0gYjsKCQliID0gYzsKCQljID0gdDsKCX0KCglmb3IgKGkgPSAwOyBpIDwgYi0+c2l6ZTsgaSsrKSB7CgkJdWludDE2X3QgZCA9IGItPmRhdGFbaV0gKyBjLT5kYXRhW2ldICsgY2Fycnk7CgkJY2FycnkgPSAwOwoJCWlmIChkID49IFJBRElYKXsKCQkJZCAtPSBSQURJWDsKCQkJY2FycnkgKys7CgkJfQoJCWEtPmRhdGFbaV0gPSBkOwoJfQoJZm9yICg7IGkgPCBjLT5zaXplOyBpKyspIHsKCQl1aW50MTZfdCBkID0gYy0+ZGF0YVtpXSArIGNhcnJ5OwoJCWNhcnJ5ID0gMDsKCQlpZiAoZCA+PSBSQURJWCl7CgkJCWQgLT0gUkFESVg7CgkJCWNhcnJ5ICsrOwoJCX0KCQlhLT5kYXRhW2ldID0gZDsKCX0KCWEtPnNpemUgPSBjLT5zaXplOwoJaWYgKGNhcnJ5ICE9IDApewoJCWEtPmRhdGFbYS0+c2l6ZSsrXSA9IGNhcnJ5OwoJfQp9Cgp2b2lkIHByaW50KGNvbnN0IEkgKmEpewoJc2l6ZV90IHMgPSBhLT5zaXplOwoJcHJpbnRmKCIldSIsIGEtPmRhdGFbLS1zXSk7Cgl3aGlsZSAocyAhPSAwKSB7CgkJcHJpbnRmKCIlMDR1IiwgYS0+ZGF0YVstLXNdKTsKCX0KfQoKdm9pZCBmKHVpbnQ2NF90IG4pewoJSSBhLCBiLCBjOwoJRiB4LCB5LCB6OwoJaW50IGksIHA7CgoJewoJCXNpemVfdCBjYXAgPSAoc2l6ZV90KWZsb29yKChsb2coc3FydCgxLjI1KSArIC41KSpuIC0gMC41KmxvZyg1LikpICogKDEuIC8gbG9nKChkb3VibGUpUkFESVgpKSArIDIuMDAxKTsKCQlpZiAoY2FwIDw9IDIpIHsKCQkJY2FwID0gMjsKCQl9CgkJcCA9IHMycChjYXApOwoJCWFsbG9jX2koJmEsIGNhcCk7CgkJYWxsb2NfaSgmYiwgY2FwKTsKCQlhbGxvY19pKCZjLCBjYXApOwoJCWFsbG9jX2YoJngsIHApOwoJCWFsbG9jX2YoJnksIHApOwoJCWFsbG9jX2YoJnosIHApOwoJCWEuZGF0YVswXSA9IDE7CgkJYS5zaXplID0gMTsKCQliLmRhdGFbMF0gPSAwOwoJCWIuc2l6ZSA9IDE7Cgl9CgoJZm9yIChpID0gNjM7IGkgPiAwOyBpLS0pIHsKCQlwID0gczJwKGIuc2l6ZSArIGIuc2l6ZSk7CgkJaTJmKCZ4LCAmYSwgcCk7CgkJaTJmKCZ5LCAmYiwgcCk7CgkJbXVsX2YyaSgmYywgJnksICZ5LCAmeik7CgkJbXVsX2YyaSgmYSwgJngsICZ4LCAmeik7CgkJYWRkX2koJmEsICZhLCAmYyk7CgkJbXVsX2YyaSgmYiwgJngsICZ5LCAmeik7CgkJYWRkX2koJmIsICZiLCAmYik7CgkJYWRkX2koJmIsICZiLCAmYyk7CgkJaWYgKG4rMSAmICh1aW50NjRfdCkxIDw8IGkpIHsKCQkJYWRkX2koJmEsICZhLCAmYik7CgkJCXN3YXBfaSgmYSwgJmIpOwoJCX0KCX0KCWlmIChuKzEgJiAxKSB7CgkJYWRkX2koJmEsICZhLCAmYSk7CgkJYWRkX2koJmEsICZhLCAmYik7CgkJcCA9IHMycChhLnNpemUgKyBiLnNpemUpOwoJCWkyZigmeCwgJmEsIHApOwoJCWkyZigmeSwgJmIsIHApOwoJCW11bF9mMmkoJmEsICZ4LCAmeSwgJnopOwoJfQoJZWxzZSB7CgkJcCA9IHMycChhLnNpemUgKyBhLnNpemUpOwoJCWkyZigmeCwgJmEsIHApOwoJCW11bF9mMmkoJmEsICZ4LCAmeCwgJnopOwoJCXAgPSBzMnAoYi5zaXplICsgYi5zaXplKTsKCQlpMmYoJnksICZiLCBwKTsKCQltdWxfZjJpKCZiLCAmeSwgJnksICZ6KTsKCQlhZGRfaSgmYSwgJmEsICZiKTsKCX0KCglwcmludGYoIkYoJWxsdSkgPSAiLCBuKTsKCXByaW50KCZhKTsKCXByaW50ZigiXHJcbiIpOwoKCWZyZWVfaSgmYSk7CglmcmVlX2koJmIpOwoJZnJlZV9pKCZjKTsKCWZyZWVfZigmeCk7CglmcmVlX2YoJnkpOwoJZnJlZV9mKCZ6KTsKfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIqKiBhcmd2KXsKCWYoMTAwMDAwMDApOwoJcmV0dXJuIDA7Cn0K

Runtime error #stdin #stdout 0.31s 18336KB

stdin

copy

Standard input is empty

stdout

copy

F(10000000) = 11298343782253997603170636377458663729448371904890408815135776432455347311679331375242197774582477454885033295415297379829176189752739285436379130293205110803936071609470676322761568284248970064197366206825555962868512001648785247571427990297634353314625437488325747280191868034426093376131220787180932249524738354896450476964115588244381035268921048858630282891083257805282510919732055013131754303952469745209515299152873878891230599963213372289561482699385535451421389231491816430274041581545933032072597248442299459017913355428362344260263652724615431201289009741731430059272677308812151604686180694939427289643128039037327184149597448016990022352747195609146994737502119772509806106348102758684530081480446195174827027793573415791787704841713444329210273445431566677078085358747888557615801979112362980511728004386656080547842813009093716948622126126722041747509359669002058596851837157109753370537531041702172377509019719126460148419486076150311486281448806743368296159389406907153746665170201973462650506957605288875128858598698715415912330640482558663338539959343448648173242997072890602522433296814831452053243437880699349221622825899305956121615723384855405729916891691429291942578131524648791854319656898393941813171636926015466482143144351635957457100430182404538253337927897538541092803085300212725282922422404802981362606558852590674567933885894037597341016752575553016128225833475708199471199130880469785460493179120211824123551595964617549536470967333966204236801744314372378414470728325598404518621030710717985662538529833306347356193745561074814454166006206636983255425426613991524762647328198712882546372246080254896453245116483934508983902330408830904565598127645699437909261067889855227758863133257607050615493005085037135846304525592491156173394639227930513986678790936581454223230605921572307483689552389112899236258760178719809463367950864186342615182841053161537643064694929083471924842331008786403350465972794929541079669622740073673671191419354637003408327384700981964960087356646822529606922344694739802934009999459990796801092523911622168793095807335257290265522640373043539523251294366158538224093821596140373357063479302639864724615665972696363363039158073923476926403796075737204773526338106275116891338003036058783325728384458875600550962841273614924593552847847100070022914907853154801448720553746231195727538692594775512918119213618415019502205171622558676151764823797829634992882345570172815207451581784004625653447382197589312487785753258476390915822487101774461271415645515681627334198090207377628486707007936803619973144581434224585016775134178608969251293076387688858732089325845043851289390756070606622681244762119190051700493956997503719253306836979317713002742082819296947043602977917363127196146202633046157198971731304967254066549821755645226951017550776450860857445374331534967281947979150332455342306401241371783592445356798416780310817377427369977517637587971827662106312426463049377849105380084683743666273202069977511418177766617639088585154499007644668011591147142948554671609110524629150296332849442806949861754225082972947933907735723648317309652014585112050094235595962212573892398972067285170691265071302557815204984777313781002051817435284610527922621208447931828371906002683351051052744572643878179909449581029193222450046181328263967348545176577989086717806153860399351599733525065860127034671133906419092047962481857758906414921403510632066733623814415483763871952960096334198496812217005459652250252645905809553388825451423299549936758209906906953849379608980014965867506664838341168027398385894278183889507983642856084373356316004512462362415791264845227216226120327926771858930436980312772763525517129375614285218419433397793345222221277276606821898551859985493280114353082055262336111393875904164522866320187838870620068537780652990107973850861353665246225100306913962487323046466598875617235164260419293190678513009518053301276583279515649366816779307342618091121317028146162905144933374686882774805378025994578348525662322295344988241717610722105255690729494297175105194209156699766485240877869412219320734457208353439035705395746870760474677365528763943602568801786713705854887148728697227837952200081422030332761412272669551565086718503256094985818514880598030912864577061138589492542291163599506930656135087455142459084523101655319819827343592325549760756788550957662738895256753874813573172195595718822664137418955739107090847549347890699786232844787964040250057363395885870847431463924982401899055832585095373193981591296956787708473114808521761744411179408037326747719016559724701215020871221156642571867227248306978931666326893599354343283136579809449841192233615752016782566458150925947299477171866796191761154449449079704920705050368322855567909666847607729499630623469304024028315314076064544507453809087537610488414385440754830464854258902617641842233484329086811066012018995188642323167229082730352903019081191254173381854870745870705975134742572233354416191686334604053661097080742426065821482075313294493139141609550385427786712623727691488784201043215837257659360154637971809453121896032678490503472138252019452707772363595826143831686102724027537582409874841551601232900583792489002353872449457343684753797301036979902258609009697051703442593709191449253547188860581012144322224947689607483242643544453168485247040818209255357884702451569001323776242168393991536670943181518740778228869273664079348944545844389629862332438167263285811150018821701985264485216062941599363278972722438249413048024275802796475018208567136483142163322506871718677981890184149094526383557606122803975551221704317755812956649145321333693372079984192694538127507366975041710873228219371818315934027459764333479483686417632509054051578227462801789189205334119517230136073815348747180725952654537588927129120240977679637595868386673475863251379469993842169484874312061378858377135672609213365728100343638691264801709442041370285387956177962592098982744185969770330151306110065697857235425664767287425139484725324886067292490886235996329880549910591993743807874481944093127000264598630094601155029411116145318336707273233969207609973428352568307513182826770685478208968691483824431792419346953941976334909610667799811238832147663676728507921662404259530898563599440062527735013612880003616366041837139896408329361926687944113838551189267452986937628465328757838190529312401369629359021719388494491856425586417888899274448055186934368723840850899842422048803397404883924867778304241977881610091304215161440522946630224435787425862558350721815910958695492959308675043561684579625284845450999035345639891828162955418379096809478905320738097641565781863099599976161398757566158176612002440757816558865602101575471141240046866160191051816313094240742309060236939448101172997756819045585622300070829112653579964274343918221391971612943194145799970080039208083680235711868568730575839996880592164671158980759943522325072060697526175353717513403830575570735155815134015276942344944040090374388293342503469812507343634320227111658094865116312908238681187411337816029355179513429515715206434638188081348127303195545580486563751424146024815430439379520200409951186088147761053773531633330381502059783312676743898742856778743054099312164943571076581241854300212890296996911350730694874884712763664042123323421182867732488988439300070007751764313491261763696621062318565974363350971081866454733353009574750894277953855994602503921956047890656903771370762922068631180158288805983367030257967473150282229378149799015540401433934131074640593427087724723286175389704402854799082630869132725522028473178607781277225494114316291520810215368906567762179555719470905860488058918423975374668162317777596190139787210292172576687821193583418557328511445586644957240356886289189203326982958193558294550661193474057944066429074018207780902360877320663604197813127493309994493048702511508492639167208344429862199555129305955564384327616468892293429759640767281260530381133719674890506455624243049477367669009022228478276577333248467361731505116338395332908191723388395613894924290459153780200087174360346375768965265297226385200394502453284413958321157645680031792918869221107414513584495394753057072945198470575263817732880334067947675274883421122135900384266460615005472840534661542322045961635560955672098047003988539400334217584688035680532219664927603685791858748825656941744368951303186166433556790244689468458834854287202642418790958514258144461805093467698331944475514784481736084439207746259404632990516866034098187074992246826616451634607738247432388518509981247659267375903803395583408876218718015253721662106958166824966565339912388774060779031908693965200542191849674651676715759656814431929945359249984729435880101234782509638278053693361885918790357679784953592379700805250590613275695549656231778106585314914132299909481100609221863445193217729666488190593554744520854233561427308031833478435388884146861954844986195639041942542564960916228964616432135454250991679304768943872992067744553378667041452184753182701589475739772981415041412517705332544109867890233771205766573217759482065691515856531374489650286034096824603577492024425355990689234222288536527871902505306298108164208531265299068487150716678022379502053035949614704426480495071795585933964579242130524013222866884802895618504194472530585605933326744845814502849208974001362127350010443744906633509122375030051798617926801484187806761226270343253129019624700860525574849845359337765329933926757115355917324041062499623741893818033637583136148720557090942046561675930875453956133207369604026358549565790981784594103068996327430877390136992526147191697614543449890850876379981505905446432821914849209298602556024711625453085891647139647914119244055176103454294298144392426411141701853022755785483362148246871943918153274247549271711542237389519277755086633018263360598977122878830312837355125901125412357930370929308458423959152390959452053985002644959875229084284585326928520745293209694380114294279973111286689051443559670180507434297019571482629429182795946190932188663302481232117463310870983326201169622777948447171063393091040437907265312829007673397379196224276171077622109212589315893951674999734851145947205340935693495968594859590333387428318960935613581366791370840941993611043543995301080644101006953408221821463706541341318755747138620048897084101740801048355223650928862387194803177452804483920384074910986094782386983261303852828973438165746146976839682476662817459774602804946737102003364463150703641564690069734441922316503600980703378354275463678218684779305559281424117790474966784398263793029888864115500067311018604113534384330036896424017626985295718041389906002054119449000692930681000887460455066066520733563165664083397229325562028310839590525010215737664658090792015995307279597607917883338106162214472148546218133247381167911243495726825288797363181716468205983108363602689823089400410736975200751726626855928177449312198798200051230529864267173428758814790711708773750691283895178727059883618656194306324775831235245941176249485612036864863408333161001342607824155417421825394121798868888888261705273496468364921707454227410876477364236951600585156414329828927346102268672145410347074885237277390910855762741590133215642848472614898000277331536760464477128109898313231941726507150524317970439857724265674140606615155993855736531405911738755514260466829712129114145207279640345620334340545527048984270216281103647472612932123810320555458959335699950794711663828072483421854398415229123743926540945363209738183842039275999641970882940532780303282592201729820854741893229076350636294870333174029260347904865678935709579080177231809828468268305928060383453126772219777978028769075135188693769730448468298250525742491252374890200972768883663164210072758446108859754893928647033297577199273245333892900626276026248481873468019746682270417513652953485967798297500452621835571645314350555781850689188785073461170774012106575908482622484572756010849228422827086395747280918538317408097914220669782444544040385670494283798237293354959972341973629002834093778471688156287550908834849607795386255947676703135745828262168457290635838217462599745404136117214793671366151473295249150140513119563705647009725443133445739948983446232822579776841105033982215260011162604060234374255479705014747778949965885475534405016393511467337031986269798471819371155464572057012232177472392826441520000075082382192269552814360126891752407557146021652147379548140431434853781957069843030797425650995369973671966081233423223533494076606363047816128852006576172154468338286503414461290772711190415441105580294078139409818604252882069604201475329381941124607337486436846921942667091922380630930150226211358377294148079598465497478668859334227156098843610797855483421719383300792044693819848656164678661361284964805568925546134806497579495774895868264739314534475173550871631397604761882239397486071107967510264200879103213699482239724021607464423816622173248618858966338573295122643067407255756002879504589274804861780867811943252023959203283794862069868974912799275743282471283084657283634334584903093946155660443140150985338679901682611741725606117089471597566528663223282110285470732513200212207887767686719166258598130039815637816280677968991518166357924545477100001303466120205177755033901538562870545634614095827050147163643508925780440463046629548742732508691126264665811896641483848166453009492038979177643488935025382083607434710458566382137902382714676035480633309786378942008748757602458520624842586230645135432615555493207829331364564765398315211367585828289998581951055923443336508948394233543126153823864637149921340067896414414159449165831508640122782621170483885962195853201488300286206835087210950855937500485181868268817045404050999393688549783615542206156536118700877468815882352205497207686880421446574641374316005250821957793498542113194806086618867792574424003812404654515702832071741965193376994597833368439369112099480622632591315478491378326049331642440671576937762776918764873524201788887475528504647849752241195554396004500191788880376931140872676104338455165037953040573647502382982245171821448566546994970493368640591274975647453078835763934417683600980928109115509931937912471574913955069224373241686548238789989280042422592581946008259679533512152094256534742319398848240627524717464844719020451587374780077321789790961221586330993311146080708018965874872912240198570220561852307923326119608431358895566007997586590897314778129696450872986509781703469942309283251856390521186438398933593431065521722217466606215353439981666262494935803839297868730087814022687662592360807792695410661926916591403210140632405445693419315171458784778459306742171664258908150732431413659333571669421098762384018851224774511552291419512049024307937512461098840147238915698681839535420762091742354805353182870327049870873170195352775667389622459042001688184119281562886623640785501202619962820542872502503248562414256037296021580755669060307528951959697970205357648395873935122710063872019588292576777161149667968546609979578811877410999384911991167983944978052786028075244315333029860269159755181496837114063694413077646005165682890812029391696063977124436129976397694064549671667844304622937810090779769292915734613559341948203586722260792238331258091023641577419644283072265970053503860401062203817696247172497788913791333855206237935843451272411386835598563468877897561100313124229583877624532924895261340358248797788529587022922438568857621295406030964887311023527167568672726902578926435452519197230710699313726500507551376613443430093022101305413443991271928902727139388382555570886240301645682455403010860542294800168337131483693668465845974616539416265986392379533728573821048881215282368491012788864307261571344306036896952769097521765850705870690637830048552178578281438758928081407253646975497768860896272909331298324314948297421129068003905672080298795066337345618018299985624905381532428119572509250251372497382209961329847790301508458408654394599051654926626901432851655935564264978094364053665408545343208815778797544822132661936505677368404079524573441239860389131467897169108130718342668659380973186239544184676539371309099587867108448088724344844688420671497402272799087165096673988959321144612978131700234640629228185707734831675559159624076061907041720039892942913591115642111908370896034155037832762420718586759751405488350203452676562396999794576704347327649609118170656326490656691047559119140547728421340164945408062969423578464506452013064582060183410051216452469328272908606307823764306441512889525145962071200719016391793061220949528475932867611879497858394777528974900884210106611852271239758394463313437172236821919454862877664385272831686193128813564950333766694938683921470479322519126805911963387448040902783259611132519299660658152483571276207393098928518191947547868176854292611239487123216874420551441190153092787414726843388475773374314068503996001541166577412142362345697332319945579262468027173683264879251856541496059415030155757701614043590274731247745583754177826698550752572546232415802104743952747418339329380595881341937239801860950866410610905647040110173511960667173621712839576859953492175420941085547121130517568924336371170629661373909750942997540793161211527541656778352828569402588635716211099374519954064820198932713752513690321860572246883125367632175412108870491222280458013488470395306120447154231549520527713091243344051661917788959120061634951314964868865632402154773650077398568072541293836539478102984741110742154212304360409080782105220677320870399568548167185320501832931505672262986117020640444024129575520457972383111069584712072959288567730007649962863044671861212821067375852780524287089034836947504837231343850435805474755050718198115259117146561461383934059214567537849495123924865056307592151562793630673702449050689284245177060642021718238055008931883798335269915179327812673719869604328865954954494172036418673426999007702446556426799551297268013607956699249710948075751996951405397289026353363657049951094632604883978750153881853139320818960315793489966792941985155943240727678483899966318591093600067132471109560796722145084496621078697675795494752210613858847534992200585675299341248270110107893251323143937052222018158250264999856645039186432474561130291388904440697208734944707694367287558615056229094917498576008545889072016534692075964959230199801637386137249854796584796798846489336163182775386276118295413286815672244963737471444792328363725101641210289329999278157476051874675638971378246553164631075275556178799114936540174760474004022177625910252937724118868791678109062475468148656349313045331261249643453685741002068362378375498943060162247218900918931930800374545063114908170303621765715449910399152726324663632043652115403037236800065947064359848826350105669701839975108291182388696535959653694351527818593786351432640709826318679090750929161926821224241297827238894783742683989514740831877530538859599264445682166337193557657120112546681525159169430082279618734455298480746285187704638595687587344819533745533157854360132357643727225327152308297144148538585247727760222426370310968180369311160653040890701927278011687996808810203906165107956470378824518555788510563546255614518648197039088151427312517755170980334345669152522918561664201524562834820251157384351095621122195719630220361684528710376791820634009300027078313948082892176163403627051563035863911352784128055957809556033634102182776081778445177130908452226946080562775454231259998738863225669102384195645810038429815901042578335097742786289013681096279672553140901297894027555794664416746080390397321548224036518354225402211665570906401767831899089431206567076270893830242342901289071956794775490341517216570618512058230121544446433838560979743222665002621867128724392812106921005635672544539905081795456877604148574724402378076139683104316312440119078698874959156752664571481694941948028166743599129476299992714946944285025499417410298336026070339552807126534038332894621768013092899480221023778786664695923921815822092069373291208462262429800737904359879888624113186914124582550206917563482915321939931832242787760664418286103013431486378159864005985809220040047022265627799098076607527496195129916425243737403243170581690172084296687557820967248066538500385063064986333361228434496038030517383499416968065872629792662069145860099815804588458137300721901039046333106327777610945920483249252219282448657970390788304414396286731209628065449964852158217373877470765307841488844753180959860337411253450501299335254967034460643638326839781385878487941566493376462879058411183627098008021555170690925317664306737943922377943904549236575025263945509137308515786164391432675856382985464973818819448677612162340893506301930759005705878222430314524408099418799133378298746311586843998813264652885666265046575652055840201039877340472669903706427313086764715439264899818408838840027549616170023790201769753269334481285419377014585963607369715967555456143948756713657028869785529509831532496533964126619656275452237293869233894474732309418080778735226337270464696874507875123907479018042338890133096788119175358440985954008483108183146199828565468350292195092847834634545169041441133214567268860472443940138151621898284503231926749322052779358598798407711730127822640227139206336030062509796194666338200895219879229246092947634002868058596047423561342730299159018605651814551307263373960420003115372717105305866275003833851022903312067400805667076489078780951966811568766566521088280346645309988360434746927684647310265167884223184400050539089191911833677783149569748235413303980723665421060494131791119831842318620845471697421111551147213821543182078778233283158258121669430143611466608858892679018356159679526399700836906437121415593117752358660841180376449770318629457245693813168234750484005851078121646965644660181518239154979947688338924321425711861821559200722559131105961925587356137831923114797655882870195476754878163527142594967719054855302586177353782560970431878868682905230897733097712779173461214856966708973333449608928245424115097251010348032992524412623000277231805345515701820446272894506260838256029957936172517358879860299568362047615710026690434689861467334514892973646436472568497282223171700659635926491581461602132508891991464085264557779933970652924145201490199182852293813911731326210166742863921030886523095393732894131530453757461404764524561154089388916631677262466443703482606227237881942737441848779161415782467040571767254834961383783345504618160300677970584530464242124053941048051992799016172626541802705466033265490316517522641076773654623843713533394164900714030584046033146627082878120621859049130800048453961843763489880416965334130320572185684071557347801111449643346425880943189223109166486756956099863173490852205066242650142797385432769179587623666827974091585479261949050466954326056943351557824690437995648714139197886970140970895336220105623186356108658171134261680216818951680404025320503081973696730556410057164243387720208687012094070734549962945323389289577473773199217361031970166023088754606817905732844996626943066849316593673749748332732973387476131699098477292690045126365867125068393684894983926952909522541148499999320410129043172386280051828938423332671429286426380505135273776013141324514674457336572814633738404340335672792239832364686809344435634320660199679634229994697014961855588468514861914560752002378284188313862057248342600720370973175064172522832922032695633976776072038820008568949824816250831499333551619257046123718703117394684586078546162588156595586167334300080137945402212255423009855525159172447493931238535078904030277131111003854608461913374475262820741682271536820486340425644842062540166690658155913835065635987175869551101244766300345276533206635610841439232434703431565710606264439197727561261918108520893429937160204616088614004015373093815592182756447051349883933972061211292210447270532778310974241894414322935259358314256253455684567020444728361917043328451873048802280372093902628457094913184498128822595101718168436312353362810173038872940944029418719245692724874602939853875855861414482994629670876795093318704673569577393154475769744361163424574036575301814531561034596584886731103313351392008960624176298211781985598319742338716337401701413967751319470236245277974647491901827826595646019997423134066473815949175299240706370402825045389042196207428335639853981625382361062339861195136515228961649780143702018154674407067007372952806209155787514534629928604169966536928627818108011569154702690474583582437504309565943516140449038323912140002254435842914717856924975638106344649012474309947168940821236320029630055542777958651826515848222726723024134389131937660978738768423837693481376986093042050900959123121635545412533941449578763642579057430326657201752772402421876099414635102505809603314309179229579197901820243808466539000893702435809871490812119282851739521675116270925861187472130160148110066282797969668088644946121108850408447856467895465752083065944901193754343250715288309018989115910639339678134468831773015313302004040508652545544775948669334033951379815552748203824482875651333081957603263133556584214252458814359782204514095268253567855553871658581791795090992472722745354766462139201778737201895573216364002950098128989107021519818656218980464429507749166914015059661172421087749222150013604605127216415528642203152901538784592417135867302924502168043520202041404735915172690530915058632719718464227131655936704573870938738677819772180153292554631509795882338420729772353201394735606317134743665126792226667220223441651078508855969515916561742732436393865848823472680163518214761317580920811238593519056930336526403995268026801706575192734512334930900454541815958989473868352252941730626027218518649247938617927954013394038533487971450299095203791011417893315159640195205128497188209688505847354737104249126882891344606819196761887408391573396629858072555370228103304432016067263919520373437155243188491625369607962490936735671453804794064371165305519786311846689987690783308015240671844793372241994479671709862308537176904074469775863784485947551972990469567098884676312156294147583483211458326932847031782921074191863448688767444869552228720288204443139801389604620344834983722472779966666441937006180145757287811586951398249955689246102323519161526330802831282105283727751848683343952090790475315454704284200730979762707281481868818697460933416465308409597515505940771866059556613890089594505263807830238769214501866809237021693571969709555132894930045385235622898091677729047049972740581896568119008311054899966553148286607542684556252392357909555969751261123023295477847562706674604476350666072538670443835703705677507764387267509778306438066555118783998657120268831060712594046253358774050085320235315235344353248338463889688842820755047590290612054747486831000663621192623894870689413261274669493648103511707993559492704998934164673551339218457851438748344821244974935022935372567472736994734132343691327945279978148252843715526399956989160936095183452868168991841262682157036436010165233483528035752088300349929431462833252314495682772427803069227285197756178525893131830157417716284299027368176175053989855354573238622996014498514083818467181737772928136351677872531192718831029015009852326798795590504739522452572260667686604232177149162649178044121148206740228219411235859870016610757698620440417500127642835793587011490448530740916825032442332122081994940882481670662790360424358187602557208486497246501183616944942416297654591563695886527315406763620895354406832709580291482071447392268541478828132533625303429167373059553988068810557126475158855187131863150771354547025998411621340642414373274506322959976823503973666733215826850431377420341591091697624882136486629988754840937351305685645800213842521690611001111430919741166168187736084917880951742447243996048931248469225737597836983656921258975890861994704120117029796356377623165046854204905412649121206650048066021715588855983860958470823157067086490081246222699334070758231172878014854216181857836322777062668651087924103430759003881959691397664291352563975334636169989183873246358401425312450941292384891776460997500672701930286924934531008586886441004248603945819053610775706872914205988557738575504335771031148959051643676623668343716506074837309741028992476932660542653543938612446671312596318897960422187762501949476646914527369151525242173839787020085065243496098424528450458901282179448415470128232468337190744589767595135135140755364870906265516298472547890110007865608064323957038333245263354457334410831593258985072245177030626185038041955232001357532287076502022482788598346738025463987084203301374061535693069835076062692810309433786280742568072684040300130493795363539388703565580327524709921068546903281528610730030162047488484383899217930680078663215296717793444576438881958795363542779643845679328233117796756282149618336181240209275862010736549072537554201284404526406228843737138299431605189074126812041410826058367091454904216378097098790717380314724509138686207166739215099560724161680109671307573695131507543276583628770502144380815650646848991346664859995770695110293575477655879763346887485733161975082534959513287284654249350930313409020188867056652149887101668741406883251541618623906562723230432339272440894481613948414637332422316684677624680997245061713460301257798591176624907136405664132896369127676400679771689941604376919623388578153530452350335973451415640869087978460274374968757462493554850804115819506653455273382600043365012885576703060109472820933183766257438328480042684845694887925250596564002234705854187333256502099390736780560940009476952801903476099279550280451358375118352658728234993326105784443157306529284431580292494759472232586745257861625729747814476268871078483660343124613063824269414721940814594122799782988437899545454549732646612948999426286226661140293160827114732679221759026601280588794093545530697527713044898494138652141024001006606689413691927388351552334033371786304279557207402039289680082316069901693533808248066077924071904779764764735446374322958945599820590277117693126127991273584272693059722867996778985244099032548891694482198715719916274189009530907244874317145746107013860105509461454166905081333659344636217214370437983568869222889171681635833204223356154209687054872712446017778821797412050933522364625970656509979546576488085522341774377903578058280073243091077314746487362263494648298360316056372721385340072610058477691252102328138476027291273958547376190838935496087875465576822862159153101266205321814232316941765968228124674792308610547456898797743263319584856787236296545206097868955345690483767610710119451205676395995226526407499176105775672961196625127021423833171308128932420079063044720671245098743893382574375326262080145867346494167484140368614098592362712910323829649295056865036387803165794717513498252457172240825205494372049397589708041768258520164645240362127319860360791424201431481658035008963177986353200064644128776557260928693286224765837467375360866022437995917090908565169623922424237691607786660266582352559366166655127351141986053216531513043036384332935842681233179951923488813374479402873944167232770421595216341017589040303964712203382207195941695762366390092691528487491009219860816678414402027744921751016099570479114877455385448542542350935900071551495243390774593597261334375754405856094554618597865393191737056546256632122562528822696125043708939728792203145657124041272667859979349155707257475185087648980290399126621403718006558884600183948813767215792799562907446289380666695953836555910531968904234039747057614904959472363701543057189276442630752029869644344768920321067826095087476294979855780656914873901637161159570232468196797645667065107094423802521217108705053320334820886201691288819509688000609163232339404889953514536703121215053091478576757039120383578360317549865045564445291302836074407401803081755699714463212921647177647651966825373421255121750068184618557053492360555172192486647139412559301776222885016066209859524901502144629925104966000820231993608036773780738995684710676973864592712689684811303512472466958018667185048204302110724809070262367426176751074772080499433962046270649635206535972607166133268447575792374223919071967097338156345265094020736803632668610168803055117395470888150695532654653389612076909235862991631288083769262856255878882943381911015004967545497544656985671325982414054708274246353629349754289451305037122887769074149494870430060520044274672761954116854760921175810529670783264945103671141766618205245914888283861981308797786031553505751076849024982002026023833787448261781164475770240834778878165637190886455593375188483735859519012823620920871580202114609478315602533278609367027528454724852171798950853056799390871469467963565601476678347738881768377351070718840098249656500615320545159225374931736229120706445172960702520484130741060274497966463328470417202148271552022340064843765502416338588694190502327082996283255095858909628595537188021030291264739732903997902507929783735738585092754000640885899050972652101117732843134459875931396006893253309406754083568778233090642984271545094098046663372857153984610680884817220713784062192672007497657208869780835794646119723610240776156456276250305005531685670716569228915822077520704048891779192677728084591654350440341251002902281390068592572610648577016388056101949120820722388160994926878619054702526073067279001709827538029222938881022946056897938494800480857404043491360995208961924527222816867612301186286451172480726123139985247985791283365842237930788519895228735360870238369768223611868808534482755556813175357906791105073598062331269390991283092151703582405613923482730499249512720890630713795980908280991629902059077019753738758812785581738033457598506932993369720018978203678073084841882565067629859989763786558047903287113705264725111035634805182930889793449897457140541703427474837620509304466441398061959970353069765886091897286885744740678622875976708077808930230668321747837215967486960279209835565333337640869481103878663972857321981324431146144672820486936138935718710708075311044907228104218370292715300328446734508356052178335028891154429319868977483432505031220040537031271412599488431701070141036803400645043800350690737239669505200317658993738560654748732881872705727212398061592504391636671957105950535464711719541051220843252912148408306095105572090347303290254743148005456256435977586252533503424762495337372005100199052315241271683895974684448558877016365757152356215087442938892279918636796251617537107475939580229071059231360075093369568473029530710650118757913443568907453687799801224436884094902407194252135185817358383262369033135330686597993795254600871284704983288171028294547444642700312226463175654057704802819596986714909612231165867173857893362077285798137669855460549364897431390060460868036897527467715751537271982357771875189967811580573828652678947989095158650438614083707662245780986176346285255854967296105653724808160713947159369523609435136474060754786553247437101878831444907530437910703450437212520863776529569520723812570105902099038678531840595842488307902732321714495591911855519972575149723474623698251421099198591052983124046557413376482374798905925439764712219840867039523382379826643793116781448076132549854976705878733584512647121147839740732969859809945682162526619875259566367782196803599817322416238695831193327535587233981003068722963165315992694264768145059123427753535701998037002519872443701266811507763211012588564454744649839655838169173873451724250830045825003743420831756735244425975248182485505630544325152528989844238181423709561773070401034893076371932634762163214199343107276746845989646043357307588161123459755227567269285012839034007780744375126322993526832416851644067375645365613448769138795171991087043917764810363864800331822533505583524862028682068883463362846712163713912901138466562263711676722139086903068072227914192160575290804621490623754029236469299312485089247133662589061421841975827167392745982324426813705620566774082882847972777863413161822383127918288611505262182796834484826636323586617907461591064539997998502649813902231647548149951224364345175580089504706087934039572975482033448878868692253119176111913059419870827604257652187884033611547303334618868356640687108397193586086260485807953213320096340491730268631620781152303780150950792532930347410556623985695496478840867069742615807454899558740636327378492156896738417008707098554745584573349062985511419629165128434562839316522938657262549998802180366872839250785035396257174464991978489836878061275995522633745578716443721493829015100516223113516942259397656345663868615533799010712513774342833079057941029007737996066509159416810017854393690029039638095255394140489142791956382688378224271760704058156974180990547927906883273792164052632196504011264585308614059110129191261483501871064118603114876518657068482828175881766314303857326261554308419578764043777997910502436206072769719384491500431370748124634360741192318338365565480350687493284288987310604883909737978412452320879957268522676428266337362279959095120185720334189862413763783276236844647691069906002898260481402457784374896648788916443791709699842572201828599701998770274052908453985866437729697756471302366218798945125624323653972385009334845487622822547858758744730651213073303723748411747662065087877645682905783441302761062335615722783994799985293818830965277160002719716819852509288549522738315523490148739787250275857929452505899107351529490067303269807930650106273103052198401502644495501327507028453828545833938302000449255290366716932636385701438939067170391045703473462937607976149782973246104103667702070462531403820825056988090913660331431776919081456142156183967916460541298120727083100591159769129570278884208422855842358179202830042950053639367671999101795783384308665171537751883395611774632894259011195865370550751969944790753933304193180748738813636020170779992031255164943161296547041183920188244686429099343314450134972792160610932634079210841942192477024033531060182626213275249898835532565451284067983145783847691781506702306681789352625983101513390687776055399208337584430526109828486277844988129558336782551517493203047613028269450790252860953231925531547000637915740213443299131608771448209227062042069084536035907035352617962596737102390434639776230692764406810897996541474879135113493090341719803645315158576031798622213498949623188816726645819843829008070079122040638022128406959182366682648152237450353659729659416413432307208870119906328629276664433831151440922008331808482262009114588222867934121045054929108103726065462015133301444750427860702094190224042593495769756122199946655325610182304774362337153463950214469138961782248981982083303813889443050409059061204502653903746082938308123840252079582577085494570956960224355156136850875129144098668214576923863479033353476814438624263506378506584742070143484133675107352654447198297684212406312416513229246661808760355808317466521315609362159660619507634472925206108306366170749836074092982012453753952846125924013971893637530331848971290323684556481777730886738290960467362341432858236242546264966501026113855158974396521013573633012908690210923828719922834698644052082791480018175835588447789749094230761318512789338068260340650062929966854365084129299376172598245804664643604983958447379024866370381461483931245528228711970740558889675121742553963821590212093880331455951214363891812783427934312930929519009913394356470083274417682157430521854524996353290451290360857533373021138667006765840308076333025343218103114901320270906722405069634896379125850824233336467296650250364485492110920381761994037497497619445629918555452241276271765953915722107470652313873028582798440735824571024447973443545475158312938894429424890385718096393591996366480357464489605089725869495666191802705716552128231922507580349364930479416187237223501736358623532163415909233611193305592122016563741030216194156286157620121904523540575486993882233143488205990390785533973583276431415935804190871075437813080074621878171407199691105344059171775926047882900115240416812341554586400638840213686957571301733615651386197854927084523716921630557886098365651528238497039455681875299935329908272297066731216419239316183121413021877303388762958645645104037546749871420178367253452554458251238405316574375496895075600183211396866062693904527767043195510649428153537483632716710992899895091881366374187799422497825381305233967804898328437710826941345061113936143874805054013571985274920426536198321818012300201371127989323101838690410309668425604404666612833161547271210323304280059686613374548578951974819625252330533645226208452485870647276628396407253671184759623631199460070226938412287622764222521160971595589537927896200299870348311470288586824197596402935281321950501303322299136019707530658082878854835298440318972318620675762800757530389466671837492299292760495586433978050608776855812105467061956613871655849024381057306415775803884343297149019068040583641627571796329696747881625042363462032607075706117383921348320451183551192596502920140158087922664698289831091162272901557515407394083414541845602402765276856579132506263586071227430154632691192412852716297488601405420764065697887410685060050069891542213365088164186041785419725315273082095138928695064192037657634367967251061330478788649638886180697065286660486845545985796428925226932811053965094561352252687678339559647559847417396845261730509743091228001451067546362895160320129759323208614210361279746880394032361305072624935031772936248308266806405156633450714189020735214470351651574424079226341698803173497579341002782038859209195007543054970672609897747613447061648423401995347667589990363033463924708664092510861039679872849708235902161603207103008047549806983353516614678447144814198994911207709282100930265749677646994725830320797268003862532732521276944368001274565642243738598639535084223713650151459328493508129525026737439264885229848143427695326283511937038348520430929370977527111162588511503289224581940380092567384507203510450460424486192541452158557073760807298280424777185722496500971983287692485555518901392217479301727123545678685465773693585342106697257030637648260633971889586454815901508110252921513195214789946431892868984116248630261375276564656401983031041880107885365040601951313002034223301612746143573765768513022140548858894671733465953347419512126435200397872452436027313616174073668050539458267378283974833201892211911342119740191091661836905037991227657391496223089516743997121538135054774594576744832541505138384680024055661769523271800830767775098323855113741324443249303023433898040636461149397788902657530969878224943907869787687741704181672174010324307209493946422421400380520922838782420657398110375522913383415106910519202654832052868271910754657216978267993276503822283866478088833441516298517606279686136634263908164794948788580119997205675771978943584652535333426534348945532985302555684815628326256692670331902699132844579896767352893459004355393440310610959448404283769322313450853152504373285348085040289015860190555965861893760321787252025111730184741966764461839267626639180323527077189240058224163700396318995038957815386476016431872242729986155580832260134874940117671005111705754969433484481934280032539219956043329766109971078221663480220702247993624949268863004791458414592966600746539997965609562599967672189354635209683429947820726468681808348659177345712983187425184682400163454254158264855055971443968912156831630701849968306828421480742439345784413560664132327973290231218764632996923276296224868150198895275838655220202872092857533582516464949482528571524854725406924583941171190624181587298341145693943368601729307685863139717068142163309074023896811820500696270288258687596110435802199088218127772850388030002300137258114184871722154316700043385187383982683335788409306659263975466189530967572442365795396808936495672462354054400158815572477992338560593141442801636589323273892674495844443162646314267273537553974966086277697218056041100200512755563542945769018231054837149293431478213946030720651714359818592762984799455127657534411513424805145995155386603733928382538834212208697736657655948826555189262948396348611751555970910183398575770832084720943401885621607476457950979201472578424006260647908105875018529731955875038184631973130390153476383734495585633678605564875738496816535222554463134664386928160971379844867134305141621011187839576990451965541462038615701344280027317700047389909731803566874239270539138109865628969155764065015864977360420807591651247970221784630192462376160493999394724678509404531817368636160451573333074466841413834674821964773390116715420648860267502764593112958597048580276840727265815264212817571904549832622496941689835127151307175222583834179245973073566376405916968105924353145519904581567761369971493212585147841115252983499433900964877191738456366190842412945236594988100738804578513822429790717607075658950255523778147141366550632097839372491567887481861947937703155008298223779570223903112723172320582798515969791087536260789489633395441137608182980932084971759190058688315017244546803930229249699745615085990394609727036930734013095639262325063742644406765633922546022883525134786778951254780037331700310464162039374262631926205847188132217005768920561009820085498318692950997215831652914299963301377827464661533139212592425667881192182393000044729410516075057063115052947102451234486762071102982707466683714062502284560802086385231419906511434586298059503072198797341644393780285245272796364068546896908832293459135697186037297744856921099123518387753645242038669033759265769119902330750664284453878447138073067566923259310341135849662711926959041135446675940179731358122924872562829221742363355976910796014072633864326404085703872304746243881919015680421840927524014512558799658369807396582021938751808800300216274378960175832181740460452069341007722892963348285388883096143574959490050383425611377478492158745061702307096726361479894960728343898018897080815364253743369051449171476426354833489166842762710583878958603233514795185698907030310938933187132669868274799711347365147852160320338851624190556817481387631378389407080859548217928236230054271074917942325571365613388852507087868352033676383825681110847044010561118060804064971785344234346934992199031189742490330417982859838907907380094951124629043870398542459670500919017555835855751921140890823867657159481626632037244014683485390662763908388252482998332215605763997168955304808800805420702699303434657086677421770855598688295084960535082503455759586099411685392907497374804440232255497978200085206912043642363999114860947148505546259489090571840231279097661641356816132648518045777569105927229558864691561757816554377199746941220851799242208589735657987350943248955508496893416391380555035822671925020441252641714827355394284448911723614536757500570558008177639369360841903309884666368545019315384339619007561023972769003698739065799108143840032095632664337027750856791219833459365205317966083166675014289713122200861142877614698045956553599648215711017100285135418659401704329843504284575543110857655908007286450557614241671659784930317695262925898134003435304490993525260645257713804046375648686256978791691831707663732284454618779096947629097402564341214228995255994009107008345144460060182727239818846815378352354220953526264612179854263178282593784329973631593331772562711736468818510055753405478316920196742176481086377282458513882203994039482908890573014545226092324129857024400123942167040236282423398775377859301084111147630173708240255032284954571949320920810463453822932748123574023210614435763424407580523431899788039437896577129735065499502324300044520374653658790510813725195290741511401925399195607452846226337330399512823411867145708697669330807343074133379956597778585346179186376918806368043562015845036116684028690437257186725432260487853060803785517192929316433813326064218236581641176423864125762592944966125073989980687414908041487270183151617927900507164380822018126679917473836978566154422698689685006119453584593315339208350663384563490744466071850507192729561980806792323728681434520007391909869331955524063427669896353507654033529092362969066715804619036460406966695597188919393116932667695909235261520886813236067691067925997806705052953768216884895154689198970946783868649264227071688574233398144129167211959767178191731318017139975903815382767041733003590083276846378934944326999838991242297330346808665169041733773043871991050283820347875774891621552149250207497986592790436716952883250609724851760119552618035421906843737441445138194700290119422095995651907571620995432956804677590538258416755056411121737350439794790116498705738521523939668986432416610794464649735090133511367195023797599969854563296128289589888353725544282987829802287143256204455145587329640391735333509326387820483010707796225334499129394361413519596851031302959236568932193729435946818501753660276393961118634745383210611562235648481063506359910700940927360834213021468077951729880677113056584849922459348147350145100802140233465318309907216643509678429695897766910609436846938798624945401336635739133299326269851435175892807049411041266965039608492953889690474453985819712146544898884575331968052471668216951477388197326533469262670132580873609930768593361550013145943649671559760845845337918039146314825604794823461286829396675424960894178377239219122596901873472463613210477431391334907114633547909998651717131629395739639000505387219005650899618306263305699305249463357960939886807017340856670978126524304767978262139179661212487140959543197410561222057471385164617673363626601487907029116975457743492351225482153191941583623946807910803312633526631861581304920118321919706981454022319827537577300594927970187065330633562320459850335653315374097627964837276702545373432885928253039986666156309052626346473525983544406143590871995732069257465109626246586553922284771678052398515386265176923595249420862815314372287356805585045219146169149044234490102141322436755811390325231132105575019718070628502153355791250051143675103760493601870100793262275746436052602755266131252741678369572842306808691205362800230160595474542633325707103159172232393336445150194644449903654180076193486375581572162795495662893010530878844375757444652113020135076512711765509419127088629714110646078371523904522693954417443900357053652115810662312278951146487225388470078539100683167804242198887517041046392824600638916930838170252311345790311984493055930613196332571988478271058061153627037883885399820981984550962933005055989110180232612862257097941562248328148520861729695074428497092190214705140410922068456417718742619756106690325031073913402153543253600289099600772808981321570594165162508721859582694223983387514270256501663088273022769885874574484205420950539951368147426750435341811847419537315623405592119541222242723447148647244449348528783584614297889176470027407883357114533510178160581715026795913486557950475051845707989469494016377541870878376943650738046145383746084053652902512759249742480575221880086794683760342718431372159995263496462506829271787173600824198965475619014528862800469394716965414603017924519600605689365640131436266369534484548705274757385303987075895020223625606186777645626982979873271059381364186385537986486884521202078993853105204443008822648694627959459022796366801211888139804103684319620043319386648610990056420185390947896872958681870484781759837535937778267248309358551396205181218879257652456922197434194395575059587400163469791112237791913129238427918793827202011134984842595143614153878778310918568197780160088141058431379420374631872494577538093474383166674663426170242709503762286483169418207715454095615916587702932551508588213155619970040282631506614253733928149907260856831115768637820025195254335124565495189610306709314407113479742931435566808474574147020858114185931833586584781743662224308971672042470410193506488904136166775764321377642587662831454445813785696850076277554688511410093659818322192711656596874461380101022275823426317571513763083118425746016288681121686534410247887788786022553652270474479726652140562201675316944333725613489979242832376661683702733685797744713789681058195134981045678465681043951519236196171903099573637687453801554887896640074263548285275951100617329433703626999156955207899592427301001974994174528964535135687360335000126169905793374336298993950281715365286132228818104181863896705682157842480391483707992244522309370648263034334238567356537746958940445997731427214268618087333819069033016219263097546674722554728424422450455913528606068717465518283059383056549886297939153101998434658232003131751793868632103846993641272792906114886366581569785029084231766636807107672501546020411452551423705329266433103519687457714202952467216088714189904572343563440370539702764985468370584767951291618941164437505114899401020430765221359487860991766829683725476110795359859823147826170664343238312448381724949602640875796640403268315749032014224011899925138806505431749063135636220402806801919619233138514087547330312926236736434212843909412880487116470288255743013401768935977887321570159901500858740328544575651369243952159111812076224373724294679458187541837404115629565731937615743797133848325823881561318634000979116132438736801598998724857656794099524788196395972059935287789754553588870300519947222423235467753141060776546759992313351549025445324432592296124764297910160905009964346949442609714089856066628674674834961103948903596172042974023910727239987928820502501329884826045211016807832992031815749185485420110406617227248016876359595492285115842733371188785620950607541810312949796945698009889166490285983306163943562767150837798457736496569664073601342454345372259868240639874685409996554219193506709205263659257232428239089740538079558975117767636562040247467927549964818273263348204996098562165981203543883946936999637964011961405122414798771567337866469656836583845795900910519081483274690582364458312589149554849052972139928333195720501187582119890330244692135011885288613295112990765311219255318757084945725027453091902930044361932207517958804606848598205551330763910890243739242349567462769593540932601965874601061434665712633104276481911777897590337112487541900876845562985384128678652391356630409695259111627180906624246470520552231785428656667723518509868146286876254071352500710553625613030027318865985759118155386926575767071885120616628137052791898063770742596483299176017281980597081095052073648707773655003119020946977900636800653591049400414178710973535922860625796704065453683727310053579092419695307361489329844125370699782321224332277869541724394202555800977875251053645741287382405742686322177720604211249746539380525195846800705555361416073327557374428740452542549445758108144266395114983079305994095142477108486977412856205472955906746245320777100988074942748508665775058079219671017664382272980459140741233798266269719738622617999824250192760354897765771403959613150232287421216706374792981531885755177179781925816963308127667391356419974920974854312646342834779155740458229909347551680353293199095819780813150771100303759185982324547624820662170132138531337122361817579312470431584694001953860899432373629637675413699932669784693495770539723990069827937551029579817153407725807618439301439193223032611918012227257467001599340721347702090578331286116658276645076023086699335516330901874928557785041465581120089837732122428332245896442791648973342403521836814785543378498979961227863572619215666195592899447708885993369925212912932622141395636941472447106907427281801890963327912538419026039755754605687329947391505008434005970235200123858712564648352481416523128106095841339135347989100011322045635089787399560677480036450594234200421544435272460866126548645414808455413609990797755676927076328877577806029239603829355068924285108914918265302743228314286142306347263819345620963748901983385062385599528247816699742831031352798242563224942937790933886496381099727161386151752682966147749633780651745831547974082636804200787356700251962689194722965455513882581130384378035348661987166130677055524863143989259788262016551821489615867822828593154804300147983185983788695684801988652095028064837521572775359886370146008445593190499646369144130670601385746484613704706952850868918767169391175861141156307535594372051292092014780784517415799397141710050067623724763027095809511326653844722014021928641412748622167400636456002603656165718550629910360628322324518323464661557971023132354865020914573442962432557214413166908960647134063594463084898108332077187788337980578060430427885730053887727694503017989777419430613631798187698051542368784957459049540089864901953147651468251159063640028385047213723625504660835477104934721434084065026745225031669811006607317215946114311468300026786502812114731300675272678650080733676792558307245924278078302768360579771326045680966965193152692682443473275668385522839806297969082471839651719444487866051378751504316317851825715569224409619729789430110938175645644213354719693678620866453321932708451024545671310866480076048606283664569187212180807380999078466281441180398178212780520173967042944309962733742244299930391165027644890517356899140115400833921361415334602803762201922696195855925133866468528002556324597267231023370845853273806604331697969533889360812782095633850722046701424087908616772524392951489589774369494103829852652193846892485218329473541099641543856697845974771423347021259353684696942192132018745459032150352384236942066273380169475008936829813428036377991263153914932150039436155270127094029299173666240483858590176007869842698475742021226929533654570263268702954013123373355778628116496405523693313269845895505667390482730316403405887408431368648880907341984729386551967968221874836001805352599970249370287088960037226740710301407584158875046971459076539970115860726870512461321506426216220759365135707496553112801202307900833151332894187369792335590675667249324561151731328144641331589934895138991481391430697511118780250027829627477909689477154318781848698851043496292100611949912639492301652900207988135525551939983984716163067275575649152680075826239988382588445693867468582354287120706432670783753016541507536175022087595206246707332582291672469720219903217787613543216759021887187066683372131872014327881826009737729363347819571758589221843831737929316688984406052541429548339312617576409289733923010618230420332991450582540781408200593565803058572077739207147320223626178749509895807318583922246592740414059968060806860574155207228903506843477709101781234939089716596348411708570324104184900369089070656445842529461614753250470218462690297680864830426933640115065521545510083404316287218015356459192538436002749887863622434016922233663961503426347553347584418238829232709943778792724361857661430939092055879369624927850346922666937126021317988679596804697483808365602655957579582633789305815294236197824290785992574167078605728484120759769844676463716857880304959944722418105742554150852229459358170322548710624881039115511009670567935400584151028260199240751626580997551368793627082342643144268455426660968506673682394882405804625358562788305391522509083522303057016965157655113810467356263137819813165732599729680817793222817914999628577797725936494484937949296430690562660603115506375912471910458447361223710457826330343392553485936513705173730886540576066659338167395480885206182376638215672498515241753062414564623834051188398126807847985679203450055770124367926151768580173471350599778956641632744861074459479059733103913168221311816307800920368072268592532549704187481852120507565182428536161394407199023135717096391474953144399379614135527364232634668033303045702410098089523518940438832467096130385019214293448209466484754679314653333780303220264625433548978699477301008553547395436634813865236262369791618235665821976953088844674179769042690899310450674252578182745780830676889168517158016059296963306935867663894091076421074861152135224975934818799599951610638895104223112634556014297885315693136325078783469149448776658210657240740509922519210155211218026200107255884613131452065565326396189618110831004118572279140619215953211426698399054608430872238244677859763481719166087910738718307939793897127856430889795465537511647687053041271508381601674328364039624416624443478178967071383139741502914734386842728785381387916103117739067172770212344734842979618379510658057621643637382688531106470670757684184292239830809410190698041972874820215373419819325158131365501928823112732023676705086497925885053020958102096763829201345788905916367619579595903921143899199479424896491639635215451504443755901671216520004235454114032314809808542989130941812331223557462786885567677229059485086240834780775913946777096664303197004262540416345247258033450487856355237764058737606150881852446074162047043491798352429107414084163936171424997520876468488480970329510016219201784088910649586418792572877934983576410872032278379777459448522694546330221090289002223934632669981682091733976817692540703206226634043933837273278558420419718656507451580078699896854172977711242917261489727479299609906658081085862001919049422365121581110461553763896227453410117231377606861770624364038181982948970802809399053745369151201141665645957093367115564956914125199400829079378881187923983111170687153536996977930003014853970554509482399827656245922761530792848927613211287913446038171035416823636960358872921393241058668106811106793240926355651748090996999165909821242045175396200007457642070096032595290905058253259507141240644785522881892160013205416149473760311434741239229203436693442533779588652379768846460505673926737899125929176199157117868247433774416984250798600542025790605225165565561350867486263866641960453302577175417660484362979821512303786622841528476369927322057341154154586446651162135032860726023465311387295141291793108948693736330214154618563902345414075054434164453945258501369962706335774401510056800390715634467783118701441921549816422863280548901076626641401278468712263166703157378614013975252721366425314757304583889464316284093702652573832383852429563641893748860034052055974100781136957371450369181535544237709709156116733793935898913506900637919912190837030108278836480609891336815620924743405805731981630142889514978786056169535636582466320030514784136923265502798380994748270898558566951332525579446581973453698260100404702471948761414278462251637120838301243506116084422121189688654204707980349722327549456263880960718492109301860989846261747182023215257755356987267825852157502939176365352583697513276834398362879383278983883002767935360471164593507654174943584793618755208705549298230426564167056344037920738296140563275622810770606849263204817703065696521263921499613993403245686397873128900525504550529573833120761883062014129811315413025612312231882962391558083772325746581832183412408088262348246084242548898785372248971746967388198100552665280396957859968157479593665497593313363429006975389060838317722582401684060878965888483901036508216014827568270023035594954465307608515519390396411068687720678685597677792009474498820336034000854371963646890263653088618821161434102482099487720684153908792050298610907644637060459438246136406851778252790705892460169172661491576087708667074938254535640941624664666657719819541648185627313960962990377420829249337221146471321025054315013985067746634468466415209216281830984236590125361541477478466116141392695112781128448994738381677741109274902095655700156120877838607510569454645235321454345886851948185164285853707174934053128717170941943001328214477945019984824217733921782625291240991407904225412968559180299294558391079467293864218523745081090439154206062892392440858747779670889036336518252662290969019094549200803171647601191657703232850014018736090347711058945768743157718955153522340658093537447037938066510630988021126226230082092726860647105896595782817846081948513525264223494507316865819694735237018103740098402941777310512605910645059854347341091748410959625899128709686244134156253555807927663861726021764682253266649803186718865867514903976080915448167839444971241993235504633405213440841992931437316996883567375259430836882967296018477954730532631407989356727888824031251480217670320224115793192919693503732498232596264572558808388288489566963183195148679725765323020005936425355679560760693927552723411454568948318715885741020810605860460534531871796832922777641728354806270460907588458732768496996701969966779234222002471315785591000758339866175509115533133911051734296129019727372779082762325799663752371646430220056622002676333014345491487254361420388410206778758104931470935085925254639260652427344193188243931502940051306650226926841721032990731444961185295351181565222634065786920202320719263531527166774744742272720973655991680653414980474661464251648967346308978848178178491811068294398357207703313447747439687852310773684760235641130309503434722258285150074664981918609503712076339210514050729104189637740864292029306654531810829595462590091857645758170256741985883582162173481117164277555424276202047999652735485027001917905497582092081018691320283179171471300352082836056202913061356403287102087804083482313152214257144416647907926326674631831622031973961482003079330606674148082639782540275867825841499854716682740403326474797624070712909701759535777869746801395547192233278330828307574918667807343032957885290474648330836709944485304351819586574661981631069113889032939825366969413959062553242030118327248803166926220806082923559654245680816769690493967161840618121995408888958826664086678277096751656672869273121375558105386128107803688750623089540323063486633623893237781570559153734969322478752119833083596179257962503758601221134598158295755306473559097964858590281090687872558772142518105554539822731101640765419474283057112388211581500299504636215765155958233170137634453627107472713251136727389065450286282050236971311237052291038073910222822176437773779871143190235010625510920813843942310871938129186059339348808212015594313905606824835202142311554634785844389620477746816724295695341130239203130212896151421698252002655479992624163

https://ideone.com/4a3zE8

language:

C (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language