QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#553882	#8431. Game on Bipartite Graph	ucup-team1005	AC ✓	7ms	3708kb	C++20	1.9kb	2024-09-08 21:55:51	2024-09-08 21:55:51

Due to the privacy settings of the submitter, you are not allowed to view this code.

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3688kb

input:

output:

2
1
2
Player 1 wins

result:

ok Player 1 wins

Test #2:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

output:

1
Player 1 wins

result:

ok Player 1 wins

Test #3:

score: 0

Accepted

time: 1ms

memory: 3608kb

input:

output:

1
2
Player 2 wins

result:

ok Player 2 wins

Test #4:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

output:

1
5
3
4
5
Player 2 wins

result:

ok Player 2 wins

Test #5:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

output:

1
1
1
1
2
2
3
3
4
4
5
5
6
7
Player 2 wins

result:

ok Player 2 wins

Test #6:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

output:

2
Player 1 wins

result:

ok Player 1 wins

Test #7:

score: 0

Accepted

time: 3ms

memory: 3636kb

input:

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

output:

result:

ok Player 1 wins

Test #8:

score: 0

Accepted

time: 2ms

memory: 3700kb

input:

50 50 677 43
6 20
8 25
17 19
22 27
30 50
1 16
18 6
48 28
26 15
12 38
6 11
13 4
9 24
47 38
11 27
15 3
7 17
40 32
25 38
21 7
20 23
19 44
13 25
40 21
42 10
13 34
13 8
39 13
29 43
7 4
22 47
50 45
10 1
43 5
44 11
46 40
24 44
27 9
26 18
24 34
25 49
19 39
24 36
32 6
2 25
33 35
44 6
41 37
48 32
4 4
41 5
5 3...

output:

result:

ok Player 1 wins

Test #9:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

50 50 1786 39
30 32
23 9
5 28
4 17
20 36
31 35
39 29
6 46
20 14
40 47
35 18
21 13
23 40
18 14
32 18
1 16
12 43
11 19
40 31
32 38
16 12
48 9
7 39
3 35
43 7
33 30
43 49
14 19
37 46
13 39
4 32
16 30
30 42
27 4
39 34
7 7
9 4
10 12
34 15
34 14
49 38
45 3
21 36
47 44
15 29
48 44
35 15
42 29
14 5
20 5
28 1...

output:

result:

ok Player 2 wins

Test #10:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

50 50 586 43
7 36
49 42
39 42
36 10
13 30
22 4
6 43
10 14
11 4
22 14
18 25
33 34
22 7
38 40
6 5
34 25
16 27
36 7
46 32
4 27
24 1
36 25
50 15
11 3
45 38
4 26
31 40
35 12
41 8
34 24
32 5
31 15
11 45
15 7
25 49
19 37
35 6
47 7
50 15
40 45
27 23
5 24
14 36
19 24
35 36
17 3
33 31
43 13
34 32
44 6
19 46
4...

output:

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

result:

ok Player 2 wins

Test #11:

score: 0

Accepted

time: 6ms

memory: 3552kb

input:

50 50 1946 42
39 39
22 21
31 47
19 46
11 21
5 19
23 16
18 40
14 3
3 23
2 32
50 6
33 19
8 8
26 43
20 38
20 2
11 44
3 24
19 12
29 47
11 32
28 29
28 12
39 27
32 22
16 27
6 17
45 11
47 13
10 37
38 45
39 36
41 6
11 14
27 12
19 12
30 10
4 24
42 29
42 8
27 46
14 31
38 12
48 47
28 12
19 39
37 9
1 5
18 7
6 1...

output:

result:

ok Player 1 wins

Test #12:

score: 0

Accepted

time: 1ms

memory: 3696kb

input:

50 50 2500 22
47 1
1 16
9 10
25 19
5 6
1 24
16 23
38 29
40 28
25 28
29 32
2 49
34 6
6 24
43 32
33 25
21 19
18 8
46 16
28 26
34 17
1 11
6 46
12 30
44 3
5 20
50 39
37 42
38 7
8 13
36 6
42 18
26 45
38 16
15 45
12 31
26 19
12 19
27 50
13 30
44 17
36 7
16 41
16 42
3 25
37 45
11 22
38 30
27 43
20 5
21 27
...

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Player 2 wins

result:

ok Player 2 wins

Test #13:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

output:

1
2
2
3
1
1
1
2
17
4
5
13
6
1
1
1
1
Player 1 wins

result:

ok Player 1 wins

Test #14:

score: 0

Accepted

time: 1ms

memory: 3564kb

input:

12 47 319 10
6 25
8 42
7 39
9 12
5 44
2 46
11 5
1 40
2 21
8 41
7 40
9 11
7 41
7 6
11 40
5 33
5 43
4 41
6 22
9 37
4 46
5 32
2 44
2 35
2 36
11 3
8 24
3 20
6 18
10 1
8 17
9 2
7 30
12 15
11 3
8 32
2 33
6 47
2 2
4 31
1 37
9 26
7 14
5 16
12 46
8 7
2 15
12 29
8 7
4 31
1 32
12 20
4 32
6 42
8 16
1 45
10 1
4 ...

output:

1
1
6
3
5
2
7
2
2
6
2
8
9
4
Player 1 wins

result:

ok Player 1 wins

Test #15:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

output:

1
1
2
3
3
2
3
4
5
4
1
5
7
7
1
1
3
Player 1 wins

result:

ok Player 1 wins

Test #16:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

10 39 334 9
2 26
1 19
10 4
8 10
8 9
1 17
6 32
8 34
5 11
2 20
9 27
6 1
2 8
10 3
4 38
8 8
6 2
8 1
6 38
1 37
2 9
10 35
4 12
8 36
1 4
8 24
2 30
2 34
9 13
3 8
1 12
9 9
9 9
6 3
9 16
6 10
8 25
4 18
10 38
6 17
8 9
8 33
1 2
8 20
1 20
8 12
8 16
9 20
6 3
10 31
3 20
1 34
5 22
2 11
9 5
9 3
3 16
1 4
1 13
3 9
6 38...

output:

1
3
2
1
3
4
4
4
6
3
4
4
2
1
1
Player 1 wins

result:

ok Player 1 wins

Test #17:

score: 0

Accepted

time: 2ms

memory: 3536kb

input:

19 50 869 15
13 27
14 19
1 47
10 3
13 49
12 28
10 35
11 50
17 6
15 27
12 27
17 19
19 31
17 27
7 42
3 32
17 27
11 34
10 19
13 25
17 24
10 21
10 17
6 50
14 27
1 27
7 37
17 28
13 50
4 47
15 28
17 8
17 27
11 18
1 8
13 21
11 39
7 27
7 13
18 35
13 32
11 25
11 39
10 18
18 28
17 18
10 43
17 35
17 46
17 16
1...

output:

3
2
2
3
6
8
13
14
8
18
15
8
9
3
2
3
4
6
8
8
8
4
6
6
6
6
6
6
6
2
21
16
18
19
19
19
21
21
25
27
28
28
29
8
8
8
11
10
10
8
8
10
3
4
3
6
8
8
6
3
6
6
6
8
10
8
11
11
13
16
18
19
19
21
17
21
25
25
13
13
16
16
12
11
12
11
13
13
13
16
15
15
13
13
13
13
13
3
4
2
Player 1 wins

result:

ok Player 1 wins

Test #18:

score: 0

Accepted

time: 1ms

memory: 3612kb

input:

output:

1
1
2
5
6
Player 1 wins

result:

ok Player 1 wins

Test #19:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

output:

1
Player 1 wins

result:

ok Player 1 wins

Test #20:

score: 0

Accepted

time: 1ms

memory: 3604kb

input:

20 44 755 18
12 31
7 1
16 44
6 16
6 6
17 43
15 40
15 30
20 37
16 20
18 16
15 36
7 36
7 19
12 15
7 29
15 25
16 40
7 40
10 8
4 32
18 3
19 35
7 10
12 32
3 35
2 16
20 5
7 35
5 34
2 16
8 36
14 40
17 37
20 2
14 29
1 7
15 9
16 36
16 15
10 10
18 37
19 10
2 43
2 36
15 8
7 3
12 9
19 37
12 19
7 8
6 27
16 33
20...

output:

2
2
1
2
2
3
3
7
4
3
3
3
3
3
3
1
3
2
7
6
8
8
9
5
5
7
8
10
10
11
12
26
29
30
7
6
6
7
8
8
9
9
10
29
12
14
11
10
16
15
15
10
10
11
8
8
7
8
5
6
6
3
2
1
3
3
8
8
9
9
9
10
10
10
9
10
11
14
12
14
14
10
9
10
5
2
1
Player 1 wins

result:

ok Player 1 wins

Test #21:

score: 0

Accepted

time: 1ms

memory: 3608kb

input:

output:

2
3
4
1
3
1
1
1
3
Player 1 wins

result:

ok Player 1 wins

Test #22:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

12 36 102 1
10 29
1 28
6 4
10 29
3 29
5 15
3 6
7 13
3 14
7 28
7 23
1 34
3 6
1 7
10 4
1 14
7 29
1 30
7 23
5 10
3 26
3 14
7 12
7 29
3 18
1 29
3 23
8 31
8 29
1 24
12 20
5 3
12 24
12 3
3 14
9 31
7 3
11 3
6 13
7 14
9 4
12 12
1 27
8 3
5 3
6 29
10 2
3 24
10 28
3 34
5 28
3 36
7 31
7 26
3 3
12 3
8 31
7 28
3 ...

output:

7
Player 1 wins

result:

ok Player 1 wins

Test #23:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

27 45 727 22
6 29
7 35
25 4
4 2
13 30
13 35
7 3
1 2
21 5
18 9
18 21
18 25
4 6
18 14
15 21
18 36
13 33
18 21
27 10
6 42
13 29
7 5
12 2
6 4
12 4
26 4
20 4
25 32
2 2
11 35
4 21
14 13
12 29
25 13
7 8
18 21
14 29
7 36
15 22
4 4
18 19
18 25
7 35
7 41
12 37
14 25
9 21
15 43
18 10
27 35
7 43
14 4
26 29
18 1...

output:

3
4
1
4
3
3
3
1
1
4
5
7
6
6
4
4
13
9
10
9
9
5
5
5
6
7
7
10
19
13
11
1
1
1
1
4
3
19
21
13
13
8
13
9
9
3
4
4
3
1
1
3
4
4
5
5
5
6
6
6
6
7
7
5
6
5
4
4
5
6
3
1
7
6
7
1
3
1
3
3
1
1
1
4
4
5
5
10
10
10
10
19
14
14
13
14
21
17
25
24
19
9
9
9
9
9
9
10
10
10
10
10
13
13
13
9
9
9
9
9
10
10
8
5
6
4
8
Player 1 wins

result:

ok Player 1 wins

Test #24:

score: 0

Accepted

time: 1ms

memory: 3572kb

input:

49 49 944 24
18 7
1 17
48 30
31 42
20 7
34 34
20 42
7 13
45 22
20 40
44 44
48 34
22 2
14 9
13 17
16 21
2 10
11 9
16 5
48 16
21 44
20 26
16 19
11 2
18 17
31 5
6 10
28 21
34 7
6 9
22 9
13 2
13 9
4 20
6 13
48 26
48 44
34 16
3 22
6 44
31 1
7 13
31 25
7 12
48 41
13 13
21 28
33 9
47 1
24 39
11 39
18 23
11...

output:

9
2
2
5
5
5
2
1
1
1
1
9
7
10
10
14
2
2
2
7
9
5
9
9
12
13
12
17
17
19
10
26
22
10
22
24
10
20
20
13
13
13
13
20
16
7
7
2
1
1
2
5
7
8
2
2
2
1
5
5
7
7
9
9
10
10
10
10
13
10
16
17
26
37
Player 1 wins

result:

ok Player 1 wins

Test #25:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

33 18 14 33
31 4
33 4
11 6
29 18
30 17
33 11
9 17
17 4
3 15
17 12
23 17
3 4
4 12
19 7

output:

11
Player 1 wins

result:

ok Player 1 wins

Test #26:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

12 1 1 2
2 1

output:

1
Player 1 wins

result:

ok Player 1 wins

Test #27:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

49 45 439 11
49 20
28 7
31 43
24 24
11 36
6 28
44 4
37 29
29 11
13 12
2 14
12 12
40 3
8 13
28 20
22 30
5 24
33 16
2 30
45 24
6 20
24 27
2 4
37 7
32 25
45 26
36 29
29 38
35 44
28 34
45 45
11 20
44 45
46 16
28 36
12 29
13 32
29 36
11 10
5 4
41 33
46 40
1 7
18 24
23 36
2 29
23 39
12 11
8 26
16 31
27 20...

output:

4
5
6
10
8
6
13
14
14
24
16
6
11
13
24
22
6
45
17
5
8
31
20
15
13
9
25
2
3
26
19
Player 1 wins

result:

ok Player 1 wins

Test #28:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

11 2 1 8
8 1

output:

1
Player 1 wins

result:

ok Player 1 wins

Test #29:

score: 0

Accepted

time: 1ms

memory: 3600kb

input:

output:

10
10
5
7
4
Player 1 wins

result:

ok Player 1 wins

Test #30:

score: 0

Accepted

time: 6ms

memory: 3568kb

input:

50 50 2420 10
27 2
48 21
22 1
46 40
45 37
17 48
33 16
28 38
11 49
9 13
16 37
10 11
32 1
38 50
24 5
48 20
44 45
29 9
22 22
35 50
37 34
12 35
30 12
41 21
13 11
17 1
10 15
11 9
23 1
33 14
28 15
48 47
14 46
28 50
48 47
17 21
43 21
31 47
13 25
12 25
24 9
49 24
35 25
7 16
11 48
25 40
48 16
14 29
21 20
26 ...

output:

result:

ok Player 1 wins

Test #31:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

2
3
4
3
2
4
2
2
4
5
5
3
5
Player 1 wins

result:

ok Player 1 wins

Test #32:

score: 0

Accepted

time: 1ms

memory: 3544kb

input:

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

output:

20
Player 1 wins

result:

ok Player 1 wins

Test #33:

score: 0

Accepted

time: 1ms

memory: 3636kb

input:

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

output:

9
7
1
8
8
8
8
8
10
18
21
2
2
3
3
5
5
2
3
15
3
3
3
2
2
1
2
3
5
5
5
3
2
2
3
3
2
2
2
3
5
5
8
8
9
10
9
12
13
14
7
8
9
7
7
5
8
8
5
8
8
9
7
12
12
13
16
16
16
18
17
17
16
18
16
16
16
12
10
10
12
13
7
5
8
8
16
16
16
16
17
17
17
17
18
18
18
18
28
17
17
10
5
7
5
5
8
2
28
10
2
2
2
10
2
5
5
5
2
Player 1 wins

result:

ok Player 1 wins

Test #34:

score: 0

Accepted

time: 1ms

memory: 3564kb

input:

37 22 51 15
24 7
26 8
8 8
16 2
23 5
25 12
36 8
15 15
19 18
8 18
26 22
35 18
18 10
4 3
29 8
19 8
8 22
22 13
14 18
23 18
10 6
22 18
24 13
23 8
8 8
35 20
19 10
10 18
26 5
6 22
15 8
21 2
6 17
25 22
23 7
9 6
6 10
14 13
18 6
19 6
37 6
14 8
14 5
14 5
22 22
37 13
8 1
6 8
8 3
11 5
20 8

output:

15
Player 1 wins

result:

ok Player 1 wins

Test #35:

score: 0

Accepted

time: 1ms

memory: 3600kb

input:

output:

3
Player 1 wins

result:

ok Player 1 wins

Test #36:

score: 0

Accepted

time: 1ms

memory: 3568kb

input:

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

output:

9
19
9
11
14
32
23
23
4
9
25
9
8
3
3
3
20
20
11
14
29
3
2
16
16
22
17
2
10
2
9
16
2
3
3
11
20
14
20
11
2
2
2
6
3
3
3
4
4
3
4
4
3
3
3
4
9
11
17
25
9
8
9
25
3
3
9
10
10
10
9
9
9
3
3
3
9
10
2
25
2
3
2
Player 1 wins

result:

ok Player 1 wins

Test #37:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

38 31 78 33
17 18
19 10
38 11
26 13
36 2
26 4
8 20
17 7
28 4
21 23
13 26
32 6
19 25
7 19
29 2
14 16
28 28
21 23
38 16
35 31
24 11
22 19
20 18
28 23
21 16
19 5
28 5
5 17
2 20
5 16
29 23
13 10
17 27
17 18
7 16
21 17
5 20
13 14
25 4
27 16
33 14
13 30
19 19
21 23
28 20
16 22
28 20
33 6
13 14
32 4
8 9
25...

output:

6
4
1
Player 1 wins

result:

ok Player 1 wins

Test #38:

score: 0

Accepted

time: 2ms

memory: 3608kb

input:

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

output:

2
7
3
3
3
9
5
5
16
8
11
11
16
5
5
5
8
2
7
7
8
9
9
7
8
8
8
8
9
11
3
3
11
11
11
11
16
16
16
9
9
2
3
7
22
26
15
17
18
11
11
12
4
8
5
11
11
11
11
14
16
16
19
19
5
9
3
3
3
3
15
11
11
5
8
8
11
2
2
2
3
3
8
5
7
16
16
16
16
17
18
4
Player 1 wins

result:

ok Player 1 wins

Test #39:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

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

output:

18
18
10
Player 1 wins

result:

ok Player 1 wins

Test #40:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

40 39 1169 26
29 15
16 36
3 9
20 5
11 7
27 27
29 15
14 22
15 19
15 8
33 9
33 11
12 7
28 23
7 6
7 23
29 16
7 22
40 7
15 5
26 8
40 28
26 14
19 16
27 26
21 26
24 5
8 6
40 6
29 19
3 36
29 18
15 15
11 16
23 5
27 14
12 7
31 22
6 22
6 4
33 27
3 19
24 23
8 34
12 11
24 5
16 23
21 15
12 6
29 8
29 37
12 8
21 7...

output:

result:

ok Player 1 wins

Test #41:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

49 44 1648 9
4 41
20 35
39 20
15 9
17 1
10 35
20 22
19 10
39 24
3 1
43 33
38 30
48 33
3 30
3 22
41 19
23 22
26 44
18 41
18 30
14 33
44 30
14 33
4 17
9 36
33 9
30 39
27 31
14 38
4 20
20 16
33 20
43 3
33 6
34 44
43 20
40 41
27 33
43 29
27 41
9 20
39 5
4 27
4 41
19 2
13 18
25 1
4 40
48 20
30 41
24 38
5...

output:

37
Player 1 wins

result:

ok Player 1 wins

Test #42:

score: 0

Accepted

time: 4ms

memory: 3676kb

input:

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

output:

result:

ok Player 1 wins

Test #43:

score: 0

Accepted

time: 3ms

memory: 3696kb

input:

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

output:

result:

ok Player 1 wins

Test #44:

score: 0

Accepted

time: 2ms

memory: 3620kb

input:

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

output:

result:

ok Player 1 wins

Test #45:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

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

output:

5
1
1
3
1
1
3
1
1
3
2
4
2
2
6
6
6
9
12
12
4
4
4
21
14
14
6
12
14
14
15
15
4
4
9
12
12
2
2
2
6
4
4
4
3
3
1
2
2
3
1
14
14
17
Player 1 wins

result:

ok Player 1 wins

Test #46:

score: 0

Accepted

time: 3ms

memory: 3624kb

input:

50 50 1766 44
41 45
3 11
23 9
22 1
15 49
8 19
30 22
41 32
36 31
6 14
39 2
36 17
39 14
40 16
23 47
3 12
47 22
3 35
49 17
43 19
34 50
47 3
20 32
17 45
14 10
7 23
28 23
13 30
16 21
21 6
34 29
12 12
12 12
49 11
36 14
15 17
43 9
15 38
45 15
7 7
3 6
47 44
29 15
33 29
35 35
16 42
45 35
1 44
49 35
21 14
3 2...

output:

result:

ok Player 1 wins

Test #47:

score: 0

Accepted

time: 1ms

memory: 3500kb

input:

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

output:

11
Player 1 wins

result:

ok Player 1 wins

Test #48:

score: 0

Accepted

time: 2ms

memory: 3604kb

input:

47 40 1146 8
38 14
12 24
43 24
28 14
18 15
22 9
33 11
29 6
23 30
13 40
11 6
33 13
26 13
2 40
34 10
43 2
16 1
5 1
36 30
11 15
24 15
43 26
14 34
23 2
13 1
31 1
3 15
23 10
42 11
27 33
42 1
3 5
23 32
45 28
29 40
21 32
47 5
13 21
31 1
26 28
38 39
47 13
36 15
17 10
26 39
13 4
20 13
30 14
3 38
31 23
1 28
2...

output:

2
1
5
2
28
12
14
14
15
21
1
1
1
5
5
1
2
3
2
12
12
25
22
23
16
14
15
14
14
40
28
29
2
1
5
12
5
12
12
14
16
2
5
1
14
14
15
28
22
17
15
15
15
22
28
23
28
30
30
35
35
23
27
16
16
1
2
1
5
5
1
2
2
2
5
8
Player 1 wins

result:

ok Player 1 wins

Test #49:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

48 46 1763 41
30 10
4 22
42 43
43 4
26 1
4 2
37 42
44 7
16 24
16 13
44 46
31 24
29 32
6 7
22 26
31 2
3 35
35 3
38 43
6 21
47 46
41 15
41 45
24 1
41 28
41 45
42 26
15 7
21 28
30 44
44 32
14 32
4 22
31 2
1 36
23 13
43 4
42 7
16 45
5 20
16 43
15 35
15 32
27 13
15 3
26 15
6 3
23 4
26 32
30 35
26 17
44 3...

output:

result:

ok Player 1 wins

Test #50:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

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

output:

16
17
17
Player 1 wins

result:

ok Player 1 wins

Test #51:

score: 0

Accepted

time: 4ms

memory: 3548kb

input:

47 47 1893 30
38 19
28 44
30 42
43 22
12 42
23 34
12 34
30 27
17 34
29 10
32 34
46 19
35 18
19 11
35 34
32 45
17 12
30 47
9 18
29 35
43 27
35 45
35 42
21 22
9 35
41 34
29 44
28 6
34 27
12 19
41 47
42 46
19 6
4 35
23 1
20 19
6 37
23 22
12 37
35 22
18 47
47 47
23 47
46 27
28 37
39 7
30 1
31 12
6 7
28 ...

output:

result:

ok Player 1 wins

Test #52:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

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

output:

result:

ok Player 1 wins

Test #53:

score: 0

Accepted

time: 1ms

memory: 3604kb

input:

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

output:

2
11
15
2
1
3
7
4
4
6
7
7
7
2
2
2
3
3
10
9
4
4
7
4
4
2
7
7
7
4
9
2
7
3
3
1
Player 1 wins

result:

ok Player 1 wins

Test #54:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

42 22 59 14
26 17
35 12
9 12
30 22
4 14
4 15
39 17
10 17
24 9
25 2
7 2
39 19
35 17
27 3
22 20
23 2
1 12
20 14
30 14
19 9
12 17
20 5
13 17
19 20
33 17
19 17
10 2
7 20
39 14
14 3
17 19
32 20
14 8
22 2
19 3
10 15
24 17
13 17
32 3
4 14
19 14
12 15
30 20
24 20
6 19
6 1
25 2
32 17
20 3
14 15
19 12
24 3
26...

output:

8
Player 1 wins

result:

ok Player 1 wins

Test #55:

score: 0

Accepted

time: 1ms

memory: 3600kb

input:

output:

5
Player 1 wins

result:

ok Player 1 wins

Test #56:

score: 0

Accepted

time: 1ms

memory: 3564kb

input:

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

output:

3
9
8
9
9
4
10
10
8
8
3
4
4
3
4
4
6
9
9
10
9
9
9
9
9
10
13
16
15
3
5
Player 1 wins

result:

ok Player 1 wins

Test #57:

score: 0

Accepted

time: 0ms

memory: 3604kb

input:

output:

8
21
21
Player 1 wins

result:

ok Player 1 wins

Test #58:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

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

output:

16
1
1
5
10
10
19
3
4
8
1
2
21
30
23
24
36
5
15
9
14
1
16
8
21
39
44
24
3
4
2
29
7
20
29
9
38
6
28
11
11
18
1
5
11
7
13
15
38
15
2
8
8
13
20
22
35
5
16
19
19
21
10
20
7
34
12
31
42
39
11
13
2
39
42
42
3
38
8
4
1
23
9
43
20
3
2
3
1
4
Player 1 wins

result:

ok Player 1 wins

Test #59:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

48 48 2127 42
17 6
17 45
10 22
17 20
4 38
23 45
39 38
35 12
44 8
27 17
47 41
9 31
46 10
13 39
48 38
16 19
16 38
34 10
4 13
38 34
17 14
7 16
5 45
4 18
4 45
34 8
17 38
45 10
28 27
42 3
38 40
27 18
45 20
9 40
45 18
23 45
17 26
19 40
3 6
4 40
48 6
45 8
7 47
17 36
33 46
28 27
43 20
4 26
23 3
40 10
6 12
1...

output:

result:

ok Player 1 wins

Test #60:

score: 0

Accepted

time: 0ms

memory: 3700kb

input:

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

output:

15
Player 1 wins

result:

ok Player 1 wins

Test #61:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

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

output:

8
2
3
2
5
4
4
4
2
3
3
3
3
4
4
5
5
5
5
9
12
12
12
9
11
12
15
8
12
9
8
3
2
2
4
5
4
4
3
5
12
16
10
2
3
4
3
4
4
11
1
Player 1 wins

result:

ok Player 1 wins

Test #62:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

20 11 68 10
8 3
8 10
19 10
16 2
12 8
8 11
10 2
10 8
2 3
20 2
13 8
7 7
9 8
2 10
12 1
10 7
2 9
20 3
1 3
13 3
9 3
9 11
9 5
10 6
20 8
3 8
2 3
10 10
2 6
20 10
2 3
7 3
3 10
16 8
12 2
9 2
11 8
6 10
16 10
19 8
8 11
15 10
12 5
13 5
16 11
8 10
11 2
2 3
16 6
5 3
2 8
20 8
20 3
16 2
10 4
11 8
9 7
15 8
8 11
6 6
1...

output:

4
Player 1 wins

result:

ok Player 1 wins

Test #63:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

48 45 785 42
6 8
2 29
19 15
2 23
8 4
6 24
34 24
15 41
24 25
44 25
18 22
12 39
39 26
14 28
31 9
41 17
39 7
12 6
38 8
24 45
30 3
30 22
12 4
39 8
40 18
2 30
42 29
8 39
30 30
42 29
44 28
11 4
39 19
44 30
15 7
44 42
1 37
31 17
1 7
42 29
30 10
24 43
44 13
1 31
44 4
14 18
11 22
31 25
39 15
32 28
18 7
14 27...

output:

2
3
3
5
3
3
2
3
2
2
8
15
19
25
22
1
9
23
25
18
8
16
24
16
9
8
8
6
8
8
9
10
15
10
14
12
8
2
2
8
15
29
29
36
43
36
3
9
5
Player 1 wins

result:

ok Player 1 wins

Test #64:

score: 0

Accepted

time: 1ms

memory: 3656kb

input:

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

output:

result:

ok Player 1 wins

Test #65:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

49 44 47 29
43 3
14 6
42 36
25 33
47 3
37 36
49 14
32 9
22 3
43 24
38 17
5 1
1 37
42 4
2 26
5 3
45 37
38 36
28 9
30 26
38 35
22 42
45 35
43 3
43 15
5 3
32 10
18 3
32 26
43 35
45 42
27 41
25 32
5 39
15 17
18 29
43 13
31 21
7 29
33 13
29 30
13 17
22 35
2 21
13 29
32 27
22 1

output:

30
Player 1 wins

result:

ok Player 1 wins

Test #66:

score: 0

Accepted

time: 1ms

memory: 3708kb

input:

50 40 48 48
30 29
6 36
12 18
6 22
50 3
7 14
47 29
7 26
17 20
12 14
26 23
2 3
22 36
39 39
48 36
48 1
35 39
30 18
10 28
48 25
34 4
21 2
42 2
38 18
30 40
4 26
35 6
49 14
31 37
21 38
19 17
41 28
34 39
6 2
13 1
47 1
13 3
17 35
6 30
16 1
49 3
46 39
39 1
39 8
42 4
34 39
16 17
35 38

output:

25
Player 1 wins

result:

ok Player 1 wins

Test #67:

score: 0

Accepted

time: 5ms

memory: 3640kb

input:

49 49 2379 10
46 7
5 14
47 30
24 49
9 33
25 21
37 29
47 9
4 45
37 9
7 22
39 18
49 49
35 30
4 1
24 14
8 45
41 37
47 14
6 40
17 26
7 45
8 11
5 30
8 30
7 22
38 14
47 20
45 14
7 42
3 40
34 6
38 9
46 30
44 6
34 22
49 7
29 7
47 34
23 11
41 3
34 6
7 37
44 9
36 20
34 8
28 25
5 49
24 11
41 49
23 26
23 49
39 ...

output:

result:

ok Player 1 wins

Test #68:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

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

output:

8
18
Player 1 wins

result:

ok Player 1 wins

Test #69:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

42 42 1472 26
15 8
7 27
5 8
24 2
36 18
2 32
16 42
20 17
5 31
31 17
42 20
24 26
15 8
8 36
7 27
21 31
8 27
20 27
38 41
38 26
31 23
5 39
13 7
2 8
13 24
37 23
38 39
38 36
23 39
24 26
3 23
21 2
1 20
20 23
37 36
20 2
1 26
16 2
23 15
20 14
12 39
21 41
23 14
21 36
1 7
13 41
25 17
20 25
42 36
28 27
13 5
13 1...

output:

2
2
2
2
2
2
8
7
7
2
2
2
8
10
2
2
8
5
5
8
5
5
16
6
2
2
2
2
5
5
5
7
8
25
8
8
8
8
11
11
2
2
2
2
2
5
5
5
2
1
Player 1 wins

result:

ok Player 1 wins

Test #70:

score: 0

Accepted

time: 1ms

memory: 3676kb

input:

39 37 209 39
13 7
2 9
7 31
6 1
6 24
10 19
13 23
7 17
14 17
10 15
30 23
5 13
6 21
23 27
16 26
38 35
39 5
37 1
34 15
33 30
24 2
7 27
34 13
17 24
6 15
20 28
17 2
6 19
24 1
5 29
24 15
8 15
25 28
26 9
2 12
2 21
33 3
33 23
34 2
38 12
31 10
39 37
16 27
27 18
33 10
7 25
22 28
9 33
10 35
14 18
16 3
33 9
9 19...

output:

37
Player 1 wins

result:

ok Player 1 wins

Test #71:

score: 0

Accepted

time: 1ms

memory: 3532kb

input:

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

output:

2
Player 1 wins

result:

ok Player 1 wins

Test #72:

score: 0

Accepted

time: 1ms

memory: 3572kb

input:

50 46 648 12
28 11
38 14
39 5
44 41
39 30
3 2
48 46
8 46
25 16
44 39
48 5
4 21
21 18
40 30
39 28
6 41
25 12
10 9
21 6
1 38
9 3
43 31
11 28
12 5
38 34
36 45
13 14
28 28
29 44
17 30
48 37
29 6
43 5
38 3
41 3
7 30
26 4
22 33
38 39
19 4
45 34
17 40
6 20
33 3
36 2
27 29
9 12
36 2
18 1
36 4
42 46
17 39
50...

output:

2
4
11
19
13
23
6
4
2
26
24
20
14
25
20
7
15
1
33
5
5
1
3
7
2
4
3
3
6
8
10
15
25
21
32
42
21
18
32
35
Player 1 wins

result:

ok Player 1 wins

Test #73:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

34 31 579 14
22 8
17 28
22 22
17 18
33 16
31 22
21 22
24 22
9 30
34 22
26 13
24 5
21 11
27 30
27 18
5 5
7 16
15 17
27 8
4 22
5 30
27 21
22 5
3 22
27 17
17 9
26 5
30 11
21 8
4 14
21 9
17 20
13 5
22 29
32 5
9 5
33 2
6 9
5 21
17 17
21 17
21 18
27 18
22 11
30 21
17 30
30 21
26 20
6 8
15 9
33 30
4 20
22 ...

output:

11
5
1
5
5
9
8
8
9
8
9
9
11
11
11
18
8
5
19
22
12
12
20
19
20
20
14
13
15
Player 1 wins

result:

ok Player 1 wins

Test #74:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

47 44 1250 10
24 18
12 15
26 9
32 9
47 15
7 17
13 8
26 3
15 25
45 6
8 19
47 24
40 36
9 9
10 13
22 4
8 15
14 27
10 37
10 22
7 15
14 9
15 35
22 9
14 5
17 22
47 23
17 3
7 9
22 35
45 22
14 8
16 14
3 36
26 2
47 9
30 15
13 19
15 30
23 14
26 25
22 30
26 36
21 3
7 5
33 13
22 6
10 7
7 22
10 31
23 23
16 1
36 ...

output:

1
1
8
9
27
1
1
1
8
8
8
8
8
8
9
2
11
2
2
6
15
4
2
2
3
7
1
2
2
2
1
1
1
1
1
2
2
2
13
18
13
15
3
3
3
4
3
3
4
3
3
3
2
2
6
11
6
6
6
6
6
15
12
Player 1 wins

result:

ok Player 1 wins

Test #75:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

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

output:

1
1
1
5
2
5
3
5
7
6
6
3
1
1
1
2
5
5
6
6
7
5
6
7
3
1
5
5
5
6
6
7
7
7
6
7
7
7
6
1
7
1
3
Player 1 wins

result:

ok Player 1 wins

Test #76:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

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

output:

1
11
4
Player 1 wins

result:

ok Player 1 wins

Test #77:

score: 0

Accepted

time: 3ms

memory: 3564kb

input:

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

output:

result:

ok Player 1 wins

Test #78:

score: 0

Accepted

time: 1ms

memory: 3552kb

input:

38 24 30 11
27 4
8 3
33 13
4 18
4 11
29 11
19 2
21 24
26 22
12 11
8 18
31 15
27 15
36 7
25 17
27 12
8 13
26 10
11 15
7 22
28 4
3 4
11 10
6 2
26 20
4 11
10 12
38 15
14 2
30 15
26

output:

10
20
Player 1 wins

result:

ok Player 1 wins

Test #79:

score: 0

Accepted

time: 5ms

memory: 3616kb

input:

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

output:

result:

ok Player 1 wins

Test #80:

score: 0

Accepted

time: 1ms

memory: 3700kb

input:

48 48 240 38
31 11
28 27
18 7
47 1
7 42
37 4
41 3
40 14
37 40
41 40
3 32
37 24
37 10
47 13
44 7
31 35
22 19
30 14
44 10
13 10
37 29
31 19
38 35
29 1
3 12
41 35
5 42
39 33
39 2
3 39
39 4
30 23
22 19
14 19
39 7
40 7
37 20
44 40
41 42
3 17
17 32
9 11
6 14
15 10
13 32
3 42
37 48
3 23
30 35
3 32
37 3
19 ...

output:

35
3
3
2
2
29
29
20
23
7
3
22
22
29
28
Player 1 wins

result:

ok Player 1 wins

Test #81:

score: 0

Accepted

time: 7ms

memory: 3640kb

input:

50 48 2368 18
10 5
20 45
18 36
47 19
42 24
44 8
19 19
16 42
36 48
44 20
6 19
20 31
7 43
23 10
46 19
33 43
10 21
46 8
4 5
41 32
13 17
36 47
24 25
47 36
9 48
24 17
45 13
48 29
47 12
26 19
23 48
24 8
4 15
10 25
26 21
16 47
45 17
5 47
45 11
17 28
38 2
47 8
13 30
8 12
19 48
40 21
11 41
20 45
26 28
13 24
...

output:

result:

ok Player 1 wins

Test #82:

score: 0

Accepted

time: 1ms

memory: 3636kb

input:

46 43 445 17
27 21
45 22
27 7
29 22
11 22
43 2
34 20
39 42
29 43
2 30
2 1
29 2
16 6
46 8
45 22
3 32
27 31
17 4
43 10
43 11
5 14
5 8
16 10
12 6
43 20
9 24
16 32
12 38
18 28
27 42
9 8
5 10
18 27
12 4
15 2
11 2
2 4
17 13
21 32
21 32
11 23
45 7
5 42
11 20
40 32
6 8
34 22
29 10
36 21
5 6
45 29
12 19
29 3...

output:

7
1
Player 1 wins

result:

ok Player 1 wins

Test #83:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

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

output:

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

result:

ok Player 1 wins

Test #84:

score: 0

Accepted

time: 2ms

memory: 3608kb

input:

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

output:

result:

ok Player 1 wins

Test #85:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

50 50 1959 42
49 32
36 30
4 4
11 37
43 30
19 31
47 21
9 35
10 24
34 31
34 27
35 36
27 13
25 7
28 16
3 16
18 45
7 25
11 44
15 24
40 33
10 11
22 6
33 24
22 35
10 13
33 13
28 11
3 20
40 26
44 36
21 28
8 15
15 10
26 11
45 8
30 8
47 45
39 20
49 22
14 13
15 3
3 23
33 13
11 13
8 41
9 35
19 27
24 8
20 49
38...

output:

result:

ok Player 1 wins

Test #86:

score: 0

Accepted

time: 1ms

memory: 3560kb

input:

48 48 1434 39
28 42
31 10
21 6
7 21
43 21
4 28
24 14
45 1
42 30
47 7
45 14
47 44
44 9
21 42
17 37
29 7
2 42
8 28
22 48
18 19
6 9
47 19
4 47
4 21
17 34
31 14
15 6
7 15
8 28
46 15
13 10
6 21
44 15
22 9
17 21
15 33
2 28
15 26
34 2
47 47
15 6
34 1
18 7
16 20
7 38
16 1
18 19
31 19
20 26
42 33
29 41
2 6
4...

output:

result:

ok Player 1 wins

Test #87:

score: 0

Accepted

time: 0ms

memory: 3560kb

input:

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

output:

4
4
4
4
Player 1 wins

result:

ok Player 1 wins

Test #88:

score: 0

Accepted

time: 6ms

memory: 3624kb

input:

50 50 1911 34
29 41
34 7
35 34
11 19
39 16
27 11
23 24
9 24
4 2
20 37
10 40
18 40
8 7
5 27
9 32
41 22
1 14
16 30
46 38
15 10
47 4
33 45
44 22
49 3
47 9
23 13
25 34
28 6
33 19
6 39
6 19
44 41
48 10
20 38
34 11
9 34
16 13
35 16
5 39
39 17
11 9
35 45
15 9
18 25
28 1
21 46
16 6
45 32
41 11
33 33
9 9
33 ...

output:

result:

ok Player 1 wins

Test #89:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

49 48 159 2
16 11
20 15
5 42
41 46
20 41
39 40
10 9
36 5
30 41
7 25
7 47
47 38
8 34
29 1
30 41
26 42
29 14
39 45
18 29
5 39
27 15
8 45
7 32
31 13
29 30
39 1
6 33
22 41
26 26
20 32
5 46
18 21
34 14
39 28
33 16
16 43
21 21
18 21
8 21
2 14
25 12
28 5
5 30
20 11
46 3
30 20
44 4
39 1
26 8
25 41
39 14
21 ...

output:

14
21
5
5
17
14
28
39
Player 1 wins

result:

ok Player 1 wins

Test #90:

score: 0

Accepted

time: 0ms

memory: 3572kb

input:

49 49 69 33
22 8
22 40
29 27
41 34
14 33
34 3
1 37
7 26
24 46
18 39
10 14
40 48
32 4
45 49
48 25
36 8
26 28
23 25
12 10
29 43
2 5
10 24
5 43
24 42
22 48
34 10
42 23
44 23
43 47
28 30
28 46
48 45
30 13
30 16
2 24
34 27
8 37
11 41
34 36
8 4
2 46
6 39
1 10
4 31
26 8
48 27
6 46
12 13
15 5
1 26
35 42
40 ...

output:

9
Player 1 wins

result:

ok Player 1 wins

Test #91:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

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

output:

7
Player 1 wins

result:

ok Player 1 wins

Test #92:

score: 0

Accepted

time: 1ms

memory: 3564kb

input:

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

output:

2
2
3
3
2
5
5
5
5
5
5
6
7
7
6
6
5
7
8
8
8
7
5
5
5
6
Player 2 wins

result:

ok Player 2 wins

Test #93:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

output:

Player 2 wins

result:

ok Player 2 wins

Test #94:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

37 11 47 27
16 9
28 8
36 1
4 10
2 6
1 5
36 8
5 11
37 8
22 10
30 8
6 7
5 8
12 4
30 8
21 11
9 6
9 6
32 5
9 5
12 1
14 5
32 2
10 9
35 3
37 9
24 1
21 4
25 6
13 3
10 7
28 4
4 7
13 8
28 8
8 5
6 8
16 8
4 6
37 1
6 8
14 8
28 4
29 4
33 1
20 7
20 2

output:

Player 2 wins

result:

ok Player 2 wins

Test #95:

score: 0

Accepted

time: 2ms

memory: 3580kb

input:

50 48 1549 1
48 46
22 42
33 45
18 38
30 35
27 29
48 3
22 18
8 28
40 6
36 22
6 23
45 38
34 46
10 34
40 33
10 29
43 6
49 6
27 6
49 46
40 1
17 17
29 19
40 46
3 46
36 15
6 45
35 38
17 4
34 28
9 25
35 40
17 14
28 25
48 18
27 16
28 2
22 18
24 24
32 20
12 38
32 17
21 29
6 9
8 1
40 3
20 4
50 6
23 5
18 10
24...

output:

result:

ok Player 2 wins

Test #96:

score: 0

Accepted

time: 1ms

memory: 3604kb

input:

35 17 50 31
24 5
21 6
35 13
17 9
25 5
8 13
21 5
23 3
31 10
31 4
7 1
7 10
21 14
3 11
16 8
11 17
16 3
18 11
12 5
14 5
7 5
24 11
35 4
33 6
9 10
33 3
9 6
30 12
7 13
2 9
24 9
27 5
30 13
34 10
20 9
24 3
30 11
25 4
22 6
27 14
1 11
27 3
28 3
27 4
11 5
5 1
16 12
14 4
20 17
8 8
14
12

output:

4
5
Player 2 wins

result:

ok Player 2 wins

Test #97:

score: 0

Accepted

time: 2ms

memory: 3568kb

input:

49 37 1626 9
4 22
1 36
4 17
21 32
22 3
28 15
38 15
3 37
45 13
32 9
28 37
45 9
15 36
2 14
3 4
40 14
8 36
4 28
13 16
13 20
24 33
45 37
48 23
15 9
2 26
3 26
43 33
24 37
26 5
45 16
2 16
3 26
32 16
8 34
47 22
45 20
43 36
40 19
5 37
24 10
19 23
8 23
2 33
38 19
8 32
3 34
43 20
45 36
21 26
19 16
24 16
26 11...

output:

result:

ok Player 2 wins

Test #98:

score: 0

Accepted

time: 0ms

memory: 3600kb

input:

output:

4
8
Player 2 wins

result:

ok Player 2 wins

Test #99:

score: 0

Accepted

time: 1ms

memory: 3612kb

input:

41 24 309 26
37 2
35 22
38 23
6 22
25 18
37 21
17 10
30 18
4 20
23 23
23 18
37 21
14 22
6 21
11 18
10 10
35 10
1 22
32 6
13 15
37 18
7 22
7 15
5 2
1 18
37 18
18 8
35 18
4 10
37 22
28 2
1 6
35 6
14 18
33 22
14 22
13 2
34 21
5 21
30 22
6 21
1 6
14 22
33 21
6 23
35 20
29 21
7 23
5 16
25 6
6 6
32 18
17 ...

output:

23
6
2
5
6
6
7
6
10
8
11
5
6
2
14
10
15
15
10
8
15
15
16
16
18
19
18
21
20
18
15
21
17
23
20
Player 2 wins

result:

ok Player 2 wins

Test #100:

score: 0

Accepted

time: 1ms

memory: 3700kb

input:

49 41 1816 34
16 14
21 12
39 7
48 10
23 14
28 27
13 39
33 35
36 14
1 2
45 27
39 5
18 34
18 28
40 2
17 35
48 26
22 40
37 33
39 8
28 27
45 16
4 21
24 1
16 38
48 15
7 15
37 10
13 31
9 13
1 2
32 18
23 7
16 11
10 1
1 25
26 11
10 31
5 13
18 8
26 13
31 18
23 17
25 30
5 8
5 1
40 12
33 2
24 38
44 16
18 34
4 ...

output:

Player 2 wins

result:

ok Player 2 wins

Test #101:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

1 1 0 1

output:

Player 2 wins

result:

ok Player 2 wins

Test #102:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

1 1 1 1
1 1

output:

1
Player 1 wins

result:

ok Player 1 wins

Test #103:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

output:

1
1
Player 1 wins

result:

ok Player 1 wins

Test #104:

score: 0

Accepted

time: 1ms

memory: 3604kb

input:

output:

1
1
1
Player 2 wins

result:

ok Player 2 wins

Test #105:

score: 0

Accepted

time: 1ms

memory: 3536kb

input:

50 2 2 43
43 1
43 2

output:

1
Player 1 wins

result:

ok Player 1 wins

Test #106:

score: 0

Accepted

time: 1ms

memory: 3600kb

input:

50 40 0 13

output:

Player 2 wins

result:

ok Player 2 wins

Test #107:

score: 0

Accepted

time: 1ms

memory: 3528kb

input:

1 50 0 1

output:

Player 2 wins

result:

ok Player 2 wins

Test #108:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

1 50 2 1
1 4
1 5

output:

4
Player 1 wins

result:

ok Player 1 wins