QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#50809#967. Rectangle PaintingCrysflyAC ✓1519ms188116kbC++113.2kb2022-09-29 14:35:502022-09-29 14:35:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-29 14:35:52]
  • 评测
  • 测评结果:AC
  • 用时:1519ms
  • 内存:188116kb
  • [2022-09-29 14:35:50]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

/*
线段树上每个点 维护哪种最小y坐标没出现(NY)
一个点的权值 = 所有祖先里的 minNY
求 权值最大 可以线段树维护

如果直接做会有问题 ,要转化成不相交的区间 
*/

int n=200000,Q;
int val[maxn<<3];
set<int>sv[maxn<<3];
void upd(int p,int l,int r){
	if(l==r){
		if(sv[p].size()) val[p]=(*sv[p].begin());
		else val[p]=inf;
	}else{
		val[p]=max(val[p<<1],val[p<<1|1]);
		if(sv[p].size())val[p]=min(val[p],*sv[p].begin());
	}
}
void build(int p,int l,int r){
	if(l==r)return upd(p,l,r);
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r),upd(p,l,r);
}
void del(int p,int l,int r,int nl,int nr,int x)
{
//	cout<<"del "<<p<<' '<<l<<" "<<r<<" "<<nl<<" "<<nr<<' '<<x<<endl;
	int mid=l+r>>1;
	if(sv[p].count(x)){
		sv[p].erase(x);
		upd(p,l,r);
		if(l>=nl&&r<=nr)return;
		if(l!=r){
			sv[p<<1].insert(x),sv[p<<1|1].insert(x);
			upd(p<<1,l,mid),upd(p<<1|1,mid+1,r);
		}
	}
	if(l>=nl&&r<=nr)return;
	if(nl<=mid)del(p<<1,l,mid,nl,nr,x);
	if(nr>mid)del(p<<1|1,mid+1,r,nl,nr,x);
	upd(p,l,r);
}
int ask(int p,int l,int r,int ql,int qr)
{
	if(l>=ql && r<=qr) return val[p];
	int mid=l+r>>1,res=0;
	if(ql<=mid)res=max(res,ask(p<<1,l,mid,ql,qr));
	if(qr>mid)res=max(res,ask(p<<1|1,mid+1,r,ql,qr));
	if(sv[p].size())res=min(res,*sv[p].begin());
	return res;
}

set<pii>s[maxn];

void add(int x,int l,int r)
{
	set<pii>::iterator it=s[x].lower_bound(mkp(l,0));
	if(it!=s[x].begin()){
		--it;
		if((it->se)>=l)
			s[x].insert(mkp(it->fi,l-1)),s[x].insert(mkp(l,it->se)),s[x].erase(it);
	}
	it=s[x].lower_bound(mkp(r+1,0));
	if(it!=s[x].begin()){
		--it;
		if((it->se)>=r+1)
			s[x].insert(mkp(it->fi,r)),s[x].insert(mkp(r+1,it->se)),s[x].erase(it);
	}
//	cout<<"set x "<<x<<endl;
//	for(auto it:s[x])cout<<it.fi<<' '<<it.se<<endl;
	int lst=l;
	while(1){
		it=s[x].lower_bound(mkp(l,0));
		if(it==s[x].end() || (it->fi)>r)break;
//		cout<<"it : "<<(it->fi)<<' '<<(it->se)<<endl;
		if(lst<=((it->fi)-1)) del(1,0,n,lst,((it->fi)-1),x);
		lst=((it->se)+1); s[x].erase(it);
	}
	if(lst<=r) del(1,0,n,lst,r,x);
	s[x].insert(mkp(l,r));
}

signed main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	For(i,0,1000000) sv[1].insert(i);
	build(1,0,n);
	int sum=0;
	Q=read();
	while(Q--)
	{
		int o=read(),l,r,x;
		if(o==1){
			x=read()^sum,l=read()^sum,r=read()^sum;
			if(x>100000)exit(233);
//			cout<<"add "<<x<<" "<<l<<' '<<r<<endl;
			add(x,l,r);
		}else{
			l=read()^sum,r=read()^sum;
			int res=ask(1,0,n,l,r);
//			cout<<"ask "<<l<<' '<<r<<endl;
			printf("%lld\n",res);sum+=res;
		}
	}
	return 0;
}
/*
10
1 0 1 1
2 0 10
1 1 9 9
1 0 0 6
1 0 3 9
2 5 5
1 1 5 5
2 5 5
2 0 5
1 7 6 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 282ms
memory: 139116kb

input:

10
1 0 1 1
2 0 10
1 1 9 9
1 0 0 6
1 0 3 9
2 5 5
1 1 5 5
2 5 5
2 0 5
1 7 6 3

output:

1
0
2
2

result:

ok 4 number(s): "1 0 2 2"

Test #2:

score: 0
Accepted
time: 282ms
memory: 139244kb

input:

2000
2 153178 192444
2 72041 76242
2 108647 126098
2 43869 69154
1 3 129701 129701
2 79398 171270
1 4 143595 143595
2 72333 171873
1 1 30279 30279
2 33775 47249
2 58699 176337
1 0 80524 80524
2 26438 130141
1 7 95801 95801
2 69894 119377
2 183011 188834
1 5 168191 168191
2 33779 117396
1 10 80932 80...

output:

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

result:

ok 857 numbers

Test #3:

score: 0
Accepted
time: 253ms
memory: 139268kb

input:

2000
2 67566 106655
1 1 100283 100283
2 43046 116908
2 60835 82549
1 3 176933 176933
2 54288 127706
1 4 80654 80654
2 112399 124519
1 2 929 929
2 65749 94670
1 6 162357 162357
2 11815 134033
2 18338 83153
1 5 64820 64820
2 77289 185584
1 9 17010 17010
2 28793 100018
2 51870 80061
2 18525 189575
2 79...

output:

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
1
1
1
1
0
0
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
1
1
0
1
1
1
1
0
1
1
0
1
1
0
1
1
1
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
0
0
0
0
1
0
0
1
1
0
0
13
13
8
0
0
0
0
13
13
13
13
13
5
0
13
13
13
8
8
8
8
5
4
4
4
4
4
4
14
14
4
14
14
14
14
4
...

result:

ok 597 numbers

Test #4:

score: 0
Accepted
time: 330ms
memory: 140076kb

input:

20000
1 0 181305 181305
2 37421 133713
2 95994 132557
2 76711 148862
2 103255 140002
1 2 162129 162129
2 88465 150764
1 5 168234 168234
2 31887 161917
1 1 129575 129575
2 44602 74661
2 20290 109569
2 25608 100437
1 4 134899 134899
2 55877 149126
1 6 158627 158627
2 141147 193270
2 8020 76253
2 10651...

output:

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

result:

ok 6008 numbers

Test #5:

score: 0
Accepted
time: 315ms
memory: 139936kb

input:

20000
2 16442 77982
2 48496 56448
2 118215 139097
2 48283 133116
2 128483 173973
2 73095 81397
2 72240 173277
2 114845 177266
1 6 37698 37698
2 76121 98968
2 88182 116321
2 28442 53119
2 25619 41573
2 31511 181384
1 2 56085 56085
2 47484 148072
2 110358 130683
1 1 133334 133334
2 72503 115178
2 8159...

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
1
0
1
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
7
0
7
0
0
0
7
7
3
7
3
1
1
1
7
7
1
7
1
1
7
7
1
7
1
7
1
7
7
1
1
1
7
1
1
1
7
7
1
7
1
7
11
7
7
7
11
7
8
8
17
11
17
21
17
17
21
17
17
21
17...

result:

ok 5742 numbers

Test #6:

score: 0
Accepted
time: 444ms
memory: 143128kb

input:

100000
2 135246 179378
2 115743 127133
2 2821 36201
1 0 119698 119698
2 129799 196907
1 3 40006 40006
2 64340 153669
1 5 104122 104122
2 37429 94126
2 24343 158125
1 5 46029 46029
2 77257 104944
1 3 157300 157300
2 92992 133515
1 6 149126 149126
2 12105 114987
2 35040 78230
2 27965 147202
1 13 12201...

output:

0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
1
0
0
1
1
1
0
1
0
1
1
0
1
1
1
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
0
1
0
0
2
0
2
0
2
2
2
2
0
2
2
0
0
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
37
37
37
32
9
...

result:

ok 28629 numbers

Test #7:

score: 0
Accepted
time: 1286ms
memory: 177876kb

input:

100000
1 43200 18594 63210
2 72098 72349
1 20075 42660 112018
2 69680 183617
1 5878 41207 142773
2 143863 185265
1 4814 40968 73548
2 59718 189403
1 11320 40455 195383
2 150206 157014
1 28986 21582 114797
2 1386 53297
1 2450 32350 106046
2 115147 152403
1 28074 9105 88821
2 56330 89790
1 3056 42653 ...

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 50000 numbers

Test #8:

score: 0
Accepted
time: 292ms
memory: 139760kb

input:

2000
1 787 81832 84078
2 10341 51540
1 144 4524 89443
2 72800 84564
1 475 52302 90668
2 21526 87668
1 362 24827 84537
2 1908 92812
1 951 40290 91298
2 13923 62852
1 992 8083 86600
2 92307 97953
1 610 30171 85746
2 3435 37819
1 301 28582 98721
2 62330 94061
1 147 78555 90167
2 37902 84444
1 421 31070...

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 1000 numbers

Test #9:

score: 0
Accepted
time: 440ms
memory: 144500kb

input:

100000
2 48687 48694
1 0 0 3336
1 0 3826 5842
1 0 10932 11412
1 0 5843 10930
1 0 11612 11673
1 0 11674 12354
2 14313 30590
1 0 12412 12459
1 0 11413 11599
1 0 15846 21183
2 40249 49418
1 0 21184 21322
1 0 22841 22850
2 37854 42966
2 17280 18917
2 23008 23015
1 1 12481 12511
1 1 13695 15070
2 24357 2...

output:

0
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
1
1
2
1
1
1
2
0
2
0
1
1
1
1
1
1
1
2
2
2
1
1
2
1
3
2
3
3
1
2
0
3
1
4
1
3
2
2
3
2
3
2
3
2
3
2
1
4
5
5
5
5
1
6
3
4
2
3
6
6
6
4
6
1
3
6
3
4
3
3
3
4
6
3
1
3
4
7
7
3
7
4
4
3
6
1
2
7
2
4
8
4
5
9
4
3
3
1
4
1
8
6
1
8
3
6
3
4
5
3
3
4
5
8
4
8
5
8
6
1
3
9
4
5
3
4
1
...

result:

ok 40064 numbers

Test #10:

score: 0
Accepted
time: 375ms
memory: 144212kb

input:

100000
1 0 203 460
2 26083 26083
1 0 490 871
1 0 0 201
1 0 3195 3204
1 0 6170 6390
1 0 873 2978
1 0 6391 6428
2 9070 30739
1 0 3206 5264
2 44512 47314
1 0 2979 3194
1 0 7534 7540
1 0 5266 6168
1 0 8322 8717
1 0 8718 9679
2 17894 37370
1 0 9733 10352
2 9653 9663
1 1 6441 6589
1 1 8034 8123
1 1 7248 7...

output:

0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
0
1
1
0
1
0
0
1
1
1
1
0
0
0
1
1
1
1
1
0
1
1
0
1
1
0
1
1
1
0
0
0
0
0
1
0
0
1
1
1
1
1
1
0
1
0
1
1
1
1
1
1
0
1
1
0
1
0
1
1
1
1
1
0
0
1
0
1
1
1
1
2
0
1
1
2
0
1
1
1
1
1
1
1
1
0
2
1
1
1
1
1
1
1
1
2
1
0
2
1
1
2
2
2
1
2
2
1
1
0
2
2
2
2
1
0
1
1
2
1
2
...

result:

ok 39960 numbers

Test #11:

score: 0
Accepted
time: 461ms
memory: 144840kb

input:

100000
2 12619 12622
1 0 0 4254
1 0 12882 15143
1 0 15144 16373
2 44313 44314
2 22451 42025
2 20422 43838
1 0 16374 16522
2 33128 35298
1 0 16524 17136
2 8487 8662
1 0 24192 26981
1 0 26983 27157
1 0 27158 27322
1 0 30550 31091
2 10175 47354
1 1 27633 28625
1 0 3997 4975
2 14604 14607
2 4421 4430
1 ...

output:

0
0
0
0
0
0
1
1
0
0
2
0
2
2
1
0
1
2
3
3
1
3
0
3
4
4
4
3
4
0
3
3
3
4
2
7
0
7
7
4
4
4
0
4
0
8
4
8
8
3
3
8
4
4
3
4
2
4
4
4
4
8
4
8
3
7
7
7
4
8
3
4
7
3
8
7
7
4
3
0
3
8
8
8
9
9
3
7
9
9
3
9
7
7
3
8
1
9
8
3
3
8
7
7
7
8
8
7
9
9
3
7
9
3
7
3
7
7
9
9
9
9
9
9
7
8
7
9
9
11
7
16
16
7
8
16
8
16
7
7
7
18
18
18
16
1...

result:

ok 39736 numbers

Test #12:

score: 0
Accepted
time: 268ms
memory: 139608kb

input:

2000
2 604 5580
1 0 0 3873
1 0 3875 6716
2 3465 3468
1 1 8989 9998
1 0 1932 9998
1 0 1 1930
1 3 9261 9998
1 2 1311 1436
1 5 1 4683
1 3 1 8170
1 4 6045 9998
1 1 6719 8029
2 4507 5553
1 2 4 1123
1 0 4680 9995
2 876 884
2 6483 7766
2 3303 3932
1 14 6113 9986
1 8 13 6039
1 5 13 712
1 14 2077 6119
1 4 21...

output:

0
1
3
3
3
3
6
6
6
7
8
7
3
3
8
7
7
9
9
7
7
9
7
9
7
7
7
9
7
3
10
8
10
11
10
12
10
12
12
12
10
12
12
10
12
10
10
12
12
12
12
12
12
12
7
12
10
13
15
13
15
15
15
10
15
15
10
13
10
15
10
13
15
15
15
13
10
10
18
15
15
15
15
18
18
15
18
18
18
18
10
18
18
18
15
18
18
10
18
10
15
18
18
10
10
15
18
18
10
18
10...

result:

ok 730 numbers

Test #13:

score: 0
Accepted
time: 341ms
memory: 142212kb

input:

40000
1 0 0 2154
1 0 10459 18923
2 31930 50633
1 0 37733 46882
1 0 18925 37731
1 0 67919 69516
1 0 66291 67917
1 0 52858 66289
1 1 0 520
1 1 47180 48570
1 0 46884 52856
1 0 2156 10457
2 29645 61202
1 3 520 12111
1 3 12109 25046
1 3 25044 47176
2 66023 78949
2 15131 16308
1 7 31250 32497
2 48233 4823...

output:

0
2
1
2
2
2
3
3
3
2
3
4
2
3
3
4
4
4
3
1
2
7
4
7
2
4
3
1
2
2
3
3
5
7
6
7
7
7
3
2
5
6
4
4
5
9
6
4
9
9
4
9
6
5
5
7
4
3
9
5
9
11
5
9
8
11
12
11
12
12
11
10
3
11
11
11
10
3
6
8
10
12
2
7
12
13
8
14
14
7
7
14
10
12
14
12
14
13
16
8
13
11
14
7
16
14
12
14
14
7
14
14
12
14
10
12
13
14
14
13
14
10
17
14
14
1...

result:

ok 16017 numbers

Test #14:

score: 0
Accepted
time: 272ms
memory: 139080kb

input:

100
1 0 0 12471
1 0 69290 77076
2 43248 43258
2 91387 91395
1 0 90535 93999
1 0 77078 90533
1 0 12473 38210
1 1 0 40815
2 36963 49184
1 3 40819 62026
1 0 2 5843
1 1 86379 86904
1 3 64321 75865
2 48741 49337
2 14129 78750
1 7 86904 93995
2 66132 66129
2 60093 83058
2 81921 81933
1 3 21471 34359
2 597...

output:

0
0
2
0
2
0
2
1
0
2
2
2
1
2
2
1
3
2
2
3
3
5
2
2
1
1
2
2
5
1
5
5
2
2
5
5
2
8

result:

ok 38 numbers

Test #15:

score: 0
Accepted
time: 1087ms
memory: 177844kb

input:

100000
1 0 9050 82367
2 5166 59560
1 0 30955 150882
2 5194 187535
1 1 24808 63504
2 78723 96650
1 6 1943 183696
2 2985 137459
1 13 6293 150010
2 102838 154866
1 12 46597 95573
2 13581 159175
1 9 33193 182719
2 12098 194451
1 17 11278 51325
2 54102 102803
1 21 34211 82256
2 63681 90622
1 22 36741 702...

output:

1
2
2
4
0
6
7
7
2
2
0
0
7
14
2
16
0
7
0
0
0
0
2
24
25
0
27
0
2
0
31
0
33
34
35
0
0
38
39
40
41
0
0
1
0
46
0
48
49
0
2
0
0
2
0
56
57
7
59
0
0
62
0
0
65
66
67
68
7
0
2
72
0
74
75
0
0
0
79
80
7
82
2
0
85
0
0
88
0
90
91
92
0
94
95
96
0
0
2
0
1
102
2
104
0
0
0
108
2
110
111
112
113
0
0
0
1
118
0
5
7
2
0
...

result:

ok 50000 numbers

Test #16:

score: 0
Accepted
time: 351ms
memory: 139108kb

input:

100000
1 0 9050 82367
2 5166 59560
1 1 30955 150882
2 5194 187535
1 2 24809 63505
2 78722 96651
1 3 1937 183702
2 2991 137461
1 4 6296 150007
2 102843 154879
1 5 46601 95577
2 13569 159179
1 6 33184 182710
2 12107 194458
1 7 11295 51308
2 54087 102786
1 8 34230 82245
2 63700 90603
1 9 36755 70212
2 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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 50000 numbers

Test #17:

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

input:

100000
1 2 19246 19246
1 1 146631 146631
1 0 20450 20450
1 7 160118 160118
2 6827 104214
1 7 125259 125259
1 4 125799 125799
1 12 170833 170833
1 17 57693 57693
1 10 184939 184939
1 11 135794 135794
1 13 95724 95724
1 5 196976 196976
1 25 71318 71318
1 16 156302 156302
1 24 137393 137393
1 36 32333 ...

output:

1
0
2
15
67
224
224
224
216
216
252
397
386
444
500
556
556
666
525
708
891
832
891
891
1082
1019
1025
1105
1137
1137
1198
1288
1288
1288
1324
1285
1346
1607
1585
1585
1665
1858
1858
1858
1880
1981
1986
2039
2170
2170
2170
2189
2319
2301
2301
2324
2399
2399
2399
2536
2667
2692
2808
2945
2945
2945
29...

result:

ok 810 numbers

Test #18:

score: 0
Accepted
time: 331ms
memory: 139000kb

input:

100000
2 52090 64166
2 58436 154827
2 4299 165689
2 4423 25871
2 96833 177988
2 32990 149906
2 129836 177211
2 85737 94049
2 134925 157468
2 9824 50932
2 15650 147198
2 21623 114239
2 12026 151306
2 62831 148386
2 10475 150697
2 26837 74702
2 80936 111038
2 81363 182551
2 83881 136073
2 8049 73068
2...

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

Test #19:

score: 0
Accepted
time: 322ms
memory: 139368kb

input:

100000
1 0 91119 91119
2 36259 134493
2 50248 106240
2 9466 158699
2 151568 158401
2 36207 134652
2 85062 134312
2 120317 178728
2 150032 162896
2 88424 114608
2 136357 171049
2 17035 134628
2 110908 115574
2 17770 114555
2 46869 74803
2 52276 119673
2 145379 174323
2 40108 192332
2 178470 180226
2 ...

output:

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

result:

ok 95171 numbers

Test #20:

score: 0
Accepted
time: 401ms
memory: 144652kb

input:

100000
1 0 0 105757
1 1 121950 200000
1 0 105759 200000
1 0 105758 105758
1 1 0 121948
1 2 198406 200000
1 2 198405 198405
2 125839 162319
1 1 13126 200002
1 1 2 13120
1 6 90439 200002
1 0 2 198406
1 7 2 153447
1 7 153445 200002
1 6 2 90433
1 4 2 197922
1 4 197923 197923
1 5 28955 200002
1 4 197920 ...

output:

2
37
67
78
144
145
196
287
290
352
369
379
383
518
560
636
657
705
827
851
915
942
1079
1129
1192
1211
1297
1310
1333
1369
1444
1508
1524
1556
1731
1794
1886
1911
1945
1949
2101
2103
2159
2178
2263
2326
2358
2403
2547
2556
2727
2740
2765
2824
2870
2900
2961
3071
3122
3226
3242
3252
3277
3281
3356
35...

result:

ok 742 numbers

Test #21:

score: 0
Accepted
time: 357ms
memory: 139352kb

input:

100000
2 10790 165554
2 125862 150956
2 24358 80386
2 100780 144216
2 27756 105452
2 55048 145240
2 101240 104901
2 10862 128102
2 31381 46801
1 1 147838 147838
2 130799 135834
2 3736 149492
2 106781 172974
2 25003 140128
2 41572 187567
2 36255 115688
2 3849 70338
2 177509 197443
2 50269 54442
2 824...

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 95190 numbers

Test #22:

score: 0
Accepted
time: 544ms
memory: 144900kb

input:

100000
1 0 56254 56254
1 3 96654 96654
1 1 53741 53741
1 4 139305 139305
1 8 163975 163975
1 2 128430 128430
1 12 105627 105627
1 10 135575 135575
1 9 4051 4051
1 15 31073 31073
1 16 150725 150725
1 21 194203 194203
1 23 190884 190884
1 17 165733 165733
1 27 18269 18269
1 25 75758 75758
1 14 107539 ...

output:

1
0
0
1
0
1
0
0
0
1
0
0
1
1
2
2
2
2
2
3
2
2
2
22
22
2
2
2
2
22
22
22
2
2
22
22
22
2
22
2
2
22
2
2
22
2
22
0
27
27
189
27
27
22
217
27
27
217
22
217
27
217
217
206
22
217
22
217
206
206
217
206
206
206
217
206
217
206
217
206
706
706
706
217
706
955
955
747
747
1658
1658
747
1658
884
884
1658
1740
17...

result:

ok 795 numbers

Test #23:

score: 0
Accepted
time: 520ms
memory: 143308kb

input:

100000
2 128633 171051
2 5428 9110
2 39785 124510
1 0 168745 168745
2 17948 106062
1 1 169518 169518
2 5250 34329
2 26220 48991
2 126394 165266
2 140911 156192
1 8 122918 122918
2 147159 178481
2 143547 165192
2 117389 133436
2 42106 114353
2 1741 110948
2 104464 174174
1 15 193704 193704
2 157961 1...

output:

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

result:

ok 28844 numbers

Test #24:

score: 0
Accepted
time: 274ms
memory: 139060kb

input:

10
2 2 200000
1 1 4 199992
2 4 199992
2 0 199999
1 2 4 199992
1 4 3 199998
1 0 3 199992
1 5 5 199992
2 1 199993
2 3 200003

output:

0
0
0
3
3

result:

ok 5 number(s): "0 0 0 3 3"

Test #25:

score: 0
Accepted
time: 1299ms
memory: 185124kb

input:

100000
1 1 994 199577
1 3 163 199780
1 2 177 199104
1 5 828 199925
1 6 957 199309
1 9 545 199665
1 4 107 199656
1 8 737 199651
1 12 906 199930
1 13 183 199001
1 14 69 199899
1 10 137 199967
1 16 988 199056
1 7 14 199844
1 18 458 199952
1 0 746 199355
1 20 113 199359
1 21 40 199479
1 11 793 199784
1 ...

output:

162
280
406
448
499
618
724
800
824
841
868
928
1019
1306
1453
1466
1548
1562
1562
1715
1730
2133
2161
2206
2244
2260
2260
2584
2718
2719
2773
2835
2982
3460
3469
3487
3518
3624
3688
3700
3706
3726
3733
3768
3821
3936
3989
3989
4034
4080
4094
4231
4282
4588
4675
4745
4891
4900
5029
5117
5120
5170
52...

result:

ok 1502 numbers

Test #26:

score: 0
Accepted
time: 271ms
memory: 140628kb

input:

100000
1 0 0 200000
1 1 0 200000
1 2 0 200000
1 3 0 200000
1 4 0 200000
1 5 0 200000
1 6 0 200000
1 7 0 200000
1 8 0 200000
1 9 0 200000
1 10 0 200000
1 11 0 200000
1 12 0 200000
1 13 0 200000
1 14 0 200000
1 15 0 200000
1 16 0 200000
1 17 0 200000
1 18 0 200000
1 19 0 200000
1 20 0 200000
1 21 0 20...

output:

73237
99998

result:

ok 2 number(s): "73237 99998"

Test #27:

score: 0
Accepted
time: 297ms
memory: 139156kb

input:

100000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200000
2 0 200...

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 99998 numbers

Test #28:

score: 0
Accepted
time: 303ms
memory: 139880kb

input:

100000
1 0 0 200000
2 0 200000
1 0 1 200001
2 1 200001
1 1 3 200003
1 0 3 200003
1 7 3 200003
2 3 200003
1 13 8 200008
1 14 8 200008
1 15 8 200008
1 0 8 200008
2 8 200008
2 17 200017
2 26 200026
1 42 35 200035
1 41 35 200035
2 35 200035
2 46 200046
2 57 200057
1 79 68 199940
2 68 199940
1 92 80 1999...

output:

1
2
5
9
9
9
11
11
11
12
13
13
17
17
18
18
19
19
20
22
22
22
23
23
24
24
24
25
26
27
28
28
28
28
28
30
31
31
34
34
35
35
36
38
40
40
42
42
44
44
44
44
46
46
52
52
53
55
55
57
61
61
62
62
62
63
64
67
68
68
68
72
72
72
72
72
72
73
74
74
78
79
79
81
81
82
83
85
86
86
87
90
91
91
94
94
96
96
97
101
101
1...

result:

ok 49969 numbers

Test #29:

score: 0
Accepted
time: 321ms
memory: 139828kb

input:

100000
1 2 0 200000
1 6 0 200000
2 0 200000
2 0 200000
1 10 0 200000
2 0 200000
1 12 0 200000
2 0 200000
2 0 200000
1 5 0 200000
1 0 0 200000
2 0 200000
1 0 1 200001
1 6 1 200001
1 9 1 200001
2 1 200001
2 4 200004
1 14 7 200007
1 22 7 200007
2 7 200007
2 10 200010
1 14 13 200013
1 29 13 200013
1 6 1...

output:

0
0
0
0
0
1
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
32
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
53
5...

result:

ok 50033 numbers

Test #30:

score: 0
Accepted
time: 370ms
memory: 142124kb

input:

100000
1 0 1 199999
2 0 199999
2 0 199998
2 3 200002
1 2 2 200003
2 3 199996
1 7 5 199994
2 5 199994
2 9 200008
1 15 10 199988
1 8 10 199988
2 10 200011
1 22 17 199983
1 23 17 200016
1 21 16 200016
1 24 17 199983
1 25 16 200016
2 17 200016
2 27 199973
1 47 37 199963
2 36 200036
1 36 46 200046
2 47 1...

output:

1
1
1
2
3
3
5
10
10
10
12
14
14
15
15
15
18
19
19
19
19
19
19
19
19
25
25
25
25
27
30
31
31
31
31
31
31
31
31
31
31
31
31
31
31
31
31
32
32
32
40
44
45
45
50
52
52
54
58
58
58
58
58
61
64
64
64
64
64
66
66
66
66
69
69
69
69
69
69
75
75
75
75
79
81
83
83
85
85
85
85
85
90
90
90
90
95
99
99
99
101
104...

result:

ok 49921 numbers

Test #31:

score: 0
Accepted
time: 772ms
memory: 164940kb

input:

100000
1 10 996 198332
2 251 198607
1 17 1563 198696
1 13 1207 199472
1 5 1593 198940
2 1013 199011
1 11 885 198453
2 522 199273
1 16 92 198770
2 21 199297
1 12 644 198849
1 26 1443 198675
1 2 818 199429
1 29 1286 199094
1 28 1550 198762
1 32 1542 198816
1 19 405 198043
2 997 198965
2 290 199676
1 2...

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
15
15
15
15
15
15
15
15
15
15
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
68
...

result:

ok 49976 numbers

Test #32:

score: 0
Accepted
time: 394ms
memory: 144080kb

input:

100000
2 230 198781
2 531 198260
2 206 197999
2 396 198376
1 1 335 199546
1 19 538 199563
2 907 199892
2 111 199389
2 671 198971
2 1147 199708
1 15 1093 198139
2 616 199380
2 1135 198364
2 1182 199276
2 1189 199093
2 1096 199346
1 5 1267 199449
2 1621 199286
2 1474 198545
2 543 198513
2 1717 199524
...

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 90243 numbers

Test #33:

score: 0
Accepted
time: 1337ms
memory: 188116kb

input:

100000
1 1 1917 199937
1 2 20 199355
2 303 197993
1 10 1189 199426
1 12 104 198355
1 3 363 199445
1 11 622 198582
1 5 380 198668
1 6 314 199505
1 0 326 199298
1 9 774 199560
1 4 1638 198877
1 7 1646 199014
1 16 1359 198973
1 21 1435 198321
1 14 1899 198118
1 8 655 198320
1 20 30 198583
1 13 988 1998...

output:

0
15
37
37
83
116
116
116
135
209
218
288
335
357
357
396
446
455
455
455
455
536
577
577
628
628
628
640
640
662
724
725
733
763
763
801
816
816
856
856
891
892
903
903
903
903
948
948
989
995
995
995
1048
1048
1091
1145
1164
1164
1164
1195
1195
1223
1268
1297
1330
1358
1358
1360
1385
1424
1448
144...

result:

ok 4978 numbers

Test #34:

score: 0
Accepted
time: 1158ms
memory: 182244kb

input:

100000
1 1 223 199681
1 2 248 199602
1 3 263 199622
1 0 178 199575
1 6 403 199922
1 4 383 199758
1 7 364 199664
1 8 13 199729
1 9 494 199980
1 10 157 199527
1 12 402 199404
1 13 352 199504
1 14 550 199718
1 15 84 199597
1 5 191 199587
1 17 412 199947
1 18 549 199783
1 19 174 199533
1 16 390 199343
1...

output:

100
138
214
370
461
495
590
704
704
749
812
856
869
889
1221
1241
1351
1824
1898
1956
2030
2198
2235
2365
2387
2538
3066
3169
3198
3207
3284
3315
3374
3468
3597
3609
3642
3686
3784
3931
4023
4592
4678
4685
4767
4778
4960
4970
4970
4975
4987
4988
5017
5255
5305
5343
5554
5651
5717
5876
5943
5983
6052...

result:

ok 1032 numbers

Test #35:

score: 0
Accepted
time: 267ms
memory: 139172kb

input:

50
1 1 93 199391
1 0 63092 171029
1 2 416 199999
1 3 873 199278
1 0 27448 176003
1 0 2547 187318
2 46265 59498
1 1 568 199802
2 2700 19528
2 78521 132993
1 8 12014 160454
1 8 38423 176919
1 10 384 199881
1 8 75196 100246
2 80061 171434
2 36682 198657
1 19 17676 115552
1 19 127263 138096
1 19 13391 1...

output:

4
4
4
7
7
12
12
12
12
18
26

result:

ok 11 numbers

Test #36:

score: 0
Accepted
time: 276ms
memory: 139452kb

input:

1000
2 102040 157914
1 96 76 199197
2 20611 187937
1 372 126 199751
1 514 160 199183
1 435 600 199497
1 7 37686 141442
1 14 554 199547
2 38521 177075
2 6084 114794
1 159 89990 174231
1 529 29938 176883
1 656 23217 183722
1 186 21917 165266
1 175 29258 122368
1 95 27527 158085
1 75 17165 187190
1 297...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
4
4
4
4
4
4
4
4
4
4
5
8
8
12
12
12
12
12
12
12
12
12
12
12
12
12
12
16
37
62
62
63
63
63
165
165
209
209
209
209
209
209
209
209
209
209
214
225
225
322
19
330
330
19
351
380
392
392
392
392
414
437
440
443
449
468
79
491
546
557
566
566
566
19
566
19
56...

result:

ok 101 numbers

Test #37:

score: 0
Accepted
time: 1519ms
memory: 182256kb

input:

100000
1 148 88497 170777
1 137 35589 195179
1 69 710 199964
1 452 16724 136628
1 279 638 199845
1 558 11549 179330
1 137 24424 187416
1 271 133 199514
1 105 60606 154795
1 151 56271 193239
1 248 168 199979
1 526 1035 180397
1 10 132378 184945
1 384 60488 178993
1 534 26291 190852
1 225 231 199743
1...

output:

2
424
424
424
424
38
424
424
424
424
424
424
424
148
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
10
424
424
424
38
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
424
38
424
424
424
424
424
424
42...

result:

ok 101 numbers

Test #38:

score: 0
Accepted
time: 1485ms
memory: 180168kb

input:

100000
1 12 4387 191126
1 541 11038 170793
1 112 57873 161627
1 569 538 199153
1 463 27 199604
1 94 146 199094
1 1 76533 182918
1 337 710 199046
1 53 58699 145237
1 397 636 185786
1 315 21951 180550
2 21636 148358
1 735 55672 151190
1 589 21185 167101
1 97 41 199445
1 267 30527 190393
1 362 52 19978...

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
93
93
93
93
93
93
93
93
93
93
4
93
93
93
93
93
93
44
246
246
246
246
246
246
246
246
246
246
246
93
246
246
246
246
246
246
246
246
246
246
246
246
246
246
246
246
1
246
246
246
93
246
93
246
246
246
24...

result:

ok 5001 numbers

Test #39:

score: 0
Accepted
time: 1327ms
memory: 174848kb

input:

100000
1 208 102376 180700
1 681 532 199866
1 308 78 199134
1 48 26552 140316
1 162 55400 181687
1 135 259 199142
1 365 111 199757
1 393 786 199745
1 110 3601 108985
1 134 398 199156
1 167 403 199846
1 826 432 199015
1 218 402 199696
1 784 63723 141771
1 366 91 199595
1 490 511 199696
1 627 824 1995...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
348
377
390
407
467
477
493
642
649
658
666
668
699
778
842
875
885
897
923
929
938
971
977
1021
1024
1052
1059
1059
1069
1076
1095
1103
1107
1132
1142
1151
1175
1211
1263
1281
1303
1329
1346
1365
1388
1401
1461
1465
1477
1139
1498
1510
1510
1511
1512
1512
154...

result:

ok 2501 numbers

Test #40:

score: 0
Accepted
time: 1247ms
memory: 171692kb

input:

100000
1 4 756 199362
1 78 4031 59935
1 105 700 199677
1 147 749 199809
1 385 21557 147386
1 138 78891 154177
1 232 13571 48256
1 229 730 199090
1 200 144881 161961
1 721 970 199149
1 13 18796 187586
1 102 4207 173046
1 301 30424 176921
1 148 123 199612
1 478 885 199681
1 286 621 199145
1 11 957 199...

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
604
604
638
651
665
688
722
751
751
805
821
831
883
883
936
984
1023
1033
1060
1062
1068
1068
1068
1083
1141
1142
1147
1147
1178
1224
1224
1224
1229
1263
1387
1391
1392
1470
1478
1498
1504
1505
1517
1549
1553
1591
1614
1674
1695
1718
1723
1798
1807
1...

result:

ok 2501 numbers

Test #41:

score: 0
Accepted
time: 1095ms
memory: 166636kb

input:

100000
1 254 778 199170
1 332 33517 199620
1 297 872 199368
1 376 19 199370
1 29 309 199385
2 14956 143091
1 117 10772 193088
1 27 182 199627
1 159 20889 193941
1 479 635 199925
1 709 993 199124
1 416 563 199997
1 9 7999 174410
1 282 27714 152618
1 3 536 199869
1 21 73662 74019
1 305 190 199309
1 29...

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

result:

ok 25001 numbers

Test #42:

score: 0
Accepted
time: 1339ms
memory: 175664kb

input:

100000
1 156 151 199917
1 154 44 199467
1 105 276 199592
1 275 750 199356
1 188 23010 176724
1 138 32 199317
1 347 16536 134748
1 527 110 199390
1 390 536 199788
1 736 3994 193452
1 0 384 199934
1 188 55256 83013
1 423 896 199272
1 548 508 199263
1 94 88574 175176
1 178 4738 178228
1 284 26109 19789...

output:

2
340
381
383
383
534
617
653
700
848
1066
1360
1701
1824
2132
2314
2054
2383
2492
2527
2532
2562
2562
916
2562
2562
2562
2562
2562
2562
2562
2562
2562
405
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562
2562...

result:

ok 501 numbers

Test #43:

score: 0
Accepted
time: 276ms
memory: 139012kb

input:

50
1 0 24095 24095
1 0 199997 200000
2 3 199997
2 2 199996
1 2 199995 199998
1 2 3 1
1 2 61668 61674
2 7 200002
1 2 0 0
1 3 134057 134057
1 3 0 7
1 2 199992 199998
1 2 199997 200003
2 7 199996
2 5 199995
1 7 36097 36110
1 5 199997 199996
1 7 3888 3902
1 7 6 6
1 7 117889 117902
1 7 199995 199993
1 7 ...

output:

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

result:

ok 13 numbers

Test #44:

score: 0
Accepted
time: 253ms
memory: 139916kb

input:

5000
1 0 5 8
1 0 83040 83045
1 0 6 10
1 0 0 7
1 0 199996 199998
1 0 28815 28822
1 0 199993 199999
1 0 2 6
1 0 157000 157007
1 0 199997 200000
1 0 5241 5247
1 0 125612 125615
1 0 6 12
1 0 199986 199996
1 0 0 5
1 0 199996 199999
1 0 0 6
1 1 199997 200000
1 0 199990 199997
1 1 0 1
1 0 199993 199995
1 0...

output:

3
6
6
10
10
10
14
15
15
17
20
23
23
30
30
35
35
36
41
44
50
51
52
53
54
50
59
63
63
64
64
66
67
69
71
71
75
77
81
84
84
88
89
89
91
91
91
92
93
95
95
97
91
104
105
105
106
108
108
108
110
113
114
117
117
119
121
122
123
117
132
134
134
134
136
123
138
138
142
137
143
148
144
149
149
149
152
155
157
...

result:

ok 98 numbers

Test #45:

score: 0
Accepted
time: 392ms
memory: 147416kb

input:

100000
1 0 199932 199933
1 0 163280 163282
1 0 7 9
1 0 199976 199978
1 0 68736 68736
1 0 141367 141369
2 50 199988
1 1 199986 199988
1 1 191959 191958
1 1 21681 21680
1 1 41 43
1 1 199949 199948
1 1 66 66
1 1 174375 174374
1 1 199948 199950
1 1 21 20
1 1 199938 199941
1 1 59494 59494
1 1 9 11
1 1 19...

output:

1
1
1
2
2
2
2
2
4
2
4
4
4
4
4
4
4
4
4
5
5
4
4
5
5
5
5
5
5
5
5
6
6
5
4
6
6
5
6
6
7
7
6
7
6
7
6
9
9
9
9
7
7
10
10
10
10
8
10
10
10
10
10
10
11
10
10
11
11
9
9
12
11
12
12
9
10
13
12
13
9
12
12
13
12
10
13
13
13
13
13
13
13
13
13
13
13
13
13
13
15
13
15
13
13
13
13
13
13
16
13
13
13
13
13
13
16
13
13
1...

result:

ok 4927 numbers

Test #46:

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

input:

100000
1 0 199959 199961
1 0 36620 36622
1 0 0 4
1 0 199970 199974
1 0 166362 166366
2 5 199980
1 1 151201 151203
1 1 23 22
1 1 199999 200001
1 1 27142 27145
1 1 32988 32988
1 1 199954 199959
1 1 29 30
1 1 30232 30234
1 1 199985 199986
1 1 1 3
1 0 1 1
1 1 199952 199954
1 1 199993 199992
1 1 2 4
1 1 ...

output:

1
2
9
8
15
17
18
20
24
25
20
27
30
30
30
33
33
34
34
40
47
52
59
53
53
61
55
61
60
60
62
65
64
66
67
67
68
70
76
77
83
83
84
85
83
85
85
89
95
98
98
100
101
103
104
104
107
113
113
116
118
123
127
127
127
130
130
135
136
136
138
139
139
139
139
141
141
143
146
148
151
151
154
155
155
165
165
165
176...

result:

ok 474 numbers

Test #47:

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

input:

100000
1 0 11 17
1 0 31 34
1 0 93 96
1 0 86 86
1 0 199903 199908
1 0 84 90
1 0 20 24
1 0 171823 171825
1 0 98037 98040
1 0 19015 19019
1 0 108923 108924
1 0 199969 199971
1 0 199897 199901
1 0 175745 175749
1 0 0 2
1 0 199986 199990
1 0 58 62
1 0 56 59
1 0 199986 199991
1 0 36869 36870
1 0 13 17
1 0...

output:

2
2
3
4
4
4
5
5
5
6
6
6
6
6
6
7
6
7
7
7
7
7
7
7
7
9
9
11
11
11
11
10
12
12
12
12
12
12
12
12
12
12
12
12
12
14
12
13
12
14
16
14
13
14
14
15
16
15
16
16
14
17
15
16
17
17
16
16
17
18
18
18
17
18
18
18
19
19
19
19
19
19
19
19
19
19
20
19
19
19
19
20
20
20
20
20
21
21
22
22
19
22
23
21
20
22
22
23
23
...

result:

ok 2454 numbers

Test #48:

score: 0
Accepted
time: 418ms
memory: 143160kb

input:

100000
1 0 199972 199982
1 0 199897 199916
1 0 199913 199923
1 0 199983 199987
1 0 87 95
1 0 199995 200000
1 0 25 34
1 0 199942 199951
1 0 130686 130695
1 1 25 30
1 0 159048 159063
1 0 199934 199940
1 0 179066 179079
1 0 31 46
1 0 199904 199918
1 0 199919 199933
1 0 178854 178870
1 0 199939 199947
1...

output:

2
3
2
3
3
3
3
3
3
3
4
4
4
4
4
4
4
5
6
5
6
6
6
6
6
7
8
9
9
9
9
10
10
10
10
10
10
10
10
10
10
11
11
11
11
11
11
11
11
12
12
12
12
12
12
12
13
13
14
14
15
15
16
16
16
16
16
16
16
16
16
16
16
16
16
16
17
17
17
17
17
17
17
17
17
18
18
18
18
18
18
18
17
21
18
18
21
18
17
18
18
17
17
20
18
18
18
17
18
21
1...

result:

ok 2534 numbers

Test #49:

score: 0
Accepted
time: 585ms
memory: 149828kb

input:

100000
2 23934 191701
1 182 211 199776
1 109 3202 183540
2 30165 169863
1 301 705 199494
2 38571 121776
2 11121 177582
1 175 886 199042
2 95334 162837
1 364 999 199968
2 36618 187255
2 55253 181077
2 1955 107664
2 81017 85649
1 488 152 199388
2 3506 65664
1 317 41951 177462
1 134 935 199051
2 140775...

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 75000 numbers

Test #50:

score: 0
Accepted
time: 341ms
memory: 141764kb

input:

100000
2 92 199962
2 12 199919
2 57 199960
2 70 199920
2 64 199953
2 7 199963
2 25 199997
2 87 199968
2 92 199992
2 40 199981
2 100 199990
2 85 199915
1 0 64 65
2 27 199900
1 1 199975 199975
1 1 88 91
2 7 199941
2 57 199941
1 3 29 29
2 55 199951
1 4 137545 137546
2 81 199941
1 5 42 53
2 62 199905
2 ...

output:

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

result:

ok 76029 numbers