In this notebookd we simulate outcome data and compare the performance of the TOR approach with minimum read fraction (MRF) approach.

Preparations

library(tidyverse)
library(poibin)
library(combinat)
library(furrr)
library(data.table)
library(matrixStats)
library(rprojroot)
library(cowplot)
plan(multiprocess)
[ONE-TIME WARNING] Forked processing ('multicore') is disabled in future (>= 1.13.0) when running R from RStudio, because it is considered unstable. Because of this, plan("multicore") will fall back to plan("sequential"), and plan("multiprocess") will fall back to plan("multisession") - not plan("multicore") as in the past. For more details, how to control forked processing or not, and how to silence this warning in future R sessions, see ?future::supportsMulticore
require(knitr)
opts_chunk$set(error=FALSE, message=FALSE, warning=FALSE)
knitr::opts_knit$set(root.dir = rprojroot::find_rstudio_root_file())
options(future.globals.maxSize= +Inf, future.fork.enable=TRUE)
figures_dir <- file.path("./figures")

Define Functions

create_data <- function(prob, rmax, nreads){
  dt <- 
    tibble(r=1:rmax,
           s=dgeom(r-1, prob[1]) ) %>% 
    mutate(s=(s/sum(s))) %>%
    mutate(rs= r*s)
  
  RMR <-sum(dt %>% pull(rs))
  nmol <- nreads/RMR
  
  dt <- 
    dt %>% 
    mutate(s= round(nmol*s))%>%
    select(-rs)
  
  return(dt)
}



get_product_logsum <- function(x, y) {
  z_log <- log(x) + log(y)
  z <- exp(z_log)
  return(z)
}


generate_outcomes_s <- function(s, p, S, r, pi_r){
  p_h <- (1 - p) / (S - 1)
  pvec <- rep(p_h, S)
  pvec[s] <- p
  pi_r_s <- pi_r[s]
  
  outcomes <- xsimplex(S, r)
  
  pmf <- apply(outcomes,
               2,
               dmnom,
               prob = pvec)
  
  outcomes <- outcomes  %>% 
    t() %>%
    as_tibble( .name_repair = "unique") %>%
    setNames(paste0("y", 1:S)) %>%
    mutate(pmf_rs=pmf,
           pmf_r=get_product_logsum(pmf, pi_r_s))
  
  return(outcomes)
}



create_grouping_vars <- function(outcomes, S, mrf) {
  
  s <- 
    outcomes %>%
    pull(s) %>%
    as.numeric()
  
  
  setDT(outcomes)
  
  outcomes[,
           outcome := do.call(paste, c(.SD, sep = ",")),
           .SDcols = paste0("y", 1:S)]
  
  outcome <-
    outcomes %>%
    pull(outcome)
  
  outcomes <-
    outcomes  %>%
    select(c(paste0("y", 1:S))) %>%
    as.matrix
  
  
  y_s <- as.integer(outcomes[cbind(seq_along(s), s)] != 0)
  
  
  r <- as.integer(rowSums2(outcomes))
  k_chimera <- as.integer(S - rowCounts(outcomes, value = 0))
  fantoms <- k_chimera - y_s
  
  
  
  s_frac_1 <-
    apply(cbind(outcomes,r),
          1,
          function(x) {
            y <- which(x[1:S] >=  (x[S + 1] *mrf[1]))
            y <- unname(y)
            if (length(y) == 0)
              y <- 0
            return(y)
          })
  
  s_frac_2 <-
    apply(cbind(outcomes,r),
          1,
          function(x) {
            y <- which(x[1:S] >=  (x[S + 1] * mrf[2]))
            y <- unname(y)
            if (length(y) == 0)
              y <- 0
            return(y)
          })
  
  
  s_frac_3 <-
    apply(cbind(outcomes,r),
          1,
          function(x) {
            y <- which(x[1:S] >=  (x[S + 1]* mrf[3]))
            y <- unname(y)
            if (length(y) == 0)
              y <- 0
            return(y)
          })
  
  grouping_vars <- tibble(outcome=outcome,
                          r = r,
                          s_frac_1 = s_frac_1,
                          s_frac_2 = s_frac_2,
                          s_frac_3 = s_frac_3,
                          fantoms =fantoms,
                          k_chimera = k_chimera)
  
  return(grouping_vars)
}


add_vars_to_outcome_counts <- function(outcomes, S, mrf) {
  
  grouping_vars <- create_grouping_vars(outcomes,S, mrf) 
  outcomes <- bind_cols(outcomes, grouping_vars)  
  
  return(outcomes)
  
}


infer_sample_of_origin_outcome <- function(..., pi_r, log_zi, S, p) {
  y <- c(...)[1:S]
  log_sample_pi <- log(pi_r)
  posterior_s <- y * log_zi + log_sample_pi
  
  ## normalize to the sample with maximum posterior probability
  posterior_s <- posterior_s - max(posterior_s)
  posterior_s <- exp(posterior_s)
  
  posterior <- posterior_s / sum(posterior_s)
  q <- max(posterior)
  s_hat <- which.max(posterior)
  
  out <- list(s_hat = s_hat, q = q)
  return(out)
}


add_posterior_prob <- function(outcomes, S, p, pi_r) {
  
  log_zi <- log((S - 1)) - log(1 / p - 1)
  
  posteriors <-
    future_pmap_dfr(
      outcomes %>%
        select(paste0("y", 1:S)),
      infer_sample_of_origin_outcome,
      pi_r=pi_r,
      log_zi = log_zi,
      S=S,
      p=p
    )
  
  outcomes <- bind_cols(outcomes %>%
                          select(-c(paste0("y", 1:S))),
                        posteriors)
  
  return(outcomes)
  
}



generate_outcomes <- function(...,p, S, mrf){
  
  r <- c(...)[1]
  pi_r <- c(...)[2:(S+1)]
  
  
  outcomes <- future_map_dfr(1:S,
                             generate_outcomes_s,
                             p=p,
                             S=S,
                             r=r,
                             pi_r=pi_r,
                             .id = "s")
  
  
  outcomes <- add_vars_to_outcome_counts(outcomes, S, mrf)
  
  
  
  outcomes <- add_posterior_prob(outcomes, S, p, pi_r) 
  
  
  outcomes <- 
    outcomes %>%
    mutate(s= as.integer(s) ,
           s_frac_1= as.integer(s_frac_1),
           s_frac_2= as.integer(s_frac_2),
           s_frac_3= as.integer(s_frac_3),
           r=as.integer(r))
  
  return(outcomes)
}


evaluate_classification <- function(outcomes) {
  
  
  outcomes <- 
    outcomes %>%
    mutate(
      hit_s= s==s_hat,
      hit_frac_1= s==s_frac_1,
      hit_frac_2= s==s_frac_2,
      hit_frac_3= s==s_frac_3,
      k_chimera_p=get_product_logsum(k_chimera, pmf),
      fantoms_p=get_product_logsum(fantoms, pmf),
      g=(1-(k_chimera-fantoms))*pmf,
      qr = 1 - q)  
  
  g_total <-  
    outcomes %>%
    summarise_at(vars(c("g")), sum)  %>%
    pull(g)
  
  outcomes<-
    outcomes %>%
    arrange(qr)%>%
    mutate(
      o = cumsum(pmf),
      FP = cumsum(get_product_logsum(
        qr,
        pmf
      )),
      FN=1 - o + FP-g_total,
      FPm= last(FP)- FP, # marginal
      FNm=FN-last(FN), # marginal
      tor=if_else(FPm <.Machine$double.neg.eps | FNm <.Machine$double.neg.eps,
                  0,
                  FNm/FPm),
      FP_1=case_when(
        !hit_frac_1 & s_frac_1!=0 ~ pmf,
        TRUE ~0),
      FN_1=case_when(s_frac_1==0 & g==0 ~ pmf,
                     !hit_frac_1 & s_frac_1!=0  & g==0 ~ pmf,
                     TRUE ~0),
      FP_2=case_when(
        !hit_frac_2 & s_frac_2!=0 ~ pmf,
        TRUE ~0),
      FN_2=case_when(s_frac_2==0 & g==0 ~ pmf,
                     !hit_frac_2 & s_frac_2!=0  & g==0 ~ pmf,
                     TRUE ~0),
      FP_3=case_when(
        !hit_frac_3 & s_frac_3!=0 ~ pmf,
        TRUE ~0),
      FN_3=case_when(s_frac_3==0 & g==0 ~ pmf,
                     !hit_frac_3 & s_frac_3!=0  & g==0 ~ pmf,
                     TRUE ~0))
  
  
  return(outcomes)
  
}

compute_classification_metrics <- function(p, pi_r,m_df, torc, mrf){
  
  outcomes <-  
    future_pmap_dfr(pi_r,
                    generate_outcomes,
                    p=p,
                    S=S,
                    mrf=mrf)
  
  outcomes <- 
    left_join(outcomes ,
              m_df, 
              by="r") %>%
    mutate(
      pmf= get_product_logsum(pmf_r,m))%>%
    select(-c("m","pmf_rs","pmf_r")) 
  
  outcomes <- evaluate_classification(outcomes) 
  
  
  tor_thresh <-
    outcomes %>%
    summarize(tor_thresh = tor[which.max(-pmax(tor, torc))]) %>%
    pull(tor_thresh)
  
  
  metrics_tor <-
    outcomes %>%
    filter(tor == tor_thresh) %>%
    slice(1)  %>%
    select(FP, FN, tor) %>%
    rename(cutoff = "tor") %>%
    mutate(cutoff = paste0("tor_", str_sub(
      as.character(cutoff),
      start = 1,
      end = 4
    )))
  
  
  maxfrac_fp <-
    outcomes %>%
    summarise_at(vars(starts_with("FP_")), sum) %>%
    gather(condition, FP) %>%
    select(FP)
  
  maxfrac_fn <-
    outcomes %>%
    summarise_at(vars(starts_with("FN_")), sum)  %>%
    gather(condition, FN) %>%
    select(FN)

  metrics_dt <- bind_cols(maxfrac_fp,
                          maxfrac_fn) %>%
    
    mutate(cutoff = sprintf("mf_%.2f", mrf)) %>%
    bind_rows(., metrics_tor) %>%
    select(cutoff, everything())
  
  
  tor_dt <-
    outcomes %>%
    filter(tor < 10 & tor > 1 & g == 0) %>%
    mutate(tor = round(tor, 4)) %>%
    group_by(tor) %>%
    filter(row_number() == 1)
  
  
  return(list(tor_dt=tor_dt,  metrics_dt= metrics_dt))
}


plot_Pi <- function(Pi, Pi_marginal) {
  p1 <-
    ggplot(Pi %>%
             select(
               -sum_mols
             ) %>%
             gather(sample, p, -c("r"))) +
    geom_line(aes(
      x = r,
      y = p,
      colour = sample
    ),
    size = 1,
    alpha = 1
    ) +
    geom_point(
      data = Pi %>%
        select(r, m),
      aes(x = r, y = m),
      shape = 10,
      size = 1,
      alpha = .9
    ) +
    theme_bw() +
    geom_hline(
      data = Pi_marginal,
      aes(
        yintercept = p_molecs,
        colour = sample
      ),
      size = 0.3,
      linetype = "longdash",
      alpha = 1
    ) +
    labs(
      x = "r (PCR duplicates)",
      y = "proportion"
    ) +
    scale_colour_viridis_d(
      option = "inferno",
      direction = -1
    ) +
    theme(
      axis.title.x = element_text(size = rel(1.4)),
      axis.title.y = element_text(size = rel(1.4)),
      axis.text = element_text(size = rel(1.3)),
      legend.title = element_text(size = rel(1.1), face = "bold"),
      legend.text = element_text(size = rel(1.1))
    )
  return(p1)
}


plot_trade_off <- function(condition, condition_name){
  
  condition$metrics_dt$cutoff[4] <- "tor*"
  
  p <- ggplot(condition$tor_dt) + 
    geom_line(
      aes(x = FP,
          y = FN),
      colour="grey")+
    geom_point(
      aes(x = FP,
          y = FN,
          color=tor),
      size=.5,
      alpha=.8)+
    scale_color_viridis_c() +
    labs(x="False Positives",
         y="False Negatives") +
    geom_point(data=condition$metrics_dt,
               aes(x = FP,
                   y = FN,
                   shape=cutoff),
               size=1.8,
               colour="brown")+
    theme_bw()  +
    #scale_y_sqrt()+
    theme(
      legend.title = element_text(face = "bold")
    ) +
    expand_limits(x = c(0, .006), y = c(0, 0.04))
  
  legend <- get_legend(p)
  p <- p + theme(legend.position = "none")
  
  p <- ggdraw() +
    draw_plot(p, 0, 0, 1, 1) +
    draw_label(paste0("SIHR=", condition_name),
               x = 0,
               y = 1,
               vjust = 2,
               hjust = -1.8,
               size = 12,
               fontface = "italic"
    )
  
  return(list(p=p, legend=legend))
}

plot_trade_off_all <- function(metrics_list) {
  
  p_tradeoff <- imap(metrics_list, plot_trade_off)
  
  p_list <- 
    p_tradeoff %>%
    map(list("p"))
  
  legend_list <- 
    p_tradeoff %>% 
    map(list("legend"))
  
  p_tradeoff_all <- 
    plot_grid(
      plot_grid(p_list[[1]],
                p_list[[2]],
                p_list[[3]], 
                p_list[[4]],
                align="hv",
                axis ="tblr"),
      plot_grid(NULL,
                legend_list[[4]], 
                NULL,
                ncol=1),
      rel_widths=c(1, 0.1))
  
  return(p_tradeoff_all)
  
}

simulate_pi <- function(prob , rmax, nreads=3e7 ){
  
  sample_names <- paste0("s", 1:length(prob))
  names(prob)  <- sample_names 
  
  dt <-
    map_dfr(prob, 
            create_data,
            rmax=rmax,
            nreads=nreads,
            .id="sample") %>%
    spread(sample, s)
  
  dt_summary <-
    dt %>%
    select(-r) %>%
    summarize_all(sum) %>%
    gather(sample, nmols) %>%
    mutate(RMR=nreads/nmols,
           pgeom_prob=prob,
           p_molecs=nmols/sum(nmols))
  
  dt <- dt %>%
    mutate(sum_mols = rowSums(.[sample_names])) %>%
    mutate_at(vars(sample_names), ~ . / sum_mols) %>%
    mutate(m= sum_mols/sum(sum_mols))
  
  return(list(Pi=dt, summary=dt_summary))
}


simulate_data <- function(prob, pvec, rmax, torc, mrf){
  pi_out <- simulate_pi(prob, rmax)
  m_df <- pi_out$Pi %>% select(r, m)
  pi_r <- pi_out$Pi %>% select(-m, -sum_mols)
  
  metrics_list <-
    map(pvec,
        compute_classification_metrics,
        pi_r=pi_r,
        m_df=m_df,
        torc=torc,
        mrf=mrf)
  
  return(list(metrics_list=metrics_list, pi_out=pi_out))
}

Simulate Molecular Complexity Profile

Set parameters

S <- 4  # sample number
rmax <- 30 # PCR amplification limit
torc <- 3 # Trade off cutoff
mrf <- c(0.6, 0.8, 0.9) #three choices for the minimum read fraction (MRF) thresholds. 0.8 is the default
pvec <- c(0.982, 0.986, 0.990, 0.994) # probability of not hopping (4 settings)
names(pvec) <- c(0.018, 0.014, 0.010, 0.006) # name vector with SIHR (i.e. hopping rate or 1-pvec) 
pvec 
0.018 0.014  0.01 0.006 
0.982 0.986 0.990 0.994 

Simulate data for parameter setting 1

Set the parameter values for the truncated geometric distributions for the S samples

prob1 <- c( 0.45, 0.4, 0.1,  0.05) 
out_1 <- simulate_data(prob1, pvec,rmax, torc, mrf) 
out_1$pi_out$summary

Plot the molecular proportions complexity profile

plot_Pi(out_1$pi_out$Pi, out_1$pi_out$summary)

Show the results

out_1$metrics_list
$`0.018`
$`0.018`$tor_dt

$`0.018`$metrics_dt


$`0.014`
$`0.014`$tor_dt

$`0.014`$metrics_dt


$`0.01`
$`0.01`$tor_dt

$`0.01`$metrics_dt


$`0.006`
$`0.006`$tor_dt

$`0.006`$metrics_dt
NANA

Plot the results


p_trade_off_1 <- plot_trade_off_all(out_1$metrics_list) 
p_trade_off_1 

save plot

save_plot(file.path(figures_dir, "simulation_tradoff01.pdf"), 
          p_trade_off_1,
          ncol = 3, # we're saving a grid plot of 2 columns
          nrow = 2, # and 2 rows
          base_height=4,
          # each individual subplot should have an aspect ratio of 1.3
          base_aspect_ratio = 1
)

Simulate data for parameter setting 2

prob2 <- c( 0.45, 0.42, 0.40,  0.05)
out_2 <- simulate_data(prob2, pvec,rmax, torc, mrf) 
out_2$pi_out$summary
plot_Pi(out_2$pi_out$Pi, out_2$pi_out$summary)

out_2$metrics_list
$`0.018`
$`0.018`$tor_dt

$`0.018`$metrics_dt


$`0.014`
$`0.014`$tor_dt

$`0.014`$metrics_dt


$`0.01`
$`0.01`$tor_dt

$`0.01`$metrics_dt


$`0.006`
$`0.006`$tor_dt

$`0.006`$metrics_dt
NANA

Plot results


p_trade_off_2 <- plot_trade_off_all(out_2$metrics_list) 
p_trade_off_2

save plot

save_plot(file.path(figures_dir, "simulation_tradoff02.pdf"), 
          p_trade_off_2,
          ncol = 3, # we're saving a grid plot of 2 columns
          nrow = 2, # and 2 rows
          base_height=4,
          # each individual subplot should have an aspect ratio of 1.3
          base_aspect_ratio = 1
)
sessionInfo()
R version 3.6.2 (2019-12-12)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 18.04.3 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/blas/libblas.so.3.7.1
LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.7.1

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C               LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8     LC_MONETARY=en_US.UTF-8   
 [6] LC_MESSAGES=en_US.UTF-8    LC_PAPER=en_US.UTF-8       LC_NAME=C                  LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
 [1] knitr_1.26         cowplot_1.0.0      rprojroot_1.3-2    matrixStats_0.55.0 data.table_1.12.8  furrr_0.1.0        future_1.15.1     
 [8] combinat_0.0-8     poibin_1.5         forcats_0.4.0      stringr_1.4.0      dplyr_0.8.3        purrr_0.3.3        readr_1.3.1       
[15] tidyr_1.0.0        tibble_2.1.3       ggplot2_3.2.1      tidyverse_1.3.0   

loaded via a namespace (and not attached):
 [1] Rcpp_1.0.3        lubridate_1.7.4   lattice_0.20-38   listenv_0.8.0     assertthat_0.2.1  zeallot_0.1.0     digest_0.6.23    
 [8] R6_2.4.1          cellranger_1.1.0  backports_1.1.5   reprex_0.3.0      httr_1.4.1        pillar_1.4.3      rlang_0.4.2      
[15] lazyeval_0.2.2    readxl_1.3.1      rstudioapi_0.10   labeling_0.3      munsell_0.5.0     broom_0.5.3       compiler_3.6.2   
[22] modelr_0.1.5      xfun_0.12         pkgconfig_2.0.3   globals_0.12.5    tidyselect_0.2.5  codetools_0.2-16  fansi_0.4.1      
[29] viridisLite_0.3.0 crayon_1.3.4      dbplyr_1.4.2      withr_2.1.2       grid_3.6.2        nlme_3.1-143      jsonlite_1.6     
[36] gtable_0.3.0      lifecycle_0.1.0   DBI_1.1.0         magrittr_1.5      scales_1.1.0      cli_2.0.1         stringi_1.4.5    
[43] farver_2.0.1      fs_1.3.1          xml2_1.2.2        ellipsis_0.3.0    generics_0.0.2    vctrs_0.2.1       tools_3.6.2      
[50] glue_1.3.1        hms_0.5.3         parallel_3.6.2    colorspace_1.4-1  rvest_0.3.5       haven_2.2.0      
LS0tCnRpdGxlOiAiUGhhbnRvbVB1cmdlUjogU2ltdWxhdGlvbiBhbmQgUGVyZm9ybWFuY2UgQ29tcGFyaXNvbiIKYXV0aG9yOiAiUmljayBGYXJvdW5pIgpwYWNrYWdlOiBQaGFudG9tUHVyZ2VSCmRhdGU6ICJgciBTeXMuRGF0ZSgpYCIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICBkZl9wcmludDogcGFnZWQKICAgIGNvZGVfZm9sZGluZzogc2hvdwogICAgdG9jOiB5ZXMKICAgIHRvY19mbG9hdDogCiAgICAgIGNvbGxhcHNlZDogZmFsc2UKICAgICAgc21vb3RoX3Njcm9sbDogZmFsc2UKLS0tCgpJbiB0aGlzIG5vdGVib29rZCB3ZSBzaW11bGF0ZSBvdXRjb21lIGRhdGEgYW5kIGNvbXBhcmUgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSBUT1IgYXBwcm9hY2ggd2l0aCBtaW5pbXVtIHJlYWQgZnJhY3Rpb24gKE1SRikgYXBwcm9hY2guCgoKIyBQcmVwYXJhdGlvbnMKCmBgYHtyICwgbWVzc2FnZT1GQUxTRX0KbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocG9pYmluKQpsaWJyYXJ5KGNvbWJpbmF0KQpsaWJyYXJ5KGZ1cnJyKQpsaWJyYXJ5KGRhdGEudGFibGUpCmxpYnJhcnkobWF0cml4U3RhdHMpCmxpYnJhcnkocnByb2pyb290KQpsaWJyYXJ5KGNvd3Bsb3QpCnBsYW4obXVsdGlwcm9jZXNzKQpgYGAKCmBgYHtyIGVjaG89VFJVRSwgbWVzc2FnZT1GQUxTRSwgcmVzdWx0cz0iaGlkZSJ9CnJlcXVpcmUoa25pdHIpCm9wdHNfY2h1bmskc2V0KGVycm9yPUZBTFNFLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFKQprbml0cjo6b3B0c19rbml0JHNldChyb290LmRpciA9IHJwcm9qcm9vdDo6ZmluZF9yc3R1ZGlvX3Jvb3RfZmlsZSgpKQpvcHRpb25zKGZ1dHVyZS5nbG9iYWxzLm1heFNpemU9ICtJbmYsIGZ1dHVyZS5mb3JrLmVuYWJsZT1UUlVFKQpgYGAKCgpgYGB7cn0KZmlndXJlc19kaXIgPC0gZmlsZS5wYXRoKCIuL2ZpZ3VyZXMiKQpgYGAKCiMjIERlZmluZSBGdW5jdGlvbnMKCgoKYGBge3J9CmNyZWF0ZV9kYXRhIDwtIGZ1bmN0aW9uKHByb2IsIHJtYXgsIG5yZWFkcyl7CiAgZHQgPC0gCiAgICB0aWJibGUocj0xOnJtYXgsCiAgICAgICAgICAgcz1kZ2VvbShyLTEsIHByb2JbMV0pICkgJT4lIAogICAgbXV0YXRlKHM9KHMvc3VtKHMpKSkgJT4lCiAgICBtdXRhdGUocnM9IHIqcykKICAKICBSTVIgPC1zdW0oZHQgJT4lIHB1bGwocnMpKQogIG5tb2wgPC0gbnJlYWRzL1JNUgogIAogIGR0IDwtIAogICAgZHQgJT4lIAogICAgbXV0YXRlKHM9IHJvdW5kKG5tb2wqcykpJT4lCiAgICBzZWxlY3QoLXJzKQogIAogIHJldHVybihkdCkKfQoKCgpnZXRfcHJvZHVjdF9sb2dzdW0gPC0gZnVuY3Rpb24oeCwgeSkgewogIHpfbG9nIDwtIGxvZyh4KSArIGxvZyh5KQogIHogPC0gZXhwKHpfbG9nKQogIHJldHVybih6KQp9CgoKZ2VuZXJhdGVfb3V0Y29tZXNfcyA8LSBmdW5jdGlvbihzLCBwLCBTLCByLCBwaV9yKXsKICBwX2ggPC0gKDEgLSBwKSAvIChTIC0gMSkKICBwdmVjIDwtIHJlcChwX2gsIFMpCiAgcHZlY1tzXSA8LSBwCiAgcGlfcl9zIDwtIHBpX3Jbc10KICAKICBvdXRjb21lcyA8LSB4c2ltcGxleChTLCByKQogIAogIHBtZiA8LSBhcHBseShvdXRjb21lcywKICAgICAgICAgICAgICAgMiwKICAgICAgICAgICAgICAgZG1ub20sCiAgICAgICAgICAgICAgIHByb2IgPSBwdmVjKQogIAogIG91dGNvbWVzIDwtIG91dGNvbWVzICAlPiUgCiAgICB0KCkgJT4lCiAgICBhc190aWJibGUoIC5uYW1lX3JlcGFpciA9ICJ1bmlxdWUiKSAlPiUKICAgIHNldE5hbWVzKHBhc3RlMCgieSIsIDE6UykpICU+JQogICAgbXV0YXRlKHBtZl9ycz1wbWYsCiAgICAgICAgICAgcG1mX3I9Z2V0X3Byb2R1Y3RfbG9nc3VtKHBtZiwgcGlfcl9zKSkKICAKICByZXR1cm4ob3V0Y29tZXMpCn0KCgoKY3JlYXRlX2dyb3VwaW5nX3ZhcnMgPC0gZnVuY3Rpb24ob3V0Y29tZXMsIFMsIG1yZikgewogIAogIHMgPC0gCiAgICBvdXRjb21lcyAlPiUKICAgIHB1bGwocykgJT4lCiAgICBhcy5udW1lcmljKCkKICAKICAKICBzZXREVChvdXRjb21lcykKICAKICBvdXRjb21lc1ssCiAgICAgICAgICAgb3V0Y29tZSA6PSBkby5jYWxsKHBhc3RlLCBjKC5TRCwgc2VwID0gIiwiKSksCiAgICAgICAgICAgLlNEY29scyA9IHBhc3RlMCgieSIsIDE6UyldCiAgCiAgb3V0Y29tZSA8LQogICAgb3V0Y29tZXMgJT4lCiAgICBwdWxsKG91dGNvbWUpCiAgCiAgb3V0Y29tZXMgPC0KICAgIG91dGNvbWVzICAlPiUKICAgIHNlbGVjdChjKHBhc3RlMCgieSIsIDE6UykpKSAlPiUKICAgIGFzLm1hdHJpeAogIAogIAogIHlfcyA8LSBhcy5pbnRlZ2VyKG91dGNvbWVzW2NiaW5kKHNlcV9hbG9uZyhzKSwgcyldICE9IDApCiAgCiAgCiAgciA8LSBhcy5pbnRlZ2VyKHJvd1N1bXMyKG91dGNvbWVzKSkKICBrX2NoaW1lcmEgPC0gYXMuaW50ZWdlcihTIC0gcm93Q291bnRzKG91dGNvbWVzLCB2YWx1ZSA9IDApKQogIGZhbnRvbXMgPC0ga19jaGltZXJhIC0geV9zCiAgCiAgCiAgCiAgc19mcmFjXzEgPC0KICAgIGFwcGx5KGNiaW5kKG91dGNvbWVzLHIpLAogICAgICAgICAgMSwKICAgICAgICAgIGZ1bmN0aW9uKHgpIHsKICAgICAgICAgICAgeSA8LSB3aGljaCh4WzE6U10gPj0gICh4W1MgKyAxXSAqbXJmWzFdKSkKICAgICAgICAgICAgeSA8LSB1bm5hbWUoeSkKICAgICAgICAgICAgaWYgKGxlbmd0aCh5KSA9PSAwKQogICAgICAgICAgICAgIHkgPC0gMAogICAgICAgICAgICByZXR1cm4oeSkKICAgICAgICAgIH0pCiAgCiAgc19mcmFjXzIgPC0KICAgIGFwcGx5KGNiaW5kKG91dGNvbWVzLHIpLAogICAgICAgICAgMSwKICAgICAgICAgIGZ1bmN0aW9uKHgpIHsKICAgICAgICAgICAgeSA8LSB3aGljaCh4WzE6U10gPj0gICh4W1MgKyAxXSAqIG1yZlsyXSkpCiAgICAgICAgICAgIHkgPC0gdW5uYW1lKHkpCiAgICAgICAgICAgIGlmIChsZW5ndGgoeSkgPT0gMCkKICAgICAgICAgICAgICB5IDwtIDAKICAgICAgICAgICAgcmV0dXJuKHkpCiAgICAgICAgICB9KQogIAogIAogIHNfZnJhY18zIDwtCiAgICBhcHBseShjYmluZChvdXRjb21lcyxyKSwKICAgICAgICAgIDEsCiAgICAgICAgICBmdW5jdGlvbih4KSB7CiAgICAgICAgICAgIHkgPC0gd2hpY2goeFsxOlNdID49ICAoeFtTICsgMV0qIG1yZlszXSkpCiAgICAgICAgICAgIHkgPC0gdW5uYW1lKHkpCiAgICAgICAgICAgIGlmIChsZW5ndGgoeSkgPT0gMCkKICAgICAgICAgICAgICB5IDwtIDAKICAgICAgICAgICAgcmV0dXJuKHkpCiAgICAgICAgICB9KQogIAogIGdyb3VwaW5nX3ZhcnMgPC0gdGliYmxlKG91dGNvbWU9b3V0Y29tZSwKICAgICAgICAgICAgICAgICAgICAgICAgICByID0gciwKICAgICAgICAgICAgICAgICAgICAgICAgICBzX2ZyYWNfMSA9IHNfZnJhY18xLAogICAgICAgICAgICAgICAgICAgICAgICAgIHNfZnJhY18yID0gc19mcmFjXzIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgc19mcmFjXzMgPSBzX2ZyYWNfMywKICAgICAgICAgICAgICAgICAgICAgICAgICBmYW50b21zID1mYW50b21zLAogICAgICAgICAgICAgICAgICAgICAgICAgIGtfY2hpbWVyYSA9IGtfY2hpbWVyYSkKICAKICByZXR1cm4oZ3JvdXBpbmdfdmFycykKfQoKCmFkZF92YXJzX3RvX291dGNvbWVfY291bnRzIDwtIGZ1bmN0aW9uKG91dGNvbWVzLCBTLCBtcmYpIHsKICAKICBncm91cGluZ192YXJzIDwtIGNyZWF0ZV9ncm91cGluZ192YXJzKG91dGNvbWVzLFMsIG1yZikgCiAgb3V0Y29tZXMgPC0gYmluZF9jb2xzKG91dGNvbWVzLCBncm91cGluZ192YXJzKSAgCiAgCiAgcmV0dXJuKG91dGNvbWVzKQogIAp9CgoKaW5mZXJfc2FtcGxlX29mX29yaWdpbl9vdXRjb21lIDwtIGZ1bmN0aW9uKC4uLiwgcGlfciwgbG9nX3ppLCBTLCBwKSB7CiAgeSA8LSBjKC4uLilbMTpTXQogIGxvZ19zYW1wbGVfcGkgPC0gbG9nKHBpX3IpCiAgcG9zdGVyaW9yX3MgPC0geSAqIGxvZ196aSArIGxvZ19zYW1wbGVfcGkKICAKICAjIyBub3JtYWxpemUgdG8gdGhlIHNhbXBsZSB3aXRoIG1heGltdW0gcG9zdGVyaW9yIHByb2JhYmlsaXR5CiAgcG9zdGVyaW9yX3MgPC0gcG9zdGVyaW9yX3MgLSBtYXgocG9zdGVyaW9yX3MpCiAgcG9zdGVyaW9yX3MgPC0gZXhwKHBvc3Rlcmlvcl9zKQogIAogIHBvc3RlcmlvciA8LSBwb3N0ZXJpb3JfcyAvIHN1bShwb3N0ZXJpb3JfcykKICBxIDwtIG1heChwb3N0ZXJpb3IpCiAgc19oYXQgPC0gd2hpY2gubWF4KHBvc3RlcmlvcikKICAKICBvdXQgPC0gbGlzdChzX2hhdCA9IHNfaGF0LCBxID0gcSkKICByZXR1cm4ob3V0KQp9CgoKYWRkX3Bvc3Rlcmlvcl9wcm9iIDwtIGZ1bmN0aW9uKG91dGNvbWVzLCBTLCBwLCBwaV9yKSB7CiAgCiAgbG9nX3ppIDwtIGxvZygoUyAtIDEpKSAtIGxvZygxIC8gcCAtIDEpCiAgCiAgcG9zdGVyaW9ycyA8LQogICAgZnV0dXJlX3BtYXBfZGZyKAogICAgICBvdXRjb21lcyAlPiUKICAgICAgICBzZWxlY3QocGFzdGUwKCJ5IiwgMTpTKSksCiAgICAgIGluZmVyX3NhbXBsZV9vZl9vcmlnaW5fb3V0Y29tZSwKICAgICAgcGlfcj1waV9yLAogICAgICBsb2dfemkgPSBsb2dfemksCiAgICAgIFM9UywKICAgICAgcD1wCiAgICApCiAgCiAgb3V0Y29tZXMgPC0gYmluZF9jb2xzKG91dGNvbWVzICU+JQogICAgICAgICAgICAgICAgICAgICAgICAgIHNlbGVjdCgtYyhwYXN0ZTAoInkiLCAxOlMpKSksCiAgICAgICAgICAgICAgICAgICAgICAgIHBvc3RlcmlvcnMpCiAgCiAgcmV0dXJuKG91dGNvbWVzKQogIAp9CgoKZ2VuZXJhdGVfb3V0Y29tZXMgPC0gZnVuY3Rpb24oLi4uLHAsIFMsIG1yZil7CiAgCiAgciA8LSBjKC4uLilbMV0KICBwaV9yIDwtIGMoLi4uKVsyOihTKzEpXQogIAogIAogIG91dGNvbWVzIDwtIGZ1dHVyZV9tYXBfZGZyKDE6UywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBnZW5lcmF0ZV9vdXRjb21lc19zLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHA9cCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBTPVMsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcj1yLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBpX3I9cGlfciwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAuaWQgPSAicyIpCiAgCiAgCiAgb3V0Y29tZXMgPC0gYWRkX3ZhcnNfdG9fb3V0Y29tZV9jb3VudHMob3V0Y29tZXMsIFMsIG1yZikKICAKICAKICAKICBvdXRjb21lcyA8LSBhZGRfcG9zdGVyaW9yX3Byb2Iob3V0Y29tZXMsIFMsIHAsIHBpX3IpIAogIAogIAogIG91dGNvbWVzIDwtIAogICAgb3V0Y29tZXMgJT4lCiAgICBtdXRhdGUocz0gYXMuaW50ZWdlcihzKSAsCiAgICAgICAgICAgc19mcmFjXzE9IGFzLmludGVnZXIoc19mcmFjXzEpLAogICAgICAgICAgIHNfZnJhY18yPSBhcy5pbnRlZ2VyKHNfZnJhY18yKSwKICAgICAgICAgICBzX2ZyYWNfMz0gYXMuaW50ZWdlcihzX2ZyYWNfMyksCiAgICAgICAgICAgcj1hcy5pbnRlZ2VyKHIpKQogIAogIHJldHVybihvdXRjb21lcykKfQoKCmV2YWx1YXRlX2NsYXNzaWZpY2F0aW9uIDwtIGZ1bmN0aW9uKG91dGNvbWVzKSB7CiAgCiAgCiAgb3V0Y29tZXMgPC0gCiAgICBvdXRjb21lcyAlPiUKICAgIG11dGF0ZSgKICAgICAgaGl0X3M9IHM9PXNfaGF0LAogICAgICBoaXRfZnJhY18xPSBzPT1zX2ZyYWNfMSwKICAgICAgaGl0X2ZyYWNfMj0gcz09c19mcmFjXzIsCiAgICAgIGhpdF9mcmFjXzM9IHM9PXNfZnJhY18zLAogICAgICBrX2NoaW1lcmFfcD1nZXRfcHJvZHVjdF9sb2dzdW0oa19jaGltZXJhLCBwbWYpLAogICAgICBmYW50b21zX3A9Z2V0X3Byb2R1Y3RfbG9nc3VtKGZhbnRvbXMsIHBtZiksCiAgICAgIGc9KDEtKGtfY2hpbWVyYS1mYW50b21zKSkqcG1mLAogICAgICBxciA9IDEgLSBxKSAgCiAgCiAgZ190b3RhbCA8LSAgCiAgICBvdXRjb21lcyAlPiUKICAgIHN1bW1hcmlzZV9hdCh2YXJzKGMoImciKSksIHN1bSkgICU+JQogICAgcHVsbChnKQogIAogIG91dGNvbWVzPC0KICAgIG91dGNvbWVzICU+JQogICAgYXJyYW5nZShxciklPiUKICAgIG11dGF0ZSgKICAgICAgbyA9IGN1bXN1bShwbWYpLAogICAgICBGUCA9IGN1bXN1bShnZXRfcHJvZHVjdF9sb2dzdW0oCiAgICAgICAgcXIsCiAgICAgICAgcG1mCiAgICAgICkpLAogICAgICBGTj0xIC0gbyArIEZQLWdfdG90YWwsCiAgICAgIEZQbT0gbGFzdChGUCktIEZQLCAjIG1hcmdpbmFsCiAgICAgIEZObT1GTi1sYXN0KEZOKSwgIyBtYXJnaW5hbAogICAgICB0b3I9aWZfZWxzZShGUG0gPC5NYWNoaW5lJGRvdWJsZS5uZWcuZXBzIHwgRk5tIDwuTWFjaGluZSRkb3VibGUubmVnLmVwcywKICAgICAgICAgICAgICAgICAgMCwKICAgICAgICAgICAgICAgICAgRk5tL0ZQbSksCiAgICAgIEZQXzE9Y2FzZV93aGVuKAogICAgICAgICFoaXRfZnJhY18xICYgc19mcmFjXzEhPTAgfiBwbWYsCiAgICAgICAgVFJVRSB+MCksCiAgICAgIEZOXzE9Y2FzZV93aGVuKHNfZnJhY18xPT0wICYgZz09MCB+IHBtZiwKICAgICAgICAgICAgICAgICAgICAgIWhpdF9mcmFjXzEgJiBzX2ZyYWNfMSE9MCAgJiBnPT0wIH4gcG1mLAogICAgICAgICAgICAgICAgICAgICBUUlVFIH4wKSwKICAgICAgRlBfMj1jYXNlX3doZW4oCiAgICAgICAgIWhpdF9mcmFjXzIgJiBzX2ZyYWNfMiE9MCB+IHBtZiwKICAgICAgICBUUlVFIH4wKSwKICAgICAgRk5fMj1jYXNlX3doZW4oc19mcmFjXzI9PTAgJiBnPT0wIH4gcG1mLAogICAgICAgICAgICAgICAgICAgICAhaGl0X2ZyYWNfMiAmIHNfZnJhY18yIT0wICAmIGc9PTAgfiBwbWYsCiAgICAgICAgICAgICAgICAgICAgIFRSVUUgfjApLAogICAgICBGUF8zPWNhc2Vfd2hlbigKICAgICAgICAhaGl0X2ZyYWNfMyAmIHNfZnJhY18zIT0wIH4gcG1mLAogICAgICAgIFRSVUUgfjApLAogICAgICBGTl8zPWNhc2Vfd2hlbihzX2ZyYWNfMz09MCAmIGc9PTAgfiBwbWYsCiAgICAgICAgICAgICAgICAgICAgICFoaXRfZnJhY18zICYgc19mcmFjXzMhPTAgICYgZz09MCB+IHBtZiwKICAgICAgICAgICAgICAgICAgICAgVFJVRSB+MCkpCiAgCiAgCiAgcmV0dXJuKG91dGNvbWVzKQogIAp9Cgpjb21wdXRlX2NsYXNzaWZpY2F0aW9uX21ldHJpY3MgPC0gZnVuY3Rpb24ocCwgcGlfcixtX2RmLCB0b3JjLCBtcmYpewogIAogIG91dGNvbWVzIDwtICAKICAgIGZ1dHVyZV9wbWFwX2RmcihwaV9yLAogICAgICAgICAgICAgICAgICAgIGdlbmVyYXRlX291dGNvbWVzLAogICAgICAgICAgICAgICAgICAgIHA9cCwKICAgICAgICAgICAgICAgICAgICBTPVMsCiAgICAgICAgICAgICAgICAgICAgbXJmPW1yZikKICAKICBvdXRjb21lcyA8LSAKICAgIGxlZnRfam9pbihvdXRjb21lcyAsCiAgICAgICAgICAgICAgbV9kZiwgCiAgICAgICAgICAgICAgYnk9InIiKSAlPiUKICAgIG11dGF0ZSgKICAgICAgcG1mPSBnZXRfcHJvZHVjdF9sb2dzdW0ocG1mX3IsbSkpJT4lCiAgICBzZWxlY3QoLWMoIm0iLCJwbWZfcnMiLCJwbWZfciIpKSAKICAKICBvdXRjb21lcyA8LSBldmFsdWF0ZV9jbGFzc2lmaWNhdGlvbihvdXRjb21lcykgCiAgCiAgCiAgdG9yX3RocmVzaCA8LQogICAgb3V0Y29tZXMgJT4lCiAgICBzdW1tYXJpemUodG9yX3RocmVzaCA9IHRvclt3aGljaC5tYXgoLXBtYXgodG9yLCB0b3JjKSldKSAlPiUKICAgIHB1bGwodG9yX3RocmVzaCkKICAKICAKICBtZXRyaWNzX3RvciA8LQogICAgb3V0Y29tZXMgJT4lCiAgICBmaWx0ZXIodG9yID09IHRvcl90aHJlc2gpICU+JQogICAgc2xpY2UoMSkgICU+JQogICAgc2VsZWN0KEZQLCBGTiwgdG9yKSAlPiUKICAgIHJlbmFtZShjdXRvZmYgPSAidG9yIikgJT4lCiAgICBtdXRhdGUoY3V0b2ZmID0gcGFzdGUwKCJ0b3JfIiwgc3RyX3N1YigKICAgICAgYXMuY2hhcmFjdGVyKGN1dG9mZiksCiAgICAgIHN0YXJ0ID0gMSwKICAgICAgZW5kID0gNAogICAgKSkpCiAgCiAgCiAgbWF4ZnJhY19mcCA8LQogICAgb3V0Y29tZXMgJT4lCiAgICBzdW1tYXJpc2VfYXQodmFycyhzdGFydHNfd2l0aCgiRlBfIikpLCBzdW0pICU+JQogICAgZ2F0aGVyKGNvbmRpdGlvbiwgRlApICU+JQogICAgc2VsZWN0KEZQKQogIAogIG1heGZyYWNfZm4gPC0KICAgIG91dGNvbWVzICU+JQogICAgc3VtbWFyaXNlX2F0KHZhcnMoc3RhcnRzX3dpdGgoIkZOXyIpKSwgc3VtKSAgJT4lCiAgICBnYXRoZXIoY29uZGl0aW9uLCBGTikgJT4lCiAgICBzZWxlY3QoRk4pCgogIG1ldHJpY3NfZHQgPC0gYmluZF9jb2xzKG1heGZyYWNfZnAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgbWF4ZnJhY19mbikgJT4lCiAgICAKICAgIG11dGF0ZShjdXRvZmYgPSBzcHJpbnRmKCJtZl8lLjJmIiwgbXJmKSkgJT4lCiAgICBiaW5kX3Jvd3MoLiwgbWV0cmljc190b3IpICU+JQogICAgc2VsZWN0KGN1dG9mZiwgZXZlcnl0aGluZygpKQogIAogIAogIHRvcl9kdCA8LQogICAgb3V0Y29tZXMgJT4lCiAgICBmaWx0ZXIodG9yIDwgMTAgJiB0b3IgPiAxICYgZyA9PSAwKSAlPiUKICAgIG11dGF0ZSh0b3IgPSByb3VuZCh0b3IsIDQpKSAlPiUKICAgIGdyb3VwX2J5KHRvcikgJT4lCiAgICBmaWx0ZXIocm93X251bWJlcigpID09IDEpCiAgCiAgCiAgcmV0dXJuKGxpc3QodG9yX2R0PXRvcl9kdCwgIG1ldHJpY3NfZHQ9IG1ldHJpY3NfZHQpKQp9CgoKcGxvdF9QaSA8LSBmdW5jdGlvbihQaSwgUGlfbWFyZ2luYWwpIHsKICBwMSA8LQogICAgZ2dwbG90KFBpICU+JQogICAgICAgICAgICAgc2VsZWN0KAogICAgICAgICAgICAgICAtc3VtX21vbHMKICAgICAgICAgICAgICkgJT4lCiAgICAgICAgICAgICBnYXRoZXIoc2FtcGxlLCBwLCAtYygiciIpKSkgKwogICAgZ2VvbV9saW5lKGFlcygKICAgICAgeCA9IHIsCiAgICAgIHkgPSBwLAogICAgICBjb2xvdXIgPSBzYW1wbGUKICAgICksCiAgICBzaXplID0gMSwKICAgIGFscGhhID0gMQogICAgKSArCiAgICBnZW9tX3BvaW50KAogICAgICBkYXRhID0gUGkgJT4lCiAgICAgICAgc2VsZWN0KHIsIG0pLAogICAgICBhZXMoeCA9IHIsIHkgPSBtKSwKICAgICAgc2hhcGUgPSAxMCwKICAgICAgc2l6ZSA9IDEsCiAgICAgIGFscGhhID0gLjkKICAgICkgKwogICAgdGhlbWVfYncoKSArCiAgICBnZW9tX2hsaW5lKAogICAgICBkYXRhID0gUGlfbWFyZ2luYWwsCiAgICAgIGFlcygKICAgICAgICB5aW50ZXJjZXB0ID0gcF9tb2xlY3MsCiAgICAgICAgY29sb3VyID0gc2FtcGxlCiAgICAgICksCiAgICAgIHNpemUgPSAwLjMsCiAgICAgIGxpbmV0eXBlID0gImxvbmdkYXNoIiwKICAgICAgYWxwaGEgPSAxCiAgICApICsKICAgIGxhYnMoCiAgICAgIHggPSAiciAoUENSIGR1cGxpY2F0ZXMpIiwKICAgICAgeSA9ICJwcm9wb3J0aW9uIgogICAgKSArCiAgICBzY2FsZV9jb2xvdXJfdmlyaWRpc19kKAogICAgICBvcHRpb24gPSAiaW5mZXJubyIsCiAgICAgIGRpcmVjdGlvbiA9IC0xCiAgICApICsKICAgIHRoZW1lKAogICAgICBheGlzLnRpdGxlLnggPSBlbGVtZW50X3RleHQoc2l6ZSA9IHJlbCgxLjQpKSwKICAgICAgYXhpcy50aXRsZS55ID0gZWxlbWVudF90ZXh0KHNpemUgPSByZWwoMS40KSksCiAgICAgIGF4aXMudGV4dCA9IGVsZW1lbnRfdGV4dChzaXplID0gcmVsKDEuMykpLAogICAgICBsZWdlbmQudGl0bGUgPSBlbGVtZW50X3RleHQoc2l6ZSA9IHJlbCgxLjEpLCBmYWNlID0gImJvbGQiKSwKICAgICAgbGVnZW5kLnRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IHJlbCgxLjEpKQogICAgKQogIHJldHVybihwMSkKfQoKCnBsb3RfdHJhZGVfb2ZmIDwtIGZ1bmN0aW9uKGNvbmRpdGlvbiwgY29uZGl0aW9uX25hbWUpewogIAogIGNvbmRpdGlvbiRtZXRyaWNzX2R0JGN1dG9mZls0XSA8LSAidG9yKiIKICAKICBwIDwtIGdncGxvdChjb25kaXRpb24kdG9yX2R0KSArIAogICAgZ2VvbV9saW5lKAogICAgICBhZXMoeCA9IEZQLAogICAgICAgICAgeSA9IEZOKSwKICAgICAgY29sb3VyPSJncmV5IikrCiAgICBnZW9tX3BvaW50KAogICAgICBhZXMoeCA9IEZQLAogICAgICAgICAgeSA9IEZOLAogICAgICAgICAgY29sb3I9dG9yKSwKICAgICAgc2l6ZT0uNSwKICAgICAgYWxwaGE9LjgpKwogICAgc2NhbGVfY29sb3JfdmlyaWRpc19jKCkgKwogICAgbGFicyh4PSJGYWxzZSBQb3NpdGl2ZXMiLAogICAgICAgICB5PSJGYWxzZSBOZWdhdGl2ZXMiKSArCiAgICBnZW9tX3BvaW50KGRhdGE9Y29uZGl0aW9uJG1ldHJpY3NfZHQsCiAgICAgICAgICAgICAgIGFlcyh4ID0gRlAsCiAgICAgICAgICAgICAgICAgICB5ID0gRk4sCiAgICAgICAgICAgICAgICAgICBzaGFwZT1jdXRvZmYpLAogICAgICAgICAgICAgICBzaXplPTEuOCwKICAgICAgICAgICAgICAgY29sb3VyPSJicm93biIpKwogICAgdGhlbWVfYncoKSAgKwogICAgI3NjYWxlX3lfc3FydCgpKwogICAgdGhlbWUoCiAgICAgIGxlZ2VuZC50aXRsZSA9IGVsZW1lbnRfdGV4dChmYWNlID0gImJvbGQiKQogICAgKSArCiAgICBleHBhbmRfbGltaXRzKHggPSBjKDAsIC4wMDYpLCB5ID0gYygwLCAwLjA0KSkKICAKICBsZWdlbmQgPC0gZ2V0X2xlZ2VuZChwKQogIHAgPC0gcCArIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKICAKICBwIDwtIGdnZHJhdygpICsKICAgIGRyYXdfcGxvdChwLCAwLCAwLCAxLCAxKSArCiAgICBkcmF3X2xhYmVsKHBhc3RlMCgiU0lIUj0iLCBjb25kaXRpb25fbmFtZSksCiAgICAgICAgICAgICAgIHggPSAwLAogICAgICAgICAgICAgICB5ID0gMSwKICAgICAgICAgICAgICAgdmp1c3QgPSAyLAogICAgICAgICAgICAgICBoanVzdCA9IC0xLjgsCiAgICAgICAgICAgICAgIHNpemUgPSAxMiwKICAgICAgICAgICAgICAgZm9udGZhY2UgPSAiaXRhbGljIgogICAgKQogIAogIHJldHVybihsaXN0KHA9cCwgbGVnZW5kPWxlZ2VuZCkpCn0KCnBsb3RfdHJhZGVfb2ZmX2FsbCA8LSBmdW5jdGlvbihtZXRyaWNzX2xpc3QpIHsKICAKICBwX3RyYWRlb2ZmIDwtIGltYXAobWV0cmljc19saXN0LCBwbG90X3RyYWRlX29mZikKICAKICBwX2xpc3QgPC0gCiAgICBwX3RyYWRlb2ZmICU+JQogICAgbWFwKGxpc3QoInAiKSkKICAKICBsZWdlbmRfbGlzdCA8LSAKICAgIHBfdHJhZGVvZmYgJT4lIAogICAgbWFwKGxpc3QoImxlZ2VuZCIpKQogIAogIHBfdHJhZGVvZmZfYWxsIDwtIAogICAgcGxvdF9ncmlkKAogICAgICBwbG90X2dyaWQocF9saXN0W1sxXV0sCiAgICAgICAgICAgICAgICBwX2xpc3RbWzJdXSwKICAgICAgICAgICAgICAgIHBfbGlzdFtbM11dLCAKICAgICAgICAgICAgICAgIHBfbGlzdFtbNF1dLAogICAgICAgICAgICAgICAgYWxpZ249Imh2IiwKICAgICAgICAgICAgICAgIGF4aXMgPSJ0YmxyIiksCiAgICAgIHBsb3RfZ3JpZChOVUxMLAogICAgICAgICAgICAgICAgbGVnZW5kX2xpc3RbWzRdXSwgCiAgICAgICAgICAgICAgICBOVUxMLAogICAgICAgICAgICAgICAgbmNvbD0xKSwKICAgICAgcmVsX3dpZHRocz1jKDEsIDAuMSkpCiAgCiAgcmV0dXJuKHBfdHJhZGVvZmZfYWxsKQogIAp9CgpzaW11bGF0ZV9waSA8LSBmdW5jdGlvbihwcm9iICwgcm1heCwgbnJlYWRzPTNlNyApewogIAogIHNhbXBsZV9uYW1lcyA8LSBwYXN0ZTAoInMiLCAxOmxlbmd0aChwcm9iKSkKICBuYW1lcyhwcm9iKSAgPC0gc2FtcGxlX25hbWVzIAogIAogIGR0IDwtCiAgICBtYXBfZGZyKHByb2IsIAogICAgICAgICAgICBjcmVhdGVfZGF0YSwKICAgICAgICAgICAgcm1heD1ybWF4LAogICAgICAgICAgICBucmVhZHM9bnJlYWRzLAogICAgICAgICAgICAuaWQ9InNhbXBsZSIpICU+JQogICAgc3ByZWFkKHNhbXBsZSwgcykKICAKICBkdF9zdW1tYXJ5IDwtCiAgICBkdCAlPiUKICAgIHNlbGVjdCgtcikgJT4lCiAgICBzdW1tYXJpemVfYWxsKHN1bSkgJT4lCiAgICBnYXRoZXIoc2FtcGxlLCBubW9scykgJT4lCiAgICBtdXRhdGUoUk1SPW5yZWFkcy9ubW9scywKICAgICAgICAgICBwZ2VvbV9wcm9iPXByb2IsCiAgICAgICAgICAgcF9tb2xlY3M9bm1vbHMvc3VtKG5tb2xzKSkKICAKICBkdCA8LSBkdCAlPiUKICAgIG11dGF0ZShzdW1fbW9scyA9IHJvd1N1bXMoLltzYW1wbGVfbmFtZXNdKSkgJT4lCiAgICBtdXRhdGVfYXQodmFycyhzYW1wbGVfbmFtZXMpLCB+IC4gLyBzdW1fbW9scykgJT4lCiAgICBtdXRhdGUobT0gc3VtX21vbHMvc3VtKHN1bV9tb2xzKSkKICAKICByZXR1cm4obGlzdChQaT1kdCwgc3VtbWFyeT1kdF9zdW1tYXJ5KSkKfQoKCnNpbXVsYXRlX2RhdGEgPC0gZnVuY3Rpb24ocHJvYiwgcHZlYywgcm1heCwgdG9yYywgbXJmKXsKICBwaV9vdXQgPC0gc2ltdWxhdGVfcGkocHJvYiwgcm1heCkKICBtX2RmIDwtIHBpX291dCRQaSAlPiUgc2VsZWN0KHIsIG0pCiAgcGlfciA8LSBwaV9vdXQkUGkgJT4lIHNlbGVjdCgtbSwgLXN1bV9tb2xzKQogIAogIG1ldHJpY3NfbGlzdCA8LQogICAgbWFwKHB2ZWMsCiAgICAgICAgY29tcHV0ZV9jbGFzc2lmaWNhdGlvbl9tZXRyaWNzLAogICAgICAgIHBpX3I9cGlfciwKICAgICAgICBtX2RmPW1fZGYsCiAgICAgICAgdG9yYz10b3JjLAogICAgICAgIG1yZj1tcmYpCiAgCiAgcmV0dXJuKGxpc3QobWV0cmljc19saXN0PW1ldHJpY3NfbGlzdCwgcGlfb3V0PXBpX291dCkpCn0KYGBgCgoKIyMgU2ltdWxhdGUgTW9sZWN1bGFyIENvbXBsZXhpdHkgUHJvZmlsZSAKCgojIyMgU2V0IHBhcmFtZXRlcnMKCmBgYHtyfQpTIDwtIDQgICMgc2FtcGxlIG51bWJlcgpybWF4IDwtIDMwICMgUENSIGFtcGxpZmljYXRpb24gbGltaXQKdG9yYyA8LSAzICMgVHJhZGUgb2ZmIGN1dG9mZgptcmYgPC0gYygwLjYsIDAuOCwgMC45KSAjdGhyZWUgY2hvaWNlcyBmb3IgdGhlIG1pbmltdW0gcmVhZCBmcmFjdGlvbiAoTVJGKSB0aHJlc2hvbGRzLiAwLjggaXMgdGhlIGRlZmF1bHQKcHZlYyA8LSBjKDAuOTgyLCAwLjk4NiwgMC45OTAsIDAuOTk0KSAjIHByb2JhYmlsaXR5IG9mIG5vdCBob3BwaW5nICg0IHNldHRpbmdzKQpuYW1lcyhwdmVjKSA8LSBjKDAuMDE4LCAwLjAxNCwgMC4wMTAsIDAuMDA2KSAjIG5hbWUgdmVjdG9yIHdpdGggU0lIUiAoaS5lLiBob3BwaW5nIHJhdGUgb3IgMS1wdmVjKSAKcHZlYyAKYGBgCgoKIyMjIFNpbXVsYXRlIGRhdGEgZm9yIHBhcmFtZXRlciBzZXR0aW5nIDEKClNldCB0aGUgcGFyYW1ldGVyIHZhbHVlcyBmb3IgdGhlIHRydW5jYXRlZCBnZW9tZXRyaWMgZGlzdHJpYnV0aW9ucyBmb3IgdGhlIFMgc2FtcGxlcwoKYGBge3J9CnByb2IxIDwtIGMoIDAuNDUsIDAuNCwgMC4xLCAgMC4wNSkgCmBgYAoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0Kb3V0XzEgPC0gc2ltdWxhdGVfZGF0YShwcm9iMSwgcHZlYyxybWF4LCB0b3JjLCBtcmYpIApgYGAKCmBgYHtyfQpvdXRfMSRwaV9vdXQkc3VtbWFyeQpgYGAKClBsb3QgdGhlIG1vbGVjdWxhciBwcm9wb3J0aW9ucyBjb21wbGV4aXR5IHByb2ZpbGUKCgpgYGB7ciBmaWcud2lkdGg9MTJ9CnBsb3RfUGkob3V0XzEkcGlfb3V0JFBpLCBvdXRfMSRwaV9vdXQkc3VtbWFyeSkKYGBgCgpTaG93IHRoZSByZXN1bHRzCgpgYGB7cn0Kb3V0XzEkbWV0cmljc19saXN0CmBgYAoKUGxvdCB0aGUgcmVzdWx0cwoKCmBgYHtyLCBmaWcud2lkdGg9MTJ9CgpwX3RyYWRlX29mZl8xIDwtIHBsb3RfdHJhZGVfb2ZmX2FsbChvdXRfMSRtZXRyaWNzX2xpc3QpIApwX3RyYWRlX29mZl8xIApgYGAKCiMgc2F2ZSBwbG90CgpgYGB7cn0Kc2F2ZV9wbG90KGZpbGUucGF0aChmaWd1cmVzX2RpciwgInNpbXVsYXRpb25fdHJhZG9mZjAxLnBkZiIpLCAKICAgICAgICAgIHBfdHJhZGVfb2ZmXzEsCiAgICAgICAgICBuY29sID0gMywgIyB3ZSdyZSBzYXZpbmcgYSBncmlkIHBsb3Qgb2YgMiBjb2x1bW5zCiAgICAgICAgICBucm93ID0gMiwgIyBhbmQgMiByb3dzCiAgICAgICAgICBiYXNlX2hlaWdodD00LAogICAgICAgICAgIyBlYWNoIGluZGl2aWR1YWwgc3VicGxvdCBzaG91bGQgaGF2ZSBhbiBhc3BlY3QgcmF0aW8gb2YgMS4zCiAgICAgICAgICBiYXNlX2FzcGVjdF9yYXRpbyA9IDEKKQpgYGAKCgojIyMgU2ltdWxhdGUgZGF0YSBmb3IgcGFyYW1ldGVyIHNldHRpbmcgMgoKYGBge3J9CnByb2IyIDwtIGMoIDAuNDUsIDAuNDIsIDAuNDAsICAwLjA1KQpgYGAKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9Cm91dF8yIDwtIHNpbXVsYXRlX2RhdGEocHJvYjIsIHB2ZWMscm1heCwgdG9yYywgbXJmKSAKYGBgCgpgYGB7cn0Kb3V0XzIkcGlfb3V0JHN1bW1hcnkKYGBgCgoKYGBge3IgZmlnLndpZHRoPTEyfQpwbG90X1BpKG91dF8yJHBpX291dCRQaSwgb3V0XzIkcGlfb3V0JHN1bW1hcnkpCmBgYAoKCmBgYHtyfQpvdXRfMiRtZXRyaWNzX2xpc3QKYGBgCgojIyBQbG90IHJlc3VsdHMKCgpgYGB7ciwgZmlnLndpZHRoPTEyfQoKcF90cmFkZV9vZmZfMiA8LSBwbG90X3RyYWRlX29mZl9hbGwob3V0XzIkbWV0cmljc19saXN0KSAKcF90cmFkZV9vZmZfMgpgYGAKCiMgc2F2ZSBwbG90CgpgYGB7cn0Kc2F2ZV9wbG90KGZpbGUucGF0aChmaWd1cmVzX2RpciwgInNpbXVsYXRpb25fdHJhZG9mZjAyLnBkZiIpLCAKICAgICAgICAgIHBfdHJhZGVfb2ZmXzIsCiAgICAgICAgICBuY29sID0gMywgIyB3ZSdyZSBzYXZpbmcgYSBncmlkIHBsb3Qgb2YgMiBjb2x1bW5zCiAgICAgICAgICBucm93ID0gMiwgIyBhbmQgMiByb3dzCiAgICAgICAgICBiYXNlX2hlaWdodD00LAogICAgICAgICAgIyBlYWNoIGluZGl2aWR1YWwgc3VicGxvdCBzaG91bGQgaGF2ZSBhbiBhc3BlY3QgcmF0aW8gb2YgMS4zCiAgICAgICAgICBiYXNlX2FzcGVjdF9yYXRpbyA9IDEKKQpgYGAKCgpgYGB7cn0Kc2Vzc2lvbkluZm8oKQpgYGAKCgo=