QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#751291#7785. Three Rectangleszhenghanyun#RE 876ms3884kbC++146.0kb2024-11-15 17:59:102024-11-15 17:59:10

Judging History

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

  • [2024-11-15 17:59:10]
  • 评测
  • 测评结果:RE
  • 用时:876ms
  • 内存:3884kb
  • [2024-11-15 17:59:10]
  • 提交

answer

#pragma GCC optimize(0)
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

ll T, W, H, ans, a[3], b[3], c[3], d[3];

inline void addmod(ll &x) {
	(x >= mod) && (x -= mod);
}

bitset <17> tmp[17];
vector <int> vec;

int a1[3], a2[3], b1[3], b2[3];

inline bool check() {
	bool flg1 = false, flg4 = false;
	for (int i = 0; i < 3; ++i) {
		flg1 |= (c[i] == 1);
	}
	for (int i = 0; i < 3; ++i) {
		flg4 |= (c[i] == 4);
	}
	if (!flg1 || !flg4) {
		return false;
	}
	for (int i = 0; i < 17; ++i) {
		tmp[i].reset();
	}
	for (int i = 0; i < 3; ++i) {
		a1[i] = 0, b1[i] = 0;
		a2[i] = 0, b2[i] = 0;
		if (c[i] == 1) {
			a1[i] = 0, b1[i] = 0;
			a2[i] = a[i], b2[i] = b[i];
		}
		if (c[i] == 2) {
			a1[i] = W - a[i], b1[i] = 0;
			a2[i] = W, b2[i] = b[i];
		}
		if (c[i] == 3) {
			a1[i] = 0, b1[i] = H - b[i];
			a2[i] = a[i], b2[i] = H;
		}
		if (c[i] == 4) {
			a1[i] = W - a[i], b1[i] = H - b[i];
			a2[i] = W, b2[i] = H;
		}
		if (c[i]) {
			vec.emplace_back(a1[i]);
			vec.emplace_back(a2[i]);
			vec.emplace_back(b1[i]);
			vec.emplace_back(b2[i]);
		}
	}
	vec.emplace_back(0);
	vec.emplace_back(H);
	vec.emplace_back(W);
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	for (int i = 0; i < 3; ++i) {
		a1[i] = lower_bound(vec.begin(), vec.end(), a1[i]) - vec.begin();
		b1[i] = lower_bound(vec.begin(), vec.end(), b1[i]) - vec.begin();
		a2[i] = lower_bound(vec.begin(), vec.end(), a2[i]) - vec.begin();
		b2[i] = lower_bound(vec.begin(), vec.end(), b2[i]) - vec.begin();
	}
	int w = lower_bound(vec.begin(), vec.end(), W) - vec.begin();
	int h = lower_bound(vec.begin(), vec.end(), H) - vec.begin();
	for (int i = 0; i < 3; ++i) {
		for (int j = a1[i]; j < a2[i]; ++j) {
			for (int k = b1[i]; k < b2[i]; ++k) {
				tmp[j][k] = 1;
			}
		}
	}
	for (int i = 0; i < w; ++i) {
		if ((int)tmp[i].count() != h) {
			return false;
		}
	}
	return true;
}

inline void calc() {
	ll t = 1;
	int cnt = 0;
	for (int i = 0; i < 3; ++i) {
		if (!c[i]) {
			t = t * d[i] % mod;
			++cnt;
		}
	}
	if (cnt >= 2) {
		return;
	}
	if (check()) {
		addmod(ans += t);
	}
}

inline void dfs(int u) {
	if (u == 3) {
		calc();
		return;
	}
	if (a[u] == W) {
		for (auto p: {0, 1, 4}) {
			c[u] = p;
			dfs(u + 1);
		}
	} else if (b[u] == H) {
		for (auto p: {0, 1, 4}) {
			c[u] = p;
			dfs(u + 1);
		}
	} else {
		for (auto p: {0, 1, 2, 3, 4}) {
			c[u] = p;
			dfs(u + 1);
		}
	}
}

inline void calc1(int x, int y, int z) {
	if (b[x] + b[z] >= H) {
		addmod(ans += H - 1 - b[y]);
	} else {
		int l = max(2ll, H - b[z] - b[y] + 1), r = min(H - b[y], b[x] + 1);
		if (l <= r) {
			addmod(ans += r - l + 1);
		}
	}
}

inline void calc2(int x, int y, int z) {
	if (max(b[x], b[y]) + b[z] >= H) {
		addmod(++ans);
	}
}

inline void solve() {
	cin >> W >> H;
	for (int i = 0; i < 3; ++i) {
		cin >> a[i] >> b[i];
	}
	ans = 0;
	for (int i = 0; i < 3; ++i) {
		if (a[i] == W && b[i] == H) {
			ans = 1;
			for (int j = 0; j < 3; ++j) {
				ans = ans * (W - a[j] + 1) % mod * (H - b[j] + 1) % mod;
			}
			cout << ans << "\n";
			return;
		}
	}
	bool flg = false;
	for (int i = 0; i < 3; ++i) {
		if (a[i] == W || b[i] == H) {
			flg = true;
		}
	}
	if (!flg) {
		cout << "0\n";
		return;
	}
	if (b[0] == H && b[1] == H && b[2] == H) {
		swap(H, W);
		swap(a[0], b[0]);
		swap(a[1], b[1]);
		swap(a[2], b[2]);
	}
	if (a[0] == W && a[1] == W && a[2] == W) {
		if (b[0] + b[1] + b[2] < H) {
			cout << "0\n";
			return;
		}
		calc1(0, 1, 2);
		calc1(0, 2, 1);
		calc1(1, 0, 2);
		calc1(1, 2, 0);
		calc1(2, 0, 1);
		calc1(2, 1, 0);
		calc2(0, 1, 2);
		calc2(0, 2, 1);
		calc2(1, 0, 2);
		calc2(1, 2, 0);
		calc2(2, 0, 1);
		calc2(2, 1, 0);
		cout << ans << "\n";
		return;
	}
	for (int i = 0; i < 3; ++i) {
		d[i] = (W - a[i] + 1) % mod * (H - b[i] + 1) % mod;
		if (a[i] == W || b[i] == H) {
			d[i] -= 2;
		} else {
			d[i] -= 4;
		}
	}
	dfs(0);
	cout << ans << "\n";
}

int main() {
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3508kb

input:

5
2 2
1 1
1 1
1 1
2 2
1 1
1 2
1 2
2 2
1 1
1 2
2 1
2 2
1 2
1 2
1 2
2 2
1 2
1 2
2 1

output:

0
8
4
6
4

result:

ok 5 number(s): "0 8 4 6 4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4
1 3
1 1
1 2
1 3
1 4
1 1
1 2
1 3
1 5
1 1
1 2
1 3
1 6
1 1
1 2
1 3

output:

6
12
14
6

result:

ok 4 number(s): "6 12 14 6"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

1
1000000000 1000000000
1 1
1 1
1000000000 1000000000

output:

2401

result:

ok 1 number(s): "2401"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

729
999999999 111111111
111111111 111111111
111111111 111111111
111111111 111111111
999999999 111111111
111111111 111111111
222222222 111111111
111111111 111111111
999999999 111111111
111111111 111111111
111111111 111111111
333333333 111111111
999999999 111111111
111111111 111111111
444444444 111111...

output:

0
0
0
0
0
0
6
777777753
456790164
0
0
0
0
0
6
222222208
555555531
135802502
0
0
0
0
6
222222208
222222208
333333309
814814847
0
0
0
6
222222208
222222208
222222208
111111087
493827185
0
0
6
222222208
222222208
222222208
222222208
888888872
172839523
0
6
222222208
222222208
222222208
222222208
222222...

result:

ok 729 numbers

Test #5:

score: 0
Accepted
time: 33ms
memory: 3876kb

input:

5832
999999999 222222222
111111111 111111111
111111111 111111111
111111111 111111111
222222222 999999999
111111111 111111111
111111111 111111111
111111111 222222222
222222222 999999999
111111111 111111111
111111111 111111111
111111111 333333333
999999999 222222222
111111111 111111111
111111111 11111...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
413046795
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
989330902
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
565615002
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
141899102
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
718183209
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
294467309
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
87...

result:

ok 5832 numbers

Test #6:

score: 0
Accepted
time: 123ms
memory: 3584kb

input:

19683
999999999 333333333
111111111 111111111
111111111 111111111
111111111 111111111
999999999 333333333
111111111 111111111
111111111 111111111
222222222 111111111
999999999 333333333
333333333 111111111
111111111 111111111
111111111 111111111
999999999 333333333
111111111 111111111
444444444 1111...

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
239292815
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
477213862
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
715134909
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
953055956
0
0
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 19683 numbers

Test #7:

score: 0
Accepted
time: 281ms
memory: 3580kb

input:

46656
999999999 444444444
111111111 111111111
111111111 111111111
111111111 111111111
999999999 444444444
111111111 111111111
111111111 111111111
222222222 111111111
444444444 999999999
111111111 333333333
111111111 111111111
111111111 111111111
999999999 444444444
444444444 111111111
111111111 1111...

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
935528231
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
599451396
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
263374561
0
0
0
0
0
0
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 46656 numbers

Test #8:

score: 0
Accepted
time: 523ms
memory: 3800kb

input:

91125
999999999 555555555
111111111 111111111
111111111 111111111
111111111 111111111
555555555 999999999
111111111 222222222
111111111 111111111
111111111 111111111
555555555 999999999
111111111 111111111
111111111 111111111
111111111 333333333
999999999 555555555
111111111 111111111
444444444 1111...

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
501753029
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
356043497
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
210333965
0
0
0
...

result:

ok 91125 numbers

Test #9:

score: 0
Accepted
time: 491ms
memory: 3672kb

input:

100000
666666666 999999999
111111111 111111111
111111111 111111111
111111111 111111111
999999999 666666666
222222222 111111111
111111111 111111111
111111111 111111111
666666666 999999999
111111111 111111111
111111111 111111111
111111111 333333333
999999999 666666666
111111111 111111111
444444444 111...

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
937967223
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
746990172
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #10:

score: 0
Accepted
time: 380ms
memory: 3636kb

input:

57464
666666666 999999999
444444444 888888888
222222222 777777777
666666666 222222222
999999999 666666666
333333333 666666666
888888888 444444444
777777777 222222222
999999999 666666666
444444444 666666666
777777777 222222222
888888888 444444444
666666666 999999999
666666666 555555555
222222222 7777...

output:

4
4
4
4
4
4
4
232891329
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
4
4
4
4
4
4
4
4
109586954
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
4
4
4
271604940
4
4
4
4
4
4
4
4
271604940
4
4
4
4
4
4
4
4
986282586
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 57464 numbers

Test #11:

score: 0
Accepted
time: 469ms
memory: 3632kb

input:

100000
777777777 999999999
111111111 111111111
111111111 111111111
111111111 111111111
999999999 777777777
222222222 111111111
111111111 111111111
111111111 111111111
777777777 999999999
111111111 111111111
111111111 111111111
111111111 333333333
777777777 999999999
111111111 111111111
111111111 111...

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
244170799
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
772291414
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #12:

score: 0
Accepted
time: 488ms
memory: 3628kb

input:

100000
999999999 777777777
222222222 333333333
444444444 222222222
888888888 333333333
999999999 777777777
444444444 222222222
888888888 333333333
333333333 333333333
999999999 777777777
888888888 333333333
444444444 222222222
444444444 333333333
999999999 777777777
888888888 333333333
444444444 222...

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
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
669562568
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
980643199
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #13:

score: 0
Accepted
time: 378ms
memory: 3580kb

input:

50047
777777777 999999999
555555555 333333333
333333333 777777777
666666666 666666666
999999999 777777777
777777777 333333333
666666666 666666666
444444444 555555555
777777777 999999999
666666666 666666666
333333333 777777777
555555555 555555555
777777777 999999999
555555555 666666666
333333333 7777...

output:

0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
4
4
4
4
4
4
356195704
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
4
4
4
4
4
4
377686331
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
4
296296298
0
0
4
4
4
4
4
4
296296298
0
...

result:

ok 50047 numbers

Test #14:

score: 0
Accepted
time: 460ms
memory: 3580kb

input:

100000
888888888 999999999
111111111 111111111
111111111 111111111
111111111 111111111
888888888 999999999
111111111 222222222
111111111 111111111
111111111 111111111
999999999 888888888
333333333 111111111
111111111 111111111
111111111 111111111
999999999 888888888
111111111 111111111
111111111 111...

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
420363771
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
431947...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 466ms
memory: 3864kb

input:

100000
888888888 999999999
888888888 222222222
333333333 333333333
333333333 222222222
888888888 999999999
333333333 222222222
333333333 333333333
888888888 333333333
999999999 888888888
333333333 333333333
444444444 888888888
222222222 333333333
999999999 888888888
222222222 333333333
333333333 333...

output:

0
0
0
0
0
0
0
638774850
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
584667189
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #16:

score: 0
Accepted
time: 475ms
memory: 3636kb

input:

100000
999999999 888888888
333333333 777777777
333333333 555555555
666666666 555555555
999999999 888888888
444444444 777777777
666666666 555555555
333333333 555555555
888888888 999999999
555555555 666666666
777777777 555555555
555555555 333333333
888888888 999999999
777777777 666666666
555555555 666...

output:

0
0
0
0
0
0
4
0
0
0
0
0
4
4
4
617283975
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
4
4
4
288065855
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
...

result:

ok 100000 numbers

Test #17:

score: 0
Accepted
time: 528ms
memory: 3636kb

input:

73248
888888888 999999999
777777777 444444444
666666666 444444444
777777777 999999999
888888888 999999999
666666666 555555555
777777777 999999999
777777777 444444444
999999999 888888888
666666666 666666666
444444444 777777777
999999999 777777777
999999999 888888888
444444444 777777777
999999999 7777...

output:

0
4
4
4
4
345679014
0
0
0
0
4
4
4
4
345679014
0
0
0
0
4
4
4
4
685871061
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
345679014
277091911
0
0
0
0
0
0
0
0
0
0
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 73248 numbers

Test #18:

score: 0
Accepted
time: 408ms
memory: 3804kb

input:

100000
999999999 999999999
111111111 111111111
111111111 111111111
111111111 111111111
999999999 999999999
111111111 222222222
111111111 111111111
111111111 111111111
999999999 999999999
111111111 333333333
111111111 111111111
111111111 111111111
999999999 999999999
111111111 111111111
111111111 111...

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
466546132
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #19:

score: 0
Accepted
time: 449ms
memory: 3840kb

input:

100000
999999999 999999999
333333333 222222222
666666666 222222222
222222222 777777777
999999999 999999999
333333333 666666666
222222222 333333333
777777777 222222222
999999999 999999999
222222222 777777777
333333333 222222222
666666666 444444444
999999999 999999999
222222222 333333333
555555555 666...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
783722091
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
480109819
0
0
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 100000 numbers

Test #20:

score: 0
Accepted
time: 448ms
memory: 3884kb

input:

100000
999999999 999999999
444444444 555555555
444444444 444444444
333333333 222222222
999999999 999999999
222222222 444444444
444444444 444444444
555555555 444444444
999999999 999999999
222222222 555555555
444444444 444444444
555555555 444444444
999999999 999999999
555555555 444444444
222222222 666...

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
4
4
4
4
243560539
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
0
0
0
0
...

result:

ok 100000 numbers

Test #21:

score: 0
Accepted
time: 414ms
memory: 3676kb

input:

100000
999999999 999999999
666666666 111111111
777777777 444444444
777777777 555555555
999999999 999999999
111111111 666666666
555555555 777777777
555555555 777777777
999999999 999999999
555555555 777777777
111111111 666666666
666666666 777777777
999999999 999999999
777777777 777777777
111111111 666...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
409236420
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
919067235
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #22:

score: 0
Accepted
time: 595ms
memory: 3572kb

input:

100000
999999999 999999999
777777777 999999999
555555555 333333333
777777777 777777777
999999999 999999999
333333333 666666666
999999999 777777777
777777777 777777777
999999999 999999999
999999999 777777777
777777777 777777777
333333333 777777777
999999999 999999999
333333333 888888888
999999999 777...

output:

4
4
4
4
4
0
4
4
4
4
4
4
4
4
0
4
4
4
4
4
4
4
4
0
4
4
4
4
4
4
4
4
0
4
4
4
4
4
4
4
4
0
4
4
4
4
4
4
4
4
0
98765434
98765434
98765434
98765434
98765434
98765434
98765434
72702332
0
0
0
0
0
0
0
0
0
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 233ms
memory: 3580kb

input:

31441
999999999 999999999
888888888 666666666
999999999 555555555
222222222 888888888
999999999 999999999
555555555 999999999
777777777 888888888
888888888 222222222
999999999 999999999
888888888 888888888
888888888 222222222
555555555 999999999
999999999 999999999
999999999 888888888
888888888 2222...

output:

4
4
4
4
0
0
0
395061730
395061730
395061730
395061730
395061730
50754460
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
888888890
0
0
0
4
4
4
4
4
888888890
0
0
0
555555549
555555549
555555549
555555549
555555549
456790140
0...

result:

ok 31441 numbers

Test #24:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

1000
1000000000 100000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 100000000
100000000 100000000
100000000 100000000
200000000 100000000
1000000000 100000000
100000000 100000000
100000000 100000000
300000000 100000000
100000000 1000000000
100000000 100000000
100000000 4...

output:

0
0
0
0
0
0
0
6
799999979
130000029
0
0
0
0
0
0
6
199999988
599999979
660000029
0
0
0
0
0
6
199999988
199999988
399999979
190000022
0
0
0
0
6
199999988
199999988
199999988
199999979
720000022
0
0
0
6
199999988
199999988
199999988
199999988
999999986
250000015
0
0
6
199999988
199999988
199999988
1999...

result:

ok 1000 numbers

Test #25:

score: 0
Accepted
time: 48ms
memory: 3592kb

input:

8000
200000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 200000000
100000000 100000000
100000000 100000000
200000000 100000000
1000000000 200000000
100000000 100000000
300000000 100000000
100000000 100000000
1000000000 200000000
400000000 100000000
100000000 1...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
781700008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
829400008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
877100008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
924800008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
972500008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
20200001
0
0
0
0
0
0
0...

result:

ok 8000 numbers

Test #26:

score: 0
Accepted
time: 176ms
memory: 3616kb

input:

27000
300000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
300000000 1000000000
100000000 100000000
100000000 200000000
100000000 100000000
1000000000 300000000
300000000 100000000
100000000 100000000
100000000 100000000
1000000000 300000000
100000000 100000000
100000000 ...

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
500800008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
585600008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
670400008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
755200008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 27000 numbers

Test #27:

score: 0
Accepted
time: 405ms
memory: 3580kb

input:

64000
1000000000 400000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 400000000
100000000 100000000
100000000 100000000
200000000 100000000
1000000000 400000000
300000000 100000000
100000000 100000000
100000000 100000000
400000000 1000000000
100000000 100000000
100000000 ...

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
287300036
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
928600036
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
569900029
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 64000 numbers

Test #28:

score: 0
Accepted
time: 540ms
memory: 3580kb

input:

100000
1000000000 500000000
100000000 100000000
100000000 100000000
100000000 100000000
500000000 1000000000
100000000 200000000
100000000 100000000
100000000 100000000
500000000 1000000000
100000000 100000000
100000000 100000000
100000000 300000000
500000000 1000000000
100000000 400000000
100000000...

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
141200092
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
858400085
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #29:

score: 0
Accepted
time: 208ms
memory: 3576kb

input:

25000
500000000 1000000000
500000000 100000000
100000000 100000000
100000000 100000000
1000000000 500000000
200000000 100000000
100000000 100000000
100000000 500000000
1000000000 500000000
300000000 100000000
100000000 500000000
100000000 100000000
500000000 1000000000
500000000 100000000
100000000 ...

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
560000023
365999952
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
920000023
411999959
0
0
0
0
0
0
0
0
0
0
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 25000 numbers

Test #30:

score: 0
Accepted
time: 493ms
memory: 3652kb

input:

100000
600000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 600000000
200000000 100000000
100000000 100000000
100000000 100000000
1000000000 600000000
100000000 100000000
300000000 100000000
100000000 100000000
1000000000 600000000
100000000 100000000
100000000...

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
62500176
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
375000155
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 100000 numbers

Test #31:

score: 0
Accepted
time: 618ms
memory: 3572kb

input:

100000
1000000000 600000000
100000000 500000000
800000000 300000000
700000000 500000000
600000000 1000000000
500000000 700000000
300000000 800000000
500000000 200000000
600000000 1000000000
500000000 700000000
300000000 800000000
500000000 300000000
600000000 1000000000
500000000 400000000
500000000...

output:

0
0
0
0
0
0
0
0
0
4
0
0
4
4
4
4
4
4
4
163600001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
4
4
4
4
4
4
4
4
150400001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
4
4
4
4
4
4
4
4
137200...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 120ms
memory: 3636kb

input:

16000
600000000 1000000000
300000000 100000000
600000000 600000000
400000000 400000000
1000000000 600000000
200000000 300000000
600000000 600000000
400000000 400000000
600000000 1000000000
600000000 600000000
300000000 300000000
400000000 400000000
1000000000 600000000
400000000 300000000
400000000 ...

output:

0
0
0
4
4
4
4
4
4
4
0
0
0
4
4
4
4
4
4
4
0
0
0
4
4
4
4
4
4
4
0
0
0
920000009
920000009
920000009
920000009
920000009
920000009
472000001
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
4
4
0
0
0
4
4
4
4
4
4
4
0
0
0
4
4
4
4
4
4
4
0
0
0
4
4
4
4
4
4
4
0
0
0
2
2
2
2
2
2
400000001
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
...

result:

ok 16000 numbers

Test #33:

score: 0
Accepted
time: 487ms
memory: 3616kb

input:

100000
700000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 700000000
200000000 100000000
100000000 100000000
100000000 100000000
700000000 1000000000
100000000 100000000
100000000 300000000
100000000 100000000
700000000 1000000000
100000000 400000000
100000000...

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
51200288
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
478400253
0
0
0...

result:

ok 100000 numbers

Test #34:

score: 0
Accepted
time: 488ms
memory: 3524kb

input:

100000
1000000000 700000000
900000000 300000000
100000000 500000000
100000000 300000000
1000000000 700000000
100000000 300000000
200000000 500000000
900000000 300000000
700000000 1000000000
300000000 100000000
300000000 900000000
500000000 300000000
700000000 1000000000
500000000 400000000
300000000...

output:

0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
878800001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
560000023
0
0
0
0
0
0
0
0
0
560000023
0
0
0
0
0
0
0
0
0
560000023
0
0
0
0
0
0
0
0
0
595999987
0
0
0
0
0
0
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 100000 numbers

Test #35:

score: 0
Accepted
time: 538ms
memory: 3572kb

input:

100000
700000000 1000000000
600000000 800000000
200000000 100000000
500000000 100000000
700000000 1000000000
600000000 800000000
200000000 200000000
500000000 100000000
1000000000 700000000
300000000 200000000
100000000 500000000
800000000 600000000
1000000000 700000000
400000000 200000000
100000000...

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
4
179200001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
4
115600001
0
0
0
0
0
0
0
0
4
680000...

result:

ok 100000 numbers

Test #36:

score: 0
Accepted
time: 374ms
memory: 3524kb

input:

43000
1000000000 700000000
600000000 200000000
200000000 700000000
100000000 600000000
1000000000 700000000
600000000 200000000
200000000 600000000
200000000 700000000
1000000000 700000000
600000000 200000000
300000000 600000000
200000000 700000000
1000000000 700000000
600000000 200000000
400000000 ...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
9
99999980
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
500000009
500000009
949999994
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 43000 numbers

Test #37:

score: 0
Accepted
time: 446ms
memory: 3612kb

input:

100000
800000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 800000000
200000000 100000000
100000000 100000000
100000000 100000000
1000000000 800000000
100000000 100000000
300000000 100000000
100000000 100000000
1000000000 800000000
100000000 100000000
100000000...

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
107300428
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #38:

score: 0
Accepted
time: 489ms
memory: 3672kb

input:

100000
1000000000 800000000
100000000 100000000
600000000 200000000
100000000 600000000
800000000 1000000000
100000000 200000000
600000000 100000000
200000000 600000000
800000000 1000000000
200000000 600000000
600000000 100000000
100000000 300000000
1000000000 800000000
100000000 600000000
600000000...

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
4
398400015
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #39:

score: 0
Accepted
time: 448ms
memory: 3524kb

input:

100000
800000000 1000000000
400000000 200000000
300000000 100000000
100000000 100000000
1000000000 800000000
200000000 100000000
200000000 400000000
100000000 300000000
1000000000 800000000
100000000 300000000
300000000 100000000
200000000 400000000
800000000 1000000000
300000000 100000000
400000000...

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
470000113
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #40:

score: 0
Accepted
time: 500ms
memory: 3572kb

input:

100000
1000000000 800000000
100000000 800000000
100000000 100000000
700000000 500000000
800000000 1000000000
500000000 700000000
100000000 200000000
800000000 100000000
800000000 1000000000
500000000 700000000
100000000 300000000
800000000 100000000
800000000 1000000000
500000000 700000000
100000000...

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
940000009
58999994
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #41:

score: 0
Accepted
time: 747ms
memory: 3836kb

input:

100000
1000000000 800000000
100000000 500000000
300000000 700000000
100000000 100000000
1000000000 800000000
100000000 500000000
200000000 100000000
300000000 700000000
800000000 1000000000
700000000 300000000
500000000 100000000
100000000 300000000
1000000000 800000000
100000000 500000000
400000000...

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
4
117299994
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #42:

score: 0
Accepted
time: 56ms
memory: 3636kb

input:

12000
800000000 1000000000
100000000 100000000
800000000 900000000
200000000 100000000
1000000000 800000000
100000000 200000000
900000000 800000000
200000000 100000000
800000000 1000000000
200000000 100000000
800000000 900000000
100000000 300000000
1000000000 800000000
400000000 100000000
100000000 ...

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
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
440000037
440000037
440000037
440000037
440000037
440000037
440000037
440000037
440000037
416000008
0
0
0
0
0
0
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 12000 numbers

Test #43:

score: 0
Accepted
time: 449ms
memory: 3840kb

input:

100000
900000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
900000000 1000000000
100000000 100000000
100000000 200000000
100000000 100000000
1000000000 900000000
100000000 100000000
100000000 100000000
300000000 100000000
900000000 1000000000
100000000 400000000
100000000...

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
230800596
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #44:

score: 0
Accepted
time: 442ms
memory: 3572kb

input:

100000
1000000000 900000000
200000000 400000000
100000000 200000000
300000000 200000000
900000000 1000000000
400000000 200000000
200000000 300000000
200000000 200000000
1000000000 900000000
200000000 400000000
300000000 200000000
300000000 200000000
1000000000 900000000
200000000 400000000
300000000...

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
155000176
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #45:

score: 0
Accepted
time: 467ms
memory: 3632kb

input:

100000
1000000000 900000000
500000000 300000000
300000000 700000000
100000000 300000000
900000000 1000000000
300000000 500000000
700000000 300000000
300000000 200000000
1000000000 900000000
300000000 300000000
500000000 300000000
300000000 700000000
900000000 1000000000
300000000 500000000
300000000...

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
4
4
4
360000015
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #46:

score: 0
Accepted
time: 472ms
memory: 3640kb

input:

100000
900000000 1000000000
400000000 100000000
100000000 400000000
400000000 800000000
1000000000 900000000
800000000 400000000
400000000 100000000
200000000 400000000
900000000 1000000000
400000000 300000000
100000000 400000000
400000000 800000000
1000000000 900000000
400000000 100000000
400000000...

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
4
0
0
0
0
0
0
0
0
0
40000015
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0...

result:

ok 100000 numbers

Test #47:

score: 0
Accepted
time: 474ms
memory: 3576kb

input:

100000
1000000000 900000000
100000000 500000000
1000000000 500000000
500000000 400000000
900000000 1000000000
500000000 200000000
400000000 500000000
500000000 1000000000
1000000000 900000000
500000000 400000000
300000000 500000000
1000000000 500000000
1000000000 900000000
500000000 400000000
400000...

output:

0
0
0
0
4
4
4
4
4
500000016
0
0
0
0
4
4
4
4
4
500000016
0
0
0
0
4
4
4
4
4
500000016
0
0
0
0
4
4
4
4
4
500000016
0
0
0
0
4
4
4
4
4
749999994
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
4
9
0
0
0
4
4
4
4
4
4
9
0
0
0
4
4
4
4
4
4
9
0
0
0
4
4
4
4
4
4
9
0
0
0
4
4
4
4
4
4
9
...

result:

ok 100000 numbers

Test #48:

score: 0
Accepted
time: 458ms
memory: 3632kb

input:

100000
900000000 1000000000
600000000 100000000
700000000 600000000
700000000 200000000
1000000000 900000000
600000000 700000000
200000000 700000000
200000000 600000000
1000000000 900000000
600000000 700000000
200000000 700000000
300000000 600000000
900000000 1000000000
700000000 600000000
700000000...

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
4
4
953600008
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
27200001
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 100000 numbers

Test #49:

score: 0
Accepted
time: 763ms
memory: 3572kb

input:

100000
1000000000 900000000
100000000 700000000
500000000 800000000
700000000 100000000
900000000 1000000000
800000000 500000000
700000000 200000000
100000000 700000000
900000000 1000000000
700000000 300000000
100000000 700000000
800000000 500000000
1000000000 900000000
500000000 800000000
400000000...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
4
4
4
4
4
685000001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
4
4
4
4
4
340000001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 100000 numbers

Test #50:

score: 0
Accepted
time: 215ms
memory: 3868kb

input:

29000
900000000 1000000000
400000000 800000000
900000000 700000000
800000000 100000000
900000000 1000000000
800000000 200000000
900000000 700000000
400000000 800000000
1000000000 900000000
300000000 800000000
700000000 900000000
800000000 400000000
1000000000 900000000
400000000 800000000
700000000 ...

output:

0
0
4
4
4
4
4
4
4
4
0
0
2
2
2
2
2
2
2
300000001
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
4
4
4
4
4
4
4
0
0
4
4
4
4
4
4
4
4
0
0
4
4
4
4
4
4
4
4
0
0
4
4
4
4
4
4
4
4
0
0
500000002
500000002
500000002
500000002
500000002
500000002
500000002
25000001
0
0
0
0
0...

result:

ok 29000 numbers

Test #51:

score: 0
Accepted
time: 430ms
memory: 3872kb

input:

100000
1000000000 1000000000
100000000 100000000
100000000 100000000
100000000 100000000
1000000000 1000000000
200000000 100000000
100000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
100000000 100000000
100000000 300000000
1000000000 1000000000
100000000 100000000
10000...

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
421700792
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #52:

score: 0
Accepted
time: 429ms
memory: 3636kb

input:

100000
1000000000 1000000000
100000000 100000000
200000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
200000000 100000000
100000000 200000000
1000000000 1000000000
200000000 100000000
100000000 100000000
100000000 300000000
1000000000 1000000000
100000000 400000000
10000...

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
309400687
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #53:

score: 0
Accepted
time: 427ms
memory: 3632kb

input:

100000
1000000000 1000000000
100000000 300000000
100000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
300000000 100000000
100000000 200000000
1000000000 1000000000
100000000 300000000
100000000 100000000
300000000 100000000
1000000000 1000000000
400000000 100000000
10000...

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
197100582
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #54:

score: 0
Accepted
time: 432ms
memory: 3576kb

input:

100000
1000000000 1000000000
100000000 100000000
400000000 100000000
100000000 100000000
1000000000 1000000000
100000000 400000000
100000000 100000000
200000000 100000000
1000000000 1000000000
400000000 100000000
100000000 300000000
100000000 100000000
1000000000 1000000000
400000000 100000000
10000...

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
84800477
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #55:

score: 0
Accepted
time: 431ms
memory: 3612kb

input:

100000
1000000000 1000000000
500000000 100000000
100000000 100000000
100000000 100000000
1000000000 1000000000
100000000 200000000
100000000 100000000
500000000 100000000
1000000000 1000000000
500000000 100000000
100000000 300000000
100000000 100000000
1000000000 1000000000
500000000 100000000
10000...

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
972500379
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #56:

score: 0
Accepted
time: 433ms
memory: 3580kb

input:

100000
1000000000 1000000000
100000000 100000000
100000000 100000000
100000000 600000000
1000000000 1000000000
200000000 100000000
100000000 100000000
100000000 600000000
1000000000 1000000000
100000000 600000000
300000000 100000000
100000000 100000000
1000000000 1000000000
400000000 100000000
10000...

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
860200274
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #57:

score: 0
Accepted
time: 435ms
memory: 3800kb

input:

100000
1000000000 1000000000
700000000 100000000
100000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
100000000 700000000
200000000 100000000
1000000000 1000000000
100000000 300000000
700000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
10000...

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
747900169
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #58:

score: 0
Accepted
time: 438ms
memory: 3640kb

input:

100000
1000000000 1000000000
100000000 100000000
100000000 100000000
100000000 800000000
1000000000 1000000000
800000000 100000000
100000000 200000000
100000000 100000000
1000000000 1000000000
800000000 100000000
100000000 100000000
100000000 300000000
1000000000 1000000000
100000000 100000000
80000...

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
635600064
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #59:

score: 0
Accepted
time: 437ms
memory: 3580kb

input:

100000
1000000000 1000000000
100000000 100000000
900000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
200000000 100000000
100000000 900000000
1000000000 1000000000
100000000 900000000
300000000 100000000
100000000 100000000
1000000000 1000000000
100000000 100000000
40000...

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
4
523299959
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #60:

score: 0
Accepted
time: 876ms
memory: 3576kb

input:

100000
1000000000 1000000000
100000000 100000000
100000000 1000000000
100000000 100000000
1000000000 1000000000
100000000 1000000000
100000000 100000000
200000000 100000000
1000000000 1000000000
100000000 100000000
100000000 1000000000
300000000 100000000
1000000000 1000000000
100000000 1000000000
4...

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
260000058
410999854
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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 100000 numbers

Test #61:

score: 0
Accepted
time: 44ms
memory: 3868kb

input:

100000
1000000000 1
314767347 1
401480838 1
962869370 1
1 1000000000
1 300605537
1 452371272
1 714371039
1000000000 1
692258752 1
458061953 1
903813193 1
1000000000 1
948907155 1
842561780 1
505547119 1
1000000000 1
227671321 1
201359338 1
42727883 1
1000000000 1
970200687 1
720287254 1
122745417 1
...

output:

641764876
65304283
891732197
405967885
0
373533270
487633180
0
670957928
0
80323388
134325066
901949409
0
0
492708780
0
254708946
0
139947806
939646701
23274430
977920194
911438556
72215223
192320750
0
96858838
509009004
124689652
642434874
0
988588335
52694994
478427310
737301687
906116646
29591256...

result:

ok 100000 numbers

Test #62:

score: -100
Runtime Error

input:

100000
10 1000000000
9 818486248
10 663863160
2 977086633
1000000000 10
187658309 6
482879526 6
40917464 1
1000000000 10
898562223 9
6782488 6
658633682 10
1000000000 10
73041819 5
145421660 3
57420175 3
10 1000000000
2 984444596
3 286943561
9 133266971
1000000000 10
280189449 8
279915192 6
51411986...

output:


result: