Course bayesian methods definition: A method of figuring out unobservable quantities given known facts that uses probability to describe the uncertainty over what the values of the unknown quantities could be.

*4 hours, 23 Videos, 58 Exercises

Strengths of bayesian methods:

  • Learns from data
  • Used for hyp. testing and linear regression.
  • Flexible enough to handle problem-specific models.
    • can include information sources in addition to the data.
    • can make comparisons between groups or data sets.
    • can use the result of a bayesian analysis to do decision analysis
    • can change the underlying statistical model.

Prior = a probability distribution that represents what the model knowns before seeing the data.

Posterior = a probability distribution that represents what the model known after having seen the data.

Bayesian Inference requires data, priors, and a generative model.

  • a generative model is a mathematical expression with a set of rules used to feed parameter values and simulate data.



Example: Probability that we have found a vaccine that cures the zombie outbreak.

# parameters
p_success <- .15 # probability of success
n_zombies <- 13 # trails

# simulate data
data <- c()
for(zombie in 1:n_zombies){
  # save if prop is between 0 & 1 and greater than our prob. of success
  data[zombie] <- runif(1, min=0, max=1) < p_success 
}

data <- as.numeric(data)
data
mean(data) # our posterior is close to our theorized probability of success of .15
sum(data) # number of successes

binomial function

  • Parameters - probability and trial size.
N=13

# prob. of success, close to our prior belief
sum(rbinom(n=1, size=N, prob=.15)) / N 
Lots of simulations
set.seed(909)

# prob. of success, close to our prior belief
sum(rbinom(n=100000, size=100, prob=.10)) / (100000*100) 
hist(rbinom(n=100000, size=100, prob=.10))



Adding an uninformed prior distribution, includes out uncertainty in a binomial distribution.

# number of observations
n_samples <- 100000 

# number of trails
n_ads_shown <- 100 

 # probability of success with a uniform prior representing our uncertainty
proportion_clicks <- runif(n = n_samples, min = 0.0, max = 0.2)

n_visitors <- rbinom(n = n_samples, size = n_ads_shown, prob = proportion_clicks)

# posterior probability, close to our previous prob constrained at .10
sum(n_visitors) / (100000*100) 

# probability of visitors, not a uniform dist like when  probability was constrained to .10
hist(n_visitors) 

# a uniform distribution of our uncertainty
hist(proportion_clicks) 

# probability of 5 clicks or more
sum(as.numeric(n_visitors >= 5)) / n_samples 





Updating our prior:



Bayesian inference = conditioning on data, in order to learn about parameter values.

  • What would be the unknown parameter value conditional on 7 visitors? .47
  • What would be the unknown parameter value conditional on 11 visitors? .87
prior <- data.frame(n_samples, n_ads_shown, proportion_clicks, n_visitors)
head(prior)

Now we collected data on 100 observations and 13 clicked our add, we can update our prior to calculate the probability of getting 5 clicks or more.

posterior  <- prior[prior$n_visitors == 13, ]

# updated posterior
head(posterior) 

prior <- posterior

head(prior)

n_samples <-  nrow(prior)

n_ads_shown <- 100

prior$n_visitors <- rbinom(n=n_samples, size = n_ads_shown, 
                           prob=prior$proportion_clicks)

hist(prior$n_visitors)

# new probability of 5 clicks or more after updating our belief from our posterior
sum(prior$n_visitors >= 5) / length(prior$n_visitors)  

Note. This approach would scale bad if we had more data or complexity.



Using the beta distribution

  • Takes 2 parameters, alpha and beta.
beta_sample <- rbeta(n = 1000000, shape1 = 1, shape2 = 1)
hist(beta_sample)
head(beta_sample)

beta_sample <- rbeta(n = 1000000, shape1 = 10, shape2 = 10)
hist(beta_sample)

# changing the shape of the beta distribution

in our add example if most adds get clicked 5% of the time, but some adds get clicked as low as 2% and as high as 8%, what beta parameters would best capture this prior distribution?

hist(rbeta(n=100, shape1 = 5, shape2 = 95))

New tweak to our previous model, adding an informed prior and data to inform the new posterior

n_draws <- 100000
n_ads_shown <- 100

# Change the prior on proportion_clicks
proportion_clicks <- rbeta(n_draws, shape1 = 5, shape2 = 95) # NEW CHANGE
n_visitors <- rbinom(n_draws, size = n_ads_shown, prob = proportion_clicks)
prior <- data.frame(proportion_clicks, n_visitors)
posterior <- prior[prior$n_visitors == 13, ]

# This plots the prior and the posterior in the same plot
par(mfcol = c(2, 1))
hist(prior$proportion_clicks, xlim = c(0, 0.25))
hist(posterior$proportion_clicks, xlim = c(0, 0.25))



Comparing between groups or datasets; example video (13 out of 100 clicked) vs text (6 out of 100 clicked) ads

n_draws <- 100000
n_ads_shown <- 100
proportion_clicks <- runif(n_draws, min = 0.0, max = 0.2)
n_visitors <- rbinom(n = n_draws, size = n_ads_shown, 
                     prob = proportion_clicks)
prior <- data.frame(proportion_clicks, n_visitors)

# Create the posteriors for video and text ads
posterior_video <- prior[prior$n_visitors == 13, ] # 13 of 100 clicked
posterior_text <- prior[prior$n_visitors == 6, ] # 6 of 100 clicked


# Visualize the posteriors
hist(posterior_video$proportion_clicks, xlim = c(0, 0.25))

hist(posterior_text$proportion_clicks, xlim = c(0, 0.25))

Compare difference in posterior proportions between video and text ads

posterior <- data.frame(
    video_prop = posterior_video$proportion_clicks[1:4000],
    text_prop  = posterior_text$proportion_click[1:4000])
    
# Calculate the posterior difference: video_prop - text_prop
posterior$prop_diff <- posterior$video_prop - posterior$text_prop

# Visualize prop_diff
hist(posterior$prop_diff)

# Summarize prop_diff
summary(posterior$prop_diff)
Most likely difference, and probability that the proportion of clicks us larger for the video than text ad.
median(posterior$prop_diff)
sum(posterior$prop_diff > 0)/length(posterior$prop_diff) 
Note. the posterior mean or median is the summary distribution over some parameter, while the mean or median of a data is a summary of the data.



Credible interval, contains the underlying parameter with a certain probability.



Decision analysis: taking a result of a statistical analysis and post process to make an informed decision (i.e., save lives, make more money).

  • example: video ads cost 25 cents, text 5 cents, and we make on average $2.53 per visitor.
video_cost <- .25
text_cost <- .05
visitor_spend <- 2.53

# P(people  that click the video ad * how much we made on visitors - cost)
posterior$video_profit <- posterior$video_prop * visitor_spend - video_cost 

# P(people that click the text ad * how much we made on visitors - cost)
posterior$text_profit <- posterior$text_prop * visitor_spend - text_cost 

# difference in profits this is the distribution we care about
posterior$profit_diff <- posterior$video_profit - posterior$text_profit 
head(posterior)
hist(posterior$profit_diff)

# Calculate a "best guess" for the difference in profits
median(posterior$profit_diff)

# Calculate the probability that text ads are better than video ads
sum(posterior$profit_diff < 0) / length(posterior$profit_diff)
In looking at the histogram there is no real difference in profits over lost yet text ads are marginally cheaper to run.



Changing the underlying statistical model

  • binomial will not work here.
  • instead, we use the poisson distribution modeling the number of clicks per day.
  • Explore the poisson distribution. Example: on a cloudy day what is the probability of breaking even if we sell on average 11.5 ice creams?
ice_cream <- rpois(n=10000, lambda = 11.5) # lambda is our average count
hist(ice_cream)
sum(ice_cream >= 15)/ length(ice_cream)
unlikely that we will break even.

Applying it to our ad problem.

  • We now get charged by the day, rather than by ad, to run an ad. Our clicks are now per day instead of per ad.
  • new day shows that in 1 day we received 19 clicks.
  • how many daily clicks should we expect on average?
n_draws <- 100000
n_ads_shown <- 100

# flat prior from 0 to 80 clicks per day
mean_clicks <- runif(n_draws, min = 0, max = 80) 

# 2 parameters size and mean
n_visitors <- rpois(n_draws, lambda = mean_clicks) 
                     
# probability of getting 19 clicks
posterior <- prior[prior$n_visitors == 19, ] 

summary(posterior$mean_clicks)

quantile(posterior$mean_clicks, prob=c(.05, .95))



Probability rules

  • Any number between 0 and 1
  • A statement (un)certainty ##### Probability of drawing one of the four aces in a stack of 52 cards
prob_to_draw_aces <- 4/52
prob_to_draw_aces
Probability of drawing all four aces in a row
prob_to_draw_four_aces <- (4/52) * (3/51) * (2/50) * (1/49)
prob_to_draw_four_aces

Calculating probabilities with functions rather than simulating data, conditioning on 10%

  • conditional probability of getting 13 clicks on our adds given that the success rate is 10%
n_visitors <- rbinom(n = 100000, size = 100, prob = 0.1)
sum(n_visitors == 13) / length(n_visitors)

# or 
dbinom(13, 100, .10)
probability of getting more than 13 clicks
n_visitors <- rbinom(n = 100000, size = 100, prob = 0.1)
sum(n_visitors > 13) / length(n_visitors)

# or 
pbinom(13, 100, .10, lower.tail=FALSE)



Conditioning on the data

n_ads_shown <- 100
n_visitors <- seq(0, 100, by=1)
proportion_clicks <- seq(0, 1, by=.01)

pars <- expand.grid(proportion_clicks=proportion_clicks, 
                    n_visitors=n_visitors)

pars$prior <- dunif(pars$proportion_clicks, min=0, max=.2)

pars$likelihood <- dbinom(pars$n_visitors, size=n_ads_shown, 
                          prob=pars$proportion_clicks)

pars$probability <- pars$likelihood * pars$prior

pars$probability <- pars$probability / sum(pars$probability)
sum(pars$probability)
head(pars)

# conditioning on data when visitors equal 6
pars <- pars[pars$n_visitors == 6,]

# normalize again
pars$probability <- pars$probability / sum(pars$probability)


# Plot the posterior pars$probability
plot(pars$proportion_clicks, y=pars$probability, type="h")



Bayes theorem:

\[ \underbrace{p(\theta|D)}_{posterior} ~=~ \frac{\overbrace{p(D|\theta)}^{likelihood}~ \overbrace{p(\theta)}^{prior}} {\underbrace{p(D)}_{evidence}} \]



The probability of different parameters \(\theta\) given some data \(D\) \(=\) The likelihood: the relative probability of the data given different parameter values \(P(D|\theta))\) \(\times\) The prior: the probability of different parameters before seeing the data \(P(\theta)\) \(\div\) The total sum of the likelihood weighted by the prior \(\sum{P(D|\theta)\times P(\theta)}\)



Mathematical notation for our model, convenient way to define model.

\[ \eta_{ads} = 100 \]

\[ P_{clicks} \sim Uniform(0.0,0.2) \]

\[ \eta_{visitors} \sim Binomial(\eta_{ads}, p_{clicks}) \]

for the poisson model

\[ \mu_{clicks} \sim Uniform(min:0, max:80) \]

\[ n_{visitors} \sim Poisson(\mu_{clicks}) \]





working with the normal distribution

# mean of 20, sd of 2
rnorm(n=5, mean=20, sd=2) 

# temperature readings from a lake
temp <- c(19, 23, 20, 17, 23) 

# relative likelihood of our data points (not probabilities)
likelihood <- dnorm(x= temp, mean=20 , sd=2) 
likelihood

# multiply all numbers together (small number)
prod(likelihood) 

# working on the log scale to avoid poor scability of data
log(likelihood)



example: how smart are zombies? Data are from IQs of zombies.

  • What we’re interested in is how much we can learn about the mean zombie IQ from this data.

\[ \mu \sim Normal(mean:100, sd:100) \]

\[ \sigma \sim Uniform(min:0, max:50) \]

\[ IQ_i \sim Normal(\mu, \sigma) \]

\[ iq = 55, 44, 34, 18, 51, 40, 40, 49, 48, 46 \]



fit the model

# The IQ of a bunch of zombies
iq <- c(55, 44, 34, 18, 51, 40, 40, 49, 48, 46)

# Defining the parameter grid
pars <- expand.grid(mu = seq(0, 150, length.out = 100), 
                    sigma = seq(0.1, 50, length.out = 100))

# Defining and calculating the prior density for each parameter combination
pars$mu_prior <- dnorm(pars$mu, mean = 100, sd = 100)
pars$sigma_prior <- dunif(pars$sigma, min = 0.1, max = 50)
pars$prior <- pars$mu_prior * pars$sigma_prior

# Calculating the likelihood for each parameter combination
for(i in 1:nrow(pars)) {
  likelihoods <- dnorm(iq, pars$mu[i], pars$sigma[i])
  pars$likelihood[i] <- prod(likelihoods)
}
pars$probability <- pars$likelihood * pars$prior
pars$probability <- pars$probability / sum(pars$probability)

levelplot(probability ~ mu*sigma, data=pars)

mean is roughly around 42 with a sd of + or -20



The posterior distribution for our example

  • pars contains the data frame representing the posterior zombie IQ.
head(pars)
sample_indices <- sample( 1:nrow(pars), size = 10000,
    replace = TRUE, prob = pars$probability)
head(sample_indices)

# Sample from pars to calculate some new measures
pars_sample <- pars[sample_indices, c("mu", "sigma")]

# Visualize pars_sample
hist(pars_sample$mu)

# Calculate the 0.025, 0.5 and 0.975 quantiles of pars_sample$mu

quantile(pars_sample$mu, c(0.025, 0.5, .975))
We estimate the mean zombie IQ to be 42 (95% CI: [35, 50])

what range of zombie IQs should we expect? And how likely is it that the next zombie you encounter is, at least, moderately intelligent?

pred_iq <- rnorm(10000, mean = pars_sample$mu, 
                 sd = pars_sample$sigma)
# Visualize pred_iq
hist(pred_iq)

# Calculate the probability of a zombie being "smart" (+60 IQ)
pred_iq <- rnorm(10000, mean=pars_sample$mu, sd=pars_sample$sigma)

# the Pr that the next zombie you'll meet will have an IQ of >=60 
sum(pred_iq >= 60)/length(pred_iq) 
very unlikely that the next zombie we encounter will have an IQ of 60 or more.



BEST: package

  • assumption, data comes from a t-distribution and uses MCMC
  • 3 parameters, mean, mu, and degree of freedom (small df assumes more outliers)
fit <- BESTmcmc(iq)
fit

We get a close mean and sd from previous analysis.

  • the following plot looks similar to our previous histogram
plot(fit)



Comparing 2 data sets.

  • example: zombies that have a regular diet and those that have a brains based diet
iq_brains <- c(44, 52, 42, 66, 53, 42, 55, 57, 56, 51)
iq_regular <- c(55, 44, 34, 18, 51, 40, 40, 49, 48, 46)
# Calculate the mean difference in IQ between the two groups
mean(iq_brains) -  mean(iq_regular)

# Fit the BEST model to the data from both groups
best_posterior <- BESTmcmc(iq_brains, iq_regular)
best_posterior
our mean difference was 9.3, our posterior mean difference (51.780 - 43.102)= 8.678
plot(best_posterior)

Bayesian estimate using a t-distribution is robust to outliers.

  • suppose one of the regular diet zombies has a score of 175
iq_brains <- c(44, 52, 42, 66, 53, 42, 55, 57, 56, 51)
iq_regular <- c(55, 44, 34, 18, 51, 40, 40, 49, 48, 175)
# Calculate the mean difference in IQ between the two groups
mean(iq_brains) -  mean(iq_regular)

# Fit the BEST model to the data from both groups
best_posterior <- BESTmcmc(iq_brains, iq_regular)
best_posterior

t=There is more uncertainty in our estimate yet, we still conclude that brain eating zombies are more likely to have a higher IQ than regular diet zombies.

plot(best_posterior)
LS0tDQp0aXRsZTogIkZ1bmRhbWVudGFscyBvZiBCYXllc2lhbiBEYXRhIEFuYWx5c2lzIGluIFIiDQphdXRob3I6ICJLZXZpbiBMLiINCmRhdGU6ICJOb3ZlbWJlciAyMywgMjAxOCINCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFKQ0Kb3B0aW9ucyhzY2lwZW49OTk5KQ0KbGlicmFyeShsYXR0aWNlKQ0KbGlicmFyeShCRVNUKQ0KbGlicmFyeSh0aWR5dmVyc2UpDQpgYGANCg0KIyMjIENvdXJzZSBiYXllc2lhbiBtZXRob2RzIGRlZmluaXRpb246IEEgbWV0aG9kIG9mIGZpZ3VyaW5nIG91dCB1bm9ic2VydmFibGUgcXVhbnRpdGllcyBnaXZlbiBrbm93biBmYWN0cyB0aGF0IHVzZXMgcHJvYmFiaWxpdHkgdG8gZGVzY3JpYmUgdGhlIHVuY2VydGFpbnR5IG92ZXIgd2hhdCB0aGUgdmFsdWVzIG9mIHRoZSB1bmtub3duIHF1YW50aXRpZXMgY291bGQgYmUuDQoqNCBob3VycywgMjMgVmlkZW9zLCA1OCBFeGVyY2lzZXMNCg0KIyMjIyBTdHJlbmd0aHMgb2YgYmF5ZXNpYW4gbWV0aG9kczoNCiogTGVhcm5zIGZyb20gZGF0YQ0KKiBVc2VkIGZvciBoeXAuIHRlc3RpbmcgYW5kIGxpbmVhciByZWdyZXNzaW9uLg0KKiBGbGV4aWJsZSBlbm91Z2ggdG8gaGFuZGxlIHByb2JsZW0tc3BlY2lmaWMgbW9kZWxzLg0KICAgICsgY2FuIGluY2x1ZGUgaW5mb3JtYXRpb24gc291cmNlcyBpbiBhZGRpdGlvbiB0byB0aGUgZGF0YS4NCiAgICArIGNhbiBtYWtlIGNvbXBhcmlzb25zIGJldHdlZW4gZ3JvdXBzIG9yIGRhdGEgc2V0cy4NCiAgICArIGNhbiB1c2UgdGhlIHJlc3VsdCBvZiBhIGJheWVzaWFuIGFuYWx5c2lzIHRvIGRvIGRlY2lzaW9uIGFuYWx5c2lzDQogICAgKyBjYW4gY2hhbmdlIHRoZSB1bmRlcmx5aW5nIHN0YXRpc3RpY2FsIG1vZGVsLg0KDQoNCiMjIyMgUHJpb3IgPSBhIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiB0aGF0IHJlcHJlc2VudHMgd2hhdCB0aGUgbW9kZWwga25vd25zIGJlZm9yZSBzZWVpbmcgdGhlIGRhdGEuDQojIyMjIFBvc3RlcmlvciA9IGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIHRoYXQgcmVwcmVzZW50cyB3aGF0IHRoZSBtb2RlbCBrbm93biBhZnRlciBoYXZpbmcgc2VlbiB0aGUgZGF0YS4NCg0KIyMjIyBCYXllc2lhbiBJbmZlcmVuY2UgcmVxdWlyZXMgZGF0YSwgcHJpb3JzLCBhbmQgYSBnZW5lcmF0aXZlIG1vZGVsLg0KKiBhIGdlbmVyYXRpdmUgbW9kZWwgaXMgYSBtYXRoZW1hdGljYWwgZXhwcmVzc2lvbiB3aXRoIGEgc2V0IG9mIHJ1bGVzIHVzZWQgdG8gZmVlZCBwYXJhbWV0ZXIgdmFsdWVzIGFuZCBzaW11bGF0ZSBkYXRhLg0KDQo8YnI+DQo8YnI+DQoNCiMjIyBFeGFtcGxlOiBQcm9iYWJpbGl0eSB0aGF0IHdlIGhhdmUgZm91bmQgYSB2YWNjaW5lIHRoYXQgY3VyZXMgdGhlIHpvbWJpZSBvdXRicmVhay4NCiogdXNpbmcgdGhlIGJpbm9taWFsIHByb2Nlc3MgYXMgYSBnZW5lcmF0aXZlIG1vZGVsDQoNCmBgYHtyfQ0KIyBwYXJhbWV0ZXJzDQpwX3N1Y2Nlc3MgPC0gLjE1ICMgcHJvYmFiaWxpdHkgb2Ygc3VjY2Vzcw0Kbl96b21iaWVzIDwtIDEzICMgdHJhaWxzDQoNCiMgc2ltdWxhdGUgZGF0YQ0KZGF0YSA8LSBjKCkNCmZvcih6b21iaWUgaW4gMTpuX3pvbWJpZXMpew0KICAjIHNhdmUgaWYgcHJvcCBpcyBiZXR3ZWVuIDAgJiAxIGFuZCBncmVhdGVyIHRoYW4gb3VyIHByb2IuIG9mIHN1Y2Nlc3MNCiAgZGF0YVt6b21iaWVdIDwtIHJ1bmlmKDEsIG1pbj0wLCBtYXg9MSkgPCBwX3N1Y2Nlc3MgDQp9DQoNCmRhdGEgPC0gYXMubnVtZXJpYyhkYXRhKQ0KZGF0YQ0KbWVhbihkYXRhKSAjIG91ciBwb3N0ZXJpb3IgaXMgY2xvc2UgdG8gb3VyIHRoZW9yaXplZCBwcm9iYWJpbGl0eSBvZiBzdWNjZXNzIG9mIC4xNQ0Kc3VtKGRhdGEpICMgbnVtYmVyIG9mIHN1Y2Nlc3Nlcw0KYGBgDQoNCiMjIyMgYmlub21pYWwgZnVuY3Rpb24NCiogUGFyYW1ldGVycyAtIHByb2JhYmlsaXR5IGFuZCB0cmlhbCBzaXplLg0KDQpgYGB7cn0NCk49MTMNCg0KIyBwcm9iLiBvZiBzdWNjZXNzLCBjbG9zZSB0byBvdXIgcHJpb3IgYmVsaWVmDQpzdW0ocmJpbm9tKG49MSwgc2l6ZT1OLCBwcm9iPS4xNSkpIC8gTiANCmBgYA0KDQojIyMjIyBMb3RzIG9mIHNpbXVsYXRpb25zDQpgYGB7cn0NCnNldC5zZWVkKDkwOSkNCg0KIyBwcm9iLiBvZiBzdWNjZXNzLCBjbG9zZSB0byBvdXIgcHJpb3IgYmVsaWVmDQpzdW0ocmJpbm9tKG49MTAwMDAwLCBzaXplPTEwMCwgcHJvYj0uMTApKSAvICgxMDAwMDAqMTAwKSANCmhpc3QocmJpbm9tKG49MTAwMDAwLCBzaXplPTEwMCwgcHJvYj0uMTApKQ0KYGBgDQoNCjxicj4NCjxicj4NCg0KDQojIyMgQWRkaW5nIGFuIHVuaW5mb3JtZWQgcHJpb3IgZGlzdHJpYnV0aW9uLCBpbmNsdWRlcyBvdXQgdW5jZXJ0YWludHkgaW4gYSBiaW5vbWlhbCBkaXN0cmlidXRpb24uDQoqIEV4LiB3ZSB3YW50IHRvIGtub3cgaG93IG1hbnkgdGltZXMgb3VyIGFkZCB3aWxsIGJlIGNsaWNrZWQgb24sIGNsaWNrcz1zdWNjZXNzLCB3ZSBhcmUgbm90IHN1cmUgaWYgaXQgaXMgMTAlIG9mIHRoZSB0aW1lIHNvIHdlIHdpbGwgYXNzaWduIGEgcHJpb3IgdGhhdCBpcyBlcXVhbGx5IGxpa2VseSBhcyBsb3cgYXMgMCUgYW5kIGFzIGhpZ2ggYXMgMjAlDQpgYGB7cn0NCiMgbnVtYmVyIG9mIG9ic2VydmF0aW9ucw0Kbl9zYW1wbGVzIDwtIDEwMDAwMCANCg0KIyBudW1iZXIgb2YgdHJhaWxzDQpuX2Fkc19zaG93biA8LSAxMDAgDQoNCiAjIHByb2JhYmlsaXR5IG9mIHN1Y2Nlc3Mgd2l0aCBhIHVuaWZvcm0gcHJpb3IgcmVwcmVzZW50aW5nIG91ciB1bmNlcnRhaW50eQ0KcHJvcG9ydGlvbl9jbGlja3MgPC0gcnVuaWYobiA9IG5fc2FtcGxlcywgbWluID0gMC4wLCBtYXggPSAwLjIpDQoNCm5fdmlzaXRvcnMgPC0gcmJpbm9tKG4gPSBuX3NhbXBsZXMsIHNpemUgPSBuX2Fkc19zaG93biwgcHJvYiA9IHByb3BvcnRpb25fY2xpY2tzKQ0KDQojIHBvc3RlcmlvciBwcm9iYWJpbGl0eSwgY2xvc2UgdG8gb3VyIHByZXZpb3VzIHByb2IgY29uc3RyYWluZWQgYXQgLjEwDQpzdW0obl92aXNpdG9ycykgLyAoMTAwMDAwKjEwMCkgDQoNCiMgcHJvYmFiaWxpdHkgb2YgdmlzaXRvcnMsIG5vdCBhIHVuaWZvcm0gZGlzdCBsaWtlIHdoZW4gIHByb2JhYmlsaXR5IHdhcyBjb25zdHJhaW5lZCB0byAuMTANCmhpc3Qobl92aXNpdG9ycykgDQoNCiMgYSB1bmlmb3JtIGRpc3RyaWJ1dGlvbiBvZiBvdXIgdW5jZXJ0YWludHkNCmhpc3QocHJvcG9ydGlvbl9jbGlja3MpIA0KDQojIHByb2JhYmlsaXR5IG9mIDUgY2xpY2tzIG9yIG1vcmUNCnN1bShhcy5udW1lcmljKG5fdmlzaXRvcnMgPj0gNSkpIC8gbl9zYW1wbGVzIA0KYGBgDQoNCjxicj4NCjxicj4NCjxicj4NCjxicj4NCg0KIyMgVXBkYXRpbmcgb3VyIHByaW9yOg0KDQo8YnI+DQo8YnI+DQoNCiMjIyBCYXllc2lhbiBpbmZlcmVuY2UgPSBjb25kaXRpb25pbmcgb24gZGF0YSwgaW4gb3JkZXIgdG8gbGVhcm4gYWJvdXQgcGFyYW1ldGVyIHZhbHVlcy4NCiogV2hhdCB3b3VsZCBiZSB0aGUgdW5rbm93biBwYXJhbWV0ZXIgdmFsdWUgY29uZGl0aW9uYWwgb24gNyB2aXNpdG9ycz8gLjQ3DQoqIFdoYXQgd291bGQgYmUgdGhlIHVua25vd24gcGFyYW1ldGVyIHZhbHVlIGNvbmRpdGlvbmFsIG9uIDExIHZpc2l0b3JzPyAuODcNCmBgYHtyfQ0KcHJpb3IgPC0gZGF0YS5mcmFtZShuX3NhbXBsZXMsIG5fYWRzX3Nob3duLCBwcm9wb3J0aW9uX2NsaWNrcywgbl92aXNpdG9ycykNCmhlYWQocHJpb3IpDQpgYGANCg0KDQoNCg0KIyMjIyBOb3cgd2UgY29sbGVjdGVkIGRhdGEgb24gMTAwIG9ic2VydmF0aW9ucyBhbmQgMTMgY2xpY2tlZCBvdXIgYWRkLCB3ZSBjYW4gdXBkYXRlIG91ciBwcmlvciB0byBjYWxjdWxhdGUgdGhlIHByb2JhYmlsaXR5IG9mIGdldHRpbmcgNSBjbGlja3Mgb3IgbW9yZS4NCmBgYHtyfQ0KcG9zdGVyaW9yICA8LSBwcmlvcltwcmlvciRuX3Zpc2l0b3JzID09IDEzLCBdDQoNCiMgdXBkYXRlZCBwb3N0ZXJpb3INCmhlYWQocG9zdGVyaW9yKSANCg0KcHJpb3IgPC0gcG9zdGVyaW9yDQoNCmhlYWQocHJpb3IpDQoNCm5fc2FtcGxlcyA8LSAgbnJvdyhwcmlvcikNCg0Kbl9hZHNfc2hvd24gPC0gMTAwDQoNCnByaW9yJG5fdmlzaXRvcnMgPC0gcmJpbm9tKG49bl9zYW1wbGVzLCBzaXplID0gbl9hZHNfc2hvd24sIA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgcHJvYj1wcmlvciRwcm9wb3J0aW9uX2NsaWNrcykNCg0KaGlzdChwcmlvciRuX3Zpc2l0b3JzKQ0KDQojIG5ldyBwcm9iYWJpbGl0eSBvZiA1IGNsaWNrcyBvciBtb3JlIGFmdGVyIHVwZGF0aW5nIG91ciBiZWxpZWYgZnJvbSBvdXIgcG9zdGVyaW9yDQpzdW0ocHJpb3Ikbl92aXNpdG9ycyA+PSA1KSAvIGxlbmd0aChwcmlvciRuX3Zpc2l0b3JzKSAgDQpgYGANCg0KDQojIyMjIE5vdGUuIFRoaXMgYXBwcm9hY2ggd291bGQgc2NhbGUgYmFkIGlmIHdlIGhhZCBtb3JlIGRhdGEgb3IgY29tcGxleGl0eS4NCg0KPGJyPg0KPGJyPg0KDQojIyMgVXNpbmcgdGhlIGJldGEgZGlzdHJpYnV0aW9uIA0KKiBUYWtlcyAyIHBhcmFtZXRlcnMsIGFscGhhIGFuZCBiZXRhLg0KYGBge3J9DQpiZXRhX3NhbXBsZSA8LSByYmV0YShuID0gMTAwMDAwMCwgc2hhcGUxID0gMSwgc2hhcGUyID0gMSkNCmhpc3QoYmV0YV9zYW1wbGUpDQpoZWFkKGJldGFfc2FtcGxlKQ0KDQpiZXRhX3NhbXBsZSA8LSByYmV0YShuID0gMTAwMDAwMCwgc2hhcGUxID0gMTAsIHNoYXBlMiA9IDEwKQ0KaGlzdChiZXRhX3NhbXBsZSkNCg0KIyBjaGFuZ2luZyB0aGUgc2hhcGUgb2YgdGhlIGJldGEgZGlzdHJpYnV0aW9uDQpgYGANCg0KDQoNCg0KDQoNCiMjIyMgaW4gb3VyIGFkZCBleGFtcGxlIGlmIG1vc3QgYWRkcyBnZXQgY2xpY2tlZCA1JSBvZiB0aGUgdGltZSwgYnV0IHNvbWUgYWRkcyBnZXQgY2xpY2tlZCBhcyBsb3cgYXMgMiUgYW5kIGFzIGhpZ2ggYXMgOCUsIHdoYXQgYmV0YSBwYXJhbWV0ZXJzIHdvdWxkIGJlc3QgY2FwdHVyZSB0aGlzIHByaW9yIGRpc3RyaWJ1dGlvbj8NCg0KYGBge3J9DQpoaXN0KHJiZXRhKG49MTAwLCBzaGFwZTEgPSA1LCBzaGFwZTIgPSA5NSkpDQpgYGANCg0KDQoNCiMjIyMgTmV3IHR3ZWFrIHRvIG91ciBwcmV2aW91cyBtb2RlbCwgYWRkaW5nIGFuIGluZm9ybWVkIHByaW9yIGFuZCBkYXRhIHRvIGluZm9ybSB0aGUgbmV3IHBvc3Rlcmlvcg0KYGBge3J9DQpuX2RyYXdzIDwtIDEwMDAwMA0Kbl9hZHNfc2hvd24gPC0gMTAwDQoNCiMgQ2hhbmdlIHRoZSBwcmlvciBvbiBwcm9wb3J0aW9uX2NsaWNrcw0KcHJvcG9ydGlvbl9jbGlja3MgPC0gcmJldGEobl9kcmF3cywgc2hhcGUxID0gNSwgc2hhcGUyID0gOTUpICMgTkVXIENIQU5HRQ0Kbl92aXNpdG9ycyA8LSByYmlub20obl9kcmF3cywgc2l6ZSA9IG5fYWRzX3Nob3duLCBwcm9iID0gcHJvcG9ydGlvbl9jbGlja3MpDQpwcmlvciA8LSBkYXRhLmZyYW1lKHByb3BvcnRpb25fY2xpY2tzLCBuX3Zpc2l0b3JzKQ0KcG9zdGVyaW9yIDwtIHByaW9yW3ByaW9yJG5fdmlzaXRvcnMgPT0gMTMsIF0NCg0KIyBUaGlzIHBsb3RzIHRoZSBwcmlvciBhbmQgdGhlIHBvc3RlcmlvciBpbiB0aGUgc2FtZSBwbG90DQpwYXIobWZjb2wgPSBjKDIsIDEpKQ0KaGlzdChwcmlvciRwcm9wb3J0aW9uX2NsaWNrcywgeGxpbSA9IGMoMCwgMC4yNSkpDQpoaXN0KHBvc3RlcmlvciRwcm9wb3J0aW9uX2NsaWNrcywgeGxpbSA9IGMoMCwgMC4yNSkpDQpgYGANCg0KDQo8YnI+DQo8YnI+DQoNCiMjIyBDb21wYXJpbmcgYmV0d2VlbiBncm91cHMgb3IgZGF0YXNldHM7IGV4YW1wbGUgdmlkZW8gKDEzIG91dCBvZiAxMDAgY2xpY2tlZCkgdnMgdGV4dCAoNiBvdXQgb2YgMTAwIGNsaWNrZWQpIGFkcw0KYGBge3J9DQpuX2RyYXdzIDwtIDEwMDAwMA0Kbl9hZHNfc2hvd24gPC0gMTAwDQpwcm9wb3J0aW9uX2NsaWNrcyA8LSBydW5pZihuX2RyYXdzLCBtaW4gPSAwLjAsIG1heCA9IDAuMikNCm5fdmlzaXRvcnMgPC0gcmJpbm9tKG4gPSBuX2RyYXdzLCBzaXplID0gbl9hZHNfc2hvd24sIA0KICAgICAgICAgICAgICAgICAgICAgcHJvYiA9IHByb3BvcnRpb25fY2xpY2tzKQ0KcHJpb3IgPC0gZGF0YS5mcmFtZShwcm9wb3J0aW9uX2NsaWNrcywgbl92aXNpdG9ycykNCg0KIyBDcmVhdGUgdGhlIHBvc3RlcmlvcnMgZm9yIHZpZGVvIGFuZCB0ZXh0IGFkcw0KcG9zdGVyaW9yX3ZpZGVvIDwtIHByaW9yW3ByaW9yJG5fdmlzaXRvcnMgPT0gMTMsIF0gIyAxMyBvZiAxMDAgY2xpY2tlZA0KcG9zdGVyaW9yX3RleHQgPC0gcHJpb3JbcHJpb3Ikbl92aXNpdG9ycyA9PSA2LCBdICMgNiBvZiAxMDAgY2xpY2tlZA0KDQoNCiMgVmlzdWFsaXplIHRoZSBwb3N0ZXJpb3JzDQpoaXN0KHBvc3Rlcmlvcl92aWRlbyRwcm9wb3J0aW9uX2NsaWNrcywgeGxpbSA9IGMoMCwgMC4yNSkpDQoNCmhpc3QocG9zdGVyaW9yX3RleHQkcHJvcG9ydGlvbl9jbGlja3MsIHhsaW0gPSBjKDAsIDAuMjUpKQ0KYGBgDQoNCg0KDQojIyMjIENvbXBhcmUgZGlmZmVyZW5jZSBpbiBwb3N0ZXJpb3IgcHJvcG9ydGlvbnMgYmV0d2VlbiB2aWRlbyBhbmQgdGV4dCBhZHMNCg0KYGBge3J9DQpwb3N0ZXJpb3IgPC0gZGF0YS5mcmFtZSgNCiAgICB2aWRlb19wcm9wID0gcG9zdGVyaW9yX3ZpZGVvJHByb3BvcnRpb25fY2xpY2tzWzE6NDAwMF0sDQogICAgdGV4dF9wcm9wICA9IHBvc3Rlcmlvcl90ZXh0JHByb3BvcnRpb25fY2xpY2tbMTo0MDAwXSkNCiAgICANCiMgQ2FsY3VsYXRlIHRoZSBwb3N0ZXJpb3IgZGlmZmVyZW5jZTogdmlkZW9fcHJvcCAtIHRleHRfcHJvcA0KcG9zdGVyaW9yJHByb3BfZGlmZiA8LSBwb3N0ZXJpb3IkdmlkZW9fcHJvcCAtIHBvc3RlcmlvciR0ZXh0X3Byb3ANCg0KIyBWaXN1YWxpemUgcHJvcF9kaWZmDQpoaXN0KHBvc3RlcmlvciRwcm9wX2RpZmYpDQoNCiMgU3VtbWFyaXplIHByb3BfZGlmZg0Kc3VtbWFyeShwb3N0ZXJpb3IkcHJvcF9kaWZmKQ0KYGBgDQoNCiMjIyMjIyBNb3N0IGxpa2VseSBkaWZmZXJlbmNlLCBhbmQgcHJvYmFiaWxpdHkgdGhhdCB0aGUgcHJvcG9ydGlvbiBvZiBjbGlja3MgdXMgbGFyZ2VyIGZvciB0aGUgdmlkZW8gdGhhbiB0ZXh0IGFkLg0KYGBge3J9DQptZWRpYW4ocG9zdGVyaW9yJHByb3BfZGlmZikNCnN1bShwb3N0ZXJpb3IkcHJvcF9kaWZmID4gMCkvbGVuZ3RoKHBvc3RlcmlvciRwcm9wX2RpZmYpIA0KYGBgDQoNCiMjIyMjIyBOb3RlLiB0aGUgcG9zdGVyaW9yIG1lYW4gb3IgbWVkaWFuIGlzIHRoZSBzdW1tYXJ5IGRpc3RyaWJ1dGlvbiBvdmVyIHNvbWUgcGFyYW1ldGVyLCB3aGlsZSB0aGUgbWVhbiBvciBtZWRpYW4gb2YgYSBkYXRhIGlzIGEgc3VtbWFyeSBvZiB0aGUgZGF0YS4NCg0KPGJyPg0KPGJyPg0KDQojIyMgQ3JlZGlibGUgaW50ZXJ2YWwsIGNvbnRhaW5zIHRoZSB1bmRlcmx5aW5nIHBhcmFtZXRlciB3aXRoIGEgY2VydGFpbiBwcm9iYWJpbGl0eS4gDQoNCjxicj4NCjxicj4NCg0KDQojIyMgRGVjaXNpb24gYW5hbHlzaXM6IHRha2luZyBhIHJlc3VsdCBvZiBhIHN0YXRpc3RpY2FsIGFuYWx5c2lzIGFuZCBwb3N0IHByb2Nlc3MgdG8gbWFrZSBhbiBpbmZvcm1lZCBkZWNpc2lvbiAoaS5lLiwgc2F2ZSBsaXZlcywgbWFrZSBtb3JlIG1vbmV5KS4gDQoqIGV4YW1wbGU6IHZpZGVvIGFkcyBjb3N0IDI1IGNlbnRzLCB0ZXh0IDUgY2VudHMsIGFuZCB3ZSBtYWtlIG9uIGF2ZXJhZ2UgJDIuNTMgcGVyIHZpc2l0b3IuDQoNCmBgYHtyfQ0KdmlkZW9fY29zdCA8LSAuMjUNCnRleHRfY29zdCA8LSAuMDUNCnZpc2l0b3Jfc3BlbmQgPC0gMi41Mw0KDQojIFAocGVvcGxlICB0aGF0IGNsaWNrIHRoZSB2aWRlbyBhZCAqIGhvdyBtdWNoIHdlIG1hZGUgb24gdmlzaXRvcnMgLSBjb3N0KQ0KcG9zdGVyaW9yJHZpZGVvX3Byb2ZpdCA8LSBwb3N0ZXJpb3IkdmlkZW9fcHJvcCAqIHZpc2l0b3Jfc3BlbmQgLSB2aWRlb19jb3N0IA0KDQojIFAocGVvcGxlIHRoYXQgY2xpY2sgdGhlIHRleHQgYWQgKiBob3cgbXVjaCB3ZSBtYWRlIG9uIHZpc2l0b3JzIC0gY29zdCkNCnBvc3RlcmlvciR0ZXh0X3Byb2ZpdCA8LSBwb3N0ZXJpb3IkdGV4dF9wcm9wICogdmlzaXRvcl9zcGVuZCAtIHRleHRfY29zdCANCg0KIyBkaWZmZXJlbmNlIGluIHByb2ZpdHMgdGhpcyBpcyB0aGUgZGlzdHJpYnV0aW9uIHdlIGNhcmUgYWJvdXQNCnBvc3RlcmlvciRwcm9maXRfZGlmZiA8LSBwb3N0ZXJpb3IkdmlkZW9fcHJvZml0IC0gcG9zdGVyaW9yJHRleHRfcHJvZml0IA0KaGVhZChwb3N0ZXJpb3IpDQpoaXN0KHBvc3RlcmlvciRwcm9maXRfZGlmZikNCg0KIyBDYWxjdWxhdGUgYSAiYmVzdCBndWVzcyIgZm9yIHRoZSBkaWZmZXJlbmNlIGluIHByb2ZpdHMNCm1lZGlhbihwb3N0ZXJpb3IkcHJvZml0X2RpZmYpDQoNCiMgQ2FsY3VsYXRlIHRoZSBwcm9iYWJpbGl0eSB0aGF0IHRleHQgYWRzIGFyZSBiZXR0ZXIgdGhhbiB2aWRlbyBhZHMNCnN1bShwb3N0ZXJpb3IkcHJvZml0X2RpZmYgPCAwKSAvIGxlbmd0aChwb3N0ZXJpb3IkcHJvZml0X2RpZmYpDQpgYGANCg0KIyMjIyMgSW4gbG9va2luZyBhdCB0aGUgaGlzdG9ncmFtIHRoZXJlIGlzIG5vIHJlYWwgZGlmZmVyZW5jZSBpbiBwcm9maXRzIG92ZXIgbG9zdCB5ZXQgdGV4dCBhZHMgYXJlIG1hcmdpbmFsbHkgY2hlYXBlciB0byBydW4uDQoNCjxicj4NCjxicj4NCg0KIyMjIENoYW5naW5nIHRoZSB1bmRlcmx5aW5nIHN0YXRpc3RpY2FsIG1vZGVsDQoqIGJpbm9taWFsIHdpbGwgbm90IHdvcmsgaGVyZS4NCiogaW5zdGVhZCwgd2UgdXNlIHRoZSBwb2lzc29uIGRpc3RyaWJ1dGlvbiBtb2RlbGluZyB0aGUgbnVtYmVyIG9mIGNsaWNrcyBwZXIgZGF5Lg0KKiBFeHBsb3JlIHRoZSBwb2lzc29uIGRpc3RyaWJ1dGlvbi4gRXhhbXBsZTogb24gYSBjbG91ZHkgZGF5IHdoYXQgaXMgdGhlIHByb2JhYmlsaXR5IG9mIGJyZWFraW5nIGV2ZW4gaWYgd2Ugc2VsbCBvbiBhdmVyYWdlIDExLjUgaWNlIGNyZWFtcz8NCg0KYGBge3J9DQppY2VfY3JlYW0gPC0gcnBvaXMobj0xMDAwMCwgbGFtYmRhID0gMTEuNSkgIyBsYW1iZGEgaXMgb3VyIGF2ZXJhZ2UgY291bnQNCmhpc3QoaWNlX2NyZWFtKQ0Kc3VtKGljZV9jcmVhbSA+PSAxNSkvIGxlbmd0aChpY2VfY3JlYW0pDQpgYGANCg0KIyMjIyMgdW5saWtlbHkgdGhhdCB3ZSB3aWxsIGJyZWFrIGV2ZW4uDQoNCg0KIyMjIyBBcHBseWluZyBpdCB0byBvdXIgYWQgcHJvYmxlbS4NCiogV2Ugbm93IGdldCBjaGFyZ2VkIGJ5IHRoZSBkYXksIHJhdGhlciB0aGFuIGJ5IGFkLCB0byBydW4gYW4gYWQuIE91ciBjbGlja3MgYXJlIG5vdyBwZXIgZGF5IGluc3RlYWQgb2YgcGVyIGFkLg0KKiBuZXcgZGF5IHNob3dzIHRoYXQgaW4gMSBkYXkgd2UgcmVjZWl2ZWQgMTkgY2xpY2tzLg0KKiBob3cgbWFueSBkYWlseSBjbGlja3Mgc2hvdWxkIHdlIGV4cGVjdCBvbiBhdmVyYWdlPw0KYGBge3J9DQpuX2RyYXdzIDwtIDEwMDAwMA0Kbl9hZHNfc2hvd24gPC0gMTAwDQoNCiMgZmxhdCBwcmlvciBmcm9tIDAgdG8gODAgY2xpY2tzIHBlciBkYXkNCm1lYW5fY2xpY2tzIDwtIHJ1bmlmKG5fZHJhd3MsIG1pbiA9IDAsIG1heCA9IDgwKSANCg0KIyAyIHBhcmFtZXRlcnMgc2l6ZSBhbmQgbWVhbg0Kbl92aXNpdG9ycyA8LSBycG9pcyhuX2RyYXdzLCBsYW1iZGEgPSBtZWFuX2NsaWNrcykgDQogICAgICAgICAgICAgICAgICAgICANCiMgcHJvYmFiaWxpdHkgb2YgZ2V0dGluZyAxOSBjbGlja3MNCnBvc3RlcmlvciA8LSBwcmlvcltwcmlvciRuX3Zpc2l0b3JzID09IDE5LCBdIA0KDQpzdW1tYXJ5KHBvc3RlcmlvciRtZWFuX2NsaWNrcykNCg0KcXVhbnRpbGUocG9zdGVyaW9yJG1lYW5fY2xpY2tzLCBwcm9iPWMoLjA1LCAuOTUpKQ0KYGBgDQoNCjxicj4NCjxicj4NCg0KIyMjIFByb2JhYmlsaXR5IHJ1bGVzDQoNCiogQW55IG51bWJlciBiZXR3ZWVuIDAgYW5kIDENCiogQSBzdGF0ZW1lbnQgKHVuKWNlcnRhaW50eQ0KIyMjIyMgUHJvYmFiaWxpdHkgb2YgZHJhd2luZyBvbmUgb2YgdGhlIGZvdXIgYWNlcyBpbiBhIHN0YWNrIG9mIDUyIGNhcmRzDQpgYGB7cn0NCnByb2JfdG9fZHJhd19hY2VzIDwtIDQvNTINCnByb2JfdG9fZHJhd19hY2VzDQpgYGANCg0KIyMjIyMgUHJvYmFiaWxpdHkgb2YgZHJhd2luZyBhbGwgZm91ciBhY2VzIGluIGEgcm93DQpgYGB7cn0NCnByb2JfdG9fZHJhd19mb3VyX2FjZXMgPC0gKDQvNTIpICogKDMvNTEpICogKDIvNTApICogKDEvNDkpDQpwcm9iX3RvX2RyYXdfZm91cl9hY2VzDQpgYGANCg0KDQojIyMjIENhbGN1bGF0aW5nIHByb2JhYmlsaXRpZXMgd2l0aCBmdW5jdGlvbnMgcmF0aGVyIHRoYW4gc2ltdWxhdGluZyBkYXRhLCBjb25kaXRpb25pbmcgb24gMTAlDQoqIGNvbmRpdGlvbmFsIHByb2JhYmlsaXR5IG9mIGdldHRpbmcgMTMgY2xpY2tzIG9uIG91ciBhZGRzIGdpdmVuIHRoYXQgdGhlIHN1Y2Nlc3MgcmF0ZSBpcyAxMCUNCmBgYHtyfQ0Kbl92aXNpdG9ycyA8LSByYmlub20obiA9IDEwMDAwMCwgc2l6ZSA9IDEwMCwgcHJvYiA9IDAuMSkNCnN1bShuX3Zpc2l0b3JzID09IDEzKSAvIGxlbmd0aChuX3Zpc2l0b3JzKQ0KDQojIG9yIA0KZGJpbm9tKDEzLCAxMDAsIC4xMCkNCmBgYA0KDQojIyMjIyBwcm9iYWJpbGl0eSBvZiBnZXR0aW5nIG1vcmUgdGhhbiAxMyBjbGlja3MNCmBgYHtyfQ0Kbl92aXNpdG9ycyA8LSByYmlub20obiA9IDEwMDAwMCwgc2l6ZSA9IDEwMCwgcHJvYiA9IDAuMSkNCnN1bShuX3Zpc2l0b3JzID4gMTMpIC8gbGVuZ3RoKG5fdmlzaXRvcnMpDQoNCiMgb3IgDQpwYmlub20oMTMsIDEwMCwgLjEwLCBsb3dlci50YWlsPUZBTFNFKQ0KYGBgDQoNCjxicj4NCjxicj4NCg0KIyMjIENvbmRpdGlvbmluZyBvbiB0aGUgZGF0YQ0KYGBge3J9DQpuX2Fkc19zaG93biA8LSAxMDANCm5fdmlzaXRvcnMgPC0gc2VxKDAsIDEwMCwgYnk9MSkNCnByb3BvcnRpb25fY2xpY2tzIDwtIHNlcSgwLCAxLCBieT0uMDEpDQoNCnBhcnMgPC0gZXhwYW5kLmdyaWQocHJvcG9ydGlvbl9jbGlja3M9cHJvcG9ydGlvbl9jbGlja3MsIA0KICAgICAgICAgICAgICAgICAgICBuX3Zpc2l0b3JzPW5fdmlzaXRvcnMpDQoNCnBhcnMkcHJpb3IgPC0gZHVuaWYocGFycyRwcm9wb3J0aW9uX2NsaWNrcywgbWluPTAsIG1heD0uMikNCg0KcGFycyRsaWtlbGlob29kIDwtIGRiaW5vbShwYXJzJG5fdmlzaXRvcnMsIHNpemU9bl9hZHNfc2hvd24sIA0KICAgICAgICAgICAgICAgICAgICAgICAgICBwcm9iPXBhcnMkcHJvcG9ydGlvbl9jbGlja3MpDQoNCnBhcnMkcHJvYmFiaWxpdHkgPC0gcGFycyRsaWtlbGlob29kICogcGFycyRwcmlvcg0KDQpwYXJzJHByb2JhYmlsaXR5IDwtIHBhcnMkcHJvYmFiaWxpdHkgLyBzdW0ocGFycyRwcm9iYWJpbGl0eSkNCnN1bShwYXJzJHByb2JhYmlsaXR5KQ0KaGVhZChwYXJzKQ0KDQojIGNvbmRpdGlvbmluZyBvbiBkYXRhIHdoZW4gdmlzaXRvcnMgZXF1YWwgNg0KcGFycyA8LSBwYXJzW3BhcnMkbl92aXNpdG9ycyA9PSA2LF0NCg0KIyBub3JtYWxpemUgYWdhaW4NCnBhcnMkcHJvYmFiaWxpdHkgPC0gcGFycyRwcm9iYWJpbGl0eSAvIHN1bShwYXJzJHByb2JhYmlsaXR5KQ0KDQoNCiMgUGxvdCB0aGUgcG9zdGVyaW9yIHBhcnMkcHJvYmFiaWxpdHkNCnBsb3QocGFycyRwcm9wb3J0aW9uX2NsaWNrcywgeT1wYXJzJHByb2JhYmlsaXR5LCB0eXBlPSJoIikNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCiMjIyBCYXllcyB0aGVvcmVtOg0KDQoNCg0KJCQNClx1bmRlcmJyYWNle3AoXHRoZXRhfEQpfV97cG9zdGVyaW9yfSAgfj1+IFxmcmFje1xvdmVyYnJhY2V7cChEfFx0aGV0YSl9XntsaWtlbGlob29kfX4gXG92ZXJicmFjZXtwKFx0aGV0YSl9Xntwcmlvcn19IHtcdW5kZXJicmFjZXtwKEQpfV97ZXZpZGVuY2V9fQ0KJCQNCg0KDQo8YnI+DQo8YnI+DQoNCiMjIyBUaGUgcHJvYmFiaWxpdHkgb2YgZGlmZmVyZW50IHBhcmFtZXRlcnMgJFx0aGV0YSQgZ2l2ZW4gc29tZSBkYXRhICREJCAkPSQgVGhlIGxpa2VsaWhvb2Q6IHRoZSByZWxhdGl2ZSBwcm9iYWJpbGl0eSBvZiB0aGUgZGF0YSBnaXZlbiBkaWZmZXJlbnQgcGFyYW1ldGVyIHZhbHVlcyAkUChEfFx0aGV0YSkpJCAkXHRpbWVzJCBUaGUgcHJpb3I6IHRoZSBwcm9iYWJpbGl0eSBvZiBkaWZmZXJlbnQgcGFyYW1ldGVycyBiZWZvcmUgc2VlaW5nIHRoZSBkYXRhICRQKFx0aGV0YSkkICRcZGl2JCBUaGUgdG90YWwgc3VtIG9mIHRoZSBsaWtlbGlob29kIHdlaWdodGVkIGJ5IHRoZSBwcmlvciAkXHN1bXtQKER8XHRoZXRhKVx0aW1lcyBQKFx0aGV0YSl9JCAgICANCg0KPGJyPg0KPGJyPg0KDQojIyMgTWF0aGVtYXRpY2FsIG5vdGF0aW9uIGZvciBvdXIgbW9kZWwsIGNvbnZlbmllbnQgd2F5IHRvIGRlZmluZSBtb2RlbC4NCg0KJCQNClxldGFfe2Fkc30gPSAxMDANCiQkDQoNCiQkDQpQX3tjbGlja3N9IFxzaW0gVW5pZm9ybSgwLjAsMC4yKQ0KJCQNCg0KJCQNClxldGFfe3Zpc2l0b3JzfSBcc2ltIEJpbm9taWFsKFxldGFfe2Fkc30sIHBfe2NsaWNrc30pDQokJA0KDQojIyMjIGZvciB0aGUgcG9pc3NvbiBtb2RlbA0KDQokJA0KXG11X3tjbGlja3N9IFxzaW0gVW5pZm9ybShtaW46MCwgbWF4OjgwKQ0KJCQNCg0KJCQNCm5fe3Zpc2l0b3JzfSBcc2ltIFBvaXNzb24oXG11X3tjbGlja3N9KQ0KJCQNCg0KPGJyPg0KPGJyPg0KPGJyPg0KPGJyPg0KDQoNCiMjIHdvcmtpbmcgd2l0aCB0aGUgbm9ybWFsIGRpc3RyaWJ1dGlvbg0KKiAyIHBhcmFtZXRlcnMgJFxtdSQgYW5kICRcc2lnbWEkDQpgYGB7cn0NCiMgbWVhbiBvZiAyMCwgc2Qgb2YgMg0Kcm5vcm0obj01LCBtZWFuPTIwLCBzZD0yKSANCg0KIyB0ZW1wZXJhdHVyZSByZWFkaW5ncyBmcm9tIGEgbGFrZQ0KdGVtcCA8LSBjKDE5LCAyMywgMjAsIDE3LCAyMykgDQoNCiMgcmVsYXRpdmUgbGlrZWxpaG9vZCBvZiBvdXIgZGF0YSBwb2ludHMgKG5vdCBwcm9iYWJpbGl0aWVzKQ0KbGlrZWxpaG9vZCA8LSBkbm9ybSh4PSB0ZW1wLCBtZWFuPTIwICwgc2Q9MikgDQpsaWtlbGlob29kDQoNCiMgbXVsdGlwbHkgYWxsIG51bWJlcnMgdG9nZXRoZXIgKHNtYWxsIG51bWJlcikNCnByb2QobGlrZWxpaG9vZCkgDQoNCiMgd29ya2luZyBvbiB0aGUgbG9nIHNjYWxlIHRvIGF2b2lkIHBvb3Igc2NhYmlsaXR5IG9mIGRhdGENCmxvZyhsaWtlbGlob29kKQ0KYGBgDQoNCjxicj4NCjxicj4NCg0KIyMjIGV4YW1wbGU6IGhvdyBzbWFydCBhcmUgem9tYmllcz8gRGF0YSBhcmUgZnJvbSBJUXMgb2Ygem9tYmllcy4gDQoqIFdoYXQgd2UncmUgaW50ZXJlc3RlZCBpbiBpcyBob3cgbXVjaCB3ZSBjYW4gbGVhcm4gYWJvdXQgdGhlIG1lYW4gem9tYmllIElRIGZyb20gdGhpcyBkYXRhLiANCg0KJCQNClxtdSBcc2ltIE5vcm1hbChtZWFuOjEwMCwgc2Q6MTAwKQ0KJCQNCg0KJCQNClxzaWdtYSBcc2ltIFVuaWZvcm0obWluOjAsIG1heDo1MCkNCiQkDQoNCiQkDQpJUV9pIFxzaW0gTm9ybWFsKFxtdSwgXHNpZ21hKQ0KJCQNCg0KJCQNCmlxID0gNTUsIDQ0LCAzNCwgMTgsIDUxLCA0MCwgNDAsIDQ5LCA0OCwgNDYNCiQkDQoNCjxicj4NCjxicj4NCg0KIyMjIGZpdCB0aGUgbW9kZWwNCmBgYHtyfQ0KIyBUaGUgSVEgb2YgYSBidW5jaCBvZiB6b21iaWVzDQppcSA8LSBjKDU1LCA0NCwgMzQsIDE4LCA1MSwgNDAsIDQwLCA0OSwgNDgsIDQ2KQ0KDQojIERlZmluaW5nIHRoZSBwYXJhbWV0ZXIgZ3JpZA0KcGFycyA8LSBleHBhbmQuZ3JpZChtdSA9IHNlcSgwLCAxNTAsIGxlbmd0aC5vdXQgPSAxMDApLCANCiAgICAgICAgICAgICAgICAgICAgc2lnbWEgPSBzZXEoMC4xLCA1MCwgbGVuZ3RoLm91dCA9IDEwMCkpDQoNCiMgRGVmaW5pbmcgYW5kIGNhbGN1bGF0aW5nIHRoZSBwcmlvciBkZW5zaXR5IGZvciBlYWNoIHBhcmFtZXRlciBjb21iaW5hdGlvbg0KcGFycyRtdV9wcmlvciA8LSBkbm9ybShwYXJzJG11LCBtZWFuID0gMTAwLCBzZCA9IDEwMCkNCnBhcnMkc2lnbWFfcHJpb3IgPC0gZHVuaWYocGFycyRzaWdtYSwgbWluID0gMC4xLCBtYXggPSA1MCkNCnBhcnMkcHJpb3IgPC0gcGFycyRtdV9wcmlvciAqIHBhcnMkc2lnbWFfcHJpb3INCg0KIyBDYWxjdWxhdGluZyB0aGUgbGlrZWxpaG9vZCBmb3IgZWFjaCBwYXJhbWV0ZXIgY29tYmluYXRpb24NCmZvcihpIGluIDE6bnJvdyhwYXJzKSkgew0KICBsaWtlbGlob29kcyA8LSBkbm9ybShpcSwgcGFycyRtdVtpXSwgcGFycyRzaWdtYVtpXSkNCiAgcGFycyRsaWtlbGlob29kW2ldIDwtIHByb2QobGlrZWxpaG9vZHMpDQp9DQpwYXJzJHByb2JhYmlsaXR5IDwtIHBhcnMkbGlrZWxpaG9vZCAqIHBhcnMkcHJpb3INCnBhcnMkcHJvYmFiaWxpdHkgPC0gcGFycyRwcm9iYWJpbGl0eSAvIHN1bShwYXJzJHByb2JhYmlsaXR5KQ0KDQpsZXZlbHBsb3QocHJvYmFiaWxpdHkgfiBtdSpzaWdtYSwgZGF0YT1wYXJzKQ0KYGBgDQoNCg0KIyMjIyBtZWFuIGlzIHJvdWdobHkgYXJvdW5kIDQyIHdpdGggYSBzZCBvZiArIG9yIC0yMA0KDQo8YnI+DQo8YnI+DQoNCiMjIyBUaGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbiBmb3Igb3VyIGV4YW1wbGUNCiogcGFycyBjb250YWlucyB0aGUgZGF0YSBmcmFtZSByZXByZXNlbnRpbmcgdGhlIHBvc3RlcmlvciB6b21iaWUgSVEuDQpgYGB7cn0NCmhlYWQocGFycykNCnNhbXBsZV9pbmRpY2VzIDwtIHNhbXBsZSggMTpucm93KHBhcnMpLCBzaXplID0gMTAwMDAsDQogICAgcmVwbGFjZSA9IFRSVUUsIHByb2IgPSBwYXJzJHByb2JhYmlsaXR5KQ0KaGVhZChzYW1wbGVfaW5kaWNlcykNCg0KIyBTYW1wbGUgZnJvbSBwYXJzIHRvIGNhbGN1bGF0ZSBzb21lIG5ldyBtZWFzdXJlcw0KcGFyc19zYW1wbGUgPC0gcGFyc1tzYW1wbGVfaW5kaWNlcywgYygibXUiLCAic2lnbWEiKV0NCg0KIyBWaXN1YWxpemUgcGFyc19zYW1wbGUNCmhpc3QocGFyc19zYW1wbGUkbXUpDQoNCiMgQ2FsY3VsYXRlIHRoZSAwLjAyNSwgMC41IGFuZCAwLjk3NSBxdWFudGlsZXMgb2YgcGFyc19zYW1wbGUkbXUNCg0KcXVhbnRpbGUocGFyc19zYW1wbGUkbXUsIGMoMC4wMjUsIDAuNSwgLjk3NSkpDQpgYGANCg0KIyMjIyMgV2UgZXN0aW1hdGUgdGhlIG1lYW4gem9tYmllIElRIHRvIGJlIDQyICg5NSUgQ0k6IFszNSwgNTBdKSANCg0KIyMjIyB3aGF0IHJhbmdlIG9mIHpvbWJpZSBJUXMgc2hvdWxkIHdlIGV4cGVjdD8gQW5kIGhvdyBsaWtlbHkgaXMgaXQgdGhhdCB0aGUgbmV4dCB6b21iaWUgeW91IGVuY291bnRlciBpcywgYXQgbGVhc3QsIG1vZGVyYXRlbHkgaW50ZWxsaWdlbnQ/DQpgYGB7cn0NCnByZWRfaXEgPC0gcm5vcm0oMTAwMDAsIG1lYW4gPSBwYXJzX3NhbXBsZSRtdSwgDQogICAgICAgICAgICAgICAgIHNkID0gcGFyc19zYW1wbGUkc2lnbWEpDQojIFZpc3VhbGl6ZSBwcmVkX2lxDQpoaXN0KHByZWRfaXEpDQoNCiMgQ2FsY3VsYXRlIHRoZSBwcm9iYWJpbGl0eSBvZiBhIHpvbWJpZSBiZWluZyAic21hcnQiICgrNjAgSVEpDQpwcmVkX2lxIDwtIHJub3JtKDEwMDAwLCBtZWFuPXBhcnNfc2FtcGxlJG11LCBzZD1wYXJzX3NhbXBsZSRzaWdtYSkNCg0KIyB0aGUgUHIgdGhhdCB0aGUgbmV4dCB6b21iaWUgeW91J2xsIG1lZXQgd2lsbCBoYXZlIGFuIElRIG9mID49NjAgDQpzdW0ocHJlZF9pcSA+PSA2MCkvbGVuZ3RoKHByZWRfaXEpIA0KYGBgDQoNCiMjIyMjIHZlcnkgdW5saWtlbHkgdGhhdCB0aGUgbmV4dCB6b21iaWUgd2UgZW5jb3VudGVyIHdpbGwgaGF2ZSBhbiBJUSBvZiA2MCBvciBtb3JlLg0KDQo8YnI+DQo8YnI+DQoNCiMjIyBCRVNUOiBwYWNrYWdlDQoqIGFzc3VtcHRpb24sIGRhdGEgY29tZXMgZnJvbSBhIHQtZGlzdHJpYnV0aW9uIGFuZCB1c2VzIE1DTUMNCiogMyBwYXJhbWV0ZXJzLCBtZWFuLCBtdSwgYW5kIGRlZ3JlZSBvZiBmcmVlZG9tIChzbWFsbCBkZiBhc3N1bWVzIG1vcmUgb3V0bGllcnMpDQpgYGB7cn0NCmZpdCA8LSBCRVNUbWNtYyhpcSkNCmZpdA0KYGBgDQoNCiMjIyMgV2UgZ2V0IGEgY2xvc2UgbWVhbiBhbmQgc2QgZnJvbSBwcmV2aW91cyBhbmFseXNpcy4NCiogdGhlIGZvbGxvd2luZyBwbG90IGxvb2tzIHNpbWlsYXIgdG8gb3VyIHByZXZpb3VzIGhpc3RvZ3JhbQ0KYGBge3J9DQpwbG90KGZpdCkNCmBgYA0KDQo8YnI+DQo8YnI+DQoNCiMjIyBDb21wYXJpbmcgMiBkYXRhIHNldHMuDQoqIGV4YW1wbGU6IHpvbWJpZXMgdGhhdCBoYXZlIGEgcmVndWxhciBkaWV0IGFuZCB0aG9zZSB0aGF0IGhhdmUgYSBicmFpbnMgYmFzZWQgZGlldA0KYGBge3J9DQppcV9icmFpbnMgPC0gYyg0NCwgNTIsIDQyLCA2NiwgNTMsIDQyLCA1NSwgNTcsIDU2LCA1MSkNCmlxX3JlZ3VsYXIgPC0gYyg1NSwgNDQsIDM0LCAxOCwgNTEsIDQwLCA0MCwgNDksIDQ4LCA0NikNCiMgQ2FsY3VsYXRlIHRoZSBtZWFuIGRpZmZlcmVuY2UgaW4gSVEgYmV0d2VlbiB0aGUgdHdvIGdyb3Vwcw0KbWVhbihpcV9icmFpbnMpIC0gIG1lYW4oaXFfcmVndWxhcikNCg0KIyBGaXQgdGhlIEJFU1QgbW9kZWwgdG8gdGhlIGRhdGEgZnJvbSBib3RoIGdyb3Vwcw0KYmVzdF9wb3N0ZXJpb3IgPC0gQkVTVG1jbWMoaXFfYnJhaW5zLCBpcV9yZWd1bGFyKQ0KYmVzdF9wb3N0ZXJpb3INCmBgYA0KDQojIyMjIyBvdXIgbWVhbiBkaWZmZXJlbmNlIHdhcyA5LjMsIG91ciBwb3N0ZXJpb3IgbWVhbiBkaWZmZXJlbmNlICg1MS43ODAgLSA0My4xMDIpPSA4LjY3OA0KYGBge3J9DQpwbG90KGJlc3RfcG9zdGVyaW9yKQ0KYGBgDQoNCg0KIyMjIyBCYXllc2lhbiBlc3RpbWF0ZSB1c2luZyBhIHQtZGlzdHJpYnV0aW9uIGlzIHJvYnVzdCB0byBvdXRsaWVycy4NCiogc3VwcG9zZSBvbmUgb2YgdGhlIHJlZ3VsYXIgZGlldCB6b21iaWVzIGhhcyBhIHNjb3JlIG9mIDE3NQ0KYGBge3J9DQppcV9icmFpbnMgPC0gYyg0NCwgNTIsIDQyLCA2NiwgNTMsIDQyLCA1NSwgNTcsIDU2LCA1MSkNCmlxX3JlZ3VsYXIgPC0gYyg1NSwgNDQsIDM0LCAxOCwgNTEsIDQwLCA0MCwgNDksIDQ4LCAxNzUpDQojIENhbGN1bGF0ZSB0aGUgbWVhbiBkaWZmZXJlbmNlIGluIElRIGJldHdlZW4gdGhlIHR3byBncm91cHMNCm1lYW4oaXFfYnJhaW5zKSAtICBtZWFuKGlxX3JlZ3VsYXIpDQoNCiMgRml0IHRoZSBCRVNUIG1vZGVsIHRvIHRoZSBkYXRhIGZyb20gYm90aCBncm91cHMNCmJlc3RfcG9zdGVyaW9yIDwtIEJFU1RtY21jKGlxX2JyYWlucywgaXFfcmVndWxhcikNCmJlc3RfcG9zdGVyaW9yDQpgYGANCg0KIyMjIyB0PVRoZXJlIGlzIG1vcmUgdW5jZXJ0YWludHkgaW4gb3VyIGVzdGltYXRlIHlldCwgd2Ugc3RpbGwgY29uY2x1ZGUgdGhhdCBicmFpbiBlYXRpbmcgem9tYmllcyBhcmUgbW9yZSBsaWtlbHkgdG8gaGF2ZSBhIGhpZ2hlciBJUSB0aGFuIHJlZ3VsYXIgZGlldCB6b21iaWVzLg0KYGBge3J9DQpwbG90KGJlc3RfcG9zdGVyaW9yKQ0KYGBgDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQoNCg0KDQo=