cat("\014")
rm(list = ls())
library(ggplot2)
Registered S3 method overwritten by 'dplyr':
method from
print.rowwise_df
library(ggrepel)
library(devtools)
Loading required package: usethis
#install_github("vqv/ggbiplot")
library(ggbiplot)
Loading required package: plyr
Loading required package: scales
Loading required package: grid
library(readxl)
library(nortest)
situacion_analisis= c(1,2,3) #grupo de alumnos a analizar según situacion academica
cuat_ini_analisis = 20090 #cuatrimestre inicial de analisis (siempre hasta el presente)
columnas = c(1,8,9,12:17) #variables a tener en cuenta (menos que las de egresados)
datos_crudos=read_xlsx("base_de_alumnos.xlsx",
sheet = 1,col_types = "numeric")
datos_numericos_1 = datos_crudos[(datos_crudos$acuat_ing>=cuat_ini_analisis)&
datos_crudos$sit_ac %in% situacion_analisis,]
datos_numericos_2 = data.frame(datos_numericos_1[columnas])
#se queda con casos completos
datos_completos = datos_numericos_2[complete.cases(datos_numericos_2),]
datos = datos_completos[c(3:ncol(datos_completos))]
#analsis exploratorio
par(mfcol = c(1,length(datos)))
for (k in 1:length(datos)){
boxplot(datos[k],main = names(datos[k]))
grid()
}

#analsis exploratorio
par(mfcol = c(2,4))
#par(mfcol = c(1,length(datos)))
for (k in 1:length(datos)){
hist(datos[,k],proba = T,main = names(datos[,k]),10)
x0 <- seq(min(datos[, k]), max(datos[, k]), le = 50)
lines(x0, dnorm(x0, mean(datos[,k]), sd(datos[,k])), col = "red", lwd = 2)
grid()
}

#analsis exploratorio
pval = list()
par(mfcol = c(1,length(datos)))
for (k in 1:length(datos)){
qqnorm(datos[,k],main = names(datos[k]))
qqline(datos[,k],col="red")
pval[k] = ad.test(datos[,k])$p.value
grid()
}

pval
[[1]]
[1] 3.7e-24
[[2]]
[1] 3.7e-24
[[3]]
[1] 3.7e-24
[[4]]
[1] 3.7e-24
[[5]]
[1] 3.7e-24
[[6]]
[1] 3.7e-24
[[7]]
[1] 3.7e-24
#estandarizo datos
datos_estandarizados = data.frame(scale(datos))
boxplot(datos_estandarizados)

#dispersograma - Ojo que tarda
pairs(datos_estandarizados,pch=19,cex=0.8)

#matriz de correlaciones aplicada directamente a "datos"
matriz_de_correlaciones = cor(datos)
round(matriz_de_correlaciones,2)
edad_1c n_mat_1c n_fallas_1c prom_1c n_mat_1y2c n_fallas_1y2c prom_1y2c
edad_1c 1.00 -0.20 -0.13 0.03 -0.25 -0.12 0.03
n_mat_1c -0.20 1.00 0.08 0.08 0.76 0.02 0.12
n_fallas_1c -0.13 0.08 1.00 -0.06 0.13 0.79 -0.06
prom_1c 0.03 0.08 -0.06 1.00 0.05 -0.06 0.80
n_mat_1y2c -0.25 0.76 0.13 0.05 1.00 0.07 0.11
n_fallas_1y2c -0.12 0.02 0.79 -0.06 0.07 1.00 -0.08
prom_1y2c 0.03 0.12 -0.06 0.80 0.11 -0.08 1.00
desc_mat_cor = eigen(matriz_de_correlaciones)
autovalores_cor = desc_mat_cor$values
round(autovalores_cor,2)
[1] 2.05 1.94 1.50 0.87 0.24 0.21 0.19
#cuanta variabilidad concentra cada autovalor?
#es lo mismo calcular esa variabilidad con los autovalores de una matriz u otra?
variabilidad_cor = autovalores_cor/sum(autovalores_cor)
round(variabilidad_cor,2)
[1] 0.29 0.28 0.21 0.12 0.03 0.03 0.03
#comando que ejecuta el metodo de componentes principales
datos.pc = prcomp(datos,scale = TRUE)
#datos.pc$sdev #raiz cuadrada de los autovalores
round(datos.pc$sdev^2,2)
[1] 2.05 1.94 1.50 0.87 0.24 0.21 0.19
round(datos.pc$rotation,2) #autovectores (en columna)
PC1 PC2 PC3 PC4 PC5 PC6 PC7
edad_1c 0.31 -0.07 0.16 -0.93 0.04 -0.01 0.01
n_mat_1c -0.52 -0.17 -0.38 -0.26 -0.68 0.07 -0.15
n_fallas_1c -0.41 0.37 0.43 -0.10 0.05 0.69 0.16
prom_1c -0.12 -0.57 0.41 0.07 -0.18 -0.15 0.66
n_mat_1y2c -0.54 -0.14 -0.37 -0.20 0.67 -0.14 0.19
n_fallas_1y2c -0.37 0.39 0.46 -0.07 -0.08 -0.68 -0.18
prom_1y2c -0.15 -0.58 0.37 0.05 0.20 0.15 -0.67
round(datos.pc$center,2) #vector de medias (de casualidad coinciden)
edad_1c n_mat_1c n_fallas_1c prom_1c n_mat_1y2c n_fallas_1y2c prom_1y2c
20.09 1.80 0.44 6.63 3.45 0.94 6.66
round(datos.pc$scale,2) #vector de desvios
edad_1c n_mat_1c n_fallas_1c prom_1c n_mat_1y2c n_fallas_1y2c prom_1y2c
2.45 0.99 0.71 1.35 2.02 1.18 1.11
#loadings
carga1 = data.frame(cbind(X=1:length(datos),
primeracarga=data.frame(datos.pc$rotation)[,1]))
carga2 = data.frame(cbind(X=1:length(datos),
segundacarga=data.frame(datos.pc$rotation)[,2]))
round(cbind(carga1,carga2),2)
ggplot(carga1, aes(X,primeracarga) ,
fill=tramo ) + geom_bar ( stat="identity" ,
position="dodge" ,
fill ="royalblue" ,
width =0.5 ) + xlab( 'Tramo' ) + ylab('Primeracarga ' )

ggplot( carga2 , aes ( X , segundacarga ) ,
fill =X ) + geom_bar ( stat="identity" , position="dodge" ,
fill ="royalblue" ,
width =0.5 ) +
xlab('Tramo') + ylab('Segundacarga')

ggbiplot(datos.pc, obs.scale=1 ,var.scale=1,alpha=0.0) #cambiando el alfa?

#calculo de scores de cada individuo
CP1 = as.matrix(datos_estandarizados)%*%as.matrix(carga1[2])
CP2 = as.matrix(datos_estandarizados)%*%as.matrix(carga2[2])
datos_estandarizados$CP1 = CP1
datos_estandarizados$CP2 = CP2
ggbiplot(datos.pc, obs.scale=0.5 ,var.scale=1,
alpha=0.5,groups=factor(datos_completos$sit_ac)) +
scale_color_manual(name="situacion academica", values=c("black", "red","green"),labels=c("cursantes", "desertores","egresados")) +
theme(legend.direction ="horizontal", legend.position = "top")

library(MASS)
datos_train = datos_completos[datos_completos$sit_ac %in% c(2,3),] #se realiza un analisis discriminante con las clases 2 y 3
modelo_lda <- lda(formula = as.factor(sit_ac) ~
edad_1c + n_mat_1c + n_fallas_1c + prom_1c
+ n_mat_1y2c + n_fallas_1y2c + prom_1y2c , data = datos_train)
modelo_lda
Call:
lda(as.factor(sit_ac) ~ edad_1c + n_mat_1c + n_fallas_1c + prom_1c +
n_mat_1y2c + n_fallas_1y2c + prom_1y2c, data = datos_train)
Prior probabilities of groups:
2 3
0.7139551 0.2860449
Group means:
edad_1c n_mat_1c n_fallas_1c prom_1c n_mat_1y2c n_fallas_1y2c prom_1y2c
2 20.55818 1.464506 0.2722853 6.553522 2.615559 0.660940 6.573485
3 19.36003 2.360032 0.1270227 6.484709 5.292071 0.263754 6.667348
Coefficients of linear discriminants:
LD1
edad_1c -0.05140860
n_mat_1c -0.18549629
n_fallas_1c -0.26415157
prom_1c -0.11196861
n_mat_1y2c 0.63107883
n_fallas_1y2c -0.25074001
prom_1y2c 0.03414477
#predecimos la clase en base al modelo entrenado (o sea, como se comportan los mismos datos usados para el modelo)
pred_lda_train <- predict(modelo_lda,datos_train)
table(datos_train$sit_ac, pred_lda_train$class, dnn = c("Clase real","Clase predicha"))
Clase predicha
Clase real 2 3
2 2729 356
3 430 806
pred_lda_train_2 = ifelse(pred_lda_train$posterior[,1]>0.1,2,3) #que significa esta linea? que es el 0.5??
table(datos_train$sit_ac, pred_lda_train_2, dnn = c("Clase real","Clase predicha"))
Clase predicha
Clase real 2 3
2 3030 55
3 1008 228
#posible intento de entender como se comporta la clase frente a las variables originales.
#Se puede hacer algo mejor?
library(klaR)
Registered S3 methods overwritten by 'htmltools':
method from
print.html tools:rstudio
print.shiny.tag tools:rstudio
print.shiny.tag.list tools:rstudio
partimat(as.factor(sit_ac) ~ edad_1c + n_mat_1c + n_fallas_1c + prom_1c,
data = datos_train, method = "lda", prec = 200,
image.colors = c("darkgoldenrod1", "snow2"),col.mean = "firebrick")

pred_lda_completos <- predict(modelo_lda,datos_completos)
ggbiplot(datos.pc, obs.scale=0.1 ,var.scale=1,
alpha=1,groups=factor(pred_lda_completos$class)) +
scale_color_manual(name="prediccion lda", values=c("red","green"),labels=c("desertores","egresados")) +
theme(legend.direction ="horizontal", legend.position = "top")

modelo_qda <- qda(as.factor(sit_ac) ~
edad_1c + n_mat_1c + n_fallas_1c + prom_1c
+ n_mat_1y2c + n_fallas_1y2c + prom_1y2c , data = datos_train)
modelo_qda
Call:
qda(as.factor(sit_ac) ~ edad_1c + n_mat_1c + n_fallas_1c + prom_1c +
n_mat_1y2c + n_fallas_1y2c + prom_1y2c, data = datos_train)
Prior probabilities of groups:
2 3
0.7139551 0.2860449
Group means:
edad_1c n_mat_1c n_fallas_1c prom_1c n_mat_1y2c n_fallas_1y2c prom_1y2c
2 20.55818 1.464506 0.2722853 6.553522 2.615559 0.660940 6.573485
3 19.36003 2.360032 0.1270227 6.484709 5.292071 0.263754 6.667348
pred_qda_train <- predict(modelo_qda,datos_train)
table(datos_train$sit_ac, pred_qda_train$class, dnn = c("Clase real","Clase predicha"))
Clase predicha
Clase real 2 3
2 2450 635
3 211 1025
# Y cuanto daba con el lda??
table(datos_train$sit_ac, pred_lda_train$class, dnn = c("Clase real","Clase predicha"))
Clase predicha
Clase real 2 3
2 2729 356
3 430 806
library(caret)
Loading required package: lattice
Registered S3 method overwritten by 'data.table':
method from
print.data.table
confusion_lda = confusionMatrix(factor(datos_train$sit_ac), pred_lda_train$class)
confusion_lda
Confusion Matrix and Statistics
Reference
Prediction 2 3
2 2729 356
3 430 806
Accuracy : 0.8181
95% CI : (0.8063, 0.8295)
No Information Rate : 0.7311
P-Value [Acc > NIR] : < 2.2e-16
Kappa : 0.5465
Mcnemar's Test P-Value : 0.009219
Sensitivity : 0.8639
Specificity : 0.6936
Pos Pred Value : 0.8846
Neg Pred Value : 0.6521
Prevalence : 0.7311
Detection Rate : 0.6316
Detection Prevalence : 0.7140
Balanced Accuracy : 0.7788
'Positive' Class : 2
confusion_qda = confusionMatrix(factor(datos_train$sit_ac), pred_qda_train$class)
confusion_qda
Confusion Matrix and Statistics
Reference
Prediction 2 3
2 2450 635
3 211 1025
Accuracy : 0.8042
95% CI : (0.7921, 0.816)
No Information Rate : 0.6158
P-Value [Acc > NIR] : < 2.2e-16
Kappa : 0.5653
Mcnemar's Test P-Value : < 2.2e-16
Sensitivity : 0.9207
Specificity : 0.6175
Pos Pred Value : 0.7942
Neg Pred Value : 0.8293
Prevalence : 0.6158
Detection Rate : 0.5670
Detection Prevalence : 0.7140
Balanced Accuracy : 0.7691
'Positive' Class : 2
pred_qda_completos <- predict(modelo_qda,datos_completos)
ggbiplot(datos.pc, obs.scale=0.5 ,var.scale=1,
alpha=1,groups=factor(pred_qda_completos$class)) +
scale_color_manual(name="prediccion qda", values=c("red","green"),labels=c("desertores","egresados")) +
theme(legend.direction ="horizontal", legend.position = "top")

#regresión logistica
modelo_lg <- glm(as.factor(sit_ac) ~
edad_1c + n_mat_1c + n_fallas_1c + prom_1c
+ n_mat_1y2c + n_fallas_1y2c + prom_1y2c , data = datos_train,family=binomial)
modelo_lg
Call: glm(formula = as.factor(sit_ac) ~ edad_1c + n_mat_1c + n_fallas_1c +
prom_1c + n_mat_1y2c + n_fallas_1y2c + prom_1y2c, family = binomial,
data = datos_train)
Coefficients:
(Intercept) edad_1c n_mat_1c n_fallas_1c prom_1c n_mat_1y2c n_fallas_1y2c prom_1y2c
2.89307 -0.24816 -0.30848 -0.46255 -0.16191 0.88365 -0.52519 -0.06329
Degrees of Freedom: 4320 Total (i.e. Null); 4313 Residual
Null Deviance: 5173
Residual Deviance: 3287 AIC: 3303
pred_lg_train <- predict(modelo_lg,type = "response")
clase_lg_train = ifelse(pred_lg_train>0.5,1,0) #ojo que el modelo genera la clase con 0 y 1 (no con 2 y 3)
table(datos_train$sit_ac, clase_lg_train, dnn = c("Clase real","Clase predicha"))
Clase predicha
Clase real 0 1
2 2764 321
3 464 772
#regresión logistica 2. Modelo mas simple sacando las que parecÃan tener correlación.
#no es desable tener multicolinealidad de variables regresoras.
modelo2_lg <- glm(as.factor(sit_ac) ~
edad_1c + n_mat_1c + n_fallas_1c + prom_1c , data = datos_train,family=binomial)
glm.fit: fitted probabilities numerically 0 or 1 occurred
modelo2_lg
Call: glm(formula = as.factor(sit_ac) ~ edad_1c + n_mat_1c + n_fallas_1c +
prom_1c, family = binomial, data = datos_train)
Coefficients:
(Intercept) edad_1c n_mat_1c n_fallas_1c prom_1c
10.7459 -0.6190 0.8745 -0.9513 -0.1391
Degrees of Freedom: 4320 Total (i.e. Null); 4316 Residual
Null Deviance: 5173
Residual Deviance: 4050 AIC: 4060
pred2_lg_train <- predict(modelo2_lg,type = "response")
clase2_lg_train = ifelse(pred2_lg_train>0.5,1,0) #que significa esta linea? que es el 0.5??
table(datos_train$sit_ac, clase2_lg_train, dnn = c("Clase real","Clase predicha"))
Clase predicha
Clase real 0 1
2 2840 245
3 686 550
#Modelo support vector machine svm
library(e1071)
modelo_svm=svm(as.factor(sit_ac)~edad_1c + n_mat_1c + n_fallas_1c + prom_1c
+ n_mat_1y2c+n_fallas_1y2c+prom_1y2c,
data=datos_train,method="C-classification",kernel="radial",cost=10,gamma=.1)
pred_svm=predict(modelo_svm, datos_train)
table(datos_train$sit_ac, pred_svm, dnn = c("Clase real", "Clase predicha"))
Clase predicha
Clase real 2 3
2 2713 372
3 340 896
error_svm<- mean(datos_train$sit_ac!= pred_svm) * 100
error_svm
[1] 16.47767
#comparacion de predicciones de diferentes modelos:
predicciones_varias = cbind(pred_lda_train$posterior[,2],
pred_qda_train$posterior[,2],
pred_lg_train,
pred2_lg_train)
cor(predicciones_varias)
pred_lg_train pred2_lg_train
1.0000000 0.9059432 0.9905854 0.7607068
0.9059432 1.0000000 0.9295371 0.7554916
pred_lg_train 0.9905854 0.9295371 1.0000000 0.7833219
pred2_lg_train 0.7607068 0.7554916 0.7833219 1.0000000
#analisis de cluster
#este primer bloque es solo para definir funciones.
library(cluster)
library(pracma)
Attaching package: ‘pracma’
The following object is masked from ‘package:e1071’:
sigmoid
# se define funcion de escalamiento disferente de la tipica normal.
esc01 <- function(x) { (x - min(x)) / (max(x) - min(x))}
# se define una funcion para calcular metricas que orientan sobre el numero de clusters a elegir para el problema.
metrica = function(datA_esc,kmax,f) {
sil = array()
#sil_2 = array()
sse = array()
datA_dist= dist(datA_esc,method = "euclidean", diag = FALSE, upper = FALSE, p = 2)
for ( i in 2:kmax) {
if (strcmp(f,"kmeans")==TRUE) { #centroide: tipico kmeans
CL = kmeans(datA_esc,centers=i,nstart=50,iter.max = kmax)
sse[i] = CL$tot.withinss
CL_sil = silhouette(CL$cluster, datA_dist)
sil[i] = summary(CL_sil)$avg.width
}
if (strcmp(f,"pam")==TRUE){ #medoide: ojo porque este metodo tarda muchisimo
CL = pam(x=datA_esc, k=i, diss = F, metric = "euclidean")
sse[i] = CL$objective[1]
sil[i] = CL$silinfo$avg.width
}
}
sse
sil
return(data.frame(sse,sil))
}
#en este bloque se estudia cuantos clusters convendrÃa generar respecto a indicadores tipicos de Clustering --> por ejemplo el "Silhouette"
kmax = 7
#2 opciones de escalamiento
#m1 = metrica(apply(datos,2,esc01),kmax,"kmeans") #definida en la funcion esc01
m1 = metrica(scale(datos),kmax,"kmeans") #tipica de la normal
did not converge in 7 iterationsdid not converge in 7 iterations
#graficos de los indicadores de clustering
par(mfrow=c(2,1))
plot(2:kmax, m1$sil[2:kmax],col=1,type="b", pch = 19, frame = FALSE,
xlab="Number of clusters K",
ylab="sil")
plot(2:kmax, m1$sse[2:kmax],type="b", pch = 19, frame = FALSE,
xlab="Number of clusters K",
ylab="sse")
par(mfrow=c(1,1))

#elegimos realizar 3 grupos
CL = kmeans(scale(datos),5,nstart=50,iter.max = 10)
#CL = kmeans(apply(datos,2,esc01),3,nstart=50,iter.max = 10)
datos$kmeans = CL$cluster
#en cuales 2 variables me conviene visualizar el cluster?
plot(datos$edad_1c,datos$prom_1c,col=datos$kmeans)+
grid()
integer(0)

#conviene en un biplot ya que tengo las flechas de las variables originales
ggbiplot(datos.pc, obs.scale=1 ,var.scale=1, alpha=0.5,groups = as.factor(datos$kmeans) )+
theme(legend.direction ="horizontal", legend.position = "top")

#lo hacemos finalmente para 3 grupos y lo visualizamos en un biplot
CL = kmeans(scale(datos),3,nstart=50,iter.max = 10)
datos$kmeans = CL$cluster
ggbiplot(datos.pc, obs.scale=1 ,var.scale=1, alpha=0.5,groups = as.factor(datos$kmeans) )+
scale_color_manual(name="Cluster kmeans", values=c("orange", "cyan","grey"),labels=c("grupo 1", "grupo 2","grupo 3")) +
theme(legend.direction ="horizontal", legend.position = "top")

#cluster jerárquico
datos2=datos[,-8]#quito columna "kmeans"
datos2=scale(datos2)
# Matriz de distancias euclÃdeas
mat_dist <- dist(x = datos2, method = "euclidean")
# Dendrogramas (según el tipo de segmentación jerárquica aplicada)
hc_complete <- hclust(d = mat_dist, method = "complete")
hc_average <- hclust(d = mat_dist, method = "average")
hc_single <- hclust(d = mat_dist, method = "single")
hc_ward <- hclust(d = mat_dist, method = "ward.D2")
#calculo del coeficiente de correlacion cofenetico
cor(x = mat_dist, cophenetic(hc_complete))
[1] 0.5846528
cor(x = mat_dist, cophenetic(hc_average))
[1] 0.7259612
cor(x = mat_dist, cophenetic(hc_single))
[1] 0.552105
cor(x = mat_dist, cophenetic(hc_ward))
[1] 0.4236285
# construccion de un dendograma usando los resultados de la técnica de Ward
plot(hc_ward )#no se ve bien si hay muchos datos
rect.hclust(hc_ward, k=3, border="red")#con 3 grupos

grupos<-cutree(hc_ward,k=3)#con 3 grupos
#split(rownames(datos),grupos)#devuelve una lista con las observaciones separadas por grupo
#visualizamos con 3 grupos el cluster jerarquico de la misma forma que kmeans
ggbiplot(datos.pc, obs.scale=1 ,var.scale=1, alpha=0.5,groups = as.factor(grupos) )+
scale_color_manual(name="Cluster jerárquico Ward", values=c("orange", "cyan","grey"),labels=c("grupo 1", "grupo 2","grupo 3")) +
theme(legend.direction ="horizontal", legend.position = "top")

LS0tCnRpdGxlOiAiQ2xhc2UgQUlEOiBDbHVzdGVycyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKYGBge3IgZWNobz1UUlVFfQpjYXQoIlwwMTQiKQpybShsaXN0ID0gbHMoKSkKbGlicmFyeShnZ3Bsb3QyKSAKbGlicmFyeShnZ3JlcGVsKQpsaWJyYXJ5KGRldnRvb2xzKQojaW5zdGFsbF9naXRodWIoInZxdi9nZ2JpcGxvdCIpCmxpYnJhcnkoZ2diaXBsb3QpCmxpYnJhcnkocmVhZHhsKQpsaWJyYXJ5KG5vcnRlc3QpCmBgYAoKYGBge3IgZWNobz1UUlVFfQpzaXR1YWNpb25fYW5hbGlzaXM9IGMoMSwyLDMpICAgICAgI2dydXBvIGRlIGFsdW1ub3MgYSBhbmFsaXphciBzZWfDum4gc2l0dWFjaW9uIGFjYWRlbWljYQpjdWF0X2luaV9hbmFsaXNpcyA9IDIwMDkwICAgICAgICAgI2N1YXRyaW1lc3RyZSBpbmljaWFsIGRlIGFuYWxpc2lzIChzaWVtcHJlIGhhc3RhIGVsIHByZXNlbnRlKQpjb2x1bW5hcyA9IGMoMSw4LDksMTI6MTcpICAgICAgICAgI3ZhcmlhYmxlcyBhIHRlbmVyIGVuIGN1ZW50YSAobWVub3MgcXVlIGxhcyBkZSBlZ3Jlc2Fkb3MpCgpgYGAKCmBgYHtyIGVjaG89VFJVRX0KZGF0b3NfY3J1ZG9zPXJlYWRfeGxzeCgiYmFzZV9kZV9hbHVtbm9zLnhsc3giLAogICAgICAgICAgICAgICAgICAgICAgIHNoZWV0ID0gMSxjb2xfdHlwZXMgPSAibnVtZXJpYyIpCgpkYXRvc19udW1lcmljb3NfMSA9IGRhdG9zX2NydWRvc1soZGF0b3NfY3J1ZG9zJGFjdWF0X2luZz49Y3VhdF9pbmlfYW5hbGlzaXMpJgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGF0b3NfY3J1ZG9zJHNpdF9hYyAlaW4lIHNpdHVhY2lvbl9hbmFsaXNpcyxdCgpkYXRvc19udW1lcmljb3NfMiA9IGRhdGEuZnJhbWUoZGF0b3NfbnVtZXJpY29zXzFbY29sdW1uYXNdKQojc2UgcXVlZGEgY29uIGNhc29zIGNvbXBsZXRvcwpkYXRvc19jb21wbGV0b3MgPSBkYXRvc19udW1lcmljb3NfMltjb21wbGV0ZS5jYXNlcyhkYXRvc19udW1lcmljb3NfMiksXQpkYXRvcyA9IGRhdG9zX2NvbXBsZXRvc1tjKDM6bmNvbChkYXRvc19jb21wbGV0b3MpKV0KCmBgYAoKYGBge3IgZWNobz1UUlVFfQojYW5hbHNpcyBleHBsb3JhdG9yaW8KcGFyKG1mY29sID0gYygxLGxlbmd0aChkYXRvcykpKQogICAgZm9yIChrIGluIDE6bGVuZ3RoKGRhdG9zKSl7CiAgICAgIGJveHBsb3QoZGF0b3Nba10sbWFpbiA9IG5hbWVzKGRhdG9zW2tdKSkKICAgICAgZ3JpZCgpCiAgICB9CmBgYApgYGB7ciBlY2hvPVRSVUV9CiNhbmFsc2lzIGV4cGxvcmF0b3JpbwpwYXIobWZjb2wgPSBjKDIsNCkpCiNwYXIobWZjb2wgPSBjKDEsbGVuZ3RoKGRhdG9zKSkpCiAgICBmb3IgKGsgaW4gMTpsZW5ndGgoZGF0b3MpKXsKICAgICAgaGlzdChkYXRvc1ssa10scHJvYmEgPSBULG1haW4gPSBuYW1lcyhkYXRvc1ssa10pLDEwKQogICAgICB4MCA8LSBzZXEobWluKGRhdG9zWywga10pLCBtYXgoZGF0b3NbLCBrXSksIGxlID0gNTApIAogICAgICBsaW5lcyh4MCwgZG5vcm0oeDAsIG1lYW4oZGF0b3NbLGtdKSwgc2QoZGF0b3NbLGtdKSksIGNvbCA9ICJyZWQiLCBsd2QgPSAyKSAKICAgICAgZ3JpZCgpCiAgICB9CmBgYAoKYGBge3IgZWNobz1UUlVFfQojYW5hbHNpcyBleHBsb3JhdG9yaW8KcHZhbCA9IGxpc3QoKSAKcGFyKG1mY29sID0gYygxLGxlbmd0aChkYXRvcykpKQogICAgZm9yIChrIGluIDE6bGVuZ3RoKGRhdG9zKSl7CiAgICAgIHFxbm9ybShkYXRvc1ssa10sbWFpbiA9IG5hbWVzKGRhdG9zW2tdKSkKICAgICAgcXFsaW5lKGRhdG9zWyxrXSxjb2w9InJlZCIpIAogICAgICBwdmFsW2tdID0gYWQudGVzdChkYXRvc1ssa10pJHAudmFsdWUKICAgICAgZ3JpZCgpCiAgICB9CgpgYGAKCmBgYHtyIGVjaG89VFJVRX0KcHZhbApgYGAKCgpgYGB7ciBlY2hvPVRSVUV9CiNlc3RhbmRhcml6byBkYXRvcwpkYXRvc19lc3RhbmRhcml6YWRvcyA9IGRhdGEuZnJhbWUoc2NhbGUoZGF0b3MpKQpib3hwbG90KGRhdG9zX2VzdGFuZGFyaXphZG9zKQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2Rpc3BlcnNvZ3JhbWEgLSBPam8gcXVlIHRhcmRhCnBhaXJzKGRhdG9zX2VzdGFuZGFyaXphZG9zLHBjaD0xOSxjZXg9MC44KQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI21hdHJpeiBkZSBjb3JyZWxhY2lvbmVzIGFwbGljYWRhIGRpcmVjdGFtZW50ZSBhICJkYXRvcyIKbWF0cml6X2RlX2NvcnJlbGFjaW9uZXMgPSBjb3IoZGF0b3MpCnJvdW5kKG1hdHJpel9kZV9jb3JyZWxhY2lvbmVzLDIpCmBgYAoKYGBge3IgZWNobz1UUlVFfQpkZXNjX21hdF9jb3IgPSBlaWdlbihtYXRyaXpfZGVfY29ycmVsYWNpb25lcykKYXV0b3ZhbG9yZXNfY29yID0gZGVzY19tYXRfY29yJHZhbHVlcwpyb3VuZChhdXRvdmFsb3Jlc19jb3IsMikKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiNjdWFudGEgdmFyaWFiaWxpZGFkIGNvbmNlbnRyYSBjYWRhIGF1dG92YWxvcj8KI2VzIGxvIG1pc21vIGNhbGN1bGFyIGVzYSB2YXJpYWJpbGlkYWQgY29uIGxvcyBhdXRvdmFsb3JlcyBkZSB1bmEgbWF0cml6IHUgb3RyYT8KdmFyaWFiaWxpZGFkX2NvciA9IGF1dG92YWxvcmVzX2Nvci9zdW0oYXV0b3ZhbG9yZXNfY29yKQpyb3VuZCh2YXJpYWJpbGlkYWRfY29yLDIpCmBgYAoKLSBDb21wb25lbnRlcyBwcmluY2lwYWxlcwoKYGBge3IgZWNobz1UUlVFfQojY29tYW5kbyBxdWUgZWplY3V0YSBlbCBtZXRvZG8gZGUgY29tcG9uZW50ZXMgcHJpbmNpcGFsZXMKZGF0b3MucGMgPSBwcmNvbXAoZGF0b3Msc2NhbGUgPSBUUlVFKQojZGF0b3MucGMkc2RldiAjcmFpeiBjdWFkcmFkYSBkZSBsb3MgYXV0b3ZhbG9yZXMKcm91bmQoZGF0b3MucGMkc2Rldl4yLDIpCmBgYAoKYGBge3IgZWNobz1UUlVFfQpyb3VuZChkYXRvcy5wYyRyb3RhdGlvbiwyKSAjYXV0b3ZlY3RvcmVzIChlbiBjb2x1bW5hKQpgYGAKCmBgYHtyIGVjaG89VFJVRX0Kcm91bmQoZGF0b3MucGMkY2VudGVyLDIpICN2ZWN0b3IgZGUgbWVkaWFzIChkZSBjYXN1YWxpZGFkIGNvaW5jaWRlbikKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CnJvdW5kKGRhdG9zLnBjJHNjYWxlLDIpICN2ZWN0b3IgZGUgZGVzdmlvcwpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2xvYWRpbmdzCmNhcmdhMSA9IGRhdGEuZnJhbWUoY2JpbmQoWD0xOmxlbmd0aChkYXRvcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgcHJpbWVyYWNhcmdhPWRhdGEuZnJhbWUoZGF0b3MucGMkcm90YXRpb24pWywxXSkpCmNhcmdhMiA9IGRhdGEuZnJhbWUoY2JpbmQoWD0xOmxlbmd0aChkYXRvcyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgc2VndW5kYWNhcmdhPWRhdGEuZnJhbWUoZGF0b3MucGMkcm90YXRpb24pWywyXSkpCnJvdW5kKGNiaW5kKGNhcmdhMSxjYXJnYTIpLDIpCmBgYAoKYGBge3IgZWNobz1UUlVFfQpnZ3Bsb3QoY2FyZ2ExLCBhZXMoWCxwcmltZXJhY2FyZ2EpICwKICAgICAgIGZpbGw9dHJhbW8gKSArIGdlb21fYmFyICggc3RhdD0iaWRlbnRpdHkiICwKICAgICAgIHBvc2l0aW9uPSJkb2RnZSIgLAogICAgICAgZmlsbCA9InJveWFsYmx1ZSIgLAogICAgICAgd2lkdGggPTAuNSApICsgeGxhYiggJ1RyYW1vJyApICsgeWxhYignUHJpbWVyYWNhcmdhICcgKQoKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CmdncGxvdCggY2FyZ2EyICwgYWVzICggWCAsIHNlZ3VuZGFjYXJnYSApICwKICAgICAgICBmaWxsID1YICkgKyBnZW9tX2JhciAoIHN0YXQ9ImlkZW50aXR5IiAsIHBvc2l0aW9uPSJkb2RnZSIgLAogICAgICAgICAgIGZpbGwgPSJyb3lhbGJsdWUiICwKICAgICAgICAgICB3aWR0aCA9MC41ICkgKwp4bGFiKCdUcmFtbycpICsgeWxhYignU2VndW5kYWNhcmdhJykKCmBgYAoKYGBge3IgZWNobz1UUlVFfQpnZ2JpcGxvdChkYXRvcy5wYywgb2JzLnNjYWxlPTEgLHZhci5zY2FsZT0xLGFscGhhPTAuMCkgI2NhbWJpYW5kbyBlbCBhbGZhPwpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2NhbGN1bG8gZGUgc2NvcmVzIGRlIGNhZGEgaW5kaXZpZHVvCkNQMSA9IGFzLm1hdHJpeChkYXRvc19lc3RhbmRhcml6YWRvcyklKiVhcy5tYXRyaXgoY2FyZ2ExWzJdKQpDUDIgPSBhcy5tYXRyaXgoZGF0b3NfZXN0YW5kYXJpemFkb3MpJSolYXMubWF0cml4KGNhcmdhMlsyXSkKZGF0b3NfZXN0YW5kYXJpemFkb3MkQ1AxID0gQ1AxCmRhdG9zX2VzdGFuZGFyaXphZG9zJENQMiA9IENQMgpgYGAKCmBgYHtyIGVjaG89VFJVRX0KZ2diaXBsb3QoZGF0b3MucGMsIG9icy5zY2FsZT0wLjUgLHZhci5zY2FsZT0xLAogICAgICAgICBhbHBoYT0wLjUsZ3JvdXBzPWZhY3RvcihkYXRvc19jb21wbGV0b3Mkc2l0X2FjKSkgKwogIHNjYWxlX2NvbG9yX21hbnVhbChuYW1lPSJzaXR1YWNpb24gYWNhZGVtaWNhIiwgdmFsdWVzPWMoImJsYWNrIiwgInJlZCIsImdyZWVuIiksbGFiZWxzPWMoImN1cnNhbnRlcyIsICJkZXNlcnRvcmVzIiwiZWdyZXNhZG9zIikpICsgIAp0aGVtZShsZWdlbmQuZGlyZWN0aW9uID0iaG9yaXpvbnRhbCIsIGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiKQoKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CmxpYnJhcnkoTUFTUykKZGF0b3NfdHJhaW4gPSBkYXRvc19jb21wbGV0b3NbZGF0b3NfY29tcGxldG9zJHNpdF9hYyAgJWluJSBjKDIsMyksXSAgICAjc2UgcmVhbGl6YSB1biBhbmFsaXNpcyBkaXNjcmltaW5hbnRlIGNvbiBsYXMgY2xhc2VzIDIgeSAzCm1vZGVsb19sZGEgPC0gbGRhKGZvcm11bGEgPSBhcy5mYWN0b3Ioc2l0X2FjKSB+IAogICAgICAgICAgICAgICAgICBlZGFkXzFjICAgICsgbl9tYXRfMWMgKyBuX2ZhbGxhc18xYyAgICsgcHJvbV8xYyAKICAgICAgICAgICAgICAgICsgbl9tYXRfMXkyYyArIG5fZmFsbGFzXzF5MmMgKyBwcm9tXzF5MmMgLCBkYXRhID0gZGF0b3NfdHJhaW4pCm1vZGVsb19sZGEKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiNwcmVkZWNpbW9zIGxhIGNsYXNlIGVuIGJhc2UgYWwgbW9kZWxvIGVudHJlbmFkbyAobyBzZWEsIGNvbW8gc2UgY29tcG9ydGFuIGxvcyBtaXNtb3MgZGF0b3MgdXNhZG9zIHBhcmEgZWwgbW9kZWxvKQpwcmVkX2xkYV90cmFpbiA8LSBwcmVkaWN0KG1vZGVsb19sZGEsZGF0b3NfdHJhaW4pCnRhYmxlKGRhdG9zX3RyYWluJHNpdF9hYywgcHJlZF9sZGFfdHJhaW4kY2xhc3MsIGRubiA9IGMoIkNsYXNlIHJlYWwiLCJDbGFzZSBwcmVkaWNoYSIpKQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KcHJlZF9sZGFfdHJhaW5fMiA9IGlmZWxzZShwcmVkX2xkYV90cmFpbiRwb3N0ZXJpb3JbLDFdPjAuMSwyLDMpICAgICNxdWUgc2lnbmlmaWNhIGVzdGEgbGluZWE/IHF1ZSBlcyBlbCAwLjU/Pwp0YWJsZShkYXRvc190cmFpbiRzaXRfYWMsIHByZWRfbGRhX3RyYWluXzIsIGRubiA9IGMoIkNsYXNlIHJlYWwiLCJDbGFzZSBwcmVkaWNoYSIpKQoKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiNwb3NpYmxlIGludGVudG8gZGUgZW50ZW5kZXIgY29tbyBzZSBjb21wb3J0YSBsYSBjbGFzZSBmcmVudGUgYSBsYXMgdmFyaWFibGVzIG9yaWdpbmFsZXMuCiNTZSBwdWVkZSBoYWNlciBhbGdvIG1lam9yPwpsaWJyYXJ5KGtsYVIpIApwYXJ0aW1hdChhcy5mYWN0b3Ioc2l0X2FjKSB+IGVkYWRfMWMgKyBuX21hdF8xYyArIG5fZmFsbGFzXzFjICsgcHJvbV8xYywgCiAgICAgICAgIGRhdGEgPSBkYXRvc190cmFpbiwgbWV0aG9kID0gImxkYSIsIHByZWMgPSAyMDAsCiAgICAgICAgIGltYWdlLmNvbG9ycyA9IGMoImRhcmtnb2xkZW5yb2QxIiwgInNub3cyIiksY29sLm1lYW4gPSAiZmlyZWJyaWNrIikKCmBgYAoKYGBge3IgZWNobz1UUlVFfQpwcmVkX2xkYV9jb21wbGV0b3MgPC0gcHJlZGljdChtb2RlbG9fbGRhLGRhdG9zX2NvbXBsZXRvcykKCmdnYmlwbG90KGRhdG9zLnBjLCBvYnMuc2NhbGU9MC4xICx2YXIuc2NhbGU9MSwKICAgICAgICAgYWxwaGE9MSxncm91cHM9ZmFjdG9yKHByZWRfbGRhX2NvbXBsZXRvcyRjbGFzcykpICsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZT0icHJlZGljY2lvbiBsZGEiLCB2YWx1ZXM9YygicmVkIiwiZ3JlZW4iKSxsYWJlbHM9YygiZGVzZXJ0b3JlcyIsImVncmVzYWRvcyIpKSArICAKdGhlbWUobGVnZW5kLmRpcmVjdGlvbiA9Imhvcml6b250YWwiLCBsZWdlbmQucG9zaXRpb24gPSAidG9wIikKCmBgYAoKYGBge3IgZWNobz1UUlVFfQoKbW9kZWxvX3FkYSA8LSBxZGEoYXMuZmFjdG9yKHNpdF9hYykgfiAKICAgICAgICAgICAgICAgICAgZWRhZF8xYyAgICArIG5fbWF0XzFjICsgbl9mYWxsYXNfMWMgICArIHByb21fMWMgCiAgICAgICAgICAgICAgICArIG5fbWF0XzF5MmMgKyBuX2ZhbGxhc18xeTJjICsgcHJvbV8xeTJjICwgZGF0YSA9IGRhdG9zX3RyYWluKQptb2RlbG9fcWRhCmBgYAoKYGBge3IgZWNobz1UUlVFfQpwcmVkX3FkYV90cmFpbiA8LSBwcmVkaWN0KG1vZGVsb19xZGEsZGF0b3NfdHJhaW4pCnRhYmxlKGRhdG9zX3RyYWluJHNpdF9hYywgcHJlZF9xZGFfdHJhaW4kY2xhc3MsIGRubiA9IGMoIkNsYXNlIHJlYWwiLCJDbGFzZSBwcmVkaWNoYSIpKQoKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiMgWSBjdWFudG8gZGFiYSBjb24gZWwgbGRhPz8KdGFibGUoZGF0b3NfdHJhaW4kc2l0X2FjLCBwcmVkX2xkYV90cmFpbiRjbGFzcywgZG5uID0gYygiQ2xhc2UgcmVhbCIsIkNsYXNlIHByZWRpY2hhIikpCmBgYAoKYGBge3IgZWNobz1UUlVFfQpsaWJyYXJ5KGNhcmV0KQpjb25mdXNpb25fbGRhID0gY29uZnVzaW9uTWF0cml4KGZhY3RvcihkYXRvc190cmFpbiRzaXRfYWMpLCBwcmVkX2xkYV90cmFpbiRjbGFzcykKY29uZnVzaW9uX2xkYQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KY29uZnVzaW9uX3FkYSA9IGNvbmZ1c2lvbk1hdHJpeChmYWN0b3IoZGF0b3NfdHJhaW4kc2l0X2FjKSwgcHJlZF9xZGFfdHJhaW4kY2xhc3MpCmNvbmZ1c2lvbl9xZGEKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CnByZWRfcWRhX2NvbXBsZXRvcyA8LSBwcmVkaWN0KG1vZGVsb19xZGEsZGF0b3NfY29tcGxldG9zKQoKZ2diaXBsb3QoZGF0b3MucGMsIG9icy5zY2FsZT0wLjUgLHZhci5zY2FsZT0xLAogICAgICAgICBhbHBoYT0xLGdyb3Vwcz1mYWN0b3IocHJlZF9xZGFfY29tcGxldG9zJGNsYXNzKSkgKwogIHNjYWxlX2NvbG9yX21hbnVhbChuYW1lPSJwcmVkaWNjaW9uIHFkYSIsIHZhbHVlcz1jKCJyZWQiLCJncmVlbiIpLGxhYmVscz1jKCJkZXNlcnRvcmVzIiwiZWdyZXNhZG9zIikpICsgIAp0aGVtZShsZWdlbmQuZGlyZWN0aW9uID0iaG9yaXpvbnRhbCIsIGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiKQoKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiNyZWdyZXNpw7NuIGxvZ2lzdGljYQptb2RlbG9fbGcgPC0gZ2xtKGFzLmZhY3RvcihzaXRfYWMpIH4gCiAgICAgICAgICAgICAgICAgIGVkYWRfMWMgICAgKyBuX21hdF8xYyArIG5fZmFsbGFzXzFjICAgKyBwcm9tXzFjIAogICAgICAgICAgICAgICAgKyBuX21hdF8xeTJjICsgbl9mYWxsYXNfMXkyYyArIHByb21fMXkyYyAsIGRhdGEgPSBkYXRvc190cmFpbixmYW1pbHk9Ymlub21pYWwpCm1vZGVsb19sZwoKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CnByZWRfbGdfdHJhaW4gIDwtIHByZWRpY3QobW9kZWxvX2xnLHR5cGUgPSAicmVzcG9uc2UiKQpjbGFzZV9sZ190cmFpbiAgPSBpZmVsc2UocHJlZF9sZ190cmFpbj4wLjUsMSwwKSAgI29qbyBxdWUgZWwgbW9kZWxvIGdlbmVyYSBsYSBjbGFzZSBjb24gMCB5IDEgKG5vIGNvbiAyIHkgMykgIAp0YWJsZShkYXRvc190cmFpbiRzaXRfYWMsIGNsYXNlX2xnX3RyYWluLCBkbm4gPSBjKCJDbGFzZSByZWFsIiwiQ2xhc2UgcHJlZGljaGEiKSkKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiNyZWdyZXNpw7NuIGxvZ2lzdGljYSAyLiBNb2RlbG8gbWFzIHNpbXBsZSBzYWNhbmRvIGxhcyBxdWUgcGFyZWPDrWFuIHRlbmVyIGNvcnJlbGFjacOzbi4KI25vIGVzIGRlc2FibGUgdGVuZXIgbXVsdGljb2xpbmVhbGlkYWQgZGUgdmFyaWFibGVzIHJlZ3Jlc29yYXMuCm1vZGVsbzJfbGcgPC0gZ2xtKGFzLmZhY3RvcihzaXRfYWMpIH4gCiAgICAgICAgICAgICAgICAgIGVkYWRfMWMgICAgKyBuX21hdF8xYyArIG5fZmFsbGFzXzFjICAgKyBwcm9tXzFjICAsIGRhdGEgPSBkYXRvc190cmFpbixmYW1pbHk9Ymlub21pYWwpCm1vZGVsbzJfbGcKCmBgYAoKYGBge3IgZWNobz1UUlVFfQpwcmVkMl9sZ190cmFpbiAgPC0gcHJlZGljdChtb2RlbG8yX2xnLHR5cGUgPSAicmVzcG9uc2UiKQpjbGFzZTJfbGdfdHJhaW4gID0gaWZlbHNlKHByZWQyX2xnX3RyYWluPjAuNSwxLDApICAgICNxdWUgc2lnbmlmaWNhIGVzdGEgbGluZWE/IHF1ZSBlcyBlbCAwLjU/PwoKdGFibGUoZGF0b3NfdHJhaW4kc2l0X2FjLCBjbGFzZTJfbGdfdHJhaW4sIGRubiA9IGMoIkNsYXNlIHJlYWwiLCJDbGFzZSBwcmVkaWNoYSIpKQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI01vZGVsbyBzdXBwb3J0IHZlY3RvciBtYWNoaW5lIHN2bQpsaWJyYXJ5KGUxMDcxKQptb2RlbG9fc3ZtPXN2bShhcy5mYWN0b3Ioc2l0X2FjKX5lZGFkXzFjICAgICsgbl9tYXRfMWMgKyBuX2ZhbGxhc18xYyAgICsgcHJvbV8xYyAKICAgICAgICAgICAgICAgICsgbl9tYXRfMXkyYytuX2ZhbGxhc18xeTJjK3Byb21fMXkyYywKICAgICAgICAgICAgICAgZGF0YT1kYXRvc190cmFpbixtZXRob2Q9IkMtY2xhc3NpZmljYXRpb24iLGtlcm5lbD0icmFkaWFsIixjb3N0PTEwLGdhbW1hPS4xKQpwcmVkX3N2bT1wcmVkaWN0KG1vZGVsb19zdm0sIGRhdG9zX3RyYWluKQp0YWJsZShkYXRvc190cmFpbiRzaXRfYWMsIHByZWRfc3ZtLCBkbm4gPSBjKCJDbGFzZSByZWFsIiwgIkNsYXNlIHByZWRpY2hhIikpCmVycm9yX3N2bTwtIG1lYW4oZGF0b3NfdHJhaW4kc2l0X2FjIT0gcHJlZF9zdm0pICogMTAwCmVycm9yX3N2bQoKYGBgCgpgYGB7cn0KI2NvbXBhcmFjaW9uIGRlIHByZWRpY2Npb25lcyBkZSBkaWZlcmVudGVzIG1vZGVsb3M6CnByZWRpY2Npb25lc192YXJpYXMgPSBjYmluZChwcmVkX2xkYV90cmFpbiRwb3N0ZXJpb3JbLDJdLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJlZF9xZGFfdHJhaW4kcG9zdGVyaW9yWywyXSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByZWRfbGdfdHJhaW4sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBwcmVkMl9sZ190cmFpbikKY29yKHByZWRpY2Npb25lc192YXJpYXMpCgpgYGAKCmBgYHtyfQojYW5hbGlzaXMgZGUgY2x1c3RlcgojZXN0ZSBwcmltZXIgYmxvcXVlIGVzIHNvbG8gcGFyYSBkZWZpbmlyIGZ1bmNpb25lcy4KbGlicmFyeShjbHVzdGVyKQpsaWJyYXJ5KHByYWNtYSkKIyBzZSBkZWZpbmUgZnVuY2lvbiBkZSBlc2NhbGFtaWVudG8gZGlzZmVyZW50ZSBkZSBsYSB0aXBpY2Egbm9ybWFsLgplc2MwMSA8LSBmdW5jdGlvbih4KSB7ICh4IC0gbWluKHgpKSAvIChtYXgoeCkgLSBtaW4oeCkpfSAKIyBzZSBkZWZpbmUgdW5hIGZ1bmNpb24gcGFyYSBjYWxjdWxhciBtZXRyaWNhcyBxdWUgb3JpZW50YW4gc29icmUgZWwgbnVtZXJvIGRlIGNsdXN0ZXJzIGEgZWxlZ2lyIHBhcmEgZWwgcHJvYmxlbWEuCm1ldHJpY2EgPSBmdW5jdGlvbihkYXRBX2VzYyxrbWF4LGYpIHsKICAKICBzaWwgPSBhcnJheSgpCiAgI3NpbF8yID0gYXJyYXkoKQogIHNzZSA9IGFycmF5KCkKICAKICBkYXRBX2Rpc3Q9IGRpc3QoZGF0QV9lc2MsbWV0aG9kID0gImV1Y2xpZGVhbiIsIGRpYWcgPSBGQUxTRSwgdXBwZXIgPSBGQUxTRSwgcCA9IDIpCiAgZm9yICggaSBpbiAgMjprbWF4KSB7CiAgICBpZiAoc3RyY21wKGYsImttZWFucyIpPT1UUlVFKSB7ICAgI2NlbnRyb2lkZTogdGlwaWNvIGttZWFucwogICAgICBDTCAgPSBrbWVhbnMoZGF0QV9lc2MsY2VudGVycz1pLG5zdGFydD01MCxpdGVyLm1heCA9IGttYXgpCiAgICAgIHNzZVtpXSAgPSBDTCR0b3Qud2l0aGluc3MgCiAgICAgIENMX3NpbCA9IHNpbGhvdWV0dGUoQ0wkY2x1c3RlciwgZGF0QV9kaXN0KQogICAgICBzaWxbaV0gID0gc3VtbWFyeShDTF9zaWwpJGF2Zy53aWR0aAogICAgICAgIH0KICAgIGlmIChzdHJjbXAoZiwicGFtIik9PVRSVUUpeyAgICAgICAjbWVkb2lkZTogb2pvIHBvcnF1ZSBlc3RlIG1ldG9kbyB0YXJkYSBtdWNoaXNpbW8gCiAgICAgIENMID0gcGFtKHg9ZGF0QV9lc2MsIGs9aSwgZGlzcyA9IEYsIG1ldHJpYyA9ICJldWNsaWRlYW4iKQogICAgICBzc2VbaV0gID0gQ0wkb2JqZWN0aXZlWzFdIAogICAgICBzaWxbaV0gID0gQ0wkc2lsaW5mbyRhdmcud2lkdGgKICAgICAgfQogIH0KICBzc2UKICBzaWwKICByZXR1cm4oZGF0YS5mcmFtZShzc2Usc2lsKSkKfQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2VuIGVzdGUgYmxvcXVlIHNlIGVzdHVkaWEgY3VhbnRvcyBjbHVzdGVycyBjb252ZW5kcsOtYSBnZW5lcmFyIHJlc3BlY3RvIGEgaW5kaWNhZG9yZXMgdGlwaWNvcyBkZSBDbHVzdGVyaW5nIC0tPiBwb3IgZWplbXBsbyBlbCAiU2lsaG91ZXR0ZSIKa21heCA9IDcKIzIgb3BjaW9uZXMgZGUgZXNjYWxhbWllbnRvCiNtMSAgID0gbWV0cmljYShhcHBseShkYXRvcywyLGVzYzAxKSxrbWF4LCJrbWVhbnMiKSAgICAgICNkZWZpbmlkYSBlbiBsYSBmdW5jaW9uIGVzYzAxCm0xICAgPSBtZXRyaWNhKHNjYWxlKGRhdG9zKSxrbWF4LCJrbWVhbnMiKSAgICAgICAgICAgICAgICN0aXBpY2EgZGUgbGEgbm9ybWFsCgpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2dyYWZpY29zIGRlIGxvcyBpbmRpY2Fkb3JlcyBkZSBjbHVzdGVyaW5nCnBhcihtZnJvdz1jKDIsMSkpCnBsb3QoMjprbWF4LCBtMSRzaWxbMjprbWF4XSxjb2w9MSx0eXBlPSJiIiwgcGNoID0gMTksIGZyYW1lID0gRkFMU0UsIAoJIHhsYWI9Ik51bWJlciBvZiBjbHVzdGVycyBLIiwKCSB5bGFiPSJzaWwiKSAKCnBsb3QoMjprbWF4LCBtMSRzc2VbMjprbWF4XSx0eXBlPSJiIiwgcGNoID0gMTksIGZyYW1lID0gRkFMU0UsIAoJIHhsYWI9Ik51bWJlciBvZiBjbHVzdGVycyBLIiwKCSB5bGFiPSJzc2UiKSAKCnBhcihtZnJvdz1jKDEsMSkpCgpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2VsZWdpbW9zIHJlYWxpemFyIDMgZ3J1cG9zCkNMICA9IGttZWFucyhzY2FsZShkYXRvcyksNSxuc3RhcnQ9NTAsaXRlci5tYXggPSAxMCkKI0NMICA9IGttZWFucyhhcHBseShkYXRvcywyLGVzYzAxKSwzLG5zdGFydD01MCxpdGVyLm1heCA9IDEwKQpkYXRvcyRrbWVhbnMgPSBDTCRjbHVzdGVyCmBgYAoKYGBge3IgZWNobz1UUlVFfQojZW4gY3VhbGVzIDIgdmFyaWFibGVzIG1lIGNvbnZpZW5lIHZpc3VhbGl6YXIgZWwgY2x1c3Rlcj8KcGxvdChkYXRvcyRlZGFkXzFjLGRhdG9zJHByb21fMWMsY29sPWRhdG9zJGttZWFucykrCmdyaWQoKQpgYGAKCmBgYHtyIGVjaG89VFJVRX0KI2NvbnZpZW5lIGVuIHVuIGJpcGxvdCB5YSBxdWUgdGVuZ28gbGFzIGZsZWNoYXMgZGUgbGFzIHZhcmlhYmxlcyBvcmlnaW5hbGVzCmdnYmlwbG90KGRhdG9zLnBjLCBvYnMuc2NhbGU9MSAsdmFyLnNjYWxlPTEsIGFscGhhPTAuNSxncm91cHMgPSBhcy5mYWN0b3IoZGF0b3Mka21lYW5zKSApKwp0aGVtZShsZWdlbmQuZGlyZWN0aW9uID0iaG9yaXpvbnRhbCIsIGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiKQpgYGAKCgpgYGB7ciBlY2hvPVRSVUV9CiNsbyBoYWNlbW9zIGZpbmFsbWVudGUgcGFyYSAzIGdydXBvcyB5IGxvIHZpc3VhbGl6YW1vcyBlbiB1biBiaXBsb3QKQ0wgID0ga21lYW5zKHNjYWxlKGRhdG9zKSwzLG5zdGFydD01MCxpdGVyLm1heCA9IDEwKQpkYXRvcyRrbWVhbnMgPSBDTCRjbHVzdGVyCgpnZ2JpcGxvdChkYXRvcy5wYywgb2JzLnNjYWxlPTEgLHZhci5zY2FsZT0xLCBhbHBoYT0wLjUsZ3JvdXBzID0gYXMuZmFjdG9yKGRhdG9zJGttZWFucykgKSsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZT0iQ2x1c3RlciBrbWVhbnMiLCB2YWx1ZXM9Yygib3JhbmdlIiwgImN5YW4iLCJncmV5IiksbGFiZWxzPWMoImdydXBvIDEiLCAiZ3J1cG8gMiIsImdydXBvIDMiKSkgKyAgCnRoZW1lKGxlZ2VuZC5kaXJlY3Rpb24gPSJob3Jpem9udGFsIiwgbGVnZW5kLnBvc2l0aW9uID0gInRvcCIpCmBgYAoKYGBge3IgZWNobz1UUlVFfQojY2x1c3RlciBqZXLDoXJxdWljbwpkYXRvczI9ZGF0b3NbLC04XSNxdWl0byBjb2x1bW5hICJrbWVhbnMiCmRhdG9zMj1zY2FsZShkYXRvczIpCgojIE1hdHJpeiBkZSBkaXN0YW5jaWFzIGV1Y2zDrWRlYXMgCm1hdF9kaXN0IDwtIGRpc3QoeCA9IGRhdG9zMiwgbWV0aG9kID0gImV1Y2xpZGVhbiIpIAoKIyBEZW5kcm9ncmFtYXMgKHNlZ8O6biBlbCB0aXBvIGRlIHNlZ21lbnRhY2nDs24gamVyw6FycXVpY2EgYXBsaWNhZGEpICAKaGNfY29tcGxldGUgPC0gaGNsdXN0KGQgPSBtYXRfZGlzdCwgbWV0aG9kID0gImNvbXBsZXRlIikgCmhjX2F2ZXJhZ2UgIDwtIGhjbHVzdChkID0gbWF0X2Rpc3QsIG1ldGhvZCA9ICJhdmVyYWdlIikKaGNfc2luZ2xlICAgPC0gaGNsdXN0KGQgPSBtYXRfZGlzdCwgbWV0aG9kID0gInNpbmdsZSIpCmhjX3dhcmQgICAgIDwtIGhjbHVzdChkID0gbWF0X2Rpc3QsIG1ldGhvZCA9ICJ3YXJkLkQyIikKI2NhbGN1bG8gZGVsIGNvZWZpY2llbnRlIGRlIGNvcnJlbGFjaW9uIGNvZmVuZXRpY28KY29yKHggPSBtYXRfZGlzdCwgY29waGVuZXRpYyhoY19jb21wbGV0ZSkpCmNvcih4ID0gbWF0X2Rpc3QsIGNvcGhlbmV0aWMoaGNfYXZlcmFnZSkpCmNvcih4ID0gbWF0X2Rpc3QsIGNvcGhlbmV0aWMoaGNfc2luZ2xlKSkKY29yKHggPSBtYXRfZGlzdCwgY29waGVuZXRpYyhoY193YXJkKSkKYGBgCgpgYGB7ciBlY2hvPVRSVUV9CiMgY29uc3RydWNjaW9uIGRlIHVuIGRlbmRvZ3JhbWEgdXNhbmRvIGxvcyByZXN1bHRhZG9zIGRlIGxhIHTDqWNuaWNhIGRlIFdhcmQKcGxvdChoY193YXJkICkjbm8gc2UgdmUgYmllbiBzaSBoYXkgbXVjaG9zIGRhdG9zCnJlY3QuaGNsdXN0KGhjX3dhcmQsIGs9MywgYm9yZGVyPSJyZWQiKSNjb24gMyBncnVwb3MKZ3J1cG9zPC1jdXRyZWUoaGNfd2FyZCxrPTMpI2NvbiAzIGdydXBvcwojc3BsaXQocm93bmFtZXMoZGF0b3MpLGdydXBvcykjZGV2dWVsdmUgdW5hIGxpc3RhIGNvbiBsYXMgb2JzZXJ2YWNpb25lcyBzZXBhcmFkYXMgcG9yIGdydXBvCmBgYAoKYGBge3IgZWNobz1UUlVFfQojdmlzdWFsaXphbW9zIGNvbiAzIGdydXBvcyBlbCBjbHVzdGVyIGplcmFycXVpY28gZGUgbGEgbWlzbWEgZm9ybWEgcXVlIGttZWFucwpnZ2JpcGxvdChkYXRvcy5wYywgb2JzLnNjYWxlPTEgLHZhci5zY2FsZT0xLCBhbHBoYT0wLjUsZ3JvdXBzID0gYXMuZmFjdG9yKGdydXBvcykgKSsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZT0iQ2x1c3RlciBqZXLDoXJxdWljbyBXYXJkIiwgdmFsdWVzPWMoIm9yYW5nZSIsICJjeWFuIiwiZ3JleSIpLGxhYmVscz1jKCJncnVwbyAxIiwgImdydXBvIDIiLCJncnVwbyAzIikpICsgIAp0aGVtZShsZWdlbmQuZGlyZWN0aW9uID0iaG9yaXpvbnRhbCIsIGxlZ2VuZC5wb3NpdGlvbiA9ICJ0b3AiKQpgYGAKCgoK