QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66106#1458. Binary Search AlgorithmeyiigjknAC ✓493ms66428kbC++141.2kb2022-12-06 19:48:002022-12-06 19:48:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-06 19:48:01]
  • 评测
  • 测评结果:AC
  • 用时:493ms
  • 内存:66428kb
  • [2022-12-06 19:48:00]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
int a[8010],b[8010],fa[8010],lc[8010],rc[8010],dis[8010];
bool cmp[8010][8010];
void query(int tot)
{
	printf("%d",tot);
	for(int i=1;i<=tot;i++) printf(" %d",a[i]);
	puts("");fflush(stdout);
	for(int i=1;i<=tot;i++) scanf("%d",&b[i]);
	for(int i=1;i<=tot;i++)
		for(int j=1;j<=tot;j++)
			cmp[b[i]][b[j]]=(i<j);
}
void pushup(int x)
{
	if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]);
	dis[x]=dis[rc[x]]+1;
}
int merge(int x,int y)
{
	if(!x || !y) return x+y;
	if(cmp[y][x]) swap(x,y);
	fa[rc[x]=merge(rc[x],y)]=x;
	pushup(x);
	return x;
}
int main()
{
	int n,x,rt=0;
	char op[10];
	cin>>n;
	fill(dis+1,dis+n+1,1);
	for(int i=0;i<2*n;i++)
	{
		scanf("%s%d",op,&x);
		if(op[0]=='a')
		{
			int tot=0;
			a[++tot]=x;
			for(int i=rt;i;i=rc[i]) a[++tot]=i;
			query(tot);
			rt=merge(rt,x);
		}
		else
		{
			int tot=0;
			for(int i=lc[x];i;i=rc[i]) a[++tot]=i;
			for(int i=rc[x];i;i=rc[i]) a[++tot]=i;
			query(tot);
			int t=merge(lc[x],rc[x]);
			fa[t]=fa[x];
			if(!fa[x]) rt=t;
			else if(lc[fa[x]]==x) lc[fa[x]]=t;
			else rc[fa[x]]=t;
			for(int i=fa[t];i;i=fa[i]) pushup(i);
		}
		printf("%d\n",rt?rt:-1);fflush(stdout);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3568kb

input:

3
add 1
1
add 3
3 1
delete 1

add 2
3 2
delete 3
2
delete 2


output:

1 1
1
2 3 1
3
0
3
2 2 3
3
1 2
2
0
-1

result:

ok n=3, OK

Test #2:

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

input:

10
add 9
9
add 4
9 4
add 6
9 6
delete 9
4 6
add 7
7 4
delete 4
6
add 5
7 5
add 8
7 5 8
add 10
7 10 5
delete 8

add 3
3 7 10
add 2
3 2
delete 6

delete 10
5
delete 7
5
add 1
3 1 2
delete 1
2
delete 3
5 2
delete 5
2
delete 2


output:

1 9
9
2 4 9
9
2 6 9
9
2 4 6
4
2 7 4
7
1 6
7
2 5 7
7
3 8 7 5
7
3 10 7 5
7
0
7
3 3 7 10
3
2 2 3
3
0
3
1 5
3
1 5
3
3 1 3 2
3
1 2
3
2 5 2
5
1 2
2
0
-1

result:

ok n=10, OK

Test #3:

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

input:

100
add 81
81
add 96
81 96
add 94
81 94
add 32
81 94 32
add 35
81 94 35
add 59
81 59 96
add 50
81 50 59
add 57
81 50 57
add 39
39 81 50 57
add 55
39 55
add 23
39 23 55
add 40
39 40 23
add 5
39 40 5
add 2
39 40 5 2
delete 55

add 12
39 12 40 5
delete 40
23 5
add 51
39 12 51
add 65
39 12 65 51
delete ...

output:

1 81
81
2 96 81
81
2 94 81
81
3 32 81 94
81
3 35 81 94
81
3 59 81 96
81
3 50 81 59
81
3 57 81 50
81
4 39 81 50 57
39
2 55 39
39
3 23 39 55
39
3 40 39 23
39
3 5 39 40
39
4 2 39 40 5
39
0
39
4 12 39 40 5
39
2 23 5
39
3 51 39 12
39
4 65 39 12 51
39
0
39
4 69 39 12 65
39
5 81 50 57 12 23
81
4 60 81 50 5...

result:

ok n=100, OK

Test #4:

score: 0
Accepted
time: 16ms
memory: 6076kb

input:

100
add 71
71
add 75
71 75
add 43
43 71
add 69
43 69
add 55
43 69 55
add 89
43 89 69
add 31
43 89 31
add 52
43 71 52
add 24
24 43 71 52
add 6
24 6
add 9
24 6 9
add 62
24 6 62
add 19
24 6 62 19
add 35
24 35 6 62
add 38
24 35 38
add 39
39 24 35 38
add 63
39 63
add 68
39 68 63
add 98
39 68 98
add 44
39...

output:

1 71
71
2 75 71
71
2 43 71
43
2 69 43
43
3 55 43 69
43
3 89 43 69
43
3 31 43 89
43
3 52 43 71
43
4 24 43 71 52
24
2 6 24
24
3 9 24 6
24
3 62 24 6
24
4 19 24 6 62
24
4 35 24 6 62
24
3 38 24 35
24
4 39 24 35 38
39
2 63 39
39
3 68 39 63
39
3 98 39 68
39
4 44 39 68 98
39
4 26 39 68 44
39
3 49 39 26
39
4...

result:

ok n=100, OK

Test #5:

score: 0
Accepted
time: 76ms
memory: 12156kb

input:

1000
add 93
93
add 917
93 917
add 921
93 921
add 70
93 921 70
add 949
93 949 921
add 777
93 949 777
add 237
93 917 237
add 581
581 93 917
add 461
581 461
add 319
581 319 461
add 42
581 42 319
add 690
581 690 42
add 631
581 631 690
add 135
581 631 135
add 424
581 631 135 424
add 647
581 631 647 135
a...

output:

1 93
93
2 917 93
93
2 921 93
93
3 70 93 921
93
3 949 93 921
93
3 777 93 949
93
3 237 93 917
93
3 581 93 917
581
2 461 581
581
3 319 581 461
581
3 42 581 319
581
3 690 581 42
581
3 631 581 690
581
3 135 581 631
581
4 424 581 631 135
581
4 647 581 631 135
581
4 165 581 631 647
581
3 901 581 165
581
4 ...

result:

ok n=1000, OK

Test #6:

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

input:

1000
add 589
589
add 844
589 844
add 341
589 341
add 362
589 341 362
add 955
955 589 341
add 565
955 565
add 467
955 565 467
add 664
955 565 664
add 167
167 955 565 664
add 879
167 879
add 934
167 934 879
add 757
167 934 757
add 941
167 934 757 941
add 56
167 934 757 56
add 337
167 934 337 879
add 8...

output:

1 589
589
2 844 589
589
2 341 589
589
3 362 589 341
589
3 955 589 341
955
2 565 955
955
3 467 955 565
955
3 664 955 565
955
4 167 955 565 664
167
2 879 167
167
3 934 167 879
167
3 757 167 934
167
4 941 167 934 757
167
4 56 167 934 757
167
4 337 167 934 879
167
4 880 167 934 337
167
5 537 167 934 337...

result:

ok n=1000, OK

Test #7:

score: 0
Accepted
time: 328ms
memory: 66060kb

input:

8000
add 2497
2497
add 827
827 2497
add 4801
827 4801
add 2709
827 4801 2709
add 4516
827 4801 4516
add 656
827 656 2497
add 4773
4773 827 656
add 1444
4773 1444
add 2338
4773 1444 2338
add 1254
4773 1444 1254
add 5749
4773 1444 1254 5749
add 3926
4773 3926 1444 1254
add 7537
4773 3926 7537
add 6800...

output:

1 2497
2497
2 827 2497
827
2 4801 827
827
3 2709 827 4801
827
3 4516 827 4801
827
3 656 827 2497
827
3 4773 827 656
4773
2 1444 4773
4773
3 2338 4773 1444
4773
3 1254 4773 1444
4773
4 5749 4773 1444 1254
4773
4 3926 4773 1444 1254
4773
3 7537 4773 3926
4773
4 6800 4773 3926 7537
4773
4 5 4773 3926 7...

result:

ok n=8000, OK

Test #8:

score: 0
Accepted
time: 319ms
memory: 66192kb

input:

8000
add 1866
1866
add 5228
5228 1866
add 4496
5228 4496
add 2574
5228 4496 2574
add 1492
5228 4496 1492
add 5427
5228 1866 5427
add 3355
3355 5228 1866
add 5495
3355 5495
add 6421
3355 5495 6421
add 7543
3355 7543 5495
add 4400
3355 4400 7543
add 4311
3355 4400 4311
add 7572
7572 3355 4400 4311
add...

output:

1 1866
1866
2 5228 1866
5228
2 4496 5228
5228
3 2574 5228 4496
5228
3 1492 5228 4496
5228
3 5427 5228 1866
5228
3 3355 5228 1866
3355
2 5495 3355
3355
3 6421 3355 5495
3355
3 7543 3355 5495
3355
3 4400 3355 7543
3355
3 4311 3355 4400
3355
4 7572 3355 4400 4311
7572
2 3077 7572
7572
3 1859 7572 3077
...

result:

ok n=8000, OK

Test #9:

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

input:

1000
add 964
964
add 650
964 650
add 967
964 967
add 129
964 967 129
add 345
964 967 345
add 454
964 650 454
add 614
964 650 614
add 11
964 650 614 11
add 963
964 650 614 963
add 357
964 650 454 357
add 300
964 650 454 300
add 785
964 967 345 785
add 700
964 967 345 700
add 442
964 967 129 442
add 1...

output:

1 964
964
2 650 964
964
2 967 964
964
3 129 964 967
964
3 345 964 967
964
3 454 964 650
964
3 614 964 650
964
4 11 964 650 614
964
4 963 964 650 614
964
4 357 964 650 454
964
4 300 964 650 454
964
4 785 964 967 345
964
4 700 964 967 345
964
4 442 964 967 129
964
4 14 964 967 129
964
5 79 964 967 129...

result:

ok n=1000, OK

Test #10:

score: 0
Accepted
time: 73ms
memory: 10776kb

input:

1000
add 651
651
add 792
792 651
add 816
792 816
add 325
792 816 325
add 876
792 816 876
add 408
792 651 408
add 289
792 289 651
add 746
792 746 289
add 492
792 746 492
add 2
792 746 2 492
add 462
792 746 462 2
add 98
792 746 462 98
add 68
792 746 68 289
add 69
792 746 68 69
add 834
792 816 834 876
...

output:

1 651
651
2 792 651
792
2 816 792
792
3 325 792 816
792
3 876 792 816
792
3 408 792 651
792
3 289 792 651
792
3 746 792 289
792
3 492 792 746
792
4 2 792 746 492
792
4 462 792 746 2
792
4 98 792 746 462
792
4 68 792 746 289
792
4 69 792 746 68
792
4 834 792 816 876
792
4 664 792 816 834
792
4 618 79...

result:

ok n=1000, OK

Test #11:

score: 0
Accepted
time: 362ms
memory: 66240kb

input:

8000
add 4964
4964
add 650
4964 650
add 6871
4964 6871
add 129
4964 6871 129
add 3768
4964 6871 3768
add 1551
4964 650 1551
add 6223
4964 650 6223
add 3875
4964 650 6223 3875
add 6536
4964 650 6223 6536
add 6438
4964 650 1551 6438
add 5015
4964 650 1551 5015
add 2528
4964 6871 3768 2528
add 1952
496...

output:

1 4964
4964
2 650 4964
4964
2 6871 4964
4964
3 129 4964 6871
4964
3 3768 4964 6871
4964
3 1551 4964 650
4964
3 6223 4964 650
4964
4 3875 4964 650 6223
4964
4 6536 4964 650 6223
4964
4 6438 4964 650 1551
4964
4 5015 4964 650 1551
4964
4 2528 4964 6871 3768
4964
4 1952 4964 6871 3768
4964
4 6441 4964 ...

result:

ok n=8000, OK

Test #12:

score: 0
Accepted
time: 409ms
memory: 66380kb

input:

8000
add 3562
3562
add 2628
3562 2628
add 6508
6508 3562
add 1830
6508 1830
add 6995
6508 6995 1830
add 2741
6508 6995 2741
add 3523
6508 3562 3523
add 4497
6508 4497 3562 3523
add 1175
6508 4497 1175
add 5626
6508 4497 5626 1175
add 2252
6508 4497 5626 2252
add 2606
6508 6995 2741 2606
add 6190
650...

output:

1 3562
3562
2 2628 3562
3562
2 6508 3562
6508
2 1830 6508
6508
3 6995 6508 1830
6508
3 2741 6508 6995
6508
3 3523 6508 3562
6508
4 4497 6508 3562 3523
6508
3 1175 6508 4497
6508
4 5626 6508 4497 1175
6508
4 2252 6508 4497 5626
6508
4 2606 6508 6995 2741
6508
4 6190 6508 6995 2741
6508
4 15 6508 6995...

result:

ok n=8000, OK

Test #13:

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

input:

10
add 3
3
add 7
3 7
add 10
3 10
add 1
3 10 1
add 9
3 10 9
add 5
3 7 5
add 4
3 7 4
add 8
3 7 4 8
add 6
3 7 4 6
add 2
3 7 5 2
delete 3
7 10 9 5
delete 7
10 9 4 6
delete 10
1 9 5
delete 9
5 4 6
delete 5
4 6 2
delete 4
8 6
delete 6
2
delete 2

delete 1
8
delete 8


output:

1 3
3
2 7 3
3
2 10 3
3
3 1 3 10
3
3 9 3 10
3
3 5 3 7
3
3 4 3 7
3
4 8 3 7 4
3
4 6 3 7 4
3
4 2 3 7 5
3
4 10 9 7 5
7
4 4 6 10 9
10
3 9 5 1
1
3 4 6 5
1
3 4 6 2
1
2 8 6
1
1 2
1
0
1
1 8
8
0
-1

result:

ok n=10, OK

Test #14:

score: 0
Accepted
time: 4ms
memory: 3736kb

input:

10
add 9
9
add 5
9 5
add 2
9 2
add 7
7 9 2
add 4
7 4
add 3
3 7 4
add 1
3 1
add 6
3 1 6
add 10
3 10 1
add 8
3 10 8
delete 3
7 10 4 8
delete 7
10 9 4 2
delete 9
5 4 2
delete 4
8 2
delete 2

delete 10
1 5
delete 1
5 6
delete 5
8 6
delete 8
6
delete 6


output:

1 9
9
2 5 9
9
2 2 9
9
3 7 9 2
7
2 4 7
7
3 3 7 4
3
2 1 3
3
3 6 3 1
3
3 10 3 1
3
3 8 3 10
3
4 7 4 10 8
7
4 9 2 10 4
10
3 4 2 5
10
2 8 2
10
0
10
2 5 1
1
2 6 5
5
2 8 6
8
1 6
6
0
-1

result:

ok n=10, OK

Test #15:

score: 0
Accepted
time: 35ms
memory: 12000kb

input:

1000
add 964
964
add 650
964 650
add 967
964 967
add 129
964 967 129
add 345
964 967 345
add 454
964 650 454
add 614
964 650 614
add 11
964 650 614 11
add 963
964 650 614 963
add 357
964 650 454 357
add 300
964 650 454 300
add 785
964 967 345 785
add 700
964 967 345 700
add 442
964 967 129 442
add 1...

output:

1 964
964
2 650 964
964
2 967 964
964
3 129 964 967
964
3 345 964 967
964
3 454 964 650
964
3 614 964 650
964
4 11 964 650 614
964
4 963 964 650 614
964
4 357 964 650 454
964
4 300 964 650 454
964
4 785 964 967 345
964
4 700 964 967 345
964
4 442 964 967 129
964
4 14 964 967 129
964
5 79 964 967 129...

result:

ok n=1000, OK

Test #16:

score: 0
Accepted
time: 25ms
memory: 12004kb

input:

1000
add 871
871
add 449
449 871
add 644
644 449
add 97
97 644
add 853
853 97
add 496
496 853
add 418
418 496
add 207
207 418
add 401
401 207
add 519
519 401
add 276
276 519
add 576
576 276
add 74
74 576
add 194
194 74
add 719
719 194
add 252
252 719
add 718
718 252
add 137
137 718
add 292
292 137
a...

output:

1 871
871
2 449 871
449
2 644 449
644
2 97 644
97
2 853 97
853
2 496 853
496
2 418 496
418
2 207 418
207
2 401 207
401
2 519 401
519
2 276 519
276
2 576 276
576
2 74 576
74
2 194 74
194
2 719 194
719
2 252 719
252
2 718 252
718
2 137 718
137
2 292 137
292
2 902 292
902
2 530 902
530
2 461 530
461
2 ...

result:

ok n=1000, OK

Test #17:

score: 0
Accepted
time: 20ms
memory: 12524kb

input:

1000
add 35
35
add 747
35 747
add 391
35 391
add 770
35 391 770
add 707
35 391 707
add 344
35 747 344
add 881
35 747 881
add 753
35 747 881 753
add 266
35 747 881 266
add 126
126 35 747 344
add 11
11 126
add 705
11 705
add 672
11 672 705
add 107
11 107 672
add 439
11 107 439
add 958
11 126 958
add 4...

output:

1 35
35
2 747 35
35
2 391 35
35
3 770 35 391
35
3 707 35 391
35
3 344 35 747
35
3 881 35 747
35
4 753 35 747 881
35
4 266 35 747 881
35
4 126 35 747 344
126
2 11 126
11
2 705 11
11
3 672 11 705
11
3 107 11 672
11
3 439 11 107
11
3 958 11 126
11
4 432 11 126 958
11
4 26 11 126 958
11
4 945 11 107 439...

result:

ok n=1000, OK

Test #18:

score: 0
Accepted
time: 45ms
memory: 12100kb

input:

1000
add 914
914
add 326
326 914
add 650
650 326
add 629
650 629
add 626
650 626 629
add 416
650 626 416
add 785
650 785 326
add 837
650 785 837
add 300
650 300 785 837
add 700
650 300 700
add 164
650 300 700 164
add 786
650 300 700 786
add 304
650 626 416 304
add 450
650 450 626 416
add 72
650 72 4...

output:

1 914
914
2 326 914
326
2 650 326
650
2 629 650
650
3 626 650 629
650
3 416 650 626
650
3 785 650 326
650
3 837 650 785
650
4 300 650 785 837
650
3 700 650 300
650
4 164 650 300 700
650
4 786 650 300 700
650
4 304 650 626 416
650
4 450 650 626 416
650
3 72 650 450
650
3 357 650 72
650
3 318 650 357
...

result:

ok n=1000, OK

Test #19:

score: 0
Accepted
time: 18ms
memory: 11820kb

input:

1000
add 129
129
add 786
129 786
add 614
129 614
add 967
967 129 614
add 454
967 454
add 34
967 454 34
add 700
967 454 700
add 300
967 454 300 700
add 488
967 454 300 488
add 963
967 454 963 34
add 79
967 454 963 79
add 743
967 129 614 743
add 11
967 129 614 11
add 384
967 129 384 786
add 980
967 12...

output:

1 129
129
2 786 129
129
2 614 129
129
3 967 129 614
967
2 454 967
967
3 34 967 454
967
3 700 967 454
967
4 300 967 454 700
967
4 488 967 454 300
967
4 963 967 454 34
967
4 79 967 454 963
967
4 743 967 129 614
967
4 11 967 129 614
967
4 384 967 129 786
967
4 980 967 129 384
967
5 972 967 129 384 980
...

result:

ok n=1000, OK

Test #20:

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

input:

8000
add 4964
4964
add 650
4964 650
add 6871
4964 6871
add 129
4964 6871 129
add 3768
4964 6871 3768
add 1551
4964 650 1551
add 6223
4964 650 6223
add 3875
4964 650 6223 3875
add 6536
4964 650 6223 6536
add 6438
4964 650 1551 6438
add 5015
4964 650 1551 5015
add 2528
4964 6871 3768 2528
add 1952
496...

output:

1 4964
4964
2 650 4964
4964
2 6871 4964
4964
3 129 4964 6871
4964
3 3768 4964 6871
4964
3 1551 4964 650
4964
3 6223 4964 650
4964
4 3875 4964 650 6223
4964
4 6536 4964 650 6223
4964
4 6438 4964 650 1551
4964
4 5015 4964 650 1551
4964
4 2528 4964 6871 3768
4964
4 1952 4964 6871 3768
4964
4 6441 4964 ...

result:

ok n=8000, OK

Test #21:

score: 0
Accepted
time: 275ms
memory: 59020kb

input:

8000
add 3493
3493
add 5110
5110 3493
add 533
533 5110
add 1700
1700 533
add 4277
4277 1700
add 2368
2368 4277
add 4495
4495 2368
add 4305
4305 4495
add 6965
6965 4305
add 2503
2503 6965
add 4339
4339 2503
add 5195
5195 4339
add 2364
2364 5195
add 3802
3802 2364
add 1752
1752 3802
add 6812
6812 1752...

output:

1 3493
3493
2 5110 3493
5110
2 533 5110
533
2 1700 533
1700
2 4277 1700
4277
2 2368 4277
2368
2 4495 2368
4495
2 4305 4495
4305
2 6965 4305
6965
2 2503 6965
2503
2 4339 2503
4339
2 5195 4339
5195
2 2364 5195
2364
2 3802 2364
3802
2 1752 3802
1752
2 6812 1752
6812
2 2956 6812
2956
2 497 2956
497
2 14...

result:

ok n=8000, OK

Test #22:

score: 0
Accepted
time: 382ms
memory: 66236kb

input:

8000
add 612
612
add 2743
612 2743
add 7916
612 7916
add 1433
1433 612 7916
add 2140
1433 2140
add 840
1433 2140 840
add 4289
1433 4289 2140
add 3912
1433 4289 3912
add 6323
1433 4289 3912 6323
add 3859
1433 4289 3859 3912
add 4368
1433 4289 3859 4368
add 6046
1433 4289 6046 2140
add 1405
1433 4289 ...

output:

1 612
612
2 2743 612
612
2 7916 612
612
3 1433 612 7916
1433
2 2140 1433
1433
3 840 1433 2140
1433
3 4289 1433 2140
1433
3 3912 1433 4289
1433
4 6323 1433 4289 3912
1433
4 3859 1433 4289 3912
1433
4 4368 1433 4289 3859
1433
4 6046 1433 4289 2140
1433
4 1405 1433 4289 6046
1433
4 5687 1433 612 7916
1...

result:

ok n=8000, OK

Test #23:

score: 0
Accepted
time: 332ms
memory: 66212kb

input:

8000
add 3393
3393
add 5029
5029 3393
add 650
650 5029
add 3599
650 3599
add 5102
650 5102 3599
add 5122
650 5102 5122
add 6641
650 5029 6641
add 475
650 5029 6641 475
add 1323
650 5029 6641 1323
add 1821
650 1821 5029 3393
add 3447
650 1821 3447
add 578
650 1821 3447 578
add 7293
650 1821 7293 3447...

output:

1 3393
3393
2 5029 3393
5029
2 650 5029
650
2 3599 650
650
3 5102 650 3599
650
3 5122 650 5102
650
3 6641 650 5029
650
4 475 650 5029 6641
650
4 1323 650 5029 6641
650
4 1821 650 5029 3393
650
3 3447 650 1821
650
4 578 650 1821 3447
650
4 7293 650 1821 3447
650
4 5600 650 1821 7293
650
4 5900 650 51...

result:

ok n=8000, OK

Test #24:

score: 0
Accepted
time: 376ms
memory: 66424kb

input:

8000
add 3768
3768
add 878
3768 878
add 5029
3768 5029
add 1821
3768 1821 5029
add 5001
3768 1821 5001
add 1608
3768 1608 878
add 2691
3768 1608 2691
add 7293
3768 1608 2691 7293
add 7275
3768 7275 1608 2691
add 6223
3768 6223 7275
add 227
3768 6223 227
add 3809
3768 6223 3809 227
add 4675
3768 6223...

output:

1 3768
3768
2 878 3768
3768
2 5029 3768
3768
3 1821 3768 5029
3768
3 5001 3768 1821
3768
3 1608 3768 878
3768
3 2691 3768 1608
3768
4 7293 3768 1608 2691
3768
4 7275 3768 1608 2691
3768
3 6223 3768 7275
3768
3 227 3768 6223
3768
4 3809 3768 6223 227
3768
4 4675 3768 6223 3809
3768
4 5397 3768 6223 7...

result:

ok n=8000, OK

Test #25:

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

input:

10
add 3
3
add 7
3 7
add 10
3 10
add 1
3 10 1
add 9
3 10 9
add 5
3 7 5
add 4
3 7 4
add 8
3 7 4 8
add 6
3 7 4 6
add 2
3 7 5 2
delete 3
7 10 9 5
delete 7
10 9 4 6
delete 10
1 9 5
delete 9
5 4 6
delete 4
8 6
delete 5
8 2
delete 8
6 2
delete 6
2
delete 1
2
delete 2


output:

1 3
3
2 7 3
3
2 10 3
3
3 1 3 10
3
3 9 3 10
3
3 5 3 7
3
3 4 3 7
3
4 8 3 7 4
3
4 6 3 7 4
3
4 2 3 7 5
3
4 10 9 7 5
7
4 4 6 10 9
10
3 9 5 1
1
3 4 6 5
1
2 8 6
1
2 8 2
1
2 6 2
1
1 2
1
1 2
2
0
-1

result:

ok n=10, OK

Test #26:

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

input:

10
add 10
10
add 8
10 8
add 4
10 4
add 3
3 10 4
add 6
3 6
add 1
3 1 6
add 7
3 7 1
add 2
3 7 2
add 9
3 7 9 2
add 5
3 7 9 5
delete 3
7 10 1 4
delete 7
10 9 5 8
delete 10
1 9 5 4
delete 9
5 4 2
delete 5
4 8
delete 4
8 2
delete 1
8 6
delete 8
6 2
delete 6
2
delete 2


output:

1 10
10
2 8 10
10
2 4 10
10
3 3 10 4
3
2 6 3
3
3 1 3 6
3
3 7 3 1
3
3 2 3 7
3
4 9 3 7 2
3
4 5 3 7 9
3
4 10 4 7 1
7
4 9 5 10 8
10
4 1 4 9 5
1
3 5 4 2
1
2 8 4
1
2 2 8
1
2 8 6
8
2 2 6
6
1 2
2
0
-1

result:

ok n=10, OK

Test #27:

score: 0
Accepted
time: 34ms
memory: 11916kb

input:

1000
add 964
964
add 650
964 650
add 967
964 967
add 129
964 967 129
add 345
964 967 345
add 454
964 650 454
add 614
964 650 614
add 11
964 650 614 11
add 963
964 650 614 963
add 357
964 650 454 357
add 300
964 650 454 300
add 785
964 967 345 785
add 700
964 967 345 700
add 442
964 967 129 442
add 1...

output:

1 964
964
2 650 964
964
2 967 964
964
3 129 964 967
964
3 345 964 967
964
3 454 964 650
964
3 614 964 650
964
4 11 964 650 614
964
4 963 964 650 614
964
4 357 964 650 454
964
4 300 964 650 454
964
4 785 964 967 345
964
4 700 964 967 345
964
4 442 964 967 129
964
4 14 964 967 129
964
5 79 964 967 129...

result:

ok n=1000, OK

Test #28:

score: 0
Accepted
time: 8ms
memory: 12016kb

input:

1000
add 871
871
add 449
449 871
add 644
644 449
add 97
97 644
add 853
853 97
add 496
496 853
add 418
418 496
add 207
207 418
add 401
401 207
add 519
519 401
add 276
276 519
add 576
576 276
add 74
74 576
add 194
194 74
add 719
719 194
add 252
252 719
add 718
718 252
add 137
137 718
add 292
292 137
a...

output:

1 871
871
2 449 871
449
2 644 449
644
2 97 644
97
2 853 97
853
2 496 853
496
2 418 496
418
2 207 418
207
2 401 207
401
2 519 401
519
2 276 519
276
2 576 276
576
2 74 576
74
2 194 74
194
2 719 194
719
2 252 719
252
2 718 252
718
2 137 718
137
2 292 137
292
2 902 292
902
2 530 902
530
2 461 530
461
2 ...

result:

ok n=1000, OK

Test #29:

score: 0
Accepted
time: 24ms
memory: 12468kb

input:

1000
add 986
986
add 800
986 800
add 897
986 897
add 601
601 986 897
add 858
858 601
add 627
858 627
add 398
858 627 398
add 124
858 124 627
add 885
858 124 885
add 554
858 554 601
add 234
858 554 234
add 482
858 482 554 234
add 489
858 482 489
add 771
858 482 489 771
add 508
858 482 489 508
add 748...

output:

1 986
986
2 800 986
986
2 897 986
986
3 601 986 897
601
2 858 601
858
2 627 858
858
3 398 858 627
858
3 124 858 627
858
3 885 858 124
858
3 554 858 601
858
3 234 858 554
858
4 482 858 554 234
858
3 489 858 482
858
4 771 858 482 489
858
4 508 858 482 489
858
4 748 858 124 885
858
4 361 858 124 885
85...

result:

ok n=1000, OK

Test #30:

score: 0
Accepted
time: 31ms
memory: 12544kb

input:

1000
add 101
101
add 442
442 101
add 183
442 183
add 373
442 373 183
add 837
442 837 373
add 326
442 837 326
add 585
442 101 585
add 450
442 101 450
add 15
442 101 15 450
add 626
442 101 15 626
add 914
442 101 585 914
add 786
442 101 585 786
add 494
442 837 326 494
add 828
442 828 837 326
add 93
442...

output:

1 101
101
2 442 101
442
2 183 442
442
3 373 442 183
442
3 837 442 373
442
3 326 442 837
442
3 585 442 101
442
3 450 442 101
442
4 15 442 101 450
442
4 626 442 101 15
442
4 914 442 101 585
442
4 786 442 101 585
442
4 494 442 837 326
442
4 828 442 837 326
442
3 93 442 828
442
4 878 442 828 93
442
4 61...

result:

ok n=1000, OK

Test #31:

score: 0
Accepted
time: 35ms
memory: 12604kb

input:

1000
add 79
79
add 442
442 79
add 454
454 442
add 520
454 520
add 101
454 101 520
add 343
454 343 101
add 585
454 343 585
add 700
454 700 442
add 632
454 700 632
add 300
454 300 700 632
add 878
454 300 878
add 64
454 300 64 878
add 227
454 300 64 227
add 964
964 454 343 585
add 828
964 828
add 488
9...

output:

1 79
79
2 442 79
442
2 454 442
454
2 520 454
454
3 101 454 520
454
3 343 454 101
454
3 585 454 343
454
3 700 454 442
454
3 632 454 700
454
4 300 454 700 632
454
3 878 454 300
454
4 64 454 300 878
454
4 227 454 300 64
454
4 964 454 343 585
964
2 828 964
964
3 488 964 828
964
3 980 964 828
964
4 581 9...

result:

ok n=1000, OK

Test #32:

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

input:

1000
add 964
964
add 871
964 871
add 449
964 449
add 644
964 644 449
add 97
964 97 644
add 853
964 853 97
add 496
964 496 853
add 418
964 418 496
add 207
964 207 418
add 401
964 401 207
add 519
964 519 401
add 276
964 276 519
add 576
964 576 276
add 74
964 74 576
add 194
964 194 74
add 719
964 719 1...

output:

1 964
964
2 871 964
964
2 449 964
964
3 644 964 449
964
3 97 964 644
964
3 853 964 97
964
3 496 964 853
964
3 418 964 496
964
3 207 964 418
964
3 401 964 207
964
3 519 964 401
964
3 276 964 519
964
3 576 964 276
964
3 74 964 576
964
3 194 964 74
964
3 719 964 194
964
3 252 964 719
964
3 718 964 252
...

result:

ok n=1000, OK

Test #33:

score: 0
Accepted
time: 342ms
memory: 66212kb

input:

8000
add 4964
4964
add 650
4964 650
add 6871
4964 6871
add 129
4964 6871 129
add 3768
4964 6871 3768
add 1551
4964 650 1551
add 6223
4964 650 6223
add 3875
4964 650 6223 3875
add 6536
4964 650 6223 6536
add 6438
4964 650 1551 6438
add 5015
4964 650 1551 5015
add 2528
4964 6871 3768 2528
add 1952
496...

output:

1 4964
4964
2 650 4964
4964
2 6871 4964
4964
3 129 4964 6871
4964
3 3768 4964 6871
4964
3 1551 4964 650
4964
3 6223 4964 650
4964
4 3875 4964 650 6223
4964
4 6536 4964 650 6223
4964
4 6438 4964 650 1551
4964
4 5015 4964 650 1551
4964
4 2528 4964 6871 3768
4964
4 1952 4964 6871 3768
4964
4 6441 4964 ...

result:

ok n=8000, OK

Test #34:

score: 0
Accepted
time: 236ms
memory: 60152kb

input:

8000
add 3493
3493
add 5110
5110 3493
add 533
533 5110
add 1700
1700 533
add 4277
4277 1700
add 2368
2368 4277
add 4495
4495 2368
add 4305
4305 4495
add 6965
6965 4305
add 2503
2503 6965
add 4339
4339 2503
add 5195
5195 4339
add 2364
2364 5195
add 3802
3802 2364
add 1752
1752 3802
add 6812
6812 1752...

output:

1 3493
3493
2 5110 3493
5110
2 533 5110
533
2 1700 533
1700
2 4277 1700
4277
2 2368 4277
2368
2 4495 2368
4495
2 4305 4495
4305
2 6965 4305
6965
2 2503 6965
2503
2 4339 2503
4339
2 5195 4339
5195
2 2364 5195
2364
2 3802 2364
3802
2 1752 3802
1752
2 6812 1752
6812
2 2956 6812
2956
2 497 2956
497
2 14...

result:

ok n=8000, OK

Test #35:

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

input:

8000
add 1338
1338
add 1220
1338 1220
add 2046
1338 2046
add 5158
5158 1338 2046
add 1439
5158 1439
add 412
5158 412 1439
add 5737
5737 5158 412
add 3968
5737 3968
add 703
5737 703 3968
add 2858
5737 2858 703
add 2783
5737 2858 2783
add 3798
5737 2858 3798 2783
add 5455
5737 2858 3798 5455
add 3890
...

output:

1 1338
1338
2 1220 1338
1338
2 2046 1338
1338
3 5158 1338 2046
5158
2 1439 5158
5158
3 412 5158 1439
5158
3 5737 5158 412
5737
2 3968 5737
5737
3 703 5737 3968
5737
3 2858 5737 703
5737
3 2783 5737 2858
5737
4 3798 5737 2858 2783
5737
4 5455 5737 2858 3798
5737
4 3890 5737 2858 703
5737
4 439 5737 5...

result:

ok n=8000, OK

Test #36:

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

input:

8000
add 6131
6131
add 4520
6131 4520
add 6799
6131 6799
add 1676
6131 1676 6799
add 1844
6131 1676 1844
add 6912
6131 4520 6912
add 3621
6131 4520 3621
add 4018
4018 6131 4520 3621
add 1178
4018 1178
add 2082
4018 1178 2082
add 6172
6172 4018 1178
add 1568
6172 1568
add 7404
6172 7404 1568
add 3759...

output:

1 6131
6131
2 4520 6131
6131
2 6799 6131
6131
3 1676 6131 6799
6131
3 1844 6131 1676
6131
3 6912 6131 4520
6131
3 3621 6131 4520
6131
4 4018 6131 4520 3621
4018
2 1178 4018
4018
3 2082 4018 1178
4018
3 6172 4018 1178
6172
2 1568 6172
6172
3 7404 6172 1568
6172
3 3759 6172 7404
6172
4 6187 6172 7404 ...

result:

ok n=8000, OK

Test #37:

score: 0
Accepted
time: 273ms
memory: 66428kb

input:

8000
add 893
893
add 2960
2960 893
add 7459
7459 2960
add 111
111 7459
add 1185
111 1185
add 3327
111 3327 1185
add 5397
5397 111 3327
add 3963
5397 3963
add 4988
5397 3963 4988
add 6640
5397 6640 3963
add 3584
5397 6640 3584
add 5536
5397 5536 6640 3584
add 6178
5397 5536 6178
add 1119
5397 1119 55...

output:

1 893
893
2 2960 893
2960
2 7459 2960
7459
2 111 7459
111
2 1185 111
111
3 3327 111 1185
111
3 5397 111 3327
5397
2 3963 5397
5397
3 4988 5397 3963
5397
3 6640 5397 3963
5397
3 3584 5397 6640
5397
4 5536 5397 6640 3584
5397
3 6178 5397 5536
5397
4 1119 5397 5536 6178
5397
3 6349 5397 1119
5397
3 397...

result:

ok n=8000, OK

Test #38:

score: 0
Accepted
time: 273ms
memory: 66240kb

input:

8000
add 3768
3768
add 355
3768 355
add 5755
3768 5755
add 5029
3768 5029 5755
add 5530
3768 5029 5530
add 7826
3768 7826 355
add 6194
3768 6194 7826
add 1821
3768 1821 6194
add 1113
3768 1821 1113
add 5015
3768 5015 1821 1113
add 343
3768 5015 343
add 650
650 3768 5015 343
add 878
650 878
add 6641
...

output:

1 3768
3768
2 355 3768
3768
2 5755 3768
3768
3 5029 3768 5755
3768
3 5530 3768 5029
3768
3 7826 3768 355
3768
3 6194 3768 7826
3768
3 1821 3768 6194
3768
3 1113 3768 1821
3768
4 5015 3768 1821 1113
3768
3 343 3768 5015
3768
4 650 3768 5015 343
650
2 878 650
650
3 6641 650 878
650
3 165 650 878
650
4...

result:

ok n=8000, OK

Test #39:

score: 0
Accepted
time: 343ms
memory: 66228kb

input:

8000
add 3325
3325
add 5911
3325 5911
add 664
3325 664
add 708
3325 708 664
add 3589
3325 3589 708
add 3869
3325 3869 3589
add 6353
3325 6353 3869
add 5408
3325 6353 5408
add 2396
3325 5911 2396
add 1926
3325 1926 5911
add 3822
3325 1926 3822
add 2476
3325 1926 2476 3822
add 6482
3325 1926 2476 6482...

output:

1 3325
3325
2 5911 3325
3325
2 664 3325
3325
3 708 3325 664
3325
3 3589 3325 708
3325
3 3869 3325 3589
3325
3 6353 3325 3869
3325
3 5408 3325 6353
3325
3 2396 3325 5911
3325
3 1926 3325 5911
3325
3 3822 3325 1926
3325
4 2476 3325 1926 3822
3325
4 6482 3325 1926 2476
3325
4 6067 3325 1926 5911
3325
4...

result:

ok n=8000, OK

Test #40:

score: 0
Accepted
time: 296ms
memory: 66240kb

input:

8000
add 520
520
add 4857
4857 520
add 3380
4857 3380
add 5397
4857 5397 3380
add 1551
1551 4857 5397
add 4675
1551 4675
add 5755
1551 4675 5755
add 2691
1551 4675 2691
add 3809
1551 3809 4675 2691
add 1608
1551 3809 1608
add 4679
1551 3809 1608 4679
add 6194
1551 3809 1608 6194
add 6223
1551 6223 4...

output:

1 520
520
2 4857 520
4857
2 3380 4857
4857
3 5397 4857 3380
4857
3 1551 4857 5397
1551
2 4675 1551
1551
3 5755 1551 4675
1551
3 2691 1551 4675
1551
4 3809 1551 4675 2691
1551
3 1608 1551 3809
1551
4 4679 1551 3809 1608
1551
4 6194 1551 3809 1608
1551
4 6223 1551 4857 5397
1551
3 5029 1551 6223
1551
...

result:

ok n=8000, OK

Test #41:

score: 0
Accepted
time: 293ms
memory: 66280kb

input:

8000
add 3540
3540
add 6114
6114 3540
add 7095
6114 7095
add 7142
6114 7095 7142
add 4694
6114 7095 4694
add 1040
6114 3540 1040
add 2503
6114 3540 2503
add 5498
6114 3540 5498 2503
add 4061
6114 3540 4061 5498
add 213
6114 3540 4061 213
add 300
6114 300 3540 1040
add 20
6114 300 20
add 2632
2632 61...

output:

1 3540
3540
2 6114 3540
6114
2 7095 6114
6114
3 7142 6114 7095
6114
3 4694 6114 7095
6114
3 1040 6114 3540
6114
3 2503 6114 3540
6114
4 5498 6114 3540 2503
6114
4 4061 6114 3540 5498
6114
4 213 6114 3540 4061
6114
4 300 6114 3540 1040
6114
3 20 6114 300
6114
4 2632 6114 300 20
2632
2 1907 2632
2632
...

result:

ok n=8000, OK

Test #42:

score: 0
Accepted
time: 344ms
memory: 66208kb

input:

8000
add 6663
6663
add 7408
7408 6663
add 2088
2088 7408
add 1213
2088 1213
add 3752
3752 2088 1213
add 4898
3752 4898
add 6916
3752 6916 4898
add 3470
3470 3752 6916
add 6588
3470 6588
add 6136
3470 6588 6136
add 3508
3508 3470 6588
add 3236
3508 3236
add 5297
3508 3236 5297
add 4892
3508 3236 4892...

output:

1 6663
6663
2 7408 6663
7408
2 2088 7408
2088
2 1213 2088
2088
3 3752 2088 1213
3752
2 4898 3752
3752
3 6916 3752 4898
3752
3 3470 3752 6916
3470
2 6588 3470
3470
3 6136 3470 6588
3470
3 3508 3470 6588
3508
2 3236 3508
3508
3 5297 3508 3236
3508
3 4892 3508 3236
3508
4 5294 3508 3236 4892
3508
4 124...

result:

ok n=8000, OK

Test #43:

score: 0
Accepted
time: 294ms
memory: 66208kb

input:

8000
add 6663
6663
add 2364
6663 2364
add 7626
6663 7626
add 131
131 6663 7626
add 6567
131 6567
add 6812
131 6567 6812
add 4718
131 6567 4718
add 1312
1312 131 6567 4718
add 5091
1312 5091
add 4819
4819 1312 5091
add 1421
4819 1421
add 2361
4819 2361 1421
add 3596
4819 3596 2361
add 6973
4819 3596 ...

output:

1 6663
6663
2 2364 6663
6663
2 7626 6663
6663
3 131 6663 7626
131
2 6567 131
131
3 6812 131 6567
131
3 4718 131 6567
131
4 1312 131 6567 4718
1312
2 5091 1312
1312
3 4819 1312 5091
4819
2 1421 4819
4819
3 2361 4819 1421
4819
3 3596 4819 2361
4819
3 6973 4819 3596
4819
4 7912 4819 3596 6973
4819
4 46...

result:

ok n=8000, OK

Test #44:

score: 0
Accepted
time: 300ms
memory: 66396kb

input:

8000
add 4339
4339
add 615
615 4339
add 7105
615 7105
add 4718
615 7105 4718
add 2503
615 7105 2503
add 4810
615 4810 4339
add 6965
615 4810 6965
add 1700
615 4810 6965 1700
add 533
615 4810 6965 533
add 3145
615 3145 4810 4339
add 6288
6288 615 3145
add 2496
6288 2496
add 4305
6288 2496 4305
add 31...

output:

1 4339
4339
2 615 4339
615
2 7105 615
615
3 4718 615 7105
615
3 2503 615 7105
615
3 4810 615 4339
615
3 6965 615 4810
615
4 1700 615 4810 6965
615
4 533 615 4810 6965
615
4 3145 615 4810 4339
615
3 6288 615 3145
6288
2 2496 6288
6288
3 4305 6288 2496
6288
3 3187 6288 2496
6288
3 2571 6288 3187
6288
...

result:

ok n=8000, OK

Test #45:

score: 0
Accepted
time: 237ms
memory: 64276kb

input:

8000
add 4964
4964
add 3493
4964 3493
add 5110
4964 5110
add 533
4964 533 5110
add 1700
4964 1700 533
add 4277
4964 4277 1700
add 2368
4964 2368 4277
add 4495
4964 4495 2368
add 4305
4964 4305 4495
add 6965
4964 6965 4305
add 2503
4964 2503 6965
add 4339
4964 4339 2503
add 5195
4964 5195 4339
add 23...

output:

1 4964
4964
2 3493 4964
4964
2 5110 4964
4964
3 533 4964 5110
4964
3 1700 4964 533
4964
3 4277 4964 1700
4964
3 2368 4964 4277
4964
3 4495 4964 2368
4964
3 4305 4964 4495
4964
3 6965 4964 4305
4964
3 2503 4964 6965
4964
3 4339 4964 2503
4964
3 5195 4964 4339
4964
3 2364 4964 5195
4964
3 3802 4964 23...

result:

ok n=8000, OK