Image generated using OpenAI’s DALL-E.

Introduction

Welcome to the Matrix of Data, a realm where choices define reality, akin to the pivotal decision between the blue and red pills in ‘The Matrix’. Opting for the blue pill is like running regression through a statistical program – a path of convenience and surface understanding. But today, we choose the red pill, delving into the intricacies of Ordinary Least Squares (OLS) regression in matrix form. This choice, embodied in our replication of the example from Annex C of the G&P textbook1 using R, takes us on a transformative journey. It reveals the inner mechanics of the statistical system, akin to understanding the underlying code of the Matrix.

Dataset

Our canvas for this statistical artistry is a dataset from the “Economic Report of the President, January 1972, Table B-16.” Compact yet rich, this dataset is the perfect medium for our exploration, allowing us to maneuver through the nuances of matrix manipulations with ease.

Variable Definitions: - PER CAPITA PERSONAL CONSUMPTION EXPENDITURE (PPCE) - PER CAPITA PERSONAL DISPOSABLE INCOME (PPDI) in the United States, 1956–1970

Time Period Encoding: 1 corresponds to the year 1956 (1 = 1956).

Data Import

data=read.table("matrix.txt", header=T)
data

We now can put this in the matrix equation format:

\[ \left[\begin{array}{l} 1673 \\ 1688 \\ 1666 \\ 1735 \\ 1749 \\ 1756 \\ 1815 \\ 1867 \\ 1948 \\ 2048 \\ 2128 \\ 2165 \\ 2257 \\ 2316 \\ 2324 \end{array}\right]=\left[\begin{array}{llr} 1 & 1839 & 1 \\ 1 & 1844 & 2 \\ 1 & 1831 & 3 \\ 1 & 1881 & 4 \\ 1 & 1883 & 5 \\ 1 & 1910 & 6 \\ 1 & 1969 & 7 \\ 1 & 2016 & 8 \\ 1 & 2126 & 9 \\ 1 & 2239 & 10 \\ 1 & 2336 & 11 \\ 1 & 2404 & 12 \\ 1 & 2487 & 13 \\ 1 & 2535 & 14 \\ 1 & 2595 & 15 \end{array}\right] \quad\left[\begin{array}{l} \hat{\beta}_1 \\ \hat{\beta}_2 \\ \hat{\beta}_3 \end{array}\right]+\left[\begin{array}{l} \hat{u}_1 \\ \hat{u}_2 \\ \hat{u}_3 \\ \hat{u}_4 \\ \hat{u}_5 \\ \hat{u}_6 \\ \hat{u}_7 \\ \hat{u}_8 \\ \hat{u}_9 \\ \hat{u}_{10} \\ \hat{u}_{11} \\ \hat{u}_{12} \\ \hat{u}_{13} \\ \hat{u}_{14} \\ \hat{u}_{15} \end{array}\right] \]

We can obtain coefficient estimates with this formula:

\[ \hat{\beta}=\left(\mathbf{X}^{\prime} \mathbf{X}\right)^{-1} \mathbf{X}^{\prime} \mathbf{y} \] The formula includes two components: A) Gram Matrix or Normal Matrix: \(\left.\mathbf{X}^{\prime} \mathbf{X}\right)\); and B) Moment Matrix: \(\mathbf{X}^{\prime} \mathbf{y}\). \(\mathbf{X}\) itself called Design Matrix or just data matrix. Gram Matrix should be invertible, otherwise, we will not be able to calculate coefficient estimates. We can calculate each component of the estimator by step by step.

  • Step 1: Create Design Matrix
# Create Design X matrix and Y 

ones_column <- matrix(1, nrow = nrow(data), ncol = 1)
X= as.matrix(data[,-1])
y= as.matrix(data[,1])

X <- cbind(ones_column, X)
colnames(X) <- NULL

X = as.matrix(X)
X
      [,1] [,2] [,3]
 [1,]    1 1839    1
 [2,]    1 1844    2
 [3,]    1 1831    3
 [4,]    1 1881    4
 [5,]    1 1883    5
 [6,]    1 1910    6
 [7,]    1 1969    7
 [8,]    1 2016    8
 [9,]    1 2126    9
[10,]    1 2239   10
[11,]    1 2336   11
[12,]    1 2404   12
[13,]    1 2487   13
[14,]    1 2535   14
[15,]    1 2595   15
y
      [,1]
 [1,] 1673
 [2,] 1688
 [3,] 1666
 [4,] 1735
 [5,] 1749
 [6,] 1756
 [7,] 1815
 [8,] 1867
 [9,] 1948
[10,] 2048
[11,] 2128
[12,] 2165
[13,] 2257
[14,] 2316
[15,] 2324
  • Step 2: Create Gram Matrix
gram_matrix=t(X)%*%X
gram_matrix
      [,1]     [,2]   [,3]
[1,]    15    31895    120
[2,] 31895 68922513 272144
[3,]   120   272144   1240
  • Step 3: Create Moment Matrix
moment_matirx = t(X)%*%y

moment_matirx
         [,1]
[1,]    29135
[2,] 62905821
[3,]   247934
  • Step 3: Calculate Betas
beta_vector = solve(gram_matrix)%*%moment_matirx

beta_vector
            [,1]
[1,] 300.2862573
[2,]   0.7419808
[3,]   8.0435627

We got the following results:

\[ \hat{\boldsymbol{\beta}}=\left(\mathbf{X}^{\prime} \mathbf{X}\right)^{-1} \mathbf{X}^{\prime} \mathbf{y}=\left[\begin{array}{r} 300.28625 \\ 0.74198 \\ 8.04356 \end{array}\right] \] We can compare these results with those obtained using the lm() function.

model1 = lm(PPCE_Y ~PPDI_X2+Time_X3, data=data)
summary(model1)

Call:
lm(formula = PPCE_Y ~ PPDI_X2 + Time_X3, data = data)

Residuals:
    Min      1Q  Median      3Q     Max 
-22.380  -6.141   3.414   6.686  22.183 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 300.28626   78.31763   3.834  0.00238 ** 
PPDI_X2       0.74198    0.04753  15.610 2.46e-09 ***
Time_X3       8.04356    2.98355   2.696  0.01945 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 12.84 on 12 degrees of freedom
Multiple R-squared:  0.9976,    Adjusted R-squared:  0.9972 
F-statistic:  2514 on 2 and 12 DF,  p-value: < 2.2e-16

We can proceed to obtain additional statistics provided in the lm() output. As the next step, we will calculate the variance-covariance matrix using the following formula:

\[ \operatorname{var}-\operatorname{cov}(\hat{\boldsymbol{\beta}})=\hat{\sigma}^2\left(\mathbf{X}^{\prime} \mathbf{X}\right)^{-1} \] We already have gram matrix, but we need to calculate \(\hat{\sigma}^2\), which is unbiased estimator of homoscedastic variance \(u_i\). We can use the following formula for calculating \(\hat{\sigma}^2\):

\[ \begin{aligned} \hat{\sigma}^2 & =\frac{\sum \hat{u}_i^2}{n-k} \\ & =\frac{\hat{\mathbf{u}}^{\prime} \hat{\mathbf{u}}}{n-k} \end{aligned} \]

But for this formula, we need \(u\) (residuals), more specifically residual sum of squares (\(\hat{\mathbf{u}}^{\prime} \hat{\mathbf{u}}\)). We can use following formula for calculating RSS:

\[ \begin{aligned} \sum \hat{u}_i^2 & =\hat{\mathbf{u}}^{\prime} \hat{\mathbf{u}} \\ & =\mathbf{y}^{\prime} \mathbf{y}-\hat{\beta}^{\prime} \mathbf{X}^{\prime} \mathbf{y}\end{aligned} \]

rss = t(y)%*%y - t(beta_vector)%*%t(X)%*%y
rss
         [,1]
[1,] 1976.855

Hence, we can obtain \(\hat{\sigma}^2\) (we are dividing rss by degrees of freedom which is 12 in this case: n-k, where n is number of observations and k number of parameters):

sigma_hat_squared= as.numeric(rss/12)
sigma_hat_squared
[1] 164.7379

Finally, we can calculate variance-covariance matrix in the following way:

var_cov_beta = sigma_hat_squared * solve(gram_matrix)
var_cov_beta
            [,1]         [,2]        [,3]
[1,] 6133.650472 -3.707940917 220.2063033
[2,]   -3.707941  0.002259457  -0.1370522
[3,]  220.206303 -0.137052200   8.9015447

The diagonal elements of the variance-covariance matrix represents variances of coefficient estimates. If we take square roots of the absolute values of the diagonal elements, we will get respective standard errors for each estimate:


standard_errors <- sqrt(abs(diag(var_cov_beta)))
standard_errors
[1] 78.31762555  0.04753374  2.98354566

We can continue the process of calculating other components of the regression output and calculate \(R^2\). In matrix form, the formula looks in the following way:

\[ R^2=\frac{\hat{\boldsymbol{\beta}}^{\prime} \mathbf{X}^{\prime} \mathbf{y}-n \bar{Y}^2}{\mathbf{y}^{\prime} \mathbf{y}-n \bar{Y}^2} \] To remind you, in the numerator in above formula, we have ESS (explained sum of squares) and denominator is TSS (total sum of squares)

n=15
ESS = (t(beta_vector) %*% t(X) %*% y - n * (mean(y))^2)
TSS = (t(y) %*% y - n * (mean(y))^2)

r_squared = ESS/TSS


r_squared
          [,1]
[1,] 0.9976186

The F-test value can be calculated with this formula: \[ F=\frac{\left(\hat{\boldsymbol{\beta}}^{\prime} \mathbf{X}^{\prime} \mathbf{y}-n \bar{Y}^2\right) /(k-1)}{\left(\mathbf{y}^{\prime} \mathbf{y}-\hat{\boldsymbol{\beta}}^{\prime} \mathbf{X}^{\prime} \mathbf{y}\right) /(n-k)} \]

Which is simply the following:

\[ F=\frac{\operatorname{ESS} /(k-1)}{\operatorname{RSS} /(n-k)} \]

k=3  # degrees of freedom 

F = (ESS/(k-1))/(rss/(n-k))
F # pretty high 
         [,1]
[1,] 2513.521

Image generated using OpenAI’s DALL-E.

Epilogue: The Beginning of Our Matrix

As Morpheus revealed a deeper reality to Neo, so has our journey through linear regression in R unveiled the intricate matrix of data. Our venture, far from concluding, is merely the beginning. Like stepping through the looking glass, we have only begun to scratch the surface of a vast universe where numbers and patterns intertwine in a complex, yet harmonious dance. This exploration is not an end, but an invitation to a larger world of understanding — a world where, with each dataset and every line of R code, we continually awaken to the endless possibilities hidden within the data matrix.

References


  1. Gujarati, D. N., & Porter, D. C. (2008). Basic Econometrics (5th ed.). McGraw-Hill Education.↩︎

LS0tDQp0aXRsZTogJ1VudmVpbGluZyB0aGUgTWF0cml4OiBBIEpvdXJuZXkgaW50byBMaW5lYXIgUmVncmVzc2lvbiB3aXRoIFIgKFBhcnQgSSknDQphdXRob3I6ICJUYXRvIEtodW5kYWR6ZSINCm91dHB1dDoNCiAgaHRtbF9ub3RlYm9vazogZGVmYXVsdA0KICBwZGZfZG9jdW1lbnQ6IGRlZmF1bHQNCi0tLQ0KDQohW10oMTUucG5nKQ0KKkltYWdlIGdlbmVyYXRlZCB1c2luZyBPcGVuQUkncyBEQUxMLUUuKg0KDQoNCiMjIEludHJvZHVjdGlvbg0KDQpXZWxjb21lIHRvIHRoZSBNYXRyaXggb2YgRGF0YSwgYSByZWFsbSB3aGVyZSBjaG9pY2VzIGRlZmluZSByZWFsaXR5LCBha2luIHRvIHRoZSBwaXZvdGFsIGRlY2lzaW9uIGJldHdlZW4gdGhlIGJsdWUgYW5kIHJlZCBwaWxscyBpbiAnVGhlIE1hdHJpeCcuIE9wdGluZyBmb3IgdGhlIGJsdWUgcGlsbCBpcyBsaWtlIHJ1bm5pbmcgcmVncmVzc2lvbiB0aHJvdWdoIGEgc3RhdGlzdGljYWwgcHJvZ3JhbSDigJMgYSBwYXRoIG9mIGNvbnZlbmllbmNlIGFuZCBzdXJmYWNlIHVuZGVyc3RhbmRpbmcuIEJ1dCB0b2RheSwgd2UgY2hvb3NlIHRoZSByZWQgcGlsbCwgZGVsdmluZyBpbnRvIHRoZSBpbnRyaWNhY2llcyBvZiBPcmRpbmFyeSBMZWFzdCBTcXVhcmVzIChPTFMpIHJlZ3Jlc3Npb24gaW4gbWF0cml4IGZvcm0uIFRoaXMgY2hvaWNlLCBlbWJvZGllZCBpbiBvdXIgcmVwbGljYXRpb24gb2YgdGhlIGV4YW1wbGUgZnJvbSBBbm5leCBDIG9mIHRoZSBHJlAgdGV4dGJvb2tbXjFdIHVzaW5nIFIsIHRha2VzIHVzIG9uIGEgdHJhbnNmb3JtYXRpdmUgam91cm5leS4gSXQgcmV2ZWFscyB0aGUgaW5uZXIgbWVjaGFuaWNzIG9mIHRoZSBzdGF0aXN0aWNhbCBzeXN0ZW0sIGFraW4gdG8gdW5kZXJzdGFuZGluZyB0aGUgdW5kZXJseWluZyBjb2RlIG9mIHRoZSBNYXRyaXguIA0KDQojIyBEYXRhc2V0DQoNCk91ciBjYW52YXMgZm9yIHRoaXMgc3RhdGlzdGljYWwgYXJ0aXN0cnkgaXMgYSBkYXRhc2V0IGZyb20gdGhlICJFY29ub21pYyBSZXBvcnQgb2YgdGhlIFByZXNpZGVudCwgSmFudWFyeSAxOTcyLCBUYWJsZSBCLTE2LiIgQ29tcGFjdCB5ZXQgcmljaCwgdGhpcyBkYXRhc2V0IGlzIHRoZSBwZXJmZWN0IG1lZGl1bSBmb3Igb3VyIGV4cGxvcmF0aW9uLCBhbGxvd2luZyB1cyB0byBtYW5ldXZlciB0aHJvdWdoIHRoZSBudWFuY2VzIG9mIG1hdHJpeCBtYW5pcHVsYXRpb25zIHdpdGggZWFzZS4gDQoNCioqVmFyaWFibGUgRGVmaW5pdGlvbnM6KioNCi0gUEVSIENBUElUQSBQRVJTT05BTCBDT05TVU1QVElPTiBFWFBFTkRJVFVSRSAoUFBDRSkNCi0gUEVSIENBUElUQSBQRVJTT05BTCBESVNQT1NBQkxFIElOQ09NRSAoUFBESSkgaW4gdGhlIFVuaXRlZCBTdGF0ZXMsIDE5NTbigJMxOTcwDQoNCioqVGltZSBQZXJpb2QgRW5jb2Rpbmc6KiogMSBjb3JyZXNwb25kcyB0byB0aGUgeWVhciAxOTU2ICgxID0gMTk1NikuDQoNCg0KDQojIyMgRGF0YSBJbXBvcnQNCg0KYGBge3J9DQpkYXRhPXJlYWQudGFibGUoIm1hdHJpeC50eHQiLCBoZWFkZXI9VCkNCmRhdGENCmBgYA0KDQoNCldlIG5vdyBjYW4gcHV0IHRoaXMgaW4gdGhlIG1hdHJpeCBlcXVhdGlvbiBmb3JtYXQ6IA0KDQokJA0KXGxlZnRbXGJlZ2lue2FycmF5fXtsfQ0KMTY3MyBcXA0KMTY4OCBcXA0KMTY2NiBcXA0KMTczNSBcXA0KMTc0OSBcXA0KMTc1NiBcXA0KMTgxNSBcXA0KMTg2NyBcXA0KMTk0OCBcXA0KMjA0OCBcXA0KMjEyOCBcXA0KMjE2NSBcXA0KMjI1NyBcXA0KMjMxNiBcXA0KMjMyNA0KXGVuZHthcnJheX1ccmlnaHRdPVxsZWZ0W1xiZWdpbnthcnJheX17bGxyfQ0KMSAmIDE4MzkgJiAxIFxcDQoxICYgMTg0NCAmIDIgXFwNCjEgJiAxODMxICYgMyBcXA0KMSAmIDE4ODEgJiA0IFxcDQoxICYgMTg4MyAmIDUgXFwNCjEgJiAxOTEwICYgNiBcXA0KMSAmIDE5NjkgJiA3IFxcDQoxICYgMjAxNiAmIDggXFwNCjEgJiAyMTI2ICYgOSBcXA0KMSAmIDIyMzkgJiAxMCBcXA0KMSAmIDIzMzYgJiAxMSBcXA0KMSAmIDI0MDQgJiAxMiBcXA0KMSAmIDI0ODcgJiAxMyBcXA0KMSAmIDI1MzUgJiAxNCBcXA0KMSAmIDI1OTUgJiAxNQ0KXGVuZHthcnJheX1ccmlnaHRdIFxxdWFkXGxlZnRbXGJlZ2lue2FycmF5fXtsfQ0KXGhhdHtcYmV0YX1fMSBcXA0KXGhhdHtcYmV0YX1fMiBcXA0KXGhhdHtcYmV0YX1fMw0KXGVuZHthcnJheX1ccmlnaHRdK1xsZWZ0W1xiZWdpbnthcnJheX17bH0NClxoYXR7dX1fMSBcXA0KXGhhdHt1fV8yIFxcDQpcaGF0e3V9XzMgXFwNClxoYXR7dX1fNCBcXA0KXGhhdHt1fV81IFxcDQpcaGF0e3V9XzYgXFwNClxoYXR7dX1fNyBcXA0KXGhhdHt1fV84IFxcDQpcaGF0e3V9XzkgXFwNClxoYXR7dX1fezEwfSBcXA0KXGhhdHt1fV97MTF9IFxcDQpcaGF0e3V9X3sxMn0gXFwNClxoYXR7dX1fezEzfSBcXA0KXGhhdHt1fV97MTR9IFxcDQpcaGF0e3V9X3sxNX0NClxlbmR7YXJyYXl9XHJpZ2h0XQ0KJCQNCg0KDQpXZSBjYW4gb2J0YWluIGNvZWZmaWNpZW50IGVzdGltYXRlcyB3aXRoIHRoaXMgZm9ybXVsYToNCg0KJCQNClxoYXR7XGJldGF9PVxsZWZ0KFxtYXRoYmZ7WH1ee1xwcmltZX0gXG1hdGhiZntYfVxyaWdodCleey0xfSBcbWF0aGJme1h9XntccHJpbWV9IFxtYXRoYmZ7eX0NCiQkDQpUaGUgZm9ybXVsYSBpbmNsdWRlcyB0d28gY29tcG9uZW50czogQSkgKipHcmFtIE1hdHJpeCoqICBvciBOb3JtYWwgTWF0cml4OiAkXGxlZnQuXG1hdGhiZntYfV57XHByaW1lfSBcbWF0aGJme1h9XHJpZ2h0KSQ7IGFuZCBCKSAqKk1vbWVudCBNYXRyaXgqKjogJFxtYXRoYmZ7WH1ee1xwcmltZX0gXG1hdGhiZnt5fSQuICAkXG1hdGhiZntYfSQgaXRzZWxmIGNhbGxlZCAqKkRlc2lnbiBNYXRyaXgqKiBvciBqdXN0IGRhdGEgbWF0cml4LiAgR3JhbSBNYXRyaXggc2hvdWxkIGJlIGludmVydGlibGUsIG90aGVyd2lzZSwgd2Ugd2lsbCBub3QgYmUgYWJsZSB0byBjYWxjdWxhdGUgY29lZmZpY2llbnQgZXN0aW1hdGVzLiBXZSBjYW4gY2FsY3VsYXRlIGVhY2ggY29tcG9uZW50IG9mIHRoZSBlc3RpbWF0b3IgYnkgc3RlcCBieSBzdGVwLiANCg0KLSBTdGVwIDE6IENyZWF0ZSBEZXNpZ24gTWF0cml4IA0KDQpgYGB7cn0NCiMgQ3JlYXRlIERlc2lnbiBYIG1hdHJpeCBhbmQgWSANCg0Kb25lc19jb2x1bW4gPC0gbWF0cml4KDEsIG5yb3cgPSBucm93KGRhdGEpLCBuY29sID0gMSkNClg9IGFzLm1hdHJpeChkYXRhWywtMV0pDQp5PSBhcy5tYXRyaXgoZGF0YVssMV0pDQoNClggPC0gY2JpbmQob25lc19jb2x1bW4sIFgpDQpjb2xuYW1lcyhYKSA8LSBOVUxMDQoNClggPSBhcy5tYXRyaXgoWCkNClgNCnkNCmBgYA0KDQotIFN0ZXAgMjogQ3JlYXRlIEdyYW0gTWF0cml4DQoNCg0KYGBge3J9DQpncmFtX21hdHJpeD10KFgpJSolWA0KZ3JhbV9tYXRyaXgNCmBgYA0KDQotIFN0ZXAgMzogQ3JlYXRlIE1vbWVudCBNYXRyaXgNCg0KYGBge3J9DQptb21lbnRfbWF0aXJ4ID0gdChYKSUqJXkNCg0KbW9tZW50X21hdGlyeA0KYGBgDQoNCi0gU3RlcCAzOiBDYWxjdWxhdGUgQmV0YXMgDQoNCmBgYHtyfQ0KYmV0YV92ZWN0b3IgPSBzb2x2ZShncmFtX21hdHJpeCklKiVtb21lbnRfbWF0aXJ4DQoNCmJldGFfdmVjdG9yDQoNCmBgYA0KDQpXZSBnb3QgdGhlIGZvbGxvd2luZyByZXN1bHRzOiANCg0KDQokJA0KXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19PVxsZWZ0KFxtYXRoYmZ7WH1ee1xwcmltZX0gXG1hdGhiZntYfVxyaWdodCleey0xfSBcbWF0aGJme1h9XntccHJpbWV9IFxtYXRoYmZ7eX09XGxlZnRbXGJlZ2lue2FycmF5fXtyfQ0KMzAwLjI4NjI1IFxcDQowLjc0MTk4IFxcDQo4LjA0MzU2DQpcZW5ke2FycmF5fVxyaWdodF0NCiQkDQpXZSBjYW4gY29tcGFyZSB0aGVzZSByZXN1bHRzIHdpdGggdGhvc2Ugb2J0YWluZWQgdXNpbmcgdGhlIGBsbSgpYCBmdW5jdGlvbi4NCg0KYGBge3J9DQptb2RlbDEgPSBsbShQUENFX1kgflBQRElfWDIrVGltZV9YMywgZGF0YT1kYXRhKQ0Kc3VtbWFyeShtb2RlbDEpDQpgYGANCldlIGNhbiBwcm9jZWVkIHRvIG9idGFpbiBhZGRpdGlvbmFsIHN0YXRpc3RpY3MgcHJvdmlkZWQgaW4gdGhlIGxtKCkgb3V0cHV0LiBBcyB0aGUgbmV4dCBzdGVwLCB3ZSB3aWxsIGNhbGN1bGF0ZSB0aGUgKip2YXJpYW5jZS1jb3ZhcmlhbmNlIG1hdHJpeCoqIHVzaW5nIHRoZSBmb2xsb3dpbmcgZm9ybXVsYToNCg0KJCQNClxvcGVyYXRvcm5hbWV7dmFyfS1cb3BlcmF0b3JuYW1le2Nvdn0oXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19KT1caGF0e1xzaWdtYX1eMlxsZWZ0KFxtYXRoYmZ7WH1ee1xwcmltZX0gXG1hdGhiZntYfVxyaWdodCleey0xfQ0KJCQNCldlIGFscmVhZHkgaGF2ZSBncmFtIG1hdHJpeCwgYnV0IHdlIG5lZWQgdG8gY2FsY3VsYXRlICRcaGF0e1xzaWdtYX1eMiQsIHdoaWNoIGlzIHVuYmlhc2VkIGVzdGltYXRvciBvZiBob21vc2NlZGFzdGljIHZhcmlhbmNlICR1X2kkLiBXZSBjYW4gdXNlIHRoZSBmb2xsb3dpbmcgZm9ybXVsYSBmb3IgY2FsY3VsYXRpbmcgJFxoYXR7XHNpZ21hfV4yJDogDQoNCiQkDQpcYmVnaW57YWxpZ25lZH0NClxoYXR7XHNpZ21hfV4yICYgPVxmcmFje1xzdW0gXGhhdHt1fV9pXjJ9e24ta30gXFwNCiYgPVxmcmFje1xoYXR7XG1hdGhiZnt1fX1ee1xwcmltZX0gXGhhdHtcbWF0aGJme3V9fX17bi1rfQ0KXGVuZHthbGlnbmVkfQ0KJCQNCg0KQnV0IGZvciB0aGlzIGZvcm11bGEsIHdlIG5lZWQgJHUkIChyZXNpZHVhbHMpLCBtb3JlIHNwZWNpZmljYWxseSByZXNpZHVhbCBzdW0gb2Ygc3F1YXJlcyAoJFxoYXR7XG1hdGhiZnt1fX1ee1xwcmltZX0gXGhhdHtcbWF0aGJme3V9fSQpLiBXZSBjYW4gdXNlIGZvbGxvd2luZyBmb3JtdWxhIGZvciBjYWxjdWxhdGluZyBSU1M6IA0KDQokJA0KXGJlZ2lue2FsaWduZWR9IFxzdW0gXGhhdHt1fV9pXjIgJiA9XGhhdHtcbWF0aGJme3V9fV57XHByaW1lfSBcaGF0e1xtYXRoYmZ7dX19IFxcICYgPVxtYXRoYmZ7eX1ee1xwcmltZX0gXG1hdGhiZnt5fS1caGF0e1xiZXRhfV57XHByaW1lfSBcbWF0aGJme1h9XntccHJpbWV9IFxtYXRoYmZ7eX1cZW5ke2FsaWduZWR9DQokJA0KYGBge3J9DQpyc3MgPSB0KHkpJSoleSAtIHQoYmV0YV92ZWN0b3IpJSoldChYKSUqJXkNCnJzcw0KYGBgDQoNCkhlbmNlLCB3ZSBjYW4gb2J0YWluICRcaGF0e1xzaWdtYX1eMiQgKHdlIGFyZSBkaXZpZGluZyByc3MgYnkgZGVncmVlcyBvZiBmcmVlZG9tIHdoaWNoIGlzIDEyIGluIHRoaXMgY2FzZTogbi1rLCB3aGVyZSBuIGlzIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgYW5kIGsgbnVtYmVyIG9mIHBhcmFtZXRlcnMpOiANCg0KYGBge3J9DQpzaWdtYV9oYXRfc3F1YXJlZD0gYXMubnVtZXJpYyhyc3MvMTIpDQpzaWdtYV9oYXRfc3F1YXJlZA0KYGBgDQoNCkZpbmFsbHksIHdlIGNhbiBjYWxjdWxhdGUgdmFyaWFuY2UtY292YXJpYW5jZSBtYXRyaXggaW4gdGhlIGZvbGxvd2luZyB3YXk6DQoNCmBgYHtyfQ0KdmFyX2Nvdl9iZXRhID0gc2lnbWFfaGF0X3NxdWFyZWQgKiBzb2x2ZShncmFtX21hdHJpeCkNCnZhcl9jb3ZfYmV0YQ0KYGBgDQpUaGUgZGlhZ29uYWwgZWxlbWVudHMgb2YgdGhlIHZhcmlhbmNlLWNvdmFyaWFuY2UgbWF0cml4IHJlcHJlc2VudHMgdmFyaWFuY2VzIG9mIGNvZWZmaWNpZW50IGVzdGltYXRlcy4gSWYgd2UgdGFrZSBzcXVhcmUgcm9vdHMgb2YgdGhlIGFic29sdXRlIHZhbHVlcyBvZiB0aGUgZGlhZ29uYWwgZWxlbWVudHMsIHdlIHdpbGwgZ2V0IHJlc3BlY3RpdmUgc3RhbmRhcmQgZXJyb3JzIGZvciBlYWNoIGVzdGltYXRlOiANCg0KYGBge3J9DQoNCnN0YW5kYXJkX2Vycm9ycyA8LSBzcXJ0KGFicyhkaWFnKHZhcl9jb3ZfYmV0YSkpKQ0Kc3RhbmRhcmRfZXJyb3JzDQoNCmBgYA0KDQpXZSBjYW4gY29udGludWUgdGhlIHByb2Nlc3Mgb2YgY2FsY3VsYXRpbmcgb3RoZXIgY29tcG9uZW50cyBvZiB0aGUgcmVncmVzc2lvbiBvdXRwdXQgYW5kIGNhbGN1bGF0ZSAkUl4yJC4gSW4gbWF0cml4IGZvcm0sIHRoZSBmb3JtdWxhIGxvb2tzIGluIHRoZSBmb2xsb3dpbmcgd2F5OiANCg0KJCQNClJeMj1cZnJhY3tcaGF0e1xib2xkc3ltYm9se1xiZXRhfX1ee1xwcmltZX0gXG1hdGhiZntYfV57XHByaW1lfSBcbWF0aGJme3l9LW4gXGJhcntZfV4yfXtcbWF0aGJme3l9XntccHJpbWV9IFxtYXRoYmZ7eX0tbiBcYmFye1l9XjJ9DQokJA0KVG8gcmVtaW5kIHlvdSwgaW4gdGhlIG51bWVyYXRvciBpbiBhYm92ZSBmb3JtdWxhLCB3ZSBoYXZlIEVTUyAoZXhwbGFpbmVkIHN1bSBvZiBzcXVhcmVzKSBhbmQgZGVub21pbmF0b3IgaXMgVFNTICh0b3RhbCBzdW0gb2Ygc3F1YXJlcykNCg0KYGBge3J9DQpuPTE1DQpFU1MgPSAodChiZXRhX3ZlY3RvcikgJSolIHQoWCkgJSolIHkgLSBuICogKG1lYW4oeSkpXjIpDQpUU1MgPSAodCh5KSAlKiUgeSAtIG4gKiAobWVhbih5KSleMikNCg0Kcl9zcXVhcmVkID0gRVNTL1RTUw0KDQoNCnJfc3F1YXJlZA0KYGBgDQoNClRoZSBGLXRlc3QgdmFsdWUgY2FuIGJlIGNhbGN1bGF0ZWQgd2l0aCB0aGlzIGZvcm11bGE6IA0KJCQNCkY9XGZyYWN7XGxlZnQoXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19XntccHJpbWV9IFxtYXRoYmZ7WH1ee1xwcmltZX0gXG1hdGhiZnt5fS1uIFxiYXJ7WX1eMlxyaWdodCkgLyhrLTEpfXtcbGVmdChcbWF0aGJme3l9XntccHJpbWV9IFxtYXRoYmZ7eX0tXGhhdHtcYm9sZHN5bWJvbHtcYmV0YX19XntccHJpbWV9IFxtYXRoYmZ7WH1ee1xwcmltZX0gXG1hdGhiZnt5fVxyaWdodCkgLyhuLWspfQ0KJCQNCg0KDQpXaGljaCBpcyBzaW1wbHkgdGhlIGZvbGxvd2luZzogDQoNCiQkDQpGPVxmcmFje1xvcGVyYXRvcm5hbWV7RVNTfSAvKGstMSl9e1xvcGVyYXRvcm5hbWV7UlNTfSAvKG4tayl9DQokJA0KDQpgYGB7cn0NCms9MyAgIyBkZWdyZWVzIG9mIGZyZWVkb20gDQoNCkYgPSAoRVNTLyhrLTEpKS8ocnNzLyhuLWspKQ0KRiANCg0KDQpgYGANCg0KIVtdKDE3LnBuZykNCipJbWFnZSBnZW5lcmF0ZWQgdXNpbmcgT3BlbkFJJ3MgREFMTC1FLioNCg0KIyMgRXBpbG9ndWU6IFRoZSBCZWdpbm5pbmcgb2YgT3VyIE1hdHJpeA0KDQpBcyBNb3JwaGV1cyByZXZlYWxlZCBhIGRlZXBlciByZWFsaXR5IHRvIE5lbywgc28gaGFzIG91ciBqb3VybmV5IHRocm91Z2ggbGluZWFyIHJlZ3Jlc3Npb24gaW4gUiB1bnZlaWxlZCB0aGUgaW50cmljYXRlIG1hdHJpeCBvZiBkYXRhLiBPdXIgdmVudHVyZSwgZmFyIGZyb20gY29uY2x1ZGluZywgaXMgbWVyZWx5IHRoZSBiZWdpbm5pbmcuIExpa2Ugc3RlcHBpbmcgdGhyb3VnaCB0aGUgbG9va2luZyBnbGFzcywgd2UgaGF2ZSBvbmx5IGJlZ3VuIHRvIHNjcmF0Y2ggdGhlIHN1cmZhY2Ugb2YgYSB2YXN0IHVuaXZlcnNlIHdoZXJlIG51bWJlcnMgYW5kIHBhdHRlcm5zIGludGVydHdpbmUgaW4gYSBjb21wbGV4LCB5ZXQgaGFybW9uaW91cyBkYW5jZS4gVGhpcyBleHBsb3JhdGlvbiBpcyBub3QgYW4gZW5kLCBidXQgYW4gaW52aXRhdGlvbiB0byBhIGxhcmdlciB3b3JsZCBvZiB1bmRlcnN0YW5kaW5nIOKAlCBhIHdvcmxkIHdoZXJlLCB3aXRoIGVhY2ggZGF0YXNldCBhbmQgZXZlcnkgbGluZSBvZiBSIGNvZGUsIHdlIGNvbnRpbnVhbGx5IGF3YWtlbiB0byB0aGUgZW5kbGVzcyBwb3NzaWJpbGl0aWVzIGhpZGRlbiB3aXRoaW4gdGhlIGRhdGEgbWF0cml4Lg0KDQojIyBSZWZlcmVuY2VzDQoNClteMV06IEd1amFyYXRpLCBELiBOLiwgJiBQb3J0ZXIsIEQuIEMuICgyMDA4KS4gKkJhc2ljIEVjb25vbWV0cmljcyogKDV0aCBlZC4pLiBNY0dyYXctSGlsbCBFZHVjYXRpb24uDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0K