ECON 306 Penn State University US National Health Interview Survey Discussion

Stock/Watson – Introduction to Econometrics 4th EditionDocumentation for Earnings_and_Height
These data are taken from the US National Health Interview Survey for 1994. They are a
subset of the data used in Anne Case and Christina Paxson’s paper “Stature and Status:
Height, Ability, and Labor Market Outcomes,” Journal of Political Economy, 2008,
116(3): 499-532, and were graciously supplied by the authors for empirical exercises in
the Stock-Watson textbook.
The dataset contains information on 17,870 workers. The table on the next page
describes the variables.
©2018 Pearson Education, Inc.
Stock/Watson – Introduction to Econometrics 4th Edition
Variable Name
age
cworker
earnings
educ
height
mrd
occupation
race
region
sex
weight
Description
Age, in years
Class of Worker:
1 = Private company Employee
2 = Federal Government Employee
3 = State Government Employee
4 = Local Government Employee
5 = Incorporated Business Employee
6 = Self Employed
annual labor earnings, expressed in $2012 (see Table notes)
years of education
height without shoes (in inches)
Marital Status
1 = Married, Spouse in household
2 = Married, Spouse not in household
3 = Widowed
4 = Divorced
5 = Separated
6 = Never Married
Occupations in 15 categories:
1 = Exec/Manager
2 = Professionals
3 = Technicians
4 = Sales
5 = Administrat
6 = Household service
7 = Protective service
8 = Other Service
9 = Farming
10 = Mechanics
11 = Construction/Mining
12 = Precision production
13 = Machine Operator
14 = Transport
15 = Laborer
race/ethnicity
1 = non-Hispanic white
2 = non-Hispanic black
3 = Hispanic
4 = other
Region of the U.S.
1 = Northeast
2 = Midwest
3 = South
4 = West
Sex, 1=Male, 0 = Female
weight without shoes (in pounds)
Notes: In the survey, labor earnings are reported in 23 brackets (for example, $26,000-$30,00). For each of
these brackets Professors Case and Paxson estimated a value of average earnings based on information in
the Current Population, and these average values were assigned to all workers with incomes in the
corresponding bracket. The earnings values for 1994 were converted to $2012 using the consumer price
index.
©2018 Pearson Education, Inc.
Stock/Watson – Introduction to Econometrics 4th Edition
©2018 Pearson Education, Inc.
Name:
Email ID:
@psu.edu
Worked with these other students:
ECON306 Problem Set 3
INSTRUCTIONS: Solve the following questions to the best of your ability. Ask me if
you do not know how to solve any of these questions before the due date. I will work with
you if you are having trouble solving these.
To receive full credit for this assignment, the problem set needs to be submitted to Canvas
in a single PDF document containing your 1) Stata log file in a .pdf file and 2) any
written explanations and answers. All of these components need to be attached together in
that order. Late submissions will NOT be accepted. DO NOT email! No assignments will be
accepted via email.
ECON 306 Problem Set 3, Fall 2022
Page 2
First of all, for this problem set, you will have to submit the Stata log file. Stata can
record your session into a file called a log file but does not start a log automatically; you must
tell Stata to record your session. By default, the resulting log file contains what you type
and what Stata produces in response, recorded in a format called Stata Markup and Control
Language (SMCL). The file can be printed or converted to plain text for incorporation
into documents you create with your word processor. You can find more information here:
https://www.stata.com/manuals13/u15.pdf.
So, in the beginning of your Stata .do file write the following command: log using PSX,
replace (or a different file name). Then, at the very end of your .do file, include log close and
then on a new line translate PSX.smcl PSX.pdf. This would translate your Stata SMCL log
files directly into PDF files and then use Adobe Acrobat to merge PDF files together. You
will need to turn in this log file to receive full credit for this assignment.
Please compile the log file in Stata after you have completed all of your code and
can run it smoothly without any errors. In that way, your log file would not contain
any lines of code that do not produce any results or any duplicate results. Please do your
best to include comments in your code (using the ∗ sign in your Stata .do file) and to make
the solutions to the different problems as clearly marked as possible. Otherwise, the graders
might have to penalize you, if they cannot follow your work. And then I will have to re-grade
your work and the whole process becomes highly inefficient.
More Fun with Earnings and Height
Using the same data as the EarningsHeight.dta from problem set 2, we will perform multiple
regression with dummy variables included. We will also explore 2 cases of omitted variable
bias.
1
Actual OVB
We have seen previously that taller peole earn more money. One potential explanation for this
is that there is an omitted variable! What if height is correlated with an omitted factor that
affects earnings? Perhaps cognitive ability is the omitted factor. How, you ask? Imagine that
poor nutrition and harmful environmental factors in utero and in early childhood negatively
affect both cognitive and physical development. Cognitive ability affects earnings later in
life but is not captured in the model.
a) Would the coefficient on height from earningsi = β0 + β1 heighti + ui be biased upward
or downward? Why?
b) While we do not have a direct measure of cognitive ability in the data set, we do have a
variable that measures education (educ) and that is likely correlated with cognitive ability
because in our society, people with higher cognitive ability are more likely to attend school
longer. If education perfectly captures cognitive ability, then this would eliminate the
omitted variable bias. If education is highly correlated with cognitive ability, then this
will reduce the size of the bias from the omitted cognitive ability. Run the regression in
part a) then comment on how the results change when you add educ to the specification.
ECON 306 Problem Set 3, Fall 2022
2
Page 3
Region Dummies
Generate dummy variables for region. There are a few ways you can do this in Stata. The
most obvious, brute force, way is to do something like:
generate northeast = 0
replace northeast = 1 if region==1
…and so on for all regions
Another option which works better when 1) there are a lot of categorizations and 2)
they’re labeled from the outset is to let Stata automatically generate all the dummies for
you. Try:
tabulate region, generate(dummy region)
You’ll notice that the numbers 1-4 are appended to the variable name. You will want to
rename these variables for clarity. For example:
rename dummy region1 northeast
and so on for all the regions.
3
Regression with Region Dummies
Include the dummy variables for region into the specification from part 1b), using South as
the reference group.
4
Comparing Regions
a) In which region of the country are earnings the lowest? Explain.
b) How much higher earnings can someone expect to make in the Northeast compared to
the Midwest? Show your work.
5
Lots of Variables
Create dummy variables for race. Also create a dummy variable called “male” then run
a regression with dummies for region, race, and sex. This time, using Northeast as the
reference group for region, other as the reference group for race, and female as the reference
group for sex.
ECON 306 Problem Set 3, Fall 2022
6
Page 4
Artificial OVB
Non-hispanic black earners are more likely to be found in the South region. Comment on
the bias this would cause if you did not have race data to include in the model.
7
Differential Effect of Education for Males
Beginning with the regression in part 5, check if an additional year of education has a different
effect on earnings for males.
8
F test in Stata
You should have 3 coefficients that are not statisticaly significant. Perform an F test in Stata
where all 3 of those coefficients are set to 0. Interpret your results.
9
F test by hand
If you couldn’t use Stata to perform the F-test in the previous question, you would need to
perform the F-test by hand. There are a couple different ways to perform the calculation of
your F-statistic but you only need to do it one way.
10
Save Data
Save these data separately from the EarningsHeight.dta that you used for Problem Set 2.
Name it EarningsHeight PS3.dta.
sex
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
age
48
41
26
37
35
25
29
44
50
38
30
29
26
50
65
45
26
57
40
36
60
32
33
27
52
36
53
29
35
46
47
34
34
57
50
41
29
35
58
29
42
34
32
38
36
50
mrd
1
6
1
1
6
6
1
4
6
1
1
4
1
1
4
6
6
4
4
1
1
1
1
1
5
1
4
6
1
1
4
4
4
4
1
1
1
2
1
1
1
1
1
1
4
1
educ
13
12
16
16
16
15
16
18
14
12
12
18
16
12
16
17
16
12
16
12
15
12
12
16
13
12
18
16
11
18
10
13
17
12
16
15
13
11
11
15
8
12
13
16
16
13
cworker
1
1
1
1
1
1
1
3
2
4
1
2
1
1
4
2
1
2
1
1
4
1
1
1
2
4
4
1
1
4
1
6
4
1
6
1
6
1
1
1
4
1
1
1
1
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
29
46
58
43
45
29
54
42
43
31
54
59
59
50
39
35
37
55
46
63
54
48
32
31
27
43
47
34
48
33
40
31
39
28
40
38
58
34
43
35
31
38
29
56
28
31
41
6
4
1
4
4
1
3
1
1
3
1
1
1
1
1
1
1
1
6
4
4
1
6
1
1
1
1
4
1
1
6
4
1
6
1
1
1
4
4
1
1
1
4
4
6
1
4
18
16
12
12
15
12
16
16
12
12
12
16
15
12
12
16
16
13
17
18
18
18
16
14
16
13
12
13
16
16
17
13
14
14
15
14
13
15
13
14
16
18
16
16
18
16
13
1
1
4
1
1
1
1
1
1
1
1
1
6
1
2
1
1
1
4
4
1
2
1
1
1
1
1
1
1
1
4
3
1
3
1
1
4
1
2
1
1
3
1
3
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
36
41
46
55
50
58
45
41
31
41
65
36
42
33
54
39
57
49
53
35
36
29
41
44
59
32
46
31
40
41
34
29
39
32
41
43
29
31
43
32
60
35
55
26
37
37
59
1
6
1
1
1
3
1
4
6
1
4
1
4
1
1
1
1
6
1
6
1
6
1
1
3
1
1
6
1
1
5
1
1
1
4
1
1
6
1
1
1
1
1
1
1
1
3
17
15
12
17
14
12
14
12
11
12
18
16
14
12
16
16
12
16
10
18
16
18
16
16
14
14
14
16
16
18
12
15
14
12
16
14
13
12
14
16
13
16
12
12
13
16
12
1
1
1
1
1
4
2
1
1
1
1
1
4
6
3
1
1
4
4
1
4
2
1
1
1
6
1
1
1
6
1
1
1
1
1
1
1
1
1
1
2
1
1
3
6
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
49
34
38
33
52
49
37
47
44
38
35
26
60
47
27
45
53
32
43
36
30
33
45
34
42
44
25
42
43
46
30
38
34
35
33
52
37
33
38
31
46
39
26
32
43
33
47
1
1
1
1
6
1
4
1
6
6
1
6
1
1
1
1
4
1
6
4
1
1
1
1
5
3
1
1
4
4
6
6
5
4
4
1
4
1
1
1
1
4
4
1
1
6
1
18
13
12
14
18
12
12
15
13
16
17
16
12
13
15
12
14
12
12
14
14
13
16
16
18
12
16
13
14
12
16
18
16
12
17
16
12
15
16
15
14
12
12
16
16
16
18
1
1
3
1
4
1
1
1
2
1
4
1
3
1
5
1
1
3
1
1
1
1
1
1
1
1
3
6
5
2
1
1
1
1
1
1
1
1
2
1
2
4
1
1
1
1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
28
43
38
57
46
47
36
41
33
32
33
41
33
49
45
34
46
49
48
28
38
28
42
39
51
39
53
28
41
34
32
47
65
41
30
26
29
27
29
37
32
38
35
46
43
34
1
6
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
6
1
1
4
1
6
6
4
6
1
3
3
1
6
6
1
1
1
1
6
1
1
1
1
1
13
16
16
15
18
14
12
16
18
16
14
12
12
13
15
11
12
16
18
13
15
15
14
16
14
18
14
14
14
12
16
12
15
16
14
16
15
16
16
16
18
10
14
16
16
13
18
2
1
1
1
4
1
6
1
4
4
1
1
1
1
1
1
6
3
3
6
1
5
1
3
4
4
1
1
2
1
1
1
1
4
1
1
1
1
1
2
1
4
1
1
4
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
37
47
46
49
27
38
48
41
25
42
44
59
35
55
34
27
49
59
39
54
50
37
34
44
27
36
31
44
29
43
29
37
26
46
54
30
26
50
41
48
25
35
36
49
56
37
44
1
4
4
4
1
1
4
4
6
1
1
4
6
6
1
1
4
3
1
4
1
6
1
1
1
6
1
1
6
1
1
1
1
1
1
1
1
1
4
1
6
1
1
1
1
1
5
14
13
16
18
12
12
14
18
16
18
18
13
16
16
18
16
12
11
14
14
18
16
15
18
13
16
12
12
18
16
14
15
17
12
13
17
18
10
5
12
14
12
14
12
18
13
12
1
1
1
1
1
1
1
3
1
1
1
3
1
3
1
1
1
1
1
1
3
1
1
1
1
1
1
1
3
1
1
1
1
1
1
2
1
6
1
1
1
1
5
1
5
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
46
45
48
46
53
43
31
27
54
30
42
43
55
25
49
39
40
41
33
28
54
31
52
40
34
38
33
32
42
37
46
26
32
37
41
27
25
56
50
54
29
30
38
34
42
33
51
1
1
1
1
1
1
1
6
4
1
4
1
6
1
1
1
1
1
6
1
4
1
1
1
6
1
1
6
4
4
1
6
6
1
4
6
1
1
1
6
6
4
5
1
4
4
1
13
16
15
12
18
16
12
18
14
14
14
16
17
12
16
13
8
12
16
12
12
12
12
13
17
14
15
16
16
16
12
16
10
12
12
18
16
15
18
16
16
15
16
14
14
12
16
1
2
1
1
4
2
1
4
1
1
6
1
2
1
1
3
1
1
1
1
1
1
1
1
6
1
1
1
1
1
4
1
1
4
1
1
1
2
1
1
1
2
1
1
4
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
32
57
39
51
39
30
33
45
38
48
45
54
27
44
56
44
36
35
35
56
30
36
42
29
54
47
42
46
58
52
54
36
30
28
30
49
36
30
34
42
40
46
32
47
29
51
1
1
3
1
1
1
1
1
1
6
1
1
3
6
1
1
4
6
6
1
1
4
4
6
1
1
1
1
1
1
1
1
4
6
5
6
1
5
6
2
6
1
1
1
4
1
1
12
12
15
18
12
12
13
16
10
16
16
16
14
13
12
12
13
12
16
12
16
13
13
16
16
18
18
14
16
17
15
16
13
16
12
18
13
9
16
18
16
14
12
16
16
14
11
1
2
1
1
1
1
1
1
1
1
2
5
1
1
1
4
2
1
1
1
1
1
4
4
1
3
1
1
4
3
1
1
6
2
1
4
1
1
1
1
1
4
6
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
41
38
42
36
38
30
55
25
36
34
60
26
33
27
31
54
40
44
58
28
36
32
33
32
48
36
49
39
47
32
39
62
25
27
51
62
39
42
29
38
37
32
41
39
35
31
4
4
1
1
1
1
2
1
6
1
4
1
1
1
1
1
4
6
1
6
6
4
1
3
1
1
1
1
1
1
1
1
3
6
6
4
4
1
1
1
1
5
1
1
4
4
1
16
14
14
12
13
14
18
12
16
18
14
16
12
14
12
12
10
16
16
14
16
12
14
16
16
12
16
12
12
16
16
12
16
18
16
14
12
17
14
16
16
12
12
12
18
16
13
1
1
6
1
1
2
3
3
3
1
1
4
3
1
1
1
1
1
1
1
2
1
6
1
1
2
1
6
1
1
1
4
1
1
1
2
1
3
1
1
4
1
1
6
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
60
41
57
25
35
49
49
36
31
48
42
44
27
37
25
41
44
38
58
46
56
26
52
60
55
46
40
37
59
28
56
35
28
35
49
34
59
35
47
38
37
41
36
46
26
35
50
3
4
1
1
1
4
3
1
6
1
6
1
1
1
6
1
4
1
1
4
1
1
1
1
4
6
1
6
1
6
4
1
1
6
1
1
1
1
1
1
6
1
1
1
1
1
1
14
13
13
13
12
16
13
16
17
16
18
18
12
16
16
12
12
12
12
12
12
16
12
14
12
17
12
12
12
18
12
12
14
16
12
12
14
16
12
14
16
13
12
12
16
13
13
1
1
4
1
4
1
1
5
1
4
1
1
1
1
1
1
1
1
4
1
4
1
1
4
4
4
4
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
4
1
1
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
38
57
44
55
44
37
58
48
25
54
40
31
33
46
42
36
48
45
31
32
26
30
50
34
39
47
39
26
53
46
48
44
45
43
62
62
49
51
50
51
36
32
53
35
44
38
43
1
1
1
1
1
6
4
4
4
4
1
1
1
1
1
1
1
1
1
1
1
1
5
1
2
6
5
1
4
1
1
1
4
1
3
1
2
6
5
1
6
6
4
1
4
1
6
13
18
13
18
16
18
18
13
16
12
14
12
13
13
13
18
12
16
12
16
13
16
17
15
12
15
15
13
16
16
12
16
14
12
12
12
12
18
14
13
14
13
13
16
18
17
14
1
4
1
4
6
1
4
1
1
1
1
1
1
3
3
1
1
2
4
1
1
1
1
1
1
1
1
1
3
2
4
3
3
1
1
1
2
1
1
1
1
1
1
1
3
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
57
46
47
42
25
37
32
60
28
40
49
61
27
35
33
33
38
46
26
59
32
32
44
62
32
26
50
33
31
47
48
34
26
60
32
25
48
30
27
33
25
37
40
44
42
39
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
2
5
6
6
4
1
1
1
5
1
6
1
1
6
1
4
1
1
1
1
1
1
6
1
3
1
4
4
16
17
13
18
13
12
13
16
14
17
16
12
12
16
12
17
12
12
12
15
16
14
12
12
14
12
14
14
16
12
14
14
12
14
14
12
12
14
16
16
16
16
13
15
12
14
12
1
1
5
1
1
4
1
1
2
1
2
1
1
1
1
1
1
1
1
5
1
1
1
3
1
1
1
1
1
1
6
1
2
1
1
1
1
1
1
1
1
1
1
1
2
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
50
47
26
37
40
45
39
28
25
53
35
48
53
37
46
30
35
39
37
28
36
30
58
41
32
47
28
29
34
27
58
47
34
25
61
27
45
52
42
59
46
45
49
26
31
47
27
1
4
1
1
4
1
4
1
1
4
1
4
1
1
1
1
1
4
1
1
1
4
6
1
6
6
1
4
4
6
4
4
1
1
1
1
1
4
1
1
1
1
1
6
6
1
4
13
17
16
12
16
13
14
11
12
12
13
13
13
13
16
17
15
16
16
14
16
16
17
16
16
16
13
16
12
13
16
14
12
15
16
14
14
12
12
16
13
16
16
12
16
12
12
6
1
1
1
1
1
1
1
1
6
1
3
2
1
3
4
1
1
1
1
6
4
1
1
2
4
1
1
1
1
5
4
1
3
6
1
1
1
1
1
1
2
5
1
1
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
38
29
44
28
34
52
55
54
29
34
25
36
52
46
28
41
29
38
40
60
25
43
47
45
49
48
50
26
38
49
35
48
36
46
41
42
25
53
31
46
60
26
25
29
30
27
41
4
6
1
1
1
4
1
1
1
1
6
1
1
1
1
6
1
1
4
3
1
1
1
1
4
1
3
1
4
1
1
1
1
1
1
1
6
1
1
1
1
6
6
6
1
4
1
14
12
11
14
16
13
12
12
16
15
16
13
12
13
14
14
16
12
18
12
12
14
15
17
17
14
12
18
16
13
14
13
18
17
17
13
16
16
12
16
12
14
16
17
12
14
14
2
4
1
1
1
1
1
2
1
3
1
1
2
1
1
1
1
1
5
1
1
1
3
1
1
1
1
1
1
3
1
3
1
1
1
2
1
1
1
1
1
5
1
6
1
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
53
37
50
33
49
32
25
34
54
27
62
31
29
40
44
28
27
49
58
50
31
25
36
31
31
38
43
30
30
39
40
29
28
38
55
32
43
48
37
44
47
57
49
26
46
51
32
1
1
4
1
1
1
1
1
1
6
1
6
1
4
5
1
1
4
4
4
1
6
1
2
1
1
4
6
6
6
4
1
4
4
1
1
3
6
4
1
1
1
1
1
1
1
1
12
16
18
14
12
16
14
16
16
16
16
17
13
17
12
17
16
14
12
12
13
16
16
16
12
12
15
16
16
18
18
12
12
13
13
14
15
12
12
12
16
12
18
16
18
16
16
1
1
4
1
2
4
1
6
1
1
2
1
6
1
1
1
1
1
2
1
1
1
4
1
1
3
6
1
1
1
3
1
1
1
1
2
1
1
1
1
2
3
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
37
40
43
39
29
36
36
41
28
44
30
37
44
61
47
35
35
28
40
33
48
32
42
52
44
47
39
44
39
34
43
37
37
44
48
37
37
34
52
36
35
30
31
37
44
30
34
1
1
1
1
4
4
5
4
1
4
1
1
4
1
1
1
1
1
1
1
1
6
1
4
1
1
1
1
1
1
4
1
4
1
1
4
1
1
1
1
1
5
6
1
1
1
1
16
15
14
16
12
16
18
12
16
16
12
17
15
12
16
13
12
16
14
16
14
12
14
14
16
14
16
14
12
12
19
16
18
12
12
17
12
16
16
18
18
16
17
14
12
12
14
3
1
1
1
1
1
1
1
3
3
1
1
4
5
1
1
2
1
1
1
4
4
1
1
1
6
1
2
1
1
1
3
3
1
1
1
1
2
1
1
5
1
1
6
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34
52
60
43
29
46
34
36
43
42
36
25
36
39
62
36
47
50
40
47
59
46
50
60
25
31
45
57
57
39
46
46
36
43
52
45
37
26
26
29
33
27
46
41
43
55
52
1
1
3
1
1
4
1
1
4
1
1
1
1
1
3
1
1
6
1
1
6
4
1
4
1
6
6
1
1
1
1
1
4
1
3
4
1
6
1
1
5
1
1
1
6
1
4
12
16
13
12
16
14
16
18
12
14
16
15
12
15
12
12
14
17
14
14
12
18
12
12
13
18
16
2
12
13
16
16
16
18
12
16
16
2
17
14
12
14
12
12
18
14
14
1
1
1
1
1
1
1
1
1
4
1
1
1
1
6
1
1
2
1
6
1
1
2
1
1
2
1
6
1
3
1
1
1
3
1
2
3
4
1
1
1
1
1
1
1
3
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
52
42
46
49
37
41
51
27
56
60
37
56
55
26
34
42
59
46
52
36
37
43
49
34
51
39
30
34
30
61
48
41
39
39
46
28
48
58
29
34
39
26
57
29
59
33
39
1
1
1
1
4
3
1
4
1
4
1
4
4
6
1
1
4
1
1
1
4
4
4
1
4
4
5
2
1
3
4
1
4
1
1
4
1
1
1
6
1
1
1
1
1
1
1
15
12
9
16
12
17
17
12
11
18
14
12
15
16
12
17
15
12
12
12
17
14
16
16
18
16
12
14
16
13
14
16
18
14
16
16
12
13
12
16
16
14
12
16
12
16
15
1
1
1
1
1
1
2
1
1
4
1
2
1
1
1
4
4
1
3
1
1
2
3
2
4
1
1
2
1
3
1
4
1
1
1
1
4
1
6
3
1
1
1
1
6
6
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
55
35
41
37
46
38
53
45
43
53
54
35
32
27
28
36
48
47
32
41
38
50
47
46
33
47
38
44
25
49
39
41
41
41
29
34
42
45
43
38
51
36
63
50
33
33
4
1
2
1
1
1
1
4
1
6
6
3
4
6
6
1
1
3
4
1
1
1
4
1
1
1
4
4
1
6
1
6
1
1
1
1
1
1
1
1
1
4
1
6
1
1
1
17
12
12
16
18
16
18
17
12
15
12
15
12
18
16
12
16
16
18
16
12
16
18
12
12
16
16
15
18
16
12
16
16
18
16
13
13
18
12
16
12
14
12
18
9
16
12
3
3
3
1
3
1
3
1
1
6
1
1
1
1
1
5
1
1
1
1
1
1
2
3
4
1
1
3
4
1
1
1
1
1
4
2
1
4
1
5
1
1
1
4
6
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
33
30
47
36
44
35
46
44
33
28
39
31
45
26
27
33
34
44
50
40
26
50
28
36
35
32
48
61
28
34
45
44
40
36
33
27
33
38
43
25
38
26
36
46
65
28
4
1
6
1
1
4
1
1
1
1
6
6
1
1
1
1
1
6
1
1
1
1
6
1
4
6
1
1
1
5
1
4
3
4
1
5
1
6
6
1
6
1
6
1
1
3
5
13
14
12
14
16
12
12
14
12
15
17
17
12
12
15
12
14
14
16
12
17
11
14
12
14
14
15
12
18
12
12
16
14
13
16
13
11
15
17
16
16
17
16
18
16
14
11
2
4
2
3
1
1
1
1
6
1
3
3
1
4
3
1
1
3
6
1
1
1
2
1
2
1
1
1
4
1
1
1
1
1
1
1
3
1
1
2
3
3
1
1
1
3
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
47
39
29
39
35
50
29
30
40
39
54
36
48
46
37
53
48
43
28
34
38
31
47
27
34
40
49
44
34
30
65
52
43
45
44
63
44
63
33
25
45
54
43
28
63
45
32
1
5
6
1
1
1
1
1
1
6
6
6
1
1
1
3
1
1
1
3
4
5
4
1
6
6
4
4
1
1
1
1
1
1
1
1
4
1
1
1
1
1
4
6
1
4
1
12
12
18
16
12
12
18
12
13
16
17
17
13
18
16
16
15
12
16
16
18
16
16
10
16
16
12
18
14
12
16
18
18
18
16
12
13
12
12
14
16
18
13
16
11
17
12
1
1
1
1
1
1
1
1
5
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
4
1
3
1
4
4
1
2
4
1
1
2
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
44
42
36
31
29
40
34
46
52
35
50
42
52
54
28
38
44
41
47
50
42
34
54
39
46
28
28
29
58
27
60
28
36
40
37
46
52
50
34
28
56
40
43
53
34
33
1
1
1
1
4
6
1
4
1
1
4
1
1
1
5
1
1
1
4
4
1
1
1
4
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
6
17
12
12
13
14
16
12
14
18
14
12
13
14
12
16
16
16
14
12
13
16
12
16
13
17
13
12
12
16
12
14
16
16
15
18
12
14
16
18
13
16
12
12
16
18
14
16
1
1
1
1
1
1
1
1
1
1
1
1
2
2
1
1
6
1
1
4
1
1
4
1
1
1
1
1
1
4
1
1
1
1
4
1
4
1
4
1
1
2
1
2
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
56
56
33
37
40
34
31
28
29
52
56
44
55
39
30
39
40
50
35
40
30
35
39
57
31
27
25
33
51
47
54
30
32
33
26
45
50
34
42
54
28
28
27
52
42
39
4
4
3
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
4
1
6
3
1
4
1
4
4
1
1
1
6
4
1
1
6
5
4
1
1
1
1
1
6
4
14
18
12
17
16
16
13
16
17
15
12
13
12
12
16
16
14
16
13
16
13
12
18
14
12
12
16
12
12
14
12
12
16
12
12
16
14
16
12
15
14
12
12
14
18
15
12
1
6
5
3
3
1
1
1
1
1
4
6
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
3
6
1
6
3
1
1
1
5
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
25
48
27
46
47
41
34
44
48
50
50
45
25
37
34
57
39
40
42
30
41
26
31
42
61
33
39
27
51
30
40
37
31
52
39
41
54
47
51
43
36
32
46
35
53
60
4
6
1
1
4
4
1
1
1
1
4
1
1
1
6
1
1
6
6
1
4
1
1
1
5
1
1
1
1
4
1
4
4
1
1
1
1
1
4
1
1
4
1
1
1
1
3
14
14
14
17
12
18
15
12
11
12
12
10
12
16
14
16
8
14
16
12
14
13
12
16
14
16
12
14
16
18
13
12
15
16
12
12
13
18
18
12
16
12
16
12
12
12
12
6
6
1
1
1
3
2
5
1
1
4
6
1
1
3
1
1
1
1
1
1
2
1
1
6
1
6
4
1
3
3
1
3
1
3
1
3
5
1
4
4
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
28
30
47
58
40
25
33
45
65
44
47
35
48
46
52
47
27
46
41
39
31
32
42
54
47
39
42
34
34
64
35
43
30
37
50
42
56
65
30
40
38
37
43
56
54
30
53
1
1
1
1
1
6
6
4
3
6
2
1
1
1
1
1
1
2
4
1
1
1
4
1
4
4
1
1
1
3
5
4
1
4
3
4
4
1
1
1
1
4
1
1
1
4
1
12
16
8
12
16
16
18
17
12
16
14
12
12
16
12
16
13
18
16
16
12
12
13
18
14
14
16
16
12
18
15
12
18
16
18
12
12
12
12
13
18
14
15
10
12
16
12
6
1
6
4
1
3
2
6
2
4
5
3
1
4
6
1
1
1
2
1
3
1
1
3
2
1
1
1
3
1
6
6
1
1
3
1
1
1
1
1
3
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
1
1
1
1
1
1
47
42
61
31
27
48
58
54
37
37
42
36
50
44
35
40
37
41
35
58
32
60
56
52
28
30
37
43
50
27
36
28
41
38
39
38
37
32
32
44
52
50
55
29
47
40
39
1
1
4
1
1
4
5
1
1
6
1
6
1
1
1
6
1
1
6
1
1
1
1
1
6
6
6
1
1
1
6
6
1
4
4
5
4
1
1
6
1
1
4
1
4
1
1
17
17
14
16
14
18
16
16
16
18
18
12
15
18
16
18
15
16
18
12
12
12
14
15
16
14
12
18
16
16
18
16
16
12
13
14
16
16
16
16
12
14
18
16
18
16
14
6
1
1
1
1
1
1
3
1
1
4
1
4
1
3
1
1
1
1
2
5
1
1
4
1
1
5
3
1
1
4
1
1
1
1
1
1
6
1
1
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
1
1
1
1
1
1
42
26
35
51
58
49
26
42
29
29
51
53
39
31
37
53
58
57
50
61
45
35
46
36
34
50
47
40
35
32
26
30
39
26
31
49
30
52
35
31
54
48
30
27
45
36
46
4
6
1
4
6
6
1
1
6
6
1
1
4
6
1
1
1
1
1
1
1
1
4
6
6
1
1
1
1
6
6
6
4
6
1
1
6
1
1
1
1
1
4
1
1
1
1
16
16
16
18
14
16
14
12
16
18
14
12
12
12
17
18
14
16
16
16
16
16
12
17
16
15
16
16
14
16
16
16
16
16
12
17
12
17
18
15
12
16
16
15
18
16
16
2
1
3
2
6
1
1
1
1
1
1
2
3
1
1
3
5
1
1
1
1
4
3
5
1
1
3
1
1
3
1
1
1
1
1
1
1
3
2
1
3
1
1
6
3
1
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
60
49
32
54
42
62
31
25
30
43
64
25
30
61
63
60
47
54
43
54
34
50
40
29
56
39
62
52
31
64
31
51
52
27
58
44
26
42
43
35
59
31
40
49
53
52
40
1
6
6
1
1
1
1
6
2
4
1
6
6
3
1
1
1
4
1
1
1
1
1
6
4
4
1
6
1
6
6
1
2
1
1
1
6
4
1
4
4
1
1
1
1
1
4
18
18
13
18
12
12
14
18
15
14
10
16
16
18
10
15
12
18
16
16
16
12
12
14
14
12
14
18
14
12
15
14
15
16
16
16
12
14
12
14
16
18
16
18
16
16
16
3
1
1
2
4
1
1
1
2
1
2
1
2
3
3
2
4
2
1
2
1
2
1
1
1
5
1
3
6
1
1
1
6
1
1
1
1
1
1
1
1
6
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
37
49
37
29
58
42
29
25
50
28
37
65
31
62
57
35
43
50
39
41
53
43
38
57
44
31
49
59
29
30
31
45
28
38
50
65
34
43
40
33
37
38
30
41
30
36
61
1
1
4
6
1
1
1
6
5
4
1
1
6
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
6
6
6
6
6
1
1
3
4
4
1
1
1
6
6
1
6
1
1
18
18
18
15
12
16
18
11
17
16
12
12
16
18
13
16
14
16
16
18
13
16
14
18
15
15
16
18
12
17
16
16
12
13
18
18
16
16
16
12
18
16
17
14
13
14
18
5
3
1
1
4
3
5
1
6
1
1
1
6
6
6
1
2
5
3
1
2
4
1
6
4
1
2
6
1
1
6
6
1
1
5
6
1
4
1
3
1
1
3
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
1
1
1
36
58
45
28
45
34
51
52
30
33
38
61
55
30
56
50
35
31
47
59
47
32
36
48
27
50
40
42
26
60
46
52
54
33
36
54
51
34
54
53
39
27
56
47
32
58
38
1
1
1
6
1
1
1
1
6
1
1
1
5
1
1
1
5
4
6
1
1
1
1
1
6
1
1
1
6
4
1
1
1
6
4
1
1
1
1
1
6
6
5
4
1
4
6
14
16
16
12
18
16
14
14
14
17
18
15
18
2
18
17
13
12
16
18
16
12
13
4
16
12
16
14
14
15
18
18
18
16
15
18
14
14
17
15
13
14
16
16
13
14
12
1
6
2
1
1
1
2
4
5
1
1
1
6
1
1
4
4
1
3
1
1
6
3
1
1
3
1
2
1
1
1
4
6
1
6
6
1
1
2
2
1
1
6
2
3
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
1
56
43
26
52
59
33
43
44
60
27
47
38
31
35
54
26
41
37
58
53
43
50
57
51
47
63
30
42
30
36
41
35
47
38
56
53
52
49
42
43
59
44
36
39
37
37
53
1
1
6
1
1
4
1
1
1
6
4
1
1
6
1
1
1
1
1
2
1
5
1
1
1
1
1
1
1
6
1
6
1
1
1
1
1
4
1
1
4
1
6
4
6
1
1
18
15
16
16
18
16
12
13
14
16
18
13
16
16
14
16
14
16
18
18
14
18
12
18
15
16
16
18
18
12
18
18
18
16
12
16
18
16
16
18
13
13
16
16
16
16
17
5
6
1
6
4
1
1
4
3
3
1
1
2
3
4
1
4
1
2
3
1
1
1
1
1
4
1
1
1
1
1
3
4
5
1
1
2
1
1
5
6
1
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
1
1
1
1
35
28
27
32
38
30
56
43
29
27
41
49
48
32
25
33
41
48
33
58
57
42
29
34
31
36
65
28
35
37
44
57
45
45
44
38
47
37
42
44
27
40
52
34
47
26
32
1
6
6
1
1
1
3
6
6
1
5
4
1
1
1
1
1
4
6
1
4
6
6
6
1
1
1
6
1
1
1
1
1
1
1
1
4
1
1
1
6
1
1
1
4
4
6
12
13
16
16
14
18
12
12
13
16
16
18
18
17
12
14
16
14
16
6
18
17
16
16
16
14
18
16
12
18
12
12
16
18
16
12
12
12
16
16
16
16
18
14
12
12
16
1
1
1
2
1
5
3
1
1
1
1
1
4
1
1
1
5
1
1
6
6
1
1
1
5
1
6
1
1
6
1
1
1
1
1
1
1
4
1
1
1
1
1
2
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
36
47
48
30
52
30
34
59
56
57
37
48
48
26
31
33
30
32
42
28
46
59
45
38
41
28
40
51
33
29
51
34
26
45
36
56
51
54
27
57
53
54
33
60
47
55
59
4
1
1
1
1
6
4
1
1
1
1
1
1
6
1
1
1
1
4
6
1
1
1
1
4
1
1
1
1
1
1
1
1
4
1
1
1
1
6
1
1
1
6
1
1
1
1
13
16
18
17
13
16
16
13
16
16
18
18
15
16
18
16
16
14
18
17
16
18
18
16
16
15
18
16
14
17
18
16
16
18
12
18
13
16
14
18
17
16
15
15
14
13
17
1
1
1
2
6
1
3
1
5
1
1
2
1
1
1
1
2
1
1
1
1
6
1
5
3
1
1
6
1
1
3
1
1
2
2
3
2
1
1
6
1
5
1
6
1
4
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
1
42
41
26
50
52
42
36
32
29
44
44
48
31
41
42
37
56
57
54
29
30
27
31
63
39
47
33
34
27
59
50
33
60
41
54
50
38
32
33
26
65
48
26
46
50
26
47
1
4
6
1
1
1
6
4
1
1
4
1
6
1
1
1
1
2
1
6
1
6
1
4
6
4
6
1
6
1
1
6
1
6
1
2
2
6
5
6
1
1
6
1
1
6
4
16
16
16
6
12
15
15
16
12
16
16
16
17
18
12
15
14
16
12
16
18
18
11
7
16
15
16
12
16
16
14
16
13
16
15
18
16
14
12
16
15
18
16
16
17
12
18
6
2
1
5
6
2
1
1
5
2
2
2
1
1
6
1
1
1
1
6
1
1
5
6
2
1
1
1
2
1
5
1
1
1
5
6
1
1
4
1
1
3
3
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
36
39
45
36
50
43
59
34
48
52
41
27
38
32
63
37
33
32
33
28
26
39
47
63
37
55
46
29
43
37
62
40
39
37
34
43
36
43
45
42
49
30
46
40
44
43
57
1
1
4
1
1
1
1
1
5
4
1
1
6
6
1
5
6
1
1
6
6
6
1
6
1
6
1
6
4
1
4
4
6
5
5
1
1
1
1
1
1
6
1
1
4
4
1
14
16
16
16
18
14
12
16
18
15
14
16
16
16
12
14
17
12
16
18
16
17
12
17
14
12
13
18
12
16
16
12
14
15
12
16
14
16
18
16
14
16
14
18
16
12
18
1
6
1
1
1
1
1
1
3
3
1
1
1
1
4
4
1
1
1
1
1
2
1
4
2
1
1
1
1
3
1
6
1
6
6
1
1
6
2
1
1
1
4
2
6
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
1
31
58
32
54
27
56
36
47
25
49
35
61
59
30
28
38
47
41
53
29
25
41
60
40
40
49
38
32
40
33
30
65
29
37
26
60
61
31
38
49
33
42
29
39
45
33
26
6
1
1
1
1
4
1
6
1
1
1
1
1
1
6
6
1
1
1
4
1
1
1
1
1
6
1
1
1
1
1
1
6
1
6
1
1
1
6
1
1
1
6
6
1
6
6
10
15
12
16
12
16
16
15
13
17
12
18
13
18
12
18
16
16
12
18
17
12
17
18
16
12
16
16
18
12
12
16
16
18
18
18
14
16
16
16
16
14
16
16
17
18
17
1
3
1
2
1
1
2
1
1
4
1
3
1
5
1
3
2
1
1
5
1
2
3
1
1
1
3
1
1
1
6
1
5
1
1
1
1
1
1
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
1
1
1
1
1
1
1
47
58
37
50
53
57
49
31
42
36
43
50
49
26
49
30
40
27
29
53
46
45
60
50
37
33
40
41
47
37
45
36
39
42
31
53
44
44
41
38
34
58
44
46
50
36
62
5
1
1
1
1
1
1
6
1
1
1
1
1
6
1
6
1
6
1
5
1
1
1
4
1
6
1
1
1
1
1
6
1
1
6
1
1
1
6
1
1
4
1
4
4
1
1
18
18
12
16
12
13
13
16
12
16
15
13
17
16
16
14
16
18
17
18
16
18
18
18
12
12
14
16
18
14
16
18
18
16
12
14
18
18
18
18
16
15
16
11
18
18
14
4
5
1
6
5
1
6
2
5
1
1
6
2
4
4
2
3
1
1
2
6
2
4
4
1
5
1
1
2
1
3
2
1
1
1
1
2
6
1
5
1
1
1
4
6
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
26
34
54
38
52
46
48
39
47
38
50
36
44
48
43
40
38
57
42
54
36
37
53
36
48
35
43
59
39
60
27
43
53
31
40
50
56
53
52
40
38
43
52
32
37
54
51
6
1
4
1
1
1
1
1
4
1
1
1
6
1
1
6
1
1
1
1
4
1
4
1
3
1
4
1
4
1
1
1
5
6
1
1
1
1
1
1
4
1
4
1
1
1
1
17
16
12
16
12
18
14
14
18
17
16
18
16
16
12
12
16
14
12
16
9
16
13
13
17
14
16
18
18
16
12
15
12
16
16
12
17
12
18
18
18
16
14
16
14
16
13
4
1
6
1
5
1
1
1
3
1
6
1
5
4
5
1
5
2
5
1
1
2
3
1
1
1
4
3
1
1
1
3
1
1
6
1
6
1
5
1
1
1
4
1
3
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
36
49
49
31
53
64
49
35
61
28
42
46
45
52
52
32
36
42
34
57
43
28
35
37
44
59
30
28
52
43
51
62
27
29
28
47
36
47
40
47
53
55
29
43
32
30
37
1
1
1
6
2
3
1
1
1
1
1
4
1
1
4
1
1
1
6
1
1
6
1
1
1
1
6
1
1
1
1
1
1
6
1
1
4
1
1
1
1
1
1
4
1
6
4
15
16
18
18
12
16
14
16
14
18
16
18
16
14
14
16
16
12
14
18
18
16
18
18
18
14
12
14
18
16
15
14
16
16
16
14
12
18
18
16
16
18
16
16
16
14
16
4
6
1
1
2
6
4
1
1
1
2
6
2
1
1
1
1
1
1
2
4
1
1
2
6
2
1
1
3
1
1
1
1
1
1
2
1
3
3
1
6
2
3
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
28
44
55
55
50
57
50
60
29
37
62
28
37
47
26
25
37
47
30
41
46
35
36
46
43
35
43
36
56
26
35
40
33
62
55
30
27
36
40
52
41
48
51
45
33
57
54
6
1
1
6
1
1
1
5
1
5
1
6
4
4
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
6
6
1
6
2
4
1
6
1
1
1
1
1
4
1
1
1
1
15
18
14
16
16
12
17
16
17
18
17
15
18
16
10
14
17
18
14
18
18
13
16
16
12
13
15
18
18
16
16
18
18
18
14
17
16
17
17
12
16
12
16
12
12
15
16
1
3
1
3
1
1
6
2
5
4
4
2
1
6
1
1
3
1
3
1
5
1
1
3
6
6
1
1
1
1
1
1
3
4
1
1
1
3
6
1
1
1
3
4
6
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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
63
27
49
53
60
31
33
61
63
48
50
26
32
26
48
27
50
53
41
47
46
56
33
46
58
59
37
36
35
44
41
45
41
34
25
28
29
41
41
39
50
36
25
45
45
34
64
1
1
4
1
1
1
1
1
4
1
1
6
1
1
6
1
1
1
1
1
6
4
6
1
1
1
6
5
1
1
1
1
1
1
1
6
5
1
1
1
1
6
6
1
3
1
1
16
13
13
12
16
16
16
18
16
18
15
16
16
13
17
16
16
16
17
14
16
18
16
17
12
18
18
17
17
16
17
12
18
13
12
17
12
16
17
12
13
18
16
16
16
12
17
1
1
3
3
1
1
6
6
1
4
1
1
1
1
4
1
3
1
4
1
1
4
1
3
1
3
1
1
3
1
4
4
4
6
1
1
1
1
6
4
6
1
1
4
3
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34
46
43
36
55
48
53
28
27
43
55
45
50
31
36
28
47
51
36
40
52
28
35
43
36
27
52
33
43
29
32
40
38
49
41
38
32
61
48
45
52
42
43
25
42
47
60
5
1
1
1
6
1
3
1
1
1
3
1
1
1
1
1
4
1
1
1
4
5
1
4
5
1
1
1
1
1
1
1
1
1
6
1
1
4
1
1
6
1
1
1
4
4
4
16
14
14
16
16
16
16
16
18
14
16
16
17
14
18
18
18
17
13
15
16
16
16
16
12
16
18
16
17
16
16
15
18
15
18
18
17
15
18
16
17
18
17
12
18
18
17
1
4
1
1
4
4
1
1
1
1
1
4
3
4
4
4
4
1
4
1
1
1
1
1
4
4
4
3
3
1
1
1
4
3
4
4
4
1
4
4
4
1
1
4
1
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34
37
39
41
44
47
45
51
40
25
29
49
34
51
54
41
33
35
50
40
51
44
37
64
38
28
51
46
64
49
41
31
50
51
28
45
46
57
50
48
43
35
36
37
57
42
36
1
1
1
1
4
6
1
1
6
1
6
4
1
1
1
1
1
1
4
1
1
6
6
4
1
6
1
1
6
1
1
6
6
5
6
1
1
1
1
1
5
4
1
6
4
1
1
15
18
15
18
16
18
17
18
16
16
18
18
16
16
18
17
16
16
15
18
17
16
16
15
17
16
18
16
17
16
16
17
18
18
12
15
19
18
15
12
15
16
17
16
16
18
16
1
3
1
1
4
4
4
3
1
1
4
1
1
1
3
4
1
1
1
4
4
6
1
1
1
2
4
1
3
1
1
4
4
4
4
1
6
4
1
1
1
4
4
1
1
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
41
31
35
46
37
47
32
37
43
47
31
38
26
61
37
40
29
45
56
42
37
48
32
39
35
32
46
28
34
39
41
57
31
54
45
29
40
58
53
62
61
43
48
26
39
33
46
1
1
1
1
1
6
6
1
1
4
4
1
1
1
1
4
6
4
1
6
1
6
1
1
6
6
1
1
1
1
1
3
1
1
1
1
1
6
4
1
4
1
4
5
6
1
6
16
17
18
16
14
18
16
13
16
15
12
16
16
17
17
15
16
18
18
12
17
16
16
12
18
18
18
16
14
18
17
15
18
16
16
15
17
16
18
18
18
16
14
16
18
16
16
4
4
1
1
1
4
2
1
1
1
3
1
4
4
1
1
1
1
4
1
1
4
4
1
1
1
4
1
1
3
1
1
4
3
3
1
1
1
1
4
4
1
1
4
3
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
36
29
41
48
43
54
42
36
30
50
39
48
60
31
41
45
41
43
55
44
36
33
38
26
38
40
28
36
42
49
34
50
32
47
44
30
37
29
28
37
40
62
33
40
42
42
1
4
1
1
1
1
1
1
4
1
6
1
4
1
6
1
1
6
1
4
6
1
1
1
6
4
1
1
4
1
1
1
1
1
4
1
4
4
6
1
1
1
4
6
1
6
1
14
17
16
18
18
16
16
15
15
13
18
16
14
18
16
14
16
18
17
18
16
13
15
16
14
18
18
16
14
14
18
13
18
16
18
14
15
18
17
16
12
15
18
18
15
16
16
1
1
4
4
4
1
1
1
1
1
3
4
1
1
1
1
4
1
1
1
4
1
1
1
1
4
3
4
3
1
4
2
1
1
2
1
1
4
1
1
1
3
4
1
6
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
43
30
36
55
42
31
45
60
48
48
49
39
47
46
58
43
56
40
36
50
33
41
42
27
37
35
48
47
41
47
27
52
41
51
41
43
46
30
26
54
48
30
37
40
59
41
37
1
1
1
1
1
4
1
1
1
1
1
6
6
1
1
1
4
1
1
1
4
1
1
1
1
6
1
4
1
1
1
4
1
1
1
1
4
1
1
1
4
1
1
4
1
5
6
13
16
16
18
14
17
12
14
18
16
18
18
18
12
12
18
18
16
18
14
15
18
18
14
12
16
18
16
18
16
16
17
18
14
18
16
12
16
14
17
17
17
16
18
12
17
16
3
1
1
6
1
1
1
1
4
3
4
4
4
4
3
1
4
1
3
1
1
4
4
4
6
1
3
4
3
4
4
6
1
1
1
4
1
1
1
1
3
1
1
4
1
3
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
34
49
44
32
50
46
55
30
25
39
35
36
61
36
48
56
32
40
49
38
37
29
56
31
42
49
44
49
50
32
43
42
29
54
33
31
49
35
58
29
47
29
30
38
47
31
43
1
4
1
1
1
6
4
4
1
6
6
1
6
1
3
1
1
1
2
1
4
6
5
6
1
1
1
4
4
6
1
1
6
1
1
1
6
1
4
2
4
6
6
1
1
1
1
16
15
15
14
18
17
16
16
16
18
12
12
18
16
17
16
17
16
18
18
17
16
9
16
18
16
17
16
18
17
18
7
17
18
16
18
14
16
12
16
14
16
18
12
18
17
18
1
1
1
1
4
3
4
1
4
1
1
4
3
1
1
1
1
1
4
1
1
1
1
1
4
1
1
3
3
4
6
1
1
4
1
4
1
1
1
4
1
4
3
1
3
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
46
46
34
52
42
51
53
33
49
56
44
45
37
47
32
49
29
58
35
55
43
42
31
46
58
28
36
37
38
43
41
38
29
28
42
44
50
33
51
53
38
52
55
35
32
49
50
1
4
6
4
1
1
4
1
4
4
1
1
1
1
1
4
6
5
6
4
1
1
6
3
1
1
1
1
1
6
1
1
1
1
4
1
6
1
1
4
4
6
4
1
1
4
1
16
18
12
18
16
16
18
14
18
16
18
16
16
15
18
17
17
16
14
16
18
16
18
16
18
16
17
18
18
18
16
16
17
17
14
18
18
18
16
16
12
17
16
16
18
18
17
2
3
1
6
2
1
1
1
1
4
3
1
1
1
1
1
1
6
1
1
4
1
1
2
1
1
3
1
4
4
1
1
1
4
1
3
3
4
3
1
1
3
4
1
1
3
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
40
43
47
33
34
46
51
47
39
40
38
35
33
52
26
45
65
35
42
26
38
29
43
42
35
34
49
49
57
26
43
26
48
33
30
48
38
26
40
39
35
35
54
55
35
42
28
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
4
1
1
1
1
1
6
1
1
1
1
3
4
1
6
4
6
6
1
6
1
1
1
1
1
1
1
1
3
4
6
4
18
16
18
18
12
18
12
12
18
18
14
18
18
17
16
14
12
13
14
14
14
13
15
4
17
12
16
18
18
16
16
16
18
14
18
12
12
16
18
14
16
16
17
16
14
18
12
3
1
1
2
1
1
1
1
1
1
1
1
4
4
1
1
3
4
1
1
1
3
1
4
5
3
4
3
3
1
1
3
3
1
1
4
4
1
4
1
6
3
1
4
2
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
26
29
46
39
45
38
45
32
39
43
26
54
54
44
33
40
51
50
26
28
31
41
48
38
39
42
45
48
42
29
30
41
42
40
28
53
45
33
32
41
41
29
64
57
50
44
26
6
1
1
1
4
1
1
1
1
1
6
6
1
4
1
2
1
1
1
1
1
6
1
5
1
1
1
6
1
1
4
1
1
6
1
4
1
1
1
1
1
6
1
1
4
1
6
16
16
14
16
18
18
12
18
17
16
16
18
14
18
16
18
17
18
16
14
18
18
16
18
18
18
10
16
14
18
13
18
18
17
18
15
12
16
16
15
17
18
12
15
12
18
17
4
1
3
1
3
1
1
2
6
1
4
1
1
1
1
4
1
3
3
1
4
6
1
6
1
1
1
1
3
1
1
1
4
2
1
3
1
1
3
1
1
1
6
3
3
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
49
31
39
35
35
45
32
31
39
50
29
51
49
34
60
48
32
35
34
28
42
33
27
25
43
34
59
25
29
36
27
41
45
40
47
57
26
41
46
35
44
57
33
31
53
30
5
1
1
1
1
1
6
1
1
6
1
1
1
1
1
3
1
1
1
1
6
1
6
1
6
1
1
1
6
1
1
1
1
4
1
4
1
6
1
1
1
6
1
1
1
4
1
12
18
16
15
16
16
18
18
18
18
13
16
17
18
18
14
16
16
16
16
17
16
16
14
16
16
12
16
14
16
16
14
16
18
16
17
18
16
15
17
12
18
18
15
16
17
16
3
4
4
4
5
4
1
1
6
1
1
1
4
3
4
1
4
1
4
4
4
1
1
1
4
1
1
4
1
1
4
1
1
4
4
3
1
4
1
4
4
1
4
1
4
3
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
36
33
45
45
33
33
31
29
46
43
28
51
43
32
36
44
52
38
38
34
27
50
54
35
52
40
51
47
36
53
35
27
59
39
60
30
42
35
37
35
51
46
60
27
39
25
39
6
1
1
1
1
1
6
1
1
4
1
6
1
6
1
1
1
4
1
1
1
4
1
1
1
1
1
1
1
1
1
6
1
1
6
1
1
1
6
1
1
4
3
1
1
1
1
18
18
17
17
14
18
16
18
16
18
18
18
18
18
18
16
17
16
16
18
16
18
16
16
18
14
12
18
16
15
18
16
16
12
18
17
16
18
16
13
16
17
18
16
16
16
12
1
1
4
4
1
4
1
4
6
4
4
1
4
4
3
1
4
1
1
1
4
4
1
1
3
1
4
1
1
1
4
1
1
4
3
1
3
1
4
4
4
4
4
1
1
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
48
29
45
51
31
56
25
35
48
52
50
34
32
47
31
31
31
47
45
45
59
43
50
26
32
52
47
53
31
47
26
33
45
50
40
42
43
49
46
39
28
31
55
63
54
31
1
4
1
1
3
6
4
6
1
6
4
1
6
6
1
1
1
6
4
4
1
3
1
2
1
6
4
1
1
1
4
1
1
1
1
1
1
1
4
1
6
1
1
1
4
1
4
13
18
16
16
18
14
12
16
18
18
18
16
18
13
16
15
18
16
14
18
18
18
17
17
16
16
16
17
15
16
18
18
16
18
14
17
18
16
15
15
18
16
18
18
18
18
18
1
1
1
1
3
1
1
4
1
4
1
1
4
1
4
1
1
4
1
4
4
6
4
4
1
1
4
4
3
4
1
1
4
1
1
3
4
1
1
1
4
1
4
6
3
3
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
45
40
35
46
41
37
36
44
30
53
43
36
46
45
50
31
46
45
40
41
43
46
63
32
35
45
35
33
43
53
28
39
37
52
42
59
62
59
47
55
26
51
41
50
40
33
4
1
1
4
1
6
1
1
1
1
1
5
1
1
1
4
6
4
1
1
6
4
1
4
6
1
1
1
1
1
1
1
4
1
1
3
1
3
1
4
1
4
1
1
1
1
6
18
18
16
16
18
17
18
14
16
16
13
14
16
16
18
18
18
14
16
14
17
16
16
18
16
15
18
15
16
14
18
16
18
16
14
16
13
18
18
18
16
18
18
18
18
16
15
4
1
1
1
1
4
4
1
4
3
4
1
1
4
3
1
1
6
6
1
4
4
4
6
1
1
4
1
1
4
4
4
1
4
3
4
4
4
4
4
4
1
4
1
4
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
47
31
32
59
45
32
31
42
36
38
42
46
59
30
65
36
45
45
56
41
36
45
52
40
42
38
37
39
31
35
40
25
47
65
45
47
57
29
25
45
48
43
33
46
44
46
25
4
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
4
1
4
1
4
4
1
1
4
1
1
1
1
6
1
1
4
1
1
5
1
6
1
6
4
1
1
1
4
1
1
12
16
16
16
15
18
18
18
12
16
18
16
18
16
16
16
13
17
16
12
16
16
18
18
18
18
13
16
18
18
12
18
12
16
16
12
17
18
14
17
16
14
16
16
18
18
13
1
4
4
4
1
1
5
3
6
1
1
6
4
4
1
6
6
4
1
3
4
4
4
4
4
3
1
4
3
1
1
1
1
6
4
4
4
1
1
4
1
4
1
4
4
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
36
48
28
39
36
58
33
36
29
33
36
26
37
52
34
30
40
45
50
46
58
40
47
27
51
50
42
39
51
38
36
44
36
31
48
25
34
47
47
55
32
34
44
46
64
26
6
1
1
1
1
6
1
1
6
6
4
1
1
6
1
1
1
1
1
6
1
1
1
1
6
1
4
6
1
1
1
1
1
1
6
1
1
4
1
1
6
1
4
1
1
3
1
17
16
16
18
18
17
18
18
18
12
14
16
12
18
17
15
12
16
16
18
18
16
16
18
17
18
18
18
18
18
18
16
16
18
14
18
12
15
18
15
18
16
15
17
16
16
15
1
4
4
4
1
1
4
1
4
1
1
1
1
4
3
1
6
1
4
4
1
4
5
4
4
4
3
4
3
4
4
6
6
1
1
4
1
1
1
1
4
1
1
1
1
3
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
58
35
32
41
48
54
45
46
33
55
38
45
48
27
43
44
42
36
47
62
37
40
38
27
49
32
27
34
36
43
41
53
55
39
32
41
55
58
44
51
58
39
43
47
31
43
6
1
6
1
1
6
1
1
1
6
6
6
1
1
1
1
4
1
4
4
4
1
1
2
1
6
1
4
6
1
1
5
1
6
1
1
4
4
4
5
4
1
1
6
1
1
4
17
12
18
12
16
18
18
18
12
18
18
16
18
16
16
17
15
18
12
15
12
12
16
17
12
18
18
12
16
12
16
15
18
18
18
16
18
12
18
16
18
18
12
18
17
15
16
3
4
1
3
1
1
4
3
3
6
1
6
4
4
3
1
1
4
1
1
1
1
1
4
1
6
5
4
3
1
4
1
4
2
4
1
3
3
1
1
6
4
1
3
4
1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
39
43
42
35
45
42
50
27
41
38
35
45
39
35
44
60
43
49
35
38
52
28
30
46
30
28
32
46
47
61
32
38
47
48
51
44
25
39
39
29
33
36
25
27
46
43
31
1
4
1
4
1
1
4
1
4
1
1
4
6
1
6
4
1
1
1
1
1
1
6
4
1
1
1
1
4
1
6
1
1
1
1
3
6
1
4
6
1
1
4
1
1
3
1
17
18
18
16
17
12
18
12
18
14
15
17
18
13
17
13
18
18
12
12
17
16
14
18
16
18
18
17
18
12
12
14
17
15
18
16
16
17
12
18
14
17
16
16
16
17
18
4
4
3
4
1
4
6
1
3
1
1
1
1
3
1
3
1
2
3
2
4
3
1
1
4
4
1
3
3
4
1
1
3
1
4
4
1
1
1
1
1
1
1
1
1
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
51
39
34
44
58
40
36
41
48
26
36
41
41
40
32
25
37
38
30
36
53
27
34
31
42
26
38
29
41
42
55
36
32
33
34
40
32
34
45
42
37
49
33
45
47
47
5
4
1
1
4
6
1
1
1
1
6
1
1
1
1
4
1
1
4
6
1
5
6
1
1
4
6
1
1
4
6
6
5
1
6
1
1
1
6
1
1
1
1
6
1
1
4
13
17
16
18
14
16
16
16
18
12
16
16
16
18
18
17
16
16
14
16
13
12
18
18
15
16
17
16
18
17
18
18
13
15
18
16
12
12
10
16
15
18
18
18
15
18
18
3
1
1
4
3
4
4
4
1
3
4
4
1
1
4
4
3
4
6
4
4
1
1
4
1
4
3
3
4
5
6
4
3
1
1
1
4
4
2
1
1
4
6
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
46
53
30
37
42
40
47
42
36
29
43
41
47
29
30
47
49
53
62
32
49
49
41
35
45
42
38
34
48
41
27
42
39
42
28
49
37
32
31
42
34
32
37
48
27
43
44
1
1
1
1
4
1
1
1
4
1
4
1
1
1
1
6
3
1
1
1
1
5
1
6
1
1
1
6
1
1
6
5
1
1
6
1
1
6
4
1
2
1
1
4
6
1
4
17
17
13
18
18
16
18
17
16
16
18
17
14
16
16
18
16
17
16
16
16
18
16
17
12
18
18
13
19
18
16
16
16
15
18
18
16
17
16
15
18
18
17
16
16
16
16
1
1
1
3
4
1
4
1
1
1
1
4
1
4
4
1
4
4
4
1
2
6
1
1
4
1
1
1
1
1
1
4
6
1
3
4
1
4
4
2
1
3
1
4
3
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
52
63
38
33
38
45
40
39
35
31
36
31
36
30
28
48
52
39
30
39
45
41
55
27
40
45
30
45
34
42
36
43
39
37
42
47
33
56
43
30
36
38
31
48
34
43
1
4
1
1
1
1
4
1
1
1
1
6
6
1
1
1
1
3
4
4
1
4
1
1
1
1
4
6
4
1
1
1
1
1
1
1
1
1
1
4
1
1
5
1
1
6
4
12
18
18
16
17
18
17
18
16
18
15
18
18
18
14
14
18
18
16
18
18
17
18
18
16
16
18
18
14
15
14
14
18
16
16
16
12
18
12
14
18
18
13
18
18
18
18
4
4
4
1
4
1
3
1
1
4
4
1
4
4
1
1
4
4
4
6
4
6
1
6
4
4
4
6
1
1
1
1
1
6
1
1
4
1
1
1
6
3
1
4
4
4
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
57
49
26
34
39
40
43
50
42
39
56
30
52
33
45
42
30
39
37
32
25
32
50
50
55
43
44
31
43
50
32
51
29
43
38
26
34
43
44
57
25
35
42
32
45
40
6
1
1
2
6
5
1
4
4
1
6
3
1
1
1
1
1
1
2
1
1
1
6
3
1
4
4
4
1
1
1
6
3
1
1
6
1
6
1
1
1
1
4
1
1
1
1
18
16
16
18
14
12
18
16
12
18
16
18
12
17
17
18
16
13
18
18
16
16
18
18
18
18
16
13
18
15
18
18
18
18
17
18
16
17
16
18
15
13
12
15
18
17
16
3
1
1
3
1
4
4
1
1
2
1
4
1
4
4
6
1
1
3
1
1
4
1
4
4
3
1
1
1
1
3
1
1
6
4
4
1
1
1
1
1
4
1
1
3
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
30
47
45
45
51
27
35
34
53
48
32
47
35
52
35
44
33
56
48
50
49
35
53
43
44
42
45
50
49
37
49
46
52
32
28
29
29
57
27
64
36
35
54
45
44
40
1
5
1
1
1
4
1
1
5
1
6
1
4
1
4
6
1
1
1
4
1
1
4
4
6
1
1
1
4
1
4
1
4
1
3
1
6
1
1
1
3
6
1
1
1
1
1
15
15
16
16
16
18
17
16
18
13
18
16
18
16
12
12
15
18
18
18
14
17
16
8
13
18
16
15
16
16
14
14
18
16
8
10
14
18
13
14
16
16
17
16
16
18
14
1
4
1
3
4
4
4
1
4
1
1
1
1
1
1
4
1
2
4
3
1
4
4
1
1
1
4
2
2
4
1
1
1
3
4
1
1
4
1
1
4
1
3
4
1
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
42
39
31
40
44
34
56
59
48
27
36
35
34
44
31
42
41
25
35
41
37
46
37
51
38
44
39
29
56
51
45
28
29
46
43
46
56
49
44
25
38
38
34
42
48
56
28
1
1
4
4
1
1
4
1
1
1
1
4
4
1
1
1
1
1
1
1
1
6
1
1
4
4
1
1
1
1
1
1
1
1
6
6
3
4
4
1
1
4
1
6
5
4
1
17
16
16
18
18
18
14
16
18
12
19
14
16
18
18
18
16
12
16
18
18
18
16
18
16
18
16
16
14
18
16
16
14
18
18
16
18
18
18
12
18
18
18
16
16
13
16
1
3
1
3
4
3
3
1
3
1
3
3
1
4
4
3
4
1
3
4
1
1
6
1
1
1
1
1
1
4
4
1
6
1
4
1
4
1
3
1
4
1
4
1
4
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
35
38
30
33
31
31
47
35
56
35
52
26
54
39
46
30
37
30
38
40
39
34
39
40
38
64
57
47
37
38
31
59
51
31
47
45
40
43
33
41
42
37
53
47
35
26
29
1
1
6
4
1
1
4
1
4
1
1
6
4
1
1
4
1
1
6
1
4
1
4
1
1
3
1
4
1
6
1
1
1
1
6
1
1
1
4
1
1
1
1
1
1
1
1
17
16
12
10
18
12
16
18
16
18
18
16
18
14
16
14
16
16
18
17
17
16
16
16
13
12
18
16
16
14
16
14
18
16
17
15
15
16
15
18
16
18
18
16
16
16
16
1
1
1
3
3
4
4
1
4
3
3
1
3
1
1
1
4
2
4
4
4
3
4
1
4
1
4
4
1
1
1
1
1
1
3
1
4
3
1
3
4
4
3
1
4
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
38
38
51
43
33
38
39
42
36
44
53
41
37
53
27
54
42
25
32
26
61
41
39
37
45
52
47
33
39
55
28
33
31
48
40
57
46
42
31
35
52
50
30
32
30
47
29
1
6
1
1
1
1
6
6
6
1
4
1
1
1
6
1
1
6
4
1
4
1
1
4
1
2
1
1
6
1
1
6
5
1
4
1
4
4
1
6
1
4
5
1
6
1
6
16
18
15
17
18
16
18
15
16
18
17
18
16
18
16
13
12
17
15
18
18
18
18
16
15
18
18
14
18
18
16
18
15
18
18
18
18
13
15
18
16
16
14
16
17
18
18
1
1
1
1
4
4
3
1
1
2
4
4
1
3
4
1
1
1
3
4
4
1
1
1
1
3
6
1
2
1
4
4
1
4
1
4
3
1
4
3
1
4
1
1
4
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
44
32
30
55
33
44
38
30
50
38
31
42
51
39
34
42
35
25
51
51
44
35
29
32
43
29
53
63
48
43
37
28
61
31
27
40
49
50
41
41
47
44
58
64
51
39
39
1
4
6
1
6
1
5
1
4
4
4
1
1
1
6
5
1
1
4
1
1
4
1
1
4
1
1
1
1
1
6
1
1
4
1
1
1
6
1
1
1
4
1
1
1
1
4
18
16
18
16
18
17
18
15
13
18
18
14
18
14
18
18
17
16
18
16
16
14
17
18
17
12
17
12
16
12
18
18
16
12
16
12
16
18
17
18
16
17
18
16
18
18
18
1
2
1
4
4
1
3
1
4
4
1
1
1
4
3
4
1
4
4
1
4
1
1
1
4
1
4
1
2
1
1
4
3
6
1
4
4
1
3
4
4
4
1
4
3
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
51
34
33
35
33
41
41
36
40
50
31
40
26
44
48
46
26
35
38
51
37
48
42
28
43
42
34
50
31
26
50
29
37
48
41
28
57
41
37
32
45
38
47
46
26
43
43
4
6
1
1
4
1
1
1
6
4
1
1
1
1
1
4
1
1
1
1
2
1
1
1
1
5
1
1
1
1
5
1
4
4
4
1
4
1
1
6
1
1
4
4
1
1
1
15
18
16
16
16
17
14
16
15
12
17
18
18
15
16
18
16
18
16
18
15
17
16
14
14
12
16
12
15
17
18
16
17
18
12
16
18
18
18
13
16
16
18
18
16
16
18
1
4
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3
4
1
3
4
1
1
3
4
4
1
1
3
4
2
1
1
1
4
1
1
1
1
2
1
4
1
3
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
36
42
33
30
56
36
36
31
32
47
49
25
52
29
44
50
27
27
25
35
34
37
50
28
45
53
53
47
53
47
40
32
25
40
47
44
34
29
41
30
54
39
39
31
27
60
34
3
1
1
1
2
1
1
4
4
1
5
1
5
1
4
1
1
1
6
4
1
1
1
1
3
6
1
1
1
4
1
1
1
1
4
6
1
4
1
6
1
1
1
1
6
1
4
16
13
16
16
18
17
13
16
15
18
18
16
16
16
16
18
16
16
17
14
15
16
12
14
12
16
18
17
18
16
16
12
16
17
13
17
14
17
12
16
18
12
14
16
15
15
14
4
1
1
1
2
1
2
1
1
4
4
1
4
1
4
4
1
1
1
4
4
1
3
2
1
4
6
1
3
4
1
1
1
3
4
3
1
4
1
1
4
6
3
4
1
4
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
38
43
40
45
51
29
54
32
32
55
27
40
44
33
45
29
40
35
44
26
64
27
38
42
45
46
41
25
37
52
32
27
33
36
35
35
56
37
31
31
37
42
47
31
36
37
38
4
1
1
1
1
1
1
1
6
1
6
1
1
1
1
1
1
4
1
6
3
6
6
1
5
6
1
6
1
1
4
1
1
4
1
1
6
1
6
4
1
1
4
6
4
4
1
17
15
13
18
16
18
14
17
12
18
18
18
11
12
13
18
14
14
18
16
18
18
18
17
16
17
15
17
16
17
16
16
12
14
18
12
18
12
16
18
18
18
16
16
15
18
17
1
1
1
4
1
1
1
1
1
1
1
4
4
4
4
4
1
1
6
1
3
1
1
3
4
4
1
1
1
1
4
3
1
1
4
1
4
4
1
1
1
3
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
34
41
45
60
25
25
42
32
54
40
39
40
45
44
46
37
43
38
27
46
36
50
33
53
57
35
60
43
43
37
45
50
28
51
41
37
47
28
46
50
30
46
27
40
32
29
4
6
1
1
4
6
1
1
6
4
1
6
6
1
1
1
4
1
1
1
4
1
1
1
6
1
6
4
1
1
6
4
1
6
4
1
1
1
1
3
1
1
1
6
1
1
1
16
18
16
18
12
16
15
16
16
18
17
17
16
16
15
14
16
16
16
18
14
12
19
14
17
18
18
16
16
14
15
18
14
17
16
12
16
16
16
18
16
17
15
18
17
16
15
1
1
1
6
1
1
1
3
1
1
3
4
1
1
1
1
1
5
4
4
4
6
1
2
3
4
1
4
3
1
1
4
3
1
4
1
4
3
1
6
1
1
4
2
4
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
36
45
30
35
38
34
49
52
26
56
35
44
34
46
49
49
50
48
43
63
47
25
57
44
26
41
40
28
30
28
58
37
29
35
52
43
56
52
34
46
36
54
35
47
42
46
41
6
1
4
6
4
1
5
1
6
1
1
1
4
4
1
1
4
4
1
3
1
5
4
1
1
6
1
1
1
1
6
1
6
1
1
4
1
1
1
1
1
1
6
1
4
4
1
18
17
13
16
16
18
18
18
17
17
18
18
12
16
16
18
15
16
17
16
18
14
16
16
16
12
12
16
18
15
18
18
18
15
18
16
12
18
17
12
17
17
15
18
14
16
16
3
4
4
1
1
1
4
3
4
1
1
2
1
1
1
1
1
4
1
1
1
1
1
1
1
6
1
3
4
1
1
1
1
1
4
4
1
1
1
1
1
4
1
4
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
47
63
53
40
25
44
32
36
40
41
44
34
43
44
39
51
30
29
63
57
32
51
30
48
44
63
48
46
59
46
47
49
32
42
42
28
43
53
58
28
26
26
48
43
44
37
1
4
3
1
1
1
6
1
1
6
6
1
1
1
1
1
6
1
6
4
1
1
4
6
4
1
1
1
4
1
1
1
3
2
1
1
1
1
4
1
1
2
6
1
1
4
6
18
12
14
12
14
12
16
16
18
17
18
16
16
18
18
16
16
17
17
12
12
18
18
18
18
14
18
14
18
12
14
16
18
16
17
17
16
16
18
12
18
12
16
18
18
16
17
1
1
1
1
1
1
3
1
4
4
1
1
1
4
3
1
4
1
4
1
1
1
3
4
4
1
4
6
1
5
6
1
3
1
4
1
4
4
4
1
4
2
1
1
5
4
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
47
49
44
30
47
57
35
32
28
25
39
46
35
54
34
53
26
65
64
49
26
53
42
49
49
60
40
48
41
30
29
37
46
43
46
30
27
54
55
43
46
47
51
43
38
56
51
1
1
1
1
1
1
6
6
1
1
1
1
1
1
1
1
5
3
3
4
1
4
4
1
1
4
1
1
4
6
6
1
1
1
4
6
1
1
4
1
4
1
1
5
6
1
1
15
18
16
16
12
17
14
16
16
18
15
16
17
16
13
16
12
16
15
16
14
17
12
16
18
18
16
18
18
17
17
18
16
18
18
18
15
17
17
16
8
17
16
16
17
17
15
1
4
4
4
2
4
1
1
3
4
1
1
1
6
1
4
1
4
1
4
1
4
4
4
1
1
4
4
3
1
4
3
4
4
4
1
1
4
4
4
1
4
1
4
1
3
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
45
49
44
57
50
31
28
42
59
55
29
42
26
32
33
34
30
44
46
39
65
42
48
25
38
54
42
57
37
48
54
25
46
39
37
34
34
41
42
50
48
64
44
54
41
44
6
1
1
6
1
1
6
1
4
4
1
1
6
1
1
1
1
5
1
5
1
4
1
1
6
1
1
1
1
1
1
6
6
1
1
1
1
4
1
1
3
1
3
1
1
1
1
18
14
16
17
12
18
18
14
18
18
16
14
16
16
18
16
12
18
18
13
15
14
16
12
17
14
17
18
14
12
18
17
18
16
14
12
16
14
16
18
18
18
18
14
18
18
18
6
1
3
4
4
1
4
4
4
4
4
1
1
4
1
2
1
1
4
1
1
4
4
4
1
6
4
1
6
3
4
4
1
4
4
1
1
1
3
4
1
4
4
1
4
1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
55
32
58
43
48
31
56
30
50
30
49
28
49
47
28
29
47
47
40
49
35
46
47
41
28
50
32
61
40
40
49
49
34
46
34
44
35
37
43
46
39
31
45
35
39
45
62
3
4
1
1
6
6
4
1
4
1
3
1
6
1
1
4
1
1
1
1
1
4
1
1
1
1
1
1
1
4
1
4
6
1
1
4
1
1
1
1
6
1
1
6
1
4
4
16
16
18
16
19
18
15
16
15
16
16
18
18
18
13
17
14
16
18
16
18
17
16
18
18
12
14
16
16
16
18
16
16
16
18
16
16
15
16
18
18
14
18
16
18
17
18
4
4
3
4
4
4
1
1
6
1
1
1
4
3
1
4
3
1
6
4
3
1
1
4
4
1
1
1
1
4
4
4
3
1
4
3
1
1
1
4
1
1
5
1
1
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
33
25
40
38
58
62
36
31
30
51
33
41
38
41
29
40
29
41
46
52
40
27
30
36
49
31
50
35
56
33
40
44
43
30
30
28
30
36
32
37
57
46
43
39
51
30
6
1
6
1
1
1
4
1
1
1
1
4
1
1
1
1
1
6
1
1
1
1
6
1
1
1
1
4
1
1
6
1
1
6
6
6
1
1
1
1
5
5
1
1
4
1
1
16
17
12
17
14
12
12
17
18
18
14
16
18
12
12
14
16
16
18
14
16
15
16
16
17
16
16
12
16
15
16
12
17
12
16
16
13
16
17
17
13
17
16
18
18
16
12
4
1
1
6
1
5
1
1
6
4
1
4
4
3
3
1
1
4
4
1
1
1
1
1
1
3
4
4
1
1
4
1
4
1
1
1
1
3
1
1
1
4
1
4
4
4
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
59
43
35
56
25
31
29
30
59
49
38
38
25
25
47
41
37
45
32
48
30
43
28
28
44
44
38
46
42
47
26
43
50
47
58
49
29
34
53
36
35
31
55
54
29
31
1
4
1
1
3
6
1
6
1
1
1
1
1
1
6
1
1
1
1
1
1
5
1
1
6
1
1
4
4
1
6
6
1
1
4
3
1
1
1
1
4
1
1
1
1
1
1
16
14
18
16
15
16
17
18
16
17
18
14
16
16
16
18
18
15
14
14
14
12
17
16
13
14
18
15
16
17
16
16
15
17
16
17
18
12
18
16
14
18
16
16
17
12
17
1
1
1
5
1
3
1
1
1
6
4
1
1
4
1
5
4
1
1
1
2
1
1
3
1
1
1
3
4
1
1
4
1
1
3
4
1
4
6
1
1
3
1
3
3
1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
40
39
30
39
31
33
26
45
50
40
54
41
37
56
31
41
25
52
25
41
48
46
53
47
44
38
41
34
29
31
37
43
56
31
38
44
41
36
26
36
41
48
44
34
41
32
39
1
6
1
3
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
4
1
1
1
1
1
1
1
1
6
1
1
1
1
1
6
6
2
1
1
4
1
6
4
1
16
15
16
17
16
18
16
18
16
18
17
14
16
16
17
13
16
18
16
18
17
18
12
16
18
18
18
16
16
16
16
18
16
16
13
18
17
13
16
12
16
16
12
16
18
14
18
1
2
1
2
4
1
4
4
3
4
1
1
4
3
4
3
1
1
1
4
4
4
1
4
1
4
1
1
4
4
4
1
3
1
1
4
4
2
3
1
1
1
1
1
1
1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
54
39
27
63
46
33
33
34
29
48
40
31
42
35
45
37
59
44
37
30
41
32
25
26
54
39
27
42
56
46
34
41
30
42
41
25
28
26
25
40
35
46
38
38
43
48
56
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
6
1
4
1
6
1
6
1
1
1
1
6
6
5
5
6
1
1
1
1
5
1
1
1
18
16
16
18
16
17
12
15
16
16
16
16
18
16
16
14
18
18
18
17
14
17
16
18
17
16
16
18
17
18
18
16
17
17
16
18
10
16
17
14
16
12
12
18
13
18
18
3
1
1
3
4
1
1
1
6
1
1
4
1
3
1
4
1
4
4
4
1
1
3
2
4
4
4
4
6
4
6
4
1
4
4
1
3
1
1
4
1
1
1
4
1
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
38
41
62
36
50
32
41
27
26
47
46
39
47
51
58
43
49
30
44
52
60
42
44
30
52
41
40
42
35
34
35
38
53
36
48
50
43
46
52
50
37
41
50
59
27
46
53
1
6
3
4
1
6
1
1
1
4
4
1
1
1
4
6
1
1
6
1
1
1
1
1
1
4
2
1
1
2
1
6
1
1
3
1
1
1
5
5
6
5
4
3
6
1
1
17
18
12
18
16
16
16
16
12
12
18
17
18
18
15
17
18
18
18
18
16
15
18
16
18
16
7
16
15
12
17
18
18
15
18
15
17
18
13
12
18
17
14
13
17
18
16
4
1
1
4
4
4
4
1
4
1
1
1
4
3
1
1
3
4
4
3
4
1
1
1
3
1
1
1
1
1
1
1
3
4
3
1
4
1
3
1
2
1
4
3
4
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
55
41
58
46
46
39
47
43
42
61
60
39
45
39
63
36
42
36
25
46
29
47
25
32
38
34
25
48
49
39
39
37
64
37
34
36
35
28
34
58
54
41
56
37
29
48
60
1
1
3
1
5
6
4
1
1
1
3
4
1
1
1
6
1
6
6
1
1
1
6
1
1
1
1
4
3
1
4
1
6
6
6
2
1
6
1
3
4
1
1
1
1
1
1
16
16
18
17
18
18
18
14
16
16
18
15
18
14
14
14
16
18
16
16
16
18
16
16
14
17
16
17
18
16
18
17
16
18
16
18
17
16
17
13
18
16
15
15
12
18
18
1
1
1
2
4
4
1
1
1
4
1
1
4
1
1
1
1
1
1
3
1
4
1
1
1
1
1
1
3
3
3
4
1
3
1
6
3
1
4
4
3
1
1
1
4
1
6
0
0
0
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
51
38
47
60
49
41
30
38
47
39
55
58
29
35
47
47
32
37
45
52
33
34
38
59
30
28
52
40
35
31
61
42
52
48
38
34
45
32
39
50
32
40
47
55
35
41
25
1
4
1
1
1
6
1
1
1
1
1
1
1
6
1
1
6
1
1
1
1
1
6
1
1
6
6
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
18
13
18
15
18
18
18
16
18
18
18
18
14
16
17
18
18
14
12
12
18
17
18
18
18
16
18
18
12
17
18
16
18
18
12
18
18
15
14
18
18
12
14
14
12
16
17
3
4
6
1
3
1
1
4
4
3
2
2
4
1
1
1
1
1
2
1
1
2
3
5
1
4
1
6
4
2
3
1
1
4
1
1
1
1
1
4
5
1
1
2
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
30
64
45
43
37
27
25
34
47
38
36
34
30
45
41
45
37
44
62
30
25
46
35
32
37
36
31
55
34
51
53
49
43
40
59
42
44
51
55
31
47
46
33
40
47
37
40
6
1
1
4
1
6
6
6
6
1
1
1
1
1
6
1
4
4
1
4
1
4
6
1
1
1
4
6
1
1
1
1
1
1
1
1
1
1
4
6
1
4
1
1
1
6
4
16
18
14
17
18
18
16
17
17
18
16
18
17
18
18
12
16
16
12
11
16
16
12
16
16
12
16
18
13
14
18
12
18
17
15
18
18
18
18
16
17
16
17
13
18
16
16
1
5
4
1
3
3
4
3
4
1
1
1
6
3
1
3
1
1
1
1
1
5
1
1
1
1
1
4
5
2
2
1
1
5
5
1
4
6
2
5
3
3
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
1
1
1
1
27
43
59
44
41
48
33
53
34
45
45
32
59
50
45
48
36
47
44
36
28
37
27
43
42
29
47
48
64
34
52
27
30
28
41
61
49
25
33
26
39
58
43
41
54
35
45
1
6
1
1
1
6
6
1
1
1
4
1
6
1
4
1
1
1
4
1
5
4
5
1
1
6
1
1
1
1
1
6
6
6
1
1
1
6
6
1
6
1
5
6
1
1
1
16
17
18
18
18
18
14
17
18
18
18
13
17
18
12
18
18
18
14
16
12
18
17
18
16
16
17
16
18
16
12
17
17
18
16
16
18
16
18
14
14
17
18
17
14
16
15
1
1
3
1
1
1
1
4
3
5
3
1
1
3
1
6
1
1
1
1
1
6
5
2
1
1
4
3
5
2
1
1
1
1
1
1
6
1
3
1
1
2
4
5
6
5
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
50
56
39
54
39
45
34
28
51
45
35
30
31
45
35
44
25
34
42
61
29
43
60
34
46
57
26
43
47
28
54
26
28
30
44
41
30
26
47
42
38
53
30
55
56
39
40
1
1
1
1
6
1
1
1
1
1
1
6
1
1
1
6
1
1
4
1
6
1
2
4
1
1
6
1
1
1
1
6
1
1
1
2
1
6
1
1
6
1
6
3
1
1
1
18
17
16
16
18
18
18
18
15
14
18
18
16
18
16
14
17
14
16
17
15
18
14
18
16
18
16
18
17
17
18
18
16
17
16
18
18
16
18
18
18
18
16
18
18
18
18
4
1
3
1
2
6
1
1
4
6
4
6
1
2
1
6
1
1
6
4
1
1
3
4
4
6
1
6
4
1
1
3
1
1
1
1
1
4
4
3
1
3
1
4
6
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
46
53
36
31
46
30
62
59
44
51
47
50
55
43
56
29
40
33
64
36
31
39
29
49
42
34
46
45
31
35
28
29
57
64
28
50
56
45
53
38
37
37
40
43
57
41
49
1
1
1
1
1
4
1
1
1
1
6
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
6
6
1
4
6
5
1
4
6
4
1
6
1
1
1
1
5
17
18
16
16
16
16
18
18
18
16
17
16
12
18
18
17
18
14
17
14
16
18
18
17
16
17
18
18
18
18
16
18
16
16
18
13
14
14
17
12
16
18
16
13
18
18
14
1
3
1
1
1
1
5
3
3
1
1
2
1
1
6
4
4
1
1
4
2
3
1
3
1
3
3
1
4
1
3
1
1
1
1
1
1
6
6
1
1
1
1
1
4
2
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
35
44
26
32
41
25
42
40
51
27
50
34
40
35
42
46
59
33
55
35
41
43
33
45
39
49
43
39
44
34
54
27
47
42
29
38
36
37
47
33
47
43
54
39
33
47
43
1
4
6
1
1
6
1
1
1
6
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
6
1
1
1
1
1
6
1
1
6
6
1
1
1
1
1
6
1
1
6
1
4
18
18
16
15
16
14
18
16
18
14
16
16
17
18
16
18
17
18
18
16
14
18
16
18
16
18
18
15
16
15
18
18
18
18
17
18
18
18
16
12
17
18
18
16
12
16
14
1
1
1
1
1
1
4
4
6
1
2
1
1
6
2
2
1
4
1
1
1
6
2
1
6
1
1
4
4
4
1
1
6
1
1
3
1
6
3
1
1
1
4
3
1
4
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
44
38
43
37
49
37
44
50
30
29
31
45
42
36
39
37
37
44
31
38
48
45
27
34
51
46
37
43
39
54
40
29
34
48
57
36
29
29
51
29
41
25
37
33
48
37
57
1
6
1
1
2
1
1
1
1
6
1
1
6
1
1
1
6
1
6
4
6
1
6
1
1
1
4
4
1
6
1
6
6
1
1
1
5
4
4
1
1
6
1
1
1
4
1
18
13
18
17
14
18
18
17
17
18
15
18
18
16
15
18
14
14
16
18
17
14
18
16
18
16
17
18
16
16
14
18
18
18
12
16
13
16
18
15
16
16
14
16
18
18
14
1
1
3
1
3
6
4
2
3
1
1
1
1
4
1
4
1
1
1
6
4
1
3
1
4
4
1
5
4
4
4
1
1
2
2
1
1
1
6
4
1
1
1
4
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
50
39
28
56
39
47
41
30
37
52
37
40
31
38
35
40
44
65
50
44
42
27
36
42
43
35
40
45
25
51
45
25
34
43
49
47
28
38
42
59
25
37
54
42
28
40
49
1
6
1
1
1
4
3
6
4
6
1
6
6
1
1
1
1
1
1
1
1
1
1
6
6
1
4
1
1
1
1
6
1
4
4
1
6
4
1
1
6
4
1
6
6
1
1
14
17
17
17
18
15
18
16
18
16
14
16
18
18
16
15
18
16
16
16
18
14
17
18
18
16
18
18
16
17
15
16
14
16
18
18
17
12
18
14
17
18
17
13
14
14
18
1
3
1
4
1
1
3
1
6
4
1
2
1
1
1
1
1
1
2
1
1
1
3
4
1
1
1
5
1
1
2
4
1
3
1
3
1
1
6
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
33
31
42
26
42
51
43
32
47
49
43
44
52
34
39
46
44
31
45
54
29
49
26
38
35
29
31
42
38
34
42
45
48
48
34
39
31
32
38
34
30
38
28
29
62
49
47
1
2
1
6
1
1
1
6
4
1
1
1
1
1
2
1
6
1
1
4
6
4
1
6
1
1
1
1
1
6
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
1
18
17
18
16
16
18
16
16
17
18
15
18
12
16
12
17
18
18
16
17
18
18
18
17
16
16
18
18
18
17
14
18
17
13
14
18
18
18
16
18
18
12
16
17
18
15
16
1
1
1
4
1
2
6
4
1
1
1
4
1
1
5
5
1
3
4
1
1
4
3
3
1
1
1
1
4
3
1
2
1
4
2
1
5
1
1
1
1
1
2
1
5
5
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
43
25
33
34
44
56
45
48
41
52
48
54
41
45
39
45
43
62
37
27
32
52
47
47
32
33
44
47
42
52
43
37
44
42
56
33
28
44
40
38
38
29
39
50
32
41
34
1
1
6
1
6
1
1
1
1
1
6
1
1
1
1
1
1
1
5
6
5
4
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
5
1
1
1
1
4
1
1
1
6
18
11
18
17
17
18
14
18
13
15
18
18
18
14
18
18
16
16
12
18
18
17
14
18
17
18
17
18
17
18
18
16
18
18
16
16
18
18
18
18
18
17
16
18
16
18
18
5
1
4
1
4
1
1
1
1
1
6
5
1
1
1
4
1
1
2
4
1
4
1
4
1
1
2
4
3
5
4
2
3
1
1
1
1
6
1
5
3
1
3
1
1
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
26
36
29
48
44
28
48
40
46
33
43
44
43
50
54
41
40
48
43
31
44
46
51
38
36
44
53
40
35
56
38
37
35
42
41
46
47
60
43
46
60
26
29
28
34
35
42
6
1
6
1
1
1
1
1
1
6
3
1
1
1
1
1
6
4
1
1
6
1
1
1
1
1
1
1
6
1
1
1
6
1
1
1
4
1
4
1
3
1
6
6
1
1
1
16
17
18
15
18
15
16
18
15
18
18
16
16
18
14
18
16
18
16
12
18
18
17
15
18
18
18
16
18
18
16
16
16
18
18
14
18
16
14
18
16
18
18
18
18
14
18
3
3
1
1
5
1
6
6
1
1
1
3
1
5
1
3
4
4
6
4
1
4
6
1
1
4
4
3
1
5
2
1
4
6
1
1
3
3
1
4
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
45
52
32
36
56
28
40
45
38
38
28
34
37
29
35
60
56
34
31
37
53
35
44
28
25
46
36
35
34
33
47
31
31
37
32
31
57
34
40
35
46
28
33
53
25
50
46
1
1
1
6
1
6
1
1
6
1
1
1
6
6
1
1
6
1
1
1
4
1
1
2
6
1
1
1
6
1
1
6
1
6
6
6
1
1
1
1
1
6
4
1
1
1
1
18
18
18
17
18
17
15
14
18
18
18
18
13
16
16
14
18
17
15
18
18
18
18
16
16
18
18
14
18
16
18
13
18
18
17
18
18
15
16
18
16
16
18
16
17
18
18
3
1
2
1
1
6
6
1
1
3
1
2
1
4
1
1
2
1
1
6
6
5
6
1
1
1
1
4
1
1
1
3
4
2
1
3
1
1
4
4
3
1
1
6
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
57
38
34
28
64
53
25
26
30
52
45
35
27
32
46
42
58
25
31
31
37
47
47
41
58
59
50
29
54
57
54
59
36
25
54
40
28
34
40
60
46
27
25
38
44
46
54
1
6
6
1
1
4
6
1
1
4
1
1
1
6
1
1
1
6
6
1
6
5
1
1
1
1
1
6
1
1
4
1
1
6
1
1
6
6
1
1
5
1
6
1
1
1
1
18
16
16
16
12
18
16
16
16
18
17
18
16
15
18
18
18
17
17
18
18
14
16
18
18
18
12
18
18
18
14
18
18
17
18
11
16
18
18
18
18
18
17
18
13
5
18
6
1
1
4
5
4
2
4
1
1
4
1
1
1
3
3
5
1
1
4
1
3
1
6
1
1
1
1
1
1
2
5
4
1
2
1
1
3
1
3
1
3
1
1
3
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
1
1
47
55
34
55
54
43
52
35
53
48
34
55
40
37
43
37
61
39
34
25
37
25
45
27
47
36
37
33
44
55
46
29
59
51
47
40
42
47
56
53
45
27
30
36
41
61
33
6
1
1
6
1
1
1
1
1
1
1
4
1
4
6
4
1
1
6
1
1
1
1
6
1
1
6
2
1
1
4
1
1
1
1
1
1
1
1
6
4
6
6
4
1
3
6
14
18
18
16
16
12
18
18
18
16
18
14
18
15
13
14
18
16
18
16
17
17
18
14
16
16
18
16
16
18
18
16
18
14
15
16
17
18
16
18
17
16
16
17
18
15
18
3
3
1
2
1
1
3
1
1
4
6
1
1
1
1
1
3
4
2
4
1
1
6
1
3
3
1
1
6
5
1
1
1
1
2
1
4
1
1
1
1
1
2
3
2
1
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
42
30
44
38
45
55
50
39
36
35
38
43
38
46
37
37
65
33
30
29
27
37
48
48
46
31
36
28
57
63
45
32
62
29
47
34
25
43
34
37
28
40
42
54
47
53
42
1
6
1
1
1
1
1
6
1
6
6
1
4
4
6
6
1
4
1
6
1
1
1
6
1
5
1
6
1
6
1
6
1
1
4
1
1
6
1
1
6
1
1
1
1
1
1
18
16
18
18
16
16
18
18
18
16
17
12
11
14
18
17
18
14
18
16
16
17
18
18
14
18
18
16
18
18
17
18
18
17
18
18
18
18
14
18
16
18
18
18
18
18
14
5
1
5
4
3
4
1
5
6
1
6
1
1
2
1
2
1
1
1
1
4
1
5
1
1
1
1
1
4
1
1
1
1
1
1
1
4
4
1
1
1
1
3
1
5
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
61
25
30
60
50
26
53
47
39
36
35
50
43
57
62
40
28
57
51
31
41
35
45
45
30
49
40
50
38
47
37
28
33
32
38
52
52
47
33
54
59
26
49
30
32
49
58
4
6
6
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
2
6
1
1
4
1
6
6
6
1
1
4
4
1
1
6
1
1
6
1
1
1
6
6
17
15
14
16
18
17
14
17
16
18
18
18
18
15
18
16
17
18
17
18
16
12
18
18
16
18
18
14
18
18
18
15
16
15
14
18
18
14
17
18
18
18
18
16
12
16
18
4
1
4
1
4
1
2
1
2
1
6
1
1
6
2
4
6
4
2
1
1
4
3
1
4
4
1
3
3
1
6
1
1
1
1
1
1
6
1
5
4
1
6
1
4
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
47
60
35
39
49
50
54
25
36
61
40
57
47
33
54
28
35
27
45
51
39
46
31
46
38
45
39
64
26
33
37
34
38
31
28
27
42
61
56
25
39
47
44
34
51
34
45
1
1
6
1
1
1
1
6
1
1
1
1
1
6
1
1
6
1
1
1
6
1
1
1
4
4
1
1
1
6
4
1
1
6
1
6
1
1
1
6
1
1
4
1
4
6
1
18
18
17
17
18
17
18
16
16
14
18
18
15
16
17
16
16
17
18
16
16
18
18
16
17
16
16
18
17
16
16
14
18
16
18
18
16
18
18
16
18
14
16
18
16
3
16
1
3
1
6
3
1
4
1
1
1
5
5
3
1
1
1
1
4
2
1
1
6
1
5
4
4
2
6
4
1
1
1
1
1
1
1
6
3
1
1
1
1
4
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
41
26
40
60
48
40
33
48
42
53
33
46
35
65
60
54
61
49
49
27
45
28
45
52
43
28
32
34
56
41
42
28
41
32
38
40
38
32
39
37
51
58
40
33
37
55
55
1
6
6
6
1
1
6
1
5
1
1
4
1
1
1
1
1
1
1
6
1
1
6
1
4
6
1
4
1
1
1
1
1
1
5
1
1
6
1
4
4
1
1
1
1
1
1
18
16
18
18
16
16
12
14
18
18
18
16
18
18
18
18
18
16
18
18
16
18
16
16
14
16
16
18
16
18
16
16
18
18
18
16
18
13
16
18
13
18
16
17
16
14
16
3
4
3
4
1
1
1
1
6
4
1
1
1
6
5
6
4
1
1
1
1
1
1
1
1
1
6
6
1
4
1
4
2
1
1
6
1
4
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
44
59
49
27
57
47
25
55
37
32
38
42
44
32
53
47
33
25
27
41
30
63
50
26
40
64
49
40
53
36
52
45
38
46
31
41
46
42
47
57
45
63
45
25
51
43
36
1
1
6
1
4
1
1
6
1
1
4
1
1
1
1
6
1
6
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
6
1
1
6
1
1
1
1
4
1
1
1
6
16
12
18
16
15
18
17
18
17
17
17
16
12
15
16
18
17
18
14
13
12
18
16
15
12
18
17
18
18
16
18
18
18
15
18
16
18
18
12
18
17
16
17
16
18
17
16
3
1
4
1
1
4
1
1
3
1
1
1
1
1
1
6
4
1
1
1
1
4
1
1
1
1
4
4
3
1
6
4
1
1
1
1
4
1
1
4
3
1
4
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
57
45
35
34
39
30
26
41
30
40
53
51
30
42
38
45
27
43
41
45
50
49
46
42
56
26
59
39
38
46
33
38
39
54
58
38
48
45
43
51
38
26
29
42
44
52
55
4
6
4
1
4
6
6
1
1
4
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
6
6
1
1
1
6
18
16
14
18
16
18
16
14
13
14
18
18
18
18
16
18
16
17
12
18
14
12
16
16
18
16
16
13
18
16
15
17
18
12
18
18
18
18
17
16
18
16
16
18
17
18
18
4
6
1
1
1
1
4
1
1
1
3
2
6
6
1
2
1
1
1
5
6
5
1
1
1
1
3
1
1
6
1
1
1
1
1
1
3
1
4
3
1
3
1
4
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
34
45
27
32
48
51
59
47
53
32
37
35
32
33
27
34
33
44
42
28
52
33
62
30
36
28
30
32
48
36
35
34
65
46
34
58
50
49
46
50
31
41
53
34
37
53
34
6
1
6
1
6
4
1
1
1
1
1
1
6
1
6
1
1
4
1
6
1
6
4
6
1
1
1
6
1
4
1
1
4
1
1
1
1
1
1
1
6
1
1
1
1
1
1
16
18
16
17
17
14
18
18
18
18
18
16
16
14
16
17
18
16
14
18
18
17
16
16
12
14
16
18
18
18
16
16
16
16
16
18
18
18
18
12
18
18
18
16
18
18
16
1
1
4
1
3
4
4
1
4
1
4
1
4
1
2
1
4
3
1
4
1
4
6
1
3
1
1
4
1
1
6
1
1
1
1
4
3
4
4
4
1
4
1
1
6
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
46
43
41
47
32
41
39
50
26
46
29
47
27
45
30
58
49
35
50
52
40
25
47
29
29
48
50
35
34
51
42
52
30
33
53
46
33
31
39
33
50
30
41
40
43
42
27
1
1
1
1
1
1
1
2
6
1
1
1
1
4
1
4
6
1
1
1
1
6
1
6
1
1
1
1
1
1
6
1
1
1
1
1
6
4
1
1
1
1
1
1
6
4
1
18
16
18
12
18
18
10
16
16
18
15
15
16
12
16
18
18
14
12
14
18
18
16
16
15
18
18
18
16
16
18
18
13
16
12
17
18
18
17
18
18
12
18
18
18
16
16
6
2
1
1
1
4
1
1
1
4
1
2
1
1
1
1
4
1
1
1
3
1
1
1
1
4
1
5
1
4
4
3
1
4
1
3
4
6
3
1
1
1
4
5
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
37
48
28
38
30
50
28
43
32
40
33
55
28
37
62
26
46
50
26
50
48
42
38
49
49
64
53
38
31
37
53
33
52
32
43
27
42
52
30
42
44
27
37
47
32
38
49
4
6
4
1
6
1
6
1
6
6
1
1
6
1
4
6
5
1
6
1
5
1
1
1
6
1
1
1
6
1
1
1
1
1
1
5
4
4
1
1
1
1
1
1
1
1
1
14
16
17
18
17
12
16
18
18
16
18
16
18
16
19
16
18
15
12
18
12
18
17
18
17
18
18
15
18
16
18
17
18
18
18
18
16
18
18
16
18
18
16
17
18
18
16
1
6
1
5
6
1
1
4
2
3
1
3
4
4
3
4
6
2
1
4
1
6
6
1
4
1
1
1
1
4
3
4
4
1
5
1
1
6
3
1
4
1
4
6
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
57
52
30
48
61
29
25
42
31
44
51
53
38
37
41
56
44
50
43
37
44
44
38
55
47
26
49
47
37
49
51
53
33
40
58
51
43
58
40
35
42
54
37
42
34
32
50
1
1
1
1
6
1
6
1
1
1
1
1
4
1
1
1
1
3
1
6
1
2
4
1
1
1
4
1
6
1
1
1
1
6
1
1
1
1
1
1
4
4
4
1
6
1
1
16
18
16
12
18
18
17
16
13
18
14
16
17
16
14
18
17
18
14
18
12
18
17
12
18
16
18
17
16
16
18
16
16
18
18
18
16
18
18
18
18
18
14
18
16
18
18
1
4
1
3
1
1
1
1
1
2
1
1
4
1
6
6
6
6
1
2
1
1
6
1
1
3
4
2
1
1
3
2
1
4
1
5
6
4
1
6
5
1
1
6
1
1
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
40
41
34
29
32
43
42
42
39
49
29
39
56
55
47
49
27
36
35
33
52
46
61
27
50
31
43
54
55
49
48
46
35
41
55
54
28
54
37
41
46
33
41
36
42
36
32
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
4
1
1
1
6
5
1
4
1
1
1
4
4
1
1
1
1
1
4
1
2
5
1
1
5
1
1
1
16
14
18
15
18
18
14
16
18
14
16
16
18
18
18
18
18
16
16
13
18
17
15
16
13
18
18
14
14
18
14
12
16
16
18
18
18
16
16
12
12
16
13
17
17
18
18
4
4
1
3
1
1
1
1
6
1
4
1
3
6
1
3
1
1
1
1
1
5
4
1
1
1
4
4
1
4
3
1
1
1
3
5
4
3
1
3
4
2
1
2
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
31
62
46
61
36
56
49
42
32
32
37
46
30
37
49
45
48
31
53
46
30
46
43
59
35
41
38
48
56
45
38
41
31
39
41
48
25
47
33
53
37
39
53
36
35
26
30
1
1
1
2
4
4
1
1
1
1
6
4
1
1
1
1
1
1
1
1
6
6
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
6
1
6
1
1
1
1
1
1
15
16
18
11
18
16
14
18
18
18
14
14
18
14
18
18
18
16
14
16
17
18
15
12
18
17
16
18
12
16
18
16
18
13
18
18
16
16
16
12
14
15
12
16
13
16
14
1
2
4
1
1
2
6
4
1
1
1
4
1
1
2
4
1
1
1
1
1
1
4
1
3
2
1
1
1
1
3
1
1
1
6
6
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
41
41
50
34
52
36
33
42
51
28
40
45
31
32
40
30
50
28
43
33
43
25
52
39
38
52
46
39
54
51
59
46
29
39
26
47
30
56
26
39
29
40
44
45
43
40
3
1
6
1
4
1
2
6
1
1
6
1
1
1
6
6
1
6
1
4
1
1
6
1
1
1
4
5
1
1
1
1
4
1
4
1
1
1
4
4
1
1
1
4
4
4
1
11
14
12
18
12
12
14
15
14
12
12
14
17
12
12
14
13
18
16
14
12
14
16
15
12
13
12
13
12
10
12
12
14
12
12
12
14
15
12
14
12
12
14
14
12
12
11
1
1
1
3
1
1
1
1
4
1
1
1
1
1
1
1
1
1
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
1
1
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
40
30
40
33
41
42
52
45
50
38
45
32
41
34
33
31
50
37
30
42
26
50
42
30
55
39
50
53
34
60
32
39
55
58
43
27
55
44
38
47
36
32
25
32
38
58
37
6
1
4
1
4
1
4
6
6
1
1
1
4
1
1
6
4
1
4
1
1
1
1
1
6
4
4
4
1
1
6
1
1
1
1
1
3
1
1
4
1
4
6
1
1
6
1
13
13
13
13
14
12
12
13
16
19
13
12
12
15
13
12
14
12
12
16
12
14
13
18
16
16
12
18
13
12
13
12
16
16
12
16
14
18
13
15
16
14
15
9
16
12
12
2
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
3
1
1
3
4
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
35
40
37
53
28
43
37
37
57
26
31
48
44
60
31
39
56
28
41
36
56
45
37
54
36
27
26
41
58
35
43
33
40
41
36
42
36
52
26
39
39
38
59
42
39
37
29
1
1
1
4
1
1
1
6
1
1
1
4
1
1
4
6
1
1
1
6
1
1
1
1
1
1
1
6
4
1
1
6
1
1
1
1
1
1
4
6
1
1
3
4
1
1
6
16
13
14
18
14
16
14
12
14
12
16
18
18
12
16
18
7
16
16
12
15
16
15
14
14
13
16
13
14
13
13
14
13
12
12
18
12
12
14
12
14
12
12
14
14
14
16
1
1
1
1
1
1
1
1
1
1
1
3
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
4
1
2
1
1
1
1
1
1
1
1
4
1
4
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
54
38
36
39
51
33
34
42
58
42
41
38
38
30
42
36
41
40
31
40
59
43
41
33
41
25
28
47
35
42
35
52
29
29
42
34
43
52
41
35
26
43
49
43
37
27
49
4
1
1
1
1
1
6
1
5
1
4
1
1
1
4
1
1
4
6
1
4
1
1
4
1
1
6
1
1
1
1
1
1
6
4
1
1
1
2
4
1
4
1
4
4
6
4
13
16
12
12
16
16
16
12
12
10
14
13
17
10
16
12
14
14
18
13
12
12
12
12
12
15
14
12
17
16
14
14
12
15
14
16
14
12
12
16
15
16
12
12
13
13
12
1
1
6
3
1
1
1
1
1
1
1
1
3
6
3
1
1
1
2
1
2
1
1
1
3
1
2
1
3
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
40
42
39
44
31
33
46
44
33
32
43
31
36
49
40
32
34
33
62
40
27
41
48
37
41
26
48
44
39
26
37
36
26
37
55
43
45
46
42
44
57
29
41
45
29
48
1
1
1
4
4
1
1
6
1
1
4
6
5
1
4
1
6
1
6
4
1
1
4
4
1
6
4
4
4
1
1
1
1
1
1
1
2
4
1
5
4
1
5
1
3
6
4
14
16
13
16
12
13
16
13
13
13
12
14
12
12
12
13
16
16
18
11
15
16
15
12
17
10
16
13
14
14
16
16
16
14
15
12
16
13
12
12
18
12
14
15
16
15
14
1
1
1
1
3
1
1
1
1
4
1
1
2
1
4
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
63
35
38
25
52
25
27
58
52
39
57
27
39
57
43
32
45
29
32
61
45
54
34
52
40
51
38
61
57
26
32
26
30
32
35
40
25
32
44
44
40
33
55
34
31
43
30
4
4
1
1
2
6
1
4
1
4
4
6
1
4
4
4
1
1
1
1
1
1
6
4
4
1
1
1
1
6
1
1
5
1
1
1
1
1
1
4
1
1
4
5
1
1
6
12
12
14
14
16
16
12
14
12
13
14
14
13
16
12
13
12
15
13
12
14
12
12
12
13
14
16
16
13
17
16
15
15
17
16
14
12
13
16
14
14
15
12
14
12
14
16
1
1
1
1
1
1
1
1
1
1
4
1
1
3
1
4
1
1
1
1
4
4
2
1
3
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
2
3
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
50
34
38
59
38
47
33
39
37
40
32
34
33
64
50
58
36
36
33
35
39
48
42
41
42
44
43
42
26
28
31
38
42
28
52
29
45
28
35
52
25
63
34
48
32
28
47
4
5
6
1
4
4
1
4
6
1
6
1
1
4
4
4
6
1
1
1
1
1
1
6
6
1
1
1
6
6
1
4
4
1
6
1
1
6
1
1
6
3
6
1
1
1
1
12
13
16
12
12
14
13
17
13
12
15
18
14
15
13
18
16
8
13
12
13
17
12
16
16
14
16
14
18
14
13
14
16
14
16
13
14
16
14
14
16
13
12
17
16
12
16
1
1
1
1
1
1
1
1
1
4
2
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
2
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
6
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
43
53
37
29
28
35
42
36
29
54
47
34
31
49
53
56
37
27
58
37
38
35
33
28
35
36
39
39
38
38
33
31
47
55
37
32
39
32
60
42
36
40
30
52
37
28
55
1
1
4
1
4
1
1
6
1
4
5
1
1
4
1
4
1
6
1
1
1
1
1
1
1
4
1
1
1
3
1
1
1
1
4
1
1
1
3
1
1
4
1
1
4
1
4
16
12
13
14
14
12
17
12
16
12
14
14
15
18
12
12
14
18
12
14
16
14
14
14
12
16
14
16
13
14
16
16
14
12
14
14
14
14
16
16
17
14
12
15
13
12
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
3
1
1
1
3
1
1
3
1
1
1
1
1
1
1
1
1
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
25
39
31
46
59
39
38
29
35
30
57
31
54
52
33
32
43
41
37
34
48
35
35
46
33
38
48
44
27
43
34
30
65
49
42
58
50
33
35
37
54
34
36
34
59
41
40
6
1
4
1
1
4
4
6
4
1
3
6
1
1
6
1
1
4
1
6
1
1
5
1
6
1
4
6
1
6
1
4
3
1
4
1
1
4
3
4
4
1
5
1
3
1
6
12
17
15
14
16
16
15
12
12
14
12
17
12
12
16
12
14
14
14
16
14
14
12
15
15
16
13
13
14
14
12
11
11
12
12
13
14
14
14
16
13
12
11
14
12
16
13
1
1
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
4
1
1
4
1
1
1
1
1
1
1
3
1
1
1
1
3
1
6
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
57
51
29
30
51
35
36
35
28
32
26
46
31
38
25
45
25
52
39
40
31
40
42
39
37
50
31
62
51
29
39
38
49
54
60
47
28
25
33
52
40
43
38
41
39
35
1
4
1
1
1
4
6
1
5
6
6
1
1
6
4
1
4
6
1
1
1
6
1
4
1
1
1
1
3
1
1
1
1
1
1
1
1
1
6
1
4
5
4
1
1
1
1
13
12
12
14
12
13
14
12
16
16
13
13
16
12
14
15
16
12
14
14
13
18
13
14
16
12
14
17
11
14
14
11
16
12
12
15
16
16
12
16
14
13
13
15
13
15
16
3
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
2
1
1
1
1
4
1
1
3
1
1
1
1
2
1
1
1
4
1
1
0
0
0
0
0
0
0
0
0
0
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
47
33
30
41
31
39
25
26
42
34
32
30
43
38
55
29
47
54
45
49
42
31
34
40
26
42
29
30
56
36
35
43
50
40
31
32
39
51
43
47
36
27
34
36
40
29
49
4
1
1
1
1
1
6
4
5
1
1
1
4
1
1
1
1
1
1
1
1
1
1
6
1
1
1
6
1
1
1
1
1
6
6
1
1
6
1
4
6
6
6
1
1
4
1
17
15
15
12
13
14
16
14
13
13
16
14
14
14
18
12
12
18
16
12
16
12
16
18
13
16
17
16
12
16
18
14
16
12
14
18
16
15
18
15
16
17
14
16
16
13
14
1
1
1
1
1
2
3
1
1
1
1
1
1
1
1
1
1
1
3
4
2
1
1
2
1
5
1
3
1
1
1
1
1
1
1
3
2
4
1
1
1
1
1
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
1
1
1
1
55
46
31
27
47
34
30
41
40
27
55
31
33
38
56
39
47
30
34
27
48
65
45
35
30
41
47
39
51
31
37
39
48
47
60
51
29
50
45
37
33
41
28
27
36
36
35
1
1
1
6
4
1
6
6
6
1
1
1
1
6
1
1
1
1
4
6
4
1
1
5
1
4
5
1
1
1
1
4
1
6
1
1
1
1
1
1
4
6
1
6
4
1
4
14
16
14
12
9
14
14
14
17
12
12
12
14
12
18
12
14
12
12
16
16
14
16
18
13
16
12
16
18
12
12
12
12
12
14
12
12
13
12
16
12
16
16
13
14
18
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
3
1
2
1
1
2
1
1
1
1
1
4
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
45
27
57
58
51
39
55
45
34
39
31
34
57
53
58
26
39
47
51
44
44
30
54
43
34
36
39
28
46
46
44
40
41
33
46
32
54
49
59
48
55
31
35
30
64
37
40
1
6
1
1
1
6
1
1
1
1
6
6
1
1
1
1
1
5
1
1
1
1
1
4
1
6
4
6
4
1
1
4
4
6
1
6
1
1
5
1
6
1
6
1
1
6
1
15
13
14
16
12
16
12
14
14
13
14
14
18
16
14
16
14
12
18
14
15
14
12
14
16
16
14
14
14
18
15
16
16
12
16
12
13
12
12
12
12
14
12
15
8
14
13
1
1
1
1
4
1
4
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
40
37
35
41
39
30
48
37
40
38
50
30
64
26
37
40
40
30
32
45
42
31
47
33
51
45
44
27
33
31
26
32
32
34
37
36
34
47
29
38
30
28
30
56
33
36
38
1
1
1
1
2
6
1
1
6
4
1
6
1
1
4
6
6
5
1
6
6
5
1
6
1
6
1
6
4
1
6
1
6
4
6
1
1
1
4
1
6
6
2
1
6
4
1
15
14
12
12
12
16
18
18
14
13
14
13
14
12
16
15
14
12
14
16
12
14
12
12
16
16
13
13
12
12
16
12
15
14
14
16
12
12
13
14
16
16
17
12
14
13
13
1
1
6
1
4
6
2
1
1
3
1
1
1
1
1
4
1
1
1
3
4
1
1
1
1
2
1
3
6
1
1
6
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
41
56
51
34
53
27
52
50
55
33
43
26
33
30
42
33
41
39
28
39
29
28
34
48
55
36
39
37
32
28
39
42
35
35
56
43
40
35
30
35
30
27
41
37
37
35
30
1
1
1
1
4
1
6
1
1
6
1
1
4
1
4
1
1
6
1
4
1
6
1
1
1
1
1
1
1
1
1
1
4
1
6
1
1
1
4
1
6
6
6
4
1
1
6
15
16
16
16
13
18
18
16
14
16
14
12
13
14
17
13
16
13
14
13
12
16
10
14
12
18
13
18
16
14
12
12
15
12
13
18
13
14
13
13
14
12
17
11
14
17
14
1
1
1
1
3
1
1
1
1
1
1
1
1
1
2
1
3
6
1
1
1
1
1
6
2
3
1
1
1
4
1
1
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
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
28
42
37
38
31
30
29
38
30
31
59
29
45
26
42
31
57
29
37
30
41
39
33
49
28
25
32
27
32
42
46
28
34
34
44
44
32
34
33
32
35
55
25
40
28
32
29
6
1
6
1
1
1
1
6
1
1
1
6
1
1
1
1
5
1
6
1
1
6
1
1
6
6
1
6
6
1
1
1
1
1
1
1
4
1
1
1
5
1
6
1
1
1
1
16
14
13
12
16
14
12
17
12
16
17
18
16
12
13
14
12
16
14
15
13
12
14
13
14
16
13
18
16
9
14
12
14
13
16
12
12
13
14
16
12
12
14
18
12
12
13
3
3
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
4
1
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
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
1
1
38
29
55
36
35
53
33
51
26
33
36
37
60
31
28
51
55
39
38
48
41
35
28
46
27
34
28
25
42
57
35
33
41
47
33
47
38
40
47
25
30
57
51
33
60
40
27
6
4
1
5
1
1
1
4
6
1
5
6
1
1
6
1
4
1
1
1
6
5
1
6
6
1
1
1
1
1
6
1
1
1
5
1
1
1
1
6
6
6
1
1
3
4
1
13
12
12
16
12
12
18
12
16
13
16
12
14
15
11
12
8
14
12
11
13
14
16
14
16
14
16
13
16
16
17
16
13
12
14
14
14
12
14
16
16
17
16
12
15
14
14
1
1
1
1
1
1
1
1
1
2
1
3
1
1
1
3
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
3
1
1
6
1
3
1
4
6
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
1
1
1
1
1
49
25
41
30
36
38
53
27
34
35
33
32
41
26
51
49
38
33
39
54
39
47
32
27
45
49
33
30
43
32
30
34
60
30
29
47
52
25
49
31
34
28
42
39
31
26
49
1
6
1
1
1
6
4
1
6
4
4
1
4
6
1
6
1
4
1
4
1
1
1
1
1
1
1
5
1
6
6
6
1
1
1
1
6
1
1
1
1
6
3
6
6
6
4
14
17
14
13
16
17
12
13
16
12
18
12
14
13
12
18
14
14
15
15
14
14
16
18
16
13
18
12
17
18
12
16
14
15
15
16
17
13
12
12
18
16
13
14
16
16
14
1
1
1
1
5
1
1
1
2
1
3
1
3
1
1
1
1
1
6
1
1
1
2
1
2
1
1
1
6
1
1
1
1
4
1
1
3
1
1
1
1
3
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
58
35
48
49
40
49
40
57
30
38
28
48
30
46
27
43
48
51
40
29
62
27
51
28
35
34
45
40
58
51
33
35
34
52
49
36
28
34
52
25
65
27
37
48
33
49
6
1
1
1
4
1
4
1
1
1
1
1
1
1
6
6
4
1
3
1
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
6
1
1
1
1
1
1
1
1
3
17
18
16
12
14
15
14
12
14
13
14
12
13
13
15
16
14
12
14
16
12
13
16
12
14
12
12
12
15
16
16
14
12
13
12
10
13
15
12
12
9
12
12
12
11
13
12
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
6
1
1
6
5
1
1
1
1
1
1
1
6
6
1
1
1
5
1
6
1
1
6
1
1
1
6
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
33
46
59
34
38
31
31
29
60
35
38
41
44
34
29
26
62
51
62
51
45
32
26
47
25
42
33
39
37
39
53
39
42
34
41
42
35
31
36
31
34
57
59
43
43
30
1
1
4
1
4
1
1
1
1
1
1
4
4
1
1
1
6
3
4
1
1
1
1
1
4
6
1
4
1
6
4
4
1
4
4
1
1
4
1
1
1
6
1
1
4
1
1
16
13
13
13
14
13
12
13
10
12
12
12
16
14
12
12
17
15
12
12
12
12
12
11
14
15
12
13
12
14
15
16
11
16
13
12
16
14
14
12
12
16
18
12
12
13
13
5
6
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
6
1
6
6
6
6
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
4
1
6
6
6
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
30
44
35
63
48
48
38
47
62
53
46
30
32
43
40
39
31
28
39
37
50
46
30
27
34
39
29
46
43
45
38
41
38
51
35
36
36
55
29
59
54
58
37
33
52
34
41
1
1
1
1
4
1
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
4
1
6
1
1
1
1
12
11
12
12
12
11
12
12
12
12
14
11
14
13
12
18
14
12
13
8
12
16
14
16
14
12
13
15
12
12
10
12
12
13
16
12
19
12
11
11
12
12
16
12
17
12
12
1
1
1
6
1
1
1
6
1
1
1
1
1
6
1
1
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
39
60
27
26
41
37
54
42
47
27
64
37
58
36
49
28
46
25
47
43
54
38
39
30
47
35
59
28
50
32
27
31
35
37
46
41
40
33
26
46
36
48
43
56
27
48
1
1
3
1
6
4
1
4
4
1
6
3
6
1
1
3
1
2
1
4
1
1
1
1
1
4
1
4
1
1
1
1
1
1
1
4
1
1
1
1
4
6
1
1
4
1
1
12
13
12
12
16
12
12
12
12
8
12
12
12
16
12
12
12
14
12
12
13
13
15
14
18
12
12
12
13
12
12
16
12
12
9
14
12
13
14
13
12
14
18
13
14
12
12
2
1
1
1
1
6
1
1
1
1
1
1
4
1
1
1
1
3
1
1
6
1
5
6
1
1
1
1
1
6
6
1
1
1
1
1
1
1
6
1
6
1
2
1
1
1
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
31
29
43
30
29
44
56
43
51
57
44
43
46
41
42
25
38
44
41
48
42
25
29
51
30
30
51
26
35
32
36
27
35
35
49
52
32
40
31
51
40
35
30
48
58
58
4
1
1
4
3
1
4
4
1
1
1
1
1
1
1
1
1
1
1
6
1
4
6
1
1
5
6
6
6
6
1
1
6
1
1
1
1
1
1
6
1
4
4
1
5
4
3
14
16
14
13
9
14
12
16
12
14
17
13
11
13
12
14
13
12
11
12
15
13
14
12
12
13
16
12
11
12
16
18
12
15
16
13
15
14
18
16
14
13
10
12
12
12
12
1
1
1
1
1
1
1
1
1
1
6
1
6
5
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
5
1
1
1
1
1
1
5
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
43
55
39
26
32
38
34
33
36
44
31
50
35
36
50
34
55
39
25
43
27
63
33
29
45
32
43
28
51
50
57
52
35
29
40
61
42
43
29
38
38
45
37
64
50
62
6
4
1
1
4
1
1
4
1
1
4
5
1
1
4
4
4
1
1
1
1
1
1
4
1
1
4
1
1
4
1
5
1
1
1
1
1
1
1
1
1
1
3
1
3
1
1
12
14
12
17
14
16
12
10
14
14
12
14
16
16
11
11
16
14
12
16
12
12
12
12
12
16
18
12
16
12
12
12
12
12
16
16
16
17
3
16
15
16
14
12
15
10
12
1
4
1
1
1
1
6
1
1
1
1
1
6
5
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
1
6
1
1
1
5
6
1
6
1
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
39
45
38
27
25
32
42
44
25
41
37
29
50
27
55
49
51
28
55
48
60
43
25
31
38
59
45
26
42
34
29
43
57
52
63
30
26
27
37
50
37
44
48
31
26
47
34
1
4
1
1
6
6
1
4
1
1
4
1
1
1
4
1
1
1
1
1
1
4
6
1
1
1
1
6
6
1
5
1
1
1
1
6
1
1
1
4
1
1
1
1
6
5
4
12
16
13
16
11
16
14
13
12
12
12
12
13
12
12
12
14
12
12
11
12
12
16
9
12
16
12
14
12
12
10
12
12
12
12
15
16
12
11
12
12
14
12
12
12
12
14
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
6
1
1
1
1
1
6
1
1
1
1
1
1
6
6
6
1
6
1
1
1
6
1
5
6
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
45
41
27
35
36
39
46
56
37
47
56
55
50
26
29
37
36
52
34
37
28
62
44
41
63
39
45
54
44
39
29
40
27
25
33
43
43
32
51
36
57
27
55
35
58
30
58
1
1
6
1
1
5
1
4
1
1
1
1
1
5
1
1
1
6
6
1
1
1
1
1
1
1
4
4
1
6
1
1
1
6
6
1
4
1
4
4
3
1
3
1
4
6
1
13
16
17
12
15
16
12
16
12
12
16
12
18
14
15
12
12
14
16
12
12
12
14
12
12
14
12
12
16
15
13
13
14
16
18
12
12
14
10
13
12
16
13
11
16
12
12
5
1
1
1
1
1
6
3
1
1
6
1
5
1
1
1
1
1
1
1
5
1
6
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
40
49
34
42
27
42
56
29
25
37
34
28
46
49
41
43
25
61
26
45
35
35
32
43
39
36
56
30
59
27
46
56
43
49
30
30
37
29
30
28
27
36
32
43
60
32
44
1
1
1
1
1
4
1
6
6
6
6
1
1
4
1
1
1
3
6
1
1
1
2
1
1
4
1
1
1
1
1
3
1
6
4
5
6
1
1
1
1
6
1
1
1
1
1
14
19
15
12
12
16
12
12
13
14
14
12
16
12
16
13
12
16
12
16
18
14
17
16
12
13
14
12
12
16
12
14
12
12
12
13
12
9
12
14
12
16
12
10
12
13
12
6
1
6
1
1
6
5
1
1
1
4
1
6
1
1
6
6
1
1
1
6
1
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
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
28
26
49
39
25
31
46
62
45
26
29
37
60
30
33
35
36
55
36
52
47
55
59
44
32
25
54
41
41
27
58
43
46
47
50
42
57
33
31
43
46
56
27
34
27
35
25
1
1
1
4
1
2
5
1
1
1
6
6
1
1
1
1
6
4
1
1
1
1
1
1
6
1
3
1
1
6
1
6
1
4
1
1
1
1
1
1
1
1
1
1
1
1
1
12
12
12
14
12
16
15
8
12
16
16
16
12
11
13
14
16
13
12
16
16
11
12
16
16
12
8
16
12
16
11
16
11
16
12
13
12
17
12
16
12
12
12
12
12
15
10
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
1
6
1
1
1
1
6
6
1
1
1
1
1
3
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
50
28
42
48
45
38
46
45
48
52
32
28
50
41
36
28
59
43
57
40
57
58
28
44
49
42
52
40
54
43
34
29
41
29
49
30
41
44
55
62
38
38
36
38
40
27
33
1
1
4
4
1
1
1
3
1
1
4
1
4
4
1
6
1
1
1
1
1
1
6
6
1
1
1
1
1
1
1
5
1
6
4
6
1
4
1
6
1
6
1
1
1
1
4
16
13
14
12
16
15
16
12
16
14
13
16
16
12
12
12
12
14
12
12
16
14
12
14
12
14
12
15
12
12
12
16
14
16
15
16
12
12
13
10
12
16
14
12
12
16
14
6
1
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
1
1
3
6
1
6
1
1
1
1
1
1
1
1
1
1
1
6
1
5
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
48
55
26
38
27
27
43
56
45
53
30
29
37
48
37
35
49
33
25
43
44
31
38
38
31
31
29
32
40
47
53
36
58
38
35
36
29
36
40
47
34
28
63
33
35
55
52
1
1
1
1
3
2
6
1
5
1
1
1
1
1
4
1
1
1
6
1
1
1
1
5
1
6
6
1
1
1
4
4
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
12
11
14
12
12
14
18
14
12
12
15
12
12
12
10
12
10
12
16
12
12
12
14
12
16
13
12
11
12
12
12
13
16
18
17
13
13
12
12
16
16
12
12
12
13
12
18
1
6
1
6
1
1
1
1
1
1
1
1
1
6
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
6
1
1
5
6
6
1
1
6
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
47
48
43
46
58
59
41
45
41
37
45
37
62
35
42
44
35
36
51
51
53
29
60
45
27
53
57
32
38
62
59
36
28
56
28
49
53
28
40
37
41
36
39
41
53
32
35
1
1
1
1
4
1
1
1
1
1
4
4
1
1
1
5
4
4
1
1
1
6
4
4
6
4
4
4
3
3
1
4
6
1
4
1
4
6
6
1
1
1
6
4
1
6
1
12
10
12
14
11
12
16
14
13
12
12
12
17
12
14
12
11
15
16
13
16
12
12
18
12
15
14
15
13
11
15
12
16
12
16
14
14
14
12
12
12
12
16
12
18
17
12
1
1
1
6
1
1
1
1
1
1
1
1
6
1
1
1
1
6
6
6
1
1
1
6
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
6
1
1
6
1
5
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
43
33
32
33
36
28
34
63
47
54
37
47
52
45
25
50
58
37
37
35
31
32
47
48
38
53
30
34
34
47
38
56
41
34
44
41
56
27
34
31
26
36
38
56
26
51
63
1
1
1
6
6
1
1
4
6
1
1
4
1
1
1
1
1
6
4
1
6
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
1
1
1
1
1
1
6
1
1
1
1
12
12
15
12
12
13
12
18
12
15
12
14
12
16
12
16
15
15
14
12
13
16
8
11
18
14
16
11
16
16
14
11
12
16
12
12
12
14
9
13
12
17
15
13
12
14
13
1
1
1
6
1
1
1
1
1
6
1
1
1
1
1
6
5
1
1
1
2
1
1
1
1
6
1
1
1
1
1
6
1
1
1
1
1
5
1
1
1
1
1
1
1
5
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
27
31
40
39
39
30
38
34
57
27
38
30
25
32
26
41
32
34
46
38
36
43
34
51
26
32
31
41
46
39
25
39
32
42
39
44
50
25
30
30
33
61
44
31
27
44
39
1
1
4
1
4
1
1
4
1
6
1
1
6
1
5
1
4
6
1
6
1
3
1
1
1
1
1
5
1
4
1
1
1
1
1
3
1
6
6
5
1
1
1
1
1
1
1
12
12
12
16
12
12
12
12
12
12
12
12
17
13
12
13
16
10
13
16
12
14
12
16
12
11
16
12
12
12
15
12
14
12
12
14
12
16
16
12
16
11
12
12
12
12
17
1
1
1
1
1
3
1
2
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
6
1
6
6
1
6
1
1
6
1
1
1
1
1
6
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
35
25
33
31
44
32
31
32
32
25
40
34
51
25
48
53
42
59
30
39
33
26
38
39
45
47
49
34
37
51
47
50
55
52
43
27
39
58
32
34
32
42
55
33
54
48
40
1
1
4
1
1
1
1
1
6
6
4
1
1
6
1
4
1
1
1
1
1
4
1
1
1
1
1
4
1
1
4
4
1
1
4
1
1
4
6
1
1
1
1
1
1
1
4
12
12
13
12
12
12
16
12
18
14
12
13
12
13
16
12
18
12
11
18
10
15
18
16
12
12
16
18
12
10
13
18
14
12
16
12
12
12
14
12
16
13
12
0
12
13
12
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
1
1
1
1
5
6
1
1
1
6
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
6
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
25
26
59
30
51
43
50
65
30
44
44
48
26
39
47
37
59
48
54
35
31
39
34
45
25
41
51
46
27
32
28
58
35
55
50
37
31
27
35
49
35
54
55
40
51
50
1
4
6
1
1
1
4
1
1
1
1
1
4
1
3
1
4
3
1
1
6
1
1
6
1
1
4
4
4
1
1
1
1
1
1
1
1
1
1
1
4
6
3
1
1
4
1
12
13
16
5
14
12
14
16
12
12
13
17
14
18
8
10
14
16
15
12
16
16
9
12
12
12
12
12
12
17
13
12
12
12
10
11
12
12
14
12
18
15
12
12
14
12
12
1
1
1
5
1
6
1
6
1
1
1
6
1
3
1
1
5
1
1
1
1
1
1
1
1
1
1
6
1
1
6
1
1
1
1
6
6
6
1
1
1
1
1
1
1
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
32
48
39
30
41
32
36
45
51
64
61
57
35
45
53
35
37
54
27
42
30
44
26
56
33
37
26
43
45
27
50
36
56
47
54
37
56
49
33
32
47
38
55
40
25
42
1
4
3
1
1
1
1
4
1
1
1
1
6
1
4
4
1
1
1
5
4
1
1
6
3
1
1
6
1
1
6
4
1
1
1
1
1
4
1
1
1
1
5
1
1
6
1
12
16
12
14
16
14
14
13
12
13
19
13
16
13
14
12
12
16
15
12
15
14
12
15
12
14
12
19
13
9
15
6
12
12
15
12
14
13
13
14
11
10
18
12
12
14
12
1
1
1
4
1
1
1
1
1
6
1
6
1
1
6
1
1
1
1
1
1
1
1
1
6
6
1
1
6
1
1
1
6
1
6
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
57
49
45
42
41
40
41
62
38
49
32
56
25
37
45
39
32
25
41
48
32
39
32
40
39
40
53
28
37
27
38
57
26
40
37
51
52
43
29
36
52
51
56
26
26
40
25
1
3
1
4
4
1
4
1
4
1
1
1
1
1
1
1
1
1
4
1
5
1
5
5
4
1
6
1
1
1
6
1
6
1
4
1
4
1
6
4
1
1
4
1
6
3
6
12
6
12
12
18
12
15
14
14
11
12
12
12
10
13
15
12
13
12
14
12
12
12
11
12
12
12
16
17
12
16
12
16
12
9
12
12
12
16
13
12
15
12
11
16
12
12
1
1
1
1
1
1
3
1
1
1
1
1
1
1
1
6
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
57
43
51
60
40
25
52
43
46
46
60
39
35
27
27
41
25
29
43
46
63
35
51
49
27
51
26
39
46
56
38
62
40
40
40
30
30
51
51
61
26
31
52
43
43
53
1
1
4
6
1
1
1
1
1
1
6
1
5
1
4
6
1
6
1
5
1
3
1
1
5
1
1
6
1
1
3
1
4
1
1
1
4
4
4
1
2
1
4
1
1
5
4
12
10
12
16
12
14
16
15
18
10
13
13
12
14
12
15
12
10
16
12
11
13
12
12
19
12
12
16
14
12
12
16
16
12
12
12
11
16
12
12
14
10
12
11
13
12
12
1
1
1
6
1
1
6
1
1
6
1
6
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4
1
1
1
6
1
6
6
1
1
1
1
1
1
1
1
1
1
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
58
38
51
25
30
62
34
34
31
31
43
46
42
32
64
32
45
43
31
50
37
34
40
43
41
45
29
42
28
60
44
54
36
25
32
48
35
38
34
51
50
36
25
27
45
27
43
1
1
1
6
1
3
1
6
4
1
1
1
1
1
1
1
1
1
1
1
1
1
5
6
4
4
1
1
1
1
1
1
1
6
6
4
4
1
1
1
1
1
6
1
4
6
4
12
18
12
12
13
13
12
14
14
12
12
12
13
12
12
14
10
16
7
13
13
12
12
15
12
12
13
12
16
13
11
16
12
16
14
14
14
14
15
15
12
12
12
13
13
16
12
5
2
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
3
1
1
1
1
1
1
1
1
1
1
1
1
1
1
5
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
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
45
30
32
37
47
51
41
41
42
56
53
50
27
38
60
53
42
54
31
45
39
29
36
53
50
60
38
30
58
52
48
26
43
43
65
42
48
30
34
29
38
35
26
61
35
30
60
1
1
1
1
1
1
1
1
1
1
1
1
1
5
4
1
1
5
6
4
1
1
4
1
1
1
4
1
1
1
1
6
6
4
1
4
1
6
1
6
1
1
6
1
1
1
1
11
12
12
12
12
12
10
16
9
12
10
18
17
11
13
12
14
12
13
16
12
16
12
18
12
18
15
13
18
16
15
12
16
14
18
15
12
16
16
16
11
12
14
19
12
12
14
1
1
1
1
1
1
1
1
1
5
1
1
1
1
1
6
1
1
1
1
1
1
6
6
1
1
1
1
1
1
6
1
3
5
2
1
1
1
1
1
1
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
1
1
1
1
1
1
60
38
34
47
44
56
34
31
31
51
41
45
56
29
40
41
61
53
43
47
28
55
34
32
42
51
25
34
46
46
55
26
35
58
41
62
49
43
26
46
59
31
38
41
29
58
33
6
1
1
4
1
1
1
4
1
1
4
4
1
6
1
1
1
4
6
1
6
1
1
1
4
4
6
1
1
1
1
6
4
1
1
6
1
1
6
1
1
6
6
4
6
1
6
12
16
16
17
17
17
16
14
12
17
13
18
12
17
16
16
12
18
17
16
12
16
16
12
12
14
12
17
16
16
16
12
16
15
13
12
18
14
11
13
12
16
14
14
14
12
18
1
1
1
1
1
6
1
1
1
5
1
6
6
1
5
1
1
1
6
1
1
1
1
6
1
1
1
1
1
1
5
1
1
1
6
1
6
1
1
1
1
1
1
5
1
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
1
60
34
49
36
30
38
42
32
39
49
52
50
52
38
50
26
37
49
32
58
53
50
28
43
63
49
47
41
25
39
38
38
39
27
55
38
37
31
57
26
52
49
38
45
31
28
41
4
1
1
4
1
1
1
1
1
4
6
1
1
1
5
1
6
1
1
1
1
1
1
6
3
4
1
4
6
6
1
6
4
1
4
6
1
6
1
4
1
1
5
6
1
6
1
16
16
18
13
16
16
15
14
16
12
18
14
12
16
14
12
16
18
16
12
15
12
16
12
18
16
18
15
17
13
12
16
12
15
14
13
12
15
17
13
12
13
13
17
16
16
16
5
6
1
6
1
1
1
1
1
1
1
1
5
1
5
1
1
1
1
6
1
1
1
1
1
5
1
1
1
1
1
1
1
1
6
1
1
5
5
1
1
1
1
1
1
1
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
40
29
35
43
60
32
33
26
57
35
38
61
37
38
54
26
48
31
59
33
32
40
41
26
38
36
49
53
37
46
28
43
44
46
38
50
57
44
42
31
28
61
46
60
47
42
33
1
1
1
1
1
6
6
1
1
1
1
1
1
6
1
1
1
6
1
6
6
1
1
1
1
6
1
1
1
1
6
1
1
1
1
6
6
4
6
1
1
4
1
1
4
4
1
16
13
13
14
12
18
15
14
12
12
12
16
16
12
12
16
12
16
12
12
16
16
17
13
18
12
14
12
12
16
18
16
12
16
11
18
15
16
18
12
12
11
14
16
15
14
16
1
1
1
1
1
1
1
1
1
6
1
1
5
1
1
1
5
1
1
1
1
6
1
1
1
6
1
1
6
6
1
1
6
1
1
1
6
1
1
5
1
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
1
1
1
1
1
28
32
42
44
30
42
35
27
48
32
38
44
30
40
54
31
51
39
30
56
56
25
37
44
25
25
30
42
37
36
47
59
52
58
25
26
43
47
36
48
55
58
36
25
58
40
48
1
1
1
1
1
1
1
6
1
1
1
1
4
1
1
6
5
1
4
1
4
1
1
1
1
6
6
1
1
1
4
1
1
4
1
6
1
1
1
1
2
1
6
1
1
6
1
16
16
16
15
16
15
17
12
18
17
14
11
12
16
12
13
12
14
16
12
18
12
16
16
16
16
14
18
15
14
16
13
18
17
13
16
14
12
12
18
16
14
16
13
12
12
18
1
1
5
1
1
6
1
1
1
1
1
6
6
1
6
1
1
1
6
6
6
1
1
1
1
1
1
1
1
5
1
1
1
1
6
1
1
1
1
1
1
5
6
1
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
1
1
1
47
30
52
43
57
42
57
59
59
43
26
39
32
25
48
31
37
33
52
25
52
49
41
25
27
31
37
37
36
34
48
34
27
49
64
31
56
34
29
42
37
44
38
35
56
39
36
1
4
4
4
1
4
1
1
6
1
6
4
4
6
1
1
1
2
4
6
4
1
6
6
1
6
1
1
1
1
4
6
1
1
1
6
1
4
1
1
1
1
6
1
1
4
6
14
12
12
16
16
16
13
12
12
12
9
9
13
15
18
11
16
14
14
16
16
18
14
18
13
16
13
9
12
14
16
12
12
12
16
17
14
14
16
15
12
12
14
13
12
16
14
1
1
1
1
1
1
1
3
6
5
1
6
1
1
1
1
1
1
1
1
1
1
6
6
1
1
1
1
1
5
6
1
1
1
6
1
1
1
1
1
1
6
1
1
5
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
1
1
41
50
45
33
34
38
48
53
36
32
42
58
28
49
38
39
34
35
31
60
52
60
48
46
56
52
27
35
25
42
41
57
57
35
49
53
39
26
36
30
31
36
36
45
61
40
40
1
4
1
1
1
1
4
1
1
1
1
1
1
1
1
6
6
1
4
1
1
4
1
1
1
1
4
6
6
1
1
1
1
6
1
1
1
1
6
1
1
6
1
6
1
2
1
16
16
14
14
12
18
17
15
16
12
14
12
12
16
14
12
16
16
12
10
12
12
14
12
18
18
16
16
14
18
14
12
15
13
18
15
15
12
18
10
12
19
17
16
12
17
16
6
1
6
1
1
6
1
1
6
1
1
1
1
1
1
1
1
1
1
6
5
1
1
6
1
6
1
6
1
6
1
6
1
6
1
6
1
1
1
1
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
1
1
1
1
1
1
31
60
40
60
48
60
37
33
46
40
46
38
48
54
26
43
42
46
40
37
26
48
45
35
37
40
47
34
55
27
52
58
60
49
51
49
44
33
46
56
40
33
43
42
30
39
32
1
1
1
6
1
1
1
1
6
6
4
6
4
1
6
1
1
1
6
1
6
1
1
1
1
4
1
6
1
6
4
1
1
1
1
4
1
6
1
4
2
1
1
1
6
1
1
15
14
12
14
11
14
15
14
18
16
14
16
14
14
16
3
12
16
17
16
12
16
15
16
16
16
16
12
12
16
13
12
11
14
15
12
14
14
12
11
12
16
12
13
16
14
14
1
1
1
1
1
1
1
1
1
1
1
6
1
1
1
1
1
1
1
1
6
6
5
1
1
1
1
1
1
1
1
6
1
1
3
1
2
1
6
6
1
1
1
6
1
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
1
1
61
28
27
35
58
40
25
38
27
33
26
29
48
25
32
29
35
44
61
27
31
51
32
25
38
33
41
47
52
58
59
27
27
36
40
34
33
43
55
36
45
44
33
51
45
49
44
1
4
6
1
1
1
1
1
6
6
1
2
1
6
4
1
1
1
1
6
6
1
5
1
4
1
1
1
1
1
1
6
1
4
1
5
1
1
1
1
1
1
1
1
1
1
1
18
16
15
14
16
16
16
12
16
15
12
12
16
16
14
16
16
14
12
14
13
16
17
13
12
13
13
13
12
16
17
17
13
15
16
12
12
16
8
16
16
14
11
14
16
12
12
1
1
1
5
6
1
1
1
1
1
1
1
5
1
1
1
6
5
1
1
1
1
1
1
1
1
1
1
1
5
5
1
1
1
6
1
1
1
1
5
1
1
1
1
1
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
1
1
26
43
52
25
61
29
27
42
57
46
42
45
31
49
34
31
27
50
54
43
46
55
45
34
36
27
34
28
49
41
25
25
33
47
55
35
60
26
37
40
50
49
44
50
43
43
33
1
1
1
6
1
1
1
5
4
1
1
1
1
1
1
1
1
1
1
1
3
1
1
1
6
6
1
6
1
1
4
6
4
4
1
1
1
6
1
1
1
1
1
3
1
1
6
18
15
18
12
18
15
15
12
12
16
13
12
14
18
16
14
14
12
18
12
16
16
16
16
12
14
13
16
18
18
14
17
12
10
11
12
12
14
12
12
13
12
13
12
16
13
9
1
1
6
1
1
1
1
4
6
1
1
1
1
1
1
5
1
1
1
1
6
1
5
1
6
1
1
5
1
1
5
1
1
1
5
6
1
5
1
1
1
1
1
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
1
1
1
34
48
61
26
28
65
59
57
46
41
43
32
32
35
35
47
28
33
57
43
43
43
43
53
47
26
40
29
29
33
61
25
55
34
25
52
27
55
53
31
33
41
42
46
38
45
37
1
1
1
5
6
1
1
1
1
1
2
6
1
1
4
1
6
2
1
3
1
1
1
1
4
6
1
6
6
4
1
6
1
1
6
1
6
1
6
4
1
4
6
1
4
1
6
16
13
16
16
13
18
13
16
16
8
17
16
14
16
14
18
12
14
16
14
12
12
16
16
12
14
14
16
16
12
12
15
13
14
12
12
12
16
15
15
12
12
16
12
14
16
14
1
6
1
1
1
5
1
1
5
1
2
5
1
1
1
1
1
1
6
1
1
4
1
1
6
1
1
1
1
1
5
1
6
5
1
6
1
1
5
1
1
1
1
1
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
1
1
27
31
39
33
32
25
64
30
42
57
29
25
47
32
46
34
43
32
40
30
32
31
45
39
49
27
37
31
39
25
46
27
52
45
40
25
25
44
32
51
50
50
39
26
50
33
45
1
1
6
1
6
1
6
6
4
4
1
6
1
6
6
1
4
6
1
1
6
6
1
1
4
1
1
6
4
6
4
6
1
1
1
6
6
1
1
1
1
1
1
1
5
6
1
14
16
12
12
12
12
13
16
14
14
16
16
16
17
12
18
12
16
16
16
16
16
16
11
12
14
10
14
12
14
14
16
18
16
16
12
16
12
12
17
16
12
14
14
12
17
15
1
1
6
1
1
1
6
1
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
6
1
1
1
1
1
1
6
1
1
6
6
1
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
44
57
44
45
31
43
57
35
41
35
55
44
31
65
58
56
27
47
44
44
51
44
56
61
52
32
29
38
37
53
54
57
28
39
57
50
56
44
45
54
37
40
56
41
56
35
63
1
1
4
6
1
4
4
1
6
6
4
4
6
1
1
1
6
6
1
1
1
6
1
1
1
1
6
1
4
1
1
1
1
1
1
1
1
1
1
1
4
5
1
1
1
1
1
14
13
11
16
18
16
12
18
12
18
12
14
12
14
14
18
12
16
16
16
16
16
12
12
15
16
16
12
14
12
16
12
15
12
13
14
12
12
14
14
16
16
12
12
14
16
10
2
6
1
4
1
1
3
5
1
6
1
6
6
6
1
1
1
1
1
1
1
1
6
6
5
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
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
1
1
1
1
34
30
48
31
43
26
32
61
53
48
44
39
34
53
26
41
25
58
38
55
25
37
27
50
28
28
44
52
31
55
54
42
34
32
42
33
47
44
27
45
32
37
32
47
26
48
25
1
6
4
6
4
1
1
4
6
1
1
1
4
1
1
1
6
1
1
1
6
6
1
1
1
1
1
1
1
4
6
1
1
1
1
6
4
1
1
1
1
1
1
1
1
1
6
18
16
18
11
16
1…