1 Background

The data used in this workflow comes from an RNA-seq experiment where airway smooth muscle cells were treated with dexamethasone, a synthetic glucocorticoid steroid with anti-inflammatory effects (Himes et al. 2014). Glucocorticoids are used, for example, by people with asthma to reduce inflammation of the airways. In the experiment, four human airway smooth muscle cell lines were treated with 1 micromolar dexamethasone for 18 hours. For each of the four cell lines, we have a treated and an untreated sample. For more description of the experiment see the article, PubMed entry 24926665, and for raw data see the GEO entry GSE52778.

Many parts of this tutorial are based on parts of a published RNA-seq workflow available via Love et al. 2015 F1000Research and as a Bioconductor package and on Charlotte Soneson’s material from the bss2019 workshop.

2 Data

FastQ files with a small subset of the reads can be found on https://github.com/statOmics/SGA2019/tree/data-rnaseq Here, we will not use our count table because it is based on a small subset of the reads. We will use the count table that was provided after mapping all the reads with the read mapper star.

library(edgeR)
library(tidyverse)

3 Read featurecounts object

We import the featurecounts object that we have stored.

fc <-  readRDS(
  url("https://github.com/statOmics/SGA2020/blob/data-rnaseq/airway/featureCounts/star_featurecounts.rds?raw=true")
  )
colnames(fc$counts)
## [1] "SRR1039508" "SRR1039509" "SRR1039512" "SRR1039513" "SRR1039516"
## [6] "SRR1039517" "SRR1039520" "SRR1039521"

3.1 Read Meta Data

target <- readRDS("airwayMetaData.rds")
## Warning in readRDS("airwayMetaData.rds"): input string 'Cells from each donor
## were treated with 1 μM dexamethasone, 1 μM albuterol, both dexamethasone and
## albuterol, or control vehicle for 18 h.' cannot be translated to UTF-8, is it
## valid in 'US-ASCII'?
## Warning in readRDS("airwayMetaData.rds"): input string 'Primary ASM cells were
## isolated from four white aborted lung transplant donors with no chronic illness.
## Passages 4 to 7 ASM cells maintained in Ham's F12 medium supplemented with 10%
## FBS were used in all experiments.' cannot be translated to UTF-8, is it valid in
## 'US-ASCII'?

4 Data Analysis

4.1 Setup count object edgeR

dge <- DGEList(fc$counts)
colnames(dge)==target$Run
##  [1]  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
## [13] FALSE FALSE FALSE FALSE
target$Run%in%colnames(dge)
##  [1]  TRUE  TRUE FALSE FALSE  TRUE  TRUE FALSE FALSE  TRUE  TRUE FALSE FALSE
## [13]  TRUE  TRUE FALSE FALSE
rownames(target) <- target$Run
target <- target[colnames(dge),]
target[,grep(":ch1",colnames(target))]
##            cell line:ch1              cell type:ch1 ercc_mix:ch1
## SRR1039508        N61311 airway smooth muscle cells            -
## SRR1039509        N61311 airway smooth muscle cells            -
## SRR1039512       N052611 airway smooth muscle cells            -
## SRR1039513       N052611 airway smooth muscle cells            1
## SRR1039516       N080611 airway smooth muscle cells            -
## SRR1039517       N080611 airway smooth muscle cells            -
## SRR1039520       N061011 airway smooth muscle cells            1
## SRR1039521       N061011 airway smooth muscle cells            1
##                                  tissue:ch1 treatment:ch1
## SRR1039508 human airway smooth muscle cells     Untreated
## SRR1039509 human airway smooth muscle cells Dexamethasone
## SRR1039512 human airway smooth muscle cells     Untreated
## SRR1039513 human airway smooth muscle cells Dexamethasone
## SRR1039516 human airway smooth muscle cells     Untreated
## SRR1039517 human airway smooth muscle cells Dexamethasone
## SRR1039520 human airway smooth muscle cells     Untreated
## SRR1039521 human airway smooth muscle cells Dexamethasone
target$cellLine <- as.factor(target[,grep("cell line:ch1",colnames(target))])
target$treatment <- as.factor(target[,grep("treatment:ch1",colnames(target))])
target$treatment <- relevel(target$treatment,"Untreated")
colnames(dge) <- paste0(
  substr(target$cellLine, 1, 3),
  "_",
  substr(target$treatment, 1, 3)
  )

4.2 Filtering and normalisation

design <- model.matrix( ~ treatment + cellLine, data = target)
keep <- filterByExpr(dge, design)
dge <- dge[keep, , keep.lib.sizes=FALSE]
dge<-calcNormFactors(dge)

4.3 Data exploration

One way to reduce dimensionality is the use of multidimensional scaling (MDS). For MDS, we first have to calculate all pairwise distances between our objects (samples in this case), and then create a (typically) two-dimensional representation where these pre-calculated distances are represented as accurately as possible. This means that depending on how the pairwise sample distances are defined, the two-dimensional plot can be very different, and it is important to choose a distance that is suitable for the type of data at hand.

edgeR contains a function plotMDS, which operates on a DGEList object and generates a two-dimensional MDS representation of the samples. The default distance between two samples can be interpreted as the “typical” log fold change between the two samples, for the genes that are most different between them (by default, the top 500 genes, but this can be modified). We generate an MDS plot from the DGEList object dge, coloring by the treatment and using different plot symbols for different cell lines.

plotMDS(dge, top = 500,col=as.double(target$cellLine))

4.4 Differential analysis

4.4.1 Model

We first estimate the overdispersion.

dge <- estimateDisp(dge, design)
plotBCV(dge)

Finally, we fit the generalized linear model and perform the test. In the glmLRT function, we indicate which coefficient (which column in the design matrix) that we would like to test for. It is possible to test more general contrasts as well, and the user guide contains many examples on how to do this. The topTags function extracts the top-ranked genes. You can indicate the adjusted p-value cutoff, and/or the number of genes to keep.

fit <- glmFit(dge, design)
lrt <- glmLRT(fit, coef = "treatmentDexamethasone")
ttAll <- topTags(lrt, n = nrow(dge)) # all genes
hist(ttAll$table$PValue)

tt <- topTags(lrt, n = nrow(dge), p.value = 0.05) # genes with adj.p<0.05
nrow(tt)
## [1] 5713

There are 5713 genes statistiscally significant at the 5% FDR level.

4.4.2 Plots

We first make a volcanoplot and an MA plot.

library(ggplot2)
volcano <- ggplot(ttAll$table,aes(x=logFC,y=-log10(PValue),color=FDR<0.05)) + geom_point() + scale_color_manual(values=c("black","red"))
volcano

plotSmear(lrt, de.tags = row.names(tt$table))

Another way of representing the results of a differential expression analysis is to construct a heatmap of the top differentially expressed genes. Here, we would expect the contrasted sample groups to cluster separately. A heatmap is a “color coded expression matrix”, where the rows and columns are clustered using hierarchical clustering. Typically, it should not be applied to counts, but works better with transformed values. Here we show how it can be applied to the variance-stabilized values generated above. We choose the top 30 differentially expressed genes. There are many functions in R that can generate heatmaps, here we show the one from the pheatmap package.

library(pheatmap)
pheatmap(cpm(dge,log=TRUE)[rownames(tt$table)[1:30],])

5 Issues

We find a huge number of DE genes. If this is the case it is always important to carefully check your results.

5.1 p-values

ttAll$table %>%
  ggplot(aes(x=PValue)) +
  geom_histogram()
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

We indeed see a large enrichment of small p-values.

We know that the inference is only asymptotically valid, i.e. for large experiments.

EdgeR is using a likelihood ratio test for statistical inference. The null distribution of this test statistic follows an asymptotic chi-square distribution.

If we test for a single contrast (e.g. one model parameter or one linear combination of model parameters) then the chi-square distribution has one degree of freedom and you will perform a two-sided test.

5.2 Empirical null distribution

Efron 2008 relaxes the use of a theoretical null distribution for assessing statistical significance.

  • He shows that we can exploit the massive parallel data structure of high throughput experiments to estimate the empirical null distribution.

  • He assumes that the test statistics follow a normal distribution under the null, but proposes to estimate the location and the variance empirically.

Assuming that the test statistic has a standard normal null distribution is not restrictive. For example, suppose that \(t\)-tests have been applied and that the null distribution is \(t_d\), with \(d\) representing the degrees of freedom. Let \(F_{td}\) denote the distribution function of \(t_d\) and let \(\Phi\) denote the distribution function of the standard normal distribution. If \(T\) denotes the \(t\)-test statistic, then, under the null hypothesis, \[ T \sim t_d \] and hence \[ F_{td}(T) \sim U[0,1] \] and \[ Z = \Phi^{-1}(F_{td}(T)) \sim N(0,1). \]

If all \(m\) null hypotheses are true, then each of the \(Z_g\) is \(N(0,1)\) and the set of \(m\) calculated \(z_g\) test statistics may be considered as a sample from \(N(0,1)\). Hence, under these conditions we expect the histogram of the \(m\) \(z_g\)’s to look like the density of the null distribution.

If a LRT test is conducted for a single contrast, we can obtain the corresponding \(Z_g\) by converting the p-values into quantiles of the normal, i.e.

\(z_g = \Phi^{-1} (1-p/2) \times \text{sign}(FC)\)

The normal distribution is very useful for diagnostics because we are used to work with it.

So in general we

  1. Start of the two-sided p-values.
  2. We divide the p-values by two to have the probability in one of the tails
  3. We calculate which quantile of the normal corresponds to it
  4. We give the z-value the sign of our contrast.
ttAll$table <- ttAll$table %>%
  mutate(z = sign(logFC) * abs(qnorm(PValue/2)))

ttAll$table %>%
  ggplot(aes(x=z)) +
  geom_histogram(aes(y = ..density..), color = "black") +
  stat_function(fun = dnorm,
      args = list(
    mean = 0,
    sd=1)
  )
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

The histogram clearly shows that the theoretical null distribution N(0,1) does not seen to match the null distribution in the airway dataset.

We can empirically estimate the null distribution using the locfdr package. The locfdr package allows you to calculate local fdrs. It uses the two groups model:

\[f(z) = \pi_0f_0(z) + (1-\pi_0) f_1(z)\]

The local fdr or posterior probability that the gene with a certain test statistic z is a false positive then becomes

\[lfdr = \frac{\pi_0 f_0(z)}{f(z)} \]

Efron suggests to use a cutoff for the lfdr of 20%. So we return all genes for which the probability that they are false positives is below 20%. He claims that this corresponds to a conventional FDR of about 5% in the set that you return.

It can be shown that the FDR:

\[ FDR = E[lfdr] \approx \frac{\sum\limits_{k \in DE-set} lfdr_k}{n_\text{DE}} \]

We can also estimate the global FDR by simply calculating the average lfdr in the set that we return.

library(locfdr)
ttAll$table <- ttAll$table %>%
  mutate(lfdr = locfdr(z)$fdr)
## Warning: Problem with `mutate()` input `lfdr`.
## ℹ f(z) misfit = 11.1.  Rerun with increased df
## ℹ Input `lfdr` is `locfdr(z)$fdr`.
## Warning in locfdr(z): f(z) misfit = 11.1. Rerun with increased df

In the plot we see the histogram of the z-values.

  • The green line is the estimate of the marginal distribution \(f(z)\). A non-parameteric density estimator is used for this purpose.
  • The blue line is the estimate of the null distribution.
  • We see that null distribution appears to be much broader than the standard normal and it shows a slight shift.
  • We see that the marginal distribution (green distribution) is not estimated well.
  • We also get a warning message that indicates that we can increase the degrees of freedom.

We re-estimate \(f(z)\) by using more degrees of freedom, e.g. df = 20.

ttAll$table <- ttAll$table %>%
  mutate(lfdr = locfdr(z, df = 20)$fdr)

Estimated FDR corresponding to the set of genes with lfdr < 0.2 and number of significant genes with lfdr < 0.2?

ttAll$table %>%
  filter(lfdr < 0.2) %>%
  summarize(
    FDR = mean(lfdr, na.rm = TRUE),
    nSig = lfdr %>%
      is.na %>%
      `!` %>%
      sum)
##          FDR nSig
## 1 0.04545589 1436

Note, that

  • the FDR of the set that is returned is indeed close to 0.5.
  • the number of significant genes has been reduced considerably.
  • It is very important to evaluate the fit of the null and marginal distribution in the plot.

If you would like to opt to use the FDR method of Benjamini and Hochberg, you also could convert the z-values back in p-values by using a normal \(N(\hat \mu, \hat \sigma^2)\), where we use the estimated parameters for the null distribution by locfdr.

h <- ttAll$table %>%
  pull(z) %>%
  locfdr(df = 20, plot=FALSE)

ttAll$table <- ttAll$table %>%
  mutate(pEmp = pnorm(
    abs(z),
    mean = h$fp0["mlest","delta"],
    sd = h$fp0["mlest","sigma"],
    lower = FALSE) * 2
    ) %>%
  mutate(pAdjEmp = p.adjust(
    pEmp,
    method="BH")
    )

ttAll$table %>%
  filter(pAdjEmp < 0.05) %>%
  nrow
## [1] 1500

We observe that the number of significant genes reduces to about the same amount as with the lfdr method of Efron. We, however, did not have to use a density estimator for the marginal cumulative distribution function of the test statistics. Instead, the BH method uses the empirical distribution of the statistics.

5.3 Assess why deviations from the null occur?

5.3.1 Failed mathematical assumptions?

If we permute the gene expression data of all observations differently for every gene, we simulate expressions under the null and breakup the correlation structure between the genes.

set.seed(1004)
dgePermAll <- dge
dgePermAll$counts <- apply(dge$counts, 1, sample)  %>% t
dgePermAll$samples$lib.size <-  dgePermAll$counts %>% colSums
dgePermAll <- calcNormFactors(dgePermAll)

dgePermAll <- estimateDisp(dgePermAll, design)
plotBCV(dgePermAll)

fitPermAll <- glmFit(dgePermAll, design)
lrtPermAll <- glmLRT(fitPermAll, coef = "treatmentDexamethasone")
ttAllPermAll <- topTags(lrtPermAll, n = nrow(dgePermAll))

ttAllPermAll$table <- ttAllPermAll$table %>%
  mutate(z = sign(logFC) * abs(qnorm(PValue/2)))

ttAllPermAll$table %>%
  ggplot(aes(x=z)) +
  geom_histogram(aes(y = ..density..), color = "black") +
  stat_function(fun = dnorm,
    args = list(
    mean = 0,
    sd=1)
  )
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

We observe that the null distribution is approximately following a standard normal distribution. There is no shift and the standard deviation in no longer larger than 1.

Hence, there do not seem to be issues related to failed mathematical assumptions.

5.3.2 Correlation of the genes?

We will now only permute the samples across conditions, but, we keep all genes together, e.g. by permuting the design matrix.

This simulates data from the null and breaks the association between the predictors and potential confounders, however, correlation between the genes remains.

Here, we have a block design so we will permute within block. We will perform a balanced permutation. We will select two cellines at random and we will permute the labels of the treatment.

designPerm <- design

cellLine <- sample(0:3,2)
cellLine
## [1] 1 2
for (i in cellLine)
  designPerm[i*2 + 1:2, 2] <- c(1,0)
designPerm
##            (Intercept) treatmentDexamethasone cellLineN061011 cellLineN080611
## SRR1039508           1                      0               0               0
## SRR1039509           1                      1               0               0
## SRR1039512           1                      1               0               0
## SRR1039513           1                      0               0               0
## SRR1039516           1                      1               0               1
## SRR1039517           1                      0               0               1
## SRR1039520           1                      0               1               0
## SRR1039521           1                      1               1               0
##            cellLineN61311
## SRR1039508              1
## SRR1039509              1
## SRR1039512              0
## SRR1039513              0
## SRR1039516              0
## SRR1039517              0
## SRR1039520              0
## SRR1039521              0
## attr(,"assign")
## [1] 0 1 2 2 2
## attr(,"contrasts")
## attr(,"contrasts")$treatment
## [1] "contr.treatment"
## 
## attr(,"contrasts")$cellLine
## [1] "contr.treatment"
fitPermSamp <- glmFit(dge, designPerm)
lrtPermSamp <- glmLRT(fitPermSamp, coef = "treatmentDexamethasone")
ttAllPermSamp <- topTags(lrtPermSamp, n = nrow(dge))

ttAllPermSamp$table <- ttAllPermSamp$table %>%
  mutate(z = sign(logFC) * abs(qnorm(PValue/2)))

ttAllPermSamp$table %>%
  ggplot(aes(x=z)) +
  geom_histogram(aes(y = ..density..), color = "black") +
  stat_function(fun = dnorm,
  args = list(
    mean = 0,
    sd=1)
  )
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

We observe that the null distribution is approximately matching with a standard normal. There is no shift and the standard deviation in no longer larger than 1. Here, the distribution seems to be a bit more narrow than the the theoretical distribution.

5.3.2.1 Repeat for other permutation:

designPerm <- design

cellLine <- c(0,2)
cellLine
## [1] 0 2
for (i in cellLine)
  designPerm[i*2 + 1:2, 2] <- c(1,0)
designPerm
##            (Intercept) treatmentDexamethasone cellLineN061011 cellLineN080611
## SRR1039508           1                      1               0               0
## SRR1039509           1                      0               0               0
## SRR1039512           1                      0               0               0
## SRR1039513           1                      1               0               0
## SRR1039516           1                      1               0               1
## SRR1039517           1                      0               0               1
## SRR1039520           1                      0               1               0
## SRR1039521           1                      1               1               0
##            cellLineN61311
## SRR1039508              1
## SRR1039509              1
## SRR1039512              0
## SRR1039513              0
## SRR1039516              0
## SRR1039517              0
## SRR1039520              0
## SRR1039521              0
## attr(,"assign")
## [1] 0 1 2 2 2
## attr(,"contrasts")
## attr(,"contrasts")$treatment
## [1] "contr.treatment"
## 
## attr(,"contrasts")$cellLine
## [1] "contr.treatment"
fitPermSamp <- glmFit(dge, designPerm)
lrtPermSamp <- glmLRT(fitPermSamp, coef = "treatmentDexamethasone")
ttAllPermSamp <- topTags(lrtPermSamp, n = nrow(dge))

ttAllPermSamp$table <- ttAllPermSamp$table %>%
  mutate(z = sign(logFC) * abs(qnorm(PValue/2)))

pPermSamp <- ttAllPermSamp$table %>%
  ggplot(aes(x=z)) +
  geom_histogram(aes(y = ..density..), color = "black") +
  stat_function(fun = dnorm,
  args = list(
    mean = 0,
    sd=1)
  )
pPermSamp
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.

pPermSamp + xlim(-4,4)
## `stat_bin()` using `bins = 30`. Pick better value with `binwidth`.
## Warning: Removed 3 rows containing non-finite values (stat_bin).
## Warning: Removed 2 rows containing missing values (geom_bar).

Both permutations show that there are no deviations from the theoretical null when we simulate under the null and break potential confounding but leave correlation between genes intact.

So there seems to be another reason for deviations of the null, than failed mathematical assumptions and correlation between genes!

Perhaps confounders that we do not account for?

5.4 Concluding remark

This example also clearly shows that although permutation methods offer a simple and attractive way to deal with mathematically complicated hypothesis testing situations, they often cannot remedy failures of the theoretical null.

So the use of permutations to establish the null distribution should also be used with care in high throughput contexts. Indeed, depending on the permutation scheme that is used you might break correlations between genes, samples and/or potential confounding.

So even if you use a permutation approach in a high throughput context, e.g. a wilcoxon rank sum test or other permutation based tests, you still might need to check for deviations of the null!

LS0tCnRpdGxlOiAiQWlyd2F5OiBERSBhbmFseXNpcyIKYXV0aG9yOiAiTGlldmVuIENsZW1lbnQiCmRhdGU6ICJzdGF0T21pY3MsIEdoZW50IFVuaXZlcnNpdHkgKGh0dHBzOi8vc3RhdG9taWNzLmdpdGh1Yi5pbykiCm91dHB1dDoKICAgIGh0bWxfZG9jdW1lbnQ6CiAgICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgICAgdGhlbWU6IGNvc21vCiAgICAgIHRvYzogdHJ1ZQogICAgICB0b2NfZmxvYXQ6IHRydWUKICAgICAgaGlnaGxpZ2h0OiB0YW5nbwogICAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUKLS0tCgojIEJhY2tncm91bmQKVGhlIGRhdGEgdXNlZCBpbiB0aGlzIHdvcmtmbG93IGNvbWVzIGZyb20gYW4gUk5BLXNlcSBleHBlcmltZW50IHdoZXJlIGFpcndheSBzbW9vdGggbXVzY2xlIGNlbGxzIHdlcmUgdHJlYXRlZCB3aXRoIGRleGFtZXRoYXNvbmUsIGEgc3ludGhldGljIGdsdWNvY29ydGljb2lkIHN0ZXJvaWQgd2l0aCBhbnRpLWluZmxhbW1hdG9yeSBlZmZlY3RzIChIaW1lcyBldCBhbC4gMjAxNCkuIEdsdWNvY29ydGljb2lkcyBhcmUgdXNlZCwgZm9yIGV4YW1wbGUsIGJ5IHBlb3BsZSB3aXRoIGFzdGhtYSB0byByZWR1Y2UgaW5mbGFtbWF0aW9uIG9mIHRoZSBhaXJ3YXlzLiBJbiB0aGUgZXhwZXJpbWVudCwgZm91ciBodW1hbiBhaXJ3YXkgc21vb3RoIG11c2NsZSBjZWxsIGxpbmVzIHdlcmUgdHJlYXRlZCB3aXRoIDEgbWljcm9tb2xhciBkZXhhbWV0aGFzb25lIGZvciAxOCBob3Vycy4gRm9yIGVhY2ggb2YgdGhlIGZvdXIgY2VsbCBsaW5lcywgd2UgaGF2ZSBhIHRyZWF0ZWQgYW5kIGFuIHVudHJlYXRlZCBzYW1wbGUuCkZvciBtb3JlIGRlc2NyaXB0aW9uIG9mIHRoZSBleHBlcmltZW50IHNlZSB0aGUgYXJ0aWNsZSwgUHViTWVkIGVudHJ5IDI0OTI2NjY1LCBhbmQgZm9yIHJhdyBkYXRhIHNlZSB0aGUgR0VPIGVudHJ5IEdTRTUyNzc4LgoKTWFueSBwYXJ0cyBvZiB0aGlzIHR1dG9yaWFsIGFyZSBiYXNlZCBvbiBwYXJ0cyBvZiBhIHB1Ymxpc2hlZCBSTkEtc2VxIHdvcmtmbG93CmF2YWlsYWJsZSB2aWEgTG92ZSBldCBhbC4gMjAxNSBbRjEwMDBSZXNlYXJjaF0oaHR0cDovL2YxMDAwcmVzZWFyY2guY29tL2FydGljbGVzLzQtMTA3MCkgYW5kIGFzIGEgW0Jpb2NvbmR1Y3RvcgpwYWNrYWdlXShodHRwczovL3d3dy5iaW9jb25kdWN0b3Iub3JnL3BhY2thZ2VzL3JlbGVhc2Uvd29ya2Zsb3dzL2h0bWwvcm5hc2VxR2VuZS5odG1sKSBhbmQgb24gQ2hhcmxvdHRlIFNvbmVzb24ncyBtYXRlcmlhbCBmcm9tIHRoZSBbYnNzMjAxOV0oaHR0cHM6Ly91Y2xvdXZhaW4tY2Jpby5naXRodWIuaW8vQlNTMjAxOS9ybmFzZXFfZ2VuZV9zdW1tZXJzY2hvb2xfYmVsZ2l1bV8yMDE5Lmh0bWwpIHdvcmtzaG9wLgoKIyBEYXRhCkZhc3RRIGZpbGVzIHdpdGggYSBzbWFsbCBzdWJzZXQgb2YgdGhlIHJlYWRzIGNhbiBiZSBmb3VuZCBvbiBodHRwczovL2dpdGh1Yi5jb20vc3RhdE9taWNzL1NHQTIwMTkvdHJlZS9kYXRhLXJuYXNlcQpIZXJlLCB3ZSB3aWxsIG5vdCB1c2Ugb3VyIGNvdW50IHRhYmxlIGJlY2F1c2UgaXQgaXMgYmFzZWQgb24gYSBzbWFsbCBzdWJzZXQgb2YgdGhlIHJlYWRzLgpXZSB3aWxsIHVzZSB0aGUgY291bnQgdGFibGUgdGhhdCB3YXMgcHJvdmlkZWQgYWZ0ZXIgbWFwcGluZyBhbGwgdGhlIHJlYWRzIHdpdGggdGhlIHJlYWQgbWFwcGVyIHN0YXIuCgoKYGBge3J9CmxpYnJhcnkoZWRnZVIpCmxpYnJhcnkodGlkeXZlcnNlKQpgYGAKCiMgUmVhZCBmZWF0dXJlY291bnRzIG9iamVjdAoKV2UgaW1wb3J0IHRoZSBmZWF0dXJlY291bnRzIG9iamVjdCB0aGF0IHdlIGhhdmUgc3RvcmVkLgoKYGBge3J9CmZjIDwtICByZWFkUkRTKAogIHVybCgiaHR0cHM6Ly9naXRodWIuY29tL3N0YXRPbWljcy9TR0EyMDIwL2Jsb2IvZGF0YS1ybmFzZXEvYWlyd2F5L2ZlYXR1cmVDb3VudHMvc3Rhcl9mZWF0dXJlY291bnRzLnJkcz9yYXc9dHJ1ZSIpCiAgKQpjb2xuYW1lcyhmYyRjb3VudHMpCmBgYAoKIyMgUmVhZCBNZXRhIERhdGEKCmBgYHtyfQp0YXJnZXQgPC0gcmVhZFJEUygiYWlyd2F5TWV0YURhdGEucmRzIikKYGBgCgojIERhdGEgQW5hbHlzaXMKIyMgU2V0dXAgY291bnQgb2JqZWN0IGVkZ2VSCgpgYGB7cn0KZGdlIDwtIERHRUxpc3QoZmMkY291bnRzKQpjb2xuYW1lcyhkZ2UpPT10YXJnZXQkUnVuCnRhcmdldCRSdW4laW4lY29sbmFtZXMoZGdlKQpgYGAKCmBgYHtyfQpyb3duYW1lcyh0YXJnZXQpIDwtIHRhcmdldCRSdW4KdGFyZ2V0IDwtIHRhcmdldFtjb2xuYW1lcyhkZ2UpLF0KdGFyZ2V0WyxncmVwKCI6Y2gxIixjb2xuYW1lcyh0YXJnZXQpKV0KYGBgCgpgYGB7cn0KdGFyZ2V0JGNlbGxMaW5lIDwtIGFzLmZhY3Rvcih0YXJnZXRbLGdyZXAoImNlbGwgbGluZTpjaDEiLGNvbG5hbWVzKHRhcmdldCkpXSkKdGFyZ2V0JHRyZWF0bWVudCA8LSBhcy5mYWN0b3IodGFyZ2V0WyxncmVwKCJ0cmVhdG1lbnQ6Y2gxIixjb2xuYW1lcyh0YXJnZXQpKV0pCnRhcmdldCR0cmVhdG1lbnQgPC0gcmVsZXZlbCh0YXJnZXQkdHJlYXRtZW50LCJVbnRyZWF0ZWQiKQpgYGAKCgpgYGB7cn0KY29sbmFtZXMoZGdlKSA8LSBwYXN0ZTAoCiAgc3Vic3RyKHRhcmdldCRjZWxsTGluZSwgMSwgMyksCiAgIl8iLAogIHN1YnN0cih0YXJnZXQkdHJlYXRtZW50LCAxLCAzKQogICkKYGBgCgojIyBGaWx0ZXJpbmcgYW5kIG5vcm1hbGlzYXRpb24KCmBgYHtyfQpkZXNpZ24gPC0gbW9kZWwubWF0cml4KCB+IHRyZWF0bWVudCArIGNlbGxMaW5lLCBkYXRhID0gdGFyZ2V0KQprZWVwIDwtIGZpbHRlckJ5RXhwcihkZ2UsIGRlc2lnbikKZGdlIDwtIGRnZVtrZWVwLCAsIGtlZXAubGliLnNpemVzPUZBTFNFXQpkZ2U8LWNhbGNOb3JtRmFjdG9ycyhkZ2UpCmBgYAoKCgoKIyMgRGF0YSBleHBsb3JhdGlvbgoKT25lIHdheSB0byByZWR1Y2UgZGltZW5zaW9uYWxpdHkgaXMgdGhlIHVzZSBvZiBtdWx0aWRpbWVuc2lvbmFsIHNjYWxpbmcgKE1EUykuIEZvciBNRFMsIHdlIGZpcnN0IGhhdmUgdG8gY2FsY3VsYXRlIGFsbCBwYWlyd2lzZSBkaXN0YW5jZXMgYmV0d2VlbiBvdXIgb2JqZWN0cyAoc2FtcGxlcyBpbiB0aGlzIGNhc2UpLCBhbmQgdGhlbiBjcmVhdGUgYSAodHlwaWNhbGx5KSB0d28tZGltZW5zaW9uYWwgcmVwcmVzZW50YXRpb24gd2hlcmUgdGhlc2UgcHJlLWNhbGN1bGF0ZWQgZGlzdGFuY2VzIGFyZSByZXByZXNlbnRlZCBhcyBhY2N1cmF0ZWx5IGFzIHBvc3NpYmxlLiBUaGlzIG1lYW5zIHRoYXQgZGVwZW5kaW5nIG9uIGhvdyB0aGUgcGFpcndpc2Ugc2FtcGxlIGRpc3RhbmNlcyBhcmUgZGVmaW5lZCwgdGhlIHR3by1kaW1lbnNpb25hbCBwbG90IGNhbiBiZSB2ZXJ5IGRpZmZlcmVudCwgYW5kIGl0IGlzIGltcG9ydGFudCB0byBjaG9vc2UgYSBkaXN0YW5jZSB0aGF0IGlzIHN1aXRhYmxlIGZvciB0aGUgdHlwZSBvZiBkYXRhIGF0IGhhbmQuCgplZGdlUiBjb250YWlucyBhIGZ1bmN0aW9uIHBsb3RNRFMsIHdoaWNoIG9wZXJhdGVzIG9uIGEgREdFTGlzdCBvYmplY3QgYW5kIGdlbmVyYXRlcyBhIHR3by1kaW1lbnNpb25hbCBNRFMgcmVwcmVzZW50YXRpb24gb2YgdGhlIHNhbXBsZXMuIFRoZSBkZWZhdWx0IGRpc3RhbmNlIGJldHdlZW4gdHdvIHNhbXBsZXMgY2FuIGJlIGludGVycHJldGVkIGFzIHRoZSAidHlwaWNhbCIgbG9nIGZvbGQgY2hhbmdlIGJldHdlZW4gdGhlIHR3byBzYW1wbGVzLCBmb3IgdGhlIGdlbmVzIHRoYXQgYXJlIG1vc3QgZGlmZmVyZW50IGJldHdlZW4gdGhlbSAoYnkgZGVmYXVsdCwgdGhlIHRvcCA1MDAgZ2VuZXMsIGJ1dCB0aGlzIGNhbiBiZSBtb2RpZmllZCkuIFdlIGdlbmVyYXRlIGFuIE1EUyBwbG90IGZyb20gdGhlIERHRUxpc3Qgb2JqZWN0IGRnZSwgY29sb3JpbmcgYnkgdGhlIHRyZWF0bWVudCBhbmQgdXNpbmcgZGlmZmVyZW50IHBsb3Qgc3ltYm9scyBmb3IgZGlmZmVyZW50IGNlbGwgbGluZXMuCgpgYGB7cn0KcGxvdE1EUyhkZ2UsIHRvcCA9IDUwMCxjb2w9YXMuZG91YmxlKHRhcmdldCRjZWxsTGluZSkpCmBgYAoKCgoKIyMgRGlmZmVyZW50aWFsIGFuYWx5c2lzCgojIyMgTW9kZWwKCldlIGZpcnN0IGVzdGltYXRlIHRoZSBvdmVyZGlzcGVyc2lvbi4KCmBgYHtyfQpkZ2UgPC0gZXN0aW1hdGVEaXNwKGRnZSwgZGVzaWduKQpwbG90QkNWKGRnZSkKYGBgCgoKRmluYWxseSwgd2UgZml0IHRoZSBnZW5lcmFsaXplZCBsaW5lYXIgbW9kZWwgYW5kIHBlcmZvcm0gdGhlIHRlc3QuIEluIHRoZSBnbG1MUlQgZnVuY3Rpb24sIHdlIGluZGljYXRlIHdoaWNoIGNvZWZmaWNpZW50ICh3aGljaCBjb2x1bW4gaW4gdGhlIGRlc2lnbiBtYXRyaXgpIHRoYXQgd2Ugd291bGQgbGlrZSB0byB0ZXN0IGZvci4gSXQgaXMgcG9zc2libGUgdG8gdGVzdCBtb3JlIGdlbmVyYWwgY29udHJhc3RzIGFzIHdlbGwsIGFuZCB0aGUgdXNlciBndWlkZSBjb250YWlucyBtYW55IGV4YW1wbGVzIG9uIGhvdyB0byBkbyB0aGlzLiBUaGUgdG9wVGFncyBmdW5jdGlvbiBleHRyYWN0cyB0aGUgdG9wLXJhbmtlZCBnZW5lcy4gWW91IGNhbiBpbmRpY2F0ZSB0aGUgYWRqdXN0ZWQgcC12YWx1ZSBjdXRvZmYsIGFuZC9vciB0aGUgbnVtYmVyIG9mIGdlbmVzIHRvIGtlZXAuCgpgYGB7cn0KZml0IDwtIGdsbUZpdChkZ2UsIGRlc2lnbikKbHJ0IDwtIGdsbUxSVChmaXQsIGNvZWYgPSAidHJlYXRtZW50RGV4YW1ldGhhc29uZSIpCnR0QWxsIDwtIHRvcFRhZ3MobHJ0LCBuID0gbnJvdyhkZ2UpKSAjIGFsbCBnZW5lcwpoaXN0KHR0QWxsJHRhYmxlJFBWYWx1ZSkKdHQgPC0gdG9wVGFncyhscnQsIG4gPSBucm93KGRnZSksIHAudmFsdWUgPSAwLjA1KSAjIGdlbmVzIHdpdGggYWRqLnA8MC4wNQpucm93KHR0KQpgYGAKClRoZXJlIGFyZSBgciBucm93KHR0KWAgZ2VuZXMgc3RhdGlzdGlzY2FsbHkgc2lnbmlmaWNhbnQgYXQgdGhlIDUlIEZEUiBsZXZlbC4KCiMjIyBQbG90cwoKV2UgZmlyc3QgbWFrZSBhIHZvbGNhbm9wbG90IGFuZCBhbiBNQSBwbG90LgoKYGBge3J9CmxpYnJhcnkoZ2dwbG90MikKdm9sY2FubyA8LSBnZ3Bsb3QodHRBbGwkdGFibGUsYWVzKHg9bG9nRkMseT0tbG9nMTAoUFZhbHVlKSxjb2xvcj1GRFI8MC4wNSkpICsgZ2VvbV9wb2ludCgpICsgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcz1jKCJibGFjayIsInJlZCIpKQp2b2xjYW5vCnBsb3RTbWVhcihscnQsIGRlLnRhZ3MgPSByb3cubmFtZXModHQkdGFibGUpKQpgYGAKCkFub3RoZXIgd2F5IG9mIHJlcHJlc2VudGluZyB0aGUgcmVzdWx0cyBvZiBhIGRpZmZlcmVudGlhbCBleHByZXNzaW9uIGFuYWx5c2lzIGlzIHRvIGNvbnN0cnVjdCBhIGhlYXRtYXAgb2YgdGhlIHRvcCBkaWZmZXJlbnRpYWxseSBleHByZXNzZWQgZ2VuZXMuIEhlcmUsIHdlIHdvdWxkIGV4cGVjdCB0aGUgY29udHJhc3RlZCBzYW1wbGUgZ3JvdXBzIHRvIGNsdXN0ZXIgc2VwYXJhdGVseS4gQSBoZWF0bWFwIGlzIGEgImNvbG9yIGNvZGVkIGV4cHJlc3Npb24gbWF0cml4Iiwgd2hlcmUgdGhlIHJvd3MgYW5kIGNvbHVtbnMgYXJlIGNsdXN0ZXJlZCB1c2luZyBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4gVHlwaWNhbGx5LCBpdCBzaG91bGQgbm90IGJlIGFwcGxpZWQgdG8gY291bnRzLCBidXQgd29ya3MgYmV0dGVyIHdpdGggdHJhbnNmb3JtZWQgdmFsdWVzLiBIZXJlIHdlIHNob3cgaG93IGl0IGNhbiBiZSBhcHBsaWVkIHRvIHRoZSB2YXJpYW5jZS1zdGFiaWxpemVkIHZhbHVlcyBnZW5lcmF0ZWQgYWJvdmUuIFdlIGNob29zZSB0aGUgdG9wIDMwIGRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZCBnZW5lcy4gVGhlcmUgYXJlIG1hbnkgZnVuY3Rpb25zIGluIFIgdGhhdCBjYW4gZ2VuZXJhdGUgaGVhdG1hcHMsIGhlcmUgd2Ugc2hvdyB0aGUgb25lIGZyb20gdGhlIHBoZWF0bWFwIHBhY2thZ2UuCgpgYGB7cn0KbGlicmFyeShwaGVhdG1hcCkKcGhlYXRtYXAoY3BtKGRnZSxsb2c9VFJVRSlbcm93bmFtZXModHQkdGFibGUpWzE6MzBdLF0pCmBgYAoKIyBJc3N1ZXMKCldlIGZpbmQgYSBodWdlIG51bWJlciBvZiBERSBnZW5lcy4gSWYgdGhpcyBpcyB0aGUgY2FzZSBpdCBpcyBhbHdheXMgaW1wb3J0YW50IHRvIGNhcmVmdWxseSBjaGVjayB5b3VyIHJlc3VsdHMuCgojIyBwLXZhbHVlcwoKYGBge3J9CnR0QWxsJHRhYmxlICU+JQogIGdncGxvdChhZXMoeD1QVmFsdWUpKSArCiAgZ2VvbV9oaXN0b2dyYW0oKQpgYGAKCldlIGluZGVlZCBzZWUgYSBsYXJnZSBlbnJpY2htZW50IG9mIHNtYWxsIHAtdmFsdWVzLgoKV2Uga25vdyB0aGF0IHRoZSBpbmZlcmVuY2UgaXMgb25seSBhc3ltcHRvdGljYWxseSB2YWxpZCwgaS5lLiBmb3IgbGFyZ2UgZXhwZXJpbWVudHMuCgpFZGdlUiBpcyB1c2luZyBhIGxpa2VsaWhvb2QgcmF0aW8gdGVzdCBmb3Igc3RhdGlzdGljYWwgaW5mZXJlbmNlLiBUaGUgbnVsbCBkaXN0cmlidXRpb24gb2YgdGhpcyB0ZXN0IHN0YXRpc3RpYyBmb2xsb3dzIGFuIGFzeW1wdG90aWMgY2hpLXNxdWFyZSBkaXN0cmlidXRpb24uCgpJZiB3ZSB0ZXN0IGZvciBhIHNpbmdsZSBjb250cmFzdCAoZS5nLiBvbmUgbW9kZWwgcGFyYW1ldGVyIG9yIG9uZSBsaW5lYXIgY29tYmluYXRpb24gb2YgbW9kZWwgcGFyYW1ldGVycykgdGhlbiB0aGUgY2hpLXNxdWFyZSBkaXN0cmlidXRpb24gaGFzIG9uZSBkZWdyZWUgb2YgZnJlZWRvbSBhbmQgeW91IHdpbGwgcGVyZm9ybSBhIHR3by1zaWRlZCB0ZXN0LgoKIyMgRW1waXJpY2FsIG51bGwgZGlzdHJpYnV0aW9uCgpFZnJvbiAyMDA4IHJlbGF4ZXMgdGhlIHVzZSBvZiBhIHRoZW9yZXRpY2FsIG51bGwgZGlzdHJpYnV0aW9uIGZvciBhc3Nlc3Npbmcgc3RhdGlzdGljYWwgc2lnbmlmaWNhbmNlLgoKLSBIZSBzaG93cyB0aGF0IHdlIGNhbiBleHBsb2l0IHRoZSBtYXNzaXZlIHBhcmFsbGVsIGRhdGEgc3RydWN0dXJlIG9mIGhpZ2ggdGhyb3VnaHB1dCBleHBlcmltZW50cyB0byBlc3RpbWF0ZSB0aGUgZW1waXJpY2FsIG51bGwgZGlzdHJpYnV0aW9uLgoKLSBIZSBhc3N1bWVzIHRoYXQgdGhlIHRlc3Qgc3RhdGlzdGljcyBmb2xsb3cgYSBub3JtYWwgZGlzdHJpYnV0aW9uIHVuZGVyIHRoZSBudWxsLCBidXQgcHJvcG9zZXMgdG8gZXN0aW1hdGUgdGhlIGxvY2F0aW9uIGFuZCB0aGUgdmFyaWFuY2UgZW1waXJpY2FsbHkuCgpBc3N1bWluZyB0aGF0IHRoZSB0ZXN0IHN0YXRpc3RpYyBoYXMgYSBzdGFuZGFyZCBub3JtYWwgbnVsbCBkaXN0cmlidXRpb24gaXMgbm90IHJlc3RyaWN0aXZlLiBGb3IgZXhhbXBsZSwgc3VwcG9zZSB0aGF0ICR0JC10ZXN0cyBoYXZlIGJlZW4gYXBwbGllZCBhbmQgdGhhdCB0aGUgbnVsbCBkaXN0cmlidXRpb24gaXMgJHRfZCQsIHdpdGggJGQkIHJlcHJlc2VudGluZyB0aGUgZGVncmVlcyBvZiBmcmVlZG9tLiBMZXQgJEZfe3RkfSQgZGVub3RlIHRoZSBkaXN0cmlidXRpb24gZnVuY3Rpb24gb2YgJHRfZCQgYW5kIGxldCAkXFBoaSQgZGVub3RlIHRoZSBkaXN0cmlidXRpb24gZnVuY3Rpb24gb2YgdGhlIHN0YW5kYXJkIG5vcm1hbCBkaXN0cmlidXRpb24uIElmICRUJCBkZW5vdGVzIHRoZSAkdCQtdGVzdCBzdGF0aXN0aWMsIHRoZW4sIHVuZGVyIHRoZSBudWxsIGh5cG90aGVzaXMsClxbCiAgVCBcc2ltIHRfZApcXQphbmQgaGVuY2UKXFsKICBGX3t0ZH0oVCkgXHNpbSBVWzAsMV0KXF0KYW5kClxbCiAgWiA9IFxQaGleey0xfShGX3t0ZH0oVCkpIFxzaW0gTigwLDEpLgpcXQoKSWYgYWxsICRtJCBudWxsIGh5cG90aGVzZXMgYXJlIHRydWUsIHRoZW4gZWFjaCBvZiB0aGUgJFpfZyQgaXMgJE4oMCwxKSQgYW5kIHRoZSBzZXQgb2YgJG0kIGNhbGN1bGF0ZWQgJHpfZyQgdGVzdCBzdGF0aXN0aWNzIG1heSBiZSBjb25zaWRlcmVkIGFzIGEgc2FtcGxlIGZyb20gJE4oMCwxKSQuIEhlbmNlLCB1bmRlciB0aGVzZSBjb25kaXRpb25zIHdlIGV4cGVjdCB0aGUgaGlzdG9ncmFtIG9mIHRoZSAkbSQgJHpfZyQncyB0byBsb29rIGxpa2UgdGhlIGRlbnNpdHkgb2YgdGhlIG51bGwgZGlzdHJpYnV0aW9uLgoKSWYgYSBMUlQgdGVzdCBpcyBjb25kdWN0ZWQgZm9yIGEgc2luZ2xlIGNvbnRyYXN0LCB3ZSBjYW4gb2J0YWluIHRoZSBjb3JyZXNwb25kaW5nICRaX2ckIGJ5IGNvbnZlcnRpbmcgdGhlIHAtdmFsdWVzIGludG8gcXVhbnRpbGVzIG9mIHRoZSBub3JtYWwsIGkuZS4KCiR6X2cgPSBcUGhpXnstMX0gKDEtcC8yKSBcdGltZXMgXHRleHR7c2lnbn0oRkMpJAoKVGhlIG5vcm1hbCBkaXN0cmlidXRpb24gaXMgdmVyeSB1c2VmdWwgZm9yIGRpYWdub3N0aWNzIGJlY2F1c2Ugd2UgYXJlIHVzZWQgdG8gd29yayB3aXRoIGl0LgoKU28gaW4gZ2VuZXJhbCB3ZQoKMS4gU3RhcnQgb2YgdGhlIHR3by1zaWRlZCBwLXZhbHVlcy4KMi4gV2UgZGl2aWRlIHRoZSBwLXZhbHVlcyBieSB0d28gdG8gaGF2ZSB0aGUgcHJvYmFiaWxpdHkgaW4gb25lIG9mIHRoZSB0YWlscwozLiBXZSBjYWxjdWxhdGUgd2hpY2ggcXVhbnRpbGUgb2YgdGhlIG5vcm1hbCBjb3JyZXNwb25kcyB0byBpdAo0LiBXZSBnaXZlIHRoZSB6LXZhbHVlIHRoZSBzaWduIG9mIG91ciBjb250cmFzdC4KCmBgYHtyfQp0dEFsbCR0YWJsZSA8LSB0dEFsbCR0YWJsZSAlPiUKICBtdXRhdGUoeiA9IHNpZ24obG9nRkMpICogYWJzKHFub3JtKFBWYWx1ZS8yKSkpCgp0dEFsbCR0YWJsZSAlPiUKICBnZ3Bsb3QoYWVzKHg9eikpICsKICBnZW9tX2hpc3RvZ3JhbShhZXMoeSA9IC4uZGVuc2l0eS4uKSwgY29sb3IgPSAiYmxhY2siKSArCiAgc3RhdF9mdW5jdGlvbihmdW4gPSBkbm9ybSwKICAgICAgYXJncyA9IGxpc3QoCiAgICBtZWFuID0gMCwKICAgIHNkPTEpCiAgKQpgYGAKClRoZSBoaXN0b2dyYW0gY2xlYXJseSBzaG93cyB0aGF0IHRoZSB0aGVvcmV0aWNhbCBudWxsIGRpc3RyaWJ1dGlvbiBOKDAsMSkgZG9lcyBub3Qgc2VlbiB0byBtYXRjaCB0aGUgbnVsbCBkaXN0cmlidXRpb24gaW4gdGhlIGFpcndheSBkYXRhc2V0LgoKV2UgY2FuIGVtcGlyaWNhbGx5IGVzdGltYXRlIHRoZSBudWxsIGRpc3RyaWJ1dGlvbiB1c2luZyB0aGUgbG9jZmRyIHBhY2thZ2UuClRoZSBsb2NmZHIgcGFja2FnZSBhbGxvd3MgeW91IHRvIGNhbGN1bGF0ZSBsb2NhbCBmZHJzLgpJdCB1c2VzIHRoZSB0d28gZ3JvdXBzIG1vZGVsOgoKXFtmKHopID0gXHBpXzBmXzAoeikgKyAoMS1ccGlfMCkgZl8xKHopXF0KClRoZSBsb2NhbCBmZHIgb3IgcG9zdGVyaW9yIHByb2JhYmlsaXR5IHRoYXQgdGhlIGdlbmUgd2l0aCBhIGNlcnRhaW4gdGVzdCBzdGF0aXN0aWMgeiBpcyBhIGZhbHNlIHBvc2l0aXZlIHRoZW4gYmVjb21lcwoKXFtsZmRyID0gXGZyYWN7XHBpXzAgZl8wKHopfXtmKHopfSBcXQoKRWZyb24gc3VnZ2VzdHMgdG8gdXNlIGEgY3V0b2ZmIGZvciB0aGUgbGZkciBvZiAyMCUuIFNvIHdlIHJldHVybiBhbGwgZ2VuZXMgZm9yIHdoaWNoIHRoZSBwcm9iYWJpbGl0eSB0aGF0IHRoZXkgYXJlIGZhbHNlIHBvc2l0aXZlcyBpcyBiZWxvdyAyMCUuIEhlIGNsYWltcyB0aGF0IHRoaXMgY29ycmVzcG9uZHMgdG8gYSBjb252ZW50aW9uYWwgRkRSIG9mIGFib3V0IDUlIGluIHRoZSBzZXQgdGhhdCB5b3UgcmV0dXJuLgoKSXQgY2FuIGJlIHNob3duIHRoYXQgdGhlIEZEUjoKClxbCkZEUiA9IEVbbGZkcl0gXGFwcHJveCBcZnJhY3tcc3VtXGxpbWl0c197ayBcaW4gREUtc2V0fSBsZmRyX2t9e25fXHRleHR7REV9fQpcXQoKV2UgY2FuIGFsc28gZXN0aW1hdGUgdGhlIGdsb2JhbCBGRFIgYnkgc2ltcGx5IGNhbGN1bGF0aW5nIHRoZSBhdmVyYWdlIGxmZHIgaW4gdGhlIHNldCB0aGF0IHdlIHJldHVybi4KCmBgYHtyfQpsaWJyYXJ5KGxvY2ZkcikKdHRBbGwkdGFibGUgPC0gdHRBbGwkdGFibGUgJT4lCiAgbXV0YXRlKGxmZHIgPSBsb2NmZHIoeikkZmRyKQpgYGAKCkluIHRoZSBwbG90IHdlIHNlZSB0aGUgaGlzdG9ncmFtIG9mIHRoZSB6LXZhbHVlcy4KCi0gVGhlIGdyZWVuIGxpbmUgaXMgdGhlIGVzdGltYXRlIG9mIHRoZSBtYXJnaW5hbCBkaXN0cmlidXRpb24gJGYoeikkLiBBIG5vbi1wYXJhbWV0ZXJpYyBkZW5zaXR5IGVzdGltYXRvciBpcyB1c2VkIGZvciB0aGlzIHB1cnBvc2UuCi0gVGhlIGJsdWUgbGluZSBpcyB0aGUgZXN0aW1hdGUgb2YgdGhlIG51bGwgZGlzdHJpYnV0aW9uLgotIFdlIHNlZSB0aGF0IG51bGwgZGlzdHJpYnV0aW9uIGFwcGVhcnMgdG8gYmUgbXVjaCBicm9hZGVyIHRoYW4gdGhlIHN0YW5kYXJkIG5vcm1hbCBhbmQgaXQgc2hvd3MgYSBzbGlnaHQgc2hpZnQuCi0gV2Ugc2VlIHRoYXQgdGhlIG1hcmdpbmFsIGRpc3RyaWJ1dGlvbiAoZ3JlZW4gZGlzdHJpYnV0aW9uKSBpcyBub3QgZXN0aW1hdGVkIHdlbGwuCi0gV2UgYWxzbyBnZXQgYSB3YXJuaW5nIG1lc3NhZ2UgdGhhdCBpbmRpY2F0ZXMgdGhhdCB3ZSBjYW4gaW5jcmVhc2UgdGhlIGRlZ3JlZXMgb2YgZnJlZWRvbS4KCldlIHJlLWVzdGltYXRlICRmKHopJCBieSB1c2luZyBtb3JlIGRlZ3JlZXMgb2YgZnJlZWRvbSwgZS5nLiBgZGYgPSAyMGAuCgpgYGB7cn0KdHRBbGwkdGFibGUgPC0gdHRBbGwkdGFibGUgJT4lCiAgbXV0YXRlKGxmZHIgPSBsb2NmZHIoeiwgZGYgPSAyMCkkZmRyKQpgYGAKCgoKRXN0aW1hdGVkIEZEUiBjb3JyZXNwb25kaW5nIHRvIHRoZSBzZXQgb2YgZ2VuZXMgd2l0aCBsZmRyIDwgMC4yIGFuZCBudW1iZXIgb2Ygc2lnbmlmaWNhbnQgZ2VuZXMgd2l0aCBsZmRyIDwgMC4yPwoKYGBge3J9CnR0QWxsJHRhYmxlICU+JQogIGZpbHRlcihsZmRyIDwgMC4yKSAlPiUKICBzdW1tYXJpemUoCiAgICBGRFIgPSBtZWFuKGxmZHIsIG5hLnJtID0gVFJVRSksCiAgICBuU2lnID0gbGZkciAlPiUKICAgICAgaXMubmEgJT4lCiAgICAgIGAhYCAlPiUKICAgICAgc3VtKQpgYGAKCk5vdGUsIHRoYXQKCi0gdGhlIEZEUiBvZiB0aGUgc2V0IHRoYXQgaXMgcmV0dXJuZWQgaXMgaW5kZWVkIGNsb3NlIHRvIDAuNS4KLSB0aGUgbnVtYmVyIG9mIHNpZ25pZmljYW50IGdlbmVzIGhhcyBiZWVuIHJlZHVjZWQgY29uc2lkZXJhYmx5LgotIEl0IGlzIHZlcnkgaW1wb3J0YW50IHRvIGV2YWx1YXRlIHRoZSBmaXQgb2YgdGhlIG51bGwgYW5kIG1hcmdpbmFsIGRpc3RyaWJ1dGlvbiBpbiB0aGUgcGxvdC4KCklmIHlvdSB3b3VsZCBsaWtlIHRvIG9wdCB0byB1c2UgdGhlIEZEUiBtZXRob2Qgb2YgQmVuamFtaW5pIGFuZCBIb2NoYmVyZywgeW91IGFsc28gY291bGQgY29udmVydCB0aGUgei12YWx1ZXMgYmFjayBpbiBwLXZhbHVlcyBieSB1c2luZyBhIG5vcm1hbCAkTihcaGF0IFxtdSwgXGhhdCBcc2lnbWFeMikkLCB3aGVyZSB3ZSB1c2UgdGhlIGVzdGltYXRlZCBwYXJhbWV0ZXJzIGZvciB0aGUgbnVsbCBkaXN0cmlidXRpb24gYnkgbG9jZmRyLgoKYGBge3J9CmggPC0gdHRBbGwkdGFibGUgJT4lCiAgcHVsbCh6KSAlPiUKICBsb2NmZHIoZGYgPSAyMCwgcGxvdD1GQUxTRSkKCnR0QWxsJHRhYmxlIDwtIHR0QWxsJHRhYmxlICU+JQogIG11dGF0ZShwRW1wID0gcG5vcm0oCiAgICBhYnMoeiksCiAgICBtZWFuID0gaCRmcDBbIm1sZXN0IiwiZGVsdGEiXSwKICAgIHNkID0gaCRmcDBbIm1sZXN0Iiwic2lnbWEiXSwKICAgIGxvd2VyID0gRkFMU0UpICogMgogICAgKSAlPiUKICBtdXRhdGUocEFkakVtcCA9IHAuYWRqdXN0KAogICAgcEVtcCwKICAgIG1ldGhvZD0iQkgiKQogICAgKQoKdHRBbGwkdGFibGUgJT4lCiAgZmlsdGVyKHBBZGpFbXAgPCAwLjA1KSAlPiUKICBucm93CmBgYAoKV2Ugb2JzZXJ2ZSB0aGF0IHRoZSBudW1iZXIgb2Ygc2lnbmlmaWNhbnQgZ2VuZXMgcmVkdWNlcyB0byBhYm91dCB0aGUgc2FtZSBhbW91bnQgYXMgd2l0aCB0aGUgbGZkciBtZXRob2Qgb2YgRWZyb24uCldlLCBob3dldmVyLCBkaWQgbm90IGhhdmUgdG8gdXNlIGEgZGVuc2l0eSBlc3RpbWF0b3IgZm9yIHRoZSBtYXJnaW5hbCBjdW11bGF0aXZlIGRpc3RyaWJ1dGlvbiBmdW5jdGlvbiBvZiB0aGUgdGVzdCBzdGF0aXN0aWNzLiBJbnN0ZWFkLCB0aGUgQkggbWV0aG9kIHVzZXMgdGhlIGVtcGlyaWNhbCBkaXN0cmlidXRpb24gb2YgdGhlIHN0YXRpc3RpY3MuCgojIyAgQXNzZXNzIHdoeSBkZXZpYXRpb25zIGZyb20gdGhlIG51bGwgb2NjdXI/CgojIyMgRmFpbGVkIG1hdGhlbWF0aWNhbCBhc3N1bXB0aW9ucz8KCklmIHdlIHBlcm11dGUgdGhlIGdlbmUgZXhwcmVzc2lvbiBkYXRhIG9mIGFsbCBvYnNlcnZhdGlvbnMgZGlmZmVyZW50bHkgZm9yIGV2ZXJ5IGdlbmUsIHdlIHNpbXVsYXRlIGV4cHJlc3Npb25zIHVuZGVyIHRoZSBudWxsIGFuZCBicmVha3VwIHRoZSBjb3JyZWxhdGlvbiBzdHJ1Y3R1cmUgYmV0d2VlbiB0aGUgZ2VuZXMuCgpgYGB7cn0Kc2V0LnNlZWQoMTAwNCkKZGdlUGVybUFsbCA8LSBkZ2UKZGdlUGVybUFsbCRjb3VudHMgPC0gYXBwbHkoZGdlJGNvdW50cywgMSwgc2FtcGxlKSAgJT4lIHQKZGdlUGVybUFsbCRzYW1wbGVzJGxpYi5zaXplIDwtICBkZ2VQZXJtQWxsJGNvdW50cyAlPiUgY29sU3VtcwpkZ2VQZXJtQWxsIDwtIGNhbGNOb3JtRmFjdG9ycyhkZ2VQZXJtQWxsKQoKZGdlUGVybUFsbCA8LSBlc3RpbWF0ZURpc3AoZGdlUGVybUFsbCwgZGVzaWduKQpwbG90QkNWKGRnZVBlcm1BbGwpCgpmaXRQZXJtQWxsIDwtIGdsbUZpdChkZ2VQZXJtQWxsLCBkZXNpZ24pCmxydFBlcm1BbGwgPC0gZ2xtTFJUKGZpdFBlcm1BbGwsIGNvZWYgPSAidHJlYXRtZW50RGV4YW1ldGhhc29uZSIpCnR0QWxsUGVybUFsbCA8LSB0b3BUYWdzKGxydFBlcm1BbGwsIG4gPSBucm93KGRnZVBlcm1BbGwpKQoKdHRBbGxQZXJtQWxsJHRhYmxlIDwtIHR0QWxsUGVybUFsbCR0YWJsZSAlPiUKICBtdXRhdGUoeiA9IHNpZ24obG9nRkMpICogYWJzKHFub3JtKFBWYWx1ZS8yKSkpCgp0dEFsbFBlcm1BbGwkdGFibGUgJT4lCiAgZ2dwbG90KGFlcyh4PXopKSArCiAgZ2VvbV9oaXN0b2dyYW0oYWVzKHkgPSAuLmRlbnNpdHkuLiksIGNvbG9yID0gImJsYWNrIikgKwogIHN0YXRfZnVuY3Rpb24oZnVuID0gZG5vcm0sCiAgICBhcmdzID0gbGlzdCgKICAgIG1lYW4gPSAwLAogICAgc2Q9MSkKICApCmBgYAoKV2Ugb2JzZXJ2ZSB0aGF0IHRoZSBudWxsIGRpc3RyaWJ1dGlvbiBpcyBhcHByb3hpbWF0ZWx5IGZvbGxvd2luZyBhIHN0YW5kYXJkIG5vcm1hbCBkaXN0cmlidXRpb24uClRoZXJlIGlzIG5vIHNoaWZ0IGFuZCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIGluIG5vIGxvbmdlciBsYXJnZXIgdGhhbiAxLgoKSGVuY2UsIHRoZXJlIGRvIG5vdCBzZWVtIHRvIGJlIGlzc3VlcyByZWxhdGVkIHRvIGZhaWxlZCBtYXRoZW1hdGljYWwgYXNzdW1wdGlvbnMuCgojIyMgQ29ycmVsYXRpb24gb2YgdGhlIGdlbmVzPwoKV2Ugd2lsbCBub3cgb25seSBwZXJtdXRlIHRoZSBzYW1wbGVzIGFjcm9zcyBjb25kaXRpb25zLCBidXQsIHdlIGtlZXAgYWxsIGdlbmVzIHRvZ2V0aGVyLCBlLmcuIGJ5IHBlcm11dGluZyB0aGUgZGVzaWduIG1hdHJpeC4KClRoaXMgc2ltdWxhdGVzIGRhdGEgZnJvbSB0aGUgbnVsbCBhbmQgYnJlYWtzIHRoZSBhc3NvY2lhdGlvbiBiZXR3ZWVuIHRoZSBwcmVkaWN0b3JzIGFuZCBwb3RlbnRpYWwgY29uZm91bmRlcnMsIGhvd2V2ZXIsIGNvcnJlbGF0aW9uIGJldHdlZW4gdGhlIGdlbmVzIHJlbWFpbnMuCgpIZXJlLCB3ZSBoYXZlIGEgYmxvY2sgZGVzaWduIHNvIHdlIHdpbGwgcGVybXV0ZSB3aXRoaW4gYmxvY2suCldlIHdpbGwgcGVyZm9ybSBhIGJhbGFuY2VkIHBlcm11dGF0aW9uLgpXZSB3aWxsIHNlbGVjdCB0d28gY2VsbGluZXMgYXQgcmFuZG9tIGFuZCB3ZSB3aWxsIHBlcm11dGUgdGhlIGxhYmVscyBvZiB0aGUgdHJlYXRtZW50LgoKYGBge3J9CmRlc2lnblBlcm0gPC0gZGVzaWduCgpjZWxsTGluZSA8LSBzYW1wbGUoMDozLDIpCmNlbGxMaW5lCgpmb3IgKGkgaW4gY2VsbExpbmUpCiAgZGVzaWduUGVybVtpKjIgKyAxOjIsIDJdIDwtIGMoMSwwKQpkZXNpZ25QZXJtCgoKZml0UGVybVNhbXAgPC0gZ2xtRml0KGRnZSwgZGVzaWduUGVybSkKbHJ0UGVybVNhbXAgPC0gZ2xtTFJUKGZpdFBlcm1TYW1wLCBjb2VmID0gInRyZWF0bWVudERleGFtZXRoYXNvbmUiKQp0dEFsbFBlcm1TYW1wIDwtIHRvcFRhZ3MobHJ0UGVybVNhbXAsIG4gPSBucm93KGRnZSkpCgp0dEFsbFBlcm1TYW1wJHRhYmxlIDwtIHR0QWxsUGVybVNhbXAkdGFibGUgJT4lCiAgbXV0YXRlKHogPSBzaWduKGxvZ0ZDKSAqIGFicyhxbm9ybShQVmFsdWUvMikpKQoKdHRBbGxQZXJtU2FtcCR0YWJsZSAlPiUKICBnZ3Bsb3QoYWVzKHg9eikpICsKICBnZW9tX2hpc3RvZ3JhbShhZXMoeSA9IC4uZGVuc2l0eS4uKSwgY29sb3IgPSAiYmxhY2siKSArCiAgc3RhdF9mdW5jdGlvbihmdW4gPSBkbm9ybSwKICBhcmdzID0gbGlzdCgKICAgIG1lYW4gPSAwLAogICAgc2Q9MSkKICApCmBgYAoKV2Ugb2JzZXJ2ZSB0aGF0IHRoZSBudWxsIGRpc3RyaWJ1dGlvbiBpcyBhcHByb3hpbWF0ZWx5IG1hdGNoaW5nIHdpdGggYSBzdGFuZGFyZCBub3JtYWwuClRoZXJlIGlzIG5vIHNoaWZ0IGFuZCB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIGluIG5vIGxvbmdlciBsYXJnZXIgdGhhbiAxLgpIZXJlLCB0aGUgZGlzdHJpYnV0aW9uIHNlZW1zIHRvIGJlIGEgYml0IG1vcmUgbmFycm93IHRoYW4gdGhlIHRoZSB0aGVvcmV0aWNhbCBkaXN0cmlidXRpb24uICAKCgojIyMjIFJlcGVhdCBmb3Igb3RoZXIgcGVybXV0YXRpb246CgpgYGB7cn0KZGVzaWduUGVybSA8LSBkZXNpZ24KCmNlbGxMaW5lIDwtIGMoMCwyKQpjZWxsTGluZQoKZm9yIChpIGluIGNlbGxMaW5lKQogIGRlc2lnblBlcm1baSoyICsgMToyLCAyXSA8LSBjKDEsMCkKZGVzaWduUGVybQoKZml0UGVybVNhbXAgPC0gZ2xtRml0KGRnZSwgZGVzaWduUGVybSkKbHJ0UGVybVNhbXAgPC0gZ2xtTFJUKGZpdFBlcm1TYW1wLCBjb2VmID0gInRyZWF0bWVudERleGFtZXRoYXNvbmUiKQp0dEFsbFBlcm1TYW1wIDwtIHRvcFRhZ3MobHJ0UGVybVNhbXAsIG4gPSBucm93KGRnZSkpCgp0dEFsbFBlcm1TYW1wJHRhYmxlIDwtIHR0QWxsUGVybVNhbXAkdGFibGUgJT4lCiAgbXV0YXRlKHogPSBzaWduKGxvZ0ZDKSAqIGFicyhxbm9ybShQVmFsdWUvMikpKQoKcFBlcm1TYW1wIDwtIHR0QWxsUGVybVNhbXAkdGFibGUgJT4lCiAgZ2dwbG90KGFlcyh4PXopKSArCiAgZ2VvbV9oaXN0b2dyYW0oYWVzKHkgPSAuLmRlbnNpdHkuLiksIGNvbG9yID0gImJsYWNrIikgKwogIHN0YXRfZnVuY3Rpb24oZnVuID0gZG5vcm0sCiAgYXJncyA9IGxpc3QoCiAgICBtZWFuID0gMCwKICAgIHNkPTEpCiAgKQpwUGVybVNhbXAKcFBlcm1TYW1wICsgeGxpbSgtNCw0KQpgYGAKCkJvdGggcGVybXV0YXRpb25zIHNob3cgdGhhdCB0aGVyZSBhcmUgbm8gZGV2aWF0aW9ucyBmcm9tIHRoZSB0aGVvcmV0aWNhbCBudWxsIHdoZW4gd2Ugc2ltdWxhdGUgdW5kZXIgdGhlIG51bGwgYW5kIGJyZWFrIHBvdGVudGlhbCBjb25mb3VuZGluZyBidXQgbGVhdmUgY29ycmVsYXRpb24gYmV0d2VlbiBnZW5lcyBpbnRhY3QuCgpTbyB0aGVyZSBzZWVtcyB0byBiZSBhbm90aGVyIHJlYXNvbiBmb3IgZGV2aWF0aW9ucyBvZiB0aGUgbnVsbCwgdGhhbiBmYWlsZWQgbWF0aGVtYXRpY2FsIGFzc3VtcHRpb25zIGFuZCBjb3JyZWxhdGlvbiBiZXR3ZWVuIGdlbmVzIQoKUGVyaGFwcyBjb25mb3VuZGVycyB0aGF0IHdlIGRvIG5vdCBhY2NvdW50IGZvcj8KCiMjIENvbmNsdWRpbmcgcmVtYXJrCgpUaGlzIGV4YW1wbGUgYWxzbyBjbGVhcmx5IHNob3dzIHRoYXQgYWx0aG91Z2ggcGVybXV0YXRpb24gbWV0aG9kcyBvZmZlciBhIHNpbXBsZSBhbmQgYXR0cmFjdGl2ZSB3YXkgdG8gZGVhbCB3aXRoIG1hdGhlbWF0aWNhbGx5IGNvbXBsaWNhdGVkIGh5cG90aGVzaXMgdGVzdGluZyBzaXR1YXRpb25zLCAgdGhleSBvZnRlbiBjYW5ub3QgcmVtZWR5IGZhaWx1cmVzIG9mIHRoZSB0aGVvcmV0aWNhbCBudWxsLgoKU28gdGhlIHVzZSBvZiBwZXJtdXRhdGlvbnMgdG8gZXN0YWJsaXNoIHRoZSBudWxsIGRpc3RyaWJ1dGlvbiBzaG91bGQgYWxzbyBiZSB1c2VkIHdpdGggY2FyZSBpbiBoaWdoIHRocm91Z2hwdXQgY29udGV4dHMuIEluZGVlZCwgZGVwZW5kaW5nIG9uIHRoZSBwZXJtdXRhdGlvbiBzY2hlbWUgdGhhdCBpcyB1c2VkIHlvdSBtaWdodCBicmVhayBjb3JyZWxhdGlvbnMgYmV0d2VlbiBnZW5lcywgc2FtcGxlcyBhbmQvb3IgcG90ZW50aWFsIGNvbmZvdW5kaW5nLiAgCgpTbyBldmVuIGlmIHlvdSB1c2UgYSBwZXJtdXRhdGlvbiBhcHByb2FjaCBpbiBhIGhpZ2ggdGhyb3VnaHB1dCBjb250ZXh0LCBlLmcuIGEgd2lsY294b24gcmFuayBzdW0gdGVzdCBvciBvdGhlciBwZXJtdXRhdGlvbiBiYXNlZCB0ZXN0cywgeW91IHN0aWxsIG1pZ2h0IG5lZWQgdG8gY2hlY2sgZm9yIGRldmlhdGlvbnMgb2YgdGhlIG51bGwhCg==