3.1.b - Derivation of R-Squared

Variance Reduction
SST, SSM, and SSE
SST = SSE + SSM
r-Squared
r-Squared and Correlation
Correlation Between $Y$ and $\hat Y$

Variance Reduction

Assume that we have two variables, X and Y that are related according to the hypothetical model $Y = \beta_0 + \beta_1 X + \varepsilon$ . We collect a sample consisting of n paired observations of the form $(x_i,y_i)$ . We then use the sample to create a fitted model of the form $\hat Y = \hat \beta_0 + \hat \beta_1 X$ .

Assume we wish to make a prediction about the value of $Y$ for a new observation. Without considering the effect that $X$ has on $Y$ , our best point estimate for the new value of $Y$ would be $\bar y$ . To take into account the uncertainty that we know exists in our prediction, we could create a 95% prediction interval around our point prediction, $\bar y$ . Such an interval is shown in the plot on the left below. We will discuss how prediction intervals are formed in a later lesson.

If, however, we know the value of $X$ in the new observation, then a better estimate for the value of $Y$ would be given by $E[Y | X = x]= \beta_0 + \beta_1 x$ , which can be approximated using our fitted model. This gives us a point estimate of $\hat y = \hat \beta_0 + \hat \beta_1 x$ . Again, we know that there is some uncertainty in our prediction, so we might create a 95% prediction interval around the point prediction $\hat y$ . Such a prediction interval is shown in the plot on the right below.

Notice that the prediction interval in the plot on the right is considerably shorter than the one on the left. By taking into account the effect that $X$ has on $Y$ , we are able to reduce the uncertainty, or variance, in our prediction. This allows us to make more precise predictions.

In this lesson, we will discuss a method of measuring the amount of variance reduction we obtain in using a regression model to explain a portion of the variation in $Y$ through its relationship with $X$ .

SST, SSM, and SSE

We will use a quantity denoted by $r^2$ to measure the proportion of the variance in our response variable $Y$ that is explained by the relationship between $Y$ and a predictor $X$ . Before we define $r^2$ , we first need to introduce some related quantities.

For a particular observation $y_i$ , notice that the quantity $t_i = y_i - \bar y$ measures the amount by which the observation deviates from the sample mean. We will decompose this quantity into two pieces.

Let $m_i = \hat y_i - \bar y$ . The quantity $m_i$ is the portion of the deviaton $t_i$ that is explained by the regression model. You would expect the $y$ value to vary from $\bar y$ by this amount as a result of the effect of $x$ .
Let $\hat \varepsilon_i = y_i - \hat y_i$ . This is the residual associated with $y_i$ . It can be thought as the portion of the overall deviation $t_i$ that is left unexplained by our model.

Notice that $t_i = m_i + \hat \varepsilon_i$ .

We now sum the squares of each of these three quantities over all of the points in our sample.

Let $SST = \sum t_i^2 = \sum (y_i - \bar y)^2$
Let $SSM = \sum m_i^2 = \sum ( \hat y_i - \bar y)^2$
Let $SSE = \sum \hat \varepsilon_i^2 = \sum ( y_i - \hat y_i)^2$

SST = SSE + SSM

An important relationship between these three sums is given by the equation $SST = SSE + SSM$ .

To establish this result, we will need to make use of the two identities shown below. These identities are known as the normal equations and were derived in the notebook titled 3.1.a - Derivation of PArameter Estimates.Rmd.

$\sum \hat \varepsilon_i = 0$
$\sum \hat \varepsilon_i \hat y_i = 0$

The first identity is one of our two normal equations. The second identity can be derived from the two normal equations. Armed with these identities, we may procede with our proof that $SST = SSE + SSM$ as follows:

$\hspace{30pt} SST = \sum (y_i - \bar{y})^2$

$\hspace{30pt} SST = \sum [(\hat \varepsilon_i + \hat y_i) - \bar{y}]^2$

$\hspace{30pt} SST = \sum [\hat \varepsilon_i + (\hat y_i - \bar{y})]^2$

$\hspace{30pt} SST = \sum [\hat \varepsilon_i^2 + 2\hat \varepsilon_i (\hat y_i - \bar{y}) + ( \hat y_i - \bar y)^2]$

$\hspace{30pt} SST = \sum \hat \varepsilon_i^2 + 2\sum \hat \varepsilon_i (\hat y_i - \bar{y}) + \sum ( \hat y_i - \bar y)^2$

$\hspace{30pt} SST = SSE + 2 \sum( \hat \varepsilon_i \hat y_i - \hat \varepsilon_i\bar{y}) + SSM$

$\hspace{30pt} SST = SSE + 2 \sum \hat \varepsilon_i \hat y_i - 2 \bar{y}\sum\hat \varepsilon_i + SSM$

$\hspace{30pt} SST = SSE + 0 - 0 + SSM$

$\hspace{30pt} SST = SSE + SSM$

r-Squared

Intuitive explanations of the meaning of the variables $SST$ , $SSM$ , and $SSE$ are as follows:

$SST$ is a measure of the amount of variation in the response variable $Y$ .
$SSM$ is a measure of the variation in $Y$ that is explained by the regression model.
$SSE$ is a measure of the variation in $Y$ that is left unexplained by our model.

Ideally, we would like for $SSE$ to be close to 0 and for $SSM$ to thus be close to $SST$ . We can measure the proportion of the variance in $Y$ that is explained by our regression model using the following quantity:

$r^2 = \frac{SSM}{SST}$

Note that since $0 \leq SSM \leq SST$ , we get that $0 \leq r^2 \leq 1$ . The quantity $r^2$ is a diagnostic tool that is commonly uses to measure the quality of the fit in a regression model.

Notice that since $SST = SSM + SSE$ , we can rewrite the formula for $r^2$ as follows:

$r^2 = \frac{SSM}{SST} = 1 - \frac{SSE}{SSM}$

The $r^2 = 1 - \frac{SSE}{SSM}$ formula for $r^2$ is often the more useful of the two formulas, since we will have other reasons for calculating $SSE$ .

r-Squared and Correlation

The value $r^2$ is related to the sample correlation $\rho_{X,Y} = \mathrm{corr}[X,Y]$ . In fact, it can be shown that:

$r^2 = \mathrm{corr}[X,Y]$

To establish this result, we first need to derive an alternate form for the expression $SSM$ . Notice that:

$\hspace{30pt} SSM = \sum\limits_{i=1}^n (\hat y_i - \bar y)^2$

$\hspace{30pt} SSM = \sum\limits_{i=1}^n \left[\left(\hat \beta_0 + \hat \beta_1 x_i \right) - \bar y\right]^2$

$\hspace{30pt} SSM = \sum\limits_{i=1}^n \left[\left(\bar y - \hat\beta_1\bar x \right) + \hat \beta_1 x_i - \bar y\right]^2$

$\hspace{30pt} SSM = \sum\limits_{i=1}^n \left( - \hat\beta_1\bar x + \hat \beta_1 x_i\right)^2$

$\hspace{30pt} SSM = \beta_1^2 \sum\limits_{i=1}^n \left( x_i - \bar x\right)^2$

$\hspace{30pt} SSM = \beta_1^2 S_{XX}$

$\hspace{30pt} SSM = \left(\frac{S_{XY}}{S_{XX}} \right)^2 S_{XX}$

$\hspace{30pt} SSM = \frac{\left(S_{XY} \right)^2}{S_{XX}}$

Now, recall that $r^2 = \frac{SSM}{SST}$ . We will substitute the expression above in for $SSM$ , and then simplify.

$\hspace{30pt} r^2 = \frac{SSM}{SST}$

$\hspace{30pt} r^2 = \frac{\left(S_{XY} \right)^2}{S_{XX}} \frac{1}{SST}$

$\hspace{30pt} r^2 = \frac{\left(S_{XY} \right)^2}{S_{XX} \cdot SST}$

$\hspace{30pt} r^2 = \frac{\left(\sum\limits_{i=1}^n (x_i - \bar x)(y_i - \bar y) \right)^2}{\sum\limits_{i=1}^n (x_i - \bar x)^2 \cdot \sum\limits_{i=1}^n (y_i - \bar y)^2}$

$\hspace{30pt} r^2 = \left(\frac{\sum\limits_{i=1}^n (x_i - \bar x)(y_i - \bar y) }{\sqrt{\sum\limits_{i=1}^n (x_i - \bar x)^2} \cdot \sqrt{\sum\limits_{i=1}^n (y_i - \bar y)^2}} \right)^2$

$\hspace{30pt} r^2 = \left( \frac{\mathrm{cov}[X,Y]}{s_X s_Y} \right)^2$

$\hspace{30pt} r^2 = \left( \mathrm{corr}[X,Y] \right)^2$

This completes our proof.

Correlation Between $Y$ and $\hat Y$

It can also be shown that the correlation between the fitted value $\hat Y$ and the response $Y$ is exactly the same as that between the predictor $X$ and the response $Y$ . In other words:

$\mathrm{corr}\left[\hat Y,Y \right] = \mathrm{corr}\left[X,Y\right]$

The proof of this fact is left as an exercise.

LS0tDQp0aXRsZTogIjMuMS5iIC0gRGVyaXZhdGlvbiBvZiBSLVNxdWFyZWQiDQphdXRob3I6ICJSb2JiaWUgQmVhbmUiDQpvdXRwdXQ6DQogIGh0bWxfbm90ZWJvb2s6DQogICAgdGhlbWU6IGZsYXRseQ0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19kZXB0aDogNA0KLS0tDQoNCg0KDQojIyMgKipWYXJpYW5jZSBSZWR1Y3Rpb24qKg0KDQpBc3N1bWUgdGhhdCB3ZSBoYXZlIHR3byB2YXJpYWJsZXMsIGBYYCBhbmQgYFlgIHRoYXQgYXJlIHJlbGF0ZWQgYWNjb3JkaW5nIHRvIHRoZSBoeXBvdGhldGljYWwgbW9kZWwgJFkgPSBcYmV0YV8wICsgXGJldGFfMSBYICsgXHZhcmVwc2lsb24kLiBXZSBjb2xsZWN0IGEgc2FtcGxlIGNvbnNpc3Rpbmcgb2YgYG5gIHBhaXJlZCBvYnNlcnZhdGlvbnMgb2YgdGhlIGZvcm0gJCh4X2kseV9pKSQuIFdlIHRoZW4gdXNlIHRoZSBzYW1wbGUgdG8gY3JlYXRlIGEgZml0dGVkIG1vZGVsIG9mIHRoZSBmb3JtICRcaGF0IFkgPSBcaGF0IFxiZXRhXzAgKyBcaGF0IFxiZXRhXzEgWCQuDQoNCkFzc3VtZSB3ZSB3aXNoIHRvIG1ha2UgYSBwcmVkaWN0aW9uIGFib3V0IHRoZSB2YWx1ZSBvZiAkWSQgZm9yIGEgbmV3IG9ic2VydmF0aW9uLiBXaXRob3V0IGNvbnNpZGVyaW5nIHRoZSBlZmZlY3QgdGhhdCAkWCQgaGFzIG9uICRZJCwgb3VyIGJlc3QgcG9pbnQgZXN0aW1hdGUgZm9yIHRoZSBuZXcgdmFsdWUgb2YgJFkkIHdvdWxkIGJlICRcYmFyIHkkLiBUbyB0YWtlIGludG8gYWNjb3VudCB0aGUgdW5jZXJ0YWludHkgdGhhdCB3ZSBrbm93IGV4aXN0cyBpbiBvdXIgcHJlZGljdGlvbiwgd2UgY291bGQgY3JlYXRlIGEgOTUlIHByZWRpY3Rpb24gaW50ZXJ2YWwgYXJvdW5kIG91ciBwb2ludCBwcmVkaWN0aW9uLCAkXGJhciB5JC4gU3VjaCBhbiBpbnRlcnZhbCBpcyBzaG93biBpbiB0aGUgcGxvdCBvbiB0aGUgbGVmdCBiZWxvdy4gV2Ugd2lsbCBkaXNjdXNzIGhvdyBwcmVkaWN0aW9uIGludGVydmFscyBhcmUgZm9ybWVkIGluIGEgbGF0ZXIgbGVzc29uLiAgIA0KDQpJZiwgaG93ZXZlciwgd2Uga25vdyB0aGUgdmFsdWUgb2YgJFgkIGluIHRoZSBuZXcgb2JzZXJ2YXRpb24sIHRoZW4gYSBiZXR0ZXIgZXN0aW1hdGUgZm9yIHRoZSB2YWx1ZSBvZiAkWSQgd291bGQgYmUgZ2l2ZW4gYnkgJEVbWSB8IFggPSB4XT0gXGJldGFfMCArIFxiZXRhXzEgeCQsIHdoaWNoIGNhbiBiZSBhcHByb3hpbWF0ZWQgdXNpbmcgb3VyIGZpdHRlZCBtb2RlbC4gVGhpcyBnaXZlcyB1cyBhIHBvaW50IGVzdGltYXRlIG9mICRcaGF0IHkgPSBcaGF0IFxiZXRhXzAgKyBcaGF0IFxiZXRhXzEgeCQuIEFnYWluLCB3ZSBrbm93IHRoYXQgdGhlcmUgaXMgc29tZSB1bmNlcnRhaW50eSBpbiBvdXIgcHJlZGljdGlvbiwgc28gd2UgbWlnaHQgY3JlYXRlIGEgOTUlIHByZWRpY3Rpb24gaW50ZXJ2YWwgYXJvdW5kIHRoZSBwb2ludCBwcmVkaWN0aW9uICRcaGF0IHkkLiBTdWNoIGEgcHJlZGljdGlvbiBpbnRlcnZhbCBpcyBzaG93biBpbiB0aGUgcGxvdCBvbiB0aGUgcmlnaHQgYmVsb3cuIA0KDQpOb3RpY2UgdGhhdCB0aGUgcHJlZGljdGlvbiBpbnRlcnZhbCBpbiB0aGUgcGxvdCBvbiB0aGUgcmlnaHQgaXMgY29uc2lkZXJhYmx5IHNob3J0ZXIgdGhhbiB0aGUgb25lIG9uIHRoZSBsZWZ0LiBCeSB0YWtpbmcgaW50byBhY2NvdW50IHRoZSBlZmZlY3QgdGhhdCAkWCQgaGFzIG9uICRZJCwgd2UgYXJlIGFibGUgdG8gcmVkdWNlIHRoZSB1bmNlcnRhaW50eSwgb3IgdmFyaWFuY2UsIGluIG91ciBwcmVkaWN0aW9uLiBUaGlzIGFsbG93cyB1cyB0byBtYWtlIG1vcmUgcHJlY2lzZSBwcmVkaWN0aW9ucy4gDQoNCkluIHRoaXMgbGVzc29uLCB3ZSB3aWxsIGRpc2N1c3MgYSBtZXRob2Qgb2YgbWVhc3VyaW5nIHRoZSBhbW91bnQgb2YgdmFyaWFuY2UgcmVkdWN0aW9uIHdlIG9idGFpbiBpbiB1c2luZyBhIHJlZ3Jlc3Npb24gbW9kZWwgdG8gZXhwbGFpbiBhIHBvcnRpb24gb2YgdGhlIHZhcmlhdGlvbiBpbiAkWSQgdGhyb3VnaCBpdHMgcmVsYXRpb25zaGlwIHdpdGggJFgkLiANCg0KPGJyIC8+DQo8YnIgLz4NCg0KDQpgYGB7ciwgZWNobz1GQUxTRSwgd2FybmluZz1GQUxTRX0NCg0Kc2V0LnNlZWQoMykNCnggPC0gcnVuaWYoMjAsIDUsMTApDQp5IDwtIDEuMiArIDAuMyAqIHggKyBybm9ybSgyMCwgMCwgMC4xKQ0KeiA8LSAwICogeCANCg0KIyBDcmVhdGUgZmlyc3QgbW9kZWwNCm9uZXMgPC0gMCoxOjIwICsgMQ0KbW9kMSA8LSBsbSh5IH4gb25lcykNCnByZWQxIDwtIHByZWRpY3QobW9kMSwgbmV3ZGF0YSA9IGRhdGEuZnJhbWUob25lcz1jKDEpKSwgaW50ZXJ2YWw9J3ByZWRpY3Rpb24nLCBsZXZlbD0wLjk1KQ0KDQoNCiMgQ3JlYXRlIHNlY29uZCBtb2RlbA0KbW9kMiA8LSBsbSh5IH4geCkNCnByZWQyIDwtIHByZWRpY3QobW9kMiwgbmV3ZGF0YSA9IGRhdGEuZnJhbWUoeD1jKDYuNSkpLCBpbnRlcnZhbD0ncHJlZGljdGlvbicsIGxldmVsPTAuOTUpDQoNCiN5aGF0IDwtIHN1bShtb2QxJGNvZWZmaWNpZW50cyAqIGMoMSw2LjUpKQ0KDQojIERpc3BsYXkgcGxvdHMNCnBhcihtZnJvdz1jKDEsMikpDQoNCnBsb3QoeSB+IHosIHhheHQ9J24nLCB4bGFiPSIiLCB5bGltPWMoMi41LDQuNSksIHBjaD0xOSwgY29sPXJnYigwLDAsMSwwLjgpLCANCiAgICAgbWFpbj0iOTUlIFByZWRpY3Rpb24gSW50IGZvciBZICIpDQphYmxpbmUoaD1tZWFuKHkpLCBsdHk9MiwgY29sPSJyZWQiKQ0Kc2VnbWVudHMoMC4yNSxwcmVkMVsyXSwwLjI1LHByZWQxWzNdLCBsd2Q9NCwgY29sPSJEYXJrIE9yYW5nZSIpDQoNCnBsb3QoeSB+IHgsIHlsaW09YygyLjUsNC41KSwgcGNoPTE5LCBjb2w9cmdiKDAsMCwxLDAuOCksDQogICAgIG1haW49Ijk1JSBQcmVkaWN0aW9uIEludCBmb3IgWSwgXG4gR2l2ZW4gdGhhdCBYPTYuNSIpDQphYmxpbmUoaD1wcmVkMlsxXSwgbHR5PTIsIGNvbD0icmVkIikNCnNlZ21lbnRzKDYuNSxwcmVkMlsyXSw2LjUscHJlZDJbM10sIGx3ZD00LCBjb2w9IkRhcmsgT3JhbmdlIikNCg0KDQpgYGANCg0KDQojIyMgKipTU1QsIFNTTSwgYW5kIFNTRSoqDQoNCldlIHdpbGwgdXNlIGEgcXVhbnRpdHkgZGVub3RlZCBieSAkcl4yJCB0byBtZWFzdXJlIHRoZSBwcm9wb3J0aW9uIG9mIHRoZSB2YXJpYW5jZSBpbiBvdXIgcmVzcG9uc2UgdmFyaWFibGUgJFkkIHRoYXQgaXMgZXhwbGFpbmVkIGJ5IHRoZSByZWxhdGlvbnNoaXAgYmV0d2VlbiAkWSQgYW5kIGEgcHJlZGljdG9yICRYJC4gQmVmb3JlIHdlIGRlZmluZSAkcl4yJCwgd2UgZmlyc3QgbmVlZCB0byBpbnRyb2R1Y2Ugc29tZSByZWxhdGVkIHF1YW50aXRpZXMuIA0KDQpGb3IgYSBwYXJ0aWN1bGFyIG9ic2VydmF0aW9uICR5X2kkLCBub3RpY2UgdGhhdCB0aGUgcXVhbnRpdHkgJHRfaSA9IHlfaSAtIFxiYXIgeSQgbWVhc3VyZXMgdGhlIGFtb3VudCBieSB3aGljaCB0aGUgb2JzZXJ2YXRpb24gZGV2aWF0ZXMgZnJvbSB0aGUgc2FtcGxlIG1lYW4uIFdlIHdpbGwgZGVjb21wb3NlIHRoaXMgcXVhbnRpdHkgaW50byB0d28gcGllY2VzLiANCg0KKiBMZXQgJG1faSA9IFxoYXQgeV9pIC0gXGJhciB5JC4gVGhlIHF1YW50aXR5ICRtX2kkIGlzIHRoZSBwb3J0aW9uIG9mIHRoZSBkZXZpYXRvbiAkdF9pJCB0aGF0IGlzIGV4cGxhaW5lZCBieSB0aGUgcmVncmVzc2lvbiBtb2RlbC4gWW91IHdvdWxkIGV4cGVjdCB0aGUgJHkkIHZhbHVlIHRvIHZhcnkgZnJvbSAkXGJhciB5JCBieSB0aGlzIGFtb3VudCBhcyBhIHJlc3VsdCBvZiB0aGUgZWZmZWN0IG9mICR4JC4NCg0KKiBMZXQgJFxoYXQgXHZhcmVwc2lsb25faSA9IHlfaSAtIFxoYXQgeV9pJC4gVGhpcyBpcyB0aGUgcmVzaWR1YWwgYXNzb2NpYXRlZCB3aXRoICR5X2kkLiBJdCBjYW4gYmUgdGhvdWdodCBhcyB0aGUgcG9ydGlvbiBvZiB0aGUgb3ZlcmFsbCBkZXZpYXRpb24gJHRfaSQgdGhhdCBpcyBsZWZ0IHVuZXhwbGFpbmVkIGJ5IG91ciBtb2RlbC4gDQoNCk5vdGljZSB0aGF0ICR0X2kgPSBtX2kgKyBcaGF0IFx2YXJlcHNpbG9uX2kkLg0KDQpgYGB7ciwgZWNobz1GQUxTRX0NCnloYXQ4IDwtIHN1bShtb2QyJGNvZWZmaWNpZW50cypjKDEseFs5XSkpDQpwbG90KHlbOV0gfiB4WzldLCB4bGltPWMoNy41LDguNCksICB5bGltPWMoMy40LDMuNzUpLCBwY2g9MTksIGNleD0yLCBjb2w9ImJsdWUiLCB4bGFiPSIiLCB5bGFiPSIiKQ0KDQphYmxpbmUobW9kMiRjb2VmZmljaWVudHMpDQphYmxpbmUoaD1tZWFuKHkpLCBsdHk9MiwgY29sPSJyZWQiKQ0KDQpkID0gMC4xDQpzZWdtZW50cyh4WzldIC0gZCxtZWFuKHkpLHhbOV0gLSBkLHlbOV0sIGx3ZD0zLCBjb2w9ImRlZXBza3libHVlMyIpDQpzZWdtZW50cyh4WzldIC0gZCx5WzldLHhbOV0seVs5XSwgbHR5PTIsIGx3ZD0yLCBjb2w9ImRlZXBza3libHVlMyIpDQoNCnNlZ21lbnRzKHhbOV0gKyBkLG1lYW4oeSkseFs5XSArIGQseWhhdDgsIGx3ZD0zLCBjb2w9IkRhcmsgT3JhbmdlIikNCnNlZ21lbnRzKHhbOV0gKyBkLHloYXQ4LHhbOV0gKyBkLHlbOV0sIGx3ZD0zLCBjb2w9IkdyZWVuNCIpDQoNCnNlZ21lbnRzKHhbOV0seWhhdDgseFs5XSArIGQseWhhdDgsIGx0eT0yLCBsd2Q9MiwgY29sPSJEYXJrIE9yYW5nZSIpDQpzZWdtZW50cyh4WzldLHlbOV0seFs5XSArIGQseVs5XSwgbHR5PTIsIGx3ZD0yLCBjb2w9IkdyZWVuNCIpDQoNCnRleHQoNy42OSwzLjYzLCBleHByZXNzaW9uKHRbaV0gPT0geVtpXSAtIGJhcih5KSksIGNleD0xLjUsIGNvbD0iZGVlcHNreWJsdWUzIikgDQp0ZXh0KDguMDgsMy42NSwgZXhwcmVzc2lvbihoYXQoZSlbaV0gPT0geVtpXSAtIGhhdCh5KVtpXSksIGNleD0xLjUsIGNvbD0iR3JlZW40IikgDQp0ZXh0KDguMDgsMy41LCBleHByZXNzaW9uKG1baV0gPT0gaGF0KHkpW2ldIC0gYmFyKHkpKSwgY2V4PTEuNSwgY29sPSJEYXJrIE9yYW5nZSIpIA0KDQpwb2ludHMoeFs5XSx5WzldLCBwY2g9MTksIGNleD0yLCBjb2w9ImJsdWUiKQ0KcG9pbnRzKHhbOV0seWhhdDgsIHBjaD0xOSwgY2V4PTIpDQpgYGANCg0KV2Ugbm93IHN1bSB0aGUgc3F1YXJlcyBvZiBlYWNoIG9mIHRoZXNlIHRocmVlIHF1YW50aXRpZXMgb3ZlciBhbGwgb2YgdGhlIHBvaW50cyBpbiBvdXIgc2FtcGxlLg0KDQoqIExldCAkU1NUID0gXHN1bSB0X2leMiAgPSBcc3VtICh5X2kgLSBcYmFyIHkpXjIkDQoNCiogTGV0ICRTU00gPSBcc3VtIG1faV4yICA9IFxzdW0gKCBcaGF0IHlfaSAtIFxiYXIgeSleMiQNCg0KKiBMZXQgJFNTRSA9IFxzdW0gXGhhdCBcdmFyZXBzaWxvbl9pXjIgID0gXHN1bSAoIHlfaSAtIFxoYXQgeV9pKV4yJA0KDQoNCiMjIyAqKlNTVCA9IFNTRSArIFNTTSoqDQoNCkFuIGltcG9ydGFudCByZWxhdGlvbnNoaXAgYmV0d2VlbiB0aGVzZSB0aHJlZSBzdW1zIGlzIGdpdmVuIGJ5IHRoZSBlcXVhdGlvbiAkU1NUID0gU1NFICsgU1NNJC4gDQoNClRvIGVzdGFibGlzaCB0aGlzIHJlc3VsdCwgd2Ugd2lsbCBuZWVkIHRvIG1ha2UgdXNlIG9mIHRoZSB0d28gaWRlbnRpdGllcyBzaG93biBiZWxvdy4gVGhlc2UgaWRlbnRpdGllcyBhcmUga25vd24gYXMgdGhlICoqbm9ybWFsIGVxdWF0aW9ucyoqIGFuZCB3ZXJlIGRlcml2ZWQgaW4gdGhlIG5vdGVib29rIHRpdGxlZCAqKjMuMS5hIC0gRGVyaXZhdGlvbiBvZiBQQXJhbWV0ZXIgRXN0aW1hdGVzLlJtZCoqLiANCg0KKiAkXHN1bSBcaGF0IFx2YXJlcHNpbG9uX2kgPSAwJA0KDQoqICRcc3VtIFxoYXQgXHZhcmVwc2lsb25faSBcaGF0IHlfaSA9IDAkDQoNClRoZSBmaXJzdCBpZGVudGl0eSBpcyBvbmUgb2Ygb3VyIHR3byBub3JtYWwgZXF1YXRpb25zLiBUaGUgc2Vjb25kIGlkZW50aXR5IGNhbiBiZSBkZXJpdmVkIGZyb20gdGhlIHR3byBub3JtYWwgZXF1YXRpb25zLiBBcm1lZCB3aXRoIHRoZXNlIGlkZW50aXRpZXMsIHdlIG1heSBwcm9jZWRlIHdpdGggb3VyIHByb29mIHRoYXQgJFNTVCA9IFNTRSArIFNTTSQgYXMgZm9sbG93czoNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSAoeV9pIC0gXGJhcnt5fSleMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSBbKFxoYXQgXHZhcmVwc2lsb25faSArIFxoYXQgeV9pKSAtIFxiYXJ7eX1dXjIkDQoNCiRcaHNwYWNlezMwcHR9IFNTVCA9IFxzdW0gW1xoYXQgXHZhcmVwc2lsb25faSArIChcaGF0IHlfaSAtIFxiYXJ7eX0pXV4yJA0KDQokXGhzcGFjZXszMHB0fSBTU1QgPSBcc3VtIFtcaGF0IFx2YXJlcHNpbG9uX2leMiArIDJcaGF0IFx2YXJlcHNpbG9uX2kgKFxoYXQgeV9pIC0gXGJhcnt5fSkgKyAoIFxoYXQgeV9pIC0gXGJhciB5KV4yXSQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gXHN1bSBcaGF0IFx2YXJlcHNpbG9uX2leMiArIDJcc3VtIFxoYXQgXHZhcmVwc2lsb25faSAoXGhhdCB5X2kgLSBcYmFye3l9KSArIFxzdW0gKCBcaGF0IHlfaSAtIFxiYXIgeSleMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gU1NFICsgMiBcc3VtKCBcaGF0IFx2YXJlcHNpbG9uX2kgXGhhdCB5X2kgLSAgXGhhdCBcdmFyZXBzaWxvbl9pXGJhcnt5fSkgKyBTU00kDQoNCiRcaHNwYWNlezMwcHR9IFNTVCA9IFNTRSArIDIgXHN1bSBcaGF0IFx2YXJlcHNpbG9uX2kgXGhhdCB5X2kgLSAgMiBcYmFye3l9XHN1bVxoYXQgXHZhcmVwc2lsb25faSArIFNTTSQNCg0KJFxoc3BhY2V7MzBwdH0gU1NUID0gU1NFICsgMCAtIDAgKyBTU00kDQoNCiRcaHNwYWNlezMwcHR9IFNTVCA9IFNTRSArIFNTTSQNCg0KDQojIyMgKipyLVNxdWFyZWQqKg0KDQpJbnR1aXRpdmUgZXhwbGFuYXRpb25zIG9mIHRoZSBtZWFuaW5nIG9mIHRoZSB2YXJpYWJsZXMgJFNTVCQsICRTU00kLCBhbmQgJFNTRSQgYXJlIGFzIGZvbGxvd3M6DQoNCiogJFNTVCQgaXMgYSBtZWFzdXJlIG9mIHRoZSBhbW91bnQgb2YgdmFyaWF0aW9uIGluIHRoZSByZXNwb25zZSB2YXJpYWJsZSAkWSQuIA0KDQoqICRTU00kIGlzIGEgbWVhc3VyZSBvZiB0aGUgdmFyaWF0aW9uIGluICRZJCB0aGF0IGlzIGV4cGxhaW5lZCBieSB0aGUgcmVncmVzc2lvbiBtb2RlbC4gDQoNCiogJFNTRSQgaXMgYSBtZWFzdXJlIG9mIHRoZSB2YXJpYXRpb24gaW4gJFkkIHRoYXQgaXMgbGVmdCB1bmV4cGxhaW5lZCBieSBvdXIgbW9kZWwuIA0KDQpJZGVhbGx5LCB3ZSB3b3VsZCBsaWtlIGZvciAkU1NFJCB0byBiZSBjbG9zZSB0byAwIGFuZCBmb3IgJFNTTSQgdG8gdGh1cyBiZSBjbG9zZSB0byAkU1NUJC4gV2UgY2FuIG1lYXN1cmUgdGhlIHByb3BvcnRpb24gb2YgdGhlIHZhcmlhbmNlIGluICRZJCB0aGF0IGlzIGV4cGxhaW5lZCBieSBvdXIgcmVncmVzc2lvbiBtb2RlbCB1c2luZyB0aGUgZm9sbG93aW5nIHF1YW50aXR5Og0KDQokJHJeMiA9IFxmcmFje1NTTX17U1NUfSQkIA0KDQpOb3RlIHRoYXQgc2luY2UgJDAgXGxlcSBTU00gXGxlcSBTU1QkLCB3ZSBnZXQgdGhhdCAkMCBcbGVxIHJeMiBcbGVxIDEkLiBUaGUgcXVhbnRpdHkgJHJeMiQgaXMgYSBkaWFnbm9zdGljIHRvb2wgdGhhdCBpcyBjb21tb25seSB1c2VzIHRvIG1lYXN1cmUgdGhlIHF1YWxpdHkgb2YgdGhlIGZpdCBpbiBhIHJlZ3Jlc3Npb24gbW9kZWwuIA0KDQpOb3RpY2UgdGhhdCBzaW5jZSAkU1NUID0gU1NNICsgU1NFJCwgd2UgY2FuIHJld3JpdGUgdGhlIGZvcm11bGEgZm9yICRyXjIkIGFzIGZvbGxvd3M6DQoNCg0KJCRyXjIgPSBcZnJhY3tTU019e1NTVH0gPSAxIC0gXGZyYWN7U1NFfXtTU019JCQgDQoNClRoZSAkcl4yID0gMSAtIFxmcmFje1NTRX17U1NNfSQgZm9ybXVsYSBmb3IgJHJeMiQgaXMgb2Z0ZW4gdGhlIG1vcmUgdXNlZnVsIG9mIHRoZSB0d28gZm9ybXVsYXMsIHNpbmNlIHdlIHdpbGwgaGF2ZSBvdGhlciByZWFzb25zIGZvciBjYWxjdWxhdGluZyAkU1NFJC4gDQoNCg0KDQojIyMgKipyLVNxdWFyZWQgYW5kIENvcnJlbGF0aW9uKioNCg0KVGhlIHZhbHVlICRyXjIkIGlzIHJlbGF0ZWQgdG8gdGhlIHNhbXBsZSBjb3JyZWxhdGlvbiAkXHJob197WCxZfSA9IFxtYXRocm17Y29ycn1bWCxZXSQuIEluIGZhY3QsIGl0IGNhbiBiZSBzaG93biB0aGF0Og0KDQokJHJeMiA9IFxtYXRocm17Y29ycn1bWCxZXSQkDQoNClRvIGVzdGFibGlzaCB0aGlzIHJlc3VsdCwgd2UgZmlyc3QgbmVlZCB0byBkZXJpdmUgYW4gYWx0ZXJuYXRlIGZvcm0gZm9yIHRoZSBleHByZXNzaW9uICRTU00kLiBOb3RpY2UgdGhhdDoNCg0KJFxoc3BhY2V7MzBwdH0gU1NNID0gXHN1bVxsaW1pdHNfe2k9MX1ebiAoXGhhdCB5X2kgLSBcYmFyIHkpXjIkDQoNCiRcaHNwYWNlezMwcHR9IFNTTSA9IFxzdW1cbGltaXRzX3tpPTF9Xm4gXGxlZnRbXGxlZnQoXGhhdCBcYmV0YV8wICsgXGhhdCBcYmV0YV8xIHhfaSBccmlnaHQpIC0gXGJhciB5XHJpZ2h0XV4yJA0KDQokXGhzcGFjZXszMHB0fSBTU00gPSBcc3VtXGxpbWl0c197aT0xfV5uIFxsZWZ0W1xsZWZ0KFxiYXIgeSAtIFxoYXRcYmV0YV8xXGJhciB4IFxyaWdodCkgKyBcaGF0IFxiZXRhXzEgeF9pICAtIFxiYXIgeVxyaWdodF1eMiQNCg0KJFxoc3BhY2V7MzBwdH0gU1NNID0gXHN1bVxsaW1pdHNfe2k9MX1ebiBcbGVmdCggLSBcaGF0XGJldGFfMVxiYXIgeCAgKyBcaGF0IFxiZXRhXzEgeF9pXHJpZ2h0KV4yJA0KDQokXGhzcGFjZXszMHB0fSBTU00gPSBcYmV0YV8xXjIgXHN1bVxsaW1pdHNfe2k9MX1ebiBcbGVmdCggeF9pIC0gXGJhciB4XHJpZ2h0KV4yJA0KDQokXGhzcGFjZXszMHB0fSBTU00gPSBcYmV0YV8xXjIgU197WFh9JA0KDQokXGhzcGFjZXszMHB0fSBTU00gPSBcbGVmdChcZnJhY3tTX3tYWX19e1Nfe1hYfX0gXHJpZ2h0KV4yIFNfe1hYfSQNCg0KJFxoc3BhY2V7MzBwdH0gU1NNID0gXGZyYWN7XGxlZnQoU197WFl9IFxyaWdodCleMn17U197WFh9fSQNCg0KDQpOb3csIHJlY2FsbCB0aGF0ICRyXjIgPSBcZnJhY3tTU019e1NTVH0kLiBXZSB3aWxsIHN1YnN0aXR1dGUgdGhlIGV4cHJlc3Npb24gYWJvdmUgaW4gZm9yICRTU00kLCBhbmQgdGhlbiBzaW1wbGlmeS4gDQoNCiRcaHNwYWNlezMwcHR9IHJeMiA9IFxmcmFje1NTTX17U1NUfSQNCg0KJFxoc3BhY2V7MzBwdH0gcl4yID0gXGZyYWN7XGxlZnQoU197WFl9IFxyaWdodCleMn17U197WFh9fSBcZnJhY3sxfXtTU1R9JA0KDQokXGhzcGFjZXszMHB0fSByXjIgPSBcZnJhY3tcbGVmdChTX3tYWX0gXHJpZ2h0KV4yfXtTX3tYWH0gXGNkb3QgU1NUfSQNCg0KJFxoc3BhY2V7MzBwdH0gcl4yID0gXGZyYWN7XGxlZnQoU197WFl9IFxyaWdodCleMn17U197WFh9IFxjZG90IFNTVH0kDQoNCiRcaHNwYWNlezMwcHR9IHJeMiA9IFxmcmFje1xsZWZ0KFxzdW1cbGltaXRzX3tpPTF9Xm4gKHhfaSAtIFxiYXIgeCkoeV9pIC0gXGJhciB5KSBccmlnaHQpXjJ9e1xzdW1cbGltaXRzX3tpPTF9Xm4gKHhfaSAtIFxiYXIgeCleMiBcY2RvdCBcc3VtXGxpbWl0c197aT0xfV5uICh5X2kgLSBcYmFyIHkpXjJ9JA0KDQokXGhzcGFjZXszMHB0fSByXjIgPSBcbGVmdChcZnJhY3tcc3VtXGxpbWl0c197aT0xfV5uICh4X2kgLSBcYmFyIHgpKHlfaSAtIFxiYXIgeSkgfXtcc3FydHtcc3VtXGxpbWl0c197aT0xfV5uICh4X2kgLSBcYmFyIHgpXjJ9IFxjZG90IFxzcXJ0e1xzdW1cbGltaXRzX3tpPTF9Xm4gKHlfaSAtIFxiYXIgeSleMn19IFxyaWdodCleMiQNCg0KJFxoc3BhY2V7MzBwdH0gcl4yID0gXGxlZnQoIFxmcmFje1xtYXRocm17Y292fVtYLFldfXtzX1ggc19ZfSAgXHJpZ2h0KV4yJA0KDQokXGhzcGFjZXszMHB0fSByXjIgPSBcbGVmdCggXG1hdGhybXtjb3JyfVtYLFldICBccmlnaHQpXjIkDQoNClRoaXMgY29tcGxldGVzIG91ciBwcm9vZi4gDQoNCiMjIyAqKkNvcnJlbGF0aW9uIEJldHdlZW4gJFkkIGFuZCAkXGhhdCBZJCoqDQoNCkl0IGNhbiBhbHNvIGJlIHNob3duIHRoYXQgdGhlIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIGZpdHRlZCB2YWx1ZSAkXGhhdCBZJCBhbmQgdGhlIHJlc3BvbnNlICRZJCBpcyBleGFjdGx5IHRoZSBzYW1lIGFzIHRoYXQgYmV0d2VlbiB0aGUgcHJlZGljdG9yICRYJCBhbmQgdGhlIHJlc3BvbnNlICRZJC4gSW4gb3RoZXIgd29yZHM6DQoNCiQkXG1hdGhybXtjb3JyfVxsZWZ0W1xoYXQgWSxZIFxyaWdodF0gPSBcbWF0aHJte2NvcnJ9XGxlZnRbWCxZXHJpZ2h0XSQkDQoNClRoZSBwcm9vZiBvZiB0aGlzIGZhY3QgaXMgbGVmdCBhcyBhbiBleGVyY2lzZS4gDQoNCg0KDQoNCg0KDQoNCg0K