Preamble: installation of R libraries

# install BiocManager package if not installed yet.
# BiocManager is the package installer for Bioconductor software.
if (!requireNamespace("BiocManager", quietly = TRUE))
    install.packages("BiocManager")

# install packages if not yet installed.
pkgs <- c("SingleCellExperiment",
          "ExperimentHub",
          "edgeR",
          "biomaRt",
          "DropletUtils", 
          "scRNAseq", 
          "scater", 
          "scuttle", 
          "scran",
          "scry",
          "BiocSingular", 
          "scDblFinder",
          "Seurat",
          "PCAtools",
          "glmpca",
          "genefilter",
          "pheatmap",
          "tidyverse",
          "mclust",
          "ggplot2",
          "devtools",
          "SingleR")
notInstalled <- pkgs[!pkgs %in% installed.packages()[,1]]
if(length(notInstalled) > 0){
  BiocManager::install(notInstalled)
}

install harmony from github

library(devtools)
install_github("immunogenomics/harmony",
               dependencies = TRUE,
               force = TRUE)

The Cuomo dataset

We here make use of the publication of Anna Cuomo et al., which we will refer to as the iPSC dataset. The paper that describes this dataset can be found using this link.

In the experiment, the authors harvested pluripotent stem cells (iPSCs) from 125 healthy human donors, and induced them to study the endoderm differentiation process, in which iPSCs differentiate to endoderm cells over the course of approximately three days. As such, the authors cultered the iPSCs cell lines and allowed them to differentiate for three days. During the experiment, cells were harvested at four different time points: day0 (directly at incubation), day1, day2 and day3. Knowing the process of endoderm differentiation, these time points should roughly correspond to different cell types: day0 are (undifferentiated) iPSCs, day1 are mostly mesendoderm cells, day2 are mostly “intermediate” cells and day3 are mostly fully differentiated endoderm cells.

This dataset was generated using the SMART-Seq2 scRNA-seq protocol.

The final goal of the experiment was to characterize population variation in the process of endoderm differentiation.

Download data

For this lab session, we will work with a subset of the data, i.e., the data for the first (alphabetically) 15 patients in the experiment. These are the data you already downloaded for lab session 2 using the Belnet filesender link.

The original data (125 patient) could be downloaded from Zenodo. At the bottom of this web-page, we can download the files raw_counts.csv.zip and cell_metadata_cols.tsv and store these files locally. We do not recommend doing this during the lab session, to avoid overloading the WiFi network.

Import data

First we read in the count matrix:

library(SingleCellExperiment)
sce <- readRDS("/Users/jg/Desktop/sce_15_cuomo.rds")
#sce <- readRDS("/Users/koenvandenberge/Desktop/sce_15_cuomo.rds")

Explore metadata

Exploration of the metadata is essential to get a better idea of what the experiment was about and how it was organized.

colData(sce)[1:5,1:10]
## DataFrame with 5 rows and 10 columns
##              assigned      auxDir cell_filter   cell_name
##             <integer> <character>   <logical> <character>
## 21554_5#104         1    aux_info        TRUE 21554_5#104
## 21554_5#110         1    aux_info        TRUE 21554_5#110
## 21554_5#113         1    aux_info        TRUE 21554_5#113
## 21554_5#117         1    aux_info        TRUE 21554_5#117
## 21554_5#127         1    aux_info        TRUE 21554_5#127
##             compatible_fragment_ratio         day       donor expected_format
##                             <numeric> <character> <character>     <character>
## 21554_5#104                  0.999981        day2        dixh              IU
## 21554_5#110                  0.999964        day2        dixh              IU
## 21554_5#113                  0.999945        day2        dixh              IU
## 21554_5#117                  0.999916        day2        dixh              IU
## 21554_5#127                  0.999863        day2        dixh              IU
##              experiment frag_dist_length
##             <character>        <integer>
## 21554_5#104     expt_21             1001
## 21554_5#110     expt_21             1001
## 21554_5#113     expt_21             1001
## 21554_5#117     expt_21             1001
## 21554_5#127     expt_21             1001
colnames(colData(sce))
##  [1] "assigned"                                   
##  [2] "auxDir"                                     
##  [3] "cell_filter"                                
##  [4] "cell_name"                                  
##  [5] "compatible_fragment_ratio"                  
##  [6] "day"                                        
##  [7] "donor"                                      
##  [8] "expected_format"                            
##  [9] "experiment"                                 
## [10] "frag_dist_length"                           
## [11] "gc_bias_correct"                            
## [12] "is_cell_control"                            
## [13] "is_cell_control_bulk"                       
## [14] "is_cell_control_control"                    
## [15] "library_types"                              
## [16] "libType"                                    
## [17] "log10_total_counts"                         
## [18] "log10_total_counts_endogenous"              
## [19] "log10_total_counts_ERCC"                    
## [20] "log10_total_counts_feature_control"         
## [21] "log10_total_counts_MT"                      
## [22] "log10_total_features"                       
## [23] "log10_total_features_endogenous"            
## [24] "log10_total_features_ERCC"                  
## [25] "log10_total_features_feature_control"       
## [26] "log10_total_features_MT"                    
## [27] "mapping_type"                               
## [28] "mates1"                                     
## [29] "mates2"                                     
## [30] "n_alt_reads"                                
## [31] "n_total_reads"                              
## [32] "num_assigned_fragments"                     
## [33] "num_bias_bins"                              
## [34] "num_bootstraps"                             
## [35] "num_compatible_fragments"                   
## [36] "num_consistent_mappings"                    
## [37] "num_inconsistent_mappings"                  
## [38] "num_libraries"                              
## [39] "num_mapped"                                 
## [40] "num_processed"                              
## [41] "num_targets"                                
## [42] "nvars_used"                                 
## [43] "pct_counts_endogenous"                      
## [44] "pct_counts_ERCC"                            
## [45] "pct_counts_feature_control"                 
## [46] "pct_counts_MT"                              
## [47] "pct_counts_top_100_features"                
## [48] "pct_counts_top_100_features_endogenous"     
## [49] "pct_counts_top_100_features_feature_control"
## [50] "pct_counts_top_200_features"                
## [51] "pct_counts_top_200_features_endogenous"     
## [52] "pct_counts_top_50_features"                 
## [53] "pct_counts_top_50_features_endogenous"      
## [54] "pct_counts_top_50_features_ERCC"            
## [55] "pct_counts_top_50_features_feature_control" 
## [56] "pct_counts_top_500_features"                
## [57] "pct_counts_top_500_features_endogenous"     
## [58] "percent_mapped"                             
## [59] "plate_id"                                   
## [60] "plate_well_id"                              
## [61] "post_prob"                                  
## [62] "public_name"                                
## [63] "read_files"                                 
## [64] "salmon_version"                             
## [65] "samp_type"                                  
## [66] "sample_id"                                  
## [67] "seq_bias_correct"                           
## [68] "size_factor"                                
## [69] "start_time"                                 
## [70] "strand_mapping_bias"                        
## [71] "total_counts"                               
## [72] "total_counts_endogenous"                    
## [73] "total_counts_ERCC"                          
## [74] "total_counts_feature_control"               
## [75] "total_counts_MT"                            
## [76] "total_features"                             
## [77] "total_features_endogenous"                  
## [78] "total_features_ERCC"                        
## [79] "total_features_feature_control"             
## [80] "total_features_MT"                          
## [81] "used_in_expt"                               
## [82] "well_id"                                    
## [83] "well_type"                                  
## [84] "donor_short_id"                             
## [85] "donor_long_id"                              
## [86] "pseudo"                                     
## [87] "PC1_top100hvgs"                             
## [88] "PC1_top200hvgs"                             
## [89] "PC1_top500hvgs"                             
## [90] "PC1_top1000hvgs"                            
## [91] "PC1_top2000hvgs"                            
## [92] "princ_curve"                                
## [93] "princ_curve_scaled01"

As stated in the paper, cells were sampled on 4 time points. Each of these time points is roughly expected to correspond with different cell types (day0 = iPSC, day1 = mesendoderm, day2 = intermediate and day3 = endoderm).

table(colData(sce)$day)
## 
## day0 day1 day2 day3 
##  876  987 1124  890

As stated in the paper, cells were harvested from 125 patients. Here, we are working on a subset with 15 patients. The number of cells harvested per patient (over all time points) ranges from 31 to 637.

length(table(colData(sce)$donor)) # number of donors
## [1] 15
range(table(colData(sce)$donor)) # cells per donor
## [1]  31 637

Below, we look at how many cells are harvest per patent and per time point.

table(colData(sce)$donor,colData(sce)$day)
##       
##        day0 day1 day2 day3
##   aowh   88  100   93   95
##   aoxv   68   58   96   71
##   babz   28    0   41    0
##   bezi   13   11    4    3
##   bima    0    0   44   31
##   bokz  159  200  164  114
##   cicb   42   21   75   26
##   ciwj   40   27   35   39
##   cuhk   41   47   39   27
##   datg  185  147  136  115
##   dixh    0   46   73   84
##   eesb   66  106  103  195
##   eipl   99  189  198   57
##   eiwy   25   18   10   25
##   eoxi   22   17   13    8

We see that for many patients the data is complete, i.e. cells were sampled on all time points.

Practically, the cells were prepared in 28 batches. Since we here only look at a subset of the data, we see that only 14 of these batches are represented.

length(table(colData(sce)$experiment))
## [1] 14
table(colData(sce)$experiment, colData(sce)$day)
##          
##           day0 day1 day2 day3
##   expt_21    0   46   73   84
##   expt_22   22   17   13    8
##   expt_24   28    0   41    0
##   expt_29   73   91   93   86
##   expt_30   15    9    0    9
##   expt_31   83   68  114   53
##   expt_33   70   49   53   64
##   expt_34  274  298  247  165
##   expt_36   25   18   10   25
##   expt_39   13   11    4    3
##   expt_41   99  189  198   57
##   expt_42    0    0   44   31
##   expt_43  134  164  199  266
##   expt_45   40   27   35   39

Obtaining and including rowData

The rowData slot of a SingleCellExperiment object allows for storing information on the features, i.e. the genes, in a dataset. In our object, the rowData slot currently contains the following:

head(rowData(sce))
## DataFrame with 6 rows and 1 column
##                       V1
##              <character>
## 1 ENSG00000000003_TSPAN6
## 2   ENSG00000000419_DPM1
## 3  ENSG00000000457_SCYL3
## 4 ENSG00000000460_C1or..
## 5  ENSG00000001036_FUCA2
## 6   ENSG00000001084_GCLC

To improve our gene-level information, we may:

  1. Split V1 into two columns, one with the ENSEMBL ID and the other with the gene symbol.

  2. Display which chromosome the gene is located

Many more options are possible, but are not necessary for us right now.

rowData(sce) <- data.frame(Ensembl = gsub("_.*", "", rowData(sce)$V1),
                           Symbol = gsub("^[^_]*_", "", rowData(sce)$V1))
head(rowData(sce))
## DataFrame with 6 rows and 2 columns
##           Ensembl      Symbol
##       <character> <character>
## 1 ENSG00000000003      TSPAN6
## 2 ENSG00000000419        DPM1
## 3 ENSG00000000457       SCYL3
## 4 ENSG00000000460    C1orf112
## 5 ENSG00000001036       FUCA2
## 6 ENSG00000001084        GCLC
# currently issues with ensembl server -> do not evaluate this chunk
library("biomaRt")
ensembl75 <- useEnsembl(biomart = 'genes', 
                        dataset = 'hsapiens_gene_ensembl',
                        version = 75)

GeneInfo <- getBM(attributes = c("ensembl_gene_id", # To match with rownames SCE
                                 "chromosome_name"), # Info on chromose
                  mart = ensembl75)
GeneInfo <- GeneInfo[match(rowData(sce)$Ensembl, GeneInfo$ensembl_gene_id),]

rowData(sce) <- cbind(rowData(sce), GeneInfo)
head(rowData(sce))
all(rowData(sce)$Ensembl == rowData(sce)$ensembl_gene_id) 
# identical, as desired, so we could optionally remove one of the two

Filtering non-informative genes

Let us first try the very simple and very lenient filtering criterion that we adopted for the Macosko dataset.

keep <- rowSums(assays(sce)$counts > 0) > 10
table(keep)
## keep
##  TRUE 
## 11231

We see that this filtering strategy does not remove any genes for this dataset. In general, datasets from plate-based scRNA-seq dataset have a far higher sequencing depth than data from droplet-based protocols. As requiring a minimum expression of 1 count in at least 10 cells is a very lenient criterion if we consider that we are working 36.000 cells, we should consider adopting a more stringent filtering criterium. Below we do so using the filterByExpr from edgeR:

library(edgeR)

table(colData(sce)$day)
## 
## day0 day1 day2 day3 
##  876  987 1124  890
keep2 <- edgeR::filterByExpr(y=sce,
                             group = colData(sce)$day,
                             min.count = 5,
                             min.prop = 0.4)
table(keep2)
## keep2
## FALSE  TRUE 
##   857 10374
sce <- sce[keep2,]

Quality control

Calculate QC variables

library(scater)
## Loading required package: scuttle
## Loading required package: ggplot2
## 
## Attaching package: 'scater'
## The following object is masked from 'package:limma':
## 
##     plotMDS
# check ERCC spike-in transcripts
sum(grepl("^ERCC-", rowData(sce)$Symbol)) # no spike-in transcripts available
## [1] 0
is.mito <- grepl("^MT", rowData(sce)$chromosome_name)
sum(is.mito) # 13 mitochondrial genes
## [1] 0
df <- perCellQCMetrics(sce, subsets=list(Mito=is.mito))
head(df)
## DataFrame with 6 rows and 6 columns
##                   sum  detected subsets_Mito_sum subsets_Mito_detected
##             <numeric> <numeric>        <numeric>             <numeric>
## 21554_5#104  138676.3      5305                0                     0
## 21554_5#110  685123.5      5927                0                     0
## 21554_5#113 1671911.4      5613                0                     0
## 21554_5#117   90419.4      6066                0                     0
## 21554_5#127   59463.2      6549                0                     0
## 21554_5#128  416482.7      7870                0                     0
##             subsets_Mito_percent     total
##                        <numeric> <numeric>
## 21554_5#104                    0  138676.3
## 21554_5#110                    0  685123.5
## 21554_5#113                    0 1671911.4
## 21554_5#117                    0   90419.4
## 21554_5#127                    0   59463.2
## 21554_5#128                    0  416482.7
## add the QC variables to sce object
colData(sce) <- cbind(colData(sce), df)

Exploratory data analysis

In the figure below, we see that several cells have a very low number of expressed genes, and where most of the molecules are derived from mitochondrial genes. This indicates likely damaged cells, presumably because of loss of cytoplasmic RNA from perforated cells, so we should remove these for the downstream analysis.

# Number of genes vs library size
plotColData(sce, x = "sum", y="detected", colour_by="day") 

# Mitochondrial genes
plotColData(sce, x = "detected", y="subsets_Mito_percent", colour_by="day")

QC using adaptive thresholds

Below, we remove cells that are outlying with respect to

  1. A low sequencing depth (number of UMIs);
  2. A low number of genes detected;
  3. A high percentage of reads from mitochondrial genes.

We remove a total of \(301\) cells, mainly due to low sequencing depth and low number of genes detected.

lowLib <- isOutlier(df$sum, type="lower", log=TRUE)
lowFeatures <- isOutlier(df$detected, type="lower", log=TRUE)
highMito <- isOutlier(df$subsets_Mito_percent, type="higher")

table(lowLib)
## lowLib
## FALSE  TRUE 
##  3676   201
table(lowFeatures)
## lowFeatures
## FALSE  TRUE 
##  3813    64
table(highMito)
## highMito
## FALSE 
##  3877
discardCells <- (lowLib | lowFeatures | highMito)
table(discardCells)
## discardCells
## FALSE  TRUE 
##  3633   244
colData(sce)$discardCells <- discardCells

# visualize cells to be removed
plotColData(sce, x = "detected", y="subsets_Mito_percent", colour_by = "discardCells")

plotColData(sce, x = "sum", y="detected", colour_by="discardCells")

# visualize cells to be removed
plotColData(sce, x = "detected", y="subsets_Mito_percent", colour_by = "donor")

plotColData(sce, x = "sum", y="detected", colour_by="donor")

# visualize cells to be removed
plotColData(sce, x = "detected", y="subsets_Mito_percent", colour_by = "experiment")

plotColData(sce, x = "sum", y="detected", colour_by="experiment")

table(sce$donor, sce$discardCells)
##       
##        FALSE TRUE
##   aowh   367    9
##   aoxv   284    9
##   babz    44   25
##   bezi    30    1
##   bima    73    2
##   bokz   625   12
##   cicb   161    3
##   ciwj   135    6
##   cuhk   147    7
##   datg   569   14
##   dixh    90  113
##   eesb   452   18
##   eipl   537    6
##   eiwy    77    1
##   eoxi    42   18
table(sce$donor, sce$discardCells)/rowSums(table(sce$donor, sce$discardCells))
##       
##             FALSE       TRUE
##   aowh 0.97606383 0.02393617
##   aoxv 0.96928328 0.03071672
##   babz 0.63768116 0.36231884
##   bezi 0.96774194 0.03225806
##   bima 0.97333333 0.02666667
##   bokz 0.98116170 0.01883830
##   cicb 0.98170732 0.01829268
##   ciwj 0.95744681 0.04255319
##   cuhk 0.95454545 0.04545455
##   datg 0.97598628 0.02401372
##   dixh 0.44334975 0.55665025
##   eesb 0.96170213 0.03829787
##   eipl 0.98895028 0.01104972
##   eiwy 0.98717949 0.01282051
##   eoxi 0.70000000 0.30000000
#fractions of removed cells per donor

Most removed cells (fraction) are from patients dixh and babz.

table(sce$experiment, sce$discardCells)
##          
##           FALSE TRUE
##   expt_21    90  113
##   expt_22    42   18
##   expt_24    44   25
##   expt_29   336    7
##   expt_30    31    2
##   expt_31   308   10
##   expt_33   227    9
##   expt_34   967   17
##   expt_36    77    1
##   expt_39    30    1
##   expt_41   537    6
##   expt_42    73    2
##   expt_43   736   27
##   expt_45   135    6
table(sce$experiment, sce$donor)
##          
##           aowh aoxv babz bezi bima bokz cicb ciwj cuhk datg dixh eesb eipl eiwy
##   expt_21    0    0    0    0    0    0    0    0    0    0  203    0    0    0
##   expt_22    0    0    0    0    0    0    0    0    0    0    0    0    0    0
##   expt_24    0    0   69    0    0    0    0    0    0    0    0    0    0    0
##   expt_29  343    0    0    0    0    0    0    0    0    0    0    0    0    0
##   expt_30   33    0    0    0    0    0    0    0    0    0    0    0    0    0
##   expt_31    0    0    0    0    0    0  164    0  154    0    0    0    0    0
##   expt_33    0    0    0    0    0    0    0    0    0  236    0    0    0    0
##   expt_34    0    0    0    0    0  637    0    0    0  347    0    0    0    0
##   expt_36    0    0    0    0    0    0    0    0    0    0    0    0    0   78
##   expt_39    0    0    0   31    0    0    0    0    0    0    0    0    0    0
##   expt_41    0    0    0    0    0    0    0    0    0    0    0    0  543    0
##   expt_42    0    0    0    0   75    0    0    0    0    0    0    0    0    0
##   expt_43    0  293    0    0    0    0    0    0    0    0    0  470    0    0
##   expt_45    0    0    0    0    0    0    0  141    0    0    0    0    0    0
##          
##           eoxi
##   expt_21    0
##   expt_22   60
##   expt_24    0
##   expt_29    0
##   expt_30    0
##   expt_31    0
##   expt_33    0
##   expt_34    0
##   expt_36    0
##   expt_39    0
##   expt_41    0
##   expt_42    0
##   expt_43    0
##   expt_45    0

Most low library sizes seem to come from patient dixh; for patient babz the effect is less pronounced.

plotColData(sce[,sce$donor=="dixh"], x = "sum", y="detected")

plotColData(sce[,sce$donor=="babz"], x = "sum", y="detected")

As such, we are mainly removing cells from specific patients and the respective batches in which they were sequenced. However, we want to be careful; we only want to remove technical artefacts, while retaining as much of the biology as possible. In our exploratory figure, we see that the cells we are removing based on the number of genes detected, are quite far apart from the bulk of the data cloud; as such, these cells may be considered suspicious. For the criterion of library size, we see that the cells removed there are still strongly connected to the data cloud. As such, we may want to relax the filtering criterion there a little bit. When we think of how the adaptive threshold strategy works, we may want to remove cells that are 4MADs away from the center, rather than the default 3 MADs.

# previously
lowLib <- isOutlier(df$sum, type="lower", log=TRUE)
table(lowLib)
## lowLib
## FALSE  TRUE 
##  3676   201
# after seeing appropriate exploratory figure
lowLib <- isOutlier(df$sum, nmads=4, type="lower", log=TRUE)
table(lowLib)
## lowLib
## FALSE  TRUE 
##  3783    94
discardCells <- (lowLib | lowFeatures | highMito)
table(discardCells)
## discardCells
## FALSE  TRUE 
##  3731   146
colData(sce)$discardCells <- discardCells

Note that these steps are not exact; different analysts will arrive to different filtering criteria for many of the steps. The key ideas are that we let appropriate exploratory figures guide us to make reasonable choices; i.e., we look at the data rather than blindly following a standardized pipeline that may work well in many cases, but maybe not our particular dataset.

# remove cells identified using adaptive thresholds
sce <- sce[, !colData(sce)$discardCells]

Normalization

For normalization, the size factors \(s_i\) computed here are simply scaled library sizes:

\[ N_i = \sum_g Y_{gi} \] \[ s_i = N_i / \bar{N}_i \]

sce <- logNormCounts(sce)

# note we also returned log counts: see the additional logcounts assay.
sce
## class: SingleCellExperiment 
## dim: 10374 3731 
## metadata(0):
## assays(2): counts logcounts
## rownames: NULL
## rowData names(2): Ensembl Symbol
## colnames(3731): 21554_5#128 21554_5#142 ... 24947_6#91 24947_6#98
## colData names(101): assigned auxDir ... discardCells sizeFactor
## reducedDimNames(0):
## mainExpName: NULL
## altExpNames(0):
# you can extract size factors using
sf <- librarySizeFactors(sce)
mean(sf) # equal to 1 due to scaling.
## [1] 1
plot(x= log(colSums(assays(sce)$counts)), 
     y=sf)


— end lab session 1 —


Feature selection

Highly variable genes

library(scran)
rownames(sce) <- rowData(sce)$Ensembl
dec <- modelGeneVar(sce)
head(dec)
## DataFrame with 6 rows and 6 columns
##                      mean     total      tech        bio   p.value       FDR
##                 <numeric> <numeric> <numeric>  <numeric> <numeric> <numeric>
## ENSG00000000003  5.452309  0.863745   1.28581 -0.4220675  0.773732  0.882711
## ENSG00000000419  5.832487  1.028264   1.07766 -0.0493993  0.541773  0.882402
## ENSG00000000457  0.760778  1.175215   1.72646 -0.5512453  0.767517  0.882402
## ENSG00000000460  3.112458  1.545048   2.62346 -1.0784118  0.826574  0.888076
## ENSG00000001036  3.570987  2.180611   2.44778 -0.2671676  0.598622  0.882402
## ENSG00000001084  1.698901  2.386060   2.55583 -0.1697705  0.560411  0.882402
fit <- metadata(dec)
plot(fit$mean, fit$var, 
     xlab="Mean of log-expression",
    ylab="Variance of log-expression")
curve(fit$trend(x), col="dodgerblue", add=TRUE, lwd=2)

# get top 1000 highly variable genes
hvg <- getTopHVGs(dec, 
                  n=1000)
head(hvg)
## [1] "ENSG00000147869" "ENSG00000158815" "ENSG00000095596" "ENSG00000104371"
## [5] "ENSG00000185155" "ENSG00000120937"
# plot these 
plot(fit$mean, fit$var, 
     col = c("orange", "darkseagreen3")[(names(fit$mean) %in% hvg)+1],
     xlab="Mean of log-expression",
    ylab="Variance of log-expression")
curve(fit$trend(x), col="dodgerblue", add=TRUE, lwd=2)
legend("topleft", 
       legend = c("Selected", "Not selected"), 
       col = c("darkseagreen3", "orange"),
       pch = 16,
       bty='n')

Dimensionality reduction

Linear dimensionality reduction: PCA with feature selection

set.seed(1234)
sce <- runPCA(sce, 
              ncomponents=30, 
              subset_row=hvg)
plotPCA(sce, 
        colour_by = "day")

PCA has been performed. The PCA information has been automatically stored in the reducedDim slot of the SingleCellExperiment object.

reducedDimNames(sce)
## [1] "PCA"
head(reducedDim(sce,
           type="PCA"))
##                    PC1       PC2        PC3      PC4       PC5       PC6
## 21554_5#128 -27.364852  9.594060  11.373564 30.76916 15.394118 -27.80931
## 21554_5#142 -26.726070  8.421937   8.355765 32.85938 -6.317488 -23.51960
## 21554_5#174 -16.417046 16.397747   9.339535 29.60662 20.174990 -23.62026
## 21554_5#176  -4.164451 15.322549  23.551281 26.57112 31.728127 -19.74506
## 21554_5#181 -22.143156  7.574105   9.966680 36.27930 12.204297 -26.26973
## 21554_5#183 -15.698590 15.525954 -13.216317 33.72004 -2.447697 -30.98004
##                    PC7        PC8         PC9       PC10      PC11       PC12
## 21554_5#128 -9.9341013  1.1274408   1.9843292   2.089876 -6.675600 -2.5301641
## 21554_5#142  8.7769917  9.3930201 -15.5791940 -11.423582 -1.627703 -4.0035113
## 21554_5#174 10.2249020 -1.3204708  -6.4121141   1.720833 17.826228  9.1196366
## 21554_5#176 -0.6745669 -0.9984625  -9.3857501  -4.181246 22.207032  4.5883345
## 21554_5#181 -0.9321336 -0.2769346   4.6500493   2.622540 -6.233380  0.2515426
## 21554_5#183  7.3013430  6.9185899  -0.2620361  -4.045207 -3.049075 -2.0505240
##                   PC13         PC14      PC15       PC16      PC17       PC18
## 21554_5#128 -3.4087788   0.02235213  1.420843  0.7293154  1.641542  0.6151673
## 21554_5#142 -9.8428164  -8.27401019 -1.105121 -3.1555296 -3.133926 -1.3455544
## 21554_5#174 -5.6386833  -2.31652358  4.070325  1.2707437  5.098201  0.3038039
## 21554_5#176  0.2916532 -14.56508569 -6.339897 -2.6535029  5.029821 -0.7144418
## 21554_5#181 -4.9837082   8.00451503  4.048105  9.2870735  4.160989  1.2141390
## 21554_5#183 -2.9067374   1.20335452  5.120246  3.1371635  6.098355 -2.2775478
##                   PC19      PC20       PC21      PC22       PC23       PC24
## 21554_5#128  5.2011841 -6.907664 -6.2647843  3.606747 -1.7431652 -1.5744543
## 21554_5#142 -0.3342526  9.669928 -0.8871485 -4.424970 11.8442676  1.7455513
## 21554_5#174  0.3691554  2.859107  3.0277004 -2.735873  5.1592166 -5.9721144
## 21554_5#176 -5.3943048 -2.840958  2.5375172  1.622524  4.6667312 -5.6725527
## 21554_5#181  3.2186974 -3.446394 -0.1923339 -2.137403 -0.7645622 -0.3988127
## 21554_5#183  2.0889075 -2.666797  0.1332723  1.779886  3.6862353  2.0159151
##                  PC25       PC26       PC27      PC28      PC29       PC30
## 21554_5#128 -0.102636  0.7537463 -3.5420691 3.7249324  5.837253 -1.4452956
## 21554_5#142 -3.035680  1.2788784  4.0515276 1.7271103 -4.905858 -3.7472445
## 21554_5#174 -6.154168 -6.3600204 -0.2767746 4.4168734  7.188644 -3.2498909
## 21554_5#176 -3.992011 -4.7046345 -0.4531632 2.8712394  2.112673 -9.8468144
## 21554_5#181  2.443517  0.9264037 -0.4445118 4.1346673 -1.364736  2.1226600
## 21554_5#183 -2.209305 -3.0687859  0.1412868 0.4865902  2.936611  0.5889153

The plotPCA function of the scater package now allows us to visualize the cells in PCA space, based on the PCA information stored in our object:

plotPCA(sce, 
        colour_by = "day")

We see that for this dataset, PCA is able to distinguish between the different developmental stages quite well.

A generalization of PCA for exponential family distributions.

library(glmpca)
set.seed(211103)
poipca <- glmpca(Y = assays(sce)$counts[hvg,],
                 L = 2, 
                 fam = "poi",
                 minibatch = "stochastic")
reducedDim(sce, "PoiPCA") <- poipca$factors
plotReducedDim(sce, 
               dimred="PoiPCA",
               colour_by = "day")

Using glmpca, we observe a similar reduced dimension plot as for the classical PCA approach, with reasonable separation between cells of different developmental stages.

Non-linear dimensionality reduction: T-SNE

set.seed(8778)
sce <- runTSNE(sce, 
               dimred = 'PCA',
               external_neighbors=TRUE)
plotTSNE(sce,
         colour_by = "day")

In this 2D t-SNE space, it is clear that cells of different developmental stages cluster separately. However, there appears to be some heterogeneity. We observe multiple clusters of cells sampled at the same time point. In addition, while still clustering separately, some clusters of cells of different time points are still very close together in 2D space.

We will explore this phenomenon in more detail later.

Non-linear dimensionality reduction: UMAP

set.seed(65187)
sce <- runUMAP(sce, 
               dimred = "PCA",
               min_dist = 0.4,
               n_dimred = 12,
               external_neighbors = TRUE)

plotUMAP(sce,
         colour_by = "day")

We observe a very similar pattern as for the t-SNE above in this UMAP; cells of different developmental stages cluster separately, however, there seems to be an additional level of heterogeneity in the data.


— end lab session 2 —


Batch correction

Observed patient/experiment effect

In this experiment, our main interest is to study the endoderm differentiation process, i.e. the 4-day differentiation process of induced pluripotent stem cells (iPSCs) at day0, via mesendoderm cells (day1) and another intermediate stage (day2) to endoderm cells (day3).

However, we will need to account for the fact that the cells have been sampled from 15 different subject, thus introducing additional biological heterogeneity. There are two variables in the colData of our SingleCellExperiment object that are useful for exploring this:

table(sce$donor,sce$experiment)
##       
##        expt_21 expt_22 expt_24 expt_29 expt_30 expt_31 expt_33 expt_34 expt_36
##   aowh       0       0       0     342      32       0       0       0       0
##   aoxv       0       0       0       0       0       0       0       0       0
##   babz       0       0      54       0       0       0       0       0       0
##   bezi       0       0       0       0       0       0       0       0       0
##   bima       0       0       0       0       0       0       0       0       0
##   bokz       0       0       0       0       0       0       0     635       0
##   cicb       0       0       0       0       0     164       0       0       0
##   ciwj       0       0       0       0       0       0       0       0       0
##   cuhk       0       0       0       0       0     152       0       0       0
##   datg       0       0       0       0       0       0     235     346       0
##   dixh     109       0       0       0       0       0       0       0       0
##   eesb       0       0       0       0       0       0       0       0       0
##   eipl       0       0       0       0       0       0       0       0       0
##   eiwy       0       0       0       0       0       0       0       0      78
##   eoxi       0      47       0       0       0       0       0       0       0
##       
##        expt_39 expt_41 expt_42 expt_43 expt_45
##   aowh       0       0       0       0       0
##   aoxv       0       0       0     292       0
##   babz       0       0       0       0       0
##   bezi      30       0       0       0       0
##   bima       0       0      73       0       0
##   bokz       0       0       0       0       0
##   cicb       0       0       0       0       0
##   ciwj       0       0       0       0     137
##   cuhk       0       0       0       0       0
##   datg       0       0       0       0       0
##   dixh       0       0       0       0       0
##   eesb       0       0       0     466       0
##   eipl       0     539       0       0       0
##   eiwy       0       0       0       0       0
##   eoxi       0       0       0       0       0

We have cells from 15 different patients and 14 different “experiments” (= sequencing batches).

We now will assess if this additional source of heterogeneity is also picked up in the reduced dimension plot.

# time effect in PCA space, all time points
plotPCA(sce,
        colour_by = "day")

# donor (nuisance) effect in PCA space, all time points
plotPCA(sce,
        colour_by = "donor")

# experiment (nuisance) effect in PCA space, all time points
plotPCA(sce,
        colour_by = "experiment")

We see that within a certain time point, cells of the same patient/experiment seem to cluster together at least to some extent. This effect becomes clearer when we visualize the data of the different time points separately.

# donor effect in PCA space, per time point
plotPCA(sce[,sce$day=="day0"], 
        colour_by = "donor")

plotPCA(sce[,sce$day=="day1"], 
        colour_by = "donor")

plotPCA(sce[,sce$day=="day2"], 
        colour_by = "donor")

plotPCA(sce[,sce$day=="day3"], 
        colour_by = "donor")

Analogously, we may inspect the effect of patient and experiment in the UMAP visualization we created earlier.

# time effect
plotUMAP(sce,
         colour_by = "day")

# nuisance effects in UMAP space, all time points
plotUMAP(sce,
         colour_by = "donor")

plotUMAP(sce,
         colour_by = "experiment")

As expected, we see that the additional heterogeneity observed in the clusters colored based on the time points can be explained by the patient effects.

In this experiment, the primary interest are the changes in gene expression across the four days, reflecting differentiation from induced pluripotent stem cells to endoderm cells. In contrast, the between-patient effects are not of interest here. Using batch correction, we will aim to “correct” for the donor effects, while hopefully retaining the main biological variation of interest!

We will explore two popular strategies for batch correction for scRNA-Seq data: Seurat CCA and Harmony.

Seurat CCA batch correction

We will first integrate the data across the different donors using Seurat. This procedure is implemented to integrate datasets/batches in a pairwise fashion. In the case of multiple batches/datasets, it integrates them in a bottom-up strategy, starting with integrating pairwise samples first. Because of this, below, we will introduce the methodology for two batches/datasets, but note that an analogous procedure is applied in the case of multiple batches/datasets.

The Seurat method will first perform feature selection to identify features that are informative in all datasets. Using these features, it will perform a canonical correlation analysis; a dimensionality reduction technique that focusses on shared variation between datasets/batches. The CCA dimensions may be viewed as gene modules that are present in each dataset. Within this shared space, it identifies anchor cells (one for each donor, in our case). These anchor cells may be considered as cells sharing the same biological state, and systematic differences between them correspond to batch/dataset-specific effects. A correction on the original gene expression matrix is then applied by considering systematic differences across all anchor cells identified for each pair of batches/datasets.

library(Seurat)
seurat_obj <- as.Seurat(sce)
seurat_obj
## An object of class Seurat 
## 10374 features across 3731 samples within 1 assay 
## Active assay: originalexp (10374 features, 0 variable features)
##  4 dimensional reductions calculated: PCA, PoiPCA, TSNE, UMAP

In the code chunk below, I remove cells for patients that have less or equal than 30 cells. If we do not do this, we will get issues downstream with the Seurat functions FindIntegrationAnchors and IntegrateData, which break down when the number of cells per batch is small. This is a known issue

and the package maintainers suggest to either remove or manually merge small batches together. We will here simply remove the cells of patient “bezi”.

table(seurat_obj$donor)
## 
## aowh aoxv babz bezi bima bokz cicb ciwj cuhk datg dixh eesb eipl eiwy eoxi 
##  374  292   54   30   73  635  164  137  152  581  109  466  539   78   47
table(seurat_obj$donor)[table(seurat_obj$donor) <= 30]
## bezi 
##   30
seurat_obj <- seurat_obj[,-which(seurat_obj$donor == names(table(seurat_obj$donor)[table(seurat_obj$donor) <= 30]))]

After this, the SplitObject object function is used to generate a list of Seurat objects, where each list elements hold the data of 1 batch (patient):

seurat_obj.list <- SplitObject(seurat_obj, split.by = "donor")
nlevels(as.factor(sce$donor)) # originally 15 patients
## [1] 15
length(seurat_obj.list) # 14 patients left
## [1] 14

Next, Seurat will perform the following steps for batch correction:

  • NormalizeData: by default, takes the count assay of the Seurat object and performs a log-transformation, resulting in an additional log-transformed assay. This is performed for each batch separately.

  • FindVariableFeatures: Feature selection, using the variance-stabilizing transformation (VST) from Seurat, which amounts to calculating Pearson residuals from a regularized negative binomial regression model, with sequencing depth as a covariate. This is performed for each batch separately.

  • SelectIntegrationFeatures: Choose the features to use when integrating multiple datasets or batches. This function ranks features by the number of batches they are deemed variable in, breaking ties by the median variable feature rank across datasets. It returns the top scoring features by this ranking, which are then used in the steps below.

  • FindIntegrationAnchors: For each pair of datasets we want to integrate, we identify anchor cells, one from each dataset, that are assumed to share a similar biological state. Anchor cells are identified as mutual nearest neighbors in the shared canonical correlation analysis space. Anchor cells are also scored and weighted according to their quality.

  • IntegrateData: Anchor cells are used to calculate a ‘corrected’ data matrix, removing systematic differences between anchor cells. This creates an integrated assay in the Seurat object containing this corrected data matrix, which may then be used for downstream visualization and analysis as such.

# Normalize and identify variable features for each dataset (patient) independently
seurat_obj.list <- lapply(X = seurat_obj.list, FUN = function(x) {
    x <- NormalizeData(x,verbose = FALSE)
    x <- FindVariableFeatures(x, 
                              selection.method = "vst", 
                              nfeatures = 1000,
                              verbose = FALSE)
})

# Select features that are repeatedly variable across datasets for integration
features <- SelectIntegrationFeatures(object.list = seurat_obj.list)

# Indentify pairs of cells with similar biological state
anchors <- FindIntegrationAnchors(object.list = seurat_obj.list, 
                                  anchor.features = features,
                                  verbose = FALSE)

# This command creates an 'integrated' data assay. We have set the `k.weight` 
# argument, which specifies the Number of neighbors to consider when weighting 
# anchors, to 30 (default is 100). This was necessary to avoid errors, since we
# have many batches with less than 100 cells.
data.combined <- IntegrateData(anchorset = anchors,
                               k.weight = 30,
                               verbose=FALSE)

data.combined
## An object of class Seurat 
## 12374 features across 3701 samples within 2 assays 
## Active assay: integrated (2000 features, 2000 variable features)
##  1 other assay present: originalexp

Now, we have a new Seurat object, which again is a single object (not a list) storing the expression values of all cells after batch correction. Note that the original expression values are still present in the originalexp assay of the object.

Finally, we may use Seurat functions for performing dimension reduction and visualization of the batch corrected data.

# Run the standard Seurat workflow for visualization and clustering

# Step 1: Scales and centers features in the dataset, prior step to PCA
data.combined <- ScaleData(object = data.combined, 
                           verbose = FALSE)

# Step 2: Perform PCA to 30 dimensions
data.combined <- RunPCA(object = data.combined, 
                        npcs = 30,
                        reduction.name = "PCA_SeuBatch",
                        verbose = FALSE)

# Step 3: Perform UMAP on the first 12 principal components
data.combined <- RunUMAP(object = data.combined, 
                         reduction = "PCA_SeuBatch",
                         reduction.name = "UMAP_SeuBatch",
                         dims = 1:12,
                         verbose = FALSE)
## Warning: The default method for RunUMAP has changed from calling Python UMAP via reticulate to the R-native UWOT using the cosine metric
## To use Python UMAP via reticulate, set umap.method to 'umap-learn' and metric to 'correlation'
## This message will be shown once per session
# UMAP visualization
p1 <- DimPlot(object = data.combined, 
              reduction = "UMAP_SeuBatch", 
              group.by = "day")

p2 <- DimPlot(object = data.combined, 
              reduction = "UMAP_SeuBatch", 
              group.by = "donor")
p1 + p2

Alternatively, we can transform the Seurat object back to a SingleCellExperiment object and generate the visualizations using the Bioconductor functions that we used previously:

# Convert Seurat object to SingleCellExperiment object
sce_intSeurat <- as.SingleCellExperiment(data.combined)

# UMAP without Seurat batch correction
p1 <- plotUMAP(sce,
               colour_by = "day") + ggtitle("Day - no batch")
p2 <- plotUMAP(sce,
               colour_by = "donor") + ggtitle("Donor - no batch")

# UMAP with Seurat batch correction
sce_intSeurat <- runUMAP(sce_intSeurat, 
                         dimred = 'PCA_SEUBATCH',
                         min_dist = 0.4,
                         n_dimred = 12,
                         external_neighbors = TRUE)

p3 <- plotUMAP(sce_intSeurat,
               colour_by = "day") + ggtitle("Day - with batch")
p4 <- plotUMAP(sce_intSeurat,
               colour_by = "donor") + ggtitle("Donor - with batch")

p1 + p3

p2 + p4

The batch correction seems to have worked very well. Both with and without batch correction, we observe that cells of the same time point cluster together. But when no batch correction is performed, there seems to be an additional level of variability in the data.

When we color the cells based on the donor variable, we see that without batch correction cells of the same donor cluster together. After batch correction, such donor effects seem to be no longer present.

Also note that while batch correction remove the between-donor variability, the between-day variability that is of interest is still preserved. As such, based on our visualizations, it looks like the batch correction did not overcorrect and succeeded in removing only the unwanted variation in the data.

Harmony batch correction

Harmony implements a complex data integration strategy, where cells are first clustered using a ‘high-diversity clustering’, favoring clusters consisting of multiple batches/datasets, and then batch effects are corrected within each cluster using a linear correction term. It iterates across these steps until no change is clustering is observed.

Performing batch correction with harmony is very simple; we only need a single function call and can directly work with our SingleCellExperiment object.

The function RunHarmony takes the following inputs:

  • object: name of the SingleCellExperiment object

  • group.by.vars: the names of the variables for which we want to perform batch correction. Conveniently, this can be multiple variables, so we can correct both for donor and experiment effects (since the correspondence between the two was not perfect)

  • reduction: Name of the previously computed reduced dimension space on which batch correction will be performed (not on raw data to improve signal-to-noise ratio). Typically PCA is used

  • reduction.save: name to store the batch corrected dimenion reduced space

  • verbose: print progress or not.

library(harmony)
## Loading required package: Rcpp
set.seed(684864)
sce <- harmony::RunHarmony(object = sce, 
                           group.by.vars    = c("donor", "experiment"),
                           reduction = "PCA",
                           reduction.save = "HARMONY_donor_experiment",
                           verbose = FALSE)

The output is an additional element in the reduced dimension space:

reducedDim(sce, type="PCA")[1:5,1:2]
##                    PC1       PC2
## 21554_5#128 -27.364852  9.594060
## 21554_5#142 -26.726070  8.421937
## 21554_5#174 -16.417046 16.397747
## 21554_5#176  -4.164451 15.322549
## 21554_5#181 -22.143156  7.574105
reducedDim(sce, type="HARMONY_donor_experiment")[1:5,1:2]
##             HARMONY_donor_experiment_1 HARMONY_donor_experiment_2
## 21554_5#128                 -25.018798                   9.814387
## 21554_5#142                 -24.132245                   5.674046
## 21554_5#174                 -15.195094                  15.285123
## 21554_5#176                   8.976033                   6.388050
## 21554_5#181                 -19.884244                   7.579687

for which the values differ as compared to the original PCA coordinates. This is a consequence of the batch correction.

plotReducedDim(object = sce,
               dimred = "PCA",
               colour_by = "day")

plotReducedDim(object = sce,
               dimred = "HARMONY_donor_experiment",
               colour_by = "day")

When coloring on day, both plots look very similar.

plotReducedDim(object = sce,
               dimred = "PCA",
               colour_by = "donor")

plotReducedDim(object = sce,
               dimred = "HARMONY_donor_experiment",
               colour_by = "donor")

This figure is too cluttered to see the donor effects. Below, we therefore generate a separate figure for each time point.

# without bacth correction
p1 <- plotReducedDim(object = sce,
                     dimred = "PCA",
                     colour_by = "donor")

p1 + facet_wrap(~sce$day, ncol=1)

Especially for time points day0 and day1, we observe clear donor effects.

# harmony batch correction
p2 <- plotReducedDim(object = sce,
                     dimred = "HARMONY_donor_experiment",
                     colour_by = "donor")

p2 + facet_wrap(~sce$day, ncol=1)

After batch correction with harmony, the donor effects are largely removed.

When using UMAP visualization, the discrepancy between the uncorrected and batch corrected data becomes even clearer:

# make UMAP space based on batch-corrected PCA data
sce <- runUMAP(sce, 
               dimred = 'HARMONY_donor_experiment',
               n_dimred = 12,
               min_dist = 0.4,
               external_neighbors=TRUE,
               name = "UMAP_HARMONY_donor_experiment")
# No batch versus batch corrected, color by day
p1 <- plotReducedDim(sce,
                     dimred = "UMAP",
                     colour_by = "day") + ggtitle("Day - no batch")

p2 <- plotReducedDim(sce,
                     dimred = "UMAP_HARMONY_donor_experiment",
                     colour_by = "day") + ggtitle("Day - batch")
p1 + p2

# No batch versus batch corrected, color by donor
p3 <- plotReducedDim(sce,
                     dimred = "UMAP",
                     colour_by = "donor") + ggtitle("Donor - no batch")

p4 <- plotReducedDim(sce,
                     dimred = "UMAP_HARMONY_donor_experiment",
                     colour_by = "donor") + ggtitle("Donor - batch")
p3 + p4

# No batch versus batch corrected, color by experiment
p5 <- plotReducedDim(sce,
                     dimred = "UMAP",
                     colour_by = "experiment") + ggtitle("Experiment - no batch")

p6 <- plotReducedDim(sce,
                     dimred = "UMAP_HARMONY_donor_experiment",
                     colour_by = "experiment") + ggtitle("Experiment - batch")
p5 + p6

We here show the UMAP visualizations comparing non-corrected versus the batch corrected data, with cells colored based on day, donor and experiment. The interpretation is analogous to the interpretation above for the Seurat batch correction:

The batch correction seems to have worked very well. Both with and without batch correction, we observe that cells of the same time point cluster together. But when no batch correction is performed, there seems to be an additional level of variability in the data.

When we color the cells based on the donor/experiment variable, we see that without batch correction cells of the same donor cluster together. After batch correction, such donor/experiment effects seem to be no longer present.

Also note that while batch correction remove the between-donor/experiment variability, the between-day variability that is of interest is still preserved. As such, based on our visualizations, it looks like the batch correction did not overcorrect and succeeded in removing only the unwanted variation in the data.

Clustering

In the second lab session, we discussed graph-based clustering, k-means clustering and hierarchical clustering. Here, we will perform hierarchical clustering.

Hierarchical clustering

We may split the hierarchical clustering process in two intuitive steps:

  1. Compute the pairwise distances between all cells. These are by default euclidean distances and, in order to reduce data complexity and increase signal to noise, we may perform this on the top (30) PC’s. Implemented in the dist function.

  2. Perform a hierarchical clustering analysis on these distances. Initially, each cell is assigned to its own cluster and then the algorithm proceeds iteratively, at each stage joining the two most similar clusters, continuing until there is just a single cluster. This is implemented in the hclust function.

Note that the hclust function allows for specifying a method argument. The differences between the different methods are beyond the scope of this session, but a brief description is provided in the function help file. In the context of scRNA-seq, we have mostly seen the use of the “ward.D2” method.

distsce <- dist(reducedDim(sce, "HARMONY_donor_experiment")[,1:10])
hcl <- hclust(distsce, method = "ward.D2")
plot(hcl, labels = FALSE)

Next, we need to “cut the tree”, i.e., choose at which resolution we want to report the (cell-type) clusters. This can be achieved with the cutree function. As an input, cutree takes the dendrogram from the hclust function and a threshold value for cutting the tree. This is either k, the number of clusters we want to report, or h, the height in the dendrogram at which we wan to cut the tree.

Here we choose k = 4, since we know in advance that we expect four clusters of cells (four time points).

clust_hcl_k4 <- cutree(hcl, k = 4)
table(clust_hcl_k4)
## clust_hcl_k4
##    1    2    3    4 
##  832  980 1001  918

Next, we visualize the data in PCA space colored based on time point and based on our inferred cluster labels.

sce$clust_hcl_k4 <- as.factor(clust_hcl_k4)

plotReducedDim(sce, 
        dimred = "HARMONY_donor_experiment",
         colour_by ="day")

plotReducedDim(sce,
        dimred = "HARMONY_donor_experiment",
        colour_by="clust_hcl_k4")

We see that our inferred clustering largely corresponds with the original day variable.

table(sce$day, sce$clust_hcl_k4)
##       
##          1   2   3   4
##   day0  31   0 826   0
##   day1  28   0  43 877
##   day2 730 215  89  38
##   day3  43 765  43   3

Mapping clusters to timepoints, we note that most cells of day0 are in hierarchical cluster 3 (arbitrary indicator), day1 cells are in cluster 4, day2 cells are mainly in cluster 1 and day3 cells are found back in cluster 2.

Trajectory inference

Trajectory inference is a computational procedure that attempts to summarize a dynamic process in a ‘trajectory’. The trajectory tries to find a sensible ordering of the cells according to their progression through this dynamic process. Trajectories can be linear, diverging, converging or cyclic. If there are multiple differentiation paths, each path is called a lineage, and the combination of lineages is called a trajectory.

Based on the trajectory, one may define a pseudotime for each cell, which defines that cell’s progression along one of the differentiation paths: if the pseudotime of a cell is close to zero, then that cell is close to the starting point of the trajectory.

Computing the trajectory

Many methods for estimating trajectories exist. Here, we will use slingshot to create a trajectory for the Cuomo dataset.

library(slingshot)
sce <- slingshot(sce, # target object
                 start.clus = "3", # cluster that corresponds to day0 cells!
                 end.clus = "2", # cluster that corresponds to day3 cells!
                 clusterLabels = "clust_hcl_k4", # clustering to use 
                 reducedDim = "HARMONY_donor_experiment") # dimred to use

Visualizing the trajectory

plot(reducedDims(sce)$HARMONY_donor_experiment, 
     col = as.factor(sce$clust_hcl_k4), # colored according to inferred clusters
     pch=16, 
     asp = 1)
lines(SlingshotDataSet(sce), 
      lwd=3, 
      type = 'lineages', 
      col = 'orange')

plot(reducedDims(sce)$HARMONY_donor_experiment, 
     col = as.factor(sce$day), # colored according to original time points
     pch=16, 
     asp = 1)
lines(SlingshotDataSet(sce), 
      lwd=3, 
      col = 'orange')

We could also use ggplot2 functions to obtained prettier figures that are more easy to annotate:

suppressPackageStartupMessages(library(dplyr))

rd <- reducedDim(sce, type="HARMONY_donor_experiment")[,1:2] # extract first two PCs
colnames(rd) <- c("Dim1", "Dim2") # give column names
cl <- sce$clust_hcl_k4 # store clustering
df <- data.frame(rd, "cl" = as.character(cl)) # PCs and clustering together in 1 data frame
sds <- slingshot(rd, cl) # convert data frame to slingshot object
curves <- slingCurves(sds, as.df = TRUE) # obtain smooth curve for lineages (here only one lineage)

# plot cells as dots in dimension reduced space
p <- ggplot(df, aes(x = Dim1, y = Dim2)) +
  geom_point(aes(fill = cl), col = "grey70", shape = 21) + 
  theme_classic()

# add smooth curves
p + geom_path(data = curves %>% arrange(Order),
              aes(group = Lineage), size = 1.5) 

# compute and add minimum spanning tree
mst <- slingMST(sds, as.df = TRUE)
p + geom_point(data = mst, size = 4) +
  geom_path(data = mst %>% arrange(Order), aes(group = Lineage), size = 2)

We see that the trajectory inferred with slingshot nicely captures the expected developmental process.

Differential gene expression tests along a trajectory using tradeSeq

As a next step, we may be interested in identifying the genes are involved in the developmental process. To this end, our group has developed the Bioconductor R package tradeSeq. tradeSeq is a flexible tool that allows for studying differential gene expression along such a trajectory, within or between different lineages. The functionalities of the package are summarized in the following figure:

knitr::include_graphics("./../tradeseq_summary.jpeg")

library(tradeSeq)

tradeSeq uses a negative binomial generalized additive model (NB-GAM) framework to smooth each gene’s expression in each lineage. Smoothers can be decomposed into a set of basis functions, which are joined together at knot points, often simply called knots (k).

Ideally, the number of knots should be selected to reach an optimal bias-variance trade-off for the smoother, where one explains as much variability in the expression data as possible with only a few regression coefficients. In order to guide that choice, we developed diagnostic plots using the Akaike Information Criterion (AIC). This is implemented in the evaluateK function in tradeSeq.

However, in the tradeSeq publication the authors show that the algorithm is not too sensitive for the number of knots, and that values between 5 and 9 often work well. The code below would allow you to find a good value for k, but we will simply use the default value of k = 6 downstream.

### Find knots

# We first need to decide on the number of knots. This is done using the  -->
# `evaluateK` function. This takes a little time. -->

# takes 9 minutes for me
set.seed(5)
icMat <- evaluateK(counts = assays(sce)$counts,
                   sds = sling$slingshot,
                   k = 3:10, 
                   nGenes = 500, 
                   verbose = T)

Fit GAM

We fit a negative binomial generalized additive model (NB-GAM), smoothing each gene’s expression along the developmental trajectory. When modeling all the genes (±10.000), this function takes about 20 minutes to complete. For this lab session, we will therefore randomly sample 1.000 genes. In addition, we make sure that three specific genes are also included: “ENSG00000111704”, “ENSG00000164458” and “ENSG00000141448”. These genes are known markers for the different developmental stages nd were use in the publication of Cuomo et al..

The tradeSeq model allows us to incorporate fixed effects. While we have estimated the trajectory on the integrated data, we model the raw gene expression data, since tradeSeq is a count model and requires raw counts as input. On the raw counts, we therefore still have substantial variability that may be explained by the patient effects. We therefore incorporate a patient fixed effect to the design matrix.

set.seed(7)
subset_genes <- sample(rownames(sce), 1000, replace = FALSE)

# genes from paper
markers <- c("ENSG00000111704", "ENSG00000164458", "ENSG00000141448")

# make sure the genes from the paper are in there
subset_genes <- c(subset_genes, markers[!markers %in% subset_genes])

# ±7min for 1000 genes
pseudotime <- slingPseudotime(sce, na = FALSE)
cellWeights <- slingCurveWeights(sce)

patient <- colData(sce)$donor
U <- model.matrix(~ 0 + patient)
sce_fit <- fitGAM(counts = assays(sce)$counts[subset_genes,], 
                  pseudotime = pseudotime, 
                  cellWeights = cellWeights,
                  nknots = 6, 
                  U = U,
                  verbose = TRUE)

To assess if all models have converged;

table(rowData(sce_fit)$tradeSeq$converged)
## 
## TRUE 
## 1003

Association test

Next, we can perform different types of differential expression testing along the trajectory.

The associationTest assesses whether the average expression of a gene is associated with pseudotime. To prioritize for genes that are also biologically relevant, we may test against a log-fold change cut-off:

assoRes2 <- associationTest(sce_fit, l2fc=log2(2))
sum(p.adjust(assoRes2$pvalue, method = "BH") < 0.05, na.rm=T)/nrow(assoRes2) 
## [1] 0.219342

Start vs end top 20

Another type of test is to compare the average gene expression of each gene between the start point and the end point of a lineage. This is implemented in the startVsEndTest function.

startRes <- startVsEndTest(sce_fit, l2fc=log2(2))

We can then visualize the gene expression profile along pseudotime of the top 5 genes for which differential expression between start and end point was identified.

oStart <- order(startRes$waldStat, decreasing = TRUE)
for (i in 1:5) {
  sigGeneStart <- oStart[i] # top 5 most significant genes in the start vs. end test
  print(plotSmoothers(sce_fit, 
                assays(sce_fit)$counts, 
                gene = sigGeneStart) +
          ggtitle(rownames(sce)[sigGeneStart]))
}

Comparison to original paper

In the Cuomo paper, the authors highlighted the following genes; “ENSG00000111704”, “ENSG00000164458” and “ENSG00000141448”. In gene symbols, these genes are NANOG, T (yes, there is a gene called “T)” and GATA6. These genes are markers of day0, day1 and day2/day3 cells, respectively.

We may now visualize the expression of these genes along pseudotime.

plotSmoothers(sce_fit, 
              assays(sce_fit)$counts, 
              gene = which(rownames(sce_fit) == "ENSG00000111704")) +
  ggtitle("ENSG00000111704")

plotSmoothers(sce_fit, 
              assays(sce_fit)$counts, 
              gene = which(rownames(sce_fit) == "ENSG00000164458")) +
  ggtitle("ENSG00000164458")

plotSmoothers(sce_fit, 
              assays(sce_fit)$counts, 
              gene = which(rownames(sce_fit) == "ENSG00000141448")) +
  ggtitle("ENSG00000141448")

A very nice correspondence with the results presented in the paper!!

knitr::include_graphics("./../cuomo_traj1.jpeg")

knitr::include_graphics("./../cuomo_traj2.jpeg")

knitr::include_graphics("./../cuomo_traj3.jpeg")

We also inspect the results in our differential testing output.

Association test:

assoRes2[markers,]
##                     waldStat df pvalue meanLogFC
## ENSG00000111704 4.596703e+13  5      0  1.514278
## ENSG00000164458 1.651328e+14  5      0  4.718686
## ENSG00000141448           NA NA     NA 10.946757

Start versus end test:

startRes[markers,]
##                    waldStat df       pvalue logFClineage1
## ENSG00000111704   0.1264224  1 7.221706e-01    -0.7887447
## ENSG00000164458  15.3192211  1 9.078804e-05     2.7371488
## ENSG00000141448 223.4040585  1 0.000000e+00    13.0634051

Another interesting visualization is implemented in the plotGeneCount function, which colors the cells based on the log-transformed expression value of the target genes.

plotGeneCount(sce$slingshot, 
              assays(sce_fit)$counts, 
              gene = which(rownames(sce_fit) == "ENSG00000111704"))

plotGeneCount(sce$slingshot, 
              assays(sce_fit)$counts, 
              gene = which(rownames(sce_fit) == "ENSG00000164458"))

plotGeneCount(sce$slingshot, 
              assays(sce_fit)$counts, 
              gene = which(rownames(sce_fit) == "ENSG00000141448"))

LS0tCnRpdGxlOiAnTGFiNDogQmF0Y2ggY29ycmVjdGlvbiBhbmQgdHJhamVjdG9yeSBpbmZlcmVuY2UgZm9yIHRoZSBDdW9tbyBkYXRhc2V0JwphdXRob3I6ICJLb2VuIFZhbiBkZW4gQmVyZ2UgYW5kIEplcm9lbiBHaWxpcyIKZGF0ZTogIjExLzEyLzIwMjEiCm91dHB1dDogCiAgaHRtbF9kb2N1bWVudDoKICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OiB0cnVlCi0tLQoKIyBQcmVhbWJsZTogaW5zdGFsbGF0aW9uIG9mIFIgbGlicmFyaWVzCgpgYGB7cn0KIyBpbnN0YWxsIEJpb2NNYW5hZ2VyIHBhY2thZ2UgaWYgbm90IGluc3RhbGxlZCB5ZXQuCiMgQmlvY01hbmFnZXIgaXMgdGhlIHBhY2thZ2UgaW5zdGFsbGVyIGZvciBCaW9jb25kdWN0b3Igc29mdHdhcmUuCmlmICghcmVxdWlyZU5hbWVzcGFjZSgiQmlvY01hbmFnZXIiLCBxdWlldGx5ID0gVFJVRSkpCiAgICBpbnN0YWxsLnBhY2thZ2VzKCJCaW9jTWFuYWdlciIpCgojIGluc3RhbGwgcGFja2FnZXMgaWYgbm90IHlldCBpbnN0YWxsZWQuCnBrZ3MgPC0gYygiU2luZ2xlQ2VsbEV4cGVyaW1lbnQiLAogICAgICAgICAgIkV4cGVyaW1lbnRIdWIiLAogICAgICAgICAgImVkZ2VSIiwKICAgICAgICAgICJiaW9tYVJ0IiwKICAgICAgICAgICJEcm9wbGV0VXRpbHMiLCAKICAgICAgICAgICJzY1JOQXNlcSIsIAogICAgICAgICAgInNjYXRlciIsIAogICAgICAgICAgInNjdXR0bGUiLCAKICAgICAgICAgICJzY3JhbiIsCiAgICAgICAgICAic2NyeSIsCiAgICAgICAgICAiQmlvY1Npbmd1bGFyIiwgCiAgICAgICAgICAic2NEYmxGaW5kZXIiLAogICAgICAgICAgIlNldXJhdCIsCiAgICAgICAgICAiUENBdG9vbHMiLAogICAgICAgICAgImdsbXBjYSIsCiAgICAgICAgICAiZ2VuZWZpbHRlciIsCiAgICAgICAgICAicGhlYXRtYXAiLAogICAgICAgICAgInRpZHl2ZXJzZSIsCiAgICAgICAgICAibWNsdXN0IiwKICAgICAgICAgICJnZ3Bsb3QyIiwKICAgICAgICAgICJkZXZ0b29scyIsCiAgICAgICAgICAiU2luZ2xlUiIpCm5vdEluc3RhbGxlZCA8LSBwa2dzWyFwa2dzICVpbiUgaW5zdGFsbGVkLnBhY2thZ2VzKClbLDFdXQppZihsZW5ndGgobm90SW5zdGFsbGVkKSA+IDApewogIEJpb2NNYW5hZ2VyOjppbnN0YWxsKG5vdEluc3RhbGxlZCkKfQpgYGAKCiMgaW5zdGFsbCBoYXJtb255IGZyb20gZ2l0aHViCgpgYGAKbGlicmFyeShkZXZ0b29scykKaW5zdGFsbF9naXRodWIoImltbXVub2dlbm9taWNzL2hhcm1vbnkiLAogICAgICAgICAgICAgICBkZXBlbmRlbmNpZXMgPSBUUlVFLAogICAgICAgICAgICAgICBmb3JjZSA9IFRSVUUpCmBgYAoKIyBUaGUgQ3VvbW8gZGF0YXNldAoKV2UgaGVyZSBtYWtlIHVzZSBvZiB0aGUgcHVibGljYXRpb24gb2YgQW5uYSBDdW9tbyAqZXQgYWwuKiwgd2hpY2ggd2Ugd2lsbCByZWZlciB0byBhcyB0aGUgYGlQU0MgZGF0YXNldGAuIFRoZSAKcGFwZXIgdGhhdCBkZXNjcmliZXMgdGhpcyBkYXRhc2V0IGNhbiBiZSBmb3VuZCB1c2luZyB0aGlzIApbbGlua10oaHR0cHM6Ly93d3cubmF0dXJlLmNvbS9hcnRpY2xlcy9zNDE0NjctMDIwLTE0NDU3LXopLgoKSW4gdGhlIGV4cGVyaW1lbnQsIHRoZSBhdXRob3JzIGhhcnZlc3RlZCBwbHVyaXBvdGVudCBzdGVtIGNlbGxzIChpUFNDcykKZnJvbSAxMjUgaGVhbHRoeSBodW1hbiBkb25vcnMsIGFuZCBpbmR1Y2VkIHRoZW0gdG8gc3R1ZHkgdGhlIGVuZG9kZXJtIApkaWZmZXJlbnRpYXRpb24gcHJvY2VzcywgaW4gd2hpY2ggaVBTQ3MgZGlmZmVyZW50aWF0ZSB0byBlbmRvZGVybSBjZWxscyBvdmVyIHRoZQpjb3Vyc2Ugb2YgYXBwcm94aW1hdGVseSB0aHJlZSBkYXlzLiBBcyBzdWNoLCB0aGUgYXV0aG9ycyAKY3VsdGVyZWQgdGhlIGlQU0NzIGNlbGwgbGluZXMgYW5kIGFsbG93ZWQgdGhlbSB0byBkaWZmZXJlbnRpYXRlIGZvciB0aHJlZSBkYXlzLiAKRHVyaW5nIHRoZSBleHBlcmltZW50LCBjZWxscyB3ZXJlIGhhcnZlc3RlZCBhdCBmb3VyIGRpZmZlcmVudCB0aW1lIHBvaW50czogCmRheTAgKGRpcmVjdGx5IGF0IGluY3ViYXRpb24pLCBkYXkxLCBkYXkyIGFuZCBkYXkzLiBLbm93aW5nIHRoZSBwcm9jZXNzIG9mIAplbmRvZGVybSBkaWZmZXJlbnRpYXRpb24sIHRoZXNlIHRpbWUgcG9pbnRzIHNob3VsZCByb3VnaGx5IGNvcnJlc3BvbmQgdG8gZGlmZmVyZW50IApjZWxsIHR5cGVzOiBkYXkwIGFyZSAodW5kaWZmZXJlbnRpYXRlZCkgaVBTQ3MsIGRheTEgYXJlIG1vc3RseSBtZXNlbmRvZGVybSBjZWxscywgZGF5MgphcmUgbW9zdGx5ICJpbnRlcm1lZGlhdGUiIGNlbGxzIGFuZCBkYXkzIGFyZSBtb3N0bHkgZnVsbHkgZGlmZmVyZW50aWF0ZWQgZW5kb2Rlcm0gY2VsbHMuCgpUaGlzIGRhdGFzZXQgd2FzIGdlbmVyYXRlZCB1c2luZyB0aGUgKipTTUFSVC1TZXEyKiogc2NSTkEtc2VxIHByb3RvY29sLgoKVGhlIGZpbmFsIGdvYWwgb2YgdGhlIGV4cGVyaW1lbnQgd2FzIHRvIGNoYXJhY3Rlcml6ZSBwb3B1bGF0aW9uIHZhcmlhdGlvbiBpbiB0aGUKcHJvY2VzcyBvZiBlbmRvZGVybSBkaWZmZXJlbnRpYXRpb24uCgojIERvd25sb2FkIGRhdGEKCkZvciB0aGlzIGxhYiBzZXNzaW9uLCB3ZSB3aWxsIHdvcmsgd2l0aCBhIHN1YnNldCBvZiB0aGUgZGF0YSwgaS5lLiwgdGhlIGRhdGEKZm9yIHRoZSBmaXJzdCAoYWxwaGFiZXRpY2FsbHkpIDE1IHBhdGllbnRzIGluIHRoZSBleHBlcmltZW50LiBUaGVzZSBhcmUgdGhlCmRhdGEgeW91IGFscmVhZHkgZG93bmxvYWRlZCBmb3IgbGFiIHNlc3Npb24gMiB1c2luZyB0aGUgKkJlbG5ldCBmaWxlc2VuZGVyKiAKbGluay4KClRoZSBvcmlnaW5hbCBkYXRhICgxMjUgcGF0aWVudCkgY291bGQgYmUgZG93bmxvYWRlZCBmcm9tIApbWmVub2RvXShodHRwczovL3plbm9kby5vcmcvcmVjb3JkLzM2MjUwMjQjLllXZmFodGxCeEIxKS4gQXQgdGhlIGJvdHRvbSBvZiB0aGlzCndlYi1wYWdlLCB3ZSBjYW4gZG93bmxvYWQgdGhlIGZpbGVzIGByYXdfY291bnRzLmNzdi56aXBgIGFuZCAKYGNlbGxfbWV0YWRhdGFfY29scy50c3ZgIGFuZCBzdG9yZSB0aGVzZSBmaWxlcyBsb2NhbGx5LiBXZSBkbyBub3QgcmVjb21tZW5kIApkb2luZyB0aGlzIGR1cmluZyB0aGUgbGFiIHNlc3Npb24sIHRvIGF2b2lkIG92ZXJsb2FkaW5nIHRoZSBXaUZpIG5ldHdvcmsuCgojIEltcG9ydCBkYXRhCgpGaXJzdCB3ZSByZWFkIGluIHRoZSBjb3VudCBtYXRyaXg6CgpgYGB7ciwgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KbGlicmFyeShTaW5nbGVDZWxsRXhwZXJpbWVudCkKc2NlIDwtIHJlYWRSRFMoIi9Vc2Vycy9qZy9EZXNrdG9wL3NjZV8xNV9jdW9tby5yZHMiKQojc2NlIDwtIHJlYWRSRFMoIi9Vc2Vycy9rb2VudmFuZGVuYmVyZ2UvRGVza3RvcC9zY2VfMTVfY3VvbW8ucmRzIikKYGBgCgojIEV4cGxvcmUgbWV0YWRhdGEKCkV4cGxvcmF0aW9uIG9mIHRoZSBtZXRhZGF0YSBpcyBlc3NlbnRpYWwgdG8gZ2V0IGEgYmV0dGVyIGlkZWEgb2Ygd2hhdCB0aGUKZXhwZXJpbWVudCB3YXMgYWJvdXQgYW5kIGhvdyBpdCB3YXMgb3JnYW5pemVkLgoKYGBge3J9CmNvbERhdGEoc2NlKVsxOjUsMToxMF0KY29sbmFtZXMoY29sRGF0YShzY2UpKQpgYGAKCkFzIHN0YXRlZCBpbiB0aGUgcGFwZXIsIGNlbGxzIHdlcmUgc2FtcGxlZCBvbiA0IHRpbWUgcG9pbnRzLiBFYWNoIG9mIHRoZXNlIAp0aW1lIHBvaW50cyBpcyByb3VnaGx5IGV4cGVjdGVkIHRvIGNvcnJlc3BvbmQgd2l0aCBkaWZmZXJlbnQgY2VsbCB0eXBlcyAoZGF5MCA9IGlQU0MsCmRheTEgPSBtZXNlbmRvZGVybSwgZGF5MiA9IGludGVybWVkaWF0ZSBhbmQgZGF5MyA9IGVuZG9kZXJtKS4KCmBgYHtyfQp0YWJsZShjb2xEYXRhKHNjZSkkZGF5KQpgYGAKCkFzIHN0YXRlZCBpbiB0aGUgcGFwZXIsIGNlbGxzIHdlcmUgaGFydmVzdGVkIGZyb20gMTI1IHBhdGllbnRzLiBIZXJlLCB3ZSBhcmUKd29ya2luZyBvbiBhIHN1YnNldCB3aXRoIDE1IHBhdGllbnRzLiBUaGUgbnVtYmVyIG9mIGNlbGxzIGhhcnZlc3RlZCBwZXIgcGF0aWVudCAKKG92ZXIgYWxsIHRpbWUgcG9pbnRzKSByYW5nZXMgZnJvbSAzMSB0byA2MzcuCgpgYGB7cn0KbGVuZ3RoKHRhYmxlKGNvbERhdGEoc2NlKSRkb25vcikpICMgbnVtYmVyIG9mIGRvbm9ycwpyYW5nZSh0YWJsZShjb2xEYXRhKHNjZSkkZG9ub3IpKSAjIGNlbGxzIHBlciBkb25vcgpgYGAKCkJlbG93LCB3ZSBsb29rIGF0IGhvdyBtYW55IGNlbGxzIGFyZSBoYXJ2ZXN0IHBlciBwYXRlbnQgYW5kIHBlciB0aW1lIHBvaW50LgoKYGBge3J9CnRhYmxlKGNvbERhdGEoc2NlKSRkb25vcixjb2xEYXRhKHNjZSkkZGF5KQpgYGAKCldlIHNlZSB0aGF0IGZvciBtYW55IHBhdGllbnRzIHRoZSBkYXRhIGlzIGNvbXBsZXRlLCBpLmUuIGNlbGxzIHdlcmUgc2FtcGxlZApvbiBhbGwgdGltZSBwb2ludHMuCgpQcmFjdGljYWxseSwgdGhlIGNlbGxzIHdlcmUgcHJlcGFyZWQgaW4gMjggYmF0Y2hlcy4gU2luY2Ugd2UgaGVyZSBvbmx5IGxvb2sKYXQgYSBzdWJzZXQgb2YgdGhlIGRhdGEsIHdlIHNlZSB0aGF0IG9ubHkgMTQgb2YgdGhlc2UgYmF0Y2hlcyBhcmUgcmVwcmVzZW50ZWQuCgpgYGB7cn0KbGVuZ3RoKHRhYmxlKGNvbERhdGEoc2NlKSRleHBlcmltZW50KSkKdGFibGUoY29sRGF0YShzY2UpJGV4cGVyaW1lbnQsIGNvbERhdGEoc2NlKSRkYXkpCmBgYAoKIyBPYnRhaW5pbmcgYW5kIGluY2x1ZGluZyByb3dEYXRhCgpUaGUgYHJvd0RhdGFgIHNsb3Qgb2YgYSBgU2luZ2xlQ2VsbEV4cGVyaW1lbnRgIG9iamVjdCBhbGxvd3MgZm9yIHN0b3JpbmcgCmluZm9ybWF0aW9uIG9uIHRoZSBmZWF0dXJlcywgaS5lLiB0aGUgZ2VuZXMsIGluIGEgZGF0YXNldC4gSW4gb3VyIG9iamVjdCwKdGhlIGByb3dEYXRhYCBzbG90IGN1cnJlbnRseSBjb250YWlucyB0aGUgZm9sbG93aW5nOgoKYGBge3J9CmhlYWQocm93RGF0YShzY2UpKQpgYGAKClRvIGltcHJvdmUgb3VyIGdlbmUtbGV2ZWwgaW5mb3JtYXRpb24sIHdlIG1heToKCjEuIFNwbGl0IGBWMWAgaW50byB0d28gY29sdW1ucywgb25lIHdpdGggdGhlIEVOU0VNQkwgSUQgYW5kIHRoZSBvdGhlciB3aXRoIAp0aGUgZ2VuZSBzeW1ib2wuCgoyLiBEaXNwbGF5IHdoaWNoIGNocm9tb3NvbWUgdGhlIGdlbmUgaXMgbG9jYXRlZAoKTWFueSBtb3JlIG9wdGlvbnMgYXJlIHBvc3NpYmxlLCBidXQgYXJlIG5vdCBuZWNlc3NhcnkgZm9yIHVzIHJpZ2h0IG5vdy4KCmBgYHtyfQpyb3dEYXRhKHNjZSkgPC0gZGF0YS5mcmFtZShFbnNlbWJsID0gZ3N1YigiXy4qIiwgIiIsIHJvd0RhdGEoc2NlKSRWMSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIFN5bWJvbCA9IGdzdWIoIl5bXl9dKl8iLCAiIiwgcm93RGF0YShzY2UpJFYxKSkKaGVhZChyb3dEYXRhKHNjZSkpCmBgYAoKYGBgCiMgY3VycmVudGx5IGlzc3VlcyB3aXRoIGVuc2VtYmwgc2VydmVyIC0+IGRvIG5vdCBldmFsdWF0ZSB0aGlzIGNodW5rCmxpYnJhcnkoImJpb21hUnQiKQplbnNlbWJsNzUgPC0gdXNlRW5zZW1ibChiaW9tYXJ0ID0gJ2dlbmVzJywgCiAgICAgICAgICAgICAgICAgICAgICAgIGRhdGFzZXQgPSAnaHNhcGllbnNfZ2VuZV9lbnNlbWJsJywKICAgICAgICAgICAgICAgICAgICAgICAgdmVyc2lvbiA9IDc1KQoKR2VuZUluZm8gPC0gZ2V0Qk0oYXR0cmlidXRlcyA9IGMoImVuc2VtYmxfZ2VuZV9pZCIsICMgVG8gbWF0Y2ggd2l0aCByb3duYW1lcyBTQ0UKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgImNocm9tb3NvbWVfbmFtZSIpLCAjIEluZm8gb24gY2hyb21vc2UKICAgICAgICAgICAgICAgICAgbWFydCA9IGVuc2VtYmw3NSkKR2VuZUluZm8gPC0gR2VuZUluZm9bbWF0Y2gocm93RGF0YShzY2UpJEVuc2VtYmwsIEdlbmVJbmZvJGVuc2VtYmxfZ2VuZV9pZCksXQoKcm93RGF0YShzY2UpIDwtIGNiaW5kKHJvd0RhdGEoc2NlKSwgR2VuZUluZm8pCmhlYWQocm93RGF0YShzY2UpKQphbGwocm93RGF0YShzY2UpJEVuc2VtYmwgPT0gcm93RGF0YShzY2UpJGVuc2VtYmxfZ2VuZV9pZCkgCiMgaWRlbnRpY2FsLCBhcyBkZXNpcmVkLCBzbyB3ZSBjb3VsZCBvcHRpb25hbGx5IHJlbW92ZSBvbmUgb2YgdGhlIHR3bwpgYGAKCiMgRmlsdGVyaW5nIG5vbi1pbmZvcm1hdGl2ZSBnZW5lcwoKTGV0IHVzIGZpcnN0IHRyeSB0aGUgdmVyeSBzaW1wbGUgYW5kIHZlcnkgbGVuaWVudCBmaWx0ZXJpbmcgY3JpdGVyaW9uIHRoYXQgd2UKYWRvcHRlZCBmb3IgdGhlIE1hY29za28gZGF0YXNldC4KCmBgYHtyfQprZWVwIDwtIHJvd1N1bXMoYXNzYXlzKHNjZSkkY291bnRzID4gMCkgPiAxMAp0YWJsZShrZWVwKQpgYGAKCldlIHNlZSB0aGF0IHRoaXMgZmlsdGVyaW5nIHN0cmF0ZWd5IGRvZXMgbm90IHJlbW92ZSBhbnkgZ2VuZXMgZm9yIHRoaXMgZGF0YXNldC4KSW4gZ2VuZXJhbCwgZGF0YXNldHMgZnJvbSBwbGF0ZS1iYXNlZCBzY1JOQS1zZXEgZGF0YXNldCBoYXZlIGEgZmFyIGhpZ2hlcgpzZXF1ZW5jaW5nIGRlcHRoIHRoYW4gZGF0YSBmcm9tIGRyb3BsZXQtYmFzZWQgcHJvdG9jb2xzLiBBcyByZXF1aXJpbmcgYSBtaW5pbXVtCmV4cHJlc3Npb24gb2YgMSBjb3VudCBpbiBhdCBsZWFzdCAxMCBjZWxscyBpcyBhIHZlcnkgbGVuaWVudCBjcml0ZXJpb24gaWYgd2UgCmNvbnNpZGVyIHRoYXQgd2UgYXJlIHdvcmtpbmcgMzYuMDAwIGNlbGxzLCB3ZSBzaG91bGQgY29uc2lkZXIgYWRvcHRpbmcgYSBtb3JlIHN0cmluZ2VudApmaWx0ZXJpbmcgY3JpdGVyaXVtLgpCZWxvdyB3ZSBkbyBzbyB1c2luZyB0aGUgYGZpbHRlckJ5RXhwcmAgZnJvbSBgZWRnZVJgOgoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoZWRnZVIpCgp0YWJsZShjb2xEYXRhKHNjZSkkZGF5KQoKa2VlcDIgPC0gZWRnZVI6OmZpbHRlckJ5RXhwcih5PXNjZSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBncm91cCA9IGNvbERhdGEoc2NlKSRkYXksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWluLmNvdW50ID0gNSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtaW4ucHJvcCA9IDAuNCkKdGFibGUoa2VlcDIpCmBgYAoKYGBge3J9CnNjZSA8LSBzY2Vba2VlcDIsXQpgYGAKCiMgUXVhbGl0eSBjb250cm9sCgojIyBDYWxjdWxhdGUgUUMgdmFyaWFibGVzCgpgYGB7cn0KbGlicmFyeShzY2F0ZXIpCgojIGNoZWNrIEVSQ0Mgc3Bpa2UtaW4gdHJhbnNjcmlwdHMKc3VtKGdyZXBsKCJeRVJDQy0iLCByb3dEYXRhKHNjZSkkU3ltYm9sKSkgIyBubyBzcGlrZS1pbiB0cmFuc2NyaXB0cyBhdmFpbGFibGUKCmlzLm1pdG8gPC0gZ3JlcGwoIl5NVCIsIHJvd0RhdGEoc2NlKSRjaHJvbW9zb21lX25hbWUpCnN1bShpcy5taXRvKSAjIDEzIG1pdG9jaG9uZHJpYWwgZ2VuZXMKCmRmIDwtIHBlckNlbGxRQ01ldHJpY3Moc2NlLCBzdWJzZXRzPWxpc3QoTWl0bz1pcy5taXRvKSkKaGVhZChkZikKCiMjIGFkZCB0aGUgUUMgdmFyaWFibGVzIHRvIHNjZSBvYmplY3QKY29sRGF0YShzY2UpIDwtIGNiaW5kKGNvbERhdGEoc2NlKSwgZGYpCmBgYAoKIyMgRXhwbG9yYXRvcnkgZGF0YSBhbmFseXNpcwoKSW4gdGhlIGZpZ3VyZSBiZWxvdywgd2Ugc2VlIHRoYXQgc2V2ZXJhbCBjZWxscyBoYXZlIGEgdmVyeSBsb3cgbnVtYmVyIG9mIApleHByZXNzZWQgZ2VuZXMsIGFuZCB3aGVyZSBtb3N0IG9mIHRoZSBtb2xlY3VsZXMgYXJlIGRlcml2ZWQgZnJvbSAKbWl0b2Nob25kcmlhbCBnZW5lcy4gVGhpcyBpbmRpY2F0ZXMgbGlrZWx5IGRhbWFnZWQgY2VsbHMsIHByZXN1bWFibHkgYmVjYXVzZSAKb2YgbG9zcyBvZiBjeXRvcGxhc21pYyBSTkEgZnJvbSBwZXJmb3JhdGVkIGNlbGxzLCBzbyB3ZSBzaG91bGQgcmVtb3ZlIHRoZXNlIGZvciAKdGhlIGRvd25zdHJlYW0gYW5hbHlzaXMuCgpgYGB7cn0KIyBOdW1iZXIgb2YgZ2VuZXMgdnMgbGlicmFyeSBzaXplCnBsb3RDb2xEYXRhKHNjZSwgeCA9ICJzdW0iLCB5PSJkZXRlY3RlZCIsIGNvbG91cl9ieT0iZGF5IikgCgojIE1pdG9jaG9uZHJpYWwgZ2VuZXMKcGxvdENvbERhdGEoc2NlLCB4ID0gImRldGVjdGVkIiwgeT0ic3Vic2V0c19NaXRvX3BlcmNlbnQiLCBjb2xvdXJfYnk9ImRheSIpCmBgYAoKIyMgUUMgdXNpbmcgYWRhcHRpdmUgdGhyZXNob2xkcwoKQmVsb3csIHdlIHJlbW92ZSBjZWxscyB0aGF0IGFyZSBvdXRseWluZyB3aXRoIHJlc3BlY3QgdG8KCiAxLiBBIGxvdyBzZXF1ZW5jaW5nIGRlcHRoIChudW1iZXIgb2YgVU1Jcyk7CiAyLiBBIGxvdyBudW1iZXIgb2YgZ2VuZXMgZGV0ZWN0ZWQ7CiAzLiBBIGhpZ2ggcGVyY2VudGFnZSBvZiByZWFkcyBmcm9tIG1pdG9jaG9uZHJpYWwgZ2VuZXMuCiAKV2UgcmVtb3ZlIGEgdG90YWwgb2YgJDMwMSQgY2VsbHMsIG1haW5seSBkdWUgdG8gbG93IHNlcXVlbmNpbmcgZGVwdGggYW5kCmxvdyBudW1iZXIgb2YgZ2VuZXMgZGV0ZWN0ZWQuCgpgYGB7cn0KbG93TGliIDwtIGlzT3V0bGllcihkZiRzdW0sIHR5cGU9Imxvd2VyIiwgbG9nPVRSVUUpCmxvd0ZlYXR1cmVzIDwtIGlzT3V0bGllcihkZiRkZXRlY3RlZCwgdHlwZT0ibG93ZXIiLCBsb2c9VFJVRSkKaGlnaE1pdG8gPC0gaXNPdXRsaWVyKGRmJHN1YnNldHNfTWl0b19wZXJjZW50LCB0eXBlPSJoaWdoZXIiKQoKdGFibGUobG93TGliKQp0YWJsZShsb3dGZWF0dXJlcykKdGFibGUoaGlnaE1pdG8pCgpkaXNjYXJkQ2VsbHMgPC0gKGxvd0xpYiB8IGxvd0ZlYXR1cmVzIHwgaGlnaE1pdG8pCnRhYmxlKGRpc2NhcmRDZWxscykKY29sRGF0YShzY2UpJGRpc2NhcmRDZWxscyA8LSBkaXNjYXJkQ2VsbHMKCiMgdmlzdWFsaXplIGNlbGxzIHRvIGJlIHJlbW92ZWQKcGxvdENvbERhdGEoc2NlLCB4ID0gImRldGVjdGVkIiwgeT0ic3Vic2V0c19NaXRvX3BlcmNlbnQiLCBjb2xvdXJfYnkgPSAiZGlzY2FyZENlbGxzIikKcGxvdENvbERhdGEoc2NlLCB4ID0gInN1bSIsIHk9ImRldGVjdGVkIiwgY29sb3VyX2J5PSJkaXNjYXJkQ2VsbHMiKQpgYGAKCmBgYHtyfQojIHZpc3VhbGl6ZSBjZWxscyB0byBiZSByZW1vdmVkCnBsb3RDb2xEYXRhKHNjZSwgeCA9ICJkZXRlY3RlZCIsIHk9InN1YnNldHNfTWl0b19wZXJjZW50IiwgY29sb3VyX2J5ID0gImRvbm9yIikKcGxvdENvbERhdGEoc2NlLCB4ID0gInN1bSIsIHk9ImRldGVjdGVkIiwgY29sb3VyX2J5PSJkb25vciIpCmBgYAoKYGBge3J9CiMgdmlzdWFsaXplIGNlbGxzIHRvIGJlIHJlbW92ZWQKcGxvdENvbERhdGEoc2NlLCB4ID0gImRldGVjdGVkIiwgeT0ic3Vic2V0c19NaXRvX3BlcmNlbnQiLCBjb2xvdXJfYnkgPSAiZXhwZXJpbWVudCIpCnBsb3RDb2xEYXRhKHNjZSwgeCA9ICJzdW0iLCB5PSJkZXRlY3RlZCIsIGNvbG91cl9ieT0iZXhwZXJpbWVudCIpCmBgYAoKYGBge3J9CnRhYmxlKHNjZSRkb25vciwgc2NlJGRpc2NhcmRDZWxscykKdGFibGUoc2NlJGRvbm9yLCBzY2UkZGlzY2FyZENlbGxzKS9yb3dTdW1zKHRhYmxlKHNjZSRkb25vciwgc2NlJGRpc2NhcmRDZWxscykpCiNmcmFjdGlvbnMgb2YgcmVtb3ZlZCBjZWxscyBwZXIgZG9ub3IKYGBgCgpNb3N0IHJlbW92ZWQgY2VsbHMgKGZyYWN0aW9uKSBhcmUgZnJvbSBwYXRpZW50cyBgZGl4aGAgYW5kIGBiYWJ6YC4KCmBgYHtyfQp0YWJsZShzY2UkZXhwZXJpbWVudCwgc2NlJGRpc2NhcmRDZWxscykKdGFibGUoc2NlJGV4cGVyaW1lbnQsIHNjZSRkb25vcikKYGBgCgpNb3N0IGxvdyBsaWJyYXJ5IHNpemVzIHNlZW0gdG8gY29tZSBmcm9tIHBhdGllbnQgYGRpeGhgOyBmb3IgcGF0aWVudCBgYmFiemAKdGhlIGVmZmVjdCBpcyBsZXNzIHByb25vdW5jZWQuCgpgYGB7cn0KcGxvdENvbERhdGEoc2NlWyxzY2UkZG9ub3I9PSJkaXhoIl0sIHggPSAic3VtIiwgeT0iZGV0ZWN0ZWQiKQpwbG90Q29sRGF0YShzY2VbLHNjZSRkb25vcj09ImJhYnoiXSwgeCA9ICJzdW0iLCB5PSJkZXRlY3RlZCIpCmBgYAoKQXMgc3VjaCwgd2UgYXJlIG1haW5seSByZW1vdmluZyBjZWxscyBmcm9tIHNwZWNpZmljIHBhdGllbnRzIGFuZCB0aGUgcmVzcGVjdGl2ZQpiYXRjaGVzIGluIHdoaWNoIHRoZXkgd2VyZSBzZXF1ZW5jZWQuIEhvd2V2ZXIsIHdlIHdhbnQgdG8gYmUgY2FyZWZ1bDsgd2Ugb25seQp3YW50IHRvIHJlbW92ZSB0ZWNobmljYWwgYXJ0ZWZhY3RzLCB3aGlsZSByZXRhaW5pbmcgYXMgbXVjaCBvZiB0aGUgYmlvbG9neSBhcwpwb3NzaWJsZS4gSW4gb3VyIGV4cGxvcmF0b3J5IGZpZ3VyZSwgd2Ugc2VlIHRoYXQgdGhlIGNlbGxzIHdlIGFyZSByZW1vdmluZyBiYXNlZApvbiB0aGUgbnVtYmVyIG9mIGdlbmVzIGRldGVjdGVkLCBhcmUgcXVpdGUgZmFyIGFwYXJ0IGZyb20gdGhlIGJ1bGsgb2YgdGhlIGRhdGEKY2xvdWQ7IGFzIHN1Y2gsIHRoZXNlIGNlbGxzIG1heSBiZSBjb25zaWRlcmVkIHN1c3BpY2lvdXMuIEZvciB0aGUgY3JpdGVyaW9uIG9mCmxpYnJhcnkgc2l6ZSwgd2Ugc2VlIHRoYXQgdGhlIGNlbGxzIHJlbW92ZWQgdGhlcmUgYXJlIHN0aWxsIHN0cm9uZ2x5IGNvbm5lY3RlZAp0byB0aGUgZGF0YSBjbG91ZC4gQXMgc3VjaCwgd2UgbWF5IHdhbnQgdG8gcmVsYXggdGhlIGZpbHRlcmluZyBjcml0ZXJpb24gdGhlcmUgYQpsaXR0bGUgYml0LiBXaGVuIHdlIHRoaW5rIG9mIGhvdyB0aGUgYWRhcHRpdmUgdGhyZXNob2xkIHN0cmF0ZWd5IHdvcmtzLCB3ZQptYXkgd2FudCB0byByZW1vdmUgY2VsbHMgdGhhdCBhcmUgNE1BRHMgYXdheSBmcm9tIHRoZSBjZW50ZXIsIHJhdGhlciB0aGFuCnRoZSBkZWZhdWx0IDMgTUFEcy4KCmBgYHtyfQojIHByZXZpb3VzbHkKbG93TGliIDwtIGlzT3V0bGllcihkZiRzdW0sIHR5cGU9Imxvd2VyIiwgbG9nPVRSVUUpCnRhYmxlKGxvd0xpYikKCiMgYWZ0ZXIgc2VlaW5nIGFwcHJvcHJpYXRlIGV4cGxvcmF0b3J5IGZpZ3VyZQpsb3dMaWIgPC0gaXNPdXRsaWVyKGRmJHN1bSwgbm1hZHM9NCwgdHlwZT0ibG93ZXIiLCBsb2c9VFJVRSkKdGFibGUobG93TGliKQoKZGlzY2FyZENlbGxzIDwtIChsb3dMaWIgfCBsb3dGZWF0dXJlcyB8IGhpZ2hNaXRvKQp0YWJsZShkaXNjYXJkQ2VsbHMpCmNvbERhdGEoc2NlKSRkaXNjYXJkQ2VsbHMgPC0gZGlzY2FyZENlbGxzCmBgYAoKTm90ZSB0aGF0IHRoZXNlIHN0ZXBzIGFyZSBub3QgZXhhY3Q7IGRpZmZlcmVudCBhbmFseXN0cyB3aWxsIGFycml2ZSB0byBkaWZmZXJlbnQKZmlsdGVyaW5nIGNyaXRlcmlhIGZvciBtYW55IG9mIHRoZSBzdGVwcy4gVGhlIGtleSBpZGVhcyBhcmUgdGhhdAp3ZSBsZXQgYXBwcm9wcmlhdGUgZXhwbG9yYXRvcnkgZmlndXJlcyBndWlkZSB1cyB0byBtYWtlIHJlYXNvbmFibGUgY2hvaWNlczsKaS5lLiwgd2UgbG9vayBhdCB0aGUgZGF0YSByYXRoZXIgdGhhbiBibGluZGx5IGZvbGxvd2luZyBhIHN0YW5kYXJkaXplZCBwaXBlbGluZQp0aGF0IG1heSB3b3JrIHdlbGwgaW4gbWFueSBjYXNlcywgYnV0IG1heWJlIG5vdCBvdXIgcGFydGljdWxhciBkYXRhc2V0LgoKYGBge3J9CiMgcmVtb3ZlIGNlbGxzIGlkZW50aWZpZWQgdXNpbmcgYWRhcHRpdmUgdGhyZXNob2xkcwpzY2UgPC0gc2NlWywgIWNvbERhdGEoc2NlKSRkaXNjYXJkQ2VsbHNdCmBgYAoKIyBOb3JtYWxpemF0aW9uCgpGb3Igbm9ybWFsaXphdGlvbiwgdGhlIHNpemUgZmFjdG9ycyAkc19pJCBjb21wdXRlZCBoZXJlIGFyZSBzaW1wbHkgc2NhbGVkIApsaWJyYXJ5IHNpemVzOgoKXFsgTl9pID0gXHN1bV9nIFlfe2dpfSBcXQpcWyBzX2kgPSBOX2kgLyBcYmFye059X2kgXF0KCmBgYHtyfQpzY2UgPC0gbG9nTm9ybUNvdW50cyhzY2UpCgojIG5vdGUgd2UgYWxzbyByZXR1cm5lZCBsb2cgY291bnRzOiBzZWUgdGhlIGFkZGl0aW9uYWwgbG9nY291bnRzIGFzc2F5LgpzY2UKCiMgeW91IGNhbiBleHRyYWN0IHNpemUgZmFjdG9ycyB1c2luZwpzZiA8LSBsaWJyYXJ5U2l6ZUZhY3RvcnMoc2NlKQptZWFuKHNmKSAjIGVxdWFsIHRvIDEgZHVlIHRvIHNjYWxpbmcuCnBsb3QoeD0gbG9nKGNvbFN1bXMoYXNzYXlzKHNjZSkkY291bnRzKSksIAogICAgIHk9c2YpCmBgYAoKLS0tCgotLS0gZW5kIGxhYiBzZXNzaW9uIDEgLS0tCgotLS0KCgojIEZlYXR1cmUgc2VsZWN0aW9uCgojIyBIaWdobHkgdmFyaWFibGUgZ2VuZXMKCmBgYHtyfQpsaWJyYXJ5KHNjcmFuKQpyb3duYW1lcyhzY2UpIDwtIHJvd0RhdGEoc2NlKSRFbnNlbWJsCmRlYyA8LSBtb2RlbEdlbmVWYXIoc2NlKQpoZWFkKGRlYykKYGBgCgpgYGB7cn0KZml0IDwtIG1ldGFkYXRhKGRlYykKcGxvdChmaXQkbWVhbiwgZml0JHZhciwgCiAgICAgeGxhYj0iTWVhbiBvZiBsb2ctZXhwcmVzc2lvbiIsCiAgICB5bGFiPSJWYXJpYW5jZSBvZiBsb2ctZXhwcmVzc2lvbiIpCmN1cnZlKGZpdCR0cmVuZCh4KSwgY29sPSJkb2RnZXJibHVlIiwgYWRkPVRSVUUsIGx3ZD0yKQpgYGAKCmBgYHtyfQojIGdldCB0b3AgMTAwMCBoaWdobHkgdmFyaWFibGUgZ2VuZXMKaHZnIDwtIGdldFRvcEhWR3MoZGVjLCAKICAgICAgICAgICAgICAgICAgbj0xMDAwKQpoZWFkKGh2ZykKCiMgcGxvdCB0aGVzZSAKcGxvdChmaXQkbWVhbiwgZml0JHZhciwgCiAgICAgY29sID0gYygib3JhbmdlIiwgImRhcmtzZWFncmVlbjMiKVsobmFtZXMoZml0JG1lYW4pICVpbiUgaHZnKSsxXSwKICAgICB4bGFiPSJNZWFuIG9mIGxvZy1leHByZXNzaW9uIiwKICAgIHlsYWI9IlZhcmlhbmNlIG9mIGxvZy1leHByZXNzaW9uIikKY3VydmUoZml0JHRyZW5kKHgpLCBjb2w9ImRvZGdlcmJsdWUiLCBhZGQ9VFJVRSwgbHdkPTIpCmxlZ2VuZCgidG9wbGVmdCIsIAogICAgICAgbGVnZW5kID0gYygiU2VsZWN0ZWQiLCAiTm90IHNlbGVjdGVkIiksIAogICAgICAgY29sID0gYygiZGFya3NlYWdyZWVuMyIsICJvcmFuZ2UiKSwKICAgICAgIHBjaCA9IDE2LAogICAgICAgYnR5PSduJykKYGBgCgojIERpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbgoKIyMgTGluZWFyIGRpbWVuc2lvbmFsaXR5IHJlZHVjdGlvbjogUENBIHdpdGggZmVhdHVyZSBzZWxlY3Rpb24KCmBgYHtyfQpzZXQuc2VlZCgxMjM0KQpzY2UgPC0gcnVuUENBKHNjZSwgCiAgICAgICAgICAgICAgbmNvbXBvbmVudHM9MzAsIAogICAgICAgICAgICAgIHN1YnNldF9yb3c9aHZnKQpwbG90UENBKHNjZSwgCiAgICAgICAgY29sb3VyX2J5ID0gImRheSIpCmBgYAoKUENBIGhhcyBiZWVuIHBlcmZvcm1lZC4gVGhlIFBDQSBpbmZvcm1hdGlvbiBoYXMgYmVlbiBhdXRvbWF0aWNhbGx5IHN0b3JlZCBpbiB0aGUKYHJlZHVjZWREaW1gIHNsb3Qgb2YgdGhlIGBTaW5nbGVDZWxsRXhwZXJpbWVudGAgb2JqZWN0LgoKYGBge3J9CnJlZHVjZWREaW1OYW1lcyhzY2UpCmBgYAoKYGBge3J9CmhlYWQocmVkdWNlZERpbShzY2UsCiAgICAgICAgICAgdHlwZT0iUENBIikpCmBgYAoKVGhlIGBwbG90UENBYCBmdW5jdGlvbiBvZiB0aGUgYHNjYXRlcmAgcGFja2FnZSBub3cgYWxsb3dzIHVzIHRvIHZpc3VhbGl6ZQp0aGUgY2VsbHMgaW4gUENBIHNwYWNlLCBiYXNlZCBvbiB0aGUgUENBIGluZm9ybWF0aW9uIHN0b3JlZCBpbiBvdXIgb2JqZWN0OgoKYGBge3J9CnBsb3RQQ0Eoc2NlLCAKICAgICAgICBjb2xvdXJfYnkgPSAiZGF5IikKYGBgCgpXZSBzZWUgdGhhdCBmb3IgdGhpcyBkYXRhc2V0LCBQQ0EgaXMgYWJsZSB0byBkaXN0aW5ndWlzaCBiZXR3ZWVuIHRoZSBkaWZmZXJlbnQKZGV2ZWxvcG1lbnRhbCBzdGFnZXMgcXVpdGUgd2VsbC4KCiMjIEEgZ2VuZXJhbGl6YXRpb24gb2YgUENBIGZvciBleHBvbmVudGlhbCBmYW1pbHkgZGlzdHJpYnV0aW9ucy4KCmBgYHtyLCBldmFsPVRSVUV9CmxpYnJhcnkoZ2xtcGNhKQpzZXQuc2VlZCgyMTExMDMpCnBvaXBjYSA8LSBnbG1wY2EoWSA9IGFzc2F5cyhzY2UpJGNvdW50c1todmcsXSwKICAgICAgICAgICAgICAgICBMID0gMiwgCiAgICAgICAgICAgICAgICAgZmFtID0gInBvaSIsCiAgICAgICAgICAgICAgICAgbWluaWJhdGNoID0gInN0b2NoYXN0aWMiKQpyZWR1Y2VkRGltKHNjZSwgIlBvaVBDQSIpIDwtIHBvaXBjYSRmYWN0b3JzCnBsb3RSZWR1Y2VkRGltKHNjZSwgCiAgICAgICAgICAgICAgIGRpbXJlZD0iUG9pUENBIiwKICAgICAgICAgICAgICAgY29sb3VyX2J5ID0gImRheSIpCmBgYAoKVXNpbmcgYGdsbXBjYWAsIHdlIG9ic2VydmUgYSBzaW1pbGFyIHJlZHVjZWQgZGltZW5zaW9uIHBsb3QgYXMgZm9yIHRoZSBjbGFzc2ljYWwgUENBIGFwcHJvYWNoLAp3aXRoIHJlYXNvbmFibGUgc2VwYXJhdGlvbiBiZXR3ZWVuIGNlbGxzIG9mIGRpZmZlcmVudCBkZXZlbG9wbWVudGFsIHN0YWdlcy4KCiMjIE5vbi1saW5lYXIgZGltZW5zaW9uYWxpdHkgcmVkdWN0aW9uOiBULVNORQoKYGBge3J9CnNldC5zZWVkKDg3NzgpCnNjZSA8LSBydW5UU05FKHNjZSwgCiAgICAgICAgICAgICAgIGRpbXJlZCA9ICdQQ0EnLAogICAgICAgICAgICAgICBleHRlcm5hbF9uZWlnaGJvcnM9VFJVRSkKcGxvdFRTTkUoc2NlLAogICAgICAgICBjb2xvdXJfYnkgPSAiZGF5IikKYGBgCgpJbiB0aGlzIDJEIHQtU05FIHNwYWNlLCBpdCBpcyBjbGVhciB0aGF0IGNlbGxzIG9mIGRpZmZlcmVudCBkZXZlbG9wbWVudGFsIHN0YWdlcwpjbHVzdGVyIHNlcGFyYXRlbHkuIEhvd2V2ZXIsIHRoZXJlIGFwcGVhcnMgdG8gYmUgc29tZQpoZXRlcm9nZW5laXR5LiBXZSBvYnNlcnZlIG11bHRpcGxlIGNsdXN0ZXJzIG9mIGNlbGxzIApzYW1wbGVkIGF0IHRoZSBzYW1lIHRpbWUgcG9pbnQuIEluIGFkZGl0aW9uLCB3aGlsZSBzdGlsbCBjbHVzdGVyaW5nIHNlcGFyYXRlbHksCnNvbWUgY2x1c3RlcnMgb2YgY2VsbHMgb2YgZGlmZmVyZW50IHRpbWUgcG9pbnRzIGFyZSBzdGlsbCB2ZXJ5IGNsb3NlIHRvZ2V0aGVyIGluIDJEIHNwYWNlLgoKV2Ugd2lsbCBleHBsb3JlIHRoaXMgcGhlbm9tZW5vbiBpbiBtb3JlIGRldGFpbCBsYXRlci4KCiMjIE5vbi1saW5lYXIgZGltZW5zaW9uYWxpdHkgcmVkdWN0aW9uOiBVTUFQCgpgYGB7cn0Kc2V0LnNlZWQoNjUxODcpCnNjZSA8LSBydW5VTUFQKHNjZSwgCiAgICAgICAgICAgICAgIGRpbXJlZCA9ICJQQ0EiLAogICAgICAgICAgICAgICBtaW5fZGlzdCA9IDAuNCwKICAgICAgICAgICAgICAgbl9kaW1yZWQgPSAxMiwKICAgICAgICAgICAgICAgZXh0ZXJuYWxfbmVpZ2hib3JzID0gVFJVRSkKCnBsb3RVTUFQKHNjZSwKICAgICAgICAgY29sb3VyX2J5ID0gImRheSIpCmBgYAoKV2Ugb2JzZXJ2ZSBhIHZlcnkgc2ltaWxhciBwYXR0ZXJuIGFzIGZvciB0aGUgdC1TTkUgYWJvdmUgaW4gdGhpcyBVTUFQOyAKY2VsbHMgb2YgZGlmZmVyZW50IGRldmVsb3BtZW50YWwgc3RhZ2VzIGNsdXN0ZXIgc2VwYXJhdGVseSwgaG93ZXZlciwgdGhlcmUgCnNlZW1zIHRvIGJlIGFuIGFkZGl0aW9uYWwgbGV2ZWwgb2YgaGV0ZXJvZ2VuZWl0eSBpbiB0aGUgZGF0YS4KCi0tLQoKLS0tIGVuZCBsYWIgc2Vzc2lvbiAyIC0tLQoKLS0tCgojIEJhdGNoIGNvcnJlY3Rpb24KCiMjIE9ic2VydmVkIHBhdGllbnQvZXhwZXJpbWVudCBlZmZlY3QKCkluIHRoaXMgZXhwZXJpbWVudCwgb3VyIG1haW4gaW50ZXJlc3QgaXMgdG8gc3R1ZHkgdGhlIGVuZG9kZXJtIGRpZmZlcmVudGlhdGlvbgpwcm9jZXNzLCBpLmUuIHRoZSA0LWRheSBkaWZmZXJlbnRpYXRpb24gcHJvY2VzcyBvZiBpbmR1Y2VkIHBsdXJpcG90ZW50IHN0ZW0gCmNlbGxzIChpUFNDcykgYXQgZGF5MCwgdmlhIG1lc2VuZG9kZXJtIGNlbGxzIChkYXkxKSBhbmQgYW5vdGhlciBpbnRlcm1lZGlhdGUgCnN0YWdlIChkYXkyKSB0byBlbmRvZGVybSBjZWxscyAoZGF5MykuCgpIb3dldmVyLCB3ZSB3aWxsIG5lZWQgdG8gYWNjb3VudCBmb3IgdGhlIGZhY3QgdGhhdCB0aGUgY2VsbHMgaGF2ZSBiZWVuIHNhbXBsZWQKZnJvbSAxNSBkaWZmZXJlbnQgc3ViamVjdCwgdGh1cyBpbnRyb2R1Y2luZyBhZGRpdGlvbmFsIGJpb2xvZ2ljYWwgaGV0ZXJvZ2VuZWl0eS4KVGhlcmUgYXJlIHR3byB2YXJpYWJsZXMgaW4gdGhlIGBjb2xEYXRhYCBvZiBvdXIgYFNpbmdsZUNlbGxFeHBlcmltZW50YCBvYmplY3QKdGhhdCBhcmUgdXNlZnVsIGZvciBleHBsb3JpbmcgdGhpczoKCmBgYHtyfQp0YWJsZShzY2UkZG9ub3Isc2NlJGV4cGVyaW1lbnQpCmBgYAoKV2UgaGF2ZSBjZWxscyBmcm9tIDE1IGRpZmZlcmVudCBwYXRpZW50cyBhbmQgMTQgZGlmZmVyZW50ICJleHBlcmltZW50cyIgCig9IHNlcXVlbmNpbmcgYmF0Y2hlcykuCgpXZSBub3cgd2lsbCBhc3Nlc3MgaWYgdGhpcyBhZGRpdGlvbmFsIHNvdXJjZSBvZiBoZXRlcm9nZW5laXR5IGlzIGFsc28KcGlja2VkIHVwIGluIHRoZSByZWR1Y2VkIGRpbWVuc2lvbiBwbG90LgoKYGBge3J9CiMgdGltZSBlZmZlY3QgaW4gUENBIHNwYWNlLCBhbGwgdGltZSBwb2ludHMKcGxvdFBDQShzY2UsCiAgICAgICAgY29sb3VyX2J5ID0gImRheSIpCgojIGRvbm9yIChudWlzYW5jZSkgZWZmZWN0IGluIFBDQSBzcGFjZSwgYWxsIHRpbWUgcG9pbnRzCnBsb3RQQ0Eoc2NlLAogICAgICAgIGNvbG91cl9ieSA9ICJkb25vciIpCgojIGV4cGVyaW1lbnQgKG51aXNhbmNlKSBlZmZlY3QgaW4gUENBIHNwYWNlLCBhbGwgdGltZSBwb2ludHMKcGxvdFBDQShzY2UsCiAgICAgICAgY29sb3VyX2J5ID0gImV4cGVyaW1lbnQiKQpgYGAKCldlIHNlZSB0aGF0IHdpdGhpbiBhIGNlcnRhaW4gdGltZSBwb2ludCwgY2VsbHMgb2YgdGhlIHNhbWUgcGF0aWVudC9leHBlcmltZW50CnNlZW0gdG8gY2x1c3RlciB0b2dldGhlciBhdCBsZWFzdCB0byBzb21lIGV4dGVudC4gVGhpcyBlZmZlY3QgYmVjb21lcyBjbGVhcmVyCndoZW4gd2UgdmlzdWFsaXplIHRoZSBkYXRhIG9mIHRoZSBkaWZmZXJlbnQgdGltZSBwb2ludHMgc2VwYXJhdGVseS4KCmBgYHtyfQojIGRvbm9yIGVmZmVjdCBpbiBQQ0Egc3BhY2UsIHBlciB0aW1lIHBvaW50CnBsb3RQQ0Eoc2NlWyxzY2UkZGF5PT0iZGF5MCJdLCAKICAgICAgICBjb2xvdXJfYnkgPSAiZG9ub3IiKQpwbG90UENBKHNjZVssc2NlJGRheT09ImRheTEiXSwgCiAgICAgICAgY29sb3VyX2J5ID0gImRvbm9yIikKcGxvdFBDQShzY2VbLHNjZSRkYXk9PSJkYXkyIl0sIAogICAgICAgIGNvbG91cl9ieSA9ICJkb25vciIpCnBsb3RQQ0Eoc2NlWyxzY2UkZGF5PT0iZGF5MyJdLCAKICAgICAgICBjb2xvdXJfYnkgPSAiZG9ub3IiKQpgYGAKCkFuYWxvZ291c2x5LCB3ZSBtYXkgaW5zcGVjdCB0aGUgZWZmZWN0IG9mIHBhdGllbnQgYW5kIGV4cGVyaW1lbnQgaW4gdGhlIFVNQVAKdmlzdWFsaXphdGlvbiB3ZSBjcmVhdGVkIGVhcmxpZXIuCgpgYGB7cn0KIyB0aW1lIGVmZmVjdApwbG90VU1BUChzY2UsCiAgICAgICAgIGNvbG91cl9ieSA9ICJkYXkiKQoKIyBudWlzYW5jZSBlZmZlY3RzIGluIFVNQVAgc3BhY2UsIGFsbCB0aW1lIHBvaW50cwpwbG90VU1BUChzY2UsCiAgICAgICAgIGNvbG91cl9ieSA9ICJkb25vciIpCgpwbG90VU1BUChzY2UsCiAgICAgICAgIGNvbG91cl9ieSA9ICJleHBlcmltZW50IikKYGBgCgpBcyBleHBlY3RlZCwgd2Ugc2VlIHRoYXQgdGhlIGFkZGl0aW9uYWwgaGV0ZXJvZ2VuZWl0eSBvYnNlcnZlZCBpbiB0aGUgY2x1c3RlcnMKY29sb3JlZCBiYXNlZCBvbiB0aGUgdGltZSBwb2ludHMgY2FuIGJlIGV4cGxhaW5lZCBieSB0aGUgcGF0aWVudCBlZmZlY3RzLgoKSW4gdGhpcyBleHBlcmltZW50LCB0aGUgcHJpbWFyeSBpbnRlcmVzdCBhcmUgdGhlIGNoYW5nZXMgaW4gZ2VuZSBleHByZXNzaW9uIAphY3Jvc3MgdGhlIGZvdXIgZGF5cywgcmVmbGVjdGluZyBkaWZmZXJlbnRpYXRpb24gZnJvbSBpbmR1Y2VkIHBsdXJpcG90ZW50IHN0ZW0gCmNlbGxzIHRvIGVuZG9kZXJtIGNlbGxzLiBJbiBjb250cmFzdCwgdGhlIGJldHdlZW4tcGF0aWVudCBlZmZlY3RzIGFyZSBub3Qgb2YKaW50ZXJlc3QgaGVyZS4gVXNpbmcgYmF0Y2ggY29ycmVjdGlvbiwgd2Ugd2lsbCBhaW0gdG8gImNvcnJlY3QiIGZvciB0aGUgZG9ub3IgCmVmZmVjdHMsIHdoaWxlIGhvcGVmdWxseSByZXRhaW5pbmcgdGhlIG1haW4gYmlvbG9naWNhbCB2YXJpYXRpb24gb2YgaW50ZXJlc3QhCgpXZSB3aWxsIGV4cGxvcmUgdHdvIHBvcHVsYXIgc3RyYXRlZ2llcyBmb3IgYmF0Y2ggY29ycmVjdGlvbiBmb3Igc2NSTkEtU2VxIGRhdGE6CioqU2V1cmF0IENDQSoqIGFuZCAqKkhhcm1vbnkqKi4KCiMjIFNldXJhdCBDQ0EgYmF0Y2ggY29ycmVjdGlvbgoKV2Ugd2lsbCBmaXJzdCBpbnRlZ3JhdGUgdGhlIGRhdGEgYWNyb3NzIHRoZSBkaWZmZXJlbnQgZG9ub3JzIHVzaW5nIGBTZXVyYXRgLiAKVGhpcyBwcm9jZWR1cmUgaXMgaW1wbGVtZW50ZWQgdG8gaW50ZWdyYXRlIGRhdGFzZXRzL2JhdGNoZXMgaW4gYSBwYWlyd2lzZSAKZmFzaGlvbi4gSW4gdGhlIGNhc2Ugb2YgbXVsdGlwbGUgYmF0Y2hlcy9kYXRhc2V0cywgaXQgaW50ZWdyYXRlcyB0aGVtIGluIGEgCmJvdHRvbS11cCBzdHJhdGVneSwgc3RhcnRpbmcgd2l0aCBpbnRlZ3JhdGluZyBwYWlyd2lzZSBzYW1wbGVzIGZpcnN0LiBCZWNhdXNlIG9mCnRoaXMsIGJlbG93LCB3ZSB3aWxsIGludHJvZHVjZSB0aGUgbWV0aG9kb2xvZ3kgZm9yIHR3byBiYXRjaGVzL2RhdGFzZXRzLCBidXQgCm5vdGUgdGhhdCBhbiBhbmFsb2dvdXMgcHJvY2VkdXJlIGlzIGFwcGxpZWQgaW4gdGhlIGNhc2Ugb2YgbXVsdGlwbGUgCmJhdGNoZXMvZGF0YXNldHMuCgpUaGUgYFNldXJhdGAgbWV0aG9kIHdpbGwgZmlyc3QgcGVyZm9ybSBmZWF0dXJlIHNlbGVjdGlvbiB0byBpZGVudGlmeSBmZWF0dXJlcyAKdGhhdCBhcmUgaW5mb3JtYXRpdmUgaW4gYWxsIGRhdGFzZXRzLiBVc2luZyB0aGVzZSBmZWF0dXJlcywgaXQgd2lsbCBwZXJmb3JtIGEgCmNhbm9uaWNhbCBjb3JyZWxhdGlvbiBhbmFseXNpczsgYSBkaW1lbnNpb25hbGl0eSByZWR1Y3Rpb24gdGVjaG5pcXVlIHRoYXQgCmZvY3Vzc2VzIG9uIHNoYXJlZCB2YXJpYXRpb24gYmV0d2VlbiBkYXRhc2V0cy9iYXRjaGVzLiBUaGUgQ0NBIGRpbWVuc2lvbnMgbWF5IApiZSB2aWV3ZWQgYXMgZ2VuZSBtb2R1bGVzIHRoYXQgYXJlIHByZXNlbnQgaW4gZWFjaCBkYXRhc2V0LiBXaXRoaW4gdGhpcyBzaGFyZWQgCnNwYWNlLCBpdCBpZGVudGlmaWVzICoqYW5jaG9yIGNlbGxzKiogKG9uZSBmb3IgZWFjaCBkb25vciwgaW4gb3VyIGNhc2UpLiBUaGVzZSAKYW5jaG9yIGNlbGxzIG1heSBiZSBjb25zaWRlcmVkIGFzIGNlbGxzIHNoYXJpbmcgdGhlIHNhbWUgYmlvbG9naWNhbCBzdGF0ZSwgYW5kIApzeXN0ZW1hdGljIGRpZmZlcmVuY2VzIGJldHdlZW4gdGhlbSBjb3JyZXNwb25kIHRvIGJhdGNoL2RhdGFzZXQtc3BlY2lmaWMgCmVmZmVjdHMuIEEgY29ycmVjdGlvbiBvbiB0aGUgb3JpZ2luYWwgZ2VuZSBleHByZXNzaW9uIG1hdHJpeCBpcyB0aGVuIGFwcGxpZWQgYnkgCmNvbnNpZGVyaW5nIHN5c3RlbWF0aWMgZGlmZmVyZW5jZXMgYWNyb3NzIGFsbCBhbmNob3IgY2VsbHMgaWRlbnRpZmllZCBmb3IgZWFjaCAKcGFpciBvZiBiYXRjaGVzL2RhdGFzZXRzLgoKYGBge3IsIHdhcm5pbmc9RkFMU0UsIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkoU2V1cmF0KQpzZXVyYXRfb2JqIDwtIGFzLlNldXJhdChzY2UpCnNldXJhdF9vYmoKYGBgCgpJbiB0aGUgY29kZSBjaHVuayBiZWxvdywgSSByZW1vdmUgY2VsbHMgZm9yIHBhdGllbnRzIHRoYXQgaGF2ZSBsZXNzIG9yIGVxdWFsIHRoYW4gCjMwIGNlbGxzLiBJZiB3ZSBkbyBub3QgZG8gdGhpcywgd2Ugd2lsbCBnZXQgaXNzdWVzIGRvd25zdHJlYW0gd2l0aCB0aGUgU2V1cmF0CmZ1bmN0aW9ucyBgRmluZEludGVncmF0aW9uQW5jaG9yc2AgYW5kIGBJbnRlZ3JhdGVEYXRhYCwgd2hpY2ggYnJlYWsgZG93bgp3aGVuIHRoZSBudW1iZXIgb2YgY2VsbHMgcGVyIGJhdGNoIGlzIHNtYWxsLiBUaGlzIGlzIGEga25vd24gaXNzdWUKCi0gaHR0cHM6Ly9naXRodWIuY29tL3NhdGlqYWxhYi9zZXVyYXQvaXNzdWVzLzM5MzAKLSBodHRwczovL2dpdGh1Yi5jb20vc2F0aWphbGFiL3NldXJhdC9pc3N1ZXMvNDgwMwotIGh0dHBzOi8vZ2l0aHViLmNvbS9zYXRpamFsYWIvc2V1cmF0L2lzc3Vlcy80ODEyCi0gaHR0cHM6Ly9naXRodWIuY29tL2Nhcm1vbmFsYWIvU1RBQ0FTL2lzc3Vlcy8xMgoKYW5kIHRoZSBwYWNrYWdlIG1haW50YWluZXJzIHN1Z2dlc3QgdG8gZWl0aGVyIHJlbW92ZSBvciBtYW51YWxseSBtZXJnZSBzbWFsbApiYXRjaGVzIHRvZ2V0aGVyLiBXZSB3aWxsIGhlcmUgc2ltcGx5IHJlbW92ZSB0aGUgY2VsbHMgb2YgcGF0aWVudCAiYmV6aSIuCgpgYGB7cn0KdGFibGUoc2V1cmF0X29iaiRkb25vcikKdGFibGUoc2V1cmF0X29iaiRkb25vcilbdGFibGUoc2V1cmF0X29iaiRkb25vcikgPD0gMzBdCnNldXJhdF9vYmogPC0gc2V1cmF0X29ialssLXdoaWNoKHNldXJhdF9vYmokZG9ub3IgPT0gbmFtZXModGFibGUoc2V1cmF0X29iaiRkb25vcilbdGFibGUoc2V1cmF0X29iaiRkb25vcikgPD0gMzBdKSldCmBgYAoKQWZ0ZXIgdGhpcywgdGhlIGBTcGxpdE9iamVjdGAgb2JqZWN0IGZ1bmN0aW9uIGlzIHVzZWQgdG8gZ2VuZXJhdGUgYSBsaXN0IG9mCmBTZXVyYXRgIG9iamVjdHMsIHdoZXJlIGVhY2ggbGlzdCBlbGVtZW50cyBob2xkIHRoZSBkYXRhIG9mIDEgYmF0Y2ggKHBhdGllbnQpOgoKYGBge3J9CnNldXJhdF9vYmoubGlzdCA8LSBTcGxpdE9iamVjdChzZXVyYXRfb2JqLCBzcGxpdC5ieSA9ICJkb25vciIpCm5sZXZlbHMoYXMuZmFjdG9yKHNjZSRkb25vcikpICMgb3JpZ2luYWxseSAxNSBwYXRpZW50cwpsZW5ndGgoc2V1cmF0X29iai5saXN0KSAjIDE0IHBhdGllbnRzIGxlZnQKYGBgCgpOZXh0LCBTZXVyYXQgd2lsbCBwZXJmb3JtIHRoZSBmb2xsb3dpbmcgc3RlcHMgZm9yIGJhdGNoIGNvcnJlY3Rpb246CgotIGBOb3JtYWxpemVEYXRhYDogYnkgZGVmYXVsdCwgdGFrZXMgdGhlIGNvdW50IGFzc2F5IG9mIHRoZSBgU2V1cmF0YCBvYmplY3QgYW5kCnBlcmZvcm1zIGEgbG9nLXRyYW5zZm9ybWF0aW9uLCByZXN1bHRpbmcgaW4gYW4gYWRkaXRpb25hbCBsb2ctdHJhbnNmb3JtZWQgYXNzYXkuClRoaXMgaXMgcGVyZm9ybWVkIGZvciBlYWNoIGJhdGNoIHNlcGFyYXRlbHkuCgotIGBGaW5kVmFyaWFibGVGZWF0dXJlc2A6IEZlYXR1cmUgc2VsZWN0aW9uLCB1c2luZyB0aGUgdmFyaWFuY2Utc3RhYmlsaXppbmcKdHJhbnNmb3JtYXRpb24gKFZTVCkgZnJvbSBgU2V1cmF0YCwgd2hpY2ggYW1vdW50cyB0byBjYWxjdWxhdGluZyBQZWFyc29uCnJlc2lkdWFscyBmcm9tIGEgcmVndWxhcml6ZWQgbmVnYXRpdmUgYmlub21pYWwgcmVncmVzc2lvbiBtb2RlbCwgd2l0aCBzZXF1ZW5jaW5nIApkZXB0aCBhcyBhIGNvdmFyaWF0ZS4gVGhpcyBpcyBwZXJmb3JtZWQgZm9yIGVhY2ggYmF0Y2ggc2VwYXJhdGVseS4KCi0gYFNlbGVjdEludGVncmF0aW9uRmVhdHVyZXNgOiBDaG9vc2UgdGhlIGZlYXR1cmVzIHRvIHVzZSB3aGVuIGludGVncmF0aW5nIAptdWx0aXBsZSBkYXRhc2V0cyBvciBiYXRjaGVzLiBUaGlzIGZ1bmN0aW9uIHJhbmtzIGZlYXR1cmVzIGJ5IHRoZSBudW1iZXIgb2YgCmJhdGNoZXMgdGhleSBhcmUgZGVlbWVkIHZhcmlhYmxlIGluLCBicmVha2luZyB0aWVzIGJ5IHRoZSBtZWRpYW4gdmFyaWFibGUgCmZlYXR1cmUgcmFuayBhY3Jvc3MgZGF0YXNldHMuIEl0IHJldHVybnMgdGhlIHRvcCBzY29yaW5nIGZlYXR1cmVzIGJ5IHRoaXMgCnJhbmtpbmcsIHdoaWNoIGFyZSB0aGVuIHVzZWQgaW4gdGhlIHN0ZXBzIGJlbG93LgoKLSBgRmluZEludGVncmF0aW9uQW5jaG9yc2A6IEZvciBlYWNoIHBhaXIgb2YgZGF0YXNldHMgd2Ugd2FudCB0byBpbnRlZ3JhdGUsIHdlIAppZGVudGlmeSBhbmNob3IgY2VsbHMsIG9uZSBmcm9tIGVhY2ggZGF0YXNldCwgdGhhdCBhcmUgYXNzdW1lZCB0byBzaGFyZSBhIApzaW1pbGFyIGJpb2xvZ2ljYWwgc3RhdGUuIEFuY2hvciBjZWxscyBhcmUgaWRlbnRpZmllZCBhcyBtdXR1YWwgbmVhcmVzdCAKbmVpZ2hib3JzIGluIHRoZSBzaGFyZWQgY2Fub25pY2FsIGNvcnJlbGF0aW9uIGFuYWx5c2lzIHNwYWNlLiBBbmNob3IgY2VsbHMgYXJlIAphbHNvIHNjb3JlZCBhbmQgd2VpZ2h0ZWQgYWNjb3JkaW5nIHRvIHRoZWlyIHF1YWxpdHkuCgotIGBJbnRlZ3JhdGVEYXRhYDogQW5jaG9yIGNlbGxzIGFyZSB1c2VkIHRvIGNhbGN1bGF0ZSBhICdjb3JyZWN0ZWQnIGRhdGEgbWF0cml4LApyZW1vdmluZyBzeXN0ZW1hdGljIGRpZmZlcmVuY2VzIGJldHdlZW4gYW5jaG9yIGNlbGxzLiBUaGlzIGNyZWF0ZXMgYW4gCmBpbnRlZ3JhdGVkYCBhc3NheSBpbiB0aGUgYFNldXJhdGAgb2JqZWN0IGNvbnRhaW5pbmcgdGhpcyBjb3JyZWN0ZWQgZGF0YSBtYXRyaXgsIAp3aGljaCBtYXkgdGhlbiBiZSB1c2VkIGZvciBkb3duc3RyZWFtIHZpc3VhbGl6YXRpb24gYW5kIGFuYWx5c2lzIGFzIHN1Y2guCgpgYGB7ciwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GQUxTRX0KIyBOb3JtYWxpemUgYW5kIGlkZW50aWZ5IHZhcmlhYmxlIGZlYXR1cmVzIGZvciBlYWNoIGRhdGFzZXQgKHBhdGllbnQpIGluZGVwZW5kZW50bHkKc2V1cmF0X29iai5saXN0IDwtIGxhcHBseShYID0gc2V1cmF0X29iai5saXN0LCBGVU4gPSBmdW5jdGlvbih4KSB7CiAgICB4IDwtIE5vcm1hbGl6ZURhdGEoeCx2ZXJib3NlID0gRkFMU0UpCiAgICB4IDwtIEZpbmRWYXJpYWJsZUZlYXR1cmVzKHgsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzZWxlY3Rpb24ubWV0aG9kID0gInZzdCIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBuZmVhdHVyZXMgPSAxMDAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2ZXJib3NlID0gRkFMU0UpCn0pCgojIFNlbGVjdCBmZWF0dXJlcyB0aGF0IGFyZSByZXBlYXRlZGx5IHZhcmlhYmxlIGFjcm9zcyBkYXRhc2V0cyBmb3IgaW50ZWdyYXRpb24KZmVhdHVyZXMgPC0gU2VsZWN0SW50ZWdyYXRpb25GZWF0dXJlcyhvYmplY3QubGlzdCA9IHNldXJhdF9vYmoubGlzdCkKCiMgSW5kZW50aWZ5IHBhaXJzIG9mIGNlbGxzIHdpdGggc2ltaWxhciBiaW9sb2dpY2FsIHN0YXRlCmFuY2hvcnMgPC0gRmluZEludGVncmF0aW9uQW5jaG9ycyhvYmplY3QubGlzdCA9IHNldXJhdF9vYmoubGlzdCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhbmNob3IuZmVhdHVyZXMgPSBmZWF0dXJlcywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlcmJvc2UgPSBGQUxTRSkKCiMgVGhpcyBjb21tYW5kIGNyZWF0ZXMgYW4gJ2ludGVncmF0ZWQnIGRhdGEgYXNzYXkuIFdlIGhhdmUgc2V0IHRoZSBgay53ZWlnaHRgIAojIGFyZ3VtZW50LCB3aGljaCBzcGVjaWZpZXMgdGhlIE51bWJlciBvZiBuZWlnaGJvcnMgdG8gY29uc2lkZXIgd2hlbiB3ZWlnaHRpbmcgCiMgYW5jaG9ycywgdG8gMzAgKGRlZmF1bHQgaXMgMTAwKS4gVGhpcyB3YXMgbmVjZXNzYXJ5IHRvIGF2b2lkIGVycm9ycywgc2luY2Ugd2UKIyBoYXZlIG1hbnkgYmF0Y2hlcyB3aXRoIGxlc3MgdGhhbiAxMDAgY2VsbHMuCmRhdGEuY29tYmluZWQgPC0gSW50ZWdyYXRlRGF0YShhbmNob3JzZXQgPSBhbmNob3JzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgay53ZWlnaHQgPSAzMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHZlcmJvc2U9RkFMU0UpCgpkYXRhLmNvbWJpbmVkCmBgYAoKTm93LCB3ZSBoYXZlIGEgbmV3IGBTZXVyYXRgIG9iamVjdCwgd2hpY2ggYWdhaW4gaXMgYSBzaW5nbGUgb2JqZWN0IChub3QgYSBsaXN0KQpzdG9yaW5nIHRoZSBleHByZXNzaW9uIHZhbHVlcyBvZiBhbGwgY2VsbHMgKiphZnRlciBiYXRjaCBjb3JyZWN0aW9uKiouIE5vdGUgdGhhdAp0aGUgb3JpZ2luYWwgZXhwcmVzc2lvbiB2YWx1ZXMgYXJlIHN0aWxsIHByZXNlbnQgaW4gdGhlICpvcmlnaW5hbGV4cCogYXNzYXkgb2YKdGhlIG9iamVjdC4KCkZpbmFsbHksIHdlIG1heSB1c2UgYFNldXJhdGAgZnVuY3Rpb25zIGZvciBwZXJmb3JtaW5nIGRpbWVuc2lvbiByZWR1Y3Rpb24gYW5kCnZpc3VhbGl6YXRpb24gb2YgdGhlIGJhdGNoIGNvcnJlY3RlZCBkYXRhLgoKYGBge3J9CiMgUnVuIHRoZSBzdGFuZGFyZCBTZXVyYXQgd29ya2Zsb3cgZm9yIHZpc3VhbGl6YXRpb24gYW5kIGNsdXN0ZXJpbmcKCiMgU3RlcCAxOiBTY2FsZXMgYW5kIGNlbnRlcnMgZmVhdHVyZXMgaW4gdGhlIGRhdGFzZXQsIHByaW9yIHN0ZXAgdG8gUENBCmRhdGEuY29tYmluZWQgPC0gU2NhbGVEYXRhKG9iamVjdCA9IGRhdGEuY29tYmluZWQsIAogICAgICAgICAgICAgICAgICAgICAgICAgICB2ZXJib3NlID0gRkFMU0UpCgojIFN0ZXAgMjogUGVyZm9ybSBQQ0EgdG8gMzAgZGltZW5zaW9ucwpkYXRhLmNvbWJpbmVkIDwtIFJ1blBDQShvYmplY3QgPSBkYXRhLmNvbWJpbmVkLCAKICAgICAgICAgICAgICAgICAgICAgICAgbnBjcyA9IDMwLAogICAgICAgICAgICAgICAgICAgICAgICByZWR1Y3Rpb24ubmFtZSA9ICJQQ0FfU2V1QmF0Y2giLAogICAgICAgICAgICAgICAgICAgICAgICB2ZXJib3NlID0gRkFMU0UpCgojIFN0ZXAgMzogUGVyZm9ybSBVTUFQIG9uIHRoZSBmaXJzdCAxMiBwcmluY2lwYWwgY29tcG9uZW50cwpkYXRhLmNvbWJpbmVkIDwtIFJ1blVNQVAob2JqZWN0ID0gZGF0YS5jb21iaW5lZCwgCiAgICAgICAgICAgICAgICAgICAgICAgICByZWR1Y3Rpb24gPSAiUENBX1NldUJhdGNoIiwKICAgICAgICAgICAgICAgICAgICAgICAgIHJlZHVjdGlvbi5uYW1lID0gIlVNQVBfU2V1QmF0Y2giLAogICAgICAgICAgICAgICAgICAgICAgICAgZGltcyA9IDE6MTIsCiAgICAgICAgICAgICAgICAgICAgICAgICB2ZXJib3NlID0gRkFMU0UpCgojIFVNQVAgdmlzdWFsaXphdGlvbgpwMSA8LSBEaW1QbG90KG9iamVjdCA9IGRhdGEuY29tYmluZWQsIAogICAgICAgICAgICAgIHJlZHVjdGlvbiA9ICJVTUFQX1NldUJhdGNoIiwgCiAgICAgICAgICAgICAgZ3JvdXAuYnkgPSAiZGF5IikKCnAyIDwtIERpbVBsb3Qob2JqZWN0ID0gZGF0YS5jb21iaW5lZCwgCiAgICAgICAgICAgICAgcmVkdWN0aW9uID0gIlVNQVBfU2V1QmF0Y2giLCAKICAgICAgICAgICAgICBncm91cC5ieSA9ICJkb25vciIpCnAxICsgcDIKYGBgCgpBbHRlcm5hdGl2ZWx5LCB3ZSBjYW4gdHJhbnNmb3JtIHRoZSBgU2V1cmF0YCBvYmplY3QgYmFjayB0byBhIApgU2luZ2xlQ2VsbEV4cGVyaW1lbnRgIG9iamVjdCBhbmQgZ2VuZXJhdGUgdGhlIHZpc3VhbGl6YXRpb25zIHVzaW5nIHRoZSAKQmlvY29uZHVjdG9yIGZ1bmN0aW9ucyB0aGF0IHdlIHVzZWQgcHJldmlvdXNseToKCmBgYHtyfQojIENvbnZlcnQgU2V1cmF0IG9iamVjdCB0byBTaW5nbGVDZWxsRXhwZXJpbWVudCBvYmplY3QKc2NlX2ludFNldXJhdCA8LSBhcy5TaW5nbGVDZWxsRXhwZXJpbWVudChkYXRhLmNvbWJpbmVkKQoKIyBVTUFQIHdpdGhvdXQgU2V1cmF0IGJhdGNoIGNvcnJlY3Rpb24KcDEgPC0gcGxvdFVNQVAoc2NlLAogICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZGF5IikgKyBnZ3RpdGxlKCJEYXkgLSBubyBiYXRjaCIpCnAyIDwtIHBsb3RVTUFQKHNjZSwKICAgICAgICAgICAgICAgY29sb3VyX2J5ID0gImRvbm9yIikgKyBnZ3RpdGxlKCJEb25vciAtIG5vIGJhdGNoIikKCiMgVU1BUCB3aXRoIFNldXJhdCBiYXRjaCBjb3JyZWN0aW9uCnNjZV9pbnRTZXVyYXQgPC0gcnVuVU1BUChzY2VfaW50U2V1cmF0LCAKICAgICAgICAgICAgICAgICAgICAgICAgIGRpbXJlZCA9ICdQQ0FfU0VVQkFUQ0gnLAogICAgICAgICAgICAgICAgICAgICAgICAgbWluX2Rpc3QgPSAwLjQsCiAgICAgICAgICAgICAgICAgICAgICAgICBuX2RpbXJlZCA9IDEyLAogICAgICAgICAgICAgICAgICAgICAgICAgZXh0ZXJuYWxfbmVpZ2hib3JzID0gVFJVRSkKCnAzIDwtIHBsb3RVTUFQKHNjZV9pbnRTZXVyYXQsCiAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJkYXkiKSArIGdndGl0bGUoIkRheSAtIHdpdGggYmF0Y2giKQpwNCA8LSBwbG90VU1BUChzY2VfaW50U2V1cmF0LAogICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZG9ub3IiKSArIGdndGl0bGUoIkRvbm9yIC0gd2l0aCBiYXRjaCIpCgpwMSArIHAzCgpwMiArIHA0CmBgYAoKVGhlIGJhdGNoIGNvcnJlY3Rpb24gc2VlbXMgdG8gaGF2ZSB3b3JrZWQgdmVyeSB3ZWxsLiBCb3RoIHdpdGggYW5kIHdpdGhvdXQKYmF0Y2ggY29ycmVjdGlvbiwgd2Ugb2JzZXJ2ZSB0aGF0IGNlbGxzIG9mIHRoZSBzYW1lIHRpbWUgcG9pbnQgY2x1c3RlciB0b2dldGhlci4KQnV0IHdoZW4gbm8gYmF0Y2ggY29ycmVjdGlvbiBpcyBwZXJmb3JtZWQsIHRoZXJlIHNlZW1zIHRvIGJlIGFuIGFkZGl0aW9uYWwgbGV2ZWwKb2YgdmFyaWFiaWxpdHkgaW4gdGhlIGRhdGEuCgpXaGVuIHdlIGNvbG9yIHRoZSBjZWxscyBiYXNlZCBvbiB0aGUgZG9ub3IgdmFyaWFibGUsIHdlIHNlZSB0aGF0IHdpdGhvdXQgYmF0Y2ggCmNvcnJlY3Rpb24gY2VsbHMgb2YgdGhlIHNhbWUgZG9ub3IgY2x1c3RlciB0b2dldGhlci4gQWZ0ZXIgYmF0Y2ggY29ycmVjdGlvbiwKc3VjaCBkb25vciBlZmZlY3RzIHNlZW0gdG8gYmUgbm8gbG9uZ2VyIHByZXNlbnQuCgpBbHNvIG5vdGUgdGhhdCB3aGlsZSBiYXRjaCBjb3JyZWN0aW9uIHJlbW92ZSB0aGUgYmV0d2Vlbi1kb25vciB2YXJpYWJpbGl0eSwKdGhlIGJldHdlZW4tZGF5IHZhcmlhYmlsaXR5IHRoYXQgaXMgb2YgaW50ZXJlc3QgaXMgc3RpbGwgcHJlc2VydmVkLiBBcyBzdWNoLApiYXNlZCBvbiBvdXIgdmlzdWFsaXphdGlvbnMsIGl0IGxvb2tzIGxpa2UgdGhlIGJhdGNoIGNvcnJlY3Rpb24gZGlkIG5vdCAKb3ZlcmNvcnJlY3QgYW5kIHN1Y2NlZWRlZCBpbiByZW1vdmluZyBvbmx5IHRoZSB1bndhbnRlZCB2YXJpYXRpb24gaW4gdGhlIGRhdGEuCgojIyBIYXJtb255IGJhdGNoIGNvcnJlY3Rpb24KCltIYXJtb255XShodHRwczovL3d3dy5uYXR1cmUuY29tL2FydGljbGVzL3M0MTU5Mi0wMTktMDYxOS0wKSBpbXBsZW1lbnRzIGEgCmNvbXBsZXggZGF0YSBpbnRlZ3JhdGlvbiBzdHJhdGVneSwgd2hlcmUgY2VsbHMgYXJlIGZpcnN0IGNsdXN0ZXJlZCB1c2luZyBhIAonaGlnaC1kaXZlcnNpdHkgY2x1c3RlcmluZycsIGZhdm9yaW5nIGNsdXN0ZXJzIGNvbnNpc3Rpbmcgb2YgbXVsdGlwbGUgCmJhdGNoZXMvZGF0YXNldHMsIGFuZCB0aGVuIGJhdGNoIGVmZmVjdHMgYXJlIGNvcnJlY3RlZCB3aXRoaW4gZWFjaCBjbHVzdGVyIAp1c2luZyBhIGxpbmVhciBjb3JyZWN0aW9uIHRlcm0uIEl0IGl0ZXJhdGVzIGFjcm9zcyB0aGVzZSBzdGVwcyB1bnRpbCBubyBjaGFuZ2UgCmlzIGNsdXN0ZXJpbmcgaXMgb2JzZXJ2ZWQuCgpQZXJmb3JtaW5nIGJhdGNoIGNvcnJlY3Rpb24gd2l0aCBgaGFybW9ueWAgaXMgdmVyeSBzaW1wbGU7IHdlIG9ubHkgbmVlZCBhIHNpbmdsZQpmdW5jdGlvbiBjYWxsIGFuZCBjYW4gZGlyZWN0bHkgd29yayB3aXRoIG91ciBgU2luZ2xlQ2VsbEV4cGVyaW1lbnRgIG9iamVjdC4KClRoZSBmdW5jdGlvbiBgUnVuSGFybW9ueWAgdGFrZXMgdGhlIGZvbGxvd2luZyBpbnB1dHM6CgotIGBvYmplY3RgOiBuYW1lIG9mIHRoZSBgU2luZ2xlQ2VsbEV4cGVyaW1lbnRgIG9iamVjdAoKLSBgZ3JvdXAuYnkudmFyc2A6IHRoZSBuYW1lcyBvZiB0aGUgdmFyaWFibGVzIGZvciB3aGljaCB3ZSB3YW50IHRvIHBlcmZvcm0gYmF0Y2gKY29ycmVjdGlvbi4gQ29udmVuaWVudGx5LCB0aGlzIGNhbiBiZSBtdWx0aXBsZSB2YXJpYWJsZXMsIHNvIHdlIGNhbiBjb3JyZWN0IGJvdGgKZm9yIGRvbm9yIGFuZCBleHBlcmltZW50IGVmZmVjdHMgKHNpbmNlIHRoZSBjb3JyZXNwb25kZW5jZSBiZXR3ZWVuIHRoZSB0d28gd2FzCm5vdCBwZXJmZWN0KQoKLSBgcmVkdWN0aW9uYDogTmFtZSBvZiB0aGUgcHJldmlvdXNseSBjb21wdXRlZCByZWR1Y2VkIGRpbWVuc2lvbiBzcGFjZSBvbiB3aGljaApiYXRjaCBjb3JyZWN0aW9uIHdpbGwgYmUgcGVyZm9ybWVkIChub3Qgb24gcmF3IGRhdGEgdG8gaW1wcm92ZSBzaWduYWwtdG8tbm9pc2UKcmF0aW8pLiBUeXBpY2FsbHkgUENBIGlzIHVzZWQKCi0gYHJlZHVjdGlvbi5zYXZlYDogbmFtZSB0byBzdG9yZSB0aGUgYmF0Y2ggY29ycmVjdGVkIGRpbWVuaW9uIHJlZHVjZWQgc3BhY2UKCi0gYHZlcmJvc2VgOiBwcmludCBwcm9ncmVzcyBvciBub3QuCgpgYGB7cn0KbGlicmFyeShoYXJtb255KQoKc2V0LnNlZWQoNjg0ODY0KQpzY2UgPC0gaGFybW9ueTo6UnVuSGFybW9ueShvYmplY3QgPSBzY2UsIAogICAgICAgICAgICAgICAgICAgICAgICAgICBncm91cC5ieS52YXJzCT0gYygiZG9ub3IiLCAiZXhwZXJpbWVudCIpLAogICAgICAgICAgICAgICAgICAgICAgICAgICByZWR1Y3Rpb24gPSAiUENBIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVkdWN0aW9uLnNhdmUgPSAiSEFSTU9OWV9kb25vcl9leHBlcmltZW50IiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IEZBTFNFKQpgYGAKClRoZSBvdXRwdXQgaXMgYW4gYWRkaXRpb25hbCBlbGVtZW50IGluIHRoZSByZWR1Y2VkIGRpbWVuc2lvbiBzcGFjZToKCmBgYHtyfQpyZWR1Y2VkRGltKHNjZSwgdHlwZT0iUENBIilbMTo1LDE6Ml0KcmVkdWNlZERpbShzY2UsIHR5cGU9IkhBUk1PTllfZG9ub3JfZXhwZXJpbWVudCIpWzE6NSwxOjJdCmBgYAoKZm9yIHdoaWNoIHRoZSB2YWx1ZXMgZGlmZmVyIGFzIGNvbXBhcmVkIHRvIHRoZSBvcmlnaW5hbCBQQ0EgY29vcmRpbmF0ZXMuIFRoaXMKaXMgYSBjb25zZXF1ZW5jZSBvZiB0aGUgYmF0Y2ggY29ycmVjdGlvbi4KCmBgYHtyfQpwbG90UmVkdWNlZERpbShvYmplY3QgPSBzY2UsCiAgICAgICAgICAgICAgIGRpbXJlZCA9ICJQQ0EiLAogICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZGF5IikKCnBsb3RSZWR1Y2VkRGltKG9iamVjdCA9IHNjZSwKICAgICAgICAgICAgICAgZGltcmVkID0gIkhBUk1PTllfZG9ub3JfZXhwZXJpbWVudCIsCiAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJkYXkiKQpgYGAKCldoZW4gY29sb3Jpbmcgb24gZGF5LCBib3RoIHBsb3RzIGxvb2sgdmVyeSBzaW1pbGFyLgoKYGBge3J9CnBsb3RSZWR1Y2VkRGltKG9iamVjdCA9IHNjZSwKICAgICAgICAgICAgICAgZGltcmVkID0gIlBDQSIsCiAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJkb25vciIpCgpwbG90UmVkdWNlZERpbShvYmplY3QgPSBzY2UsCiAgICAgICAgICAgICAgIGRpbXJlZCA9ICJIQVJNT05ZX2Rvbm9yX2V4cGVyaW1lbnQiLAogICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZG9ub3IiKQpgYGAKClRoaXMgZmlndXJlIGlzIHRvbyBjbHV0dGVyZWQgdG8gc2VlIHRoZSBkb25vciBlZmZlY3RzLiBCZWxvdywgd2UgdGhlcmVmb3JlCmdlbmVyYXRlIGEgc2VwYXJhdGUgZmlndXJlIGZvciBlYWNoIHRpbWUgcG9pbnQuCgpgYGB7ciwgZmlnLmhlaWdodD0xMCwgZmlnLndpZHRoPTR9CiMgd2l0aG91dCBiYWN0aCBjb3JyZWN0aW9uCnAxIDwtIHBsb3RSZWR1Y2VkRGltKG9iamVjdCA9IHNjZSwKICAgICAgICAgICAgICAgICAgICAgZGltcmVkID0gIlBDQSIsCiAgICAgICAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJkb25vciIpCgpwMSArIGZhY2V0X3dyYXAofnNjZSRkYXksIG5jb2w9MSkKYGBgCgpFc3BlY2lhbGx5IGZvciB0aW1lIHBvaW50cyBkYXkwIGFuZCBkYXkxLCB3ZSBvYnNlcnZlIGNsZWFyIGRvbm9yIGVmZmVjdHMuCgpgYGB7ciwgZmlnLmhlaWdodD0xMCwgZmlnLndpZHRoPTR9CiMgaGFybW9ueSBiYXRjaCBjb3JyZWN0aW9uCnAyIDwtIHBsb3RSZWR1Y2VkRGltKG9iamVjdCA9IHNjZSwKICAgICAgICAgICAgICAgICAgICAgZGltcmVkID0gIkhBUk1PTllfZG9ub3JfZXhwZXJpbWVudCIsCiAgICAgICAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJkb25vciIpCgpwMiArIGZhY2V0X3dyYXAofnNjZSRkYXksIG5jb2w9MSkKYGBgCgpBZnRlciBiYXRjaCBjb3JyZWN0aW9uIHdpdGggaGFybW9ueSwgdGhlIGRvbm9yIGVmZmVjdHMgYXJlIGxhcmdlbHkgcmVtb3ZlZC4KCldoZW4gdXNpbmcgVU1BUCB2aXN1YWxpemF0aW9uLCB0aGUgZGlzY3JlcGFuY3kgYmV0d2VlbiB0aGUgdW5jb3JyZWN0ZWQgYW5kCmJhdGNoIGNvcnJlY3RlZCBkYXRhIGJlY29tZXMgZXZlbiBjbGVhcmVyOgoKYGBge3J9CiMgbWFrZSBVTUFQIHNwYWNlIGJhc2VkIG9uIGJhdGNoLWNvcnJlY3RlZCBQQ0EgZGF0YQpzY2UgPC0gcnVuVU1BUChzY2UsIAogICAgICAgICAgICAgICBkaW1yZWQgPSAnSEFSTU9OWV9kb25vcl9leHBlcmltZW50JywKICAgICAgICAgICAgICAgbl9kaW1yZWQgPSAxMiwKICAgICAgICAgICAgICAgbWluX2Rpc3QgPSAwLjQsCiAgICAgICAgICAgICAgIGV4dGVybmFsX25laWdoYm9ycz1UUlVFLAogICAgICAgICAgICAgICBuYW1lID0gIlVNQVBfSEFSTU9OWV9kb25vcl9leHBlcmltZW50IikKYGBgCgpgYGB7cn0KIyBObyBiYXRjaCB2ZXJzdXMgYmF0Y2ggY29ycmVjdGVkLCBjb2xvciBieSBkYXkKcDEgPC0gcGxvdFJlZHVjZWREaW0oc2NlLAogICAgICAgICAgICAgICAgICAgICBkaW1yZWQgPSAiVU1BUCIsCiAgICAgICAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJkYXkiKSArIGdndGl0bGUoIkRheSAtIG5vIGJhdGNoIikKCnAyIDwtIHBsb3RSZWR1Y2VkRGltKHNjZSwKICAgICAgICAgICAgICAgICAgICAgZGltcmVkID0gIlVNQVBfSEFSTU9OWV9kb25vcl9leHBlcmltZW50IiwKICAgICAgICAgICAgICAgICAgICAgY29sb3VyX2J5ID0gImRheSIpICsgZ2d0aXRsZSgiRGF5IC0gYmF0Y2giKQpwMSArIHAyCgojIE5vIGJhdGNoIHZlcnN1cyBiYXRjaCBjb3JyZWN0ZWQsIGNvbG9yIGJ5IGRvbm9yCnAzIDwtIHBsb3RSZWR1Y2VkRGltKHNjZSwKICAgICAgICAgICAgICAgICAgICAgZGltcmVkID0gIlVNQVAiLAogICAgICAgICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZG9ub3IiKSArIGdndGl0bGUoIkRvbm9yIC0gbm8gYmF0Y2giKQoKcDQgPC0gcGxvdFJlZHVjZWREaW0oc2NlLAogICAgICAgICAgICAgICAgICAgICBkaW1yZWQgPSAiVU1BUF9IQVJNT05ZX2Rvbm9yX2V4cGVyaW1lbnQiLAogICAgICAgICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZG9ub3IiKSArIGdndGl0bGUoIkRvbm9yIC0gYmF0Y2giKQpwMyArIHA0CgojIE5vIGJhdGNoIHZlcnN1cyBiYXRjaCBjb3JyZWN0ZWQsIGNvbG9yIGJ5IGV4cGVyaW1lbnQKcDUgPC0gcGxvdFJlZHVjZWREaW0oc2NlLAogICAgICAgICAgICAgICAgICAgICBkaW1yZWQgPSAiVU1BUCIsCiAgICAgICAgICAgICAgICAgICAgIGNvbG91cl9ieSA9ICJleHBlcmltZW50IikgKyBnZ3RpdGxlKCJFeHBlcmltZW50IC0gbm8gYmF0Y2giKQoKcDYgPC0gcGxvdFJlZHVjZWREaW0oc2NlLAogICAgICAgICAgICAgICAgICAgICBkaW1yZWQgPSAiVU1BUF9IQVJNT05ZX2Rvbm9yX2V4cGVyaW1lbnQiLAogICAgICAgICAgICAgICAgICAgICBjb2xvdXJfYnkgPSAiZXhwZXJpbWVudCIpICsgZ2d0aXRsZSgiRXhwZXJpbWVudCAtIGJhdGNoIikKcDUgKyBwNgpgYGAKCldlIGhlcmUgc2hvdyB0aGUgVU1BUCB2aXN1YWxpemF0aW9ucyBjb21wYXJpbmcgbm9uLWNvcnJlY3RlZCB2ZXJzdXMgdGhlIGJhdGNoCmNvcnJlY3RlZCBkYXRhLCB3aXRoIGNlbGxzIGNvbG9yZWQgYmFzZWQgb24gZGF5LCBkb25vciBhbmQgZXhwZXJpbWVudC4gVGhlCmludGVycHJldGF0aW9uIGlzIGFuYWxvZ291cyB0byB0aGUgaW50ZXJwcmV0YXRpb24gYWJvdmUgZm9yIHRoZSBTZXVyYXQKYmF0Y2ggY29ycmVjdGlvbjoKClRoZSBiYXRjaCBjb3JyZWN0aW9uIHNlZW1zIHRvIGhhdmUgd29ya2VkIHZlcnkgd2VsbC4gQm90aCB3aXRoIGFuZCB3aXRob3V0CmJhdGNoIGNvcnJlY3Rpb24sIHdlIG9ic2VydmUgdGhhdCBjZWxscyBvZiB0aGUgc2FtZSB0aW1lIHBvaW50IGNsdXN0ZXIgdG9nZXRoZXIuCkJ1dCB3aGVuIG5vIGJhdGNoIGNvcnJlY3Rpb24gaXMgcGVyZm9ybWVkLCB0aGVyZSBzZWVtcyB0byBiZSBhbiBhZGRpdGlvbmFsIGxldmVsCm9mIHZhcmlhYmlsaXR5IGluIHRoZSBkYXRhLgoKV2hlbiB3ZSBjb2xvciB0aGUgY2VsbHMgYmFzZWQgb24gdGhlIGRvbm9yL2V4cGVyaW1lbnQgdmFyaWFibGUsIHdlIHNlZSB0aGF0CndpdGhvdXQgYmF0Y2ggY29ycmVjdGlvbiBjZWxscyBvZiB0aGUgc2FtZSBkb25vciBjbHVzdGVyIHRvZ2V0aGVyLiBBZnRlciAKYmF0Y2ggY29ycmVjdGlvbiwgc3VjaCBkb25vci9leHBlcmltZW50IGVmZmVjdHMgc2VlbSB0byBiZSBubyBsb25nZXIgcHJlc2VudC4KCkFsc28gbm90ZSB0aGF0IHdoaWxlIGJhdGNoIGNvcnJlY3Rpb24gcmVtb3ZlIHRoZSBiZXR3ZWVuLWRvbm9yL2V4cGVyaW1lbnQgCnZhcmlhYmlsaXR5LCB0aGUgYmV0d2Vlbi1kYXkgdmFyaWFiaWxpdHkgdGhhdCBpcyBvZiBpbnRlcmVzdCBpcyBzdGlsbCBwcmVzZXJ2ZWQuIApBcyBzdWNoLCBiYXNlZCBvbiBvdXIgdmlzdWFsaXphdGlvbnMsIGl0IGxvb2tzIGxpa2UgdGhlIGJhdGNoIGNvcnJlY3Rpb24gZGlkIG5vdCAKb3ZlcmNvcnJlY3QgYW5kIHN1Y2NlZWRlZCBpbiByZW1vdmluZyBvbmx5IHRoZSB1bndhbnRlZCB2YXJpYXRpb24gaW4gdGhlIGRhdGEuCgojIENsdXN0ZXJpbmcKCkluIHRoZSBzZWNvbmQgbGFiIHNlc3Npb24sIHdlIGRpc2N1c3NlZCBncmFwaC1iYXNlZCBjbHVzdGVyaW5nLCBrLW1lYW5zIApjbHVzdGVyaW5nIGFuZCBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4gSGVyZSwgd2Ugd2lsbCBwZXJmb3JtIGhpZXJhcmNoaWNhbCAKY2x1c3RlcmluZy4KCiMjIEhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nCgpXZSBtYXkgc3BsaXQgdGhlIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHByb2Nlc3MgaW4gdHdvIGludHVpdGl2ZSBzdGVwczoKCjEuIENvbXB1dGUgdGhlIHBhaXJ3aXNlIGRpc3RhbmNlcyBiZXR3ZWVuIGFsbCBjZWxscy4gVGhlc2UgYXJlIGJ5IGRlZmF1bHQKZXVjbGlkZWFuIGRpc3RhbmNlcyBhbmQsIGluIG9yZGVyIHRvIHJlZHVjZSBkYXRhIGNvbXBsZXhpdHkgYW5kIGluY3JlYXNlIHNpZ25hbAp0byBub2lzZSwgd2UgbWF5IHBlcmZvcm0gdGhpcyBvbiB0aGUgdG9wICgzMCkgUEMncy4gSW1wbGVtZW50ZWQgaW4gdGhlIGBkaXN0YApmdW5jdGlvbi4KCjIuIFBlcmZvcm0gYSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBhbmFseXNpcyBvbiB0aGVzZSBkaXN0YW5jZXMuIEluaXRpYWxseSwgCmVhY2ggY2VsbCBpcyBhc3NpZ25lZCB0byBpdHMgb3duIGNsdXN0ZXIgYW5kIHRoZW4gdGhlIAphbGdvcml0aG0gcHJvY2VlZHMgaXRlcmF0aXZlbHksIGF0IGVhY2ggc3RhZ2Ugam9pbmluZyB0aGUgdHdvIG1vc3Qgc2ltaWxhciAKY2x1c3RlcnMsIGNvbnRpbnVpbmcgdW50aWwgdGhlcmUgaXMganVzdCBhIHNpbmdsZSBjbHVzdGVyLiBUaGlzIGlzIGltcGxlbWVudGVkIAppbiB0aGUgYGhjbHVzdGAgZnVuY3Rpb24uCgpOb3RlIHRoYXQgdGhlIGBoY2x1c3RgIGZ1bmN0aW9uIGFsbG93cyBmb3Igc3BlY2lmeWluZyBhIGBtZXRob2RgIGFyZ3VtZW50LgpUaGUgZGlmZmVyZW5jZXMgYmV0d2VlbiB0aGUgZGlmZmVyZW50IG1ldGhvZHMgYXJlIGJleW9uZCB0aGUgc2NvcGUgb2YgdGhpcwpzZXNzaW9uLCBidXQgYSBicmllZiBkZXNjcmlwdGlvbiBpcyBwcm92aWRlZCBpbiB0aGUgZnVuY3Rpb24gaGVscCBmaWxlLgpJbiB0aGUgY29udGV4dCBvZiBzY1JOQS1zZXEsIHdlIGhhdmUgbW9zdGx5IHNlZW4gdGhlIHVzZSBvZiB0aGUgIndhcmQuRDIiCm1ldGhvZC4KCmBgYHtyfQpkaXN0c2NlIDwtIGRpc3QocmVkdWNlZERpbShzY2UsICJIQVJNT05ZX2Rvbm9yX2V4cGVyaW1lbnQiKVssMToxMF0pCmhjbCA8LSBoY2x1c3QoZGlzdHNjZSwgbWV0aG9kID0gIndhcmQuRDIiKQpwbG90KGhjbCwgbGFiZWxzID0gRkFMU0UpCmBgYAoKTmV4dCwgd2UgbmVlZCB0byAiY3V0IHRoZSB0cmVlIiwgaS5lLiwgY2hvb3NlIGF0IHdoaWNoIHJlc29sdXRpb24gd2Ugd2FudCB0bwpyZXBvcnQgdGhlIChjZWxsLXR5cGUpIGNsdXN0ZXJzLiBUaGlzIGNhbiBiZSBhY2hpZXZlZCB3aXRoIHRoZSBgY3V0cmVlYCAKZnVuY3Rpb24uIEFzIGFuIGlucHV0LCBgY3V0cmVlYCB0YWtlcyB0aGUgZGVuZHJvZ3JhbSBmcm9tIHRoZSBgaGNsdXN0YCBmdW5jdGlvbgphbmQgYSB0aHJlc2hvbGQgdmFsdWUgZm9yIGN1dHRpbmcgdGhlIHRyZWUuIFRoaXMgaXMgZWl0aGVyIGBrYCwgdGhlIG51bWJlciBvZgpjbHVzdGVycyB3ZSB3YW50IHRvIHJlcG9ydCwgb3IgYGhgLCB0aGUgaGVpZ2h0IGluIHRoZSBkZW5kcm9ncmFtIGF0IHdoaWNoCndlIHdhbiB0byBjdXQgdGhlIHRyZWUuCgpIZXJlIHdlIGNob29zZSBgayA9IDRgLCBzaW5jZSB3ZSBrbm93IGluIGFkdmFuY2UgdGhhdCB3ZSBleHBlY3QgZm91ciBjbHVzdGVycyBvZgpjZWxscyAoZm91ciB0aW1lIHBvaW50cykuCgpgYGB7cn0KY2x1c3RfaGNsX2s0IDwtIGN1dHJlZShoY2wsIGsgPSA0KQp0YWJsZShjbHVzdF9oY2xfazQpCmBgYAoKTmV4dCwgd2UgdmlzdWFsaXplIHRoZSBkYXRhIGluIFBDQSBzcGFjZSBjb2xvcmVkIGJhc2VkIG9uIHRpbWUgcG9pbnQgYW5kIGJhc2VkCm9uIG91ciBpbmZlcnJlZCBjbHVzdGVyIGxhYmVscy4KCmBgYHtyfQpzY2UkY2x1c3RfaGNsX2s0IDwtIGFzLmZhY3RvcihjbHVzdF9oY2xfazQpCgpwbG90UmVkdWNlZERpbShzY2UsIAogICAgICAgIGRpbXJlZCA9ICJIQVJNT05ZX2Rvbm9yX2V4cGVyaW1lbnQiLAogICAgICAgICBjb2xvdXJfYnkgPSJkYXkiKQpwbG90UmVkdWNlZERpbShzY2UsCiAgICAgICAgZGltcmVkID0gIkhBUk1PTllfZG9ub3JfZXhwZXJpbWVudCIsCiAgICAgICAgY29sb3VyX2J5PSJjbHVzdF9oY2xfazQiKQpgYGAKCldlIHNlZSB0aGF0IG91ciBpbmZlcnJlZCBjbHVzdGVyaW5nIGxhcmdlbHkgY29ycmVzcG9uZHMgd2l0aCB0aGUgb3JpZ2luYWwKZGF5IHZhcmlhYmxlLgoKYGBge3J9CnRhYmxlKHNjZSRkYXksIHNjZSRjbHVzdF9oY2xfazQpCmBgYAoKTWFwcGluZyBjbHVzdGVycyB0byB0aW1lcG9pbnRzLCB3ZSBub3RlIHRoYXQgbW9zdCBjZWxscyBvZiBkYXkwIGFyZSBpbiAKaGllcmFyY2hpY2FsIGNsdXN0ZXIgMyAoYXJiaXRyYXJ5IGluZGljYXRvciksIGRheTEgY2VsbHMgYXJlIGluIGNsdXN0ZXIgNCwgCmRheTIgY2VsbHMgYXJlIG1haW5seSBpbiBjbHVzdGVyIDEgYW5kIGRheTMgY2VsbHMgYXJlIGZvdW5kIGJhY2sgaW4gY2x1c3RlciAyLgoKIyBUcmFqZWN0b3J5IGluZmVyZW5jZQoKVHJhamVjdG9yeSBpbmZlcmVuY2UgaXMgYSBjb21wdXRhdGlvbmFsIHByb2NlZHVyZSB0aGF0IGF0dGVtcHRzIHRvIHN1bW1hcml6ZSAKYSBkeW5hbWljIHByb2Nlc3MgaW4gYSAndHJhamVjdG9yeScuIFRoZSB0cmFqZWN0b3J5IHRyaWVzIHRvIGZpbmQgYSBzZW5zaWJsZSAKb3JkZXJpbmcgb2YgdGhlIGNlbGxzIGFjY29yZGluZyB0byB0aGVpciBwcm9ncmVzc2lvbiB0aHJvdWdoIHRoaXMgZHluYW1pYyAKcHJvY2Vzcy4gVHJhamVjdG9yaWVzIGNhbiBiZSBsaW5lYXIsIGRpdmVyZ2luZywgY29udmVyZ2luZyBvciBjeWNsaWMuIElmIHRoZXJlIAphcmUgbXVsdGlwbGUgZGlmZmVyZW50aWF0aW9uIHBhdGhzLCBlYWNoIHBhdGggaXMgY2FsbGVkIGEgbGluZWFnZSwgYW5kIHRoZSAKY29tYmluYXRpb24gb2YgbGluZWFnZXMgaXMgY2FsbGVkIGEgdHJhamVjdG9yeS4KCkJhc2VkIG9uIHRoZSB0cmFqZWN0b3J5LCBvbmUgbWF5IGRlZmluZSBhICoqcHNldWRvdGltZSoqIGZvciBlYWNoIGNlbGwsIHdoaWNoIApkZWZpbmVzIHRoYXQgY2VsbCdzIHByb2dyZXNzaW9uIGFsb25nIG9uZSBvZiB0aGUgZGlmZmVyZW50aWF0aW9uIHBhdGhzOiBpZiB0aGUgCnBzZXVkb3RpbWUgb2YgYSBjZWxsIGlzIGNsb3NlIHRvIHplcm8sIHRoZW4gdGhhdCBjZWxsIGlzIGNsb3NlIHRvIHRoZSBzdGFydGluZyAKcG9pbnQgb2YgdGhlIHRyYWplY3RvcnkuCgojIyBDb21wdXRpbmcgdGhlIHRyYWplY3RvcnkKCk1hbnkgbWV0aG9kcyBmb3IgZXN0aW1hdGluZyB0cmFqZWN0b3JpZXMgZXhpc3QuIEhlcmUsIHdlIHdpbGwgdXNlIApbc2xpbmdzaG90XShodHRwczovL2Jpb2NvbmR1Y3Rvci5vcmcvcGFja2FnZXMvcmVsZWFzZS9iaW9jL2h0bWwvc2xpbmdzaG90Lmh0bWwpIAp0byBjcmVhdGUgYSB0cmFqZWN0b3J5IGZvciB0aGUgQ3VvbW8gZGF0YXNldC4KCmBgYHtyLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KHNsaW5nc2hvdCkKc2NlIDwtIHNsaW5nc2hvdChzY2UsICMgdGFyZ2V0IG9iamVjdAogICAgICAgICAgICAgICAgIHN0YXJ0LmNsdXMgPSAiMyIsICMgY2x1c3RlciB0aGF0IGNvcnJlc3BvbmRzIHRvIGRheTAgY2VsbHMhCiAgICAgICAgICAgICAgICAgZW5kLmNsdXMgPSAiMiIsICMgY2x1c3RlciB0aGF0IGNvcnJlc3BvbmRzIHRvIGRheTMgY2VsbHMhCiAgICAgICAgICAgICAgICAgY2x1c3RlckxhYmVscyA9ICJjbHVzdF9oY2xfazQiLCAjIGNsdXN0ZXJpbmcgdG8gdXNlIAogICAgICAgICAgICAgICAgIHJlZHVjZWREaW0gPSAiSEFSTU9OWV9kb25vcl9leHBlcmltZW50IikgIyBkaW1yZWQgdG8gdXNlCmBgYAoKIyMgVmlzdWFsaXppbmcgdGhlIHRyYWplY3RvcnkKCmBgYHtyfQpwbG90KHJlZHVjZWREaW1zKHNjZSkkSEFSTU9OWV9kb25vcl9leHBlcmltZW50LCAKICAgICBjb2wgPSBhcy5mYWN0b3Ioc2NlJGNsdXN0X2hjbF9rNCksICMgY29sb3JlZCBhY2NvcmRpbmcgdG8gaW5mZXJyZWQgY2x1c3RlcnMKICAgICBwY2g9MTYsIAogICAgIGFzcCA9IDEpCmxpbmVzKFNsaW5nc2hvdERhdGFTZXQoc2NlKSwgCiAgICAgIGx3ZD0zLCAKICAgICAgdHlwZSA9ICdsaW5lYWdlcycsIAogICAgICBjb2wgPSAnb3JhbmdlJykKYGBgCgpgYGB7cn0KcGxvdChyZWR1Y2VkRGltcyhzY2UpJEhBUk1PTllfZG9ub3JfZXhwZXJpbWVudCwgCiAgICAgY29sID0gYXMuZmFjdG9yKHNjZSRkYXkpLCAjIGNvbG9yZWQgYWNjb3JkaW5nIHRvIG9yaWdpbmFsIHRpbWUgcG9pbnRzCiAgICAgcGNoPTE2LCAKICAgICBhc3AgPSAxKQpsaW5lcyhTbGluZ3Nob3REYXRhU2V0KHNjZSksIAogICAgICBsd2Q9MywgCiAgICAgIGNvbCA9ICdvcmFuZ2UnKQpgYGAKCldlIGNvdWxkIGFsc28gdXNlIGBnZ3Bsb3QyYCBmdW5jdGlvbnMgdG8gb2J0YWluZWQgcHJldHRpZXIgZmlndXJlcyB0aGF0IGFyZQptb3JlIGVhc3kgdG8gYW5ub3RhdGU6CgpgYGB7cn0Kc3VwcHJlc3NQYWNrYWdlU3RhcnR1cE1lc3NhZ2VzKGxpYnJhcnkoZHBseXIpKQoKcmQgPC0gcmVkdWNlZERpbShzY2UsIHR5cGU9IkhBUk1PTllfZG9ub3JfZXhwZXJpbWVudCIpWywxOjJdICMgZXh0cmFjdCBmaXJzdCB0d28gUENzCmNvbG5hbWVzKHJkKSA8LSBjKCJEaW0xIiwgIkRpbTIiKSAjIGdpdmUgY29sdW1uIG5hbWVzCmNsIDwtIHNjZSRjbHVzdF9oY2xfazQgIyBzdG9yZSBjbHVzdGVyaW5nCmRmIDwtIGRhdGEuZnJhbWUocmQsICJjbCIgPSBhcy5jaGFyYWN0ZXIoY2wpKSAjIFBDcyBhbmQgY2x1c3RlcmluZyB0b2dldGhlciBpbiAxIGRhdGEgZnJhbWUKc2RzIDwtIHNsaW5nc2hvdChyZCwgY2wpICMgY29udmVydCBkYXRhIGZyYW1lIHRvIHNsaW5nc2hvdCBvYmplY3QKY3VydmVzIDwtIHNsaW5nQ3VydmVzKHNkcywgYXMuZGYgPSBUUlVFKSAjIG9idGFpbiBzbW9vdGggY3VydmUgZm9yIGxpbmVhZ2VzIChoZXJlIG9ubHkgb25lIGxpbmVhZ2UpCgojIHBsb3QgY2VsbHMgYXMgZG90cyBpbiBkaW1lbnNpb24gcmVkdWNlZCBzcGFjZQpwIDwtIGdncGxvdChkZiwgYWVzKHggPSBEaW0xLCB5ID0gRGltMikpICsKICBnZW9tX3BvaW50KGFlcyhmaWxsID0gY2wpLCBjb2wgPSAiZ3JleTcwIiwgc2hhcGUgPSAyMSkgKyAKICB0aGVtZV9jbGFzc2ljKCkKCiMgYWRkIHNtb290aCBjdXJ2ZXMKcCArIGdlb21fcGF0aChkYXRhID0gY3VydmVzICU+JSBhcnJhbmdlKE9yZGVyKSwKICAgICAgICAgICAgICBhZXMoZ3JvdXAgPSBMaW5lYWdlKSwgc2l6ZSA9IDEuNSkgCgojIGNvbXB1dGUgYW5kIGFkZCBtaW5pbXVtIHNwYW5uaW5nIHRyZWUKbXN0IDwtIHNsaW5nTVNUKHNkcywgYXMuZGYgPSBUUlVFKQpwICsgZ2VvbV9wb2ludChkYXRhID0gbXN0LCBzaXplID0gNCkgKwogIGdlb21fcGF0aChkYXRhID0gbXN0ICU+JSBhcnJhbmdlKE9yZGVyKSwgYWVzKGdyb3VwID0gTGluZWFnZSksIHNpemUgPSAyKQpgYGAKCldlIHNlZSB0aGF0IHRoZSB0cmFqZWN0b3J5IGluZmVycmVkIHdpdGggYHNsaW5nc2hvdGAgbmljZWx5IGNhcHR1cmVzIHRoZQpleHBlY3RlZCBkZXZlbG9wbWVudGFsIHByb2Nlc3MuCgojIERpZmZlcmVudGlhbCBnZW5lIGV4cHJlc3Npb24gdGVzdHMgYWxvbmcgYSB0cmFqZWN0b3J5IHVzaW5nIHRyYWRlU2VxCgpBcyBhIG5leHQgc3RlcCwgd2UgbWF5IGJlIGludGVyZXN0ZWQgaW4gaWRlbnRpZnlpbmcgdGhlIGdlbmVzIGFyZSBpbnZvbHZlZCBpbiAKdGhlIGRldmVsb3BtZW50YWwgcHJvY2Vzcy4gVG8gdGhpcyBlbmQsIG91ciBncm91cCBoYXMgZGV2ZWxvcGVkIHRoZSBCaW9jb25kdWN0b3IKUiBwYWNrYWdlIFt0cmFkZVNlcV0oaHR0cDovL3d3dy5iaW9jb25kdWN0b3Iub3JnL3BhY2thZ2VzL3JlbGVhc2UvYmlvYy9odG1sL3RyYWRlU2VxLmh0bWwpLgpgdHJhZGVTZXFgIGlzIGEgZmxleGlibGUgdG9vbCB0aGF0IGFsbG93cyBmb3Igc3R1ZHlpbmcgZGlmZmVyZW50aWFsIGdlbmUKZXhwcmVzc2lvbiBhbG9uZyBzdWNoIGEgdHJhamVjdG9yeSwgd2l0aGluIG9yIGJldHdlZW4gZGlmZmVyZW50IGxpbmVhZ2VzLgpUaGUgZnVuY3Rpb25hbGl0aWVzIG9mIHRoZSBwYWNrYWdlIGFyZSBzdW1tYXJpemVkIGluIHRoZSBmb2xsb3dpbmcgZmlndXJlOgoKYGBge3J9CmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCIuLy4uL3RyYWRlc2VxX3N1bW1hcnkuanBlZyIpCmBgYAoKYGBge3IsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkodHJhZGVTZXEpCmBgYAoKYHRyYWRlU2VxYCB1c2VzIGEgbmVnYXRpdmUgYmlub21pYWwgZ2VuZXJhbGl6ZWQgYWRkaXRpdmUgbW9kZWwgKE5CLUdBTSkgCmZyYW1ld29yayB0byBzbW9vdGggZWFjaCBnZW5l4oCZcyBleHByZXNzaW9uIGluIGVhY2ggbGluZWFnZS4gU21vb3RoZXJzIGNhbiBiZSAKZGVjb21wb3NlZCBpbnRvIGEgc2V0IG9mIGJhc2lzIGZ1bmN0aW9ucywgd2hpY2ggYXJlIGpvaW5lZCB0b2dldGhlciBhdCBrbm90IApwb2ludHMsIG9mdGVuIHNpbXBseSBjYWxsZWQga25vdHMgKGBrYCkuCgpJZGVhbGx5LCB0aGUgbnVtYmVyIG9mIGtub3RzIHNob3VsZCBiZSBzZWxlY3RlZCB0byByZWFjaCBhbiBvcHRpbWFsIApiaWFzLXZhcmlhbmNlIHRyYWRlLW9mZiBmb3IgdGhlIHNtb290aGVyLCB3aGVyZSBvbmUgZXhwbGFpbnMgYXMgbXVjaCAKdmFyaWFiaWxpdHkgaW4gdGhlIGV4cHJlc3Npb24gZGF0YSBhcyBwb3NzaWJsZSB3aXRoIG9ubHkgYSBmZXcgcmVncmVzc2lvbiAKY29lZmZpY2llbnRzLiBJbiBvcmRlciB0byBndWlkZSB0aGF0IGNob2ljZSwgd2UgZGV2ZWxvcGVkIGRpYWdub3N0aWMgcGxvdHMgCnVzaW5nIHRoZSBBa2Fpa2UgSW5mb3JtYXRpb24gQ3JpdGVyaW9uIChBSUMpLiBUaGlzIGlzIGltcGxlbWVudGVkIGluIHRoZSAKYGV2YWx1YXRlS2AgZnVuY3Rpb24gaW4gYHRyYWRlU2VxYC4KCkhvd2V2ZXIsIGluIHRoZSBbdHJhZGVTZXFdKGh0dHBzOi8vd3d3Lm5hdHVyZS5jb20vYXJ0aWNsZXMvczQxNDY3LTAyMC0xNDc2Ni0zKSAKcHVibGljYXRpb24gdGhlIGF1dGhvcnMgc2hvdyB0aGF0IHRoZSAgYWxnb3JpdGhtIGlzIG5vdCB0b28gc2Vuc2l0aXZlIGZvciB0aGUKbnVtYmVyIG9mIGtub3RzLCBhbmQgdGhhdCB2YWx1ZXMgYmV0d2VlbiA1IGFuZCA5IG9mdGVuIHdvcmsgd2VsbC4gVGhlIGNvZGUKYmVsb3cgd291bGQgYWxsb3cgeW91IHRvIGZpbmQgYSBnb29kIHZhbHVlIGZvciBga2AsIGJ1dCB3ZSB3aWxsIHNpbXBseSB1c2UKdGhlIGRlZmF1bHQgdmFsdWUgb2YgYGsgPSA2YCBkb3duc3RyZWFtLgoKYGBgCiMjIyBGaW5kIGtub3RzCgojIFdlIGZpcnN0IG5lZWQgdG8gZGVjaWRlIG9uIHRoZSBudW1iZXIgb2Yga25vdHMuIFRoaXMgaXMgZG9uZSB1c2luZyB0aGUgIC0tPgojIGBldmFsdWF0ZUtgIGZ1bmN0aW9uLiBUaGlzIHRha2VzIGEgbGl0dGxlIHRpbWUuIC0tPgoKIyB0YWtlcyA5IG1pbnV0ZXMgZm9yIG1lCnNldC5zZWVkKDUpCmljTWF0IDwtIGV2YWx1YXRlSyhjb3VudHMgPSBhc3NheXMoc2NlKSRjb3VudHMsCiAgICAgICAgICAgICAgICAgICBzZHMgPSBzbGluZyRzbGluZ3Nob3QsCiAgICAgICAgICAgICAgICAgICBrID0gMzoxMCwgCiAgICAgICAgICAgICAgICAgICBuR2VuZXMgPSA1MDAsIAogICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IFQpCmBgYAoKIyMgRml0IEdBTQoKV2UgZml0IGEgbmVnYXRpdmUgYmlub21pYWwgZ2VuZXJhbGl6ZWQgYWRkaXRpdmUgbW9kZWwgKE5CLUdBTSksIHNtb290aGluZyBlYWNoIApnZW5l4oCZcyBleHByZXNzaW9uIGFsb25nIHRoZSBkZXZlbG9wbWVudGFsIHRyYWplY3RvcnkuIFdoZW4gbW9kZWxpbmcgYWxsIHRoZSAKZ2VuZXMgKMKxMTAuMDAwKSwgdGhpcyBmdW5jdGlvbiB0YWtlcyBhYm91dCAyMCBtaW51dGVzIHRvIGNvbXBsZXRlLiBGb3IgdGhpcwpsYWIgc2Vzc2lvbiwgd2Ugd2lsbCB0aGVyZWZvcmUgcmFuZG9tbHkgc2FtcGxlIDEuMDAwIGdlbmVzLiBJbiBhZGRpdGlvbiwgd2UgbWFrZQpzdXJlIHRoYXQgdGhyZWUgc3BlY2lmaWMgZ2VuZXMgYXJlIGFsc28gaW5jbHVkZWQ6ICJFTlNHMDAwMDAxMTE3MDQiLCAKIkVOU0cwMDAwMDE2NDQ1OCIgYW5kICJFTlNHMDAwMDAxNDE0NDgiLiBUaGVzZSBnZW5lcyBhcmUga25vd24gbWFya2VycyBmb3IgdGhlIApkaWZmZXJlbnQgZGV2ZWxvcG1lbnRhbCBzdGFnZXMgbmQgd2VyZSB1c2UgaW4gdGhlIHB1YmxpY2F0aW9uIG9mICpDdW9tbyBldCBhbC4qLgoKVGhlIGB0cmFkZVNlcWAgbW9kZWwgYWxsb3dzIHVzIHRvIGluY29ycG9yYXRlIGZpeGVkIGVmZmVjdHMuIFdoaWxlIHdlIGhhdmUgCmVzdGltYXRlZCB0aGUgdHJhamVjdG9yeSBvbiB0aGUgaW50ZWdyYXRlZCBkYXRhLCB3ZSBtb2RlbCB0aGUgcmF3IGdlbmUgCmV4cHJlc3Npb24gZGF0YSwgc2luY2UgYHRyYWRlU2VxYCBpcyBhIGNvdW50IG1vZGVsIGFuZCByZXF1aXJlcyByYXcgY291bnRzIGFzIAppbnB1dC4gT24gdGhlIHJhdyBjb3VudHMsIHdlIHRoZXJlZm9yZSBzdGlsbCBoYXZlIHN1YnN0YW50aWFsIHZhcmlhYmlsaXR5IHRoYXQgCm1heSBiZSBleHBsYWluZWQgYnkgdGhlIHBhdGllbnQgZWZmZWN0cy4gV2UgdGhlcmVmb3JlIGluY29ycG9yYXRlIGEgcGF0aWVudCAKZml4ZWQgZWZmZWN0IHRvIHRoZSBkZXNpZ24gbWF0cml4LgoKYGBge3J9CnNldC5zZWVkKDcpCnN1YnNldF9nZW5lcyA8LSBzYW1wbGUocm93bmFtZXMoc2NlKSwgMTAwMCwgcmVwbGFjZSA9IEZBTFNFKQoKIyBnZW5lcyBmcm9tIHBhcGVyCm1hcmtlcnMgPC0gYygiRU5TRzAwMDAwMTExNzA0IiwgIkVOU0cwMDAwMDE2NDQ1OCIsICJFTlNHMDAwMDAxNDE0NDgiKQoKIyBtYWtlIHN1cmUgdGhlIGdlbmVzIGZyb20gdGhlIHBhcGVyIGFyZSBpbiB0aGVyZQpzdWJzZXRfZ2VuZXMgPC0gYyhzdWJzZXRfZ2VuZXMsIG1hcmtlcnNbIW1hcmtlcnMgJWluJSBzdWJzZXRfZ2VuZXNdKQoKIyDCsTdtaW4gZm9yIDEwMDAgZ2VuZXMKcHNldWRvdGltZSA8LSBzbGluZ1BzZXVkb3RpbWUoc2NlLCBuYSA9IEZBTFNFKQpjZWxsV2VpZ2h0cyA8LSBzbGluZ0N1cnZlV2VpZ2h0cyhzY2UpCgpwYXRpZW50IDwtIGNvbERhdGEoc2NlKSRkb25vcgpVIDwtIG1vZGVsLm1hdHJpeCh+IDAgKyBwYXRpZW50KQpzY2VfZml0IDwtIGZpdEdBTShjb3VudHMgPSBhc3NheXMoc2NlKSRjb3VudHNbc3Vic2V0X2dlbmVzLF0sIAogICAgICAgICAgICAgICAgICBwc2V1ZG90aW1lID0gcHNldWRvdGltZSwgCiAgICAgICAgICAgICAgICAgIGNlbGxXZWlnaHRzID0gY2VsbFdlaWdodHMsCiAgICAgICAgICAgICAgICAgIG5rbm90cyA9IDYsIAogICAgICAgICAgICAgICAgICBVID0gVSwKICAgICAgICAgICAgICAgICAgdmVyYm9zZSA9IFRSVUUpCmBgYAoKVG8gYXNzZXNzIGlmIGFsbCBtb2RlbHMgaGF2ZSBjb252ZXJnZWQ7CgpgYGB7cn0KdGFibGUocm93RGF0YShzY2VfZml0KSR0cmFkZVNlcSRjb252ZXJnZWQpCmBgYAoKIyMgQXNzb2NpYXRpb24gdGVzdAoKTmV4dCwgd2UgY2FuIHBlcmZvcm0gZGlmZmVyZW50IHR5cGVzIG9mIGRpZmZlcmVudGlhbCBleHByZXNzaW9uIHRlc3RpbmcgYWxvbmcKdGhlIHRyYWplY3RvcnkuCgpUaGUgYGFzc29jaWF0aW9uVGVzdGAgYXNzZXNzZXMgd2hldGhlciB0aGUgYXZlcmFnZSBleHByZXNzaW9uIG9mIGEgZ2VuZSBpcyAKYXNzb2NpYXRlZCB3aXRoIHBzZXVkb3RpbWUuIFRvIHByaW9yaXRpemUgZm9yIGdlbmVzIHRoYXQgYXJlIGFsc28gYmlvbG9naWNhbGx5IApyZWxldmFudCwgd2UgbWF5IHRlc3QgYWdhaW5zdCBhIGxvZy1mb2xkIGNoYW5nZSBjdXQtb2ZmOgoKYGBge3J9CmFzc29SZXMyIDwtIGFzc29jaWF0aW9uVGVzdChzY2VfZml0LCBsMmZjPWxvZzIoMikpCnN1bShwLmFkanVzdChhc3NvUmVzMiRwdmFsdWUsIG1ldGhvZCA9ICJCSCIpIDwgMC4wNSwgbmEucm09VCkvbnJvdyhhc3NvUmVzMikgCmBgYAoKIyMgU3RhcnQgdnMgZW5kIHRvcCAyMAoKQW5vdGhlciB0eXBlIG9mIHRlc3QgaXMgdG8gY29tcGFyZSB0aGUgYXZlcmFnZSBnZW5lIGV4cHJlc3Npb24gb2YgZWFjaCBnZW5lIApiZXR3ZWVuIHRoZSBzdGFydCBwb2ludCBhbmQgdGhlIGVuZCBwb2ludCBvZiBhIGxpbmVhZ2UuIFRoaXMgaXMgaW1wbGVtZW50ZWQKaW4gdGhlIGBzdGFydFZzRW5kVGVzdGAgZnVuY3Rpb24uCgpgYGB7cn0Kc3RhcnRSZXMgPC0gc3RhcnRWc0VuZFRlc3Qoc2NlX2ZpdCwgbDJmYz1sb2cyKDIpKQpgYGAKCldlIGNhbiB0aGVuIHZpc3VhbGl6ZSB0aGUgZ2VuZSBleHByZXNzaW9uIHByb2ZpbGUgYWxvbmcgcHNldWRvdGltZSBvZiB0aGUgdG9wIDUKZ2VuZXMgZm9yIHdoaWNoIGRpZmZlcmVudGlhbCBleHByZXNzaW9uIGJldHdlZW4gc3RhcnQgYW5kIGVuZCBwb2ludCB3YXMgCmlkZW50aWZpZWQuCgpgYGB7cn0Kb1N0YXJ0IDwtIG9yZGVyKHN0YXJ0UmVzJHdhbGRTdGF0LCBkZWNyZWFzaW5nID0gVFJVRSkKZm9yIChpIGluIDE6NSkgewogIHNpZ0dlbmVTdGFydCA8LSBvU3RhcnRbaV0gIyB0b3AgNSBtb3N0IHNpZ25pZmljYW50IGdlbmVzIGluIHRoZSBzdGFydCB2cy4gZW5kIHRlc3QKICBwcmludChwbG90U21vb3RoZXJzKHNjZV9maXQsIAogICAgICAgICAgICAgICAgYXNzYXlzKHNjZV9maXQpJGNvdW50cywgCiAgICAgICAgICAgICAgICBnZW5lID0gc2lnR2VuZVN0YXJ0KSArCiAgICAgICAgICBnZ3RpdGxlKHJvd25hbWVzKHNjZSlbc2lnR2VuZVN0YXJ0XSkpCn0KYGBgCgojIyBDb21wYXJpc29uIHRvIG9yaWdpbmFsIHBhcGVyCgpJbiB0aGUgQ3VvbW8gcGFwZXIsIHRoZSBhdXRob3JzIGhpZ2hsaWdodGVkIHRoZSBmb2xsb3dpbmcgZ2VuZXM7CiJFTlNHMDAwMDAxMTE3MDQiLCAiRU5TRzAwMDAwMTY0NDU4IiBhbmQgIkVOU0cwMDAwMDE0MTQ0OCIuIEluIGdlbmUgc3ltYm9scywKdGhlc2UgZ2VuZXMgYXJlIE5BTk9HLCBUICh5ZXMsIHRoZXJlIGlzIGEgZ2VuZSBjYWxsZWQgIlQpIiBhbmQgR0FUQTYuIFRoZXNlCmdlbmVzIGFyZSBtYXJrZXJzIG9mIGRheTAsIGRheTEgYW5kIGRheTIvZGF5MyBjZWxscywgcmVzcGVjdGl2ZWx5LgoKV2UgbWF5IG5vdyB2aXN1YWxpemUgdGhlIGV4cHJlc3Npb24gb2YgdGhlc2UgZ2VuZXMgYWxvbmcgcHNldWRvdGltZS4KCmBgYHtyfQpwbG90U21vb3RoZXJzKHNjZV9maXQsIAogICAgICAgICAgICAgIGFzc2F5cyhzY2VfZml0KSRjb3VudHMsIAogICAgICAgICAgICAgIGdlbmUgPSB3aGljaChyb3duYW1lcyhzY2VfZml0KSA9PSAiRU5TRzAwMDAwMTExNzA0IikpICsKICBnZ3RpdGxlKCJFTlNHMDAwMDAxMTE3MDQiKQoKcGxvdFNtb290aGVycyhzY2VfZml0LCAKICAgICAgICAgICAgICBhc3NheXMoc2NlX2ZpdCkkY291bnRzLCAKICAgICAgICAgICAgICBnZW5lID0gd2hpY2gocm93bmFtZXMoc2NlX2ZpdCkgPT0gIkVOU0cwMDAwMDE2NDQ1OCIpKSArCiAgZ2d0aXRsZSgiRU5TRzAwMDAwMTY0NDU4IikKCnBsb3RTbW9vdGhlcnMoc2NlX2ZpdCwgCiAgICAgICAgICAgICAgYXNzYXlzKHNjZV9maXQpJGNvdW50cywgCiAgICAgICAgICAgICAgZ2VuZSA9IHdoaWNoKHJvd25hbWVzKHNjZV9maXQpID09ICJFTlNHMDAwMDAxNDE0NDgiKSkgKwogIGdndGl0bGUoIkVOU0cwMDAwMDE0MTQ0OCIpCgpgYGAKCioqQSB2ZXJ5IG5pY2UgY29ycmVzcG9uZGVuY2Ugd2l0aCB0aGUgcmVzdWx0cyBwcmVzZW50ZWQgaW4gdGhlIHBhcGVyISEqKgoKYGBge3J9CmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCIuLy4uL2N1b21vX3RyYWoxLmpwZWciKQprbml0cjo6aW5jbHVkZV9ncmFwaGljcygiLi8uLi9jdW9tb190cmFqMi5qcGVnIikKa25pdHI6OmluY2x1ZGVfZ3JhcGhpY3MoIi4vLi4vY3VvbW9fdHJhajMuanBlZyIpCmBgYAoKV2UgYWxzbyBpbnNwZWN0IHRoZSByZXN1bHRzIGluIG91ciBkaWZmZXJlbnRpYWwgdGVzdGluZyBvdXRwdXQuCgpBc3NvY2lhdGlvbiB0ZXN0OgoKYGBge3J9CmFzc29SZXMyW21hcmtlcnMsXQpgYGAKClN0YXJ0IHZlcnN1cyBlbmQgdGVzdDoKCmBgYHtyfQpzdGFydFJlc1ttYXJrZXJzLF0KYGBgCgpBbm90aGVyIGludGVyZXN0aW5nIHZpc3VhbGl6YXRpb24gaXMgaW1wbGVtZW50ZWQgaW4gdGhlIGBwbG90R2VuZUNvdW50YCAKZnVuY3Rpb24sIHdoaWNoIGNvbG9ycyB0aGUgY2VsbHMgYmFzZWQgb24gdGhlIGxvZy10cmFuc2Zvcm1lZCBleHByZXNzaW9uCnZhbHVlIG9mIHRoZSB0YXJnZXQgZ2VuZXMuCgpgYGB7cn0KcGxvdEdlbmVDb3VudChzY2Ukc2xpbmdzaG90LCAKICAgICAgICAgICAgICBhc3NheXMoc2NlX2ZpdCkkY291bnRzLCAKICAgICAgICAgICAgICBnZW5lID0gd2hpY2gocm93bmFtZXMoc2NlX2ZpdCkgPT0gIkVOU0cwMDAwMDExMTcwNCIpKQogICAgICAgICAgICAgIApwbG90R2VuZUNvdW50KHNjZSRzbGluZ3Nob3QsIAogICAgICAgICAgICAgIGFzc2F5cyhzY2VfZml0KSRjb3VudHMsIAogICAgICAgICAgICAgIGdlbmUgPSB3aGljaChyb3duYW1lcyhzY2VfZml0KSA9PSAiRU5TRzAwMDAwMTY0NDU4IikpCgpwbG90R2VuZUNvdW50KHNjZSRzbGluZ3Nob3QsIAogICAgICAgICAgICAgIGFzc2F5cyhzY2VfZml0KSRjb3VudHMsIAogICAgICAgICAgICAgIGdlbmUgPSB3aGljaChyb3duYW1lcyhzY2VfZml0KSA9PSAiRU5TRzAwMDAwMTQxNDQ4IikpCmBgYAoK