General notes on testing in statistics


N = 10000
p_1 = rnorm(n=N,mean=0,sd=1)
p_2 = rnorm(n=N,mean=2,sd=1)
# number of samples
n_samples = 100
# number of times
n_times = 1000

# compute the mean difference an store them in the container below
container = c()

for(k in 1:n_times){
  # draw samples from the populations
  X_1 = sample(p_1,n_samples)
  X_2 = sample(p_2,n_samples)
  # compute their mean difference and store in container 
  container[k] = mean(X_2)-mean(X_1)
}
hist(container,col='gray')

container = c()

for(k in 1:n_times){
  # draw samples from the populations
  X_11 = sample(p_1,n_samples)
  X_12 = sample(p_1,n_samples)
  # compute their mean difference and store in container
  container[k] = mean(X_11)-mean(X_12)
}
hist(container,col='gray')

# count the number of times the difference was exactly zero
sum(container == 0)
[1] 0

Now when statisticians says the null \(\bar X_1 - \bar X_2=0\), it means that under this null assumption the we expect the distribution of the difference to be the second histogram above, i.e., center around zero. Lets compare the second histogram (a histogram constructed under the null) to a normal distribution

qqnorm(container)
qqline(container)

Ok it seems like it the null hypothesis is true, the null distribution (the histogram centered at zero) is normal. We know the mean of the null distribution is zero. What is it standard deviation. To avoid answering that question, instead of looking at \(z_1 =\bar X_1 - \bar X_2\) (\(z_1\) is the test statistics) we could look at \[ z_2 = \frac{\bar X_1 - \bar X_2}{\text{std}(\bar X_1 - \bar X_2)} \] \(z_2\) is a normalised test statistic and \(\text{std}(z_2)=1\)

z_1 = c()
z_2 = c()
for(k in 1:n_times){
  # draw samples from the populations
  X_11 = sample(p_1,n_samples)
  X_12 = sample(p_1,n_samples)
  # compute their mean difference and store in container
  z_1[k] = mean(X_11)-mean(X_12)
}
z_2 = z_1/sd(z_1)
hist(z_1,col='gray',xlim = c(-4,4))
hist(z_2,add=TRUE,col=rgb(0,0,0.5,0.3))

So we could now conlude that the distribution of \(z_2\) is standard normal. So we are saying that under the null hypothesis, the distribution of \(z_2\) is a standard normal distribution. Is this always true?

Questions 1.

Write two functions twosample.t(X1, X2, n.perm) and paired.t(X1,X2, n.perm) that return the permutation p-value of a two-sided twosample t-test and a two-sided paired t-test based on n.perm permutations. You should implement this test yourself, so don’t use a test from e.g. the coin package. As your answer to this question, copy-paste the (readable) R code of these two functions so that we can check your implementation.

  • Very important: note that twosample.t(X1, X2, n.perm) and paired.t(X1,X2, n.perm) have NOTHING to do with a \(t\)-test. Please don’t be confuse with the .t in the function names. This can be misleading I know, the .t in the names simply means they are tests.

Solution

# two samples 
#_______
# pool samples
# draw two groups from pooled sample  without replacement
# compute difference between their means 
# compare with observed

twosample.t= function(X1,X2,n.perm){
  len = length(X1)
  # observed value 
  obs = mean(X1)-mean(X2)
  # pooled samples,under the null it does not matter where the sample belongs
  X = c(X1,X2)
  # their indices
  index = seq(1,2*len)


  statistics = c()
  for(i in 1:n.perm){
    # sample the indices, it does not matter which sample was the observation 
    # came from
    index_sample_1 = sample(index,len,replace = FALSE)
    index_sample_2 = index[!(index %in% index_sample_1)]
    statistics[i] = mean(X[index_sample_1])-mean(X[index_sample_2])
  }
  # proportions of test statistics below obs
  p_value = sum(abs(statistics)>abs(obs))/n.perm
  # p_value = ifelse(p_value>0.5,1-p_value,p_value)
  return(p_value)
}


# compute X1-X2
# switch their signs randomly
# compute mean of difference
# compare with the observed value

paired.t= function(X1,X2,n.perm){
  len = length(X1)
  # observed value 
  obs = mean(X1)-mean(X2)

  statistics = c()
  for(i in 1:n.perm){
    signs = sample(c(1,-1),len,replace = TRUE)
    
    # change sign of difference  randomly it does not matter which measurement was done 
    # first, this what the null hypothesis says
    
    statistics[i] = mean((X1-X2)*signs)
  }

  # proportions of test statistics below obs
  p_value = sum(abs(statistics)>abs(obs))/n.perm
  # p_value = ifelse(p_value>0.5,1-p_value,p_value)
  return(p_value)
}

# play with the two tests change the means of X1 and X2 and see what happens
N<-100
n.perm = 1000
X1 = rnorm(N,mean=2,sd=2)
X2 = rnorm(N,mean=2.3,sd=2)
paired.t(X1,X2,n.perm=n.perm)
[1] 0.201
twosample.t(X1,X2,n.perm=n.perm)
[1] 0.173

Question 2

Write a function simulate.data(n, delta, correlation) that simulates \(n\) paired observations (so the total number of observations is \(2n\)), say

X1 and X2, from a skewed distribution where E[X1]−E[X2] = delta. The parameter correlation can take on a number from 1 to 5 and is related to the strength of the correlation. More specifically, correlation = 1 should correspond to cor(X1, X2) = 0, correlation = 2 to cor(X1, X2) = 0.1, correlation = 3 to cor(X1, X2) = 0.25, correlation = 4 to cor(X1, X2) = 0.5 and correlation = 5 to cor(X1, X2) = 0.7. Note that many parameters are left free in this function (e.g. the marginal means

and variances - you can choose the values yourself for this). As your an- swer to this question, copy-paste the (readable) R code of this function.

Tip: you might want to examine the code below to get inspiration on how you can simulate correlated skewed bivariate data. Note that cor below will not exactly equal cor(X1, X2), so you will have to fine tune this. You can do this be setting \(n\) to a large number (e.g. 10000) and see what the sample correlation is (which will be very close to cor(X1, X2) because \(n\) is large) for a choice of cor. It is not mandatory to use this code.

library(mvtnorm)
n <- 100000
cor <- .1
Y <- rmvnorm(n, mean = c(0,2),sigma = matrix(nrow = 2, ncol = 2, c(1, cor, cor, 1)))

cov(Y)
           [,1]       [,2]
[1,] 0.99953182 0.09751816
[2,] 0.09751816 1.00656266
Z <- pnorm(Y) # standard normal 

X1 <- qexp(Z[,1])
X2 <- qexp(Z[,2])




cor_data = data.frame(correlation=c(1:5),cor=c(0,0.1,0.25,0.5,0.7))

simulate.data=function(n, delta, correlation){
  cor = cor_data[correlation,2]
  Y <- rmvnorm(n, mean = c(0,delta),sigma = matrix(nrow = 2, ncol = 2, c(1, cor, cor, 1)))
  Z <- pnorm(Y) # standard normal
  X1 <- qexp(Z[,1])
  X2 <- qexp(Z[,2])
  data.frame(X1,X2)
}

Create a graph where you plot the empirical type I and type II error for each test as a function of the correlation where the correlation takes on the values 0, 0.1, 0.25, 0.5 and 0.7 and for \(\alpha\) = 5%. Here \(n\) should be equal to \(5\) (mimicking a very small sample) and to 100 (mimicking a larger sample) and you can choose the number of permutations and Monte-Carlo simulations yourself (the higher the better, but higher also means computationally more intensive, so there is a trade-off). In your answer to this question you should only include two plots: one for n = 5 and one for n = 100 each with 4 curves (for both errors and for both tests) - this plot should be readable in black-and-white and please provide an informative caption. Make sure that when you simulate data under \(H_A\) the type II error is not too close to zero or one (because then it is hard to compare the methods - the delta is allowed to be different when n = 5 and when n = 100).

## 1) state the type I and II errors
## 2) simulate data with null hypothesis true
## 3) simulate data with null hypothesis false
## set n = 5 
## set n = 100
## set delta for n = 5 and 100



alpha = 0.05
B = 100
n.perm = 1000

paired_con = c()
twosample_con = c()

# containers for n=5 type I and type II
error_type_I = data.frame(matrix(NA,nrow=2,ncol = 5))
error_type_II = data.frame(matrix(NA,nrow=2,ncol = 5))

rownames(error_type_I) = c('type_I_paired','type_I_twosample')
colnames(error_type_I)= paste('correlation_',seq(1,5))

rownames(error_type_II) = c('type_II_paired','type_II_twosample')
colnames(error_type_II)= paste('correlation_',seq(1,5))




# our simulation and plot function
correlations = c(1:5)
all_sim = function(n,delta){
for(j in 1:length(correlations)){
    for(b in 1:B){
      data = simulate.data(n=n,delta=0,correlation=correlations[j])
      paired_con[b] = paired.t(X1=data$X1,X2=data$X2,n.perm = n.perm)<=alpha
      twosample_con[b] = twosample.t(X1=data$X1,X2=data$X2,n.perm = n.perm)<=alpha
    }
    error_type_I[1,j] =  sum(paired_con)/B
    error_type_I[2,j] =  sum(twosample_con)/B
}
#type II 
for(j in 1:length(correlations)){
    for(b in 1:B){
      data = simulate.data(n=n,delta=delta,correlation=correlations[j])
      paired_con[b] = paired.t(X1=data$X1,X2=data$X2,n.perm = n.perm)>alpha
      twosample_con[b] = twosample.t(X1=data$X1,X2=data$X2,n.perm = n.perm)>alpha
    }
    error_type_II[1,j] =  sum(paired_con)/B
    error_type_II[2,j] =  sum(twosample_con)/B
}

corr_ = c(0,0.1,0.25,0.5,0.7)
ylimits = c(min(error_type_I,error_type_II),max(error_type_I,error_type_II))
plot(
  x = corr_,
  y = error_type_I[1, ],
  type = 'b',
  main = paste('n = ',n, 'type I and II error rates'),
  xlab = 'correlations',
  ylab = 'Error rate',
  ylim = ylimits,
  lty=1,
  pch = 1
)
lines(x = corr_,
      y = error_type_I[2, ],
      type = 'b',
      lty = 2,
      pch=2)
lines(
  x = corr_,
  y = error_type_II[1, ],
  type = 'b',
  lty = 3,
  pch = 3
)
lines(
  x = corr_,
  y = error_type_II[2, ],
  type = 'b',
  lty = 4,
  pch = 4
)
legend("topright",
       legend = c('Paired type I', 'two_sample type I','Paired type II', 'two_sample type II'),
       lty = c(1, 2,3,5),pch=c(1,2,3,4))
}
all_sim(n=5,delta=2)

What do you conclude for n=5, two sample test seems to perform better with small samples?.

set.seed(100)
all_sim(n=100,delta = 0.35)

observations

  • Generally errors seem to drop with increasing correlation
  • What can you say about the paired and two sample tests perfomance for type I and type II error rates?
  • It seems like the paired test has an edge over the two sample for the type II error rates?

Question 5

We now turn to confidence intervals and we are first interested in some analytical results.

  • Work out the expectation and variance of the sample mean difference \(\bar X_1\)\(\bar X_2\) assuming a) independence and b) dependence between \(X_1\) and \(X_2\). Tip: for at least one of the two scenarios the solution can be found in the course notes on hypothesis testing.
  1. Use the above expressions to write down the formula of an \((1 − \alpha) ×100\%\) confidence interval for \(E [X_1] − E [X_2]\) assuming a) independence and b) dependence between \(X_1\) and \(X_2\). When deriving the

confidence intervals, you can assume that the variables are normally distributed or you can rely on large-sample approximations.

Solution

  1. independence Let \(\sigma_1^2\) and \(\sigma_2^2\) be the variances of \(X_1\) and \(X_2\) respectively then and per the requirements of the problem at hand the sample size is \(n\) for both groups then: \[ E(\bar X_1 - \bar X_2) = \bar X_1-\bar X_2 \] \[ \text{Var}(\bar X_1 - \bar X_2) = \text{Var}(\bar X_1)+\text{Var}(\bar X_2) = \frac{ \sigma^2_1}{n}+\frac{\sigma^2_2}{n} = \frac{ \sigma_1^2+\sigma_2^2}{n} \]
  2. dependence

\[ E(\bar X_1 - \bar X_2) = \bar X_1-\bar X_2 \] \[ \text{Var}(\bar X_1 - \bar X_2) = \frac{ \sigma_1^2+\sigma_2^2}{n}-2\text{Cov}(\bar X_1,\bar X_2) \] b) Independence \[ Z = \frac{\bar X_1-\bar X_2}{\sqrt{\frac{ \sigma_1^2+\sigma_2^2}{n}}}\sim N(0,1) \]

\(\alpha\)% confidence is \[ \Phi^{-1}(\frac{\alpha}{2})\leq Z\leq \Phi^{-1}(1-\frac{\alpha}{2}) \]

where \(\Phi(.)\) is the cummulative normal distribution function. or \[ \sqrt{\frac{\sigma_1^2+\sigma_2^2}{n}}\Phi^{-1}(\frac{\alpha}{2})\leq \bar X_1-\bar X_2\leq \Phi^{-1}(1-\frac{\alpha}{2}) \sqrt{\frac{\sigma_1^2+\sigma_2^2}{n}} \] \[ \left[(\bar X_1-\bar X_2)+\sqrt{\frac{\sigma_1^2+\sigma_2^2}{n}}\Phi^{-1}(\frac{\alpha}{2}), ( \bar X_1-\bar X_2)+\Phi^{-1}(1-\frac{\alpha}{2}) \sqrt{\frac{\sigma_1^2+\sigma_2^2}{n}}\right] \] b) Dependence \[ Z = \frac{\bar X_1-\bar X_2}{\sqrt{\frac{ \sigma_1^2+\sigma_2^2-2\text{Cov}(\bar X_1,\bar X_2)}{n}}}\sim N(0,1) \]

Derive the confidence interval in a similar way as above.

Question 6

Simulate data under \(H_0\) or \(H_A\) (you can choose and you can reuse the code from the previous questions) for n = 100 and compute the empirical coverage and average width of a \(95\%\) confidence interval for E [X1]−E [X2]

(using the two confidence intervals you have derived in the previous ques- tion - so you implement these confidence intervals in R yourself). Make

two graphs: one with the empirical coverage as a function of the correla- tion and one with the average width as a function of the correlation where the correlation takes on the values 0, 0.1, 0.25, 0.5 and 0.7.

## coverage = proportion of times the true value is in the confidence interval
## length of CI = max-min 



## Important note 
## Note that the data  from our sample function has been transformed so a delta = 0
## correponds to a specific value in the transformed scale we set the sample size very 
## large to see the corresponding value 
n <- 1000000
cor <- .1
Y <- rmvnorm(n, mean = c(0,0),sigma = matrix(nrow = 2, ncol = 2, c(1, cor, cor, 0)))
sigma is numerically not positive semidefinite
Z <- pnorm(Y) # standard normal 

X1 <- qexp(Z[,1])
X2 <- qexp(Z[,2])

trans_delta = round(mean(X2)-mean(X1),2)
#the correponding value is -0.3 round to 2 dp


n = 100 
alpha = 0.05
delta = 1





coverage_dep = c()
coverage_ind = c()

length_dep = c()
length_ind = c()

for(j in 1:length(correlations)){
    len_dep = c()
    len_ind = c()
    
    cove_dep = c()
    cove_ind = c()
    for(b in 1:B){
      data = simulate.data(n=n,delta=0,correlation=correlations[j])
      v1 = var(data$X1)
      v2 = var(data$X2)
      
      deltahat = mean(data$X2) - mean(data$X1)
      term_ind = sqrt((v1+v2)/n)*qnorm(1-(alpha/2))
      term_dep = sqrt((v1+v2-2*cov(data$X1,data$X2))/n)*qnorm(1-alpha/2)
      
      # compute 
      
      lb_ind = deltahat-term_ind
      up_ind = deltahat+term_ind
      
      lb_dep = deltahat-term_dep
      up_dep = deltahat+term_dep
      
      len_ind[b] = up_ind-lb_ind
      len_dep[b] = up_dep-lb_dep
      
      cove_ind[b]= lb_ind <= trans_delta & trans_delta<=up_ind
      cove_dep[b]= lb_dep <= trans_delta & trans_delta<=up_dep

    }
    coverage_dep[j] = sum(cove_dep)/B
    coverage_ind[j] = sum(cove_ind)/B
    
    length_dep[j] = mean(len_dep)
    length_ind[j] = mean(len_ind)
}


corr_ = c(0,0.1,0.25,0.5,0.7)
ylimits = c(min(coverage_dep,coverage_ind),max(coverage_dep,coverage_ind))
plot(x = corr_,y = coverage_dep,type = 'b',
     xlab = 'correlations',ylab = 'Coverage',ylim = ylimits,
  lty=1,pch = 1
)
lines(x = corr_,y = coverage_ind,type = 'b',lty = 2,pch=2)

### add a legend
corr_ = c(0,0.1,0.25,0.5,0.7)
ylimits = c(min(length_dep,length_ind),max(length_dep,length_ind))
plot(x = corr_,y = length_dep,type = 'b',
     xlab = 'Correlation',ylab = 'average width',ylim = ylimits,
  lty=1,pch = 1
)
lines(x = corr_,y = length_ind,type = 'b',lty = 2,pch=2)

LS0tCnRpdGxlOiAiUHJpbnN0YXRzIGhvbWV3b3JrIDIiCm91dHB1dDogaHRtbF9ub3RlYm9vawotLS0KCgoKCiMgR2VuZXJhbCBub3RlcyBvbiB0ZXN0aW5nIGluIHN0YXRpc3RpY3MKKiBsZXQgc2F5IHdlIGhhdmUgdHdvIHBvcHVsYXRpb25zICRcbWF0aGNhbHtQfV8xJCBhbmQgJFxtYXRoY2Fse1B9XzIkCiogd2UgdGFrZSB0d28gc2FtcGxlcyAkWF8xJCBhbmQgJFhfMiQgIHdpdGggc2FtcGxlIG1lYW5zICRcYmFyIFhfMSQgYW5kICRcYmFyIFhfMiQgcmVzcGVjdGl2ZWx5IGZyb20gJFxtYXRoY2Fse1B9XzEkIGFuZCAkXG1hdGhjYWx7UH1fMiQKKiBnb2FsIGlzIHRvIHRlc3QgaWYgdGhlcmUgaXMgYSBkaWZmZXJlbmNlIGJldHdlZW4gICRcYmFyIFhfMSQgYW5kICRcYmFyIFhfMiQKKiBub3RlIHRoYXQgaW4gbW9zdCBjYXNlcywgaWYgbm90IGFsbCwgJFxiYXIgWF8xIFxuZXEgXGJhciBYXzIkLiAKTGV0cyBkbyB0aGlzIGluIFIgYW5kIHNlZS4KCmBgYHtyfQoKTiA9IDEwMDAwCnBfMSA9IHJub3JtKG49TixtZWFuPTAsc2Q9MSkKcF8yID0gcm5vcm0obj1OLG1lYW49MixzZD0xKQpgYGAKKiBsZXRzIGtlZXAgZHJhd2luZyBzYW1wbGVzIG9mIGVxdWFsIHNpemUgZnJvbSB0aGUgdHdvIHBvcHVsYXRpb25zIHdpdGggdGhlIGBzYW1wbGUoKWAgZnVuY3Rpb24gaW4gYFJgLiBXZSB3aWxsIGRyYXcgc2FtcGxlcyBvZiBzaXplIDEwMCBmcm9tIGVhY2ggcG9wdWxhdGlvbiBhbmQgY29tcHV0ZSB0aGVpciBtZWFucyBhbmQgY2hlY2sgaWYgdGhleSBhcmUgZXF1YWwuIFdlIHdpbGwgZG8gdGhpcyAxMDAwIHRpbWVzLgpgYGB7cn0KIyBudW1iZXIgb2Ygc2FtcGxlcwpuX3NhbXBsZXMgPSAxMDAKIyBudW1iZXIgb2YgdGltZXMKbl90aW1lcyA9IDEwMDAKCiMgY29tcHV0ZSB0aGUgbWVhbiBkaWZmZXJlbmNlIGFuIHN0b3JlIHRoZW0gaW4gdGhlIGNvbnRhaW5lciBiZWxvdwpjb250YWluZXIgPSBjKCkKCmZvcihrIGluIDE6bl90aW1lcyl7CiAgIyBkcmF3IHNhbXBsZXMgZnJvbSB0aGUgcG9wdWxhdGlvbnMKICBYXzEgPSBzYW1wbGUocF8xLG5fc2FtcGxlcykKICBYXzIgPSBzYW1wbGUocF8yLG5fc2FtcGxlcykKICAjIGNvbXB1dGUgdGhlaXIgbWVhbiBkaWZmZXJlbmNlIGFuZCBzdG9yZSBpbiBjb250YWluZXIgCiAgY29udGFpbmVyW2tdID0gbWVhbihYXzIpLW1lYW4oWF8xKQp9CmBgYAoKKiBsZXRzIG1ha2UgYSBoaXN0b2dyYW0gd2l0aCB0aGUgcmVzdWx0cyAgaW4gdGhlIGNvbnRhaW5lcgpgYGB7cn0KaGlzdChjb250YWluZXIsY29sPSdncmF5JykKYGBgCgoqIG9rLCB3ZSBzZWUgdGhhdCBlYWNoIHRpbWUgd2UgZHJhdyBhIHNhbXBsZSBmcm9tIHRoZSBwb3B1bGF0aW9ucyB3ZSBnZW5lcmF0ZSBhIG5ldyBtZWFuIGRpZmZlcmVuY2UgCiogdGhlIGhpc3RvZ3JhbSBhYm92ZSBzYXlzIHRoZSBtZWFuIG9mIHRoZSBkaWZmZXJlbmNlcyBpbiBtZWFuIGlzIGNlbnRlcmVkIHNvbWV3aGVyZSBhcnJvdW5kIDIuCiogbGV0cyBkcmF3IHR3byBzYW1wbGVzIGZyb20gdGhlIHNhbWUgcG9wdWxhdGlvbiBhbmQgc2VlIHdoYXQgd2lsbCBoYXBwZW4gCmBgYHtyfQpjb250YWluZXIgPSBjKCkKCmZvcihrIGluIDE6bl90aW1lcyl7CiAgIyBkcmF3IHNhbXBsZXMgZnJvbSB0aGUgcG9wdWxhdGlvbnMKICBYXzExID0gc2FtcGxlKHBfMSxuX3NhbXBsZXMpCiAgWF8xMiA9IHNhbXBsZShwXzEsbl9zYW1wbGVzKQogICMgY29tcHV0ZSB0aGVpciBtZWFuIGRpZmZlcmVuY2UgYW5kIHN0b3JlIGluIGNvbnRhaW5lcgogIGNvbnRhaW5lcltrXSA9IG1lYW4oWF8xMSktbWVhbihYXzEyKQp9Cmhpc3QoY29udGFpbmVyLGNvbD0nZ3JheScpCmBgYAoKKiB3ZSBub3cgc2VlIHRoYXQgZXZlbiB0aG91Z2ggdGhlIHR3byBzYW1wbGVzIGFyZSBmcm9tIHRoZSB0aGUgc2FtZSBwb3B1bGF0aW9uICRcYmFyIFhfezF9JCBpcyBub3QgZXF1YWwgJFxiYXIgWF8yJCBhbGwgdGhlIHRpbWUgLCBpLmUuLCAkXGJhciBYXzEgLSBcYmFyIFhfMiBcbmVxIDAkIGFsbCB0aGUgdGltZSwgYnV0IHRoZSBkaWZmZXJlbmNlIGlzIHZlcnkgY2xvc2UgdG8gemVybyB0aG91Z2guIEluZmFjdCAkXGJhciBYXzEgLSBcYmFyIFhfMiBcbmVxIDAkIGFsbCB0aGUgdGltZSwgd2UgY2FuIGNoZWNrIHRoaXMgaW4gY29kZS4KYGBge3J9CiMgY291bnQgdGhlIG51bWJlciBvZiB0aW1lcyB0aGUgZGlmZmVyZW5jZSB3YXMgZXhhY3RseSB6ZXJvCnN1bShjb250YWluZXIgPT0gMCkKYGBgCgoqIGFjdHVhbGx5ICRcYmFyIFhfMSAtIFxiYXIgWF8yIFxuZXEgMCQgYWxsIHRoZSB0aW1lCiogc28gd2hhdCBkbyBzdGF0aXN0aWNpYW5zIHJlYWxseSBtZWFuIHdoZW4gdGhleSBzYXkgIGNoZWNrIGlmICRcYmFyIFhfMSAtIFxiYXIgWF8yPTAkPyAKKiBzdGF0aXN0aWNpYW5zIHdpbGwgb2Z0ZW4gZm9ybXVsYXRlIHRoZSBwcm9ibGVtIGluIHRlcm1zIG9mIGEgbnVsbCBhbmQgYWx0ZXJuYXRpdmUgaHlwb3RoZXNpcy4KKiB0aGUgbnVsbCBoeXBvdGhlcnNpcyBpcyBmb3JtdWxhdGVkIGFzOiAkWF8xJCBhbmQgJFhfMiQgY29tZSBmcm9tIHRoZSBzYW1lIHBvcHVsYXRpb24sIGFuZCBvZnRlbiB0aGUgcHJvYmxlbSBpcyBzaW1wbGlmaWVkIHRvIHNheWluZyB0aGF0ICAkXGJhciBYXzEgID0gXGJhciBYXzI9MCQgb3IgJFxiYXIgWF8xIC0gXGJhciBYXzI9MCQuCiogdGhlIGFsdGVuYXRpdmUgaHlwb3RoZXNpcyAgaXMgdGhlIGNvbnZlcnNlIChzb21ldGltZXMgbm90IGEgY29tcGxldGUgY29udmVyc2UpIG9mIHRoZSBudWxsLCBpLmUuLCAkXGJhciBYXzEgLSBcYmFyIFhfMlxuZXEgMCQKCk5vdyB3aGVuIHN0YXRpc3RpY2lhbnMgc2F5cyB0aGUgbnVsbCAkXGJhciBYXzEgLSBcYmFyIFhfMj0wJCwgaXQgbWVhbnMgdGhhdCB1bmRlciB0aGlzIG51bGwgYXNzdW1wdGlvbiB0aGUgd2UgZXhwZWN0IHRoZSBkaXN0cmlidXRpb24gb2YgdGhlIGRpZmZlcmVuY2UgdG8gYmUgdGhlIHNlY29uZCBoaXN0b2dyYW0gYWJvdmUsIGkuZS4sIGNlbnRlciBhcm91bmQgemVyby4gTGV0cyBjb21wYXJlIHRoZSBzZWNvbmQgaGlzdG9ncmFtIChhIGhpc3RvZ3JhbSBjb25zdHJ1Y3RlZCB1bmRlciB0aGUgbnVsbCkgdG8gYSBub3JtYWwgZGlzdHJpYnV0aW9uCmBgYHtyfQpxcW5vcm0oY29udGFpbmVyKQpxcWxpbmUoY29udGFpbmVyKQpgYGAKCk9rIGl0IHNlZW1zIGxpa2UgaXQgdGhlIG51bGwgaHlwb3RoZXNpcyBpcyB0cnVlLCB0aGUgbnVsbCBkaXN0cmlidXRpb24gKHRoZSBoaXN0b2dyYW0gY2VudGVyZWQgYXQgemVybykgaXMgbm9ybWFsLiBXZSBrbm93IHRoZSBtZWFuIG9mIHRoZSBudWxsIGRpc3RyaWJ1dGlvbiBpcyB6ZXJvLiBXaGF0IGlzIGl0IHN0YW5kYXJkIGRldmlhdGlvbi4gVG8gYXZvaWQgYW5zd2VyaW5nIHRoYXQgcXVlc3Rpb24sIGluc3RlYWQgb2YgbG9va2luZyBhdCAkel8xID1cYmFyIFhfMSAtIFxiYXIgWF8yJCAoJHpfMSQgIGlzIHRoZSB0ZXN0IHN0YXRpc3RpY3MpIHdlIGNvdWxkIGxvb2sgYXQgCiQkCnpfMiA9IFxmcmFje1xiYXIgWF8xIC0gXGJhciBYXzJ9e1x0ZXh0e3N0ZH0oXGJhciBYXzEgLSBcYmFyIFhfMil9CiQkCiR6XzIkIGlzIGEgbm9ybWFsaXNlZCB0ZXN0IHN0YXRpc3RpYyBhbmQgICRcdGV4dHtzdGR9KHpfMik9MSQgCmBgYHtyfQp6XzEgPSBjKCkKel8yID0gYygpCmZvcihrIGluIDE6bl90aW1lcyl7CiAgIyBkcmF3IHNhbXBsZXMgZnJvbSB0aGUgcG9wdWxhdGlvbnMKICBYXzExID0gc2FtcGxlKHBfMSxuX3NhbXBsZXMpCiAgWF8xMiA9IHNhbXBsZShwXzEsbl9zYW1wbGVzKQogICMgY29tcHV0ZSB0aGVpciBtZWFuIGRpZmZlcmVuY2UgYW5kIHN0b3JlIGluIGNvbnRhaW5lcgogIHpfMVtrXSA9IG1lYW4oWF8xMSktbWVhbihYXzEyKQp9CnpfMiA9IHpfMS9zZCh6XzEpCmhpc3Qoel8xLGNvbD0nZ3JheScseGxpbSA9IGMoLTQsNCkpCmhpc3Qoel8yLGFkZD1UUlVFLGNvbD1yZ2IoMCwwLDAuNSwwLjMpKQpgYGAKU28gd2UgY291bGQgbm93IGNvbmx1ZGUgdGhhdCB0aGUgZGlzdHJpYnV0aW9uIG9mICR6XzIkIGlzIHN0YW5kYXJkIG5vcm1hbC4gU28gd2UgYXJlIHNheWluZyB0aGF0IHVuZGVyIHRoZSBudWxsIGh5cG90aGVzaXMsIHRoZSBkaXN0cmlidXRpb24gb2YgJHpfMiQgaXMgYSBzdGFuZGFyZCBub3JtYWwgZGlzdHJpYnV0aW9uLiBJcyB0aGlzIGFsd2F5cyB0cnVlPyAKCgojIyBRdWVzdGlvbnMgMS4KV3JpdGUgdHdvIGZ1bmN0aW9ucyBgdHdvc2FtcGxlLnQoWDEsIFgyLCBuLnBlcm0pYCBhbmQgYHBhaXJlZC50KFgxLFgyLCBuLnBlcm0pYCAgdGhhdCByZXR1cm4gdGhlIHBlcm11dGF0aW9uIHAtdmFsdWUgb2YgYSB0d28tc2lkZWQgdHdvc2FtcGxlIHQtdGVzdCBhbmQgYSB0d28tc2lkZWQgcGFpcmVkIHQtdGVzdCBiYXNlZCBvbiBuLnBlcm0gcGVybXV0YXRpb25zLgpZb3Ugc2hvdWxkIGltcGxlbWVudCB0aGlzIHRlc3QgeW91cnNlbGYsIHNvIGRvbuKAmXQgdXNlIGEgdGVzdCBmcm9tIGUuZy4gdGhlCmNvaW4gcGFja2FnZS4gQXMgeW91ciBhbnN3ZXIgdG8gdGhpcyBxdWVzdGlvbiwgY29weS1wYXN0ZSB0aGUgKHJlYWRhYmxlKQpSIGNvZGUgb2YgdGhlc2UgdHdvIGZ1bmN0aW9ucyBzbyB0aGF0IHdlIGNhbiBjaGVjayB5b3VyIGltcGxlbWVudGF0aW9uLgoKCiogKipWZXJ5IGltcG9ydGFudDoqKiBub3RlIHRoYXQgYHR3b3NhbXBsZS50KFgxLCBYMiwgbi5wZXJtKWAgYW5kIGBwYWlyZWQudChYMSxYMiwgbi5wZXJtKWAgaGF2ZSBOT1RISU5HIHRvIGRvIHdpdGggYSAkdCQtdGVzdC4gUGxlYXNlIGRvbid0IGJlIGNvbmZ1c2Ugd2l0aCB0aGUgYC50YCBpbiB0aGUgZnVuY3Rpb24gbmFtZXMuIFRoaXMgY2FuIGJlIG1pc2xlYWRpbmcgSSBrbm93LCB0aGUgYC50YCBpbiB0aGUgbmFtZXMgc2ltcGx5IG1lYW5zIHRoZXkgYXJlIHRlc3RzLiAKCgojIyMgU29sdXRpb24gCmBgYHtyfQojIHR3byBzYW1wbGVzIAojX19fX19fXwojIHBvb2wgc2FtcGxlcwojIGRyYXcgdHdvIGdyb3VwcyBmcm9tIHBvb2xlZCBzYW1wbGUgIHdpdGhvdXQgcmVwbGFjZW1lbnQKIyBjb21wdXRlIGRpZmZlcmVuY2UgYmV0d2VlbiB0aGVpciBtZWFucyAKIyBjb21wYXJlIHdpdGggb2JzZXJ2ZWQKCnR3b3NhbXBsZS50PSBmdW5jdGlvbihYMSxYMixuLnBlcm0pewogIGxlbiA9IGxlbmd0aChYMSkKICAjIG9ic2VydmVkIHZhbHVlIAogIG9icyA9IG1lYW4oWDEpLW1lYW4oWDIpCiAgIyBwb29sZWQgc2FtcGxlcyx1bmRlciB0aGUgbnVsbCBpdCBkb2VzIG5vdCBtYXR0ZXIgd2hlcmUgdGhlIHNhbXBsZSBiZWxvbmdzCiAgWCA9IGMoWDEsWDIpCiAgIyB0aGVpciBpbmRpY2VzCiAgaW5kZXggPSBzZXEoMSwyKmxlbikKCgogIHN0YXRpc3RpY3MgPSBjKCkKICBmb3IoaSBpbiAxOm4ucGVybSl7CiAgICAjIHNhbXBsZSB0aGUgaW5kaWNlcywgaXQgZG9lcyBub3QgbWF0dGVyIHdoaWNoIHNhbXBsZSB3YXMgdGhlIG9ic2VydmF0aW9uIAogICAgIyBjYW1lIGZyb20KICAgIGluZGV4X3NhbXBsZV8xID0gc2FtcGxlKGluZGV4LGxlbixyZXBsYWNlID0gRkFMU0UpCiAgICBpbmRleF9zYW1wbGVfMiA9IGluZGV4WyEoaW5kZXggJWluJSBpbmRleF9zYW1wbGVfMSldCiAgICBzdGF0aXN0aWNzW2ldID0gbWVhbihYW2luZGV4X3NhbXBsZV8xXSktbWVhbihYW2luZGV4X3NhbXBsZV8yXSkKICB9CiAgIyBwcm9wb3J0aW9ucyBvZiB0ZXN0IHN0YXRpc3RpY3MgYmVsb3cgb2JzCiAgcF92YWx1ZSA9IHN1bShhYnMoc3RhdGlzdGljcyk+YWJzKG9icykpL24ucGVybQogICMgcF92YWx1ZSA9IGlmZWxzZShwX3ZhbHVlPjAuNSwxLXBfdmFsdWUscF92YWx1ZSkKICByZXR1cm4ocF92YWx1ZSkKfQoKCiMgY29tcHV0ZSBYMS1YMgojIHN3aXRjaCB0aGVpciBzaWducyByYW5kb21seQojIGNvbXB1dGUgbWVhbiBvZiBkaWZmZXJlbmNlCiMgY29tcGFyZSB3aXRoIHRoZSBvYnNlcnZlZCB2YWx1ZQoKcGFpcmVkLnQ9IGZ1bmN0aW9uKFgxLFgyLG4ucGVybSl7CiAgbGVuID0gbGVuZ3RoKFgxKQogICMgb2JzZXJ2ZWQgdmFsdWUgCiAgb2JzID0gbWVhbihYMSktbWVhbihYMikKCiAgc3RhdGlzdGljcyA9IGMoKQogIGZvcihpIGluIDE6bi5wZXJtKXsKICAgIHNpZ25zID0gc2FtcGxlKGMoMSwtMSksbGVuLHJlcGxhY2UgPSBUUlVFKQogICAgCiAgICAjIGNoYW5nZSBzaWduIG9mIGRpZmZlcmVuY2UgIHJhbmRvbWx5IGl0IGRvZXMgbm90IG1hdHRlciB3aGljaCBtZWFzdXJlbWVudCB3YXMgZG9uZSAKICAgICMgZmlyc3QsIHRoaXMgd2hhdCB0aGUgbnVsbCBoeXBvdGhlc2lzIHNheXMKICAgIAogICAgc3RhdGlzdGljc1tpXSA9IG1lYW4oKFgxLVgyKSpzaWducykKICB9CgogICMgcHJvcG9ydGlvbnMgb2YgdGVzdCBzdGF0aXN0aWNzIGJlbG93IG9icwogIHBfdmFsdWUgPSBzdW0oYWJzKHN0YXRpc3RpY3MpPmFicyhvYnMpKS9uLnBlcm0KICAjIHBfdmFsdWUgPSBpZmVsc2UocF92YWx1ZT4wLjUsMS1wX3ZhbHVlLHBfdmFsdWUpCiAgcmV0dXJuKHBfdmFsdWUpCn0KCiMgcGxheSB3aXRoIHRoZSB0d28gdGVzdHMgY2hhbmdlIHRoZSBtZWFucyBvZiBYMSBhbmQgWDIgYW5kIHNlZSB3aGF0IGhhcHBlbnMKTjwtMTAwCm4ucGVybSA9IDEwMDAKWDEgPSBybm9ybShOLG1lYW49MixzZD0yKQpYMiA9IHJub3JtKE4sbWVhbj0yLjMsc2Q9MikKcGFpcmVkLnQoWDEsWDIsbi5wZXJtPW4ucGVybSkKdHdvc2FtcGxlLnQoWDEsWDIsbi5wZXJtPW4ucGVybSkKCgpgYGAKIyMgUXVlc3Rpb24gMgpXcml0ZSBhIGZ1bmN0aW9uIGBzaW11bGF0ZS5kYXRhKG4sIGRlbHRhLCBjb3JyZWxhdGlvbilgIHRoYXQgc2ltdWxhdGVzICRuJCBwYWlyZWQgb2JzZXJ2YXRpb25zIChzbyB0aGUgdG90YWwgbnVtYmVyIG9mIG9ic2VydmF0aW9ucyBpcyAkMm4kKSwgc2F5CgpgWDFgIGFuZCBgWDJgLCBmcm9tIGEgc2tld2VkIGRpc3RyaWJ1dGlvbiB3aGVyZSBgRVtYMV3iiJJFW1gyXSA9IGRlbHRhYC4gVGhlCnBhcmFtZXRlciBjb3JyZWxhdGlvbiBjYW4gdGFrZSBvbiBhIG51bWJlciBmcm9tIDEgdG8gNSBhbmQgaXMgcmVsYXRlZAp0byB0aGUgc3RyZW5ndGggb2YgdGhlIGNvcnJlbGF0aW9uLiBNb3JlIHNwZWNpZmljYWxseSwgYGNvcnJlbGF0aW9uID0gMWAKc2hvdWxkIGNvcnJlc3BvbmQgdG8gYGNvcihYMSwgWDIpID0gMGAsIGBjb3JyZWxhdGlvbiA9IDJgIHRvIGBjb3IoWDEsIFgyKSA9CjAuMWAsIGBjb3JyZWxhdGlvbiA9IDNgIHRvIGBjb3IoWDEsIFgyKSA9IDAuMjVgLCBjb3JyZWxhdGlvbiA9IDQgdG8KY29yKFgxLCBYMikgPSAwLjUgYW5kIGNvcnJlbGF0aW9uID0gNSB0byBjb3IoWDEsIFgyKSA9IDAuNy4gTm90ZSB0aGF0Cm1hbnkgcGFyYW1ldGVycyBhcmUgbGVmdCBmcmVlIGluIHRoaXMgZnVuY3Rpb24gKGUuZy4gdGhlIG1hcmdpbmFsIG1lYW5zCgphbmQgdmFyaWFuY2VzIC0geW91IGNhbiBjaG9vc2UgdGhlIHZhbHVlcyB5b3Vyc2VsZiBmb3IgdGhpcykuIEFzIHlvdXIgYW4tCnN3ZXIgdG8gdGhpcyBxdWVzdGlvbiwgY29weS1wYXN0ZSB0aGUgKHJlYWRhYmxlKSBSIGNvZGUgb2YgdGhpcyBmdW5jdGlvbi4KCgpUaXA6IHlvdSBtaWdodCB3YW50IHRvIGV4YW1pbmUgdGhlIGNvZGUgYmVsb3cgdG8gZ2V0IGluc3BpcmF0aW9uIG9uIGhvdwp5b3UgY2FuIHNpbXVsYXRlIGNvcnJlbGF0ZWQgc2tld2VkIGJpdmFyaWF0ZSBkYXRhLiBOb3RlIHRoYXQgY29yIGJlbG93CndpbGwgbm90IGV4YWN0bHkgZXF1YWwgYGNvcihYMSwgWDIpYCwgc28geW91IHdpbGwgaGF2ZSB0byBmaW5lIHR1bmUgdGhpcy4gWW91CmNhbiBkbyB0aGlzIGJlIHNldHRpbmcgJG4kIHRvIGEgbGFyZ2UgbnVtYmVyIChlLmcuIDEwMDAwKSBhbmQgc2VlIHdoYXQgdGhlCnNhbXBsZSBjb3JyZWxhdGlvbiBpcyAod2hpY2ggd2lsbCBiZSB2ZXJ5IGNsb3NlIHRvIGNvcihYMSwgWDIpIGJlY2F1c2UgJG4kIGlzCmxhcmdlKSBmb3IgYSBjaG9pY2Ugb2YgY29yLiBJdCBpcyBub3QgbWFuZGF0b3J5IHRvIHVzZSB0aGlzIGNvZGUuCmBgYHtyfQpsaWJyYXJ5KG12dG5vcm0pCm4gPC0gMTAwMDAwCmNvciA8LSAuMQpZIDwtIHJtdm5vcm0obiwgbWVhbiA9IGMoMCwyKSxzaWdtYSA9IG1hdHJpeChucm93ID0gMiwgbmNvbCA9IDIsIGMoMSwgY29yLCBjb3IsIDEpKSkKCmNvdihZKQpaIDwtIHBub3JtKFkpICMgc3RhbmRhcmQgbm9ybWFsIAoKWDEgPC0gcWV4cChaWywxXSkKWDIgPC0gcWV4cChaWywyXSkKCgoKCmNvcl9kYXRhID0gZGF0YS5mcmFtZShjb3JyZWxhdGlvbj1jKDE6NSksY29yPWMoMCwwLjEsMC4yNSwwLjUsMC43KSkKCnNpbXVsYXRlLmRhdGE9ZnVuY3Rpb24obiwgZGVsdGEsIGNvcnJlbGF0aW9uKXsKICBjb3IgPSBjb3JfZGF0YVtjb3JyZWxhdGlvbiwyXQogIFkgPC0gcm12bm9ybShuLCBtZWFuID0gYygwLGRlbHRhKSxzaWdtYSA9IG1hdHJpeChucm93ID0gMiwgbmNvbCA9IDIsIGMoMSwgY29yLCBjb3IsIDEpKSkKICBaIDwtIHBub3JtKFkpICMgc3RhbmRhcmQgbm9ybWFsCiAgWDEgPC0gcWV4cChaWywxXSkKICBYMiA8LSBxZXhwKFpbLDJdKQogIGRhdGEuZnJhbWUoWDEsWDIpCn0KCmBgYApDcmVhdGUgYSBncmFwaCB3aGVyZSB5b3UgcGxvdCB0aGUgZW1waXJpY2FsIGB0eXBlIElgIGFuZCBgdHlwZSBJSWAgZXJyb3IKZm9yIGVhY2ggdGVzdCBhcyBhIGZ1bmN0aW9uIG9mIHRoZSBjb3JyZWxhdGlvbiB3aGVyZSB0aGUgY29ycmVsYXRpb24gdGFrZXMKb24gdGhlIHZhbHVlcyBgMCwgMC4xLCAwLjI1LCAwLjUgYW5kIDAuN2AgYW5kIGZvciAkXGFscGhhJCA9IDUlLiBIZXJlICRuJCBzaG91bGQKYmUgZXF1YWwgdG8gJDUkIChtaW1pY2tpbmcgYSB2ZXJ5IHNtYWxsIHNhbXBsZSkgYW5kIHRvIDEwMCAobWltaWNraW5nCmEgbGFyZ2VyIHNhbXBsZSkgYW5kIHlvdSBjYW4gY2hvb3NlIHRoZSBudW1iZXIgb2YgcGVybXV0YXRpb25zIGFuZApNb250ZS1DYXJsbyBzaW11bGF0aW9ucyB5b3Vyc2VsZiAodGhlIGhpZ2hlciB0aGUgYmV0dGVyLCBidXQgaGlnaGVyIGFsc28KbWVhbnMgY29tcHV0YXRpb25hbGx5IG1vcmUgaW50ZW5zaXZlLCBzbyB0aGVyZSBpcyBhIHRyYWRlLW9mZikuIEluIHlvdXIKYW5zd2VyIHRvIHRoaXMgcXVlc3Rpb24geW91IHNob3VsZCBvbmx5IGluY2x1ZGUgdHdvIHBsb3RzOiBvbmUgZm9yIGBuID0gNWAKYW5kIG9uZSBmb3IgYG4gPSAxMDBgIGVhY2ggd2l0aCA0IGN1cnZlcyAoZm9yIGJvdGggZXJyb3JzIGFuZCBmb3IgYm90aCB0ZXN0cykKLSB0aGlzIHBsb3Qgc2hvdWxkIGJlIHJlYWRhYmxlIGluIGJsYWNrLWFuZC13aGl0ZSBhbmQgcGxlYXNlIHByb3ZpZGUgYW4KaW5mb3JtYXRpdmUgY2FwdGlvbi4gTWFrZSBzdXJlIHRoYXQgd2hlbiB5b3Ugc2ltdWxhdGUgZGF0YSB1bmRlciAkSF9BJAp0aGUgdHlwZSBJSSBlcnJvciBpcyBub3QgdG9vIGNsb3NlIHRvIHplcm8gb3Igb25lIChiZWNhdXNlIHRoZW4gaXQgaXMgaGFyZCB0bwpjb21wYXJlIHRoZSBtZXRob2RzIC0gdGhlIGRlbHRhIGlzIGFsbG93ZWQgdG8gYmUgZGlmZmVyZW50IHdoZW4gYG4gPSA1YAphbmQgd2hlbiBgbiA9IDEwMGApLgpgYGB7cn0KIyMgMSkgc3RhdGUgdGhlIHR5cGUgSSBhbmQgSUkgZXJyb3JzCiMjIDIpIHNpbXVsYXRlIGRhdGEgd2l0aCBudWxsIGh5cG90aGVzaXMgdHJ1ZQojIyAzKSBzaW11bGF0ZSBkYXRhIHdpdGggbnVsbCBoeXBvdGhlc2lzIGZhbHNlCiMjIHNldCBuID0gNSAKIyMgc2V0IG4gPSAxMDAKIyMgc2V0IGRlbHRhIGZvciBuID0gNSBhbmQgMTAwCgoKCmFscGhhID0gMC4wNQpCID0gMTAwCm4ucGVybSA9IDEwMDAKCnBhaXJlZF9jb24gPSBjKCkKdHdvc2FtcGxlX2NvbiA9IGMoKQoKIyBjb250YWluZXJzIGZvciBuPTUgdHlwZSBJIGFuZCB0eXBlIElJCmVycm9yX3R5cGVfSSA9IGRhdGEuZnJhbWUobWF0cml4KE5BLG5yb3c9MixuY29sID0gNSkpCmVycm9yX3R5cGVfSUkgPSBkYXRhLmZyYW1lKG1hdHJpeChOQSxucm93PTIsbmNvbCA9IDUpKQoKcm93bmFtZXMoZXJyb3JfdHlwZV9JKSA9IGMoJ3R5cGVfSV9wYWlyZWQnLCd0eXBlX0lfdHdvc2FtcGxlJykKY29sbmFtZXMoZXJyb3JfdHlwZV9JKT0gcGFzdGUoJ2NvcnJlbGF0aW9uXycsc2VxKDEsNSkpCgpyb3duYW1lcyhlcnJvcl90eXBlX0lJKSA9IGMoJ3R5cGVfSUlfcGFpcmVkJywndHlwZV9JSV90d29zYW1wbGUnKQpjb2xuYW1lcyhlcnJvcl90eXBlX0lJKT0gcGFzdGUoJ2NvcnJlbGF0aW9uXycsc2VxKDEsNSkpCgoKCgojIG91ciBzaW11bGF0aW9uIGFuZCBwbG90IGZ1bmN0aW9uCmNvcnJlbGF0aW9ucyA9IGMoMTo1KQphbGxfc2ltID0gZnVuY3Rpb24obixkZWx0YSl7CmZvcihqIGluIDE6bGVuZ3RoKGNvcnJlbGF0aW9ucykpewogICAgZm9yKGIgaW4gMTpCKXsKICAgICAgZGF0YSA9IHNpbXVsYXRlLmRhdGEobj1uLGRlbHRhPTAsY29ycmVsYXRpb249Y29ycmVsYXRpb25zW2pdKQogICAgICBwYWlyZWRfY29uW2JdID0gcGFpcmVkLnQoWDE9ZGF0YSRYMSxYMj1kYXRhJFgyLG4ucGVybSA9IG4ucGVybSk8PWFscGhhCiAgICAgIHR3b3NhbXBsZV9jb25bYl0gPSB0d29zYW1wbGUudChYMT1kYXRhJFgxLFgyPWRhdGEkWDIsbi5wZXJtID0gbi5wZXJtKTw9YWxwaGEKICAgIH0KICAgIGVycm9yX3R5cGVfSVsxLGpdID0gIHN1bShwYWlyZWRfY29uKS9CCiAgICBlcnJvcl90eXBlX0lbMixqXSA9ICBzdW0odHdvc2FtcGxlX2NvbikvQgp9CiN0eXBlIElJIApmb3IoaiBpbiAxOmxlbmd0aChjb3JyZWxhdGlvbnMpKXsKICAgIGZvcihiIGluIDE6Qil7CiAgICAgIGRhdGEgPSBzaW11bGF0ZS5kYXRhKG49bixkZWx0YT1kZWx0YSxjb3JyZWxhdGlvbj1jb3JyZWxhdGlvbnNbal0pCiAgICAgIHBhaXJlZF9jb25bYl0gPSBwYWlyZWQudChYMT1kYXRhJFgxLFgyPWRhdGEkWDIsbi5wZXJtID0gbi5wZXJtKT5hbHBoYQogICAgICB0d29zYW1wbGVfY29uW2JdID0gdHdvc2FtcGxlLnQoWDE9ZGF0YSRYMSxYMj1kYXRhJFgyLG4ucGVybSA9IG4ucGVybSk+YWxwaGEKICAgIH0KICAgIGVycm9yX3R5cGVfSUlbMSxqXSA9ICBzdW0ocGFpcmVkX2NvbikvQgogICAgZXJyb3JfdHlwZV9JSVsyLGpdID0gIHN1bSh0d29zYW1wbGVfY29uKS9CCn0KCmNvcnJfID0gYygwLDAuMSwwLjI1LDAuNSwwLjcpCnlsaW1pdHMgPSBjKG1pbihlcnJvcl90eXBlX0ksZXJyb3JfdHlwZV9JSSksbWF4KGVycm9yX3R5cGVfSSxlcnJvcl90eXBlX0lJKSkKcGxvdCgKICB4ID0gY29ycl8sCiAgeSA9IGVycm9yX3R5cGVfSVsxLCBdLAogIHR5cGUgPSAnYicsCiAgbWFpbiA9IHBhc3RlKCduID0gJyxuLCAndHlwZSBJIGFuZCBJSSBlcnJvciByYXRlcycpLAogIHhsYWIgPSAnY29ycmVsYXRpb25zJywKICB5bGFiID0gJ0Vycm9yIHJhdGUnLAogIHlsaW0gPSB5bGltaXRzLAogIGx0eT0xLAogIHBjaCA9IDEKKQpsaW5lcyh4ID0gY29ycl8sCiAgICAgIHkgPSBlcnJvcl90eXBlX0lbMiwgXSwKICAgICAgdHlwZSA9ICdiJywKICAgICAgbHR5ID0gMiwKICAgICAgcGNoPTIpCmxpbmVzKAogIHggPSBjb3JyXywKICB5ID0gZXJyb3JfdHlwZV9JSVsxLCBdLAogIHR5cGUgPSAnYicsCiAgbHR5ID0gMywKICBwY2ggPSAzCikKbGluZXMoCiAgeCA9IGNvcnJfLAogIHkgPSBlcnJvcl90eXBlX0lJWzIsIF0sCiAgdHlwZSA9ICdiJywKICBsdHkgPSA0LAogIHBjaCA9IDQKKQpsZWdlbmQoInRvcHJpZ2h0IiwKICAgICAgIGxlZ2VuZCA9IGMoJ1BhaXJlZCB0eXBlIEknLCAndHdvX3NhbXBsZSB0eXBlIEknLCdQYWlyZWQgdHlwZSBJSScsICd0d29fc2FtcGxlIHR5cGUgSUknKSwKICAgICAgIGx0eSA9IGMoMSwgMiwzLDUpLHBjaD1jKDEsMiwzLDQpKQp9CmBgYAoKCmBgYHtyfQphbGxfc2ltKG49NSxkZWx0YT0yKQpgYGAKCldoYXQgZG8geW91IGNvbmNsdWRlIGZvciBgbj01YCwgdHdvIHNhbXBsZSB0ZXN0IHNlZW1zIHRvIHBlcmZvcm0gYmV0dGVyIHdpdGggc21hbGwgc2FtcGxlcz8uIApgYGB7cn0Kc2V0LnNlZWQoMTAwKQphbGxfc2ltKG49MTAwLGRlbHRhID0gMC4zNSkKYGBgCgojIyMgb2JzZXJ2YXRpb25zCiogR2VuZXJhbGx5IGVycm9ycyBzZWVtIHRvIGRyb3Agd2l0aCBpbmNyZWFzaW5nIGNvcnJlbGF0aW9uCiogV2hhdCBjYW4geW91IHNheSBhYm91dCB0aGUgcGFpcmVkIGFuZCB0d28gc2FtcGxlIHRlc3RzIHBlcmZvbWFuY2UgZm9yIHR5cGUgSSBhbmQgdHlwZSBJSSBlcnJvciByYXRlcz8KKiBJdCBzZWVtcyBsaWtlIHRoZSBwYWlyZWQgdGVzdCBoYXMgYW4gZWRnZSBvdmVyIHRoZSB0d28gc2FtcGxlIGZvciB0aGUgdHlwZSBJSSBlcnJvciByYXRlcz8gCgojIyBRdWVzdGlvbiA1IApXZSBub3cgdHVybiB0byBjb25maWRlbmNlIGludGVydmFscyBhbmQgd2UgYXJlIGZpcnN0IGludGVyZXN0ZWQgaW4gc29tZQphbmFseXRpY2FsIHJlc3VsdHMuCgoqICBXb3JrIG91dCB0aGUgZXhwZWN0YXRpb24gYW5kIHZhcmlhbmNlIG9mIHRoZSBzYW1wbGUgbWVhbiBkaWZmZXJlbmNlCiRcYmFyIFhfMSQg4oiSICRcYmFyIFhfMiQgYXNzdW1pbmcgYSkgaW5kZXBlbmRlbmNlIGFuZCBiKSBkZXBlbmRlbmNlIGJldHdlZW4gJFhfMSQKYW5kICRYXzIkLiBUaXA6IGZvciBhdCBsZWFzdCBvbmUgb2YgdGhlIHR3byBzY2VuYXJpb3MgdGhlIHNvbHV0aW9uIGNhbgpiZSBmb3VuZCBpbiB0aGUgY291cnNlIG5vdGVzIG9uIGh5cG90aGVzaXMgdGVzdGluZy4KKGIpIFVzZSB0aGUgYWJvdmUgZXhwcmVzc2lvbnMgdG8gd3JpdGUgZG93biB0aGUgZm9ybXVsYSBvZiBhbiAkKDEg4oiSIFxhbHBoYSkgw5cxMDBcJSQgY29uZmlkZW5jZSBpbnRlcnZhbCBmb3IgJEUgW1hfMV0g4oiSIEUgW1hfMl0kIGFzc3VtaW5nIGEpIAppbmRlcGVuZGVuY2UgYW5kIGIpIGRlcGVuZGVuY2UgYmV0d2VlbiAkWF8xJCBhbmQgJFhfMiQuIFdoZW4gZGVyaXZpbmcgdGhlCgpjb25maWRlbmNlIGludGVydmFscywgeW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgdmFyaWFibGVzIGFyZSBub3JtYWxseQpkaXN0cmlidXRlZCBvciB5b3UgY2FuIHJlbHkgb24gbGFyZ2Utc2FtcGxlIGFwcHJveGltYXRpb25zLgoKIyMjIFNvbHV0aW9uIAphKSBpbmRlcGVuZGVuY2UKTGV0ICRcc2lnbWFfMV4yJCBhbmQgJFxzaWdtYV8yXjIkIGJlIHRoZSB2YXJpYW5jZXMgb2YgJFhfMSQgYW5kICRYXzIkIHJlc3BlY3RpdmVseSB0aGVuIGFuZCBwZXIgdGhlIHJlcXVpcmVtZW50cyBvZiB0aGUgcHJvYmxlbSBhdCBoYW5kIHRoZSBzYW1wbGUgc2l6ZSBpcyAkbiQgZm9yIGJvdGggZ3JvdXBzIHRoZW46CiQkCkUoXGJhciBYXzEgLSBcYmFyIFhfMikgPSBcYmFyIFhfMS1cYmFyIFhfMgokJAokJApcdGV4dHtWYXJ9KFxiYXIgWF8xIC0gXGJhciBYXzIpID0gXHRleHR7VmFyfShcYmFyIFhfMSkrXHRleHR7VmFyfShcYmFyIFhfMikgPSAgXGZyYWN7IFxzaWdtYV4yXzF9e259K1xmcmFje1xzaWdtYV4yXzJ9e259ID0gXGZyYWN7IFxzaWdtYV8xXjIrXHNpZ21hXzJeMn17bn0KJCQKYikgZGVwZW5kZW5jZSAKCiQkCkUoXGJhciBYXzEgLSBcYmFyIFhfMikgPSBcYmFyIFhfMS1cYmFyIFhfMgokJAokJApcdGV4dHtWYXJ9KFxiYXIgWF8xIC0gXGJhciBYXzIpICA9IFxmcmFjeyBcc2lnbWFfMV4yK1xzaWdtYV8yXjJ9e259LTJcdGV4dHtDb3Z9KFxiYXIgWF8xLFxiYXIgWF8yKQokJApiKSBJbmRlcGVuZGVuY2UKJCQKWiA9IFxmcmFje1xiYXIgWF8xLVxiYXIgWF8yfXtcc3FydHtcZnJhY3sgXHNpZ21hXzFeMitcc2lnbWFfMl4yfXtufX19XHNpbSBOKDAsMSkKJCQKCiRcYWxwaGEkJSBjb25maWRlbmNlICBpcyAKJCQKXFBoaV57LTF9KFxmcmFje1xhbHBoYX17Mn0pXGxlcSBaXGxlcSBcUGhpXnstMX0oMS1cZnJhY3tcYWxwaGF9ezJ9KQokJAoKd2hlcmUgJFxQaGkoLikkIGlzIHRoZSBjdW1tdWxhdGl2ZSBub3JtYWwgZGlzdHJpYnV0aW9uIGZ1bmN0aW9uLiAKb3IgCiQkClxzcXJ0e1xmcmFje1xzaWdtYV8xXjIrXHNpZ21hXzJeMn17bn19XFBoaV57LTF9KFxmcmFje1xhbHBoYX17Mn0pXGxlcSBcYmFyIFhfMS1cYmFyIFhfMlxsZXEgXFBoaV57LTF9KDEtXGZyYWN7XGFscGhhfXsyfSkgXHNxcnR7XGZyYWN7XHNpZ21hXzFeMitcc2lnbWFfMl4yfXtufX0KJCQKJCQKXGxlZnRbKFxiYXIgWF8xLVxiYXIgWF8yKStcc3FydHtcZnJhY3tcc2lnbWFfMV4yK1xzaWdtYV8yXjJ9e259fVxQaGleey0xfShcZnJhY3tcYWxwaGF9ezJ9KSwgKCBcYmFyIFhfMS1cYmFyIFhfMikrXFBoaV57LTF9KDEtXGZyYWN7XGFscGhhfXsyfSkgXHNxcnR7XGZyYWN7XHNpZ21hXzFeMitcc2lnbWFfMl4yfXtufX1ccmlnaHRdCiQkCmIpIERlcGVuZGVuY2UKJCQKWiA9IFxmcmFje1xiYXIgWF8xLVxiYXIgWF8yfXtcc3FydHtcZnJhY3sgXHNpZ21hXzFeMitcc2lnbWFfMl4yLTJcdGV4dHtDb3Z9KFxiYXIgWF8xLFxiYXIgWF8yKX17bn19fVxzaW0gTigwLDEpCiQkCgpEZXJpdmUgdGhlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgaW4gYSBzaW1pbGFyIHdheSBhcyBhYm92ZS4gCgoKCiMgUXVlc3Rpb24gNiAKU2ltdWxhdGUgZGF0YSB1bmRlciAkSF8wJCBvciAkSF9BJCAoeW91IGNhbiBjaG9vc2UgYW5kIHlvdSBjYW4gcmV1c2UgdGhlCmNvZGUgZnJvbSB0aGUgcHJldmlvdXMgcXVlc3Rpb25zKSBmb3IgbiA9IDEwMCBhbmQgY29tcHV0ZSB0aGUgZW1waXJpY2FsCmNvdmVyYWdlIGFuZCBhdmVyYWdlIHdpZHRoIG9mIGEgJDk1XCUkIGNvbmZpZGVuY2UgaW50ZXJ2YWwgZm9yIEUgW1gxXeKIkkUgW1gyXQoKKHVzaW5nIHRoZSB0d28gY29uZmlkZW5jZSBpbnRlcnZhbHMgeW91IGhhdmUgZGVyaXZlZCBpbiB0aGUgcHJldmlvdXMgcXVlcy0KdGlvbiAtIHNvIHlvdSBpbXBsZW1lbnQgdGhlc2UgY29uZmlkZW5jZSBpbnRlcnZhbHMgaW4gUiB5b3Vyc2VsZikuIE1ha2UKCnR3byBncmFwaHM6IG9uZSB3aXRoIHRoZSBlbXBpcmljYWwgY292ZXJhZ2UgYXMgYSBmdW5jdGlvbiBvZiB0aGUgY29ycmVsYS0KdGlvbiBhbmQgb25lIHdpdGggdGhlIGF2ZXJhZ2Ugd2lkdGggYXMgYSBmdW5jdGlvbiBvZiB0aGUgY29ycmVsYXRpb24gd2hlcmUKdGhlIGNvcnJlbGF0aW9uIHRha2VzIG9uIHRoZSB2YWx1ZXMgMCwgMC4xLCAwLjI1LCAwLjUgYW5kIDAuNy4KYGBge3J9CiMjIGNvdmVyYWdlID0gcHJvcG9ydGlvbiBvZiB0aW1lcyB0aGUgdHJ1ZSB2YWx1ZSBpcyBpbiB0aGUgY29uZmlkZW5jZSBpbnRlcnZhbAojIyBsZW5ndGggb2YgQ0kgPSBtYXgtbWluIAoKCgojIyBJbXBvcnRhbnQgbm90ZSAKIyMgTm90ZSB0aGF0IHRoZSBkYXRhICBmcm9tIG91ciBzYW1wbGUgZnVuY3Rpb24gaGFzIGJlZW4gdHJhbnNmb3JtZWQgc28gYSBkZWx0YSA9IDAKIyMgY29ycmVwb25kcyB0byBhIHNwZWNpZmljIHZhbHVlIGluIHRoZSB0cmFuc2Zvcm1lZCBzY2FsZSB3ZSBzZXQgdGhlIHNhbXBsZSBzaXplIHZlcnkgCiMjIGxhcmdlIHRvIHNlZSB0aGUgY29ycmVzcG9uZGluZyB2YWx1ZSAKbiA8LSAxMDAwMDAwCmNvciA8LSAuMQpZIDwtIHJtdm5vcm0obiwgbWVhbiA9IGMoMCwwKSxzaWdtYSA9IG1hdHJpeChucm93ID0gMiwgbmNvbCA9IDIsIGMoMSwgY29yLCBjb3IsIDApKSkKCgpaIDwtIHBub3JtKFkpICMgc3RhbmRhcmQgbm9ybWFsIAoKWDEgPC0gcWV4cChaWywxXSkKWDIgPC0gcWV4cChaWywyXSkKCnRyYW5zX2RlbHRhID0gcm91bmQobWVhbihYMiktbWVhbihYMSksMikKI3RoZSBjb3JyZXBvbmRpbmcgdmFsdWUgaXMgLTAuMyByb3VuZCB0byAyIGRwCgoKbiA9IDEwMCAKYWxwaGEgPSAwLjA1CmRlbHRhID0gMQoKCgoKCmNvdmVyYWdlX2RlcCA9IGMoKQpjb3ZlcmFnZV9pbmQgPSBjKCkKCmxlbmd0aF9kZXAgPSBjKCkKbGVuZ3RoX2luZCA9IGMoKQoKZm9yKGogaW4gMTpsZW5ndGgoY29ycmVsYXRpb25zKSl7CiAgICBsZW5fZGVwID0gYygpCiAgICBsZW5faW5kID0gYygpCiAgICAKICAgIGNvdmVfZGVwID0gYygpCiAgICBjb3ZlX2luZCA9IGMoKQogICAgZm9yKGIgaW4gMTpCKXsKICAgICAgZGF0YSA9IHNpbXVsYXRlLmRhdGEobj1uLGRlbHRhPTAsY29ycmVsYXRpb249Y29ycmVsYXRpb25zW2pdKQogICAgICB2MSA9IHZhcihkYXRhJFgxKQogICAgICB2MiA9IHZhcihkYXRhJFgyKQogICAgICAKICAgICAgZGVsdGFoYXQgPSBtZWFuKGRhdGEkWDIpIC0gbWVhbihkYXRhJFgxKQogICAgICB0ZXJtX2luZCA9IHNxcnQoKHYxK3YyKS9uKSpxbm9ybSgxLShhbHBoYS8yKSkKICAgICAgdGVybV9kZXAgPSBzcXJ0KCh2MSt2Mi0yKmNvdihkYXRhJFgxLGRhdGEkWDIpKS9uKSpxbm9ybSgxLWFscGhhLzIpCiAgICAgIAogICAgICAjIGNvbXB1dGUgCiAgICAgIAogICAgICBsYl9pbmQgPSBkZWx0YWhhdC10ZXJtX2luZAogICAgICB1cF9pbmQgPSBkZWx0YWhhdCt0ZXJtX2luZAogICAgICAKICAgICAgbGJfZGVwID0gZGVsdGFoYXQtdGVybV9kZXAKICAgICAgdXBfZGVwID0gZGVsdGFoYXQrdGVybV9kZXAKICAgICAgCiAgICAgIGxlbl9pbmRbYl0gPSB1cF9pbmQtbGJfaW5kCiAgICAgIGxlbl9kZXBbYl0gPSB1cF9kZXAtbGJfZGVwCiAgICAgIAogICAgICBjb3ZlX2luZFtiXT0gbGJfaW5kIDw9IHRyYW5zX2RlbHRhICYgdHJhbnNfZGVsdGE8PXVwX2luZAogICAgICBjb3ZlX2RlcFtiXT0gbGJfZGVwIDw9IHRyYW5zX2RlbHRhICYgdHJhbnNfZGVsdGE8PXVwX2RlcAoKICAgIH0KICAgIGNvdmVyYWdlX2RlcFtqXSA9IHN1bShjb3ZlX2RlcCkvQgogICAgY292ZXJhZ2VfaW5kW2pdID0gc3VtKGNvdmVfaW5kKS9CCiAgICAKICAgIGxlbmd0aF9kZXBbal0gPSBtZWFuKGxlbl9kZXApCiAgICBsZW5ndGhfaW5kW2pdID0gbWVhbihsZW5faW5kKQp9CgoKY29ycl8gPSBjKDAsMC4xLDAuMjUsMC41LDAuNykKeWxpbWl0cyA9IGMobWluKGNvdmVyYWdlX2RlcCxjb3ZlcmFnZV9pbmQpLG1heChjb3ZlcmFnZV9kZXAsY292ZXJhZ2VfaW5kKSkKcGxvdCh4ID0gY29ycl8seSA9IGNvdmVyYWdlX2RlcCx0eXBlID0gJ2InLAogICAgIHhsYWIgPSAnY29ycmVsYXRpb25zJyx5bGFiID0gJ0NvdmVyYWdlJyx5bGltID0geWxpbWl0cywKICBsdHk9MSxwY2ggPSAxCikKbGluZXMoeCA9IGNvcnJfLHkgPSBjb3ZlcmFnZV9pbmQsdHlwZSA9ICdiJyxsdHkgPSAyLHBjaD0yKQojIyMgYWRkIGEgbGVnZW5kCmBgYAoKCmBgYHtyfQpjb3JyXyA9IGMoMCwwLjEsMC4yNSwwLjUsMC43KQp5bGltaXRzID0gYyhtaW4obGVuZ3RoX2RlcCxsZW5ndGhfaW5kKSxtYXgobGVuZ3RoX2RlcCxsZW5ndGhfaW5kKSkKcGxvdCh4ID0gY29ycl8seSA9IGxlbmd0aF9kZXAsdHlwZSA9ICdiJywKICAgICB4bGFiID0gJ0NvcnJlbGF0aW9uJyx5bGFiID0gJ2F2ZXJhZ2Ugd2lkdGgnLHlsaW0gPSB5bGltaXRzLAogIGx0eT0xLHBjaCA9IDEKKQpsaW5lcyh4ID0gY29ycl8seSA9IGxlbmd0aF9pbmQsdHlwZSA9ICdiJyxsdHkgPSAyLHBjaD0yKQpgYGAK