Overview

This is a reproduction of the workflow for creating many models, which comes from Chapter 25 of R for Data Science. The purpose was to learn the concepts. I stick pretty close to the book, but you may find me taking a few creative liberties.

The Gapminder Analysis illustrates a workflow for integrating modelling to multiple subsets of data using the modelr and broom packages. In addition, the purrr mapping functions are integrated into the analysis workflow. The ultimate goal is to showcase the concepts that enable analysts to visualize the models, extracting meaningful information on residuals, r-squared values, etc.

The details behind creating many models cover both creating and simplifying nested data frames. These skills are necessary for the modelling workflow.


Prerequisites

library(modelr)
options(na.action = na.warn)
library(broom)
library(tidyverse) # ggplot2, purrr, dplyr, tidyr, readr, tibble
library(gridExtra) # grid.arange()
library(gapminder) # gapminder data

Gapminder Analysis: Multiple Models Workflow

gapminder 

Question to answer: “How does life expectancy (lifeExp) change over time (year) for each country (country)?”

gapminder %>%
    ggplot(aes(year, lifeExp, group = country)) + 
    geom_line(alpha = 0.35)

Problems:

Solution: Use models. Model captures trend and residuals capture remaining pattern (if any).

Process for Single Country:

nz <- filter(gapminder, country == "New Zealand")
p1 <- nz %>%
    ggplot(aes(year, lifeExp)) + 
    geom_line() + 
    ggtitle("Full data = ")
nz_mod <- lm(lifeExp ~ year, data = nz) # Model
p2 <- nz %>%
    add_predictions(nz_mod) %>%
    ggplot(aes(year, pred)) +
    geom_line() + 
    ggtitle("Linear trend + ")
p3 <- nz %>%
    add_residuals(nz_mod) %>%
    ggplot(aes(year, resid)) +
    geom_line() + 
    ggtitle("Remaining pattern")
    
grid.arrange(p1, p2, p3, ncol=3)

Nested data (nest)

Now we need to extend this analysis to many other countries. We do this using a map function from purrr by extracting out a common function and using map to apply to all elements of a list or data frame.

Problem: Data is structured differently. We need to repeat the map function one a subset of rows instead of each single row.

Solution: Nested data frame. Easiest way is to use group_by() then pass to nest().

by_country <- gapminder %>%
    group_by(country, continent) %>%
    nest()
by_country %>% head 

Can drill into the data column.

by_country$data[[1]] %>% head()

List-columns (use map on nested columns)

Next, need a model function to iterate over.

country_model <- function(df) {
    lm(lifeExp ~ year, data = df)
}

Then apply to each country using purrr::map(). The workflow stores the model as part of the nested data frame.

by_country <- by_country %>%
    mutate(model = map(.x = data, .f = country_model))
by_country %>% head()

Follow the same process to add predictions and residuals.

by_country <- by_country %>%
    mutate(
        preds  = map2(.x = data, .y = model, .f = add_predictions),
        resids = map2(.x = data, .y = model, .f = add_residuals)
    )
by_country %>% head()

Unnesting (unnest)

Now we need to plot, but this is very difficult in current structure.

Problem: The nested data frame structure makes plotting difficult. Need to be able to plot, but structure is a list of data frames.

Solution: Unnest with unnest() function.

preds <- unnest(data = by_country, preds)
preds %>% head()
resids <- unnest(data = by_country, resids)
resids %>% head()

First, take a look at trends (preds):

preds %>%
    ggplot(aes(year, pred, group = country)) +
    geom_line(alpha = 0.35) +
    facet_wrap(~ continent)

Second, take a look at resids (resids):

resids %>%
    ggplot(aes(year, resid, group = country)) +
    geom_line(alpha = 0.35) + 
    facet_wrap(~ continent)

Upon inspection of residuals, we can get the following takeaways:

  1. It looks like we missed some mild pattern.

  2. Africa has a weird wave motion in the residuals indicating something interesting that needs further investigation.

Assessing model quality (broom package)

Quick overview of broom package

The broom package provides three general tools for turning models into tidy data frames:

  1. broom::glance(model) returns a row for each model. Each column gives a model summary: either a measure of model quality, or complexity, or a combination of the two.

  2. broom::tidy(model) returns a row for each coefficient in the model. Each column gives information about the estimate or its variability.

  3. broom::augment(model, data) returns a row for each row in data, adding extra values like residuals, and influence statistics.

glance(nz_mod)
tidy(nz_mod)
augment(nz_mod, nz) %>% head()

Back to assessing the model quality

We want to use broom::glance() to get the lowest r.squared values. Two steps:

  1. Use map() to apply glance() to the models.

  2. Use unnest() to return the model statistics. Set .drop = TRUE to suppress unnested list-columns.

glance <- by_country %>% 
    mutate(glance = map(model, broom::glance)) %>% 
    unnest(glance, .drop = TRUE) %>%
    arrange(r.squared) 
glance %>% head()

Visualize the r-squared values:

Africa has some low r-squared values.

glance %>%
    ggplot(aes(continent, r.squared)) + 
    geom_jitter()

Review countries with low r-squared values:

bad_fit <- filter(glance, r.squared <= 0.25)
gapminder %>%
    filter(country %in% unique(bad_fit$country)) %>%
    ggplot(aes(year, lifeExp, color = country, group = country)) +
    geom_line()

Explanation is:

  • Rwanda genocide in late 1980’s through early 2000’s.
  • AIDS epidemic affecting African countries in 1990s through 2000s.

Exercises

I focus specifically on Exercise 1 as it pertains to extending the Gapminder analysis.

Exercise 1

A linear trend seems to be slightly too simple for the overall trend. Can you do better with a quadratic polynomial? How can you interpret the coefficients of the quadratic? (Hint you might want to transform year so that it has mean zero.)

Instead of jumping to 4th order polynomial, I first want to see which model appears to have the best fit on a subset of the data. First, I create a polynomial model with splines::ns() on a subset of the data. I use the New Zealand subset, nz. I loop through models with increasing polynomial complexity.

library(splines)
# Plot polynomial functions from order 1 to 5 on nz data
for (i in 1:5) {
    # Model
    nz_mod <- lm(lifeExp ~ ns(year, i), data = nz)
    
    # Visualize data
    p1 <- nz %>%
        ggplot(aes(year, lifeExp)) + 
        geom_line() + 
        ggtitle("Full data = ")
    
    # Visualize model
    p2 <- nz %>%
        add_predictions(nz_mod) %>%
        ggplot(aes(year, pred)) +
        geom_line() + 
        ggtitle("Linear trend + ")
    
    # Visualize residuals
    p3 <- nz %>%
        add_residuals(nz_mod) %>%
        ggplot(aes(year, resid)) +
        geom_line() + 
        ggtitle("Remaining pattern") +
        # Set limits to see improvement on same scale
        scale_y_continuous(limits = c(-1.2, 1.2)) 
    
    # Output in grid    
    grid.arrange(p1, p2, p3, ncol=3,
                 top = stringr::str_c("Polynomial: Order = ", i, sep = ""))
}

Fourth and fifth order polynomials have much lower residuals in the remaining pattern. Let’s go with the quadratic.

Next, we apply the model to the full data set as part of a nested data frame.

by_country <- gapminder %>%
    group_by(country, continent) %>%
    nest()
country_model_4 <- function(df) {
    lm(lifeExp ~ ns(year, 4), data = df)
}
by_country <- by_country %>%
    mutate(model = map(.x = data, .f = country_model_4))
by_country %>% head()

Assess the model quality:

glance <- by_country %>%
    mutate(glance = map(model, broom::glance)) %>%
    unnest(glance, .drop = TRUE) 
glance %>%
    ggplot(aes(continent, r.squared)) +
    geom_jitter() +
    scale_y_continuous(limits = c(0,1))

The r.squared improved considerably with a more flexible, quadratic model.

Let’s visualize outliers with a boxplot:

glance %>%
    ggplot(aes(continent, r.squared)) +
    geom_boxplot()

Use r.squared <= 0.8 as a limit to visualize “low” model fits.

bad_fit <- filter(glance, r.squared <= 0.8)
preds <- by_country %>%
    filter(country %in% unique(bad_fit$country)) %>%
    mutate(preds = map2(.x = data, .y = model, .f = add_predictions)) %>%
    unnest(preds, .drop = TRUE) %>%
    select(-(pop:gdpPercap)) 
preds %>%
    ggplot(aes(year, lifeExp, color = country, group = country)) +
    geom_line() + 
    geom_line(aes(x = year, y = pred, color = country, group = country), 
              linetype = "dashed", data = preds)

The deviations from the model are due to:

  1. Cambodia: Impact of the Vietnam war in through the 1970s.

  2. Rwanda: Impact of Rwanda genocide (as noted previously).

In summary, the quadratic model does a better job fitting the minor fluctuations in the data. Thus, outliers from the data significantly deviate from the normal pattern. The largest outliers tend to have dramatic effects due to significant events in the country’s history that caused life expectency to deviate from the norm.


Details behind Creating Many Models

This section is meant to go into greater detail on the functions used in the Gapminder analysis. It specifically focuses on creating list-columns within nested data frames and then simplifying list-columns into unnested (flat) data frames.

Creating list-columns (4 methods)

  1. With nesting: group_by() + tidyr::nest(): to convert grouped data that has list-column

  2. From vectorized functions: mutate() + vectorized function that returns a list

  3. From multivalued summaries: summarize() + summary function that returns a list

  4. From a named list: tibble::enframe()

With nesting

gapminder %>%
    group_by(country, continent) %>%
    nest() %>%
    head()

Alternatively, can use on ungrouped data frame by specifying data columns:

gapminder %>%
    nest(year:gdpPercap) %>%
    head()

From vectorized functions

df <- tibble(x1 = c("a,b,c", "d,e,f,g"))
df %>%
    mutate(x2 = stringr::str_split(x1, ","))

Use unnest() to handle this.

df %>%
    mutate(x2 = stringr::str_split(x1, ",")) %>%
    unnest()

Can also use tidyr::separate_rows():

df %>% separate_rows(x1, sep = ",")

Using map(), map2(), pmap(), or invoke_map():

sim <- tribble(
    ~f,      ~params,
    "runif", list(min = -1, max = -1),
    "rnorm", list(sd = 5),
    "rpois", list(lambda = 10)
)
sim %>%
    mutate(sims = invoke_map(f, params, n = 10))

From multivalued summaries

Problem: One restriction of summarise() is that is only works with summary functions that return a single value. For example, cannot be used with quantile().

mtcars %>%
    group_by(cyl) %>%
    summarise(q = quantile(mpg))

Above code results in error. Pass functions that return lists as a list to get nested data frame. Can then unnest.

probs <- c(0.01, 0.25, 0.5, 0.75, 0.99)
mtcars %>%
    group_by(cyl) %>%
    summarise(p = list(probs), 
              q = list(quantile(mpg))) %>%
    unnest()

From a named list

tibble::enframe() to create nested data frame from nested list.

x <- list(
    a = 1:5,
    b = 3:4, 
    c = 5:6
    )
x
$a
[1] 1 2 3 4 5

$b
[1] 3 4

$c
[1] 5 6
enframe(x) %>% unnest()

Can iterate over names and values using map2().

df <- enframe(x)
df
df %>%
    mutate(summary = map2_chr(name, value, ~ stringr::str_c(.x, ": ", .y[[1]])))

Simplifying list-columns

Need to be able to convert list columns back to atomic vector or set of atomic vectors (i.e. a flat data frame). Two methods:

  1. If want single value: mutate() + (map_lgl() | map_int() | map_dbl() | map_chr()). These map functions create atomic vectors.

  2. If want many values: unnest()

List to vector

df <- tribble(
  ~x,
  letters[1:5],
  1:3,
  runif(5)
)
  
df %>% mutate(
  type = map_chr(x, typeof),
  length = map_int(x, length)
)

Shortcuts: Use names of nested list items to drill into lists.

df <- tribble(
  ~x,
  list(a = 1, b = 2),
  list(a = 2, c = 4)
)
df %>% mutate(
  a = map_dbl(x, "a", .null = NA_real_),
  b = map_dbl(x, "b", .null = NA_real_) # Throws error if no NA handling
)

Unnesting

Unnest to get the entire sub-list items.

tibble(x = 1:2, y = list(1:4, 1))
tibble(x = 1:2, y = list(1:4, 1)) %>% unnest()
LS0tDQp0aXRsZTogJ0NoYXB0ZXIgMjU6IE1hbnkgTW9kZWxzJw0Kb3V0cHV0Og0KICBodG1sX25vdGVib29rOg0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICB0b2M6IHllcw0KICAgIHRvY19kZXB0aDogMw0KICBodG1sX2RvY3VtZW50Og0KICAgIHRoZW1lOiBmbGF0bHkNCiAgICB0b2M6IHllcw0KICAgIHRvY19kZXB0aDogMw0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0KbGlicmFyeShrbml0cikNCm9wdHNfY2h1bmskc2V0KGZpZy53aWR0aD01LCBmaWcuaGVpZ2h0PTMsIGZpZy5hbGlnbj0nY2VudGVyJywNCiAgICAgICAgICAgICAgIG1lc3NhZ2UgPSBGQUxTRSwgd2FybmluZyA9IEZBTFNFKQ0KYGBgDQoNCiMgT3ZlcnZpZXcNCg0KVGhpcyBpcyBhIHJlcHJvZHVjdGlvbiBvZiB0aGUgd29ya2Zsb3cgZm9yIGNyZWF0aW5nIG1hbnkgbW9kZWxzLCB3aGljaCBjb21lcyBmcm9tIFtDaGFwdGVyIDI1IG9mIF9SIGZvciBEYXRhIFNjaWVuY2VfXShodHRwOi8vcjRkcy5oYWQuY28ubnovbWFueS1tb2RlbHMuaHRtbCkuIFRoZSBwdXJwb3NlIHdhcyB0byBsZWFybiB0aGUgY29uY2VwdHMuIEkgc3RpY2sgcHJldHR5IGNsb3NlIHRvIHRoZSBib29rLCBidXQgeW91IG1heSBmaW5kIG1lIHRha2luZyBhIGZldyBjcmVhdGl2ZSBsaWJlcnRpZXMuDQoNClRoZSBHYXBtaW5kZXIgQW5hbHlzaXMgaWxsdXN0cmF0ZXMgYSB3b3JrZmxvdyBmb3IgaW50ZWdyYXRpbmcgbW9kZWxsaW5nIHRvIG11bHRpcGxlIHN1YnNldHMgb2YgZGF0YSB1c2luZyB0aGUgYG1vZGVscmAgYW5kIGBicm9vbWAgcGFja2FnZXMuIEluIGFkZGl0aW9uLCB0aGUgYHB1cnJyYCBtYXBwaW5nIGZ1bmN0aW9ucyBhcmUgaW50ZWdyYXRlZCBpbnRvIHRoZSBhbmFseXNpcyB3b3JrZmxvdy4gVGhlIHVsdGltYXRlIGdvYWwgaXMgdG8gc2hvd2Nhc2UgdGhlIGNvbmNlcHRzIHRoYXQgZW5hYmxlIGFuYWx5c3RzIHRvIHZpc3VhbGl6ZSB0aGUgbW9kZWxzLCBleHRyYWN0aW5nIG1lYW5pbmdmdWwgaW5mb3JtYXRpb24gb24gcmVzaWR1YWxzLCByLXNxdWFyZWQgdmFsdWVzLCBldGMuIA0KDQpUaGUgZGV0YWlscyBiZWhpbmQgY3JlYXRpbmcgbWFueSBtb2RlbHMgY292ZXIgYm90aCBjcmVhdGluZyBhbmQgc2ltcGxpZnlpbmcgbmVzdGVkIGRhdGEgZnJhbWVzLiBUaGVzZSBza2lsbHMgYXJlIG5lY2Vzc2FyeSBmb3IgdGhlIG1vZGVsbGluZyB3b3JrZmxvdy4NCg0KLS0tLQ0KDQojIFByZXJlcXVpc2l0ZXMNCg0KYGBge3J9DQpsaWJyYXJ5KG1vZGVscikNCm9wdGlvbnMobmEuYWN0aW9uID0gbmEud2FybikNCmxpYnJhcnkoYnJvb20pDQoNCmxpYnJhcnkodGlkeXZlcnNlKSAjIGdncGxvdDIsIHB1cnJyLCBkcGx5ciwgdGlkeXIsIHJlYWRyLCB0aWJibGUNCmxpYnJhcnkoZ3JpZEV4dHJhKSAjIGdyaWQuYXJhbmdlKCkNCg0KbGlicmFyeShnYXBtaW5kZXIpICMgZ2FwbWluZGVyIGRhdGENCmBgYA0KDQotLS0tDQoNCiMgR2FwbWluZGVyIEFuYWx5c2lzOiBNdWx0aXBsZSBNb2RlbHMgV29ya2Zsb3cNCg0KYGBge3J9DQpnYXBtaW5kZXIgDQpgYGANCg0KX19RdWVzdGlvbiB0byBhbnN3ZXI6X18gIkhvdyBkb2VzIGxpZmUgZXhwZWN0YW5jeSAoYGxpZmVFeHBgKSBjaGFuZ2Ugb3ZlciB0aW1lIChgeWVhcmApIGZvciBlYWNoIGNvdW50cnkgKGBjb3VudHJ5YCk/Ig0KDQpgYGB7ciwgZmlnLmFsaWduPSdjZW50ZXInfQ0KZ2FwbWluZGVyICU+JQ0KICAgIGdncGxvdChhZXMoeWVhciwgbGlmZUV4cCwgZ3JvdXAgPSBjb3VudHJ5KSkgKyANCiAgICBnZW9tX2xpbmUoYWxwaGEgPSAwLjM1KQ0KYGBgDQoNCl9fUHJvYmxlbXM6X18NCiAgDQogICogRGlmZmljdWx0IHRvIHNlZSB3aGF0J3MgZ29pbmcgb24uDQogICogR2VuZXJhbCB0cmVuZCBpcyBwb3NpdGl2ZSwgYnV0IHNvbWUgY291bnRyaWVzIGRvbid0IGZvbGxvdyB0aGUgZ3JvdXAgcGF0dGVybi4NCiAgKiBOZWVkIHRvIGJlIGFibGUgdG8gbWFrZSBjb3VudHJpZXMgbm90IGZvbGxvd2luZyBwYXR0ZXJuIGVhc2llciB0byBzdGFuZCBvdXQuDQoNCl9fU29sdXRpb246IF9fDQpVc2UgbW9kZWxzLiBNb2RlbCBjYXB0dXJlcyB0cmVuZCBhbmQgcmVzaWR1YWxzIGNhcHR1cmUgcmVtYWluaW5nIHBhdHRlcm4gKGlmIGFueSkuDQoNCl9fUHJvY2VzcyBmb3IgU2luZ2xlIENvdW50cnk6X18NCg0KYGBge3IgZmlnLndpZHRoPTEyfQ0KbnogPC0gZmlsdGVyKGdhcG1pbmRlciwgY291bnRyeSA9PSAiTmV3IFplYWxhbmQiKQ0KDQpwMSA8LSBueiAlPiUNCiAgICBnZ3Bsb3QoYWVzKHllYXIsIGxpZmVFeHApKSArIA0KICAgIGdlb21fbGluZSgpICsgDQogICAgZ2d0aXRsZSgiRnVsbCBkYXRhID0gIikNCg0KbnpfbW9kIDwtIGxtKGxpZmVFeHAgfiB5ZWFyLCBkYXRhID0gbnopICMgTW9kZWwNCg0KcDIgPC0gbnogJT4lDQogICAgYWRkX3ByZWRpY3Rpb25zKG56X21vZCkgJT4lDQogICAgZ2dwbG90KGFlcyh5ZWFyLCBwcmVkKSkgKw0KICAgIGdlb21fbGluZSgpICsgDQogICAgZ2d0aXRsZSgiTGluZWFyIHRyZW5kICsgIikNCg0KcDMgPC0gbnogJT4lDQogICAgYWRkX3Jlc2lkdWFscyhuel9tb2QpICU+JQ0KICAgIGdncGxvdChhZXMoeWVhciwgcmVzaWQpKSArDQogICAgZ2VvbV9saW5lKCkgKyANCiAgICBnZ3RpdGxlKCJSZW1haW5pbmcgcGF0dGVybiIpDQogICAgDQpncmlkLmFycmFuZ2UocDEsIHAyLCBwMywgbmNvbD0zKQ0KYGBgDQoNCiMjIE5lc3RlZCBkYXRhIChuZXN0KQ0KDQpOb3cgd2UgbmVlZCB0byBleHRlbmQgdGhpcyBhbmFseXNpcyB0byBtYW55IG90aGVyIGNvdW50cmllcy4gV2UgZG8gdGhpcyB1c2luZyBhIG1hcCBmdW5jdGlvbiBmcm9tIGBwdXJycmAgYnkgZXh0cmFjdGluZyBvdXQgYSBjb21tb24gZnVuY3Rpb24gYW5kIHVzaW5nIG1hcCB0byBhcHBseSB0byBhbGwgZWxlbWVudHMgb2YgYSBsaXN0IG9yIGRhdGEgZnJhbWUuIA0KDQpfX1Byb2JsZW06X18NCkRhdGEgaXMgc3RydWN0dXJlZCBkaWZmZXJlbnRseS4gV2UgbmVlZCB0byByZXBlYXQgdGhlIG1hcCBmdW5jdGlvbiBvbmUgYSBzdWJzZXQgb2Ygcm93cyBpbnN0ZWFkIG9mIGVhY2ggc2luZ2xlIHJvdy4NCg0KX19Tb2x1dGlvbjpfXyANCk5lc3RlZCBkYXRhIGZyYW1lLiBFYXNpZXN0IHdheSBpcyB0byB1c2UgYGdyb3VwX2J5KClgIHRoZW4gcGFzcyB0byBgbmVzdCgpYC4NCg0KYGBge3J9DQpieV9jb3VudHJ5IDwtIGdhcG1pbmRlciAlPiUNCiAgICBncm91cF9ieShjb3VudHJ5LCBjb250aW5lbnQpICU+JQ0KICAgIG5lc3QoKQ0KYnlfY291bnRyeSAlPiUgaGVhZCANCmBgYA0KDQpDYW4gZHJpbGwgaW50byB0aGUgYGRhdGFgIGNvbHVtbi4NCg0KYGBge3J9DQpieV9jb3VudHJ5JGRhdGFbWzFdXSAlPiUgaGVhZCgpDQpgYGANCg0KIyMgTGlzdC1jb2x1bW5zICh1c2UgbWFwIG9uIG5lc3RlZCBjb2x1bW5zKQ0KDQpOZXh0LCBuZWVkIGEgbW9kZWwgZnVuY3Rpb24gdG8gaXRlcmF0ZSBvdmVyLg0KDQpgYGB7cn0NCmNvdW50cnlfbW9kZWwgPC0gZnVuY3Rpb24oZGYpIHsNCiAgICBsbShsaWZlRXhwIH4geWVhciwgZGF0YSA9IGRmKQ0KfQ0KYGBgDQoNClRoZW4gYXBwbHkgdG8gZWFjaCBjb3VudHJ5IHVzaW5nIGBwdXJycjo6bWFwKClgLiBUaGUgd29ya2Zsb3cgc3RvcmVzIHRoZSBtb2RlbCBhcyBwYXJ0IG9mIHRoZSBuZXN0ZWQgZGF0YSBmcmFtZS4NCg0KYGBge3J9DQpieV9jb3VudHJ5IDwtIGJ5X2NvdW50cnkgJT4lDQogICAgbXV0YXRlKG1vZGVsID0gbWFwKC54ID0gZGF0YSwgLmYgPSBjb3VudHJ5X21vZGVsKSkNCmJ5X2NvdW50cnkgJT4lIGhlYWQoKQ0KYGBgDQoNCkZvbGxvdyB0aGUgc2FtZSBwcm9jZXNzIHRvIGFkZCBwcmVkaWN0aW9ucyBhbmQgcmVzaWR1YWxzLg0KDQpgYGB7cn0NCmJ5X2NvdW50cnkgPC0gYnlfY291bnRyeSAlPiUNCiAgICBtdXRhdGUoDQogICAgICAgIHByZWRzICA9IG1hcDIoLnggPSBkYXRhLCAueSA9IG1vZGVsLCAuZiA9IGFkZF9wcmVkaWN0aW9ucyksDQogICAgICAgIHJlc2lkcyA9IG1hcDIoLnggPSBkYXRhLCAueSA9IG1vZGVsLCAuZiA9IGFkZF9yZXNpZHVhbHMpDQogICAgKQ0KYnlfY291bnRyeSAlPiUgaGVhZCgpDQpgYGANCg0KDQojIyBVbm5lc3RpbmcgKHVubmVzdCkNCg0KTm93IHdlIG5lZWQgdG8gcGxvdCwgYnV0IHRoaXMgaXMgdmVyeSBkaWZmaWN1bHQgaW4gY3VycmVudCBzdHJ1Y3R1cmUuDQoNCl9fUHJvYmxlbTpfXyBUaGUgbmVzdGVkIGRhdGEgZnJhbWUgc3RydWN0dXJlIG1ha2VzIHBsb3R0aW5nIGRpZmZpY3VsdC4gTmVlZCB0byBiZSBhYmxlIHRvIHBsb3QsIGJ1dCBzdHJ1Y3R1cmUgaXMgYSBsaXN0IG9mIGRhdGEgZnJhbWVzLg0KDQpfX1NvbHV0aW9uOl9fIFVubmVzdCB3aXRoIGB1bm5lc3QoKWAgZnVuY3Rpb24uDQoNCmBgYHtyfQ0KcHJlZHMgPC0gdW5uZXN0KGRhdGEgPSBieV9jb3VudHJ5LCBwcmVkcykNCnByZWRzICU+JSBoZWFkKCkNCmBgYA0KDQpgYGB7cn0NCnJlc2lkcyA8LSB1bm5lc3QoZGF0YSA9IGJ5X2NvdW50cnksIHJlc2lkcykNCnJlc2lkcyAlPiUgaGVhZCgpDQpgYGANCg0KDQpGaXJzdCwgdGFrZSBhIGxvb2sgYXQgdHJlbmRzIChgcHJlZHNgKToNCg0KYGBge3J9DQpwcmVkcyAlPiUNCiAgICBnZ3Bsb3QoYWVzKHllYXIsIHByZWQsIGdyb3VwID0gY291bnRyeSkpICsNCiAgICBnZW9tX2xpbmUoYWxwaGEgPSAwLjM1KSArDQogICAgZmFjZXRfd3JhcCh+IGNvbnRpbmVudCkNCmBgYA0KDQpTZWNvbmQsIHRha2UgYSBsb29rIGF0IHJlc2lkcyAoYHJlc2lkc2ApOg0KDQpgYGB7cn0NCnJlc2lkcyAlPiUNCiAgICBnZ3Bsb3QoYWVzKHllYXIsIHJlc2lkLCBncm91cCA9IGNvdW50cnkpKSArDQogICAgZ2VvbV9saW5lKGFscGhhID0gMC4zNSkgKyANCiAgICBmYWNldF93cmFwKH4gY29udGluZW50KQ0KYGBgDQoNClVwb24gaW5zcGVjdGlvbiBvZiByZXNpZHVhbHMsIHdlIGNhbiBnZXQgdGhlIGZvbGxvd2luZyB0YWtlYXdheXM6DQogIA0KMS4gSXQgbG9va3MgbGlrZSB3ZSBtaXNzZWQgc29tZSBtaWxkIHBhdHRlcm4uDQoNCjIuIEFmcmljYSBoYXMgYSB3ZWlyZCB3YXZlIG1vdGlvbiBpbiB0aGUgcmVzaWR1YWxzIGluZGljYXRpbmcgc29tZXRoaW5nIGludGVyZXN0aW5nIHRoYXQgbmVlZHMgZnVydGhlciBpbnZlc3RpZ2F0aW9uLg0KDQoNCiMjIEFzc2Vzc2luZyBtb2RlbCBxdWFsaXR5IChicm9vbSBwYWNrYWdlKQ0KDQojIyMgUXVpY2sgb3ZlcnZpZXcgb2YgYnJvb20gcGFja2FnZQ0KDQpUaGUgYGJyb29tYCBwYWNrYWdlIHByb3ZpZGVzIHRocmVlIGdlbmVyYWwgdG9vbHMgZm9yIHR1cm5pbmcgbW9kZWxzIGludG8gdGlkeSBkYXRhIGZyYW1lczoNCg0KMS4gYGJyb29tOjpnbGFuY2UobW9kZWwpYCByZXR1cm5zIGEgcm93IGZvciBlYWNoIG1vZGVsLiBFYWNoIGNvbHVtbiBnaXZlcyBhIG1vZGVsIHN1bW1hcnk6IGVpdGhlciBhIG1lYXN1cmUgb2YgbW9kZWwgcXVhbGl0eSwgb3IgY29tcGxleGl0eSwgb3IgYSBjb21iaW5hdGlvbiBvZiB0aGUgdHdvLg0KDQoyLiBgYnJvb206OnRpZHkobW9kZWwpYCByZXR1cm5zIGEgcm93IGZvciBlYWNoIGNvZWZmaWNpZW50IGluIHRoZSBtb2RlbC4gRWFjaCBjb2x1bW4gZ2l2ZXMgaW5mb3JtYXRpb24gYWJvdXQgdGhlIGVzdGltYXRlIG9yIGl0cyB2YXJpYWJpbGl0eS4NCg0KMy4gYGJyb29tOjphdWdtZW50KG1vZGVsLCBkYXRhKWAgcmV0dXJucyBhIHJvdyBmb3IgZWFjaCByb3cgaW4gZGF0YSwgYWRkaW5nIGV4dHJhIHZhbHVlcyBsaWtlIHJlc2lkdWFscywgYW5kIGluZmx1ZW5jZSBzdGF0aXN0aWNzLg0KDQpgYGB7cn0NCmdsYW5jZShuel9tb2QpDQpgYGANCg0KYGBge3J9DQp0aWR5KG56X21vZCkNCmBgYA0KDQpgYGB7cn0NCmF1Z21lbnQobnpfbW9kLCBueikgJT4lIGhlYWQoKQ0KYGBgDQoNCiMjIyBCYWNrIHRvIGFzc2Vzc2luZyB0aGUgbW9kZWwgcXVhbGl0eQ0KDQpXZSB3YW50IHRvIHVzZSBgYnJvb206OmdsYW5jZSgpYCB0byBnZXQgdGhlIGxvd2VzdCBgci5zcXVhcmVkYCB2YWx1ZXMuIFR3byBzdGVwczoNCg0KMS4gVXNlIGBtYXAoKWAgdG8gYXBwbHkgYGdsYW5jZSgpYCB0byB0aGUgbW9kZWxzLg0KDQoyLiBVc2UgYHVubmVzdCgpYCB0byByZXR1cm4gdGhlIG1vZGVsIHN0YXRpc3RpY3MuIFNldCBgLmRyb3AgPSBUUlVFYCB0byBzdXBwcmVzcyB1bm5lc3RlZCBsaXN0LWNvbHVtbnMuICANCg0KYGBge3J9DQpnbGFuY2UgPC0gYnlfY291bnRyeSAlPiUgDQogICAgbXV0YXRlKGdsYW5jZSA9IG1hcChtb2RlbCwgYnJvb206OmdsYW5jZSkpICU+JSANCiAgICB1bm5lc3QoZ2xhbmNlLCAuZHJvcCA9IFRSVUUpICU+JQ0KICAgIGFycmFuZ2Uoci5zcXVhcmVkKSANCmdsYW5jZSAlPiUgaGVhZCgpDQpgYGANCg0KX19WaXN1YWxpemUgdGhlIHItc3F1YXJlZCB2YWx1ZXM6X18NCg0KQWZyaWNhIGhhcyBzb21lIGxvdyByLXNxdWFyZWQgdmFsdWVzLiANCg0KYGBge3J9DQpnbGFuY2UgJT4lDQogICAgZ2dwbG90KGFlcyhjb250aW5lbnQsIHIuc3F1YXJlZCkpICsgDQogICAgZ2VvbV9qaXR0ZXIoKQ0KYGBgDQoNCl9fUmV2aWV3IGNvdW50cmllcyB3aXRoIGxvdyByLXNxdWFyZWQgdmFsdWVzOl9fDQoNCmBgYHtyfQ0KYmFkX2ZpdCA8LSBmaWx0ZXIoZ2xhbmNlLCByLnNxdWFyZWQgPD0gMC4yNSkNCg0KZ2FwbWluZGVyICU+JQ0KICAgIGZpbHRlcihjb3VudHJ5ICVpbiUgdW5pcXVlKGJhZF9maXQkY291bnRyeSkpICU+JQ0KICAgIGdncGxvdChhZXMoeWVhciwgbGlmZUV4cCwgY29sb3IgPSBjb3VudHJ5LCBncm91cCA9IGNvdW50cnkpKSArDQogICAgZ2VvbV9saW5lKCkNCmBgYA0KDQpFeHBsYW5hdGlvbiBpczoNCg0KKiBSd2FuZGEgZ2Vub2NpZGUgaW4gbGF0ZSAxOTgwJ3MgdGhyb3VnaCBlYXJseSAyMDAwJ3MuDQoqIEFJRFMgZXBpZGVtaWMgYWZmZWN0aW5nIEFmcmljYW4gY291bnRyaWVzIGluIDE5OTBzIHRocm91Z2ggMjAwMHMuDQoNCg0KIyMjIEV4ZXJjaXNlcw0KDQpJIGZvY3VzIHNwZWNpZmljYWxseSBvbiBFeGVyY2lzZSAxIGFzIGl0IHBlcnRhaW5zIHRvIGV4dGVuZGluZyB0aGUgR2FwbWluZGVyIGFuYWx5c2lzLiAgDQoNCiMjIyMgRXhlcmNpc2UgMQ0KDQpfQSBsaW5lYXIgdHJlbmQgc2VlbXMgdG8gYmUgc2xpZ2h0bHkgdG9vIHNpbXBsZSBmb3IgdGhlIG92ZXJhbGwgdHJlbmQuIENhbiB5b3UgZG8gYmV0dGVyIHdpdGggYSBxdWFkcmF0aWMgcG9seW5vbWlhbD8gSG93IGNhbiB5b3UgaW50ZXJwcmV0IHRoZSBjb2VmZmljaWVudHMgb2YgdGhlIHF1YWRyYXRpYz8gKEhpbnQgeW91IG1pZ2h0IHdhbnQgdG8gdHJhbnNmb3JtIHllYXIgc28gdGhhdCBpdCBoYXMgbWVhbiB6ZXJvLilfDQoNCkluc3RlYWQgb2YganVtcGluZyB0byA0dGggb3JkZXIgcG9seW5vbWlhbCwgSSBmaXJzdCB3YW50IHRvIHNlZSB3aGljaCBtb2RlbCBhcHBlYXJzIHRvIGhhdmUgdGhlIGJlc3QgZml0IG9uIGEgc3Vic2V0IG9mIHRoZSBkYXRhLiBGaXJzdCwgSSBjcmVhdGUgYSBwb2x5bm9taWFsIG1vZGVsIHdpdGggYHNwbGluZXM6Om5zKClgIG9uIGEgc3Vic2V0IG9mIHRoZSBkYXRhLiBJIHVzZSB0aGUgTmV3IFplYWxhbmQgc3Vic2V0LCBgbnpgLiBJIGxvb3AgdGhyb3VnaCBtb2RlbHMgd2l0aCBpbmNyZWFzaW5nIHBvbHlub21pYWwgY29tcGxleGl0eS4NCg0KYGBge3IsIGZpZy53aWR0aD0xMn0NCmxpYnJhcnkoc3BsaW5lcykNCg0KIyBQbG90IHBvbHlub21pYWwgZnVuY3Rpb25zIGZyb20gb3JkZXIgMSB0byA1IG9uIG56IGRhdGENCmZvciAoaSBpbiAxOjUpIHsNCiAgICAjIE1vZGVsDQogICAgbnpfbW9kIDwtIGxtKGxpZmVFeHAgfiBucyh5ZWFyLCBpKSwgZGF0YSA9IG56KQ0KICAgIA0KICAgICMgVmlzdWFsaXplIGRhdGENCiAgICBwMSA8LSBueiAlPiUNCiAgICAgICAgZ2dwbG90KGFlcyh5ZWFyLCBsaWZlRXhwKSkgKyANCiAgICAgICAgZ2VvbV9saW5lKCkgKyANCiAgICAgICAgZ2d0aXRsZSgiRnVsbCBkYXRhID0gIikNCiAgICANCiAgICAjIFZpc3VhbGl6ZSBtb2RlbA0KICAgIHAyIDwtIG56ICU+JQ0KICAgICAgICBhZGRfcHJlZGljdGlvbnMobnpfbW9kKSAlPiUNCiAgICAgICAgZ2dwbG90KGFlcyh5ZWFyLCBwcmVkKSkgKw0KICAgICAgICBnZW9tX2xpbmUoKSArIA0KICAgICAgICBnZ3RpdGxlKCJMaW5lYXIgdHJlbmQgKyAiKQ0KICAgIA0KICAgICMgVmlzdWFsaXplIHJlc2lkdWFscw0KICAgIHAzIDwtIG56ICU+JQ0KICAgICAgICBhZGRfcmVzaWR1YWxzKG56X21vZCkgJT4lDQogICAgICAgIGdncGxvdChhZXMoeWVhciwgcmVzaWQpKSArDQogICAgICAgIGdlb21fbGluZSgpICsgDQogICAgICAgIGdndGl0bGUoIlJlbWFpbmluZyBwYXR0ZXJuIikgKw0KICAgICAgICAjIFNldCBsaW1pdHMgdG8gc2VlIGltcHJvdmVtZW50IG9uIHNhbWUgc2NhbGUNCiAgICAgICAgc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoLTEuMiwgMS4yKSkgDQogICAgDQogICAgIyBPdXRwdXQgaW4gZ3JpZCAgICANCiAgICBncmlkLmFycmFuZ2UocDEsIHAyLCBwMywgbmNvbD0zLA0KICAgICAgICAgICAgICAgICB0b3AgPSBzdHJpbmdyOjpzdHJfYygiUG9seW5vbWlhbDogT3JkZXIgPSAiLCBpLCBzZXAgPSAiIikpDQp9DQpgYGANCg0KRm91cnRoIGFuZCBmaWZ0aCBvcmRlciBwb2x5bm9taWFscyBoYXZlIG11Y2ggbG93ZXIgcmVzaWR1YWxzIGluIHRoZSByZW1haW5pbmcgcGF0dGVybi4gTGV0J3MgZ28gd2l0aCB0aGUgcXVhZHJhdGljLg0KDQpOZXh0LCB3ZSBhcHBseSB0aGUgbW9kZWwgdG8gdGhlIGZ1bGwgZGF0YSBzZXQgYXMgcGFydCBvZiBhIG5lc3RlZCBkYXRhIGZyYW1lLg0KDQpgYGB7cn0NCmJ5X2NvdW50cnkgPC0gZ2FwbWluZGVyICU+JQ0KICAgIGdyb3VwX2J5KGNvdW50cnksIGNvbnRpbmVudCkgJT4lDQogICAgbmVzdCgpDQoNCmNvdW50cnlfbW9kZWxfNCA8LSBmdW5jdGlvbihkZikgew0KICAgIGxtKGxpZmVFeHAgfiBucyh5ZWFyLCA0KSwgZGF0YSA9IGRmKQ0KfQ0KDQpieV9jb3VudHJ5IDwtIGJ5X2NvdW50cnkgJT4lDQogICAgbXV0YXRlKG1vZGVsID0gbWFwKC54ID0gZGF0YSwgLmYgPSBjb3VudHJ5X21vZGVsXzQpKQ0KYnlfY291bnRyeSAlPiUgaGVhZCgpDQpgYGANCg0KX19Bc3Nlc3MgdGhlIG1vZGVsIHF1YWxpdHk6X18NCg0KYGBge3J9DQpnbGFuY2UgPC0gYnlfY291bnRyeSAlPiUNCiAgICBtdXRhdGUoZ2xhbmNlID0gbWFwKG1vZGVsLCBicm9vbTo6Z2xhbmNlKSkgJT4lDQogICAgdW5uZXN0KGdsYW5jZSwgLmRyb3AgPSBUUlVFKSANCg0KZ2xhbmNlICU+JQ0KICAgIGdncGxvdChhZXMoY29udGluZW50LCByLnNxdWFyZWQpKSArDQogICAgZ2VvbV9qaXR0ZXIoKSArDQogICAgc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoMCwxKSkNCmBgYA0KDQpUaGUgYHIuc3F1YXJlZGAgaW1wcm92ZWQgY29uc2lkZXJhYmx5IHdpdGggYSBtb3JlIGZsZXhpYmxlLCBxdWFkcmF0aWMgbW9kZWwuIA0KDQpMZXQncyB2aXN1YWxpemUgb3V0bGllcnMgd2l0aCBhIGJveHBsb3Q6DQoNCmBgYHtyfQ0KZ2xhbmNlICU+JQ0KICAgIGdncGxvdChhZXMoY29udGluZW50LCByLnNxdWFyZWQpKSArDQogICAgZ2VvbV9ib3hwbG90KCkNCmBgYA0KDQpVc2UgYHIuc3F1YXJlZCA8PSAwLjhgIGFzIGEgbGltaXQgdG8gdmlzdWFsaXplICJsb3ciIG1vZGVsIGZpdHMuDQoNCmBgYHtyfQ0KYmFkX2ZpdCA8LSBmaWx0ZXIoZ2xhbmNlLCByLnNxdWFyZWQgPD0gMC44KQ0KDQpwcmVkcyA8LSBieV9jb3VudHJ5ICU+JQ0KICAgIGZpbHRlcihjb3VudHJ5ICVpbiUgdW5pcXVlKGJhZF9maXQkY291bnRyeSkpICU+JQ0KICAgIG11dGF0ZShwcmVkcyA9IG1hcDIoLnggPSBkYXRhLCAueSA9IG1vZGVsLCAuZiA9IGFkZF9wcmVkaWN0aW9ucykpICU+JQ0KICAgIHVubmVzdChwcmVkcywgLmRyb3AgPSBUUlVFKSAlPiUNCiAgICBzZWxlY3QoLShwb3A6Z2RwUGVyY2FwKSkgDQoNCnByZWRzICU+JQ0KICAgIGdncGxvdChhZXMoeWVhciwgbGlmZUV4cCwgY29sb3IgPSBjb3VudHJ5LCBncm91cCA9IGNvdW50cnkpKSArDQogICAgZ2VvbV9saW5lKCkgKyANCiAgICBnZW9tX2xpbmUoYWVzKHggPSB5ZWFyLCB5ID0gcHJlZCwgY29sb3IgPSBjb3VudHJ5LCBncm91cCA9IGNvdW50cnkpLCANCiAgICAgICAgICAgICAgbGluZXR5cGUgPSAiZGFzaGVkIiwgZGF0YSA9IHByZWRzKQ0KYGBgDQoNClRoZSBkZXZpYXRpb25zIGZyb20gdGhlIG1vZGVsIGFyZSBkdWUgdG86DQoNCjEuIENhbWJvZGlhOiBJbXBhY3Qgb2YgdGhlIFZpZXRuYW0gd2FyIGluIHRocm91Z2ggdGhlIDE5NzBzLg0KDQoyLiBSd2FuZGE6IEltcGFjdCBvZiBSd2FuZGEgZ2Vub2NpZGUgKGFzIG5vdGVkIHByZXZpb3VzbHkpLg0KDQpJbiBzdW1tYXJ5LCB0aGUgcXVhZHJhdGljIG1vZGVsIGRvZXMgYSBiZXR0ZXIgam9iIGZpdHRpbmcgdGhlIG1pbm9yIGZsdWN0dWF0aW9ucyBpbiB0aGUgZGF0YS4gVGh1cywgb3V0bGllcnMgZnJvbSB0aGUgZGF0YSBzaWduaWZpY2FudGx5IGRldmlhdGUgZnJvbSB0aGUgbm9ybWFsIHBhdHRlcm4uIFRoZSBsYXJnZXN0IG91dGxpZXJzIHRlbmQgdG8gaGF2ZSBkcmFtYXRpYyBlZmZlY3RzIGR1ZSB0byBzaWduaWZpY2FudCBldmVudHMgaW4gdGhlIGNvdW50cnkncyBoaXN0b3J5IHRoYXQgY2F1c2VkIGxpZmUgZXhwZWN0ZW5jeSB0byBkZXZpYXRlIGZyb20gdGhlIG5vcm0uIA0KDQotLS0tDQoNCiMgRGV0YWlscyBiZWhpbmQgQ3JlYXRpbmcgTWFueSBNb2RlbHMNCg0KVGhpcyBzZWN0aW9uIGlzIG1lYW50IHRvIGdvIGludG8gZ3JlYXRlciBkZXRhaWwgb24gdGhlIGZ1bmN0aW9ucyB1c2VkIGluIHRoZSBHYXBtaW5kZXIgYW5hbHlzaXMuIEl0IHNwZWNpZmljYWxseSBmb2N1c2VzIG9uIGNyZWF0aW5nIGxpc3QtY29sdW1ucyB3aXRoaW4gbmVzdGVkIGRhdGEgZnJhbWVzIGFuZCB0aGVuIHNpbXBsaWZ5aW5nIGxpc3QtY29sdW1ucyBpbnRvIHVubmVzdGVkIChmbGF0KSBkYXRhIGZyYW1lcy4NCg0KIyMgQ3JlYXRpbmcgbGlzdC1jb2x1bW5zICg0IG1ldGhvZHMpDQoNCjEuIF9fV2l0aCBuZXN0aW5nOl9fIGBncm91cF9ieSgpYCArIGB0aWR5cjo6bmVzdCgpYDogdG8gY29udmVydCBncm91cGVkIGRhdGEgdGhhdCBoYXMgbGlzdC1jb2x1bW4NCg0KMi4gX19Gcm9tIHZlY3Rvcml6ZWQgZnVuY3Rpb25zOl9fIGBtdXRhdGUoKWAgKyB2ZWN0b3JpemVkIGZ1bmN0aW9uIHRoYXQgcmV0dXJucyBhIGxpc3QNCg0KMy4gX19Gcm9tIG11bHRpdmFsdWVkIHN1bW1hcmllczpfXyBgc3VtbWFyaXplKClgICsgc3VtbWFyeSBmdW5jdGlvbiB0aGF0IHJldHVybnMgYSBsaXN0DQoNCjQuIF9fRnJvbSBhIG5hbWVkIGxpc3Q6X18gYHRpYmJsZTo6ZW5mcmFtZSgpYA0KDQojIyMgV2l0aCBuZXN0aW5nDQoNCmBgYHtyfQ0KZ2FwbWluZGVyICU+JQ0KICAgIGdyb3VwX2J5KGNvdW50cnksIGNvbnRpbmVudCkgJT4lDQogICAgbmVzdCgpICU+JQ0KICAgIGhlYWQoKQ0KYGBgDQoNCkFsdGVybmF0aXZlbHksIGNhbiB1c2Ugb24gdW5ncm91cGVkIGRhdGEgZnJhbWUgYnkgc3BlY2lmeWluZyBkYXRhIGNvbHVtbnM6DQoNCmBgYHtyfQ0KZ2FwbWluZGVyICU+JQ0KICAgIG5lc3QoeWVhcjpnZHBQZXJjYXApICU+JQ0KICAgIGhlYWQoKQ0KYGBgDQoNCiMjIyBGcm9tIHZlY3Rvcml6ZWQgZnVuY3Rpb25zDQoNCmBgYHtyfQ0KZGYgPC0gdGliYmxlKHgxID0gYygiYSxiLGMiLCAiZCxlLGYsZyIpKQ0KDQpkZiAlPiUNCiAgICBtdXRhdGUoeDIgPSBzdHJpbmdyOjpzdHJfc3BsaXQoeDEsICIsIikpDQpgYGANCg0KVXNlIGB1bm5lc3QoKWAgdG8gaGFuZGxlIHRoaXMuDQoNCmBgYHtyfQ0KZGYgJT4lDQogICAgbXV0YXRlKHgyID0gc3RyaW5ncjo6c3RyX3NwbGl0KHgxLCAiLCIpKSAlPiUNCiAgICB1bm5lc3QoKQ0KYGBgDQoNCkNhbiBhbHNvIHVzZSBgdGlkeXI6OnNlcGFyYXRlX3Jvd3MoKWA6DQoNCmBgYHtyfQ0KZGYgJT4lIHNlcGFyYXRlX3Jvd3MoeDEsIHNlcCA9ICIsIikNCmBgYA0KDQpVc2luZyBgbWFwKClgLCBgbWFwMigpYCwgYHBtYXAoKWAsIG9yIGBpbnZva2VfbWFwKClgOg0KDQpgYGB7cn0NCnNpbSA8LSB0cmliYmxlKA0KICAgIH5mLCAgICAgIH5wYXJhbXMsDQogICAgInJ1bmlmIiwgbGlzdChtaW4gPSAtMSwgbWF4ID0gLTEpLA0KICAgICJybm9ybSIsIGxpc3Qoc2QgPSA1KSwNCiAgICAicnBvaXMiLCBsaXN0KGxhbWJkYSA9IDEwKQ0KKQ0KDQpzaW0gJT4lDQogICAgbXV0YXRlKHNpbXMgPSBpbnZva2VfbWFwKGYsIHBhcmFtcywgbiA9IDEwKSkNCmBgYA0KDQojIyMgRnJvbSBtdWx0aXZhbHVlZCBzdW1tYXJpZXMNCg0KX19Qcm9ibGVtOl9fIE9uZSByZXN0cmljdGlvbiBvZiBgc3VtbWFyaXNlKClgIGlzIHRoYXQgaXMgb25seSB3b3JrcyB3aXRoIHN1bW1hcnkgZnVuY3Rpb25zIHRoYXQgcmV0dXJuIGEgc2luZ2xlIHZhbHVlLiBGb3IgZXhhbXBsZSwgY2Fubm90IGJlIHVzZWQgd2l0aCBgcXVhbnRpbGUoKWAuDQoNCmBgYHtyLCBldmFsID0gRn0NCm10Y2FycyAlPiUNCiAgICBncm91cF9ieShjeWwpICU+JQ0KICAgIHN1bW1hcmlzZShxID0gcXVhbnRpbGUobXBnKSkNCmBgYA0KDQpBYm92ZSBjb2RlIHJlc3VsdHMgaW4gZXJyb3IuIFBhc3MgZnVuY3Rpb25zIHRoYXQgcmV0dXJuIGxpc3RzIGFzIGEgbGlzdCB0byBnZXQgbmVzdGVkIGRhdGEgZnJhbWUuIENhbiB0aGVuIHVubmVzdC4NCg0KYGBge3J9DQpwcm9icyA8LSBjKDAuMDEsIDAuMjUsIDAuNSwgMC43NSwgMC45OSkNCm10Y2FycyAlPiUNCiAgICBncm91cF9ieShjeWwpICU+JQ0KICAgIHN1bW1hcmlzZShwID0gbGlzdChwcm9icyksIA0KICAgICAgICAgICAgICBxID0gbGlzdChxdWFudGlsZShtcGcpKSkgJT4lDQogICAgdW5uZXN0KCkNCmBgYA0KDQojIyMgRnJvbSBhIG5hbWVkIGxpc3QNCg0KYHRpYmJsZTo6ZW5mcmFtZSgpYCB0byBjcmVhdGUgbmVzdGVkIGRhdGEgZnJhbWUgZnJvbSBuZXN0ZWQgbGlzdC4NCg0KYGBge3J9DQp4IDwtIGxpc3QoDQogICAgYSA9IDE6NSwNCiAgICBiID0gMzo0LCANCiAgICBjID0gNTo2DQogICAgKQ0KeA0KYGBgDQoNCmBgYHtyfQ0KZW5mcmFtZSh4KSAlPiUgdW5uZXN0KCkNCmBgYA0KDQpDYW4gaXRlcmF0ZSBvdmVyIG5hbWVzIGFuZCB2YWx1ZXMgdXNpbmcgYG1hcDIoKWAuDQoNCmBgYHtyfQ0KZGYgPC0gZW5mcmFtZSh4KQ0KZGYNCmBgYA0KDQpgYGB7cn0NCmRmICU+JQ0KICAgIG11dGF0ZShzdW1tYXJ5ID0gbWFwMl9jaHIobmFtZSwgdmFsdWUsIH4gc3RyaW5ncjo6c3RyX2MoLngsICI6ICIsIC55W1sxXV0pKSkNCmBgYA0KDQojIyBTaW1wbGlmeWluZyBsaXN0LWNvbHVtbnMNCg0KTmVlZCB0byBiZSBhYmxlIHRvIGNvbnZlcnQgbGlzdCBjb2x1bW5zIGJhY2sgdG8gYXRvbWljIHZlY3RvciBvciBzZXQgb2YgYXRvbWljIHZlY3RvcnMgKGkuZS4gYSBmbGF0IGRhdGEgZnJhbWUpLiBUd28gbWV0aG9kczoNCg0KMS4gSWYgd2FudCBfX3NpbmdsZSB2YWx1ZV9fOiBgbXV0YXRlKClgICsgKGBtYXBfbGdsKClgIHwgYG1hcF9pbnQoKWAgfCBgbWFwX2RibCgpYCB8IGBtYXBfY2hyKClgKS4gVGhlc2UgbWFwIGZ1bmN0aW9ucyBjcmVhdGUgYXRvbWljIHZlY3RvcnMuDQoNCjIuIElmIHdhbnQgX19tYW55IHZhbHVlc19fOiBgdW5uZXN0KClgDQoNCiMjIyBMaXN0IHRvIHZlY3Rvcg0KDQoNCg0KYGBge3J9DQpkZiA8LSB0cmliYmxlKA0KICB+eCwNCiAgbGV0dGVyc1sxOjVdLA0KICAxOjMsDQogIHJ1bmlmKDUpDQopDQogIA0KZGYgJT4lIG11dGF0ZSgNCiAgdHlwZSA9IG1hcF9jaHIoeCwgdHlwZW9mKSwNCiAgbGVuZ3RoID0gbWFwX2ludCh4LCBsZW5ndGgpDQopDQpgYGANCg0KU2hvcnRjdXRzOiBVc2UgbmFtZXMgb2YgbmVzdGVkIGxpc3QgaXRlbXMgdG8gZHJpbGwgaW50byBsaXN0cy4NCg0KYGBge3J9DQpkZiA8LSB0cmliYmxlKA0KICB+eCwNCiAgbGlzdChhID0gMSwgYiA9IDIpLA0KICBsaXN0KGEgPSAyLCBjID0gNCkNCikNCmRmICU+JSBtdXRhdGUoDQogIGEgPSBtYXBfZGJsKHgsICJhIiwgLm51bGwgPSBOQV9yZWFsXyksDQogIGIgPSBtYXBfZGJsKHgsICJiIiwgLm51bGwgPSBOQV9yZWFsXykgIyBUaHJvd3MgZXJyb3IgaWYgbm8gTkEgaGFuZGxpbmcNCikNCmBgYA0KDQojIyMgVW5uZXN0aW5nDQoNClVubmVzdCB0byBnZXQgdGhlIGVudGlyZSBzdWItbGlzdCBpdGVtcy4NCg0KYGBge3J9DQp0aWJibGUoeCA9IDE6MiwgeSA9IGxpc3QoMTo0LCAxKSkNCmBgYA0KDQpgYGB7cn0NCnRpYmJsZSh4ID0gMToyLCB5ID0gbGlzdCgxOjQsIDEpKSAlPiUgdW5uZXN0KCkNCmBgYA0KDQo=