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
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?
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?!
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.
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)
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.
Arguments
Arguments of length 1
Everything in R is a vector.
For instance the number 2 is a vector:
[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:
[1] 4
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)
[1] 12
Local variables
Inside square_sum
you defined an object output
. But if you call it you’ll get an error:
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!
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
}
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
:
[1] 13
[1] "function"
Arguments of length \(n\)
sum()
can add a single number:
[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.
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
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.
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:
- calculate the deviations \(x_i - \bar{x}\) where \(\bar{x}\) is the sample mean
- square the deviations
- add up the squared deviations
- multiply by \(\frac{1}{n-1}\) (use
length()
) to get the length of x
, i.e. \(n\)
- 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.
Checkpoint
Most often you will use functions on observational data rather than simulated data.
Load the diamonds
data set:
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))
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
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:
The if(x==2)
is the logical test, a test that only returns TRUE
or FALSE
:
[1] TRUE
[1] FALSE
So when if(x==2)
evaluates to TRUE
the function proceeds.
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”
else
But what if we pass an argument other than two?
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)
}
[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.
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
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"
Appendix
Dot-dot-dot
You may have noticed that many functions in R have the argument ...
.
For instance, the arguments to mean()
are:
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?
mean(x)
will return NA
:
[1] NA
but you can pass na.rm
to ...
so that mean()
only looks at numerical values:
[1] 1.5
Ditto sd()
. Without na.rm
:
[1] NA
With na.rm
:
[1] 0.7071068
This underscores the real value of ...
: passing optional arguments to other functions that have optional arguments – like mean()
and sd()
.
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.
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