In this notebook1, we’ll take a look at how how CNNs interpret images from a visual perspective. There are several approaches one could take but we’ll look at the following three:

For the first method, activation visualization, we’ll use the small CNN that we trained from scratch in the cat vs. dog module. For the other two methods, we will use the VGG16 model that we introduced in the CNN Transfer learning notebook.

Required packages

# Initialize package
library(keras)
library(tensorflow)
library(grid)         # for producing section 1 & 2 images
library(gridExtra)    # for producing section 1 & 2 images
library(magick)       # for producing section 3 images
library(viridis)      # for producing section 3 images
library(lime)         # for producing section 3 images

# We disable eager execution to extract the gradients later on. This isn't
# required as we could also get gradients with tf$GradientTape. See this
# discussion for details https://github.com/rstudio/keras/issues/945
tf$compat$v1$disable_eager_execution()

Visualizing intermediate activations

Visualizing intermediate activations consists of displaying the feature maps that are output by various convolution and pooling layers in a network. This gives a view into how an input is decomposed unto the different filters learned by the network. These feature maps we want to visualize have 3 dimensions: width, height, and depth (aka channels). Each channel encodes relatively independent features, so the proper way to visualize these feature maps is by independently plotting the contents of every channel, as a 2D image. Let’s start by loading the model that we saved in the cat vs. dog module.

file_local <- here::here("materials", "04-computer-vision-CNNs", "cats_and_dogs_small_2.h5")
model <- load_model_hdf5(file_local)
model
Model
Model: "sequential"
__________________________________________________________________________________________________
Layer (type)                                Output Shape                           Param #        
==================================================================================================
conv2d (Conv2D)                             (None, 148, 148, 32)                   896            
__________________________________________________________________________________________________
max_pooling2d (MaxPooling2D)                (None, 74, 74, 32)                     0              
__________________________________________________________________________________________________
conv2d_1 (Conv2D)                           (None, 72, 72, 64)                     18496          
__________________________________________________________________________________________________
max_pooling2d_1 (MaxPooling2D)              (None, 36, 36, 64)                     0              
__________________________________________________________________________________________________
conv2d_2 (Conv2D)                           (None, 34, 34, 128)                    73856          
__________________________________________________________________________________________________
max_pooling2d_2 (MaxPooling2D)              (None, 17, 17, 128)                    0              
__________________________________________________________________________________________________
conv2d_3 (Conv2D)                           (None, 15, 15, 128)                    147584         
__________________________________________________________________________________________________
max_pooling2d_3 (MaxPooling2D)              (None, 7, 7, 128)                      0              
__________________________________________________________________________________________________
flatten (Flatten)                           (None, 6272)                           0              
__________________________________________________________________________________________________
dropout (Dropout)                           (None, 6272)                           0              
__________________________________________________________________________________________________
dense (Dense)                               (None, 512)                            3211776        
__________________________________________________________________________________________________
dense_1 (Dense)                             (None, 1)                              513            
==================================================================================================
Total params: 3,453,121
Trainable params: 3,453,121
Non-trainable params: 0
__________________________________________________________________________________________________

This will be the input image we will use – a picture of a dog, not part of images that the network was trained on. This image is particularly interesting because it also has a picture of a human but if you were to predict the class of this image our model correctly predicts a dog.

# Preprocesses the image into a 4D tensor
img_path <- here::here("materials", "data", "dogs-vs-cats", "test", "dogs", "dog.1508.jpg")
img <- image_load(img_path, target_size = c(150, 150))
img_tensor <- image_to_array(img)
img_tensor <- array_reshape(img_tensor, c(1, 150, 150, 3))
img_tensor <- img_tensor / 255

dim(img_tensor)
[1]   1 150 150   3
plot(as.raster(img_tensor[1,,,]))

In order to extract the feature maps you want to look at, you’ll create a Keras model that takes batches of images as input, and outputs the activations of all convolution and pooling layers. To do this, we will use the keras_model() function (recall keras_model() was introduced in the collaborative filtering notebook.

layer_outputs <- lapply(model$layers[1:8], function(layer) layer$output)
activation_model <- keras_model(inputs = model$input, outputs = layer_outputs)

When fed an image input, this model returns the activation output values for each of the 8 hidden layers in the convolution section of our model.

activations <- activation_model %>% predict(img_tensor)

For instance, this is the activation of the first convolution layer for our dog image. Note how the dimension align to the dimensions of the first layer in our CNN model.

first_layer_activation <- activations[[1]]
dim(first_layer_activation)
[1]   1 148 148  32

It’s a 148 x 148 feature map with 32 channels. Let’s visualize some of these channels.

plot_channel <- function(channel) {
  rotate <- function(x) t(apply(x, 2, rev))
  image(rotate(channel), axes = FALSE, asp = 1,
        col = terrain.colors(12))
}

The 20th channel seems to capture the outline of the dog and also the person’s face.

plot_channel(first_layer_activation[1,,,20])

The 28th channel seems to outline some of the other features in the image ( i.e. window panels).

plot_channel(first_layer_activation[1,,,28])

We can go ahead and create images for each channel in each of the 8 layers of our convolution part of our model. The following will create a new subdirectory, plot every channel in each of our 8 activation maps, stack the results in one big image tensor, with channels stacked side-by-side plot, and save them in the new directory.

dir.create("dog_activations")
image_size <- 58
images_per_row <- 16
for (i in 1:8) {
  
  layer_activation <- activations[[i]]
  layer_name <- model$layers[[i]]$name
 
  n_features <- dim(layer_activation)[[4]]
  n_cols <- n_features %/% images_per_row
 
  png(paste0("dog_activations/", i, "_", layer_name, ".png"), 
      width = image_size * images_per_row, 
      height = image_size * n_cols)
  op <- par(mfrow = c(n_cols, images_per_row), mai = rep_len(0.02, 4))
  
  for (col in 0:(n_cols - 1)) {
    for (row in 0:(images_per_row - 1)) {
      channel_image <- layer_activation[1,,,(col*images_per_row) + row + 1]
      plot_channel(channel_image)
    }
  }
  
  par(op)
  dev.off()
}

You should now have plots visualizing the first 8 feature channels:

  1. 1_conv2d.png
  2. 2_max_pooling2d.png
  3. 3_conv2d_1.png
  4. 4_max_pooling2d_1.png
  5. 5_conv2d_2.png
  6. 6_max_pooling2d_2.png
  7. 7_conv2d_3.png
  8. 8_max_pooling2d_3.png

The following plots the feature maps in the first layer and then the final 8th layer. Note how the final layer is very abstract to human eyes…but it has a lot of mathematical information interpretable by our CNN model. The activations of layers higher-up carry less and less information about the specific input being seen, and more and more information about the target (in our case, the class of the image: cat or dog).

knitr::include_graphics("dog_activations/1_conv2d.png")

knitr::include_graphics("dog_activations/8_max_pooling2d_3.png")

Visualizing CNN filters:

Another easy thing to do to inspect the filters learned by convnets is to display the visual pattern that each filter is meant to respond to. This can be done with gradient ascent in input space: applying gradient descent to the value of the input image of a convnet so as to maximize the response of a specific filter, starting from a blank input image. The resulting input image would be one that the chosen filter is maximally responsive to.

The process is simple: we will build a loss function that maximizes the value of a given filter in a given convolution layer, then we will use stochastic gradient descent to adjust the values of the input image so as to maximize this activation value. For instance, here’s a loss for the activation of filter 0 in the layer “block3_conv1” of the VGG16 network, pre-trained on ImageNet:

model <- application_vgg16(
  weights = "imagenet",
  include_top = FALSE
  )

layer_name <- "block3_conv1"
filter_index <- 1
layer_output <- get_layer(model, layer_name)$output
loss <- k_mean(layer_output[,,,filter_index])

To implement gradient descent, we will need the gradient of this loss with respect to the model’s input. To do this, we will use the k_gradients() Keras backend function. In TF 2.0 a change was made where k_gradients() can only be ran when eager execution is turned off, which is why we ran tf$compat$v1$disable_eager_execution() at the top of the script. See https://github.com/rstudio/keras/issues/945 for more details.

# The call to k_gradients returns an R list of tensors (of size 1 in this case). 
# Hence, you keep only the first element—which is a tensor.
grads <- k_gradients(loss, model$input)[[1]]

A non-obvious trick to use for the gradient descent process to go smoothly is to normalize the gradient tensor, by dividing it by its L2 norm (the square root of the average of the square of the values in the tensor). This ensures that the magnitude of the updates done to the input image is always within a same range.

# Add 1e-5 before dividing to avoid accidentally dividing by 0
grads <- grads / (k_sqrt(k_mean(k_square(grads))) + 1e-5)

Now you need a way to compute the value of the loss tensor and the gradient tensor, given an input image. You can define a Keras backend function to do this: iterate() is a function that takes a tensor (as a list of tensors of size 1) and returns a list of two tensors: the loss value and the gradient value.

iterate <- k_function(list(model$input), list(loss, grads))
c(loss_value, grads_value) %<-% iterate(list(array(0, dim = c(1, 150, 150, 3))))

At this point we can define an R loop to do stochastic gradient descent:

# Starts from a gray image with some noise
input_img_data <- array(runif(150 * 150 * 3), dim = c(1, 150, 150, 3)) * 20 + 128

# Runs gradient ascent for 40 step
step <- 1
for (i in 1:40) { 
  # Computes the loss value and gradient value
  c(loss_value, grads_value) %<-% iterate(list(input_img_data))
  
  # Adjusts the input image in the direction that maximizes the loss
  input_img_data <- input_img_data + (grads_value * step)  
}

The resulting image tensor is a floating-point tensor of shape (1, 150, 150, 3), with values that may not be integers within [0, 255]. Hence you need to post-process this tensor to turn it into a displayable image. You do so with the following straightforward utility function.

deprocess_image <- function(x) {
  dms <- dim(x)

    # Normalizes the tensor: centers on 0., ensures that std is 0.1
  x <- x - mean(x)
  x <- x / (sd(x) + 1e-5)
  x <- x * 0.1
  
  # Clips to [0, 1]
  x <- x + 0.5
  x <- pmax(0, pmin(x, 1))
  
  # Returns with the original image dimensions
  array(x, dim = dms)
}

Now you have all the pieces. Let’s put them together into an R function that takes as input a layer name and a filter index, and returns a valid image tensor representing the pattern that maximizes the activation of the specified filter.

generate_pattern <- function(layer_name, filter_index, size = 150) {
  
  # Builds a loss function that maximizes the activation of the nth filter of the layer under consideration
  layer_output <- model$get_layer(layer_name)$output
  loss <- k_mean(layer_output[,,,filter_index])
  
  # Computes the gradient of the input picture with regard to this loss
  grads <- k_gradients(loss, model$input)[[1]]
  
  # Normalization trick: normalizes the gradient
  grads <- grads / (k_sqrt(k_mean(k_square(grads))) + 1e-5)
  
  # Returns the loss and grads given the input picture
  iterate <- k_function(list(model$input), list(loss, grads))
  
  # Starts from a gray image with some noise
  input_img_data <-
  array(runif(size * size * 3), dim = c(1, size, size, 3)) * 20 + 128

  # Runs gradient ascent for 40 steps
  step <- 1
  for (i in 1:40) {
    c(loss_value, grads_value) %<-% iterate(list(input_img_data))
    input_img_data <- input_img_data + (grads_value * step)
    }
  
  img <- input_img_data[1,,,]
  deprocess_image(img)
  }

Now we can start visualizing every single filter in every layer. For simplicity, we will only look at the first 64 filters in each layer, and will only look at the first layer of the following convolution blocks: block1_conv1, block2_conv1, block3_conv1, block4_conv1. We will arrange the outputs on a 8x8 grid of filter patterns.

layers <- c("block1_conv1", "block2_conv1", "block3_conv1", "block4_conv1")
dir.create("vgg_filters")

for (layer_name in layers) {
size <- 140
  png(paste0("vgg_filters/", layer_name, ".png"),
      width = 8 * size, height = 8 * size)
  grobs <- list()
  for (i in 0:7) {
    for (j in 0:7) {
      pattern <- generate_pattern(layer_name, i + (j*8) + 1, size = size)
      grob <- rasterGrob(pattern,
                         width = unit(0.9, "npc"),
                   height = unit(0.9, "npc"))
      grobs[[length(grobs) + 1]] <- grob
    }
    }
  grid.arrange(grobs = grobs, ncol = 8)
  dev.off()
}

The previous code results in a new directory /vgg_filters that contains four images. Below is the image for the first CNN block filter and the second image is the fourth block. These filter visualizations tell you a lot about how CNN layers see the world: each layer in a CNN learns a collection of filters such that their inputs can be expressed as a combination of the filters. You can see that earlier filters (i.e. block1_conv1) encode more simple directional edges and colors whereas later filters (i.e. block4_conv1) start to resemble textures found in natural images (i.e. eyes, feathers, balls).

knitr::include_graphics(c("vgg_filters/block1_conv1.png", "vgg_filters/block4_conv1.png"))

Visualizing heatmaps of class activation

This last technique demonstrates how to highlight the parts of an image that is likely to be the most important in how the model classified the image. For example, in our dog image, which contains a human, we can see that our model classifies the image, with 0.89 probability, as a dog (in this model the target is encoded as 0-cat and 1-dog). So one question may arise, what about this image causes our model to predict this? What pixels in the image are most relevant?

# predicting dog picture
predict(model, img_tensor)
          [,1]
[1,] 0.8906708

Manual class activation map

A class-activation heatmap is a 2D grid of scores associated with a specific output class, computed for every location in any input image, indicating how important each location is with respect to the class under consideration. For instance, given an image fed into a cat-versus-dog CNN, CAM visualization allows you to generate a heatmap for the class “cat,” indicating how cat-like different parts of the image are, and also a heatmap for the class “dog,” indicating how dog-like parts of the image are.

The specific implementation you’ll use is the one described in “Grad-CAM: Visual Explanations from Deep Networks via Gradient-based Localization.”footnote:[Ramprasaath R. Selvaraju et al., Cornell University Library, March 21, 2017, https://arxiv.org/abs/1610.02391.]. It consists of taking the output feature map of a convolution layer, given an input image, and weighing every channel in that feature map by the gradient of the class with respect to the channel. Intuitively, one way to understand this trick is that you’re weighting a spatial map of “how intensely the input image activates different channels” by “how important each channel is with regard to the class,” resulting in a spatial map of “how intensely the input image activates the class.”

Let’s demonstrate with our dog image.

# This is the prediction vector for our dog
dog_output <- model$output[, 1]

# The is the output feature map of the `conv2d_3` layer, the last
# convolutional layer in our Cats vs Dogs model that we imported earlier
last_conv_layer <- model %>% get_layer("conv2d_3")

# This is the gradient of the "dog" class with regard to the output
# feature map of `conv2d_3`
grads <- k_gradients(dog_output, last_conv_layer$output)[[1]]

# This is a vector of shape (128,), where each entry is the mean
# intensity of the gradient over a specific feature map channel
pooled_grads <- k_mean(grads, axis = c(1, 2, 3))

# This function allows us to access the values of the quantities we just defined:
# `pooled_grads` and the output feature map of `conv2d_3`,
# given a sample image
iterate <- k_function(list(model$input),
                      list(pooled_grads, last_conv_layer$output[1,,,]))

# These are the values of these two quantities, as arrays,
# given our sample image of two elephants
c(pooled_grads_value, conv_layer_output_value) %<-% iterate(list(img_tensor))

# We multiply each channel in the feature map array by
# "how important this channel is" with regard to the dog class
for (i in 1:128) {
  conv_layer_output_value[,,i] <- 
    conv_layer_output_value[,,i] * pooled_grads_value[[i]] 
}

# The channel-wise mean of the resulting feature map
# is our heatmap of class activation
heatmap <- apply(conv_layer_output_value, c(1,2), mean)

We can now create the heatmap and save it to disk for later. Note that the heatmap width and height need to be the same as our preprocessed image, which we cropped to 150x150.

heatmap <- pmax(heatmap, 0) 
heatmap <- heatmap / max(heatmap)
write_heatmap <- function(heatmap, filename, width = 150, height = 150,
                          bg = "white", col = terrain.colors(12)) {
  png(filename, width = width, height = height, bg = bg)
  op = par(mar = c(0,0,0,0))
  on.exit({par(op); dev.off()}, add = TRUE)
  rotate <- function(x) t(apply(x, 2, rev))
  image(rotate(heatmap), axes = FALSE, asp = 1, col = col)
}
write_heatmap(heatmap, "dog_heatmap.png") 
knitr::include_graphics("dog_heatmap.png")

Now we can use the magick package to generate an image that superimposes the original image with the heatmap we just obtained. We can see that the heatmap is focused on the dogs face and, more specifically, on the left eye and upper part of the snout of the dog.

library(magick) 
library(viridis) 
# Read the original elephant image and it's geometry
image <- image_read(img_path)
info <- image_info(image) 
geometry <- sprintf("%dx%d!", info$width, info$height) 
# Create a blended / transparent version of the heatmap image
pal <- col2rgb(viridis(20), alpha = TRUE) 
alpha <- floor(seq(0, 255, length = ncol(pal))) 
pal_col <- rgb(t(pal), alpha = alpha, maxColorValue = 255)
write_heatmap(heatmap, "dog_overlay.png", 
              width = 14, height = 14, bg = NA, col = pal_col) 
# Overlay the heatmap
image_read("dog_overlay.png") %>% 
  image_resize(geometry, filter = "quadratic") %>% 
  image_composite(image, operator = "blend", compose_args = "20") %>%
  plot() 

Superpixels with LIME

The LIME package offers a similar capability referred to as superpixels. Superpixels is the process of segmenting an image. We can use this concept to help identify parts of an image that explain our model’s prediction.

plot_superpixels(img_path)

First, we’ll create a function that preprocesses our image.

image_prep <- function(x) {
  arrays <- lapply(x, function(path) {
  img <- image_load(path, target_size = c(150, 150))
  x <- image_to_array(img)
  x <- array_reshape(x, c(1, dim(x)))
  x <- x / 255
  })
  do.call(abind::abind, c(arrays, list(along = 1)))
}

Next, we’ll create a lime explainer object that takes our image path, our cats_and_dogs_small_2.h5 model object, and the image preprocessing function. Also, since keras does not supply class labels in the model object we pass a vector that relates the label to the 0-1 predictions.

model_labels <- c("0" = "cat", "1" = "dog")
explainer <- lime(img_path, as_classifier(model, model_labels), image_prep)

We can now run the explain() function which implements the methodology in https://arxiv.org/abs/1602.04938. See https://lime.data-imaginist.com/ for more details. In this example, we are searching for the 35 superpixels that help to explain our model’s prediction. The current settings result in an explanation fit (\(R^2\)) of 0.7. You could tweak the parameter settings for explain() to try increase the explanation fit. We see that the face of the dog is identified as one of the superpixels that helps to explain the correct prediction.

explanation <- explain(
  img_path, 
  explainer,
  n_labels = 2,
  n_features = 35,
  n_superpixels = 35,
  weight = 10,
  background = "white"
  )
plot_image_explanation(explanation)

An alternative view that puts more focus on the relevant superpixels, but removes the context can be seen by using display = ‘block’:

plot_image_explanation(explanation, display = 'block')


  1. Note that much of the content in this module comes from Chapter 5 of Deep Learning with R and also from this notebook by the author.

LS0tCnRpdGxlOiAiVmlzdWFsaXppbmcgd2hhdCBDTk5zIGxlYXJuIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLCBtZXNzYWdlID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRSkKZ2dwbG90Mjo6dGhlbWVfc2V0KGdncGxvdDI6OnRoZW1lX2J3KCkpCmBgYAoKSW4gdGhpcyBub3RlYm9va15bTm90ZSB0aGF0IG11Y2ggb2YgdGhlIGNvbnRlbnQgaW4gdGhpcyBtb2R1bGUgY29tZXMgZnJvbQpDaGFwdGVyIDUgb2YgW0RlZXAgTGVhcm5pbmcgd2l0aCBSXShodHRwczovL3d3dy5tYW5uaW5nLmNvbS9ib29rcy9kZWVwLWxlYXJuaW5nLXdpdGgtcikKYW5kIGFsc28gZnJvbSB0aGlzIFtub3RlYm9va10oaHR0cHM6Ly9qamFsbGFpcmUuZ2l0aHViLmlvL2RlZXAtbGVhcm5pbmctd2l0aC1yLW5vdGVib29rcy9ub3RlYm9va3MvNS40LXZpc3VhbGl6aW5nLXdoYXQtY29udm5ldHMtbGVhcm4ubmIuaHRtbCkgYnkgdGhlIGF1dGhvci5dLCB3ZSdsbCB0YWtlIGEgbG9vayBhdCBob3cgaG93IENOTnMgaW50ZXJwcmV0IGltYWdlcyBmcm9tIGEKdmlzdWFsIHBlcnNwZWN0aXZlLiBUaGVyZSBhcmUgc2V2ZXJhbCBhcHByb2FjaGVzIG9uZSBjb3VsZCB0YWtlIGJ1dCB3ZSdsbCBsb29rCmF0IHRoZSBmb2xsb3dpbmcgdGhyZWU6CgoqIFZpc3VhbGl6aW5nIGludGVybWVkaWF0ZSBDTk4gb3V0cHV0cyAo4oCcaW50ZXJtZWRpYXRlIGFjdGl2YXRpb25z4oCdKS4gVGhpcyBpcwogIHVzZWZ1bCB0byB1bmRlcnN0YW5kIGhvdyBzdWNjZXNzaXZlIENOTiBsYXllcnMgdHJhbnNmb3JtIHRoZWlyIGlucHV0LCBhbmQgdG8KICBnZXQgYSBmaXJzdCBpZGVhIG9mIHRoZSBtZWFuaW5nIG9mIGluZGl2aWR1YWwgQ05OIGZpbHRlcnMuCiogVmlzdWFsaXppbmcgQ05OIGZpbHRlcnMuIFRoaXMgaXMgdXNlZnVsIHRvIHVuZGVyc3RhbmQgcHJlY2lzZWx5IHdoYXQgdmlzdWFsCiAgcGF0dGVybiBvciBjb25jZXB0IGVhY2ggZmlsdGVyIGluIGEgQ05OIGlzIHJlY2VwdGl2ZSB0by4KKiBWaXN1YWxpemluZyBzdXBlcnBpeGVscyBhbmQgaGVhdG1hcHMgb2YgY2xhc3MgYWN0aXZhdGlvbiBpbiBhbiBpbWFnZS4gVGhpcyBpcyB1c2VmdWwgdG8KICB1bmRlcnN0YW5kIHdoaWNoIHBhcnQgb2YgYW4gaW1hZ2Ugd2VyZSBpZGVudGlmaWVkIGFzIGJlbG9uZ2luZyB0byBhIGdpdmVuCiAgY2xhc3MsIGFuZCB0aHVzIGFsbG93cyB0byBsb2NhbGl6ZSBvYmplY3RzIGluIGltYWdlcy4KICAKRm9yIHRoZSBmaXJzdCBtZXRob2QsIGFjdGl2YXRpb24gdmlzdWFsaXphdGlvbiwgd2UnbGwgdXNlIHRoZSBzbWFsbCBDTk4gdGhhdCB3ZQp0cmFpbmVkIGZyb20gc2NyYXRjaCBpbiB0aGUgW2NhdCB2cy4gZG9nIG1vZHVsZV0oaHR0cHM6Ly9yc3R1ZGlvLWNvbmYtMjAyMC5naXRodWIuaW8vZGwta2VyYXMtdGYvbm90ZWJvb2tzLzAyLWNhdHMtdnMtZG9ncy5uYi5odG1sI21vZGVsLTIpLgpGb3IgdGhlIG90aGVyIHR3byBtZXRob2RzLCB3ZSB3aWxsIHVzZSB0aGUgVkdHMTYgbW9kZWwgdGhhdCB3ZSBpbnRyb2R1Y2VkIGluIHRoZQpbQ05OIFRyYW5zZmVyIGxlYXJuaW5nIG5vdGVib29rXShGb3IgdGhlIG5leHQgdHdvIG1ldGhvZHMsIHdlIHdpbGwgdXNlIHRoZSBWR0cxNiBtb2RlbCB0aGF0IHdlIGludHJvZHVjZWQgaW4gdGhlIHByZXZpb3VzIHNlY3Rpb24uKS4KCiMgUmVxdWlyZWQgcGFja2FnZXMKCmBgYHtyfQojIEluaXRpYWxpemUgcGFja2FnZQpsaWJyYXJ5KGtlcmFzKQpsaWJyYXJ5KHRlbnNvcmZsb3cpCmxpYnJhcnkoZ3JpZCkgICAgICAgICAjIGZvciBwcm9kdWNpbmcgc2VjdGlvbiAxICYgMiBpbWFnZXMKbGlicmFyeShncmlkRXh0cmEpICAgICMgZm9yIHByb2R1Y2luZyBzZWN0aW9uIDEgJiAyIGltYWdlcwpsaWJyYXJ5KG1hZ2ljaykgICAgICAgIyBmb3IgcHJvZHVjaW5nIHNlY3Rpb24gMyBpbWFnZXMKbGlicmFyeSh2aXJpZGlzKSAgICAgICMgZm9yIHByb2R1Y2luZyBzZWN0aW9uIDMgaW1hZ2VzCmxpYnJhcnkobGltZSkgICAgICAgICAjIGZvciBwcm9kdWNpbmcgc2VjdGlvbiAzIGltYWdlcwoKIyBXZSBkaXNhYmxlIGVhZ2VyIGV4ZWN1dGlvbiB0byBleHRyYWN0IHRoZSBncmFkaWVudHMgbGF0ZXIgb24uIFRoaXMgaXNuJ3QKIyByZXF1aXJlZCBhcyB3ZSBjb3VsZCBhbHNvIGdldCBncmFkaWVudHMgd2l0aCB0ZiRHcmFkaWVudFRhcGUuIFNlZSB0aGlzCiMgZGlzY3Vzc2lvbiBmb3IgZGV0YWlscyBodHRwczovL2dpdGh1Yi5jb20vcnN0dWRpby9rZXJhcy9pc3N1ZXMvOTQ1CnRmJGNvbXBhdCR2MSRkaXNhYmxlX2VhZ2VyX2V4ZWN1dGlvbigpCmBgYAoKIyBWaXN1YWxpemluZyBpbnRlcm1lZGlhdGUgYWN0aXZhdGlvbnMKClZpc3VhbGl6aW5nIGludGVybWVkaWF0ZSBhY3RpdmF0aW9ucyBjb25zaXN0cyBvZiBkaXNwbGF5aW5nIHRoZSBmZWF0dXJlIG1hcHMgdGhhdCBhcmUgb3V0cHV0IGJ5IHZhcmlvdXMgY29udm9sdXRpb24gYW5kIHBvb2xpbmcgbGF5ZXJzIGluIGEgbmV0d29yay4gVGhpcyBnaXZlcyBhIHZpZXcgaW50byBob3cgYW4gaW5wdXQgaXMgZGVjb21wb3NlZCB1bnRvIHRoZSBkaWZmZXJlbnQgZmlsdGVycyBsZWFybmVkIGJ5IHRoZSBuZXR3b3JrLiBUaGVzZSBmZWF0dXJlIG1hcHMgd2Ugd2FudCB0byB2aXN1YWxpemUgaGF2ZSAzIGRpbWVuc2lvbnM6IHdpZHRoLCBoZWlnaHQsIGFuZCBkZXB0aCAoYWthIGNoYW5uZWxzKS4gRWFjaCBjaGFubmVsIGVuY29kZXMgcmVsYXRpdmVseSBpbmRlcGVuZGVudCBmZWF0dXJlcywgc28gdGhlIHByb3BlciB3YXkgdG8gdmlzdWFsaXplIHRoZXNlIGZlYXR1cmUgbWFwcyBpcyBieSBpbmRlcGVuZGVudGx5IHBsb3R0aW5nIHRoZSBjb250ZW50cyBvZiBldmVyeSBjaGFubmVsLCBhcyBhIDJEIGltYWdlLiBMZXTigJlzIHN0YXJ0IGJ5IGxvYWRpbmcgdGhlIG1vZGVsIHRoYXQgd2Ugc2F2ZWQgaW4gdGhlIFtjYXQgdnMuIGRvZyBtb2R1bGVdKGh0dHBzOi8vcnN0dWRpby1jb25mLTIwMjAuZ2l0aHViLmlvL2RsLWtlcmFzLXRmL25vdGVib29rcy8wMi1jYXRzLXZzLWRvZ3MubmIuaHRtbCNtb2RlbC0yKS4KCmBgYHtyIGxvYWQtbW9kZWx9CmZpbGVfbG9jYWwgPC0gaGVyZTo6aGVyZSgibWF0ZXJpYWxzIiwgIjA0LWNvbXB1dGVyLXZpc2lvbi1DTk5zIiwgImNhdHNfYW5kX2RvZ3Nfc21hbGxfMi5oNSIpCm1vZGVsIDwtIGxvYWRfbW9kZWxfaGRmNShmaWxlX2xvY2FsKQptb2RlbApgYGAKClRoaXMgd2lsbCBiZSB0aGUgaW5wdXQgaW1hZ2Ugd2Ugd2lsbCB1c2Ug4oCTIGEgcGljdHVyZSBvZiBhIGRvZywgbm90IHBhcnQgb2YgaW1hZ2VzIHRoYXQgdGhlIG5ldHdvcmsgd2FzIHRyYWluZWQgb24uIFRoaXMgaW1hZ2UgaXMgcGFydGljdWxhcmx5IGludGVyZXN0aW5nIGJlY2F1c2UgaXQgYWxzbyBoYXMgYSBwaWN0dXJlIG9mIGEgaHVtYW4gYnV0IGlmIHlvdSB3ZXJlIHRvIHByZWRpY3QgdGhlIGNsYXNzIG9mIHRoaXMgaW1hZ2Ugb3VyIG1vZGVsIGNvcnJlY3RseSBwcmVkaWN0cyBhIGRvZy4KCmBgYHtyIGdldC1pbWFnZX0KIyBQcmVwcm9jZXNzZXMgdGhlIGltYWdlIGludG8gYSA0RCB0ZW5zb3IKaW1nX3BhdGggPC0gaGVyZTo6aGVyZSgibWF0ZXJpYWxzIiwgImRhdGEiLCAiZG9ncy12cy1jYXRzIiwgInRlc3QiLCAiZG9ncyIsICJkb2cuMTUwOC5qcGciKQppbWcgPC0gaW1hZ2VfbG9hZChpbWdfcGF0aCwgdGFyZ2V0X3NpemUgPSBjKDE1MCwgMTUwKSkKaW1nX3RlbnNvciA8LSBpbWFnZV90b19hcnJheShpbWcpCmltZ190ZW5zb3IgPC0gYXJyYXlfcmVzaGFwZShpbWdfdGVuc29yLCBjKDEsIDE1MCwgMTUwLCAzKSkKaW1nX3RlbnNvciA8LSBpbWdfdGVuc29yIC8gMjU1CgpkaW0oaW1nX3RlbnNvcikKYGBgCgpgYGB7ciBwbG90LWltYWdlfQpwbG90KGFzLnJhc3RlcihpbWdfdGVuc29yWzEsLCxdKSkKYGBgCgpJbiBvcmRlciB0byBleHRyYWN0IHRoZSBmZWF0dXJlIG1hcHMgeW91IHdhbnQgdG8gbG9vayBhdCwgeW914oCZbGwgY3JlYXRlIGEgS2VyYXMgbW9kZWwgdGhhdCB0YWtlcyBiYXRjaGVzIG9mIGltYWdlcyBhcyBpbnB1dCwgYW5kIG91dHB1dHMgdGhlIGFjdGl2YXRpb25zIG9mIGFsbCBjb252b2x1dGlvbiBhbmQgcG9vbGluZyBsYXllcnMuIFRvIGRvIHRoaXMsIHdlIHdpbGwgdXNlIHRoZSBga2VyYXNfbW9kZWwoKWAgZnVuY3Rpb24gKHJlY2FsbCBga2VyYXNfbW9kZWwoKWAgd2FzIGludHJvZHVjZWQgaW4gdGhlIFtjb2xsYWJvcmF0aXZlIGZpbHRlcmluZ10oaHR0cHM6Ly9yc3R1ZGlvLWNvbmYtMjAyMC5naXRodWIuaW8vZGwta2VyYXMtdGYvbm90ZWJvb2tzL2NvbGxhYm9yYXRpdmUtZmlsdGVyaW5nLm5iLmh0bWwjYmFzaWMtbW9kZWwpIG5vdGVib29rLiAKCmBgYHtyfQpsYXllcl9vdXRwdXRzIDwtIGxhcHBseShtb2RlbCRsYXllcnNbMTo4XSwgZnVuY3Rpb24obGF5ZXIpIGxheWVyJG91dHB1dCkKYWN0aXZhdGlvbl9tb2RlbCA8LSBrZXJhc19tb2RlbChpbnB1dHMgPSBtb2RlbCRpbnB1dCwgb3V0cHV0cyA9IGxheWVyX291dHB1dHMpCmBgYAoKV2hlbiBmZWQgYW4gaW1hZ2UgaW5wdXQsIHRoaXMgbW9kZWwgcmV0dXJucyB0aGUgYWN0aXZhdGlvbiBvdXRwdXQgdmFsdWVzIGZvciBlYWNoIG9mIHRoZSA4IGhpZGRlbiBsYXllcnMgaW4gdGhlIGNvbnZvbHV0aW9uIHNlY3Rpb24gb2Ygb3VyIG1vZGVsLgoKYGBge3J9CmFjdGl2YXRpb25zIDwtIGFjdGl2YXRpb25fbW9kZWwgJT4lIHByZWRpY3QoaW1nX3RlbnNvcikKYGBgCgpGb3IgaW5zdGFuY2UsIHRoaXMgaXMgdGhlIGFjdGl2YXRpb24gb2YgdGhlIGZpcnN0IGNvbnZvbHV0aW9uIGxheWVyIGZvciBvdXIgZG9nCmltYWdlLiBOb3RlIGhvdyB0aGUgZGltZW5zaW9uIGFsaWduIHRvIHRoZSBkaW1lbnNpb25zIG9mIHRoZSBmaXJzdCBsYXllciBpbiBvdXIKQ05OIG1vZGVsLgoKYGBge3IgYWN0Mn0KZmlyc3RfbGF5ZXJfYWN0aXZhdGlvbiA8LSBhY3RpdmF0aW9uc1tbMV1dCmRpbShmaXJzdF9sYXllcl9hY3RpdmF0aW9uKQpgYGAKCkl04oCZcyBhIDE0OCB4IDE0OCBmZWF0dXJlIG1hcCB3aXRoIDMyIGNoYW5uZWxzLiBMZXQncyB2aXN1YWxpemUgc29tZSBvZiB0aGVzZQpjaGFubmVscy4KCmBgYHtyfQpwbG90X2NoYW5uZWwgPC0gZnVuY3Rpb24oY2hhbm5lbCkgewogIHJvdGF0ZSA8LSBmdW5jdGlvbih4KSB0KGFwcGx5KHgsIDIsIHJldikpCiAgaW1hZ2Uocm90YXRlKGNoYW5uZWwpLCBheGVzID0gRkFMU0UsIGFzcCA9IDEsCiAgICAgICAgY29sID0gdGVycmFpbi5jb2xvcnMoMTIpKQp9CmBgYAoKVGhlIDIwdGggY2hhbm5lbCBzZWVtcyB0byBjYXB0dXJlIHRoZSBvdXRsaW5lIG9mIHRoZSBkb2cgYW5kIGFsc28gdGhlIHBlcnNvbidzCmZhY2UuCgpgYGB7ciB2aXoyfQpwbG90X2NoYW5uZWwoZmlyc3RfbGF5ZXJfYWN0aXZhdGlvblsxLCwsMjBdKQpgYGAKClRoZSAyOHRoIGNoYW5uZWwgc2VlbXMgdG8gb3V0bGluZSBzb21lIG9mIHRoZSBvdGhlciBmZWF0dXJlcyBpbiB0aGUgaW1hZ2UgKGkuZS4Kd2luZG93IHBhbmVscykuCgpgYGB7ciB2aXo3fQpwbG90X2NoYW5uZWwoZmlyc3RfbGF5ZXJfYWN0aXZhdGlvblsxLCwsMjhdKQpgYGAKCldlIGNhbiBnbyBhaGVhZCBhbmQgY3JlYXRlIGltYWdlcyBmb3IgZWFjaCBjaGFubmVsIGluIGVhY2ggb2YgdGhlIDggbGF5ZXJzIG9mCm91ciBjb252b2x1dGlvbiBwYXJ0IG9mIG91ciBtb2RlbC4gVGhlIGZvbGxvd2luZyB3aWxsIGNyZWF0ZSBhIG5ldyBzdWJkaXJlY3RvcnksCnBsb3QgZXZlcnkgY2hhbm5lbCBpbiBlYWNoIG9mIG91ciA4IGFjdGl2YXRpb24gbWFwcywgc3RhY2sgdGhlIHJlc3VsdHMgaW4gb25lCmJpZyBpbWFnZSB0ZW5zb3IsIHdpdGggY2hhbm5lbHMgc3RhY2tlZCBzaWRlLWJ5LXNpZGUgcGxvdCwgYW5kIHNhdmUgdGhlbSBpbiB0aGUKbmV3IGRpcmVjdG9yeS4KCmBgYHtyIHZpekFsbH0KZGlyLmNyZWF0ZSgiZG9nX2FjdGl2YXRpb25zIikKaW1hZ2Vfc2l6ZSA8LSA1OAppbWFnZXNfcGVyX3JvdyA8LSAxNgpmb3IgKGkgaW4gMTo4KSB7CiAgCiAgbGF5ZXJfYWN0aXZhdGlvbiA8LSBhY3RpdmF0aW9uc1tbaV1dCiAgbGF5ZXJfbmFtZSA8LSBtb2RlbCRsYXllcnNbW2ldXSRuYW1lCiAKICBuX2ZlYXR1cmVzIDwtIGRpbShsYXllcl9hY3RpdmF0aW9uKVtbNF1dCiAgbl9jb2xzIDwtIG5fZmVhdHVyZXMgJS8lIGltYWdlc19wZXJfcm93CiAKICBwbmcocGFzdGUwKCJkb2dfYWN0aXZhdGlvbnMvIiwgaSwgIl8iLCBsYXllcl9uYW1lLCAiLnBuZyIpLCAKICAgICAgd2lkdGggPSBpbWFnZV9zaXplICogaW1hZ2VzX3Blcl9yb3csIAogICAgICBoZWlnaHQgPSBpbWFnZV9zaXplICogbl9jb2xzKQogIG9wIDwtIHBhcihtZnJvdyA9IGMobl9jb2xzLCBpbWFnZXNfcGVyX3JvdyksIG1haSA9IHJlcF9sZW4oMC4wMiwgNCkpCiAgCiAgZm9yIChjb2wgaW4gMDoobl9jb2xzIC0gMSkpIHsKICAgIGZvciAocm93IGluIDA6KGltYWdlc19wZXJfcm93IC0gMSkpIHsKICAgICAgY2hhbm5lbF9pbWFnZSA8LSBsYXllcl9hY3RpdmF0aW9uWzEsLCwoY29sKmltYWdlc19wZXJfcm93KSArIHJvdyArIDFdCiAgICAgIHBsb3RfY2hhbm5lbChjaGFubmVsX2ltYWdlKQogICAgfQogIH0KICAKICBwYXIob3ApCiAgZGV2Lm9mZigpCn0KYGBgCgpZb3Ugc2hvdWxkIG5vdyBoYXZlIHBsb3RzIHZpc3VhbGl6aW5nIHRoZSBmaXJzdCA4IGZlYXR1cmUgY2hhbm5lbHM6CgoxLiAxX2NvbnYyZC5wbmcKMi4gMl9tYXhfcG9vbGluZzJkLnBuZwozLiAzX2NvbnYyZF8xLnBuZwo0LiA0X21heF9wb29saW5nMmRfMS5wbmcKNS4gNV9jb252MmRfMi5wbmcKNi4gNl9tYXhfcG9vbGluZzJkXzIucG5nCjcuIDdfY29udjJkXzMucG5nCjguIDhfbWF4X3Bvb2xpbmcyZF8zLnBuZwoKVGhlIGZvbGxvd2luZyBwbG90cyB0aGUgZmVhdHVyZSBtYXBzIGluIHRoZSBmaXJzdCBsYXllciBhbmQgdGhlbiB0aGUgZmluYWwgOHRoCmxheWVyLiBOb3RlIGhvdyB0aGUgZmluYWwgbGF5ZXIgaXMgdmVyeSBhYnN0cmFjdCB0byBodW1hbiBleWVzLi4uYnV0IGl0IGhhcyBhIGxvdApvZiBtYXRoZW1hdGljYWwgaW5mb3JtYXRpb24gaW50ZXJwcmV0YWJsZSBieSBvdXIgQ05OIG1vZGVsLiBUaGUgYWN0aXZhdGlvbnMgb2YKbGF5ZXJzIGhpZ2hlci11cCBjYXJyeSBsZXNzIGFuZCBsZXNzIGluZm9ybWF0aW9uIGFib3V0IHRoZSBzcGVjaWZpYyBpbnB1dCBiZWluZwpzZWVuLCBhbmQgbW9yZSBhbmQgbW9yZSBpbmZvcm1hdGlvbiBhYm91dCB0aGUgdGFyZ2V0IChpbiBvdXIgY2FzZSwgdGhlIGNsYXNzIG9mCnRoZSBpbWFnZTogY2F0IG9yIGRvZykuCgpgYGB7cn0Ka25pdHI6OmluY2x1ZGVfZ3JhcGhpY3MoImRvZ19hY3RpdmF0aW9ucy8xX2NvbnYyZC5wbmciKQpgYGAKCmBgYHtyfQprbml0cjo6aW5jbHVkZV9ncmFwaGljcygiZG9nX2FjdGl2YXRpb25zLzhfbWF4X3Bvb2xpbmcyZF8zLnBuZyIpCmBgYAoKIyBWaXN1YWxpemluZyBDTk4gZmlsdGVyczoKCkFub3RoZXIgZWFzeSB0aGluZyB0byBkbyB0byBpbnNwZWN0IHRoZSBmaWx0ZXJzIGxlYXJuZWQgYnkgY29udm5ldHMgaXMgdG8gZGlzcGxheSB0aGUgdmlzdWFsIHBhdHRlcm4gdGhhdCBlYWNoIGZpbHRlciBpcyBtZWFudCB0byByZXNwb25kIHRvLiBUaGlzIGNhbiBiZSBkb25lIHdpdGggZ3JhZGllbnQgYXNjZW50IGluIGlucHV0IHNwYWNlOiBhcHBseWluZyBncmFkaWVudCBkZXNjZW50IHRvIHRoZSB2YWx1ZSBvZiB0aGUgaW5wdXQgaW1hZ2Ugb2YgYSBjb252bmV0IHNvIGFzIHRvIG1heGltaXplIHRoZSByZXNwb25zZSBvZiBhIHNwZWNpZmljIGZpbHRlciwgc3RhcnRpbmcgZnJvbSBhIGJsYW5rIGlucHV0IGltYWdlLiBUaGUgcmVzdWx0aW5nIGlucHV0IGltYWdlIHdvdWxkIGJlIG9uZSB0aGF0IHRoZSBjaG9zZW4gZmlsdGVyIGlzIG1heGltYWxseSByZXNwb25zaXZlIHRvLgoKVGhlIHByb2Nlc3MgaXMgc2ltcGxlOiB3ZSB3aWxsIGJ1aWxkIGEgbG9zcyBmdW5jdGlvbiB0aGF0IG1heGltaXplcyB0aGUgdmFsdWUgb2YgYSBnaXZlbiBmaWx0ZXIgaW4gYSBnaXZlbiBjb252b2x1dGlvbiBsYXllciwgdGhlbiB3ZSB3aWxsIHVzZSBzdG9jaGFzdGljIGdyYWRpZW50IGRlc2NlbnQgdG8gYWRqdXN0IHRoZSB2YWx1ZXMgb2YgdGhlIGlucHV0IGltYWdlIHNvIGFzIHRvIG1heGltaXplIHRoaXMgYWN0aXZhdGlvbiB2YWx1ZS4gRm9yIGluc3RhbmNlLCBoZXJl4oCZcyBhIGxvc3MgZm9yIHRoZSBhY3RpdmF0aW9uIG9mIGZpbHRlciAwIGluIHRoZSBsYXllciDigJxibG9jazNfY29udjHigJ0gb2YgdGhlIFZHRzE2IG5ldHdvcmssIHByZS10cmFpbmVkIG9uIEltYWdlTmV0OgoKYGBge3J9Cm1vZGVsIDwtIGFwcGxpY2F0aW9uX3ZnZzE2KAogIHdlaWdodHMgPSAiaW1hZ2VuZXQiLAogIGluY2x1ZGVfdG9wID0gRkFMU0UKICApCgpsYXllcl9uYW1lIDwtICJibG9jazNfY29udjEiCmZpbHRlcl9pbmRleCA8LSAxCmxheWVyX291dHB1dCA8LSBnZXRfbGF5ZXIobW9kZWwsIGxheWVyX25hbWUpJG91dHB1dApsb3NzIDwtIGtfbWVhbihsYXllcl9vdXRwdXRbLCwsZmlsdGVyX2luZGV4XSkKYGBgCgpUbyBpbXBsZW1lbnQgZ3JhZGllbnQgZGVzY2VudCwgd2Ugd2lsbCBuZWVkIHRoZSBncmFkaWVudCBvZiB0aGlzIGxvc3Mgd2l0aCByZXNwZWN0IHRvIHRoZSBtb2RlbOKAmXMgaW5wdXQuIFRvIGRvIHRoaXMsIHdlIHdpbGwgdXNlIHRoZSBga19ncmFkaWVudHMoKWAgS2VyYXMgYmFja2VuZCBmdW5jdGlvbi4gSW4gVEYgMi4wIGEgY2hhbmdlIHdhcyBtYWRlIHdoZXJlIGBrX2dyYWRpZW50cygpYCBjYW4gb25seSBiZSByYW4gd2hlbiBlYWdlciBleGVjdXRpb24gaXMgdHVybmVkIG9mZiwgd2hpY2ggaXMKd2h5IHdlIHJhbiBgdGYkY29tcGF0JHYxJGRpc2FibGVfZWFnZXJfZXhlY3V0aW9uKClgIGF0IHRoZSB0b3Agb2YgdGhlIHNjcmlwdC4gU2VlIGh0dHBzOi8vZ2l0aHViLmNvbS9yc3R1ZGlvL2tlcmFzL2lzc3Vlcy85NDUgZm9yIG1vcmUgZGV0YWlscy4KCmBgYHtyfQojIFRoZSBjYWxsIHRvIGtfZ3JhZGllbnRzIHJldHVybnMgYW4gUiBsaXN0IG9mIHRlbnNvcnMgKG9mIHNpemUgMSBpbiB0aGlzIGNhc2UpLiAKIyBIZW5jZSwgeW91IGtlZXAgb25seSB0aGUgZmlyc3QgZWxlbWVudOKAlHdoaWNoIGlzIGEgdGVuc29yLgpncmFkcyA8LSBrX2dyYWRpZW50cyhsb3NzLCBtb2RlbCRpbnB1dClbWzFdXQpgYGAKCkEgbm9uLW9idmlvdXMgdHJpY2sgdG8gdXNlIGZvciB0aGUgZ3JhZGllbnQgZGVzY2VudCBwcm9jZXNzIHRvIGdvIHNtb290aGx5IGlzIHRvIG5vcm1hbGl6ZSB0aGUgZ3JhZGllbnQgdGVuc29yLCBieSBkaXZpZGluZyBpdCBieSBpdHMgTDIgbm9ybSAodGhlIHNxdWFyZSByb290IG9mIHRoZSBhdmVyYWdlIG9mIHRoZSBzcXVhcmUgb2YgdGhlIHZhbHVlcyBpbiB0aGUgdGVuc29yKS4gVGhpcyBlbnN1cmVzIHRoYXQgdGhlIG1hZ25pdHVkZSBvZiB0aGUgdXBkYXRlcyBkb25lIHRvIHRoZSBpbnB1dCBpbWFnZSBpcyBhbHdheXMgd2l0aGluIGEgc2FtZSByYW5nZS4KCmBgYHtyfQojIEFkZCAxZS01IGJlZm9yZSBkaXZpZGluZyB0byBhdm9pZCBhY2NpZGVudGFsbHkgZGl2aWRpbmcgYnkgMApncmFkcyA8LSBncmFkcyAvIChrX3NxcnQoa19tZWFuKGtfc3F1YXJlKGdyYWRzKSkpICsgMWUtNSkKYGBgCgpOb3cgeW91IG5lZWQgYSB3YXkgdG8gY29tcHV0ZSB0aGUgdmFsdWUgb2YgdGhlIGxvc3MgdGVuc29yIGFuZCB0aGUgZ3JhZGllbnQgdGVuc29yLCBnaXZlbiBhbiBpbnB1dCBpbWFnZS4gWW91IGNhbiBkZWZpbmUgYSBLZXJhcyBiYWNrZW5kIGZ1bmN0aW9uIHRvIGRvIHRoaXM6IGBpdGVyYXRlKClgIGlzIGEgZnVuY3Rpb24gdGhhdCB0YWtlcyBhIHRlbnNvciAoYXMgYSBsaXN0IG9mIHRlbnNvcnMgb2Ygc2l6ZSAxKSBhbmQgcmV0dXJucyBhIGxpc3Qgb2YgdHdvIHRlbnNvcnM6IHRoZSBsb3NzIHZhbHVlIGFuZCB0aGUgZ3JhZGllbnQgdmFsdWUuCgpgYGB7cn0KaXRlcmF0ZSA8LSBrX2Z1bmN0aW9uKGxpc3QobW9kZWwkaW5wdXQpLCBsaXN0KGxvc3MsIGdyYWRzKSkKYyhsb3NzX3ZhbHVlLCBncmFkc192YWx1ZSkgJTwtJSBpdGVyYXRlKGxpc3QoYXJyYXkoMCwgZGltID0gYygxLCAxNTAsIDE1MCwgMykpKSkKYGBgCgpBdCB0aGlzIHBvaW50IHdlIGNhbiBkZWZpbmUgYW4gUiBsb29wIHRvIGRvIHN0b2NoYXN0aWMgZ3JhZGllbnQgZGVzY2VudDoKCmBgYHtyfQojIFN0YXJ0cyBmcm9tIGEgZ3JheSBpbWFnZSB3aXRoIHNvbWUgbm9pc2UKaW5wdXRfaW1nX2RhdGEgPC0gYXJyYXkocnVuaWYoMTUwICogMTUwICogMyksIGRpbSA9IGMoMSwgMTUwLCAxNTAsIDMpKSAqIDIwICsgMTI4CgojIFJ1bnMgZ3JhZGllbnQgYXNjZW50IGZvciA0MCBzdGVwCnN0ZXAgPC0gMQpmb3IgKGkgaW4gMTo0MCkgeyAKICAjIENvbXB1dGVzIHRoZSBsb3NzIHZhbHVlIGFuZCBncmFkaWVudCB2YWx1ZQogIGMobG9zc192YWx1ZSwgZ3JhZHNfdmFsdWUpICU8LSUgaXRlcmF0ZShsaXN0KGlucHV0X2ltZ19kYXRhKSkKICAKICAjIEFkanVzdHMgdGhlIGlucHV0IGltYWdlIGluIHRoZSBkaXJlY3Rpb24gdGhhdCBtYXhpbWl6ZXMgdGhlIGxvc3MKICBpbnB1dF9pbWdfZGF0YSA8LSBpbnB1dF9pbWdfZGF0YSArIChncmFkc192YWx1ZSAqIHN0ZXApICAKfQpgYGAKClRoZSByZXN1bHRpbmcgaW1hZ2UgdGVuc29yIGlzIGEgZmxvYXRpbmctcG9pbnQgdGVuc29yIG9mIHNoYXBlIGAoMSwgMTUwLCAxNTAsIDMpYCwgd2l0aCB2YWx1ZXMgdGhhdCBtYXkgbm90IGJlIGludGVnZXJzIHdpdGhpbiBbMCwgMjU1XS4gSGVuY2UgeW91IG5lZWQgdG8gcG9zdC1wcm9jZXNzIHRoaXMgdGVuc29yIHRvIHR1cm4gaXQgaW50byBhIGRpc3BsYXlhYmxlIGltYWdlLiBZb3UgZG8gc28gd2l0aCB0aGUgZm9sbG93aW5nIHN0cmFpZ2h0Zm9yd2FyZCB1dGlsaXR5IGZ1bmN0aW9uLgoKYGBge3J9CmRlcHJvY2Vzc19pbWFnZSA8LSBmdW5jdGlvbih4KSB7CiAgZG1zIDwtIGRpbSh4KQoKICAgICMgTm9ybWFsaXplcyB0aGUgdGVuc29yOiBjZW50ZXJzIG9uIDAuLCBlbnN1cmVzIHRoYXQgc3RkIGlzIDAuMQogIHggPC0geCAtIG1lYW4oeCkKICB4IDwtIHggLyAoc2QoeCkgKyAxZS01KQogIHggPC0geCAqIDAuMQogIAogICMgQ2xpcHMgdG8gWzAsIDFdCiAgeCA8LSB4ICsgMC41CiAgeCA8LSBwbWF4KDAsIHBtaW4oeCwgMSkpCiAgCiAgIyBSZXR1cm5zIHdpdGggdGhlIG9yaWdpbmFsIGltYWdlIGRpbWVuc2lvbnMKICBhcnJheSh4LCBkaW0gPSBkbXMpCn0KYGBgCgpOb3cgeW91IGhhdmUgYWxsIHRoZSBwaWVjZXMuIExldOKAmXMgcHV0IHRoZW0gdG9nZXRoZXIgaW50byBhbiBSIGZ1bmN0aW9uIHRoYXQgdGFrZXMgYXMgaW5wdXQgYSBsYXllciBuYW1lIGFuZCBhIGZpbHRlciBpbmRleCwgYW5kIHJldHVybnMgYSB2YWxpZCBpbWFnZSB0ZW5zb3IgcmVwcmVzZW50aW5nIHRoZSBwYXR0ZXJuIHRoYXQgbWF4aW1pemVzIHRoZSBhY3RpdmF0aW9uIG9mIHRoZSBzcGVjaWZpZWQgZmlsdGVyLgoKYGBge3J9CmdlbmVyYXRlX3BhdHRlcm4gPC0gZnVuY3Rpb24obGF5ZXJfbmFtZSwgZmlsdGVyX2luZGV4LCBzaXplID0gMTUwKSB7CiAgCiAgIyBCdWlsZHMgYSBsb3NzIGZ1bmN0aW9uIHRoYXQgbWF4aW1pemVzIHRoZSBhY3RpdmF0aW9uIG9mIHRoZSBudGggZmlsdGVyIG9mIHRoZSBsYXllciB1bmRlciBjb25zaWRlcmF0aW9uCiAgbGF5ZXJfb3V0cHV0IDwtIG1vZGVsJGdldF9sYXllcihsYXllcl9uYW1lKSRvdXRwdXQKICBsb3NzIDwtIGtfbWVhbihsYXllcl9vdXRwdXRbLCwsZmlsdGVyX2luZGV4XSkKICAKICAjIENvbXB1dGVzIHRoZSBncmFkaWVudCBvZiB0aGUgaW5wdXQgcGljdHVyZSB3aXRoIHJlZ2FyZCB0byB0aGlzIGxvc3MKICBncmFkcyA8LSBrX2dyYWRpZW50cyhsb3NzLCBtb2RlbCRpbnB1dClbWzFdXQogIAogICMgTm9ybWFsaXphdGlvbiB0cmljazogbm9ybWFsaXplcyB0aGUgZ3JhZGllbnQKICBncmFkcyA8LSBncmFkcyAvIChrX3NxcnQoa19tZWFuKGtfc3F1YXJlKGdyYWRzKSkpICsgMWUtNSkKICAKICAjIFJldHVybnMgdGhlIGxvc3MgYW5kIGdyYWRzIGdpdmVuIHRoZSBpbnB1dCBwaWN0dXJlCiAgaXRlcmF0ZSA8LSBrX2Z1bmN0aW9uKGxpc3QobW9kZWwkaW5wdXQpLCBsaXN0KGxvc3MsIGdyYWRzKSkKICAKICAjIFN0YXJ0cyBmcm9tIGEgZ3JheSBpbWFnZSB3aXRoIHNvbWUgbm9pc2UKICBpbnB1dF9pbWdfZGF0YSA8LQogIGFycmF5KHJ1bmlmKHNpemUgKiBzaXplICogMyksIGRpbSA9IGMoMSwgc2l6ZSwgc2l6ZSwgMykpICogMjAgKyAxMjgKCiAgIyBSdW5zIGdyYWRpZW50IGFzY2VudCBmb3IgNDAgc3RlcHMKICBzdGVwIDwtIDEKICBmb3IgKGkgaW4gMTo0MCkgewogICAgYyhsb3NzX3ZhbHVlLCBncmFkc192YWx1ZSkgJTwtJSBpdGVyYXRlKGxpc3QoaW5wdXRfaW1nX2RhdGEpKQogICAgaW5wdXRfaW1nX2RhdGEgPC0gaW5wdXRfaW1nX2RhdGEgKyAoZ3JhZHNfdmFsdWUgKiBzdGVwKQogICAgfQogIAogIGltZyA8LSBpbnB1dF9pbWdfZGF0YVsxLCwsXQogIGRlcHJvY2Vzc19pbWFnZShpbWcpCiAgfQpgYGAKCgpOb3cgd2UgY2FuIHN0YXJ0IHZpc3VhbGl6aW5nIGV2ZXJ5IHNpbmdsZSBmaWx0ZXIgaW4gZXZlcnkgbGF5ZXIuIEZvciBzaW1wbGljaXR5LCB3ZSB3aWxsIG9ubHkgbG9vayBhdCB0aGUgZmlyc3QgNjQgZmlsdGVycyBpbiBlYWNoIGxheWVyLCBhbmQgd2lsbCBvbmx5IGxvb2sgYXQgdGhlIGZpcnN0IGxheWVyIG9mIHRoZSBmb2xsb3dpbmcgY29udm9sdXRpb24gYmxvY2tzOiBibG9jazFfY29udjEsIGJsb2NrMl9jb252MSwgYmxvY2szX2NvbnYxLCBibG9jazRfY29udjEuIFdlIHdpbGwgYXJyYW5nZSB0aGUgb3V0cHV0cyBvbiBhIDh4OCBncmlkIG9mIGZpbHRlciBwYXR0ZXJucy4KCmBgYHtyfQpsYXllcnMgPC0gYygiYmxvY2sxX2NvbnYxIiwgImJsb2NrMl9jb252MSIsICJibG9jazNfY29udjEiLCAiYmxvY2s0X2NvbnYxIikKZGlyLmNyZWF0ZSgidmdnX2ZpbHRlcnMiKQoKZm9yIChsYXllcl9uYW1lIGluIGxheWVycykgewogIHNpemUgPC0gMTQwCiAgcG5nKHBhc3RlMCgidmdnX2ZpbHRlcnMvIiwgbGF5ZXJfbmFtZSwgIi5wbmciKSx3aWR0aCA9IDggKiBzaXplLCBoZWlnaHQgPSA4ICogc2l6ZSkKICBncm9icyA8LSBsaXN0KCkKICBmb3IgKGkgaW4gMDo3KSB7CiAgICBmb3IgKGogaW4gMDo3KSB7CiAgICAgIHBhdHRlcm4gPC0gZ2VuZXJhdGVfcGF0dGVybihsYXllcl9uYW1lLCBpICsgKGoqOCkgKyAxLCBzaXplID0gc2l6ZSkKICAgICAgZ3JvYiA8LSByYXN0ZXJHcm9iKHBhdHRlcm4sIHdpZHRoID0gdW5pdCgwLjksICJucGMiKSwgaGVpZ2h0ID0gdW5pdCgwLjksICJucGMiKSkKICAgICAgZ3JvYnNbW2xlbmd0aChncm9icykgKyAxXV0gPC0gZ3JvYgogICAgICB9CiAgICB9CiAgZ3JpZC5hcnJhbmdlKGdyb2JzID0gZ3JvYnMsIG5jb2wgPSA4KQogIGRldi5vZmYoKQp9CmBgYAoKVGhlIHByZXZpb3VzIGNvZGUgcmVzdWx0cyBpbiBhIG5ldyBkaXJlY3RvcnkgYC92Z2dfZmlsdGVyc2AgdGhhdCBjb250YWlucyBmb3VyIGltYWdlcy4gQmVsb3cgaXMgdGhlIGltYWdlIGZvciB0aGUgZmlyc3QgQ05OIGJsb2NrIGZpbHRlciBhbmQgdGhlIHNlY29uZCBpbWFnZSBpcyB0aGUgZm91cnRoIGJsb2NrLiBUaGVzZSBmaWx0ZXIgdmlzdWFsaXphdGlvbnMgdGVsbCB5b3UgYSBsb3QgYWJvdXQgaG93IENOTiBsYXllcnMgc2VlIHRoZSB3b3JsZDogZWFjaCBsYXllciBpbiBhIENOTiBsZWFybnMgYSBjb2xsZWN0aW9uIG9mIGZpbHRlcnMgc3VjaCB0aGF0IHRoZWlyIGlucHV0cyBjYW4gYmUgZXhwcmVzc2VkIGFzIGEgY29tYmluYXRpb24gb2YgdGhlIGZpbHRlcnMuIFlvdSBjYW4gc2VlIHRoYXQgZWFybGllciBmaWx0ZXJzIChpLmUuIGJsb2NrMV9jb252MSkgZW5jb2RlIG1vcmUgc2ltcGxlIGRpcmVjdGlvbmFsIGVkZ2VzIGFuZCBjb2xvcnMgd2hlcmVhcyBsYXRlciBmaWx0ZXJzIChpLmUuIGJsb2NrNF9jb252MSkgc3RhcnQgdG8gcmVzZW1ibGUgdGV4dHVyZXMgZm91bmQgaW4gbmF0dXJhbCBpbWFnZXMgKGkuZS4gZXllcywgZmVhdGhlcnMsIGJhbGxzKS4KCmBgYHtyfQprbml0cjo6aW5jbHVkZV9ncmFwaGljcyhjKCJ2Z2dfZmlsdGVycy9ibG9jazFfY29udjEucG5nIiwgInZnZ19maWx0ZXJzL2Jsb2NrNF9jb252MS5wbmciKSkKYGBgCgojIFZpc3VhbGl6aW5nIGhlYXRtYXBzIG9mIGNsYXNzIGFjdGl2YXRpb24KClRoaXMgbGFzdCB0ZWNobmlxdWUgZGVtb25zdHJhdGVzIGhvdyB0byBoaWdobGlnaHQgdGhlIHBhcnRzIG9mIGFuIGltYWdlIHRoYXQgaXMKbGlrZWx5IHRvIGJlIHRoZSBtb3N0IGltcG9ydGFudCBpbiBob3cgdGhlIG1vZGVsIGNsYXNzaWZpZWQgdGhlIGltYWdlLiBGb3IgZXhhbXBsZSwKaW4gb3VyIGRvZyBpbWFnZSwgd2hpY2ggY29udGFpbnMgYSBodW1hbiwgd2UgY2FuIHNlZSB0aGF0IG91ciBtb2RlbCBjbGFzc2lmaWVzIHRoZQppbWFnZSwgd2l0aCAwLjg5IHByb2JhYmlsaXR5LCBhcyBhIGRvZyAoaW4gdGhpcyBtb2RlbCB0aGUgdGFyZ2V0IGlzIGVuY29kZWQgYXMKMC1jYXQgYW5kIDEtZG9nKS4gU28gb25lIHF1ZXN0aW9uIG1heSBhcmlzZSwgd2hhdCBhYm91dCB0aGlzIGltYWdlIGNhdXNlcyBvdXIKbW9kZWwgdG8gcHJlZGljdCB0aGlzPyBXaGF0IHBpeGVscyBpbiB0aGUgaW1hZ2UgYXJlIG1vc3QgcmVsZXZhbnQ/CgpgYGB7cn0KIyBwcmVkaWN0aW5nIGRvZyBwaWN0dXJlCnByZWRpY3QobW9kZWwsIGltZ190ZW5zb3IpCmBgYAoKIyMgTWFudWFsIGNsYXNzIGFjdGl2YXRpb24gbWFwCgpBIGNsYXNzLWFjdGl2YXRpb24gaGVhdG1hcCBpcyBhIDJEIGdyaWQgb2Ygc2NvcmVzIGFzc29jaWF0ZWQgd2l0aCBhIHNwZWNpZmljIG91dHB1dCBjbGFzcywgY29tcHV0ZWQgZm9yIGV2ZXJ5IGxvY2F0aW9uIGluIGFueSBpbnB1dCBpbWFnZSwgaW5kaWNhdGluZyBob3cgaW1wb3J0YW50IGVhY2ggbG9jYXRpb24gaXMgd2l0aCByZXNwZWN0IHRvIHRoZSBjbGFzcyB1bmRlciBjb25zaWRlcmF0aW9uLiBGb3IgaW5zdGFuY2UsIGdpdmVuIGFuIGltYWdlIGZlZCBpbnRvIGEgY2F0LXZlcnN1cy1kb2cgQ05OLCBDQU0gdmlzdWFsaXphdGlvbiBhbGxvd3MgeW91IHRvIGdlbmVyYXRlIGEgaGVhdG1hcCBmb3IgdGhlIGNsYXNzIOKAnGNhdCzigJ0gaW5kaWNhdGluZyBob3cgY2F0LWxpa2UgZGlmZmVyZW50IHBhcnRzIG9mIHRoZSBpbWFnZSBhcmUsIGFuZCBhbHNvIGEgaGVhdG1hcCBmb3IgdGhlIGNsYXNzIOKAnGRvZyzigJ0gaW5kaWNhdGluZyBob3cgZG9nLWxpa2UgcGFydHMgb2YgdGhlIGltYWdlIGFyZS4KClRoZSBzcGVjaWZpYyBpbXBsZW1lbnRhdGlvbiB5b3XigJlsbCB1c2UgaXMgdGhlIG9uZSBkZXNjcmliZWQgaW4g4oCcR3JhZC1DQU06IFZpc3VhbCBFeHBsYW5hdGlvbnMgZnJvbSBEZWVwIE5ldHdvcmtzIHZpYSBHcmFkaWVudC1iYXNlZCBMb2NhbGl6YXRpb24u4oCdZm9vdG5vdGU6W1JhbXByYXNhYXRoIFIuIFNlbHZhcmFqdSBldCBhbC4sIENvcm5lbGwgVW5pdmVyc2l0eSBMaWJyYXJ5LCBNYXJjaCAyMSwgMjAxNywgaHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzE2MTAuMDIzOTEuXS4gSXQgY29uc2lzdHMgb2YgdGFraW5nIHRoZSBvdXRwdXQgZmVhdHVyZSBtYXAgb2YgYSBjb252b2x1dGlvbiBsYXllciwgZ2l2ZW4gYW4gaW5wdXQgaW1hZ2UsIGFuZCB3ZWlnaGluZyBldmVyeSBjaGFubmVsIGluIHRoYXQgZmVhdHVyZSBtYXAgYnkgdGhlIGdyYWRpZW50IG9mIHRoZSBjbGFzcyB3aXRoIHJlc3BlY3QgdG8gdGhlIGNoYW5uZWwuIEludHVpdGl2ZWx5LCBvbmUgd2F5IHRvIHVuZGVyc3RhbmQgdGhpcyB0cmljayBpcyB0aGF0IHlvdeKAmXJlIHdlaWdodGluZyBhIHNwYXRpYWwgbWFwIG9mIOKAnGhvdyBpbnRlbnNlbHkgdGhlIGlucHV0IGltYWdlIGFjdGl2YXRlcyBkaWZmZXJlbnQgY2hhbm5lbHPigJ0gYnkg4oCcaG93IGltcG9ydGFudCBlYWNoIGNoYW5uZWwgaXMgd2l0aCByZWdhcmQgdG8gdGhlIGNsYXNzLOKAnSByZXN1bHRpbmcgaW4gYSBzcGF0aWFsIG1hcCBvZiDigJxob3cgaW50ZW5zZWx5IHRoZSBpbnB1dCBpbWFnZSBhY3RpdmF0ZXMgdGhlIGNsYXNzLuKAnQoKTGV0J3MgZGVtb25zdHJhdGUgd2l0aCBvdXIgZG9nIGltYWdlLgoKYGBge3J9CiMgVGhpcyBpcyB0aGUgcHJlZGljdGlvbiB2ZWN0b3IgZm9yIG91ciBkb2cKZG9nX291dHB1dCA8LSBtb2RlbCRvdXRwdXRbLCAxXQoKIyBUaGUgaXMgdGhlIG91dHB1dCBmZWF0dXJlIG1hcCBvZiB0aGUgYGNvbnYyZF8zYCBsYXllciwgdGhlIGxhc3QKIyBjb252b2x1dGlvbmFsIGxheWVyIGluIG91ciBDYXRzIHZzIERvZ3MgbW9kZWwgdGhhdCB3ZSBpbXBvcnRlZCBlYXJsaWVyCmxhc3RfY29udl9sYXllciA8LSBtb2RlbCAlPiUgZ2V0X2xheWVyKCJjb252MmRfMyIpCgojIFRoaXMgaXMgdGhlIGdyYWRpZW50IG9mIHRoZSAiZG9nIiBjbGFzcyB3aXRoIHJlZ2FyZCB0byB0aGUgb3V0cHV0CiMgZmVhdHVyZSBtYXAgb2YgYGNvbnYyZF8zYApncmFkcyA8LSBrX2dyYWRpZW50cyhkb2dfb3V0cHV0LCBsYXN0X2NvbnZfbGF5ZXIkb3V0cHV0KVtbMV1dCgojIFRoaXMgaXMgYSB2ZWN0b3Igb2Ygc2hhcGUgKDEyOCwpLCB3aGVyZSBlYWNoIGVudHJ5IGlzIHRoZSBtZWFuCiMgaW50ZW5zaXR5IG9mIHRoZSBncmFkaWVudCBvdmVyIGEgc3BlY2lmaWMgZmVhdHVyZSBtYXAgY2hhbm5lbApwb29sZWRfZ3JhZHMgPC0ga19tZWFuKGdyYWRzLCBheGlzID0gYygxLCAyLCAzKSkKCiMgVGhpcyBmdW5jdGlvbiBhbGxvd3MgdXMgdG8gYWNjZXNzIHRoZSB2YWx1ZXMgb2YgdGhlIHF1YW50aXRpZXMgd2UganVzdCBkZWZpbmVkOgojIGBwb29sZWRfZ3JhZHNgIGFuZCB0aGUgb3V0cHV0IGZlYXR1cmUgbWFwIG9mIGBjb252MmRfM2AsCiMgZ2l2ZW4gYSBzYW1wbGUgaW1hZ2UKaXRlcmF0ZSA8LSBrX2Z1bmN0aW9uKGxpc3QobW9kZWwkaW5wdXQpLAogICAgICAgICAgICAgICAgICAgICAgbGlzdChwb29sZWRfZ3JhZHMsIGxhc3RfY29udl9sYXllciRvdXRwdXRbMSwsLF0pKQoKIyBUaGVzZSBhcmUgdGhlIHZhbHVlcyBvZiB0aGVzZSB0d28gcXVhbnRpdGllcywgYXMgYXJyYXlzLAojIGdpdmVuIG91ciBzYW1wbGUgaW1hZ2Ugb2YgdHdvIGVsZXBoYW50cwpjKHBvb2xlZF9ncmFkc192YWx1ZSwgY29udl9sYXllcl9vdXRwdXRfdmFsdWUpICU8LSUgaXRlcmF0ZShsaXN0KGltZ190ZW5zb3IpKQoKIyBXZSBtdWx0aXBseSBlYWNoIGNoYW5uZWwgaW4gdGhlIGZlYXR1cmUgbWFwIGFycmF5IGJ5CiMgImhvdyBpbXBvcnRhbnQgdGhpcyBjaGFubmVsIGlzIiB3aXRoIHJlZ2FyZCB0byB0aGUgZG9nIGNsYXNzCmZvciAoaSBpbiAxOjEyOCkgewogIGNvbnZfbGF5ZXJfb3V0cHV0X3ZhbHVlWywsaV0gPC0gCiAgICBjb252X2xheWVyX291dHB1dF92YWx1ZVssLGldICogcG9vbGVkX2dyYWRzX3ZhbHVlW1tpXV0gCn0KCiMgVGhlIGNoYW5uZWwtd2lzZSBtZWFuIG9mIHRoZSByZXN1bHRpbmcgZmVhdHVyZSBtYXAKIyBpcyBvdXIgaGVhdG1hcCBvZiBjbGFzcyBhY3RpdmF0aW9uCmhlYXRtYXAgPC0gYXBwbHkoY29udl9sYXllcl9vdXRwdXRfdmFsdWUsIGMoMSwyKSwgbWVhbikKYGBgCgpXZSBjYW4gbm93IGNyZWF0ZSB0aGUgaGVhdG1hcCBhbmQgc2F2ZSBpdCB0byBkaXNrIGZvciBsYXRlci4gTm90ZSB0aGF0IHRoZQpoZWF0bWFwIHdpZHRoIGFuZCBoZWlnaHQgbmVlZCB0byBiZSB0aGUgc2FtZSBhcyBvdXIgcHJlcHJvY2Vzc2VkIGltYWdlLCB3aGljaAp3ZSBjcm9wcGVkIHRvIDE1MHgxNTAuCgpgYGB7cn0KaGVhdG1hcCA8LSBwbWF4KGhlYXRtYXAsIDApIApoZWF0bWFwIDwtIGhlYXRtYXAgLyBtYXgoaGVhdG1hcCkKd3JpdGVfaGVhdG1hcCA8LSBmdW5jdGlvbihoZWF0bWFwLCBmaWxlbmFtZSwgd2lkdGggPSAxNTAsIGhlaWdodCA9IDE1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICBiZyA9ICJ3aGl0ZSIsIGNvbCA9IHRlcnJhaW4uY29sb3JzKDEyKSkgewogIHBuZyhmaWxlbmFtZSwgd2lkdGggPSB3aWR0aCwgaGVpZ2h0ID0gaGVpZ2h0LCBiZyA9IGJnKQogIG9wID0gcGFyKG1hciA9IGMoMCwwLDAsMCkpCiAgb24uZXhpdCh7cGFyKG9wKTsgZGV2Lm9mZigpfSwgYWRkID0gVFJVRSkKICByb3RhdGUgPC0gZnVuY3Rpb24oeCkgdChhcHBseSh4LCAyLCByZXYpKQogIGltYWdlKHJvdGF0ZShoZWF0bWFwKSwgYXhlcyA9IEZBTFNFLCBhc3AgPSAxLCBjb2wgPSBjb2wpCn0Kd3JpdGVfaGVhdG1hcChoZWF0bWFwLCAiZG9nX2hlYXRtYXAucG5nIikgCmBgYAoKYGBge3J9CmtuaXRyOjppbmNsdWRlX2dyYXBoaWNzKCJkb2dfaGVhdG1hcC5wbmciKQpgYGAKCk5vdyB3ZSBjYW4gdXNlIHRoZSBtYWdpY2sgcGFja2FnZSB0byBnZW5lcmF0ZSBhbiBpbWFnZSB0aGF0IHN1cGVyaW1wb3NlcyB0aGUgb3JpZ2luYWwgaW1hZ2Ugd2l0aCB0aGUgaGVhdG1hcCB3ZSBqdXN0IG9idGFpbmVkLiBXZSBjYW4gc2VlIHRoYXQgdGhlIGhlYXRtYXAgaXMgZm9jdXNlZCBvbiB0aGUgZG9ncyBmYWNlIGFuZCwgbW9yZSBzcGVjaWZpY2FsbHksIG9uIHRoZSBsZWZ0IGV5ZSBhbmQgdXBwZXIgcGFydCBvZiB0aGUgc25vdXQgb2YgdGhlIGRvZy4KCmBgYHtyfQojIFJlYWQgdGhlIG9yaWdpbmFsIGVsZXBoYW50IGltYWdlIGFuZCBpdCdzIGdlb21ldHJ5CmltYWdlIDwtIGltYWdlX3JlYWQoaW1nX3BhdGgpCmluZm8gPC0gaW1hZ2VfaW5mbyhpbWFnZSkgCmdlb21ldHJ5IDwtIHNwcmludGYoIiVkeCVkISIsIGluZm8kd2lkdGgsIGluZm8kaGVpZ2h0KSAKCiMgQ3JlYXRlIGEgYmxlbmRlZCAvIHRyYW5zcGFyZW50IHZlcnNpb24gb2YgdGhlIGhlYXRtYXAgaW1hZ2UKcGFsIDwtIGNvbDJyZ2IodmlyaWRpcygyMCksIGFscGhhID0gVFJVRSkgCmFscGhhIDwtIGZsb29yKHNlcSgwLCAyNTUsIGxlbmd0aCA9IG5jb2wocGFsKSkpIApwYWxfY29sIDwtIHJnYih0KHBhbCksIGFscGhhID0gYWxwaGEsIG1heENvbG9yVmFsdWUgPSAyNTUpCndyaXRlX2hlYXRtYXAoaGVhdG1hcCwgImRvZ19vdmVybGF5LnBuZyIsIAogICAgICAgICAgICAgIHdpZHRoID0gMTQsIGhlaWdodCA9IDE0LCBiZyA9IE5BLCBjb2wgPSBwYWxfY29sKSAKCiMgT3ZlcmxheSB0aGUgaGVhdG1hcAppbWFnZV9yZWFkKCJkb2dfb3ZlcmxheS5wbmciKSAlPiUgCiAgaW1hZ2VfcmVzaXplKGdlb21ldHJ5LCBmaWx0ZXIgPSAicXVhZHJhdGljIikgJT4lIAogIGltYWdlX2NvbXBvc2l0ZShpbWFnZSwgb3BlcmF0b3IgPSAiYmxlbmQiLCBjb21wb3NlX2FyZ3MgPSAiMjAiKSAlPiUKICBwbG90KCkgCmBgYAoKIyMgU3VwZXJwaXhlbHMgd2l0aCBMSU1FCgpUaGUgTElNRSBwYWNrYWdlIG9mZmVycyBhIHNpbWlsYXIgY2FwYWJpbGl0eSByZWZlcnJlZCB0byBhcyBzdXBlcnBpeGVscy4gU3VwZXJwaXhlbHMKaXMgdGhlIHByb2Nlc3Mgb2Ygc2VnbWVudGluZyBhbiBpbWFnZS4gV2UgY2FuIHVzZSB0aGlzIGNvbmNlcHQgdG8gaGVscCBpZGVudGlmeQpwYXJ0cyBvZiBhbiBpbWFnZSB0aGF0IGV4cGxhaW4gb3VyIG1vZGVsJ3MgcHJlZGljdGlvbi4KCmBgYHtyfQpwbG90X3N1cGVycGl4ZWxzKGltZ19wYXRoKQpgYGAKCkZpcnN0LCB3ZSdsbCBjcmVhdGUgYSBmdW5jdGlvbiB0aGF0IHByZXByb2Nlc3NlcyBvdXIgaW1hZ2UuCgpgYGB7cn0KaW1hZ2VfcHJlcCA8LSBmdW5jdGlvbih4KSB7CiAgYXJyYXlzIDwtIGxhcHBseSh4LCBmdW5jdGlvbihwYXRoKSB7CiAgaW1nIDwtIGltYWdlX2xvYWQocGF0aCwgdGFyZ2V0X3NpemUgPSBjKDE1MCwgMTUwKSkKICB4IDwtIGltYWdlX3RvX2FycmF5KGltZykKICB4IDwtIGFycmF5X3Jlc2hhcGUoeCwgYygxLCBkaW0oeCkpKQogIHggPC0geCAvIDI1NQogIH0pCiAgZG8uY2FsbChhYmluZDo6YWJpbmQsIGMoYXJyYXlzLCBsaXN0KGFsb25nID0gMSkpKQp9CmBgYAoKTmV4dCwgd2UnbGwgY3JlYXRlIGEgbGltZSBleHBsYWluZXIgb2JqZWN0IHRoYXQgdGFrZXMgb3VyIGltYWdlIHBhdGgsIG91cgpjYXRzX2FuZF9kb2dzX3NtYWxsXzIuaDUgbW9kZWwgb2JqZWN0LCBhbmQgdGhlIGltYWdlIHByZXByb2Nlc3NpbmcgZnVuY3Rpb24uIEFsc28sCnNpbmNlIGtlcmFzIGRvZXMgbm90IHN1cHBseSBjbGFzcyBsYWJlbHMgaW4gdGhlIG1vZGVsIG9iamVjdCB3ZSBwYXNzIGEgdmVjdG9yCnRoYXQgcmVsYXRlcyB0aGUgbGFiZWwgdG8gdGhlIDAtMSBwcmVkaWN0aW9ucy4KCmBgYHtyfQptb2RlbF9sYWJlbHMgPC0gYygiMCIgPSAiY2F0IiwgIjEiID0gImRvZyIpCmV4cGxhaW5lciA8LSBsaW1lKGltZ19wYXRoLCBhc19jbGFzc2lmaWVyKG1vZGVsLCBtb2RlbF9sYWJlbHMpLCBpbWFnZV9wcmVwKQpgYGAKCldlIGNhbiBub3cgcnVuIHRoZSBgZXhwbGFpbigpYCBmdW5jdGlvbiB3aGljaCBpbXBsZW1lbnRzIHRoZSBtZXRob2RvbG9neSBpbgpodHRwczovL2FyeGl2Lm9yZy9hYnMvMTYwMi4wNDkzOC4gU2VlIGh0dHBzOi8vbGltZS5kYXRhLWltYWdpbmlzdC5jb20vIGZvciBtb3JlCmRldGFpbHMuIEluIHRoaXMgZXhhbXBsZSwgd2UgYXJlIHNlYXJjaGluZyBmb3IgdGhlIDM1IHN1cGVycGl4ZWxzIHRoYXQgaGVscCB0bwpleHBsYWluIG91ciBtb2RlbCdzIHByZWRpY3Rpb24uIFRoZSBjdXJyZW50IHNldHRpbmdzIHJlc3VsdCBpbiBhbiBleHBsYW5hdGlvbgpmaXQgKCRSXjIkKSBvZiAwLjcuIFlvdSBjb3VsZCB0d2VhayB0aGUgcGFyYW1ldGVyIHNldHRpbmdzIGZvciBgZXhwbGFpbigpYCB0bwp0cnkgaW5jcmVhc2UgdGhlIGV4cGxhbmF0aW9uIGZpdC4gV2Ugc2VlIHRoYXQgdGhlIGZhY2Ugb2YgdGhlIGRvZyBpcyBpZGVudGlmaWVkCmFzIG9uZSBvZiB0aGUgc3VwZXJwaXhlbHMgdGhhdCBoZWxwcyB0byBleHBsYWluIHRoZSBjb3JyZWN0IHByZWRpY3Rpb24uCgpgYGB7cn0KZXhwbGFuYXRpb24gPC0gZXhwbGFpbigKICBpbWdfcGF0aCwgCiAgZXhwbGFpbmVyLAogIG5fbGFiZWxzID0gMiwKICBuX2ZlYXR1cmVzID0gMzUsCiAgbl9zdXBlcnBpeGVscyA9IDM1LAogIHdlaWdodCA9IDEwCiAgKQpgYGAKCmBgYHtyfQpwbG90X2ltYWdlX2V4cGxhbmF0aW9uKGV4cGxhbmF0aW9uKQpgYGAKCkFuIGFsdGVybmF0aXZlIHZpZXcgdGhhdCBwdXRzIG1vcmUgZm9jdXMgb24gdGhlIHJlbGV2YW50IHN1cGVycGl4ZWxzLCBidXQgcmVtb3Zlcwp0aGUgY29udGV4dCBjYW4gYmUgc2VlbiBieSB1c2luZyBkaXNwbGF5ID0gJ2Jsb2NrJzoKCmBgYHtyfQpwbG90X2ltYWdlX2V4cGxhbmF0aW9uKGV4cGxhbmF0aW9uLCBkaXNwbGF5ID0gJ2Jsb2NrJykKYGBgCgo=