Datasets

Lavoreremo con un dataset creato appositamente, uno invece già caricato in R (ad esempio ChickWeights) e uno di dati reali (censimento di persone senza tetto per regioni italiane dall’ISTAT).

Dataset pseudo-casuale

Per generare il dataset, usiamo il comand rnorm().

# Possiamo importare un seed per la riproducibilità, altrimenti ognuno avrà un dataset leggermente diverso
# set.seed(42)

# Generazione di dati fittizi con 200 osservazoni, 
n <- 100
x1 <- rnorm(n, mean = 5, sd = 1)
y1 <- rnorm(n, mean = 5, sd = 1)
x2 <- rnorm(n, mean = 8, sd = 1)
y2 <- rnorm(n, mean = 8, sd = 1)


# Creiamo un dataframe, includiamo anche il gruppo (non useremo per il clustering)
data_random <- data.frame(
  x = c(x1, x2),
  y = c(y1, y2),
  group = factor(rep(1:2, each = n))
)

Visualizziamo i dati generati con il comando plot() di base oppure usando ggplot2.

# plot di base
plot(data_random$x, data_random$y, col=data_random$group)

# usando ggplot

library("ggplot2")


ggplot(data_random, aes(x, y, color = group)) +
  geom_point() +
  labs(title = "Dataset generato", x = "X", y = "Y")

Dataset ChickWeight

Questo dataset ChickWeight (cercare sull’help) contiene informazioni relative alla crescita di polli con diverse diete. Il clustering permette di esplorare i dati ad esempio individuando due (o più) categorie di diete in base all’effetto sulla crescita.

head(ChickWeight)

Notiamo però che è presente una colonna Time in cui è registrato il tempo dalla crescita dell’individuo colonna Chick. Per applicare il clustering voremmo invece avere solo una riga per individuo contenente i pesi nei vari giorni (0, 2, 4, 6, ecc.). Questo accade spesso con dati reali: non sono strutturati come vorremmo (perché raccolti da altri, ad esempio con altri scopi). Per ripulire i dati, possiamo usare il pacchetto tidyr della suite tidyverse (https://www.tidyverse.org/). Questo foglio descrive brevemente alcuni comandi principali: https://leadousset.github.io/intro-to-R/cheatsheet_tidy.pdf

# dare il comando install.packages("tidyverse") se non è già installato
library("tidyr")

Nel nostro caso vogliamo allargare il data frame in modo che abbia più colonne (una per ciascuna età). Usiamo quindi il comando pivot_wider().

chick_tidy <- pivot_wider(data=ChickWeight, names_from = Time, values_from = weight)

Visualizziamo la tabella ripulita.

chick_tidy

Notiamo che ci sono dei valori mancanti NA. Questo accade spesso con dati reali e bisogna tenerne conto. L’approccio più semplice è di rimuovere completamente le righe per cui almeno una osservazione è mancante. In tidyr esiste il comando drop_na() che fa appunto questo.

chick_tidy <- drop_na(chick_tidy)

chick_tidy
NA

Le righe con almeno un dato mancante sono state rimosse. Attenzione però al rischio di cadere in errori logici come il Survivorship bias oppure il cherry picking: rimuovendo una porzione di dati rilevanti al problema, si potrebbero trarre conclusioni del tutto errate. Ad esempio, i polli che crescono di più grazie ad una particolare dieta vengono uccisi una settimana prima e quindi non si registra il peso dell’ultima settimana. Se fosse così, rimuovendo i valori NA si rimuove proprio il segnale che si sta cercando!

Dataset senzatetto

Carichiamo infine un dataset reale, proveniente dall’Istituto nazionale di statistica (ISTAT), relativo al numero di persone senza tetto e senza fissa dimora per regione, anno 2021. I dati sono scaricati dalla pagina https://esploradati.istat.it/databrowser/#/it/censpop/categories/DCSS_SENZA_TETTO_TV/IT1,DF_DCSS_SENZA_TETTO_TV_1,1.0 ma si trovano anche sul team o il sito del corso.

I dati possono essere salvati in vari formati, il più comune e standard è il formato .csv(comma-separated values) in cui (eccetto al più qualche riga di commento iniziare), i dati sono scritti in testo semplice, ciascuna riga relativa ad una riga del data frame e le colonne separate dalla virgola (comma in inglese). Il comando di base per leggere i file in questo formato è read.csv(), mettendo come argomento una stringa con il nome del file (eventualmente nelle sottocartelle del progetto).

# dopo aver scaricato il file senza_tetto_italia.csv e averlo copiato in una sottocartella del progetto chiamata datasets, carichiamo il file

senza_tetto_caricato <- read.csv("datasets/senza_tetto_italia.csv")

head(senza_tetto_caricato)
NA

Anche in questo caso vediamo che i dati vanno ripuliti, selezionando solo le colonne di interesse ed eventualmente allargando le righe per le classi di età.

Digressione su input/output di dati

Notiamo intanto che l’uso della virgola potrebbe essere un problema con i decimali: in inglese si usa invece il punto \(\pi= 3.1415..\), mentre in italiano e altre lingue potrebbe creare letture sbagliate. Per questo ci sono anche formati alternativi, come il .tsv (tab-separated values) in cui si usa una spaziatura tab per separare i valori. Il comando diventa allora read.tsv()

Altra cosa invece sono i formati di Excel che sono proprietari contengono molte più informazioni, anche circa la storia delle operazioni che sono state effettuate sui dati (ad esempio, un caso di dati manomessi è stato appunto sollevato proprio studiando le operazioni effettuate sull’Excel fornito da un gruppo di autori https://datacolada.org/109). Il pacchetto standard dedicato all’input di dati da Excel in R è `readxl. Se preferite usare l’interfaccia grafica di RStudio, nel tab Environment trovate il bottone Import Dataset che permette di importare da csv, Excel e anche fare delle prime operazioni sul data frame che verrà assegnato.

Per gestire in modo più semplice l’input di dati da vari formati, personalmente consiglio il pacchetto rio che ha qualche funzionalità automatizzata per l’input (comando import()) e l’output (comando export).

# per installare rio usare il comando install.packages("rio")
library("rio")

# esportiamo il dataset dei polli ripulito in formato excel semplicemente dando l'estensione .xlsx al nome del file

export(chick_tidy, "datasets/polli_puliti.xlsx")

# se navigate nella sottocartella datasets troviamo il file salvato. Possiamo salvare anche in altri formati, digitando l'estensione corretta.

export(chick_tidy, "datasets/polli_puliti.csv")

# con il comando import carichiamo invece da molteplici formati, incluso Excel.

polli_excel <- import("datasets/polli_puliti.xlsx")

head(polli_excel)

Pulizia dataset senza tetto

Torniamo al dateset senza tetto che abbiamo caricato.

head(senza_tetto_caricato)

Selezioniamo solo le colonne corrispondenti alla regione Territorio al codice di età e alla frequenza rilevata Osservazione.


senza_tetto_selezione <- data.frame( "regione" = senza_tetto_caricato$Territorio, "age" = senza_tetto_caricato$AGE_CLASS, "frequenza" = senza_tetto_caricato$Osservazione)

head(senza_tetto_selezione)

A questo punto usiamo di nuovo pivot_wider per creare delle colonne relative alle varie età.

senza_tetto_tidy <- pivot_wider(senza_tetto_selezione, names_from = age, values_from = frequenza)

head(senza_tetto_tidy)

Possiamo anche salvare il dataset ripulito nel caso ci servisse più avanti (o dovessimo caricarlo, ad esempio per il progetto della proma di esame).

export(senza_tetto_tidy, "datasets/senza_tetto_tidy.csv")

Metodi non gerarchici

Discutiamo prima i metodi di clustering non gerarchici, in particolare K-means kmeans() e Partitioning Around Medoids (pam() dalla libreria cluster).

K-means clustering

Applichiamo K-means al dataset generato. Togliamo la terza colonna (quella che contiene già il gruppo, per come l’abbiamo generato).

head(data_random)
kmeans_data_random <- kmeans(data_random[-3], centers = 2)

# Il risultato è una lista contenente varie informazioni

kmeans_data_random
K-means clustering with 2 clusters of sizes 102, 98

Cluster means:
         x        y
1 5.063792 4.963971
2 8.103742 8.050131

Clustering vector:
  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 [36] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 [71] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
[106] 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[141] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2
[176] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

Within cluster sum of squares by cluster:
[1] 202.2157 194.6455
 (between_SS / total_SS =  70.3 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"    
[5] "tot.withinss" "betweenss"    "size"         "iter"        
[9] "ifault"      

Ricordiamo che erano 100 punti per gruppo e le medie (che ci aspettiamo essere i centri) erano rispettivamente \((5,5)\), \((8,8)\). Aggiungiamo la colonna del cluster al data frame originale.


data_random <- cbind( data_random, "kmeans" =  factor(kmeans_data_random$cluster ))

Possiamo confrontare quindi con una tabella di contingenza table() i due cluster (originale e quello di kmeans).

table( "originale" = data_random$group, "kmeans"=data_random$kmeans)
         kmeans
originale   1   2
        1 100   0
        2   2  98

Ovviamente non è detto che il cluster etichettato con \(1\) da k-means corrisponda con la classe \(1\) originale!

Possiamo fare un plot usando come colore il cluster trovato con k-means.


plot(data_random$x, data_random$y, col=data_random$kmeans)

Con ggplot possiamo assegnare la forma del gruppo originale e il colore del cluster trovato con k-means. Riuscite a vedere i punti non classificati correttamente?

ggplot(data = data_random, aes(x=x, y=y, colour = kmeans, shape = group)) + geom_point()

Come determinare \(k\)? l’output di k-means fornisce il WCSS per cluster e il WCSS totale.


kmeans_data_random$withinss
[1] 202.2157 194.6455
kmeans_data_random$tot.withinss
[1] 396.8612

Plottiamo il WCSS per vari valori di \(k\) (cercando di applicare il cosiddetto metodo elbow).


WCSS <- c()

for(k in 2:10){
  WCSS <- c(WCSS, kmeans(data_random[1:2], centers=k)$tot.withinss)
}

plot(2:10,  WCSS, type='l', xlab="numero di clusters", ylab="WCSS")

Provate a riapplicare il blocco di codice sopra. Cosa notate? L’algoritmo di k-means (e pure pam) è in realtà molto sensibile ai centri iniziali. Per questo è meglio applicare il metodo diverse istanze, indicare il valore medio e un intervallo di confidenza (in questo caso bilatero al livello \(95\%\)).


WCSS <- data.frame("k"=numeric(), "mean"=numeric(), "sd" =numeric() )

numero_runs <- 10

for(k in 2:10){
  wcss_runs <- c()
  for (i in 1:numero_runs){
    wcss_runs <- c(wcss_runs,  kmeans(data_random[1:2], centers=k)$tot.withinss)
  }
  WCSS <- rbind( WCSS, data.frame(k, mean(wcss_runs), sd(wcss_runs)))
}

plot(2:10,  WCSS$mean, type='l', xlab="numero di clusters", ylab="WCSS", col="red")
lines(2:10, WCSS$mean+qt(0.975, df=numero_runs-1) * WCSS$sd/sqrt(numero_runs), col="grey")
lines(2:10, WCSS$mean-qt(0.975, df=numero_runs-1) * WCSS$sd/sqrt(numero_runs), col="grey")

Per esercizio, creare un dataset in cui il numero di clusters sia diverso da 2 e verificare l’andamento del WCSS riconoscendo se possibile il punto di gomito.

Partitioning Around Medoids (PAM)

Applichiamo ora PAM e confrontiamo il risultato con k-means al dataset chick_tidy. Il comando è pam() dal pacchetto cluster. Come kmeans, bisogna specificare \(k\). Togliamo le prime due colonne (numero identificativo individuo e tipo di dieta).


pam_chick <- pam(chick_tidy[-(1:2)], k = 2)

pam_chick
Medoids:
     ID  0  2  4  6   8  10  12  14  16  18  20  21
[1,] 18 41 55 64 77  90  95 108 111 131 148 164 167
[2,] 21 40 49 62 78 102 124 146 164 197 231 259 265
Clustering vector:
 [1] 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 1 2 1 1 1 2 2 1 2 2 1 2 2 1 2 2 2 1 2 2
[36] 2 2 2 2 1 2 2 2 2 2
Objective function:
   build     swap 
82.28238 74.21691 

Available components:
 [1] "medoids"    "id.med"     "clustering" "objective"  "isolation" 
 [6] "clusinfo"   "silinfo"    "diss"       "call"       "data"      

Possiamo anche in questo case aggiungere il vettore di clustering trovato al data frame.


chick_tidy$pam_cluster <- pam_chick$clustering

In questo caso non abbiamo delle classi con cui naturalmente confrontare il risultato, quindi possiamo ad esempio confrontare con \(k\)-means.


# rimuoviamo anche l'ultima colonna (che contiene il clustering di pam)

kmeans_chick <- kmeans(chick_tidy[-c(1, 2, 15)],  2)

kmeans_chick
K-means clustering with 2 clusters of sizes 23, 22

Cluster means:
         0        2        4        6         8        10       12
1 41.43478 49.17391 58.78261 70.82609  83.95652  97.04348 112.7391
2 40.68182 50.00000 61.59091 79.09091 101.27273 123.72727 153.7273
        14       16       18       20       21
1 120.6957 134.8696 148.4348 160.3478 162.5217
2 172.9545 205.7727 238.4091 265.1818 277.4091

Clustering vector:
 [1] 1 1 1 1 2 1 2 1 1 1 1 1 2 1 1 1 2 1 1 1 2 2 1 2 2 1 2 2 1 2 2 2 1 2 2
[36] 2 1 2 2 1 2 1 2 2 2

Within cluster sum of squares by cluster:
[1] 164560.6 160635.7
 (between_SS / total_SS =  59.7 %)

Available components:

[1] "cluster"      "centers"      "totss"        "withinss"    
[5] "tot.withinss" "betweenss"    "size"         "iter"        
[9] "ifault"      

Aggiungiamo anche questi risultati al data frame e confrontiamo con una tabella di contingenza.


chick_tidy$kmeans_cluster <- kmeans_chick$cluster

table("pam"=chick_tidy$pam_cluster, "kmeans"=chick_tidy$kmeans_cluster)
   kmeans
pam  1  2
  1 21  0
  2  2 22

Vediamo che le classi trovate sono molto simili. La scelta dei medoid può influenzare i risultati, ma PAM è generalmente più stabile in presenza di rumore.

Un vantaggio notevole di pam rispetto a k-means è la possibilità di usare metriche diverse. È possibile dare come input invece del data frame una matrice di dissimilarità, oppure specificare metric = "manhattan" per usare la distanza \(\ell_1\) (taxicab).


pam_chick <- pam(chick_tidy[-c(1,2, 15, 16)], k = 2, metric="manhattan")

chick_tidy$pam_manhattan_cluster <- pam_chick$cluster

Confrontiamo i risultati di pam con le due metriche.

table("pam"=chick_tidy$pam_cluster, "pam_manhattan"=chick_tidy$pam_manhattan_cluster)
   pam_manhattan
pam  1  2
  1 20  1
  2  0 24

Possiamo infine usare la silhouette per valutare i cluster trovati (anche per lo stesso \(k\)). Il comando è silhouette() dal pacchetto cluster, a cui bisogna dare come input il vettore del cluster e una matrice di dissimilarità (ad esempio calcolata con la funzione dist())

sil_pam <- silhouette(chick_tidy$pam_cluster, dist(chick_tidy[-c(1,2,15, 16, 17)]))

sil_pam_manhattan <- silhouette(chick_tidy$pam_manhattan_cluster, dist(chick_tidy[-c(1,2,15, 16, 17)]))
                                
sil_kmeans <- silhouette(chick_tidy$kmeans_cluster, dist(chick_tidy[-c(1,2,15, 16, 17)]))

Possiamo plottare la silhouette per ciascun metodo o per ciascun cluster, oppure limitarci alla silhouette media.


plot(sil_pam)


boxplot(sil_pam[, 3])


# con la funzione summary otteniamo un riassunto delle varie silhouette in cui possiamo visualizzare la silhouette media

summary(sil_pam)
Silhouette of 45 units in 2 clusters from silhouette.default(x = chick_tidy$pam_cluster, dist = dist(chick_tidy[-c(1, 2, 15, 16, 17)])) :
 Cluster sizes and average silhouette widths:
       21        24 
0.4800079 0.4547099 
Individual silhouette widths:
    Min.  1st Qu.   Median     Mean  3rd Qu.     Max. 
-0.02622  0.37946  0.53847  0.46652  0.61631  0.64761 

Confrontiamo le tre silhouette medie.


print(paste("silhouette media per PAM:", round(mean(sil_pam[, 3]), 4)))
[1] "silhouette media per PAM: 0.4665"
print(paste("silhouette media per PAM Manhattan:", round( mean(sil_pam_manhattan[,3]), 4)))
[1] "silhouette media per PAM Manhattan: 0.4664"
print(paste("silhouette media per k-means:", round(mean(sil_kmeans[,3]), 4)))
[1] "silhouette media per k-means: 0.471"

Per esercizio: completate aggiungendo la deviazione standard delle silhouette calcolate.

Metodi gerarchici

Agnes (agglomerativo)

Il comando hclust() permette di utilizzare diversi metodi. In alternativa, possiamo essere più specifici e usare agnes() del pacchetto cluster.

Consideriamo il dataset relativo alle persone senza tetto e usiamo agnes(), che di base usa il metodo di average linkage con distanza Euclidea (togliamo la prima colonna che contiene i nomi).


agnes_senza_tetto <- agnes(senza_tetto_tidy[-1])

Possiamo visualizzare il risultato con il dendrogramma.

plot(agnes_senza_tetto)

Per visualizzare il plot possiamo usare prima colonna come nome delle righe del data frame e usare ggdendro(estensione di ggplot2).

senza_tetto_labels <- as.data.frame(senza_tetto_tidy[-1])
rownames(senza_tetto_labels) <- senza_tetto_tidy$regione

#ggdendro permette di visualizzare meglio i dendrogrammi usando la grammatica di ggplot2

library("ggdendro")

dg <- dendro_data(agnes(senza_tetto_labels))

ggdendrogram(dg)

Una osservazione importante sui dati: stiamo confrontando le frequenze assolute dei senza tetto, quindi è naturale che le regioni più popolose avranno più persone senza fissa dimora (stiamo quindi implicitamente facendo clustering in base alla popolazione totale nella regione).

Esercizio: recuperare dal sito ISTAT il numero di abitanti per regione ed eseguire un clustering usando la frequenza relativa dei senza tetto sulla popolazione totale. Confrontare i dendrogrammi ottenuti.

Per ovviare a questo problema, effuttiamo clustering soltanto sulla frequenza relativa della popolazione nelle varie classi di età.

senza_tetto_relative <- data.frame( senza_tetto_labels[1:4]/senza_tetto_labels[,5])

agnes_senza_tetto_relative <- agnes(senza_tetto_relative)

ggdendrogram(dendro_data(agnes_senza_tetto_relative))

Tornando al problema, il comando cutree() permette di ricavare il vero e proprio clustering tagliando il dendrogramma: si può specificare l’altezza o il numero di cluster desiderati. Consideriamo ad esempio \(k=5\) clusters.


senza_tetto_relative$agnes_k_5 <- cutree(agnes_senza_tetto_relative, k=5)

Studiamo la silhouette: notiamo un valore medio non molto alto.

sil_agnes_senza_tetto <- silhouette(senza_tetto_relative$agnes_k_5, dist(senza_tetto_relative[1:4]))

summary(sil_agnes_senza_tetto)
Silhouette of 22 units in 5 clusters from silhouette.default(x = senza_tetto_relative$agnes_k_5, dist = dist(senza_tetto_relative[1:4])) :
 Cluster sizes and average silhouette widths:
        8         9         3         1         1 
0.4142725 0.5059859 0.3994374 0.0000000 0.0000000 
Individual silhouette widths:
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.0000  0.4163  0.4618  0.4121  0.5146  0.6255 

Diana (divisivo)

Con il comando diana() applichiamo il metodo divisivo. Vediamo che non ci sono grandi differenze.


diana_senza_tetto_relative <- diana(senza_tetto_relative)

ggdendrogram(dendro_data(diana_senza_tetto_relative))

Calcoliamo al solito la silhouette, per \(k=5\).


senza_tetto_relative$diana_k_5 = cutree(diana_senza_tetto_relative, k=5)

sil_diana_senza_tetto <- silhouette(senza_tetto_relative$diana_k_5, dist(senza_tetto_relative[1:4]))

summary(sil_diana_senza_tetto)
Silhouette of 22 units in 5 clusters from silhouette.default(x = senza_tetto_relative$diana_k_5, dist = dist(senza_tetto_relative[1:4])) :
 Cluster sizes and average silhouette widths:
        8         9         3         1         1 
0.4142725 0.5059859 0.3994374 0.0000000 0.0000000 
Individual silhouette widths:
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.0000  0.4163  0.4618  0.4121  0.5146  0.6255 

Confrontiamo con un metodo non gerarchico, \(k\)-means.

senza_tetto_relative$kmeans <- kmeans(senza_tetto_relative, 5)$cluster

summary(silhouette(senza_tetto_relative$kmeans,dist(senza_tetto_relative[1:4]) ))
Silhouette of 22 units in 5 clusters from silhouette.default(x = senza_tetto_relative$kmeans, dist = dist(senza_tetto_relative[1:4])) :
 Cluster sizes and average silhouette widths:
        1         8         9         3         1 
0.0000000 0.4142725 0.5059859 0.3994374 0.0000000 
Individual silhouette widths:
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
 0.0000  0.4163  0.4618  0.4121  0.5146  0.6255 

Confrontiamo i plot trovati con una tabella di contingenza.

table(data.frame("kmeans"= factor(senza_tetto_relative$kmeans), "agnes"=factor(senza_tetto_relative$agnes_k_5)))
      agnes
kmeans 1 2 3 4 5
     1 0 0 0 0 1
     2 8 0 0 0 0
     3 0 9 0 0 0
     4 0 0 3 0 0
     5 0 0 0 1 0

Esercizi

  1. Generare una tabella di 3 colonne e 120 righe, in modo tale che la terza colonna indichi l’appartenenza ad un cluster, e sia pari a 1 per le prime 50 righe e pari a 2 per le ultime 70 righe. Implementare il calcolo diretto della silhouette dell’individuo corrispondente alla prima riga, usando come distanza tra individui la distanza euclidea tra i punti le cui coordinate sono i fattori degli individui.

  2. Generare una tabella in modo che la silhouette ottenuta come risultato di una analisi di clustering mostri la pessima attribuzione di un individuo.

  3. Generare una tabella in modo che la silhouette ottenuta come risultato di una analisi di clustering mostri il pessimo punteggio di un cluster.

  4. Generare un campione i cui individui siano caratterizzati da 6 diverse caratteristiche, e tali che in una analisi di clustering tipo pam la scelta di un numero di cluster inferiore a 4 non risulti buona. Implementare anche l’analisi della bontà del metodo.

  5. Svolgere una analisi di clustering sul dataset USArrests utilizzando il metodo partition around medoids con distanza manhattan.

  6. Analizzare il problema del clustering sul dataset USArrests utilizzando metodi gerarchici.

  7. Analizzare il problema del clustering sul dataset iris utilizzando metodi gerarchici, valutando i differenti casi ottenuti al variare delle possibili distanze tra punti e tra cluster.

  8. Analizzare il problema del clustering sul dataset votes.repub utilizzando metodi gerarchici, valutando i differenti casi ottenuti al variare delle possibili distanze tra punti e tra cluster.

  9. Analizzare il problema del clustering per il dataset agriculture (presente nel pacchetto cluster), relativo a dati su PIL e percentuale di impiegati nell’agricoltura nei paesi UE nel 1993.

  10. Analizzare il problema del clustering per il dataset flower (presente nel pacchetto cluster), relativo a otto caratteristiche di alcuni fiori.

  11. Analizzare il problema del clustering per il dataset UScereals.

LS0tCnRpdGxlOiAiQ2x1c3RlcmluZyAobm90ZWJvb2sgMikiCmF1dGhvcjogIkRhcmlvIFRyZXZpc2FuIgpkYXRlOiAiMDEvMTAvMjAyNSIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogJzMnCiAgICBkZl9wcmludDogcGFnZWQKICBodG1sX25vdGVib29rOgogICAgdG9jOiB0cnVlCiAgICB0b2NfZGVwdGg6IDMKICAgIHRvY19mbG9hdDogdHJ1ZQogICAgdGhlbWU6IHJlYWRhYmxlCiAgICBkZl9wcmludDogcGFnZWQKICAgIGRvd25sb2FkX2hhbmRsZXI6IHRydWUKc3VidGl0bGU6ICJTdGF0aXN0aWNhIElJIC0gNzUwQUEiCi0tLQoKIyBEYXRhc2V0cwoKTGF2b3JlcmVtbyBjb24gdW4gZGF0YXNldCBjcmVhdG8gYXBwb3NpdGFtZW50ZSwgdW5vIGludmVjZSBnacOgIGNhcmljYXRvIGluIFIgKGFkIGVzZW1waW8gYGBDaGlja1dlaWdodHNgYCkgZSB1bm8gZGkgZGF0aSByZWFsaSAoY2Vuc2ltZW50byBkaSBwZXJzb25lIHNlbnphIHRldHRvIHBlciByZWdpb25pIGl0YWxpYW5lIGRhbGwnSVNUQVQpLgoKIyMjIERhdGFzZXQgcHNldWRvLWNhc3VhbGUKClBlciBnZW5lcmFyZSBpbCBkYXRhc2V0LCB1c2lhbW8gaWwgY29tYW5kIGBgcm5vcm0oKWBgLgoKYGBge3J9CiMgUG9zc2lhbW8gaW1wb3J0YXJlIHVuIHNlZWQgcGVyIGxhIHJpcHJvZHVjaWJpbGl0w6AsIGFsdHJpbWVudGkgb2dudW5vIGF2csOgIHVuIGRhdGFzZXQgbGVnZ2VybWVudGUgZGl2ZXJzbwojIHNldC5zZWVkKDQyKQoKIyBHZW5lcmF6aW9uZSBkaSBkYXRpIGZpdHRpemkgY29uIDIwMCBvc3NlcnZhem9uaSwgCm4gPC0gMTAwCngxIDwtIHJub3JtKG4sIG1lYW4gPSA1LCBzZCA9IDEpCnkxIDwtIHJub3JtKG4sIG1lYW4gPSA1LCBzZCA9IDEpCngyIDwtIHJub3JtKG4sIG1lYW4gPSA4LCBzZCA9IDEpCnkyIDwtIHJub3JtKG4sIG1lYW4gPSA4LCBzZCA9IDEpCgoKIyBDcmVpYW1vIHVuIGRhdGFmcmFtZSwgaW5jbHVkaWFtbyBhbmNoZSBpbCBncnVwcG8gKG5vbiB1c2VyZW1vIHBlciBpbCBjbHVzdGVyaW5nKQpkYXRhX3JhbmRvbSA8LSBkYXRhLmZyYW1lKAogIHggPSBjKHgxLCB4MiksCiAgeSA9IGMoeTEsIHkyKSwKICBncm91cCA9IGZhY3RvcihyZXAoMToyLCBlYWNoID0gbikpCikKYGBgCgpWaXN1YWxpenppYW1vIGkgZGF0aSBnZW5lcmF0aSBjb24gaWwgY29tYW5kbyBgYHBsb3QoKWBgIGRpIGJhc2Ugb3BwdXJlIHVzYW5kbyBnZ3Bsb3QyLgoKYGBge3J9CiMgcGxvdCBkaSBiYXNlCnBsb3QoZGF0YV9yYW5kb20keCwgZGF0YV9yYW5kb20keSwgY29sPWRhdGFfcmFuZG9tJGdyb3VwKQoKIyB1c2FuZG8gZ2dwbG90CgpsaWJyYXJ5KCJnZ3Bsb3QyIikKCmdncGxvdChkYXRhX3JhbmRvbSwgYWVzKHgsIHksIGNvbG9yID0gZ3JvdXApKSArCiAgZ2VvbV9wb2ludCgpICsKICBsYWJzKHRpdGxlID0gIkRhdGFzZXQgZ2VuZXJhdG8iLCB4ID0gIlgiLCB5ID0gIlkiKQpgYGAKCiMjIyBEYXRhc2V0IENoaWNrV2VpZ2h0CgpRdWVzdG8gZGF0YXNldCBgYENoaWNrV2VpZ2h0YGAgKGNlcmNhcmUgc3VsbCdoZWxwKSBjb250aWVuZSBpbmZvcm1hemlvbmkgcmVsYXRpdmUgYWxsYSBjcmVzY2l0YSBkaSBwb2xsaSBjb24gZGl2ZXJzZSBkaWV0ZS4gSWwgY2x1c3RlcmluZyBwZXJtZXR0ZSBkaSBlc3Bsb3JhcmUgaSBkYXRpIGFkIGVzZW1waW8gaW5kaXZpZHVhbmRvIGR1ZSAobyBwacO5KSBjYXRlZ29yaWUgZGkgZGlldGUgaW4gYmFzZSBhbGwnZWZmZXR0byBzdWxsYSBjcmVzY2l0YS4KCgpgYGB7cn0KaGVhZChDaGlja1dlaWdodCkKYGBgCk5vdGlhbW8gcGVyw7IgY2hlIMOoIHByZXNlbnRlIHVuYSBjb2xvbm5hIF9UaW1lXyBpbiBjdWkgw6ggcmVnaXN0cmF0byBpbCB0ZW1wbyBkYWxsYSBjcmVzY2l0YSBkZWxsJ2luZGl2aWR1byBjb2xvbm5hIF9DaGlja18uIFBlciBhcHBsaWNhcmUgaWwgY2x1c3RlcmluZyAgdm9yZW1tbyBpbnZlY2UgYXZlcmUgc29sbyB1bmEgcmlnYSBwZXIgaW5kaXZpZHVvIGNvbnRlbmVudGUgaSBwZXNpIG5laSB2YXJpIGdpb3JuaSAoMCwgMiwgNCwgNiwgZWNjLikuIFF1ZXN0byBhY2NhZGUgc3Blc3NvIGNvbiBkYXRpIHJlYWxpOiBub24gc29ubyBzdHJ1dHR1cmF0aSBjb21lIHZvcnJlbW1vIChwZXJjaMOpIHJhY2NvbHRpIGRhIGFsdHJpLCBhZCBlc2VtcGlvIGNvbiBhbHRyaSBzY29waSkuIFBlciBfcmlwdWxpcmVfIGkgZGF0aSwgcG9zc2lhbW8gdXNhcmUgaWwgcGFjY2hldHRvIGBgdGlkeXJgYCBkZWxsYSBzdWl0ZSBgYHRpZHl2ZXJzZWBgICg8aHR0cHM6Ly93d3cudGlkeXZlcnNlLm9yZy8+KS4gUXVlc3RvIGZvZ2xpbyBkZXNjcml2ZSBicmV2ZW1lbnRlIGFsY3VuaSBjb21hbmRpIHByaW5jaXBhbGk6IDxodHRwczovL2xlYWRvdXNzZXQuZ2l0aHViLmlvL2ludHJvLXRvLVIvY2hlYXRzaGVldF90aWR5LnBkZj4KCgpgYGB7cn0KIyBkYXJlIGlsIGNvbWFuZG8gaW5zdGFsbC5wYWNrYWdlcygidGlkeXZlcnNlIikgc2Ugbm9uIMOoIGdpw6AgaW5zdGFsbGF0bwpsaWJyYXJ5KCJ0aWR5ciIpCmBgYAoKTmVsIG5vc3RybyBjYXNvIHZvZ2xpYW1vIF9hbGxhcmdhcmVfIGlsIGRhdGEgZnJhbWUgaW4gbW9kbyBjaGUgYWJiaWEgcGnDuSBjb2xvbm5lICh1bmEgcGVyIGNpYXNjdW5hIGV0w6ApLiBVc2lhbW8gcXVpbmRpIGlsIGNvbWFuZG8gYGBwaXZvdF93aWRlcigpYGAuCgoKYGBge3J9CmNoaWNrX3RpZHkgPC0gcGl2b3Rfd2lkZXIoZGF0YT1DaGlja1dlaWdodCwgbmFtZXNfZnJvbSA9IFRpbWUsIHZhbHVlc19mcm9tID0gd2VpZ2h0KQpgYGAKClZpc3VhbGl6emlhbW8gbGEgdGFiZWxsYSBfcmlwdWxpdGFfLgoKYGBge3J9CmNoaWNrX3RpZHkKYGBgCgpOb3RpYW1vIGNoZSBjaSBzb25vIGRlaSB2YWxvcmkgbWFuY2FudGkgYGBOQWBgLiBRdWVzdG8gYWNjYWRlIHNwZXNzbyBjb24gZGF0aSByZWFsaSBlIGJpc29nbmEgdGVuZXJuZSBjb250by4gTCdhcHByb2NjaW8gcGnDuSBzZW1wbGljZSDDqCBkaSByaW11b3ZlcmUgY29tcGxldGFtZW50ZSBsZSByaWdoZSBwZXIgY3VpIGFsbWVubyB1bmEgb3NzZXJ2YXppb25lIMOoIG1hbmNhbnRlLiBJbiBgYHRpZHlyYGAgZXNpc3RlIGlsIGNvbWFuZG8gYGBkcm9wX25hKClgYCBjaGUgZmEgYXBwdW50byBxdWVzdG8uCgpgYGB7cn0KY2hpY2tfdGlkeSA8LSBkcm9wX25hKGNoaWNrX3RpZHkpCgpjaGlja190aWR5CgpgYGAKTGUgcmlnaGUgY29uIGFsbWVubyB1biBkYXRvIG1hbmNhbnRlIHNvbm8gc3RhdGUgcmltb3NzZS4gQXR0ZW56aW9uZSBwZXLDsiBhbCByaXNjaGlvIGRpIGNhZGVyZSBpbiBlcnJvcmkgbG9naWNpIGNvbWUgaWwgW1N1cnZpdm9yc2hpcCBiaWFzXShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9TdXJ2aXZvcnNoaXBfYmlhcykgb3BwdXJlIGlsIFtjaGVycnkgcGlja2luZ10oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvQ2hlcnJ5X3BpY2tpbmcpOiByaW11b3ZlbmRvIHVuYSBwb3J6aW9uZSBkaSBkYXRpIHJpbGV2YW50aSBhbCBwcm9ibGVtYSwgc2kgcG90cmViYmVybyB0cmFycmUgY29uY2x1c2lvbmkgZGVsIHR1dHRvIGVycmF0ZS4gQWQgZXNlbXBpbywgaSBwb2xsaSBjaGUgY3Jlc2Nvbm8gZGkgcGnDuSBncmF6aWUgYWQgdW5hIHBhcnRpY29sYXJlIGRpZXRhICAgdmVuZ29ubyB1Y2Npc2kgdW5hIHNldHRpbWFuYSBwcmltYSBlIHF1aW5kaSBub24gc2kgcmVnaXN0cmEgaWwgcGVzbyBkZWxsJ3VsdGltYSBzZXR0aW1hbmEuIFNlIGZvc3NlIGNvc8OsLCByaW11b3ZlbmRvIGkgdmFsb3JpIGBgTkFgYCBzaSByaW11b3ZlIHByb3ByaW8gaWwgc2VnbmFsZSBjaGUgc2kgc3RhIGNlcmNhbmRvISAKIAojIyMgRGF0YXNldCBzZW56YXRldHRvCgpDYXJpY2hpYW1vIGluZmluZSB1biBkYXRhc2V0IHJlYWxlLCBwcm92ZW5pZW50ZSBkYWxsJ0lzdGl0dXRvIG5hemlvbmFsZSBkaSBzdGF0aXN0aWNhIChJU1RBVCksIHJlbGF0aXZvIGFsIG51bWVybyBkaSBwZXJzb25lIHNlbnphIHRldHRvIGUgc2VuemEgZmlzc2EgZGltb3JhIHBlciByZWdpb25lLCBhbm5vIDIwMjEuIEkgZGF0aSBzb25vIHNjYXJpY2F0aSBkYWxsYSBwYWdpbmEgPGh0dHBzOi8vZXNwbG9yYWRhdGkuaXN0YXQuaXQvZGF0YWJyb3dzZXIvIy9pdC9jZW5zcG9wL2NhdGVnb3JpZXMvRENTU19TRU5aQV9URVRUT19UVi9JVDEsREZfRENTU19TRU5aQV9URVRUT19UVl8xLDEuMD4gbWEgc2kgdHJvdmFubyBhbmNoZSBzdWwgdGVhbSBvIGlsIHNpdG8gZGVsIGNvcnNvLiAKCkkgZGF0aSBwb3Nzb25vIGVzc2VyZSBzYWx2YXRpIGluIHZhcmkgZm9ybWF0aSwgaWwgcGnDuSBjb211bmUgZSBzdGFuZGFyZCDDqCBpbCBmb3JtYXRvIGBgLmNzdmBgKCpjb21tYS1zZXBhcmF0ZWQgdmFsdWVzKikgaW4gY3VpIChlY2NldHRvIGFsIHBpw7kgcXVhbGNoZSByaWdhIGRpIGNvbW1lbnRvIGluaXppYXJlKSwgaSBkYXRpIHNvbm8gc2NyaXR0aSBpbiB0ZXN0byBzZW1wbGljZSwgY2lhc2N1bmEgcmlnYSByZWxhdGl2YSBhZCB1bmEgcmlnYSBkZWwgZGF0YSBmcmFtZSBlIGxlIGNvbG9ubmUgc2VwYXJhdGUgZGFsbGEgdmlyZ29sYSAoKmNvbW1hKiBpbiBpbmdsZXNlKS4gIElsIGNvbWFuZG8gZGkgYmFzZSBwZXIgbGVnZ2VyZSBpIGZpbGUgaW4gcXVlc3RvIGZvcm1hdG8gw6ggYGByZWFkLmNzdigpYGAsIG1ldHRlbmRvIGNvbWUgYXJnb21lbnRvIHVuYSBzdHJpbmdhIGNvbiBpbCBub21lIGRlbCBmaWxlIChldmVudHVhbG1lbnRlIG5lbGxlIHNvdHRvY2FydGVsbGUgZGVsIHByb2dldHRvKS4KCmBgYHtyfQojIGRvcG8gYXZlciBzY2FyaWNhdG8gaWwgZmlsZSBzZW56YV90ZXR0b19pdGFsaWEuY3N2IGUgYXZlcmxvIGNvcGlhdG8gaW4gdW5hIHNvdHRvY2FydGVsbGEgZGVsIHByb2dldHRvIGNoaWFtYXRhIGRhdGFzZXRzLCBjYXJpY2hpYW1vIGlsIGZpbGUKCnNlbnphX3RldHRvX2NhcmljYXRvIDwtIHJlYWQuY3N2KCJkYXRhc2V0cy9zZW56YV90ZXR0b19pdGFsaWEuY3N2IikKCmhlYWQoc2VuemFfdGV0dG9fY2FyaWNhdG8pCgpgYGAKCkFuY2hlIGluIHF1ZXN0byBjYXNvIHZlZGlhbW8gY2hlIGkgZGF0aSB2YW5ubyBfcmlwdWxpdGlfLCBzZWxlemlvbmFuZG8gc29sbyBsZSBjb2xvbm5lIGRpIGludGVyZXNzZSBlZCBldmVudHVhbG1lbnRlIGFsbGFyZ2FuZG8gbGUgcmlnaGUgcGVyIGxlIGNsYXNzaSBkaSBldMOgLiAKCgojIyMjIERpZ3Jlc3Npb25lIHN1IGlucHV0L291dHB1dCBkaSBkYXRpCgoKTm90aWFtbyBpbnRhbnRvIGNoZSBsJ3VzbyBkZWxsYSB2aXJnb2xhIHBvdHJlYmJlIGVzc2VyZSB1biBwcm9ibGVtYSBjb24gaSBkZWNpbWFsaTogaW4gaW5nbGVzZSBzaSB1c2EgaW52ZWNlIGlsIHB1bnRvICRccGk9IDMuMTQxNS4uJCwgbWVudHJlIGluIGl0YWxpYW5vIGUgW2FsdHJlIGxpbmd1ZV0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvRGVjaW1hbF9zZXBhcmF0b3IjL21lZGlhL0ZpbGU6RGVjaW1hbFNlcGFyYXRvci5zdmcpIHBvdHJlYmJlIGNyZWFyZSBsZXR0dXJlIHNiYWdsaWF0ZS4gUGVyIHF1ZXN0byBjaSBzb25vIGFuY2hlIGZvcm1hdGkgYWx0ZXJuYXRpdmksIGNvbWUgaWwgYGAudHN2YGAgKCp0YWItc2VwYXJhdGVkIHZhbHVlcyopIGluIGN1aSBzaSB1c2EgdW5hIHNwYXppYXR1cmEgYGB0YWJgYCBwZXIgc2VwYXJhcmUgaSB2YWxvcmkuIElsIGNvbWFuZG8gZGl2ZW50YSBhbGxvcmEgYGByZWFkLnRzdigpYGAKCkFsdHJhIGNvc2EgaW52ZWNlIHNvbm8gaSBmb3JtYXRpIGRpIEV4Y2VsIGNoZSBzb25vIHByb3ByaWV0YXJpIGNvbnRlbmdvbm8gbW9sdGUgcGnDuSBpbmZvcm1hemlvbmksIGFuY2hlIGNpcmNhIGxhIHN0b3JpYSBkZWxsZSBvcGVyYXppb25pIGNoZSBzb25vIHN0YXRlIGVmZmV0dHVhdGUgc3VpIGRhdGkgKGFkIGVzZW1waW8sIHVuIGNhc28gZGkgZGF0aSBfbWFub21lc3NpXyDDqCBzdGF0byBhcHB1bnRvIHNvbGxldmF0byBwcm9wcmlvIHN0dWRpYW5kbyBsZSBvcGVyYXppb25pIGVmZmV0dHVhdGUgc3VsbCdFeGNlbCBmb3JuaXRvIGRhIHVuIGdydXBwbyBkaSBhdXRvcmkgPGh0dHBzOi8vZGF0YWNvbGFkYS5vcmcvMTA5PikuIElsIHBhY2NoZXR0byBzdGFuZGFyZCBkZWRpY2F0byBhbGwnaW5wdXQgZGkgZGF0aSBkYSBFeGNlbCBpbiBSIMOoIGBgcmVhZHhsYC4gU2UgcHJlZmVyaXRlIHVzYXJlIGwnaW50ZXJmYWNjaWEgZ3JhZmljYSBkaSBSU3R1ZGlvLCBuZWwgdGFiIF9FbnZpcm9ubWVudF8gdHJvdmF0ZSBpbCBib3R0b25lIF9JbXBvcnQgRGF0YXNldF8gY2hlIHBlcm1ldHRlIGRpIGltcG9ydGFyZSBkYSBjc3YsIEV4Y2VsIGUgYW5jaGUgZmFyZSBkZWxsZSBwcmltZSBvcGVyYXppb25pIHN1bCBkYXRhIGZyYW1lIGNoZSB2ZXJyw6AgYXNzZWduYXRvLgoKUGVyIGdlc3RpcmUgaW4gbW9kbyBwacO5IHNlbXBsaWNlIGwnaW5wdXQgZGkgZGF0aSBkYSB2YXJpIGZvcm1hdGksIHBlcnNvbmFsbWVudGUgY29uc2lnbGlvIGlsIHBhY2NoZXR0byBgYHJpb2BgIGNoZSBoYSBxdWFsY2hlIGZ1bnppb25hbGl0w6AgYXV0b21hdGl6emF0YSBwZXIgbCdpbnB1dCAoY29tYW5kbyBgYGltcG9ydCgpYGApIGUgbCdvdXRwdXQgKGNvbWFuZG8gYGBleHBvcnRgYCkuCgpgYGB7cn0KIyBwZXIgaW5zdGFsbGFyZSByaW8gdXNhcmUgaWwgY29tYW5kbyBpbnN0YWxsLnBhY2thZ2VzKCJyaW8iKQpsaWJyYXJ5KCJyaW8iKQoKIyBlc3BvcnRpYW1vIGlsIGRhdGFzZXQgZGVpIHBvbGxpIHJpcHVsaXRvIGluIGZvcm1hdG8gZXhjZWwgc2VtcGxpY2VtZW50ZSBkYW5kbyBsJ2VzdGVuc2lvbmUgLnhsc3ggYWwgbm9tZSBkZWwgZmlsZQoKZXhwb3J0KGNoaWNrX3RpZHksICJkYXRhc2V0cy9wb2xsaV9wdWxpdGkueGxzeCIpCgojIHNlIG5hdmlnYXRlIG5lbGxhIHNvdHRvY2FydGVsbGEgZGF0YXNldHMgdHJvdmlhbW8gaWwgZmlsZSBzYWx2YXRvLiBQb3NzaWFtbyBzYWx2YXJlIGFuY2hlIGluIGFsdHJpIGZvcm1hdGksIGRpZ2l0YW5kbyBsJ2VzdGVuc2lvbmUgY29ycmV0dGEuCgpleHBvcnQoY2hpY2tfdGlkeSwgImRhdGFzZXRzL3BvbGxpX3B1bGl0aS5jc3YiKQoKIyBjb24gaWwgY29tYW5kbyBpbXBvcnQgY2FyaWNoaWFtbyBpbnZlY2UgZGEgbW9sdGVwbGljaSBmb3JtYXRpLCBpbmNsdXNvIEV4Y2VsLgoKcG9sbGlfZXhjZWwgPC0gaW1wb3J0KCJkYXRhc2V0cy9wb2xsaV9wdWxpdGkueGxzeCIpCgpoZWFkKHBvbGxpX2V4Y2VsKQpgYGAKIyMjIyBQdWxpemlhIGRhdGFzZXQgc2VuemEgdGV0dG8KClRvcm5pYW1vIGFsIGRhdGVzZXQgc2VuemEgdGV0dG8gY2hlIGFiYmlhbW8gY2FyaWNhdG8uCgpgYGB7cn0KaGVhZChzZW56YV90ZXR0b19jYXJpY2F0bykKYGBgCgpTZWxlemlvbmlhbW8gc29sbyBsZSBjb2xvbm5lIGNvcnJpc3BvbmRlbnRpIGFsbGEgcmVnaW9uZSBfVGVycml0b3Jpb18gYWwgY29kaWNlIGRpIGV0w6AgZSBhbGxhIGZyZXF1ZW56YSByaWxldmF0YSBfT3NzZXJ2YXppb25lXy4KCmBgYHtyfQoKc2VuemFfdGV0dG9fc2VsZXppb25lIDwtIGRhdGEuZnJhbWUoICJyZWdpb25lIiA9IHNlbnphX3RldHRvX2NhcmljYXRvJFRlcnJpdG9yaW8sICJhZ2UiID0gc2VuemFfdGV0dG9fY2FyaWNhdG8kQUdFX0NMQVNTLCAiZnJlcXVlbnphIiA9IHNlbnphX3RldHRvX2NhcmljYXRvJE9zc2VydmF6aW9uZSkKCmhlYWQoc2VuemFfdGV0dG9fc2VsZXppb25lKQpgYGAKQSBxdWVzdG8gcHVudG8gdXNpYW1vIGRpIG51b3ZvIGBgcGl2b3Rfd2lkZXJgYCBwZXIgY3JlYXJlIGRlbGxlIGNvbG9ubmUgcmVsYXRpdmUgYWxsZSB2YXJpZSBldMOgLgoKYGBge3J9CnNlbnphX3RldHRvX3RpZHkgPC0gcGl2b3Rfd2lkZXIoc2VuemFfdGV0dG9fc2VsZXppb25lLCBuYW1lc19mcm9tID0gYWdlLCB2YWx1ZXNfZnJvbSA9IGZyZXF1ZW56YSkKCmhlYWQoc2VuemFfdGV0dG9fdGlkeSkKYGBgCgpQb3NzaWFtbyBhbmNoZSBzYWx2YXJlIGlsIGRhdGFzZXQgX3JpcHVsaXRvXyBuZWwgY2FzbyBjaSBzZXJ2aXNzZSBwacO5IGF2YW50aSAobyBkb3Zlc3NpbW8gY2FyaWNhcmxvLCBhZCBlc2VtcGlvIHBlciBpbCBwcm9nZXR0byBkZWxsYSBwcm9tYSBkaSBlc2FtZSkuCgpgYGB7cn0KZXhwb3J0KHNlbnphX3RldHRvX3RpZHksICJkYXRhc2V0cy9zZW56YV90ZXR0b190aWR5LmNzdiIpCmBgYAoKCgojIE1ldG9kaSBub24gZ2VyYXJjaGljaSAKCkRpc2N1dGlhbW8gcHJpbWEgaSBtZXRvZGkgZGkgY2x1c3RlcmluZyBub24gZ2VyYXJjaGljaSwgaW4gcGFydGljb2xhcmUgSy1tZWFucyBgYGttZWFucygpYGAgZSBQYXJ0aXRpb25pbmcgQXJvdW5kIE1lZG9pZHMgKGBgcGFtKClgYCBkYWxsYSBsaWJyZXJpYSBgYGNsdXN0ZXJgYCkuIAoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CiMgQ2FyaWNoaWFtbyBsYSBsaWJyZXJpYSBjbHVzdGVyCmxpYnJhcnkoY2x1c3RlcikKCiMgbW9zdHJlcmVtbyBzaWEgaSBwbG90IGRpIGJhc2UgY2hlIGkgcGxvdCBvdHRlbnV0aSBjb24gZ2dwbG90MgpsaWJyYXJ5KGdncGxvdDIpCmBgYAoKCiMjIEstbWVhbnMgY2x1c3RlcmluZwoKCgpBcHBsaWNoaWFtbyBLLW1lYW5zIGFsIGRhdGFzZXQgZ2VuZXJhdG8uIFRvZ2xpYW1vIGxhIHRlcnphIGNvbG9ubmEgKHF1ZWxsYSBjaGUgY29udGllbmUgZ2nDoCBpbCBncnVwcG8sIHBlciBjb21lIGwnYWJiaWFtbyBnZW5lcmF0bykuCgpgYGB7cn0KaGVhZChkYXRhX3JhbmRvbSkKYGBgCgpgYGB7cn0Ka21lYW5zX2RhdGFfcmFuZG9tIDwtIGttZWFucyhkYXRhX3JhbmRvbVstM10sIGNlbnRlcnMgPSAyKQoKIyBJbCByaXN1bHRhdG8gw6ggdW5hIGxpc3RhIGNvbnRlbmVudGUgdmFyaWUgaW5mb3JtYXppb25pCgprbWVhbnNfZGF0YV9yYW5kb20KYGBgCgpSaWNvcmRpYW1vIGNoZSBlcmFubyAxMDAgcHVudGkgcGVyIGdydXBwbyBlIGxlIG1lZGllIChjaGUgY2kgYXNwZXR0aWFtbyBlc3NlcmUgaSBjZW50cmkpIGVyYW5vIHJpc3BldHRpdmFtZW50ZSAkKDUsNSkkLCAkKDgsOCkkLiAgQWdnaXVuZ2lhbW8gbGEgY29sb25uYSBkZWwgY2x1c3RlciBhbCBkYXRhIGZyYW1lIG9yaWdpbmFsZS4KCmBgYHtyfQoKZGF0YV9yYW5kb20gPC0gY2JpbmQoIGRhdGFfcmFuZG9tLCAia21lYW5zIiA9ICBmYWN0b3Ioa21lYW5zX2RhdGFfcmFuZG9tJGNsdXN0ZXIgKSkKYGBgCgpQb3NzaWFtbyBjb25mcm9udGFyZSBxdWluZGkgY29uIHVuYSB0YWJlbGxhIGRpIGNvbnRpbmdlbnphIGBgdGFibGUoKWBgIGkgZHVlIGNsdXN0ZXIgKG9yaWdpbmFsZSBlIHF1ZWxsbyBkaSBrbWVhbnMpLgoKYGBge3J9CnRhYmxlKCAib3JpZ2luYWxlIiA9IGRhdGFfcmFuZG9tJGdyb3VwLCAia21lYW5zIj1kYXRhX3JhbmRvbSRrbWVhbnMpCmBgYApPdnZpYW1lbnRlIG5vbiDDqCBkZXR0byBjaGUgaWwgY2x1c3RlciBldGljaGV0dGF0byBjb24gJDEkIGRhIGstbWVhbnMgY29ycmlzcG9uZGEgY29uIGxhIGNsYXNzZSAkMSQgb3JpZ2luYWxlIQoKUG9zc2lhbW8gZmFyZSB1biBwbG90IHVzYW5kbyBjb21lIGNvbG9yZSBpbCBjbHVzdGVyIHRyb3ZhdG8gY29uIGstbWVhbnMuCgpgYGB7cn0KCnBsb3QoZGF0YV9yYW5kb20keCwgZGF0YV9yYW5kb20keSwgY29sPWRhdGFfcmFuZG9tJGttZWFucykKYGBgCgpDb24gYGBnZ3Bsb3RgYCBwb3NzaWFtbyBhc3NlZ25hcmUgbGEgZm9ybWEgZGVsIGdydXBwbyBvcmlnaW5hbGUgZSBpbCBjb2xvcmUgZGVsIGNsdXN0ZXIgdHJvdmF0byBjb24gay1tZWFucy4gUml1c2NpdGUgYSB2ZWRlcmUgaSBwdW50aSBub24gX2NsYXNzaWZpY2F0aSBjb3JyZXR0YW1lbnRlXz8KCmBgYHtyfQpnZ3Bsb3QoZGF0YSA9IGRhdGFfcmFuZG9tLCBhZXMoeD14LCB5PXksIGNvbG91ciA9IGttZWFucywgc2hhcGUgPSBncm91cCkpICsgZ2VvbV9wb2ludCgpCmBgYAoKQ29tZSBkZXRlcm1pbmFyZSAkayQ/IGwnb3V0cHV0IGRpIGstbWVhbnMgZm9ybmlzY2UgaWwgV0NTUyBwZXIgY2x1c3RlciBlIGlsIFdDU1MgdG90YWxlLgpgYGB7cn0KCmttZWFuc19kYXRhX3JhbmRvbSR3aXRoaW5zcwoKa21lYW5zX2RhdGFfcmFuZG9tJHRvdC53aXRoaW5zcwoKYGBgCgpQbG90dGlhbW8gaWwgV0NTUyBwZXIgdmFyaSB2YWxvcmkgZGkgJGskIChjZXJjYW5kbyBkaSBhcHBsaWNhcmUgaWwgY29zaWRkZXR0byBfbWV0b2RvIGVsYm93XykuCgpgYGB7cn0KCldDU1MgPC0gYygpCgpmb3IoayBpbiAyOjEwKXsKICBXQ1NTIDwtIGMoV0NTUywga21lYW5zKGRhdGFfcmFuZG9tWzE6Ml0sIGNlbnRlcnM9aykkdG90LndpdGhpbnNzKQp9CgpwbG90KDI6MTAsICBXQ1NTLCB0eXBlPSdsJywgeGxhYj0ibnVtZXJvIGRpIGNsdXN0ZXJzIiwgeWxhYj0iV0NTUyIpCgpgYGAKClByb3ZhdGUgYSByaWFwcGxpY2FyZSBpbCBibG9jY28gZGkgY29kaWNlIHNvcHJhLiBDb3NhIG5vdGF0ZT8gTCdhbGdvcml0bW8gZGkgay1tZWFucyAoZSBwdXJlIHBhbSkgw6ggaW4gcmVhbHTDoCBtb2x0byBzZW5zaWJpbGUgYWkgY2VudHJpIGluaXppYWxpLiBQZXIgcXVlc3RvIMOoIG1lZ2xpbyBhcHBsaWNhcmUgaWwgbWV0b2RvIGRpdmVyc2UgaXN0YW56ZSwgaW5kaWNhcmUgaWwgdmFsb3JlIG1lZGlvIGUgdW4gaW50ZXJ2YWxsbyBkaSBjb25maWRlbnphIChpbiBxdWVzdG8gY2FzbyBiaWxhdGVybyBhbCBsaXZlbGxvICQ5NVwlJCkuCgpgYGB7cn0KCldDU1MgPC0gZGF0YS5mcmFtZSgiayI9bnVtZXJpYygpLCAibWVhbiI9bnVtZXJpYygpLCAic2QiID1udW1lcmljKCkgKQoKbnVtZXJvX3J1bnMgPC0gMTAKCmZvcihrIGluIDI6MTApewogIHdjc3NfcnVucyA8LSBjKCkKICBmb3IgKGkgaW4gMTpudW1lcm9fcnVucyl7CiAgICB3Y3NzX3J1bnMgPC0gYyh3Y3NzX3J1bnMsICBrbWVhbnMoZGF0YV9yYW5kb21bMToyXSwgY2VudGVycz1rKSR0b3Qud2l0aGluc3MpCiAgfQogIFdDU1MgPC0gcmJpbmQoIFdDU1MsIGRhdGEuZnJhbWUoaywgbWVhbih3Y3NzX3J1bnMpLCBzZCh3Y3NzX3J1bnMpKSkKfQoKcGxvdCgyOjEwLCAgV0NTUyRtZWFuLCB0eXBlPSdsJywgeGxhYj0ibnVtZXJvIGRpIGNsdXN0ZXJzIiwgeWxhYj0iV0NTUyIsIGNvbD0icmVkIikKbGluZXMoMjoxMCwgV0NTUyRtZWFuK3F0KDAuOTc1LCBkZj1udW1lcm9fcnVucy0xKSAqIFdDU1Mkc2Qvc3FydChudW1lcm9fcnVucyksIGNvbD0iZ3JleSIpCmxpbmVzKDI6MTAsIFdDU1MkbWVhbi1xdCgwLjk3NSwgZGY9bnVtZXJvX3J1bnMtMSkgKiBXQ1NTJHNkL3NxcnQobnVtZXJvX3J1bnMpLCBjb2w9ImdyZXkiKQpgYGAKClBlciAqKmVzZXJjaXppbyoqLCBjcmVhcmUgdW4gZGF0YXNldCBpbiBjdWkgaWwgbnVtZXJvIGRpICpjbHVzdGVycyogc2lhIGRpdmVyc28gZGEgMiBlIHZlcmlmaWNhcmUgbCdhbmRhbWVudG8gZGVsIFdDU1Mgcmljb25vc2NlbmRvIHNlIHBvc3NpYmlsZSBpbCBwdW50byBkaSAqZ29taXRvKi4KCgojIyBQYXJ0aXRpb25pbmcgQXJvdW5kIE1lZG9pZHMgKFBBTSkKCkFwcGxpY2hpYW1vIG9yYSBQQU0gZSBjb25mcm9udGlhbW8gaWwgcmlzdWx0YXRvIGNvbiBrLW1lYW5zIGFsIGRhdGFzZXQgYGBjaGlja190aWR5YGAuIElsIGNvbWFuZG8gw6ggYGBwYW0oKWBgIGRhbCBwYWNjaGV0dG8gYGBjbHVzdGVyYGAuIENvbWUga21lYW5zLCBiaXNvZ25hIHNwZWNpZmljYXJlICRrJC4gVG9nbGlhbW8gbGUgcHJpbWUgZHVlIGNvbG9ubmUgKG51bWVybyBpZGVudGlmaWNhdGl2byBpbmRpdmlkdW8gZSB0aXBvIGRpIGRpZXRhKS4KCmBgYHtyfQoKcGFtX2NoaWNrIDwtIHBhbShjaGlja190aWR5Wy0oMToyKV0sIGsgPSAyKQoKcGFtX2NoaWNrCmBgYAoKUG9zc2lhbW8gYW5jaGUgaW4gcXVlc3RvIGNhc2UgYWdnaXVuZ2VyZSBpbCB2ZXR0b3JlIGRpIGNsdXN0ZXJpbmcgdHJvdmF0byBhbCBkYXRhIGZyYW1lLgoKYGBge3J9CgpjaGlja190aWR5JHBhbV9jbHVzdGVyIDwtIHBhbV9jaGljayRjbHVzdGVyaW5nCgpgYGAKCkluIHF1ZXN0byBjYXNvIG5vbiBhYmJpYW1vIGRlbGxlIGNsYXNzaSBjb24gY3VpIG5hdHVyYWxtZW50ZSBjb25mcm9udGFyZSBpbCByaXN1bHRhdG8sIHF1aW5kaSBwb3NzaWFtbyBhZCBlc2VtcGlvIGNvbmZyb250YXJlIGNvbiAkayQtbWVhbnMuCgpgYGB7cn0KCiMgcmltdW92aWFtbyBhbmNoZSBsJ3VsdGltYSBjb2xvbm5hIChjaGUgY29udGllbmUgaWwgY2x1c3RlcmluZyBkaSBwYW0pCgprbWVhbnNfY2hpY2sgPC0ga21lYW5zKGNoaWNrX3RpZHlbLWMoMSwgMiwgMTUpXSwgIDIpCgprbWVhbnNfY2hpY2sKYGBgCgpBZ2dpdW5naWFtbyBhbmNoZSBxdWVzdGkgcmlzdWx0YXRpIGFsIGRhdGEgZnJhbWUgZSBjb25mcm9udGlhbW8gY29uIHVuYSB0YWJlbGxhIGRpIGNvbnRpbmdlbnphLgoKYGBge3J9CgpjaGlja190aWR5JGttZWFuc19jbHVzdGVyIDwtIGttZWFuc19jaGljayRjbHVzdGVyCgp0YWJsZSgicGFtIj1jaGlja190aWR5JHBhbV9jbHVzdGVyLCAia21lYW5zIj1jaGlja190aWR5JGttZWFuc19jbHVzdGVyKQpgYGAKClZlZGlhbW8gY2hlIGxlIGNsYXNzaSB0cm92YXRlIHNvbm8gbW9sdG8gc2ltaWxpLiBMYSBzY2VsdGEgZGVpIG1lZG9pZCBwdcOyIGluZmx1ZW56YXJlIGkgcmlzdWx0YXRpLCBtYSBQQU0gw6ggZ2VuZXJhbG1lbnRlIHBpw7kgc3RhYmlsZSBpbiBwcmVzZW56YSBkaSBydW1vcmUuCgoKVW4gdmFudGFnZ2lvIG5vdGV2b2xlIGRpIGBgcGFtYGAgcmlzcGV0dG8gYSBrLW1lYW5zIMOoIGxhIHBvc3NpYmlsaXTDoCBkaSB1c2FyZSBtZXRyaWNoZSBkaXZlcnNlLiDDiCBwb3NzaWJpbGUgZGFyZSBjb21lIGlucHV0IGludmVjZSBkZWwgZGF0YSBmcmFtZSB1bmEgbWF0cmljZSBkaSBkaXNzaW1pbGFyaXTDoCwgb3BwdXJlIHNwZWNpZmljYXJlIGBgbWV0cmljID0gIm1hbmhhdHRhbiJgYCBwZXIgdXNhcmUgbGEgZGlzdGFuemEgJFxlbGxfMSQgKHRheGljYWIpLiAKCmBgYHtyfQoKcGFtX2NoaWNrIDwtIHBhbShjaGlja190aWR5Wy1jKDEsMiwgMTUsIDE2KV0sIGsgPSAyLCBtZXRyaWM9Im1hbmhhdHRhbiIpCgpjaGlja190aWR5JHBhbV9tYW5oYXR0YW5fY2x1c3RlciA8LSBwYW1fY2hpY2skY2x1c3RlcgoKYGBgCgpDb25mcm9udGlhbW8gaSByaXN1bHRhdGkgZGkgcGFtIGNvbiBsZSBkdWUgbWV0cmljaGUuCgpgYGB7cn0KdGFibGUoInBhbSI9Y2hpY2tfdGlkeSRwYW1fY2x1c3RlciwgInBhbV9tYW5oYXR0YW4iPWNoaWNrX3RpZHkkcGFtX21hbmhhdHRhbl9jbHVzdGVyKQoKYGBgCgpQb3NzaWFtbyBpbmZpbmUgdXNhcmUgbGEgc2lsaG91ZXR0ZSBwZXIgdmFsdXRhcmUgaSBjbHVzdGVyIHRyb3ZhdGkgKGFuY2hlIHBlciBsbyBzdGVzc28gJGskKS4gSWwgY29tYW5kbyDDqCBgYHNpbGhvdWV0dGUoKWBgIGRhbCBwYWNjaGV0dG8gYGBjbHVzdGVyYGAsIGEgY3VpIGJpc29nbmEgZGFyZSBjb21lIGlucHV0IGlsIHZldHRvcmUgZGVsIGNsdXN0ZXIgZSB1bmEgbWF0cmljZSBkaSBkaXNzaW1pbGFyaXTDoCAoYWQgZXNlbXBpbyBjYWxjb2xhdGEgY29uIGxhIGZ1bnppb25lIGBgZGlzdCgpYGApCgpgYGB7cn0Kc2lsX3BhbSA8LSBzaWxob3VldHRlKGNoaWNrX3RpZHkkcGFtX2NsdXN0ZXIsIGRpc3QoY2hpY2tfdGlkeVstYygxLDIsMTUsIDE2LCAxNyldKSkKCnNpbF9wYW1fbWFuaGF0dGFuIDwtIHNpbGhvdWV0dGUoY2hpY2tfdGlkeSRwYW1fbWFuaGF0dGFuX2NsdXN0ZXIsIGRpc3QoY2hpY2tfdGlkeVstYygxLDIsMTUsIDE2LCAxNyldKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKc2lsX2ttZWFucyA8LSBzaWxob3VldHRlKGNoaWNrX3RpZHkka21lYW5zX2NsdXN0ZXIsIGRpc3QoY2hpY2tfdGlkeVstYygxLDIsMTUsIDE2LCAxNyldKSkKYGBgCgpQb3NzaWFtbyBwbG90dGFyZSBsYSBzaWxob3VldHRlIHBlciBjaWFzY3VuIG1ldG9kbyBvIHBlciBjaWFzY3VuIGNsdXN0ZXIsIG9wcHVyZSBsaW1pdGFyY2kgYWxsYSBzaWxob3VldHRlIG1lZGlhLgoKYGBge3J9CgpwbG90KHNpbF9wYW0pCgpib3hwbG90KHNpbF9wYW1bLCAzXSkKCiMgY29uIGxhIGZ1bnppb25lIHN1bW1hcnkgb3R0ZW5pYW1vIHVuIHJpYXNzdW50byBkZWxsZSB2YXJpZSBzaWxob3VldHRlIGluIGN1aSBwb3NzaWFtbyB2aXN1YWxpenphcmUgbGEgc2lsaG91ZXR0ZSBtZWRpYQoKc3VtbWFyeShzaWxfcGFtKQoKYGBgCgpDb25mcm9udGlhbW8gbGUgdHJlIHNpbGhvdWV0dGUgbWVkaWUuCgpgYGB7cn0KCnByaW50KHBhc3RlKCJzaWxob3VldHRlIG1lZGlhIHBlciBQQU06Iiwgcm91bmQobWVhbihzaWxfcGFtWywgM10pLCA0KSkpCgpwcmludChwYXN0ZSgic2lsaG91ZXR0ZSBtZWRpYSBwZXIgUEFNIE1hbmhhdHRhbjoiLCByb3VuZCggbWVhbihzaWxfcGFtX21hbmhhdHRhblssM10pLCA0KSkpCgpwcmludChwYXN0ZSgic2lsaG91ZXR0ZSBtZWRpYSBwZXIgay1tZWFuczoiLCByb3VuZChtZWFuKHNpbF9rbWVhbnNbLDNdKSwgNCkpKQoKCmBgYApQZXIgKiplc2VyY2l6aW8qKjogY29tcGxldGF0ZSBhZ2dpdW5nZW5kbyBsYSBkZXZpYXppb25lIHN0YW5kYXJkIGRlbGxlIHNpbGhvdWV0dGUgY2FsY29sYXRlLgoKCgojIE1ldG9kaSBnZXJhcmNoaWNpCgoKIyMgQWduZXMgKGFnZ2xvbWVyYXRpdm8pCgpJbCBjb21hbmRvIGBgaGNsdXN0KClgYCBwZXJtZXR0ZSBkaSB1dGlsaXp6YXJlIGRpdmVyc2kgbWV0b2RpLiBJbiBhbHRlcm5hdGl2YSwgcG9zc2lhbW8gZXNzZXJlIHBpw7kgc3BlY2lmaWNpIGUgdXNhcmUgYGBhZ25lcygpYGAgZGVsIHBhY2NoZXR0byBgYGNsdXN0ZXJgYC4KCgpDb25zaWRlcmlhbW8gaWwgZGF0YXNldCByZWxhdGl2byBhbGxlIHBlcnNvbmUgc2VuemEgdGV0dG8gZSB1c2lhbW8gIGBgYWduZXMoKWBgLCBjaGUgZGkgYmFzZSB1c2EgaWwgbWV0b2RvIGRpIF9hdmVyYWdlIGxpbmthZ2VfIGNvbiBkaXN0YW56YSBFdWNsaWRlYSAodG9nbGlhbW8gbGEgcHJpbWEgY29sb25uYSBjaGUgY29udGllbmUgaSBub21pKS4KCmBgYHtyfQoKYWduZXNfc2VuemFfdGV0dG8gPC0gYWduZXMoc2VuemFfdGV0dG9fdGlkeVstMV0pCmBgYAoKUG9zc2lhbW8gdmlzdWFsaXp6YXJlIGlsIHJpc3VsdGF0byBjb24gaWwgZGVuZHJvZ3JhbW1hLgoKYGBge3J9CnBsb3QoYWduZXNfc2VuemFfdGV0dG8pCmBgYApQZXIgdmlzdWFsaXp6YXJlIGlsIHBsb3QgcG9zc2lhbW8gdXNhcmUgcHJpbWEgY29sb25uYSBjb21lIG5vbWUgZGVsbGUgcmlnaGUgZGVsIGRhdGEgZnJhbWUgZSB1c2FyZSBgYGdnZGVuZHJvYGAoZXN0ZW5zaW9uZSBkaSBgYGdncGxvdDJgYCkuCgpgYGB7cn0Kc2VuemFfdGV0dG9fbGFiZWxzIDwtIGFzLmRhdGEuZnJhbWUoc2VuemFfdGV0dG9fdGlkeVstMV0pCnJvd25hbWVzKHNlbnphX3RldHRvX2xhYmVscykgPC0gc2VuemFfdGV0dG9fdGlkeSRyZWdpb25lCgojZ2dkZW5kcm8gcGVybWV0dGUgZGkgdmlzdWFsaXp6YXJlIG1lZ2xpbyBpIGRlbmRyb2dyYW1taSB1c2FuZG8gbGEgZ3JhbW1hdGljYSBkaSBnZ3Bsb3QyCgpsaWJyYXJ5KCJnZ2RlbmRybyIpCgpkZyA8LSBkZW5kcm9fZGF0YShhZ25lcyhzZW56YV90ZXR0b19sYWJlbHMpKQoKZ2dkZW5kcm9ncmFtKGRnKQoKYGBgCgpVbmEgb3NzZXJ2YXppb25lIF9pbXBvcnRhbnRlXyBzdWkgZGF0aTogc3RpYW1vIGNvbmZyb250YW5kbyBsZSBmcmVxdWVuemUgYXNzb2x1dGUgZGVpIHNlbnphIHRldHRvLCBxdWluZGkgw6ggbmF0dXJhbGUgY2hlIGxlIHJlZ2lvbmkgcGnDuSBwb3BvbG9zZSBhdnJhbm5vIHBpw7kgcGVyc29uZSBzZW56YSBmaXNzYSBkaW1vcmEgKHN0aWFtbyBxdWluZGkgaW1wbGljaXRhbWVudGUgZmFjZW5kbyBjbHVzdGVyaW5nIGluIGJhc2UgYWxsYSBwb3BvbGF6aW9uZSB0b3RhbGUgbmVsbGEgcmVnaW9uZSkuIAoKKipFc2VyY2l6aW8qKjogcmVjdXBlcmFyZSBkYWwgc2l0byBJU1RBVCBpbCBudW1lcm8gZGkgYWJpdGFudGkgcGVyIHJlZ2lvbmUgZWQgZXNlZ3VpcmUgdW4gY2x1c3RlcmluZyB1c2FuZG8gbGEgZnJlcXVlbnphIHJlbGF0aXZhIGRlaSBzZW56YSB0ZXR0byBzdWxsYSBwb3BvbGF6aW9uZSB0b3RhbGUuIENvbmZyb250YXJlIGkgZGVuZHJvZ3JhbW1pIG90dGVudXRpLgoKUGVyIG92dmlhcmUgYSBxdWVzdG8gcHJvYmxlbWEsIGVmZnV0dGlhbW8gY2x1c3RlcmluZyBzb2x0YW50byBzdWxsYSBmcmVxdWVuemEgX3JlbGF0aXZhXyBkZWxsYSBwb3BvbGF6aW9uZSBuZWxsZSB2YXJpZSBjbGFzc2kgZGkgZXTDoC4KCmBgYHtyfQpzZW56YV90ZXR0b19yZWxhdGl2ZSA8LSBkYXRhLmZyYW1lKCBzZW56YV90ZXR0b19sYWJlbHNbMTo0XS9zZW56YV90ZXR0b19sYWJlbHNbLDVdKQoKYWduZXNfc2VuemFfdGV0dG9fcmVsYXRpdmUgPC0gYWduZXMoc2VuemFfdGV0dG9fcmVsYXRpdmUpCgpnZ2RlbmRyb2dyYW0oZGVuZHJvX2RhdGEoYWduZXNfc2VuemFfdGV0dG9fcmVsYXRpdmUpKQoKYGBgCgoKVG9ybmFuZG8gYWwgcHJvYmxlbWEsIGlsIGNvbWFuZG8gYGBjdXRyZWUoKWBgIHBlcm1ldHRlIGRpIHJpY2F2YXJlIGlsIHZlcm8gZSBwcm9wcmlvIGNsdXN0ZXJpbmcgX3RhZ2xpYW5kb18gaWwgZGVuZHJvZ3JhbW1hOiBzaSBwdcOyIHNwZWNpZmljYXJlIGwnYWx0ZXp6YSBvIGlsIG51bWVybyBkaSBjbHVzdGVyIGRlc2lkZXJhdGkuIENvbnNpZGVyaWFtbyBhZCBlc2VtcGlvICRrPTUkIGNsdXN0ZXJzLgoKYGBge3J9CgpzZW56YV90ZXR0b19yZWxhdGl2ZSRhZ25lc19rXzUgPC0gY3V0cmVlKGFnbmVzX3NlbnphX3RldHRvX3JlbGF0aXZlLCBrPTUpCgpgYGAKClN0dWRpYW1vIGxhIHNpbGhvdWV0dGU6IG5vdGlhbW8gdW4gdmFsb3JlIG1lZGlvIG5vbiBtb2x0byBhbHRvLgoKYGBge3J9CnNpbF9hZ25lc19zZW56YV90ZXR0byA8LSBzaWxob3VldHRlKHNlbnphX3RldHRvX3JlbGF0aXZlJGFnbmVzX2tfNSwgZGlzdChzZW56YV90ZXR0b19yZWxhdGl2ZVsxOjRdKSkKCnN1bW1hcnkoc2lsX2FnbmVzX3NlbnphX3RldHRvKQpgYGAKCiMjIERpYW5hIChkaXZpc2l2bykgCgpDb24gaWwgY29tYW5kbyBgYGRpYW5hKClgYCBhcHBsaWNoaWFtbyBpbCBtZXRvZG8gZGl2aXNpdm8uIFZlZGlhbW8gY2hlIG5vbiBjaSBzb25vIGdyYW5kaSBkaWZmZXJlbnplLgoKYGBge3J9CgpkaWFuYV9zZW56YV90ZXR0b19yZWxhdGl2ZSA8LSBkaWFuYShzZW56YV90ZXR0b19yZWxhdGl2ZSkKCmdnZGVuZHJvZ3JhbShkZW5kcm9fZGF0YShkaWFuYV9zZW56YV90ZXR0b19yZWxhdGl2ZSkpCgpgYGAKCkNhbGNvbGlhbW8gYWwgc29saXRvIGxhIHNpbGhvdWV0dGUsIHBlciAkaz01JC4KCmBgYHtyfQoKc2VuemFfdGV0dG9fcmVsYXRpdmUkZGlhbmFfa181ID0gY3V0cmVlKGRpYW5hX3NlbnphX3RldHRvX3JlbGF0aXZlLCBrPTUpCgpzaWxfZGlhbmFfc2VuemFfdGV0dG8gPC0gc2lsaG91ZXR0ZShzZW56YV90ZXR0b19yZWxhdGl2ZSRkaWFuYV9rXzUsIGRpc3Qoc2VuemFfdGV0dG9fcmVsYXRpdmVbMTo0XSkpCgpzdW1tYXJ5KHNpbF9kaWFuYV9zZW56YV90ZXR0bykKCmBgYAoKQ29uZnJvbnRpYW1vIGNvbiB1biBtZXRvZG8gbm9uIGdlcmFyY2hpY28sICRrJC1tZWFucy4KCgpgYGB7cn0Kc2VuemFfdGV0dG9fcmVsYXRpdmUka21lYW5zIDwtIGttZWFucyhzZW56YV90ZXR0b19yZWxhdGl2ZSwgNSkkY2x1c3RlcgoKc3VtbWFyeShzaWxob3VldHRlKHNlbnphX3RldHRvX3JlbGF0aXZlJGttZWFucyxkaXN0KHNlbnphX3RldHRvX3JlbGF0aXZlWzE6NF0pICkpCgpgYGAKCkNvbmZyb250aWFtbyBpIHBsb3QgdHJvdmF0aSBjb24gdW5hIHRhYmVsbGEgZGkgY29udGluZ2VuemEuCgpgYGB7cn0KdGFibGUoZGF0YS5mcmFtZSgia21lYW5zIj0gZmFjdG9yKHNlbnphX3RldHRvX3JlbGF0aXZlJGttZWFucyksICJhZ25lcyI9ZmFjdG9yKHNlbnphX3RldHRvX3JlbGF0aXZlJGFnbmVzX2tfNSkpKQoKYGBgCgojIEVzZXJjaXppCgoxLiBHZW5lcmFyZSB1bmEgdGFiZWxsYSBkaSAzIGNvbG9ubmUgZSAxMjAgcmlnaGUsIGluIG1vZG8gdGFsZSBjaGUgbGEgdGVyemEgY29sb25uYSBpbmRpY2hpIGzigJlhcHBhcnRlbmVuemEgYWQgdW4gY2x1c3RlciwgZSBzaWEgcGFyaSBhIDEgcGVyIGxlIHByaW1lIDUwIHJpZ2hlIGUgcGFyaSBhIDIgcGVyIGxlIHVsdGltZSA3MCByaWdoZS4gSW1wbGVtZW50YXJlIGlsIGNhbGNvbG8gZGlyZXR0byBkZWxsYSBzaWxob3VldHRlIGRlbGzigJlpbmRpdmlkdW8gY29ycmlzcG9uZGVudGUgYWxsYSBwcmltYSByaWdhLCB1c2FuZG8gY29tZSBkaXN0YW56YSB0cmEgaW5kaXZpZHVpIGxhIGRpc3RhbnphIGV1Y2xpZGVhIHRyYSBpIHB1bnRpIGxlIGN1aSBjb29yZGluYXRlIHNvbm8gaSBmYXR0b3JpIGRlZ2xpIGluZGl2aWR1aS4KCjIuIEdlbmVyYXJlIHVuYSB0YWJlbGxhIGluIG1vZG8gY2hlIGxhIHNpbGhvdWV0dGUgb3R0ZW51dGEgY29tZSByaXN1bHRhdG8gZGkgdW5hIGFuYWxpc2kgZGkgY2x1c3RlcmluZyBtb3N0cmkgbGEgcGVzc2ltYSBhdHRyaWJ1emlvbmUgZGkgdW4gaW5kaXZpZHVvLgoKMy4gR2VuZXJhcmUgdW5hIHRhYmVsbGEgaW4gbW9kbyBjaGUgbGEgc2lsaG91ZXR0ZSBvdHRlbnV0YSBjb21lIHJpc3VsdGF0byBkaSB1bmEgYW5hbGlzaSBkaSBjbHVzdGVyaW5nIG1vc3RyaSBpbCBwZXNzaW1vIHB1bnRlZ2dpbyBkaSB1biBjbHVzdGVyLgoKNC4gR2VuZXJhcmUgdW4gY2FtcGlvbmUgaSBjdWkgaW5kaXZpZHVpIHNpYW5vIGNhcmF0dGVyaXp6YXRpIGRhIDYKZGl2ZXJzZSBjYXJhdHRlcmlzdGljaGUsIGUgdGFsaSBjaGUgaW4gdW5hIGFuYWxpc2kgZGkgY2x1c3RlcmluZyB0aXBvIHBhbSBsYSBzY2VsdGEgZGkgdW4gbnVtZXJvIGRpIGNsdXN0ZXIgaW5mZXJpb3JlIGEgNCBub24gcmlzdWx0aSBidW9uYS4gSW1wbGVtZW50YXJlIGFuY2hlIGzigJlhbmFsaXNpIGRlbGxhIGJvbnTDoCBkZWwgbWV0b2RvLgoKNS4gU3ZvbGdlcmUgdW5hIGFuYWxpc2kgZGkgY2x1c3RlcmluZyBzdWwgZGF0YXNldCBgYFVTQXJyZXN0c2BgIHV0aWxpenphbmRvIGlsIG1ldG9kbyBwYXJ0aXRpb24gYXJvdW5kIG1lZG9pZHMgY29uIGRpc3RhbnphIG1hbmhhdHRhbi4KCjYuIEFuYWxpenphcmUgaWwgcHJvYmxlbWEgZGVsIGNsdXN0ZXJpbmcgc3VsIGRhdGFzZXQgYGBVU0FycmVzdHNgYCB1dGlsaXp6YW5kbyBtZXRvZGkgZ2VyYXJjaGljaS4KCjcuIEFuYWxpenphcmUgaWwgcHJvYmxlbWEgZGVsIGNsdXN0ZXJpbmcgc3VsIGRhdGFzZXQgYGBpcmlzYGAgdXRpbGl6emFuZG8gbWV0b2RpIGdlcmFyY2hpY2ksIHZhbHV0YW5kbyBpIGRpZmZlcmVudGkgY2FzaSBvdHRlbnV0aSBhbCB2YXJpYXJlIGRlbGxlIHBvc3NpYmlsaSBkaXN0YW56ZSB0cmEgcHVudGkgZSB0cmEgY2x1c3Rlci4KCjguIEFuYWxpenphcmUgaWwgcHJvYmxlbWEgZGVsIGNsdXN0ZXJpbmcgc3VsIGRhdGFzZXQgYGB2b3Rlcy5yZXB1YmBgIHV0aWxpenphbmRvIG1ldG9kaSBnZXJhcmNoaWNpLCB2YWx1dGFuZG8gaSBkaWZmZXJlbnRpIGNhc2kgb3R0ZW51dGkgYWwgdmFyaWFyZSBkZWxsZSBwb3NzaWJpbGkgZGlzdGFuemUgdHJhIHB1bnRpIGUgdHJhIGNsdXN0ZXIuCgo5LiBBbmFsaXp6YXJlIGlsIHByb2JsZW1hIGRlbCBjbHVzdGVyaW5nIHBlciBpbCBkYXRhc2V0IGBgYWdyaWN1bHR1cmVgYCAocHJlc2VudGUgbmVsIHBhY2NoZXR0byBjbHVzdGVyKSwgcmVsYXRpdm8gYSBkYXRpIHN1IFBJTCBlIHBlcmNlbnR1YWxlIGRpIGltcGllZ2F0aSBuZWxs4oCZYWdyaWNvbHR1cmEgbmVpIHBhZXNpIFVFIG5lbCAxOTkzLgoKMTAuIEFuYWxpenphcmUgaWwgcHJvYmxlbWEgZGVsIGNsdXN0ZXJpbmcgcGVyIGlsIGRhdGFzZXQgYGBmbG93ZXJgYCAocHJlc2VudGUgbmVsIHBhY2NoZXR0byBjbHVzdGVyKSwgcmVsYXRpdm8gYSBvdHRvIGNhcmF0dGVyaXN0aWNoZSBkaSBhbGN1bmkgZmlvcmkuCgoxMS4gQW5hbGl6emFyZSBpbCBwcm9ibGVtYSBkZWwgY2x1c3RlcmluZyBwZXIgaWwgZGF0YXNldCBgYFVTY2VyZWFsc2BgLgo=