Introduction

In the broad field of machine learning, there are mainly 3 types of algorithms. The classical classification is:
- supervised learning: try to explain (and then predict) one variable (\(y\)) with other variables (\(X\));
- unsupervised learning: try to make sense of a dataset on its own; often, this amounts to finding clusters;
- reinforcement learning: learn via trial and error; perform actions, get rewards and improve!

This notebook is dedicated to supervised learning. In supervised learning, there are two key elements:

Label Feature
y X
Dependent variable Independent variable
Output Input
Predicted variable Predictor

The core equation has the form: \[y = f(X)+e,\] because we try to make sense of \(y\) with the knowledge of \(X\). By "make sense’, we mean: find a magical formula (\(f\)) such that the related error \(e\) are not too big (see below). When \(y\) is a number, we talk about regression, when \(y\) is a category or class, the exercise is a classification. For simplicity, we only focus on regression in this notebook, but the ideas are very similar for classification.

The kind of questions we can answer are for instance:

  • can we explain the price (\(y\)) of a diamond with is size (carat), cut, color, clarity? All these variables are included/stacked into \(X\).
  • can we predict the popularity (\(y\)) of a song with \(X\) being its length, valence, danceability, loudness, etc.?

Linear models: the genesis, the building blocks

The basic idea

The simplest functions are linear. For diamonds, the formula would be:

\[price = b + b_{carat} \times carat + b_{cut} \times cut + b_{color} \times color + b_{clarity} \times clarity,\]

and the whole challenge is to find the magical numbers \(b_{xxx}\). It is customary to include a constant in the model - here it is \(b\). Naturally, the above formulation assumes that all variables are numerical: it is impossible to multiply text or categories. This is no big deal for ordered categories: we can simply transform them into numbers. For instance, the cut values of the diamonds will be coded as 1 for Fair, 2 for Good, 3 for Very Good, 4 for Premium and 5 for Ideal.

Obviously, if we want to find a formula for a large quantity of diamonds, say 10,000, it will be impossible to find values of the coefficients \(b_{xxx}\) that exactly match the prices of the diamonds. We will have to admit that the models makes some errors. Hence, the formula will be

\[price_i = b + b_{carat} \times carat_i + b_{cut} \times cut_i + b_{color} \times color_i + b_{clarity} \times clarity_i + error_i,\]

where we use the index i to show that we model the price of diamond number i with the carat number i, the cut number i, and so on. For each diamond, the model will make an error, also indexed by i. Note that the coefficients \(b_{xxx}\) are not indexed by i: they will be common to all diamonds.

The key question now is: how do we determine these coefficients?

The answer is simple: we want to make the smallest errors as possible! A simple objective would be to minimize the sum of errors. This is not a good idea because positive errors would offset negative errors (i.e. if we overprice or underprice the diamonds). Instead, it is more relevant to minimize the sum of squared errors:

\[\underset{b_{xxx}}{\text{min}} \ \sum_{i=1}^N(error_i)^2\]

Remember that the errors depend directly on the \(b_{xxx}\) numbers.

Some practice

Simple linear models are obtained in R via the function lm(). The syntax is a it strange at first because of the tilde ~, but very recurrent in other statistical packages. First, we digitize the diamonds database. For technical reasons, we also divide the price of diamonds by 1,000. Machine learning algorithms prefer when numbers have homogeneous magnitudes and are possibly not too big.

library(tidyverse)
diams <- diamonds %>%
    select(price, carat, cut, color, clarity) %>%
    mutate_if(is.factor, as.numeric) %>%
    mutate(price = price / 1000)
head(diams)

We confirm that all variables are numerical.
We can then proceed to the regression.

lm(price ~ carat + cut + color + clarity, data = diams)

Call:
lm(formula = price ~ carat + cut + color + clarity, data = diams)

Coefficients:
(Intercept)        carat          cut        color      clarity  
    -4.6612       8.7838       0.1557      -0.3197       0.5248  

The (Intercept) is the constant \(b\). The model is thus:

\[price_i = -4.66 + 8.78 \times carat_i + 0.16 \times cut_i-0.32 \times color_i + 0.52 \times clarity_i+ error_i\]

Beyond this simple output, many interesting quantities can be computed that further characterize the regression output (\(R^2\), \(t\)-statistics, \(p\)-values, etc.). To obtain them, it suffices to pipe a summary. A detailed analysis of these numbers is out of the scope of this introductory session.

lm(price ~ carat + cut + color + clarity, data = diams) %>% summary()

Call:
lm(formula = price ~ carat + cut + color + clarity, data = diams)

Residuals:
     Min       1Q   Median       3Q      Max 
-19.7704  -0.6934  -0.1692   0.5488   9.7219 

Coefficients:
             Estimate Std. Error t value Pr(>|t|)    
(Intercept) -4.661173   0.027590 -168.94   <2e-16 ***
carat        8.783772   0.012692  692.09   <2e-16 ***
cut          0.155700   0.004863   32.01   <2e-16 ***
color       -0.319673   0.003302  -96.81   <2e-16 ***
clarity      0.524843   0.003527  148.80   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1.235 on 53935 degrees of freedom
Multiple R-squared:  0.9042,    Adjusted R-squared:  0.9042 
F-statistic: 1.272e+05 on 4 and 53935 DF,  p-value: < 2.2e-16

Now, let us imagine a small diamond, say with 0.4 carat, a fair cut, and color code of 2 and average clarity of 3 (corresponding to SI1). Let us compute the model value (assuming zero error) for this diamond:

\[price = -4.66 + 8.78 \times 0.4 + 0.16 \times 1-0.32 \times 2 + 0.52 \times 3 = -0.07,\]

that is: the predicted price is negative. Hum hum….
Linear relationships are too limited.
But it’s possible to build models that are more complex…

Neural networks

Introduction

Often, neural networks (NNs) are represented with figures like the one below:

This is a very simplistic view of what NNs are. In fact, in each circle, there is a linear model! And in between different colors, a non-linear model is applied. The output from the blue models are altered and sent as input to the green linear models. The same process is re-iterated from green to red. Each color represents what is called a layer. The original input is transformed and passed to layers to the right, until it reaches the last layer, which is simply the output.

The exact structure is detailed below for a very small network.

Needless to say: NNs can be very complicated functions with lots of parameters. In neural networks, the parameters are all the coefficients (called weights) in all linear units in the network.

The crucial step is thus to find the best parameters, just like for regressions. Just like for regression, the model will aim at minimizing the sum of squared errors. This quantity is called the loss.

Finding the optimal parameters for a complex function like a NN cannot be done automatically like for regressions. The process that finds good parameters is progressive, iterative. The idea is the following:

The aim is to reduce the total error. So we use the derivative and follow it to reach a minimum point.

The process is complicated at the scale of the whole network and relies on the chain rule for differentiation. It starts from the right of the network and then diffuses back progressively to the early nodes of the network. That’s why it’s called backpropagation.

Example: diamonds

We show how to implement NNs in R via the keras package. But first, we must prepare the data.

even <- 2*(1:20000)                   # Even numbers
odd <- even + 1                       # Odd numbers
diam_train <- diams[even,]            # Training set
train_label <- diam_train$price       # Training label
train_features <- diam_train %>%      # Training features
  select(-price) %>%
  as.matrix()
diam_test <- diams[odd,]              # Testing sample
test_label <- diam_test$price         # Testing label
test_features <- diam_test %>%        # Testing features
  select(-price) %>%
  as.matrix()

The construction of the network requires 3 steps:
1. Definition of the structure of the network (unmber of layers & units per layer)
2. Setting of the loss function and learning process
3. Training by specifying the batch sizes and number of rounds

The batch size is how many instances are used to compute gradients in the backprop (at a time). The number of rounds is how many times the backprop sees the whole training sample.

The lines below rely on Keras, a deep learning framework originally coded in Python. They require a Python installation as well as the keras package, see the installation section of https://keras.rstudio.com.

library(keras)
# install_keras() # To complete installation
model <- keras_model_sequential()
model %>%   # This defines the structure of the network, i.e. how layers are organized
    layer_dense(units = 16, activation = 'relu', input_shape = ncol(train_features)) %>%
    layer_dense(units = 8, activation = 'sigmoid') %>%
    layer_dense(units = 1) # No activation means linear activation: f(x) = x.
2020-02-27 22:01:48.192533: I tensorflow/core/platform/cpu_feature_guard.cc:142] Your CPU supports instructions that this TensorFlow binary was not compiled to use: AVX2 FMA
2020-02-27 22:01:48.209129: I tensorflow/compiler/xla/service/service.cc:168] XLA service 0x7fc7640aee50 executing computations on platform Host. Devices:
2020-02-27 22:01:48.209146: I tensorflow/compiler/xla/service/service.cc:175]   StreamExecutor device (0): Host, Default Version

We can plot this architecture via tools such as: http://alexlenail.me/NN-SVG/index.html.

model %>% compile(                             # Model specification
    loss = 'mean_squared_error',               # Loss function
    optimizer = optimizer_rmsprop(),           # Optimisation method (weight updating)
    metrics = c('mean_absolute_error')         # Output metric
)
summary(model)                                 # Model architecture
Model: "sequential"
____________________________________________________________________________________________________________________________
Layer (type)                                           Output Shape                                      Param #            
============================================================================================================================
dense (Dense)                                          (None, 16)                                        80                 
____________________________________________________________________________________________________________________________
dense_1 (Dense)                                        (None, 8)                                         136                
____________________________________________________________________________________________________________________________
dense_2 (Dense)                                        (None, 1)                                         9                  
============================================================================================================================
Total params: 225
Trainable params: 225
Non-trainable params: 0
____________________________________________________________________________________________________________________________
fit_NN <- model %>% 
    fit(train_features,                                          # Training features
        train_label,                                             # Training labels
        epochs = 50, batch_size = 512,                           # Training parameters
        validation_data = list(test_features, test_label),       # Test data
        verbose = 0                                              # No messages
        ) 
plot(fit_NN)                                                     # Plot, evidently!

Let’s test the model on the fake diamond mentioned before (0.4 carat, 1 cut, 2 color, 3 clarity):

example <- c(0.4, 1, 2, 3) %>% t()  # Transpose for technical reason
predict(model, example)
          [,1]
[1,] 0.2422513

Example: predicting song popularity

Recycling a model structure is very easy! Let’s try this on the songs dataset. First, we import the data and normalize some columns.

load("songs.RData")
songs <- songs %>%
  mutate(duration = duration / 60,
         popularity = popularity / 100,
         tempo = tempo / 100)

Let’s have a look at the first row.

songs[1,]

We want to be able to predict this popularity of 73 with a neural network. Let’s go! We build the model on all songs except the first one. First, we construct the training data.

feature_songs <- c("duration", "danceability", "energy", "loudness", "speechiness", "tempo", "valence")
train_songs <- songs[2:13070,]
songs_features <- train_songs %>%
  select(feature_songs) %>%
  as.matrix()
songs_label <- train_songs$popularity 

Next, we rebuild the model.

model2 <- keras_model_sequential()
model2 %>%   # This defines the structure of the network, i.e. how layers are organized
    layer_dense(units = 16, activation = 'relu', input_shape = length(feature_songs)) %>% # The orignal size is different
    layer_dense(units = 8, activation = 'sigmoid') %>%
    layer_dense(units = 1) # No activation means linear activation: f(x) = x.

model2 %>% compile(                             # Model specification
    loss = 'mean_squared_error',               # Loss function
    optimizer = optimizer_rmsprop(),           # Optimisation method (weight updating)
    metrics = c('mean_absolute_error')         # Output metric
)
summary(model2)                                 # Model architecture
Model: "sequential_1"
____________________________________________________________________________________________________________________________
Layer (type)                                           Output Shape                                      Param #            
============================================================================================================================
dense_3 (Dense)                                        (None, 16)                                        128                
____________________________________________________________________________________________________________________________
dense_4 (Dense)                                        (None, 8)                                         136                
____________________________________________________________________________________________________________________________
dense_5 (Dense)                                        (None, 1)                                         9                  
============================================================================================================================
Total params: 273
Trainable params: 273
Non-trainable params: 0
____________________________________________________________________________________________________________________________

There are more parameters because the original data has 7 columns and not 4. Now let’s turn to the actual learning: don’t forget to change the inputs.

fit_NN2 <- model2 %>% 
    fit(songs_features,                                          # Training features
        songs_label,                                             # Training labels
        epochs = 30, batch_size = 256,                           # Training parameters
        validation_data = list(songs_features, songs_label),     # Test data
        verbose = 0                                              # No messages
        ) 
plot(fit_NN2)                                                    # Plot, evidently!

predict(model2, songs[1,] %>% select(feature_songs) %>% as.matrix())
          [,1]
[1,] 0.5408809

The number is not great. In addition, it’s random. Because the original weights are determined randomly.

For diamonds, the NN work well because the variables have an obvious direct impact on the price: size, purity, etc.
For songs, this is not obvious. Hence, the lower precision.

LS0tCnRpdGxlOiAiU3VwZXJ2aXNlZCBsZWFybmluZyIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQotLS0KCjxzdHlsZSB0eXBlPSJ0ZXh0L2NzcyI+Ci50YWJsZSB7CiAgICB3aWR0aDogNTAlOwogICAgbWFyZ2luLWxlZnQ6YXV0bzsgCiAgICBtYXJnaW4tcmlnaHQ6YXV0bzsKfQo8L3N0eWxlPgoKIyBJbnRyb2R1Y3Rpb24KCkluIHRoZSBicm9hZCBmaWVsZCBvZiBtYWNoaW5lIGxlYXJuaW5nLCB0aGVyZSBhcmUgbWFpbmx5IDMgdHlwZXMgb2YgYWxnb3JpdGhtcy4gVGhlIGNsYXNzaWNhbCBjbGFzc2lmaWNhdGlvbiBpczogICAKLSAqKnN1cGVydmlzZWQgbGVhcm5pbmcqKjogdHJ5IHRvIGV4cGxhaW4gKGFuZCB0aGVuIHByZWRpY3QpIG9uZSB2YXJpYWJsZSAoJHkkKSB3aXRoIG90aGVyIHZhcmlhYmxlcyAoJFgkKTsgICAgCi0gKip1bnN1cGVydmlzZWQgbGVhcm5pbmcqKjogdHJ5IHRvIG1ha2Ugc2Vuc2Ugb2YgYSBkYXRhc2V0IG9uIGl0cyBvd247IG9mdGVuLCB0aGlzIGFtb3VudHMgdG8gZmluZGluZyBjbHVzdGVyczsgICAKLSAqKnJlaW5mb3JjZW1lbnQgbGVhcm5pbmcqKjogbGVhcm4gdmlhIHRyaWFsIGFuZCBlcnJvcjsgcGVyZm9ybSBhY3Rpb25zLCBnZXQgcmV3YXJkcyBhbmQgaW1wcm92ZSEgICAgIAoKClRoaXMgbm90ZWJvb2sgaXMgZGVkaWNhdGVkIHRvIHN1cGVydmlzZWQgbGVhcm5pbmcuIEluIHN1cGVydmlzZWQgbGVhcm5pbmcsIHRoZXJlIGFyZSB0d28ga2V5IGVsZW1lbnRzOiAKCnxMYWJlbHxGZWF0dXJlfAp8LS0tOnwtLS06fAp8eXxYfAp8RGVwZW5kZW50IHZhcmlhYmxlfEluZGVwZW5kZW50IHZhcmlhYmxlfAp8T3V0cHV0fElucHV0fAp8UHJlZGljdGVkIHZhcmlhYmxlfFByZWRpY3RvcnwKClRoZSBjb3JlIGVxdWF0aW9uIGhhcyB0aGUgZm9ybToKJCR5ID0gZihYKStlLCQkCmJlY2F1c2Ugd2UgdHJ5IHRvIG1ha2Ugc2Vuc2Ugb2YgJHkkIHdpdGggdGhlIGtub3dsZWRnZSBvZiAkWCQuIEJ5ICIqbWFrZSBzZW5zZSonLCB3ZSBtZWFuOiBmaW5kIGEgKiptYWdpY2FsIGZvcm11bGEqKiAoJGYkKSBzdWNoIHRoYXQgdGhlIHJlbGF0ZWQgZXJyb3IgJGUkIGFyZSBub3QgdG9vIGJpZyAoc2VlIGJlbG93KS4gV2hlbiAkeSQgaXMgYSBudW1iZXIsIHdlIHRhbGsgYWJvdXQgKipyZWdyZXNzaW9uKiosIHdoZW4gJHkkIGlzIGEgY2F0ZWdvcnkgb3IgY2xhc3MsIHRoZSBleGVyY2lzZSBpcyBhICoqY2xhc3NpZmljYXRpb24qKi4gRm9yIHNpbXBsaWNpdHksIHdlIG9ubHkgZm9jdXMgb24gcmVncmVzc2lvbiBpbiB0aGlzIG5vdGVib29rLCBidXQgdGhlIGlkZWFzIGFyZSB2ZXJ5IHNpbWlsYXIgZm9yIGNsYXNzaWZpY2F0aW9uLgoKVGhlIGtpbmQgb2YgcXVlc3Rpb25zIHdlIGNhbiBhbnN3ZXIgYXJlIGZvciBpbnN0YW5jZToKCi0gY2FuIHdlIGV4cGxhaW4gdGhlIHByaWNlICgkeSQpIG9mIGEgZGlhbW9uZCB3aXRoIGlzIHNpemUgKGNhcmF0KSwgY3V0LCBjb2xvciwgY2xhcml0eT8gQWxsIHRoZXNlIHZhcmlhYmxlcyBhcmUgaW5jbHVkZWQvc3RhY2tlZCBpbnRvICRYJC4gICAgIAotIGNhbiB3ZSBwcmVkaWN0IHRoZSBwb3B1bGFyaXR5ICgkeSQpIG9mIGEgc29uZyB3aXRoICRYJCBiZWluZyBpdHMgbGVuZ3RoLCB2YWxlbmNlLCBkYW5jZWFiaWxpdHksIGxvdWRuZXNzLCBldGMuPwoKCiMgTGluZWFyIG1vZGVsczogdGhlIGdlbmVzaXMsIHRoZSBidWlsZGluZyBibG9ja3MKIyMgVGhlIGJhc2ljIGlkZWEKClRoZSBzaW1wbGVzdCBmdW5jdGlvbnMgYXJlIGxpbmVhci4gRm9yIGRpYW1vbmRzLCB0aGUgZm9ybXVsYSB3b3VsZCBiZToKCiQkcHJpY2UgPSBiICsgYl97Y2FyYXR9IFx0aW1lcyBjYXJhdCArIGJfe2N1dH0gXHRpbWVzIGN1dCArIGJfe2NvbG9yfSBcdGltZXMgY29sb3IgKyBiX3tjbGFyaXR5fSBcdGltZXMgY2xhcml0eSwkJAoKYW5kIHRoZSB3aG9sZSBjaGFsbGVuZ2UgaXMgdG8gZmluZCB0aGUgbWFnaWNhbCBudW1iZXJzICRiX3t4eHh9JC4gSXQgaXMgY3VzdG9tYXJ5IHRvIGluY2x1ZGUgYSBjb25zdGFudCBpbiB0aGUgbW9kZWwgLSBoZXJlIGl0IGlzICRiJC4gTmF0dXJhbGx5LCB0aGUgYWJvdmUgZm9ybXVsYXRpb24gYXNzdW1lcyB0aGF0IGFsbCB2YXJpYWJsZXMgYXJlICoqbnVtZXJpY2FsKio6IGl0IGlzIGltcG9zc2libGUgdG8gbXVsdGlwbHkgdGV4dCBvciBjYXRlZ29yaWVzLiBUaGlzIGlzIG5vIGJpZyBkZWFsIGZvciBvcmRlcmVkIGNhdGVnb3JpZXM6IHdlIGNhbiBzaW1wbHkgdHJhbnNmb3JtIHRoZW0gaW50byBudW1iZXJzLiBGb3IgaW5zdGFuY2UsIHRoZSAqKmN1dCoqIHZhbHVlcyAgb2YgdGhlIGRpYW1vbmRzIHdpbGwgYmUgY29kZWQgYXMgMSBmb3IgKipGYWlyKiosIDIgZm9yICoqR29vZCoqLCAzIGZvciAqKlZlcnkgR29vZCoqLCA0IGZvciAqKlByZW1pdW0qKiBhbmQgNSBmb3IgKipJZGVhbCoqLgoKCk9idmlvdXNseSwgaWYgd2Ugd2FudCB0byBmaW5kIGEgZm9ybXVsYSBmb3IgYSBsYXJnZSBxdWFudGl0eSBvZiBkaWFtb25kcywgc2F5IDEwLDAwMCwgaXQgd2lsbCBiZSBpbXBvc3NpYmxlIHRvIGZpbmQgdmFsdWVzIG9mIHRoZSBjb2VmZmljaWVudHMgJGJfe3h4eH0kIHRoYXQgZXhhY3RseSBtYXRjaCB0aGUgcHJpY2VzIG9mIHRoZSBkaWFtb25kcy4gV2Ugd2lsbCBoYXZlIHRvIGFkbWl0IHRoYXQgdGhlIG1vZGVscyBtYWtlcyBzb21lICoqZXJyb3JzKiouIEhlbmNlLCB0aGUgZm9ybXVsYSB3aWxsIGJlCgokJHByaWNlX2kgPSBiICsgYl97Y2FyYXR9IFx0aW1lcyBjYXJhdF9pICsgYl97Y3V0fSBcdGltZXMgY3V0X2kgKyBiX3tjb2xvcn0gXHRpbWVzIGNvbG9yX2kgKyBiX3tjbGFyaXR5fSBcdGltZXMgY2xhcml0eV9pICsgZXJyb3JfaSwkJAoKd2hlcmUgd2UgdXNlIHRoZSBpbmRleCBpIHRvIHNob3cgdGhhdCB3ZSBtb2RlbCB0aGUgcHJpY2Ugb2YgZGlhbW9uZCBudW1iZXIgaSB3aXRoIHRoZSBjYXJhdCBudW1iZXIgaSwgdGhlIGN1dCBudW1iZXIgaSwgYW5kIHNvIG9uLiBGb3IgZWFjaCBkaWFtb25kLCB0aGUgbW9kZWwgd2lsbCBtYWtlIGFuIGVycm9yLCBhbHNvIGluZGV4ZWQgYnkgaS4gTm90ZSB0aGF0IHRoZSBjb2VmZmljaWVudHMgJGJfe3h4eH0kIGFyZSBub3QgaW5kZXhlZCBieSBpOiB0aGV5IHdpbGwgYmUgY29tbW9uIHRvIGFsbCBkaWFtb25kcy4KClRoZSBrZXkgcXVlc3Rpb24gbm93IGlzOiBob3cgZG8gd2UgZGV0ZXJtaW5lIHRoZXNlICoqY29lZmZpY2llbnRzKio/CgpUaGUgYW5zd2VyIGlzIHNpbXBsZTogd2Ugd2FudCB0byBtYWtlIHRoZSBzbWFsbGVzdCBlcnJvcnMgYXMgcG9zc2libGUhIEEgc2ltcGxlIG9iamVjdGl2ZSB3b3VsZCBiZSB0byBtaW5pbWl6ZSB0aGUgc3VtIG9mIGVycm9ycy4gVGhpcyBpcyBub3QgYSBnb29kIGlkZWEgYmVjYXVzZSBwb3NpdGl2ZSBlcnJvcnMgd291bGQgb2Zmc2V0IG5lZ2F0aXZlIGVycm9ycyAoaS5lLiBpZiB3ZSBvdmVycHJpY2Ugb3IgdW5kZXJwcmljZSB0aGUgZGlhbW9uZHMpLiBJbnN0ZWFkLCBpdCBpcyBtb3JlIHJlbGV2YW50IHRvICoqbWluaW1pemUgdGhlIHN1bSBvZiBzcXVhcmVkIGVycm9ycyoqOgoKJCRcdW5kZXJzZXR7Yl97eHh4fX17XHRleHR7bWlufX0gXCBcc3VtX3tpPTF9Xk4oZXJyb3JfaSleMiQkCgpSZW1lbWJlciB0aGF0IHRoZSBlcnJvcnMgZGVwZW5kIGRpcmVjdGx5IG9uIHRoZSAkYl97eHh4fSQgbnVtYmVycy4gCgojIyBTb21lIHByYWN0aWNlCgpTaW1wbGUgbGluZWFyIG1vZGVscyBhcmUgb2J0YWluZWQgaW4gUiB2aWEgdGhlIGZ1bmN0aW9uIGxtKCkuIFRoZSBzeW50YXggaXMgYSBpdCBzdHJhbmdlIGF0IGZpcnN0IGJlY2F1c2Ugb2YgdGhlIHRpbGRlIH4sIGJ1dCB2ZXJ5IHJlY3VycmVudCBpbiBvdGhlciBzdGF0aXN0aWNhbCBwYWNrYWdlcy4gRmlyc3QsIHdlIGRpZ2l0aXplIHRoZSBkaWFtb25kcyBkYXRhYmFzZS4gRm9yIHRlY2huaWNhbCByZWFzb25zLCB3ZSBhbHNvIGRpdmlkZSB0aGUgcHJpY2Ugb2YgZGlhbW9uZHMgYnkgMSwwMDAuIE1hY2hpbmUgbGVhcm5pbmcgYWxnb3JpdGhtcyBwcmVmZXIgd2hlbiBudW1iZXJzIGhhdmUgKipob21vZ2VuZW91cyBtYWduaXR1ZGVzKiogYW5kIGFyZSBwb3NzaWJseSBub3QgdG9vIGJpZy4KCmBgYHtyLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0KbGlicmFyeSh0aWR5dmVyc2UpCmRpYW1zIDwtIGRpYW1vbmRzICU+JQogICAgc2VsZWN0KHByaWNlLCBjYXJhdCwgY3V0LCBjb2xvciwgY2xhcml0eSkgJT4lCiAgICBtdXRhdGVfaWYoaXMuZmFjdG9yLCBhcy5udW1lcmljKSAlPiUKICAgIG11dGF0ZShwcmljZSA9IHByaWNlIC8gMTAwMCkKaGVhZChkaWFtcykKYGBgCgpXZSBjb25maXJtIHRoYXQgYWxsIHZhcmlhYmxlcyBhcmUgbnVtZXJpY2FsLiAgIApXZSBjYW4gdGhlbiBwcm9jZWVkIHRvIHRoZSByZWdyZXNzaW9uLgoKYGBge3J9CmxtKHByaWNlIH4gY2FyYXQgKyBjdXQgKyBjb2xvciArIGNsYXJpdHksIGRhdGEgPSBkaWFtcykKYGBgCgpUaGUgKEludGVyY2VwdCkgaXMgdGhlIGNvbnN0YW50ICRiJC4gVGhlIG1vZGVsIGlzIHRodXM6CgokJHByaWNlX2kgPSAtNC42NiAgKyA4Ljc4IFx0aW1lcyBjYXJhdF9pICsgMC4xNiBcdGltZXMgY3V0X2ktMC4zMiBcdGltZXMgY29sb3JfaSArIDAuNTIgXHRpbWVzIGNsYXJpdHlfaSsgZXJyb3JfaSQkCgpCZXlvbmQgdGhpcyBzaW1wbGUgb3V0cHV0LCBtYW55IGludGVyZXN0aW5nIHF1YW50aXRpZXMgY2FuIGJlIGNvbXB1dGVkIHRoYXQgZnVydGhlciBjaGFyYWN0ZXJpemUgdGhlIHJlZ3Jlc3Npb24gb3V0cHV0ICgkUl4yJCwgJHQkLXN0YXRpc3RpY3MsICRwJC12YWx1ZXMsIGV0Yy4pLiBUbyBvYnRhaW4gdGhlbSwgaXQgc3VmZmljZXMgdG8gcGlwZSBhIHN1bW1hcnkuIEEgZGV0YWlsZWQgYW5hbHlzaXMgb2YgdGhlc2UgbnVtYmVycyBpcyBvdXQgb2YgdGhlIHNjb3BlIG9mIHRoaXMgaW50cm9kdWN0b3J5IHNlc3Npb24uCgpgYGB7cn0KbG0ocHJpY2UgfiBjYXJhdCArIGN1dCArIGNvbG9yICsgY2xhcml0eSwgZGF0YSA9IGRpYW1zKSAlPiUgc3VtbWFyeSgpCmBgYAoKTm93LCBsZXQgdXMgaW1hZ2luZSBhIHNtYWxsIGRpYW1vbmQsIHNheSB3aXRoIDAuNCBjYXJhdCwgYSBmYWlyIGN1dCwgYW5kIGNvbG9yIGNvZGUgb2YgMiBhbmQgYXZlcmFnZSBjbGFyaXR5IG9mIDMgKGNvcnJlc3BvbmRpbmcgdG8gU0kxKS4gTGV0IHVzIGNvbXB1dGUgdGhlIG1vZGVsIHZhbHVlIChhc3N1bWluZyB6ZXJvIGVycm9yKSBmb3IgdGhpcyBkaWFtb25kOgoKJCRwcmljZSA9IC00LjY2ICArIDguNzggXHRpbWVzIDAuNCArIDAuMTYgXHRpbWVzIDEtMC4zMiBcdGltZXMgMiArIDAuNTIgXHRpbWVzIDMgPSAtMC4wNywkJAoKdGhhdCBpczogdGhlIHByZWRpY3RlZCBwcmljZSBpcyBuZWdhdGl2ZS4gSHVtIGh1bS4uLi4gICAKTGluZWFyIHJlbGF0aW9uc2hpcHMgYXJlIHRvbyBsaW1pdGVkLiAgIApCdXQgaXQncyBwb3NzaWJsZSB0byBidWlsZCBtb2RlbHMgdGhhdCBhcmUgbW9yZSBjb21wbGV4Li4uIAoKCiMgTmV1cmFsIG5ldHdvcmtzCgojIyBJbnRyb2R1Y3Rpb24KCk9mdGVuLCBuZXVyYWwgbmV0d29ya3MgKE5OcykgYXJlIHJlcHJlc2VudGVkIHdpdGggZmlndXJlcyBsaWtlIHRoZSBvbmUgYmVsb3c6CgpgYGB7ciwgZWNobyA9IEZBTFNFLCBmaWcuYWxpZ249J2NlbnRlcid9CmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCJubi5wbmciKQpgYGAKClRoaXMgaXMgYSB2ZXJ5IHNpbXBsaXN0aWMgdmlldyBvZiB3aGF0IE5OcyBhcmUuIEluIGZhY3QsIGluIGVhY2ggY2lyY2xlLCB0aGVyZSBpcyBhIGxpbmVhciBtb2RlbCEgQW5kIGluIGJldHdlZW4gZGlmZmVyZW50IGNvbG9ycywgYSBub24tbGluZWFyIG1vZGVsIGlzIGFwcGxpZWQuIFRoZSBvdXRwdXQgZnJvbSB0aGUgYmx1ZSBtb2RlbHMgYXJlIGFsdGVyZWQgYW5kIHNlbnQgYXMgaW5wdXQgdG8gdGhlIGdyZWVuIGxpbmVhciBtb2RlbHMuIFRoZSBzYW1lIHByb2Nlc3MgaXMgcmUtaXRlcmF0ZWQgZnJvbSBncmVlbiB0byByZWQuIEVhY2ggY29sb3IgcmVwcmVzZW50cyB3aGF0IGlzIGNhbGxlZCAqKmEgbGF5ZXIqKi4gVGhlIG9yaWdpbmFsIGlucHV0IGlzIHRyYW5zZm9ybWVkIGFuZCBwYXNzZWQgdG8gbGF5ZXJzIHRvIHRoZSByaWdodCwgdW50aWwgaXQgcmVhY2hlcyB0aGUgbGFzdCBsYXllciwgd2hpY2ggaXMgc2ltcGx5IHRoZSBvdXRwdXQuCgpUaGUgZXhhY3Qgc3RydWN0dXJlIGlzIGRldGFpbGVkIGJlbG93IGZvciBhIHZlcnkgc21hbGwgbmV0d29yay4KCmBgYHtyLCBlY2hvID0gRkFMU0UsIGZpZy5hbGlnbj0nY2VudGVyJ30Ka25pdHI6OmluY2x1ZGVfZ3JhcGhpY3MoIk5OX3NjaGVtZS5wbmciKQpgYGAKCk5lZWRsZXNzIHRvIHNheTogTk5zIGNhbiBiZSB2ZXJ5IGNvbXBsaWNhdGVkIGZ1bmN0aW9ucyB3aXRoIGxvdHMgb2YgcGFyYW1ldGVycy4gSW4gbmV1cmFsIG5ldHdvcmtzLCB0aGUgcGFyYW1ldGVycyBhcmUgYWxsIHRoZSBjb2VmZmljaWVudHMgKGNhbGxlZCB3ZWlnaHRzKSBpbiBhbGwgbGluZWFyIHVuaXRzIGluIHRoZSBuZXR3b3JrLiAKClRoZSBjcnVjaWFsIHN0ZXAgaXMgdGh1cyB0byBmaW5kIHRoZSAqYmVzdCogcGFyYW1ldGVycywganVzdCBsaWtlIGZvciByZWdyZXNzaW9ucy4gCkp1c3QgbGlrZSBmb3IgcmVncmVzc2lvbiwgdGhlIG1vZGVsIHdpbGwgYWltIGF0IG1pbmltaXppbmcgdGhlIHN1bSBvZiBzcXVhcmVkIGVycm9ycy4gVGhpcyBxdWFudGl0eSBpcyBjYWxsZWQgdGhlIGxvc3MuCgpGaW5kaW5nIHRoZSBvcHRpbWFsIHBhcmFtZXRlcnMgZm9yIGEgY29tcGxleCBmdW5jdGlvbiBsaWtlIGEgTk4gY2Fubm90IGJlIGRvbmUgYXV0b21hdGljYWxseSBsaWtlIGZvciByZWdyZXNzaW9ucy4KVGhlIHByb2Nlc3MgdGhhdCBmaW5kcyBnb29kIHBhcmFtZXRlcnMgaXMgcHJvZ3Jlc3NpdmUsIGl0ZXJhdGl2ZS4gClRoZSBpZGVhIGlzIHRoZSBmb2xsb3dpbmc6CgpgYGB7ciwgZWNobyA9IEZBTFNFfQprbml0cjo6aW5jbHVkZV9ncmFwaGljcygiTmV3dG9uLnBuZyIpCmBgYApUaGUgYWltIGlzIHRvIHJlZHVjZSB0aGUgdG90YWwgZXJyb3IuIFNvIHdlIHVzZSB0aGUgZGVyaXZhdGl2ZSBhbmQgZm9sbG93IGl0IHRvIHJlYWNoIGEgbWluaW11bSBwb2ludC4gCgpUaGUgcHJvY2VzcyBpcyBjb21wbGljYXRlZCBhdCB0aGUgc2NhbGUgb2YgdGhlIHdob2xlIG5ldHdvcmsgYW5kIHJlbGllcyBvbiB0aGUgKipjaGFpbiBydWxlKiogZm9yIGRpZmZlcmVudGlhdGlvbi4KSXQgc3RhcnRzIGZyb20gdGhlIHJpZ2h0IG9mIHRoZSBuZXR3b3JrIGFuZCB0aGVuIGRpZmZ1c2VzIGJhY2sgcHJvZ3Jlc3NpdmVseSB0byB0aGUgZWFybHkgbm9kZXMgb2YgdGhlIG5ldHdvcmsuClRoYXQncyB3aHkgaXQncyBjYWxsZWQgKipiYWNrcHJvcGFnYXRpb24qKi4KCiMjIEV4YW1wbGU6IGRpYW1vbmRzCgpXZSBzaG93IGhvdyB0byBpbXBsZW1lbnQgTk5zIGluIFIgdmlhIHRoZSBrZXJhcyBwYWNrYWdlLiAKQnV0IGZpcnN0LCB3ZSBtdXN0IHByZXBhcmUgdGhlIGRhdGEuCgpgYGB7cn0KZXZlbiA8LSAyKigxOjIwMDAwKSAgICAgICAgICAgICAgICAgICAjIEV2ZW4gbnVtYmVycwpvZGQgPC0gZXZlbiArIDEgICAgICAgICAgICAgICAgICAgICAgICMgT2RkIG51bWJlcnMKZGlhbV90cmFpbiA8LSBkaWFtc1tldmVuLF0gICAgICAgICAgICAjIFRyYWluaW5nIHNldAp0cmFpbl9sYWJlbCA8LSBkaWFtX3RyYWluJHByaWNlICAgICAgICMgVHJhaW5pbmcgbGFiZWwKdHJhaW5fZmVhdHVyZXMgPC0gZGlhbV90cmFpbiAlPiUgICAgICAjIFRyYWluaW5nIGZlYXR1cmVzCiAgc2VsZWN0KC1wcmljZSkgJT4lCiAgYXMubWF0cml4KCkKZGlhbV90ZXN0IDwtIGRpYW1zW29kZCxdICAgICAgICAgICAgICAjIFRlc3Rpbmcgc2FtcGxlCnRlc3RfbGFiZWwgPC0gZGlhbV90ZXN0JHByaWNlICAgICAgICAgIyBUZXN0aW5nIGxhYmVsCnRlc3RfZmVhdHVyZXMgPC0gZGlhbV90ZXN0ICU+JSAgICAgICAgIyBUZXN0aW5nIGZlYXR1cmVzCiAgc2VsZWN0KC1wcmljZSkgJT4lCiAgYXMubWF0cml4KCkKYGBgCgpUaGUgY29uc3RydWN0aW9uIG9mIHRoZSBuZXR3b3JrIHJlcXVpcmVzIDMgc3RlcHM6ICAgCjEuIERlZmluaXRpb24gb2YgdGhlIHN0cnVjdHVyZSBvZiB0aGUgbmV0d29yayAodW5tYmVyIG9mIGxheWVycyAmIHVuaXRzIHBlciBsYXllcikgICAgCjIuIFNldHRpbmcgb2YgdGhlIGxvc3MgZnVuY3Rpb24gYW5kIGxlYXJuaW5nIHByb2Nlc3MgICAgCjMuIFRyYWluaW5nIGJ5IHNwZWNpZnlpbmcgdGhlIGJhdGNoIHNpemVzIGFuZCBudW1iZXIgb2Ygcm91bmRzICAgCgpUaGUgKipiYXRjaCBzaXplKiogaXMgaG93IG1hbnkgaW5zdGFuY2VzIGFyZSB1c2VkIHRvIGNvbXB1dGUgZ3JhZGllbnRzIGluIHRoZSBiYWNrcHJvcCAoYXQgYSB0aW1lKS4gVGhlIG51bWJlciBvZiAqKnJvdW5kcyoqIGlzIGhvdyBtYW55IHRpbWVzIHRoZSBiYWNrcHJvcCBzZWVzIHRoZSB3aG9sZSB0cmFpbmluZyBzYW1wbGUuCgpUaGUgbGluZXMgYmVsb3cgcmVseSBvbiAqKktlcmFzKiosIGEgZGVlcCBsZWFybmluZyBmcmFtZXdvcmsgb3JpZ2luYWxseSBjb2RlZCBpbiBQeXRob24uIFRoZXkgcmVxdWlyZSBhIFB5dGhvbiBpbnN0YWxsYXRpb24gYXMgd2VsbCBhcyB0aGUga2VyYXMgcGFja2FnZSwgc2VlIHRoZSBpbnN0YWxsYXRpb24gc2VjdGlvbiBvZiBodHRwczovL2tlcmFzLnJzdHVkaW8uY29tLgoKYGBge3IsIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFfQpsaWJyYXJ5KGtlcmFzKQojIGluc3RhbGxfa2VyYXMoKSAjIFRvIGNvbXBsZXRlIGluc3RhbGxhdGlvbgptb2RlbCA8LSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkKbW9kZWwgJT4lICAgIyBUaGlzIGRlZmluZXMgdGhlIHN0cnVjdHVyZSBvZiB0aGUgbmV0d29yaywgaS5lLiBob3cgbGF5ZXJzIGFyZSBvcmdhbml6ZWQKICAgIGxheWVyX2RlbnNlKHVuaXRzID0gMTYsIGFjdGl2YXRpb24gPSAncmVsdScsIGlucHV0X3NoYXBlID0gbmNvbCh0cmFpbl9mZWF0dXJlcykpICU+JQogICAgbGF5ZXJfZGVuc2UodW5pdHMgPSA4LCBhY3RpdmF0aW9uID0gJ3NpZ21vaWQnKSAlPiUKICAgIGxheWVyX2RlbnNlKHVuaXRzID0gMSkgIyBObyBhY3RpdmF0aW9uIG1lYW5zIGxpbmVhciBhY3RpdmF0aW9uOiBmKHgpID0geC4KYGBgCgpXZSBjYW4gcGxvdCB0aGlzIGFyY2hpdGVjdHVyZSB2aWEgdG9vbHMgc3VjaCBhczogaHR0cDovL2FsZXhsZW5haWwubWUvTk4tU1ZHL2luZGV4Lmh0bWwuCgoKYGBge3J9Cm1vZGVsICU+JSBjb21waWxlKCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBNb2RlbCBzcGVjaWZpY2F0aW9uCiAgICBsb3NzID0gJ21lYW5fc3F1YXJlZF9lcnJvcicsICAgICAgICAgICAgICAgIyBMb3NzIGZ1bmN0aW9uCiAgICBvcHRpbWl6ZXIgPSBvcHRpbWl6ZXJfcm1zcHJvcCgpLCAgICAgICAgICAgIyBPcHRpbWlzYXRpb24gbWV0aG9kICh3ZWlnaHQgdXBkYXRpbmcpCiAgICBtZXRyaWNzID0gYygnbWVhbl9hYnNvbHV0ZV9lcnJvcicpICAgICAgICAgIyBPdXRwdXQgbWV0cmljCikKc3VtbWFyeShtb2RlbCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIE1vZGVsIGFyY2hpdGVjdHVyZQpgYGAKCmBgYHtyLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRX0KZml0X05OIDwtIG1vZGVsICU+JSAKICAgIGZpdCh0cmFpbl9mZWF0dXJlcywgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRyYWluaW5nIGZlYXR1cmVzCiAgICAgICAgdHJhaW5fbGFiZWwsICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBUcmFpbmluZyBsYWJlbHMKICAgICAgICBlcG9jaHMgPSA1MCwgYmF0Y2hfc2l6ZSA9IDUxMiwgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRyYWluaW5nIHBhcmFtZXRlcnMKICAgICAgICB2YWxpZGF0aW9uX2RhdGEgPSBsaXN0KHRlc3RfZmVhdHVyZXMsIHRlc3RfbGFiZWwpLCAgICAgICAjIFRlc3QgZGF0YQogICAgICAgIHZlcmJvc2UgPSAwICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgTm8gbWVzc2FnZXMKICAgICAgICApIApwbG90KGZpdF9OTikgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgUGxvdCwgZXZpZGVudGx5IQpgYGAKCgpMZXQncyB0ZXN0IHRoZSBtb2RlbCBvbiB0aGUgZmFrZSBkaWFtb25kIG1lbnRpb25lZCBiZWZvcmUgKDAuNCBjYXJhdCwgMSBjdXQsIDIgY29sb3IsIDMgY2xhcml0eSk6CgpgYGB7cn0KZXhhbXBsZSA8LSBjKDAuNCwgMSwgMiwgMykgJT4lIHQoKSAgIyBUcmFuc3Bvc2UgZm9yIHRlY2huaWNhbCByZWFzb24KcHJlZGljdChtb2RlbCwgZXhhbXBsZSkKYGBgCgojIyBFeGFtcGxlOiBwcmVkaWN0aW5nIHNvbmcgcG9wdWxhcml0eQoKUmVjeWNsaW5nIGEgbW9kZWwgc3RydWN0dXJlIGlzIHZlcnkgZWFzeSEgTGV0J3MgdHJ5IHRoaXMgb24gdGhlIHNvbmdzIGRhdGFzZXQuIEZpcnN0LCB3ZSBpbXBvcnQgdGhlIGRhdGEgYW5kIG5vcm1hbGl6ZSBzb21lIGNvbHVtbnMuCgpgYGB7cn0KbG9hZCgic29uZ3MuUkRhdGEiKQpzb25ncyA8LSBzb25ncyAlPiUKICBtdXRhdGUoZHVyYXRpb24gPSBkdXJhdGlvbiAvIDYwLAogICAgICAgICBwb3B1bGFyaXR5ID0gcG9wdWxhcml0eSAvIDEwMCwKICAgICAgICAgdGVtcG8gPSB0ZW1wbyAvIDEwMCkKYGBgCgpMZXQncyBoYXZlIGEgbG9vayBhdCB0aGUgZmlyc3Qgcm93LgoKYGBge3J9CnNvbmdzWzEsXQpgYGAKV2Ugd2FudCB0byBiZSBhYmxlIHRvIHByZWRpY3QgdGhpcyBwb3B1bGFyaXR5IG9mIDczIHdpdGggYSBuZXVyYWwgbmV0d29yay4gTGV0J3MgZ28hCldlIGJ1aWxkIHRoZSBtb2RlbCBvbiBhbGwgc29uZ3MgZXhjZXB0IHRoZSBmaXJzdCBvbmUuIEZpcnN0LCB3ZSBjb25zdHJ1Y3QgdGhlIHRyYWluaW5nIGRhdGEuCgpgYGB7ciwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9CmZlYXR1cmVfc29uZ3MgPC0gYygiZHVyYXRpb24iLCAiZGFuY2VhYmlsaXR5IiwgImVuZXJneSIsICJsb3VkbmVzcyIsICJzcGVlY2hpbmVzcyIsICJ0ZW1wbyIsICJ2YWxlbmNlIikKdHJhaW5fc29uZ3MgPC0gc29uZ3NbMjoxMzA3MCxdCnNvbmdzX2ZlYXR1cmVzIDwtIHRyYWluX3NvbmdzICU+JQogIHNlbGVjdChmZWF0dXJlX3NvbmdzKSAlPiUKICBhcy5tYXRyaXgoKQpzb25nc19sYWJlbCA8LSB0cmFpbl9zb25ncyRwb3B1bGFyaXR5IApgYGAKCk5leHQsIHdlIHJlYnVpbGQgdGhlIG1vZGVsLiAKCmBgYHtyfQptb2RlbDIgPC0ga2VyYXNfbW9kZWxfc2VxdWVudGlhbCgpCm1vZGVsMiAlPiUgICAjIFRoaXMgZGVmaW5lcyB0aGUgc3RydWN0dXJlIG9mIHRoZSBuZXR3b3JrLCBpLmUuIGhvdyBsYXllcnMgYXJlIG9yZ2FuaXplZAogICAgbGF5ZXJfZGVuc2UodW5pdHMgPSAxNiwgYWN0aXZhdGlvbiA9ICdyZWx1JywgaW5wdXRfc2hhcGUgPSBsZW5ndGgoZmVhdHVyZV9zb25ncykpICU+JSAjIFRoZSBvcmlnbmFsIHNpemUgaXMgZGlmZmVyZW50CiAgICBsYXllcl9kZW5zZSh1bml0cyA9IDgsIGFjdGl2YXRpb24gPSAnc2lnbW9pZCcpICU+JQogICAgbGF5ZXJfZGVuc2UodW5pdHMgPSAxKSAjIE5vIGFjdGl2YXRpb24gbWVhbnMgbGluZWFyIGFjdGl2YXRpb246IGYoeCkgPSB4LgoKbW9kZWwyICU+JSBjb21waWxlKCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBNb2RlbCBzcGVjaWZpY2F0aW9uCiAgICBsb3NzID0gJ21lYW5fc3F1YXJlZF9lcnJvcicsICAgICAgICAgICAgICAgIyBMb3NzIGZ1bmN0aW9uCiAgICBvcHRpbWl6ZXIgPSBvcHRpbWl6ZXJfcm1zcHJvcCgpLCAgICAgICAgICAgIyBPcHRpbWlzYXRpb24gbWV0aG9kICh3ZWlnaHQgdXBkYXRpbmcpCiAgICBtZXRyaWNzID0gYygnbWVhbl9hYnNvbHV0ZV9lcnJvcicpICAgICAgICAgIyBPdXRwdXQgbWV0cmljCikKc3VtbWFyeShtb2RlbDIpICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBNb2RlbCBhcmNoaXRlY3R1cmUKYGBgCgpUaGVyZSBhcmUgbW9yZSBwYXJhbWV0ZXJzIGJlY2F1c2UgdGhlIG9yaWdpbmFsIGRhdGEgaGFzIDcgY29sdW1ucyBhbmQgbm90IDQuIApOb3cgbGV0J3MgdHVybiB0byB0aGUgYWN0dWFsIGxlYXJuaW5nOiBkb24ndCBmb3JnZXQgdG8gY2hhbmdlIHRoZSBpbnB1dHMuCgpgYGB7cn0KZml0X05OMiA8LSBtb2RlbDIgJT4lIAogICAgZml0KHNvbmdzX2ZlYXR1cmVzLCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVHJhaW5pbmcgZmVhdHVyZXMKICAgICAgICBzb25nc19sYWJlbCwgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAjIFRyYWluaW5nIGxhYmVscwogICAgICAgIGVwb2NocyA9IDMwLCBiYXRjaF9zaXplID0gMjU2LCAgICAgICAgICAgICAgICAgICAgICAgICAgICMgVHJhaW5pbmcgcGFyYW1ldGVycwogICAgICAgIHZhbGlkYXRpb25fZGF0YSA9IGxpc3Qoc29uZ3NfZmVhdHVyZXMsIHNvbmdzX2xhYmVsKSwgICAgICMgVGVzdCBkYXRhCiAgICAgICAgdmVyYm9zZSA9IDAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBObyBtZXNzYWdlcwogICAgICAgICkgCnBsb3QoZml0X05OMikgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyBQbG90LCBldmlkZW50bHkhCmBgYAoKCgpgYGB7cn0KcHJlZGljdChtb2RlbDIsIHNvbmdzWzEsXSAlPiUgc2VsZWN0KGZlYXR1cmVfc29uZ3MpICU+JSBhcy5tYXRyaXgoKSkKYGBgCgpUaGUgbnVtYmVyIGlzIG5vdCBncmVhdC4gSW4gYWRkaXRpb24sIGl0J3MgcmFuZG9tLiBCZWNhdXNlIHRoZSBvcmlnaW5hbCB3ZWlnaHRzIGFyZSBkZXRlcm1pbmVkIHJhbmRvbWx5LgoKRm9yIGRpYW1vbmRzLCB0aGUgTk4gd29yayB3ZWxsIGJlY2F1c2UgdGhlIHZhcmlhYmxlcyBoYXZlIGFuIG9idmlvdXMgZGlyZWN0IGltcGFjdCBvbiB0aGUgcHJpY2U6IHNpemUsIHB1cml0eSwgZXRjLiAgIApGb3Igc29uZ3MsIHRoaXMgaXMgbm90IG9idmlvdXMuIEhlbmNlLCB0aGUgbG93ZXIgcHJlY2lzaW9uLiAKCmBgYHtyfQoKYGBgCgo=