Some Clustering Algorithms
Nana Boateng
October 19, 2017
This article describes several clustering algorithms implemented in R.
#install.packages("factoextra")
library(Rtsne)
library(tsne)
library(tidyverse)Loading tidyverse: ggplot2
Loading tidyverse: tibble
Loading tidyverse: tidyr
Loading tidyverse: readr
Loading tidyverse: purrr
Loading tidyverse: dplyr
Conflicts with tidy packages ---------------------------------------------------------------------------
filter(): dplyr, stats
lag(): dplyr, statslibrary(rio)The following rio suggested packages are not installed: ‘clipr’, ‘csvy’, ‘feather’, ‘fst’, ‘readODS’, ‘rmatio’
Use 'install_formats()' to install themlibrary(RColorBrewer)
library(knitr)
library("factoextra")Welcome! Related Books: `Practical Guide To Cluster Analysis in R` at https://goo.gl/13EFCZlibrary(cluster) ## calling the installed package
train<- import("/Users/nanaakwasiabayieboateng/Documents/memphisclassesbooks/DataMiningscience/Clustering/Crowdsourced Mapping/training.csv")
head(train)train$class=as.factor(train$class)str(train)'data.frame': 10545 obs. of 29 variables:
$ class : Factor w/ 6 levels "farm","forest",..: 6 6 6 6 6 2 6 6 6 6 ...
$ max_ndvi : num 998 914 3801 952 1232 ...
$ 20150720_N: num 637.6 634.2 1671.3 58 72.5 ...
$ 20150602_N: num 659 594 1207 -1599 -1221 ...
$ 20150517_N: num -1882 -1626 450 211 380 ...
$ 20150501_N: num -1924 -1672 1071 -1053 -1257 ...
$ 20150415_N: num 998 914 546 579 516 ...
$ 20150330_N: num -1740 -692 1078 -1565 -1413 ...
$ 20150314_N: num 630 708 215 -858 -803 ...
$ 20150226_N: num -1628 -1671 850 730 683 ...
$ 20150210_N: num -1326 -1409 1284 -3162 -2829 ...
$ 20150125_N: num -944 -989 1305 -1522 -1268 ...
$ 20150109_N: num 277 214 542 433 461 ...
$ 20141117_N: num -206.8 -75.6 922.6 228.2 317.5 ...
$ 20141101_N: num 536 893 890 555 405 ...
$ 20141016_N: num 749 401 836 531 564 ...
$ 20140930_N: num -483 -390 1824 952 1232 ...
$ 20140813_N: num 492 394 1670 -1075 -118 ...
$ 20140626_N: num 656 667 2307 546 683 ...
$ 20140610_N: num -921 -955 1562 -1026 -1814 ...
$ 20140525_N: num -1043 -934 1566 369 156 ...
$ 20140509_N: num -1942 -625 2208 -1787 -1190 ...
$ 20140423_N: num 267 120 1057 -1228 -924 ...
$ 20140407_N: num 367 365 385 305 432 ...
$ 20140322_N: num 452 477 301 291 283 ...
$ 20140218_N: num 211 221 294 369 298 ...
$ 20140202_N: num -2203 -2250 2763 -2202 -2197 ...
$ 20140117_N: num -1180 -1361 151 600 626 ...
$ 20140101_N: num 434 524 3801 -1344 -827 ...train=train%>%mutate_if(is.numeric,as.factor)# K-Means Clustering with 3 clusters
fit <- kmeans(iris[,1:4], 3)
# Cluster Plot against 1st 2 principal components
clusplot(iris[,1:4], fit$cluster, color=TRUE, shade=TRUE, labels=3, lines=0)
fit%>%head()$cluster
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[51] 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[101] 3 2 3 3 3 3 2 3 3 3 3 3 3 2 2 3 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3 3 3 2 3 3 2
$centers
Sepal.Length Sepal.Width Petal.Length Petal.Width
1 5.006000 3.428000 1.462000 0.246000
2 5.901613 2.748387 4.393548 1.433871
3 6.850000 3.073684 5.742105 2.071053
$totss
[1] 681.3706
$withinss
[1] 15.15100 39.82097 23.87947
$tot.withinss
[1] 78.85144
$betweenss
[1] 602.5192# K-Means Clustering with 6 clusters
fit <- kmeans(train[,-1], 6)
# Cluster Plot against 1st 2 principal components
clusplot(train[,-1], fit$cluster, color=TRUE, shade=TRUE, labels=6, lines=0)
Hierrachical Clustering
Compute the distances.
distances = dist(train[,-1], method = "euclidean")There are various techniques in hierarchical clustering. Here, we are considerating Ward’s method which considers distances between centroids and variances.
fit_hc<-hclust(distances, method = "ward.D")plot(fit_hc)
plot(fit_hc)
rect.hclust(fit_hc, k = 6, border = "blue")
plot(fit_hc) # display dendogram
groups <- cutree(fit_hc, k=3) # cut tree into 5 clusters
# draw dendogram with red borders around the 5 clusters
rect.hclust(fit_hc, k=3, border="red")
#library(rpud)
install.packages("rpud")Installing package into ‘/Users/nanaakwasiabayieboateng/Library/R/3.4/library’
(as ‘lib’ is unspecified)Warning in install.packages :
package ‘rpud’ is not available (for R version 3.4.1)k-means
fit_km = kmeans(train[,-1], centers = 6, nstart = 20)
names(fit_km)[1] "cluster" "centers" "totss" "withinss" "tot.withinss" "betweenss"
[7] "size" "iter" "ifault" attributes(fit_km)$names
[1] "cluster" "centers" "totss" "withinss" "tot.withinss" "betweenss"
[7] "size" "iter" "ifault"
$class
[1] "kmeans"fit_km$centers max_ndvi 20150720_N 20150602_N 20150517_N 20150501_N 20150415_N 20150330_N 20150314_N 20150226_N
1 7951.808 7041.744 2756.644 6396.5180 7148.348 496.4735 3529.513 1894.856 5252.8405
2 7837.537 6484.468 5362.508 4835.0892 5917.055 2556.1776 5433.398 3954.655 5455.9754
3 7087.216 4875.583 3801.549 2716.2724 3789.584 1977.7132 4893.552 3816.139 3876.7899
4 8092.030 6286.156 7405.038 5494.5289 5926.027 6785.9893 6858.562 3294.386 6597.1688
5 2597.921 1809.370 1268.958 774.4369 1201.813 1194.7143 1217.718 1173.303 818.8006
6 7827.469 6075.783 6587.107 4709.2019 4970.326 3796.6643 5575.058 4506.093 5715.9119
20150210_N 20150125_N 20150109_N 20141117_N 20141101_N 20141016_N 20140930_N 20140813_N 20140626_N
1 1802.241 2585.466 933.6302 1996.766 637.8239 1166.279 991.5442 1696.6322 2487.878
2 4945.251 7267.725 3781.3251 2021.533 2081.7024 1490.661 1126.3265 2631.8926 3210.604
3 3210.029 4261.117 1591.0804 2337.748 2037.0799 2068.411 1849.9389 1740.9452 3408.682
4 6696.053 7282.415 3473.8132 6943.557 4778.3507 4707.625 4102.8139 856.0087 2819.742
5 1211.962 1266.042 747.1180 1459.684 1316.5520 1319.166 1329.8296 1002.7528 1474.555
6 6364.351 5979.931 1616.2231 4447.159 4534.2848 5606.437 4798.5566 862.5837 3728.317
20140610_N 20140525_N 20140509_N 20140423_N 20140407_N 20140322_N 20140218_N 20140202_N 20140117_N
1 3649.289 4759.695 2913.354 4144.2253 739.5823 2886.8984 629.7423 6746.569 711.201
2 4903.869 4069.703 2923.284 3250.8815 1398.3357 4663.7203 1562.9058 6764.144 2582.180
3 3916.864 3163.083 3675.098 3216.8030 1818.2729 1760.8143 1161.0218 5557.568 1512.822
4 6802.208 2639.935 2615.503 2147.5663 3605.1606 3875.4071 4591.3772 7274.335 5304.153
5 1538.597 1599.596 1361.412 938.4758 827.3844 755.0112 611.2895 1458.597 1121.484
6 6591.674 4675.166 3608.978 3292.8240 3420.2253 1362.4768 3479.9115 6689.611 3818.138
20140101_N
1 1214.008
2 4851.483
3 2573.937
4 2779.081
5 622.777
6 2004.545#fit_km%>%head()
table(fit_km$cluster, train$class)
farm forest grass impervious orchard water
1 97 1604 2 2 17 4
2 136 1393 198 54 18 5
3 102 1867 31 13 6 4
4 17 18 20 672 0 165
5 1 1686 17 5 3 1
6 1088 863 178 223 9 26fit_km$cluster <- as.factor(fit_km$cluster )
ggplot(train, aes(train[,3],train[,2], color = fit_km$cluster)) + geom_point()
ggplot(train, aes(train[,4],train[,5], color = fit_km$cluster)) + geom_point()
names(train) [1] "class" "max_ndvi" "20150720_N" "20150602_N" "20150517_N" "20150501_N" "20150415_N"
[8] "20150330_N" "20150314_N" "20150226_N" "20150210_N" "20150125_N" "20150109_N" "20141117_N"
[15] "20141101_N" "20141016_N" "20140930_N" "20140813_N" "20140626_N" "20140610_N" "20140525_N"
[22] "20140509_N" "20140423_N" "20140407_N" "20140322_N" "20140218_N" "20140202_N" "20140117_N"
[29] "20140101_N"Optimal Number of Clusters
A fundamental question is how to determine the value of the parameter . If we look at the percentage of variance explained as a function of the number of clusters: One should choose a number of clusters so that adding another cluster doesn’t give much better modeling of the data. More precisely, if one plots the percentage of variance explained by the clusters against the number of clusters, the first clusters will add much information (explain a lot of variance), but at some point the marginal gain will drop, giving an angle in the graph. The number of clusters is chosen at this point, hence the “elbow criterion”.
wssplot <- function(data, nc=15, seed=148){
wss <- (nrow(data)-1)*sum(apply(data,2,var))
for (i in 2:nc){
set.seed(seed)
wss[i] <- sum(kmeans(data, centers=i)$withinss)}
plot(1:nc, wss, type="b", xlab="Number of Clusters",
ylab="Within groups sum of squares")}
wssplot(train[,-1], nc=8)
library(cluster)
clusplot(train[,-1], fit_km$cluster, main='2D representation of the Cluster solution',
color=TRUE, shade=TRUE,
labels=2, lines=0)
o=order(fit_km$cluster)
data.frame(train$class[o],fit_km$cluster[o])%>%head()
library(cluster)
clusplot(train[,-1], fit_km$cluster, main='2D representation of the Cluster solution',
color=TRUE, shade=TRUE, labels=2, lines=0)
#foodagg=agnes(train,diss=FALSE,metric="euclidian")
#plot(foodagg, main='Dendrogram') ## dendrogram
Distance measures
The classification of objects, into clusters, requires some methods for measuring the distance or the (dis)similarity between the objects. Chapter Clustering Distance Measures Essentials covers the common distance measures used for assessing similarity between observations.
It’s simple to compute and visualize distance matrix using the functions get_dist() and fviz_dist() [factoextra R package]:
get_dist(): for computing a distance matrix between the rows of a data matrix. Compared to the standard dist() function, it supports correlation-based distance measures including “pearson”, “kendall” and “spearman” methods. fviz_dist(): for visualizing a distance matrix
res.dist <- get_dist(USArrests, stand = TRUE, method = "pearson")
fviz_dist(res.dist,
gradient = list(low = "#00AFBB", mid = "white", high = "#FC4E07"))
Multiple Correspondence Analysis (MCA)
library(FactoMineR)
#works with qualitative variables
#MCA(train[,-1], ncp = 5, graph = TRUE)
#res.mca <- MCA(train[,-1],quanti.sup=19,quali.sup=20:36)
#summary(res.mca)Prepare the data
# Load data
data("USArrests")
my_data1 <- USArrests
# Remove any missing value (i.e, NA values for not available)
my_data1 <- na.omit(my_data1)
# Scale variables
my_data1 <- scale(my_data1)
# View the firt 3 rows
head(my_data1, n = 5) Murder Assault UrbanPop Rape
Alabama 1.24256408 0.7828393 -0.5209066 -0.003416473
Alaska 0.50786248 1.1068225 -1.2117642 2.484202941
Arizona 0.07163341 1.4788032 0.9989801 1.042878388
Arkansas 0.23234938 0.2308680 -1.0735927 -0.184916602
California 0.27826823 1.2628144 1.7589234 2.067820292Determine the optimal number of clusters: use factoextra::fviz_nbclust()
Three popular methods for determining the optimal number of clusters ◦ Elbow method ◾ Concept ◾ Algorithm ◾ R codes ◦ Average silhouette method ◾ Concept ◾ Algorithm ◾ R codes ◦ Conclusions about elbow and silhouette methods ◦ Gap statistic method ◾ Concept ◾ Algorithm ◾ R codes
fviz_nbclust(my_data1, kmeans, method = "gap_stat")Clustering k = 1,2,..., K.max (= 10): .. done
Bootstrapping, b = 1,2,..., B (= 100) [one "." per sample]:
.................................................. 50
.................................................. 100 
NbClust: A Package providing 30 indices for determining the best number of
clusters
install.packages("NbClust")Installing package into ‘/Users/nanaakwasiabayieboateng/Library/R/3.4/library’
(as ‘lib’ is unspecified)
trying URL 'https://cran.rstudio.com/bin/macosx/el-capitan/contrib/3.4/NbClust_3.0.tgz'
Content type 'application/x-gzip' length 37891 bytes (37 KB)
==================================================
downloaded 37 KB
The downloaded binary packages are in
/var/folders/mj/w1gxzjcd0qx2cw_0690z7y640000gn/T//RtmppzlA5w/downloaded_packageslibrary("NbClust")
res.nbclust <- NbClust(my_data1, distance = "euclidean",
min.nc = 2, max.nc = 10,
method = "complete", index ="all")*** : The Hubert index is a graphical method of determining the number of clusters.
In the plot of Hubert index, we seek a significant knee that corresponds to a
significant increase of the value of the measure i.e the significant peak in Hubert
index second differences plot.
*** : The D index is a graphical method of determining the number of clusters.
In the plot of D index, we seek a significant knee (the significant peak in Dindex
second differences plot) that corresponds to a significant increase of the value of
the measure.
*******************************************************************
* Among all indices:
* 9 proposed 2 as the best number of clusters
* 4 proposed 3 as the best number of clusters
* 6 proposed 4 as the best number of clusters
* 2 proposed 5 as the best number of clusters
* 1 proposed 8 as the best number of clusters
* 1 proposed 10 as the best number of clusters
***** Conclusion *****
* According to the majority rule, the best number of clusters is 2
******************************************************************* 
Visualize using factoextra:
factoextra::fviz_nbclust(res.nbclust) + theme_minimal()Among all indices:
===================
* 2 proposed 0 as the best number of clusters
* 1 proposed 1 as the best number of clusters
* 9 proposed 2 as the best number of clusters
* 4 proposed 3 as the best number of clusters
* 6 proposed 4 as the best number of clusters
* 2 proposed 5 as the best number of clusters
* 1 proposed 8 as the best number of clusters
* 1 proposed 10 as the best number of clusters
Conclusion
=========================
* According to the majority rule, the best number of clusters is 2 .
Clustering validation statistics
The term clustering validation is used to design the procedure of evaluating the results of a clustering algorithm. Clustering validation statistics: fpc::cluster.stats()
my_data <- scale(iris[, -5])
# Enhanced hierarchical clustering, cut in 3 groups
library("factoextra")
res.hc <- eclust(my_data, "hclust", k = 3, graph = FALSE)
# Visualize
fviz_dend(res.hc, rect = TRUE, show_labels = FALSE)
K-means clustering
Determine the optimal number of clusters:
fviz_nbclust(my_data1, kmeans, method = "gap_stat")Clustering k = 1,2,..., K.max (= 10): .. done
Bootstrapping, b = 1,2,..., B (= 100) [one "." per sample]:
.................................................. 50
.................................................. 100
#Compute and visualize k-means clustering
km.res <- kmeans(my_data1, 4, nstart = 25)
# Visualize
fviz_cluster(km.res, data = my_data1, frame.type = "convex")+
theme_minimal()argument frame is deprecated; please use ellipse instead.argument frame.type is deprecated; please use ellipse.type instead.
K-medoids clustering or PAM (Partitioning Around Medoids)
An alternative to k-means clustering is the K-medoids clustering or PAM (Partitioning Around Medoids, Kaufman & Rousseeuw, 1990), which is less sensitive to outliers compared to k-means.
pam.res <- pam(my_data1, 4)
# Visualize
fviz_cluster(pam.res)
Hierarchical clustering
Determine the optimal number of clusters:
Estimate the number of clusters in the data using gap statistics : factoextra::fviz_nbclust()
fviz_nbclust(my_data, kmeans, method = "gap_stat")Clustering k = 1,2,..., K.max (= 10): .. done
Bootstrapping, b = 1,2,..., B (= 100) [one "." per sample]:
.did not converge in 10 iterationsdid not converge in 10 iterations....did not converge in 10 iterationsdid not converge in 10 iterations.did not converge in 10 iterations..did not converge in 10 iterations..did not converge in 10 iterations...did not converge in 10 iterations...did not converge in 10 iterations...did not converge in 10 iterations.did not converge in 10 iterationsdid not converge in 10 iterations...did not converge in 10 iterations.Quick-TRANSfer stage steps exceeded maximum (= 527250).....did not converge in 10 iterations..did not converge in 10 iterations..did not converge in 10 iterations..did not converge in 10 iterations..did not converge in 10 iterations..Quick-TRANSfer stage steps exceeded maximum (= 527250).did not converge in 10 iterationsdid not converge in 10 iterations..did not converge in 10 iterations.did not converge in 10 iterations...did not converge in 10 iterations...did not converge in 10 iterations. 50
.did not converge in 10 iterations..did not converge in 10 iterations.did not converge in 10 iterations......did not converge in 10 iterations....did not converge in 10 iterations.did not converge in 10 iterations..did not converge in 10 iterations.did not converge in 10 iterations....Quick-TRANSfer stage steps exceeded maximum (= 527250).......did not converge in 10 iterations...did not converge in 10 iterations....did not converge in 10 iterations..did not converge in 10 iterations.....did not converge in 10 iterations..did not converge in 10 iterations..... 100 
library("NbClust")
set.seed(123)
res.nbclust <- NbClust(my_data, distance = "euclidean",
min.nc = 2, max.nc = 10,
method = "complete", index ="all")
Visualize using factoextra:
factoextra::fviz_nbclust(res.nbclust) + theme_minimal()
k-means clustering: Partitioning Around Medoids. Robust alternative to k-means
clustering, less sensitive to outliers.
#Compute and visualize k-means clustering
km.res <- kmeans(my_data, 6, nstart = 25)
# Visualize
fviz_cluster(km.res, data = my_data, frame.type = "convex")+
theme_minimal()argument frame is deprecated; please use ellipse instead.argument frame.type is deprecated; please use ellipse.type instead.
# Compute hierarchical clustering and cut into 4 clusters
res <- hcut(my_data, k = 6, stand = TRUE)
# Visualize
fviz_dend(res, rect = TRUE, cex = 0.5,
k_colors = c("#00AFBB","#2E9FDF", "#E7B800", "#FC4E
07","#99D594", "#3288BD"))PAM clustering: Partitioning Around Medoids. Robust alternative to k-means
clustering, less sensitive to outliers.
pam.res <- pam(my_data, 4)
# Visualize
fviz_cluster(pam.res)
Hierarchical clustering
# 2. Compute dissimilarity matrix
d <- dist(my_data1, method = "euclidean")
# Hierarchical clustering using Ward's method
res.hc <- hclust(d, method = "ward.D2" )
# Cut tree into 4 groups
rp <- cutree(res.hc, k = 4)
# Visualize
plot(res.hc, cex = 0.6) # plot tree
rect.hclust(res.hc, k = 4, border = 2:5) # add rectangle
Clustering validation
Clustering validation includes three main tasks: 1. clustering tendency assesses whether applying clustering is suitable to your data. 2. clustering evaluation assesses the goodness or quality of the clustering. 3. clustering stability seeks to understand the sensitivity of the clustering result to various algorithmic parameters, for example, the number of clusters.
- Methods for assessing clustering tendency ◦ Hopkins statistic ◾ Algorithm ◾ R function for computing Hopkins statistic: clustertend::hopkins() ◦ VAT: Visual Assessment of cluster Tendency: seriation::dissplot() ◾ VAT Algorithm ◾ R functions for VAT
- A single function for Hopkins statistic and VAT: factoextra::get_clust_tendency()
• Hopkins statistic: If the value of Hopkins statistic is close to zero (far below 0.5), then we can conclude that the dataset is significantly clusterable. • VAT (Visual Assessment of cluster Tendency): The VAT detects the clustering tendency in a visual form by counting the number of square shaped dark (or colored) blocks along the diagonal in a VAT image.
my_data2 <- scale(iris[, -5])
get_clust_tendency(my_data2, n = 50,
gradient = list(low = "steelblue", high
= "white"))$hopkins_stat
[1] 0.2002686
$plot
# 1. Loading and preparing data
data("USArrests")
my_data <- scale(USArrests)
# 2. Compute dissimilarity matrix
d <- dist(my_data, method = "euclidean")
# Hierarchical clustering using Ward's method
res.hc <- hclust(d, method = "ward.D2" )
grp <- cutree(res.hc, k = 4)
# Visualize
plot(res.hc, cex = 0.6) # plot tree
rect.hclust(res.hc, k = 4, border = 2:5) # add rectangle
# Compute hierarchical clustering and cut into 4 clusters
res <- hcut(my_data1, k = 4, stand = TRUE)
# Visualize
fviz_dend(res, rect = TRUE, cex = 0.5,
k_colors = c("#D53E4F","#FC8D59", "#E6F598", "#99D594" ,"#3288BD"))Length of color vector was longer than the number of clusters - first k elements are used
my_data3 <- scale(iris[, -5])
# Enhanced hierarchical clustering, cut in 3 groups
library("factoextra")
res.hc <- eclust(my_data3, "hclust", k = 3, graph = FALSE)
# Visualize
fviz_dend(res.hc, rect = TRUE, show_labels = FALSE)
#Compute hierarchical clustering and cut into 4 clusters
res <- hcut(my_data3, k = 3, stand = TRUE)
# Visualize
fviz_dend(res, rect = TRUE, cex = 0.5,
k_colors = c("#D53E4F", "#E6F598", "#99D594" ,"#3288BD"))Length of color vector was longer than the number of clusters - first k elements are used
Validate clustering results by inspection the cluster silhouette plot
Recall that the silhouette \(S_i\) measures how similar an object \(i\) is to the the other objects in its own cluster versus those in the neighbor cluster. \(S_i\) values range from 1 to - 1: • A value of \(S_i\) close to 1 indicates that the object is well clustered. In the other words, the object \(i\) is similar to the other objects in its group. • A value of \(S_i\) close to -1 indicates that the object is poorly clustered, and that assignment to some other cluster would probably improve the overall results.
# Visualize the silhouette plot
fviz_silhouette(res.hc) cluster size ave.sil.width
1 1 49 0.63
2 2 30 0.44
3 3 71 0.32
Which samples have negative silhouette? To what cluster are they closer?
# Silhouette width of observations
sil <- res.hc$silinfo$widths[, 1:3]
# Objects with negative silhouette
neg_sil_index <- which(sil[, 'sil_width'] < 0)
sil[neg_sil_index, , drop = FALSE]res.hc$dist.method[1] "euclidean"How to choose the appropriate clustering algorithms
for your data?
- Clustering validation measures in clValid package ◦ Internal validation measures ◦ Stability validation measures ◦ Biological validation measures
- R function clValid() ◦ Format ◦ Examples of usage ◾ Data ◾ Compute clValid()
install.packages("clValid")Installing package into ‘/Users/nanaakwasiabayieboateng/Library/R/3.4/library’
(as ‘lib’ is unspecified)
trying URL 'https://cran.rstudio.com/bin/macosx/el-capitan/contrib/3.4/clValid_0.6-6.tgz'
Content type 'application/x-gzip' length 506712 bytes (494 KB)
==================================================
downloaded 494 KB
The downloaded binary packages are in
/var/folders/mj/w1gxzjcd0qx2cw_0690z7y640000gn/T//RtmppzlA5w/downloaded_packages# Compute clValid
library("clValid")
intern <- clValid(my_data1, nClust = 2:6,
clMethods = c("hierarchical","kmeans","pam"),
validation = "internal")
# Summary
summary(intern)
Clustering Methods:
hierarchical kmeans pam
Cluster sizes:
2 3 4 5 6
Validation Measures:
2 3 4 5 6
hierarchical Connectivity 6.6437 9.5615 13.9563 22.5782 31.2873
Dunn 0.2214 0.2214 0.2224 0.2046 0.2126
Silhouette 0.4085 0.3486 0.3637 0.3213 0.2720
kmeans Connectivity 6.6437 13.6484 16.2413 24.6639 33.7194
Dunn 0.2214 0.2224 0.2224 0.1983 0.2231
Silhouette 0.4085 0.3668 0.3573 0.3377 0.3079
pam Connectivity 6.6437 13.8302 20.4421 29.5726 38.2643
Dunn 0.2214 0.1376 0.1849 0.1849 0.2019
Silhouette 0.4085 0.3144 0.3390 0.3105 0.2630
Optimal Scores:
Score Method Clusters
Connectivity 6.6437 hierarchical 2
Dunn 0.2231 kmeans 6
Silhouette 0.4085 hierarchical 2 How to compute p-value for hierarchical clustering in
R?
The R package pvclust (Suzuki et al., 2004) which uses bootstrap resampling techniques to compute p-value for each clusters.
#install.packages("pvclust")
library(pvclust)
# Data preparation
set.seed(123)
data("lung")
ss <- sample(1:73, 30) # extract 20 samples out of
my_data4 <- lung[, ss]
my_data4%>%head()# Compute pvclust
res.pv <- pvclust(my_data4, method.dist="cor",
method.hclust="average", nboot = 10)Bootstrap (r = 0.5)... Done.
Bootstrap (r = 0.6)... Done.
Bootstrap (r = 0.7)... Done.
Bootstrap (r = 0.8)... Done.
Bootstrap (r = 0.9)... Done.
Bootstrap (r = 1.0)... Done.
Bootstrap (r = 1.1)... Done.
Bootstrap (r = 1.2)... Done.
Bootstrap (r = 1.3)... Done.
Bootstrap (r = 1.4)... Done.# Default plot
plot(res.pv, hang = -1, cex = 0.5)
pvrect(res.pv)
10 Advanced clustering methods
10.1 Fuzzy clustering analysis
Fuzzy clustering is also known as soft method. Standard clustering approaches produce partitions (K-means, PAM), in which each observation belongs to only one cluster. This is known as hard clustering. In Fuzzy clustering, items can be a member of more than one cluster. Each item has a set of membership coefficients corresponding to the degree of being in a given cluster. The Fuzzy c-means method is the most popular fuzzy clustering algorithm. Read more: Fuzzy clustering analysis. 10.2 Model-based clustering In model-based clustering, the data are viewed as coming from a distribution that is mixture of two ore more clusters. It finds best fit of models to data and estimates the number of clusters. Read more: Model-based clustering.
7 Clustering validation
Clustering validation includes three main tasks: 1. clustering tendency assesses whether applying clustering is suitable to your data. 2. clustering evaluation assesses the goodness or quality of the clustering. 3. clustering stability seeks to understand the sensitivity of the clustering result to various algorithmic parameters, for example, the number of clusters.
- Methods for assessing clustering tendency ◦ Hopkins statistic ◾ lgorithm ◾ R function for computing Hopkins statistic: clustertend::hopkins() ◦ VAT: Visual Assessment of cluster Tendency: seriation::dissplot() ◾ VAT Algorithm ◾ R functions for VAT
- A single function for Hopkins statistic and VAT: factoextra::get_clust_tendency()
• Hopkins statistic: If the value of Hopkins statistic is close to zero (far below 0.5), then we can conclude that the dataset is significantly clusterable. • VAT (Visual Assessment of cluster Tendency): The VAT detects the clustering tendency in a visual form by counting the number of square shaped dark (or colored) blocks along the diagonal in a VAT image.
Hierarchical K-Means Clustering
K-means (Chapter @ref(kmeans-clustering)) represents one of the most popular clustering algorithm. However, it has some limitations: it requires the user to specify the number of clusters in advance and selects initial centroids randomly. The final k-means clustering solution is very sensitive to this initial random selection of cluster centers. The result might be (slightly) different each time you compute k-means.
# Compute hierarchical k-means clustering
library(factoextra)
res.hk <-hkmeans(my_data1, 4)
# Elements returned by hkmeans()
names(res.hk) [1] "cluster" "centers" "totss" "withinss" "tot.withinss" "betweenss"
[7] "size" "iter" "ifault" "data" "hclust" # Print the results
res.hkHierarchical K-means clustering with 4 clusters of sizes 8, 13, 16, 13
Cluster means:
Murder Assault UrbanPop Rape
1 1.4118898 0.8743346 -0.8145211 0.01927104
2 0.6950701 1.0394414 0.7226370 1.27693964
3 -0.4894375 -0.3826001 0.5758298 -0.26165379
4 -0.9615407 -1.1066010 -0.9301069 -0.96676331
Clustering vector:
Alabama Alaska Arizona Arkansas California Colorado
1 2 2 1 2 2
Connecticut Delaware Florida Georgia Hawaii Idaho
3 3 2 1 3 4
Illinois Indiana Iowa Kansas Kentucky Louisiana
2 3 4 3 4 1
Maine Maryland Massachusetts Michigan Minnesota Mississippi
4 2 3 2 4 1
Missouri Montana Nebraska Nevada New Hampshire New Jersey
2 4 4 2 4 3
New Mexico New York North Carolina North Dakota Ohio Oklahoma
2 2 1 4 3 3
Oregon Pennsylvania Rhode Island South Carolina South Dakota Tennessee
3 3 3 1 4 1
Texas Utah Vermont Virginia Washington West Virginia
2 3 4 3 3 4
Wisconsin Wyoming
4 3
Within cluster sum of squares by cluster:
[1] 8.316061 19.922437 16.212213 11.952463
(between_SS / total_SS = 71.2 %)
Available components:
[1] "cluster" "centers" "totss" "withinss" "tot.withinss" "betweenss"
[7] "size" "iter" "ifault" "data" "hclust" # Visualize the tree
fviz_dend(res.hk, cex = 0.6, palette = "jco",
rect = TRUE, rect_border = "jco", rect_fill = TRUE)
# Visualize the hkmeans final clusters
fviz_cluster(res.hk, palette = "jco", repel = TRUE,
ggtheme = theme_classic())
The fuzzy clustering is considered as soft clustering, in which each element has a probability of belonging to each cluster. In other words, each element has a set of membership coefficients corresponding to the degree of being in a given cluster.
This is different from k-means and k-medoid clustering, where each object is affected exactly to one cluster. K-means and k-medoids clustering are known as hard or non-fuzzy clustering.
In fuzzy clustering, points close to the center of a cluster, may be in the cluster to a higher degree than points in the edge of a cluster. The degree, to which an element belongs to a given cluster, is a numerical value varying from 0 to 1.
The fuzzy c-means (FCM) algorithm is one of the most widely used fuzzy clustering algorithms. The centroid of a cluster is calculated as the mean of all points, weighted by their degree of belonging to the cluster:
Computing fuzzy clustering
The function fanny() [cluster R package] can be used to compute fuzzy clustering. FANNY stands for fuzzy analysis clustering. A simplified format is:
x: A data matrix or data frame or dissimilarity matrix k: The desired number of clusters to be generated metric: Metric for calculating dissimilarities between observations stand: If TRUE, variables are standardized before calculating the dissimilarities The function fanny() returns an object including the following components:
membership: matrix containing the degree to which each observation belongs to a given cluster. Column names are the clusters and rows are observations coeff: Dunn’s partition coefficient F(k) of the clustering, where k is the number of clusters. F(k) is the sum of all squared membership coefficients, divided by the number of observations. Its value is between 1/k and 1. The normalized form of the coefficient is also given. It is defined as (F(k)−1/k)/(1−1/k) , and ranges between 0 and 1. A low value of Dunn’s coefficient indicates a very fuzzy clustering, whereas a value close to 1 indicates a near-crisp clustering. clustering: the clustering vector containing the nearest crisp grouping of observations
library(cluster)
df <- scale(USArrests) # Standardize the data
res.fanny <- fanny(df, 2) # Compute fuzzy clustering with k = 2head(res.fanny$membership, 3) # Membership coefficients [,1] [,2]
Alabama 0.6641977 0.3358023
Alaska 0.6098062 0.3901938
Arizona 0.6862278 0.3137722res.fanny$coeff # Dunn's partition coefficientdunn_coeff normalized
0.5547365 0.1094731 head(res.fanny$clustering) # Observation groups Alabama Alaska Arizona Arkansas California Colorado
1 1 1 2 1 1 To visualize observation groups, use the function fviz_cluster() [factoextra package]:
fviz_cluster(res.fanny, ellipse.type = "norm", repel = TRUE,
palette = "jco", ggtheme = theme_minimal(),
legend = "right")
To evaluate the goodnesss of the clustering results, plot the silhouette coefficient as follow:
fviz_silhouette(res.fanny, palette = "jco",
ggtheme = theme_minimal()) cluster size ave.sil.width
1 1 22 0.32
2 2 28 0.44
Model Based Clustering Essentials
The traditional clustering methods, such as hierarchical clustering (Chapter @ref(agglomerative-clustering)) and k-means clustering (Chapter @ref(kmeans-clustering)), are heuristic and are not based on formal models. Furthermore, k-means algorithm is commonly randomnly initialized, so different runs of k-means will often yield different results. Additionally, k-means requires the user to specify the the optimal number of clusters.
An alternative is model-based clustering, which consider the data as coming from a distribution that is mixture of two or more clusters (Fraley and Raftery 2002, Fraley et al. (2012)). Unlike k-means, the model-based clustering uses a soft assignment, where each data point has a probability of belonging to each cluster.
Concept of model-based clustering
In model-based clustering, the data is considered as coming from a mixture of density.
Each component (i.e. cluster) k is modeled by the normal or Gaussian distribution which is characterized by the parameters:
μk: mean vector, ∑k: covariance matrix, An associated probability in the mixture. Each point has a probability of belonging to each cluster. For example, consider the “old faithful geyser data” [in MASS R package], which can be illustrated as follow using the ggpubr R package:
# Load the data
library("MASS")
Attaching package: ‘MASS’
The following object is masked from ‘package:dplyr’:
selectdata("geyser")
# Scatter plot
library("ggpubr")Loading required package: magrittr
Attaching package: ‘magrittr’
The following object is masked from ‘package:purrr’:
set_names
The following object is masked from ‘package:tidyr’:
extractggscatter(geyser, x = "duration", y = "waiting")+
geom_density2d() # Add 2D density
The plot above suggests at least 3 clusters in the mixture. The shape of each of the 3 clusters appears to be approximately elliptical suggesting three bivariate normal distributions. As the 3 ellipses seems to be similar in terms of volume, shape and orientation, we might anticipate that the three components of this mixture might have homogeneous covariance matrices.
Estimating model parameters
The model parameters can be estimated using the Expectation-Maximization (EM) algorithm initialized by hierarchical model-based clustering. Each cluster k is centered at the means μk , with increased density for points near the mean.
Geometric features (shape, volume, orientation) of each cluster are determined by the covariance matrix ∑k .
Different possible parameterizations of ∑k are available in the R package mclust (see ?mclustModelNames).
The available model options, in mclust package, are represented by identifiers including: EII, VII, EEI, VEI, EVI, VVI, EEE, EEV, VEV and VVV.
The first identifier refers to volume, the second to shape and the third to orientation. E stands for “equal”, V for “variable” and I for “coordinate axes”.
For example:
EVI denotes a model in which the volumes of all clusters are equal (E), the shapes of the clusters may vary (V), and the orientation is the identity (I) or “coordinate axes. EEE means that the clusters have the same volume, shape and orientation in p-dimensional space. VEI means that the clusters have variable volume, the same shape and orientation equal to coordinate axes. Choosing the best model
The Mclust package uses maximum likelihood to fit all these models, with different covariance matrix parameterizations, for a range of k components.
The best model is selected using the Bayesian Information Criterion or BIC. A large BIC score indicates strong evidence for the corresponding model.
library("mclust")
data("diabetes")
head(diabetes, 3)df <- scale(diabetes[, -1]) # Standardize the data
mc <- Mclust(df) # Model-based-clusteringfitting ...
|
| | 0%
|
|= | 1%
|
|= | 2%
|
|== | 2%
|
|=== | 3%
|
|==== | 4%
|
|==== | 5%
|
|===== | 6%
|
|====== | 6%
|
|======= | 7%
|
|======= | 8%
|
|======== | 9%
|
|========= | 9%
|
|========== | 10%
|
|========== | 11%
|
|=========== | 12%
|
|============ | 13%
|
|============= | 13%
|
|============= | 14%
|
|============== | 15%
|
|=============== | 16%
|
|================ | 17%
|
|================= | 18%
|
|================== | 19%
|
|=================== | 20%
|
|==================== | 21%
|
|===================== | 22%
|
|===================== | 23%
|
|====================== | 24%
|
|======================= | 24%
|
|======================== | 25%
|
|======================== | 26%
|
|========================= | 27%
|
|========================== | 28%
|
|=========================== | 28%
|
|=========================== | 29%
|
|============================ | 30%
|
|============================= | 31%
|
|============================== | 31%
|
|============================== | 32%
|
|=============================== | 33%
|
|================================ | 34%
|
|================================= | 35%
|
|================================== | 36%
|
|=================================== | 37%
|
|==================================== | 38%
|
|==================================== | 39%
|
|===================================== | 39%
|
|====================================== | 40%
|
|====================================== | 41%
|
|======================================= | 42%
|
|======================================== | 43%
|
|========================================= | 43%
|
|========================================= | 44%
|
|========================================== | 45%
|
|=========================================== | 46%
|
|============================================ | 46%
|
|============================================ | 47%
|
|============================================= | 48%
|
|============================================== | 49%
|
|=============================================== | 50%
|
|================================================ | 51%
|
|================================================= | 52%
|
|================================================== | 53%
|
|================================================== | 54%
|
|=================================================== | 54%
|
|==================================================== | 55%
|
|===================================================== | 56%
|
|===================================================== | 57%
|
|====================================================== | 57%
|
|======================================================= | 58%
|
|======================================================== | 59%
|
|======================================================== | 60%
|
|========================================================= | 61%
|
|========================================================== | 61%
|
|========================================================== | 62%
|
|=========================================================== | 63%
|
|============================================================ | 64%
|
|============================================================= | 65%
|
|============================================================== | 66%
|
|=============================================================== | 67%
|
|================================================================ | 68%
|
|================================================================ | 69%
|
|================================================================= | 69%
|
|================================================================== | 70%
|
|=================================================================== | 71%
|
|=================================================================== | 72%
|
|==================================================================== | 72%
|
|===================================================================== | 73%
|
|====================================================================== | 74%
|
|====================================================================== | 75%
|
|======================================================================= | 76%
|
|======================================================================== | 76%
|
|========================================================================= | 77%
|
|========================================================================= | 78%
|
|========================================================================== | 79%
|
|=========================================================================== | 80%
|
|============================================================================ | 81%
|
|============================================================================= | 82%
|
|============================================================================== | 83%
|
|=============================================================================== | 84%
|
|================================================================================ | 85%
|
|================================================================================= | 86%
|
|================================================================================= | 87%
|
|================================================================================== | 87%
|
|=================================================================================== | 88%
|
|==================================================================================== | 89%
|
|==================================================================================== | 90%
|
|===================================================================================== | 91%
|
|====================================================================================== | 91%
|
|======================================================================================= | 92%
|
|======================================================================================= | 93%
|
|======================================================================================== | 94%
|
|========================================================================================= | 94%
|
|========================================================================================== | 95%
|
|========================================================================================== | 96%
|
|=========================================================================================== | 97%
|
|============================================================================================ | 98%
|
|============================================================================================= | 98%
|
|============================================================================================= | 99%
|
|==============================================================================================| 100%summary(mc) # Print a summary----------------------------------------------------
Gaussian finite mixture model fitted by EM algorithm
----------------------------------------------------
Mclust VVV (ellipsoidal, varying volume, shape, and orientation) model with 3 components:
log.likelihood n df BIC ICL
-169.0918 145 29 -482.5089 -501.4368
Clustering table:
1 2 3
81 36 28 For this data, it can be seen that model-based clustering selected a model with three components (i.e. clusters). The optimal selected model name is VVV model. That is the three components are ellipsoidal with varying volume, shape, and orientation. The summary contains also the clustering table specifying the number of observations in each clusters.
You can access to the results as follow:
mc$modelName # Optimal selected model ==> "VVV"[1] "VVV"mc$G # Optimal number of cluster => 3[1] 3head(mc$z, 30) # Probality to belong to a given cluster [,1] [,2] [,3]
1 0.9907874 0.008870671 3.419770e-04
2 0.9824097 0.017586177 4.107625e-06
3 0.9779945 0.021948580 5.690665e-05
4 0.9777076 0.022077703 2.147003e-04
5 0.9217797 0.078151587 6.868319e-05
6 0.9864768 0.012835588 6.876134e-04
7 0.9436635 0.056211528 1.249607e-04
8 0.9771351 0.022689680 1.752408e-04
9 0.9742319 0.025580223 1.878661e-04
10 0.9842886 0.015700736 1.061526e-05
11 0.9608016 0.039063321 1.350300e-04
12 0.9820004 0.017881233 1.184090e-04
13 0.9818349 0.018011976 1.531207e-04
14 0.9751132 0.024576982 3.097991e-04
15 0.9676354 0.032185044 1.795065e-04
16 0.9757508 0.020466961 3.782239e-03
17 0.9867246 0.013089300 1.861052e-04
18 0.9719509 0.027856308 1.927908e-04
19 0.9854911 0.014497880 1.099339e-05
20 0.9878355 0.012130965 3.352455e-05
21 0.9844490 0.015337570 2.134332e-04
22 0.9873609 0.012616432 2.266848e-05
23 0.9799708 0.019894253 1.349581e-04
24 0.9803321 0.019540366 1.275444e-04
25 0.6609733 0.339015667 1.108037e-05
26 0.9555813 0.038816298 5.602419e-03
27 0.9780961 0.021784401 1.195137e-04
28 0.9761452 0.023700606 1.542353e-04
29 0.9848905 0.014928363 1.810939e-04
30 0.9499927 0.049921182 8.607427e-05head(mc$classification, 10) # Cluster assignement of each observation 1 2 3 4 5 6 7 8 9 10
1 1 1 1 1 1 1 1 1 1 Visualizing model-based clustering
Model-based clustering results can be drawn using the base function plot.Mclust() [in mclust package]. Here we’ll use the function fviz_mclust() [in factoextra package] to create beautiful plots based on ggplot2.
In the situation, where the data contain more than two variables, fviz_mclust() uses a principal component analysis to reduce the dimensionnality of the data. The first two principal components are used to produce a scatter plot of the data. However, if you want to plot the data using only two variables of interest, let say here c(“insulin”, “sspg”), you can specify that in the fviz_mclust() function using the argument choose.vars = c(“insulin”, “sspg”).
library(factoextra)
# BIC values used for choosing the number of clusters
fviz_mclust(mc, "BIC", palette = "jco")
# Classification: plot showing the clustering
fviz_mclust(mc, "classification", geom = "point",
pointsize = 1.5, palette = "jco")
# Classification uncertainty
fviz_mclust(mc, "uncertainty", palette = "jco")
DBSCAN: Density-Based Clustering Essentials
DBSCAN (Density-Based Spatial Clustering and Application with Noise), is a density-based clusering algorithm, introduced in Ester et al. 1996, which can be used to identify clusters of any shape in a data set containing noise and outliers.
The basic idea behind the density-based clustering approach is derived from a human intuitive clustering method. For instance, by looking at the figure below, one can easily identify four clusters along with several points of noise, because of the differences in the density of points.
Clusters are dense regions in the data space, separated by regions of lower density of points. The DBSCAN algorithm is based on this intuitive notion of “clusters” and “noise”. The key idea is that for each point of a cluster, the neighborhood of a given radius has to contain at least a minimum number of points.
Why DBSCAN?
Partitioning methods (K-means, PAM clustering) and hierarchical clustering are suitable for finding spherical-shaped clusters or convex clusters. In other words, they work well only for compact and well separated clusters. Moreover, they are also severely affected by the presence of noise and outliers in the data.
Unfortunately, real life data can contain: i) clusters of arbitrary shape such as those shown in the figure below (oval, linear and “S” shape clusters); ii) many outliers and noise.
The figure below shows a data set containing nonconvex clusters and outliers/noises. The simulated data set multishapes [in factoextra package] is used.
data("multishapes")
df <- multishapes[, 1:2]
set.seed(123)
km.res <- kmeans(df, 5, nstart = 25)
fviz_cluster(km.res, df, geom = "point",
ellipse= FALSE, show.clust.cent = FALSE,
palette = "jco", ggtheme = theme_classic())
Computing DBSCAN
Here, we’ll use the R package fpc to compute DBSCAN. It’s also possible to use the package dbscan, which provides a faster re-implementation of DBSCAN algorithm compared to the fpc package.
We’ll also use the factoextra package for visualizing clusters.
First, install the packages as follow:
#install.packages("fpc")
install.packages("dbscan")Installing package into ‘/Users/nanaakwasiabayieboateng/Library/R/3.4/library’
(as ‘lib’ is unspecified)
trying URL 'https://cran.rstudio.com/bin/macosx/el-capitan/contrib/3.4/dbscan_1.1-1.tgz'
Content type 'application/x-gzip' length 3129485 bytes (3.0 MB)
==================================================
downloaded 3.0 MB
The downloaded binary packages are in
/var/folders/mj/w1gxzjcd0qx2cw_0690z7y640000gn/T//RtmpDAVf3z/downloaded_packages# Load the data
data("multishapes", package = "factoextra")
df <- multishapes[, 1:2]
# Compute DBSCAN using fpc package
library("fpc")
set.seed(123)
db <- fpc::dbscan(df, eps = 0.15, MinPts = 5)
# Plot DBSCAN results
library("factoextra")Loading required package: ggplot2
Welcome! Related Books: `Practical Guide To Cluster Analysis in R` at https://goo.gl/13EFCZfviz_cluster(db, data = df, stand = FALSE,
ellipse = FALSE, show.clust.cent = FALSE,
geom = "point",palette = "jco", ggtheme = theme_classic())
print(db)dbscan Pts=1100 MinPts=5 eps=0.15
0 1 2 3 4 5
border 31 24 1 5 7 1
seed 0 386 404 99 92 50
total 31 410 405 104 99 51In the table above, column names are cluster number. Cluster 0 corresponds to outliers (black points in the DBSCAN plot). The function print.dbscan() shows a statistic of the number of points belonging to the clusters that are seeds and border points.
# Cluster membership. Noise/outlier observations are coded as 0
# A random subset is shown
db$cluster[sample(1:1089, 20)] [1] 3 2 4 0 1 2 4 2 2 0 2 2 2 1 4 1 1 1 0 4Method for determining the optimal eps value
The method proposed here consists of computing the k-nearest neighbor distances in a matrix of points.
The idea is to calculate, the average of the distances of every point to its k nearest neighbors. The value of k will be specified by the user and corresponds to MinPts.
Next, these k-distances are plotted in an ascending order. The aim is to determine the “knee”, which corresponds to the optimal eps parameter.
A knee corresponds to a threshold where a sharp change occurs along the k-distance curve.
The function kNNdistplot() [in dbscan package] can be used to draw the k-distance plot:
dbscan::kNNdistplot(df, k = 5)
abline(h = 0.15, lty = 2)
HCPC - Hierarchical Clustering on Principal Components: Essentials
Clustering is one of the important data mining methods for discovering knowledge in multivariate data sets. The goal is to identify groups (i.e. clusters) of similar objects within a data set of interest. To learn more about clustering, you can read our book entitled “Practical Guide to Cluster Analysis in R” (https://goo.gl/DmJ5y5).
Briefly, the two most common clustering strategies are:
Hierarchical clustering, used for identifying groups of similar observations in a data set. Partitioning clustering such as k-means algorithm, used for splitting a data set into several groups. The HCPC (Hierarchical Clustering on Principal Components) approach allows us to combine the three standard methods used in multivariate data analyses (Husson, Josse, and J. 2010):
Principal component methods (PCA, CA, MCA, FAMD, MFA), Hierarchical clustering and Partitioning clustering, particularly the k-means method.
Why HCPC
Combining principal component methods and clustering methods are useful in at least three situations.
Case 1: Continuous variables
In the situation where you have a multidimensional data set containing multiple continuous variables, the principal component analysis (PCA) can be used to reduce the dimension of the data into few continuous variables containing the most important information in the data. Next, you can perform cluster analysis on the PCA results.
The PCA step can be considered as a denoising step which can lead to a more stable clustering. This might be very useful if you have a large data set with multiple variables, such as in gene expression data.
Case 2: Clustering on categorical data
In order to perform clustering analysis on categorical data, the correspondence analysis (CA, for analyzing contingency table) and the multiple correspondence analysis (MCA, for analyzing multidimensional categorical variables) can be used to transform categorical variables into a set of few continuous variables (the principal components). The cluster analysis can be then applied on the (M)CA results.
In this case, the (M)CA method can be considered as pre-processing steps which allow to compute clustering on categorical data.
Case 3: Clustering on mixed data
When you have a mixed data of continuous and categorical variables, you can first perform FAMD (factor analysis of mixed data) or MFA (multiple factor analysis). Next, you can apply cluster analysis on the FAMD/MFA outputs.
Algorithm of the HCPC method
The algorithm of the HCPC method, as implemented in the FactoMineR package, can be summarized as follow:
Compute principal component methods: PCA, (M)CA or MFA depending on the types of variables in the data set and the structure of the data set. At this step, you can choose the number of dimensions to be retained in the output by specifying the argument ncp. The default value is 5.
Compute hierarchical clustering: Hierarchical clustering is performed using the Ward’s criterion on the selected principal components. Ward criterion is used in the hierarchical clustering because it is based on the multidimensional variance like principal component analysis.
Choose the number of clusters based on the hierarchical tree: An initial partitioning is performed by cutting the hierarchical tree.
Perform K-means clustering to improve the initial partition obtained from hierarchical clustering. The final partitioning solution, obtained after consolidation with k-means, can be (slightly) different from the one obtained with the hierarchical clustering.
Computation
R packages
We’ll use two R packages: i) FactoMineR for computing HCPC and ii) factoextra for visualizing the results.
To install the packages, type this:
library(factoextra)
library(FactoMineR)The function HCPC() [in FactoMineR package] can be used to compute hierarchical clustering on principal components.
A simplified format is:
#HCPC(res, nb.clust = 0, min = 3, max = NULL, graph = TRUE)res: Either the result of a factor analysis or a data frame. nb.clust: an integer specifying the number of clusters. Possible values are: 0: the tree is cut at the level the user clicks on -1: the tree is automatically cut at the suggested level Any positive integer: the tree is cut with nb.clusters clusters min, max: the minimum and the maximum number of clusters to be generated, respectively graph: if TRUE, graphics are displayed Case of continuous variables
We start by computing again the principal component analysis (PCA). The argument ncp = 3 is used in the function PCA() to keep only the first three principal components. Next, the HCPC is applied on the result of the PCA.
# Compute PCA with ncp = 3
res.pca <- PCA(USArrests, ncp = 3, graph = FALSE)
# Compute hierarchical clustering on principal components
res.hcpc <- HCPC(res.pca, graph = FALSE)To visualize the dendrogram generated by the hierarchical clustering, we’ll use the function fviz_dend() [factoextra package]:
fviz_dend(res.hcpc,
cex = 0.7, # Label size
palette = "jco", # Color palette see ?ggpubr::ggpar
rect = TRUE, rect_fill = TRUE, # Add rectangle around groups
rect_border = "jco", # Rectangle color
labels_track_height = 0.8 # Augment the room for labels
)
It’s possible to visualize individuals on the principal component map and to color individuals according to the cluster they belong to. The function fviz_cluster() [in factoextra] can be used to visualize individuals clusters.
fviz_cluster(res.hcpc,
repel = TRUE, # Avoid label overlapping
show.clust.cent = TRUE, # Show cluster centersYou can also draw a three dimensional plot combining the hierarchical clustering and the factorial map using the R base function plot():
# Principal components + tree
plot(res.hcpc, choice = "3D.map")
The function HCPC() returns a list containing:
data.clust: The original data with a supplementary column called class containing the partition. desc.var: The variables describing clusters desc.ind: The more typical individuals of each cluster desc.axes: The axes describing clusters To display the original data with cluster assignments, type this:
head(res.hcpc$data.clust, 10)In the table above, the last column contains the cluster assignments.
To display quantitative variables that describe the most each cluster, type this:
res.hcpc$desc.var$quanti$`1`
v.test Mean in category Overall mean sd in category Overall sd p.value
UrbanPop -3.898420 52.07692 65.540 9.691087 14.329285 9.682222e-05
Murder -4.030171 3.60000 7.788 2.269870 4.311735 5.573624e-05
Rape -4.052061 12.17692 21.232 3.130779 9.272248 5.076842e-05
Assault -4.638172 78.53846 170.760 24.700095 82.500075 3.515038e-06
$`2`
v.test Mean in category Overall mean sd in category Overall sd p.value
UrbanPop 2.793185 73.87500 65.540 8.652131 14.329285 0.005219187
Murder -2.374121 5.65625 7.788 1.594902 4.311735 0.017590794
$`3`
v.test Mean in category Overall mean sd in category Overall sd p.value
Murder 4.357187 13.9375 7.788 2.433587 4.311735 1.317449e-05
Assault 2.698255 243.6250 170.760 46.540137 82.500075 6.970399e-03
UrbanPop -2.513667 53.7500 65.540 7.529110 14.329285 1.194833e-02
$`4`
v.test Mean in category Overall mean sd in category Overall sd p.value
Rape 5.352124 33.19231 21.232 6.996643 9.272248 8.692769e-08
Assault 4.356682 257.38462 170.760 41.850537 82.500075 1.320491e-05
UrbanPop 3.028838 76.00000 65.540 10.347798 14.329285 2.454964e-03
Murder 2.913295 10.81538 7.788 2.001863 4.311735 3.576369e-03From the output above, it can be seen that:
the variables UrbanPop, Murder, Rape and Assault are most significantly associated with the cluster 1. For example, the mean value of the Assault variable in cluster 1 is 78.53 which is less than it’s overall mean (170.76) across all clusters. Therefore, It can be conclude that the cluster 1 is characterized by a low rate of Assault compared to all clusters.
the variables UrbanPop and Murder are most significantly associated with the cluster 2.
…and so on …
res.hcpc$desc.axes$quanti$`1`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.1 -5.175764 -1.964502 -5.639933e-16 0.6192556 1.574878 2.269806e-07
$`2`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.2 3.585635 0.7428712 -5.369316e-16 0.6137936 0.9948694 0.0003362596
$`3`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.1 2.058338 1.0610731 -5.639933e-16 0.5146613 1.5748783 3.955769e-02
Dim.3 2.028887 0.3965588 3.535366e-17 0.3714503 0.5971291 4.246985e-02
Dim.2 -4.536594 -1.4773302 -5.369316e-16 0.5750284 0.9948694 5.717010e-06
$`4`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.1 4.986474 1.892656 -5.639933e-16 0.6126035 1.574878 6.149115e-07Finally, representative individuals of each cluster can be extracted as follow:
res.hcpc$desc.ind$paraCluster: 1
Idaho South Dakota Maine Iowa New Hampshire
0.3674381 0.4993032 0.5012072 0.5533105 0.5891145
-----------------------------------------------------------------------------
Cluster: 2
Ohio Oklahoma Pennsylvania Kansas Indiana
0.2796100 0.5047549 0.5088363 0.6039091 0.7100820
-----------------------------------------------------------------------------
Cluster: 3
Alabama South Carolina Georgia Tennessee Louisiana
0.3553460 0.5335189 0.6136865 0.8522640 0.8780872
-----------------------------------------------------------------------------
Cluster: 4
Michigan Arizona New Mexico Maryland Texas
0.3246254 0.4532480 0.5176322 0.9013514 0.9239792 Case of categorical variables
For categorical variables, compute CA or MCA and then apply the function HCPC() on the results as described above.
Here, we’ll use the tea data [in FactoMineR] as demo data set: Rows represent the individuals and columns represent categorical variables.
We start, by performing an MCA on the individuals. We keep the first 20 axes of the MCA which retain 87% of the information.
# Loading data
library(FactoMineR)
data(tea)
# Performing MCA
res.mca <- MCA(tea,
ncp = 20, # Number of components kept
quanti.sup = 19, # Quantitative supplementary variables
quali.sup = c(20:36), # Qualitative supplementary variables
graph=FALSE)Next, we apply hierarchical clustering on the results of the MCA:
res.hcpc <- HCPC (res.mca, graph = FALSE, max = 3)Chi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrectChi-squared approximation may be incorrect# Dendrogram
fviz_dend(res.hcpc, show_labels = FALSE)
# Individuals facor map
fviz_cluster(res.hcpc, geom = "point", main = "Factor map")
As mentioned above, clusters can be described by i) variables and/or categories, ii) principal axes and iii) individuals. In the example below, we display only a subset of the results.
Description by variables and categories
# Description by variables
res.hcpc$desc.var$test.chi2 p.value df
where 8.465616e-79 4
how 3.144675e-47 4
price 1.862462e-28 10
tearoom 9.624188e-19 2
pub 8.539893e-10 2
friends 6.137618e-08 2
resto 3.537876e-07 2
How 3.616532e-06 6
Tea 1.778330e-03 4
sex 1.789593e-03 2
frequency 1.973274e-03 6
work 3.052988e-03 2
tea.time 3.679599e-03 2
lunch 1.052478e-02 2
dinner 2.234313e-02 2
always 3.600913e-02 2
sugar 3.685785e-02 2
sophisticated 4.077297e-02 2# Description by variable categories
res.hcpc$desc.var$category$`1`
Cla/Mod Mod/Cla Global p.value v.test
where=chain store 85.937500 93.750000 64.000000 2.094419e-40 13.307475
how=tea bag 84.117647 81.250000 56.666667 1.478564e-25 10.449142
tearoom=Not.tearoom 70.661157 97.159091 80.666667 1.082077e-18 8.826287
price=p_branded 83.157895 44.886364 31.666667 1.631861e-09 6.030764
pub=Not.pub 67.088608 90.340909 79.000000 1.249296e-08 5.692859
friends=Not.friends 76.923077 45.454545 34.666667 2.177180e-06 4.736242
resto=Not.resto 64.705882 81.250000 73.666667 4.546462e-04 3.506146
price=p_private label 90.476190 10.795455 7.000000 1.343844e-03 3.206448
tea.time=Not.tea time 67.938931 50.568182 43.666667 4.174032e-03 2.864701
How=alone 64.102564 71.022727 65.000000 9.868387e-03 2.580407
work=Not.work 63.380282 76.704545 71.000000 1.036429e-02 2.563432
sugar=sugar 66.206897 54.545455 48.333333 1.066744e-02 2.553408
always=Not.always 63.959391 71.590909 65.666667 1.079912e-02 2.549133
price=p_unknown 91.666667 6.250000 4.000000 1.559798e-02 2.418189
frequency=1 to 2/week 75.000000 18.750000 14.666667 1.649092e-02 2.397866
frequency=1/day 68.421053 36.931818 31.666667 1.958790e-02 2.334149
age_Q=15-24 68.478261 35.795455 30.666667 2.179803e-02 2.293869
price=p_cheap 100.000000 3.977273 2.333333 2.274539e-02 2.277684
lunch=Not.lunch 61.328125 89.204545 85.333333 2.681490e-02 2.214202
SPC=senior 42.857143 8.522727 11.666667 4.813710e-02 -1.976156
lunch=lunch 43.181818 10.795455 14.666667 2.681490e-02 -2.214202
always=always 48.543689 28.409091 34.333333 1.079912e-02 -2.549133
sugar=No.sugar 51.612903 45.454545 51.666667 1.066744e-02 -2.553408
work=work 47.126437 23.295455 29.000000 1.036429e-02 -2.563432
tea.time=tea time 51.479290 49.431818 56.333333 4.174032e-03 -2.864701
How=lemon 30.303030 5.681818 11.000000 5.943089e-04 -3.434198
resto=resto 41.772152 18.750000 26.333333 4.546462e-04 -3.506146
How=other 0.000000 0.000000 3.000000 2.952904e-04 -3.619397
price=p_variable 44.642857 28.409091 37.333333 1.595638e-04 -3.775692
frequency=+2/day 45.669291 32.954545 42.333333 9.872288e-05 -3.893709
friends=friends 48.979592 54.545455 65.333333 2.177180e-06 -4.736242
how=unpackaged 19.444444 3.977273 12.000000 4.328211e-07 -5.053925
pub=pub 26.984127 9.659091 21.000000 1.249296e-08 -5.692859
where=tea shop 6.666667 1.136364 10.000000 4.770573e-10 -6.226471
price=p_upscale 18.867925 5.681818 17.666667 9.472539e-11 -6.475138
how=tea bag+unpackaged 27.659574 14.772727 31.333333 1.927326e-13 -7.353743
tearoom=tearoom 8.620690 2.840909 19.333333 1.082077e-18 -8.826287
where=chain store+tea shop 11.538462 5.113636 26.000000 1.133459e-23 -10.029275
$`2`
Cla/Mod Mod/Cla Global p.value v.test
where=tea shop 90.000000 84.375 10.00000 3.703402e-30 11.410559
how=unpackaged 66.666667 75.000 12.00000 5.346850e-20 9.156781
price=p_upscale 49.056604 81.250 17.66667 2.392655e-17 8.472945
Tea=green 27.272727 28.125 11.00000 4.436713e-03 2.845318
sophisticated=sophisticated 13.488372 90.625 71.66667 8.080918e-03 2.648670
sex=M 16.393443 62.500 40.66667 9.511848e-03 2.593088
resto=Not.resto 13.122172 90.625 73.66667 1.587879e-02 2.411690
dinner=dinner 28.571429 18.750 7.00000 1.874042e-02 2.350655
escape.exoticism=Not.escape-exoticism 14.556962 71.875 52.66667 2.177458e-02 2.294277
how=tea bag+unpackaged 5.319149 15.625 31.33333 3.876799e-02 -2.066641
escape.exoticism=escape-exoticism 6.338028 28.125 47.33333 2.177458e-02 -2.294277
dinner=Not.dinner 9.318996 81.250 93.00000 1.874042e-02 -2.350655
resto=resto 3.797468 9.375 26.33333 1.587879e-02 -2.411690
Tea=Earl Grey 7.253886 43.750 64.33333 1.314753e-02 -2.479748
sex=F 6.741573 37.500 59.33333 9.511848e-03 -2.593088
sophisticated=Not.sophisticated 3.529412 9.375 28.33333 8.080918e-03 -2.648670
where=chain store+tea shop 2.564103 6.250 26.00000 3.794134e-03 -2.894789
price=p_variable 3.571429 12.500 37.33333 1.349384e-03 -3.205264
age_Q=15-24 2.173913 6.250 30.66667 6.100227e-04 -3.427119
price=p_branded 2.105263 6.250 31.66667 4.024289e-04 -3.538486
how=tea bag 1.764706 9.375 56.66667 5.537403e-09 -5.830161
where=chain store 1.562500 9.375 64.00000 1.664577e-11 -6.732775
$`3`
Cla/Mod Mod/Cla Global p.value v.test
where=chain store+tea shop 85.897436 72.826087 26.00000 5.730651e-34 12.150084
how=tea bag+unpackaged 67.021277 68.478261 31.33333 1.382641e-19 9.053653
tearoom=tearoom 77.586207 48.913043 19.33333 1.252051e-16 8.278053
pub=pub 63.492063 43.478261 21.00000 1.126679e-09 6.090345
friends=friends 41.836735 89.130435 65.33333 1.429181e-09 6.052158
price=p_variable 51.785714 63.043478 37.33333 1.572243e-09 6.036775
resto=resto 54.430380 46.739130 26.33333 2.406386e-07 5.164845
How=other 100.000000 9.782609 3.00000 1.807938e-05 4.287379
frequency=+2/day 41.732283 57.608696 42.33333 4.237330e-04 3.524844
tea.time=tea time 38.461538 70.652174 56.33333 8.453564e-04 3.337500
work=work 44.827586 42.391304 29.00000 9.079377e-04 3.317602
sex=F 37.078652 71.739130 59.33333 3.494245e-03 2.920541
lunch=lunch 50.000000 23.913043 14.66667 3.917102e-03 2.884762
How=lemon 51.515152 18.478261 11.00000 8.747530e-03 2.621767
sugar=No.sugar 36.129032 60.869565 51.66667 3.484061e-02 2.110206
home=home 31.615120 100.000000 97.00000 3.506563e-02 2.107600
home=Not.home 0.000000 0.000000 3.00000 3.506563e-02 -2.107600
sugar=sugar 24.827586 39.130435 48.33333 3.484061e-02 -2.110206
price=p_private label 9.523810 2.173913 7.00000 2.370629e-02 -2.261856
how=unpackaged 13.888889 5.434783 12.00000 1.645107e-02 -2.398752
How=alone 25.128205 53.260870 65.00000 5.300881e-03 -2.788157
lunch=Not.lunch 27.343750 76.086957 85.33333 3.917102e-03 -2.884762
sex=M 21.311475 28.260870 40.66667 3.494245e-03 -2.920541
Tea=green 9.090909 3.260870 11.00000 2.545816e-03 -3.017842
frequency=1 to 2/week 11.363636 5.434783 14.66667 1.604219e-03 -3.155139
work=Not.work 24.882629 57.608696 71.00000 9.079377e-04 -3.317602
tea.time=Not.tea time 20.610687 29.347826 43.66667 8.453564e-04 -3.337500
where=tea shop 3.333333 1.086957 10.00000 1.466234e-04 -3.796720
price=p_branded 14.736842 15.217391 31.66667 2.746948e-05 -4.193490
resto=Not.resto 22.171946 53.260870 73.66667 2.406386e-07 -5.164845
friends=Not.friends 9.615385 10.869565 34.66667 1.429181e-09 -6.052158
pub=Not.pub 21.940928 56.521739 79.00000 1.126679e-09 -6.090345
how=tea bag 14.117647 26.086957 56.66667 1.082059e-12 -7.119644
tearoom=Not.tearoom 19.421488 51.086957 80.66667 1.252051e-16 -8.278053
where=chain store 12.500000 26.086957 64.00000 1.711522e-19 -9.030332Description by principal components
res.hcpc$desc.axes$quanti.var
Eta2 P-value
Dim.2 0.66509105 2.828937e-71
Dim.1 0.63497903 1.009707e-65
Dim.4 0.11231020 2.073924e-08
Dim.14 0.03141943 8.732913e-03
Dim.6 0.02358138 2.890373e-02
$quanti
$quanti$`1`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.6 2.647552 0.03433626 -2.721637e-17 0.2655618 0.2671712 8.107689e-03
Dim.2 -7.796641 -0.13194656 -6.207419e-17 0.1813156 0.3486355 6.357699e-15
Dim.1 -12.409741 -0.23196088 -1.678981e-16 0.2143767 0.3850642 2.314001e-35
$quanti$`2`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.2 13.918285 0.81210870 -6.207419e-17 0.2340345 0.3486355 4.905356e-44
Dim.4 4.350620 0.20342610 7.249699e-19 0.3700048 0.2793822 1.357531e-05
Dim.14 2.909073 0.10749165 4.512196e-17 0.2161509 0.2207818 3.625025e-03
Dim.13 2.341566 0.08930402 1.266782e-17 0.1606616 0.2278809 1.920305e-02
Dim.3 2.208179 0.11087544 -4.161891e-17 0.2449710 0.3000159 2.723180e-02
Dim.11 -2.234447 -0.08934293 6.504924e-17 0.2066708 0.2389094 2.545367e-02
$quanti$`3`
v.test Mean in category Overall mean sd in category Overall sd p.value
Dim.1 13.485906 0.45155993 -1.678981e-16 0.2516544 0.3850642 1.893256e-41
Dim.6 -2.221728 -0.05161581 -2.721637e-17 0.2488566 0.2671712 2.630166e-02
Dim.4 -4.725270 -0.11479621 7.249699e-19 0.2924881 0.2793822 2.298093e-06
attr(,"class")
[1] "catdes" "list " Description by individuals
res.hcpc$desc.ind$paraCluster: 1
285 152 166 143 71
0.5884476 0.6242123 0.6242123 0.6244176 0.6478185
-----------------------------------------------------------------------------
Cluster: 2
31 95 53 182 202
0.6620553 0.7442013 0.7610437 0.7948663 0.8154826
-----------------------------------------------------------------------------
Cluster: 3
172 33 233 18 67
0.7380497 0.7407711 0.7503006 0.7572188 0.7701598 Summary
We described how to compute hierarchical clustering on principal components (HCPC). This approach is useful in situations, including:
When you have a large data set containing continuous variables, a principal component analysis can be used to reduce the dimension of the data before the hierarchical clustering analysis.
When you have a data set containing categorical variables, a (Multiple)Correspondence analysis can be used to transform the categorical variables into few continuous principal components, which can be used as the input of the cluster analysis.
We used the FactoMineR package to compute the HCPC and the factoextra R package for ggplot2-based elegant data visualization.
LS0tCnRpdGxlOiAiU29tZSBDbHVzdGVyaW5nIEFsZ29yaXRobXMiCm91dHB1dDogaHRtbF9ub3RlYm9vawphdXRob3I6IE5hbmEgQm9hdGVuZwpkZl9wcmludDogcGFnZWQKVGltZTogJ2ByIFN5cy50aW1lKClgJwpkYXRlOiAiYHIgZm9ybWF0KFN5cy50aW1lKCksICclQiAlZCwgJVknKWAiCi0tLQoKVGhpcyBhcnRpY2xlIGRlc2NyaWJlcyBzZXZlcmFsIGNsdXN0ZXJpbmcgYWxnb3JpdGhtcyBpbXBsZW1lbnRlZCBpbiBSLgoKYGBge3J9CgojaW5zdGFsbC5wYWNrYWdlcygiZmFjdG9leHRyYSIpCmxpYnJhcnkoUnRzbmUpCmxpYnJhcnkodHNuZSkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocmlvKQpsaWJyYXJ5KFJDb2xvckJyZXdlcikKbGlicmFyeShrbml0cikKbGlicmFyeSgiZmFjdG9leHRyYSIpCmxpYnJhcnkoY2x1c3RlcikgCgoKYGBgCgoKCmBgYHtyfQojIyBjYWxsaW5nIHRoZSBpbnN0YWxsZWQgcGFja2FnZQp0cmFpbjwtIGltcG9ydCgiL1VzZXJzL25hbmFha3dhc2lhYmF5aWVib2F0ZW5nL0RvY3VtZW50cy9tZW1waGlzY2xhc3Nlc2Jvb2tzL0RhdGFNaW5pbmdzY2llbmNlL0NsdXN0ZXJpbmcvQ3Jvd2Rzb3VyY2VkIE1hcHBpbmcvdHJhaW5pbmcuY3N2IikKCmhlYWQodHJhaW4pCgp0cmFpbiRjbGFzcz1hcy5mYWN0b3IodHJhaW4kY2xhc3MpCmBgYAoKYGBge3J9CnN0cih0cmFpbikKdHJhaW49dHJhaW4lPiVtdXRhdGVfaWYoaXMubnVtZXJpYyxhcy5mYWN0b3IpCgpgYGAKCgoKYGBge3J9CiMgSy1NZWFucyBDbHVzdGVyaW5nIHdpdGggMyBjbHVzdGVycwpmaXQgPC0ga21lYW5zKGlyaXNbLDE6NF0sIDMpCgojIENsdXN0ZXIgUGxvdCBhZ2FpbnN0IDFzdCAyIHByaW5jaXBhbCBjb21wb25lbnRzCgpjbHVzcGxvdChpcmlzWywxOjRdLCBmaXQkY2x1c3RlciwgY29sb3I9VFJVRSwgc2hhZGU9VFJVRSwgbGFiZWxzPTMsIGxpbmVzPTApCgpgYGAKCgpgYGB7cn0KZml0JT4laGVhZCgpCgpgYGAKCgpgYGB7cn0KIyBLLU1lYW5zIENsdXN0ZXJpbmcgd2l0aCA2IGNsdXN0ZXJzCmZpdCA8LSBrbWVhbnModHJhaW5bLC0xXSwgNikKCiMgQ2x1c3RlciBQbG90IGFnYWluc3QgMXN0IDIgcHJpbmNpcGFsIGNvbXBvbmVudHMKCmNsdXNwbG90KHRyYWluWywtMV0sIGZpdCRjbHVzdGVyLCBjb2xvcj1UUlVFLCBzaGFkZT1UUlVFLCBsYWJlbHM9NiwgbGluZXM9MCkKCgpgYGAKCgoKCiMjIyMgIEhpZXJyYWNoaWNhbCBDbHVzdGVyaW5nCgpDb21wdXRlIHRoZSBkaXN0YW5jZXMuCgpgYGB7cn0KZGlzdGFuY2VzID0gZGlzdCh0cmFpblssLTFdLCBtZXRob2QgPSAiZXVjbGlkZWFuIikKYGBgCgpUaGVyZSBhcmUgdmFyaW91cyB0ZWNobmlxdWVzIGluIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nLiBIZXJlLCB3ZSBhcmUgY29uc2lkZXJhdGluZyBXYXJkJ3MgbWV0aG9kIHdoaWNoCmNvbnNpZGVycyBkaXN0YW5jZXMgYmV0d2VlbiBjZW50cm9pZHMgYW5kIHZhcmlhbmNlcy4KCmBgYHtyfQpmaXRfaGM8LWhjbHVzdChkaXN0YW5jZXMsIG1ldGhvZCA9ICJ3YXJkLkQiKQoKYGBgCgoKCmBgYHtyfQpwbG90KGZpdF9oYykKYGBgCgoKCgoKCgoKCgpgYGB7cn0KcGxvdChmaXRfaGMpCnJlY3QuaGNsdXN0KGZpdF9oYywgayA9IDYsIGJvcmRlciA9ICJibHVlIikKYGBgCgpgYGB7cn0KcGxvdChmaXRfaGMpICMgZGlzcGxheSBkZW5kb2dyYW0KZ3JvdXBzIDwtIGN1dHJlZShmaXRfaGMsIGs9MykgIyBjdXQgdHJlZSBpbnRvIDUgY2x1c3RlcnMKIyBkcmF3IGRlbmRvZ3JhbSB3aXRoIHJlZCBib3JkZXJzIGFyb3VuZCB0aGUgNSBjbHVzdGVycwpyZWN0LmhjbHVzdChmaXRfaGMsIGs9MywgYm9yZGVyPSJyZWQiKQpgYGAKCgoKYGBge3J9CiNsaWJyYXJ5KHJwdWQpCiNpbnN0YWxsLnBhY2thZ2VzKCJycHVkIikKYGBgCgoKCgojIyMjIGstbWVhbnMKCmBgYHtyfQpmaXRfa20gPSBrbWVhbnModHJhaW5bLC0xXSwgY2VudGVycyA9IDYsIG5zdGFydCA9IDIwKQoKbmFtZXMoZml0X2ttKQoKYXR0cmlidXRlcyhmaXRfa20pCgpgYGAKCgoKCgpgYGB7cn0KCmZpdF9rbSRjZW50ZXJzCgpgYGAKCgoKYGBge3J9CgojZml0X2ttJT4laGVhZCgpCgp0YWJsZShmaXRfa20kY2x1c3RlciwgdHJhaW4kY2xhc3MpCgpgYGAKCgpgYGB7cn0KZml0X2ttJGNsdXN0ZXIgPC0gYXMuZmFjdG9yKGZpdF9rbSRjbHVzdGVyICkKZ2dwbG90KHRyYWluLCBhZXModHJhaW5bLDNdLHRyYWluWywyXSwgY29sb3IgPSBmaXRfa20kY2x1c3RlcikpICsgZ2VvbV9wb2ludCgpCmdncGxvdCh0cmFpbiwgYWVzKHRyYWluWyw0XSx0cmFpblssNV0sIGNvbG9yID0gZml0X2ttJGNsdXN0ZXIpKSArIGdlb21fcG9pbnQoKQpuYW1lcyh0cmFpbikKYGBgCgoKIyMjIyBPcHRpbWFsIE51bWJlciBvZiBDbHVzdGVycwoKQSBmdW5kYW1lbnRhbCBxdWVzdGlvbiBpcyBob3cgdG8gZGV0ZXJtaW5lIHRoZSB2YWx1ZSBvZiB0aGUgcGFyYW1ldGVyIC4gSWYgd2UgbG9vayBhdCB0aGUgcGVyY2VudGFnZSBvZgp2YXJpYW5jZSBleHBsYWluZWQgYXMgYSBmdW5jdGlvbiBvZiB0aGUgbnVtYmVyIG9mIGNsdXN0ZXJzOiBPbmUgc2hvdWxkIGNob29zZSBhIG51bWJlciBvZiBjbHVzdGVycyBzbyB0aGF0CmFkZGluZyBhbm90aGVyIGNsdXN0ZXIgZG9lc27igJl0IGdpdmUgbXVjaCBiZXR0ZXIgbW9kZWxpbmcgb2YgdGhlIGRhdGEuIE1vcmUgcHJlY2lzZWx5LCBpZiBvbmUgcGxvdHMgdGhlCnBlcmNlbnRhZ2Ugb2YgdmFyaWFuY2UgZXhwbGFpbmVkIGJ5IHRoZSBjbHVzdGVycyBhZ2FpbnN0IHRoZSBudW1iZXIgb2YgY2x1c3RlcnMsIHRoZSBmaXJzdCBjbHVzdGVycyB3aWxsIGFkZAptdWNoIGluZm9ybWF0aW9uIChleHBsYWluIGEgbG90IG9mIHZhcmlhbmNlKSwgYnV0IGF0IHNvbWUgcG9pbnQgdGhlIG1hcmdpbmFsIGdhaW4gd2lsbCBkcm9wLCBnaXZpbmcgYW4gYW5nbGUgaW4gdGhlIGdyYXBoLiBUaGUgbnVtYmVyIG9mIGNsdXN0ZXJzIGlzIGNob3NlbiBhdCB0aGlzIHBvaW50LCBoZW5jZSB0aGUg4oCcZWxib3cgY3JpdGVyaW9u4oCdLgoKCmBgYHtyfQoKd3NzcGxvdCA8LSBmdW5jdGlvbihkYXRhLCBuYz0xNSwgc2VlZD0xNDgpewp3c3MgPC0gKG5yb3coZGF0YSktMSkqc3VtKGFwcGx5KGRhdGEsMix2YXIpKQpmb3IgKGkgaW4gMjpuYyl7CnNldC5zZWVkKHNlZWQpCndzc1tpXSA8LSBzdW0oa21lYW5zKGRhdGEsIGNlbnRlcnM9aSkkd2l0aGluc3MpfQpwbG90KDE6bmMsIHdzcywgdHlwZT0iYiIsIHhsYWI9Ik51bWJlciBvZiBDbHVzdGVycyIsCnlsYWI9IldpdGhpbiBncm91cHMgc3VtIG9mIHNxdWFyZXMiKX0KCgp3c3NwbG90KHRyYWluWywtMV0sIG5jPTgpCgoKYGBgCgoKCgpgYGB7cn0KbGlicmFyeShjbHVzdGVyKQpjbHVzcGxvdCh0cmFpblssLTFdLCBmaXRfa20kY2x1c3RlciwgbWFpbj0nMkQgcmVwcmVzZW50YXRpb24gb2YgdGhlIENsdXN0ZXIgc29sdXRpb24nLApjb2xvcj1UUlVFLCBzaGFkZT1UUlVFLApsYWJlbHM9MiwgbGluZXM9MCkKYGBgCgoKCmBgYHtyfQoKbz1vcmRlcihmaXRfa20kY2x1c3RlcikKCmRhdGEuZnJhbWUodHJhaW4kY2xhc3Nbb10sZml0X2ttJGNsdXN0ZXJbb10pJT4laGVhZCgpCgpsaWJyYXJ5KGNsdXN0ZXIpCmNsdXNwbG90KHRyYWluWywtMV0sIGZpdF9rbSRjbHVzdGVyLCBtYWluPScyRCByZXByZXNlbnRhdGlvbiBvZiB0aGUgQ2x1c3RlciBzb2x1dGlvbicsCiAgICAgICAgIApjb2xvcj1UUlVFLCBzaGFkZT1UUlVFLCBsYWJlbHM9MiwgbGluZXM9MCkKCiNmb29kYWdnPWFnbmVzKHRyYWluLGRpc3M9RkFMU0UsbWV0cmljPSJldWNsaWRpYW4iKQojcGxvdChmb29kYWdnLCBtYWluPSdEZW5kcm9ncmFtJykgIyMgZGVuZHJvZ3JhbQoKYGBgCgoKCiMjIyMgRGlzdGFuY2UgbWVhc3VyZXMKClRoZSBjbGFzc2lmaWNhdGlvbiBvZiBvYmplY3RzLCBpbnRvIGNsdXN0ZXJzLCByZXF1aXJlcyBzb21lIG1ldGhvZHMgZm9yIG1lYXN1cmluZyB0aGUgZGlzdGFuY2Ugb3IgdGhlIChkaXMpc2ltaWxhcml0eSBiZXR3ZWVuIHRoZSBvYmplY3RzLiBDaGFwdGVyIENsdXN0ZXJpbmcgRGlzdGFuY2UgTWVhc3VyZXMgRXNzZW50aWFscyBjb3ZlcnMgdGhlIGNvbW1vbiBkaXN0YW5jZSBtZWFzdXJlcyB1c2VkIGZvciBhc3Nlc3Npbmcgc2ltaWxhcml0eSBiZXR3ZWVuIG9ic2VydmF0aW9ucy4KCkl04oCZcyBzaW1wbGUgdG8gY29tcHV0ZSBhbmQgdmlzdWFsaXplIGRpc3RhbmNlIG1hdHJpeCB1c2luZyB0aGUgZnVuY3Rpb25zIGdldF9kaXN0KCkgYW5kIGZ2aXpfZGlzdCgpIFtmYWN0b2V4dHJhIFIgcGFja2FnZV06CgpnZXRfZGlzdCgpOiBmb3IgY29tcHV0aW5nIGEgZGlzdGFuY2UgbWF0cml4IGJldHdlZW4gdGhlIHJvd3Mgb2YgYSBkYXRhIG1hdHJpeC4gQ29tcGFyZWQgdG8gdGhlIHN0YW5kYXJkIGRpc3QoKSBmdW5jdGlvbiwgaXQgc3VwcG9ydHMgY29ycmVsYXRpb24tYmFzZWQgZGlzdGFuY2UgbWVhc3VyZXMgaW5jbHVkaW5nIOKAnHBlYXJzb27igJ0sIOKAnGtlbmRhbGzigJ0gYW5kIOKAnHNwZWFybWFu4oCdIG1ldGhvZHMuCmZ2aXpfZGlzdCgpOiBmb3IgdmlzdWFsaXppbmcgYSBkaXN0YW5jZSBtYXRyaXgKCgpgYGB7cn0KcmVzLmRpc3QgPC0gZ2V0X2Rpc3QoVVNBcnJlc3RzLCBzdGFuZCA9IFRSVUUsIG1ldGhvZCA9ICJwZWFyc29uIikKZnZpel9kaXN0KHJlcy5kaXN0LCAKICAgZ3JhZGllbnQgPSBsaXN0KGxvdyA9ICIjMDBBRkJCIiwgbWlkID0gIndoaXRlIiwgaGlnaCA9ICIjRkM0RTA3IikpCmBgYAoKCgojIyMjIE11bHRpcGxlIENvcnJlc3BvbmRlbmNlIEFuYWx5c2lzIChNQ0EpCgpgYGB7cn0KbGlicmFyeShGYWN0b01pbmVSKQoKCgoKCgojd29ya3Mgd2l0aCBxdWFsaXRhdGl2ZSB2YXJpYWJsZXMKI01DQSh0cmFpblssLTFdLCBuY3AgPSA1LCBncmFwaCA9IFRSVUUpCiNyZXMubWNhIDwtIE1DQSh0cmFpblssLTFdLHF1YW50aS5zdXA9MTkscXVhbGkuc3VwPTIwOjM2KQogI3N1bW1hcnkocmVzLm1jYSkKYGBgCgoKCiMjIyMgUHJlcGFyZSB0aGUgZGF0YSAKCmBgYHtyfQojIExvYWQgZGF0YQpkYXRhKCJVU0FycmVzdHMiKQpteV9kYXRhMSA8LSBVU0FycmVzdHMKIyBSZW1vdmUgYW55IG1pc3NpbmcgdmFsdWUgKGkuZSwgTkEgdmFsdWVzIGZvciBub3QgYXZhaWxhYmxlKQpteV9kYXRhMSA8LSBuYS5vbWl0KG15X2RhdGExKQojIFNjYWxlIHZhcmlhYmxlcwpteV9kYXRhMSA8LSBzY2FsZShteV9kYXRhMSkKIyBWaWV3IHRoZSBmaXJ0IDMgcm93cwpoZWFkKG15X2RhdGExLCBuID0gNSkKYGBgCgoKIyMjIyBEZXRlcm1pbmUgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzOiB1c2UgZmFjdG9leHRyYTo6ZnZpel9uYmNsdXN0KCkKClRocmVlIHBvcHVsYXIgbWV0aG9kcyBmb3IgZGV0ZXJtaW5pbmcgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzCuKXpiBFbGJvdyBtZXRob2QK4pe+IENvbmNlcHQK4pe+IEFsZ29yaXRobQril74gUiBjb2Rlcwril6YgQXZlcmFnZSBzaWxob3VldHRlIG1ldGhvZAril74gQ29uY2VwdAril74gQWxnb3JpdGhtCuKXviBSIGNvZGVzCuKXpiBDb25jbHVzaW9ucyBhYm91dCBlbGJvdyBhbmQgc2lsaG91ZXR0ZSBtZXRob2RzCuKXpiBHYXAgc3RhdGlzdGljIG1ldGhvZAril74gQ29uY2VwdAril74gQWxnb3JpdGhtCuKXviBSIGNvZGVzCgpgYGB7cn0KZnZpel9uYmNsdXN0KG15X2RhdGExLCBrbWVhbnMsIG1ldGhvZCA9ICJnYXBfc3RhdCIpCmBgYAoKCiMjIyMjIE5iQ2x1c3Q6IEEgUGFja2FnZSBwcm92aWRpbmcgMzAgaW5kaWNlcyBmb3IgZGV0ZXJtaW5pbmcgdGhlIGJlc3QgbnVtYmVyIG9mCmNsdXN0ZXJzCgpgYGB7cn0KI2luc3RhbGwucGFja2FnZXMoIk5iQ2x1c3QiKQoKbGlicmFyeSgiTmJDbHVzdCIpCgpyZXMubmJjbHVzdCA8LSBOYkNsdXN0KG15X2RhdGExLCBkaXN0YW5jZSA9ICJldWNsaWRlYW4iLAptaW4ubmMgPSAyLCBtYXgubmMgPSAxMCwKbWV0aG9kID0gImNvbXBsZXRlIiwgaW5kZXggPSJhbGwiKQpgYGAKCgpWaXN1YWxpemUgdXNpbmcgZmFjdG9leHRyYToKCgpgYGB7cn0KZmFjdG9leHRyYTo6ZnZpel9uYmNsdXN0KHJlcy5uYmNsdXN0KSArIHRoZW1lX21pbmltYWwoKQpgYGAKCgojIyMjIENsdXN0ZXJpbmcgdmFsaWRhdGlvbiBzdGF0aXN0aWNzCgpUaGUgdGVybSBjbHVzdGVyaW5nIHZhbGlkYXRpb24gaXMgdXNlZCB0byBkZXNpZ24gdGhlIHByb2NlZHVyZSBvZgpldmFsdWF0aW5nIHRoZSByZXN1bHRzIG9mIGEgY2x1c3RlcmluZyBhbGdvcml0aG0uIENsdXN0ZXJpbmcgdmFsaWRhdGlvbiBzdGF0aXN0aWNzOiBmcGM6OmNsdXN0ZXIuc3RhdHMoKQoKCmBgYHtyfQpteV9kYXRhIDwtIHNjYWxlKGlyaXNbLCAtNV0pCiMgRW5oYW5jZWQgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcsIGN1dCBpbiAzIGdyb3VwcwpsaWJyYXJ5KCJmYWN0b2V4dHJhIikKcmVzLmhjIDwtIGVjbHVzdChteV9kYXRhLCAiaGNsdXN0IiwgayA9IDMsIGdyYXBoID0gRkFMU0UpCiMgVmlzdWFsaXplCmZ2aXpfZGVuZChyZXMuaGMsIHJlY3QgPSBUUlVFLCBzaG93X2xhYmVscyA9IEZBTFNFKQoKCmBgYAoKCgojIyMjIEstbWVhbnMgY2x1c3RlcmluZwojIyMjIERldGVybWluZSB0aGUgb3B0aW1hbCBudW1iZXIgb2YgY2x1c3RlcnM6CgpgYGB7cn0KCmZ2aXpfbmJjbHVzdChteV9kYXRhMSwga21lYW5zLCBtZXRob2QgPSAiZ2FwX3N0YXQiKQoKI0NvbXB1dGUgYW5kIHZpc3VhbGl6ZSBrLW1lYW5zIGNsdXN0ZXJpbmcKa20ucmVzIDwtIGttZWFucyhteV9kYXRhMSwgNCwgbnN0YXJ0ID0gMjUpCiMgVmlzdWFsaXplCgpmdml6X2NsdXN0ZXIoa20ucmVzLCBkYXRhID0gbXlfZGF0YTEsIGZyYW1lLnR5cGUgPSAiY29udmV4IikrCnRoZW1lX21pbmltYWwoKQoKYGBgCgoKCgoKIyMjIyBLLW1lZG9pZHMgY2x1c3RlcmluZyBvciBQQU0gKFBhcnRpdGlvbmluZyBBcm91bmQgTWVkb2lkcykKCkFuIGFsdGVybmF0aXZlIHRvIGstbWVhbnMgY2x1c3RlcmluZyBpcyB0aGUgSy1tZWRvaWRzIGNsdXN0ZXJpbmcgb3IgUEFNIChQYXJ0aXRpb25pbmcgQXJvdW5kIE1lZG9pZHMsIEthdWZtYW4gJiBSb3Vzc2VldXcsIDE5OTApLCB3aGljaCBpcyBsZXNzIHNlbnNpdGl2ZSB0byBvdXRsaWVycyBjb21wYXJlZCB0byBrLW1lYW5zLgoKYGBge3J9CnBhbS5yZXMgPC0gcGFtKG15X2RhdGExLCA0KQojIFZpc3VhbGl6ZQpmdml6X2NsdXN0ZXIocGFtLnJlcykKYGBgCgoKCiMjIyMgSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcKCgoKIyMjIyBEZXRlcm1pbmUgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzOgoKRXN0aW1hdGUgdGhlIG51bWJlciBvZiBjbHVzdGVycyBpbiB0aGUgZGF0YSB1c2luZyBnYXAgc3RhdGlzdGljcyA6IGZhY3RvZXh0cmE6OmZ2aXpfbmJjbHVzdCgpCgoKYGBge3J9Cm15X2RhdGEgPC0gdHJhaW5bLC0xXQojIFJlbW92ZSBhbnkgbWlzc2luZyB2YWx1ZSAoaS5lLCBOQSB2YWx1ZXMgZm9yIG5vdCBhdmFpbGFibGUpCm15X2RhdGEgPC0gbmEub21pdChteV9kYXRhKQojIFNjYWxlIHZhcmlhYmxlcwpteV9kYXRhIDwtIHNjYWxlKG15X2RhdGEpCiMgVmlldyB0aGUgZmlydCAzIHJvd3MKaGVhZChteV9kYXRhLCBuID0gNSkKCmZ2aXpfbmJjbHVzdChteV9kYXRhLCBrbWVhbnMsIG1ldGhvZCA9ICJnYXBfc3RhdCIpCgpgYGAKCgoKYGBge3J9CmxpYnJhcnkoIk5iQ2x1c3QiKQpzZXQuc2VlZCgxMjMpCnJlcy5uYmNsdXN0IDwtIE5iQ2x1c3QobXlfZGF0YSwgZGlzdGFuY2UgPSAiZXVjbGlkZWFuIiwKbWluLm5jID0gMiwgbWF4Lm5jID0gMTAsCm1ldGhvZCA9ICJjb21wbGV0ZSIsIGluZGV4ID0iYWxsIikKCmBgYAoKClZpc3VhbGl6ZSB1c2luZyBmYWN0b2V4dHJhOgoKCmBgYHtyfQpmYWN0b2V4dHJhOjpmdml6X25iY2x1c3QocmVzLm5iY2x1c3QpICsgdGhlbWVfbWluaW1hbCgpCgpgYGAKCgoKIyMjIyBrLW1lYW5zIGNsdXN0ZXJpbmc6IFBhcnRpdGlvbmluZyBBcm91bmQgTWVkb2lkcy4gUm9idXN0IGFsdGVybmF0aXZlIHRvIGstbWVhbnMKY2x1c3RlcmluZywgbGVzcyBzZW5zaXRpdmUgdG8gb3V0bGllcnMuCgpgYGB7cn0KI0NvbXB1dGUgYW5kIHZpc3VhbGl6ZSBrLW1lYW5zIGNsdXN0ZXJpbmcKa20ucmVzIDwtIGttZWFucyhteV9kYXRhLCA2LCBuc3RhcnQgPSAyNSkKIyBWaXN1YWxpemUKCmZ2aXpfY2x1c3RlcihrbS5yZXMsIGRhdGEgPSBteV9kYXRhLCBmcmFtZS50eXBlID0gImNvbnZleCIpKwp0aGVtZV9taW5pbWFsKCkKCgpgYGAKCgoKCgpgYGB7cn0KIyBDb21wdXRlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIGFuZCBjdXQgaW50byA0IGNsdXN0ZXJzCnJlcyA8LSBoY3V0KG15X2RhdGEsIGsgPSA2LCBzdGFuZCA9IFRSVUUpCiMgVmlzdWFsaXplCmZ2aXpfZGVuZChyZXMsIHJlY3QgPSBUUlVFLCBjZXggPSAwLjUsCmtfY29sb3JzID0gYygiIzAwQUZCQiIsIiMyRTlGREYiLCAiI0U3QjgwMCIsICIjRkM0RQowNyIsIiM5OUQ1OTQiLCAiIzMyODhCRCIpKQpgYGAKCgoKCiMjIyMgUEFNIGNsdXN0ZXJpbmc6IFBhcnRpdGlvbmluZyBBcm91bmQgTWVkb2lkcy4gUm9idXN0IGFsdGVybmF0aXZlIHRvIGstbWVhbnMKY2x1c3RlcmluZywgbGVzcyBzZW5zaXRpdmUgdG8gb3V0bGllcnMuCgpgYGB7cn0KcGFtLnJlcyA8LSBwYW0obXlfZGF0YSwgNikKIyBWaXN1YWxpemUKZnZpel9jbHVzdGVyKHBhbS5yZXMpCmBgYAoKIyMjIyBIaWVyYXJjaGljYWwgY2x1c3RlcmluZwoKCmBgYHtyfQoKIyAyLiBDb21wdXRlIGRpc3NpbWlsYXJpdHkgbWF0cml4CmQgPC0gZGlzdChteV9kYXRhMSwgbWV0aG9kID0gImV1Y2xpZGVhbiIpCiMgSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgdXNpbmcgV2FyZCdzIG1ldGhvZApyZXMuaGMgPC0gaGNsdXN0KGQsIG1ldGhvZCA9ICJ3YXJkLkQyIiApCiMgQ3V0IHRyZWUgaW50byA0IGdyb3VwcwpycCA8LSBjdXRyZWUocmVzLmhjLCBrID0gNCkKIyBWaXN1YWxpemUKcGxvdChyZXMuaGMsIGNleCA9IDAuNikgIyBwbG90IHRyZWUKcmVjdC5oY2x1c3QocmVzLmhjLCBrID0gNCwgYm9yZGVyID0gMjo1KSAjIGFkZCByZWN0YW5nbGUKYGBgCgoKIyMjIyBDbHVzdGVyaW5nIHZhbGlkYXRpb24KQ2x1c3RlcmluZyB2YWxpZGF0aW9uIGluY2x1ZGVzIHRocmVlIG1haW4gdGFza3M6CjEuIGNsdXN0ZXJpbmcgdGVuZGVuY3kgYXNzZXNzZXMgd2hldGhlciBhcHBseWluZyBjbHVzdGVyaW5nIGlzIHN1aXRhYmxlIHRvIHlvdXIKZGF0YS4KMi4gY2x1c3RlcmluZyBldmFsdWF0aW9uIGFzc2Vzc2VzIHRoZSBnb29kbmVzcyBvciBxdWFsaXR5IG9mIHRoZSBjbHVzdGVyaW5nLgozLiBjbHVzdGVyaW5nIHN0YWJpbGl0eSBzZWVrcyB0byB1bmRlcnN0YW5kIHRoZSBzZW5zaXRpdml0eSBvZiB0aGUgY2x1c3RlcmluZyByZXN1bHQKdG8gdmFyaW91cyBhbGdvcml0aG1pYyBwYXJhbWV0ZXJzLCBmb3IgZXhhbXBsZSwgdGhlIG51bWJlciBvZiBjbHVzdGVycy4KCgo0LiBNZXRob2RzIGZvciBhc3Nlc3NpbmcgY2x1c3RlcmluZyB0ZW5kZW5jeQril6YgSG9wa2lucyBzdGF0aXN0aWMK4pe+IEFsZ29yaXRobQril74gUiBmdW5jdGlvbiBmb3IgY29tcHV0aW5nIEhvcGtpbnMgc3RhdGlzdGljOiBjbHVzdGVydGVuZDo6aG9wa2lucygpCuKXpiBWQVQ6IFZpc3VhbCBBc3Nlc3NtZW50IG9mIGNsdXN0ZXIgVGVuZGVuY3k6IHNlcmlhdGlvbjo6ZGlzc3Bsb3QoKQril74gVkFUIEFsZ29yaXRobQril74gUiBmdW5jdGlvbnMgZm9yIFZBVAo1LiBBIHNpbmdsZSBmdW5jdGlvbiBmb3IgSG9wa2lucyBzdGF0aXN0aWMgYW5kIFZBVDogZmFjdG9leHRyYTo6Z2V0X2NsdXN0X3RlbmRlbmN5KCkKCgrigKIgSG9wa2lucyBzdGF0aXN0aWM6IElmIHRoZSB2YWx1ZSBvZiBIb3BraW5zIHN0YXRpc3RpYyBpcyBjbG9zZSB0byB6ZXJvIChmYXIgYmVsb3cKMC41KSwgdGhlbiB3ZSBjYW4gY29uY2x1ZGUgdGhhdCB0aGUgZGF0YXNldCBpcyBzaWduaWZpY2FudGx5IGNsdXN0ZXJhYmxlLgrigKIgVkFUIChWaXN1YWwgQXNzZXNzbWVudCBvZiBjbHVzdGVyIFRlbmRlbmN5KTogVGhlIFZBVCBkZXRlY3RzIHRoZSBjbHVzdGVyaW5nCnRlbmRlbmN5IGluIGEgdmlzdWFsIGZvcm0gYnkgY291bnRpbmcgdGhlIG51bWJlciBvZiBzcXVhcmUgc2hhcGVkCmRhcmsgKG9yIGNvbG9yZWQpIGJsb2NrcyBhbG9uZyB0aGUgZGlhZ29uYWwgaW4gYSBWQVQgaW1hZ2UuCgoKYGBge3J9Cm15X2RhdGEyIDwtIHNjYWxlKGlyaXNbLCAtNV0pCmdldF9jbHVzdF90ZW5kZW5jeShteV9kYXRhMiwgbiA9IDUwLApncmFkaWVudCA9IGxpc3QobG93ID0gInN0ZWVsYmx1ZSIsIGhpZ2gKPSAid2hpdGUiKSkKYGBgCgoKCmBgYHtyfQojIDEuIExvYWRpbmcgYW5kIHByZXBhcmluZyBkYXRhCmRhdGEoIlVTQXJyZXN0cyIpCm15X2RhdGEgPC0gc2NhbGUoVVNBcnJlc3RzKQojIDIuIENvbXB1dGUgZGlzc2ltaWxhcml0eSBtYXRyaXgKZCA8LSBkaXN0KG15X2RhdGEsIG1ldGhvZCA9ICJldWNsaWRlYW4iKQojIEhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHVzaW5nIFdhcmQncyBtZXRob2QKcmVzLmhjIDwtIGhjbHVzdChkLCBtZXRob2QgPSAid2FyZC5EMiIgKQpncnAgPC0gY3V0cmVlKHJlcy5oYywgayA9IDQpCiMgVmlzdWFsaXplCnBsb3QocmVzLmhjLCBjZXggPSAwLjYpICMgcGxvdCB0cmVlCnJlY3QuaGNsdXN0KHJlcy5oYywgayA9IDQsIGJvcmRlciA9IDI6NSkgIyBhZGQgcmVjdGFuZ2xlCmBgYAoKCgpgYGB7cn0KIyBDb21wdXRlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIGFuZCBjdXQgaW50byA0IGNsdXN0ZXJzCnJlcyA8LSBoY3V0KG15X2RhdGExLCBrID0gNCwgc3RhbmQgPSBUUlVFKQojIFZpc3VhbGl6ZQpmdml6X2RlbmQocmVzLCByZWN0ID0gVFJVRSwgY2V4ID0gMC41LAprX2NvbG9ycyA9IGMoIiNENTNFNEYiLCIjRkM4RDU5IiwgIiNFNkY1OTgiLCAiIzk5RDU5NCIgLCIjMzI4OEJEIikpCmBgYAoKCgoKCmBgYHtyfQpteV9kYXRhMyA8LSBzY2FsZShpcmlzWywgLTVdKQojIEVuaGFuY2VkIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nLCBjdXQgaW4gMyBncm91cHMKbGlicmFyeSgiZmFjdG9leHRyYSIpCnJlcy5oYyA8LSBlY2x1c3QobXlfZGF0YTMsICJoY2x1c3QiLCBrID0gMywgZ3JhcGggPSBGQUxTRSkKIyBWaXN1YWxpemUKZnZpel9kZW5kKHJlcy5oYywgcmVjdCA9IFRSVUUsIHNob3dfbGFiZWxzID0gRkFMU0UpCgoKCiNDb21wdXRlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIGFuZCBjdXQgaW50byA0IGNsdXN0ZXJzCnJlcyA8LSBoY3V0KG15X2RhdGEzLCBrID0gMywgc3RhbmQgPSBUUlVFKQojIFZpc3VhbGl6ZQpmdml6X2RlbmQocmVzLCByZWN0ID0gVFJVRSwgY2V4ID0gMC41LAprX2NvbG9ycyA9IGMoIiNENTNFNEYiLCAiI0U2RjU5OCIsICIjOTlENTk0IiAsIiMzMjg4QkQiKSkKYGBgCgojIyMjIFZhbGlkYXRlIGNsdXN0ZXJpbmcgcmVzdWx0cyBieSBpbnNwZWN0aW9uIHRoZSBjbHVzdGVyIHNpbGhvdWV0dGUgcGxvdAoKUmVjYWxsIHRoYXQgdGhlIHNpbGhvdWV0dGUgJFNfaSQgbWVhc3VyZXMgaG93IHNpbWlsYXIgYW4gb2JqZWN0ICRpJCBpcyB0byB0aGUgdGhlCm90aGVyIG9iamVjdHMgaW4gaXRzIG93biBjbHVzdGVyIHZlcnN1cyB0aG9zZSBpbiB0aGUgbmVpZ2hib3IgY2x1c3Rlci4gJFNfaSQgdmFsdWVzCnJhbmdlIGZyb20gMSB0byAtIDE6CuKAoiBBIHZhbHVlIG9mICRTX2kkIGNsb3NlIHRvIDEgaW5kaWNhdGVzIHRoYXQgdGhlIG9iamVjdCBpcyB3ZWxsIGNsdXN0ZXJlZC4gSW4gdGhlCm90aGVyIHdvcmRzLCB0aGUgb2JqZWN0ICRpJCBpcyBzaW1pbGFyIHRvIHRoZSBvdGhlciBvYmplY3RzIGluIGl0cyBncm91cC4K4oCiIEEgdmFsdWUgb2YgJFNfaSQgY2xvc2UgdG8gLTEgaW5kaWNhdGVzIHRoYXQgdGhlIG9iamVjdCBpcyBwb29ybHkgY2x1c3RlcmVkLCBhbmQKdGhhdCBhc3NpZ25tZW50IHRvIHNvbWUgb3RoZXIgY2x1c3RlciB3b3VsZCBwcm9iYWJseSBpbXByb3ZlIHRoZSBvdmVyYWxsIHJlc3VsdHMuCgpgYGB7cn0KIyBWaXN1YWxpemUgdGhlIHNpbGhvdWV0dGUgcGxvdApmdml6X3NpbGhvdWV0dGUocmVzLmhjKQpgYGAKCgoKV2hpY2ggc2FtcGxlcyBoYXZlIG5lZ2F0aXZlIHNpbGhvdWV0dGU/IFRvIHdoYXQgY2x1c3RlciDvhKggYXJlIHRoZXkgY2xvc2VyPwoKYGBge3J9CiMgU2lsaG91ZXR0ZSB3aWR0aCBvZiBvYnNlcnZhdGlvbnMKc2lsIDwtIHJlcy5oYyRzaWxpbmZvJHdpZHRoc1ssIDE6M10KCgojIE9iamVjdHMgd2l0aCBuZWdhdGl2ZSBzaWxob3VldHRlCm5lZ19zaWxfaW5kZXggPC0gd2hpY2goc2lsWywgJ3NpbF93aWR0aCddIDwgMCkKc2lsW25lZ19zaWxfaW5kZXgsICwgZHJvcCA9IEZBTFNFXQoKYGBgCgoKYGBge3J9CnJlcy5oYyRkaXN0Lm1ldGhvZApgYGAKCgojIyMjIEhvdyB0byBjaG9vc2UgdGhlIGFwcHJvcHJpYXRlIGNsdXN0ZXJpbmcgYWxnb3JpdGhtcwpmb3IgeW91ciBkYXRhPwoKCjEuIENsdXN0ZXJpbmcgdmFsaWRhdGlvbiBtZWFzdXJlcyBpbiBjbFZhbGlkIHBhY2thZ2UK4pemIEludGVybmFsIHZhbGlkYXRpb24gbWVhc3VyZXMK4pemIFN0YWJpbGl0eSB2YWxpZGF0aW9uIG1lYXN1cmVzCuKXpiBCaW9sb2dpY2FsIHZhbGlkYXRpb24gbWVhc3VyZXMKMi4gUiBmdW5jdGlvbiBjbFZhbGlkKCkK4pemIEZvcm1hdAril6YgRXhhbXBsZXMgb2YgdXNhZ2UK4pe+IERhdGEK4pe+IENvbXB1dGUgY2xWYWxpZCgpCgoKCgpgYGB7cn0KCiNpbnN0YWxsLnBhY2thZ2VzKCJjbFZhbGlkIikKIyBDb21wdXRlIGNsVmFsaWQKbGlicmFyeSgiY2xWYWxpZCIpCmludGVybiA8LSBjbFZhbGlkKG15X2RhdGExLCBuQ2x1c3QgPSAyOjYsCmNsTWV0aG9kcyA9IGMoImhpZXJhcmNoaWNhbCIsImttZWFucyIsInBhbSIpLAp2YWxpZGF0aW9uID0gImludGVybmFsIikKIyBTdW1tYXJ5CnN1bW1hcnkoaW50ZXJuKQpgYGAKCiMjIyMgSG93IHRvIGNvbXB1dGUgcC12YWx1ZSBmb3IgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgaW4KUj8KClRoZSBSIHBhY2thZ2UgcHZjbHVzdCAoU3V6dWtpIGV0IGFsLiwgMjAwNCkgd2hpY2ggdXNlcwpib290c3RyYXAgcmVzYW1wbGluZyB0ZWNobmlxdWVzIHRvIGNvbXB1dGUgcC12YWx1ZSBmb3IgZWFjaCBjbHVzdGVycy4KCmBgYHtyfQoKI2luc3RhbGwucGFja2FnZXMoInB2Y2x1c3QiKQpsaWJyYXJ5KHB2Y2x1c3QpCiMgRGF0YSBwcmVwYXJhdGlvbgpzZXQuc2VlZCgxMjMpCmRhdGEoImx1bmciKQpzcyA8LSBzYW1wbGUoMTo3MywgMzApICMgZXh0cmFjdCAyMCBzYW1wbGVzIG91dCBvZgpteV9kYXRhNCA8LSBsdW5nWywgc3NdCgpteV9kYXRhNCU+JWhlYWQoKQoKYGBgCgoKCmBgYHtyfQojIENvbXB1dGUgcHZjbHVzdApyZXMucHYgPC0gcHZjbHVzdChteV9kYXRhNCwgbWV0aG9kLmRpc3Q9ImNvciIsCm1ldGhvZC5oY2x1c3Q9ImF2ZXJhZ2UiLCBuYm9vdCA9IDEwKQpgYGAKCgpgYGB7cn0KIyBEZWZhdWx0IHBsb3QKcGxvdChyZXMucHYsIGhhbmcgPSAtMSwgY2V4ID0gMC41KQpwdnJlY3QocmVzLnB2KQpgYGAKCgoKCiMjIyMgMTAgQWR2YW5jZWQgY2x1c3RlcmluZyBtZXRob2RzCiMjIyMgMTAuMSBGdXp6eSBjbHVzdGVyaW5nIGFuYWx5c2lzCkZ1enp5IGNsdXN0ZXJpbmcgaXMgYWxzbyBrbm93biBhcyBzb2Z0IG1ldGhvZC4gU3RhbmRhcmQgY2x1c3RlcmluZyBhcHByb2FjaGVzIHByb2R1Y2UKcGFydGl0aW9ucyAoSy1tZWFucywgUEFNKSwgaW4gd2hpY2ggZWFjaCBvYnNlcnZhdGlvbiBiZWxvbmdzIHRvIG9ubHkgb25lIGNsdXN0ZXIuClRoaXMgaXMga25vd24gYXMgaGFyZCBjbHVzdGVyaW5nLgpJbiBGdXp6eSBjbHVzdGVyaW5nLCBpdGVtcyBjYW4gYmUgYSBtZW1iZXIgb2YgbW9yZSB0aGFuIG9uZSBjbHVzdGVyLiBFYWNoIGl0ZW0KaGFzIGEgc2V0IG9mIG1lbWJlcnNoaXAgY29lZmZpY2llbnRzIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGRlZ3JlZSBvZiBiZWluZyBpbiBhCmdpdmVuIGNsdXN0ZXIuIFRoZSBGdXp6eSBjLW1lYW5zIG1ldGhvZCBpcyB0aGUgbW9zdCBwb3B1bGFyIGZ1enp5IGNsdXN0ZXJpbmcKYWxnb3JpdGhtLiBSZWFkIG1vcmU6IEZ1enp5IGNsdXN0ZXJpbmcgYW5hbHlzaXMuCjEwLjIgTW9kZWwtYmFzZWQgY2x1c3RlcmluZwpJbiBtb2RlbC1iYXNlZCBjbHVzdGVyaW5nLCB0aGUgZGF0YSBhcmUgdmlld2VkIGFzIGNvbWluZyBmcm9tIGEgZGlzdHJpYnV0aW9uCnRoYXQgaXMgbWl4dHVyZSBvZiB0d28gb3JlIG1vcmUgY2x1c3RlcnMuIEl0IGZpbmRzIGJlc3QgZml0IG9mIG1vZGVscyB0byBkYXRhIGFuZAplc3RpbWF0ZXMgdGhlIG51bWJlciBvZiBjbHVzdGVycy4gUmVhZCBtb3JlOiBNb2RlbC1iYXNlZCBjbHVzdGVyaW5nLgoKCiMjIyMgNyBDbHVzdGVyaW5nIHZhbGlkYXRpb24KQ2x1c3RlcmluZyB2YWxpZGF0aW9uIGluY2x1ZGVzIHRocmVlIG1haW4gdGFza3M6CjEuIGNsdXN0ZXJpbmcgdGVuZGVuY3kgYXNzZXNzZXMgd2hldGhlciBhcHBseWluZyBjbHVzdGVyaW5nIGlzIHN1aXRhYmxlIHRvIHlvdXIKZGF0YS4KMi4gY2x1c3RlcmluZyBldmFsdWF0aW9uIGFzc2Vzc2VzIHRoZSBnb29kbmVzcyBvciBxdWFsaXR5IG9mIHRoZSBjbHVzdGVyaW5nLgozLiBjbHVzdGVyaW5nIHN0YWJpbGl0eSBzZWVrcyB0byB1bmRlcnN0YW5kIHRoZSBzZW5zaXRpdml0eSBvZiB0aGUgY2x1c3RlcmluZyByZXN1bHQKdG8gdmFyaW91cyBhbGdvcml0aG1pYyBwYXJhbWV0ZXJzLCBmb3IgZXhhbXBsZSwgdGhlIG51bWJlciBvZiBjbHVzdGVycy4KCgo0LiBNZXRob2RzIGZvciBhc3Nlc3NpbmcgY2x1c3RlcmluZyB0ZW5kZW5jeQril6YgSG9wa2lucyBzdGF0aXN0aWMK4pe+IGxnb3JpdGhtCuKXviBSIGZ1bmN0aW9uIGZvciBjb21wdXRpbmcgSG9wa2lucyBzdGF0aXN0aWM6IGNsdXN0ZXJ0ZW5kOjpob3BraW5zKCkK4pemIFZBVDogVmlzdWFsIEFzc2Vzc21lbnQgb2YgY2x1c3RlciBUZW5kZW5jeTogc2VyaWF0aW9uOjpkaXNzcGxvdCgpCuKXviBWQVQgQWxnb3JpdGhtCuKXviBSIGZ1bmN0aW9ucyBmb3IgVkFUCjUuIEEgc2luZ2xlIGZ1bmN0aW9uIGZvciBIb3BraW5zIHN0YXRpc3RpYyBhbmQgVkFUOiBmYWN0b2V4dHJhOjpnZXRfY2x1c3RfdGVuZGVuY3koKQoKCgrigKIgSG9wa2lucyBzdGF0aXN0aWM6IElmIHRoZSB2YWx1ZSBvZiBIb3BraW5zIHN0YXRpc3RpYyBpcyBjbG9zZSB0byB6ZXJvIChmYXIgYmVsb3cKMC41KSwgdGhlbiB3ZSBjYW4gY29uY2x1ZGUgdGhhdCB0aGUgZGF0YXNldCBpcyBzaWduaWZpY2FudGx5IGNsdXN0ZXJhYmxlLgrigKIgVkFUIChWaXN1YWwgQXNzZXNzbWVudCBvZiBjbHVzdGVyIFRlbmRlbmN5KTogVGhlIFZBVCBkZXRlY3RzIHRoZSBjbHVzdGVyaW5nCnRlbmRlbmN5IGluIGEgdmlzdWFsIGZvcm0gYnkgY291bnRpbmcgdGhlIG51bWJlciBvZiBzcXVhcmUgc2hhcGVkCmRhcmsgKG9yIGNvbG9yZWQpIGJsb2NrcyBhbG9uZyB0aGUgZGlhZ29uYWwgaW4gYSBWQVQgaW1hZ2UuCgoKCiMjIyMgSGllcmFyY2hpY2FsIEstTWVhbnMgQ2x1c3RlcmluZwoKSy1tZWFucyAoQ2hhcHRlciBAcmVmKGttZWFucy1jbHVzdGVyaW5nKSkgcmVwcmVzZW50cyBvbmUgb2YgdGhlIG1vc3QgcG9wdWxhciBjbHVzdGVyaW5nIGFsZ29yaXRobS4gSG93ZXZlciwgaXQgaGFzIHNvbWUgbGltaXRhdGlvbnM6IGl0IHJlcXVpcmVzIHRoZSB1c2VyIHRvIHNwZWNpZnkgdGhlIG51bWJlciBvZiBjbHVzdGVycyBpbiBhZHZhbmNlIGFuZCBzZWxlY3RzIGluaXRpYWwgY2VudHJvaWRzIHJhbmRvbWx5LiBUaGUgZmluYWwgay1tZWFucyBjbHVzdGVyaW5nIHNvbHV0aW9uIGlzIHZlcnkgc2Vuc2l0aXZlIHRvIHRoaXMgaW5pdGlhbCByYW5kb20gc2VsZWN0aW9uIG9mIGNsdXN0ZXIgY2VudGVycy4gVGhlIHJlc3VsdCBtaWdodCBiZSAoc2xpZ2h0bHkpIGRpZmZlcmVudCBlYWNoIHRpbWUgeW91IGNvbXB1dGUgay1tZWFucy4KCmBgYHtyfQojIENvbXB1dGUgaGllcmFyY2hpY2FsIGstbWVhbnMgY2x1c3RlcmluZwpsaWJyYXJ5KGZhY3RvZXh0cmEpCnJlcy5oayA8LWhrbWVhbnMobXlfZGF0YTEsIDQpCiMgRWxlbWVudHMgcmV0dXJuZWQgYnkgaGttZWFucygpCm5hbWVzKHJlcy5oaykKYGBgCgoKCmBgYHtyfQojIFByaW50IHRoZSByZXN1bHRzCnJlcy5oawpgYGAKCgoKYGBge3J9CiMgVmlzdWFsaXplIHRoZSB0cmVlCmZ2aXpfZGVuZChyZXMuaGssIGNleCA9IDAuNiwgcGFsZXR0ZSA9ICJqY28iLCAKICAgICAgICAgIHJlY3QgPSBUUlVFLCByZWN0X2JvcmRlciA9ICJqY28iLCByZWN0X2ZpbGwgPSBUUlVFKQpgYGAKCgoKYGBge3J9CiMgVmlzdWFsaXplIHRoZSBoa21lYW5zIGZpbmFsIGNsdXN0ZXJzCmZ2aXpfY2x1c3RlcihyZXMuaGssIHBhbGV0dGUgPSAiamNvIiwgcmVwZWwgPSBUUlVFLAogICAgICAgICAgICAgZ2d0aGVtZSA9IHRoZW1lX2NsYXNzaWMoKSkKYGBgCgoKCiMjIyMgVGhlIGZ1enp5IGNsdXN0ZXJpbmcgaXMgY29uc2lkZXJlZCBhcyBzb2Z0IGNsdXN0ZXJpbmcsIGluIHdoaWNoIGVhY2ggZWxlbWVudCBoYXMgYSBwcm9iYWJpbGl0eSBvZiBiZWxvbmdpbmcgdG8gZWFjaCBjbHVzdGVyLiBJbiBvdGhlciB3b3JkcywgZWFjaCBlbGVtZW50IGhhcyBhIHNldCBvZiBtZW1iZXJzaGlwIGNvZWZmaWNpZW50cyBjb3JyZXNwb25kaW5nIHRvIHRoZSBkZWdyZWUgb2YgYmVpbmcgaW4gYSBnaXZlbiBjbHVzdGVyLgoKVGhpcyBpcyBkaWZmZXJlbnQgZnJvbSBrLW1lYW5zIGFuZCBrLW1lZG9pZCBjbHVzdGVyaW5nLCB3aGVyZSBlYWNoIG9iamVjdCBpcyBhZmZlY3RlZCBleGFjdGx5IHRvIG9uZSBjbHVzdGVyLiBLLW1lYW5zIGFuZCBrLW1lZG9pZHMgY2x1c3RlcmluZyBhcmUga25vd24gYXMgaGFyZCBvciBub24tZnV6enkgY2x1c3RlcmluZy4KCkluIGZ1enp5IGNsdXN0ZXJpbmcsIHBvaW50cyBjbG9zZSB0byB0aGUgY2VudGVyIG9mIGEgY2x1c3RlciwgbWF5IGJlIGluIHRoZSBjbHVzdGVyIHRvIGEgaGlnaGVyIGRlZ3JlZSB0aGFuIHBvaW50cyBpbiB0aGUgZWRnZSBvZiBhIGNsdXN0ZXIuIFRoZSBkZWdyZWUsIHRvIHdoaWNoIGFuIGVsZW1lbnQgYmVsb25ncyB0byBhIGdpdmVuIGNsdXN0ZXIsIGlzIGEgbnVtZXJpY2FsIHZhbHVlIHZhcnlpbmcgZnJvbSAwIHRvIDEuCgpUaGUgZnV6enkgYy1tZWFucyAoRkNNKSBhbGdvcml0aG0gaXMgb25lIG9mIHRoZSBtb3N0IHdpZGVseSB1c2VkIGZ1enp5IGNsdXN0ZXJpbmcgYWxnb3JpdGhtcy4gVGhlIGNlbnRyb2lkIG9mIGEgY2x1c3RlciBpcyBjYWxjdWxhdGVkIGFzIHRoZSBtZWFuIG9mIGFsbCBwb2ludHMsIHdlaWdodGVkIGJ5IHRoZWlyIGRlZ3JlZSBvZiBiZWxvbmdpbmcgdG8gdGhlIGNsdXN0ZXI6CgoKIyMjIyBDb21wdXRpbmcgZnV6enkgY2x1c3RlcmluZwoKVGhlIGZ1bmN0aW9uIGZhbm55KCkgW2NsdXN0ZXIgUiBwYWNrYWdlXSBjYW4gYmUgdXNlZCB0byBjb21wdXRlIGZ1enp5IGNsdXN0ZXJpbmcuIEZBTk5ZIHN0YW5kcyBmb3IgZnV6enkgYW5hbHlzaXMgY2x1c3RlcmluZy4gQSBzaW1wbGlmaWVkIGZvcm1hdCBpczoKCgoKeDogQSBkYXRhIG1hdHJpeCBvciBkYXRhIGZyYW1lIG9yIGRpc3NpbWlsYXJpdHkgbWF0cml4Cms6IFRoZSBkZXNpcmVkIG51bWJlciBvZiBjbHVzdGVycyB0byBiZSBnZW5lcmF0ZWQKbWV0cmljOiBNZXRyaWMgZm9yIGNhbGN1bGF0aW5nIGRpc3NpbWlsYXJpdGllcyBiZXR3ZWVuIG9ic2VydmF0aW9ucwpzdGFuZDogSWYgVFJVRSwgdmFyaWFibGVzIGFyZSBzdGFuZGFyZGl6ZWQgYmVmb3JlIGNhbGN1bGF0aW5nIHRoZSBkaXNzaW1pbGFyaXRpZXMKVGhlIGZ1bmN0aW9uIGZhbm55KCkgcmV0dXJucyBhbiBvYmplY3QgaW5jbHVkaW5nIHRoZSBmb2xsb3dpbmcgY29tcG9uZW50czoKCm1lbWJlcnNoaXA6IG1hdHJpeCBjb250YWluaW5nIHRoZSBkZWdyZWUgdG8gd2hpY2ggZWFjaCBvYnNlcnZhdGlvbiBiZWxvbmdzIHRvIGEgZ2l2ZW4gY2x1c3Rlci4gQ29sdW1uIG5hbWVzIGFyZSB0aGUgY2x1c3RlcnMgYW5kIHJvd3MgYXJlIG9ic2VydmF0aW9ucwpjb2VmZjogRHVubuKAmXMgcGFydGl0aW9uIGNvZWZmaWNpZW50IEYoaykgb2YgdGhlIGNsdXN0ZXJpbmcsIHdoZXJlIGsgaXMgdGhlIG51bWJlciBvZiBjbHVzdGVycy4gRihrKSBpcyB0aGUgc3VtIG9mIGFsbCBzcXVhcmVkIG1lbWJlcnNoaXAgY29lZmZpY2llbnRzLCBkaXZpZGVkIGJ5IHRoZSBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zLiBJdHMgdmFsdWUgaXMgYmV0d2VlbiAxL2sgYW5kIDEuIFRoZSBub3JtYWxpemVkIGZvcm0gb2YgdGhlIGNvZWZmaWNpZW50IGlzIGFsc28gZ2l2ZW4uIEl0IGlzIGRlZmluZWQgYXMgKEYoayniiJIxL2spLygx4oiSMS9rKQosIGFuZCByYW5nZXMgYmV0d2VlbiAwIGFuZCAxLiBBIGxvdyB2YWx1ZSBvZiBEdW5u4oCZcyBjb2VmZmljaWVudCBpbmRpY2F0ZXMgYSB2ZXJ5IGZ1enp5IGNsdXN0ZXJpbmcsIHdoZXJlYXMgYSB2YWx1ZSBjbG9zZSB0byAxIGluZGljYXRlcyBhIG5lYXItY3Jpc3AgY2x1c3RlcmluZy4KY2x1c3RlcmluZzogdGhlIGNsdXN0ZXJpbmcgdmVjdG9yIGNvbnRhaW5pbmcgdGhlIG5lYXJlc3QgY3Jpc3AgZ3JvdXBpbmcgb2Ygb2JzZXJ2YXRpb25zCgoKYGBge3J9CmxpYnJhcnkoY2x1c3RlcikKZGYgPC0gc2NhbGUoVVNBcnJlc3RzKSAgICAgIyBTdGFuZGFyZGl6ZSB0aGUgZGF0YQpyZXMuZmFubnkgPC0gZmFubnkoZGYsIDIpICAjIENvbXB1dGUgZnV6enkgY2x1c3RlcmluZyB3aXRoIGsgPSAyCmBgYAoKCmBgYHtyfQpoZWFkKHJlcy5mYW5ueSRtZW1iZXJzaGlwLCAzKSAjIE1lbWJlcnNoaXAgY29lZmZpY2llbnRzCmBgYAoKCgoKYGBge3J9CnJlcy5mYW5ueSRjb2VmZiAjIER1bm4ncyBwYXJ0aXRpb24gY29lZmZpY2llbnQKYGBgCgoKCmBgYHtyfQpoZWFkKHJlcy5mYW5ueSRjbHVzdGVyaW5nKSAjIE9ic2VydmF0aW9uIGdyb3VwcwpgYGAKCgpUbyB2aXN1YWxpemUgb2JzZXJ2YXRpb24gZ3JvdXBzLCB1c2UgdGhlIGZ1bmN0aW9uIGZ2aXpfY2x1c3RlcigpIFtmYWN0b2V4dHJhIHBhY2thZ2VdOgoKCmBgYHtyfQpmdml6X2NsdXN0ZXIocmVzLmZhbm55LCBlbGxpcHNlLnR5cGUgPSAibm9ybSIsIHJlcGVsID0gVFJVRSwKICAgICAgICAgICAgIHBhbGV0dGUgPSAiamNvIiwgZ2d0aGVtZSA9IHRoZW1lX21pbmltYWwoKSwKICAgICAgICAgICAgIGxlZ2VuZCA9ICJyaWdodCIpCmBgYAoKVG8gZXZhbHVhdGUgdGhlIGdvb2RuZXNzcyBvZiB0aGUgY2x1c3RlcmluZyByZXN1bHRzLCBwbG90IHRoZSBzaWxob3VldHRlIGNvZWZmaWNpZW50IGFzIGZvbGxvdzoKCmBgYHtyfQpmdml6X3NpbGhvdWV0dGUocmVzLmZhbm55LCBwYWxldHRlID0gImpjbyIsCiAgICAgICAgICAgICAgICBnZ3RoZW1lID0gdGhlbWVfbWluaW1hbCgpKQpgYGAKCgoKIyMjIyBNb2RlbCBCYXNlZCBDbHVzdGVyaW5nIEVzc2VudGlhbHMKCgpUaGUgdHJhZGl0aW9uYWwgY2x1c3RlcmluZyBtZXRob2RzLCBzdWNoIGFzIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIChDaGFwdGVyIEByZWYoYWdnbG9tZXJhdGl2ZS1jbHVzdGVyaW5nKSkgYW5kIGstbWVhbnMgY2x1c3RlcmluZyAoQ2hhcHRlciBAcmVmKGttZWFucy1jbHVzdGVyaW5nKSksIGFyZSBoZXVyaXN0aWMgYW5kIGFyZSBub3QgYmFzZWQgb24gZm9ybWFsIG1vZGVscy4gRnVydGhlcm1vcmUsIGstbWVhbnMgYWxnb3JpdGhtIGlzIGNvbW1vbmx5IHJhbmRvbW5seSBpbml0aWFsaXplZCwgc28gZGlmZmVyZW50IHJ1bnMgb2Ygay1tZWFucyB3aWxsIG9mdGVuIHlpZWxkIGRpZmZlcmVudCByZXN1bHRzLiBBZGRpdGlvbmFsbHksIGstbWVhbnMgcmVxdWlyZXMgdGhlIHVzZXIgdG8gc3BlY2lmeSB0aGUgdGhlIG9wdGltYWwgbnVtYmVyIG9mIGNsdXN0ZXJzLgoKQW4gYWx0ZXJuYXRpdmUgaXMgbW9kZWwtYmFzZWQgY2x1c3RlcmluZywgd2hpY2ggY29uc2lkZXIgdGhlIGRhdGEgYXMgY29taW5nIGZyb20gYSBkaXN0cmlidXRpb24gdGhhdCBpcyBtaXh0dXJlIG9mIHR3byBvciBtb3JlIGNsdXN0ZXJzIChGcmFsZXkgYW5kIFJhZnRlcnkgMjAwMiwgRnJhbGV5IGV0IGFsLiAoMjAxMikpLiBVbmxpa2Ugay1tZWFucywgdGhlIG1vZGVsLWJhc2VkIGNsdXN0ZXJpbmcgdXNlcyBhIHNvZnQgYXNzaWdubWVudCwgd2hlcmUgZWFjaCBkYXRhIHBvaW50IGhhcyBhIHByb2JhYmlsaXR5IG9mIGJlbG9uZ2luZyB0byBlYWNoIGNsdXN0ZXIuCgoKQ29uY2VwdCBvZiBtb2RlbC1iYXNlZCBjbHVzdGVyaW5nCgpJbiBtb2RlbC1iYXNlZCBjbHVzdGVyaW5nLCB0aGUgZGF0YSBpcyBjb25zaWRlcmVkIGFzIGNvbWluZyBmcm9tIGEgbWl4dHVyZSBvZiBkZW5zaXR5LgoKRWFjaCBjb21wb25lbnQgKGkuZS4gY2x1c3RlcikgayBpcyBtb2RlbGVkIGJ5IHRoZSBub3JtYWwgb3IgR2F1c3NpYW4gZGlzdHJpYnV0aW9uIHdoaWNoIGlzIGNoYXJhY3Rlcml6ZWQgYnkgdGhlIHBhcmFtZXRlcnM6CgrOvGs6IG1lYW4gdmVjdG9yLAriiJFrOiBjb3ZhcmlhbmNlIG1hdHJpeCwKQW4gYXNzb2NpYXRlZCBwcm9iYWJpbGl0eSBpbiB0aGUgbWl4dHVyZS4gRWFjaCBwb2ludCBoYXMgYSBwcm9iYWJpbGl0eSBvZiBiZWxvbmdpbmcgdG8gZWFjaCBjbHVzdGVyLgpGb3IgZXhhbXBsZSwgY29uc2lkZXIgdGhlIOKAnG9sZCBmYWl0aGZ1bCBnZXlzZXIgZGF0YeKAnSBbaW4gTUFTUyBSIHBhY2thZ2VdLCB3aGljaCBjYW4gYmUgaWxsdXN0cmF0ZWQgYXMgZm9sbG93IHVzaW5nIHRoZSBnZ3B1YnIgUiBwYWNrYWdlOgoKYGBge3J9CiMgTG9hZCB0aGUgZGF0YQpsaWJyYXJ5KCJNQVNTIikKZGF0YSgiZ2V5c2VyIikKIyBTY2F0dGVyIHBsb3QKbGlicmFyeSgiZ2dwdWJyIikKZ2dzY2F0dGVyKGdleXNlciwgeCA9ICJkdXJhdGlvbiIsIHkgPSAid2FpdGluZyIpKwogIGdlb21fZGVuc2l0eTJkKCkgIyBBZGQgMkQgZGVuc2l0eQpgYGAKCgoKClRoZSBwbG90IGFib3ZlIHN1Z2dlc3RzIGF0IGxlYXN0IDMgY2x1c3RlcnMgaW4gdGhlIG1peHR1cmUuIFRoZSBzaGFwZSBvZiBlYWNoIG9mIHRoZSAzIGNsdXN0ZXJzIGFwcGVhcnMgdG8gYmUgYXBwcm94aW1hdGVseSBlbGxpcHRpY2FsIHN1Z2dlc3RpbmcgdGhyZWUgYml2YXJpYXRlIG5vcm1hbCBkaXN0cmlidXRpb25zLiBBcyB0aGUgMyBlbGxpcHNlcyBzZWVtcyB0byBiZSBzaW1pbGFyIGluIHRlcm1zIG9mIHZvbHVtZSwgc2hhcGUgYW5kIG9yaWVudGF0aW9uLCB3ZSBtaWdodCBhbnRpY2lwYXRlIHRoYXQgdGhlIHRocmVlIGNvbXBvbmVudHMgb2YgdGhpcyBtaXh0dXJlIG1pZ2h0IGhhdmUgaG9tb2dlbmVvdXMgY292YXJpYW5jZSBtYXRyaWNlcy4KCiMjIyMgRXN0aW1hdGluZyBtb2RlbCBwYXJhbWV0ZXJzCgpUaGUgbW9kZWwgcGFyYW1ldGVycyBjYW4gYmUgZXN0aW1hdGVkIHVzaW5nIHRoZSBFeHBlY3RhdGlvbi1NYXhpbWl6YXRpb24gKEVNKSBhbGdvcml0aG0gaW5pdGlhbGl6ZWQgYnkgaGllcmFyY2hpY2FsIG1vZGVsLWJhc2VkIGNsdXN0ZXJpbmcuIEVhY2ggY2x1c3RlciBrIGlzIGNlbnRlcmVkIGF0IHRoZSBtZWFucyDOvGsKLCB3aXRoIGluY3JlYXNlZCBkZW5zaXR5IGZvciBwb2ludHMgbmVhciB0aGUgbWVhbi4KCkdlb21ldHJpYyBmZWF0dXJlcyAoc2hhcGUsIHZvbHVtZSwgb3JpZW50YXRpb24pIG9mIGVhY2ggY2x1c3RlciBhcmUgZGV0ZXJtaW5lZCBieSB0aGUgY292YXJpYW5jZSBtYXRyaXgg4oiRawouCgpEaWZmZXJlbnQgcG9zc2libGUgcGFyYW1ldGVyaXphdGlvbnMgb2Yg4oiRawogYXJlIGF2YWlsYWJsZSBpbiB0aGUgUiBwYWNrYWdlIG1jbHVzdCAoc2VlID9tY2x1c3RNb2RlbE5hbWVzKS4KClRoZSBhdmFpbGFibGUgbW9kZWwgb3B0aW9ucywgaW4gbWNsdXN0IHBhY2thZ2UsIGFyZSByZXByZXNlbnRlZCBieSBpZGVudGlmaWVycyBpbmNsdWRpbmc6IEVJSSwgVklJLCBFRUksIFZFSSwgRVZJLCBWVkksIEVFRSwgRUVWLCBWRVYgYW5kIFZWVi4KClRoZSBmaXJzdCBpZGVudGlmaWVyIHJlZmVycyB0byB2b2x1bWUsIHRoZSBzZWNvbmQgdG8gc2hhcGUgYW5kIHRoZSB0aGlyZCB0byBvcmllbnRhdGlvbi4gRSBzdGFuZHMgZm9yIOKAnGVxdWFs4oCdLCBWIGZvciDigJx2YXJpYWJsZeKAnSBhbmQgSSBmb3Ig4oCcY29vcmRpbmF0ZSBheGVz4oCdLgoKRm9yIGV4YW1wbGU6CgpFVkkgZGVub3RlcyBhIG1vZGVsIGluIHdoaWNoIHRoZSB2b2x1bWVzIG9mIGFsbCBjbHVzdGVycyBhcmUgZXF1YWwgKEUpLCB0aGUgc2hhcGVzIG9mIHRoZSBjbHVzdGVycyBtYXkgdmFyeSAoViksIGFuZCB0aGUgb3JpZW50YXRpb24gaXMgdGhlIGlkZW50aXR5IChJKSBvciDigJxjb29yZGluYXRlIGF4ZXMuCkVFRSBtZWFucyB0aGF0IHRoZSBjbHVzdGVycyBoYXZlIHRoZSBzYW1lIHZvbHVtZSwgc2hhcGUgYW5kIG9yaWVudGF0aW9uIGluIHAtZGltZW5zaW9uYWwgc3BhY2UuClZFSSBtZWFucyB0aGF0IHRoZSBjbHVzdGVycyBoYXZlIHZhcmlhYmxlIHZvbHVtZSwgdGhlIHNhbWUgc2hhcGUgYW5kIG9yaWVudGF0aW9uIGVxdWFsIHRvIGNvb3JkaW5hdGUgYXhlcy4KQ2hvb3NpbmcgdGhlIGJlc3QgbW9kZWwKClRoZSBNY2x1c3QgcGFja2FnZSB1c2VzIG1heGltdW0gbGlrZWxpaG9vZCB0byBmaXQgYWxsIHRoZXNlIG1vZGVscywgd2l0aCBkaWZmZXJlbnQgY292YXJpYW5jZSBtYXRyaXggcGFyYW1ldGVyaXphdGlvbnMsIGZvciBhIHJhbmdlIG9mIGsgY29tcG9uZW50cy4KClRoZSBiZXN0IG1vZGVsIGlzIHNlbGVjdGVkIHVzaW5nIHRoZSBCYXllc2lhbiBJbmZvcm1hdGlvbiBDcml0ZXJpb24gb3IgQklDLiBBIGxhcmdlIEJJQyBzY29yZSBpbmRpY2F0ZXMgc3Ryb25nIGV2aWRlbmNlIGZvciB0aGUgY29ycmVzcG9uZGluZyBtb2RlbC4KCgoKYGBge3J9CmxpYnJhcnkoIm1jbHVzdCIpCmRhdGEoImRpYWJldGVzIikKaGVhZChkaWFiZXRlcywgMykKCmRmIDwtIHNjYWxlKGRpYWJldGVzWywgLTFdKSAjIFN0YW5kYXJkaXplIHRoZSBkYXRhCm1jIDwtIE1jbHVzdChkZikgICAgICAgICAgICAjIE1vZGVsLWJhc2VkLWNsdXN0ZXJpbmcKc3VtbWFyeShtYykgICAgICAgICAgICAgICAgICMgUHJpbnQgYSBzdW1tYXJ5CmBgYAoKCkZvciB0aGlzIGRhdGEsIGl0IGNhbiBiZSBzZWVuIHRoYXQgbW9kZWwtYmFzZWQgY2x1c3RlcmluZyBzZWxlY3RlZCBhIG1vZGVsIHdpdGggdGhyZWUgY29tcG9uZW50cyAoaS5lLiBjbHVzdGVycykuIFRoZSBvcHRpbWFsIHNlbGVjdGVkIG1vZGVsIG5hbWUgaXMgVlZWIG1vZGVsLiBUaGF0IGlzIHRoZSB0aHJlZSBjb21wb25lbnRzIGFyZSBlbGxpcHNvaWRhbCB3aXRoIHZhcnlpbmcgdm9sdW1lLCBzaGFwZSwgYW5kIG9yaWVudGF0aW9uLiBUaGUgc3VtbWFyeSBjb250YWlucyBhbHNvIHRoZSBjbHVzdGVyaW5nIHRhYmxlIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgaW4gZWFjaCBjbHVzdGVycy4KCllvdSBjYW4gYWNjZXNzIHRvIHRoZSByZXN1bHRzIGFzIGZvbGxvdzoKCmBgYHtyfQptYyRtb2RlbE5hbWUgICAgICAgICAgICAgICAgIyBPcHRpbWFsIHNlbGVjdGVkIG1vZGVsID09PiAiVlZWIgptYyRHICAgICAgICAgICAgICAgICAgICAgICAgIyBPcHRpbWFsIG51bWJlciBvZiBjbHVzdGVyID0+IDMKaGVhZChtYyR6LCAzMCkgICAgICAgICAgICAgICMgUHJvYmFsaXR5IHRvIGJlbG9uZyB0byBhIGdpdmVuIGNsdXN0ZXIKaGVhZChtYyRjbGFzc2lmaWNhdGlvbiwgMTApICMgQ2x1c3RlciBhc3NpZ25lbWVudCBvZiBlYWNoIG9ic2VydmF0aW9uCmBgYAoKCgojIyMjIFZpc3VhbGl6aW5nIG1vZGVsLWJhc2VkIGNsdXN0ZXJpbmcKCk1vZGVsLWJhc2VkIGNsdXN0ZXJpbmcgcmVzdWx0cyBjYW4gYmUgZHJhd24gdXNpbmcgdGhlIGJhc2UgZnVuY3Rpb24gcGxvdC5NY2x1c3QoKSBbaW4gbWNsdXN0IHBhY2thZ2VdLiBIZXJlIHdl4oCZbGwgdXNlIHRoZSBmdW5jdGlvbiBmdml6X21jbHVzdCgpIFtpbiBmYWN0b2V4dHJhIHBhY2thZ2VdIHRvIGNyZWF0ZSBiZWF1dGlmdWwgcGxvdHMgYmFzZWQgb24gZ2dwbG90Mi4KCkluIHRoZSBzaXR1YXRpb24sIHdoZXJlIHRoZSBkYXRhIGNvbnRhaW4gbW9yZSB0aGFuIHR3byB2YXJpYWJsZXMsIGZ2aXpfbWNsdXN0KCkgdXNlcyBhIHByaW5jaXBhbCBjb21wb25lbnQgYW5hbHlzaXMgdG8gcmVkdWNlIHRoZSBkaW1lbnNpb25uYWxpdHkgb2YgdGhlIGRhdGEuIFRoZSBmaXJzdCB0d28gcHJpbmNpcGFsIGNvbXBvbmVudHMgYXJlIHVzZWQgdG8gcHJvZHVjZSBhIHNjYXR0ZXIgcGxvdCBvZiB0aGUgZGF0YS4gSG93ZXZlciwgaWYgeW91IHdhbnQgdG8gcGxvdCB0aGUgZGF0YSB1c2luZyBvbmx5IHR3byB2YXJpYWJsZXMgb2YgaW50ZXJlc3QsIGxldCBzYXkgaGVyZSBjKOKAnGluc3VsaW7igJ0sIOKAnHNzcGfigJ0pLCB5b3UgY2FuIHNwZWNpZnkgdGhhdCBpbiB0aGUgZnZpel9tY2x1c3QoKSBmdW5jdGlvbiB1c2luZyB0aGUgYXJndW1lbnQgY2hvb3NlLnZhcnMgPSBjKOKAnGluc3VsaW7igJ0sIOKAnHNzcGfigJ0pLgpgYGB7cn0KbGlicmFyeShmYWN0b2V4dHJhKQojIEJJQyB2YWx1ZXMgdXNlZCBmb3IgY2hvb3NpbmcgdGhlIG51bWJlciBvZiBjbHVzdGVycwpmdml6X21jbHVzdChtYywgIkJJQyIsIHBhbGV0dGUgPSAiamNvIikKIyBDbGFzc2lmaWNhdGlvbjogcGxvdCBzaG93aW5nIHRoZSBjbHVzdGVyaW5nCmZ2aXpfbWNsdXN0KG1jLCAiY2xhc3NpZmljYXRpb24iLCBnZW9tID0gInBvaW50IiwgCiAgICAgICAgICAgIHBvaW50c2l6ZSA9IDEuNSwgcGFsZXR0ZSA9ICJqY28iKQojIENsYXNzaWZpY2F0aW9uIHVuY2VydGFpbnR5CmZ2aXpfbWNsdXN0KG1jLCAidW5jZXJ0YWludHkiLCBwYWxldHRlID0gImpjbyIpCmBgYAoKCgojIyMjIERCU0NBTjogRGVuc2l0eS1CYXNlZCBDbHVzdGVyaW5nIEVzc2VudGlhbHMKCgpEQlNDQU4gKERlbnNpdHktQmFzZWQgU3BhdGlhbCBDbHVzdGVyaW5nIGFuZCBBcHBsaWNhdGlvbiB3aXRoIE5vaXNlKSwgaXMgYSBkZW5zaXR5LWJhc2VkIGNsdXNlcmluZyBhbGdvcml0aG0sIGludHJvZHVjZWQgaW4gRXN0ZXIgZXQgYWwuIDE5OTYsIHdoaWNoIGNhbiBiZSB1c2VkIHRvIGlkZW50aWZ5IGNsdXN0ZXJzIG9mIGFueSBzaGFwZSBpbiBhIGRhdGEgc2V0IGNvbnRhaW5pbmcgbm9pc2UgYW5kIG91dGxpZXJzLgoKVGhlIGJhc2ljIGlkZWEgYmVoaW5kIHRoZSBkZW5zaXR5LWJhc2VkIGNsdXN0ZXJpbmcgYXBwcm9hY2ggaXMgZGVyaXZlZCBmcm9tIGEgaHVtYW4gaW50dWl0aXZlIGNsdXN0ZXJpbmcgbWV0aG9kLiBGb3IgaW5zdGFuY2UsIGJ5IGxvb2tpbmcgYXQgdGhlIGZpZ3VyZSBiZWxvdywgb25lIGNhbiBlYXNpbHkgaWRlbnRpZnkgZm91ciBjbHVzdGVycyBhbG9uZyB3aXRoIHNldmVyYWwgcG9pbnRzIG9mIG5vaXNlLCBiZWNhdXNlIG9mIHRoZSBkaWZmZXJlbmNlcyBpbiB0aGUgZGVuc2l0eSBvZiBwb2ludHMuCgpDbHVzdGVycyBhcmUgZGVuc2UgcmVnaW9ucyBpbiB0aGUgZGF0YSBzcGFjZSwgc2VwYXJhdGVkIGJ5IHJlZ2lvbnMgb2YgbG93ZXIgZGVuc2l0eSBvZiBwb2ludHMuIFRoZSBEQlNDQU4gYWxnb3JpdGhtIGlzIGJhc2VkIG9uIHRoaXMgaW50dWl0aXZlIG5vdGlvbiBvZiDigJxjbHVzdGVyc+KAnSBhbmQg4oCcbm9pc2XigJ0uIFRoZSBrZXkgaWRlYSBpcyB0aGF0IGZvciBlYWNoIHBvaW50IG9mIGEgY2x1c3RlciwgdGhlIG5laWdoYm9yaG9vZCBvZiBhIGdpdmVuIHJhZGl1cyBoYXMgdG8gY29udGFpbiBhdCBsZWFzdCBhIG1pbmltdW0gbnVtYmVyIG9mIHBvaW50cy4KCgpXaHkgREJTQ0FOPwoKUGFydGl0aW9uaW5nIG1ldGhvZHMgKEstbWVhbnMsIFBBTSBjbHVzdGVyaW5nKSBhbmQgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgYXJlIHN1aXRhYmxlIGZvciBmaW5kaW5nIHNwaGVyaWNhbC1zaGFwZWQgY2x1c3RlcnMgb3IgY29udmV4IGNsdXN0ZXJzLiBJbiBvdGhlciB3b3JkcywgdGhleSB3b3JrIHdlbGwgb25seSBmb3IgY29tcGFjdCBhbmQgd2VsbCBzZXBhcmF0ZWQgY2x1c3RlcnMuIE1vcmVvdmVyLCB0aGV5IGFyZSBhbHNvIHNldmVyZWx5IGFmZmVjdGVkIGJ5IHRoZSBwcmVzZW5jZSBvZiBub2lzZSBhbmQgb3V0bGllcnMgaW4gdGhlIGRhdGEuCgpVbmZvcnR1bmF0ZWx5LCByZWFsIGxpZmUgZGF0YSBjYW4gY29udGFpbjogaSkgY2x1c3RlcnMgb2YgYXJiaXRyYXJ5IHNoYXBlIHN1Y2ggYXMgdGhvc2Ugc2hvd24gaW4gdGhlIGZpZ3VyZSBiZWxvdyAob3ZhbCwgbGluZWFyIGFuZCDigJxT4oCdIHNoYXBlIGNsdXN0ZXJzKTsgaWkpIG1hbnkgb3V0bGllcnMgYW5kIG5vaXNlLgoKVGhlIGZpZ3VyZSBiZWxvdyBzaG93cyBhIGRhdGEgc2V0IGNvbnRhaW5pbmcgbm9uY29udmV4IGNsdXN0ZXJzIGFuZCBvdXRsaWVycy9ub2lzZXMuIFRoZSBzaW11bGF0ZWQgZGF0YSBzZXQgbXVsdGlzaGFwZXMgW2luIGZhY3RvZXh0cmEgcGFja2FnZV0gaXMgdXNlZC4KCgpgYGB7cn0KZGF0YSgibXVsdGlzaGFwZXMiKQpkZiA8LSBtdWx0aXNoYXBlc1ssIDE6Ml0Kc2V0LnNlZWQoMTIzKQprbS5yZXMgPC0ga21lYW5zKGRmLCA1LCBuc3RhcnQgPSAyNSkKZnZpel9jbHVzdGVyKGttLnJlcywgZGYsICBnZW9tID0gInBvaW50IiwgCiAgICAgICAgICAgICBlbGxpcHNlPSBGQUxTRSwgc2hvdy5jbHVzdC5jZW50ID0gRkFMU0UsCiAgICAgICAgICAgICBwYWxldHRlID0gImpjbyIsIGdndGhlbWUgPSB0aGVtZV9jbGFzc2ljKCkpCmBgYAoKCgojIyMjIENvbXB1dGluZyBEQlNDQU4KCkhlcmUsIHdl4oCZbGwgdXNlIHRoZSBSIHBhY2thZ2UgZnBjIHRvIGNvbXB1dGUgREJTQ0FOLiBJdOKAmXMgYWxzbyBwb3NzaWJsZSB0byB1c2UgdGhlIHBhY2thZ2UgZGJzY2FuLCB3aGljaCBwcm92aWRlcyBhIGZhc3RlciByZS1pbXBsZW1lbnRhdGlvbiBvZiBEQlNDQU4gYWxnb3JpdGhtIGNvbXBhcmVkIHRvIHRoZSBmcGMgcGFja2FnZS4KCldl4oCZbGwgYWxzbyB1c2UgdGhlIGZhY3RvZXh0cmEgcGFja2FnZSBmb3IgdmlzdWFsaXppbmcgY2x1c3RlcnMuCgpGaXJzdCwgaW5zdGFsbCB0aGUgcGFja2FnZXMgYXMgZm9sbG93OgoKYGBge3J9CiNpbnN0YWxsLnBhY2thZ2VzKCJmcGMiKQojaW5zdGFsbC5wYWNrYWdlcygiZGJzY2FuIikKYGBgCgoKCmBgYHtyfQojIExvYWQgdGhlIGRhdGEgCmRhdGEoIm11bHRpc2hhcGVzIiwgcGFja2FnZSA9ICJmYWN0b2V4dHJhIikKZGYgPC0gbXVsdGlzaGFwZXNbLCAxOjJdCiMgQ29tcHV0ZSBEQlNDQU4gdXNpbmcgZnBjIHBhY2thZ2UKbGlicmFyeSgiZnBjIikKc2V0LnNlZWQoMTIzKQpkYiA8LSBmcGM6OmRic2NhbihkZiwgZXBzID0gMC4xNSwgTWluUHRzID0gNSkKIyBQbG90IERCU0NBTiByZXN1bHRzCmxpYnJhcnkoImZhY3RvZXh0cmEiKQpmdml6X2NsdXN0ZXIoZGIsIGRhdGEgPSBkZiwgc3RhbmQgPSBGQUxTRSwKICAgICAgICAgICAgIGVsbGlwc2UgPSBGQUxTRSwgc2hvdy5jbHVzdC5jZW50ID0gRkFMU0UsCiAgICAgICAgICAgICBnZW9tID0gInBvaW50IixwYWxldHRlID0gImpjbyIsIGdndGhlbWUgPSB0aGVtZV9jbGFzc2ljKCkpCmBgYAoKCgoKCmBgYHtyfQpwcmludChkYikKYGBgCgpJbiB0aGUgdGFibGUgYWJvdmUsIGNvbHVtbiBuYW1lcyBhcmUgY2x1c3RlciBudW1iZXIuIENsdXN0ZXIgMCBjb3JyZXNwb25kcyB0byBvdXRsaWVycyAoYmxhY2sgcG9pbnRzIGluIHRoZSBEQlNDQU4gcGxvdCkuIFRoZSBmdW5jdGlvbiBwcmludC5kYnNjYW4oKSBzaG93cyBhIHN0YXRpc3RpYyBvZiB0aGUgbnVtYmVyIG9mIHBvaW50cyBiZWxvbmdpbmcgdG8gdGhlIGNsdXN0ZXJzIHRoYXQgYXJlIHNlZWRzIGFuZCBib3JkZXIgcG9pbnRzLgoKYGBge3J9CiMgQ2x1c3RlciBtZW1iZXJzaGlwLiBOb2lzZS9vdXRsaWVyIG9ic2VydmF0aW9ucyBhcmUgY29kZWQgYXMgMAojIEEgcmFuZG9tIHN1YnNldCBpcyBzaG93bgpkYiRjbHVzdGVyW3NhbXBsZSgxOjEwODksIDIwKV0KYGBgCgoKCiMjIyMgTWV0aG9kIGZvciBkZXRlcm1pbmluZyB0aGUgb3B0aW1hbCBlcHMgdmFsdWUKClRoZSBtZXRob2QgcHJvcG9zZWQgaGVyZSBjb25zaXN0cyBvZiBjb21wdXRpbmcgdGhlIGstbmVhcmVzdCBuZWlnaGJvciBkaXN0YW5jZXMgaW4gYSBtYXRyaXggb2YgcG9pbnRzLgoKVGhlIGlkZWEgaXMgdG8gY2FsY3VsYXRlLCB0aGUgYXZlcmFnZSBvZiB0aGUgZGlzdGFuY2VzIG9mIGV2ZXJ5IHBvaW50IHRvIGl0cyBrIG5lYXJlc3QgbmVpZ2hib3JzLiBUaGUgdmFsdWUgb2YgayB3aWxsIGJlIHNwZWNpZmllZCBieSB0aGUgdXNlciBhbmQgY29ycmVzcG9uZHMgdG8gTWluUHRzLgoKTmV4dCwgdGhlc2Ugay1kaXN0YW5jZXMgYXJlIHBsb3R0ZWQgaW4gYW4gYXNjZW5kaW5nIG9yZGVyLiBUaGUgYWltIGlzIHRvIGRldGVybWluZSB0aGUg4oCca25lZeKAnSwgd2hpY2ggY29ycmVzcG9uZHMgdG8gdGhlIG9wdGltYWwgZXBzIHBhcmFtZXRlci4KCkEga25lZSBjb3JyZXNwb25kcyB0byBhIHRocmVzaG9sZCB3aGVyZSBhIHNoYXJwIGNoYW5nZSBvY2N1cnMgYWxvbmcgdGhlIGstZGlzdGFuY2UgY3VydmUuCgpUaGUgZnVuY3Rpb24ga05OZGlzdHBsb3QoKSBbaW4gZGJzY2FuIHBhY2thZ2VdIGNhbiBiZSB1c2VkIHRvIGRyYXcgdGhlIGstZGlzdGFuY2UgcGxvdDoKCgpgYGB7cn0KZGJzY2FuOjprTk5kaXN0cGxvdChkZiwgayA9ICA1KQphYmxpbmUoaCA9IDAuMTUsIGx0eSA9IDIpCmBgYAoKCgojIyMjIEhDUEMgLSBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZyBvbiBQcmluY2lwYWwgQ29tcG9uZW50czogRXNzZW50aWFscwoKQ2x1c3RlcmluZyBpcyBvbmUgb2YgdGhlIGltcG9ydGFudCBkYXRhIG1pbmluZyBtZXRob2RzIGZvciBkaXNjb3ZlcmluZyBrbm93bGVkZ2UgaW4gbXVsdGl2YXJpYXRlIGRhdGEgc2V0cy4gVGhlIGdvYWwgaXMgdG8gaWRlbnRpZnkgZ3JvdXBzIChpLmUuIGNsdXN0ZXJzKSBvZiBzaW1pbGFyIG9iamVjdHMgd2l0aGluIGEgZGF0YSBzZXQgb2YgaW50ZXJlc3QuIFRvIGxlYXJuIG1vcmUgYWJvdXQgY2x1c3RlcmluZywgeW91IGNhbiByZWFkIG91ciBib29rIGVudGl0bGVkIOKAnFByYWN0aWNhbCBHdWlkZSB0byBDbHVzdGVyIEFuYWx5c2lzIGluIFLigJ0gKGh0dHBzOi8vZ29vLmdsL0RtSjV5NSkuCgpCcmllZmx5LCB0aGUgdHdvIG1vc3QgY29tbW9uIGNsdXN0ZXJpbmcgc3RyYXRlZ2llcyBhcmU6CgpIaWVyYXJjaGljYWwgY2x1c3RlcmluZywgdXNlZCBmb3IgaWRlbnRpZnlpbmcgZ3JvdXBzIG9mIHNpbWlsYXIgb2JzZXJ2YXRpb25zIGluIGEgZGF0YSBzZXQuClBhcnRpdGlvbmluZyBjbHVzdGVyaW5nIHN1Y2ggYXMgay1tZWFucyBhbGdvcml0aG0sIHVzZWQgZm9yIHNwbGl0dGluZyBhIGRhdGEgc2V0IGludG8gc2V2ZXJhbCBncm91cHMuClRoZSBIQ1BDIChIaWVyYXJjaGljYWwgQ2x1c3RlcmluZyBvbiBQcmluY2lwYWwgQ29tcG9uZW50cykgYXBwcm9hY2ggYWxsb3dzIHVzIHRvIGNvbWJpbmUgdGhlIHRocmVlIHN0YW5kYXJkIG1ldGhvZHMgdXNlZCBpbiBtdWx0aXZhcmlhdGUgZGF0YSBhbmFseXNlcyAoSHVzc29uLCBKb3NzZSwgYW5kIEouIDIwMTApOgoKUHJpbmNpcGFsIGNvbXBvbmVudCBtZXRob2RzIChQQ0EsIENBLCBNQ0EsIEZBTUQsIE1GQSksCkhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIGFuZApQYXJ0aXRpb25pbmcgY2x1c3RlcmluZywgcGFydGljdWxhcmx5IHRoZSBrLW1lYW5zIG1ldGhvZC4KCgoKV2h5IEhDUEMKCkNvbWJpbmluZyBwcmluY2lwYWwgY29tcG9uZW50IG1ldGhvZHMgYW5kIGNsdXN0ZXJpbmcgbWV0aG9kcyBhcmUgdXNlZnVsIGluIGF0IGxlYXN0IHRocmVlIHNpdHVhdGlvbnMuCgpDYXNlIDE6IENvbnRpbnVvdXMgdmFyaWFibGVzCgpJbiB0aGUgc2l0dWF0aW9uIHdoZXJlIHlvdSBoYXZlIGEgbXVsdGlkaW1lbnNpb25hbCBkYXRhIHNldCBjb250YWluaW5nIG11bHRpcGxlIGNvbnRpbnVvdXMgdmFyaWFibGVzLCB0aGUgcHJpbmNpcGFsIGNvbXBvbmVudCBhbmFseXNpcyAoUENBKSBjYW4gYmUgdXNlZCB0byByZWR1Y2UgdGhlIGRpbWVuc2lvbiBvZiB0aGUgZGF0YSBpbnRvIGZldyBjb250aW51b3VzIHZhcmlhYmxlcyBjb250YWluaW5nIHRoZSBtb3N0IGltcG9ydGFudCBpbmZvcm1hdGlvbiBpbiB0aGUgZGF0YS4gTmV4dCwgeW91IGNhbiBwZXJmb3JtIGNsdXN0ZXIgYW5hbHlzaXMgb24gdGhlIFBDQSByZXN1bHRzLgoKVGhlIFBDQSBzdGVwIGNhbiBiZSBjb25zaWRlcmVkIGFzIGEgZGVub2lzaW5nIHN0ZXAgd2hpY2ggY2FuIGxlYWQgdG8gYSBtb3JlIHN0YWJsZSBjbHVzdGVyaW5nLiBUaGlzIG1pZ2h0IGJlIHZlcnkgdXNlZnVsIGlmIHlvdSBoYXZlIGEgbGFyZ2UgZGF0YSBzZXQgd2l0aCBtdWx0aXBsZSB2YXJpYWJsZXMsIHN1Y2ggYXMgaW4gZ2VuZSBleHByZXNzaW9uIGRhdGEuCgpDYXNlIDI6IENsdXN0ZXJpbmcgb24gY2F0ZWdvcmljYWwgZGF0YQoKSW4gb3JkZXIgdG8gcGVyZm9ybSBjbHVzdGVyaW5nIGFuYWx5c2lzIG9uIGNhdGVnb3JpY2FsIGRhdGEsIHRoZSBjb3JyZXNwb25kZW5jZSBhbmFseXNpcyAoQ0EsIGZvciBhbmFseXppbmcgY29udGluZ2VuY3kgdGFibGUpIGFuZCB0aGUgbXVsdGlwbGUgY29ycmVzcG9uZGVuY2UgYW5hbHlzaXMgKE1DQSwgZm9yIGFuYWx5emluZyBtdWx0aWRpbWVuc2lvbmFsIGNhdGVnb3JpY2FsIHZhcmlhYmxlcykgY2FuIGJlIHVzZWQgdG8gdHJhbnNmb3JtIGNhdGVnb3JpY2FsIHZhcmlhYmxlcyBpbnRvIGEgc2V0IG9mIGZldyBjb250aW51b3VzIHZhcmlhYmxlcyAodGhlIHByaW5jaXBhbCBjb21wb25lbnRzKS4gVGhlIGNsdXN0ZXIgYW5hbHlzaXMgY2FuIGJlIHRoZW4gYXBwbGllZCBvbiB0aGUgKE0pQ0EgcmVzdWx0cy4KCkluIHRoaXMgY2FzZSwgdGhlIChNKUNBIG1ldGhvZCBjYW4gYmUgY29uc2lkZXJlZCBhcyBwcmUtcHJvY2Vzc2luZyBzdGVwcyB3aGljaCBhbGxvdyB0byBjb21wdXRlIGNsdXN0ZXJpbmcgb24gY2F0ZWdvcmljYWwgZGF0YS4KCkNhc2UgMzogQ2x1c3RlcmluZyBvbiBtaXhlZCBkYXRhCgpXaGVuIHlvdSBoYXZlIGEgbWl4ZWQgZGF0YSBvZiBjb250aW51b3VzIGFuZCBjYXRlZ29yaWNhbCB2YXJpYWJsZXMsIHlvdSBjYW4gZmlyc3QgcGVyZm9ybSBGQU1EIChmYWN0b3IgYW5hbHlzaXMgb2YgbWl4ZWQgZGF0YSkgb3IgTUZBIChtdWx0aXBsZSBmYWN0b3IgYW5hbHlzaXMpLiBOZXh0LCB5b3UgY2FuIGFwcGx5IGNsdXN0ZXIgYW5hbHlzaXMgb24gdGhlIEZBTUQvTUZBIG91dHB1dHMuCgpBbGdvcml0aG0gb2YgdGhlIEhDUEMgbWV0aG9kCgpUaGUgYWxnb3JpdGhtIG9mIHRoZSBIQ1BDIG1ldGhvZCwgYXMgaW1wbGVtZW50ZWQgaW4gdGhlIEZhY3RvTWluZVIgcGFja2FnZSwgY2FuIGJlIHN1bW1hcml6ZWQgYXMgZm9sbG93OgoKQ29tcHV0ZSBwcmluY2lwYWwgY29tcG9uZW50IG1ldGhvZHM6IFBDQSwgKE0pQ0Egb3IgTUZBIGRlcGVuZGluZyBvbiB0aGUgdHlwZXMgb2YgdmFyaWFibGVzIGluIHRoZSBkYXRhIHNldCBhbmQgdGhlIHN0cnVjdHVyZSBvZiB0aGUgZGF0YSBzZXQuIEF0IHRoaXMgc3RlcCwgeW91IGNhbiBjaG9vc2UgdGhlIG51bWJlciBvZiBkaW1lbnNpb25zIHRvIGJlIHJldGFpbmVkIGluIHRoZSBvdXRwdXQgYnkgc3BlY2lmeWluZyB0aGUgYXJndW1lbnQgbmNwLiBUaGUgZGVmYXVsdCB2YWx1ZSBpcyA1LgoKQ29tcHV0ZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZzogSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgaXMgcGVyZm9ybWVkIHVzaW5nIHRoZSBXYXJk4oCZcyBjcml0ZXJpb24gb24gdGhlIHNlbGVjdGVkIHByaW5jaXBhbCBjb21wb25lbnRzLiBXYXJkIGNyaXRlcmlvbiBpcyB1c2VkIGluIHRoZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBiZWNhdXNlIGl0IGlzIGJhc2VkIG9uIHRoZSBtdWx0aWRpbWVuc2lvbmFsIHZhcmlhbmNlIGxpa2UgcHJpbmNpcGFsIGNvbXBvbmVudCBhbmFseXNpcy4KCkNob29zZSB0aGUgbnVtYmVyIG9mIGNsdXN0ZXJzIGJhc2VkIG9uIHRoZSBoaWVyYXJjaGljYWwgdHJlZTogQW4gaW5pdGlhbCBwYXJ0aXRpb25pbmcgaXMgcGVyZm9ybWVkIGJ5IGN1dHRpbmcgdGhlIGhpZXJhcmNoaWNhbCB0cmVlLgoKUGVyZm9ybSBLLW1lYW5zIGNsdXN0ZXJpbmcgdG8gaW1wcm92ZSB0aGUgaW5pdGlhbCBwYXJ0aXRpb24gb2J0YWluZWQgZnJvbSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4gVGhlIGZpbmFsIHBhcnRpdGlvbmluZyBzb2x1dGlvbiwgb2J0YWluZWQgYWZ0ZXIgY29uc29saWRhdGlvbiB3aXRoIGstbWVhbnMsIGNhbiBiZSAoc2xpZ2h0bHkpIGRpZmZlcmVudCBmcm9tIHRoZSBvbmUgb2J0YWluZWQgd2l0aCB0aGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcuCgpDb21wdXRhdGlvbgoKUiBwYWNrYWdlcwoKV2XigJlsbCB1c2UgdHdvIFIgcGFja2FnZXM6IGkpIEZhY3RvTWluZVIgZm9yIGNvbXB1dGluZyBIQ1BDIGFuZCBpaSkgZmFjdG9leHRyYSBmb3IgdmlzdWFsaXppbmcgdGhlIHJlc3VsdHMuCgpUbyBpbnN0YWxsIHRoZSBwYWNrYWdlcywgdHlwZSB0aGlzOgoKYGBge3J9CmxpYnJhcnkoZmFjdG9leHRyYSkKbGlicmFyeShGYWN0b01pbmVSKQpgYGAKClRoZSBmdW5jdGlvbiBIQ1BDKCkgW2luIEZhY3RvTWluZVIgcGFja2FnZV0gY2FuIGJlIHVzZWQgdG8gY29tcHV0ZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBvbiBwcmluY2lwYWwgY29tcG9uZW50cy4KCkEgc2ltcGxpZmllZCBmb3JtYXQgaXM6CgpgYGB7cn0KI0hDUEMocmVzLCBuYi5jbHVzdCA9IDAsIG1pbiA9IDMsIG1heCA9IE5VTEwsIGdyYXBoID0gVFJVRSkKYGBgCgoKCnJlczogRWl0aGVyIHRoZSByZXN1bHQgb2YgYSBmYWN0b3IgYW5hbHlzaXMgb3IgYSBkYXRhIGZyYW1lLgpuYi5jbHVzdDogYW4gaW50ZWdlciBzcGVjaWZ5aW5nIHRoZSBudW1iZXIgb2YgY2x1c3RlcnMuIFBvc3NpYmxlIHZhbHVlcyBhcmU6CjA6IHRoZSB0cmVlIGlzIGN1dCBhdCB0aGUgbGV2ZWwgdGhlIHVzZXIgY2xpY2tzIG9uCi0xOiB0aGUgdHJlZSBpcyBhdXRvbWF0aWNhbGx5IGN1dCBhdCB0aGUgc3VnZ2VzdGVkIGxldmVsCkFueSBwb3NpdGl2ZSBpbnRlZ2VyOiB0aGUgdHJlZSBpcyBjdXQgd2l0aCBuYi5jbHVzdGVycyBjbHVzdGVycwptaW4sIG1heDogdGhlIG1pbmltdW0gYW5kIHRoZSBtYXhpbXVtIG51bWJlciBvZiBjbHVzdGVycyB0byBiZSBnZW5lcmF0ZWQsIHJlc3BlY3RpdmVseQpncmFwaDogaWYgVFJVRSwgZ3JhcGhpY3MgYXJlIGRpc3BsYXllZApDYXNlIG9mIGNvbnRpbnVvdXMgdmFyaWFibGVzCgpXZSBzdGFydCBieSBjb21wdXRpbmcgYWdhaW4gdGhlIHByaW5jaXBhbCBjb21wb25lbnQgYW5hbHlzaXMgKFBDQSkuIFRoZSBhcmd1bWVudCBuY3AgPSAzIGlzIHVzZWQgaW4gdGhlIGZ1bmN0aW9uIFBDQSgpIHRvIGtlZXAgb25seSB0aGUgZmlyc3QgdGhyZWUgcHJpbmNpcGFsIGNvbXBvbmVudHMuIE5leHQsIHRoZSBIQ1BDIGlzIGFwcGxpZWQgb24gdGhlIHJlc3VsdCBvZiB0aGUgUENBLgoKYGBge3J9CiMgQ29tcHV0ZSBQQ0Egd2l0aCBuY3AgPSAzCnJlcy5wY2EgPC0gUENBKFVTQXJyZXN0cywgbmNwID0gMywgZ3JhcGggPSBGQUxTRSkKIyBDb21wdXRlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIG9uIHByaW5jaXBhbCBjb21wb25lbnRzCnJlcy5oY3BjIDwtIEhDUEMocmVzLnBjYSwgZ3JhcGggPSBGQUxTRSkKYGBgCgpUbyB2aXN1YWxpemUgdGhlIGRlbmRyb2dyYW0gZ2VuZXJhdGVkIGJ5IHRoZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZywgd2XigJlsbCB1c2UgdGhlIGZ1bmN0aW9uIGZ2aXpfZGVuZCgpIFtmYWN0b2V4dHJhIHBhY2thZ2VdOgoKYGBge3J9CmZ2aXpfZGVuZChyZXMuaGNwYywgCiAgICAgICAgICBjZXggPSAwLjcsICAgICAgICAgICAgICAgICAgICAgIyBMYWJlbCBzaXplCiAgICAgICAgICBwYWxldHRlID0gImpjbyIsICAgICAgICAgICAgICAgIyBDb2xvciBwYWxldHRlIHNlZSA/Z2dwdWJyOjpnZ3BhcgogICAgICAgICAgcmVjdCA9IFRSVUUsIHJlY3RfZmlsbCA9IFRSVUUsICMgQWRkIHJlY3RhbmdsZSBhcm91bmQgZ3JvdXBzCiAgICAgICAgICByZWN0X2JvcmRlciA9ICJqY28iLCAgICAgICAgICAgIyBSZWN0YW5nbGUgY29sb3IKICAgICAgICAgIGxhYmVsc190cmFja19oZWlnaHQgPSAwLjggICAgICAjIEF1Z21lbnQgdGhlIHJvb20gZm9yIGxhYmVscwogICAgICAgICAgKQpgYGAKCkl04oCZcyBwb3NzaWJsZSB0byB2aXN1YWxpemUgaW5kaXZpZHVhbHMgb24gdGhlIHByaW5jaXBhbCBjb21wb25lbnQgbWFwIGFuZCB0byBjb2xvciBpbmRpdmlkdWFscyBhY2NvcmRpbmcgdG8gdGhlIGNsdXN0ZXIgdGhleSBiZWxvbmcgdG8uIFRoZSBmdW5jdGlvbiBmdml6X2NsdXN0ZXIoKSBbaW4gZmFjdG9leHRyYV0gY2FuIGJlIHVzZWQgdG8gdmlzdWFsaXplIGluZGl2aWR1YWxzIGNsdXN0ZXJzLgoKCmBgYHtyfQpmdml6X2NsdXN0ZXIocmVzLmhjcGMsCiAgICAgICAgICAgICByZXBlbCA9IFRSVUUsICAgICAgICAgICAgIyBBdm9pZCBsYWJlbCBvdmVybGFwcGluZwogICAgICAgICAgICAgc2hvdy5jbHVzdC5jZW50ID0gVFJVRSwgIyBTaG93IGNsdXN0ZXIgY2VudGVycwogICAgICAgICAgICAgcGFsZXR0ZSA9ICJqY28iLCAgICAgICAgICMgQ29sb3IgcGFsZXR0ZSBzZWUgP2dncHVicjo6Z2dwYXIKICAgICAgICAgICAgIGdndGhlbWUgPSB0aGVtZV9taW5pbWFsKCksCiAgICAgICAgICAgICBtYWluID0gIkZhY3RvciBtYXAiCiAgICAgICAgICAgICApCmBgYAoKCllvdSBjYW4gYWxzbyBkcmF3IGEgdGhyZWUgZGltZW5zaW9uYWwgcGxvdCBjb21iaW5pbmcgdGhlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIGFuZCB0aGUgZmFjdG9yaWFsIG1hcCB1c2luZyB0aGUgUiBiYXNlIGZ1bmN0aW9uIHBsb3QoKToKCgpgYGB7cn0KIyBQcmluY2lwYWwgY29tcG9uZW50cyArIHRyZWUKcGxvdChyZXMuaGNwYywgY2hvaWNlID0gIjNELm1hcCIpCmBgYAoKVGhlIGZ1bmN0aW9uIEhDUEMoKSByZXR1cm5zIGEgbGlzdCBjb250YWluaW5nOgoKZGF0YS5jbHVzdDogVGhlIG9yaWdpbmFsIGRhdGEgd2l0aCBhIHN1cHBsZW1lbnRhcnkgY29sdW1uIGNhbGxlZCBjbGFzcyBjb250YWluaW5nIHRoZSBwYXJ0aXRpb24uCmRlc2MudmFyOiBUaGUgdmFyaWFibGVzIGRlc2NyaWJpbmcgY2x1c3RlcnMKZGVzYy5pbmQ6IFRoZSBtb3JlIHR5cGljYWwgaW5kaXZpZHVhbHMgb2YgZWFjaCBjbHVzdGVyCmRlc2MuYXhlczogVGhlIGF4ZXMgZGVzY3JpYmluZyBjbHVzdGVycwpUbyBkaXNwbGF5IHRoZSBvcmlnaW5hbCBkYXRhIHdpdGggY2x1c3RlciBhc3NpZ25tZW50cywgdHlwZSB0aGlzOgoKCmBgYHtyfQpoZWFkKHJlcy5oY3BjJGRhdGEuY2x1c3QsIDEwKQpgYGAKCkluIHRoZSB0YWJsZSBhYm92ZSwgdGhlIGxhc3QgY29sdW1uIGNvbnRhaW5zIHRoZSBjbHVzdGVyIGFzc2lnbm1lbnRzLgoKVG8gZGlzcGxheSBxdWFudGl0YXRpdmUgdmFyaWFibGVzIHRoYXQgZGVzY3JpYmUgdGhlIG1vc3QgZWFjaCBjbHVzdGVyLCB0eXBlIHRoaXM6CgpgYGB7cn0KcmVzLmhjcGMkZGVzYy52YXIkcXVhbnRpCmBgYAoKCkZyb20gdGhlIG91dHB1dCBhYm92ZSwgaXQgY2FuIGJlIHNlZW4gdGhhdDoKCnRoZSB2YXJpYWJsZXMgVXJiYW5Qb3AsIE11cmRlciwgUmFwZSBhbmQgQXNzYXVsdCBhcmUgbW9zdCBzaWduaWZpY2FudGx5IGFzc29jaWF0ZWQgd2l0aCB0aGUgY2x1c3RlciAxLiBGb3IgZXhhbXBsZSwgdGhlIG1lYW4gdmFsdWUgb2YgdGhlIEFzc2F1bHQgdmFyaWFibGUgaW4gY2x1c3RlciAxIGlzIDc4LjUzIHdoaWNoIGlzIGxlc3MgdGhhbiBpdOKAmXMgb3ZlcmFsbCBtZWFuICgxNzAuNzYpIGFjcm9zcyBhbGwgY2x1c3RlcnMuIFRoZXJlZm9yZSwgSXQgY2FuIGJlIGNvbmNsdWRlIHRoYXQgdGhlIGNsdXN0ZXIgMSBpcyBjaGFyYWN0ZXJpemVkIGJ5IGEgbG93IHJhdGUgb2YgQXNzYXVsdCBjb21wYXJlZCB0byBhbGwgY2x1c3RlcnMuCgp0aGUgdmFyaWFibGVzIFVyYmFuUG9wIGFuZCBNdXJkZXIgYXJlIG1vc3Qgc2lnbmlmaWNhbnRseSBhc3NvY2lhdGVkIHdpdGggdGhlIGNsdXN0ZXIgMi4KCuKApmFuZCBzbyBvbiDigKYKCgpgYGB7cn0KcmVzLmhjcGMkZGVzYy5heGVzJHF1YW50aQpgYGAKCgpGaW5hbGx5LCByZXByZXNlbnRhdGl2ZSBpbmRpdmlkdWFscyBvZiBlYWNoIGNsdXN0ZXIgY2FuIGJlIGV4dHJhY3RlZCBhcyBmb2xsb3c6CgoKYGBge3J9CnJlcy5oY3BjJGRlc2MuaW5kJHBhcmEKYGBgCgojIyMjIENhc2Ugb2YgY2F0ZWdvcmljYWwgdmFyaWFibGVzCgpGb3IgY2F0ZWdvcmljYWwgdmFyaWFibGVzLCBjb21wdXRlIENBIG9yIE1DQSBhbmQgdGhlbiBhcHBseSB0aGUgZnVuY3Rpb24gSENQQygpIG9uIHRoZSByZXN1bHRzIGFzIGRlc2NyaWJlZCBhYm92ZS4KCkhlcmUsIHdl4oCZbGwgdXNlIHRoZSB0ZWEgZGF0YSBbaW4gRmFjdG9NaW5lUl0gYXMgZGVtbyBkYXRhIHNldDogUm93cyByZXByZXNlbnQgdGhlIGluZGl2aWR1YWxzIGFuZCBjb2x1bW5zIHJlcHJlc2VudCBjYXRlZ29yaWNhbCB2YXJpYWJsZXMuCgpXZSBzdGFydCwgYnkgcGVyZm9ybWluZyBhbiBNQ0Egb24gdGhlIGluZGl2aWR1YWxzLiBXZSBrZWVwIHRoZSBmaXJzdCAyMCBheGVzIG9mIHRoZSBNQ0Egd2hpY2ggcmV0YWluIDg3JSBvZiB0aGUgaW5mb3JtYXRpb24uCgpgYGB7cn0KIyBMb2FkaW5nIGRhdGEKbGlicmFyeShGYWN0b01pbmVSKQpkYXRhKHRlYSkKIyBQZXJmb3JtaW5nIE1DQQpyZXMubWNhIDwtIE1DQSh0ZWEsIAogICAgICAgICAgICAgICBuY3AgPSAyMCwgICAgICAgICAgICAjIE51bWJlciBvZiBjb21wb25lbnRzIGtlcHQKICAgICAgICAgICAgICAgcXVhbnRpLnN1cCA9IDE5LCAgICAgIyBRdWFudGl0YXRpdmUgc3VwcGxlbWVudGFyeSB2YXJpYWJsZXMKICAgICAgICAgICAgICAgcXVhbGkuc3VwID0gYygyMDozNiksICMgUXVhbGl0YXRpdmUgc3VwcGxlbWVudGFyeSB2YXJpYWJsZXMKICAgICAgICAgICAgICAgZ3JhcGg9RkFMU0UpCmBgYAoKTmV4dCwgd2UgYXBwbHkgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgb24gdGhlIHJlc3VsdHMgb2YgdGhlIE1DQToKCmBgYHtyfQpyZXMuaGNwYyA8LSBIQ1BDIChyZXMubWNhLCBncmFwaCA9IEZBTFNFLCBtYXggPSAzKQpgYGAKCgpgYGB7cn0KIyBEZW5kcm9ncmFtCmZ2aXpfZGVuZChyZXMuaGNwYywgc2hvd19sYWJlbHMgPSBGQUxTRSkKIyBJbmRpdmlkdWFscyBmYWNvciBtYXAKZnZpel9jbHVzdGVyKHJlcy5oY3BjLCBnZW9tID0gInBvaW50IiwgbWFpbiA9ICJGYWN0b3IgbWFwIikKYGBgCgoKQXMgbWVudGlvbmVkIGFib3ZlLCBjbHVzdGVycyBjYW4gYmUgZGVzY3JpYmVkIGJ5IGkpIHZhcmlhYmxlcyBhbmQvb3IgY2F0ZWdvcmllcywgaWkpIHByaW5jaXBhbCBheGVzIGFuZCBpaWkpIGluZGl2aWR1YWxzLiBJbiB0aGUgZXhhbXBsZSBiZWxvdywgd2UgZGlzcGxheSBvbmx5IGEgc3Vic2V0IG9mIHRoZSByZXN1bHRzLgoKRGVzY3JpcHRpb24gYnkgdmFyaWFibGVzIGFuZCBjYXRlZ29yaWVzCgpgYGB7cn0KIyBEZXNjcmlwdGlvbiBieSB2YXJpYWJsZXMKcmVzLmhjcGMkZGVzYy52YXIkdGVzdC5jaGkyCmBgYAoKCmBgYHtyfQojIERlc2NyaXB0aW9uIGJ5IHZhcmlhYmxlIGNhdGVnb3JpZXMKcmVzLmhjcGMkZGVzYy52YXIkY2F0ZWdvcnkKYGBgCgpEZXNjcmlwdGlvbiBieSBwcmluY2lwYWwgY29tcG9uZW50cwoKYGBge3J9CnJlcy5oY3BjJGRlc2MuYXhlcwpgYGAKCgpEZXNjcmlwdGlvbiBieSBpbmRpdmlkdWFscwoKYGBge3J9CnJlcy5oY3BjJGRlc2MuaW5kJHBhcmEKYGBgCgoKClN1bW1hcnkKCldlIGRlc2NyaWJlZCBob3cgdG8gY29tcHV0ZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBvbiBwcmluY2lwYWwgY29tcG9uZW50cyAoSENQQykuIFRoaXMgYXBwcm9hY2ggaXMgdXNlZnVsIGluIHNpdHVhdGlvbnMsIGluY2x1ZGluZzoKCldoZW4geW91IGhhdmUgYSBsYXJnZSBkYXRhIHNldCBjb250YWluaW5nIGNvbnRpbnVvdXMgdmFyaWFibGVzLCBhIHByaW5jaXBhbCBjb21wb25lbnQgYW5hbHlzaXMgY2FuIGJlIHVzZWQgdG8gcmVkdWNlIHRoZSBkaW1lbnNpb24gb2YgdGhlIGRhdGEgYmVmb3JlIHRoZSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBhbmFseXNpcy4KCldoZW4geW91IGhhdmUgYSBkYXRhIHNldCBjb250YWluaW5nIGNhdGVnb3JpY2FsIHZhcmlhYmxlcywgYSAoTXVsdGlwbGUpQ29ycmVzcG9uZGVuY2UgYW5hbHlzaXMgY2FuIGJlIHVzZWQgdG8gdHJhbnNmb3JtIHRoZSBjYXRlZ29yaWNhbCB2YXJpYWJsZXMgaW50byBmZXcgY29udGludW91cyBwcmluY2lwYWwgY29tcG9uZW50cywgd2hpY2ggY2FuIGJlIHVzZWQgYXMgdGhlIGlucHV0IG9mIHRoZSBjbHVzdGVyIGFuYWx5c2lzLgoKV2UgdXNlZCB0aGUgRmFjdG9NaW5lUiBwYWNrYWdlIHRvIGNvbXB1dGUgdGhlIEhDUEMgYW5kIHRoZSBmYWN0b2V4dHJhIFIgcGFja2FnZSBmb3IgZ2dwbG90Mi1iYXNlZCBlbGVnYW50IGRhdGEgdmlzdWFsaXphdGlvbi4=