library(tidyverse)
Registered S3 methods overwritten by 'dbplyr':
  method         from
  print.tbl_lazy     
  print.tbl_sql      
── Attaching packages ─────────────────────────────── tidyverse 1.3.0 ──
✓ ggplot2 3.3.2     ✓ purrr   0.3.4
✓ tibble  3.0.1     ✓ dplyr   1.0.0
✓ tidyr   1.1.0     ✓ stringr 1.4.0
✓ readr   1.3.1     ✓ forcats 0.5.0
── Conflicts ────────────────────────────────── tidyverse_conflicts() ──
x dplyr::filter() masks stats::filter()
x dplyr::lag()    masks stats::lag()

Load data

tab <- read_csv("../data/Ex009_experiment_set_up_20171019.csv")
Parsed with column specification:
cols(
  ALT_ID = col_character(),
  Sample = col_character(),
  Strain = col_character(),
  Genotype = col_character(),
  Replicate = col_double(),
  Timepoint = col_character()
)
dat <- read_tsv("../data/Ex009_normalized_log2_read_counts.zip")
Parsed with column specification:
cols(
  .default = col_double(),
  gene = col_character()
)
See spec(...) for full column specifications.

Prepare data

In this analysis we will focus on the “wt” samples,
# choose the samples to use and convert the time points to numeric variable
time2num <- c("pre" = 0, "20m" = 20, "30m" = 30, "45m" = 45, "60m" = 60,
               "90m" = 90, "120m" = 120, "150m" = 150, "180m" = 180, 
               "240m" = 240)
samples.use <- tab %>% 
  filter(Genotype == "wt", Timepoint != "del80") %>% 
  mutate(Time = time2num[Timepoint]) %>% 
  select(Sample, Time)

# extract the list of sample names
wt.list <- samples.use$Sample

# subset the data
dat1 <- dat %>% select(gene, all_of(wt.list))

# there are technical duplicates for each time point. for our purpose
# we just need one value per time point. It is sensible to compute the 
# mean value for each gene at each time point. to do this we first convert
# the data table into a long format, which allows for aggregation functions
dat1.long <- dat1 %>% 
  pivot_longer(starts_with("S"), names_to = "sample") %>% 
  left_join(samples.use, by = c("sample" = "Sample")) %>% 
  select(gene, time = Time, exn = value)

# calculate mean value for each timepoint within each gene
dat1.aggr <- dat1.long %>% 
  group_by(gene, time) %>% 
  summarize(avg.exn = mean(exn), sd.exn = sd(exn), .groups = "drop_last") %>%  
  # subtract the value of the first timepoint from the 
  # rest to form relative expression level (baseline)
  mutate(rel.exn = avg.exn - first(avg.exn))

# convert the long format back to the wide format for extracting matrix
dat1.wide <- dat1.aggr %>% 
  pivot_wider(id_cols = gene, names_from = time, values_from = avg.exn)

dat2.wide <- dat1.aggr %>% 
  pivot_wider(id_cols = gene, names_from = time, values_from = rel.exn)

# convert the result into a matrix for downstream analysis
m.dat1 <- as.matrix(dat1.wide[,-1])
rownames(m.dat1) <- dat1.wide$gene

m.dat2 <- as.matrix(dat2.wide[,-1])
rownames(m.dat2) <- dat2.wide$gene

Calculate distance (dissimilarity) between genes

Our goal is to group genes based on their temporal profile, that is, genes that share the same temporal pattern, such as increase in expression over time, should be grouped together.

For example, here are some genes known to be induced after starvation:

# plot examples
exp.list <- paste0("CAGL0",c("B02475g", "F02145g", "K10868g", "J04202g"))
exp.label <- paste(exp.list, c("PHO84","PHM2","CTA1","HSP12"), sep = " ")
names(exp.label) <- exp.list
dat1.aggr %>% 
  filter(gene %in% exp.list) %>% 
  ggplot(aes(x = time, y = rel.exn)) + geom_line() + geom_point(shape = 0) +
  geom_errorbar(aes(ymin = rel.exn - 1.96*sd.exn, 
                    ymax = rel.exn + 1.96*sd.exn)) +
  facet_wrap(~gene, labeller = labeller(gene = exp.label)) + 
  xlab("time (min)") + ylab("log2 normalized mRNA counts - time_0") +
  labs(caption = "points are average of at least two biological replicates\nerror bars are 95% confidence intervals") +
  theme(plot.caption = element_text(hjust = 0))

And here are genes that are not expected to respond to phosphate starvation:

# plot examples
exp.list <- paste0("CAGL0",c("K12694g", "K05005g", "D06138g", "D05170g"))
exp.label <- paste(exp.list, c("ACT1","ALG9","HEM2","PHO4"), sep = " ")
names(exp.label) <- exp.list
dat1.aggr %>% 
  filter(gene %in% exp.list) %>% 
  ggplot(aes(x = time, y = rel.exn)) + geom_line() + geom_point(shape = 0) +
  geom_errorbar(aes(ymin = rel.exn - 1.96*sd.exn, 
                    ymax = rel.exn + 1.96*sd.exn)) +
  facet_wrap(~gene, labeller = labeller(gene = exp.label)) + ylim(-5,5) +
  xlab("time (min)") + ylab("log2 normalized mRNA counts - time_0") +
  labs(caption = "points are average of at least two biological replicates\nerror bars are 95% confidence intervals") +
  theme(plot.caption = element_text(hjust = 0))

A toy example

In order to cluster genes based on this criteria, we need to first quantify the dissimilarity between genes. Here we are less interested in the “magnitude” of gene expression than the “profile” or temporal dynamics of gene expression. In the above example, notice that the absolute maximum expression levels of the four genes differ a lot. However, they all show the same “pattern”, i.e. an early rise followed by sustained expression. Let’s look at a simple example consisting of four genes and four time points:

toy <- matrix(c(2,4,4,4,6,6,3,2,20,40,40,40,45,45,35,20), 
              byrow = T, nrow = 4, 
              dimnames = list(gene = paste("gene", 1:4), 
                              time = c(10,20,30,40)))
toy
        time
gene     10 20 30 40
  gene 1  2  4  4  4
  gene 2  6  6  3  2
  gene 3 20 40 40 40
  gene 4 45 45 35 20
plot(x = 1, type = "n", xlim = c(10,50), ylim = c(0, 50))
t = c(10,20,30,40)
for(i in 1:4){
  points(t, toy[i,], pch = i)
  lines(t, toy[i,])
}
legend("topright", legend = rownames(toy), pch = 1:4)

Scaling to the rescue

Although the scales make it a bit difficult to see, but one can tell that genes 1 and 3 “rise” over time while genes 2 and 4 “fall” over time. The question is, how can we turn that intuition into a number that can be calculated from the data? One idea is to “scale” the data by subtracting the mean expression level across time of each gene from each time point, and divide the result by the standard deviation of the four time points. This will “center” and standardize the genes.

toy.scaled <- scale(t(toy)) # note that most r functions operate on columns
# since we want to operate on the time series, we transpose the matrix so
# that each gene is in a column
matplot(t, toy.scaled, type = "b", pch = 1:4, lty = 1, col = 1)
legend("topright", colnames(toy.scaled), pch = 1:4)

dist() function

Now the (dis)similarity patterns are more clear. But we still don’t have a number. We can now calculate the “Euclidian distance” between each pair of genes. In a 2D or 3D space, this measure would be the familiar “distance”. In higher dimensions such as here (each gene is a data point in a 4-D space spanned by their expression levels at each of the four time points), the idea would be the same, where \(D := \sqrt{\sum_{i=1}^{4}(x_i-y_i)^2}\). Using the dist() function, we found the result to be

dist(t(toy.scaled)) # dist() computes the distance between rows
          gene 1    gene 2    gene 3
gene 2 3.0652078                    
gene 3 0.0000000 3.0652078          
gene 4 2.9937354 0.5955187 2.9937354

Compare this to the result had we applied the function on the unscaled raw data

dist(toy)
         gene 1   gene 2   gene 3
gene 2  5.00000                  
gene 3 64.89992 64.53681         
gene 4 68.89848 66.25708 32.78719

Pearson’s Correlation Coefficient as another way to measure similarity

There is another way to quantify the dissimilarity between the expression patterns of the genes: calculate the Pearson’s correlation coefficient between the time series and subtract it from 1. The Pearson’s correlation coefficient describes the colinearity between two variables. Often written as “r”, it is closely related to linear regression. In fact, you may well have seen “r” or “\(R^2\)” written on plots with linear regression lines. Intuitively, two time series are perfectly positively correlated if they rise or fall together, and perfectly anti-correlated if they have the opposite pattern. In the example above, gene 1 and 3 would have a Pearson’s correlation coefficient of +1. Now let’s compute the results for all pairs:

Note

cor() computes the pairwise correlation between COLUMNS of a matrix and therefore we need to transpose the original matrix

cor(t(toy))
           gene 1     gene 2     gene 3     gene 4
gene 1  1.0000000 -0.5659165  1.0000000 -0.4937419
gene 2 -0.5659165  1.0000000 -0.5659165  0.9408929
gene 3  1.0000000 -0.5659165  1.0000000 -0.4937419
gene 4 -0.4937419  0.9408929 -0.4937419  1.0000000

Compare this to the result using the untransposed matrix, which shows the correlations between time points (this may be of interest as well).

cor(toy)
          10        20        30        40
10 1.0000000 0.8948817 0.7860212 0.5019804
20 0.8948817 1.0000000 0.9788613 0.8351485
30 0.7860212 0.9788613 1.0000000 0.9288416
40 0.5019804 0.8351485 0.9288416 1.0000000

Note that we don’t have to scale the original data because the calculation of correlation includes the scaling (see wiki)

Clustering genes

Armed with two different ways to measure the distance or similarity between genes, we can now move on to cluster the genes and visualize them with the aheatmap() function from the NMF package.

Use Euclidean distance

# we first use the Euclidean distance on the scaled matrix
# note that dist() operates on the rows
t(toy.scaled)
        time
gene             10        20         30        40
  gene 1 -1.5000000 0.5000000  0.5000000  0.500000
  gene 2  0.8488747 0.8488747 -0.6063391 -1.091410
  gene 3 -1.5000000 0.5000000  0.5000000  0.500000
  gene 4  0.7406129 0.7406129 -0.1058018 -1.375424
attr(,"scaled:center")
gene 1 gene 2 gene 3 gene 4 
  3.50   4.25  35.00  36.25 
attr(,"scaled:scale")
   gene 1    gene 2    gene 3    gene 4 
 1.000000  2.061553 10.000000 11.814539 
toy.dist1 <- dist(t(toy.scaled), method = "euclidean")
toy.dist1
          gene 1    gene 2    gene 3
gene 2 3.0652078                    
gene 3 0.0000000 3.0652078          
gene 4 2.9937354 0.5955187 2.9937354
toy.clust1 <- hclust(toy.dist1)
plot(toy.clust1)

Use correlation matrix

# remember that cor() operates on the columns
t(toy)
    gene
time gene 1 gene 2 gene 3 gene 4
  10      2      6     20     45
  20      4      6     40     45
  30      4      3     40     35
  40      4      2     40     20
toy.dist2 <- 1-cor(t(toy))
toy.dist2
         gene 1     gene 2   gene 3     gene 4
gene 1 0.000000 1.56591646 0.000000 1.49374193
gene 2 1.565916 0.00000000 1.565916 0.05910708
gene 3 0.000000 1.56591646 0.000000 1.49374193
gene 4 1.493742 0.05910708 1.493742 0.00000000
toy.clust2 <- hclust(as.dist(toy.dist2))
plot(toy.clust2)

Notice that the topologies are the same but the tree height units are different between the two. But that doesn’t concern us.

Before we apply what we learned to our actual gene expression dataset, let’s look at one more thing, that is, how heatmap() function works.

Dissecting the heatmap() function

Brief explanation

heatmap() actually involves a series of steps. First the function applies, by default, the hierarchical clustering algorithm on both the rows and the columns based on the input data (non-scaled). It then reorders the rows and the columns to match the order after the clustering. Note, however, the clustering is done on the unscaled data. This is especially confusing because the base R’s heatmap() function has an argument called scaled. This, however, only affects how the data are plotted, not how they are clustered. Note that this clustering step can be skipped by setting Rowv = NA and Colv = NA, each of which controls whether clustering and reordering is done for the rows and the columns respectively.

Once the rows and columns are reordered, unless disabled by the arguments shown above, the function then checks the value of scale. The default for this argument depends on the value of another argument, symm, whose default is false. If “symm” is false, scale defaults to “row”, i.e. scaling by row. Otherwise, scaling is off.

After reordering and scaling, if applicable, heatmap() then transposes the resulting matrix and plots it using the base function image(). We will see the reason for transposin the matrix later. Let’s first understand how image() works. This function simply draws rectangles and colors them by the value given. Note there is something nonintuitive about the mapping from the matrix to the image – the image() function draws a cartesian coordinate with (0,0) at the lower left corner. It then colors the square corresponding to (i,j) to the value of X[i,j] in the matrix. If you follows me so far, you realize that the while in the matrix the first index is the row and the second the column, in the image, the rows now become the x-axis and the columns the y-axis. Essentially, the matrix has been rotated 90 degrees counterclockwise.

Using the image() function

Now let’s look at the toy example to understand these intuitively. First, if we directly apply image() to the toy data, this is what we get

image(x = 1:4, y = c(10,20,30,40), z = toy, xlab = "gene", ylab = "time (min)", xaxt = "n", yaxt = "n")
axis(side = 1, at = 1:4, labels = rownames(toy))
axis(side = 2, at = c(10,20,30,40), labels = colnames(toy))

Next we use the heatmap() function without clustering or scaling

heatmap(toy, Rowv = NA, Colv = NA, scale = "none")

Once we imagine that the row labels be moved to the left side, we realize that the heatmap() function effectively swapped the rows and the columns, i.e. transposed the matrix. Presumably, this makes the rows and columns appear nearly the same as the input matrix. I say “nearly” because – notice that – the row orders were reversed, again because in a plot, (0,0) is in the lower left corner.

Adding the clustering based reordering

Now let’s add the clustering – note that we only want to cluster the genes, and would like to keep the time points in their original order, for obvious reasons. To achieve this, we realize that time series are in the columns. So we just need to set Colv = NA, while leaving Rowv = NULL, which means it uses the default clustering order.

# with row clustering
heatmap(toy, Rowv = NULL, Colv = NA, scale = "none")

Adding scaling doesn’t change the reordering

We found that the clustering is not what we have expected, i.e. gene 1/3 and gene 2/4. This is because by default heatmap() clusters the rows based on the unscaled values. So what if we set scale = "row"? Let’s see:

#heatmap with row scaling and clustering
heatmap(toy, Rowv = NULL, Colv = NA, scale = "row")

Implement the reordering step outside the heatmap() function

So now the plotted colors match the scaled values, but the clustering order is still the original! This shows that the scaling step is only for plotting, not for reordering. We can actually implement the ordering step outside of the heatmap() function

# below is how reordering is done inside the heatmap function
# recall that we have set toy.dist1 = dist(toy)
toy.dist1
          gene 1    gene 2    gene 3
gene 2 3.0652078                    
gene 3 0.0000000 3.0652078          
gene 4 2.9937354 0.5955187 2.9937354
# we can then cluster the genes using this distance matrix, which we stored as toy.clust1
plot(toy.clust1)

# we can then use this order in the heatmap
heatmap(toy, Rowv = as.dendrogram(toy.clust1), Colv = NA, scale = "row")

Now this is what we would have expected. This tells us that if we should think of heatmap and clustering as two steps, even though the heatmap() function in base R and many of its variations combine the two. This helps use clearly define

  1. which variable do we want to cluster, the genes or the time series (or any other dimension)?
  2. how do we want to measure the dissimilarity (distance) – by Euclidean disance or Pearson’s Correlation Coefficient?
  3. how do we want to visualize the data, e.g. whether to reorder the rows or columns, whether to plot scaled or unscaled data etc. Note that scaling would remove the difference between genes in their absolute expression level, leaving only the temporal dynamics visible. Sometimes that may be exactly what we want, while in other cases that may not be desirable.

Apply to our data

plot the raw data, scaled or not

Since we are interested in genes that change their expression over the time course, it is natural to first look at the distribution of maximum change in expression for each gene over all time points, and then choose a cutoff and only select those genes with maximum change in expression greater than that cutoff.

# check distribution of changes
dat1.aggr %>% 
  group_by(gene) %>% 
  summarize(max.exn = max(abs(rel.exn))) %>% 
  ggplot(aes(max.exn)) + stat_ecdf(geom = "step") +
  scale_x_continuous(breaks = -1:15) +
  xlab("log2 maximum fold change in expression relative to time_0") +
  ylab("cumulative # of genes") +
  ggtitle("Cumulative distribution of maximum fold change in expression")
`summarise()` ungrouping output (override with `.groups` argument)

Let’s select the genes with a maximum fold change of 4 or above (log2 fold change of 2 or above)

# subset the data
morethan4fold <- apply(m.dat2, 1, function(x) any(abs(x) >= 2))
m.dat3 <- m.dat2[morethan4fold,]

Now we can plot the log2 fold changes relative to time 0 for these genes:

# we will use the pheatmap function from the pheatmap package, which is 
# similar but with better defaults than the base R's heatmap()
suppressPackageStartupMessages(library(pheatmap))
# nmf.options(grid.patch=TRUE)
colour <- colorRampPalette( c("blue", "black", "yellow"), space="rgb")(64) # for plotting
pheatmap(m.dat3, color = colour, breaks = seq(-8,8,length.out = 65), cluster_rows = F, cluster_cols = F, scale = "none", labels_row = "")

Now let’s try to cluster the genes using Pearson’s Correlation Coefficient. First, we will compute the correlation matrix and visualize it using the image() function, with reordering based on hierarchical clustering.

library(corrplot) # plot correlation matrix in heatmap format
dat3.cor <- cor(t(m.dat3), method = "pearson")
dat3.hc <- hclust(as.dist(1-dat3.cor), method = "complete")
od <- dat3.hc$order
colour <- colorRampPalette( c("blue", "black", "yellow"), space="rgb")(64)
corrplot(dat3.cor, col = colour, method = "color", order = "hclust", hclust.method = "ward.D", addrect = 4, tl.pos = "n", title = "Pairwise Pearson's Correlation Coefficient for 1519 genes with >4 fold change")

Next we apply the clustering order to the rows in the heatmap for gene expression.

pheatmap(m.dat3, color = colour, breaks = seq(-8,8,length.out = 65), cluster_rows = dat3.hc, cluster_cols = F, scale = "none", labels_row = "")

Another question is how similar are the time points with each other. We use similar approaches above, but this time applied to the time points as columns.

dat1.cor <- cor(m.dat1, method = "pearson")
dat1.hc <- hclust(as.dist(1-dat1.cor), method = "complete")
od1 <- dat1.hc$order
colour <- colorRampPalette( c("blue", "black", "yellow"), space="rgb")(64)
pheatmap(dat1.cor, col = colour, cluster_rows = F, cluster_cols = F, scale = "none")

The result is self-explanatory.

LS0tCnRpdGxlOiBBbmFseXplIEMuIGdsYWJyYXRhIHRpbWUgY291cnNlIGV4cHJlc3Npb24KYXV0aG9yOiBCaW4gSGUKZGF0ZTogMjAyMC0wOC0wMQpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHllcwotLS0KCmBgYHtyIHNldHVwfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKYGBgCgojIyBMb2FkIGRhdGEKYGBge3J9CnRhYiA8LSByZWFkX2NzdigiLi4vZGF0YS9FeDAwOV9leHBlcmltZW50X3NldF91cF8yMDE3MTAxOS5jc3YiKQpkYXQgPC0gcmVhZF90c3YoIi4uL2RhdGEvRXgwMDlfbm9ybWFsaXplZF9sb2cyX3JlYWRfY291bnRzLnppcCIpCmBgYAojIyBQcmVwYXJlIGRhdGEKCkluIHRoaXMgYW5hbHlzaXMgd2Ugd2lsbCBmb2N1cyBvbiB0aGUgInd0IiBzYW1wbGVzLCBgciB0YWIgJT4lIGZpbHRlcihHZW5vdHlwZSA9PSAid3QiLCBUaW1lcG9pbnQgIT0gImRlbDgwIilgCgpgYGB7cn0KIyBjaG9vc2UgdGhlIHNhbXBsZXMgdG8gdXNlIGFuZCBjb252ZXJ0IHRoZSB0aW1lIHBvaW50cyB0byBudW1lcmljIHZhcmlhYmxlCnRpbWUybnVtIDwtIGMoInByZSIgPSAwLCAiMjBtIiA9IDIwLCAiMzBtIiA9IDMwLCAiNDVtIiA9IDQ1LCAiNjBtIiA9IDYwLAogICAgICAgICAgICAgICAiOTBtIiA9IDkwLCAiMTIwbSIgPSAxMjAsICIxNTBtIiA9IDE1MCwgIjE4MG0iID0gMTgwLCAKICAgICAgICAgICAgICAgIjI0MG0iID0gMjQwKQpzYW1wbGVzLnVzZSA8LSB0YWIgJT4lIAogIGZpbHRlcihHZW5vdHlwZSA9PSAid3QiLCBUaW1lcG9pbnQgIT0gImRlbDgwIikgJT4lIAogIG11dGF0ZShUaW1lID0gdGltZTJudW1bVGltZXBvaW50XSkgJT4lIAogIHNlbGVjdChTYW1wbGUsIFRpbWUpCgojIGV4dHJhY3QgdGhlIGxpc3Qgb2Ygc2FtcGxlIG5hbWVzCnd0Lmxpc3QgPC0gc2FtcGxlcy51c2UkU2FtcGxlCgojIHN1YnNldCB0aGUgZGF0YQpkYXQxIDwtIGRhdCAlPiUgc2VsZWN0KGdlbmUsIGFsbF9vZih3dC5saXN0KSkKCiMgdGhlcmUgYXJlIHRlY2huaWNhbCBkdXBsaWNhdGVzIGZvciBlYWNoIHRpbWUgcG9pbnQuIGZvciBvdXIgcHVycG9zZQojIHdlIGp1c3QgbmVlZCBvbmUgdmFsdWUgcGVyIHRpbWUgcG9pbnQuIEl0IGlzIHNlbnNpYmxlIHRvIGNvbXB1dGUgdGhlIAojIG1lYW4gdmFsdWUgZm9yIGVhY2ggZ2VuZSBhdCBlYWNoIHRpbWUgcG9pbnQuIHRvIGRvIHRoaXMgd2UgZmlyc3QgY29udmVydAojIHRoZSBkYXRhIHRhYmxlIGludG8gYSBsb25nIGZvcm1hdCwgd2hpY2ggYWxsb3dzIGZvciBhZ2dyZWdhdGlvbiBmdW5jdGlvbnMKZGF0MS5sb25nIDwtIGRhdDEgJT4lIAogIHBpdm90X2xvbmdlcihzdGFydHNfd2l0aCgiUyIpLCBuYW1lc190byA9ICJzYW1wbGUiKSAlPiUgCiAgbGVmdF9qb2luKHNhbXBsZXMudXNlLCBieSA9IGMoInNhbXBsZSIgPSAiU2FtcGxlIikpICU+JSAKICBzZWxlY3QoZ2VuZSwgdGltZSA9IFRpbWUsIGV4biA9IHZhbHVlKQoKIyBjYWxjdWxhdGUgbWVhbiB2YWx1ZSBmb3IgZWFjaCB0aW1lcG9pbnQgd2l0aGluIGVhY2ggZ2VuZQpkYXQxLmFnZ3IgPC0gZGF0MS5sb25nICU+JSAKICBncm91cF9ieShnZW5lLCB0aW1lKSAlPiUgCiAgc3VtbWFyaXplKGF2Zy5leG4gPSBtZWFuKGV4biksIHNkLmV4biA9IHNkKGV4biksIC5ncm91cHMgPSAiZHJvcF9sYXN0IikgJT4lICAKICAjIHN1YnRyYWN0IHRoZSB2YWx1ZSBvZiB0aGUgZmlyc3QgdGltZXBvaW50IGZyb20gdGhlIAogICMgcmVzdCB0byBmb3JtIHJlbGF0aXZlIGV4cHJlc3Npb24gbGV2ZWwgKGJhc2VsaW5lKQogIG11dGF0ZShyZWwuZXhuID0gYXZnLmV4biAtIGZpcnN0KGF2Zy5leG4pKQoKIyBjb252ZXJ0IHRoZSBsb25nIGZvcm1hdCBiYWNrIHRvIHRoZSB3aWRlIGZvcm1hdCBmb3IgZXh0cmFjdGluZyBtYXRyaXgKZGF0MS53aWRlIDwtIGRhdDEuYWdnciAlPiUgCiAgcGl2b3Rfd2lkZXIoaWRfY29scyA9IGdlbmUsIG5hbWVzX2Zyb20gPSB0aW1lLCB2YWx1ZXNfZnJvbSA9IGF2Zy5leG4pCgpkYXQyLndpZGUgPC0gZGF0MS5hZ2dyICU+JSAKICBwaXZvdF93aWRlcihpZF9jb2xzID0gZ2VuZSwgbmFtZXNfZnJvbSA9IHRpbWUsIHZhbHVlc19mcm9tID0gcmVsLmV4bikKCiMgY29udmVydCB0aGUgcmVzdWx0IGludG8gYSBtYXRyaXggZm9yIGRvd25zdHJlYW0gYW5hbHlzaXMKbS5kYXQxIDwtIGFzLm1hdHJpeChkYXQxLndpZGVbLC0xXSkKcm93bmFtZXMobS5kYXQxKSA8LSBkYXQxLndpZGUkZ2VuZQoKbS5kYXQyIDwtIGFzLm1hdHJpeChkYXQyLndpZGVbLC0xXSkKcm93bmFtZXMobS5kYXQyKSA8LSBkYXQyLndpZGUkZ2VuZQpgYGAKCiMjIENhbGN1bGF0ZSBkaXN0YW5jZSAoZGlzc2ltaWxhcml0eSkgYmV0d2VlbiBnZW5lcwoKT3VyIGdvYWwgaXMgdG8gZ3JvdXAgZ2VuZXMgYmFzZWQgb24gdGhlaXIgdGVtcG9yYWwgcHJvZmlsZSwgdGhhdCBpcywgZ2VuZXMgdGhhdCBzaGFyZSB0aGUgc2FtZSB0ZW1wb3JhbCBwYXR0ZXJuLCBzdWNoIGFzIGluY3JlYXNlIGluIGV4cHJlc3Npb24gb3ZlciB0aW1lLCBzaG91bGQgYmUgZ3JvdXBlZCB0b2dldGhlci4KCkZvciBleGFtcGxlLCBoZXJlIGFyZSBzb21lIGdlbmVzIGtub3duIHRvIGJlIGluZHVjZWQgYWZ0ZXIgc3RhcnZhdGlvbjoKYGBge3J9CiMgcGxvdCBleGFtcGxlcwpleHAubGlzdCA8LSBwYXN0ZTAoIkNBR0wwIixjKCJCMDI0NzVnIiwgIkYwMjE0NWciLCAiSzEwODY4ZyIsICJKMDQyMDJnIikpCmV4cC5sYWJlbCA8LSBwYXN0ZShleHAubGlzdCwgYygiUEhPODQiLCJQSE0yIiwiQ1RBMSIsIkhTUDEyIiksIHNlcCA9ICIgIikKbmFtZXMoZXhwLmxhYmVsKSA8LSBleHAubGlzdApkYXQxLmFnZ3IgJT4lIAogIGZpbHRlcihnZW5lICVpbiUgZXhwLmxpc3QpICU+JSAKICBnZ3Bsb3QoYWVzKHggPSB0aW1lLCB5ID0gcmVsLmV4bikpICsgZ2VvbV9saW5lKCkgKyBnZW9tX3BvaW50KHNoYXBlID0gMCkgKwogIGdlb21fZXJyb3JiYXIoYWVzKHltaW4gPSByZWwuZXhuIC0gMS45NipzZC5leG4sIAogICAgICAgICAgICAgICAgICAgIHltYXggPSByZWwuZXhuICsgMS45NipzZC5leG4pKSArCiAgZmFjZXRfd3JhcCh+Z2VuZSwgbGFiZWxsZXIgPSBsYWJlbGxlcihnZW5lID0gZXhwLmxhYmVsKSkgKyAKICB4bGFiKCJ0aW1lIChtaW4pIikgKyB5bGFiKCJsb2cyIG5vcm1hbGl6ZWQgbVJOQSBjb3VudHMgLSB0aW1lXzAiKSArCiAgbGFicyhjYXB0aW9uID0gInBvaW50cyBhcmUgYXZlcmFnZSBvZiBhdCBsZWFzdCB0d28gYmlvbG9naWNhbCByZXBsaWNhdGVzXG5lcnJvciBiYXJzIGFyZSA5NSUgY29uZmlkZW5jZSBpbnRlcnZhbHMiKSArCiAgdGhlbWUocGxvdC5jYXB0aW9uID0gZWxlbWVudF90ZXh0KGhqdXN0ID0gMCkpCmBgYApBbmQgaGVyZSBhcmUgZ2VuZXMgdGhhdCBhcmUgbm90IGV4cGVjdGVkIHRvIHJlc3BvbmQgdG8gcGhvc3BoYXRlIHN0YXJ2YXRpb246CmBgYHtyfQojIHBsb3QgZXhhbXBsZXMKZXhwLmxpc3QgPC0gcGFzdGUwKCJDQUdMMCIsYygiSzEyNjk0ZyIsICJLMDUwMDVnIiwgIkQwNjEzOGciLCAiRDA1MTcwZyIpKQpleHAubGFiZWwgPC0gcGFzdGUoZXhwLmxpc3QsIGMoIkFDVDEiLCJBTEc5IiwiSEVNMiIsIlBITzQiKSwgc2VwID0gIiAiKQpuYW1lcyhleHAubGFiZWwpIDwtIGV4cC5saXN0CmRhdDEuYWdnciAlPiUgCiAgZmlsdGVyKGdlbmUgJWluJSBleHAubGlzdCkgJT4lIAogIGdncGxvdChhZXMoeCA9IHRpbWUsIHkgPSByZWwuZXhuKSkgKyBnZW9tX2xpbmUoKSArIGdlb21fcG9pbnQoc2hhcGUgPSAwKSArCiAgZ2VvbV9lcnJvcmJhcihhZXMoeW1pbiA9IHJlbC5leG4gLSAxLjk2KnNkLmV4biwgCiAgICAgICAgICAgICAgICAgICAgeW1heCA9IHJlbC5leG4gKyAxLjk2KnNkLmV4bikpICsKICBmYWNldF93cmFwKH5nZW5lLCBsYWJlbGxlciA9IGxhYmVsbGVyKGdlbmUgPSBleHAubGFiZWwpKSArIHlsaW0oLTUsNSkgKwogIHhsYWIoInRpbWUgKG1pbikiKSArIHlsYWIoImxvZzIgbm9ybWFsaXplZCBtUk5BIGNvdW50cyAtIHRpbWVfMCIpICsKICBsYWJzKGNhcHRpb24gPSAicG9pbnRzIGFyZSBhdmVyYWdlIG9mIGF0IGxlYXN0IHR3byBiaW9sb2dpY2FsIHJlcGxpY2F0ZXNcbmVycm9yIGJhcnMgYXJlIDk1JSBjb25maWRlbmNlIGludGVydmFscyIpICsKICB0aGVtZShwbG90LmNhcHRpb24gPSBlbGVtZW50X3RleHQoaGp1c3QgPSAwKSkKYGBgCgojIyMgQSB0b3kgZXhhbXBsZQpJbiBvcmRlciB0byBjbHVzdGVyIGdlbmVzIGJhc2VkIG9uIHRoaXMgY3JpdGVyaWEsIHdlIG5lZWQgdG8gZmlyc3QgcXVhbnRpZnkgdGhlIGRpc3NpbWlsYXJpdHkgYmV0d2VlbiBnZW5lcy4gSGVyZSB3ZSBhcmUgbGVzcyBpbnRlcmVzdGVkIGluIHRoZSAibWFnbml0dWRlIiBvZiBnZW5lIGV4cHJlc3Npb24gdGhhbiB0aGUgInByb2ZpbGUiIG9yIHRlbXBvcmFsIGR5bmFtaWNzIG9mIGdlbmUgZXhwcmVzc2lvbi4gSW4gdGhlIGFib3ZlIGV4YW1wbGUsIG5vdGljZSB0aGF0IHRoZSBhYnNvbHV0ZSBtYXhpbXVtIGV4cHJlc3Npb24gbGV2ZWxzIG9mIHRoZSBmb3VyIGdlbmVzIGRpZmZlciBhIGxvdC4gSG93ZXZlciwgdGhleSBhbGwgc2hvdyB0aGUgc2FtZSAicGF0dGVybiIsIGkuZS4gYW4gZWFybHkgcmlzZSBmb2xsb3dlZCBieSBzdXN0YWluZWQgZXhwcmVzc2lvbi4gTGV0J3MgbG9vayBhdCBhIHNpbXBsZSBleGFtcGxlIGNvbnNpc3Rpbmcgb2YgZm91ciBnZW5lcyBhbmQgZm91ciB0aW1lIHBvaW50czoKCmBgYHtyfQp0b3kgPC0gbWF0cml4KGMoMiw0LDQsNCw2LDYsMywyLDIwLDQwLDQwLDQwLDQ1LDQ1LDM1LDIwKSwgCiAgICAgICAgICAgICAgYnlyb3cgPSBULCBucm93ID0gNCwgCiAgICAgICAgICAgICAgZGltbmFtZXMgPSBsaXN0KGdlbmUgPSBwYXN0ZSgiZ2VuZSIsIDE6NCksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0aW1lID0gYygxMCwyMCwzMCw0MCkpKQp0b3kKcGxvdCh4ID0gMSwgdHlwZSA9ICJuIiwgeGxpbSA9IGMoMTAsNTApLCB5bGltID0gYygwLCA1MCkpCnQgPSBjKDEwLDIwLDMwLDQwKQpmb3IoaSBpbiAxOjQpewogIHBvaW50cyh0LCB0b3lbaSxdLCBwY2ggPSBpKQogIGxpbmVzKHQsIHRveVtpLF0pCn0KbGVnZW5kKCJ0b3ByaWdodCIsIGxlZ2VuZCA9IHJvd25hbWVzKHRveSksIHBjaCA9IDE6NCkKYGBgCiMjIyBTY2FsaW5nIHRvIHRoZSByZXNjdWUKQWx0aG91Z2ggdGhlIHNjYWxlcyBtYWtlIGl0IGEgYml0IGRpZmZpY3VsdCB0byBzZWUsIGJ1dCBvbmUgY2FuIHRlbGwgdGhhdCBnZW5lcyAxIGFuZCAzICJyaXNlIiBvdmVyIHRpbWUgd2hpbGUgZ2VuZXMgMiBhbmQgNCAiZmFsbCIgb3ZlciB0aW1lLiBUaGUgcXVlc3Rpb24gaXMsIGhvdyBjYW4gd2UgdHVybiB0aGF0IGludHVpdGlvbiBpbnRvIGEgbnVtYmVyIHRoYXQgY2FuIGJlIGNhbGN1bGF0ZWQgZnJvbSB0aGUgZGF0YT8gT25lIGlkZWEgaXMgdG8gInNjYWxlIiB0aGUgZGF0YSBieSBzdWJ0cmFjdGluZyB0aGUgbWVhbiBleHByZXNzaW9uIGxldmVsIGFjcm9zcyB0aW1lIG9mIGVhY2ggZ2VuZSBmcm9tIGVhY2ggdGltZSBwb2ludCwgYW5kIGRpdmlkZSB0aGUgcmVzdWx0IGJ5IHRoZSBzdGFuZGFyZCBkZXZpYXRpb24gb2YgdGhlIGZvdXIgdGltZSBwb2ludHMuIFRoaXMgd2lsbCAiY2VudGVyIiBhbmQgc3RhbmRhcmRpemUgdGhlIGdlbmVzLgpgYGB7cn0KdG95LnNjYWxlZCA8LSBzY2FsZSh0KHRveSkpICMgbm90ZSB0aGF0IG1vc3QgciBmdW5jdGlvbnMgb3BlcmF0ZSBvbiBjb2x1bW5zCiMgc2luY2Ugd2Ugd2FudCB0byBvcGVyYXRlIG9uIHRoZSB0aW1lIHNlcmllcywgd2UgdHJhbnNwb3NlIHRoZSBtYXRyaXggc28KIyB0aGF0IGVhY2ggZ2VuZSBpcyBpbiBhIGNvbHVtbgptYXRwbG90KHQsIHRveS5zY2FsZWQsIHR5cGUgPSAiYiIsIHBjaCA9IDE6NCwgbHR5ID0gMSwgY29sID0gMSkKbGVnZW5kKCJ0b3ByaWdodCIsIGNvbG5hbWVzKHRveS5zY2FsZWQpLCBwY2ggPSAxOjQpCmBgYAojIyMgYGRpc3QoKWAgZnVuY3Rpb24KTm93IHRoZSAoZGlzKXNpbWlsYXJpdHkgcGF0dGVybnMgYXJlIG1vcmUgY2xlYXIuIEJ1dCB3ZSBzdGlsbCBkb24ndCBoYXZlIGEgbnVtYmVyLiBXZSBjYW4gbm93IGNhbGN1bGF0ZSB0aGUgIkV1Y2xpZGlhbiBkaXN0YW5jZSIgYmV0d2VlbiBlYWNoIHBhaXIgb2YgZ2VuZXMuIEluIGEgMkQgb3IgM0Qgc3BhY2UsIHRoaXMgbWVhc3VyZSB3b3VsZCBiZSB0aGUgZmFtaWxpYXIgImRpc3RhbmNlIi4gSW4gaGlnaGVyIGRpbWVuc2lvbnMgc3VjaCBhcyBoZXJlIChlYWNoIGdlbmUgaXMgYSBkYXRhIHBvaW50IGluIGEgNC1EIHNwYWNlIHNwYW5uZWQgYnkgdGhlaXIgZXhwcmVzc2lvbiBsZXZlbHMgYXQgZWFjaCBvZiB0aGUgZm91ciB0aW1lIHBvaW50cyksIHRoZSBpZGVhIHdvdWxkIGJlIHRoZSBzYW1lLCB3aGVyZSAkRCA6PSBcc3FydHtcc3VtX3tpPTF9Xns0fSh4X2kteV9pKV4yfSQuIFVzaW5nIHRoZSBgZGlzdCgpYCBmdW5jdGlvbiwgd2UgZm91bmQgdGhlIHJlc3VsdCB0byBiZSAKYGBge3J9CmRpc3QodCh0b3kuc2NhbGVkKSkgIyBkaXN0KCkgY29tcHV0ZXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gcm93cwpgYGAKQ29tcGFyZSB0aGlzIHRvIHRoZSByZXN1bHQgaGFkIHdlIGFwcGxpZWQgdGhlIGZ1bmN0aW9uIG9uIHRoZSB1bnNjYWxlZCByYXcgZGF0YQpgYGB7cn0KZGlzdCh0b3kpCmBgYAoKIyMjIFBlYXJzb24ncyBDb3JyZWxhdGlvbiBDb2VmZmljaWVudCBhcyBhbm90aGVyIHdheSB0byBtZWFzdXJlIHNpbWlsYXJpdHkKVGhlcmUgaXMgYW5vdGhlciB3YXkgdG8gcXVhbnRpZnkgdGhlIGRpc3NpbWlsYXJpdHkgYmV0d2VlbiB0aGUgZXhwcmVzc2lvbiBwYXR0ZXJucyBvZiB0aGUgZ2VuZXM6IGNhbGN1bGF0ZSB0aGUgUGVhcnNvbidzIGNvcnJlbGF0aW9uIGNvZWZmaWNpZW50IGJldHdlZW4gdGhlIHRpbWUgc2VyaWVzIGFuZCBzdWJ0cmFjdCBpdCBmcm9tIDEuIFRoZSBQZWFyc29uJ3MgY29ycmVsYXRpb24gY29lZmZpY2llbnQgZGVzY3JpYmVzIHRoZSBjb2xpbmVhcml0eSBiZXR3ZWVuIHR3byB2YXJpYWJsZXMuIE9mdGVuIHdyaXR0ZW4gYXMgInIiLCBpdCBpcyBjbG9zZWx5IHJlbGF0ZWQgdG8gbGluZWFyIHJlZ3Jlc3Npb24uIEluIGZhY3QsIHlvdSBtYXkgd2VsbCBoYXZlIHNlZW4gInIiIG9yICIkUl4yJCIgd3JpdHRlbiBvbiBwbG90cyB3aXRoIGxpbmVhciByZWdyZXNzaW9uIGxpbmVzLiBJbnR1aXRpdmVseSwgdHdvIHRpbWUgc2VyaWVzIGFyZSBwZXJmZWN0bHkgcG9zaXRpdmVseSBjb3JyZWxhdGVkIGlmIHRoZXkgcmlzZSBvciBmYWxsIHRvZ2V0aGVyLCBhbmQgcGVyZmVjdGx5IGFudGktY29ycmVsYXRlZCBpZiB0aGV5IGhhdmUgdGhlIG9wcG9zaXRlIHBhdHRlcm4uIEluIHRoZSBleGFtcGxlIGFib3ZlLCBnZW5lIDEgYW5kIDMgd291bGQgaGF2ZSBhIFBlYXJzb24ncyBjb3JyZWxhdGlvbiBjb2VmZmljaWVudCBvZiArMS4gTm93IGxldCdzIGNvbXB1dGUgdGhlIHJlc3VsdHMgZm9yIGFsbCBwYWlyczoKCj4gX05vdGVfCj4KPiAgICBgY29yKClgIGNvbXB1dGVzIHRoZSBwYWlyd2lzZSBjb3JyZWxhdGlvbiBiZXR3ZWVuICpDT0xVTU5TKiBvZiBhIG1hdHJpeCBhbmQgdGhlcmVmb3JlIHdlIG5lZWQgdG8gdHJhbnNwb3NlIHRoZSBvcmlnaW5hbCBtYXRyaXgKCmBgYHtyfQpjb3IodCh0b3kpKQpgYGAKQ29tcGFyZSB0aGlzIHRvIHRoZSByZXN1bHQgdXNpbmcgdGhlIHVudHJhbnNwb3NlZCBtYXRyaXgsIHdoaWNoIHNob3dzIHRoZSBjb3JyZWxhdGlvbnMgYmV0d2VlbiB0aW1lIHBvaW50cyAodGhpcyBtYXkgYmUgb2YgaW50ZXJlc3QgYXMgd2VsbCkuICAKYGBge3J9CmNvcih0b3kpCmBgYAoKTm90ZSB0aGF0IHdlIGRvbid0IGhhdmUgdG8gc2NhbGUgdGhlIG9yaWdpbmFsIGRhdGEgYmVjYXVzZSB0aGUgY2FsY3VsYXRpb24gb2YgY29ycmVsYXRpb24gaW5jbHVkZXMgdGhlIHNjYWxpbmcgKHNlZSBbd2lraV0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvQ29ycmVsYXRpb25fYW5kX2RlcGVuZGVuY2UpKQoKIyMgQ2x1c3RlcmluZyBnZW5lcwpBcm1lZCB3aXRoIHR3byBkaWZmZXJlbnQgd2F5cyB0byBtZWFzdXJlIHRoZSBkaXN0YW5jZSBvciBzaW1pbGFyaXR5IGJldHdlZW4gZ2VuZXMsIHdlIGNhbiBub3cgbW92ZSBvbiB0byBjbHVzdGVyIHRoZSBnZW5lcyBhbmQgdmlzdWFsaXplIHRoZW0gd2l0aCB0aGUgYGFoZWF0bWFwKClgIGZ1bmN0aW9uIGZyb20gdGhlIGBOTUZgIHBhY2thZ2UuCgojIyMgVXNlIEV1Y2xpZGVhbiBkaXN0YW5jZQpgYGB7cn0KIyB3ZSBmaXJzdCB1c2UgdGhlIEV1Y2xpZGVhbiBkaXN0YW5jZSBvbiB0aGUgc2NhbGVkIG1hdHJpeAojIG5vdGUgdGhhdCBkaXN0KCkgb3BlcmF0ZXMgb24gdGhlIHJvd3MKdCh0b3kuc2NhbGVkKQp0b3kuZGlzdDEgPC0gZGlzdCh0KHRveS5zY2FsZWQpLCBtZXRob2QgPSAiZXVjbGlkZWFuIikKdG95LmRpc3QxCnRveS5jbHVzdDEgPC0gaGNsdXN0KHRveS5kaXN0MSkKcGxvdCh0b3kuY2x1c3QxKQpgYGAKCiMjIyBVc2UgY29ycmVsYXRpb24gbWF0cml4CmBgYHtyfQojIHJlbWVtYmVyIHRoYXQgY29yKCkgb3BlcmF0ZXMgb24gdGhlIGNvbHVtbnMKdCh0b3kpCnRveS5kaXN0MiA8LSAxLWNvcih0KHRveSkpCnRveS5kaXN0Mgp0b3kuY2x1c3QyIDwtIGhjbHVzdChhcy5kaXN0KHRveS5kaXN0MikpCnBsb3QodG95LmNsdXN0MikKYGBgCk5vdGljZSB0aGF0IHRoZSB0b3BvbG9naWVzIGFyZSB0aGUgc2FtZSBidXQgdGhlIHRyZWUgaGVpZ2h0IHVuaXRzIGFyZSBkaWZmZXJlbnQgYmV0d2VlbiB0aGUgdHdvLiBCdXQgdGhhdCBkb2Vzbid0IGNvbmNlcm4gdXMuCgpCZWZvcmUgd2UgYXBwbHkgd2hhdCB3ZSBsZWFybmVkIHRvIG91ciBhY3R1YWwgZ2VuZSBleHByZXNzaW9uIGRhdGFzZXQsIGxldCdzIGxvb2sgYXQgb25lIG1vcmUgdGhpbmcsIHRoYXQgaXMsIGhvdyBgaGVhdG1hcCgpYCBmdW5jdGlvbiB3b3Jrcy4KCiMjIERpc3NlY3RpbmcgdGhlIGBoZWF0bWFwKClgIGZ1bmN0aW9uCgojIyMgQnJpZWYgZXhwbGFuYXRpb24KYGhlYXRtYXAoKWAgYWN0dWFsbHkgaW52b2x2ZXMgYSBzZXJpZXMgb2Ygc3RlcHMuIEZpcnN0IHRoZSBmdW5jdGlvbiBhcHBsaWVzLCBieSBkZWZhdWx0LCB0aGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgYWxnb3JpdGhtIG9uIGJvdGggdGhlIHJvd3MgYW5kIHRoZSBjb2x1bW5zIGJhc2VkIG9uIHRoZSBpbnB1dCBkYXRhIChub24tc2NhbGVkKS4gSXQgdGhlbiByZW9yZGVycyB0aGUgcm93cyBhbmQgdGhlIGNvbHVtbnMgdG8gbWF0Y2ggdGhlIG9yZGVyIGFmdGVyIHRoZSBjbHVzdGVyaW5nLiBOb3RlLCBob3dldmVyLCB0aGUgY2x1c3RlcmluZyBpcyBkb25lIG9uIHRoZSB1bnNjYWxlZCBkYXRhLiBUaGlzIGlzIGVzcGVjaWFsbHkgY29uZnVzaW5nIGJlY2F1c2UgdGhlIGJhc2UgUidzIGBoZWF0bWFwKClgIGZ1bmN0aW9uIGhhcyBhbiBhcmd1bWVudCBjYWxsZWQgYHNjYWxlZGAuIFRoaXMsIGhvd2V2ZXIsIG9ubHkgYWZmZWN0cyBob3cgdGhlIGRhdGEgYXJlIHBsb3R0ZWQsIG5vdCBob3cgdGhleSBhcmUgY2x1c3RlcmVkLiBOb3RlIHRoYXQgdGhpcyBjbHVzdGVyaW5nIHN0ZXAgY2FuIGJlIHNraXBwZWQgYnkgc2V0dGluZyBgUm93diA9IE5BYCBhbmQgYENvbHYgPSBOQWAsIGVhY2ggb2Ygd2hpY2ggY29udHJvbHMgd2hldGhlciBjbHVzdGVyaW5nIGFuZCByZW9yZGVyaW5nIGlzIGRvbmUgZm9yIHRoZSByb3dzIGFuZCB0aGUgY29sdW1ucyByZXNwZWN0aXZlbHkuCgpPbmNlIHRoZSByb3dzIGFuZCBjb2x1bW5zIGFyZSByZW9yZGVyZWQsIHVubGVzcyBkaXNhYmxlZCBieSB0aGUgYXJndW1lbnRzIHNob3duIGFib3ZlLCB0aGUgZnVuY3Rpb24gdGhlbiBjaGVja3MgdGhlIHZhbHVlIG9mIGBzY2FsZWAuIFRoZSBkZWZhdWx0IGZvciB0aGlzIGFyZ3VtZW50IGRlcGVuZHMgb24gdGhlIHZhbHVlIG9mIGFub3RoZXIgYXJndW1lbnQsIGBzeW1tYCwgd2hvc2UgZGVmYXVsdCBpcyBgZmFsc2VgLiBJZiAic3ltbSIgaXMgZmFsc2UsIGBzY2FsZWAgZGVmYXVsdHMgdG8gInJvdyIsIGkuZS4gc2NhbGluZyBieSByb3cuIE90aGVyd2lzZSwgc2NhbGluZyBpcyBvZmYuCgpBZnRlciByZW9yZGVyaW5nIGFuZCBzY2FsaW5nLCBpZiBhcHBsaWNhYmxlLCBgaGVhdG1hcCgpYCB0aGVuIF90cmFuc3Bvc2VzXyB0aGUgcmVzdWx0aW5nIG1hdHJpeCBhbmQgcGxvdHMgaXQgdXNpbmcgdGhlIGJhc2UgZnVuY3Rpb24gYGltYWdlKClgLiBXZSB3aWxsIHNlZSB0aGUgcmVhc29uIGZvciB0cmFuc3Bvc2luIHRoZSBtYXRyaXggbGF0ZXIuIExldCdzIGZpcnN0IHVuZGVyc3RhbmQgaG93IGBpbWFnZSgpYCB3b3Jrcy4gVGhpcyBmdW5jdGlvbiBzaW1wbHkgZHJhd3MgcmVjdGFuZ2xlcyBhbmQgY29sb3JzIHRoZW0gYnkgdGhlIHZhbHVlIGdpdmVuLiBOb3RlIHRoZXJlIGlzIHNvbWV0aGluZyBub25pbnR1aXRpdmUgYWJvdXQgdGhlIG1hcHBpbmcgZnJvbSB0aGUgbWF0cml4IHRvIHRoZSBpbWFnZSAtLSB0aGUgYGltYWdlKClgIGZ1bmN0aW9uIGRyYXdzIGEgY2FydGVzaWFuIGNvb3JkaW5hdGUgd2l0aCAoMCwwKSBhdCB0aGUgbG93ZXIgbGVmdCBjb3JuZXIuIEl0IHRoZW4gY29sb3JzIHRoZSBzcXVhcmUgY29ycmVzcG9uZGluZyB0byAoaSxqKSB0byB0aGUgdmFsdWUgb2YgWFtpLGpdIGluIHRoZSBtYXRyaXguIElmIHlvdSBmb2xsb3dzIG1lIHNvIGZhciwgeW91IHJlYWxpemUgdGhhdCB0aGUgd2hpbGUgaW4gdGhlIG1hdHJpeCB0aGUgZmlyc3QgaW5kZXggaXMgdGhlIHJvdyBhbmQgdGhlIHNlY29uZCB0aGUgY29sdW1uLCBpbiB0aGUgaW1hZ2UsIHRoZSByb3dzIG5vdyBiZWNvbWUgdGhlIHgtYXhpcyBhbmQgdGhlIGNvbHVtbnMgdGhlIHktYXhpcy4gRXNzZW50aWFsbHksIHRoZSBtYXRyaXggaGFzIGJlZW4gcm90YXRlZCA5MCBkZWdyZWVzIGNvdW50ZXJjbG9ja3dpc2UuCgojIyMgVXNpbmcgdGhlIGBpbWFnZSgpYCBmdW5jdGlvbgpOb3cgbGV0J3MgbG9vayBhdCB0aGUgdG95IGV4YW1wbGUgdG8gdW5kZXJzdGFuZCB0aGVzZSBpbnR1aXRpdmVseS4KRmlyc3QsIGlmIHdlIGRpcmVjdGx5IGFwcGx5IGltYWdlKCkgdG8gdGhlIHRveSBkYXRhLCB0aGlzIGlzIHdoYXQgd2UgZ2V0CmBgYHtyfQppbWFnZSh4ID0gMTo0LCB5ID0gYygxMCwyMCwzMCw0MCksIHogPSB0b3ksIHhsYWIgPSAiZ2VuZSIsIHlsYWIgPSAidGltZSAobWluKSIsIHhheHQgPSAibiIsIHlheHQgPSAibiIpCmF4aXMoc2lkZSA9IDEsIGF0ID0gMTo0LCBsYWJlbHMgPSByb3duYW1lcyh0b3kpKQpheGlzKHNpZGUgPSAyLCBhdCA9IGMoMTAsMjAsMzAsNDApLCBsYWJlbHMgPSBjb2xuYW1lcyh0b3kpKQpgYGAKTmV4dCB3ZSB1c2UgdGhlIGBoZWF0bWFwKClgIGZ1bmN0aW9uIHdpdGhvdXQgY2x1c3RlcmluZyBvciBzY2FsaW5nCmBgYHtyfQpoZWF0bWFwKHRveSwgUm93diA9IE5BLCBDb2x2ID0gTkEsIHNjYWxlID0gIm5vbmUiKQpgYGAKT25jZSB3ZSBpbWFnaW5lIHRoYXQgdGhlIHJvdyBsYWJlbHMgYmUgbW92ZWQgdG8gdGhlIGxlZnQgc2lkZSwgd2UgcmVhbGl6ZSB0aGF0IHRoZSBgaGVhdG1hcCgpYCBmdW5jdGlvbiBlZmZlY3RpdmVseSBzd2FwcGVkIHRoZSByb3dzIGFuZCB0aGUgY29sdW1ucywgaS5lLiBfdHJhbnNwb3NlZF8gdGhlIG1hdHJpeC4gUHJlc3VtYWJseSwgdGhpcyBtYWtlcyB0aGUgcm93cyBhbmQgY29sdW1ucyBhcHBlYXIgX25lYXJseV8gdGhlIHNhbWUgYXMgdGhlIGlucHV0IG1hdHJpeC4gSSBzYXkgIm5lYXJseSIgYmVjYXVzZSAtLSBub3RpY2UgdGhhdCAtLSB0aGUgcm93IG9yZGVycyB3ZXJlIHJldmVyc2VkLCBhZ2FpbiBiZWNhdXNlIGluIGEgcGxvdCwgKDAsMCkgaXMgaW4gdGhlIGxvd2VyIGxlZnQgY29ybmVyLgoKIyMjIEFkZGluZyB0aGUgY2x1c3RlcmluZyBiYXNlZCByZW9yZGVyaW5nCk5vdyBsZXQncyBhZGQgdGhlIGNsdXN0ZXJpbmcgLS0gbm90ZSB0aGF0IHdlIG9ubHkgd2FudCB0byBjbHVzdGVyIHRoZSBnZW5lcywgYW5kIHdvdWxkIGxpa2UgdG8ga2VlcCB0aGUgdGltZSBwb2ludHMgaW4gdGhlaXIgb3JpZ2luYWwgb3JkZXIsIGZvciBvYnZpb3VzIHJlYXNvbnMuIFRvIGFjaGlldmUgdGhpcywgd2UgcmVhbGl6ZSB0aGF0IHRpbWUgc2VyaWVzIGFyZSBpbiB0aGUgY29sdW1ucy4gU28gd2UganVzdCBuZWVkIHRvIHNldCBgQ29sdiA9IE5BYCwgd2hpbGUgbGVhdmluZyBgUm93diA9IE5VTExgLCB3aGljaCBtZWFucyBpdCB1c2VzIHRoZSBkZWZhdWx0IGNsdXN0ZXJpbmcgb3JkZXIuCmBgYHtyfQojIHdpdGggcm93IGNsdXN0ZXJpbmcKaGVhdG1hcCh0b3ksIFJvd3YgPSBOVUxMLCBDb2x2ID0gTkEsIHNjYWxlID0gIm5vbmUiKQpgYGAKIyMjIEFkZGluZyBzY2FsaW5nIGRvZXNuJ3QgY2hhbmdlIHRoZSByZW9yZGVyaW5nCldlIGZvdW5kIHRoYXQgdGhlIGNsdXN0ZXJpbmcgaXMgbm90IHdoYXQgd2UgaGF2ZSBleHBlY3RlZCwgaS5lLiBnZW5lIDEvMyBhbmQgZ2VuZSAyLzQuIFRoaXMgaXMgYmVjYXVzZSBieSBkZWZhdWx0IGBoZWF0bWFwKClgIGNsdXN0ZXJzIHRoZSByb3dzIGJhc2VkIG9uIHRoZSB1bnNjYWxlZCB2YWx1ZXMuIFNvIHdoYXQgaWYgd2Ugc2V0IGBzY2FsZSA9ICJyb3ciYD8gTGV0J3Mgc2VlOgpgYGB7cn0KI2hlYXRtYXAgd2l0aCByb3cgc2NhbGluZyBhbmQgY2x1c3RlcmluZwpoZWF0bWFwKHRveSwgUm93diA9IE5VTEwsIENvbHYgPSBOQSwgc2NhbGUgPSAicm93IikKYGBgCiMjIyBJbXBsZW1lbnQgdGhlIHJlb3JkZXJpbmcgc3RlcCBvdXRzaWRlIHRoZSBgaGVhdG1hcCgpYCBmdW5jdGlvbgpTbyBub3cgdGhlIHBsb3R0ZWQgY29sb3JzIG1hdGNoIHRoZSBzY2FsZWQgdmFsdWVzLCBidXQgdGhlIGNsdXN0ZXJpbmcgb3JkZXIgaXMgc3RpbGwgdGhlIG9yaWdpbmFsISBUaGlzIHNob3dzIHRoYXQgdGhlIHNjYWxpbmcgc3RlcCBpcyBvbmx5IGZvciBwbG90dGluZywgbm90IGZvciByZW9yZGVyaW5nLiBXZSBjYW4gYWN0dWFsbHkgaW1wbGVtZW50IHRoZSBvcmRlcmluZyBzdGVwIG91dHNpZGUgb2YgdGhlIGBoZWF0bWFwKClgIGZ1bmN0aW9uCmBgYHtyfQojIGJlbG93IGlzIGhvdyByZW9yZGVyaW5nIGlzIGRvbmUgaW5zaWRlIHRoZSBoZWF0bWFwIGZ1bmN0aW9uCiMgcmVjYWxsIHRoYXQgd2UgaGF2ZSBzZXQgdG95LmRpc3QxID0gZGlzdCh0b3kpCnRveS5kaXN0MQojIHdlIGNhbiB0aGVuIGNsdXN0ZXIgdGhlIGdlbmVzIHVzaW5nIHRoaXMgZGlzdGFuY2UgbWF0cml4LCB3aGljaCB3ZSBzdG9yZWQgYXMgdG95LmNsdXN0MQpwbG90KHRveS5jbHVzdDEpCiMgd2UgY2FuIHRoZW4gdXNlIHRoaXMgb3JkZXIgaW4gdGhlIGhlYXRtYXAKaGVhdG1hcCh0b3ksIFJvd3YgPSBhcy5kZW5kcm9ncmFtKHRveS5jbHVzdDEpLCBDb2x2ID0gTkEsIHNjYWxlID0gInJvdyIpCmBgYApOb3cgdGhpcyBpcyB3aGF0IHdlIHdvdWxkIGhhdmUgZXhwZWN0ZWQuIFRoaXMgdGVsbHMgdXMgdGhhdCBpZiB3ZSBzaG91bGQgdGhpbmsgb2YgaGVhdG1hcCBhbmQgY2x1c3RlcmluZyBhcyB0d28gc3RlcHMsIGV2ZW4gdGhvdWdoIHRoZSBgaGVhdG1hcCgpYCBmdW5jdGlvbiBpbiBiYXNlIFIgYW5kIG1hbnkgb2YgaXRzIHZhcmlhdGlvbnMgY29tYmluZSB0aGUgdHdvLiBUaGlzIGhlbHBzIHVzZSBjbGVhcmx5IGRlZmluZQoKMS4gd2hpY2ggdmFyaWFibGUgZG8gd2Ugd2FudCB0byBjbHVzdGVyLCB0aGUgZ2VuZXMgb3IgdGhlIHRpbWUgc2VyaWVzIChvciBhbnkgb3RoZXIgZGltZW5zaW9uKT8KMS4gaG93IGRvIHdlIHdhbnQgdG8gbWVhc3VyZSB0aGUgZGlzc2ltaWxhcml0eSAoZGlzdGFuY2UpIC0tIGJ5IEV1Y2xpZGVhbiBkaXNhbmNlIG9yIFBlYXJzb24ncyBDb3JyZWxhdGlvbiBDb2VmZmljaWVudD8KMS4gaG93IGRvIHdlIHdhbnQgdG8gdmlzdWFsaXplIHRoZSBkYXRhLCBlLmcuIHdoZXRoZXIgdG8gcmVvcmRlciB0aGUgcm93cyBvciBjb2x1bW5zLCB3aGV0aGVyIHRvIHBsb3Qgc2NhbGVkIG9yIHVuc2NhbGVkIGRhdGEgZXRjLiBOb3RlIHRoYXQgc2NhbGluZyB3b3VsZCByZW1vdmUgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiBnZW5lcyBpbiB0aGVpciBhYnNvbHV0ZSBleHByZXNzaW9uIGxldmVsLCBsZWF2aW5nIG9ubHkgdGhlIHRlbXBvcmFsIGR5bmFtaWNzIHZpc2libGUuIFNvbWV0aW1lcyB0aGF0IG1heSBiZSBleGFjdGx5IHdoYXQgd2Ugd2FudCwgd2hpbGUgaW4gb3RoZXIgY2FzZXMgdGhhdCBtYXkgbm90IGJlIGRlc2lyYWJsZS4KCiMjIEFwcGx5IHRvIG91ciBkYXRhCiMjIyBwbG90IHRoZSByYXcgZGF0YSwgc2NhbGVkIG9yIG5vdApTaW5jZSB3ZSBhcmUgaW50ZXJlc3RlZCBpbiBnZW5lcyB0aGF0IGNoYW5nZSB0aGVpciBleHByZXNzaW9uIG92ZXIgdGhlIHRpbWUgY291cnNlLCBpdCBpcyBuYXR1cmFsIHRvIGZpcnN0IGxvb2sgYXQgdGhlIGRpc3RyaWJ1dGlvbiBvZiBtYXhpbXVtIGNoYW5nZSBpbiBleHByZXNzaW9uIGZvciBlYWNoIGdlbmUgb3ZlciBhbGwgdGltZSBwb2ludHMsIGFuZCB0aGVuIGNob29zZSBhIGN1dG9mZiBhbmQgb25seSBzZWxlY3QgdGhvc2UgZ2VuZXMgd2l0aCBtYXhpbXVtIGNoYW5nZSBpbiBleHByZXNzaW9uIGdyZWF0ZXIgdGhhbiB0aGF0IGN1dG9mZi4KYGBge3J9CiMgY2hlY2sgZGlzdHJpYnV0aW9uIG9mIGNoYW5nZXMKZGF0MS5hZ2dyICU+JSAKICBncm91cF9ieShnZW5lKSAlPiUgCiAgc3VtbWFyaXplKG1heC5leG4gPSBtYXgoYWJzKHJlbC5leG4pKSkgJT4lIAogIGdncGxvdChhZXMobWF4LmV4bikpICsgc3RhdF9lY2RmKGdlb20gPSAic3RlcCIpICsKICBzY2FsZV94X2NvbnRpbnVvdXMoYnJlYWtzID0gLTE6MTUpICsKICB4bGFiKCJsb2cyIG1heGltdW0gZm9sZCBjaGFuZ2UgaW4gZXhwcmVzc2lvbiByZWxhdGl2ZSB0byB0aW1lXzAiKSArCiAgeWxhYigiY3VtdWxhdGl2ZSAjIG9mIGdlbmVzIikgKwogIGdndGl0bGUoIkN1bXVsYXRpdmUgZGlzdHJpYnV0aW9uIG9mIG1heGltdW0gZm9sZCBjaGFuZ2UgaW4gZXhwcmVzc2lvbiIpCmBgYApMZXQncyBzZWxlY3QgdGhlIGdlbmVzIHdpdGggYSBtYXhpbXVtIGZvbGQgY2hhbmdlIG9mIDQgb3IgYWJvdmUgKGxvZzIgZm9sZCBjaGFuZ2Ugb2YgMiBvciBhYm92ZSkKYGBge3J9CiMgc3Vic2V0IHRoZSBkYXRhCm1vcmV0aGFuNGZvbGQgPC0gYXBwbHkobS5kYXQyLCAxLCBmdW5jdGlvbih4KSBhbnkoYWJzKHgpID49IDIpKQptLmRhdDMgPC0gbS5kYXQyW21vcmV0aGFuNGZvbGQsXQpgYGAKCk5vdyB3ZSBjYW4gcGxvdCB0aGUgbG9nMiBmb2xkIGNoYW5nZXMgcmVsYXRpdmUgdG8gdGltZSAwIGZvciB0aGVzZSBnZW5lczoKYGBge3J9CiMgd2Ugd2lsbCB1c2UgdGhlIHBoZWF0bWFwIGZ1bmN0aW9uIGZyb20gdGhlIHBoZWF0bWFwIHBhY2thZ2UsIHdoaWNoIGlzIAojIHNpbWlsYXIgYnV0IHdpdGggYmV0dGVyIGRlZmF1bHRzIHRoYW4gdGhlIGJhc2UgUidzIGhlYXRtYXAoKQpzdXBwcmVzc1BhY2thZ2VTdGFydHVwTWVzc2FnZXMobGlicmFyeShwaGVhdG1hcCkpCiMgbm1mLm9wdGlvbnMoZ3JpZC5wYXRjaD1UUlVFKQpjb2xvdXIgPC0gY29sb3JSYW1wUGFsZXR0ZSggYygiYmx1ZSIsICJibGFjayIsICJ5ZWxsb3ciKSwgc3BhY2U9InJnYiIpKDY0KSAjIGZvciBwbG90dGluZwpwaGVhdG1hcChtLmRhdDMsIGNvbG9yID0gY29sb3VyLCBicmVha3MgPSBzZXEoLTgsOCxsZW5ndGgub3V0ID0gNjUpLCBjbHVzdGVyX3Jvd3MgPSBGLCBjbHVzdGVyX2NvbHMgPSBGLCBzY2FsZSA9ICJub25lIiwgbGFiZWxzX3JvdyA9ICIiKQpgYGAKTm93IGxldCdzIHRyeSB0byBjbHVzdGVyIHRoZSBnZW5lcyB1c2luZyBQZWFyc29uJ3MgQ29ycmVsYXRpb24gQ29lZmZpY2llbnQuIEZpcnN0LCB3ZSB3aWxsIGNvbXB1dGUgdGhlIGNvcnJlbGF0aW9uIG1hdHJpeCBhbmQgdmlzdWFsaXplIGl0IHVzaW5nIHRoZSBgaW1hZ2UoKWAgZnVuY3Rpb24sIHdpdGggcmVvcmRlcmluZyBiYXNlZCBvbiBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4KYGBge3IsIGZpZy53aWR0aD01LCBmaWcuaGVpZ2h0PTV9CmxpYnJhcnkoY29ycnBsb3QpICMgcGxvdCBjb3JyZWxhdGlvbiBtYXRyaXggaW4gaGVhdG1hcCBmb3JtYXQKZGF0My5jb3IgPC0gY29yKHQobS5kYXQzKSwgbWV0aG9kID0gInBlYXJzb24iKQpkYXQzLmhjIDwtIGhjbHVzdChhcy5kaXN0KDEtZGF0My5jb3IpLCBtZXRob2QgPSAiY29tcGxldGUiKQpvZCA8LSBkYXQzLmhjJG9yZGVyCmNvbG91ciA8LSBjb2xvclJhbXBQYWxldHRlKCBjKCJibHVlIiwgImJsYWNrIiwgInllbGxvdyIpLCBzcGFjZT0icmdiIikoNjQpCmNvcnJwbG90KGRhdDMuY29yLCBjb2wgPSBjb2xvdXIsIG1ldGhvZCA9ICJjb2xvciIsIG9yZGVyID0gImhjbHVzdCIsIGhjbHVzdC5tZXRob2QgPSAid2FyZC5EIiwgYWRkcmVjdCA9IDQsIHRsLnBvcyA9ICJuIiwgdGl0bGUgPSAiUGFpcndpc2UgUGVhcnNvbidzIENvcnJlbGF0aW9uIENvZWZmaWNpZW50IGZvciAxNTE5IGdlbmVzIHdpdGggPjQgZm9sZCBjaGFuZ2UiKQpgYGAKCk5leHQgd2UgYXBwbHkgdGhlIGNsdXN0ZXJpbmcgb3JkZXIgdG8gdGhlIHJvd3MgaW4gdGhlIGhlYXRtYXAgZm9yIGdlbmUgZXhwcmVzc2lvbi4KYGBge3J9CnBoZWF0bWFwKG0uZGF0MywgY29sb3IgPSBjb2xvdXIsIGJyZWFrcyA9IHNlcSgtOCw4LGxlbmd0aC5vdXQgPSA2NSksIGNsdXN0ZXJfcm93cyA9IGRhdDMuaGMsIGNsdXN0ZXJfY29scyA9IEYsIHNjYWxlID0gIm5vbmUiLCBsYWJlbHNfcm93ID0gIiIpCmBgYAoKQW5vdGhlciBxdWVzdGlvbiBpcyBob3cgc2ltaWxhciBhcmUgdGhlIHRpbWUgcG9pbnRzIHdpdGggZWFjaCBvdGhlci4gV2UgdXNlIHNpbWlsYXIgYXBwcm9hY2hlcyBhYm92ZSwgYnV0IHRoaXMgdGltZSBhcHBsaWVkIHRvIHRoZSB0aW1lIHBvaW50cyBhcyBjb2x1bW5zLgpgYGB7ciwgZmlnLndpZHRoPTYsIGZpZy5oZWlnaHQ9NX0KZGF0MS5jb3IgPC0gY29yKG0uZGF0MSwgbWV0aG9kID0gInBlYXJzb24iKQpkYXQxLmhjIDwtIGhjbHVzdChhcy5kaXN0KDEtZGF0MS5jb3IpLCBtZXRob2QgPSAiY29tcGxldGUiKQpvZDEgPC0gZGF0MS5oYyRvcmRlcgpjb2xvdXIgPC0gY29sb3JSYW1wUGFsZXR0ZSggYygiYmx1ZSIsICJibGFjayIsICJ5ZWxsb3ciKSwgc3BhY2U9InJnYiIpKDY0KQpwaGVhdG1hcChkYXQxLmNvciwgY29sID0gY29sb3VyLCBjbHVzdGVyX3Jvd3MgPSBGLCBjbHVzdGVyX2NvbHMgPSBGLCBzY2FsZSA9ICJub25lIikKYGBgYAoKVGhlIHJlc3VsdCBpcyBzZWxmLWV4cGxhbmF0b3J5Lg==