1. load libraries

2. Nice function to easily draw a graph:

3. Reading data

All_samples_Merged <- readRDS("../../All_samples_Merged_with_STCAT_and_renamed_FINAL.rds")

Define some color palette



# Define some color palette
pal <- c(scales::hue_pal()(8), RColorBrewer::brewer.pal(9, "Set1"), RColorBrewer::brewer.pal(8, "Set2"))
set.seed(1)
pal <- rep(sample(pal, length(pal)), 200)

4. Trajectory inference using Slingshot

             used   (Mb) gc trigger    (Mb)   max used   (Mb)
Ncells    8836312  472.0   15780645   842.8   11849183  632.9
Vcells 1232081946 9400.1 1529471188 11669.0 1243595250 9487.9

Let’s visualize which clusters we have in our dataset:


vars <- c("Patient_origin", "orig.ident", "seurat_clusters", "Phase")
pl <- list()

for (i in vars) {
  pl[[i]] <- DimPlot(obj, group.by = i, label = T) + theme_void() + NoLegend()
}
wrap_plots(pl)


table(obj$seurat_clusters)

   0    1    2    3    4    5    6    7    8    9   10   11   12   13 
6789 5275 4663 4661 4086 3634 3536 3409 3338 3273 3212 1675 1063  691 

5. Exploring the data


vars <- c("TOX", "LAG3", "CTLA4", "TIGIT", "FOXP3", "IL2RA", "CTLA4", "IKZF2", "TIGIT", "CCR7", "SELL", "IL7R", "TCF7", "CCR7", "SELL", "IL7R", "TCF7", "LEF1", "GZMB", "PRF1", "IFNG", "KLRG1", "CD69", "CXCR6", "PRF1", "GZMB", "NKG7", "GNLY", "ISG15", "IFI6", "IFIT3", "MX1", "MKI67", "TOP2A", "STAT3", "AHR", "CCR6", "BATF", "PTPRC", "GZMB", "BCL6", "ICOS", "HSPA1A", "ATF3", "IL2RA", "CD69", "HLA-DRA", "CD34")
pl <- list()

pl <- list(DimPlot(obj, group.by = "seurat_clusters", label = T) + theme_void() + NoLegend())
for (i in vars) {
  pl[[i]] <- FeaturePlot(obj, features = i, order = T) + theme_void() + NoLegend()
}
wrap_plots(pl)

NA
NA

. Exploring the data-2


# Load necessary libraries
library(Seurat)
library(patchwork)
library(glue)

# Define marker groups
marker_groups <- list(
  "CD4 Tex (Exhausted)" = c("TOX", "LAG3", "CTLA4", "TIGIT"),
  "CD4 Treg" = c("FOXP3", "IL2RA", "CTLA4", "IKZF2", "TIGIT"),
  "CD4 Tcm (Central Memory)" = c("CCR7", "SELL", "IL7R", "TCF7"),
  "CD4 Tn (Naive)" = c("CCR7", "SELL", "IL7R", "TCF7", "LEF1"),
  "CD4 Tem (Effector Memory)" = c("GZMB", "PRF1", "IFNG", "KLRG1"),
  "CD4 Trm (Tissue Resident)" = c("CD69", "CXCR6"),
  "CD4 Tc (Cytotoxic)" = c("PRF1", "GZMB", "NKG7", "GNLY"),
  "CD4 Tisg (IFN Signature)" = c("ISG15", "IFI6", "IFIT3", "MX1"),
  "CD4 Proliferation" = c("MKI67", "TOP2A"),
  "CD4 Th17" = c("STAT3", "AHR", "CCR6", "BATF"),
  "CD4 Temra (Effector Memory RA+)" = c("PTPRC", "GZMB"),
  "CD4 Tfh (Follicular Helper)" = c("BCL6", "ICOS"),
  "CD4 Tstr (Stress)" = c("HSPA1A", "ATF3"),
  "CD4 Activated" = c("IL2RA", "CD69", "HLA-DRA")
)

# OPTIONAL: Uncomment this to save all plots in a single PDF
# pdf("CD4_MarkerGroups_FeaturePlots.pdf", width = 12, height = 10)

# Main plotting loop
for (group_name in names(marker_groups)) {
  genes <- unique(marker_groups[[group_name]])
  message(glue("Plotting: {group_name}"))

  # Cleaner titles and better theme
  pl <- lapply(genes, function(gene) {
    FeaturePlot(obj, features = gene, order = TRUE) +
      ggtitle(gene) +  # shorter title
      theme_minimal(base_size = 10) +  # use minimal for spacing
      NoLegend()
  })

  # Combine plots
  combined_plot <- wrap_plots(pl, ncol = 2) +  # fewer columns = more space
                   plot_annotation(title = group_name)

  print(combined_plot)
}

# OPTIONAL: Uncomment if using pdf()
# dev.off()

. Exploring the data-3


# Required markers
progenitor_markers <- c("CD34", "KIT", "GATA2", "MKI67", "PROM1", "FLT3")

# Feature plots for each marker
FeaturePlot(obj, features = progenitor_markers, order = TRUE, ncol = 3)

NA
NA
NA
NA

6. compute the lineages on these dataset

set.seed(1)

# # Define lineage ends
ENDS <- c("1", "4", "8" , "0","13")

set.seed(1)
lineages <- as.SlingshotDataSet(getLineages(
  data           = obj@reductions$umap@cell.embeddings,
  clusterLabels  = obj$seurat_clusters,
  dist.method    = "mnn", # It can be: "simple", "scaled.full", "scaled.diag", "slingshot" or "mnn"
  end.clus       = ENDS, # You can also define the ENDS!
  start.clus     = "3"
)) # define where to START the trajectories


# IF NEEDED, ONE CAN ALSO MANULALLY EDIT THE LINEAGES, FOR EXAMPLE:
# sel <- sapply( lineages@lineages, function(x){rev(x)[1]} ) %in% ENDS
# lineages@lineages <- lineages@lineages[ sel ]
# names(lineages@lineages) <- paste0("Lineage",1:length(lineages@lineages))
# lineages


# Change the reduction to our "fixed" UMAP2d (FOR VISUALISATION ONLY)
lineages@reducedDim <- obj@reductions$umap@cell.embeddings

{
  plot(obj@reductions$umap@cell.embeddings, col = pal[obj$seurat_clusters], cex = .5, pch = 16)
  lines(lineages, lwd = 1, col = "black", cex = 2)
  text(centroids2d, labels = rownames(centroids2d), cex = 0.8, font = 2, col = "white")
}

Defining Principal Curves


# Define curves
curves <- as.SlingshotDataSet(getCurves(
  data          = lineages,
  thresh        = 1e-1,
  stretch       = 1e-1,
  allow.breaks  = F,
  approx_points = 1000
))

curves
class: SlingshotDataSet 

lineages: 7 
Lineage1: 3  5  7  9  2  6  13  
Lineage2: 3  5  7  9  2  6  8  
Lineage3: 3  5  7  9  4  
Lineage4: 3  5  7  0  
Lineage5: 3  5  7  11  
Lineage6: 3  5  7  12  
Lineage7: 3  10  1  

curves: 7 
Curve1: Length: 41.042  Samples: 23200.83
Curve2: Length: 28.57   Samples: 24480.98
Curve3: Length: 22.1    Samples: 16916.57
Curve4: Length: 26.704  Samples: 21446.99
Curve5: Length: 26.124  Samples: 13694.79
Curve6: Length: 27.465  Samples: 13510.43
Curve7: Length: 17.775  Samples: 13465.54

Plot


# Plots
{
  plot(obj@reductions$umap@cell.embeddings, col = pal[obj$seurat_clusters], pch = 16)
  lines(curves, lwd = 2, col = "black")
  text(centroids2d, labels = levels(obj$seurat_clusters), cex = 1, font = 2)
}

compute the differentiation pseudotime


pseudotime <- slingPseudotime(curves, na = FALSE)
cellWeights <- slingCurveWeights(curves)

x <- rowMeans(pseudotime)
x <- x / max(x)
o <- order(x)

{
  plot(obj@reductions$umap@cell.embeddings[o, ],
    main = paste0("pseudotime"), pch = 16, cex = 0.4, axes = F, xlab = "", ylab = "",
    col = colorRampPalette(c("grey70", "orange3", "firebrick", "purple4"))(99)[x[o] * 98 + 1]
  )
  points(centroids2d, cex = 2.5, pch = 16, col = "#FFFFFF99")
  text(centroids2d, labels = levels(obj$seurat_clusters), cex = 1, font = 2)
}

7. Finding differentially expressed genes


# 🔴 CHANGE: Use all cells
sel_cells <- colnames(obj)

# 🔴 CHANGE: Use existing HVGs
hvg_genes <- VariableFeatures(obj)

library(BiocParallel)
# Use raw counts (needed for tradeSeq fitGAM)
counts_mat <- GetAssayData(obj, assay = "RNA", slot = "counts")


pseudotime_sel <- pseudotime[sel_cells, , drop = FALSE]

all(sel_cells %in% rownames(pseudotime))    # should be TRUE
[1] TRUE
all(sel_cells %in% rownames(cellWeights))  # should be TRUE
[1] TRUE
sceGAM <- fitGAM(
  counts = drop0(counts_mat[hvg_genes, sel_cells]),
  pseudotime = pseudotime_sel,
  cellWeights = cellWeights[sel_cells, , drop = FALSE],
  nknots = 7,
  verbose = TRUE,
  parallel = FALSE,  # start serially to avoid memory issues
  sce = TRUE
)

  |                                                  | 0 % ~calculating  
  |+                                                 | 1 % ~17h 10m 34s  
  |+                                                 | 2 % ~13h 37m 55s  
  |++                                                | 3 % ~12h 57m 50s  
  |++                                                | 4 % ~11h 46m 57s  
  |+++                                               | 5 % ~10h 48m 20s  
  |+++                                               | 6 % ~10h 26m 10s  
  |++++                                              | 7 % ~09h 50m 33s  
  |++++                                              | 8 % ~10h 12m 47s  
  |+++++                                             | 9 % ~09h 48m 23s  
  |+++++                                             | 10% ~09h 32m 08s  
  |++++++                                            | 11% ~09h 18m 31s  
  |++++++                                            | 12% ~09h 00m 59s  
  |+++++++                                           | 13% ~08h 45m 02s  
  |+++++++                                           | 14% ~08h 31m 56s  
  |++++++++                                          | 15% ~08h 17m 02s  
  |++++++++                                          | 16% ~08h 04m 38s  
  |+++++++++                                         | 17% ~07h 53m 17s  
  |+++++++++                                         | 18% ~07h 43m 17s  
  |++++++++++                                        | 19% ~07h 33m 30s  
  |++++++++++                                        | 20% ~07h 25m 29s  
  |+++++++++++                                       | 21% ~07h 15m 59s  
  |+++++++++++                                       | 22% ~07h 05m 33s  
  |++++++++++++                                      | 23% ~06h 56m 44s  
  |++++++++++++                                      | 24% ~06h 48m 31s  
  |+++++++++++++                                     | 25% ~06h 40m 41s  
  |+++++++++++++                                     | 26% ~06h 32m 36s  
  |++++++++++++++                                    | 27% ~06h 26m 28s  
  |++++++++++++++                                    | 28% ~06h 19m 01s  
  |+++++++++++++++                                   | 29% ~06h 10m 51s  
  |+++++++++++++++                                   | 30% ~06h 03m 35s  
  |++++++++++++++++                                  | 31% ~05h 56m 42s  
  |++++++++++++++++                                  | 32% ~05h 49m 59s  
  |+++++++++++++++++                                 | 33% ~05h 44m 32s  
  |+++++++++++++++++                                 | 34% ~05h 38m 33s  
  |++++++++++++++++++                                | 35% ~05h 32m 03s  
  |++++++++++++++++++                                | 36% ~05h 26m 07s  
  |+++++++++++++++++++                               | 37% ~05h 20m 02s  
  |+++++++++++++++++++                               | 38% ~05h 13m 43s  
  |++++++++++++++++++++                              | 39% ~05h 08m 29s  
  |++++++++++++++++++++                              | 40% ~05h 01m 40s  
  |+++++++++++++++++++++                             | 41% ~04h 55m 33s  
  |+++++++++++++++++++++                             | 42% ~04h 49m 10s  
  |++++++++++++++++++++++                            | 43% ~04h 43m 31s  
  |++++++++++++++++++++++                            | 44% ~04h 37m 44s  
  |+++++++++++++++++++++++                           | 45% ~04h 31m 58s  
  |+++++++++++++++++++++++                           | 46% ~04h 25m 55s  
  |++++++++++++++++++++++++                          | 47% ~04h 20m 30s  
  |++++++++++++++++++++++++                          | 48% ~04h 14m 41s  
  |+++++++++++++++++++++++++                         | 49% ~04h 09m 51s  
  |+++++++++++++++++++++++++                         | 50% ~04h 04m 17s  
  |++++++++++++++++++++++++++                        | 51% ~03h 58m 55s  
  |++++++++++++++++++++++++++                        | 52% ~03h 53m 48s  
  |+++++++++++++++++++++++++++                       | 53% ~03h 48m 30s  
  |+++++++++++++++++++++++++++                       | 54% ~03h 43m 03s  
  |++++++++++++++++++++++++++++                      | 55% ~03h 37m 37s  
  |++++++++++++++++++++++++++++                      | 56% ~03h 32m 17s  
  |+++++++++++++++++++++++++++++                     | 57% ~03h 27m 06s  
  |+++++++++++++++++++++++++++++                     | 58% ~03h 21m 49s  
  |++++++++++++++++++++++++++++++                    | 59% ~03h 16m 41s  
  |++++++++++++++++++++++++++++++                    | 60% ~03h 11m 23s  
  |+++++++++++++++++++++++++++++++                   | 61% ~03h 06m 18s  
  |+++++++++++++++++++++++++++++++                   | 62% ~03h 01m 13s  
  |++++++++++++++++++++++++++++++++                  | 63% ~02h 56m 37s  
  |++++++++++++++++++++++++++++++++                  | 64% ~02h 51m 23s  
  |+++++++++++++++++++++++++++++++++                 | 65% ~02h 46m 42s  
  |+++++++++++++++++++++++++++++++++                 | 66% ~02h 41m 47s  
  |++++++++++++++++++++++++++++++++++                | 67% ~02h 37m 09s  
  |++++++++++++++++++++++++++++++++++                | 68% ~02h 32m 06s  
  |+++++++++++++++++++++++++++++++++++               | 69% ~02h 27m 07s  
  |+++++++++++++++++++++++++++++++++++               | 70% ~02h 22m 07s  
  |++++++++++++++++++++++++++++++++++++              | 71% ~02h 17m 05s  
  |++++++++++++++++++++++++++++++++++++              | 72% ~02h 12m 06s  
  |+++++++++++++++++++++++++++++++++++++             | 73% ~02h 07m 04s  
  |+++++++++++++++++++++++++++++++++++++             | 74% ~02h 02m 11s  
  |++++++++++++++++++++++++++++++++++++++            | 75% ~01h 57m 29s  
  |++++++++++++++++++++++++++++++++++++++            | 76% ~01h 52m 37s  
  |+++++++++++++++++++++++++++++++++++++++           | 77% ~01h 47m 47s  
  |+++++++++++++++++++++++++++++++++++++++           | 78% ~01h 42m 52s  
  |++++++++++++++++++++++++++++++++++++++++          | 79% ~01h 38m 04s  
  |++++++++++++++++++++++++++++++++++++++++          | 80% ~01h 33m 16s  
  |+++++++++++++++++++++++++++++++++++++++++         | 81% ~01h 28m 27s  
  |+++++++++++++++++++++++++++++++++++++++++         | 82% ~01h 23m 43s  
  |++++++++++++++++++++++++++++++++++++++++++        | 83% ~01h 18m 58s  
  |++++++++++++++++++++++++++++++++++++++++++        | 84% ~01h 14m 13s  
  |+++++++++++++++++++++++++++++++++++++++++++       | 85% ~01h 09m 32s  
  |+++++++++++++++++++++++++++++++++++++++++++       | 86% ~01h 04m 45s  
  |++++++++++++++++++++++++++++++++++++++++++++      | 87% ~01h 00m 07s  
  |++++++++++++++++++++++++++++++++++++++++++++      | 88% ~55m 24s      
  |+++++++++++++++++++++++++++++++++++++++++++++     | 89% ~50m 46s      
  |+++++++++++++++++++++++++++++++++++++++++++++     | 90% ~46m 12s      
  |++++++++++++++++++++++++++++++++++++++++++++++    | 91% ~41m 33s      
  |++++++++++++++++++++++++++++++++++++++++++++++    | 92% ~36m 57s      
  |+++++++++++++++++++++++++++++++++++++++++++++++   | 93% ~32m 18s      
  |+++++++++++++++++++++++++++++++++++++++++++++++   | 94% ~27m 38s      
  |++++++++++++++++++++++++++++++++++++++++++++++++  | 95% ~23m 01s      
  |++++++++++++++++++++++++++++++++++++++++++++++++  | 96% ~18m 24s      
  |+++++++++++++++++++++++++++++++++++++++++++++++++ | 97% ~13m 48s      
  |+++++++++++++++++++++++++++++++++++++++++++++++++ | 98% ~09m 11s      
  |++++++++++++++++++++++++++++++++++++++++++++++++++| 99% ~04m 35s      
  |++++++++++++++++++++++++++++++++++++++++++++++++++| 100% elapsed=07h 38m 38s
# Visualize gene counts per lineage
plotGeneCount(curves, clusters = obj$seurat_clusters, models = sceGAM)


# Plot lineages
lc <- sapply(lineages@lineages, function(x) {rev(x)[1]})
names(lc) <- gsub("Lineage", "L", names(lc))
lc.idx = match(lc, levels(obj$seurat_clusters))

plot(obj@reductions$umap@cell.embeddings, col = pal[obj$seurat_clusters], pch = 16)
lines(curves, lwd = 2, col = "black")
points(centroids2d[lc.idx, ], col = "black", pch = 16, cex = 4)
text(centroids2d[lc.idx, ], labels = names(lc), cex = 1, font = 2, col = "white")

Genes that change with pseudotime

gc()
             used    (Mb) gc trigger    (Mb)    max used    (Mb)
Ncells    9541130   509.6   19618421  1047.8    18617056   994.3
Vcells 1659947594 12664.4 9093818920 69380.4 11367270202 86725.4
set.seed(8)
res <- na.omit(associationTest(sceGAM, contrastType = "consecutive"))
res <- res[res$pvalue < 1e-3, ]
res <- res[res$waldStat > mean(res$waldStat), ]
res <- res[order(res$waldStat, decreasing = T), ]
res[1:10, ]
NA

We can plot their expression


par(mfrow = c(4, 4), mar = c(.1, .1, 2, 1))
{
  plot(obj@reductions$umap@cell.embeddings, col = pal[obj$seurat_clusters], cex = .5, pch = 16, axes = F, xlab = "", ylab = "")
  lines(curves, lwd = 2, col = "black")
  points(centroids2d[lc.idx, ], col = "black", pch = 15, cex = 3, xpd = T)
  text(centroids2d[lc.idx, ], labels = names(lc), cex = 1, font = 2, col = "white", xpd = T)
}

vars <- rownames(res[1:15, ])
vars <- na.omit(vars[vars != "NA"])

for (i in vars) {
  x <- drop0(obj@assays$SCT@data)[i, ]
  x <- (x - min(x)) / (max(x) - min(x))
  o <- order(x)
  plot(obj@reductions$umap@cell.embeddings[o, ],
    main = paste0(i), pch = 16, cex = 0.5, axes = F, xlab = "", ylab = "",
    col = colorRampPalette(c("lightgray", "grey60", "navy"))(99)[x[o] * 98 + 1]
  )
}

Genes that change between two pseudotime points

res <- na.omit(startVsEndTest(sceGAM, pseudotimeValues = c(0, 1)))
res <- res[res$pvalue < 1e-3, ]
res <- res[res$waldStat > mean(res$waldStat), ]
res <- res[order(res$waldStat, decreasing = T), ]
res[1:10, 1:6]

identify which genes go up or down. Let’s check lineage 1:

# Get the top UP and Down regulated in lineage 1
res_lin1 <- sort(setNames(res$logFClineage1, rownames(res)))
vars <- names(c(rev(res_lin1)[1:7], res_lin1[1:8]))
vars <- na.omit(vars[vars != "NA"])

par(mfrow = c(4, 4), mar = c(.1, .1, 2, 1))

{
  plot(obj@reductions$umap@cell.embeddings, col = pal[obj$seurat_clusters], cex = .5, pch = 16, axes = F, xlab = "", ylab = "")
  lines(curves, lwd = 2, col = "black")
  points(centroids2d[lc.idx, ], col = "black", pch = 15, cex = 3, xpd = T)
  text(centroids2d[lc.idx, ], labels = names(lc), cex = 1, font = 2, col = "white", xpd = T)
}

for (i in vars) {
  x <- drop0(obj@assays$SCT@data)[i, ]
  x <- (x - min(x)) / (max(x) - min(x))
  o <- order(x)
  plot(obj@reductions$umap@cell.embeddings[o, ],
    main = paste0(i), pch = 16, cex = 0.5, axes = F, xlab = "", ylab = "",
    col = colorRampPalette(c("lightgray", "grey60", "navy"))(99)[x[o] * 98 + 1]
  )
}

Genes that are different between lineages

res <- na.omit(diffEndTest(sceGAM))
res <- res[res$pvalue < 1e-3, ]
res <- res[res$waldStat > mean(res$waldStat), ]
res <- res[order(res$waldStat, decreasing = T), ]
res[1:10, ]
NA

pairwise comparison between each lineage. Let’s check lineage 1 vs lineage 2:

# Get the top UP and Down regulated in lineage 1 vs 2
res_lin1_2 <- sort(setNames(res$logFC1_2, rownames(res)))
vars <- names(c(rev(res_lin1_2)[1:7], res_lin1_2[1:8]))
vars <- na.omit(vars[vars != "NA"])

par(mfrow = c(4, 4), mar = c(.1, .1, 2, 1))
{
  plot(obj@reductions$umap@cell.embeddings, col = pal[obj$seurat_clusters], cex = .5, pch = 16, axes = F, xlab = "", ylab = "")
  lines(curves, lwd = 2, col = "black")
  points(centroids2d[lc.idx, ], col = "black", pch = 15, cex = 3, xpd = T)
  text(centroids2d[lc.idx, ], labels = names(lc), cex = 1, font = 2, col = "white", xpd = T)
}

for (i in vars) {
  x <- drop0(obj@assays$SCT@data)[i, ]
  x <- (x - min(x)) / (max(x) - min(x))
  o <- order(x)
  plot(obj@reductions$umap@cell.embeddings[o, ],
    main = paste0(i), pch = 16, cex = 0.5, axes = F, xlab = "", ylab = "",
    col = colorRampPalette(c("lightgray", "grey60", "navy"))(99)[x[o] * 98 + 1]
  )
}

save sceGAM after fitting:

saveRDS(sceGAM, "sceGAM_allHVGs.rds")

save sceGAM after fitting:

saveRDS(obj, "All_samples_Merged_after_Slingshot.rds")
LS0tCnRpdGxlOiAiVHJhamVjdG9yeSBpbmZlcmVuY2UgdXNpbmcgU2xpbmdzaG90IgphdXRob3I6IE5hc2lyIE1haG1vb2QgQWJiYXNpCmRhdGU6ICJgciBTeXMuRGF0ZSgpYCIKb3V0cHV0OgogICNybWRmb3JtYXRzOjpyZWFkdGhlZG93bgogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgdG9jX2NvbGxhcHNlZDogdHJ1ZQotLS0KCiMgMS4gbG9hZCBsaWJyYXJpZXMKYGBge3IsIGluY2x1ZGU9RkFMU0V9CnN1cHByZXNzUGFja2FnZVN0YXJ0dXBNZXNzYWdlcyh7CiAgbGlicmFyeShTZXVyYXQpCiAgbGlicmFyeShwbG90bHkpCiAgb3B0aW9ucyhyZ2wucHJpbnRSZ2x3aWRnZXQgPSBUUlVFKQogIGxpYnJhcnkoTWF0cml4KQogIGxpYnJhcnkoc3BhcnNlTWF0cml4U3RhdHMpCiAgbGlicmFyeShzbGluZ3Nob3QpCiAgbGlicmFyeSh0cmFkZVNlcSkKICBsaWJyYXJ5KHBhdGNod29yaykKfSkKCgpgYGAKCiMgMi4gTmljZSBmdW5jdGlvbiB0byBlYXNpbHkgZHJhdyBhIGdyYXBoOgpgYGB7ciwgaW5jbHVkZT1GQUxTRX0KIyBBZGQgZ3JhcGggdG8gdGhlIGJhc2UgUiBncmFwaGljcyBwbG90CmRyYXdfZ3JhcGggPC0gZnVuY3Rpb24obGF5b3V0LCBncmFwaCwgbHdkID0gMC4yLCBjb2wgPSAiZ3JleSIpIHsKICByZXMgPC0gcmVwKHggPSAxOihsZW5ndGgoZ3JhcGhAcCkgLSAxKSwgdGltZXMgPSAoZ3JhcGhAcFstMV0gLSBncmFwaEBwWy1sZW5ndGgoZ3JhcGhAcCldKSkKICBzZWdtZW50cygKICAgIHgwID0gbGF5b3V0W2dyYXBoQGkgKyAxLCAxXSwgeDEgPSBsYXlvdXRbcmVzLCAxXSwKICAgIHkwID0gbGF5b3V0W2dyYXBoQGkgKyAxLCAyXSwgeTEgPSBsYXlvdXRbcmVzLCAyXSwgbHdkID0gbHdkLCBjb2wgPSBjb2wKICApCn0KYGBgCgojIDMuIFJlYWRpbmcgZGF0YQpgYGB7cn0KQWxsX3NhbXBsZXNfTWVyZ2VkIDwtIHJlYWRSRFMoIi4uLy4uL0FsbF9zYW1wbGVzX01lcmdlZF93aXRoX1NUQ0FUX2FuZF9yZW5hbWVkX0ZJTkFMLnJkcyIpCgoKYGBgCgoKIyMgIERlZmluZSBzb21lIGNvbG9yIHBhbGV0dGUKYGBge3J9CgoKIyBEZWZpbmUgc29tZSBjb2xvciBwYWxldHRlCnBhbCA8LSBjKHNjYWxlczo6aHVlX3BhbCgpKDgpLCBSQ29sb3JCcmV3ZXI6OmJyZXdlci5wYWwoOSwgIlNldDEiKSwgUkNvbG9yQnJld2VyOjpicmV3ZXIucGFsKDgsICJTZXQyIikpCnNldC5zZWVkKDEpCnBhbCA8LSByZXAoc2FtcGxlKHBhbCwgbGVuZ3RoKHBhbCkpLCAyMDApCgpgYGAKCiMgNC4gVHJhamVjdG9yeSBpbmZlcmVuY2UgdXNpbmcgU2xpbmdzaG90CmBgYHtyLCBlY2hvPUZBTFNFfQpvYmogPC1BbGxfc2FtcGxlc19NZXJnZWQKCnJtKEFsbF9zYW1wbGVzX01lcmdlZCkKCmdjKCkKCiMgQ2FsY3VsYXRlIGNsdXN0ZXIgY2VudHJvaWRzIChmb3IgcGxvdHRpbmcgdGhlIGxhYmVscyBsYXRlcikKbW0gPC0gc3BhcnNlLm1vZGVsLm1hdHJpeCh+IDAgKyBmYWN0b3Iob2JqJHNldXJhdF9jbHVzdGVycykpCmNvbG5hbWVzKG1tKSA8LSBsZXZlbHMoZmFjdG9yKG9iaiRzZXVyYXRfY2x1c3RlcnMpKQpjZW50cm9pZHMyZCA8LSBhcy5tYXRyaXgodCh0KG9iakByZWR1Y3Rpb25zJHVtYXBAY2VsbC5lbWJlZGRpbmdzKSAlKiUgbW0pIC8gTWF0cml4Ojpjb2xTdW1zKG1tKSkKCmBgYAoKCiMjIExldOKAmXMgdmlzdWFsaXplIHdoaWNoIGNsdXN0ZXJzIHdlIGhhdmUgaW4gb3VyIGRhdGFzZXQ6CmBgYHtyLCBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD0xMH0KCnZhcnMgPC0gYygiUGF0aWVudF9vcmlnaW4iLCAib3JpZy5pZGVudCIsICJzZXVyYXRfY2x1c3RlcnMiLCAiUGhhc2UiKQpwbCA8LSBsaXN0KCkKCmZvciAoaSBpbiB2YXJzKSB7CiAgcGxbW2ldXSA8LSBEaW1QbG90KG9iaiwgZ3JvdXAuYnkgPSBpLCBsYWJlbCA9IFQpICsgdGhlbWVfdm9pZCgpICsgTm9MZWdlbmQoKQp9CndyYXBfcGxvdHMocGwpCgp0YWJsZShvYmokc2V1cmF0X2NsdXN0ZXJzKQpgYGAKCiMgNS4gRXhwbG9yaW5nIHRoZSBkYXRhCmBgYHtyfQoKdmFycyA8LSBjKCJUT1giLCAiTEFHMyIsICJDVExBNCIsICJUSUdJVCIsICJGT1hQMyIsICJJTDJSQSIsICJDVExBNCIsICJJS1pGMiIsICJUSUdJVCIsICJDQ1I3IiwgIlNFTEwiLCAiSUw3UiIsICJUQ0Y3IiwgIkNDUjciLCAiU0VMTCIsICJJTDdSIiwgIlRDRjciLCAiTEVGMSIsICJHWk1CIiwgIlBSRjEiLCAiSUZORyIsICJLTFJHMSIsICJDRDY5IiwgIkNYQ1I2IiwgIlBSRjEiLCAiR1pNQiIsICJOS0c3IiwgIkdOTFkiLCAiSVNHMTUiLCAiSUZJNiIsICJJRklUMyIsICJNWDEiLCAiTUtJNjciLCAiVE9QMkEiLCAiU1RBVDMiLCAiQUhSIiwgIkNDUjYiLCAiQkFURiIsICJQVFBSQyIsICJHWk1CIiwgIkJDTDYiLCAiSUNPUyIsICJIU1BBMUEiLCAiQVRGMyIsICJJTDJSQSIsICJDRDY5IiwgIkhMQS1EUkEiLCAiQ0QzNCIpCnBsIDwtIGxpc3QoKQoKcGwgPC0gbGlzdChEaW1QbG90KG9iaiwgZ3JvdXAuYnkgPSAic2V1cmF0X2NsdXN0ZXJzIiwgbGFiZWwgPSBUKSArIHRoZW1lX3ZvaWQoKSArIE5vTGVnZW5kKCkpCmZvciAoaSBpbiB2YXJzKSB7CiAgcGxbW2ldXSA8LSBGZWF0dXJlUGxvdChvYmosIGZlYXR1cmVzID0gaSwgb3JkZXIgPSBUKSArIHRoZW1lX3ZvaWQoKSArIE5vTGVnZW5kKCkKfQp3cmFwX3Bsb3RzKHBsKQoKCmBgYAoKIyMgLiBFeHBsb3JpbmcgdGhlIGRhdGEtMgpgYGB7ciwgZmlnLmhlaWdodD04LCBmaWcud2lkdGg9MTB9CgojIExvYWQgbmVjZXNzYXJ5IGxpYnJhcmllcwpsaWJyYXJ5KFNldXJhdCkKbGlicmFyeShwYXRjaHdvcmspCmxpYnJhcnkoZ2x1ZSkKCiMgRGVmaW5lIG1hcmtlciBncm91cHMKbWFya2VyX2dyb3VwcyA8LSBsaXN0KAogICJDRDQgVGV4IChFeGhhdXN0ZWQpIiA9IGMoIlRPWCIsICJMQUczIiwgIkNUTEE0IiwgIlRJR0lUIiksCiAgIkNENCBUcmVnIiA9IGMoIkZPWFAzIiwgIklMMlJBIiwgIkNUTEE0IiwgIklLWkYyIiwgIlRJR0lUIiksCiAgIkNENCBUY20gKENlbnRyYWwgTWVtb3J5KSIgPSBjKCJDQ1I3IiwgIlNFTEwiLCAiSUw3UiIsICJUQ0Y3IiksCiAgIkNENCBUbiAoTmFpdmUpIiA9IGMoIkNDUjciLCAiU0VMTCIsICJJTDdSIiwgIlRDRjciLCAiTEVGMSIpLAogICJDRDQgVGVtIChFZmZlY3RvciBNZW1vcnkpIiA9IGMoIkdaTUIiLCAiUFJGMSIsICJJRk5HIiwgIktMUkcxIiksCiAgIkNENCBUcm0gKFRpc3N1ZSBSZXNpZGVudCkiID0gYygiQ0Q2OSIsICJDWENSNiIpLAogICJDRDQgVGMgKEN5dG90b3hpYykiID0gYygiUFJGMSIsICJHWk1CIiwgIk5LRzciLCAiR05MWSIpLAogICJDRDQgVGlzZyAoSUZOIFNpZ25hdHVyZSkiID0gYygiSVNHMTUiLCAiSUZJNiIsICJJRklUMyIsICJNWDEiKSwKICAiQ0Q0IFByb2xpZmVyYXRpb24iID0gYygiTUtJNjciLCAiVE9QMkEiKSwKICAiQ0Q0IFRoMTciID0gYygiU1RBVDMiLCAiQUhSIiwgIkNDUjYiLCAiQkFURiIpLAogICJDRDQgVGVtcmEgKEVmZmVjdG9yIE1lbW9yeSBSQSspIiA9IGMoIlBUUFJDIiwgIkdaTUIiKSwKICAiQ0Q0IFRmaCAoRm9sbGljdWxhciBIZWxwZXIpIiA9IGMoIkJDTDYiLCAiSUNPUyIpLAogICJDRDQgVHN0ciAoU3RyZXNzKSIgPSBjKCJIU1BBMUEiLCAiQVRGMyIpLAogICJDRDQgQWN0aXZhdGVkIiA9IGMoIklMMlJBIiwgIkNENjkiLCAiSExBLURSQSIpCikKCiMgT1BUSU9OQUw6IFVuY29tbWVudCB0aGlzIHRvIHNhdmUgYWxsIHBsb3RzIGluIGEgc2luZ2xlIFBERgojIHBkZigiQ0Q0X01hcmtlckdyb3Vwc19GZWF0dXJlUGxvdHMucGRmIiwgd2lkdGggPSAxMiwgaGVpZ2h0ID0gMTApCgojIE1haW4gcGxvdHRpbmcgbG9vcApmb3IgKGdyb3VwX25hbWUgaW4gbmFtZXMobWFya2VyX2dyb3VwcykpIHsKICBnZW5lcyA8LSB1bmlxdWUobWFya2VyX2dyb3Vwc1tbZ3JvdXBfbmFtZV1dKQogIG1lc3NhZ2UoZ2x1ZSgiUGxvdHRpbmc6IHtncm91cF9uYW1lfSIpKQoKICAjIENsZWFuZXIgdGl0bGVzIGFuZCBiZXR0ZXIgdGhlbWUKICBwbCA8LSBsYXBwbHkoZ2VuZXMsIGZ1bmN0aW9uKGdlbmUpIHsKICAgIEZlYXR1cmVQbG90KG9iaiwgZmVhdHVyZXMgPSBnZW5lLCBvcmRlciA9IFRSVUUpICsKICAgICAgZ2d0aXRsZShnZW5lKSArICAjIHNob3J0ZXIgdGl0bGUKICAgICAgdGhlbWVfbWluaW1hbChiYXNlX3NpemUgPSAxMCkgKyAgIyB1c2UgbWluaW1hbCBmb3Igc3BhY2luZwogICAgICBOb0xlZ2VuZCgpCiAgfSkKCiAgIyBDb21iaW5lIHBsb3RzCiAgY29tYmluZWRfcGxvdCA8LSB3cmFwX3Bsb3RzKHBsLCBuY29sID0gMikgKyAgIyBmZXdlciBjb2x1bW5zID0gbW9yZSBzcGFjZQogICAgICAgICAgICAgICAgICAgcGxvdF9hbm5vdGF0aW9uKHRpdGxlID0gZ3JvdXBfbmFtZSkKCiAgcHJpbnQoY29tYmluZWRfcGxvdCkKfQojIE9QVElPTkFMOiBVbmNvbW1lbnQgaWYgdXNpbmcgcGRmKCkKIyBkZXYub2ZmKCkKCgoKCmBgYAoKIyMgLiBFeHBsb3JpbmcgdGhlIGRhdGEtMwpgYGB7ciwgZmlnLmhlaWdodD04LCBmaWcud2lkdGg9MTB9CgojIFJlcXVpcmVkIG1hcmtlcnMKcHJvZ2VuaXRvcl9tYXJrZXJzIDwtIGMoIkNEMzQiLCAiS0lUIiwgIkdBVEEyIiwgIk1LSTY3IiwgIlBST00xIiwgIkZMVDMiKQoKIyBGZWF0dXJlIHBsb3RzIGZvciBlYWNoIG1hcmtlcgpGZWF0dXJlUGxvdChvYmosIGZlYXR1cmVzID0gcHJvZ2VuaXRvcl9tYXJrZXJzLCBvcmRlciA9IFRSVUUsIG5jb2wgPSAzKQoKCgoKYGBgCgojIDYuIGNvbXB1dGUgdGhlIGxpbmVhZ2VzIG9uIHRoZXNlIGRhdGFzZXQKYGBge3J9CnNldC5zZWVkKDEpCgojICMgRGVmaW5lIGxpbmVhZ2UgZW5kcwpFTkRTIDwtIGMoIjEiLCAiNCIsICI4IiAsICIwIiwiMTMiKQoKc2V0LnNlZWQoMSkKbGluZWFnZXMgPC0gYXMuU2xpbmdzaG90RGF0YVNldChnZXRMaW5lYWdlcygKICBkYXRhICAgICAgICAgICA9IG9iakByZWR1Y3Rpb25zJHVtYXBAY2VsbC5lbWJlZGRpbmdzLAogIGNsdXN0ZXJMYWJlbHMgID0gb2JqJHNldXJhdF9jbHVzdGVycywKICBkaXN0Lm1ldGhvZCAgICA9ICJtbm4iLCAjIEl0IGNhbiBiZTogInNpbXBsZSIsICJzY2FsZWQuZnVsbCIsICJzY2FsZWQuZGlhZyIsICJzbGluZ3Nob3QiIG9yICJtbm4iCiAgZW5kLmNsdXMgICAgICAgPSBFTkRTLCAjIFlvdSBjYW4gYWxzbyBkZWZpbmUgdGhlIEVORFMhCiAgc3RhcnQuY2x1cyAgICAgPSAiMyIKKSkgIyBkZWZpbmUgd2hlcmUgdG8gU1RBUlQgdGhlIHRyYWplY3RvcmllcwoKCiMgSUYgTkVFREVELCBPTkUgQ0FOIEFMU08gTUFOVUxBTExZIEVESVQgVEhFIExJTkVBR0VTLCBGT1IgRVhBTVBMRToKIyBzZWwgPC0gc2FwcGx5KCBsaW5lYWdlc0BsaW5lYWdlcywgZnVuY3Rpb24oeCl7cmV2KHgpWzFdfSApICVpbiUgRU5EUwojIGxpbmVhZ2VzQGxpbmVhZ2VzIDwtIGxpbmVhZ2VzQGxpbmVhZ2VzWyBzZWwgXQojIG5hbWVzKGxpbmVhZ2VzQGxpbmVhZ2VzKSA8LSBwYXN0ZTAoIkxpbmVhZ2UiLDE6bGVuZ3RoKGxpbmVhZ2VzQGxpbmVhZ2VzKSkKIyBsaW5lYWdlcwoKCiMgQ2hhbmdlIHRoZSByZWR1Y3Rpb24gdG8gb3VyICJmaXhlZCIgVU1BUDJkIChGT1IgVklTVUFMSVNBVElPTiBPTkxZKQpsaW5lYWdlc0ByZWR1Y2VkRGltIDwtIG9iakByZWR1Y3Rpb25zJHVtYXBAY2VsbC5lbWJlZGRpbmdzCgp7CiAgcGxvdChvYmpAcmVkdWN0aW9ucyR1bWFwQGNlbGwuZW1iZWRkaW5ncywgY29sID0gcGFsW29iaiRzZXVyYXRfY2x1c3RlcnNdLCBjZXggPSAuNSwgcGNoID0gMTYpCiAgbGluZXMobGluZWFnZXMsIGx3ZCA9IDEsIGNvbCA9ICJibGFjayIsIGNleCA9IDIpCiAgdGV4dChjZW50cm9pZHMyZCwgbGFiZWxzID0gcm93bmFtZXMoY2VudHJvaWRzMmQpLCBjZXggPSAwLjgsIGZvbnQgPSAyLCBjb2wgPSAid2hpdGUiKQp9CgpgYGAKCiMjICBEZWZpbmluZyBQcmluY2lwYWwgQ3VydmVzCmBgYHtyfQoKIyBEZWZpbmUgY3VydmVzCmN1cnZlcyA8LSBhcy5TbGluZ3Nob3REYXRhU2V0KGdldEN1cnZlcygKICBkYXRhICAgICAgICAgID0gbGluZWFnZXMsCiAgdGhyZXNoICAgICAgICA9IDFlLTEsCiAgc3RyZXRjaCAgICAgICA9IDFlLTEsCiAgYWxsb3cuYnJlYWtzICA9IEYsCiAgYXBwcm94X3BvaW50cyA9IDEwMDAKKSkKCmN1cnZlcwoKYGBgCgojIyAgUGxvdApgYGB7cn0KCiMgUGxvdHMKewogIHBsb3Qob2JqQHJlZHVjdGlvbnMkdW1hcEBjZWxsLmVtYmVkZGluZ3MsIGNvbCA9IHBhbFtvYmokc2V1cmF0X2NsdXN0ZXJzXSwgcGNoID0gMTYpCiAgbGluZXMoY3VydmVzLCBsd2QgPSAyLCBjb2wgPSAiYmxhY2siKQogIHRleHQoY2VudHJvaWRzMmQsIGxhYmVscyA9IGxldmVscyhvYmokc2V1cmF0X2NsdXN0ZXJzKSwgY2V4ID0gMSwgZm9udCA9IDIpCn0KYGBgCgoKCiMjICBjb21wdXRlIHRoZSBkaWZmZXJlbnRpYXRpb24gcHNldWRvdGltZQpgYGB7cn0KCnBzZXVkb3RpbWUgPC0gc2xpbmdQc2V1ZG90aW1lKGN1cnZlcywgbmEgPSBGQUxTRSkKY2VsbFdlaWdodHMgPC0gc2xpbmdDdXJ2ZVdlaWdodHMoY3VydmVzKQoKeCA8LSByb3dNZWFucyhwc2V1ZG90aW1lKQp4IDwtIHggLyBtYXgoeCkKbyA8LSBvcmRlcih4KQoKewogIHBsb3Qob2JqQHJlZHVjdGlvbnMkdW1hcEBjZWxsLmVtYmVkZGluZ3NbbywgXSwKICAgIG1haW4gPSBwYXN0ZTAoInBzZXVkb3RpbWUiKSwgcGNoID0gMTYsIGNleCA9IDAuNCwgYXhlcyA9IEYsIHhsYWIgPSAiIiwgeWxhYiA9ICIiLAogICAgY29sID0gY29sb3JSYW1wUGFsZXR0ZShjKCJncmV5NzAiLCAib3JhbmdlMyIsICJmaXJlYnJpY2siLCAicHVycGxlNCIpKSg5OSlbeFtvXSAqIDk4ICsgMV0KICApCiAgcG9pbnRzKGNlbnRyb2lkczJkLCBjZXggPSAyLjUsIHBjaCA9IDE2LCBjb2wgPSAiI0ZGRkZGRjk5IikKICB0ZXh0KGNlbnRyb2lkczJkLCBsYWJlbHMgPSBsZXZlbHMob2JqJHNldXJhdF9jbHVzdGVycyksIGNleCA9IDEsIGZvbnQgPSAyKQp9CmBgYAojIDcuIEZpbmRpbmcgZGlmZmVyZW50aWFsbHkgZXhwcmVzc2VkIGdlbmVzCmBgYHtyfQoKIyDwn5S0IENIQU5HRTogVXNlIGFsbCBjZWxscwpzZWxfY2VsbHMgPC0gY29sbmFtZXMob2JqKQoKIyDwn5S0IENIQU5HRTogVXNlIGV4aXN0aW5nIEhWR3MKaHZnX2dlbmVzIDwtIFZhcmlhYmxlRmVhdHVyZXMob2JqKQoKbGlicmFyeShCaW9jUGFyYWxsZWwpCiMgVXNlIHJhdyBjb3VudHMgKG5lZWRlZCBmb3IgdHJhZGVTZXEgZml0R0FNKQpjb3VudHNfbWF0IDwtIEdldEFzc2F5RGF0YShvYmosIGFzc2F5ID0gIlJOQSIsIHNsb3QgPSAiY291bnRzIikKCgpwc2V1ZG90aW1lX3NlbCA8LSBwc2V1ZG90aW1lW3NlbF9jZWxscywgLCBkcm9wID0gRkFMU0VdCgphbGwoc2VsX2NlbGxzICVpbiUgcm93bmFtZXMocHNldWRvdGltZSkpICAgICMgc2hvdWxkIGJlIFRSVUUKYWxsKHNlbF9jZWxscyAlaW4lIHJvd25hbWVzKGNlbGxXZWlnaHRzKSkgICMgc2hvdWxkIGJlIFRSVUUKCgpzY2VHQU0gPC0gZml0R0FNKAogIGNvdW50cyA9IGRyb3AwKGNvdW50c19tYXRbaHZnX2dlbmVzLCBzZWxfY2VsbHNdKSwKICBwc2V1ZG90aW1lID0gcHNldWRvdGltZV9zZWwsCiAgY2VsbFdlaWdodHMgPSBjZWxsV2VpZ2h0c1tzZWxfY2VsbHMsICwgZHJvcCA9IEZBTFNFXSwKICBua25vdHMgPSA3LAogIHZlcmJvc2UgPSBUUlVFLAogIHBhcmFsbGVsID0gRkFMU0UsICAjIHN0YXJ0IHNlcmlhbGx5IHRvIGF2b2lkIG1lbW9yeSBpc3N1ZXMKICBzY2UgPSBUUlVFCikKCgojIFZpc3VhbGl6ZSBnZW5lIGNvdW50cyBwZXIgbGluZWFnZQpwbG90R2VuZUNvdW50KGN1cnZlcywgY2x1c3RlcnMgPSBvYmokc2V1cmF0X2NsdXN0ZXJzLCBtb2RlbHMgPSBzY2VHQU0pCgojIFBsb3QgbGluZWFnZXMKbGMgPC0gc2FwcGx5KGxpbmVhZ2VzQGxpbmVhZ2VzLCBmdW5jdGlvbih4KSB7cmV2KHgpWzFdfSkKbmFtZXMobGMpIDwtIGdzdWIoIkxpbmVhZ2UiLCAiTCIsIG5hbWVzKGxjKSkKbGMuaWR4ID0gbWF0Y2gobGMsIGxldmVscyhvYmokc2V1cmF0X2NsdXN0ZXJzKSkKCnBsb3Qob2JqQHJlZHVjdGlvbnMkdW1hcEBjZWxsLmVtYmVkZGluZ3MsIGNvbCA9IHBhbFtvYmokc2V1cmF0X2NsdXN0ZXJzXSwgcGNoID0gMTYpCmxpbmVzKGN1cnZlcywgbHdkID0gMiwgY29sID0gImJsYWNrIikKcG9pbnRzKGNlbnRyb2lkczJkW2xjLmlkeCwgXSwgY29sID0gImJsYWNrIiwgcGNoID0gMTYsIGNleCA9IDQpCnRleHQoY2VudHJvaWRzMmRbbGMuaWR4LCBdLCBsYWJlbHMgPSBuYW1lcyhsYyksIGNleCA9IDEsIGZvbnQgPSAyLCBjb2wgPSAid2hpdGUiKQoKYGBgCgoKCgoKCgoKIyMgR2VuZXMgdGhhdCBjaGFuZ2Ugd2l0aCBwc2V1ZG90aW1lCmBgYHtyfQpnYygpCgpzZXQuc2VlZCg4KQpyZXMgPC0gbmEub21pdChhc3NvY2lhdGlvblRlc3Qoc2NlR0FNLCBjb250cmFzdFR5cGUgPSAiY29uc2VjdXRpdmUiKSkKcmVzIDwtIHJlc1tyZXMkcHZhbHVlIDwgMWUtMywgXQpyZXMgPC0gcmVzW3JlcyR3YWxkU3RhdCA+IG1lYW4ocmVzJHdhbGRTdGF0KSwgXQpyZXMgPC0gcmVzW29yZGVyKHJlcyR3YWxkU3RhdCwgZGVjcmVhc2luZyA9IFQpLCBdCnJlc1sxOjEwLCBdCgpgYGAKCgojIyBXZSBjYW4gcGxvdCB0aGVpciBleHByZXNzaW9uCmBgYHtyfQoKcGFyKG1mcm93ID0gYyg0LCA0KSwgbWFyID0gYyguMSwgLjEsIDIsIDEpKQp7CiAgcGxvdChvYmpAcmVkdWN0aW9ucyR1bWFwQGNlbGwuZW1iZWRkaW5ncywgY29sID0gcGFsW29iaiRzZXVyYXRfY2x1c3RlcnNdLCBjZXggPSAuNSwgcGNoID0gMTYsIGF4ZXMgPSBGLCB4bGFiID0gIiIsIHlsYWIgPSAiIikKICBsaW5lcyhjdXJ2ZXMsIGx3ZCA9IDIsIGNvbCA9ICJibGFjayIpCiAgcG9pbnRzKGNlbnRyb2lkczJkW2xjLmlkeCwgXSwgY29sID0gImJsYWNrIiwgcGNoID0gMTUsIGNleCA9IDMsIHhwZCA9IFQpCiAgdGV4dChjZW50cm9pZHMyZFtsYy5pZHgsIF0sIGxhYmVscyA9IG5hbWVzKGxjKSwgY2V4ID0gMSwgZm9udCA9IDIsIGNvbCA9ICJ3aGl0ZSIsIHhwZCA9IFQpCn0KCnZhcnMgPC0gcm93bmFtZXMocmVzWzE6MTUsIF0pCnZhcnMgPC0gbmEub21pdCh2YXJzW3ZhcnMgIT0gIk5BIl0pCgpmb3IgKGkgaW4gdmFycykgewogIHggPC0gZHJvcDAob2JqQGFzc2F5cyRTQ1RAZGF0YSlbaSwgXQogIHggPC0gKHggLSBtaW4oeCkpIC8gKG1heCh4KSAtIG1pbih4KSkKICBvIDwtIG9yZGVyKHgpCiAgcGxvdChvYmpAcmVkdWN0aW9ucyR1bWFwQGNlbGwuZW1iZWRkaW5nc1tvLCBdLAogICAgbWFpbiA9IHBhc3RlMChpKSwgcGNoID0gMTYsIGNleCA9IDAuNSwgYXhlcyA9IEYsIHhsYWIgPSAiIiwgeWxhYiA9ICIiLAogICAgY29sID0gY29sb3JSYW1wUGFsZXR0ZShjKCJsaWdodGdyYXkiLCAiZ3JleTYwIiwgIm5hdnkiKSkoOTkpW3hbb10gKiA5OCArIDFdCiAgKQp9CgpgYGAKCgoKIyMgR2VuZXMgdGhhdCBjaGFuZ2UgYmV0d2VlbiB0d28gcHNldWRvdGltZSBwb2ludHMKYGBge3J9CnJlcyA8LSBuYS5vbWl0KHN0YXJ0VnNFbmRUZXN0KHNjZUdBTSwgcHNldWRvdGltZVZhbHVlcyA9IGMoMCwgMSkpKQpyZXMgPC0gcmVzW3JlcyRwdmFsdWUgPCAxZS0zLCBdCnJlcyA8LSByZXNbcmVzJHdhbGRTdGF0ID4gbWVhbihyZXMkd2FsZFN0YXQpLCBdCnJlcyA8LSByZXNbb3JkZXIocmVzJHdhbGRTdGF0LCBkZWNyZWFzaW5nID0gVCksIF0KcmVzWzE6MTAsIDE6Nl0KYGBgCiMjIGlkZW50aWZ5IHdoaWNoIGdlbmVzIGdvIHVwIG9yIGRvd24uIExldOKAmXMgY2hlY2sgbGluZWFnZSAxOgpgYGB7cn0KIyBHZXQgdGhlIHRvcCBVUCBhbmQgRG93biByZWd1bGF0ZWQgaW4gbGluZWFnZSAxCnJlc19saW4xIDwtIHNvcnQoc2V0TmFtZXMocmVzJGxvZ0ZDbGluZWFnZTEsIHJvd25hbWVzKHJlcykpKQp2YXJzIDwtIG5hbWVzKGMocmV2KHJlc19saW4xKVsxOjddLCByZXNfbGluMVsxOjhdKSkKdmFycyA8LSBuYS5vbWl0KHZhcnNbdmFycyAhPSAiTkEiXSkKCnBhcihtZnJvdyA9IGMoNCwgNCksIG1hciA9IGMoLjEsIC4xLCAyLCAxKSkKCnsKICBwbG90KG9iakByZWR1Y3Rpb25zJHVtYXBAY2VsbC5lbWJlZGRpbmdzLCBjb2wgPSBwYWxbb2JqJHNldXJhdF9jbHVzdGVyc10sIGNleCA9IC41LCBwY2ggPSAxNiwgYXhlcyA9IEYsIHhsYWIgPSAiIiwgeWxhYiA9ICIiKQogIGxpbmVzKGN1cnZlcywgbHdkID0gMiwgY29sID0gImJsYWNrIikKICBwb2ludHMoY2VudHJvaWRzMmRbbGMuaWR4LCBdLCBjb2wgPSAiYmxhY2siLCBwY2ggPSAxNSwgY2V4ID0gMywgeHBkID0gVCkKICB0ZXh0KGNlbnRyb2lkczJkW2xjLmlkeCwgXSwgbGFiZWxzID0gbmFtZXMobGMpLCBjZXggPSAxLCBmb250ID0gMiwgY29sID0gIndoaXRlIiwgeHBkID0gVCkKfQoKZm9yIChpIGluIHZhcnMpIHsKICB4IDwtIGRyb3AwKG9iakBhc3NheXMkU0NUQGRhdGEpW2ksIF0KICB4IDwtICh4IC0gbWluKHgpKSAvIChtYXgoeCkgLSBtaW4oeCkpCiAgbyA8LSBvcmRlcih4KQogIHBsb3Qob2JqQHJlZHVjdGlvbnMkdW1hcEBjZWxsLmVtYmVkZGluZ3NbbywgXSwKICAgIG1haW4gPSBwYXN0ZTAoaSksIHBjaCA9IDE2LCBjZXggPSAwLjUsIGF4ZXMgPSBGLCB4bGFiID0gIiIsIHlsYWIgPSAiIiwKICAgIGNvbCA9IGNvbG9yUmFtcFBhbGV0dGUoYygibGlnaHRncmF5IiwgImdyZXk2MCIsICJuYXZ5IikpKDk5KVt4W29dICogOTggKyAxXQogICkKfQpgYGAKCiMjIEdlbmVzIHRoYXQgYXJlIGRpZmZlcmVudCBiZXR3ZWVuIGxpbmVhZ2VzCmBgYHtyfQpyZXMgPC0gbmEub21pdChkaWZmRW5kVGVzdChzY2VHQU0pKQpyZXMgPC0gcmVzW3JlcyRwdmFsdWUgPCAxZS0zLCBdCnJlcyA8LSByZXNbcmVzJHdhbGRTdGF0ID4gbWVhbihyZXMkd2FsZFN0YXQpLCBdCnJlcyA8LSByZXNbb3JkZXIocmVzJHdhbGRTdGF0LCBkZWNyZWFzaW5nID0gVCksIF0KcmVzWzE6MTAsIF0KCmBgYAoKIyMgcGFpcndpc2UgY29tcGFyaXNvbiBiZXR3ZWVuIGVhY2ggbGluZWFnZS4gTGV04oCZcyBjaGVjayBsaW5lYWdlIDEgdnMgbGluZWFnZSAyOgpgYGB7cn0KIyBHZXQgdGhlIHRvcCBVUCBhbmQgRG93biByZWd1bGF0ZWQgaW4gbGluZWFnZSAxIHZzIDIKcmVzX2xpbjFfMiA8LSBzb3J0KHNldE5hbWVzKHJlcyRsb2dGQzFfMiwgcm93bmFtZXMocmVzKSkpCnZhcnMgPC0gbmFtZXMoYyhyZXYocmVzX2xpbjFfMilbMTo3XSwgcmVzX2xpbjFfMlsxOjhdKSkKdmFycyA8LSBuYS5vbWl0KHZhcnNbdmFycyAhPSAiTkEiXSkKCnBhcihtZnJvdyA9IGMoNCwgNCksIG1hciA9IGMoLjEsIC4xLCAyLCAxKSkKewogIHBsb3Qob2JqQHJlZHVjdGlvbnMkdW1hcEBjZWxsLmVtYmVkZGluZ3MsIGNvbCA9IHBhbFtvYmokc2V1cmF0X2NsdXN0ZXJzXSwgY2V4ID0gLjUsIHBjaCA9IDE2LCBheGVzID0gRiwgeGxhYiA9ICIiLCB5bGFiID0gIiIpCiAgbGluZXMoY3VydmVzLCBsd2QgPSAyLCBjb2wgPSAiYmxhY2siKQogIHBvaW50cyhjZW50cm9pZHMyZFtsYy5pZHgsIF0sIGNvbCA9ICJibGFjayIsIHBjaCA9IDE1LCBjZXggPSAzLCB4cGQgPSBUKQogIHRleHQoY2VudHJvaWRzMmRbbGMuaWR4LCBdLCBsYWJlbHMgPSBuYW1lcyhsYyksIGNleCA9IDEsIGZvbnQgPSAyLCBjb2wgPSAid2hpdGUiLCB4cGQgPSBUKQp9Cgpmb3IgKGkgaW4gdmFycykgewogIHggPC0gZHJvcDAob2JqQGFzc2F5cyRTQ1RAZGF0YSlbaSwgXQogIHggPC0gKHggLSBtaW4oeCkpIC8gKG1heCh4KSAtIG1pbih4KSkKICBvIDwtIG9yZGVyKHgpCiAgcGxvdChvYmpAcmVkdWN0aW9ucyR1bWFwQGNlbGwuZW1iZWRkaW5nc1tvLCBdLAogICAgbWFpbiA9IHBhc3RlMChpKSwgcGNoID0gMTYsIGNleCA9IDAuNSwgYXhlcyA9IEYsIHhsYWIgPSAiIiwgeWxhYiA9ICIiLAogICAgY29sID0gY29sb3JSYW1wUGFsZXR0ZShjKCJsaWdodGdyYXkiLCAiZ3JleTYwIiwgIm5hdnkiKSkoOTkpW3hbb10gKiA5OCArIDFdCiAgKQp9CmBgYAoKCiMjIHNhdmUgc2NlR0FNIGFmdGVyIGZpdHRpbmc6CmBgYHtyfQpzYXZlUkRTKHNjZUdBTSwgInNjZUdBTV9hbGxIVkdzLnJkcyIpCmBgYAoKIyMgc2F2ZSBzY2VHQU0gYWZ0ZXIgZml0dGluZzoKYGBge3J9CnNhdmVSRFMob2JqLCAiQWxsX3NhbXBsZXNfTWVyZ2VkX2FmdGVyX1NsaW5nc2hvdC5yZHMiKQoKYGBgCgo=