Muhammad Ghozy Al Haqqoni / 16.9293

ASUMSI REGRESI

Terdapat 5 asumsi regresi yang menentukan apakah regresi linear dapat dilakukan : 1. Normalitas 2. Linearitas 3. Multikolinearitas 4. Autokolinearitas 5. Heteroskedastisitas

DATA

Data dibangkitkan menggunakan fungsi pembangkit data. Data yang digunakan adalah data berdistribusi normal serta gamma untuk perwakilan data berdistribusi tidak normal.

Bangkitkan Data Berdistribusi NORMAL

set.seed(Sys.Date())
#diambil dari distribusi uniform (0,1)
#fungsi dengan runif
get_normStd <- function(n) {
  u1<-runif(n, 0,1)
  u2<-runif(n, 0,1)
 #using box-muller transformation
  z1<-sqrt(-2*log(u1))*cos(2*pi*u2)
  return(z1)
}
#test using shaprio-wilk test
# where Null Hypothesis = Normal, def alpha = 5%
Z_runif <- get_normStd(100)
data.frame(Z_runif) %>% 
ggplot2::ggplot(aes(Z_runif))+
  geom_density(color="black", fill="lightgreen") +
  labs(title="Distribusi Normal",x="Z-value", y = "Density") +
  theme_minimal()

shapiro.test(Z_runif)

    Shapiro-Wilk normality test

data:  Z_runif
W = 0.98896, p-value = 0.581

Dengan tingkat signifikansi 5% peneliti mempunyai cukup bukti untuk menyatakan bahwa distribusi data tersebut berdistribusi normal.

Bangkitkan Data Berdistribusi CHI-SQUARE

get_chiSqr <- function(n, df) {
#penyesuaian normal standard (z) ke chisquare (z^2)
  set.seed(Sys.Date())
  chi<- rep(0, 100)
  for(i in c(1:df)){
    u1<-runif(n,0,1)
    u2<-runif(n,0,1)
    z1<-sqrt(-2*log(u1))*cos(2*pi*u2)
    z<-z1
    x<-z^2
    chi<-chi+x
  }
  return(chi)
}
#test
df <- 2
xx1 <- get_chiSqr(100,df)
data.frame(xx1) %>% 
ggplot2::ggplot(aes(xx1))+
  geom_density(color="black", fill="pink") +
  labs(title="Distribusi Chi-Square",x="chisqr-value", y = "Density") +
  theme_minimal()

shapiro.test(xx1)

    Shapiro-Wilk normality test

data:  xx1
W = 0.84801, p-value = 1.002e-08

Dengan tingkat signifikansi 5% peneliti tidak mempunyai cukup bukti untuk menyatakan bahwa distribusi data tersebut berdistribusi normal.

1. NORMALITAS

Uji normalitas bertujuan untuk menguji apakah dalam model regresi, variabel penggangu atau residual memiliki distribusi normal. Jika asumsi ini dilanggar, maka uji statistik menjadi tidak valid atau bias terutama untuk sampel kecil. Uji normalitas dapat dilakukan melalui dua pendekatan yaitu melalui pendekatan grafik (histogram dan P-P Plot) atau uji kolmogorov-smirnov, chi-square, Liliefors maupun Shapiro-Wilk.

Residual Berdistribusi Normal

residual_normal <- Z_runif #residual berdistribusi N(0,1)
x <- runif(100, min = 1, max = 10) 
b <- c(1,2.7)
independen <- model.matrix(~x) 
y <- independen %*% b + residual_normal
model <- lm(y~x)              #Membuat Model persamaan
residu <- resid(model)        #Mengambil nilai residu dari persamaan
data.frame(residu) %>% 
ggplot2::ggplot(aes(residu))+
  geom_density(color="black", fill="lightgreen") +
  labs(title="Distribusi Residu",x="x", y = "Density") +
  theme_minimal()         #plot bukti bahwa residu berdistribusi normal

shapiro.test(residu)          #uji shapiro membuktikan bahwa pvalue >0.05 (residu berdistribusi Normal)

    Shapiro-Wilk normality test

data:  residu
W = 0.98856, p-value = 0.5503
data_normal <- data.frame(y,x) #menyimpan hasil 

Residual Tidak Berdistribusi Normal

residual_chisqr <- xx1
y <- independen %*% b + residual_chisqr
model <- lm(y~x)              #Membuat Model persamaan
residu <- resid(model)        #Mengambil nilai residu dari persamaan
data.frame(residu) %>% 
ggplot2::ggplot(aes(residu))+
  geom_density(color="black", fill="pink") +
  labs(title="Distribusi Residu",x="x", y = "Density") +
  theme_minimal()         #plot bukti bahwa residu tidak berdistribusi normal

shapiro.test(residu)          #uji shapiro membuktikan bahwa pvalue <0.05 (Tidak Normal)

    Shapiro-Wilk normality test

data:  residu
W = 0.86144, p-value = 3.215e-08
data_tidak_normal <- data.frame(y,x) #menyimpan hasil

Efek

set.seed(Sys.Date())
efekNormalitas <- function(data_normal, data_tidak_normal){
  count_normal <- 0
  for (i in 1:100) {
    test <- lm(y~x , data = data_normal %>% dplyr::sample_n(10, F))
    test <- summary(test)
    p_value <- test$coefficients[2,4] #cek apabila tidak signifikan maka count+1
    if(p_value > 0.05) {
      count_normal <- count_normal + 1
    }
  }
  
  count_tidak_normal <- 0
  for (i in 1:100) {
    test <- lm(y~x , data = data_tidak_normal %>% dplyr::sample_n(10, F))
    test <- summary(test)
    p_value <- test$coefficients[2,4] #cek apabila tidak signifikan maka count+1
    if(p_value > 0.05) {
      count_tidak_normal <- count_tidak_normal + 1
    }
  }
  hasil <- data.frame(count_normal, count_tidak_normal)
  return(hasil)
}
efekNormalitas(data_normal, data_tidak_normal)

*Kesimpulan: Count_normal hasilnya 0, sehingga apabila asumsi normalitas terpenuhi, maka variabel x selalu signifikan. Sedangkan, count_tidak_normal hasilnya >0, maka tidak normalitas akan menyebabkan variabel x bisa tidak signifikan.

2. LINEARITAS

Uji linearitas bertujuan untuk mengetahui apakah dua variabel mempunyai hubungan yang linear atau tidak secara signifikan. Jika tidak signifikan, artinya hubungan tidak linear, residu tidak normal, secara tak langsung juga melanggar asumsi normalitas.

Data Linear

set.seed(Sys.Date())
residual_linear <- Z_runif #residual berdistribusi N(0,1)
x <- runif(100,0,1)
b <- c(1,1.3)
independen <- model.matrix(~x)
y <- independen %*% b + residual_linear
data_linear <- data.frame(y,x)
data_linear %>% 
ggplot(aes(x,y)) + 
  geom_point(color='darkblue') +
  ggtitle("y =", y) +
  theme_minimal()

Data Non Linear

set.seed(Sys.Date())
x <- runif(100,-7,7)
y <- cos(x) - 10
data_non_linear <- data.frame(y,x)
data_non_linear %>% 
ggplot(aes(x,y)) + 
  geom_point(color='darkblue') +
  ggtitle("y =", y) +
  theme_minimal()

Efek

#meangambil residual
linearModel <- lm(y~x, data_linear)
nonLinearModel <- lm(y~x, data_non_linear)
linearResidu <- resid(linearModel)
nonLinearResidu <- resid(nonLinearModel)
data.frame(linearResidu) %>% 
ggplot2::ggplot(aes(linearResidu))+
  geom_density(color="black", fill="lightgreen") +
  labs(title="Distribusi linearResidu",x="x", y = "Density") +
  theme_minimal() 

data.frame(nonLinearResidu) %>% 
ggplot2::ggplot(aes(nonLinearResidu))+
  geom_density(color="black", fill="pink") +
  labs(title="Distribusi nonLinearResidu",x="x", y = "Density") +
  theme_minimal() 

shapiro.test(linearResidu)

    Shapiro-Wilk normality test

data:  linearResidu
W = 0.98782, p-value = 0.4947
shapiro.test(nonLinearResidu)

    Shapiro-Wilk normality test

data:  nonLinearResidu
W = 0.90154, p-value = 1.671e-06

3. MULTIKOLINEARITAS

Multikolinearitas muncul jika terdapat hubungan yang sempurna atau pasti di antara beberapa atau semua variabel independen dalam model. Terdapat beberapa metode untuk mendeteksi keberadaan multikolinearitas (Gujarati, 1995;Ramanathan, 1995). Untuk mendeteksi multikolinearitas digunakan pengukuran terhadap nilai VIF (Variable Inflation Factor) dan nilai Tolerance.

Data Multikolinearitas

res_multikol <- Z_runif
x1 <- runif(100, 0, 1)
b <- c(1,2.7)
independen <- model.matrix(~x1)
x2 <- independen %*% b + res_multikol
b <- c(1,1.2,1.7)
independen <- model.matrix(~x1+x2)
y <- independen%*%b + res_multikol
data_multikol <- data.frame(y,x1,x2)
data_cor <- cor(data_multikol)
korelasi <- function(data_cor){
  hasil <- data_cor %>% corrplot::corrplot(method="color",  
                      type="upper", 
                      order="hclust", 
                      addCoef.col = "black",
                      tl.col="black", 
                      insig = "blank",
                      diag=FALSE) 
  return(hasil)
}
korelasi(data_cor)
          x1         y        x2
x1 1.0000000 0.4702420 0.5648252
y  0.4702420 1.0000000 0.9938838
x2 0.5648252 0.9938838 1.0000000

Data Non-Multikolinearitas

res_non_multikol <- Z_runif
x1 <- runif(100, 1, 10)
x2 <- runif(100, 0, 5)
b <- c(1,2.7,3.5)
independen <- model.matrix(~x1+x2)
y <- independen%*%b + res_non_multikol
data_no_multikol <- data.frame(y,x1,x2)
corr <- cor(data_no_multikol)
korelasi(corr)
          x2         y        x1
x2 1.0000000 0.6570779 0.1201982
y  0.6570779 1.0000000 0.8180143
x1 0.1201982 0.8180143 1.0000000

Efek

#Kita lihat konsistensi tanda + - pada koefisiennya
konsistensiMultikol <- function(data_mul_or_not){
  x1_minus <- 0
  x2_minus <- 0
  for (i in 1:100) {
    tes <- lm(y~x1+x2 , data = data_mul_or_not %>% sample_n(10, F))
    tes <- summary(tes)
    koefx1 <- tes$coefficients[2]
    koefx2 <- tes$coefficients[3]
    if(koefx1 < 0) {
      x1_minus <- x1_minus + 1
    } 
    if(koefx2 < 0) {
      x2_minus <- x2_minus + 1
    } 
  }
  return(data.frame(x1_minus, x2_minus))
}
#untuk data multikol
konsistensiMultikol(data_multikol)
#untuk data tak multikol
konsistensiMultikol(data_no_multikol)

Data yang tidak mengalami multikolinearitas memiliki konsistensi pada variabel-variabelnya.

4. AUTOKOLINEARITAS

Autokorelasi adalah korelasi antara anggota serangkaian observasi yang diurutkan menurut waktu seperti data deret waktu atau ruang seperti data cross-section. Autokorelasi yang kuat dapat menyebabkan dua variabel yang tidak berhubungan menjadi berhubungan. Biasa disebut spourious regression. Untuk mengetahui autokorelasi digunakan uji Durbin-Watson (DW-test). Adanya autokorelasi dalam regresi dapat diketahui dengan menggunakan beberapa cara antara lain metode grafik (ACF) dan uji Durbin-Watson.

Data Berautokorelasi

res_autokol <- seq(1,10.9,
                   by = .5)
x <- runif(100, 0,1)
b <- c(1,2.7)
independen <- model.matrix(~x)
y <- independen %*% b + res_autokol
data_autokol <- data.frame(y,x)
model_autokol <- lm(y~x, data = data_autokol)
res <- resid(lm(y~x, data = data_autokol))
acf(res)

lmtest::dwtest(model_autokol)

    Durbin-Watson test

data:  model_autokol
DW = 0.46457, p-value = 4.917e-15
alternative hypothesis: true autocorrelation is greater than 0

Data Tidak Berautokorelasi

res_non_autokol <- Z_runif
x <- runif(100,0,1)
b <- c(1,2.7)
independen <- model.matrix(~x)
y <- independen %*% b + res_non_autokol
data_non_autokol <- data.frame(y,x)
model_non_autokol <- lm(y~x, data = data_non_autokol)
res <- resid(model_non_autokol)
acf(res)

lmtest::dwtest(model_non_autokol)

    Durbin-Watson test

data:  model_non_autokol
DW = 1.8998, p-value = 0.3049
alternative hypothesis: true autocorrelation is greater than 0

Efek

predict(model_autokol,data_autokol) %>% head(7)
       1        2        3        4        5        6        7 
7.705781 9.526169 6.899705 6.751222 6.687397 9.072762 9.089097 
predict(model_non_autokol,data_non_autokol) %>% head(7)
       1        2        3        4        5        6        7 
3.253183 3.139747 2.549803 2.853409 1.950185 3.801643 3.236872 
r_sqr <- function(data, model){
  actual <- data$y #varians data autokol
  preds <-  predict(model)#prediksi model
  rss <- sum((preds - actual) ^ 2)  ## residual sum of squares
  tss <- sum((actual - mean(actual)) ^ 2)  ## total sum of squares
  return(1 - rss/tss)
}
r_sqr(data_autokol, model_autokol)
[1] 0.09874248
r_sqr(data_non_autokol, model_non_autokol)
[1] 0.4683949

Tidak dijumpai nilai R-squared yang tinggi antara kedua data yang telah disimulasikan, akan tetapi, data yang berautokorelasi, mempunyai pengaruh variabel lag waktu sebelumnya terhadap variabel Y, terlihat dari grafik ACF yang berpola sekuensial. Sehingga dapat memengaruhi prediksi dari sebuah model regresi.

5. HETEROSKEDASTISITAS

Dalam regresi linear salah satu yang harus dipenuhi agar taksiran parameter dalam model tersebut bersifat BLUE (Best, Linear, Unbiased, and Estimator), dimana var (ui) = \(σ^2\) mempunyai variasi yang sama. Pada kasus-kasus tertentu terjadi variasi ui tidak konstan atau variabel berubah-ubah. Untuk mendeteksi heteroskedastisitas dapat dilakukan pengujian dengan metode grafik.

Dengan pengujian ini dapat dideteksi apakah kesalahan pengganggu dari model yang diamati tidak memiliki varians yang konstan dari satu observasi ke observasi lainnya. Dengan metode grafik, hasilnya dapat menunjukkan ada tidaknya pola-pola tertentu yang terbentuk seperti bergelombang, melebar kemudian menyempit serta titik-titik menyebar di atas dan di bawah angka 0 (nol) pada sumbu Y.

Residual Homoskedastis

res_homo <- Z_runif
x <- runif(100, 0, 1)
b <- c(1,2.7)
independen <- model.matrix(~x)
y <- independen %*% b + res_homo
model <- lm(y~x)
resid <- resid(model)
plot(resid, col = "#009999", lwd=7)

data_homo <- data.frame(y,x)

Residual Heteroskedastis

sd <- 1:250
res_hetero <- rnorm(n=100, mean = sd, sd=.2*sd)
x <- runif(100,1,2)
b <- c(1,2.7)
independen <- model.matrix(~x)
y <- independen %*% b + res_hetero
model <- lm(y~x)
residu <- resid(model)
plot(residu,col = "#009999", lwd=7)

data_hetero <- data.frame(y,x)

Standard Error Comparison

set.seed(Sys.Date())
compare_se <- function(data_homo, data_hetero){
  stdeHOMO <- NULL
  for (i in 1:100) {
    tesHo <- lm(y~x , data_homo %>%  dplyr::sample_n(10,replace = FALSE))
    stdeHOMO <- c(stdeHOMO, sqrt(deviance(tesHo)/df.residual(tesHo)))
  }
  SE_homo <- var(stdeHOMO)
  stdeHETERO <- NULL
  for (i in 1:100) {
    tesHe <- lm(y~x , data = data_hetero %>%  dplyr::sample_n(10,replace = FALSE))
    stdeHETERO <- c(stdeHETERO,sqrt(deviance(tesHe)/df.residual(tesHe)))
  }
  SE_hetero <- var(stdeHETERO)
  
  hasil <- data.frame(SE_homo, SE_hetero)
  return(hasil)
}
compare_se(data_homo, data_hetero)

Standard error residual heteroskedastis tinggi bila dibandingkan dengan yang homoskedastis. Selain itu, residual yang heteroskedastis akan menyebabkan hasil yang over/under estimate, jika ditinjau dari grafik yang ada pada poin hetero, hasil yang didapat kemungkinan besar akan overestimate, karena grafik semakin melebar ke kanan sepanjang t (waktu).

LS0tDQp0aXRsZTogIkFzdW1zaSBSZWdyZXNzaSINCmRlc2NyaXB0aW9uOiAiTXVoYW1tYWQgR2hvenkgQWwgSGFxcW9uaSAtIDNLUzEiDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQ0Kcm0obGlzdCA9IGxzKCkpDQpwYWNtYW46OnBfbG9hZCgidGlkeXZlcnNlIiwgImphbml0b3IiLCAibG10ZXN0IiwgImNvcnJwbG90IikNCmBgYA0KDQo+IE11aGFtbWFkIEdob3p5IEFsIEhhcXFvbmkgLyAxNi45MjkzDQoNCg0KIyBBU1VNU0kgUkVHUkVTSQ0KVGVyZGFwYXQgNSBhc3Vtc2kgcmVncmVzaSB5YW5nIG1lbmVudHVrYW4gYXBha2FoIHJlZ3Jlc2kgbGluZWFyIGRhcGF0IGRpbGFrdWthbiA6DQoxLiBOb3JtYWxpdGFzDQoyLiBMaW5lYXJpdGFzDQozLiBNdWx0aWtvbGluZWFyaXRhcw0KNC4gQXV0b2tvbGluZWFyaXRhcw0KNS4gSGV0ZXJvc2tlZGFzdGlzaXRhcw0KDQoNCiMjIERBVEENCkRhdGEgZGliYW5na2l0a2FuIG1lbmdndW5ha2FuIGZ1bmdzaSBwZW1iYW5na2l0IGRhdGEuIERhdGEgeWFuZyBkaWd1bmFrYW4gYWRhbGFoIGRhdGEgYmVyZGlzdHJpYnVzaSBub3JtYWwgc2VydGEgZ2FtbWEgdW50dWsgcGVyd2FraWxhbiBkYXRhIGJlcmRpc3RyaWJ1c2kgdGlkYWsgbm9ybWFsLg0KDQojIyMgQmFuZ2tpdGthbiBEYXRhIEJlcmRpc3RyaWJ1c2kgTk9STUFMDQpgYGB7ciBnZXRub3Jtc3RhbmRhcmR9DQpzZXQuc2VlZChTeXMuRGF0ZSgpKQ0KI2RpYW1iaWwgZGFyaSBkaXN0cmlidXNpIHVuaWZvcm0gKDAsMSkNCiNmdW5nc2kgZGVuZ2FuIHJ1bmlmDQpnZXRfbm9ybVN0ZCA8LSBmdW5jdGlvbihuKSB7DQogIHUxPC1ydW5pZihuLCAwLDEpDQogIHUyPC1ydW5pZihuLCAwLDEpDQogI3VzaW5nIGJveC1tdWxsZXIgdHJhbnNmb3JtYXRpb24NCiAgejE8LXNxcnQoLTIqbG9nKHUxKSkqY29zKDIqcGkqdTIpDQogIHJldHVybih6MSkNCn0NCg0KI3Rlc3QgdXNpbmcgc2hhcHJpby13aWxrIHRlc3QNCiMgd2hlcmUgTnVsbCBIeXBvdGhlc2lzID0gTm9ybWFsLCBkZWYgYWxwaGEgPSA1JQ0KWl9ydW5pZiA8LSBnZXRfbm9ybVN0ZCgxMDApDQpkYXRhLmZyYW1lKFpfcnVuaWYpICU+JSANCmdncGxvdDI6OmdncGxvdChhZXMoWl9ydW5pZikpKw0KICBnZW9tX2RlbnNpdHkoY29sb3I9ImJsYWNrIiwgZmlsbD0ibGlnaHRncmVlbiIpICsNCiAgbGFicyh0aXRsZT0iRGlzdHJpYnVzaSBOb3JtYWwiLHg9IlotdmFsdWUiLCB5ID0gIkRlbnNpdHkiKSArDQogIHRoZW1lX21pbmltYWwoKQ0Kc2hhcGlyby50ZXN0KFpfcnVuaWYpDQpgYGANCkRlbmdhbiB0aW5na2F0IHNpZ25pZmlrYW5zaSA1JSBwZW5lbGl0aSBtZW1wdW55YWkgY3VrdXAgYnVrdGkgdW50dWsgbWVueWF0YWthbiBiYWh3YSBkaXN0cmlidXNpIGRhdGEgdGVyc2VidXQgYmVyZGlzdHJpYnVzaSAqKm5vcm1hbCoqLg0KDQojIyMgQmFuZ2tpdGthbiBEYXRhIEJlcmRpc3RyaWJ1c2kgQ0hJLVNRVUFSRQ0KYGBge3IgZ2V0Y2hpc3FyfQ0KZ2V0X2NoaVNxciA8LSBmdW5jdGlvbihuLCBkZikgew0KI3Blbnllc3VhaWFuIG5vcm1hbCBzdGFuZGFyZCAoeikga2UgY2hpc3F1YXJlICh6XjIpDQogIHNldC5zZWVkKFN5cy5EYXRlKCkpDQogIGNoaTwtIHJlcCgwLCAxMDApDQogIGZvcihpIGluIGMoMTpkZikpew0KICAgIHUxPC1ydW5pZihuLDAsMSkNCiAgICB1MjwtcnVuaWYobiwwLDEpDQogICAgejE8LXNxcnQoLTIqbG9nKHUxKSkqY29zKDIqcGkqdTIpDQogICAgejwtejENCiAgICB4PC16XjINCiAgICBjaGk8LWNoaSt4DQogIH0NCiAgcmV0dXJuKGNoaSkNCn0NCg0KI3Rlc3QNCmRmIDwtIDINCnh4MSA8LSBnZXRfY2hpU3FyKDEwMCxkZikNCmRhdGEuZnJhbWUoeHgxKSAlPiUgDQpnZ3Bsb3QyOjpnZ3Bsb3QoYWVzKHh4MSkpKw0KICBnZW9tX2RlbnNpdHkoY29sb3I9ImJsYWNrIiwgZmlsbD0icGluayIpICsNCiAgbGFicyh0aXRsZT0iRGlzdHJpYnVzaSBDaGktU3F1YXJlIix4PSJjaGlzcXItdmFsdWUiLCB5ID0gIkRlbnNpdHkiKSArDQogIHRoZW1lX21pbmltYWwoKQ0Kc2hhcGlyby50ZXN0KHh4MSkNCmBgYA0KRGVuZ2FuIHRpbmdrYXQgc2lnbmlmaWthbnNpIDUlIHBlbmVsaXRpIHRpZGFrIG1lbXB1bnlhaSBjdWt1cCBidWt0aSB1bnR1ayBtZW55YXRha2FuIGJhaHdhIGRpc3RyaWJ1c2kgZGF0YSB0ZXJzZWJ1dCBiZXJkaXN0cmlidXNpICoqbm9ybWFsKiouDQoNCg0KDQojIyAxLiBOT1JNQUxJVEFTDQpVamkgbm9ybWFsaXRhcyBiZXJ0dWp1YW4gdW50dWsgbWVuZ3VqaSBhcGFrYWggZGFsYW0gbW9kZWwgcmVncmVzaSwgdmFyaWFiZWwgcGVuZ2dhbmd1IGF0YXUgcmVzaWR1YWwgbWVtaWxpa2kgZGlzdHJpYnVzaSBub3JtYWwuIEppa2EgYXN1bXNpIGluaSBkaWxhbmdnYXIsIG1ha2EgdWppIHN0YXRpc3RpayBtZW5qYWRpIHRpZGFrIHZhbGlkIGF0YXUgYmlhcyB0ZXJ1dGFtYSB1bnR1ayBzYW1wZWwga2VjaWwuIFVqaSBub3JtYWxpdGFzIGRhcGF0IGRpbGFrdWthbiBtZWxhbHVpIGR1YSBwZW5kZWthdGFuIHlhaXR1IG1lbGFsdWkgcGVuZGVrYXRhbiBncmFmaWsgKGhpc3RvZ3JhbSBkYW4gUC1QIFBsb3QpIGF0YXUgdWppIGtvbG1vZ29yb3Ytc21pcm5vdiwgY2hpLXNxdWFyZSwgTGlsaWVmb3JzIG1hdXB1biBTaGFwaXJvLVdpbGsuDQoNCiMjIyBSZXNpZHVhbCBCZXJkaXN0cmlidXNpIE5vcm1hbA0KYGBge3IgcmVzTm9ybX0NCnJlc2lkdWFsX25vcm1hbCA8LSBaX3J1bmlmICNyZXNpZHVhbCBiZXJkaXN0cmlidXNpIE4oMCwxKQ0KeCA8LSBydW5pZigxMDAsIG1pbiA9IDEsIG1heCA9IDEwKSANCmIgPC0gYygxLDIuNykNCmluZGVwZW5kZW4gPC0gbW9kZWwubWF0cml4KH54KSANCnkgPC0gaW5kZXBlbmRlbiAlKiUgYiArIHJlc2lkdWFsX25vcm1hbA0KbW9kZWwgPC0gbG0oeX54KSAgICAgICAgICAgICAgI01lbWJ1YXQgTW9kZWwgcGVyc2FtYWFuDQpyZXNpZHUgPC0gcmVzaWQobW9kZWwpICAgICAgICAjTWVuZ2FtYmlsIG5pbGFpIHJlc2lkdSBkYXJpIHBlcnNhbWFhbg0KZGF0YS5mcmFtZShyZXNpZHUpICU+JSANCmdncGxvdDI6OmdncGxvdChhZXMocmVzaWR1KSkrDQogIGdlb21fZGVuc2l0eShjb2xvcj0iYmxhY2siLCBmaWxsPSJsaWdodGdyZWVuIikgKw0KICBsYWJzKHRpdGxlPSJEaXN0cmlidXNpIFJlc2lkdSIseD0ieCIsIHkgPSAiRGVuc2l0eSIpICsNCiAgdGhlbWVfbWluaW1hbCgpICAgICAgICAgI3Bsb3QgYnVrdGkgYmFod2EgcmVzaWR1IGJlcmRpc3RyaWJ1c2kgbm9ybWFsDQoNCnNoYXBpcm8udGVzdChyZXNpZHUpICAgICAgICAgICN1amkgc2hhcGlybyBtZW1idWt0aWthbiBiYWh3YSBwdmFsdWUgPjAuMDUgKHJlc2lkdSBiZXJkaXN0cmlidXNpIE5vcm1hbCkNCmRhdGFfbm9ybWFsIDwtIGRhdGEuZnJhbWUoeSx4KSAjbWVueWltcGFuIGhhc2lsIA0KYGBgDQoNCiMjIyBSZXNpZHVhbCBUaWRhayBCZXJkaXN0cmlidXNpIE5vcm1hbA0KYGBge3IgcmVzQ2hpfQ0KcmVzaWR1YWxfY2hpc3FyIDwtIHh4MQ0KeSA8LSBpbmRlcGVuZGVuICUqJSBiICsgcmVzaWR1YWxfY2hpc3FyDQptb2RlbCA8LSBsbSh5fngpICAgICAgICAgICAgICAjTWVtYnVhdCBNb2RlbCBwZXJzYW1hYW4NCnJlc2lkdSA8LSByZXNpZChtb2RlbCkgICAgICAgICNNZW5nYW1iaWwgbmlsYWkgcmVzaWR1IGRhcmkgcGVyc2FtYWFuDQpkYXRhLmZyYW1lKHJlc2lkdSkgJT4lIA0KZ2dwbG90Mjo6Z2dwbG90KGFlcyhyZXNpZHUpKSsNCiAgZ2VvbV9kZW5zaXR5KGNvbG9yPSJibGFjayIsIGZpbGw9InBpbmsiKSArDQogIGxhYnModGl0bGU9IkRpc3RyaWJ1c2kgUmVzaWR1Iix4PSJ4IiwgeSA9ICJEZW5zaXR5IikgKw0KICB0aGVtZV9taW5pbWFsKCkgICAgICAgICAjcGxvdCBidWt0aSBiYWh3YSByZXNpZHUgdGlkYWsgYmVyZGlzdHJpYnVzaSBub3JtYWwNCnNoYXBpcm8udGVzdChyZXNpZHUpICAgICAgICAgICN1amkgc2hhcGlybyBtZW1idWt0aWthbiBiYWh3YSBwdmFsdWUgPDAuMDUgKFRpZGFrIE5vcm1hbCkNCmRhdGFfdGlkYWtfbm9ybWFsIDwtIGRhdGEuZnJhbWUoeSx4KSAjbWVueWltcGFuIGhhc2lsDQpgYGANCg0KIyMjIEVmZWsNCmBgYHtyIG5vcm1FZmZlY3R9DQpzZXQuc2VlZChTeXMuRGF0ZSgpKQ0KZWZla05vcm1hbGl0YXMgPC0gZnVuY3Rpb24oZGF0YV9ub3JtYWwsIGRhdGFfdGlkYWtfbm9ybWFsKXsNCiAgY291bnRfbm9ybWFsIDwtIDANCiAgZm9yIChpIGluIDE6MTAwKSB7DQogICAgdGVzdCA8LSBsbSh5fnggLCBkYXRhID0gZGF0YV9ub3JtYWwgJT4lIGRwbHlyOjpzYW1wbGVfbigxMCwgRikpDQogICAgdGVzdCA8LSBzdW1tYXJ5KHRlc3QpDQogICAgcF92YWx1ZSA8LSB0ZXN0JGNvZWZmaWNpZW50c1syLDRdICNjZWsgYXBhYmlsYSB0aWRhayBzaWduaWZpa2FuIG1ha2EgY291bnQrMQ0KICAgIGlmKHBfdmFsdWUgPiAwLjA1KSB7DQogICAgICBjb3VudF9ub3JtYWwgPC0gY291bnRfbm9ybWFsICsgMQ0KICAgIH0NCiAgfQ0KICANCiAgY291bnRfdGlkYWtfbm9ybWFsIDwtIDANCiAgZm9yIChpIGluIDE6MTAwKSB7DQogICAgdGVzdCA8LSBsbSh5fnggLCBkYXRhID0gZGF0YV90aWRha19ub3JtYWwgJT4lIGRwbHlyOjpzYW1wbGVfbigxMCwgRikpDQogICAgdGVzdCA8LSBzdW1tYXJ5KHRlc3QpDQogICAgcF92YWx1ZSA8LSB0ZXN0JGNvZWZmaWNpZW50c1syLDRdICNjZWsgYXBhYmlsYSB0aWRhayBzaWduaWZpa2FuIG1ha2EgY291bnQrMQ0KICAgIGlmKHBfdmFsdWUgPiAwLjA1KSB7DQogICAgICBjb3VudF90aWRha19ub3JtYWwgPC0gY291bnRfdGlkYWtfbm9ybWFsICsgMQ0KICAgIH0NCiAgfQ0KICBoYXNpbCA8LSBkYXRhLmZyYW1lKGNvdW50X25vcm1hbCwgY291bnRfdGlkYWtfbm9ybWFsKQ0KICByZXR1cm4oaGFzaWwpDQp9DQplZmVrTm9ybWFsaXRhcyhkYXRhX25vcm1hbCwgZGF0YV90aWRha19ub3JtYWwpDQpgYGANCipLZXNpbXB1bGFuOg0KQ291bnRfbm9ybWFsIGhhc2lsbnlhIDAsIHNlaGluZ2dhIGFwYWJpbGEgYXN1bXNpIG5vcm1hbGl0YXMgdGVycGVudWhpLCBtYWthIHZhcmlhYmVsIHggc2VsYWx1IHNpZ25pZmlrYW4uDQpTZWRhbmdrYW4sIGNvdW50X3RpZGFrX25vcm1hbCBoYXNpbG55YSA+MCwgbWFrYSB0aWRhayBub3JtYWxpdGFzIGFrYW4gbWVueWViYWJrYW4gdmFyaWFiZWwgeCBiaXNhIHRpZGFrIHNpZ25pZmlrYW4uDQoNCg0KIyMgMi4gTElORUFSSVRBUw0KVWppIGxpbmVhcml0YXMgYmVydHVqdWFuIHVudHVrIG1lbmdldGFodWkgYXBha2FoIGR1YSB2YXJpYWJlbCBtZW1wdW55YWkgaHVidW5nYW4geWFuZyBsaW5lYXIgYXRhdSB0aWRhayBzZWNhcmEgc2lnbmlmaWthbi4gSmlrYSB0aWRhayBzaWduaWZpa2FuLCBhcnRpbnlhIGh1YnVuZ2FuIHRpZGFrIGxpbmVhciwgcmVzaWR1IHRpZGFrIG5vcm1hbCwgc2VjYXJhIHRhayBsYW5nc3VuZyBqdWdhIG1lbGFuZ2dhciBhc3Vtc2kgbm9ybWFsaXRhcy4NCg0KIyMjIERhdGEgTGluZWFyIA0KYGBge3IgbGluWn0NCnNldC5zZWVkKFN5cy5EYXRlKCkpDQpyZXNpZHVhbF9saW5lYXIgPC0gWl9ydW5pZiAjcmVzaWR1YWwgYmVyZGlzdHJpYnVzaSBOKDAsMSkNCnggPC0gcnVuaWYoMTAwLDAsMSkNCmIgPC0gYygxLDEuMykNCmluZGVwZW5kZW4gPC0gbW9kZWwubWF0cml4KH54KQ0KeSA8LSBpbmRlcGVuZGVuICUqJSBiICsgcmVzaWR1YWxfbGluZWFyDQpkYXRhX2xpbmVhciA8LSBkYXRhLmZyYW1lKHkseCkNCg0KZGF0YV9saW5lYXIgJT4lIA0KZ2dwbG90KGFlcyh4LHkpKSArIA0KICBnZW9tX3BvaW50KGNvbG9yPSdkYXJrYmx1ZScpICsNCiAgZ2d0aXRsZSgieSA9IiwgeSkgKw0KICB0aGVtZV9taW5pbWFsKCkNCmBgYA0KDQojIyMgRGF0YSBOb24gTGluZWFyDQpgYGB7ciBjb3N4fQ0Kc2V0LnNlZWQoU3lzLkRhdGUoKSkNCnggPC0gcnVuaWYoMTAwLC03LDcpDQp5IDwtIGNvcyh4KSAtIDEwDQpkYXRhX25vbl9saW5lYXIgPC0gZGF0YS5mcmFtZSh5LHgpDQoNCmRhdGFfbm9uX2xpbmVhciAlPiUgDQpnZ3Bsb3QoYWVzKHgseSkpICsgDQogIGdlb21fcG9pbnQoY29sb3I9J2RhcmtibHVlJykgKw0KICBnZ3RpdGxlKCJ5ID0iLCB5KSArDQogIHRoZW1lX21pbmltYWwoKQ0KYGBgDQoNCiMjIyBFZmVrDQpgYGB7ciBsaW5FZmZlY3R9DQojbWVhbmdhbWJpbCByZXNpZHVhbA0KbGluZWFyTW9kZWwgPC0gbG0oeX54LCBkYXRhX2xpbmVhcikNCm5vbkxpbmVhck1vZGVsIDwtIGxtKHl+eCwgZGF0YV9ub25fbGluZWFyKQ0KDQpsaW5lYXJSZXNpZHUgPC0gcmVzaWQobGluZWFyTW9kZWwpDQpub25MaW5lYXJSZXNpZHUgPC0gcmVzaWQobm9uTGluZWFyTW9kZWwpDQoNCmRhdGEuZnJhbWUobGluZWFyUmVzaWR1KSAlPiUgDQpnZ3Bsb3QyOjpnZ3Bsb3QoYWVzKGxpbmVhclJlc2lkdSkpKw0KICBnZW9tX2RlbnNpdHkoY29sb3I9ImJsYWNrIiwgZmlsbD0ibGlnaHRncmVlbiIpICsNCiAgbGFicyh0aXRsZT0iRGlzdHJpYnVzaSBsaW5lYXJSZXNpZHUiLHg9IngiLCB5ID0gIkRlbnNpdHkiKSArDQogIHRoZW1lX21pbmltYWwoKSANCg0KZGF0YS5mcmFtZShub25MaW5lYXJSZXNpZHUpICU+JSANCmdncGxvdDI6OmdncGxvdChhZXMobm9uTGluZWFyUmVzaWR1KSkrDQogIGdlb21fZGVuc2l0eShjb2xvcj0iYmxhY2siLCBmaWxsPSJwaW5rIikgKw0KICBsYWJzKHRpdGxlPSJEaXN0cmlidXNpIG5vbkxpbmVhclJlc2lkdSIseD0ieCIsIHkgPSAiRGVuc2l0eSIpICsNCiAgdGhlbWVfbWluaW1hbCgpIA0KDQpzaGFwaXJvLnRlc3QobGluZWFyUmVzaWR1KQ0Kc2hhcGlyby50ZXN0KG5vbkxpbmVhclJlc2lkdSkNCmBgYA0KDQojIyAzLiBNVUxUSUtPTElORUFSSVRBUw0KTXVsdGlrb2xpbmVhcml0YXMgbXVuY3VsIGppa2EgdGVyZGFwYXQgaHVidW5nYW4geWFuZyBzZW1wdXJuYSBhdGF1IHBhc3RpIGRpIGFudGFyYSBiZWJlcmFwYSBhdGF1IHNlbXVhIHZhcmlhYmVsIGluZGVwZW5kZW4gZGFsYW0gbW9kZWwuIFRlcmRhcGF0IGJlYmVyYXBhIG1ldG9kZSB1bnR1ayBtZW5kZXRla3NpIGtlYmVyYWRhYW4gbXVsdGlrb2xpbmVhcml0YXMgKEd1amFyYXRpLCAxOTk1O1JhbWFuYXRoYW4sIDE5OTUpLiBVbnR1ayBtZW5kZXRla3NpIG11bHRpa29saW5lYXJpdGFzIGRpZ3VuYWthbiBwZW5ndWt1cmFuIHRlcmhhZGFwIG5pbGFpIFZJRiAoVmFyaWFibGUgSW5mbGF0aW9uIEZhY3RvcikgZGFuIG5pbGFpIFRvbGVyYW5jZS4NCg0KIyMjIERhdGEgTXVsdGlrb2xpbmVhcml0YXMNCmBgYHtyIHJlc19tdWx0aWtvbH0NCnJlc19tdWx0aWtvbCA8LSBaX3J1bmlmDQp4MSA8LSBydW5pZigxMDAsIDAsIDEpDQpiIDwtIGMoMSwyLjcpDQppbmRlcGVuZGVuIDwtIG1vZGVsLm1hdHJpeCh+eDEpDQp4MiA8LSBpbmRlcGVuZGVuICUqJSBiICsgcmVzX211bHRpa29sDQpiIDwtIGMoMSwxLjIsMS43KQ0KaW5kZXBlbmRlbiA8LSBtb2RlbC5tYXRyaXgofngxK3gyKQ0KeSA8LSBpbmRlcGVuZGVuJSolYiArIHJlc19tdWx0aWtvbA0KDQpkYXRhX211bHRpa29sIDwtIGRhdGEuZnJhbWUoeSx4MSx4MikNCmRhdGFfY29yIDwtIGNvcihkYXRhX211bHRpa29sKQ0Ka29yZWxhc2kgPC0gZnVuY3Rpb24oZGF0YV9jb3Ipew0KICBoYXNpbCA8LSBkYXRhX2NvciAlPiUgY29ycnBsb3Q6OmNvcnJwbG90KG1ldGhvZD0iY29sb3IiLCAgDQogICAgICAgICAgICAgICAgICAgICAgdHlwZT0idXBwZXIiLCANCiAgICAgICAgICAgICAgICAgICAgICBvcmRlcj0iaGNsdXN0IiwgDQogICAgICAgICAgICAgICAgICAgICAgYWRkQ29lZi5jb2wgPSAiYmxhY2siLA0KICAgICAgICAgICAgICAgICAgICAgIHRsLmNvbD0iYmxhY2siLCANCiAgICAgICAgICAgICAgICAgICAgICBpbnNpZyA9ICJibGFuayIsDQogICAgICAgICAgICAgICAgICAgICAgZGlhZz1GQUxTRSkgDQogIHJldHVybihoYXNpbCkNCn0NCmtvcmVsYXNpKGRhdGFfY29yKQ0KYGBgDQoNCiMjIyBEYXRhIE5vbi1NdWx0aWtvbGluZWFyaXRhcw0KYGBge3IgcmVzX25vbl9tdWx0aWtvbH0NCnJlc19ub25fbXVsdGlrb2wgPC0gWl9ydW5pZg0KeDEgPC0gcnVuaWYoMTAwLCAxLCAxMCkNCngyIDwtIHJ1bmlmKDEwMCwgMCwgNSkNCmIgPC0gYygxLDIuNywzLjUpDQppbmRlcGVuZGVuIDwtIG1vZGVsLm1hdHJpeCh+eDEreDIpDQp5IDwtIGluZGVwZW5kZW4lKiViICsgcmVzX25vbl9tdWx0aWtvbA0KDQpkYXRhX25vX211bHRpa29sIDwtIGRhdGEuZnJhbWUoeSx4MSx4MikNCmNvcnIgPC0gY29yKGRhdGFfbm9fbXVsdGlrb2wpDQprb3JlbGFzaShjb3JyKQ0KYGBgDQoNCiMjIyBFZmVrDQpgYGB7ciBlZmZNdWwsIHdhcm5pbmc9IEZBTFNFfQ0KI0tpdGEgbGloYXQga29uc2lzdGVuc2kgdGFuZGEgKyAtIHBhZGEga29lZmlzaWVubnlhDQprb25zaXN0ZW5zaU11bHRpa29sIDwtIGZ1bmN0aW9uKGRhdGFfbXVsX29yX25vdCl7DQogIHgxX21pbnVzIDwtIDANCiAgeDJfbWludXMgPC0gMA0KICBmb3IgKGkgaW4gMToxMDApIHsNCiAgICB0ZXMgPC0gbG0oeX54MSt4MiAsIGRhdGEgPSBkYXRhX211bF9vcl9ub3QgJT4lIHNhbXBsZV9uKDEwLCBGKSkNCiAgICB0ZXMgPC0gc3VtbWFyeSh0ZXMpDQogICAga29lZngxIDwtIHRlcyRjb2VmZmljaWVudHNbMl0NCiAgICBrb2VmeDIgPC0gdGVzJGNvZWZmaWNpZW50c1szXQ0KICAgIGlmKGtvZWZ4MSA8IDApIHsNCiAgICAgIHgxX21pbnVzIDwtIHgxX21pbnVzICsgMQ0KICAgIH0gDQogICAgaWYoa29lZngyIDwgMCkgew0KICAgICAgeDJfbWludXMgPC0geDJfbWludXMgKyAxDQogICAgfSANCiAgfQ0KICByZXR1cm4oZGF0YS5mcmFtZSh4MV9taW51cywgeDJfbWludXMpKQ0KfQ0KDQojdW50dWsgZGF0YSBtdWx0aWtvbA0Ka29uc2lzdGVuc2lNdWx0aWtvbChkYXRhX211bHRpa29sKQ0KI3VudHVrIGRhdGEgdGFrIG11bHRpa29sDQprb25zaXN0ZW5zaU11bHRpa29sKGRhdGFfbm9fbXVsdGlrb2wpDQpgYGANCkRhdGEgeWFuZyB0aWRhayBtZW5nYWxhbWkgbXVsdGlrb2xpbmVhcml0YXMgbWVtaWxpa2kga29uc2lzdGVuc2kgcGFkYSB2YXJpYWJlbC12YXJpYWJlbG55YS4NCg0KDQojIyA0LiBBVVRPS09MSU5FQVJJVEFTDQpBdXRva29yZWxhc2kgYWRhbGFoIGtvcmVsYXNpIGFudGFyYSBhbmdnb3RhIHNlcmFuZ2thaWFuIG9ic2VydmFzaSB5YW5nIGRpdXJ1dGthbiBtZW51cnV0IHdha3R1IHNlcGVydGkgZGF0YSBkZXJldCB3YWt0dSBhdGF1IHJ1YW5nIHNlcGVydGkgZGF0YSBjcm9zcy1zZWN0aW9uLiBBdXRva29yZWxhc2kgeWFuZyBrdWF0IGRhcGF0IG1lbnllYmFia2FuIGR1YSB2YXJpYWJlbCB5YW5nIHRpZGFrIGJlcmh1YnVuZ2FuIG1lbmphZGkgYmVyaHVidW5nYW4uIEJpYXNhIGRpc2VidXQgc3BvdXJpb3VzIHJlZ3Jlc3Npb24uICBVbnR1ayBtZW5nZXRhaHVpIGF1dG9rb3JlbGFzaSBkaWd1bmFrYW4gdWppIER1cmJpbi1XYXRzb24gKERXLXRlc3QpLiBBZGFueWEgYXV0b2tvcmVsYXNpIGRhbGFtIHJlZ3Jlc2kgZGFwYXQgZGlrZXRhaHVpIGRlbmdhbiBtZW5nZ3VuYWthbiBiZWJlcmFwYSBjYXJhIGFudGFyYSBsYWluIG1ldG9kZSBncmFmaWsgKEFDRikgZGFuIHVqaSBEdXJiaW4tV2F0c29uLg0KDQojIyMgRGF0YSBCZXJhdXRva29yZWxhc2kNCmBgYHtyIGFrb2x9DQpyZXNfYXV0b2tvbCA8LSBzZXEoMSwxMC45LA0KICAgICAgICAgICAgICAgICAgIGJ5ID0gLjUpDQp4IDwtIHJ1bmlmKDEwMCwgMCwxKQ0KYiA8LSBjKDEsMi43KQ0KaW5kZXBlbmRlbiA8LSBtb2RlbC5tYXRyaXgofngpDQp5IDwtIGluZGVwZW5kZW4gJSolIGIgKyByZXNfYXV0b2tvbA0KZGF0YV9hdXRva29sIDwtIGRhdGEuZnJhbWUoeSx4KQ0KbW9kZWxfYXV0b2tvbCA8LSBsbSh5fngsIGRhdGEgPSBkYXRhX2F1dG9rb2wpDQpyZXMgPC0gcmVzaWQobG0oeX54LCBkYXRhID0gZGF0YV9hdXRva29sKSkNCmFjZihyZXMpDQpsbXRlc3Q6OmR3dGVzdChtb2RlbF9hdXRva29sKQ0KYGBgDQoNCiMjIyBEYXRhIFRpZGFrIEJlcmF1dG9rb3JlbGFzaQ0KYGBge3Igbm9rb2x9DQpyZXNfbm9uX2F1dG9rb2wgPC0gWl9ydW5pZg0KeCA8LSBydW5pZigxMDAsMCwxKQ0KYiA8LSBjKDEsMi43KQ0KaW5kZXBlbmRlbiA8LSBtb2RlbC5tYXRyaXgofngpDQp5IDwtIGluZGVwZW5kZW4gJSolIGIgKyByZXNfbm9uX2F1dG9rb2wNCmRhdGFfbm9uX2F1dG9rb2wgPC0gZGF0YS5mcmFtZSh5LHgpDQptb2RlbF9ub25fYXV0b2tvbCA8LSBsbSh5fngsIGRhdGEgPSBkYXRhX25vbl9hdXRva29sKQ0KcmVzIDwtIHJlc2lkKG1vZGVsX25vbl9hdXRva29sKQ0KYWNmKHJlcykNCmxtdGVzdDo6ZHd0ZXN0KG1vZGVsX25vbl9hdXRva29sKQ0KYGBgDQoNCiMjIyBFZmVrDQoNCmBgYHtyIHByZWRpa3NpQXV0b2tvbH0NCnByZWRpY3QobW9kZWxfYXV0b2tvbCxkYXRhX2F1dG9rb2wpICU+JSBoZWFkKDcpDQpwcmVkaWN0KG1vZGVsX25vbl9hdXRva29sLGRhdGFfbm9uX2F1dG9rb2wpICU+JSBoZWFkKDcpDQpgYGANCg0KYGBge3IgcnNxdWFyZUF1dG9rb2x9DQpyX3NxciA8LSBmdW5jdGlvbihkYXRhLCBtb2RlbCl7DQogIGFjdHVhbCA8LSBkYXRhJHkgI3ZhcmlhbnMgZGF0YSBhdXRva29sDQogIHByZWRzIDwtICBwcmVkaWN0KG1vZGVsKSNwcmVkaWtzaSBtb2RlbA0KICByc3MgPC0gc3VtKChwcmVkcyAtIGFjdHVhbCkgXiAyKSAgIyMgcmVzaWR1YWwgc3VtIG9mIHNxdWFyZXMNCiAgdHNzIDwtIHN1bSgoYWN0dWFsIC0gbWVhbihhY3R1YWwpKSBeIDIpICAjIyB0b3RhbCBzdW0gb2Ygc3F1YXJlcw0KICByZXR1cm4oMSAtIHJzcy90c3MpDQp9DQoNCnJfc3FyKGRhdGFfYXV0b2tvbCwgbW9kZWxfYXV0b2tvbCkNCnJfc3FyKGRhdGFfbm9uX2F1dG9rb2wsIG1vZGVsX25vbl9hdXRva29sKQ0KYGBgDQpUaWRhayBkaWp1bXBhaSBuaWxhaSBSLXNxdWFyZWQgeWFuZyB0aW5nZ2kgYW50YXJhIGtlZHVhIGRhdGEgeWFuZyB0ZWxhaCBkaXNpbXVsYXNpa2FuLCBha2FuIHRldGFwaSwgZGF0YSB5YW5nIGJlcmF1dG9rb3JlbGFzaSwgbWVtcHVueWFpIHBlbmdhcnVoIHZhcmlhYmVsIGxhZyB3YWt0dSBzZWJlbHVtbnlhIHRlcmhhZGFwIHZhcmlhYmVsIFksIHRlcmxpaGF0IGRhcmkgZ3JhZmlrIEFDRiB5YW5nIGJlcnBvbGEgc2VrdWVuc2lhbC4gU2VoaW5nZ2EgZGFwYXQgbWVtZW5nYXJ1aGkgcHJlZGlrc2kgZGFyaSBzZWJ1YWggbW9kZWwgcmVncmVzaS4NCg0KDQojIyA1LiBIRVRFUk9TS0VEQVNUSVNJVEFTDQpEYWxhbSByZWdyZXNpICBsaW5lYXIgc2FsYWggc2F0dSB5YW5nIGhhcnVzIGRpcGVudWhpIGFnYXIgdGFrc2lyYW4gcGFyYW1ldGVyIGRhbGFtIG1vZGVsIHRlcnNlYnV0IGJlcnNpZmF0IEJMVUUgKEJlc3QsIExpbmVhciwgVW5iaWFzZWQsIGFuZCBFc3RpbWF0b3IpLCBkaW1hbmEgdmFyICh1aSkgPSAkz4NeMiQgbWVtcHVueWFpIHZhcmlhc2kgeWFuZyBzYW1hLiBQYWRhIGthc3VzLWthc3VzIHRlcnRlbnR1IHRlcmphZGkgdmFyaWFzaSB1aSB0aWRhayBrb25zdGFuIGF0YXUgdmFyaWFiZWwgYmVydWJhaC11YmFoLiBVbnR1ayBtZW5kZXRla3NpIGhldGVyb3NrZWRhc3Rpc2l0YXMgZGFwYXQgZGlsYWt1a2FuIHBlbmd1amlhbiBkZW5nYW4gbWV0b2RlIGdyYWZpay4NCg0KRGVuZ2FuIHBlbmd1amlhbiBpbmkgZGFwYXQgZGlkZXRla3NpIGFwYWthaCBrZXNhbGFoYW4gcGVuZ2dhbmdndSBkYXJpIG1vZGVsIHlhbmcgZGlhbWF0aSB0aWRhayBtZW1pbGlraSB2YXJpYW5zIHlhbmcga29uc3RhbiBkYXJpIHNhdHUgb2JzZXJ2YXNpIGtlIG9ic2VydmFzaSBsYWlubnlhLiBEZW5nYW4gbWV0b2RlIGdyYWZpaywgaGFzaWxueWEgZGFwYXQgbWVudW5qdWtrYW4gYWRhIHRpZGFrbnlhIHBvbGEtcG9sYSB0ZXJ0ZW50dSB5YW5nIHRlcmJlbnR1ayBzZXBlcnRpIGJlcmdlbG9tYmFuZywgbWVsZWJhciBrZW11ZGlhbiBtZW55ZW1waXQgc2VydGEgdGl0aWstdGl0aWsgbWVueWViYXIgZGkgYXRhcyBkYW4gZGkgYmF3YWggYW5na2EgMCAobm9sKSBwYWRhIHN1bWJ1IFkuDQoNCiMjIyBSZXNpZHVhbCBIb21vc2tlZGFzdGlzDQpgYGB7ciBob21vfQ0KcmVzX2hvbW8gPC0gWl9ydW5pZg0KeCA8LSBydW5pZigxMDAsIDAsIDEpDQpiIDwtIGMoMSwyLjcpDQppbmRlcGVuZGVuIDwtIG1vZGVsLm1hdHJpeCh+eCkNCnkgPC0gaW5kZXBlbmRlbiAlKiUgYiArIHJlc19ob21vDQoNCm1vZGVsIDwtIGxtKHl+eCkNCnJlc2lkIDwtIHJlc2lkKG1vZGVsKQ0KcGxvdChyZXNpZCwgY29sID0gIiMwMDk5OTkiLCBsd2Q9NykNCg0KZGF0YV9ob21vIDwtIGRhdGEuZnJhbWUoeSx4KQ0KYGBgDQoNCiMjIyBSZXNpZHVhbCBIZXRlcm9za2VkYXN0aXMNCmBgYHtyIHNheU5vVG9Ib21vfQ0Kc2QgPC0gMToyNTANCnJlc19oZXRlcm8gPC0gcm5vcm0obj0xMDAsIG1lYW4gPSBzZCwgc2Q9LjIqc2QpDQoNCnggPC0gcnVuaWYoMTAwLDEsMikNCmIgPC0gYygxLDIuNykNCmluZGVwZW5kZW4gPC0gbW9kZWwubWF0cml4KH54KQ0KeSA8LSBpbmRlcGVuZGVuICUqJSBiICsgcmVzX2hldGVybw0KDQptb2RlbCA8LSBsbSh5fngpDQpyZXNpZHUgPC0gcmVzaWQobW9kZWwpDQoNCnBsb3QocmVzaWR1LGNvbCA9ICIjMDA5OTk5IiwgbHdkPTcpDQpkYXRhX2hldGVybyA8LSBkYXRhLmZyYW1lKHkseCkNCmBgYA0KDQojIyMgU3RhbmRhcmQgRXJyb3IgQ29tcGFyaXNvbg0KYGBge3IgU0Vjb21wYXJlfQ0Kc2V0LnNlZWQoU3lzLkRhdGUoKSkNCmNvbXBhcmVfc2UgPC0gZnVuY3Rpb24oZGF0YV9ob21vLCBkYXRhX2hldGVybyl7DQogIHN0ZGVIT01PIDwtIE5VTEwNCiAgZm9yIChpIGluIDE6MTAwKSB7DQogICAgdGVzSG8gPC0gbG0oeX54ICwgZGF0YV9ob21vICU+JSAgZHBseXI6OnNhbXBsZV9uKDEwLHJlcGxhY2UgPSBGQUxTRSkpDQogICAgc3RkZUhPTU8gPC0gYyhzdGRlSE9NTywgc3FydChkZXZpYW5jZSh0ZXNIbykvZGYucmVzaWR1YWwodGVzSG8pKSkNCiAgfQ0KICBTRV9ob21vIDwtIHZhcihzdGRlSE9NTykNCg0KICBzdGRlSEVURVJPIDwtIE5VTEwNCiAgZm9yIChpIGluIDE6MTAwKSB7DQogICAgdGVzSGUgPC0gbG0oeX54ICwgZGF0YSA9IGRhdGFfaGV0ZXJvICU+JSAgZHBseXI6OnNhbXBsZV9uKDEwLHJlcGxhY2UgPSBGQUxTRSkpDQogICAgc3RkZUhFVEVSTyA8LSBjKHN0ZGVIRVRFUk8sc3FydChkZXZpYW5jZSh0ZXNIZSkvZGYucmVzaWR1YWwodGVzSGUpKSkNCiAgfQ0KICBTRV9oZXRlcm8gPC0gdmFyKHN0ZGVIRVRFUk8pDQogIA0KICBoYXNpbCA8LSBkYXRhLmZyYW1lKFNFX2hvbW8sIFNFX2hldGVybykNCiAgcmV0dXJuKGhhc2lsKQ0KfQ0KY29tcGFyZV9zZShkYXRhX2hvbW8sIGRhdGFfaGV0ZXJvKQ0KYGBgDQpTdGFuZGFyZCBlcnJvciByZXNpZHVhbCBoZXRlcm9za2VkYXN0aXMgdGluZ2dpIGJpbGEgZGliYW5kaW5na2FuIGRlbmdhbiB5YW5nIGhvbW9za2VkYXN0aXMuIFNlbGFpbiBpdHUsIHJlc2lkdWFsIHlhbmcgaGV0ZXJvc2tlZGFzdGlzIGFrYW4gbWVueWViYWJrYW4gaGFzaWwgeWFuZyBvdmVyL3VuZGVyIGVzdGltYXRlLCBqaWthIGRpdGluamF1IGRhcmkgZ3JhZmlrIHlhbmcgYWRhIHBhZGEgcG9pbiBoZXRlcm8sIGhhc2lsIHlhbmcgZGlkYXBhdCBrZW11bmdraW5hbiBiZXNhciBha2FuIG92ZXJlc3RpbWF0ZSwga2FyZW5hIGdyYWZpayBzZW1ha2luIG1lbGViYXIga2Uga2FuYW4gc2VwYW5qYW5nIHQgKHdha3R1KS4=