Setup knitr and load utility functions

knitr::opts_chunk$set(echo = TRUE)
knitr::opts_knit$set(root.dir="E:/DISC/reproducibility")
utilities_path = "./source/utilities.r"
source(utilities_path)
Registered S3 method overwritten by 'dplyr':
  method           from
  print.rowwise_df     
Registered S3 methods overwritten by 'htmltools':
  method               from         
  print.html           tools:rstudio
  print.shiny.tag      tools:rstudio
  print.shiny.tag.list tools:rstudio
Registered S3 method overwritten by 'htmlwidgets':
  method           from         
  print.htmlwidget tools:rstudio
Registered S3 method overwritten by 'data.table':
  method           from
  print.data.table     
reldist: Relative Distribution Methods
Version 1.6-6 created on 2016-10-07.
copyright (c) 2003, Mark S. Handcock, University of California-Los Angeles
 For citation information, type citation("reldist").
 Type help(package="reldist") to get started.

Load raw data and downsampling

Here, we use PBMC dataset as an example.
The fraction of sampling is set to 50% of the original library size across cells.
Only 1 replicate will be generated here as an example.
Only imputed genes will be kept for comparison.

used_datasets = c("MELANOMA", "SSCORTEX", "CBMC", "PBMC")
method_names = c("DISC", "scVI", "MAGIC", "DCA", "scScope", "DeepImpute", "VIPER", "scImpute")
output_dir = "./results/Identification_of_true_zeros"
dir.create(output_dir, showWarnings = F, recursive = T)
data_list = list()
for(ii in used_datasets){
  data_list[[ii]] = list()
  raw_data = readh5_loom(paste0("./data/", ii, "/raw.loom"))
  vst_file = paste0(output_dir, "/", ii, "_vst_gene.tsv")
  if(file.exists(vst_file)){
    hvg_info = read.table(vst_file)
    print("load vst_file")
  }else{
    hvg_info = FindVariableFeatures_vst_by_genes(raw_data)
    hvg_info = hvg_info[order(hvg_info$variance.standardized, decreasing = T), ]
    write.table(hvg_info, vst_file, sep = "\t", quote = F, row.names = T, col.names = T)
  }
  ds_dir = paste0("./data/", ii, "/ds_0.5/r1")
  observed_data = readh5_loom(paste0(ds_dir, "/gene_selection.loom"))
  compared_genes = rownames(observed_data)
  top_1000_genes = rownames(hvg_info)[rownames(hvg_info) %in% compared_genes][1:1000]
  raw_data = raw_data[compared_genes, ]
  for(jj in method_names){
    if(jj == "DISC"){
      imputation = readh5_loom(paste0(ds_dir, "/", jj, ".loom"))[compared_genes, ]
    }else{
      imputation = readh5_imputation(paste0(ds_dir, "/", jj, ".hdf5"))[compared_genes, ]
    }
    imputation_cp10k = sweep(imputation, 2, 10000 / colSums(imputation), "*")
    raw_zero = raw_data == 0 & observed_data == 0
    induced_zero = raw_data != 0 & observed_data == 0
    kept_values = raw_data != 0 & observed_data != 0
    data_list[[ii]][[jj]] = list(raw_zero_imputation = imputation_cp10k[raw_zero],
                                 induced_zero_imputation = imputation_cp10k[induced_zero],
                                 top_raw_zero_imputation = imputation_cp10k[top_1000_genes, ][raw_zero[top_1000_genes, ]],
                                 top_induced_zero_imputation = imputation_cp10k[top_1000_genes, ][induced_zero[top_1000_genes, ]])
    cat("Finish: ", ii, " - ", jj, "\n")
  }
  cat("Finish: ", ii, "\n")
}
[1] "./data/MELANOMA/raw.loom"
[1] 32287  8498
[1] "load vst_file"
[1] "./data/MELANOMA/ds_0.5/r1/gene_selection.loom"
[1] 12509  8498
[1] "./data/MELANOMA/ds_0.5/r1/DISC.loom"
[1] 32287  8498
Finish:  MELANOMA  -  DISC 
[1] "./data/MELANOMA/ds_0.5/r1/scVI.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  scVI 
[1] "./data/MELANOMA/ds_0.5/r1/MAGIC.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  MAGIC 
[1] "./data/MELANOMA/ds_0.5/r1/DCA.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  DCA 
[1] "./data/MELANOMA/ds_0.5/r1/scScope.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  scScope 
[1] "./data/MELANOMA/ds_0.5/r1/DeepImpute.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  DeepImpute 
[1] "./data/MELANOMA/ds_0.5/r1/VIPER.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  VIPER 
[1] "./data/MELANOMA/ds_0.5/r1/scImpute.hdf5"
[1] 12509  8498
Finish:  MELANOMA  -  scImpute 
Finish:  MELANOMA 
[1] "./data/SSCORTEX/raw.loom"
[1] 27998  7416
[1] "load vst_file"
[1] "./data/SSCORTEX/ds_0.5/r1/gene_selection.loom"
[1] 12584  7416
[1] "./data/SSCORTEX/ds_0.5/r1/DISC.loom"
[1] 27998  7416
Finish:  SSCORTEX  -  DISC 
[1] "./data/SSCORTEX/ds_0.5/r1/scVI.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  scVI 
[1] "./data/SSCORTEX/ds_0.5/r1/MAGIC.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  MAGIC 
[1] "./data/SSCORTEX/ds_0.5/r1/DCA.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  DCA 
[1] "./data/SSCORTEX/ds_0.5/r1/scScope.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  scScope 
[1] "./data/SSCORTEX/ds_0.5/r1/DeepImpute.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  DeepImpute 
[1] "./data/SSCORTEX/ds_0.5/r1/VIPER.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  VIPER 
[1] "./data/SSCORTEX/ds_0.5/r1/scImpute.hdf5"
[1] 12584  7416
Finish:  SSCORTEX  -  scImpute 
Finish:  SSCORTEX 
[1] "./data/CBMC/raw.loom"
[1] 20400  8005
[1] "load vst_file"
[1] "./data/CBMC/ds_0.5/r1/gene_selection.loom"
[1] 9273 8005
[1] "./data/CBMC/ds_0.5/r1/DISC.loom"
[1] 20400  8005
Finish:  CBMC  -  DISC 
[1] "./data/CBMC/ds_0.5/r1/scVI.hdf5"
[1] 9273 8005
Finish:  CBMC  -  scVI 
[1] "./data/CBMC/ds_0.5/r1/MAGIC.hdf5"
[1] 9273 8005
Finish:  CBMC  -  MAGIC 
[1] "./data/CBMC/ds_0.5/r1/DCA.hdf5"
[1] 9273 8005
Finish:  CBMC  -  DCA 
[1] "./data/CBMC/ds_0.5/r1/scScope.hdf5"
[1] 9273 8005
Finish:  CBMC  -  scScope 
[1] "./data/CBMC/ds_0.5/r1/DeepImpute.hdf5"
[1] 9273 8005
Finish:  CBMC  -  DeepImpute 
[1] "./data/CBMC/ds_0.5/r1/VIPER.hdf5"
[1] 9273 8005
Finish:  CBMC  -  VIPER 
[1] "./data/CBMC/ds_0.5/r1/scImpute.hdf5"
[1] 9273 8005
Finish:  CBMC  -  scImpute 
Finish:  CBMC 
[1] "./data/PBMC/raw.loom"
[1] 32738  2638
[1] "load vst_file"
[1] "./data/PBMC/ds_0.5/r1/gene_selection.loom"
[1] 6403 2638
[1] "./data/PBMC/ds_0.5/r1/DISC.loom"
[1] 32738  2638
Finish:  PBMC  -  DISC 
[1] "./data/PBMC/ds_0.5/r1/scVI.hdf5"
[1] 6403 2638
Finish:  PBMC  -  scVI 
[1] "./data/PBMC/ds_0.5/r1/MAGIC.hdf5"
[1] 6403 2638
Finish:  PBMC  -  MAGIC 
[1] "./data/PBMC/ds_0.5/r1/DCA.hdf5"
[1] 6403 2638
Finish:  PBMC  -  DCA 
[1] "./data/PBMC/ds_0.5/r1/scScope.hdf5"
[1] 6403 2638
Finish:  PBMC  -  scScope 
[1] "./data/PBMC/ds_0.5/r1/DeepImpute.hdf5"
[1] 6403 2638
Finish:  PBMC  -  DeepImpute 
[1] "./data/PBMC/ds_0.5/r1/VIPER.hdf5"
[1] 6403 2638
Finish:  PBMC  -  VIPER 
[1] "./data/PBMC/ds_0.5/r1/scImpute.hdf5"
[1] 6403 2638
Finish:  PBMC  -  scImpute 
Finish:  PBMC 

Following this paper (SAVER: gene expression recovery for single-cell RNA sequencing, https://www.nature.com/articles/s41592-018-0033-z), we evaluate the performance of different imputation methods to indentify true zeros.

All genes

par(mfrow = c(1, length(used_datasets)), mar = c(5, 0, 0.5, 0), oma = c(0, 5, 6, 2), mgp = c(3.5, 1, 0), cex.axis = 1.1, cex.lab = 1.5, font.lab = 2, cex.main = 1.5)
mtext_position = seq(from = 0, to = 1, by = 1 / length(used_datasets) / 2)[seq(length(used_datasets)) * 2]
names(mtext_position) = used_datasets
for(ii in used_datasets){
  max_value = 0
  for(jj in method_names){
    max_value = max(c(max_value, data_list[[ii]][[jj]][["raw_zero_imputation"]], data_list[[ii]][[jj]][["induced_zero_imputation"]]))
  }
  n = 2 ^ (round(log(max_value, base = 2)) + 7)
  bw = (max_value * (n + 10)) / (n ^ 2)
  to = max_value + (bw * 5)
  from = -(bw * 5)
  x_max = 0
  for(jj in method_names){
    data_list[[ii]][[jj]][["raw_zero_density"]] = density(data_list[[ii]][[jj]][["raw_zero_imputation"]], from = from, to = to, n = n, bw = bw)
    data_list[[ii]][[jj]][["induced_zero_density"]] = density(data_list[[ii]][[jj]][["induced_zero_imputation"]], from = from, to = to, n = n, bw = bw)
    data_list[[ii]][[jj]][["y_max"]] = max(c(data_list[[ii]][[jj]][["raw_zero_density"]]$y, data_list[[ii]][[jj]][["induced_zero_density"]]$y))
    cutoff = data_list[[ii]][[jj]][["y_max"]] * 0.005
    test_vector = !(data_list[[ii]][[jj]][["raw_zero_density"]]$y < cutoff & data_list[[ii]][[jj]][["induced_zero_density"]]$y < cutoff)
    for(kk in seq(from = length(test_vector), to = 1)){
      if(test_vector[kk]){
        x_max = max(c(x_max, data_list[[ii]][[jj]][["raw_zero_density"]]$x[kk + 1]))
        break()
      }
    }
  }
  data_list[[ii]][["x_max"]] = x_max
  cat("Finish: ", ii, "\n")
}
Finish:  MELANOMA 
Finish:  SSCORTEX 
Finish:  CBMC 
Finish:  PBMC 
for(ii in method_names){
  for(jj in used_datasets){
    plot(0, type = "n", xlim = c(-min(c(1, data_list[[jj]][["x_max"]] * 0.05)), data_list[[jj]][["x_max"]]), ylim = c(0, data_list[[jj]][[ii]][["y_max"]]), axes = FALSE, ann = FALSE, frame.plot = TRUE)
    lines(data_list[[jj]][[ii]][["raw_zero_density"]], col = "black", lwd = 2)
    lines(data_list[[jj]][[ii]][["induced_zero_density"]], col = "red", lwd = 2)
    axis(1)
    mtext(jj, outer = TRUE, cex = 1.2, font = 2, line = 0.5, at = mtext_position[jj])
    cat("Finish: ", ii, " - ", jj, "\n")
  }
  mtext(paste0(ii, " - All genes"), outer = TRUE, cex = 1.4, font = 2, line = 3)
  legend("topright", c("Raw zero", "Sampled zero"), lty = 1, col = c("black", "red"), lwd = 2)
}
Finish:  DISC  -  MELANOMA 
Finish:  DISC  -  SSCORTEX 
Finish:  DISC  -  CBMC 
Finish:  DISC  -  PBMC 

Finish:  scVI  -  MELANOMA 
Finish:  scVI  -  SSCORTEX 
Finish:  scVI  -  CBMC 
Finish:  scVI  -  PBMC 

Finish:  MAGIC  -  MELANOMA 
Finish:  MAGIC  -  SSCORTEX 
Finish:  MAGIC  -  CBMC 
Finish:  MAGIC  -  PBMC 

Finish:  DCA  -  MELANOMA 
Finish:  DCA  -  SSCORTEX 
Finish:  DCA  -  CBMC 
Finish:  DCA  -  PBMC 

Finish:  scScope  -  MELANOMA 
Finish:  scScope  -  SSCORTEX 
Finish:  scScope  -  CBMC 
Finish:  scScope  -  PBMC 

Finish:  DeepImpute  -  MELANOMA 
Finish:  DeepImpute  -  SSCORTEX 
Finish:  DeepImpute  -  CBMC 
Finish:  DeepImpute  -  PBMC 

Finish:  VIPER  -  MELANOMA 
Finish:  VIPER  -  SSCORTEX 
Finish:  VIPER  -  CBMC 
Finish:  VIPER  -  PBMC 

Finish:  scImpute  -  MELANOMA 
Finish:  scImpute  -  SSCORTEX 
Finish:  scImpute  -  CBMC 
Finish:  scImpute  -  PBMC 

Top 1000 genes

par(mfrow = c(1, length(used_datasets)), mar = c(5, 0, 0.5, 0), oma = c(0, 5, 6, 2), mgp = c(3.5, 1, 0), cex.axis = 1.1, cex.lab = 1.5, font.lab = 2, cex.main = 1.5)
mtext_position = seq(from = 0, to = 1, by = 1 / length(used_datasets) / 2)[seq(length(used_datasets)) * 2]
names(mtext_position) = used_datasets
for(ii in used_datasets){
  max_value = 0
  for(jj in method_names){
    max_value = max(c(max_value, data_list[[ii]][[jj]][["top_raw_zero_imputation"]], data_list[[ii]][[jj]][["top_induced_zero_imputation"]]))
  }
  n = 2 ^ (round(log(max_value, base = 2)) + 7)
  bw = (max_value * (n + 10)) / (n ^ 2)
  to = max_value + (bw * 5)
  from = -(bw * 5)
  x_max = 0
  for(jj in method_names){
    data_list[[ii]][[jj]][["top_raw_zero_density"]] = density(data_list[[ii]][[jj]][["top_raw_zero_imputation"]], from = from, to = to, n = n, bw = bw)
    data_list[[ii]][[jj]][["top_induced_zero_density"]] = density(data_list[[ii]][[jj]][["top_induced_zero_imputation"]], from = from, to = to, n = n, bw = bw)
    data_list[[ii]][[jj]][["top_y_max"]] = max(c(data_list[[ii]][[jj]][["top_raw_zero_density"]]$y, data_list[[ii]][[jj]][["top_induced_zero_density"]]$y))
    cutoff = data_list[[ii]][[jj]][["top_y_max"]] * 0.005
    test_vector = !(data_list[[ii]][[jj]][["top_raw_zero_density"]]$y < cutoff & data_list[[ii]][[jj]][["top_induced_zero_density"]]$y < cutoff)
    for(kk in seq(from = length(test_vector), to = 1)){
      if(test_vector[kk]){
        x_max = max(c(x_max, data_list[[ii]][[jj]][["top_raw_zero_density"]]$x[kk + 1]))
        break()
      }
    }
  }
  data_list[[ii]][["top_x_max"]] = x_max
  cat("Finish: ", ii, "\n")
}
Finish:  MELANOMA 
Finish:  SSCORTEX 
Finish:  CBMC 
Finish:  PBMC 
for(ii in method_names){
  for(jj in used_datasets){
    plot(0, type = "n", xlim = c(-min(c(1, data_list[[jj]][["top_x_max"]] * 0.05)), data_list[[jj]][["top_x_max"]]), ylim = c(0, data_list[[jj]][[ii]][["top_y_max"]]), axes = FALSE, ann = FALSE, frame.plot = TRUE)
    lines(data_list[[jj]][[ii]][["top_raw_zero_density"]], col = "black", lwd = 2)
    lines(data_list[[jj]][[ii]][["top_induced_zero_density"]], col = "red", lwd = 2)
    axis(1)
    mtext(jj, outer = TRUE, cex = 1.2, font = 2, line = 0.5, at = mtext_position[jj])
    cat("Finish: ", ii, " - ", jj, "\n")
  }
  mtext(paste0(ii, " - Top 1000 genes"), outer = TRUE, cex = 1.4, font = 2, line = 3)
  legend("topright", c("Raw zero", "Sampled zero"), lty = 1, col = c("black", "red"), lwd = 2)
}
Finish:  DISC  -  MELANOMA 
Finish:  DISC  -  SSCORTEX 
Finish:  DISC  -  CBMC 
Finish:  DISC  -  PBMC 

Finish:  scVI  -  MELANOMA 
Finish:  scVI  -  SSCORTEX 
Finish:  scVI  -  CBMC 
Finish:  scVI  -  PBMC 

Finish:  MAGIC  -  MELANOMA 
Finish:  MAGIC  -  SSCORTEX 
Finish:  MAGIC  -  CBMC 
Finish:  MAGIC  -  PBMC 

Finish:  DCA  -  MELANOMA 
Finish:  DCA  -  SSCORTEX 
Finish:  DCA  -  CBMC 
Finish:  DCA  -  PBMC 

Finish:  scScope  -  MELANOMA 
Finish:  scScope  -  SSCORTEX 
Finish:  scScope  -  CBMC 
Finish:  scScope  -  PBMC 

Finish:  DeepImpute  -  MELANOMA 
Finish:  DeepImpute  -  SSCORTEX 
Finish:  DeepImpute  -  CBMC 
Finish:  DeepImpute  -  PBMC 

Finish:  VIPER  -  MELANOMA 
Finish:  VIPER  -  SSCORTEX 
Finish:  VIPER  -  CBMC 
Finish:  VIPER  -  PBMC 

Finish:  scImpute  -  MELANOMA 
Finish:  scImpute  -  SSCORTEX 
Finish:  scImpute  -  CBMC 
Finish:  scImpute  -  PBMC 

LS0tDQp0aXRsZTogIklkZW50aWZpY2F0aW9uIG9mIHRydWUgemVyb3MiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KIyMjIFNldHVwIGtuaXRyIGFuZCBsb2FkIHV0aWxpdHkgZnVuY3Rpb25zDQpgYGB7ciBzZXR1cH0NCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkNCmtuaXRyOjpvcHRzX2tuaXQkc2V0KHJvb3QuZGlyPSJFOi9ESVNDL3JlcHJvZHVjaWJpbGl0eSIpDQpgYGANCmBgYHtyfQ0KdXRpbGl0aWVzX3BhdGggPSAiLi9zb3VyY2UvdXRpbGl0aWVzLnIiDQpzb3VyY2UodXRpbGl0aWVzX3BhdGgpDQpgYGANCiMjIyBMb2FkIHJhdyBkYXRhIGFuZCBkb3duc2FtcGxpbmcNCkhlcmUsIHdlIHVzZSBQQk1DIGRhdGFzZXQgYXMgYW4gZXhhbXBsZS48L2JyPg0KVGhlIGZyYWN0aW9uIG9mIHNhbXBsaW5nIGlzIHNldCB0byA1MCUgb2YgdGhlIG9yaWdpbmFsIGxpYnJhcnkgc2l6ZSBhY3Jvc3MgY2VsbHMuPC9icj4NCk9ubHkgMSByZXBsaWNhdGUgd2lsbCBiZSBnZW5lcmF0ZWQgaGVyZSBhcyBhbiBleGFtcGxlLjwvYnI+DQpPbmx5IGltcHV0ZWQgZ2VuZXMgd2lsbCBiZSBrZXB0IGZvciBjb21wYXJpc29uLg0KYGBge3J9DQp1c2VkX2RhdGFzZXRzID0gYygiTUVMQU5PTUEiLCAiU1NDT1JURVgiLCAiQ0JNQyIsICJQQk1DIikNCm1ldGhvZF9uYW1lcyA9IGMoIkRJU0MiLCAic2NWSSIsICJNQUdJQyIsICJEQ0EiLCAic2NTY29wZSIsICJEZWVwSW1wdXRlIiwgIlZJUEVSIiwgInNjSW1wdXRlIikNCm91dHB1dF9kaXIgPSAiLi9yZXN1bHRzL0lkZW50aWZpY2F0aW9uX29mX3RydWVfemVyb3MiDQpkaXIuY3JlYXRlKG91dHB1dF9kaXIsIHNob3dXYXJuaW5ncyA9IEYsIHJlY3Vyc2l2ZSA9IFQpDQpkYXRhX2xpc3QgPSBsaXN0KCkNCmZvcihpaSBpbiB1c2VkX2RhdGFzZXRzKXsNCiAgZGF0YV9saXN0W1tpaV1dID0gbGlzdCgpDQogIHJhd19kYXRhID0gcmVhZGg1X2xvb20ocGFzdGUwKCIuL2RhdGEvIiwgaWksICIvcmF3Lmxvb20iKSkNCiAgdnN0X2ZpbGUgPSBwYXN0ZTAob3V0cHV0X2RpciwgIi8iLCBpaSwgIl92c3RfZ2VuZS50c3YiKQ0KICBpZihmaWxlLmV4aXN0cyh2c3RfZmlsZSkpew0KICAgIGh2Z19pbmZvID0gcmVhZC50YWJsZSh2c3RfZmlsZSkNCiAgICBwcmludCgibG9hZCB2c3RfZmlsZSIpDQogIH1lbHNlew0KICAgIGh2Z19pbmZvID0gRmluZFZhcmlhYmxlRmVhdHVyZXNfdnN0X2J5X2dlbmVzKHJhd19kYXRhKQ0KICAgIGh2Z19pbmZvID0gaHZnX2luZm9bb3JkZXIoaHZnX2luZm8kdmFyaWFuY2Uuc3RhbmRhcmRpemVkLCBkZWNyZWFzaW5nID0gVCksIF0NCiAgICB3cml0ZS50YWJsZShodmdfaW5mbywgdnN0X2ZpbGUsIHNlcCA9ICJcdCIsIHF1b3RlID0gRiwgcm93Lm5hbWVzID0gVCwgY29sLm5hbWVzID0gVCkNCiAgfQ0KICBkc19kaXIgPSBwYXN0ZTAoIi4vZGF0YS8iLCBpaSwgIi9kc18wLjUvcjEiKQ0KICBvYnNlcnZlZF9kYXRhID0gcmVhZGg1X2xvb20ocGFzdGUwKGRzX2RpciwgIi9nZW5lX3NlbGVjdGlvbi5sb29tIikpDQogIGNvbXBhcmVkX2dlbmVzID0gcm93bmFtZXMob2JzZXJ2ZWRfZGF0YSkNCiAgdG9wXzEwMDBfZ2VuZXMgPSByb3duYW1lcyhodmdfaW5mbylbcm93bmFtZXMoaHZnX2luZm8pICVpbiUgY29tcGFyZWRfZ2VuZXNdWzE6MTAwMF0NCiAgcmF3X2RhdGEgPSByYXdfZGF0YVtjb21wYXJlZF9nZW5lcywgXQ0KICBmb3IoamogaW4gbWV0aG9kX25hbWVzKXsNCiAgICBpZihqaiA9PSAiRElTQyIpew0KICAgICAgaW1wdXRhdGlvbiA9IHJlYWRoNV9sb29tKHBhc3RlMChkc19kaXIsICIvIiwgamosICIubG9vbSIpKVtjb21wYXJlZF9nZW5lcywgXQ0KICAgIH1lbHNlew0KICAgICAgaW1wdXRhdGlvbiA9IHJlYWRoNV9pbXB1dGF0aW9uKHBhc3RlMChkc19kaXIsICIvIiwgamosICIuaGRmNSIpKVtjb21wYXJlZF9nZW5lcywgXQ0KICAgIH0NCiAgICBpbXB1dGF0aW9uX2NwMTBrID0gc3dlZXAoaW1wdXRhdGlvbiwgMiwgMTAwMDAgLyBjb2xTdW1zKGltcHV0YXRpb24pLCAiKiIpDQogICAgcmF3X3plcm8gPSByYXdfZGF0YSA9PSAwICYgb2JzZXJ2ZWRfZGF0YSA9PSAwDQogICAgaW5kdWNlZF96ZXJvID0gcmF3X2RhdGEgIT0gMCAmIG9ic2VydmVkX2RhdGEgPT0gMA0KICAgIGtlcHRfdmFsdWVzID0gcmF3X2RhdGEgIT0gMCAmIG9ic2VydmVkX2RhdGEgIT0gMA0KICAgIGRhdGFfbGlzdFtbaWldXVtbampdXSA9IGxpc3QocmF3X3plcm9faW1wdXRhdGlvbiA9IGltcHV0YXRpb25fY3AxMGtbcmF3X3plcm9dLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5kdWNlZF96ZXJvX2ltcHV0YXRpb24gPSBpbXB1dGF0aW9uX2NwMTBrW2luZHVjZWRfemVyb10sDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0b3BfcmF3X3plcm9faW1wdXRhdGlvbiA9IGltcHV0YXRpb25fY3AxMGtbdG9wXzEwMDBfZ2VuZXMsIF1bcmF3X3plcm9bdG9wXzEwMDBfZ2VuZXMsIF1dLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdG9wX2luZHVjZWRfemVyb19pbXB1dGF0aW9uID0gaW1wdXRhdGlvbl9jcDEwa1t0b3BfMTAwMF9nZW5lcywgXVtpbmR1Y2VkX3plcm9bdG9wXzEwMDBfZ2VuZXMsIF1dKQ0KICAgIGNhdCgiRmluaXNoOiAiLCBpaSwgIiAtICIsIGpqLCAiXG4iKQ0KICB9DQogIGNhdCgiRmluaXNoOiAiLCBpaSwgIlxuIikNCn0NCmBgYA0KRm9sbG93aW5nIHRoaXMgcGFwZXIgKFNBVkVSOiBnZW5lIGV4cHJlc3Npb24gcmVjb3ZlcnkgZm9yIHNpbmdsZS1jZWxsIFJOQSBzZXF1ZW5jaW5nLCBodHRwczovL3d3dy5uYXR1cmUuY29tL2FydGljbGVzL3M0MTU5Mi0wMTgtMDAzMy16KSwgd2UgZXZhbHVhdGUgdGhlIHBlcmZvcm1hbmNlIG9mIGRpZmZlcmVudCBpbXB1dGF0aW9uIG1ldGhvZHMgdG8gaW5kZW50aWZ5IHRydWUgemVyb3MuDQpgYGANCmBgYA0KIyMjIEFsbCBnZW5lcw0KYGBge3IgZmlnLmhlaWdodD01LCBmaWcud2lkdGg9OH0NCnBhcihtZnJvdyA9IGMoMSwgbGVuZ3RoKHVzZWRfZGF0YXNldHMpKSwgbWFyID0gYyg1LCAwLCAwLjUsIDApLCBvbWEgPSBjKDAsIDUsIDYsIDIpLCBtZ3AgPSBjKDMuNSwgMSwgMCksIGNleC5heGlzID0gMS4xLCBjZXgubGFiID0gMS41LCBmb250LmxhYiA9IDIsIGNleC5tYWluID0gMS41KQ0KbXRleHRfcG9zaXRpb24gPSBzZXEoZnJvbSA9IDAsIHRvID0gMSwgYnkgPSAxIC8gbGVuZ3RoKHVzZWRfZGF0YXNldHMpIC8gMilbc2VxKGxlbmd0aCh1c2VkX2RhdGFzZXRzKSkgKiAyXQ0KbmFtZXMobXRleHRfcG9zaXRpb24pID0gdXNlZF9kYXRhc2V0cw0KZm9yKGlpIGluIHVzZWRfZGF0YXNldHMpew0KICBtYXhfdmFsdWUgPSAwDQogIGZvcihqaiBpbiBtZXRob2RfbmFtZXMpew0KICAgIG1heF92YWx1ZSA9IG1heChjKG1heF92YWx1ZSwgZGF0YV9saXN0W1tpaV1dW1tqal1dW1sicmF3X3plcm9faW1wdXRhdGlvbiJdXSwgZGF0YV9saXN0W1tpaV1dW1tqal1dW1siaW5kdWNlZF96ZXJvX2ltcHV0YXRpb24iXV0pKQ0KICB9DQogIG4gPSAyIF4gKHJvdW5kKGxvZyhtYXhfdmFsdWUsIGJhc2UgPSAyKSkgKyA3KQ0KICBidyA9IChtYXhfdmFsdWUgKiAobiArIDEwKSkgLyAobiBeIDIpDQogIHRvID0gbWF4X3ZhbHVlICsgKGJ3ICogNSkNCiAgZnJvbSA9IC0oYncgKiA1KQ0KICB4X21heCA9IDANCiAgZm9yKGpqIGluIG1ldGhvZF9uYW1lcyl7DQogICAgZGF0YV9saXN0W1tpaV1dW1tqal1dW1sicmF3X3plcm9fZGVuc2l0eSJdXSA9IGRlbnNpdHkoZGF0YV9saXN0W1tpaV1dW1tqal1dW1sicmF3X3plcm9faW1wdXRhdGlvbiJdXSwgZnJvbSA9IGZyb20sIHRvID0gdG8sIG4gPSBuLCBidyA9IGJ3KQ0KICAgIGRhdGFfbGlzdFtbaWldXVtbampdXVtbImluZHVjZWRfemVyb19kZW5zaXR5Il1dID0gZGVuc2l0eShkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJpbmR1Y2VkX3plcm9faW1wdXRhdGlvbiJdXSwgZnJvbSA9IGZyb20sIHRvID0gdG8sIG4gPSBuLCBidyA9IGJ3KQ0KICAgIGRhdGFfbGlzdFtbaWldXVtbampdXVtbInlfbWF4Il1dID0gbWF4KGMoZGF0YV9saXN0W1tpaV1dW1tqal1dW1sicmF3X3plcm9fZGVuc2l0eSJdXSR5LCBkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJpbmR1Y2VkX3plcm9fZGVuc2l0eSJdXSR5KSkNCiAgICBjdXRvZmYgPSBkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJ5X21heCJdXSAqIDAuMDA1DQogICAgdGVzdF92ZWN0b3IgPSAhKGRhdGFfbGlzdFtbaWldXVtbampdXVtbInJhd196ZXJvX2RlbnNpdHkiXV0keSA8IGN1dG9mZiAmIGRhdGFfbGlzdFtbaWldXVtbampdXVtbImluZHVjZWRfemVyb19kZW5zaXR5Il1dJHkgPCBjdXRvZmYpDQogICAgZm9yKGtrIGluIHNlcShmcm9tID0gbGVuZ3RoKHRlc3RfdmVjdG9yKSwgdG8gPSAxKSl7DQogICAgICBpZih0ZXN0X3ZlY3Rvcltra10pew0KICAgICAgICB4X21heCA9IG1heChjKHhfbWF4LCBkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJyYXdfemVyb19kZW5zaXR5Il1dJHhba2sgKyAxXSkpDQogICAgICAgIGJyZWFrKCkNCiAgICAgIH0NCiAgICB9DQogIH0NCiAgZGF0YV9saXN0W1tpaV1dW1sieF9tYXgiXV0gPSB4X21heA0KICBjYXQoIkZpbmlzaDogIiwgaWksICJcbiIpDQp9DQpmb3IoaWkgaW4gbWV0aG9kX25hbWVzKXsNCiAgZm9yKGpqIGluIHVzZWRfZGF0YXNldHMpew0KICAgIHBsb3QoMCwgdHlwZSA9ICJuIiwgeGxpbSA9IGMoLW1pbihjKDEsIGRhdGFfbGlzdFtbampdXVtbInhfbWF4Il1dICogMC4wNSkpLCBkYXRhX2xpc3RbW2pqXV1bWyJ4X21heCJdXSksIHlsaW0gPSBjKDAsIGRhdGFfbGlzdFtbampdXVtbaWldXVtbInlfbWF4Il1dKSwgYXhlcyA9IEZBTFNFLCBhbm4gPSBGQUxTRSwgZnJhbWUucGxvdCA9IFRSVUUpDQogICAgbGluZXMoZGF0YV9saXN0W1tqal1dW1tpaV1dW1sicmF3X3plcm9fZGVuc2l0eSJdXSwgY29sID0gImJsYWNrIiwgbHdkID0gMikNCiAgICBsaW5lcyhkYXRhX2xpc3RbW2pqXV1bW2lpXV1bWyJpbmR1Y2VkX3plcm9fZGVuc2l0eSJdXSwgY29sID0gInJlZCIsIGx3ZCA9IDIpDQogICAgYXhpcygxKQ0KICAgIG10ZXh0KGpqLCBvdXRlciA9IFRSVUUsIGNleCA9IDEuMiwgZm9udCA9IDIsIGxpbmUgPSAwLjUsIGF0ID0gbXRleHRfcG9zaXRpb25bampdKQ0KICAgIGNhdCgiRmluaXNoOiAiLCBpaSwgIiAtICIsIGpqLCAiXG4iKQ0KICB9DQogIG10ZXh0KHBhc3RlMChpaSwgIiAtIEFsbCBnZW5lcyIpLCBvdXRlciA9IFRSVUUsIGNleCA9IDEuNCwgZm9udCA9IDIsIGxpbmUgPSAzKQ0KICBsZWdlbmQoInRvcHJpZ2h0IiwgYygiUmF3IHplcm8iLCAiU2FtcGxlZCB6ZXJvIiksIGx0eSA9IDEsIGNvbCA9IGMoImJsYWNrIiwgInJlZCIpLCBsd2QgPSAyKQ0KfQ0KYGBgDQojIyMgVG9wIDEwMDAgZ2VuZXMNCmBgYHtyIGZpZy5oZWlnaHQ9NSwgZmlnLndpZHRoPTh9DQpwYXIobWZyb3cgPSBjKDEsIGxlbmd0aCh1c2VkX2RhdGFzZXRzKSksIG1hciA9IGMoNSwgMCwgMC41LCAwKSwgb21hID0gYygwLCA1LCA2LCAyKSwgbWdwID0gYygzLjUsIDEsIDApLCBjZXguYXhpcyA9IDEuMSwgY2V4LmxhYiA9IDEuNSwgZm9udC5sYWIgPSAyLCBjZXgubWFpbiA9IDEuNSkNCm10ZXh0X3Bvc2l0aW9uID0gc2VxKGZyb20gPSAwLCB0byA9IDEsIGJ5ID0gMSAvIGxlbmd0aCh1c2VkX2RhdGFzZXRzKSAvIDIpW3NlcShsZW5ndGgodXNlZF9kYXRhc2V0cykpICogMl0NCm5hbWVzKG10ZXh0X3Bvc2l0aW9uKSA9IHVzZWRfZGF0YXNldHMNCmZvcihpaSBpbiB1c2VkX2RhdGFzZXRzKXsNCiAgbWF4X3ZhbHVlID0gMA0KICBmb3IoamogaW4gbWV0aG9kX25hbWVzKXsNCiAgICBtYXhfdmFsdWUgPSBtYXgoYyhtYXhfdmFsdWUsIGRhdGFfbGlzdFtbaWldXVtbampdXVtbInRvcF9yYXdfemVyb19pbXB1dGF0aW9uIl1dLCBkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJ0b3BfaW5kdWNlZF96ZXJvX2ltcHV0YXRpb24iXV0pKQ0KICB9DQogIG4gPSAyIF4gKHJvdW5kKGxvZyhtYXhfdmFsdWUsIGJhc2UgPSAyKSkgKyA3KQ0KICBidyA9IChtYXhfdmFsdWUgKiAobiArIDEwKSkgLyAobiBeIDIpDQogIHRvID0gbWF4X3ZhbHVlICsgKGJ3ICogNSkNCiAgZnJvbSA9IC0oYncgKiA1KQ0KICB4X21heCA9IDANCiAgZm9yKGpqIGluIG1ldGhvZF9uYW1lcyl7DQogICAgZGF0YV9saXN0W1tpaV1dW1tqal1dW1sidG9wX3Jhd196ZXJvX2RlbnNpdHkiXV0gPSBkZW5zaXR5KGRhdGFfbGlzdFtbaWldXVtbampdXVtbInRvcF9yYXdfemVyb19pbXB1dGF0aW9uIl1dLCBmcm9tID0gZnJvbSwgdG8gPSB0bywgbiA9IG4sIGJ3ID0gYncpDQogICAgZGF0YV9saXN0W1tpaV1dW1tqal1dW1sidG9wX2luZHVjZWRfemVyb19kZW5zaXR5Il1dID0gZGVuc2l0eShkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJ0b3BfaW5kdWNlZF96ZXJvX2ltcHV0YXRpb24iXV0sIGZyb20gPSBmcm9tLCB0byA9IHRvLCBuID0gbiwgYncgPSBidykNCiAgICBkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJ0b3BfeV9tYXgiXV0gPSBtYXgoYyhkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJ0b3BfcmF3X3plcm9fZGVuc2l0eSJdXSR5LCBkYXRhX2xpc3RbW2lpXV1bW2pqXV1bWyJ0b3BfaW5kdWNlZF96ZXJvX2RlbnNpdHkiXV0keSkpDQogICAgY3V0b2ZmID0gZGF0YV9saXN0W1tpaV1dW1tqal1dW1sidG9wX3lfbWF4Il1dICogMC4wMDUNCiAgICB0ZXN0X3ZlY3RvciA9ICEoZGF0YV9saXN0W1tpaV1dW1tqal1dW1sidG9wX3Jhd196ZXJvX2RlbnNpdHkiXV0keSA8IGN1dG9mZiAmIGRhdGFfbGlzdFtbaWldXVtbampdXVtbInRvcF9pbmR1Y2VkX3plcm9fZGVuc2l0eSJdXSR5IDwgY3V0b2ZmKQ0KICAgIGZvcihrayBpbiBzZXEoZnJvbSA9IGxlbmd0aCh0ZXN0X3ZlY3RvciksIHRvID0gMSkpew0KICAgICAgaWYodGVzdF92ZWN0b3Jba2tdKXsNCiAgICAgICAgeF9tYXggPSBtYXgoYyh4X21heCwgZGF0YV9saXN0W1tpaV1dW1tqal1dW1sidG9wX3Jhd196ZXJvX2RlbnNpdHkiXV0keFtrayArIDFdKSkNCiAgICAgICAgYnJlYWsoKQ0KICAgICAgfQ0KICAgIH0NCiAgfQ0KICBkYXRhX2xpc3RbW2lpXV1bWyJ0b3BfeF9tYXgiXV0gPSB4X21heA0KICBjYXQoIkZpbmlzaDogIiwgaWksICJcbiIpDQp9DQpmb3IoaWkgaW4gbWV0aG9kX25hbWVzKXsNCiAgZm9yKGpqIGluIHVzZWRfZGF0YXNldHMpew0KICAgIHBsb3QoMCwgdHlwZSA9ICJuIiwgeGxpbSA9IGMoLW1pbihjKDEsIGRhdGFfbGlzdFtbampdXVtbInRvcF94X21heCJdXSAqIDAuMDUpKSwgZGF0YV9saXN0W1tqal1dW1sidG9wX3hfbWF4Il1dKSwgeWxpbSA9IGMoMCwgZGF0YV9saXN0W1tqal1dW1tpaV1dW1sidG9wX3lfbWF4Il1dKSwgYXhlcyA9IEZBTFNFLCBhbm4gPSBGQUxTRSwgZnJhbWUucGxvdCA9IFRSVUUpDQogICAgbGluZXMoZGF0YV9saXN0W1tqal1dW1tpaV1dW1sidG9wX3Jhd196ZXJvX2RlbnNpdHkiXV0sIGNvbCA9ICJibGFjayIsIGx3ZCA9IDIpDQogICAgbGluZXMoZGF0YV9saXN0W1tqal1dW1tpaV1dW1sidG9wX2luZHVjZWRfemVyb19kZW5zaXR5Il1dLCBjb2wgPSAicmVkIiwgbHdkID0gMikNCiAgICBheGlzKDEpDQogICAgbXRleHQoamosIG91dGVyID0gVFJVRSwgY2V4ID0gMS4yLCBmb250ID0gMiwgbGluZSA9IDAuNSwgYXQgPSBtdGV4dF9wb3NpdGlvbltqal0pDQogICAgY2F0KCJGaW5pc2g6ICIsIGlpLCAiIC0gIiwgamosICJcbiIpDQogIH0NCiAgbXRleHQocGFzdGUwKGlpLCAiIC0gVG9wIDEwMDAgZ2VuZXMiKSwgb3V0ZXIgPSBUUlVFLCBjZXggPSAxLjQsIGZvbnQgPSAyLCBsaW5lID0gMykNCiAgbGVnZW5kKCJ0b3ByaWdodCIsIGMoIlJhdyB6ZXJvIiwgIlNhbXBsZWQgemVybyIpLCBsdHkgPSAxLCBjb2wgPSBjKCJibGFjayIsICJyZWQiKSwgbHdkID0gMikNCn0NCmBgYA0K