Implementing a 1D convnet
W pakiecie Keras jednowymiarowe sieci konwolucyjne zostały zaimplementowane w postaci warstwy layer_conv_1d, której interfejs działa podobnie do interfejsu warstwy layer_conv_2d. Na wejściu warstwa ta przyjmuje trójwymiarowe tensory o kształcie (próbki, czas, cechy) i zwraca trójwymiarowe tensory o takim samym kształcie. Okno konwolucyjne jest jednowymiarowym oknem poruszającym się wzdłuż osi czasu (drugiej osi tensora wejściowego).
Zbudujmy prostą jednowymiarową sieć konwolucyjną i spróbujmy użyć jej do analizy sentymentu recenzji wchodzących w skład zbioru IMDB. Przypominam kod importujący i przetwarzający wstępnie dane tego zbioru:
r
r library(keras) max_features <- 10000 max_len <- 500 cat(data…)
Loading data...
r
r imdb <- dataset_imdb(num_words = max_features)
Using TensorFlow backend.
2017-11-23 11:43:44.246774: I tensorflow/core/platform/cpu_feature_guard.cc:137] Your CPU supports instructions that this TensorFlow binary was not compiled to use: SSE4.1 SSE4.2 AVX AVX2 FMA
2017-11-23 11:43:46.912966: I tensorflow/stream_executor/cuda/cuda_gpu_executor.cc:892] successful NUMA node read from SysFS had negative value (-1), but there must be at least one NUMA node, so returning NUMA node zero
2017-11-23 11:43:46.913301: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1030] Found device 0 with properties:
name: Tesla K80 major: 3 minor: 7 memoryClockRate(GHz): 0.8235
pciBusID: 0000:00:1e.0
totalMemory: 11.17GiB freeMemory: 11.10GiB
2017-11-23 11:43:46.913327: I tensorflow/core/common_runtime/gpu/gpu_device.cc:1120] Creating TensorFlow device (/device:GPU:0) -> (device: 0, name: Tesla K80, pci bus id: 0000:00:1e.0, compute capability: 3.7)
r
r c(c(x_train, y_train), c(x_test, y_test)) %<-% imdb cat(length(x_train), sequences)
25000 train sequences
r
r cat(length(x_test), sequences)
25000 test sequences
r
r cat(sequences (samples x time))
Pad sequences (samples x time)
r
r x_train <- pad_sequences(x_train, maxlen = max_len) x_test <- pad_sequences(x_test, maxlen = max_len) cat(_train shape:, dim(x_train), \n)
x_train shape: 25000 500
r
r cat(_test shape:, dim(x_test), \n)
x_test shape: 25000 500
Jednowymiarowe sieci konwolucyjne mają taką samą strukturę jak ich dwuwymiarowe odpowiedniki, z których korzystaliśmy w rozdziale 5.: składają się ze stosu warstw layer_conv_1d i layer_max_pooling_1d, a na ich końcu znajduje się globalna warstwa łącząca lub warstwa spłaszczająca (layer_flatten) zamieniająca trójwymiarowe obiekty wyjściowe w obiekty dwuwymiarowe, co pozwala na dodanie do modelu klasyfikacji lub regresji przynajmniej jednej warstwy dense.
Jedną z różnic między tymi typami sieci jest to, że w przypadku jednowymiarowych sieci konwolucyjnych możemy pozwolić sobie na użycie większych okien konwolucji. W przypadku dwuwymiarowej warstwy konwolucji okno konwolucji o wymiarach 33 zawiera 3 3 = 9 wektorów cech, a w przypadku warstwy jednowymiarowej konwolucji okno konwolucji o rozmiarze równym 3 składa się tylko z 3 wektorów cech. W związku z tym możemy swobodnie pozwolić sobie na korzystanie z jednowymiarowych okien konwolucji o rozmiarze równym 7 lub 9.
Oto przykładowa jednowymiarowa sieć konwolucyjna przetwarzająca zbiór danych IMDB.
r
r model <- keras_model_sequential() %>% layer_embedding(input_dim = max_features, output_dim = 128, input_length = max_len) %>% layer_conv_1d(filters = 32, kernel_size = 7, activation = ) %>% layer_max_pooling_1d(pool_size = 5) %>% layer_conv_1d(filters = 32, kernel_size = 7, activation = ) %>% layer_global_max_pooling_1d() %>% layer_dense(units = 1) summary(model)
_______________________________________________________________________________________
Layer (type) Output Shape Param #
=======================================================================================
embedding_1 (Embedding) (None, 500, 128) 1280000
_______________________________________________________________________________________
conv1d_1 (Conv1D) (None, 494, 32) 28704
_______________________________________________________________________________________
max_pooling1d_1 (MaxPooling1D) (None, 98, 32) 0
_______________________________________________________________________________________
conv1d_2 (Conv1D) (None, 92, 32) 7200
_______________________________________________________________________________________
global_max_pooling1d_1 (GlobalMaxPooli (None, 32) 0
_______________________________________________________________________________________
dense_1 (Dense) (None, 1) 33
=======================================================================================
Total params: 1,315,937
Trainable params: 1,315,937
Non-trainable params: 0
_______________________________________________________________________________________
Oto wyniki procesu trenowania i walidacji modelu. Dokładność walidacji jest nieco mniejsza od tej, którą uzyskał model sieci layer_lstm, ale trenowanie bieżącego modelu trwało znacznie szybciej (dotyczy to pracy na układzie CPU, a także układzie GPU). Oczywiście dokładny przyrost prędkości wykonywania obliczeń zależy od konfiguracji sprzętowej. Możemy zapisać ten model, ograniczając czas jego wykonywania do ośmiu epok, a następnie sprawdzić jego działanie na zbiorze testowym. To z pewnością przekonujący dowód na to, że jednowymiarowa sieć konwolucyjna jest szybszą i tańszą alternatywą stosowania sieci rekurencyjnej w przypadku problemu analizy sentymentu na poziomie słów.
r
r plot(history)

Łączenie sieci konwolucyjnych i rekurencyjnych w celu przetworzenia długich sekwencji
Jednowymiarowe sieci konwolucyjne przetwarzają sekwencje wejściowe w sposób niezależny. W przeciwieństwie do sieci rekurencyjnych nie są wrażliwe na kolejność obserwacji (poza skalą lokalną określaną przez rozmiar okna konwolucji). Oczywiście w celu rozpoznania bardziej rozciągniętych prawidłowości możemy utworzyć stos wielu warstw konwolucyjnych i warstw łączących. W ten sposób górne warstwy będą analizować dłuższe fragmenty danych wejściowych, ale jest to słaby sposób na wprowadzenie wrażliwości modelu na kolejność obserwacji. Sprawdźmy w praktyce tę słabość modelu podczas prognozowania temperatury (w tym problemie kolejność jest bardzo ważna dla otrzymania prawidłowych prognoz). W poniższym przykładzie korzystamy ponownie ze zdefiniowanych wcześniej zmiennych float_data, train_gen, val_gen i val_steps:
r
r library(tibble) library(readr) data_dir <- ~/Downloads/jena_climate
fname <- file.path(data_dir, _climate_2009_2016.csv) data <- read_csv(fname) data <- data.matrix(data[,-1]) train_data <- data[1:200000,] mean <- apply(train_data, 2, mean) std <- apply(train_data, 2, sd) data <- scale(data, center = mean, scale = std) generator <- function(data, lookback, delay, min_index, max_index, shuffle = FALSE, batch_size = 128, step = 6) { if (is.null(max_index)) max_index <- nrow(data) - delay - 1 i <- min_index + lookback function() { if (shuffle) { rows <- sample(c((min_index+lookback):max_index), size = batch_size) } else { if (i + batch_size >= max_index) i <<- min_index + lookback rows <- c(i:min(i+batch_size, max_index)) i <<- i + length(rows) }
samples <- array(0, dim = c(length(rows),
lookback / step,
dim(data)[[-1]]))
targets <- array(0, dim = c(length(rows)))
for (j in 1:length(rows)) {
indices <- seq(rows[[j]] - lookback, rows[[j]],
length.out = dim(samples)[[2]])
samples[j,,] <- data[indices,]
targets[[j]] <- data[rows[[j]] + delay,2]
}
list(samples, targets)
} } lookback <- 1440 step <- 6 delay <- 144 batch_size <- 128 train_gen <- generator( data, lookback = lookback, delay = delay, min_index = 1, max_index = 200000, shuffle = TRUE, step = step, batch_size = batch_size ) val_gen = generator( data, lookback = lookback, delay = delay, min_index = 200001, max_index = 300000, step = step, batch_size = batch_size ) test_gen <- generator( data, lookback = lookback, delay = delay, min_index = 300001, max_index = NULL, step = step, batch_size = batch_size ) # This is how many steps to draw from val_gen
# in order to see the whole validation set: val_steps <- (300000 - 200001 - lookback) / batch_size # This is how many steps to draw from test_gen
# in order to see the whole test set: test_steps <- (nrow(data) - 300001 - lookback) / batch_size
r
r model <- keras_model_sequential() %>% layer_conv_1d(filters = 32, kernel_size = 5, activation = , input_shape = list(NULL, dim(data)[[-1]])) %>% layer_max_pooling_1d(pool_size = 3) %>% layer_conv_1d(filters = 32, kernel_size = 5, activation = ) %>% layer_max_pooling_1d(pool_size = 3) %>% layer_conv_1d(filters = 32, kernel_size = 5, activation = ) %>% layer_global_max_pooling_1d() %>% layer_dense(units = 1) model %>% compile( optimizer = optimizer_rmsprop(), loss =
) history <- model %>% fit_generator( train_gen, steps_per_epoch = 500, epochs = 20, validation_data = val_gen, validation_steps = val_steps )
Oto wykres średniego bezwzględnego błędu trenowania i walidacji.
r
r plot(history)

Średni bezwzględny błąd walidacji utrzymuje się na poziomie około 40%, a więc model ten nie jest w stanie pokonać nawet zdefiniowanego wcześniej punktu odniesienia. Dzieje się tak, ponieważ sieć konwolucyjna poszukuje zależności w całych danych szeregu czasowego bez wiedzy o tym, w jakim czasie zaobserwowano przetwarzane wartości (nie zwraca uwagi na to, czy są one zbliżone bardziej do początku, czy do końca analizowanego zbioru). W tym problemie nowsze dane powinny być interpretowane w inny sposób od danych z dalszej przeszłości, a więc sieć konwolucyjna nie jest w stanie wygenerować sensownych wyników. To ograniczenie sieci konwolucyjnych nie jest problematyczne w przypadku zbioru IMDB, ponieważ słowa świadczące o tym, że dana recenzja jest pochlebna lub negatywna, mogą znajdować się w dowolnym miejscu analizowanych zdań.
Sposobem na połączenie szybkości i lekkości sieci konwolucyjnych z braniem pod uwagę kolejności przez sieci rekurencyjne jest zastosowanie jednowymiarowej sieci konwolucyjnej w roli mechanizmu przetwarzającego wstępnie dane kierowane do sieci rekurencyjnej (patrz rysunek 6.25). Rozwiązanie takie sprawdza się szczególnie dobrze podczas pracy z długimi sekwencjami, których długość uniemożliwia ich sensowne przetworzenie za pomocą samych sieci rekurencyjnych (piszę tu o sekwencjach składających się nawet z tysięcy kroków). Sieć konwolucyjna zamieni długą sekwencję wejściową w krótsze sekwencje cech wyższego poziomu, które można następnie skierować do warstwy rekurencyjnej.
Technika ta jest na tyle mało znana, że rzadko spotyka się ją w artykułach naukowych i praktycznych zastosowaniach. Jest jednak na tyle skuteczna, że powinna być bardziej popularna. Spróbujmy użyć jej w celu rozwiązania problemu prognozowania temperatury. Rozwiązanie to pozwala na przetwarzanie o wiele dłuższych sekwencji, a więc możemy przyglądać się danym z dalszej przeszłości poprzez zwiększenie wartości parametru lookback generatora danych lub przyglądać się szeregom czasowym o wyższej rozdzielczości poprzez zmniejszenie wartości parametru step generatora danych. W zaprezentowanym przykładzie zdecydowałem się na zmniejszenie o połowę parametru step, co wydłużyło dwukrotnie analizowane szeregi czasowe (pracujemy z próbkami temperatury odczytywanej w odstępie 30 minut). Ponownie korzystam ze zdefiniowanej wcześniej funkcji generator.
r
r # This was previously set to 6 (one point per hour). # Now 3 (one point per 30 min). step <- 3 lookback <- 720 # Unchanged delay <- 144 # Unchanged
train_gen <- generator( data, lookback = lookback, delay = delay, min_index = 1, max_index = 200000, shuffle = TRUE, step = step ) val_gen <- generator( data, lookback = lookback, delay = delay, min_index = 200001, max_index = 300000, step = step ) test_gen <- generator( data, lookback = lookback, delay = delay, min_index = 300001, max_index = NULL, step = step ) val_steps <- (300000 - 200001 - lookback) / 128 test_steps <- (nrow(data) - 300001 - lookback) / 128
Teraz możemy stworzyć model. Połączymy dwie warstwy layer_conv_1d z warstwą layer_gru.
r
r model <- keras_model_sequential() %>% layer_conv_1d(filters = 32, kernel_size = 5, activation = , input_shape = list(NULL, dim(data)[[-1]])) %>% layer_max_pooling_1d(pool_size = 3) %>% layer_conv_1d(filters = 32, kernel_size = 5, activation = ) %>% layer_gru(units = 32, dropout = 0.1, recurrent_dropout = 0.5) %>% layer_dense(units = 1) summary(model)
_______________________________________________________________________________________
Layer (type) Output Shape Param #
=======================================================================================
conv1d_6 (Conv1D) (None, None, 32) 2272
_______________________________________________________________________________________
max_pooling1d_4 (MaxPooling1D) (None, None, 32) 0
_______________________________________________________________________________________
conv1d_7 (Conv1D) (None, None, 32) 5152
_______________________________________________________________________________________
gru_1 (GRU) (None, 32) 6240
_______________________________________________________________________________________
dense_3 (Dense) (None, 1) 33
=======================================================================================
Total params: 13,697
Trainable params: 13,697
Non-trainable params: 0
_______________________________________________________________________________________
r
r model %>% compile( optimizer = optimizer_rmsprop(), loss =
) history <- model %>% fit_generator( train_gen, steps_per_epoch = 500, epochs = 20, validation_data = val_gen, validation_steps = val_steps )
r
r plot(history)

Przyglądając się wykresowi straty walidacyjnej, możemy stwierdzić, że taka konfiguracja modelu jest słabsza od samej warstwy layer_gru poddanej regularyzacji, ale działa znacznie szybciej. Analizuje dwa razy więcej danych, co w tym przypadku nie jest zabiegiem szczególnie przydatnym, ale w innych zbiorach danych może przynieść znaczną poprawę pracy algorytmu.
LS0tDQp0aXRsZTogIktvbndvbHVjeWpuZSBzaWVjaSBuZXVyb25vd2UgaSBwcnpldHdhcnphbmllIHNla3dlbmNqaSINCm91dHB1dDogDQogIGh0bWxfbm90ZWJvb2s6IA0KICAgIHRoZW1lOiBjZXJ1bGVhbg0KICAgIGhpZ2hsaWdodDogdGV4dG1hdGUNCi0tLQ0KDQpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0NCmtuaXRyOjpvcHRzX2NodW5rJHNldCh3YXJuaW5nID0gRkFMU0UsIG1lc3NhZ2UgPSBGQUxTRSkNCmBgYA0KDQoNCg0KIyMgSW1wbGVtZW50aW5nIGEgMUQgY29udm5ldA0KICANClcgcGFraWVjaWUgS2VyYXMgamVkbm93eW1pYXJvd2Ugc2llY2kga29ud29sdWN5am5lIHpvc3RhxYJ5IHphaW1wbGVtZW50b3dhbmUgdyBwb3N0YWNpIHdhcnN0d3kgbGF5ZXJfY29udl8xZCwga3TDs3JlaiBpbnRlcmZlanMgZHppYcWCYSBwb2RvYm5pZSBkbyBpbnRlcmZlanN1IHdhcnN0d3kgbGF5ZXJfY29udl8yZC4gTmEgd2VqxZtjaXUgd2Fyc3R3YSB0YSBwcnp5am11amUgdHLDs2p3eW1pYXJvd2UgdGVuc29yeSBvIGtzenRhxYJjaWUgKHByw7Nia2ksIGN6YXMsIGNlY2h5KSBpIHp3cmFjYSB0csOzand5bWlhcm93ZSB0ZW5zb3J5IG8gdGFraW0gc2FteW0ga3N6dGHFgmNpZS4gT2tubyBrb253b2x1Y3lqbmUgamVzdCBqZWRub3d5bWlhcm93eW0gb2tuZW0gcG9ydXN6YWrEhWN5bSBzacSZIHd6ZMWCdcW8IG9zaSBjemFzdSAoZHJ1Z2llaiBvc2kgdGVuc29yYSB3ZWrFm2Npb3dlZ28pLg0KDQpaYnVkdWpteSBwcm9zdMSFIGplZG5vd3ltaWFyb3fEhSBzaWXEhyBrb253b2x1Y3lqbsSFIGkgc3Byw7NidWpteSB1xbx5xIcgamVqIGRvIGFuYWxpenkgc2VudHltZW50dSByZWNlbnpqaSB3Y2hvZHrEhWN5Y2ggdyBza8WCYWQgemJpb3J1IElNREIuIFByenlwb21pbmFtIGtvZCBpbXBvcnR1asSFY3kgaSBwcnpldHdhcnphasSFY3kgd3N0xJlwbmllIGRhbmUgdGVnbyB6YmlvcnU6DQoNCg0KYGBge3J9DQpsaWJyYXJ5KGtlcmFzKQ0KDQptYXhfZmVhdHVyZXMgPC0gMTAwMDANCm1heF9sZW4gPC0gNTAwDQoNCmNhdCgixYFhZG93YW5pZSBkYW55Y2guLi5cbiIpDQppbWRiIDwtIGRhdGFzZXRfaW1kYihudW1fd29yZHMgPSBtYXhfZmVhdHVyZXMpDQpjKGMoeF90cmFpbiwgeV90cmFpbiksIGMoeF90ZXN0LCB5X3Rlc3QpKSAlPC0lIGltZGIgDQpjYXQobGVuZ3RoKHhfdHJhaW4pLCAic2Vrd2VuY2plIHRyZW5pbmdvd2VcbiIpDQpjYXQobGVuZ3RoKHhfdGVzdCksICJzZWt3ZW5jamUgdGVzdG93ZSIpDQoNCmNhdCgiU2Vrd2VuY2plIChwcsOzYmtpIHggY3phcylcbiIpDQp4X3RyYWluIDwtIHBhZF9zZXF1ZW5jZXMoeF90cmFpbiwgbWF4bGVuID0gbWF4X2xlbikNCnhfdGVzdCA8LSBwYWRfc2VxdWVuY2VzKHhfdGVzdCwgbWF4bGVuID0gbWF4X2xlbikNCmNhdCgiS3N6dGHFgnQgb2JpZWt0dSB4X3RyYWluOiIsIGRpbSh4X3RyYWluKSwgIlxuIikNCmNhdCgiS3N6dGHFgnQgb2JpZWt0dSB4X3Rlc3Q6IiwgZGltKHhfdGVzdCksICJcbiIpDQpgYGANCg0KSmVkbm93eW1pYXJvd2Ugc2llY2kga29ud29sdWN5am5lIG1hasSFIHRha8SFIHNhbcSFIHN0cnVrdHVyxJkgamFrIGljaCBkd3V3eW1pYXJvd2Ugb2Rwb3dpZWRuaWtpLCB6IGt0w7NyeWNoIGtvcnp5c3RhbGnFm215IHcgcm96ZHppYWxlIDUuOiBza8WCYWRhasSFIHNpxJkgemUgc3Rvc3Ugd2Fyc3R3IGxheWVyX2NvbnZfMWQgaSBsYXllcl9tYXhfcG9vbGluZ18xZCwgYSBuYSBpY2gga2/FhGN1IHpuYWpkdWplIHNpxJkgZ2xvYmFsbmEgd2Fyc3R3YSDFgsSFY3rEhWNhIGx1YiB3YXJzdHdhIHNwxYJhc3pjemFqxIVjYSAobGF5ZXJfZmxhdHRlbikgemFtaWVuaWFqxIVjYSB0csOzand5bWlhcm93ZSBvYmlla3R5IHd5asWbY2lvd2UgdyBvYmlla3R5IGR3dXd5bWlhcm93ZSwgY28gcG96d2FsYSBuYSBkb2RhbmllIGRvIG1vZGVsdSBrbGFzeWZpa2FjamkgbHViIHJlZ3Jlc2ppIHByenluYWptbmllaiBqZWRuZWogd2Fyc3R3eSBkZW5zZS4NCg0KSmVkbsSFIHogcsOzxbxuaWMgbWnEmWR6eSB0eW1pIHR5cGFtaSBzaWVjaSBqZXN0IHRvLCDFvGUgdyBwcnp5cGFka3UgamVkbm93eW1pYXJvd3ljaCBzaWVjaSBrb253b2x1Y3lqbnljaCBtb8W8ZW15IHBvendvbGnEhyBzb2JpZSBuYSB1xbx5Y2llIHdpxJlrc3p5Y2ggb2tpZW4ga29ud29sdWNqaS4gVyBwcnp5cGFka3UgZHd1d3ltaWFyb3dlaiB3YXJzdHd5IGtvbndvbHVjamkgb2tubyBrb253b2x1Y2ppIG8gd3ltaWFyYWNoIDPvgrQzIHphd2llcmEgMyDvgrQgMyA9IDkgd2VrdG9yw7N3IGNlY2gsIGEgdyBwcnp5cGFka3Ugd2Fyc3R3eSBqZWRub3d5bWlhcm93ZWoga29ud29sdWNqaSBva25vIGtvbndvbHVjamkgbyByb3ptaWFyemUgcsOzd255bSAzIHNrxYJhZGEgc2nEmSB0eWxrbyB6IDMgd2VrdG9yw7N3IGNlY2guIFcgendpxIV6a3UgeiB0eW0gbW/FvGVteSBzd29ib2RuaWUgcG96d29sacSHIHNvYmllIG5hIGtvcnp5c3RhbmllIHogamVkbm93eW1pYXJvd3ljaCBva2llbiBrb253b2x1Y2ppIG8gcm96bWlhcnplIHLDs3dueW0gNyBsdWIgOS4NCg0KT3RvIHByenlrxYJhZG93YSBqZWRub3d5bWlhcm93YSBzaWXEhyBrb253b2x1Y3lqbmEgcHJ6ZXR3YXJ6YWrEhWNhIHpiacOzciBkYW55Y2ggSU1EQi4NCg0KDQpgYGB7cn0NCm1vZGVsIDwtIGtlcmFzX21vZGVsX3NlcXVlbnRpYWwoKSAlPiUgDQogIGxheWVyX2VtYmVkZGluZyhpbnB1dF9kaW0gPSBtYXhfZmVhdHVyZXMsIG91dHB1dF9kaW0gPSAxMjgsDQogICAgICAgICAgICAgICAgICBpbnB1dF9sZW5ndGggPSBtYXhfbGVuKSAlPiUgDQogIGxheWVyX2NvbnZfMWQoZmlsdGVycyA9IDMyLCBrZXJuZWxfc2l6ZSA9IDcsIGFjdGl2YXRpb24gPSAicmVsdSIpICU+JSANCiAgbGF5ZXJfbWF4X3Bvb2xpbmdfMWQocG9vbF9zaXplID0gNSkgJT4lIA0KICBsYXllcl9jb252XzFkKGZpbHRlcnMgPSAzMiwga2VybmVsX3NpemUgPSA3LCBhY3RpdmF0aW9uID0gInJlbHUiKSAlPiUgDQogIGxheWVyX2dsb2JhbF9tYXhfcG9vbGluZ18xZCgpICU+JSANCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSAxKQ0KDQpzdW1tYXJ5KG1vZGVsKQ0KYGBgDQoNCmBgYHtyLCBlY2hvPUZBTFNFLCByZXN1bHRzPSdoaWRlJ30NCg0KbW9kZWwgJT4lIGNvbXBpbGUoDQogIG9wdGltaXplciA9IG9wdGltaXplcl9ybXNwcm9wKGxyID0gMWUtNCksDQogIGxvc3MgPSAiYmluYXJ5X2Nyb3NzZW50cm9weSIsDQogIG1ldHJpY3MgPSBjKCJhY2MiKQ0KKQ0KDQpoaXN0b3J5IDwtIG1vZGVsICU+JSBmaXQoDQogIHhfdHJhaW4sIHlfdHJhaW4sDQogIGVwb2NocyA9IDEwLA0KICBiYXRjaF9zaXplID0gMTI4LA0KICB2YWxpZGF0aW9uX3NwbGl0ID0gMC4yDQopDQpgYGANCg0KT3RvIHd5bmlraSBwcm9jZXN1IHRyZW5vd2FuaWEgaSB3YWxpZGFjamkgbW9kZWx1LiBEb2vFgmFkbm/Fm8SHIHdhbGlkYWNqaSBqZXN0IG5pZWNvIG1uaWVqc3phIG9kIHRlaiwga3TDs3LEhSB1enlza2HFgiBtb2RlbCBzaWVjaSBsYXllcl9sc3RtLCBhbGUgdHJlbm93YW5pZSBiaWXFvMSFY2VnbyBtb2RlbHUgdHJ3YcWCbyB6bmFjem5pZSBzenliY2llaiAoZG90eWN6eSB0byBwcmFjeSBuYSB1a8WCYWR6aWUgQ1BVLCBhIHRha8W8ZSB1a8WCYWR6aWUgR1BVKS4gT2N6eXdpxZtjaWUgZG9rxYJhZG55IHByenlyb3N0IHByxJlka2/Fm2NpIHd5a29ueXdhbmlhIG9ibGljemXFhCB6YWxlxbx5IG9kIGtvbmZpZ3VyYWNqaSBzcHJ6xJl0b3dlai4gTW/FvGVteSB6YXBpc2HEhyB0ZW4gbW9kZWwsIG9ncmFuaWN6YWrEhWMgY3phcyBqZWdvIHd5a29ueXdhbmlhIGRvIG/Fm21pdSBlcG9rLCBhIG5hc3TEmXBuaWUgc3ByYXdkemnEhyBqZWdvIGR6aWHFgmFuaWUgbmEgemJpb3J6ZSB0ZXN0b3d5bS4gVG8geiBwZXdub8WbY2nEhSBwcnpla29udWrEhWN5IGRvd8OzZCBuYSB0bywgxbxlIGplZG5vd3ltaWFyb3dhIHNpZcSHIGtvbndvbHVjeWpuYSBqZXN0IHN6eWJzesSFIGkgdGHFhHN6xIUgYWx0ZXJuYXR5d8SFIHN0b3Nvd2FuaWEgc2llY2kgcmVrdXJlbmN5am5laiB3IHByenlwYWRrdSBwcm9ibGVtdSBhbmFsaXp5IHNlbnR5bWVudHUgbmEgcG96aW9taWUgc8WCw7N3Lg0KDQpgYGB7cn0NCnBsb3QoaGlzdG9yeSkNCmBgYA0KDQojIyDFgcSFY3plbmllIHNpZWNpIGtvbndvbHVjeWpueWNoIGkgcmVrdXJlbmN5am55Y2ggdyBjZWx1IHByemV0d29yemVuaWEgZMWCdWdpY2ggc2Vrd2VuY2ppDQoNCg0KSmVkbm93eW1pYXJvd2Ugc2llY2kga29ud29sdWN5am5lIHByemV0d2FyemFqxIUgc2Vrd2VuY2plIHdlasWbY2lvd2UgdyBzcG9zw7NiIG5pZXphbGXFvG55LiBXIHByemVjaXdpZcWEc3R3aWUgZG8gc2llY2kgcmVrdXJlbmN5am55Y2ggbmllIHPEhSB3cmHFvGxpd2UgbmEga29sZWpub8WbxIcgb2JzZXJ3YWNqaSAocG96YSBza2FsxIUgbG9rYWxuxIUgb2tyZcWbbGFuxIUgcHJ6ZXogcm96bWlhciBva25hIGtvbndvbHVjamkpLiBPY3p5d2nFm2NpZSB3IGNlbHUgcm96cG96bmFuaWEgYmFyZHppZWogcm96Y2nEhWduacSZdHljaCBwcmF3aWTFgm93b8WbY2kgbW/FvGVteSB1dHdvcnp5xIcgc3RvcyB3aWVsdSB3YXJzdHcga29ud29sdWN5am55Y2ggaSB3YXJzdHcgxYLEhWN6xIVjeWNoLiBXIHRlbiBzcG9zw7NiIGfDs3JuZSB3YXJzdHd5IGLEmWTEhSBhbmFsaXpvd2HEhyBkxYJ1xbxzemUgZnJhZ21lbnR5IGRhbnljaCB3ZWrFm2Npb3d5Y2gsIGFsZSBqZXN0IHRvIHPFgmFieSBzcG9zw7NiIG5hIHdwcm93YWR6ZW5pZSB3cmHFvGxpd2/Fm2NpIG1vZGVsdSBuYSBrb2xlam5vxZvEhyBvYnNlcndhY2ppLiBTcHJhd2TFum15IHcgcHJha3R5Y2UgdMSZIHPFgmFib8WbxIcgbW9kZWx1IHBvZGN6YXMgcHJvZ25vem93YW5pYSB0ZW1wZXJhdHVyeSAodyB0eW0gcHJvYmxlbWllIGtvbGVqbm/Fm8SHIGplc3QgYmFyZHpvIHdhxbxuYSBkbGEgb3RyenltYW5pYSBwcmF3aWTFgm93eWNoIHByb2dub3opLiBXIHBvbmnFvHN6eW0gcHJ6eWvFgmFkemllIGtvcnp5c3RhbXkgcG9ub3duaWUgemUgemRlZmluaW93YW55Y2ggd2N6ZcWbbmllaiB6bWllbm55Y2ggZmxvYXRfZGF0YSwgdHJhaW5fZ2VuLCB2YWxfZ2VuIGkgdmFsX3N0ZXBzOg0KDQpgYGB7cn0NCmxpYnJhcnkodGliYmxlKQ0KbGlicmFyeShyZWFkcikNCg0KZGF0YV9kaXIgPC0gIn4vRG93bmxvYWRzL2plbmFfY2xpbWF0ZSINCmZuYW1lIDwtIGZpbGUucGF0aChkYXRhX2RpciwgImplbmFfY2xpbWF0ZV8yMDA5XzIwMTYuY3N2IikNCmRhdGEgPC0gcmVhZF9jc3YoZm5hbWUpDQoNCmRhdGEgPC0gZGF0YS5tYXRyaXgoZGF0YVssLTFdKQ0KDQp0cmFpbl9kYXRhIDwtIGRhdGFbMToyMDAwMDAsXQ0KbWVhbiA8LSBhcHBseSh0cmFpbl9kYXRhLCAyLCBtZWFuKQ0Kc3RkIDwtIGFwcGx5KHRyYWluX2RhdGEsIDIsIHNkKQ0KZGF0YSA8LSBzY2FsZShkYXRhLCBjZW50ZXIgPSBtZWFuLCBzY2FsZSA9IHN0ZCkNCg0KZ2VuZXJhdG9yIDwtIGZ1bmN0aW9uKGRhdGEsIGxvb2tiYWNrLCBkZWxheSwgbWluX2luZGV4LCBtYXhfaW5kZXgsDQogICAgICAgICAgICAgICAgICAgICAgc2h1ZmZsZSA9IEZBTFNFLCBiYXRjaF9zaXplID0gMTI4LCBzdGVwID0gNikgew0KICBpZiAoaXMubnVsbChtYXhfaW5kZXgpKQ0KICAgIG1heF9pbmRleCA8LSBucm93KGRhdGEpIC0gZGVsYXkgLSAxDQogIGkgPC0gbWluX2luZGV4ICsgbG9va2JhY2sNCiAgZnVuY3Rpb24oKSB7DQogICAgaWYgKHNodWZmbGUpIHsNCiAgICAgIHJvd3MgPC0gc2FtcGxlKGMoKG1pbl9pbmRleCtsb29rYmFjayk6bWF4X2luZGV4KSwgc2l6ZSA9IGJhdGNoX3NpemUpDQogICAgfSBlbHNlIHsNCiAgICAgIGlmIChpICsgYmF0Y2hfc2l6ZSA+PSBtYXhfaW5kZXgpDQogICAgICAgIGkgPDwtIG1pbl9pbmRleCArIGxvb2tiYWNrDQogICAgICByb3dzIDwtIGMoaTptaW4oaStiYXRjaF9zaXplLCBtYXhfaW5kZXgpKQ0KICAgICAgaSA8PC0gaSArIGxlbmd0aChyb3dzKQ0KICAgIH0NCiAgICANCiAgICBzYW1wbGVzIDwtIGFycmF5KDAsIGRpbSA9IGMobGVuZ3RoKHJvd3MpLCANCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbG9va2JhY2sgLyBzdGVwLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaW0oZGF0YSlbWy0xXV0pKQ0KICAgIHRhcmdldHMgPC0gYXJyYXkoMCwgZGltID0gYyhsZW5ndGgocm93cykpKQ0KICAgICAgICAgICAgICAgICAgICAgDQogICAgZm9yIChqIGluIDE6bGVuZ3RoKHJvd3MpKSB7DQogICAgICBpbmRpY2VzIDwtIHNlcShyb3dzW1tqXV0gLSBsb29rYmFjaywgcm93c1tbal1dLCANCiAgICAgICAgICAgICAgICAgICAgIGxlbmd0aC5vdXQgPSBkaW0oc2FtcGxlcylbWzJdXSkNCiAgICAgIHNhbXBsZXNbaiwsXSA8LSBkYXRhW2luZGljZXMsXQ0KICAgICAgdGFyZ2V0c1tbal1dIDwtIGRhdGFbcm93c1tbal1dICsgZGVsYXksMl0NCiAgICB9ICAgICAgICAgICAgDQogICAgDQogICAgbGlzdChzYW1wbGVzLCB0YXJnZXRzKQ0KICB9DQp9DQoNCmxvb2tiYWNrIDwtIDE0NDANCnN0ZXAgPC0gNg0KZGVsYXkgPC0gMTQ0DQpiYXRjaF9zaXplIDwtIDEyOA0KDQp0cmFpbl9nZW4gPC0gZ2VuZXJhdG9yKA0KICBkYXRhLA0KICBsb29rYmFjayA9IGxvb2tiYWNrLA0KICBkZWxheSA9IGRlbGF5LA0KICBtaW5faW5kZXggPSAxLA0KICBtYXhfaW5kZXggPSAyMDAwMDAsDQogIHNodWZmbGUgPSBUUlVFLA0KICBzdGVwID0gc3RlcCwgDQogIGJhdGNoX3NpemUgPSBiYXRjaF9zaXplDQopDQoNCnZhbF9nZW4gPSBnZW5lcmF0b3IoDQogIGRhdGEsDQogIGxvb2tiYWNrID0gbG9va2JhY2ssDQogIGRlbGF5ID0gZGVsYXksDQogIG1pbl9pbmRleCA9IDIwMDAwMSwNCiAgbWF4X2luZGV4ID0gMzAwMDAwLA0KICBzdGVwID0gc3RlcCwNCiAgYmF0Y2hfc2l6ZSA9IGJhdGNoX3NpemUNCikNCg0KdGVzdF9nZW4gPC0gZ2VuZXJhdG9yKA0KICBkYXRhLA0KICBsb29rYmFjayA9IGxvb2tiYWNrLA0KICBkZWxheSA9IGRlbGF5LA0KICBtaW5faW5kZXggPSAzMDAwMDEsDQogIG1heF9pbmRleCA9IE5VTEwsDQogIHN0ZXAgPSBzdGVwLA0KICBiYXRjaF9zaXplID0gYmF0Y2hfc2l6ZQ0KKQ0KDQojIExpY3piYSBrcm9rw7N3IHBvYmllcmFuaWEgZGFueWNoIHogb2JpZWt0dSB2YWxfZ2VuIHphcGV3bmlhasSFY3ljaCANCiMgcHJ6ZXR3b3J6ZW5pZSBjYcWCZWdvIHdhbGlkYWN5am5lZ28gemJpb3J1IGRhbnljaC4NCnZhbF9zdGVwcyA8LSAoMzAwMDAwIC0gMjAwMDAxIC0gbG9va2JhY2spIC8gYmF0Y2hfc2l6ZQ0KDQogICMgTGljemJhIGtyb2vDs3cgcG9iaWVyYW5pYSBkYW55Y2ggeiBvYmlla3R1IHRlc3RfZ2VuLCANCiAgIyBwcnp5IGt0w7NyZWogcHJ6ZXR3b3J6b255IHpvc3RhbmllIGNhxYJ5IHRlc3Rvd3kgemJpw7NyIGRhbnljaC4NCnRlc3Rfc3RlcHMgPC0gKG5yb3coZGF0YSkgLSAzMDAwMDEgLSBsb29rYmFjaykgLyBiYXRjaF9zaXplDQpgYGANCg0KYGBge3IsIGVjaG89VFJVRSwgcmVzdWx0cz0naGlkZSd9DQptb2RlbCA8LSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkgJT4lIA0KICBsYXllcl9jb252XzFkKGZpbHRlcnMgPSAzMiwga2VybmVsX3NpemUgPSA1LCBhY3RpdmF0aW9uID0gInJlbHUiLA0KICAgICAgICAgICAgICAgIGlucHV0X3NoYXBlID0gbGlzdChOVUxMLCBkaW0oZGF0YSlbWy0xXV0pKSAlPiUgDQogIGxheWVyX21heF9wb29saW5nXzFkKHBvb2xfc2l6ZSA9IDMpICU+JSANCiAgbGF5ZXJfY29udl8xZChmaWx0ZXJzID0gMzIsIGtlcm5lbF9zaXplID0gNSwgYWN0aXZhdGlvbiA9ICJyZWx1IikgJT4lIA0KICBsYXllcl9tYXhfcG9vbGluZ18xZChwb29sX3NpemUgPSAzKSAlPiUgDQogIGxheWVyX2NvbnZfMWQoZmlsdGVycyA9IDMyLCBrZXJuZWxfc2l6ZSA9IDUsIGFjdGl2YXRpb24gPSAicmVsdSIpICU+JSANCiAgbGF5ZXJfZ2xvYmFsX21heF9wb29saW5nXzFkKCkgJT4lIA0KICBsYXllcl9kZW5zZSh1bml0cyA9IDEpDQoNCg0KbW9kZWwgJT4lIGNvbXBpbGUoDQogIG9wdGltaXplciA9IG9wdGltaXplcl9ybXNwcm9wKCksDQogIGxvc3MgPSAibWFlIg0KKQ0KDQpoaXN0b3J5IDwtIG1vZGVsICU+JSBmaXRfZ2VuZXJhdG9yKA0KICB0cmFpbl9nZW4sDQogIHN0ZXBzX3Blcl9lcG9jaCA9IDUwMCwNCiAgZXBvY2hzID0gMjAsDQogIHZhbGlkYXRpb25fZGF0YSA9IHZhbF9nZW4sDQogIHZhbGlkYXRpb25fc3RlcHMgPSB2YWxfc3RlcHMNCikNCmBgYA0KDQpPdG8gd3lrcmVzIMWbcmVkbmllZ28gYmV6d3pnbMSZZG5lZ28gYsWCxJlkdSB0cmVub3dhbmlhIGkgd2FsaWRhY2ppLg0KDQpgYGB7cn0NCnBsb3QoaGlzdG9yeSkNCmBgYA0KDQrFmnJlZG5pIGJlend6Z2zEmWRueSBixYLEhWQgd2FsaWRhY2ppIHV0cnp5bXVqZSBzacSZIG5hIHBvemlvbWllIG9rb8WCbyA0MCUsIGEgd2nEmWMgbW9kZWwgdGVuIG5pZSBqZXN0IHcgc3RhbmllIHBva29uYcSHIG5hd2V0IHpkZWZpbmlvd2FuZWdvIHdjemXFm25pZWogcHVua3R1IG9kbmllc2llbmlhLiBEemllamUgc2nEmSB0YWssIHBvbmlld2HFvCBzaWXEhyBrb253b2x1Y3lqbmEgcG9zenVrdWplIHphbGXFvG5vxZtjaSB3IGNhxYJ5Y2ggZGFueWNoIHN6ZXJlZ3UgY3phc293ZWdvIGJleiB3aWVkenkgbyB0eW0sIHcgamFraW0gY3phc2llIHphb2JzZXJ3b3dhbm8gcHJ6ZXR3YXJ6YW5lIHdhcnRvxZtjaSAobmllIHp3cmFjYSB1d2FnaSBuYSB0bywgY3p5IHPEhSBvbmUgemJsacW8b25lIGJhcmR6aWVqIGRvIHBvY3rEhXRrdSwgY3p5IGRvIGtvxYRjYSBhbmFsaXpvd2FuZWdvIHpiaW9ydSkuIFcgdHltIHByb2JsZW1pZSBub3dzemUgZGFuZSBwb3dpbm55IGJ5xIcgaW50ZXJwcmV0b3dhbmUgdyBpbm55IHNwb3PDs2Igb2QgZGFueWNoIHogZGFsc3plaiBwcnplc3rFgm/Fm2NpLCBhIHdpxJljIHNpZcSHIGtvbndvbHVjeWpuYSBuaWUgamVzdCB3IHN0YW5pZSB3eWdlbmVyb3dhxIcgc2Vuc293bnljaCB3eW5pa8Ozdy4gVG8gb2dyYW5pY3plbmllIHNpZWNpIGtvbndvbHVjeWpueWNoIG5pZSBqZXN0IHByb2JsZW1hdHljem5lIHcgcHJ6eXBhZGt1IHpiaW9ydSBJTURCLCBwb25pZXdhxbwgc8WCb3dhIMWbd2lhZGN6xIVjZSBvIHR5bSwgxbxlIGRhbmEgcmVjZW56amEgamVzdCBwb2NobGVibmEgbHViIG5lZ2F0eXduYSwgbW9nxIUgem5hamRvd2HEhyBzacSZIHcgZG93b2xueW0gbWllanNjdSBhbmFsaXpvd2FueWNoIHpkYcWELg0KDQpTcG9zb2JlbSBuYSBwb8WCxIVjemVuaWUgc3p5YmtvxZtjaSBpIGxla2tvxZtjaSBzaWVjaSBrb253b2x1Y3lqbnljaCB6IGJyYW5pZW0gcG9kIHV3YWfEmSBrb2xlam5vxZtjaSBwcnpleiBzaWVjaSByZWt1cmVuY3lqbmUgamVzdCB6YXN0b3Nvd2FuaWUgamVkbm93eW1pYXJvd2VqIHNpZWNpIGtvbndvbHVjeWpuZWogdyByb2xpIG1lY2hhbml6bXUgcHJ6ZXR3YXJ6YWrEhWNlZ28gd3N0xJlwbmllIGRhbmUga2llcm93YW5lIGRvIHNpZWNpIHJla3VyZW5jeWpuZWogKHBhdHJ6IHJ5c3VuZWsgNi4yNSkuIFJvendpxIV6YW5pZSB0YWtpZSBzcHJhd2R6YSBzacSZIHN6Y3plZ8OzbG5pZSBkb2JyemUgcG9kY3phcyBwcmFjeSB6IGTFgnVnaW1pIHNla3dlbmNqYW1pLCBrdMOzcnljaCBkxYJ1Z2/Fm8SHIHVuaWVtb8W8bGl3aWEgaWNoIHNlbnNvd25lIHByemV0d29yemVuaWUgemEgcG9tb2PEhSBzYW15Y2ggc2llY2kgcmVrdXJlbmN5am55Y2ggKHBpc3rEmSB0dSBvIHNla3dlbmNqYWNoIHNrxYJhZGFqxIVjeWNoIHNpxJkgbmF3ZXQgeiB0eXNpxJljeSBrcm9rw7N3KS4gU2llxIcga29ud29sdWN5am5hIHphbWllbmkgZMWCdWfEhSBzZWt3ZW5jasSZIHdlasWbY2lvd8SFIHcga3LDs3RzemUgc2Vrd2VuY2plIGNlY2ggd3nFvHN6ZWdvIHBvemlvbXUsIGt0w7NyZSBtb8W8bmEgbmFzdMSZcG5pZSBza2llcm93YcSHIGRvIHdhcnN0d3kgcmVrdXJlbmN5am5lai4NCg0KDQpUZWNobmlrYSB0YSBqZXN0IG5hIHR5bGUgbWHFgm8gem5hbmEsIMW8ZSByemFka28gc3BvdHlrYSBzacSZIGrEhSB3IGFydHlrdcWCYWNoIG5hdWtvd3ljaCBpIHByYWt0eWN6bnljaCB6YXN0b3Nvd2FuaWFjaC4gSmVzdCBqZWRuYWsgbmEgdHlsZSBza3V0ZWN6bmEsIMW8ZSBwb3dpbm5hIGJ5xIcgYmFyZHppZWogcG9wdWxhcm5hLiBTcHLDs2J1am15IHXFvHnEhyBqZWogdyBjZWx1IHJvendpxIV6YW5pYSBwcm9ibGVtdSBwcm9nbm96b3dhbmlhIHRlbXBlcmF0dXJ5LiBSb3p3acSFemFuaWUgdG8gcG96d2FsYSBuYSBwcnpldHdhcnphbmllIG8gd2llbGUgZMWCdcW8c3p5Y2ggc2Vrd2VuY2ppLCBhIHdpxJljIG1vxbxlbXkgcHJ6eWdsxIVkYcSHIHNpxJkgZGFueW0geiBkYWxzemVqIHByemVzesWCb8WbY2kgcG9wcnpleiB6d2nEmWtzemVuaWUgd2FydG/Fm2NpIHBhcmFtZXRydSBsb29rYmFjayBnZW5lcmF0b3JhIGRhbnljaCBsdWIgcHJ6eWdsxIVkYcSHIHNpxJkgc3plcmVnb20gY3phc293eW0gbyB3ecW8c3plaiByb3pkemllbGN6b8WbY2kgcG9wcnpleiB6bW5pZWpzemVuaWUgd2FydG/Fm2NpIHBhcmFtZXRydSBzdGVwIGdlbmVyYXRvcmEgZGFueWNoLiBXIHphcHJlemVudG93YW55bSBwcnp5a8WCYWR6aWUgemRlY3lkb3dhxYJlbSBzacSZIG5hIHptbmllanN6ZW5pZSBvIHBvxYJvd8SZIHBhcmFtZXRydSBzdGVwLCBjbyB3eWTFgnXFvHnFgm8gZHd1a3JvdG5pZSBhbmFsaXpvd2FuZSBzemVyZWdpIGN6YXNvd2UgKHByYWN1amVteSB6IHByw7Nia2FtaSB0ZW1wZXJhdHVyeSBvZGN6eXR5d2FuZWogdyBvZHN0xJlwaWUgMzAgbWludXQpLiBQb25vd25pZSBrb3J6eXN0YW0gemUgemRlZmluaW93YW5laiB3Y3plxZtuaWVqIGZ1bmtjamkgZ2VuZXJhdG9yLg0KDQoNCmBgYHtyfQ0KIyBXY3plxZtuaWVqIHBhcmFtZXRyIHRlbiBwcnp5am1vd2HFgiB3YXJ0b8WbxIcgcsOzd27EhSA2ICgxIG9ic2Vyd2FjamEgbmEgZ29kemluxJkpLiANCiMgb2JzZXJ3YWNqYSBuYSAzMCBtaW51dCkuDQpzdGVwIDwtIDMgDQpsb29rYmFjayA8LSA3MjAgICMgQmV6IHptaWFuLg0KZGVsYXkgPC0gMTQ0ICAjIEJleiB6bWlhbi4NCiAgDQp0cmFpbl9nZW4gPC0gZ2VuZXJhdG9yKA0KICBkYXRhLA0KICBsb29rYmFjayA9IGxvb2tiYWNrLA0KICBkZWxheSA9IGRlbGF5LA0KICBtaW5faW5kZXggPSAxLA0KICBtYXhfaW5kZXggPSAyMDAwMDAsDQogIHNodWZmbGUgPSBUUlVFLA0KICBzdGVwID0gc3RlcA0KKQ0KDQp2YWxfZ2VuIDwtIGdlbmVyYXRvcigNCiAgZGF0YSwNCiAgbG9va2JhY2sgPSBsb29rYmFjaywNCiAgZGVsYXkgPSBkZWxheSwNCiAgbWluX2luZGV4ID0gMjAwMDAxLA0KICBtYXhfaW5kZXggPSAzMDAwMDAsDQogIHN0ZXAgPSBzdGVwDQopDQoNCnRlc3RfZ2VuIDwtIGdlbmVyYXRvcigNCiAgZGF0YSwNCiAgbG9va2JhY2sgPSBsb29rYmFjaywNCiAgZGVsYXkgPSBkZWxheSwNCiAgbWluX2luZGV4ID0gMzAwMDAxLA0KICBtYXhfaW5kZXggPSBOVUxMLA0KICBzdGVwID0gc3RlcA0KKQ0KDQp2YWxfc3RlcHMgPC0gKDMwMDAwMCAtIDIwMDAwMSAtIGxvb2tiYWNrKSAvIDEyOA0KdGVzdF9zdGVwcyA8LSAobnJvdyhkYXRhKSAtIDMwMDAwMSAtIGxvb2tiYWNrKSAvIDEyOA0KYGBgDQoNClRlcmF6IG1vxbxlbXkgc3R3b3J6ecSHIG1vZGVsLiBQb8WCxIVjenlteSBkd2llIHdhcnN0d3kgbGF5ZXJfY29udl8xZCB6IHdhcnN0d8SFIGxheWVyX2dydS4NCg0KYGBge3J9DQptb2RlbCA8LSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkgJT4lIA0KICBsYXllcl9jb252XzFkKGZpbHRlcnMgPSAzMiwga2VybmVsX3NpemUgPSA1LCBhY3RpdmF0aW9uID0gInJlbHUiLA0KICAgICAgICAgICAgICAgIGlucHV0X3NoYXBlID0gbGlzdChOVUxMLCBkaW0oZGF0YSlbWy0xXV0pKSAlPiUgDQogIGxheWVyX21heF9wb29saW5nXzFkKHBvb2xfc2l6ZSA9IDMpICU+JSANCiAgbGF5ZXJfY29udl8xZChmaWx0ZXJzID0gMzIsIGtlcm5lbF9zaXplID0gNSwgYWN0aXZhdGlvbiA9ICJyZWx1IikgJT4lIA0KICBsYXllcl9ncnUodW5pdHMgPSAzMiwgZHJvcG91dCA9IDAuMSwgcmVjdXJyZW50X2Ryb3BvdXQgPSAwLjUpICU+JSANCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSAxKQ0KDQpzdW1tYXJ5KG1vZGVsKQ0KYGBgDQoNCmBgYHtyLCBlY2hvPVRSVUUsIHJlc3VsdHM9J2hpZGUnfQ0KbW9kZWwgJT4lIGNvbXBpbGUoDQogIG9wdGltaXplciA9IG9wdGltaXplcl9ybXNwcm9wKCksDQogIGxvc3MgPSAibWFlIg0KKQ0KDQpoaXN0b3J5IDwtIG1vZGVsICU+JSBmaXRfZ2VuZXJhdG9yKA0KICB0cmFpbl9nZW4sDQogIHN0ZXBzX3Blcl9lcG9jaCA9IDUwMCwNCiAgZXBvY2hzID0gMjAsDQogIHZhbGlkYXRpb25fZGF0YSA9IHZhbF9nZW4sDQogIHZhbGlkYXRpb25fc3RlcHMgPSB2YWxfc3RlcHMNCikNCmBgYA0KDQpgYGB7cn0NCnBsb3QoaGlzdG9yeSkNCmBgYA0KDQpQcnp5Z2zEhWRhasSFYyBzacSZIHd5a3Jlc293aSBzdHJhdHkgd2FsaWRhY3lqbmVqLCBtb8W8ZW15IHN0d2llcmR6acSHLCDFvGUgdGFrYSBrb25maWd1cmFjamEgbW9kZWx1IGplc3Qgc8WCYWJzemEgb2Qgc2FtZWogd2Fyc3R3eSBsYXllcl9ncnUgcG9kZGFuZWogcmVndWxhcnl6YWNqaSwgYWxlIGR6aWHFgmEgem5hY3puaWUgc3p5YmNpZWouIEFuYWxpenVqZSBkd2EgcmF6eSB3acSZY2VqIGRhbnljaCwgY28gdyB0eW0gcHJ6eXBhZGt1IG5pZSBqZXN0IHphYmllZ2llbSBzemN6ZWfDs2xuaWUgcHJ6eWRhdG55bSwgYWxlIHcgaW5ueWNoIHpiaW9yYWNoIGRhbnljaCBtb8W8ZSBwcnp5bmllxZvEhyB6bmFjem7EhSBwb3ByYXfEmSBwcmFjeSBhbGdvcnl0bXUuDQoNCiMjIFduaW9za2kNCg0KT3RvIHduaW9za2ksIGt0w7NyZSBuYWxlxbx5IHd5bmllxZvEhyB6IHRlZ28gcG9kcm96ZHppYcWCdToNCg0KKglKZWRub3d5bWlhcm93ZSBrb253b2x1Y3lqbmUgc2llY2kgbmV1cm9ub3dlIGRvc2tvbmFsZSBuYWRhasSFIHNpxJkgZG8gcHJ6ZXR3YXJ6YW5pYSBkYW55Y2ggc3plcmVnw7N3IGN6YXNvd3ljaCwgdGFrIGphayBkd3V3eW1pYXJvd2Ugc2llY2kga29ud29sdWN5am5lIGRvc2tvbmFsZSBuYWRhasSFIHNpxJkgZG8gcHJ6ZXR3YXJ6YW5pYSB3em9yY8OzdyB6YWtvZG93YW55Y2ggdyBwxYJhc3pjenl6bmFjaCBkd3V3eW1pYXJvd3ljaCBvYnJhesOzdy4gVyBwcnp5cGFka3Ugbmlla3TDs3J5Y2ggcHJvYmxlbcOzdyBzaWVjaSB0ZSBzdGFub3dpxIUgc3p5YnN6xIUgYWx0ZXJuYXR5d8SZIHNpZWNpIHJla3VyZW5jeWpueWNoLiBEb3R5Y3p5IHRvIHN6Y3plZ8OzbG5pZSB6YWRhxYQgendpxIV6YW55Y2ggeiBwcnpldHdhcnphbmllbSBqxJl6eWthIG5hdHVyYWxuZWdvLg0KKglad3lrbGUgamVkbm93eW1pYXJvd2Ugc2llY2kga29ud29sdWN5am5lIG1hasSFIHN0cnVrdHVyxJkgcHJ6eXBvbWluYWrEhWPEhSBzdHJ1a3R1csSZIGljaCBkd3V3eW1pYXJvd3ljaCBvZHBvd2llZG5pa8OzdyBzdG9zb3dhbnljaCBkbyBwcnpldHdhcnphbmlhIG9icmF6dTogc2vFgmFkYWrEhSBzacSZIHplIHN0b3N1IHdhcnN0dyBsYXllcl9jb252XzFkIGkgbGF5ZXJfbWF4X3Bvb2xpbmdfMWQgKG5hIGljaCBrb8WEY3Ugc3Rvc293YW5lIHPEhSB3YXJzdHd5IHd5a29udWrEhWNlIG9wZXJhY2plIGdsb2JhbG5lZ28gc3Vtb3dhbmlhIGx1YiBzcMWCYXN6Y3phbmlhKS4NCioJVcW8eXdhbmllIHJla3VyZW5jeWpueWNoIHNpZWNpIG5ldXJvbm93eWNoIGRvIHByemV0d2FyemFuaWEgZMWCdWdpY2ggc2Vrd2VuY2ppIHdpxIXFvGUgc2nEmSB6IGR1xbx5bSB3eWRhdGtpZW0gb2JsaWN6ZW5pb3d5bSwgYSBqZWRub3d5bWlhcm93ZSBzaWVjaSBrb253b2x1Y3lqbmUgd3ltYWdhasSFIG8gd2llbGUgcHJvc3RzenljaCBvYmxpY3plxYQuIFcgendpxIV6a3UgeiB0eW0gd2FydG8gdcW8eXdhxIcgamVkbm93eW1pYXJvd3ljaCBzaWVjaSBrb253b2x1Y3lqbnljaCB3IHJvbGkgbWVjaGFuaXptw7N3IHdzdMSZcG5pZSBwcnpldHdhcnphasSFY3ljaCBkYW5lIHByemVkIHNraWVyb3dhbmllbSBpY2ggZG8gd2Fyc3R3IHNpZWNpIHJla3VyZW5jeWpuZWouIFRha2llIHJvendpxIV6YW5pZSBza3JhY2EgYW5hbGl6b3dhbsSFIHNla3dlbmNqxJksIGEgd2Fyc3R3eSByZWt1cmVuY3lqbmUgemFqbXVqxIUgc2nEmSB0eWxrbyBwcnp5ZGF0bnltaSByZXByZXplbnRhY2phbWkgZGFueWNoLg0K