1. load libraries

2. Nice function to easily draw a graph:

3. Reading data

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

# 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)

📌 Step 1: Load PAGA embedding and match cells

📌 Step 2: Add PAGA UMAP as a new reduction in Seurat

📌 Step 3: Add Leiden cluster info to metadata

4. Trajectory inference using Slingshot

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


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

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


table(obj$leiden)

   0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17 
7140 5705 5289 4709 4389 3835 3702 3308 2904 1944 1497 1268 1262  956  623  500  247   27 

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 = "leiden", label = T) + theme_void() + NoLegend())
for (i in vars) {
  pl[[i]] <- FeaturePlot(obj, features = i, order = T) + theme_void() + NoLegend()
}
Warning: The `slot` argument of `FetchData()` is deprecated as of SeuratObject 5.0.0.
Please use the `layer` argument instead.
wrap_plots(pl)

NA
NA

6. compute the lineages on these dataset

# Define lineage ends
ENDS <- c("2", "6", "8")

set.seed(1)
lineages <- as.SlingshotDataSet(getLineages(
  data           = obj@reductions$paga@cell.embeddings,
  clusterLabels  = obj$leiden,
  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
Warning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observationsWarning: 'k' capped at the number of observations
# 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$paga@cell.embeddings

{
  plot(obj@reductions$paga@cell.embeddings, col = pal[obj$leiden], 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 = 100
))


# Plots
{
  plot(obj@reductions$paga@cell.embeddings, col = pal[obj$leiden], pch = 16)
  lines(curves, lwd = 2, col = "black")
  text(centroids2d, labels = levels(obj$leiden), 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$paga@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$leiden), cex = 1, font = 2)
}

7. Finding differentially expressed genes


sel_cells <- split(colnames(obj@assays$SCT@data), obj$leiden)
sel_cells <- unlist(lapply(sel_cells, function(x) {
  set.seed(1)
  return(sample(x, 20))
}))

gv <- as.data.frame(na.omit(scran::modelGeneVar(obj@assays$SCT@data[, sel_cells])))
Warning: collapsing to unique 'x' values
gv <- gv[order(gv$bio, decreasing = T), ]
sel_genes <- sort(rownames(gv)[1:500])

path_file <- "/home/bioinfo/data/trajectory/seurat_scegam.rds"

# fetch_data is defined at the top of this document
sceGAM <- fitGAM(
  counts = drop0(obj@assays$SCT@data[sel_genes, sel_cells]),
  pseudotime = pseudotime[sel_cells, ],
  cellWeights = cellWeights[sel_cells, ],
  nknots = 5, verbose = TRUE, parallel = TRUE, sce = TRUE,
  BPPARAM = BiocParallel::MulticoreParam()
)
Warning: Impossible to place a knot at all endpoints.Increase the number of knots to avoid this issue.

  |                                                                                                  
  |                                                                                            |   0%
  |                                                                                                  
  |==                                                                                          |   3%
  |                                                                                                  
  |=====                                                                                       |   5%
  |                                                                                                  
  |=======                                                                                     |   8%
  |                                                                                                  
  |==========                                                                                  |  10%
  |                                                                                                  
  |============                                                                                |  13%
  |                                                                                                  
  |==============                                                                              |  16%
  |                                                                                                  
  |=================                                                                           |  18%
  |                                                                                                  
  |===================                                                                         |  21%
  |                                                                                                  
  |======================                                                                      |  23%
  |                                                                                                  
  |========================                                                                    |  26%
  |                                                                                                  
  |==========================                                                                  |  29%
  |                                                                                                  
  |=============================                                                               |  31%
  |                                                                                                  
  |===============================                                                             |  34%
  |                                                                                                  
  |=================================                                                           |  36%
  |                                                                                                  
  |====================================                                                        |  39%
  |                                                                                                  
  |======================================                                                      |  42%
  |                                                                                                  
  |=========================================                                                   |  44%
  |                                                                                                  
  |===========================================                                                 |  47%
  |                                                                                                  
  |=============================================                                               |  49%
  |                                                                                                  
  |================================================                                            |  52%
  |                                                                                                  
  |==================================================                                          |  55%
  |                                                                                                  
  |=====================================================                                       |  57%
  |                                                                                                  
  |=======================================================                                     |  60%
  |                                                                                                  
  |=========================================================                                   |  62%
  |                                                                                                  
  |============================================================                                |  65%
  |                                                                                                  
  |==============================================================                              |  68%
  |                                                                                                  
  |=================================================================                           |  70%
  |                                                                                                  
  |==================================================================                          |  71%
  |                                                                                                  
  |====================================================================                        |  74%
  |                                                                                                  
  |======================================================================                      |  77%
  |                                                                                                  
  |=========================================================================                   |  79%
  |                                                                                                  
  |===========================================================================                 |  82%
  |                                                                                                  
  |==============================================================================              |  84%
  |                                                                                                  
  |================================================================================            |  87%
  |                                                                                                  
  |==================================================================================          |  90%
  |                                                                                                  
  |=====================================================================================       |  92%
  |                                                                                                  
  |=======================================================================================     |  95%
  |                                                                                                  
  |==========================================================================================  |  97%
  |                                                                                                  
  |============================================================================================| 100%
plotGeneCount(curves, clusters = obj$leiden, models = sceGAM)



lineages
class: SlingshotDataSet 

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

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

{
  plot(obj@reductions$paga@cell.embeddings, col = pal[obj$leiden], 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")
}

NA
NA
NA
NA

Genes that change with pseudotime


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$paga@cell.embeddings, col = pal[obj$leiden], 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$paga@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]
  )
}
Error in .subscript.2ary(x, i, , drop = TRUE) : subscript out of bounds

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$paga@cell.embeddings, col = pal[obj$leiden], 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$paga@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$paga@cell.embeddings, col = pal[obj$leiden], 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$paga@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]
  )
}

LS0tCnRpdGxlOiAiVHJhamVjdG9yeSBpbmZlcmVuY2UgdXNpbmcgU2xpbmdzaG90IHVzaW5nIFBBR0EgZW1iZWRkaW5ncyIKYXV0aG9yOiBOYXNpciBNYWhtb29kIEFiYmFzaQpkYXRlOiAiYHIgU3lzLkRhdGUoKWAiCm91dHB1dDoKICAjcm1kZm9ybWF0czo6cmVhZHRoZWRvd24KICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIHRvY19jb2xsYXBzZWQ6IHRydWUKLS0tCgojIDEuIGxvYWQgbGlicmFyaWVzCmBgYHtyLCBpbmNsdWRlPUZBTFNFfQpzdXBwcmVzc1BhY2thZ2VTdGFydHVwTWVzc2FnZXMoewogIGxpYnJhcnkoU2V1cmF0KQogIGxpYnJhcnkocGxvdGx5KQogIG9wdGlvbnMocmdsLnByaW50Umdsd2lkZ2V0ID0gVFJVRSkKICBsaWJyYXJ5KE1hdHJpeCkKICBsaWJyYXJ5KHNwYXJzZU1hdHJpeFN0YXRzKQogIGxpYnJhcnkoc2xpbmdzaG90KQogIGxpYnJhcnkodHJhZGVTZXEpCiAgbGlicmFyeShwYXRjaHdvcmspCn0pCgoKYGBgCgojIDIuIE5pY2UgZnVuY3Rpb24gdG8gZWFzaWx5IGRyYXcgYSBncmFwaDoKYGBge3IsIGluY2x1ZGU9RkFMU0V9CiMgQWRkIGdyYXBoIHRvIHRoZSBiYXNlIFIgZ3JhcGhpY3MgcGxvdApkcmF3X2dyYXBoIDwtIGZ1bmN0aW9uKGxheW91dCwgZ3JhcGgsIGx3ZCA9IDAuMiwgY29sID0gImdyZXkiKSB7CiAgcmVzIDwtIHJlcCh4ID0gMToobGVuZ3RoKGdyYXBoQHApIC0gMSksIHRpbWVzID0gKGdyYXBoQHBbLTFdIC0gZ3JhcGhAcFstbGVuZ3RoKGdyYXBoQHApXSkpCiAgc2VnbWVudHMoCiAgICB4MCA9IGxheW91dFtncmFwaEBpICsgMSwgMV0sIHgxID0gbGF5b3V0W3JlcywgMV0sCiAgICB5MCA9IGxheW91dFtncmFwaEBpICsgMSwgMl0sIHkxID0gbGF5b3V0W3JlcywgMl0sIGx3ZCA9IGx3ZCwgY29sID0gY29sCiAgKQp9CmBgYAoKIyAzLiBSZWFkaW5nIGRhdGEKYGBge3J9CkFsbF9zYW1wbGVzX01lcmdlZCA8LSByZWFkUkRTKCIuLi8uLi8wLVNldXJhdF9SRFNfT0JKRUNUX0ZJTkFML0FsbF9zYW1wbGVzX01lcmdlZF93aXRoX1NUQ0FUX2FuZF9yZW5hbWVkX0ZJTkFMLnJkcyIpCgojIERlZmluZSBzb21lIGNvbG9yIHBhbGV0dGUKcGFsIDwtIGMoc2NhbGVzOjpodWVfcGFsKCkoOCksIFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbCg5LCAiU2V0MSIpLCBSQ29sb3JCcmV3ZXI6OmJyZXdlci5wYWwoOCwgIlNldDIiKSkKc2V0LnNlZWQoMSkKcGFsIDwtIHJlcChzYW1wbGUocGFsLCBsZW5ndGgocGFsKSksIDIwMCkKCmBgYAoKIyMg8J+TjCBTdGVwIDE6IExvYWQgUEFHQSBlbWJlZGRpbmcgYW5kIG1hdGNoIGNlbGxzCmBgYHtyLCBpbmNsdWRlPUZBTFNFfQojIFJlYWQgZW1iZWRkaW5nIENTViBmaWxlCmVtYmVkZGluZ19kZiA8LSByZWFkLmNzdigicGFnYV9lbWJlZGRpbmdfZm9yX3NldXJhdF9zbGluZ3Nob3QuY3N2IikKCiMgU2V0IHJvd25hbWVzIHRvIGJhcmNvZGUgZm9yIG1hdGNoaW5nCnJvd25hbWVzKGVtYmVkZGluZ19kZikgPC0gZW1iZWRkaW5nX2RmJGJhcmNvZGUKCiMgU3Vic2V0IGVtYmVkZGluZyB0byBvbmx5IGNlbGxzIHByZXNlbnQgaW4geW91ciBTZXVyYXQgb2JqZWN0CmVtYmVkZGluZ19kZiA8LSBlbWJlZGRpbmdfZGZbQ2VsbHMoQWxsX3NhbXBsZXNfTWVyZ2VkKSwgXQoKIyBDaGVjayBpZiBhbGwgY2VsbHMgbWF0Y2hlZCBjb3JyZWN0bHkKaWYoIWFsbChDZWxscyhBbGxfc2FtcGxlc19NZXJnZWQpICVpbiUgcm93bmFtZXMoZW1iZWRkaW5nX2RmKSkpIHsKICB3YXJuaW5nKCJTb21lIGNlbGxzIGluIEFsbF9zYW1wbGVzX01lcmdlZCBhcmUgbWlzc2luZyBpbiBlbWJlZGRpbmcgZGF0YSEiKQp9CgpgYGAKCgojIyDwn5OMIFN0ZXAgMjogQWRkIFBBR0EgVU1BUCBhcyBhIG5ldyByZWR1Y3Rpb24gaW4gU2V1cmF0CmBgYHtyLCBpbmNsdWRlPUZBTFNFfQpsaWJyYXJ5KFNldXJhdCkKCiMgT25seSB0aGUgZW1iZWRkaW5nIGNvb3JkaW5hdGVzCnBhZ2FfZW1iZWRkaW5nIDwtIGFzLm1hdHJpeChlbWJlZGRpbmdfZGZbLCBjKCJQQUdBX1VNQVBfMSIsICJQQUdBX1VNQVBfMiIpXSkKCiMgQWRkIHRvIFNldXJhdApBbGxfc2FtcGxlc19NZXJnZWRbWyJwYWdhIl1dIDwtIENyZWF0ZURpbVJlZHVjT2JqZWN0KAogIGVtYmVkZGluZ3MgPSBwYWdhX2VtYmVkZGluZywKICBrZXkgPSAiUEFHQV8iLAogIGFzc2F5ID0gRGVmYXVsdEFzc2F5KEFsbF9zYW1wbGVzX01lcmdlZCkKKQoKYGBgCgoKIyMg8J+TjCBTdGVwIDM6IEFkZCBMZWlkZW4gY2x1c3RlciBpbmZvIHRvIG1ldGFkYXRhCmBgYHtyLCBpbmNsdWRlPUZBTFNFfQojIyBBZGQgbGVpZGVuIGNsdXN0ZXIgZnJvbSBDU1YgdG8gbWV0YWRhdGEKQWxsX3NhbXBsZXNfTWVyZ2VkJGxlaWRlbiA8LSBlbWJlZGRpbmdfZGZbQ2VsbHMoQWxsX3NhbXBsZXNfTWVyZ2VkKSwgImxlaWRlbiJdCgpgYGAKCgojIDQuIFRyYWplY3RvcnkgaW5mZXJlbmNlIHVzaW5nIFNsaW5nc2hvdApgYGB7ciwgZWNobz1GQUxTRX0KIyBvYmogPC0gQWxsX3NhbXBsZXNfTWVyZ2VkCiMgCiMgcm0oQWxsX3NhbXBsZXNfTWVyZ2VkKQojIAojIGdjKCkKCiMgQ2FsY3VsYXRlIGNsdXN0ZXIgY2VudHJvaWRzIChmb3IgcGxvdHRpbmcgdGhlIGxhYmVscyBsYXRlcikKbW0gPC0gc3BhcnNlLm1vZGVsLm1hdHJpeCh+IDAgKyBmYWN0b3Iob2JqJGxlaWRlbikpCmNvbG5hbWVzKG1tKSA8LSBsZXZlbHMoZmFjdG9yKG9iaiRsZWlkZW4pKQpjZW50cm9pZHMyZCA8LSBhcy5tYXRyaXgodCh0KG9iakByZWR1Y3Rpb25zJHBhZ2FAY2VsbC5lbWJlZGRpbmdzKSAlKiUgbW0pIC8gTWF0cml4Ojpjb2xTdW1zKG1tKSkKCmBgYAoKCiMjIExldOKAmXMgdmlzdWFsaXplIHdoaWNoIGNsdXN0ZXJzIHdlIGhhdmUgaW4gb3VyIGRhdGFzZXQ6CmBgYHtyLCBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD0xMH0KCnZhcnMgPC0gYygiUGF0aWVudF9vcmlnaW4iLCAib3JpZy5pZGVudCIsICJsZWlkZW4iLCAiUGhhc2UiKQpwbCA8LSBsaXN0KCkKCmZvciAoaSBpbiB2YXJzKSB7CiAgcGxbW2ldXSA8LSBEaW1QbG90KG9iaiwgZ3JvdXAuYnkgPSBpLCBsYWJlbCA9IFQpICsgdGhlbWVfdm9pZCgpICsgTm9MZWdlbmQoKQp9CndyYXBfcGxvdHMocGwpCgp0YWJsZShvYmokbGVpZGVuKQpgYGAKCiMgNS4gRXhwbG9yaW5nIHRoZSBkYXRhCmBgYHtyfQoKdmFycyA8LSBjKCJUT1giLCAiTEFHMyIsICJDVExBNCIsICJUSUdJVCIsICJGT1hQMyIsICJJTDJSQSIsICJDVExBNCIsICJJS1pGMiIsICJUSUdJVCIsICJDQ1I3IiwgIlNFTEwiLCAiSUw3UiIsICJUQ0Y3IiwgIkNDUjciLCAiU0VMTCIsICJJTDdSIiwgIlRDRjciLCAiTEVGMSIsICJHWk1CIiwgIlBSRjEiLCAiSUZORyIsICJLTFJHMSIsICJDRDY5IiwgIkNYQ1I2IiwgIlBSRjEiLCAiR1pNQiIsICJOS0c3IiwgIkdOTFkiLCAiSVNHMTUiLCAiSUZJNiIsICJJRklUMyIsICJNWDEiLCAiTUtJNjciLCAiVE9QMkEiLCAiU1RBVDMiLCAiQUhSIiwgIkNDUjYiLCAiQkFURiIsICJQVFBSQyIsICJHWk1CIiwgIkJDTDYiLCAiSUNPUyIsICJIU1BBMUEiLCAiQVRGMyIsICJJTDJSQSIsICJDRDY5IiwgIkhMQS1EUkEiLCAiQ0QzNCIpCnBsIDwtIGxpc3QoKQoKcGwgPC0gbGlzdChEaW1QbG90KG9iaiwgZ3JvdXAuYnkgPSAibGVpZGVuIiwgbGFiZWwgPSBUKSArIHRoZW1lX3ZvaWQoKSArIE5vTGVnZW5kKCkpCmZvciAoaSBpbiB2YXJzKSB7CiAgcGxbW2ldXSA8LSBGZWF0dXJlUGxvdChvYmosIGZlYXR1cmVzID0gaSwgb3JkZXIgPSBUKSArIHRoZW1lX3ZvaWQoKSArIE5vTGVnZW5kKCkKfQp3cmFwX3Bsb3RzKHBsKQoKCmBgYAojIDYuIGNvbXB1dGUgdGhlIGxpbmVhZ2VzIG9uIHRoZXNlIGRhdGFzZXQKYGBge3J9CiMgRGVmaW5lIGxpbmVhZ2UgZW5kcwpFTkRTIDwtIGMoIjIiLCAiNiIsICI4IikKCnNldC5zZWVkKDEpCmxpbmVhZ2VzIDwtIGFzLlNsaW5nc2hvdERhdGFTZXQoZ2V0TGluZWFnZXMoCiAgZGF0YSAgICAgICAgICAgPSBvYmpAcmVkdWN0aW9ucyRwYWdhQGNlbGwuZW1iZWRkaW5ncywKICBjbHVzdGVyTGFiZWxzICA9IG9iaiRsZWlkZW4sCiAgZGlzdC5tZXRob2QgICAgPSAibW5uIiwgIyBJdCBjYW4gYmU6ICJzaW1wbGUiLCAic2NhbGVkLmZ1bGwiLCAic2NhbGVkLmRpYWciLCAic2xpbmdzaG90IiBvciAibW5uIgogIGVuZC5jbHVzICAgICAgID0gRU5EUywgIyBZb3UgY2FuIGFsc28gZGVmaW5lIHRoZSBFTkRTIQogIHN0YXJ0LmNsdXMgICAgID0gIjMiCikpICMgZGVmaW5lIHdoZXJlIHRvIFNUQVJUIHRoZSB0cmFqZWN0b3JpZXMKCgojIElGIE5FRURFRCwgT05FIENBTiBBTFNPIE1BTlVMQUxMWSBFRElUIFRIRSBMSU5FQUdFUywgRk9SIEVYQU1QTEU6CiMgc2VsIDwtIHNhcHBseSggbGluZWFnZXNAbGluZWFnZXMsIGZ1bmN0aW9uKHgpe3Jldih4KVsxXX0gKSAlaW4lIEVORFMKIyBsaW5lYWdlc0BsaW5lYWdlcyA8LSBsaW5lYWdlc0BsaW5lYWdlc1sgc2VsIF0KIyBuYW1lcyhsaW5lYWdlc0BsaW5lYWdlcykgPC0gcGFzdGUwKCJMaW5lYWdlIiwxOmxlbmd0aChsaW5lYWdlc0BsaW5lYWdlcykpCiMgbGluZWFnZXMKCgojIENoYW5nZSB0aGUgcmVkdWN0aW9uIHRvIG91ciAiZml4ZWQiIFVNQVAyZCAoRk9SIFZJU1VBTElTQVRJT04gT05MWSkKbGluZWFnZXNAcmVkdWNlZERpbSA8LSBvYmpAcmVkdWN0aW9ucyRwYWdhQGNlbGwuZW1iZWRkaW5ncwoKewogIHBsb3Qob2JqQHJlZHVjdGlvbnMkcGFnYUBjZWxsLmVtYmVkZGluZ3MsIGNvbCA9IHBhbFtvYmokbGVpZGVuXSwgY2V4ID0gLjUsIHBjaCA9IDE2KQogIGxpbmVzKGxpbmVhZ2VzLCBsd2QgPSAxLCBjb2wgPSAiYmxhY2siLCBjZXggPSAyKQogIHRleHQoY2VudHJvaWRzMmQsIGxhYmVscyA9IHJvd25hbWVzKGNlbnRyb2lkczJkKSwgY2V4ID0gMC44LCBmb250ID0gMiwgY29sID0gIndoaXRlIikKfQoKYGBgCgojIyAgRGVmaW5pbmcgUHJpbmNpcGFsIEN1cnZlcwpgYGB7cn0KCiMgRGVmaW5lIGN1cnZlcwpjdXJ2ZXMgPC0gYXMuU2xpbmdzaG90RGF0YVNldChnZXRDdXJ2ZXMoCiAgZGF0YSAgICAgICAgICA9IGxpbmVhZ2VzLAogIHRocmVzaCAgICAgICAgPSAxZS0xLAogIHN0cmV0Y2ggICAgICAgPSAxZS0xLAogIGFsbG93LmJyZWFrcyAgPSBGLAogIGFwcHJveF9wb2ludHMgPSAxMDAKKSkKCgojIFBsb3RzCnsKICBwbG90KG9iakByZWR1Y3Rpb25zJHBhZ2FAY2VsbC5lbWJlZGRpbmdzLCBjb2wgPSBwYWxbb2JqJGxlaWRlbl0sIHBjaCA9IDE2KQogIGxpbmVzKGN1cnZlcywgbHdkID0gMiwgY29sID0gImJsYWNrIikKICB0ZXh0KGNlbnRyb2lkczJkLCBsYWJlbHMgPSBsZXZlbHMob2JqJGxlaWRlbiksIGNleCA9IDEsIGZvbnQgPSAyKQp9CmBgYAoKIyMgIGNvbXB1dGUgdGhlIGRpZmZlcmVudGlhdGlvbiBwc2V1ZG90aW1lCmBgYHtyfQoKcHNldWRvdGltZSA8LSBzbGluZ1BzZXVkb3RpbWUoY3VydmVzLCBuYSA9IEZBTFNFKQpjZWxsV2VpZ2h0cyA8LSBzbGluZ0N1cnZlV2VpZ2h0cyhjdXJ2ZXMpCgp4IDwtIHJvd01lYW5zKHBzZXVkb3RpbWUpCnggPC0geCAvIG1heCh4KQpvIDwtIG9yZGVyKHgpCgp7CiAgcGxvdChvYmpAcmVkdWN0aW9ucyRwYWdhQGNlbGwuZW1iZWRkaW5nc1tvLCBdLAogICAgbWFpbiA9IHBhc3RlMCgicHNldWRvdGltZSIpLCBwY2ggPSAxNiwgY2V4ID0gMC40LCBheGVzID0gRiwgeGxhYiA9ICIiLCB5bGFiID0gIiIsCiAgICBjb2wgPSBjb2xvclJhbXBQYWxldHRlKGMoImdyZXk3MCIsICJvcmFuZ2UzIiwgImZpcmVicmljayIsICJwdXJwbGU0IikpKDk5KVt4W29dICogOTggKyAxXQogICkKICBwb2ludHMoY2VudHJvaWRzMmQsIGNleCA9IDIuNSwgcGNoID0gMTYsIGNvbCA9ICIjRkZGRkZGOTkiKQogIHRleHQoY2VudHJvaWRzMmQsIGxhYmVscyA9IGxldmVscyhvYmokbGVpZGVuKSwgY2V4ID0gMSwgZm9udCA9IDIpCn0KYGBgCiMgNy4gRmluZGluZyBkaWZmZXJlbnRpYWxseSBleHByZXNzZWQgZ2VuZXMKYGBge3J9CgpzZWxfY2VsbHMgPC0gc3BsaXQoY29sbmFtZXMob2JqQGFzc2F5cyRTQ1RAZGF0YSksIG9iaiRsZWlkZW4pCnNlbF9jZWxscyA8LSB1bmxpc3QobGFwcGx5KHNlbF9jZWxscywgZnVuY3Rpb24oeCkgewogIHNldC5zZWVkKDEpCiAgcmV0dXJuKHNhbXBsZSh4LCAyMCkpCn0pKQoKZ3YgPC0gYXMuZGF0YS5mcmFtZShuYS5vbWl0KHNjcmFuOjptb2RlbEdlbmVWYXIob2JqQGFzc2F5cyRTQ1RAZGF0YVssIHNlbF9jZWxsc10pKSkKZ3YgPC0gZ3Zbb3JkZXIoZ3YkYmlvLCBkZWNyZWFzaW5nID0gVCksIF0Kc2VsX2dlbmVzIDwtIHNvcnQocm93bmFtZXMoZ3YpWzE6NTAwXSkKCnBhdGhfZmlsZSA8LSAiL2hvbWUvYmlvaW5mby9kYXRhL3RyYWplY3Rvcnkvc2V1cmF0X3NjZWdhbS5yZHMiCgojIGZldGNoX2RhdGEgaXMgZGVmaW5lZCBhdCB0aGUgdG9wIG9mIHRoaXMgZG9jdW1lbnQKc2NlR0FNIDwtIGZpdEdBTSgKICBjb3VudHMgPSBkcm9wMChvYmpAYXNzYXlzJFNDVEBkYXRhW3NlbF9nZW5lcywgc2VsX2NlbGxzXSksCiAgcHNldWRvdGltZSA9IHBzZXVkb3RpbWVbc2VsX2NlbGxzLCBdLAogIGNlbGxXZWlnaHRzID0gY2VsbFdlaWdodHNbc2VsX2NlbGxzLCBdLAogIG5rbm90cyA9IDUsIHZlcmJvc2UgPSBUUlVFLCBwYXJhbGxlbCA9IFRSVUUsIHNjZSA9IFRSVUUsCiAgQlBQQVJBTSA9IEJpb2NQYXJhbGxlbDo6TXVsdGljb3JlUGFyYW0oKQopCgoKCnBsb3RHZW5lQ291bnQoY3VydmVzLCBjbHVzdGVycyA9IG9iaiRsZWlkZW4sIG1vZGVscyA9IHNjZUdBTSkKCgpsaW5lYWdlcwoKbGMgPC0gc2FwcGx5KGxpbmVhZ2VzQGxpbmVhZ2VzLCBmdW5jdGlvbih4KSB7CiAgcmV2KHgpWzFdCn0pCm5hbWVzKGxjKSA8LSBnc3ViKCJMaW5lYWdlIiwgIkwiLCBuYW1lcyhsYykpCmxjLmlkeCA9IG1hdGNoKGxjLCBsZXZlbHMob2JqJGxlaWRlbikpCgp7CiAgcGxvdChvYmpAcmVkdWN0aW9ucyRwYWdhQGNlbGwuZW1iZWRkaW5ncywgY29sID0gcGFsW29iaiRsZWlkZW5dLCBwY2ggPSAxNikKICBsaW5lcyhjdXJ2ZXMsIGx3ZCA9IDIsIGNvbCA9ICJibGFjayIpCiAgcG9pbnRzKGNlbnRyb2lkczJkW2xjLmlkeCwgXSwgY29sID0gImJsYWNrIiwgcGNoID0gMTYsIGNleCA9IDQpCiAgdGV4dChjZW50cm9pZHMyZFtsYy5pZHgsIF0sIGxhYmVscyA9IG5hbWVzKGxjKSwgY2V4ID0gMSwgZm9udCA9IDIsIGNvbCA9ICJ3aGl0ZSIpCn0KCgoKCmBgYAoKCgoKCgoKCiMjIEdlbmVzIHRoYXQgY2hhbmdlIHdpdGggcHNldWRvdGltZQpgYGB7cn0KCnNldC5zZWVkKDgpCnJlcyA8LSBuYS5vbWl0KGFzc29jaWF0aW9uVGVzdChzY2VHQU0sIGNvbnRyYXN0VHlwZSA9ICJjb25zZWN1dGl2ZSIpKQpyZXMgPC0gcmVzW3JlcyRwdmFsdWUgPCAxZS0zLCBdCnJlcyA8LSByZXNbcmVzJHdhbGRTdGF0ID4gbWVhbihyZXMkd2FsZFN0YXQpLCBdCnJlcyA8LSByZXNbb3JkZXIocmVzJHdhbGRTdGF0LCBkZWNyZWFzaW5nID0gVCksIF0KcmVzWzE6MTAsIF0KCmBgYAoKCiMjIFdlIGNhbiBwbG90IHRoZWlyIGV4cHJlc3Npb24KYGBge3J9CgpwYXIobWZyb3cgPSBjKDQsIDQpLCBtYXIgPSBjKC4xLCAuMSwgMiwgMSkpCnsKICBwbG90KG9iakByZWR1Y3Rpb25zJHBhZ2FAY2VsbC5lbWJlZGRpbmdzLCBjb2wgPSBwYWxbb2JqJGxlaWRlbl0sIGNleCA9IC41LCBwY2ggPSAxNiwgYXhlcyA9IEYsIHhsYWIgPSAiIiwgeWxhYiA9ICIiKQogIGxpbmVzKGN1cnZlcywgbHdkID0gMiwgY29sID0gImJsYWNrIikKICBwb2ludHMoY2VudHJvaWRzMmRbbGMuaWR4LCBdLCBjb2wgPSAiYmxhY2siLCBwY2ggPSAxNSwgY2V4ID0gMywgeHBkID0gVCkKICB0ZXh0KGNlbnRyb2lkczJkW2xjLmlkeCwgXSwgbGFiZWxzID0gbmFtZXMobGMpLCBjZXggPSAxLCBmb250ID0gMiwgY29sID0gIndoaXRlIiwgeHBkID0gVCkKfQoKdmFycyA8LSByb3duYW1lcyhyZXNbMToxNSwgXSkKdmFycyA8LSBuYS5vbWl0KHZhcnNbdmFycyAhPSAiTkEiXSkKCmZvciAoaSBpbiB2YXJzKSB7CiAgeCA8LSBkcm9wMChvYmpAYXNzYXlzJFNDVEBkYXRhKVtpLCBdCiAgeCA8LSAoeCAtIG1pbih4KSkgLyAobWF4KHgpIC0gbWluKHgpKQogIG8gPC0gb3JkZXIoeCkKICBwbG90KG9iakByZWR1Y3Rpb25zJHBhZ2FAY2VsbC5lbWJlZGRpbmdzW28sIF0sCiAgICBtYWluID0gcGFzdGUwKGkpLCBwY2ggPSAxNiwgY2V4ID0gMC41LCBheGVzID0gRiwgeGxhYiA9ICIiLCB5bGFiID0gIiIsCiAgICBjb2wgPSBjb2xvclJhbXBQYWxldHRlKGMoImxpZ2h0Z3JheSIsICJncmV5NjAiLCAibmF2eSIpKSg5OSlbeFtvXSAqIDk4ICsgMV0KICApCn0KCmBgYAoKCgojIyBHZW5lcyB0aGF0IGNoYW5nZSBiZXR3ZWVuIHR3byBwc2V1ZG90aW1lIHBvaW50cwpgYGB7cn0KcmVzIDwtIG5hLm9taXQoc3RhcnRWc0VuZFRlc3Qoc2NlR0FNLCBwc2V1ZG90aW1lVmFsdWVzID0gYygwLCAxKSkpCnJlcyA8LSByZXNbcmVzJHB2YWx1ZSA8IDFlLTMsIF0KcmVzIDwtIHJlc1tyZXMkd2FsZFN0YXQgPiBtZWFuKHJlcyR3YWxkU3RhdCksIF0KcmVzIDwtIHJlc1tvcmRlcihyZXMkd2FsZFN0YXQsIGRlY3JlYXNpbmcgPSBUKSwgXQpyZXNbMToxMCwgMTo2XQpgYGAKIyMgaWRlbnRpZnkgd2hpY2ggZ2VuZXMgZ28gdXAgb3IgZG93bi4gTGV04oCZcyBjaGVjayBsaW5lYWdlIDE6CmBgYHtyfQojIEdldCB0aGUgdG9wIFVQIGFuZCBEb3duIHJlZ3VsYXRlZCBpbiBsaW5lYWdlIDEKcmVzX2xpbjEgPC0gc29ydChzZXROYW1lcyhyZXMkbG9nRkNsaW5lYWdlMSwgcm93bmFtZXMocmVzKSkpCnZhcnMgPC0gbmFtZXMoYyhyZXYocmVzX2xpbjEpWzE6N10sIHJlc19saW4xWzE6OF0pKQp2YXJzIDwtIG5hLm9taXQodmFyc1t2YXJzICE9ICJOQSJdKQoKcGFyKG1mcm93ID0gYyg0LCA0KSwgbWFyID0gYyguMSwgLjEsIDIsIDEpKQoKewogIHBsb3Qob2JqQHJlZHVjdGlvbnMkcGFnYUBjZWxsLmVtYmVkZGluZ3MsIGNvbCA9IHBhbFtvYmokbGVpZGVuXSwgY2V4ID0gLjUsIHBjaCA9IDE2LCBheGVzID0gRiwgeGxhYiA9ICIiLCB5bGFiID0gIiIpCiAgbGluZXMoY3VydmVzLCBsd2QgPSAyLCBjb2wgPSAiYmxhY2siKQogIHBvaW50cyhjZW50cm9pZHMyZFtsYy5pZHgsIF0sIGNvbCA9ICJibGFjayIsIHBjaCA9IDE1LCBjZXggPSAzLCB4cGQgPSBUKQogIHRleHQoY2VudHJvaWRzMmRbbGMuaWR4LCBdLCBsYWJlbHMgPSBuYW1lcyhsYyksIGNleCA9IDEsIGZvbnQgPSAyLCBjb2wgPSAid2hpdGUiLCB4cGQgPSBUKQp9Cgpmb3IgKGkgaW4gdmFycykgewogIHggPC0gZHJvcDAob2JqQGFzc2F5cyRTQ1RAZGF0YSlbaSwgXQogIHggPC0gKHggLSBtaW4oeCkpIC8gKG1heCh4KSAtIG1pbih4KSkKICBvIDwtIG9yZGVyKHgpCiAgcGxvdChvYmpAcmVkdWN0aW9ucyRwYWdhQGNlbGwuZW1iZWRkaW5nc1tvLCBdLAogICAgbWFpbiA9IHBhc3RlMChpKSwgcGNoID0gMTYsIGNleCA9IDAuNSwgYXhlcyA9IEYsIHhsYWIgPSAiIiwgeWxhYiA9ICIiLAogICAgY29sID0gY29sb3JSYW1wUGFsZXR0ZShjKCJsaWdodGdyYXkiLCAiZ3JleTYwIiwgIm5hdnkiKSkoOTkpW3hbb10gKiA5OCArIDFdCiAgKQp9CmBgYAoKIyMgR2VuZXMgdGhhdCBhcmUgZGlmZmVyZW50IGJldHdlZW4gbGluZWFnZXMKYGBge3J9CnJlcyA8LSBuYS5vbWl0KGRpZmZFbmRUZXN0KHNjZUdBTSkpCnJlcyA8LSByZXNbcmVzJHB2YWx1ZSA8IDFlLTMsIF0KcmVzIDwtIHJlc1tyZXMkd2FsZFN0YXQgPiBtZWFuKHJlcyR3YWxkU3RhdCksIF0KcmVzIDwtIHJlc1tvcmRlcihyZXMkd2FsZFN0YXQsIGRlY3JlYXNpbmcgPSBUKSwgXQpyZXNbMToxMCwgXQoKYGBgCgojIyBwYWlyd2lzZSBjb21wYXJpc29uIGJldHdlZW4gZWFjaCBsaW5lYWdlLiBMZXTigJlzIGNoZWNrIGxpbmVhZ2UgMSB2cyBsaW5lYWdlIDI6CmBgYHtyfQojIEdldCB0aGUgdG9wIFVQIGFuZCBEb3duIHJlZ3VsYXRlZCBpbiBsaW5lYWdlIDEgdnMgMgpyZXNfbGluMV8yIDwtIHNvcnQoc2V0TmFtZXMocmVzJGxvZ0ZDMV8yLCByb3duYW1lcyhyZXMpKSkKdmFycyA8LSBuYW1lcyhjKHJldihyZXNfbGluMV8yKVsxOjddLCByZXNfbGluMV8yWzE6OF0pKQp2YXJzIDwtIG5hLm9taXQodmFyc1t2YXJzICE9ICJOQSJdKQoKcGFyKG1mcm93ID0gYyg0LCA0KSwgbWFyID0gYyguMSwgLjEsIDIsIDEpKQp7CiAgcGxvdChvYmpAcmVkdWN0aW9ucyRwYWdhQGNlbGwuZW1iZWRkaW5ncywgY29sID0gcGFsW29iaiRsZWlkZW5dLCBjZXggPSAuNSwgcGNoID0gMTYsIGF4ZXMgPSBGLCB4bGFiID0gIiIsIHlsYWIgPSAiIikKICBsaW5lcyhjdXJ2ZXMsIGx3ZCA9IDIsIGNvbCA9ICJibGFjayIpCiAgcG9pbnRzKGNlbnRyb2lkczJkW2xjLmlkeCwgXSwgY29sID0gImJsYWNrIiwgcGNoID0gMTUsIGNleCA9IDMsIHhwZCA9IFQpCiAgdGV4dChjZW50cm9pZHMyZFtsYy5pZHgsIF0sIGxhYmVscyA9IG5hbWVzKGxjKSwgY2V4ID0gMSwgZm9udCA9IDIsIGNvbCA9ICJ3aGl0ZSIsIHhwZCA9IFQpCn0KCmZvciAoaSBpbiB2YXJzKSB7CiAgeCA8LSBkcm9wMChvYmpAYXNzYXlzJFNDVEBkYXRhKVtpLCBdCiAgeCA8LSAoeCAtIG1pbih4KSkgLyAobWF4KHgpIC0gbWluKHgpKQogIG8gPC0gb3JkZXIoeCkKICBwbG90KG9iakByZWR1Y3Rpb25zJHBhZ2FAY2VsbC5lbWJlZGRpbmdzW28sIF0sCiAgICBtYWluID0gcGFzdGUwKGkpLCBwY2ggPSAxNiwgY2V4ID0gMC41LCBheGVzID0gRiwgeGxhYiA9ICIiLCB5bGFiID0gIiIsCiAgICBjb2wgPSBjb2xvclJhbXBQYWxldHRlKGMoImxpZ2h0Z3JheSIsICJncmV5NjAiLCAibmF2eSIpKSg5OSlbeFtvXSAqIDk4ICsgMV0KICApCn0KYGBgCgoKCgo=