0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
1
0
0
0
2
1
1
1
0
3
0
0
0
2
0
4
2
0
1
3
0
0
1
2
1
0
0
1
0
2
0
4
4
7
2
5
4
3
0
6
4
2
0
1
0
1
3
1
0
2
6
0
3
2
4
9
4
8
12
6
8
3
5
4
2
3
8
4
15
5
3
7
13
7
5
11
11
11
5
2
8
9
14
8
18
8
16
6
12
12
10
2
12
11
10
11
7
10
6
10
11
9
10
12
3
14
12
12
14
9
14
17
14
15
10
13
15
8
9
13
12
16
10
9
12
18
14
12
19
15
16
13
10
17
17
17
16
26
13
21
12
17
15
21
9
17
15
17
18
16
18
17
17
16
14
16
20
9
20
20
19
20
19
25
25
21
20
22
23
21
16
18
20
23
25
23
17
20
23
20
20
27
21
25
23
20
26
24
23
23
29
21
25
20
22
23
23
18
22
23
22
24
23
25
26
23
23
22
24
24
19
26
26
25
24
25
31
30
31
28
30
30
28
23
28
25
31
33
32
27
28
30
27
28
35
30
33
31
26
32
29
31
30
37
28
34
26
31
28
29
25
30
31
29
34
27
30
30
31
31
27
32
33
24
31
31
34
31
33
36
35
42
33
35
35
34
30
33
31
36
37
39
32
33
38
32
32
41
36
36
37
33
37
37
35
34
40
37
40
35
38
30
36
30
36
36
35
39
34
35
35
36
35
33
35
37
32
37
36
38
31
37
38
42
44
39
41
42
40
39
40
37
41
45
44
36
40
41
39
44
43
40
44
41
38
43
42
41
40
45
42
47
39
42
37
40
36
44
39
41
43
40
42
45
44
40
41
40
44
37
45
42
43
38
43
40
46
49
40
44
46
43
41
42
44
46
52
50
40
42
47
43
46
53
44
49
46
40
48
46
47
48
48
46
47
43
44
39
45
40
45
44
48
48
44
45
48
46
41
46
46
48
39
49
45
46
45
49
40
53
55
46
49
55
52
51
48
49
52
53
58
45
49
51
53
52
54
49
52
50
47
51
49
50
50
52
52
53
45
49
45
51
49
49
46
50
55
48
52
51
54
45
50
52
53
47
55
48
52
47
52
47
56
60
54
52
57
54
59
53
55
55
58
59
50
55
56
55
56
58
55
56
55
53
55
55
55
54
58
53
56
49
53
53
58
53
53
52
57
57
54
55
56
59
52
55
53
57
52
52
52
57
54
57
51
59
63
58
57
59
59
59
60
57
59
61
66
52
61
57
60
58
63
59
62
58
56
60
58
60
61
64
57
58
53
57
54
65
56
59
57
60
61
57
57
59
66
56
59
59
59
55
56
58
60
58
59
57
66
67
65
62
66
62
63
66
62
65
67
67
58
68
62
66
64
67
63
66
63
62
65
58
66
66
65
63
63
62
62
61
68
63
62
61
64
66
63
63
64
67
62
65
64
60
60
59
60
65
59
64
60
69
69
62
66
70
67
65
69
67
70
73
71
66
72
70
70
70
71
70
70
66
67
69
63
69
68
67
67
69
64
67
68
70
67
67
67
69
71
67
66
68
71
66
73
66
69
67
62
65
68
65
68
61
72
75
62
70
73
70
71
72
72
72
74
72
69
75
71
73
71
73
74
72
74
73
73
69
71
72
74
71
72
70
69
70
74
71
71
70
72
75
70
71
70
72
69
74
71
69
70
67
68
73
69
72
65
76
77
67
74
75
70
75
75
75
76
77
77
71
79
76
76
72
77
76
77
77
74
72
74
76
77
77
75
77
69
73
72
76
74
75
75
76
78
74
75
71
78
75
79
72
74
73
71
74
76
72
72
70
78
77
72
76
79
76
79
79
79
78
79
78
74
80
78
80
77
80
79
80
80
76
77
77
79
81
79
78
79
71
72
78
79
76
77
77
78
80
78
78
71
80
77
80
77
78
77
74
77
81
74
78
74
81
81
72
79
82
80
82
80
83
81
83
83
79
85
82
83
79
81
81
81
83
79
80
81
80
83
81
80
81
70
77
79
81
81
82
81
82
82
80
81
75
83
81
82
80
79
80
78
81
80
80
81
75
82
84
76
81
84
81
83
83
84
84
85
86
83
86
84
85
81
84
84
83
85
83
83
81
85
85
83
84
85
73
80
82
85
82
82
82
84
84
83
82
78
84
84
85
81
82
84
82
82
83
81
81
78
85
87
81
83
86
85
87
89
88
87
87
86
87
89
86
88
83
88
86
86
87
85
86
84
85
88
86
87
87
80
84
82
88
83
86
85
87
87
88
85
84
88
87
89
85
85
86
85
86
87
81
85
77
86
88
83
84
88
86
88
88
89
89
88
88
88
91
88
88
84
88
89
85
88
88
88
85
87
89
88
88
89
77
84
87
89
84
86
89
89
89
89
87
85
88
88
89
86
87
87
87
85
88
85
85
80
89
89
86
86
90
89
90
88
90
90
89
91
89
92
88
91
87
91
89
89
90
89
90
86
90
91
90
89
89
81
86
87
91
87
89
87
90
90
90
88
86
90
90
91
86
88
89
89
88
91
87
89
84
91
92
88
90
91
89
92
93
91
92
90
92
89
94
91
92
90
91
92
90
92
91
90
87
91
92
92
92
92
82
89
90
93
88
92
91
95
92
91
91
86
92
92
93
86
92
90
89
91
92
88
91
85
92
92
89
91
93
90
93
93
91
93
94
93
93
95
92
94
92
92
95
93
93
91
94
89
91
95
93
93
94
85
90
91
93
91
93
93
95
93
93
92
90
93
94
95
87
93
93
90
91
95
89
92
88
95
95
92
93
93
90
95
95
93
95
95
95
95
97
91
95
94
93
95
95
95
92
95
89
94
95
94
94
93
85
92
92
95
93
94
94
96
94
95
94
90
93
95
97
88
95
94
92
94
95
91
95
88
97
98
92
93
95
90
96
97
96
97
96
96
97
98
94
98
96
94
95
96
97
92
96
91
95
98
95
96
96
89
94
92
96
95
95
96
97
97
97
95
90
96
96
97
90
96
95
93
94
97
91
96
89
99
98
94
95
97
93
98
97
97
97
99
98
98
98
96
99
96
97
98
98
98
93
97
93
96
100
95
99
97
92
94
94
97
96
95
97
100
98
97
96
92
97
97
99
90
97
96
97
94
99
92
97
90
99
99
96
97
99
93
99
99
98
99
99
99
100
100
98
101
98
98
99
99
98
95
99
93
98
101
97
99
98
94
95
97
98
97
96
97
101
100
98
98
94
97
98
101
91
99
98
97
95
100
94
99
93
101
101
97
98
99
95
100
100
99
101
99
100
101
100
98
101
99
99
100
99
100
96
101
95
100
102
99
101
99
95
96
97
101
99
97
99
102
102
99
99
94
99
99
102
94
99
99
97
96
101
96
100
0
29
0
28
28
4
22
6
29
0
29
0
0
0
0
28
0
0
0
0
11
4
0
0
0
0
11
0
0
27
0
0
0
0
34
27
0
11
0
0
0
14
11
0
11
0
14
0
31
19
0
0
19
55
47
35
47
66
38
46
45
62
60
47
43
34
33
56
58
34
32
37
4
64
64
42
18
32
56
47
33
49
71
43
50
12
0
47
48
31
41
47
23
27
51
49
30
43
48
51
36
61
54
45
33
72
85
70
74
46
89
42
82
76
90
88
78
79
74
64
91
69
46
46
78
6
94
79
64
31
51
91
63
51
64
89
71
74
54
0
80
73
59
64
71
38
55
86
58
50
80
45
70
73
70
87
79
50
83
100
91
97
51
100
82
83
85
108
102
96
96
98
91
101
88
80
81
75
12
100
82
90
77
66
102
94
54
92
94
93
95
75
46
95
92
70
63
87
81
88
101
83
74
97
56
83
92
80
96
100
88
94
0
43
0
41
45
15
34
18
42
3
43
3
0
0
0
45
0
0
0
0
22
15
0
3
0
0
21
2
0
41
0
0
0
0
41
41
0
21
0
0
3
27
21
3
22
0
27
0
42
28
0
0
28
72
64
38
63
85
41
55
50
76
72
64
49
39
37
71
74
39
39
45
1
79
72
49
23
36
71
54
37
65
91
55
61
18
0
63
62
32
48
61
25
32
60
54
35
48
56
60
40
76
55
62
38
81
93
80
81
63
101
48
93
88
105
100
91
93
91
73
104
86
51
59
88
12
106
89
81
37
56
100
77
55
77
102
85
76
68
0
95
86
67
71
83
42
58
97
72
54
89
54
80
88
84
96
95
62
91
0
63
15
66
72
32
46
36
72
24
63
16
0
0
6
72
0
0
0
0
39
32
0
24
0
6
32
17
0
70
0
0
15
0
53
71
15
32
0
0
16
42
32
24
39
0
42
0
67
44
0
0
44
90
80
48
80
101
53
68
70
97
96
80
66
52
47
91
96
49
52
57
9
99
88
66
36
45
91
74
47
85
110
79
70
28
0
77
86
40
57
82
31
40
75
72
44
56
66
75
48
94
68
81
51
101
14
94
29
99
92
54
60
60
113
43
94
30
0
0
19
92
0
0
0
0
64
54
0
43
0
19
43
31
0
108
0
0
29
0
74
107
29
43
0
0
30
54
43
43
64
0
54
0
98
66
0
3
66
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
2
2
3
2
7
8
8
7
8
14
17
15
18
16
21
23
23
23
23
28
30
29
30
29
32
35
34
37
36
35
40
39
40
40
39
46
45
45
46
43
51
51
49
50
48
56
54
53
56
50
61
58
55
58
55
66
64
61
65
57
68
66
63
66
63
72
71
66
71
66
73
73
69
74
69
77
76
74
75
70
80
79
77
79
74
82
81
81
80
76
83
81
81
82
78
84
83
83
83
80
86
85
85
85
81
87
86
86
87
84
88
87
88
88
85
89
88
88
89
86
90
90
90
90
87
91
90
91
91
88
92
91
92
92
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
2
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
1
0
0
4
7
5
0
2
3
1
5
1
4
5
3
0
2
0
4
3
3
4
6
1
1
2
1
0
5
4
5
4
9
2
7
0
0
0
5
0
2
4
1
2
1
2
3
2
8
2
1
10
16
11
8
9
8
5
13
4
12
10
13
7
9
7
11
12
10
9
16
9
8
6
14
8
14
11
19
12
16
12
13
5
3
4
10
9
7
11
8
10
8
11
13
9
17
5
10
18
23
15
19
17
15
15
18
9
18
16
16
10
18
13
16
19
15
18
19
13
19
13
16
13
18
17
27
16
20
17
19
12
11
12
15
17
13
18
14
19
13
19
19
14
24
15
16
22
28
26
23
26
22
21
27
18
23
23
22
21
27
20
27
23
25
24
28
21
27
22
26
23
25
27
31
26
30
23
24
19
19
20
22
24
26
22
24
26
22
25
23
22
27
22
22
28
37
35
30
35
30
27
32
27
31
30
29
30
35
27
30
32
29
31
36
27
35
30
30
29
33
32
35
30
36
30
32
22
28
26
28
32
35
34
30
29
29
33
31
30
38
33
30
30
38
39
34
41
32
33
38
34
38
36
35
39
39
32
38
38
36
39
40
30
43
35
36
35
39
38
43
37
41
37
40
27
36
34
35
37
40
40
34
35
35
37
37
37
42
41
36
33
45
41
40
44
38
40
47
40
39
42
42
43
46
40
45
42
48
43
46
41
46
39
41
41
46
42
49
40
45
42
42
34
42
39
40
42
45
43
40
43
42
46
43
43
47
44
41
31
47
45
45
51
42
44
51
43
44
48
47
50
47
43
48
47
48
46
49
44
52
42
47
44
54
46
51
47
47
44
48
36
43
44
43
42
54
47
46
47
44
54
45
45
49
47
45
33
52
50
49
56
45
50
59
50
51
52
52
55
52
50
54
50
57
52
56
49
57
49
51
51
58
52
53
52
52
47
51
43
48
48
51
47
57
53
52
51
50
56
50
52
56
51
50
38
56
55
54
59
52
55
61
54
58
54
56
59
58
54
59
54
56
57
60
55
61
52
55
54
61
60
55
55
54
50
54
51
54
54
53
55
59
58
56
54
54
60
54
59
57
58
56
42
61
59
56
62
54
59
68
59
60
57
58
64
61
60
63
60
62
62
63
58
65
57
61
58
64
61
63
59
56
59
60
50
60
59
60
56
61
63
60
59
60
67
58
63
64
61
63
49
67
62
63
68
62
64
71
64
67
62
64
66
66
64
68
66
63
66
68
62
68
63
64
60
66
69
66
65
65
65
67
56
66
62
64
61
68
68
65
63
62
72
62
66
69
63
66
52
68
68
64
71
66
69
72
70
70
64
69
70
70
70
72
69
72
70
73
68
72
69
69
62
72
70
70
70
71
68
67
61
71
68
69
67
71
72
70
69
68
75
69
72
69
69
68
57
72
73
65
73
71
71
75
74
73
69
72
75
72
75
75
75
73
74
78
68
76
73
73
66
78
72
72
72
71
69
72
64
73
72
73
72
73
76
72
72
70
78
72
75
74
75
72
63
73
75
69
78
76
74
80
76
77
77
76
78
75
77
78
78
76
76
79
76
78
75
77
72
77
77
79
76
76
69
73
68
79
74
76
76
78
78
78
74
71
79
77
77
76
75
74
66
78
78
71
77
79
77
81
81
77
77
78
80
79
82
81
81
79
79
82
78
83
77
80
77
81
80
78
77
81
70
73
74
80
79
81
79
79
81
81
76
73
82
80
81
80
81
78
68
80
82
73
81
81
82
83
82
83
80
81
85
84
84
83
85
81
82
86
77
86
77
83
80
84
81
80
82
83
71
77
74
81
83
82
81
84
83
84
81
78
84
83
84
82
83
79
69
82
85
76
83
85
83
86
83
83
81
82
86
86
87
85
87
82
84
85
79
88
80
86
81
86
85
82
85
85
74
78
77
86
84
85
83
86
86
84
83
77
88
85
85
83
85
81
75
86
88
82
85
86
86
86
88
88
82
87
89
88
88
88
89
84
88
88
82
90
84
87
82
88
88
83
87
87
80
83
82
87
83
88
86
86
91
88
86
83
89
87
89
84
86
86
78
87
90
82
87
88
88
89
88
88
84
88
90
89
90
89
89
88
89
90
84
91
86
90
81
89
89
87
88
88
78
83
84
90
86
90
88
89
91
90
88
84
89
90
90
85
88
87
79
89
91
86
88
91
89
91
88
90
86
90
92
91
92
90
91
88
91
92
86
93
89
91
84
89
91
88
89
90
82
85
86
92
87
91
89
92
94
91
90
87
92
92
91
85
90
89
82
90
93
87
89
91
89
92
92
91
89
92
93
92
93
91
94
89
91
94
87
93
91
94
86
91
91
88
91
94
83
86
90
93
91
92
90
93
94
92
90
87
93
94
93
87
91
90
83
92
94
91
91
93
90
93
94
91
91
95
95
94
94
92
95
91
93
95
91
96
92
95
88
94
94
89
92
95
85
88
90
94
91
93
91
95
97
94
93
89
95
95
94
88
94
92
88
94
96
91
92
93
93
95
95
93
92
95
96
96
96
93
95
93
93
95
94
96
91
97
89
95
94
92
94
95
87
91
91
94
94
94
93
96
98
95
94
89
97
96
96
89
95
94
88
95
97
93
94
95
93
97
96
96
94
97
98
98
97
94
97
96
95
96
95
98
92
99
92
96
96
94
96
96
90
92
92
95
95
95
95
98
100
95
95
93
98
98
99
89
97
95
90
97
99
95
94
97
93
98
98
96
96
99
99
98
98
97
98
98
96
97
97
99
93
99
94
98
97
94
97
98
91
94
94
98
95
95
97
99
101
96
97
93
98
98
100
90
98
96
91
99
100
97
97
98
93
101
99
98
98
100
101
100
98
97
100
99
99
98
96
100
94
100
94
99
100
95
99
98
94
94
95
99
98
96
98
100
102
97
97
94
99
100
101
90
100
98
93
100
102
99
99
98
97
101
100
100
99
100
101
101
98
98
101
100
100
99
97
102
96
101
96
100
100
96
101
99
95
95
96
101
99
98
99
102
104
98
98
95
100
101
102
92
100
99
11
20
20
11
20
57
45
56
36
41
72
83
79
43
53
77
89
88
47
58
21
30
30
21
30
72
52
70
41
47
84
91
90
47
58
32
41
41
32
41
88
59
87
47
54
42
54
54
42
54
0
29
0
8
0
0
6
0
0
18
29
33
0
0
0
0
0
0
0
4
0
0
0
18
0
0
28
0
4
28
0
4
0
0
0
6
29
28
0
0
33
28
8
18
0
0
28
0
22
52
60
39
39
14
38
36
46
64
62
65
28
20
22
47
36
1
33
35
45
56
43
21
29
26
47
32
52
65
47
59
12
0
6
41
47
69
46
20
47
56
61
60
21
54
56
39
72
64
77
38
65
26
78
52
49
75
78
89
61
55
73
59
42
1
73
47
79
80
78
27
58
62
69
48
87
86
81
78
44
0
56
77
81
84
67
47
65
82
91
55
50
76
69
54
90
88
93
42
87
43
81
74
50
92
86
100
92
79
94
88
73
59
80
41
93
87
96
70
86
72
95
63
103
93
93
98
57
41
75
97
96
84
83
77
93
88
101
79
81
81
80
88
0
41
0
17
2
0
18
0
0
29
41
40
0
0
0
0
0
0
0
15
0
1
0
29
0
0
39
3
15
41
0
15
0
0
0
18
41
39
0
0
40
46
17
29
0
2
46
0
27
73
60
39
47
18
43
40
62
75
77
81
35
26
27
61
39
1
47
34
62
62
48
30
34
29
62
36
61
82
52
72
18
0
12
45
67
84
59
16
56
69
77
71
24
67
69
45
85
82
87
42
78
30
92
60
66
88
93
103
77
68
84
75
48
1
91
53
91
90
92
37
60
64
82
52
100
97
94
88
54
0
61
90
96
95
80
51
71
91
102
73
59
88
82
60
0
62
15
28
16
0
35
20
0
48
62
52
0
0
0
0
0
0
0
31
0
15
0
48
0
6
64
18
31
71
6
31
15
0
0
35
62
64
0
0
52
70
28
48
0
16
70
6
32
89
78
42
56
25
54
51
82
93
87
97
52
38
32
81
46
1
73
43
84
79
66
45
41
35
81
45
81
102
70
95
28
0
19
52
84
100
83
27
69
91
89
89
30
91
91
54
14
93
28
39
31
3
58
39
0
86
93
69
0
0
14
0
0
0
0
52
0
35
0
86
0
18
98
28
52
111
18
52
28
0
0
58
93
98
0
0
69
90
39
86
0
31
90
18