QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666488#9518. 观虫我 (旧版数据)ningago100 ✓6058ms541404kbC++145.4kb2024-10-22 18:45:082024-10-22 18:45:11

Judging History

你现在查看的是测评时间为 2024-10-22 18:45:11 的历史记录

  • [2024-10-22 21:24:23]
  • 管理员手动重测本题所有提交记录
  • 测评结果:100
  • 用时:6706ms
  • 内存:541212kb
  • [2024-10-22 18:45:11]
  • 评测
  • 测评结果:100
  • 用时:6058ms
  • 内存:541404kb
  • [2024-10-22 18:45:08]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <cctype>
#include <set>
#include <ctime>
#include <random>

namespace uvu
{
// #define LOCAL ____________DONT_DEFINE_ME____________
#define ll long long
#define inf 0x3f3f3f3f
// #define int long long
// #define inf 0x3f3f3f3f3f3f3f3fll
#define infll 0x3f3f3f3f3f3f3f3fll
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define gline debug("now is #%d\n", __LINE__)
#define pii std::pair <int, int>
#define mkp std::make_pair
#define fi first
#define se second
char _ST_;
const int BUFSIZE = (1 << 20);
char ibuf[BUFSIZE], *iS = ibuf, *iT = ibuf;
char obuf[BUFSIZE], *oS = obuf, *oT = obuf + BUFSIZE;
char getc()
{
#ifdef LOCAL
	return getchar();
#else
	if(iS == iT) iT = (iS = ibuf) + fread(ibuf, 1, BUFSIZE, stdin);
	return iS == iT ? EOF : *iS++;
#endif
#define getchar ERR
}

void Flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; }
struct Flusher { ~Flusher(){ Flush(); } }iamflusher;

void putc(char c)
{
#ifdef LOCAL
	putchar(c);
#else
	*oS++ = c;
	if(oS == oT) Flush();
#endif
#define putchar ERR
}

template <typename T = int> T read()
{
	T x = 0, f = 1; char c = getc();
	for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
	for(;  isdigit(c); c = getc()) x = (x << 3) + (x << 1) + (c ^ 48);
	return x * f;
}

template <typename T> void print(T x, char c)
{
static int sta[BUFSIZE], top;
	top = 0;
	if(x < 0) putc('-'), x = -x;
	if(!x) sta[top = 1] = 0;
	for(; x; x /= 10) sta[++top] = x % 10;
	for(; top; ) putc(sta[top--] ^ 48);
	if(c) putc(c);
}

int readstr(char *s, int base)
{
	int idx = base - 1; char c = getc();
	for(; !(isdigit(c) || isalpha(c) || c == '?' || c == '!'); c = getc());
	for(;   isdigit(c) || isalpha(c) || c == '?' || c == '!' ; c = getc()) s[++idx] = c;
	return idx - base + 1;
}

void printf(const char *s) { for(; *s; s++) putc(*s); }
template <typename T, typename ... Args>
void printf(const char *s, T x, Args ... rest)
{
	for(; *s; s++)
	{
		if(*s != '%') { putc(*s); continue; }
		s++; if(*s == 'd') print(x, 0);
		else if(*s == 'c') putc(x);
		printf(s + 1, rest ...);
		return;
	}
}

template <typename T> void ckmax(T &x, T y) { x = x > y ? x : y; }
template <typename T> void ckmin(T &x, T y) { x = x < y ? x : y; }
#define mod 998244353
// #define mod 1000000007
int sm(int x) { return x >= mod ? x - mod : x; }
void plus_(int &x, int y) { x = sm(x + y); }
void mul_(int &x, int y) { x = 1ll * x * y % mod; }
int ksm(int a, int b) { int res = 1; for(; b; b >>= 1, mul_(a, a)) if(b & 1) mul_(res, a); return res; }

#define N 1000010
int n, m;
#define ui unsigned int
#define ull unsigned long long
#define u128 __uint128_t
int op[100], op_[100];
ll mn;
std::mt19937 rnd('x' + 'i' + 'n' + 'y' + 'u' + 'e');
int x_[N]; ui y_[N]; char str[N];
u128 tag[1 << 26];
u128 pos[1 << 7][1 << 7];
// int tot = 0;

void change(ui base, ui S)
{
	// printf("change %d %d\n", base, S);
	ui U = S >> 7;
	// debug("pp = %d\n", 1 << __builtin_popcount(U));
	for(ui T = U; ;T = (T - 1) & U)
	{
		// tot++;
		tag[T | (base >> 7)] ^= pos[base & 127][S & 127];
		if(!T) break;
	}
}

int query(ui base, ui S)
{
	// printf("query %d %d\n", base, S);
	u128 ans = 0;
	ui U = S >> 7;
	// debug("pp = %d\n", 1 << __builtin_popcount(U));
	for(ui T = U; ;T = (T - 1) & U)
	{
		// tot++;
		ans ^= tag[T | (base >> 7)] & pos[base & 127][S & 127];
		if(!T) break;
	}
	return __builtin_parityll(ans >> 64) ^ __builtin_parityll(ans & ((ull)-1));
}

void solve()
{
	// memset(h, idx = -1, sizeof(h));
	n = read(), m = read();
	for(int i = 1; i <= m; i++) readstr(str, 0), x_[i] = (str[0] == '?'), y_[i] = read<ui>();
	mn = infll; ui full = -1;
	for(int _ = 1; _ <= 10; _++)
	{
		for(int i = 0; i < n; i++) op[i] = rnd() % 3;
		ui A = 0, B = 0, C = 0; ll now = 0;
		for(int i = 6; i < n; i++) if(op[i] == 0) A |= (1u << i);
		for(int i = 6; i < n; i++) if(op[i] == 1) B |= (1u << i);
		for(int i = 6; i < n; i++) if(op[i] == 2) C |= (1u << i);
		for(int i = 1; i <= m; i++)
		{
			if(!x_[i]) now += 1ll << (__builtin_popcount(B & (full ^ y_[i])) + __builtin_popcount(C & y_[i]));
			else       now += 1ll << (__builtin_popcount(A & y_[i]) + __builtin_popcount(C & (full ^ y_[i])));
		}
		if(now < mn) 
		{
			mn = now;
			for(int i = 0; i < n; i++) op_[i] = op[i];
		}
	}
	for(int i = 0; i < n; i++) op[i] = op_[i];
	ui A = 0, B = 0, C = 0;
	for(int i = 0; i < n; i++) if(op[i] == 0) A |= (1u << i);
	for(int i = 0; i < n; i++) if(op[i] == 1) B |= (1u << i);
	for(int i = 0; i < n; i++) if(op[i] == 2) C |= (1u << i);
	for(int i = 1; i <= m; i++)
	{
		if(!x_[i]) change(y_[i] ^ (C & y_[i]), (B & (full ^ y_[i])) | (C & y_[i]));
		else putc(query(y_[i] ^ (A & y_[i]) ^ (C & y_[i]), (A & y_[i]) | (C & (full ^ y_[i]))) + '0'), putc('\n');
	}
}

void init()
{
	for(int S = 0; S < (1 << 7); S++) for(int T = 0; T < (1 << 7); T++)
	{
		for(int U = T; ; U = (U - 1) & T)
		{
			pos[S][T] |= ((u128)1) << (S | U);
			if(!U) break;
		}
	}
}

char _ED_;

void mian()
{
	debug("%.3f MB\n", abs(&_ST_ - &_ED_) / 1024.0 / 1024);
	init();
	for(int T = 1; T; solve(), T--);
}

#ifdef int
	#undef int
#endif
}

int main()
{
	// freopen("subset.in", "r", stdin);
	// freopen("subset.out", "w", stdout);
	uvu::mian(); return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 274ms
memory: 16948kb

input:

24 1000000
! 9475137
! 4501536
? 14277831
? 16695039
? 5723102
? 6093887
? 3014539
! 475969
? 12500973
! 8750136
? 15617895
! 4589313
! 152300
? 3612579
? 15248179
! 764162
! 4461105
? 7274495
? 13299697
! 8388872
? 13490383
! 3875594
! 9439685
? 16776189
! 6443172
? 13864879
! 395691
? 7142271
? 16...

output:

1
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
1
1
1
0
0
1
1
0
0
1
0
0
0
1
1
0
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
0
0
0
1
0
1
1
0
1
1
0
0
0
0
1
1
0
0
1
1
0
1
0
0
0
0
0
0
1
1
1
1
1
0
1
0
0
0
0
0
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
0
0
0
1
1
0
...

result:

ok Accepted.

Test #2:

score: 20
Accepted
time: 157ms
memory: 15828kb

input:

24 1000000
! 0
? 16777215
! 0
! 0
! 262144
? 16777215
? 16777215
? 15728639
! 0
? 16777215
? 16777215
! 16384
? 16777211
! 0
? 16777215
! 0
! 0
? 16760831
! 0
! 0
? 16777215
! 0
? 16777215
! 0
? 16777215
! 0
? 16777215
? 16777215
! 0
! 0
? 16777215
? 16777215
? 16777215
? 16777215
! 32768
? 16777215...

output:

1
0
0
0
1
1
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
0
0
1
0
0
0
1
0
0
1
0
1
0
0
1
1
1
1
1
1
0
1
1
0
0
1
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
0
0
1
0
1
0
0
0
0
0
1
0
0
1
0
1
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
0
1
0
1
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
1
1
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
...

result:

ok Accepted.

Test #3:

score: 20
Accepted
time: 185ms
memory: 18592kb

input:

24 1000000
! 197632
! 1075232
? 16775167
! 65792
? 16777147
? 8388575
? 16252927
? 15825369
? 16775135
! 4194304
! 552
? 16775871
? 8125439
? 16252667
? 16768703
? 7864319
? 16773113
! 4722688
! 1048760
! 1028
? 16576484
! 2136320
? 16776703
? 16707039
? 12580831
! 100
? 16776191
! 17476
? 16773119
...

output:

1
1
0
1
1
0
1
0
0
1
1
1
1
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
1
1
1
0
1
0
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
0
1
1
0
1
0
1
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
0
0
1
0
1
1
1
0
1
0
0
...

result:

ok Accepted.

Test #4:

score: 20
Accepted
time: 307ms
memory: 17104kb

input:

24 1000000
! 6820106
! 443659
! 3080
? 525571
! 377345
? 5504934
! 13641450
? 12039421
! 12866772
? 14514068
! 6489651
? 2882394
? 15728506
? 1559551
! 11885066
! 15575062
! 13885663
! 4246041
? 12441078
? 16742263
! 8407354
? 16773116
! 739912
? 14397343
? 8220285
? 15727728
? 3146756
? 14536632
? ...

output:

0
0
0
0
0
0
1
0
1
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
0
0
0
0
1
0
1
1
1
1
0
0
0
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
0
0
0
1
0
0
1
1
0
1
1
1
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
1
1
0
1
1
1
1
1
0
1
1
0
1
1
0
0
1
0
1
1
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
1
1
0
0
...

result:

ok Accepted.

Test #5:

score: 20
Accepted
time: 272ms
memory: 18928kb

input:

24 1000000
! 131592
? 15728123
! 544
? 11780584
? 10477567
! 256
! 1032
? 15728638
? 16777207
? 15717887
! 8358425
! 0
! 237735
? 12582399
? 15777814
! 2240422
? 3878186
? 16777215
! 48
! 10322848
! 7758449
! 4994634
? 6696114
? 16760828
! 6295624
! 5329776
! 69648
! 0
! 6276117
! 9364500
! 11781556...

output:

0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
0
0
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
0
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
0
1
0
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
0
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
0
1
1
0
1
...

result:

ok Accepted.

Test #6:

score: 20
Accepted
time: 250ms
memory: 17440kb

input:

24 1000000
! 10467318
! 16738876
! 2
! 0
! 16384
! 4194562
! 8204
? 18603
? 12862536
! 49
! 132168
! 6213595
! 16220133
? 12582863
? 680960
! 9441304
! 64
! 4195328
! 4194304
? 12617956
! 5369125
? 16072703
? 4915492
? 10729472
? 11067810
! 32
? 16777085
? 16711677
? 16774655
! 16334796
? 3121151
! ...

output:

1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
0
0
0
1
0
1
1
1
1
1
0
1
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
0
1
1
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
0
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
0
1
1
1
1
0
1
0
1
0
0
0
0
0
1
1
1
1
1
1
1
1
0
...

result:

ok Accepted.

Test #7:

score: 20
Accepted
time: 232ms
memory: 18924kb

input:

24 1000000
! 16773119
! 16515007
? 32
? 14647295
! 65536
! 16773117
? 12582895
! 12582879
? 16744447
? 9907711
! 8405120
? 16244446
! 256
! 393217
? 16711167
! 66048
? 16302047
! 1179648
! 199680
? 16777211
? 16773117
? 8126463
? 16777215
! 512
? 16777135
? 0
! 8192
! 8257535
? 1
! 4
! 16744187
? 21...

output:

0
0
1
1
1
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
1
1
0
1
1
1
1
1
0
0
1
1
1
0
0
0
1
1
1
1
0
1
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
1
0
1
0
0
0
0
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
0
1
1
0
1
0
1
1
1
1
0
1
1
0
0
1
1
0
1
0
0
0
0
1
1
0
1
0
1
0
1
0
0
1
1
1
0
1
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
1
0
1
1
0
1
1
0
...

result:

ok Accepted.

Test #8:

score: 20
Accepted
time: 238ms
memory: 16956kb

input:

24 1000000
! 16764936
? 16776419
? 16775574
! 3182592
? 16773120
? 16775168
? 16775459
! 5369856
! 2310660
! 10965249
? 16758952
? 16776921
? 16642080
! 16773128
! 835717
? 16766163
? 16234302
! 11759872
? 5108382
? 16773120
! 16773120
? 16776864
! 8450048
! 6909952
! 16773120
! 15298560
! 16758762
...

output:

0
0
1
1
1
1
1
0
1
1
0
0
1
1
1
0
0
0
1
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
0
1
1
0
1
0
1
1
1
1
1
0
0
0
1
1
0
1
0
1
1
0
1
0
1
1
0
0
0
0
1
0
0
0
1
0
1
1
1
1
1
1
1
1
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
0
1
1
0
1
1
0
0
0
1
1
1
0
0
1
1
1
1
1
1
...

result:

ok Accepted.

Test #9:

score: 20
Accepted
time: 226ms
memory: 17280kb

input:

24 1000000
! 2084864
? 16743423
! 2375680
? 8323006
? 16777199
! 1052676
! 8192
! 9675264
! 13045904
? 16776639
? 16710836
? 0
? 16251250
? 16768646
! 14974976
? 16776000
? 16775832
? 15728320
? 16217979
! 2101248
? 16777215
! 4128768
! 2080768
! 14213120
! 16285824
? 16668655
? 16776188
! 6037508
?...

output:

0
1
0
1
1
0
0
1
1
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
1
1
0
1
1
1
1
1
0
1
0
1
0
0
0
0
1
1
0
1
1
0
1
0
0
1
1
0
0
0
0
1
1
1
1
1
0
1
1
1
1
0
1
1
0
1
1
1
0
1
1
1
0
1
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
1
0
0
...

result:

ok Accepted.

Test #10:

score: 20
Accepted
time: 255ms
memory: 18584kb

input:

24 1000000
! 1204808
! 5230471
? 295200
! 16709503
? 427666
? 0
! 1376552
! 4728839
! 262272
? 13408158
? 14352383
! 11955895
! 16515067
? 16777215
! 65569
! 5855981
? 11352945
! 16314879
? 1909256
! 16375558
! 3185312
? 11836419
! 9433711
? 2036849
! 4202562
! 8192
! 16777215
? 2056884
? 8421401
! ...

output:

0
0
0
1
0
0
1
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
0
0
0
1
0
0
0
1
0
1
1
0
1
0
0
1
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
0
...

result:

ok Accepted.

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 392ms
memory: 24736kb

input:

26 1000000
! 18006034
? 66957270
! 2133064
! 147618
! 34621442
? 49715575
? 62879287
! 18620682
? 67073751
! 62941186
! 7634532
? 67100031
? 12517237
! 4804997
? 65991126
! 138275
? 65722687
? 66043391
! 19147234
? 45743743
! 2242648
! 44378336
? 48226020
! 34341926
! 665045
? 55433083
! 5554254
? 4...

output:

0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
0
0
0
1
1
0
1
1
1
0
1
1
1
0
1
0
1
1
0
0
0
0
1
1
0
0
1
0
1
0
0
1
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
1
0
0
0
0
1
0
1
0
1
1
0
0
1
0
1
1
0
0
0
1
0
1
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
1
1
0
1
1
1
0
1
...

result:

ok Accepted.

Test #12:

score: 20
Accepted
time: 172ms
memory: 18256kb

input:

26 1000000
! 0
! 16779264
! 4
? 67092479
? 67108863
! 1048832
! 0
? 67108863
? 67108863
? 67108863
? 67108863
! 0
! 0
! 0
? 67108863
! 2048
? 67108863
! 0
? 66584575
! 8192
! 0
? 67108863
? 67108863
! 0
! 0
? 67092479
? 67108863
! 0
? 67108863
? 67108863
? 67108863
? 67108863
? 67108863
! 0
? 671088...

output:

1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
1
1
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
1
0
0
1
0
1
1
1
1
1
0
0
1
1
0
1
1
1
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
0
0
1
1
0
1
1
0
1
0
0
0
1
0
1
0
1
1
...

result:

ok Accepted.

Test #13:

score: 20
Accepted
time: 258ms
memory: 24064kb

input:

26 1000000
! 34816
! 229376
? 33554422
? 62504959
! 271362
? 66965439
! 16777346
? 66977630
? 67108831
! 8194
? 58653671
! 8224
? 67108735
! 16793616
? 58589055
! 18874880
! 34816
? 58720191
! 526432
! 8397312
? 66977663
! 2097704
! 9437312
? 66060223
? 50331647
? 67108863
? 67104767
! 64
! 106497
?...

output:

0
1
1
0
0
1
1
1
1
1
1
0
1
1
1
1
0
1
0
1
0
1
0
0
1
0
1
0
0
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
1
1
0
1
0
1
0
0
0
0
1
0
0
0
1
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
1
1
1
0
1
1
0
1
1
1
0
0
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
0
...

result:

ok Accepted.

Test #14:

score: 20
Accepted
time: 397ms
memory: 23096kb

input:

26 1000000
! 12239560
? 11240340
? 56270731
! 15892480
? 66054107
? 58653679
? 67097875
? 29022650
! 44635136
! 9765921
? 46792429
? 41933503
! 311312
! 38289409
! 8912897
? 43515829
? 52935717
! 10028228
? 17263997
! 36244352
! 37748760
! 4816901
! 40788992
! 1180229
! 38429834
? 29015917
! 3296346...

output:

0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
1
1
0
1
1
0
1
1
0
1
0
0
0
0
0
0
1
1
1
1
1
0
1
0
1
1
1
0
0
0
0
1
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
0
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
1
...

result:

ok Accepted.

Test #15:

score: 20
Accepted
time: 387ms
memory: 24264kb

input:

26 1000000
! 17894450
! 28643972
! 33554432
! 528
? 14168274
! 2537556
! 44889809
? 31675344
? 8351743
! 43354354
! 65537
! 39790768
? 66579959
? 65994748
? 21499891
? 34735264
? 58720255
! 20972688
? 46437446
? 62910207
! 4210689
? 66060243
? 1181484
! 16851026
! 50331648
! 50374762
? 52527805
? 17...

output:

0
1
1
0
1
1
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
0
0
0
1
0
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
1
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
1
1
1
0
1
0
1
1
1
0
1
0
0
1
0
1
1
0
0
0
0
0
1
1
1
0
1
1
1
0
1
0
1
1
0
0
0
1
0
0
0
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
0
1
0
0
1
1
0
1
...

result:

ok Accepted.

Test #16:

score: 20
Accepted
time: 348ms
memory: 23652kb

input:

26 1000000
! 64945459
! 2130432
! 2532046
! 12599424
! 56282647
? 19344017
? 45090833
? 4805144
? 46960018
? 16943286
! 12584068
! 50327645
! 64749309
! 67005375
? 66944887
? 31721023
? 66584446
! 2048
! 50257395
? 45236384
! 7858013
? 1079434
! 2
! 10518528
? 67108863
! 34615298
! 33824768
? 628490...

output:

0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
0
0
1
1
1
0
0
0
1
1
1
0
1
1
1
0
0
1
0
1
1
1
1
0
1
1
1
1
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
0
0
1
0
1
1
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1
1
0
0
1
1
0
0
0
0
1
1
0
1
1
1
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
0
1
...

result:

ok Accepted.

Test #17:

score: 20
Accepted
time: 293ms
memory: 23444kb

input:

26 1000000
! 50265974
? 67103483
? 33550318
! 67107839
! 2053
! 66772981
! 2150528
? 62906358
! 67027965
? 65544
? 67108863
! 50265903
? 16781313
? 67108863
? 66048
? 66567159
? 25243672
? 67108859
! 60129279
? 65007615
! 50331262
? 4718592
! 49283071
! 0
? 2261536
? 256
? 62914047
! 6815872
! 8262
...

output:

0
0
1
0
0
0
1
0
1
0
1
1
0
1
1
1
1
1
1
0
1
1
0
0
1
1
0
1
0
1
0
1
1
1
0
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
1
0
1
1
1
1
0
1
1
1
0
1
1
0
1
0
0
1
0
0
1
1
1
0
1
1
1
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
0
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
0
0
1
1
1
1
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
1
1
0
1
0
1
1
0
0
...

result:

ok Accepted.

Test #18:

score: 20
Accepted
time: 324ms
memory: 25036kb

input:

26 1000000
! 66052096
? 42209280
? 67104857
! 67100800
! 67100672
? 67093698
? 67102967
! 67100736
! 65003520
! 57491456
? 66969856
? 67105249
? 67101966
? 67103853
! 65626112
? 27226114
? 67100674
? 66969600
! 67100688
! 67100672
! 20259584
? 67100680
! 58220584
? 67105285
! 33548292
! 36084616
! 5...

output:

0
1
0
1
1
0
0
1
0
1
0
0
0
1
0
0
1
1
0
1
0
1
0
0
1
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
0
1
1
0
1
0
0
0
1
0
1
0
1
1
1
0
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
1
1
0
1
...

result:

ok Accepted.

Test #19:

score: 20
Accepted
time: 406ms
memory: 23820kb

input:

26 1000000
! 13918736
? 49807334
? 65011455
? 67102822
? 67108726
! 57503776
? 67105367
! 17432832
? 67074047
? 67107284
? 67090997
! 491520
! 10436672
? 66971808
? 67107137
! 5545984
? 67100784
? 67102789
! 21217280
! 20914176
? 67104416
! 30859264
! 20201472
! 27369480
? 67106623
? 67107466
? 6710...

output:

0
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
1
1
1
0
1
0
0
1
0
1
1
1
0
1
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
1
0
1
1
1
1
0
0
1
0
1
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
1
1
0
0
0
1
0
1
1
0
0
0
1
1
...

result:

ok Accepted.

Test #20:

score: 20
Accepted
time: 351ms
memory: 24752kb

input:

26 1000000
! 59739044
? 37748736
? 28249674
? 34779261
! 1408249
? 66289518
? 67108863
! 2772107
? 58719741
! 10498082
? 66052095
! 688328
! 49649064
? 49739239
! 12582912
! 33478607
? 0
! 26083666
! 20736
? 56016858
! 1097
! 47696511
? 40296265
? 48219897
! 62242430
! 58515375
? 17563672
! 62806902...

output:

0
0
0
0
0
1
0
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
1
1
1
1
1
1
1
0
1
0
0
0
1
0
0
0
1
1
0
0
1
0
0
1
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
1
1
0
1
0
1
0
0
0
1
0
1
0
0
1
1
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
0
0
0
1
1
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
1
0
1
1
1
1
...

result:

ok Accepted.

Subtask #3:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 848ms
memory: 48220kb

input:

28 1000000
! 1081468
! 128476263
! 67930241
? 94304031
! 103698752
! 19982
! 198050624
? 249519591
? 71286719
? 255700799
! 103309888
! 819340
! 12852092
? 124739445
? 192734967
! 101320328
! 117594711
? 252032927
! 134267948
? 262940285
! 3155972
? 267876218
! 41984160
? 246413294
? 246824252
? 163...

output:

0
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
1
0
1
1
1
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
1
0
0
1
1
1
0
1
1
0
1
0
1
1
1
0
0
0
0
1
1
1
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
0
1
1
1
1
1
0
1
0
1
0
1
0
0
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
0
1
1
1
0
1
1
0
1
0
1
...

result:

ok Accepted.

Test #22:

score: 20
Accepted
time: 266ms
memory: 26172kb

input:

28 1000000
! 0
? 268435455
? 268435455
? 268435455
? 268435455
? 268435454
! 262144
! 2097152
? 268435455
? 266338303
! 0
? 268435455
? 268431359
? 268435455
? 268435199
? 268435455
! 0
? 268435455
? 268304383
? 268435455
? 267386871
! 0
! 0
! 0
! 8192
? 234881023
? 268435455
? 268435455
? 268435455...

output:

1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
0
0
0
0
1
1
0
1
0
1
1
1
1
0
0
0
0
1
1
0
1
1
1
1
1
0
1
0
1
1
1
1
0
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
1
0
1
...

result:

ok Accepted.

Test #23:

score: 20
Accepted
time: 419ms
memory: 48028kb

input:

28 1000000
! 67108864
? 268369919
? 108724215
! 2621440
! 360576
? 259319807
? 62414335
? 267911039
? 268434111
! 204968
! 3670272
? 255844319
! 8404992
? 267643903
? 264239485
? 268435451
! 67469313
! 136314896
? 268435455
! 0
? 268361727
? 266268671
! 131074
? 268271607
! 16384
! 1705984
! 270464
...

output:

1
1
1
1
1
1
0
1
0
0
0
0
1
0
0
1
0
1
1
1
1
0
1
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
1
0
1
0
0
1
1
1
1
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
0
1
1
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
0
0
0
1
1
0
1
1
0
0
0
1
0
1
1
0
0
1
0
0
1
1
1
0
0
0
1
1
1
0
0
...

result:

ok Accepted.

Test #24:

score: 20
Accepted
time: 841ms
memory: 48596kb

input:

28 1000000
! 1902096
? 81641694
? 247381723
? 268423692
! 117194752
? 75033877
? 226360807
! 88368128
? 38723567
! 50598934
! 144779282
? 130765271
! 211109508
! 9496640
? 259837397
? 192822463
! 17358848
! 23330881
! 199852673
? 201030356
! 8467396
? 249459704
! 142884899
! 34112802
! 167781384
? 1...

output:

0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
1
1
0
1
0
1
1
0
1
0
0
1
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
0
0
1
1
0
0
0
1
1
0
1
1
0
1
0
0
0
1
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
1
0
0
0
0
1
0
1
0
1
0
1
1
0
1
1
1
1
0
1
0
1
0
1
1
0
0
1
0
1
0
0
1
0
1
0
1
...

result:

ok Accepted.

Test #25:

score: 20
Accepted
time: 786ms
memory: 47752kb

input:

28 1000000
! 210829378
? 36947522
? 259790155
? 268433343
? 233308142
? 205687805
! 262177
? 246208617
? 268173279
! 35651584
! 8520002
? 234749947
? 180634441
! 147279353
! 192794271
! 131076
? 268353534
? 130268453
? 101299305
? 228765468
! 33685506
! 557056
! 260
? 268434428
? 207609440
? 2572858...

output:

0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
0
1
0
0
1
1
1
0
0
0
1
1
1
0
0
...

result:

ok Accepted.

Test #26:

score: 20
Accepted
time: 664ms
memory: 48444kb

input:

28 1000000
! 64484791
! 33554496
! 134217748
? 15770753
? 234878457
! 112293486
! 268426430
? 168308817
! 8389248
? 251656191
? 267991807
? 151001904
? 201325631
? 218124361
! 33556752
! 67108864
! 4
! 265177583
! 263691254
! 206307327
? 268304383
? 268034047
! 266253730
? 6427266
? 268435455
? 1851...

output:

0
0
1
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
0
1
1
1
0
1
1
0
1
0
0
1
0
0
0
1
0
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
0
1
1
1
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
1
0
0
1
1
0
1
1
1
1
1
0
0
1
1
0
0
0
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
1
1
0
1
1
1
0
0
0
1
0
0
1
1
...

result:

ok Accepted.

Test #27:

score: 20
Accepted
time: 474ms
memory: 48904kb

input:

28 1000000
! 4202592
? 262144
? 134217728
? 134217727
! 268433915
? 8667202
! 266174462
? 10487808
! 266338303
? 268435455
! 267370495
! 131072
? 268434879
! 248501679
! 0
? 268434935
! 268429303
? 125693919
? 268432895
? 1048704
! 257912703
! 72324
? 268337150
! 33619972
? 67108866
! 199097855
? 26...

output:

0
0
1
0
0
0
1
1
1
0
1
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
0
0
1
1
1
1
0
1
0
1
1
0
0
1
0
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
0
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
1
0
0
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
1
1
1
1
1
0
1
0
1
0
...

result:

ok Accepted.

Test #28:

score: 20
Accepted
time: 450ms
memory: 48592kb

input:

28 1000000
! 268435455
? 268404569
! 201285633
! 268427264
? 201310256
! 126173184
! 266326028
? 268420376
? 134207050
! 268288000
? 267898882
? 268433315
! 87539712
? 267370496
! 257802240
? 266289152
! 134135808
! 268419072
? 268421951
? 268422248
! 175866400
! 268419072
? 268419104
? 201310208
? ...

output:

0
0
1
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
1
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
0
0
1
1
0
0
1
0
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
0
0
0
1
1
0
1
1
1
0
1
1
0
0
1
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
0
1
1
0
0
1
0
1
1
1
...

result:

ok Accepted.

Test #29:

score: 20
Accepted
time: 500ms
memory: 49332kb

input:

28 1000000
! 98304
! 17301505
! 246243328
? 268427255
! 103022880
! 33554432
? 268288300
? 66974465
? 268393616
! 250662912
! 148521024
? 268148687
? 260046591
? 268427804
? 268424330
! 152322048
! 268435071
! 220708864
! 186187776
? 268422639
? 268435287
? 268421745
! 249331729
! 204685312
! 244465...

output:

0
1
1
1
1
1
1
1
0
1
1
1
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
1
1
1
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
0
0
0
1
1
1
0
1
1
1
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
1
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
0
1
0
0
1
1
0
1
1
0
1
1
1
...

result:

ok Accepted.

Test #30:

score: 20
Accepted
time: 757ms
memory: 48652kb

input:

28 1000000
! 102051418
? 2048
? 213870324
! 50323454
! 16908290
! 216060049
! 268237299
! 265797110
? 266959613
! 34131606
! 215308128
? 98433979
! 251658239
! 0
! 268434427
? 21560592
! 250565469
? 238864954
? 3670016
! 267384827
! 126104535
! 169446416
! 139149481
? 254782395
! 1581056
? 210929166...

output:

0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
1
1
0
1
1
0
1
1
0
0
1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
0
1
1
1
1
0
1
0
0
1
0
1
1
1
0
0
1
1
1
1
1
1
0
0
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
1
1
0
0
...

result:

ok Accepted.

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 2193ms
memory: 147112kb

input:

30 1000000
! 33852274
? 1017904007
? 1046413001
! 151029382
? 466826079
? 250568375
! 6769874
! 2106474
? 536832803
? 209627867
! 167104971
? 1048372157
! 245380745
! 25174496
? 819646460
! 539548800
! 671358165
? 402955591
? 527753201
! 582494209
? 862862931
? 938974695
? 263672827
? 366968669
? 87...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
0
1
1
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
1
1
0
1
0
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
0
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0
1
1
0
1
1
1
0
1
0
1
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
1
0
1
1
1
...

result:

ok Accepted.

Test #32:

score: 20
Accepted
time: 231ms
memory: 18312kb

input:

30 1000000
! 16777216
? 1073741823
! 0
! 0
! 0
? 1073741823
? 1073741823
? 1056964607
? 1073741823
! 0
? 1073741823
! 0
! 0
? 1073741823
? 1073741823
! 0
! 0
? 1073741823
! 0
? 1069408255
! 0
? 1073741823
! 0
? 1073741823
! 0
? 1073741823
! 128
! 131072
? 1073741823
? 1073741823
? 1073741823
? 10737...

output:

1
0
0
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
1
0
1
1
0
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
1
1
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
0
0
1
1
0
...

result:

ok Accepted.

Test #33:

score: 20
Accepted
time: 576ms
memory: 144896kb

input:

30 1000000
! 1073661373
? 1069547518
? 1040187327
? 1064828927
! 268435584
! 54526017
! 536870912
? 1071644655
! 8519680
? 1071640575
! 1073741823
! 1064992
! 64
? 1072160767
? 805298175
? 1006628831
! 2752512
? 1073737724
! 1024
! 536870912
? 939524067
! 4204544
! 0
! 142671904
! 134742202
? 106482...

output:

0
0
0
1
0
1
1
1
0
1
1
0
1
0
1
1
1
0
1
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
0
0
0
1
1
1
0
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
1
0
0
1
1
0
0
0
0
0
1
0
1
0
0
1
0
1
1
1
1
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
0
1
1
1
0
1
0
1
0
0
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
1
0
0
1
...

result:

ok Accepted.

Test #34:

score: 20
Accepted
time: 2201ms
memory: 148016kb

input:

30 1000000
! 814786940
! 940688522
! 341410458
! 42352898
! 860209250
! 514633857
! 26763330
! 243310796
! 25600418
! 68363333
? 938056250
! 251896592
! 553651236
! 100810789
? 506984941
? 116056774
! 616784901
! 276957332
! 75829252
! 25231922
! 673186852
! 808545586
? 330911500
! 268996754
? 79272...

output:

0
1
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
1
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
1
1
1
0
1
0
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
1
1
0
1
1
1
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
1
0
0
1
0
1
0
0
1
1
0
1
1
0
1
0
0
0
0
0
0
1
0
0
1
...

result:

ok Accepted.

Test #35:

score: 20
Accepted
time: 1882ms
memory: 146900kb

input:

30 1000000
! 947623540
? 1073709055
! 536727820
! 757142973
? 514413951
! 541065216
? 1073741823
! 728124554
! 131072
! 2114632
? 1071349757
! 128
? 346158708
! 736032396
? 848072391
! 786688
? 463405431
? 348336648
! 1024
? 973078525
? 1073217535
? 270010037
? 804255743
! 471525397
? 1064302589
! 1...

output:

0
0
0
0
0
1
0
1
1
1
0
1
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
0
0
1
0
1
0
1
1
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
1
1
0
1
1
0
1
0
1
1
0
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
1
0
0
0
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
0
1
1
0
1
1
1
0
1
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
...

result:

ok Accepted.

Test #36:

score: 20
Accepted
time: 1377ms
memory: 147156kb

input:

30 1000000
! 62316343
? 1073676223
! 2097160
! 359907021
! 0
! 138
? 1073463023
? 1006632947
! 67109000
? 1073741311
! 1037934173
! 326717363
? 838852607
? 74195224
! 4194434
? 86115012
! 276963330
! 137428992
! 0
? 398458847
! 247461197
! 790030063
! 1005752186
? 1023377407
? 276827768
? 1073740735...

output:

1
0
1
0
1
0
1
0
0
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
1
1
1
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
1
0
1
1
1
0
0
0
0
1
1
0
0
0
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0
0
1
0
1
1
1
1
1
1
0
1
1
0
1
...

result:

ok Accepted.

Test #37:

score: 20
Accepted
time: 859ms
memory: 138964kb

input:

30 1000000
! 33818632
? 32898
! 1071644543
? 1073217023
! 134225920
! 98306
? 1072660475
! 989839343
? 139264
! 536937472
! 16448
! 1073725183
? 268435456
? 989331455
! 939655170
? 376728390
! 52428800
? 0
? 939491071
! 939524017
! 536215549
? 4196352
! 131072
? 67108866
! 16777216
! 269504512
? 805...

output:

0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
0
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
1
0
1
1
0
1
1
0
1
1
0
1
1
1
0
0
1
0
0
0
1
1
1
0
1
1
1
0
0
1
1
1
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
0
1
0
0
1
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
1
1
0
1
1
...

result:

ok Accepted.

Test #38:

score: 20
Accepted
time: 928ms
memory: 147820kb

input:

30 1000000
! 715751424
! 752582658
! 1069514754
! 223576192
! 393480192
! 332922880
! 1073709064
! 1071622152
! 398393344
! 409174016
! 1001848896
? 1073719187
? 1073578048
? 1073728087
? 754317263
? 1073728377
! 986611712
! 267026432
! 536846352
? 1073710080
? 930145416
? 1069514944
! 1073709073
? ...

output:

1
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
0
0
0
1
0
1
1
0
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
1
0
0
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
1
0
0
0
1
1
1
0
1
0
1
1
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
1
0
0
1
1
0
0
1
0
1
1
0
0
1
1
0
1
0
1
1
0
1
0
0
0
0
0
1
1
0
0
...

result:

ok Accepted.

Test #39:

score: 20
Accepted
time: 1169ms
memory: 146220kb

input:

30 1000000
! 778207233
! 5374208
? 1073741311
? 1073737215
! 276824064
! 643579904
! 1023213568
! 985070382
! 151011332
? 1073712036
? 1073710389
? 1056948256
? 1072168959
! 937688703
! 613318656
? 1071622071
? 1073733503
? 1040155944
! 553517056
? 1073726692
! 773292036
? 1073684637
! 5308416
! 131...

output:

0
0
1
0
1
1
1
1
0
0
1
0
1
1
0
0
0
1
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
1
0
1
0
0
1
1
0
1
1
1
0
0
1
0
1
1
0
1
0
1
1
1
0
1
1
1
1
1
0
1
0
1
1
1
1
0
1
1
0
0
0
0
1
1
1
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
1
0
1
0
0
1
0
1
0
0
0
1
1
1
1
1
0
0
1
1
1
0
1
0
1
0
0
1
0
0
...

result:

ok Accepted.

Test #40:

score: 20
Accepted
time: 1605ms
memory: 147040kb

input:

30 1000000
! 1034944509
! 939523935
? 1073741823
! 993976731
? 536838141
? 1073741823
! 673341776
! 1056948222
? 33818282
! 1035993023
? 1073694470
? 269496832
! 187690975
? 272782352
! 1031782331
? 951778952
! 1073741823
? 1073675743
? 181122811
? 0
? 1039532031
? 345064149
! 531988
? 1073741822
? ...

output:

0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
1
0
0
1
0
0
0
1
1
0
1
1
1
1
0
1
0
1
0
0
...

result:

ok Accepted.

Subtask #5:

score: 20
Accepted

Test #41:

score: 20
Accepted
time: 4933ms
memory: 541008kb

input:

32 1000000
! 2474971548
! 348268033
? 1055293046
? 3382525679
? 1805515707
? 3210332902
? 2805668987
? 4025974780
! 2217771280
! 176949664
! 4213841344
! 1477473321
? 3150869759
? 2127418041
! 1610631720
! 3624477314
! 2288149532
! 70909964
! 40117153
! 1343751456
? 3758095615
! 513059275
! 31956816...

output:

0
0
0
0
0
0
0
0
1
1
1
0
1
1
0
1
0
0
1
1
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
0
1
0
0
1
1
1
0
1
1
0
1
0
0
0
0
1
0
1
1
1
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
1
1
0
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #42:

score: 20
Accepted
time: 278ms
memory: 28432kb

input:

32 1000000
! 0
? 4294965247
? 4294967295
? 4278189567
? 4294967293
? 4294959103
? 4290772991
! 0
! 0
! 0
! 0
! 32768
? 4294967295
! 0
? 4294967295
! 0
! 0
? 4294967295
? 4160749567
? 4294967295
! 0
? 4294967295
? 4294967295
! 8192
! 0
? 3221225471
! 0
? 4294966783
! 0
? 4160749567
! 0
! 0
? 42949672...

output:

1
1
1
1
1
1
0
1
1
1
1
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
1
1
1
0
1
1
0
0
0
1
0
0
1
1
1
1
1
1
1
1
0
0
1
1
0
1
1
0
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
0
1
1
1
0
0
0
0
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
1
0
...

result:

ok Accepted.

Test #43:

score: 20
Accepted
time: 1254ms
memory: 463332kb

input:

32 1000000
! 0
! 67371008
? 4290772735
? 4294442943
? 3219118063
? 4158652415
? 4227186542
? 4294950911
? 3753869311
! 73728
! 34832
? 4025483231
! 1073741824
! 33555456
! 536870914
? 4026531839
? 4211015679
! 2560
? 4294967295
? 4294967279
? 4290510847
? 3137339390
! 268566528
? 2062530029
! 335544...

output:

0
0
0
0
1
0
0
0
1
1
0
1
1
0
1
0
0
1
0
0
0
0
1
1
1
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
0
1
0
1
0
1
0
1
0
0
1
1
0
1
1
1
1
1
1
1
0
0
0
0
1
0
0
0
1
0
0
1
0
0
1
1
0
1
0
0
1
0
1
1
0
0
0
0
1
1
0
1
1
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
1
0
0
0
1
0
0
1
0
1
1
0
0
0
1
1
0
...

result:

ok Accepted.

Test #44:

score: 20
Accepted
time: 4507ms
memory: 539048kb

input:

32 1000000
! 1755841544
! 573047496
! 16778565
! 2785673864
? 129892336
! 3293577794
! 14942209
? 4191678459
! 565320
? 2291867647
! 136852497
! 372265921
? 2078127419
! 3524808720
? 3741015384
? 4007450330
! 1083707211
! 268443921
? 4113519611
! 1183502594
? 671233048
! 1113114717
? 3210182381
! 38...

output:

0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
1
0
0
1
1
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
0
1
1
0
0
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
1
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
0
0
1
1
0
1
1
0
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
1
0
1
1
0
1
1
0
0
0
1
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
0
0
1
1
1
0
0
0
1
0
1
1
...

result:

ok Accepted.

Test #45:

score: 20
Accepted
time: 4057ms
memory: 540360kb

input:

32 1000000
! 105373520
! 473126059
? 836554967
? 4294966655
? 1017917278
! 33554496
! 936097420
! 4098
? 4227334143
? 3217020903
? 4261402095
! 2064
? 388354464
! 33556480
? 4273994239
! 10502152
? 244136115
! 4194308
? 4294443007
! 131281
! 466808739
! 2361409608
! 225471362
! 131104
? 867749959
! ...

output:

0
0
0
0
0
0
0
0
1
0
0
1
1
1
1
0
0
0
0
0
1
1
0
0
1
0
0
1
1
0
0
1
1
0
1
1
1
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
0
1
1
0
1
1
1
0
1
0
0
0
1
0
0
1
1
0
1
0
0
0
1
1
1
1
1
1
1
0
1
0
0
0
1
1
1
1
1
0
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
1
0
0
0
1
1
0
0
0
1
1
1
1
1
1
1
1
1
0
1
1
1
0
0
1
0
0
1
0
1
0
1
1
0
0
0
1
0
0
0
...

result:

ok Accepted.

Test #46:

score: 20
Accepted
time: 3327ms
memory: 538592kb

input:

32 1000000
! 268439685
! 1073807360
? 4294967135
? 4160684031
! 1775730655
! 1614842369
? 129245452
? 2006188086
? 1246017555
? 4294933491
? 4286578558
? 4275566271
! 4152178530
! 2348767807
? 4290740218
! 65536
? 3220635135
! 2148042756
! 3454528470
! 4126785535
! 163846
! 4001021815
? 3749699519
!...

output:

1
1
0
0
0
1
1
0
1
1
1
1
0
1
1
0
0
0
1
0
0
1
1
0
1
1
0
1
1
1
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
0
1
0
0
1
1
1
1
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
1
1
0
1
1
1
0
0
1
1
0
0
1
0
0
0
0
1
0
0
0
...

result:

ok Accepted.

Test #47:

score: 20
Accepted
time: 1953ms
memory: 481940kb

input:

32 1000000
! 2164374266
! 12583009
! 4294402047
! 4093640127
! 4294179839
? 1077957264
? 2097152
? 65600
? 2147352511
? 1073742144
? 4026515455
? 1350697216
? 4160749559
? 4026531837
! 805306355
! 263176
! 1077936136
! 531488
! 4294836223
? 4291820991
! 4294819743
! 2
? 8192
? 0
? 167776386
! 429470...

output:

0
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
1
0
1
0
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
0
0
0
0
0
1
0
1
1
1
0
0
1
1
0
1
1
1
0
1
1
1
1
1
1
0
0
0
0
0
1
0
1
0
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
1
1
0
0
1
0
0
0
1
0
1
1
0
0
0
1
1
0
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
...

result:

ok Accepted.

Test #48:

score: 20
Accepted
time: 1639ms
memory: 540976kb

input:

32 1000000
! 4261348608
? 4294902784
! 4290506559
? 4294932691
! 4026466560
? 4294770688
! 4261281792
! 3345809408
! 2147418240
? 4294901760
! 4293853184
! 4294901760
! 1039925252
! 4293853184
? 4286513152
? 4293826460
? 4026466304
? 4293896996
! 4294901760
? 4294920722
! 4227792896
? 3758030848
! 4...

output:

0
0
0
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
0
1
1
1
0
0
0
1
1
1
0
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
0
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
1
1
0
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
1
0
1
1
0
0
1
0
1
1
1
0
1
0
0
0
0
0
0
1
0
1
...

result:

ok Accepted.

Test #49:

score: 20
Accepted
time: 1824ms
memory: 534860kb

input:

32 1000000
! 3928096769
! 743243776
! 3790422144
? 4294907850
? 4294967294
? 3690970111
! 2135949314
? 4294967279
! 134217984
! 1107296288
? 2146889723
? 4293917695
! 2164523264
? 4294919973
? 4294967295
? 4291816959
! 3783330848
? 4294967295
! 138674176
? 4292870015
? 4294932538
? 4294944684
? 4227...

output:

1
0
0
0
1
1
1
1
0
0
1
0
1
1
0
1
0
0
0
0
1
0
1
1
0
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
1
0
1
1
0
1
1
0
1
0
1
1
1
0
0
1
1
0
1
1
1
1
1
1
1
0
1
1
0
1
0
0
1
0
0
0
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
0
0
0
0
1
0
1
0
0
0
0
1
1
1
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
0
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
1
1
1
1
0
...

result:

ok Accepted.

Test #50:

score: 20
Accepted
time: 3812ms
memory: 539240kb

input:

32 1000000
! 4007572863
? 3224895744
? 2818859861
? 2710063109
! 4259838844
? 3990878207
? 3015434939
! 134089204
! 2322595840
? 4294967294
? 2595192733
? 531155243
? 67208192
! 2681605630
? 1659540665
? 2452859716
? 16777216
? 3499900612
! 133120
! 3283531230
? 4294967295
! 19410952
! 2146222079
? ...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
0
1
1
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
0
1
1
0
0
1
1
0
1
1
0
1
1
1
1
1
1
1
1
0
0
0
1
0
1
1
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
1
1
0
1
1
0
0
1
1
0
1
1
0
1
0
0
1
0
0
0
...

result:

ok Accepted.

Test #51:

score: 20
Accepted
time: 4230ms
memory: 540620kb

input:

32 1000000
! 4294967039
? 16785418
? 565264
? 962022560
! 4127505850
? 608438944
! 1270795938
! 4222222189
! 2701039246
? 35
! 4282384381
? 1155673165
! 4293853147
! 4286545919
? 646528671
! 4294967294
! 4294832127
? 24592
? 16641
? 25165892
! 2183348260
? 1880114442
? 2164916256
! 894714876
? 98631...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #52:

score: 20
Accepted
time: 3999ms
memory: 539452kb

input:

32 1000000
! 2703672842
! 2147614720
? 717425925
? 4294932479
? 4292849663
? 486709647
? 2502206490
! 4283198347
? 3992846271
? 3765565792
! 8
? 2233142852
? 264658440
? 357699752
! 136314900
! 2226759639
? 2155326246
? 82051200
? 2806808759
? 1208305216
! 1073741856
! 35651585
! 2160093441
! 230687...

output:

0
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
1
0
1
0
1
1
0
0
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
1
1
1
0
1
1
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
0
0
1
0
1
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
1
0
...

result:

ok Accepted.

Test #53:

score: 20
Accepted
time: 4389ms
memory: 539632kb

input:

32 1000000
! 4325376
? 2942289498
? 1065232
? 4260793815
! 136380673
! 1828661908
! 83902464
? 1213185410
? 3518090997
! 3454158591
! 3389172838
! 1554456425
? 67127296
! 3760326824
! 406863923
? 3133125038
! 17334281
! 476736842
? 2613854206
! 134225968
? 208196627
? 4096
? 2
? 2113807481
? 5368729...

output:

1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
0
1
0
1
1
1
1
1
1
0
0
0
1
0
0
1
1
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
1
0
1
1
0
1
1
1
0
1
0
0
1
0
1
0
0
0
1
1
1
1
1
1
0
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
0
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
...

result:

ok Accepted.

Test #54:

score: 20
Accepted
time: 2881ms
memory: 540560kb

input:

32 1000000
! 1054834631
! 3890085887
? 1073807376
! 3814710433
? 1579717444
? 541100032
? 317227048
! 231388265
? 327532608
? 1107496962
? 1249894359
? 2468842800
! 1037432826
! 7083217
! 2390746362
! 2143289327
! 4290247679
! 1929145024
! 2805205998
! 4294966971
? 13632001
! 4085219311
? 1337982907...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
...

result:

ok Accepted.

Test #55:

score: 20
Accepted
time: 2881ms
memory: 540140kb

input:

32 1000000
! 4127191035
? 1126308712
? 1091043328
? 1142164041
? 2370114440
? 405823501
! 4291690495
! 2415787951
? 2948326205
! 1972533067
? 2147483776
? 335675392
! 2424198314
! 3017633763
! 346235782
! 1676712843
? 416468046
? 2415939584
! 67108928
? 513577209
? 33554436
! 1565236247
? 176343552
...

output:

0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
0
1
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
...

result:

ok Accepted.

Test #56:

score: 20
Accepted
time: 2850ms
memory: 540644kb

input:

32 1000000
! 4294967263
? 2387309966
? 1195203
? 347406661
! 2415919280
! 3212834543
? 3096175610
? 3475604192
! 4294963199
! 1871401793
? 1073750272
? 1419888993
! 3241738578
! 4033431254
! 872058013
! 4294967036
! 1006632379
? 8454160
! 3154074623
? 1080688706
! 3919819014
! 4276092895
! 422571206...

output:

0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok Accepted.

Test #57:

score: 20
Accepted
time: 3012ms
memory: 537608kb

input:

32 1000000
! 4085251839
! 4290772991
? 2562740821
! 33554472
! 4137410303
? 872719524
? 555811840
! 3094738490
? 4291526643
? 49417336
? 3221328898
? 2161784960
! 18222593
! 2013239831
? 8536192
? 135729992
? 4294817790
? 1131496
? 4293917695
? 570439822
! 2952788991
? 50334978
! 4278188026
! 429496...

output:

0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
0
1
1
0
0
1
1
1
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
0
1
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
0
0
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
0
1
...

result:

ok Accepted.

Test #58:

score: 20
Accepted
time: 4503ms
memory: 540356kb

input:

32 1000000
! 3882512057
? 412001591
? 2079848443
! 180512006
? 2616479743
! 2754392312
! 916832049
! 268451840
! 1100101129
! 369238121
! 224527770
! 167774218
? 1573574995
? 4086779765
? 4284415999
! 823297152
! 1223948829
? 1543446722
! 676614144
! 8519688
! 1835098954
? 4028241306
! 2920563601
! ...

output:

0
0
0
1
1
1
0
0
1
1
1
1
1
1
0
1
1
1
0
0
0
0
0
1
0
1
1
1
1
0
0
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
0
1
0
1
1
1
1
1
0
0
1
0
1
0
1
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
0
1
0
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
1
1
1
1
...

result:

ok Accepted.

Test #59:

score: 20
Accepted
time: 3495ms
memory: 534788kb

input:

32 1000000
! 29392967
! 0
? 4285530095
? 1604157439
! 1444937984
? 3024204224
? 1728387496
! 268697633
? 3478975201
? 337650315
? 2130694110
! 805339136
? 179184004
! 655488
! 61096000
? 2977322927
? 4261411839
? 2113339263
! 2677792767
? 2659182102
? 2587372108
? 3166949124
! 8389284
? 1143786637
!...

output:

1
1
1
1
1
1
0
1
0
1
0
1
1
0
1
1
0
0
0
1
1
1
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
0
1
1
1
0
1
1
1
0
0
0
0
1
1
1
0
1
0
1
0
0
0
1
1
1
0
1
1
1
1
1
0
0
0
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
0
...

result:

ok Accepted.

Test #60:

score: 20
Accepted
time: 4474ms
memory: 540808kb

input:

32 1000000
! 1073750568
? 180355724
! 268451842
? 2754702427
! 2726359563
! 1063795536
! 953253952
! 2372440925
? 1811397501
! 4004578507
! 90163654
! 18087943
? 1210160580
! 71304256
? 901921280
? 1540347903
! 270215440
? 4148304216
? 1092616288
! 1133118016
! 67109120
? 4121285749
? 266284674
? 40...

output:

0
0
1
0
0
1
0
0
0
0
1
0
1
1
0
1
1
1
0
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
0
1
0
0
1
0
1
1
1
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
0
0
1
1
1
0
0
0
1
0
1
0
1
0
0
1
0
0
1
0
1
0
1
1
1
1
1
0
1
1
...

result:

ok Accepted.

Test #61:

score: 20
Accepted
time: 5121ms
memory: 527032kb

input:

32 1000000
! 1755655192
? 3556632831
! 105333599
? 4293875517
? 4166942439
! 2955424560
? 3181374678
! 1755516162
! 1892696672
? 1651242687
? 3623872767
! 75498025
! 1145194084
? 3219627736
? 3907351518
? 4090059549
! 3447914851
! 587730948
? 4126924635
? 4129287626
! 167837756
! 337197076
? 2133810...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
1
1
0
1
0
1
0
0
1
0
1
0
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
0
1
1
1
1
0
1
1
1
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
1
0
1
0
0
0
1
1
1
0
1
1
0
1
1
1
0
1
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
0
0
0
1
1
1
1
1
1
1
0
1
1
...

result:

ok Accepted.

Test #62:

score: 20
Accepted
time: 2761ms
memory: 533156kb

input:

32 1000000
! 20743253
! 1114744840
! 805833234
! 269223485
! 3271559744
? 1944911263
! 146853900
! 2416706949
! 2488708256
! 1690549636
? 3210607453
! 203232775
? 3221022205
! 171983360
! 102307562
! 134292363
! 5345414
! 1216479745
! 2920318000
! 1226868739
! 1146112375
! 2181199560
! 3494121664
? ...

output:

0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
1
1
1
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
1
1
0
0
1
1
0
0
1
1
1
0
1
1
1
0
1
0
0
0
0
1
1
1
1
0
1
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
1
1
0
...

result:

ok Accepted.

Test #63:

score: 20
Accepted
time: 2779ms
memory: 518196kb

input:

32 1000000
! 140949949
? 2765274079
? 3200232829
? 3882978467
? 3439277023
? 1039620606
? 1275034493
? 4267166079
? 4290734161
? 2885668849
? 4268680636
? 1862752478
? 4019975546
? 3751589879
? 3632790590
! 2490432
? 224386607
? 715243482
? 2935747646
? 2042101743
? 2666067119
? 1051975077
? 4273964...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
1
1
0
1
0
1
1
0
0
0
0
0
1
1
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
1
1
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
0
0
1
0
0
0
1
1
0
1
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
...

result:

ok Accepted.

Test #64:

score: 20
Accepted
time: 6058ms
memory: 541404kb

input:

32 1000000
! 3418940814
! 1283294422
! 3650200284
! 2411028620
! 2408141143
! 2013647332
! 3275826010
? 2014355746
! 2303907255
! 1620667876
! 274443302
! 1310521304
! 1621726782
? 3708729161
! 4078223031
! 3148356892
! 3158231476
! 1529829637
! 768101117
? 912143052
! 271710112
! 11622142
! 1658009...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
...

result:

ok Accepted.

Test #65:

score: 20
Accepted
time: 2774ms
memory: 540016kb

input:

32 1000000
! 243279041
? 2721774018
? 1441138964
? 3988206681
? 3210113645
? 2089258579
? 1591461658
? 3733962652
? 1232650659
! 251147285
? 4082135943
? 2325198763
? 3037997954
? 3137687904
? 4207452054
? 66054072
? 3570445421
? 1312157199
? 4094451581
! 2325390404
? 2584086965
? 3341954290
? 38874...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok Accepted.

Test #66:

score: 20
Accepted
time: 830ms
memory: 515200kb

input:

32 1000000
! 4160684032
! 4294778944
? 4278124544
! 4293896200
! 4294950912
! 4294901760
? 4294901760
? 2146893856
? 4294967295
? 4026466304
! 4294902272
! 4294901760
! 2145321984
! 1162306225
? 3355377680
! 4294901760
! 3623682048
? 4261347328
! 563262017
? 4294918176
! 4286513152
? 4160684032
! 42...

output:

0
0
0
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
0
1
1
1
0
0
1
0
1
0
0
0
1
0
1
1
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
1
1
1
0
1
1
0
0
1
1
1
0
0
1
1
1
0
1
0
0
1
1
1
1
1
0
0
0
1
0
0
1
1
0
1
1
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
...

result:

ok Accepted.

Test #67:

score: 20
Accepted
time: 1126ms
memory: 521864kb

input:

32 1000000
! 4026466304
! 4292804868
? 4294901760
? 4293263360
? 3221159936
? 4160684128
? 4294909952
? 3220897792
! 4227843136
! 4292804612
? 4292804608
? 4294901760
! 4286513152
? 4294901762
? 2039985846
? 3221159936
? 4227801088
? 4294902848
! 4227793408
? 3758030848
? 4294902272
! 4294639616
? 4...

output:

1
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
1
1
0
1
1
0
1
0
1
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
1
1
1
1
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
...

result:

ok Accepted.

Test #68:

score: 20
Accepted
time: 1135ms
memory: 519308kb

input:

32 1000000
! 4294901760
? 4278124544
? 4294903936
? 4294381568
! 4261347330
! 4294836228
! 4294901760
! 4294901761
? 4294901760
? 4294901760
! 4294905856
? 4294901760
? 2147435008
? 4294901760
? 4294903814
! 2952724608
! 3200204800
! 4294903296
? 4294901760
! 4160684160
? 4160618496
? 4290707456
? 4...

output:

0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
1
0
0
1
1
1
1
0
0
0
1
1
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
0
1
0
1
1
0
0
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
0
1
1
...

result:

ok Accepted.

Test #69:

score: 20
Accepted
time: 819ms
memory: 514120kb

input:

32 1000000
! 4294902016
! 4294377472
! 4294901760
! 4294906400
? 4294901761
! 4294377472
! 4290658304
! 4160684032
! 4026466308
! 4294901776
? 563359779
? 4294901760
! 4294901760
! 4294901760
! 4294901760
? 4261380096
? 4277075968
? 4158586880
! 3221161984
! 4293869632
! 4290707456
! 4292804608
! 42...

output:

0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
1
0
1
1
1
0
0
1
1
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
1
1
1
1
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
0
0
1
0
0
0
0
0
0
1
1
1
0
1
1
0
1
0
1
1
0
1
1
1
0
0
0
1
0
0
0
1
1
0
0
0
0
1
1
0
1
0
0
0
1
1
1
0
...

result:

ok Accepted.

Test #70:

score: 20
Accepted
time: 1060ms
memory: 504424kb

input:

32 1000000
! 4294901824
? 4293787648
! 4294901760
! 4294901760
? 4227801216
! 4294901824
? 2013249532
! 4286517248
? 4286251009
! 4026466306
! 4156489792
! 4294901760
? 4022288384
! 3758030848
! 2147418112
? 4286513409
? 4294918144
! 3221160960
? 4293853184
? 4294918148
! 4286529536
? 4294902288
! 4...

output:

0
0
0
0
0
0
1
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
0
0
1
0
1
0
1
0
0
1
1
1
1
1
1
1
1
1
1
0
0
0
0
1
0
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
1
1
1
1
0
1
0
0
0
1
0
1
1
1
1
1
0
1
1
1
0
0
1
0
1
0
1
1
0
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
0
0
...

result:

ok Accepted.

Test #71:

score: 20
Accepted
time: 799ms
memory: 524636kb

input:

32 1000000
! 1479548946
? 1935093537
! 1211113490
! 1211113490
? 4261264444
? 4261264444
? 4261264508
? 273026745
! 1211637778
! 1211113490
? 4261264446
! 3358597138
? 3992828988
? 4261264444
! 1211113490
? 4261264444
? 4259167292
? 4261264444
? 4261264444
? 4261264508
? 4261264700
! 1211113490
? 28...

output:

0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
1
1
1
0
0
1
1
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
1
...

result:

ok Accepted.

Test #72:

score: 20
Accepted
time: 1242ms
memory: 525460kb

input:

32 1000000
! 4194304
! 0
? 4259315711
? 4259315710
! 0
? 4259315711
! 0
! 0
! 134217728
! 0
! 2048
? 4259315711
? 4259315710
! 1048576
? 2164391936
! 1048576
! 0
? 4259315711
? 4259315711
? 4259315711
? 4261412863
! 1073741824
? 4259315679
? 4292870143
? 4259315711
! 4194299870
? 4259299327
! 0
! 25...

output:

0
0
1
0
0
1
1
1
1
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
1
1
1
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
1
1
0
1
1
1
0
1
0
0
1
0
0
0
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
1
0
0
1
0
1
1
1
1
1
0
0
0
1
0
1
0
1
1
1
1
0
0
1
1
0
0
1
1
1
1
1
1
0
1
1
1
1
...

result:

ok Accepted.

Test #73:

score: 20
Accepted
time: 912ms
memory: 526224kb

input:

32 1000000
! 75499008
! 75499008
? 180421984
? 4294967295
! 75507200
? 4294836223
? 4294967295
? 4294967295
? 4294963199
! 75499008
! 3749410669
! 75499008
? 4294967295
? 4294966783
! 75499040
! 75499008
! 75499008
? 4294967295
! 75499009
! 75499008
? 4294967231
? 4294967295
? 4294967295
! 75499008
...

output:

0
0
1
1
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
0
0
0
1
1
0
0
1
0
1
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #74:

score: 20
Accepted
time: 931ms
memory: 521840kb

input:

32 1000000
! 2147483648
! 319300160
? 3967651749
! 319300160
! 97418808
! 1183167424
? 3984428965
! 319304256
? 3984428965
? 3984428965
? 3984428965
! 1613787186
? 3984428965
? 3982331813
? 3984428965
! 319300160
? 3984428965
! 2466783808
? 3984428965
? 3984560037
? 1841647044
! 319302208
? 80741478...

output:

1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
1
0
0
1
1
1
0
1
1
1
1
...

result:

ok Accepted.

Test #75:

score: 20
Accepted
time: 778ms
memory: 524664kb

input:

32 1000000
! 1293850081
! 48271617
! 1277072865
! 1293850081
? 868842913
! 1293850081
! 1293325793
! 1293850081
! 1298044385
! 1293850081
? 868842912
? 331972001
! 1293850081
? 868842913
! 1293849953
? 868842913
? 868842913
? 868834721
? 868840865
! 1293850080
! 1159632353
? 3016326561
? 868842913
?...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
...

result:

ok Accepted.

Test #76:

score: 20
Accepted
time: 1153ms
memory: 521660kb

input:

32 1000000
! 25174784
! 25174784
! 25174848
? 327808
! 25174816
! 25174528
? 393799546
? 387508074
! 159392512
? 389605226
? 389605226
? 926476138
? 402188138
! 25174800
? 389605226
! 25174784
! 26223360
? 356034410
? 389604202
! 58729216
! 58729216
? 389605226
! 159396608
! 25174856
! 562045696
! 2...

output:

0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
1
1
1
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
0
1
1
1
1
1
1
1
0
0
0
0
1
0
0
1
0
1
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
0
0
1
1
1
0
1
1
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #77:

score: 20
Accepted
time: 902ms
memory: 524508kb

input:

32 1000000
! 1087524524
? 3153034239
? 3153030143
? 3153034239
! 1116884648
! 1087524520
! 1104300712
? 4226776063
? 3153033983
! 1087532712
! 1079135912
? 1005550591
? 3152968695
? 3144645631
? 3148839935
? 3153034239
? 3153034237
? 3153034239
? 3152903167
! 1087524488
! 1087524520
? 3153034239
! 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok Accepted.

Test #78:

score: 20
Accepted
time: 854ms
memory: 516972kb

input:

32 1000000
! 805314624
? 404840470
? 405889046
! 536879168
! 536879184
? 405299222
! 2818580544
! 553657355
! 2685411392
? 404840470
? 404840454
? 16384
? 404842518
? 409034774
! 536879168
! 536879168
? 408969238
? 404840470
! 536895552
? 404840470
? 404840470
! 536879108
? 409034774
? 536870912
! 5...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
...

result:

ok Accepted.

Test #79:

score: 20
Accepted
time: 1578ms
memory: 514424kb

input:

32 1000000
! 2005090143
! 2005352399
? 4290740151
! 2005086175
? 4290609083
? 50397472
? 4290740159
! 2005090271
! 2005090271
? 3216998335
! 2005090271
? 4290740157
? 4290740159
? 4290740159
? 4223631295
! 1988313055
? 4290740158
? 4282351535
? 4290740159
! 1954758623
! 2005090271
! 4152573919
! 200...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
0
1
0
1
1
0
1
1
1
0
0
0
0
1
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
0
0
0
0
0
1
1
1
0
1
0
0
1
1
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
...

result:

ok Accepted.

Test #80:

score: 20
Accepted
time: 777ms
memory: 528000kb

input:

32 1000000
! 3875350091
! 3875286601
? 1216908055
! 4294967295
? 2950168507
! 3875352138
? 1286114055
! 3875343947
! 3875352139
! 3808243211
? 1284016919
? 1149799191
? 1284016919
! 3875350091
? 2009070871
? 1286113559
! 3875352139
? 1285065495
? 1284016919
? 3187660079
? 1275595543
! 3875352139
? 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok Accepted.

Extra Test:

score: 0
Extra Test Passed