St Edwards University Airline Satisfaction Discriminant Analysis

Description

This week’s assignment focuses on discriminant analysis. Discriminant analysis allows for the use of a categorical dependent variable with continuous independent variables. Discriminant analysis allows the researcher to understand if the levels in the dependent variable differ and what independent variables contribute most to the difference between the groups.

Download and review the

Discriminant Analysis assignment document

.

You will use the

DA analysis data file.

Please answer the following questions:

Do each of the variables significantly discriminate between business and personal travelers? Include the Tests of Equality of Group Means table.

What percentage of business travelers was correctly classified? What percentage of personal travelers was correctly classified? What is the total percentage of cases correctly classified? Please include the Classification Results table.

In two to three sentences, as the marketing manager, what types of actions could you recommend based on these results?

What other analysis (not limited to regression) or other variables could you add to the analysis that would be helpful in adding further insight?

Please submit your answers to the above questions as a WORD document and

copy and paste the tables

in the WORD document

. Please do not submit the SPSS output file.

The Bill Munday School of Business
St. Edward’s University
Airline Satisfaction: Discriminant Analysis
During a study, there are often questions that strike the researcher that must be answered. These
questions include questions like ‘are the groups different?’, ‘on what variables, are the groups
most different?’, ‘can one predict which group a person belongs to using such variables?’ etc. In
answering such questions, discriminant analysis is quite helpful.
Discriminant analysis is a technique that is used by the researcher to analyze the research data
when the dependent variable is categorical and the predictor or the independent variables are
continuous. In many ways, discriminant analysis parallels multiple regression analysis. The
main difference between these two techniques is that regression analysis deals with a continuous
dependent variable, while discriminant analysis must have a categorical dependent variable. The
term categorical variable means that the dependent variable is divided into a number of
categories. For example, three brands of computers, Computer A, Computer B and Computer C
can be the categorical dependent variable.
The objective of discriminant analysis is to develop discriminant functions that are nothing but
the linear combination of independent variables that will discriminate between the categories of
the dependent variable in a perfect manner. It enables the researcher to examine whether
significant differences exist among the groups, in terms of the predictor variables. It also
evaluates the accuracy of the classification.
Discriminant analysis is described by the number of categories that is possessed by the
dependent variable. When the dependent variable has two categories, then the type used is twogroup discriminant analysis. If the dependent variable has three or more than three categories,
then the type used is multiple discriminant analysis. The major distinction to the types of
discriminant analysis is that for a two group, it is possible to derive only one discriminant
function. On the other hand, in the case of multiple discriminant analysis, more than one
discriminant function can be computed.
There are many examples that can explain when discriminant analysis fits. It can be used to
know whether heavy, medium and light users of soft drinks are different in terms of their
consumption of frozen foods. It can be used to differentiate between the price sensitive and nonprice sensitive buyers of groceries in terms of their psychological attributes or characteristics.
Professor Wesley Pollitte prepared this note to provide material for class discussion.
Copyright © 2018 by Wesley Pollitte.
The Bill Munday School of Business
St. Edward’s University
In addition, it can be used to understand the characteristics or the attributes of a customer
possessing store loyalty and a customer who does not have store loyalty.
As the marketing manager for a major airline, you like to know how business and personal
travelers differ by their satisfaction and number of flights taken each year, and, if so, can a model
be built to predict passengers flying on business or personal travel.
Discriminant Analysis Assignment
Using the dataset DA analysis.sav conduct a discriminant analysis using the variable Type of
Travel as the dependent variable and Satisfaction and Number of Flights per year as the
independent variables.
If you did this correctly, you should have the canonical discriminant function coefficients for
Satisfaction of 1.159 and -.024 for Number of Flights per Year.
Please answer the following questions:
1. Do each of the variables significantly discriminate between business and personal travelers?
Include the Tests of Equality of Group Means table.
2. What percentage of business travelers was correctly classified? What percentage of personal
travelers was correctly classified? What is the total percentage of cases correctly classified?
Please include the Classification Results table.
3. In two to three sentences, as the marketing manager, Besides doing more research, what types
of actions could you recommend based on these results?
4. What other analysis (not limited to regression) or other variables could you add to the analysis
that would be helpful in adding further insight?
5. Please submit your answers to the above questions as a WORD document and copy and paste
the tables in the WORD document. Please do not submit the SPSS output file.
SatisfactionAge
4
4
5
5
4
4
4
4
2
5
3
3
2
1
3
3
2
3
1
2
3
2
4
5
4
5
5
4
4
5
5
5
5
5
4
5
4
4
4
4
5
4
5
4
4
2
56
43
49
49
33
44
51
28
39
46
26
62
24
75
19
38
62
16
67
47
62
85
34
52
44
28
46
48
25
25
33
48
52
65
59
50
40
51
54
44
32
51
56
52
32
40
NoofFlightsTypeofTravel
41
1
9
1
14
1
0
1
4
1
8
1
12
1
37
1
17
1
29
1
13
1
45
2
33
2
15
2
35
2
35
2
64
2
21
2
42
2
40
2
18
2
28
1
22
1
14
1
13
1
22
1
8
1
10
1
37
1
18
1
7
1
4
1
0
1
26
1
14
1
13
1
7
1
41
1
5
1
21
1
0
1
25
1
13
1
31
1
31
1
10
1
4
4
4
4
4
4
3
4
4
4
4
4
4
3
3
4
4
2
4
3
3
3
4
5
2
2
2
2
4
3
2
3
3
3
5
3
4
2
2
3
4
4
4
5
4
5
5
60
34
44
49
37
40
36
56
59
66
20
45
42
31
17
56
45
36
33
43
67
44
80
48
75
60
66
15
40
65
79
67
74
71
41
32
54
51
51
59
49
30
38
53
29
37
50
27
0
21
6
31
31
16
13
16
14
4
14
12
17
23
1
27
10
24
21
38
21
15
21
22
61
16
13
12
21
41
29
9
23
23
9
9
25
21
25
34
4
37
23
10
40
21
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
2
2
1
1
1
1
1
1
1
4
4
4
3
2
4
4
3
3
3
3
3
3
3
2
3
3
2
2
2
3
4
3
5
4
4
5
4
4
3
4
4
4
5
4
3
5
3
2
2
3
5
3
4
4
3
3
56
37
36
47
80
15
47
19
38
24
20
39
46
43
66
75
71
80
67
16
31
58
36
59
23
56
43
25
45
69
31
55
25
30
21
16
32
30
45
37
21
36
59
35
58
17
49
23
16
4
30
54
23
19
29
3
17
58
9
24
7
25
34
17
53
42
8
43
4
29
0
0
13
14
10
12
32
8
25
7
6
80
6
1
32
10
15
18
13
35
0
10
15
35
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
2
2
3
3
3
2
2
2
2
3
2
4
4
4
3
4
2
2
3
4
4
4
4
5
3
4
4
4
4
4
3
3
4
4
4
4
4
4
5
3
3
4
3
3
3
3
38
66
53
80
75
73
31
56
17
23
46
33
49
37
52
25
36
80
65
80
41
48
20
46
37
25
47
36
20
51
41
25
36
63
39
26
51
56
57
59
25
49
28
52
71
56
53
13
1
23
40
17
8
28
44
35
8
12
22
25
32
14
7
31
33
38
35
18
4
6
19
21
25
4
48
34
3
26
26
6
10
6
0
25
45
22
9
14
8
24
13
30
30
30
1
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
3
2
4
2
3
3
2
3
1
2
2
3
3
2
2
4
4
4
4
3
5
2
3
4
4
5
5
5
3
2
3
3
3
2
3
2
3
2
4
4
4
5
3
3
2
2
40
49
68
33
35
85
71
47
55
80
42
32
31
18
48
79
33
44
47
57
18
48
43
74
51
50
35
30
46
85
28
37
71
19
69
31
68
55
70
34
50
35
34
20
70
43
21
9
10
56
14
14
21
47
36
20
8
30
21
31
38
9
16
31
13
8
4
17
0
20
42
13
13
5
0
31
23
48
40
11
15
52
5
14
27
17
5
16
8
9
10
35
11
43
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
2
1
2
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
1
2
2
2
4
4
4
5
3
5
4
3
2
3
3
4
2
2
4
2
4
4
4
3
4
4
2
2
4
5
4
3
3
3
4
4
4
4
4
4
4
3
4
4
4
5
4
4
5
4
15
38
57
51
34
52
22
67
43
40
61
69
17
69
85
77
41
71
48
25
53
49
17
72
65
47
42
29
52
68
31
46
60
49
28
48
60
44
63
34
39
33
46
23
51
30
28
23
8
28
17
4
24
15
50
17
23
25
34
42
56
11
27
10
43
2
0
1
15
44
6
40
29
0
4
12
21
7
7
38
16
30
52
11
0
9
10
19
13
11
0
27
4
13
2
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
4
5
5
3
3
3
3
2
4
4
3
4
3
4
3
3
3
3
2
3
2
2
2
3
1
2
2
2
3
2
4
3
3
2
2
3
4
4
4
4
4
5
5
4
4
5
36
33
58
23
37
17
39
50
36
31
49
33
39
27
42
41
56
43
56
79
23
80
71
85
70
35
32
67
43
69
16
33
65
85
75
80
78
34
43
29
36
31
40
31
27
33
64
0
16
13
28
14
6
31
6
18
9
19
33
3
0
17
9
22
12
19
42
17
23
55
52
10
20
29
33
30
65
27
20
14
42
16
22
28
27
17
16
19
25
12
13
11
16
26
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
2
2
2
2
1
1
1
1
1
1
1
1
1
1
4
4
4
4
4
4
5
4
5
5
4
4
5
5
4
5
5
4
5
4
5
4
5
4
5
5
4
4
4
4
3
3
5
4
5
4
4
5
3
2
4
3
2
3
3
4
3
35
52
32
53
54
52
44
43
36
51
54
54
41
42
34
27
46
58
43
32
35
46
69
61
44
52
56
53
35
31
35
42
54
38
63
36
37
47
19
57
16
32
47
50
32
49
67
30
31
26
6
23
10
25
28
11
13
43
35
0
2
17
10
0
17
5
6
19
20
22
31
45
32
16
14
14
27
0
32
16
31
3
12
4
23
15
30
19
5
1
17
14
58
12
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
4
3
2
4
2
2
2
3
3
2
2
3
2
3
2
3
4
3
2
5
4
4
4
4
4
4
4
5
4
4
4
4
4
5
5
4
4
4
4
4
4
5
4
4
4
5
53
51
18
32
16
72
66
65
46
58
76
79
27
56
78
18
17
44
21
30
30
31
42
42
48
42
32
27
29
50
59
47
34
52
46
45
38
47
28
56
26
30
38
40
34
29
44
5
8
21
15
17
29
29
38
28
48
36
42
39
24
49
17
19
13
0
25
8
4
5
0
26
0
6
0
7
13
19
27
54
14
9
10
26
7
21
19
0
4
9
19
29
6
0
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
4
4
5
4
4
5
4
4
4
4
4
5
4
5
4
4
4
4
4
4
5
4
4
5
4
5
5
4
4
4
4
4
4
4
5
4
4
4
4
4
5
5
4
4
4
28
40
32
39
63
62
41
43
28
37
61
38
34
45
48
60
49
41
35
43
53
57
48
32
46
34
53
49
57
48
38
48
38
46
52
52
36
38
31
52
27
26
56
50
45
57
28
6
29
13
4
8
17
23
21
25
14
2
13
23
8
23
17
18
33
40
13
3
34
15
4
13
0
15
8
54
25
10
10
0
14
24
15
36
0
27
0
48
35
20
8
0
9
29
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
4
5
4
4
4
4
4
4
5
4
4
4
5
4
4
4
4
4
4
4
4
4
4
5
4
2
4
15
34
41
59
39
26
50
30
38
28
61
54
32
56
38
38
32
42
53
61
37
41
24
54
34
29
38
53
59
33
55
32
40
55
47
29
38
31
34
31
48
41
32
25
59
29
40
14
10
1
11
14
10
17
3
12
4
34
12
24
21
18
4
29
4
12
36
13
25
38
41
15
2
46
6
28
14
13
9
25
22
33
6
16
4
4
16
0
20
30
19
44
17
14
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
4
4
4
4
4
3
5
5
4
4
5
4
4
4
4
4
4
3
4
4
4
5
4
4
5
4
4
5
5
5
5
5
4
5
4
4
4
4
4
3
5
4
4
4
4
62
52
57
38
47
40
49
64
27
52
54
68
50
37
56
59
49
23
37
25
53
58
66
40
50
56
56
55
39
51
44
59
49
37
59
56
57
44
47
48
40
46
27
30
50
23
33
11
0
14
25
5
17
16
32
4
11
0
31
17
29
2
46
26
42
9
37
11
7
16
52
9
14
4
6
16
20
6
16
6
10
2
0
28
16
1
6
0
8
10
4
10
39
21
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
4
4
4
4
2
5
4
4
4
5
4
4
4
4
4
4
4
4
4
4
5
4
5
4
4
4
4
4
3
4
5
4
4
4
4
5
4
4
5
4
5
4
4
4
3
4
52
55
40
33
34
35
48
31
58
28
45
29
33
53
38
58
42
35
49
42
40
50
30
55
57
41
52
39
37
45
45
55
35
35
52
37
51
37
44
38
23
35
30
32
39
64
48
27
6
6
4
19
6
7
17
9
19
10
19
29
13
30
49
4
18
15
34
4
8
10
26
4
16
13
1
12
45
29
11
10
4
29
22
8
17
8
14
7
0
10
20
5
5
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
4
4
4
4
5
4
4
4
5
3
4
4
4
5
4
4
4
4
4
4
3
4
4
3
3
4
4
4
5
5
4
4
4
5
4
4
4
3
5
4
4
4
5
4
2
37
41
30
33
52
58
38
52
49
48
40
50
48
33
39
40
27
52
66
26
47
25
17
46
41
32
30
34
32
33
43
51
37
49
58
29
34
45
43
18
46
61
18
24
50
55
44
8
2
23
22
11
7
0
32
10
51
8
45
15
2
4
5
12
13
49
0
14
1
20
21
10
26
47
30
16
11
4
0
20
2
0
21
22
48
4
0
17
40
20
3
40
4
17
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
2
4
4
4
4
3
4
4
3
4
4
3
4
4
4
4
1
4
3
4
3
4
4
3
3
4
4
4
3
4
5
5
4
4
2
4
5
2
3
5
4
4
4
4
5
50
55
38
44
40
36
34
47
27
35
17
44
47
41
48
44
64
50
45
56
36
64
16
27
42
34
41
38
39
33
56
46
63
47
32
39
50
36
52
72
51
58
52
49
37
47
47
12
39
15
16
9
0
38
17
28
17
8
20
33
9
8
21
31
10
24
4
13
29
31
0
20
17
1
24
13
52
12
20
10
20
19
41
22
13
25
7
25
24
44
9
12
5
10
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
5
4
4
3
4
4
4
4
4
4
4
4
4
3
3
4
2
5
3
3
4
2
4
5
2
4
4
4
5
4
4
5
3
5
3
5
4
3
5
4
4
2
3
4
3
5
53
56
28
36
28
46
30
27
33
37
33
43
47
64
18
56
49
39
34
73
17
52
31
39
40
42
37
60
27
39
27
30
40
41
48
30
46
46
17
41
49
51
44
17
60
48
43
15
21
0
28
10
32
13
17
20
19
0
44
7
22
37
24
17
0
33
4
8
35
24
12
4
15
0
6
18
7
14
8
6
34
7
0
10
13
18
3
24
34
15
10
0
31
38
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
4
3
3
3
3
2
3
4
2
3
4
3
3
3
4
4
4
2
5
3
3
4
4
5
4
1
4
4
3
3
2
3
5
3
3
3
1
3
3
3
3
4
3
4
4
3
25
30
52
45
44
25
39
58
27
57
75
48
52
17
30
37
70
80
37
36
41
17
32
34
68
55
47
55
61
57
31
46
18
73
42
34
39
43
25
37
56
58
70
23
52
30
19
17
8
5
10
6
14
2
14
5
48
4
10
28
33
33
13
13
20
42
29
43
20
0
15
21
14
8
26
5
18
46
27
25
31
9
9
21
10
47
0
22
31
46
7
12
10
41
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
3
3
3
2
2
3
4
4
3
4
3
4
3
4
5
4
4
3
3
2
3
5
2
3
3
4
4
3
3
4
4
3
4
3
4
2
4
4
1
3
3
3
3
4
3
3
38
63
38
23
68
40
17
18
45
53
26
45
18
79
77
38
26
39
52
44
54
73
45
38
21
64
35
53
31
20
73
17
80
31
59
31
15
29
45
47
44
24
17
31
59
32
33
14
25
15
9
32
2
12
13
26
10
4
18
3
47
14
4
16
21
14
0
9
28
8
20
30
47
7
26
5
14
4
18
13
10
15
4
34
18
4
0
8
17
5
0
16
15
55
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
3
2
4
3
3
2
3
3
2
3
3
3
4
3
4
3
3
4
4
3
4
4
4
3
3
4
3
2
3
3
3
3
2
2
4
3
2
3
3
4
4
4
3
3
3
4
51
53
39
16
40
36
51
18
47
58
48
19
44
18
27
45
35
23
19
51
77
58
61
56
32
76
27
55
47
43
58
45
25
39
62
34
57
49
61
43
42
24
44
61
54
17
29
13
8
22
21
40
3
17
18
10
21
19
15
19
3
4
13
6
17
24
7
29
8
15
15
6
9
4
4
6
0
13
19
25
0
4
14
45
46
26
41
3
10
26
9
8
11
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
4
4
3
3
3
2
1
3
1
3
4
3
3
1
3
4
3
3
4
3
3
4
3
3
4
3
3
3
4
3
4
3
3
3
2
2
4
4
3
3
4
4
4
4
4
5
33
46
21
46
61
28
35
70
78
36
63
76
61
34
35
24
17
41
74
20
33
68
38
51
31
17
51
57
66
27
46
57
40
27
47
54
43
17
20
36
41
53
48
28
31
64
59
6
10
8
5
10
1
56
25
45
26
15
15
47
4
8
9
5
15
14
21
46
20
16
8
25
2
6
24
18
25
19
4
13
13
7
12
1
17
42
8
13
29
4
29
6
5
23
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
3
5
2
5
4
2
3
3
2
2
4
2
2
2
3
2
2
5
4
2
2
2
3
3
4
2
3
2
2
2
2
2
2
2
2
5
3
3
2
2
2
2
3
2
2
2
61
68
27
80
58
65
20
30
19
15
76
45
18
51
40
67
65
85
29
68
61
51
69
73
64
31
64
71
37
80
19
78
18
15
85
77
48
71
30
35
58
78
16
59
67
75
38
41
3
0
68
8
18
24
10
36
8
19
11
29
28
53
38
39
26
19
6
68
21
42
43
17
20
7
28
4
28
13
25
31
22
30
26
30
29
12
14
19
13
25
60
40
56
33
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
2
3
3
3
2
3
3
3
3
2
3
1
3
4
3
3
3
3
3
2
3
3
2
2
2
3
2
2
2
2
3
3
2
4
2
3
3
4
2
1
2
2
3
3
56
34
73
21
72
65
49
71
71
70
74
85
80
76
66
64
80
57
75
67
47
39
80
68
72
79
47
71
55
76
57
64
65
43
59
69
34
58
68
63
42
40
80
80
78
68
80
10
13
40
14
77
20
18
23
32
30
25
24
8
17
36
41
12
63
0
26
10
5
29
24
56
21
77
10
29
17
24
21
37
23
16
11
19
19
14
36
8
36
52
20
40
8
16
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
2
2
3
3
2
2
2
2
3
3
2
2
4
2
3
3
3
2
2
3
2
3
3
2
2
2
2
3
4
4
4
3
3
2
3
2
3
2
3
3
3
2
2
2
2
80
31
72
17
16
80
77
72
71
18
51
71
73
35
63
26
76
69
80
78
16
72
36
18
54
72
85
70
58
58
65
59
47
34
44
18
17
78
57
85
67
33
85
15
63
53
64
55
5
33
36
17
31
58
37
30
55
15
35
24
29
35
0
33
30
42
13
42
33
13
17
29
37
22
51
31
43
25
20
18
11
11
8
13
55
50
33
33
18
43
25
38
28
23
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
3
2
2
2
1
4
2
3
2
4
3
2
3
2
2
3
3
3
3
3
3
2
2
2
2
3
2
3
2
2
3
3
3
1
2
2
4
3
4
3
3
32
75
64
80
36
35
72
15
64
16
64
43
80
67
72
23
70
79
80
79
69
85
17
65
15
64
85
68
59
69
17
70
70
80
61
52
45
53
74
32
57
30
35
35
30
48
32
0
17
34
17
28
19
39
42
50
21
38
0
32
41
21
8
33
31
41
23
51
16
13
23
35
19
9
25
43
44
0
42
75
51
37
36
0
31
26
20
13
48
0
4
12
31
11
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
2
2
2
2
2
2
2
2
2
3
2
2
3
3
3
3
3
1
4
1
3
2
2
2
2
2
2
2
3
2
3
2
2
2
2
3
2
3
3
3
2
3
2
4
3
80
79
16
76
47
63
51
71
19
69
76
23
45
58
78
63
72
28
65
50
57
72
75
57
78
78
31
18
70
74
64
70
18
72
85
49
39
80
54
72
43
47
70
31
22
39
54
33
17
6
20
37
54
28
50
40
12
40
12
13
62
47
8
24
30
5
6
9
33
33
35
54
31
15
27
40
41
15
6
28
33
33
14
18
13
3
48
47
6
28
7
2
34
34
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
2
3
2
3
3
3
2
2
1
3
4
4
4
4
4
5
4
4
4
4
4
4
4
4
4
4
5
4
5
5
4
5
4
4
4
4
4
4
4
4
4
4
4
4
4
64
53
78
41
60
67
70
80
68
73
43
80
62
48
69
33
18
55
42
55
42
24
30
29
56
29
53
64
34
33
44
54
39
36
45
47
24
41
27
36
31
45
58
30
52
46
56
17
50
22
17
26
56
17
30
33
13
31
12
1
10
12
4
29
10
29
5
14
5
13
6
20
46
4
5
14
0
20
29
3
8
28
15
7
9
8
6
0
12
10
0
31
19
12
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
3
4
4
4
4
4
4
5
3
4
4
3
4
3
3
3
4
5
3
3
3
4
2
4
4
4
3
2
3
4
4
3
3
4
2
2
4
3
2
2
3
3
3
1
3
2
25
48
38
45
50
35
36
28
30
16
23
56
16
61
34
41
55
32
63
17
54
34
28
64
41
51
56
72
68
26
38
20
46
18
55
60
19
50
17
30
68
65
67
41
56
22
60
1
28
10
20
7
3
31
16
10
0
45
0
19
10
12
15
8
13
15
6
11
22
16
30
15
23
47
1
33
14
0
11
25
14
8
32
23
8
19
23
22
26
24
1
21
21
36
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
3
2
2
3
2
3
2
3
2
2
1
4
3
3
2
2
3
1
2
2
2
4
2
5
4
4
3
3
3
4
4
4
3
3
4
4
3
1
5
4
4
5
4
16
72
80
41
25
73
85
80
36
85
80
40
63
41
46
68
67
85
80
58
72
63
27
62
67
52
63
39
25
21
57
20
45
50
40
40
45
48
26
47
80
80
39
59
45
41
40
8
20
19
29
4
20
13
0
4
10
17
10
21
28
50
19
23
19
38
8
16
22
8
45
12
5
26
3
27
2
2
32
12
5
5
5
12
6
48
44
35
28
9
33
9
8
35
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
1
1
1
4
4
4
4
5
4
5
4
3
4
5
4
3
2
3
3
3
4
4
2
3
2
3
1
2
2
2
2
3
3
3
5
2
4
3
2
3
5
4
5
4
4
4
5
4
2
5
55
48
38
34
56
56
34
55
43
40
54
25
46
45
40
32
29
43
50
72
38
73
50
80
74
77
74
35
50
77
77
29
50
73
65
79
17
30
51
41
30
74
31
41
55
51
34
23
2
14
13
4
19
3
38
0
20
8
45
14
19
6
16
5
8
12
25
17
41
1
45
39
35
49
17
45
23
28
37
30
18
32
29
8
22
2
4
19
36
45
6
29
0
40
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
2
2
1
1
1
1
1
1
1
1
1
1
4
3
3
4
2
2
3
1
2
3
2
3
4
4
4
4
4
4
4
4
4
5
4
5
4
4
4
4
5
3
4
5
4
3
4
3
3
3
4
3
2
3
3
3
3
2
2
23
29
39
36
17
16
75
74
53
21
43
80
28
49
29
58
46
51
33
44
32
35
23
40
38
36
50
36
57
36
21
46
52
48
48
46
45
55
42
61
38
28
39
51
51
17
76
25
23
20
12
7
28
47
22
43
48
6
0
6
16
15
8
1
12
9
26
23
24
30
10
28
21
22
2
17
32
18
21
23
44
50
9
8
25
5
30
40
6
10
3
22
21
20
1
1
1
2
2
2
2
2
2
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
5
2
3
1
3
2
2
4
3
2
2
2
4
4
5
3
2
4
4
4
4
4
5
4
4
4
4
3
4
4
4
3
3
4
3
4
4
3
2
3
2
4
2
3
3
4
2
39
85
39
69
67
29
50
22
72
85
70
15
60
24
45
64
85
60
42
52
30
49
31
40
53
53
32
69
21
48
56
52
64
36
26
25
24
16
32
19
56
41
20
77
80
32
16
13
34
12
36
23
23
75
5
8
28
60
11
26
8
18
8
30
14
5
24
24
12
28
8
24
40
18
71
23
23
20
18
20
18
23
19
21
3
16
29
14
17
8
17
28
16
23
2
2
2
2
2
2
2
1
1
2
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
3
3
2
3
3
1
2
2
2
3
3
3
3
3
4
4
4
3
2
2
2
5
4
5
4
4
5
3
4
3
3
3
5
2
3
2
3
3
3
2
4
4
2
3
4
4
4
54
65
67
72
77
57
36
85
80
26
66
41
80
39
25
54
47
70
44
44
72
46
38
40
53
50
44
47
59
47
16
19
50
62
68
54
44
35
47
77
48
40
58
73
49
63
56
54
21
33
31
12
13
8
17
10
31
7
45
26
9
22
31
12
40
26
42
0
15
4
9
4
11
30
31
44
0
36
13
12
67
40
4
8
8
12
0
4
18
28
13
23
13
21
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
2
2
2
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
4
2
4
1
4
1
4
4
5
3
3
3
3
2
2
3
3
3
2
2
5
4
5
5
5
3
3
3
2
4
4
2
4
4
4
4
3
4
3
3
1
4
5
4
4
5
4
40
77
39
57
24
56
29
42
50
47
59
19
42
85
63
45
78
77
15
85
40
32
62
33
37
52
61
38
70
73
61
80
47
64
59
47
41
55
62
58
80
34
59
23
50
31
53
3
64
4
23
23
36
0
14
8
14
13
23
0
36
38
15
26
16
1
30
18
13
20
12
6
24
30
14
49
18
12
39
17
18
12
15
57
22
29
39
48
46
23
19
18
14
2
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
2
2
2
2
1
1
1
1
1
1
1
2
2
1
1
1
1
1
1
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
3
4
4
3
3
2
4
3
3
3
3
4
2
3
4
4
3
2
5
3
3
4
4
2
2
3
2
2
3
2
1
3
27
22
31
23
39
45
49
30
56
39
48
56
22
35
56
41
30
44
49
35
43
19
48
63
73
45
53
44
63
40
41
44
65
40
80
71
46
55
66
74
80
51
36
20
59
28
15
19
14
24
52
2
8
24
23
9
16
10
25
42
1
19
4
15
43
20
0
12
43
32
10
48
13
13
6
4
6
7
16
27
19
45
25
10
10
11
42
31
26
31
8
31
16
27
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
4
4
3
4
4
4
4
1
3
3
3
3
2
4
4
3
4
5
4
5
4
5
5
4
4
4
4
4
2
4
4
4
4
4
4
4
4
3
5
4
4
4
4
4
66
73
85
53
29
62
37
58
63
40
48
52
55
51
65
30
33
49
24
57
40
55
51
33
58
53
52
29
66
43
42
48
42
36
55
40
40
49
39
58
29
41
60
53
63
52
40
10
33
31
20
21
13
0
8
12
9
0
27
3
8
24
40
18
22
6
54
8
8
15
13
25
8
37
50
21
22
10
12
14
15
14
20
21
15
7
13
4
8
11
3
0
35
10
2
2
2
2
1
1
1
1
1
1
1
1
1
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
4
4
5
4
4
4
4
4
4
3
2
5
2
3
3
4
4
3
3
4
3
3
4
3
3
2
4
3
3
3
3
2
3
4
2
4
1
2
2
2
3
3
3
2
2
2
50
44
44
41
47
44
57
33
33
16
50
73
49
67
39
29
30
33
79
65
26
20
30
51
31
29
39
58
40
73
70
62
80
40
45
78
31
60
56
80
54
61
67
22
74
55
28
12
2
11
8
8
4
6
9
53
13
11
35
1
14
21
8
12
12
2
22
29
3
25
15
3
17
6
13
11
41
21
45
37
0
5
37
8
14
45
26
25
12
59
15
58
8
63
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
4
3
2
5
3
4
3
2
2
2
4
5
4
4
4
4
4
4
4
4
4
4
2
3
3
4
3
4
3
4
3
4
2
2
3
2
3
3
3
4
5
4
5
4
5
3
34
67
70
77
40
68
59
72
24
59
40
45
36
26
52
29
30
56
41
42
49
54
39
40
24
38
65
56
18
52
57
65
31
67
75
77
63
80
31
18
48
64
23
32
29
56
76
16
26
20
29
16
12
13
37
16
43
13
15
0
27
4
4
16
66
4
0
29
23
1
10
27
3
18
9
19
15
0
6
33
25
42
25
58
37
0
5
0
17
4
2
10
19
23
2
2
2
2
1
1
1
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
1
2
1
1
1
1
1
1
1
2
2
5
4
4
5
4
4
4
4
4
5
4
4
4
4
3
3
5
4
4
4
4
5
5
4
5
5
5
5
4
4
4
4
5
4
4
4
3
4
3
3
4
4
4
4
4
69
70
62
50
54
38
32
39
61
40
39
37
44
54
26
46
22
44
40
38
34
38
27
34
43
48
37
35
53
39
36
43
36
36
33
60
39
31
21
57
19
49
52
38
60
51
46
13
24
8
13
5
6
7
8
11
22
10
11
8
25
4
0
6
12
50
24
13
10
6
0
10
23
6
10
8
17
8
11
13
7
11
0
9
17
23
6
40
17
15
1
13
37
45
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
5
3
4
3
3
3
3
3
3
3
3
3
2
2
4
2
3
4
4
2
1
2
3
2
4
2
3
3
2
2
2
3
2
1
4
3
2
3
2
3
2
3
2
2
2
2
37
51
53
37
42
16
35
61
36
46
47
35
56
27
49
33
66
68
22
31
73
38
78
79
80
34
63
38
15
72
78
67
80
76
41
42
74
60
36
60
29
66
52
42
68
66
59
11
9
10
34
21
5
45
30
35
7
18
6
19
40
15
16
34
13
14
4
53
18
21
27
41
11
43
12
16
30
48
32
14
23
41
43
12
59
8
22
21
54
36
30
32
36
57
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
3
2
4
5
4
4
4
2
2
2
2
3
4
5
4
5
4
4
5
2
3
4
2
3
4
4
4
4
4
3
4
4
5
5
5
5
4
4
4
5
5
4
5
4
3
80
65
51
55
54
25
46
28
18
75
74
31
51
41
49
35
37
49
46
30
49
68
19
50
30
43
42
27
43
35
51
34
37
58
56
43
50
30
52
38
46
52
30
37
36
56
41
45
20
32
43
14
24
16
1
9
21
29
25
33
14
9
6
26
22
10
9
32
4
9
2
26
30
13
35
23
30
20
12
28
0
18
13
2
3
0
13
6
16
30
16
25
36
0
2
2
2
2
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
5
5
4
3
2
4
4
4
5
4
4
3
3
4
2
4
3
3
3
1
4
4
4
2
2
2
3
3
4
3
3
2
3
3
1
2
3
3
3
2
2
3
4
3
3
3
45
44
35
50
29
44
35
41
44
58
56
34
35
38
51
78
40
52
18
32
55
16
34
16
48
17
80
48
72
80
68
51
46
52
73
71
28
71
80
38
60
80
80
42
38
72
37
13
10
8
30
8
12
17
16
6
10
4
17
12
5
35
23
46
23
4
8
16
8
26
9
0
36
29
35
26
59
37
21
45
6
20
30
34
35
37
22
35
46
75
18
31
14
41
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
3
2
2
2
3
2
2
5
5
5
5
4
4
5
4
4
5
4
4
4
2
4
4
2
3
3
3
3
4
3
2
3
2
4
3
2
3
3
3
3
4
80
63
80
67
51
53
17
73
37
39
16
69
15
42
66
39
48
36
51
45
43
44
51
45
68
50
34
21
78
69
49
57
35
45
27
50
48
50
80
74
38
45
70
17
53
37
25
56
48
53
25
5
13
27
0
0
38
17
28
2
5
16
22
19
15
34
33
15
1
14
41
16
4
10
21
7
32
0
8
23
10
34
23
11
1
8
29
16
4
9
41
58
25
0
2
2
2
2
2
2
2
2
2
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
1
2
2
2
2
1
4
5
3
2
4
5
4
4
4
4
4
4
4
4
4
4
4
2
4
3
3
4
4
3
4
4
1
3
2
3
3
3
1
3
4
3
3
3
2
3
2
2
2
3
3
2
2
35
57
20
26
35
38
52
50
41
34
55
29
33
43
53
40
37
67
59
35
23
57
55
49
57
42
36
45
45
57
25
34
52
45
24
36
66
22
21
48
68
80
27
51
85
42
67
15
40
47
12
16
51
12
6
0
8
5
3
12
0
2
0
0
6
14
13
24
24
17
17
29
27
5
12
36
0
13
11
7
28
1
2
0
0
42
18
63
47
37
21
25
42
34
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
4
2
2
2
2
2
5
4
2
4
3
1
5
4
4
4
4
4
5
4
3
4
4
3
3
4
4
4
2
3
3
3
2
3
2
4
4
4
4
4
4
4
5
4
3
4
4
32
62
23
57
17
67
29
53
17
42
70
46
45
48
47
28
38
49
47
55
73
27
59
67
53
22
23
35
39
19
75
62
79
53
76
63
49
70
41
38
51
41
42
37
50
52
39
18
10
29
16
13
43
7
13
23
21
29
16
4
17
1
14
4
0
21
25
21
17
0
20
21
21
15
16
38
4
15
40
29
14
23
6
6
25
37
39
17
38
1
11
27
24
22
2
2
2
2
2
2
1
1
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
4
3
5
5
4
4
4
4
4
4
4
4
4
4
4
4
5
4
5
5
4
4
4
5
5
4
4
4
2
4
4
4
3
4
3
5
4
4
2
3
3
3
3
3
4
4
3
27
30
28
31
36
59
57
36
27
22
74
38
51
53
32
59
51
62
30
27
59
59
27
37
60
33
47
26
59
34
54
55
21
56
74
63
57
58
60
44
18
63
52
57
37
27
19
9
8
13
6
2
17
16
65
12
3
16
20
13
29
17
41
23
12
3
15
34
37
8
4
4
12
36
12
17
13
16
31
16
8
33
22
15
8
6
53
52
28
9
3
26
28
20
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
3
3
2
3
4
2
2
2
2
2
4
3
2
3
2
3
3
4
2
1
2
2
2
2
3
1
2
2
2
3
2
4
3
3
3
2
2
2
3
2
5
2
4
4
4
4
27
35
55
56
61
71
44
68
29
28
51
60
44
54
66
60
47
73
45
73
30
24
65
29
54
70
55
32
25
39
70
52
45
49
16
24
60
61
85
16
47
61
16
55
45
41
29
27
30
0
23
22
25
11
25
22
36
62
13
4
50
55
6
42
17
21
31
20
0
26
20
28
43
52
59
10
17
45
17
21
15
18
3
13
12
24
25
44
29
6
9
8
24
17
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
2
2
2
2
1
2
1
1
1
1
4
4
5
3
5
4
4
3
3
2
2
2
2
4
3
2
4
4
3
3
4
4
5
5
4
4
4
4
4
4
4
5
4
4
5
4
4
4
4
3
5
4
3
4
3
5
3
56
45
51
37
37
45
50
40
39
80
48
73
50
51
77
37
48
44
61
43
31
52
34
43
45
48
37
32
35
23
64
32
31
43
52
46
55
29
41
37
25
48
38
59
85
38
27
29
17
23
23
9
8
27
41
0
39
0
24
41
12
45
11
4
12
56
32
30
12
23
16
9
21
9
35
17
0
1
4
8
33
13
39
15
18
3
9
20
0
28
13
19
2
0
1
1
1
1
1
1
1
1
1
2
2
2
2
1
1
2
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
4
3
3
4
1
3
2
3
1
2
2
4
2
2
2
2
2
3
2
4
2
2
2
3
3
3
2
3
3
3
2
3
2
3
4
3
4
4
4
2
3
2
4
3
3
2
55
34
51
63
17
50
42
58
56
76
66
55
59
63
75
64
74
73
70
58
57
16
26
80
70
65
67
66
45
63
15
75
59
35
52
45
16
31
31
19
56
63
85
41
20
54
79
8
4
15
50
4
26
14
37
49
35
44
16
17
45
37
26
18
47
61
29
10
10
2
40
41
41
26
25
15
28
33
46
59
2
27
13
6
22
9
3
30
28
17
8
27
2
49
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
2
2
2
1
1
2
2
4
5
3
4
4
3
4
3
3
1
2
2
2
3
2
2
2
3
5
2
3
5
5
3
4
4
4
4
4
4
4
4
5
3
3
3
3
3
2
2
2
3
4
4
4
4
3
28
56
66
38
37
30
39
17
48
50
50
20
54
85
65
33
80
16
46
64
59
43
28
57
23
29
28
29
41
29
40
58
46
38
47
42
62
18
80
55
57
78
57
41
33
64
61
9
3
24
2
8
2
8
22
21
14
20
24
0
38
50
27
8
0
36
45
20
38
7
0
28
29
36
0
16
30
10
13
7
10
4
18
17
18
51
30
6
15
33
26
51
38
4
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
5
4
4
4
3
3
3
2
3
4
4
4
4
4
4
4
4
4
5
4
4
4
4
5
5
3
4
4
4
4
4
4
4
4
4
4
4
4
5
3
4
4
4
4
3
3
5
41
57
45
50
42
51
16
61
44
58
32
42
45
48
34
30
35
45
37
46
62
30
26
39
49
44
29
42
38
29
37
50
40
25
46
57
50
63
57
23
56
36
64
41
39
43
31
6
9
14
20
19
13
20
57
7
8
64
44
6
19
0
2
23
35
17
13
26
6
16
36
6
33
51
24
0
11
44
15
16
13
21
18
13
61
53
17
12
28
3
24
0
17
6
1
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
3
4
4
4
4
3
3
4
3
1
2
4
3
3
2
4
2
4
2
3
4
2
4
3
3
2
2
3
3
2
1
2
2
4
1
3
3
2
3
2
2
2
2
3
3
2
25
53
58
57
23
30
54
61
17
64
33
39
32
55
31
53
51
53
26
65
57
32
38
43
38
16
59
72
17
34
55
63
75
59
80
80
85
17
72
68
71
75
17
19
65
75
54
35
23
18
33
16
11
5
8
14
36
7
5
47
18
23
10
3
2
4
2
22
6
22
0
1
38
7
30
26
13
25
13
48
58
42
43
10
18
27
31
31
25
34
16
43
38
7
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
2
1
3
2
3
3
2
2
2
5
5
5
4
4
5
3
3
2
2
2
3
3
4
3
4
4
5
5
5
5
4
4
4
5
5
5
4
4
4
5
4
4
74
54
74
41
61
65
59
53
58
72
24
43
23
66
48
36
41
59
45
43
29
51
71
19
80
62
16
49
80
25
51
37
49
39
38
31
65
41
32
56
54
60
34
60
28
43
23
21
44
24
55
45
55
14
50
81
51
13
18
1
63
16
10
10
11
8
0
5
4
23
23
21
25
25
6
44
7
29
21
4
18
8
24
13
0
27
13
13
0
11
17
20
21
21
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
1
1
1
1
1
1
1
2
2
2
2
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
4
4
3
5
3
4
4
5
4
3
4
2
3
2
3
4
1
3
1
4
2
3
2
2
3
4
3
4
4
5
4
5
1
4
5
4
4
4
4
4
4
3
3
4
3
42
61
26
55
20
42
17
20
17
46
46
37
43
49
45
71
57
41
60
15
75
50
45
79
85
78
33
72
57
18
52
46
22
42
46
41
42
59
46
56
43
41
32
28
45
40
36
0
22
10
24
15
3
0
36
22
18
27
13
31
3
33
31
50
15
32
0
33
8
10
42
35
35
6
7
22
35
25
10
16
1
13
5
0
23
0
38
7
12
15
15
27
0
14
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
3
2
3
2
3
2
3
2
3
3
3
3
4
4
4
2
2
4
4
4
5
5
4
5
4
4
4
4
4
5
4
4
4
3
5
2
3
3
4
4
4
3
4
3
3
2
57
17
70
31
75
50
18
32
80
79
63
78
39
71
27
16
20
80
31
30
33
36
35
33
40
23
30
39
45
34
44
40
54
48
44
70
47
38
18
40
26
41
17
27
34
46
41
41
44
44
8
28
53
33
40
33
38
59
26
0
43
11
10
27
26
13
28
1
8
3
12
25
8
17
1
16
9
7
10
10
15
58
30
6
24
19
23
59
3
6
29
9
31
18
1
1
2
2
2
2
2
2
2
2
2
2
2
2
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
3
3
3
3
3
2
2
5
4
4
5
4
4
2
3
5
4
4
5
5
4
4
4
5
4
3
5
5
2
5
4
4
4
3
2
3
3
3
2
3
3
4
4
3
3
2
72
58
77
28
65
80
60
85
44
47
57
49
44
42
46
80
41
47
61
59
53
42
40
52
33
44
38
57
45
52
44
62
42
40
43
52
30
32
53
36
80
80
38
30
76
85
63
43
31
38
3
12
15
36
25
6
13
15
8
26
0
39
24
3
19
27
17
16
7
2
29
13
11
17
17
10
4
20
19
33
26
44
35
16
5
33
13
11
20
9
11
20
61
59
2
2
2
1
2
2
2
2
1
1
1
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
4
5
3
5
3
4
3
2
4
4
3
4
4
4
4
4
5
4
5
4
4
4
5
5
3
5
4
4
5
3
4
4
2
3
3
4
4
5
4
3
3
4
3
3
4
3
4
54
66
18
37
29
17
28
66
45
36
25
22
44
53
28
28
50
46
28
39
34
37
53
55
40
60
33
38
77
59
62
56
47
28
65
48
37
43
28
48
32
31
51
25
45
62
39
6
29
2
0
24
28
23
2
39
0
21
20
5
10
6
28
34
25
8
3
23
17
22
13
12
4
31
33
38
1
14
19
0
15
35
52
23
9
0
13
21
14
11
11
17
17
10
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
3
3
3
3
2
3
4
2
2
3
2
2
2
2
2
2
2
2
2
2
2
2
3
2
2
2
2
3
3
3
3
2
2
2
2
2
2
2
3
2
3
2
2
4
3
2
55
59
51
46
44
29
56
24
72
42
53
43
65
48
22
47
69
80
15
28
26
60
72
73
44
80
71
32
64
69
47
75
69
69
73
67
69
55
70
66
43
15
80
26
80
68
85
38
48
20
11
14
14
18
9
14
13
38
13
62
28
16
18
24
33
13
20
1
78
36
20
41
55
24
34
60
51
26
4
21
20
46
38
36
8
39
21
30
12
23
39
21
27
16
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
4
5
3
3
4
2
5
4
3
4
2
4
5
4
3
4
4
4
2
2
3
3
3
2
3
5
5
4
2
3
5
4
4
4
4
4
4
4
2
3
3
4
5
5
4
4
53
49
52
55
53
33
80
55
33
48
26
16
39
33
55
28
67
47
43
42
38
64
56
20
80
53
28
39
50
65
25
35
39
34
56
35
41
25
44
30
43
33
75
39
62
29
62
28
27
4
0
18
13
45
9
33
16
12
44
10
0
10
22
6
11
32
2
15
28
13
13
51
37
21
13
27
26
13
9
23
16
10
6
7
15
21
38
2
11
17
6
22
16
13
2
1
1
1
1
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
2
2
2
2
2
2
1
1
1
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
2
3
4
2
4
3
2
3
2
2
5
4
3
4
2
4
4
4
5
3
2
2
3
2
2
3
4
4
4
4
5
4
4
4
4
3
5
4
5
4
4
4
5
4
4
4
58
57
47
36
33
62
41
66
63
63
63
50
43
35
21
78
60
33
45
53
16
47
41
53
22
62
85
47
45
80
35
42
16
78
29
45
57
54
28
39
43
35
52
32
43
57
53
5
29
5
35
10
29
0
24
24
58
14
22
25
16
13
46
42
11
13
7
15
45
20
29
50
35
34
8
21
18
7
24
50
44
35
3
9
6
6
6
21
9
3
30
19
19
25
1
1
1
1
2
2
2
2
2
2
2
1
1
1
1
2
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
4
4
5
4
4
2
3
4
4
2
5
4
2
3
3
5
3
2
2
1
3
3
2
2
4
3
2
3
4
3
4
4
4
4
3
5
2
2
2
2
1
4
4
4
4
4
4
30
47
29
31
55
47
24
30
67
57
49
17
38
36
64
55
38
78
85
29
75
17
74
80
35
40
43
50
36
48
40
42
26
51
32
36
80
80
73
80
85
38
41
63
55
40
41
6
12
10
33
18
14
1
20
12
8
21
8
13
14
23
26
15
64
31
54
10
0
48
31
8
21
25
6
13
7
4
54
24
14
42
0
39
43
37
36
10
0
5
4
10
8
15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
1
2
2
1
1
1
1
1
1
1
1
1
2
2
2
2
2
1
1
1
1
1
1
3
2
3
2
2
3
4
4
2
4
4
4
4
5
4
4
4
4
5
4
3
4
4
3
4
3
5
4
4
4
4
4
2
2
4
3
2
2
3
2
4
3
3
2
3
2
4
37
68
47
80
57
80
37
64
73
42
63
50
49
40
45
20
33
40
48
23
46
50
54
54
26
42
63
32
52
28
39
30
49
25
58
22
79
79
80
28
25
34
67
78
51
74
36
24
31
48
28
48
22
6
46
39
14
28
31
19
6
19
30
19
4
14
23
9
14
12
15
39
17
6
0
24
0
7
25
34
4
16
19
45
22
41
22
18
8
0
22
30
9
68
1
2
2
2
2
2
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2

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

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