Load Data

The Prostate data can be found [here]. The data is to examine the correlation between the level of prostate-specific antigen and a number of clinical measures in men who were about to receive a radical prostatectomy.

  • lcavol: log cancer volume
  • lweight: log prostate weight
  • age: in years
  • lbph: log of the amount of benign prostatic hyperplasia
  • svi: seminal vesicle invasion
  • lcp: log of capsular penetration
  • gleason: a numeric vector
  • pgg45: percent of Gleason score 4 or 5
  • lpsa: response

The first 8 columns are predictors; column 9 is the outcome/response. We do not use column 10, which indicates which 67 observations were used as the “training set” and which 30 as the test set, as described on page 48 in the ESL book.

myData = read.table(file = "https://hastie.su.domains/ElemStatLearn/datasets/prostate.data", header = TRUE)
dim(myData)
names(myData)

Remove column 10 and run a quick summary of each column of the data. For convenience, we rename the response column with a generic name Y.

myData = myData[, -10]
names(myData)[9] = 'Y'
summary(myData)

Produce a pair-wise scatter plot. Caution: a big figure.

pairs(myData, pch='.')

Fit a Linear Model

Fit a linear regression model using all the predictors and print the summary of the LS results

lmfit <-  lm(Y ~ ., data = myData)
summary(lmfit)

Call:
lm(formula = Y ~ ., data = myData)

Residuals:
     Min       1Q   Median       3Q      Max 
-1.76644 -0.35510 -0.00328  0.38087  1.55770 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)  0.181561   1.320568   0.137  0.89096    
lcavol       0.564341   0.087833   6.425 6.55e-09 ***
lweight      0.622020   0.200897   3.096  0.00263 ** 
age         -0.021248   0.011084  -1.917  0.05848 .  
lbph         0.096713   0.057913   1.670  0.09848 .  
svi          0.761673   0.241176   3.158  0.00218 ** 
lcp         -0.106051   0.089868  -1.180  0.24115    
gleason      0.049228   0.155341   0.317  0.75207    
pgg45        0.004458   0.004365   1.021  0.31000    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.6995 on 88 degrees of freedom
Multiple R-squared:  0.6634,    Adjusted R-squared:  0.6328 
F-statistic: 21.68 on 8 and 88 DF,  p-value: < 2.2e-16

Check what are returned by lm and learn how to retrieve those results.

names(lmfit)  # What are returned by "lm"?
 [1] "coefficients"  "residuals"     "effects"       "rank"          "fitted.values"
 [6] "assign"        "qr"            "df.residual"   "xlevels"       "call"         
[11] "terms"         "model"        
names(summary(lmfit)) # What are returned by the summary of lmfit
 [1] "call"          "terms"         "residuals"     "coefficients"  "aliased"      
 [6] "sigma"         "df"            "r.squared"     "adj.r.squared" "fstatistic"   
[11] "cov.unscaled" 
# Regression coefficients including the intercept
lmfit$coef    
lmfit$residuals[1]
length(lmfit$residuals)

Check the calculation for Residual standard error and Multiple R-squared in the summary output: \[ \sigma = \sqrt{\frac{\sum_{i=1}^n r_i^2}{n - p-1}}, \quad p = \text{ # of non-intercept predictors} \] \[ R^2 = \frac{\sum_{i=1}^n r_i^2}{\sum_{i=1}^n (y_i - \bar{y})^2} = \frac{\sum_{i=1}^n r_i^2}{\text{SampleVar}(y_i)\times (n-1)} = \frac{\text{SampleVar}(r_i)}{\text{SampleVar}(y_i)} \]

n = dim(myData)[1]
p = dim(myData)[2] - 1
# Residual standard error
c(sqrt(sum(lmfit$residuals^2)/(n- p - 1)), summary(lmfit)$sigma)  
# R-squared
c(1 - sum(lmfit$residuals^2)/(var(myData$Y)*(n-1)), summary(lmfit)$r.squared) 
1 - var(lmfit$residuals)/var(myData$Y)

Prediction

Predicting responses for new observations can be accomplished through two methods:

  • Method 1: Begin by organizing the new observations into a matrix or vector. Then, apply the following formula: newX * beta + beta0, where (beta0, beta) represent the coefficients obtained through LS regression.

  • Method 2: Alternatively, structure the new observations as a data frame with identical column names as those in myData. Subsequently, utilize the predict function.

To exemplify these methods, we consider two novel patients. One individual is 50 years old, while the other is 70 years old. All other attributes assume median values from the existing dataset encompassing 97 patients.

Method 1

apply(myData, 2, median)
    lcavol    lweight        age       lbph        svi        lcp    gleason 
 1.4469190  3.6230070 65.0000000  0.3001046  0.0000000 -0.7985077  7.0000000 
     pgg45          Y 
15.0000000  2.5915164 
newx1 = c(1.45, 3.62, 50, 0.30, 0, -0.80, 7, 15) #1st patient: age = 50
newx2 = newx1
newx2[3] = 70 #2nd patient: age = 70
newx = rbind(newx1, newx2)
newx %*% lmfit$coef[-1] + lmfit$coef[1]
          [,1]
newx1 2.714471
newx2 2.289507

Method 2

newdf = data.frame(newx)
names(newdf) = names(myData[, -dim(myData)[2]]) # assign col names after dropping the last col

An advantage of the predict function is that once columns have names, their order does not matter. So, let’s shuffle the columns of newdf and then predict. The result should be the same as what is returned by Method 1.

newdf
newdf = newdf[, sample(1:dim(newdf)[2])]
newdf
predict(lmfit, newdata = newdf)

Rank Deficiency

In cases where the design matrix, including the intercept, does not have full rank, the coefficient vector returned by R will contain some NA elements. An NA estimate for a column signifies that that column can be written as a linear combination of preceding columns, rendering it redundant.

NA values do not indicate errors. They simply indicate that in the LS fitting process, R discards columns with NA coefficients. However, this doesn’t hinder the utility of the fitted model for prediction purposes. The predictions derived from this model will align with those obtained from fitting a linear regression model excluding the columns with NA coefficients.

## Add a fake column named "junk", which is a linear combination of the first two predictors
myData$junk <-  myData[, 1] + myData[, 2]
tmp.lm <-  lm(Y ~ ., myData)
summary(tmp.lm)

The fitted values from the original lmfit and the new fit tmp.lim are the same.

tmp.lm$fitted[1:3]
lmfit$fitted[1:3]

## drop the "junk" column
myData = myData[, !names(myData) == 'junk' ]

Training vs Test Errors

In linear regression models, as we introduce more variables, training error (measured by RSS or MSE) consistently decreases. However, this reduction in training error does not guarantee a corresponding decrease in test error, which measures prediction accuracy on independent test data. To demonstrate this, we randomly split our dataset into 60% training and 40% test portions, progressively adding predictors. This approach highlights how additional predictors can lower training error while test error may not follow the same trend.

n <- dim(myData)[1] # sample size
p <-  dim(myData)[2] - 1 # number of non-intercept predictors

ntrain <-  round(n*0.6)
train.id <-  sample(1:n, ntrain)
train.MSE <-  rep(0, p)
test.MSE <-  rep(0, p)

for(i in 1:p){
  myfit <-  lm(Y ~ ., myData[train.id, c(1:i, (p+1))])
  train.Y <-  myData[train.id, (p+1)]
  train.Y.pred <-  myfit$fitted
  train.MSE[i] <-  mean((train.Y - train.Y.pred)^2)
  
  test.Y <-  myData[-train.id, (p+1)]
  test.Y.pred <-  predict(myfit, newdata = myData[-train.id, ])
  test.MSE[i] <-  mean((test.Y - test.Y.pred)^2)
}

## type="n": don't plot; just set the plotting region
  plot(c(1, p), range(train.MSE, test.MSE), type="n", xlab="# of variables", ylab="MSE")
  points(train.MSE, col = "blue", pch = 1)
  lines(train.MSE, col = "blue", pch = 1)
  points(test.MSE, col = "red", pch = 2)
  lines(test.MSE, col = "red", pch = 2)

Feel free to run the provided code multiple times. You’ll observe the following patterns:

  • In most instances, the blue line (representing training error) tends to be positioned below the red line (representing test error), indicating that the training error is generally superior to the test error. However, due to the inherent randomness, there might be instances where the red line falls below the blue line, indicating that the test error outperforms the training error occasionally.

  • In each iteration, the blue line consistently exhibits a monotonically decreasing trend, signifying the reduction of training error as more predictors are incorporated. On the other hand, the red line’s trajectory may not uniformly decrease. Upon closer examination of the differences between adjacent terms, you’ll observe negative values consistently for the blue line, but for the red line, these differences might encompass some positive values.

diff(train.MSE) ## always negative
diff(test.MSE)  ## not always negative

Interpret LS Coefficients

How to interpret LS coefficients? LS coefficients express how changes in predictors affect the response while holding all other predictors constant. For instance, the coefficient for age quantifies the average change in the response variable for each year increase in age, holding all other predictors constant.

It’s noteworthy that results from Simple Linear Regression (SLR), which involves only one non-intercept predictor, might differ from results in Multiple Linear Regression (MLR), which incorporates multiple predictors. This divergence can arise due to correlations among predictors.

For instance, consider the case where age is positively correlated with some predictors that have a positive effect on the response. In a joint model (MLR), the coefficient for age appears negative, seemingly contrary to its positive effect in an isolated model (SLR). This adjustment compensates for the positive contribution introduced by other predictors, ensuring that the overall model accurately represents the relationships between predictors and the response variable.

summary(lm(Y~ age, myData))

Call:
lm(formula = Y ~ age, data = myData)

Residuals:
     Min       1Q   Median       3Q      Max 
-2.90738 -0.71234  0.06967  0.66187  2.99584 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)  
(Intercept)  0.79906    1.00793   0.793   0.4299  
age          0.02629    0.01568   1.677   0.0968 .
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.144 on 95 degrees of freedom
Multiple R-squared:  0.02876,   Adjusted R-squared:  0.01854 
F-statistic: 2.813 on 1 and 95 DF,  p-value: 0.09677
round(cor(myData), dig=2)
        lcavol lweight  age  lbph   svi   lcp gleason pgg45    Y
lcavol    1.00    0.28 0.22  0.03  0.54  0.68    0.43  0.43 0.73
lweight   0.28    1.00 0.35  0.44  0.16  0.16    0.06  0.11 0.43
age       0.22    0.35 1.00  0.35  0.12  0.13    0.27  0.28 0.17
lbph      0.03    0.44 0.35  1.00 -0.09 -0.01    0.08  0.08 0.18
svi       0.54    0.16 0.12 -0.09  1.00  0.67    0.32  0.46 0.57
lcp       0.68    0.16 0.13 -0.01  0.67  1.00    0.51  0.63 0.55
gleason   0.43    0.06 0.27  0.08  0.32  0.51    1.00  0.75 0.37
pgg45     0.43    0.11 0.28  0.08  0.46  0.63    0.75  1.00 0.42
Y         0.73    0.43 0.17  0.18  0.57  0.55    0.37  0.42 1.00

Partial Regression Coef

Check how to retrieve the LS coefficient for age using Algorithm 3.1

y.star <-  lm(Y ~ ., data = subset(myData, select = -age))$res
age.star <-  lm(age ~ ., data = subset(myData, select = -Y))$res
tmpfit <-  lm(y.star ~ age.star)

The LS coefficient for age (from lmfit) is the same as the one from tmpfit. The residuals from the two LS models are also the same.

tmpfit$coef
sum((lmfit$res - tmpfit$res)^2)

F-test

Test a single predictor (in this case, F-test = t-test).

lmfit0 <- lm(Y ~ ., data = subset(myData, select = -age))
anova(lmfit0, lmfit)

Test multiple predictors.

lmfit0 <- lm(Y ~ ., data = myData[, -c(1:3)])
anova(lmfit0, lmfit)

Collinearity

Check the Car Seat Position Data from faraway package.

Car drivers like to adjust the seat position for their own comfort. Car designers would find it helpful to know how different drivers will position the seat depending on their size and age. Researchers at the HuMoSim laboratory at the University of Michigan collected data on 38 drivers.

  • Age:
  • Weight:
  • HtShoes: height with shoes in cm
  • Ht: height without shoes in cm
  • Seated: seated height in cm
  • Arm: lower arm length in cm
  • Thigh: thigh length in cm
  • Leg: lower leg length in cm
  • hipcenter: horizontal distance of the midpoint of the hips from a fixed location in the car in mm

The researchers were interested in determining if a relationship exists between hipcenter and the other variables. Due to the high correlations among the predictors, we see high R-square, significant overall F-test, but no individual variables are significant.

library(faraway)
data(seatpos)
pairs(seatpos, pch = ".")
summary(lm(hipcenter ~ . , data=seatpos))
## check pairwise correlation
round(cor(seatpos), dig=2)

If we remove some (almost) redundant variables, the LS results make much more sense.

summary(lm(hipcenter ~ Age + Weight + Ht + Seated, data=seatpos))
summary(lm(hipcenter ~ Ht, data=seatpos))
LS0tCnRpdGxlOiAiUFNMOiBMaW5lYXIgUmVncmVzc2lvbiIKZGF0ZTogIkZhbGwgMjAyMyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICB0aGVtZTogcmVhZGFibGUKICAgIHRvYzogVFJVRQogICAgdG9jX2Zsb2F0OiBUUlVFCi0tLQoKIyMgTG9hZCBEYXRhCgpUaGUgKipQcm9zdGF0ZSBkYXRhKiogY2FuIGJlIGZvdW5kIFtbaGVyZV0oaHR0cHM6Ly9oYXN0aWUuc3UuZG9tYWlucy9FbGVtU3RhdExlYXJuL2RhdGEuaHRtbCldLiBUaGUgZGF0YSBpcyB0byBleGFtaW5lIHRoZSBjb3JyZWxhdGlvbiBiZXR3ZWVuIHRoZSBsZXZlbCBvZiBwcm9zdGF0ZS1zcGVjaWZpYyBhbnRpZ2VuIGFuZCBhIG51bWJlciBvZiBjbGluaWNhbCBtZWFzdXJlcyBpbiBtZW4gd2hvIHdlcmUgYWJvdXQgdG8gcmVjZWl2ZSBhIHJhZGljYWwgcHJvc3RhdGVjdG9teS4KCi0gYGxjYXZvbGA6ICBsb2cgY2FuY2VyIHZvbHVtZQotIGBsd2VpZ2h0YDogbG9nIHByb3N0YXRlIHdlaWdodAotIGBhZ2VgOiBpbiB5ZWFycwotIGBsYnBoYDogbG9nIG9mIHRoZSBhbW91bnQgb2YgYmVuaWduIHByb3N0YXRpYyBoeXBlcnBsYXNpYQotIGBzdmlgOiBzZW1pbmFsIHZlc2ljbGUgaW52YXNpb24KLSBgbGNwYDogbG9nIG9mIGNhcHN1bGFyIHBlbmV0cmF0aW9uCi0gYGdsZWFzb25gOiBhIG51bWVyaWMgdmVjdG9yCi0gYHBnZzQ1YDogcGVyY2VudCBvZiBHbGVhc29uIHNjb3JlIDQgb3IgNQotIGBscHNhYDogcmVzcG9uc2UKClRoZSBmaXJzdCA4IGNvbHVtbnMgYXJlIHByZWRpY3RvcnM7IGNvbHVtbiA5IGlzIHRoZSBvdXRjb21lL3Jlc3BvbnNlLiBXZSBkbyBub3QgdXNlIGNvbHVtbiAxMCwgd2hpY2ggaW5kaWNhdGVzIHdoaWNoIDY3IG9ic2VydmF0aW9ucyB3ZXJlIHVzZWQgYXMgdGhlICJ0cmFpbmluZyBzZXQiIGFuZCB3aGljaCAzMCBhcyB0aGUgdGVzdCBzZXQsIGFzIGRlc2NyaWJlZCBvbiBwYWdlIDQ4IGluIHRoZSBFU0wgYm9vay4gCgoKCmBgYHtyfQpteURhdGEgPSByZWFkLnRhYmxlKGZpbGUgPSAiaHR0cHM6Ly9oYXN0aWUuc3UuZG9tYWlucy9FbGVtU3RhdExlYXJuL2RhdGFzZXRzL3Byb3N0YXRlLmRhdGEiLCBoZWFkZXIgPSBUUlVFKQpkaW0obXlEYXRhKQpuYW1lcyhteURhdGEpCmBgYAoKUmVtb3ZlIGNvbHVtbiAxMCBhbmQgcnVuIGEgcXVpY2sgc3VtbWFyeSBvZiBlYWNoIGNvbHVtbiBvZiB0aGUgZGF0YS4gRm9yIGNvbnZlbmllbmNlLCB3ZSByZW5hbWUgdGhlIHJlc3BvbnNlIGNvbHVtbiB3aXRoIGEgZ2VuZXJpYyBuYW1lIFkuCgpgYGB7cn0KbXlEYXRhID0gbXlEYXRhWywgLTEwXQpuYW1lcyhteURhdGEpWzldID0gJ1knCnN1bW1hcnkobXlEYXRhKQpgYGAKClByb2R1Y2UgYSBwYWlyLXdpc2Ugc2NhdHRlciBwbG90LiBDYXV0aW9uOiBhIGJpZyBmaWd1cmUuCgpgYGB7cn0KcGFpcnMobXlEYXRhLCBwY2g9Jy4nKQpgYGAKCiMjIEZpdCBhIExpbmVhciBNb2RlbAoKRml0IGEgbGluZWFyIHJlZ3Jlc3Npb24gbW9kZWwgdXNpbmcgYWxsIHRoZSBwcmVkaWN0b3JzIGFuZCBwcmludCB0aGUgc3VtbWFyeSBvZiB0aGUgTFMgcmVzdWx0cwoKYGBge3J9CmxtZml0IDwtICBsbShZIH4gLiwgZGF0YSA9IG15RGF0YSkKc3VtbWFyeShsbWZpdCkKYGBgCgpDaGVjayB3aGF0IGFyZSByZXR1cm5lZCBieSBgbG1gIGFuZCBsZWFybiBob3cgdG8gcmV0cmlldmUgdGhvc2UgcmVzdWx0cy4KCmBgYHtyfQpuYW1lcyhsbWZpdCkgICMgV2hhdCBhcmUgcmV0dXJuZWQgYnkgImxtIj8KbmFtZXMoc3VtbWFyeShsbWZpdCkpICMgV2hhdCBhcmUgcmV0dXJuZWQgYnkgdGhlIHN1bW1hcnkgb2YgbG1maXQKYGBgCgpgYGB7ciwgZXZhbD1GQUxTRX0KIyBSZWdyZXNzaW9uIGNvZWZmaWNpZW50cyBpbmNsdWRpbmcgdGhlIGludGVyY2VwdApsbWZpdCRjb2VmICAgIApsbWZpdCRyZXNpZHVhbHNbMV0KbGVuZ3RoKGxtZml0JHJlc2lkdWFscykKYGBgCgpDaGVjayB0aGUgY2FsY3VsYXRpb24gZm9yIGBSZXNpZHVhbCBzdGFuZGFyZCBlcnJvcmAgYW5kIGBNdWx0aXBsZSBSLXNxdWFyZWRgIGluIHRoZSBzdW1tYXJ5IG91dHB1dDoKJCQKXHNpZ21hID0gXHNxcnR7XGZyYWN7XHN1bV97aT0xfV5uIHJfaV4yfXtuIC0gcC0xfX0sIFxxdWFkIHAgPSBcdGV4dHsgIyBvZiBub24taW50ZXJjZXB0IHByZWRpY3RvcnN9CiQkCiQkIApSXjIgPSBcZnJhY3tcc3VtX3tpPTF9Xm4gcl9pXjJ9e1xzdW1fe2k9MX1ebiAoeV9pIC0gXGJhcnt5fSleMn0gPSBcZnJhY3tcc3VtX3tpPTF9Xm4gcl9pXjJ9e1x0ZXh0e1NhbXBsZVZhcn0oeV9pKVx0aW1lcyAobi0xKX0gPSBcZnJhY3tcdGV4dHtTYW1wbGVWYXJ9KHJfaSl9e1x0ZXh0e1NhbXBsZVZhcn0oeV9pKX0KJCQKCmBgYHtyfQpuID0gZGltKG15RGF0YSlbMV0KcCA9IGRpbShteURhdGEpWzJdIC0gMQojIFJlc2lkdWFsIHN0YW5kYXJkIGVycm9yCmMoc3FydChzdW0obG1maXQkcmVzaWR1YWxzXjIpLyhuLSBwIC0gMSkpLCBzdW1tYXJ5KGxtZml0KSRzaWdtYSkgIAojIFItc3F1YXJlZApjKDEgLSBzdW0obG1maXQkcmVzaWR1YWxzXjIpLyh2YXIobXlEYXRhJFkpKihuLTEpKSwgc3VtbWFyeShsbWZpdCkkci5zcXVhcmVkKSAKMSAtIHZhcihsbWZpdCRyZXNpZHVhbHMpL3ZhcihteURhdGEkWSkKYGBgCgojIyBQcmVkaWN0aW9uCgpQcmVkaWN0aW5nIHJlc3BvbnNlcyBmb3IgbmV3IG9ic2VydmF0aW9ucyBjYW4gYmUgYWNjb21wbGlzaGVkIHRocm91Z2ggdHdvIG1ldGhvZHM6CgotICoqTWV0aG9kIDEqKjogQmVnaW4gYnkgb3JnYW5pemluZyB0aGUgbmV3IG9ic2VydmF0aW9ucyBpbnRvIGEgbWF0cml4IG9yIHZlY3Rvci4gVGhlbiwgYXBwbHkgdGhlIGZvbGxvd2luZyBmb3JtdWxhOiBuZXdYICogYmV0YSArIGJldGEwLCB3aGVyZSAoYmV0YTAsIGJldGEpIHJlcHJlc2VudCB0aGUgY29lZmZpY2llbnRzIG9idGFpbmVkIHRocm91Z2ggTFMgcmVncmVzc2lvbi4KCi0gKipNZXRob2QgMioqOiBBbHRlcm5hdGl2ZWx5LCBzdHJ1Y3R1cmUgdGhlIG5ldyBvYnNlcnZhdGlvbnMgYXMgYSBkYXRhIGZyYW1lIHdpdGggaWRlbnRpY2FsIGNvbHVtbiBuYW1lcyBhcyB0aG9zZSBpbiBgbXlEYXRhYC4gU3Vic2VxdWVudGx5LCB1dGlsaXplIHRoZSBgcHJlZGljdGAgZnVuY3Rpb24uCgpUbyBleGVtcGxpZnkgdGhlc2UgbWV0aG9kcywgd2UgY29uc2lkZXIgdHdvIG5vdmVsIHBhdGllbnRzLiBPbmUgaW5kaXZpZHVhbCBpcyA1MCB5ZWFycyBvbGQsIHdoaWxlIHRoZSBvdGhlciBpcyA3MCB5ZWFycyBvbGQuIEFsbCBvdGhlciBhdHRyaWJ1dGVzIGFzc3VtZSBtZWRpYW4gdmFsdWVzIGZyb20gdGhlIGV4aXN0aW5nIGRhdGFzZXQgZW5jb21wYXNzaW5nIDk3IHBhdGllbnRzLgoKIyMjIyBNZXRob2QgMQoKYGBge3J9CmFwcGx5KG15RGF0YSwgMiwgbWVkaWFuKQpuZXd4MSA9IGMoMS40NSwgMy42MiwgNTAsIDAuMzAsIDAsIC0wLjgwLCA3LCAxNSkgIzFzdCBwYXRpZW50OiBhZ2UgPSA1MApuZXd4MiA9IG5ld3gxCm5ld3gyWzNdID0gNzAgIzJuZCBwYXRpZW50OiBhZ2UgPSA3MApuZXd4ID0gcmJpbmQobmV3eDEsIG5ld3gyKQpuZXd4ICUqJSBsbWZpdCRjb2VmWy0xXSArIGxtZml0JGNvZWZbMV0KYGBgCgojIyMjIE1ldGhvZCAyCgoKYGBge3J9Cm5ld2RmID0gZGF0YS5mcmFtZShuZXd4KQoKIyBhc3NpZ24gY29sIG5hbWVzIGFmdGVyIGRyb3BwaW5nIHRoZSBsYXN0IGNvbApuYW1lcyhuZXdkZikgPSBuYW1lcyhteURhdGFbLCAtZGltKG15RGF0YSlbMl1dKSAKYGBgCgpBbiBhZHZhbnRhZ2Ugb2YgdGhlIGBwcmVkaWN0YCBmdW5jdGlvbiBpcyB0aGF0IG9uY2UgY29sdW1ucyBoYXZlIG5hbWVzLCB0aGVpciBvcmRlciBkb2VzIG5vdCBtYXR0ZXIuIFNvLCBsZXQncyBzaHVmZmxlIHRoZSBjb2x1bW5zIG9mIGBuZXdkZmAgYW5kIHRoZW4gcHJlZGljdC4gVGhlIHJlc3VsdCBzaG91bGQgYmUgdGhlIHNhbWUgYXMgd2hhdCBpcyByZXR1cm5lZCBieSBNZXRob2QgMS4gCgpgYGB7cn0KbmV3ZGYKbmV3ZGYgPSBuZXdkZlssIHNhbXBsZSgxOmRpbShuZXdkZilbMl0pXQpuZXdkZgpwcmVkaWN0KGxtZml0LCBuZXdkYXRhID0gbmV3ZGYpCmBgYAoKIyMgUmFuayBEZWZpY2llbmN5CgpJbiBjYXNlcyB3aGVyZSB0aGUgZGVzaWduIG1hdHJpeCwgaW5jbHVkaW5nIHRoZSBpbnRlcmNlcHQsIGRvZXMgbm90IGhhdmUgZnVsbCByYW5rLCB0aGUgY29lZmZpY2llbnQgdmVjdG9yIHJldHVybmVkIGJ5IFIgd2lsbCBjb250YWluIHNvbWUgTkEgZWxlbWVudHMuIEFuIE5BIGVzdGltYXRlIGZvciBhIGNvbHVtbiBzaWduaWZpZXMgdGhhdCB0aGF0IGNvbHVtbiBjYW4gYmUgd3JpdHRlbiBhcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiBwcmVjZWRpbmcgY29sdW1ucywgcmVuZGVyaW5nIGl0IHJlZHVuZGFudC4KCioqTkEgdmFsdWVzIGRvIG5vdCBpbmRpY2F0ZSBlcnJvcnMqKi4gVGhleSBzaW1wbHkgaW5kaWNhdGUgdGhhdCBpbiB0aGUgTFMgZml0dGluZyBwcm9jZXNzLCBSIGRpc2NhcmRzIGNvbHVtbnMgd2l0aCBOQSBjb2VmZmljaWVudHMuIEhvd2V2ZXIsIHRoaXMgZG9lc24ndCBoaW5kZXIgdGhlIHV0aWxpdHkgb2YgdGhlIGZpdHRlZCBtb2RlbCBmb3IgcHJlZGljdGlvbiBwdXJwb3Nlcy4gVGhlIHByZWRpY3Rpb25zIGRlcml2ZWQgZnJvbSB0aGlzIG1vZGVsIHdpbGwgYWxpZ24gd2l0aCB0aG9zZSBvYnRhaW5lZCBmcm9tIGZpdHRpbmcgYSBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbCBleGNsdWRpbmcgdGhlIGNvbHVtbnMgd2l0aCBOQSBjb2VmZmljaWVudHMuCgpgYGB7cn0KIyMgQWRkIGEgZmFrZSBjb2x1bW4gbmFtZWQgImp1bmsiLCB3aGljaCBpcyBhIGxpbmVhciBjb21iaW5hdGlvbiBvZiB0aGUgZmlyc3QgdHdvIHByZWRpY3RvcnMKbXlEYXRhJGp1bmsgPC0gIG15RGF0YVssIDFdICsgbXlEYXRhWywgMl0KdG1wLmxtIDwtICBsbShZIH4gLiwgbXlEYXRhKQpzdW1tYXJ5KHRtcC5sbSkKYGBgCgpUaGUgZml0dGVkIHZhbHVlcyBmcm9tIHRoZSBvcmlnaW5hbCBgbG1maXRgIGFuZCB0aGUgbmV3IGZpdCBgdG1wLmxpbWAgYXJlIHRoZSBzYW1lLiAKYGBge3J9CnRtcC5sbSRmaXR0ZWRbMTozXQpsbWZpdCRmaXR0ZWRbMTozXQoKIyMgZHJvcCB0aGUgImp1bmsiIGNvbHVtbgpteURhdGEgPSBteURhdGFbLCAhbmFtZXMobXlEYXRhKSA9PSAnanVuaycgXQpgYGAKCiMjIFRyYWluaW5nIHZzIFRlc3QgRXJyb3JzCgpJbiBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbHMsIGFzIHdlIGludHJvZHVjZSBtb3JlIHZhcmlhYmxlcywgdHJhaW5pbmcgZXJyb3IgKG1lYXN1cmVkIGJ5IFJTUyBvciBNU0UpIGNvbnNpc3RlbnRseSBkZWNyZWFzZXMuIEhvd2V2ZXIsIHRoaXMgcmVkdWN0aW9uIGluIHRyYWluaW5nIGVycm9yIGRvZXMgbm90IGd1YXJhbnRlZSBhIGNvcnJlc3BvbmRpbmcgZGVjcmVhc2UgaW4gdGVzdCBlcnJvciwgd2hpY2ggbWVhc3VyZXMgcHJlZGljdGlvbiBhY2N1cmFjeSBvbiBpbmRlcGVuZGVudCB0ZXN0IGRhdGEuIFRvIGRlbW9uc3RyYXRlIHRoaXMsIHdlIHJhbmRvbWx5IHNwbGl0IG91ciBkYXRhc2V0IGludG8gNjBcJSB0cmFpbmluZyBhbmQgNDBcJSB0ZXN0IHBvcnRpb25zLCBwcm9ncmVzc2l2ZWx5IGFkZGluZyBwcmVkaWN0b3JzLiBUaGlzIGFwcHJvYWNoIGhpZ2hsaWdodHMgaG93IGFkZGl0aW9uYWwgcHJlZGljdG9ycyBjYW4gbG93ZXIgdHJhaW5pbmcgZXJyb3Igd2hpbGUgdGVzdCBlcnJvciBtYXkgbm90IGZvbGxvdyB0aGUgc2FtZSB0cmVuZC4KCmBgYHtyfQpuIDwtIGRpbShteURhdGEpWzFdICMgc2FtcGxlIHNpemUKcCA8LSAgZGltKG15RGF0YSlbMl0gLSAxICMgbnVtYmVyIG9mIG5vbi1pbnRlcmNlcHQgcHJlZGljdG9ycwoKbnRyYWluIDwtICByb3VuZChuKjAuNikKdHJhaW4uaWQgPC0gIHNhbXBsZSgxOm4sIG50cmFpbikKdHJhaW4uTVNFIDwtICByZXAoMCwgcCkKdGVzdC5NU0UgPC0gIHJlcCgwLCBwKQoKZm9yKGkgaW4gMTpwKXsKICBteWZpdCA8LSAgbG0oWSB+IC4sIG15RGF0YVt0cmFpbi5pZCwgYygxOmksIChwKzEpKV0pCiAgdHJhaW4uWSA8LSAgbXlEYXRhW3RyYWluLmlkLCAocCsxKV0KICB0cmFpbi5ZLnByZWQgPC0gIG15Zml0JGZpdHRlZAogIHRyYWluLk1TRVtpXSA8LSAgbWVhbigodHJhaW4uWSAtIHRyYWluLlkucHJlZCleMikKICAKICB0ZXN0LlkgPC0gIG15RGF0YVstdHJhaW4uaWQsIChwKzEpXQogIHRlc3QuWS5wcmVkIDwtICBwcmVkaWN0KG15Zml0LCBuZXdkYXRhID0gbXlEYXRhWy10cmFpbi5pZCwgXSkKICB0ZXN0Lk1TRVtpXSA8LSAgbWVhbigodGVzdC5ZIC0gdGVzdC5ZLnByZWQpXjIpCn0KCiMjIHR5cGU9Im4iOiBkb24ndCBwbG90OyBqdXN0IHNldCB0aGUgcGxvdHRpbmcgcmVnaW9uCiAgcGxvdChjKDEsIHApLCByYW5nZSh0cmFpbi5NU0UsIHRlc3QuTVNFKSwgdHlwZT0ibiIsIHhsYWI9IiMgb2YgdmFyaWFibGVzIiwgeWxhYj0iTVNFIikKICBwb2ludHModHJhaW4uTVNFLCBjb2wgPSAiYmx1ZSIsIHBjaCA9IDEpCiAgbGluZXModHJhaW4uTVNFLCBjb2wgPSAiYmx1ZSIsIHBjaCA9IDEpCiAgcG9pbnRzKHRlc3QuTVNFLCBjb2wgPSAicmVkIiwgcGNoID0gMikKICBsaW5lcyh0ZXN0Lk1TRSwgY29sID0gInJlZCIsIHBjaCA9IDIpCmBgYAoKRmVlbCBmcmVlIHRvIHJ1biB0aGUgcHJvdmlkZWQgY29kZSBtdWx0aXBsZSB0aW1lcy4gWW91J2xsIG9ic2VydmUgdGhlIGZvbGxvd2luZyBwYXR0ZXJuczoKCi0gSW4gbW9zdCBpbnN0YW5jZXMsIHRoZSBibHVlIGxpbmUgKHJlcHJlc2VudGluZyB0cmFpbmluZyBlcnJvcikgdGVuZHMgdG8gYmUgcG9zaXRpb25lZCBiZWxvdyB0aGUgcmVkIGxpbmUgKHJlcHJlc2VudGluZyB0ZXN0IGVycm9yKSwgaW5kaWNhdGluZyB0aGF0IHRoZSB0cmFpbmluZyBlcnJvciBpcyBnZW5lcmFsbHkgc3VwZXJpb3IgdG8gdGhlIHRlc3QgZXJyb3IuIEhvd2V2ZXIsIGR1ZSB0byB0aGUgaW5oZXJlbnQgcmFuZG9tbmVzcywgdGhlcmUgbWlnaHQgYmUgaW5zdGFuY2VzIHdoZXJlIHRoZSByZWQgbGluZSBmYWxscyBiZWxvdyB0aGUgYmx1ZSBsaW5lLCBpbmRpY2F0aW5nIHRoYXQgdGhlIHRlc3QgZXJyb3Igb3V0cGVyZm9ybXMgdGhlIHRyYWluaW5nIGVycm9yIG9jY2FzaW9uYWxseS4KCi0gSW4gZWFjaCBpdGVyYXRpb24sIHRoZSBibHVlIGxpbmUgY29uc2lzdGVudGx5IGV4aGliaXRzIGEgbW9ub3RvbmljYWxseSBkZWNyZWFzaW5nIHRyZW5kLCBzaWduaWZ5aW5nIHRoZSByZWR1Y3Rpb24gb2YgdHJhaW5pbmcgZXJyb3IgYXMgbW9yZSBwcmVkaWN0b3JzIGFyZSBpbmNvcnBvcmF0ZWQuIE9uIHRoZSBvdGhlciBoYW5kLCB0aGUgcmVkIGxpbmUncyB0cmFqZWN0b3J5IG1heSBub3QgdW5pZm9ybWx5IGRlY3JlYXNlLiBVcG9uIGNsb3NlciBleGFtaW5hdGlvbiBvZiB0aGUgZGlmZmVyZW5jZXMgYmV0d2VlbiBhZGphY2VudCB0ZXJtcywgIHlvdSdsbCBvYnNlcnZlIG5lZ2F0aXZlIHZhbHVlcyBjb25zaXN0ZW50bHkgZm9yIHRoZSBibHVlIGxpbmUsIGJ1dCBmb3IgdGhlIHJlZCBsaW5lLCB0aGVzZSBkaWZmZXJlbmNlcyBtaWdodCBlbmNvbXBhc3Mgc29tZSBwb3NpdGl2ZSB2YWx1ZXMuIAoKYGBge3IsIGV2YWw9RkFMU0V9CmRpZmYodHJhaW4uTVNFKSAjIyBhbHdheXMgbmVnYXRpdmUKZGlmZih0ZXN0Lk1TRSkgICMjIG5vdCBhbHdheXMgbmVnYXRpdmUKYGBgCgojIyBJbnRlcnByZXQgTFMgQ29lZmZpY2llbnRzCgpIb3cgdG8gaW50ZXJwcmV0IExTIGNvZWZmaWNpZW50cz8gTFMgY29lZmZpY2llbnRzIGV4cHJlc3MgaG93IGNoYW5nZXMgaW4gcHJlZGljdG9ycyBhZmZlY3QgdGhlIHJlc3BvbnNlIHdoaWxlIGhvbGRpbmcgYWxsIG90aGVyIHByZWRpY3RvcnMgY29uc3RhbnQuIEZvciBpbnN0YW5jZSwgdGhlIGNvZWZmaWNpZW50IGZvciBgYWdlYCBxdWFudGlmaWVzIHRoZSBhdmVyYWdlIGNoYW5nZSBpbiB0aGUgcmVzcG9uc2UgdmFyaWFibGUgZm9yIGVhY2ggeWVhciBpbmNyZWFzZSBpbiBhZ2UsICoqaG9sZGluZyBhbGwgb3RoZXIgcHJlZGljdG9ycyBjb25zdGFudCoqLiAKCkl0J3Mgbm90ZXdvcnRoeSB0aGF0IHJlc3VsdHMgZnJvbSBTaW1wbGUgTGluZWFyIFJlZ3Jlc3Npb24gKFNMUiksIHdoaWNoIGludm9sdmVzIG9ubHkgb25lIG5vbi1pbnRlcmNlcHQgcHJlZGljdG9yLCBtaWdodCBkaWZmZXIgZnJvbSByZXN1bHRzIGluIE11bHRpcGxlIExpbmVhciBSZWdyZXNzaW9uIChNTFIpLCB3aGljaCBpbmNvcnBvcmF0ZXMgbXVsdGlwbGUgcHJlZGljdG9ycy4gVGhpcyBkaXZlcmdlbmNlIGNhbiBhcmlzZSBkdWUgdG8gY29ycmVsYXRpb25zIGFtb25nIHByZWRpY3RvcnMuCiAKRm9yIGluc3RhbmNlLCBjb25zaWRlciB0aGUgY2FzZSB3aGVyZSBgYWdlYCBpcyBwb3NpdGl2ZWx5IGNvcnJlbGF0ZWQgd2l0aCBzb21lIHByZWRpY3RvcnMgdGhhdCBoYXZlIGEgcG9zaXRpdmUgZWZmZWN0IG9uIHRoZSByZXNwb25zZS4gSW4gYSBqb2ludCBtb2RlbCAoTUxSKSwgdGhlIGNvZWZmaWNpZW50IGZvciBgYWdlYCBhcHBlYXJzIG5lZ2F0aXZlLCBzZWVtaW5nbHkgY29udHJhcnkgdG8gaXRzIHBvc2l0aXZlIGVmZmVjdCBpbiBhbiBpc29sYXRlZCBtb2RlbCAoU0xSKS4gVGhpcyBhZGp1c3RtZW50IGNvbXBlbnNhdGVzIGZvciB0aGUgcG9zaXRpdmUgY29udHJpYnV0aW9uIGludHJvZHVjZWQgYnkgb3RoZXIgcHJlZGljdG9ycywgZW5zdXJpbmcgdGhhdCB0aGUgb3ZlcmFsbCBtb2RlbCBhY2N1cmF0ZWx5IHJlcHJlc2VudHMgdGhlIHJlbGF0aW9uc2hpcHMgYmV0d2VlbiBwcmVkaWN0b3JzIGFuZCB0aGUgcmVzcG9uc2UgdmFyaWFibGUuCiAKCmBgYHtyfQpzdW1tYXJ5KGxtKFl+IGFnZSwgbXlEYXRhKSkKcm91bmQoY29yKG15RGF0YSksIGRpZz0yKQpgYGAKCgojIyBQYXJ0aWFsIFJlZ3Jlc3Npb24gQ29lZgoKQ2hlY2sgaG93IHRvIHJldHJpZXZlIHRoZSBMUyBjb2VmZmljaWVudCBmb3IgYGFnZWAgdXNpbmcgQWxnb3JpdGhtIDMuMQoKYGBge3J9Cnkuc3RhciA8LSAgbG0oWSB+IC4sIGRhdGEgPSBzdWJzZXQobXlEYXRhLCBzZWxlY3QgPSAtYWdlKSkkcmVzCmFnZS5zdGFyIDwtICBsbShhZ2UgfiAuLCBkYXRhID0gc3Vic2V0KG15RGF0YSwgc2VsZWN0ID0gLVkpKSRyZXMKdG1wZml0IDwtICBsbSh5LnN0YXIgfiBhZ2Uuc3RhcikKYGBgCgpUaGUgTFMgY29lZmZpY2llbnQgZm9yIGBhZ2VgIChmcm9tIGBsbWZpdGApIGlzIHRoZSBzYW1lIGFzIHRoZSBvbmUgZnJvbSBgdG1wZml0YC4gVGhlIHJlc2lkdWFscyBmcm9tIHRoZSB0d28gTFMgbW9kZWxzIGFyZSBhbHNvIHRoZSBzYW1lLgoKYGBge3J9CnRtcGZpdCRjb2VmCnN1bSgobG1maXQkcmVzIC0gdG1wZml0JHJlcyleMikKYGBgCgojIyBGLXRlc3QKClRlc3QgYSBzaW5nbGUgcHJlZGljdG9yIChpbiB0aGlzIGNhc2UsIEYtdGVzdCA9IHQtdGVzdCkuCgpgYGB7cn0KbG1maXQwIDwtIGxtKFkgfiAuLCBkYXRhID0gc3Vic2V0KG15RGF0YSwgc2VsZWN0ID0gLWFnZSkpCmFub3ZhKGxtZml0MCwgbG1maXQpCmBgYAoKVGVzdCBtdWx0aXBsZSBwcmVkaWN0b3JzLgoKYGBge3J9CmxtZml0MCA8LSBsbShZIH4gLiwgZGF0YSA9IG15RGF0YVssIC1jKDE6MyldKQphbm92YShsbWZpdDAsIGxtZml0KQpgYGAKCgojIyBDb2xsaW5lYXJpdHkKCkNoZWNrIHRoZSBDYXIgU2VhdCBQb3NpdGlvbiBEYXRhIGZyb20gZmFyYXdheSBwYWNrYWdlLgoKQ2FyIGRyaXZlcnMgbGlrZSB0byBhZGp1c3QgdGhlIHNlYXQgcG9zaXRpb24gZm9yIHRoZWlyIG93biBjb21mb3J0LiBDYXIgZGVzaWduZXJzIHdvdWxkIGZpbmQgaXQgaGVscGZ1bCB0byBrbm93IGhvdyBkaWZmZXJlbnQgZHJpdmVycyB3aWxsIHBvc2l0aW9uIHRoZSBzZWF0IGRlcGVuZGluZyBvbiB0aGVpciBzaXplIGFuZCBhZ2UuIFJlc2VhcmNoZXJzIGF0IHRoZSBbSHVNb1NpbSBsYWJvcmF0b3J5XShodHRwOi8vaHVtb3NpbS5vcmcvKSBhdCB0aGUgVW5pdmVyc2l0eSBvZiBNaWNoaWdhbiBjb2xsZWN0ZWQgZGF0YSBvbiAzOCBkcml2ZXJzLgoKLSBgQWdlYDoKLSBgV2VpZ2h0YDoKLSBgSHRTaG9lc2A6IGhlaWdodCB3aXRoIHNob2VzIGluIGNtCi0gYEh0YDogaGVpZ2h0IHdpdGhvdXQgc2hvZXMgaW4gY20KLSBgU2VhdGVkYDogc2VhdGVkIGhlaWdodCBpbiBjbQotIGBBcm1gOiBsb3dlciBhcm0gbGVuZ3RoIGluIGNtCi0gYFRoaWdoYDogdGhpZ2ggbGVuZ3RoIGluIGNtCi0gYExlZ2A6IGxvd2VyIGxlZyBsZW5ndGggaW4gY20KLSBgaGlwY2VudGVyYDogaG9yaXpvbnRhbCBkaXN0YW5jZSBvZiB0aGUgbWlkcG9pbnQgb2YgdGhlIGhpcHMgZnJvbSBhIGZpeGVkIGxvY2F0aW9uIGluIHRoZSBjYXIgaW4gbW0KClRoZSByZXNlYXJjaGVycyB3ZXJlIGludGVyZXN0ZWQgaW4gZGV0ZXJtaW5pbmcgaWYgYSByZWxhdGlvbnNoaXAgZXhpc3RzIGJldHdlZW4gYGhpcGNlbnRlcmAgYW5kIHRoZSBvdGhlciB2YXJpYWJsZXMuIER1ZSB0byB0aGUgaGlnaCBjb3JyZWxhdGlvbnMgYW1vbmcgdGhlIHByZWRpY3RvcnMsIHdlIHNlZSBoaWdoIFItc3F1YXJlLCBzaWduaWZpY2FudCBvdmVyYWxsIEYtdGVzdCwgYnV0IG5vIGluZGl2aWR1YWwgdmFyaWFibGVzIGFyZSBzaWduaWZpY2FudC4KCmBgYHtyfQpsaWJyYXJ5KGZhcmF3YXkpCmRhdGEoc2VhdHBvcykKcGFpcnMoc2VhdHBvcywgcGNoID0gIi4iKQpzdW1tYXJ5KGxtKGhpcGNlbnRlciB+IC4gLCBkYXRhPXNlYXRwb3MpKQojIyBjaGVjayBwYWlyd2lzZSBjb3JyZWxhdGlvbgpyb3VuZChjb3Ioc2VhdHBvcyksIGRpZz0yKQpgYGAKCklmIHdlIHJlbW92ZSBzb21lIChhbG1vc3QpIHJlZHVuZGFudCB2YXJpYWJsZXMsIHRoZSBMUyByZXN1bHRzIG1ha2UgbXVjaCBtb3JlIHNlbnNlLgoKYGBge3J9CnN1bW1hcnkobG0oaGlwY2VudGVyIH4gQWdlICsgV2VpZ2h0ICsgSHQgKyBTZWF0ZWQsIGRhdGE9c2VhdHBvcykpCnN1bW1hcnkobG0oaGlwY2VudGVyIH4gSHQsIGRhdGE9c2VhdHBvcykpCmBgYA==