Classificazione basata su Bayes

In questo notebook R consideriamo i metodi di classificazione basati sulla formula di Bayes: Naive Bayes, LDA (Linear Discriminant Analysis), QDA (Quadratic Discriminant Analysis), regressione logistica, regressione softmax. Utilizzeremo come in altre occasioni dataset generati ma anche dataset reali.

Iniziamo con caricare delle librerie necessarie. Installate i pacchetti se non sono già disponibili.

# Carica le librerie necessarie
library(ggplot2)
library(caret) 
library(e1071)  # Per Naive Bayes semplificato
library(naivebayes) # Naive Bayes avanzato
library(MASS)   # Per LDA e QDA

Datasets

Consideriamo 3 datasets: uno generato, uno dal pacchetto caret relativo a dati di individui per accesso al credito in Germania, e infine i dati sugli infortuni sul lavoro in Toscana.

Dataset generato

Generiamo una tabella con \(4\) features: 2 di tipo discreto, 2 di tipo numerico e una etichetta binaria, e alleniamo un modello di Naive Bayes su di esso.


# features (si può usare anche rbinom)
x1 <- sample( c(TRUE, FALSE), size=200, replace=TRUE, prob=c(0.2, 0.8))
x2 <- sample(  c(TRUE, FALSE), size=50, replace=TRUE, prob=c(0.5, 0.5))
y1 <- sample(  c(TRUE, FALSE), size=200, replace=TRUE, prob=c(0.3, 0.7))
y2 <- sample(  c(TRUE, FALSE), size=50, replace=TRUE, prob=c(0.2, 0.8))
z1 <- rnorm(200, mean=0, sd=1)
z2 <- rnorm(50, mean=2, sd=2)
w1 <- rpois(200, lambda=2)
w2 <- rpois(50, lambda=3)

# labels
data_generated <- data.frame("x" = c(x1, x2), "y"=c(y1, y2), "z"=c(z1, z2), "w"=c(w1, w2), "label"=as.factor(c(rep(-1, 200), rep(1,50))))

head(data_generated)

Partizioniamo il dataset in train e test usando il comando createDataPartition() dal pacchetto caret. Questo campiona in modo casuale come sample() ma cerca di rispettare la anche distribuzione delle diverse classi.

train_index <- createDataPartition(data_generated$label, p = 0.8, list = FALSE)
train_data_generated <- data_generated[train_index, ]
test_data_generated <- data_generated[-train_index, ]

print(paste("Taglia del train set:",nrow(train_data_generated) ))
[1] "Taglia del train set: 200"
print(paste("Taglia del test set:", nrow(test_data_generated) ))
[1] "Taglia del test set: 50"

Dataset German Credit Data

Nel pacchetto caret vi sono diversi dataset precaricati. Usiamo il dataset GermanCredit per addestrare e testare i modelli di classificazione basati su Bayes.

data("GermanCredit")

# Visualizza le prime righe del dataset

head(GermanCredit)
NA

Suddividiamo il dataset in training e test.

set.seed(42)

train_index_gc <- createDataPartition(GermanCredit$Class, p = 0.7, list = FALSE)
train_set_gc <- GermanCredit[train_index_gc, ]
test_set_gc <- GermanCredit[-train_index_gc, ]

print(paste("Taglia del train set:",nrow(train_set_gc) ))
[1] "Taglia del train set: 700"
print(paste("Taglia del test set:", nrow(test_set_gc) ))
[1] "Taglia del test set: 300"

Dataset Infortuni sul Lavoro in Toscana

I dati sugli infortuni sul lavoro in Italia divisi per regione e con alta granularità sono disponibili online sul sito Inail Open Data. Abbiamo scaricato il dataset relativo ai dati mensili e lo abbiamo salvato in formato CSV nella cartella datasets. Carichiamo il dataset usando il pacchetto rio.


library(rio)

infortuni_toscana <- import("datasets/DatiConCadenzaMensileInfortuniToscana.csv")

head(infortuni_toscana)
NA

Notiamo che in tutto il dataset comprende 61818 righe.

Selezioniamo solo alcune colonne di features rilevanti.

infortuni_toscana_tidy <- infortuni_toscana[ c(5, 7, 8, 9, 10, 11,13, 15)]


head(infortuni_toscana_tidy)

Un obiettivo potrebbe essere di classificare il luogo di nascita (ITALIA/ESTERO) dell’infortunato/a in base alle altre caratteristiche. Trasformiamo quindi la colonna LuogoNascita in una feature binaria (NatItal) ed estraiamo anche in questo caso il dataset in training e test set.

set.seed(42)

infortuni_toscana_tidy$NatItal <- factor(infortuni_toscana_tidy$LuogoNascita == "ITAL")

# rimuoviamo la colonna LuogoNascita
infortuni_toscana_tidy$LuogoNascita <- NULL

# estraiamo train e test set usando la colonnna NatItal come label

train_index_it <- createDataPartition(infortuni_toscana_tidy$NatItal, p = 0.7, list = FALSE)

train_set_it <- infortuni_toscana_tidy[train_index_it, ]
test_set_it <- infortuni_toscana_tidy[-train_index_it, ]

print(paste("Taglia del train set:",nrow(train_set_it) ))
[1] "Taglia del train set: 43274"
print(paste("Taglia del test set:", nrow(test_set_it) ))
[1] "Taglia del test set: 18544"

Naive Bayes

Ricordiamo che il classificatore Naive Bayes si basa sulla formula di Bayes, assumendo l’indipendenza condizionale tra le features data la label. La previsione per una nuova osservazione \(x=(x_1, x_2, \ldots, x_d)\) viene effettuata calcolando la probabilità a posteriori per ciascuna label \(\ell\) e scegliendo la label con la probabilità massima.

Ci sono vari pacchetti che contengono funzioni per calcolare classificatori Naive Bayes in R: caret (consigliato anche se un po’ più lento), e1071 e naivebayes.

Dataset generato

Vediamoli in azione sul dataset generato. Il comando è nel pacchetto caret è train() specificando nelle opzioni il metodo method="naive_bayes". Bisogna anche specificare una formula come in altri modelli di regressione/classificazione in R (questo è il primo caso che vediamo).


# Allenamento del modello Naive Bayes con caret
nb_model_caret <- train(label ~ ., data = train_data_generated, method = "naive_bayes")

#print(nb_model_caret)

# valuta sul test set
nb_pred_caret <- predict(nb_model_caret, test_data_generated)

confusionMatrix(nb_pred_caret, test_data_generated$label)
Confusion Matrix and Statistics

          Reference
Prediction -1  1
        -1 38  3
        1   2  7
                                          
               Accuracy : 0.9             
                 95% CI : (0.7819, 0.9667)
    No Information Rate : 0.8             
    P-Value [Acc > NIR] : 0.04803         
                                          
                  Kappa : 0.6753          
                                          
 Mcnemar's Test P-Value : 1.00000         
                                          
            Sensitivity : 0.9500          
            Specificity : 0.7000          
         Pos Pred Value : 0.9268          
         Neg Pred Value : 0.7778          
             Prevalence : 0.8000          
         Detection Rate : 0.7600          
   Detection Prevalence : 0.8200          
      Balanced Accuracy : 0.8250          
                                          
       'Positive' Class : -1              
                                          

Confrontiamo con il pacchetto e1071.

# Allenamento del modello Naive Bayes con e1071

nb_model_e1071 <- naiveBayes(label ~ x+z+w, data = train_data_generated)

# la formula indica che vogliamo prevedere la colonna "label" in funzione di tutte le altre colonne (features). Se avessimo voluto usare solo alcune features ad esempio la colonna x, avremmo scritto ad esempio label ~ x

print(nb_model_e1071)

Naive Bayes Classifier for Discrete Predictors

Call:
naiveBayes.default(x = X, y = Y, laplace = laplace)

A-priori probabilities:
Y
 -1   1 
0.8 0.2 

Conditional probabilities:
    x
Y      FALSE    TRUE
  -1 0.76875 0.23125
  1  0.47500 0.52500

    z
Y          [,1]      [,2]
  -1 0.08540609 0.9381225
  1  2.66902610 1.7484799

    w
Y       [,1]     [,2]
  -1 1.89375 1.403486
  1  2.82500 1.583367

Facciamo ora le previsioni sul test set e calcoliamo la matrice di confusione e l’accuratezza. Il comando è predict() come per altri modelli in R. La sintassi richiede di specificare il modello allenato e il dataset su cui fare le previsioni.

# Previsione sul test set

nb_pred_e1071 <- predict(nb_model_e1071, test_data_generated)

# il vettore contiene le etichette classificate.
# verifichiamo l'accuratezza e altre metriche con la matrice di confusione

nb_conf_matrix_e1071 <- confusionMatrix(nb_pred_e1071, test_data_generated$label)

print(nb_conf_matrix_e1071)
Confusion Matrix and Statistics

          Reference
Prediction -1  1
        -1 38  3
        1   2  7
                                          
               Accuracy : 0.9             
                 95% CI : (0.7819, 0.9667)
    No Information Rate : 0.8             
    P-Value [Acc > NIR] : 0.04803         
                                          
                  Kappa : 0.6753          
                                          
 Mcnemar's Test P-Value : 1.00000         
                                          
            Sensitivity : 0.9500          
            Specificity : 0.7000          
         Pos Pred Value : 0.9268          
         Neg Pred Value : 0.7778          
             Prevalence : 0.8000          
         Detection Rate : 0.7600          
   Detection Prevalence : 0.8200          
      Balanced Accuracy : 0.8250          
                                          
       'Positive' Class : -1              
                                          

Possiamo anche plottare la curva ROC per valutare la performance del classificatore al variare della soglia di accetazione (o equivalentemente delle probabilità a priori). Usiamo il pacchetto pROC per calcolare e plottare la curva ROC.

library(pROC)

# Ci servono le probabilità predette per la classe positiva, non soltanto l'etichetta predetta. Per questo specifichiamo type="raw" e prendiamo la seconda colonna (corrispondente alla classe +1)

nb_pred_prob_e1071 <- predict(nb_model_e1071, test_data_generated, type = "raw")[, 2]

# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse

roc_nb_e1071 <- roc(test_data_generated$label, nb_pred_prob_e1071)

ggroc(roc_nb_e1071, legacy.axes = TRUE) +
  ggtitle("ROC Curve per Naive Bayes dataset generato") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate")


auc(roc_nb_e1071)
Area under the curve: 0.9475

Per confronto, applichiamo invece la funzione naive_bayes() dal pacchetto naivebayes.

# Allenamento del modello Naive Bayes con naivebayes

nb_model_nb <- naive_bayes(label ~ ., data = train_data_generated)

print(nb_model_nb)

========================= Naive Bayes ==========================

Call:
naive_bayes.formula(formula = label ~ ., data = train_data_generated)

---------------------------------------------------------------- 
 
Laplace smoothing: 0

---------------------------------------------------------------- 
 
A priori probabilities: 

 -1   1 
0.8 0.2 

---------------------------------------------------------------- 
 
Tables: 

---------------------------------------------------------------- 
:: x (Bernoulli) 
---------------------------------------------------------------- 
       
x            -1       1
  FALSE 0.76875 0.47500
  TRUE  0.23125 0.52500

---------------------------------------------------------------- 
:: y (Bernoulli) 
---------------------------------------------------------------- 
       
y            -1       1
  FALSE 0.63125 0.75000
  TRUE  0.36875 0.25000

---------------------------------------------------------------- 
:: z (Gaussian) 
---------------------------------------------------------------- 
      
z              -1          1
  mean 0.08540609 2.66902610
  sd   0.93812248 1.74847988

---------------------------------------------------------------- 
:: w (Gaussian) 
---------------------------------------------------------------- 
      
w            -1        1
  mean 1.893750 2.825000
  sd   1.403486 1.583367

----------------------------------------------------------------
nb_pred_nb <- predict(nb_model_nb, test_data_generated[1:2])

# Confrontiamo le due previsioni

table(nb_pred_nb, nb_pred_e1071)
          nb_pred_e1071
nb_pred_nb -1  1
        -1 41  9
        1   0  0

Applichiamo infine \(k\)-nn sullo stesso dataset per confronto. Usiamo sempre il pacchetto caret per coerenza.

# Allenamento del modello KNN


# usiamo il pacchetto caret e cross validation per scegliere il valore di k
knn_model_generated <- train(label ~ ., data = train_data_generated, method="knn", tuneLength=10)

print(knn_model_generated)
k-Nearest Neighbors 

200 samples
  4 predictor
  2 classes: '-1', '1' 

No pre-processing
Resampling: Bootstrapped (25 reps) 
Summary of sample sizes: 200, 200, 200, 200, 200, 200, ... 
Resampling results across tuning parameters:

  k   Accuracy   Kappa    
   5  0.8956391  0.6405813
   7  0.9066797  0.6720492
   9  0.9053593  0.6676041
  11  0.9059815  0.6669415
  13  0.9059195  0.6615438
  15  0.9088043  0.6686325
  17  0.9056190  0.6547086
  19  0.9024574  0.6414763
  21  0.9051536  0.6544913
  23  0.9045415  0.6489380

Accuracy was used to select the optimal model using the
 largest value.
The final value used for the model was k = 15.
plot(knn_model_generated)

# Previsione sul test set
knn_pred_generated <- predict(knn_model_generated, test_data_generated)

# Matrice di confusione e accuratezza
knn_conf_matrix_generated <- confusionMatrix(knn_pred_generated, test_data_generated$label)

print(knn_conf_matrix_generated)
Confusion Matrix and Statistics

          Reference
Prediction -1  1
        -1 39  5
        1   1  5
                                          
               Accuracy : 0.88            
                 95% CI : (0.7569, 0.9547)
    No Information Rate : 0.8             
    P-Value [Acc > NIR] : 0.1034          
                                          
                  Kappa : 0.5588          
                                          
 Mcnemar's Test P-Value : 0.2207          
                                          
            Sensitivity : 0.9750          
            Specificity : 0.5000          
         Pos Pred Value : 0.8864          
         Neg Pred Value : 0.8333          
             Prevalence : 0.8000          
         Detection Rate : 0.7800          
   Detection Prevalence : 0.8800          
      Balanced Accuracy : 0.7375          
                                          
       'Positive' Class : -1              
                                          

Dataset German Credit Data

Applichiamo ora Naive Bayes sul dataset German Credit Data. Visualizziamo prima la correlazione tra le features usando una heatmap.

library(ggcorrplot)

# Calcola la matrice di correlazione relativa al training set per gli individui con una buona/cattiva classificazione di credito

cor_matrix_gc <- cor(train_set_gc[train_set_gc$Class=="Good", sapply(train_set_gc, is.numeric)])
# Plot della heatmap
ggcorrplot(cor_matrix_gc, 
           method = "square", 
           type = "full", 
           lab = FALSE, 
           title = "Matrice di Correlazione - German Credit Data", tl.cex=0)

Applichiamo Naive Bayes per determinare se un individuo ha un buon o cattivo credito (colonna Class).


# Allenamento del modello Naive Bayes

nb_model_gc <- naiveBayes(Class ~ ., data = train_set_gc)

# Previsione sul test set

nb_pred_gc <- predict(nb_model_gc, test_set_gc)

# Matrice di confusione e accuratezza

nb_conf_matrix_gc <- confusionMatrix(nb_pred_gc, test_set_gc$Class)

print(nb_conf_matrix_gc)
Confusion Matrix and Statistics

          Reference
Prediction Bad Good
      Bad   70   95
      Good  20  115
                                        
               Accuracy : 0.6167        
                 95% CI : (0.559, 0.672)
    No Information Rate : 0.7           
    P-Value [Acc > NIR] : 0.9992        
                                        
                  Kappa : 0.2628        
                                        
 Mcnemar's Test P-Value : 5.181e-12     
                                        
            Sensitivity : 0.7778        
            Specificity : 0.5476        
         Pos Pred Value : 0.4242        
         Neg Pred Value : 0.8519        
             Prevalence : 0.3000        
         Detection Rate : 0.2333        
   Detection Prevalence : 0.5500        
      Balanced Accuracy : 0.6627        
                                        
       'Positive' Class : Bad           
                                        

Plottiamo anche in questo caso la curva ROC.

# attenzione: se usate caret il comando per ottenere le probabilità predette è leggermente diverso "prob" invece di "raw"

nb_pred_prob_gc <- predict(nb_model_gc, test_set_gc, type = "raw")[, 2]

# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse

roc_nb_e1071 <- roc(test_set_gc$Class, nb_pred_prob_gc, levels=c("Good", "Bad"))

ggroc(roc_nb_e1071, legacy.axes = TRUE) +
  ggtitle("ROC Curve per Naive Bayes dataset generato") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate")

NA
NA

Ci chiediamo: quali delle features sono più importanti per la classificazione? Usiamo la funzione varImp() dal pacchetto caret per calcolare l’importanza delle variabili ed eventualmente effettuare una selezione delle features per aumentare l’intepretabilità del modello.


# Calcola l'importanza delle variabili

var_imp_gc <- varImp(nb_model_gc)
Error in UseMethod("varImp") : 
  no applicable method for 'varImp' applied to an object of class "naiveBayes"

Esercizio: Provate a rifare l’analisi di Naive Bayes usando solo le prime 5 features più importanti (in base alla classifica calcolata sopra). Come cambiano le performance del modello?

Dataset Infortuni sul Lavoro in Toscana

Applichiamo Naive Bayes sul dataset degli infortuni sul lavoro in Toscana per prevedere se l’infortunato è nato in Italia o all’estero (colonna NatItal).


# Allenamento del modello Naive Bayes

#nb_model_it <- train(NatItal ~ ., data =train_set_it, method="naive_bayes")

nb_model_it <- naiveBayes(NatItal ~ ., data = train_set_it)
# Previsione sul test set

nb_pred_it <- predict(nb_model_it, test_set_it)

Consideriamo la performance con la solita matrice di confusione.


# Matrice di confusione e accuratezza

nb_conf_matrix_it <- confusionMatrix(as.factor(nb_pred_it), as.factor(test_set_it$NatItal))

print(nb_conf_matrix_it)
Confusion Matrix and Statistics

          Reference
Prediction FALSE  TRUE
     FALSE   462   549
     TRUE   3642 13891
                                        
               Accuracy : 0.774         
                 95% CI : (0.7679, 0.78)
    No Information Rate : 0.7787        
    P-Value [Acc > NIR] : 0.9389        
                                        
                  Kappa : 0.1021        
                                        
 Mcnemar's Test P-Value : <2e-16        
                                        
            Sensitivity : 0.11257       
            Specificity : 0.96198       
         Pos Pred Value : 0.45697       
         Neg Pred Value : 0.79228       
             Prevalence : 0.22131       
         Detection Rate : 0.02491       
   Detection Prevalence : 0.05452       
      Balanced Accuracy : 0.53728       
                                        
       'Positive' Class : FALSE         
                                        
nb_pred_prob_it <- predict(nb_model_it, test_set_it, type = "raw")[, 2]

# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse


roc_nb_it <- roc(test_set_it$NatItal, nb_pred_prob_it, levels=c("TRUE", "FALSE"))

ggroc(roc_nb_it, legacy.axes = TRUE) +
  ggtitle("ROC Curve per Naive Bayes dataset INAIL") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate")

LDA e QDA

Applichiamo lda al dataset generato. Il comando per allenare il modello è lda() dal pacchetto MASS. Oppure il comando train() dal pacchetto caret specificando method="lda".`


# Allenamento del modello LDA

lda_model_generated <- lda(label ~ ., data = train_data_generated)
# Previsione sul test set
lda_pred_generated <- predict(lda_model_generated, test_data_generated)
# Matrice di confusione e accuratezza
lda_conf_matrix_generated <- confusionMatrix(lda_pred_generated$class, test_data_generated$label)
print(lda_conf_matrix_generated)
Confusion Matrix and Statistics

          Reference
Prediction -1  1
        -1 38  4
        1   2  6
                                          
               Accuracy : 0.88            
                 95% CI : (0.7569, 0.9547)
    No Information Rate : 0.8             
    P-Value [Acc > NIR] : 0.1034          
                                          
                  Kappa : 0.5946          
                                          
 Mcnemar's Test P-Value : 0.6831          
                                          
            Sensitivity : 0.9500          
            Specificity : 0.6000          
         Pos Pred Value : 0.9048          
         Neg Pred Value : 0.7500          
             Prevalence : 0.8000          
         Detection Rate : 0.7600          
   Detection Prevalence : 0.8400          
      Balanced Accuracy : 0.7750          
                                          
       'Positive' Class : -1              
                                          

Applichiamo anche QDA per confronto. Il comando è qda().


# Allenamento del modello QDA
qda_model_generated <- qda(label ~ ., data = train_data_generated)
# Previsione sul test set
qda_pred_generated <- predict(qda_model_generated, test_data_generated)
# Matrice di confusione e accuratezza
qda_conf_matrix_generated <- confusionMatrix(qda_pred_generated$class, test_data_generated$label)
print(qda_conf_matrix_generated)
Confusion Matrix and Statistics

          Reference
Prediction -1  1
        -1 38  3
        1   2  7
                                          
               Accuracy : 0.9             
                 95% CI : (0.7819, 0.9667)
    No Information Rate : 0.8             
    P-Value [Acc > NIR] : 0.04803         
                                          
                  Kappa : 0.6753          
                                          
 Mcnemar's Test P-Value : 1.00000         
                                          
            Sensitivity : 0.9500          
            Specificity : 0.7000          
         Pos Pred Value : 0.9268          
         Neg Pred Value : 0.7778          
             Prevalence : 0.8000          
         Detection Rate : 0.7600          
   Detection Prevalence : 0.8200          
      Balanced Accuracy : 0.8250          
                                          
       'Positive' Class : -1              
                                          

Confrontiamo le curve ROC per i due modelli (LDA e QDA).


lda_pred_prob_generated <- predict(lda_model_generated, test_data_generated)$posterior[, 2]
qda_pred_prob_generated <- predict(qda_model_generated, test_data_generated)$posterior[, 2]
# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse
roc_lda_generated <- roc(test_data_generated$label, lda_pred_prob_generated)
roc_qda_generated <- roc(test_data_generated$label, qda_pred_prob_generated)
ggroc(roc_lda_generated, legacy.axes = TRUE, color="blue") +
  ggtitle("ROC Curve per LDA (blu) e QDA (verde) - Dataset Generato") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate") +
  geom_line(data = ggroc(roc_qda_generated)$data, aes(x = 1 - specificity, y = sensitivity), color="green") +
  theme(legend.position = "bottom") +
  guides(color = guide_legend(override.aes = list(size = 4)))

Dataset German Credit Data

Applichiamo ora LDA sul dataset German Credit Data.

# Allenamento del modello LDA

# se applicato interamente al dataset abbiamo un errore perchè alcune colonne all'interno dei gruppi sono costanti. Questo crea dei problemi nella stima della varianza. Rimuoviamole.

#train_set_gc[c(25, 26, 30, 33, 36,  39, 42, 44)] <- NULL

gc_tidy <- train_set_gc[1:10]

lda_model_gc <- train(Class ~ ., data = gc_tidy, method="lda")
# Previsione sul test set
lda_pred_gc <- predict(lda_model_gc, test_set_gc[1:10])

# Matrice di confusione e accuratezza
lda_conf_matrix_gc <- confusionMatrix(lda_pred_gc, test_set_gc$Class)
print(lda_conf_matrix_gc)

Plottiamo anche in questo caso la curva ROC (sovrapponendola a quella di Naive Bayes per confronto).

lda_pred_prob_gc <- predict(lda_model_gc, test_set_gc, type="prob")[, 2]

# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse

roc_lda_gc <- roc(test_set_gc$Class, lda_pred_prob_gc, levels=c("Good", "Bad"))

ggroc(roc_lda_gc, legacy.axes = TRUE, color="blue") +
  ggtitle("ROC Curve per Naive Bayes (rosso) e LDA (blu)- German Credit Data") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate") +
  geom_line(data = ggroc(roc_nb_e1071)$data, aes(x = 1 - specificity, y = sensitivity), color="red") +
  theme(legend.position = "bottom") +
  guides(color = guide_legend(override.aes = list(size = 4)))

Vediamo che LDA migliora leggermente le performance rispetto a Naive Bayes in questo caso.

Dataset Infortuni sul Lavoro in Toscana

Applichiamo ora LDA e QDA sul dataset degli infortuni sul lavoro in Toscana per prevedere se l’infortunato è nato in Italia o all’estero (colonna NatItal). Usiamo prima LDA.


# Allenamento del modello LDA
lda_model_it <- lda(NatItal ~ ., data = train_set_it)
# Previsione sul test set
lda_pred_it <- predict(lda_model_it, test_set_it)
# Matrice di confusione e accuratezza
lda_conf_matrix_it <- confusionMatrix(lda_pred_it$class, test_set_it$NatItal)
print(lda_conf_matrix_it)
Confusion Matrix and Statistics

          Reference
Prediction FALSE  TRUE
     FALSE   233   232
     TRUE   3871 14208
                                          
               Accuracy : 0.7787          
                 95% CI : (0.7727, 0.7847)
    No Information Rate : 0.7787          
    P-Value [Acc > NIR] : 0.4971          
                                          
                  Kappa : 0.0596          
                                          
 Mcnemar's Test P-Value : <2e-16          
                                          
            Sensitivity : 0.05677         
            Specificity : 0.98393         
         Pos Pred Value : 0.50108         
         Neg Pred Value : 0.78588         
             Prevalence : 0.22131         
         Detection Rate : 0.01256         
   Detection Prevalence : 0.02508         
      Balanced Accuracy : 0.52035         
                                          
       'Positive' Class : FALSE           
                                          

Confrontiamo le previsioni dei due modelli (LDA e Naive Bayes).


# tabella di contingenza

table(lda_pred_it$class, nb_pred_it)
       nb_pred_it
        FALSE  TRUE
  FALSE   410    55
  TRUE    601 17478

Confrontiamo le curve ROC.


lda_pred_prob_it <- predict(lda_model_it, test_set_it)$posterior[, 2]
# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse

roc_lda_it <- roc(test_set_it$NatItal, lda_pred_prob_it, levels=c("TRUE", "FALSE"))

ggroc(roc_lda_it, legacy.axes = TRUE, color="blue") +
  ggtitle("ROC Curve per Naive Bayes (rosso) e LDA (blu)- INAIL Toscana") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate") +
  geom_line(data = ggroc(roc_nb_it)$data, aes(x = 1 - specificity, y = sensitivity), color="red") +
  theme(legend.position = "bottom") +
  guides(color = guide_legend(override.aes = list(size = 4)))

NA
NA

Non stupisce che il modello LDA abbia performance peggiori: non sta utilizzando le colonne discrete in modo ottimale.

Esercizio: Provate a rifare l’analisi di LDA usando solo le colonne numeriche del dataset e trasformando eventuali factor in numerici (come il genere). Come cambiano le performance del modello?

Regressione Logistica

Consideriamo il dataset generato, che contiene 4 features (tutte numeriche) e due sole labels. Il comando per applicare la regressione logistica in R è glm() specificando family=binomial. Possiamo in alternativa usare il pacchetto caret con method="multinom" (per la regressione logistica multinomiale, che funziona anche per il caso binario).

# Allenamento del modello di regressione logistica
log_model_generated <- glm(label ~ ., data = train_data_generated, family = binomial)

#con la funzione summary() otteniamo un riassunto del modello
summary(log_model_generated)

Call:
glm(formula = label ~ ., family = binomial, data = train_data_generated)

Coefficients:
            Estimate Std. Error z value Pr(>|z|)    
(Intercept)  -4.2609     0.7060  -6.036 1.58e-09 ***
xTRUE         1.4844     0.5812   2.554   0.0106 *  
yTRUE        -1.1254     0.6383  -1.763   0.0779 .  
z             1.6121     0.2958   5.451 5.01e-08 ***
w             0.3825     0.1850   2.067   0.0387 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 200.161  on 199  degrees of freedom
Residual deviance:  91.126  on 195  degrees of freedom
AIC: 101.13

Number of Fisher Scoring iterations: 6


# Previsione sul test set
log_pred_generated_prob <- predict(log_model_generated, test_data_generated, type = "response")

# Convertiamo le probabilità in etichette
log_pred_generated <- ifelse(log_pred_generated_prob > 0.5, 1, -1)

# Matrice di confusione e accuracy

log_conf_matrix_generated <- confusionMatrix(as.factor(log_pred_generated), test_data_generated$label)
print(log_conf_matrix_generated)
Confusion Matrix and Statistics

          Reference
Prediction -1  1
        -1 38  4
        1   2  6
                                          
               Accuracy : 0.88            
                 95% CI : (0.7569, 0.9547)
    No Information Rate : 0.8             
    P-Value [Acc > NIR] : 0.1034          
                                          
                  Kappa : 0.5946          
                                          
 Mcnemar's Test P-Value : 0.6831          
                                          
            Sensitivity : 0.9500          
            Specificity : 0.6000          
         Pos Pred Value : 0.9048          
         Neg Pred Value : 0.7500          
             Prevalence : 0.8000          
         Detection Rate : 0.7600          
   Detection Prevalence : 0.8400          
      Balanced Accuracy : 0.7750          
                                          
       'Positive' Class : -1              
                                          

Plottiamo ora le curve ROC per i tre metodi (Naive Bayes, LDA, Regressione Logistica) per confronto.


log_pred_prob_generated <- predict(log_model_generated, test_data_generated, type = "response")

# Calcola la ROC curve ed esegui un plot usando ggroc (pacchetto pROC). Specifichiamo legacy.axes=TRUE per avere FPR nelle ascisse
roc_log_generated <- roc(test_data_generated$label, log_pred_prob_generated)
ggroc(roc_log_generated, legacy.axes = TRUE, color="green") +
  ggtitle("ROC: NB (rosso), LDA (blu) e RL (verde) - Dataset Generato") +
  xlab("False Positive Rate") +
  ylab("True Positive Rate") +
  geom_line(data = ggroc(roc_nb_e1071)$data, aes(x = 1 - specificity, y = sensitivity), color="red") +
  geom_line(data = ggroc(roc_lda_generated)$data, aes(x = 1 - specificity, y = sensitivity), color="blue") +
  theme(legend.position = "bottom") +
  guides(color = guide_legend(override.aes = list(size = 4)))

Consideriamo infine un modello di classificazione nel caso multi-classe. Per semplicità aggiungiamo una terza classe al dataset generato.


# Aggiungiamo una terza classe al dataset generato
x3 <- sample( 0:1, size=80, replace=TRUE, prob=c(0.2, 0.8))
y3 <- sample( 0:1, size=80, replace=TRUE, prob=c(0.5, 0.5))
z3 <- rnorm(80, mean=0, sd=2)
w3 <- rpois(80, lambda=5)

data_generated_multi <- data.frame("x" = c(x1, x2, x3), "y"=c(y1, y2, y3), "z"=c(z1, z2, z3), "w"=c(w1, w2, w3), "label"=as.factor(c(rep(-1, 200), rep(1,50), rep(0,80))))

# Suddivisione in train e test set
train_index_multi <- createDataPartition(data_generated_multi$label, p = 0.7, list = FALSE)
train_data_generated_multi <- data_generated_multi[train_index_multi, ]
test_data_generated_multi <- data_generated_multi[-train_index_multi, ]

ggplot(data_generated_multi, aes(x =z, y = w, color = label)) +
  geom_point() +
  labs(title = "Dataset Fittizio Multi-classe", x = "feature 3", y = "feature 4")

Applichiamo prima una strategia euristica one-vs-all per la regressione logistica multi-classe.

# Allenamento del modello di regressione logistica one-vs-all
log_models_multi <- list()

classes <- levels(train_data_generated_multi$label)
for (cls in classes) {
  binary_labels <- ifelse(train_data_generated_multi$label == cls, 1, 0)
  log_models_multi[[cls]] <- glm(binary_labels ~ ., data = train_data_generated_multi, family = binomial)
}
# Previsione sul test set
log_pred_multi <- sapply(classes, function(cls) {
  predict(log_models_multi[[cls]], test_data_generated_multi, type = "response")
})
log_pred_multi_labels <- apply(log_pred_multi, 1, function(probs) {
  classes[which.max(probs)]
})
# Matrice di confusione e accuracy
log_conf_matrix_multi <- confusionMatrix(as.factor(log_pred_multi_labels), test_data_generated_multi$label)
print(log_conf_matrix_multi)
Confusion Matrix and Statistics

          Reference
Prediction -1  0  1
        -1 60  0  0
        0   0 24  0
        1   0  0 15

Overall Statistics
                                     
               Accuracy : 1          
                 95% CI : (0.9634, 1)
    No Information Rate : 0.6061     
    P-Value [Acc > NIR] : < 2.2e-16  
                                     
                  Kappa : 1          
                                     
 Mcnemar's Test P-Value : NA         

Statistics by Class:

                     Class: -1 Class: 0 Class: 1
Sensitivity             1.0000   1.0000   1.0000
Specificity             1.0000   1.0000   1.0000
Pos Pred Value          1.0000   1.0000   1.0000
Neg Pred Value          1.0000   1.0000   1.0000
Prevalence              0.6061   0.2424   0.1515
Detection Rate          0.6061   0.2424   0.1515
Detection Prevalence    0.6061   0.2424   0.1515
Balanced Accuracy       1.0000   1.0000   1.0000

Applichiamo ora una regressione multinomiale usando il pacchetto caret.


# Allenamento del modello di regressione logistica multi classe
log_model_multi <- train(label ~ ., data = train_data_generated_multi, trControl = trainControl(verboseIter = FALSE),  trace = FALSE, method = "multinom")

# Previsione sul test set
log_pred_multi_caret <- predict(log_model_multi, test_data_generated_multi)
# Matrice di confusione e accuracy
log_conf_matrix_multi_caret <- confusionMatrix(log_pred_multi_caret, test_data_generated_multi$label)
print(log_conf_matrix_multi_caret)
Confusion Matrix and Statistics

          Reference
Prediction -1  0  1
        -1 58  5  4
        0   1 18  2
        1   1  1  9

Overall Statistics
                                          
               Accuracy : 0.8586          
                 95% CI : (0.7741, 0.9205)
    No Information Rate : 0.6061          
    P-Value [Acc > NIR] : 3.558e-08       
                                          
                  Kappa : 0.7289          
                                          
 Mcnemar's Test P-Value : 0.187           

Statistics by Class:

                     Class: -1 Class: 0 Class: 1
Sensitivity             0.9667   0.7500  0.60000
Specificity             0.7692   0.9600  0.97619
Pos Pred Value          0.8657   0.8571  0.81818
Neg Pred Value          0.9375   0.9231  0.93182
Prevalence              0.6061   0.2424  0.15152
Detection Rate          0.5859   0.1818  0.09091
Detection Prevalence    0.6768   0.2121  0.11111
Balanced Accuracy       0.8679   0.8550  0.78810

Esercizio: Applicare la regressione logistica al dataset German Credit Data e confrontare le performance con Naive Bayes e LDA viste in precedenza.

Esercizi

  1. Generare una tabella con 30 righe e 8 colonne con dati casuali. Aggiungere una quinta colonna contenente una classificazione binaria, generata anche essa casualmente. Calcolare la discrepanza tra la classificazione originaria e il risultato di una classificazione logistica. Se si ripete questo esperimento per 1000 volte, calcolare valore medio e deviazione standard della discrepanza.

  2. Generare una tabella A con 170 righe e 7 colonne, in modo che l’ultima colonna contenga valori binari relativi all’appartenenza a una o l’altra di due classi. Generare una seconda tabella B con 5 righe e 6 colonne. Implementare una classificazione degli individui nella tabella B applicando alla tabella A la classificazione logistica e la analisi discriminante lineare. Confrontare i risultati dei due metodi.

  3. Confrontare i metodi di regressione logistica e analisi discriminante lineare e quadratica sul dataset titanic usando l’autovalidazione, per stabilire il metodo migliore.

  4. Determinare il migliore metodo di classificazione (tra quelli studiati nel corso) per il dataset Pima.tr (pacchetto MASS). Usare poi i modelli per classificare i nuovi dati contenuti nel dataset Pima.te e verificare se il miglior modello stabilito nella prima parte sia effettivamente il più efficace.

Nota sui blocchi

Potete creare un blocco iniziale e non visualizzare il codice di tutti i blocchi in un R notebook usande il comando: knitr::opts_chunk$set(warning = FALSE, message = FALSE, echo=FALSE)

LS0tCnRpdGxlOiAiQ2xhc3NpZmljYXppb25lIElJIChub3RlYm9vayA1KSIKYXV0aG9yOiAiRGFyaW8gVHJldmlzYW4iCmRhdGU6ICIyMi8xMC8yMDI1IgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2RlcHRoOiAzCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIHRoZW1lOiByZWFkYWJsZQogICAgZGZfcHJpbnQ6IHBhZ2VkCiAgICBkb3dubG9hZF9oYW5kbGVyOiB0cnVlCiAgaHRtbF9kb2N1bWVudDoKICAgIHRvYzogdHJ1ZQogICAgdG9jX2RlcHRoOiAnMycKICAgIGRmX3ByaW50OiBwYWdlZApzdWJ0aXRsZTogIlN0YXRpc3RpY2EgSUkgLSA3NTBBQSIKLS0tCgoKCiMgQ2xhc3NpZmljYXppb25lIGJhc2F0YSBzdSBCYXllcwoKCkluIHF1ZXN0byBub3RlYm9vayBSIGNvbnNpZGVyaWFtbyBpIG1ldG9kaSBkaSBjbGFzc2lmaWNhemlvbmUgYmFzYXRpIHN1bGxhIGZvcm11bGEgZGkgQmF5ZXM6IE5haXZlIEJheWVzLCBMREEgKExpbmVhciBEaXNjcmltaW5hbnQgQW5hbHlzaXMpLCBRREEgKFF1YWRyYXRpYyBEaXNjcmltaW5hbnQgQW5hbHlzaXMpLCByZWdyZXNzaW9uZSBsb2dpc3RpY2EsIHJlZ3Jlc3Npb25lIHNvZnRtYXguIFV0aWxpenplcmVtbyBjb21lIGluIGFsdHJlIG9jY2FzaW9uaSBkYXRhc2V0IGdlbmVyYXRpIG1hIGFuY2hlIGRhdGFzZXQgcmVhbGkuCgoKSW5pemlhbW8gY29uIGNhcmljYXJlIGRlbGxlIGxpYnJlcmllIG5lY2Vzc2FyaWUuIEluc3RhbGxhdGUgaSBwYWNjaGV0dGkgc2Ugbm9uIHNvbm8gZ2nDoCBkaXNwb25pYmlsaS4KCmBgYHtyfQojIENhcmljYSBsZSBsaWJyZXJpZSBuZWNlc3NhcmllCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShjYXJldCkgCmxpYnJhcnkoZTEwNzEpICAjIFBlciBOYWl2ZSBCYXllcyBzZW1wbGlmaWNhdG8KbGlicmFyeShuYWl2ZWJheWVzKSAjIE5haXZlIEJheWVzIGF2YW56YXRvCmxpYnJhcnkoTUFTUykgICAjIFBlciBMREEgZSBRREEKYGBgCiMjIERhdGFzZXRzCgpDb25zaWRlcmlhbW8gMyBkYXRhc2V0czogdW5vIGdlbmVyYXRvLCB1bm8gZGFsIHBhY2NoZXR0byBgYGNhcmV0YGAgcmVsYXRpdm8gYSBkYXRpIGRpIGluZGl2aWR1aSBwZXIgYWNjZXNzbyBhbCBjcmVkaXRvIGluIEdlcm1hbmlhLCBlIGluZmluZSBpIGRhdGkgc3VnbGkgaW5mb3J0dW5pIHN1bCBsYXZvcm8gaW4gVG9zY2FuYS4gCgojIyMgRGF0YXNldCBnZW5lcmF0bwoKR2VuZXJpYW1vIHVuYSB0YWJlbGxhIGNvbiAkNCQgZmVhdHVyZXM6IDIgZGkgdGlwbyBkaXNjcmV0bywgMiBkaSB0aXBvIG51bWVyaWNvIGUgdW5hIGV0aWNoZXR0YSBiaW5hcmlhLCBlIGFsbGVuaWFtbyB1biBtb2RlbGxvIGRpIE5haXZlIEJheWVzIHN1IGRpIGVzc28uCgoKYGBge3J9CgojIGZlYXR1cmVzIChzaSBwdcOyIHVzYXJlIGFuY2hlIHJiaW5vbSkKeDEgPC0gc2FtcGxlKCBjKFRSVUUsIEZBTFNFKSwgc2l6ZT0yMDAsIHJlcGxhY2U9VFJVRSwgcHJvYj1jKDAuMiwgMC44KSkKeDIgPC0gc2FtcGxlKCAgYyhUUlVFLCBGQUxTRSksIHNpemU9NTAsIHJlcGxhY2U9VFJVRSwgcHJvYj1jKDAuNSwgMC41KSkKeTEgPC0gc2FtcGxlKCAgYyhUUlVFLCBGQUxTRSksIHNpemU9MjAwLCByZXBsYWNlPVRSVUUsIHByb2I9YygwLjMsIDAuNykpCnkyIDwtIHNhbXBsZSggIGMoVFJVRSwgRkFMU0UpLCBzaXplPTUwLCByZXBsYWNlPVRSVUUsIHByb2I9YygwLjIsIDAuOCkpCnoxIDwtIHJub3JtKDIwMCwgbWVhbj0wLCBzZD0xKQp6MiA8LSBybm9ybSg1MCwgbWVhbj0yLCBzZD0yKQp3MSA8LSBycG9pcygyMDAsIGxhbWJkYT0yKQp3MiA8LSBycG9pcyg1MCwgbGFtYmRhPTMpCgojIGxhYmVscwpkYXRhX2dlbmVyYXRlZCA8LSBkYXRhLmZyYW1lKCJ4IiA9IGMoeDEsIHgyKSwgInkiPWMoeTEsIHkyKSwgInoiPWMoejEsIHoyKSwgInciPWModzEsIHcyKSwgImxhYmVsIj1hcy5mYWN0b3IoYyhyZXAoLTEsIDIwMCksIHJlcCgxLDUwKSkpKQoKaGVhZChkYXRhX2dlbmVyYXRlZCkKYGBgCgpQYXJ0aXppb25pYW1vIGlsIGRhdGFzZXQgaW4gdHJhaW4gZSB0ZXN0IHVzYW5kbyBpbCBjb21hbmRvIGBgY3JlYXRlRGF0YVBhcnRpdGlvbigpYGAgZGFsIHBhY2NoZXR0byBgYGNhcmV0YGAuIFF1ZXN0byBjYW1waW9uYSBpbiBtb2RvIGNhc3VhbGUgY29tZSBgYHNhbXBsZSgpYGAgbWEgY2VyY2EgZGkgcmlzcGV0dGFyZSBsYSBhbmNoZSBkaXN0cmlidXppb25lIGRlbGxlIGRpdmVyc2UgY2xhc3NpLgoKYGBge3J9CnRyYWluX2luZGV4IDwtIGNyZWF0ZURhdGFQYXJ0aXRpb24oZGF0YV9nZW5lcmF0ZWQkbGFiZWwsIHAgPSAwLjgsIGxpc3QgPSBGQUxTRSkKdHJhaW5fZGF0YV9nZW5lcmF0ZWQgPC0gZGF0YV9nZW5lcmF0ZWRbdHJhaW5faW5kZXgsIF0KdGVzdF9kYXRhX2dlbmVyYXRlZCA8LSBkYXRhX2dlbmVyYXRlZFstdHJhaW5faW5kZXgsIF0KCnByaW50KHBhc3RlKCJUYWdsaWEgZGVsIHRyYWluIHNldDoiLG5yb3codHJhaW5fZGF0YV9nZW5lcmF0ZWQpICkpCnByaW50KHBhc3RlKCJUYWdsaWEgZGVsIHRlc3Qgc2V0OiIsIG5yb3codGVzdF9kYXRhX2dlbmVyYXRlZCkgKSkKCmBgYAoKIyMjIERhdGFzZXQgR2VybWFuIENyZWRpdCBEYXRhCgpOZWwgcGFjY2hldHRvIGBgY2FyZXRgYCB2aSBzb25vIGRpdmVyc2kgZGF0YXNldCBwcmVjYXJpY2F0aS4gVXNpYW1vIGlsIGRhdGFzZXQgYGBHZXJtYW5DcmVkaXRgYCBwZXIgYWRkZXN0cmFyZSBlIHRlc3RhcmUgaSBtb2RlbGxpIGRpIGNsYXNzaWZpY2F6aW9uZSBiYXNhdGkgc3UgQmF5ZXMuCgpgYGB7cn0KZGF0YSgiR2VybWFuQ3JlZGl0IikKCiMgVmlzdWFsaXp6YSBsZSBwcmltZSByaWdoZSBkZWwgZGF0YXNldAoKaGVhZChHZXJtYW5DcmVkaXQpCgpgYGAKClN1ZGRpdmlkaWFtbyBpbCBkYXRhc2V0IGluIHRyYWluaW5nIGUgdGVzdC4KCmBgYHtyfQpzZXQuc2VlZCg0MikKCnRyYWluX2luZGV4X2djIDwtIGNyZWF0ZURhdGFQYXJ0aXRpb24oR2VybWFuQ3JlZGl0JENsYXNzLCBwID0gMC43LCBsaXN0ID0gRkFMU0UpCnRyYWluX3NldF9nYyA8LSBHZXJtYW5DcmVkaXRbdHJhaW5faW5kZXhfZ2MsIF0KdGVzdF9zZXRfZ2MgPC0gR2VybWFuQ3JlZGl0Wy10cmFpbl9pbmRleF9nYywgXQoKcHJpbnQocGFzdGUoIlRhZ2xpYSBkZWwgdHJhaW4gc2V0OiIsbnJvdyh0cmFpbl9zZXRfZ2MpICkpCnByaW50KHBhc3RlKCJUYWdsaWEgZGVsIHRlc3Qgc2V0OiIsIG5yb3codGVzdF9zZXRfZ2MpICkpCgpgYGAKCiMjIyBEYXRhc2V0IEluZm9ydHVuaSBzdWwgTGF2b3JvIGluIFRvc2NhbmEKCkkgZGF0aSBzdWdsaSBpbmZvcnR1bmkgc3VsIGxhdm9ybyBpbiBJdGFsaWEgZGl2aXNpIHBlciByZWdpb25lIGUgY29uIGFsdGEgZ3JhbnVsYXJpdMOgIHNvbm8gZGlzcG9uaWJpbGkgb25saW5lIHN1bCBzaXRvIFtJbmFpbCBPcGVuIERhdGFdKGh0dHBzOi8vZGF0aS5pbmFpbC5pdC9wb3J0YWxlL2l0L2dsaS1vcGVuLWRhdGEtaW5haWwvZGF0aS1zdG9yaWNpL2luZm9ydHVuaS1zdWwtbGF2b3JvLmh0bWw/cGFnZT0xKS4gQWJiaWFtbyBzY2FyaWNhdG8gaWwgZGF0YXNldCByZWxhdGl2byBhaSBkYXRpIG1lbnNpbGkgZSBsbyBhYmJpYW1vIHNhbHZhdG8gaW4gZm9ybWF0byBDU1YgbmVsbGEgY2FydGVsbGEgYGBkYXRhc2V0c2BgLiBDYXJpY2hpYW1vIGlsIGRhdGFzZXQgdXNhbmRvIGlsIHBhY2NoZXR0byBgYHJpb2BgLgoKCmBgYHtyfQoKbGlicmFyeShyaW8pCgppbmZvcnR1bmlfdG9zY2FuYSA8LSBpbXBvcnQoImRhdGFzZXRzL0RhdGlDb25DYWRlbnphTWVuc2lsZUluZm9ydHVuaVRvc2NhbmEuY3N2IikKCmhlYWQoaW5mb3J0dW5pX3Rvc2NhbmEpCgpgYGAKTm90aWFtbyBjaGUgaW4gdHV0dG8gaWwgZGF0YXNldCBjb21wcmVuZGUgYHIgbnJvdyhpbmZvcnR1bmlfdG9zY2FuYSlgIHJpZ2hlLiAKClNlbGV6aW9uaWFtbyBzb2xvIGFsY3VuZSBjb2xvbm5lIGRpIGZlYXR1cmVzIHJpbGV2YW50aS4KCmBgYHtyfQppbmZvcnR1bmlfdG9zY2FuYV90aWR5IDwtIGluZm9ydHVuaV90b3NjYW5hWyBjKDUsIDcsIDgsIDksIDEwLCAxMSwxMywgMTUpXQoKCmhlYWQoaW5mb3J0dW5pX3Rvc2NhbmFfdGlkeSkKYGBgCgpVbiBvYmlldHRpdm8gcG90cmViYmUgZXNzZXJlIGRpIGNsYXNzaWZpY2FyZSBpbCBsdW9nbyBkaSBuYXNjaXRhIChJVEFMSUEvRVNURVJPKSBkZWxsJ2luZm9ydHVuYXRvL2EgaW4gYmFzZSBhbGxlIGFsdHJlIGNhcmF0dGVyaXN0aWNoZS4gVHJhc2Zvcm1pYW1vIHF1aW5kaSBsYSBjb2xvbm5hICpMdW9nb05hc2NpdGEqIGluIHVuYSBmZWF0dXJlIGJpbmFyaWEgKCpOYXRJdGFsKikgZWQgZXN0cmFpYW1vIGFuY2hlIGluIHF1ZXN0byBjYXNvIGlsIGRhdGFzZXQgaW4gdHJhaW5pbmcgZSB0ZXN0IHNldC4KCmBgYHtyfQpzZXQuc2VlZCg0MikKCmluZm9ydHVuaV90b3NjYW5hX3RpZHkkTmF0SXRhbCA8LSBmYWN0b3IoaW5mb3J0dW5pX3Rvc2NhbmFfdGlkeSRMdW9nb05hc2NpdGEgPT0gIklUQUwiKQoKIyByaW11b3ZpYW1vIGxhIGNvbG9ubmEgTHVvZ29OYXNjaXRhCmluZm9ydHVuaV90b3NjYW5hX3RpZHkkTHVvZ29OYXNjaXRhIDwtIE5VTEwKCiMgZXN0cmFpYW1vIHRyYWluIGUgdGVzdCBzZXQgdXNhbmRvIGxhIGNvbG9ubm5hIE5hdEl0YWwgY29tZSBsYWJlbAoKdHJhaW5faW5kZXhfaXQgPC0gY3JlYXRlRGF0YVBhcnRpdGlvbihpbmZvcnR1bmlfdG9zY2FuYV90aWR5JE5hdEl0YWwsIHAgPSAwLjcsIGxpc3QgPSBGQUxTRSkKCnRyYWluX3NldF9pdCA8LSBpbmZvcnR1bmlfdG9zY2FuYV90aWR5W3RyYWluX2luZGV4X2l0LCBdCnRlc3Rfc2V0X2l0IDwtIGluZm9ydHVuaV90b3NjYW5hX3RpZHlbLXRyYWluX2luZGV4X2l0LCBdCgpwcmludChwYXN0ZSgiVGFnbGlhIGRlbCB0cmFpbiBzZXQ6Iixucm93KHRyYWluX3NldF9pdCkgKSkKcHJpbnQocGFzdGUoIlRhZ2xpYSBkZWwgdGVzdCBzZXQ6IiwgbnJvdyh0ZXN0X3NldF9pdCkgKSkKCgpgYGAKCiMjIE5haXZlIEJheWVzCgpSaWNvcmRpYW1vIGNoZSBpbCBjbGFzc2lmaWNhdG9yZSBOYWl2ZSBCYXllcyBzaSBiYXNhIHN1bGxhIGZvcm11bGEgZGkgQmF5ZXMsIGFzc3VtZW5kbyBsJ2luZGlwZW5kZW56YSBjb25kaXppb25hbGUgdHJhIGxlIGZlYXR1cmVzIGRhdGEgbGEgbGFiZWwuIExhIHByZXZpc2lvbmUgcGVyIHVuYSBudW92YSBvc3NlcnZhemlvbmUgJHg9KHhfMSwgeF8yLCBcbGRvdHMsIHhfZCkkIHZpZW5lIGVmZmV0dHVhdGEgY2FsY29sYW5kbyBsYSBwcm9iYWJpbGl0w6AgYSBwb3N0ZXJpb3JpIHBlciBjaWFzY3VuYSBsYWJlbCAkXGVsbCQgZSBzY2VnbGllbmRvIGxhIGxhYmVsIGNvbiBsYSBwcm9iYWJpbGl0w6AgbWFzc2ltYS4KCkNpIHNvbm8gdmFyaSBwYWNjaGV0dGkgY2hlIGNvbnRlbmdvbm8gZnVuemlvbmkgcGVyIGNhbGNvbGFyZSBjbGFzc2lmaWNhdG9yaSBOYWl2ZSBCYXllcyBpbiBSOiBgYGNhcmV0YGAgKGNvbnNpZ2xpYXRvIGFuY2hlIHNlIHVuIHBvJyBwacO5IGxlbnRvKSwgYGBlMTA3MWBgIGUgYGBuYWl2ZWJheWVzYGAuCgoKIyMjIERhdGFzZXQgZ2VuZXJhdG8KClZlZGlhbW9saSBpbiBhemlvbmUgc3VsIGRhdGFzZXQgZ2VuZXJhdG8uIElsIGNvbWFuZG8gw6ggbmVsIHBhY2NoZXR0byBgYGNhcmV0YGAgw6ggYGB0cmFpbigpYGAgc3BlY2lmaWNhbmRvIG5lbGxlIG9wemlvbmkgaWwgbWV0b2RvIGBgbWV0aG9kPSJuYWl2ZV9iYXllcyJgYC4gIEJpc29nbmEgYW5jaGUgc3BlY2lmaWNhcmUgdW5hICpmb3JtdWxhKiBjb21lIGluIGFsdHJpIG1vZGVsbGkgZGkgcmVncmVzc2lvbmUvY2xhc3NpZmljYXppb25lIGluIFIgKHF1ZXN0byDDqCBpbCBwcmltbyBjYXNvIGNoZSB2ZWRpYW1vKS4KCgpgYGB7cn0KCiMgQWxsZW5hbWVudG8gZGVsIG1vZGVsbG8gTmFpdmUgQmF5ZXMgY29uIGNhcmV0Cm5iX21vZGVsX2NhcmV0IDwtIHRyYWluKGxhYmVsIH4gLiwgZGF0YSA9IHRyYWluX2RhdGFfZ2VuZXJhdGVkLCBtZXRob2QgPSAibmFpdmVfYmF5ZXMiKQoKI3ByaW50KG5iX21vZGVsX2NhcmV0KQoKIyB2YWx1dGEgc3VsIHRlc3Qgc2V0Cm5iX3ByZWRfY2FyZXQgPC0gcHJlZGljdChuYl9tb2RlbF9jYXJldCwgdGVzdF9kYXRhX2dlbmVyYXRlZCkKCmNvbmZ1c2lvbk1hdHJpeChuYl9wcmVkX2NhcmV0LCB0ZXN0X2RhdGFfZ2VuZXJhdGVkJGxhYmVsKQpgYGAKCkNvbmZyb250aWFtbyBjb24gaWwgcGFjY2hldHRvIGBgZTEwNzFgYC4KCmBgYHtyfQojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIE5haXZlIEJheWVzIGNvbiBlMTA3MQoKbmJfbW9kZWxfZTEwNzEgPC0gbmFpdmVCYXllcyhsYWJlbCB+IHgreit3LCBkYXRhID0gdHJhaW5fZGF0YV9nZW5lcmF0ZWQpCgojIGxhIGZvcm11bGEgaW5kaWNhIGNoZSB2b2dsaWFtbyBwcmV2ZWRlcmUgbGEgY29sb25uYSAibGFiZWwiIGluIGZ1bnppb25lIGRpIHR1dHRlIGxlIGFsdHJlIGNvbG9ubmUgKGZlYXR1cmVzKS4gU2UgYXZlc3NpbW8gdm9sdXRvIHVzYXJlIHNvbG8gYWxjdW5lIGZlYXR1cmVzIGFkIGVzZW1waW8gbGEgY29sb25uYSB4LCBhdnJlbW1vIHNjcml0dG8gYWQgZXNlbXBpbyBsYWJlbCB+IHgKCnByaW50KG5iX21vZGVsX2UxMDcxKQoKYGBgCgpGYWNjaWFtbyBvcmEgbGUgcHJldmlzaW9uaSBzdWwgdGVzdCBzZXQgZSBjYWxjb2xpYW1vIGxhIG1hdHJpY2UgZGkgY29uZnVzaW9uZSBlIGwnYWNjdXJhdGV6emEuIElsIGNvbWFuZG8gw6ggYHByZWRpY3QoKWAgY29tZSBwZXIgYWx0cmkgbW9kZWxsaSBpbiBSLiBMYSBzaW50YXNzaSByaWNoaWVkZSBkaSBzcGVjaWZpY2FyZSBpbCBtb2RlbGxvIGFsbGVuYXRvIGUgaWwgZGF0YXNldCBzdSBjdWkgZmFyZSBsZSBwcmV2aXNpb25pLgoKYGBge3J9CiMgUHJldmlzaW9uZSBzdWwgdGVzdCBzZXQKCm5iX3ByZWRfZTEwNzEgPC0gcHJlZGljdChuYl9tb2RlbF9lMTA3MSwgdGVzdF9kYXRhX2dlbmVyYXRlZCkKCiMgaWwgdmV0dG9yZSBjb250aWVuZSBsZSBldGljaGV0dGUgY2xhc3NpZmljYXRlLgojIHZlcmlmaWNoaWFtbyBsJ2FjY3VyYXRlenphIGUgYWx0cmUgbWV0cmljaGUgY29uIGxhIG1hdHJpY2UgZGkgY29uZnVzaW9uZQoKbmJfY29uZl9tYXRyaXhfZTEwNzEgPC0gY29uZnVzaW9uTWF0cml4KG5iX3ByZWRfZTEwNzEsIHRlc3RfZGF0YV9nZW5lcmF0ZWQkbGFiZWwpCgpwcmludChuYl9jb25mX21hdHJpeF9lMTA3MSkKCgpgYGAKCgpQb3NzaWFtbyBhbmNoZSBwbG90dGFyZSBsYSBjdXJ2YSBST0MgcGVyIHZhbHV0YXJlIGxhIHBlcmZvcm1hbmNlIGRlbCBjbGFzc2lmaWNhdG9yZSBhbCB2YXJpYXJlIGRlbGxhIHNvZ2xpYSBkaSBhY2NldGF6aW9uZSAobyBlcXVpdmFsZW50ZW1lbnRlIGRlbGxlIHByb2JhYmlsaXTDoCBhIHByaW9yaSkuIFVzaWFtbyBpbCBwYWNjaGV0dG8gYGBwUk9DYGAgcGVyIGNhbGNvbGFyZSBlIHBsb3R0YXJlIGxhIGN1cnZhIFJPQy4KCmBgYHtyfQpsaWJyYXJ5KHBST0MpCgojIENpIHNlcnZvbm8gbGUgcHJvYmFiaWxpdMOgIHByZWRldHRlIHBlciBsYSBjbGFzc2UgcG9zaXRpdmEsIG5vbiBzb2x0YW50byBsJ2V0aWNoZXR0YSBwcmVkZXR0YS4gUGVyIHF1ZXN0byBzcGVjaWZpY2hpYW1vIHR5cGU9InJhdyIgZSBwcmVuZGlhbW8gbGEgc2Vjb25kYSBjb2xvbm5hIChjb3JyaXNwb25kZW50ZSBhbGxhIGNsYXNzZSArMSkKCm5iX3ByZWRfcHJvYl9lMTA3MSA8LSBwcmVkaWN0KG5iX21vZGVsX2UxMDcxLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkLCB0eXBlID0gInJhdyIpWywgMl0KCiMgQ2FsY29sYSBsYSBST0MgY3VydmUgZWQgZXNlZ3VpIHVuIHBsb3QgdXNhbmRvIGdncm9jIChwYWNjaGV0dG8gcFJPQykuIFNwZWNpZmljaGlhbW8gbGVnYWN5LmF4ZXM9VFJVRSBwZXIgYXZlcmUgRlBSIG5lbGxlIGFzY2lzc2UKCnJvY19uYl9lMTA3MSA8LSByb2ModGVzdF9kYXRhX2dlbmVyYXRlZCRsYWJlbCwgbmJfcHJlZF9wcm9iX2UxMDcxKQoKZ2dyb2Mocm9jX25iX2UxMDcxLCBsZWdhY3kuYXhlcyA9IFRSVUUpICsKICBnZ3RpdGxlKCJST0MgQ3VydmUgcGVyIE5haXZlIEJheWVzIGRhdGFzZXQgZ2VuZXJhdG8iKSArCiAgeGxhYigiRmFsc2UgUG9zaXRpdmUgUmF0ZSIpICsKICB5bGFiKCJUcnVlIFBvc2l0aXZlIFJhdGUiKQoKYXVjKHJvY19uYl9lMTA3MSkKCmBgYAoKUGVyIGNvbmZyb250bywgYXBwbGljaGlhbW8gaW52ZWNlIGxhIGZ1bnppb25lIGBuYWl2ZV9iYXllcygpYCBkYWwgcGFjY2hldHRvIGBuYWl2ZWJheWVzYC4KCmBgYHtyfQojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIE5haXZlIEJheWVzIGNvbiBuYWl2ZWJheWVzCgpuYl9tb2RlbF9uYiA8LSBuYWl2ZV9iYXllcyhsYWJlbCB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhX2dlbmVyYXRlZCkKCnByaW50KG5iX21vZGVsX25iKQoKbmJfcHJlZF9uYiA8LSBwcmVkaWN0KG5iX21vZGVsX25iLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkWzE6Ml0pCgojIENvbmZyb250aWFtbyBsZSBkdWUgcHJldmlzaW9uaQoKdGFibGUobmJfcHJlZF9uYiwgbmJfcHJlZF9lMTA3MSkKCmBgYAoKQXBwbGljaGlhbW8gaW5maW5lICRrJC1ubiBzdWxsbyBzdGVzc28gZGF0YXNldCBwZXIgY29uZnJvbnRvLiBVc2lhbW8gc2VtcHJlIGlsIHBhY2NoZXR0byBgY2FyZXRgIHBlciBjb2VyZW56YS4KCmBgYHtyfQojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIEtOTgoKCiMgdXNpYW1vIGlsIHBhY2NoZXR0byBjYXJldCBlIGNyb3NzIHZhbGlkYXRpb24gcGVyIHNjZWdsaWVyZSBpbCB2YWxvcmUgZGkgawprbm5fbW9kZWxfZ2VuZXJhdGVkIDwtIHRyYWluKGxhYmVsIH4gLiwgZGF0YSA9IHRyYWluX2RhdGFfZ2VuZXJhdGVkLCBtZXRob2Q9ImtubiIsIHR1bmVMZW5ndGg9MTApCgpwcmludChrbm5fbW9kZWxfZ2VuZXJhdGVkKQpwbG90KGtubl9tb2RlbF9nZW5lcmF0ZWQpCmBgYAoKYGBge3J9CiMgUHJldmlzaW9uZSBzdWwgdGVzdCBzZXQKa25uX3ByZWRfZ2VuZXJhdGVkIDwtIHByZWRpY3Qoa25uX21vZGVsX2dlbmVyYXRlZCwgdGVzdF9kYXRhX2dlbmVyYXRlZCkKCiMgTWF0cmljZSBkaSBjb25mdXNpb25lIGUgYWNjdXJhdGV6emEKa25uX2NvbmZfbWF0cml4X2dlbmVyYXRlZCA8LSBjb25mdXNpb25NYXRyaXgoa25uX3ByZWRfZ2VuZXJhdGVkLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkJGxhYmVsKQoKcHJpbnQoa25uX2NvbmZfbWF0cml4X2dlbmVyYXRlZCkKYGBgCiMjIyBEYXRhc2V0IEdlcm1hbiBDcmVkaXQgRGF0YQoKQXBwbGljaGlhbW8gb3JhIE5haXZlIEJheWVzIHN1bCBkYXRhc2V0IEdlcm1hbiBDcmVkaXQgRGF0YS4gVmlzdWFsaXp6aWFtbyBwcmltYSBsYSBjb3JyZWxhemlvbmUgdHJhIGxlIGZlYXR1cmVzIHVzYW5kbyB1bmEgaGVhdG1hcC4KCmBgYHtyfQpsaWJyYXJ5KGdnY29ycnBsb3QpCgojIENhbGNvbGEgbGEgbWF0cmljZSBkaSBjb3JyZWxhemlvbmUgcmVsYXRpdmEgYWwgdHJhaW5pbmcgc2V0IHBlciBnbGkgaW5kaXZpZHVpIGNvbiB1bmEgYnVvbmEvY2F0dGl2YSBjbGFzc2lmaWNhemlvbmUgZGkgY3JlZGl0bwoKY29yX21hdHJpeF9nYyA8LSBjb3IodHJhaW5fc2V0X2djW3RyYWluX3NldF9nYyRDbGFzcz09Ikdvb2QiLCBzYXBwbHkodHJhaW5fc2V0X2djLCBpcy5udW1lcmljKV0pCiMgUGxvdCBkZWxsYSBoZWF0bWFwCmdnY29ycnBsb3QoY29yX21hdHJpeF9nYywgCiAgICAgICAgICAgbWV0aG9kID0gInNxdWFyZSIsIAogICAgICAgICAgIHR5cGUgPSAiZnVsbCIsIAogICAgICAgICAgIGxhYiA9IEZBTFNFLCAKICAgICAgICAgICB0aXRsZSA9ICJNYXRyaWNlIGRpIENvcnJlbGF6aW9uZSAtIEdlcm1hbiBDcmVkaXQgRGF0YSIsIHRsLmNleD0wKQoKYGBgCkFwcGxpY2hpYW1vIE5haXZlIEJheWVzIHBlciBkZXRlcm1pbmFyZSBzZSB1biBpbmRpdmlkdW8gaGEgdW4gYnVvbiBvIGNhdHRpdm8gY3JlZGl0byAoY29sb25uYSAqQ2xhc3MqKS4KCmBgYHtyfQoKIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBOYWl2ZSBCYXllcwoKbmJfbW9kZWxfZ2MgPC0gbmFpdmVCYXllcyhDbGFzcyB+IC4sIGRhdGEgPSB0cmFpbl9zZXRfZ2MpCgojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0CgpuYl9wcmVkX2djIDwtIHByZWRpY3QobmJfbW9kZWxfZ2MsIHRlc3Rfc2V0X2djKQoKIyBNYXRyaWNlIGRpIGNvbmZ1c2lvbmUgZSBhY2N1cmF0ZXp6YQoKbmJfY29uZl9tYXRyaXhfZ2MgPC0gY29uZnVzaW9uTWF0cml4KG5iX3ByZWRfZ2MsIHRlc3Rfc2V0X2djJENsYXNzKQoKcHJpbnQobmJfY29uZl9tYXRyaXhfZ2MpCgoKYGBgCgpQbG90dGlhbW8gYW5jaGUgaW4gcXVlc3RvIGNhc28gbGEgY3VydmEgUk9DLgoKYGBge3J9CiMgYXR0ZW56aW9uZTogc2UgdXNhdGUgY2FyZXQgaWwgY29tYW5kbyBwZXIgb3R0ZW5lcmUgbGUgcHJvYmFiaWxpdMOgIHByZWRldHRlIMOoIGxlZ2dlcm1lbnRlIGRpdmVyc28gInByb2IiIGludmVjZSBkaSAicmF3IgoKbmJfcHJlZF9wcm9iX2djIDwtIHByZWRpY3QobmJfbW9kZWxfZ2MsIHRlc3Rfc2V0X2djLCB0eXBlID0gInJhdyIpWywgMl0KCiMgQ2FsY29sYSBsYSBST0MgY3VydmUgZWQgZXNlZ3VpIHVuIHBsb3QgdXNhbmRvIGdncm9jIChwYWNjaGV0dG8gcFJPQykuIFNwZWNpZmljaGlhbW8gbGVnYWN5LmF4ZXM9VFJVRSBwZXIgYXZlcmUgRlBSIG5lbGxlIGFzY2lzc2UKCnJvY19uYl9lMTA3MSA8LSByb2ModGVzdF9zZXRfZ2MkQ2xhc3MsIG5iX3ByZWRfcHJvYl9nYywgbGV2ZWxzPWMoIkdvb2QiLCAiQmFkIikpCgpnZ3JvYyhyb2NfbmJfZTEwNzEsIGxlZ2FjeS5heGVzID0gVFJVRSkgKwogIGdndGl0bGUoIlJPQyBDdXJ2ZSBwZXIgTmFpdmUgQmF5ZXMgZGF0YXNldCBnZW5lcmF0byIpICsKICB4bGFiKCJGYWxzZSBQb3NpdGl2ZSBSYXRlIikgKwogIHlsYWIoIlRydWUgUG9zaXRpdmUgUmF0ZSIpCgoKYGBgCkNpIGNoaWVkaWFtbzogcXVhbGkgZGVsbGUgZmVhdHVyZXMgc29ubyBwacO5IGltcG9ydGFudGkgcGVyIGxhIGNsYXNzaWZpY2F6aW9uZT8gVXNpYW1vIGxhIGZ1bnppb25lIGB2YXJJbXAoKWAgZGFsIHBhY2NoZXR0byBgY2FyZXRgIHBlciBjYWxjb2xhcmUgbCdpbXBvcnRhbnphIGRlbGxlIHZhcmlhYmlsaSBlZCBldmVudHVhbG1lbnRlIGVmZmV0dHVhcmUgdW5hICpzZWxlemlvbmUgZGVsbGUgZmVhdHVyZXMqIHBlciBhdW1lbnRhcmUgbCdpbnRlcHJldGFiaWxpdMOgIGRlbCBtb2RlbGxvLgoKYGBge3J9CgojIENhbGNvbGEgbCdpbXBvcnRhbnphIGRlbGxlIHZhcmlhYmlsaQoKdmFyX2ltcF9nYyA8LSB2YXJJbXAobmJfbW9kZWxfZ2MpCgpwcmludCh2YXJfaW1wX2djKQpgYGAKCioqRXNlcmNpemlvOioqIFByb3ZhdGUgYSByaWZhcmUgbCdhbmFsaXNpIGRpIE5haXZlIEJheWVzIHVzYW5kbyBzb2xvIGxlIHByaW1lIDUgZmVhdHVyZXMgcGnDuSBpbXBvcnRhbnRpIChpbiBiYXNlIGFsbGEgY2xhc3NpZmljYSBjYWxjb2xhdGEgc29wcmEpLiBDb21lIGNhbWJpYW5vIGxlIHBlcmZvcm1hbmNlIGRlbCBtb2RlbGxvPwoKCiMjIyBEYXRhc2V0IEluZm9ydHVuaSBzdWwgTGF2b3JvIGluIFRvc2NhbmEKCkFwcGxpY2hpYW1vIE5haXZlIEJheWVzIHN1bCBkYXRhc2V0IGRlZ2xpIGluZm9ydHVuaSBzdWwgbGF2b3JvIGluIFRvc2NhbmEgcGVyIHByZXZlZGVyZSBzZSBsJ2luZm9ydHVuYXRvIMOoIG5hdG8gaW4gSXRhbGlhIG8gYWxsJ2VzdGVybyAoY29sb25uYSAqTmF0SXRhbCopLgoKYGBge3J9CgojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIE5haXZlIEJheWVzCgojbmJfbW9kZWxfaXQgPC0gdHJhaW4oTmF0SXRhbCB+IC4sIGRhdGEgPXRyYWluX3NldF9pdCwgbWV0aG9kPSJuYWl2ZV9iYXllcyIpCgpuYl9tb2RlbF9pdCA8LSBuYWl2ZUJheWVzKE5hdEl0YWwgfiAuLCBkYXRhID0gdHJhaW5fc2V0X2l0KQojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0CgpuYl9wcmVkX2l0IDwtIHByZWRpY3QobmJfbW9kZWxfaXQsIHRlc3Rfc2V0X2l0KQoKYGBgCgpDb25zaWRlcmlhbW8gbGEgcGVyZm9ybWFuY2UgY29uIGxhIHNvbGl0YSBtYXRyaWNlIGRpIGNvbmZ1c2lvbmUuCgpgYGB7cn0KCiMgTWF0cmljZSBkaSBjb25mdXNpb25lIGUgYWNjdXJhdGV6emEKCm5iX2NvbmZfbWF0cml4X2l0IDwtIGNvbmZ1c2lvbk1hdHJpeChhcy5mYWN0b3IobmJfcHJlZF9pdCksIGFzLmZhY3Rvcih0ZXN0X3NldF9pdCROYXRJdGFsKSkKCnByaW50KG5iX2NvbmZfbWF0cml4X2l0KQoKYGBgCgpgYGB7cn0KbmJfcHJlZF9wcm9iX2l0IDwtIHByZWRpY3QobmJfbW9kZWxfaXQsIHRlc3Rfc2V0X2l0LCB0eXBlID0gInJhdyIpWywgMl0KCiMgQ2FsY29sYSBsYSBST0MgY3VydmUgZWQgZXNlZ3VpIHVuIHBsb3QgdXNhbmRvIGdncm9jIChwYWNjaGV0dG8gcFJPQykuIFNwZWNpZmljaGlhbW8gbGVnYWN5LmF4ZXM9VFJVRSBwZXIgYXZlcmUgRlBSIG5lbGxlIGFzY2lzc2UKCgpyb2NfbmJfaXQgPC0gcm9jKHRlc3Rfc2V0X2l0JE5hdEl0YWwsIG5iX3ByZWRfcHJvYl9pdCwgbGV2ZWxzPWMoIlRSVUUiLCAiRkFMU0UiKSkKCmdncm9jKHJvY19uYl9pdCwgbGVnYWN5LmF4ZXMgPSBUUlVFKSArCiAgZ2d0aXRsZSgiUk9DIEN1cnZlIHBlciBOYWl2ZSBCYXllcyBkYXRhc2V0IElOQUlMIikgKwogIHhsYWIoIkZhbHNlIFBvc2l0aXZlIFJhdGUiKSArCiAgeWxhYigiVHJ1ZSBQb3NpdGl2ZSBSYXRlIikKYGBgCgoKIyMgTERBIGUgUURBCgpBcHBsaWNoaWFtbyBsZGEgYWwgZGF0YXNldCBnZW5lcmF0by4gSWwgY29tYW5kbyBwZXIgYWxsZW5hcmUgaWwgbW9kZWxsbyDDqCBgbGRhKClgIGRhbCBwYWNjaGV0dG8gYE1BU1NgLiBPcHB1cmUgaWwgY29tYW5kbyBgdHJhaW4oKWAgZGFsIHBhY2NoZXR0byBgY2FyZXRgIHNwZWNpZmljYW5kbyBgbWV0aG9kPSJsZGEiYC5gCgpgYGB7cn0KCiMgQWxsZW5hbWVudG8gZGVsIG1vZGVsbG8gTERBCgpsZGFfbW9kZWxfZ2VuZXJhdGVkIDwtIGxkYShsYWJlbCB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhX2dlbmVyYXRlZCkKIyBQcmV2aXNpb25lIHN1bCB0ZXN0IHNldApsZGFfcHJlZF9nZW5lcmF0ZWQgPC0gcHJlZGljdChsZGFfbW9kZWxfZ2VuZXJhdGVkLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkKQojIE1hdHJpY2UgZGkgY29uZnVzaW9uZSBlIGFjY3VyYXRlenphCmxkYV9jb25mX21hdHJpeF9nZW5lcmF0ZWQgPC0gY29uZnVzaW9uTWF0cml4KGxkYV9wcmVkX2dlbmVyYXRlZCRjbGFzcywgdGVzdF9kYXRhX2dlbmVyYXRlZCRsYWJlbCkKcHJpbnQobGRhX2NvbmZfbWF0cml4X2dlbmVyYXRlZCkKCgpgYGAKQXBwbGljaGlhbW8gYW5jaGUgUURBIHBlciBjb25mcm9udG8uIElsIGNvbWFuZG8gw6ggYGBxZGEoKWBgLgoKYGBge3J9CgojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIFFEQQpxZGFfbW9kZWxfZ2VuZXJhdGVkIDwtIHFkYShsYWJlbCB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhX2dlbmVyYXRlZCkKIyBQcmV2aXNpb25lIHN1bCB0ZXN0IHNldApxZGFfcHJlZF9nZW5lcmF0ZWQgPC0gcHJlZGljdChxZGFfbW9kZWxfZ2VuZXJhdGVkLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkKQojIE1hdHJpY2UgZGkgY29uZnVzaW9uZSBlIGFjY3VyYXRlenphCnFkYV9jb25mX21hdHJpeF9nZW5lcmF0ZWQgPC0gY29uZnVzaW9uTWF0cml4KHFkYV9wcmVkX2dlbmVyYXRlZCRjbGFzcywgdGVzdF9kYXRhX2dlbmVyYXRlZCRsYWJlbCkKcHJpbnQocWRhX2NvbmZfbWF0cml4X2dlbmVyYXRlZCkKYGBgCgpDb25mcm9udGlhbW8gbGUgY3VydmUgUk9DIHBlciBpIGR1ZSBtb2RlbGxpIChMREEgZSBRREEpLgoKYGBge3J9CgpsZGFfcHJlZF9wcm9iX2dlbmVyYXRlZCA8LSBwcmVkaWN0KGxkYV9tb2RlbF9nZW5lcmF0ZWQsIHRlc3RfZGF0YV9nZW5lcmF0ZWQpJHBvc3RlcmlvclssIDJdCnFkYV9wcmVkX3Byb2JfZ2VuZXJhdGVkIDwtIHByZWRpY3QocWRhX21vZGVsX2dlbmVyYXRlZCwgdGVzdF9kYXRhX2dlbmVyYXRlZCkkcG9zdGVyaW9yWywgMl0KIyBDYWxjb2xhIGxhIFJPQyBjdXJ2ZSBlZCBlc2VndWkgdW4gcGxvdCB1c2FuZG8gZ2dyb2MgKHBhY2NoZXR0byBwUk9DKS4gU3BlY2lmaWNoaWFtbyBsZWdhY3kuYXhlcz1UUlVFIHBlciBhdmVyZSBGUFIgbmVsbGUgYXNjaXNzZQpyb2NfbGRhX2dlbmVyYXRlZCA8LSByb2ModGVzdF9kYXRhX2dlbmVyYXRlZCRsYWJlbCwgbGRhX3ByZWRfcHJvYl9nZW5lcmF0ZWQpCnJvY19xZGFfZ2VuZXJhdGVkIDwtIHJvYyh0ZXN0X2RhdGFfZ2VuZXJhdGVkJGxhYmVsLCBxZGFfcHJlZF9wcm9iX2dlbmVyYXRlZCkKZ2dyb2Mocm9jX2xkYV9nZW5lcmF0ZWQsIGxlZ2FjeS5heGVzID0gVFJVRSwgY29sb3I9ImJsdWUiKSArCiAgZ2d0aXRsZSgiUk9DIEN1cnZlIHBlciBMREEgKGJsdSkgZSBRREEgKHZlcmRlKSAtIERhdGFzZXQgR2VuZXJhdG8iKSArCiAgeGxhYigiRmFsc2UgUG9zaXRpdmUgUmF0ZSIpICsKICB5bGFiKCJUcnVlIFBvc2l0aXZlIFJhdGUiKSArCiAgZ2VvbV9saW5lKGRhdGEgPSBnZ3JvYyhyb2NfcWRhX2dlbmVyYXRlZCkkZGF0YSwgYWVzKHggPSAxIC0gc3BlY2lmaWNpdHksIHkgPSBzZW5zaXRpdml0eSksIGNvbG9yPSJncmVlbiIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAiYm90dG9tIikgKwogIGd1aWRlcyhjb2xvciA9IGd1aWRlX2xlZ2VuZChvdmVycmlkZS5hZXMgPSBsaXN0KHNpemUgPSA0KSkpCmBgYAojIyMgRGF0YXNldCBHZXJtYW4gQ3JlZGl0IERhdGEKCkFwcGxpY2hpYW1vIG9yYSBMREEgc3VsIGRhdGFzZXQgR2VybWFuIENyZWRpdCBEYXRhLgoKYGBge3IgZXZhbD1GQUxTRX0KIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBMREEKCiMgc2UgYXBwbGljYXRvIGludGVyYW1lbnRlIGFsIGRhdGFzZXQgYWJiaWFtbyB1biBlcnJvcmUgcGVyY2jDqCBhbGN1bmUgY29sb25uZSBhbGwnaW50ZXJubyBkZWkgZ3J1cHBpIHNvbm8gY29zdGFudGkuIFF1ZXN0byBjcmVhIGRlaSBwcm9ibGVtaSBuZWxsYSBzdGltYSBkZWxsYSB2YXJpYW56YS4gUmltdW92aWFtb2xlLgoKI3RyYWluX3NldF9nY1tjKDI1LCAyNiwgMzAsIDMzLCAzNiwgIDM5LCA0MiwgNDQpXSA8LSBOVUxMCgpnY190aWR5IDwtIHRyYWluX3NldF9nY1sxOjEwXQoKbGRhX21vZGVsX2djIDwtIHRyYWluKENsYXNzIH4gLiwgZGF0YSA9IGdjX3RpZHksIG1ldGhvZD0ibGRhIikKIyBQcmV2aXNpb25lIHN1bCB0ZXN0IHNldApsZGFfcHJlZF9nYyA8LSBwcmVkaWN0KGxkYV9tb2RlbF9nYywgdGVzdF9zZXRfZ2NbMToxMF0pCgojIE1hdHJpY2UgZGkgY29uZnVzaW9uZSBlIGFjY3VyYXRlenphCmxkYV9jb25mX21hdHJpeF9nYyA8LSBjb25mdXNpb25NYXRyaXgobGRhX3ByZWRfZ2MsIHRlc3Rfc2V0X2djJENsYXNzKQpwcmludChsZGFfY29uZl9tYXRyaXhfZ2MpCgpgYGAKClBsb3R0aWFtbyBhbmNoZSBpbiBxdWVzdG8gY2FzbyBsYSBjdXJ2YSBST0MgKHNvdnJhcHBvbmVuZG9sYSBhIHF1ZWxsYSBkaSBOYWl2ZSBCYXllcyBwZXIgY29uZnJvbnRvKS4KCmBgYHtyIGV2YWw9RkFMU0V9CgpsZGFfcHJlZF9wcm9iX2djIDwtIHByZWRpY3QobGRhX21vZGVsX2djLCB0ZXN0X3NldF9nYywgdHlwZT0icHJvYiIpWywgMl0KCiMgQ2FsY29sYSBsYSBST0MgY3VydmUgZWQgZXNlZ3VpIHVuIHBsb3QgdXNhbmRvIGdncm9jIChwYWNjaGV0dG8gcFJPQykuIFNwZWNpZmljaGlhbW8gbGVnYWN5LmF4ZXM9VFJVRSBwZXIgYXZlcmUgRlBSIG5lbGxlIGFzY2lzc2UKCnJvY19sZGFfZ2MgPC0gcm9jKHRlc3Rfc2V0X2djJENsYXNzLCBsZGFfcHJlZF9wcm9iX2djLCBsZXZlbHM9YygiR29vZCIsICJCYWQiKSkKCmdncm9jKHJvY19sZGFfZ2MsIGxlZ2FjeS5heGVzID0gVFJVRSwgY29sb3I9ImJsdWUiKSArCiAgZ2d0aXRsZSgiUk9DIEN1cnZlIHBlciBOYWl2ZSBCYXllcyAocm9zc28pIGUgTERBIChibHUpLSBHZXJtYW4gQ3JlZGl0IERhdGEiKSArCiAgeGxhYigiRmFsc2UgUG9zaXRpdmUgUmF0ZSIpICsKICB5bGFiKCJUcnVlIFBvc2l0aXZlIFJhdGUiKSArCiAgZ2VvbV9saW5lKGRhdGEgPSBnZ3JvYyhyb2NfbmJfZTEwNzEpJGRhdGEsIGFlcyh4ID0gMSAtIHNwZWNpZmljaXR5LCB5ID0gc2Vuc2l0aXZpdHkpLCBjb2xvcj0icmVkIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJib3R0b20iKSArCiAgZ3VpZGVzKGNvbG9yID0gZ3VpZGVfbGVnZW5kKG92ZXJyaWRlLmFlcyA9IGxpc3Qoc2l6ZSA9IDQpKSkKCmBgYApWZWRpYW1vIGNoZSBMREEgbWlnbGlvcmEgbGVnZ2VybWVudGUgbGUgcGVyZm9ybWFuY2UgcmlzcGV0dG8gYSBOYWl2ZSBCYXllcyBpbiBxdWVzdG8gY2Fzby4gCgoKIyMjIERhdGFzZXQgSW5mb3J0dW5pIHN1bCBMYXZvcm8gaW4gVG9zY2FuYQoKQXBwbGljaGlhbW8gb3JhIExEQSBlIFFEQSBzdWwgZGF0YXNldCBkZWdsaSBpbmZvcnR1bmkgc3VsIGxhdm9ybyBpbiBUb3NjYW5hIHBlciBwcmV2ZWRlcmUgc2UgbCdpbmZvcnR1bmF0byDDqCBuYXRvIGluIEl0YWxpYSBvIGFsbCdlc3Rlcm8gKGNvbG9ubmEgKk5hdEl0YWwqKS4gVXNpYW1vIHByaW1hIExEQS4KCmBgYHtyfQoKIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBMREEKbGRhX21vZGVsX2l0IDwtIGxkYShOYXRJdGFsIH4gLiwgZGF0YSA9IHRyYWluX3NldF9pdCkKIyBQcmV2aXNpb25lIHN1bCB0ZXN0IHNldApsZGFfcHJlZF9pdCA8LSBwcmVkaWN0KGxkYV9tb2RlbF9pdCwgdGVzdF9zZXRfaXQpCiMgTWF0cmljZSBkaSBjb25mdXNpb25lIGUgYWNjdXJhdGV6emEKbGRhX2NvbmZfbWF0cml4X2l0IDwtIGNvbmZ1c2lvbk1hdHJpeChsZGFfcHJlZF9pdCRjbGFzcywgdGVzdF9zZXRfaXQkTmF0SXRhbCkKcHJpbnQobGRhX2NvbmZfbWF0cml4X2l0KQoKYGBgCgpDb25mcm9udGlhbW8gbGUgcHJldmlzaW9uaSBkZWkgZHVlIG1vZGVsbGkgKExEQSBlIE5haXZlIEJheWVzKS4KCmBgYHtyfQoKIyB0YWJlbGxhIGRpIGNvbnRpbmdlbnphCgp0YWJsZShsZGFfcHJlZF9pdCRjbGFzcywgbmJfcHJlZF9pdCkKCmBgYApDb25mcm9udGlhbW8gbGUgY3VydmUgUk9DLgoKYGBge3J9CgpsZGFfcHJlZF9wcm9iX2l0IDwtIHByZWRpY3QobGRhX21vZGVsX2l0LCB0ZXN0X3NldF9pdCkkcG9zdGVyaW9yWywgMl0KIyBDYWxjb2xhIGxhIFJPQyBjdXJ2ZSBlZCBlc2VndWkgdW4gcGxvdCB1c2FuZG8gZ2dyb2MgKHBhY2NoZXR0byBwUk9DKS4gU3BlY2lmaWNoaWFtbyBsZWdhY3kuYXhlcz1UUlVFIHBlciBhdmVyZSBGUFIgbmVsbGUgYXNjaXNzZQoKcm9jX2xkYV9pdCA8LSByb2ModGVzdF9zZXRfaXQkTmF0SXRhbCwgbGRhX3ByZWRfcHJvYl9pdCwgbGV2ZWxzPWMoIlRSVUUiLCAiRkFMU0UiKSkKCmdncm9jKHJvY19sZGFfaXQsIGxlZ2FjeS5heGVzID0gVFJVRSwgY29sb3I9ImJsdWUiKSArCiAgZ2d0aXRsZSgiUk9DIEN1cnZlIHBlciBOYWl2ZSBCYXllcyAocm9zc28pIGUgTERBIChibHUpLSBJTkFJTCBUb3NjYW5hIikgKwogIHhsYWIoIkZhbHNlIFBvc2l0aXZlIFJhdGUiKSArCiAgeWxhYigiVHJ1ZSBQb3NpdGl2ZSBSYXRlIikgKwogIGdlb21fbGluZShkYXRhID0gZ2dyb2Mocm9jX25iX2l0KSRkYXRhLCBhZXMoeCA9IDEgLSBzcGVjaWZpY2l0eSwgeSA9IHNlbnNpdGl2aXR5KSwgY29sb3I9InJlZCIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAiYm90dG9tIikgKwogIGd1aWRlcyhjb2xvciA9IGd1aWRlX2xlZ2VuZChvdmVycmlkZS5hZXMgPSBsaXN0KHNpemUgPSA0KSkpCgoKYGBgCk5vbiBzdHVwaXNjZSBjaGUgaWwgbW9kZWxsbyBMREEgYWJiaWEgcGVyZm9ybWFuY2UgcGVnZ2lvcmk6IG5vbiBzdGEgdXRpbGl6emFuZG8gbGUgY29sb25uZSBkaXNjcmV0ZSBpbiBtb2RvIG90dGltYWxlLgoKKipFc2VyY2l6aW86KiogUHJvdmF0ZSBhIHJpZmFyZSBsJ2FuYWxpc2kgZGkgTERBIHVzYW5kbyBzb2xvIGxlIGNvbG9ubmUgbnVtZXJpY2hlIGRlbCBkYXRhc2V0IGUgdHJhc2Zvcm1hbmRvIGV2ZW50dWFsaSBmYWN0b3IgaW4gbnVtZXJpY2kgKGNvbWUgaWwgZ2VuZXJlKS4gQ29tZSBjYW1iaWFubyBsZSBwZXJmb3JtYW5jZSBkZWwgbW9kZWxsbz8KCiMjIFJlZ3Jlc3Npb25lIExvZ2lzdGljYQoKQ29uc2lkZXJpYW1vIGlsIGRhdGFzZXQgZ2VuZXJhdG8sIGNoZSBjb250aWVuZSA0IGZlYXR1cmVzICh0dXR0ZSBudW1lcmljaGUpIGUgZHVlIHNvbGUgbGFiZWxzLiBJbCBjb21hbmRvIHBlciBhcHBsaWNhcmUgbGEgcmVncmVzc2lvbmUgbG9naXN0aWNhIGluIFIgw6ggYGdsbSgpYCBzcGVjaWZpY2FuZG8gYGZhbWlseT1iaW5vbWlhbGAuIFBvc3NpYW1vIGluIGFsdGVybmF0aXZhIHVzYXJlIGlsIHBhY2NoZXR0byBgY2FyZXRgIGNvbiBgbWV0aG9kPSJtdWx0aW5vbSJgIChwZXIgbGEgcmVncmVzc2lvbmUgbG9naXN0aWNhIG11bHRpbm9taWFsZSwgY2hlIGZ1bnppb25hIGFuY2hlIHBlciBpbCBjYXNvIGJpbmFyaW8pLgoKCmBgYHtyfQojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIGRpIHJlZ3Jlc3Npb25lIGxvZ2lzdGljYQpsb2dfbW9kZWxfZ2VuZXJhdGVkIDwtIGdsbShsYWJlbCB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhX2dlbmVyYXRlZCwgZmFtaWx5ID0gYmlub21pYWwpCgojY29uIGxhIGZ1bnppb25lIHN1bW1hcnkoKSBvdHRlbmlhbW8gdW4gcmlhc3N1bnRvIGRlbCBtb2RlbGxvCnN1bW1hcnkobG9nX21vZGVsX2dlbmVyYXRlZCkKYGBgCmBgYHtyfQoKCiMgUHJldmlzaW9uZSBzdWwgdGVzdCBzZXQKbG9nX3ByZWRfZ2VuZXJhdGVkX3Byb2IgPC0gcHJlZGljdChsb2dfbW9kZWxfZ2VuZXJhdGVkLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkLCB0eXBlID0gInJlc3BvbnNlIikKCiMgQ29udmVydGlhbW8gbGUgcHJvYmFiaWxpdMOgIGluIGV0aWNoZXR0ZQpsb2dfcHJlZF9nZW5lcmF0ZWQgPC0gaWZlbHNlKGxvZ19wcmVkX2dlbmVyYXRlZF9wcm9iID4gMC41LCAxLCAtMSkKCiMgTWF0cmljZSBkaSBjb25mdXNpb25lIGUgYWNjdXJhY3kKCmxvZ19jb25mX21hdHJpeF9nZW5lcmF0ZWQgPC0gY29uZnVzaW9uTWF0cml4KGFzLmZhY3Rvcihsb2dfcHJlZF9nZW5lcmF0ZWQpLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkJGxhYmVsKQpwcmludChsb2dfY29uZl9tYXRyaXhfZ2VuZXJhdGVkKQoKYGBgCgpQbG90dGlhbW8gb3JhIGxlIGN1cnZlIFJPQyBwZXIgaSB0cmUgbWV0b2RpIChOYWl2ZSBCYXllcywgTERBLCBSZWdyZXNzaW9uZSBMb2dpc3RpY2EpIHBlciBjb25mcm9udG8uCgpgYGB7cn0KCmxvZ19wcmVkX3Byb2JfZ2VuZXJhdGVkIDwtIHByZWRpY3QobG9nX21vZGVsX2dlbmVyYXRlZCwgdGVzdF9kYXRhX2dlbmVyYXRlZCwgdHlwZSA9ICJyZXNwb25zZSIpCgojIENhbGNvbGEgbGEgUk9DIGN1cnZlIGVkIGVzZWd1aSB1biBwbG90IHVzYW5kbyBnZ3JvYyAocGFjY2hldHRvIHBST0MpLiBTcGVjaWZpY2hpYW1vIGxlZ2FjeS5heGVzPVRSVUUgcGVyIGF2ZXJlIEZQUiBuZWxsZSBhc2Npc3NlCnJvY19sb2dfZ2VuZXJhdGVkIDwtIHJvYyh0ZXN0X2RhdGFfZ2VuZXJhdGVkJGxhYmVsLCBsb2dfcHJlZF9wcm9iX2dlbmVyYXRlZCkKZ2dyb2Mocm9jX2xvZ19nZW5lcmF0ZWQsIGxlZ2FjeS5heGVzID0gVFJVRSwgY29sb3I9ImdyZWVuIikgKwogIGdndGl0bGUoIlJPQzogTkIgKHJvc3NvKSwgTERBIChibHUpIGUgUkwgKHZlcmRlKSAtIERhdGFzZXQgR2VuZXJhdG8iKSArCiAgeGxhYigiRmFsc2UgUG9zaXRpdmUgUmF0ZSIpICsKICB5bGFiKCJUcnVlIFBvc2l0aXZlIFJhdGUiKSArCiAgZ2VvbV9saW5lKGRhdGEgPSBnZ3JvYyhyb2NfbmJfZTEwNzEpJGRhdGEsIGFlcyh4ID0gMSAtIHNwZWNpZmljaXR5LCB5ID0gc2Vuc2l0aXZpdHkpLCBjb2xvcj0icmVkIikgKwogIGdlb21fbGluZShkYXRhID0gZ2dyb2Mocm9jX2xkYV9nZW5lcmF0ZWQpJGRhdGEsIGFlcyh4ID0gMSAtIHNwZWNpZmljaXR5LCB5ID0gc2Vuc2l0aXZpdHkpLCBjb2xvcj0iYmx1ZSIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAiYm90dG9tIikgKwogIGd1aWRlcyhjb2xvciA9IGd1aWRlX2xlZ2VuZChvdmVycmlkZS5hZXMgPSBsaXN0KHNpemUgPSA0KSkpCmBgYAoKCkNvbnNpZGVyaWFtbyBpbmZpbmUgdW4gbW9kZWxsbyBkaSBjbGFzc2lmaWNhemlvbmUgbmVsIGNhc28gbXVsdGktY2xhc3NlLiBQZXIgc2VtcGxpY2l0w6AgYWdnaXVuZ2lhbW8gdW5hIHRlcnphIGNsYXNzZSBhbCBkYXRhc2V0IGdlbmVyYXRvLgoKYGBge3J9CgojIEFnZ2l1bmdpYW1vIHVuYSB0ZXJ6YSBjbGFzc2UgYWwgZGF0YXNldCBnZW5lcmF0bwp4MyA8LSBzYW1wbGUoIDA6MSwgc2l6ZT04MCwgcmVwbGFjZT1UUlVFLCBwcm9iPWMoMC4yLCAwLjgpKQp5MyA8LSBzYW1wbGUoIDA6MSwgc2l6ZT04MCwgcmVwbGFjZT1UUlVFLCBwcm9iPWMoMC41LCAwLjUpKQp6MyA8LSBybm9ybSg4MCwgbWVhbj0wLCBzZD0yKQp3MyA8LSBycG9pcyg4MCwgbGFtYmRhPTUpCgpkYXRhX2dlbmVyYXRlZF9tdWx0aSA8LSBkYXRhLmZyYW1lKCJ4IiA9IGMoeDEsIHgyLCB4MyksICJ5Ij1jKHkxLCB5MiwgeTMpLCAieiI9Yyh6MSwgejIsIHozKSwgInciPWModzEsIHcyLCB3MyksICJsYWJlbCI9YXMuZmFjdG9yKGMocmVwKC0xLCAyMDApLCByZXAoMSw1MCksIHJlcCgwLDgwKSkpKQoKIyBTdWRkaXZpc2lvbmUgaW4gdHJhaW4gZSB0ZXN0IHNldAp0cmFpbl9pbmRleF9tdWx0aSA8LSBjcmVhdGVEYXRhUGFydGl0aW9uKGRhdGFfZ2VuZXJhdGVkX211bHRpJGxhYmVsLCBwID0gMC43LCBsaXN0ID0gRkFMU0UpCnRyYWluX2RhdGFfZ2VuZXJhdGVkX211bHRpIDwtIGRhdGFfZ2VuZXJhdGVkX211bHRpW3RyYWluX2luZGV4X211bHRpLCBdCnRlc3RfZGF0YV9nZW5lcmF0ZWRfbXVsdGkgPC0gZGF0YV9nZW5lcmF0ZWRfbXVsdGlbLXRyYWluX2luZGV4X211bHRpLCBdCgpnZ3Bsb3QoZGF0YV9nZW5lcmF0ZWRfbXVsdGksIGFlcyh4ID16LCB5ID0gdywgY29sb3IgPSBsYWJlbCkpICsKICBnZW9tX3BvaW50KCkgKwogIGxhYnModGl0bGUgPSAiRGF0YXNldCBGaXR0aXppbyBNdWx0aS1jbGFzc2UiLCB4ID0gImZlYXR1cmUgMyIsIHkgPSAiZmVhdHVyZSA0IikKCmBgYAoKQXBwbGljaGlhbW8gcHJpbWEgdW5hIHN0cmF0ZWdpYSBldXJpc3RpY2Egb25lLXZzLWFsbCBwZXIgbGEgcmVncmVzc2lvbmUgbG9naXN0aWNhIG11bHRpLWNsYXNzZS4KCmBgYHtyfQojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIGRpIHJlZ3Jlc3Npb25lIGxvZ2lzdGljYSBvbmUtdnMtYWxsCmxvZ19tb2RlbHNfbXVsdGkgPC0gbGlzdCgpCgpjbGFzc2VzIDwtIGxldmVscyh0cmFpbl9kYXRhX2dlbmVyYXRlZF9tdWx0aSRsYWJlbCkKZm9yIChjbHMgaW4gY2xhc3NlcykgewogIGJpbmFyeV9sYWJlbHMgPC0gaWZlbHNlKHRyYWluX2RhdGFfZ2VuZXJhdGVkX211bHRpJGxhYmVsID09IGNscywgMSwgMCkKICBsb2dfbW9kZWxzX211bHRpW1tjbHNdXSA8LSBnbG0oYmluYXJ5X2xhYmVscyB+IC4sIGRhdGEgPSB0cmFpbl9kYXRhX2dlbmVyYXRlZF9tdWx0aSwgZmFtaWx5ID0gYmlub21pYWwpCn0KIyBQcmV2aXNpb25lIHN1bCB0ZXN0IHNldApsb2dfcHJlZF9tdWx0aSA8LSBzYXBwbHkoY2xhc3NlcywgZnVuY3Rpb24oY2xzKSB7CiAgcHJlZGljdChsb2dfbW9kZWxzX211bHRpW1tjbHNdXSwgdGVzdF9kYXRhX2dlbmVyYXRlZF9tdWx0aSwgdHlwZSA9ICJyZXNwb25zZSIpCn0pCmxvZ19wcmVkX211bHRpX2xhYmVscyA8LSBhcHBseShsb2dfcHJlZF9tdWx0aSwgMSwgZnVuY3Rpb24ocHJvYnMpIHsKICBjbGFzc2VzW3doaWNoLm1heChwcm9icyldCn0pCiMgTWF0cmljZSBkaSBjb25mdXNpb25lIGUgYWNjdXJhY3kKbG9nX2NvbmZfbWF0cml4X211bHRpIDwtIGNvbmZ1c2lvbk1hdHJpeChhcy5mYWN0b3IobG9nX3ByZWRfbXVsdGlfbGFiZWxzKSwgdGVzdF9kYXRhX2dlbmVyYXRlZF9tdWx0aSRsYWJlbCkKcHJpbnQobG9nX2NvbmZfbWF0cml4X211bHRpKQpgYGAKQXBwbGljaGlhbW8gb3JhIHVuYSByZWdyZXNzaW9uZSBtdWx0aW5vbWlhbGUgdXNhbmRvIGlsIHBhY2NoZXR0byBgYGNhcmV0YGAuCgpgYGB7cn0KCiMgQWxsZW5hbWVudG8gZGVsIG1vZGVsbG8gZGkgcmVncmVzc2lvbmUgbG9naXN0aWNhIG11bHRpIGNsYXNzZQpsb2dfbW9kZWxfbXVsdGkgPC0gdHJhaW4obGFiZWwgfiAuLCBkYXRhID0gdHJhaW5fZGF0YV9nZW5lcmF0ZWRfbXVsdGksIHRyQ29udHJvbCA9IHRyYWluQ29udHJvbCh2ZXJib3NlSXRlciA9IEZBTFNFKSwgIHRyYWNlID0gRkFMU0UsIG1ldGhvZCA9ICJtdWx0aW5vbSIpCgojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0CmxvZ19wcmVkX211bHRpX2NhcmV0IDwtIHByZWRpY3QobG9nX21vZGVsX211bHRpLCB0ZXN0X2RhdGFfZ2VuZXJhdGVkX211bHRpKQojIE1hdHJpY2UgZGkgY29uZnVzaW9uZSBlIGFjY3VyYWN5CmxvZ19jb25mX21hdHJpeF9tdWx0aV9jYXJldCA8LSBjb25mdXNpb25NYXRyaXgobG9nX3ByZWRfbXVsdGlfY2FyZXQsIHRlc3RfZGF0YV9nZW5lcmF0ZWRfbXVsdGkkbGFiZWwpCnByaW50KGxvZ19jb25mX21hdHJpeF9tdWx0aV9jYXJldCkKCmBgYAoqKkVzZXJjaXppbzoqKiBBcHBsaWNhcmUgbGEgcmVncmVzc2lvbmUgbG9naXN0aWNhIGFsIGRhdGFzZXQgR2VybWFuIENyZWRpdCBEYXRhIGUgY29uZnJvbnRhcmUgbGUgcGVyZm9ybWFuY2UgY29uIE5haXZlIEJheWVzIGUgTERBIHZpc3RlIGluIHByZWNlZGVuemEuCgojIyBFc2VyY2l6aQoKMS4gR2VuZXJhcmUgdW5hIHRhYmVsbGEgY29uIDMwIHJpZ2hlIGUgOCBjb2xvbm5lIGNvbiBkYXRpIGNhc3VhbGkuIEFnZ2l1bmdlcmUgdW5hIHF1aW50YSBjb2xvbm5hIGNvbnRlbmVudGUgdW5hIGNsYXNzaWZpY2F6aW9uZSBiaW5hcmlhLCBnZW5lcmF0YSBhbmNoZSBlc3NhIGNhc3VhbG1lbnRlLiBDYWxjb2xhcmUgbGEgZGlzY3JlcGFuemEgdHJhIGxhIGNsYXNzaWZpY2F6aW9uZSBvcmlnaW5hcmlhIGUgaWwgcmlzdWx0YXRvIGRpIHVuYSBjbGFzc2lmaWNhemlvbmUgbG9naXN0aWNhLiBTZSBzaSByaXBldGUgcXVlc3RvIGVzcGVyaW1lbnRvIHBlciAxMDAwIHZvbHRlLCBjYWxjb2xhcmUgdmFsb3JlIG1lZGlvIGUgZGV2aWF6aW9uZSBzdGFuZGFyZCBkZWxsYSBkaXNjcmVwYW56YS4KCjIuIEdlbmVyYXJlIHVuYSB0YWJlbGxhIEEgY29uIDE3MCByaWdoZSBlIDcgY29sb25uZSwgaW4gbW9kbyBjaGUgbOKAmXVsdGltYSBjb2xvbm5hIGNvbnRlbmdhIHZhbG9yaSBiaW5hcmkgcmVsYXRpdmkgYWxs4oCZYXBwYXJ0ZW5lbnphIGEgdW5hIG8gbOKAmWFsdHJhIGRpIGR1ZSBjbGFzc2kuIEdlbmVyYXJlIHVuYSBzZWNvbmRhIHRhYmVsbGEgQiBjb24gNSByaWdoZSBlIDYgY29sb25uZS4gSW1wbGVtZW50YXJlIHVuYSBjbGFzc2lmaWNhemlvbmUgZGVnbGkgaW5kaXZpZHVpIG5lbGxhIHRhYmVsbGEgQiBhcHBsaWNhbmRvIGFsbGEgdGFiZWxsYSBBIGxhIGNsYXNzaWZpY2F6aW9uZSBsb2dpc3RpY2EgZSBsYSBhbmFsaXNpIGRpc2NyaW1pbmFudGUgbGluZWFyZS4gQ29uZnJvbnRhcmUgaSByaXN1bHRhdGkgZGVpIGR1ZSBtZXRvZGkuCgozLiBDb25mcm9udGFyZSBpIG1ldG9kaSBkaSByZWdyZXNzaW9uZSBsb2dpc3RpY2EgZSBhbmFsaXNpIGRpc2NyaW1pbmFudGUgbGluZWFyZSBlIHF1YWRyYXRpY2Egc3VsIGRhdGFzZXQgW3RpdGFuaWNdKGh0dHBzOi8vd3d3LmthZ2dsZS5jb20vZGF0YXNldHMveWFzc2VyaC90aXRhbmljLWRhdGFzZXQpIHVzYW5kbyBs4oCZYXV0b3ZhbGlkYXppb25lLCBwZXIgc3RhYmlsaXJlIGlsIG1ldG9kbyBtaWdsaW9yZS4KCgo0LiBEZXRlcm1pbmFyZSBpbCBtaWdsaW9yZSBtZXRvZG8gZGkgY2xhc3NpZmljYXppb25lICh0cmEgcXVlbGxpIHN0dWRpYXRpIG5lbCBjb3JzbykgcGVyIGlsIGRhdGFzZXQgYGBQaW1hLnRyYGAgKHBhY2NoZXR0byBNQVNTKS4gVXNhcmUgcG9pIGkgbW9kZWxsaSBwZXIgY2xhc3NpZmljYXJlIGkgbnVvdmkgZGF0aSBjb250ZW51dGkgbmVsIGRhdGFzZXQgYGBQaW1hLnRlYGAgZSB2ZXJpZmljYXJlIHNlIGlsIG1pZ2xpb3IgbW9kZWxsbyBzdGFiaWxpdG8gbmVsbGEgcHJpbWEgcGFydGUgc2lhIGVmZmV0dGl2YW1lbnRlIGlsIHBpw7kgZWZmaWNhY2UuCgoKIyMgTm90YSBzdWkgYmxvY2NoaQoKUG90ZXRlIGNyZWFyZSB1biBibG9jY28gaW5pemlhbGUgZSBub24gdmlzdWFsaXp6YXJlIGlsIGNvZGljZSBkaSAqdHV0dGkqIGkgYmxvY2NoaSBpbiB1biBSIG5vdGVib29rIHVzYW5kZSBpbCBjb21hbmRvOiBgYGtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSwgZWNobz1GQUxTRSlgYAo=