rm(list=ls(all=T))
Sys.setlocale("LC_ALL","C")
[1] "C"
options(digits=4, scipen=12)
library(dplyr)
library(caret)



1. 資料常態化

1.1 資料摘要

Read the dataset AirlinesCluster.csv into R and call it “airlines”. Looking at the summary of airlines,

A = read.csv('data/AirlinesCluster.csv')
summary(A)
    Balance          QualMiles       BonusMiles       BonusTrans    FlightMiles     FlightTrans   
 Min.   :      0   Min.   :    0   Min.   :     0   Min.   : 0.0   Min.   :    0   Min.   : 0.00  
 1st Qu.:  18528   1st Qu.:    0   1st Qu.:  1250   1st Qu.: 3.0   1st Qu.:    0   1st Qu.: 0.00  
 Median :  43097   Median :    0   Median :  7171   Median :12.0   Median :    0   Median : 0.00  
 Mean   :  73601   Mean   :  144   Mean   : 17145   Mean   :11.6   Mean   :  460   Mean   : 1.37  
 3rd Qu.:  92404   3rd Qu.:    0   3rd Qu.: 23800   3rd Qu.:17.0   3rd Qu.:  311   3rd Qu.: 1.00  
 Max.   :1704838   Max.   :11148   Max.   :263685   Max.   :86.0   Max.   :30817   Max.   :53.00  
 DaysSinceEnroll
 Min.   :   2   
 1st Qu.:2330   
 Median :4096   
 Mean   :4119   
 3rd Qu.:5790   
 Max.   :8296   
colMeans(A) %>% sort
    FlightTrans      BonusTrans       QualMiles     FlightMiles DaysSinceEnroll      BonusMiles 
          1.374          11.602         144.115         460.056        4118.559       17144.846 
        Balance 
      73601.328 

which TWO variables have (on average) the smallest values?

  • FlightTrans
  • BonusTrans

Which TWO variables have (on average) the largest values?

  • Balance
  • BonusMiles
1.2 為甚麼要做資料常態化

In this problem, we will normalize our data before we run the clustering algorithms.

Why is it important to normalize the data before clustering?

  • If we don’t normalize the data, the variables that are on a larger scale will contribute much more to the distance calculation, and thus will dominate the clustering.
  • 資料常態化後,可以將變數間的影響力調整,不會讓較大的變數擁有優勢
1.3 使用caret套件做資料常態化

Let’s go ahead and normalize our data. You can normalize the variables in a data frame by using the preProcess function in the “caret” package. You should already have this package installed from Week 4, but if not, go ahead and install it with install.packages(“caret”). Then load the package with library(caret).

Now, create a normalized data frame called “airlinesNorm” by running the following commands:

preproc = preProcess(airlines)

airlinesNorm = predict(preproc, airlines)

The first command pre-processes the data, and the second command performs the normalization. If you look at the summary of airlinesNorm, you should see that all of the variables now have mean zero. You can also see that each of the variables has standard deviation 1 by using the sd() function.

library(caret)
preproc = preProcess(A)
AN = predict(preproc, A)  
summary(AN)
    Balance         QualMiles        BonusMiles       BonusTrans      FlightMiles      FlightTrans    
 Min.   :-0.730   Min.   :-0.186   Min.   :-0.710   Min.   :-1.208   Min.   :-0.329   Min.   :-0.362  
 1st Qu.:-0.546   1st Qu.:-0.186   1st Qu.:-0.658   1st Qu.:-0.896   1st Qu.:-0.329   1st Qu.:-0.362  
 Median :-0.303   Median :-0.186   Median :-0.413   Median : 0.041   Median :-0.329   Median :-0.362  
 Mean   : 0.000   Mean   : 0.000   Mean   : 0.000   Mean   : 0.000   Mean   : 0.000   Mean   : 0.000  
 3rd Qu.: 0.187   3rd Qu.:-0.186   3rd Qu.: 0.276   3rd Qu.: 0.562   3rd Qu.:-0.106   3rd Qu.:-0.098  
 Max.   :16.187   Max.   :14.223   Max.   :10.208   Max.   : 7.747   Max.   :21.680   Max.   :13.610  
 DaysSinceEnroll  
 Min.   :-1.9934  
 1st Qu.:-0.8661  
 Median :-0.0109  
 Mean   : 0.0000  
 3rd Qu.: 0.8096  
 Max.   : 2.0228  
apply(AN, 2, mean) %>% round(3)
        Balance       QualMiles      BonusMiles      BonusTrans     FlightMiles     FlightTrans 
              0               0               0               0               0               0 
DaysSinceEnroll 
              0 
apply(AN, 2, sd) %>% round(3)
        Balance       QualMiles      BonusMiles      BonusTrans     FlightMiles     FlightTrans 
              1               1               1               1               1               1 
DaysSinceEnroll 
              1 
apply(AN, 2, max) %>% sort
DaysSinceEnroll      BonusTrans      BonusMiles     FlightTrans       QualMiles         Balance 
          2.023           7.747          10.208          13.610          14.223          16.187 
    FlightMiles 
         21.680 

In the normalized data, which variable has the largest maximum value?

  • FlightMiles
apply(AN, 2, min) %>% sort
DaysSinceEnroll      BonusTrans         Balance      BonusMiles     FlightTrans     FlightMiles 
        -1.9934         -1.2081         -0.7303         -0.7099         -0.3621         -0.3286 
      QualMiles 
        -0.1863 

In the normalized data, which variable has the smallest minimum value?

  • DaysSinceEnroll



2. 層級式集群分析

2.1 依據樹狀圖和應用需求決定群數

Compute the distances between data points (using euclidean distance) and then run the Hierarchical clustering algorithm (using method=“ward.D”) on the normalized data. It may take a few minutes for the commands to finish since the dataset has a large number of observations for hierarchical clustering.

Then, plot the dendrogram of the hierarchical clustering process. Suppose the airline is looking for somewhere between 2 and 10 clusters.

d = dist(AN,method="euclidean")
hc = hclust(d, method='ward.D')
plot(hc)

According to the dendrogram, which of the following is NOT a good choice for the number of clusters?

  • 6
  • 根據樹狀圖的Y軸,1300可以切兩群,800可以切三群,400可以切三群
2.2 分割群組

Suppose that after looking at the dendrogram and discussing with the marketing department, the airline decides to proceed with 5 clusters. Divide the data points into 5 clusters by using the cutree function.

kg = cutree(hc, k=5)
table(kg)
kg
   1    2    3    4    5 
 776  519  494  868 1342 

How many data points are in Cluster 1?

  • 776
2.3 從區隔變數的平均值推論族群特性

Now, use tapply to compare the average values in each of the variables for the 5 clusters (the centroids of the clusters). You may want to compute the average values of the unnormalized data so that it is easier to interpret. You can do this for the variable “Balance” with the following command:

tapply(airlines$Balance, clusterGroups, mean)

sapply(split(A,kg), colMeans) %>% round(2) 
                       1         2         3        4        5
Balance         57866.90 110669.27 198191.57 52335.91 36255.91
QualMiles           0.64   1065.98     30.35     4.85     2.51
BonusMiles      10360.12  22881.76  55795.86 20788.77  2264.79
BonusTrans         10.82     18.23     19.66    17.09     2.97
FlightMiles        83.18   2613.42    327.68   111.57   119.32
FlightTrans         0.30      7.40      1.07     0.34     0.44
DaysSinceEnroll  6235.36   4402.41   5615.71  2840.82  3060.08

Compared to the other clusters, Cluster 1 has the largest average values in which variables (if any)? Select all that apply.

  • DaysSinceEnroll

How would you describe the customers in Cluster 1?

  • Infrequent but loyal customers.
2.4 Cluster 2
split(AN,kg) %>% sapply(colMeans) %>% round(2)
                    1    2     3     4     5
Balance         -0.16 0.37  1.24 -0.21 -0.37
QualMiles       -0.19 1.19 -0.15 -0.18 -0.18
BonusMiles      -0.28 0.24  1.60  0.15 -0.62
BonusTrans      -0.08 0.69  0.84  0.57 -0.90
FlightMiles     -0.27 1.54 -0.09 -0.25 -0.24
FlightTrans     -0.28 1.59 -0.08 -0.27 -0.25
DaysSinceEnroll  1.03 0.14  0.72 -0.62 -0.51
par(cex=0.8)
split(AN,kg) %>% sapply(colMeans) %>% barplot(beside=T,col=rainbow(7))
legend('topright',legend=colnames(A),fill=rainbow(7))

Compared to the other clusters, Cluster 2 has the largest average values in which variables (if any)? Select all that apply.

  • QualMiles
  • FlightMiles
  • FlightTrans

How would you describe the customers in Cluster 2?

  • Customers who have accumulated a large amount of miles, and the ones with the largest number of flight transactions.
2.5 Cluster 3

Compared to the other clusters, Cluster 3 has the largest average values in which variables (if any)? Select all that apply.

  • Balance
  • BonusMiles
  • BonusTrans

How would you describe the customers in Cluster 3?

  • Customers who have accumulated a large amount of miles, mostly through non-flight transactions.
2.6 Cluster 4

Compared to the other clusters, Cluster 4 has the largest average values in which variables (if any)? Select all that apply.

  • none

How would you describe the customers in Cluster 4?

  • Relatively new customers who seem to be accumulating miles, mostly through non-flight transactions.
2.7 Cluster 5

Compared to the other clusters, Cluster 5 has the largest average values in which variables (if any)? Select all that apply.

  • none

How would you describe the customers in Cluster 5?

  • Relatively new customers who don’t use the airline very often.

3. K-Means集群分析

3.1 K-Means集群分析

Now run the k-means clustering algorithm on the normalized data, again creating 5 clusters. Set the seed to 88 right before running the clustering algorithm, and set the argument iter.max to 1000.

set.seed(88)
km = kmeans(AN, 5, iter.max = 1000)
kg2 = km$cluster
table(kg2)
kg2
   1    2    3    4    5 
 408  141  993 1182 1275 

How many clusters have more than 1,000 observations?

  • cluster4and5
par(cex=0.8)
km$centers %>% round(2) %>% t %>% barplot(beside=T,col=rainbow(7))
legend('topright',legend=colnames(A),fill=rainbow(7))

3.2 Hierarchical和K-Means集群的對應關係

Now, compare the cluster centroids to each other either by dividing the data points into groups and then using tapply, or by looking at the output of kmeansClust\(centers, where "kmeansClust" is the name of the output of the kmeans function. (Note that the output of kmeansClust\)centers will be for the normalized data. If you want to look at the average values for the unnormalized data, you need to use tapply like we did for hierarchical clustering.)

table(Hierarchical=kg, KMeans=kg2)
            KMeans
Hierarchical    1    2    3    4    5
           1    4    0   98  673    1
           2   92  137  105   92   93
           3  300    4  132   58    0
           4   12    0  653   30  173
           5    0    0    5  329 1008

Do you expect Cluster 1 of the K-Means clustering output to necessarily be similar to Cluster 1 of the Hierarchical clustering output?

  • No, because cluster ordering is not meaningful in either k-means clustering or hierarchical clustering.
  • 集群的次序並非固定的,同比資料在kmeans和hierarchical可能有所不同。
  • 兩個模型背後運算的原理並不完全相同,因此在每群中還是會有些許不同。


【討論問題】

請你們為這五個族群各起一個名稱

  • 1 瞌睡顧客
  • 2 主力顧客
  • 3 潛在顧客
  • 4 沈睡顧客
  • 5 非目標客群

請你們為這五個族群各設計一個行銷策略

  • 1 瞌睡顧客:此群顧客的註冊時間偏長,在flightmile的表現偏差,但在bonus這塊累積很多,代表此群顧客日後有很大機會仍會來使用我們的服務,我們針對他們的行銷就是提升flightmile的表現,因此推出旅遊方案等,加速他們來使用我們服務的意願

  • 2 主力顧客:此群顧客註冊時間不長,算在成長中的顧客群,在各項類別的表驗都很好,針對此顧客群,要推出忠誠方案,透過累積里程數等提供們許多優惠和服務,留住這些成長客群。

  • 3 潛在顧客:此目標客群選擇我們航空公司的bonus,表示他們日後有可能來消費的意願,因此針對他們做出首飛特別服務或第一次飛行優惠,來吸引他們使用我們的服務。

  • 4 沈睡顧客:此目標客群,註冊時間偏長,但在其他各項表現偏差,推測可能轉向其他航空公司,針對這些顧客,我們可以先提供滿問卷調查送里程優惠,希望他們提供意見,為何後來不使用我們服務,接著可以推出老友回娘家,吸引他們回流。

  • 5 非目標客群:此客群可能是其他航空公司的忠實顧客,他們的轉換成本可能很高,因此我們不會針對此目標客群特別行銷,會將預算留給上述客群。

統計上最好的分群也是實務上最好的分群嗎?

  • 統計上針對<數字>提供給我們客觀的分析,但實務上考慮的變數可能更多,以航空公司來說,為我們分析好了上述類群,但我們可能要更多的細節下去做行銷,像是男女比、年齡等,第二點,實務上的分群可能還會牽涉到非數字的決策,像是航空公司的政策或是其他考量,有時候不是光看統計數字就能決定的,但不可否認,統計分群提供管理者一個直接客觀的結果,幫助管理者進行後面的決策。

除了考慮群間和群間距離之外,實務上的分群通常還需要考慮那些因素?

  • 群和群間的距離,是統計就模型區分出來的,但實務上的分群很多時候考量的不只是數字上的差別,以航空公司例子來說,我們看類別1和3,可能會覺得他們有所不同,但假如航空公司今天是要以註冊時間長短來行銷,那麼此時的分群有會不同,因此模型提供我們一個客觀的事實後,管理者分群時要配合公司的需求,或是成本和經濟效益上考量,做出來的決策或許有時候和統計數字上會有所不同。

```




LS0tDQp0aXRsZTogIkFTNi0yIOiIquepuuWFrOWPuOeahOW4guWgtOWNgOmalCINCmF1dGhvcjogIkdyb3VwIDIiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQo8YnI+DQoNCg0KKyDliKnnlKjpm4bnvqTliIbmnpDlgZrluILloLTljYDpmpQNCisg6LOH5paZ5bi45oWL5YyWDQorIOizh+aWmeimluimuuWMlg0KKyDml4/nvqTnibnmgKfoiIfooYzpirfnrZbnlaUNCisg6KGM6Yq35bel5YW3dnPooYzpirflsI3osaENCg0KDQpgYGB7ciBlY2hvPVQsIG1lc3NhZ2U9RiwgY2FjaGU9Riwgd2FybmluZz1GfQ0Kcm0obGlzdD1scyhhbGw9VCkpDQpTeXMuc2V0bG9jYWxlKCJMQ19BTEwiLCJDIikNCm9wdGlvbnMoZGlnaXRzPTQsIHNjaXBlbj0xMikNCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KGNhcmV0KQ0KYGBgDQo8YnI+DQoNCi0gLSAtDQoNCiMjIyAxLiDos4fmlpnluLjmhYvljJYNCg0KIyMjIyMgMS4xIOizh+aWmeaRmOimgQ0KUmVhZCB0aGUgZGF0YXNldCBBaXJsaW5lc0NsdXN0ZXIuY3N2IGludG8gUiBhbmQgY2FsbCBpdCAiYWlybGluZXMiLiBMb29raW5nIGF0IHRoZSBzdW1tYXJ5IG9mIGFpcmxpbmVzLCANCmBgYHtyfQ0KQSA9IHJlYWQuY3N2KCdkYXRhL0FpcmxpbmVzQ2x1c3Rlci5jc3YnKQ0Kc3VtbWFyeShBKQ0KYGBgDQpgYGB7cn0NCmNvbE1lYW5zKEEpICU+JSBzb3J0DQpgYGANCg0KX3doaWNoIFRXTyB2YXJpYWJsZXMgaGF2ZSAob24gYXZlcmFnZSkgdGhlIHNtYWxsZXN0IHZhbHVlcz9fDQoNCisgRmxpZ2h0VHJhbnMNCisgQm9udXNUcmFucw0KDQoNCl9XaGljaCBUV08gdmFyaWFibGVzIGhhdmUgKG9uIGF2ZXJhZ2UpIHRoZSBsYXJnZXN0IHZhbHVlcz9fDQoNCisgQmFsYW5jZQ0KKyBCb251c01pbGVzDQogDQoNCg0KIyMjIyMgMS4yIOeCuueUmum6vOimgeWBmuizh+aWmeW4uOaFi+WMlg0KSW4gdGhpcyBwcm9ibGVtLCB3ZSB3aWxsIG5vcm1hbGl6ZSBvdXIgZGF0YSBiZWZvcmUgd2UgcnVuIHRoZSBjbHVzdGVyaW5nIGFsZ29yaXRobXMuIA0KDQpfV2h5IGlzIGl0IGltcG9ydGFudCB0byBub3JtYWxpemUgdGhlIGRhdGEgYmVmb3JlIGNsdXN0ZXJpbmc/Xw0KDQorIElmIHdlIGRvbid0IG5vcm1hbGl6ZSB0aGUgZGF0YSwgdGhlIHZhcmlhYmxlcyB0aGF0IGFyZSBvbiBhIGxhcmdlciBzY2FsZSB3aWxsIGNvbnRyaWJ1dGUgbXVjaCBtb3JlIHRvIHRoZSBkaXN0YW5jZSBjYWxjdWxhdGlvbiwgYW5kIHRodXMgd2lsbCBkb21pbmF0ZSB0aGUgY2x1c3RlcmluZy4NCisg6LOH5paZ5bi45oWL5YyW5b6M77yM5Y+v5Lul5bCH6K6K5pW46ZaT55qE5b2x6Z+/5Yqb6Kq/5pW077yM5LiN5pyD6K6T6LyD5aSn55qE6K6K5pW45pOB5pyJ5YSq5YuiDQoNCiMjIyMjIDEuMyDkvb/nlKhjYXJldOWll+S7tuWBmuizh+aWmeW4uOaFi+WMlg0KTGV0J3MgZ28gYWhlYWQgYW5kIG5vcm1hbGl6ZSBvdXIgZGF0YS4gWW91IGNhbiBub3JtYWxpemUgdGhlIHZhcmlhYmxlcyBpbiBhIGRhdGEgZnJhbWUgYnkgdXNpbmcgdGhlIHByZVByb2Nlc3MgZnVuY3Rpb24gaW4gdGhlICJjYXJldCIgcGFja2FnZS4gWW91IHNob3VsZCBhbHJlYWR5IGhhdmUgdGhpcyBwYWNrYWdlIGluc3RhbGxlZCBmcm9tIFdlZWsgNCwgYnV0IGlmIG5vdCwgZ28gYWhlYWQgYW5kIGluc3RhbGwgaXQgd2l0aCBpbnN0YWxsLnBhY2thZ2VzKCJjYXJldCIpLiBUaGVuIGxvYWQgdGhlIHBhY2thZ2Ugd2l0aCBsaWJyYXJ5KGNhcmV0KS4NCg0KTm93LCBjcmVhdGUgYSBub3JtYWxpemVkIGRhdGEgZnJhbWUgY2FsbGVkICJhaXJsaW5lc05vcm0iIGJ5IHJ1bm5pbmcgdGhlIGZvbGxvd2luZyBjb21tYW5kczoNCg0KcHJlcHJvYyA9IHByZVByb2Nlc3MoYWlybGluZXMpDQoNCmFpcmxpbmVzTm9ybSA9IHByZWRpY3QocHJlcHJvYywgYWlybGluZXMpDQoNClRoZSBmaXJzdCBjb21tYW5kIHByZS1wcm9jZXNzZXMgdGhlIGRhdGEsIGFuZCB0aGUgc2Vjb25kIGNvbW1hbmQgcGVyZm9ybXMgdGhlIG5vcm1hbGl6YXRpb24uIElmIHlvdSBsb29rIGF0IHRoZSBzdW1tYXJ5IG9mIGFpcmxpbmVzTm9ybSwgeW91IHNob3VsZCBzZWUgdGhhdCBhbGwgb2YgdGhlIHZhcmlhYmxlcyBub3cgaGF2ZSBtZWFuIHplcm8uIFlvdSBjYW4gYWxzbyBzZWUgdGhhdCBlYWNoIG9mIHRoZSB2YXJpYWJsZXMgaGFzIHN0YW5kYXJkIGRldmlhdGlvbiAxIGJ5IHVzaW5nIHRoZSBzZCgpIGZ1bmN0aW9uLg0KDQpgYGB7cn0NCmxpYnJhcnkoY2FyZXQpDQpwcmVwcm9jID0gcHJlUHJvY2VzcyhBKQ0KQU4gPSBwcmVkaWN0KHByZXByb2MsIEEpICANCnN1bW1hcnkoQU4pDQphcHBseShBTiwgMiwgbWVhbikgJT4lIHJvdW5kKDMpDQphcHBseShBTiwgMiwgc2QpICU+JSByb3VuZCgzKQ0KYGBgDQoNCmBgYHtyfQ0KYXBwbHkoQU4sIDIsIG1heCkgJT4lIHNvcnQNCmBgYA0KDQpJbiB0aGUgbm9ybWFsaXplZCBkYXRhLCBfd2hpY2ggdmFyaWFibGUgaGFzIHRoZSBsYXJnZXN0IG1heGltdW0gdmFsdWU/Xw0KDQorIEZsaWdodE1pbGVzDQoNCg0KYGBge3J9DQphcHBseShBTiwgMiwgbWluKSAlPiUgc29ydA0KYGBgDQoNCkluIHRoZSBub3JtYWxpemVkIGRhdGEsIF93aGljaCB2YXJpYWJsZSBoYXMgdGhlIHNtYWxsZXN0IG1pbmltdW0gdmFsdWU/Xw0KDQorICBEYXlzU2luY2VFbnJvbGwNCg0KDQo8YnI+DQoNCi0gLSAtDQoNCiMjIyAyLiDlsaTntJrlvI/pm4bnvqTliIbmnpANCg0KIyMjIyMgMi4xIOS+neaTmuaoueeLgOWcluWSjOaHieeUqOmcgOaxguaxuuWumue+pOaVuA0KQ29tcHV0ZSB0aGUgZGlzdGFuY2VzIGJldHdlZW4gZGF0YSBwb2ludHMgKHVzaW5nIGV1Y2xpZGVhbiBkaXN0YW5jZSkgYW5kIHRoZW4gcnVuIHRoZSBIaWVyYXJjaGljYWwgY2x1c3RlcmluZyBhbGdvcml0aG0gKHVzaW5nIG1ldGhvZD0id2FyZC5EIikgb24gdGhlIG5vcm1hbGl6ZWQgZGF0YS4gSXQgbWF5IHRha2UgYSBmZXcgbWludXRlcyBmb3IgdGhlIGNvbW1hbmRzIHRvIGZpbmlzaCBzaW5jZSB0aGUgZGF0YXNldCBoYXMgYSBsYXJnZSBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zIGZvciBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4NCg0KVGhlbiwgcGxvdCB0aGUgZGVuZHJvZ3JhbSBvZiB0aGUgaGllcmFyY2hpY2FsIGNsdXN0ZXJpbmcgcHJvY2Vzcy4gU3VwcG9zZSB0aGUgYWlybGluZSBpcyBsb29raW5nIGZvciBzb21ld2hlcmUgYmV0d2VlbiAyIGFuZCAxMCBjbHVzdGVycy4gDQpgYGB7cn0NCmQgPSBkaXN0KEFOLG1ldGhvZD0iZXVjbGlkZWFuIikNCmhjID0gaGNsdXN0KGQsIG1ldGhvZD0nd2FyZC5EJykNCnBsb3QoaGMpDQpgYGANCkFjY29yZGluZyB0byB0aGUgZGVuZHJvZ3JhbSwgX3doaWNoIG9mIHRoZSBmb2xsb3dpbmcgaXMgTk9UIGEgZ29vZCBjaG9pY2UgZm9yIHRoZSBudW1iZXIgb2YgY2x1c3RlcnM/Xw0KDQorIDYNCisg5qC55pOa5qi554uA5ZyW55qEWei7uO+8jDEzMDDlj6/ku6XliIflhannvqTvvIw4MDDlj6/ku6XliIfkuInnvqTvvIw0MDDlj6/ku6XliIfkuInnvqQNCg0KIyMjIyMgMi4yIOWIhuWJsue+pOe1hA0KU3VwcG9zZSB0aGF0IGFmdGVyIGxvb2tpbmcgYXQgdGhlIGRlbmRyb2dyYW0gYW5kIGRpc2N1c3Npbmcgd2l0aCB0aGUgbWFya2V0aW5nIGRlcGFydG1lbnQsIHRoZSBhaXJsaW5lIGRlY2lkZXMgdG8gcHJvY2VlZCB3aXRoIDUgY2x1c3RlcnMuIERpdmlkZSB0aGUgZGF0YSBwb2ludHMgaW50byA1IGNsdXN0ZXJzIGJ5IHVzaW5nIHRoZSBjdXRyZWUgZnVuY3Rpb24uIA0KYGBge3J9DQprZyA9IGN1dHJlZShoYywgaz01KQ0KdGFibGUoa2cpDQpgYGANCl9Ib3cgbWFueSBkYXRhIHBvaW50cyBhcmUgaW4gQ2x1c3RlciAxP18NCg0KKyA3NzYNCg0KDQojIyMjIyAyLjMg5b6e5Y2A6ZqU6K6K5pW455qE5bmz5Z2H5YC85o6o6KuW5peP576k54m55oCnDQpOb3csIHVzZSB0YXBwbHkgdG8gY29tcGFyZSB0aGUgYXZlcmFnZSB2YWx1ZXMgaW4gZWFjaCBvZiB0aGUgdmFyaWFibGVzIGZvciB0aGUgNSBjbHVzdGVycyAodGhlIGNlbnRyb2lkcyBvZiB0aGUgY2x1c3RlcnMpLiBZb3UgbWF5IHdhbnQgdG8gY29tcHV0ZSB0aGUgYXZlcmFnZSB2YWx1ZXMgb2YgdGhlIHVubm9ybWFsaXplZCBkYXRhIHNvIHRoYXQgaXQgaXMgZWFzaWVyIHRvIGludGVycHJldC4gWW91IGNhbiBkbyB0aGlzIGZvciB0aGUgdmFyaWFibGUgIkJhbGFuY2UiIHdpdGggdGhlIGZvbGxvd2luZyBjb21tYW5kOg0KDQp0YXBwbHkoYWlybGluZXMkQmFsYW5jZSwgY2x1c3Rlckdyb3VwcywgbWVhbikNCmBgYHtyfQ0Kc2FwcGx5KHNwbGl0KEEsa2cpLCBjb2xNZWFucykgJT4lIHJvdW5kKDIpIA0KYGBgDQpDb21wYXJlZCB0byB0aGUgb3RoZXIgY2x1c3RlcnMsIF9DbHVzdGVyIDEgaGFzIHRoZSBsYXJnZXN0IGF2ZXJhZ2UgdmFsdWVzIGluIHdoaWNoIHZhcmlhYmxlcyAoaWYgYW55KT8gU2VsZWN0IGFsbCB0aGF0IGFwcGx5Ll8NCg0KKyBEYXlzU2luY2VFbnJvbGwgIA0KDQoNCl9Ib3cgd291bGQgeW91IGRlc2NyaWJlIHRoZSBjdXN0b21lcnMgaW4gQ2x1c3RlciAxP18NCg0KKyBJbmZyZXF1ZW50IGJ1dCBsb3lhbCBjdXN0b21lcnMuDQoNCg0KIyMjIyMgMi40IENsdXN0ZXIgMg0KYGBge3J9DQpzcGxpdChBTixrZykgJT4lIHNhcHBseShjb2xNZWFucykgJT4lIHJvdW5kKDIpDQpgYGANCg0KYGBge3J9DQpwYXIoY2V4PTAuOCkNCnNwbGl0KEFOLGtnKSAlPiUgc2FwcGx5KGNvbE1lYW5zKSAlPiUgYmFycGxvdChiZXNpZGU9VCxjb2w9cmFpbmJvdyg3KSkNCmxlZ2VuZCgndG9wcmlnaHQnLGxlZ2VuZD1jb2xuYW1lcyhBKSxmaWxsPXJhaW5ib3coNykpDQpgYGANCg0KQ29tcGFyZWQgdG8gdGhlIG90aGVyIGNsdXN0ZXJzLCBfQ2x1c3RlciAyIGhhcyB0aGUgbGFyZ2VzdCBhdmVyYWdlIHZhbHVlcyBpbiB3aGljaCB2YXJpYWJsZXMgKGlmIGFueSk/IFNlbGVjdCBhbGwgdGhhdCBhcHBseS5fDQoNCisgUXVhbE1pbGVzDQorIEZsaWdodE1pbGVzIA0KKyBGbGlnaHRUcmFucyAgICAgICAgIA0KDQpfSG93IHdvdWxkIHlvdSBkZXNjcmliZSB0aGUgY3VzdG9tZXJzIGluIENsdXN0ZXIgMj9fDQoNCg0KKyBDdXN0b21lcnMgd2hvIGhhdmUgYWNjdW11bGF0ZWQgYSBsYXJnZSBhbW91bnQgb2YgbWlsZXMsIGFuZCB0aGUgb25lcyB3aXRoIHRoZSBsYXJnZXN0IG51bWJlciBvZiBmbGlnaHQgdHJhbnNhY3Rpb25zLg0KDQoNCiMjIyMjIDIuNSBDbHVzdGVyIDMNCkNvbXBhcmVkIHRvIHRoZSBvdGhlciBjbHVzdGVycywgX0NsdXN0ZXIgMyBoYXMgdGhlIGxhcmdlc3QgYXZlcmFnZSB2YWx1ZXMgaW4gd2hpY2ggdmFyaWFibGVzIChpZiBhbnkpPyBTZWxlY3QgYWxsIHRoYXQgYXBwbHkuXw0KDQorIEJhbGFuY2UgIA0KKyBCb251c01pbGVzDQorIEJvbnVzVHJhbnMgDQoNCl9Ib3cgd291bGQgeW91IGRlc2NyaWJlIHRoZSBjdXN0b21lcnMgaW4gQ2x1c3RlciAzP18NCg0KKyBDdXN0b21lcnMgd2hvIGhhdmUgYWNjdW11bGF0ZWQgYSBsYXJnZSBhbW91bnQgb2YgbWlsZXMsIG1vc3RseSB0aHJvdWdoIG5vbi1mbGlnaHQgdHJhbnNhY3Rpb25zLg0KDQojIyMjIyAyLjYgQ2x1c3RlciA0DQpDb21wYXJlZCB0byB0aGUgb3RoZXIgY2x1c3RlcnMsIF9DbHVzdGVyIDQgaGFzIHRoZSBsYXJnZXN0IGF2ZXJhZ2UgdmFsdWVzIGluIHdoaWNoIHZhcmlhYmxlcyAoaWYgYW55KT8gU2VsZWN0IGFsbCB0aGF0IGFwcGx5Ll8NCg0KKyBub25lDQoNCl9Ib3cgd291bGQgeW91IGRlc2NyaWJlIHRoZSBjdXN0b21lcnMgaW4gQ2x1c3RlciA0P18NCg0KKyBSZWxhdGl2ZWx5IG5ldyBjdXN0b21lcnMgd2hvIHNlZW0gdG8gYmUgYWNjdW11bGF0aW5nIG1pbGVzLCBtb3N0bHkgdGhyb3VnaCBub24tZmxpZ2h0IHRyYW5zYWN0aW9ucy4gDQoNCiMjIyMjIDIuNyBDbHVzdGVyIDUNCkNvbXBhcmVkIHRvIHRoZSBvdGhlciBjbHVzdGVycywgX0NsdXN0ZXIgNSBoYXMgdGhlIGxhcmdlc3QgYXZlcmFnZSB2YWx1ZXMgaW4gd2hpY2ggdmFyaWFibGVzIChpZiBhbnkpPyBTZWxlY3QgYWxsIHRoYXQgYXBwbHkuXw0KDQorIG5vbmUNCg0KX0hvdyB3b3VsZCB5b3UgZGVzY3JpYmUgdGhlIGN1c3RvbWVycyBpbiBDbHVzdGVyIDU/Xw0KDQorIFJlbGF0aXZlbHkgbmV3IGN1c3RvbWVycyB3aG8gZG9uJ3QgdXNlIHRoZSBhaXJsaW5lIHZlcnkgb2Z0ZW4uIA0KDQotIC0gLQ0KDQojIyMgMy4gSy1NZWFuc+mbhue+pOWIhuaekA0KDQojIyMjIyAzLjEgSy1NZWFuc+mbhue+pOWIhuaekA0KTm93IHJ1biB0aGUgay1tZWFucyBjbHVzdGVyaW5nIGFsZ29yaXRobSBvbiB0aGUgbm9ybWFsaXplZCBkYXRhLCBhZ2FpbiBjcmVhdGluZyA1IGNsdXN0ZXJzLiBTZXQgdGhlIHNlZWQgdG8gODggcmlnaHQgYmVmb3JlIHJ1bm5pbmcgdGhlIGNsdXN0ZXJpbmcgYWxnb3JpdGhtLCBhbmQgc2V0IHRoZSBhcmd1bWVudCBpdGVyLm1heCB0byAxMDAwLg0KDQpgYGB7cn0NCnNldC5zZWVkKDg4KQ0Ka20gPSBrbWVhbnMoQU4sIDUsIGl0ZXIubWF4ID0gMTAwMCkNCmtnMiA9IGttJGNsdXN0ZXINCnRhYmxlKGtnMikNCmBgYA0KX0hvdyBtYW55IGNsdXN0ZXJzIGhhdmUgbW9yZSB0aGFuIDEsMDAwIG9ic2VydmF0aW9ucz9fDQoNCisgY2x1c3RlcjRhbmQ1DQoNCmBgYHtyfQ0KcGFyKGNleD0wLjgpDQprbSRjZW50ZXJzICU+JSByb3VuZCgyKSAlPiUgdCAlPiUgYmFycGxvdChiZXNpZGU9VCxjb2w9cmFpbmJvdyg3KSkNCmxlZ2VuZCgndG9wcmlnaHQnLGxlZ2VuZD1jb2xuYW1lcyhBKSxmaWxsPXJhaW5ib3coNykpDQpgYGANCg0KIyMjIyMgMy4yIEhpZXJhcmNoaWNhbOWSjEstTWVhbnPpm4bnvqTnmoTlsI3mh4npl5zkv4INCk5vdywgY29tcGFyZSB0aGUgY2x1c3RlciBjZW50cm9pZHMgdG8gZWFjaCBvdGhlciBlaXRoZXIgYnkgZGl2aWRpbmcgdGhlIGRhdGEgcG9pbnRzIGludG8gZ3JvdXBzIGFuZCB0aGVuIHVzaW5nIHRhcHBseSwgb3IgYnkgbG9va2luZyBhdCB0aGUgb3V0cHV0IG9mIGttZWFuc0NsdXN0JGNlbnRlcnMsIHdoZXJlICJrbWVhbnNDbHVzdCIgaXMgdGhlIG5hbWUgb2YgdGhlIG91dHB1dCBvZiB0aGUga21lYW5zIGZ1bmN0aW9uLiAoTm90ZSB0aGF0IHRoZSBvdXRwdXQgb2Yga21lYW5zQ2x1c3QkY2VudGVycyB3aWxsIGJlIGZvciB0aGUgbm9ybWFsaXplZCBkYXRhLiBJZiB5b3Ugd2FudCB0byBsb29rIGF0IHRoZSBhdmVyYWdlIHZhbHVlcyBmb3IgdGhlIHVubm9ybWFsaXplZCBkYXRhLCB5b3UgbmVlZCB0byB1c2UgdGFwcGx5IGxpa2Ugd2UgZGlkIGZvciBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4pDQpgYGB7cn0NCnRhYmxlKEhpZXJhcmNoaWNhbD1rZywgS01lYW5zPWtnMikNCmBgYA0KX0RvIHlvdSBleHBlY3QgQ2x1c3RlciAxIG9mIHRoZSBLLU1lYW5zIGNsdXN0ZXJpbmcgb3V0cHV0IHRvIG5lY2Vzc2FyaWx5IGJlIHNpbWlsYXIgdG8gQ2x1c3RlciAxIG9mIHRoZSBIaWVyYXJjaGljYWwgY2x1c3RlcmluZyBvdXRwdXQ/Xw0KDQorIE5vLCBiZWNhdXNlIGNsdXN0ZXIgb3JkZXJpbmcgaXMgbm90IG1lYW5pbmdmdWwgaW4gZWl0aGVyIGstbWVhbnMgY2x1c3RlcmluZyBvciBoaWVyYXJjaGljYWwgY2x1c3RlcmluZy4NCisg6ZuG576k55qE5qyh5bqP5Lim6Z2e5Zu65a6a55qE77yM5ZCM5q+U6LOH5paZ5Zyoa21lYW5z5ZKMaGllcmFyY2hpY2Fs5Y+v6IO95pyJ5omA5LiN5ZCM44CCDQorIOWFqeWAi+aooeWei+iDjOW+jOmBi+eul+eahOWOn+eQhuS4puS4jeWujOWFqOebuOWQjO+8jOWboOatpOWcqOavj+e+pOS4remChOaYr+acg+acieS6m+ioseS4jeWQjOOAgg0KDQoNCg0KPGJyPg0KDQojIyMjIyDjgJDoqI7oq5bllY/poYzjgJENCg0K6KuL5L2g5YCR54K66YCZ5LqU5YCL5peP576k5ZCE6LW35LiA5YCL5ZCN56ixDQoNCisgMSDnnoznnaHpoaflrqINCisgMiDkuLvlipvpoaflrqINCisgMyDmvZvlnKjpoaflrqINCisgNCDmsojnnaHpoaflrqINCisgNSDpnZ7nm67mqJnlrqLnvqQNCg0KDQroq4vkvaDlgJHngrrpgJnkupTlgIvml4/nvqTlkIToqK3oqIjkuIDlgIvooYzpirfnrZbnlaUNCg0KKyAxIOeejOedoemhp+Wuou+8muatpOe+pOmhp+WuoueahOiou+WGiuaZgumWk+WBj+mVt++8jOWcqGZsaWdodG1pbGXnmoTooajnj77lgY/lt67vvIzkvYblnKhib251c+mAmeWhiue0r+epjeW+iOWkmu+8jOS7o+ihqOatpOe+pOmhp+WuouaXpeW+jOacieW+iOWkp+apn+acg+S7jeacg+S+huS9v+eUqOaIkeWAkeeahOacjeWLme+8jOaIkeWAkemHneWwjeS7luWAkeeahOihjOmKt+WwseaYr+aPkOWNh2ZsaWdodG1pbGXnmoTooajnj77vvIzlm6DmraTmjqjlh7rml4XpgYrmlrnmoYjnrYnvvIzliqDpgJ/ku5blgJHkvobkvb/nlKjmiJHlgJHmnI3li5nnmoTmhI/poZgNCg0KKyAyIOS4u+WKm+mhp+Wuou+8muatpOe+pOmhp+Wuouiou+WGiuaZgumWk+S4jemVt++8jOeul+WcqOaIkOmVt+S4reeahOmhp+Wuoue+pO+8jOWcqOWQhOmghemhnuWIpeeahOihqOmpl+mDveW+iOWlve+8jOmHneWwjeatpOmhp+Wuoue+pO+8jOimgeaOqOWHuuW/oOiqoOaWueahiO+8jOmAj+mBjue0r+epjemHjOeoi+aVuOetieaPkOS+m+WAkeioseWkmuWEquaDoOWSjOacjeWLme+8jOeVmeS9j+mAmeS6m+aIkOmVt+Wuoue+pOOAgg0KDQorIDMg5r2b5Zyo6aGn5a6i77ya5q2k55uu5qiZ5a6i576k6YG45pOH5oiR5YCR6Iiq56m65YWs5Y+455qEYm9udXPvvIzooajnpLrku5blgJHml6XlvozmnInlj6/og73kvobmtojosrvnmoTmhI/poZjvvIzlm6DmraTph53lsI3ku5blgJHlgZrlh7rpppbpo5vnibnliKXmnI3li5nmiJbnrKzkuIDmrKHpo5vooYzlhKrmg6DvvIzkvoblkLjlvJXku5blgJHkvb/nlKjmiJHlgJHnmoTmnI3li5njgIINCg0KKyA0IOayiOedoemhp+Wuou+8muatpOebruaomeWuoue+pO+8jOiou+WGiuaZgumWk+WBj+mVt++8jOS9huWcqOWFtuS7luWQhOmgheihqOePvuWBj+W3ru+8jOaOqOa4rOWPr+iDvei9ieWQkeWFtuS7luiIquepuuWFrOWPuO+8jOmHneWwjemAmeS6m+mhp+Wuou+8jOaIkeWAkeWPr+S7peWFiOaPkOS+m+a7v+WVj+WNt+iqv+afpemAgemHjOeoi+WEquaDoO+8jOW4jOacm+S7luWAkeaPkOS+m+aEj+imi++8jOeCuuS9leW+jOS+huS4jeS9v+eUqOaIkeWAkeacjeWLme+8jOaOpeiRl+WPr+S7peaOqOWHuuiAgeWPi+WbnuWomOWutu+8jOWQuOW8leS7luWAkeWbnua1geOAgg0KDQorIDUg6Z2e55uu5qiZ5a6i576k77ya5q2k5a6i576k5Y+v6IO95piv5YW25LuW6Iiq56m65YWs5Y+455qE5b+g5a+m6aGn5a6i77yM5LuW5YCR55qE6L2J5o+b5oiQ5pys5Y+v6IO95b6I6auY77yM5Zug5q2k5oiR5YCR5LiN5pyD6Yed5bCN5q2k55uu5qiZ5a6i576k54m55Yil6KGM6Yq377yM5pyD5bCH6aCQ566X55WZ57Wm5LiK6L+w5a6i576k44CCDQoNCue1seioiOS4iuacgOWlveeahOWIhue+pOS5n+aYr+WvpuWLmeS4iuacgOWlveeahOWIhue+pOWXju+8nyANCg0KKyDntbHoqIjkuIrph53lsI085pW45a2XPuaPkOS+m+e1puaIkeWAkeWuouingOeahOWIhuaekO+8jOS9huWvpuWLmeS4iuiAg+aFrueahOiuiuaVuOWPr+iDveabtOWkmu+8jOS7peiIquepuuWFrOWPuOS+huiqqu+8jOeCuuaIkeWAkeWIhuaekOWlveS6huS4iui/sOmhnue+pO+8jOS9huaIkeWAkeWPr+iDveimgeabtOWkmueahOe0sOevgOS4i+WOu+WBmuihjOmKt++8jOWDj+aYr+eUt+Wls+avlOOAgeW5tOm9oeetie+8jOesrOS6jOm7nu+8jOWvpuWLmeS4iueahOWIhue+pOWPr+iDvemChOacg+eJvea2ieWIsOmdnuaVuOWtl+eahOaxuuetlu+8jOWDj+aYr+iIquepuuWFrOWPuOeahOaUv+etluaIluaYr+WFtuS7luiAg+mHj++8jOacieaZguWAmeS4jeaYr+WFieeci+e1seioiOaVuOWtl+WwseiDveaxuuWumueahO+8jOS9huS4jeWPr+WQpuiqje+8jOe1seioiOWIhue+pOaPkOS+m+euoeeQhuiAheS4gOWAi+ebtOaOpeWuouingOeahOe1kOaenO+8jOW5q+WKqeeuoeeQhuiAhemAsuihjOW+jOmdoueahOaxuuetluOAgg0KDQrpmaTkuobogIPmha7nvqTplpPlkoznvqTplpPot53pm6LkuYvlpJbvvIzlr6bli5nkuIrnmoTliIbnvqTpgJrluLjpgoTpnIDopoHogIPmha7pgqPkupvlm6DntKDvvJ8gDQoNCisg576k5ZKM576k6ZaT55qE6Led6Zui77yM5piv57Wx6KiI5bCx5qih5Z6L5Y2A5YiG5Ye65L6G55qE77yM5L2G5a+m5YuZ5LiK55qE5YiG576k5b6I5aSa5pmC5YCZ6ICD6YeP55qE5LiN5Y+q5piv5pW45a2X5LiK55qE5beu5Yil77yM5Lul6Iiq56m65YWs5Y+45L6L5a2Q5L6G6Kqq77yM5oiR5YCR55yL6aGe5YilMeWSjDPvvIzlj6/og73mnIPoprrlvpfku5blgJHmnInmiYDkuI3lkIzvvIzkvYblgYflpoLoiKrnqbrlhazlj7jku4rlpKnmmK/opoHku6XoqLvlhormmYLplpPplbfnn63kvobooYzpirfvvIzpgqPpurzmraTmmYLnmoTliIbnvqTmnInmnIPkuI3lkIzvvIzlm6DmraTmqKHlnovmj5DkvpvmiJHlgJHkuIDlgIvlrqLop4DnmoTkuovlr6blvozvvIznrqHnkIbogIXliIbnvqTmmYLopoHphY3lkIjlhazlj7jnmoTpnIDmsYLvvIzmiJbmmK/miJDmnKzlkozntpPmv5/mlYjnm4rkuIrogIPph4/vvIzlgZrlh7rkvobnmoTmsbrnrZbmiJboqLHmnInmmYLlgJnlkozntbHoqIjmlbjlrZfkuIrmnIPmnInmiYDkuI3lkIzjgIINCg0KLSAtIC0NCmBgYA0KPGJyPjxicj48YnI+PGJyPjxicj4NCg0KPHN0eWxlPg0KLmNhcHRpb24gew0KICBjb2xvcjogIzc3NzsNCiAgbWFyZ2luLXRvcDogMTBweDsNCn0NCnAgY29kZSB7DQogIHdoaXRlLXNwYWNlOiBpbmhlcml0Ow0KfQ0KcHJlIHsNCiAgd29yZC1icmVhazogbm9ybWFsOw0KICB3b3JkLXdyYXA6IG5vcm1hbDsNCiAgbGluZS1oZWlnaHQ6IDE7DQp9DQpwcmUgY29kZSB7DQogIHdoaXRlLXNwYWNlOiBpbmhlcml0Ow0KfQ0KcCxsaSB7DQogIGZvbnQtZmFtaWx5OiAiVHJlYnVjaGV0IE1TIiwgIj8/Pz8/Pz8/Pz8/Pz8/PyIsICJNaWNyb3NvZnQgSmhlbmdIZWkiOw0KfQ0KDQoucnsNCiAgbGluZS1oZWlnaHQ6IDEuMjsNCn0NCg0KdGl0bGV7DQogIGNvbG9yOiAjY2MwMDAwOw0KICBmb250LWZhbWlseTogIlRyZWJ1Y2hldCBNUyIsICI/Pz8/Pz8/Pz8/Pz8/Pz8iLCAiTWljcm9zb2Z0IEpoZW5nSGVpIjsNCn0NCg0KYm9keXsNCiAgZm9udC1mYW1pbHk6ICJUcmVidWNoZXQgTVMiLCAiPz8/Pz8/Pz8/Pz8/Pz8/IiwgIk1pY3Jvc29mdCBKaGVuZ0hlaSI7DQp9DQoNCmgxLGgyLGgzLGg0LGg1ew0KICBjb2xvcjogIzAwODgwMDsNCiAgZm9udC1mYW1pbHk6ICJUcmVidWNoZXQgTVMiLCAiPz8/Pz8/Pz8/Pz8/Pz8/IiwgIk1pY3Jvc29mdCBKaGVuZ0hlaSI7DQp9DQoNCmgzew0KICBjb2xvcjogI2IzNmIwMDsNCiAgYmFja2dyb3VuZDogI2ZmZTBiMzsNCiAgbGluZS1oZWlnaHQ6IDI7DQogIGZvbnQtd2VpZ2h0OiBib2xkOw0KfQ0KDQpoNXsNCiAgY29sb3I6ICMwMDYwMDA7DQogIGJhY2tncm91bmQ6ICNmZmZmZTA7DQogIGxpbmUtaGVpZ2h0OiAyOw0KICBmb250LXdlaWdodDogYm9sZDsNCn0NCg0KZW17DQogIGNvbG9yOiAjMDAwMGMwOw0KICBiYWNrZ3JvdW5kOiAjZjBmMGYwOw0KICB9DQo8L3N0eWxlPg0KDQo=