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=