QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#573432#8222. 投票游戏Arghariza100 ✓1145ms87456kbC++174.6kb2024-09-18 18:43:542024-09-18 18:43:54

Judging History

你现在查看的是最新测评结果

  • [2024-09-18 18:43:54]
  • 评测
  • 测评结果:100
  • 用时:1145ms
  • 内存:87456kb
  • [2024-09-18 18:43:54]
  • 提交

answer

// Problem: P10214 [CTS2024] 投票游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10214
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
bool Mbe;

mt19937 rnd(114514);
const int N = 2e5 + 5;
const ll inf = 1e18;

int n, q, dfc, a[N], b[N];
int fa[N], son[N], sz[N], dep[N], top[N], bot[N], id[N];
ll s[N], f[N];

vector<int> g[N];

struct Treap {
	int rt[N];
	struct S { 
		int lc, rc, id; 
		ll s, m; 
	} t[N];
	#define ls(x) t[x].lc
	#define rs(x) t[x].rc
	void pup(int x) {
		t[x].s = t[ls(x)].s + t[rs(x)].s + b[x];
		t[x].m = min(t[ls(x)].m, min(t[ls(x)].s + f[x], t[ls(x)].s + b[x] + t[rs(x)].m));
	}
	void spl(int p, ll k, int q, int &x, int &y) {
		if (!p) return x = y = 0, void();
		if (f[p] > k || (f[p] == k && p > q)) x = p, spl(rs(x), k, q, rs(x), y), pup(x);
		else y = p, spl(ls(y), k, q, x, ls(y)), pup(y);
	}
	int mrg(int x, int y) {
		if (!x || !y) return x | y;
		if (t[x].id < t[y].id) return rs(x) = mrg(rs(x), y), pup(x), x;
		else return ls(y) = mrg(x, ls(y)), pup(y), y;
	}
	ll qry(int p, ll k) {
		if (!p) return k;
		if (t[ls(p)].m < k) return qry(ls(p), k);
		if (t[ls(p)].s + f[p] < k) return k - t[ls(p)].s;
		return qry(rs(p), k - t[ls(p)].s - b[p]);
	}
	ll q(int v, ll k) { return qry(rt[v], k); }
	void i(int v) {
		if (v == 1) return;
		int u = fa[v], x, y; x = y = 0;
		spl(rt[u], f[v], v, x, y);
		t[v].m = f[v], t[v].s = b[v];
		rt[u] = mrg(x, mrg(v, y));
	}
	void e(int v) {
		if (v == 1) return;
		int u = fa[v], x, y, z; x = y = z = 0;
		spl(rt[u], f[v], v, x, y);
		spl(y, f[v], v - 1, y, z);
		rt[u] = mrg(x, z);
	}
	#undef ls
	#undef rs
} T1;

struct S {
	ll k, x, y;
	S () { }
	S (ll _k, ll _x, ll _y) :
	 	k(_k), x(_x), y(_y) { }
	ll q(ll p) { return p < k ? x : y; }
	S operator + (S rh) const { return S(k, rh.q(x), rh.q(y)); }
};

struct SEG {
	S t[N << 2];
	#define ls x << 1
	#define rs x << 1 | 1
	#define m ((l + r) >> 1)
	void pup(int x) { t[x] = t[rs] + t[ls]; }
	void upd(int l, int r, int p, S c, int x) {
		if (l == r) return t[x] = c, void();
		if (p <= m) upd(l, m, p, c, ls);
		else upd(m + 1, r, p, c, rs);
		pup(x);
	}
	S qry(int l, int r, int L, int R, int x) {
		if (L <= l && r <= R) return t[x];
		if (L > m) return qry(m + 1, r, L, R, rs);
		if (R <= m) return qry(l, m, L, R, ls);
		return qry(m + 1, r, L, R, rs) + qry(l, m, L, R, ls);
	}
	void u(int p, S c) { upd(1, n, p, c, 1); }
	S q(int l, int r) { return qry(1, n, l, r, 1); }
	#undef ls
	#undef rs
	#undef m
} T2;

S qg(int u) {
	if (!g[u].size()) return S(0, 0, a[u]);
	ll lim = T1.q(u, a[u] + s[u]);
	return S(lim, lim, T1.q(u, a[u] + s[u] - b[son[u]]));
}

ll qf(int u) {
	return T2.q(id[u], id[bot[u]]).q(0);
}

void dfs1(int u) {
	sz[u] = 1, dep[u] = dep[fa[u]] + 1;
	for (int v : g[u]) {
		dfs1(v), sz[u] += sz[v], s[u] += b[v];
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
	for (int v : g[u])
		if (v != son[u]) T1.i(v);
	f[u] = qg(u).q(f[son[u]]);
}

void dfs2(int u, int pr) {
	top[u] = pr, id[u] = ++dfc, T2.u(id[u], qg(u));
	if (!g[u].size()) return bot[u] = u, void();
	dfs2(son[u], pr), bot[u] = bot[son[u]];
	for (int v : g[u]) if (v != son[u]) dfs2(v, v);
}

void upd(int u) {
	while (top[u]) {
		T2.u(id[u], qg(u));
		T1.e(top[u]), f[top[u]] = qf(top[u]), T1.i(top[u]);
		u = fa[top[u]];
	}
}

void solve() {
	cin >> n >> q;
	for (int i = 2; i <= n; i++)
		cin >> fa[i], g[fa[i]].eb(i);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) T1.t[i].id = rnd();
	T1.t[0].m = inf;
	dfs1(1), dfs2(1, 1);
	while (q--) {
		int op, u, x, y; cin >> op;
		if (op == 1) {
			cin >> u >> x >> y;
			a[u] = x, upd(u);
			if (u == 1) continue;
			s[fa[u]] += y - b[u], b[u] = y;
			if (u != son[fa[u]]) T1.e(u), f[u] = qf(u), T1.i(u);
			upd(fa[u]);
		} else {
			cin >> x >> y;
			ll fx = qf(x), fy = qf(y);
			if (fx > fy || (fx == fy && x > y)) cout << 0 << '\n';
			else cout << 1 << '\n';
		}
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 20400kb

input:

20 500
1 1 3 1 3 5 6 6 7 3 5 3 9 5 4 7 7 18 2
42129194 82765784 1447057 29726963 82321558 32094641 22474113 49277574 27527633 20746795 47630926 92888389 26787144 80703040 43876864 97991729 12117966 75633318 33577855 93462601
69163546 49621952 45236756 46447931 34085269 55246550 54414402 99593046 103...

output:

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

result:

ok 238 numbers

Test #2:

score: 5
Accepted
time: 0ms
memory: 18360kb

input:

20 500
1 1 3 1 3 5 3 4 2 4 3 12 6 7 12 6 4 11 10
2 0 2 1 1 1 2 0 2 2 1 0 0 2 1 0 1 0 1 1
0 0 2 0 0 0 1 2 2 2 0 2 2 2 1 0 1 0 1 1
2 5 2
1 6 1 0
1 7 1 1
2 5 11
2 18 16
2 13 7
2 4 3
1 6 0 0
1 5 0 2
2 16 12
2 5 18
2 8 16
1 4 0 0
2 5 2
1 19 2 2
1 10 0 0
1 15 2 2
2 12 14
1 12 1 1
1 13 1 2
1 3 2 2
1 6 2 2
...

output:

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

result:

ok 226 numbers

Test #3:

score: 5
Accepted
time: 0ms
memory: 20456kb

input:

500 500
1 2 1 1 3 4 7 3 9 9 4 9 5 9 1 16 2 9 18 13 1 17 19 20 25 13 1 10 29 17 16 8 5 26 10 31 37 9 26 18 41 5 26 44 40 11 32 37 43 2 3 5 25 53 31 7 25 23 29 40 33 26 56 53 24 25 31 40 43 62 2 21 24 65 75 69 27 38 16 55 77 38 79 20 46 48 80 81 22 55 28 64 91 13 22 76 77 25 34 44 101 41 62 73 99 20 2...

output:

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

result:

ok 247 numbers

Test #4:

score: 5
Accepted
time: 0ms
memory: 20548kb

input:

500 500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

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

result:

ok 255 numbers

Test #5:

score: 5
Accepted
time: 3ms
memory: 18348kb

input:

500 500
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 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 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 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 1 1 1 1 1 1 ...

output:

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

result:

ok 243 numbers

Test #6:

score: 5
Accepted
time: 3ms
memory: 20492kb

input:

500 500
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

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

result:

ok 248 numbers

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #7:

score: 10
Accepted
time: 2ms
memory: 20408kb

input:

100 3000
1 1 2 1 3 4 1 4 7 8 1 9 5 7 2 9 7 7 1 3 20 22 16 18 23 15 24 4 14 1 21 4 21 32 14 14 33 28 13 4 20 27 41 43 18 26 4 8 24 16 30 16 13 45 20 46 6 17 4 48 24 23 54 59 61 42 62 41 26 35 10 40 9 41 35 68 67 63 48 53 10 59 81 54 15 22 86 69 49 52 55 3 27 52 48 15 54 16 87
32745005 92702519 399483...

output:

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

result:

ok 1494 numbers

Test #8:

score: 10
Accepted
time: 2ms
memory: 20436kb

input:

100 3000
1 2 3 1 1 5 7 7 1 3 3 6 7 9 12 2 11 5 19 20 10 16 7 7 3 22 16 24 5 27 22 13 24 24 24 25 5 11 16 22 40 26 6 39 14 2 46 21 43 50 20 27 28 7 54 41 55 16 36 26 38 46 4 29 63 12 45 64 28 47 53 33 28 28 44 17 27 36 41 22 39 55 32 79 57 64 76 48 45 45 61 69 73 67 68 92 36 66 73
0 1 2 2 0 0 1 0 2 1...

output:

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

result:

ok 1495 numbers

Test #9:

score: 10
Accepted
time: 3ms
memory: 20624kb

input:

3000 3000
1 1 2 1 1 4 7 1 1 9 6 7 1 14 11 1 16 6 17 20 4 18 4 21 22 23 17 19 20 15 6 22 4 2 28 16 19 19 24 2 31 38 20 33 1 44 13 21 10 42 40 27 4 34 25 22 15 53 43 12 11 31 54 24 31 27 16 43 41 69 23 38 70 66 58 60 7 60 30 61 28 26 14 30 55 22 49 37 31 6 59 22 39 8 56 17 35 67 1 63 43 6 82 41 56 30 ...

output:

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

result:

ok 1450 numbers

Test #10:

score: 10
Accepted
time: 4ms
memory: 21116kb

input:

3000 3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

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

result:

ok 1532 numbers

Test #11:

score: 10
Accepted
time: 7ms
memory: 22644kb

input:

3000 3000
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 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 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 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 1 1 1 1 1 ...

output:

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

result:

ok 1481 numbers

Test #12:

score: 10
Accepted
time: 0ms
memory: 21300kb

input:

3000 3000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

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

result:

ok 1541 numbers

Subtask #3:

score: 10
Accepted

Test #13:

score: 10
Accepted
time: 94ms
memory: 18432kb

input:

200 200000
1 2 3 3 5 3 1 6 2 9 11 5 5 2 4 9 17 8 1 4 10 20 18 20 23 13 16 28 15 4 6 27 26 11 30 25 10 2 13 23 25 35 4 8 40 43 36 26 7 27 45 35 14 31 54 45 9 8 9 54 16 32 62 9 29 2 43 39 34 39 27 2 52 56 6 9 48 26 66 28 35 57 79 13 71 61 38 43 80 26 61 26 79 1 24 64 79 15 41 42 56 55 6 24 92 43 89 76...

output:

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

result:

ok 100045 numbers

Test #14:

score: 10
Accepted
time: 100ms
memory: 20428kb

input:

200 200000
1 2 3 2 1 5 2 8 9 2 6 7 12 11 9 6 16 15 11 2 17 13 23 7 23 12 22 2 12 28 11 22 9 7 11 10 16 36 25 5 8 20 41 38 19 38 2 16 38 6 44 33 42 41 42 37 36 33 49 35 13 3 9 26 50 48 31 65 3 2 13 64 8 12 55 69 67 35 59 58 16 43 1 21 64 41 5 85 22 81 66 54 6 44 25 26 53 78 58 42 7 25 68 30 86 9 36 3...

output:

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

result:

ok 99983 numbers

Test #15:

score: 10
Accepted
time: 158ms
memory: 20360kb

input:

2000 200000
1 1 3 4 3 2 5 1 8 9 2 7 6 7 6 12 5 7 15 8 16 10 18 23 6 19 24 14 23 8 6 22 18 14 8 5 36 4 30 14 19 11 28 1 15 23 11 16 24 46 10 34 1 9 17 21 2 9 13 27 13 5 43 46 14 19 49 58 32 15 38 11 18 1 30 69 51 5 59 49 21 31 1 75 44 78 6 52 5 11 12 91 16 32 4 27 40 80 13 53 95 54 76 76 63 27 2 102 ...

output:

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

result:

ok 99757 numbers

Test #16:

score: 10
Accepted
time: 226ms
memory: 23280kb

input:

20000 200000
1 1 2 1 5 3 6 5 2 6 10 6 13 13 6 14 15 17 7 2 15 17 13 23 2 14 11 20 20 16 31 19 27 29 24 28 30 12 5 31 4 21 5 22 7 9 18 48 11 17 24 34 51 22 33 31 26 17 3 9 50 28 51 47 14 58 35 19 15 49 21 45 32 59 12 46 21 61 50 64 24 51 31 34 17 30 13 77 25 42 89 22 81 45 70 35 94 77 47 24 94 92 59 ...

output:

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

result:

ok 99952 numbers

Test #17:

score: 10
Accepted
time: 424ms
memory: 42172kb

input:

200000 200000
1 2 3 3 2 1 5 2 1 8 1 8 10 8 3 10 10 9 9 6 1 12 15 21 5 19 2 10 3 3 6 19 30 6 23 2 13 34 23 5 5 29 26 23 16 28 38 40 47 30 35 45 36 1 10 2 36 18 49 49 28 22 15 7 27 4 42 59 60 7 51 56 50 46 18 31 37 58 5 76 16 41 1 67 59 35 3 58 50 1 48 90 69 57 29 89 89 47 6 29 12 80 15 56 50 100 11 1...

output:

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

result:

ok 99519 numbers

Subtask #4:

score: 25
Accepted

Test #18:

score: 25
Accepted
time: 142ms
memory: 20240kb

input:

200 200000
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 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 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 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 1 1 1 1 1...

output:

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

result:

ok 99788 numbers

Test #19:

score: 25
Accepted
time: 152ms
memory: 20380kb

input:

200 200000
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 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 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 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 1 1 1 1 1...

output:

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

result:

ok 99818 numbers

Test #20:

score: 25
Accepted
time: 205ms
memory: 20532kb

input:

2000 200000
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 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 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 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 1 1 1 1 ...

output:

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

result:

ok 100002 numbers

Test #21:

score: 25
Accepted
time: 290ms
memory: 23784kb

input:

20000 200000
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 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 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 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 1 1 1 1...

output:

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

result:

ok 99886 numbers

Test #22:

score: 25
Accepted
time: 573ms
memory: 38880kb

input:

200000 200000
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 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 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 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 1 1 1 ...

output:

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

result:

ok 100006 numbers

Test #23:

score: 25
Accepted
time: 577ms
memory: 39520kb

input:

200000 200000
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 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 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 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 1 1 1 ...

output:

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

result:

ok 99439 numbers

Test #24:

score: 25
Accepted
time: 606ms
memory: 40964kb

input:

200000 200000
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 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 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 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 1 1 1 ...

output:

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

result:

ok 100458 numbers

Test #25:

score: 25
Accepted
time: 573ms
memory: 39048kb

input:

200000 200000
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 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 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 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 1 1 1 ...

output:

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

result:

ok 100269 numbers

Subtask #5:

score: 20
Accepted

Test #26:

score: 20
Accepted
time: 42ms
memory: 18472kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

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

result:

ok 100455 numbers

Test #27:

score: 20
Accepted
time: 51ms
memory: 20472kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

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

result:

ok 99902 numbers

Test #28:

score: 20
Accepted
time: 64ms
memory: 22940kb

input:

2000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

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

result:

ok 99882 numbers

Test #29:

score: 20
Accepted
time: 84ms
memory: 27496kb

input:

20000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

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

result:

ok 100151 numbers

Test #30:

score: 20
Accepted
time: 174ms
memory: 87368kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

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

result:

ok 100291 numbers

Test #31:

score: 20
Accepted
time: 168ms
memory: 85316kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

0
1
1
0
0
0
0
1
1
0
0
1
0
1
1
1
1
1
1
0
1
0
0
0
1
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
1
1
1
0
1
0
1
1
0
0
0
0
1
0
0
0
1
0
0
1
1
0
1
0
1
1
1
0
1
1
1
1
0
1
0
1
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
0
1
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
1
0
1
1
0
1
0
1
0
1
0
0
0
0
1
0
0
1
1
1
1
...

result:

ok 100358 numbers

Test #32:

score: 20
Accepted
time: 150ms
memory: 87456kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

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

result:

ok 66538 numbers

Subtask #6:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Test #33:

score: 30
Accepted
time: 1102ms
memory: 38996kb

input:

200000 200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 5...

output:

0
0
0
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
0
0
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
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
1
0
0
1
0
1
0
1
1
0
0
0
1
1
0
0
0
1
1
0
1
1
1
0
...

result:

ok 20048 numbers

Test #34:

score: 30
Accepted
time: 189ms
memory: 63292kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

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

result:

ok 66294 numbers

Test #35:

score: 30
Accepted
time: 55ms
memory: 20488kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

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

result:

ok 100092 numbers

Test #36:

score: 30
Accepted
time: 63ms
memory: 20972kb

input:

2000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

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

result:

ok 100456 numbers

Test #37:

score: 30
Accepted
time: 81ms
memory: 28144kb

input:

20000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

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

result:

ok 100428 numbers

Test #38:

score: 30
Accepted
time: 165ms
memory: 85388kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

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

result:

ok 99950 numbers

Test #39:

score: 30
Accepted
time: 165ms
memory: 87336kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

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

result:

ok 99920 numbers

Test #40:

score: 30
Accepted
time: 159ms
memory: 86172kb

input:

200000 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...

output:

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

result:

ok 100012 numbers

Test #41:

score: 30
Accepted
time: 46ms
memory: 20460kb

input:

200 200000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 1...

output:

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

result:

ok 99885 numbers

Test #42:

score: 30
Accepted
time: 1145ms
memory: 39464kb

input:

200000 200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 5...

output:

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

result:

ok 20265 numbers

Test #43:

score: 30
Accepted
time: 1054ms
memory: 40096kb

input:

200000 200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 5...

output:

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

result:

ok 20034 numbers

Test #44:

score: 30
Accepted
time: 982ms
memory: 38956kb

input:

200000 200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 5...

output:

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

result:

ok 20016 numbers

Test #45:

score: 30
Accepted
time: 765ms
memory: 39884kb

input:

200000 200000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 5...

output:

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

result:

ok 20088 numbers

Extra Test:

score: 0
Extra Test Passed