Binary Dependent Variables

Description

Please read instructions in the word file, all work should be submitted on word file. please don’t use Chatgpt pr any AI language. if required, use STATA.

Unformatted Attachment Preview

Special Notes Related to All Problem Sets:
A) Please type what you can.
B) All math problems do not have to be typed, but please write very clear and explain all
derivations.
Submission: A hard copy in class
Part I
1. Complete reading SW, Chapters 11-12.
Part II
1. Explain in your own words the meaning of internal and external validity. Be specific.
2. What are the main threats to internal validity? Explain in your own words. Describe the
conditions under which the estimator of  is biased. Explain and show your derivations.
2. Provide an example of a real-world problem where you need to use a binary dependent
variable model to solve it. Explain your example, why you chose it and the way you
would solve it.
3. Given the data below (consisting of 20 observations of the dependent variable Y and the
independent variable X),
(A) estimate a probit model and test the hypothesis that X is not influential in determining
the probability that y=1.
(B) Repeat the estimation with a Logit model.
(C) Compare (in a table) your results for these two estimators. (Recall: compare the
slopes, also called marginal effects, and not just the estimated coefficients; and remember
to have a constant term – intercept – in your models.) Discuss and Explain.
The Data:
y = {10100111010001001011}
x = {72531689131212323345}
Note: Remember to use an intercept.
Part III
Case Study: Smoking Ban in the Workplace
For quite a while, public concern about “second-hand” smoke has led to smoking bans in many
US workplaces. In some cases, smoking bans are determined by local ordinance that covers
indoor workplaces over a certain size, sometimes with exemptions such as for bars or restaurants.
In other cases, smoking bans are voluntarily adopted by individual businesses (these voluntary
bans were the main type of ban during the time period of the data for this problem set).
It has been hypothesized that workplace smoking bans induce smokers to quit by
reducing their opportunities to smoke. In this assignment you will estimate the effect of
workplace smoking bans on smoking. To do this you will use data on a sample of 10,000 US
indoor workers in 1991-1993. The data set contains information on whether individuals were, or
were not, subject to a workplace smoking ban, whether or not the individuals smoked, and other
individual characteristics. The data set (Econ_623_PS6_Fall_2023(Smoking).xlsx) is posted on
Canvas.
1. (a) Calculate the frequency of smoking for
(i)
all workers (the full sample)
(ii)
workers affected by workplace smoking bans
(iii) workers not affected by workplace smoking bans
Note: In above questions you just need to look at the sample’s “frequencies”.
b) What is the difference in the probability of smoking between workers affected by a
workplace smoking ban and workers not affected by a workplace smoking ban? Use a
logit model to determine whether this difference is statistically significant.
c) Estimate a logit model with smoker as the dependent variable and the following
regressors: smkban, female, age, age2, hsdrop, hsgrad, colsome, colgrad, black, and
hispanic. Compare the estimated effect of a smoking ban from this regression with your
answer to 1(b). Suggest a reason, based on the substance of this regression, explaining
the change in the estimated effect of a smoking ban between 1(b) and 1(c).
d) Test the hypothesis that the coefficient on smkban is zero in the population version of the
regression in 1(c), against the alternative that it is nonzero, at the 1% significance level.
e) Test the hypothesis that the probability of smoking does not depend on the level of
education in the regression in 1(c). Explain (and show the details).
f) In words, describe the estimated relationship between education and smoking (holding
the other regressors constant).
g) Can you improve on the model you used in (c) above? Explain and discuss.
2. Estimate a probit model using the same regressors as in 1(c).
3. Use the model of question (2) above to calculate the following scenarios:
(a) Consider a hypothetical individual, Ms. A, who is White, 30 years old, and a high
school dropout. Suppose Ms. A is subject to a workplace smoking ban. Calculate the
probability that Ms. A smokes. Do the calculation “by hand.” That is, calculate the
“z-value” of the probit model using the estimated coefficients, then look up the
probability in a standard normal table. Show your work.
(b) Repeat the calculation in 3(a) but have your software do the calculation for you.
(c) Test the hypothesis that the probability of smoking does not depend on race in this
probit model.
4. Read Table 1 below (and the notes to that Table). Then, fill in the missing entries.
(a) Compare the Marginal Effects of Smoke Ban (smkban) on the probability of smoking
for the two models used.
(b) Construct and show the prediction tables for the probit and logit models.
5. Would you use the linear probability model to do all of the above analyses? Explain.
Table 1: Estimated Effect on the Probability of Smoking of a Workplace Smoking
Ban on Two Hypothetical Workers
Mr. A: male, white, at least 30 years old, high school dropout
Ms. B: female, Black, at least 40 years old, college graduate
(1) Probit
(3) Logit
Model
Model
Estimated coefficient on smkban
(standard error in parentheses)
Predicted probabilities of smoking for Mr. A:
(i) with workplace ban
(ii) without workplace smoking ban
Difference, (i) – (ii)
Predicted probabilities of smoking for Ms. B:
(iii) with workplace ban
(iv) without workplace smoking ban
Difference, (iii) – (iv)
Notes: The entry in the first row is the estimated coefficient on smkban in the probit model
(column (1)) and the linear probability model (column (2)), with standard errors in parentheses;
both regressions include the following control variables: female, age, age2, hsdrop, hsgrad,
colsome, colgrad, black, and hispanic. The entries in the remaining rows are predicted
probabilities of smoking for the indicated hypothetical individuals, and differences in those
predicted probabilities.
DATA DESCRIPTION, FILE: Econ_623_PS6_Fall_2023(Smoking).xlsx
The data set is a cross-sectional data set with observations on 10,000 indoor workers, which is a
subset of a 18,090-observation data set collected as part of the National Health Interview Survey
in 1991 and then again (with different respondents) in 1993. The educational binary indicators
refer to the highest level attained and thus are mutually exclusive. Note: an individual with a
Master’s degree or higher has values of 0 for hsdrop, hsgrad, colsome, and colgrad.
smoker
smkban
age
hsdrop
hsgrad
colsome
colgrad
black
hispanic
female
=1 if current smoker, =0 otherwise
=1 if there is a work area smoking ban, =0 otherwise
age in years
=1 if high school dropout, =0 otherwise
=1 if high school graduate, =0 otherwise
=1 if some college, =0 otherwise
=1 if college graduate, =0 otherwise
=1 if black, =0 otherwise
=1 if Hispanic =0 otherwise
=1 if female, =0 otherwise
smoker smkban
1
1
1
1
0
0
1
0
0
1
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
1
1
1
1
1
1
0
0
1
0
0
1
1
1
1
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
1
0
1
1
1
0
1
age
41
44
19
29
28
40
47
36
49
44
33
49
28
32
29
47
36
48
28
24
39
32
60
37
31
33
49
28
24
27
31
41
36
48
50
45
23
29
51
32
57
27
30
39
18
58
48
30
37
41
46
hsdrop
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
hsgrad colsome colgrad
1
0
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
0
1
0
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
1
black hispanic
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
female
1
1
1
1
1
0
1
0
1
0
1
1
0
0
1
0
1
1
1
0
0
1
1
1
0
1
0
1
0
0
0
0
1
0
1
0
1
0
1
1
1
0
1
1
1
0
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
1
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
1
1
1
0
1
0
1
1
1
26
34
34
34
46
44
34
35
32
51
28
33
40
35
32
49
48
48
37
51
26
49
19
45
31
23
39
28
43
41
50
58
19
29
54
32
40
39
20
32
62
45
37
60
40
33
26
41
28
54
56
46
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
1
0
1
1
0
0
0
1
0
0
1
0
0
1
0
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
1
1
1
1
1
0
0
1
0
1
1
0
0
0
1
1
1
0
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
0
0
1
0
1
1
1
1
1
0
1
0
1
1
34
28
36
34
37
34
22
41
45
37
46
44
27
66
26
67
48
31
31
41
19
37
32
41
40
35
58
31
76
28
24
30
28
43
42
26
26
29
21
26
35
30
36
27
30
39
37
35
30
34
22
24
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
1
1
0
1
0
0
0
0
0
0
0
1
0
0
0
1
1
1
0
0
1
0
0
0
1
1
1
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
0
0
1
1
1
0
1
1
0
0
1
0
1
1
1
0
1
0
1
1
1
1
0
1
1
0
1
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
0
1
0
1
1
1
0
0
0
0
0
0
1
1
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
0
1
1
1
0
0
1
1
0
0
0
0
0
21
54
27
22
56
28
37
24
32
21
38
20
50
62
76
55
37
30
46
60
61
41
33
24
23
20
55
52
23
42
44
28
25
40
50
42
34
23
37
65
37
78
33
25
35
40
19
44
71
20
43
31
0
0
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
0
1
0
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
0
1
1
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
1
0
0
1
0
1
0
0
1
0
0
0
0
1
1
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
1
1
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
1
1
0
1
1
0
0
1
0
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
50
40
30
53
63
51
23
27
29
23
21
63
59
24
27
39
29
29
35
40
21
60
39
31
35
40
49
38
28
32
31
32
23
44
36
61
42
35
37
37
32
45
62
47
27
26
21
30
32
31
34
34
1
0
1
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
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
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
1
1
1
0
1
1
1
1
0
0
1
1
1
0
0
0
0
0
1
1
0
1
1
1
0
0
0
1
0
1
0
0
1
0
0
1
1
0
1
0
0
0
0
0
0
1
1
1
1
1
1
0
1
0
0
0
1
0
1
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
1
1
0
1
1
0
0
1
0
0
0
1
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
0
1
0
1
1
1
1
0
0
0
0
1
0
1
1
1
0
0
1
0
0
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
1
0
1
37
28
37
30
30
37
28
31
33
19
19
28
29
29
38
39
78
25
42
24
47
25
25
29
35
55
34
38
55
34
20
24
23
56
33
36
29
51
48
45
53
35
36
29
79
27
27
20
46
37
48
37
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0
0
0
1
1
0
1
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
1
0
1
0
1
0
0
1
0
1
0
0
0
0
1
1
1
1
0
1
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
1
0
1
0
0
1
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
1
1
1
0
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
1
1
1
1
1
1
1
1
34
41
55
37
44
24
24
23
58
57
19
50
52
24
47
34
65
37
31
39
30
43
42
47
46
35
67
40
45
37
35
37
19
24
35
48
42
25
25
37
39
50
35
36
23
23
59
29
24
29
30
22
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
1
1
1
1
1
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
0
0
0
0
1
1
0
0
1
0
1
1
1
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
1
1
1
0
0
1
1
1
0
1
1
0
1
0
1
0
1
1
0
1
1
1
1
0
1
1
0
0
1
0
1
1
1
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
1
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
1
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
0
1
1
0
0
0
1
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
1
0
1
1
1
0
1
1
1
0
0
1
0
1
1
1
1
64
39
49
57
30
48
45
26
31
31
33
64
48
46
41
30
32
57
56
22
42
31
25
21
31
55
28
41
20
32
36
34
31
49
50
34
64
60
55
24
46
30
32
40
31
41
61
47
45
19
19
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
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
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
1
0
0
1
0
0
1
1
0
0
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
0
0
1
0
1
0
1
1
0
1
0
1
1
1
0
0
0
1
1
0
1
1
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
1
0
1
1
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
1
1
0
1
1
0
1
1
0
1
0
0
0
1
1
1
1
0
1
1
1
0
0
34
35
38
44
33
31
70
19
40
45
40
41
40
45
53
24
26
44
52
28
56
63
42
26
22
46
67
24
47
35
31
21
31
32
37
27
22
35
40
39
52
40
40
35
33
41
25
26
57
34
30
29
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
0
1
1
0
0
1
1
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
1
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
0
1
0
0
0
1
1
1
0
1
1
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
1
0
1
1
0
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
1
34
25
59
46
29
37
34
39
29
25
64
56
38
22
41
33
33
35
36
52
67
41
30
22
68
64
42
53
42
58
38
21
60
20
35
22
30
60
62
44
25
55
31
43
31
42
57
59
43
37
58
53
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
1
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
0
0
0
1
1
0
0
1
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
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
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
1
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0
0
1
0
1
1
1
1
1
0
1
0
1
1
0
1
1
1
0
1
1
0
1
0
0
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
0
1
1
0
0
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
1
1
1
0
1
1
1
1
1
1
0
1
1
1
0
0
1
1
1
1
1
0
1
1
1
0
0
0
0
1
1
56
25
53
21
32
46
37
35
36
33
35
49
28
27
22
51
48
20
22
20
25
42
40
48
20
34
34
41
43
49
31
37
18
18
78
40
33
45
59
54
27
25
42
54
29
32
19
40
31
40
22
37
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
1
1
0
0
1
1
1
0
1
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
1
1
1
1
1
1
0
1
0
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
1
0
0
1
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
1
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
0
0
1
0
0
1
0
0
1
1
1
1
0
1
1
1
1
0
0
0
1
1
1
1
1
0
1
1
1
0
0
1
1
0
0
1
1
0
1
1
0
0
1
1
1
1
1
1
1
1
1
1
1
1
0
1
1
0
0
1
38
64
34
38
39
40
49
59
30
28
34
54
25
36
33
55
50
44
24
52
22
23
31
41
53
35
46
34
25
40
50
44
32
32
34
51
32
27
35
35
23
38
32
28
33
29
39
43
43
30
55
40
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
0
1
0
1
0
0
0
0
1
1
0
1
0
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
1
1
1
0
1
0
0
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
1
0
1
0
0
0
0
0
0
1
0
1
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
1
1
1
1
1
0
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
1
0
1
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
0
0
1
1
1
1
1
0
1
39
36
18
25
28
25
60
27
25
30
61
31
42
38
37
44
18
23
20
31
30
50
30
24
54
24
28
49
38
37
46
47
38
49
53
64
20
50
39
35
38
23
23
23
37
28
52
32
34
49
54
36
1
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
1
0
0
0
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
1
0
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
1
0
0
0
0
1
1
1
1
0
1
0
0
0
1
0
0
1
1
0
1
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
1
1
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
0
0
1
1
1
0
1
1
0
0
0
1
0
1
1
1
1
1
0
0
0
0
0
1
0
0
1
0
0
1
1
57
59
31
20
39
36
32
31
35
29
34
45
40
58
27
30
61
35
25
31
34
45
28
46
22
21
25
59
27
44
48
23
57
39
35
55
52
56
26
28
37
34
25
33
32
26
27
27
38
34
25
32
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
1
1
1
1
0
0
1
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
1
1
1
0
0
0
0
0
0
1
0
1
1
1
1
0
1
0
0
0
1
0
1
0
1
1
0
1
1
0
1
0
0
0
0
0
1
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
1
1
1
0
0
1
1
0
1
1
0
1
1
1
1
0
0
0
1
1
0
0
1
1
1
1
1
1
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
1
52
36
33
44
41
32
36
38
33
52
29
64
38
32
30
32
36
36
31
50
22
29
39
24
25
23
22
81
26
58
23
30
45
21
50
29
42
73
48
46
29
26
26
56
44
46
59
47
23
26
25
42
1
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
1
0
1
0
1
1
1
0
0
0
0
1
1
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
1
0
1
0
1
0
1
0
1
0
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
1
0
0
1
0
1
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
0
1
1
0
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
0
0
0
1
1
1
1
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
1
1
1
1
1
0
53
44
29
60
33
32
33
23
34
41
26
22
33
31
40
32
34
36
30
51
18
60
25
21
46
46
38
35
33
46
49
37
32
27
52
39
42
23
43
32
32
26
51
35
27
24
48
49
50
46
26
35
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
1
1
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
1
0
1
1
0
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
0
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
1
0
1
0
1
1
0
1
0
0
0
1
1
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
1
1
1
0
1
1
1
1
0
0
0
1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
0
0
1
1
1
0
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
0
0
40
43
25
22
42
47
45
44
24
66
42
29
32
48
57
32
26
33
51
46
30
25
41
45
44
53
40
39
39
24
23
20
55
52
44
25
40
32
33
40
45
26
32
31
62
56
25
24
35
34
44
34
0
0
0
1
1
0
0
0
1
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
1
0
0
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
1
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
1
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
0
1
1
1
1
1
1
0
1
1
0
1
0
1
0
1
1
1
1
0
1
1
0
1
1
0
31
25
27
62
38
34
44
47
54
43
41
33
38
37
32
42
41
34
36
48
44
71
22
24
24
41
44
35
19
42
39
22
28
41
34
40
21
24
60
40
36
26
32
66
59
28
27
68
44
68
56
66
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
1
0
0
0
0
1
0
1
0
1
0
0
1
0
0
1
1
0
1
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
0
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1
0
1
1
0
0
1
0
0
1
1
0
0
0
1
1
0
1
1
0
1
1
1
0
1
1
1
0
1
0
1
1
0
0
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
0
1
1
0
0
0
0
1
1
1
31
30
26
56
54
28
40
54
28
19
48
32
35
33
59
19
20
44
35
43
39
30
42
31
46
46
28
49
59
88
19
18
57
33
27
46
36
24
26
49
52
45
23
22
35
37
28
34
41
35
32
19
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
1
1
0
1
0
1
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
1
0
1
0
1
0
1
0
0
1
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
1
1
0
1
1
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
0
1
1
1
0
0
0
0
1
0
0
1
1
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
0
0
1
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
0
0
1
1
0
0
1
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
44
54
23
41
29
38
49
31
57
42
40
45
24
24
25
39
39
54
30
30
32
33
40
46
28
42
18
45
41
23
30
33
40
33
44
22
46
26
25
52
50
57
36
44
34
21
62
41
18
39
28
44
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
1
0
0
1
1
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
1
0
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
1
1
1
0
1
1
1
0
0
1
1
0
0
0
1
0
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
1
0
1
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
1
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
1
0
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
1
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
1
1
1
0
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
1
0
1
1
0
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
1
1
1
1
0
0
38
40
34
23
22
56
40
49
38
31
56
41
22
55
38
46
22
39
34
46
48
43
20
26
43
31
37
55
51
21
52
21
26
61
58
33
61
29
50
48
26
35
43
33
43
27
53
45
46
44
22
23
0
0
0
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
0
1
0
0
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
0
0
1
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
0
0
0
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
0
1
0
0
0
0
1
0
0
1
1
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
1
1
0
1
0
0
1
1
0
1
1
1
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
1
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
1
1
1
0
0
1
1
1
1
1
1
0
1
0
1
0
1
1
1
1
1
1
0
0
1
1
1
0
0
1
1
1
0
1
1
0
1
0
0
0
0
1
1
0
1
1
30
29
43
29
29
55
50
44
30
22
22
23
49
24
24
26
54
32
32
27
33
20
27
48
18
48
34
42
39
39
40
30
29
21
48
40
30
34
37
33
27
54
50
45
40
37
30
40
21
36
28
45
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
1
0
0
0
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
1
0
0
0
1
0
0
0
1
1
0
0
0
1
1
1
1
0
1
0
1
0
0
1
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
1
0
0
0
1
1
0
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
1
1
0
1
0
1
1
0
0
1
1
0
1
0
1
0
0
1
0
1
1
0
1
1
1
0
1
0
1
0
0
1
0
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
1
1
1
1
0
0
0
1
0
0
1
0
1
1
0
1
1
0
1
1
1
1
1
0
1
1
1
1
0
1
0
0
1
0
0
0
1
0
0
1
0
1
1
1
0
1
1
1
1
1
1
1
25
22
62
30
28
18
20
61
31
31
39
51
32
33
34
60
44
27
27
45
45
43
41
53
55
21
45
45
35
21
19
24
52
23
23
23
50
20
19
34
44
32
34
44
31
26
23
42
54
44
45
21
0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
1
0
0
0
0
0
1
1
1
0
1
0
0
0
1
0
0
1
0
0
0
1
0
0
1
1
1
0
0
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
0
0
0
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
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
1
1
1
1
0
0
1
0
0
1
0
0
1
1
0
1
0
0
0
1
0
1
1
0
0
0
1
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
1
0
0
1
1
0
1
1
1
0
1
0
0
1
1
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
1
1
1
1
0
1
1
1
1
1
1
1
0
1
0
1
1
1
0
1
0
1
1
1
0
1
0
1
1
0
0
0
1
1
1
1
1
0
0
1
1
0
1
1
1
1
1
1
1
0
35
49
26
41
42
20
47
47
32
28
33
35
36
35
29
48
34
33
73
66
46
20
34
24
27
39
18
40
27
64
35
77
33
36
40
27
22
72
22
33
32
50
40
32
32
26
20
37
33
43
40
25
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
1
1
1
1
0
0
0
1
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
1
0
0