QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#62004#2830. Data StructurelarryzhongAC ✓346ms37944kbC++172.6kb2022-11-16 20:54:192022-11-16 20:54:22

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 3
2 1 2
2 1 2
0
1 1
2 1 1
3 4
2 1 3
2 2 3
1 1
1 2

output:

3
1 3
2 3
1 2
0
-1

result:

ok 3 cases passed. max #moves/#balls = 1.500000000

Test #2:

score: 0
Accepted
time: 2ms
memory: 3536kb

input:

1 2
1 1
1 1
1 3
1 1
0
1 1
1 4
1 1
1 1
0
0
1 1
2 1 1
1 2
2 1 1
0
1 3
0
0
2 1 1

output:

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

result:

ok 6 cases passed. max #moves/#balls = 1.000000000

Test #3:

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

input:

2 4
1 1
1 2
1 2
1 1
2 5
1 1
1 2
0
1 1
1 2
2 6
0
1 1
0
1 1
1 2
1 2
2 4
1 2
1 1
1 1
1 2
2 5
1 1
0
1 2
1 2
1 1
2 6
1 2
0
1 1
0
1 1
1 2
2 4
1 1
1 2
1 2
1 1
2 5
0
1 2
1 1
1 1
1 2
2 6
1 1
0
1 2
1 2
0
1 1
2 3
2 2 1
1 1
1 2
2 4
2 2 1
1 1
0
1 2
2 5
1 1
0
1 2
2 1 2
0
2 3
1 2
2 1 2
1 1
2 4
1 1
2 2 1
1 2
0
2 5
...

output:

2
2 3
1 4
2
1 4
2 5
2
2 4
5 6
2
2 3
1 4
2
3 4
1 5
2
3 5
1 6
2
2 3
1 4
2
3 4
2 5
2
3 4
1 6
2
1 2
3 1
2
1 2
4 1
2
4 3
1 4
2
2 1
3 2
2
2 1
3 2
2
1 3
4 1
-1
3
2 1
3 1
2 3
3
2 1
4 1
2 4
-1
3
2 3
1 2
3 1
3
1 3
2 1
3 2
1
2 3
1
3 4
1
1 4
0
0
0

result:

ok 27 cases passed. max #moves/#balls = 1.500000000

Test #4:

score: 0
Accepted
time: 3ms
memory: 3384kb

input:

3 6
1 1
1 2
1 2
1 3
1 3
1 1
3 7
1 3
0
1 2
1 2
1 1
1 1
1 3
3 8
0
1 3
1 2
0
1 1
1 1
1 2
1 3
3 6
1 3
1 3
1 2
1 1
1 1
1 2
3 7
1 1
1 3
1 1
1 2
1 2
1 3
0
3 8
1 1
1 2
0
1 3
1 2
0
1 3
1 1
3 6
1 3
1 1
1 2
1 3
1 2
1 1
3 7
1 1
1 2
0
1 1
1 3
1 3
1 2
3 8
1 2
1 1
1 3
1 2
0
1 3
0
1 1
3 6
1 2
1 2
1 3
1 1
1 1
1 3
3 ...

output:

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

result:

ok 180 cases passed. max #moves/#balls = 1.333333333

Test #5:

score: 0
Accepted
time: 3ms
memory: 3476kb

input:

4 8
1 3
1 3
1 4
1 1
1 2
1 1
1 4
1 2
4 9
1 3
0
1 2
1 1
1 4
1 1
1 4
1 2
1 3
4 10
1 1
1 3
1 3
1 2
1 2
0
1 1
1 4
1 4
0
4 8
1 4
1 3
1 2
1 2
1 1
1 4
1 1
1 3
4 9
1 4
1 3
1 1
1 3
1 4
1 2
1 1
1 2
0
4 10
1 4
1 1
1 2
1 3
0
0
1 2
1 1
1 3
1 4
4 8
1 2
1 4
1 3
1 4
1 2
1 3
1 1
1 1
4 9
1 1
1 4
1 3
1 2
1 3
1 2
0
1 4
...

output:

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

result:

ok 1575 cases passed. max #moves/#balls = 1.500000000

Test #6:

score: 0
Accepted
time: 49ms
memory: 3548kb

input:

5 10
1 1
1 4
1 2
1 4
1 5
1 2
1 3
1 5
1 1
1 3
5 11
1 1
1 3
1 1
1 2
1 5
1 2
0
1 5
1 4
1 3
1 4
5 12
1 2
0
1 1
1 5
1 2
1 4
1 3
1 4
0
1 5
1 3
1 1
5 10
1 3
1 5
1 1
1 1
1 2
1 4
1 4
1 5
1 2
1 3
5 11
1 3
1 5
1 2
1 2
1 4
1 3
1 1
1 1
0
1 4
1 5
5 12
1 3
1 4
1 2
0
1 5
1 1
1 2
1 1
1 4
1 5
0
1 3
5 10
1 4
1 5
1 3
1...

output:

5
2 4
3 6
5 8
1 9
7 10
5
1 3
4 6
5 8
2 10
9 11
5
1 5
6 8
4 10
7 11
3 12
5
3 4
6 7
2 8
5 9
1 10
5
3 4
1 6
7 8
5 10
2 11
5
3 7
6 8
2 9
5 10
1 12
5
1 5
2 6
4 7
8 9
3 10
5
2 4
1 6
5 7
8 9
3 11
5
2 3
4 5
1 7
8 9
10 11
5
1 3
4 5
6 7
2 9
8 10
5
2 3
4 5
6 7
8 9
1 11
5
2 6
1 7
8 9
3 10
4 11
5
4 5
2 6
7 8
3 9...

result:

ok 17010 cases passed. max #moves/#balls = 1.400000000

Test #7:

score: 0
Accepted
time: 43ms
memory: 3548kb

input:

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

output:

6
1 6
4 7
2 9
5 11
10 8
3 10
5
5 4
1 5
7 6
9 6
7 9
-1
8
3 7
5 6
8 6
2 8
5 2
1 3
4 1
3 4
7
1 8
4 9
5 1
7 1
3 5
6 7
2 6
5
2 7
4 1
5 2
3 5
4 3
5
6 3
7 1
2 6
8 7
2 8
5
2 6
5 7
1 9
3 10
8 11
6
1 6
5 1
3 8
4 8
2 4
3 2
-1
6
2 3
6 8
4 9
5 10
1 11
7 12
3
7 6
5 7
3 5
8
1 2
7 2
9 1
4 7
3 4
5 6
8 6
5 8
6
1 3
4 ...

result:

ok 14285 cases passed. max #moves/#balls = 1.500000000

Test #8:

score: 0
Accepted
time: 49ms
memory: 3472kb

input:

7 10
2 4 3
1 1
2 2 2
2 4 3
2 7 7
2 6 6
2 5 5
0
1 1
0
7 12
1 2
1 6
1 6
1 5
2 4 1
1 1
2 4 3
1 7
1 5
1 3
1 2
1 7
7 15
1 4
1 6
1 2
1 4
1 6
1 5
1 7
1 1
1 3
0
1 7
1 5
1 1
1 3
1 2
7 7
2 7 3
2 2 3
2 5 7
2 1 1
2 6 6
2 2 5
2 4 4
7 12
2 3 2
1 7
2 6 3
1 4
1 2
1 5
1 1
1 4
1 5
1 1
1 6
1 7
7 14
2 3 5
0
1 2
1 6
1 4...

output:

4
2 9
1 8
4 8
1 4
7
2 3
4 9
1 11
8 12
5 6
7 10
5 7
7
1 4
2 5
7 11
6 12
8 13
9 14
3 15
-1
7
4 8
6 9
7 10
2 12
1 5
3 1
11 3
7
5 8
9 11
4 12
10 13
3 14
1 7
6 1
7
1 6
3 2
10 2
7 3
8 10
4 8
7 4
7
1 4
8 9
7 10
5 12
2 11
6 2
3 6
7
4 6
2 10
5 11
3 1
7 1
5 3
9 7
7
2 7
5 9
4 1
6 4
8 2
10 2
8 10
7
4 5
3 8
2 9
...

result:

ok 12500 cases passed. max #moves/#balls = 1.428571429

Test #9:

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

input:

8 16
1 2
0
1 5
1 8
1 1
1 5
2 4 4
1 8
1 6
1 1
1 2
0
2 7 7
1 3
1 6
1 3
8 13
1 8
1 4
1 2
1 6
2 1 3
2 1 3
1 7
1 2
1 5
1 6
1 8
2 4 5
1 7
8 9
2 1 3
2 4 5
2 7 2
2 7 8
2 4 8
2 1 6
2 5 2
2 6 3
0
8 17
1 1
1 4
1 3
1 7
1 2
1 2
1 7
1 5
1 3
1 4
1 6
1 8
1 5
1 6
1 8
1 1
0
8 15
1 6
1 4
0
1 5
1 7
1 3
1 2
1 8
1 6
1 7
...

output:

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

result:

ok 11111 cases passed. max #moves/#balls = 1.500000000

Test #10:

score: 0
Accepted
time: 49ms
memory: 3520kb

input:

9 13
1 2
2 4 5
2 5 4
2 2 9
1 8
1 3
1 1
1 3
1 1
2 7 6
1 9
1 8
2 7 6
9 13
1 4
2 5 6
2 7 5
2 9 3
1 4
2 9 7
0
2 8 6
2 1 3
0
1 2
1 2
2 8 1
9 18
1 4
1 7
1 7
1 9
1 8
1 8
1 2
1 3
1 6
1 2
1 1
1 3
1 5
1 1
1 6
1 5
1 4
1 9
9 13
0
2 6 7
2 2 2
1 3
2 6 8
2 9 1
2 1 4
1 9
2 8 7
0
1 4
1 3
2 5 5
9 17
1 9
2 1 3
1 2
1 5...

output:

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

result:

ok 10000 cases passed. max #moves/#balls = 1.444444444

Test #11:

score: 0
Accepted
time: 49ms
memory: 3380kb

input:

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

output:

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

result:

ok 9090 cases passed. max #moves/#balls = 1.500000000

Test #12:

score: 0
Accepted
time: 49ms
memory: 3544kb

input:

11 15
2 11 11
2 3 3
1 2
0
2 8 5
1 2
2 6 4
2 4 5
1 1
1 1
1 9
1 10
2 8 6
2 7 7
2 9 10
11 17
2 4 8
1 11
2 6 7
1 9
1 9
1 5
1 2
1 2
1 5
1 10
1 3
1 1
1 11
2 10 8
1 1
2 3 7
2 4 6
11 21
1 10
1 6
1 3
1 9
1 8
1 1
1 5
1 10
1 5
1 4
1 8
1 9
1 11
1 6
1 11
1 7
1 1
1 4
2 2 2
1 7
1 3
11 15
1 5
1 1
1 2
2 3 3
2 10 7
0...

output:

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

result:

ok 8333 cases passed. max #moves/#balls = 1.363636364

Test #13:

score: 0
Accepted
time: 49ms
memory: 3388kb

input:

12 25
1 9
1 10
1 4
1 7
1 5
1 3
1 6
1 1
1 12
1 3
1 2
1 9
1 11
1 2
0
1 10
1 7
1 12
1 11
1 4
1 6
1 5
1 1
1 8
1 8
12 19
1 2
1 12
2 8 8
2 1 3
0
2 3 4
1 5
2 11 11
2 1 5
2 9 6
1 12
1 7
1 7
2 6 9
1 2
1 4
1 10
1 10
0
12 14
2 2 4
2 8 8
2 1 3
2 9 9
2 6 12
2 6 1
0
2 10 10
2 5 5
2 3 12
0
2 4 7
2 7 2
2 11 11
12 1...

output:

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

result:

ok 7692 cases passed. max #moves/#balls = 1.416666667

Test #14:

score: 0
Accepted
time: 49ms
memory: 3468kb

input:

13 15
2 8 8
2 6 6
2 1 1
2 3 3
2 11 11
2 2 5
2 5 13
1 4
1 12
2 2 13
1 12
2 10 10
1 4
2 9 9
2 7 7
13 21
2 11 11
1 9
1 2
1 9
1 13
1 1
1 13
1 5
2 12 8
2 7 7
1 5
1 6
1 6
2 4 3
1 1
0
2 10 10
1 2
2 4 3
0
2 8 12
13 24
1 8
1 7
1 6
1 3
1 5
1 9
1 2
1 13
1 2
1 12
2 10 10
1 3
1 1
1 8
1 4
1 12
1 6
1 5
1 7
1 4
2 1...

output:

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

result:

ok 7142 cases passed. max #moves/#balls = 1.384615385

Test #15:

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

input:

14 24
1 3
1 11
1 2
1 7
1 5
0
1 11
2 4 8
2 12 5
2 9 4
1 3
1 10
2 12 9
1 1
0
2 13 13
1 2
1 7
1 6
1 10
1 14
1 1
1 6
2 8 14
14 27
1 8
1 10
1 1
1 1
1 12
1 14
1 6
1 11
1 5
1 12
1 7
1 4
1 10
1 14
1 7
1 9
1 2
1 6
1 11
1 9
2 3 3
1 2
1 4
1 13
1 8
1 5
1 13
14 22
1 14
2 7 5
1 3
1 10
1 9
1 9
2 13 5
2 12 2
2 6 6
...

output:

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

result:

ok 6666 cases passed. max #moves/#balls = 1.357142857

Test #16:

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

input:

15 22
0
2 6 13
1 13
1 4
1 8
1 8
0
2 10 3
2 11 15
2 15 7
1 5
2 2 12
2 11 12
1 6
1 7
2 9 9
1 5
2 1 1
2 3 10
2 14 14
1 4
1 2
15 24
1 2
1 4
2 8 11
1 9
0
1 1
2 5 5
1 9
2 6 6
1 12
1 3
1 3
2 7 13
2 11 10
1 14
1 12
2 10 4
1 15
2 8 7
1 2
0
1 1
1 15
2 13 14
15 24
0
1 14
1 14
2 1 1
1 10
1 12
1 5
2 10 6
1 13
1 ...

output:

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

result:

ok 6250 cases passed. max #moves/#balls = 1.400000000

Test #17:

score: 0
Accepted
time: 40ms
memory: 3520kb

input:

16 23
1 3
1 9
0
1 9
1 14
1 4
2 5 14
1 10
2 16 5
2 6 6
2 1 1
2 16 11
2 12 12
1 2
1 4
0
2 8 8
2 11 13
1 7
1 10
2 2 15
2 3 15
2 7 13
16 29
0
1 6
1 3
1 7
1 14
1 12
1 9
1 3
1 10
1 14
1 13
1 2
2 6 9
1 4
1 2
2 5 1
1 8
1 16
1 4
2 1 5
1 11
1 7
2 8 10
1 15
1 12
1 11
1 15
1 16
1 13
16 28
1 13
1 8
1 9
1 12
2 15...

output:

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

result:

ok 5882 cases passed. max #moves/#balls = 1.375000000

Test #18:

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

input:

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

output:

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

result:

ok 5555 cases passed. max #moves/#balls = 1.352941176

Test #19:

score: 0
Accepted
time: 21ms
memory: 3512kb

input:

18 19
2 8 5
2 7 11
2 1 13
2 2 2
0
2 17 11
2 14 6
2 18 18
2 3 12
2 4 3
2 8 12
2 6 14
2 9 16
2 13 1
2 15 15
2 9 16
2 10 10
2 5 4
2 7 17
18 26
2 16 4
2 10 15
1 7
1 13
1 11
1 11
2 15 10
1 14
1 5
1 8
2 9 3
2 2 9
2 4 12
1 13
1 1
1 1
1 17
1 5
2 16 6
1 7
1 8
2 12 6
1 17
2 18 3
1 14
2 2 18
18 23
2 16 16
2 18...

output:

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

result:

ok 5263 cases passed. max #moves/#balls = 1.388888889

Test #20:

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

input:

19 25
2 8 13
0
1 16
1 5
2 18 13
2 4 7
0
2 17 1
2 12 16
2 12 4
2 19 15
2 1 8
1 3
1 7
2 6 2
2 2 9
2 18 14
1 11
2 10 10
2 15 17
2 6 14
1 5
2 9 19
1 11
1 3
19 34
1 12
1 16
1 16
1 7
1 6
2 4 4
1 8
1 18
2 9 19
1 11
1 13
1 14
1 7
1 6
1 3
1 14
2 9 5
1 11
1 15
1 1
1 3
2 19 1
1 17
1 17
1 13
1 2
1 12
1 8
1 15
1...

output:

20
4 22
18 24
13 25
6 14
9 3
10 6
9 10
1 2
5 2
12 1
8 12
20 8
11 20
23 11
16 23
15 16
17 7
21 7
5 17
15 21
18
2 3
4 13
5 14
12 16
10 18
15 21
23 24
11 25
1 27
7 28
19 29
8 31
26 32
30 34
22 20
17 33
9 22
17 9
-1
21
5 7
2 9
14 19
18 21
17 23
24 25
11 27
1 3
4 3
15 1
20 4
6 5
8 5
15 6
20 8
13 2
22 2
1...

result:

ok 5000 cases passed. max #moves/#balls = 1.368421053

Test #21:

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

input:

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

output:

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

result:

ok 4761 cases passed. max #moves/#balls = 1.300000000

Test #22:

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

input:

70 79
2 13 14
2 49 46
1 43
2 27 27
2 5 5
2 63 50
2 63 15
2 61 25
2 17 39
2 44 26
2 15 45
2 65 2
2 64 6
2 2 28
2 55 60
2 13 68
1 40
2 30 30
1 62
2 41 60
2 16 25
1 69
1 62
2 28 23
2 46 49
2 26 57
1 35
2 66 66
2 10 69
2 33 55
1 10
2 54 9
1 32
2 11 12
1 40
1 7
1 29
2 33 54
2 12 11
2 22 1
1 29
2 6 64
2 2...

output:

79
19 23
17 35
37 41
36 45
3 47
44 50
27 62
33 75
29 22
31 29
40 19
52 19
63 40
9 63
26 17
60 17
52 60
10 26
72 10
9 72
32 37
61 37
38 32
78 61
15 36
20 36
30 15
38 30
68 3
79 3
20 68
78 79
1 44
65 44
16 65
1 16
8 27
21 27
69 8
55 33
67 33
69 55
54 67
21 54
11 31
74 31
7 11
76 74
51 76
48 51
56 48
6...

result:

ok 1000 cases passed. max #moves/#balls = 1.500000000

Test #23:

score: 0
Accepted
time: 19ms
memory: 3756kb

input:

89 125
2 6 86
1 11
1 43
1 77
1 27
2 72 88
1 52
2 26 75
1 77
2 89 86
1 60
1 18
2 20 20
1 25
2 57 75
1 3
1 55
2 38 19
2 76 2
2 22 24
1 3
2 61 61
2 39 59
2 42 74
1 56
2 71 71
1 68
2 79 87
2 81 67
1 25
2 66 21
1 37
1 70
2 40 83
1 60
1 48
1 52
2 22 24
2 62 62
1 84
2 41 23
1 69
2 32 26
1 36
1 15
2 88 72
1...

output:

88
4 9
16 21
14 30
11 35
7 37
5 47
42 52
40 64
3 75
62 76
51 78
44 87
79 88
25 90
85 91
48 92
54 93
36 94
59 96
61 98
2 105
57 107
12 108
95 109
56 112
110 113
45 114
33 115
73 116
32 117
82 118
83 119
27 122
17 123
63 106
19 81
67 81
70 19
63 70
34 67
77 34
49 4
102 4
80 102
49 80
55 16
60 16
58 55...

result:

ok 100 cases passed. max #moves/#balls = 1.169811321

Test #24:

score: 0
Accepted
time: 189ms
memory: 37944kb

input:

199990 199994
2 112787 58235
2 74630 28941
2 167642 28933
2 133872 119903
2 134119 187247
2 12074 126849
2 172463 191232
2 69306 129651
2 85342 121061
2 31874 148765
2 6567 39825
2 70847 178127
2 161417 173942
2 60884 49005
2 10700 112396
2 134185 131889
2 62930 176558
2 153356 48329
2 88968 136672
...

output:

249866
47930 39403
45681 123950
52624 103430
29499 45681
33532 199993
149868 199993
55718 149868
174021 55718
82791 199994
120612 199994
8600 82791
45526 120612
47930 45526
73469 8600
121113 73469
140740 174021
199529 174021
166239 140740
131387 166239
52624 131387
72220 47930
127457 47930
71505 722...

result:

ok 1 cases passed. max #moves/#balls = 1.249392470

Test #25:

score: 0
Accepted
time: 346ms
memory: 37884kb

input:

199900 199939
2 159852 65847
2 26090 50275
2 87513 124862
2 86896 171149
2 108960 21092
2 60944 176432
2 64408 168417
2 110938 48609
2 30886 178149
2 180183 52005
2 185615 173446
2 91034 36919
2 121714 75547
2 97679 89549
2 161524 190571
2 129781 26065
2 726 162459
2 28052 166745
2 193665 65435
2 45...

output:

249613
106581 195508
87499 466
141785 86599
193462 112079
111161 180271
70518 20388
177189 95960
51089 145236
42342 50137
130367 94233
13675 161933
167502 5649
83100 170999
1669 70219
141132 188272
118999 98362
45466 80993
36392 181613
184780 156194
113064 98870
73883 46654
111332 77134
149863 85671...

result:

ok 1 cases passed. max #moves/#balls = 1.248689345

Test #26:

score: 0
Accepted
time: 182ms
memory: 37944kb

input:

199000 199158
2 87128 180318
2 51427 22755
2 151883 144846
2 86404 42933
2 86031 56171
2 97601 190366
2 100929 91717
2 10606 53797
2 151688 90226
2 65599 83910
2 159670 153323
2 98395 126956
2 104190 188119
2 134860 5110
2 82527 59574
2 185228 58544
2 131591 9348
2 88390 99580
2 79913 120984
2 12854...

output:

248620
159826 170232
824 116779
65806 96668
64102 145895
184853 35084
41063 63660
96981 145392
110701 113358
103047 42388
108644 192770
110485 176389
5748 32464
28323 198599
143694 167502
3800 40526
57803 183718
162603 5916
126242 67012
181408 90168
33958 113178
96959 160229
144623 64830
59284 11561...

result:

ok 1 cases passed. max #moves/#balls = 1.249346734

Test #27:

score: 0
Accepted
time: 184ms
memory: 36308kb

input:

190000 195490
2 57925 137657
2 115225 31941
2 113825 126389
2 86640 44883
2 54487 34585
2 118366 61471
2 120619 96922
1 140665
2 42131 138488
2 115971 83797
2 79814 139047
2 182772 4122
2 134485 135722
2 83056 53620
2 4840 71513
2 58767 175090
2 55378 47553
2 158331 65564
2 2231 167672
2 45248 44008...

output:

234894
4755 6118
8647 16180
11096 19603
18134 34806
20357 36247
4023 39925
11730 44145
39650 45518
11276 45822
36329 49544
47179 50373
45199 54669
54857 57867
7693 59170
18426 64265
41297 67516
27162 68702
19476 72813
60375 78081
30688 82920
53409 84342
36263 85676
14958 86387
13697 86705
66312 8826...

result:

ok 1 cases passed. max #moves/#balls = 1.236284211

Test #28:

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

input:

100000 150784
1 11363
2 48695 10015
1 45261
0
0
2 59469 34868
2 37754 54971
2 1159 2258
2 36656 7427
1 86418
0
2 58664 20429
1 53392
1 61881
2 17499 14399
1 31182
1 7141
0
2 58765 17577
1 21750
2 55759 24096
0
0
2 68221 45178
1 34307
1 952
0
1 37862
1 31349
2 79909 53730
2 61993 40470
0
1 8272
2 824...

output:

111036
129 349
727 3146
2765 3363
1798 4115
3386 4951
3394 4973
1878 5051
3035 5139
2944 5675
2640 6032
3238 6151
1069 6205
3694 6284
4606 6285
5287 6311
4936 6453
3977 6559
1512 6659
1012 6717
7475 7765
3720 7984
373 8026
7385 8048
5214 8108
6455 8170
1533 8365
2232 8426
5402 8473
4151 8608
1335 87...

result:

ok 1 cases passed. max #moves/#balls = 1.110360000

Test #29:

score: 0
Accepted
time: 177ms
memory: 37852kb

input:

199998 200000
2 197320 165241
2 136684 67821
2 38136 196111
2 36675 168634
2 193814 85383
2 188893 178378
2 107377 34791
2 77322 157440
2 51337 91683
2 141729 123337
2 88834 166216
2 172041 99918
2 81678 190214
2 145905 79139
2 184733 143722
2 20662 175460
2 73374 152647
2 111949 12058
2 7347 64349
...

output:

250095
171410 199999
181365 199999
97712 171410
52612 97712
119503 52612
138016 119503
28740 138016
129434 200000
141131 200000
181365 129434
88862 141131
21514 181365
91173 181365
169576 21514
77064 91173
36185 169576
8836 36185
74434 8836
28740 74434
70173 28740
113999 28740
88862 113999
96199 701...

result:

ok 1 cases passed. max #moves/#balls = 1.250487505