5.py

import math
import collections
from collections import Counter
import re

TEST = """
47|53
97|13
97|61
97|47
75|29
61|13
75|53
29|13
97|29
53|29
61|53
97|53
61|29
47|13
75|47
97|75
47|61
75|61
47|29
75|13
53|13

75,47,61,53,29
97,61,53,29,13
75,29,13
75,97,47,61,53
61,13,29
97,13,75,29,47
"""

PROD = """
43|66
84|81
84|11
91|77
91|67
91|11
88|11
88|69
88|99
88|37
16|63
16|28
16|19
16|91
16|33
71|64
71|91
71|77
71|26
71|15
71|66
64|32
64|89
64|18
64|75
64|34
64|11
64|33
32|45
32|21
32|99
32|89
32|94
32|17
32|26
32|84
17|12
17|43
17|53
17|46
17|36
17|13
17|24
17|91
17|75
34|94
34|68
34|41
34|23
34|89
34|33
34|17
34|18
34|97
34|87
89|74
89|46
89|85
89|69
89|71
89|99
89|26
89|97
89|22
89|15
89|68
39|12
39|23
39|88
39|19
39|66
39|16
39|75
39|89
39|62
39|41
39|91
39|28
36|62
36|24
36|13
36|26
36|16
36|34
36|39
36|15
36|43
36|35
36|75
36|85
36|71
94|17
94|64
94|15
94|43
94|72
94|91
94|13
94|24
94|74
94|36
94|35
94|49
94|71
94|53
85|53
85|77
85|91
85|64
85|26
85|49
85|66
85|13
85|67
85|88
85|46
85|63
85|34
85|62
85|23
41|99
41|69
41|68
41|81
41|13
41|35
41|15
41|22
41|94
41|37
41|74
41|32
41|11
41|36
41|89
41|85
33|36
33|97
33|41
33|81
33|32
33|89
33|94
33|69
33|45
33|71
33|19
33|15
33|99
33|11
33|18
33|17
33|24
72|91
72|21
72|53
72|77
72|28
72|71
72|26
72|46
72|13
72|16
72|75
72|39
72|49
72|34
72|62
72|12
72|66
72|67
24|66
24|85
24|23
24|62
24|28
24|67
24|71
24|64
24|15
24|16
24|91
24|21
24|46
24|88
24|12
24|49
24|72
24|13
24|39
12|67
12|66
12|84
12|18
12|28
12|89
12|63
12|32
12|33
12|34
12|41
12|49
12|75
12|87
12|77
12|91
12|43
12|88
12|53
12|64
18|24
18|72
18|11
18|22
18|74
18|94
18|36
18|41
18|17
18|89
18|32
18|84
18|13
18|71
18|69
18|45
18|35
18|68
18|97
18|81
18|85
22|64
22|62
22|74
22|99
22|12
22|24
22|49
22|39
22|17
22|46
22|35
22|37
22|36
22|71
22|16
22|26
22|97
22|15
22|81
22|21
22|72
22|13
26|63
26|23
26|91
26|62
26|77
26|41
26|46
26|75
26|43
26|28
26|53
26|19
26|33
26|66
26|67
26|18
26|49
26|88
26|34
26|12
26|64
26|87
26|39
62|28
62|68
62|63
62|23
62|18
62|32
62|33
62|69
62|16
62|91
62|88
62|64
62|19
62|84
62|43
62|66
62|41
62|53
62|34
62|67
62|75
62|77
62|87
62|89
11|81
11|17
11|37
11|16
11|74
11|39
11|72
11|85
11|24
11|35
11|36
11|22
11|62
11|13
11|94
11|97
11|49
11|99
11|26
11|21
11|12
11|71
11|46
11|15
13|67
13|28
13|66
13|87
13|75
13|77
13|53
13|39
13|88
13|91
13|26
13|19
13|46
13|62
13|63
13|64
13|21
13|12
13|34
13|16
13|33
13|49
13|23
13|43
81|72
81|17
81|49
81|46
81|13
81|21
81|43
81|26
81|15
81|85
81|91
81|24
81|94
81|99
81|16
81|74
81|12
81|62
81|36
81|75
81|64
81|71
81|39
81|35
19|11
19|15
19|36
19|37
19|89
19|99
19|84
19|24
19|17
19|41
19|85
19|71
19|32
19|18
19|74
19|22
19|94
19|69
19|35
19|45
19|97
19|81
19|68
19|72
15|66
15|46
15|23
15|49
15|77
15|12
15|28
15|85
15|91
15|53
15|16
15|39
15|88
15|34
15|87
15|67
15|43
15|62
15|64
15|75
15|21
15|26
15|13
15|63
97|36
97|26
97|64
97|43
97|81
97|21
97|46
97|39
97|85
97|49
97|99
97|24
97|16
97|72
97|94
97|62
97|71
97|75
97|35
97|15
97|12
97|74
97|13
97|17
23|88
23|63
23|77
23|19
23|32
23|68
23|41
23|74
23|11
23|18
23|89
23|87
23|22
23|45
23|99
23|84
23|94
23|69
23|97
23|81
23|17
23|33
23|28
23|37
67|22
67|89
67|66
67|77
67|81
67|18
67|37
67|19
67|69
67|87
67|68
67|28
67|23
67|97
67|34
67|32
67|33
67|94
67|11
67|63
67|88
67|84
67|45
67|41
37|74
37|85
37|81
37|17
37|35
37|39
37|36
37|13
37|26
37|62
37|94
37|71
37|64
37|16
37|49
37|15
37|99
37|12
37|97
37|72
37|24
37|46
37|43
37|21
35|46
35|13
35|85
35|21
35|64
35|67
35|34
35|62
35|26
35|66
35|15
35|39
35|75
35|71
35|49
35|16
35|12
35|24
35|23
35|53
35|43
35|28
35|72
35|91
28|88
28|81
28|89
28|33
28|17
28|41
28|18
28|84
28|19
28|63
28|74
28|87
28|22
28|69
28|97
28|68
28|32
28|94
28|45
28|37
28|36
28|11
28|99
28|77
69|12
69|94
69|37
69|15
69|99
69|49
69|97
69|22
69|11
69|21
69|36
69|26
69|35
69|81
69|85
69|46
69|13
69|45
69|39
69|74
69|24
69|72
69|71
69|17
53|34
53|37
53|41
53|89
53|97
53|18
53|63
53|19
53|67
53|11
53|68
53|28
53|77
53|88
53|87
53|22
53|84
53|81
53|32
53|23
53|69
53|33
53|45
53|66
74|71
74|35
74|13
74|34
74|67
74|99
74|62
74|72
74|36
74|21
74|43
74|15
74|12
74|91
74|85
74|64
74|53
74|49
74|24
74|46
74|75
74|39
74|26
74|16
87|72
87|99
87|71
87|94
87|19
87|37
87|18
87|33
87|24
87|45
87|81
87|32
87|35
87|36
87|97
87|41
87|89
87|69
87|74
87|68
87|11
87|22
87|84
87|17
66|11
66|68
66|32
66|33
66|23
66|94
66|69
66|22
66|18
66|63
66|45
66|81
66|88
66|37
66|87
66|89
66|84
66|19
66|41
66|74
66|28
66|17
66|77
66|97
75|89
75|28
75|34
75|33
75|66
75|88
75|67
75|45
75|69
75|22
75|77
75|37
75|11
75|19
75|53
75|84
75|63
75|91
75|18
75|23
75|87
75|32
75|41
75|68
63|22
63|17
63|99
63|68
63|11
63|87
63|19
63|89
63|81
63|32
63|41
63|94
63|84
63|45
63|97
63|72
63|69
63|74
63|35
63|24
63|33
63|36
63|18
63|37
45|97
45|15
45|49
45|74
45|85
45|35
45|81
45|71
45|94
45|24
45|72
45|62
45|21
45|26
45|36
45|13
45|99
45|11
45|22
45|39
45|46
45|12
45|37
45|17
46|33
46|67
46|32
46|62
46|88
46|53
46|43
46|39
46|16
46|64
46|18
46|75
46|23
46|12
46|41
46|87
46|66
46|91
46|49
46|28
46|34
46|63
46|77
46|19
77|68
77|33
77|94
77|41
77|74
77|89
77|63
77|69
77|18
77|11
77|81
77|87
77|84
77|35
77|37
77|32
77|22
77|97
77|36
77|19
77|17
77|99
77|24
77|45
49|66
49|32
49|19
49|88
49|33
49|67
49|28
49|41
49|18
49|89
49|16
49|64
49|91
49|63
49|75
49|84
49|23
49|34
49|62
49|68
49|43
49|77
49|87
49|53
68|12
68|69
68|22
68|17
68|15
68|81
68|37
68|71
68|72
68|26
68|35
68|11
68|46
68|13
68|24
68|39
68|36
68|85
68|45
68|74
68|21
68|94
68|97
68|99
99|72
99|26
99|35
99|36
99|75
99|24
99|62
99|39
99|66
99|49
99|85
99|46
99|34
99|15
99|64
99|67
99|53
99|21
99|16
99|43
99|91
99|71
99|13
99|12
21|46
21|53
21|75
21|43
21|39
21|87
21|16
21|49
21|62
21|63
21|88
21|77
21|19
21|34
21|91
21|33
21|12
21|28
21|66
21|64
21|26
21|67
21|18
21|23
43|89
43|34
43|84
43|77
43|18
43|87
43|28
43|22
43|23
43|67
43|32
43|11
43|88
43|69
43|19
43|68
43|75
43|41
43|53
43|91
43|45
43|63
43|33
84|71
84|94
84|74
84|24
84|46
84|26
84|17
84|68
84|13
84|45
84|85
84|15
84|37
84|35
84|97
84|21
84|99
84|69
84|39
84|72
84|22
84|36
91|37
91|87
91|69
91|88
91|18
91|97
91|53
91|84
91|19
91|34
91|33
91|22
91|32
91|66
91|28
91|41
91|45
91|68
91|23
91|89
91|63
88|87
88|77
88|68
88|81
88|74
88|94
88|19
88|17
88|33
88|22
88|63
88|35
88|97
88|18
88|32
88|84
88|45
88|36
88|89
88|41
16|41
16|75
16|89
16|88
16|53
16|64
16|45
16|43
16|23
16|87
16|67
16|69
16|18
16|32
16|66
16|68
16|77
16|84
16|34
71|53
71|12
71|16
71|23
71|88
71|28
71|49
71|62
71|75
71|13
71|21
71|46
71|67
71|85
71|39
71|43
71|63
71|34
64|91
64|88
64|43
64|66
64|77
64|67
64|87
64|19
64|41
64|69
64|23
64|53
64|28
64|84
64|68
64|45
64|63
32|15
32|35
32|22
32|68
32|11
32|97
32|36
32|69
32|72
32|37
32|24
32|71
32|74
32|13
32|85
32|81
17|85
17|15
17|67
17|74
17|16
17|21
17|35
17|72
17|99
17|64
17|71
17|26
17|62
17|39
17|49
34|69
34|45
34|63
34|32
34|81
34|84
34|28
34|66
34|19
34|22
34|11
34|77
34|37
34|88
89|81
89|94
89|72
89|84
89|24
89|13
89|17
89|45
89|36
89|11
89|21
89|37
89|35
39|64
39|33
39|87
39|53
39|67
39|77
39|32
39|18
39|49
39|43
39|63
39|34
36|64
36|67
36|49
36|53
36|21
36|46
36|12
36|72
36|66
36|23
36|91
94|26
94|12
94|21
94|75
94|85
94|99
94|46
94|16
94|39
94|62
85|12
85|43
85|39
85|21
85|28
85|33
85|16
85|75
85|87
41|84
41|17
41|97
41|21
41|71
41|24
41|45
41|72
33|72
33|74
33|35
33|37
33|68
33|84
33|22
72|64
72|43
72|23
72|15
72|85
72|88
24|34
24|43
24|75
24|26
24|53
12|16
12|62
12|19
12|23
18|99
18|15
18|37
22|85
22|94
26|16

87,63,45,41,37,19,18,88,97,28,89,53,33,22,11,67,34
84,69,45,11,22,37,97,94,17,99,36,35,24,72,15,85,21,26,46
77,32,69,11,94,74,35
46,67,74,26,99,35,13,21,36,71,72,39,12
97,17,99,36,35,71,15,85,13,26,46,49,43
68,22,45,81,94,33,74,18,11,19,41,71,69,97,84,17,24,35,89,32,99,36,37
17,49,74,39,16,46,24,81,26
13,64,88,49,16,21,46,23,12,75,53,85,77,62,71
33,18,41,68,69,45,11,22,37,97,81,17,99,36,24,72,71
49,64,43,75,53,67,34,66,28,77,63,19,18,41,32,89,84
35,36,24,21,72,75,49,46,74,81,39
23,88,77,19,84,11,74
11,33,88,84,45,66,22,89,87,41,17
77,63,33,18,41,32,84,69,45,37,97,81,74,99,36
64,66,13,28,67,16,91,23,12,75,85,53,87,49,43
81,19,89,17,11,36,99,69,18,63,22,97,41,84,77,87,74,45,33,37,32,35,94
97,33,69,66,32,28,45,11,19,63,84,18,81,23,77,22,68,67,89,34,88,37,87
16,64,43,75,91,53,67,34,66,23,28,88,77,63,87,33,19,18,41,32,89,84,69
66,28,88,63,41,32,69,45,22,37,97,81,17
16,91,34,66,23,28,88,77,33,19,32,89,84,68,69
72,43,91,26,62,46,23,21,13,34,85,66,24,75,35,67,16
36,72,71,15,21,16,43,91,67,34,66
23,63,89,37,81
12,91,33,43,13,21,87,88,67,46,34,28,23,75,77
33,18,41,22,37,97,99,35,71
21,64,75,34,23,28,77
19,89,45,15,71,22,69
99,26,12,62,64
37,97,81,94,17,74,99,36,35,15,85,13,26,46,39,12,49,16,64
85,13,21,46,12,49,62,43,75,91,67,23,28,88,77
91,53,66,23,28,88,63,18,89,84,45,11,22
64,91,21,53,12,99,46,72,71,36,17,16,39,62,24,85,35,43,74,26,15,49,13
24,72,71,15,85,13,21,26,46,39,12,49,62,16,64,43,75,91,67,34,66,23,28
84,69,11,97,94,15,46
16,75,67,53,87,89,12,64,23
13,71,11,45,84,81,89,68,22,69,21,99,17,26,94
28,45,34,19,63,97,77
66,11,53,87,68,23,22,33,75,77,45,84,69,34,89,28,32,41,91
23,28,88,77,63,87,19,18,41,32,89,84,68,69,45,11,22,37,81,17,74
37,81,17,74,24,85,46,49,64
28,67,24,64,43,15,53
19,18,41,32,68,45,11,22,37,81,17,99,36,35,24,71,15
68,11,17,36,21
33,18,67,34,66,23,64,12,16,39,88,62,53,49,28,77,43,75,19,87,32
17,37,15,11,74,81,32,68,35,36,89,85,84,94,71,13,22,21,24,99,97
85,21,62,67,34,88,87
62,13,72,15,16,17,21,71,94,35,97,24,36,12,49,74,64
28,87,33,41,84,68,11,74,99
13,26,46,39,12,49,62,16,64,75,91,53,67,34,66,23,28,88,77,87,33
16,64,43,75,91,67,34,66,23,28,88,77,63,87,33,19,18,41,89,84,68
41,32,89,45,11,22,81,94,17,74,99,24,71,85,13
74,99,36,35,24,72,71,85,13,21,39,12,49,62,16,43,75,53,67
91,17,36,62,13,53,16,99,39
66,23,28,88,77,63,87,33,19,18,41,89,45,11,17
66,33,67,91,68,53,75
87,33,19,41,32,89,84,68,45,11,22,37,81,94,17,74,99,36,35,24,72
18,84,22,37,34,89,28,33,19,23,11,87,63,41,69,68,81,88,32,94,97,77,66
15,26,12,13,75,62,71,46,85,72,64,16,35,81,99,21,94,39,17,24,49,43,36
63,41,66,87,19,28,39,33,49,64,18
13,71,53,39,23,15,16,24,72,28,46
39,35,36,26,21,12,94,99,71,15,13,81,85,97,11,37,72,46,74,22,49,17,62
53,34,66,28,88,77,63,87,33,19,18,41,32,89,84,68,69,45,11,22,97
17,74,45,32,35,13,11,37,21,94,89,36,22,99,85
37,18,28,68,17,84,88,81,94,87,77
88,68,63,18,77,64,67,41,32,23,91,75,89,87,19,45,66,84,69,33,43
37,18,41,84,63,88,33,91,66,67,68,89,22,77,23,28,53,11,45,19,69
11,37,22,85,24,69,99,94,46,97,17,15,45,36,35,71,39,21,13
17,21,49,35,15,36,16
35,72,36,85,74,37,26,69,22,24,71,94,11,81,17,84,13,97,45,89,99
84,22,37,97,81,94,17,36,35,72,46
99,36,35,24,72,71,15,85,21,46,39,12,49,62,16,43,91
72,12,35,17,99,36,53
53,67,34,66,23,28,88,63,87,33,19,18,41,89,69,45,22,37,97
71,94,69,36,85,12,72
32,63,34,39,91,66,67,87,16
84,63,87,77,68,23,53,32,75,91,33,19,11,34,22,18,45,67,89,69,88
75,53,67,34,66,23,28,88,63,87,33,18,41,32,84,45,11
74,99,36,24,71,15,85,26,46,39,62,16,43,75,91,53,67
81,69,87,36,45,99,84,32,18,35,22,24,63,89,11,74,97
87,49,53,39,41,28,19,16,66,77,64,46,12,34,67,18,75,33,63,91,62
43,91,53,67,23,87,84,45,11
84,41,74,94,99,72,87,37,18,97,32
89,35,94,72,17,87,11
28,81,89,87,68,94,69,74,84,63,97,23,17,18,41,32,22,77,37,88,11
89,22,97,94,99,72,71,15,85
71,85,13,46,49,16,43,34,66,23,88
28,88,77,63,87,33,19,18,41,32,89,84,68,69,45,11,37,97,81,94,17,74,99
62,46,43,21,24,35,49,12,17,94,36,16,85,75,91
45,22,37,97,81,17,74,99,35,72,85,26,46,39,49
12,49,16,64,43,75,91,53,67,34,66,23,77,63,87,33,18,32,89
12,74,15,94,69,22,24
39,17,24,16,36,62,22,37,85,74,12,49,71,46,26,94,13,99,21,81,35
72,71,85,46,12,49,16,43,75,91,53,67,66,28,88
75,91,53,67,34,66,23,28,63,33,18,68,69,11,22
91,23,34,49,66
41,63,66,16,77,64,49,28,91,75,43,67,88,84,87,89,53,19,62,18,34
24,72,13,12,49,62,75,23,28
74,99,24,15,13,39,12,16,64,43,67
89,32,23,63,11,28,45,41,22,87,75,91,18,19,66
18,74,11,69,77,37,36,94,35,81,19
35,21,26,46,49,64,75,91,53,67,23
11,22,97,81,17,36,72,15,21,26,46,39,12,49,62
64,41,69,19,77,84,45
84,45,37,74,99,36,72,21,46
64,49,66,75,28,84,53
69,11,22,81,74,99,36,24,71,26,46,39,12
32,66,37,87,69,97,23,34,89,41,22,67,53,11,88,19,77
67,34,66,23,77,87,33,19,18,41,32,84,68,69,11,22,81
91,43,46,88,72,75,49,13,67,15,21,66,64,53,62,71,12
37,81,74,24,85,26,46,39,64
74,99,36,46,12,43,91
26,49,62,43,91,53,34,88,77,33,18
62,72,21,67,85,64,12,53,74,13,71,75,39,24,15,43,16,26,46,91,99
88,87,19,18,84,69,81
17,74,35,24,72,71,15,13,26,46,39,12,49,62,16,64,43,75,53
49,62,16,64,43,91,53,67,34,66,23,28,88,77,63,87,33,19,18,41,32,89,84
53,67,34,66,28,88,77,63,87,33,19,18,41,32,89,69,45,11,22,37,97
45,74,68,24,37,13,41,15,35,17,11
62,64,16,12,32,89,91
68,69,11,22,37,97,81,94,99,24,72,71,15,85,13,46,39
63,87,32,84,68,22,37,94,17,74,99
22,37,97,17,36,35,85,13,26,46,16
22,81,26,11,45,69,46,72,84,37,21,13,15
33,19,77,81,28,18,41,34,89,23,63,67,11,87,37,66,68,97,22
43,75,91,67,34,66,23,28,88,77,63,87,33,19,18,32,84,68,69,45,11
69,45,11,22,37,97,81,17,74,99,36,24,72,71,15,85,13,26,46,39,12
49,62,16,64,43,75,53,67,66,23,88,87,33,32,89
64,43,75,91,53,67,34,23,28,88,77,63,87,19,32,89,84,68,45
23,88,63,18,89,84,22,81,94
26,39,49,62,64,43,53,34,23,28,63,87,18
66,23,28,88,77,63,87,33,19,18,41,32,84,68,69,45,11,22,37,97,81,94,17
18,94,89,36,35,22,77,74,99,19,69,97,63
35,24,94,32,85,36,69,15,37,81,97,11,74,72,17,45,22
11,37,94,99,24,15,85,21,26,49,62
66,18,88,32,64,75,34,43,23,62,63,84,19,87,89,53,33
12,49,62,16,64,43,53,67,34,66,23,28,88,77,63,19,18,32,89
19,41,89,84,37,81,74,36,24,71,15
41,37,74,99,36,15,13
17,22,46,69,94,81,74,68,99,36,85,21,45
34,66,33,18,11,97,94
32,84,68,11,22,94,24,71,85
94,17,74,99,36,35,72,71,85,13,21,26,46,39,12,49,62,16,64,43,91
15,85,13,21,26,46,39,12,49,62,16,64,43,75,53,67,34,66,23,28,88,77,63
74,99,35,24,72,71,15,85,13,21,26,39,49,64,75,53,67
97,37,81,41,88,19,77,45,36,84,89,69,94,87,22,33,17
69,45,22,37,97,81,17,74,99,36,35,72,15,85,13,21,26,46,39
67,63,22,28,53,37,34
21,71,26,16,62,35,46,39,17,36,72,43,64,24,75,13,99,15,49,94,12,74,81
39,12,49,62,64,43,91,67,66,23,28,88,63,87,33,19,32
77,88,67,46,53,26,12,39,16,75,33,62,66,13,63,49,34,64,87,21,91
41,11,34,89,19,69,32,91,53,28,67,45,84,37,33,18,23
39,77,49,23,66
45,36,17,89,74
45,11,74,99,24,71,13,12,49
66,23,28,88,77,63,87,33,32,89,68,69,45,11,22,37,97,81,17
19,18,41,32,89,68,11,37,97,81,17,74,99,36,35,24,72,71,15
23,77,91,16,12,39,63,75,64,66,32,67,33
67,34,88,77,63,33,18,41,32,89,84,68,69,45,11,22,37,97,81
97,81,94,17,74,99,36,35,24,72,71,15,85,13,21,46,39,12,49,62,16,64,43
69,68,37,18,77,99,17,97,84,81,63,32,45,35,94,19,89,87,41
75,34,43,46,21,62,15,16,88,91,67,23,77,26,13,64,85,63,39
28,88,33,19,41,89,84,68,69,45,11,22,97
49,62,16,64,75,91,67,34,23,28,63,33,84
19,18,41,32,89,84,68,69,45,11,22,37,97,81,74,36,35,24,72,71,15
33,41,99,71,74,19,11
77,45,41,53,23,69,64,87,75
63,81,68,23,77,11,19,41,34,28,45,18,94
87,11,53,32,33,63,18,22,23,69,91,34,68,67,89,75,45,77,66,28,19
18,41,89,84,37,97,94,17,74,36,35,24,71,15,85
71,24,21,74,94,64,17,91,49
62,16,64,43,53,67,28,77,63,87,33,19,18,41,89,84,68
28,88,77,63,87,33,19,18,41,32,89,84,68,45,11,22,37,97,81,94,17,74,99
21,26,46,39,12,49,16,64,43,75,91,53,67,34,28,88,77,63,87,33,19
43,75,91,23,19,18,41,32,89,84,11
81,22,45,84,89,41,77,35,33
69,45,11,22,37,97,81,94,17,74,99,36,24,72,71,15,85,13,21,26,46,39,12
75,49,28,66,88,41,12,23,91,53,32,67,19,64,43,39,87,16,33,62,18,77,34
88,77,63,19,32,89,84,68,69,45,11,22,37,97,36
64,75,66,62,21,34,36
99,26,46,34,12,53,36,75,62,13,24
21,26,46,39,49,64,43,75,91,67,23,88,77,63,87,33,19
19,18,32,68,11,22,97,74,99,35,72,71,15
32,89,22,97,94,17,74,99,36,24,15
67,34,23,28,88,77,63,87,19,18,41,89,84,68,69,45,11,22,37,97,81
53,49,75,13,46,71,26,62,85,67,28,88,43,91,77,21,16,66,23,12,15
"""

x = TEST
x = PROD
x = x.strip()

# Data in differnt formats for quick access
text = x
lines = x.split("\n")
grid = [list(line) for line in lines]


rules, updates = x.split("\n\n")


rules = [[int(x) for x in row.split("|")] for row in rules.split("\n")]
updates = [[int(x) for x in row.split(",")] for row in updates.split("\n")]


def is_correct(update):
    for first, second in zip(update, update[1:]):
        if [second, first] in rules:
            return False

    return True


from itertools import permutations
from tqdm import tqdm

s = 0
for update in tqdm(updates):
    if is_correct(update):
        # take the middle number and add it to sum
        pass

    else:
        for i in range(len(update) - 1):
            for j in range(i + 1, len(update)):
                first, second = update[i], update[j]
                # find out if a rule is violated

                if [second, first] in rules:
                    # swap the two numbers
                    update[i], update[j] = second, first

        if is_correct(update):
            print("Fixed after swaps")
            s += update[len(update) // 2]
        else:
            print("Not fixed after swaps")


print(s)