QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393797#4998. Keyboard QueriesEcec243AC ✓103ms13144kbC++232.7kb2024-04-19 12:37:182024-04-19 12:37:19

Judging History

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

  • [2024-04-19 12:37:19]
  • 评测
  • 测评结果:AC
  • 用时:103ms
  • 内存:13144kb
  • [2024-04-19 12:37:18]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=1e9+9;
const int P=19260817;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=1e5+5;
int n,q;

struct BIT_mod{
	int w[N];
	void clear(){memset(w,0,sizeof(w));}
	int lowbit(int x){return x&(-x);}
	void Add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))add(w[i],v);}
	int qsum(int x){int res=0;for(int i=x;i;i-=lowbit(i))add(res,w[i]);return res;}
	int sum(int l,int r){return cmod(qsum(r)-qsum(l-1)+mod);}
};

int val[N];
namespace Hash{
	BIT_mod A,B;
	int Pw[N],Iv[N];
	void init(int V){
		A.clear(),B.clear();int IP=inv(P);
		Pw[0]=1;for(int i=1;i<=V;i++)Pw[i]=1ll*Pw[i-1]*P%mod;
		Iv[0]=1;for(int i=1;i<=V;i++)Iv[i]=1ll*Iv[i-1]*IP%mod;
	}
	// A[i] = p^{i-1} * w[i]
	// B[i] = p^{n-i} * w[i]
	void modify(int p,int c){
		int D=cmod(c-val[p]+mod);val[p]=c;
		A.Add(p,1ll*D*Pw[p-1]%mod),B.Add(p,1ll*D*Pw[n-p]%mod);
	}
	int q1(int l,int r){return 1ll*A.sum(l,r)*Iv[l-1]%mod;}
	int q2(int l,int r){return 1ll*B.sum(l,r)*Iv[n-r]%mod;}
}

using Hash::q1;
using Hash::q2;
using Hash::modify;

vector<int>nodes[N];
void add_palin(int l,int r){
	while(q1(l,r)!=q2(l,r)){
		int L=l,R=(l+r)>>1,res=R;
		assert(q1(l,R)!=q2(l+r-R,r));
		while(L<=R){
			int mid=(L+R)>>1;
			if(q1(l,mid)!=q2(l+r-mid,r))res=mid,R=mid-1;
			else L=mid+1;
		}
		int p=res,q=l+r-res;
		int x=val[p],y=val[q];
		if(nodes[x].size()>nodes[y].size())swap(x,y);
		for(int j:nodes[x])modify(j,y),nodes[y].emplace_back(j);
		nodes[x].clear();
	}
}

int query(int l,int r,int s,int t){
	if(t-s!=r-l)return -1;
	return q1(l,r)==q1(s,t);
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	n=read(),q=read();
	Hash::init(n);
	for(int i=1;i<=n;i++)modify(i,i),nodes[i].emplace_back(i);
	for(int i=1;i<=q;i++){
		int op=read(),l=read(),r=read();
		if(op==1)add_palin(l,r);
		else{
			int s=read(),t=read();
			int res=query(l,r,s,t);
			if(res==-1)puts("Not equal");
			else if(res==0)puts("Unknown");
			else puts("Equal");
		}
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 4580kb

input:

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

output:

Equal
Unknown
Not equal
Equal
Equal
Unknown

result:

ok 6 lines

Test #2:

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

input:

100 200
2 2 5 2 5
2 2 4 2 4
1 1 3
1 2 4
1 5 5
2 1 4 1 4
2 2 5 2 5
2 2 3 4 5
1 4 5
2 3 3 2 2
1 6 6
1 6 6
1 7 8
1 7 8
2 8 8 8 8
1 7 8
2 9 9 9 9
2 9 9 9 9
2 19 24 19 24
1 10 18
2 10 12 22 24
2 18 18 23 23
1 13 20
1 10 15
1 18 20
1 15 23
1 10 24
1 10 17
2 11 15 11 15
1 16 16
1 19 21
1 19 22
1 13 16
1 10...

output:

Equal
Equal
Equal
Equal
Unknown
Unknown
Equal
Equal
Equal
Equal
Unknown
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Equal
Equal
Unknown
Unknown
Equal
Unknow...

result:

ok 88 lines

Test #3:

score: 0
Accepted
time: 70ms
memory: 11764kb

input:

100000 200000
1 67745 67758
2 63101 63113 63101 63113
1 9467 9472
1 66260 66285
2 75601 75604 75601 75604
1 68407 68413
2 39349 39352 39354 39357
2 45999 46011 46003 46015
2 58347 58359 58347 58359
2 82752 82776 82746 82770
2 60409 60411 60416 60418
1 95275 95278
1 7738 7753
2 46294 46336 46295 4633...

output:

Equal
Equal
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Un...

result:

ok 99927 lines

Test #4:

score: 0
Accepted
time: 98ms
memory: 12356kb

input:

100000 200000
1 670 4584
1 76745 77306
1 15676 31521
1 7564 12795
2 57503 60058 62355 64910
1 24871 70536
2 29000 51372 45221 67593
2 56412 67208 49196 59992
2 31499 51386 4074 23961
1 85917 99901
2 32481 46886 48776 63181
1 35827 64377
1 89882 90683
1 80642 88541
1 74098 97351
1 79430 96270
2 80489...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Eq...

result:

ok 100042 lines

Test #5:

score: 0
Accepted
time: 101ms
memory: 11320kb

input:

100000 200000
1 33910 33911
2 61869 73448 74466 86045
1 33909 33911
2 579 98866 1247 99534
2 5240 99979 2947 97686
2 9873 88116 5264 83507
1 33909 33912
2 13298 88259 10845 85806
1 33909 33913
2 33659 87441 30798 84580
1 33908 33913
1 33908 33914
2 21881 91229 24055 93403
2 65807 96530 55461 86184
1...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 87ms
memory: 11332kb

input:

100000 200000
1 16332 16333
1 16331 16333
1 16331 16334
1 16330 16334
1 16330 16335
1 16330 16336
1 16330 16337
1 16330 16338
1 16329 16338
1 16328 16338
1 16327 16338
1 16326 16338
1 16325 16338
1 16324 16338
1 16323 16338
1 16323 16339
1 16322 16339
1 16321 16339
1 16320 16339
1 16320 16340
1 1632...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 10000 lines

Test #7:

score: 0
Accepted
time: 22ms
memory: 11292kb

input:

100000 200000
2 10807 94442 5971 89606
2 12786 33713 28677 49604
2 4588 96653 5728 97793
2 878 45434 16222 60778
2 34047 95890 29289 91132
2 10569 69071 17100 75602
2 31418 49828 65167 83577
2 45116 92222 15767 62873
2 308 99562 56 99310
2 1984 34922 23175 56113
2 4480 38665 3965 38150
2 29797 94878...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 198000 lines

Test #8:

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

input:

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

output:

Unknown
Unknown
Equal
Equal
Unknown
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Equal
Unknown
Unknown
Unknown
Equal
Equal
Equal
Unknown
Unknown
Equal
Equal
Equal
Equal
Unknown
Equal
Un...

result:

ok 3023 lines

Test #9:

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

input:

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

output:

Unknown
Unknown
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Eq...

result:

ok 100343 lines

Test #10:

score: 0
Accepted
time: 46ms
memory: 11304kb

input:

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

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Equal
...

result:

ok 105463 lines

Test #11:

score: 0
Accepted
time: 39ms
memory: 11316kb

input:

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

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unknown
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknow...

result:

ok 110924 lines

Test #12:

score: 0
Accepted
time: 28ms
memory: 4932kb

input:

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

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknow...

result:

ok 195684 lines

Test #13:

score: 0
Accepted
time: 26ms
memory: 5028kb

input:

7000 200000
2 2256 5207 3010 5961
1 2382 4030
2 4191 5725 5258 6792
2 3395 4198 2404 3207
1 1260 3712
2 1819 4823 2679 5683
2 697 3086 3507 5896
1 40 3074
2 4279 6523 2803 5047
2 2826 5571 1403 4148
1 2613 3963
1 1652 5668
1 2735 3989
1 2274 3496
2 1386 4036 834 3484
2 4752 6441 1276 2965
1 3815 635...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Equal
Unknown
Equal
Unknown
...

result:

ok 100000 lines

Test #14:

score: 0
Accepted
time: 103ms
memory: 12088kb

input:

100000 200000
1 87818 92226
2 32424 92295 16913 76784
1 70714 99416
2 9544 72420 11162 74038
2 10271 96899 3264 89892
2 49061 97381 33226 81546
1 30140 56684
1 78310 90854
1 15986 68196
1 56156 74776
1 83625 90065
2 33086 90701 34976 92591
1 73280 97000
1 7456 15236
1 22070 46046
1 60552 65590
1 142...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Equal
Unknown
Unknown
Unknown
Unknown
Eq...

result:

ok 100000 lines

Test #15:

score: 0
Accepted
time: 95ms
memory: 12784kb

input:

100000 200000
2 59778 75146 47503 62871
2 3987 90980 8236 95229
2 48676 65230 70072 86626
2 30166 76979 30839 77652
2 6413 97498 7166 98251
2 57337 89682 60118 92463
2 32397 37785 54625 60013
2 1005 65576 18678 83249
2 5507 98330 6974 99797
2 53301 87746 15827 50272
2 62106 85792 70308 93994
2 22910...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 199000 lines

Test #16:

score: 0
Accepted
time: 81ms
memory: 12104kb

input:

100000 200000
1 39298 59368
1 51203 71337
1 38832 75470
1 3878 91242
1 14749 19285
1 16841 24981
1 85933 92891
1 25053 33885
1 5004 47698
1 63580 76142
1 16489 29279
1 74016 88200
1 2499 78945
1 66768 74810
1 7485 76605
1 29642 41170
1 10035 35293
1 45646 96782
1 40779 62889
1 15210 88814
1 37439 57...

output:

Equal
Unknown
Unknown
Equal
Unknown
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Equal
Equal
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Equal
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Unknow...

result:

ok 1000 lines

Test #17:

score: 0
Accepted
time: 30ms
memory: 6136kb

input:

17000 200000
2 10400 14558 12161 16319
2 4500 12734 368 8602
2 162 4712 6750 11300
2 941 7803 9818 16680
2 5055 15676 2198 12819
2 14816 16436 1801 3421
2 1138 12438 4492 15792
2 8739 15040 5967 12268
2 7099 8433 5601 6935
2 695 15210 145 14660
2 157 9572 168 9583
2 8587 13293 9783 14489
2 1957 1641...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 198301 lines

Test #18:

score: 0
Accepted
time: 79ms
memory: 13144kb

input:

100000 200000
2 9421 82113 7544 80236
2 40942 92381 17276 68715
2 13590 13590 56286 56286
2 2796 6650 8190 12044
2 34425 62026 67407 95008
2 27520 81535 3211 57226
2 722 94373 4435 98086
2 15702 67095 7238 58631
2 26382 31078 79839 84535
1 65661 65674
2 6524 78116 21339 92931
2 22878 59297 35127 715...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 185716 lines

Test #19:

score: 0
Accepted
time: 83ms
memory: 12752kb

input:

100000 200000
2 4887 96564 6654 98331
2 11281 96040 10851 95610
2 31688 93961 18099 80372
2 30792 60434 9211 38853
2 15713 25565 17216 27068
2 20689 46955 28794 55060
2 47260 77506 7525 37771
2 85575 97543 28966 40934
2 78868 84939 77031 83102
2 13653 85347 15861 87555
2 4168 82930 2222 80984
2 7057...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 198971 lines

Test #20:

score: 0
Accepted
time: 90ms
memory: 11944kb

input:

100000 200000
2 65363 65363 29656 29656
2 39191 84324 10826 55959
2 3882 95685 4020 95823
2 32896 34478 85984 87566
2 301 99528 18 99245
2 4333 90062 7180 92909
2 8184 98879 331 91026
2 30303 93601 3829 67127
2 16411 16411 75219 75219
2 35352 80472 43328 88448
2 1789 99607 1694 99512
2 15243 84302 2...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 199920 lines

Test #21:

score: 0
Accepted
time: 87ms
memory: 11552kb

input:

100000 200000
2 30323 51688 63053 84418
2 45 99991 50 99996
2 382 99972 1 99591
2 3335 75109 20505 92279
2 13530 93314 2396 82180
2 23527 57502 9160 43135
2 85214 96444 61221 72451
2 5659 91246 2978 88565
2 1656 64828 6771 69943
2 1076 99239 987 99150
2 11928 97663 13888 99623
2 58356 85051 13805 40...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 199991 lines

Test #22:

score: 0
Accepted
time: 93ms
memory: 12828kb

input:

100000 200000
1 276 99906
1 217 99887
2 1 99999 2 100000
1 153 99923
2 1 99999 2 100000
1 146 99947
1 210 99763
2 1 100000 1 100000
2 1 99999 2 100000
1 287 99892
2 1 100000 1 100000
2 1 100000 1 100000
1 160 99973
1 51 99748
2 1 100000 1 100000
2 1 99999 2 100000
2 1 99999 2 100000
2 1 99999 2 1000...

output:

Unknown
Unknown
Equal
Unknown
Equal
Equal
Equal
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Unknown
Eq...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 79ms
memory: 12396kb

input:

100000 200000
2 1 99999 2 100000
2 1 100000 1 100000
2 1 100000 1 100000
2 1 100000 1 100000
2 1 100000 1 100000
2 1 100000 1 100000
2 1 99999 2 100000
2 1 100000 1 100000
2 1 100000 1 100000
2 1 99999 2 100000
2 1 99999 2 100000
2 1 99999 2 100000
2 1 100000 1 100000
2 1 100000 1 100000
2 1 100000 ...

output:

Unknown
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Unknown
Unknown
Unknown
Equal
Equal
Equal
Equal
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Equal
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Equal
Un...

result:

ok 199000 lines

Test #24:

score: 0
Accepted
time: 90ms
memory: 12284kb

input:

100000 199000
1 62 99635
1 128 99515
1 485 99857
1 153 99887
1 117 99620
1 266 99845
1 422 99941
1 76 99628
1 230 99954
1 439 99953
1 571 99945
1 294 99831
1 49 99470
1 118 99665
1 457 99883
1 220 99851
1 36 99477
1 169 99801
1 109 99668
1 362 99969
1 76 99889
1 172 99949
1 200 99744
1 253 99624
1 2...

output:

Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
...

result:

ok 1000 lines

Test #25:

score: 0
Accepted
time: 50ms
memory: 11852kb

input:

100000 200000
1 2 3
1 1 3
1 3 3
1 2 2
1 3 4
2 2 4 2 4
1 1 2
1 2 4
1 5 9
2 8 11 7 10
1 10 11
2 11 11 7 7
1 7 11
1 11 12
2 6 10 8 12
2 6 12 5 11
2 8 12 6 10
2 8 11 7 10
2 5 9 5 9
1 8 10
1 5 11
2 7 12 5 10
2 5 7 7 9
1 10 12
2 22 41 34 53
1 23 32
2 14 59 17 62
1 30 54
1 29 49
1 16 35
1 17 33
1 21 50
1 2...

output:

Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Equal
Unknown
Unknown
Equal
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Equal
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Equal
Unknown
Equal
Equal
Unknown
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Unknow...

result:

ok 100058 lines

Test #26:

score: 0
Accepted
time: 57ms
memory: 12064kb

input:

100000 200000
1 16 25
1 8 16
1 12 12
1 15 28
2 9 22 15 28
1 5 21
1 3 27
2 2 19 2 19
2 4 26 7 29
2 16 21 10 15
2 1 28 1 28
1 10 14
2 6 26 5 25
1 13 20
1 11 23
2 19 25 19 25
1 15 16
2 1 25 1 25
2 3 24 4 25
1 4 25
2 14 19 15 20
1 14 28
1 4 11
1 14 16
2 9 18 2 11
2 7 9 22 24
2 6 21 13 28
1 5 12
1 10 14
...

output:

Unknown
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Unknown
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unkn...

result:

ok 99937 lines

Test #27:

score: 0
Accepted
time: 86ms
memory: 12128kb

input:

100000 100000
2 14725 30550 3578 95156
1 2491 42133
1 15037 91430
1 43053 63957
1 43375 70289
2 44428 45048 18151 91105
1 29561 34904
1 69619 87629
1 19148 54183
2 27174 66629 36558 57295
1 632 82877
1 49499 54692
1 35105 71224
1 23786 56172
2 24831 61057 14881 94030
1 14214 46814
1 51726 75145
1 67...

output:

Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
...

result:

ok 9901 lines

Test #28:

score: 0
Accepted
time: 79ms
memory: 12204kb

input:

100000 100000
1 17260 57037
2 38361 49064 91393 94953
1 8286 13063
1 17841 57720
1 87304 95694
1 35042 97830
1 88264 96944
1 48341 73865
1 28982 39455
1 71608 94102
1 42832 84014
1 51985 82148
1 62447 89889
2 15429 45203 72136 96892
1 28623 97833
1 31952 58504
1 78799 92460
1 30833 34317
1 39314 818...

output:

Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
...

result:

ok 10080 lines

Test #29:

score: 0
Accepted
time: 83ms
memory: 12792kb

input:

100000 100000
1 32246 89946
1 96181 96428
1 45702 47315
1 21669 72225
1 54102 80530
1 13406 86100
1 46870 88719
1 85087 88023
1 28312 69638
1 71302 86228
1 5668 38179
1 11701 29396
1 11382 52707
1 4208 30591
1 37204 60915
1 19130 85526
1 45620 89923
1 27400 48733
2 24112 53615 55852 97808
1 14412 56...

output:

Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
...

result:

ok 10001 lines

Test #30:

score: 0
Accepted
time: 94ms
memory: 12892kb

input:

100000 100000
2 12668 57343 31511 36646
2 79451 82793 36148 43350
2 32269 98846 3121 65274
2 31644 86482 32056 81871
2 15315 68156 16189 17319
2 15544 26030 7411 79991
2 16809 68369 21760 92044
1 1984 15959
2 4470 15711 31823 40921
1 29244 77148
1 80804 96162
2 66773 79243 71580 99100
2 51480 93285 ...

output:

Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
...

result:

ok 89942 lines

Test #31:

score: 0
Accepted
time: 92ms
memory: 12336kb

input:

100000 100000
2 67765 96716 18320 67637
1 29377 93183
2 345 65364 6381 41734
1 8135 31192
1 91057 94723
2 32509 85101 48293 96086
2 12630 62078 22714 66295
2 43432 45128 18905 56400
2 12451 28537 65275 66358
2 43750 90980 76907 88907
2 10605 62921 15812 65511
2 35290 73678 14440 20889
1 67850 79966
...

output:

Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
...

result:

ok 89900 lines

Test #32:

score: 0
Accepted
time: 88ms
memory: 12372kb

input:

100000 100000
2 45014 67043 46311 56377
2 70726 90172 84299 87366
2 20631 47548 30657 40786
2 4151 82904 43535 93296
2 52332 67626 40307 79148
2 30217 74660 2247 3174
2 71075 79420 44152 83517
2 9255 50913 5951 39731
2 23143 73161 17617 41166
2 71067 83150 3611 23819
2 25138 56198 57750 62526
2 2806...

output:

Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
Not equal
...

result:

ok 89991 lines

Test #33:

score: 0
Accepted
time: 102ms
memory: 13136kb

input:

100000 200000
2 28851 48798 29255 49202
2 15339 96166 17626 98453
2 67753 86268 67637 86152
1 3038 82968
1 8827 13480
1 16541 80552
1 18483 48944
2 6578 26992 4300 24714
1 43900 50836
2 17316 40367 64484 87535
1 19839 77017
1 15711 40358
1 38260 87867
2 21961 52318 18028 48385
2 14796 44837 28860 58...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unknown
Unknown
Equal
Unknown
Unknown
Unknown
Equal
Unknown
Equal
Equal
Unknown
Unknown
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Unknown
Equal
Eq...

result:

ok 100194 lines

Test #34:

score: 0
Accepted
time: 89ms
memory: 12812kb

input:

100000 100000
2 58986 59109 94017 94140
2 83470 83714 1271 1515
2 86368 86506 38095 38233
1 15667 77718
2 88917 88920 23125 23128
2 29862 29959 85923 86020
2 1092 1364 11088 11360
2 70511 70650 94957 95096
2 17421 17587 46137 46303
2 30873 31009 70270 70406
2 45419 45602 16517 16700
2 51749 51850 44...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Equal
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Unknown
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Equal
Unknown
Un...

result:

ok 90060 lines

Test #35:

score: 0
Accepted
time: 91ms
memory: 12312kb

input:

100000 100000
2 73869 74069 63690 63890
2 96374 96670 1598 1894
2 47406 47547 14937 15078
2 74333 74409 36833 36909
2 47319 47465 80016 80162
2 84690 84725 78988 79023
1 51100 70828
1 48423 72327
2 46070 46177 82437 82544
2 9226 9536 48583 48893
2 6971 7240 35828 36097
2 9115 9163 27660 27708
2 3773...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 89972 lines

Test #36:

score: 0
Accepted
time: 91ms
memory: 12172kb

input:

100000 100000
2 67523 67544 42617 42638
2 49058 49328 29337 29607
2 1207 1370 85600 85763
2 98575 98613 6335 6373
2 96279 96547 21699 21967
2 79768 80040 88216 88488
2 5499 5667 65109 65277
1 42564 88023
2 74296 74490 78427 78621
2 35216 35345 50565 50694
2 10314 10552 95485 95723
2 73816 73830 9858...

output:

Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unknown
Unkn...

result:

ok 89953 lines

Test #37:

score: 0
Accepted
time: 95ms
memory: 11252kb

input:

100000 100000
1 50000 50001
1 49999 50002
1 49998 50003
1 49997 50004
1 49996 50005
1 49995 50006
1 49994 50007
1 49993 50008
1 49992 50009
1 49991 50010
1 49990 50011
1 49989 50012
1 49988 50013
1 49987 50014
1 49986 50015
1 49985 50016
1 49984 50017
1 49983 50018
1 49982 50019
1 49981 50020
1 4998...

output:

Equal

result:

ok single line: 'Equal'

Test #38:

score: 0
Accepted
time: 74ms
memory: 11244kb

input:

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

output:

Equal

result:

ok single line: 'Equal'