5
6
12
17
8
22
27
18
10
19
28
23
24
26
31
19
25
23
17
15
18
13
17
19
8
7
14
8
10
11
11
16
7
14
25
32
27
31
45
57
84
94
137
180
173
236
299
367
466
532
637
786
868
1115
1259
1465
1634
1787
2029
2223
2586
2834
3064
3331
3745
3830
4293
4530
4821
5076
5184
5506
5695
5850
6149
6124
6219
6311
6313
6384
6164
6351
6212
6155
6133
5918
5871
5673
5616
5484
5454
5258
5097
5098
5078
4992
4888
4993
4896
4896
4962
4914
4822
4874
4820
4833
4793
4832
4750
4654
4607
4522
4458
4302
4227
4032
3823
3568
3437
3082
2861
2622
2441
2313
2027
1742
1561
1427
1217
1074
972
752
806
641
580
479
471
443
384
349
318
307
286
270
259
275
244
239
286
266
226
216
235
226
240
260
240
227
250
190
229
228
241
255
258
282
311
307
294
311
319
350
339
366
387
447
444
510
534
568
590
589
663
632
739
783
820
856
945
989
971
1071
1166
1238
1233
1390
1356
1371
1535
1608
1733
1780
1897
2061
2085
2186
2345
2571
2794
3071
3307
3628
3926
4291
4917
5632
6061
6715
7462
8391
9137
10169
11553
12608
13807
15152
16436
18021
19227
20924
22391
23908
25341
26825
28378
29901
30741
31848
33007
33538
34213
34517
34798
35081
34830
34197
33793
33372
32070
31194
29786
28728
27305
25900
23976
22574
21045
19180
17500
16269
14698
13225
11798
10843
9496
8231
7163
6376
5423
4713
4042
3332
2845
2479
2023
1663
1429
1195
932
821
664
542
449
342
293
230
204
178
141
125
133
99
97
99
98
84
103
86
90
96
82
91
80
72
86
72
104
91
101
84
75
69
66
83
70
58
71
91
88
87
75
84
59
68
61
61
74
57
55
61
59
51
47
52
49
46
54
53
34
29
46
35
51
40
46
32
29
28
27
38
23
26
28
26
31
25
26
22
25
33
24
29
30
25
33
20
25
24
29
29
26
24
30
27
22
21
28
24
36
24
39
30
31
49
48
36
39
38
37
50
52
44
41
45
45
53
42
49
45
63
40
44
64
51
49
60
53
53
52
65
65
51
49
62
59
45
60
50
54
51
50
52
45
35
47
46
52
42
46
40
35
48
38
38
46
27
29
37
37
39
46
37
51
42
39
39
48
61
49
44
28
39
41
38
28
39
51
58
51
37
38
45
37
45
32
59
44
42
50
46
38
43
52
38
44
43
46
37
36
36
37
40
39
25
36
29
29
25
34
21
18
23
28
24
17
28
22
27
27
18
20
14
22
15
13
12
21
14
10
12
8
11
10
7
5
15
7
7
11
6
14
8
7
10
5
5
6
7
4
6
7
6
3
3
6
5
2
5
6
5
2
6
5
3
6
6
2
4
7
3
5
6
3
7
9
3
3
3
4
4
2
9
2
3
2
3
2
4
4
1
5
2
7
4
5
2
0
4
5
2
9
4
4
4
4
3
8
6
6
3
10
5
5
11
5
3
3
3
2
6
5
5
5
6
8
2
7
3
3
4
3
8
6
2
6
7
7
4
4
5
3
5
7
3
8
6
12
6
9
3
3
4
3
3
5
8
5
2
7
12
6
3
4
3
6
5
3
3
3
4
7
6
3
5
5
0
0
5
4
1
8
3
3
3
7
6
4
3
6
5
1
1
1
2
2
2
3
7
2
3
6
1
2
3
0
3
2
3
2
3
3
3
3
2
6
2
4
4
1
3
3
4
4
3
3
3
1
3
5
2
1
3
5
3
5
1
9
2
3
2
1
3
2
0
3
3
3
3
0
5
2
4
3
5
4
5
2
1
1
3
1
1
1
1
1
3
2
6
2
2
2
3
2
4
2
4
3
0
3
3
2
5
3
3
0
1
3
2
4
1
2
3
4
4
2
2
0
3
2
3
1
3
2
4
1
2
1
1
3
1
4
1
1
2
3
4
3
3
1
1
3
2
1
1
2
6
3
1
0
1
7
6
0
1
3
3
2
1
2
3
4
1
1
1
0
4
1
2
3
2
3
5
1
0
2
0
1
3
2
4
2
4
2
4
2
1
1
4
1
2
5
3
1
2
0
2
1
2
2
0
1
1
1
2
1
0
1
1
2
0
2
1
0
1
2
1
1
1
4
3
3
3
0
2
1
0
1
3
4
2
3
1
0
4
1
2
2
2
4
2
1
1
0
0
2
1
3
1
0
3
1
3
3
1
2
1
1
3
1
1
1
2
0
0
0
2
2
2
3
0
1
6
1
0
0
1
0
2
2
1
7
0
0
1
1
1
4
6
2
3
1
1
2
0
1
4
2
1
0
2
1
2
1
3
2
1
3
2
2
2
1
1
2
1
0
2
2
1
0
1
3
3
2
1
0
1
0
0
0
2
1
1
2
0
3
3
2
1
0
0
1
1
0
0
0
0
2
1
5
0
1
0
1
1
1
2
0
1
1
0
4
0
2
1
3
1
1
2
1
1
2
3
1
1
1
1
1
0
3
0
2
0
0
1
3
4
0
1
2
1
1
1
1
1
3
1
2
2
1
0
3
2
1
0
0
0
0
2
0
0
0
0
1
1
1
2
2
0
2
0
0
2
1
0
1
1
3
1
0
2
0
0
3
0
1
1
0
3
0
1
0
1
1
0
0
3
2
0
0
1
4
0
1
2
1
1
1
0
0
1
1
0
1
3
2
5
1
2
1
1
1
2
0
1
0
1
1
1
1
1
0
1
1
0
1
0
0
1
0
2
1
1
1
1
1
1
3
1
1
1
1
0
3
0
3
0
2
0
3
0
1
1
2
2
1
0
1
0
0
0
0
1
1
0
1
0
1
0
0
1
3
2
0
1
1
0
0
2
2
0
0
0
0
0
2
1
0
0
0
1
0
1
1
0
0
0
1
1
1
1
1
1
1
1
0
1
0
3
1
0
0
1
1
1
0
0
0
0
1
1
1
0
0
1
1
2
0
1
0
2
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
2
0
1
1
1
1
1
0
1
2
1
0
0
2
3
1
1
0
0
1
2
1
1
1
0
2
0
0
3
1
0
1
0
1
1
1
0
1
1
0
0
2
0
1
1
0
2
2
1
0
1
1
3
1
1
0
2
1
0
1
2
1
2
0
0
0
0
1
2
0
0
0
0
0
2
2
0
1
1
0
3
0
0
0
0
2
0
0
0
0
1
0
0
1
0
2
1
0
0
0
0
1
1
1
0
2
2
1
1
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
0
1
1
0
1
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
2
1
0
0
0
1
0
0
0
1
1
0
1
0
0
0
1
1
0
0
0
0
1
1
0
1
1
0
1
0
0
2
0
0
0
0
0
0
0
1
2
0
0
0
1
0
1
0
0
0
0
0
0
2
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
1
0
2
1
0
0
1
0
0
0
1
1
0
0
2
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
0
1
0
1
1
0
0
1
1
3
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
1
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
2
0
0
0
0
0
0
1
0
1
1
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
1
0
0
2
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
0
0
0
0
1
1
2
0
1
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
0
0
1
0
1
0
1
1
2
0
1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
1
0
0
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
1
0
1
1
1
0
2
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
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
1
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
0
1
2
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
0
0
0
0
0
1
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
1
0
0
1
2
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
2
0
0
0
2
0
0
0
0
0
2
0
0
0
0
0
1
0
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
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
2
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
0
1
1
2
0
0
0
0
0
0
1
2
1
2
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
0
1
1
1
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
2
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
2
0
1
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
2
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
2
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
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
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
1
0
1
0
0
0
0
1
2
0
0
0
1
0
0
1
2
0
0
0
0
0
0
0
1
0
0
0
0
0
0
2
0
1
1
0
1
0
0
0
0
1
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
1
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
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
1
0
0
1
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
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
1
0
0
0
0
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
1
0
0
0
0
0
2
0
0
0
0
1
0
0
0
0
0
0
1
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
1
0
0
0
1
0
0
2
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
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
2
0
2
0
1
1
0
0
2
1
0
1
1
0
0
1
0
0
0
0
0
0
1
0
0
2
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
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
1
0
0
0
0
0
0
0
0
0
1
0
0
2
0
2
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
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
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
1
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
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
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
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
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
1
0
2
0
0
0
2
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
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
1
0
0
1
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
1
1
1
0
2
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
2
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
2
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
5
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
1
2
1
0
1
1
2
0
0
0
1
3
4
1
2
2
8
7
5
3
4
5
6
5
4
5
5
10
3
6
10
5
9
11
4
3
1
6
5
1
2
1
0
1
2
1
1
1
1
2