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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
9
2
0
2
0
0
0
0
4
0
0
2
0
2
1
0
0
0
0
0
3
0
3
2
2
0
0
5
0
1
1
1
1
0
0
0
3
10
2
0
7
0
1
0
0
1
0
0
3
0
1
0
0
2
0
0
0
2
20
8
4
8
0
2
7
2
2
0
6
4
2
5
7
11
5
6
3
7
12
3
7
11
9
3
2
8
0
5
7
4
8
2
2
7
9
10
5
2
17
3
9
0
4
1
6
3
9
6
9
7
2
2
3
3
2
8
27
12
8
17
1
3
9
1
9
0
9
9
9
7
9
14
7
15
10
9
14
10
13
15
15
4
4
9
1
9
11
14
16
3
3
13
15
19
10
12
20
11
14
2
8
7
14
12
11
14
13
9
4
4
6
5
7
9
27
15
12
23
9
5
17
10
11
4
14
16
17
12
18
15
14
19
14
14
17
20
15
17
15
4
7
16
4
14
14
19
21
7
13
17
25
25
14
15
22
14
20
6
10
10
19
14
14
15
16
14
12
11
10
11
9
12
30
21
18
27
11
7
20
17
16
10
19
15
20
14
21
23
21
27
21
18
19
26
18
19
19
5
13
18
10
16
19
28
23
18
20
22
27
27
17
18
25
17
23
11
12
18
22
18
19
17
23
24
16
14
10
14
15
20
30
23
19
27
16
13
26
22
21
19
22
17
25
18
26
25
25
28
22
20
24
28
17
24
23
16
23
25
15
22
25
27
27
24
24
26
30
30
20
27
27
22
28
18
18
25
25
21
26
19
24
33
24
19
14
21
22
25
31
26
22
36
22
13
30
27
23
26
27
20
28
28
29
28
26
32
30
23
30
30
22
24
29
16
25
27
23
29
31
34
28
26
29
29
33
34
29
28
35
27
32
23
27
25
30
24
29
30
29
36
26
26
20
25
22
26
34
31
24
38
24
19
34
29
29
28
30
23
30
29
28
37
30
37
32
28
33
32
26
31
32
20
29
29
25
32
33
35
33
31
31
32
33
38
32
33
37
30
33
28
30
29
36
29
31
31
31
37
30
30
24
30
28
31
35
40
27
43
29
24
36
34
32
33
33
27
35
31
36
40
32
43
35
32
41
38
30
35
34
26
32
34
27
37
32
40
38
34
35
32
35
41
36
37
39
34
39
33
31
35
37
33
36
34
36
39
35
35
29
34
36
34
35
43
28
47
34
32
40
38
37
36
34
34
37
33
38
42
32
43
39
39
42
39
32
38
33
31
34
36
31
38
32
41
39
38
39
37
37
44
38
40
41
36
41
38
35
39
40
34
39
35
39
40
36
40
34
37
37
37
36
46
33
49
40
36
44
40
41
37
34
37
41
39
42
45
37
45
39
41
46
44
32
42
36
31
41
39
33
44
38
44
41
41
43
39
43
45
37
42
44
37
45
41
36
44
44
35
41
37
43
42
40
42
36
40
41
41
41
49
37
50
45
36
45
43
42
39
35
40
43
42
43
46
39
47
46
45
48
47
36
43
36
35
43
42
35
46
43
45
44
43
45
42
45
46
39
44
45
41
46
44
40
46
44
39
44
36
44
44
38
42
39
44
42
44
45
51
41
50
46
40
49
45
42
43
41
44
46
45
45
47
44
48
48
49
48
49
39
46
41
41
47
48
41
49
47
49
47
44
48
44
48
50
41
48
46
45
51
47
44
49
46
43
47
40
47
45
42
46
46
46
45
46
46
52
42
51
49
40
49
51
45
45
45
47
47
48
45
47
44
52
51
49
49
50
42
49
38
44
51
48
44
50
48
53
49
47
51
47
50
49
44
51
48
47
53
48
45
51
49
46
50
41
51
46
42
47
48
46
48
48
48
55
43
54
48
45
52
52
48
46
46
49
52
51
49
50
48
56
54
50
53
51
47
52
44
48
51
50
48
52
48
53
50
49
52
49
52
54
48
54
50
50
53
51
48
51
48
45
51
44
52
49
45
50
52
45
52
51
52
57
44
55
50
47
55
56
51
48
49
52
54
51
52
50
50
57
54
52
54
52
47
53
48
52
56
52
50
52
47
55
54
51
55
52
54
55
50
56
52
50
57
53
52
51
49
46
53
44
55
52
48
53
54
50
53
54
53
59
49
57
50
49
57
57
53
48
50
55
55
53
55
53
51
58
56
53
55
53
50
54
48
52
57
53
54
54
49
57
55
52
57
56
54
56
54
56
53
53
58
56
53
55
50
47
56
44
55
53
49
56
57
50
56
54
51
59
49
59
49
50
57
57
56
49
54
56
57
55
55
57
52
58
56
53
55
54
52
57
51
54
58
55
53
57
53
57
56
53
57
55
54
59
54
57
56
54
60
56
53
55
50
48
56
49
58
54
52
57
58
53
57
55
55
62
54
62
50
54
59
58
56
50
54
58
58
56
58
59
56
61
58
54
56
56
53
59
50
56
60
58
53
58
56
59
58
54
56
58
57
59
58
59
56
57
63
58
56
56
53
49
58
50
60
58
54
59
60
54
58
59
56
63
55
62
52
54
60
60
56
51
55
61
58
58
61
60
56
63
61
56
59
56
53
60
50
57
61
59
56
59
56
60
61
57
58
59
59
60
59
60
58
57
65
59
57
56
54
49
59
51
62
58
56
60
62
55
58
59
58
62
57
63
54
57
61
61
56
55
58
60
61
59
62
60
58
65
61
58
62
57
56
62
50
58
61
62
57
59
56
60
62
59
58
60
59
61
60
61
59
57
66
60
59
56
56
50
62
51
62
59
57
61
64
56
59
59
59
63
59
65
56
58
62
62
59
55
58
62
62
59
63
60
58
65
62
60
64
59
56
63
53
59
62
63
58
59
57
61
62
61
60
62
59
63
61
62
60
58
68
60
62
58
60
54
62
54
64
59
57
63
64
56
60
60
59
64
60
68
58
61
61
64
61
58
60
64
62
60
64
62
59
66
62
61
63
62
57
63
54
61
64
63
61
63
59
62
64
63
62
62
61
63
62
64
61
60
68
61
61
59
60
55
62
57
66
61
59
63
65
57
63
60
60
66
60
69
60
62
64
66
62
61
62
67
62
62
67
64
60
66
64
63
65
62
61
65
56
61
67
65
62
64
59
65
65
64
65
65
62
64
62
65
62
60
68
61
65
59
63
59
64
58
66
61
61
65
65
59
65
61
62
68
62
70
61
63
64
69
63
61
64
69
64
64
67
65
61
68
65
64
65
64
61
67
56
64
67
65
64
65
61
65
64
64
65
65
63
66
64
66
62
61
68
63
67
60
64
60
66
61
68
62
63
67
67
58
65
63
62
71
63
70
62
65
65
70
64
66
65
69
64
65
69
69
63
69
65
66
66
66
62
67
57
64
69
65
66
67
64
68
67
65
69
65
65
68
65
68
62
61
71
67
66
60
66
60
69
61
69
65
63
67
68
60
67
65
64
71
65
71
63
68
66
71
66
68
66
71
66
67
68
69
64
72
66
66
67
66
64
68
57
66
71
65
66
66
64
68
69
68
71
66
66
68
67
69
64
60
71
67
67
60
69
64
69
64
69
66
63
69
69
61
69
66
66
71
68
73
64
68
68
72
68
70
66
72
67
70
68
72
66
74
68
68
67
66
63
69
58
68
72
68
66
70
66
68
72
69
71
66
67
68
68
70
67
63
71
68
67
61
69
64
70
66
69
65
62
70
69
64
70
67
0
0
0
16
0
0
0
0
0
0
0
0
0
0
21
0
0
0
0
0
0
0
0
0
0
21
0
0
0
0
21
0
0
0
0
0
0
0
0
0
0
1
16
0
0
0
1
21
0
13
0
0
13
0
0
0
0
0
18
0
0
36
2
0
1
0
17
1
0
0
0
0
40
22
34
0
16
0
0
31
0
0
15
41
7
0
3
0
39
38
0
0
5
0
0
15
7
9
0
46
30
1
4
41
32
25
0
27
40
27
42
21
0
1
2
1
29
2
11
32
6
1
42
0
34
26
4
17
1
21
41
14
49
15
14
2
4
50
44
19
54
41
21
2
28
0
40
48
0
0
29
16
19
28
22
2
1
52
31
13
14
53
52
42
1
28
38
38
62
22
0
22
31
41
39
7
17
33
21
27
32
2
47
37
6
33
22
38
60
34
63
27
39
1
6
52
49
32
53
61
46
10
36
0
64
54
1
0
47
6
20
30
27
17
13
57
59
45
42
54
71
53
1
57
51
54
71
37
24
43
32
64
0
0
0
23
0
0
0
0
0
0
0
0
0
0
31
0
0
0
0
0
0
0
0
0
0
31
0
0
0
0
31
0
0
0
0
0
0
0
0
0
0
7
23
0
0
0
7
31
0
22
0
0
22
0
0
0
0
0
21
0
1
43
6
1
0
0
22
2
0
0
1
0
49
27
41
0
22
0
0
37
0
0
15
51
8
0
1
0
50
41
0
0
10
0
0
18
10
12
0
58
35
0
7
48
36
37
0
30
45
30
47
25
0
1
5
0
46
3
20
37
15
1
45
0
49
36
8
15
1
28
53
30
60
25
27
2
7
58
52
18
61
56
29
10
30
0
54
54
0
0
35
22
22
35
33
11
1
62
39
4
20
62
61
53
0
33
48
47
70
32
0
32
41
48
0
0
0
37
3
0
0
0
0
0
14
0
0
1
47
3
1
0
1
0
1
0
0
0
0
47
0
0
0
0
47
0
0
0
9
0
0
0
0
0
0
20
37
0
1
3
20
47
0
38
18
5
38
3
0
0
0
0
40
0
1
47
16
0
0
0
38
16
8
0
0
11
62
42
55
9
38
0
1
51
7
0
19
70
20
9
0
0
66
54
0
0
20
0
0
23
24
26
0
71
46
0
15
61
42
48
0
41
53
34
61
39
0
10
0
0
0
0
0
60
17
0
0
0
0
0
24
0
0
17
69
17
17
0
17
0
14
0
6
0
0
69
0
0
0
0
69
0
0
0
20
0
0
0
0
0
0
30
60
0
18
17
30
69
0
63
36
16
63
17
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
1
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
5
1
0
0
0
2
1
0
0
1
0
0
0
0
0
0
0
3
0
2
0
0
0
2
0
0
0
3
1
3
0
0
9
4
1
0
0
6
5
3
3
4
9
0
2
0
0
0
0
6
1
2
1
0
1
2
0
0
0
6
3
3
0
0
10
7
4
1
3
9
6
6
7
7
9
0
0
0
0
0
2
11
1
5
1
0
4
5
0
1
3
7
7
11
0
4
15
10
6
3
6
11
10
8
7
10
11
0
7
2
0
0
6
12
1
7
5
0
7
4
6
6
6
6
11
10
1
3
18
14
9
5
10
16
13
10
7
15
14
0
9
5
0
0
6
14
5
9
3
0
10
7
9
12
9
11
12
14
5
8
21
18
9
7
12
19
17
14
11
14
13
2
11
10
0
3
9
16
4
9
13
0
11
6
11
18
11
11
14
17
11
7
24
19
11
6
15
22
18
17
16
16
14
2
11
13
6
9
13
18
8
11
15
7
14
11
16
22
14
16
13
23
13
7
26
22
14
9
16
21
23
19
21
18
18
6
13
14
14
10
18
23
18
10
17
10
21
11
19
21
20
23
14
23
15
16
28
26
15
15
20
22
28
21
24
21
21
19
13
16
20
16
21
25
24
15
25
15
28
16
26
30
25
23
21
25
18
13
30
28
18
18
25
26
28
21
29
22
24
22
15
16
24
16
24
26
25
18
28
22
26
22
28
31
27
30
22
33
22
19
32
31
17
20
32
28
33
26
31
24
26
28
21
21
30
21
27
27
27
28
32
27
27
26
30
32
31
30
22
34
23
19
36
33
20
29
32
28
32
25
31
24
27
28
21
23
31
20
28
27
33
32
36
31
32
26
32
34
30
38
25
37
28
21
40
38
24
29
38
33
34
27
31
29
31
30
30
30
31
28
31
26
33
35
39
31
32
25
33
35
31
38
27
37
30
24
41
37
26
32
37
34
34
29
34
30
36
33
31
33
33
32
30
30
35
32
42
32
34
27
35
36
33
39
29
43
33
25
42
41
24
35
39
37
35
30
35
33
36
33
33
36
35
36
30
31
37
36
46
39
34
32
39
38
30
42
30
43
34
28
46
41
28
35
37
38
34
29
37
38
36
36
36
37
36
41
33
31
37
38
45
41
37
34
39
39
30
43
33
45
39
31
46
40
32
37
37
38
37
34
39
38
37
36
36
38
38
43
38
32
38
40
46
41
36
34
41
41
31
46
33
44
38
31
44
41
35
37
36
39
39
36
40
40
37
36
38
38
39
44
38
33
40
40
45
42
40
31
41
42
31
47
38
45
39
31
46
43
34
39
37
43
40
37
41
40
37
41
43
38
40
46
41
35
41
42
47
44
40
33
43
42
33
47
38
45
44
32
46
43
34
40
36
45
40
36
41
39
41
41
41
38
39
44
44
38
42
41
48
44
40
33
42
43
36
46
36
46
44
35
52
42
34
41
40
45
40
36
43
38
41
42
43
40
40
45
41
39
42
45
49
45
40
37
44
45
37
47
37
46
44
34
52
44
36
42
44
46
41
39
43
39
44
43
43
39
40
49
42
38
44
48
52
48
40
40
45
46
39
46
38
46
45
35
52
46
36
42
43
46
42
39
44
41
44
44
45
43
41
47
41
38
48
48
52
48
41
41
48
46
38
51
39
48
46
35
52
47
34
49
45
48
46
45
46
40
42
48
49
43
44
49
42
41
46
50
52
49
43
45
52
46
40
50
42
50
47
35
54
47
38
49
47
50
47
43
46
41
43
50
49
44
45
52
43
41
48
50
53
50
44
46
54
46
40
50
42
51
49
35
55
49
38
49
47
55
47
44
50
42
43
52
50
43
48
50
43
41
49
52
53
50
47
45
53
48
41
52
41
53
51
36
55
51
41
49
49
53
51
50
50
39
47
53
53
45
47
51
46
44
50
54
53
54
50
50
56
50
42
54
50
55
51
39
54
52
40
51
49
55
51
51
51
40
48
57
54
45
50
50
46
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
2
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
2
0
0
0
1
0
3
2
0
11
2
0
1
1
0
6
1
1
1
1
2
6
4
2
2
3
6
2
2
0
7
0
13
12
3
16
5
4
8
5
2
9
10
4
4
4
10
13
11
10
10
10
14
9
5
6
17
4
19
18
6
22
15
7
15
15
6
15
19
7
6
7
12
16
16
18
12
16
17
13
14
10
23
6
22
25
14
24
25
16
24
24
13
19
26
17
19
12
19
22
20
25
20
20
20
19
25
16
29
16
26
28
25
25
32
28
25
32
25
23
31
24
22
22
22
29
29
34
30
27
27
24
26
18
29
26
26
33
29
32
37
30
30
33
30
29
33
32
23
26
28
38
33
38
38
34
31
33
31
23
37
29
25
37
31
37
44
33
36
39
34
35
38
38
32
31
35
40
39
41
40
38
34
35
33
32
38
35
23
40
36
40
45
37
40
43
39
39
41
39
35
36
40
43
42
42
42
42
32
37
37
38
38
40
24
46
40
43
50
39
47
46
43
45
44
41
40
39
44
46
46
44
46
45
35
42
41
42
43
43
29
47
43
46
50
42
49
48
44
50
48
45
45
41
47
48
48
45
49
49
39
45
43
47
46
44
32
53
48
48
52
46
50
51
50
51
52
48
49
46
51
51
51
49
52
51
43
47
47
51
48
50
38
56
51
52
55
48
51
56
51
55
55
52
51
50
51
55
54
51
53
55
47
54
50
51
48
53
43
59
55
52
58
51
54
57
55
58
59
56
55
53
55
58
56
53
57
57
51
57
54
55
50
58
44
59
56
51
59
51
56
60
57
62
59
57
55
57
57
59
56
54
57
60
52
58
57
56
51
60
49
61
58
54
59
56
58
60
59
62
61
60
61
58
56
62
59
54
58
61
56
59
58
59
52
61
51
61
60
57
60
60
60
62
62
63
61
62
61
62
58
64
61
57
62
65
56
60
60
60
56
64
53
65
63
58
62
63
65
64
63
65
64
62
64
64
61
65
62
60
64
65
58
63
62
64
57
66
55
67
65
60
62
64
65
67
65
66
66
64
66
65
62
69
64
59
68
68
58
64
64
65
57
68
57
70
68
63
64
67
69
70
66
69
68
66
69
67
63
70
65
63
69
71
59
67
66
65
60
71
58
72
68
64
65
68
68
70
66
70
69
69
71
71
66
70
67
65
71
72
60
68
67
66
60
71
60
74
69
65
68
69
70
72
66
70
71
72
73
72
67
72
68
65
72
73
62
68
69
67
61
75
61
75
71
69
69
71
69
74
70
70
73
74
74
74
69
73
70
66
73
74
65
70
71
71
63
76
62
76
72
71
72
72
70
75
69
71
73
75
75
74
71
74
72
69
74
74
66
72
70
71
64
77
65
78
74
72
74
73
73
78
72
71
75
76
76
75
72
74
72
71
74
77
70
73
70
74
66
79
65
80
78
73
75
75
74
81
72
75
75
77
77
77
73
77
74
72
75
77
71
74
72
74
66
82
67
80
78
75
78
77
74
82
74
77
78
80
77
79
73
77
76
74
78
77
73
74
72
75
68
83
68
81
79
77
78
78
74
83
74
79
78
82
82
81
72
77
76
76
79
77
72
74
74
77
68
84
73
83
81
78
80
78
76
83
77
79
81
82
81
82
75
78
75
78
80
77
74
75
74
79
70
85
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
16
0
6
1
0
0
0
0
0
0
0
0
0
0
17
0
4
0
0
2
4
2
0
0
0
17
10
0
0
0
0
2
12
18
15
22
0
6
0
0
17
0
0
17
0
2
32
0
11
0
0
8
8
5
4
0
9
16
13
1
1
0
9
15
20
13
22
17
0
2
2
0
24
2
0
25
0
16
37
0
13
0
10
3
15
7
19
0
10
28
17
2
2
0
15
27
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
22
1
9
0
0
0
0
0
0
0
0
0
1
0
21
0
9
0
0
0
3
0
0
0
0
21
9
0
0
0
0
0
28
22
28
26
0
2
0
0
23
0
0
13
1
7
45
0
18
0
0
1
15
1
10
0
11
31
21
1
2
0
17
5
6
0
0
0
0
0
0
0
13
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
13
0
0
0
41
0
23
0
0
0
0
0
6
0
0
0
0
12
40
0
22
0
0
1
7
0
0
0
0
40
18
0
6
0
2
0
28
0
0
0
0
0
0
0
38
0
0
0
0
17
0
0
17
0
17
0
0
0
0
0
0
0
0
0
38
0
0
0
0
0
0
0
1
0
13
0
0
0
0
0
0
0
21
1
0
0
0
0
0
0
0
0
0
21
11
31
22
2
37
13
32
29
17
27
36
29
16
30
38
32
8
2
13
13
16
26
37
11
18
38
38
57
50
7
52
15
33
32
13
42
53
43
30
37
51
44
18
5
25
14
49
55
52
34
43
60
44
67
66
9
63
51
34
44
22
64
59
64
47
52
64
59
35
38
26
15
62
63
63
61
49
76
0
0
0
0
8
0
22
0
0
0
0
0
0
0
31
8
0
0
0
0
0
0
0
0
0
31
16
34
27
7
43
17
34
32
21
31
41
33
22
37
48
35
12
2
17
12
17
29
43
18
14
48
43
59
56
13
62
19
40
40
22
54
61
54
41
41
61
54
30
11
34
17
62
62
61
43
59
74
0
14
14
1
20
5
37
13
0
21
14
3
0
0
46
20
0
0
0
5
0
5
0
21
0
46
21
43
36
15
52
22
45
39
31
46
51
51
38
43
61
47
28
10
31
19
26
34
55
26
17
61
0
24
24
18
30
16
63
34
0
44
24
17
0
0
69
30
0
0
0
16
6
16
6
44
0
69