#################################################################################################################
# advanced regression models #
# ref : http://r-statistics.co/adv-regression-models.html #
# ref : https://onlinecourses.science.psu.edu/stat504/node/216 #
# ref : https://blog.cloudera.com/blog/2015/12/common-probability-distributions-the-data-scientists-crib-sheet/ #
# ref : http://rstudio-pubs-static.s3.amazonaws.com/190997_40fa09db8e344b19b14a687ea5de914b.html #
#################################################################################################################
######################################################################################################
# package & method #
# smbinning : https://cran.r-project.org/web/packages/smbinning/smbinning.pdf #
# : smbinning.factor() #
# InformationValue : https://cran.r-project.org/web/packages/InformationValue/InformationValue.pdf #
# : optimalCutoff() , plotRoc() #
######################################################################################################
# linear regression 의 가정중 dependent variable 정규분포해야 한다는 것이 있는데,
# 이 가정은, 서비스단에서는 앵간하면 맞추기 힘든 가정이다.
# depnendent value 가 다양한 분포를 가질때, 사용할 수 있는 glm 에 대해서 정리
GLM
# General Linear Model
# refers to conventional linear regression models for a continuous response variable
# given continuous and/or categorical predictors
#
# Generalized Linear Model
# the response variable yi is assumed to follow an exponential family distribution with mean μi,
# which is assumed to be some (often nonlinear) function of T(xi)β.
# three components
## Random Component : the probability distribution of the response variable (Y)
## Systematic Component : the explanatory variables (X1, X2, ... Xk) as a combination of linear predictors; e.g. β0 + β1x1 + β2x2
## Link Function (η or g(μ)) : specifies the link between random and systematic components , e.g. η = logit(π) for logistic regression
## : GLM은 Y ~ X 가 linear 관계가 아님. link function 을통해서, linear 관계를 만들어주는 역할
## : binary ( 0, 1 ) 값만을 갖는 Y 를 , 확률개념으로 변경하여 continuous variable 로 만들어주는 역할
## : 아래 그림에서 'x' 점으로 찍히는 y 변수값을, sigmoid curve 형태로 변환시키는 역할
## : http://www.columbia.edu/~so33/SusDev/Lecture_9.pdf
Binary Logistic Regression
# ref : http://r-statistics.co/Logistic-Regression-With-R.html#Build%20Logit%20Models%20and%20Predict
#
#1. Random component : Binomial Distribution ( Y )
#2. Systematic component : Explanatory var. ( can be continuous / discret | Xs )
#3. Link function : Logit
#
# Assumptions
##4.1 dependent variable 끼리 independent 해야함
##4.2 샘플 데이터가 충분히 많아야 함.
#
# MLE ( Maximum Likelihood Estimation ) : 여기까지 봐야하는가?
## 오직 주어진 Observation, 혹은 데이터들 만을 토대로 parameter estimation을 하는 방법
## observation에 따라 그 값이 너무 민감하게 변한다는 단점 ( so, 샘플 데이터가 충분히 많아야 함 )
#
# No Outliers ( 0 or 1 )
# ref : http://rfriend.tistory.com/99
# binomial distribution
# Discret Prob. Distribution > Binomial Distribution , Poisson Distribution
#
# 반복시행시, Success / Fail 만 발생하는 케이스 ( 베르누이 시행 )
# 성공확률이 p인 베르누이 시행을 n번 반복했을 때 성공하는 횟수를 X라 하면, 확률변수 X는 모수 n과 p인 이항분포(Binomial distributio)을 따른다
y <- dbinom(0:20, size=20, prob=0.5)
plot(0:20, y, type='h', lwd=5, col="grey", ylab="Probability", xlab="확률변수 X", main = c("X ~ B(20, 0.5)"))

plot(pbinom(0:20, size=20, prob=0.5), type='h')

# sum(dbinom(0:12, size=20, prob=0.5))
# rbinom(12, size=20, prob=0.5)
library(data.table)
adult <- fread("/Users/CA/Downloads/adult.csv", stringsAsFactors = F)
head(adult, n = 1)
# Create Training Data
input_ones <- adult[which(adult$ABOVE50K == 1), ] # all 1's
input_zeros <- adult[which(adult$ABOVE50K == 0), ] # all 0's
set.seed(100)
input_ones_training_rows <- sample(1:nrow(input_ones), 0.7*nrow(input_ones)) # 1's for training
input_zeros_training_rows <- sample(1:nrow(input_zeros), 0.7*nrow(input_ones)) # 0's for training. Pick as many 0's as 1's
training_ones <- input_ones[input_ones_training_rows, ]
training_zeros <- input_zeros[input_zeros_training_rows, ]
trainingData <- rbind(training_ones, training_zeros) # row bind the 1's and 0's
# Create Test Data
test_ones <- input_ones[-input_ones_training_rows, ]
test_zeros <- input_zeros[-input_zeros_training_rows, ]
testData <- rbind(test_ones, test_zeros) # row bind the 1's and 0's
library(smbinning)
# segregate continuous and factor variables
factor_vars <- c ("WORKCLASS", "EDUCATION", "MARITALSTATUS", "OCCUPATION", "RELATIONSHIP", "RACE", "SEX", "NATIVECOUNTRY")
continuous_vars <- c("AGE", "FNLWGT","EDUCATIONNUM", "HOURSPERWEEK", "CAPITALGAIN", "CAPITALLOSS")
iv_df <- data.frame(VARS=c(factor_vars, continuous_vars), IV=numeric(14)) # init for IV results
# compute IV for categoricals
for(factor_var in factor_vars){
smb <- smbinning.factor(trainingData, y="ABOVE50K", x=factor_var) # WOE table
if(class(smb) != "character"){
iv_df[iv_df$VARS == factor_var, "IV"] <- smb$iv
}
}
# compute IV for continuous vars
for(continuous_var in continuous_vars){
smb <- smbinning(trainingData, y="ABOVE50K", x=continuous_var) # WOE table
if(class(smb) != "character"){ # any error while calculating scores.
iv_df[iv_df$VARS == continuous_var, "IV"] <- smb$iv
}
}
NAs introduced by coercionNAs introduced by coercionNAs introduced by coercionNAs introduced by coercionNAs introduced by coercion
iv_df <- iv_df[order(-iv_df$IV), ] # sort
iv_df
# Check Random component : Binomial Distribution ( Y ) , Success(1) or Fail(0) => Binomial + Logit function
table(trainingData$ABOVE50K)
0 1
5488 5488
# 0 과 1 만 갖는 분포는 transformation을 하더라도, nomal distribution 의 모양을 가질 수 없다.
plot(density(adult$ABOVE50K))

# binomial distribution 의 link function 으로, glm() 에서는 logit . probit . couchit 을 사용할 수 있다.
model <- glm(ABOVE50K ~ AGE + CAPITALGAIN + EDUCATIONNUM + HOURSPERWEEK + CAPITALLOSS, data=trainingData, family=binomial(link="logit"))
glm.fit: fitted probabilities numerically 0 or 1 occurred
testData$predicted <- predict(model, testData, type="response") # predicted scores
summary(model)
Call:
glm(formula = ABOVE50K ~ AGE + CAPITALGAIN + EDUCATIONNUM + HOURSPERWEEK +
CAPITALLOSS, family = binomial(link = "logit"), data = trainingData)
Deviance Residuals:
Min 1Q Median 3Q Max
-3.8040 -0.8310 -0.0421 0.8669 2.7637
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept) -7.72106683 0.17998331 -42.90 <0.0000000000000002 ***
AGE 0.04991639 0.00195081 25.59 <0.0000000000000002 ***
CAPITALGAIN 0.00032189 0.00001745 18.45 <0.0000000000000002 ***
EDUCATIONNUM 0.32710225 0.01042704 31.37 <0.0000000000000002 ***
HOURSPERWEEK 0.04611973 0.00219967 20.97 <0.0000000000000002 ***
CAPITALLOSS 0.00060828 0.00005436 11.19 <0.0000000000000002 ***
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
(Dispersion parameter for binomial family taken to be 1)
Null deviance: 15216 on 10975 degrees of freedom
Residual deviance: 11022 on 10970 degrees of freedom
AIC: 11034
Number of Fisher Scoring iterations: 7
# check multicollinearity ( 다중공선성 ) 독립변수들간에 높은 선형관계가 존재하면 ( 다중공선성이 존재하면 ) 회귀분석 전제 가정 위배
library(car)
sqrt(vif(model)) > 2
AGE CAPITALGAIN EDUCATIONNUM HOURSPERWEEK CAPITALLOSS
FALSE FALSE FALSE FALSE FALSE
# feature 들의 상대적인 중요도 ( feature 를 추가했을때 평균적은 R2 의 증가를 보는 것 )
relweights <- function(fit,...){
R <- cor(fit$model)
nvar <- ncol(R)
rxx <- R[2:nvar, 2:nvar]
rxy <- R[2:nvar, 1]
svd <- eigen(rxx)
evec <- svd$vectors
ev <- svd$values
delta <- diag(sqrt(ev))
lambda <- evec %*% delta %*% t(evec)
lambdasq <- lambda ^ 2
beta <- solve(lambda) %*% rxy
rsquare <- colSums(beta ^ 2)
rawwgt <- lambdasq %*% beta ^ 2
import <- (rawwgt / rsquare) * 100
import <- as.data.frame(import)
row.names(import) <- names(fit$model[2:nvar])
names(import) <- "Weights"
import <- import[order(import),1, drop=FALSE]
dotchart(import$Weights, labels=row.names(import),
xlab="% of R-Square", pch=19,
main="Relative Importance of Predictor Variables",
sub=paste("Total R-Square=", round(rsquare, digits=3)),
...)
return(import)
}
relweights(model)

library(InformationValue)
threshold <- optimalCutoff(testData$ABOVE50K, testData$predicted)
misClassError(testData$ABOVE50K, testData$predicted, threshold = threshold)
[1] 0.0965
plotROC(testData$ABOVE50K, testData$predicted)

# linear regression 의 가정을 검사하기 위한 아래 plot 들은, 당연하게도 모두 위배되는 결과를 보인다.
par(mfrow = c(2,2))
plot(model)

# model 비교
model.1 <- model <- glm(ABOVE50K ~ 1, data=trainingData, family=binomial(link="logit"))
model.2 <- model <- glm(ABOVE50K ~ AGE, data=trainingData, family=binomial(link="logit"))
model.3 <- model <- glm(ABOVE50K ~ AGE + CAPITALGAIN, data=trainingData, family=binomial(link="logit"))
glm.fit: fitted probabilities numerically 0 or 1 occurred
library(rcompanion)
compareGLM(model.1, model.2, model.3)
$Models
Formula
1 "ABOVE50K ~ 1"
2 "ABOVE50K ~ AGE"
3 "ABOVE50K ~ AGE + CAPITALGAIN"
$Fit.criteria
anova(model.1, model.2, model.3)
Analysis of Deviance Table
Model 1: ABOVE50K ~ 1
Model 2: ABOVE50K ~ AGE
Model 3: ABOVE50K ~ AGE + CAPITALGAIN
Resid. Df Resid. Dev Df Deviance
1 10975 15216
2 10974 14273 1 942.62
3 10973 13178 1 1095.60
# 최선의 모델을 고르는 방법 중에, 앞선 모델 evaluation 과 함께 몇가지 통계량을 기준으로 선택하는 방법도 있다.
# 위의 compareGLM function 의 결과를 보면 AIC / BIC 등의 통계량이 나오는데, 이에 대한 내용을 살펴보자
#
# AIC(Akaike’s An Information Criterion)
## 모형의 통계적 적합성 및 통계 적합에 필요한 인수의 수를 설명 ( ? )
## AIC 값이 적은 모형, 즉 적은 인수를 가지고 적절한 적합성을 보이는 모형이 선호 ( AIC 값은 적으면 좋다. AIC 값은 음수도 가능하다. )
## AIC / BIC function 의 doc 을 살펴보면, 아래와 같다.
## When comparing models fitted by maximum likelihood to the same data, the smaller the AIC or BIC, the better the fit.
AIC(model.1, model.2, model.3)
# 위 예에서는 model.3 의 AIC 값이 제일 작게 나왔으므로, AIC 기준으로는 model.3 이 제일 적절한 모델이라고 판단한다.
# 이때, independent var. 를 자동으로 추가해가면서 여러 모델을 쉽게 비교해 볼 수 도 있는데, step 함수를 사용하면 된다.
# step 함수는 backward ( feature 를 빼가면서, ) , forward ( 지정된 feature 들을 하나씩 추가하면서 ) 최소 AIC 값을 찾는다.
super.model = glm(ABOVE50K ~ 1 , data = trainingData)
sub.model = step(super.model,
direction = "forward",
scope = (ABOVE50K ~AGE + CAPITALGAIN + EDUCATIONNUM + HOURSPERWEEK + CAPITALLOSS),
trace = 0)
summary(sub.model)
Call:
glm(formula = ABOVE50K ~ EDUCATIONNUM + AGE + HOURSPERWEEK +
CAPITALGAIN + CAPITALLOSS, data = trainingData)
Deviance Residuals:
Min 1Q Median 3Q Max
-1.30068 -0.36853 -0.00151 0.37907 1.16576
Coefficients:
Estimate Std. Error t value Pr(>|t|)
(Intercept) -0.8607493215 0.0235767419 -36.51 <0.0000000000000002 ***
EDUCATIONNUM 0.0599233849 0.0016031719 37.38 <0.0000000000000002 ***
AGE 0.0092871239 0.0003158898 29.40 <0.0000000000000002 ***
HOURSPERWEEK 0.0077724553 0.0003416700 22.75 <0.0000000000000002 ***
CAPITALGAIN 0.0000049110 0.0000003842 12.78 <0.0000000000000002 ***
CAPITALLOSS 0.0000884968 0.0000086535 10.23 <0.0000000000000002 ***
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
(Dispersion parameter for gaussian family taken to be 0.1816425)
Null deviance: 2744.0 on 10975 degrees of freedom
Residual deviance: 1992.6 on 10970 degrees of freedom
AIC: 12435
Number of Fisher Scoring iterations: 2
# 추가적으로 dummy coding 이 적용되었음을 볼 수 있다.
# 아래 결과는 smbinning 을 통해 feature 를 selection 한 결과와는 다소 차이가 있는데, selection 의 기준이 다른 것이지 어느게 맞고 틀리고의 문제는 아니다.
# ( Stepwise regression은 논란의 여지가 있다. 이 방법을 통해서 좋은 모형을 찾을 수는 있지만 최선의 모형이라는 보장은 없다고 한다. )
super.model = glm(ABOVE50K ~ . , data = trainingData)
sub.model = step(super.model,
direction = "backward",
trace = 0)
summary(sub.model)
Call:
glm(formula = ABOVE50K ~ AGE + WORKCLASS + EDUCATION + MARITALSTATUS +
OCCUPATION + RELATIONSHIP + SEX + CAPITALGAIN + CAPITALLOSS +
HOURSPERWEEK, data = trainingData)
Deviance Residuals:
Min 1Q Median 3Q Max
-1.16358 -0.24830 0.04366 0.26503 1.23987
Coefficients: (1 not defined because of singularities)
Estimate Std. Error t value Pr(>|t|)
(Intercept) -0.2176612302 0.0620936039 -3.505 0.000458 ***
AGE 0.0039158938 0.0003480717 11.250 < 0.0000000000000002 ***
WORKCLASS Federal-gov 0.1483278291 0.0307674444 4.821 0.00000144813701874 ***
WORKCLASS Local-gov 0.0189662061 0.0276407711 0.686 0.492622
WORKCLASS Never-worked 0.1316368230 0.1865781872 0.706 0.480494
WORKCLASS Private 0.0606786508 0.0241217712 2.516 0.011900 *
WORKCLASS Self-emp-inc 0.0922718863 0.0292939172 3.150 0.001638 **
WORKCLASS Self-emp-not-inc 0.0160970788 0.0270663080 0.595 0.552038
WORKCLASS State-gov -0.0047074598 0.0300679722 -0.157 0.875594
WORKCLASS Without-pay -0.0539326449 0.2154031550 -0.250 0.802298
EDUCATION 11th 0.0005553596 0.0330492619 0.017 0.986593
EDUCATION 12th 0.0143839256 0.0416193099 0.346 0.729645
EDUCATION 1st-4th -0.1584027879 0.0581623653 -2.723 0.006470 **
EDUCATION 5th-6th -0.1199547846 0.0473723410 -2.532 0.011350 *
EDUCATION 7th-8th -0.1110682470 0.0386398760 -2.874 0.004055 **
EDUCATION 9th -0.0564954363 0.0425877132 -1.327 0.184680
EDUCATION Assoc-acdm 0.1421904469 0.0317469646 4.479 0.00000758018607599 ***
EDUCATION Assoc-voc 0.1428015087 0.0304761755 4.686 0.00000282406418285 ***
EDUCATION Bachelors 0.2292445880 0.0267800900 8.560 < 0.0000000000000002 ***
EDUCATION Doctorate 0.3208177158 0.0363621562 8.823 < 0.0000000000000002 ***
EDUCATION HS-grad 0.0498731514 0.0256111266 1.947 0.051522 .
EDUCATION Masters 0.2648763068 0.0291740439 9.079 < 0.0000000000000002 ***
EDUCATION Preschool -0.2855220829 0.1102914318 -2.589 0.009644 **
EDUCATION Prof-school 0.3088747268 0.0344194361 8.974 < 0.0000000000000002 ***
EDUCATION Some-college 0.1187370026 0.0261210670 4.546 0.00000553567358735 ***
MARITALSTATUS Married-AF-spouse 0.2923877218 0.1332320772 2.195 0.028215 *
MARITALSTATUS Married-civ-spouse 0.1925430790 0.0481188830 4.001 0.00006338343712847 ***
MARITALSTATUS Married-spouse-absent 0.0245921424 0.0365667163 0.673 0.501262
MARITALSTATUS Never-married -0.0238518146 0.0149377972 -1.597 0.110352
MARITALSTATUS Separated -0.0216743671 0.0255018884 -0.850 0.395393
MARITALSTATUS Widowed 0.0210239155 0.0259651211 0.810 0.418131
OCCUPATION Adm-clerical 0.0063112701 0.0208946494 0.302 0.762618
OCCUPATION Armed-Forces -0.1742573735 0.2165631268 -0.805 0.421040
OCCUPATION Craft-repair 0.0434817843 0.0194093726 2.240 0.025095 *
OCCUPATION Exec-managerial 0.1620763288 0.0195193418 8.303 < 0.0000000000000002 ***
OCCUPATION Farming-fishing -0.1264055860 0.0272153570 -4.645 0.00000344644199015 ***
OCCUPATION Handlers-cleaners -0.0569818919 0.0260198885 -2.190 0.028550 *
OCCUPATION Machine-op-inspct -0.0428607606 0.0228215134 -1.878 0.060396 .
OCCUPATION Other-service -0.0436358817 0.0217759172 -2.004 0.045110 *
OCCUPATION Priv-house-serv -0.0306822525 0.0626331702 -0.490 0.624234
OCCUPATION Prof-specialty 0.1350309036 0.0207405073 6.510 0.00000000007819094 ***
OCCUPATION Protective-serv 0.1318706516 0.0304850745 4.326 0.00001533678611790 ***
OCCUPATION Sales 0.0699466748 0.0199834039 3.500 0.000467 ***
OCCUPATION Tech-support 0.1349436628 0.0266019579 5.073 0.00000039865911098 ***
OCCUPATION Transport-moving NA NA NA NA
RELATIONSHIP Not-in-family -0.1392870330 0.0478823987 -2.909 0.003634 **
RELATIONSHIP Other-relative -0.1875317170 0.0472994733 -3.965 0.00007393384645715 ***
RELATIONSHIP Own-child -0.1786630248 0.0477186530 -3.744 0.000182 ***
RELATIONSHIP Unmarried -0.1457543619 0.0498602048 -2.923 0.003471 **
RELATIONSHIP Wife 0.1716370871 0.0191453005 8.965 < 0.0000000000000002 ***
SEX Male 0.0953608305 0.0121372899 7.857 0.00000000000000431 ***
CAPITALGAIN 0.0000041883 0.0000003408 12.290 < 0.0000000000000002 ***
CAPITALLOSS 0.0000568831 0.0000075652 7.519 0.00000000000005952 ***
HOURSPERWEEK 0.0041407861 0.0003270325 12.662 < 0.0000000000000002 ***
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
(Dispersion parameter for gaussian family taken to be 0.1374828)
Null deviance: 2744.0 on 10975 degrees of freedom
Residual deviance: 1501.7 on 10923 degrees of freedom
AIC: 9424.2
Number of Fisher Scoring iterations: 2
# stepwise regression 은 가능한 모든 조합을 탐색하지는 않지만,
# all subsets regression 은 가능한 모든 조합을 탐색하여, 각 예측인자별로 best n 개 ( nbest ) 를 표시한다.
# 하지만 이 방법은 feature set 의 크기에 따라, 수행시간이 매우 길어지는 단점이 있다. ( really.big argument ㅜㅜ)
# all_subset_regression <- regsubsets(ABOVE50K ~ ., data = trainingData, nbest = 2, really.big = T)
library(leaps)
all_subset_regression <- regsubsets(
ABOVE50K ~ AGE + WORKCLASS + EDUCATION + OCCUPATION + RELATIONSHIP + SEX + CAPITALGAIN + CAPITALLOSS,
data = trainingData,
nbest = 2
)
1 linear dependencies found
Reordering variables and trying again:
plot(all_subset_regression, scale = "adjr2") # scale = [rsq|rss|adjr2|cp|bic|outmat]

# 위 plot 의 각 행의 색깔이 칠해진 것이 feature 의 갯수이다.
# 위에서 nbest = 2 를 주었으므로, 2개가 색칠된 것이 아래부터 2개이고,
# 그위에는 3개가 색칠된 것이 3개이고 이런식이다. 이 경우, adjr2 를 기준으로 best 를 찾은 것이니 1 에 가까운 모델이 최적이다.
Multinomial Regression
# ref : https://onlinecourses.science.psu.edu/stat504/node/40
# ref : http://r-statistics.co/Multinomial-Regression-With-R.html
#
#1. Random component : Multinomial Distribution ( Y , multi levels )
#2. Systematic component : Explanatory var. ( can be continuous / discret | Xs )
#3. Link function : Generalized Logit
cmcData <- read.csv("http://archive.ics.uci.edu/ml/machine-learning-databases/cmc/cmc.data", stringsAsFactors=FALSE, header=F)
colnames(cmcData) <- c("wife_age", "wife_edu", "hus_edu", "num_child", "wife_rel", "wife_work", "hus_occu", "sil", "media_exp", "cmc")
head(cmcData, n = 1)
levels(as.factor(cmcData$cmc))
[1] "1" "2" "3"
cmcData <- transform(cmcData, cmc <- as.factor(cmc))
# random component 의 distribution 의 type 과 그에 따른 link function 이 달라진 것 이외에는
# 큰 차이가 없어 추가적인 설명없이, nnet package 의 multinom function 을 통한 prediction 까지만 수행한다.
# summary 결과를 보면, 각 level 별 coefficient 값이 estimation 됨을 알 수 있다.
library(nnet)
model <- multinom(cmc ~ . , data = cmcData)
# weights: 33 (20 variable)
initial value 1618.255901
iter 10 value 1425.547165
iter 20 value 1393.032613
final value 1391.288728
converged
summary(model)
Call:
multinom(formula = cmc ~ ., data = cmcData)
Coefficients:
(Intercept) wife_age wife_edu hus_edu num_child wife_rel wife_work hus_occu sil media_exp
2 -3.2489937 -0.04552648 0.8841599 -0.08376536 0.3446932 -0.4787242 0.03124732 -0.07945559 0.3419976 -0.4421317
3 -0.1244396 -0.10557077 0.3695350 0.05643188 0.3505750 -0.3249388 0.16619955 0.18149509 0.2280536 -0.4756168
Std. Errors:
(Intercept) wife_age wife_edu hus_edu num_child wife_rel wife_work hus_occu sil media_exp
2 0.7592481 0.01205427 0.11453340 0.1339649 0.04287206 0.2004112 0.1683670 0.09724308 0.09679462 0.3880349
3 0.6270848 0.01124560 0.08746493 0.1006902 0.03860957 0.1980680 0.1506602 0.08437123 0.07253987 0.2726890
Residual Deviance: 2782.577
AIC: 2822.577
cmcData$pred <- predict(model, cmcData)
cmcData <- cbind(cmcData, as.data.frame(predict(model, cmcData, type = "prob")))
table(cmcData$pred, cmcData$cmc)
1 2 3
1 407 96 181
2 43 122 84
3 179 115 246
# predict 의 type 으로 prob 을 지정하는 경우, 각 level 이 될 확률값을 matrix 로 반환하게 된다.
head(cmcData[c("cmc", "pred", "1", "2", "3")])
# vglm package 를 사용하면, model summary 로 significance 값을 알 수 있다.
cmcData <- read.csv("http://archive.ics.uci.edu/ml/machine-learning-databases/cmc/cmc.data", stringsAsFactors=FALSE, header=F)
colnames(cmcData) <- c("wife_age", "wife_edu", "hus_edu", "num_child", "wife_rel", "wife_work", "hus_occu", "sil", "media_exp", "cmc")
library(VGAM)
model <- vglm(cmc ~ . , family = multinomial(refLevel = 1), data = cmcData)
exp(coef(model))
(Intercept):1 (Intercept):2 wife_age:1 wife_age:2 wife_edu:1 wife_edu:2 hus_edu:1 hus_edu:2 num_child:1 num_child:2
0.03881314 0.88298963 0.95549418 0.89981058 2.42095796 1.44706290 0.91964531 1.05805549 1.41155837 1.41988463
wife_rel:1 wife_rel:2 wife_work:1 wife_work:2 hus_occu:1 hus_occu:2 sil:1 sil:2 media_exp:1 media_exp:2
0.61957124 0.72257099 1.03173928 1.18080883 0.92361870 1.19900979 1.40775746 1.25615273 0.64268382 0.62150338
summary(model)
Call:
vglm(formula = cmc ~ ., family = multinomial(refLevel = 1), data = cmcData)
Pearson residuals:
Min 1Q Median 3Q Max
log(mu[,2]/mu[,1]) -2.285 -0.5427 -0.2721 -0.07947 8.309
log(mu[,3]/mu[,1]) -2.363 -0.7109 -0.3746 0.99564 3.436
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept):1 -3.24900 0.75925 -4.279 0.000018754188419641 ***
(Intercept):2 -0.12444 0.62708 -0.198 0.842697
wife_age:1 -0.04553 0.01205 -3.777 0.000159 ***
wife_age:2 -0.10557 0.01125 -9.388 < 0.0000000000000002 ***
wife_edu:1 0.88416 0.11453 7.720 0.000000000000011661 ***
wife_edu:2 0.36954 0.08746 4.225 0.000023898352591387 ***
hus_edu:1 -0.08377 0.13396 -0.625 0.531779
hus_edu:2 0.05643 0.10069 0.560 0.575166
num_child:1 0.34469 0.04287 8.040 0.000000000000000898 ***
num_child:2 0.35058 0.03861 9.080 < 0.0000000000000002 ***
wife_rel:1 -0.47873 0.20041 -2.389 0.016907 *
wife_rel:2 -0.32494 0.19807 -1.641 0.100892
wife_work:1 0.03125 0.16837 0.186 0.852772
wife_work:2 0.16620 0.15066 1.103 0.269965
hus_occu:1 -0.07946 0.09724 -0.817 0.413879
hus_occu:2 0.18150 0.08437 2.151 0.031464 *
sil:1 0.34200 0.09679 3.533 0.000411 ***
sil:2 0.22805 0.07254 3.144 0.001667 **
media_exp:1 -0.44210 0.38803 -1.139 0.254559
media_exp:2 -0.47561 0.27269 -1.744 0.081131 .
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
Number of linear predictors: 2
Names of linear predictors: log(mu[,2]/mu[,1]), log(mu[,3]/mu[,1])
Residual deviance: 2782.577 on 2926 degrees of freedom
Log-likelihood: -1391.289 on 2926 degrees of freedom
Number of iterations: 5
Reference group is level 1 of the response
# mlogit package 를 사용해볼 수도 있다.
# https://cran.r-project.org/web/packages/mlogit/vignettes/mlogit.pdf
Poisson Regression
# ref : https://onlinecourses.science.psu.edu/stat504/node/165
# ref : http://wiki.stat.ucla.edu/socr/index.php/AP_Statistics_Curriculum_2007_Distrib_Poisson
#
#1. Random component : Poisson, QuasiPoisson Distribution ( Y )
#2. Systematic component : Explanatory var. ( can be continuous / discret | Xs )
#3. Link function : Log , Identity
#
# 웹서비스를 제공하면서, Poisson Distribution 을 겪을 수 있는 케이스
# O2O 배달주문, 콜 호출
# 그외 각종 count 류의 데이터들 ( 사이버가 아니라 현실과 가까울 수록 )
# Poisson Distribution
# Discret Prob. Distribution > Binomial Distribution , Poisson Distribution
# 실서비스의 데이터를 사용하면 제일 좋지만, rpubs 에 게시하기로 했으므로
# http://data.princeton.edu/wws509/datasets/#ceb 를 사용한다.
#
library(foreign)
data <- read.dta("http://data.princeton.edu/wws509/datasets/ceb.dta")
library(dplyr)
glimpse(data)
par(mfrow = c(3,2))
plot(density(data$n))
plot(density(data$mean))
car::qqPlot(data$n)
# Clearly the variance increases with the mean.
upper_20 <- subset(data, n >= 20)
plot(log(upper_20$mean), log(upper_20$var))
abline(0,1)
# dependent variable : y = mean number of children ever born * number of women in the cell
data$y <- round(data$mean * data$n, 0)
plot(density(data$y))
plot(data$n, data$y)

# If the number of CEB to one woman in a given cell is a Poisson random variable with mean (and variance) μ,
# then the number born to all n women in that cell is a Poisson r.v. with mean (and variance) nμ.
# The log of the expected sum is log(n)+log(μ), and consists of a known offset and the quantity we are interested in modeling.
data$os <- log(data$n)
model.0 <- glm( y ~ 1, offset = os, data = data, family = poisson)
summary(model.0)
Call:
glm(formula = y ~ 1, family = poisson, data = data, offset = os)
Deviance Residuals:
Min 1Q Median 3Q Max
-18.6368 -4.4774 -0.8548 2.5292 21.9744
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept) 1.376346 0.009712 141.7 <0.0000000000000002 ***
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
(Dispersion parameter for poisson family taken to be 1)
Null deviance: 3731.9 on 69 degrees of freedom
Residual deviance: 3731.9 on 69 degrees of freedom
AIC: 4163.3
Number of Fisher Scoring iterations: 5
paste("exp(coef(model.0)) : ", exp(coef(model.0)), " == sum(data$y)/sum(data$n) : ", sum(data$y)/sum(data$n))
[1] "exp(coef(model.0)) : 3.96040343668286 == sum(data$y)/sum(data$n) : 3.96040343668285"
model.res <- glm( y ~ res, offset = os, data = data, family = poisson)
summary(model.res)
Call:
glm(formula = y ~ res, family = poisson, data = data, offset = os)
Deviance Residuals:
Min 1Q Median 3Q Max
-19.6141 -4.1326 -0.3872 3.2787 20.1998
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept) 1.20460 0.02499 48.199 < 0.0000000000000002 ***
resUrban 0.14429 0.03245 4.447 0.000008716338818415 ***
resRural 0.22806 0.02783 8.194 0.000000000000000252 ***
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
(Dispersion parameter for poisson family taken to be 1)
Null deviance: 3731.9 on 69 degrees of freedom
Residual deviance: 3659.3 on 67 degrees of freedom
AIC: 4094.8
Number of Fisher Scoring iterations: 5
exp(coef(model.res))
(Intercept) resUrban resRural
3.335417 1.155219 1.256160
c(deviance(model.0)-deviance(model.res), deviance(model.res))
[1] 72.57247 3659.27915
all_subset_regression <- regsubsets(
y ~ offset(os) + dur + res + educ,
data = data,
nbest = 2
)
plot(all_subset_regression, scale = "bic") # scale = [rsq|rss|adjr2|cp|bic|outmat]

model.all <- glm( y ~ dur + res + educ, offset = os, data = data, family = poisson)
summary(model.all)
Call:
glm(formula = y ~ dur + res + educ, family = poisson, data = data,
offset = os)
Deviance Residuals:
Min 1Q Median 3Q Max
-2.2960 -0.6641 0.0725 0.6336 3.6782
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept) -0.11710 0.05491 -2.132 0.032969 *
dur5-9 0.99693 0.05274 18.902 < 0.0000000000000002 ***
dur10-14 1.36940 0.05107 26.815 < 0.0000000000000002 ***
dur15-19 1.61376 0.05119 31.522 < 0.0000000000000002 ***
dur20-24 1.78491 0.05121 34.852 < 0.0000000000000002 ***
dur25+ 1.97641 0.05003 39.501 < 0.0000000000000002 ***
resUrban 0.11242 0.03250 3.459 0.000541 ***
resRural 0.15166 0.02833 5.353 0.0000000863 ***
educLower primary 0.02297 0.02266 1.014 0.310597
educUpper primary -0.10127 0.03099 -3.268 0.001082 **
educSecondary+ -0.31015 0.05521 -5.618 0.0000000194 ***
---
Signif. codes: 0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
(Dispersion parameter for poisson family taken to be 1)
Null deviance: 3731.852 on 69 degrees of freedom
Residual deviance: 70.665 on 59 degrees of freedom
AIC: 522.14
Number of Fisher Scoring iterations: 4
exp(coef(model.all))
(Intercept) dur5-9 dur10-14 dur15-19 dur20-24 dur25+ resUrban
0.8894987 2.7099627 3.9329722 5.0216439 5.9590510 7.2167534 1.1189812
resRural educLower primary educUpper primary educSecondary+
1.1637648 1.0232387 0.9036856 0.7333373
c(deviance(model.0)-deviance(model.all), deviance(model.all))
[1] 3661.1863 70.6653
dur_count <- t(data %>% dplyr::group_by(dur) %>% summarise(mean = sum(mean) / n()))
res_count <- t(data %>% dplyr::group_by(res) %>% summarise(mean = sum(mean) / n()))
count <- cbind(dur_count, res_count)
colnames(count) <- as.character(unlist(count[1, ]))
count[rownames(count) == "mean", ]
0-4 5-9 10-14 15-19 20-24 25+ Suva Urban Rural
"0.8891667" "2.6300000" "3.5541666" "4.2216667" "4.9841667" "6.3380000" "3.267917" "3.998696" "3.840435"
models <- c("dur+res*educ","dur*res+educ","dur*educ+res",
"(dur+res)*educ","(dur+educ)*res","dur*(res+educ)",
"dur*res*educ - dur:res:educ")
dd <- matrix(0, length(models), 2)
i <- 1
for(model in models) {
formula <- paste("y ~ offset(os) + ",model)
m <- glm(formula, family=poisson, data=data)
dd[i,] <- c(deviance(m), m$df.residual)
i <- i+1
}
data.frame(model=models,deviance=round(dd[,1],2),
pval=round(pchisq(dd[,1],dd[,2],lower.tail=FALSE),4))
# 위에서, formula 에 들어가는 모든 feature 들의 subset 에 대해 평가하는 시도를 해봤는데,
# 특히 그 조합의 수가 많은 경우 매우 느리다는 것을 보았다.
# 이런 경우, 계산량을 줄이는 기법 중에 하나가 Ridge 혹은 Lasso Regression 이다.
Model Selection ( Statistical Technicals )
# 아래 Ridge 와 Lasso 를 보기전에, Model Selection 에 대한 부분을 디벼 보자.
#
# ref : https://lagunita.stanford.edu/c4x/HumanitiesScience/StatLearning/asset/model_selection.pdf
# ref : http://sosal.kr/868
# ref : http://www.statground.org/?module=file&act=procFileDownload&file_srl=9145&sid=a0a4e7fd21503e45194d485ccb0c5476&module_srl=137
#
# 1. Subset Selection : like a regsubsets function ( estimate model based on AIC , BIC , ADJR2 , CP .. )
# : Stepwise Selection ( Backward / Forward ) or regsubsets ( 위에서 수행한 내용 )
# 2. Shrinkage ( Regularization ) : Lasso , Ridge , ElasticNet
# : shrinks the coefficient estimates towards zero
# 3. Dimension Reduction : PCA
#
# Occam's Razor in Model Selection ( 최소의 feature , 설명변수로 설명을 하자 )
## All things being equal, usually the simplest explanation of a phenomenon is a good hypothesis.
## Simplicity = representational succinctness
## 통계 모델링에서 간결함의 원리
# - 복잡한 설명보다 단순하고 간단한 설명이 좋다.
# - 모형에 있어서 모수는 가능한 적게 가지고 있어야 한다.
# - 선형 모델이 비선형 모델보다 좋다.
# - 적은 수의 가정을 가진 실험은 많은 가정을 가진 실험보다 좋다.
# - 데이터로부터 회귀모델을 구할 때는 위해선 최소적합이 될 때까지 축소해야한다.
## 단순화 작업 목록
# - 유의하지 않은 교호작용 항목을 제거한다.
# - 유의하지 않은 2차 또는 비선형 항목을 제거한다.
# - 유의하지 않은 설명 변수를 제거한다.
# - 유사한 모수값을 갖는 설명 변수를 통합한다.
#
# 선형회귀모형에서 모형계수 벡터(coefficient estimated value) 에 대한 최소제곱 해보다
# 이것을 약간 축소한 ridge 해를 쓰는 것이 예측 성과가 좋은 것으로 알려져 있다.
# 또한 모형계수 벡터의 일부요소를 0으로 퇴화시킨 lasso 해를 쓰게 되면 모형이 간결해진다는 잇점이 있다.
Ridge Regression ( Linear Regression with L2 regularization, α=0 )
# ref : https://onlinecourses.science.psu.edu/stat857/node/155
# ref : https://ncss-wpengine.netdna-ssl.com/wp-content/themes/ncss/pdf/Procedures/NCSS/Ridge_Regression.pdf
# ref : https://lagunita.stanford.edu/c4x/HumanitiesScience/StatLearning/asset/model_selection.pdf
# ref : https://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html
# ref : https://drsimonj.svbtle.com/ridge-regression-with-glmnet
# ref : https://gerardnico.com/wiki/lang/r/ridge_lasso#formula_parameters
# ref : http://r-bong.blogspot.kr/p/blog-page_4.html
#
# Motivation: too many predictors
# Motivation: ill-conditioned X
# Motivation: 다중공분산성 존재 해결
library(glmnet)
data(BinomialExample)
glimpse(as.data.frame(x))
Observations: 100
Variables: 30
$ V1 <dbl> -0.619261352, 1.094272782, -0.356704020, -2.469070123, 0.567288518, 0.912925427, 0.095673049, 1.934206669, 0.282757006, 0.80...
$ V2 <dbl> 0.01624409, 0.47257285, 0.30121334, 2.84771447, 0.88888747, 0.77350086, 0.14027229, -0.71114983, 1.05940570, 1.53674274, 2.5...
$ V3 <dbl> -0.62606831, -1.33714704, 0.19056192, 1.66024352, -0.01158671, 0.55836355, -0.76043921, -0.27387147, -0.03944966, -1.0123076...
$ V4 <dbl> 0.41268461, -0.64058126, 0.23402677, 1.56881297, 0.57627526, -0.53509922, -0.04935541, 1.00113828, 0.30277367, -0.38480878, ...
$ V5 <dbl> 0.49443737, 0.28231989, 0.16980865, -0.83305695, -0.86894535, 0.35070935, 1.57409924, 1.04390121, -0.91617615, -2.03190998, ...
$ V6 <dbl> -0.44932691, -0.60933212, 1.22914266, -0.56200878, -0.31325709, -0.57630209, -0.12409033, 0.80288927, 0.69149343, 0.22363140...
$ V7 <dbl> 0.67600532, 0.35472319, 1.16280950, -0.61424552, 0.69029066, -0.38826725, -1.11062763, -0.60357694, 0.60875533, -1.16288468,...
$ V8 <dbl> -0.067714189, -0.626865146, 0.880242416, -1.765298380, -1.299611997, 0.555186632, 1.728954516, -0.511363802, 0.309215943, -0...
$ V9 <dbl> -1.47470315, -0.11572657, 0.76164309, 0.39023457, -0.96736399, 0.35695623, -1.24507511, 0.42946576, 1.03080204, -0.72415080,...
$ V10 <dbl> 1.07591778, -0.31270712, -1.18080414, 1.79400617, -0.27323220, 1.36296403, -0.44391646, 0.51898565, -0.03086332, -0.04368505...
$ V11 <dbl> 0.57060390, 0.41386677, -0.48768528, 0.46447534, -0.52395953, -0.78199306, 0.36040354, 0.95508062, 0.12818637, 0.27686071, -...
$ V12 <dbl> -0.09864730, -1.87169972, 0.45650048, 0.51681031, -0.82159177, 0.60533784, -1.93464482, 0.59361080, -1.61166897, -0.20969135...
$ V13 <dbl> 1.2099852651, 0.1640714232, 0.6450244725, -1.0808010261, 0.5460573463, -0.4721640040, -0.5793974421, -0.5499844788, 0.201644...
$ V14 <dbl> -1.067236343, 0.772106042, 1.752761666, -0.298094014, -0.515107637, 1.255609733, 0.425012238, -0.117441666, -0.721208510, 0....
$ V15 <dbl> 0.34329125, -0.86250855, 0.49003474, -0.58492559, -0.13621841, -1.18593654, -1.60255584, -1.13825281, -0.86039000, 0.5039227...
$ V16 <dbl> -0.02255467, 1.46205409, 2.27150850, -1.35886288, -1.11128459, -2.60167966, 0.37601661, -0.43159934, 0.20612204, -2.21481512...
$ V17 <dbl> -0.10206712, -0.43697967, -0.73408583, -0.65949297, -0.97840076, -0.34922893, -0.14361636, -1.60487751, -0.01159857, 0.05097...
$ V18 <dbl> 0.141396200, -1.040576427, 0.976631268, -1.199244134, -1.377847577, 0.162100751, -0.313691971, -1.115409953, 0.189800512, 0....
$ V19 <dbl> -0.54935769, -0.60271031, -0.35846388, 0.20162167, -1.35167004, -0.87035201, 0.86895743, 0.27109331, 0.65493038, 1.71682268,...
$ V20 <dbl> -0.201680275, -0.320569476, -0.080051607, 0.507079112, 0.959261661, -1.748484377, -0.350490405, 0.725738748, -0.984670053, -...
$ V21 <dbl> 0.45660069, 0.21247573, 1.24529573, 0.67274655, 0.49191549, -0.20263506, 0.27961034, -0.22359249, 0.15490587, 0.24866870, -0...
$ V22 <dbl> 0.80728018, 0.61291024, 1.01187663, -0.42514840, -1.34002195, 1.70688487, -1.44030057, -0.16096838, 1.59133102, -0.32262962,...
$ V23 <dbl> 0.01473546, -0.81898245, 0.03927982, -0.98728378, -0.13288456, -1.51250049, -0.22509945, 0.30174828, -1.26593344, -0.5384656...
$ V24 <dbl> -1.116096788, 2.903714215, 1.017275065, -0.401273920, 0.219702267, 1.176929799, 0.471839849, -1.001070418, -2.251378574, -0....
$ V25 <dbl> -0.015876170, -0.157830993, 0.297052891, -2.066153107, 0.789746549, 1.668301931, -1.731136499, -1.854376870, -0.513064119, 1...
$ V26 <dbl> 1.14549082, -2.10469356, 0.40180292, -0.55248745, -0.14745205, 0.06319776, 1.00031874, 1.92738918, -0.99683357, 1.59311684, ...
$ V27 <dbl> 0.94175286, 0.64084422, 1.92464695, -1.37902657, -0.80188950, 0.29071513, 0.61124388, -0.12412178, -0.45950970, 0.71393487, ...
$ V28 <dbl> 1.43715303, 0.01236235, 0.31108274, 0.09518939, 0.77559612, -0.73832848, 0.34301517, -2.00604840, 0.90450461, 0.41088674, -0...
$ V29 <dbl> -0.92783303, 0.48111055, 0.89830290, -0.38971056, 1.11845955, -0.40887682, 0.52683668, 0.29409299, -1.41784242, 0.95574856, ...
$ V30 <dbl> 0.9080937, -2.0492817, -1.2089006, 1.7796744, -1.1970731, -1.0545311, -0.1119846, -0.1780586, 0.5141867, 1.5930828, -0.34353...
model.ridge <- glmnet(x, y, family = "binomial", alpha = 0 )
par(mfrow=c(2,2))
plot(density(y))
plot(model.ridge, xvar="lambda", label=TRUE)
plot(model.ridge, xvar="norm", label=TRUE)
plot(model.ridge, xvar="dev", label=TRUE)

cv.ridge <- cv.glmnet(x, y, alpha = 0, family = "binomial", nfolds = 100)
Option grouped=FALSE enforced in cv.glmnet, since < 3 observations per fold
plot(cv.ridge)

coef(cv.ridge, s = cv.ridge$lambda.min)
31 x 1 sparse Matrix of class "dgCMatrix"
1
(Intercept) 0.1718290283
V1 0.1148574142
V2 0.5068431000
V3 -0.3384649794
V4 -0.8634050979
V5 -0.3141436782
V6 -0.6956355852
V7 0.0798900376
V8 -0.5167458568
V9 0.5193890584
V10 -1.0182682093
V11 -0.2077506627
V12 -0.2218540968
V13 -0.1638673635
V14 0.1370473811
V15 0.0388320169
V16 0.3621440665
V17 -0.1226309533
V18 -0.1492504287
V19 -0.0497939458
V20 -0.2024006258
V21 0.0006531455
V22 0.2456970018
V23 0.4333057414
V24 -0.1769632495
V25 0.5320062623
V26 -0.3875044960
V27 -0.2157079430
V28 0.3337625633
V29 -0.2659968175
V30 0.1601149964
library(doMC)
registerDoMC(cores = 4)
cv.ridge <- cv.glmnet(x, y, alpha = 0, family = "binomial", nfolds = 100, type.measure = "class")
Option grouped=FALSE enforced in cv.glmnet, since < 3 observations per fold
plot(cv.ridge)

foldid <- sample(1:10,size=length(y),replace=TRUE)
cv.1 <- cv.glmnet(x,y,foldid=foldid,alpha=1)
cv.05 <- cv.glmnet(x,y,foldid=foldid,alpha=.5)
cv.0 <- cv.glmnet(x,y,foldid=foldid,alpha=0)
par(mfrow=c(2,2))
plot(cv.1);plot(cv.05);plot(cv.0)
plot(log(cv.1$lambda),cv.1$cvm,pch=19,col="red",xlab="log(Lambda)",ylab=cv.1$name)
points(log(cv.05$lambda),cv.05$cvm,pch=19,col="grey")
points(log(cv.0$lambda),cv.0$cvm,pch=19,col="blue")
legend("topleft",legend=c("alpha= 1","alpha= .5","alpha 0"),pch=19,col=c("red","grey","blue"))

Lasso Regression
ElasticNet Regression
LS0tCnRpdGxlOiAiYWR2YW5jZWRfcmVncmVzc2lvbl9tb2RlbHMiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCmBgYHtyfQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojIGFkdmFuY2VkIHJlZ3Jlc3Npb24gbW9kZWxzICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIAojIHJlZiA6IGh0dHA6Ly9yLXN0YXRpc3RpY3MuY28vYWR2LXJlZ3Jlc3Npb24tbW9kZWxzLmh0bWwgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIHJlZiA6IGh0dHBzOi8vb25saW5lY291cnNlcy5zY2llbmNlLnBzdS5lZHUvc3RhdDUwNC9ub2RlLzIxNiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIHJlZiA6IGh0dHBzOi8vYmxvZy5jbG91ZGVyYS5jb20vYmxvZy8yMDE1LzEyL2NvbW1vbi1wcm9iYWJpbGl0eS1kaXN0cmlidXRpb25zLXRoZS1kYXRhLXNjaWVudGlzdHMtY3JpYi1zaGVldC8gIwojIHJlZiA6IGh0dHA6Ly9yc3R1ZGlvLXB1YnMtc3RhdGljLnMzLmFtYXpvbmF3cy5jb20vMTkwOTk3XzQwZmEwOWRiOGUzNDRiMTliMTRhNjg3ZWE1ZGU5MTRiLmh0bWwgICAgICAgICAgICAgICAgIwojIHJlZiA6IGh0dHA6Ly9rb3N0YXQuZ28ua3IvYXR0YWNoL2pvdXJuYWwvMTItMi0zLnBkZiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwoKIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiMgcGFja2FnZSAmIG1ldGhvZCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIwojIHNtYmlubmluZyA6IGh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9zbWJpbm5pbmcvc21iaW5uaW5nLnBkZiAgICAgICAgICAgICAgICAgICAgICAgICMKIyAgICAgICAgICAgOiBzbWJpbm5pbmcuZmFjdG9yKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjCiMgSW5mb3JtYXRpb25WYWx1ZSA6IGh0dHBzOi8vY3Jhbi5yLXByb2plY3Qub3JnL3dlYi9wYWNrYWdlcy9JbmZvcm1hdGlvblZhbHVlL0luZm9ybWF0aW9uVmFsdWUucGRmICAgIwojICAgICAgICAgICAgICAgICAgOiBvcHRpbWFsQ3V0b2ZmKCkgLCBwbG90Um9jKCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMKIyBnbG1uZXQgOiBodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvZ2xtbmV0L2dsbW5ldC5wZGYgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwpgYGAKCmBgYHtyfQojIGxpbmVhciByZWdyZXNzaW9uIOydmCDqsIDsoJXspJEgZGVwZW5kZW50IHZhcmlhYmxlIOygleq3nOu2hO2PrO2VtOyVvCDtlZzri6TripQg6rKD7J20IOyeiOuKlOuNsCwKIyDsnbQg6rCA7KCV7J2ALCDshJzruYTsiqTri6jsl5DshJzripQg7JW16rCE7ZWY66m0IOunnuy2lOq4sCDtnpjrk6Ag6rCA7KCV7J2064ukLgojIGRlcG5lbmRlbnQgdmFsdWUg6rCAIOuLpOyWke2VnCDrtoTtj6zrpbwg6rCA7KeI65WMLCDsgqzsmqntlaAg7IiYIOyeiOuKlCBnbG0g7JeQIOuMgO2VtOyEnCDsoJXrpqwKYGBgCiFbXSgvVXNlcnMvQ0EvRG93bmxvYWRzL2ZhbWlseWcucG5nKQoKIyMgR0xNCgpgYGB7cn0KIyBHZW5lcmFsIExpbmVhciBNb2RlbCAKIyAgICAgICAgcmVmZXJzIHRvIGNvbnZlbnRpb25hbCBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbHMgZm9yIGEgY29udGludW91cyByZXNwb25zZSB2YXJpYWJsZSAKIyAgICAgICAgZ2l2ZW4gY29udGludW91cyBhbmQvb3IgY2F0ZWdvcmljYWwgcHJlZGljdG9ycwojCiMgR2VuZXJhbGl6ZWQgTGluZWFyIE1vZGVsCiMgICAgICAgIHRoZSByZXNwb25zZSB2YXJpYWJsZSB5aSBpcyBhc3N1bWVkIHRvIGZvbGxvdyBhbiBleHBvbmVudGlhbCBmYW1pbHkgZGlzdHJpYnV0aW9uIHdpdGggbWVhbiDOvGksIAojICAgICAgICB3aGljaCBpcyBhc3N1bWVkIHRvIGJlIHNvbWUgKG9mdGVuIG5vbmxpbmVhcikgZnVuY3Rpb24gb2YgVCh4aSnOsi4KYGBgCiFbXSgvVXNlcnMvQ0EvRG93bmxvYWRzL2ZhbWlseS5wbmcpCgoKYGBge3J9CiMgdGhyZWUgY29tcG9uZW50cwojIyBSYW5kb20gQ29tcG9uZW50IDogdGhlIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBvZiB0aGUgcmVzcG9uc2UgdmFyaWFibGUgKFkpCiMjIFN5c3RlbWF0aWMgQ29tcG9uZW50IDogdGhlIGV4cGxhbmF0b3J5IHZhcmlhYmxlcyAoWDEsIFgyLCAuLi4gWGspIGFzIGEgY29tYmluYXRpb24gb2YgbGluZWFyIHByZWRpY3RvcnM7IGUuZy4gzrIwICsgzrIxeDEgKyDOsjJ4MgojIyBMaW5rIEZ1bmN0aW9uICjOtyBvciBnKM68KSkgOiBzcGVjaWZpZXMgdGhlIGxpbmsgYmV0d2VlbiByYW5kb20gYW5kIHN5c3RlbWF0aWMgY29tcG9uZW50cyAsIGUuZy4gzrcgPSBsb2dpdCjPgCkgZm9yIGxvZ2lzdGljIHJlZ3Jlc3Npb24KIyMgICAgICAgICAgICAgICAgICAgICAgICAgICA6IEdMTeydgCBZIH4gWCDqsIAgbGluZWFyIOq0gOqzhOqwgCDslYTri5guIGxpbmsgZnVuY3Rpb24g7J2E7Ya17ZW07IScLCBsaW5lYXIg6rSA6rOE66W8IOunjOuTpOyWtOyjvOuKlCDsl63tlaAgCiMjICAgICAgICAgICAgICAgICAgICAgICAgICAgOiBiaW5hcnkgKCAwLCAxICkg6rCS66eM7J2EIOqwluuKlCBZIOulvCAsIO2ZleuloOqwnOuFkOycvOuhnCDrs4Dqsr3tlZjsl6wgY29udGludW91cyB2YXJpYWJsZSDroZwg66eM65Ok7Ja07KO864qUIOyXre2VoCAKIyMgICAgICAgICAgICAgICAgICAgICAgICAgICA6IOyVhOuemCDqt7jrprzsl5DshJwgJ3gnIOygkOycvOuhnCDssI3tnojripQgeSDrs4DsiJjqsJLsnYQsIHNpZ21vaWQgY3VydmUg7ZiV7YOc66GcIOuzgO2ZmOyLnO2CpOuKlCDsl63tlaAgCiMjICAgICAgICAgICAgICAgICAgICAgICAgICAgOiBodHRwOi8vd3d3LmNvbHVtYmlhLmVkdS9+c28zMy9TdXNEZXYvTGVjdHVyZV85LnBkZgpgYGAKIVtdKC9Vc2Vycy9DQS9Eb3dubG9hZHMvc2lnbW9pZC5wbmcpCgojIyBCaW5hcnkgTG9naXN0aWMgUmVncmVzc2lvbiAKCmBgYHtyfQojIHJlZiA6IGh0dHA6Ly9yLXN0YXRpc3RpY3MuY28vTG9naXN0aWMtUmVncmVzc2lvbi1XaXRoLVIuaHRtbCNCdWlsZCUyMExvZ2l0JTIwTW9kZWxzJTIwYW5kJTIwUHJlZGljdAojCiMxLiBSYW5kb20gY29tcG9uZW50IDogQmlub21pYWwgRGlzdHJpYnV0aW9uICggWSApCiMyLiBTeXN0ZW1hdGljIGNvbXBvbmVudCA6IEV4cGxhbmF0b3J5IHZhci4gKCBjYW4gYmUgY29udGludW91cyAvIGRpc2NyZXQgfCBYcyApCiMzLiBMaW5rIGZ1bmN0aW9uIDogTG9naXQKIwojIEFzc3VtcHRpb25zCiMjNC4xIGRlcGVuZGVudCB2YXJpYWJsZSDrgbzrpqwgaW5kZXBlbmRlbnQg7ZW07JW87ZWoIAojIzQuMiDsg5jtlIwg642w7J207YSw6rCAIOy2qeu2hO2eiCDrp47slYTslbwg7ZWoLgojCiMgTUxFICggTWF4aW11bSBMaWtlbGlob29kIEVzdGltYXRpb24gKSA6IOyXrOq4sOq5jOyngCDrtJDslbztlZjripTqsIA/IAojIyDsmKTsp4Eg7KO87Ja07KeEIE9ic2VydmF0aW9uLCDtmLnsnYAg642w7J207YSw65OkIOunjOydhCDthqDrjIDroZwgcGFyYW1ldGVyIGVzdGltYXRpb27snYQg7ZWY64qUIOuwqeuylQojIyBvYnNlcnZhdGlvbuyXkCDrlLDrnbwg6re4IOqwkuydtCDrhIjrrLQg66+86rCQ7ZWY6rKMIOuzgO2VnOuLpOuKlCDri6jsoJAgKCBzbywg7IOY7ZSMIOuNsOydtO2EsOqwgCDstqnrtoTtnogg66eO7JWE7JW8IO2VqCApCiMKIyBObyBPdXRsaWVycyAoIDAgb3IgMSApCmBgYAohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9sb2dpdGZ1bmMucG5nKQoKYGBge3J9CiMgcmVmIDogaHR0cDovL3JmcmllbmQudGlzdG9yeS5jb20vOTkKIyBiaW5vbWlhbCBkaXN0cmlidXRpb24KIyBEaXNjcmV0IFByb2IuIERpc3RyaWJ1dGlvbiA+IEJpbm9taWFsIERpc3RyaWJ1dGlvbiAsIFBvaXNzb24gRGlzdHJpYnV0aW9uIAojIAojIOuwmOuzteyLnO2WieyLnCwgU3VjY2VzcyAvIEZhaWwg66eMIOuwnOyDne2VmOuKlCDsvIDsnbTsiqQgKCDrsqDrpbTriITsnbQg7Iuc7ZaJICkKIyDshLHqs7XtmZXrpaDsnbQgcOyduCDrsqDrpbTriITsnbQg7Iuc7ZaJ7J2EIG7rsogg67CY67O17ZaI7J2EIOuVjCDshLHqs7XtlZjripQg7Zqf7IiY66W8IFjrnbwg7ZWY66m0LCDtmZXrpaDrs4DsiJggWOuKlCDrqqjsiJggbuqzvCBw7J24IOydtO2Vreu2hO2PrChCaW5vbWlhbCBkaXN0cmlidXRpbynsnYQg65Sw66W464ukCmBgYAohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9sb2dpc3RpYy5wbmcpCgpgYGB7cn0KeSA8LSBkYmlub20oMDoyMCwgc2l6ZT0yMCwgcHJvYj0wLjUpCnBsb3QoMDoyMCwgeSwgdHlwZT0naCcsIGx3ZD01LCBjb2w9ImdyZXkiLCB5bGFiPSJQcm9iYWJpbGl0eSIsIHhsYWI9Iu2ZleuloOuzgOyImCBYIiwgbWFpbiA9IGMoIlggfiBCKDIwLCAwLjUpIikpCnBsb3QocGJpbm9tKDA6MjAsIHNpemU9MjAsIHByb2I9MC41KSwgdHlwZT0naCcpCgojIHN1bShkYmlub20oMDoxMiwgc2l6ZT0yMCwgcHJvYj0wLjUpKQojIHJiaW5vbSgxMiwgc2l6ZT0yMCwgcHJvYj0wLjUpCmBgYAoKYGBge3J9CmxpYnJhcnkoZGF0YS50YWJsZSkKCmFkdWx0IDwtIGZyZWFkKCIvVXNlcnMvQ0EvRG93bmxvYWRzL2FkdWx0LmNzdiIsIHN0cmluZ3NBc0ZhY3RvcnMgPSBGKQpoZWFkKGFkdWx0LCBuID0gMSkKYGBgCgpgYGB7cn0KIyBDcmVhdGUgVHJhaW5pbmcgRGF0YQppbnB1dF9vbmVzIDwtIGFkdWx0W3doaWNoKGFkdWx0JEFCT1ZFNTBLID09IDEpLCBdICAjIGFsbCAxJ3MKaW5wdXRfemVyb3MgPC0gYWR1bHRbd2hpY2goYWR1bHQkQUJPVkU1MEsgPT0gMCksIF0gICMgYWxsIDAncwoKc2V0LnNlZWQoMTAwKSAgCmlucHV0X29uZXNfdHJhaW5pbmdfcm93cyA8LSBzYW1wbGUoMTpucm93KGlucHV0X29uZXMpLCAwLjcqbnJvdyhpbnB1dF9vbmVzKSkgICMgMSdzIGZvciB0cmFpbmluZwppbnB1dF96ZXJvc190cmFpbmluZ19yb3dzIDwtIHNhbXBsZSgxOm5yb3coaW5wdXRfemVyb3MpLCAwLjcqbnJvdyhpbnB1dF9vbmVzKSkgICMgMCdzIGZvciB0cmFpbmluZy4gUGljayBhcyBtYW55IDAncyBhcyAxJ3MKdHJhaW5pbmdfb25lcyA8LSBpbnB1dF9vbmVzW2lucHV0X29uZXNfdHJhaW5pbmdfcm93cywgXSAgCnRyYWluaW5nX3plcm9zIDwtIGlucHV0X3plcm9zW2lucHV0X3plcm9zX3RyYWluaW5nX3Jvd3MsIF0KdHJhaW5pbmdEYXRhIDwtIHJiaW5kKHRyYWluaW5nX29uZXMsIHRyYWluaW5nX3plcm9zKSAgIyByb3cgYmluZCB0aGUgMSdzIGFuZCAwJ3MgCgojIENyZWF0ZSBUZXN0IERhdGEKdGVzdF9vbmVzIDwtIGlucHV0X29uZXNbLWlucHV0X29uZXNfdHJhaW5pbmdfcm93cywgXQp0ZXN0X3plcm9zIDwtIGlucHV0X3plcm9zWy1pbnB1dF96ZXJvc190cmFpbmluZ19yb3dzLCBdCnRlc3REYXRhIDwtIHJiaW5kKHRlc3Rfb25lcywgdGVzdF96ZXJvcykgICMgcm93IGJpbmQgdGhlIDEncyBhbmQgMCdzIApgYGAKCmBgYHtyfQpsaWJyYXJ5KHNtYmlubmluZykKIyBzZWdyZWdhdGUgY29udGludW91cyBhbmQgZmFjdG9yIHZhcmlhYmxlcwpmYWN0b3JfdmFycyA8LSBjICgiV09SS0NMQVNTIiwgIkVEVUNBVElPTiIsICJNQVJJVEFMU1RBVFVTIiwgIk9DQ1VQQVRJT04iLCAiUkVMQVRJT05TSElQIiwgIlJBQ0UiLCAiU0VYIiwgIk5BVElWRUNPVU5UUlkiKQpjb250aW51b3VzX3ZhcnMgPC0gYygiQUdFIiwgIkZOTFdHVCIsIkVEVUNBVElPTk5VTSIsICJIT1VSU1BFUldFRUsiLCAiQ0FQSVRBTEdBSU4iLCAiQ0FQSVRBTExPU1MiKQoKaXZfZGYgPC0gZGF0YS5mcmFtZShWQVJTPWMoZmFjdG9yX3ZhcnMsIGNvbnRpbnVvdXNfdmFycyksIElWPW51bWVyaWMoMTQpKSAgIyBpbml0IGZvciBJViByZXN1bHRzCgojIGNvbXB1dGUgSVYgZm9yIGNhdGVnb3JpY2Fscwpmb3IoZmFjdG9yX3ZhciBpbiBmYWN0b3JfdmFycyl7CiAgc21iIDwtIHNtYmlubmluZy5mYWN0b3IodHJhaW5pbmdEYXRhLCB5PSJBQk9WRTUwSyIsIHg9ZmFjdG9yX3ZhcikgICMgV09FIHRhYmxlCiAgaWYoY2xhc3Moc21iKSAhPSAiY2hhcmFjdGVyIil7IAogICAgaXZfZGZbaXZfZGYkVkFSUyA9PSBmYWN0b3JfdmFyLCAiSVYiXSA8LSBzbWIkaXYKICB9Cn0KCiMgY29tcHV0ZSBJViBmb3IgY29udGludW91cyB2YXJzCmZvcihjb250aW51b3VzX3ZhciBpbiBjb250aW51b3VzX3ZhcnMpewogIHNtYiA8LSBzbWJpbm5pbmcodHJhaW5pbmdEYXRhLCB5PSJBQk9WRTUwSyIsIHg9Y29udGludW91c192YXIpICAjIFdPRSB0YWJsZQogIGlmKGNsYXNzKHNtYikgIT0gImNoYXJhY3RlciIpeyAgIyBhbnkgZXJyb3Igd2hpbGUgY2FsY3VsYXRpbmcgc2NvcmVzLgogICAgaXZfZGZbaXZfZGYkVkFSUyA9PSBjb250aW51b3VzX3ZhciwgIklWIl0gPC0gc21iJGl2CiAgfQp9Cgppdl9kZiA8LSBpdl9kZltvcmRlcigtaXZfZGYkSVYpLCBdICAjIHNvcnQKaXZfZGYKYGBgCgpgYGB7cn0KIyBDaGVjayBSYW5kb20gY29tcG9uZW50IDogQmlub21pYWwgRGlzdHJpYnV0aW9uICggWSApICwgU3VjY2VzcygxKSBvciBGYWlsKDApID0+IEJpbm9taWFsICsgTG9naXQgZnVuY3Rpb24gCnRhYmxlKHRyYWluaW5nRGF0YSRBQk9WRTUwSykKCiMgMCDqs7wgMSDrp4wg6rCW64qUIOu2hO2PrOuKlCB0cmFuc2Zvcm1hdGlvbuydhCDtlZjrjZTrnbzrj4QsIG5vbWFsIGRpc3RyaWJ1dGlvbiDsnZgg66qo7JaR7J2EIOqwgOyniCDsiJgg7JeG64ukLiAKcGxvdChkZW5zaXR5KGFkdWx0JEFCT1ZFNTBLKSkKYGBgCgpgYGB7cn0KIyBiaW5vbWlhbCBkaXN0cmlidXRpb24g7J2YIGxpbmsgZnVuY3Rpb24g7Jy866GcLCBnbG0oKSDsl5DshJzripQgbG9naXQgLiBwcm9iaXQgLiBjb3VjaGl0IOydhCDsgqzsmqntlaAg7IiYIOyeiOuLpC4gCmBgYAohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9pdC5wbmcpCgpgYGB7cn0KbW9kZWwgPC0gZ2xtKEFCT1ZFNTBLIH4gIEFHRSArIENBUElUQUxHQUlOICsgRURVQ0FUSU9OTlVNICsgSE9VUlNQRVJXRUVLICsgQ0FQSVRBTExPU1MsIGRhdGE9dHJhaW5pbmdEYXRhLCBmYW1pbHk9Ymlub21pYWwobGluaz0ibG9naXQiKSkKCnRlc3REYXRhJHByZWRpY3RlZCA8LSBwcmVkaWN0KG1vZGVsLCB0ZXN0RGF0YSwgdHlwZT0icmVzcG9uc2UiKSAgIyBwcmVkaWN0ZWQgc2NvcmVzCgpzdW1tYXJ5KG1vZGVsKQoKIyBjaGVjayBtdWx0aWNvbGxpbmVhcml0eSAoIOuLpOykkeqzteyEoOyEsSApIOuPheumveuzgOyImOuTpOqwhOyXkCDrhpLsnYAg7ISg7ZiV6rSA6rOE6rCAIOyhtOyerO2VmOuptCAoIOuLpOykkeqzteyEoOyEseydtCDsobTsnqztlZjrqbQgKSDtmozqt4DrtoTshJ0g7KCE7KCcIOqwgOyglSDsnITrsLAKbGlicmFyeShjYXIpCnNxcnQodmlmKG1vZGVsKSkgPiAyIApgYGAKIVtdKC9Vc2Vycy9DQS9Eb3dubG9hZHMvY29saS5wbmcpCmBgYHtyfQojIGZlYXR1cmUg65Ok7J2YIOyDgeuMgOyggeyduCDspJHsmpTrj4QgKCBmZWF0dXJlIOulvCDstpTqsIDtlojsnYTrlYwg7Y+J6reg7KCB7J2AIFIyIOydmCDspp3qsIDrpbwg67O064qUIOqygyApCnJlbHdlaWdodHMgPC0gZnVuY3Rpb24oZml0LC4uLil7CiAgICAgICAgIFIgPC0gY29yKGZpdCRtb2RlbCkKICAgICAgICAgbnZhciA8LSBuY29sKFIpCiAgICAgICAgIHJ4eCA8LSBSWzI6bnZhciwgMjpudmFyXQogICAgICAgICByeHkgPC0gUlsyOm52YXIsIDFdCiAgICAgICAgIHN2ZCA8LSBlaWdlbihyeHgpCiAgICAgICAgIGV2ZWMgPC0gc3ZkJHZlY3RvcnMKICAgICAgICAgZXYgPC0gc3ZkJHZhbHVlcwogICAgICAgICBkZWx0YSA8LSBkaWFnKHNxcnQoZXYpKQogICAgICAgICBsYW1iZGEgPC0gZXZlYyAlKiUgZGVsdGEgJSolIHQoZXZlYykKICAgICAgICAgbGFtYmRhc3EgPC0gbGFtYmRhIF4gMgogICAgICAgICBiZXRhIDwtIHNvbHZlKGxhbWJkYSkgJSolIHJ4eQogICAgICAgICByc3F1YXJlIDwtIGNvbFN1bXMoYmV0YSBeIDIpCiAgICAgICAgIHJhd3dndCA8LSBsYW1iZGFzcSAlKiUgYmV0YSBeIDIKICAgICAgICAgaW1wb3J0IDwtIChyYXd3Z3QgLyByc3F1YXJlKSAqIDEwMAogICAgICAgICBpbXBvcnQgPC0gYXMuZGF0YS5mcmFtZShpbXBvcnQpCiAgICAgICAgIHJvdy5uYW1lcyhpbXBvcnQpIDwtIG5hbWVzKGZpdCRtb2RlbFsyOm52YXJdKQogICAgICAgICBuYW1lcyhpbXBvcnQpIDwtICJXZWlnaHRzIgogICAgICAgICBpbXBvcnQgPC0gaW1wb3J0W29yZGVyKGltcG9ydCksMSwgZHJvcD1GQUxTRV0KICAgICAgICAgZG90Y2hhcnQoaW1wb3J0JFdlaWdodHMsIGxhYmVscz1yb3cubmFtZXMoaW1wb3J0KSwKICAgICAgICAgICAgeGxhYj0iJSBvZiBSLVNxdWFyZSIsIHBjaD0xOSwKICAgICAgICAgICAgbWFpbj0iUmVsYXRpdmUgSW1wb3J0YW5jZSBvZiBQcmVkaWN0b3IgVmFyaWFibGVzIiwKICAgICAgICAgICAgc3ViPXBhc3RlKCJUb3RhbCBSLVNxdWFyZT0iLCByb3VuZChyc3F1YXJlLCBkaWdpdHM9MykpLAogICAgICAgICAgICAuLi4pCiAgICAgICAgIHJldHVybihpbXBvcnQpCn0KCnJlbHdlaWdodHMobW9kZWwpCmBgYAoKYGBge3J9CmxpYnJhcnkoSW5mb3JtYXRpb25WYWx1ZSkKdGhyZXNob2xkIDwtIG9wdGltYWxDdXRvZmYodGVzdERhdGEkQUJPVkU1MEssIHRlc3REYXRhJHByZWRpY3RlZCkKbWlzQ2xhc3NFcnJvcih0ZXN0RGF0YSRBQk9WRTUwSywgdGVzdERhdGEkcHJlZGljdGVkLCB0aHJlc2hvbGQgPSB0aHJlc2hvbGQpCnBsb3RST0ModGVzdERhdGEkQUJPVkU1MEssIHRlc3REYXRhJHByZWRpY3RlZCkKYGBgCgpgYGB7cn0KIyBsaW5lYXIgcmVncmVzc2lvbiDsnZgg6rCA7KCV7J2EIOqygOyCrO2VmOq4sCDsnITtlZwg7JWE656YIHBsb3Qg65Ok7J2ALCDri7nsl7DtlZjqsozrj4Qg66qo65GQIOychOuwsOuQmOuKlCDqsrDqs7zrpbwg67O07J2464ukLiAKCnBhcihtZnJvdyA9IGMoMiwyKSkKcGxvdChtb2RlbCkKYGBgCgoKYGBge3J9CiMgbW9kZWwg67mE6rWQIAptb2RlbC4xIDwtIG1vZGVsIDwtIGdsbShBQk9WRTUwSyB+ICAxLCBkYXRhPXRyYWluaW5nRGF0YSwgZmFtaWx5PWJpbm9taWFsKGxpbms9ImxvZ2l0IikpCm1vZGVsLjIgPC0gbW9kZWwgPC0gZ2xtKEFCT1ZFNTBLIH4gIEFHRSwgZGF0YT10cmFpbmluZ0RhdGEsIGZhbWlseT1iaW5vbWlhbChsaW5rPSJsb2dpdCIpKQptb2RlbC4zIDwtIG1vZGVsIDwtIGdsbShBQk9WRTUwSyB+ICBBR0UgKyBDQVBJVEFMR0FJTiwgZGF0YT10cmFpbmluZ0RhdGEsIGZhbWlseT1iaW5vbWlhbChsaW5rPSJsb2dpdCIpKQoKbGlicmFyeShyY29tcGFuaW9uKQoKY29tcGFyZUdMTShtb2RlbC4xLCBtb2RlbC4yLCBtb2RlbC4zKQphbm92YShtb2RlbC4xLCBtb2RlbC4yLCBtb2RlbC4zKQpgYGAKCmBgYHtyfQojIOy1nOyEoOydmCDrqqjrjbjsnYQg6rOg66W064qUIOuwqeuylSDspJHsl5AsIOyVnuyEoCDrqqjrjbggZXZhbHVhdGlvbiDqs7wg7ZWo6ruYIOuqh+qwgOyngCDthrXqs4Trn4nsnYQg6riw7KSA7Jy866GcIOyEoO2Dne2VmOuKlCDrsKnrspXrj4Qg7J6I64ukLiAKIyDsnITsnZggY29tcGFyZUdMTSBmdW5jdGlvbiDsnZgg6rKw6rO866W8IOuztOuptCBBSUMgLyBCSUMg65Ox7J2YIO2GteqzhOufieydtCDrgpjsmKTripTrjbAsIOydtOyXkCDrjIDtlZwg64K07Jqp7J2EIOyCtO2OtOuztOyekCAKIwojIEFJQyhBa2Fpa2XigJlzIEFuIEluZm9ybWF0aW9uIENyaXRlcmlvbikKIyMg66qo7ZiV7J2YIO2GteqzhOyggSDsoIHtlanshLEg67CPIO2GteqzhCDsoIHtlansl5Ag7ZWE7JqU7ZWcIOyduOyImOydmCDsiJjrpbwg7ISk66qFICggPyApCiMjIEFJQyDqsJLsnbQg7KCB7J2AIOuqqO2YlSwg7KaJIOyggeydgCDsnbjsiJjrpbwg6rCA7KeA6rOgIOyggeygiO2VnCDsoIHtlanshLHsnYQg67O07J2064qUIOuqqO2YleydtCDshKDtmLggKCBBSUMg6rCS7J2AIOyggeycvOuptCDsoovri6QuIEFJQyDqsJLsnYAg7J2M7IiY64+EIOqwgOuKpe2VmOuLpC4gKQojIyBBSUMgLyBCSUMgZnVuY3Rpb24g7J2YIGRvYyDsnYQg7IK07Y6067O066m0LCDslYTrnpjsmYAg6rCZ64ukLiAKIyMgV2hlbiBjb21wYXJpbmcgbW9kZWxzIGZpdHRlZCBieSBtYXhpbXVtIGxpa2VsaWhvb2QgdG8gdGhlIHNhbWUgZGF0YSwgdGhlIHNtYWxsZXIgdGhlIEFJQyBvciBCSUMsIHRoZSBiZXR0ZXIgdGhlIGZpdC4KCkFJQyhtb2RlbC4xLCBtb2RlbC4yLCBtb2RlbC4zKQpgYGAKCmBgYHtyfQojIOychCDsmIjsl5DshJzripQgbW9kZWwuMyDsnZggQUlDIOqwkuydtCDsoJzsnbwg7J6R6rKMIOuCmOyZlOycvOuvgOuhnCwgQUlDIOq4sOykgOycvOuhnOuKlCBtb2RlbC4zIOydtCDsoJzsnbwg7KCB7KCI7ZWcIOuqqOuNuOydtOudvOqzoCDtjJDri6jtlZzri6QuIAojIOydtOuVjCwgaW5kZXBlbmRlbnQgdmFyLiDrpbwg7J6Q64+Z7Jy866GcIOy2lOqwgO2VtOqwgOuptOyEnCDsl6zrn6wg66qo64247J2EIOyJveqyjCDruYTqtZDtlbQg67O8IOyImCDrj4Qg7J6I64qU642wLCBzdGVwIO2VqOyImOulvCDsgqzsmqntlZjrqbQg65Cc64ukLiAKIyBzdGVwIO2VqOyImOuKlCBiYWNrd2FyZCAoIGZlYXR1cmUg66W8IOu5vOqwgOuptOyEnCwgKSAsIGZvcndhcmQgKCDsp4DsoJXrkJwgZmVhdHVyZSDrk6TsnYQg7ZWY64KY7JSpIOy2lOqwgO2VmOuptOyEnCApIOy1nOyGjCBBSUMg6rCS7J2EIOywvuuKlOuLpC4gIApzdXBlci5tb2RlbCA9IGdsbShBQk9WRTUwSyB+IDEgLCBkYXRhID0gdHJhaW5pbmdEYXRhKQpzdWIubW9kZWwgPSBzdGVwKHN1cGVyLm1vZGVsLCAKICAgICAgICAgICAgICAgICBkaXJlY3Rpb24gPSAiZm9yd2FyZCIsIAogICAgICAgICAgICAgICAgIHNjb3BlID0gKEFCT1ZFNTBLIH5BR0UgKyBDQVBJVEFMR0FJTiArIEVEVUNBVElPTk5VTSArIEhPVVJTUEVSV0VFSyArIENBUElUQUxMT1NTKSwKICAgICAgICAgICAgICAgICB0cmFjZSA9IDApCgpzdW1tYXJ5KHN1Yi5tb2RlbCkKYGBgCgpgYGB7cn0KIyDstpTqsIDsoIHsnLzroZwgZHVtbXkgY29kaW5nIOydtCDsoIHsmqnrkJjsl4jsnYzsnYQg67O8IOyImCDsnojri6QuIAojIOyVhOuemCDqsrDqs7zripQgc21iaW5uaW5nIOydhCDthrXtlbQgZmVhdHVyZSDrpbwgc2VsZWN0aW9uIO2VnCDqsrDqs7zsmYDripQg64uk7IaMIOywqOydtOqwgCDsnojripTrjbAsIHNlbGVjdGlvbiDsnZgg6riw7KSA7J20IOuLpOuluCDqsoPsnbTsp4Ag7Ja064qQ6rKMIOunnuqzoCDti4Drpqzqs6DsnZgg66y47KCc64qUIOyVhOuLiOuLpC4gCiMgKCBTdGVwd2lzZSByZWdyZXNzaW9u7J2AIOuFvOuegOydmCDsl6zsp4DqsIAg7J6I64ukLiDsnbQg67Cp67KV7J2EIO2Gte2VtOyEnCDsoovsnYAg66qo7ZiV7J2EIOywvuydhCDsiJjripQg7J6I7KeA66eMIOy1nOyEoOydmCDrqqjtmJXsnbTrnbzripQg67O07J6l7J2AIOyXhuuLpOqzoCDtlZzri6QuICkKc3VwZXIubW9kZWwgPSBnbG0oQUJPVkU1MEsgfiAuICwgZGF0YSA9IHRyYWluaW5nRGF0YSkKc3ViLm1vZGVsID0gc3RlcChzdXBlci5tb2RlbCwgCiAgICAgICAgICAgICAgICAgZGlyZWN0aW9uID0gImJhY2t3YXJkIiwgCiAgICAgICAgICAgICAgICAgdHJhY2UgPSAwKQoKc3VtbWFyeShzdWIubW9kZWwpCmBgYAoKYGBge3J9CiMgc3RlcHdpc2UgcmVncmVzc2lvbiDsnYAg6rCA64ql7ZWcIOuqqOuToCDsobDtlansnYQg7YOQ7IOJ7ZWY7KeA64qUIOyViuyngOunjCwgCiMgYWxsIHN1YnNldHMgcmVncmVzc2lvbiDsnYAg6rCA64ql7ZWcIOuqqOuToCDsobDtlansnYQg7YOQ7IOJ7ZWY7JesLCDqsIEg7JiI7Lih7J247J6Q67OE66GcIGJlc3QgbiDqsJwgKCBuYmVzdCApIOulvCDtkZzsi5ztlZzri6QuIAojIO2VmOyngOunjCDsnbQg67Cp67KV7J2AIGZlYXR1cmUgc2V0IOydmCDtgazquLDsl5Ag65Sw6528LCDsiJjtlonsi5zqsITsnbQg66ek7JqwIOq4uOyWtOyngOuKlCDri6jsoJDsnbQg7J6I64ukLiAoIHJlYWxseS5iaWcgYXJndW1lbnQg44Wc44WcKQojIGFsbF9zdWJzZXRfcmVncmVzc2lvbiA8LSByZWdzdWJzZXRzKEFCT1ZFNTBLIH4gLiwgZGF0YSA9IHRyYWluaW5nRGF0YSwgbmJlc3QgPSAyLCByZWFsbHkuYmlnID0gVCkKbGlicmFyeShsZWFwcykKCmFsbF9zdWJzZXRfcmVncmVzc2lvbiA8LSByZWdzdWJzZXRzKAogIEFCT1ZFNTBLIH4gQUdFICsgV09SS0NMQVNTICsgRURVQ0FUSU9OICsgT0NDVVBBVElPTiArIFJFTEFUSU9OU0hJUCArIFNFWCArIENBUElUQUxHQUlOICsgQ0FQSVRBTExPU1MsIAogIGRhdGEgPSB0cmFpbmluZ0RhdGEsIAogIG5iZXN0ID0gMgopCnBsb3QoYWxsX3N1YnNldF9yZWdyZXNzaW9uLCBzY2FsZSA9ICJhZGpyMiIpICMgc2NhbGUgPSBbcnNxfHJzc3xhZGpyMnxjcHxiaWN8b3V0bWF0XQpgYGAKCmBgYHtyfQojIOychCBwbG90IOydmCDqsIEg7ZaJ7J2YIOyDieq5lOydtCDsuaDtlbTsp4Qg6rKD7J20IGZlYXR1cmUg7J2YIOqwr+yImOydtOuLpC4gCiMg7JyE7JeQ7IScIG5iZXN0ID0gMiDrpbwg7KO87JeI7Jy866+A66GcLCAy6rCc6rCAIOyDiey5oOuQnCDqsoPsnbQg7JWE656Y67aA7YSwIDLqsJzsnbTqs6AsIAojIOq3uOychOyXkOuKlCAz6rCc6rCAIOyDiey5oOuQnCDqsoPsnbQgM+qwnOydtOqzoCDsnbTrn7Dsi53snbTri6QuIOydtCDqsr3smrAsIGFkanIyIOulvCDquLDspIDsnLzroZwgYmVzdCDrpbwg7LC+7J2AIOqyg+ydtOuLiCAxIOyXkCDqsIDquYzsmrQg66qo64247J20IOy1nOyggeydtOuLpC4gCmBgYAoKCiMjIE11bHRpbm9taWFsIFJlZ3Jlc3Npb24KCmBgYHtyfQojIHJlZiA6IGh0dHBzOi8vb25saW5lY291cnNlcy5zY2llbmNlLnBzdS5lZHUvc3RhdDUwNC9ub2RlLzQwCiMgcmVmIDogaHR0cDovL3Itc3RhdGlzdGljcy5jby9NdWx0aW5vbWlhbC1SZWdyZXNzaW9uLVdpdGgtUi5odG1sCiMgCiMxLiBSYW5kb20gY29tcG9uZW50IDogTXVsdGlub21pYWwgRGlzdHJpYnV0aW9uICggWSAsIG11bHRpIGxldmVscyApCiMyLiBTeXN0ZW1hdGljIGNvbXBvbmVudCA6IEV4cGxhbmF0b3J5IHZhci4gKCBjYW4gYmUgY29udGludW91cyAvIGRpc2NyZXQgfCBYcyApCiMzLiBMaW5rIGZ1bmN0aW9uIDogR2VuZXJhbGl6ZWQgTG9naXQKYGBgCgpgYGB7cn0KY21jRGF0YSA8LSByZWFkLmNzdigiaHR0cDovL2FyY2hpdmUuaWNzLnVjaS5lZHUvbWwvbWFjaGluZS1sZWFybmluZy1kYXRhYmFzZXMvY21jL2NtYy5kYXRhIiwgc3RyaW5nc0FzRmFjdG9ycz1GQUxTRSwgaGVhZGVyPUYpCmNvbG5hbWVzKGNtY0RhdGEpIDwtIGMoIndpZmVfYWdlIiwgIndpZmVfZWR1IiwgImh1c19lZHUiLCAibnVtX2NoaWxkIiwgIndpZmVfcmVsIiwgIndpZmVfd29yayIsICJodXNfb2NjdSIsICJzaWwiLCAibWVkaWFfZXhwIiwgImNtYyIpCmhlYWQoY21jRGF0YSwgbiA9IDEpCgpsZXZlbHMoYXMuZmFjdG9yKGNtY0RhdGEkY21jKSkKY21jRGF0YSA8LSB0cmFuc2Zvcm0oY21jRGF0YSwgY21jIDwtIGFzLmZhY3RvcihjbWMpKQpgYGAKCmBgYHtyfQojIHJhbmRvbSBjb21wb25lbnQg7J2YIGRpc3RyaWJ1dGlvbiDsnZggdHlwZSDqs7wg6re47JeQIOuUsOuluCBsaW5rIGZ1bmN0aW9uIOydtCDri6zrnbzsp4Qg6rKDIOydtOyZuOyXkOuKlCAKIyDtgbAg7LCo7J206rCAIOyXhuyWtCDstpTqsIDsoIHsnbgg7ISk66qF7JeG7J20LCBubmV0IHBhY2thZ2Ug7J2YIG11bHRpbm9tIGZ1bmN0aW9uIOydhCDthrXtlZwgcHJlZGljdGlvbiDquYzsp4Drp4wg7IiY7ZaJ7ZWc64ukLiAKIyBzdW1tYXJ5IOqysOqzvOulvCDrs7TrqbQsIOqwgSBsZXZlbCDrs4QgY29lZmZpY2llbnQg6rCS7J20IGVzdGltYXRpb24g65Co7J2EIOyVjCDsiJgg7J6I64ukLiAKbGlicmFyeShubmV0KQoKbW9kZWwgPC0gbXVsdGlub20oY21jIH4gLiAsIGRhdGEgPSBjbWNEYXRhKQpzdW1tYXJ5KG1vZGVsKQpjbWNEYXRhJHByZWQgPC0gcHJlZGljdChtb2RlbCwgY21jRGF0YSkKY21jRGF0YSA8LSBjYmluZChjbWNEYXRhLCBhcy5kYXRhLmZyYW1lKHByZWRpY3QobW9kZWwsIGNtY0RhdGEsIHR5cGUgPSAicHJvYiIpKSkKCnRhYmxlKGNtY0RhdGEkcHJlZCwgY21jRGF0YSRjbWMpCmBgYAoKCmBgYHtyfQojIHByZWRpY3Qg7J2YIHR5cGUg7Jy866GcIHByb2Ig7J2EIOyngOygle2VmOuKlCDqsr3smrAsIOqwgSBsZXZlbCDsnbQg65CgIO2ZleuloOqwkuydhCBtYXRyaXgg66GcIOuwmO2ZmO2VmOqyjCDrkJzri6QuIApoZWFkKGNtY0RhdGFbYygiY21jIiwgInByZWQiLCAiMSIsICIyIiwgIjMiKV0pCmBgYAoKYGBge3J9CiMgdmdsbSBwYWNrYWdlIOulvCDsgqzsmqntlZjrqbQsIG1vZGVsIHN1bW1hcnkg66GcIHNpZ25pZmljYW5jZSDqsJLsnYQg7JWMIOyImCDsnojri6QuIApjbWNEYXRhIDwtIHJlYWQuY3N2KCJodHRwOi8vYXJjaGl2ZS5pY3MudWNpLmVkdS9tbC9tYWNoaW5lLWxlYXJuaW5nLWRhdGFiYXNlcy9jbWMvY21jLmRhdGEiLCBzdHJpbmdzQXNGYWN0b3JzPUZBTFNFLCBoZWFkZXI9RikKY29sbmFtZXMoY21jRGF0YSkgPC0gYygid2lmZV9hZ2UiLCAid2lmZV9lZHUiLCAiaHVzX2VkdSIsICJudW1fY2hpbGQiLCAid2lmZV9yZWwiLCAid2lmZV93b3JrIiwgImh1c19vY2N1IiwgInNpbCIsICJtZWRpYV9leHAiLCAiY21jIikKCmxpYnJhcnkoVkdBTSkKbW9kZWwgPC0gdmdsbShjbWMgfiAuICwgZmFtaWx5ID0gbXVsdGlub21pYWwocmVmTGV2ZWwgPSAxKSwgZGF0YSA9IGNtY0RhdGEpCgpleHAoY29lZihtb2RlbCkpCnN1bW1hcnkobW9kZWwpCmBgYAoKYGBge3J9CiMgbWxvZ2l0IHBhY2thZ2Ug66W8IOyCrOyaqe2VtOuzvCDsiJjrj4Qg7J6I64ukLiAKIyBodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvbWxvZ2l0L3ZpZ25ldHRlcy9tbG9naXQucGRmCmBgYAoKCiMjIFBvaXNzb24gUmVncmVzc2lvbiAKYGBge3J9CiMgcmVmIDogaHR0cHM6Ly9vbmxpbmVjb3Vyc2VzLnNjaWVuY2UucHN1LmVkdS9zdGF0NTA0L25vZGUvMTY1CiMgcmVmIDogaHR0cDovL3dpa2kuc3RhdC51Y2xhLmVkdS9zb2NyL2luZGV4LnBocC9BUF9TdGF0aXN0aWNzX0N1cnJpY3VsdW1fMjAwN19EaXN0cmliX1BvaXNzb24KIyByZWYgOiBodHRwOi8vZGF0YS5wcmluY2V0b24uZWR1L3d3czUwOS9SL2M0czEuaHRtbAojIHJlZiA6IGh0dHBzOi8vc3RhdHMuaWRyZS51Y2xhLmVkdS9yL2RhZS9wb2lzc29uLXJlZ3Jlc3Npb24vCiMgcmVmIDogaHR0cDovL3ItYm9uZy5ibG9nc3BvdC5rci8yMDE2LzExL2Jsb2ctcG9zdC5odG1sCiMgcmVmIDogaHR0cDovL3d3dy5zdGF0Z3JvdW5kLm9yZy8/bW9kdWxlPWZpbGUmYWN0PXByb2NGaWxlRG93bmxvYWQmZmlsZV9zcmw9MTc5MyZzaWQ9M2M3ZjJkMWQxZDJjMTU0M2E5N2NmMGY2MTQ0YTVlOTAmbW9kdWxlX3NybD0xMzcKIwojMS4gUmFuZG9tIGNvbXBvbmVudCA6IFBvaXNzb24sIFF1YXNpUG9pc3NvbiBEaXN0cmlidXRpb24gKCBZICkKIzIuIFN5c3RlbWF0aWMgY29tcG9uZW50IDogRXhwbGFuYXRvcnkgdmFyLiAoIGNhbiBiZSBjb250aW51b3VzIC8gZGlzY3JldCB8IFhzICkKIzMuIExpbmsgZnVuY3Rpb24gOiBMb2cgLCBJZGVudGl0eQojCiMg7Ju57ISc67mE7Iqk66W8IOygnOqzte2VmOuptOyEnCwgUG9pc3NvbiBEaXN0cmlidXRpb24g7J2EIOqyquydhCDsiJgg7J6I64qUIOy8gOydtOyKpCAKIyBPMk8g67Cw64us7KO866y4LCDsvZwg7Zi47LacIAojIOq3uOyZuCDqsIHsooUgY291bnQg66WY7J2YIOuNsOydtO2EsOuTpCAoIOyCrOydtOuyhOuztOuLpOuKlCDtmITsi6Tqs7wg6rCA6rmM7Jq4IOyImOuhnSApCmBgYAohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9yZWdyZXNzaW9ucy5wbmcpCgpgYGB7cn0KIyBQb2lzc29uIERpc3RyaWJ1dGlvbgojIERpc2NyZXQgUHJvYi4gRGlzdHJpYnV0aW9uID4gQmlub21pYWwgRGlzdHJpYnV0aW9uICwgUG9pc3NvbiBEaXN0cmlidXRpb24gCmBgYAoKYGBge3J9CiMg7Iuk7ISc67mE7Iqk7J2YIOuNsOydtO2EsOulvCDsgqzsmqntlZjrqbQg7KCc7J28IOyii+yngOunjCwgcnB1YnMg7JeQIOqyjOyLnO2VmOq4sOuhnCDtlojsnLzrr4DroZwKIyBodHRwOi8vZGF0YS5wcmluY2V0b24uZWR1L3d3czUwOS9kYXRhc2V0cy8jY2ViIOulvCDsgqzsmqntlZzri6QuCiMKbGlicmFyeShmb3JlaWduKQpkYXRhIDwtIHJlYWQuZHRhKCJodHRwOi8vZGF0YS5wcmluY2V0b24uZWR1L3d3czUwOS9kYXRhc2V0cy9jZWIuZHRhIikKCmxpYnJhcnkoZHBseXIpCmdsaW1wc2UoZGF0YSkKYGBgCgpgYGB7cn0KcGFyKG1mcm93ID0gYygzLDIpKQpwbG90KGRlbnNpdHkoZGF0YSRuKSkKcGxvdChkZW5zaXR5KGRhdGEkbWVhbikpCmNhcjo6cXFQbG90KGRhdGEkbikKCiMgQ2xlYXJseSB0aGUgdmFyaWFuY2UgaW5jcmVhc2VzIHdpdGggdGhlIG1lYW4uCnVwcGVyXzIwIDwtIHN1YnNldChkYXRhLCBuID49IDIwKQpwbG90KGxvZyh1cHBlcl8yMCRtZWFuKSwgbG9nKHVwcGVyXzIwJHZhcikpCmFibGluZSgwLDEpCgojIGRlcGVuZGVudCB2YXJpYWJsZSA6IHkgPSBtZWFuIG51bWJlciBvZiBjaGlsZHJlbiBldmVyIGJvcm4gKiBudW1iZXIgb2Ygd29tZW4gaW4gdGhlIGNlbGwgCmRhdGEkeSA8LSByb3VuZChkYXRhJG1lYW4gKiBkYXRhJG4sIDApCgpwbG90KGRlbnNpdHkoZGF0YSR5KSkKcGxvdChkYXRhJG4sIGRhdGEkeSkKYGBgCgpgYGB7cn0KCgojIElmIHRoZSBudW1iZXIgb2YgQ0VCIHRvIG9uZSB3b21hbiBpbiBhIGdpdmVuIGNlbGwgaXMgYSBQb2lzc29uIHJhbmRvbSB2YXJpYWJsZSB3aXRoIG1lYW4gKGFuZCB2YXJpYW5jZSkgzrwsIAojIHRoZW4gdGhlIG51bWJlciBib3JuIHRvIGFsbCBuIHdvbWVuIGluIHRoYXQgY2VsbCBpcyBhIFBvaXNzb24gci52LiB3aXRoIG1lYW4gKGFuZCB2YXJpYW5jZSkgbs68LiAKIyBUaGUgbG9nIG9mIHRoZSBleHBlY3RlZCBzdW0gaXMgbG9nKG4pK2xvZyjOvCksIGFuZCBjb25zaXN0cyBvZiBhIGtub3duIG9mZnNldCBhbmQgdGhlIHF1YW50aXR5IHdlIGFyZSBpbnRlcmVzdGVkIGluIG1vZGVsaW5nLiAKIwojIDEuIG51bWJlciBvZiB3b21lbiBpbiB0aGUgY2VsbCDsl5Ag67mE66GA7ZWY7JesIOy7pOyniCDqsr3tlqXsnbQg7J6I7J2EIOqyg+ydtOuvgOuhnAojICAgIFkgfiBwb2lzc29uKM68KSwg7Y+J6regIM68IOyduCDtj6zslYTshqHrtoTtj6zrpbwg65Sw66W064qUIOuqqOuNuOydhCDsgqzsmqntlZzri6QuICggWSDripQgZGlzY3JldGUgdmFyaWFibGUgKQojCiMgMi4gbG4ozrwpID0gbG4obikgKyDsoIjtjrggKyB4MSArIHgyIC4uLiAvLyDsnbQg7KSRIOyyq+2VreydhCDsmrDrpqzripQgb2Zmc2V0IOydtOudvOqzoCDtlZjrqbAsIOydtOqyg+ydtCBwb2lzc29uIGxpbmsgZnVuY3Rpb24g7J2064ukLiAoIGxvZy1saW5lYXIgbW9kZWwgKQojICAgIG9mZnNldCDsnZggY29lZmZpY2llbnQg6rCS7J2EIOq1rO2VmOuptCDslYTrnpjsmYAg6rCZ6rOgLCDqt7gg6rCS7J2AIOyghOyytCDstpzsg53slYQg7IiYIOulvCDsoITssrQg7Jes7ISx7IiY66GcIOuCmOuIiCDqsJLqs7wg6rCZ64ukLiDug7cKCmRhdGEkb3MgPC0gbG9nKGRhdGEkbikgCgptb2RlbC4wIDwtIGdsbSggeSB+IDEsIG9mZnNldCA9IG9zLCBkYXRhID0gZGF0YSwgZmFtaWx5ID0gcG9pc3NvbikKc3VtbWFyeShtb2RlbC4wKQpwYXN0ZSgiZXhwKGNvZWYobW9kZWwuMCkpIDogIiwgZXhwKGNvZWYobW9kZWwuMCkpLCAgIiA9PSBzdW0oZGF0YSR5KS9zdW0oZGF0YSRuKSA6ICIsIHN1bShkYXRhJHkpL3N1bShkYXRhJG4pKQpgYGAKCmBgYHtyfQptb2RlbC5yZXMgPC0gZ2xtKCB5IH4gcmVzLCBvZmZzZXQgPSBvcywgZGF0YSA9IGRhdGEsIGZhbWlseSA9IHBvaXNzb24pCnN1bW1hcnkobW9kZWwucmVzKQpleHAoY29lZihtb2RlbC5yZXMpKQpjKGRldmlhbmNlKG1vZGVsLjApLWRldmlhbmNlKG1vZGVsLnJlcyksIGRldmlhbmNlKG1vZGVsLnJlcykpCmBgYAoKYGBge3J9CmFsbF9zdWJzZXRfcmVncmVzc2lvbiA8LSByZWdzdWJzZXRzKAogIHkgfiBvZmZzZXQob3MpICsgZHVyICsgcmVzICsgZWR1YywgCiAgZGF0YSA9IGRhdGEsIAogIG5iZXN0ID0gMgopCnBsb3QoYWxsX3N1YnNldF9yZWdyZXNzaW9uLCBzY2FsZSA9ICJiaWMiKSAjIHNjYWxlID0gW3JzcXxyc3N8YWRqcjJ8Y3B8YmljfG91dG1hdF0KYGBgCgpgYGB7cn0KbW9kZWwuYWxsIDwtIGdsbSggeSB+IGR1ciArIHJlcyArIGVkdWMsIG9mZnNldCA9IG9zLCBkYXRhID0gZGF0YSwgZmFtaWx5ID0gcG9pc3NvbikKCnN1bW1hcnkobW9kZWwuYWxsKQpleHAoY29lZihtb2RlbC5hbGwpKQpjKGRldmlhbmNlKG1vZGVsLjApLWRldmlhbmNlKG1vZGVsLmFsbCksIGRldmlhbmNlKG1vZGVsLmFsbCkpCmBgYAoKYGBge3J9CmR1cl9jb3VudCA8LSB0KGRhdGEgJT4lIGRwbHlyOjpncm91cF9ieShkdXIpICU+JSBzdW1tYXJpc2UobWVhbiA9IHN1bShtZWFuKSAvIG4oKSkpCnJlc19jb3VudCA8LSB0KGRhdGEgJT4lIGRwbHlyOjpncm91cF9ieShyZXMpICU+JSBzdW1tYXJpc2UobWVhbiA9IHN1bShtZWFuKSAvIG4oKSkpCgpjb3VudCA8LSBjYmluZChkdXJfY291bnQsIHJlc19jb3VudCkKY29sbmFtZXMoY291bnQpIDwtIGFzLmNoYXJhY3Rlcih1bmxpc3QoY291bnRbMSwgXSkpCmNvdW50W3Jvd25hbWVzKGNvdW50KSA9PSAibWVhbiIsIF0KYGBgCgpgYGB7cn0KbW9kZWxzIDwtIGMoImR1cityZXMqZWR1YyIsImR1cipyZXMrZWR1YyIsImR1ciplZHVjK3JlcyIsCiAgICAgICAgICAgICAiKGR1cityZXMpKmVkdWMiLCIoZHVyK2VkdWMpKnJlcyIsImR1cioocmVzK2VkdWMpIiwKICAgICAgICAgICAgICJkdXIqcmVzKmVkdWMgLSBkdXI6cmVzOmVkdWMiKQoKZGQgPC0gbWF0cml4KDAsIGxlbmd0aChtb2RlbHMpLCAyKQoKaSA8LSAxCmZvcihtb2RlbCBpbiBtb2RlbHMpIHsKICAgZm9ybXVsYSA8LSBwYXN0ZSgieSB+IG9mZnNldChvcykgKyAiLG1vZGVsKQogICBtIDwtIGdsbShmb3JtdWxhLCBmYW1pbHk9cG9pc3NvbiwgZGF0YT1kYXRhKQogICBkZFtpLF0gPC0gYyhkZXZpYW5jZShtKSwgbSRkZi5yZXNpZHVhbCkKICAgaSA8LSBpKzEKIH0KCmRhdGEuZnJhbWUoIG1vZGVsPW1vZGVscywKICAgICAgICAgICAgZGV2aWFuY2U9cm91bmQoZGRbLDFdLDIpLCAKICAgICAgICAgICAgcHZhbD1yb3VuZChwY2hpc3EoZGRbLDFdLCBkZFssMl0sIGxvd2VyLnRhaWwgPSBGQUxTRSksIDQpKQpgYGAKCmBgYHtyfQojIOychOyXkOyEnCwgZm9ybXVsYSDsl5Ag65Ok7Ja06rCA64qUIOuqqOuToCBmZWF0dXJlIOuTpOydmCBzdWJzZXQg7JeQIOuMgO2VtCDtj4nqsIDtlZjripQg7Iuc64+E66W8IO2VtOu0pOuKlOuNsCwgIAojIO2Kue2eiCDqt7gg7KGw7ZWp7J2YIOyImOqwgCDrp47snYAg6rK97JqwIOunpOyasCDripDrpqzri6TripQg6rKD7J2EIOuztOyVmOuLpC4KIyDsnbTrn7Ag6rK97JqwLCDqs4TsgrDrn4nsnYQg7KSE7J2064qUIOq4sOuylSDspJHsl5Ag7ZWY64KY6rCAIFJpZGdlIO2YueydgCBMYXNzbyBSZWdyZXNzaW9uIOydtOuLpC4gCmBgYAoKIyMgTW9kZWwgU2VsZWN0aW9uICggU3RhdGlzdGljYWwgVGVjaG5pY2FscyApCmBgYHtyfQojIOyVhOuemCBSaWRnZSDsmYAgTGFzc28g66W8IOuztOq4sOyghOyXkCwgTW9kZWwgU2VsZWN0aW9uIOyXkCDrjIDtlZwg67aA67aE7J2EIOuUlOuyvCDrs7TsnpAuCiMgCiMgcmVmIDogaHR0cHM6Ly9sYWd1bml0YS5zdGFuZm9yZC5lZHUvYzR4L0h1bWFuaXRpZXNTY2llbmNlL1N0YXRMZWFybmluZy9hc3NldC9tb2RlbF9zZWxlY3Rpb24ucGRmCiMgcmVmIDogaHR0cDovL3Nvc2FsLmtyLzg2OAojIHJlZiA6IGh0dHA6Ly93d3cuc3RhdGdyb3VuZC5vcmcvP21vZHVsZT1maWxlJmFjdD1wcm9jRmlsZURvd25sb2FkJmZpbGVfc3JsPTkxNDUmc2lkPWEwYTRlN2ZkMjE1MDNlNDUxOTRkNDg1Y2NiMGM1NDc2Jm1vZHVsZV9zcmw9MTM3CiMKIyAxLiBTdWJzZXQgU2VsZWN0aW9uIDogbGlrZSBhIHJlZ3N1YnNldHMgZnVuY3Rpb24gKCBlc3RpbWF0ZSBtb2RlbCBiYXNlZCBvbiBBSUMgLCBCSUMgLCBBREpSMiAsIENQIC4uICApIAojICAgICAgICAgICAgICAgICAgICAgOiBTdGVwd2lzZSBTZWxlY3Rpb24gKCBCYWNrd2FyZCAvIEZvcndhcmQgKSBvciByZWdzdWJzZXRzICgg7JyE7JeQ7IScIOyImO2Wie2VnCDrgrTsmqkgKQojIDIuIFNocmlua2FnZSAoIFJlZ3VsYXJpemF0aW9uICkgOiBMYXNzbyAsIFJpZGdlICwgRWxhc3RpY05ldAojICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgOiBzaHJpbmtzIHRoZSBjb2VmZmljaWVudCBlc3RpbWF0ZXMgdG93YXJkcyB6ZXJvCiMgMy4gRGltZW5zaW9uIFJlZHVjdGlvbiA6IFBDQSAKIyAKIyBPY2NhbSdzIFJhem9yIGluIE1vZGVsIFNlbGVjdGlvbiAoIOy1nOyGjOydmCBmZWF0dXJlICwg7ISk66qF67OA7IiY66GcIOyEpOuqheydhCDtlZjsnpAgKQojIyBBbGwgdGhpbmdzIGJlaW5nIGVxdWFsLCB1c3VhbGx5IHRoZSBzaW1wbGVzdCBleHBsYW5hdGlvbiBvZiBhIHBoZW5vbWVub24gaXMgYSBnb29kIGh5cG90aGVzaXMuCiMjIFNpbXBsaWNpdHkgPSByZXByZXNlbnRhdGlvbmFsIHN1Y2NpbmN0bmVzcyAKIyMg7Ya16rOEIOuqqOuNuOungeyXkOyEnCDqsITqsrDtlajsnZgg7JuQ66asCiMgIC0g67O17J6h7ZWcIOyEpOuqheuztOuLpCDri6jsiJztlZjqs6Ag6rCE64uo7ZWcIOyEpOuqheydtCDsoovri6QuCiMgIC0g66qo7ZiV7JeQIOyeiOyWtOyEnCDrqqjsiJjripQg6rCA64ql7ZWcIOyggeqyjCDqsIDsp4Dqs6Ag7J6I7Ja07JW8IO2VnOuLpC4KIyAgLSDshKDtmJUg66qo64247J20IOu5hOyEoO2YlSDrqqjrjbjrs7Tri6Qg7KKL64ukLgojICAtIOyggeydgCDsiJjsnZgg6rCA7KCV7J2EIOqwgOynhCDsi6Ttl5jsnYAg66eO7J2AIOqwgOygleydhCDqsIDsp4Qg7Iuk7ZeY67O064ukIOyii+uLpC4KIyAgLSDrjbDsnbTthLDroZzrtoDthLAg7ZqM6reA66qo64247J2EIOq1rO2VoCDrlYzripQg7JyE7ZW07ISgIOy1nOyGjOygge2VqeydtCDrkKAg65WM6rmM7KeAIOy2leyGjO2VtOyVvO2VnOuLpC4KIyMg64uo7Iic7ZmUIOyekeyXhSDrqqnroZ0KIyAgLSDsnKDsnZjtlZjsp4Ag7JWK7J2AIOq1kO2YuOyekeyaqSDtla3rqqnsnYQg7KCc6rGw7ZWc64ukLgojICAtIOycoOydmO2VmOyngCDslYrsnYAgMuywqCDrmJDripQg67mE7ISg7ZiVIO2VreuqqeydhCDsoJzqsbDtlZzri6QuCiMgIC0g7Jyg7J2Y7ZWY7KeAIOyViuydgCDshKTrqoUg67OA7IiY66W8IOygnOqxsO2VnOuLpC4KIyAgLSDsnKDsgqztlZwg66qo7IiY6rCS7J2EIOqwluuKlCDshKTrqoUg67OA7IiY66W8IO2Gte2Vqe2VnOuLpC4KIwojIOyEoO2Yle2ajOq3gOuqqO2YleyXkOyEnCDrqqjtmJXqs4TsiJgg67Kh7YSwKGNvZWZmaWNpZW50IGVzdGltYXRlZCB2YWx1ZSkg7JeQIOuMgO2VnCDstZzshozsoJzqs7Eg7ZW067O064ukCiMg7J206rKD7J2EIOyVveqwhCDstpXshoztlZwgcmlkZ2Ug7ZW066W8IOyTsOuKlCDqsoPsnbQg7JiI7LihIOyEseqzvOqwgCDsoovsnYAg6rKD7Jy866GcIOyVjOugpOyguCDsnojri6QuIAojIOuYkO2VnCDrqqjtmJXqs4TsiJgg67Kh7YSw7J2YIOydvOu2gOyalOyGjOulvCAw7Jy866GcIO2HtO2ZlOyLnO2CqCBsYXNzbyDtlbTrpbwg7JOw6rKMIOuQmOuptCDrqqjtmJXsnbQg6rCE6rKw7ZW07KeE64uk64qUIOyeh+ygkOydtCDsnojri6QuIApgYGAKCiMjIFJpZGdlIFJlZ3Jlc3Npb24gKCBMaW5lYXIgUmVncmVzc2lvbiB3aXRoIEwyIHJlZ3VsYXJpemF0aW9uLCAgzrE9MCAgKQpgYGB7cn0KIyByZWYgOiBodHRwczovL29ubGluZWNvdXJzZXMuc2NpZW5jZS5wc3UuZWR1L3N0YXQ4NTcvbm9kZS8xNTUKIyByZWYgOiBodHRwczovL25jc3Mtd3BlbmdpbmUubmV0ZG5hLXNzbC5jb20vd3AtY29udGVudC90aGVtZXMvbmNzcy9wZGYvUHJvY2VkdXJlcy9OQ1NTL1JpZGdlX1JlZ3Jlc3Npb24ucGRmCiMgcmVmIDogaHR0cHM6Ly9sYWd1bml0YS5zdGFuZm9yZC5lZHUvYzR4L0h1bWFuaXRpZXNTY2llbmNlL1N0YXRMZWFybmluZy9hc3NldC9tb2RlbF9zZWxlY3Rpb24ucGRmCiMgcmVmIDogaHR0cHM6Ly93ZWIuc3RhbmZvcmQuZWR1L35oYXN0aWUvZ2xtbmV0L2dsbW5ldF9hbHBoYS5odG1sCiMgcmVmIDogaHR0cHM6Ly9kcnNpbW9uai5zdmJ0bGUuY29tL3JpZGdlLXJlZ3Jlc3Npb24td2l0aC1nbG1uZXQKIyByZWYgOiBodHRwczovL2dlcmFyZG5pY28uY29tL3dpa2kvbGFuZy9yL3JpZGdlX2xhc3NvI2Zvcm11bGFfcGFyYW1ldGVycwojIHJlZiA6IGh0dHA6Ly9yLWJvbmcuYmxvZ3Nwb3Qua3IvcC9ibG9nLXBhZ2VfNC5odG1sCiMgCiMgTW90aXZhdGlvbjogdG9vIG1hbnkgcHJlZGljdG9ycwojIE1vdGl2YXRpb246IGlsbC1jb25kaXRpb25lZCBYCiMgTW90aXZhdGlvbjog64uk7KSR6rO167aE7IKw7ISxIOyhtOyerCDtlbTqsrAgCmBgYAohW10oL1VzZXJzL0NBL0Rvd25sb2Fkcy9yaWRnZS5wbmcpCgpgYGB7cn0KbGlicmFyeShnbG1uZXQpCmRhdGEoQmlub21pYWxFeGFtcGxlKQoKZ2xpbXBzZShhcy5kYXRhLmZyYW1lKHgpKQoKbW9kZWwucmlkZ2UgPC0gZ2xtbmV0KHgsIHksIGZhbWlseSA9ICJiaW5vbWlhbCIsIGFscGhhID0gMCApCgpwYXIobWZyb3c9YygyLDIpKQpwbG90KGRlbnNpdHkoeSkpCnBsb3QobW9kZWwucmlkZ2UsIHh2YXI9ImxhbWJkYSIsIGxhYmVsPVRSVUUpCnBsb3QobW9kZWwucmlkZ2UsIHh2YXI9Im5vcm0iLCBsYWJlbD1UUlVFKQpwbG90KG1vZGVsLnJpZGdlLCB4dmFyPSJkZXYiLCBsYWJlbD1UUlVFKQpgYGAKCmBgYHtyfQpjdi5yaWRnZSA8LSBjdi5nbG1uZXQoeCwgeSwgYWxwaGEgPSAwLCBmYW1pbHkgPSAiYmlub21pYWwiLCBuZm9sZHMgPSAxMDApCnBsb3QoY3YucmlkZ2UpCgpjb2VmKGN2LnJpZGdlLCBzID0gY3YucmlkZ2UkbGFtYmRhLm1pbikKYGBgCgpgYGB7cn0KbGlicmFyeShkb01DKQpyZWdpc3RlckRvTUMoY29yZXMgPSA0KQpjdi5yaWRnZSA8LSBjdi5nbG1uZXQoeCwgeSwgYWxwaGEgPSAwLCBmYW1pbHkgPSAiYmlub21pYWwiLCBuZm9sZHMgPSAxMDAsIHR5cGUubWVhc3VyZSA9ICJjbGFzcyIpCnBsb3QoY3YucmlkZ2UpCmBgYAoKCmBgYHtyfQpmb2xkaWQgPC0gc2FtcGxlKDE6MTAsc2l6ZT1sZW5ndGgoeSkscmVwbGFjZT1UUlVFKQpjdi4xICA8LSBjdi5nbG1uZXQoeCx5LGZvbGRpZD1mb2xkaWQsYWxwaGE9MSkKY3YuMDUgPC0gY3YuZ2xtbmV0KHgseSxmb2xkaWQ9Zm9sZGlkLGFscGhhPS41KQpjdi4wICA8LSBjdi5nbG1uZXQoeCx5LGZvbGRpZD1mb2xkaWQsYWxwaGE9MCkKCnBhcihtZnJvdz1jKDIsMikpCnBsb3QoY3YuMSk7cGxvdChjdi4wNSk7cGxvdChjdi4wKQpwbG90KGxvZyhjdi4xJGxhbWJkYSksY3YuMSRjdm0scGNoPTE5LGNvbD0icmVkIix4bGFiPSJsb2coTGFtYmRhKSIseWxhYj1jdi4xJG5hbWUpCnBvaW50cyhsb2coY3YuMDUkbGFtYmRhKSxjdi4wNSRjdm0scGNoPTE5LGNvbD0iZ3JleSIpCnBvaW50cyhsb2coY3YuMCRsYW1iZGEpLGN2LjAkY3ZtLHBjaD0xOSxjb2w9ImJsdWUiKQpsZWdlbmQoInRvcGxlZnQiLGxlZ2VuZD1jKCJhbHBoYT0gMSIsImFscGhhPSAuNSIsImFscGhhIDAiKSxwY2g9MTksY29sPWMoInJlZCIsImdyZXkiLCJibHVlIikpCmBgYAoKIyMgTGFzc28gUmVncmVzc2lvbiAKCiMjIEVsYXN0aWNOZXQgUmVncmVzc2lvbgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoK