Eğim Inis

Gerçek değer \(y\) ile tahminimiz \(h_\theta(x)\) arasındaki hatayı minimuma indirecek \(\theta^*\) değerini arıyoruz. Yapay öğrenme, en iyi \(\theta^*\) değerini öğrenmekten ibarettir. Hata fonksiyonu \[ Hata(\theta) = \frac{1}{2} (y - h_\theta(x))^2 \]

Hatayi minimuma indirecek parametre değerlerini, eğim iniş yöntemi ile bulacağız. \(Hata(\theta)\) fonksiyonun minimum noktasini

\[ \theta_i = \theta_i - \alpha \frac{d Hata(\theta)}{d\theta_i} \]

Bu \(\theta\) değerlerini nasıl güncelleyeceğimizi söyler. Türevin aksi yönde \(\alpha\) adım büyüklüğü ile orantılı olarak yol al. Basitten başlamak için, hata fonksiyonumuzun

\[ Hata(\theta) = \theta^2 + 5 \] olduğunu düşünelim. Bakalım eğim iniş yöntemi bu hata fonksiyonun minimum noktasını bula bilecek mi?

##########################################################
# Basit bir f fonksiyonun minimum noktasini bulalim
# f fonksiyonunu hata fonksiyonu gibi dusunelim
theta = -100:100
f <- function(theta){theta^2 + 5}
f.turev <- function(theta){2*theta}
guncelleme = 20 # guncelleme sayisi
basla = 94
##########################################################
dereceli.inis <- function(theta = basla, alpha = 0.025, dongu = guncelleme){
  th = rep(theta, dongu)
  for(i in 2:dongu){
    theta <- theta - alpha * f.turev(theta)
    th[i] = theta
  }
  return(th)
}
##########################################################
inis = dereceli.inis()
plot(theta,f(theta), type = 'l')
lines(inis, f(inis), type = 'o', col = "blue")
grid()

20 guncelleme sayisi ve \(\alpha = 0.025\) adım büyüklüğü ile hedefe ulaşamadık. Adım büyüklüğümüzü arttıralım.

##########################################################
inis = dereceli.inis(alpha = 0.05)
plot(theta,f(theta), type = 'l')
lines(inis, f(inis), type = 'o', col = "orange")
grid()

Az kaldı, biraz daha arttıtralım.

##########################################################
inis = dereceli.inis(alpha = 0.1)
plot(theta,f(theta), type = 'l')
lines(inis, f(inis), type = 'o', col = "red")
grid()

Şimdi oldu. Peki neden daha büyük adımlarla gitmeyelim? \(alpha = 1\) olursa ne olur mesela?

Iris Verisi

Şimdi çiçeklere ait bir veriyi inceleyeceğiz. Botanik bilmesek de yapay zeka tekniklerini biliyoruz.

################################################
# Veri hazirligi : Uc tur Cicek verisi yerine 2 tip cicek verisi ile calısacagiz
# Siniflandirma: 
#         Cicek "virginica" mi "setosa" mi?
#         x1 : 1
#         x2 : sepal-length (canak yaprak uzunlugu),
#         x3 : petal-length (tac yaprak uzunlugu), 
#         ozelliklerine bakarak  karar verecegiz
################################################
data_df <- as.data.frame(iris)
# iki tur cicekle ilgilenelim
tur <- data_df$Species %in% c("virginica", "setosa")
data_df <- data_df[tur,]
# 1: "virginica" ve 0: "setosa" olsun
y <- ifelse(data_df$Species=="virginica", 1, 0)
# 4 boyut (ozellik) yerine 2 boyut ozellik ile ilgilenelim => cizim kolayligi 
X <- data_df[c(1,3)]
X <- as.matrix(X/max(X))
# theta0 icin ilk kolon 1 yapildi
X = cbind(rep(1, length(y)), X)
# Verimizin ilk 6 degerlerine goz atalim
head(X)
    Sepal.Length Petal.Length
1 1    0.6455696    0.1772152
2 1    0.6202532    0.1772152
3 1    0.5949367    0.1645570
4 1    0.5822785    0.1898734
5 1    0.6329114    0.1772152
6 1    0.6835443    0.2151899
plot(X[,2], X[,3],col = y + 1,
     xlab = "Canak (sepal) yaprak uzunlugu",
     ylab = "Tac (petal) yaprak uzunlugu")
grid()

Modelimizi Oluşturalım

Bir yapay sinir hücresi, kendisine gelen uyarıları (\(x_1, x_2, x_3\)) önem dereceleri (\(\theta_1, \theta_2, \theta_3\)) ile çarpararak ağırlıklı bir toplam oluşturur.

\[z = \theta \cdot x = \theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3\]

Şimdi bu toplam girdiden sigmoid fonksiyonunu kullanarak tahminimizi oluşturacağız.

\[h_\theta(x) = \sigma (z) = \frac{1}{1 + e^{-z}}\]

Amacımız hipotezimiz \(h_\theta\) ile gerçek çıktı olan \(y\) arasındaki farkı en az indirecek \(\theta_0\), \(\theta_1\), \(\theta_2\) değerlerini bulmaktır. Şimdi tek bir örnek üzerinden yapılan hataya bir göz atalım

\[ Hata(\theta) = \frac{1}{2}(y - h_\theta(x))^2 \]

Hatayı minimize etmek için eğim iniş yöntemini kullanacağız. Hatanın türevini hesaplamamız gerekiyor. \[ \frac{d Hata(\theta)}{d\theta_i} = \frac{d Hata(\theta)}{dh_\theta(x)} \times \frac{d h_\theta(x)}{d\theta_i} = - (y - h_\theta(x)) \frac{d h_\theta(x)}{d\theta_i} \]

Demek ki, zincir kuralı gereği hipotezimin türevini hesaplamamız gerekiyor.

\[\begin{equation} \begin{split} \frac{d h_\theta(x)}{d\theta_i} &=& \frac{d \sigma (z)}{d\theta_i} \\ &=& \frac{d \sigma (z)}{dz} \frac{d z}{d\theta_i}\\ &=& \sigma (z) (1 - \sigma (z)) \frac{d z}{d\theta_i}\\ &=& \sigma (z) (1 - \sigma (z)) \frac{d (\theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3)}{d\theta_i}\\ &=& \sigma (z) (1 - \sigma (z)) x_i\\ &=& h_\theta(x) (1 - h_\theta(x)) x_i\\ \end{split} \end{equation}\]

Tüm bu matematiksel denklemleri bir araya getirip, hatamızın türevini hesaplayalım

\[ \frac{d Hata(\theta)}{d\theta_i} = (h_\theta(x) - y) h_\theta(x) (1 - h_\theta(x)) x_i \] Dereceli İniş

Hata fonksiyonun minimum noktasını elde etmek için adım adım aşağıdaki gibi ilerleyeceğiz.

\[ \theta_i = \theta_i - \alpha \frac{d Hata(\theta)}{d\theta_i} \] Sigmoid fonksiyonun dünya gözüyle bir görelim.

sigmoid <- function(z){
  return (1 / (1 + exp(-z)))
}
z = -10:10
plot(z, sigmoid(z), type="b")

Aşağıda i.inci gözlem için hatanın nasıl elde edildiğini matris ve vektör bakışıyla inceleyelim.

############################################################
# X gozlem verilerini tutan matristir
egim.inis <- function(X = X, y = y, th, adim = 0.5){
  z = X %*% th                          # gozlem verisini theta ile carpıyoruz 
  h = sigmoid(z)                        # sigmoid ile tahmın yapıyoruz
  hata = 0.5 * sum((y - h) *  (y - h))  # Toplam Hata: Tahmin ve gercek y arasındaki fark
  
  # Tum thetalar sadece BIR KEZ guncelleniyor
  for(i in 1:length(th)){
    gradyan = sum((h-y) * h * (1-h) * X[,i]) # Butun hatalarin toplami, Dikkat: h, y ve X[,i] ler ayni boyda
    th[i] = th[i] - adim * gradyan
  }
  # Thetalar ve tehmın hatasi geri donuyor
  return(list(th = th , hata = hata))
}
# ilk theta degerlerı 0 olsun
th <- rep(0,ncol(X))
# 
simulasyon = egim.inis(X, y , th)
th = simulasyon$th
print(simulasyon)
$th
[1] 0.0000000 0.6257911 1.6178797

$hata
[1] 12.5

Büyük bir hata var. Ama parametrelerimizi güncellemeyi sürdürürsek eğimli iniş bizi en iyi parametrelere götürecektir.

simulasyon = egim.inis(X, y , th)
th = simulasyon$th
print(simulasyon)
$th
[1] -3.151160 -1.270309  1.310737

$hata
[1] 11.79086
for(i in 1:10000){
  simulasyon = egim.inis(X, y , th, adim = 0.5)
  th = simulasyon$th
}
print(simulasyon)
$th
[1] -10.1470785   0.5655115  23.4601114

$hata
[1] 0.001531893

\(\theta_1 x_1 + \theta_2 x_2 + \theta_3 x_3 = 0\) ve \(x_1 = 1\) olduğuna göre

\[ x_3 = - \frac{\theta_2}{\theta_3}x_2 - \frac{\theta_1}{\theta_3} \]

model = (-th[2] * X[,2]) / th[3] - th[1] / th[3]
plot(X[,2], X[,3],col = y + 1,
     xlab = "Canak (sepal) yaprak uzunlugu",
     ylab = "Tac (petal) yaprak uzunlugu")
lines(X[,2],model)
grid()

Sentetik Veri

Dogrusal Sınıflandırma yöntemini kullanarak, sentetik bir veriyi iki sınıfa ayıralım.

n = 50
merkez1 = 5
kume1.x1 = rnorm(n, mean = merkez1, sd=3)
kume1.x2  = rnorm(n, mean = merkez1, sd=3)
kume1.y = rep(0,n)
merkez2 = 20
kume2.x1 = rnorm(n, mean = merkez2, sd=3)
kume2.x2  = rnorm(n, mean = merkez2, sd=3)
kume2.y = rep(0,n)
plot(kume1.x1,kume1.x2,col= "red", type = "p", xlim = c(0,30), ylim = c(0,30))
lines(kume2.x1,kume2.x2,col= "green", type = "p")
grid()

VX = cbind(rep(1,2*n),
          c(kume1.x1, kume2.x1),
          c(kume1.x2, kume2.x2))
Vy = c(rep(0,n),rep(1,n))
  
th = c(0,0,0)
for(i in 1:10000){
  simulasyon = egim.inis(VX, Vy , th, adim = 0.005)
  th = simulasyon$th
}
print(simulasyon)
$th
[1] -8.2541734  0.1781334  0.4628224

$hata
[1] 0.06215666
plot(VX[,2], VX[,3], col = Vy + 2, xlim = c(0,30), ylim = c(0,30))
model = (-th[2] * VX[,2]) / th[3] - th[1] / th[3]
lines(VX[,2],model)
grid()

Dikkat ederseniz yeni hiç bir kod yazmadık, önce bir botanikçi gibi çiçekleri birbirinden ayırdık sonra rastgele üretilmiş iki sınıf verisini birbirinden ayırdık. Gene hiçbir kod yazmadan eğer bize gerekli gözlem verisi verilirse, bir doktor gibi hasta-hasta değil ya da bir güvenlik uzmanı gibi spam-spam değil, ya da bir ekonomist gibi krediye uygun-krediye uygun değil, hatta bir siyasetçi gibi oy verir-oy vermez gibi ayrımları yapabiliriz.

Buradaki muhteşem gücün farkında mısınız?

Sadece basit bir yapay öğrenme aracını öğrendik ve bir doktor, bir ekonomist ya da bir siyasetçi gibi çalışma yapabilir hale geldik.

İşte bu yüzden gelecekte yapay zekayı kullanma dışında bir mesleğe hiç gerek kalmayabilir.

YSA Baslangıç

# Yeni bir veri kumesi ekleyelim
merkez3 = 35
kume3.x1 = rnorm(n, mean = merkez3, sd=3)
kume3.x2  = rnorm(n, mean = merkez3, sd=3)
kume3.y = rep(0,n)
VX = rbind(VX, cbind(rep(1,n),
          c(kume3.x1, kume3.x1),
          c(kume3.x2, kume3.x2)))
Vy = c(Vy, rep(0,n))
plot(VX[,2], VX[,3], col = Vy + 2, xlim = c(0,50), ylim = c(0,50))
grid()

Buradaki yeşil tip veriyi, kırmızı tip veriden ayırmak tek bir doğru ile mümkün değil.

Netlogo ile Oyun Programlama

extensions [sound]
breed [oyuncular oyuncu]          ;; iki oyuncu
breed [toplar top]                ;; bir top
toplar-own[hiz carpma-mesafesi]   ;; topun hizi ve carpma-mesafesi gibi ozellikleri var


to setup
  ca
  create-oyuncular 2 [
    set shape "face happy"        ;; baslangicta herkes mutlu
    set size 3
    set color blue
    ses
  ]
  create-toplar 1 [
    set shape "dot"
    set color red
    set size 2
    set heading (- 135)           ;; topun yonu
    set hiz 0.00005               ;; topun hizi
    set carpma-mesafesi 2         ;; topun mesafesi
  ]
  ask oyuncu 0 [setxy -20 0]      ;; oyuncu 0in konumu
  ask oyuncu 1 [setxy 20 0]       ;; oyuncu 1in konumu
  ask patches with [pxcor = [xcor] of oyuncu 0 or pxcor = [xcor] of oyuncu 1] [set pcolor white]
  ;; oyuncularin oldugu yerde dikey beyaz cizgi
end


to go
  oyna                           ;; top hareket ediyor
  carpma-kontrol                 ;; top bir yere carpti mi? kontrol et.
  if (kazan = true) [            ;; Oyunculardan biri kazandiysa ses cikar
    ses                              ;; ses cikar
    wait 2
    ses
    reset-oyuncular
    ask top 2 [
      setxy 0 0                      ;; topu ortaya al
      set heading random 360         ;; rtestgele yon ata
    ]
  ]
end



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Kim kazandi
to-report kazan
  if( [xcor] of top 2 < [xcor] of oyuncu 0)[
    ;;ask top 2 [set hiz 0]
    ask oyuncu 0 [
      set shape "face sad"
      set label "kaybettin"
      set color violet
    ]
    report true
  ]
  if( [xcor] of top 2 > [xcor] of oyuncu 1)[
    ;;ask top 2 [set hiz 0]
    ask oyuncu 1 [
      set shape "face sad"
      set label "kaybettin"
      set color violet
    ]
    report true
  ]
  report false
end


to reset-oyuncular
  ask oyuncular [
    set shape "face happy"        ;; baslangicta herkes mutlu
    set label ""
    set color blue
  ]
end


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Top Hareketi
to oyna
  ask top 2 [fd hiz]
end

to carpma-kontrol
  carpma-oyuncu0
  carpma-yatay-duvar
  carpma-dikey-duvar
end

to carpma-oyuncu0
  ask top 2 [
    if (distance oyuncu 0 < carpma-mesafesi) [     ;; topun oyuncu 0a mesafesi 2den az ise,
      show "oyuncu0a fazla yakin"
      set heading ( 360 - heading)   ;; topun geri yansir

      while [distance oyuncu 0 < carpma-mesafesi][fd hiz]
    ]
  ]
end

to carpma-yatay-duvar
  let y [ycor] of top 2
  ask top 2 [
    if (abs(y) > (abs(min-pycor) - 0.1)) [     ;; topun oyuncu 0a mesafesi 2den az ise,
      show "yatay duvara fazla yakin"
      set heading ( 180 - heading)   ;; topun geri yansir
    ]
  ]
end

to carpma-dikey-duvar
  let x [xcor] of top 2
  ask top 2 [
    if (abs(x) > (abs(min-pxcor) - 0.1)) [     ;; topun oyuncu 0a mesafesi 2den az ise,
      show "dikey duvara fazla yakin"
      set heading ( 360 - heading)   ;; topun geri yansir
    ]
  ]
end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Oyuncu Kontrol
to yukari
  let y [ycor] of oyuncu 0
  let x [xcor] of oyuncu 0
  ask oyuncu 0 [
    if(abs(y + 1) < abs(min-pycor)) [setxy x (y + 1)]
  ]
end

to asagi
  let y [ycor] of oyuncu 0
  let x [xcor] of oyuncu 0
  ask oyuncu 0 [
    if(abs(y - 1) < abs(min-pycor)) [setxy x (y - 1)]
  ]
end

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; Top Hareketi
to ses
  sound:play-drum "ACOUSTIC SNARE" 64
end

Python ile Programlamaya Giris

Netlogo ve R dillerinde daha önce gördüğümüz, veri tipleri, fonksiyonlar, kontrol yapıları ve döndüler pythın dilinin de temellerini oluşturur.

# Liste
L = [1, [1,2], 3]
print(L)
print(L[0])
print(L[1])
# Listenin uzunlugu
print(len(L))
[1, [1, 2], 3]
1
[1, 2]
3
a, b = 1, 8
a, b = b, a
print(a," ",b)
(8, ' ', 1)
# Fonksiyon
def degis(a,b):
    a, b = b, a
    return a, b

x, y = 3, 4
print("x, y = ", degis(x,y))
('x, y = ', (4, 3))
x, y = 3, 4
# Kontol
if(x > y):
    print(x, ",", y, "den buyuk")
else:
    print(y, ",", x, "den buyuk")
(4, ',', 3, 'den buyuk')
def kategori(yas):
    if yas<=18:
        durum="cocuk"
    elif yas>65:
        durum="emekli"
    else:
        durum="normal"
    return durum

print(kategori(15))
cocuk
Say = [1,2,3,4,5,6,7]
for i in Say:  
    print(i**2)   
1
4
9
16
25
36
49
# range([bas,] son [,adim]) : bas varsayilan degeri 0, adim varsayilan degeri 1
for i in range(4,10,2):
    print(i)
4
6
8
# Sozlukler
DB = {
    "uzay" : {"Star Wars": 4.5, "Superman": 3.5,"Batman": 4,},
    "selin" : {"Venedik": 4.5, "Paris": 3.5,"Batman": 4,},
    "fatih" : {"Superman": 4,"Batman": 4},
}
print("\nUzay Begenileri: ", DB['uzay'])
print("Uzayin Star Wars filmine verdigi puan: ", DB['uzay']['Star Wars'])
('\nUzay Begenileri: ', {'Star Wars': 4.5, 'Batman': 4, 'Superman': 3.5})
('Uzayin Star Wars filmine verdigi puan: ', 4.5)
# Sozlukler
DB = {
    "uzay" : {"Star Wars": 4.5, "Superman": 3.5,"Batman": 4,},
    "selin" : {"Venedik": 4.5, "Paris": 3.5,"Batman": 4,},
    "fatih" : {"Superman": 4,"Batman": 4},
}
# Yeni deger ekleme
DB.setdefault("Umut", {"Maymunlar Cehennemi": 4, "Babam ve Oglum": 3})
print(DB)
print("\n\n")
for k in DB.keys():  
    print(k)  
{'selin': {'Paris': 3.5, 'Batman': 4, 'Venedik': 4.5}, 'Umut': {'Maymunlar Cehennemi': 4, 'Babam ve Oglum': 3}, 'fatih': {'Batman': 4, 'Superman': 4}, 'uzay': {'Star Wars': 4.5, 'Batman': 4, 'Superman': 3.5}}



selin
Umut
fatih
uzay
# Sozlukler
DB = {
    "uzay" : {"Star Wars": 4.5, "Superman": 3.5,"Batman": 4,},
    "selin" : {"Venedik": 4.5, "Paris": 3.5,"Batman": 4,},
    "fatih" : {"Superman": 4,"Batman": 4},
}
# Yeni deger ekleme
DB.setdefault("Umut", {"Maymunlar Cehennemi": 4, "Babam ve Oglum": 3})

for deger in DB.values():  
    print(deger)
{'Paris': 3.5, 'Batman': 4, 'Venedik': 4.5}
{'Maymunlar Cehennemi': 4, 'Babam ve Oglum': 3}
{'Batman': 4, 'Superman': 4}
{'Star Wars': 4.5, 'Batman': 4, 'Superman': 3.5}
# Ileri Liste Islemler
print([x*5 for x in range(5)])
print([x for x in range(5) if x%2 == 0])
[0, 5, 10, 15, 20]
[0, 2, 4]
import numpy as np
liste = np.array(range(5))
print(liste)
[0 1 2 3 4]
import numpy as np
liste = np.array(range(5))
liste = liste * liste
print(liste)

import math
for i in liste:
    print(math.sqrt(i))
[ 0  1  4  9 16]
0.0
1.0
2.0
3.0
4.0
import numpy as np
liste = np.array([0, 1,  4,  9, 16])
print(len(liste))
print("liste[liste > 5]: ", liste[liste > 5])

liste = np.append(liste, [25,36,49])
print(liste)

liste = liste - 16
liste[liste>0] = 1
liste[liste<0] = -1
print(liste)

liste2 = np.zeros(8)
liste2[5:] = -1
print(liste2)
print(liste + liste2)
5
('liste[liste > 5]: ', array([ 9, 16]))
[ 0  1  4  9 16 25 36 49]
[-1 -1 -1 -1  0  1  1  1]
[ 0.  0.  0.  0.  0. -1. -1. -1.]
[-1. -1. -1. -1.  0.  0.  0.  0.]

Daha fazlasi icin python ve numpy kodlari: https://s3.amazonaws.com/assets.datacamp.com/blog_assets/Numpy_Python_Cheat_Sheet.pdf

LS0tCnRpdGxlOiAiWWFwYXkgU2luaXIgQcSfbGFyxLFuYSBHaXJpxZ8iCmF1dGhvcjogRHIuIFV6YXkgw4dldGluCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCgojIyBFxJ9pbSBJbmlzCkdlcsOnZWsgZGXEn2VyICR5JCBpbGUgdGFobWluaW1peiAkaF9cdGhldGEoeCkkIGFyYXPEsW5kYWtpIGhhdGF5xLEgbWluaW11bWEgaW5kaXJlY2VrICRcdGhldGFeKiQgZGXEn2VyaW5pIGFyxLF5b3J1ei4gWWFwYXkgw7bEn3Jlbm1lLCBlbiBpeWkgJFx0aGV0YV4qJCBkZcSfZXJpbmkgw7bEn3Jlbm1la3RlbiBpYmFyZXR0aXIuIEhhdGEgZm9ua3NpeW9udQokJApIYXRhKFx0aGV0YSkgPSBcZnJhY3sxfXsyfSAoeSAtIGhfXHRoZXRhKHgpKV4yCiQkCgpIYXRheWkgbWluaW11bWEgaW5kaXJlY2VrIHBhcmFtZXRyZSBkZcSfZXJsZXJpbmksIGXEn2ltIGluacWfIHnDtm50ZW1pIGlsZSBidWxhY2HEn8Sxei4gJEhhdGEoXHRoZXRhKSQgZm9ua3NpeW9udW4gbWluaW11bSBub2t0YXNpbmkKCiQkClx0aGV0YV9pID0gXHRoZXRhX2kgLSBcYWxwaGEgXGZyYWN7ZCBIYXRhKFx0aGV0YSl9e2RcdGhldGFfaX0KJCQKCkJ1ICRcdGhldGEkIGRlxJ9lcmxlcmluaSBuYXPEsWwgZ8O8bmNlbGxleWVjZcSfaW1pemkgc8O2eWxlci4gVMO8cmV2aW4gYWtzaSB5w7ZuZGUgJFxhbHBoYSQgYWTEsW0gYsO8ecO8a2zDvMSfw7wgaWxlIG9yYW50xLFsxLEgb2xhcmFrIHlvbCBhbC4gQmFzaXR0ZW4gYmHFn2xhbWFrIGnDp2luLCBoYXRhIGZvbmtzaXlvbnVtdXp1bgoKJCQKSGF0YShcdGhldGEpID0gXHRoZXRhXjIgKyA1CiQkCm9sZHXEn3VudSBkw7zFn8O8bmVsaW0uIEJha2FsxLFtIGXEn2ltIGluacWfIHnDtm50ZW1pIGJ1IGhhdGEgZm9ua3NpeW9udW4gbWluaW11bSBub2t0YXPEsW7EsSBidWxhIGJpbGVjZWsgbWk/CgpgYGB7cn0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojIEJhc2l0IGJpciBmIGZvbmtzaXlvbnVuIG1pbmltdW0gbm9rdGFzaW5pIGJ1bGFsaW0KIyBmIGZvbmtzaXlvbnVudSBoYXRhIGZvbmtzaXlvbnUgZ2liaSBkdXN1bmVsaW0KdGhldGEgPSAtMTAwOjEwMApmIDwtIGZ1bmN0aW9uKHRoZXRhKXt0aGV0YV4yICsgNX0KZi50dXJldiA8LSBmdW5jdGlvbih0aGV0YSl7Mip0aGV0YX0KZ3VuY2VsbGVtZSA9IDIwICMgZ3VuY2VsbGVtZSBzYXlpc2kKYmFzbGEgPSA5NAojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCmRlcmVjZWxpLmluaXMgPC0gZnVuY3Rpb24odGhldGEgPSBiYXNsYSwgYWxwaGEgPSAwLjAyNSwgZG9uZ3UgPSBndW5jZWxsZW1lKXsKICB0aCA9IHJlcCh0aGV0YSwgZG9uZ3UpCiAgZm9yKGkgaW4gMjpkb25ndSl7CiAgICB0aGV0YSA8LSB0aGV0YSAtIGFscGhhICogZi50dXJldih0aGV0YSkKICAgIHRoW2ldID0gdGhldGEKICB9CiAgcmV0dXJuKHRoKQp9CiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKaW5pcyA9IGRlcmVjZWxpLmluaXMoKQpwbG90KHRoZXRhLGYodGhldGEpLCB0eXBlID0gJ2wnKQpsaW5lcyhpbmlzLCBmKGluaXMpLCB0eXBlID0gJ28nLCBjb2wgPSAiYmx1ZSIpCmdyaWQoKQpgYGAKCjIwIGd1bmNlbGxlbWUgc2F5aXNpIHZlICRcYWxwaGEgPSAwLjAyNSQgYWTEsW0gYsO8ecO8a2zDvMSfw7wgaWxlIGhlZGVmZSB1bGHFn2FtYWTEsWsuIEFkxLFtIGLDvHnDvGtsw7zEn8O8bcO8esO8IGFydHTEsXJhbMSxbS4KCmBgYHtyfQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCmluaXMgPSBkZXJlY2VsaS5pbmlzKGFscGhhID0gMC4wNSkKcGxvdCh0aGV0YSxmKHRoZXRhKSwgdHlwZSA9ICdsJykKbGluZXMoaW5pcywgZihpbmlzKSwgdHlwZSA9ICdvJywgY29sID0gIm9yYW5nZSIpCmdyaWQoKQpgYGAKQXoga2FsZMSxLCBiaXJheiBkYWhhIGFydHTEsXRyYWzEsW0uCgpgYGB7cn0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwppbmlzID0gZGVyZWNlbGkuaW5pcyhhbHBoYSA9IDAuMSkKcGxvdCh0aGV0YSxmKHRoZXRhKSwgdHlwZSA9ICdsJykKbGluZXMoaW5pcywgZihpbmlzKSwgdHlwZSA9ICdvJywgY29sID0gInJlZCIpCmdyaWQoKQpgYGAKCsWeaW1kaSBvbGR1LiBQZWtpIG5lZGVuIGRhaGEgYsO8ecO8ayBhZMSxbWxhcmxhIGdpdG1leWVsaW0/CiRhbHBoYSA9IDEkIG9sdXJzYSBuZSBvbHVyIG1lc2VsYT8KCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgoKCgojIyBJcmlzIFZlcmlzaSAKxZ5pbWRpIMOnacOnZWtsZXJlIGFpdCBiaXIgdmVyaXlpIGluY2VsZXllY2XEn2l6LiBCb3RhbmlrIGJpbG1lc2VrIGRlIHlhcGF5IHpla2EgdGVrbmlrbGVyaW5pIGJpbGl5b3J1ei4gCgo8cCBzdHlsZT0idGV4dC1hbGlnbjpjZW50ZXI7Ij48aW1nIHNyYz0iaXJpcy5wbmciICB3aWR0aD0iNTYwIiBoZWlnaHQ9IjMxNSI+PC9wPgoKYGBge3J9CiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIwojIFZlcmkgaGF6aXJsaWdpIDogVWMgdHVyIENpY2VrIHZlcmlzaSB5ZXJpbmUgMiB0aXAgY2ljZWsgdmVyaXNpIGlsZSBjYWzEsXNhY2FnaXoKIyBTaW5pZmxhbmRpcm1hOiAKIyAgICAgICAgIENpY2VrICJ2aXJnaW5pY2EiIG1pICJzZXRvc2EiIG1pPwojICAgICAgICAgeDEgOiAxCiMgICAgICAgICB4MiA6IHNlcGFsLWxlbmd0aCAoY2FuYWsgeWFwcmFrIHV6dW5sdWd1KSwKIyAgICAgICAgIHgzIDogcGV0YWwtbGVuZ3RoICh0YWMgeWFwcmFrIHV6dW5sdWd1KSwgCiMgICAgICAgICBvemVsbGlrbGVyaW5lIGJha2FyYWsgIGthcmFyIHZlcmVjZWdpegojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKZGF0YV9kZiA8LSBhcy5kYXRhLmZyYW1lKGlyaXMpCiMgaWtpIHR1ciBjaWNla2xlIGlsZ2lsZW5lbGltCnR1ciA8LSBkYXRhX2RmJFNwZWNpZXMgJWluJSBjKCJ2aXJnaW5pY2EiLCAic2V0b3NhIikKZGF0YV9kZiA8LSBkYXRhX2RmW3R1cixdCiMgMTogInZpcmdpbmljYSIgdmUgMDogInNldG9zYSIgb2xzdW4KeSA8LSBpZmVsc2UoZGF0YV9kZiRTcGVjaWVzPT0idmlyZ2luaWNhIiwgMSwgMCkKIyA0IGJveXV0IChvemVsbGlrKSB5ZXJpbmUgMiBib3l1dCBvemVsbGlrIGlsZSBpbGdpbGVuZWxpbSA9PiBjaXppbSBrb2xheWxpZ2kgClggPC0gZGF0YV9kZltjKDEsMyldClggPC0gYXMubWF0cml4KFgvbWF4KFgpKQojIHRoZXRhMCBpY2luIGlsayBrb2xvbiAxIHlhcGlsZGkKWCA9IGNiaW5kKHJlcCgxLCBsZW5ndGgoeSkpLCBYKQoKIyBWZXJpbWl6aW4gaWxrIDYgZGVnZXJsZXJpbmUgZ296IGF0YWxpbQpoZWFkKFgpCnBsb3QoWFssMl0sIFhbLDNdLGNvbCA9IHkgKyAxLAogICAgIHhsYWIgPSAiQ2FuYWsgKHNlcGFsKSB5YXByYWsgdXp1bmx1Z3UiLAogICAgIHlsYWIgPSAiVGFjIChwZXRhbCkgeWFwcmFrIHV6dW5sdWd1IikKZ3JpZCgpCgoKYGBgCgoKCgojIE1vZGVsaW1pemkgT2x1xZ90dXJhbMSxbQpCaXIgeWFwYXkgc2luaXIgaMO8Y3Jlc2ksIGtlbmRpc2luZSBnZWxlbiB1eWFyxLFsYXLEsSAoJHhfMSwgeF8yLCB4XzMkKSDDtm5lbSBkZXJlY2VsZXJpICgkXHRoZXRhXzEsIFx0aGV0YV8yLCBcdGhldGFfMyQpIGlsZSDDp2FycGFyYXJhayBhxJ/EsXJsxLFrbMSxIGJpciB0b3BsYW0gb2x1xZ90dXJ1ci4KCiQkeiA9IFx0aGV0YSBcY2RvdCB4ID0gXHRoZXRhXzEgeF8xICsgXHRoZXRhXzIgeF8yICsgXHRoZXRhXzMgeF8zJCQKCsWeaW1kaSBidSB0b3BsYW0gZ2lyZGlkZW4gc2lnbW9pZCBmb25rc2l5b251bnUga3VsbGFuYXJhayB0YWhtaW5pbWl6aSBvbHXFn3R1cmFjYcSfxLF6LgoKJCRoX1x0aGV0YSh4KSA9IFxzaWdtYSAoeikgPSBcZnJhY3sxfXsxICsgZV57LXp9fSQkCgoKCgo8cCBzdHlsZT0idGV4dC1hbGlnbjpjZW50ZXI7Ij48aW1nIHNyYz0ibm9yb24ucGRmIiAgd2lkdGg9IjU2MCIgaGVpZ2h0PSIzMTUiPjwvcD4KCgpBbWFjxLFtxLF6IGhpcG90ZXppbWl6ICRoX1x0aGV0YSQgaWxlIGdlcsOnZWsgw6fEsWt0xLEgb2xhbiAkeSQgYXJhc8SxbmRha2kgZmFya8SxIGVuIGF6IGluZGlyZWNlayAkXHRoZXRhXzAkLCAkXHRoZXRhXzEkLCAkXHRoZXRhXzIkIGRlxJ9lcmxlcmluaSBidWxtYWt0xLFyLiDFnmltZGkgdGVrIGJpciDDtnJuZWsgw7x6ZXJpbmRlbiB5YXDEsWxhbiBoYXRheWEgYmlyIGfDtnogYXRhbMSxbQoKJCQKSGF0YShcdGhldGEpID0gXGZyYWN7MX17Mn0oeSAtIGhfXHRoZXRhKHgpKV4yCiQkCgpIYXRhecSxIG1pbmltaXplIGV0bWVrIGnDp2luIGXEn2ltIGluacWfIHnDtm50ZW1pbmkga3VsbGFuYWNhxJ/EsXouIEhhdGFuxLFuIHTDvHJldmluaSBoZXNhcGxhbWFtxLF6IGdlcmVraXlvci4gCiQkClxmcmFje2QgSGF0YShcdGhldGEpfXtkXHRoZXRhX2l9ID0KXGZyYWN7ZCBIYXRhKFx0aGV0YSl9e2RoX1x0aGV0YSh4KX0gXHRpbWVzIFxmcmFje2QgaF9cdGhldGEoeCl9e2RcdGhldGFfaX0KPSAtICh5IC0gaF9cdGhldGEoeCkpIFxmcmFje2QgaF9cdGhldGEoeCl9e2RcdGhldGFfaX0KJCQKCkRlbWVrIGtpLCB6aW5jaXIga3VyYWzEsSBnZXJlxJ9pIGhpcG90ZXppbWluIHTDvHJldmluaSBoZXNhcGxhbWFtxLF6IGdlcmVraXlvci4gCgpcYmVnaW57ZXF1YXRpb259IApcYmVnaW57c3BsaXR9ClxmcmFje2QgaF9cdGhldGEoeCl9e2RcdGhldGFfaX0gJj0mICBcZnJhY3tkIFxzaWdtYSAoeil9e2RcdGhldGFfaX0gXFwgCiY9JiBcZnJhY3tkIFxzaWdtYSAoeil9e2R6fSBcZnJhY3tkIHp9e2RcdGhldGFfaX1cXAomPSYgXHNpZ21hICh6KSAoMSAtIFxzaWdtYSAoeikpIFxmcmFje2Qgen17ZFx0aGV0YV9pfVxcCiY9JiBcc2lnbWEgKHopICgxIC0gXHNpZ21hICh6KSkgXGZyYWN7ZCAoXHRoZXRhXzEgeF8xICsgXHRoZXRhXzIgeF8yICsgXHRoZXRhXzMgeF8zKX17ZFx0aGV0YV9pfVxcCiY9JiBcc2lnbWEgKHopICgxIC0gXHNpZ21hICh6KSkgeF9pXFwKJj0mIGhfXHRoZXRhKHgpICgxIC0gaF9cdGhldGEoeCkpIHhfaVxcClxlbmR7c3BsaXR9ClxlbmR7ZXF1YXRpb259CgpUw7xtIGJ1IG1hdGVtYXRpa3NlbCBkZW5rbGVtbGVyaSBiaXIgYXJheWEgZ2V0aXJpcCwgaGF0YW3EsXrEsW4gdMO8cmV2aW5pIGhlc2FwbGF5YWzEsW0KCiQkClxmcmFje2QgSGF0YShcdGhldGEpfXtkXHRoZXRhX2l9ID0gIChoX1x0aGV0YSh4KSAtIHkpIGhfXHRoZXRhKHgpICgxIC0gaF9cdGhldGEoeCkpIHhfaQokJApgRGVyZWNlbGkgxLBuacWfYAoKSGF0YSBmb25rc2l5b251biBtaW5pbXVtIG5va3Rhc8SxbsSxIGVsZGUgZXRtZWsgacOnaW4gYWTEsW0gYWTEsW0gYcWfYcSfxLFkYWtpIGdpYmkgaWxlcmxleWVjZcSfaXouCgokJApcdGhldGFfaSA9IFx0aGV0YV9pIC0gXGFscGhhIFxmcmFje2QgSGF0YShcdGhldGEpfXtkXHRoZXRhX2l9CiQkClNpZ21vaWQgZm9ua3NpeW9udW4gZMO8bnlhIGfDtnrDvHlsZSBiaXIgZ8O2cmVsaW0uCmBgYHtyfQpzaWdtb2lkIDwtIGZ1bmN0aW9uKHopewogIHJldHVybiAoMSAvICgxICsgZXhwKC16KSkpCn0KeiA9IC0xMDoxMApwbG90KHosIHNpZ21vaWQoeiksIHR5cGU9ImIiKQpgYGAKCkHFn2HEn8SxZGEgaS5pbmNpIGfDtnpsZW0gacOnaW4gaGF0YW7EsW4gbmFzxLFsIGVsZGUgZWRpbGRpxJ9pbmkgbWF0cmlzIHZlIHZla3TDtnIgYmFrxLHFn8SxeWxhIGluY2VsZXllbGltLgo8cCBzdHlsZT0idGV4dC1hbGlnbjpjZW50ZXI7Ij48aW1nIHNyYz0ibWF0cmlzLnBkZiIgIHdpZHRoPSI1NjAiIGhlaWdodD0iMzE1Ij48L3A+CgpgYGB7cn0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCiMgWCBnb3psZW0gdmVyaWxlcmluaSB0dXRhbiBtYXRyaXN0aXIKZWdpbS5pbmlzIDwtIGZ1bmN0aW9uKFggPSBYLCB5ID0geSwgdGgsIGFkaW0gPSAwLjUpewogIHogPSBYICUqJSB0aCAgICAgICAgICAgICAgICAgICAgICAgICAgIyBnb3psZW0gdmVyaXNpbmkgdGhldGEgaWxlIGNhcnDEsXlvcnV6IAogIGggPSBzaWdtb2lkKHopICAgICAgICAgICAgICAgICAgICAgICAgIyBzaWdtb2lkIGlsZSB0YWhtxLFuIHlhcMSxeW9ydXoKICBoYXRhID0gMC41ICogc3VtKCh5IC0gaCkgKiAgKHkgLSBoKSkgICMgVG9wbGFtIEhhdGE6IFRhaG1pbiB2ZSBnZXJjZWsgeSBhcmFzxLFuZGFraSBmYXJrCiAgCiAgIyBUdW0gdGhldGFsYXIgc2FkZWNlIEJJUiBLRVogZ3VuY2VsbGVuaXlvcgogIGZvcihpIGluIDE6bGVuZ3RoKHRoKSl7CiAgICBncmFkeWFuID0gc3VtKChoLXkpICogaCAqICgxLWgpICogWFssaV0pICMgQnV0dW4gaGF0YWxhcmluIHRvcGxhbWksIERpa2thdDogaCwgeSB2ZSBYWyxpXSBsZXIgYXluaSBib3lkYQogICAgdGhbaV0gPSB0aFtpXSAtIGFkaW0gKiBncmFkeWFuCiAgfQogICMgVGhldGFsYXIgdmUgdGVobcSxbiBoYXRhc2kgZ2VyaSBkb251eW9yCiAgcmV0dXJuKGxpc3QodGggPSB0aCAsIGhhdGEgPSBoYXRhKSkKfQpgYGAKCmBgYHtyfQojIGlsayB0aGV0YSBkZWdlcmxlcsSxIDAgb2xzdW4KdGggPC0gcmVwKDAsbmNvbChYKSkKIyAKc2ltdWxhc3lvbiA9IGVnaW0uaW5pcyhYLCB5ICwgdGgpCnRoID0gc2ltdWxhc3lvbiR0aApwcmludChzaW11bGFzeW9uKQpgYGAKCkLDvHnDvGsgYmlyIGhhdGEgdmFyLiBBbWEgcGFyYW1ldHJlbGVyaW1pemkgZ8O8bmNlbGxlbWV5aSBzw7xyZMO8csO8cnNlayBlxJ9pbWxpIGluacWfIGJpemkgZW4gaXlpIHBhcmFtZXRyZWxlcmUgZ8O2dMO8cmVjZWt0aXIuCgpgYGB7cn0Kc2ltdWxhc3lvbiA9IGVnaW0uaW5pcyhYLCB5ICwgdGgpCnRoID0gc2ltdWxhc3lvbiR0aApwcmludChzaW11bGFzeW9uKQpgYGAKCgoKYGBge3J9CmZvcihpIGluIDE6MTAwMDApewogIHNpbXVsYXN5b24gPSBlZ2ltLmluaXMoWCwgeSAsIHRoLCBhZGltID0gMC41KQogIHRoID0gc2ltdWxhc3lvbiR0aAp9CnByaW50KHNpbXVsYXN5b24pCmBgYAoKJFx0aGV0YV8xIHhfMSArIFx0aGV0YV8yIHhfMiArIFx0aGV0YV8zIHhfMyA9IDAkIHZlICR4XzEgPSAgMSQKb2xkdcSfdW5hIGfDtnJlCgokJAp4XzMgPSAtIFxmcmFje1x0aGV0YV8yfXtcdGhldGFfM314XzIgLSBcZnJhY3tcdGhldGFfMX17XHRoZXRhXzN9CiQkCgoKYGBge3J9Cm1vZGVsID0gKC10aFsyXSAqIFhbLDJdKSAvIHRoWzNdIC0gdGhbMV0gLyB0aFszXQpwbG90KFhbLDJdLCBYWywzXSxjb2wgPSB5ICsgMSwKICAgICB4bGFiID0gIkNhbmFrIChzZXBhbCkgeWFwcmFrIHV6dW5sdWd1IiwKICAgICB5bGFiID0gIlRhYyAocGV0YWwpIHlhcHJhayB1enVubHVndSIpCmxpbmVzKFhbLDJdLG1vZGVsKQpncmlkKCkKYGBgCgoKCiMjIFNlbnRldGlrIFZlcmkKCkRvZ3J1c2FsIFPEsW7EsWZsYW5kxLFybWEgecO2bnRlbWluaSBrdWxsYW5hcmFrLCBzZW50ZXRpayBiaXIgdmVyaXlpIGlraSBzxLFuxLFmYSBhecSxcmFsxLFtLgoKCmBgYHtyfQoKbiA9IDUwCgptZXJrZXoxID0gNQprdW1lMS54MSA9IHJub3JtKG4sIG1lYW4gPSBtZXJrZXoxLCBzZD0zKQprdW1lMS54MiAgPSBybm9ybShuLCBtZWFuID0gbWVya2V6MSwgc2Q9MykKa3VtZTEueSA9IHJlcCgwLG4pCgptZXJrZXoyID0gMjAKa3VtZTIueDEgPSBybm9ybShuLCBtZWFuID0gbWVya2V6Miwgc2Q9MykKa3VtZTIueDIgID0gcm5vcm0obiwgbWVhbiA9IG1lcmtlejIsIHNkPTMpCmt1bWUyLnkgPSByZXAoMCxuKQoKcGxvdChrdW1lMS54MSxrdW1lMS54Mixjb2w9ICJyZWQiLCB0eXBlID0gInAiLCB4bGltID0gYygwLDMwKSwgeWxpbSA9IGMoMCwzMCkpCmxpbmVzKGt1bWUyLngxLGt1bWUyLngyLGNvbD0gImdyZWVuIiwgdHlwZSA9ICJwIikKZ3JpZCgpCmBgYAoKYGBge3J9ClZYID0gY2JpbmQocmVwKDEsMipuKSwKICAgICAgICAgIGMoa3VtZTEueDEsIGt1bWUyLngxKSwKICAgICAgICAgIGMoa3VtZTEueDIsIGt1bWUyLngyKSkKVnkgPSBjKHJlcCgwLG4pLHJlcCgxLG4pKQogIAp0aCA9IGMoMCwwLDApCmZvcihpIGluIDE6MTAwMDApewogIHNpbXVsYXN5b24gPSBlZ2ltLmluaXMoVlgsIFZ5ICwgdGgsIGFkaW0gPSAwLjAwNSkKICB0aCA9IHNpbXVsYXN5b24kdGgKfQpwcmludChzaW11bGFzeW9uKQpgYGAKCmBgYHtyfQpwbG90KFZYWywyXSwgVlhbLDNdLCBjb2wgPSBWeSArIDIsIHhsaW0gPSBjKDAsMzApLCB5bGltID0gYygwLDMwKSkKbW9kZWwgPSAoLXRoWzJdICogVlhbLDJdKSAvIHRoWzNdIC0gdGhbMV0gLyB0aFszXQpsaW5lcyhWWFssMl0sbW9kZWwpCmdyaWQoKQpgYGAKCgpEaWtrYXQgZWRlcnNlbml6IHllbmkgaGnDpyBiaXIga29kIHlhem1hZMSxaywgw7ZuY2UgYmlyIGJvdGFuaWvDp2kgZ2liaSDDp2nDp2VrbGVyaSBiaXJiaXJpbmRlbiBhecSxcmTEsWsgc29ucmEgcmFzdGdlbGUgw7xyZXRpbG1pxZ8gaWtpIHPEsW7EsWYgdmVyaXNpbmkgYmlyYmlyaW5kZW4gYXnEsXJkxLFrLiBHZW5lIGhpw6diaXIga29kIHlhem1hZGFuIGXEn2VyIGJpemUgZ2VyZWtsaSBnw7Z6bGVtIHZlcmlzaSB2ZXJpbGlyc2UsIGJpciBkb2t0b3IgZ2liaSBoYXN0YS1oYXN0YSBkZcSfaWwgeWEgZGEgYmlyIGfDvHZlbmxpayB1em1hbsSxIGdpYmkgc3BhbS1zcGFtIGRlxJ9pbCwgeWEgZGEgYmlyIGVrb25vbWlzdCBnaWJpIGtyZWRpeWUgdXlndW4ta3JlZGl5ZSB1eWd1biBkZcSfaWwsIGhhdHRhIGJpciBzaXlhc2V0w6dpIGdpYmkgb3kgdmVyaXItb3kgdmVybWV6IGdpYmkgYXlyxLFtbGFyxLEgeWFwYWJpbGlyaXouIAoKPiBCdXJhZGFraSBtdWh0ZcWfZW0gZ8O8Y8O8biBmYXJrxLFuZGEgbcSxc8SxbsSxej8gCgpTYWRlY2UgYmFzaXQgYmlyIHlhcGF5IMO2xJ9yZW5tZSBhcmFjxLFuxLEgw7bEn3JlbmRpayB2ZSBiaXIgZG9rdG9yLCBiaXIgZWtvbm9taXN0IHlhIGRhIGJpciBzaXlhc2V0w6dpIGdpYmkgw6dhbMSxxZ9tYSB5YXBhYmlsaXIgaGFsZSBnZWxkaWsuIAoKPiDEsMWfdGUgYnUgecO8emRlbiBnZWxlY2VrdGUgeWFwYXkgemVrYXnEsSBrdWxsYW5tYSBkxLHFn8SxbmRhIGJpciBtZXNsZcSfZSBoacOnIGdlcmVrIGthbG1heWFiaWxpci4KCgojIFlTQSBCYXNsYW5nxLHDpwoKYGBge3J9CiMgWWVuaSBiaXIgdmVyaSBrdW1lc2kgZWtsZXllbGltCm1lcmtlejMgPSAzNQprdW1lMy54MSA9IHJub3JtKG4sIG1lYW4gPSBtZXJrZXozLCBzZD0zKQprdW1lMy54MiAgPSBybm9ybShuLCBtZWFuID0gbWVya2V6Mywgc2Q9MykKa3VtZTMueSA9IHJlcCgwLG4pCgpWWCA9IHJiaW5kKFZYLCBjYmluZChyZXAoMSxuKSwKICAgICAgICAgIGMoa3VtZTMueDEsIGt1bWUzLngxKSwKICAgICAgICAgIGMoa3VtZTMueDIsIGt1bWUzLngyKSkpClZ5ID0gYyhWeSwgcmVwKDAsbikpCgpwbG90KFZYWywyXSwgVlhbLDNdLCBjb2wgPSBWeSArIDIsIHhsaW0gPSBjKDAsNTApLCB5bGltID0gYygwLDUwKSkKZ3JpZCgpCmBgYAoKQnVyYWRha2kgeWXFn2lsIHRpcCB2ZXJpeWksIGvEsXJtxLF6xLEgdGlwIHZlcmlkZW4gYXnEsXJtYWsgdGVrIGJpciBkb8SfcnUgaWxlIG3DvG1rw7xuIGRlxJ9pbC4KCgojIE5ldGxvZ28gaWxlIE95dW4gUHJvZ3JhbWxhbWEKCjxwIHN0eWxlPSJ0ZXh0LWFsaWduOmNlbnRlcjsiPjxpbWcgc3JjPSJveXVuLnBuZyIgIHdpZHRoPSI1NjAiIGhlaWdodD0iMzE1Ij48L3A+CgpgYGB7ciwgZXZhbD1GQUxTRX0KZXh0ZW5zaW9ucyBbc291bmRdCmJyZWVkIFtveXVuY3VsYXIgb3l1bmN1XSAgICAgICAgICA7OyBpa2kgb3l1bmN1CmJyZWVkIFt0b3BsYXIgdG9wXSAgICAgICAgICAgICAgICA7OyBiaXIgdG9wCnRvcGxhci1vd25baGl6IGNhcnBtYS1tZXNhZmVzaV0gICA7OyB0b3B1biBoaXppIHZlIGNhcnBtYS1tZXNhZmVzaSBnaWJpIG96ZWxsaWtsZXJpIHZhcgoKCnRvIHNldHVwCiAgY2EKICBjcmVhdGUtb3l1bmN1bGFyIDIgWwogICAgc2V0IHNoYXBlICJmYWNlIGhhcHB5IiAgICAgICAgOzsgYmFzbGFuZ2ljdGEgaGVya2VzIG11dGx1CiAgICBzZXQgc2l6ZSAzCiAgICBzZXQgY29sb3IgYmx1ZQogICAgc2VzCiAgXQogIGNyZWF0ZS10b3BsYXIgMSBbCiAgICBzZXQgc2hhcGUgImRvdCIKICAgIHNldCBjb2xvciByZWQKICAgIHNldCBzaXplIDIKICAgIHNldCBoZWFkaW5nICgtIDEzNSkgICAgICAgICAgIDs7IHRvcHVuIHlvbnUKICAgIHNldCBoaXogMC4wMDAwNSAgICAgICAgICAgICAgIDs7IHRvcHVuIGhpemkKICAgIHNldCBjYXJwbWEtbWVzYWZlc2kgMiAgICAgICAgIDs7IHRvcHVuIG1lc2FmZXNpCiAgXQogIGFzayBveXVuY3UgMCBbc2V0eHkgLTIwIDBdICAgICAgOzsgb3l1bmN1IDBpbiBrb251bXUKICBhc2sgb3l1bmN1IDEgW3NldHh5IDIwIDBdICAgICAgIDs7IG95dW5jdSAxaW4ga29udW11CiAgYXNrIHBhdGNoZXMgd2l0aCBbcHhjb3IgPSBbeGNvcl0gb2Ygb3l1bmN1IDAgb3IgcHhjb3IgPSBbeGNvcl0gb2Ygb3l1bmN1IDFdIFtzZXQgcGNvbG9yIHdoaXRlXQogIDs7IG95dW5jdWxhcmluIG9sZHVndSB5ZXJkZSBkaWtleSBiZXlheiBjaXpnaQplbmQKCgp0byBnbwogIG95bmEgICAgICAgICAgICAgICAgICAgICAgICAgICA7OyB0b3AgaGFyZWtldCBlZGl5b3IKICBjYXJwbWEta29udHJvbCAgICAgICAgICAgICAgICAgOzsgdG9wIGJpciB5ZXJlIGNhcnB0aSBtaT8ga29udHJvbCBldC4KICBpZiAoa2F6YW4gPSB0cnVlKSBbICAgICAgICAgICAgOzsgT3l1bmN1bGFyZGFuIGJpcmkga2F6YW5kaXlzYSBzZXMgY2lrYXIKICAgIHNlcyAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDs7IHNlcyBjaWthcgogICAgd2FpdCAyCiAgICBzZXMKICAgIHJlc2V0LW95dW5jdWxhcgogICAgYXNrIHRvcCAyIFsKICAgICAgc2V0eHkgMCAwICAgICAgICAgICAgICAgICAgICAgIDs7IHRvcHUgb3J0YXlhIGFsCiAgICAgIHNldCBoZWFkaW5nIHJhbmRvbSAzNjAgICAgICAgICA7OyBydGVzdGdlbGUgeW9uIGF0YQogICAgXQogIF0KZW5kCgoKCjs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7OyBLaW0ga2F6YW5kaQp0by1yZXBvcnQga2F6YW4KICBpZiggW3hjb3JdIG9mIHRvcCAyIDwgW3hjb3JdIG9mIG95dW5jdSAwKVsKICAgIDs7YXNrIHRvcCAyIFtzZXQgaGl6IDBdCiAgICBhc2sgb3l1bmN1IDAgWwogICAgICBzZXQgc2hhcGUgImZhY2Ugc2FkIgogICAgICBzZXQgbGFiZWwgImtheWJldHRpbiIKICAgICAgc2V0IGNvbG9yIHZpb2xldAogICAgXQogICAgcmVwb3J0IHRydWUKICBdCiAgaWYoIFt4Y29yXSBvZiB0b3AgMiA+IFt4Y29yXSBvZiBveXVuY3UgMSlbCiAgICA7O2FzayB0b3AgMiBbc2V0IGhpeiAwXQogICAgYXNrIG95dW5jdSAxIFsKICAgICAgc2V0IHNoYXBlICJmYWNlIHNhZCIKICAgICAgc2V0IGxhYmVsICJrYXliZXR0aW4iCiAgICAgIHNldCBjb2xvciB2aW9sZXQKICAgIF0KICAgIHJlcG9ydCB0cnVlCiAgXQogIHJlcG9ydCBmYWxzZQplbmQKCgp0byByZXNldC1veXVuY3VsYXIKICBhc2sgb3l1bmN1bGFyIFsKICAgIHNldCBzaGFwZSAiZmFjZSBoYXBweSIgICAgICAgIDs7IGJhc2xhbmdpY3RhIGhlcmtlcyBtdXRsdQogICAgc2V0IGxhYmVsICIiCiAgICBzZXQgY29sb3IgYmx1ZQogIF0KZW5kCgoKOzs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7IFRvcCBIYXJla2V0aQp0byBveW5hCiAgYXNrIHRvcCAyIFtmZCBoaXpdCmVuZAoKdG8gY2FycG1hLWtvbnRyb2wKICBjYXJwbWEtb3l1bmN1MAogIGNhcnBtYS15YXRheS1kdXZhcgogIGNhcnBtYS1kaWtleS1kdXZhcgplbmQKCnRvIGNhcnBtYS1veXVuY3UwCiAgYXNrIHRvcCAyIFsKICAgIGlmIChkaXN0YW5jZSBveXVuY3UgMCA8IGNhcnBtYS1tZXNhZmVzaSkgWyAgICAgOzsgdG9wdW4gb3l1bmN1IDBhIG1lc2FmZXNpIDJkZW4gYXogaXNlLAogICAgICBzaG93ICJveXVuY3UwYSBmYXpsYSB5YWtpbiIKICAgICAgc2V0IGhlYWRpbmcgKCAzNjAgLSBoZWFkaW5nKSAgIDs7IHRvcHVuIGdlcmkgeWFuc2lyCgogICAgICB3aGlsZSBbZGlzdGFuY2Ugb3l1bmN1IDAgPCBjYXJwbWEtbWVzYWZlc2ldW2ZkIGhpel0KICAgIF0KICBdCmVuZAoKdG8gY2FycG1hLXlhdGF5LWR1dmFyCiAgbGV0IHkgW3ljb3JdIG9mIHRvcCAyCiAgYXNrIHRvcCAyIFsKICAgIGlmIChhYnMoeSkgPiAoYWJzKG1pbi1weWNvcikgLSAwLjEpKSBbICAgICA7OyB0b3B1biBveXVuY3UgMGEgbWVzYWZlc2kgMmRlbiBheiBpc2UsCiAgICAgIHNob3cgInlhdGF5IGR1dmFyYSBmYXpsYSB5YWtpbiIKICAgICAgc2V0IGhlYWRpbmcgKCAxODAgLSBoZWFkaW5nKSAgIDs7IHRvcHVuIGdlcmkgeWFuc2lyCiAgICBdCiAgXQplbmQKCnRvIGNhcnBtYS1kaWtleS1kdXZhcgogIGxldCB4IFt4Y29yXSBvZiB0b3AgMgogIGFzayB0b3AgMiBbCiAgICBpZiAoYWJzKHgpID4gKGFicyhtaW4tcHhjb3IpIC0gMC4xKSkgWyAgICAgOzsgdG9wdW4gb3l1bmN1IDBhIG1lc2FmZXNpIDJkZW4gYXogaXNlLAogICAgICBzaG93ICJkaWtleSBkdXZhcmEgZmF6bGEgeWFraW4iCiAgICAgIHNldCBoZWFkaW5nICggMzYwIC0gaGVhZGluZykgICA7OyB0b3B1biBnZXJpIHlhbnNpcgogICAgXQogIF0KZW5kCgo7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7OzsgT3l1bmN1IEtvbnRyb2wKdG8geXVrYXJpCiAgbGV0IHkgW3ljb3JdIG9mIG95dW5jdSAwCiAgbGV0IHggW3hjb3JdIG9mIG95dW5jdSAwCiAgYXNrIG95dW5jdSAwIFsKICAgIGlmKGFicyh5ICsgMSkgPCBhYnMobWluLXB5Y29yKSkgW3NldHh5IHggKHkgKyAxKV0KICBdCmVuZAoKdG8gYXNhZ2kKICBsZXQgeSBbeWNvcl0gb2Ygb3l1bmN1IDAKICBsZXQgeCBbeGNvcl0gb2Ygb3l1bmN1IDAKICBhc2sgb3l1bmN1IDAgWwogICAgaWYoYWJzKHkgLSAxKSA8IGFicyhtaW4tcHljb3IpKSBbc2V0eHkgeCAoeSAtIDEpXQogIF0KZW5kCgo7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7Ozs7OzsgVG9wIEhhcmVrZXRpCnRvIHNlcwogIHNvdW5kOnBsYXktZHJ1bSAiQUNPVVNUSUMgU05BUkUiIDY0CmVuZApgYGAKCgojIFB5dGhvbiBpbGUgUHJvZ3JhbWxhbWF5YSBHaXJpcwpOZXRsb2dvIHZlIFIgZGlsbGVyaW5kZSBkYWhhIMO2bmNlIGfDtnJkw7zEn8O8bcO8eiwgdmVyaSB0aXBsZXJpLCBmb25rc2l5b25sYXIsIGtvbnRyb2wgeWFwxLFsYXLEsSB2ZSBkw7ZuZMO8bGVyIHB5dGjEsW4gZGlsaW5pbiBkZSB0ZW1lbGxlcmluaSBvbHXFn3R1cnVyLgpgYGB7cHl0aG9ufQojIExpc3RlCkwgPSBbMSwgWzEsMl0sIDNdCnByaW50KEwpCnByaW50KExbMF0pCnByaW50KExbMV0pCiMgTGlzdGVuaW4gdXp1bmx1Z3UKcHJpbnQobGVuKEwpKQpgYGAKCmBgYHtweXRob259CmEsIGIgPSAxLCA4CmEsIGIgPSBiLCBhCnByaW50KGEsIiAiLGIpCmBgYApgYGB7cHl0aG9ufQojIEZvbmtzaXlvbgpkZWYgZGVnaXMoYSxiKToKICAgIGEsIGIgPSBiLCBhCiAgICByZXR1cm4gYSwgYgoKeCwgeSA9IDMsIDQKcHJpbnQoIngsIHkgPSAiLCBkZWdpcyh4LHkpKQpgYGAKCmBgYHtweXRob259CngsIHkgPSAzLCA0CiMgS29udG9sCmlmKHggPiB5KToKICAgIHByaW50KHgsICIsIiwgeSwgImRlbiBidXl1ayIpCmVsc2U6CiAgICBwcmludCh5LCAiLCIsIHgsICJkZW4gYnV5dWsiKQpgYGAKCmBgYHtweXRob259CmRlZiBrYXRlZ29yaSh5YXMpOgogICAgaWYgeWFzPD0xODoKICAgICAgICBkdXJ1bT0iY29jdWsiCiAgICBlbGlmIHlhcz42NToKICAgICAgICBkdXJ1bT0iZW1la2xpIgogICAgZWxzZToKICAgICAgICBkdXJ1bT0ibm9ybWFsIgogICAgcmV0dXJuIGR1cnVtCgpwcmludChrYXRlZ29yaSgxNSkpCmBgYAoKCmBgYHtweXRob259ClNheSA9IFsxLDIsMyw0LDUsNiw3XQpmb3IgaSBpbiBTYXk6ICAKICAgIHByaW50KGkqKjIpICAgCmBgYAoKYGBge3B5dGhvbn0KIyByYW5nZShbYmFzLF0gc29uIFssYWRpbV0pIDogYmFzIHZhcnNheWlsYW4gZGVnZXJpIDAsIGFkaW0gdmFyc2F5aWxhbiBkZWdlcmkgMQpmb3IgaSBpbiByYW5nZSg0LDEwLDIpOgogICAgcHJpbnQoaSkKYGBgCgpgYGB7cHl0aG9ufQojIFNvemx1a2xlcgpEQiA9IHsKICAgICJ1emF5IiA6IHsiU3RhciBXYXJzIjogNC41LCAiU3VwZXJtYW4iOiAzLjUsIkJhdG1hbiI6IDQsfSwKICAgICJzZWxpbiIgOiB7IlZlbmVkaWsiOiA0LjUsICJQYXJpcyI6IDMuNSwiQmF0bWFuIjogNCx9LAogICAgImZhdGloIiA6IHsiU3VwZXJtYW4iOiA0LCJCYXRtYW4iOiA0fSwKfQpwcmludCgiXG5VemF5IEJlZ2VuaWxlcmk6ICIsIERCWyd1emF5J10pCnByaW50KCJVemF5aW4gU3RhciBXYXJzIGZpbG1pbmUgdmVyZGlnaSBwdWFuOiAiLCBEQlsndXpheSddWydTdGFyIFdhcnMnXSkKYGBgCgpgYGB7cHl0aG9ufQojIFNvemx1a2xlcgpEQiA9IHsKICAgICJ1emF5IiA6IHsiU3RhciBXYXJzIjogNC41LCAiU3VwZXJtYW4iOiAzLjUsIkJhdG1hbiI6IDQsfSwKICAgICJzZWxpbiIgOiB7IlZlbmVkaWsiOiA0LjUsICJQYXJpcyI6IDMuNSwiQmF0bWFuIjogNCx9LAogICAgImZhdGloIiA6IHsiU3VwZXJtYW4iOiA0LCJCYXRtYW4iOiA0fSwKfQojIFllbmkgZGVnZXIgZWtsZW1lCkRCLnNldGRlZmF1bHQoIlVtdXQiLCB7Ik1heW11bmxhciBDZWhlbm5lbWkiOiA0LCAiQmFiYW0gdmUgT2dsdW0iOiAzfSkKcHJpbnQoREIpCnByaW50KCJcblxuIikKZm9yIGsgaW4gREIua2V5cygpOiAgCiAgICBwcmludChrKSAgCmBgYAoKCgoKCmBgYHtweXRob259CiMgU296bHVrbGVyCkRCID0gewogICAgInV6YXkiIDogeyJTdGFyIFdhcnMiOiA0LjUsICJTdXBlcm1hbiI6IDMuNSwiQmF0bWFuIjogNCx9LAogICAgInNlbGluIiA6IHsiVmVuZWRpayI6IDQuNSwgIlBhcmlzIjogMy41LCJCYXRtYW4iOiA0LH0sCiAgICAiZmF0aWgiIDogeyJTdXBlcm1hbiI6IDQsIkJhdG1hbiI6IDR9LAp9CiMgWWVuaSBkZWdlciBla2xlbWUKREIuc2V0ZGVmYXVsdCgiVW11dCIsIHsiTWF5bXVubGFyIENlaGVubmVtaSI6IDQsICJCYWJhbSB2ZSBPZ2x1bSI6IDN9KQoKZm9yIGRlZ2VyIGluIERCLnZhbHVlcygpOiAgCiAgICBwcmludChkZWdlcikKYGBgCgpgYGB7cHl0aG9ufQojIElsZXJpIExpc3RlIElzbGVtbGVyCnByaW50KFt4KjUgZm9yIHggaW4gcmFuZ2UoNSldKQpwcmludChbeCBmb3IgeCBpbiByYW5nZSg1KSBpZiB4JTIgPT0gMF0pCmBgYAoKYGBge3B5dGhvbn0KaW1wb3J0IG51bXB5IGFzIG5wCmxpc3RlID0gbnAuYXJyYXkocmFuZ2UoNSkpCnByaW50KGxpc3RlKQpgYGAKCgpgYGB7cHl0aG9ufQppbXBvcnQgbnVtcHkgYXMgbnAKbGlzdGUgPSBucC5hcnJheShyYW5nZSg1KSkKbGlzdGUgPSBsaXN0ZSAqIGxpc3RlCnByaW50KGxpc3RlKQoKaW1wb3J0IG1hdGgKZm9yIGkgaW4gbGlzdGU6CiAgICBwcmludChtYXRoLnNxcnQoaSkpCmBgYAoKCmBgYHtweXRob259CmltcG9ydCBudW1weSBhcyBucApsaXN0ZSA9IG5wLmFycmF5KFswLCAxLCAgNCwgIDksIDE2XSkKcHJpbnQobGVuKGxpc3RlKSkKcHJpbnQoImxpc3RlW2xpc3RlID4gNV06ICIsIGxpc3RlW2xpc3RlID4gNV0pCgpsaXN0ZSA9IG5wLmFwcGVuZChsaXN0ZSwgWzI1LDM2LDQ5XSkKcHJpbnQobGlzdGUpCgpsaXN0ZSA9IGxpc3RlIC0gMTYKbGlzdGVbbGlzdGU+MF0gPSAxCmxpc3RlW2xpc3RlPDBdID0gLTEKcHJpbnQobGlzdGUpCgpsaXN0ZTIgPSBucC56ZXJvcyg4KQpsaXN0ZTJbNTpdID0gLTEKcHJpbnQobGlzdGUyKQpwcmludChsaXN0ZSArIGxpc3RlMikKYGBgCgoKCkRhaGEgZmF6bGFzaSBpY2luIHB5dGhvbiB2ZSBudW1weSBrb2RsYXJpOiBodHRwczovL3MzLmFtYXpvbmF3cy5jb20vYXNzZXRzLmRhdGFjYW1wLmNvbS9ibG9nX2Fzc2V0cy9OdW1weV9QeXRob25fQ2hlYXRfU2hlZXQucGRmCgoKCgoKCgoKCg==