1 R for Problem Solving

Quando si comincia ad entrare nell’ottica della programmazione e data manipulation, si possono risolvere molti problemi concreti in modo creativo, riproducibile e anche efficiente. Generalmente ci sono due modi di affrontare problemi concreti nella vita accademica di tutti i giorni:

  • one-shot
  • take your time

Il modo one-shot è quello (apparentemente) più rapido, immediato e (apparentemente) efficiente. Ad esempio:

Questionario somministrato a 100 persone. Scarico i dati dalla piattaforma di somministrazione ed eseguo delle operazioni manualmente (ricodifica item, eliminare delle righe/colonne).

  • Pros: concludo in poco tempo il lavoro (dipende sempre dal lavoro)
  • Cons: Se i dati in input cambiano o aumentano devo ricominciare
  • Probabilità di errori: alta

Il metodo take your time prevede di investire anche molto tempo per capire il problema, sviluppare una soluzione riproducibile (ed eventualmente applicabile anche altre volte) e poi applicarla indipendentemente dall’input.

  • Pros: in caso di errori o cambiamenti non devo rifare nulla
  • Cons: devo saperlo fare e investire più tempo inizialmente
  • Probabilità di errori: bassa (o comunque controllabile)

2 Correlazioni in sottogruppi

Un altro problema che spesso si incontra è quello di applicare operazioni, manipolazioni o statistiche a solo un sotto-gruppo di elementi di un dataset. In questo caso l’idea è di partire con un dataframe ben organizzato per poi selezionare solo le righe/colonne che ci interessano. Facciamo un esempio di un ipotetico dataframe con 4 gruppi, e 4 variabili da correlare:

# simuliamo i dati
ngroups <- 4
nsample <- 20
cordat_long <- faux::rnorm_multi(ngroups * nsample, mu = c(0, 0, 0, 0), sd = 1, r = 0.7)
names(cordat_long) <- paste0("y", 1:4)

# creiamo i gruppi
cordat_long$group <- rep(c("g1", "g2", "g3", "g4"), each = nsample) # colonna che identifica il gruppo
cordat_long$id <- rep(1:nsample, ngroups) # colonna che identifica il soggetto dentro il gruppo
head(cordat_long)                                                                                                                                                  
##           y1          y2          y3          y4 group id
## 1 -0.3907054 -0.10418786 -1.14739655  0.62415156    g1  1
## 2  0.7566390  1.19353030  0.41739875  0.55210250    g1  2
## 3 -0.1988493 -0.07532804 -0.07230436 -0.03730916    g1  3
## 4  0.9674661  0.81599485  0.28159492  1.71803443    g1  4
## 5  0.3847578  0.85751760  1.00767355  1.30495711    g1  5
## 6  1.4592939  0.76407362  1.00865915  1.43983568    g1  6

Quello che abbiamo creato è un dataframe in forma lunga o long e consiste nell’avere le variabili dipendenti come colonne separate e quelle indipendenti organizzate in riga. In altri termini abbiamo ogni riga come 1 osservazione e la colonna gruppo come unica. L’alternativa è usare il formato wide (sconsigliato in questo caso):

cordat_wide <- tidyr::pivot_wider(cordat_long, names_from = group, values_from = c(y1, y2, y3, y4))
head(cordat_wide)
## # A tibble: 6 × 17
##      id  y1_g1   y1_g2  y1_g3  y1_g4   y2_g1  y2_g2  y2_g3  y2_g4   y3_g1   y3_g2
##   <int>  <dbl>   <dbl>  <dbl>  <dbl>   <dbl>  <dbl>  <dbl>  <dbl>   <dbl>   <dbl>
## 1     1 -0.391 -1.30    0.922  0.234 -0.104  -2.24   0.466 -0.497 -1.15   -1.97  
## 2     2  0.757 -0.426   1.57   0.436  1.19   -0.372  0.268  0.279  0.417  -0.233 
## 3     3 -0.199  0.678  -0.206  0.775 -0.0753 -0.801  0.977  0.967 -0.0723  0.0835
## 4     4  0.967 -0.0695 -0.858 -0.260  0.816  -0.553 -0.271  0.238  0.282   0.431 
## 5     5  0.385  0.0151 -1.01  -0.747  0.858   0.109 -1.01  -0.861  1.01    0.456 
## 6     6  1.46   0.369   0.941 -1.06   0.764   0.733  0.428 -0.967  1.01    0.489 
## # ℹ 6 more variables: y3_g3 <dbl>, y3_g4 <dbl>, y4_g1 <dbl>, y4_g2 <dbl>,
## #   y4_g3 <dbl>, y4_g4 <dbl>

Seppur il formato wide possa sembrare più intuitivo, la maggior parte dei pacchetti per fare analisi, grafici o altro lavora meglio se il dataframe è in formato long. Forse l’unico caso dove il formato wide è consigliato è lavorare con le correlazioni MA in questo caso visto che ci sono 4 gruppi e diverse variabili è comunque meglio quello long. Ma vediamo la soluzione in entrambi i casi.

Il risultato che vogliamo ottenere è quello di calcolare una matrice di correlazione tra le 4 variabili dipendenti indipendentemente per ogni sottogruppo di partecipanti. Il modo più semplice è quello di fare un subset del nostro dataframe e applicare la funzione cor o qualsiasi altra operazione.

cor(cordat_long[cordat_long$group == "g1", c("y1", "y2", "y3", "y4")])
##           y1        y2        y3        y4
## y1 1.0000000 0.7036695 0.7007338 0.7048780
## y2 0.7036695 1.0000000 0.7216552 0.7049523
## y3 0.7007338 0.7216552 1.0000000 0.5310279
## y4 0.7048780 0.7049523 0.5310279 1.0000000
cor(cordat_long[cordat_long$group == "g2", c("y1", "y2", "y3", "y4")])
##           y1        y2        y3        y4
## y1 1.0000000 0.4309987 0.6618698 0.6839404
## y2 0.4309987 1.0000000 0.7179861 0.6043282
## y3 0.6618698 0.7179861 1.0000000 0.7842218
## y4 0.6839404 0.6043282 0.7842218 1.0000000
cor(cordat_long[cordat_long$group == "g3", c("y1", "y2", "y3", "y4")])
##           y1        y2        y3        y4
## y1 1.0000000 0.6255719 0.7487112 0.6494289
## y2 0.6255719 1.0000000 0.8234187 0.7218656
## y3 0.7487112 0.8234187 1.0000000 0.8299013
## y4 0.6494289 0.7218656 0.8299013 1.0000000
cor(cordat_long[cordat_long$group == "g4", c("y1", "y2", "y3", "y4")])
##           y1        y2        y3        y4
## y1 1.0000000 0.6822066 0.7670467 0.6369017
## y2 0.6822066 1.0000000 0.7495865 0.7120413
## y3 0.7670467 0.7495865 1.0000000 0.6370760
## y4 0.6369017 0.7120413 0.6370760 1.0000000

In questo caso stiamo ripetendo molto codice ma il principio è lo stesso. Applicare la funzione cor ad ogni sottogruppo. Possiamo per esempio renderlo più efficiente usando una procedura iterativa come un for oppure una funzione *apply. Vediamo la soluzione con for:

var_for_cor <- c("y1", "y2", "y3", "y4") # per convenienza metto le colonne da considerare qui
cormats <- vector(mode = "list", length = length(unique(cordat_long$group))) # inizializzo una lista vuota per essere più efficiente

# itero per la lunghezza di cormats che equivale a quanti gruppi abbiamo e applico la funzione cor selezionando un gruppo alla volta
for(i in 1:length(cormats)){
    cormats[[i]] <- cor(cordat_long[cordat_long$group == unique(cordat_long$group)[i], var_for_cor])
}

Vediamo la soluzione con lapply ragionando in modo simile al for:

# non serve inizializzare perchè lo fa già internamente. Itero su un vettore con i valori dei gruppi e seleziono
cormats <- lapply(unique(cordat_long$group), function(group) cor(cordat_long[cordat_long$group == group, var_for_cor]))
cormats
## [[1]]
##           y1        y2        y3        y4
## y1 1.0000000 0.7036695 0.7007338 0.7048780
## y2 0.7036695 1.0000000 0.7216552 0.7049523
## y3 0.7007338 0.7216552 1.0000000 0.5310279
## y4 0.7048780 0.7049523 0.5310279 1.0000000
## 
## [[2]]
##           y1        y2        y3        y4
## y1 1.0000000 0.4309987 0.6618698 0.6839404
## y2 0.4309987 1.0000000 0.7179861 0.6043282
## y3 0.6618698 0.7179861 1.0000000 0.7842218
## y4 0.6839404 0.6043282 0.7842218 1.0000000
## 
## [[3]]
##           y1        y2        y3        y4
## y1 1.0000000 0.6255719 0.7487112 0.6494289
## y2 0.6255719 1.0000000 0.8234187 0.7218656
## y3 0.7487112 0.8234187 1.0000000 0.8299013
## y4 0.6494289 0.7218656 0.8299013 1.0000000
## 
## [[4]]
##           y1        y2        y3        y4
## y1 1.0000000 0.6822066 0.7670467 0.6369017
## y2 0.6822066 1.0000000 0.7495865 0.7120413
## y3 0.7670467 0.7495865 1.0000000 0.6370760
## y4 0.6369017 0.7120413 0.6370760 1.0000000

Vediamo la soluzione con lapply ma in modo ancora più compatto usando la funzione ?split per scomporre i dataframe fuori dalla funzione iterativa:

cordat_long_split <- split(cordat_long, cordat_long$group)
cormats <- lapply(cordat_long_split, function(x) cor(x[, var_for_cor]))
cormats
## $g1
##           y1        y2        y3        y4
## y1 1.0000000 0.7036695 0.7007338 0.7048780
## y2 0.7036695 1.0000000 0.7216552 0.7049523
## y3 0.7007338 0.7216552 1.0000000 0.5310279
## y4 0.7048780 0.7049523 0.5310279 1.0000000
## 
## $g2
##           y1        y2        y3        y4
## y1 1.0000000 0.4309987 0.6618698 0.6839404
## y2 0.4309987 1.0000000 0.7179861 0.6043282
## y3 0.6618698 0.7179861 1.0000000 0.7842218
## y4 0.6839404 0.6043282 0.7842218 1.0000000
## 
## $g3
##           y1        y2        y3        y4
## y1 1.0000000 0.6255719 0.7487112 0.6494289
## y2 0.6255719 1.0000000 0.8234187 0.7218656
## y3 0.7487112 0.8234187 1.0000000 0.8299013
## y4 0.6494289 0.7218656 0.8299013 1.0000000
## 
## $g4
##           y1        y2        y3        y4
## y1 1.0000000 0.6822066 0.7670467 0.6369017
## y2 0.6822066 1.0000000 0.7495865 0.7120413
## y3 0.7670467 0.7495865 1.0000000 0.6370760
## y4 0.6369017 0.7120413 0.6370760 1.0000000

L’ultima soluzione è quella che ritengo migliore in termini di chiarezza ed efficienza. Proviamo ora a ragionare sul dataframe wide. Qui non abbiamo la possibilità di scomporre il dataframe nei gruppi in base alle righe (per questo è sempre meglio usare la versione long) ma tutto si basa sulla selezione di colonne che per molti versi è meno intuitiva ed automatica di quella di righe.

L’idea è quella di identificare le colonne in base ai nomi (è quindi sempre fondamentale dare nomi consistenti e significativi). Le colonne del gruppo “g1” finiscono sempre per _g1 e così per tutti i gruppi. Possiamo usare la funzione endsWith che prende una stringa ed un pattern e fornisce TRUE quando la stringa finisce con il pattern che abbiamo selezionato.

endsWith(colnames(cordat_wide), "g1")
##  [1] FALSE  TRUE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE
## [14]  TRUE FALSE FALSE FALSE
cor(cordat_wide[, endsWith(colnames(cordat_wide), "g1")])
##           y1_g1     y2_g1     y3_g1     y4_g1
## y1_g1 1.0000000 0.7036695 0.7007338 0.7048780
## y2_g1 0.7036695 1.0000000 0.7216552 0.7049523
## y3_g1 0.7007338 0.7216552 1.0000000 0.5310279
## y4_g1 0.7048780 0.7049523 0.5310279 1.0000000
cor(cordat_wide[, endsWith(colnames(cordat_wide), "g2")])
##           y1_g2     y2_g2     y3_g2     y4_g2
## y1_g2 1.0000000 0.4309987 0.6618698 0.6839404
## y2_g2 0.4309987 1.0000000 0.7179861 0.6043282
## y3_g2 0.6618698 0.7179861 1.0000000 0.7842218
## y4_g2 0.6839404 0.6043282 0.7842218 1.0000000
cor(cordat_wide[, endsWith(colnames(cordat_wide), "g3")])
##           y1_g3     y2_g3     y3_g3     y4_g3
## y1_g3 1.0000000 0.6255719 0.7487112 0.6494289
## y2_g3 0.6255719 1.0000000 0.8234187 0.7218656
## y3_g3 0.7487112 0.8234187 1.0000000 0.8299013
## y4_g3 0.6494289 0.7218656 0.8299013 1.0000000
cor(cordat_wide[, endsWith(colnames(cordat_wide), "g4")])
##           y1_g4     y2_g4     y3_g4     y4_g4
## y1_g4 1.0000000 0.6822066 0.7670467 0.6369017
## y2_g4 0.6822066 1.0000000 0.7495865 0.7120413
## y3_g4 0.7670467 0.7495865 1.0000000 0.6370760
## y4_g4 0.6369017 0.7120413 0.6370760 1.0000000
cormats <- lapply(c("g1", "g2", "g3", "g4"), function(x) cor(cordat_wide[endsWith(colnames(cordat_wide), x)]))

Seppur efficace trovo molto meno intuitivo ragionare in termini di colonne che di righe. Ma comunque entrambe le soluzioni portano allo stesso risultato.

3 Complex filtering

Spesso negli esperimenti dobbiamo escludere dei trial in base a condizioni semplici (giusto o sbagliato) o condizioni più complesse che dipendono anche da informazioni di altri trial o condizioni. Ad esempio, una modalità comune in esperimenti da laboratorio che indagano prestazioni di Working Memory è quella di analizzare non solo i trial corretti ma anche quelli corretti preceduti da un trial corretto. In altri termini eliminare i trial sbagliati o corretti ma preceduti da trial sbagliati. Un esperimento comune con 30 soggetti può arrivare anche ad avere 1000 trial per soggetto rendendo l’opzione manuale non solo sconsigliata ma improponibile.

Proviamo a simulare uno scenario. Questo è un dataset ipotetico con diverse condizioni e 30 soggetti ed una variabil y che indica l’accuratezza.

block <- 1:6
cond <- c("a", "b", "c", "d")
ntrial <- 20
nsubj <- 30

dat <- expand.grid(id = 1:nsubj,
                   block = block,
                   cond = cond, 
                   ntrial = 1:ntrial)

dat$y <- rbinom(nrow(dat), 1, prob = 0.5)

head(dat)
##   id block cond ntrial y
## 1  1     1    a      1 0
## 2  2     1    a      1 0
## 3  3     1    a      1 1
## 4  4     1    a      1 0
## 5  5     1    a      1 0
## 6  6     1    a      1 1

Quindi l’obiettivo è quello di eliminare tutti i trial sbagliati e quelli giusti ma preceduti da uno sbagliato. Per risolvere questo problema ci serve:

  1. un modo per selezionare i trial giusti/sbagliati (e.g., indicizzazione logica)
  2. un modo per “guardare” il trial precedente
  3. applicare lo stesso metodo per ogni soggetto condizione in modo separato

Per il punto 1 dobbiamo semplicemente selezionare quali trial sono corretti e quali sono sbagliati. Fortunatamente essendo una variabile binaria abbiamo solo una possibilità e ci basta quindi un solo test logico

table(dat$y) # 1 = corretto, 0 = sbagliato
## 
##    0    1 
## 7267 7133
table(dat$y == 1)
## 
## FALSE  TRUE 
##  7267  7133
head(subset(dat, subset = y == 1)) # metodo 1
##    id block cond ntrial y
## 3   3     1    a      1 1
## 6   6     1    a      1 1
## 8   8     1    a      1 1
## 10 10     1    a      1 1
## 12 12     1    a      1 1
## 15 15     1    a      1 1
head(dat[dat$y == 1, ]) # metodo 2
##    id block cond ntrial y
## 3   3     1    a      1 1
## 6   6     1    a      1 1
## 8   8     1    a      1 1
## 10 10     1    a      1 1
## 12 12     1    a      1 1
## 15 15     1    a      1 1

Ora il problema è che non stiamo considerando la seconda condizione, quella dove il trial precedente deve essere considerato per tenere al 100% un trial corretto. Per fare questo la cosa migliore è ragionare in ottica iterativa. Se lo facessimo a mano semplicemente scorriamo trial per trial, vediamo se è giusto e vediamo se il trial prima è sbagliato. Questo è esattamente lo scopo della programmazione iterativa ad esempio i cicli for:

keep <- vector(mode = "logical", length = nrow(dat)) # inizializzo un vettore vuoto. Non essenziale ma aumenta la velocità del codice per operazioni lunghe

for(i in 1:nrow(dat)){
    if(i == 1){
        keep[i] <- dat$y[i] == 1
    }else{
        keep[i] <- dat$y[i] == 1 & dat$y[i - 1] == 1
    }
}

Analizziamo il codice precedente. Questa riga inizializza un vettore che dovrà contenere il nostro risultato. L’idea è quella di scorrere riga per riga e poi segnare se un trial è da tenere oppure no in modo da utilizzare questo oggetto dopo per selezionare le righe corrette. Siccome sappiamo che a prescindere dal risultato il nostro vettore logico di selezione sarà lungo come il dataset possiamo inizializzarlo.

keep <- vector(mode = "logical", length = nrow(dat))

Poi partiamo con il ciclo for. Ora l’idea è di scomporre gli scenari possibili nel modo più chiaro e semplice. Abbiamo 2 possibilità:

  • il trial che stiamo considerando è il primo e quindi non ha un valore precedente. Questo è un problema perchè se usiamo l’iteratore i calcolando i - 1 il codice ci darà errore perchè non esiste la posizione 0.
  • il trial che stiamo considerando è diverso dal primo e quindi i - 1 non darà mai errore
if(i == 1){ # se il trial è il primo
    ...
}else{ # in tutti gli altri casi
    ...
}

Infine dobbiamo fare un check della condizione principale ovvero guardare se il trial è corretto y == 1 e nel caso dove i != 1 vedere anche il trial prima:

if(i == 1){
    keep[i] <- dat$y[i] == 1 # se y[i] == 1 diventa TRUE altrimenti FALSE
}else{
    keep[i] <- dat$y[i] == 1 & dat$y[i - 1] == 1 # se y[i] == 1 ed il trial precendente == 1 doventa TRUE, altrimenti FALSE
}

Ora dobbiamo semplicemente ripetere questo check logico per ogni elemento del dataframe impostando il ciclo for da 1 a quante righe ci sono nel dataframe.

for(i in 1:nrow(dat)){
    ...
}

Proviamo il nostro metodo:

keep <- vector(mode = "logical", length = nrow(dat)) # inizializzo un vettore vuoto. Non essenziale ma aumenta la velocità del codice per operazioni lunghe

for(i in 1:nrow(dat)){
    if(i == 1){
        keep[i] <- dat$y[i] == 1
    }else{
        keep[i] <- dat$y[i] == 1 & dat$y[i - 1] == 1
    }
}
dat$keep <- keep

Tutto perfetto ma c’è un problema. Il metodo deve essere applicato ad ogni soggetto/condizione separatamente altrimenti il trial di un blocco/condizione precedente può impattare quella di un blocco/condizione diversa. La cosa interessante è che la nostra soluzione è perfetta se applicata in una condizione specifica. Ci basterà replicare (iterare) il codice precedente per ogni soggetto/blocco/condizione.

  • mettiamo dentro una funzione il codice precedente
  • splittiamo (vedi ?split) il dataframe
  • applichiamo con for o in modo più compatto con *apply il codice precedente ad ogni elemento dello splitting

Facciamo la funzione:

keep_correct <- function(data){ # notate data vs dat per generalizzare
    keep <- vector(mode = "logical", length = nrow(data))
    
    for(i in 1:nrow(data)){
        if(i == 1){
            keep[i] <- data$y[i] == 1
        }else{
            keep[i] <- data$y[i] == 1 & data$y[i - 1] == 1
        }
    }
    data_correct <- data[keep, ] # filtro il dataset
    return(data_correct) # restituisco il dataset
}

Splittiamo il dataframe:

dat_split <- split(dat, list(dat$id, dat$block, dat$cond))
head(dat_split[[1]])
##      id block cond ntrial y
## 1     1     1    a      1 0
## 721   1     1    a      2 0
## 1441  1     1    a      3 1
## 2161  1     1    a      4 1
## 2881  1     1    a      5 1
## 3601  1     1    a      6 0
nrow(dat_split[[1]]) # numero di righe in un elemento = numero di trial per soggetto/condizione/blocco
## [1] 20
length(dat_split)
## [1] 720
length(block) * length(cond) * nsubj # numero di condizioni = numero di elementi nella lista
## [1] 720

Ora applichiamo la funzione di prima ad ognuno di questi elementi:

dat_split_sel <- lapply(dat_split, keep_correct)
dat_split_sel[[1]] # questo è il risultato
##       id block cond ntrial y
## 2161   1     1    a      4 1
## 2881   1     1    a      5 1
## 5041   1     1    a      8 1
## 10081  1     1    a     15 1
## 10801  1     1    a     16 1

Ora possiamo ricostruire il dataset attaccando insieme tutti i nuovi dataset filtrati. In qualche modo dobbiamo fare il contrario di split. Ci sono vari modi:

dat_sel <- dplyr::bind_rows(dat_split_sel) # usando dplyr::bind_rows()
dat_sel <- do.call(rbind, dat_split_sel) # usando base R con do.call e rbind

# usando un ciclo for (implicito negli altri metodi) ma brutto e poco efficiente. Utile per capire cosa accade

dat_sel <- dat_split_sel[[1]] # inizializziamo il primo

for(i in 2:length(dat_split_sel)){ # partiamo dal secondo perchè il primo è già fatto
    dat_sel <- rbind(dat_sel, dat_split_sel[[i]])
}

Il mio preferito è il primo. Semplice e veloce:

dat_sel <- dplyr::bind_rows(dat_split_sel) # usando dplyr::bind_rows()
head(dat_sel)
##   id block cond ntrial y
## 1  1     1    a      4 1
## 2  1     1    a      5 1
## 3  1     1    a      8 1
## 4  1     1    a     15 1
## 5  1     1    a     16 1
## 6  2     1    a      3 1
LS0tCnRpdGxlOiAiUiBmb3IgUHJvYmxlbSBTb2x2aW5nIgphdXRob3I6ICJGaWxpcHBvIEdhbWJhcm90YSIKb3V0cHV0OiAKICAgIGJvb2tkb3duOjpodG1sX2RvY3VtZW50MjoKICAgICAgICB0b2M6IHRydWUKICAgICAgICB0b2NfZmxvYXQ6IHRydWUKICAgICAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCmNzczogWyIuLi9maWxlcy9jc3MvY291cnNlX2h0bWwuY3NzIl0KLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLAogICAgICAgICAgICAgICAgICAgICAgd2FybmluZyA9IEZBTFNFLAogICAgICAgICAgICAgICAgICAgICAgbWVzc2FnZSA9IEZBTFNFKQpgYGAKCiMgUiBmb3IgUHJvYmxlbSBTb2x2aW5nCgpRdWFuZG8gc2kgY29taW5jaWEgYWQgZW50cmFyZSBuZWxsJ290dGljYSBkZWxsYSBwcm9ncmFtbWF6aW9uZSBlIGRhdGEgbWFuaXB1bGF0aW9uLCBzaSBwb3Nzb25vIHJpc29sdmVyZSBtb2x0aSBwcm9ibGVtaSBjb25jcmV0aSBpbiBtb2RvIGNyZWF0aXZvLCByaXByb2R1Y2liaWxlIGUgYW5jaGUgZWZmaWNpZW50ZS4gR2VuZXJhbG1lbnRlIGNpIHNvbm8gZHVlIG1vZGkgZGkgYWZmcm9udGFyZSBwcm9ibGVtaSBjb25jcmV0aSBuZWxsYSB2aXRhIGFjY2FkZW1pY2EgZGkgdHV0dGkgaSBnaW9ybmk6CgotICoqb25lLXNob3QqKgotICoqdGFrZSB5b3VyIHRpbWUqKgoKSWwgbW9kbyAqKm9uZS1zaG90Kiogw6ggcXVlbGxvIChhcHBhcmVudGVtZW50ZSkgcGnDuSByYXBpZG8sIGltbWVkaWF0byBlIChhcHBhcmVudGVtZW50ZSkgZWZmaWNpZW50ZS4gQWQgZXNlbXBpbzoKCj4gUXVlc3Rpb25hcmlvIHNvbW1pbmlzdHJhdG8gYSAxMDAgcGVyc29uZS4gU2NhcmljbyBpIGRhdGkgZGFsbGEgcGlhdHRhZm9ybWEgZGkgc29tbWluaXN0cmF6aW9uZSBlZCBlc2VndW8gZGVsbGUgb3BlcmF6aW9uaSBtYW51YWxtZW50ZSAocmljb2RpZmljYSBpdGVtLCBlbGltaW5hcmUgZGVsbGUgcmlnaGUvY29sb25uZSkuCgotICoqUHJvcyoqOiBjb25jbHVkbyBpbiBwb2NvIHRlbXBvIGlsIGxhdm9ybyAoZGlwZW5kZSBzZW1wcmUgZGFsIGxhdm9ybykKLSAqKkNvbnMqKjogU2UgaSBkYXRpIGluIGlucHV0IGNhbWJpYW5vIG8gYXVtZW50YW5vIGRldm8gcmljb21pbmNpYXJlCi0gKipQcm9iYWJpbGl0w6AgZGkgZXJyb3JpKio6IGFsdGEKCklsIG1ldG9kbyAqKnRha2UgeW91ciB0aW1lKiogcHJldmVkZSBkaSBpbnZlc3RpcmUgYW5jaGUgbW9sdG8gdGVtcG8gcGVyIGNhcGlyZSBpbCBwcm9ibGVtYSwgc3ZpbHVwcGFyZSB1bmEgc29sdXppb25lIHJpcHJvZHVjaWJpbGUgKGVkIGV2ZW50dWFsbWVudGUgYXBwbGljYWJpbGUgYW5jaGUgYWx0cmUgdm9sdGUpIGUgcG9pIGFwcGxpY2FybGEgaW5kaXBlbmRlbnRlbWVudGUgZGFsbCdpbnB1dC4KCi0gKipQcm9zKio6IGluIGNhc28gZGkgZXJyb3JpIG8gY2FtYmlhbWVudGkgbm9uIGRldm8gcmlmYXJlIG51bGxhCi0gKipDb25zKio6IGRldm8gc2FwZXJsbyBmYXJlIGUgaW52ZXN0aXJlIHBpw7kgdGVtcG8gaW5pemlhbG1lbnRlCi0gKipQcm9iYWJpbGl0w6AgZGkgZXJyb3JpKio6IGJhc3NhIChvIGNvbXVucXVlIGNvbnRyb2xsYWJpbGUpCgojIENvcnJlbGF6aW9uaSBpbiBzb3R0b2dydXBwaQoKVW4gYWx0cm8gcHJvYmxlbWEgY2hlIHNwZXNzbyBzaSBpbmNvbnRyYSDDqCBxdWVsbG8gZGkgYXBwbGljYXJlIG9wZXJhemlvbmksIG1hbmlwb2xhemlvbmkgbyBzdGF0aXN0aWNoZSBhIHNvbG8gdW4gc290dG8tZ3J1cHBvIGRpIGVsZW1lbnRpIGRpIHVuIGRhdGFzZXQuIEluIHF1ZXN0byBjYXNvIGwnaWRlYSDDqCBkaSBwYXJ0aXJlIGNvbiB1biBkYXRhZnJhbWUgYmVuIG9yZ2FuaXp6YXRvIHBlciBwb2kgc2VsZXppb25hcmUgc29sbyBsZSByaWdoZS9jb2xvbm5lIGNoZSBjaSBpbnRlcmVzc2Fuby4gRmFjY2lhbW8gdW4gZXNlbXBpbyBkaSB1biBpcG90ZXRpY28gZGF0YWZyYW1lIGNvbiA0IGdydXBwaSwgZSA0IHZhcmlhYmlsaSBkYSBjb3JyZWxhcmU6CgpgYGB7cn0KIyBzaW11bGlhbW8gaSBkYXRpCm5ncm91cHMgPC0gNApuc2FtcGxlIDwtIDIwCmNvcmRhdF9sb25nIDwtIGZhdXg6OnJub3JtX211bHRpKG5ncm91cHMgKiBuc2FtcGxlLCBtdSA9IGMoMCwgMCwgMCwgMCksIHNkID0gMSwgciA9IDAuNykKbmFtZXMoY29yZGF0X2xvbmcpIDwtIHBhc3RlMCgieSIsIDE6NCkKCiMgY3JlaWFtbyBpIGdydXBwaQpjb3JkYXRfbG9uZyRncm91cCA8LSByZXAoYygiZzEiLCAiZzIiLCAiZzMiLCAiZzQiKSwgZWFjaCA9IG5zYW1wbGUpICMgY29sb25uYSBjaGUgaWRlbnRpZmljYSBpbCBncnVwcG8KY29yZGF0X2xvbmckaWQgPC0gcmVwKDE6bnNhbXBsZSwgbmdyb3VwcykgIyBjb2xvbm5hIGNoZSBpZGVudGlmaWNhIGlsIHNvZ2dldHRvIGRlbnRybyBpbCBncnVwcG8KaGVhZChjb3JkYXRfbG9uZykgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIApgYGAKClF1ZWxsbyBjaGUgYWJiaWFtbyBjcmVhdG8gw6ggdW4gZGF0YWZyYW1lIGluIGZvcm1hIGx1bmdhIG8gKmxvbmcqIGUgY29uc2lzdGUgbmVsbCdhdmVyZSBsZSB2YXJpYWJpbGkgKipkaXBlbmRlbnRpKiogY29tZSBjb2xvbm5lIHNlcGFyYXRlIGUgcXVlbGxlICoqaW5kaXBlbmRlbnRpKiogb3JnYW5penphdGUgaW4gcmlnYS4gSW4gYWx0cmkgdGVybWluaSBhYmJpYW1vIG9nbmkgcmlnYSBjb21lIDEgb3NzZXJ2YXppb25lIGUgbGEgY29sb25uYSBncnVwcG8gY29tZSB1bmljYS4gTCdhbHRlcm5hdGl2YSDDqCB1c2FyZSBpbCBmb3JtYXRvICp3aWRlKiAoc2NvbnNpZ2xpYXRvIGluIHF1ZXN0byBjYXNvKToKCmBgYHtyfQpjb3JkYXRfd2lkZSA8LSB0aWR5cjo6cGl2b3Rfd2lkZXIoY29yZGF0X2xvbmcsIG5hbWVzX2Zyb20gPSBncm91cCwgdmFsdWVzX2Zyb20gPSBjKHkxLCB5MiwgeTMsIHk0KSkKaGVhZChjb3JkYXRfd2lkZSkKYGBgCgpTZXBwdXIgaWwgZm9ybWF0byAqd2lkZSogcG9zc2Egc2VtYnJhcmUgcGnDuSBpbnR1aXRpdm8sIGxhIG1hZ2dpb3IgcGFydGUgZGVpIHBhY2NoZXR0aSBwZXIgZmFyZSBhbmFsaXNpLCBncmFmaWNpIG8gYWx0cm8gbGF2b3JhIG1lZ2xpbyBzZSBpbCBkYXRhZnJhbWUgw6ggaW4gZm9ybWF0byAqbG9uZyouIEZvcnNlIGwndW5pY28gY2FzbyBkb3ZlIGlsIGZvcm1hdG8gKndpZGUqIMOoIGNvbnNpZ2xpYXRvIMOoIGxhdm9yYXJlIGNvbiBsZSBjb3JyZWxhemlvbmkgTUEgaW4gcXVlc3RvIGNhc28gdmlzdG8gY2hlIGNpIHNvbm8gNCBncnVwcGkgZSBkaXZlcnNlIHZhcmlhYmlsaSDDqCBjb211bnF1ZSBtZWdsaW8gcXVlbGxvICpsb25nKi4gTWEgdmVkaWFtbyBsYSBzb2x1emlvbmUgaW4gZW50cmFtYmkgaSBjYXNpLgoKSWwgcmlzdWx0YXRvIGNoZSB2b2dsaWFtbyBvdHRlbmVyZSDDqCBxdWVsbG8gZGkgY2FsY29sYXJlIHVuYSBtYXRyaWNlIGRpIGNvcnJlbGF6aW9uZSB0cmEgbGUgNCB2YXJpYWJpbGkgZGlwZW5kZW50aSBpbmRpcGVuZGVudGVtZW50ZSBwZXIgb2duaSBzb3R0b2dydXBwbyBkaSBwYXJ0ZWNpcGFudGkuIElsIG1vZG8gcGnDuSBzZW1wbGljZSDDqCBxdWVsbG8gZGkgZmFyZSB1biBgc3Vic2V0YCBkZWwgbm9zdHJvIGRhdGFmcmFtZSBlIGFwcGxpY2FyZSBsYSBmdW56aW9uZSBgY29yYCBvIHF1YWxzaWFzaSBhbHRyYSBvcGVyYXppb25lLgoKYGBge3J9CmNvcihjb3JkYXRfbG9uZ1tjb3JkYXRfbG9uZyRncm91cCA9PSAiZzEiLCBjKCJ5MSIsICJ5MiIsICJ5MyIsICJ5NCIpXSkKY29yKGNvcmRhdF9sb25nW2NvcmRhdF9sb25nJGdyb3VwID09ICJnMiIsIGMoInkxIiwgInkyIiwgInkzIiwgInk0IildKQpjb3IoY29yZGF0X2xvbmdbY29yZGF0X2xvbmckZ3JvdXAgPT0gImczIiwgYygieTEiLCAieTIiLCAieTMiLCAieTQiKV0pCmNvcihjb3JkYXRfbG9uZ1tjb3JkYXRfbG9uZyRncm91cCA9PSAiZzQiLCBjKCJ5MSIsICJ5MiIsICJ5MyIsICJ5NCIpXSkKYGBgCgpJbiBxdWVzdG8gY2FzbyBzdGlhbW8gcmlwZXRlbmRvIG1vbHRvIGNvZGljZSBtYSBpbCBwcmluY2lwaW8gw6ggbG8gc3Rlc3NvLiBBcHBsaWNhcmUgbGEgZnVuemlvbmUgYGNvcmAgYWQgb2duaSBzb3R0b2dydXBwby4gUG9zc2lhbW8gcGVyIGVzZW1waW8gcmVuZGVybG8gcGnDuSBlZmZpY2llbnRlIHVzYW5kbyB1bmEgcHJvY2VkdXJhIGl0ZXJhdGl2YSBjb21lIHVuIGBmb3JgIG9wcHVyZSB1bmEgZnVuemlvbmUgYCphcHBseWAuClZlZGlhbW8gbGEgc29sdXppb25lIGNvbiBgZm9yYDoKCmBgYHtyfQp2YXJfZm9yX2NvciA8LSBjKCJ5MSIsICJ5MiIsICJ5MyIsICJ5NCIpICMgcGVyIGNvbnZlbmllbnphIG1ldHRvIGxlIGNvbG9ubmUgZGEgY29uc2lkZXJhcmUgcXVpCmNvcm1hdHMgPC0gdmVjdG9yKG1vZGUgPSAibGlzdCIsIGxlbmd0aCA9IGxlbmd0aCh1bmlxdWUoY29yZGF0X2xvbmckZ3JvdXApKSkgIyBpbml6aWFsaXp6byB1bmEgbGlzdGEgdnVvdGEgcGVyIGVzc2VyZSBwacO5IGVmZmljaWVudGUKCiMgaXRlcm8gcGVyIGxhIGx1bmdoZXp6YSBkaSBjb3JtYXRzIGNoZSBlcXVpdmFsZSBhIHF1YW50aSBncnVwcGkgYWJiaWFtbyBlIGFwcGxpY28gbGEgZnVuemlvbmUgY29yIHNlbGV6aW9uYW5kbyB1biBncnVwcG8gYWxsYSB2b2x0YQpmb3IoaSBpbiAxOmxlbmd0aChjb3JtYXRzKSl7CiAgICBjb3JtYXRzW1tpXV0gPC0gY29yKGNvcmRhdF9sb25nW2NvcmRhdF9sb25nJGdyb3VwID09IHVuaXF1ZShjb3JkYXRfbG9uZyRncm91cClbaV0sIHZhcl9mb3JfY29yXSkKfQpgYGAKClZlZGlhbW8gbGEgc29sdXppb25lIGNvbiBgbGFwcGx5YCByYWdpb25hbmRvIGluIG1vZG8gc2ltaWxlIGFsIGBmb3JgOgoKYGBge3J9CiMgbm9uIHNlcnZlIGluaXppYWxpenphcmUgcGVyY2jDqCBsbyBmYSBnacOgIGludGVybmFtZW50ZS4gSXRlcm8gc3UgdW4gdmV0dG9yZSBjb24gaSB2YWxvcmkgZGVpIGdydXBwaSBlIHNlbGV6aW9ubwpjb3JtYXRzIDwtIGxhcHBseSh1bmlxdWUoY29yZGF0X2xvbmckZ3JvdXApLCBmdW5jdGlvbihncm91cCkgY29yKGNvcmRhdF9sb25nW2NvcmRhdF9sb25nJGdyb3VwID09IGdyb3VwLCB2YXJfZm9yX2Nvcl0pKQpjb3JtYXRzCmBgYAoKVmVkaWFtbyBsYSBzb2x1emlvbmUgY29uIGBsYXBwbHlgIG1hIGluIG1vZG8gYW5jb3JhIHBpw7kgY29tcGF0dG8gdXNhbmRvIGxhIGZ1bnppb25lIGA/c3BsaXRgIHBlciBzY29tcG9ycmUgaSBkYXRhZnJhbWUgZnVvcmkgZGFsbGEgZnVuemlvbmUgaXRlcmF0aXZhOgoKYGBge3J9CmNvcmRhdF9sb25nX3NwbGl0IDwtIHNwbGl0KGNvcmRhdF9sb25nLCBjb3JkYXRfbG9uZyRncm91cCkKY29ybWF0cyA8LSBsYXBwbHkoY29yZGF0X2xvbmdfc3BsaXQsIGZ1bmN0aW9uKHgpIGNvcih4WywgdmFyX2Zvcl9jb3JdKSkKY29ybWF0cwpgYGAKCkwndWx0aW1hIHNvbHV6aW9uZSDDqCBxdWVsbGEgY2hlIHJpdGVuZ28gbWlnbGlvcmUgaW4gdGVybWluaSBkaSBjaGlhcmV6emEgZWQgZWZmaWNpZW56YS4gUHJvdmlhbW8gb3JhIGEgcmFnaW9uYXJlIHN1bCBkYXRhZnJhbWUgYHdpZGVgLiBRdWkgbm9uIGFiYmlhbW8gbGEgcG9zc2liaWxpdMOgIGRpIHNjb21wb3JyZSBpbCBkYXRhZnJhbWUgbmVpIGdydXBwaSBpbiBiYXNlIGFsbGUgcmlnaGUgKHBlciBxdWVzdG8gw6ggc2VtcHJlIG1lZ2xpbyB1c2FyZSBsYSB2ZXJzaW9uZSBgbG9uZ2ApIG1hIHR1dHRvIHNpIGJhc2Egc3VsbGEgc2VsZXppb25lIGRpIGNvbG9ubmUgY2hlIHBlciBtb2x0aSB2ZXJzaSDDqCBtZW5vIGludHVpdGl2YSBlZCBhdXRvbWF0aWNhIGRpIHF1ZWxsYSBkaSByaWdoZS4KCkwnaWRlYSDDqCBxdWVsbGEgZGkgaWRlbnRpZmljYXJlIGxlIGNvbG9ubmUgaW4gYmFzZSBhaSBub21pICjDqCBxdWluZGkgc2VtcHJlIGZvbmRhbWVudGFsZSBkYXJlIG5vbWkgY29uc2lzdGVudGkgZSBzaWduaWZpY2F0aXZpKS4gTGUgY29sb25uZSBkZWwgZ3J1cHBvICJnMSIgZmluaXNjb25vIHNlbXByZSBwZXIgYF9nMWAgZSBjb3PDrCBwZXIgdHV0dGkgaSBncnVwcGkuIFBvc3NpYW1vIHVzYXJlIGxhIGZ1bnppb25lIGBlbmRzV2l0aGAgY2hlIHByZW5kZSB1bmEgc3RyaW5nYSBlZCB1biBwYXR0ZXJuIGUgZm9ybmlzY2UgYFRSVUVgIHF1YW5kbyBsYSBzdHJpbmdhIGZpbmlzY2UgY29uIGlsIHBhdHRlcm4gY2hlIGFiYmlhbW8gc2VsZXppb25hdG8uCgpgYGB7cn0KZW5kc1dpdGgoY29sbmFtZXMoY29yZGF0X3dpZGUpLCAiZzEiKQoKY29yKGNvcmRhdF93aWRlWywgZW5kc1dpdGgoY29sbmFtZXMoY29yZGF0X3dpZGUpLCAiZzEiKV0pCmNvcihjb3JkYXRfd2lkZVssIGVuZHNXaXRoKGNvbG5hbWVzKGNvcmRhdF93aWRlKSwgImcyIildKQpjb3IoY29yZGF0X3dpZGVbLCBlbmRzV2l0aChjb2xuYW1lcyhjb3JkYXRfd2lkZSksICJnMyIpXSkKY29yKGNvcmRhdF93aWRlWywgZW5kc1dpdGgoY29sbmFtZXMoY29yZGF0X3dpZGUpLCAiZzQiKV0pCgpjb3JtYXRzIDwtIGxhcHBseShjKCJnMSIsICJnMiIsICJnMyIsICJnNCIpLCBmdW5jdGlvbih4KSBjb3IoY29yZGF0X3dpZGVbZW5kc1dpdGgoY29sbmFtZXMoY29yZGF0X3dpZGUpLCB4KV0pKQpgYGAKClNlcHB1ciBlZmZpY2FjZSB0cm92byBtb2x0byBtZW5vIGludHVpdGl2byByYWdpb25hcmUgaW4gdGVybWluaSBkaSBjb2xvbm5lIGNoZSBkaSByaWdoZS4gTWEgY29tdW5xdWUgZW50cmFtYmUgbGUgc29sdXppb25pIHBvcnRhbm8gYWxsbyBzdGVzc28gcmlzdWx0YXRvLgoKIyBDb21wbGV4IGZpbHRlcmluZwoKU3Blc3NvIG5lZ2xpIGVzcGVyaW1lbnRpIGRvYmJpYW1vIGVzY2x1ZGVyZSBkZWkgdHJpYWwgaW4gYmFzZSBhIGNvbmRpemlvbmkgc2VtcGxpY2kgKGdpdXN0byBvIHNiYWdsaWF0bykgbyBjb25kaXppb25pIHBpw7kgY29tcGxlc3NlIGNoZSBkaXBlbmRvbm8gYW5jaGUgZGEgaW5mb3JtYXppb25pIGRpIGFsdHJpIHRyaWFsIG8gY29uZGl6aW9uaS4gQWQgZXNlbXBpbywgdW5hIG1vZGFsaXTDoCBjb211bmUgaW4gZXNwZXJpbWVudGkgZGEgbGFib3JhdG9yaW8gY2hlIGluZGFnYW5vIHByZXN0YXppb25pIGRpIFdvcmtpbmcgTWVtb3J5IMOoIHF1ZWxsYSBkaSBhbmFsaXp6YXJlIG5vbiBzb2xvIGkgdHJpYWwgY29ycmV0dGkgbWEgYW5jaGUgcXVlbGxpIGNvcnJldHRpIHByZWNlZHV0aSBkYSB1biB0cmlhbCBjb3JyZXR0by4gSW4gYWx0cmkgdGVybWluaSBlbGltaW5hcmUgaSB0cmlhbCBzYmFnbGlhdGkgbyBjb3JyZXR0aSBtYSBwcmVjZWR1dGkgZGEgdHJpYWwgc2JhZ2xpYXRpLiBVbiBlc3BlcmltZW50byBjb211bmUgY29uIDMwIHNvZ2dldHRpIHB1w7IgYXJyaXZhcmUgYW5jaGUgYWQgYXZlcmUgMTAwMCB0cmlhbCBwZXIgc29nZ2V0dG8gcmVuZGVuZG8gbCdvcHppb25lICptYW51YWxlKiBub24gc29sbyBzY29uc2lnbGlhdGEgbWEgaW1wcm9wb25pYmlsZS4KClByb3ZpYW1vIGEgc2ltdWxhcmUgdW5vIHNjZW5hcmlvLiBRdWVzdG8gw6ggdW4gZGF0YXNldCBpcG90ZXRpY28gY29uIGRpdmVyc2UgY29uZGl6aW9uaSBlIDMwIHNvZ2dldHRpIGVkIHVuYSB2YXJpYWJpbCBgeWAgY2hlIGluZGljYSBsJ2FjY3VyYXRlenphLgoKYGBge3J9CmJsb2NrIDwtIDE6Ngpjb25kIDwtIGMoImEiLCAiYiIsICJjIiwgImQiKQpudHJpYWwgPC0gMjAKbnN1YmogPC0gMzAKCmRhdCA8LSBleHBhbmQuZ3JpZChpZCA9IDE6bnN1YmosCiAgICAgICAgICAgICAgICAgICBibG9jayA9IGJsb2NrLAogICAgICAgICAgICAgICAgICAgY29uZCA9IGNvbmQsIAogICAgICAgICAgICAgICAgICAgbnRyaWFsID0gMTpudHJpYWwpCgpkYXQkeSA8LSByYmlub20obnJvdyhkYXQpLCAxLCBwcm9iID0gMC41KQoKaGVhZChkYXQpCmBgYAoKUXVpbmRpIGwnb2JpZXR0aXZvIMOoIHF1ZWxsbyBkaSBlbGltaW5hcmUgdHV0dGkgaSB0cmlhbCBzYmFnbGlhdGkgZSBxdWVsbGkgZ2l1c3RpIG1hIHByZWNlZHV0aSBkYSB1bm8gc2JhZ2xpYXRvLiBQZXIgcmlzb2x2ZXJlIHF1ZXN0byBwcm9ibGVtYSBjaSBzZXJ2ZToKCjEuIHVuIG1vZG8gcGVyIHNlbGV6aW9uYXJlIGkgdHJpYWwgZ2l1c3RpL3NiYWdsaWF0aSAoZS5nLiwgKippbmRpY2l6emF6aW9uZSBsb2dpY2EqKikKMi4gdW4gbW9kbyBwZXIgImd1YXJkYXJlIiBpbCB0cmlhbCBwcmVjZWRlbnRlCjMuIGFwcGxpY2FyZSBsbyBzdGVzc28gbWV0b2RvIHBlciBvZ25pIHNvZ2dldHRvIGNvbmRpemlvbmUgaW4gbW9kbyBzZXBhcmF0bwoKUGVyIGlsIHB1bnRvIDEgZG9iYmlhbW8gc2VtcGxpY2VtZW50ZSBzZWxlemlvbmFyZSBxdWFsaSB0cmlhbCBzb25vIGNvcnJldHRpIGUgcXVhbGkgc29ubyBzYmFnbGlhdGkuIEZvcnR1bmF0YW1lbnRlIGVzc2VuZG8gdW5hIHZhcmlhYmlsZSBiaW5hcmlhIGFiYmlhbW8gc29sbyB1bmEgcG9zc2liaWxpdMOgIGUgY2kgYmFzdGEgcXVpbmRpIHVuIHNvbG8gKip0ZXN0IGxvZ2ljbyoqCgpgYGB7cn0KdGFibGUoZGF0JHkpICMgMSA9IGNvcnJldHRvLCAwID0gc2JhZ2xpYXRvCnRhYmxlKGRhdCR5ID09IDEpCmhlYWQoc3Vic2V0KGRhdCwgc3Vic2V0ID0geSA9PSAxKSkgIyBtZXRvZG8gMQpoZWFkKGRhdFtkYXQkeSA9PSAxLCBdKSAjIG1ldG9kbyAyCmBgYAoKT3JhIGlsIHByb2JsZW1hIMOoIGNoZSBub24gc3RpYW1vIGNvbnNpZGVyYW5kbyBsYSBzZWNvbmRhIGNvbmRpemlvbmUsIHF1ZWxsYSBkb3ZlIGlsIHRyaWFsIHByZWNlZGVudGUgZGV2ZSBlc3NlcmUgY29uc2lkZXJhdG8gcGVyIHRlbmVyZSBhbCAxMDAlIHVuIHRyaWFsIGNvcnJldHRvLiBQZXIgZmFyZSBxdWVzdG8gbGEgY29zYSBtaWdsaW9yZSDDqCByYWdpb25hcmUgaW4gb3R0aWNhIGl0ZXJhdGl2YS4gU2UgbG8gZmFjZXNzaW1vIGEgbWFubyBzZW1wbGljZW1lbnRlIHNjb3JyaWFtbyB0cmlhbCBwZXIgdHJpYWwsIHZlZGlhbW8gc2Ugw6ggZ2l1c3RvIGUgdmVkaWFtbyBzZSBpbCB0cmlhbCBwcmltYSDDqCBzYmFnbGlhdG8uIFF1ZXN0byDDqCBlc2F0dGFtZW50ZSBsbyBzY29wbyBkZWxsYSBwcm9ncmFtbWF6aW9uZSAqKml0ZXJhdGl2YSoqIGFkIGVzZW1waW8gaSBjaWNsaSBgZm9yYDoKCmBgYHtyfQprZWVwIDwtIHZlY3Rvcihtb2RlID0gImxvZ2ljYWwiLCBsZW5ndGggPSBucm93KGRhdCkpICMgaW5pemlhbGl6em8gdW4gdmV0dG9yZSB2dW90by4gTm9uIGVzc2VuemlhbGUgbWEgYXVtZW50YSBsYSB2ZWxvY2l0w6AgZGVsIGNvZGljZSBwZXIgb3BlcmF6aW9uaSBsdW5naGUKCmZvcihpIGluIDE6bnJvdyhkYXQpKXsKICAgIGlmKGkgPT0gMSl7CiAgICAgICAga2VlcFtpXSA8LSBkYXQkeVtpXSA9PSAxCiAgICB9ZWxzZXsKICAgICAgICBrZWVwW2ldIDwtIGRhdCR5W2ldID09IDEgJiBkYXQkeVtpIC0gMV0gPT0gMQogICAgfQp9CmBgYAoKQW5hbGl6emlhbW8gaWwgY29kaWNlIHByZWNlZGVudGUuIFF1ZXN0YSByaWdhIGluaXppYWxpenphIHVuIHZldHRvcmUgY2hlIGRvdnLDoCBjb250ZW5lcmUgaWwgbm9zdHJvIHJpc3VsdGF0by4gTCdpZGVhIMOoIHF1ZWxsYSBkaSBzY29ycmVyZSByaWdhIHBlciByaWdhIGUgcG9pICpzZWduYXJlKiBzZSB1biB0cmlhbCDDqCBkYSB0ZW5lcmUgb3BwdXJlIG5vIGluIG1vZG8gZGEgdXRpbGl6emFyZSBxdWVzdG8gb2dnZXR0byBkb3BvIHBlciBzZWxlemlvbmFyZSBsZSByaWdoZSBjb3JyZXR0ZS4gU2ljY29tZSBzYXBwaWFtbyBjaGUgYSBwcmVzY2luZGVyZSBkYWwgcmlzdWx0YXRvIGlsIG5vc3RybyB2ZXR0b3JlIGxvZ2ljbyBkaSBzZWxlemlvbmUgc2Fyw6AgbHVuZ28gY29tZSBpbCBkYXRhc2V0IHBvc3NpYW1vIGluaXppYWxpenphcmxvLgoKYGBge3J9CmtlZXAgPC0gdmVjdG9yKG1vZGUgPSAibG9naWNhbCIsIGxlbmd0aCA9IG5yb3coZGF0KSkKYGBgCgpQb2kgcGFydGlhbW8gY29uIGlsIGNpY2xvIGBmb3JgLiBPcmEgbCdpZGVhIMOoIGRpIHNjb21wb3JyZSBnbGkgc2NlbmFyaSBwb3NzaWJpbGkgbmVsIG1vZG8gcGnDuSBjaGlhcm8gZSBzZW1wbGljZS4gQWJiaWFtbyAyIHBvc3NpYmlsaXTDoDoKCi0gaWwgdHJpYWwgY2hlIHN0aWFtbyBjb25zaWRlcmFuZG8gw6ggaWwgcHJpbW8gZSBxdWluZGkgbm9uIGhhIHVuIHZhbG9yZSBwcmVjZWRlbnRlLiBRdWVzdG8gw6ggdW4gcHJvYmxlbWEgcGVyY2jDqCBzZSB1c2lhbW8gbCdpdGVyYXRvcmUgYGlgIGNhbGNvbGFuZG8gYGkgLSAxYCBpbCBjb2RpY2UgY2kgZGFyw6AgZXJyb3JlIHBlcmNow6ggbm9uIGVzaXN0ZSBsYSBwb3NpemlvbmUgMC4KLSBpbCB0cmlhbCBjaGUgc3RpYW1vIGNvbnNpZGVyYW5kbyDDqCBkaXZlcnNvIGRhbCBwcmltbyBlIHF1aW5kaSBgaSAtIDFgIG5vbiBkYXLDoCBtYWkgZXJyb3JlCgpgYGB7ciwgZXZhbCA9IEZBTFNFfQppZihpID09IDEpeyAjIHNlIGlsIHRyaWFsIMOoIGlsIHByaW1vCiAgICAuLi4KfWVsc2V7ICMgaW4gdHV0dGkgZ2xpIGFsdHJpIGNhc2kKICAgIC4uLgp9CmBgYAoKSW5maW5lIGRvYmJpYW1vIGZhcmUgdW4gY2hlY2sgZGVsbGEgY29uZGl6aW9uZSBwcmluY2lwYWxlIG92dmVybyBndWFyZGFyZSBzZSBpbCB0cmlhbCDDqCBjb3JyZXR0byBgeSA9PSAxYCBlIG5lbCBjYXNvIGRvdmUgYGkgIT0gMWAgdmVkZXJlIGFuY2hlIGlsIHRyaWFsIHByaW1hOgoKYGBge3J9CmlmKGkgPT0gMSl7CiAgICBrZWVwW2ldIDwtIGRhdCR5W2ldID09IDEgIyBzZSB5W2ldID09IDEgZGl2ZW50YSBUUlVFIGFsdHJpbWVudGkgRkFMU0UKfWVsc2V7CiAgICBrZWVwW2ldIDwtIGRhdCR5W2ldID09IDEgJiBkYXQkeVtpIC0gMV0gPT0gMSAjIHNlIHlbaV0gPT0gMSBlZCBpbCB0cmlhbCBwcmVjZW5kZW50ZSA9PSAxIGRvdmVudGEgVFJVRSwgYWx0cmltZW50aSBGQUxTRQp9CmBgYAoKT3JhIGRvYmJpYW1vIHNlbXBsaWNlbWVudGUgcmlwZXRlcmUgcXVlc3RvIGNoZWNrIGxvZ2ljbyBwZXIgb2duaSBlbGVtZW50byBkZWwgZGF0YWZyYW1lIGltcG9zdGFuZG8gaWwgY2ljbG8gZm9yIGRhIDEgYSBxdWFudGUgcmlnaGUgY2kgc29ubyBuZWwgZGF0YWZyYW1lLgoKYGBge3IsIGV2YWwgPSBGQUxTRX0KZm9yKGkgaW4gMTpucm93KGRhdCkpewogICAgLi4uCn0KYGBgCgpQcm92aWFtbyBpbCBub3N0cm8gbWV0b2RvOgoKYGBge3IsIGV2YWwgPSBGQUxTRX0Ka2VlcCA8LSB2ZWN0b3IobW9kZSA9ICJsb2dpY2FsIiwgbGVuZ3RoID0gbnJvdyhkYXQpKSAjIGluaXppYWxpenpvIHVuIHZldHRvcmUgdnVvdG8uIE5vbiBlc3NlbnppYWxlIG1hIGF1bWVudGEgbGEgdmVsb2NpdMOgIGRlbCBjb2RpY2UgcGVyIG9wZXJhemlvbmkgbHVuZ2hlCgpmb3IoaSBpbiAxOm5yb3coZGF0KSl7CiAgICBpZihpID09IDEpewogICAgICAgIGtlZXBbaV0gPC0gZGF0JHlbaV0gPT0gMQogICAgfWVsc2V7CiAgICAgICAga2VlcFtpXSA8LSBkYXQkeVtpXSA9PSAxICYgZGF0JHlbaSAtIDFdID09IDEKICAgIH0KfQpkYXQka2VlcCA8LSBrZWVwCmBgYAoKVHV0dG8gcGVyZmV0dG8gbWEgYyfDqCB1biBwcm9ibGVtYS4gSWwgbWV0b2RvIGRldmUgZXNzZXJlIGFwcGxpY2F0byBhZCBvZ25pIHNvZ2dldHRvL2NvbmRpemlvbmUgc2VwYXJhdGFtZW50ZSBhbHRyaW1lbnRpIGlsIHRyaWFsIGRpIHVuIGJsb2Njby9jb25kaXppb25lIHByZWNlZGVudGUgcHXDsiBpbXBhdHRhcmUgcXVlbGxhIGRpIHVuIGJsb2Njby9jb25kaXppb25lIGRpdmVyc2EuIExhIGNvc2EgaW50ZXJlc3NhbnRlIMOoIGNoZSBsYSBub3N0cmEgc29sdXppb25lIMOoIHBlcmZldHRhIHNlIGFwcGxpY2F0YSBpbiB1bmEgY29uZGl6aW9uZSBzcGVjaWZpY2EuIENpIGJhc3RlcsOgIHJlcGxpY2FyZSAoKml0ZXJhcmUqKSBpbCBjb2RpY2UgcHJlY2VkZW50ZSBwZXIgb2duaSBzb2dnZXR0by9ibG9jY28vY29uZGl6aW9uZS4KCi0gbWV0dGlhbW8gZGVudHJvIHVuYSBmdW56aW9uZSBpbCBjb2RpY2UgcHJlY2VkZW50ZQotIHNwbGl0dGlhbW8gKHZlZGkgYD9zcGxpdGApIGlsIGRhdGFmcmFtZQotIGFwcGxpY2hpYW1vIGNvbiBgZm9yYCBvIGluIG1vZG8gcGnDuSBjb21wYXR0byBjb24gYCphcHBseWAgaWwgY29kaWNlIHByZWNlZGVudGUgYWQgb2duaSBlbGVtZW50byBkZWxsbyBzcGxpdHRpbmcKCkZhY2NpYW1vIGxhIGZ1bnppb25lOgoKYGBge3J9CmtlZXBfY29ycmVjdCA8LSBmdW5jdGlvbihkYXRhKXsgIyBub3RhdGUgZGF0YSB2cyBkYXQgcGVyIGdlbmVyYWxpenphcmUKICAgIGtlZXAgPC0gdmVjdG9yKG1vZGUgPSAibG9naWNhbCIsIGxlbmd0aCA9IG5yb3coZGF0YSkpCiAgICAKICAgIGZvcihpIGluIDE6bnJvdyhkYXRhKSl7CiAgICAgICAgaWYoaSA9PSAxKXsKICAgICAgICAgICAga2VlcFtpXSA8LSBkYXRhJHlbaV0gPT0gMQogICAgICAgIH1lbHNlewogICAgICAgICAgICBrZWVwW2ldIDwtIGRhdGEkeVtpXSA9PSAxICYgZGF0YSR5W2kgLSAxXSA9PSAxCiAgICAgICAgfQogICAgfQogICAgZGF0YV9jb3JyZWN0IDwtIGRhdGFba2VlcCwgXSAjIGZpbHRybyBpbCBkYXRhc2V0CiAgICByZXR1cm4oZGF0YV9jb3JyZWN0KSAjIHJlc3RpdHVpc2NvIGlsIGRhdGFzZXQKfQpgYGAKClNwbGl0dGlhbW8gaWwgZGF0YWZyYW1lOgoKYGBge3J9CmRhdF9zcGxpdCA8LSBzcGxpdChkYXQsIGxpc3QoZGF0JGlkLCBkYXQkYmxvY2ssIGRhdCRjb25kKSkKaGVhZChkYXRfc3BsaXRbWzFdXSkKbnJvdyhkYXRfc3BsaXRbWzFdXSkgIyBudW1lcm8gZGkgcmlnaGUgaW4gdW4gZWxlbWVudG8gPSBudW1lcm8gZGkgdHJpYWwgcGVyIHNvZ2dldHRvL2NvbmRpemlvbmUvYmxvY2NvCmxlbmd0aChkYXRfc3BsaXQpCmxlbmd0aChibG9jaykgKiBsZW5ndGgoY29uZCkgKiBuc3ViaiAjIG51bWVybyBkaSBjb25kaXppb25pID0gbnVtZXJvIGRpIGVsZW1lbnRpIG5lbGxhIGxpc3RhCmBgYAoKT3JhIGFwcGxpY2hpYW1vIGxhIGZ1bnppb25lIGRpIHByaW1hIGFkIG9nbnVubyBkaSBxdWVzdGkgZWxlbWVudGk6CgpgYGB7cn0KZGF0X3NwbGl0X3NlbCA8LSBsYXBwbHkoZGF0X3NwbGl0LCBrZWVwX2NvcnJlY3QpCmRhdF9zcGxpdF9zZWxbWzFdXSAjIHF1ZXN0byDDqCBpbCByaXN1bHRhdG8KYGBgCgpPcmEgcG9zc2lhbW8gcmljb3N0cnVpcmUgaWwgZGF0YXNldCAqYXR0YWNjYW5kbyogaW5zaWVtZSB0dXR0aSBpIG51b3ZpIGRhdGFzZXQgZmlsdHJhdGkuIEluIHF1YWxjaGUgbW9kbyBkb2JiaWFtbyBmYXJlIGlsIGNvbnRyYXJpbyBkaSBgc3BsaXRgLiBDaSBzb25vIHZhcmkgbW9kaToKCmBgYHtyLCBldmFsID0gRkFMU0V9CmRhdF9zZWwgPC0gZHBseXI6OmJpbmRfcm93cyhkYXRfc3BsaXRfc2VsKSAjIHVzYW5kbyBkcGx5cjo6YmluZF9yb3dzKCkKZGF0X3NlbCA8LSBkby5jYWxsKHJiaW5kLCBkYXRfc3BsaXRfc2VsKSAjIHVzYW5kbyBiYXNlIFIgY29uIGRvLmNhbGwgZSByYmluZAoKIyB1c2FuZG8gdW4gY2ljbG8gZm9yIChpbXBsaWNpdG8gbmVnbGkgYWx0cmkgbWV0b2RpKSBtYSBicnV0dG8gZSBwb2NvIGVmZmljaWVudGUuIFV0aWxlIHBlciBjYXBpcmUgY29zYSBhY2NhZGUKCmRhdF9zZWwgPC0gZGF0X3NwbGl0X3NlbFtbMV1dICMgaW5pemlhbGl6emlhbW8gaWwgcHJpbW8KCmZvcihpIGluIDI6bGVuZ3RoKGRhdF9zcGxpdF9zZWwpKXsgIyBwYXJ0aWFtbyBkYWwgc2Vjb25kbyBwZXJjaMOoIGlsIHByaW1vIMOoIGdpw6AgZmF0dG8KICAgIGRhdF9zZWwgPC0gcmJpbmQoZGF0X3NlbCwgZGF0X3NwbGl0X3NlbFtbaV1dKQp9CmBgYAoKSWwgbWlvIHByZWZlcml0byDDqCBpbCBwcmltby4gU2VtcGxpY2UgZSB2ZWxvY2U6CgpgYGB7cn0KZGF0X3NlbCA8LSBkcGx5cjo6YmluZF9yb3dzKGRhdF9zcGxpdF9zZWwpICMgdXNhbmRvIGRwbHlyOjpiaW5kX3Jvd3MoKQpoZWFkKGRhdF9zZWwpCmBgYAoKCgoK