1 Summary

This R Notebook generates figures for Platform Effect Demonstration.

  1. Inputs:

  2. Outputs:

    • Figure. UMAP of STARmap and scRNA-seq reference cells before and after CVAE transforming, as well as the UMAP of latent embeddings of those cells
    • Figure. Boxplot of performance on simulated data

2 Version

version[['version.string']]
[1] "R version 4.2.2 Patched (2022-11-10 r83330)"
print(sprintf('Package %s version: %s', 'ggplot2', packageVersion('ggplot2')))
[1] "Package ggplot2 version: 3.4.2"
print(sprintf('Package %s version: %s', 'ggpubr', packageVersion('ggpubr')))
[1] "Package ggpubr version: 0.6.0"
print(sprintf('Package %s version: %s', 'philentropy', packageVersion('philentropy'))) # JSD function
[1] "Package philentropy version: 0.7.0"

3 Read relevant files

3.1 Read STARmap cell annotation

file_name = file.path(home.dir, 'STARmap_cell_celltype.csv')
starmap_cell_anno = read.csv(file_name, row.names = 1, check.names = F, stringsAsFactors = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/STARmap_cell_celltype.csv"
print(sprintf('total %d cells', nrow(starmap_cell_anno)))
[1] "total 2002 cells"
table(starmap_cell_anno$celltype)

Astro eL2/3   eL4   eL5   eL6  Endo Micro Oligo PVALB   Smc   SST   VIP 
  259   292   327   110   368   134    69   278    61    42    33    29 

generate the truth cell type proportion.

celltype_order = c("Astro", "eL2/3", "eL4", "eL5", "eL6", "Endo", "Micro", "Oligo", "PVALB", "Smc", "SST", "VIP")
truth = data.frame(matrix(0, nrow=nrow(starmap_cell_anno), ncol=length(celltype_order)))
colnames(truth) = celltype_order
row.names(truth) = row.names(starmap_cell_anno)

for (i in 1:nrow(starmap_cell_anno)) {
  truth[i, starmap_cell_anno[i, 'celltype']] = 1
}

3.2 Read cell type annotation of external reference

file_name = file.path(home.dir, 'ref_scRNA_cell_celltype.csv')
ref_cell_anno = read.csv(file_name, row.names = 1, check.names = F, stringsAsFactors = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/ref_scRNA_cell_celltype.csv"
print(sprintf('total %d cells', nrow(ref_cell_anno)))
[1] "total 11835 cells"
table(ref_cell_anno$celltype)

Astro eL2/3   eL4   eL5   eL6  Endo Micro Oligo PVALB   Smc   SST   VIP 
  361   968  1350  1679  2773    76    44    61  1211    55  1567  1690 

Combine cell type annotations of STARmap cells and scRNA-seq cells.

starmap_cell_anno$dataset = 'Spatial'
ref_cell_anno$dataset = 'Reference'

comb_cell_anno = rbind(starmap_cell_anno, ref_cell_anno)

3.3 Read estimated cell type proportions

file_name = file.path(home.dir, 'PlatEffDemo_all_results.rds')
all_res = readRDS(file_name)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/PlatEffDemo_all_results.rds"

Check the order of spots and cell types are consistent before performance evaluation.

for (method_name in names(all_res)) {
  stopifnot(all(row.names(all_res[[method_name]]) == row.names(truth)))
  stopifnot(all(colnames(all_res[[method_name]]) == colnames(truth)))
}

Check whether negative values of estimated cell type proportions exist, as negative values may cause error in JSD calculation and got NaN. Replace them as 0.

for (method_name in names(all_res)) {
  tmp_df = all_res[[method_name]]
  for (i in 1:nrow(tmp_df)) {
    for (j in 1:ncol(tmp_df)) {
      if (tmp_df[i, j] < 0) {
        print(sprintf('%s result: row %d (%s) column %d (%s) has negative value %g', method_name, i, row.names(tmp_df)[i], j, colnames(tmp_df)[j], tmp_df[i, j]))
        # replace them with 0
        all_res[[method_name]][i, j] = 0
      }
    }
  }
}

3.4 Read UMAP coordinates before CVAE transformation

UMAP coordinates for gene expression of spatial spots and scRNA-seq reference cells are in file UMAP_coordinates_raw_input.csv.

file_name = file.path(home.dir, 'PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis', 'diagnosis', 'raw_input_data', 'UMAP_coordinates_raw_input.csv')
umap_before = read.csv(file_name, row.names = 1, check.names = F, stringsAsFactors = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis/diagnosis/raw_input_data/UMAP_coordinates_raw_input.csv"
print(sprintf('total %d rows', nrow(umap_before)))
[1] "total 13849 rows"

Add the cell type annotation.

umap_before = merge(umap_before, comb_cell_anno, by = 'row.names')

3.5 Read UMAP coordinates in CVAE latent space

UMAP coordinates for embedding in CVAE latent space of spatial spots and scRNA-seq reference cells are in file UMAP_coordinates_latent_mu_embedding_spatial_spots.csv and UMAP_coordinates_latent_mu_embedding_scRNA-seq_cells.csv.

file_name = file.path(home.dir, 'PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis', 'diagnosis', 'CVAE_latent_space', 'UMAP_coordinates_latent_mu_embedding_spatial_spots.csv')
umap_latent_spatial = read.csv(file_name, row.names = 1, check.names = F, stringsAsFactors = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis/diagnosis/CVAE_latent_space/UMAP_coordinates_latent_mu_embedding_spatial_spots.csv"
file_name = file.path(home.dir, 'PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis', 'diagnosis', 'CVAE_latent_space', 'UMAP_coordinates_latent_mu_embedding_scRNA-seq_cells.csv')
umap_latent_ref = read.csv(file_name, row.names = 1, check.names = F, stringsAsFactors = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis/diagnosis/CVAE_latent_space/UMAP_coordinates_latent_mu_embedding_scRNA-seq_cells.csv"
umap_latent = rbind(umap_latent_spatial, umap_latent_ref)
print(sprintf('total %d rows', nrow(umap_latent)))
[1] "total 51910 rows"

Add the cell type annotation.

umap_latent = merge(umap_latent, comb_cell_anno, by = 'row.names')

3.6 Read UMAP coordinates after CVAE transformation

UMAP coordinates for gene expression of spatial spots and scRNA-seq reference cells are in file UMAP_coordinates_decoded_value.csv.

file_name = file.path(home.dir, 'PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis', 'diagnosis', 'CVAE_transformed_data', 'UMAP_coordinates_decoded_value.csv')
umap_after = read.csv(file_name, row.names = 1, check.names = F, stringsAsFactors = F)
print(sprintf('load data from %s', file_name))
[1] "load data from /home/hill103/Documents/Spatial/PlatEffDemo/PlatEffDemo_ref_scRNA_SDePER_WITH_CVAE_diagnosis/diagnosis/CVAE_transformed_data/UMAP_coordinates_decoded_value.csv"
print(sprintf('total %d rows', nrow(umap_after)))
[1] "total 51922 rows"

Add the cell type annotation.

umap_after = merge(umap_after, comb_cell_anno, by = 'row.names')

4 Evaluate performance of cell type deconvolution methods

4.1 Calculate spot-wise performance of all methods

5 performance measurements:

  • root mean square error (RMSE): quantifies the overall estimation accuracy
  • Jensen-Shannon Divergence (JSD): assesses similarity between the estimated cell type distribution and ground-truth per spot
  • Pearson’s correlation coefficient: measures the similarity of estimation to ground-truth
  • false discovery rate (FDR): measures how many cell types were falsely predicted to be present
  • false negative rate (FNR): measures how many presented cell types were falsely predicted to be not present
binaryPredEvaluation = function(truth, pred) {
  # Given an array of truth and predictions (either 0 or 1), calculate confusion matrix
  # convert to factors to ensure get a full 2*2 confusion matrix
  truth_factor = factor(truth, levels = c(0, 1))
  pred_factor = factor(pred, levels = c(0, 1))
  # Generate confusion matrix
  conf_matrix = table(Actual = truth_factor, Predicted = pred_factor)
  # Extract elements of the confusion matrix
  TP = conf_matrix[2, 2]
  FP = conf_matrix[1, 2]
  FN = conf_matrix[2, 1]
  TN = conf_matrix[1, 1]
  # Calculate FDR (False Discovery Rate)
  FDR = FP / (TP + FP)
  # Calculate FNR (False Negative Rate)
  FNR = FN / (TP + FN)
  return(c(FDR, FNR))
}

calcPerformance = function(truth, pred) {
  # calculate RMSE, JSD, correlation and FDR for each row
  # inputs are matrix with rows as spots and columns as cell types, order has been checked to be consistent
  stopifnot(all(row.names(truth) == row.names(pred)))
  stopifnot(all(colnames(truth) == colnames(pred)))
  
  # binary cell type proportions (0:absent; 1:present)
  truth_binary = truth != 0
  pred_binary = pred != 0
  # in-place conversion from bool to 0/1 while keeping dimensions, row names and column names, as `as.numeric()` will "flattern" the original matrix
  truth_binary[] = as.numeric(truth_binary)
  pred_binary[] = as.numeric(pred_binary)
  
  perform_df = data.frame(matrix(ncol=5, nrow=0))
  colnames(perform_df) = c('RMSE', 'JSD', 'Pearson', 'FDR', 'FNR')
  
  for (i in 1:nrow(truth)) {
    RMSE = sqrt(mean((truth[i,] - pred[i,]) ^ 2))
    if (sum(pred[i,])>0 & sum(truth[i,])>0) {
      JSD = philentropy::JSD(rbind(truth[i,], pred[i,]), unit = 'log2', est.prob = 'empirical')
    } else {
      JSD = 1
    }
    Pearson = cor.test(truth[i,], pred[i,])$estimate
    tmp = binaryPredEvaluation(truth_binary[i,], pred_binary[i,])
    FDR = tmp[1]
    FNR = tmp[2]
    
    perform_df[nrow(perform_df)+1, ] = c(RMSE, JSD, Pearson, FDR, FNR)
  }
  
  # also record spot names
  stopifnot(nrow(perform_df) == nrow(truth))
  perform_df['Spot'] = row.names(truth)
  
  return(perform_df)
}


all_perform = list()

for (method_name in names(all_res)) {
  all_perform[[method_name]] = calcPerformance(as.matrix(truth), as.matrix(all_res[[method_name]]))
}

4.2 Summary spot-wise performance into method-wise

perform_raw_df = data.frame(matrix(ncol=10, nrow=0))
colnames(perform_raw_df) = c('Dataset', 'Scenario', 'Method', 'Reference', 'Spot', 'RMSE', 'JSD', 'Pearson', 'FDR', 'FNR')

# calculate median performance across all spatial spots for all methods
perform_median_df = data.frame(matrix(ncol=9, nrow=0))
colnames(perform_median_df) = c('Dataset', 'Scenario', 'Method', 'Reference', 'median_RMSE', 'median_JSD', 'median_Pearson', 'median_FDR', 'median_FNR')

this_dataset = 'STARmap-based'
this_scenario = 'Scenario 1'
this_ref = 'External'
      
for (method_name in names(all_perform)) {
  tmp_df = all_perform[[method_name]]
  tmp_df['Dataset'] = this_dataset
  tmp_df['Scenario'] = this_scenario
  tmp_df['Method'] = method_name
  tmp_df['Reference'] = this_ref
    
  perform_raw_df = rbind(perform_raw_df, tmp_df[, c('Dataset', 'Scenario', 'Method', 'Reference', 'Spot', 'RMSE', 'JSD', 'Pearson', 'FDR', 'FNR')])
    
  perform_median_df[nrow(perform_median_df)+1, ] = c(this_dataset, this_scenario, method_name, this_ref,
                                                     round(median(tmp_df$RMSE), 3),
                                                     round(median(tmp_df$JSD), 3),
                                                     round(median(tmp_df$Pearson), 3),
                                                     round(median(tmp_df$FDR), 3),
                                                     round(median(tmp_df$FNR), 3))
}

# set method column as factors
perform_raw_df['Method'] = factor(perform_raw_df$Method, levels = c("SDePER", "GLRM", "NO_PlatEffRmv"))

perform_median_df[, c('Dataset', 'Scenario', 'Method', 'Reference', 'median_RMSE', 'median_JSD', 'median_Pearson', 'median_FDR', 'median_FNR')]

5 Draw figures

5.1 UMAP of spatial spots and reference cells before CVAE transformation

ggplot(umap_before, aes(x=UMAP1, y=UMAP2, color=celltype)) +
  geom_point(shape=20, size=0.5) +
  theme_classic() +
  scale_color_manual(values = my_color) +
  facet_grid(~dataset) +
  theme(legend.title = element_blank(), strip.text = element_text(size=14)) +
  guides(color = guide_legend(override.aes = list(size = 3)))

5.2 UMAP of spatial spots and reference cells in CVAE latent space

ggplot(umap_latent, aes(x=UMAP1, y=UMAP2, color=celltype)) +
  geom_point(shape=20, size=0.5) +
  theme_classic() +
  scale_color_manual(values = my_color) +
  facet_grid(~dataset) +
  theme(legend.title = element_blank(), strip.text = element_text(size=14)) +
  guides(color = guide_legend(override.aes = list(size = 3)))

5.3 UMAP of spatial spots and reference cells after CVAE transformation

ggplot(umap_after, aes(x=UMAP1, y=UMAP2, color=celltype)) +
  geom_point(shape=20, size=0.5) +
  theme_classic() +
  scale_color_manual(values = my_color) +
  facet_grid(~dataset) +
  theme(legend.title = element_blank(), strip.text = element_text(size=14)) +
  guides(color = guide_legend(override.aes = list(size = 3)))

5.4 Boxplot of performance of all methods

plot_df = perform_raw_df

g_list = list()

for (perform_ind in c('RMSE', 'Pearson', 'JSD', 'FDR')) {
  g_list[[perform_ind]] = ggplot(plot_df, aes(x=Method, y=.data[[perform_ind]], fill=Method)) +
                            geom_boxplot(position=position_dodge(), outlier.shape=NA) +
                            scale_fill_manual(values=method_color, labels=c('SDePER'='SDePER (baseline)','GLRM'='GLRM (NO CVAE)', 'NO_PlatEffRmv'='NO PlatEffRmv')) +
                            theme_classic() +
                            theme(axis.text = element_text(color="black"),
                                  axis.ticks.x = element_blank(),
                                  axis.text.x = element_blank(),
                                  axis.title.x = element_blank(),
                                  legend.title = element_blank())
                            
}

g_list[['Pearson']] = g_list[['Pearson']] + geom_hline(yintercept=0, color="red", linetype="dashed")

ggpubr::ggarrange(plotlist=g_list, ncol=4, nrow=1, common.legend=TRUE, legend="bottom", align = 'hv')

5.5 Addtional boxplot for FNR

ggplot(plot_df, aes(x=Method, y=FNR, fill=Method)) +
  geom_boxplot(position=position_dodge(), outlier.shape=NA) +
  scale_fill_manual(values=method_color, labels=c('SDePER'='SDePER (baseline)','GLRM'='GLRM (NO CVAE)', 'NO_PlatEffRmv'='NO PlatEffRmv')) +
  theme_classic() +
  theme(axis.text = element_text(color="black"),
        axis.ticks.x = element_blank(),
        axis.text.x = element_blank(),
        axis.title.x = element_blank(),
        legend.title = element_blank())

LS0tCnRpdGxlOiAiR2VuZXJhdGUgZmlndXJlcyBpbiBQbGF0Zm9ybSBFZmZlY3QgRGVtb25zdHJhdGlvbiIKYXV0aG9yOiAiTmluZ3NoYW4gTGkiCmRhdGU6ICIyMDI0LzA3LzE0IgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6CiAgICBjb2RlX2ZvbGRpbmc6IGhpZGUKICAgIGhpZ2hsaWdodDogdGFuZ28KICAgIG51bWJlcl9zZWN0aW9uczogeWVzCiAgICB0aGVtZTogdW5pdGVkCiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiA2CiAgICB0b2NfZmxvYXQ6IHllcwotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUsIGV2YWwgPSBUUlVFLCB3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSwgcmVzdWx0cz0naG9sZCcsIGZpZy53aWR0aCA9IDcsIGZpZy5oZWlnaHQgPSA1LCBkcGkgPSAzMDApCgoKIyB1c2UgZ2dwdWJyIHBhY2thZ2UgKGh0dHA6Ly93d3cuc3RoZGEuY29tL2VuZ2xpc2gvYXJ0aWNsZXMvMjQtZ2dwdWJyLXB1YmxpY2F0aW9uLXJlYWR5LXBsb3RzLzgxLWdncGxvdDItZWFzeS13YXktdG8tbWl4LW11bHRpcGxlLWdyYXBocy1vbi10aGUtc2FtZS1wYWdlLykKbGlicmFyeShkcGx5cikKbGlicmFyeShnZ3Bsb3QyKQoKCmAlbm90aW4lYCA9IE5lZ2F0ZShgJWluJWApCgpzZXQuc2VlZCgxKQoKaG9tZS5kaXIgPSAnL2hvbWUvaGlsbDEwMy9Eb2N1bWVudHMvU3BhdGlhbC9QbGF0RWZmRGVtbycKc2F2ZV9maWxlID0gRkFMU0UKCm15X2NvbG9yID0gYygnI2U2MTk0YicsICcjM2NiNDRiJywgJyNmZmUxMTknLCAnIzQzNjNkOCcsICcjZjU4MjMxJywgJyM5MTFlYjQnLCAnIzQ2ZjBmMCcsICcjZjAzMmU2JywgJyNiY2Y2MGMnLCAnI2ZhYmViZScsICcjMDA4MDgwJywgJyNlNmJlZmYnLCAnIzlhNjMyNCcsICcjZmZmYWM4JywgJyM4MDAwMDAnLCAnI2FhZmZjMycsICcjODA4MDAwJywgJyNmZmQ4YjEnLCAnIzAwMDA3NScsICcjODA4MDgwJywgJyNmZmZmZmYnLCAnIzAwMDAwMCcpCm1ldGhvZF9jb2xvciA9IGMoIlNEZVBFUiI9JyNlNjE5NGInLCAiR0xSTSI9JyNmMDMyZTYnLCAiTk9fUGxhdEVmZlJtdiI9JyM4MDgwMDAnKQpgYGAKCgojIFN1bW1hcnkKClRoaXMgUiBOb3RlYm9vayBnZW5lcmF0ZXMgZmlndXJlcyBmb3IgKipQbGF0Zm9ybSBFZmZlY3QgRGVtb25zdHJhdGlvbioqLgoKMS4gICoqSW5wdXRzKio6CgogICAgKiBbYGFsbF9yZXN1bHRzLnJkc2BdKGh0dHBzOi8vZ2l0aHViLmNvbS9hejdqaDIvU0RlUEVSX0FuYWx5c2lzL2Jsb2IvbWFpbi9QbGF0RWZmRGVtby9QbGF0RWZmRGVtb19hbGxfcmVzdWx0cy5yZHMpOiBjZWxsIHR5cGUgZGVjb252b2x1dGlvbiByZXN1bHRzLgogICAgKiBbYFBsYXRFZmZEZW1vX3JlZl9zY1JOQV9TRGVQRVJfV0lUSF9DVkFFX2RpYWdub3Npcy50YXJgXShodHRwczovL2dpdGh1Yi5jb20vYXo3amgyL1NEZVBFUl9BbmFseXNpcy9ibG9iL21haW4vUGxhdEVmZkRlbW8vUGxhdEVmZkRlbW9fcmVmX3NjUk5BX1NEZVBFUl9XSVRIX0NWQUVfZGlhZ25vc2lzLnRhcik6IENvbXByZXNzZWQgZmlsZSBpbmNsdWRpbmcgYWxsIGRpYWdub3N0aWMgcGxvdHMgZnJvbSBydW5uaW5nIFNEZVBFUiBpbiB0aGlzIHNpbXVsYXRpb24uCiAgICAqIFtgU1RBUm1hcF9jZWxsX2NlbGx0eXBlLmNzdmBdKGh0dHBzOi8vZ2l0aHViLmNvbS9hejdqaDIvU0RlUEVSX0FuYWx5c2lzL2Jsb2IvbWFpbi9TaW11bGF0aW9uL1J1bl9TRGVQRVJfb25fc2ltdWxhdGlvbl9kYXRhL1NjZW5hcmlvXzEvcmVmX3NwYXRpYWwvU1RBUm1hcF9jZWxsX2NlbGx0eXBlLmNzdik6IGNlbGwgdHlwZSBhbm5vdGF0aW9uIG9mIGFsbCAyLDAwMiBTVEFSbWFwIGNlbGxzLgogICAgKiBbYHJlZl9zY1JOQV9jZWxsX2NlbGx0eXBlLmNzdmBdKGh0dHBzOi8vZ2l0aHViLmNvbS9hejdqaDIvU0RlUEVSX0FuYWx5c2lzL2Jsb2IvbWFpbi9TaW11bGF0aW9uL1J1bl9TRGVQRVJfb25fc2ltdWxhdGlvbl9kYXRhL1NjZW5hcmlvXzEvcmVmX3NjUk5BX3NlcS9yZWZfc2NSTkFfY2VsbF9jZWxsdHlwZS5jc3YpOiBjZWxsIHR5cGUgYW5ub3RhdGlvbiBvZiBjZWxscyBpbiBleHRlcm5hbCBzY1JOQS1zZXEgcmVmZXJlbmNlIGRhdGEuCgoyLiAgKipPdXRwdXRzKio6CgogICAgKiBGaWd1cmUuIFVNQVAgb2YgU1RBUm1hcCBhbmQgc2NSTkEtc2VxIHJlZmVyZW5jZSBjZWxscyBiZWZvcmUgYW5kIGFmdGVyIENWQUUgdHJhbnNmb3JtaW5nLCBhcyB3ZWxsIGFzIHRoZSBVTUFQIG9mIGxhdGVudCBlbWJlZGRpbmdzIG9mIHRob3NlIGNlbGxzCiAgICAqIEZpZ3VyZS4gQm94cGxvdCBvZiBwZXJmb3JtYW5jZSBvbiBzaW11bGF0ZWQgZGF0YQoKCgojIFZlcnNpb24KCmBgYHtyfQp2ZXJzaW9uW1sndmVyc2lvbi5zdHJpbmcnXV0KcHJpbnQoc3ByaW50ZignUGFja2FnZSAlcyB2ZXJzaW9uOiAlcycsICdnZ3Bsb3QyJywgcGFja2FnZVZlcnNpb24oJ2dncGxvdDInKSkpCnByaW50KHNwcmludGYoJ1BhY2thZ2UgJXMgdmVyc2lvbjogJXMnLCAnZ2dwdWJyJywgcGFja2FnZVZlcnNpb24oJ2dncHVicicpKSkKcHJpbnQoc3ByaW50ZignUGFja2FnZSAlcyB2ZXJzaW9uOiAlcycsICdwaGlsZW50cm9weScsIHBhY2thZ2VWZXJzaW9uKCdwaGlsZW50cm9weScpKSkgIyBKU0QgZnVuY3Rpb24KYGBgCgojIFJlYWQgcmVsZXZhbnQgZmlsZXMKCiMjIFJlYWQgU1RBUm1hcCBjZWxsIGFubm90YXRpb24KCmBgYHtyfQpmaWxlX25hbWUgPSBmaWxlLnBhdGgoaG9tZS5kaXIsICdTVEFSbWFwX2NlbGxfY2VsbHR5cGUuY3N2JykKc3Rhcm1hcF9jZWxsX2Fubm8gPSByZWFkLmNzdihmaWxlX25hbWUsIHJvdy5uYW1lcyA9IDEsIGNoZWNrLm5hbWVzID0gRiwgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCnByaW50KHNwcmludGYoJ2xvYWQgZGF0YSBmcm9tICVzJywgZmlsZV9uYW1lKSkKcHJpbnQoc3ByaW50ZigndG90YWwgJWQgY2VsbHMnLCBucm93KHN0YXJtYXBfY2VsbF9hbm5vKSkpCnRhYmxlKHN0YXJtYXBfY2VsbF9hbm5vJGNlbGx0eXBlKQpgYGAKCmdlbmVyYXRlIHRoZSB0cnV0aCBjZWxsIHR5cGUgcHJvcG9ydGlvbi4KCmBgYHtyfQpjZWxsdHlwZV9vcmRlciA9IGMoIkFzdHJvIiwgImVMMi8zIiwgImVMNCIsICJlTDUiLCAiZUw2IiwgIkVuZG8iLCAiTWljcm8iLCAiT2xpZ28iLCAiUFZBTEIiLCAiU21jIiwgIlNTVCIsICJWSVAiKQp0cnV0aCA9IGRhdGEuZnJhbWUobWF0cml4KDAsIG5yb3c9bnJvdyhzdGFybWFwX2NlbGxfYW5ubyksIG5jb2w9bGVuZ3RoKGNlbGx0eXBlX29yZGVyKSkpCmNvbG5hbWVzKHRydXRoKSA9IGNlbGx0eXBlX29yZGVyCnJvdy5uYW1lcyh0cnV0aCkgPSByb3cubmFtZXMoc3Rhcm1hcF9jZWxsX2Fubm8pCgpmb3IgKGkgaW4gMTpucm93KHN0YXJtYXBfY2VsbF9hbm5vKSkgewogIHRydXRoW2ksIHN0YXJtYXBfY2VsbF9hbm5vW2ksICdjZWxsdHlwZSddXSA9IDEKfQpgYGAKCgojIyBSZWFkIGNlbGwgdHlwZSBhbm5vdGF0aW9uIG9mIGV4dGVybmFsIHJlZmVyZW5jZQoKYGBge3J9CmZpbGVfbmFtZSA9IGZpbGUucGF0aChob21lLmRpciwgJ3JlZl9zY1JOQV9jZWxsX2NlbGx0eXBlLmNzdicpCnJlZl9jZWxsX2Fubm8gPSByZWFkLmNzdihmaWxlX25hbWUsIHJvdy5uYW1lcyA9IDEsIGNoZWNrLm5hbWVzID0gRiwgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCnByaW50KHNwcmludGYoJ2xvYWQgZGF0YSBmcm9tICVzJywgZmlsZV9uYW1lKSkKcHJpbnQoc3ByaW50ZigndG90YWwgJWQgY2VsbHMnLCBucm93KHJlZl9jZWxsX2Fubm8pKSkKdGFibGUocmVmX2NlbGxfYW5ubyRjZWxsdHlwZSkKYGBgCgpDb21iaW5lIGNlbGwgdHlwZSBhbm5vdGF0aW9ucyBvZiBTVEFSbWFwIGNlbGxzIGFuZCBzY1JOQS1zZXEgY2VsbHMuCgpgYGB7cn0Kc3Rhcm1hcF9jZWxsX2Fubm8kZGF0YXNldCA9ICdTcGF0aWFsJwpyZWZfY2VsbF9hbm5vJGRhdGFzZXQgPSAnUmVmZXJlbmNlJwoKY29tYl9jZWxsX2Fubm8gPSByYmluZChzdGFybWFwX2NlbGxfYW5ubywgcmVmX2NlbGxfYW5ubykKYGBgCgoKCiMjIFJlYWQgZXN0aW1hdGVkIGNlbGwgdHlwZSBwcm9wb3J0aW9ucwoKYGBge3J9CmZpbGVfbmFtZSA9IGZpbGUucGF0aChob21lLmRpciwgJ1BsYXRFZmZEZW1vX2FsbF9yZXN1bHRzLnJkcycpCmFsbF9yZXMgPSByZWFkUkRTKGZpbGVfbmFtZSkKcHJpbnQoc3ByaW50ZignbG9hZCBkYXRhIGZyb20gJXMnLCBmaWxlX25hbWUpKQpgYGAKCkNoZWNrIHRoZSBvcmRlciBvZiBzcG90cyBhbmQgY2VsbCB0eXBlcyBhcmUgY29uc2lzdGVudCBiZWZvcmUgcGVyZm9ybWFuY2UgZXZhbHVhdGlvbi4KCmBgYHtyfQpmb3IgKG1ldGhvZF9uYW1lIGluIG5hbWVzKGFsbF9yZXMpKSB7CiAgc3RvcGlmbm90KGFsbChyb3cubmFtZXMoYWxsX3Jlc1tbbWV0aG9kX25hbWVdXSkgPT0gcm93Lm5hbWVzKHRydXRoKSkpCiAgc3RvcGlmbm90KGFsbChjb2xuYW1lcyhhbGxfcmVzW1ttZXRob2RfbmFtZV1dKSA9PSBjb2xuYW1lcyh0cnV0aCkpKQp9CmBgYAoKQ2hlY2sgd2hldGhlciBuZWdhdGl2ZSB2YWx1ZXMgb2YgZXN0aW1hdGVkIGNlbGwgdHlwZSBwcm9wb3J0aW9ucyBleGlzdCwgYXMgbmVnYXRpdmUgdmFsdWVzIG1heSBjYXVzZSBlcnJvciBpbiBKU0QgY2FsY3VsYXRpb24gYW5kIGdvdCBgTmFOYC4gUmVwbGFjZSB0aGVtIGFzIDAuCgpgYGB7cn0KZm9yIChtZXRob2RfbmFtZSBpbiBuYW1lcyhhbGxfcmVzKSkgewogIHRtcF9kZiA9IGFsbF9yZXNbW21ldGhvZF9uYW1lXV0KICBmb3IgKGkgaW4gMTpucm93KHRtcF9kZikpIHsKICAgIGZvciAoaiBpbiAxOm5jb2wodG1wX2RmKSkgewogICAgICBpZiAodG1wX2RmW2ksIGpdIDwgMCkgewogICAgICAgIHByaW50KHNwcmludGYoJyVzIHJlc3VsdDogcm93ICVkICglcykgY29sdW1uICVkICglcykgaGFzIG5lZ2F0aXZlIHZhbHVlICVnJywgbWV0aG9kX25hbWUsIGksIHJvdy5uYW1lcyh0bXBfZGYpW2ldLCBqLCBjb2xuYW1lcyh0bXBfZGYpW2pdLCB0bXBfZGZbaSwgal0pKQogICAgICAgICMgcmVwbGFjZSB0aGVtIHdpdGggMAogICAgICAgIGFsbF9yZXNbW21ldGhvZF9uYW1lXV1baSwgal0gPSAwCiAgICAgIH0KICAgIH0KICB9Cn0KYGBgCgoKIyMgUmVhZCBVTUFQIGNvb3JkaW5hdGVzIGJlZm9yZSBDVkFFIHRyYW5zZm9ybWF0aW9uCgpVTUFQIGNvb3JkaW5hdGVzIGZvciBnZW5lIGV4cHJlc3Npb24gb2Ygc3BhdGlhbCBzcG90cyBhbmQgc2NSTkEtc2VxIHJlZmVyZW5jZSBjZWxscyBhcmUgaW4gZmlsZSBgVU1BUF9jb29yZGluYXRlc19yYXdfaW5wdXQuY3N2YC4KCmBgYHtyfQpmaWxlX25hbWUgPSBmaWxlLnBhdGgoaG9tZS5kaXIsICdQbGF0RWZmRGVtb19yZWZfc2NSTkFfU0RlUEVSX1dJVEhfQ1ZBRV9kaWFnbm9zaXMnLCAnZGlhZ25vc2lzJywgJ3Jhd19pbnB1dF9kYXRhJywgJ1VNQVBfY29vcmRpbmF0ZXNfcmF3X2lucHV0LmNzdicpCnVtYXBfYmVmb3JlID0gcmVhZC5jc3YoZmlsZV9uYW1lLCByb3cubmFtZXMgPSAxLCBjaGVjay5uYW1lcyA9IEYsIHN0cmluZ3NBc0ZhY3RvcnMgPSBGKQpwcmludChzcHJpbnRmKCdsb2FkIGRhdGEgZnJvbSAlcycsIGZpbGVfbmFtZSkpCnByaW50KHNwcmludGYoJ3RvdGFsICVkIHJvd3MnLCBucm93KHVtYXBfYmVmb3JlKSkpCmBgYAoKQWRkIHRoZSBjZWxsIHR5cGUgYW5ub3RhdGlvbi4KCmBgYHtyfQp1bWFwX2JlZm9yZSA9IG1lcmdlKHVtYXBfYmVmb3JlLCBjb21iX2NlbGxfYW5ubywgYnkgPSAncm93Lm5hbWVzJykKYGBgCgoKIyMgUmVhZCBVTUFQIGNvb3JkaW5hdGVzIGluIENWQUUgbGF0ZW50IHNwYWNlCgpVTUFQIGNvb3JkaW5hdGVzIGZvciBlbWJlZGRpbmcgaW4gQ1ZBRSBsYXRlbnQgc3BhY2Ugb2Ygc3BhdGlhbCBzcG90cyBhbmQgc2NSTkEtc2VxIHJlZmVyZW5jZSBjZWxscyBhcmUgaW4gZmlsZSBgVU1BUF9jb29yZGluYXRlc19sYXRlbnRfbXVfZW1iZWRkaW5nX3NwYXRpYWxfc3BvdHMuY3N2YCBhbmQgYFVNQVBfY29vcmRpbmF0ZXNfbGF0ZW50X211X2VtYmVkZGluZ19zY1JOQS1zZXFfY2VsbHMuY3N2YC4KCmBgYHtyfQpmaWxlX25hbWUgPSBmaWxlLnBhdGgoaG9tZS5kaXIsICdQbGF0RWZmRGVtb19yZWZfc2NSTkFfU0RlUEVSX1dJVEhfQ1ZBRV9kaWFnbm9zaXMnLCAnZGlhZ25vc2lzJywgJ0NWQUVfbGF0ZW50X3NwYWNlJywgJ1VNQVBfY29vcmRpbmF0ZXNfbGF0ZW50X211X2VtYmVkZGluZ19zcGF0aWFsX3Nwb3RzLmNzdicpCnVtYXBfbGF0ZW50X3NwYXRpYWwgPSByZWFkLmNzdihmaWxlX25hbWUsIHJvdy5uYW1lcyA9IDEsIGNoZWNrLm5hbWVzID0gRiwgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCnByaW50KHNwcmludGYoJ2xvYWQgZGF0YSBmcm9tICVzJywgZmlsZV9uYW1lKSkKCmZpbGVfbmFtZSA9IGZpbGUucGF0aChob21lLmRpciwgJ1BsYXRFZmZEZW1vX3JlZl9zY1JOQV9TRGVQRVJfV0lUSF9DVkFFX2RpYWdub3NpcycsICdkaWFnbm9zaXMnLCAnQ1ZBRV9sYXRlbnRfc3BhY2UnLCAnVU1BUF9jb29yZGluYXRlc19sYXRlbnRfbXVfZW1iZWRkaW5nX3NjUk5BLXNlcV9jZWxscy5jc3YnKQp1bWFwX2xhdGVudF9yZWYgPSByZWFkLmNzdihmaWxlX25hbWUsIHJvdy5uYW1lcyA9IDEsIGNoZWNrLm5hbWVzID0gRiwgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCnByaW50KHNwcmludGYoJ2xvYWQgZGF0YSBmcm9tICVzJywgZmlsZV9uYW1lKSkKCnVtYXBfbGF0ZW50ID0gcmJpbmQodW1hcF9sYXRlbnRfc3BhdGlhbCwgdW1hcF9sYXRlbnRfcmVmKQpwcmludChzcHJpbnRmKCd0b3RhbCAlZCByb3dzJywgbnJvdyh1bWFwX2xhdGVudCkpKQpgYGAKCkFkZCB0aGUgY2VsbCB0eXBlIGFubm90YXRpb24uCgpgYGB7cn0KdW1hcF9sYXRlbnQgPSBtZXJnZSh1bWFwX2xhdGVudCwgY29tYl9jZWxsX2Fubm8sIGJ5ID0gJ3Jvdy5uYW1lcycpCmBgYAoKCiMjIFJlYWQgVU1BUCBjb29yZGluYXRlcyBhZnRlciBDVkFFIHRyYW5zZm9ybWF0aW9uCgpVTUFQIGNvb3JkaW5hdGVzIGZvciBnZW5lIGV4cHJlc3Npb24gb2Ygc3BhdGlhbCBzcG90cyBhbmQgc2NSTkEtc2VxIHJlZmVyZW5jZSBjZWxscyBhcmUgaW4gZmlsZSBgVU1BUF9jb29yZGluYXRlc19kZWNvZGVkX3ZhbHVlLmNzdmAuCgpgYGB7cn0KZmlsZV9uYW1lID0gZmlsZS5wYXRoKGhvbWUuZGlyLCAnUGxhdEVmZkRlbW9fcmVmX3NjUk5BX1NEZVBFUl9XSVRIX0NWQUVfZGlhZ25vc2lzJywgJ2RpYWdub3NpcycsICdDVkFFX3RyYW5zZm9ybWVkX2RhdGEnLCAnVU1BUF9jb29yZGluYXRlc19kZWNvZGVkX3ZhbHVlLmNzdicpCnVtYXBfYWZ0ZXIgPSByZWFkLmNzdihmaWxlX25hbWUsIHJvdy5uYW1lcyA9IDEsIGNoZWNrLm5hbWVzID0gRiwgc3RyaW5nc0FzRmFjdG9ycyA9IEYpCnByaW50KHNwcmludGYoJ2xvYWQgZGF0YSBmcm9tICVzJywgZmlsZV9uYW1lKSkKcHJpbnQoc3ByaW50ZigndG90YWwgJWQgcm93cycsIG5yb3codW1hcF9hZnRlcikpKQpgYGAKCkFkZCB0aGUgY2VsbCB0eXBlIGFubm90YXRpb24uCgpgYGB7cn0KdW1hcF9hZnRlciA9IG1lcmdlKHVtYXBfYWZ0ZXIsIGNvbWJfY2VsbF9hbm5vLCBieSA9ICdyb3cubmFtZXMnKQpgYGAKCgoKIyBFdmFsdWF0ZSBwZXJmb3JtYW5jZSBvZiBjZWxsIHR5cGUgZGVjb252b2x1dGlvbiBtZXRob2RzCgojIyBDYWxjdWxhdGUgc3BvdC13aXNlIHBlcmZvcm1hbmNlIG9mIGFsbCBtZXRob2RzCgo1IHBlcmZvcm1hbmNlIG1lYXN1cmVtZW50czoKCiogcm9vdCBtZWFuIHNxdWFyZSBlcnJvciAoKipSTVNFKiopOiBxdWFudGlmaWVzIHRoZSBvdmVyYWxsIGVzdGltYXRpb24gYWNjdXJhY3kKKiBKZW5zZW4tU2hhbm5vbiBEaXZlcmdlbmNlICgqKkpTRCoqKTogYXNzZXNzZXMgc2ltaWxhcml0eSBiZXR3ZWVuIHRoZSBlc3RpbWF0ZWQgY2VsbCB0eXBlIGRpc3RyaWJ1dGlvbiBhbmQgZ3JvdW5kLXRydXRoIHBlciBzcG90CiogKipQZWFyc29uJ3MgY29ycmVsYXRpb24gY29lZmZpY2llbnQqKjogbWVhc3VyZXMgdGhlIHNpbWlsYXJpdHkgb2YgZXN0aW1hdGlvbiB0byBncm91bmQtdHJ1dGgKKiBmYWxzZSBkaXNjb3ZlcnkgcmF0ZSAoKipGRFIqKik6IG1lYXN1cmVzIGhvdyBtYW55IGNlbGwgdHlwZXMgd2VyZSBmYWxzZWx5IHByZWRpY3RlZCB0byBiZSBwcmVzZW50CiogZmFsc2UgbmVnYXRpdmUgcmF0ZSAoKipGTlIqKik6IG1lYXN1cmVzIGhvdyBtYW55IHByZXNlbnRlZCBjZWxsIHR5cGVzIHdlcmUgZmFsc2VseSBwcmVkaWN0ZWQgdG8gYmUgbm90IHByZXNlbnQKCmBgYHtyfQpiaW5hcnlQcmVkRXZhbHVhdGlvbiA9IGZ1bmN0aW9uKHRydXRoLCBwcmVkKSB7CiAgIyBHaXZlbiBhbiBhcnJheSBvZiB0cnV0aCBhbmQgcHJlZGljdGlvbnMgKGVpdGhlciAwIG9yIDEpLCBjYWxjdWxhdGUgY29uZnVzaW9uIG1hdHJpeAogICMgY29udmVydCB0byBmYWN0b3JzIHRvIGVuc3VyZSBnZXQgYSBmdWxsIDIqMiBjb25mdXNpb24gbWF0cml4CiAgdHJ1dGhfZmFjdG9yID0gZmFjdG9yKHRydXRoLCBsZXZlbHMgPSBjKDAsIDEpKQogIHByZWRfZmFjdG9yID0gZmFjdG9yKHByZWQsIGxldmVscyA9IGMoMCwgMSkpCiAgIyBHZW5lcmF0ZSBjb25mdXNpb24gbWF0cml4CiAgY29uZl9tYXRyaXggPSB0YWJsZShBY3R1YWwgPSB0cnV0aF9mYWN0b3IsIFByZWRpY3RlZCA9IHByZWRfZmFjdG9yKQogICMgRXh0cmFjdCBlbGVtZW50cyBvZiB0aGUgY29uZnVzaW9uIG1hdHJpeAogIFRQID0gY29uZl9tYXRyaXhbMiwgMl0KICBGUCA9IGNvbmZfbWF0cml4WzEsIDJdCiAgRk4gPSBjb25mX21hdHJpeFsyLCAxXQogIFROID0gY29uZl9tYXRyaXhbMSwgMV0KICAjIENhbGN1bGF0ZSBGRFIgKEZhbHNlIERpc2NvdmVyeSBSYXRlKQogIEZEUiA9IEZQIC8gKFRQICsgRlApCiAgIyBDYWxjdWxhdGUgRk5SIChGYWxzZSBOZWdhdGl2ZSBSYXRlKQogIEZOUiA9IEZOIC8gKFRQICsgRk4pCiAgcmV0dXJuKGMoRkRSLCBGTlIpKQp9CgpjYWxjUGVyZm9ybWFuY2UgPSBmdW5jdGlvbih0cnV0aCwgcHJlZCkgewogICMgY2FsY3VsYXRlIFJNU0UsIEpTRCwgY29ycmVsYXRpb24gYW5kIEZEUiBmb3IgZWFjaCByb3cKICAjIGlucHV0cyBhcmUgbWF0cml4IHdpdGggcm93cyBhcyBzcG90cyBhbmQgY29sdW1ucyBhcyBjZWxsIHR5cGVzLCBvcmRlciBoYXMgYmVlbiBjaGVja2VkIHRvIGJlIGNvbnNpc3RlbnQKICBzdG9waWZub3QoYWxsKHJvdy5uYW1lcyh0cnV0aCkgPT0gcm93Lm5hbWVzKHByZWQpKSkKICBzdG9waWZub3QoYWxsKGNvbG5hbWVzKHRydXRoKSA9PSBjb2xuYW1lcyhwcmVkKSkpCiAgCiAgIyBiaW5hcnkgY2VsbCB0eXBlIHByb3BvcnRpb25zICgwOmFic2VudDsgMTpwcmVzZW50KQogIHRydXRoX2JpbmFyeSA9IHRydXRoICE9IDAKICBwcmVkX2JpbmFyeSA9IHByZWQgIT0gMAogICMgaW4tcGxhY2UgY29udmVyc2lvbiBmcm9tIGJvb2wgdG8gMC8xIHdoaWxlIGtlZXBpbmcgZGltZW5zaW9ucywgcm93IG5hbWVzIGFuZCBjb2x1bW4gbmFtZXMsIGFzIGBhcy5udW1lcmljKClgIHdpbGwgImZsYXR0ZXJuIiB0aGUgb3JpZ2luYWwgbWF0cml4CiAgdHJ1dGhfYmluYXJ5W10gPSBhcy5udW1lcmljKHRydXRoX2JpbmFyeSkKICBwcmVkX2JpbmFyeVtdID0gYXMubnVtZXJpYyhwcmVkX2JpbmFyeSkKICAKICBwZXJmb3JtX2RmID0gZGF0YS5mcmFtZShtYXRyaXgobmNvbD01LCBucm93PTApKQogIGNvbG5hbWVzKHBlcmZvcm1fZGYpID0gYygnUk1TRScsICdKU0QnLCAnUGVhcnNvbicsICdGRFInLCAnRk5SJykKICAKICBmb3IgKGkgaW4gMTpucm93KHRydXRoKSkgewogICAgUk1TRSA9IHNxcnQobWVhbigodHJ1dGhbaSxdIC0gcHJlZFtpLF0pIF4gMikpCiAgICBpZiAoc3VtKHByZWRbaSxdKT4wICYgc3VtKHRydXRoW2ksXSk+MCkgewogICAgICBKU0QgPSBwaGlsZW50cm9weTo6SlNEKHJiaW5kKHRydXRoW2ksXSwgcHJlZFtpLF0pLCB1bml0ID0gJ2xvZzInLCBlc3QucHJvYiA9ICdlbXBpcmljYWwnKQogICAgfSBlbHNlIHsKICAgICAgSlNEID0gMQogICAgfQogICAgUGVhcnNvbiA9IGNvci50ZXN0KHRydXRoW2ksXSwgcHJlZFtpLF0pJGVzdGltYXRlCiAgICB0bXAgPSBiaW5hcnlQcmVkRXZhbHVhdGlvbih0cnV0aF9iaW5hcnlbaSxdLCBwcmVkX2JpbmFyeVtpLF0pCiAgICBGRFIgPSB0bXBbMV0KICAgIEZOUiA9IHRtcFsyXQogICAgCiAgICBwZXJmb3JtX2RmW25yb3cocGVyZm9ybV9kZikrMSwgXSA9IGMoUk1TRSwgSlNELCBQZWFyc29uLCBGRFIsIEZOUikKICB9CiAgCiAgIyBhbHNvIHJlY29yZCBzcG90IG5hbWVzCiAgc3RvcGlmbm90KG5yb3cocGVyZm9ybV9kZikgPT0gbnJvdyh0cnV0aCkpCiAgcGVyZm9ybV9kZlsnU3BvdCddID0gcm93Lm5hbWVzKHRydXRoKQogIAogIHJldHVybihwZXJmb3JtX2RmKQp9CgoKYWxsX3BlcmZvcm0gPSBsaXN0KCkKCmZvciAobWV0aG9kX25hbWUgaW4gbmFtZXMoYWxsX3JlcykpIHsKICBhbGxfcGVyZm9ybVtbbWV0aG9kX25hbWVdXSA9IGNhbGNQZXJmb3JtYW5jZShhcy5tYXRyaXgodHJ1dGgpLCBhcy5tYXRyaXgoYWxsX3Jlc1tbbWV0aG9kX25hbWVdXSkpCn0KYGBgCgoKIyMgU3VtbWFyeSBzcG90LXdpc2UgcGVyZm9ybWFuY2UgaW50byBtZXRob2Qtd2lzZQoKYGBge3J9CnBlcmZvcm1fcmF3X2RmID0gZGF0YS5mcmFtZShtYXRyaXgobmNvbD0xMCwgbnJvdz0wKSkKY29sbmFtZXMocGVyZm9ybV9yYXdfZGYpID0gYygnRGF0YXNldCcsICdTY2VuYXJpbycsICdNZXRob2QnLCAnUmVmZXJlbmNlJywgJ1Nwb3QnLCAnUk1TRScsICdKU0QnLCAnUGVhcnNvbicsICdGRFInLCAnRk5SJykKCiMgY2FsY3VsYXRlIG1lZGlhbiBwZXJmb3JtYW5jZSBhY3Jvc3MgYWxsIHNwYXRpYWwgc3BvdHMgZm9yIGFsbCBtZXRob2RzCnBlcmZvcm1fbWVkaWFuX2RmID0gZGF0YS5mcmFtZShtYXRyaXgobmNvbD05LCBucm93PTApKQpjb2xuYW1lcyhwZXJmb3JtX21lZGlhbl9kZikgPSBjKCdEYXRhc2V0JywgJ1NjZW5hcmlvJywgJ01ldGhvZCcsICdSZWZlcmVuY2UnLCAnbWVkaWFuX1JNU0UnLCAnbWVkaWFuX0pTRCcsICdtZWRpYW5fUGVhcnNvbicsICdtZWRpYW5fRkRSJywgJ21lZGlhbl9GTlInKQoKdGhpc19kYXRhc2V0ID0gJ1NUQVJtYXAtYmFzZWQnCnRoaXNfc2NlbmFyaW8gPSAnU2NlbmFyaW8gMScKdGhpc19yZWYgPSAnRXh0ZXJuYWwnCiAgICAgIApmb3IgKG1ldGhvZF9uYW1lIGluIG5hbWVzKGFsbF9wZXJmb3JtKSkgewogIHRtcF9kZiA9IGFsbF9wZXJmb3JtW1ttZXRob2RfbmFtZV1dCiAgdG1wX2RmWydEYXRhc2V0J10gPSB0aGlzX2RhdGFzZXQKICB0bXBfZGZbJ1NjZW5hcmlvJ10gPSB0aGlzX3NjZW5hcmlvCiAgdG1wX2RmWydNZXRob2QnXSA9IG1ldGhvZF9uYW1lCiAgdG1wX2RmWydSZWZlcmVuY2UnXSA9IHRoaXNfcmVmCiAgICAKICBwZXJmb3JtX3Jhd19kZiA9IHJiaW5kKHBlcmZvcm1fcmF3X2RmLCB0bXBfZGZbLCBjKCdEYXRhc2V0JywgJ1NjZW5hcmlvJywgJ01ldGhvZCcsICdSZWZlcmVuY2UnLCAnU3BvdCcsICdSTVNFJywgJ0pTRCcsICdQZWFyc29uJywgJ0ZEUicsICdGTlInKV0pCiAgICAKICBwZXJmb3JtX21lZGlhbl9kZltucm93KHBlcmZvcm1fbWVkaWFuX2RmKSsxLCBdID0gYyh0aGlzX2RhdGFzZXQsIHRoaXNfc2NlbmFyaW8sIG1ldGhvZF9uYW1lLCB0aGlzX3JlZiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByb3VuZChtZWRpYW4odG1wX2RmJFJNU0UpLCAzKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByb3VuZChtZWRpYW4odG1wX2RmJEpTRCksIDMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvdW5kKG1lZGlhbih0bXBfZGYkUGVhcnNvbiksIDMpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJvdW5kKG1lZGlhbih0bXBfZGYkRkRSKSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcm91bmQobWVkaWFuKHRtcF9kZiRGTlIpLCAzKSkKfQoKIyBzZXQgbWV0aG9kIGNvbHVtbiBhcyBmYWN0b3JzCnBlcmZvcm1fcmF3X2RmWydNZXRob2QnXSA9IGZhY3RvcihwZXJmb3JtX3Jhd19kZiRNZXRob2QsIGxldmVscyA9IGMoIlNEZVBFUiIsICJHTFJNIiwgIk5PX1BsYXRFZmZSbXYiKSkKCnBlcmZvcm1fbWVkaWFuX2RmWywgYygnRGF0YXNldCcsICdTY2VuYXJpbycsICdNZXRob2QnLCAnUmVmZXJlbmNlJywgJ21lZGlhbl9STVNFJywgJ21lZGlhbl9KU0QnLCAnbWVkaWFuX1BlYXJzb24nLCAnbWVkaWFuX0ZEUicsICdtZWRpYW5fRk5SJyldCmBgYAoKCiMgRHJhdyBmaWd1cmVzCgojIyBVTUFQIG9mIHNwYXRpYWwgc3BvdHMgYW5kIHJlZmVyZW5jZSBjZWxscyBiZWZvcmUgQ1ZBRSB0cmFuc2Zvcm1hdGlvbgoKYGBge3IsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD01fQpnZ3Bsb3QodW1hcF9iZWZvcmUsIGFlcyh4PVVNQVAxLCB5PVVNQVAyLCBjb2xvcj1jZWxsdHlwZSkpICsKICBnZW9tX3BvaW50KHNoYXBlPTIwLCBzaXplPTAuNSkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgc2NhbGVfY29sb3JfbWFudWFsKHZhbHVlcyA9IG15X2NvbG9yKSArCiAgZmFjZXRfZ3JpZCh+ZGF0YXNldCkgKwogIHRoZW1lKGxlZ2VuZC50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSwgc3RyaXAudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplPTE0KSkgKwogIGd1aWRlcyhjb2xvciA9IGd1aWRlX2xlZ2VuZChvdmVycmlkZS5hZXMgPSBsaXN0KHNpemUgPSAzKSkpCmBgYAoKCiMjIFVNQVAgb2Ygc3BhdGlhbCBzcG90cyBhbmQgcmVmZXJlbmNlIGNlbGxzIGluIENWQUUgbGF0ZW50IHNwYWNlCgpgYGB7ciwgZmlnLndpZHRoPTEwLCBmaWcuaGVpZ2h0PTV9CmdncGxvdCh1bWFwX2xhdGVudCwgYWVzKHg9VU1BUDEsIHk9VU1BUDIsIGNvbG9yPWNlbGx0eXBlKSkgKwogIGdlb21fcG9pbnQoc2hhcGU9MjAsIHNpemU9MC41KSArCiAgdGhlbWVfY2xhc3NpYygpICsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gbXlfY29sb3IpICsKICBmYWNldF9ncmlkKH5kYXRhc2V0KSArCiAgdGhlbWUobGVnZW5kLnRpdGxlID0gZWxlbWVudF9ibGFuaygpLCBzdHJpcC50ZXh0ID0gZWxlbWVudF90ZXh0KHNpemU9MTQpKSArCiAgZ3VpZGVzKGNvbG9yID0gZ3VpZGVfbGVnZW5kKG92ZXJyaWRlLmFlcyA9IGxpc3Qoc2l6ZSA9IDMpKSkKYGBgCgoKIyMgVU1BUCBvZiBzcGF0aWFsIHNwb3RzIGFuZCByZWZlcmVuY2UgY2VsbHMgYWZ0ZXIgQ1ZBRSB0cmFuc2Zvcm1hdGlvbgoKYGBge3IsIGZpZy53aWR0aD0xMCwgZmlnLmhlaWdodD01fQpnZ3Bsb3QodW1hcF9hZnRlciwgYWVzKHg9VU1BUDEsIHk9VU1BUDIsIGNvbG9yPWNlbGx0eXBlKSkgKwogIGdlb21fcG9pbnQoc2hhcGU9MjAsIHNpemU9MC41KSArCiAgdGhlbWVfY2xhc3NpYygpICsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gbXlfY29sb3IpICsKICBmYWNldF9ncmlkKH5kYXRhc2V0KSArCiAgdGhlbWUobGVnZW5kLnRpdGxlID0gZWxlbWVudF9ibGFuaygpLCBzdHJpcC50ZXh0ID0gZWxlbWVudF90ZXh0KHNpemU9MTQpKSArCiAgZ3VpZGVzKGNvbG9yID0gZ3VpZGVfbGVnZW5kKG92ZXJyaWRlLmFlcyA9IGxpc3Qoc2l6ZSA9IDMpKSkKYGBgCgoKCiMjIEJveHBsb3Qgb2YgcGVyZm9ybWFuY2Ugb2YgYWxsIG1ldGhvZHMKCmBgYHtyLCBmaWcud2lkdGg9NSwgZmlnLmhlaWdodD0yfQpwbG90X2RmID0gcGVyZm9ybV9yYXdfZGYKCmdfbGlzdCA9IGxpc3QoKQoKZm9yIChwZXJmb3JtX2luZCBpbiBjKCdSTVNFJywgJ1BlYXJzb24nLCAnSlNEJywgJ0ZEUicpKSB7CiAgZ19saXN0W1twZXJmb3JtX2luZF1dID0gZ2dwbG90KHBsb3RfZGYsIGFlcyh4PU1ldGhvZCwgeT0uZGF0YVtbcGVyZm9ybV9pbmRdXSwgZmlsbD1NZXRob2QpKSArCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBnZW9tX2JveHBsb3QocG9zaXRpb249cG9zaXRpb25fZG9kZ2UoKSwgb3V0bGllci5zaGFwZT1OQSkgKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2NhbGVfZmlsbF9tYW51YWwodmFsdWVzPW1ldGhvZF9jb2xvciwgbGFiZWxzPWMoJ1NEZVBFUic9J1NEZVBFUiAoYmFzZWxpbmUpJywnR0xSTSc9J0dMUk0gKE5PIENWQUUpJywgJ05PX1BsYXRFZmZSbXYnPSdOTyBQbGF0RWZmUm12JykpICsKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHRoZW1lX2NsYXNzaWMoKSArCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0aGVtZShheGlzLnRleHQgPSBlbGVtZW50X3RleHQoY29sb3I9ImJsYWNrIiksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBheGlzLnRpY2tzLnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGF4aXMudGl0bGUueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGxlZ2VuZC50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIAp9CgpnX2xpc3RbWydQZWFyc29uJ11dID0gZ19saXN0W1snUGVhcnNvbiddXSArIGdlb21faGxpbmUoeWludGVyY2VwdD0wLCBjb2xvcj0icmVkIiwgbGluZXR5cGU9ImRhc2hlZCIpCgpnZ3B1YnI6OmdnYXJyYW5nZShwbG90bGlzdD1nX2xpc3QsIG5jb2w9NCwgbnJvdz0xLCBjb21tb24ubGVnZW5kPVRSVUUsIGxlZ2VuZD0iYm90dG9tIiwgYWxpZ24gPSAnaHYnKQpgYGAKCiMjIEFkZHRpb25hbCBib3hwbG90IGZvciBGTlIKCmBgYHtyLCBmaWcud2lkdGg9NCwgZmlnLmhlaWdodD0zfQpnZ3Bsb3QocGxvdF9kZiwgYWVzKHg9TWV0aG9kLCB5PUZOUiwgZmlsbD1NZXRob2QpKSArCiAgZ2VvbV9ib3hwbG90KHBvc2l0aW9uPXBvc2l0aW9uX2RvZGdlKCksIG91dGxpZXIuc2hhcGU9TkEpICsKICBzY2FsZV9maWxsX21hbnVhbCh2YWx1ZXM9bWV0aG9kX2NvbG9yLCBsYWJlbHM9YygnU0RlUEVSJz0nU0RlUEVSIChiYXNlbGluZSknLCdHTFJNJz0nR0xSTSAoTk8gQ1ZBRSknLCAnTk9fUGxhdEVmZlJtdic9J05PIFBsYXRFZmZSbXYnKSkgKwogIHRoZW1lX2NsYXNzaWMoKSArCiAgdGhlbWUoYXhpcy50ZXh0ID0gZWxlbWVudF90ZXh0KGNvbG9yPSJibGFjayIpLAogICAgICAgIGF4aXMudGlja3MueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSwKICAgICAgICBheGlzLnRpdGxlLnggPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgbGVnZW5kLnRpdGxlID0gZWxlbWVudF9ibGFuaygpKQpgYGAKCgo=