Case: Compring Housing Value of the top 5 wealthiest states using MCMC (may need some bayesian inference experience)
According to U.S. News, the top 10 wealthiest states in May 2019 are as follows:
- Maryland
- Alaska
- New Jersey
- Massachusetts
- Hawaii
- Connecticut
- New Hampshire
- Virginia
- California
- Washington
Now, we may be safe to assume that the wealthiest states most likely have some of the highest home values in the US. Of course, we do not know this for certain, however it is a good starting point.
What model should we use?
Regular reporting may be good, however, what if you wanted to make predictions and inference on direct differences? Would regular reporting allow for this? Not really. There are various techniques, however we will be looking at the Markov-Chain Monte Carlo Method to analyze our data.
The MC MC is a bayesian method of hiearchical analysis that allows for complex integration to be done computationally. For this specific example, we will be assuming a normally distributed dataset and normally distributed prior distribution with unknown µ and σ2. It is essentially doing a multi-sample t-test of differences in a Bayesian way.
It first creates two full conditional distributions for µ and σ2 using gibbs sampling. These two distributions are then included as possible samples of µ and σ2 to create posterior and posterior predictive distributions.
Now that (above) was a very general explanation of how the model works. However, if you are curious on the specifics, make sure to check this resource out. A general knowledge of Bayesian techniques and distributional knowledge may be necessary to complete this task. However, If for any reason you don’t really care about the statistics and you want to just do the modelling, just scroll down for the code
Wait, but are housing prices normally distributed?
Well, in all honesty, it depends. Housing prices are commonly non-normal distributions because of the way our economy is. There are fewer uber-rich people as there are lower-income. However, if transformed, this data might be taken as normally distributed.
Data
In comparing these states, we will use the Zillow dataset to look at their home value index. We are mostly interested in the Zhvi
data for each state. This is data collected on homes that were displayed on their website for sale. We assume that the data is independently collected from observation to observation.
The invgamma
will be necessary when including the full-conditional distribution for σ2 (which we will cover in a bit).
# Packages
library(tidyverse)
library(invgamma)
library(MASS)
# Read me in!
path <- "~/Downloads/Metro_Zhvi_Summary_AllHomes.csv"
zill <- read_csv(path)
Parsed with column specification:
cols(
RegionID = col_integer(),
Date = col_date(format = ""),
RegionName = col_character(),
State = col_character(),
SizeRank = col_integer(),
Zhvi = col_integer(),
MoM = col_double(),
QoQ = col_double(),
YoY = col_double(),
`5Year` = col_double(),
`10Year` = col_double(),
PeakMonth = col_character(),
PeakQuarter = col_character(),
PeakZHVI = col_integer(),
PctFallFromPeak = col_double(),
LastTimeAtCurrZHVI = col_character()
)
glimpse(zill)
Observations: 783
Variables: 16
$ RegionID [3m[38;5;246m<int>[39m[23m 102001, 394913, 753899, 394463, 394514, 394974, 394692, 395209, 394856, 394347…
$ Date [3m[38;5;246m<date>[39m[23m 2019-02-28, 2019-02-28, 2019-02-28, 2019-02-28, 2019-02-28, 2019-02-28, 2019-…
$ RegionName [3m[38;5;246m<chr>[39m[23m "United States", "New York, NY", "Los Angeles-Long Beach-Anaheim, CA", "Chicag…
$ State [3m[38;5;246m<chr>[39m[23m NA, "NY", "CA", "IL", "TX", "PA", "TX", "DC", "FL", "GA", "MA", "CA", "MI", "C…
$ SizeRank [3m[38;5;246m<int>[39m[23m 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, …
$ Zhvi [3m[38;5;246m<int>[39m[23m 226300, 440400, 652200, 225300, 244400, 233500, 206300, 406800, 284700, 218600…
$ MoM [3m[38;5;246m<dbl>[39m[23m 0.0031028369, 0.0034176350, -0.0007660487, 0.0022241993, 0.0057613169, 0.00300…
$ QoQ [3m[38;5;246m<dbl>[39m[23m 0.014343344, 0.010555301, 0.001228124, 0.010313901, 0.025167785, 0.009948097, …
$ YoY [3m[38;5;246m<dbl>[39m[23m 0.07200379, 0.04707561, 0.02466614, 0.03491043, 0.09990999, 0.03501773, 0.0628…
$ `5Year` [3m[38;5;246m<dbl>[39m[23m 0.06522199, 0.04517718, 0.06177574, 0.05122774, 0.10537396, 0.03851077, 0.0741…
$ `10Year` [3m[38;5;246m<dbl>[39m[23m 0.027220895, 0.012722285, 0.040997305, 0.003806871, 0.053739509, 0.006431629, …
$ PeakMonth [3m[38;5;246m<chr>[39m[23m "2019-02", "2006-07", "2019-01", "2007-02", "2019-02", "2007-05", "2019-02", "…
$ PeakQuarter [3m[38;5;246m<chr>[39m[23m "2019-Q1", "2006-Q3", "2019-Q1", "2007-Q1", "2019-Q1", "2007-Q2", "2019-Q1", "…
$ PeakZHVI [3m[38;5;246m<int>[39m[23m 226300, 452800, 652700, 254100, 244400, 237300, 206300, 435400, 311600, 218600…
$ PctFallFromPeak [3m[38;5;246m<dbl>[39m[23m 0.0000000000, -0.0273851590, -0.0007660487, -0.1133412043, 0.0000000000, -0.01…
$ LastTimeAtCurrZHVI [3m[38;5;246m<chr>[39m[23m "2019-02", "2006-01", "2018-12", "2004-12", "2019-02", "2006-05", "2019-02", "…
Data will be first separated into just the top 10 states.
state_codes <- c('MD', 'AK', 'NJ', 'MA', 'HI')
hvi <- zill[zill$State %in% state_codes,c(4,6)] # pull only state and house value.
unique(hvi$State) %in% state_codes %>% sum # confirm if correct.
[1] 5
summary(hvi$Zhvi)
Min. 1st Qu. Median Mean 3rd Qu. Max.
92200 218500 278000 331560 381600 810800
rm(path,zill)
Distributions of each of the groups are as follows. Not all the data looks roughly normal, but we will have to move forward with the assumptions. Interestingly, transformations will be hard to do. This is because the variances output by the model will be large, and re-transforming the data will may make the data converge to infinity.
boxplot(Zhvi ~ State, data = hvi)
Prior Elicitation
Now it is time to choose our prior parameters. Especially because our data is sparse, we are not so certain what the average value of homes in the top 5 states are. Accordingly, we will have to do with choosing the similar prior distributions for µ and uncertain priors for σ2.
Some general ways we may choose priors::
- Ask an expert what they believe to be the mean and standard deviation.
- Use a time-series analysis for data per state, pick a reasonable point estimate
- Do a regression analysis on income and housing prices. Predict a typical value of income for home.
- Assume ignorance
Since we are working with both unknown population variance means, we will have to generate each of them. If life and math was easier, we wouldn’t lose conjugacy when assuming both unknown values. We know this cannot happen because the variance is hiearchically defined in terms of the mean.
Explanation for Priors
To find our priors, we need to first determine which models we are going to use.
- µ will be distributed as a Normal with parameters m, v.
- σ2 will be distributed as an Inverse Gamma with parameters a, b.
Why this is so, may be found here in section 2.
Choosing our Priors
For this example, we will choose the following prior distributions (these were not all generated empirically).
m |
500000 |
278000 |
278000 |
278000 |
278000 |
v |
4000 |
4000 |
4000 |
4000 |
4000 |
a |
.01 |
.01 |
.01 |
.01 |
.01 |
b |
.01 |
.01 |
.01 |
.01 |
.01 |
Here is a justification for why I chose these priors. - m - This is generally the median of the top 5 data. - Hawaii adjusted based on relative median. - v - We want to choose a larger variance due to uncertainty. - Real values should most likely be picked generally larger due to uncertainty. - Depending on how much larger the spread for each state was, the variance was adjusted slightly. - a = .01 - Assuming ignorance - b = .01 - assuming ignorance
Building the Markov-Chain Model
Now here is the most interesting part. Generally, there are three steps required to create our Markov Chain model:
- Create intial values for µ and σ2.
- We will need to initialize a vector with some starting simulated values.
- These can be either µ = 0 and σ2 = 1 or the mean and variance our data.
- For the sake of learning, we will start with 0 and 1.
For i in J iterations…
a1) take a sample from full conditional (~same as posterior m) for µ where σ2 = j-1 b1) take a sample from full conditional (~same as posterior v) for σ2 where v = j-1 c1) These full conditional values will be used to create µj
cont… using the new mu[j] generated!! (this is one of the components that make it hiearchical)
a2) generate a full conditional (~same as posterior a) using prior a and length n of data. b2) generate a full conditional (~same as posterior b) for priors b, data, and using µj c2) these full conditional values will be used to create σ2j
- The new µj and σ2j values are the posterior distributions!
- Predictive distributions may be chosen by generating random samples of from either the posterior or prior.
Burn and thin samples that have not converged yet.
- Values generated by MC samples take time to converge, we will need to remove all values prior to that.
- Because each hiearchical value depends on each other, data may become heavily correlated. We may thin the data by choosing every multiple of uncorrelated data (using acf plots)
Let’s put it all together in a function!
norm_mcmc <- function(J, m, v, a, b, y) {
#' m, v, a, b : full-conditional priors for NN and IG
#' J : Monte-Carlo iterations
#' y : Data
# Set starting values for mu, sig2
mu <- c(0) ; sig2 <- c(1)
# Get important values
n <- length(y) ; ybar <- mean(y)
for (j in 2:J) {
# Create posterior for unknown mu using full conditionals
mstar <- ((n * v * ybar) + (m * sig2[j-1])) / (n * v + sig2[j-1])
vstar <- (v * sig2[j-1]) / (n * v + sig2[j-1])
mu[j] <- rnorm(1,mstar,sqrt(vstar))
# Create posterior for unknown sig^2 using full conditionals
astar <- a + (n/2)
bstar <- b + sum((y-mu[j])^2)/2
sig2[j] <- rinvgamma(1,astar,bstar)
}
list("Posterior mu" = mu,"Posterior sig2" = sig2, "post-pred" = rnorm(J,mu,sqrt(sig2)),
"Prior-pred" = rnorm(J,rnorm(J,m,sqrt(v)), sqrt(rinvgamma(J,a,b))))
# taking a looooooop of each mu and sig2, so okay to perish at certain values.
}
For practice, let’s pull out data from just Maryland and generate our posterior distribution. For J, a large value such as 100000 will suffice! Procedurally, some do 102000 to burn the first 2000 automatically. Don’t worry if NAs are produced. This is usually due to generating impossible prior predictive values. We’ll probably never need to use that distribution anyways.
mc_val <- norm_mcmc(100000, 278000, 4000, .01,.01, subset(hvi,hvi$State=='MD')$Zhvi)
NAs produced
lapply(mc_val, head)
$`Posterior mu`
[1] 0.0 210002.7 277971.8 278108.0 278063.4 278109.4
$`Posterior sig2`
[1] 1 5610195569 8269114600 12194980759 8169307515 9448542737
$`post-pred`
[1] -1.508377e-01 1.689168e+05 4.097918e+05 2.592844e+05 2.113386e+05 3.918210e+05
$`Prior-pred`
[1] -1.993960e+23 8.483385e+04 1.763289e+55 -1.400694e+20 -1.579684e+34 1.044109e+13
Burning, thinning, and assessing performance
Let’s take a look at some traceplots to see how many we will need to burn.
par(mfrow = c(1,2))
plot(mc_val$`Posterior sig2`, type = 'l', col = "red")
plot(mc_val$`Posterior mu`, type = 'l', col = "blue")
par(mfrow = c(1,1))
These traceplots show quick convergence. The variance looked rather healthy and converged immediately. For µ, we can take a look at the data without plotting and notice that there is a huge jump in mu from 0 to 129851 then convergence on the third value. We will burn the first 50 just to be safe. If we see a lot of oscillating, this means that we have a healthy markov chain
As for the thinning, we will observe ACF plots.
par(mfrow = c(1,2))
acf(mc_val$`Posterior sig2`)
acf(mc_val$`Posterior mu`)
par(mfrow = c(1,1))
Both plots show no serious correlation in any multiple from 1-50. Usually, if there are bars that exceed the blue lines, it means there is autocorrelation. These plots are also used for time-series analysis. We will keep all our values for the Maryland posterior
# if there was autocorrelation, use something like this to grab every 10th, or 5th or whatever multiple
# seq(50:100000, by = 5)[-1] removes first 50 and takes every 5th value...
rem <- function(data,rems) data[-c(1:rems)]
mc_val <- lapply(mc_val, function(x) rem(x, 50))
Other assessments and plots can be made as follows:
2D perspective plots show that there is a relatively small variance. Using Azimuth angles, you may navigate through the latent space.
persp(kde2d(mc_val$`Posterior mu`, mc_val$`Posterior sig2`), phi = , 65,theta = 60, xlab = "µ", ylab = "sigma^2")
Image plots give us a heat map of the same thing from a birds eye view, a relatively precise variance. Contour lines show us the Z distribution density. This will most likely give us posterior values that are closely knit.
image(kde2d(mc_val$`Posterior mu`, mc_val$`Posterior sig2`))
contour(kde2d(mc_val$`Posterior mu`, mc_val$`Posterior sig2`), add = TRUE)
mtext(expression(sigma^2), side =2, line = 2.5)
Comparing distributions
Now here comes the real analysis. Since we have 5 different states, the proper burning and thinning will be done without explanation below (turns out, no thinning or burning is really too necessary. Our data was so small, that it immediately converged and did not affect our markov chain very much. So much for a fun analysis!).
hi_val <- norm_mcmc(100000, 500000, 4000, .01,.01, subset(hvi,hvi$State=='HI')$Zhvi)
ak_val <- norm_mcmc(100000, 278000, 4000, .01,.01, subset(hvi,hvi$State=='AK')$Zhvi)
ma_val <- norm_mcmc(100000, 278000, 4000, .01,.01, subset(hvi,hvi$State=='MA')$Zhvi)
md_val <- norm_mcmc(100000, 278000, 4000, .01,.01, subset(hvi,hvi$State=='MD')$Zhvi)
nj_val <- norm_mcmc(100000, 278000, 4000, .01,.01, subset(hvi,hvi$State=='NJ')$Zhvi)
hi_val <- lapply(hi_val, function(x) rem(x,50)) ; ak_val <- lapply(ak_val, function(x) rem(x,50))
ma_val <- lapply(ma_val, function(x) rem(x,50)) ; md_val <- lapply(md_val, function(x) rem(x,50))
nj_val <- lapply(nj_val, function(x) rem(x,50))
Distributional curves may be compared in a pariwise manner. This is the beauty of using monte-carlo sampling. Since we are looking at multiple comparisons we will start by performing a pseudo F-test (comparing the ratios of the variances). Since there are choose(5,2) = 10 possible combinations, we will only grab the most interesting looking ones.
plot(density(hi_val$`Posterior sig2`), xlim = c(0,8*10^10), ylim = c(0, 7*10^-10))
lines(density(ak_val$`Posterior sig2`), col = "blue") ; lines(density(md_val$`Posterior sig2`), col = "red")
lines(density(nj_val$`Posterior sig2`), col = "green") ; lines(density(ma_val$`Posterior sig2`), col = "brown")
legend("topright", rep(3,1), state_codes, c("red", "blue", "green", "brown", "black"))
Hawaii is not significantly larger than any of the other states because the intervals don’t contain 1. This will mean that the none of the other comparisons will yield much of a difference.
quantile(hi_val$`Posterior sig2`/md_val$`Posterior sig2`,c(.025, .975))
2.5% 97.5%
0.3191672 18.3357108
quantile(hi_val$`Posterior sig2`/nj_val$`Posterior sig2`,c(.025, .975))
2.5% 97.5%
0.2375116 22.1070397
quantile(hi_val$`Posterior sig2`/ak_val$`Posterior sig2`,c(.025, .975))
2.5% 97.5%
0.6402673 58.4333022
quantile(hi_val$`Posterior sig2`/ma_val$`Posterior sig2`,c(.025, .975))
2.5% 97.5%
0.07318601 3.67102904
We may surmise here that Hawaii is NOT significanty different from the rest of the states. HOWEVER, there is a practical significance here. Hawaiian homes on average are 222,000 dollars larger on average than Maryland homes. This is not a trivial difference.
quantile(hi_val$`Posterior mu` - md_val$`Posterior mu`,c(.025, .975))
2.5% 97.5%
221825.5 222174.9
Posterior probabilities may also be discovered.
mean(nj_val$`Posterior mu` < 278000)
[1] 0.4996398
The posterior probability of observing a home in New Jersey that costs less than 278k is close to 50%. These tight distributions are most likely due to having not enough data to inference off of.
Posterior Predictive
Predictive distributions were also included in the formula. These predictives have a support from (-inf,inf) so it might be normal. The distribution is larger than just the posterior.. The posterior predictive probability of the next home in Alaska being larger than 300k is below:
mean(nj_val$`post-pred`>300*10^3)
[1] 0.4170285
Conclusion
Overall, this analysis was very simple. There are 4 key takeaways:
- Best to have data that is as normally distributed as possible
- The posterior distribution really made a large effect on the outcomes of our model
- Data sufficiency is very important. Our overall posterior was very tight knit close to the data.
- Always remember where the data comes from. This is a representative sample of zillow home sellers.
There are so many assumptions to be made while working with simulation models. However, there are so many benefits as well! Modelling heiarchical models may be applied in various settings (marketing, supply-chain, machine learning, etc). Knowing the basics definitely pays off. Go try this with a new dataset!
LS0tCnRpdGxlOiAiSW5mZXJlbmNpbmcgTm9ybWFsIERpc3RyaWJ1dGlvbnMgdXNpbmcgTWFya292IENoYWluIE1vbnRlIENhcmxvIgpvdXRwdXQ6IAogIGh0bWxfbm90ZWJvb2s6CiAgICB0b2M6IHRydWUKICAgIHRvY19mbG9hdDogdHJ1ZQotLS0KCjxiPkNhc2U6PC9iPiBDb21wcmluZyBIb3VzaW5nIFZhbHVlIG9mIHRoZSB0b3AgNSB3ZWFsdGhpZXN0IHN0YXRlcyB1c2luZyBNQ01DIChtYXkgbmVlZCBzb21lIGJheWVzaWFuIGluZmVyZW5jZSBleHBlcmllbmNlKQoKQWNjb3JkaW5nIHRvIFtVLlMuIE5ld3NdKGh0dHBzOi8vd3d3LnVzbmV3cy5jb20vbmV3cy9iZXN0LXN0YXRlcy9zbGlkZXNob3dzLzEwLXdlYWx0aGllc3Qtc3RhdGVzLWluLWFtZXJpY2EpLCB0aGUgdG9wIDEwIHdlYWx0aGllc3Qgc3RhdGVzIGluIE1heSAyMDE5IGFyZSBhcyBmb2xsb3dzOgoKICAxLiBNYXJ5bGFuZAogIDIuIEFsYXNrYQogIDMuIE5ldyBKZXJzZXkKICA0LiBNYXNzYWNodXNldHRzCiAgNS4gSGF3YWlpCiAgNi4gQ29ubmVjdGljdXQKICA3LiBOZXcgSGFtcHNoaXJlCiAgOC4gVmlyZ2luaWEKICA5LiBDYWxpZm9ybmlhCiAgMTAuIFdhc2hpbmd0b24KCk5vdywgd2UgbWF5IGJlIHNhZmUgdG8gYXNzdW1lIHRoYXQgdGhlIHdlYWx0aGllc3Qgc3RhdGVzIG1vc3QgbGlrZWx5IGhhdmUgc29tZSBvZiB0aGUgaGlnaGVzdCBob21lIHZhbHVlcyBpbiB0aGUgVVMuIE9mIGNvdXJzZSwgd2UgZG8gbm90IGtub3cgdGhpcyBmb3IgY2VydGFpbiwgaG93ZXZlciBpdCBpcyBhIGdvb2Qgc3RhcnRpbmcgcG9pbnQuIAoKIyMjIFdoYXQgbW9kZWwgc2hvdWxkIHdlIHVzZT8KClJlZ3VsYXIgcmVwb3J0aW5nIG1heSBiZSBnb29kLCBob3dldmVyLCB3aGF0IGlmIHlvdSB3YW50ZWQgdG8gbWFrZSBwcmVkaWN0aW9ucyBhbmQgaW5mZXJlbmNlIG9uIGRpcmVjdCBkaWZmZXJlbmNlcz8gV291bGQgcmVndWxhciByZXBvcnRpbmcgYWxsb3cgZm9yIHRoaXM/IE5vdCByZWFsbHkuIFRoZXJlIGFyZSB2YXJpb3VzIHRlY2huaXF1ZXMsIGhvd2V2ZXIgd2Ugd2lsbCBiZSBsb29raW5nIGF0IHRoZSBNYXJrb3YtQ2hhaW4gTW9udGUgQ2FybG8gTWV0aG9kIHRvIGFuYWx5emUgb3VyIGRhdGEuCgpUaGUgTUMgTUMgaXMgYSBiYXllc2lhbiBtZXRob2Qgb2YgaGllYXJjaGljYWwgYW5hbHlzaXMgdGhhdCBhbGxvd3MgZm9yIGNvbXBsZXggaW50ZWdyYXRpb24gdG8gYmUgZG9uZSBjb21wdXRhdGlvbmFsbHkuIEZvciB0aGlzIHNwZWNpZmljIGV4YW1wbGUsIHdlIHdpbGwgYmUgYXNzdW1pbmcgYSBub3JtYWxseSBkaXN0cmlidXRlZCBkYXRhc2V0IGFuZCBub3JtYWxseSBkaXN0cmlidXRlZCBwcmlvciBkaXN0cmlidXRpb24gd2l0aCB1bmtub3duIMK1IGFuZCDPgzxzdXA+Mjwvc3VwPi4gSXQgaXMgZXNzZW50aWFsbHkgZG9pbmcgYSBtdWx0aS1zYW1wbGUgdC10ZXN0IG9mIGRpZmZlcmVuY2VzIGluIGEgQmF5ZXNpYW4gd2F5LgoKSXQgZmlyc3QgY3JlYXRlcyB0d28gZnVsbCBjb25kaXRpb25hbCBkaXN0cmlidXRpb25zIGZvciDCtSBhbmQgz4M8c3VwPjI8L3N1cD4gdXNpbmcgZ2liYnMgc2FtcGxpbmcuIFRoZXNlIHR3byBkaXN0cmlidXRpb25zIGFyZSB0aGVuIGluY2x1ZGVkIGFzIHBvc3NpYmxlIHNhbXBsZXMgb2YgwrUgYW5kIM+DPHN1cD4yPC9zdXA+IHRvIGNyZWF0ZSBwb3N0ZXJpb3IgYW5kIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbnMuCgpOb3cgdGhhdCAoYWJvdmUpIHdhcyBhICp2ZXJ5KiBnZW5lcmFsIGV4cGxhbmF0aW9uIG9mIGhvdyB0aGUgbW9kZWwgd29ya3MuIEhvd2V2ZXIsIGlmIHlvdSBhcmUgY3VyaW91cyBvbiB0aGUgc3BlY2lmaWNzLCBtYWtlIHN1cmUgdG8gY2hlY2sgW3RoaXNdKGh0dHA6Ly93d3cuY29sdW1iaWEuZWR1L35taDIwNzgvTWFjaGluZUxlYXJuaW5nT1JGRS9NQ01DX0JheWVzLnBkZikgcmVzb3VyY2Ugb3V0LiBBIGdlbmVyYWwga25vd2xlZGdlIG9mIEJheWVzaWFuIHRlY2huaXF1ZXMgYW5kIGRpc3RyaWJ1dGlvbmFsIGtub3dsZWRnZSBtYXkgYmUgbmVjZXNzYXJ5IHRvIGNvbXBsZXRlIHRoaXMgdGFzay4gPGI+SG93ZXZlciwgSWYgZm9yIGFueSByZWFzb24geW91IGRvbid0IHJlYWxseSBjYXJlIGFib3V0IHRoZSBzdGF0aXN0aWNzIGFuZCB5b3Ugd2FudCB0byBqdXN0IGRvIHRoZSBtb2RlbGxpbmcsIGp1c3Qgc2Nyb2xsIGRvd24gZm9yIHRoZSBjb2RlPC9iPiAKCiMjIyBXYWl0LCBidXQgYXJlIGhvdXNpbmcgcHJpY2VzIG5vcm1hbGx5IGRpc3RyaWJ1dGVkPwoKV2VsbCwgaW4gYWxsIGhvbmVzdHksIGl0IGRlcGVuZHMuIEhvdXNpbmcgcHJpY2VzIGFyZSBjb21tb25seSBub24tbm9ybWFsIGRpc3RyaWJ1dGlvbnMgYmVjYXVzZSBvZiB0aGUgd2F5IG91ciBlY29ub215IGlzLiBUaGVyZSBhcmUgZmV3ZXIgdWJlci1yaWNoIHBlb3BsZSBhcyB0aGVyZSBhcmUgbG93ZXItaW5jb21lLiBIb3dldmVyLCBpZiB0cmFuc2Zvcm1lZCwgdGhpcyBkYXRhIG1pZ2h0IGJlIHRha2VuIGFzIG5vcm1hbGx5IGRpc3RyaWJ1dGVkLgoKIyMjIERhdGEKCkluIGNvbXBhcmluZyB0aGVzZSBzdGF0ZXMsIHdlIHdpbGwgdXNlIHRoZSBbWmlsbG93XShodHRwczovL3d3dy56aWxsb3cuY29tLykgZGF0YXNldCB0byBsb29rIGF0IHRoZWlyIGhvbWUgdmFsdWUgaW5kZXguIFdlIGFyZSBtb3N0bHkgaW50ZXJlc3RlZCBpbiB0aGUgYFpodmlgIGRhdGEgZm9yIGVhY2ggc3RhdGUuIFRoaXMgaXMgZGF0YSBjb2xsZWN0ZWQgb24gaG9tZXMgdGhhdCB3ZXJlIGRpc3BsYXllZCBvbiB0aGVpciB3ZWJzaXRlIGZvciBzYWxlLiBXZSBhc3N1bWUgdGhhdCB0aGUgZGF0YSBpcyBpbmRlcGVuZGVudGx5IGNvbGxlY3RlZCBmcm9tIG9ic2VydmF0aW9uIHRvIG9ic2VydmF0aW9uLgoKVGhlIGBpbnZnYW1tYWAgd2lsbCBiZSBuZWNlc3Nhcnkgd2hlbiBpbmNsdWRpbmcgdGhlIGZ1bGwtY29uZGl0aW9uYWwgZGlzdHJpYnV0aW9uIGZvciDPgzxzdXA+Mjwvc3VwPiAod2hpY2ggd2Ugd2lsbCBjb3ZlciBpbiBhIGJpdCkuCgpgYGB7cn0KIyBQYWNrYWdlcwpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShpbnZnYW1tYSkKbGlicmFyeShNQVNTKQojIFJlYWQgbWUgaW4hCnBhdGggPC0gIn4vRG93bmxvYWRzL01ldHJvX1podmlfU3VtbWFyeV9BbGxIb21lcy5jc3YiCnppbGwgPC0gcmVhZF9jc3YocGF0aCkKZ2xpbXBzZSh6aWxsKQpgYGAKCkRhdGEgd2lsbCBiZSBmaXJzdCBzZXBhcmF0ZWQgaW50byBqdXN0IHRoZSB0b3AgMTAgc3RhdGVzLgoKYGBge3J9CnN0YXRlX2NvZGVzIDwtIGMoJ01EJywgJ0FLJywgJ05KJywgJ01BJywgJ0hJJykKaHZpIDwtIHppbGxbemlsbCRTdGF0ZSAlaW4lIHN0YXRlX2NvZGVzLGMoNCw2KV0gIyBwdWxsIG9ubHkgc3RhdGUgYW5kIGhvdXNlIHZhbHVlLgp1bmlxdWUoaHZpJFN0YXRlKSAlaW4lIHN0YXRlX2NvZGVzICAlPiUgc3VtICMgY29uZmlybSBpZiBjb3JyZWN0LgpzdW1tYXJ5KGh2aSRaaHZpKQpybShwYXRoLHppbGwpCmBgYAoKRGlzdHJpYnV0aW9ucyBvZiBlYWNoIG9mIHRoZSBncm91cHMgYXJlIGFzIGZvbGxvd3MuIE5vdCBhbGwgdGhlIGRhdGEgbG9va3Mgcm91Z2hseSBub3JtYWwsIGJ1dCB3ZSB3aWxsIGhhdmUgdG8gbW92ZSBmb3J3YXJkIHdpdGggdGhlIGFzc3VtcHRpb25zLiBJbnRlcmVzdGluZ2x5LCB0cmFuc2Zvcm1hdGlvbnMgd2lsbCBiZSBoYXJkIHRvIGRvLiBUaGlzIGlzIGJlY2F1c2UgdGhlIHZhcmlhbmNlcyBvdXRwdXQgYnkgdGhlIG1vZGVsIHdpbGwgYmUgbGFyZ2UsIGFuZCByZS10cmFuc2Zvcm1pbmcgdGhlIGRhdGEgd2lsbCBtYXkgbWFrZSB0aGUgZGF0YSBjb252ZXJnZSB0byBpbmZpbml0eS4KCmBgYHtyfQpib3hwbG90KFpodmkgfiBTdGF0ZSwgZGF0YSA9IGh2aSkgCmBgYAoKIyMjIFByaW9yIEVsaWNpdGF0aW9uCgpOb3cgaXQgaXMgdGltZSB0byBjaG9vc2Ugb3VyIHByaW9yIHBhcmFtZXRlcnMuIEVzcGVjaWFsbHkgYmVjYXVzZSBvdXIgZGF0YSBpcyBzcGFyc2UsIHdlIGFyZSBub3Qgc28gY2VydGFpbiB3aGF0IHRoZSBhdmVyYWdlIHZhbHVlIG9mIGhvbWVzIGluIHRoZSB0b3AgNSBzdGF0ZXMgYXJlLiBBY2NvcmRpbmdseSwgd2Ugd2lsbCBoYXZlIHRvIGRvIHdpdGggY2hvb3NpbmcgdGhlIHNpbWlsYXIgcHJpb3IgZGlzdHJpYnV0aW9ucyBmb3IgwrUgYW5kIHVuY2VydGFpbiBwcmlvcnMgZm9yIM+DPHN1cD4yPC9zdXA+LgoKU29tZSBnZW5lcmFsIHdheXMgd2UgbWF5IGNob29zZSBwcmlvcnM6OgoKICAxLiBBc2sgYW4gZXhwZXJ0IHdoYXQgdGhleSBiZWxpZXZlIHRvIGJlIHRoZSBtZWFuIGFuZCBzdGFuZGFyZCBkZXZpYXRpb24uCiAgMi4gVXNlIGEgdGltZS1zZXJpZXMgYW5hbHlzaXMgZm9yIGRhdGEgcGVyIHN0YXRlLCBwaWNrIGEgcmVhc29uYWJsZSBwb2ludCBlc3RpbWF0ZQogIDMuIERvIGEgcmVncmVzc2lvbiBhbmFseXNpcyBvbiBpbmNvbWUgYW5kIGhvdXNpbmcgcHJpY2VzLiBQcmVkaWN0IGEgdHlwaWNhbCB2YWx1ZSBvZiBpbmNvbWUgZm9yIGhvbWUuCiAgNC4gQXNzdW1lIGlnbm9yYW5jZQoKU2luY2Ugd2UgYXJlIHdvcmtpbmcgd2l0aCBib3RoIHVua25vd24gcG9wdWxhdGlvbiB2YXJpYW5jZSBtZWFucywgd2Ugd2lsbCBoYXZlIHRvIGdlbmVyYXRlIGVhY2ggb2YgdGhlbS4gSWYgbGlmZSBhbmQgbWF0aCB3YXMgZWFzaWVyLCB3ZSB3b3VsZG4ndCBsb3NlIGNvbmp1Z2FjeSB3aGVuIGFzc3VtaW5nIGJvdGggdW5rbm93biB2YWx1ZXMuIFdlIGtub3cgdGhpcyBjYW5ub3QgaGFwcGVuIGJlY2F1c2UgdGhlIHZhcmlhbmNlIGlzIGhpZWFyY2hpY2FsbHkgZGVmaW5lZCBpbiB0ZXJtcyBvZiB0aGUgbWVhbi4gCgojIyMjIEV4cGxhbmF0aW9uIGZvciBQcmlvcnMKClRvIGZpbmQgb3VyIHByaW9ycywgd2UgbmVlZCB0byBmaXJzdCBkZXRlcm1pbmUgd2hpY2ggbW9kZWxzIHdlIGFyZSBnb2luZyB0byB1c2UuCgogIC0gwrUgd2lsbCBiZSBkaXN0cmlidXRlZCBhcyBhIE5vcm1hbCB3aXRoIHBhcmFtZXRlcnMgbSwgdi4KICAtIM+DPHN1cD4yPC9zdXA+IHdpbGwgYmUgZGlzdHJpYnV0ZWQgYXMgYW4gSW52ZXJzZSBHYW1tYSB3aXRoIHBhcmFtZXRlcnMgYSwgYi4KCldoeSB0aGlzIGlzIHNvLCBtYXkgYmUgZm91bmQgW2hlcmVdKGh0dHA6Ly93d3cuY29sdW1iaWEuZWR1L35taDIwNzgvTWFjaGluZUxlYXJuaW5nT1JGRS9NQ01DX0JheWVzLnBkZikgaW4gc2VjdGlvbiAyLgoKIyMjIyBDaG9vc2luZyBvdXIgUHJpb3JzCgpGb3IgdGhpcyBleGFtcGxlLCB3ZSB3aWxsIGNob29zZSB0aGUgZm9sbG93aW5nIHByaW9yIGRpc3RyaWJ1dGlvbnMgKHRoZXNlIHdlcmUgbm90IGFsbCBnZW5lcmF0ZWQgZW1waXJpY2FsbHkpLgoKfCBYIHwgSGF3YWlpIHwgQWxhc2thIHwgTWFzc2FjaHVzZXR0cyB8IE1hcnlsYW5kIHwgTmV3IEplcnNleSB8CnwtLS18LS0tLS0tLS18LS0tLS0tLS18LS0tLS0tLS0tLS0tLS0tfC0tLS0tLS0tLS18LS0tLS0tLS0tLS0tfAp8IG0gfCA1MDAwMDAgfCAyNzgwMDAgfCAyNzgwMDAgICAgICAgIHwgMjc4MDAwICAgfCAyNzgwMDAgICAgIHwKfCB2IHwgIDQwMDAgIHwgIDQwMDAgIHwgIDQwMDAgICAgICAgICB8ICA0MDAwICAgIHwgIDQwMDAgICAgICB8CnwgYSB8IC4wMSAgICB8IC4wMSAgICB8IC4wMSAgICAgICAgICAgfCAuMDEgICAgICB8IC4wMSAgICAgICAgfAp8IGIgfCAuMDEgICAgfCAuMDEgICAgfCAuMDEgICAgICAgICAgIHwgLjAxICAgICAgfCAuMDEgICAgICAgIHwKCgpIZXJlIGlzIGEganVzdGlmaWNhdGlvbiBmb3Igd2h5IEkgY2hvc2UgdGhlc2UgcHJpb3JzLgogIC0gbSAKICAtIFRoaXMgaXMgZ2VuZXJhbGx5IHRoZSBtZWRpYW4gb2YgdGhlIHRvcCA1IGRhdGEuIAogIC0gSGF3YWlpIGFkanVzdGVkIGJhc2VkIG9uIHJlbGF0aXZlIG1lZGlhbi4KICAtIHYKICAgIC0gV2Ugd2FudCB0byBjaG9vc2UgYSBsYXJnZXIgdmFyaWFuY2UgZHVlIHRvIHVuY2VydGFpbnR5LgogICAgLSBSZWFsIHZhbHVlcyBzaG91bGQgbW9zdCBsaWtlbHkgYmUgcGlja2VkIGdlbmVyYWxseSBsYXJnZXIgZHVlIHRvIHVuY2VydGFpbnR5LgogICAgLSBEZXBlbmRpbmcgb24gaG93IG11Y2ggbGFyZ2VyIHRoZSBzcHJlYWQgZm9yIGVhY2ggc3RhdGUgd2FzLCB0aGUgdmFyaWFuY2Ugd2FzIGFkanVzdGVkIHNsaWdodGx5LgogIC0gYSA9IC4wMSAKICAgIC0gQXNzdW1pbmcgaWdub3JhbmNlCiAgLSBiID0gLjAxIAogICAgLSBhc3N1bWluZyBpZ25vcmFuY2UKCiMjIyBCdWlsZGluZyB0aGUgTWFya292LUNoYWluIE1vZGVsCgpOb3cgaGVyZSBpcyB0aGUgbW9zdCBpbnRlcmVzdGluZyBwYXJ0LiAKR2VuZXJhbGx5LCB0aGVyZSBhcmUgdGhyZWUgc3RlcHMgcmVxdWlyZWQgdG8gY3JlYXRlIG91ciBNYXJrb3YgQ2hhaW4gbW9kZWw6CgogIDEuIENyZWF0ZSBpbnRpYWwgdmFsdWVzIGZvciDCtSBhbmQgz4M8c3VwPjI8L3N1cD4uCiAgICAtIFdlIHdpbGwgbmVlZCB0byBpbml0aWFsaXplIGEgdmVjdG9yIHdpdGggc29tZSBzdGFydGluZyBzaW11bGF0ZWQgdmFsdWVzLgogICAgLSBUaGVzZSBjYW4gYmUgZWl0aGVyIMK1ID0gMCBhbmQgz4M8c3VwPjI8L3N1cD4gPSAxIG9yIHRoZSBtZWFuIGFuZCB2YXJpYW5jZSBvdXIgZGF0YS4KICAgIC0gRm9yIHRoZSBzYWtlIG9mIGxlYXJuaW5nLCB3ZSB3aWxsIHN0YXJ0IHdpdGggMCBhbmQgMS4KCmBgYHtyLCBlY2hvID0gRkFMU0UsIHJlc3VsdHM9IEZBTFNFfQptdSA8LSBjKDApICMgb3IgbXUgPC0gbWVhbihkYXRhKQpzaWcyIDwtIGMoMSkgIyBvciBzaWcyIDwtIHZhcihkYXRhKQojIG4gPC0gbGVuZ3RoKGRhdGEpCiMgbSA8LSByZWZlciB0byBjaGFydCBhYm92ZSA7IGEgPC0gcmVmZXIgdG8gY2hhcnQgYWJvdmUKIyB2IDwtIHJlZmVyIHRvIGNoYXJ0IGFib3ZlIDsgYiA8LSByZWZlciB0byBjaGFydCBhYm92ZQpybShtdSxzaWcyKSAjIHdlIHdvbid0IGJlIHVzaW5nIHRoZXNlCmBgYAoKICAyLiBGb3IgaSBpbiBKIGl0ZXJhdGlvbnMuLi4KICAKICAgIGExKSB0YWtlIGEgc2FtcGxlIGZyb20gZnVsbCBjb25kaXRpb25hbCAofnNhbWUgYXMgcG9zdGVyaW9yIG0qKSBmb3IgwrUgd2hlcmUgz4M8c3VwPjI8L3N1cD4gID0gai0xCiAgICBiMSkgdGFrZSBhIHNhbXBsZSBmcm9tIGZ1bGwgY29uZGl0aW9uYWwgKH5zYW1lIGFzIHBvc3RlcmlvciB2KikgZm9yIM+DPHN1cD4yPC9zdXA+IHdoZXJlIHYgPSBqLTEKICAgIGMxKSBUaGVzZSBmdWxsIGNvbmRpdGlvbmFsIHZhbHVlcyB3aWxsIGJlIHVzZWQgdG8gY3JlYXRlIMK1PHN1Yj5qPC9zdWI+CgpgYGB7ciwgZWNobyA9IEZBTFNFLCByZXN1bHRzID0gRkFMU0V9CnZzdGFyIDwtIHYgKiBzaWcyW2otMV0gLyAobiAqIHYgKyBzaWcyW2ogLSAxXSkgIyB0aGlzIGlzIHRoZSBwb3N0ZXJpb3IgdioKbXN0YXIgPC0gKG4gKiB2ICogeWJhciArIG0gKiBzaWcyW2ogLSAxXSkvKG4gKiB2ICsgc2lnMltqIC0gMV0pICMgdGhpcyBpcyB0aGUgcG9zdGVyaW9yIG0qCm11W2pdIDwtIHJub3JtKDEsIG1zdGFyLCBzcXJ0KHZzdGFyKSkgIyBHZW5lcmF0ZSAxIHNhbXBsZSBmcm9tIGZ1bGwtY29uZGl0aW9uYWwocG9zdGVyaW9yKSBkaXN0cmlidXRpb24KYGBgCgogIDIuIGNvbnQuLi4gdXNpbmcgdGhlIG5ldyBtdVtqXSBnZW5lcmF0ZWQhISAodGhpcyBpcyBvbmUgb2YgdGhlIGNvbXBvbmVudHMgdGhhdCBtYWtlIGl0IGhpZWFyY2hpY2FsKQogIAogICAgYTIpIGdlbmVyYXRlIGEgZnVsbCBjb25kaXRpb25hbCAofnNhbWUgYXMgcG9zdGVyaW9yIGEqKSB1c2luZyBwcmlvciBhIGFuZCBsZW5ndGggbiBvZiBkYXRhLgogICAgYjIpIGdlbmVyYXRlIGEgZnVsbCBjb25kaXRpb25hbCAofnNhbWUgYXMgcG9zdGVyaW9yIGIqKSBmb3IgcHJpb3JzIGIsIGRhdGEsIGFuZCB1c2luZyDCtTxzdWI+ajwvc3ViPgogICAgYzIpIHRoZXNlIGZ1bGwgY29uZGl0aW9uYWwgdmFsdWVzIHdpbGwgYmUgdXNlZCB0byBjcmVhdGUgz4M8c3VwPjI8L3N1cD48c3ViPmo8L3N1Yj4KCmBgYHtyLCBlY2hvID0gRkFMU0UsIHJlc3VsdHM9IEZBTFNFfQphc3RhciA8LSBhICsgKG4vMikKYnN0YXIgPC0gYiArIHN1bSgoZGF0YS1tdVtqXSleMikvMgpzaWcyW2pdIDwtIHJpbnZnYW1tYSgxLGFzdGFyLGJzdGFyKQpgYGAKCiAgMy4gVGhlIG5ldyDCtTxzdWI+ajwvc3ViPiBhbmQgz4M8c3VwPjI8L3N1cD48c3ViPmo8L3N1Yj4gdmFsdWVzIGFyZSB0aGUgcG9zdGVyaW9yIGRpc3RyaWJ1dGlvbnMhCiAgNC4gUHJlZGljdGl2ZSBkaXN0cmlidXRpb25zIG1heSBiZSBjaG9zZW4gYnkgZ2VuZXJhdGluZyByYW5kb20gc2FtcGxlcyBvZiBmcm9tIGVpdGhlciB0aGUgcG9zdGVyaW9yIG9yIHByaW9yLgogIApgYGB7ciwgZWNobyA9IEZBTFNFLCByZXN1bHRzPSBGQUxTRX0KbGlzdCgicG9zdC1wcmVkIiA9IHJub3JtKEosbXUsc3FydChzaWcyKSksICJQcmlvci1wcmVkIiA9IHJub3JtKEoscm5vcm0oSixtLHNxcnQodikpLCBzcXJ0KHJpbnZnYW1tYShKLGEsYikpKSkKYGBgCgogIDQuIEJ1cm4gYW5kIHRoaW4gc2FtcGxlcyB0aGF0IGhhdmUgbm90IGNvbnZlcmdlZCB5ZXQuCiAgCiAgICAtIFZhbHVlcyBnZW5lcmF0ZWQgYnkgTUMgc2FtcGxlcyB0YWtlIHRpbWUgdG8gY29udmVyZ2UsIHdlIHdpbGwgbmVlZCB0byByZW1vdmUgYWxsIHZhbHVlcyBwcmlvciB0byB0aGF0LgogICAgLSBCZWNhdXNlIGVhY2ggaGllYXJjaGljYWwgdmFsdWUgZGVwZW5kcyBvbiBlYWNoIG90aGVyLCBkYXRhIG1heSBiZWNvbWUgaGVhdmlseSBjb3JyZWxhdGVkLiBXZSBtYXkgdGhpbiB0aGUgZGF0YSBieSBjaG9vc2luZyBldmVyeSBtdWx0aXBsZSBvZiB1bmNvcnJlbGF0ZWQgZGF0YSAodXNpbmcgYWNmIHBsb3RzKQoKPGhyPgoKTGV0J3MgcHV0IGl0IGFsbCB0b2dldGhlciBpbiBhIGZ1bmN0aW9uIQoKYGBge3J9Cm5vcm1fbWNtYyA8LSBmdW5jdGlvbihKLCBtLCB2LCBhLCBiLCB5KSB7CiAgIycgIG0sIHYsIGEsIGIgOiBmdWxsLWNvbmRpdGlvbmFsIHByaW9ycyBmb3IgTk4gYW5kIElHCiAgIycgIEogOiBNb250ZS1DYXJsbyBpdGVyYXRpb25zCiAgIycgIHkgOiBEYXRhCiAgCiAgIyBTZXQgc3RhcnRpbmcgdmFsdWVzIGZvciBtdSwgc2lnMgogIG11IDwtIGMoMCkgOyBzaWcyIDwtIGMoMSkKICAjIEdldCBpbXBvcnRhbnQgdmFsdWVzCiAgbiA8LSBsZW5ndGgoeSkgOyB5YmFyIDwtIG1lYW4oeSkKICAKICBmb3IgKGogaW4gMjpKKSB7CiAgICAjIENyZWF0ZSBwb3N0ZXJpb3IgZm9yIHVua25vd24gbXUgdXNpbmcgZnVsbCBjb25kaXRpb25hbHMKICAgIG1zdGFyIDwtICgobiAqIHYgKiB5YmFyKSArIChtICogc2lnMltqLTFdKSkgLyAobiAqIHYgKyBzaWcyW2otMV0pCiAgICB2c3RhciA8LSAodiAqIHNpZzJbai0xXSkgLyAobiAqIHYgKyBzaWcyW2otMV0pCiAgICBtdVtqXSA8LSBybm9ybSgxLG1zdGFyLHNxcnQodnN0YXIpKQogICAgIyBDcmVhdGUgcG9zdGVyaW9yIGZvciB1bmtub3duIHNpZ14yIHVzaW5nIGZ1bGwgY29uZGl0aW9uYWxzCiAgICBhc3RhciA8LSBhICsgKG4vMikKICAgIGJzdGFyIDwtIGIgKyBzdW0oKHktbXVbal0pXjIpLzIKICAgIHNpZzJbal0gPC0gcmludmdhbW1hKDEsYXN0YXIsYnN0YXIpCiAgfQogIGxpc3QoIlBvc3RlcmlvciBtdSIgPSBtdSwiUG9zdGVyaW9yIHNpZzIiID0gc2lnMiwgInBvc3QtcHJlZCIgPSBybm9ybShKLG11LHNxcnQoc2lnMikpLCAKICAgICAgICJQcmlvci1wcmVkIiA9IHJub3JtKEoscm5vcm0oSixtLHNxcnQodikpLCBzcXJ0KHJpbnZnYW1tYShKLGEsYikpKSkKICAjIHRha2luZyBhIGxvb29vb29vcCBvZiBlYWNoIG11IGFuZCBzaWcyLCBzbyBva2F5IHRvIHBlcmlzaCBhdCBjZXJ0YWluIHZhbHVlcy4KfQpgYGAKCjxocj4KCkZvciBwcmFjdGljZSwgbGV0J3MgcHVsbCBvdXQgZGF0YSBmcm9tIGp1c3QgTWFyeWxhbmQgYW5kIGdlbmVyYXRlIG91ciBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uLiBGb3IgSiwgYSBsYXJnZSB2YWx1ZSBzdWNoIGFzIDEwMDAwMCB3aWxsIHN1ZmZpY2UhIFByb2NlZHVyYWxseSwgc29tZSBkbyAxMDIwMDAgdG8gYnVybiB0aGUgZmlyc3QgMjAwMCBhdXRvbWF0aWNhbGx5LiBEb24ndCB3b3JyeSBpZiBOQXMgYXJlIHByb2R1Y2VkLiBUaGlzIGlzIHVzdWFsbHkgZHVlIHRvIGdlbmVyYXRpbmcgaW1wb3NzaWJsZSBwcmlvciBwcmVkaWN0aXZlIHZhbHVlcy4gV2UnbGwgcHJvYmFibHkgbmV2ZXIgbmVlZCB0byB1c2UgdGhhdCBkaXN0cmlidXRpb24gYW55d2F5cy4KCmBgYHtyfQptY192YWwgPC0gbm9ybV9tY21jKDEwMDAwMCwgMjc4MDAwLCA0MDAwLCAuMDEsLjAxLCBzdWJzZXQoaHZpLGh2aSRTdGF0ZT09J01EJykkWmh2aSkKbGFwcGx5KG1jX3ZhbCwgaGVhZCkKYGBgCgojIyMgQnVybmluZywgdGhpbm5pbmcsIGFuZCBhc3Nlc3NpbmcgcGVyZm9ybWFuY2UKCkxldCdzIHRha2UgYSBsb29rIGF0IHNvbWUgdHJhY2VwbG90cyB0byBzZWUgaG93IG1hbnkgd2Ugd2lsbCBuZWVkIHRvIGJ1cm4uCgpgYGB7cn0KcGFyKG1mcm93ID0gYygxLDIpKQpwbG90KG1jX3ZhbCRgUG9zdGVyaW9yIHNpZzJgLCB0eXBlID0gJ2wnLCBjb2wgPSAicmVkIikKcGxvdChtY192YWwkYFBvc3RlcmlvciBtdWAsIHR5cGUgPSAnbCcsIGNvbCA9ICJibHVlIikKcGFyKG1mcm93ID0gYygxLDEpKQpgYGAKClRoZXNlIHRyYWNlcGxvdHMgc2hvdyBxdWljayBjb252ZXJnZW5jZS4gVGhlIHZhcmlhbmNlIGxvb2tlZCByYXRoZXIgaGVhbHRoeSBhbmQgY29udmVyZ2VkIGltbWVkaWF0ZWx5LiBGb3IgwrUsIHdlIGNhbiB0YWtlIGEgbG9vayBhdCB0aGUgZGF0YSB3aXRob3V0IHBsb3R0aW5nIGFuZCBub3RpY2UgdGhhdCB0aGVyZSBpcyBhIGh1Z2UganVtcCBpbiBtdSBmcm9tIDAgdG8gMTI5ODUxIHRoZW4gY29udmVyZ2VuY2Ugb24gdGhlIHRoaXJkIHZhbHVlLiBXZSB3aWxsIGJ1cm4gdGhlIGZpcnN0IDUwIGp1c3QgdG8gYmUgc2FmZS4gSWYgd2Ugc2VlIGEgbG90IG9mIG9zY2lsbGF0aW5nLCB0aGlzIG1lYW5zIHRoYXQgd2UgaGF2ZSBhIGhlYWx0aHkgbWFya292IGNoYWluCgo8aHI+CgpBcyBmb3IgdGhlIHRoaW5uaW5nLCB3ZSB3aWxsIG9ic2VydmUgQUNGIHBsb3RzLgoKYGBge3J9CnBhcihtZnJvdyA9IGMoMSwyKSkKYWNmKG1jX3ZhbCRgUG9zdGVyaW9yIHNpZzJgKQphY2YobWNfdmFsJGBQb3N0ZXJpb3IgbXVgKQpwYXIobWZyb3cgPSBjKDEsMSkpCmBgYAoKQm90aCBwbG90cyBzaG93IG5vIHNlcmlvdXMgY29ycmVsYXRpb24gaW4gYW55IG11bHRpcGxlIGZyb20gMS01MC4gVXN1YWxseSwgaWYgdGhlcmUgYXJlIGJhcnMgdGhhdCBleGNlZWQgdGhlIGJsdWUgbGluZXMsIGl0IG1lYW5zIHRoZXJlIGlzIGF1dG9jb3JyZWxhdGlvbi4gVGhlc2UgcGxvdHMgYXJlIGFsc28gdXNlZCBmb3IgdGltZS1zZXJpZXMgYW5hbHlzaXMuIFdlIHdpbGwga2VlcCBhbGwgb3VyIHZhbHVlcyBmb3IgdGhlIE1hcnlsYW5kIHBvc3RlcmlvcgoKYGBge3J9CiMgaWYgdGhlcmUgd2FzIGF1dG9jb3JyZWxhdGlvbiwgdXNlIHNvbWV0aGluZyBsaWtlIHRoaXMgdG8gZ3JhYiBldmVyeSAxMHRoLCBvciA1dGggb3Igd2hhdGV2ZXIgbXVsdGlwbGUKIyBzZXEoNTA6MTAwMDAwLCBieSA9IDUpWy0xXSByZW1vdmVzIGZpcnN0IDUwIGFuZCB0YWtlcyBldmVyeSA1dGggdmFsdWUuLi4KcmVtIDwtIGZ1bmN0aW9uKGRhdGEscmVtcykgZGF0YVstYygxOnJlbXMpXQptY192YWwgPC0gbGFwcGx5KG1jX3ZhbCwgZnVuY3Rpb24oeCkgcmVtKHgsIDUwKSkKYGBgCgo8aHI+CgpPdGhlciBhc3Nlc3NtZW50cyBhbmQgcGxvdHMgY2FuIGJlIG1hZGUgYXMgZm9sbG93czoKCjJEIHBlcnNwZWN0aXZlIHBsb3RzIHNob3cgdGhhdCB0aGVyZSBpcyBhIHJlbGF0aXZlbHkgc21hbGwgdmFyaWFuY2UuIFVzaW5nIEF6aW11dGggYW5nbGVzLCB5b3UgbWF5IG5hdmlnYXRlIHRocm91Z2ggdGhlIGxhdGVudCBzcGFjZS4KCmBgYHtyfQpwZXJzcChrZGUyZChtY192YWwkYFBvc3RlcmlvciBtdWAsIG1jX3ZhbCRgUG9zdGVyaW9yIHNpZzJgKSwgcGhpID0gLCA2NSx0aGV0YSA9IDYwLCB4bGFiID0gIsK1IiwgeWxhYiA9ICJzaWdtYV4yIikKYGBgCgpJbWFnZSBwbG90cyBnaXZlIHVzIGEgaGVhdCBtYXAgb2YgdGhlIHNhbWUgdGhpbmcgZnJvbSBhIGJpcmRzIGV5ZSB2aWV3LCBhIHJlbGF0aXZlbHkgcHJlY2lzZSB2YXJpYW5jZS4gQ29udG91ciBsaW5lcyBzaG93IHVzIHRoZSBaIGRpc3RyaWJ1dGlvbiBkZW5zaXR5LiBUaGlzIHdpbGwgbW9zdCBsaWtlbHkgZ2l2ZSB1cyBwb3N0ZXJpb3IgdmFsdWVzIHRoYXQgYXJlIGNsb3NlbHkga25pdC4KCmBgYHtyfQppbWFnZShrZGUyZChtY192YWwkYFBvc3RlcmlvciBtdWAsIG1jX3ZhbCRgUG9zdGVyaW9yIHNpZzJgKSkKY29udG91cihrZGUyZChtY192YWwkYFBvc3RlcmlvciBtdWAsIG1jX3ZhbCRgUG9zdGVyaW9yIHNpZzJgKSwgYWRkID0gVFJVRSkKbXRleHQoZXhwcmVzc2lvbihzaWdtYV4yKSwgc2lkZSA9MiwgbGluZSA9IDIuNSkKYGBgCgoKIyMjIENvbXBhcmluZyBkaXN0cmlidXRpb25zCgpOb3cgaGVyZSBjb21lcyB0aGUgcmVhbCBhbmFseXNpcy4gU2luY2Ugd2UgaGF2ZSA1IGRpZmZlcmVudCBzdGF0ZXMsIHRoZSBwcm9wZXIgYnVybmluZyBhbmQgdGhpbm5pbmcgd2lsbCBiZSBkb25lIHdpdGhvdXQgZXhwbGFuYXRpb24gYmVsb3cgKHR1cm5zIG91dCwgbm8gdGhpbm5pbmcgb3IgYnVybmluZyBpcyByZWFsbHkgdG9vIG5lY2Vzc2FyeS4gT3VyIGRhdGEgd2FzIHNvIHNtYWxsLCB0aGF0IGl0IGltbWVkaWF0ZWx5IGNvbnZlcmdlZCBhbmQgZGlkIG5vdCBhZmZlY3Qgb3VyIG1hcmtvdiBjaGFpbiB2ZXJ5IG11Y2guIFNvIG11Y2ggZm9yIGEgZnVuIGFuYWx5c2lzISkuCgpgYGB7cn0KaGlfdmFsIDwtIG5vcm1fbWNtYygxMDAwMDAsIDUwMDAwMCwgNDAwMCwgLjAxLC4wMSwgc3Vic2V0KGh2aSxodmkkU3RhdGU9PSdISScpJFpodmkpCmFrX3ZhbCA8LSBub3JtX21jbWMoMTAwMDAwLCAyNzgwMDAsIDQwMDAsIC4wMSwuMDEsIHN1YnNldChodmksaHZpJFN0YXRlPT0nQUsnKSRaaHZpKQptYV92YWwgPC0gbm9ybV9tY21jKDEwMDAwMCwgMjc4MDAwLCA0MDAwLCAuMDEsLjAxLCBzdWJzZXQoaHZpLGh2aSRTdGF0ZT09J01BJykkWmh2aSkKbWRfdmFsIDwtIG5vcm1fbWNtYygxMDAwMDAsIDI3ODAwMCwgNDAwMCwgLjAxLC4wMSwgc3Vic2V0KGh2aSxodmkkU3RhdGU9PSdNRCcpJFpodmkpCm5qX3ZhbCA8LSBub3JtX21jbWMoMTAwMDAwLCAyNzgwMDAsIDQwMDAsIC4wMSwuMDEsIHN1YnNldChodmksaHZpJFN0YXRlPT0nTkonKSRaaHZpKQpgYGAKCgpgYGB7cn0KaGlfdmFsIDwtIGxhcHBseShoaV92YWwsIGZ1bmN0aW9uKHgpIHJlbSh4LDUwKSkgOyBha192YWwgPC0gbGFwcGx5KGFrX3ZhbCwgZnVuY3Rpb24oeCkgcmVtKHgsNTApKQptYV92YWwgPC0gbGFwcGx5KG1hX3ZhbCwgZnVuY3Rpb24oeCkgcmVtKHgsNTApKSA7IG1kX3ZhbCA8LSBsYXBwbHkobWRfdmFsLCBmdW5jdGlvbih4KSByZW0oeCw1MCkpCm5qX3ZhbCA8LSBsYXBwbHkobmpfdmFsLCBmdW5jdGlvbih4KSByZW0oeCw1MCkpCmBgYAoKRGlzdHJpYnV0aW9uYWwgY3VydmVzIG1heSBiZSBjb21wYXJlZCBpbiBhIHBhcml3aXNlIG1hbm5lci4gVGhpcyBpcyB0aGUgYmVhdXR5IG9mIHVzaW5nIG1vbnRlLWNhcmxvIHNhbXBsaW5nLiBTaW5jZSB3ZSBhcmUgbG9va2luZyBhdCBtdWx0aXBsZSBjb21wYXJpc29ucyB3ZSB3aWxsIHN0YXJ0IGJ5IHBlcmZvcm1pbmcgYSBwc2V1ZG8gRi10ZXN0IChjb21wYXJpbmcgdGhlIHJhdGlvcyBvZiB0aGUgdmFyaWFuY2VzKS4gU2luY2UgdGhlcmUgYXJlIGNob29zZSg1LDIpID0gMTAgcG9zc2libGUgY29tYmluYXRpb25zLCB3ZSB3aWxsIG9ubHkgZ3JhYiB0aGUgbW9zdCBpbnRlcmVzdGluZyBsb29raW5nIG9uZXMuCgpgYGB7cn0KcGxvdChkZW5zaXR5KGhpX3ZhbCRgUG9zdGVyaW9yIHNpZzJgKSwgeGxpbSA9IGMoMCw4KjEwXjEwKSwgeWxpbSA9IGMoMCwgNyoxMF4tMTApKQpsaW5lcyhkZW5zaXR5KGFrX3ZhbCRgUG9zdGVyaW9yIHNpZzJgKSwgY29sID0gImJsdWUiKSA7IGxpbmVzKGRlbnNpdHkobWRfdmFsJGBQb3N0ZXJpb3Igc2lnMmApLCBjb2wgPSAicmVkIikKbGluZXMoZGVuc2l0eShual92YWwkYFBvc3RlcmlvciBzaWcyYCksIGNvbCA9ICJncmVlbiIpIDsgbGluZXMoZGVuc2l0eShtYV92YWwkYFBvc3RlcmlvciBzaWcyYCksIGNvbCA9ICJicm93biIpCmxlZ2VuZCgidG9wcmlnaHQiLCByZXAoMywxKSwgc3RhdGVfY29kZXMsIGMoInJlZCIsICJibHVlIiwgImdyZWVuIiwgImJyb3duIiwgImJsYWNrIikpCmBgYAoKSGF3YWlpIGlzIG5vdCBzaWduaWZpY2FudGx5IGxhcmdlciB0aGFuIGFueSBvZiB0aGUgb3RoZXIgc3RhdGVzIGJlY2F1c2UgdGhlIGludGVydmFscyBkb24ndCBjb250YWluIDEuIFRoaXMgd2lsbCBtZWFuIHRoYXQgdGhlIG5vbmUgb2YgdGhlIG90aGVyIGNvbXBhcmlzb25zIHdpbGwgeWllbGQgbXVjaCBvZiBhIGRpZmZlcmVuY2UuCgpgYGB7cn0KcXVhbnRpbGUoaGlfdmFsJGBQb3N0ZXJpb3Igc2lnMmAvbWRfdmFsJGBQb3N0ZXJpb3Igc2lnMmAsYyguMDI1LCAuOTc1KSkKcXVhbnRpbGUoaGlfdmFsJGBQb3N0ZXJpb3Igc2lnMmAvbmpfdmFsJGBQb3N0ZXJpb3Igc2lnMmAsYyguMDI1LCAuOTc1KSkKcXVhbnRpbGUoaGlfdmFsJGBQb3N0ZXJpb3Igc2lnMmAvYWtfdmFsJGBQb3N0ZXJpb3Igc2lnMmAsYyguMDI1LCAuOTc1KSkKcXVhbnRpbGUoaGlfdmFsJGBQb3N0ZXJpb3Igc2lnMmAvbWFfdmFsJGBQb3N0ZXJpb3Igc2lnMmAsYyguMDI1LCAuOTc1KSkKYGBgCgoKV2UgbWF5IHN1cm1pc2UgaGVyZSB0aGF0IEhhd2FpaSBpcyBOT1Qgc2lnbmlmaWNhbnR5IGRpZmZlcmVudCBmcm9tIHRoZSByZXN0IG9mIHRoZSBzdGF0ZXMuIEhPV0VWRVIsIHRoZXJlIGlzIGEgcHJhY3RpY2FsIHNpZ25pZmljYW5jZSBoZXJlLiBIYXdhaWlhbiBob21lcyBvbiBhdmVyYWdlIGFyZSAyMjIsMDAwIGRvbGxhcnMgbGFyZ2VyIG9uIGF2ZXJhZ2UgdGhhbiBNYXJ5bGFuZCBob21lcy4gVGhpcyBpcyBub3QgYSB0cml2aWFsIGRpZmZlcmVuY2UuCgpgYGB7cn0KcXVhbnRpbGUoaGlfdmFsJGBQb3N0ZXJpb3IgbXVgIC0gbWRfdmFsJGBQb3N0ZXJpb3IgbXVgLGMoLjAyNSwgLjk3NSkpCmBgYAoKUG9zdGVyaW9yIHByb2JhYmlsaXRpZXMgbWF5IGFsc28gYmUgZGlzY292ZXJlZC4KCmBgYHtyfQptZWFuKG5qX3ZhbCRgUG9zdGVyaW9yIG11YCA8IDI3OCoxMF4zKQpgYGAKClRoZSBwb3N0ZXJpb3IgcHJvYmFiaWxpdHkgb2Ygb2JzZXJ2aW5nIGEgaG9tZSBpbiBOZXcgSmVyc2V5IHRoYXQgY29zdHMgbGVzcyB0aGFuIDI3OGsgaXMgY2xvc2UgdG8gNTAlLiBUaGVzZSB0aWdodCBkaXN0cmlidXRpb25zIGFyZSBtb3N0IGxpa2VseSBkdWUgdG8gaGF2aW5nIG5vdCBlbm91Z2ggZGF0YSB0byBpbmZlcmVuY2Ugb2ZmIG9mLiAKCiMjIyBQb3N0ZXJpb3IgUHJlZGljdGl2ZSAKClByZWRpY3RpdmUgZGlzdHJpYnV0aW9ucyB3ZXJlIGFsc28gaW5jbHVkZWQgaW4gdGhlIGZvcm11bGEuIFRoZXNlIHByZWRpY3RpdmVzIGhhdmUgYSBzdXBwb3J0IGZyb20gKC1pbmYsaW5mKSBzbyBpdCBtaWdodCBiZSBub3JtYWwuIFRoZSBkaXN0cmlidXRpb24gaXMgbGFyZ2VyIHRoYW4ganVzdCB0aGUgcG9zdGVyaW9yLi4gVGhlIHBvc3RlcmlvciBwcmVkaWN0aXZlIHByb2JhYmlsaXR5IG9mIHRoZSBuZXh0IGhvbWUgaW4gQWxhc2thIGJlaW5nIGxhcmdlciB0aGFuIDMwMGsgaXMgYmVsb3c6CgoKYGBge3J9Cm1lYW4obmpfdmFsJGBwb3N0LXByZWRgPjMwMCoxMF4zKQpgYGAKCiMjIyBDb25jbHVzaW9uCgpPdmVyYWxsLCB0aGlzIGFuYWx5c2lzIHdhcyB2ZXJ5IHNpbXBsZS4gVGhlcmUgYXJlIDQga2V5IHRha2Vhd2F5czoKCiAgMSkgQmVzdCB0byBoYXZlIGRhdGEgdGhhdCBpcyBhcyBub3JtYWxseSBkaXN0cmlidXRlZCBhcyBwb3NzaWJsZQogIDIpIFRoZSBwb3N0ZXJpb3IgZGlzdHJpYnV0aW9uIHJlYWxseSBtYWRlIGEgbGFyZ2UgZWZmZWN0IG9uIHRoZSBvdXRjb21lcyBvZiBvdXIgbW9kZWwKICAzKSBEYXRhIHN1ZmZpY2llbmN5IGlzIHZlcnkgaW1wb3J0YW50LiBPdXIgb3ZlcmFsbCBwb3N0ZXJpb3Igd2FzIHZlcnkgdGlnaHQga25pdCBjbG9zZSB0byB0aGUgZGF0YS4KICA0KSBBbHdheXMgcmVtZW1iZXIgd2hlcmUgdGhlIGRhdGEgY29tZXMgZnJvbS4gVGhpcyBpcyBhIHJlcHJlc2VudGF0aXZlIHNhbXBsZSBvZiB6aWxsb3cgaG9tZSBzZWxsZXJzLgoKVGhlcmUgYXJlIHNvIG1hbnkgYXNzdW1wdGlvbnMgdG8gYmUgbWFkZSB3aGlsZSB3b3JraW5nIHdpdGggc2ltdWxhdGlvbiBtb2RlbHMuIEhvd2V2ZXIsIHRoZXJlIGFyZSBzbyBtYW55IGJlbmVmaXRzIGFzIHdlbGwhIE1vZGVsbGluZyBoZWlhcmNoaWNhbCBtb2RlbHMgbWF5IGJlIGFwcGxpZWQgaW4gdmFyaW91cyBzZXR0aW5ncyAobWFya2V0aW5nLCBzdXBwbHktY2hhaW4sIG1hY2hpbmUgbGVhcm5pbmcsIGV0YykuIEtub3dpbmcgdGhlIGJhc2ljcyBkZWZpbml0ZWx5IHBheXMgb2ZmLiBHbyB0cnkgdGhpcyB3aXRoIGEgbmV3IGRhdGFzZXQhCgoKCg==