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:

  1. Maryland
  2. Alaska
  3. New Jersey
  4. Massachusetts
  5. Hawaii
  6. Connecticut
  7. New Hampshire
  8. Virginia
  9. California
  10. 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           <int> 102001, 394913, 753899, 394463, 394514, 394974, 394692, 395209, 394856, 394347…
$ Date               <date> 2019-02-28, 2019-02-28, 2019-02-28, 2019-02-28, 2019-02-28, 2019-02-28, 2019-…
$ RegionName         <chr> "United States", "New York, NY", "Los Angeles-Long Beach-Anaheim, CA", "Chicag…
$ State              <chr> NA, "NY", "CA", "IL", "TX", "PA", "TX", "DC", "FL", "GA", "MA", "CA", "MI", "C…
$ SizeRank           <int> 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, …
$ Zhvi               <int> 226300, 440400, 652200, 225300, 244400, 233500, 206300, 406800, 284700, 218600…
$ MoM                <dbl> 0.0031028369, 0.0034176350, -0.0007660487, 0.0022241993, 0.0057613169, 0.00300…
$ QoQ                <dbl> 0.014343344, 0.010555301, 0.001228124, 0.010313901, 0.025167785, 0.009948097, …
$ YoY                <dbl> 0.07200379, 0.04707561, 0.02466614, 0.03491043, 0.09990999, 0.03501773, 0.0628…
$ `5Year`            <dbl> 0.06522199, 0.04517718, 0.06177574, 0.05122774, 0.10537396, 0.03851077, 0.0741…
$ `10Year`           <dbl> 0.027220895, 0.012722285, 0.040997305, 0.003806871, 0.053739509, 0.006431629, …
$ PeakMonth          <chr> "2019-02", "2006-07", "2019-01", "2007-02", "2019-02", "2007-05", "2019-02", "…
$ PeakQuarter        <chr> "2019-Q1", "2006-Q3", "2019-Q1", "2007-Q1", "2019-Q1", "2007-Q2", "2019-Q1", "…
$ PeakZHVI           <int> 226300, 452800, 652700, 254100, 244400, 237300, 206300, 435400, 311600, 218600…
$ PctFallFromPeak    <dbl> 0.0000000000, -0.0273851590, -0.0007660487, -0.1133412043, 0.0000000000, -0.01…
$ LastTimeAtCurrZHVI <chr> "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::

  1. Ask an expert what they believe to be the mean and standard deviation.
  2. Use a time-series analysis for data per state, pick a reasonable point estimate
  3. Do a regression analysis on income and housing prices. Predict a typical value of income for home.
  4. 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).

X Hawaii Alaska Massachusetts Maryland New Jersey
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:

  1. 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.
  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

  1. 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

  1. The new µj and σ2j values are the posterior distributions!
  2. Predictive distributions may be chosen by generating random samples of from either the posterior or prior.
  1. 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:

  1. Best to have data that is as normally distributed as possible
  2. The posterior distribution really made a large effect on the outcomes of our model
  3. Data sufficiency is very important. Our overall posterior was very tight knit close to the data.
  4. 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==