Set-up

library(tidyverse)

Acknowledgements

This notebook is based on Chapter 19 of R for Data Science.

1 What is a function?

You’ve already used tons of functions.

Take for example sum(). It sums the elements of a numerical vector:

# vector with elements 1 and 2
x <- c(1,2) 
# add them up
sum(x)
[1] 3

1.1 Vending machines

In general a function is an object that converts an input into an output.

A vending machine is a function:

  • input: money
  • output: tasty snack

When you write functions think of yourself as a vending-machine designer. Why? Because vending machines are easy to use. The input is obvious. The output is obvious. Nobody has to read a manual to use a vending machine.

So when you design a function, ask yourself:

  • Does it have an easy-to-understand name?
  • Does it have easy-to-understand inputs (arguments)?
  • Does it have an easy-to-understand output?

1.2 Who cares?

In some cases these desiderata must be satisfied so other people can use your code without fuss.

But in most cases you should think about your future self. They review code you wrote a few weeks ago. myfunc(x). What the hell is that?!

1.3 Our focus

We will focus on writing functions with different inputs:

  • vectors of length 1 (e.g., a number)
  • vectors of length \(n\) (e.g., many numbers)

Our goal is to build up to iteration: applying a function many times to different objects (e.g., to many columns of a tibble/data frame). Efficiently running the same calculation on different data is where programming really becomes important.

1.4 When should you write a function?

The book says it best:

You should consider writing a function whenever you’ve copied and pasted a block of code more than twice (i.e. you now have three copies of the same code).

Here are some other thoughts:

  • Writing functions helps you think more about design (“How should this code be used?”).
  • Writing functions is a great way to learn stats/machine learning. By coding up your own estimators you can really understand what goes on under the hood of canned estimators. This will make you a better scientist.
    • that said you should still use canned estimators in real work because they typically are optimized (e.g., written in C)

2 The function template

Here is a template for writing a function:

informative_name <- function(x) {
  output <- # do stuff and create an output
  return(output) # return the output
}

The function informative_name() takes an input x and returns output. If output is a specific thing (e.g., the sum of squares of a vector) you could give it a specific name (e.g., sum_of_squares).

As always in programming there are multiple ways of doing the same thing.

For instance, some people prefer a non-explicit return call:

informative_name2 <- function(x) {
  output <- # do stuff and create an output
  output # return the output
}

This function does the same thing: it returns output.

The book makes a few arguments (no pun intended!) as to why you should or shouldn’t explicitly call return() (see section 19.6.1). Mostly these are edge cases and you won’t run into them. At the end of the day you navigate it like any other convention. Do what everybody else does. That way your code can enjoy network effects.

In the case of return() it does not really matter. The advantage of return() is that it is explicit. Looking at informative_name() it is crystal clear what is returned. But at the end of the day this is a situation where you can pick one or the other. What matters is sticking with a choice. Consistency is key.

3 Arguments

3.1 Arguments of length 1

Everything in R is a vector.

For instance the number 2 is a vector:

class(2)
[1] "numeric"

A numeric vector of length 1.

Consider this function:

add_two <- function(x=2) { 
  output <- x + 2
  return(output)
}

add_two() does what it says on the tin: takes a number and adds two to it.

Press the “play” button to compile it. You will see it appear in the Environment tab. Once compiled a function can be used.

For instance:

# input: 3
# output: 3 + 2 = 5
add_two(x = 3)
[1] 5

Notice how we wrote function(x=2). That means the argument x is optional. If you don’t feed a number to add_two(), it will feed itself with its default value of 2:

add_two()
[1] 4

3.2 Checkpoint

Write a function called square_sum that takes a numerical input x (defaulting to 3) and

  • squares it, then;
  • adds the square to x to create an object output, then;
  • returns output:
square_sum <- function(x=3){
  square_x = x^2
  output <- x + square_x
  return(output)
}

Test it out by running:

  • square_sum(x=3)
  • square_sum(x=100)
square_sum(x = 3)
[1] 12

3.3 Local variables

Inside square_sum you defined an object output. But if you call it you’ll get an error:

output
Error: object 'output' not found

This is because output is a local variable. It only “exists” (to R) inside square_sum. The big idea here is that functions are environments. What happens in Vegas stays in Vegas – unless you return() it!

3.4 Multiple “single” numerical arguments

Functions of course can take many arguments. Just specify them inside function():

informative_name <- function(x, y, z) {
  output <- # do stuff with x, y and z to create an output
  return(output) # return the output
}

3.5 Checkpoint

Write a function sum_squares that takes two arguments x and y and:

  • squares x and y, then;
  • adds the squares to create output, then;
  • returns output
sum_squares <- function(x, y){
  square_x = x^2
  square_y = y^2
  output = square_x + square_y
  return(output)
}

Test it out for x=10 and y=100:

sum_squares(2, 3)
[1] 13
class(sum_squares)
[1] "function"

3.6 Arguments of length \(n\)

sum() can add a single number:

sum(2)
[1] 2

which of course is not useful at all.

What is useful is sum() adding up many numbers:

set.seed(123) # so we get the same random numbers
# create a vector of 1000 random standard normal numbers (mean 0, sd 1)
random_normal_numbers <- rnorm(n = 1000, mean = 0, sd = 1)
# add them up
sum(random_normal_numbers)
[1] 16.12787

To sum() the argument x is always a numerical vector of any length.

3.7 Checkpoint

Re-writesquare_sum so that it takes in a vector, squares each value, adds them up, and returns:

square_sum <- function(x){
  square_x = x^2
  output = sum(square_x)
  return(output)
}

Test it out on random_normal_numbers:

square_sum(x = random_normal_numbers)
[1] 982.7356

4 Functions to do math

Writing functions is useful when you want to do math.

Most math is usually just a bunch of small, easy steps (addition, subtraction, etc.) chained together.

You might find yourself in this position if you need to code up a stats estimator.

4.1 Checkpoint

Write a function called my_sd() that calculates the standard deviation of a vector. The formula is:

\[ s = \sqrt{\frac{1}{n-1} \sum_{i=1}^n (x_i - \bar{x})^2} \]

Think about the steps when coding it up:

  1. calculate the deviations \(x_i - \bar{x}\) where \(\bar{x}\) is the sample mean
  2. square the deviations
  3. add up the squared deviations
  4. multiply by \(\frac{1}{n-1}\) (use length()) to get the length of x, i.e. \(n\)
  5. take the square root
my_sd = function(x){
  # step 1
  deviations = x - mean(x)
  # step 2
  squared_deviations = deviations^2
  # step 3
  sum_squared_deviations = sum(squared_deviations)
  # step 4
  n = length(x)
  variance = (1/(n-1))*sum_squared_deviations
  # step 5
  sd = sqrt(variance)
  # return!!!!!
  return(sd)
}

Test it out on random_normal_numbers:

my_sd(random_normal_numbers)
[1] 0.991695

Compare it to the canned routine sd():

sd(random_normal_numbers)
[1] 0.991695

Side note: Why is the result close to 1?

Because we drew those numbers from a distribution with a standard deviation of 1. So my_sd() and sd() recover the parameter.

This idea of “recovering” paramaters is the bedrock of stats. The goal is to “recover” the population parameter from a sample.

4.2 Checkpoint

Most often you will use functions on observational data rather than simulated data.

Load the diamonds data set:

data("diamonds")

The standard deviation of price is just sd() on the price vector inside the diamonds tibble:

diamonds %>% 
  summarise(sd(price))

Replicate the results from sd() with my_sd().

diamonds %>% 
  summarise(my_sd(price))

4.3 Checkpoint

Do carats influence the price of diamonds? We can build a model:

\[ \begin{aligned} \text{prices} &= f(\text{carats}) + \epsilon \\ &= \beta_0 + \beta_1(\text{carats}) + \epsilon \end{aligned} \] where \(\beta_1\) captures the average effect of carats on prices. If \(\hat{\beta_1}\) (the estimate) is positive, then more carats = higher prices, on average. The formula for \(\beta_1\) is:

\[ \hat{\beta_1} = \frac{\sum_{i=1}^n (x_i - \bar{x})(y_i - \bar{y})}{\sum_{i=1}^n (x_i - \bar{x})^2} \] We can estimate the parameters with lm():

lm(formula = price ~ carat, data = diamonds) %>% 
  summary()

Call:
lm(formula = price ~ carat, data = diamonds)

Residuals:
     Min       1Q   Median       3Q      Max 
-18585.3   -804.8    -18.9    537.4  12731.7 

Coefficients:
            Estimate Std. Error t value Pr(>|t|)    
(Intercept) -2256.36      13.06  -172.8   <2e-16 ***
carat        7756.43      14.07   551.4   <2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

Residual standard error: 1549 on 53938 degrees of freedom
Multiple R-squared:  0.8493,    Adjusted R-squared:  0.8493 
F-statistic: 3.041e+05 on 1 and 53938 DF,  p-value: < 2.2e-16

Write a function called my_lm() that takes an x and y argument and calculates the regression coefficient of x on y. Then replicate the results from lm(formula = price ~ carat, data = diamonds). Think about what code you can re-use from my_sd().

my_lm = function(x, y){
  # 1. NUMERATOR
  ## step 1
  x_deviations = x - mean(x)
  y_deviations = y - mean(y)
  ## step 2
  product_deviations = x_deviations * y_deviations
  ## step 3
  numerator = sum(product_deviations)
  # 2. DENOMINATOR
  ## step 1
  x_deviations_squared = x_deviations^2
  ## step 2
  denominator = sum(x_deviations_squared)
  # 3. put it all together
  beta = numerator / denominator
  # RETURN!!
  return(beta)
}
my_lm(x = diamonds$carat, y = diamonds$price)
[1] 7756.426

5 Conditional execution

What if you want your function to do different things depending on the input?

Use an if statement!

This function checks if the argument is equal to two. If it is, add two and return.

add_two_if <- function(x) { 
  if(x == 2){
    output <- x + 2
    return(output)
  }
}

Try it out:

add_two_if(x = 1)

The if(x==2) is the logical test, a test that only returns TRUE or FALSE:

2 == 2
[1] TRUE
2 == 3
[1] FALSE

So when if(x==2) evaluates to TRUE the function proceeds.

5.0.1 Logical tests

Like in dplyr::filter() we can use the following conditionals inside if():

  • ==: “is equal to”
  • !=: “is not equal to”
  • &: “and”
  • |: “or”
  • >, >=: “greater than”, “less than or equal to”
  • <, <=: “less than”, “less than or equal to”

5.0.2 else

But what if we pass an argument other than two?

add_two_if(x = 3)

Nothing happens.

What we need is a way to handle the exception – a way to deal with arguments that are not equal to 2.

This is where else comes in.

The general structure of an if-else statement is:

if(TRUE) { # if the test is true
  # do this thing
} else { # otherwise
  # do this other thing
}

Let’s modify add_two_if to add three if an argument is not two:

add_two_if <- function(x) { 
  if(x > 2 && x < 4){
    output <- x + 2
    # do some function
  } else {
    output <- x - 2
    # do some other function
  }
  return(output)
}
add_two_if(x = 2)
[1] 0

Notice how the return() statement is outside the if...else scope. (Anything in R wrapped in {} is a “scope”).

In theory you can chain together as many if...else statements as you want by adding more logical tests:

add_two_if <- function(x) { 
  if(x == 2){
    output <- x + 2
  } else if(x == 3) {
    output <- x + 3
  } else if(x == 4){
    output <- x + 3
  } else { 
    print("this is a bad function")
  }
  return(output)
}

But you want to avoid this. It’s hard to read and probably not necessary. The chapter has a few suggestions for alternatives. For now we will stick to one logical test.

5.1 Checkpoint

Write a function truth_or_dare that takes a vector and checks whether the third entry is positive. If yes, print “truth”. If no, print “dare”.

Update We changed this to also demo stop().

truth_or_dare = function(x){
  if(length(x) == 1) stop("vector is too short")
  if(x[3] %% 2 == 0) {
    warning("The challenge is to do ", round(rnorm(1, mean = 10, sd =5),0), " dares")
    #print(paste())
  } else {
    print("truth")
  }
}
vec = c(2,3,4,5)
truth_or_dare(2)
Error in truth_or_dare(2) : vector is too short

5.2 ifelse()

The if...else scope only works for vectors of length 1.

Run this chunk:

another_vector <- c(1, NA, 3, NA)
if(is.na(another_vector)) {
  "NA :("
} else{
  "number"
}
the condition has length > 1 and only the first element will be used
[1] "number"

if stopped after the first entry of another_vector.

Use ifelse() to run an if..else scope over an entire vector:

ifelse(test = is.na(another_vector), yes = 0, no = "a")
[1] "a" "0" "a" "0"

6 Appendix

6.1 Dot-dot-dot

You may have noticed that many functions in R have the argument ....

For instance, the arguments to mean() are:

mean(x, ...)

The argument x is mandatory. The argument ... is optional. What is cool about ... is that you can pass any number of arbitrary arguments to it.

For instance, what if you have NA in a vector?

v <- c(1,2,NA)

mean(x) will return NA:

mean(v)
[1] NA

but you can pass na.rm to ... so that mean() only looks at numerical values:

mean(v, na.rm = TRUE)
[1] 1.5

Ditto sd(). Without na.rm:

sd(v)
[1] NA

With na.rm:

sd(v, na.rm = TRUE)
[1] 0.7071068

This underscores the real value of ...: passing optional arguments to other functions that have optional arguments – like mean() and sd().

6.1.1 Checkpoint

Say you have this vector with NAs:

# create a vector of random numbers
na_vector <- rnorm(n = 1000, mean = 0, sd = 1)
# randomly replace some of the values as NA
na_vector[sample(1:1000, 100)] <- NA

Write a function called z_score that calculates the z-score of each element of na_vector. The formula is:

\[ z_i = \frac{x_i - \bar{x}}{s} \]

where \(\bar{x}\) is the sample mean and \(s\) is the sample standard deviation. Make sure your function can account for NAs by including ... and passing that to mean(x, ...) and sd(x, ...).

z_score = function(x, ...){
  z = (x - mean(x, ...)) / sd(x, ...)
  return(z)
}

Test it out on na_vector:

z_score(x = na_vector, na.rm = TRUE) %>% 
  mean(x = ., na.rm = TRUE)
[1] -7.998159e-18

Section 19.5.3 links to other ways to use .... They’re handy when you write functions that take entire data sets as arguments. For more see Chapters 18-21 of the Tidyverse Design Guide.

6.1.2 Aside: randomly sampling a vector

Let’s randomly replace some of the values in random_normal_numbers using indexing and sample().

Recall that [] indexes vectors by position. For instance, the first three elements of random_normal_numbers:

random_normal_numbers[1:3]
[1] -0.5604756 -0.2301775  1.5587083

and sample() will randomly sample any vector. For instance, randomly sample two integers between 1 and 10:

sample(x = 1:10, size = 3)
[1] 1 9 3

For instance I could randomly sample a vector:

# vector of 1, 2, .., 10
x <- 1:10
# the length of the vector
n <- length(x)
# randomly draw three elements from x
x[sample(x = 1:n, size = 3)]
[1] 4 1 9

so we can combine indexing and sample to randomly switch values in a vector to NA:

# get the length of random_normal_numbers (1000)
n <- length(random_normal_numbers)
# from the positional index of 1:n, randomly choose 100 of them, 
## and reassign their corresponding values in random_normal_numbers to NA
random_normal_numbers[sample(1:n, 100)] <- NA
LS0tCnRpdGxlOiAiRnVuY3Rpb25zIChDb21wbGV0ZWQgTm90ZWJvb2spIgphdXRob3I6ICJMREciCnN1YnRpdGxlOiAiUiBmb3IgRGF0YSBTY2llbmNlIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIGhpZ2hsaWdodDogcHlnbWVudHMKICAgIG51bWJlcl9zZWN0aW9uczogeWVzCiAgICB0aGVtZTogcmVhZGFibGUKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6CiAgICAgIGNvbGxhcHNlZDogeWVzCi0tLQoKCiMgU2V0LXVwIHstfQogIApgYGB7ciBsb2FkIHBhY2thZ2VzLCBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKYGBgCgojIyBBY2tub3dsZWRnZW1lbnRzIHstfQoKVGhpcyBub3RlYm9vayBpcyBiYXNlZCBvbiBDaGFwdGVyIDE5IG9mIFsqUiBmb3IgRGF0YSBTY2llbmNlKl0oaHR0cHM6Ly9yNGRzLmhhZC5jby5uei9pbmRleC5odG1sKS4KCiMgV2hhdCBpcyBhIGZ1bmN0aW9uPyAKCllvdSd2ZSBhbHJlYWR5IHVzZWQgdG9ucyBvZiBmdW5jdGlvbnMuIAoKVGFrZSBmb3IgZXhhbXBsZSBgc3VtKClgLiBJdCBzdW1zIHRoZSBlbGVtZW50cyBvZiBhIG51bWVyaWNhbCB2ZWN0b3I6CgpgYGB7ciBzdW0gZGVtb30KIyB2ZWN0b3Igd2l0aCBlbGVtZW50cyAxIGFuZCAyCnggPC0gYygxLDIpIAojIGFkZCB0aGVtIHVwCnN1bSh4KQpgYGAKCiMjIFZlbmRpbmcgbWFjaGluZXMKCkluIGdlbmVyYWwgYSBmdW5jdGlvbiBpcyBhbiAqKm9iamVjdCoqIHRoYXQgKipjb252ZXJ0cyoqIGFuICoqaW5wdXQqKiBpbnRvIGFuICoqb3V0cHV0KiouCgpBIHZlbmRpbmcgbWFjaGluZSBpcyBhIGZ1bmN0aW9uOiAKCiogaW5wdXQ6IG1vbmV5Ciogb3V0cHV0OiB0YXN0eSBzbmFjawoKV2hlbiB5b3Ugd3JpdGUgZnVuY3Rpb25zIHRoaW5rIG9mIHlvdXJzZWxmIGFzIGEgdmVuZGluZy1tYWNoaW5lIGRlc2lnbmVyLiBXaHk/IEJlY2F1c2UgdmVuZGluZyBtYWNoaW5lcyBhcmUgKiplYXN5IHRvIHVzZSoqLiBUaGUgaW5wdXQgaXMgb2J2aW91cy4gVGhlIG91dHB1dCBpcyBvYnZpb3VzLiBOb2JvZHkgaGFzIHRvIHJlYWQgYSBtYW51YWwgdG8gdXNlIGEgdmVuZGluZyBtYWNoaW5lLiAKClNvIHdoZW4geW91IGRlc2lnbiBhIGZ1bmN0aW9uLCBhc2sgeW91cnNlbGY6CgoqIERvZXMgaXQgaGF2ZSBhbiBlYXN5LXRvLXVuZGVyc3RhbmQgbmFtZT8gCiogRG9lcyBpdCBoYXZlIGVhc3ktdG8tdW5kZXJzdGFuZCBpbnB1dHMgKGFyZ3VtZW50cyk/CiogRG9lcyBpdCBoYXZlIGFuIGVhc3ktdG8tdW5kZXJzdGFuZCBvdXRwdXQ/IAoKIyMgV2hvIGNhcmVzPwoKSW4gc29tZSBjYXNlcyB0aGVzZSBkZXNpZGVyYXRhIG11c3QgYmUgc2F0aXNmaWVkIHNvICoqb3RoZXIgcGVvcGxlKiogY2FuIHVzZSB5b3VyIGNvZGUgd2l0aG91dCBmdXNzLiAKCkJ1dCBpbiBtb3N0IGNhc2VzIHlvdSBzaG91bGQgdGhpbmsgYWJvdXQgeW91ciAqKmZ1dHVyZSBzZWxmLioqIFRoZXkgcmV2aWV3IGNvZGUgeW91IHdyb3RlIGEgZmV3IHdlZWtzIGFnby4gYG15ZnVuYyh4KWAuIFdoYXQgdGhlIGhlbGwgaXMgdGhhdD8hCgojIyBPdXIgZm9jdXMKCldlIHdpbGwgZm9jdXMgb24gd3JpdGluZyBmdW5jdGlvbnMgd2l0aCBkaWZmZXJlbnQgaW5wdXRzOiAgCgoqIHZlY3RvcnMgb2YgbGVuZ3RoIDEgKGUuZy4sIGEgbnVtYmVyKQoqIHZlY3RvcnMgb2YgbGVuZ3RoICRuJCAoZS5nLiwgbWFueSBudW1iZXJzKQoKT3VyIGdvYWwgaXMgdG8gYnVpbGQgdXAgdG8gKippdGVyYXRpb24qKjogYXBwbHlpbmcgYSBmdW5jdGlvbiBtYW55IHRpbWVzIHRvIGRpZmZlcmVudCBvYmplY3RzIChlLmcuLCB0byBtYW55IGNvbHVtbnMgb2YgYSB0aWJibGUvZGF0YSBmcmFtZSkuIEVmZmljaWVudGx5IHJ1bm5pbmcgdGhlIHNhbWUgY2FsY3VsYXRpb24gb24gZGlmZmVyZW50IGRhdGEgaXMgd2hlcmUgcHJvZ3JhbW1pbmcgcmVhbGx5IGJlY29tZXMgaW1wb3J0YW50LgoKIyMgV2hlbiBzaG91bGQgeW91IHdyaXRlIGEgZnVuY3Rpb24/IAoKVGhlIGJvb2sgc2F5cyBpdCBiZXN0OgoKPiBZb3Ugc2hvdWxkIGNvbnNpZGVyIHdyaXRpbmcgYSBmdW5jdGlvbiB3aGVuZXZlciB5b3XigJl2ZSBjb3BpZWQgYW5kIHBhc3RlZCBhIGJsb2NrIG9mIGNvZGUgbW9yZSB0aGFuIHR3aWNlIChpLmUuIHlvdSBub3cgaGF2ZSB0aHJlZSBjb3BpZXMgb2YgdGhlIHNhbWUgY29kZSkuCgpIZXJlIGFyZSBzb21lIG90aGVyIHRob3VnaHRzOgoKKiBXcml0aW5nIGZ1bmN0aW9ucyBoZWxwcyB5b3UgdGhpbmsgbW9yZSBhYm91dCAqKmRlc2lnbioqICgiSG93IHNob3VsZCB0aGlzIGNvZGUgYmUgdXNlZD8iKS4KKiBXcml0aW5nIGZ1bmN0aW9ucyBpcyBhIGdyZWF0IHdheSB0byBsZWFybiBzdGF0cy9tYWNoaW5lIGxlYXJuaW5nLiBCeSBjb2RpbmcgdXAgeW91ciBvd24gZXN0aW1hdG9ycyB5b3UgY2FuIHJlYWxseSB1bmRlcnN0YW5kIHdoYXQgZ29lcyBvbiB1bmRlciB0aGUgaG9vZCBvZiBjYW5uZWQgZXN0aW1hdG9ycy4gVGhpcyB3aWxsIG1ha2UgeW91IGEgYmV0dGVyIHNjaWVudGlzdC4KICAtIHRoYXQgc2FpZCB5b3Ugc2hvdWxkIHN0aWxsIHVzZSBjYW5uZWQgZXN0aW1hdG9ycyBpbiByZWFsIHdvcmsgYmVjYXVzZSB0aGV5IHR5cGljYWxseSBhcmUgb3B0aW1pemVkIChlLmcuLCB3cml0dGVuIGluIEMpCgojIFRoZSBmdW5jdGlvbiB0ZW1wbGF0ZQoKSGVyZSBpcyBhIHRlbXBsYXRlIGZvciB3cml0aW5nIGEgZnVuY3Rpb246CgpgYGB7ciBmdW5jdGlvbiB0ZW1wbGF0ZSwgZXZhbD1GQUxTRX0KaW5mb3JtYXRpdmVfbmFtZSA8LSBmdW5jdGlvbih4KSB7CiAgb3V0cHV0IDwtICMgZG8gc3R1ZmYgYW5kIGNyZWF0ZSBhbiBvdXRwdXQKICByZXR1cm4ob3V0cHV0KSAjIHJldHVybiB0aGUgb3V0cHV0Cn0KYGBgCgpUaGUgZnVuY3Rpb24gYGluZm9ybWF0aXZlX25hbWUoKWAgdGFrZXMgYW4gaW5wdXQgYHhgIGFuZCAqKnJldHVybnMqKiBgb3V0cHV0YC4gSWYgb3V0cHV0IGlzIGEgc3BlY2lmaWMgdGhpbmcgKGUuZy4sIHRoZSBzdW0gb2Ygc3F1YXJlcyBvZiBhIHZlY3RvcikgeW91IGNvdWxkIGdpdmUgaXQgYSBzcGVjaWZpYyBuYW1lIChlLmcuLCBgc3VtX29mX3NxdWFyZXNgKS4KCkFzIGFsd2F5cyBpbiBwcm9ncmFtbWluZyB0aGVyZSBhcmUgbXVsdGlwbGUgd2F5cyBvZiBkb2luZyB0aGUgc2FtZSB0aGluZy4gCgpGb3IgaW5zdGFuY2UsIHNvbWUgcGVvcGxlIHByZWZlciBhIG5vbi1leHBsaWNpdCByZXR1cm4gY2FsbDoKCmBgYHtyIGZ1bmN0aW9uIHRlbXBsYXRlIGFsdGVybmF0aXZlLCBldmFsPUZBTFNFfQppbmZvcm1hdGl2ZV9uYW1lMiA8LSBmdW5jdGlvbih4KSB7CiAgb3V0cHV0IDwtICMgZG8gc3R1ZmYgYW5kIGNyZWF0ZSBhbiBvdXRwdXQKICBvdXRwdXQgIyByZXR1cm4gdGhlIG91dHB1dAp9CmBgYAoKVGhpcyBmdW5jdGlvbiBkb2VzIHRoZSBzYW1lIHRoaW5nOiBpdCByZXR1cm5zIGBvdXRwdXRgLiAKClRoZSBib29rIG1ha2VzIGEgZmV3IGFyZ3VtZW50cyAobm8gcHVuIGludGVuZGVkISkgYXMgdG8gd2h5IHlvdSBzaG91bGQgb3Igc2hvdWxkbid0IGV4cGxpY2l0bHkgY2FsbCBgcmV0dXJuKClgIChzZWUgc2VjdGlvbiAxOS42LjEpLiBNb3N0bHkgdGhlc2UgYXJlIGVkZ2UgY2FzZXMgYW5kIHlvdSB3b24ndCBydW4gaW50byB0aGVtLiBBdCB0aGUgZW5kIG9mIHRoZSBkYXkgeW91IG5hdmlnYXRlIGl0IGxpa2UgYW55IG90aGVyIGNvbnZlbnRpb24uIERvIHdoYXQgZXZlcnlib2R5IGVsc2UgZG9lcy4gVGhhdCB3YXkgeW91ciBjb2RlIGNhbiBlbmpveSAqKm5ldHdvcmsgZWZmZWN0cyoqLiAKCkluIHRoZSBjYXNlIG9mIGByZXR1cm4oKWAgaXQgZG9lcyBub3QgcmVhbGx5IG1hdHRlci4gVGhlIGFkdmFudGFnZSBvZiBgcmV0dXJuKClgIGlzIHRoYXQgaXQgaXMgKipleHBsaWNpdCoqLiBMb29raW5nIGF0IGBpbmZvcm1hdGl2ZV9uYW1lKClgIGl0IGlzIGNyeXN0YWwgY2xlYXIgd2hhdCBpcyByZXR1cm5lZC4gQnV0IGF0IHRoZSBlbmQgb2YgdGhlIGRheSB0aGlzIGlzIGEgc2l0dWF0aW9uIHdoZXJlIHlvdSBjYW4gcGljayBvbmUgb3IgdGhlIG90aGVyLiBXaGF0IG1hdHRlcnMgaXMgc3RpY2tpbmcgd2l0aCBhIGNob2ljZS4gQ29uc2lzdGVuY3kgaXMga2V5LiAKCiMgQXJndW1lbnRzCgojIyBBcmd1bWVudHMgb2YgbGVuZ3RoIDEKCkV2ZXJ5dGhpbmcgaW4gUiBpcyBhIHZlY3Rvci4gCgpGb3IgaW5zdGFuY2UgdGhlIG51bWJlciAyIGlzIGEgdmVjdG9yOgoKYGBge3IgY2xhc3MgMn0KY2xhc3MoMikKYGBgCgpBIG51bWVyaWMgdmVjdG9yIG9mIGxlbmd0aCAxLiAKCkNvbnNpZGVyIHRoaXMgZnVuY3Rpb246CgpgYGB7ciBhZGQtdHdvfQphZGRfdHdvIDwtIGZ1bmN0aW9uKHg9MikgeyAKICBvdXRwdXQgPC0geCArIDIKICByZXR1cm4ob3V0cHV0KQp9CmBgYAoKYGFkZF90d28oKWAgZG9lcyB3aGF0IGl0IHNheXMgb24gdGhlIHRpbjogdGFrZXMgYSBudW1iZXIgYW5kIGFkZHMgdHdvIHRvIGl0LiAKClByZXNzIHRoZSAicGxheSIgYnV0dG9uIHRvICoqY29tcGlsZSoqIGl0LiBZb3Ugd2lsbCBzZWUgaXQgYXBwZWFyIGluIHRoZSBFbnZpcm9ubWVudCB0YWIuIE9uY2UgY29tcGlsZWQgYSBmdW5jdGlvbiBjYW4gYmUgdXNlZC4gCgpGb3IgaW5zdGFuY2U6CgpgYGB7ciBhZGRfdHdvfQojIGlucHV0OiAzCiMgb3V0cHV0OiAzICsgMiA9IDUKYWRkX3R3byh4ID0gMykKYGBgCgpOb3RpY2UgaG93IHdlIHdyb3RlIGBmdW5jdGlvbih4PTIpYC4gVGhhdCBtZWFucyB0aGUgYXJndW1lbnQgYHhgIGlzICoqb3B0aW9uYWwqKi4gSWYgeW91IGRvbid0IGZlZWQgYSBudW1iZXIgdG8gYGFkZF90d28oKWAsIGl0IHdpbGwgZmVlZCBpdHNlbGYgd2l0aCBpdHMgKipkZWZhdWx0KiogdmFsdWUgb2YgMjoKCmBgYHtyfQphZGRfdHdvKCkKYGBgCgojIyBDaGVja3BvaW50CgpXcml0ZSBhIGZ1bmN0aW9uIGNhbGxlZCBgc3F1YXJlX3N1bWAgdGhhdCB0YWtlcyBhIG51bWVyaWNhbCBpbnB1dCBgeGAgKGRlZmF1bHRpbmcgdG8gMykgYW5kIAoKKiBzcXVhcmVzIGl0LCB0aGVuOwoqIGFkZHMgdGhlIHNxdWFyZSB0byBgeGAgdG8gY3JlYXRlIGFuIG9iamVjdCBgb3V0cHV0YCwgdGhlbjsKKiByZXR1cm5zIGBvdXRwdXRgOgoKYGBge3IgY2hlY2twb2ludCBzcXVhcmVfc3VtfQpzcXVhcmVfc3VtIDwtIGZ1bmN0aW9uKHg9Myl7CiAgc3F1YXJlX3ggPSB4XjIKICBvdXRwdXQgPC0geCArIHNxdWFyZV94CiAgcmV0dXJuKG91dHB1dCkKfQpgYGAKClRlc3QgaXQgb3V0IGJ5IHJ1bm5pbmc6CgoqIGBzcXVhcmVfc3VtKHg9MylgCiogYHNxdWFyZV9zdW0oeD0xMDApYAoKYGBge3IgY2hlY2twb2ludCBzcXVhcmVfc3VtIHRlc3R9CnNxdWFyZV9zdW0oeCA9IDMpCmBgYAoKIyMgTG9jYWwgdmFyaWFibGVzCgpJbnNpZGUgYHNxdWFyZV9zdW1gIHlvdSBkZWZpbmVkIGFuIG9iamVjdCBgb3V0cHV0YC4gQnV0IGlmIHlvdSBjYWxsIGl0IHlvdSdsbCBnZXQgYW4gZXJyb3I6CgpgYGB7ciB3aGVyZSBpcyBvdXRwdXQ/fQpvdXRwdXQKYGBgCgpUaGlzIGlzIGJlY2F1c2UgYG91dHB1dGAgaXMgYSAqKmxvY2FsIHZhcmlhYmxlKiouIEl0IG9ubHkgImV4aXN0cyIgKHRvIFIpIGluc2lkZSBgc3F1YXJlX3N1bWAuIFRoZSBiaWcgaWRlYSBoZXJlIGlzIHRoYXQgZnVuY3Rpb25zIGFyZSAqKmVudmlyb25tZW50cyoqLiBXaGF0IGhhcHBlbnMgaW4gVmVnYXMgc3RheXMgaW4gVmVnYXMgLS0gdW5sZXNzIHlvdSBgcmV0dXJuKClgIGl0IQoKIyMgTXVsdGlwbGUgInNpbmdsZSIgbnVtZXJpY2FsIGFyZ3VtZW50cwoKRnVuY3Rpb25zIG9mIGNvdXJzZSBjYW4gdGFrZSBtYW55IGFyZ3VtZW50cy4gSnVzdCBzcGVjaWZ5IHRoZW0gaW5zaWRlIGBmdW5jdGlvbigpYDoKCmBgYHtyIGZ1bmN0aW9uIHRlbXBsYXRlIG11bHRpcGxlIGFyZ3VtZW50cywgZXZhbD1GQUxTRX0KaW5mb3JtYXRpdmVfbmFtZSA8LSBmdW5jdGlvbih4LCB5LCB6KSB7CiAgb3V0cHV0IDwtICMgZG8gc3R1ZmYgd2l0aCB4LCB5IGFuZCB6IHRvIGNyZWF0ZSBhbiBvdXRwdXQKICByZXR1cm4ob3V0cHV0KSAjIHJldHVybiB0aGUgb3V0cHV0Cn0KYGBgCgojIyBDaGVja3BvaW50IAoKV3JpdGUgYSBmdW5jdGlvbiBgc3VtX3NxdWFyZXNgIHRoYXQgdGFrZXMgKip0d28qKiBhcmd1bWVudHMgYHhgIGFuZCBgeWAgYW5kOgoKKiBzcXVhcmVzIGB4YCBhbmQgYHlgLCB0aGVuOwoqIGFkZHMgdGhlIHNxdWFyZXMgdG8gY3JlYXRlIGBvdXRwdXRgLCB0aGVuOwoqIHJldHVybnMgYG91dHB1dGAKCmBgYHtyIGNoZWNrcG9pbnQgc3VtX3NxdWFyZXN9CnN1bV9zcXVhcmVzIDwtIGZ1bmN0aW9uKHgsIHkpewogIHNxdWFyZV94ID0geF4yCiAgc3F1YXJlX3kgPSB5XjIKICBvdXRwdXQgPSBzcXVhcmVfeCArIHNxdWFyZV95CiAgcmV0dXJuKG91dHB1dCkKfQpgYGAKClRlc3QgaXQgb3V0IGZvciBgeD0xMGAgYW5kIGB5PTEwMGA6CgpgYGB7ciBjaGVja3BvaW50IHN1bV9zcXVhcmVzIHRlc3R9CnN1bV9zcXVhcmVzKDIsIDMpCmBgYAoKYGBge3J9CmNsYXNzKHN1bV9zcXVhcmVzKQpgYGAKCiMjIEFyZ3VtZW50cyBvZiBsZW5ndGggJG4kCgpgc3VtKClgIGNhbiBhZGQgYSBzaW5nbGUgbnVtYmVyOgoKYGBge3Igc3VtIGRlbW8gb25lIG51bWJlcn0Kc3VtKDIpIApgYGAKCndoaWNoIG9mIGNvdXJzZSBpcyBub3QgdXNlZnVsIGF0IGFsbC4gCgpXaGF0IF9pc18gdXNlZnVsIGlzIGBzdW0oKWAgYWRkaW5nIHVwICoqbWFueSoqIG51bWJlcnM6CgpgYGB7cn0Kc2V0LnNlZWQoMTIzKSAjIHNvIHdlIGdldCB0aGUgc2FtZSByYW5kb20gbnVtYmVycwojIGNyZWF0ZSBhIHZlY3RvciBvZiAxMDAwIHJhbmRvbSBzdGFuZGFyZCBub3JtYWwgbnVtYmVycyAobWVhbiAwLCBzZCAxKQpyYW5kb21fbm9ybWFsX251bWJlcnMgPC0gcm5vcm0obiA9IDEwMDAsIG1lYW4gPSAwLCBzZCA9IDEpCiMgYWRkIHRoZW0gdXAKc3VtKHJhbmRvbV9ub3JtYWxfbnVtYmVycykKYGBgCgpUbyBgc3VtKClgIHRoZSBhcmd1bWVudCBgeGAgaXMgYWx3YXlzIGEgbnVtZXJpY2FsIHZlY3RvciBvZiAqKmFueSoqIGxlbmd0aC4gCgojIyBDaGVja3BvaW50CgpSZS13cml0ZWBzcXVhcmVfc3VtYCBzbyB0aGF0IGl0IHRha2VzIGluIGEgdmVjdG9yLCBzcXVhcmVzIGVhY2ggdmFsdWUsIGFkZHMgdGhlbSB1cCwgYW5kIHJldHVybnM6CgpgYGB7ciBjaGVja3BvaW50IHNxdWFyZV9zdW0gdmVjdG9yfQpzcXVhcmVfc3VtIDwtIGZ1bmN0aW9uKHgpewogIHNxdWFyZV94ID0geF4yCiAgb3V0cHV0ID0gc3VtKHNxdWFyZV94KQogIHJldHVybihvdXRwdXQpCn0KYGBgCgpUZXN0IGl0IG91dCBvbiBgcmFuZG9tX25vcm1hbF9udW1iZXJzYDoKCmBgYHtyIGNoZWNrcG9pbnQgc3F1YXJlX3N1bSB2ZWN0b3IgdGVzdH0Kc3F1YXJlX3N1bSh4ID0gcmFuZG9tX25vcm1hbF9udW1iZXJzKQpgYGAKCiMgRnVuY3Rpb25zIHRvIGRvIG1hdGgKCldyaXRpbmcgZnVuY3Rpb25zIGlzIHVzZWZ1bCB3aGVuIHlvdSB3YW50IHRvIGRvIG1hdGguIAoKTW9zdCBtYXRoIGlzIHVzdWFsbHkganVzdCBhIGJ1bmNoIG9mIHNtYWxsLCBlYXN5IHN0ZXBzIChhZGRpdGlvbiwgc3VidHJhY3Rpb24sIGV0Yy4pIGNoYWluZWQgdG9nZXRoZXIuIAoKWW91IG1pZ2h0IGZpbmQgeW91cnNlbGYgaW4gdGhpcyBwb3NpdGlvbiBpZiB5b3UgbmVlZCB0byBjb2RlIHVwIGEgc3RhdHMgZXN0aW1hdG9yLgoKIyMgQ2hlY2twb2ludAoKV3JpdGUgYSBmdW5jdGlvbiBjYWxsZWQgYG15X3NkKClgIHRoYXQgY2FsY3VsYXRlcyB0aGUgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIGEgdmVjdG9yLiBUaGUgZm9ybXVsYSBpczoKCiQkCnMgPSBcc3FydHtcZnJhY3sxfXtuLTF9IFxzdW1fe2k9MX1ebiAoeF9pIC0gXGJhcnt4fSleMn0KJCQKClRoaW5rIGFib3V0IHRoZSBzdGVwcyB3aGVuIGNvZGluZyBpdCB1cDoKCjEuIGNhbGN1bGF0ZSB0aGUgKipkZXZpYXRpb25zKiogJHhfaSAgLSBcYmFye3h9JCB3aGVyZSAkXGJhcnt4fSQgaXMgdGhlIHNhbXBsZSBtZWFuCjIuIHNxdWFyZSB0aGUgZGV2aWF0aW9ucwozLiBhZGQgdXAgdGhlIHNxdWFyZWQgZGV2aWF0aW9ucwo0LiBtdWx0aXBseSBieSAkXGZyYWN7MX17bi0xfSQgKHVzZSBgbGVuZ3RoKClgKSB0byBnZXQgdGhlIGxlbmd0aCBvZiBgeGAsIGkuZS4gJG4kCjUuIHRha2UgdGhlIHNxdWFyZSByb290CgpgYGB7ciBjaGVja3BvaW50IG15X3NkfQpteV9zZCA9IGZ1bmN0aW9uKHgpewogICMgc3RlcCAxCiAgZGV2aWF0aW9ucyA9IHggLSBtZWFuKHgpCiAgIyBzdGVwIDIKICBzcXVhcmVkX2RldmlhdGlvbnMgPSBkZXZpYXRpb25zXjIKICAjIHN0ZXAgMwogIHN1bV9zcXVhcmVkX2RldmlhdGlvbnMgPSBzdW0oc3F1YXJlZF9kZXZpYXRpb25zKQogICMgc3RlcCA0CiAgbiA9IGxlbmd0aCh4KQogIHZhcmlhbmNlID0gKDEvKG4tMSkpKnN1bV9zcXVhcmVkX2RldmlhdGlvbnMKICAjIHN0ZXAgNQogIHNkID0gc3FydCh2YXJpYW5jZSkKICAjIHJldHVybiEhISEhCiAgcmV0dXJuKHNkKQp9CgpgYGAKClRlc3QgaXQgb3V0IG9uIGByYW5kb21fbm9ybWFsX251bWJlcnNgOgoKYGBge3IgY2hlY2twb2ludCBteV9zZCB0ZXN0fQpteV9zZChyYW5kb21fbm9ybWFsX251bWJlcnMpCmBgYAoKQ29tcGFyZSBpdCB0byB0aGUgY2FubmVkIHJvdXRpbmUgYHNkKClgOgoKYGBge3Igc2QgdnMgbXlfc2R9CnNkKHJhbmRvbV9ub3JtYWxfbnVtYmVycykKYGBgCgpTaWRlIG5vdGU6IFdoeSBpcyB0aGUgcmVzdWx0IGNsb3NlIHRvIDE/IAoKQmVjYXVzZSB3ZSBkcmV3IHRob3NlIG51bWJlcnMgZnJvbSBhIGRpc3RyaWJ1dGlvbiB3aXRoIGEgc3RhbmRhcmQgZGV2aWF0aW9uIG9mIDEuIFNvIGBteV9zZCgpYCBhbmQgYHNkKClgICoqcmVjb3ZlcioqIHRoZSBwYXJhbWV0ZXIuIAoKVGhpcyBpZGVhIG9mICJyZWNvdmVyaW5nIiBwYXJhbWF0ZXJzIGlzIHRoZSBiZWRyb2NrIG9mIHN0YXRzLiBUaGUgZ29hbCBpcyB0byAicmVjb3ZlciIgdGhlIHBvcHVsYXRpb24gcGFyYW1ldGVyIGZyb20gYSBzYW1wbGUuIAoKCiMjIENoZWNrcG9pbnQgCgpNb3N0IG9mdGVuIHlvdSB3aWxsIHVzZSBmdW5jdGlvbnMgb24gb2JzZXJ2YXRpb25hbCBkYXRhIHJhdGhlciB0aGFuIHNpbXVsYXRlZCBkYXRhLiAKCkxvYWQgdGhlIGBkaWFtb25kc2AgZGF0YSBzZXQ6CgpgYGB7ciBsb2FkIGRpYW1vbmRzfQpkYXRhKCJkaWFtb25kcyIpCmBgYAoKVGhlIHN0YW5kYXJkIGRldmlhdGlvbiBvZiBwcmljZSBpcyBqdXN0IGBzZCgpYCBvbiB0aGUgYHByaWNlYCB2ZWN0b3IgaW5zaWRlIHRoZSBgZGlhbW9uZHNgIHRpYmJsZToKCmBgYHtyIHNkIHByaWNlfQpkaWFtb25kcyAlPiUgCiAgc3VtbWFyaXNlKHNkKHByaWNlKSkKYGBgCgpSZXBsaWNhdGUgdGhlIHJlc3VsdHMgZnJvbSBgc2QoKWAgd2l0aCBgbXlfc2QoKWAuCgpgYGB7ciBjaGVja3BvaW50IG15X3NkIHByaWNlfQpkaWFtb25kcyAlPiUgCiAgc3VtbWFyaXNlKG15X3NkKHByaWNlKSkKYGBgCgojIyBDaGVja3BvaW50CgpEbyBjYXJhdHMgaW5mbHVlbmNlIHRoZSBwcmljZSBvZiBkaWFtb25kcz8gV2UgY2FuIGJ1aWxkIGEgbW9kZWw6CgokJApcYmVnaW57YWxpZ25lZH0KXHRleHR7cHJpY2VzfSAmPSBmKFx0ZXh0e2NhcmF0c30pICsgXGVwc2lsb24gXFwKICAgICAgICAgICAgICAgICAgICAgJj0gXGJldGFfMCArIFxiZXRhXzEoXHRleHR7Y2FyYXRzfSkgKyBcZXBzaWxvbgpcZW5ke2FsaWduZWR9CiQkCndoZXJlICRcYmV0YV8xJCBjYXB0dXJlcyB0aGUgYXZlcmFnZSBlZmZlY3Qgb2YgY2FyYXRzIG9uIHByaWNlcy4gSWYgJFxoYXR7XGJldGFfMX0kICh0aGUgZXN0aW1hdGUpIGlzIHBvc2l0aXZlLCB0aGVuIG1vcmUgY2FyYXRzID0gaGlnaGVyIHByaWNlcywgb24gYXZlcmFnZS4gVGhlIGZvcm11bGEgZm9yICRcYmV0YV8xJCBpczoKCiQkClxoYXR7XGJldGFfMX0gPSBcZnJhY3tcc3VtX3tpPTF9Xm4gKHhfaSAtIFxiYXJ7eH0pKHlfaSAtIFxiYXJ7eX0pfXtcc3VtX3tpPTF9Xm4gKHhfaSAtIFxiYXJ7eH0pXjJ9CiQkCldlIGNhbiBlc3RpbWF0ZSB0aGUgcGFyYW1ldGVycyB3aXRoIGBsbSgpYDoKCmBgYHtyIGxtIGRpYW1vbmRzfQpsbShmb3JtdWxhID0gcHJpY2UgfiBjYXJhdCwgZGF0YSA9IGRpYW1vbmRzKSAlPiUgCiAgc3VtbWFyeSgpCmBgYAoKV3JpdGUgYSBmdW5jdGlvbiBjYWxsZWQgYG15X2xtKClgIHRoYXQgdGFrZXMgYW4gYHhgIGFuZCBgeWAgYXJndW1lbnQgYW5kIGNhbGN1bGF0ZXMgdGhlIHJlZ3Jlc3Npb24gY29lZmZpY2llbnQgb2YgYHhgIG9uIGB5YC4gVGhlbiByZXBsaWNhdGUgdGhlIHJlc3VsdHMgZnJvbSBgbG0oZm9ybXVsYSA9IHByaWNlIH4gY2FyYXQsIGRhdGEgPSBkaWFtb25kcylgLiBUaGluayBhYm91dCB3aGF0IGNvZGUgeW91IGNhbiByZS11c2UgZnJvbSBgbXlfc2QoKWAuCgpgYGB7ciBjaGVja3BvaW50IG15X2xtfQpteV9sbSA9IGZ1bmN0aW9uKHgsIHkpewogICMgMS4gTlVNRVJBVE9SCiAgIyMgc3RlcCAxCiAgeF9kZXZpYXRpb25zID0geCAtIG1lYW4oeCkKICB5X2RldmlhdGlvbnMgPSB5IC0gbWVhbih5KQogICMjIHN0ZXAgMgogIHByb2R1Y3RfZGV2aWF0aW9ucyA9IHhfZGV2aWF0aW9ucyAqIHlfZGV2aWF0aW9ucwogICMjIHN0ZXAgMwogIG51bWVyYXRvciA9IHN1bShwcm9kdWN0X2RldmlhdGlvbnMpCiAgIyAyLiBERU5PTUlOQVRPUgogICMjIHN0ZXAgMQogIHhfZGV2aWF0aW9uc19zcXVhcmVkID0geF9kZXZpYXRpb25zXjIKICAjIyBzdGVwIDIKICBkZW5vbWluYXRvciA9IHN1bSh4X2RldmlhdGlvbnNfc3F1YXJlZCkKICAjIDMuIHB1dCBpdCBhbGwgdG9nZXRoZXIKICBiZXRhID0gbnVtZXJhdG9yIC8gZGVub21pbmF0b3IKICAjIFJFVFVSTiEhCiAgcmV0dXJuKGJldGEpCn0KYGBgCgpgYGB7ciBjaGVja3BvaW50IG15X2xtIHRlc3R9Cm15X2xtKHggPSBkaWFtb25kcyRjYXJhdCwgeSA9IGRpYW1vbmRzJHByaWNlKQpgYGAKCiMgQ29uZGl0aW9uYWwgZXhlY3V0aW9uIAoKV2hhdCAqKmlmKiogeW91IHdhbnQgeW91ciBmdW5jdGlvbiB0byBkbyBkaWZmZXJlbnQgdGhpbmdzIGRlcGVuZGluZyBvbiB0aGUgaW5wdXQ/CgpVc2UgYW4gYGlmYCBzdGF0ZW1lbnQhIAoKVGhpcyBmdW5jdGlvbiBjaGVja3MgKippZioqIHRoZSBhcmd1bWVudCBpcyBlcXVhbCB0byB0d28uIElmIGl0IGlzLCBhZGQgdHdvIGFuZCByZXR1cm4uIAoKYGBge3IgYWRkX3R3b19pZiB9CmFkZF90d29faWYgPC0gZnVuY3Rpb24oeCkgeyAKICBpZih4ID09IDIpewogICAgb3V0cHV0IDwtIHggKyAyCiAgICByZXR1cm4ob3V0cHV0KQogIH0KfQpgYGAKClRyeSBpdCBvdXQ6CgpgYGB7ciBhZGRfdHdvX2lmIGRlbW99CmFkZF90d29faWYoeCA9IDEpCmBgYAoKVGhlIGBpZih4PT0yKWAgaXMgdGhlICoqbG9naWNhbCB0ZXN0KiosIGEgdGVzdCB0aGF0IG9ubHkgcmV0dXJucyBgVFJVRWAgb3IgYEZBTFNFYDoKCmBgYHtyIGJvb2xlYW4gMX0KMiA9PSAyCmBgYAoKYGBge3IgYm9vbGVhbiAyfQoyID09IDMKYGBgCgpTbyB3aGVuIGBpZih4PT0yKWAgZXZhbHVhdGVzIHRvIGBUUlVFYCB0aGUgZnVuY3Rpb24gcHJvY2VlZHMuIAoKIyMjIExvZ2ljYWwgdGVzdHMKCkxpa2UgaW4gIGBkcGx5cjo6ZmlsdGVyKClgIHdlIGNhbiB1c2UgdGhlIGZvbGxvd2luZyBjb25kaXRpb25hbHMgaW5zaWRlIGBpZigpYDoKCiogYD09YDogImlzIGVxdWFsIHRvIgoqIGAhPWA6ICJpcyBub3QgZXF1YWwgdG8iCiogYCZgOiAiYW5kIgoqIGB8YDogIm9yIgoqIGA+YCwgYD49YDogImdyZWF0ZXIgdGhhbiIsICJsZXNzIHRoYW4gb3IgZXF1YWwgdG8iCiogYDxgLCBgPD1gOiAibGVzcyB0aGFuIiwgImxlc3MgdGhhbiBvciBlcXVhbCB0byIKCiMjIyBgZWxzZWAKCkJ1dCB3aGF0IGlmIHdlIHBhc3MgYW4gYXJndW1lbnQgb3RoZXIgdGhhbiB0d28/IAoKYGBge3IgYWRkX3R3b19pZiBub3QgMn0KYWRkX3R3b19pZih4ID0gMykKYGBgCgpOb3RoaW5nIGhhcHBlbnMuIAoKV2hhdCB3ZSBuZWVkIGlzIGEgd2F5IHRvICoqaGFuZGxlKiogdGhlICoqZXhjZXB0aW9uKiogLS0gYSB3YXkgdG8gZGVhbCB3aXRoIGFyZ3VtZW50cyB0aGF0IGFyZSBub3QgZXF1YWwgdG8gMi4gCgpUaGlzIGlzIHdoZXJlIGBlbHNlYCBjb21lcyBpbi4KClRoZSBnZW5lcmFsIHN0cnVjdHVyZSBvZiBhbiBgaWYtZWxzZWAgc3RhdGVtZW50IGlzOgoKYGBge3IgaWYgZWxzZSBvdXRsaW5lLCBldmFsPUZBTFNFfQppZihUUlVFKSB7ICMgaWYgdGhlIHRlc3QgaXMgdHJ1ZQogICMgZG8gdGhpcyB0aGluZwp9IGVsc2UgeyAjIG90aGVyd2lzZQogICMgZG8gdGhpcyBvdGhlciB0aGluZwp9CmBgYAoKTGV0J3MgbW9kaWZ5IGBhZGRfdHdvX2lmYCB0byBhZGQgdGhyZWUgaWYgYW4gYXJndW1lbnQgaXMgbm90IHR3bzoKCmBgYHtyIGFkZF90d29faWYgZWxzZX0KYWRkX3R3b19pZiA8LSBmdW5jdGlvbih4KSB7IAogIGlmKHggPiAyICYmIHggPCA0KXsKICAgIG91dHB1dCA8LSB4ICsgMgogICAgIyBkbyBzb21lIGZ1bmN0aW9uCiAgfSBlbHNlIHsKICAgIG91dHB1dCA8LSB4IC0gMgogICAgIyBkbyBzb21lIG90aGVyIGZ1bmN0aW9uCiAgfQogIHJldHVybihvdXRwdXQpCn0KYGBgCgpgYGB7cn0KYWRkX3R3b19pZih4ID0gMikKYGBgCgoKTm90aWNlIGhvdyB0aGUgYHJldHVybigpYCBzdGF0ZW1lbnQgaXMgb3V0c2lkZSB0aGUgYGlmLi4uZWxzZWAgc2NvcGUuIChBbnl0aGluZyBpbiBSIHdyYXBwZWQgaW4gYHt9YCBpcyBhICJzY29wZSIpLgoKSW4gdGhlb3J5IHlvdSBjYW4gY2hhaW4gdG9nZXRoZXIgYXMgbWFueSBgaWYuLi5lbHNlYCBzdGF0ZW1lbnRzIGFzIHlvdSB3YW50IGJ5IGFkZGluZyBtb3JlIGxvZ2ljYWwgdGVzdHM6CgpgYGB7ciBhZGRfdHdvX2lmIGJhZCwgZXZhbD1GQUxTRX0KYWRkX3R3b19pZiA8LSBmdW5jdGlvbih4KSB7IAogIGlmKHggPT0gMil7CiAgICBvdXRwdXQgPC0geCArIDIKICB9IGVsc2UgaWYoeCA9PSAzKSB7CiAgICBvdXRwdXQgPC0geCArIDMKICB9IGVsc2UgaWYoeCA9PSA0KXsKICAgIG91dHB1dCA8LSB4ICsgMwogIH0gZWxzZSB7IAogICAgcHJpbnQoInRoaXMgaXMgYSBiYWQgZnVuY3Rpb24iKQogIH0KICByZXR1cm4ob3V0cHV0KQp9CmBgYAoKQnV0IHlvdSB3YW50IHRvIGF2b2lkIHRoaXMuIEl0J3MgaGFyZCB0byByZWFkIGFuZCBwcm9iYWJseSBub3QgbmVjZXNzYXJ5LiBUaGUgY2hhcHRlciBoYXMgYSBmZXcgc3VnZ2VzdGlvbnMgZm9yIGFsdGVybmF0aXZlcy4gRm9yIG5vdyB3ZSB3aWxsIHN0aWNrIHRvIG9uZSBsb2dpY2FsIHRlc3QuIAoKIyMgQ2hlY2twb2ludAoKV3JpdGUgYSBmdW5jdGlvbiBgdHJ1dGhfb3JfZGFyZWAgdGhhdCB0YWtlcyBhIHZlY3RvciBhbmQgY2hlY2tzIHdoZXRoZXIgdGhlIHRoaXJkIGVudHJ5IGlzIHBvc2l0aXZlLiBJZiB5ZXMsIHByaW50ICJ0cnV0aCIuIElmIG5vLCBwcmludCAiZGFyZSIuICAKCioqVXBkYXRlKiogV2UgY2hhbmdlZCB0aGlzIHRvIGFsc28gZGVtbyBgc3RvcCgpYC4KCmBgYHtyIGNoZWNrcG9pbnQgdHJ1dGhfb3JfZGFyZX0KdHJ1dGhfb3JfZGFyZSA9IGZ1bmN0aW9uKHgpewogIGlmKGxlbmd0aCh4KSA9PSAxKSBzdG9wKCJ2ZWN0b3IgaXMgdG9vIHNob3J0IikKICBpZih4WzNdICUlIDIgPT0gMCkgewogICAgd2FybmluZygiVGhlIGNoYWxsZW5nZSBpcyB0byBkbyAiLCByb3VuZChybm9ybSgxLCBtZWFuID0gMTAsIHNkID01KSwwKSwgIiBkYXJlcyIpCiAgICAjcHJpbnQocGFzdGUoKSkKICB9IGVsc2UgewogICAgcHJpbnQoInRydXRoIikKICB9Cn0KYGBgCgpgYGB7cn0KdmVjID0gYygyLDMsNCw1KQp0cnV0aF9vcl9kYXJlKDIpCmBgYAoKCiMjIGBpZmVsc2UoKWAKClRoZSBgaWYuLi5lbHNlYCBzY29wZSBvbmx5IHdvcmtzIGZvciB2ZWN0b3JzIG9mIGxlbmd0aCAxLgoKUnVuIHRoaXMgY2h1bms6CgpgYGB7ciBpZi1lbHNlIGxlbmd0aCAxfQphbm90aGVyX3ZlY3RvciA8LSBjKDEsIE5BLCAzLCBOQSkKaWYoaXMubmEoYW5vdGhlcl92ZWN0b3IpKSB7CiAgIk5BIDooIgp9IGVsc2V7CiAgIm51bWJlciIKfQpgYGAKCmBpZmAgc3RvcHBlZCBhZnRlciB0aGUgZmlyc3QgZW50cnkgb2YgYGFub3RoZXJfdmVjdG9yYC4KClVzZSBgaWZlbHNlKClgIHRvIHJ1biBhbiBgaWYuLmVsc2VgIHNjb3BlIG92ZXIgYW4gZW50aXJlIHZlY3RvcjoKCmBgYHtyIGlmZWxzZX0KaWZlbHNlKHRlc3QgPSBpcy5uYShhbm90aGVyX3ZlY3RvciksIHllcyA9IDAsIG5vID0gImEiKQpgYGAKCiMgQXBwZW5kaXgKCiMjIERvdC1kb3QtZG90CgpZb3UgbWF5IGhhdmUgbm90aWNlZCB0aGF0IG1hbnkgZnVuY3Rpb25zIGluIFIgaGF2ZSB0aGUgYXJndW1lbnQgYC4uLmAuIAoKRm9yIGluc3RhbmNlLCB0aGUgYXJndW1lbnRzIHRvIGBtZWFuKClgIGFyZToKCmBgYHtyLCBldmFsPUZBTFNFfQptZWFuKHgsIC4uLikKYGBgCgpUaGUgYXJndW1lbnQgYHhgIGlzIG1hbmRhdG9yeS4gVGhlIGFyZ3VtZW50IGAuLi5gIGlzIG9wdGlvbmFsLiBXaGF0IGlzIGNvb2wgYWJvdXQgYC4uLmAgaXMgdGhhdCB5b3UgY2FuIHBhc3MgYW55IG51bWJlciBvZiBhcmJpdHJhcnkgYXJndW1lbnRzIHRvIGl0LiAKCkZvciBpbnN0YW5jZSwgd2hhdCBpZiB5b3UgaGF2ZSBgTkFgIGluIGEgdmVjdG9yPyAKCmBgYHtyIHZlY3RvciB3aXRoIE5BfQp2IDwtIGMoMSwyLE5BKQpgYGAKCmBtZWFuKHgpYCB3aWxsIHJldHVybiBgTkFgOgoKYGBge3IgbWVhbiB2ZWMgd2l0aCBOQX0KbWVhbih2KQpgYGAKCmJ1dCB5b3UgY2FuIHBhc3MgYG5hLnJtYCB0byBgLi4uYCBzbyB0aGF0IGBtZWFuKClgIG9ubHkgbG9va3MgYXQgbnVtZXJpY2FsIHZhbHVlczoKCmBgYHtyIG1lYW4gdmVjIHdpdGggTkEgYW5kIG5hLnJtfQptZWFuKHYsIG5hLnJtID0gVFJVRSkKYGBgCgpEaXR0byBgc2QoKWAuIFdpdGhvdXQgYG5hLnJtYDoKCmBgYHtyIHNkIHZlYyB3aXRoIE5BfQpzZCh2KQpgYGAKCldpdGggYG5hLnJtYDoKCmBgYHtyIHZlYyB3aXRoIE5BIGFuZCBuYS5ybX0Kc2QodiwgbmEucm0gPSBUUlVFKQpgYGAKClRoaXMgdW5kZXJzY29yZXMgdGhlIHJlYWwgdmFsdWUgb2YgYC4uLmA6IHBhc3Npbmcgb3B0aW9uYWwgYXJndW1lbnRzIHRvIG90aGVyIGZ1bmN0aW9ucyB0aGF0IGhhdmUgb3B0aW9uYWwgYXJndW1lbnRzIC0tIGxpa2UgYG1lYW4oKWAgYW5kIGBzZCgpYC4KCiMjIyBDaGVja3BvaW50CgpTYXkgeW91IGhhdmUgdGhpcyB2ZWN0b3Igd2l0aCBOQXM6CgpgYGB7cn0KIyBjcmVhdGUgYSB2ZWN0b3Igb2YgcmFuZG9tIG51bWJlcnMKbmFfdmVjdG9yIDwtIHJub3JtKG4gPSAxMDAwLCBtZWFuID0gMCwgc2QgPSAxKQojIHJhbmRvbWx5IHJlcGxhY2Ugc29tZSBvZiB0aGUgdmFsdWVzIGFzIE5BCm5hX3ZlY3RvcltzYW1wbGUoMToxMDAwLCAxMDApXSA8LSBOQQpgYGAKCldyaXRlIGEgZnVuY3Rpb24gY2FsbGVkIGB6X3Njb3JlYCB0aGF0IGNhbGN1bGF0ZXMgdGhlIHotc2NvcmUgb2YgZWFjaCBlbGVtZW50IG9mIGBuYV92ZWN0b3JgLiBUaGUgZm9ybXVsYSBpczoKCiQkCnpfaSA9IFxmcmFje3hfaSAtIFxiYXJ7eH19e3N9CiQkCgp3aGVyZSAkXGJhcnt4fSQgaXMgdGhlIHNhbXBsZSBtZWFuIGFuZCAkcyQgaXMgdGhlIHNhbXBsZSBzdGFuZGFyZCBkZXZpYXRpb24uIE1ha2Ugc3VyZSB5b3VyIGZ1bmN0aW9uIGNhbiBhY2NvdW50IGZvciBOQXMgYnkgaW5jbHVkaW5nIGAuLi5gIGFuZCBwYXNzaW5nIHRoYXQgdG8gYG1lYW4oeCwgLi4uKWAgYW5kIGBzZCh4LCAuLi4pYC4KCmBgYHtyIGNoZWNrcG9pbnQgei1zY29yZX0Kel9zY29yZSA9IGZ1bmN0aW9uKHgsIC4uLil7CiAgeiA9ICh4IC0gbWVhbih4LCAuLi4pKSAvIHNkKHgsIC4uLikKICByZXR1cm4oeikKfQpgYGAKClRlc3QgaXQgb3V0IG9uIGBuYV92ZWN0b3JgOgoKYGBge3IgY2hlY2twb2ludCB6LXNjb3JlIHRlc3R9Cnpfc2NvcmUoeCA9IG5hX3ZlY3RvciwgbmEucm0gPSBUUlVFKSAlPiUgCiAgbWVhbih4ID0gLiwgbmEucm0gPSBUUlVFKQpgYGAKClNlY3Rpb24gMTkuNS4zIGxpbmtzIHRvIG90aGVyIHdheXMgdG8gdXNlIGAuLi5gLiBUaGV5J3JlIGhhbmR5IHdoZW4geW91IHdyaXRlIGZ1bmN0aW9ucyB0aGF0IHRha2UgZW50aXJlIGRhdGEgc2V0cyBhcyBhcmd1bWVudHMuIEZvciBtb3JlIHNlZSBDaGFwdGVycyAxOC0yMSBvZiB0aGUgW1RpZHl2ZXJzZSBEZXNpZ24gR3VpZGVdKGh0dHBzOi8vZGVzaWduLnRpZHl2ZXJzZS5vcmcvZG90cy1wb3NpdGlvbi5odG1sKS4KCiMjIyBBc2lkZTogcmFuZG9tbHkgc2FtcGxpbmcgYSB2ZWN0b3IKCkxldCdzIHJhbmRvbWx5IHJlcGxhY2Ugc29tZSBvZiB0aGUgdmFsdWVzIGluIGByYW5kb21fbm9ybWFsX251bWJlcnNgIHVzaW5nICoqaW5kZXhpbmcqKiBhbmQgYHNhbXBsZSgpYC4KClJlY2FsbCB0aGF0IGBbXWAgaW5kZXhlcyB2ZWN0b3JzIGJ5ICoqcG9zaXRpb24qKi4gRm9yIGluc3RhbmNlLCB0aGUgZmlyc3QgdGhyZWUgZWxlbWVudHMgb2YgYHJhbmRvbV9ub3JtYWxfbnVtYmVyc2A6CgpgYGB7ciBpbmRleGluZ30KcmFuZG9tX25vcm1hbF9udW1iZXJzWzE6M10KYGBgCgphbmQgYHNhbXBsZSgpYCB3aWxsIHJhbmRvbWx5IHNhbXBsZSBhbnkgdmVjdG9yLiBGb3IgaW5zdGFuY2UsIHJhbmRvbWx5IHNhbXBsZSB0d28gIGludGVnZXJzIGJldHdlZW4gMSBhbmQgMTA6CgpgYGB7ciBzYW1wbGV9CnNhbXBsZSh4ID0gMToxMCwgc2l6ZSA9IDMpCmBgYAoKRm9yIGluc3RhbmNlIEkgY291bGQgcmFuZG9tbHkgc2FtcGxlIGEgdmVjdG9yOgoKYGBge3IgZGVtbyBzYW1wbGV9CiMgdmVjdG9yIG9mIDEsIDIsIC4uLCAxMAp4IDwtIDE6MTAKIyB0aGUgbGVuZ3RoIG9mIHRoZSB2ZWN0b3IKbiA8LSBsZW5ndGgoeCkKIyByYW5kb21seSBkcmF3IHRocmVlIGVsZW1lbnRzIGZyb20geAp4W3NhbXBsZSh4ID0gMTpuLCBzaXplID0gMyldCmBgYAoKc28gd2UgY2FuIGNvbWJpbmUgaW5kZXhpbmcgYW5kIHNhbXBsZSB0byByYW5kb21seSBzd2l0Y2ggdmFsdWVzIGluIGEgdmVjdG9yIHRvIE5BOgoKYGBge3J9CiMgZ2V0IHRoZSBsZW5ndGggb2YgcmFuZG9tX25vcm1hbF9udW1iZXJzICgxMDAwKQpuIDwtIGxlbmd0aChyYW5kb21fbm9ybWFsX251bWJlcnMpCiMgZnJvbSB0aGUgcG9zaXRpb25hbCBpbmRleCBvZiAxOm4sIHJhbmRvbWx5IGNob29zZSAxMDAgb2YgdGhlbSwgCiMjIGFuZCByZWFzc2lnbiB0aGVpciBjb3JyZXNwb25kaW5nIHZhbHVlcyBpbiByYW5kb21fbm9ybWFsX251bWJlcnMgdG8gTkEKcmFuZG9tX25vcm1hbF9udW1iZXJzW3NhbXBsZSgxOm4sIDEwMCldIDwtIE5BCmBgYAoK