1 Foreword:About the Machine Learning in Medicine project

You are reading the 36th case study by MLM team. Our MLM project has been initialized in 2016 and aims to:

  1. Encourage using Machine Learning techniques in medical research in Vietnam

and (2) Promote the use of R statistical programming language, an open source and leading tool for practicing data science.

2 Introduction

In machine learning, ensembling means to combine several base algorithms (learners) for making a stronger algorithm. Such integrated system incorporates the predictions from all individual learners in the best way to provide the final prediction. An ensemble model usually outperforms standalone base learners as brainstorming and teamwork do in our life. The present tutorial provides a hands-on experiment on some basic techniques of ensemble modelling. These include:

Weighted average: this method consists of applying weights on predictions then taking the average of predictions from base learners. Thus, the learners contribute differently to the averaged prediction, depending on their performance.

Majority vote consists of considering the prediction with maximum vote from all base algorithms. This method is strictly applied to classification problem.

Stacking: this method aims to build a multiple layers of models, where the output from the models in the under layers will be used as input for another in superior layer. The top layer model will take final decision.

3 Dataset and study objective

Our study implies a multilabel classification problem that involves the Cardiotocography (CTG) reading in Obstetrics. CTG is a method for monitoring the foetal heart rate (cardio) by ultrasound and its temporal relationship to uterine contractions (toco). This method could be used both before (3rd trimester) and during labour to monitor the baby for any signs of distress. Changes in fetal heart rate that occur along with contractions form a pattern. Certain changes in this pattern may suggest a problem.

A description of the dataset could be found here:

<https://archive.ics.uci.edu/ml/machine-learning-databases/arrhythmia/arrhythmia.names

The original dataset has been created by Ayres de Campos et al. (Faculty of Medicine, University of Porto, Portugal) in 2000 for upgrading a computer program (SisPorto 2.0) for automated analysis of Cardiotocograms. The dataset included 2126 preprocessed fetal cardiotocograms (CTGs). The CTGs were classified by three expert obstetricians and a consensus classification label assigned to each of them.

The 21 features included: baseline values (LBE,LB, which were determined by approximating the mean FHR rounded to increments of 5 beats per minute (bpm) during a 10-minute window, excluding accelerations and decelerations and periods of marked FHR variability (greater than 25 bpm)), accelerations (AC), foetal movement (FM), uterine contractions (UC), percentage of time with abnormal short term variability (ASTV), mean value of short term variability (mSTV), percentage of time with abnormal long term variability (ALTV), mean value of long term variability (mLTV), light decelerations (DL), severe decelerations (DS), prolongued decelerations (DP), repetitive decelerations (DR), histogram width (Width), low freq. of the histogram (Min), high freq. of the histogram (Max), number of histogram peaks (nMax), number of histogram zeros (Nzeroes), histograms’ mode, mean, median, variance and tendency (left assymetric; symmetric, right assymetric).

Clinical objective was to classify 10 morphologic patterns, including: Calm sleep, REM sleep, calm vigilance, active vigilance, shift pattern (A or Susp with shifts), accelerative/decelerative pattern (stress situation), decelerative pattern (vagal stimulation), largely decelerative pattern, flat-sinusoidal pattern (pathological state) and suspect patterns. So, this is a multiclass classification problem The data could be downloaded from:

https://archive.ics.uci.edu/ml/datasets/Cardiotocography#

Reference: Ayres de Campos et al. (2000) SisPorto 2.0 A Program for Automated Analysis of Cardiotocograms. J Matern Fetal Med 5:311-318

Practical objective: The present data experiment aims to explore the utility of 3 ensembling techniques: Weighted averaging, Majority voting and Stacking.

4 Methods

Before being used as input, the original data was cleaned and transformed. The features with no or low variance, as well as high collinearity were removed. Only 15 features remained in the final dataframe. Some of them have been transformed by Yeo-Johnson power transformation in order to optimize their contrast among 10 classes. This dataset was the randomly splited into 2 subsets for training (50%,n=1066) and testing (50%,n=1060). Models’ performance was evaluated by visual confusion matrix, Kappa coefficient and F1 score (for each label).

Our ensembling experiment consisted of 4 steps

  • 1)First, we trained 5 basic classifiers that based on Support vector machine (SVM with linear kernel), k-nearest neighbors (KNN), simple decision tree (CART), One rule (OneR) and Random Forest (Ranger package).

  • 2)We developed the first ensemble model that based on Weighted Averaging principle.

  • 3)In a similar way, we applied the Majority voting principle to make another Ensemble model.

  • 4)Finally, we used Stacking ensemble technique to combine the 5 basic learners under a Gradient boosting machine learner.

The caret package (Max Kuhn, 2012) was used through out our experiment. All 3 ensembling procedures were manually performed using customized loops and functions in R. We also introduced 2 functions for visualizing the confusion matrix and the performance for multilabel classifier.

5 Data preparation and exploration

First, we will prepare the ggplot theme for our experiment

library(tidyverse)

my_theme <- function(base_size = 5, base_family = "sans"){
  theme_minimal(base_size = base_size, base_family = base_family) +
    theme(
      axis.text = element_text(size = 5),
      axis.text.x = element_text(angle = 0, vjust = 0.5, hjust = 0.5),
      axis.title = element_text(size = 5),
      panel.grid.major = element_line(color = "grey"),
      panel.grid.minor = element_blank(),
      panel.background = element_rect(fill = "white"),
      strip.background = element_rect(fill = "#4f0870", color = "#4f0870", size =0.5),
      strip.text = element_text(face = "bold", size =5, color = "white"),
      legend.position = "bottom",
      legend.justification = "center",
      legend.background = element_blank(),
      panel.border = element_rect(color = "grey30", fill = NA, size = 0.5)
    )
}
theme_set(my_theme())

mycol=c("#ff0048","#fce628","#0de2aa","#2dd6e2","#c362f7","#ffae22","#b1e827","#3495ea","#ac9af9","#ff51c5")

Now we load the dataset into R:

#load data

df=read.csv("Cardiotocography.csv",sep=";")%>%.[,-c(21:31)]%>%.[,-22]

df[c(1:20)] <- lapply(df[c(1:20)], as.numeric)

df$CLASS=recode_factor(df$CLASS,`1` = "CalmSleep", `2` = "REM",`3` = "CalmVig",`4` = "ActVig", `5` = "Shiftpattern",`6` = "AD",`7` = "DE", `8` = "LD",`9` = "Flatsinusoidal",`10` = "Suspect")

df$CLASS=as.factor(df$CLASS)

head(df)%>%knitr::kable()
LB AC FM UC DL DS DP ASTV MSTV ALTV MLTV Width Min Max Nmax Nzeros Mode Mean Median Variance CLASS
120 0.000 0 0.000 0.000 0 0.000 73 0.5 43 2.4 64 62 126 2 0 120 137 121 73 Flatsinusoidal
132 0.006 0 0.006 0.003 0 0.000 17 2.1 0 10.4 130 68 198 6 1 141 136 140 12 AD
133 0.003 0 0.008 0.003 0 0.000 16 2.1 0 13.4 130 68 198 5 1 141 135 138 13 AD
134 0.003 0 0.008 0.003 0 0.000 16 2.4 0 23.0 117 53 170 11 0 137 134 137 13 AD
132 0.007 0 0.008 0.000 0 0.000 16 2.4 0 19.9 117 53 170 9 0 137 136 138 11 REM
134 0.001 0 0.010 0.009 0 0.002 26 5.9 0 0.0 150 50 200 5 3 76 107 107 170 LD

6 Data cleaning, Visualisation and Transformations

df%>%gather(LB:Variance,key="Feature",value="Value")%>%ggplot(aes(x=Value,fill=CLASS))+geom_density(color="black",alpha=0.4,show.legend = T)+facet_wrap(~Feature,drop = TRUE,ncol=5,scales="free")+my_theme(5)+scale_fill_manual(values=mycol)+ggtitle("Original data: Density curves")

The density plots can tell us two things:

  • Some features seem to be equivalent (for example: Mean, Mode and Median) as their distribution densities were almost identical.

  • Some features had abnormal distribution (as they are count data). A transformation might be needed in order to improve the contrast of their value amongst 10 classes. These include: AC, ALTV, DL, DP, DB, MLTV, MBTV, Nmax,Nzeros,UC and Variance.

Therefore, we will apply a transformation to our data. This transformation consists of:

  • Removing the features with no or low variance, as they will not contribute to our prediction.
  • Applying systematically a Yeo-Johnson transformation to features that have skewed distribution
  • Filtering the features with high colinearity
library(caret)

YJT=preProcess(df[,-21],method=c("nzv", "conditionalX","YeoJohnson","corr"))
YJTdata=predict(YJT,newdata=df[,-21])%>%mutate(.,CLASS=df$CLASS)
  
head(YJTdata)%>%knitr::kable()
LB AC FM UC DL ASTV MSTV MLTV Width Min Max Nmax Nzeros Mode Variance CLASS
70.66978 0.0000000 0 0.0000000 0.0000000 37.79783 0.3656240 1.667680 14.78483 11.93782 1.302152 1.258806 0.0000000 140263.93 3.786020 Flatsinusoidal
76.75360 0.0036132 0 0.0055709 0.0017965 11.36043 0.8555929 4.631112 22.07718 12.52325 1.312364 2.486427 0.2093696 215262.77 2.374588 AD
77.25702 0.0022980 0 0.0072499 0.0017965 10.79710 0.8555929 5.430553 22.07718 12.52325 1.312364 2.243921 0.2093696 215262.77 2.437832 AD
77.75991 0.0022980 0 0.0072499 0.0017965 10.79710 0.9057134 7.526446 20.81537 10.99830 1.309291 3.409286 0.0000000 199414.11 2.437832 AD
76.75360 0.0039122 0 0.0072499 0.0000000 10.79710 0.9057134 6.907120 20.81537 10.99830 1.309291 3.083532 0.0000000 199414.11 2.305958 REM
77.75991 0.0009123 0 0.0088473 0.0025659 16.18889 1.2194202 0.000000 23.90556 10.66597 1.312555 2.243921 0.2181477 41837.61 4.414257 LD

After transformation, our dataset contains only 15 features (so 5 features have been removed from the original data, due to low variance or colinearity).

We visualise again the data:

YJTdata%>%gather(LB:Variance,key="Feature",value="Value")%>%ggplot(aes(x=Value,fill=CLASS))+geom_density(color="black",alpha=0.4)+facet_wrap(~Feature,drop = TRUE,ncol=5,scales="free")+my_theme(5)+scale_fill_manual(values=mycol)+ggtitle("Transformed data: Density curves")

As we could see, the Yeo_johnson transformation has corrected as best as it could the abnormal skewness in AC, FM, DL, Nzeores, Width, UC and Variance. After being transformed, those variables show better contrasts. However, such transformation might not be required for ASTV, LB,Min and Max.

Though the transformation automatically removed DP and DB due to low variance, we saw that the DP in raw value showed at least a contrast between 2/10 classes, so we will keep this feature.

We decide to build the final dataset as follows:

features in Raw values: ASTV, LB,Min and Max Among Mean, Mode and Median: only 1 is needed. We decide to keep raw Median Between DP and DB: only one is needed and in raw value, we choose DP Other variables would be in transformed value: MLTV, MSTV,Nmax,Nzero,Variance,Width,UC and DL

rawval=c("ASTV","LB","Min","Max","Median","DP")
yjval=c("MLTV","MSTV","Nmax","Nzero","Variance","Width","UC","DL","FM","AC")

data=cbind(df[,(names(df) %in% rawval)],YJTdata[,(names(YJTdata) %in% yjval)])%>%mutate(.,CLASS=df$CLASS)

rm(YJTdata,df,rawval,yjval,YJT)

Our final dataset contains 15 features and could be visualised as below:

data%>%gather(LB:Variance,key="Feature",value="Value")%>%ggplot(aes(x=Value,fill=CLASS))+geom_density(color="black",alpha=0.4)+facet_wrap(~Feature,drop = TRUE,ncol=3,scales="free")+my_theme(5)+scale_fill_manual(values=mycol)+ggtitle("Cleaned and transformed data")

data%>%gather(LB:Variance,key="Feature",value="Value")%>%ggplot(aes(x=CLASS,y=Value,fill=CLASS))+geom_violin(color="black",alpha=0.7)+facet_wrap(~Feature,drop = TRUE,ncol=3,scales="free")+my_theme(5)+scale_fill_manual(values=mycol)+ggtitle("Cleaned and transformed data")

This dataset will be randomly splitted to Train and test subsets:

set.seed(1234)

idTrain=createDataPartition(y=data$CLASS,p=0.5,list=FALSE)
trainset=data[idTrain,]
testset=data[-idTrain,]

A correlation matrix that shows the association pattern among 15 features in our train subset:

library(corrplot)
library(RColorBrewer)

cor_mat=as.matrix(cor(method="spearman",as.matrix(trainset[,c(1:15)])))

cor_mat%>%corrplot(.,order="hclust",type="lower",method="color",tl.col="black", tl.srt=45,tl.cex=0.6,col=rev(brewer.pal(n=10, name="Spectral")))

It’s another matrix that shows the distribution of the classes from different bidimensional viewpoints

plotfuncmid <- function(data,mapping){
  p <- ggplot(data = data,mapping=mapping)+geom_density(aes(fill=data$CLASS),alpha=0.5,color="black")+scale_fill_manual(values=mycol)+scale_color_manual(values=mycol)
  p
}

plotfuncLow <- function(data,mapping){
  p <- ggplot(data = data,mapping=mapping)+stat_density2d(geom="polygon",aes(fill=data$CLASS,alpha = ..level..))+scale_fill_manual(values=mycol)
  p
}

plotfuncUp <- function(data,mapping){
  p <- ggplot(data = data,mapping=mapping)+geom_smooth(method="lm",se=FALSE,alpha=0.6,aes(color=data$CLASS))+scale_fill_manual(values=mycol)
  p
}


library(GGally)

ggpairs(data,columns=1:15,lower=list(continuous=plotfuncLow),diag=list(continuous=plotfuncmid),upper = list(continuous=plotfuncUp))

7 Training 5 base learners

The first step in our experiment consists of training 5 different base learners. These include: SVM, CART, KNN, OneR and Random Forest.

#5 models

Control=trainControl(method="repeatedcv",number=10,repeats=10,classProbs=TRUE,summaryFunction=multiClassSummary,savePredictions ="final")

#1) SVM

set.seed(1234)

svmod=train(CLASS~.,data=trainset,method = "svmLinear2",trControl=Control,tuneLength=5)

predsvm=predict(svmod,newdata=testset)
cm1=confusionMatrix(predsvm,testset$CLASS)

#2) CART

set.seed(666)

cartmod=train(CLASS~.,data=trainset,method = "rpart",trControl=Control,tuneLength=5)

predcart=predict(cartmod,newdata=testset)
cm2=confusionMatrix(predcart,testset$CLASS)

#3) KNN

set.seed(333)

knnmod=train(CLASS~.,data=trainset,method = "knn",trControl=Control,tuneLength=5)

predknn=predict(knnmod,newdata=testset)
cm3=confusionMatrix(predknn,testset$CLASS)

#4) 1R

set.seed(333)

ormod=train(CLASS~.,data=trainset,method = "OneR",trControl=Control,tuneLength=5)

predor=predict(ormod,newdata=testset)
cm4=confusionMatrix(predor,testset$CLASS)

#5) rang

set.seed(333)

rgmod=train(CLASS~.,data=trainset,method = "ranger",trControl=Control)

predrg=predict(rgmod,newdata=testset)
cm5=confusionMatrix(predrg,testset$CLASS)

Because our problem is complexe, as we have 10 classes to classify, we would like to represent our confusion matrix and model performance in graphs. Here is the solutions:

multiclasscmplot=function(modelobj,testdf,target,modelname){
  predt=predict(modelobj,newdata=testdf)
  cm=caret::confusionMatrix(predt,testdf[,target])
  
  cmt=cm$table%>%as_tibble()
  
  freq=Hmisc::describe(testdf[,target])%>%.$values%>%.$frequency
  labels=row.names(cm$table)
  
  k=1
  cmt$rate=cmt$n/1
  for(i in 1:10){
    for(k in 1:100){
      if(cmt$Reference[k]==labels[i]){
        cmt$rate[k]<-100*(cmt$n[k]/freq[i])
        k=k+1
      }
      else{k=k}
    }
  }
  
  cmt%>%ggplot(aes(x=Prediction,y=Reference,fill=rate))+
    geom_tile(color="black")+my_theme(10)+
    scale_fill_gradient2(low="white",mid="#008cff",high="#ff0059",midpoint=50)+
    theme(axis.text.x = element_text(angle =45, hjust = 0.5))+
    ggtitle(modelname)+
    geom_text(aes(y=Reference,x=Prediction,label=round(rate,1)),color="black",size=3)+coord_fixed()
}
multiclasscmplot(modelobj=svmod,testdf=testset,target="CLASS",modelname="SVM")

multiclasscmplot(modelobj=cartmod,testdf=testset,target="CLASS",modelname="CART")

multiclasscmplot(modelobj=ormod,testdf=testset,target="CLASS",modelname="One_R")

multiclasscmplot(modelobj=knnmod,testdf=testset,target="CLASS",modelname="KNN")

multiclasscmplot(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RandomForest")

multiclasscmsum=function(modelobj,testdf,target,modelname,lowcol,highcol){
  
  predt=predict(modelobj,newdata=testdf)
  cm=caret::confusionMatrix(predt,testdf[,target])
  
  sum=cm$byClass%>%as_tibble()%>%.[,c(7,11)]%>%mutate(.,Labels=row.names(cm$table))
  sum%>%ggplot(aes(x=reorder(Labels,F1),y=F1))+
    geom_bar(aes(fill=F1),stat="identity",color="black")+
    coord_flip()+
    geom_text(aes(label=round(F1,2)),hjust=1,size=5,color="white")+ggtitle(paste(modelname,"/ F1 score"))+
    scale_fill_gradient(low=lowcol,high=highcol)
  }
multiclasscmsum(modelobj=svmod,testdf=testset,target="CLASS",modelname="SVM",lowcol="#c94be5",highcol="#ff0066")

multiclasscmsum(modelobj=knnmod,testdf=testset,target="CLASS",modelname="KNN",lowcol="#c94be5",highcol="#ff0066")

multiclasscmsum(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RF",lowcol="#c94be5",highcol="#ff0066")

multiclasscmsum(modelobj=ormod,testdf=testset,target="CLASS",modelname="ONER",lowcol="#c94be5",highcol="#ff0066")

multiclasscmsum(modelobj=cartmod,testdf=testset,target="CLASS",modelname="CART",lowcol="#c94be5",highcol="#ff0066")

Based on the confusion matrices and F1 score graphs, we can see that the best model was Random Forest, the second best was SVM. OneR and Decision tree (CART) were weak, both of them failed to classify correctly the pathological patterns among 10 target labels. The KNN was better than CART or OneR but this base learner cannot assure the correct prediction of all 10 labels.

8 First ensemble rule: Weighted average

Our fist ensemble model applies a simple principle of weighted average. As mentioned above, we found that the RF and SVM were two best models for the prediction, so we will assign higher weights for those two models (0.45 and 0.3, respectively). In contrast, KNN and CART were weak, and OneR was the worst, so we assign a lower weights to them (0.1 for KNN and CART, 0.01 to OneR). Then we combine those 5 predicted probabilities together to make a new prediction. The label with highest probability among 10 will be taken as the final prediction.

pred1=predict(svmod,newdata=testset,type="prob")
pred1=pred1*0.30
pred1=pred1%>%as_tibble()%>%mutate(.,Model="SVM")

pred2=predict(rgmod,newdata=testset,type="prob")
pred2=pred2*0.45
pred2=pred2%>%as_tibble()%>%mutate(.,Model="RF")

pred3=predict(knnmod,newdata=testset,type="prob")
pred3=pred3*0.1
pred3=pred3%>%as_tibble()%>%mutate(.,Model="KNN")

pred4=predict(ormod,newdata=testset,type="prob")
pred4=pred4*0.01
pred4=pred4%>%as_tibble()%>%mutate(.,Model="ONER")

pred5=predict(cartmod,newdata=testset,type="prob")
pred5=pred5*0.1
pred5=pred5%>%as_tibble()%>%mutate(.,Model="CART")

predt=pred1[,-11]
predt[,]<-NA
Labels=colnames(predt)

for(i in 1:1060){
  for (j in 1:10){
    predt[i,j]=pred1[i,j]+pred2[i,j]+pred3[i,j]+pred4[i,j]+pred5[i,j]
  }
}
  
predt$Predict=rep(NA,1060)


k=1
for(i in 1:1060){
  for(k in 1:10){
    if(is.na(predt$Predict[i])){
  maxprob=max(predt[i,c(1:10)])
  predt$Predict[i]<-ifelse(predt[i,k]==maxprob,Labels[k],NA)
  k=k+1
    }
    else{(k=k)
}
  }
}

We will also create two functions for plotting the confusion matrix and F1 scores for our Ensemble predictions:

ensemblecmplot=function(vote,truth){
  cm=confusionMatrix(reference = truth,vote)
  cmt=cm$table%>%as_tibble()
  freq=Hmisc::describe(truth)%>%.$values%>%.$frequency
  labels=row.names(cm$table)
  
  k=1
  cmt$rate=cmt$n/1
  for(i in 1:10){
    for(k in 1:100){
      if(cmt$Reference[k]==labels[i]){
        cmt$rate[k]<-100*(cmt$n[k]/freq[i])
        k=k+1
      }
      else{k=k}
    }
  }
  
  cmt%>%ggplot(aes(x=Prediction,y=Reference,fill=rate))+
    geom_tile(color="black")+my_theme(10)+
    scale_fill_gradient2(low="white",mid="#008cff",high="#ff0059",midpoint=50)+
    theme(axis.text.x = element_text(angle =45, hjust = 0.5))+
    ggtitle("Ensemble")+
    geom_text(aes(y=Reference,x=Prediction,label=round(rate,1)),color="black",size=3)+coord_fixed()
}
p1=ensemblecmplot(vote=predt$Predict,truth=testset$CLASS)+ggtitle("Weighted averaging")
p2=multiclasscmplot(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RandomForest")

gridExtra::grid.arrange(p1,p2,ncol=2)

The confusion matrix of Weighted averaged prediction was better than that obtained by Random Forest but not for all patterns. The averaged prediction was improved for Shiftpattern, REM, Flatsinusoidal, DE, CalmSleep and ActVigilence; however it was unchanged for Suspect,AD and LD, and did worst for Calm vigilence. However we could say that the Ensemble model did imporve the accuracy of prediction.

ensemblecmsum=function(vote,truth,lowcol,highcol){
  
  cm=confusionMatrix(reference = truth,vote)
  
  sum=cm$byClass%>%as_tibble()%>%.[,c(7,11)]%>%mutate(.,Labels=row.names(cm$table))
  sum%>%ggplot(aes(x=reorder(Labels,F1),y=F1))+
    geom_bar(aes(fill=F1),stat="identity",color="black")+
    coord_flip()+
    geom_text(aes(label=round(F1,2)),hjust=1,size=5,color="white")+ggtitle(paste("Ensemble"))+
    scale_fill_gradient(low=lowcol,high=highcol)
}
p1=ensemblecmsum(vote=predt$Predict,truth=testset$CLASS,lowcol="#c94be5",highcol="#ff0066")+ggtitle("Weighted averaging")
p2=multiclasscmsum(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RF",lowcol="#c94be5",highcol="#ff0066")

gridExtra::grid.arrange(p1,p2,ncol=2)

Based on F1 score per class, the Weighted average prediction performs better than the best individual model which was Random Forest.

9 Second ensemble rule: Majority Voting

The second Ensemble method consists of considering the highest number of votes by 5 individual models to make the final decision. We made a loop for doing this manually. Note that majority vote among 5 learners means that at least 3 learners gave the same prediction for a target label. If the majority cannot be reached, we will assign systematically the prediction by the strongest model which is Random Forest.

pdf=data.frame(RF=predrg,SVM=predsvm,KNN=predknn,ONER=predor,CART=predcart)

labels=row.names(cm1$table)

predt=rep(NA,1060)

k=1

for(i in 1:10){
  for(k in 1:1060){
    if(is.na(predt[k])){
      predt[[k]]<-ifelse(pdf$RF[k]==labels[i] & pdf$SVM[k]==labels[i] & pdf$KNN[k]==labels[i],labels[i],
                 ifelse(pdf$RF[k]==labels[i] & pdf$SVM[k]==labels[i] & pdf$ONER[k]==labels[i],labels[i],
                 ifelse(pdf$RF[k]==labels[i] & pdf$SVM[k]==labels[i] & pdf$CART[k]==labels[i],labels[i],
                 ifelse(pdf$RF[k]==labels[i] & pdf$KNN[k]==labels[i] & pdf$ONER[k]==labels[i],labels[i],
                 ifelse(pdf$RF[k]==labels[i] & pdf$KNN[k]==labels[i] & pdf$CART[k]==labels[i],labels[i],
                 ifelse(pdf$RF[k]==labels[i] & pdf$ONER[k]==labels[i] & pdf$CART[k]==labels[i],labels[i],
                 ifelse(pdf$SVM[k]==labels[i] & pdf$KNN[k]==labels[i] & pdf$ONER[k]==labels[i],labels[i],
                 ifelse(pdf$SVM[k]==labels[i] & pdf$KNN[k]==labels[i] & pdf$CART[k]==labels[i],labels[i],
                 ifelse(pdf$KNN[k]==labels[i] & pdf$CART[k]==labels[i] & pdf$ONER[k]==labels[i],labels[i],NA
                                      )))))))))
      k=k+1}
    else{k=k}
  }
}

for(k in 1:1060){
  if(is.na(predt[[k]])){predt[[k]]<-as.vector(pdf$RF[[k]])
  k=k+1
  }
}

pdf$Majority=as.vector(predt)
pdf$Truth=testset$CLASS
p1=ensemblecmplot(vote=pdf$Majority,truth=pdf$Truth)
p2=multiclasscmplot(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RandomForest")

gridExtra::grid.arrange(p1,p2,ncol=2)

p1=ensemblecmsum(vote=pdf$Majority,truth=pdf$Truth,lowcol="red",highcol="purple")
p2=multiclasscmsum(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RF",lowcol="#c94be5",highcol="#ff0066")
gridExtra::grid.arrange(p1,p2,ncol=2)

Overall, the ensemble prediction that based on Majority vote is worst than that by Weighted average method, and worst than that by the stand alone Random Forest model.

10 The third ensmble model: GBM Stacking

The 3rd Ensemble method consists of using the output of 5 individual models as the input of a top layer model which is a GBM learner. In brief, we will generate new trainsubset and new testsubset that incorporate the predicted probabilities of 10 labels x 5 models = 50 new input features for training and testing a GBM model.

#TRAINPRED

pred1=predict(svmod,newdata=trainset,type="prob")%>%as_tibble()
colnames(pred1)<-paste(Labels,1,sep="_")

pred2=predict(rgmod,newdata=trainset,type="prob")%>%as_tibble()
colnames(pred2)<-paste(Labels,2,sep="_")

pred3=predict(knnmod,newdata=trainset,type="prob")%>%as_tibble()
colnames(pred3)<-paste(Labels,3,sep="_")

pred4=predict(ormod,newdata=trainset,type="prob")%>%as_tibble()
colnames(pred4)<-paste(Labels,4,sep="_")

pred5=predict(cartmod,newdata=trainset,type="prob")%>%as_tibble()
colnames(pred5)<-paste(Labels,5,sep="_")

trainstackdf=cbind(pred1,pred2,pred3,pred4,pred5)%>%mutate(.,CLASS=trainset$CLASS)

#TESTPRED

pred1=predict(svmod,newdata=testset,type="prob")%>%as_tibble()
colnames(pred1)<-paste(Labels,1,sep="_")

pred2=predict(rgmod,newdata=testset,type="prob")%>%as_tibble()
colnames(pred2)<-paste(Labels,2,sep="_")

pred3=predict(knnmod,newdata=testset,type="prob")%>%as_tibble()
colnames(pred3)<-paste(Labels,3,sep="_")

pred4=predict(ormod,newdata=testset,type="prob")%>%as_tibble()
colnames(pred4)<-paste(Labels,4,sep="_")

pred5=predict(cartmod,newdata=testset,type="prob")%>%as_tibble()
colnames(pred5)<-paste(Labels,5,sep="_")

teststackdf=cbind(pred1,pred2,pred3,pred4,pred5)%>%mutate(.,CLASS=testset$CLASS)
#Stacking GBM

set.seed(1234)
Control2=trainControl(method="repeatedcv",number=5,repeats=5,classProbs=TRUE,summaryFunction=multiClassSummary)

stackGBM<-train(CLASS~.,data=trainstackdf,method='gbm',trControl=Control2,tuneLength=3)

predSTKGBM=predict(stackGBM,newdata=teststackdf)

cmstk=confusionMatrix(predSTKGBM,teststackdf$CLASS)
p1=ensemblecmplot(vote=predSTKGBM,truth=teststackdf$CLASS)+ggtitle("GBM Stacking")

p2=multiclasscmplot(modelobj=rgmod,testdf=testset,target="CLASS",modelname="RandomForest")

gridExtra::grid.arrange(p1,p2,ncol=2)

ensemblecmsum(vote=predSTKGBM,truth=teststackdf$CLASS,lowcol="gold",highcol="red")+ggtitle("GBM Stacking")

Yes, as you could see: the two layers Stacking ensemble model did a very good job, it could perform even better than a standalone Random Forest model.

10.1 Conclusion

Ensembling is a simple but effective approach to improve the performance of weak base algorithms. In most situations, an ensemble model work better than a standalone learner. Ensembling offers robustness and stability for both classification and regression tasks, even the complex problem likes the multilabel classification in our study.

However, an ensemble model might be not necessary if you already have a strong learner likes Random Forest or GBM among base learners. In fact, Random Forest and GBM are also Ensemble models that correspond to Bagging and Boosting algorithms, respectively.

There are some disadvantages of Ensemble modelling; as this process is time consuming and makes the model very difficult to interpret. By consequence, ensembling is not a good choice for interpretive studies and real time analyzing tasks.

Thank you for joining us and see you in the next tutorial.

LS0tDQp0aXRsZTogIk1MTSBDYXNlIHN0dWR5IFgxNiINCnN1YnRpdGxlOiAiRW5zZW1ibGUgbW9kZWxsaW5nIg0KYXV0aG9yOiAiTGUgRG9uZyBOaGF0IE5hbSAoTUQsIFBoRCkiDQpkYXRlOiAiSnVseSAwNSwgMjAxNyINCm91dHB1dDogDQogIGh0bWxfZG9jdW1lbnQ6IA0KICAgIGNvZGVfZG93bmxvYWQ6IHRydWUNCiAgICBjb2RlX2ZvbGRpbmc6IGhpZGUNCiAgICBudW1iZXJfc2VjdGlvbnM6IHllcw0KICAgIHRoZW1lOiBqb3VybmFsDQogICAgZGZfcHJpbnQ6IGthYmxlDQogICAgdG9jOiBUUlVFDQogICAgdG9jX2Zsb2F0OiBUUlVFDQotLS0NCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUsIGVycm9yID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFKQ0KDQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkobWF0cml4U3RhdHMpDQpsaWJyYXJ5KGNvcnJwbG90KQ0KbGlicmFyeShSQ29sb3JCcmV3ZXIpDQpsaWJyYXJ5KGNhcmV0KQ0KDQpgYGANCg0KIVtdKGVuc2VtYmxpbmcucG5nKQ0KDQojIEZvcmV3b3JkOkFib3V0IHRoZSBNYWNoaW5lIExlYXJuaW5nIGluIE1lZGljaW5lIHByb2plY3QgDQoNCllvdSBhcmUgcmVhZGluZyB0aGUgMzZ0aCBjYXNlIHN0dWR5IGJ5IE1MTSB0ZWFtLiBPdXIgTUxNIHByb2plY3QgaGFzIGJlZW4gaW5pdGlhbGl6ZWQgaW4gMjAxNiBhbmQgYWltcyB0bzoNCg0KKDEpIEVuY291cmFnZSB1c2luZyBNYWNoaW5lIExlYXJuaW5nIHRlY2huaXF1ZXMgaW4gbWVkaWNhbCByZXNlYXJjaCBpbiBWaWV0bmFtDQoNCmFuZCAoMikgUHJvbW90ZSB0aGUgdXNlIG9mIFIgc3RhdGlzdGljYWwgcHJvZ3JhbW1pbmcgbGFuZ3VhZ2UsIGFuIG9wZW4gc291cmNlIGFuZCBsZWFkaW5nIHRvb2wgZm9yIHByYWN0aWNpbmcgZGF0YSBzY2llbmNlLg0KICAgIA0KIyBJbnRyb2R1Y3Rpb24NCg0KSW4gbWFjaGluZSBsZWFybmluZywgZW5zZW1ibGluZyBtZWFucyB0byBjb21iaW5lIHNldmVyYWwgYmFzZSBhbGdvcml0aG1zIChsZWFybmVycykgZm9yIG1ha2luZyBhIHN0cm9uZ2VyIGFsZ29yaXRobS4gU3VjaCBpbnRlZ3JhdGVkIHN5c3RlbSBpbmNvcnBvcmF0ZXMgdGhlIHByZWRpY3Rpb25zIGZyb20gYWxsIGluZGl2aWR1YWwgbGVhcm5lcnMgaW4gdGhlIGJlc3Qgd2F5IHRvIHByb3ZpZGUgdGhlIGZpbmFsIHByZWRpY3Rpb24uIEFuIGVuc2VtYmxlIG1vZGVsIHVzdWFsbHkgb3V0cGVyZm9ybXMgc3RhbmRhbG9uZSBiYXNlIGxlYXJuZXJzIGFzIGJyYWluc3Rvcm1pbmcgYW5kIHRlYW13b3JrIGRvIGluIG91ciBsaWZlLiANClRoZSBwcmVzZW50IHR1dG9yaWFsIHByb3ZpZGVzIGEgaGFuZHMtb24gZXhwZXJpbWVudCBvbiBzb21lIGJhc2ljIHRlY2huaXF1ZXMgb2YgZW5zZW1ibGUgbW9kZWxsaW5nLiBUaGVzZSBpbmNsdWRlOiANCg0KV2VpZ2h0ZWQgYXZlcmFnZTogdGhpcyBtZXRob2QgY29uc2lzdHMgb2YgYXBwbHlpbmcgd2VpZ2h0cyBvbiBwcmVkaWN0aW9ucyB0aGVuIHRha2luZyB0aGUgYXZlcmFnZSBvZiBwcmVkaWN0aW9ucyBmcm9tIGJhc2UgbGVhcm5lcnMuIFRodXMsIHRoZSBsZWFybmVycyBjb250cmlidXRlIGRpZmZlcmVudGx5IHRvIHRoZSBhdmVyYWdlZCBwcmVkaWN0aW9uLCBkZXBlbmRpbmcgb24gdGhlaXIgcGVyZm9ybWFuY2UuIA0KDQpNYWpvcml0eSB2b3RlIGNvbnNpc3RzIG9mIGNvbnNpZGVyaW5nIHRoZSBwcmVkaWN0aW9uIHdpdGggbWF4aW11bSB2b3RlIGZyb20gYWxsIGJhc2UgYWxnb3JpdGhtcy4gVGhpcyBtZXRob2QgaXMgc3RyaWN0bHkgYXBwbGllZCB0byBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtLg0KDQpTdGFja2luZzogdGhpcyBtZXRob2QgYWltcyB0byBidWlsZCBhIG11bHRpcGxlIGxheWVycyBvZiBtb2RlbHMsIHdoZXJlIHRoZSBvdXRwdXQgZnJvbSB0aGUgbW9kZWxzIGluIHRoZSB1bmRlciBsYXllcnMgd2lsbCBiZSB1c2VkIGFzIGlucHV0IGZvciBhbm90aGVyIGluIHN1cGVyaW9yIGxheWVyLiBUaGUgdG9wIGxheWVyIG1vZGVsIHdpbGwgdGFrZSBmaW5hbCBkZWNpc2lvbi4NCg0KIVtdKGhlcm90ZWFtLnBuZykNCg0KIyBEYXRhc2V0IGFuZCBzdHVkeSBvYmplY3RpdmUNCg0KT3VyIHN0dWR5IGltcGxpZXMgYSBtdWx0aWxhYmVsIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0gdGhhdCBpbnZvbHZlcyB0aGUgQ2FyZGlvdG9jb2dyYXBoeSAoQ1RHKSByZWFkaW5nIGluIE9ic3RldHJpY3MuIENURyBpcyBhIG1ldGhvZCBmb3IgbW9uaXRvcmluZyB0aGUgZm9ldGFsIGhlYXJ0IHJhdGUgKGNhcmRpbykgYnkgdWx0cmFzb3VuZCBhbmQgaXRzIHRlbXBvcmFsIHJlbGF0aW9uc2hpcCB0byB1dGVyaW5lIGNvbnRyYWN0aW9ucyAodG9jbykuIFRoaXMgbWV0aG9kIGNvdWxkIGJlIHVzZWQgYm90aCBiZWZvcmUgKDNyZCB0cmltZXN0ZXIpIGFuZCBkdXJpbmcgbGFib3VyIHRvIG1vbml0b3IgdGhlIGJhYnkgZm9yIGFueSBzaWducyBvZiBkaXN0cmVzcy4gQ2hhbmdlcyBpbiBmZXRhbCBoZWFydCByYXRlIHRoYXQgb2NjdXIgYWxvbmcgd2l0aCBjb250cmFjdGlvbnMgZm9ybSBhIHBhdHRlcm4uIENlcnRhaW4gY2hhbmdlcyBpbiB0aGlzIHBhdHRlcm4gbWF5IHN1Z2dlc3QgYSBwcm9ibGVtLg0KDQpBIGRlc2NyaXB0aW9uIG9mIHRoZSBkYXRhc2V0IGNvdWxkIGJlIGZvdW5kIGhlcmU6IA0KDQo8aHR0cHM6Ly9hcmNoaXZlLmljcy51Y2kuZWR1L21sL21hY2hpbmUtbGVhcm5pbmctZGF0YWJhc2VzL2Fycmh5dGhtaWEvYXJyaHl0aG1pYS5uYW1lcw0KDQohW10odG9jbzIucG5nKQ0KDQpUaGUgb3JpZ2luYWwgZGF0YXNldCBoYXMgYmVlbiBjcmVhdGVkIGJ5IEF5cmVzIGRlIENhbXBvcyBldCBhbC4gKEZhY3VsdHkgb2YgTWVkaWNpbmUsIFVuaXZlcnNpdHkgb2YgUG9ydG8sIFBvcnR1Z2FsKSBpbiAyMDAwIGZvciB1cGdyYWRpbmcgYSBjb21wdXRlciBwcm9ncmFtIChTaXNQb3J0byAyLjApIGZvciBhdXRvbWF0ZWQgYW5hbHlzaXMgb2YgQ2FyZGlvdG9jb2dyYW1zLiBUaGUgZGF0YXNldCBpbmNsdWRlZCAyMTI2IHByZXByb2Nlc3NlZCBmZXRhbCBjYXJkaW90b2NvZ3JhbXMgKENUR3MpLiBUaGUgQ1RHcyB3ZXJlIGNsYXNzaWZpZWQgYnkgdGhyZWUgZXhwZXJ0IG9ic3RldHJpY2lhbnMgYW5kIGEgY29uc2Vuc3VzIGNsYXNzaWZpY2F0aW9uIGxhYmVsIGFzc2lnbmVkIHRvIGVhY2ggb2YgdGhlbS4gDQoNCioqVGhlIDIxIGZlYXR1cmVzIGluY2x1ZGVkOiAqKiBiYXNlbGluZSB2YWx1ZXMgKExCRSxMQiwgd2hpY2ggd2VyZSBkZXRlcm1pbmVkIGJ5IGFwcHJveGltYXRpbmcgdGhlIG1lYW4gRkhSIHJvdW5kZWQgdG8gaW5jcmVtZW50cyBvZiA1IGJlYXRzIHBlciBtaW51dGUgKGJwbSkgZHVyaW5nIGEgMTAtbWludXRlIHdpbmRvdywgZXhjbHVkaW5nIGFjY2VsZXJhdGlvbnMgYW5kIGRlY2VsZXJhdGlvbnMgYW5kIHBlcmlvZHMgb2YgbWFya2VkIEZIUiB2YXJpYWJpbGl0eSAoZ3JlYXRlciB0aGFuIDI1IGJwbSkpLCAgYWNjZWxlcmF0aW9ucyAoQUMpLCBmb2V0YWwgbW92ZW1lbnQgKEZNKSwgdXRlcmluZSBjb250cmFjdGlvbnMgKFVDKSwgcGVyY2VudGFnZSBvZiB0aW1lIHdpdGggYWJub3JtYWwgc2hvcnQgdGVybSB2YXJpYWJpbGl0eSAoQVNUViksIG1lYW4gdmFsdWUgb2Ygc2hvcnQgdGVybSB2YXJpYWJpbGl0eSAobVNUViksIHBlcmNlbnRhZ2Ugb2YgdGltZSB3aXRoIGFibm9ybWFsIGxvbmcgdGVybSB2YXJpYWJpbGl0eSAoQUxUViksIG1lYW4gdmFsdWUgb2YgbG9uZyB0ZXJtIHZhcmlhYmlsaXR5IChtTFRWKSwgbGlnaHQgZGVjZWxlcmF0aW9ucyAoREwpLCBzZXZlcmUgZGVjZWxlcmF0aW9ucyAoRFMpLCBwcm9sb25ndWVkIGRlY2VsZXJhdGlvbnMgKERQKSwgcmVwZXRpdGl2ZSBkZWNlbGVyYXRpb25zIChEUiksIGhpc3RvZ3JhbSB3aWR0aCAoV2lkdGgpLCBsb3cgZnJlcS4gb2YgdGhlIGhpc3RvZ3JhbSAoTWluKSwgaGlnaCBmcmVxLiBvZiB0aGUgaGlzdG9ncmFtIChNYXgpLCBudW1iZXIgb2YgaGlzdG9ncmFtIHBlYWtzIChuTWF4KSwgbnVtYmVyIG9mIGhpc3RvZ3JhbSB6ZXJvcyAoTnplcm9lcyksIGhpc3RvZ3JhbXPigJkgbW9kZSwgbWVhbiwgbWVkaWFuLCB2YXJpYW5jZSBhbmQgdGVuZGVuY3kgKGxlZnQgYXNzeW1ldHJpYzsgc3ltbWV0cmljLCByaWdodCBhc3N5bWV0cmljKS4NCg0KKipDbGluaWNhbCBvYmplY3RpdmUqKiB3YXMgdG8gY2xhc3NpZnkgMTAgbW9ycGhvbG9naWMgcGF0dGVybnMsIGluY2x1ZGluZzogQ2FsbSBzbGVlcCwgUkVNIHNsZWVwLCBjYWxtIHZpZ2lsYW5jZSwgYWN0aXZlIHZpZ2lsYW5jZSwgc2hpZnQgcGF0dGVybiAoQSBvciBTdXNwIHdpdGggc2hpZnRzKSwgYWNjZWxlcmF0aXZlL2RlY2VsZXJhdGl2ZSBwYXR0ZXJuIChzdHJlc3Mgc2l0dWF0aW9uKSwgZGVjZWxlcmF0aXZlIHBhdHRlcm4gKHZhZ2FsIHN0aW11bGF0aW9uKSwgbGFyZ2VseSBkZWNlbGVyYXRpdmUgcGF0dGVybiwgZmxhdC1zaW51c29pZGFsIHBhdHRlcm4gKHBhdGhvbG9naWNhbCBzdGF0ZSkgYW5kIHN1c3BlY3QgcGF0dGVybnMuIFNvLCB0aGlzIGlzIGEgbXVsdGljbGFzcyBjbGFzc2lmaWNhdGlvbiBwcm9ibGVtDQpUaGUgZGF0YSBjb3VsZCBiZSBkb3dubG9hZGVkIGZyb206DQoNCjxodHRwczovL2FyY2hpdmUuaWNzLnVjaS5lZHUvbWwvZGF0YXNldHMvQ2FyZGlvdG9jb2dyYXBoeSM+DQoNClJlZmVyZW5jZTogQXlyZXMgZGUgQ2FtcG9zIGV0IGFsLiAoMjAwMCkgU2lzUG9ydG8gMi4wIEEgUHJvZ3JhbSBmb3IgQXV0b21hdGVkIEFuYWx5c2lzIG9mIENhcmRpb3RvY29ncmFtcy4gSiBNYXRlcm4gRmV0YWwgTWVkIDU6MzExLTMxOA0KDQoqKlByYWN0aWNhbCBvYmplY3RpdmUqKjogVGhlIHByZXNlbnQgZGF0YSBleHBlcmltZW50IGFpbXMgdG8gZXhwbG9yZSB0aGUgdXRpbGl0eSBvZiAzIGVuc2VtYmxpbmcgdGVjaG5pcXVlczogV2VpZ2h0ZWQgYXZlcmFnaW5nLCBNYWpvcml0eSB2b3RpbmcgYW5kIFN0YWNraW5nLg0KDQojIE1ldGhvZHMNCg0KQmVmb3JlIGJlaW5nIHVzZWQgYXMgaW5wdXQsIHRoZSBvcmlnaW5hbCBkYXRhIHdhcyBjbGVhbmVkIGFuZCB0cmFuc2Zvcm1lZC4gVGhlIGZlYXR1cmVzIHdpdGggbm8gb3IgbG93IHZhcmlhbmNlLCBhcyB3ZWxsIGFzIGhpZ2ggY29sbGluZWFyaXR5IHdlcmUgcmVtb3ZlZC4gT25seSAxNSBmZWF0dXJlcyByZW1haW5lZCBpbiB0aGUgZmluYWwgZGF0YWZyYW1lLiBTb21lIG9mIHRoZW0gaGF2ZSBiZWVuIHRyYW5zZm9ybWVkIGJ5IFllby1Kb2huc29uIHBvd2VyIHRyYW5zZm9ybWF0aW9uIGluIG9yZGVyIHRvIG9wdGltaXplIHRoZWlyIGNvbnRyYXN0IGFtb25nIDEwIGNsYXNzZXMuIFRoaXMgZGF0YXNldCB3YXMgdGhlIHJhbmRvbWx5IHNwbGl0ZWQgaW50byAyIHN1YnNldHMgZm9yIHRyYWluaW5nICg1MCUsbj0xMDY2KSBhbmQgdGVzdGluZyAoNTAlLG49MTA2MCkuIE1vZGVsc+KAmSBwZXJmb3JtYW5jZSB3YXMgZXZhbHVhdGVkIGJ5IHZpc3VhbCBjb25mdXNpb24gbWF0cml4LCBLYXBwYSBjb2VmZmljaWVudCBhbmQgRjEgc2NvcmUgKGZvciBlYWNoIGxhYmVsKS4NCg0KKk91ciBlbnNlbWJsaW5nIGV4cGVyaW1lbnQgY29uc2lzdGVkIG9mIDQgc3RlcHMqDQoNCisgMSlGaXJzdCwgd2UgdHJhaW5lZCA1IGJhc2ljIGNsYXNzaWZpZXJzIHRoYXQgYmFzZWQgb24gU3VwcG9ydCB2ZWN0b3IgbWFjaGluZSAoU1ZNIHdpdGggbGluZWFyIGtlcm5lbCksIGstbmVhcmVzdCBuZWlnaGJvcnMgKEtOTiksIHNpbXBsZSBkZWNpc2lvbiB0cmVlIChDQVJUKSwgT25lIHJ1bGUgKE9uZVIpIGFuZCBSYW5kb20gRm9yZXN0IChSYW5nZXIgcGFja2FnZSkuDQoNCisgMilXZSBkZXZlbG9wZWQgdGhlIGZpcnN0IGVuc2VtYmxlIG1vZGVsIHRoYXQgYmFzZWQgb24gV2VpZ2h0ZWQgQXZlcmFnaW5nIHByaW5jaXBsZS4NCg0KKyAzKUluIGEgc2ltaWxhciB3YXksIHdlIGFwcGxpZWQgdGhlIE1ham9yaXR5IHZvdGluZyBwcmluY2lwbGUgdG8gbWFrZSBhbm90aGVyIEVuc2VtYmxlIG1vZGVsLg0KDQorIDQpRmluYWxseSwgd2UgdXNlZCBTdGFja2luZyBlbnNlbWJsZSB0ZWNobmlxdWUgdG8gY29tYmluZSB0aGUgNSBiYXNpYyBsZWFybmVycyB1bmRlciBhIEdyYWRpZW50IGJvb3N0aW5nIG1hY2hpbmUgbGVhcm5lci4gDQoNClRoZSBjYXJldCBwYWNrYWdlIChNYXggS3VobiwgMjAxMikgd2FzIHVzZWQgdGhyb3VnaCBvdXQgb3VyIGV4cGVyaW1lbnQuIEFsbCAzIGVuc2VtYmxpbmcgcHJvY2VkdXJlcyB3ZXJlIG1hbnVhbGx5IHBlcmZvcm1lZCB1c2luZyBjdXN0b21pemVkIGxvb3BzIGFuZCBmdW5jdGlvbnMgaW4gUi4gV2UgYWxzbyBpbnRyb2R1Y2VkIDIgZnVuY3Rpb25zIGZvciB2aXN1YWxpemluZyB0aGUgY29uZnVzaW9uIG1hdHJpeCBhbmQgdGhlIHBlcmZvcm1hbmNlIGZvciBtdWx0aWxhYmVsIGNsYXNzaWZpZXIuDQoNCiMgRGF0YSBwcmVwYXJhdGlvbiBhbmQgZXhwbG9yYXRpb24NCg0KRmlyc3QsIHdlIHdpbGwgcHJlcGFyZSB0aGUgZ2dwbG90IHRoZW1lIGZvciBvdXIgZXhwZXJpbWVudA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCg0KbGlicmFyeSh0aWR5dmVyc2UpDQoNCm15X3RoZW1lIDwtIGZ1bmN0aW9uKGJhc2Vfc2l6ZSA9IDUsIGJhc2VfZmFtaWx5ID0gInNhbnMiKXsNCiAgdGhlbWVfbWluaW1hbChiYXNlX3NpemUgPSBiYXNlX3NpemUsIGJhc2VfZmFtaWx5ID0gYmFzZV9mYW1pbHkpICsNCiAgICB0aGVtZSgNCiAgICAgIGF4aXMudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gNSksDQogICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9IDAsIHZqdXN0ID0gMC41LCBoanVzdCA9IDAuNSksDQogICAgICBheGlzLnRpdGxlID0gZWxlbWVudF90ZXh0KHNpemUgPSA1KSwNCiAgICAgIHBhbmVsLmdyaWQubWFqb3IgPSBlbGVtZW50X2xpbmUoY29sb3IgPSAiZ3JleSIpLA0KICAgICAgcGFuZWwuZ3JpZC5taW5vciA9IGVsZW1lbnRfYmxhbmsoKSwNCiAgICAgIHBhbmVsLmJhY2tncm91bmQgPSBlbGVtZW50X3JlY3QoZmlsbCA9ICJ3aGl0ZSIpLA0KICAgICAgc3RyaXAuYmFja2dyb3VuZCA9IGVsZW1lbnRfcmVjdChmaWxsID0gIiM0ZjA4NzAiLCBjb2xvciA9ICIjNGYwODcwIiwgc2l6ZSA9MC41KSwNCiAgICAgIHN0cmlwLnRleHQgPSBlbGVtZW50X3RleHQoZmFjZSA9ICJib2xkIiwgc2l6ZSA9NSwgY29sb3IgPSAid2hpdGUiKSwNCiAgICAgIGxlZ2VuZC5wb3NpdGlvbiA9ICJib3R0b20iLA0KICAgICAgbGVnZW5kLmp1c3RpZmljYXRpb24gPSAiY2VudGVyIiwNCiAgICAgIGxlZ2VuZC5iYWNrZ3JvdW5kID0gZWxlbWVudF9ibGFuaygpLA0KICAgICAgcGFuZWwuYm9yZGVyID0gZWxlbWVudF9yZWN0KGNvbG9yID0gImdyZXkzMCIsIGZpbGwgPSBOQSwgc2l6ZSA9IDAuNSkNCiAgICApDQp9DQp0aGVtZV9zZXQobXlfdGhlbWUoKSkNCg0KbXljb2w9YygiI2ZmMDA0OCIsIiNmY2U2MjgiLCIjMGRlMmFhIiwiIzJkZDZlMiIsIiNjMzYyZjciLCIjZmZhZTIyIiwiI2IxZTgyNyIsIiMzNDk1ZWEiLCIjYWM5YWY5IiwiI2ZmNTFjNSIpDQpgYGANCg0KTm93IHdlIGxvYWQgdGhlIGRhdGFzZXQgaW50byBSOg0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCiNsb2FkIGRhdGENCg0KZGY9cmVhZC5jc3YoIkNhcmRpb3RvY29ncmFwaHkuY3N2IixzZXA9IjsiKSU+JS5bLC1jKDIxOjMxKV0lPiUuWywtMjJdDQoNCmRmW2MoMToyMCldIDwtIGxhcHBseShkZltjKDE6MjApXSwgYXMubnVtZXJpYykNCg0KZGYkQ0xBU1M9cmVjb2RlX2ZhY3RvcihkZiRDTEFTUyxgMWAgPSAiQ2FsbVNsZWVwIiwgYDJgID0gIlJFTSIsYDNgID0gIkNhbG1WaWciLGA0YCA9ICJBY3RWaWciLCBgNWAgPSAiU2hpZnRwYXR0ZXJuIixgNmAgPSAiQUQiLGA3YCA9ICJERSIsIGA4YCA9ICJMRCIsYDlgID0gIkZsYXRzaW51c29pZGFsIixgMTBgID0gIlN1c3BlY3QiKQ0KDQpkZiRDTEFTUz1hcy5mYWN0b3IoZGYkQ0xBU1MpDQoNCmhlYWQoZGYpJT4la25pdHI6OmthYmxlKCkNCg0KYGBgDQoNCiMgRGF0YSBjbGVhbmluZywgVmlzdWFsaXNhdGlvbiBhbmQgVHJhbnNmb3JtYXRpb25zDQoNCmBgYHtyfQ0KZGYlPiVnYXRoZXIoTEI6VmFyaWFuY2Usa2V5PSJGZWF0dXJlIix2YWx1ZT0iVmFsdWUiKSU+JWdncGxvdChhZXMoeD1WYWx1ZSxmaWxsPUNMQVNTKSkrZ2VvbV9kZW5zaXR5KGNvbG9yPSJibGFjayIsYWxwaGE9MC40LHNob3cubGVnZW5kID0gVCkrZmFjZXRfd3JhcCh+RmVhdHVyZSxkcm9wID0gVFJVRSxuY29sPTUsc2NhbGVzPSJmcmVlIikrbXlfdGhlbWUoNSkrc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPW15Y29sKStnZ3RpdGxlKCJPcmlnaW5hbCBkYXRhOiBEZW5zaXR5IGN1cnZlcyIpDQoNCmBgYA0KDQpUaGUgZGVuc2l0eSBwbG90cyBjYW4gdGVsbCB1cyB0d28gdGhpbmdzOg0KDQorIFNvbWUgZmVhdHVyZXMgc2VlbSB0byBiZSBlcXVpdmFsZW50IChmb3IgZXhhbXBsZTogTWVhbiwgTW9kZSBhbmQgTWVkaWFuKSBhcyB0aGVpciBkaXN0cmlidXRpb24gZGVuc2l0aWVzIHdlcmUgYWxtb3N0IGlkZW50aWNhbC4NCg0KKyBTb21lIGZlYXR1cmVzIGhhZCBhYm5vcm1hbCBkaXN0cmlidXRpb24gKGFzIHRoZXkgYXJlIGNvdW50IGRhdGEpLiBBIHRyYW5zZm9ybWF0aW9uIG1pZ2h0IGJlIG5lZWRlZCBpbiBvcmRlciB0byBpbXByb3ZlIHRoZSBjb250cmFzdCBvZiB0aGVpciB2YWx1ZSBhbW9uZ3N0IDEwIGNsYXNzZXMuIFRoZXNlIGluY2x1ZGU6IEFDLCBBTFRWLCBETCwgRFAsIERCLCBNTFRWLCBNQlRWLCBObWF4LE56ZXJvcyxVQyBhbmQgVmFyaWFuY2UuDQoNClRoZXJlZm9yZSwgd2Ugd2lsbCBhcHBseSBhIHRyYW5zZm9ybWF0aW9uIHRvIG91ciBkYXRhLiBUaGlzIHRyYW5zZm9ybWF0aW9uIGNvbnNpc3RzIG9mOg0KDQorIFJlbW92aW5nIHRoZSBmZWF0dXJlcyB3aXRoIG5vIG9yIGxvdyB2YXJpYW5jZSwgYXMgdGhleSB3aWxsIG5vdCBjb250cmlidXRlIHRvIG91ciBwcmVkaWN0aW9uLg0KKyBBcHBseWluZyBzeXN0ZW1hdGljYWxseSBhIFllby1Kb2huc29uIHRyYW5zZm9ybWF0aW9uIHRvIGZlYXR1cmVzIHRoYXQgaGF2ZSBza2V3ZWQgZGlzdHJpYnV0aW9uDQorIEZpbHRlcmluZyB0aGUgZmVhdHVyZXMgd2l0aCBoaWdoIGNvbGluZWFyaXR5IA0KDQpgYGB7cn0NCmxpYnJhcnkoY2FyZXQpDQoNCllKVD1wcmVQcm9jZXNzKGRmWywtMjFdLG1ldGhvZD1jKCJuenYiLCAiY29uZGl0aW9uYWxYIiwiWWVvSm9obnNvbiIsImNvcnIiKSkNCllKVGRhdGE9cHJlZGljdChZSlQsbmV3ZGF0YT1kZlssLTIxXSklPiVtdXRhdGUoLixDTEFTUz1kZiRDTEFTUykNCiAgDQpoZWFkKFlKVGRhdGEpJT4la25pdHI6OmthYmxlKCkNCg0KYGBgDQoNCkFmdGVyIHRyYW5zZm9ybWF0aW9uLCBvdXIgZGF0YXNldCBjb250YWlucyBvbmx5IDE1IGZlYXR1cmVzIChzbyA1IGZlYXR1cmVzIGhhdmUgYmVlbiByZW1vdmVkIGZyb20gdGhlIG9yaWdpbmFsIGRhdGEsIGR1ZSB0byBsb3cgdmFyaWFuY2Ugb3IgY29saW5lYXJpdHkpLiANCg0KV2UgdmlzdWFsaXNlIGFnYWluIHRoZSBkYXRhOg0KDQpgYGB7cn0NCllKVGRhdGElPiVnYXRoZXIoTEI6VmFyaWFuY2Usa2V5PSJGZWF0dXJlIix2YWx1ZT0iVmFsdWUiKSU+JWdncGxvdChhZXMoeD1WYWx1ZSxmaWxsPUNMQVNTKSkrZ2VvbV9kZW5zaXR5KGNvbG9yPSJibGFjayIsYWxwaGE9MC40KStmYWNldF93cmFwKH5GZWF0dXJlLGRyb3AgPSBUUlVFLG5jb2w9NSxzY2FsZXM9ImZyZWUiKStteV90aGVtZSg1KStzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXM9bXljb2wpK2dndGl0bGUoIlRyYW5zZm9ybWVkIGRhdGE6IERlbnNpdHkgY3VydmVzIikNCg0KYGBgDQoNCkFzIHdlIGNvdWxkIHNlZSwgdGhlIFllb19qb2huc29uIHRyYW5zZm9ybWF0aW9uIGhhcyBjb3JyZWN0ZWQgYXMgYmVzdCBhcyBpdCBjb3VsZCB0aGUgYWJub3JtYWwgc2tld25lc3MgaW4gQUMsIEZNLCBETCwgTnplb3JlcywgV2lkdGgsIFVDIGFuZCBWYXJpYW5jZS4gQWZ0ZXIgYmVpbmcgdHJhbnNmb3JtZWQsIHRob3NlIHZhcmlhYmxlcyBzaG93IGJldHRlciBjb250cmFzdHMuIEhvd2V2ZXIsIHN1Y2ggdHJhbnNmb3JtYXRpb24gbWlnaHQgbm90IGJlIHJlcXVpcmVkIGZvciBBU1RWLCBMQixNaW4gYW5kIE1heC4NCg0KVGhvdWdoIHRoZSB0cmFuc2Zvcm1hdGlvbiBhdXRvbWF0aWNhbGx5IHJlbW92ZWQgRFAgYW5kIERCIGR1ZSB0byBsb3cgdmFyaWFuY2UsIHdlIHNhdyB0aGF0IHRoZSBEUCBpbiByYXcgdmFsdWUgc2hvd2VkIGF0IGxlYXN0IGEgY29udHJhc3QgYmV0d2VlbiAyLzEwIGNsYXNzZXMsIHNvIHdlIHdpbGwga2VlcCB0aGlzIGZlYXR1cmUuDQoNCldlIGRlY2lkZSB0byBidWlsZCB0aGUgZmluYWwgZGF0YXNldCBhcyBmb2xsb3dzOg0KDQpmZWF0dXJlcyBpbiBSYXcgdmFsdWVzOiBBU1RWLCBMQixNaW4gYW5kIE1heA0KQW1vbmcgTWVhbiwgTW9kZSBhbmQgTWVkaWFuOiBvbmx5IDEgaXMgbmVlZGVkLiBXZSBkZWNpZGUgdG8ga2VlcCByYXcgTWVkaWFuDQpCZXR3ZWVuIERQIGFuZCBEQjogb25seSBvbmUgaXMgbmVlZGVkIGFuZCBpbiByYXcgdmFsdWUsIHdlIGNob29zZSBEUA0KT3RoZXIgdmFyaWFibGVzIHdvdWxkIGJlIGluIHRyYW5zZm9ybWVkIHZhbHVlOiBNTFRWLCBNU1RWLE5tYXgsTnplcm8sVmFyaWFuY2UsV2lkdGgsVUMgYW5kIERMDQoNCmBgYHtyfQ0KcmF3dmFsPWMoIkFTVFYiLCJMQiIsIk1pbiIsIk1heCIsIk1lZGlhbiIsIkRQIikNCnlqdmFsPWMoIk1MVFYiLCJNU1RWIiwiTm1heCIsIk56ZXJvIiwiVmFyaWFuY2UiLCJXaWR0aCIsIlVDIiwiREwiLCJGTSIsIkFDIikNCg0KZGF0YT1jYmluZChkZlssKG5hbWVzKGRmKSAlaW4lIHJhd3ZhbCldLFlKVGRhdGFbLChuYW1lcyhZSlRkYXRhKSAlaW4lIHlqdmFsKV0pJT4lbXV0YXRlKC4sQ0xBU1M9ZGYkQ0xBU1MpDQoNCnJtKFlKVGRhdGEsZGYscmF3dmFsLHlqdmFsLFlKVCkNCg0KYGBgDQoNCk91ciBmaW5hbCBkYXRhc2V0IGNvbnRhaW5zIDE1IGZlYXR1cmVzIGFuZCBjb3VsZCBiZSB2aXN1YWxpc2VkIGFzIGJlbG93Og0KDQpgYGB7cn0NCmRhdGElPiVnYXRoZXIoTEI6VmFyaWFuY2Usa2V5PSJGZWF0dXJlIix2YWx1ZT0iVmFsdWUiKSU+JWdncGxvdChhZXMoeD1WYWx1ZSxmaWxsPUNMQVNTKSkrZ2VvbV9kZW5zaXR5KGNvbG9yPSJibGFjayIsYWxwaGE9MC40KStmYWNldF93cmFwKH5GZWF0dXJlLGRyb3AgPSBUUlVFLG5jb2w9MyxzY2FsZXM9ImZyZWUiKStteV90aGVtZSg1KStzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXM9bXljb2wpK2dndGl0bGUoIkNsZWFuZWQgYW5kIHRyYW5zZm9ybWVkIGRhdGEiKQ0KDQpkYXRhJT4lZ2F0aGVyKExCOlZhcmlhbmNlLGtleT0iRmVhdHVyZSIsdmFsdWU9IlZhbHVlIiklPiVnZ3Bsb3QoYWVzKHg9Q0xBU1MseT1WYWx1ZSxmaWxsPUNMQVNTKSkrZ2VvbV92aW9saW4oY29sb3I9ImJsYWNrIixhbHBoYT0wLjcpK2ZhY2V0X3dyYXAofkZlYXR1cmUsZHJvcCA9IFRSVUUsbmNvbD0zLHNjYWxlcz0iZnJlZSIpK215X3RoZW1lKDUpK3NjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcz1teWNvbCkrZ2d0aXRsZSgiQ2xlYW5lZCBhbmQgdHJhbnNmb3JtZWQgZGF0YSIpDQoNCmBgYA0KDQpUaGlzIGRhdGFzZXQgd2lsbCBiZSByYW5kb21seSBzcGxpdHRlZCB0byBUcmFpbiBhbmQgdGVzdCBzdWJzZXRzOg0KDQpgYGB7cn0NCnNldC5zZWVkKDEyMzQpDQoNCmlkVHJhaW49Y3JlYXRlRGF0YVBhcnRpdGlvbih5PWRhdGEkQ0xBU1MscD0wLjUsbGlzdD1GQUxTRSkNCnRyYWluc2V0PWRhdGFbaWRUcmFpbixdDQp0ZXN0c2V0PWRhdGFbLWlkVHJhaW4sXQ0KDQpgYGANCg0KQSBjb3JyZWxhdGlvbiBtYXRyaXggdGhhdCBzaG93cyB0aGUgYXNzb2NpYXRpb24gcGF0dGVybiBhbW9uZyAxNSBmZWF0dXJlcyBpbiBvdXIgdHJhaW4gc3Vic2V0Og0KDQpgYGB7cn0NCmxpYnJhcnkoY29ycnBsb3QpDQpsaWJyYXJ5KFJDb2xvckJyZXdlcikNCg0KY29yX21hdD1hcy5tYXRyaXgoY29yKG1ldGhvZD0ic3BlYXJtYW4iLGFzLm1hdHJpeCh0cmFpbnNldFssYygxOjE1KV0pKSkNCg0KY29yX21hdCU+JWNvcnJwbG90KC4sb3JkZXI9ImhjbHVzdCIsdHlwZT0ibG93ZXIiLG1ldGhvZD0iY29sb3IiLHRsLmNvbD0iYmxhY2siLCB0bC5zcnQ9NDUsdGwuY2V4PTAuNixjb2w9cmV2KGJyZXdlci5wYWwobj0xMCwgbmFtZT0iU3BlY3RyYWwiKSkpDQoNCmBgYA0KDQpJdCdzIGFub3RoZXIgbWF0cml4IHRoYXQgc2hvd3MgdGhlIGRpc3RyaWJ1dGlvbiBvZiB0aGUgY2xhc3NlcyBmcm9tIGRpZmZlcmVudCBiaWRpbWVuc2lvbmFsIHZpZXdwb2ludHMNCg0KYGBge3J9DQoNCnBsb3RmdW5jbWlkIDwtIGZ1bmN0aW9uKGRhdGEsbWFwcGluZyl7DQogIHAgPC0gZ2dwbG90KGRhdGEgPSBkYXRhLG1hcHBpbmc9bWFwcGluZykrZ2VvbV9kZW5zaXR5KGFlcyhmaWxsPWRhdGEkQ0xBU1MpLGFscGhhPTAuNSxjb2xvcj0iYmxhY2siKStzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXM9bXljb2wpK3NjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXM9bXljb2wpDQogIHANCn0NCg0KcGxvdGZ1bmNMb3cgPC0gZnVuY3Rpb24oZGF0YSxtYXBwaW5nKXsNCiAgcCA8LSBnZ3Bsb3QoZGF0YSA9IGRhdGEsbWFwcGluZz1tYXBwaW5nKStzdGF0X2RlbnNpdHkyZChnZW9tPSJwb2x5Z29uIixhZXMoZmlsbD1kYXRhJENMQVNTLGFscGhhID0gLi5sZXZlbC4uKSkrc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPW15Y29sKQ0KICBwDQp9DQoNCnBsb3RmdW5jVXAgPC0gZnVuY3Rpb24oZGF0YSxtYXBwaW5nKXsNCiAgcCA8LSBnZ3Bsb3QoZGF0YSA9IGRhdGEsbWFwcGluZz1tYXBwaW5nKStnZW9tX3Ntb290aChtZXRob2Q9ImxtIixzZT1GQUxTRSxhbHBoYT0wLjYsYWVzKGNvbG9yPWRhdGEkQ0xBU1MpKStzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXM9bXljb2wpDQogIHANCn0NCg0KDQpsaWJyYXJ5KEdHYWxseSkNCg0KZ2dwYWlycyhkYXRhLGNvbHVtbnM9MToxNSxsb3dlcj1saXN0KGNvbnRpbnVvdXM9cGxvdGZ1bmNMb3cpLGRpYWc9bGlzdChjb250aW51b3VzPXBsb3RmdW5jbWlkKSx1cHBlciA9IGxpc3QoY29udGludW91cz1wbG90ZnVuY1VwKSkNCg0KYGBgDQoNCiMgVHJhaW5pbmcgNSBiYXNlIGxlYXJuZXJzDQoNClRoZSBmaXJzdCBzdGVwIGluIG91ciBleHBlcmltZW50IGNvbnNpc3RzIG9mIHRyYWluaW5nIDUgZGlmZmVyZW50IGJhc2UgbGVhcm5lcnMuIFRoZXNlIGluY2x1ZGU6IFNWTSwgQ0FSVCwgS05OLCBPbmVSIGFuZCBSYW5kb20gRm9yZXN0LiANCg0KYGBge3IsbWVzc2FnZSA9IEZBTFNFLHJlc3VsdHM9ImhpZGUifQ0KDQojNSBtb2RlbHMNCg0KQ29udHJvbD10cmFpbkNvbnRyb2wobWV0aG9kPSJyZXBlYXRlZGN2IixudW1iZXI9MTAscmVwZWF0cz0xMCxjbGFzc1Byb2JzPVRSVUUsc3VtbWFyeUZ1bmN0aW9uPW11bHRpQ2xhc3NTdW1tYXJ5LHNhdmVQcmVkaWN0aW9ucyA9ImZpbmFsIikNCg0KIzEpIFNWTQ0KDQpzZXQuc2VlZCgxMjM0KQ0KDQpzdm1vZD10cmFpbihDTEFTU34uLGRhdGE9dHJhaW5zZXQsbWV0aG9kID0gInN2bUxpbmVhcjIiLHRyQ29udHJvbD1Db250cm9sLHR1bmVMZW5ndGg9NSkNCg0KcHJlZHN2bT1wcmVkaWN0KHN2bW9kLG5ld2RhdGE9dGVzdHNldCkNCmNtMT1jb25mdXNpb25NYXRyaXgocHJlZHN2bSx0ZXN0c2V0JENMQVNTKQ0KDQojMikgQ0FSVA0KDQpzZXQuc2VlZCg2NjYpDQoNCmNhcnRtb2Q9dHJhaW4oQ0xBU1N+LixkYXRhPXRyYWluc2V0LG1ldGhvZCA9ICJycGFydCIsdHJDb250cm9sPUNvbnRyb2wsdHVuZUxlbmd0aD01KQ0KDQpwcmVkY2FydD1wcmVkaWN0KGNhcnRtb2QsbmV3ZGF0YT10ZXN0c2V0KQ0KY20yPWNvbmZ1c2lvbk1hdHJpeChwcmVkY2FydCx0ZXN0c2V0JENMQVNTKQ0KDQojMykgS05ODQoNCnNldC5zZWVkKDMzMykNCg0Ka25ubW9kPXRyYWluKENMQVNTfi4sZGF0YT10cmFpbnNldCxtZXRob2QgPSAia25uIix0ckNvbnRyb2w9Q29udHJvbCx0dW5lTGVuZ3RoPTUpDQoNCnByZWRrbm49cHJlZGljdChrbm5tb2QsbmV3ZGF0YT10ZXN0c2V0KQ0KY20zPWNvbmZ1c2lvbk1hdHJpeChwcmVka25uLHRlc3RzZXQkQ0xBU1MpDQoNCiM0KSAxUg0KDQpzZXQuc2VlZCgzMzMpDQoNCm9ybW9kPXRyYWluKENMQVNTfi4sZGF0YT10cmFpbnNldCxtZXRob2QgPSAiT25lUiIsdHJDb250cm9sPUNvbnRyb2wsdHVuZUxlbmd0aD01KQ0KDQpwcmVkb3I9cHJlZGljdChvcm1vZCxuZXdkYXRhPXRlc3RzZXQpDQpjbTQ9Y29uZnVzaW9uTWF0cml4KHByZWRvcix0ZXN0c2V0JENMQVNTKQ0KDQojNSkgcmFuZw0KDQpzZXQuc2VlZCgzMzMpDQoNCnJnbW9kPXRyYWluKENMQVNTfi4sZGF0YT10cmFpbnNldCxtZXRob2QgPSAicmFuZ2VyIix0ckNvbnRyb2w9Q29udHJvbCkNCg0KcHJlZHJnPXByZWRpY3Qocmdtb2QsbmV3ZGF0YT10ZXN0c2V0KQ0KY201PWNvbmZ1c2lvbk1hdHJpeChwcmVkcmcsdGVzdHNldCRDTEFTUykNCg0KYGBgDQoNCkJlY2F1c2Ugb3VyIHByb2JsZW0gaXMgY29tcGxleGUsIGFzIHdlIGhhdmUgMTAgY2xhc3NlcyB0byBjbGFzc2lmeSwgd2Ugd291bGQgbGlrZSB0byByZXByZXNlbnQgb3VyIGNvbmZ1c2lvbiBtYXRyaXggYW5kIG1vZGVsIHBlcmZvcm1hbmNlIGluIGdyYXBocy4gSGVyZSBpcyB0aGUgc29sdXRpb25zOg0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCm11bHRpY2xhc3NjbXBsb3Q9ZnVuY3Rpb24obW9kZWxvYmosdGVzdGRmLHRhcmdldCxtb2RlbG5hbWUpew0KICBwcmVkdD1wcmVkaWN0KG1vZGVsb2JqLG5ld2RhdGE9dGVzdGRmKQ0KICBjbT1jYXJldDo6Y29uZnVzaW9uTWF0cml4KHByZWR0LHRlc3RkZlssdGFyZ2V0XSkNCiAgDQogIGNtdD1jbSR0YWJsZSU+JWFzX3RpYmJsZSgpDQogIA0KICBmcmVxPUhtaXNjOjpkZXNjcmliZSh0ZXN0ZGZbLHRhcmdldF0pJT4lLiR2YWx1ZXMlPiUuJGZyZXF1ZW5jeQ0KICBsYWJlbHM9cm93Lm5hbWVzKGNtJHRhYmxlKQ0KICANCiAgaz0xDQogIGNtdCRyYXRlPWNtdCRuLzENCiAgZm9yKGkgaW4gMToxMCl7DQogICAgZm9yKGsgaW4gMToxMDApew0KICAgICAgaWYoY210JFJlZmVyZW5jZVtrXT09bGFiZWxzW2ldKXsNCiAgICAgICAgY210JHJhdGVba108LTEwMCooY210JG5ba10vZnJlcVtpXSkNCiAgICAgICAgaz1rKzENCiAgICAgIH0NCiAgICAgIGVsc2V7az1rfQ0KICAgIH0NCiAgfQ0KICANCiAgY210JT4lZ2dwbG90KGFlcyh4PVByZWRpY3Rpb24seT1SZWZlcmVuY2UsZmlsbD1yYXRlKSkrDQogICAgZ2VvbV90aWxlKGNvbG9yPSJibGFjayIpK215X3RoZW1lKDEwKSsNCiAgICBzY2FsZV9maWxsX2dyYWRpZW50Mihsb3c9IndoaXRlIixtaWQ9IiMwMDhjZmYiLGhpZ2g9IiNmZjAwNTkiLG1pZHBvaW50PTUwKSsNCiAgICB0aGVtZShheGlzLnRleHQueCA9IGVsZW1lbnRfdGV4dChhbmdsZSA9NDUsIGhqdXN0ID0gMC41KSkrDQogICAgZ2d0aXRsZShtb2RlbG5hbWUpKw0KICAgIGdlb21fdGV4dChhZXMoeT1SZWZlcmVuY2UseD1QcmVkaWN0aW9uLGxhYmVsPXJvdW5kKHJhdGUsMSkpLGNvbG9yPSJibGFjayIsc2l6ZT0zKStjb29yZF9maXhlZCgpDQp9DQoNCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCm11bHRpY2xhc3NjbXBsb3QobW9kZWxvYmo9c3Ztb2QsdGVzdGRmPXRlc3RzZXQsdGFyZ2V0PSJDTEFTUyIsbW9kZWxuYW1lPSJTVk0iKQ0KDQptdWx0aWNsYXNzY21wbG90KG1vZGVsb2JqPWNhcnRtb2QsdGVzdGRmPXRlc3RzZXQsdGFyZ2V0PSJDTEFTUyIsbW9kZWxuYW1lPSJDQVJUIikNCg0KbXVsdGljbGFzc2NtcGxvdChtb2RlbG9iaj1vcm1vZCx0ZXN0ZGY9dGVzdHNldCx0YXJnZXQ9IkNMQVNTIixtb2RlbG5hbWU9Ik9uZV9SIikNCg0KbXVsdGljbGFzc2NtcGxvdChtb2RlbG9iaj1rbm5tb2QsdGVzdGRmPXRlc3RzZXQsdGFyZ2V0PSJDTEFTUyIsbW9kZWxuYW1lPSJLTk4iKQ0KDQptdWx0aWNsYXNzY21wbG90KG1vZGVsb2JqPXJnbW9kLHRlc3RkZj10ZXN0c2V0LHRhcmdldD0iQ0xBU1MiLG1vZGVsbmFtZT0iUmFuZG9tRm9yZXN0IikNCg0KDQoNCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCm11bHRpY2xhc3NjbXN1bT1mdW5jdGlvbihtb2RlbG9iaix0ZXN0ZGYsdGFyZ2V0LG1vZGVsbmFtZSxsb3djb2wsaGlnaGNvbCl7DQogIA0KICBwcmVkdD1wcmVkaWN0KG1vZGVsb2JqLG5ld2RhdGE9dGVzdGRmKQ0KICBjbT1jYXJldDo6Y29uZnVzaW9uTWF0cml4KHByZWR0LHRlc3RkZlssdGFyZ2V0XSkNCiAgDQogIHN1bT1jbSRieUNsYXNzJT4lYXNfdGliYmxlKCklPiUuWyxjKDcsMTEpXSU+JW11dGF0ZSguLExhYmVscz1yb3cubmFtZXMoY20kdGFibGUpKQ0KICBzdW0lPiVnZ3Bsb3QoYWVzKHg9cmVvcmRlcihMYWJlbHMsRjEpLHk9RjEpKSsNCiAgICBnZW9tX2JhcihhZXMoZmlsbD1GMSksc3RhdD0iaWRlbnRpdHkiLGNvbG9yPSJibGFjayIpKw0KICAgIGNvb3JkX2ZsaXAoKSsNCiAgICBnZW9tX3RleHQoYWVzKGxhYmVsPXJvdW5kKEYxLDIpKSxoanVzdD0xLHNpemU9NSxjb2xvcj0id2hpdGUiKStnZ3RpdGxlKHBhc3RlKG1vZGVsbmFtZSwiLyBGMSBzY29yZSIpKSsNCiAgICBzY2FsZV9maWxsX2dyYWRpZW50KGxvdz1sb3djb2wsaGlnaD1oaWdoY29sKQ0KICB9DQoNCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCm11bHRpY2xhc3NjbXN1bShtb2RlbG9iaj1zdm1vZCx0ZXN0ZGY9dGVzdHNldCx0YXJnZXQ9IkNMQVNTIixtb2RlbG5hbWU9IlNWTSIsbG93Y29sPSIjYzk0YmU1IixoaWdoY29sPSIjZmYwMDY2IikNCg0KbXVsdGljbGFzc2Ntc3VtKG1vZGVsb2JqPWtubm1vZCx0ZXN0ZGY9dGVzdHNldCx0YXJnZXQ9IkNMQVNTIixtb2RlbG5hbWU9IktOTiIsbG93Y29sPSIjYzk0YmU1IixoaWdoY29sPSIjZmYwMDY2IikNCg0KbXVsdGljbGFzc2Ntc3VtKG1vZGVsb2JqPXJnbW9kLHRlc3RkZj10ZXN0c2V0LHRhcmdldD0iQ0xBU1MiLG1vZGVsbmFtZT0iUkYiLGxvd2NvbD0iI2M5NGJlNSIsaGlnaGNvbD0iI2ZmMDA2NiIpDQoNCm11bHRpY2xhc3NjbXN1bShtb2RlbG9iaj1vcm1vZCx0ZXN0ZGY9dGVzdHNldCx0YXJnZXQ9IkNMQVNTIixtb2RlbG5hbWU9Ik9ORVIiLGxvd2NvbD0iI2M5NGJlNSIsaGlnaGNvbD0iI2ZmMDA2NiIpDQoNCm11bHRpY2xhc3NjbXN1bShtb2RlbG9iaj1jYXJ0bW9kLHRlc3RkZj10ZXN0c2V0LHRhcmdldD0iQ0xBU1MiLG1vZGVsbmFtZT0iQ0FSVCIsbG93Y29sPSIjYzk0YmU1IixoaWdoY29sPSIjZmYwMDY2IikNCg0KYGBgDQoNCkJhc2VkIG9uIHRoZSBjb25mdXNpb24gbWF0cmljZXMgYW5kIEYxIHNjb3JlIGdyYXBocywgd2UgY2FuIHNlZSB0aGF0IHRoZSBiZXN0IG1vZGVsIHdhcyBSYW5kb20gRm9yZXN0LCB0aGUgc2Vjb25kIGJlc3Qgd2FzIFNWTS4gT25lUiBhbmQgRGVjaXNpb24gdHJlZSAoQ0FSVCkgd2VyZSB3ZWFrLCBib3RoIG9mIHRoZW0gZmFpbGVkIHRvIGNsYXNzaWZ5IGNvcnJlY3RseSB0aGUgcGF0aG9sb2dpY2FsIHBhdHRlcm5zIGFtb25nIDEwIHRhcmdldCBsYWJlbHMuIFRoZSBLTk4gd2FzIGJldHRlciB0aGFuIENBUlQgb3IgT25lUiBidXQgdGhpcyBiYXNlIGxlYXJuZXIgY2Fubm90IGFzc3VyZSB0aGUgY29ycmVjdCBwcmVkaWN0aW9uIG9mIGFsbCAxMCBsYWJlbHMuDQoNCiMgRmlyc3QgZW5zZW1ibGUgcnVsZTogV2VpZ2h0ZWQgYXZlcmFnZQ0KDQpPdXIgZmlzdCBlbnNlbWJsZSBtb2RlbCBhcHBsaWVzIGEgc2ltcGxlIHByaW5jaXBsZSBvZiB3ZWlnaHRlZCBhdmVyYWdlLiBBcyBtZW50aW9uZWQgYWJvdmUsIHdlIGZvdW5kIHRoYXQgdGhlIFJGIGFuZCBTVk0gd2VyZSB0d28gYmVzdCBtb2RlbHMgZm9yIHRoZSBwcmVkaWN0aW9uLCBzbyB3ZSB3aWxsIGFzc2lnbiBoaWdoZXIgd2VpZ2h0cyBmb3IgdGhvc2UgdHdvIG1vZGVscyAoMC40NSBhbmQgMC4zLCByZXNwZWN0aXZlbHkpLiBJbiBjb250cmFzdCwgS05OIGFuZCBDQVJUIHdlcmUgd2VhaywgYW5kIE9uZVIgd2FzIHRoZSB3b3JzdCwgc28gd2UgYXNzaWduIGEgbG93ZXIgd2VpZ2h0cyB0byB0aGVtICgwLjEgZm9yIEtOTiBhbmQgQ0FSVCwgMC4wMSB0byBPbmVSKS4gVGhlbiB3ZSBjb21iaW5lIHRob3NlIDUgcHJlZGljdGVkIHByb2JhYmlsaXRpZXMgdG9nZXRoZXIgdG8gbWFrZSBhIG5ldyBwcmVkaWN0aW9uLiBUaGUgbGFiZWwgd2l0aCBoaWdoZXN0IHByb2JhYmlsaXR5IGFtb25nIDEwIHdpbGwgYmUgdGFrZW4gYXMgdGhlIGZpbmFsIHByZWRpY3Rpb24uDQoNCmBgYHtyLG1lc3NhZ2UgPSBGQUxTRSx3YXJuaW5nPUZBTFNFfQ0KDQpwcmVkMT1wcmVkaWN0KHN2bW9kLG5ld2RhdGE9dGVzdHNldCx0eXBlPSJwcm9iIikNCnByZWQxPXByZWQxKjAuMzANCnByZWQxPXByZWQxJT4lYXNfdGliYmxlKCklPiVtdXRhdGUoLixNb2RlbD0iU1ZNIikNCg0KcHJlZDI9cHJlZGljdChyZ21vZCxuZXdkYXRhPXRlc3RzZXQsdHlwZT0icHJvYiIpDQpwcmVkMj1wcmVkMiowLjQ1DQpwcmVkMj1wcmVkMiU+JWFzX3RpYmJsZSgpJT4lbXV0YXRlKC4sTW9kZWw9IlJGIikNCg0KcHJlZDM9cHJlZGljdChrbm5tb2QsbmV3ZGF0YT10ZXN0c2V0LHR5cGU9InByb2IiKQ0KcHJlZDM9cHJlZDMqMC4xDQpwcmVkMz1wcmVkMyU+JWFzX3RpYmJsZSgpJT4lbXV0YXRlKC4sTW9kZWw9IktOTiIpDQoNCnByZWQ0PXByZWRpY3Qob3Jtb2QsbmV3ZGF0YT10ZXN0c2V0LHR5cGU9InByb2IiKQ0KcHJlZDQ9cHJlZDQqMC4wMQ0KcHJlZDQ9cHJlZDQlPiVhc190aWJibGUoKSU+JW11dGF0ZSguLE1vZGVsPSJPTkVSIikNCg0KcHJlZDU9cHJlZGljdChjYXJ0bW9kLG5ld2RhdGE9dGVzdHNldCx0eXBlPSJwcm9iIikNCnByZWQ1PXByZWQ1KjAuMQ0KcHJlZDU9cHJlZDUlPiVhc190aWJibGUoKSU+JW11dGF0ZSguLE1vZGVsPSJDQVJUIikNCg0KcHJlZHQ9cHJlZDFbLC0xMV0NCnByZWR0WyxdPC1OQQ0KTGFiZWxzPWNvbG5hbWVzKHByZWR0KQ0KDQpmb3IoaSBpbiAxOjEwNjApew0KICBmb3IgKGogaW4gMToxMCl7DQogICAgcHJlZHRbaSxqXT1wcmVkMVtpLGpdK3ByZWQyW2ksal0rcHJlZDNbaSxqXStwcmVkNFtpLGpdK3ByZWQ1W2ksal0NCiAgfQ0KfQ0KICANCnByZWR0JFByZWRpY3Q9cmVwKE5BLDEwNjApDQoNCg0Kaz0xDQpmb3IoaSBpbiAxOjEwNjApew0KICBmb3IoayBpbiAxOjEwKXsNCiAgICBpZihpcy5uYShwcmVkdCRQcmVkaWN0W2ldKSl7DQogIG1heHByb2I9bWF4KHByZWR0W2ksYygxOjEwKV0pDQogIHByZWR0JFByZWRpY3RbaV08LWlmZWxzZShwcmVkdFtpLGtdPT1tYXhwcm9iLExhYmVsc1trXSxOQSkNCiAgaz1rKzENCiAgICB9DQogICAgZWxzZXsoaz1rKQ0KfQ0KICB9DQp9DQpgYGANCg0KV2Ugd2lsbCBhbHNvIGNyZWF0ZSB0d28gZnVuY3Rpb25zIGZvciBwbG90dGluZyB0aGUgY29uZnVzaW9uIG1hdHJpeCBhbmQgRjEgc2NvcmVzIGZvciBvdXIgRW5zZW1ibGUgcHJlZGljdGlvbnM6DQoNCmBgYHtyLG1lc3NhZ2UgPSBGQUxTRSx3YXJuaW5nPUZBTFNFfQ0KDQplbnNlbWJsZWNtcGxvdD1mdW5jdGlvbih2b3RlLHRydXRoKXsNCiAgY209Y29uZnVzaW9uTWF0cml4KHJlZmVyZW5jZSA9IHRydXRoLHZvdGUpDQogIGNtdD1jbSR0YWJsZSU+JWFzX3RpYmJsZSgpDQogIGZyZXE9SG1pc2M6OmRlc2NyaWJlKHRydXRoKSU+JS4kdmFsdWVzJT4lLiRmcmVxdWVuY3kNCiAgbGFiZWxzPXJvdy5uYW1lcyhjbSR0YWJsZSkNCiAgDQogIGs9MQ0KICBjbXQkcmF0ZT1jbXQkbi8xDQogIGZvcihpIGluIDE6MTApew0KICAgIGZvcihrIGluIDE6MTAwKXsNCiAgICAgIGlmKGNtdCRSZWZlcmVuY2Vba109PWxhYmVsc1tpXSl7DQogICAgICAgIGNtdCRyYXRlW2tdPC0xMDAqKGNtdCRuW2tdL2ZyZXFbaV0pDQogICAgICAgIGs9aysxDQogICAgICB9DQogICAgICBlbHNle2s9a30NCiAgICB9DQogIH0NCiAgDQogIGNtdCU+JWdncGxvdChhZXMoeD1QcmVkaWN0aW9uLHk9UmVmZXJlbmNlLGZpbGw9cmF0ZSkpKw0KICAgIGdlb21fdGlsZShjb2xvcj0iYmxhY2siKStteV90aGVtZSgxMCkrDQogICAgc2NhbGVfZmlsbF9ncmFkaWVudDIobG93PSJ3aGl0ZSIsbWlkPSIjMDA4Y2ZmIixoaWdoPSIjZmYwMDU5IixtaWRwb2ludD01MCkrDQogICAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPTQ1LCBoanVzdCA9IDAuNSkpKw0KICAgIGdndGl0bGUoIkVuc2VtYmxlIikrDQogICAgZ2VvbV90ZXh0KGFlcyh5PVJlZmVyZW5jZSx4PVByZWRpY3Rpb24sbGFiZWw9cm91bmQocmF0ZSwxKSksY29sb3I9ImJsYWNrIixzaXplPTMpK2Nvb3JkX2ZpeGVkKCkNCn0NCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCnAxPWVuc2VtYmxlY21wbG90KHZvdGU9cHJlZHQkUHJlZGljdCx0cnV0aD10ZXN0c2V0JENMQVNTKStnZ3RpdGxlKCJXZWlnaHRlZCBhdmVyYWdpbmciKQ0KcDI9bXVsdGljbGFzc2NtcGxvdChtb2RlbG9iaj1yZ21vZCx0ZXN0ZGY9dGVzdHNldCx0YXJnZXQ9IkNMQVNTIixtb2RlbG5hbWU9IlJhbmRvbUZvcmVzdCIpDQoNCmdyaWRFeHRyYTo6Z3JpZC5hcnJhbmdlKHAxLHAyLG5jb2w9MikNCmBgYA0KDQpUaGUgY29uZnVzaW9uIG1hdHJpeCBvZiBXZWlnaHRlZCBhdmVyYWdlZCBwcmVkaWN0aW9uIHdhcyBiZXR0ZXIgdGhhbiB0aGF0IG9idGFpbmVkIGJ5IFJhbmRvbSBGb3Jlc3QgYnV0IG5vdCBmb3IgYWxsIHBhdHRlcm5zLiBUaGUgYXZlcmFnZWQgcHJlZGljdGlvbiB3YXMgaW1wcm92ZWQgZm9yIFNoaWZ0cGF0dGVybiwgUkVNLCBGbGF0c2ludXNvaWRhbCwgREUsIENhbG1TbGVlcCBhbmQgQWN0VmlnaWxlbmNlOyBob3dldmVyIGl0IHdhcyB1bmNoYW5nZWQgZm9yIFN1c3BlY3QsQUQgYW5kIExELCBhbmQgZGlkIHdvcnN0IGZvciBDYWxtIHZpZ2lsZW5jZS4gSG93ZXZlciB3ZSBjb3VsZCBzYXkgdGhhdCB0aGUgRW5zZW1ibGUgbW9kZWwgZGlkIGltcG9ydmUgdGhlIGFjY3VyYWN5IG9mIHByZWRpY3Rpb24uDQoNCmBgYHtyLG1lc3NhZ2UgPSBGQUxTRSx3YXJuaW5nPUZBTFNFfQ0KDQplbnNlbWJsZWNtc3VtPWZ1bmN0aW9uKHZvdGUsdHJ1dGgsbG93Y29sLGhpZ2hjb2wpew0KICANCiAgY209Y29uZnVzaW9uTWF0cml4KHJlZmVyZW5jZSA9IHRydXRoLHZvdGUpDQogIA0KICBzdW09Y20kYnlDbGFzcyU+JWFzX3RpYmJsZSgpJT4lLlssYyg3LDExKV0lPiVtdXRhdGUoLixMYWJlbHM9cm93Lm5hbWVzKGNtJHRhYmxlKSkNCiAgc3VtJT4lZ2dwbG90KGFlcyh4PXJlb3JkZXIoTGFiZWxzLEYxKSx5PUYxKSkrDQogICAgZ2VvbV9iYXIoYWVzKGZpbGw9RjEpLHN0YXQ9ImlkZW50aXR5Iixjb2xvcj0iYmxhY2siKSsNCiAgICBjb29yZF9mbGlwKCkrDQogICAgZ2VvbV90ZXh0KGFlcyhsYWJlbD1yb3VuZChGMSwyKSksaGp1c3Q9MSxzaXplPTUsY29sb3I9IndoaXRlIikrZ2d0aXRsZShwYXN0ZSgiRW5zZW1ibGUiKSkrDQogICAgc2NhbGVfZmlsbF9ncmFkaWVudChsb3c9bG93Y29sLGhpZ2g9aGlnaGNvbCkNCn0NCg0KYGBgDQoNCmBgYHtyLG1lc3NhZ2UgPSBGQUxTRSx3YXJuaW5nPUZBTFNFfQ0KDQpwMT1lbnNlbWJsZWNtc3VtKHZvdGU9cHJlZHQkUHJlZGljdCx0cnV0aD10ZXN0c2V0JENMQVNTLGxvd2NvbD0iI2M5NGJlNSIsaGlnaGNvbD0iI2ZmMDA2NiIpK2dndGl0bGUoIldlaWdodGVkIGF2ZXJhZ2luZyIpDQpwMj1tdWx0aWNsYXNzY21zdW0obW9kZWxvYmo9cmdtb2QsdGVzdGRmPXRlc3RzZXQsdGFyZ2V0PSJDTEFTUyIsbW9kZWxuYW1lPSJSRiIsbG93Y29sPSIjYzk0YmU1IixoaWdoY29sPSIjZmYwMDY2IikNCg0KZ3JpZEV4dHJhOjpncmlkLmFycmFuZ2UocDEscDIsbmNvbD0yKQ0KYGBgDQoNCkJhc2VkIG9uIEYxIHNjb3JlIHBlciBjbGFzcywgdGhlIFdlaWdodGVkIGF2ZXJhZ2UgcHJlZGljdGlvbiBwZXJmb3JtcyBiZXR0ZXIgdGhhbiB0aGUgYmVzdCBpbmRpdmlkdWFsIG1vZGVsIHdoaWNoIHdhcyBSYW5kb20gRm9yZXN0Lg0KDQojIFNlY29uZCBlbnNlbWJsZSBydWxlOiBNYWpvcml0eSBWb3RpbmcNCg0KVGhlIHNlY29uZCBFbnNlbWJsZSBtZXRob2QgY29uc2lzdHMgb2YgY29uc2lkZXJpbmcgdGhlIGhpZ2hlc3QgbnVtYmVyIG9mIHZvdGVzIGJ5IDUgaW5kaXZpZHVhbCBtb2RlbHMgdG8gbWFrZSB0aGUgZmluYWwgZGVjaXNpb24uIFdlIG1hZGUgYSBsb29wIGZvciBkb2luZyB0aGlzIG1hbnVhbGx5LiBOb3RlIHRoYXQgbWFqb3JpdHkgdm90ZSBhbW9uZyA1IGxlYXJuZXJzIG1lYW5zIHRoYXQgYXQgbGVhc3QgMyBsZWFybmVycyBnYXZlIHRoZSBzYW1lIHByZWRpY3Rpb24gZm9yIGEgdGFyZ2V0IGxhYmVsLiBJZiB0aGUgbWFqb3JpdHkgY2Fubm90IGJlIHJlYWNoZWQsIHdlIHdpbGwgYXNzaWduIHN5c3RlbWF0aWNhbGx5IHRoZSBwcmVkaWN0aW9uIGJ5IHRoZSBzdHJvbmdlc3QgbW9kZWwgd2hpY2ggaXMgUmFuZG9tIEZvcmVzdC4NCg0KYGBge3IsbWVzc2FnZSA9IEZBTFNFLHdhcm5pbmc9RkFMU0V9DQpwZGY9ZGF0YS5mcmFtZShSRj1wcmVkcmcsU1ZNPXByZWRzdm0sS05OPXByZWRrbm4sT05FUj1wcmVkb3IsQ0FSVD1wcmVkY2FydCkNCg0KbGFiZWxzPXJvdy5uYW1lcyhjbTEkdGFibGUpDQoNCnByZWR0PXJlcChOQSwxMDYwKQ0KDQprPTENCg0KZm9yKGkgaW4gMToxMCl7DQogIGZvcihrIGluIDE6MTA2MCl7DQogICAgaWYoaXMubmEocHJlZHRba10pKXsNCiAgICAgIHByZWR0W1trXV08LWlmZWxzZShwZGYkUkZba109PWxhYmVsc1tpXSAmIHBkZiRTVk1ba109PWxhYmVsc1tpXSAmIHBkZiRLTk5ba109PWxhYmVsc1tpXSxsYWJlbHNbaV0sDQogICAgICAgICAgICAgICAgIGlmZWxzZShwZGYkUkZba109PWxhYmVsc1tpXSAmIHBkZiRTVk1ba109PWxhYmVsc1tpXSAmIHBkZiRPTkVSW2tdPT1sYWJlbHNbaV0sbGFiZWxzW2ldLA0KICAgICAgICAgICAgICAgICBpZmVsc2UocGRmJFJGW2tdPT1sYWJlbHNbaV0gJiBwZGYkU1ZNW2tdPT1sYWJlbHNbaV0gJiBwZGYkQ0FSVFtrXT09bGFiZWxzW2ldLGxhYmVsc1tpXSwNCiAgICAgICAgICAgICAgICAgaWZlbHNlKHBkZiRSRltrXT09bGFiZWxzW2ldICYgcGRmJEtOTltrXT09bGFiZWxzW2ldICYgcGRmJE9ORVJba109PWxhYmVsc1tpXSxsYWJlbHNbaV0sDQogICAgICAgICAgICAgICAgIGlmZWxzZShwZGYkUkZba109PWxhYmVsc1tpXSAmIHBkZiRLTk5ba109PWxhYmVsc1tpXSAmIHBkZiRDQVJUW2tdPT1sYWJlbHNbaV0sbGFiZWxzW2ldLA0KICAgICAgICAgICAgICAgICBpZmVsc2UocGRmJFJGW2tdPT1sYWJlbHNbaV0gJiBwZGYkT05FUltrXT09bGFiZWxzW2ldICYgcGRmJENBUlRba109PWxhYmVsc1tpXSxsYWJlbHNbaV0sDQogICAgICAgICAgICAgICAgIGlmZWxzZShwZGYkU1ZNW2tdPT1sYWJlbHNbaV0gJiBwZGYkS05OW2tdPT1sYWJlbHNbaV0gJiBwZGYkT05FUltrXT09bGFiZWxzW2ldLGxhYmVsc1tpXSwNCiAgICAgICAgICAgICAgICAgaWZlbHNlKHBkZiRTVk1ba109PWxhYmVsc1tpXSAmIHBkZiRLTk5ba109PWxhYmVsc1tpXSAmIHBkZiRDQVJUW2tdPT1sYWJlbHNbaV0sbGFiZWxzW2ldLA0KICAgICAgICAgICAgICAgICBpZmVsc2UocGRmJEtOTltrXT09bGFiZWxzW2ldICYgcGRmJENBUlRba109PWxhYmVsc1tpXSAmIHBkZiRPTkVSW2tdPT1sYWJlbHNbaV0sbGFiZWxzW2ldLE5BDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICkpKSkpKSkpKQ0KICAgICAgaz1rKzF9DQogICAgZWxzZXtrPWt9DQogIH0NCn0NCg0KZm9yKGsgaW4gMToxMDYwKXsNCiAgaWYoaXMubmEocHJlZHRbW2tdXSkpe3ByZWR0W1trXV08LWFzLnZlY3RvcihwZGYkUkZbW2tdXSkNCiAgaz1rKzENCiAgfQ0KfQ0KDQpwZGYkTWFqb3JpdHk9YXMudmVjdG9yKHByZWR0KQ0KcGRmJFRydXRoPXRlc3RzZXQkQ0xBU1MNCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCg0KcDE9ZW5zZW1ibGVjbXBsb3Qodm90ZT1wZGYkTWFqb3JpdHksdHJ1dGg9cGRmJFRydXRoKQ0KcDI9bXVsdGljbGFzc2NtcGxvdChtb2RlbG9iaj1yZ21vZCx0ZXN0ZGY9dGVzdHNldCx0YXJnZXQ9IkNMQVNTIixtb2RlbG5hbWU9IlJhbmRvbUZvcmVzdCIpDQoNCmdyaWRFeHRyYTo6Z3JpZC5hcnJhbmdlKHAxLHAyLG5jb2w9MikNCg0KYGBgDQoNCmBgYHtyLG1lc3NhZ2UgPSBGQUxTRSx3YXJuaW5nPUZBTFNFfQ0KcDE9ZW5zZW1ibGVjbXN1bSh2b3RlPXBkZiRNYWpvcml0eSx0cnV0aD1wZGYkVHJ1dGgsbG93Y29sPSJyZWQiLGhpZ2hjb2w9InB1cnBsZSIpDQpwMj1tdWx0aWNsYXNzY21zdW0obW9kZWxvYmo9cmdtb2QsdGVzdGRmPXRlc3RzZXQsdGFyZ2V0PSJDTEFTUyIsbW9kZWxuYW1lPSJSRiIsbG93Y29sPSIjYzk0YmU1IixoaWdoY29sPSIjZmYwMDY2IikNCmdyaWRFeHRyYTo6Z3JpZC5hcnJhbmdlKHAxLHAyLG5jb2w9MikNCg0KYGBgDQoNCk92ZXJhbGwsIHRoZSBlbnNlbWJsZSBwcmVkaWN0aW9uIHRoYXQgYmFzZWQgb24gTWFqb3JpdHkgdm90ZSBpcyB3b3JzdCB0aGFuIHRoYXQgYnkgV2VpZ2h0ZWQgYXZlcmFnZSBtZXRob2QsIGFuZCB3b3JzdCB0aGFuIHRoYXQgYnkgdGhlIHN0YW5kIGFsb25lIFJhbmRvbSBGb3Jlc3QgbW9kZWwuDQoNCiMgVGhlIHRoaXJkIGVuc21ibGUgbW9kZWw6IEdCTSBTdGFja2luZyANCg0KVGhlIDNyZCBFbnNlbWJsZSBtZXRob2QgY29uc2lzdHMgb2YgdXNpbmcgdGhlIG91dHB1dCBvZiA1IGluZGl2aWR1YWwgbW9kZWxzIGFzIHRoZSBpbnB1dCBvZiBhIHRvcCBsYXllciBtb2RlbCB3aGljaCBpcyBhIEdCTSBsZWFybmVyLiBJbiBicmllZiwgd2Ugd2lsbCBnZW5lcmF0ZSBuZXcgdHJhaW5zdWJzZXQgYW5kIG5ldyB0ZXN0c3Vic2V0IHRoYXQgaW5jb3Jwb3JhdGUgdGhlIHByZWRpY3RlZCBwcm9iYWJpbGl0aWVzIG9mIDEwIGxhYmVscyB4IDUgbW9kZWxzID0gNTAgbmV3IGlucHV0IGZlYXR1cmVzIGZvciB0cmFpbmluZyBhbmQgdGVzdGluZyBhIEdCTSBtb2RlbC4gDQoNCmBgYHtyLG1lc3NhZ2UgPSBGQUxTRSx3YXJuaW5nPUZBTFNFLHJlc3VsdHM9ImhpZGUifQ0KDQojVFJBSU5QUkVEDQoNCnByZWQxPXByZWRpY3Qoc3Ztb2QsbmV3ZGF0YT10cmFpbnNldCx0eXBlPSJwcm9iIiklPiVhc190aWJibGUoKQ0KY29sbmFtZXMocHJlZDEpPC1wYXN0ZShMYWJlbHMsMSxzZXA9Il8iKQ0KDQpwcmVkMj1wcmVkaWN0KHJnbW9kLG5ld2RhdGE9dHJhaW5zZXQsdHlwZT0icHJvYiIpJT4lYXNfdGliYmxlKCkNCmNvbG5hbWVzKHByZWQyKTwtcGFzdGUoTGFiZWxzLDIsc2VwPSJfIikNCg0KcHJlZDM9cHJlZGljdChrbm5tb2QsbmV3ZGF0YT10cmFpbnNldCx0eXBlPSJwcm9iIiklPiVhc190aWJibGUoKQ0KY29sbmFtZXMocHJlZDMpPC1wYXN0ZShMYWJlbHMsMyxzZXA9Il8iKQ0KDQpwcmVkND1wcmVkaWN0KG9ybW9kLG5ld2RhdGE9dHJhaW5zZXQsdHlwZT0icHJvYiIpJT4lYXNfdGliYmxlKCkNCmNvbG5hbWVzKHByZWQ0KTwtcGFzdGUoTGFiZWxzLDQsc2VwPSJfIikNCg0KcHJlZDU9cHJlZGljdChjYXJ0bW9kLG5ld2RhdGE9dHJhaW5zZXQsdHlwZT0icHJvYiIpJT4lYXNfdGliYmxlKCkNCmNvbG5hbWVzKHByZWQ1KTwtcGFzdGUoTGFiZWxzLDUsc2VwPSJfIikNCg0KdHJhaW5zdGFja2RmPWNiaW5kKHByZWQxLHByZWQyLHByZWQzLHByZWQ0LHByZWQ1KSU+JW11dGF0ZSguLENMQVNTPXRyYWluc2V0JENMQVNTKQ0KDQojVEVTVFBSRUQNCg0KcHJlZDE9cHJlZGljdChzdm1vZCxuZXdkYXRhPXRlc3RzZXQsdHlwZT0icHJvYiIpJT4lYXNfdGliYmxlKCkNCmNvbG5hbWVzKHByZWQxKTwtcGFzdGUoTGFiZWxzLDEsc2VwPSJfIikNCg0KcHJlZDI9cHJlZGljdChyZ21vZCxuZXdkYXRhPXRlc3RzZXQsdHlwZT0icHJvYiIpJT4lYXNfdGliYmxlKCkNCmNvbG5hbWVzKHByZWQyKTwtcGFzdGUoTGFiZWxzLDIsc2VwPSJfIikNCg0KcHJlZDM9cHJlZGljdChrbm5tb2QsbmV3ZGF0YT10ZXN0c2V0LHR5cGU9InByb2IiKSU+JWFzX3RpYmJsZSgpDQpjb2xuYW1lcyhwcmVkMyk8LXBhc3RlKExhYmVscywzLHNlcD0iXyIpDQoNCnByZWQ0PXByZWRpY3Qob3Jtb2QsbmV3ZGF0YT10ZXN0c2V0LHR5cGU9InByb2IiKSU+JWFzX3RpYmJsZSgpDQpjb2xuYW1lcyhwcmVkNCk8LXBhc3RlKExhYmVscyw0LHNlcD0iXyIpDQoNCnByZWQ1PXByZWRpY3QoY2FydG1vZCxuZXdkYXRhPXRlc3RzZXQsdHlwZT0icHJvYiIpJT4lYXNfdGliYmxlKCkNCmNvbG5hbWVzKHByZWQ1KTwtcGFzdGUoTGFiZWxzLDUsc2VwPSJfIikNCg0KdGVzdHN0YWNrZGY9Y2JpbmQocHJlZDEscHJlZDIscHJlZDMscHJlZDQscHJlZDUpJT4lbXV0YXRlKC4sQ0xBU1M9dGVzdHNldCRDTEFTUykNCg0KDQoNCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRSxyZXN1bHRzPSJoaWRlIn0NCg0KI1N0YWNraW5nIEdCTQ0KDQpzZXQuc2VlZCgxMjM0KQ0KQ29udHJvbDI9dHJhaW5Db250cm9sKG1ldGhvZD0icmVwZWF0ZWRjdiIsbnVtYmVyPTUscmVwZWF0cz01LGNsYXNzUHJvYnM9VFJVRSxzdW1tYXJ5RnVuY3Rpb249bXVsdGlDbGFzc1N1bW1hcnkpDQoNCnN0YWNrR0JNPC10cmFpbihDTEFTU34uLGRhdGE9dHJhaW5zdGFja2RmLG1ldGhvZD0nZ2JtJyx0ckNvbnRyb2w9Q29udHJvbDIsdHVuZUxlbmd0aD0zKQ0KDQpwcmVkU1RLR0JNPXByZWRpY3Qoc3RhY2tHQk0sbmV3ZGF0YT10ZXN0c3RhY2tkZikNCg0KY21zdGs9Y29uZnVzaW9uTWF0cml4KHByZWRTVEtHQk0sdGVzdHN0YWNrZGYkQ0xBU1MpDQoNCmBgYA0KDQpgYGB7cixtZXNzYWdlID0gRkFMU0Usd2FybmluZz1GQUxTRX0NCg0KcDE9ZW5zZW1ibGVjbXBsb3Qodm90ZT1wcmVkU1RLR0JNLHRydXRoPXRlc3RzdGFja2RmJENMQVNTKStnZ3RpdGxlKCJHQk0gU3RhY2tpbmciKQ0KDQpwMj1tdWx0aWNsYXNzY21wbG90KG1vZGVsb2JqPXJnbW9kLHRlc3RkZj10ZXN0c2V0LHRhcmdldD0iQ0xBU1MiLG1vZGVsbmFtZT0iUmFuZG9tRm9yZXN0IikNCg0KZ3JpZEV4dHJhOjpncmlkLmFycmFuZ2UocDEscDIsbmNvbD0yKQ0KDQplbnNlbWJsZWNtc3VtKHZvdGU9cHJlZFNUS0dCTSx0cnV0aD10ZXN0c3RhY2tkZiRDTEFTUyxsb3djb2w9ImdvbGQiLGhpZ2hjb2w9InJlZCIpK2dndGl0bGUoIkdCTSBTdGFja2luZyIpDQoNCmBgYA0KDQpZZXMsIGFzIHlvdSBjb3VsZCBzZWU6IHRoZSB0d28gbGF5ZXJzIFN0YWNraW5nIGVuc2VtYmxlIG1vZGVsIGRpZCBhIHZlcnkgZ29vZCBqb2IsIGl0IGNvdWxkIHBlcmZvcm0gZXZlbiBiZXR0ZXIgdGhhbiBhIHN0YW5kYWxvbmUgUmFuZG9tIEZvcmVzdCBtb2RlbC4NCg0KIyMgQ29uY2x1c2lvbg0KDQpFbnNlbWJsaW5nIGlzIGEgc2ltcGxlIGJ1dCBlZmZlY3RpdmUgYXBwcm9hY2ggdG8gaW1wcm92ZSB0aGUgcGVyZm9ybWFuY2Ugb2Ygd2VhayBiYXNlIGFsZ29yaXRobXMuIEluIG1vc3Qgc2l0dWF0aW9ucywgYW4gZW5zZW1ibGUgbW9kZWwgd29yayBiZXR0ZXIgdGhhbiBhIHN0YW5kYWxvbmUgbGVhcm5lci4gRW5zZW1ibGluZyBvZmZlcnMgcm9idXN0bmVzcyBhbmQgc3RhYmlsaXR5IGZvciBib3RoIGNsYXNzaWZpY2F0aW9uIGFuZCByZWdyZXNzaW9uIHRhc2tzLCBldmVuIHRoZSBjb21wbGV4IHByb2JsZW0gbGlrZXMgdGhlIG11bHRpbGFiZWwgY2xhc3NpZmljYXRpb24gaW4gb3VyIHN0dWR5LiANCg0KSG93ZXZlciwgYW4gZW5zZW1ibGUgbW9kZWwgbWlnaHQgYmUgbm90IG5lY2Vzc2FyeSBpZiB5b3UgYWxyZWFkeSBoYXZlIGEgc3Ryb25nIGxlYXJuZXIgbGlrZXMgUmFuZG9tIEZvcmVzdCBvciBHQk0gYW1vbmcgYmFzZSBsZWFybmVycy4gSW4gZmFjdCwgUmFuZG9tIEZvcmVzdCBhbmQgR0JNIGFyZSBhbHNvIEVuc2VtYmxlIG1vZGVscyB0aGF0IGNvcnJlc3BvbmQgdG8gQmFnZ2luZyBhbmQgQm9vc3RpbmcgYWxnb3JpdGhtcywgcmVzcGVjdGl2ZWx5LiANCg0KVGhlcmUgYXJlIHNvbWUgZGlzYWR2YW50YWdlcyBvZiBFbnNlbWJsZSBtb2RlbGxpbmc7IGFzIHRoaXMgcHJvY2VzcyBpcyB0aW1lIGNvbnN1bWluZyBhbmQgbWFrZXMgdGhlIG1vZGVsIHZlcnkgZGlmZmljdWx0IHRvIGludGVycHJldC4gQnkgY29uc2VxdWVuY2UsIGVuc2VtYmxpbmcgaXMgbm90IGEgZ29vZCBjaG9pY2UgZm9yIGludGVycHJldGl2ZSBzdHVkaWVzIGFuZCByZWFsIHRpbWUgYW5hbHl6aW5nIHRhc2tzLg0KDQoqKlRoYW5rIHlvdSBmb3Igam9pbmluZyB1cyBhbmQgc2VlIHlvdSBpbiB0aGUgbmV4dCB0dXRvcmlhbC4qKg0K