Introduzione

In questo notebook esploreremo diverse tecniche di regressione: \(k\)-NN per la regressione, regressione lineare semplice, regressione polinomiale e un esempio di regressione (apparentemente) non lineare. Utilizzeremo vari dataset per illustrare i concetti.

Carichiamo delle librerie che saranno utili.

library(caret) 
library(FNN) # pacchetto con knn per regressione (anche per classificazione)
library(ggplot2)
library(MASS)     # Per dataset reali

Dataset

Come al solito consideriamo tre datasets, uno generato e due reali (uno precaricato).

Dataset generato

Nel primo esempio generiamo un data frame con due colonne, legate da una relazione di associazione lineare cui aggiungiamo del rumore.

set.seed(42)

# scegliamo coefficiente angolare e intercetta
a = 3
b = 2
n <- 100
x <- rt(n, df=6)
y <- sin(x) + 0.1*rt(n, df=4)

df_generated <- data.frame(x, y)

# Visualizza il dataset generato
ggplot(df_generated, aes(x = x, y = y)) +
  geom_point() +
  ggtitle("Dataset Generato")

Dataset precaricato (Boston Housing)

Il dataset Boston dal pacchetto MASS riguarda i prezzi delle case in 506 quartieri di Boston e include varie caratteristiche delle abitazioni.


df_boston <- Boston

# Visualizza il dataset Boston
head(df_boston)

Selezioniamo solo alcune colonne per la visualizzazione (esplorate anche le altre features).


# Visualizza il dataset
ggplot(Boston, aes(x = lstat, y = medv, colour=rm)) +
  geom_point() +
  ggtitle("Boston Housing Dataset")

NA
NA

È già evidente una correlazione negativa tra lstat (stato della popolazione nel quartiere) e medv (valore mediano delle case occupate da proprietari).

Dataset Reale (Ricoveri Careggi 2012)

Usiamo i dati reali raccolti nel 2012 circa i ricoveri presso l’ospedale Careggi di Firenze scaricabili dal sito OpenToscano.

df_careggi <- read.csv("datasets/ricoverati-ammessi-dimessi-e-permanenza-in-reparti-ordinari-per-area-di-attivita.csv")

head(df_careggi)

#usiamo ggpairs per un grafico che combina nuvola di punti, densità stimata e correlogramma (in alternativa usare solo il comando plot)

library(GGally)
ggpairs(df_careggi[2:4])

NA
NA

Vediamo una perfetta correlazione tra Ammessi e Dimessi, mentre una correlazione positiva tra Ammessi (o Dimessi) e giorni accumulati di degenza presso il reparto.

KNN per la Regressione

Per la regressione usiamo inizialmente il modello \(k\)-NN che si basa sulla media dei fattori di uscita dei \(k\) punti più vicini a un punto test in termini di distanza euclidea delle caratteristiche di ingresso. Possiamo usare comandi da due pacchetti: knn.reg() da FNN (che funziona grossomodo come knn del pacchetto class) oppure train specificando il metodo knn e predict di caret.

Dataset generato

library(FNN)

# scegliamo intanto un valore di k a piacere

k <- 5

knn_generated <- knn.reg(train = as.matrix(df_generated$x), test = as.matrix(x), y = df_generated$y, k = k)

df_generated_pred <- data.frame(x = x, y = knn_generated$pred)

ggplot() +
  geom_point(data = df_generated, aes(x = x, y = y)) +
  geom_line(data = df_generated_pred, aes(x = x, y = y), colour='red')+
  ggtitle(paste("Regressione KNN sul dataset generato con k =", k))

Per l’allenamento del modello (ossia la scelta del parametro \(k\)) conviene usare il pacchetto caret.


# Suddivisione dei dati
train_index <- createDataPartition(df_generated$y, p = 0.7, list = FALSE)
train_set <- df_generated[train_index, ]
test_set <- df_generated[-train_index, ]

# Allenamento del modello KNN
knn_model <- train(y ~ x, data = train_set, method = "knn", tuneGrid = data.frame("k"= 1:50))
# per specificare i valori di k dare l'opzione tuneGrid=data.frame("k"=...)

plot(knn_model)

print(knn_model)
k-Nearest Neighbors 

72 samples
 1 predictor

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

  k   RMSE       Rsquared   MAE      
   1  0.2285392  0.8926993  0.1643142
   2  0.2186904  0.9005930  0.1597419
   3  0.2123933  0.9054767  0.1577372
   4  0.2076258  0.9098265  0.1553781
   5  0.1997857  0.9154713  0.1489045
   6  0.1995335  0.9147411  0.1473896
   7  0.1978503  0.9168041  0.1439567
   8  0.1983277  0.9161153  0.1443514
   9  0.2000995  0.9146540  0.1459419
  10  0.2010859  0.9141720  0.1477840
  11  0.2007175  0.9148232  0.1481636
  12  0.2025846  0.9150106  0.1506338
  13  0.2054951  0.9130907  0.1529180
  14  0.2070120  0.9132680  0.1560020
  15  0.2100132  0.9130388  0.1588261
  16  0.2116558  0.9133411  0.1606263
  17  0.2135414  0.9150390  0.1623269
  18  0.2169669  0.9150046  0.1662987
  19  0.2201531  0.9160524  0.1692551
  20  0.2232591  0.9159149  0.1728527
  21  0.2297069  0.9132365  0.1789611
  22  0.2331192  0.9136055  0.1824157
  23  0.2395994  0.9116681  0.1883441
  24  0.2440008  0.9105096  0.1932502
  25  0.2502260  0.9107947  0.2004753
  26  0.2580332  0.9102989  0.2081613
  27  0.2641159  0.9099707  0.2141989
  28  0.2718084  0.9094414  0.2215129
  29  0.2797407  0.9083466  0.2297738
  30  0.2876010  0.9066373  0.2371173
  31  0.2943189  0.9061321  0.2430919
  32  0.3024447  0.9051786  0.2503504
  33  0.3078908  0.9061798  0.2559810
  34  0.3150735  0.9066025  0.2628268
  35  0.3227413  0.9071477  0.2692529
  36  0.3317649  0.9083220  0.2775795
  37  0.3384199  0.9084589  0.2835297
  38  0.3487506  0.9057239  0.2924154
  39  0.3583677  0.9064073  0.3009588
  40  0.3660420  0.9067228  0.3087697
  41  0.3741855  0.9074475  0.3165264
  42  0.3825200  0.9076738  0.3245892
  43  0.3919679  0.9073862  0.3330232
  44  0.4014234  0.9081728  0.3421511
  45  0.4107612  0.9095466  0.3504502
  46  0.4187719  0.9135308  0.3571954
  47  0.4298985  0.9119670  0.3672567
  48  0.4388752  0.9107123  0.3740874
  49  0.4482458  0.9121328  0.3815309
  50  0.4581600  0.9116745  0.3899834

RMSE was used to select the optimal model using
 the smallest value.
The final value used for the model was k = 7.

Per la previsione usiamo la funzione predict specificando modello e test set.

# Previsione sul test set
knn_pred <- predict(knn_model, test_set)

# Calcolo dell'errore
knn_rmse <- sqrt(mean((knn_pred - test_set$y)^2))
print(paste("RMSE KNN:", knn_rmse))
[1] "RMSE KNN: 0.417918495369135"

# plot della previsione vs fattori di uscita effettivi

df_test_pred <- data.frame(x = test_set$x, y_true = test_set$y, y_pred = knn_pred)
ggplot(df_test_pred, aes(x = x)) +
  geom_point(aes(y = y_true), colour = "black", shape=1) +
  geom_point(aes(y = y_pred), colour = "red", shape=2) +
  ggtitle("Previsioni KNN vs Valori Reali sul Test Set") +
  ylab("Valore di uscita") +
  xlab("Caratteristica di ingresso")

Possiamo anche considerare altri indicatori di performance sul test set (confrontiamoli con quelli della cross validation usata per determinare \(k\)).


# calcola il MAE sul test set

knn_mae <- mean(abs(knn_pred - test_set$y))

# calcola il coefficiente di determinazione R^2 sul test set

ss_total <- sum((test_set$y - mean(test_set$y))^2)
ss_res <- sum((knn_pred - test_set$y)^2)
knn_r2 <- 1 - (ss_res / ss_total)

L`erore medio assoluto (MAE) vale 0.1923258 e il coefficiente di determinazione \(R^2\) vale 0.5849585 (calcolati sul test set).

Dataset Boston

Passiamo ora al dataset sulle case dei quartieri di Boston. Esso contiene molte caratteristiche, quindi possiamo valutare di effettuare una riduzione dimensionale (ad esempio tramite PCA). Ricordate anche che con i metodi basati sulla distanza è consigliato standardizzare le caratteristiche di input (non è necessario standardizzare quelle di output).

Usiamo la caratteristica medv (valore della casa mediano nel quartiere) come caratteristica di uscita.

# usiamo il pacchetto caret per knn sul dataset boston

# Suddivisione dei dati
set.seed(42)
train_index <- createDataPartition(df_boston$medv, p = 0.7, list = FALSE)
train_set <- df_boston[train_index, ]
test_set <- df_boston[-train_index, ]

# Allenamento del modello KNN specifichiamo di centrare e scalare i dati
knn_model_boston <- train(medv ~ ., data = train_set,   preProcess = c("center", "scale"), method = "knn", tuneGrid = data.frame("k"= 1:20))

plot(knn_model_boston)

print(knn_model_boston)
k-Nearest Neighbors 

356 samples
 13 predictor

Pre-processing: centered (13), scaled (13) 
Resampling: Bootstrapped (25 reps) 
Summary of sample sizes: 356, 356, 356, 356, 356, 356, ... 
Resampling results across tuning parameters:

  k   RMSE      Rsquared   MAE     
   1  5.286680  0.6936377  3.432798
   2  5.203928  0.6912242  3.388151
   3  5.119846  0.7014548  3.353115
   4  5.169694  0.6963904  3.352357
   5  5.210683  0.6921727  3.361788
   6  5.213923  0.6941756  3.358467
   7  5.182495  0.6997888  3.332981
   8  5.140886  0.7095845  3.320832
   9  5.195486  0.7045500  3.357256
  10  5.157155  0.7115381  3.346632
  11  5.172255  0.7122806  3.377432
  12  5.150771  0.7171045  3.375410
  13  5.174643  0.7159958  3.412493
  14  5.190267  0.7162546  3.424034
  15  5.227784  0.7129960  3.455417
  16  5.272501  0.7083041  3.490901
  17  5.312728  0.7042011  3.514802
  18  5.334650  0.7025041  3.534245
  19  5.373924  0.6991709  3.561547
  20  5.403465  0.6977176  3.572611

RMSE was used to select the optimal model using
 the smallest value.
The final value used for the model was k = 3.

Possiamo ora usare il modello per prevedere il valore sui quartieri di test.


# Previsione sul test set
knn_pred_boston <- predict(knn_model_boston, test_set)
# Calcolo dell'errore di test
knn_rmse_boston <- sqrt(mean((knn_pred_boston - test_set$medv)^2))
print(paste("RMSE KNN Boston:", knn_rmse_boston))
[1] "RMSE KNN Boston: 3.8008312930882"
# Coefficiente R^2 di test
ss_total_boston <- sum((test_set$medv - mean(test_set$medv))^2)
ss_res_boston <- sum((knn_pred_boston - test_set$medv)^2)
knn_r2_boston <- 1 - (ss_res_boston / ss_total_boston)
print(paste("R^2 KNN Boston:", knn_r2_boston))
[1] "R^2 KNN Boston: 0.815582465902293"

Esercizio: ripetere l’analisi selezionando solamente alcune caratteristiche del dataset. Come cambia il RMSE? come cambia il coefficiente di determinazione \(R^2\)? Come cambia la performance del metodo senza standardizzare i dati?

Confrontiamo l’errore di training con l’errore di test al variare di \(k\).

# calcola train e test error al variare di k
train_error_boston <- numeric(20)
for (k in 1:20){
  # calcola le previsioni sul train set
  knn_pred_train <- predict(train(medv ~ ., data = train_set,   preProcess = c("center", "scale"), method = "knn", tuneGrid = data.frame("k"= k)), train_set)
  # calcola il RMSE
  train_error_boston[k] <- sqrt(mean((knn_pred_train - train_set$medv)^2))
}

# plot dei risultati della cross-validation
df_error_boston <- data.frame(k = 1:20, train_error = train_error_boston, test_error = knn_model_boston$results$RMSE)
ggplot(df_error_boston, aes(x = k)) +
  geom_line(aes(y = train_error, colour = "Training Error")) +
  geom_point(aes(y = train_error, colour = "Training Error"), shape=1) +
  geom_line(aes(y = test_error, colour = "Test Error")) +
  geom_point(aes(y = test_error, colour = "Test Error"), shape=1) +
  ylab("RMSE") +
  ggtitle("Training e Test Error al variare di k (Boston Housing)") +
  scale_colour_manual("", 
                      breaks = c("Training Error", "Test Error"),
                      values = c("Training Error"="violet", "Test Error"="blue"))+
  theme_minimal()

Dataset Careggi

Consideriamo infine il dataset dei ricoveri al Careggi. L’obiettivo della regressione è prevedere il numero di Giorni Accumulati in funzione del numero di Ammessi (o Dimessi).

# Suddivisione dei dati
set.seed(42)
train_index <- createDataPartition(df_careggi$GiorniAccumulati, p = 0.7, list = FALSE)
train_set <- df_careggi[train_index, ]
test_set <- df_careggi[-train_index, ]

# Allenamento del modello KNN
knn_model_careggi <- train(GiorniAccumulati ~ Ammessi, data = train_set, method = "knn", tuneGrid = data.frame("k"= 1:40))
plot(knn_model_careggi)

print(knn_model_careggi)
k-Nearest Neighbors 

51 samples
 1 predictor

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

  k   RMSE      Rsquared   MAE     
   1  4312.127  0.2244879  3235.359
   2  3852.788  0.2679383  2870.393
   3  3751.619  0.2902639  2754.002
   4  3564.636  0.3179102  2643.992
   5  3495.508  0.3222912  2580.224
   6  3391.071  0.3391636  2520.578
   7  3318.963  0.3483867  2467.923
   8  3325.561  0.3417332  2467.559
   9  3312.029  0.3372959  2461.531
  10  3265.029  0.3526664  2426.125
  11  3226.596  0.3582410  2410.690
  12  3217.623  0.3646161  2412.532
  13  3182.658  0.3751188  2397.457
  14  3203.922  0.3654594  2412.722
  15  3212.363  0.3637422  2412.042
  16  3198.851  0.3657141  2402.494
  17  3187.655  0.3697047  2392.078
  18  3181.200  0.3756738  2392.754
  19  3194.256  0.3726998  2390.529
  20  3194.230  0.3793524  2385.257
  21  3205.937  0.3777413  2396.998
  22  3219.338  0.3754725  2401.059
  23  3238.105  0.3723319  2412.547
  24  3249.707  0.3723834  2414.864
  25  3260.388  0.3659392  2421.295
  26  3281.801  0.3644368  2439.896
  27  3310.523  0.3432603  2450.157
  28  3318.563  0.3459337  2449.805
  29  3327.317  0.3406555  2456.821
  30  3337.274  0.3414789  2469.056
  31  3351.196  0.3378359  2475.937
  32  3373.304  0.3348179  2498.442
  33  3375.098  0.3378106  2495.380
  34  3389.458  0.3301105  2512.359
  35  3410.479  0.3210328  2525.236
  36  3436.087  0.3091044  2544.050
  37  3468.837  0.2984539  2578.627
  38  3499.223  0.2832781  2609.325
  39  3523.468  0.2810815  2646.532
  40  3542.763  0.2869567  2671.431

RMSE was used to select the optimal model using
 the smallest value.
The final value used for the model was k = 18.

Il modello con \(k=\) rknn_model_careggi$bestTune$k minimizza l’errore di cross-validation. Tuttavia il coefficiente \(R^2=\) 0.3756738 indica che il modello spiega solo una piccola parte della varianza.

Regressione Lineare

Passiamo ora alla regressione lineare semplice (una variabile di input). Il comando di base è lm(), ma anche caret può essere usato per l’allenamento del modello.

Dataset generato

Per il dataset generato possiamo aspettarci un’ottima aderenza al modello sottostante.

# divisione train e test set
train_index <- createDataPartition(df_generated$y, p = 0.7, list = FALSE)
train_set <- df_generated[train_index, ]
test_set <- df_generated[-train_index, ]

# Allenamento del modello di regressione lineare semplice
lm_model_generated <- lm(y ~ ., data = train_set)

summary(lm_model_generated)

Call:
lm(formula = y ~ ., data = train_set)

Residuals:
     Min       1Q   Median       3Q      Max 
-2.86328 -0.24552 -0.04007  0.33662  1.12190 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) -0.04895    0.05818  -0.841    0.403    
x            0.41069    0.05225   7.860 3.31e-11 ***
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.4931 on 70 degrees of freedom
Multiple R-squared:  0.4688,    Adjusted R-squared:  0.4612 
F-statistic: 61.78 on 1 and 70 DF,  p-value: 3.307e-11

Dalla teoria sappiamo che il coefficiente angolare è proporzionale alla correlazione. Verifichiamolo numericamente.


lambda <- cor(train_set$y, train_set$x)*sd(train_set$y)/sd(train_set$x)


print(paste("Coefficiente angolare stimato:", coef(lm_model_generated)[2]))
[1] "Coefficiente angolare stimato: 0.41068744537476"
print(paste("Coefficiente angolare teorico:", lambda))
[1] "Coefficiente angolare teorico: 0.410687445374759"

Possiamo effettuare ora una previsione sul test set e calcolare l’errore (RMSE).


# Previsione sul test set
lm_pred_generated <- predict(lm_model_generated, test_set)


# Calcolo dell'errore
lm_rmse_generated <- sqrt(mean((lm_pred_generated - test_set$y)^2))
print(paste("RMSE Regressione Lineare (generato):", lm_rmse_generated))
[1] "RMSE Regressione Lineare (generato): 0.309452490992269"

Visualizziamo anche la retta di regressione.

ggplot(df_generated, aes(x = x, y = y)) +
  geom_point() +
geom_abline(slope=lm_model_generated$coefficients[2], intercept=lm_model_generated$coefficients[1], col='red') +  ggtitle("Regressione Lineare Semplice sul Dataset Generato")

Come possiamo aggiungere dell’informazione riguardo all’incertezza della previsione? Vedremo la teoria nella prossima lezione, per il momento usiamo il comando predict con l’opzione interval="prediction".

# Intervalli di previsione
lm_pred_conf <- predict(lm_model_generated, test_set, interval="prediction", level=0.95)

# Aggiungi delle barre di previsione al plot
df_test_pred_conf <- data.frame(x = test_set$x, y_true = test_set$y, y_pred = lm_pred_conf[,1], lwr = lm_pred_conf[,2], upr = lm_pred_conf[,3])
ggplot(df_test_pred_conf, aes(x = x)) +
  geom_point(aes(y = y_true), colour = "blue", shape=1) +
  geom_line(aes(y = y_pred), colour = "red") +
  geom_ribbon(aes(ymin = lwr, ymax = upr), alpha = 0.2) +
  ggtitle("Regressione Lineare con Intervalli di previsione") +
  ylab("Valore di uscita") +
  xlab("Caratteristica di ingresso")

Dataset Boston housing

Consideriamo il dataset Boston Housing e la relazione tra lstat (percentuale della popolazione a basso reddito) e medv (valore mediano delle case occupate da proprietari). Usiamo stavolta il pacchetto caret.

# Allenamento del modello di regressione lineare semplice
set.seed(42)
train_index <- createDataPartition(Boston$medv, p = 0.7, list = FALSE)
train_set <- Boston[train_index, ]
test_set <- Boston[-train_index, ]

# usiamo caret
lm_model_boston <- train(medv ~ lstat, data = train_set, method = "lm")

print(lm_model_boston)
Linear Regression 

356 samples
  1 predictor

No pre-processing
Resampling: Bootstrapped (25 reps) 
Summary of sample sizes: 356, 356, 356, 356, 356, 356, ... 
Resampling results:

  RMSE      Rsquared   MAE     
  6.492122  0.5251329  4.840703

Tuning parameter 'intercept' was held constant at
 a value of TRUE

Confrontiamo i parametri trovati con i due metodi.


summary(lm(medv ~ lstat, data = train_set))

Call:
lm(formula = medv ~ lstat, data = train_set)

Residuals:
    Min      1Q  Median      3Q     Max 
-15.293  -4.114  -1.476   2.286  24.351 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) 34.56528    0.69568   49.69   <2e-16 ***
lstat       -0.93555    0.04758  -19.66   <2e-16 ***
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 6.464 on 354 degrees of freedom
Multiple R-squared:  0.522, Adjusted R-squared:  0.5207 
F-statistic: 386.7 on 1 and 354 DF,  p-value: < 2.2e-16
lm_model_boston$finalModel

Call:
lm(formula = .outcome ~ ., data = dat)

Coefficients:
(Intercept)        lstat  
    34.5653      -0.9356  

Notiamo che il coefficiente \(R^2\) è peggiore di quello trovato con \(k\)-NN (questo è dovuto al bias del modello lineare oltre al fatto che stiamo usando una sola caratteristica: provare ad applicare \(k\)-NN con il solo fattore di ingresso lstat). Confrontiamo quindi l’errore di train con l’errore di test.

# calcolar RMSE e R**2 sul test set
train_pred_boston <- predict(lm_model_boston, train_set)
train_rmse_boston <- sqrt(mean((train_pred_boston - train_set$medv)^2))
ss_total_train_boston <- sum((train_set$medv - mean(train_set$medv))^2)
ss_res_train_boston <- sum((train_pred_boston - train_set$medv)^2)
train_r2_boston <- 1 - (ss_res_train_boston / ss_total_train_boston)
test_pred_boston <- predict(lm_model_boston, test_set)
test_rmse_boston <- sqrt(mean((test_pred_boston - test_set$medv)^2))
ss_total_test_boston <- sum((test_set$medv - mean(test_set$medv))^2)
ss_res_test_boston <- sum((test_pred_boston - test_set$medv)^2)
test_r2_boston <- 1 - (ss_res_test_boston / ss_total_test_boston)
print(paste("RMSE Train Boston:", train_rmse_boston))
[1] "RMSE Train Boston: 6.44581268369236"
print(paste("R^2 Train Boston:", train_r2_boston))
[1] "R^2 Train Boston: 0.522041789419562"
print(paste("RMSE Test Boston:", test_rmse_boston))
[1] "RMSE Test Boston: 5.60103528132736"
print(paste("R^2 Test Boston:", test_r2_boston))
[1] "R^2 Test Boston: 0.599519254079983"

Procediamo comunque con la previsione sul test set e plottiamo la retta di regressione.

# Previsione sul test set
lm_pred <- predict(lm_model_boston, test_set)

# Calcolo dell'errore
lm_rmse <- sqrt(mean((lm_pred - test_set$medv)^2))
print(paste("RMSE Regressione Lineare:", lm_rmse))
[1] "RMSE Regressione Lineare: 5.60103528132736"
# Visualizza la regressione
ggplot(Boston, aes(x = lstat, y = medv)) +
  geom_point() +
  geom_abline(slope=lm_model_boston$finalModel$coefficients[2], intercept = lm_model_boston$finalModel$coefficients[1], col="blue")+
  ggtitle("Regressione Lineare Semplice")

Aggiungiamo l’intervallo di previsione (confrontare con intervallo di confidenza).


lm_model_boston = lm(medv ~ lstat, data = train_set)

# Intervalli di previsione
lm_pred_conf_boston <- predict(lm_model_boston, test_set, interval="prediction", level=0.95)
# Aggiungi delle barre di previsione al plot
df_test_pred_conf_boston <- data.frame(x = test_set$lstat, y_true = test_set$medv, y_pred = lm_pred_conf_boston[,1], lwr = lm_pred_conf_boston[,2], upr = lm_pred_conf_boston[,3])
ggplot(df_test_pred_conf_boston, aes(x = x)) +
  geom_point(aes(y = y_true), colour = "blue", shape=1) +
  geom_line(aes(y = y_pred), colour = "red") +
  geom_ribbon(aes(ymin = lwr, ymax = upr), alpha = 0.2) +
  ggtitle("Regressione Lineare Boston con Intervalli di previsione") +
  ylab("Valore di uscita") +
  xlab("Caratteristica di ingresso")

Regressione polinomiale

Proviamo ad aumentare la complessità del modello mantenendo una singola caratteristica (lstat) ma usando una funzione polinomiale. Consideriamo per confronto il dataset generato (per cui non dovrebbe essere necessiario).

# Allenamento del modello di regressione polinomiale con grado 2
poly_model_generated <- lm(y ~ x + I(x^2), data = df_generated)
summary(poly_model_generated)

Call:
lm(formula = y ~ x + I(x^2), data = df_generated)

Residuals:
     Min       1Q   Median       3Q      Max 
-1.78027 -0.26017 -0.03059  0.26429  1.80353 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept)  0.06442    0.04705   1.369    0.174    
x            0.46085    0.03653  12.617  < 2e-16 ***
I(x^2)      -0.07120    0.01689  -4.214 5.62e-05 ***
---
Signif. codes:  
0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.4134 on 97 degrees of freedom
Multiple R-squared:  0.6261,    Adjusted R-squared:  0.6184 
F-statistic: 81.21 on 2 and 97 DF,  p-value: < 2.2e-16

Una alternativa tecnicamente migliore è di usare il comando poly() specificando il grado del modello polinomiale. Attenzione però che i coefficienti non sono direttamente quelli del polinomio naturale (il comando usa combinazioni lineari dei polinomi per migliorare la precisione).

poly_model_generated <- lm(y ~ poly(x, degree =10), data = df_generated)
summary(poly_model_generated)

Call:
lm(formula = y ~ poly(x, degree = 10), data = df_generated)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.32774 -0.08232 -0.01211  0.07392  0.54405 

Coefficients:
                       Estimate Std. Error t value Pr(>|t|)    
(Intercept)            -0.02860    0.01366  -2.095   0.0391 *  
poly(x, degree = 10)1   4.97241    0.13656  36.411  < 2e-16 ***
poly(x, degree = 10)2  -1.74226    0.13656 -12.758  < 2e-16 ***
poly(x, degree = 10)3  -3.68979    0.13656 -27.019  < 2e-16 ***
poly(x, degree = 10)4   0.78815    0.13656   5.771 1.13e-07 ***
poly(x, degree = 10)5   0.73409    0.13656   5.375 6.08e-07 ***
poly(x, degree = 10)6  -0.06162    0.13656  -0.451   0.6529    
poly(x, degree = 10)7  -0.02097    0.13656  -0.154   0.8783    
poly(x, degree = 10)8   0.21391    0.13656   1.566   0.1208    
poly(x, degree = 10)9  -0.07845    0.13656  -0.574   0.5671    
poly(x, degree = 10)10  0.29613    0.13656   2.168   0.0328 *  
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.1366 on 89 degrees of freedom
Multiple R-squared:  0.9626,    Adjusted R-squared:  0.9584 
F-statistic: 228.8 on 10 and 89 DF,  p-value: < 2.2e-16

Vediamo che in entrambi i casi il coefficiente del termine di grado \(0\) non è significativo (quindi può essere rimosso). Vedremo meglio la teoria di questo test la prossima lezione. Per il momento applichiamo la stessa strategia al datset Boston.

# Allenamento del modello di regressione polinomiale con grado 2
poly_model <- lm(medv ~ poly(lstat, degree = 10), data = train_set)

summary(poly_model)

Call:
lm(formula = medv ~ poly(lstat, degree = 10), data = train_set)

Residuals:
     Min       1Q   Median       3Q      Max 
-14.7454  -3.2492  -0.8553   2.1386  26.1995 

Coefficients:
                            Estimate Std. Error t value Pr(>|t|)    
(Intercept)                  22.6596     0.2851  79.469  < 2e-16 ***
poly(lstat, degree = 10)1  -127.1043     5.3800 -23.625  < 2e-16 ***
poly(lstat, degree = 10)2    58.2666     5.3800  10.830  < 2e-16 ***
poly(lstat, degree = 10)3   -24.0367     5.3800  -4.468 1.07e-05 ***
poly(lstat, degree = 10)4    18.4519     5.3800   3.430 0.000677 ***
poly(lstat, degree = 10)5   -17.1279     5.3800  -3.184 0.001587 ** 
poly(lstat, degree = 10)6     5.1373     5.3800   0.955 0.340296    
poly(lstat, degree = 10)7     4.4559     5.3800   0.828 0.408106    
poly(lstat, degree = 10)8    -4.2425     5.3800  -0.789 0.430908    
poly(lstat, degree = 10)9     8.8995     5.3800   1.654 0.098999 .  
poly(lstat, degree = 10)10   -7.4488     5.3800  -1.385 0.167085    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 5.38 on 345 degrees of freedom
Multiple R-squared:  0.6773,    Adjusted R-squared:  0.668 
F-statistic: 72.42 on 10 and 345 DF,  p-value: < 2.2e-16

Vediamo che il coefficiente \(R^2\) è migliorato (ma attenzione all’overfitting).

# Previsione sul test set
poly_pred <- predict(poly_model, test_set)

# Calcolo dell'errore
poly_rmse <- sqrt(mean((poly_pred - test_set$medv)^2))
print(paste("RMSE Regressione Polinomiale:", poly_rmse))
[1] "RMSE Regressione Polinomiale: 4.80813588113572"
# Visualizza la regressione polinomiale
ggplot(df_boston, aes(x = lstat, y = medv)) +
  geom_point() +
  geom_line(data=test_set, aes(x = lstat, y = predict(poly_model, newdata = test_set), col="red" ))+
 # geom_smooth(method = "lm", formula = y ~ poly(x, 2), col = "red") +
  ggtitle("Regressione Polinomiale")

Studiamo al variare del grado l’errore di training (usiamo qui \(R^2\) e cerchiamo un punto di gomito).

set.seed(42)

train_r2 <- numeric(10)

for (grado in 1:10){
  # allenamento del modello polinomiale usando lm()
  poly_model_cv <- glm(medv ~ poly(lstat, degree =  grado ), data = train_set)
  
  # calcolo R^2 di train
  train_pred <- predict(poly_model_cv, train_set)
  ss_total_train <- sum((train_set$medv - mean(train_set$medv))^2)
  ss_res_train <- sum((train_pred - train_set$medv)^2)
  train_r2[grado] <- 1 - (ss_res_train / ss_total_train)
}

# plot
df_r2 <- data.frame(grado = 1:10, train_r2 = train_r2)
ggplot(df_r2, aes(x = grado, y = train_r2)) +
  geom_line() +
  geom_point() +
  ylab("R^2 di Train") +
  xlab("Grado del Polinomio") +
  ggtitle("R^2 di Train al variare del grado del polinomio")

Regressione esponenziale

Possiamo usare i modelli lineari anche per dipendenze più complesse, ad esempio possiamo cercare una relazione del tipo \(y \approx exp(ax+b)\): basta infatti passare al logaritmo e diventa una regressione lineare semplice \(\log(y) \approx ax+b\).

# Allenamento del modello di regressione esponenziale
There were 50 or more warnings (use warnings() to see the first 50)
exp_model <- lm(log(medv) ~ lstat, data = train_set)

summary(exp_model)

Call:
lm(formula = log(medv) ~ lstat, data = train_set)

Residuals:
     Min       1Q   Median       3Q      Max 
-0.97429 -0.15022 -0.03139  0.12516  0.87385 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)  3.605393   0.027247  132.32   <2e-16 ***
lstat       -0.044459   0.001863  -23.86   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.2532 on 354 degrees of freedom
Multiple R-squared:  0.6166,    Adjusted R-squared:  0.6155 
F-statistic: 569.2 on 1 and 354 DF,  p-value: < 2.2e-16
# Previsione sul test set
exp_pred_log <- predict(exp_model, test_set)
exp_pred <- exp(exp_pred_log)
# Calcolo dell'errore
exp_rmse <- sqrt(mean((exp_pred - test_set$medv)^2))
print(paste("RMSE Regressione Esponenziale:", exp_rmse))
[1] "RMSE Regressione Esponenziale: 5.27754108639585"
# Visualizza la regressione esponenziale
ggplot() +
  geom_point(data = test_set, aes(x = lstat, y = medv), color = "blue") +
  geom_line(data = test_set, aes(x = lstat, y = exp(predict(exp_model, newdata = test_set))), color = "red") +
  labs(title = "Regressione Esponenziale", x = "lstat", y = "medv") +
  theme_minimal()

Dataset Careggi

Confrontiamo infine la performance di una regressione lineare semplice, polinomiale e infine esponenziale sul dataset dell’ospedale Careggi.

# regressione lineare

set.seed(42)
train_index <- createDataPartition(df_careggi$GiorniAccumulati, p = 0.8, list = FALSE)
train_set <- df_careggi[train_index, ]
test_set <- df_careggi[-train_index, ]


linear_model_careggi <- lm(GiorniAccumulati ~ Ammessi, data = train_set)
  
summary(linear_model_careggi)

Call:
lm(formula = GiorniAccumulati ~ Ammessi, data = train_set)

Residuals:
    Min      1Q  Median      3Q     Max 
-5895.3 -1617.4  -703.6  1387.1 13823.8 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) 1190.8305   566.3918   2.102   0.0399 *  
Ammessi        3.7817     0.3837   9.857 6.36e-14 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3119 on 57 degrees of freedom
Multiple R-squared:  0.6303,    Adjusted R-squared:  0.6238 
F-statistic: 97.16 on 1 and 57 DF,  p-value: 6.359e-14
linear_pred_careggi <- predict(linear_model_careggi, test_set)
linear_rmse_values <- sqrt(mean((poly_pred_careggi - test_set$GiorniAccumulati)^2))

Consideriamo ora una regressione quadratica (polinomiale di grado \(2\)).


poly_model_careggi <- lm(GiorniAccumulati ~ poly(Ammessi, degree = 2), data = train_set)
summary(poly_model_careggi)

Call:
lm(formula = GiorniAccumulati ~ poly(Ammessi, degree = 2), data = train_set)

Residuals:
    Min      1Q  Median      3Q     Max 
-6132.5 -1652.1  -464.4  1283.0 13487.4 

Coefficients:
                           Estimate Std. Error t value Pr(>|t|)    
(Intercept)                    5083        408  12.459  < 2e-16 ***
poly(Ammessi, degree = 2)1    30744       3134   9.811 9.08e-14 ***
poly(Ammessi, degree = 2)2    -2151       3134  -0.686    0.495    
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 3134 on 56 degrees of freedom
Multiple R-squared:  0.6333,    Adjusted R-squared:  0.6202 
F-statistic: 48.36 on 2 and 56 DF,  p-value: 6.301e-13
poly_pred_careggi <- predict(poly_model_careggi, test_set)
poly_rmse_values <- sqrt(mean((poly_pred_careggi - test_set$GiorniAccumulati)^2))

Vediamo che il termine di secondo grado non è significativo. Possiamo limitarci al caso lineare. Consideriamo infine una relazione del tipo \(Giorni \approx Visite ^\alpha\), dove \(\alpha\) è da determinare. Per questo possiamo passare al logaritmo ambo i membri e diventa di nuovo una regressione lineare semplice.

log_model_careggi <- lm(log(GiorniAccumulati) ~ log(Ammessi), data = train_set)
summary(log_model_careggi)

Call:
lm(formula = log(GiorniAccumulati) ~ log(Ammessi), data = train_set)

Residuals:
     Min       1Q   Median       3Q      Max 
-2.03909 -0.44110  0.00677  0.48194  1.88021 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept)    1.5541     0.5340    2.91  0.00515 ** 
log(Ammessi)   0.9937     0.0822   12.09  < 2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 0.825 on 57 degrees of freedom
Multiple R-squared:  0.7194,    Adjusted R-squared:  0.7145 
F-statistic: 146.1 on 1 and 57 DF,  p-value: < 2.2e-16
log_pred_careggi_log <- predict(log_model_careggi, test_set)
log_pred_careggi <- exp(log_pred_careggi_log)
log_rmse_values <- sqrt(mean((log_pred_careggi - test_set$GiorniAccumulati)^2))

Il coefficiente del logaritmo è \(0.99\), quindi l’ipotesi di relazione lineare è ulteriormente confermata.

Confrontiamo infine i RMSE.

print(paste("RMSE Regressione Lineare (Careggi):", linear_rmse_values))
[1] "RMSE Regressione Lineare (Careggi): 3756.44220814634"
print(paste("RMSE Regressione Polinomiale (Careggi):", poly_rmse_values)) 
[1] "RMSE Regressione Polinomiale (Careggi): 3756.44220814634"
print(paste("RMSE Regressione Esponenziale (Careggi):", log_rmse_values)) 
[1] "RMSE Regressione Esponenziale (Careggi): 3579.85710029027"

Plottiamo i tre modelli.


ggplot() +
  geom_point(data = df_careggi, aes(x = Ammessi, y = GiorniAccumulati), color = "blue") +
  geom_smooth(data = train_set, aes(x = Ammessi, y = GiorniAccumulati), method = "lm", formula = y ~ x, color = "red", se = FALSE) +
  geom_smooth(data = train_set, aes(x = Ammessi, y = GiorniAccumulati), method = "lm", formula = y ~ poly(x, 2), color = "green", se = FALSE) +
  geom_line(data = test_set, aes(x = Ammessi, y = exp(predict(log_model_careggi, newdata = test_set))), color = "purple") +
  labs(title = "Confronto Modelli di Regressione (Careggi)", x = "Ammessi", y = "Giorni Accumulati") +
  theme_minimal() +
  scale_color_manual(name = "Modello", values = c("Lineare" = "red", "Polinomiale" = "green", "Esponenziale" = "purple"))

Esercizi

  1. Utilizza il dataset mtcars per prevedere il consumo di carburante (mpg) in base al peso dell’auto (wt). Valuta le performance del modello \(k\)-NN al variare del valore di \(k\).

  2. Utilizza il dataset iris per prevedere la lunghezza del petalo (Petal.Length) in base alla lunghezza del sepalo (Sepal.Length). Calcola e interpreta il coefficiente di determinazione \(R^2\).

  3. Genera un dataset con una relazione quadratica (ad esempio, \(y = x^2 + \text{rumore}\)). Applica una regressione polinomiale di secondo grado e confronta il risultato con una regressione lineare semplice.

  4. Crea un dataset in cui la variabile dipendente cresce esponenzialmente rispetto a una variabile indipendente. Applica una regressione esponenziale e confronta il RMSE con quello di una regressione lineare.

  5. Utilizza il dataset Iris per prevedere la lunghezza del petalo come funzione della lunghezza del sepalo elevata ad un esponente \(\alpha\) da determinare tramite regressione lineare.

  6. Utilizza il dataset airquality per prevedere la temperatura (Temp) in base all’ozono (Ozone). Sperimenta con KNN e regressione lineare semplice e confronta gli errori di previsione.

  7. Per un modello KNN costruito con un dataset generato, calcola l’errore medio assoluto (MAE) e il root mean squared error (RMSE) e discuti le loro implicazioni.

  8. Utilizza il dataset diamonds per prevedere il prezzo (price) in base alle caratteristiche del diamante (carat, cut, color). Prova a usare KNN e regressione polinomiale e discuti come la scelta delle caratteristiche influisce sulle performance.

  9. Costruisci un modello di regressione lineare semplice utilizzando il dataset ChickWeight per prevedere il peso (weight) in base all’età (Time). Visualizza i risultati e gli intervalli di previsione.

LS0tCnRpdGxlOiAiUmVncmVzc2lvbmUgSSAobm90ZWJvb2sgNikiCmF1dGhvcjogIkRhcmlvIFRyZXZpc2FuIgpkYXRlOiAiMjkvMTAvMjAyNSIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogJzMnCiAgICBkZl9wcmludDogcGFnZWQKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgdGhlbWU6IHJlYWRhYmxlCiAgICBkZl9wcmludDogcGFnZWQKICAgIGRvd25sb2FkX2hhbmRsZXI6IHRydWUKc3VidGl0bGU6ICJTdGF0aXN0aWNhIElJIC0gNzUwQUEiCi0tLQoKCgoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CiNrbml0cjo6b3B0c19jaHVuayRzZXQod2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UsIGVjaG89RkFMU0UpIApgYGAKCgojIEludHJvZHV6aW9uZQoKSW4gcXVlc3RvIG5vdGVib29rIGVzcGxvcmVyZW1vIGRpdmVyc2UgdGVjbmljaGUgZGkgcmVncmVzc2lvbmU6ICRrJC1OTiBwZXIgbGEgcmVncmVzc2lvbmUsIHJlZ3Jlc3Npb25lIGxpbmVhcmUgc2VtcGxpY2UsIHJlZ3Jlc3Npb25lIHBvbGlub21pYWxlIGUgdW4gZXNlbXBpbyBkaSByZWdyZXNzaW9uZSAoYXBwYXJlbnRlbWVudGUpIG5vbiBsaW5lYXJlLiBVdGlsaXp6ZXJlbW8gdmFyaSBkYXRhc2V0IHBlciBpbGx1c3RyYXJlIGkgY29uY2V0dGkuCgpDYXJpY2hpYW1vIGRlbGxlIGxpYnJlcmllIGNoZSBzYXJhbm5vIHV0aWxpLgoKYGBge3J9CmxpYnJhcnkoY2FyZXQpIApsaWJyYXJ5KEZOTikgIyBwYWNjaGV0dG8gY29uIGtubiBwZXIgcmVncmVzc2lvbmUgKGFuY2hlIHBlciBjbGFzc2lmaWNhemlvbmUpCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShNQVNTKSAgICAgIyBQZXIgZGF0YXNldCByZWFsaQpgYGAKCiMgRGF0YXNldAoKQ29tZSBhbCBzb2xpdG8gY29uc2lkZXJpYW1vIHRyZSBkYXRhc2V0cywgdW5vIGdlbmVyYXRvIGUgZHVlIHJlYWxpICh1bm8gcHJlY2FyaWNhdG8pLiAKCiMjIERhdGFzZXQgZ2VuZXJhdG8KCk5lbCBwcmltbyBlc2VtcGlvIGdlbmVyaWFtbyB1biBkYXRhIGZyYW1lIGNvbiBkdWUgY29sb25uZSwgbGVnYXRlIGRhIHVuYSByZWxhemlvbmUgZGkgYXNzb2NpYXppb25lIGxpbmVhcmUgY3VpIGFnZ2l1bmdpYW1vIGRlbCBydW1vcmUuCgpgYGB7cn0Kc2V0LnNlZWQoNDIpCgojIHNjZWdsaWFtbyBjb2VmZmljaWVudGUgYW5nb2xhcmUgZSBpbnRlcmNldHRhCmEgPSAzCmIgPSAyCm4gPC0gMTAwCnggPC0gcnQobiwgZGY9NikKeSA8LSBzaW4oeCkgKyAwLjEqcnQobiwgZGY9NCkKCmRmX2dlbmVyYXRlZCA8LSBkYXRhLmZyYW1lKHgsIHkpCgojIFZpc3VhbGl6emEgaWwgZGF0YXNldCBnZW5lcmF0bwpnZ3Bsb3QoZGZfZ2VuZXJhdGVkLCBhZXMoeCA9IHgsIHkgPSB5KSkgKwogIGdlb21fcG9pbnQoKSArCiAgZ2d0aXRsZSgiRGF0YXNldCBHZW5lcmF0byIpCmBgYAoKIyMgRGF0YXNldCBwcmVjYXJpY2F0byAoQm9zdG9uIEhvdXNpbmcpCgpJbCBkYXRhc2V0IEJvc3RvbiBkYWwgcGFjY2hldHRvIGBgTUFTU2BgIHJpZ3VhcmRhIGkgcHJlenppIGRlbGxlIGNhc2UgaW4gNTA2IHF1YXJ0aWVyaSBkaSBCb3N0b24gZSBpbmNsdWRlIHZhcmllIGNhcmF0dGVyaXN0aWNoZSBkZWxsZSBhYml0YXppb25pLgoKYGBge3J9CgpkZl9ib3N0b24gPC0gQm9zdG9uCgojIFZpc3VhbGl6emEgaWwgZGF0YXNldCBCb3N0b24KaGVhZChkZl9ib3N0b24pCmBgYAoKClNlbGV6aW9uaWFtbyBzb2xvIGFsY3VuZSBjb2xvbm5lIHBlciBsYSB2aXN1YWxpenphemlvbmUgKGVzcGxvcmF0ZSBhbmNoZSBsZSBhbHRyZSBmZWF0dXJlcykuCgpgYGB7cn0KCiMgVmlzdWFsaXp6YSBpbCBkYXRhc2V0CmdncGxvdChCb3N0b24sIGFlcyh4ID0gbHN0YXQsIHkgPSBtZWR2LCBjb2xvdXI9cm0pKSArCiAgZ2VvbV9wb2ludCgpICsKICBnZ3RpdGxlKCJCb3N0b24gSG91c2luZyBEYXRhc2V0IikKCgpgYGAKCsOIIGdpw6AgZXZpZGVudGUgdW5hIGNvcnJlbGF6aW9uZSBuZWdhdGl2YSB0cmEgYGxzdGF0YCAoc3RhdG8gZGVsbGEgcG9wb2xhemlvbmUgbmVsIHF1YXJ0aWVyZSkgZSBgbWVkdmAgKHZhbG9yZSBtZWRpYW5vIGRlbGxlIGNhc2Ugb2NjdXBhdGUgZGEgcHJvcHJpZXRhcmkpLgoKIyMgRGF0YXNldCBSZWFsZSAoUmljb3ZlcmkgQ2FyZWdnaSAyMDEyKQoKVXNpYW1vIGkgZGF0aSByZWFsaSByYWNjb2x0aSBuZWwgMjAxMiBjaXJjYSBpIHJpY292ZXJpIHByZXNzbyBsJ29zcGVkYWxlIENhcmVnZ2kgZGkgRmlyZW56ZSBzY2FyaWNhYmlsaSBkYWwgc2l0byBbT3BlblRvc2Nhbm9dKGh0dHBzOi8vZGF0aS50b3NjYW5hLml0L2RhdGFzZXQvcmljb3ZlcmF0aS1hbW1lc3NpLWRpbWVzc2ktZS1wZXJtYW5lbnphLWluLXJlcGFydGktb3JkaW5hcmktYW91LWNhcmVnZ2ktYW5uby0yMDEyKS4KCgpgYGB7cn0KZGZfY2FyZWdnaSA8LSByZWFkLmNzdigiZGF0YXNldHMvcmljb3ZlcmF0aS1hbW1lc3NpLWRpbWVzc2ktZS1wZXJtYW5lbnphLWluLXJlcGFydGktb3JkaW5hcmktcGVyLWFyZWEtZGktYXR0aXZpdGEuY3N2IikKCmhlYWQoZGZfY2FyZWdnaSkKCiN1c2lhbW8gZ2dwYWlycyBwZXIgdW4gZ3JhZmljbyBjaGUgY29tYmluYSBudXZvbGEgZGkgcHVudGksIGRlbnNpdMOgIHN0aW1hdGEgZSBjb3JyZWxvZ3JhbW1hIChpbiBhbHRlcm5hdGl2YSB1c2FyZSBzb2xvIGlsIGNvbWFuZG8gcGxvdCkKCmxpYnJhcnkoR0dhbGx5KQpnZ3BhaXJzKGRmX2NhcmVnZ2lbMjo0XSkKCgpgYGAKVmVkaWFtbyB1bmEgcGVyZmV0dGEgY29ycmVsYXppb25lIHRyYSBBbW1lc3NpIGUgRGltZXNzaSwgbWVudHJlIHVuYSBjb3JyZWxhemlvbmUgcG9zaXRpdmEgdHJhIEFtbWVzc2kgKG8gRGltZXNzaSkgZSBnaW9ybmkgYWNjdW11bGF0aSBkaSBkZWdlbnphIHByZXNzbyBpbCByZXBhcnRvLgoKCgojIEtOTiBwZXIgbGEgUmVncmVzc2lvbmUKClBlciBsYSByZWdyZXNzaW9uZSB1c2lhbW8gaW5pemlhbG1lbnRlIGlsIG1vZGVsbG8gJGskLU5OIGNoZSBzaSBiYXNhIHN1bGxhIG1lZGlhIGRlaSBmYXR0b3JpIGRpIHVzY2l0YSBkZWkgJGskIHB1bnRpIHBpw7kgdmljaW5pIGEgdW4gcHVudG8gdGVzdCBpbiB0ZXJtaW5pIGRpIGRpc3RhbnphIGV1Y2xpZGVhIGRlbGxlIGNhcmF0dGVyaXN0aWNoZSBkaSBpbmdyZXNzby4gUG9zc2lhbW8gdXNhcmUgY29tYW5kaSBkYSBkdWUgcGFjY2hldHRpOiBgYGtubi5yZWcoKWBgIGRhIGBgRk5OYGAgKGNoZSBmdW56aW9uYSBncm9zc29tb2RvIGNvbWUgYGBrbm5gYCBkZWwgcGFjY2hldHRvIGBgY2xhc3NgYCkgb3BwdXJlICBgYHRyYWluYGAgc3BlY2lmaWNhbmRvIGlsIG1ldG9kbyBgYGtubmBgIGUgYGBwcmVkaWN0YGAgZGkgYGBjYXJldGBgLgoKCiMjIERhdGFzZXQgZ2VuZXJhdG8KCmBgYHtyfQpsaWJyYXJ5KEZOTikKCiMgc2NlZ2xpYW1vIGludGFudG8gdW4gdmFsb3JlIGRpIGsgYSBwaWFjZXJlCgprIDwtIDUKCmtubl9nZW5lcmF0ZWQgPC0ga25uLnJlZyh0cmFpbiA9IGFzLm1hdHJpeChkZl9nZW5lcmF0ZWQkeCksIHRlc3QgPSBhcy5tYXRyaXgoeCksIHkgPSBkZl9nZW5lcmF0ZWQkeSwgayA9IGspCgpkZl9nZW5lcmF0ZWRfcHJlZCA8LSBkYXRhLmZyYW1lKHggPSB4LCB5ID0ga25uX2dlbmVyYXRlZCRwcmVkKQoKZ2dwbG90KCkgKwogIGdlb21fcG9pbnQoZGF0YSA9IGRmX2dlbmVyYXRlZCwgYWVzKHggPSB4LCB5ID0geSkpICsKICBnZW9tX2xpbmUoZGF0YSA9IGRmX2dlbmVyYXRlZF9wcmVkLCBhZXMoeCA9IHgsIHkgPSB5KSwgY29sb3VyPSdyZWQnKSsKICBnZ3RpdGxlKHBhc3RlKCJSZWdyZXNzaW9uZSBLTk4gc3VsIGRhdGFzZXQgZ2VuZXJhdG8gY29uIGsgPSIsIGspKQpgYGAKCgpQZXIgbCcqYWxsZW5hbWVudG8qIGRlbCBtb2RlbGxvIChvc3NpYSBsYSBzY2VsdGEgZGVsIHBhcmFtZXRybyAkayQpIGNvbnZpZW5lIHVzYXJlIGlsIHBhY2NoZXR0byBjYXJldC4KCgpgYGB7cn0KCiMgU3VkZGl2aXNpb25lIGRlaSBkYXRpCnRyYWluX2luZGV4IDwtIGNyZWF0ZURhdGFQYXJ0aXRpb24oZGZfZ2VuZXJhdGVkJHksIHAgPSAwLjcsIGxpc3QgPSBGQUxTRSkKdHJhaW5fc2V0IDwtIGRmX2dlbmVyYXRlZFt0cmFpbl9pbmRleCwgXQp0ZXN0X3NldCA8LSBkZl9nZW5lcmF0ZWRbLXRyYWluX2luZGV4LCBdCgojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIEtOTgprbm5fbW9kZWwgPC0gdHJhaW4oeSB+IHgsIGRhdGEgPSB0cmFpbl9zZXQsIG1ldGhvZCA9ICJrbm4iLCB0dW5lR3JpZCA9IGRhdGEuZnJhbWUoImsiPSAxOjUwKSkKIyBwZXIgc3BlY2lmaWNhcmUgaSB2YWxvcmkgZGkgayBkYXJlIGwnb3B6aW9uZSB0dW5lR3JpZD1kYXRhLmZyYW1lKCJrIj0uLi4pCgpwbG90KGtubl9tb2RlbCkKcHJpbnQoa25uX21vZGVsKQpgYGAKUGVyIGxhIHByZXZpc2lvbmUgdXNpYW1vIGxhIGZ1bnppb25lIGBgcHJlZGljdGBgIHNwZWNpZmljYW5kbyBtb2RlbGxvIGUgdGVzdCBzZXQuCgpgYGB7cn0KIyBQcmV2aXNpb25lIHN1bCB0ZXN0IHNldAprbm5fcHJlZCA8LSBwcmVkaWN0KGtubl9tb2RlbCwgdGVzdF9zZXQpCiAKIyBDYWxjb2xvIGRlbGwnZXJyb3JlCmtubl9ybXNlIDwtIHNxcnQobWVhbigoa25uX3ByZWQgLSB0ZXN0X3NldCR5KV4yKSkKcHJpbnQocGFzdGUoIlJNU0UgS05OOiIsIGtubl9ybXNlKSkKYGBgCgpgYGB7cn0KCiMgcGxvdCBkZWxsYSBwcmV2aXNpb25lIHZzIGZhdHRvcmkgZGkgdXNjaXRhIGVmZmV0dGl2aQoKZGZfdGVzdF9wcmVkIDwtIGRhdGEuZnJhbWUoeCA9IHRlc3Rfc2V0JHgsIHlfdHJ1ZSA9IHRlc3Rfc2V0JHksIHlfcHJlZCA9IGtubl9wcmVkKQpnZ3Bsb3QoZGZfdGVzdF9wcmVkLCBhZXMoeCA9IHgpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHlfdHJ1ZSksIGNvbG91ciA9ICJibGFjayIsIHNoYXBlPTEpICsKICBnZW9tX3BvaW50KGFlcyh5ID0geV9wcmVkKSwgY29sb3VyID0gInJlZCIsIHNoYXBlPTIpICsKICBnZ3RpdGxlKCJQcmV2aXNpb25pIEtOTiB2cyBWYWxvcmkgUmVhbGkgc3VsIFRlc3QgU2V0IikgKwogIHlsYWIoIlZhbG9yZSBkaSB1c2NpdGEiKSArCiAgeGxhYigiQ2FyYXR0ZXJpc3RpY2EgZGkgaW5ncmVzc28iKQpgYGAKClBvc3NpYW1vIGFuY2hlIGNvbnNpZGVyYXJlIGFsdHJpIGluZGljYXRvcmkgZGkgcGVyZm9ybWFuY2Ugc3VsIHRlc3Qgc2V0IChjb25mcm9udGlhbW9saSBjb24gcXVlbGxpIGRlbGxhIGNyb3NzIHZhbGlkYXRpb24gdXNhdGEgcGVyIGRldGVybWluYXJlICRrJCkuCgpgYGB7cn0KCiMgY2FsY29sYSBpbCBNQUUgc3VsIHRlc3Qgc2V0Cgprbm5fbWFlIDwtIG1lYW4oYWJzKGtubl9wcmVkIC0gdGVzdF9zZXQkeSkpCgojIGNhbGNvbGEgaWwgY29lZmZpY2llbnRlIGRpIGRldGVybWluYXppb25lIFJeMiBzdWwgdGVzdCBzZXQKCnNzX3RvdGFsIDwtIHN1bSgodGVzdF9zZXQkeSAtIG1lYW4odGVzdF9zZXQkeSkpXjIpCnNzX3JlcyA8LSBzdW0oKGtubl9wcmVkIC0gdGVzdF9zZXQkeSleMikKa25uX3IyIDwtIDEgLSAoc3NfcmVzIC8gc3NfdG90YWwpCgpgYGAKCkxgZXJvcmUgbWVkaW8gYXNzb2x1dG8gKE1BRSkgdmFsZSBgciBrbm5fbWFlYCBlIGlsIGNvZWZmaWNpZW50ZSBkaSBkZXRlcm1pbmF6aW9uZSAkUl4yJCB2YWxlIGByIGtubl9yMmAgKGNhbGNvbGF0aSBzdWwgdGVzdCBzZXQpLgoKIyMgRGF0YXNldCBCb3N0b24KClBhc3NpYW1vIG9yYSBhbCBkYXRhc2V0IHN1bGxlIGNhc2UgZGVpIHF1YXJ0aWVyaSBkaSBCb3N0b24uIEVzc28gY29udGllbmUgbW9sdGUgY2FyYXR0ZXJpc3RpY2hlLCBxdWluZGkgcG9zc2lhbW8gdmFsdXRhcmUgZGkgZWZmZXR0dWFyZSB1bmEgcmlkdXppb25lIGRpbWVuc2lvbmFsZSAoYWQgZXNlbXBpbyB0cmFtaXRlIFBDQSkuIFJpY29yZGF0ZSBhbmNoZSBjaGUgY29uIGkgbWV0b2RpIGJhc2F0aSBzdWxsYSBkaXN0YW56YSDDqCBjb25zaWdsaWF0byBzdGFuZGFyZGl6emFyZSBsZSBjYXJhdHRlcmlzdGljaGUgZGkgaW5wdXQgKG5vbiDDqCBuZWNlc3NhcmlvIHN0YW5kYXJkaXp6YXJlIHF1ZWxsZSBkaSBvdXRwdXQpLgoKVXNpYW1vIGxhIGNhcmF0dGVyaXN0aWNhIGBgbWVkdmBgICh2YWxvcmUgZGVsbGEgY2FzYSBtZWRpYW5vIG5lbCBxdWFydGllcmUpIGNvbWUgY2FyYXR0ZXJpc3RpY2EgZGkgdXNjaXRhLgoKYGBge3J9CiMgdXNpYW1vIGlsIHBhY2NoZXR0byBjYXJldCBwZXIga25uIHN1bCBkYXRhc2V0IGJvc3RvbgoKIyBTdWRkaXZpc2lvbmUgZGVpIGRhdGkKc2V0LnNlZWQoNDIpCnRyYWluX2luZGV4IDwtIGNyZWF0ZURhdGFQYXJ0aXRpb24oZGZfYm9zdG9uJG1lZHYsIHAgPSAwLjcsIGxpc3QgPSBGQUxTRSkKdHJhaW5fc2V0IDwtIGRmX2Jvc3Rvblt0cmFpbl9pbmRleCwgXQp0ZXN0X3NldCA8LSBkZl9ib3N0b25bLXRyYWluX2luZGV4LCBdCgojIEFsbGVuYW1lbnRvIGRlbCBtb2RlbGxvIEtOTiBzcGVjaWZpY2hpYW1vIGRpIGNlbnRyYXJlIGUgc2NhbGFyZSBpIGRhdGkKa25uX21vZGVsX2Jvc3RvbiA8LSB0cmFpbihtZWR2IH4gLiwgZGF0YSA9IHRyYWluX3NldCwgICBwcmVQcm9jZXNzID0gYygiY2VudGVyIiwgInNjYWxlIiksIG1ldGhvZCA9ICJrbm4iLCB0dW5lR3JpZCA9IGRhdGEuZnJhbWUoImsiPSAxOjIwKSkKCnBsb3Qoa25uX21vZGVsX2Jvc3RvbikKcHJpbnQoa25uX21vZGVsX2Jvc3RvbikKCmBgYAoKUG9zc2lhbW8gb3JhIHVzYXJlIGlsIG1vZGVsbG8gcGVyIHByZXZlZGVyZSBpbCB2YWxvcmUgc3VpIHF1YXJ0aWVyaSBkaSB0ZXN0LgoKYGBge3J9CgojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0Cmtubl9wcmVkX2Jvc3RvbiA8LSBwcmVkaWN0KGtubl9tb2RlbF9ib3N0b24sIHRlc3Rfc2V0KQojIENhbGNvbG8gZGVsbCdlcnJvcmUgZGkgdGVzdAprbm5fcm1zZV9ib3N0b24gPC0gc3FydChtZWFuKChrbm5fcHJlZF9ib3N0b24gLSB0ZXN0X3NldCRtZWR2KV4yKSkKcHJpbnQocGFzdGUoIlJNU0UgS05OIEJvc3RvbjoiLCBrbm5fcm1zZV9ib3N0b24pKQojIENvZWZmaWNpZW50ZSBSXjIgZGkgdGVzdApzc190b3RhbF9ib3N0b24gPC0gc3VtKCh0ZXN0X3NldCRtZWR2IC0gbWVhbih0ZXN0X3NldCRtZWR2KSleMikKc3NfcmVzX2Jvc3RvbiA8LSBzdW0oKGtubl9wcmVkX2Jvc3RvbiAtIHRlc3Rfc2V0JG1lZHYpXjIpCmtubl9yMl9ib3N0b24gPC0gMSAtIChzc19yZXNfYm9zdG9uIC8gc3NfdG90YWxfYm9zdG9uKQpwcmludChwYXN0ZSgiUl4yIEtOTiBCb3N0b246Iiwga25uX3IyX2Jvc3RvbikpCmBgYAoKKipFc2VyY2l6aW86KiogcmlwZXRlcmUgbCdhbmFsaXNpIHNlbGV6aW9uYW5kbyBzb2xhbWVudGUgYWxjdW5lIGNhcmF0dGVyaXN0aWNoZSBkZWwgZGF0YXNldC4gQ29tZSBjYW1iaWEgaWwgUk1TRT8gY29tZSBjYW1iaWEgaWwgY29lZmZpY2llbnRlIGRpIGRldGVybWluYXppb25lICRSXjIkPyBDb21lIGNhbWJpYSBsYSBwZXJmb3JtYW5jZSBkZWwgbWV0b2RvIHNlbnphIHN0YW5kYXJkaXp6YXJlIGkgZGF0aT8KCgoKQ29uZnJvbnRpYW1vIGwnZXJyb3JlIGRpIHRyYWluaW5nIGNvbiBsJ2Vycm9yZSBkaSB0ZXN0IGFsIHZhcmlhcmUgZGkgJGskLgoKYGBge3J9CiMgY2FsY29sYSB0cmFpbiBlIHRlc3QgZXJyb3IgYWwgdmFyaWFyZSBkaSBrCnRyYWluX2Vycm9yX2Jvc3RvbiA8LSBudW1lcmljKDIwKQpmb3IgKGsgaW4gMToyMCl7CiAgIyBjYWxjb2xhIGxlIHByZXZpc2lvbmkgc3VsIHRyYWluIHNldAogIGtubl9wcmVkX3RyYWluIDwtIHByZWRpY3QodHJhaW4obWVkdiB+IC4sIGRhdGEgPSB0cmFpbl9zZXQsICAgcHJlUHJvY2VzcyA9IGMoImNlbnRlciIsICJzY2FsZSIpLCBtZXRob2QgPSAia25uIiwgdHVuZUdyaWQgPSBkYXRhLmZyYW1lKCJrIj0gaykpLCB0cmFpbl9zZXQpCiAgIyBjYWxjb2xhIGlsIFJNU0UKICB0cmFpbl9lcnJvcl9ib3N0b25ba10gPC0gc3FydChtZWFuKChrbm5fcHJlZF90cmFpbiAtIHRyYWluX3NldCRtZWR2KV4yKSkKfQoKIyBwbG90IGRlaSByaXN1bHRhdGkgZGVsbGEgY3Jvc3MtdmFsaWRhdGlvbgpkZl9lcnJvcl9ib3N0b24gPC0gZGF0YS5mcmFtZShrID0gMToyMCwgdHJhaW5fZXJyb3IgPSB0cmFpbl9lcnJvcl9ib3N0b24sIHRlc3RfZXJyb3IgPSBrbm5fbW9kZWxfYm9zdG9uJHJlc3VsdHMkUk1TRSkKZ2dwbG90KGRmX2Vycm9yX2Jvc3RvbiwgYWVzKHggPSBrKSkgKwogIGdlb21fbGluZShhZXMoeSA9IHRyYWluX2Vycm9yLCBjb2xvdXIgPSAiVHJhaW5pbmcgRXJyb3IiKSkgKwogIGdlb21fcG9pbnQoYWVzKHkgPSB0cmFpbl9lcnJvciwgY29sb3VyID0gIlRyYWluaW5nIEVycm9yIiksIHNoYXBlPTEpICsKICBnZW9tX2xpbmUoYWVzKHkgPSB0ZXN0X2Vycm9yLCBjb2xvdXIgPSAiVGVzdCBFcnJvciIpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHRlc3RfZXJyb3IsIGNvbG91ciA9ICJUZXN0IEVycm9yIiksIHNoYXBlPTEpICsKICB5bGFiKCJSTVNFIikgKwogIGdndGl0bGUoIlRyYWluaW5nIGUgVGVzdCBFcnJvciBhbCB2YXJpYXJlIGRpIGsgKEJvc3RvbiBIb3VzaW5nKSIpICsKICBzY2FsZV9jb2xvdXJfbWFudWFsKCIiLCAKICAgICAgICAgICAgICAgICAgICAgIGJyZWFrcyA9IGMoIlRyYWluaW5nIEVycm9yIiwgIlRlc3QgRXJyb3IiKSwKICAgICAgICAgICAgICAgICAgICAgIHZhbHVlcyA9IGMoIlRyYWluaW5nIEVycm9yIj0idmlvbGV0IiwgIlRlc3QgRXJyb3IiPSJibHVlIikpKwogIHRoZW1lX21pbmltYWwoKQpgYGAKCiMjIERhdGFzZXQgQ2FyZWdnaQoKQ29uc2lkZXJpYW1vIGluZmluZSBpbCBkYXRhc2V0IGRlaSByaWNvdmVyaSBhbCBDYXJlZ2dpLiBMJ29iaWV0dGl2byBkZWxsYSByZWdyZXNzaW9uZSDDqCBwcmV2ZWRlcmUgaWwgbnVtZXJvIGRpIEdpb3JuaSBBY2N1bXVsYXRpIGluIGZ1bnppb25lIGRlbCBudW1lcm8gZGkgQW1tZXNzaSAobyBEaW1lc3NpKS4KCmBgYHtyfQojIFN1ZGRpdmlzaW9uZSBkZWkgZGF0aQpzZXQuc2VlZCg0MikKdHJhaW5faW5kZXggPC0gY3JlYXRlRGF0YVBhcnRpdGlvbihkZl9jYXJlZ2dpJEdpb3JuaUFjY3VtdWxhdGksIHAgPSAwLjcsIGxpc3QgPSBGQUxTRSkKdHJhaW5fc2V0IDwtIGRmX2NhcmVnZ2lbdHJhaW5faW5kZXgsIF0KdGVzdF9zZXQgPC0gZGZfY2FyZWdnaVstdHJhaW5faW5kZXgsIF0KCiMgQWxsZW5hbWVudG8gZGVsIG1vZGVsbG8gS05OCmtubl9tb2RlbF9jYXJlZ2dpIDwtIHRyYWluKEdpb3JuaUFjY3VtdWxhdGkgfiBBbW1lc3NpLCBkYXRhID0gdHJhaW5fc2V0LCBtZXRob2QgPSAia25uIiwgdHVuZUdyaWQgPSBkYXRhLmZyYW1lKCJrIj0gMTo0MCkpCnBsb3Qoa25uX21vZGVsX2NhcmVnZ2kpCnByaW50KGtubl9tb2RlbF9jYXJlZ2dpKQoKYGBgCgpJbCBtb2RlbGxvIGNvbiAkaz0kIGBgcmtubl9tb2RlbF9jYXJlZ2dpJGJlc3RUdW5lJGtgYCBtaW5pbWl6emEgbCdlcnJvcmUgZGkgY3Jvc3MtdmFsaWRhdGlvbi4gVHV0dGF2aWEgaWwgY29lZmZpY2llbnRlICRSXjI9JCBgYHIga25uX21vZGVsX2NhcmVnZ2kkcmVzdWx0cyRSc3F1YXJlZFtrbm5fbW9kZWxfY2FyZWdnaSRyZXN1bHRzJGsgPT0ga25uX21vZGVsX2NhcmVnZ2kkYmVzdFR1bmUka11gYCBpbmRpY2EgY2hlIGlsIG1vZGVsbG8gc3BpZWdhIHNvbG8gdW5hIHBpY2NvbGEgcGFydGUgZGVsbGEgdmFyaWFuemEuCgoKIyBSZWdyZXNzaW9uZSBMaW5lYXJlCgpQYXNzaWFtbyBvcmEgYWxsYSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlICh1bmEgdmFyaWFiaWxlIGRpIGlucHV0KS4gSWwgY29tYW5kbyBkaSBiYXNlIMOoIGBgbG0oKWBgLCBtYSBhbmNoZSBjYXJldCBwdcOyIGVzc2VyZSB1c2F0byBwZXIgbCdhbGxlbmFtZW50byBkZWwgbW9kZWxsby4KCiMjIERhdGFzZXQgZ2VuZXJhdG8KClBlciBpbCBkYXRhc2V0IGdlbmVyYXRvIHBvc3NpYW1vIGFzcGV0dGFyY2kgdW4nb3R0aW1hIGFkZXJlbnphIGFsIG1vZGVsbG8gc290dG9zdGFudGUuCgpgYGB7cn0KIyBkaXZpc2lvbmUgdHJhaW4gZSB0ZXN0IHNldAp0cmFpbl9pbmRleCA8LSBjcmVhdGVEYXRhUGFydGl0aW9uKGRmX2dlbmVyYXRlZCR5LCBwID0gMC43LCBsaXN0ID0gRkFMU0UpCnRyYWluX3NldCA8LSBkZl9nZW5lcmF0ZWRbdHJhaW5faW5kZXgsIF0KdGVzdF9zZXQgPC0gZGZfZ2VuZXJhdGVkWy10cmFpbl9pbmRleCwgXQoKIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBkaSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlCmxtX21vZGVsX2dlbmVyYXRlZCA8LSBsbSh5IH4gLiwgZGF0YSA9IHRyYWluX3NldCkKCnN1bW1hcnkobG1fbW9kZWxfZ2VuZXJhdGVkKQpgYGAKRGFsbGEgdGVvcmlhIHNhcHBpYW1vIGNoZSBpbCBjb2VmZmljaWVudGUgYW5nb2xhcmUgw6ggcHJvcG9yemlvbmFsZSBhbGxhIGNvcnJlbGF6aW9uZS4gVmVyaWZpY2hpYW1vbG8gbnVtZXJpY2FtZW50ZS4KCmBgYHtyfQoKbGFtYmRhIDwtIGNvcih0cmFpbl9zZXQkeSwgdHJhaW5fc2V0JHgpKnNkKHRyYWluX3NldCR5KS9zZCh0cmFpbl9zZXQkeCkKCgpwcmludChwYXN0ZSgiQ29lZmZpY2llbnRlIGFuZ29sYXJlIHN0aW1hdG86IiwgY29lZihsbV9tb2RlbF9nZW5lcmF0ZWQpWzJdKSkKcHJpbnQocGFzdGUoIkNvZWZmaWNpZW50ZSBhbmdvbGFyZSB0ZW9yaWNvOiIsIGxhbWJkYSkpCmBgYAoKCgpQb3NzaWFtbyBlZmZldHR1YXJlIG9yYSB1bmEgcHJldmlzaW9uZSBzdWwgdGVzdCBzZXQgZSBjYWxjb2xhcmUgbCdlcnJvcmUgKFJNU0UpLgoKYGBge3J9CgojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0CmxtX3ByZWRfZ2VuZXJhdGVkIDwtIHByZWRpY3QobG1fbW9kZWxfZ2VuZXJhdGVkLCB0ZXN0X3NldCkKCgojIENhbGNvbG8gZGVsbCdlcnJvcmUKbG1fcm1zZV9nZW5lcmF0ZWQgPC0gc3FydChtZWFuKChsbV9wcmVkX2dlbmVyYXRlZCAtIHRlc3Rfc2V0JHkpXjIpKQpwcmludChwYXN0ZSgiUk1TRSBSZWdyZXNzaW9uZSBMaW5lYXJlIChnZW5lcmF0byk6IiwgbG1fcm1zZV9nZW5lcmF0ZWQpKQpgYGAKClZpc3VhbGl6emlhbW8gYW5jaGUgbGEgcmV0dGEgZGkgcmVncmVzc2lvbmUuCgpgYGB7cn0KZ2dwbG90KGRmX2dlbmVyYXRlZCwgYWVzKHggPSB4LCB5ID0geSkpICsKICBnZW9tX3BvaW50KCkgKwpnZW9tX2FibGluZShzbG9wZT1sbV9tb2RlbF9nZW5lcmF0ZWQkY29lZmZpY2llbnRzWzJdLCBpbnRlcmNlcHQ9bG1fbW9kZWxfZ2VuZXJhdGVkJGNvZWZmaWNpZW50c1sxXSwgY29sPSdyZWQnKSArICBnZ3RpdGxlKCJSZWdyZXNzaW9uZSBMaW5lYXJlIFNlbXBsaWNlIHN1bCBEYXRhc2V0IEdlbmVyYXRvIikKYGBgCgpDb21lIHBvc3NpYW1vIGFnZ2l1bmdlcmUgZGVsbCdpbmZvcm1hemlvbmUgcmlndWFyZG8gYWxsJyppbmNlcnRlenphKiBkZWxsYSBwcmV2aXNpb25lPyBWZWRyZW1vIGxhIHRlb3JpYSBuZWxsYSBwcm9zc2ltYSBsZXppb25lLCBwZXIgaWwgbW9tZW50byB1c2lhbW8gaWwgY29tYW5kbyBgYHByZWRpY3RgYCBjb24gbCdvcHppb25lIGBgaW50ZXJ2YWw9InByZWRpY3Rpb24iYGAuCgpgYGB7cn0KIyBJbnRlcnZhbGxpIGRpIHByZXZpc2lvbmUKbG1fcHJlZF9jb25mIDwtIHByZWRpY3QobG1fbW9kZWxfZ2VuZXJhdGVkLCB0ZXN0X3NldCwgaW50ZXJ2YWw9InByZWRpY3Rpb24iLCBsZXZlbD0wLjk1KQoKIyBBZ2dpdW5naSBkZWxsZSBiYXJyZSBkaSBwcmV2aXNpb25lIGFsIHBsb3QKZGZfdGVzdF9wcmVkX2NvbmYgPC0gZGF0YS5mcmFtZSh4ID0gdGVzdF9zZXQkeCwgeV90cnVlID0gdGVzdF9zZXQkeSwgeV9wcmVkID0gbG1fcHJlZF9jb25mWywxXSwgbHdyID0gbG1fcHJlZF9jb25mWywyXSwgdXByID0gbG1fcHJlZF9jb25mWywzXSkKZ2dwbG90KGRmX3Rlc3RfcHJlZF9jb25mLCBhZXMoeCA9IHgpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHlfdHJ1ZSksIGNvbG91ciA9ICJibHVlIiwgc2hhcGU9MSkgKwogIGdlb21fbGluZShhZXMoeSA9IHlfcHJlZCksIGNvbG91ciA9ICJyZWQiKSArCiAgZ2VvbV9yaWJib24oYWVzKHltaW4gPSBsd3IsIHltYXggPSB1cHIpLCBhbHBoYSA9IDAuMikgKwogIGdndGl0bGUoIlJlZ3Jlc3Npb25lIExpbmVhcmUgY29uIEludGVydmFsbGkgZGkgcHJldmlzaW9uZSIpICsKICB5bGFiKCJWYWxvcmUgZGkgdXNjaXRhIikgKwogIHhsYWIoIkNhcmF0dGVyaXN0aWNhIGRpIGluZ3Jlc3NvIikKYGBgCgoKCiMjIERhdGFzZXQgQm9zdG9uIGhvdXNpbmcKCgpDb25zaWRlcmlhbW8gaWwgZGF0YXNldCBCb3N0b24gSG91c2luZyBlIGxhIHJlbGF6aW9uZSB0cmEgYGxzdGF0YCAocGVyY2VudHVhbGUgZGVsbGEgcG9wb2xhemlvbmUgYSBiYXNzbyByZWRkaXRvKSBlIGBtZWR2YCAodmFsb3JlIG1lZGlhbm8gZGVsbGUgY2FzZSBvY2N1cGF0ZSBkYSBwcm9wcmlldGFyaSkuIFVzaWFtbyBzdGF2b2x0YSBpbCBwYWNjaGV0dG8gY2FyZXQuCgpgYGB7ciBsaW5lYXItcmVncmVzc2lvbn0KIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBkaSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlCnNldC5zZWVkKDQyKQp0cmFpbl9pbmRleCA8LSBjcmVhdGVEYXRhUGFydGl0aW9uKEJvc3RvbiRtZWR2LCBwID0gMC43LCBsaXN0ID0gRkFMU0UpCnRyYWluX3NldCA8LSBCb3N0b25bdHJhaW5faW5kZXgsIF0KdGVzdF9zZXQgPC0gQm9zdG9uWy10cmFpbl9pbmRleCwgXQoKIyB1c2lhbW8gY2FyZXQKbG1fbW9kZWxfYm9zdG9uIDwtIHRyYWluKG1lZHYgfiBsc3RhdCwgZGF0YSA9IHRyYWluX3NldCwgbWV0aG9kID0gImxtIikKCnByaW50KGxtX21vZGVsX2Jvc3RvbikKYGBgCgpDb25mcm9udGlhbW8gaSBwYXJhbWV0cmkgdHJvdmF0aSBjb24gaSBkdWUgbWV0b2RpLgoKYGBge3J9CgpzdW1tYXJ5KGxtKG1lZHYgfiBsc3RhdCwgZGF0YSA9IHRyYWluX3NldCkpCgpsbV9tb2RlbF9ib3N0b24kZmluYWxNb2RlbAoKYGBgCgpOb3RpYW1vIGNoZSBpbCBjb2VmZmljaWVudGUgJFJeMiQgw6ggcGVnZ2lvcmUgZGkgcXVlbGxvIHRyb3ZhdG8gY29uICRrJC1OTiAocXVlc3RvIMOoIGRvdnV0byBhbCBiaWFzIGRlbCBtb2RlbGxvIGxpbmVhcmUgb2x0cmUgYWwgZmF0dG8gY2hlIHN0aWFtbyB1c2FuZG8gdW5hIHNvbGEgY2FyYXR0ZXJpc3RpY2E6ICoqcHJvdmFyZSBhZCBhcHBsaWNhcmUgJGskLU5OIGNvbiBpbCBzb2xvIGZhdHRvcmUgZGkgaW5ncmVzc28gbHN0YXQqKikuIENvbmZyb250aWFtbyBxdWluZGkgbCdlcnJvcmUgZGkgdHJhaW4gY29uIGwnZXJyb3JlIGRpIHRlc3QuCgpgYGB7cn0KIyBjYWxjb2xhciBSTVNFIGUgUioqMiBzdWwgdGVzdCBzZXQKdHJhaW5fcHJlZF9ib3N0b24gPC0gcHJlZGljdChsbV9tb2RlbF9ib3N0b24sIHRyYWluX3NldCkKdHJhaW5fcm1zZV9ib3N0b24gPC0gc3FydChtZWFuKCh0cmFpbl9wcmVkX2Jvc3RvbiAtIHRyYWluX3NldCRtZWR2KV4yKSkKc3NfdG90YWxfdHJhaW5fYm9zdG9uIDwtIHN1bSgodHJhaW5fc2V0JG1lZHYgLSBtZWFuKHRyYWluX3NldCRtZWR2KSleMikKc3NfcmVzX3RyYWluX2Jvc3RvbiA8LSBzdW0oKHRyYWluX3ByZWRfYm9zdG9uIC0gdHJhaW5fc2V0JG1lZHYpXjIpCnRyYWluX3IyX2Jvc3RvbiA8LSAxIC0gKHNzX3Jlc190cmFpbl9ib3N0b24gLyBzc190b3RhbF90cmFpbl9ib3N0b24pCnRlc3RfcHJlZF9ib3N0b24gPC0gcHJlZGljdChsbV9tb2RlbF9ib3N0b24sIHRlc3Rfc2V0KQp0ZXN0X3Jtc2VfYm9zdG9uIDwtIHNxcnQobWVhbigodGVzdF9wcmVkX2Jvc3RvbiAtIHRlc3Rfc2V0JG1lZHYpXjIpKQpzc190b3RhbF90ZXN0X2Jvc3RvbiA8LSBzdW0oKHRlc3Rfc2V0JG1lZHYgLSBtZWFuKHRlc3Rfc2V0JG1lZHYpKV4yKQpzc19yZXNfdGVzdF9ib3N0b24gPC0gc3VtKCh0ZXN0X3ByZWRfYm9zdG9uIC0gdGVzdF9zZXQkbWVkdileMikKdGVzdF9yMl9ib3N0b24gPC0gMSAtIChzc19yZXNfdGVzdF9ib3N0b24gLyBzc190b3RhbF90ZXN0X2Jvc3RvbikKcHJpbnQocGFzdGUoIlJNU0UgVHJhaW4gQm9zdG9uOiIsIHRyYWluX3Jtc2VfYm9zdG9uKSkKcHJpbnQocGFzdGUoIlJeMiBUcmFpbiBCb3N0b246IiwgdHJhaW5fcjJfYm9zdG9uKSkKcHJpbnQocGFzdGUoIlJNU0UgVGVzdCBCb3N0b246IiwgdGVzdF9ybXNlX2Jvc3RvbikpCnByaW50KHBhc3RlKCJSXjIgVGVzdCBCb3N0b246IiwgdGVzdF9yMl9ib3N0b24pKQpgYGAKCgpQcm9jZWRpYW1vIGNvbXVucXVlIGNvbiBsYSBwcmV2aXNpb25lIHN1bCB0ZXN0IHNldCBlIHBsb3R0aWFtbyBsYSByZXR0YSBkaSByZWdyZXNzaW9uZS4KCmBgYHtyfQojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0CmxtX3ByZWQgPC0gcHJlZGljdChsbV9tb2RlbF9ib3N0b24sIHRlc3Rfc2V0KQoKIyBDYWxjb2xvIGRlbGwnZXJyb3JlCmxtX3Jtc2UgPC0gc3FydChtZWFuKChsbV9wcmVkIC0gdGVzdF9zZXQkbWVkdileMikpCnByaW50KHBhc3RlKCJSTVNFIFJlZ3Jlc3Npb25lIExpbmVhcmU6IiwgbG1fcm1zZSkpCgojIFZpc3VhbGl6emEgbGEgcmVncmVzc2lvbmUKZ2dwbG90KEJvc3RvbiwgYWVzKHggPSBsc3RhdCwgeSA9IG1lZHYpKSArCiAgZ2VvbV9wb2ludCgpICsKICBnZW9tX2FibGluZShzbG9wZT1sbV9tb2RlbF9ib3N0b24kZmluYWxNb2RlbCRjb2VmZmljaWVudHNbMl0sIGludGVyY2VwdCA9IGxtX21vZGVsX2Jvc3RvbiRmaW5hbE1vZGVsJGNvZWZmaWNpZW50c1sxXSwgY29sPSJibHVlIikrCiAgZ2d0aXRsZSgiUmVncmVzc2lvbmUgTGluZWFyZSBTZW1wbGljZSIpCmBgYAoKQWdnaXVuZ2lhbW8gbCdpbnRlcnZhbGxvIGRpIHByZXZpc2lvbmUgKGNvbmZyb250YXJlIGNvbiBpbnRlcnZhbGxvIGRpIGNvbmZpZGVuemEpLiAKCmBgYHtyfQoKbG1fbW9kZWxfYm9zdG9uID0gbG0obWVkdiB+IGxzdGF0LCBkYXRhID0gdHJhaW5fc2V0KQoKIyBJbnRlcnZhbGxpIGRpIHByZXZpc2lvbmUKbG1fcHJlZF9jb25mX2Jvc3RvbiA8LSBwcmVkaWN0KGxtX21vZGVsX2Jvc3RvbiwgdGVzdF9zZXQsIGludGVydmFsPSJwcmVkaWN0aW9uIiwgbGV2ZWw9MC45NSkKIyBBZ2dpdW5naSBkZWxsZSBiYXJyZSBkaSBwcmV2aXNpb25lIGFsIHBsb3QKZGZfdGVzdF9wcmVkX2NvbmZfYm9zdG9uIDwtIGRhdGEuZnJhbWUoeCA9IHRlc3Rfc2V0JGxzdGF0LCB5X3RydWUgPSB0ZXN0X3NldCRtZWR2LCB5X3ByZWQgPSBsbV9wcmVkX2NvbmZfYm9zdG9uWywxXSwgbHdyID0gbG1fcHJlZF9jb25mX2Jvc3RvblssMl0sIHVwciA9IGxtX3ByZWRfY29uZl9ib3N0b25bLDNdKQpnZ3Bsb3QoZGZfdGVzdF9wcmVkX2NvbmZfYm9zdG9uLCBhZXMoeCA9IHgpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHlfdHJ1ZSksIGNvbG91ciA9ICJibHVlIiwgc2hhcGU9MSkgKwogIGdlb21fbGluZShhZXMoeSA9IHlfcHJlZCksIGNvbG91ciA9ICJyZWQiKSArCiAgZ2VvbV9yaWJib24oYWVzKHltaW4gPSBsd3IsIHltYXggPSB1cHIpLCBhbHBoYSA9IDAuMikgKwogIGdndGl0bGUoIlJlZ3Jlc3Npb25lIExpbmVhcmUgQm9zdG9uIGNvbiBJbnRlcnZhbGxpIGRpIHByZXZpc2lvbmUiKSArCiAgeWxhYigiVmFsb3JlIGRpIHVzY2l0YSIpICsKICB4bGFiKCJDYXJhdHRlcmlzdGljYSBkaSBpbmdyZXNzbyIpCmBgYAoKIyMjIFJlZ3Jlc3Npb25lIHBvbGlub21pYWxlCgpQcm92aWFtbyBhZCBhdW1lbnRhcmUgbGEgY29tcGxlc3NpdMOgIGRlbCBtb2RlbGxvIG1hbnRlbmVuZG8gdW5hIHNpbmdvbGEgY2FyYXR0ZXJpc3RpY2EgKGxzdGF0KSBtYSB1c2FuZG8gdW5hIGZ1bnppb25lIHBvbGlub21pYWxlLiBDb25zaWRlcmlhbW8gcGVyIGNvbmZyb250byBpbCBkYXRhc2V0IGdlbmVyYXRvIChwZXIgY3VpIG5vbiBkb3ZyZWJiZSBlc3NlcmUgbmVjZXNzaWFyaW8pLgoKYGBge3J9CiMgQWxsZW5hbWVudG8gZGVsIG1vZGVsbG8gZGkgcmVncmVzc2lvbmUgcG9saW5vbWlhbGUgY29uIGdyYWRvIDIKcG9seV9tb2RlbF9nZW5lcmF0ZWQgPC0gbG0oeSB+IHggKyBJKHheMiksIGRhdGEgPSBkZl9nZW5lcmF0ZWQpCnN1bW1hcnkocG9seV9tb2RlbF9nZW5lcmF0ZWQpCmBgYApVbmEgYWx0ZXJuYXRpdmEgdGVjbmljYW1lbnRlIG1pZ2xpb3JlIMOoIGRpIHVzYXJlIGlsIGNvbWFuZG8gYGBwb2x5KClgYCBzcGVjaWZpY2FuZG8gaWwgZ3JhZG8gZGVsIG1vZGVsbG8gcG9saW5vbWlhbGUuIEF0dGVuemlvbmUgcGVyw7IgY2hlIGkgY29lZmZpY2llbnRpICpub24qIHNvbm8gZGlyZXR0YW1lbnRlIHF1ZWxsaSBkZWwgcG9saW5vbWlvIG5hdHVyYWxlIChpbCBjb21hbmRvIHVzYSBjb21iaW5hemlvbmkgbGluZWFyaSBkZWkgcG9saW5vbWkgcGVyIG1pZ2xpb3JhcmUgbGEgcHJlY2lzaW9uZSkuCgpgYGB7cn0KcG9seV9tb2RlbF9nZW5lcmF0ZWQgPC0gbG0oeSB+IHBvbHkoeCwgZGVncmVlID0xMCksIGRhdGEgPSBkZl9nZW5lcmF0ZWQpCnN1bW1hcnkocG9seV9tb2RlbF9nZW5lcmF0ZWQpCgpgYGAKVmVkaWFtbyBjaGUgaW4gZW50cmFtYmkgaSBjYXNpIGlsIGNvZWZmaWNpZW50ZSBkZWwgdGVybWluZSBkaSBncmFkbyAkMCQgbm9uIMOoIHNpZ25pZmljYXRpdm8gKHF1aW5kaSBwdcOyIGVzc2VyZSByaW1vc3NvKS4gVmVkcmVtbyBtZWdsaW8gbGEgdGVvcmlhIGRpIHF1ZXN0byB0ZXN0IGxhIHByb3NzaW1hIGxlemlvbmUuIFBlciBpbCBtb21lbnRvIGFwcGxpY2hpYW1vIGxhIHN0ZXNzYSBzdHJhdGVnaWEgYWwgZGF0c2V0IEJvc3Rvbi4KCmBgYHtyIHBvbHlub21pYWwtcmVncmVzc2lvbn0KIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBkaSByZWdyZXNzaW9uZSBwb2xpbm9taWFsZSBjb24gZ3JhZG8gMgpwb2x5X21vZGVsIDwtIGxtKG1lZHYgfiBwb2x5KGxzdGF0LCBkZWdyZWUgPSAxMCksIGRhdGEgPSB0cmFpbl9zZXQpCgpzdW1tYXJ5KHBvbHlfbW9kZWwpCgpgYGAKVmVkaWFtbyBjaGUgaWwgY29lZmZpY2llbnRlICRSXjIkIMOoIG1pZ2xpb3JhdG8gKG1hIGF0dGVuemlvbmUgYWxsJypvdmVyZml0dGluZyopLgoKYGBge3J9CiMgUHJldmlzaW9uZSBzdWwgdGVzdCBzZXQKcG9seV9wcmVkIDwtIHByZWRpY3QocG9seV9tb2RlbCwgdGVzdF9zZXQpCgojIENhbGNvbG8gZGVsbCdlcnJvcmUKcG9seV9ybXNlIDwtIHNxcnQobWVhbigocG9seV9wcmVkIC0gdGVzdF9zZXQkbWVkdileMikpCnByaW50KHBhc3RlKCJSTVNFIFJlZ3Jlc3Npb25lIFBvbGlub21pYWxlOiIsIHBvbHlfcm1zZSkpCgojIFZpc3VhbGl6emEgbGEgcmVncmVzc2lvbmUgcG9saW5vbWlhbGUKZ2dwbG90KGRmX2Jvc3RvbiwgYWVzKHggPSBsc3RhdCwgeSA9IG1lZHYpKSArCiAgZ2VvbV9wb2ludCgpICsKICBnZW9tX2xpbmUoZGF0YT10ZXN0X3NldCwgYWVzKHggPSBsc3RhdCwgeSA9IHByZWRpY3QocG9seV9tb2RlbCwgbmV3ZGF0YSA9IHRlc3Rfc2V0KSwgY29sPSJyZWQiICkpKwogIyBnZW9tX3Ntb290aChtZXRob2QgPSAibG0iLCBmb3JtdWxhID0geSB+IHBvbHkoeCwgMiksIGNvbCA9ICJyZWQiKSArCiAgZ2d0aXRsZSgiUmVncmVzc2lvbmUgUG9saW5vbWlhbGUiKQpgYGAKClN0dWRpYW1vIGFsIHZhcmlhcmUgZGVsIGdyYWRvIGwnZXJyb3JlIGRpIHRyYWluaW5nICh1c2lhbW8gcXVpICRSXjIkIGUgY2VyY2hpYW1vIHVuIHB1bnRvIGRpICpnb21pdG8qKS4KCmBgYHtyfQpzZXQuc2VlZCg0MikKCnRyYWluX3IyIDwtIG51bWVyaWMoMTApCgpmb3IgKGdyYWRvIGluIDE6MTApewogICMgYWxsZW5hbWVudG8gZGVsIG1vZGVsbG8gcG9saW5vbWlhbGUgdXNhbmRvIGxtKCkKICBwb2x5X21vZGVsX2N2IDwtIGdsbShtZWR2IH4gcG9seShsc3RhdCwgZGVncmVlID0gIGdyYWRvICksIGRhdGEgPSB0cmFpbl9zZXQpCiAgCiAgIyBjYWxjb2xvIFJeMiBkaSB0cmFpbgogIHRyYWluX3ByZWQgPC0gcHJlZGljdChwb2x5X21vZGVsX2N2LCB0cmFpbl9zZXQpCiAgc3NfdG90YWxfdHJhaW4gPC0gc3VtKCh0cmFpbl9zZXQkbWVkdiAtIG1lYW4odHJhaW5fc2V0JG1lZHYpKV4yKQogIHNzX3Jlc190cmFpbiA8LSBzdW0oKHRyYWluX3ByZWQgLSB0cmFpbl9zZXQkbWVkdileMikKICB0cmFpbl9yMltncmFkb10gPC0gMSAtIChzc19yZXNfdHJhaW4gLyBzc190b3RhbF90cmFpbikKfQoKIyBwbG90CmRmX3IyIDwtIGRhdGEuZnJhbWUoZ3JhZG8gPSAxOjEwLCB0cmFpbl9yMiA9IHRyYWluX3IyKQpnZ3Bsb3QoZGZfcjIsIGFlcyh4ID0gZ3JhZG8sIHkgPSB0cmFpbl9yMikpICsKICBnZW9tX2xpbmUoKSArCiAgZ2VvbV9wb2ludCgpICsKICB5bGFiKCJSXjIgZGkgVHJhaW4iKSArCiAgeGxhYigiR3JhZG8gZGVsIFBvbGlub21pbyIpICsKICBnZ3RpdGxlKCJSXjIgZGkgVHJhaW4gYWwgdmFyaWFyZSBkZWwgZ3JhZG8gZGVsIHBvbGlub21pbyIpCgpgYGAKCiMjIyBSZWdyZXNzaW9uZSBlc3BvbmVuemlhbGUKClBvc3NpYW1vIHVzYXJlIGkgbW9kZWxsaSBsaW5lYXJpIGFuY2hlIHBlciBkaXBlbmRlbnplIHBpw7kgY29tcGxlc3NlLCBhZCBlc2VtcGlvIHBvc3NpYW1vIGNlcmNhcmUgdW5hIHJlbGF6aW9uZSBkZWwgdGlwbyAkeSBcYXBwcm94IGV4cChheCtiKSQ6IGJhc3RhIGluZmF0dGkgcGFzc2FyZSBhbCBsb2dhcml0bW8gZSBkaXZlbnRhIHVuYSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlICRcbG9nKHkpIFxhcHByb3ggYXgrYiQuCgpgYGB7cn0KIyBBbGxlbmFtZW50byBkZWwgbW9kZWxsbyBkaSByZWdyZXNzaW9uZSBlc3BvbmVuemlhbGUKZXhwX21vZGVsIDwtIGxtKGxvZyhtZWR2KSB+IGxzdGF0LCBkYXRhID0gdHJhaW5fc2V0KQoKc3VtbWFyeShleHBfbW9kZWwpCmBgYAoKCmBgYHtyfQojIFByZXZpc2lvbmUgc3VsIHRlc3Qgc2V0CmV4cF9wcmVkX2xvZyA8LSBwcmVkaWN0KGV4cF9tb2RlbCwgdGVzdF9zZXQpCmV4cF9wcmVkIDwtIGV4cChleHBfcHJlZF9sb2cpCiMgQ2FsY29sbyBkZWxsJ2Vycm9yZQpleHBfcm1zZSA8LSBzcXJ0KG1lYW4oKGV4cF9wcmVkIC0gdGVzdF9zZXQkbWVkdileMikpCnByaW50KHBhc3RlKCJSTVNFIFJlZ3Jlc3Npb25lIEVzcG9uZW56aWFsZToiLCBleHBfcm1zZSkpCiMgVmlzdWFsaXp6YSBsYSByZWdyZXNzaW9uZSBlc3BvbmVuemlhbGUKZ2dwbG90KCkgKwogIGdlb21fcG9pbnQoZGF0YSA9IHRlc3Rfc2V0LCBhZXMoeCA9IGxzdGF0LCB5ID0gbWVkdiksIGNvbG9yID0gImJsdWUiKSArCiAgZ2VvbV9saW5lKGRhdGEgPSB0ZXN0X3NldCwgYWVzKHggPSBsc3RhdCwgeSA9IGV4cChwcmVkaWN0KGV4cF9tb2RlbCwgbmV3ZGF0YSA9IHRlc3Rfc2V0KSkpLCBjb2xvciA9ICJyZWQiKSArCiAgbGFicyh0aXRsZSA9ICJSZWdyZXNzaW9uZSBFc3BvbmVuemlhbGUiLCB4ID0gImxzdGF0IiwgeSA9ICJtZWR2IikgKwogIHRoZW1lX21pbmltYWwoKQoKYGBgCgojIyBEYXRhc2V0IENhcmVnZ2kKCgpDb25mcm9udGlhbW8gaW5maW5lIGxhIHBlcmZvcm1hbmNlIGRpIHVuYSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlLCBwb2xpbm9taWFsZSBlIGluZmluZSBlc3BvbmVuemlhbGUgc3VsIGRhdGFzZXQgZGVsbCdvc3BlZGFsZSBDYXJlZ2dpLgoKCmBgYHtyfQojIHJlZ3Jlc3Npb25lIGxpbmVhcmUKCnNldC5zZWVkKDQyKQp0cmFpbl9pbmRleCA8LSBjcmVhdGVEYXRhUGFydGl0aW9uKGRmX2NhcmVnZ2kkR2lvcm5pQWNjdW11bGF0aSwgcCA9IDAuOCwgbGlzdCA9IEZBTFNFKQp0cmFpbl9zZXQgPC0gZGZfY2FyZWdnaVt0cmFpbl9pbmRleCwgXQp0ZXN0X3NldCA8LSBkZl9jYXJlZ2dpWy10cmFpbl9pbmRleCwgXQoKCmxpbmVhcl9tb2RlbF9jYXJlZ2dpIDwtIGxtKEdpb3JuaUFjY3VtdWxhdGkgfiBBbW1lc3NpLCBkYXRhID0gdHJhaW5fc2V0KQogIApzdW1tYXJ5KGxpbmVhcl9tb2RlbF9jYXJlZ2dpKQpsaW5lYXJfcHJlZF9jYXJlZ2dpIDwtIHByZWRpY3QobGluZWFyX21vZGVsX2NhcmVnZ2ksIHRlc3Rfc2V0KQpsaW5lYXJfcm1zZV92YWx1ZXMgPC0gc3FydChtZWFuKChwb2x5X3ByZWRfY2FyZWdnaSAtIHRlc3Rfc2V0JEdpb3JuaUFjY3VtdWxhdGkpXjIpKQpgYGAKCkNvbnNpZGVyaWFtbyBvcmEgdW5hIHJlZ3Jlc3Npb25lIHF1YWRyYXRpY2EgKHBvbGlub21pYWxlIGRpIGdyYWRvICQyJCkuCgpgYGB7cn0KCnBvbHlfbW9kZWxfY2FyZWdnaSA8LSBsbShHaW9ybmlBY2N1bXVsYXRpIH4gcG9seShBbW1lc3NpLCBkZWdyZWUgPSAyKSwgZGF0YSA9IHRyYWluX3NldCkKc3VtbWFyeShwb2x5X21vZGVsX2NhcmVnZ2kpCnBvbHlfcHJlZF9jYXJlZ2dpIDwtIHByZWRpY3QocG9seV9tb2RlbF9jYXJlZ2dpLCB0ZXN0X3NldCkKcG9seV9ybXNlX3ZhbHVlcyA8LSBzcXJ0KG1lYW4oKHBvbHlfcHJlZF9jYXJlZ2dpIC0gdGVzdF9zZXQkR2lvcm5pQWNjdW11bGF0aSleMikpCmBgYCAKVmVkaWFtbyBjaGUgaWwgdGVybWluZSBkaSBzZWNvbmRvIGdyYWRvIG5vbiDDqCBzaWduaWZpY2F0aXZvLiBQb3NzaWFtbyBsaW1pdGFyY2kgYWwgY2FzbyBsaW5lYXJlLiAgQ29uc2lkZXJpYW1vIGluZmluZSB1bmEgcmVsYXppb25lIGRlbCB0aXBvICRHaW9ybmkgXGFwcHJveCBWaXNpdGUgXlxhbHBoYSQsIGRvdmUgJFxhbHBoYSQgw6ggZGEgZGV0ZXJtaW5hcmUuIFBlciBxdWVzdG8gcG9zc2lhbW8gcGFzc2FyZSBhbCBsb2dhcml0bW8gYW1ibyBpIG1lbWJyaSBlIGRpdmVudGEgZGkgbnVvdm8gdW5hIHJlZ3Jlc3Npb25lIGxpbmVhcmUgc2VtcGxpY2UuCgpgYGB7cn0KbG9nX21vZGVsX2NhcmVnZ2kgPC0gbG0obG9nKEdpb3JuaUFjY3VtdWxhdGkpIH4gbG9nKEFtbWVzc2kpLCBkYXRhID0gdHJhaW5fc2V0KQpzdW1tYXJ5KGxvZ19tb2RlbF9jYXJlZ2dpKQpsb2dfcHJlZF9jYXJlZ2dpX2xvZyA8LSBwcmVkaWN0KGxvZ19tb2RlbF9jYXJlZ2dpLCB0ZXN0X3NldCkKbG9nX3ByZWRfY2FyZWdnaSA8LSBleHAobG9nX3ByZWRfY2FyZWdnaV9sb2cpCmxvZ19ybXNlX3ZhbHVlcyA8LSBzcXJ0KG1lYW4oKGxvZ19wcmVkX2NhcmVnZ2kgLSB0ZXN0X3NldCRHaW9ybmlBY2N1bXVsYXRpKV4yKSkKYGBgCklsIGNvZWZmaWNpZW50ZSBkZWwgbG9nYXJpdG1vIMOoICQwLjk5JCwgcXVpbmRpIGwnaXBvdGVzaSBkaSByZWxhemlvbmUgbGluZWFyZSDDqCB1bHRlcmlvcm1lbnRlIGNvbmZlcm1hdGEuCgpDb25mcm9udGlhbW8gaW5maW5lIGkgUk1TRS4KCmBgYHtyfQpwcmludChwYXN0ZSgiUk1TRSBSZWdyZXNzaW9uZSBMaW5lYXJlIChDYXJlZ2dpKToiLCBsaW5lYXJfcm1zZV92YWx1ZXMpKQpwcmludChwYXN0ZSgiUk1TRSBSZWdyZXNzaW9uZSBQb2xpbm9taWFsZSAoQ2FyZWdnaSk6IiwgcG9seV9ybXNlX3ZhbHVlcykpIApwcmludChwYXN0ZSgiUk1TRSBSZWdyZXNzaW9uZSBFc3BvbmVuemlhbGUgKENhcmVnZ2kpOiIsIGxvZ19ybXNlX3ZhbHVlcykpIApgYGAKClBsb3R0aWFtbyBpIHRyZSBtb2RlbGxpLgoKYGBge3J9CgpnZ3Bsb3QoKSArCiAgZ2VvbV9wb2ludChkYXRhID0gZGZfY2FyZWdnaSwgYWVzKHggPSBBbW1lc3NpLCB5ID0gR2lvcm5pQWNjdW11bGF0aSksIGNvbG9yID0gImJsdWUiKSArCiAgZ2VvbV9zbW9vdGgoZGF0YSA9IHRyYWluX3NldCwgYWVzKHggPSBBbW1lc3NpLCB5ID0gR2lvcm5pQWNjdW11bGF0aSksIG1ldGhvZCA9ICJsbSIsIGZvcm11bGEgPSB5IH4geCwgY29sb3IgPSAicmVkIiwgc2UgPSBGQUxTRSkgKwogIGdlb21fc21vb3RoKGRhdGEgPSB0cmFpbl9zZXQsIGFlcyh4ID0gQW1tZXNzaSwgeSA9IEdpb3JuaUFjY3VtdWxhdGkpLCBtZXRob2QgPSAibG0iLCBmb3JtdWxhID0geSB+IHBvbHkoeCwgMiksIGNvbG9yID0gImdyZWVuIiwgc2UgPSBGQUxTRSkgKwogIGdlb21fbGluZShkYXRhID0gdGVzdF9zZXQsIGFlcyh4ID0gQW1tZXNzaSwgeSA9IGV4cChwcmVkaWN0KGxvZ19tb2RlbF9jYXJlZ2dpLCBuZXdkYXRhID0gdGVzdF9zZXQpKSksIGNvbG9yID0gInB1cnBsZSIpICsKICBsYWJzKHRpdGxlID0gIkNvbmZyb250byBNb2RlbGxpIGRpIFJlZ3Jlc3Npb25lIChDYXJlZ2dpKSIsIHggPSAiQW1tZXNzaSIsIHkgPSAiR2lvcm5pIEFjY3VtdWxhdGkiKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICBzY2FsZV9jb2xvcl9tYW51YWwobmFtZSA9ICJNb2RlbGxvIiwgdmFsdWVzID0gYygiTGluZWFyZSIgPSAicmVkIiwgIlBvbGlub21pYWxlIiA9ICJncmVlbiIsICJFc3BvbmVuemlhbGUiID0gInB1cnBsZSIpKQpgYGAKCgoKIyBFc2VyY2l6aQoKCgoxLiBVdGlsaXp6YSBpbCBkYXRhc2V0IGBtdGNhcnNgIHBlciBwcmV2ZWRlcmUgaWwgY29uc3VtbyBkaSBjYXJidXJhbnRlIChgbXBnYCkgaW4gYmFzZSBhbCBwZXNvIGRlbGwnYXV0byAoYHd0YCkuIFZhbHV0YSBsZSBwZXJmb3JtYW5jZSBkZWwgbW9kZWxsbyAkayQtTk4gYWwgdmFyaWFyZSBkZWwgdmFsb3JlIGRpICRrJC4KCjIuIFV0aWxpenphIGlsIGRhdGFzZXQgYGlyaXNgIHBlciBwcmV2ZWRlcmUgbGEgbHVuZ2hlenphIGRlbCBwZXRhbG8gKGBQZXRhbC5MZW5ndGhgKSBpbiBiYXNlIGFsbGEgbHVuZ2hlenphIGRlbCBzZXBhbG8gKGBTZXBhbC5MZW5ndGhgKS4gQ2FsY29sYSBlIGludGVycHJldGEgaWwgY29lZmZpY2llbnRlIGRpIGRldGVybWluYXppb25lIFwoIFJeMiBcKS4KCjMuIEdlbmVyYSB1biBkYXRhc2V0IGNvbiB1bmEgcmVsYXppb25lIHF1YWRyYXRpY2EgKGFkIGVzZW1waW8sIFwoIHkgPSB4XjIgKyBcdGV4dHtydW1vcmV9IFwpKS4gQXBwbGljYSB1bmEgcmVncmVzc2lvbmUgcG9saW5vbWlhbGUgZGkgc2Vjb25kbyBncmFkbyBlIGNvbmZyb250YSBpbCByaXN1bHRhdG8gY29uIHVuYSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlLgoKNC4gQ3JlYSB1biBkYXRhc2V0IGluIGN1aSBsYSB2YXJpYWJpbGUgZGlwZW5kZW50ZSBjcmVzY2UgZXNwb25lbnppYWxtZW50ZSByaXNwZXR0byBhIHVuYSB2YXJpYWJpbGUgaW5kaXBlbmRlbnRlLiBBcHBsaWNhIHVuYSByZWdyZXNzaW9uZSBlc3BvbmVuemlhbGUgZSBjb25mcm9udGEgaWwgUk1TRSBjb24gcXVlbGxvIGRpIHVuYSByZWdyZXNzaW9uZSBsaW5lYXJlLgoKNS4gVXRpbGl6emEgaWwgZGF0YXNldCBgSXJpc2AgcGVyIHByZXZlZGVyZSBsYSBsdW5naGV6emEgZGVsIHBldGFsbyBjb21lIGZ1bnppb25lIGRlbGxhIGx1bmdoZXp6YSBkZWwgc2VwYWxvIGVsZXZhdGEgYWQgdW4gZXNwb25lbnRlICRcYWxwaGEkIGRhIGRldGVybWluYXJlIHRyYW1pdGUgcmVncmVzc2lvbmUgbGluZWFyZS4KCjYuIFV0aWxpenphIGlsIGRhdGFzZXQgYGFpcnF1YWxpdHlgIHBlciBwcmV2ZWRlcmUgbGEgdGVtcGVyYXR1cmEgKGBUZW1wYCkgaW4gYmFzZSBhbGwnb3pvbm8gKGBPem9uZWApLiBTcGVyaW1lbnRhIGNvbiBLTk4gZSByZWdyZXNzaW9uZSBsaW5lYXJlIHNlbXBsaWNlIGUgY29uZnJvbnRhIGdsaSBlcnJvcmkgZGkgcHJldmlzaW9uZS4KCjcuIFBlciB1biBtb2RlbGxvIEtOTiBjb3N0cnVpdG8gY29uIHVuIGRhdGFzZXQgZ2VuZXJhdG8sIGNhbGNvbGEgbCdlcnJvcmUgbWVkaW8gYXNzb2x1dG8gKE1BRSkgZSBpbCByb290IG1lYW4gc3F1YXJlZCBlcnJvciAoUk1TRSkgZSBkaXNjdXRpIGxlIGxvcm8gaW1wbGljYXppb25pLgoKOC4gVXRpbGl6emEgaWwgZGF0YXNldCBgZGlhbW9uZHNgIHBlciBwcmV2ZWRlcmUgaWwgcHJlenpvIChgcHJpY2VgKSBpbiBiYXNlIGFsbGUgY2FyYXR0ZXJpc3RpY2hlIGRlbCBkaWFtYW50ZSAoYGNhcmF0YCwgYGN1dGAsIGBjb2xvcmApLiBQcm92YSBhIHVzYXJlIEtOTiBlIHJlZ3Jlc3Npb25lIHBvbGlub21pYWxlIGUgZGlzY3V0aSBjb21lIGxhIHNjZWx0YSBkZWxsZSBjYXJhdHRlcmlzdGljaGUgaW5mbHVpc2NlIHN1bGxlIHBlcmZvcm1hbmNlLgoKOS4gQ29zdHJ1aXNjaSB1biBtb2RlbGxvIGRpIHJlZ3Jlc3Npb25lIGxpbmVhcmUgc2VtcGxpY2UgdXRpbGl6emFuZG8gaWwgZGF0YXNldCBgQ2hpY2tXZWlnaHRgIHBlciBwcmV2ZWRlcmUgaWwgcGVzbyAoYHdlaWdodGApIGluIGJhc2UgYWxsJ2V0w6AgKGBUaW1lYCkuIFZpc3VhbGl6emEgaSByaXN1bHRhdGkgZSBnbGkgaW50ZXJ2YWxsaSBkaSBwcmV2aXNpb25lLgoKCgo=