Clustering

Analysis & Perdictive Modeling

foto

Nama : Chello Frhino Mike Mandolang

Program Studi : Sains Data

Nama Dosen : BAKTI SIREGAR, M.Sc., CDS.

Institusi : ITSB

1 Pendahuluan

Dataset yang digunakan adalah Mall Customers Dataset dari Kaggle. Dataset ini berisi data pelanggan yang mencakup umur, pendapatan tahunan, dan skor pengeluaran. Tujuan analisis ini adalah mengelompokkan pelanggan berdasarkan kemiripan karakteristik menggunakan metode hierarchical clustering.

Relevansi clustering: membantu memahami segmentasi pelanggan untuk analisis pemasaran, penawaran personal, dan pemetaan perilaku.

2 Teori Dasar Hierarchical Clustering

Hierarchical clustering adalah metode pengelompokan yang membangun hierarki cluster. Terdiri dari dua pendekatan utama: Agglomerative (bottom-up) dan Divisive (top-down).

2.1 Definisi

  • Agglomerative: setiap titik data mulai sebagai cluster tunggal lalu digabung secara bertahap.
  • Divisive: seluruh data dianggap satu cluster lalu dipecah menjadi cluster lebih kecil.

2.2 Rumus Inti

Menggunakan distance matrix berdasarkan Euclidean distance:

\[d(x, y) = \sqrt{\sum_{i=1}^{n} (x_i - y_i)^2}\]

2.3 Linkage Methods

  • Single linkage: jarak minimum antar dua cluster.
  • Complete linkage: jarak maksimum antar dua cluster.
  • Average linkage: rata-rata jarak antar anggota cluster.
  • Ward linkage: meminimalkan total variansi dalam cluster.

2.4 Kelebihan & Kekurangan

Kelebihan: - Tidak perlu menentukan jumlah cluster di awal. - Dendrogram memudahkan interpretasi.

Kekurangan: - Komputasi lebih berat untuk dataset besar. - Sensitif terhadap noise dan outlier.

3 Sumber & Loading Data

Dataset: Mall Customers
Sumber: Kaggle (https://www.kaggle.com/datasets/shwetabh123/mall-customers)

4 Eksplorasi Data

## 'data.frame':    200 obs. of  5 variables:
##  $ CustomerID            : int  1 2 3 4 5 6 7 8 9 10 ...
##  $ Genre                 : chr  "Male" "Male" "Female" "Female" ...
##  $ Age                   : int  19 21 20 23 31 22 35 23 64 30 ...
##  $ Annual.Income..k..    : int  15 15 16 16 17 17 18 18 19 19 ...
##  $ Spending.Score..1.100.: int  39 81 6 77 40 76 6 94 3 72 ...
##    CustomerID        Genre                Age        Annual.Income..k..
##  Min.   :  1.00   Length:200         Min.   :18.00   Min.   : 15.00    
##  1st Qu.: 50.75   Class :character   1st Qu.:28.75   1st Qu.: 41.50    
##  Median :100.50   Mode  :character   Median :36.00   Median : 61.50    
##  Mean   :100.50                      Mean   :38.85   Mean   : 60.56    
##  3rd Qu.:150.25                      3rd Qu.:49.00   3rd Qu.: 78.00    
##  Max.   :200.00                      Max.   :70.00   Max.   :137.00    
##  Spending.Score..1.100.
##  Min.   : 1.00         
##  1st Qu.:34.75         
##  Median :50.00         
##  Mean   :50.20         
##  3rd Qu.:73.00         
##  Max.   :99.00

4.1 CustomerID

  • Rentang: 1 – 200
  • Mean dan median sama-sama 100.5
  • Variabel ini merupakan identifier dan tidak memiliki informasi numerik yang relevan untuk analisis.
  • Tidak digunakan dalam clustering karena tidak menggambarkan karakteristik pelanggan.

4.2 Genre (Jenis Kelamin)

  • Tipe data: karakter (Male/Female)
  • Jumlah observasi: 200
  • Variabel kategorikal ini dapat digunakan jika di-encode, tetapi dalam banyak kasus tidak memberikan kontribusi besar terhadap pemisahan klaster.
  • Penggunaan variabel ini opsional bergantung pada tujuan analisis.

4.3 Age (Usia)

  • Rentang: 18 – 70 tahun
  • Median: 36
  • Mean: 38.85
  • Distribusi usia sedikit condong ke kanan, terlihat dari mean yang sedikit lebih besar dari median.
  • Mayoritas pelanggan berada pada rentang usia 28 hingga 49 tahun (kuartil kedua dan ketiga).
  • Tidak terdapat nilai yang tampak sebagai outlier ekstrem, sehingga variabel ini stabil untuk digunakan sebagai fitur clustering.

4.4 Annual Income (Pendapatan Tahunan, dalam ribuan USD)

  • Rentang: 15 – 137
  • Median: 61.50
  • Mean: 60.56
  • Distribusi pendapatan relatif simetris karena mean hampir sama dengan median.
  • Variasi pendapatan cukup besar, menunjukkan adanya kelompok pelanggan dengan tingkat ekonomi yang berbeda-beda.
  • Variabel ini sangat relevan untuk segmentasi pelanggan berdasarkan daya beli.

4.5 Spending Score

  • Rentang: 1 – 99
  • Median: 50
  • Mean: 50.20
  • Nilai skor tersebar merata dan tidak condong ke satu sisi.
  • Variabel ini menggambarkan perilaku belanja pelanggan dan biasanya menjadi faktor utama dalam pembentukan klaster.
  • Variabel ini penting dalam memahami perbedaan tingkat konsumsi antar pelanggan.

4.6 Kesimpulan EDA

  • Semua variabel yang digunakan memiliki distribusi yang wajar dan tidak terdapat indikasi nilai ekstrem yang mengganggu analisis.
  • Variabel paling relevan untuk clustering: Age, Annual Income, dan Spending Score.
  • CustomerID tidak digunakan karena hanya berupa identitas.
  • Genre dapat digunakan tetapi bersifat opsional tergantung tujuan segmentasi.

5 Pra-Proses Data

Dataset dibersihkan dengan hanya memilih variabel numerik yang relevan untuk clustering, yaitu Age, Annual Income, dan Spending Score. Proses scaling dilakukan untuk menyeimbangkan kontribusi setiap variabel, karena hierarchical clustering sensitif terhadap perbedaan skala. Tahap ini memastikan hasil clustering lebih akurat dan stabil.

df_clean <- df %>% 
  select(Age, Annual.Income..k.., Spending.Score..1.100.)

# Scaling
scaled <- scale(df_clean)

6 Reduksi Dimensi (Opsional)

Reduksi dimensi dilakukan untuk menyederhanakan struktur data sehingga pola klaster lebih mudah diamati. Dalam analisis ini, PCA digunakan untuk mengekstraksi komponen utama yang memuat variasi terbesar pada data. Visualisasi dua komponen utama (PC1 dan PC2) memberikan gambaran awal mengenai kemungkinan pemisahan klaster. Teknik seperti t-SNE dan UMAP dapat digunakan sebagai visualisasi tambahan untuk melihat struktur lokal dan pola non-linear yang tidak dapat ditangkap oleh PCA. Meskipun demikian, PCA lebih sesuai sebagai dasar perhitungan jarak untuk hierarchical clustering karena mempertahankan struktur global data.

library(plotly)

# PCA
pca <- prcomp(df_clean, scale. = TRUE)

pca_df <- data.frame(
  CustomerID = df$CustomerID,   # ambil CustomerID agar muncul sebagai label
  PC1 = pca$x[,1],
  PC2 = pca$x[,2]
)

plot_ly(
  pca_df,
  x = ~PC1,
  y = ~PC2,
  type = "scatter",
  mode = "markers",
  text = ~paste("CustomerID:", CustomerID,
                "<br>PC1:", round(PC1, 2),
                "<br>PC2:", round(PC2, 2)),
  hoverinfo = "text"
)

Plot PCA di atas menampilkan distribusi seluruh pelanggan berdasarkan dua komponen utama, yaitu Dimensi 1 (44.3%) dan Dimensi 2 (33.3%), yang secara keseluruhan menjelaskan sekitar 77.6% variasi total data. Dengan demikian, representasi dua dimensi ini sudah cukup menggambarkan struktur data asli.

6.1 Penyebaran Data Secara Umum

Pelanggan tersebar luas di seluruh area plot tanpa adanya pemisahan cluster yang sangat jelas. Hal ini menunjukkan bahwa:

  • Variabel Age, Annual Income, dan Spending Score saling berkontribusi terhadap variasi data.
  • Pola klaster tidak langsung terlihat secara visual hanya dari PCA.
  • Clustering hierarchical diperlukan untuk mengidentifikasi struktur kelompok yang lebih teratur.

6.2 Interpretasi Dimensi 1 (Komponen Utama Pertama)

Dim1 menjelaskan 44.3% variasi data. Biasanya pada dataset ini:

  • Dim1 menangkap perbedaan terutama pada Annual Income dan Spending Score.
  • Titik-titik di sisi kanan umumnya menggambarkan pelanggan dengan pendapatan atau skor pengeluaran yang lebih tinggi.
  • Titik di sisi kiri menggambarkan pelanggan dengan pendapatan atau skor pengeluaran lebih rendah.

Artinya, pergeseran horizontal menunjukkan perbedaan daya beli dan perilaku belanja pelanggan.

6.3 Interpretasi Dimensi 2 (Komponen Utama Kedua)

Dim2 menjelaskan 33.3% variasi data. Dimensi ini kemungkinan menangkap perbedaan yang lebih dipengaruhi oleh:

  • Usia, atau
  • Kombinasi variabel lain yang tidak dominan di Dim1.

Titik yang berada lebih tinggi pada plot biasanya memiliki karakteristik berbeda dalam hal usia atau pola belanja tertentu.

6.4 Pola Distribusi

Beberapa pola utama dapat diamati:

  • Pelanggan dengan nomor ID tertentu tampak berkumpul di wilayah tengah, mengindikasikan karakteristik yang tidak terlalu ekstrem.
  • Titik-titik di bagian kanan atas (misalnya ID 195, 197, 199, 200) menunjukkan pelanggan dengan karakteristik yang berbeda cukup signifikan dari mayoritas (misalnya pendapatan tinggi atau spending score tinggi).
  • Tidak tampak pengelompokan yang sangat rapat seperti dalam dataset dengan pola klaster kuat. Ini wajar karena PCA adalah metode linear, sedangkan pola klaster Mall Customer Data biasanya lebih terlihat dengan metode non-linear seperti t-SNE atau UMAP.

6.5 Implikasi untuk Analisis Clustering

Interpretasi ini menunjukkan bahwa:

  • Data memiliki variasi yang cukup besar sehingga hierarchical clustering berpotensi mengungkap klaster yang berbeda.
  • PCA membantu memberikan gambaran awal tentang struktur data, tetapi tidak cukup untuk menentukan cluster secara visual.
  • Hasil klaster nantinya akan lebih dipengaruhi oleh kombinasi informasi numerik asli, bukan hanya plot PCA.

Plot PCA menunjukkan bahwa data pelanggan memiliki sebaran yang cukup luas dan variasi tinggi, dengan dua komponen utama yang bersama-sama menjelaskan lebih dari 75% informasi penting dalam data. Meskipun pola klaster belum tampak jelas dalam visualisasi PCA, teknik ini memberikan representasi awal yang membantu memahami arah variasi utama dalam dataset. Analisis clustering hierarchical diperlukan untuk menghasilkan pemisahan kelompok yang lebih terstruktur.

7 Hierarchical Clustering

7.1 Distance Matrix

dist_mat <- dist(scaled, method = "euclidean")

Pada langkah ini dibuat distance matrix menggunakan Euclidean distance dari data yang sudah dinormalisasi (scaled). Distance matrix berisi nilai jarak antar setiap pasangan data. Semakin kecil nilai jaraknya, semakin mirip dua observasi tersebut. Distance matrix inilah yang menjadi input utama untuk metode hierarchical clustering agglomerative.

7.2 Agglomerative (Single, Complete, Average, Ward)

hc_single <- hclust(dist_mat, method = "single")
hc_complete <- hclust(dist_mat, method = "complete")
hc_average <- hclust(dist_mat, method = "average")
hc_ward <- hclust(dist_mat, method = "ward.D2")

  1. Single Linkage

    • Menggabungkan dua cluster berdasarkan jarak terdekat antar anggota.
    • Cenderung menghasilkan bentuk cluster yang memanjang (chaining effect).
    • Sensitif terhadap outlier.

  2. Complete Linkage

    • Menggabungkan cluster berdasarkan jarak terjauh antar anggota.
    • Menghasilkan cluster yang lebih kompak dan membulat.
    • Lebih tahan terhadap chaining.

  3. Average Linkage

    • Menggunakan rata-rata jarak antar semua pasangan titik di dua cluster.
    • Merupakan kompromi antara single dan complete.
    • Memberikan cluster yang stabil dan tidak terlalu ekstrem.

  4. Ward’s Method (ward.D2)

    • Menggabungkan cluster berdasarkan minimasi variansi total dalam cluster.
    • Sering menghasilkan cluster paling jelas dan seimbang.
    • Cocok saat kita ingin cluster dengan ukuran relatif seragam.

7.3 Divisive (DIANA)

library(cluster)
diana_res <- diana(scaled)

Metode DIANA (Divisive Analysis) adalah kebalikan dari agglomerative. Alih-alih menggabungkan cluster dari bawah ke atas, DIANA:

  1. Memulai dari satu cluster besar (semua data).
  2. Kemudian memecah cluster menjadi subcluster berdasarkan perbedaan yang paling besar.
  3. Proses pemisahan terus berlangsung sampai setiap observasi menjadi cluster sendiri.

DIANA cocok untuk mendeteksi struktur data yang memiliki kelompok besar yang secara natural terpisah di awal.

8 Visualisasi Dendrogram

# ================================
# 1. Load Packages
# ================================
library(ggplot2)
library(ggdendro)
library(cluster)

# ================================
# 2. Distance Matrix
# ================================
dist_mat <- dist(scaled, method = "euclidean")

# ================================
# 3. Fit Hierarchical Models
# ================================
hc_single   <- hclust(dist_mat, method = "single")
hc_complete <- hclust(dist_mat, method = "complete")
hc_average  <- hclust(dist_mat, method = "average")
hc_ward     <- hclust(dist_mat, method = "ward.D2")

# DIANA (Divisive)
diana_res <- diana(scaled)

# ================================
# 4. Fungsi untuk Plot ggdendro
# ================================
plot_dend_gg <- function(hc_object, title = "Dendrogram") {
  dend <- as.dendrogram(hc_object)
  ggd  <- dendro_data(dend)

  ggplot() +
    geom_segment(
      data = ggd$segments,
      aes(x = x, y = y, xend = xend, yend = yend),
      linewidth = 0.4
    ) +
    geom_text(
      data = ggd$labels,
      aes(x = x, y = y, label = label),
      size = 3,
      vjust = 1
    ) +
    theme_minimal() +
    labs(title = title, x = "", y = "Height") +
    theme(
      axis.text.x = element_blank(),
      axis.ticks.x = element_blank()
    )
}

# ================================
# 5. Plot Semua Dendrogram
# ================================

# Single Linkage
plot_dend_gg(hc_single, "Single Linkage")

# Complete Linkage
plot_dend_gg(hc_complete, "Complete Linkage")

# Average Linkage
plot_dend_gg(hc_average, "Average Linkage")

# Ward Linkage
plot_dend_gg(hc_ward, "Ward Linkage")

# ================================
# 6. DIANA Dendrogram
# ================================
dend_diana  <- as.dendrogram(diana_res)
ggd_diana   <- dendro_data(dend_diana)

ggplot() +
  geom_segment(
    data = ggd_diana$segments,
    aes(x = x, y = y, xend = xend, yend = yend),
    linewidth = 0.4
  ) +
  geom_text(
    data = ggd_diana$labels,
    aes(x = x, y = y, label = label),
    size = 3,
    vjust = 1
  ) +
  theme_minimal() +
  labs(title = "DIANA (Divisive Clustering)", x = "", y = "Height") +
  theme(
    axis.text.x = element_blank(),
    axis.ticks.x = element_blank()
  )

1. Complete Linkage

Karakteristik Visual:

  • Cabang lebih rapat dan simetris dibanding single linkage.
  • Tidak terlihat chaining effect.
  • Beberapa cabang menyatu di ketinggian cukup besar, menunjukkan pemisahan klaster yang lebih stabil.

Interpretasi:

  1. Complete linkage mengukur jarak maksimum antar klaster, sehingga menghasilkan klaster yang lebih kompak dan seimbang.

  2. Klaster terbentuk lebih konsisten daripada single linkage.

  3. Terlihat beberapa “blok” besar pada ketinggian menengah—ini tanda bahwa:

    • Ada grup pelanggan yang benar-benar berbeda satu sama lain.

  4. Karena complete linkage menghindari chaining, hasilnya lebih mudah dibaca dan digunakan untuk menentukan jumlah klaster.

Kesimpulan Method:

Metode ini cocok untuk dataset Mall Customers karena menghasilkan pemisahan klaster yang lebih tegas dan stabil.

2. Average Linkage (UPGMA)

Karakteristik Visual:

  • Bentuk dendrogram lebih halus dan seimbang.
  • Tinggi penggabungan berada di tengah-tengah (antara single dan complete).
  • Klaster cukup jelas namun tidak seketat complete linkage.

Interpretasi:

  1. Average linkage menggunakan jarak rata-rata, sehingga memberikan kompromi antara Single dan Complete.

  2. Klaster terbentuk lebih natural tanpa over-fitting struktur linear seperti single linkage.

  3. Tinggi penggabungan menunjukkan:

    • Ada 3–5 klaster alami pada data (tergantung cutoff height).

  4. Cocok untuk dataset dengan distribusi variabel yang tidak terlalu ekstrem—seperti Mall Customers.

Kesimpulan Method:

Metode ini memberikan hasil yang stabil dan cukup mudah diinterpretasi, sangat cocok untuk eksplorasi awal struktur klaster.

3. Ward Linkage (Ward.D2)

Karakteristik Visual:

  • Dendrogram paling “mengotak” dan simetris.
  • Cabang besar menyatu pada ketinggian tinggi.
  • Klaster besar terlihat sangat jelas.

Interpretasi:

  1. Ward meminimalkan peningkatan variansi dalam klaster, sehingga membentuk klaster yang homogen.

  2. Hasilnya adalah struktur klaster paling jelas dibanding metode lain.

  3. Dendrogram biasanya menunjukkan lonjakan jarak besar sebelum gabungan klaster terakhir → tanda klaster kuat.

  4. Pola pada Mall Customer Data kemungkinan menunjukkan:

    • Kelompok pendapatan rendah–spending rendah
    • Kelompok pendapatan tinggi–spending rendah
    • Kelompok pendapatan tinggi–spending tinggi

  5. Ini cocok dengan distribusi variabel dalam dataset Mall Customers.

Kesimpulan Method:

Ward Linkage kemungkinan memberikan hasil terbaik untuk dataset ini. Biasanya Ward digunakan untuk rekomendasi final jumlah klaster sebelum KMeans.

4. Divisive Clustering (DIANA)

Karakteristik Visual:

  • Struktur awal memulai dari 1 klaster besar → dipisah menjadi sub-klaster.
  • Cabang paling awal merepresentasikan grup yang sangat berbeda dari sisanya.
  • Pemisahan besar muncul lebih awal daripada metode agglomerative.

Interpretasi:

  1. DIANA memulai dari seluruh data sebagai satu klaster, lalu memecah klaster yang memiliki heterogenitas tertinggi.

  2. Cabang pertama yang memisah menunjukkan kelompok pelanggan paling unik, misalnya:

    • Sangat tinggi spending namun pendapatan sedang.
    • Atau outlier tertentu.

  3. DIANA cocok untuk mendeteksi klaster yang benar-benar berbeda dari populasi umum.

  4. Klaster yang terbentuk lebih tegas di awal dan menyusut menjadi subklaster kecil.

Kesimpulan Method:

DIANA sangat baik untuk mengidentifikasi kelompok unik atau ekstrem dalam dataset. Cocok sebagai metode komplementer untuk memvalidasi struktur klaster dari Ward atau Average linkage.

Rangkuman Perbandingan

Metode Kelebihan Kekurangan Cocok untuk Mall Dataset
Single Menangkap kedekatan lokal Chaining, klaster tidak jelas Tidak cocok
Complete Klaster kompak dan stabil Bisa terlalu ketat Cocok
Average Seimbang, natural Kurang tegas dibanding Ward Cocok
Ward Klaster paling jelas & homogen Sensitif normalisasi Sangat cocok
DIANA Menemukan grup unik/outlier Lebih berat komputasinya Cocok sebagai pendukung

9 Cutting Tree & Mendapatkan Cluster

k <- 4
cl_single <- cutree(hc_single, k)
cl_complete <- cutree(hc_complete, k)
cl_average <- cutree(hc_average, k)
cl_ward <- cutree(hc_ward, k)
cl_diana <- cutree(as.hclust(diana_res), k)

Pada bagian ini dilakukan pemotongan dendrogram untuk menentukan jumlah klaster yang sesuai berdasarkan struktur hirarki yang terbentuk.

9.1 1. Menentukan Jumlah Cluster

Pemilihan jumlah klaster dilakukan dengan melihat height pada dendrogram, yaitu titik ketika jarak antar klaster meningkat tajam. Dari semua metode:

  • Ward linkage menunjukkan pemisahan cluster paling jelas.
  • Average dan Complete linkage juga cukup stabil.
  • Single linkage kurang baik karena efek chaining.
  • DIANA memisahkan kelompok yang paling berbeda terlebih dahulu.

Dari pola ini, jumlah klaster alami biasanya berada pada 3–5 klaster untuk dataset Mall Customers.

9.2 2. Pemotongan Dendrogram

Dengan menggunakan fungsi seperti cutree(), setiap observasi dikelompokkan sesuai titik pemotongan. Cluster yang terbentuk mencerminkan kelompok pelanggan dengan karakteristik mirip berdasarkan variabel seperti pendapatan dan spending score.

9.3 3. Perbandingan Metode

  • Ward menghasilkan cluster paling kompak dan mudah diinterpretasikan.
  • Average memberikan hasil seimbang.
  • Complete lebih ketat dalam menggabungkan cluster.
  • DIANA efektif dalam mengidentifikasi kelompok ekstrem.

9.4 Kesimpulan

Pemotongan dendrogram menunjukkan bahwa metode Ward linkage memberikan struktur klaster paling kuat. Jumlah klaster yang optimal berada pada kisaran 4–5 klaster, tergantung kebutuhan analisis.

10 Evaluasi Cluster

Menggunakan silhouette score dan indeks lainnya.

# ============================
# 0. Load Packages
# ============================
library(cluster)
library(factoextra)
library(fpc)
library(dplyr)
library(DT)

# ============================
# 1. Distance Matrix
# ============================
dist_mat <- dist(scaled, method = "euclidean")

# ============================
# 2. Hierarchical Clustering
# ============================
hc_single   <- hclust(dist_mat, method = "single")
hc_complete <- hclust(dist_mat, method = "complete")
hc_average  <- hclust(dist_mat, method = "average")
hc_ward     <- hclust(dist_mat, method = "ward.D2")
diana_res   <- diana(scaled)

# ============================
# 3. Tentukan jumlah cluster
# ============================
k <- 4

cl_single   <- cutree(hc_single,   k)
cl_complete <- cutree(hc_complete, k)
cl_average  <- cutree(hc_average,  k)
cl_ward     <- cutree(hc_ward,     k)
cl_diana    <- cutree(as.hclust(diana_res), k)

# ============================
# 4. Fungsi Evaluasi
# ============================
eval_cluster <- function(cluster_labels, dist_matrix, data_matrix) {
  
  # Silhouette
  sil <- silhouette(cluster_labels, dist_matrix)
  sil_avg <- mean(sil[,3])
  
  # Davies Bouldin Index (lower = better)
  dbi <- fpc::cluster.stats(dist_matrix, cluster_labels)$db
  
  # Calinski-Harabasz Index (higher = better)
  ch <- calinhara(data_matrix, cluster_labels)
  
  return(c(Silhouette = sil_avg, DBI = dbi, CH = ch))
}

# ============================
# 5. Hitung Evaluasi untuk Semua Metode
# ============================
results <- rbind(
  Single   = eval_cluster(cl_single,   dist_mat, scaled),
  Complete = eval_cluster(cl_complete, dist_mat, scaled),
  Average  = eval_cluster(cl_average,  dist_mat, scaled),
  Ward     = eval_cluster(cl_ward,     dist_mat, scaled),
  DIANA    = eval_cluster(cl_diana,    dist_mat, scaled)
)

# ============================
# 6. Tampilkan Tabel Hasil
# ============================

results_df <- as.data.frame(results)

datatable(
  round(results_df, 4),
  options = list(
    pageLength = 10,
    autoWidth = TRUE,
    dom = 'ftip'
  ),
  rownames = TRUE
)

10.1 Evaluasi Cluster (Silhouette, DBI, CH Index)

Evaluasi dilakukan untuk menilai kualitas cluster yang dihasilkan oleh setiap metode hierarchical clustering. Tiga metrik digunakan:

  • Silhouette Score Mengukur seberapa mirip suatu data dengan klusternya sendiri dibandingkan dengan kluster lain. Nilai mendekati 1 = klaster jelas; Mendekati 0 = tumpang tindih; Negatif = salah klaster.

  • Davies-Bouldin Index (DBI) Semakin kecil, semakin baik karena menunjukkan bahwa cluster semakin terpisah dan kompak.

  • Calinski–Harabasz (CH) Index Semakin besar, semakin baik. Mencerminkan perbandingan variasi antar-klaster dan dalam klaster.

10.2 Hasil Evaluasi per Metode

10.2.1 Single Linkage

  • Silhouette: biasanya rendah
  • DBI: tinggi (buruk)
  • CH: rendah
  • Interpretasi: Struktur chaining membuat cluster memanjang dan tidak kompak. Kurang baik untuk dataset Mall Customers. Jarang direkomendasikan.

10.2.2 Complete Linkage

  • Silhouette: sedang–baik
  • DBI: lebih rendah dari single
  • CH: cukup baik
  • Interpretasi: Klaster lebih stabil dan kompak dibanding single. Pemisahan antar cluster cukup tegas. Layak digunakan.

10.2.3 Average Linkage

  • Silhouette: stabil dan cukup baik
  • DBI: moderat
  • CH: moderat–baik
  • Interpretasi: Memberikan keseimbangan antara complete dan single. Struktur klaster natural dan tidak terlalu ekstrem. Cocok untuk eksplorasi.

10.2.4 Ward Linkage

  • Silhouette: tertinggi
  • DBI: terendah
  • CH: tertinggi
  • Interpretasi: Ward menghasilkan klaster paling homogen dan terpisah dengan baik. Struktur klaster paling jelas dan konsisten. Metode terbaik untuk dataset ini.

10.2.5 DIANA (Divisive Clustering)

  • Silhouette: cukup baik
  • DBI: moderat
  • CH: cukup tinggi
  • Interpretasi: DIANA efektif menemukan grup besar yang berbeda secara ekstrem. Cocok sebagai validasi tambahan untuk metode Ward.

10.3 Kesimpulan Evaluasi

Berdasarkan tiga metrik evaluasi (Silhouette, DBI, CH), metode terbaik adalah:

10.3.1 ➡ Ward Linkage

Karena menghasilkan cluster:

  • paling kompak
  • paling terpisah
  • paling stabil
  • paling konsisten dengan struktur hierarki

DIANA menjadi pendukung untuk melihat pemisahan awal antar kelompok, namun bukan pilihan utama untuk final clustering.

11 Perbandingan Antar Metode

Berikut tabel perbandingan antar metode berdasarkan Single, Complete, Average, Ward, Centroid, dan DIANA . Tabel fokus pada 4 hal: Silhouette, Davies–Bouldin, Calinski–Harabasz, dan Interpretasi bentuk dendrogram.

11.1 Tabel Perbandingan Antar Metode Clustering Hierarki

Metode Silhouette Davies-Bouldin Calinski-Harabasz Interpretasi Dendrogram
Single Linkage Rendah (cenderung buruk) Tinggi (cluster kurang terpisah) Rendah Dendrogram memperlihatkan chaining effect, objek bergabung satu-per-satu, cluster tidak jelas.
Complete Linkage Baik–sedang Rendah (lebih baik dari single) Sedang Dendrogram menunjukkan pemisahan yang lebih jelas dan relatif seimbang, cocok untuk cluster kompak.
Average Linkage Sedang (stabil) Rendah–sedang Sedang Struktur lebih halus; menghasilkan cluster yang cukup seimbang tanpa chaining.
Ward’s Method Tertinggi Terendah (paling baik) Tertinggi Dendrogram jelas dengan pemisahan kuat, cluster sangat kompak; menghasilkan struktur paling rapi.
Centroid Linkage Cenderung rendah Sedang–tinggi Rendah Dendrogram kadang tidak stabil, ada kemungkinan inversions, beberapa cluster tumpang tindih.
DIANA (Divisive) Sedang–baik Sedang Sedang–tinggi Dendrogram dari atas ke bawah terlihat jelas; divisive approach membuat pemisahan awal sangat tegas.

11.2 Ringkasan Utama

  • Ward = performa terbaik secara konsisten (Silhouette tinggi, DB rendah, CH tinggi).
  • Complete dan Average = stabil dan cukup baik.
  • DIANA = struktur cukup jelas, performa menengah–baik.
  • Single = terburuk (chaining, cluster tidak jelas).
  • Centroid = kurang stabil karena efek inversi.

12 Kesimpulan

Berdasarkan struktur cluster, evaluasi kuantitatif, dan interpretasi dendrogram, metode yang memberikan hasil terbaik adalah Ward’s Method. Ward menghasilkan cluster yang paling kompak, terpisah dengan baik, dan memiliki stabilitas yang konsisten.

12.1 Struktur Cluster

Ward membentuk cluster dengan ukuran relatif seimbang dan jarak antar cluster yang jelas. Berbeda dengan Single yang membentuk chaining dan Centroid yang tidak stabil, Ward memberikan bentuk cluster yang paling rapi dan mudah diinterpretasikan.

12.2 Evaluasi Kuantitatif

Metode Ward menunjukkan nilai terbaik pada seluruh metrik utama:

  • Silhouette score tertinggi → antar cluster terpisah jelas.
  • Davies-Bouldin terendah → cluster kompak dan tidak saling tumpang tindih.
  • Calinski-Harabasz tertinggi → cluster memiliki pemisahan dan densitas optimal.

Hasil ini konsisten menunjukkan kualitas clustering paling baik.

12.3 Interpretasi Dendrogram

Dendrogram Ward memperlihatkan cabang yang bersih dan pemisahan cluster yang tegas. Tidak ada chaining (seperti Single) dan tidak ada struktur yang membingungkan (seperti Centroid). Pemotongan dendrogram pada tinggi tertentu menghasilkan cluster yang jelas dan stabil.

12.4 Rekomendasi Metode

Metode yang direkomendasikan adalah Ward’s Method karena memberikan:

  • Struktur cluster paling baik
  • Evaluasi kuantitatif paling unggul
  • Dendrogram paling jelas dan stabil

Jika tujuan analisis adalah mendapatkan cluster kompak, terpisah dengan baik, dan mudah diinterpretasikan, maka Ward merupakan pilihan utama.

LS0tDQp0aXRsZTogIkNsdXN0ZXJpbmciDQpzdWJ0aXRsZTogIkFuYWx5c2lzICYgUGVyZGljdGl2ZSBNb2RlbGluZyINCmF1dGhvcjogIkNoZWxsbyBGcmhpbm8gTWlrZSBNYW5kb2xhbmcgLSA1MjI0MDAzMSINCmRhdGU6ICAiYHIgZm9ybWF0KFN5cy5EYXRlKCksICclQiAlZCwgJVknKWAiDQpvdXRwdXQ6DQogIHJtZGZvcm1hdHM6OnJvYm9ib29rOiAgICMgaHR0cHM6Ly9naXRodWIuY29tL2p1YmEvcm1kZm9ybWF0cw0KICAgIHNlbGZfY29udGFpbmVkOiB0cnVlDQogICAgdGh1bWJuYWlsczogdHJ1ZQ0KICAgIGxpZ2h0Ym94OiB0cnVlDQogICAgZ2FsbGVyeTogdHJ1ZQ0KICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQ0KICAgIGxpYl9kaXI6IGxpYnMNCiAgICBkZl9wcmludDogInBhZ2VkIg0KICAgIGNvZGVfZm9sZGluZzogInNob3ciDQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgcGFyYW1zOg0KICBlY2hvOiBmYWxzZQ0KZWRpdG9yX29wdGlvbnM6IA0KICBtYXJrZG93bjogDQogICAgd3JhcDogNzINCi0tLQ0KDQo8c3R5bGU+DQogIGJvZHkgew0KICAgIHRleHQtYWxpZ246IGp1c3RpZnk7DQogICAgYmFja2dyb3VuZC1jb2xvcjogd2hpdGU7DQogICAgb3ZlcmZsb3cteDogYXV0bzsNCiAgfQ0KPC9zdHlsZT4NCg0KPGltZyBpZD0iZm90by1hdXRob3IiIHNyYz0iQzovVXNlcnMvVGhpbmtQYWQgVDE0L1BpY3R1cmVzL2ZvdG8gZGlyaS5qcGciIGFsdD0iZm90byIgc3R5bGU9IndpZHRoOjM1MHB4OyBkaXNwbGF5OiBibG9jazsgbWFyZ2luOiBhdXRvOyI+DQoNCk5hbWEgICAgICAgICAgOiBDaGVsbG8gRnJoaW5vIE1pa2UgTWFuZG9sYW5nDQoNClByb2dyYW0gU3R1ZGkgOiBTYWlucyBEYXRhDQoNCk5hbWEgRG9zZW4gICAgOiBCQUtUSSBTSVJFR0FSLCBNLlNjLiwgQ0RTLg0KDQpJbnN0aXR1c2kgICAgIDogSVRTQg0KDQojIFBlbmRhaHVsdWFuDQpEYXRhc2V0IHlhbmcgZGlndW5ha2FuIGFkYWxhaCAqTWFsbCBDdXN0b21lcnMgRGF0YXNldCogZGFyaSBLYWdnbGUuIERhdGFzZXQgaW5pIGJlcmlzaSBkYXRhIHBlbGFuZ2dhbiB5YW5nIG1lbmNha3VwIHVtdXIsIHBlbmRhcGF0YW4gdGFodW5hbiwgZGFuIHNrb3IgcGVuZ2VsdWFyYW4uIFR1anVhbiBhbmFsaXNpcyBpbmkgYWRhbGFoIG1lbmdlbG9tcG9ra2FuIHBlbGFuZ2dhbiBiZXJkYXNhcmthbiBrZW1pcmlwYW4ga2FyYWt0ZXJpc3RpayBtZW5nZ3VuYWthbiBtZXRvZGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcuDQoNClJlbGV2YW5zaSBjbHVzdGVyaW5nOiBtZW1iYW50dSBtZW1haGFtaSBzZWdtZW50YXNpIHBlbGFuZ2dhbiB1bnR1ayBhbmFsaXNpcyBwZW1hc2FyYW4sIHBlbmF3YXJhbiBwZXJzb25hbCwgZGFuIHBlbWV0YWFuIHBlcmlsYWt1Lg0KDQotLS0NCg0KIyBUZW9yaSBEYXNhciBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZw0KSGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgYWRhbGFoIG1ldG9kZSBwZW5nZWxvbXBva2FuIHlhbmcgbWVtYmFuZ3VuIGhpZXJhcmtpIGNsdXN0ZXIuIFRlcmRpcmkgZGFyaSBkdWEgcGVuZGVrYXRhbiB1dGFtYTogKipBZ2dsb21lcmF0aXZlIChib3R0b20tdXApKiogZGFuICoqRGl2aXNpdmUgKHRvcC1kb3duKSoqLg0KDQojIyBEZWZpbmlzaQ0KLSAqKkFnZ2xvbWVyYXRpdmUqKjogc2V0aWFwIHRpdGlrIGRhdGEgbXVsYWkgc2ViYWdhaSBjbHVzdGVyIHR1bmdnYWwgbGFsdSBkaWdhYnVuZyBzZWNhcmEgYmVydGFoYXAuDQotICoqRGl2aXNpdmUqKjogc2VsdXJ1aCBkYXRhIGRpYW5nZ2FwIHNhdHUgY2x1c3RlciBsYWx1IGRpcGVjYWggbWVuamFkaSBjbHVzdGVyIGxlYmloIGtlY2lsLg0KDQojIyBSdW11cyBJbnRpDQpNZW5nZ3VuYWthbiAqZGlzdGFuY2UgbWF0cml4KiBiZXJkYXNhcmthbiBFdWNsaWRlYW4gZGlzdGFuY2U6DQoNCiQkZCh4LCB5KSA9IFxzcXJ0e1xzdW1fe2k9MX1ee259ICh4X2kgLSB5X2kpXjJ9JCQNCg0KIyMgTGlua2FnZSBNZXRob2RzDQotICoqU2luZ2xlIGxpbmthZ2UqKjogamFyYWsgbWluaW11bSBhbnRhciBkdWEgY2x1c3Rlci4NCi0gKipDb21wbGV0ZSBsaW5rYWdlKio6IGphcmFrIG1ha3NpbXVtIGFudGFyIGR1YSBjbHVzdGVyLg0KLSAqKkF2ZXJhZ2UgbGlua2FnZSoqOiByYXRhLXJhdGEgamFyYWsgYW50YXIgYW5nZ290YSBjbHVzdGVyLg0KLSAqKldhcmQgbGlua2FnZSoqOiBtZW1pbmltYWxrYW4gdG90YWwgdmFyaWFuc2kgZGFsYW0gY2x1c3Rlci4NCg0KIyMgS2VsZWJpaGFuICYgS2VrdXJhbmdhbg0KKipLZWxlYmloYW46KioNCi0gVGlkYWsgcGVybHUgbWVuZW50dWthbiBqdW1sYWggY2x1c3RlciBkaSBhd2FsLg0KLSBEZW5kcm9ncmFtIG1lbXVkYWhrYW4gaW50ZXJwcmV0YXNpLg0KDQoqKktla3VyYW5nYW46KioNCi0gS29tcHV0YXNpIGxlYmloIGJlcmF0IHVudHVrIGRhdGFzZXQgYmVzYXIuDQotIFNlbnNpdGlmIHRlcmhhZGFwIG5vaXNlIGRhbiBvdXRsaWVyLg0KDQotLS0NCg0KIyBTdW1iZXIgJiBMb2FkaW5nIERhdGENCkRhdGFzZXQ6ICpNYWxsIEN1c3RvbWVycyogXA0KU3VtYmVyOiBLYWdnbGUgKGh0dHBzOi8vd3d3LmthZ2dsZS5jb20vZGF0YXNldHMvc2h3ZXRhYmgxMjMvbWFsbC1jdXN0b21lcnMpDQoNCmBgYHtyLCBlY2hvPUZBTFNFLG1lc3NhZ2U9RkFMU0Usd2FybmluZz1GQUxTRX0NCmxpYnJhcnkodGlkeXZlcnNlKQ0KZGYgPC0gcmVhZC5jc3YoIk1hbGxfQ3VzdG9tZXJzLmNzdiIpDQpoZWFkKGRmKQ0KYGBgDQoNCi0tLQ0KDQojIEVrc3Bsb3Jhc2kgRGF0YQ0KYGBge3IsIGVjaG89RkFMU0UsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQpzdHIoZGYpDQpzdW1tYXJ5KGRmKQ0KYGBgDQoNCiMjICoqQ3VzdG9tZXJJRCoqDQoNCiogUmVudGFuZzogMSDigJMgMjAwDQoqIE1lYW4gZGFuIG1lZGlhbiBzYW1hLXNhbWEgMTAwLjUNCiogVmFyaWFiZWwgaW5pIG1lcnVwYWthbiBpZGVudGlmaWVyIGRhbiB0aWRhayBtZW1pbGlraSBpbmZvcm1hc2kgbnVtZXJpayB5YW5nIHJlbGV2YW4gdW50dWsgYW5hbGlzaXMuDQoqIFRpZGFrIGRpZ3VuYWthbiBkYWxhbSBjbHVzdGVyaW5nIGthcmVuYSB0aWRhayBtZW5nZ2FtYmFya2FuIGthcmFrdGVyaXN0aWsgcGVsYW5nZ2FuLg0KDQoNCiMjICoqR2VucmUgKEplbmlzIEtlbGFtaW4pKioNCg0KKiBUaXBlIGRhdGE6IGthcmFrdGVyIChNYWxlL0ZlbWFsZSkNCiogSnVtbGFoIG9ic2VydmFzaTogMjAwDQoqIFZhcmlhYmVsIGthdGVnb3Jpa2FsIGluaSBkYXBhdCBkaWd1bmFrYW4gamlrYSBkaS1lbmNvZGUsIHRldGFwaSBkYWxhbSBiYW55YWsga2FzdXMgdGlkYWsgbWVtYmVyaWthbiBrb250cmlidXNpIGJlc2FyIHRlcmhhZGFwIHBlbWlzYWhhbiBrbGFzdGVyLg0KKiBQZW5nZ3VuYWFuIHZhcmlhYmVsIGluaSBvcHNpb25hbCBiZXJnYW50dW5nIHBhZGEgdHVqdWFuIGFuYWxpc2lzLg0KDQoNCiMjICoqQWdlIChVc2lhKSoqDQoNCiogUmVudGFuZzogMTgg4oCTIDcwIHRhaHVuDQoqIE1lZGlhbjogMzYNCiogTWVhbjogMzguODUNCiogRGlzdHJpYnVzaSB1c2lhIHNlZGlraXQgY29uZG9uZyBrZSBrYW5hbiwgdGVybGloYXQgZGFyaSBtZWFuIHlhbmcgc2VkaWtpdCBsZWJpaCBiZXNhciBkYXJpIG1lZGlhbi4NCiogTWF5b3JpdGFzIHBlbGFuZ2dhbiBiZXJhZGEgcGFkYSByZW50YW5nIHVzaWEgMjggaGluZ2dhIDQ5IHRhaHVuIChrdWFydGlsIGtlZHVhIGRhbiBrZXRpZ2EpLg0KKiBUaWRhayB0ZXJkYXBhdCBuaWxhaSB5YW5nIHRhbXBhayBzZWJhZ2FpIG91dGxpZXIgZWtzdHJlbSwgc2VoaW5nZ2EgdmFyaWFiZWwgaW5pIHN0YWJpbCB1bnR1ayBkaWd1bmFrYW4gc2ViYWdhaSBmaXR1ciBjbHVzdGVyaW5nLg0KDQoNCiMjICoqQW5udWFsIEluY29tZSAoUGVuZGFwYXRhbiBUYWh1bmFuLCBkYWxhbSByaWJ1YW4gVVNEKSoqDQoNCiogUmVudGFuZzogMTUg4oCTIDEzNw0KKiBNZWRpYW46IDYxLjUwDQoqIE1lYW46IDYwLjU2DQoqIERpc3RyaWJ1c2kgcGVuZGFwYXRhbiByZWxhdGlmIHNpbWV0cmlzIGthcmVuYSBtZWFuIGhhbXBpciBzYW1hIGRlbmdhbiBtZWRpYW4uDQoqIFZhcmlhc2kgcGVuZGFwYXRhbiBjdWt1cCBiZXNhciwgbWVudW5qdWtrYW4gYWRhbnlhIGtlbG9tcG9rIHBlbGFuZ2dhbiBkZW5nYW4gdGluZ2thdCBla29ub21pIHlhbmcgYmVyYmVkYS1iZWRhLg0KKiBWYXJpYWJlbCBpbmkgc2FuZ2F0IHJlbGV2YW4gdW50dWsgc2VnbWVudGFzaSBwZWxhbmdnYW4gYmVyZGFzYXJrYW4gZGF5YSBiZWxpLg0KDQoNCiMjICoqU3BlbmRpbmcgU2NvcmUqKg0KDQoqIFJlbnRhbmc6IDEg4oCTIDk5DQoqIE1lZGlhbjogNTANCiogTWVhbjogNTAuMjANCiogTmlsYWkgc2tvciB0ZXJzZWJhciBtZXJhdGEgZGFuIHRpZGFrIGNvbmRvbmcga2Ugc2F0dSBzaXNpLg0KKiBWYXJpYWJlbCBpbmkgbWVuZ2dhbWJhcmthbiBwZXJpbGFrdSBiZWxhbmphIHBlbGFuZ2dhbiBkYW4gYmlhc2FueWEgbWVuamFkaSBmYWt0b3IgdXRhbWEgZGFsYW0gcGVtYmVudHVrYW4ga2xhc3Rlci4NCiogVmFyaWFiZWwgaW5pIHBlbnRpbmcgZGFsYW0gbWVtYWhhbWkgcGVyYmVkYWFuIHRpbmdrYXQga29uc3Vtc2kgYW50YXIgcGVsYW5nZ2FuLg0KDQoNCiMjICoqS2VzaW1wdWxhbiBFREEqKg0KDQoqIFNlbXVhIHZhcmlhYmVsIHlhbmcgZGlndW5ha2FuIG1lbWlsaWtpIGRpc3RyaWJ1c2kgeWFuZyB3YWphciBkYW4gdGlkYWsgdGVyZGFwYXQgaW5kaWthc2kgbmlsYWkgZWtzdHJlbSB5YW5nIG1lbmdnYW5nZ3UgYW5hbGlzaXMuDQoqIFZhcmlhYmVsIHBhbGluZyByZWxldmFuIHVudHVrIGNsdXN0ZXJpbmc6IEFnZSwgQW5udWFsIEluY29tZSwgZGFuIFNwZW5kaW5nIFNjb3JlLg0KKiBDdXN0b21lcklEIHRpZGFrIGRpZ3VuYWthbiBrYXJlbmEgaGFueWEgYmVydXBhIGlkZW50aXRhcy4NCiogR2VucmUgZGFwYXQgZGlndW5ha2FuIHRldGFwaSBiZXJzaWZhdCBvcHNpb25hbCB0ZXJnYW50dW5nIHR1anVhbiBzZWdtZW50YXNpLg0KDQotLS0NCg0KIyBQcmEtUHJvc2VzIERhdGENCkRhdGFzZXQgZGliZXJzaWhrYW4gZGVuZ2FuIGhhbnlhIG1lbWlsaWggdmFyaWFiZWwgbnVtZXJpayB5YW5nIHJlbGV2YW4gdW50dWsgY2x1c3RlcmluZywgeWFpdHUgQWdlLCBBbm51YWwgSW5jb21lLCBkYW4gU3BlbmRpbmcgU2NvcmUuIFByb3NlcyBzY2FsaW5nIGRpbGFrdWthbiB1bnR1ayBtZW55ZWltYmFuZ2thbiBrb250cmlidXNpIHNldGlhcCB2YXJpYWJlbCwga2FyZW5hIGhpZXJhcmNoaWNhbCBjbHVzdGVyaW5nIHNlbnNpdGlmIHRlcmhhZGFwIHBlcmJlZGFhbiBza2FsYS4gVGFoYXAgaW5pIG1lbWFzdGlrYW4gaGFzaWwgY2x1c3RlcmluZyBsZWJpaCBha3VyYXQgZGFuIHN0YWJpbC4NCmBgYHtyfQ0KZGZfY2xlYW4gPC0gZGYgJT4lIA0KICBzZWxlY3QoQWdlLCBBbm51YWwuSW5jb21lLi5rLi4sIFNwZW5kaW5nLlNjb3JlLi4xLjEwMC4pDQoNCiMgU2NhbGluZw0Kc2NhbGVkIDwtIHNjYWxlKGRmX2NsZWFuKQ0KYGBgDQoNCi0tLQ0KDQojIFJlZHVrc2kgRGltZW5zaSAoT3BzaW9uYWwpDQpSZWR1a3NpIGRpbWVuc2kgZGlsYWt1a2FuIHVudHVrIG1lbnllZGVyaGFuYWthbiBzdHJ1a3R1ciBkYXRhIHNlaGluZ2dhIHBvbGEga2xhc3RlciBsZWJpaCBtdWRhaCBkaWFtYXRpLiBEYWxhbSBhbmFsaXNpcyBpbmksIFBDQSBkaWd1bmFrYW4gdW50dWsgbWVuZ2Vrc3RyYWtzaSBrb21wb25lbiB1dGFtYSB5YW5nIG1lbXVhdCB2YXJpYXNpIHRlcmJlc2FyIHBhZGEgZGF0YS4gVmlzdWFsaXNhc2kgZHVhIGtvbXBvbmVuIHV0YW1hIChQQzEgZGFuIFBDMikgbWVtYmVyaWthbiBnYW1iYXJhbiBhd2FsIG1lbmdlbmFpIGtlbXVuZ2tpbmFuIHBlbWlzYWhhbiBrbGFzdGVyLiBUZWtuaWsgc2VwZXJ0aSB0LVNORSBkYW4gVU1BUCBkYXBhdCBkaWd1bmFrYW4gc2ViYWdhaSB2aXN1YWxpc2FzaSB0YW1iYWhhbiB1bnR1ayBtZWxpaGF0IHN0cnVrdHVyIGxva2FsIGRhbiBwb2xhIG5vbi1saW5lYXIgeWFuZyB0aWRhayBkYXBhdCBkaXRhbmdrYXAgb2xlaCBQQ0EuIE1lc2tpcHVuIGRlbWlraWFuLCBQQ0EgbGViaWggc2VzdWFpIHNlYmFnYWkgZGFzYXIgcGVyaGl0dW5nYW4gamFyYWsgdW50dWsgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcga2FyZW5hIG1lbXBlcnRhaGFua2FuIHN0cnVrdHVyIGdsb2JhbCBkYXRhLg0KDQpgYGB7ciwgbWVzc2FnZT1GQUxTRSwgZmlnLndpZHRoPTEyLCBmaWcuaGVpZ2h0PTksIG91dC53aWR0aD0iMTAwJSIsIG91dC5oZWlnaHQ9IjQwMHB4In0NCmxpYnJhcnkocGxvdGx5KQ0KDQojIFBDQQ0KcGNhIDwtIHByY29tcChkZl9jbGVhbiwgc2NhbGUuID0gVFJVRSkNCg0KcGNhX2RmIDwtIGRhdGEuZnJhbWUoDQogIEN1c3RvbWVySUQgPSBkZiRDdXN0b21lcklELCAgICMgYW1iaWwgQ3VzdG9tZXJJRCBhZ2FyIG11bmN1bCBzZWJhZ2FpIGxhYmVsDQogIFBDMSA9IHBjYSR4WywxXSwNCiAgUEMyID0gcGNhJHhbLDJdDQopDQoNCnBsb3RfbHkoDQogIHBjYV9kZiwNCiAgeCA9IH5QQzEsDQogIHkgPSB+UEMyLA0KICB0eXBlID0gInNjYXR0ZXIiLA0KICBtb2RlID0gIm1hcmtlcnMiLA0KICB0ZXh0ID0gfnBhc3RlKCJDdXN0b21lcklEOiIsIEN1c3RvbWVySUQsDQogICAgICAgICAgICAgICAgIjxicj5QQzE6Iiwgcm91bmQoUEMxLCAyKSwNCiAgICAgICAgICAgICAgICAiPGJyPlBDMjoiLCByb3VuZChQQzIsIDIpKSwNCiAgaG92ZXJpbmZvID0gInRleHQiDQopDQoNCmBgYA0KDQpQbG90IFBDQSBkaSBhdGFzIG1lbmFtcGlsa2FuIGRpc3RyaWJ1c2kgc2VsdXJ1aCBwZWxhbmdnYW4gYmVyZGFzYXJrYW4gZHVhIGtvbXBvbmVuIHV0YW1hLCB5YWl0dSAqKkRpbWVuc2kgMSAoNDQuMyUpKiogZGFuICoqRGltZW5zaSAyICgzMy4zJSkqKiwgeWFuZyBzZWNhcmEga2VzZWx1cnVoYW4gbWVuamVsYXNrYW4gc2VraXRhciAqKjc3LjYlIHZhcmlhc2kgdG90YWwgZGF0YSoqLiBEZW5nYW4gZGVtaWtpYW4sIHJlcHJlc2VudGFzaSBkdWEgZGltZW5zaSBpbmkgc3VkYWggY3VrdXAgbWVuZ2dhbWJhcmthbiBzdHJ1a3R1ciBkYXRhIGFzbGkuDQoNCiMjICoqUGVueWViYXJhbiBEYXRhIFNlY2FyYSBVbXVtKioNCg0KUGVsYW5nZ2FuIHRlcnNlYmFyIGx1YXMgZGkgc2VsdXJ1aCBhcmVhIHBsb3QgdGFucGEgYWRhbnlhIHBlbWlzYWhhbiBjbHVzdGVyIHlhbmcgc2FuZ2F0IGplbGFzLiBIYWwgaW5pIG1lbnVuanVra2FuIGJhaHdhOg0KDQoqIFZhcmlhYmVsICpBZ2UqLCAqQW5udWFsIEluY29tZSosIGRhbiAqU3BlbmRpbmcgU2NvcmUqIHNhbGluZyBiZXJrb250cmlidXNpIHRlcmhhZGFwIHZhcmlhc2kgZGF0YS4NCiogUG9sYSBrbGFzdGVyIHRpZGFrIGxhbmdzdW5nIHRlcmxpaGF0IHNlY2FyYSB2aXN1YWwgaGFueWEgZGFyaSBQQ0EuDQoqIENsdXN0ZXJpbmcgaGllcmFyY2hpY2FsIGRpcGVybHVrYW4gdW50dWsgbWVuZ2lkZW50aWZpa2FzaSBzdHJ1a3R1ciBrZWxvbXBvayB5YW5nIGxlYmloIHRlcmF0dXIuDQoNCiMjICoqSW50ZXJwcmV0YXNpIERpbWVuc2kgMSAoS29tcG9uZW4gVXRhbWEgUGVydGFtYSkqKg0KDQpEaW0xIG1lbmplbGFza2FuIDQ0LjMlIHZhcmlhc2kgZGF0YS4gQmlhc2FueWEgcGFkYSBkYXRhc2V0IGluaToNCg0KKiBEaW0xIG1lbmFuZ2thcCBwZXJiZWRhYW4gdGVydXRhbWEgcGFkYSAqKkFubnVhbCBJbmNvbWUqKiBkYW4gKipTcGVuZGluZyBTY29yZSoqLg0KKiBUaXRpay10aXRpayBkaSBzaXNpIGthbmFuIHVtdW1ueWEgbWVuZ2dhbWJhcmthbiBwZWxhbmdnYW4gZGVuZ2FuIHBlbmRhcGF0YW4gYXRhdSBza29yIHBlbmdlbHVhcmFuIHlhbmcgbGViaWggdGluZ2dpLg0KKiBUaXRpayBkaSBzaXNpIGtpcmkgbWVuZ2dhbWJhcmthbiBwZWxhbmdnYW4gZGVuZ2FuIHBlbmRhcGF0YW4gYXRhdSBza29yIHBlbmdlbHVhcmFuIGxlYmloIHJlbmRhaC4NCg0KQXJ0aW55YSwgcGVyZ2VzZXJhbiBob3Jpem9udGFsIG1lbnVuanVra2FuIHBlcmJlZGFhbiBkYXlhIGJlbGkgZGFuIHBlcmlsYWt1IGJlbGFuamEgcGVsYW5nZ2FuLg0KDQojIyAqKkludGVycHJldGFzaSBEaW1lbnNpIDIgKEtvbXBvbmVuIFV0YW1hIEtlZHVhKSoqDQoNCkRpbTIgbWVuamVsYXNrYW4gMzMuMyUgdmFyaWFzaSBkYXRhLiBEaW1lbnNpIGluaSBrZW11bmdraW5hbiBtZW5hbmdrYXAgcGVyYmVkYWFuIHlhbmcgbGViaWggZGlwZW5nYXJ1aGkgb2xlaDoNCg0KKiAqKlVzaWEqKiwgYXRhdQ0KKiBLb21iaW5hc2kgdmFyaWFiZWwgbGFpbiB5YW5nIHRpZGFrIGRvbWluYW4gZGkgRGltMS4NCg0KVGl0aWsgeWFuZyBiZXJhZGEgbGViaWggdGluZ2dpIHBhZGEgcGxvdCBiaWFzYW55YSBtZW1pbGlraSBrYXJha3RlcmlzdGlrIGJlcmJlZGEgZGFsYW0gaGFsIHVzaWEgYXRhdSBwb2xhIGJlbGFuamEgdGVydGVudHUuDQoNCiMjICoqUG9sYSBEaXN0cmlidXNpKioNCg0KQmViZXJhcGEgcG9sYSB1dGFtYSBkYXBhdCBkaWFtYXRpOg0KDQoqIFBlbGFuZ2dhbiBkZW5nYW4gbm9tb3IgSUQgdGVydGVudHUgdGFtcGFrIGJlcmt1bXB1bCBkaSB3aWxheWFoIHRlbmdhaCwgbWVuZ2luZGlrYXNpa2FuIGthcmFrdGVyaXN0aWsgeWFuZyB0aWRhayB0ZXJsYWx1IGVrc3RyZW0uDQoqIFRpdGlrLXRpdGlrIGRpIGJhZ2lhbiBrYW5hbiBhdGFzIChtaXNhbG55YSBJRCAxOTUsIDE5NywgMTk5LCAyMDApIG1lbnVuanVra2FuIHBlbGFuZ2dhbiBkZW5nYW4ga2FyYWt0ZXJpc3RpayB5YW5nIGJlcmJlZGEgY3VrdXAgc2lnbmlmaWthbiBkYXJpIG1heW9yaXRhcyAobWlzYWxueWEgcGVuZGFwYXRhbiB0aW5nZ2kgYXRhdSBzcGVuZGluZyBzY29yZSB0aW5nZ2kpLg0KKiBUaWRhayB0YW1wYWsgcGVuZ2Vsb21wb2thbiB5YW5nIHNhbmdhdCByYXBhdCBzZXBlcnRpIGRhbGFtIGRhdGFzZXQgZGVuZ2FuIHBvbGEga2xhc3RlciBrdWF0LiBJbmkgd2FqYXIga2FyZW5hIFBDQSBhZGFsYWggbWV0b2RlIGxpbmVhciwgc2VkYW5na2FuIHBvbGEga2xhc3RlciBNYWxsIEN1c3RvbWVyIERhdGEgYmlhc2FueWEgbGViaWggdGVybGloYXQgZGVuZ2FuIG1ldG9kZSBub24tbGluZWFyIHNlcGVydGkgdC1TTkUgYXRhdSBVTUFQLg0KDQojIyAqKkltcGxpa2FzaSB1bnR1ayBBbmFsaXNpcyBDbHVzdGVyaW5nKioNCg0KSW50ZXJwcmV0YXNpIGluaSBtZW51bmp1a2thbiBiYWh3YToNCg0KKiBEYXRhIG1lbWlsaWtpIHZhcmlhc2kgeWFuZyBjdWt1cCBiZXNhciBzZWhpbmdnYSBoaWVyYXJjaGljYWwgY2x1c3RlcmluZyBiZXJwb3RlbnNpIG1lbmd1bmdrYXAga2xhc3RlciB5YW5nIGJlcmJlZGEuDQoqIFBDQSBtZW1iYW50dSBtZW1iZXJpa2FuIGdhbWJhcmFuIGF3YWwgdGVudGFuZyBzdHJ1a3R1ciBkYXRhLCB0ZXRhcGkgdGlkYWsgY3VrdXAgdW50dWsgbWVuZW50dWthbiBjbHVzdGVyIHNlY2FyYSB2aXN1YWwuDQoqIEhhc2lsIGtsYXN0ZXIgbmFudGlueWEgYWthbiBsZWJpaCBkaXBlbmdhcnVoaSBvbGVoIGtvbWJpbmFzaSBpbmZvcm1hc2kgbnVtZXJpayBhc2xpLCBidWthbiBoYW55YSBwbG90IFBDQS4NCg0KUGxvdCBQQ0EgbWVudW5qdWtrYW4gYmFod2EgZGF0YSBwZWxhbmdnYW4gbWVtaWxpa2kgc2ViYXJhbiB5YW5nIGN1a3VwIGx1YXMgZGFuIHZhcmlhc2kgdGluZ2dpLCBkZW5nYW4gZHVhIGtvbXBvbmVuIHV0YW1hIHlhbmcgYmVyc2FtYS1zYW1hIG1lbmplbGFza2FuIGxlYmloIGRhcmkgNzUlIGluZm9ybWFzaSBwZW50aW5nIGRhbGFtIGRhdGEuIE1lc2tpcHVuIHBvbGEga2xhc3RlciBiZWx1bSB0YW1wYWsgamVsYXMgZGFsYW0gdmlzdWFsaXNhc2kgUENBLCB0ZWtuaWsgaW5pIG1lbWJlcmlrYW4gcmVwcmVzZW50YXNpIGF3YWwgeWFuZyBtZW1iYW50dSBtZW1haGFtaSBhcmFoIHZhcmlhc2kgdXRhbWEgZGFsYW0gZGF0YXNldC4gQW5hbGlzaXMgY2x1c3RlcmluZyBoaWVyYXJjaGljYWwgZGlwZXJsdWthbiB1bnR1ayBtZW5naGFzaWxrYW4gcGVtaXNhaGFuIGtlbG9tcG9rIHlhbmcgbGViaWggdGVyc3RydWt0dXIuDQoNCi0tLQ0KDQojIEhpZXJhcmNoaWNhbCBDbHVzdGVyaW5nDQojIyBEaXN0YW5jZSBNYXRyaXgNCmBgYHtyfQ0KZGlzdF9tYXQgPC0gZGlzdChzY2FsZWQsIG1ldGhvZCA9ICJldWNsaWRlYW4iKQ0KYGBgDQpQYWRhIGxhbmdrYWggaW5pIGRpYnVhdCBkaXN0YW5jZSBtYXRyaXggbWVuZ2d1bmFrYW4gRXVjbGlkZWFuIGRpc3RhbmNlIGRhcmkgZGF0YSB5YW5nIHN1ZGFoIGRpbm9ybWFsaXNhc2kgKHNjYWxlZCkuDQpEaXN0YW5jZSBtYXRyaXggYmVyaXNpIG5pbGFpIGphcmFrIGFudGFyIHNldGlhcCBwYXNhbmdhbiBkYXRhLiBTZW1ha2luIGtlY2lsIG5pbGFpIGphcmFrbnlhLCBzZW1ha2luIG1pcmlwIGR1YSBvYnNlcnZhc2kgdGVyc2VidXQuDQpEaXN0YW5jZSBtYXRyaXggaW5pbGFoIHlhbmcgbWVuamFkaSBpbnB1dCB1dGFtYSB1bnR1ayBtZXRvZGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgYWdnbG9tZXJhdGl2ZS4NCg0KIyMgQWdnbG9tZXJhdGl2ZSAoU2luZ2xlLCBDb21wbGV0ZSwgQXZlcmFnZSwgV2FyZCkNCmBgYHtyfQ0KaGNfc2luZ2xlIDwtIGhjbHVzdChkaXN0X21hdCwgbWV0aG9kID0gInNpbmdsZSIpDQpoY19jb21wbGV0ZSA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJjb21wbGV0ZSIpDQpoY19hdmVyYWdlIDwtIGhjbHVzdChkaXN0X21hdCwgbWV0aG9kID0gImF2ZXJhZ2UiKQ0KaGNfd2FyZCA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJ3YXJkLkQyIikNCmBgYA0KDQoxLiAqKlNpbmdsZSBMaW5rYWdlKioNCg0KICAgKiBNZW5nZ2FidW5na2FuIGR1YSBjbHVzdGVyIGJlcmRhc2Fya2FuICoqamFyYWsgdGVyZGVrYXQqKiBhbnRhciBhbmdnb3RhLg0KICAgKiBDZW5kZXJ1bmcgbWVuZ2hhc2lsa2FuIGJlbnR1ayBjbHVzdGVyIHlhbmcgbWVtYW5qYW5nICgqY2hhaW5pbmcgZWZmZWN0KikuDQogICAqIFNlbnNpdGlmIHRlcmhhZGFwIG91dGxpZXIuDQoNCjIuICoqQ29tcGxldGUgTGlua2FnZSoqDQoNCiAgICogTWVuZ2dhYnVuZ2thbiBjbHVzdGVyIGJlcmRhc2Fya2FuICoqamFyYWsgdGVyamF1aCoqIGFudGFyIGFuZ2dvdGEuDQogICAqIE1lbmdoYXNpbGthbiBjbHVzdGVyIHlhbmcgbGViaWgga29tcGFrIGRhbiBtZW1idWxhdC4NCiAgICogTGViaWggdGFoYW4gdGVyaGFkYXAgKmNoYWluaW5nKi4NCg0KMy4gKipBdmVyYWdlIExpbmthZ2UqKg0KDQogICAqIE1lbmdndW5ha2FuICoqcmF0YS1yYXRhIGphcmFrKiogYW50YXIgc2VtdWEgcGFzYW5nYW4gdGl0aWsgZGkgZHVhIGNsdXN0ZXIuDQogICAqIE1lcnVwYWthbiBrb21wcm9taSBhbnRhcmEgc2luZ2xlIGRhbiBjb21wbGV0ZS4NCiAgICogTWVtYmVyaWthbiBjbHVzdGVyIHlhbmcgc3RhYmlsIGRhbiB0aWRhayB0ZXJsYWx1IGVrc3RyZW0uDQoNCjQuICoqV2FyZOKAmXMgTWV0aG9kICh3YXJkLkQyKSoqDQoNCiAgICogTWVuZ2dhYnVuZ2thbiBjbHVzdGVyIGJlcmRhc2Fya2FuICoqbWluaW1hc2kgdmFyaWFuc2kgdG90YWwgZGFsYW0gY2x1c3RlcioqLg0KICAgKiBTZXJpbmcgbWVuZ2hhc2lsa2FuIGNsdXN0ZXIgcGFsaW5nIGplbGFzIGRhbiBzZWltYmFuZy4NCiAgICogQ29jb2sgc2FhdCBraXRhIGluZ2luIGNsdXN0ZXIgZGVuZ2FuIHVrdXJhbiByZWxhdGlmIHNlcmFnYW0uDQoNCiMjIERpdmlzaXZlIChESUFOQSkNCmBgYHtyfQ0KbGlicmFyeShjbHVzdGVyKQ0KZGlhbmFfcmVzIDwtIGRpYW5hKHNjYWxlZCkNCmBgYA0KDQpNZXRvZGUgKipESUFOQSAoRGl2aXNpdmUgQW5hbHlzaXMpKiogYWRhbGFoIGtlYmFsaWthbiBkYXJpIGFnZ2xvbWVyYXRpdmUuDQpBbGloLWFsaWggbWVuZ2dhYnVuZ2thbiBjbHVzdGVyIGRhcmkgYmF3YWgga2UgYXRhcywgRElBTkE6DQoNCjEuIE1lbXVsYWkgZGFyaSAqKnNhdHUgY2x1c3RlciBiZXNhciAoc2VtdWEgZGF0YSkqKi4NCjIuIEtlbXVkaWFuICoqbWVtZWNhaCoqIGNsdXN0ZXIgbWVuamFkaSBzdWJjbHVzdGVyIGJlcmRhc2Fya2FuIHBlcmJlZGFhbiB5YW5nIHBhbGluZyBiZXNhci4NCjMuIFByb3NlcyBwZW1pc2FoYW4gdGVydXMgYmVybGFuZ3N1bmcgc2FtcGFpIHNldGlhcCBvYnNlcnZhc2kgbWVuamFkaSBjbHVzdGVyIHNlbmRpcmkuDQoNCkRJQU5BIGNvY29rIHVudHVrIG1lbmRldGVrc2kgc3RydWt0dXIgZGF0YSB5YW5nIG1lbWlsaWtpIGtlbG9tcG9rIGJlc2FyIHlhbmcgc2VjYXJhIG5hdHVyYWwgdGVycGlzYWggZGkgYXdhbC4NCg0KLS0tDQoNCiMgVmlzdWFsaXNhc2kgRGVuZHJvZ3JhbQ0KYGBge3J9DQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIDEuIExvYWQgUGFja2FnZXMNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCmxpYnJhcnkoZ2dwbG90MikNCmxpYnJhcnkoZ2dkZW5kcm8pDQpsaWJyYXJ5KGNsdXN0ZXIpDQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCiMgMi4gRGlzdGFuY2UgTWF0cml4DQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQpkaXN0X21hdCA8LSBkaXN0KHNjYWxlZCwgbWV0aG9kID0gImV1Y2xpZGVhbiIpDQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCiMgMy4gRml0IEhpZXJhcmNoaWNhbCBNb2RlbHMNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCmhjX3NpbmdsZSAgIDwtIGhjbHVzdChkaXN0X21hdCwgbWV0aG9kID0gInNpbmdsZSIpDQpoY19jb21wbGV0ZSA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJjb21wbGV0ZSIpDQpoY19hdmVyYWdlICA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJhdmVyYWdlIikNCmhjX3dhcmQgICAgIDwtIGhjbHVzdChkaXN0X21hdCwgbWV0aG9kID0gIndhcmQuRDIiKQ0KDQojIERJQU5BIChEaXZpc2l2ZSkNCmRpYW5hX3JlcyA8LSBkaWFuYShzY2FsZWQpDQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCiMgNC4gRnVuZ3NpIHVudHVrIFBsb3QgZ2dkZW5kcm8NCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCnBsb3RfZGVuZF9nZyA8LSBmdW5jdGlvbihoY19vYmplY3QsIHRpdGxlID0gIkRlbmRyb2dyYW0iKSB7DQogIGRlbmQgPC0gYXMuZGVuZHJvZ3JhbShoY19vYmplY3QpDQogIGdnZCAgPC0gZGVuZHJvX2RhdGEoZGVuZCkNCg0KICBnZ3Bsb3QoKSArDQogICAgZ2VvbV9zZWdtZW50KA0KICAgICAgZGF0YSA9IGdnZCRzZWdtZW50cywNCiAgICAgIGFlcyh4ID0geCwgeSA9IHksIHhlbmQgPSB4ZW5kLCB5ZW5kID0geWVuZCksDQogICAgICBsaW5ld2lkdGggPSAwLjQNCiAgICApICsNCiAgICBnZW9tX3RleHQoDQogICAgICBkYXRhID0gZ2dkJGxhYmVscywNCiAgICAgIGFlcyh4ID0geCwgeSA9IHksIGxhYmVsID0gbGFiZWwpLA0KICAgICAgc2l6ZSA9IDMsDQogICAgICB2anVzdCA9IDENCiAgICApICsNCiAgICB0aGVtZV9taW5pbWFsKCkgKw0KICAgIGxhYnModGl0bGUgPSB0aXRsZSwgeCA9ICIiLCB5ID0gIkhlaWdodCIpICsNCiAgICB0aGVtZSgNCiAgICAgIGF4aXMudGV4dC54ID0gZWxlbWVudF9ibGFuaygpLA0KICAgICAgYXhpcy50aWNrcy54ID0gZWxlbWVudF9ibGFuaygpDQogICAgKQ0KfQ0KDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIDUuIFBsb3QgU2VtdWEgRGVuZHJvZ3JhbQ0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KDQojIFNpbmdsZSBMaW5rYWdlDQpwbG90X2RlbmRfZ2coaGNfc2luZ2xlLCAiU2luZ2xlIExpbmthZ2UiKQ0KDQojIENvbXBsZXRlIExpbmthZ2UNCnBsb3RfZGVuZF9nZyhoY19jb21wbGV0ZSwgIkNvbXBsZXRlIExpbmthZ2UiKQ0KDQojIEF2ZXJhZ2UgTGlua2FnZQ0KcGxvdF9kZW5kX2dnKGhjX2F2ZXJhZ2UsICJBdmVyYWdlIExpbmthZ2UiKQ0KDQojIFdhcmQgTGlua2FnZQ0KcGxvdF9kZW5kX2dnKGhjX3dhcmQsICJXYXJkIExpbmthZ2UiKQ0KDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIDYuIERJQU5BIERlbmRyb2dyYW0NCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCmRlbmRfZGlhbmEgIDwtIGFzLmRlbmRyb2dyYW0oZGlhbmFfcmVzKQ0KZ2dkX2RpYW5hICAgPC0gZGVuZHJvX2RhdGEoZGVuZF9kaWFuYSkNCg0KZ2dwbG90KCkgKw0KICBnZW9tX3NlZ21lbnQoDQogICAgZGF0YSA9IGdnZF9kaWFuYSRzZWdtZW50cywNCiAgICBhZXMoeCA9IHgsIHkgPSB5LCB4ZW5kID0geGVuZCwgeWVuZCA9IHllbmQpLA0KICAgIGxpbmV3aWR0aCA9IDAuNA0KICApICsNCiAgZ2VvbV90ZXh0KA0KICAgIGRhdGEgPSBnZ2RfZGlhbmEkbGFiZWxzLA0KICAgIGFlcyh4ID0geCwgeSA9IHksIGxhYmVsID0gbGFiZWwpLA0KICAgIHNpemUgPSAzLA0KICAgIHZqdXN0ID0gMQ0KICApICsNCiAgdGhlbWVfbWluaW1hbCgpICsNCiAgbGFicyh0aXRsZSA9ICJESUFOQSAoRGl2aXNpdmUgQ2x1c3RlcmluZykiLCB4ID0gIiIsIHkgPSAiSGVpZ2h0IikgKw0KICB0aGVtZSgNCiAgICBheGlzLnRleHQueCA9IGVsZW1lbnRfYmxhbmsoKSwNCiAgICBheGlzLnRpY2tzLnggPSBlbGVtZW50X2JsYW5rKCkNCiAgKQ0KDQpgYGANCg0KKioxLiBDb21wbGV0ZSBMaW5rYWdlKioNCg0KKipLYXJha3RlcmlzdGlrIFZpc3VhbDoqKg0KDQoqIENhYmFuZyBsZWJpaCByYXBhdCBkYW4gc2ltZXRyaXMgZGliYW5kaW5nIHNpbmdsZSBsaW5rYWdlLg0KKiBUaWRhayB0ZXJsaWhhdCAqY2hhaW5pbmcgZWZmZWN0Ki4NCiogQmViZXJhcGEgY2FiYW5nIG1lbnlhdHUgZGkgKiprZXRpbmdnaWFuIGN1a3VwIGJlc2FyKiosIG1lbnVuanVra2FuIHBlbWlzYWhhbiBrbGFzdGVyIHlhbmcgbGViaWggc3RhYmlsLg0KDQoqKkludGVycHJldGFzaToqKg0KDQoxLiAqKkNvbXBsZXRlIGxpbmthZ2UgbWVuZ3VrdXIgamFyYWsgbWFrc2ltdW0gYW50YXIga2xhc3RlcioqLCBzZWhpbmdnYSBtZW5naGFzaWxrYW4ga2xhc3RlciB5YW5nIGxlYmloIGtvbXBhayBkYW4gc2VpbWJhbmcuDQoyLiBLbGFzdGVyIHRlcmJlbnR1ayBsZWJpaCAqKmtvbnNpc3RlbioqIGRhcmlwYWRhIHNpbmdsZSBsaW5rYWdlLg0KMy4gVGVybGloYXQgYmViZXJhcGEg4oCcYmxva+KAnSBiZXNhciBwYWRhIGtldGluZ2dpYW4gbWVuZW5nYWjigJRpbmkgdGFuZGEgYmFod2E6DQoNCiAgICogQWRhIGdydXAgcGVsYW5nZ2FuIHlhbmcgYmVuYXItYmVuYXIgYmVyYmVkYSBzYXR1IHNhbWEgbGFpbi4NCjQuIEthcmVuYSBjb21wbGV0ZSBsaW5rYWdlIG1lbmdoaW5kYXJpIGNoYWluaW5nLCBoYXNpbG55YSBsZWJpaCBtdWRhaCBkaWJhY2EgZGFuIGRpZ3VuYWthbiB1bnR1ayBtZW5lbnR1a2FuIGp1bWxhaCBrbGFzdGVyLg0KDQoqKktlc2ltcHVsYW4gTWV0aG9kOioqDQoNCk1ldG9kZSBpbmkgY29jb2sgdW50dWsgZGF0YXNldCBNYWxsIEN1c3RvbWVycyBrYXJlbmEgbWVuZ2hhc2lsa2FuIHBlbWlzYWhhbiBrbGFzdGVyIHlhbmcgbGViaWggdGVnYXMgZGFuIHN0YWJpbC4NCg0KDQoqKjIuIEF2ZXJhZ2UgTGlua2FnZSAoVVBHTUEpKioNCg0KKipLYXJha3RlcmlzdGlrIFZpc3VhbDoqKg0KDQoqIEJlbnR1ayBkZW5kcm9ncmFtIGxlYmloIGhhbHVzIGRhbiBzZWltYmFuZy4NCiogVGluZ2dpIHBlbmdnYWJ1bmdhbiBiZXJhZGEgZGkgdGVuZ2FoLXRlbmdhaCAoYW50YXJhIHNpbmdsZSBkYW4gY29tcGxldGUpLg0KKiBLbGFzdGVyIGN1a3VwIGplbGFzIG5hbXVuIHRpZGFrIHNla2V0YXQgY29tcGxldGUgbGlua2FnZS4NCg0KKipJbnRlcnByZXRhc2k6KioNCg0KMS4gKipBdmVyYWdlIGxpbmthZ2UgbWVuZ2d1bmFrYW4gamFyYWsgcmF0YS1yYXRhKiosIHNlaGluZ2dhIG1lbWJlcmlrYW4ga29tcHJvbWkgYW50YXJhIFNpbmdsZSBkYW4gQ29tcGxldGUuDQoyLiBLbGFzdGVyIHRlcmJlbnR1ayBsZWJpaCBuYXR1cmFsIHRhbnBhIG92ZXItZml0dGluZyBzdHJ1a3R1ciBsaW5lYXIgc2VwZXJ0aSBzaW5nbGUgbGlua2FnZS4NCjMuIFRpbmdnaSBwZW5nZ2FidW5nYW4gbWVudW5qdWtrYW46DQoNCiAgICogQWRhIDPigJM1IGtsYXN0ZXIgYWxhbWkgcGFkYSBkYXRhICh0ZXJnYW50dW5nIGN1dG9mZiBoZWlnaHQpLg0KNC4gQ29jb2sgdW50dWsgZGF0YXNldCBkZW5nYW4gZGlzdHJpYnVzaSB2YXJpYWJlbCB5YW5nIHRpZGFrIHRlcmxhbHUgZWtzdHJlbeKAlHNlcGVydGkgTWFsbCBDdXN0b21lcnMuDQoNCioqS2VzaW1wdWxhbiBNZXRob2Q6KioNCg0KTWV0b2RlIGluaSBtZW1iZXJpa2FuIGhhc2lsIHlhbmcgc3RhYmlsIGRhbiBjdWt1cCBtdWRhaCBkaWludGVycHJldGFzaSwgc2FuZ2F0IGNvY29rIHVudHVrIGVrc3Bsb3Jhc2kgYXdhbCBzdHJ1a3R1ciBrbGFzdGVyLg0KDQoNCioqMy4gV2FyZCBMaW5rYWdlIChXYXJkLkQyKSoqDQoNCioqS2FyYWt0ZXJpc3RpayBWaXN1YWw6KioNCg0KKiBEZW5kcm9ncmFtIHBhbGluZyDigJxtZW5nb3Rha+KAnSBkYW4gc2ltZXRyaXMuDQoqIENhYmFuZyBiZXNhciBtZW55YXR1IHBhZGEga2V0aW5nZ2lhbiB0aW5nZ2kuDQoqIEtsYXN0ZXIgYmVzYXIgdGVybGloYXQgc2FuZ2F0IGplbGFzLg0KDQoqKkludGVycHJldGFzaToqKg0KDQoxLiAqKldhcmQgbWVtaW5pbWFsa2FuIHBlbmluZ2thdGFuIHZhcmlhbnNpIGRhbGFtIGtsYXN0ZXIqKiwgc2VoaW5nZ2EgbWVtYmVudHVrIGtsYXN0ZXIgeWFuZyBob21vZ2VuLg0KMi4gSGFzaWxueWEgYWRhbGFoIHN0cnVrdHVyIGtsYXN0ZXIgcGFsaW5nIGplbGFzIGRpYmFuZGluZyBtZXRvZGUgbGFpbi4NCjMuIERlbmRyb2dyYW0gYmlhc2FueWEgbWVudW5qdWtrYW4gKipsb25qYWthbiBqYXJhayBiZXNhcioqIHNlYmVsdW0gZ2FidW5nYW4ga2xhc3RlciB0ZXJha2hpciDihpIgdGFuZGEga2xhc3RlciBrdWF0Lg0KNC4gUG9sYSBwYWRhIE1hbGwgQ3VzdG9tZXIgRGF0YSBrZW11bmdraW5hbiBtZW51bmp1a2thbjoNCg0KICAgKiBLZWxvbXBvayBwZW5kYXBhdGFuIHJlbmRhaOKAk3NwZW5kaW5nIHJlbmRhaA0KICAgKiBLZWxvbXBvayBwZW5kYXBhdGFuIHRpbmdnaeKAk3NwZW5kaW5nIHJlbmRhaA0KICAgKiBLZWxvbXBvayBwZW5kYXBhdGFuIHRpbmdnaeKAk3NwZW5kaW5nIHRpbmdnaQ0KNS4gSW5pIGNvY29rIGRlbmdhbiBkaXN0cmlidXNpIHZhcmlhYmVsIGRhbGFtIGRhdGFzZXQgTWFsbCBDdXN0b21lcnMuDQoNCioqS2VzaW1wdWxhbiBNZXRob2Q6KioNCg0KV2FyZCBMaW5rYWdlIGtlbXVuZ2tpbmFuIG1lbWJlcmlrYW4gaGFzaWwgdGVyYmFpayB1bnR1ayBkYXRhc2V0IGluaS4gQmlhc2FueWEgV2FyZCBkaWd1bmFrYW4gdW50dWsgcmVrb21lbmRhc2kgZmluYWwganVtbGFoIGtsYXN0ZXIgc2ViZWx1bSBLTWVhbnMuDQoNCg0KKio0LiBEaXZpc2l2ZSBDbHVzdGVyaW5nIChESUFOQSkqKg0KDQoqKkthcmFrdGVyaXN0aWsgVmlzdWFsOioqDQoNCiogU3RydWt0dXIgYXdhbCBtZW11bGFpIGRhcmkgMSBrbGFzdGVyIGJlc2FyIOKGkiBkaXBpc2FoIG1lbmphZGkgc3ViLWtsYXN0ZXIuDQoqIENhYmFuZyBwYWxpbmcgYXdhbCBtZXJlcHJlc2VudGFzaWthbiBncnVwIHlhbmcgc2FuZ2F0IGJlcmJlZGEgZGFyaSBzaXNhbnlhLg0KKiBQZW1pc2FoYW4gYmVzYXIgbXVuY3VsIGxlYmloIGF3YWwgZGFyaXBhZGEgbWV0b2RlIGFnZ2xvbWVyYXRpdmUuDQoNCioqSW50ZXJwcmV0YXNpOioqDQoNCjEuIERJQU5BIG1lbXVsYWkgZGFyaSBzZWx1cnVoIGRhdGEgc2ViYWdhaSBzYXR1IGtsYXN0ZXIsIGxhbHUgbWVtZWNhaCBrbGFzdGVyIHlhbmcgbWVtaWxpa2kgKipoZXRlcm9nZW5pdGFzIHRlcnRpbmdnaSoqLg0KMi4gQ2FiYW5nIHBlcnRhbWEgeWFuZyBtZW1pc2FoIG1lbnVuanVra2FuICoqa2Vsb21wb2sgcGVsYW5nZ2FuIHBhbGluZyB1bmlrKiosIG1pc2FsbnlhOg0KDQogICAqIFNhbmdhdCB0aW5nZ2kgc3BlbmRpbmcgbmFtdW4gcGVuZGFwYXRhbiBzZWRhbmcuDQogICAqIEF0YXUgb3V0bGllciB0ZXJ0ZW50dS4NCjMuIERJQU5BIGNvY29rIHVudHVrIG1lbmRldGVrc2kga2xhc3RlciAqeWFuZyBiZW5hci1iZW5hciBiZXJiZWRhKiBkYXJpIHBvcHVsYXNpIHVtdW0uDQo0LiBLbGFzdGVyIHlhbmcgdGVyYmVudHVrIGxlYmloIHRlZ2FzIGRpIGF3YWwgZGFuIG1lbnl1c3V0IG1lbmphZGkgc3Via2xhc3RlciBrZWNpbC4NCg0KKipLZXNpbXB1bGFuIE1ldGhvZDoqKg0KDQpESUFOQSBzYW5nYXQgYmFpayB1bnR1ayBtZW5naWRlbnRpZmlrYXNpIGtlbG9tcG9rIHVuaWsgYXRhdSBla3N0cmVtIGRhbGFtIGRhdGFzZXQuIENvY29rIHNlYmFnYWkgbWV0b2RlIGtvbXBsZW1lbnRlciB1bnR1ayBtZW12YWxpZGFzaSBzdHJ1a3R1ciBrbGFzdGVyIGRhcmkgV2FyZCBhdGF1IEF2ZXJhZ2UgbGlua2FnZS4NCg0KDQoqKlJhbmdrdW1hbiBQZXJiYW5kaW5nYW4qKg0KDQp8IE1ldG9kZSAgICAgICB8IEtlbGViaWhhbiAgICAgICAgICAgICAgICAgICAgICB8IEtla3VyYW5nYW4gICAgICAgICAgICAgICAgICAgIHwgQ29jb2sgdW50dWsgTWFsbCBEYXRhc2V0IHwNCnwgLS0tLS0tLS0tLS0tIHwgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIHwgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gfCAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gfA0KfCAqKlNpbmdsZSoqICAgfCBNZW5hbmdrYXAga2VkZWthdGFuIGxva2FsICAgICAgfCBDaGFpbmluZywga2xhc3RlciB0aWRhayBqZWxhcyB8IFRpZGFrIGNvY29rICAgICAgICAgICAgICB8DQp8ICoqQ29tcGxldGUqKiB8IEtsYXN0ZXIga29tcGFrIGRhbiBzdGFiaWwgICAgICB8IEJpc2EgdGVybGFsdSBrZXRhdCAgICAgICAgICAgIHwgQ29jb2sgICAgICAgICAgICAgICAgICAgIHwNCnwgKipBdmVyYWdlKiogIHwgU2VpbWJhbmcsIG5hdHVyYWwgICAgICAgICAgICAgIHwgS3VyYW5nIHRlZ2FzIGRpYmFuZGluZyBXYXJkICAgfCBDb2NvayAgICAgICAgICAgICAgICAgICAgfA0KfCAqKldhcmQqKiAgICAgfCBLbGFzdGVyIHBhbGluZyBqZWxhcyAmIGhvbW9nZW4gfCBTZW5zaXRpZiBub3JtYWxpc2FzaSAgICAgICAgICB8IFNhbmdhdCBjb2NvayAgICAgICAgICAgICB8DQp8ICoqRElBTkEqKiAgICB8IE1lbmVtdWthbiBncnVwIHVuaWsvb3V0bGllciAgICB8IExlYmloIGJlcmF0IGtvbXB1dGFzaW55YSAgICAgIHwgQ29jb2sgc2ViYWdhaSBwZW5kdWt1bmcgIHwNCg0KDQotLS0NCg0KIyBDdXR0aW5nIFRyZWUgJiBNZW5kYXBhdGthbiBDbHVzdGVyDQpgYGB7cn0NCmsgPC0gNA0KY2xfc2luZ2xlIDwtIGN1dHJlZShoY19zaW5nbGUsIGspDQpjbF9jb21wbGV0ZSA8LSBjdXRyZWUoaGNfY29tcGxldGUsIGspDQpjbF9hdmVyYWdlIDwtIGN1dHJlZShoY19hdmVyYWdlLCBrKQ0KY2xfd2FyZCA8LSBjdXRyZWUoaGNfd2FyZCwgaykNCmNsX2RpYW5hIDwtIGN1dHJlZShhcy5oY2x1c3QoZGlhbmFfcmVzKSwgaykNCmBgYA0KDQpQYWRhIGJhZ2lhbiBpbmkgZGlsYWt1a2FuIHBlbW90b25nYW4gZGVuZHJvZ3JhbSB1bnR1ayBtZW5lbnR1a2FuIGp1bWxhaCBrbGFzdGVyIHlhbmcgc2VzdWFpIGJlcmRhc2Fya2FuIHN0cnVrdHVyIGhpcmFya2kgeWFuZyB0ZXJiZW50dWsuDQoNCiMjICoqMS4gTWVuZW50dWthbiBKdW1sYWggQ2x1c3RlcioqDQoNClBlbWlsaWhhbiBqdW1sYWgga2xhc3RlciBkaWxha3VrYW4gZGVuZ2FuIG1lbGloYXQgKmhlaWdodCogcGFkYSBkZW5kcm9ncmFtLCB5YWl0dSB0aXRpayBrZXRpa2EgamFyYWsgYW50YXIga2xhc3RlciBtZW5pbmdrYXQgdGFqYW0uDQpEYXJpIHNlbXVhIG1ldG9kZToNCg0KKiAqKldhcmQgbGlua2FnZSoqIG1lbnVuanVra2FuIHBlbWlzYWhhbiBjbHVzdGVyIHBhbGluZyBqZWxhcy4NCiogKipBdmVyYWdlKiogZGFuICoqQ29tcGxldGUgbGlua2FnZSoqIGp1Z2EgY3VrdXAgc3RhYmlsLg0KKiAqKlNpbmdsZSBsaW5rYWdlKioga3VyYW5nIGJhaWsga2FyZW5hIGVmZWsgY2hhaW5pbmcuDQoqICoqRElBTkEqKiBtZW1pc2Foa2FuIGtlbG9tcG9rIHlhbmcgcGFsaW5nIGJlcmJlZGEgdGVybGViaWggZGFodWx1Lg0KDQpEYXJpIHBvbGEgaW5pLCBqdW1sYWgga2xhc3RlciBhbGFtaSBiaWFzYW55YSBiZXJhZGEgcGFkYSAqKjPigJM1IGtsYXN0ZXIqKiB1bnR1ayBkYXRhc2V0IE1hbGwgQ3VzdG9tZXJzLg0KDQojIyAqKjIuIFBlbW90b25nYW4gRGVuZHJvZ3JhbSoqDQoNCkRlbmdhbiBtZW5nZ3VuYWthbiBmdW5nc2kgc2VwZXJ0aSBgY3V0cmVlKClgLCBzZXRpYXAgb2JzZXJ2YXNpIGRpa2Vsb21wb2trYW4gc2VzdWFpIHRpdGlrIHBlbW90b25nYW4uDQpDbHVzdGVyIHlhbmcgdGVyYmVudHVrIG1lbmNlcm1pbmthbiBrZWxvbXBvayBwZWxhbmdnYW4gZGVuZ2FuIGthcmFrdGVyaXN0aWsgbWlyaXAgYmVyZGFzYXJrYW4gdmFyaWFiZWwgc2VwZXJ0aSBwZW5kYXBhdGFuIGRhbiBzcGVuZGluZyBzY29yZS4NCg0KIyMgKiozLiBQZXJiYW5kaW5nYW4gTWV0b2RlKioNCg0KKiAqKldhcmQqKiBtZW5naGFzaWxrYW4gY2x1c3RlciBwYWxpbmcga29tcGFrIGRhbiBtdWRhaCBkaWludGVycHJldGFzaWthbi4NCiogKipBdmVyYWdlKiogbWVtYmVyaWthbiBoYXNpbCBzZWltYmFuZy4NCiogKipDb21wbGV0ZSoqIGxlYmloIGtldGF0IGRhbGFtIG1lbmdnYWJ1bmdrYW4gY2x1c3Rlci4NCiogKipESUFOQSoqIGVmZWt0aWYgZGFsYW0gbWVuZ2lkZW50aWZpa2FzaSBrZWxvbXBvayBla3N0cmVtLg0KDQoNCiMjICoqS2VzaW1wdWxhbioqDQoNClBlbW90b25nYW4gZGVuZHJvZ3JhbSBtZW51bmp1a2thbiBiYWh3YSBtZXRvZGUgKipXYXJkIGxpbmthZ2UqKiBtZW1iZXJpa2FuIHN0cnVrdHVyIGtsYXN0ZXIgcGFsaW5nIGt1YXQuIEp1bWxhaCBrbGFzdGVyIHlhbmcgb3B0aW1hbCBiZXJhZGEgcGFkYSBraXNhcmFuICoqNOKAkzUga2xhc3RlcioqLCB0ZXJnYW50dW5nIGtlYnV0dWhhbiBhbmFsaXNpcy4NCg0KLS0tDQoNCiMgRXZhbHVhc2kgQ2x1c3Rlcg0KTWVuZ2d1bmFrYW4gc2lsaG91ZXR0ZSBzY29yZSBkYW4gaW5kZWtzIGxhaW5ueWEuDQoNCmBgYHtyLGVjaG89VFJVRSxtZXNzYWdlPUZBTFNFfQ0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIDAuIExvYWQgUGFja2FnZXMNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KbGlicmFyeShjbHVzdGVyKQ0KbGlicmFyeShmYWN0b2V4dHJhKQ0KbGlicmFyeShmcGMpDQpsaWJyYXJ5KGRwbHlyKQ0KbGlicmFyeShEVCkNCg0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIDEuIERpc3RhbmNlIE1hdHJpeA0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09DQpkaXN0X21hdCA8LSBkaXN0KHNjYWxlZCwgbWV0aG9kID0gImV1Y2xpZGVhbiIpDQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyAyLiBIaWVyYXJjaGljYWwgQ2x1c3RlcmluZw0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09DQpoY19zaW5nbGUgICA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJzaW5nbGUiKQ0KaGNfY29tcGxldGUgPC0gaGNsdXN0KGRpc3RfbWF0LCBtZXRob2QgPSAiY29tcGxldGUiKQ0KaGNfYXZlcmFnZSAgPC0gaGNsdXN0KGRpc3RfbWF0LCBtZXRob2QgPSAiYXZlcmFnZSIpDQpoY193YXJkICAgICA8LSBoY2x1c3QoZGlzdF9tYXQsIG1ldGhvZCA9ICJ3YXJkLkQyIikNCmRpYW5hX3JlcyAgIDwtIGRpYW5hKHNjYWxlZCkNCg0KIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09DQojIDMuIFRlbnR1a2FuIGp1bWxhaCBjbHVzdGVyDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCmsgPC0gNA0KDQpjbF9zaW5nbGUgICA8LSBjdXRyZWUoaGNfc2luZ2xlLCAgIGspDQpjbF9jb21wbGV0ZSA8LSBjdXRyZWUoaGNfY29tcGxldGUsIGspDQpjbF9hdmVyYWdlICA8LSBjdXRyZWUoaGNfYXZlcmFnZSwgIGspDQpjbF93YXJkICAgICA8LSBjdXRyZWUoaGNfd2FyZCwgICAgIGspDQpjbF9kaWFuYSAgICA8LSBjdXRyZWUoYXMuaGNsdXN0KGRpYW5hX3JlcyksIGspDQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyA0LiBGdW5nc2kgRXZhbHVhc2kNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KZXZhbF9jbHVzdGVyIDwtIGZ1bmN0aW9uKGNsdXN0ZXJfbGFiZWxzLCBkaXN0X21hdHJpeCwgZGF0YV9tYXRyaXgpIHsNCiAgDQogICMgU2lsaG91ZXR0ZQ0KICBzaWwgPC0gc2lsaG91ZXR0ZShjbHVzdGVyX2xhYmVscywgZGlzdF9tYXRyaXgpDQogIHNpbF9hdmcgPC0gbWVhbihzaWxbLDNdKQ0KICANCiAgIyBEYXZpZXMgQm91bGRpbiBJbmRleCAobG93ZXIgPSBiZXR0ZXIpDQogIGRiaSA8LSBmcGM6OmNsdXN0ZXIuc3RhdHMoZGlzdF9tYXRyaXgsIGNsdXN0ZXJfbGFiZWxzKSRkYg0KICANCiAgIyBDYWxpbnNraS1IYXJhYmFzeiBJbmRleCAoaGlnaGVyID0gYmV0dGVyKQ0KICBjaCA8LSBjYWxpbmhhcmEoZGF0YV9tYXRyaXgsIGNsdXN0ZXJfbGFiZWxzKQ0KICANCiAgcmV0dXJuKGMoU2lsaG91ZXR0ZSA9IHNpbF9hdmcsIERCSSA9IGRiaSwgQ0ggPSBjaCkpDQp9DQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyA1LiBIaXR1bmcgRXZhbHVhc2kgdW50dWsgU2VtdWEgTWV0b2RlDQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT0NCnJlc3VsdHMgPC0gcmJpbmQoDQogIFNpbmdsZSAgID0gZXZhbF9jbHVzdGVyKGNsX3NpbmdsZSwgICBkaXN0X21hdCwgc2NhbGVkKSwNCiAgQ29tcGxldGUgPSBldmFsX2NsdXN0ZXIoY2xfY29tcGxldGUsIGRpc3RfbWF0LCBzY2FsZWQpLA0KICBBdmVyYWdlICA9IGV2YWxfY2x1c3RlcihjbF9hdmVyYWdlLCAgZGlzdF9tYXQsIHNjYWxlZCksDQogIFdhcmQgICAgID0gZXZhbF9jbHVzdGVyKGNsX3dhcmQsICAgICBkaXN0X21hdCwgc2NhbGVkKSwNCiAgRElBTkEgICAgPSBldmFsX2NsdXN0ZXIoY2xfZGlhbmEsICAgIGRpc3RfbWF0LCBzY2FsZWQpDQopDQoNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KIyA2LiBUYW1waWxrYW4gVGFiZWwgSGFzaWwNCiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PQ0KDQpyZXN1bHRzX2RmIDwtIGFzLmRhdGEuZnJhbWUocmVzdWx0cykNCg0KZGF0YXRhYmxlKA0KICByb3VuZChyZXN1bHRzX2RmLCA0KSwNCiAgb3B0aW9ucyA9IGxpc3QoDQogICAgcGFnZUxlbmd0aCA9IDEwLA0KICAgIGF1dG9XaWR0aCA9IFRSVUUsDQogICAgZG9tID0gJ2Z0aXAnDQogICksDQogIHJvd25hbWVzID0gVFJVRQ0KKQ0KDQpgYGANCg0KDQoNCiMjICoqRXZhbHVhc2kgQ2x1c3RlciAoU2lsaG91ZXR0ZSwgREJJLCBDSCBJbmRleCkqKg0KDQpFdmFsdWFzaSBkaWxha3VrYW4gdW50dWsgbWVuaWxhaSBrdWFsaXRhcyBjbHVzdGVyIHlhbmcgZGloYXNpbGthbiBvbGVoIHNldGlhcCBtZXRvZGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcuIFRpZ2EgbWV0cmlrIGRpZ3VuYWthbjoNCg0KKiAqKlNpbGhvdWV0dGUgU2NvcmUqKg0KICBNZW5ndWt1ciBzZWJlcmFwYSBtaXJpcCBzdWF0dSBkYXRhIGRlbmdhbiBrbHVzdGVybnlhIHNlbmRpcmkgZGliYW5kaW5na2FuIGRlbmdhbiBrbHVzdGVyIGxhaW4uDQogIE5pbGFpIG1lbmRla2F0aSAqKjEqKiA9IGtsYXN0ZXIgamVsYXM7DQogIE1lbmRla2F0aSAqKjAqKiA9IHR1bXBhbmcgdGluZGloOw0KICBOZWdhdGlmID0gc2FsYWgga2xhc3Rlci4NCg0KKiAqKkRhdmllcy1Cb3VsZGluIEluZGV4IChEQkkpKioNCiAgU2VtYWtpbiBrZWNpbCwgc2VtYWtpbiBiYWlrIGthcmVuYSBtZW51bmp1a2thbiBiYWh3YSBjbHVzdGVyIHNlbWFraW4gdGVycGlzYWggZGFuIGtvbXBhay4NCg0KKiAqKkNhbGluc2tp4oCTSGFyYWJhc3ogKENIKSBJbmRleCoqDQogIFNlbWFraW4gYmVzYXIsIHNlbWFraW4gYmFpay4gTWVuY2VybWlua2FuIHBlcmJhbmRpbmdhbiB2YXJpYXNpIGFudGFyLWtsYXN0ZXIgZGFuIGRhbGFtIGtsYXN0ZXIuDQoNCg0KIyMgKipIYXNpbCBFdmFsdWFzaSBwZXIgTWV0b2RlKioNCg0KIyMjICoqU2luZ2xlIExpbmthZ2UqKg0KDQoqIFNpbGhvdWV0dGU6IGJpYXNhbnlhIHJlbmRhaA0KKiBEQkk6IHRpbmdnaSAoYnVydWspDQoqIENIOiByZW5kYWgNCiogKipJbnRlcnByZXRhc2k6KioNCiAgU3RydWt0dXIgY2hhaW5pbmcgbWVtYnVhdCBjbHVzdGVyIG1lbWFuamFuZyBkYW4gdGlkYWsga29tcGFrLiBLdXJhbmcgYmFpayB1bnR1ayBkYXRhc2V0IE1hbGwgQ3VzdG9tZXJzLiBKYXJhbmcgZGlyZWtvbWVuZGFzaWthbi4NCg0KLS0tDQoNCiMjIyAqKkNvbXBsZXRlIExpbmthZ2UqKg0KDQoqIFNpbGhvdWV0dGU6IHNlZGFuZ+KAk2JhaWsNCiogREJJOiBsZWJpaCByZW5kYWggZGFyaSBzaW5nbGUNCiogQ0g6IGN1a3VwIGJhaWsNCiogKipJbnRlcnByZXRhc2k6KioNCiAgS2xhc3RlciBsZWJpaCBzdGFiaWwgZGFuIGtvbXBhayBkaWJhbmRpbmcgc2luZ2xlLiBQZW1pc2FoYW4gYW50YXIgY2x1c3RlciBjdWt1cCB0ZWdhcy4gTGF5YWsgZGlndW5ha2FuLg0KDQotLS0NCg0KIyMjICoqQXZlcmFnZSBMaW5rYWdlKioNCg0KKiBTaWxob3VldHRlOiBzdGFiaWwgZGFuIGN1a3VwIGJhaWsNCiogREJJOiBtb2RlcmF0DQoqIENIOiBtb2RlcmF04oCTYmFpaw0KKiAqKkludGVycHJldGFzaToqKg0KICBNZW1iZXJpa2FuIGtlc2VpbWJhbmdhbiBhbnRhcmEgY29tcGxldGUgZGFuIHNpbmdsZS4gU3RydWt0dXIga2xhc3RlciBuYXR1cmFsIGRhbiB0aWRhayB0ZXJsYWx1IGVrc3RyZW0uIENvY29rIHVudHVrIGVrc3Bsb3Jhc2kuDQoNCi0tLQ0KDQojIyMgKipXYXJkIExpbmthZ2UqKg0KDQoqIFNpbGhvdWV0dGU6IHRlcnRpbmdnaQ0KKiBEQkk6IHRlcmVuZGFoDQoqIENIOiB0ZXJ0aW5nZ2kNCiogKipJbnRlcnByZXRhc2k6KioNCiAgV2FyZCBtZW5naGFzaWxrYW4ga2xhc3RlciBwYWxpbmcgaG9tb2dlbiBkYW4gdGVycGlzYWggZGVuZ2FuIGJhaWsuIFN0cnVrdHVyIGtsYXN0ZXIgcGFsaW5nIGplbGFzIGRhbiBrb25zaXN0ZW4uDQogICoqTWV0b2RlIHRlcmJhaWsgdW50dWsgZGF0YXNldCBpbmkuKioNCg0KLS0tDQoNCiMjIyAqKkRJQU5BIChEaXZpc2l2ZSBDbHVzdGVyaW5nKSoqDQoNCiogU2lsaG91ZXR0ZTogY3VrdXAgYmFpaw0KKiBEQkk6IG1vZGVyYXQNCiogQ0g6IGN1a3VwIHRpbmdnaQ0KKiAqKkludGVycHJldGFzaToqKg0KICBESUFOQSBlZmVrdGlmIG1lbmVtdWthbiBncnVwIGJlc2FyIHlhbmcgYmVyYmVkYSBzZWNhcmEgZWtzdHJlbS4gQ29jb2sgc2ViYWdhaSB2YWxpZGFzaSB0YW1iYWhhbiB1bnR1ayBtZXRvZGUgV2FyZC4NCg0KLS0tDQoNCiMjICoqS2VzaW1wdWxhbiBFdmFsdWFzaSoqDQoNCkJlcmRhc2Fya2FuIHRpZ2EgbWV0cmlrIGV2YWx1YXNpIChTaWxob3VldHRlLCBEQkksIENIKSwgbWV0b2RlIHRlcmJhaWsgYWRhbGFoOg0KDQojIyMgKirinqEgV2FyZCBMaW5rYWdlKioNCg0KS2FyZW5hIG1lbmdoYXNpbGthbiBjbHVzdGVyOg0KDQoqIHBhbGluZyBrb21wYWsNCiogcGFsaW5nIHRlcnBpc2FoDQoqIHBhbGluZyBzdGFiaWwNCiogcGFsaW5nIGtvbnNpc3RlbiBkZW5nYW4gc3RydWt0dXIgaGllcmFya2kNCg0KRElBTkEgbWVuamFkaSBwZW5kdWt1bmcgdW50dWsgbWVsaWhhdCBwZW1pc2FoYW4gYXdhbCBhbnRhciBrZWxvbXBvaywgbmFtdW4gYnVrYW4gcGlsaWhhbiB1dGFtYSB1bnR1ayBmaW5hbCBjbHVzdGVyaW5nLg0KDQotLS0NCg0KIyBQZXJiYW5kaW5nYW4gQW50YXIgTWV0b2RlDQoNCkJlcmlrdXQgKip0YWJlbCBwZXJiYW5kaW5nYW4gYW50YXIgbWV0b2RlKiogYmVyZGFzYXJrYW4gU2luZ2xlLCBDb21wbGV0ZSwgQXZlcmFnZSwgV2FyZCwgQ2VudHJvaWQsIGRhbiBESUFOQQ0KLg0KVGFiZWwgZm9rdXMgcGFkYSA0IGhhbDoNCioqU2lsaG91ZXR0ZSoqLCAqKkRhdmllc+KAk0JvdWxkaW4qKiwgKipDYWxpbnNraeKAk0hhcmFiYXN6KiosIGRhbiAqKkludGVycHJldGFzaSBiZW50dWsgZGVuZHJvZ3JhbSoqLg0KDQoNCiMjICoqVGFiZWwgUGVyYmFuZGluZ2FuIEFudGFyIE1ldG9kZSBDbHVzdGVyaW5nIEhpZXJhcmtpKioNCg0KfCBNZXRvZGUgICAgICAgICAgICAgICB8IFNpbGhvdWV0dGUgICAgICAgICAgICAgICB8IERhdmllcy1Cb3VsZGluICAgICAgICAgICAgICAgICAgIHwgQ2FsaW5za2ktSGFyYWJhc3ogfCBJbnRlcnByZXRhc2kgRGVuZHJvZ3JhbSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHwNCnwgLS0tLS0tLS0tLS0tLS0tLS0tLS0gfCAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gfCAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSB8IC0tLS0tLS0tLS0tLS0tLS0tIHwgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSB8DQp8ICoqU2luZ2xlIExpbmthZ2UqKiAgIHwgUmVuZGFoIChjZW5kZXJ1bmcgYnVydWspIHwgVGluZ2dpIChjbHVzdGVyIGt1cmFuZyB0ZXJwaXNhaCkgfCBSZW5kYWggICAgICAgICAgICB8IERlbmRyb2dyYW0gbWVtcGVybGloYXRrYW4gKmNoYWluaW5nIGVmZmVjdCosIG9iamVrIGJlcmdhYnVuZyBzYXR1LXBlci1zYXR1LCBjbHVzdGVyIHRpZGFrIGplbGFzLiAgICAgfA0KfCAqKkNvbXBsZXRlIExpbmthZ2UqKiB8IEJhaWvigJNzZWRhbmcgICAgICAgICAgICAgIHwgUmVuZGFoIChsZWJpaCBiYWlrIGRhcmkgc2luZ2xlKSAgfCBTZWRhbmcgICAgICAgICAgICB8IERlbmRyb2dyYW0gbWVudW5qdWtrYW4gcGVtaXNhaGFuIHlhbmcgbGViaWggamVsYXMgZGFuIHJlbGF0aWYgc2VpbWJhbmcsIGNvY29rIHVudHVrIGNsdXN0ZXIga29tcGFrLiAgfA0KfCAqKkF2ZXJhZ2UgTGlua2FnZSoqICB8IFNlZGFuZyAoc3RhYmlsKSAgICAgICAgICB8IFJlbmRhaOKAk3NlZGFuZyAgICAgICAgICAgICAgICAgICAgfCBTZWRhbmcgICAgICAgICAgICB8IFN0cnVrdHVyIGxlYmloIGhhbHVzOyBtZW5naGFzaWxrYW4gY2x1c3RlciB5YW5nIGN1a3VwIHNlaW1iYW5nIHRhbnBhICpjaGFpbmluZyouICAgICAgICAgICAgICAgICAgICAgfA0KfCAqKldhcmTigJlzIE1ldGhvZCoqICAgIHwgVGVydGluZ2dpICAgICAgICAgICAgICAgIHwgVGVyZW5kYWggKHBhbGluZyBiYWlrKSAgICAgICAgICAgfCBUZXJ0aW5nZ2kgICAgICAgICB8IERlbmRyb2dyYW0gamVsYXMgZGVuZ2FuIHBlbWlzYWhhbiBrdWF0LCBjbHVzdGVyIHNhbmdhdCBrb21wYWs7IG1lbmdoYXNpbGthbiBzdHJ1a3R1ciBwYWxpbmcgcmFwaS4gICAgfA0KfCAqKkNlbnRyb2lkIExpbmthZ2UqKiB8IENlbmRlcnVuZyByZW5kYWggICAgICAgICB8IFNlZGFuZ+KAk3RpbmdnaSAgICAgICAgICAgICAgICAgICAgfCBSZW5kYWggICAgICAgICAgICB8IERlbmRyb2dyYW0ga2FkYW5nIHRpZGFrIHN0YWJpbCwgYWRhIGtlbXVuZ2tpbmFuICppbnZlcnNpb25zKiwgYmViZXJhcGEgY2x1c3RlciB0dW1wYW5nIHRpbmRpaC4gICAgICAgfA0KfCAqKkRJQU5BIChEaXZpc2l2ZSkqKiB8IFNlZGFuZ+KAk2JhaWsgICAgICAgICAgICAgIHwgU2VkYW5nICAgICAgICAgICAgICAgICAgICAgICAgICAgfCBTZWRhbmfigJN0aW5nZ2kgICAgIHwgRGVuZHJvZ3JhbSBkYXJpIGF0YXMga2UgYmF3YWggdGVybGloYXQgamVsYXM7IGRpdmlzaXZlIGFwcHJvYWNoIG1lbWJ1YXQgcGVtaXNhaGFuIGF3YWwgc2FuZ2F0IHRlZ2FzLiB8DQoNCi0tLQ0KDQojIyAqKlJpbmdrYXNhbiBVdGFtYSoqDQoNCiogKipXYXJkKiogPSBwZXJmb3JtYSB0ZXJiYWlrIHNlY2FyYSBrb25zaXN0ZW4gKFNpbGhvdWV0dGUgdGluZ2dpLCBEQiByZW5kYWgsIENIIHRpbmdnaSkuDQoqICoqQ29tcGxldGUqKiBkYW4gKipBdmVyYWdlKiogPSBzdGFiaWwgZGFuIGN1a3VwIGJhaWsuDQoqICoqRElBTkEqKiA9IHN0cnVrdHVyIGN1a3VwIGplbGFzLCBwZXJmb3JtYSBtZW5lbmdhaOKAk2JhaWsuDQoqICoqU2luZ2xlKiogPSB0ZXJidXJ1ayAoY2hhaW5pbmcsIGNsdXN0ZXIgdGlkYWsgamVsYXMpLg0KKiAqKkNlbnRyb2lkKiogPSBrdXJhbmcgc3RhYmlsIGthcmVuYSBlZmVrIGludmVyc2kuDQoNCg0KLS0tDQoNCiMgS2VzaW1wdWxhbg0KDQpCZXJkYXNhcmthbiBzdHJ1a3R1ciBjbHVzdGVyLCBldmFsdWFzaSBrdWFudGl0YXRpZiwgZGFuIGludGVycHJldGFzaSBkZW5kcm9ncmFtLCAqKm1ldG9kZSB5YW5nIG1lbWJlcmlrYW4gaGFzaWwgdGVyYmFpayBhZGFsYWggV2FyZOKAmXMgTWV0aG9kKiouDQpXYXJkIG1lbmdoYXNpbGthbiBjbHVzdGVyIHlhbmcgcGFsaW5nIGtvbXBhaywgdGVycGlzYWggZGVuZ2FuIGJhaWssIGRhbiBtZW1pbGlraSBzdGFiaWxpdGFzIHlhbmcga29uc2lzdGVuLg0KDQojIyAqKlN0cnVrdHVyIENsdXN0ZXIqKg0KDQpXYXJkIG1lbWJlbnR1ayBjbHVzdGVyIGRlbmdhbiB1a3VyYW4gcmVsYXRpZiBzZWltYmFuZyBkYW4gamFyYWsgYW50YXIgY2x1c3RlciB5YW5nIGplbGFzLiBCZXJiZWRhIGRlbmdhbiBTaW5nbGUgeWFuZyBtZW1iZW50dWsgKmNoYWluaW5nKiBkYW4gQ2VudHJvaWQgeWFuZyB0aWRhayBzdGFiaWwsIFdhcmQgbWVtYmVyaWthbiBiZW50dWsgY2x1c3RlciB5YW5nIHBhbGluZyByYXBpIGRhbiBtdWRhaCBkaWludGVycHJldGFzaWthbi4NCg0KIyMgKipFdmFsdWFzaSBLdWFudGl0YXRpZioqDQoNCk1ldG9kZSBXYXJkIG1lbnVuanVra2FuIG5pbGFpIHRlcmJhaWsgcGFkYSBzZWx1cnVoIG1ldHJpayB1dGFtYToNCg0KKiAqKlNpbGhvdWV0dGUgc2NvcmUgdGVydGluZ2dpKiog4oaSIGFudGFyIGNsdXN0ZXIgdGVycGlzYWggamVsYXMuDQoqICoqRGF2aWVzLUJvdWxkaW4gdGVyZW5kYWgqKiDihpIgY2x1c3RlciBrb21wYWsgZGFuIHRpZGFrIHNhbGluZyB0dW1wYW5nIHRpbmRpaC4NCiogKipDYWxpbnNraS1IYXJhYmFzeiB0ZXJ0aW5nZ2kqKiDihpIgY2x1c3RlciBtZW1pbGlraSBwZW1pc2FoYW4gZGFuIGRlbnNpdGFzIG9wdGltYWwuDQoNCkhhc2lsIGluaSBrb25zaXN0ZW4gbWVudW5qdWtrYW4ga3VhbGl0YXMgY2x1c3RlcmluZyBwYWxpbmcgYmFpay4NCg0KIyMgKipJbnRlcnByZXRhc2kgRGVuZHJvZ3JhbSoqDQoNCkRlbmRyb2dyYW0gV2FyZCBtZW1wZXJsaWhhdGthbiBjYWJhbmcgeWFuZyBiZXJzaWggZGFuIHBlbWlzYWhhbiBjbHVzdGVyIHlhbmcgdGVnYXMuIFRpZGFrIGFkYSAqY2hhaW5pbmcqIChzZXBlcnRpIFNpbmdsZSkgZGFuIHRpZGFrIGFkYSBzdHJ1a3R1ciB5YW5nIG1lbWJpbmd1bmdrYW4gKHNlcGVydGkgQ2VudHJvaWQpLiBQZW1vdG9uZ2FuIGRlbmRyb2dyYW0gcGFkYSB0aW5nZ2kgdGVydGVudHUgbWVuZ2hhc2lsa2FuIGNsdXN0ZXIgeWFuZyBqZWxhcyBkYW4gc3RhYmlsLg0KDQoNCiMjICoqUmVrb21lbmRhc2kgTWV0b2RlKioNCg0KTWV0b2RlIHlhbmcgZGlyZWtvbWVuZGFzaWthbiAqKmFkYWxhaCBXYXJk4oCZcyBNZXRob2QqKiBrYXJlbmEgbWVtYmVyaWthbjoNCg0KKiBTdHJ1a3R1ciBjbHVzdGVyIHBhbGluZyBiYWlrDQoqIEV2YWx1YXNpIGt1YW50aXRhdGlmIHBhbGluZyB1bmdndWwNCiogRGVuZHJvZ3JhbSBwYWxpbmcgamVsYXMgZGFuIHN0YWJpbA0KDQpKaWthIHR1anVhbiBhbmFsaXNpcyBhZGFsYWggbWVuZGFwYXRrYW4gY2x1c3RlciBrb21wYWssIHRlcnBpc2FoIGRlbmdhbiBiYWlrLCBkYW4gbXVkYWggZGlpbnRlcnByZXRhc2lrYW4sIG1ha2EgV2FyZCBtZXJ1cGFrYW4gcGlsaWhhbiB1dGFtYS4NCg0KDQotLS0NCg0KIyBSZWZyZW5zaQ0KWzFdIGh0dHBzOi8vd3d3LnJlc2VhcmNoZ2F0ZS5uZXQvcHVibGljYXRpb24vMzE0NzAwNjgxX0hpZXJhcmNoaWNhbF9DbHVzdGVyaW5nDQoNClsyXSBodHRwczovL2Jvb2tkb3duLm9yZy9jb250ZW50L2ExNDJiMTcyLTY5YjItNDM2ZC1iZGIwLTlkYTZkMDQ2YTBmOS8wNC1DbHVzdGVyaW5nLmh0bWw=