Demonstration of covariance matrix and basis function implementation of Gaussian process model in Stan.

The basics of the covariance matrix approach is based on the Chapter 10 of Stan User’s Guide, Version 2.26 by Stan Development Team (2021). https://mc-stan.org/docs/stan-users-guide/

The basics of the Hilbert space basis function approximation is based on Riutort-Mayol, Bürkner, Andersen, Solin, and Vehtari (2020). Practical Hilbert space approximate Bayesian Gaussian processes for probabilistic programming. https://arxiv.org/abs/2004.11408

1 Motorcycle accident acceleration data

Data are measurements of head acceleration in a simulated motorcycle accident, used to test crash helmets.

Data are modelled first with normal distribution having Gaussian process prior on mean: \[ y \sim \mbox{normal}(f(x), \sigma)\\ f \sim GP(0, K_1)\\ \sigma \sim \mbox{normal}^{+}(0, 1), \] and then with normal distribution having Gaussian process prior on mean and log standard deviation: \[ y \sim \mbox{normal}(f(x), \exp(g(x))\\ f \sim GP(0, K_1)\\ g \sim GP(0, K_2). \]

Load packages

library(cmdstanr) 
library(posterior)
library(loo)
library(tidybayes)
options(pillar.neg = FALSE, pillar.subtle=FALSE, pillar.sigfig=2)
library(tidyr) 
library(dplyr) 
library(ggplot2)
library(ggrepel)
library(latex2exp)
library(bayesplot)
theme_set(bayesplot::theme_default(base_family = "sans", base_size=16))
set1 <- RColorBrewer::brewer.pal(7, "Set1")
SEED <- 48927 # set random seed for reproducibility

1.1 Load and plot data

Load data

data(mcycle, package="MASS")
head(mcycle)
  times accel
1   2.4   0.0
2   2.6  -1.3
3   3.2  -2.7
4   3.6   0.0
5   4.0  -2.7
6   6.2  -2.7

Plot data

mcycle %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")

2 Homoskedastic GP with covariance matrices

We start with a simpler homoskedastic residual Gaussian process model \[ y \sim \mbox{normal}(f(x), \sigma)\\ f \sim GP(0, K_1)\\ \sigma \sim \mbox{normal}^{+}(0, 1), \] that has analytic marginal likelihood for the covariance function and residual scale parameters.

2.1 Model code

file_gpcovf <- "gpcovf.stan"
writeLines(readLines(file_gpcovf))
functions {
  vector gp_pred_rng(array[] real x2,
                     vector y1,
                     array[] real x1,
                     real sigma_f,
                     real lengthscale_f,
                     real sigma,
                     real jitter) {
    int N1 = rows(y1);
    int N2 = size(x2);
    vector[N2] f2;
    {
      matrix[N1, N1] L_K;
      vector[N1] K_div_y1;
      matrix[N1, N2] k_x1_x2;
      matrix[N1, N2] v_pred;
      vector[N2] f2_mu;
      matrix[N2, N2] cov_f2;
      matrix[N1, N1] K;
      K = gp_exp_quad_cov(x1, sigma_f, lengthscale_f);
      for (n in 1:N1)
        K[n, n] = K[n,n] + square(sigma);
      L_K = cholesky_decompose(K);
      K_div_y1 = mdivide_left_tri_low(L_K, y1);
      K_div_y1 = mdivide_right_tri_low(K_div_y1', L_K)';
      k_x1_x2 = gp_exp_quad_cov(x1, x2, sigma_f, lengthscale_f);
      f2_mu = (k_x1_x2' * K_div_y1);
      v_pred = mdivide_left_tri_low(L_K, k_x1_x2);
      cov_f2 = gp_exp_quad_cov(x2, sigma_f, lengthscale_f) - v_pred' * v_pred;

      f2 = multi_normal_rng(f2_mu, add_diag(cov_f2, rep_vector(jitter, N2)));
    }
    return f2;
  }
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
  int<lower=1> N2;     // number of test points
  vector[N2] x2;       // univariate test points
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  array[N] real xn = to_array_1d((x - xmean)/xsd);
  array[N2] real x2n = to_array_1d((x2 - xmean)/xsd);
  vector[N] yn = (y - ymean)/ysd;
  real sigma_intercept = 1;
  vector[N] zeros = rep_vector(0, N);
}
parameters {
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> sigman;         // noise sigma
}
model {
  // covariances and Cholesky decompositions
  matrix[N, N] K_f = gp_exp_quad_cov(xn, sigma_f, lengthscale_f)+
                     sigma_intercept^2;
  matrix[N, N] L_f = cholesky_decompose(add_diag(K_f, sigman^2));
  // priors
  lengthscale_f ~ normal(0, 1);
  sigma_f ~ normal(0, 1);
  sigman ~ normal(0, 1);
  // model
  yn ~ multi_normal_cholesky(zeros, L_f);
}
generated quantities {
  // function scaled back to the original scale
  vector[N2] f = gp_pred_rng(x2n, yn, xn, sigma_f, lengthscale_f, sigman, 1e-9)*ysd + ymean;
  real sigma = sigman*ysd;
}

Compile Stan model

model_gpcovf <- cmdstan_model(stan_file = file_gpcovf)

Data to be passed to Stan

standata_gpcovf <- list(x=mcycle$times,
                        x2=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        N2=length(mcycle$times))

2.2 Optimize and find MAP estimate

opt_gpcovf <- model_gpcovf$optimize(data=standata_gpcovf,
                                    init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpcovf <- as_draws_rvars(opt_gpcovf$draws())
subset(odraws_gpcovf, variable=c('sigma_','lengthscale_','sigma'), regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 4 variables
$sigma_f: rvar<1>[1] mean ± sd:
[1] 0.91 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.39 ± NA 

$sigman: rvar<1>[1] mean ± sd:
[1] 0.47 ± NA 

$sigma: rvar<1>[1] mean ± sd:
[1] 23 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(odraws_gpcovf$f),
         sigma=mean(odraws_gpcovf$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The model fit given optimized parameters, looks reasonable considering the use of homoskedastic residual model.

2.3 Sample using dynamic HMC

fit_gpcovf <- model_gpcovf$sample(data=standata_gpcovf,
                                  iter_warmup=500, iter_sampling=500,
                                  chains=4, parallel_chains=4, refresh=100)

Check whether parameters have reasonable values

draws_gpcovf <- as_draws_rvars(fit_gpcovf$draws())
summarise_draws(subset(draws_gpcovf,
                       variable=c('sigma_','lengthscale_','sigma'),
                       regex=TRUE))
# A tibble: 4 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <num>  <num> <num> <num> <num> <num> <num>    <num>    <num>
1 sigma_f        1.1    1.0  0.31  0.27   0.69  1.7    1.0    1263.    1184.
2 lengthscale_f  0.40   0.41 0.063 0.060  0.30  0.51   1.0    1151.    1172.
3 sigman         0.47   0.47 0.030 0.029  0.42  0.52   1.0    1545.    1411.
4 sigma         23.    23.   1.5   1.4   20.   25.     1.0    1545.    1411.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpcovf$f),
         sigma=mean(draws_gpcovf$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The model fit given integrated parameters looks similar to the optimized one.

Compare the posterior draws to the optimized parameters

odraws_gpcovf <- as_draws_df(opt_gpcovf$draws())
draws_gpcovf %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpcovf,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpcovf$lengthscale_f),
           y=max(draws_gpcovf$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpcovf$lengthscale_f+0.01,
           y=odraws_gpcovf$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

The optimization result is in the middle of the posterior and quite well representative of the low dimensional posterior (in higher dimensions the mean or mode of the posterior is not likely to be representative).

Compare optimized and posterior predictive distributions

odraws_gpcovf <- as_draws_rvars(opt_gpcovf$draws())
mcycle %>%
  mutate(Ef=mean(draws_gpcovf$f),
         sigma=mean(draws_gpcovf$sigma),
         Efo=mean(odraws_gpcovf$f),
         sigmao=mean(odraws_gpcovf$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Efo), color=set1[2])+
  geom_line(aes(y=Efo-2*sigmao), color=set1[2],linetype="dashed")+
  geom_line(aes(y=Efo+2*sigmao), color=set1[2],linetype="dashed")

The model predictions are very similar, and in general GP covariance function and observation model parameters can be quite safely optimized if there are only a few of them and thus marginal posterior is low dimensional and the number of observations is relatively high.

2.4 10% of data

To demonstrate that the optimization is not always safe, we use only 10% of the data for model fitting.

Data to be passed to Stan

mcycle_10p <- mcycle[seq(1,133,by=10),]
standata_10p <- list(x=mcycle_10p$times,
                     x2=mcycle$times,
                     y=mcycle_10p$accel,
                     N=length(mcycle_10p$times),
                     N2=length(mcycle$times))

Optimize and find MAP estimate

opt_10p <- model_gpcovf$optimize(data=standata_10p, init=0.1,
                                 algorithm='lbfgs')

Check whether parameters have reasonable values

odraws_10p <- as_draws_rvars(opt_10p$draws())
subset(odraws_10p, variable=c('sigma_','lengthscale_','sigma'), regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 4 variables
$sigma_f: rvar<1>[1] mean ± sd:
[1] 0.93 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.25 ± NA 

$sigman: rvar<1>[1] mean ± sd:
[1] 0.18 ± NA 

$sigma: rvar<1>[1] mean ± sd:
[1] 8 ± NA 

Compare the model to the data

mcycle_10p %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(data=mcycle,aes(x=times,y=mean(odraws_10p$f)), color=set1[1])+
  geom_line(data=mcycle,aes(x=times,y=mean(odraws_10p$f-2*odraws_10p$sigma)), color=set1[1],
            linetype="dashed")+
  geom_line(data=mcycle,aes(x=times,y=mean(odraws_10p$f+2*odraws_10p$sigma)), color=set1[1],
            linetype="dashed")

The model fit is clearly over-fitted and over-confident.

Sample using dynamic HMC

fit_10p <- model_gpcovf$sample(data=standata_10p,
                               iter_warmup=1000, iter_sampling=1000,
                               adapt_delta=0.95,
                               chains=4, parallel_chains=4, refresh=100)

Check whether parameters have reasonable values

draws_10p <- as_draws_rvars(fit_10p$draws())
summarise_draws(subset(draws_10p, variable=c('sigma_','lengthscale_','sigma'),
                       regex=TRUE))
# A tibble: 4 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <num>  <num> <num> <num> <num> <num> <num>    <num>    <num>
1 sigma_f        0.99   0.96  0.34 0.29   0.45  1.6    1.0    1173.     572.
2 lengthscale_f  0.35   0.29  0.25 0.092  0.15  0.78   1.0    1099.     840.
3 sigman         0.42   0.34  0.27 0.21   0.13  0.98   1.0     920.    1316.
4 sigma         19.    15.   12.   9.4    5.6  44.     1.0     920.    1316.

Compare the model to the data

mcycle_10p %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(data=mcycle,aes(x=times,y=mean(draws_10p$f)), color=set1[1])+
  geom_line(data=mcycle,aes(x=times,y=mean(draws_10p$f-2*draws_10p$sigma)), color=set1[1],
            linetype="dashed")+
  geom_line(data=mcycle,aes(x=times,y=mean(draws_10p$f+2*draws_10p$sigma)), color=set1[1],
            linetype="dashed")

The posterior predictive distribution is much more conservative and shows the uncertainty due to having only a small number of observations.

Compare the posterior draws to the optimized parameters

odraws_10p <- as_draws_df(opt_10p$draws())
draws_10p %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=sigma,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_10p,color=set1[1],size=4)+
  annotate("text",x=median(draws_10p$sigma),
           y=max(draws_10p$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_10p$sigma+0.01,
           y=odraws_10p$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

The optimization result is in the edge of the posterior close to zero residual scale. While there are posterior draws close to zero, integrating over the wide posterior takes into account the uncertainty and the predictions thus are more uncertain, too.

Compare optimized and posterior predictive distributions

odraws_10p <- as_draws_rvars(opt_10p$draws())
mcycle %>%
  mutate(Ef=mean(draws_10p$f),
         sigma=mean(draws_10p$sigma),
         Efo=mean(odraws_10p$f),
         sigmao=mean(odraws_10p$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Efo), color=set1[2])+
  geom_line(aes(y=Efo-2*sigmao), color=set1[2],linetype="dashed")+
  geom_line(aes(y=Efo+2*sigmao), color=set1[2],linetype="dashed")

The figure shows the model prediction given 10% of data, but also the full data as test data. The optimized model is over-fitted and overconfident. Even if the homoskedastic residual is wrong here, the posterior predictive interval covers most of the observation (and in case of good calibration should not cover them all).

3 Heteroskedastic GP with covariance matrices

We next make a model with heteroskedastic residual model using Gaussian process prior also for the logarithm of the residual scale: \[ y \sim \mbox{normal}(f(x), \exp(g(x))\\ f \sim GP(0, K_1)\\ g \sim GP(0, K_2). \]

Now there is no analytical solution as GP prior through the exponential function is not a conjugate prior. In this case we present the latent values of f and g explicitly and sample from the joint posterior of the covariance function parameters, and the latent values. It would be possible also to use Laplace, variational inference, or expectation propagation to integrate over the latent values, but that is another story.

3.1 Model code

file_gpcovfg <- "gpcovfg.stan"
writeLines(readLines(file_gpcovfg))
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  array[N] real xn = to_array_1d((x - xmean)/xsd);
  vector[N] yn = (y - ymean)/ysd;
  real sigma_intercept = 0.1;
  vector[N] jitter = rep_vector(1e-9, N);
}
parameters {
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> lengthscale_g; // lengthscale of g
  real<lower=0> sigma_g;       // scale of g
  vector[N] z_f;
  vector[N] z_g;
}
model {
  // covariances and Cholesky decompositions
  matrix[N, N] K_f = gp_exp_quad_cov(xn, sigma_f, lengthscale_f)+
                     sigma_intercept^2;
  matrix[N, N] L_f = cholesky_decompose(add_diag(K_f, jitter));
  matrix[N, N] K_g = gp_exp_quad_cov(xn, sigma_g, lengthscale_g)+
                     sigma_intercept^2;
  matrix[N, N] L_g = cholesky_decompose(add_diag(K_g, jitter));
  // priors
  z_f ~ std_normal();
  z_g ~ std_normal();
  lengthscale_f ~ lognormal(log(.3), .2);
  lengthscale_g ~ lognormal(log(.5), .2);
  sigma_f ~ normal(0, .5);
  sigma_g ~ normal(0, .5);
  // model
  yn ~ normal(L_f * z_f, exp(L_g * z_g));
}
generated quantities {
  vector[N] f;
  vector[N] sigma;
  {
    // covariances and Cholesky decompositions
    matrix[N, N] K_f = gp_exp_quad_cov(xn, sigma_f, lengthscale_f)+
                       sigma_intercept^2;
    matrix[N, N] L_f = cholesky_decompose(add_diag(K_f, jitter));
    matrix[N, N] K_g = gp_exp_quad_cov(xn, sigma_g, lengthscale_g)+
                       sigma_intercept^2;
    matrix[N, N] L_g = cholesky_decompose(add_diag(K_g, jitter));
    // function scaled back to the original scale
    f = (L_f * z_f)*ysd + ymean;
    sigma = exp(L_g * z_g)*ysd;
  }
}

Compile Stan model

model_gpcovfg <- cmdstan_model(stan_file = file_gpcovfg)

Data to be passed to Stan

standata_gpcovfg <- list(x=mcycle$times,
                         y=mcycle$accel,
                         N=length(mcycle$times))

3.2 Optimize and find MAP estimate

opt_gpcovfg <- model_gpcovfg$optimize(data=standata_gpcovfg,
                                      init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpcovfg <- as_draws_rvars(opt_gpcovfg$draws())
subset(odraws_gpcovfg, variable=c('sigma_','lengthscale_'), regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 4 variables
$sigma_f: rvar<1>[1] mean ± sd:
[1] 1.7 ± NA 

$sigma_g: rvar<1>[1] mean ± sd:
[1] 2 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.11 ± NA 

$lengthscale_g: rvar<1>[1] mean ± sd:
[1] 0.29 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef = mean(odraws_gpcovfg$f),
         sigma = mean(odraws_gpcovfg$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The optimization overfits, as we are now optimizing the joint posterior of 2 covariance function parameters and 2 x 133 latent values.

3.3 Sample using dynamic HMC

fit_gpcovfg <- model_gpcovfg$sample(data=standata_gpcovfg,
                                    iter_warmup=100, iter_sampling=200,
                                    chains=4, parallel_chains=4, refresh=20)

Check whether parameters have reasonable values

draws_gpcovfg <- as_draws_rvars(fit_gpcovfg$draws())
summarise_draws(subset(draws_gpcovfg, variable=c('sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 4 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <num>  <num> <num> <num> <num> <num> <num>    <num>    <num>
1 sigma_f        0.77   0.74 0.15  0.14   0.55  1.1    1.0     353.     479.
2 sigma_g        1.3    1.2  0.22  0.21   0.95  1.6    1.0    1014.     674.
3 lengthscale_f  0.32   0.32 0.041 0.045  0.26  0.39   1.0     210.     372.
4 lengthscale_g  0.51   0.51 0.072 0.068  0.40  0.63   1.0     315.     382.

Compare the model to the data

mcycle %>%
  mutate(Ef = mean(draws_gpcovfg$f),
         sigma = mean(draws_gpcovfg$sigma)) %>%
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good.

Plot posterior draws and posterior mean of the mean function

draws_gpcovfg %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE) +
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpcovfg$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We can also plot the posterior draws of the latent functions, which is a good reminder that individual draws are more wiggly than the average of the draws, and thus show better also the uncertainty, for example, in the edge of the data.

Compare the posterior draws to the optimized parameters

odraws_gpcovfg <- as_draws_df(opt_gpcovfg$draws())
draws_gpcovfg %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpcovfg,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpcovfg$lengthscale_f),
           y=max(draws_gpcovfg$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpcovfg$lengthscale_f+0.01,
           y=odraws_gpcovfg$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

Optimization result is far from being representative of the posterior.

4 Heteroskedastic GP with Hilbert basis functions

The covariance matrix approach requires computation of Cholesky of the covariance matrix which has time cost O(n^3) and this is needs to be done every time the parameters change, which in case of MCMC can be quite many times and thus the computation time can be significant when n grows. One way to speed up the computation in low dimensional covariate case is to use basis function approximation which changes the GP to a linear model. Here we use Hilbert space basis functions. With increasing number of basis functions and factor c, the approximation error can be made arbitrarily small. Sufficient accuracy and significant saving in the computation speed is often achieveved with a relatively small number of basis functions.

4.1 Illustrate the basis functions

Code

filebf0 <- "gpbf0.stan"
writeLines(readLines(filebf0))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real xsd = sd(x);
  vector[N] xn = (x - xmean)/xsd;
  // Basis functions for f
  real L_f = c_f*max(xn);
}
generated quantities {
  // Basis functions for f
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
  // spectral densities
  vector[M_f] diagSPD_EQ_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
  vector[M_f] diagSPD_Matern32_f = diagSPD_Matern32(sigma_f, lengthscale_f, L_f, M_f);
}

The model code includes Hilbert space basis function helpers

writeLines(readLines("gpbasisfun_functions.stan"))
vector diagSPD_EQ(real alpha, real rho, real L, int M) {
  return alpha * sqrt(sqrt(2*pi()) * rho) * exp(-0.25*(rho*pi()/2/L)^2 * linspaced_vector(M, 1, M)^2);
}
vector diagSPD_Matern32(real alpha, real rho, real L, int M) {
   return 2*alpha * (sqrt(3)/rho)^1.5 * inv((sqrt(3)/rho)^2 + ((pi()/2/L) * linspaced_vector(M, 1, M))^2);
}
vector diagSPD_periodic(real alpha, real rho, int M) {
  real a = 1/rho^2;
  vector[M] q = exp(log(alpha) + 0.5 * (log(2) - a + to_vector(log_modified_bessel_first_kind(linspaced_int_array(M, 1, M), a))));
  return append_row(q,q);
}
matrix PHI(int N, int M, real L, vector x) {
  return sin(diag_post_multiply(rep_matrix(pi()/(2*L) * (x+L), M), linspaced_vector(M, 1, M)))/sqrt(L);
}
matrix PHI_periodic(int N, int M, real w0, vector x) {
  matrix[N,M] mw0x = diag_post_multiply(rep_matrix(w0*x, M), linspaced_vector(M, 1, M));
  return append_col(cos(mw0x), sin(mw0x));
}

Compile basis function generation code

modelbf0 <- cmdstan_model(stan_file = filebf0, include_paths = ".")

Data to be passed to Stan

standatabf0 <- list(x=seq(0,1,length.out=100),
                    N=100,
                    c_f=3, # factor c of basis functions for GP for f1
                    M_f=160,  # number of basis functions for GP for f1
                    sigma_f=1,
                    lengthscale_f=1) 

Generate basis functions

fixbf0 <- modelbf0$sample(data=standatabf0, fixed_param=TRUE,
                          chains=1, iter=1, iter_sampling=1)
Running MCMC with 1 chain...

Chain 1 Iteration: 1 / 1 [100%]  (Sampling) 
Chain 1 finished in 0.0 seconds.

There is certainly easier way to do this, but this is what I came up quickly

q<-subset(fixbf0$draws(), variable="PHI_f") %>%
  as_draws_matrix() %>%
  as.numeric()%>%
  matrix(nrow=100,ncol=160)%>%
  as.data.frame()
id <- rownames(q)
q <- cbind(x=as.numeric(id), q)
q <- q %>%
  pivot_longer(!x,
               names_to="ind",
               names_transform = list(ind = readr::parse_number),
               values_to="f")%>%
  mutate(x=x/100)

Plot the first 6 basis functions. These are just sine and cosine functions with different frequencies and truncated to a pre-defined box.

q %>%
  filter(ind<=6) %>%
  ggplot(aes(x=x, y=f, group=ind, color=factor(ind))) +
  geom_line()+
  geom_text_repel(data=filter(q, ind<=6 & x==0.01),aes(x=-0.01,y=f,label=ind),
                  direction="y")+
  geom_text_repel(data=filter(q, ind<=6 & x==1),aes(x=1.02,y=f,label=ind),
                  direction="y")+
  theme(legend.position="none")

The first 8 spectral densities for exponentiated quadratic covariance function with sigma_f=1 and lengthscale_f=1. These spectral densities give a prior weight for each basis function. Bigger weights on the smoother basis functions thus imply a prior on function space favoring smoother functions.

spd_EQ <- as.matrix(fixbf0$draws(variable='diagSPD_EQ_f'))
round(spd_EQ[1:12],2)
 [1] 1.55 1.44 1.28 1.09 0.88 0.68 0.50 0.35 0.24 0.15 0.09 0.05

The first 8 spectral densities for Matern-3/2 covariance function with sigma_f=1 and lengthscale_f=1. The spectral density values go down much slower than for the exponentiated quadratic covariance function, which is natural as Matern-3/2 is less smooth.

spd_Matern32 <- as.matrix(fixbf0$draws(variable='diagSPD_Matern32_f'))
round(spd_Matern32[1:12],2)
 [1] 1.47 1.35 1.18 1.01 0.85 0.71 0.60 0.51 0.43 0.37 0.32 0.28

Plot 4 random draws from the prior on function space with exponentiated quadratic covariance function and sigma_f=1 and lengthscale_f=1. The basis function approximation is just a linear model, with the basis functions weighted by the spectral densities depending on the sigma_f and lengthscale_f, and the prior for the linear model coefficients is simply independent normal(0,1).

set.seed(365)
qr <- bind_rows(lapply(1:4, function(i) {
  q %>%
    mutate(r=rep(rnorm(160),times=100),fr=f*r*spd_EQ[ind]) %>%
    group_by(x) %>%
    summarise(f=sum(fr)) %>%
    mutate(ind=i) }))
qr %>%
  ggplot(aes(x=x, y=f, group=ind, color=factor(ind))) +
  geom_line()+
  geom_text_repel(data=filter(qr, x==0.01),aes(x=-0.01,y=f,label=ind),
                  direction="y")+
  geom_text_repel(data=filter(qr, x==1),aes(x=1.02,y=f,label=ind),
                  direction="y")+
  theme(legend.position="none")

Plot 4 random draws from the prior on function space with Matern-3/2 covariance function and sigma_f=1 and lengthscale_f=1. The same random number generator seed was used so that you can compare this plot to the above one. Matern-3/2 had more prior mass on higher frequencies and the prior draws are more wiggly.

set.seed(365)
qr <- bind_rows(lapply(1:4, function(i) {
  q %>%
    mutate(r=rep(rnorm(160),times=100),fr=f*r*spd_Matern32[ind]) %>%
    group_by(x) %>%
    summarise(f=sum(fr)) %>%
    mutate(ind=i) }))
qr %>%
  ggplot(aes(x=x, y=f, group=ind, color=factor(ind))) +
  geom_line()+
  geom_text_repel(data=filter(qr, x==0.01),aes(x=-0.01,y=f,label=ind),
                  direction="y")+
  geom_text_repel(data=filter(qr, x==1),aes(x=1.02,y=f,label=ind),
                  direction="y")+
  theme(legend.position="none")

Let’s do the same with lengthscale_f=0.3

standatabf0 <- list(x=seq(0,1,length.out=100),
                    N=100,
                    c_f=1.5, # factor c of basis functions for GP for f1
                    M_f=160,  # number of basis functions for GP for f1
                    sigma_f=1,
                    lengthscale_f=0.3) 
fixbf0 <- modelbf0$sample(data=standatabf0, fixed_param=TRUE,
                          chains=1, iter=1, iter_sampling=1)
Running MCMC with 1 chain...

Chain 1 Iteration: 1 / 1 [100%]  (Sampling) 
Chain 1 finished in 0.0 seconds.

The basis functions are exactly the same, and only the spectral densities have changed. Now the weight doesn’t drop as fast for the more wiggly basis functions.

spd_EQ <- as.matrix(fixbf0$draws(variable='diagSPD_EQ_f'))
round(spd_EQ[1:15],2)
 [1] 0.86 0.84 0.80 0.76 0.70 0.64 0.57 0.50 0.44 0.37 0.31 0.26 0.21 0.16 0.13
spd_Matern32 <- as.matrix(fixbf0$draws(variable='diagSPD_Matern32_f'))
round(spd_Matern32[1:15],2)
 [1] 0.82 0.80 0.76 0.70 0.65 0.59 0.54 0.48 0.43 0.39 0.35 0.32 0.29 0.26 0.23

Plot 4 random draws from the prior on function space with exponentiated quadratic covariance function and sigma_f=1 and lengthscale_f=0.3. The random functions from the prior are now more wiggly. The same random number generator seed was used so that you can compare this plot to the above one. Above the prior draw number 2 looks like a decreasing slope. Here the prior draw number 2 still has downward trend, but is more wiggly. The same random draw from the coefficient space produces a wigglier function as the spectral densities go down slower for the more wiggly basis functions.

set.seed(365)
qr <- bind_rows(lapply(1:4, function(i) {
  q %>%
    mutate(r=rep(rnorm(160),times=100),fr=f*r*spd_EQ[ind]) %>%
    group_by(x) %>%
    summarise(f=sum(fr)) %>%
    mutate(ind=i) }))
qr %>%
  ggplot(aes(x=x, y=f, group=ind, color=factor(ind))) +
  geom_line()+
  geom_text_repel(data=filter(qr, x==0.01),aes(x=-0.01,y=f,label=ind),
                  direction="y")+
  geom_text_repel(data=filter(qr, x==1),aes(x=1.02,y=f,label=ind),
                  direction="y")+
  theme(legend.position="none")

Plot 4 random draws from the prior on function space with Matern-3/2 covariance function and sigma_f=1 and lengthscale_f=0.3. The prior draws are more wiggly than with exponentiated quadratic.

set.seed(365)
qr <- bind_rows(lapply(1:4, function(i) {
  q %>%
    mutate(r=rep(rnorm(160),times=100),fr=f*r*spd_Matern32[ind]) %>%
    group_by(x) %>%
    summarise(f=sum(fr)) %>%
    mutate(ind=i) }))
qr %>%
  ggplot(aes(x=x, y=f, group=ind, color=factor(ind))) +
  geom_line()+
  geom_text_repel(data=filter(qr, x==0.01),aes(x=-0.01,y=f,label=ind),
                  direction="y")+
  geom_text_repel(data=filter(qr, x==1),aes(x=1.02,y=f,label=ind),
                  direction="y")+
  theme(legend.position="none")

4.2 GP with basis functions for f

Model code

file_gpbff <- "gpbff.stan"
writeLines(readLines(file_gpbff))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  vector[N] xn = (x - xmean)/xsd;
  vector[N] yn = (y - ymean)/ysd;
  // Basis functions for f
  real L_f = c_f*max(xn);
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
}
parameters {
  real intercept_f;
  vector[M_f] beta_f;          // the basis functions coefficients
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> sigman;         // noise sigma
}
model {
  // spectral densities for f and g
  vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
  // priors
  intercept_f ~ normal(0, 0.1);
  beta_f ~ normal(0, 1);
  lengthscale_f ~ normal(0, 1);
  sigma_f ~ normal(0, 1);
  sigman ~ normal(0, 1);
  // model
  yn ~ normal(intercept_f + PHI_f * (diagSPD_f .* beta_f), sigman);
}
generated quantities {
  vector[N] f;
  vector[N] log_lik;
  real sigma = sigman*ysd;
  {
    // spectral densities
    vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
    // function scaled back to the original scale
    f = (intercept_f + PHI_f * (diagSPD_f .* beta_f))*ysd + ymean;
    for (n in 1:N) {
      log_lik[n] = normal_lpdf(yn[n] | intercept_f + PHI_f[n] * (diagSPD_f .* beta_f),
          sigman);
    }
  }
}

Compile Stan model

model_gpbff <- cmdstan_model(stan_file = file_gpbff, include_paths = ".", stanc_options = list("O1"))

Data to be passed to Stan

standata_gpbff <- list(x=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        c_f=1.5, # factor c of basis functions for GP for f1
                        M_f=40,  # number of basis functions for GP for f1
                        c_g=1.5, # factor c of basis functions for GP for g3
                        M_g=40)  # number of basis functions for GP for g3

4.3 Optimize and find MAP estimate

opt_gpbff <- model_gpbff$optimize(data=standata_gpbff,
                                    init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpbff <- as_draws_rvars(opt_gpbff$draws())
subset(odraws_gpbff, variable=c('intercept','sigma_','lengthscale_'),
       regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 3 variables
$intercept_f: rvar<1>[1] mean ± sd:
[1] 0.0088 ± NA 

$sigma_f: rvar<1>[1] mean ± sd:
[1] 1.8 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.15 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(odraws_gpbff$f),
         sigma=mean(odraws_gpbff$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The optimization is not that bad. We are now optimizing the joint posterior of 1 covariance function parameters and 40 basis function co-efficients.

4.4 Sample using dynamic HMC

fit_gpbff <- model_gpbff$sample(data=standata_gpbff,
                                  iter_warmup=500, iter_sampling=500, refresh=100,
                                  chains=4, parallel_chains=4, adapt_delta=0.9)

Check whether parameters have reasonable values

draws_gpbff <- as_draws_rvars(fit_gpbff$draws())
summarise_draws(subset(draws_gpbff,
                       variable=c('intercept','sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 3 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <num>  <num> <num> <num> <num> <num> <num>    <num>    <num>
1 intercept_f   0.016  0.017 0.10  0.11  -0.15  0.17   1.0    2764.    1431.
2 sigma_f       1.0    0.97  0.28  0.25   0.66  1.6    1.0     908.    1261.
3 lengthscale_f 0.40   0.40  0.061 0.062  0.30  0.50   1.0    1228.    1186.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpbff$f),
         sigma=mean(draws_gpbff$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good. The model fit is clearly more smooth than with optimization.

Plot posterior draws and posterior mean of the mean function

draws_gpbff %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE)+
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpbff$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We can also plot the posterior draws of the latent functions, which is a good reminder that individual draws are more wiggly than the average of the draws, and thus show better also the uncertainty, for example, in the edge of the data.

Compare the posterior draws to the optimized parameters

odraws_gpbff <- as_draws_df(opt_gpbff$draws())
draws_gpbff %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpbff,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpbff$lengthscale_f),
           y=max(draws_gpbff$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpbff$lengthscale_f+0.01,
           y=odraws_gpbff$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

Optimization result is far from being representative of the posterior.

4.5 GP with basis functions for f and g

Model code

file_gpbffg <- "gpbffg.stan"
writeLines(readLines(file_gpbffg))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
  real<lower=0> c_g;   // factor c to determine the boundary value L
  int<lower=1> M_g;    // number of basis functions
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  vector[N] xn = (x - xmean)/xsd;
  vector[N] yn = (y - ymean)/ysd;
  // Basis functions for f
  real L_f = c_f*max(xn);
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
  // Basis functions for g
  real L_g= c_g*max(xn);
  matrix[N,M_g] PHI_g = PHI(N, M_g, L_g, xn);
}
parameters {
  real intercept_f;
  real intercept_g;
  vector[M_f] beta_f;          // the basis functions coefficients
  vector[M_g] beta_g;          // the basis functions coefficients
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> lengthscale_g; // lengthscale of g
  real<lower=0> sigma_g;       // scale of g
}
model {
  // spectral densities for f and g
  vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
  vector[M_g] diagSPD_g = diagSPD_EQ(sigma_g, lengthscale_g, L_g, M_g);
  // priors
  intercept_f ~ normal(0, .1);
  intercept_g ~ normal(0, .1);
  beta_f ~ normal(0, 1);
  beta_g ~ normal(0, 1);
  lengthscale_f ~ normal(0, 1);
  lengthscale_g ~ normal(0, 1);
  sigma_f ~ normal(0, .5);
  sigma_g ~ normal(0, .5);
  // model
  yn ~ normal(intercept_f + PHI_f * (diagSPD_f .* beta_f),
          exp(intercept_g + PHI_g * (diagSPD_g .* beta_g)));
}
generated quantities {
  vector[N] f;
  vector[N] sigma;
  vector[N] log_lik;
  {
    // spectral densities
    vector[M_f] diagSPD_f = diagSPD_EQ(sigma_f, lengthscale_f, L_f, M_f);
    vector[M_g] diagSPD_g = diagSPD_EQ(sigma_g, lengthscale_g, L_g, M_g);
    // function scaled back to the original scale
    f = (intercept_f + PHI_f * (diagSPD_f .* beta_f))*ysd + ymean;
    sigma = exp(intercept_g + PHI_g * (diagSPD_g .* beta_g))*ysd;
    for (n in 1:N) {
      log_lik[n] = normal_lpdf(yn[n] | intercept_f + PHI_f[n] * (diagSPD_f .* beta_f),
          exp(intercept_g + PHI_g[n] * (diagSPD_g .* beta_g)));
    }
  }
}

Compile Stan model

model_gpbffg <- cmdstan_model(stan_file = file_gpbffg, include_paths = ".", stanc_options = list("O1"))

Data to be passed to Stan

standata_gpbffg <- list(x=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        c_f=1.5, # factor c of basis functions for GP for f1
                        M_f=40,  # number of basis functions for GP for f1
                        c_g=1.5, # factor c of basis functions for GP for g3
                        M_g=40)  # number of basis functions for GP for g3

4.6 Optimize and find MAP estimate

opt_gpbffg <- model_gpbffg$optimize(data=standata_gpbffg,
                                    init=0.1, algorithm='bfgs')

Check whether parameters have reasonable values

odraws_gpbffg <- as_draws_rvars(opt_gpbffg$draws())
subset(odraws_gpbffg, variable=c('intercept','sigma_','lengthscale_'),
       regex=TRUE)
# A draws_rvars: 1 iterations, 1 chains, and 6 variables
$intercept_f: rvar<1>[1] mean ± sd:
[1] 0.021 ± NA 

$intercept_g: rvar<1>[1] mean ± sd:
[1] -0.065 ± NA 

$sigma_f: rvar<1>[1] mean ± sd:
[1] 1.5 ± NA 

$sigma_g: rvar<1>[1] mean ± sd:
[1] 4 ± NA 

$lengthscale_f: rvar<1>[1] mean ± sd:
[1] 0.11 ± NA 

$lengthscale_g: rvar<1>[1] mean ± sd:
[1] 0.1 ± NA 

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(odraws_gpbffg$f),
         sigma=mean(odraws_gpbffg$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The optimization overfits, as we are now optimizing the joint posterior of 2 covariance function parameters and 2 x 40 basis function co-efficients.

4.7 Sample using dynamic HMC

fit_gpbffg <- model_gpbffg$sample(data=standata_gpbffg,
                                  iter_warmup=500, iter_sampling=500, refresh=100,
                                  chains=4, parallel_chains=4, adapt_delta=0.9)

Check whether parameters have reasonable values

draws_gpbffg <- as_draws_rvars(fit_gpbffg$draws())
summarise_draws(subset(draws_gpbffg,
                       variable=c('intercept','sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 6 × 10
  variable        mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>          <num>  <num> <num> <num> <num> <num> <num>    <num>    <num>
1 intercept_f    0.029  0.031 0.097 0.096 -0.13  0.19   1.0    1617.    1269.
2 intercept_g   -0.044 -0.046 0.10  0.097 -0.21  0.13   1.0    2845.    1323.
3 sigma_f        0.80   0.78  0.16  0.15   0.58  1.1    1.0     992.    1134.
4 sigma_g        1.3    1.2   0.23  0.22   0.93  1.7    1.0    1169.    1233.
5 lengthscale_f  0.34   0.33  0.050 0.052  0.26  0.42   1.0     634.    1133.
6 lengthscale_g  0.51   0.51  0.10  0.10   0.34  0.68   1.0     756.    1119.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpbffg$f),
         sigma=mean(draws_gpbffg$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good.

Plot posterior draws and posterior mean of the mean function

draws_gpbffg %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE)+
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpbffg$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We can also plot the posterior draws of the latent functions, which is a good reminder that individual draws are more wiggly than the average of the draws, and thus show better also the uncertainty, for example, in the edge of the data.

Compare the posterior draws to the optimized parameters

odraws_gpbffg <- as_draws_df(opt_gpbffg$draws())
draws_gpbffg %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=lengthscale_f,y=sigma_f))+
  geom_point(color=set1[2])+
  geom_point(data=odraws_gpbffg,color=set1[1],size=4)+
  annotate("text",x=median(draws_gpbffg$lengthscale_f),
           y=max(draws_gpbffg$sigma_f)+0.1,
           label='Posterior draws',hjust=0.5,color=set1[2],size=6)+
  annotate("text",x=odraws_gpbffg$lengthscale_f+0.01,
           y=odraws_gpbffg$sigma_f,
           label='Optimized',hjust=0,color=set1[1],size=6)

Optimization result is far from being representative of the posterior.

4.8 Model comparison

Looking at the plots comparing model predictions and data, it is quite obvious in this case that the heteroskedastic model is better for these data. In cases when it is not as clear, we can use leave-one-out cross-validation comparison. Here we compare homoskedastic and heteroskedastic models.

loobff <- fit_gpbff$loo()
loobffg <- fit_gpbffg$loo()
loo_compare(list(homoskedastic=loobff,heteroskedastic=loobffg))
                elpd_diff se_diff
heteroskedastic   0.0       0.0  
homoskedastic   -49.5      10.0  

Heteroskedastic model has clearly much higher elpd estimate.

We can plot also the difference in the pointwise elpd values (log scores) so that we see in which parts the heteroskedastic model is better

data.frame(time=mcycle$times,
           elpd_diff=loobffg$pointwise[,'elpd_loo']-loobff$pointwise[,'elpd_loo']) |>
  ggplot(aes(x=time,y=elpd_diff))+
  geom_point(color=set1[2])+
  geom_hline(yintercept=0, linetype="dashed")+
  labs(x="Time (ms)", y=TeX("elpd of heteroskedastic GP is higher $\\rightarrow$"))

4.9 Variational inference

Variational inference is popular in machine learning and also with Gaussian processes. When used carefully for selected models, parameters, parameterization, and approximate distribution, variational inference can be useful and fast. The following example illustrates, why it can also fail when applied in black box style. Run auto-differentiated variational inference (ADVI) with meanfield normal approximation, and in the end, sample from the approximation.

vi_gpbffg <- model_gpbffg$variational(data=standata_gpbffg,
                                      init=0.01, tol_rel_obj=1e-4, iter=1e5, refresh=1000, seed=75)

Check whether parameters have reasonable values

vidraws_gpbffg <- as_draws_rvars(vi_gpbffg$draws())
summarise_draws(subset(vidraws_gpbffg,
                       variable=c('intercept','sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 6 × 10
  variable        mean median    sd   mad     q5   q95  rhat ess_bulk ess_tail
  <chr>          <num>  <num> <num> <num>  <num> <num> <num>    <num>    <num>
1 intercept_f    0.031  0.032 0.029 0.028 -0.017 0.081   1.0     931.    1031.
2 intercept_g   -0.039 -0.039 0.057 0.055 -0.13  0.054   1.0     975.    1057.
3 sigma_f        0.66   0.65  0.032 0.032  0.61  0.71    1.0     935.     951.
4 sigma_g        0.93   0.93  0.070 0.072  0.82  1.0     1.0     861.     919.
5 lengthscale_f  0.39   0.39  0.020 0.020  0.36  0.42    1.0     986.     946.
6 lengthscale_g  1.4    1.4   0.088 0.085  1.2   1.5     1.0     982.     983.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(vidraws_gpbffg$f),
         sigma=mean(vidraws_gpbffg$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

ADVI inference is catching the mean function well, and some of the varying noise variance, but clearly overestimating the noise variance in the early part.

Plot posterior draws and posterior mean of the mean function

vidraws_gpbffg %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE)+
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(vidraws_gpbffg$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We can also plot the posterior draws of the latent functions, which is a good reminder that individual draws are more wiggly than the average of the draws, and thus show better also the uncertainty, for example, in the edge of the data.

Compare the draws from the variational approximation to the MCMC draws and optimized parameters. This time show f[1] and g[1] to illustrate the challenging funnel shape. Although the inference happens in the space of beta_f and beta_g, f[1] and g[1] are linear projection of beta_f and beta_g, and thus the funnel is causing the problems for ADVI. Full rank normal approximation would not be able to help here.

odraws_gpbffg <- as_draws_df(opt_gpbffg$draws())
draws_gpbffg %>%
  thin_draws(thin=5) %>%
  as_draws_df() %>%
  ggplot(aes(x=`f[1]`,y=log(`sigma[1]`)))+
  geom_point(color=set1[2])+
  geom_point(data=as_draws_df(vidraws_gpbffg),color=set1[3])+
  geom_point(data=odraws_gpbffg,color=set1[1],size=4)+
  annotate("text",x=median(vidraws_gpbffg$f[1])+1.3,
           y=max(log(vidraws_gpbffg$sigma[1]))+0.1,
           label='Variational inference',hjust=0,color=set1[3],size=6)+
  annotate("text",x=median(draws_gpbffg$f[1])+1,
           y=min(log(draws_gpbffg$sigma[1]))-0.1,
           label='MCMC draws',hjust=0,color=set1[2],size=6)+
  annotate("text",x=odraws_gpbffg$`f[1]`+1,
           y=log(odraws_gpbffg$`sigma[1]`),
           label='Optimized',hjust=0,color=set1[1],size=6)+
  labs(y="g[1]")

5 Heteroskedastic GP with Matern covariance function and Hilbert basis functions

Exponentiated quadratic is sometimes considered to be too smooth as all the derivatives are continuos. For comparison we use Matern-3/2 covariance. The Hilbert space basis functions are the same and only the spectral density values change (that is different basis functions have a different weighting).

5.1 Model code

file_gpbffg2 <- "gpbffg_matern.stan"
writeLines(readLines(file_gpbffg2))
functions {
#include gpbasisfun_functions.stan
}
data {
  int<lower=1> N;      // number of observations
  vector[N] x;         // univariate covariate
  vector[N] y;         // target variable
        
  real<lower=0> c_f;   // factor c to determine the boundary value L
  int<lower=1> M_f;    // number of basis functions
  real<lower=0> c_g;   // factor c to determine the boundary value L
  int<lower=1> M_g;    // number of basis functions
}
transformed data {
  // Normalize data
  real xmean = mean(x);
  real ymean = mean(y);
  real xsd = sd(x);
  real ysd = sd(y);
  vector[N] xn = (x - xmean)/xsd;
  vector[N] yn = (y - ymean)/ysd;
  // Basis functions for f
  real L_f = c_f*max(xn);
  matrix[N,M_f] PHI_f = PHI(N, M_f, L_f, xn);
  // Basis functions for g
  real L_g= c_g*max(xn);
  matrix[N,M_g] PHI_g = PHI(N, M_g, L_g, xn);
}
parameters {
  real intercept_f;
  real intercept_g;
  vector[M_f] beta_f;          // the basis functions coefficients
  vector[M_g] beta_g;          // the basis functions coefficients
  real<lower=0> lengthscale_f; // lengthscale of f
  real<lower=0> sigma_f;       // scale of f
  real<lower=0> lengthscale_g; // lengthscale of g
  real<lower=0> sigma_g;       // scale of g
}
model {
  // spectral densities for f and g
  vector[M_f] diagSPD_f = diagSPD_Matern32(sigma_f, lengthscale_f, L_f, M_f);
  vector[M_g] diagSPD_g = diagSPD_Matern32(sigma_g, lengthscale_g, L_g, M_g);
  // priors
  intercept_f ~ normal(0, 1);
  intercept_g ~ normal(0, 1);
  beta_f ~ normal(0, 1);
  beta_g ~ normal(0, 1);
  lengthscale_f ~ normal(0, 1);
  lengthscale_g ~ normal(0, 1);
  sigma_f ~ normal(0, .5);
  sigma_g ~ normal(0, .5);
  // model
  yn ~ normal(intercept_f + PHI_f * (diagSPD_f .* beta_f),
          exp(intercept_g + PHI_g * (diagSPD_g .* beta_g)));
}
generated quantities {
  vector[N] f;
  vector[N] sigma;
  vector[N] log_lik;
  {
    // spectral densities
    vector[M_f] diagSPD_f = diagSPD_Matern32(sigma_f, lengthscale_f, L_f, M_f);
    vector[M_g] diagSPD_g = diagSPD_Matern32(sigma_g, lengthscale_g, L_g, M_g);
    // function scaled back to the original scale
    f = (intercept_f + PHI_f * (diagSPD_f .* beta_f))*ysd + ymean;
    sigma = exp(intercept_g + PHI_g * (diagSPD_g .* beta_g))*ysd;
    for (n in 1:N) {
      log_lik[n] = normal_lpdf(yn[n] | intercept_f + PHI_f[n] * (diagSPD_f .* beta_f),
          exp(intercept_g + PHI_g[n] * (diagSPD_g .* beta_g)));
    }
  }
}

Compile Stan model

model_gpbffg2 <- cmdstan_model(stan_file = file_gpbffg2, include_paths = ".")

Data to be passed to Stan

standata_gpbffg2 <- list(x=mcycle$times,
                        y=mcycle$accel,
                        N=length(mcycle$times),
                        c_f=1.5, # factor c of basis functions for GP for f1
                        M_f=160,  # number of basis functions for GP for f1
                        c_g=1.5, # factor c of basis functions for GP for g3
                        M_g=160)  # number of basis functions for GP for g3

5.2 Sample using dynamic HMC

fit_gpbffg2 <- model_gpbffg2$sample(data=standata_gpbffg2,
                                  iter_warmup=500, iter_sampling=500,
                                  chains=4, parallel_chains=4, adapt_delta=0.9)

Check whether parameters have reasonable values

draws_gpbffg2 <- as_draws_rvars(fit_gpbffg2$draws())
summarise_draws(subset(draws_gpbffg2,
                       variable=c('intercept','sigma_','lengthscale_'),
                       regex=TRUE))
# A tibble: 6 × 10
  variable       mean median    sd   mad    q5   q95  rhat ess_bulk ess_tail
  <chr>         <num>  <num> <num> <num> <num> <num> <num>    <num>    <num>
1 intercept_f    0.27   0.28  0.46  0.42 -0.48  1.0    1.0     843.    1044.
2 intercept_g   -1.2   -1.3   0.52  0.48 -2.0  -0.35   1.0    1248.    1278.
3 sigma_f        0.93   0.89  0.21  0.21  0.62  1.3    1.0     955.     748.
4 sigma_g        1.1    1.0   0.23  0.22  0.73  1.5    1.0    1032.    1403.
5 lengthscale_f  0.66   0.64  0.15  0.14  0.43  0.93   1.0     930.    1025.
6 lengthscale_g  0.69   0.66  0.23  0.22  0.37  1.1    1.0     690.     577.

Compare the model to the data

mcycle %>%
  mutate(Ef=mean(draws_gpbffg2$f),
         sigma=mean(draws_gpbffg2$sigma)) %>%  
  ggplot(aes(x=times,y=accel))+
  geom_point()+
  labs(x="Time (ms)", y="Acceleration (g)")+
  geom_line(aes(y=Ef), color=set1[1])+
  geom_line(aes(y=Ef-2*sigma), color=set1[1],linetype="dashed")+
  geom_line(aes(y=Ef+2*sigma), color=set1[1],linetype="dashed")

The MCMC integration works well and the model fit looks good.

Plot posterior draws and posterior mean of the mean function

draws_gpbffg2 %>%
  thin_draws(thin=5) %>%
  spread_rvars(f[i]) %>%
  unnest_rvars() %>%
  mutate(time=mcycle$times[i]) %>%
  ggplot(aes(x=time, y=f, group = .draw)) +
  geom_line(color=set1[2], alpha = 0.1) +
  geom_point(data=mcycle, mapping=aes(x=times,y=accel), inherit.aes=FALSE)+
  geom_line(data=mcycle, mapping=aes(x=times,y=mean(draws_gpbffg2$f)),
            inherit.aes=FALSE, color=set1[1], size=1)+
  labs(x="Time (ms)", y="Acceleration (g)")

We see that when using Matern-3/2 covariance instead of the exponentiated quadratic, the model fit is more wigggly.

LS0tCnRpdGxlOiAiR2F1c3NpYW4gcHJvY2VzcyBkZW1vbnN0cmF0aW9uIHdpdGggU3RhbiIKYXV0aG9yOiAiW0FraSBWZWh0YXJpXShodHRwczovL3VzZXJzLmFhbHRvLmZpL35hdmUvKSIKZGF0ZTogIkZpcnN0IHZlcnNpb24gMjAyMS0wMS0yOC4gTGFzdCBtb2RpZmllZCBgciBmb3JtYXQoU3lzLkRhdGUoKSlgLiIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICBib290c3RyYXBfdmVyc2lvbjogNAogICAgdGhlbWU6IHJlYWRhYmxlCiAgICBmb250LXNpemUtYmFzZTogMS41cmVtCiAgICB0b2M6IHRydWUKICAgIHRvY19kZXB0aDogMgogICAgbnVtYmVyX3NlY3Rpb25zOiBUUlVFCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGNvZGVfZG93bmxvYWQ6IHRydWUKICAgIGtlZXBfbWQ6IHRydWUKLS0tCkRlbW9uc3RyYXRpb24gb2YgY292YXJpYW5jZSBtYXRyaXggYW5kIGJhc2lzIGZ1bmN0aW9uCmltcGxlbWVudGF0aW9uIG9mIEdhdXNzaWFuIHByb2Nlc3MgbW9kZWwgaW4gU3Rhbi4KClRoZSBiYXNpY3Mgb2YgdGhlIGNvdmFyaWFuY2UgbWF0cml4IGFwcHJvYWNoIGlzIGJhc2VkIG9uIHRoZSBDaGFwdGVyCjEwIG9mIFN0YW4gVXNlcuKAmXMgR3VpZGUsIFZlcnNpb24gMi4yNiBieSBTdGFuIERldmVsb3BtZW50IFRlYW0KKDIwMjEpLiBodHRwczovL21jLXN0YW4ub3JnL2RvY3Mvc3Rhbi11c2Vycy1ndWlkZS8KClRoZSBiYXNpY3Mgb2YgdGhlIEhpbGJlcnQgc3BhY2UgYmFzaXMgZnVuY3Rpb24gYXBwcm94aW1hdGlvbiBpcwpiYXNlZCBvbiBSaXV0b3J0LU1heW9sLCBCw7xya25lciwgQW5kZXJzZW4sIFNvbGluLCBhbmQgVmVodGFyaQooMjAyMCkuIFByYWN0aWNhbCBIaWxiZXJ0IHNwYWNlIGFwcHJveGltYXRlIEJheWVzaWFuIEdhdXNzaWFuCnByb2Nlc3NlcyBmb3IgcHJvYmFiaWxpc3RpYyBwcm9ncmFtbWluZy4gaHR0cHM6Ly9hcnhpdi5vcmcvYWJzLzIwMDQuMTE0MDgKCiMgTW90b3JjeWNsZSBhY2NpZGVudCBhY2NlbGVyYXRpb24gZGF0YQoKRGF0YSBhcmUgbWVhc3VyZW1lbnRzIG9mIGhlYWQgYWNjZWxlcmF0aW9uIGluIGEgc2ltdWxhdGVkCm1vdG9yY3ljbGUgYWNjaWRlbnQsIHVzZWQgdG8gdGVzdCBjcmFzaCBoZWxtZXRzLgoKRGF0YSBhcmUgbW9kZWxsZWQgZmlyc3Qgd2l0aCBub3JtYWwgZGlzdHJpYnV0aW9uIGhhdmluZyBHYXVzc2lhbiBwcm9jZXNzCnByaW9yIG9uIG1lYW46CiQkCnkgXHNpbSBcbWJveHtub3JtYWx9KGYoeCksIFxzaWdtYSlcXApmIFxzaW0gR1AoMCwgS18xKVxcClxzaWdtYSBcc2ltIFxtYm94e25vcm1hbH1eeyt9KDAsIDEpLAokJAphbmQgdGhlbiB3aXRoIG5vcm1hbCBkaXN0cmlidXRpb24gaGF2aW5nIEdhdXNzaWFuIHByb2Nlc3MKcHJpb3Igb24gbWVhbiBhbmQgbG9nIHN0YW5kYXJkIGRldmlhdGlvbjoKJCQKeSBcc2ltIFxtYm94e25vcm1hbH0oZih4KSwgXGV4cChnKHgpKVxcCmYgXHNpbSBHUCgwLCBLXzEpXFwKZyBcc2ltIEdQKDAsIEtfMikuCiQkCgoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChtZXNzYWdlPUZBTFNFLCBlcnJvcj1GQUxTRSwgd2FybmluZz1GQUxTRSwgY29tbWVudD1OQSwgY2FjaGU9RkFMU0UpCmBgYAoKIyMjIExvYWQgcGFja2FnZXMgey51bm51bWJlcmVkfQoKYGBge3IgfQpsaWJyYXJ5KGNtZHN0YW5yKSAKbGlicmFyeShwb3N0ZXJpb3IpCmxpYnJhcnkobG9vKQpsaWJyYXJ5KHRpZHliYXllcykKb3B0aW9ucyhwaWxsYXIubmVnID0gRkFMU0UsIHBpbGxhci5zdWJ0bGU9RkFMU0UsIHBpbGxhci5zaWdmaWc9MikKbGlicmFyeSh0aWR5cikgCmxpYnJhcnkoZHBseXIpIApsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoZ2dyZXBlbCkKbGlicmFyeShsYXRleDJleHApCmxpYnJhcnkoYmF5ZXNwbG90KQp0aGVtZV9zZXQoYmF5ZXNwbG90Ojp0aGVtZV9kZWZhdWx0KGJhc2VfZmFtaWx5ID0gInNhbnMiLCBiYXNlX3NpemU9MTYpKQpzZXQxIDwtIFJDb2xvckJyZXdlcjo6YnJld2VyLnBhbCg3LCAiU2V0MSIpClNFRUQgPC0gNDg5MjcgIyBzZXQgcmFuZG9tIHNlZWQgZm9yIHJlcHJvZHVjaWJpbGl0eQpgYGAKCiMjIExvYWQgYW5kIHBsb3QgZGF0YQoKTG9hZCBkYXRhCgpgYGB7ciB9CmRhdGEobWN5Y2xlLCBwYWNrYWdlPSJNQVNTIikKaGVhZChtY3ljbGUpCmBgYAoKUGxvdCBkYXRhCgpgYGB7ciB9Cm1jeWNsZSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKQpgYGAKCiMgSG9tb3NrZWRhc3RpYyBHUCB3aXRoIGNvdmFyaWFuY2UgbWF0cmljZXMKCldlIHN0YXJ0IHdpdGggYSBzaW1wbGVyIGhvbW9za2VkYXN0aWMgcmVzaWR1YWwgR2F1c3NpYW4gcHJvY2VzcyBtb2RlbAokJAp5IFxzaW0gXG1ib3h7bm9ybWFsfShmKHgpLCBcc2lnbWEpXFwKZiBcc2ltIEdQKDAsIEtfMSlcXApcc2lnbWEgXHNpbSBcbWJveHtub3JtYWx9XnsrfSgwLCAxKSwKJCQKdGhhdCBoYXMgYW5hbHl0aWMgbWFyZ2luYWwgbGlrZWxpaG9vZCBmb3IgdGhlIGNvdmFyaWFuY2UgZnVuY3Rpb24KYW5kIHJlc2lkdWFsIHNjYWxlIHBhcmFtZXRlcnMuCgojIyBNb2RlbCBjb2RlCgpgYGB7ciB9CmZpbGVfZ3Bjb3ZmIDwtICJncGNvdmYuc3RhbiIKd3JpdGVMaW5lcyhyZWFkTGluZXMoZmlsZV9ncGNvdmYpKQpgYGAKCkNvbXBpbGUgU3RhbiBtb2RlbAoKYGBge3IgcmVzdWx0cz0naGlkZSd9Cm1vZGVsX2dwY292ZiA8LSBjbWRzdGFuX21vZGVsKHN0YW5fZmlsZSA9IGZpbGVfZ3Bjb3ZmKQpgYGAKCkRhdGEgdG8gYmUgcGFzc2VkIHRvIFN0YW4KCmBgYHtyIH0Kc3RhbmRhdGFfZ3Bjb3ZmIDwtIGxpc3QoeD1tY3ljbGUkdGltZXMsCiAgICAgICAgICAgICAgICAgICAgICAgIHgyPW1jeWNsZSR0aW1lcywKICAgICAgICAgICAgICAgICAgICAgICAgeT1tY3ljbGUkYWNjZWwsCiAgICAgICAgICAgICAgICAgICAgICAgIE49bGVuZ3RoKG1jeWNsZSR0aW1lcyksCiAgICAgICAgICAgICAgICAgICAgICAgIE4yPWxlbmd0aChtY3ljbGUkdGltZXMpKQpgYGAKCiMjIE9wdGltaXplIGFuZCBmaW5kIE1BUCBlc3RpbWF0ZQoKYGBge3Igb3B0X2dwY292ZiwgcmVzdWx0cz0naGlkZSd9Cm9wdF9ncGNvdmYgPC0gbW9kZWxfZ3Bjb3ZmJG9wdGltaXplKGRhdGE9c3RhbmRhdGFfZ3Bjb3ZmLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbml0PTAuMSwgYWxnb3JpdGhtPSdiZmdzJykKYGBgCgpDaGVjayB3aGV0aGVyIHBhcmFtZXRlcnMgaGF2ZSByZWFzb25hYmxlIHZhbHVlcwoKYGBge3IgfQpvZHJhd3NfZ3Bjb3ZmIDwtIGFzX2RyYXdzX3J2YXJzKG9wdF9ncGNvdmYkZHJhd3MoKSkKc3Vic2V0KG9kcmF3c19ncGNvdmYsIHZhcmlhYmxlPWMoJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycsJ3NpZ21hJyksIHJlZ2V4PVRSVUUpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKG9kcmF3c19ncGNvdmYkZiksCiAgICAgICAgIHNpZ21hPW1lYW4ob2RyYXdzX2dwY292ZiRzaWdtYSkpICU+JSAgCiAgZ2dwbG90KGFlcyh4PXRpbWVzLHk9YWNjZWwpKSsKICBnZW9tX3BvaW50KCkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKSwgY29sb3I9c2V0MVsxXSkrCiAgZ2VvbV9saW5lKGFlcyh5PUVmLTIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYrMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpCmBgYAoKVGhlIG1vZGVsIGZpdCBnaXZlbiBvcHRpbWl6ZWQgcGFyYW1ldGVycywgbG9va3MgcmVhc29uYWJsZQpjb25zaWRlcmluZyB0aGUgdXNlIG9mIGhvbW9za2VkYXN0aWMgcmVzaWR1YWwgbW9kZWwuCgojIyBTYW1wbGUgdXNpbmcgZHluYW1pYyBITUMKCmBgYHtyIGZpdF9ncGNvdmYsIHJlc3VsdHM9J2hpZGUnfQpmaXRfZ3Bjb3ZmIDwtIG1vZGVsX2dwY292ZiRzYW1wbGUoZGF0YT1zdGFuZGF0YV9ncGNvdmYsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpdGVyX3dhcm11cD01MDAsIGl0ZXJfc2FtcGxpbmc9NTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCByZWZyZXNoPTEwMCkKYGBgCgpDaGVjayB3aGV0aGVyIHBhcmFtZXRlcnMgaGF2ZSByZWFzb25hYmxlIHZhbHVlcwoKYGBge3IgfQpkcmF3c19ncGNvdmYgPC0gYXNfZHJhd3NfcnZhcnMoZml0X2dwY292ZiRkcmF3cygpKQpzdW1tYXJpc2VfZHJhd3Moc3Vic2V0KGRyYXdzX2dwY292ZiwKICAgICAgICAgICAgICAgICAgICAgICB2YXJpYWJsZT1jKCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nLCdzaWdtYScpLAogICAgICAgICAgICAgICAgICAgICAgIHJlZ2V4PVRSVUUpKQpgYGAKCkNvbXBhcmUgdGhlIG1vZGVsIHRvIHRoZSBkYXRhCgpgYGB7ciB9Cm1jeWNsZSAlPiUKICBtdXRhdGUoRWY9bWVhbihkcmF3c19ncGNvdmYkZiksCiAgICAgICAgIHNpZ21hPW1lYW4oZHJhd3NfZ3Bjb3ZmJHNpZ21hKSkgJT4lICAKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgbW9kZWwgZml0IGdpdmVuIGludGVncmF0ZWQgcGFyYW1ldGVycyBsb29rcyBzaW1pbGFyIHRvIHRoZQpvcHRpbWl6ZWQgb25lLgoKQ29tcGFyZSB0aGUgcG9zdGVyaW9yIGRyYXdzIHRvIHRoZSBvcHRpbWl6ZWQgcGFyYW1ldGVycwoKYGBge3IgfQpvZHJhd3NfZ3Bjb3ZmIDwtIGFzX2RyYXdzX2RmKG9wdF9ncGNvdmYkZHJhd3MoKSkKZHJhd3NfZ3Bjb3ZmICU+JQogIGFzX2RyYXdzX2RmKCkgJT4lCiAgZ2dwbG90KGFlcyh4PWxlbmd0aHNjYWxlX2YseT1zaWdtYV9mKSkrCiAgZ2VvbV9wb2ludChjb2xvcj1zZXQxWzJdKSsKICBnZW9tX3BvaW50KGRhdGE9b2RyYXdzX2dwY292Zixjb2xvcj1zZXQxWzFdLHNpemU9NCkrCiAgYW5ub3RhdGUoInRleHQiLHg9bWVkaWFuKGRyYXdzX2dwY292ZiRsZW5ndGhzY2FsZV9mKSwKICAgICAgICAgICB5PW1heChkcmF3c19ncGNvdmYkc2lnbWFfZikrMC4xLAogICAgICAgICAgIGxhYmVsPSdQb3N0ZXJpb3IgZHJhd3MnLGhqdXN0PTAuNSxjb2xvcj1zZXQxWzJdLHNpemU9NikrCiAgYW5ub3RhdGUoInRleHQiLHg9b2RyYXdzX2dwY292ZiRsZW5ndGhzY2FsZV9mKzAuMDEsCiAgICAgICAgICAgeT1vZHJhd3NfZ3Bjb3ZmJHNpZ21hX2YsCiAgICAgICAgICAgbGFiZWw9J09wdGltaXplZCcsaGp1c3Q9MCxjb2xvcj1zZXQxWzFdLHNpemU9NikKYGBgCgpUaGUgb3B0aW1pemF0aW9uIHJlc3VsdCBpcyBpbiB0aGUgbWlkZGxlIG9mIHRoZSBwb3N0ZXJpb3IgYW5kIHF1aXRlCndlbGwgcmVwcmVzZW50YXRpdmUgb2YgdGhlIGxvdyBkaW1lbnNpb25hbCBwb3N0ZXJpb3IgKGluIGhpZ2hlcgpkaW1lbnNpb25zIHRoZSBtZWFuIG9yIG1vZGUgb2YgdGhlIHBvc3RlcmlvciBpcyBub3QgbGlrZWx5IHRvIGJlCnJlcHJlc2VudGF0aXZlKS4KCkNvbXBhcmUgb3B0aW1pemVkIGFuZCBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBkaXN0cmlidXRpb25zCgpgYGB7ciB9Cm9kcmF3c19ncGNvdmYgPC0gYXNfZHJhd3NfcnZhcnMob3B0X2dwY292ZiRkcmF3cygpKQptY3ljbGUgJT4lCiAgbXV0YXRlKEVmPW1lYW4oZHJhd3NfZ3Bjb3ZmJGYpLAogICAgICAgICBzaWdtYT1tZWFuKGRyYXdzX2dwY292ZiRzaWdtYSksCiAgICAgICAgIEVmbz1tZWFuKG9kcmF3c19ncGNvdmYkZiksCiAgICAgICAgIHNpZ21hbz1tZWFuKG9kcmF3c19ncGNvdmYkc2lnbWEpKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmbyksIGNvbG9yPXNldDFbMl0pKwogIGdlb21fbGluZShhZXMoeT1FZm8tMipzaWdtYW8pLCBjb2xvcj1zZXQxWzJdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWZvKzIqc2lnbWFvKSwgY29sb3I9c2V0MVsyXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgbW9kZWwgcHJlZGljdGlvbnMgYXJlIHZlcnkgc2ltaWxhciwgYW5kIGluIGdlbmVyYWwgR1AKY292YXJpYW5jZSBmdW5jdGlvbiBhbmQgb2JzZXJ2YXRpb24gbW9kZWwgcGFyYW1ldGVycyBjYW4gYmUgcXVpdGUKc2FmZWx5IG9wdGltaXplZCBpZiB0aGVyZSBhcmUgb25seSBhIGZldyBvZiB0aGVtIGFuZCB0aHVzIG1hcmdpbmFsCnBvc3RlcmlvciBpcyBsb3cgZGltZW5zaW9uYWwgYW5kIHRoZSBudW1iZXIgb2Ygb2JzZXJ2YXRpb25zIGlzCnJlbGF0aXZlbHkgaGlnaC4KCiMjIDEwJSBvZiBkYXRhCgpUbyBkZW1vbnN0cmF0ZSB0aGF0IHRoZSBvcHRpbWl6YXRpb24gaXMgbm90IGFsd2F5cyBzYWZlLCB3ZSB1c2UKb25seSAxMCUgb2YgdGhlIGRhdGEgZm9yIG1vZGVsIGZpdHRpbmcuCgpEYXRhIHRvIGJlIHBhc3NlZCB0byBTdGFuCgpgYGB7ciB9Cm1jeWNsZV8xMHAgPC0gbWN5Y2xlW3NlcSgxLDEzMyxieT0xMCksXQpzdGFuZGF0YV8xMHAgPC0gbGlzdCh4PW1jeWNsZV8xMHAkdGltZXMsCiAgICAgICAgICAgICAgICAgICAgIHgyPW1jeWNsZSR0aW1lcywKICAgICAgICAgICAgICAgICAgICAgeT1tY3ljbGVfMTBwJGFjY2VsLAogICAgICAgICAgICAgICAgICAgICBOPWxlbmd0aChtY3ljbGVfMTBwJHRpbWVzKSwKICAgICAgICAgICAgICAgICAgICAgTjI9bGVuZ3RoKG1jeWNsZSR0aW1lcykpCmBgYAoKT3B0aW1pemUgYW5kIGZpbmQgTUFQIGVzdGltYXRlCgpgYGB7ciBvcHRfMTBwLCByZXN1bHRzPSdoaWRlJ30Kb3B0XzEwcCA8LSBtb2RlbF9ncGNvdmYkb3B0aW1pemUoZGF0YT1zdGFuZGF0YV8xMHAsIGluaXQ9MC4xLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhbGdvcml0aG09J2xiZmdzJykKYGBgCgpDaGVjayB3aGV0aGVyIHBhcmFtZXRlcnMgaGF2ZSByZWFzb25hYmxlIHZhbHVlcwoKYGBge3IgfQpvZHJhd3NfMTBwIDwtIGFzX2RyYXdzX3J2YXJzKG9wdF8xMHAkZHJhd3MoKSkKc3Vic2V0KG9kcmF3c18xMHAsIHZhcmlhYmxlPWMoJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycsJ3NpZ21hJyksIHJlZ2V4PVRSVUUpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlXzEwcCAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsYWVzKHg9dGltZXMseT1tZWFuKG9kcmF3c18xMHAkZikpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsYWVzKHg9dGltZXMseT1tZWFuKG9kcmF3c18xMHAkZi0yKm9kcmF3c18xMHAkc2lnbWEpKSwgY29sb3I9c2V0MVsxXSwKICAgICAgICAgICAgbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4ob2RyYXdzXzEwcCRmKzIqb2RyYXdzXzEwcCRzaWdtYSkpLCBjb2xvcj1zZXQxWzFdLAogICAgICAgICAgICBsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgbW9kZWwgZml0IGlzIGNsZWFybHkgb3Zlci1maXR0ZWQgYW5kIG92ZXItY29uZmlkZW50LgoKU2FtcGxlIHVzaW5nIGR5bmFtaWMgSE1DCgpgYGB7ciBmaXRfMTBwLCByZXN1bHRzPSdoaWRlJ30KZml0XzEwcCA8LSBtb2RlbF9ncGNvdmYkc2FtcGxlKGRhdGE9c3RhbmRhdGFfMTBwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcl93YXJtdXA9MTAwMCwgaXRlcl9zYW1wbGluZz0xMDAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWRhcHRfZGVsdGE9MC45NSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNoYWlucz00LCBwYXJhbGxlbF9jaGFpbnM9NCwgcmVmcmVzaD0xMDApCmBgYAoKQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKCmBgYHtyIH0KZHJhd3NfMTBwIDwtIGFzX2RyYXdzX3J2YXJzKGZpdF8xMHAkZHJhd3MoKSkKc3VtbWFyaXNlX2RyYXdzKHN1YnNldChkcmF3c18xMHAsIHZhcmlhYmxlPWMoJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycsJ3NpZ21hJyksCiAgICAgICAgICAgICAgICAgICAgICAgcmVnZXg9VFJVRSkpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlXzEwcCAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsYWVzKHg9dGltZXMseT1tZWFuKGRyYXdzXzEwcCRmKSksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4oZHJhd3NfMTBwJGYtMipkcmF3c18xMHAkc2lnbWEpKSwgY29sb3I9c2V0MVsxXSwKICAgICAgICAgICAgbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSxhZXMoeD10aW1lcyx5PW1lYW4oZHJhd3NfMTBwJGYrMipkcmF3c18xMHAkc2lnbWEpKSwgY29sb3I9c2V0MVsxXSwKICAgICAgICAgICAgbGluZXR5cGU9ImRhc2hlZCIpCmBgYAoKVGhlIHBvc3RlcmlvciBwcmVkaWN0aXZlIGRpc3RyaWJ1dGlvbiBpcyBtdWNoIG1vcmUgY29uc2VydmF0aXZlIGFuZApzaG93cyB0aGUgdW5jZXJ0YWludHkgZHVlIHRvIGhhdmluZyBvbmx5IGEgc21hbGwgbnVtYmVyIG9mCm9ic2VydmF0aW9ucy4KCkNvbXBhcmUgdGhlIHBvc3RlcmlvciBkcmF3cyB0byB0aGUgb3B0aW1pemVkIHBhcmFtZXRlcnMKCmBgYHtyIH0Kb2RyYXdzXzEwcCA8LSBhc19kcmF3c19kZihvcHRfMTBwJGRyYXdzKCkpCmRyYXdzXzEwcCAlPiUKICB0aGluX2RyYXdzKHRoaW49NSkgJT4lCiAgYXNfZHJhd3NfZGYoKSAlPiUKICBnZ3Bsb3QoYWVzKHg9c2lnbWEseT1zaWdtYV9mKSkrCiAgZ2VvbV9wb2ludChjb2xvcj1zZXQxWzJdKSsKICBnZW9tX3BvaW50KGRhdGE9b2RyYXdzXzEwcCxjb2xvcj1zZXQxWzFdLHNpemU9NCkrCiAgYW5ub3RhdGUoInRleHQiLHg9bWVkaWFuKGRyYXdzXzEwcCRzaWdtYSksCiAgICAgICAgICAgeT1tYXgoZHJhd3NfMTBwJHNpZ21hX2YpKzAuMSwKICAgICAgICAgICBsYWJlbD0nUG9zdGVyaW9yIGRyYXdzJyxoanVzdD0wLjUsY29sb3I9c2V0MVsyXSxzaXplPTYpKwogIGFubm90YXRlKCJ0ZXh0Iix4PW9kcmF3c18xMHAkc2lnbWErMC4wMSwKICAgICAgICAgICB5PW9kcmF3c18xMHAkc2lnbWFfZiwKICAgICAgICAgICBsYWJlbD0nT3B0aW1pemVkJyxoanVzdD0wLGNvbG9yPXNldDFbMV0sc2l6ZT02KQpgYGAKClRoZSBvcHRpbWl6YXRpb24gcmVzdWx0IGlzIGluIHRoZSBlZGdlIG9mIHRoZSBwb3N0ZXJpb3IgY2xvc2UgdG8KemVybyByZXNpZHVhbCBzY2FsZS4gV2hpbGUgdGhlcmUgYXJlIHBvc3RlcmlvciBkcmF3cyBjbG9zZSB0byB6ZXJvLAppbnRlZ3JhdGluZyBvdmVyIHRoZSB3aWRlIHBvc3RlcmlvciB0YWtlcyBpbnRvIGFjY291bnQgdGhlCnVuY2VydGFpbnR5IGFuZCB0aGUgcHJlZGljdGlvbnMgdGh1cyBhcmUgbW9yZSB1bmNlcnRhaW4sIHRvby4KCkNvbXBhcmUgb3B0aW1pemVkIGFuZCBwb3N0ZXJpb3IgcHJlZGljdGl2ZSBkaXN0cmlidXRpb25zCgpgYGB7ciB9Cm9kcmF3c18xMHAgPC0gYXNfZHJhd3NfcnZhcnMob3B0XzEwcCRkcmF3cygpKQptY3ljbGUgJT4lCiAgbXV0YXRlKEVmPW1lYW4oZHJhd3NfMTBwJGYpLAogICAgICAgICBzaWdtYT1tZWFuKGRyYXdzXzEwcCRzaWdtYSksCiAgICAgICAgIEVmbz1tZWFuKG9kcmF3c18xMHAkZiksCiAgICAgICAgIHNpZ21hbz1tZWFuKG9kcmF3c18xMHAkc2lnbWEpKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmbyksIGNvbG9yPXNldDFbMl0pKwogIGdlb21fbGluZShhZXMoeT1FZm8tMipzaWdtYW8pLCBjb2xvcj1zZXQxWzJdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWZvKzIqc2lnbWFvKSwgY29sb3I9c2V0MVsyXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgZmlndXJlIHNob3dzIHRoZSBtb2RlbCBwcmVkaWN0aW9uIGdpdmVuIDEwJSBvZiBkYXRhLCBidXQgYWxzbwp0aGUgZnVsbCBkYXRhIGFzIHRlc3QgZGF0YS4gVGhlIG9wdGltaXplZCBtb2RlbCBpcyBvdmVyLWZpdHRlZCBhbmQKb3ZlcmNvbmZpZGVudC4gRXZlbiBpZiB0aGUgaG9tb3NrZWRhc3RpYyByZXNpZHVhbCBpcyB3cm9uZyBoZXJlLAp0aGUgcG9zdGVyaW9yIHByZWRpY3RpdmUgaW50ZXJ2YWwgY292ZXJzIG1vc3Qgb2YgdGhlIG9ic2VydmF0aW9uCihhbmQgaW4gY2FzZSBvZiBnb29kIGNhbGlicmF0aW9uIHNob3VsZCBub3QgY292ZXIgdGhlbSBhbGwpLgoKIyBIZXRlcm9za2VkYXN0aWMgR1Agd2l0aCBjb3ZhcmlhbmNlIG1hdHJpY2VzCgpXZSBuZXh0IG1ha2UgYSBtb2RlbCB3aXRoIGhldGVyb3NrZWRhc3RpYyByZXNpZHVhbCBtb2RlbCB1c2luZwpHYXVzc2lhbiBwcm9jZXNzIHByaW9yIGFsc28gZm9yIHRoZSBsb2dhcml0aG0gb2YgdGhlIHJlc2lkdWFsCnNjYWxlOgokJAp5IFxzaW0gXG1ib3h7bm9ybWFsfShmKHgpLCBcZXhwKGcoeCkpXFwKZiBcc2ltIEdQKDAsIEtfMSlcXApnIFxzaW0gR1AoMCwgS18yKS4KJCQKCk5vdyB0aGVyZSBpcyBubyBhbmFseXRpY2FsIHNvbHV0aW9uIGFzIEdQIHByaW9yIHRocm91Z2ggdGhlCmV4cG9uZW50aWFsIGZ1bmN0aW9uIGlzIG5vdCBhIGNvbmp1Z2F0ZSBwcmlvci4gSW4gdGhpcyBjYXNlIHdlCnByZXNlbnQgdGhlIGxhdGVudCB2YWx1ZXMgb2YgZiBhbmQgZyBleHBsaWNpdGx5IGFuZCBzYW1wbGUgZnJvbSB0aGUKam9pbnQgcG9zdGVyaW9yIG9mIHRoZSBjb3ZhcmlhbmNlIGZ1bmN0aW9uIHBhcmFtZXRlcnMsIGFuZCB0aGUKbGF0ZW50IHZhbHVlcy4gSXQgd291bGQgYmUgcG9zc2libGUgYWxzbyB0byB1c2UgTGFwbGFjZSwKdmFyaWF0aW9uYWwgaW5mZXJlbmNlLCBvciBleHBlY3RhdGlvbiBwcm9wYWdhdGlvbiB0byBpbnRlZ3JhdGUgb3Zlcgp0aGUgbGF0ZW50IHZhbHVlcywgYnV0IHRoYXQgaXMgYW5vdGhlciBzdG9yeS4KCiMjIE1vZGVsIGNvZGUKCmBgYHtyIH0KZmlsZV9ncGNvdmZnIDwtICJncGNvdmZnLnN0YW4iCndyaXRlTGluZXMocmVhZExpbmVzKGZpbGVfZ3Bjb3ZmZykpCmBgYAoKQ29tcGlsZSBTdGFuIG1vZGVsCgpgYGB7ciByZXN1bHRzPSdoaWRlJ30KbW9kZWxfZ3Bjb3ZmZyA8LSBjbWRzdGFuX21vZGVsKHN0YW5fZmlsZSA9IGZpbGVfZ3Bjb3ZmZykKYGBgCgpEYXRhIHRvIGJlIHBhc3NlZCB0byBTdGFuCgpgYGB7ciB9CnN0YW5kYXRhX2dwY292ZmcgPC0gbGlzdCh4PW1jeWNsZSR0aW1lcywKICAgICAgICAgICAgICAgICAgICAgICAgIHk9bWN5Y2xlJGFjY2VsLAogICAgICAgICAgICAgICAgICAgICAgICAgTj1sZW5ndGgobWN5Y2xlJHRpbWVzKSkKYGBgCgojIyBPcHRpbWl6ZSBhbmQgZmluZCBNQVAgZXN0aW1hdGUKCmBgYHtyIG9wdF9ncGNvdmZnLCByZXN1bHRzPSdoaWRlJ30Kb3B0X2dwY292ZmcgPC0gbW9kZWxfZ3Bjb3ZmZyRvcHRpbWl6ZShkYXRhPXN0YW5kYXRhX2dwY292ZmcsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5pdD0wLjEsIGFsZ29yaXRobT0nYmZncycpCmBgYAoKQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKCmBgYHtyIH0Kb2RyYXdzX2dwY292ZmcgPC0gYXNfZHJhd3NfcnZhcnMob3B0X2dwY292ZmckZHJhd3MoKSkKc3Vic2V0KG9kcmF3c19ncGNvdmZnLCB2YXJpYWJsZT1jKCdzaWdtYV8nLCdsZW5ndGhzY2FsZV8nKSwgcmVnZXg9VFJVRSkKYGBgCgpDb21wYXJlIHRoZSBtb2RlbCB0byB0aGUgZGF0YQoKYGBge3IgfQptY3ljbGUgJT4lCiAgbXV0YXRlKEVmID0gbWVhbihvZHJhd3NfZ3Bjb3ZmZyRmKSwKICAgICAgICAgc2lnbWEgPSBtZWFuKG9kcmF3c19ncGNvdmZnJHNpZ21hKSkgJT4lCiAgZ2dwbG90KGFlcyh4PXRpbWVzLHk9YWNjZWwpKSsKICBnZW9tX3BvaW50KCkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKSwgY29sb3I9c2V0MVsxXSkrCiAgZ2VvbV9saW5lKGFlcyh5PUVmLTIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYrMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpCmBgYAoKVGhlIG9wdGltaXphdGlvbiBvdmVyZml0cywgYXMgd2UgYXJlIG5vdyBvcHRpbWl6aW5nIHRoZSBqb2ludApwb3N0ZXJpb3Igb2YgMiBjb3ZhcmlhbmNlIGZ1bmN0aW9uIHBhcmFtZXRlcnMgYW5kIDIgeCAxMzMgbGF0ZW50CnZhbHVlcy4KCiMjIFNhbXBsZSB1c2luZyBkeW5hbWljIEhNQwoKYGBge3IgZml0X2dwY292ZmcsIHJlc3VsdHM9J2hpZGUnfQpmaXRfZ3Bjb3ZmZyA8LSBtb2RlbF9ncGNvdmZnJHNhbXBsZShkYXRhPXN0YW5kYXRhX2dwY292ZmcsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJfd2FybXVwPTEwMCwgaXRlcl9zYW1wbGluZz0yMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNoYWlucz00LCBwYXJhbGxlbF9jaGFpbnM9NCwgcmVmcmVzaD0yMCkKYGBgCgpDaGVjayB3aGV0aGVyIHBhcmFtZXRlcnMgaGF2ZSByZWFzb25hYmxlIHZhbHVlcwoKYGBge3IgfQpkcmF3c19ncGNvdmZnIDwtIGFzX2RyYXdzX3J2YXJzKGZpdF9ncGNvdmZnJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQoZHJhd3NfZ3Bjb3ZmZywgdmFyaWFibGU9Yygnc2lnbWFfJywnbGVuZ3Roc2NhbGVfJyksCiAgICAgICAgICAgICAgICAgICAgICAgcmVnZXg9VFJVRSkpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlICU+JQogIG11dGF0ZShFZiA9IG1lYW4oZHJhd3NfZ3Bjb3ZmZyRmKSwKICAgICAgICAgc2lnbWEgPSBtZWFuKGRyYXdzX2dwY292Zmckc2lnbWEpKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgTUNNQyBpbnRlZ3JhdGlvbiB3b3JrcyB3ZWxsIGFuZCB0aGUgbW9kZWwgZml0IGxvb2tzIGdvb2QuCgpQbG90IHBvc3RlcmlvciBkcmF3cyBhbmQgcG9zdGVyaW9yIG1lYW4gb2YgdGhlIG1lYW4gZnVuY3Rpb24KCmBgYHtyIH0KZHJhd3NfZ3Bjb3ZmZyAlPiUKICBzcHJlYWRfcnZhcnMoZltpXSkgJT4lCiAgdW5uZXN0X3J2YXJzKCkgJT4lCiAgbXV0YXRlKHRpbWU9bWN5Y2xlJHRpbWVzW2ldKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZSwgeT1mLCBncm91cCA9IC5kcmF3KSkgKwogIGdlb21fbGluZShjb2xvcj1zZXQxWzJdLCBhbHBoYSA9IDAuMSkgKwogIGdlb21fcG9pbnQoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1hY2NlbCksIGluaGVyaXQuYWVzPUZBTFNFKSArCiAgZ2VvbV9saW5lKGRhdGE9bWN5Y2xlLCBtYXBwaW5nPWFlcyh4PXRpbWVzLHk9bWVhbihkcmF3c19ncGNvdmZnJGYpKSwKICAgICAgICAgICAgaW5oZXJpdC5hZXM9RkFMU0UsIGNvbG9yPXNldDFbMV0sIHNpemU9MSkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikKYGBgCgpXZSBjYW4gYWxzbyBwbG90IHRoZSBwb3N0ZXJpb3IgZHJhd3Mgb2YgdGhlIGxhdGVudCBmdW5jdGlvbnMsIHdoaWNoCmlzIGEgZ29vZCByZW1pbmRlciB0aGF0IGluZGl2aWR1YWwgZHJhd3MgYXJlIG1vcmUgd2lnZ2x5IHRoYW4gdGhlCmF2ZXJhZ2Ugb2YgdGhlIGRyYXdzLCBhbmQgdGh1cyBzaG93IGJldHRlciBhbHNvIHRoZSB1bmNlcnRhaW50eSwKZm9yIGV4YW1wbGUsIGluIHRoZSBlZGdlIG9mIHRoZSBkYXRhLgoKQ29tcGFyZSB0aGUgcG9zdGVyaW9yIGRyYXdzIHRvIHRoZSBvcHRpbWl6ZWQgcGFyYW1ldGVycwoKYGBge3IgfQpvZHJhd3NfZ3Bjb3ZmZyA8LSBhc19kcmF3c19kZihvcHRfZ3Bjb3ZmZyRkcmF3cygpKQpkcmF3c19ncGNvdmZnICU+JQogIGFzX2RyYXdzX2RmKCkgJT4lCiAgZ2dwbG90KGFlcyh4PWxlbmd0aHNjYWxlX2YseT1zaWdtYV9mKSkrCiAgZ2VvbV9wb2ludChjb2xvcj1zZXQxWzJdKSsKICBnZW9tX3BvaW50KGRhdGE9b2RyYXdzX2dwY292ZmcsY29sb3I9c2V0MVsxXSxzaXplPTQpKwogIGFubm90YXRlKCJ0ZXh0Iix4PW1lZGlhbihkcmF3c19ncGNvdmZnJGxlbmd0aHNjYWxlX2YpLAogICAgICAgICAgIHk9bWF4KGRyYXdzX2dwY292Zmckc2lnbWFfZikrMC4xLAogICAgICAgICAgIGxhYmVsPSdQb3N0ZXJpb3IgZHJhd3MnLGhqdXN0PTAuNSxjb2xvcj1zZXQxWzJdLHNpemU9NikrCiAgYW5ub3RhdGUoInRleHQiLHg9b2RyYXdzX2dwY292ZmckbGVuZ3Roc2NhbGVfZiswLjAxLAogICAgICAgICAgIHk9b2RyYXdzX2dwY292Zmckc2lnbWFfZiwKICAgICAgICAgICBsYWJlbD0nT3B0aW1pemVkJyxoanVzdD0wLGNvbG9yPXNldDFbMV0sc2l6ZT02KQpgYGAKCk9wdGltaXphdGlvbiByZXN1bHQgaXMgZmFyIGZyb20gYmVpbmcgcmVwcmVzZW50YXRpdmUgb2YgdGhlCnBvc3Rlcmlvci4KCiMgSGV0ZXJvc2tlZGFzdGljIEdQIHdpdGggSGlsYmVydCBiYXNpcyBmdW5jdGlvbnMKClRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBhcHByb2FjaCByZXF1aXJlcyBjb21wdXRhdGlvbiBvZiBDaG9sZXNreSBvZgp0aGUgY292YXJpYW5jZSBtYXRyaXggd2hpY2ggaGFzIHRpbWUgY29zdCBPKG5eMykgYW5kIHRoaXMgaXMgbmVlZHMKdG8gYmUgZG9uZSBldmVyeSB0aW1lIHRoZSBwYXJhbWV0ZXJzIGNoYW5nZSwgd2hpY2ggaW4gY2FzZSBvZiBNQ01DCmNhbiBiZSBxdWl0ZSBtYW55IHRpbWVzIGFuZCB0aHVzIHRoZSBjb21wdXRhdGlvbiB0aW1lIGNhbiBiZQpzaWduaWZpY2FudCB3aGVuIG4gZ3Jvd3MuIE9uZSB3YXkgdG8gc3BlZWQgdXAgdGhlIGNvbXB1dGF0aW9uIGluCmxvdyBkaW1lbnNpb25hbCBjb3ZhcmlhdGUgY2FzZSBpcyB0byB1c2UgYmFzaXMgZnVuY3Rpb24KYXBwcm94aW1hdGlvbiB3aGljaCBjaGFuZ2VzIHRoZSBHUCB0byBhIGxpbmVhciBtb2RlbC4gSGVyZSB3ZSB1c2UKSGlsYmVydCBzcGFjZSBiYXNpcyBmdW5jdGlvbnMuIFdpdGggaW5jcmVhc2luZyBudW1iZXIgb2YgYmFzaXMKZnVuY3Rpb25zIGFuZCBmYWN0b3IgYywgdGhlIGFwcHJveGltYXRpb24gZXJyb3IgY2FuIGJlIG1hZGUKYXJiaXRyYXJpbHkgc21hbGwuIFN1ZmZpY2llbnQgYWNjdXJhY3kgYW5kIHNpZ25pZmljYW50IHNhdmluZyBpbgp0aGUgY29tcHV0YXRpb24gc3BlZWQgaXMgb2Z0ZW4gYWNoaWV2ZXZlZCB3aXRoIGEgcmVsYXRpdmVseSBzbWFsbApudW1iZXIgb2YgYmFzaXMgZnVuY3Rpb25zLgoKIyMgSWxsdXN0cmF0ZSB0aGUgYmFzaXMgZnVuY3Rpb25zCgpDb2RlCgpgYGB7ciB9CmZpbGViZjAgPC0gImdwYmYwLnN0YW4iCndyaXRlTGluZXMocmVhZExpbmVzKGZpbGViZjApKQpgYGAKClRoZSBtb2RlbCBjb2RlIGluY2x1ZGVzIEhpbGJlcnQgc3BhY2UgYmFzaXMgZnVuY3Rpb24gaGVscGVycwoKYGBge3IgfQp3cml0ZUxpbmVzKHJlYWRMaW5lcygiZ3BiYXNpc2Z1bl9mdW5jdGlvbnMuc3RhbiIpKQpgYGAKCkNvbXBpbGUgYmFzaXMgZnVuY3Rpb24gZ2VuZXJhdGlvbiBjb2RlCgpgYGB7ciByZXN1bHRzPSdoaWRlJ30KbW9kZWxiZjAgPC0gY21kc3Rhbl9tb2RlbChzdGFuX2ZpbGUgPSBmaWxlYmYwLCBpbmNsdWRlX3BhdGhzID0gIi4iKQpgYGAKCkRhdGEgdG8gYmUgcGFzc2VkIHRvIFN0YW4KCmBgYHtyIH0Kc3RhbmRhdGFiZjAgPC0gbGlzdCh4PXNlcSgwLDEsbGVuZ3RoLm91dD0xMDApLAogICAgICAgICAgICAgICAgICAgIE49MTAwLAogICAgICAgICAgICAgICAgICAgIGNfZj0zLCAjIGZhY3RvciBjIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGYxCiAgICAgICAgICAgICAgICAgICAgTV9mPTE2MCwgICMgbnVtYmVyIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGYxCiAgICAgICAgICAgICAgICAgICAgc2lnbWFfZj0xLAogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNjYWxlX2Y9MSkgCmBgYAoKR2VuZXJhdGUgYmFzaXMgZnVuY3Rpb25zCgpgYGB7ciB9CmZpeGJmMCA8LSBtb2RlbGJmMCRzYW1wbGUoZGF0YT1zdGFuZGF0YWJmMCwgZml4ZWRfcGFyYW09VFJVRSwKICAgICAgICAgICAgICAgICAgICAgICAgICBjaGFpbnM9MSwgaXRlcj0xLCBpdGVyX3NhbXBsaW5nPTEpCmBgYAoKVGhlcmUgaXMgY2VydGFpbmx5IGVhc2llciB3YXkgdG8gZG8gdGhpcywgYnV0IHRoaXMgaXMgd2hhdCBJIGNhbWUgdXAgcXVpY2tseQoKYGBge3IgfQpxPC1zdWJzZXQoZml4YmYwJGRyYXdzKCksIHZhcmlhYmxlPSJQSElfZiIpICU+JQogIGFzX2RyYXdzX21hdHJpeCgpICU+JQogIGFzLm51bWVyaWMoKSU+JQogIG1hdHJpeChucm93PTEwMCxuY29sPTE2MCklPiUKICBhcy5kYXRhLmZyYW1lKCkKaWQgPC0gcm93bmFtZXMocSkKcSA8LSBjYmluZCh4PWFzLm51bWVyaWMoaWQpLCBxKQpxIDwtIHEgJT4lCiAgcGl2b3RfbG9uZ2VyKCF4LAogICAgICAgICAgICAgICBuYW1lc190bz0iaW5kIiwKICAgICAgICAgICAgICAgbmFtZXNfdHJhbnNmb3JtID0gbGlzdChpbmQgPSByZWFkcjo6cGFyc2VfbnVtYmVyKSwKICAgICAgICAgICAgICAgdmFsdWVzX3RvPSJmIiklPiUKICBtdXRhdGUoeD14LzEwMCkKYGBgCgpQbG90IHRoZSBmaXJzdCA2IGJhc2lzIGZ1bmN0aW9ucy4gVGhlc2UgYXJlIGp1c3Qgc2luZSBhbmQgY29zaW5lCmZ1bmN0aW9ucyB3aXRoIGRpZmZlcmVudCBmcmVxdWVuY2llcyBhbmQgdHJ1bmNhdGVkIHRvIGEgcHJlLWRlZmluZWQKYm94LgoKYGBge3IgfQpxICU+JQogIGZpbHRlcihpbmQ8PTYpICU+JQogIGdncGxvdChhZXMoeD14LCB5PWYsIGdyb3VwPWluZCwgY29sb3I9ZmFjdG9yKGluZCkpKSArCiAgZ2VvbV9saW5lKCkrCiAgZ2VvbV90ZXh0X3JlcGVsKGRhdGE9ZmlsdGVyKHEsIGluZDw9NiAmIHg9PTAuMDEpLGFlcyh4PS0wLjAxLHk9ZixsYWJlbD1pbmQpLAogICAgICAgICAgICAgICAgICBkaXJlY3Rpb249InkiKSsKICBnZW9tX3RleHRfcmVwZWwoZGF0YT1maWx0ZXIocSwgaW5kPD02ICYgeD09MSksYWVzKHg9MS4wMix5PWYsbGFiZWw9aW5kKSwKICAgICAgICAgICAgICAgICAgZGlyZWN0aW9uPSJ5IikrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uPSJub25lIikKYGBgCgpUaGUgZmlyc3QgOCBzcGVjdHJhbCBkZW5zaXRpZXMgZm9yIGV4cG9uZW50aWF0ZWQgcXVhZHJhdGljCmNvdmFyaWFuY2UgZnVuY3Rpb24gd2l0aCBzaWdtYV9mPTEgYW5kIGxlbmd0aHNjYWxlX2Y9MS4gVGhlc2UKc3BlY3RyYWwgZGVuc2l0aWVzIGdpdmUgYSBwcmlvciB3ZWlnaHQgZm9yIGVhY2ggYmFzaXMKZnVuY3Rpb24uIEJpZ2dlciB3ZWlnaHRzIG9uIHRoZSBzbW9vdGhlciBiYXNpcyBmdW5jdGlvbnMgdGh1cyBpbXBseQphIHByaW9yIG9uIGZ1bmN0aW9uIHNwYWNlIGZhdm9yaW5nIHNtb290aGVyIGZ1bmN0aW9ucy4KCmBgYHtyIH0Kc3BkX0VRIDwtIGFzLm1hdHJpeChmaXhiZjAkZHJhd3ModmFyaWFibGU9J2RpYWdTUERfRVFfZicpKQpyb3VuZChzcGRfRVFbMToxMl0sMikKYGBgCgpUaGUgZmlyc3QgOCBzcGVjdHJhbCBkZW5zaXRpZXMgZm9yIE1hdGVybi0zLzIgY292YXJpYW5jZSBmdW5jdGlvbgp3aXRoIHNpZ21hX2Y9MSBhbmQgbGVuZ3Roc2NhbGVfZj0xLiBUaGUgc3BlY3RyYWwgZGVuc2l0eSB2YWx1ZXMgZ28KZG93biBtdWNoIHNsb3dlciB0aGFuIGZvciB0aGUgZXhwb25lbnRpYXRlZCBxdWFkcmF0aWMgY292YXJpYW5jZQpmdW5jdGlvbiwgd2hpY2ggaXMgbmF0dXJhbCBhcyBNYXRlcm4tMy8yIGlzIGxlc3Mgc21vb3RoLgoKYGBge3IgfQpzcGRfTWF0ZXJuMzIgPC0gYXMubWF0cml4KGZpeGJmMCRkcmF3cyh2YXJpYWJsZT0nZGlhZ1NQRF9NYXRlcm4zMl9mJykpCnJvdW5kKHNwZF9NYXRlcm4zMlsxOjEyXSwyKQpgYGAKClBsb3QgNCByYW5kb20gZHJhd3MgZnJvbSB0aGUgcHJpb3Igb24gZnVuY3Rpb24gc3BhY2Ugd2l0aApleHBvbmVudGlhdGVkIHF1YWRyYXRpYyBjb3ZhcmlhbmNlIGZ1bmN0aW9uIGFuZCBzaWdtYV9mPTEgYW5kCmxlbmd0aHNjYWxlX2Y9MS4gVGhlIGJhc2lzIGZ1bmN0aW9uIGFwcHJveGltYXRpb24gaXMganVzdCBhIGxpbmVhcgptb2RlbCwgd2l0aCB0aGUgYmFzaXMgZnVuY3Rpb25zIHdlaWdodGVkIGJ5IHRoZSBzcGVjdHJhbCBkZW5zaXRpZXMKZGVwZW5kaW5nIG9uIHRoZSBzaWdtYV9mIGFuZCBsZW5ndGhzY2FsZV9mLCBhbmQgdGhlIHByaW9yIGZvciB0aGUKbGluZWFyIG1vZGVsIGNvZWZmaWNpZW50cyBpcyBzaW1wbHkgaW5kZXBlbmRlbnQgbm9ybWFsKDAsMSkuCgpgYGB7ciB9CnNldC5zZWVkKDM2NSkKcXIgPC0gYmluZF9yb3dzKGxhcHBseSgxOjQsIGZ1bmN0aW9uKGkpIHsKICBxICU+JQogICAgbXV0YXRlKHI9cmVwKHJub3JtKDE2MCksdGltZXM9MTAwKSxmcj1mKnIqc3BkX0VRW2luZF0pICU+JQogICAgZ3JvdXBfYnkoeCkgJT4lCiAgICBzdW1tYXJpc2UoZj1zdW0oZnIpKSAlPiUKICAgIG11dGF0ZShpbmQ9aSkgfSkpCnFyICU+JQogIGdncGxvdChhZXMoeD14LCB5PWYsIGdyb3VwPWluZCwgY29sb3I9ZmFjdG9yKGluZCkpKSArCiAgZ2VvbV9saW5lKCkrCiAgZ2VvbV90ZXh0X3JlcGVsKGRhdGE9ZmlsdGVyKHFyLCB4PT0wLjAxKSxhZXMoeD0tMC4wMSx5PWYsbGFiZWw9aW5kKSwKICAgICAgICAgICAgICAgICAgZGlyZWN0aW9uPSJ5IikrCiAgZ2VvbV90ZXh0X3JlcGVsKGRhdGE9ZmlsdGVyKHFyLCB4PT0xKSxhZXMoeD0xLjAyLHk9ZixsYWJlbD1pbmQpLAogICAgICAgICAgICAgICAgICBkaXJlY3Rpb249InkiKSsKICB0aGVtZShsZWdlbmQucG9zaXRpb249Im5vbmUiKQpgYGAKClBsb3QgNCByYW5kb20gZHJhd3MgZnJvbSB0aGUgcHJpb3Igb24gZnVuY3Rpb24gc3BhY2Ugd2l0aApNYXRlcm4tMy8yIGNvdmFyaWFuY2UgZnVuY3Rpb24gYW5kIHNpZ21hX2Y9MSBhbmQKbGVuZ3Roc2NhbGVfZj0xLiBUaGUgc2FtZSByYW5kb20gbnVtYmVyIGdlbmVyYXRvciBzZWVkIHdhcyB1c2VkIHNvCnRoYXQgeW91IGNhbiBjb21wYXJlIHRoaXMgcGxvdCB0byB0aGUgYWJvdmUgb25lLiBNYXRlcm4tMy8yIGhhZAptb3JlIHByaW9yIG1hc3Mgb24gaGlnaGVyIGZyZXF1ZW5jaWVzIGFuZCB0aGUgcHJpb3IgZHJhd3MgYXJlIG1vcmUKd2lnZ2x5LgoKYGBge3IgfQpzZXQuc2VlZCgzNjUpCnFyIDwtIGJpbmRfcm93cyhsYXBwbHkoMTo0LCBmdW5jdGlvbihpKSB7CiAgcSAlPiUKICAgIG11dGF0ZShyPXJlcChybm9ybSgxNjApLHRpbWVzPTEwMCksZnI9ZipyKnNwZF9NYXRlcm4zMltpbmRdKSAlPiUKICAgIGdyb3VwX2J5KHgpICU+JQogICAgc3VtbWFyaXNlKGY9c3VtKGZyKSkgJT4lCiAgICBtdXRhdGUoaW5kPWkpIH0pKQpxciAlPiUKICBnZ3Bsb3QoYWVzKHg9eCwgeT1mLCBncm91cD1pbmQsIGNvbG9yPWZhY3RvcihpbmQpKSkgKwogIGdlb21fbGluZSgpKwogIGdlb21fdGV4dF9yZXBlbChkYXRhPWZpbHRlcihxciwgeD09MC4wMSksYWVzKHg9LTAuMDEseT1mLGxhYmVsPWluZCksCiAgICAgICAgICAgICAgICAgIGRpcmVjdGlvbj0ieSIpKwogIGdlb21fdGV4dF9yZXBlbChkYXRhPWZpbHRlcihxciwgeD09MSksYWVzKHg9MS4wMix5PWYsbGFiZWw9aW5kKSwKICAgICAgICAgICAgICAgICAgZGlyZWN0aW9uPSJ5IikrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uPSJub25lIikKYGBgCgpMZXQncyBkbyB0aGUgc2FtZSB3aXRoIGxlbmd0aHNjYWxlX2Y9MC4zCgpgYGB7ciB9CnN0YW5kYXRhYmYwIDwtIGxpc3QoeD1zZXEoMCwxLGxlbmd0aC5vdXQ9MTAwKSwKICAgICAgICAgICAgICAgICAgICBOPTEwMCwKICAgICAgICAgICAgICAgICAgICBjX2Y9MS41LCAjIGZhY3RvciBjIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGYxCiAgICAgICAgICAgICAgICAgICAgTV9mPTE2MCwgICMgbnVtYmVyIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGYxCiAgICAgICAgICAgICAgICAgICAgc2lnbWFfZj0xLAogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNjYWxlX2Y9MC4zKSAKZml4YmYwIDwtIG1vZGVsYmYwJHNhbXBsZShkYXRhPXN0YW5kYXRhYmYwLCBmaXhlZF9wYXJhbT1UUlVFLAogICAgICAgICAgICAgICAgICAgICAgICAgIGNoYWlucz0xLCBpdGVyPTEsIGl0ZXJfc2FtcGxpbmc9MSkKYGBgCgpUaGUgYmFzaXMgZnVuY3Rpb25zIGFyZSBleGFjdGx5IHRoZSBzYW1lLCBhbmQgb25seSB0aGUgc3BlY3RyYWwKZGVuc2l0aWVzIGhhdmUgY2hhbmdlZC4gTm93IHRoZSB3ZWlnaHQgZG9lc24ndCBkcm9wIGFzIGZhc3QgZm9yCnRoZSBtb3JlIHdpZ2dseSBiYXNpcyBmdW5jdGlvbnMuCgpgYGB7ciB9CnNwZF9FUSA8LSBhcy5tYXRyaXgoZml4YmYwJGRyYXdzKHZhcmlhYmxlPSdkaWFnU1BEX0VRX2YnKSkKcm91bmQoc3BkX0VRWzE6MTVdLDIpCnNwZF9NYXRlcm4zMiA8LSBhcy5tYXRyaXgoZml4YmYwJGRyYXdzKHZhcmlhYmxlPSdkaWFnU1BEX01hdGVybjMyX2YnKSkKcm91bmQoc3BkX01hdGVybjMyWzE6MTVdLDIpCmBgYAoKUGxvdCA0IHJhbmRvbSBkcmF3cyBmcm9tIHRoZSBwcmlvciBvbiBmdW5jdGlvbiBzcGFjZSB3aXRoCmV4cG9uZW50aWF0ZWQgcXVhZHJhdGljIGNvdmFyaWFuY2UgZnVuY3Rpb24gYW5kIHNpZ21hX2Y9MSBhbmQKbGVuZ3Roc2NhbGVfZj0wLjMuIFRoZSByYW5kb20gZnVuY3Rpb25zIGZyb20gdGhlIHByaW9yIGFyZSBub3cgbW9yZQp3aWdnbHkuIFRoZSBzYW1lIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yIHNlZWQgd2FzIHVzZWQgc28gdGhhdCB5b3UKY2FuIGNvbXBhcmUgdGhpcyBwbG90IHRvIHRoZSBhYm92ZSBvbmUuIEFib3ZlIHRoZSBwcmlvciBkcmF3IG51bWJlcgoyIGxvb2tzIGxpa2UgYSBkZWNyZWFzaW5nIHNsb3BlLiBIZXJlIHRoZSBwcmlvciBkcmF3IG51bWJlciAyIHN0aWxsCmhhcyBkb3dud2FyZCB0cmVuZCwgYnV0IGlzIG1vcmUgd2lnZ2x5LiBUaGUgc2FtZSByYW5kb20gZHJhdyBmcm9tCnRoZSBjb2VmZmljaWVudCBzcGFjZSBwcm9kdWNlcyBhIHdpZ2dsaWVyIGZ1bmN0aW9uIGFzIHRoZSBzcGVjdHJhbApkZW5zaXRpZXMgZ28gZG93biBzbG93ZXIgZm9yIHRoZSBtb3JlIHdpZ2dseSBiYXNpcyBmdW5jdGlvbnMuCgpgYGB7ciB9CnNldC5zZWVkKDM2NSkKcXIgPC0gYmluZF9yb3dzKGxhcHBseSgxOjQsIGZ1bmN0aW9uKGkpIHsKICBxICU+JQogICAgbXV0YXRlKHI9cmVwKHJub3JtKDE2MCksdGltZXM9MTAwKSxmcj1mKnIqc3BkX0VRW2luZF0pICU+JQogICAgZ3JvdXBfYnkoeCkgJT4lCiAgICBzdW1tYXJpc2UoZj1zdW0oZnIpKSAlPiUKICAgIG11dGF0ZShpbmQ9aSkgfSkpCnFyICU+JQogIGdncGxvdChhZXMoeD14LCB5PWYsIGdyb3VwPWluZCwgY29sb3I9ZmFjdG9yKGluZCkpKSArCiAgZ2VvbV9saW5lKCkrCiAgZ2VvbV90ZXh0X3JlcGVsKGRhdGE9ZmlsdGVyKHFyLCB4PT0wLjAxKSxhZXMoeD0tMC4wMSx5PWYsbGFiZWw9aW5kKSwKICAgICAgICAgICAgICAgICAgZGlyZWN0aW9uPSJ5IikrCiAgZ2VvbV90ZXh0X3JlcGVsKGRhdGE9ZmlsdGVyKHFyLCB4PT0xKSxhZXMoeD0xLjAyLHk9ZixsYWJlbD1pbmQpLAogICAgICAgICAgICAgICAgICBkaXJlY3Rpb249InkiKSsKICB0aGVtZShsZWdlbmQucG9zaXRpb249Im5vbmUiKQpgYGAKClBsb3QgNCByYW5kb20gZHJhd3MgZnJvbSB0aGUgcHJpb3Igb24gZnVuY3Rpb24gc3BhY2Ugd2l0aApNYXRlcm4tMy8yIGNvdmFyaWFuY2UgZnVuY3Rpb24gYW5kIHNpZ21hX2Y9MSBhbmQKbGVuZ3Roc2NhbGVfZj0wLjMuIFRoZSBwcmlvciBkcmF3cyBhcmUgbW9yZSB3aWdnbHkgdGhhbiB3aXRoCmV4cG9uZW50aWF0ZWQgcXVhZHJhdGljLgoKYGBge3IgfQpzZXQuc2VlZCgzNjUpCnFyIDwtIGJpbmRfcm93cyhsYXBwbHkoMTo0LCBmdW5jdGlvbihpKSB7CiAgcSAlPiUKICAgIG11dGF0ZShyPXJlcChybm9ybSgxNjApLHRpbWVzPTEwMCksZnI9ZipyKnNwZF9NYXRlcm4zMltpbmRdKSAlPiUKICAgIGdyb3VwX2J5KHgpICU+JQogICAgc3VtbWFyaXNlKGY9c3VtKGZyKSkgJT4lCiAgICBtdXRhdGUoaW5kPWkpIH0pKQpxciAlPiUKICBnZ3Bsb3QoYWVzKHg9eCwgeT1mLCBncm91cD1pbmQsIGNvbG9yPWZhY3RvcihpbmQpKSkgKwogIGdlb21fbGluZSgpKwogIGdlb21fdGV4dF9yZXBlbChkYXRhPWZpbHRlcihxciwgeD09MC4wMSksYWVzKHg9LTAuMDEseT1mLGxhYmVsPWluZCksCiAgICAgICAgICAgICAgICAgIGRpcmVjdGlvbj0ieSIpKwogIGdlb21fdGV4dF9yZXBlbChkYXRhPWZpbHRlcihxciwgeD09MSksYWVzKHg9MS4wMix5PWYsbGFiZWw9aW5kKSwKICAgICAgICAgICAgICAgICAgZGlyZWN0aW9uPSJ5IikrCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uPSJub25lIikKYGBgCgojIyBHUCB3aXRoIGJhc2lzIGZ1bmN0aW9ucyBmb3IgZgoKTW9kZWwgY29kZQoKYGBge3IgfQpmaWxlX2dwYmZmIDwtICJncGJmZi5zdGFuIgp3cml0ZUxpbmVzKHJlYWRMaW5lcyhmaWxlX2dwYmZmKSkKYGBgCgpDb21waWxlIFN0YW4gbW9kZWwKCmBgYHtyIHJlc3VsdHM9J2hpZGUnfQptb2RlbF9ncGJmZiA8LSBjbWRzdGFuX21vZGVsKHN0YW5fZmlsZSA9IGZpbGVfZ3BiZmYsIGluY2x1ZGVfcGF0aHMgPSAiLiIsIHN0YW5jX29wdGlvbnMgPSBsaXN0KCJPMSIpKQpgYGAKCkRhdGEgdG8gYmUgcGFzc2VkIHRvIFN0YW4KCmBgYHtyIH0Kc3RhbmRhdGFfZ3BiZmYgPC0gbGlzdCh4PW1jeWNsZSR0aW1lcywKICAgICAgICAgICAgICAgICAgICAgICAgeT1tY3ljbGUkYWNjZWwsCiAgICAgICAgICAgICAgICAgICAgICAgIE49bGVuZ3RoKG1jeWNsZSR0aW1lcyksCiAgICAgICAgICAgICAgICAgICAgICAgIGNfZj0xLjUsICMgZmFjdG9yIGMgb2YgYmFzaXMgZnVuY3Rpb25zIGZvciBHUCBmb3IgZjEKICAgICAgICAgICAgICAgICAgICAgICAgTV9mPTQwLCAgIyBudW1iZXIgb2YgYmFzaXMgZnVuY3Rpb25zIGZvciBHUCBmb3IgZjEKICAgICAgICAgICAgICAgICAgICAgICAgY19nPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBnMwogICAgICAgICAgICAgICAgICAgICAgICBNX2c9NDApICAjIG51bWJlciBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBnMwpgYGAKCiMjIE9wdGltaXplIGFuZCBmaW5kIE1BUCBlc3RpbWF0ZQoKYGBge3Igb3B0X2dwYmZmLCByZXN1bHRzPSdoaWRlJ30Kb3B0X2dwYmZmIDwtIG1vZGVsX2dwYmZmJG9wdGltaXplKGRhdGE9c3RhbmRhdGFfZ3BiZmYsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluaXQ9MC4xLCBhbGdvcml0aG09J2JmZ3MnKQpgYGAKCkNoZWNrIHdoZXRoZXIgcGFyYW1ldGVycyBoYXZlIHJlYXNvbmFibGUgdmFsdWVzCgpgYGB7ciB9Cm9kcmF3c19ncGJmZiA8LSBhc19kcmF3c19ydmFycyhvcHRfZ3BiZmYkZHJhd3MoKSkKc3Vic2V0KG9kcmF3c19ncGJmZiwgdmFyaWFibGU9YygnaW50ZXJjZXB0Jywnc2lnbWFfJywnbGVuZ3Roc2NhbGVfJyksCiAgICAgICByZWdleD1UUlVFKQpgYGAKCkNvbXBhcmUgdGhlIG1vZGVsIHRvIHRoZSBkYXRhCgpgYGB7ciB9Cm1jeWNsZSAlPiUKICBtdXRhdGUoRWY9bWVhbihvZHJhd3NfZ3BiZmYkZiksCiAgICAgICAgIHNpZ21hPW1lYW4ob2RyYXdzX2dwYmZmJHNpZ21hKSkgJT4lICAKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgb3B0aW1pemF0aW9uIGlzIG5vdCB0aGF0IGJhZC4gV2UgYXJlIG5vdyBvcHRpbWl6aW5nIHRoZSBqb2ludApwb3N0ZXJpb3Igb2YgMSBjb3ZhcmlhbmNlIGZ1bmN0aW9uIHBhcmFtZXRlcnMgYW5kIDQwIGJhc2lzCmZ1bmN0aW9uIGNvLWVmZmljaWVudHMuCgojIyBTYW1wbGUgdXNpbmcgZHluYW1pYyBITUMKCmBgYHtyIGZpdF9ncGJmZiwgcmVzdWx0cz0naGlkZSd9CmZpdF9ncGJmZiA8LSBtb2RlbF9ncGJmZiRzYW1wbGUoZGF0YT1zdGFuZGF0YV9ncGJmZiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJfd2FybXVwPTUwMCwgaXRlcl9zYW1wbGluZz01MDAsIHJlZnJlc2g9MTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCBhZGFwdF9kZWx0YT0wLjkpCmBgYAoKQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKCmBgYHtyIH0KZHJhd3NfZ3BiZmYgPC0gYXNfZHJhd3NfcnZhcnMoZml0X2dwYmZmJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQoZHJhd3NfZ3BiZmYsCiAgICAgICAgICAgICAgICAgICAgICAgdmFyaWFibGU9YygnaW50ZXJjZXB0Jywnc2lnbWFfJywnbGVuZ3Roc2NhbGVfJyksCiAgICAgICAgICAgICAgICAgICAgICAgcmVnZXg9VFJVRSkpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKGRyYXdzX2dwYmZmJGYpLAogICAgICAgICBzaWdtYT1tZWFuKGRyYXdzX2dwYmZmJHNpZ21hKSkgJT4lICAKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpUaGUgTUNNQyBpbnRlZ3JhdGlvbiB3b3JrcyB3ZWxsIGFuZCB0aGUgbW9kZWwgZml0IGxvb2tzIGdvb2QuIFRoZSBtb2RlbCBmaXQKaXMgY2xlYXJseSBtb3JlIHNtb290aCB0aGFuIHdpdGggb3B0aW1pemF0aW9uLgoKUGxvdCBwb3N0ZXJpb3IgZHJhd3MgYW5kIHBvc3RlcmlvciBtZWFuIG9mIHRoZSBtZWFuIGZ1bmN0aW9uCgpgYGB7ciB9CmRyYXdzX2dwYmZmICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBzcHJlYWRfcnZhcnMoZltpXSkgJT4lCiAgdW5uZXN0X3J2YXJzKCkgJT4lCiAgbXV0YXRlKHRpbWU9bWN5Y2xlJHRpbWVzW2ldKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZSwgeT1mLCBncm91cCA9IC5kcmF3KSkgKwogIGdlb21fbGluZShjb2xvcj1zZXQxWzJdLCBhbHBoYSA9IDAuMSkgKwogIGdlb21fcG9pbnQoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1hY2NlbCksIGluaGVyaXQuYWVzPUZBTFNFKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1tZWFuKGRyYXdzX2dwYmZmJGYpKSwKICAgICAgICAgICAgaW5oZXJpdC5hZXM9RkFMU0UsIGNvbG9yPXNldDFbMV0sIHNpemU9MSkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikKYGBgCgpXZSBjYW4gYWxzbyBwbG90IHRoZSBwb3N0ZXJpb3IgZHJhd3Mgb2YgdGhlIGxhdGVudCBmdW5jdGlvbnMsIHdoaWNoCmlzIGEgZ29vZCByZW1pbmRlciB0aGF0IGluZGl2aWR1YWwgZHJhd3MgYXJlIG1vcmUgd2lnZ2x5IHRoYW4gdGhlCmF2ZXJhZ2Ugb2YgdGhlIGRyYXdzLCBhbmQgdGh1cyBzaG93IGJldHRlciBhbHNvIHRoZSB1bmNlcnRhaW50eSwKZm9yIGV4YW1wbGUsIGluIHRoZSBlZGdlIG9mIHRoZSBkYXRhLgoKQ29tcGFyZSB0aGUgcG9zdGVyaW9yIGRyYXdzIHRvIHRoZSBvcHRpbWl6ZWQgcGFyYW1ldGVycwoKYGBge3IgfQpvZHJhd3NfZ3BiZmYgPC0gYXNfZHJhd3NfZGYob3B0X2dwYmZmJGRyYXdzKCkpCmRyYXdzX2dwYmZmICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBhc19kcmF3c19kZigpICU+JQogIGdncGxvdChhZXMoeD1sZW5ndGhzY2FsZV9mLHk9c2lnbWFfZikpKwogIGdlb21fcG9pbnQoY29sb3I9c2V0MVsyXSkrCiAgZ2VvbV9wb2ludChkYXRhPW9kcmF3c19ncGJmZixjb2xvcj1zZXQxWzFdLHNpemU9NCkrCiAgYW5ub3RhdGUoInRleHQiLHg9bWVkaWFuKGRyYXdzX2dwYmZmJGxlbmd0aHNjYWxlX2YpLAogICAgICAgICAgIHk9bWF4KGRyYXdzX2dwYmZmJHNpZ21hX2YpKzAuMSwKICAgICAgICAgICBsYWJlbD0nUG9zdGVyaW9yIGRyYXdzJyxoanVzdD0wLjUsY29sb3I9c2V0MVsyXSxzaXplPTYpKwogIGFubm90YXRlKCJ0ZXh0Iix4PW9kcmF3c19ncGJmZiRsZW5ndGhzY2FsZV9mKzAuMDEsCiAgICAgICAgICAgeT1vZHJhd3NfZ3BiZmYkc2lnbWFfZiwKICAgICAgICAgICBsYWJlbD0nT3B0aW1pemVkJyxoanVzdD0wLGNvbG9yPXNldDFbMV0sc2l6ZT02KQpgYGAKCk9wdGltaXphdGlvbiByZXN1bHQgaXMgZmFyIGZyb20gYmVpbmcgcmVwcmVzZW50YXRpdmUgb2YgdGhlCnBvc3Rlcmlvci4KCiMjIEdQIHdpdGggYmFzaXMgZnVuY3Rpb25zIGZvciBmIGFuZCBnCgpNb2RlbCBjb2RlCgpgYGB7ciB9CmZpbGVfZ3BiZmZnIDwtICJncGJmZmcuc3RhbiIKd3JpdGVMaW5lcyhyZWFkTGluZXMoZmlsZV9ncGJmZmcpKQpgYGAKCkNvbXBpbGUgU3RhbiBtb2RlbAoKYGBge3IgcmVzdWx0cz0naGlkZSd9Cm1vZGVsX2dwYmZmZyA8LSBjbWRzdGFuX21vZGVsKHN0YW5fZmlsZSA9IGZpbGVfZ3BiZmZnLCBpbmNsdWRlX3BhdGhzID0gIi4iLCBzdGFuY19vcHRpb25zID0gbGlzdCgiTzEiKSkKYGBgCgpEYXRhIHRvIGJlIHBhc3NlZCB0byBTdGFuCgpgYGB7ciB9CnN0YW5kYXRhX2dwYmZmZyA8LSBsaXN0KHg9bWN5Y2xlJHRpbWVzLAogICAgICAgICAgICAgICAgICAgICAgICB5PW1jeWNsZSRhY2NlbCwKICAgICAgICAgICAgICAgICAgICAgICAgTj1sZW5ndGgobWN5Y2xlJHRpbWVzKSwKICAgICAgICAgICAgICAgICAgICAgICAgY19mPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBmMQogICAgICAgICAgICAgICAgICAgICAgICBNX2Y9NDAsICAjIG51bWJlciBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBmMQogICAgICAgICAgICAgICAgICAgICAgICBjX2c9MS41LCAjIGZhY3RvciBjIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGczCiAgICAgICAgICAgICAgICAgICAgICAgIE1fZz00MCkgICMgbnVtYmVyIG9mIGJhc2lzIGZ1bmN0aW9ucyBmb3IgR1AgZm9yIGczCmBgYAoKIyMgT3B0aW1pemUgYW5kIGZpbmQgTUFQIGVzdGltYXRlCgpgYGB7ciBvcHRfZ3BiZmZnLCByZXN1bHRzPSdoaWRlJ30Kb3B0X2dwYmZmZyA8LSBtb2RlbF9ncGJmZmckb3B0aW1pemUoZGF0YT1zdGFuZGF0YV9ncGJmZmcsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluaXQ9MC4xLCBhbGdvcml0aG09J2JmZ3MnKQpgYGAKCkNoZWNrIHdoZXRoZXIgcGFyYW1ldGVycyBoYXZlIHJlYXNvbmFibGUgdmFsdWVzCgpgYGB7ciB9Cm9kcmF3c19ncGJmZmcgPC0gYXNfZHJhd3NfcnZhcnMob3B0X2dwYmZmZyRkcmF3cygpKQpzdWJzZXQob2RyYXdzX2dwYmZmZywgdmFyaWFibGU9YygnaW50ZXJjZXB0Jywnc2lnbWFfJywnbGVuZ3Roc2NhbGVfJyksCiAgICAgICByZWdleD1UUlVFKQpgYGAKCkNvbXBhcmUgdGhlIG1vZGVsIHRvIHRoZSBkYXRhCgpgYGB7ciB9Cm1jeWNsZSAlPiUKICBtdXRhdGUoRWY9bWVhbihvZHJhd3NfZ3BiZmZnJGYpLAogICAgICAgICBzaWdtYT1tZWFuKG9kcmF3c19ncGJmZmckc2lnbWEpKSAlPiUgIAogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShhZXMoeT1FZiksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShhZXMoeT1FZi0yKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKzIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKQpgYGAKClRoZSBvcHRpbWl6YXRpb24gb3ZlcmZpdHMsIGFzIHdlIGFyZSBub3cgb3B0aW1pemluZyB0aGUgam9pbnQKcG9zdGVyaW9yIG9mIDIgY292YXJpYW5jZSBmdW5jdGlvbiBwYXJhbWV0ZXJzIGFuZCAyIHggNDAgYmFzaXMKZnVuY3Rpb24gY28tZWZmaWNpZW50cy4KCiMjIFNhbXBsZSB1c2luZyBkeW5hbWljIEhNQwoKYGBge3IgZml0X2dwYmZmZywgcmVzdWx0cz0naGlkZSd9CmZpdF9ncGJmZmcgPC0gbW9kZWxfZ3BiZmZnJHNhbXBsZShkYXRhPXN0YW5kYXRhX2dwYmZmZywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGl0ZXJfd2FybXVwPTUwMCwgaXRlcl9zYW1wbGluZz01MDAsIHJlZnJlc2g9MTAwLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2hhaW5zPTQsIHBhcmFsbGVsX2NoYWlucz00LCBhZGFwdF9kZWx0YT0wLjkpCmBgYAoKQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKCmBgYHtyIH0KZHJhd3NfZ3BiZmZnIDwtIGFzX2RyYXdzX3J2YXJzKGZpdF9ncGJmZmckZHJhd3MoKSkKc3VtbWFyaXNlX2RyYXdzKHN1YnNldChkcmF3c19ncGJmZmcsCiAgICAgICAgICAgICAgICAgICAgICAgdmFyaWFibGU9YygnaW50ZXJjZXB0Jywnc2lnbWFfJywnbGVuZ3Roc2NhbGVfJyksCiAgICAgICAgICAgICAgICAgICAgICAgcmVnZXg9VFJVRSkpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKGRyYXdzX2dwYmZmZyRmKSwKICAgICAgICAgc2lnbWE9bWVhbihkcmF3c19ncGJmZmckc2lnbWEpKSAlPiUgIAogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShhZXMoeT1FZiksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShhZXMoeT1FZi0yKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKzIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKQpgYGAKClRoZSBNQ01DIGludGVncmF0aW9uIHdvcmtzIHdlbGwgYW5kIHRoZSBtb2RlbCBmaXQgbG9va3MgZ29vZC4KClBsb3QgcG9zdGVyaW9yIGRyYXdzIGFuZCBwb3N0ZXJpb3IgbWVhbiBvZiB0aGUgbWVhbiBmdW5jdGlvbgoKYGBge3IgfQpkcmF3c19ncGJmZmcgJT4lCiAgdGhpbl9kcmF3cyh0aGluPTUpICU+JQogIHNwcmVhZF9ydmFycyhmW2ldKSAlPiUKICB1bm5lc3RfcnZhcnMoKSAlPiUKICBtdXRhdGUodGltZT1tY3ljbGUkdGltZXNbaV0pICU+JQogIGdncGxvdChhZXMoeD10aW1lLCB5PWYsIGdyb3VwID0gLmRyYXcpKSArCiAgZ2VvbV9saW5lKGNvbG9yPXNldDFbMl0sIGFscGhhID0gMC4xKSArCiAgZ2VvbV9wb2ludChkYXRhPW1jeWNsZSwgbWFwcGluZz1hZXMoeD10aW1lcyx5PWFjY2VsKSwgaW5oZXJpdC5hZXM9RkFMU0UpKwogIGdlb21fbGluZShkYXRhPW1jeWNsZSwgbWFwcGluZz1hZXMoeD10aW1lcyx5PW1lYW4oZHJhd3NfZ3BiZmZnJGYpKSwKICAgICAgICAgICAgaW5oZXJpdC5hZXM9RkFMU0UsIGNvbG9yPXNldDFbMV0sIHNpemU9MSkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikKYGBgCgpXZSBjYW4gYWxzbyBwbG90IHRoZSBwb3N0ZXJpb3IgZHJhd3Mgb2YgdGhlIGxhdGVudCBmdW5jdGlvbnMsIHdoaWNoCmlzIGEgZ29vZCByZW1pbmRlciB0aGF0IGluZGl2aWR1YWwgZHJhd3MgYXJlIG1vcmUgd2lnZ2x5IHRoYW4gdGhlCmF2ZXJhZ2Ugb2YgdGhlIGRyYXdzLCBhbmQgdGh1cyBzaG93IGJldHRlciBhbHNvIHRoZSB1bmNlcnRhaW50eSwKZm9yIGV4YW1wbGUsIGluIHRoZSBlZGdlIG9mIHRoZSBkYXRhLgoKQ29tcGFyZSB0aGUgcG9zdGVyaW9yIGRyYXdzIHRvIHRoZSBvcHRpbWl6ZWQgcGFyYW1ldGVycwoKYGBge3IgfQpvZHJhd3NfZ3BiZmZnIDwtIGFzX2RyYXdzX2RmKG9wdF9ncGJmZmckZHJhd3MoKSkKZHJhd3NfZ3BiZmZnICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBhc19kcmF3c19kZigpICU+JQogIGdncGxvdChhZXMoeD1sZW5ndGhzY2FsZV9mLHk9c2lnbWFfZikpKwogIGdlb21fcG9pbnQoY29sb3I9c2V0MVsyXSkrCiAgZ2VvbV9wb2ludChkYXRhPW9kcmF3c19ncGJmZmcsY29sb3I9c2V0MVsxXSxzaXplPTQpKwogIGFubm90YXRlKCJ0ZXh0Iix4PW1lZGlhbihkcmF3c19ncGJmZmckbGVuZ3Roc2NhbGVfZiksCiAgICAgICAgICAgeT1tYXgoZHJhd3NfZ3BiZmZnJHNpZ21hX2YpKzAuMSwKICAgICAgICAgICBsYWJlbD0nUG9zdGVyaW9yIGRyYXdzJyxoanVzdD0wLjUsY29sb3I9c2V0MVsyXSxzaXplPTYpKwogIGFubm90YXRlKCJ0ZXh0Iix4PW9kcmF3c19ncGJmZmckbGVuZ3Roc2NhbGVfZiswLjAxLAogICAgICAgICAgIHk9b2RyYXdzX2dwYmZmZyRzaWdtYV9mLAogICAgICAgICAgIGxhYmVsPSdPcHRpbWl6ZWQnLGhqdXN0PTAsY29sb3I9c2V0MVsxXSxzaXplPTYpCmBgYAoKT3B0aW1pemF0aW9uIHJlc3VsdCBpcyBmYXIgZnJvbSBiZWluZyByZXByZXNlbnRhdGl2ZSBvZiB0aGUKcG9zdGVyaW9yLgoKIyMgTW9kZWwgY29tcGFyaXNvbgoKTG9va2luZyBhdCB0aGUgcGxvdHMgY29tcGFyaW5nIG1vZGVsIHByZWRpY3Rpb25zIGFuZCBkYXRhLCBpdCBpcwpxdWl0ZSBvYnZpb3VzIGluIHRoaXMgY2FzZSB0aGF0IHRoZSBoZXRlcm9za2VkYXN0aWMgbW9kZWwgaXMgYmV0dGVyCmZvciB0aGVzZSBkYXRhLiBJbiBjYXNlcyB3aGVuIGl0IGlzIG5vdCBhcyBjbGVhciwgd2UgY2FuIHVzZQpsZWF2ZS1vbmUtb3V0IGNyb3NzLXZhbGlkYXRpb24gY29tcGFyaXNvbi4gSGVyZSB3ZSBjb21wYXJlCmhvbW9za2VkYXN0aWMgYW5kIGhldGVyb3NrZWRhc3RpYyBtb2RlbHMuCgoKYGBge3IgfQpsb29iZmYgPC0gZml0X2dwYmZmJGxvbygpCmxvb2JmZmcgPC0gZml0X2dwYmZmZyRsb28oKQpsb29fY29tcGFyZShsaXN0KGhvbW9za2VkYXN0aWM9bG9vYmZmLGhldGVyb3NrZWRhc3RpYz1sb29iZmZnKSkKYGBgCgpIZXRlcm9za2VkYXN0aWMgbW9kZWwgaGFzIGNsZWFybHkgbXVjaCBoaWdoZXIgZWxwZCBlc3RpbWF0ZS4KCldlIGNhbiBwbG90IGFsc28gdGhlIGRpZmZlcmVuY2UgaW4gdGhlIHBvaW50d2lzZSBlbHBkIHZhbHVlcyAobG9nIHNjb3JlcykKc28gdGhhdCB3ZSBzZWUgaW4gd2hpY2ggcGFydHMgdGhlIGhldGVyb3NrZWRhc3RpYyBtb2RlbCBpcyBiZXR0ZXIKCgpgYGB7ciB9CmRhdGEuZnJhbWUodGltZT1tY3ljbGUkdGltZXMsCiAgICAgICAgICAgZWxwZF9kaWZmPWxvb2JmZmckcG9pbnR3aXNlWywnZWxwZF9sb28nXS1sb29iZmYkcG9pbnR3aXNlWywnZWxwZF9sb28nXSkgfD4KICBnZ3Bsb3QoYWVzKHg9dGltZSx5PWVscGRfZGlmZikpKwogIGdlb21fcG9pbnQoY29sb3I9c2V0MVsyXSkrCiAgZ2VvbV9obGluZSh5aW50ZXJjZXB0PTAsIGxpbmV0eXBlPSJkYXNoZWQiKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9VGVYKCJlbHBkIG9mIGhldGVyb3NrZWRhc3RpYyBHUCBpcyBoaWdoZXIgJFxccmlnaHRhcnJvdyQiKSkKYGBgCgojIyBWYXJpYXRpb25hbCBpbmZlcmVuY2UKClZhcmlhdGlvbmFsIGluZmVyZW5jZSBpcyBwb3B1bGFyIGluIG1hY2hpbmUgbGVhcm5pbmcgYW5kIGFsc28gd2l0aApHYXVzc2lhbiBwcm9jZXNzZXMuIFdoZW4gdXNlZCBjYXJlZnVsbHkgZm9yIHNlbGVjdGVkIG1vZGVscywKcGFyYW1ldGVycywgcGFyYW1ldGVyaXphdGlvbiwgYW5kIGFwcHJveGltYXRlIGRpc3RyaWJ1dGlvbiwKdmFyaWF0aW9uYWwgaW5mZXJlbmNlIGNhbiBiZSB1c2VmdWwgYW5kIGZhc3QuIFRoZSBmb2xsb3dpbmcgZXhhbXBsZQppbGx1c3RyYXRlcywgd2h5IGl0IGNhbiBhbHNvIGZhaWwgd2hlbiBhcHBsaWVkIGluIGJsYWNrIGJveCBzdHlsZS4KUnVuIGF1dG8tZGlmZmVyZW50aWF0ZWQgdmFyaWF0aW9uYWwgaW5mZXJlbmNlIChBRFZJKSB3aXRoIG1lYW5maWVsZApub3JtYWwgYXBwcm94aW1hdGlvbiwgYW5kIGluIHRoZSBlbmQsIHNhbXBsZSBmcm9tIHRoZQphcHByb3hpbWF0aW9uLgoKYGBge3IgdmlfZ3BiZmZnLCByZXN1bHRzPSdoaWRlJ30KdmlfZ3BiZmZnIDwtIG1vZGVsX2dwYmZmZyR2YXJpYXRpb25hbChkYXRhPXN0YW5kYXRhX2dwYmZmZywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbml0PTAuMDEsIHRvbF9yZWxfb2JqPTFlLTQsIGl0ZXI9MWU1LCByZWZyZXNoPTEwMDAsIHNlZWQ9NzUpCmBgYAoKQ2hlY2sgd2hldGhlciBwYXJhbWV0ZXJzIGhhdmUgcmVhc29uYWJsZSB2YWx1ZXMKCmBgYHtyIH0KdmlkcmF3c19ncGJmZmcgPC0gYXNfZHJhd3NfcnZhcnModmlfZ3BiZmZnJGRyYXdzKCkpCnN1bW1hcmlzZV9kcmF3cyhzdWJzZXQodmlkcmF3c19ncGJmZmcsCiAgICAgICAgICAgICAgICAgICAgICAgdmFyaWFibGU9YygnaW50ZXJjZXB0Jywnc2lnbWFfJywnbGVuZ3Roc2NhbGVfJyksCiAgICAgICAgICAgICAgICAgICAgICAgcmVnZXg9VFJVRSkpCmBgYAoKQ29tcGFyZSB0aGUgbW9kZWwgdG8gdGhlIGRhdGEKCmBgYHtyIH0KbWN5Y2xlICU+JQogIG11dGF0ZShFZj1tZWFuKHZpZHJhd3NfZ3BiZmZnJGYpLAogICAgICAgICBzaWdtYT1tZWFuKHZpZHJhd3NfZ3BiZmZnJHNpZ21hKSkgJT4lICAKICBnZ3Bsb3QoYWVzKHg9dGltZXMseT1hY2NlbCkpKwogIGdlb21fcG9pbnQoKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYpLCBjb2xvcj1zZXQxWzFdKSsKICBnZW9tX2xpbmUoYWVzKHk9RWYtMipzaWdtYSksIGNvbG9yPXNldDFbMV0sbGluZXR5cGU9ImRhc2hlZCIpKwogIGdlb21fbGluZShhZXMoeT1FZisyKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikKYGBgCgpBRFZJIGluZmVyZW5jZSBpcyBjYXRjaGluZyB0aGUgbWVhbiBmdW5jdGlvbiB3ZWxsLCBhbmQgc29tZSBvZiB0aGUKdmFyeWluZyBub2lzZSB2YXJpYW5jZSwgYnV0IGNsZWFybHkgb3ZlcmVzdGltYXRpbmcgdGhlIG5vaXNlCnZhcmlhbmNlIGluIHRoZSBlYXJseSBwYXJ0LgoKUGxvdCBwb3N0ZXJpb3IgZHJhd3MgYW5kIHBvc3RlcmlvciBtZWFuIG9mIHRoZSBtZWFuIGZ1bmN0aW9uCgpgYGB7ciB9CnZpZHJhd3NfZ3BiZmZnICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBzcHJlYWRfcnZhcnMoZltpXSkgJT4lCiAgdW5uZXN0X3J2YXJzKCkgJT4lCiAgbXV0YXRlKHRpbWU9bWN5Y2xlJHRpbWVzW2ldKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZSwgeT1mLCBncm91cCA9IC5kcmF3KSkgKwogIGdlb21fbGluZShjb2xvcj1zZXQxWzJdLCBhbHBoYSA9IDAuMSkgKwogIGdlb21fcG9pbnQoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1hY2NlbCksIGluaGVyaXQuYWVzPUZBTFNFKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1tZWFuKHZpZHJhd3NfZ3BiZmZnJGYpKSwKICAgICAgICAgICAgaW5oZXJpdC5hZXM9RkFMU0UsIGNvbG9yPXNldDFbMV0sIHNpemU9MSkrCiAgbGFicyh4PSJUaW1lIChtcykiLCB5PSJBY2NlbGVyYXRpb24gKGcpIikKYGBgCgpXZSBjYW4gYWxzbyBwbG90IHRoZSBwb3N0ZXJpb3IgZHJhd3Mgb2YgdGhlIGxhdGVudCBmdW5jdGlvbnMsIHdoaWNoCmlzIGEgZ29vZCByZW1pbmRlciB0aGF0IGluZGl2aWR1YWwgZHJhd3MgYXJlIG1vcmUgd2lnZ2x5IHRoYW4gdGhlCmF2ZXJhZ2Ugb2YgdGhlIGRyYXdzLCBhbmQgdGh1cyBzaG93IGJldHRlciBhbHNvIHRoZSB1bmNlcnRhaW50eSwKZm9yIGV4YW1wbGUsIGluIHRoZSBlZGdlIG9mIHRoZSBkYXRhLgoKQ29tcGFyZSB0aGUgZHJhd3MgZnJvbSB0aGUgdmFyaWF0aW9uYWwgYXBwcm94aW1hdGlvbiB0byB0aGUgTUNNQwpkcmF3cyBhbmQgb3B0aW1pemVkIHBhcmFtZXRlcnMuIFRoaXMgdGltZSBzaG93IGZbMV0gYW5kIGdbMV0gdG8KaWxsdXN0cmF0ZSB0aGUgY2hhbGxlbmdpbmcgZnVubmVsIHNoYXBlLiBBbHRob3VnaCB0aGUgaW5mZXJlbmNlCmhhcHBlbnMgaW4gdGhlIHNwYWNlIG9mIGJldGFfZiBhbmQgYmV0YV9nLCBmWzFdIGFuZCBnWzFdIGFyZSBsaW5lYXIKcHJvamVjdGlvbiBvZiBiZXRhX2YgYW5kIGJldGFfZywgYW5kIHRodXMgdGhlIGZ1bm5lbCBpcyBjYXVzaW5nIHRoZQpwcm9ibGVtcyBmb3IgQURWSS4gRnVsbCByYW5rIG5vcm1hbCBhcHByb3hpbWF0aW9uIHdvdWxkIG5vdCBiZSBhYmxlCnRvIGhlbHAgaGVyZS4KCmBgYHtyIH0Kb2RyYXdzX2dwYmZmZyA8LSBhc19kcmF3c19kZihvcHRfZ3BiZmZnJGRyYXdzKCkpCmRyYXdzX2dwYmZmZyAlPiUKICB0aGluX2RyYXdzKHRoaW49NSkgJT4lCiAgYXNfZHJhd3NfZGYoKSAlPiUKICBnZ3Bsb3QoYWVzKHg9YGZbMV1gLHk9bG9nKGBzaWdtYVsxXWApKSkrCiAgZ2VvbV9wb2ludChjb2xvcj1zZXQxWzJdKSsKICBnZW9tX3BvaW50KGRhdGE9YXNfZHJhd3NfZGYodmlkcmF3c19ncGJmZmcpLGNvbG9yPXNldDFbM10pKwogIGdlb21fcG9pbnQoZGF0YT1vZHJhd3NfZ3BiZmZnLGNvbG9yPXNldDFbMV0sc2l6ZT00KSsKICBhbm5vdGF0ZSgidGV4dCIseD1tZWRpYW4odmlkcmF3c19ncGJmZmckZlsxXSkrMS4zLAogICAgICAgICAgIHk9bWF4KGxvZyh2aWRyYXdzX2dwYmZmZyRzaWdtYVsxXSkpKzAuMSwKICAgICAgICAgICBsYWJlbD0nVmFyaWF0aW9uYWwgaW5mZXJlbmNlJyxoanVzdD0wLGNvbG9yPXNldDFbM10sc2l6ZT02KSsKICBhbm5vdGF0ZSgidGV4dCIseD1tZWRpYW4oZHJhd3NfZ3BiZmZnJGZbMV0pKzEsCiAgICAgICAgICAgeT1taW4obG9nKGRyYXdzX2dwYmZmZyRzaWdtYVsxXSkpLTAuMSwKICAgICAgICAgICBsYWJlbD0nTUNNQyBkcmF3cycsaGp1c3Q9MCxjb2xvcj1zZXQxWzJdLHNpemU9NikrCiAgYW5ub3RhdGUoInRleHQiLHg9b2RyYXdzX2dwYmZmZyRgZlsxXWArMSwKICAgICAgICAgICB5PWxvZyhvZHJhd3NfZ3BiZmZnJGBzaWdtYVsxXWApLAogICAgICAgICAgIGxhYmVsPSdPcHRpbWl6ZWQnLGhqdXN0PTAsY29sb3I9c2V0MVsxXSxzaXplPTYpKwogIGxhYnMoeT0iZ1sxXSIpCmBgYAoKIyBIZXRlcm9za2VkYXN0aWMgR1Agd2l0aCBNYXRlcm4gY292YXJpYW5jZSBmdW5jdGlvbiBhbmQgSGlsYmVydCBiYXNpcyBmdW5jdGlvbnMgCgpFeHBvbmVudGlhdGVkIHF1YWRyYXRpYyBpcyBzb21ldGltZXMgY29uc2lkZXJlZCB0byBiZSB0b28gc21vb3RoIGFzCmFsbCB0aGUgZGVyaXZhdGl2ZXMgYXJlIGNvbnRpbnVvcy4gRm9yIGNvbXBhcmlzb24gd2UgdXNlIE1hdGVybi0zLzIKY292YXJpYW5jZS4gVGhlIEhpbGJlcnQgc3BhY2UgYmFzaXMgZnVuY3Rpb25zIGFyZSB0aGUgc2FtZSBhbmQgb25seQp0aGUgc3BlY3RyYWwgZGVuc2l0eSB2YWx1ZXMgY2hhbmdlICh0aGF0IGlzIGRpZmZlcmVudCBiYXNpcwpmdW5jdGlvbnMgaGF2ZSBhIGRpZmZlcmVudCB3ZWlnaHRpbmcpLgoKIyMgTW9kZWwgY29kZQoKYGBge3IgfQpmaWxlX2dwYmZmZzIgPC0gImdwYmZmZ19tYXRlcm4uc3RhbiIKd3JpdGVMaW5lcyhyZWFkTGluZXMoZmlsZV9ncGJmZmcyKSkKYGBgCgpDb21waWxlIFN0YW4gbW9kZWwKCmBgYHtyIHJlc3VsdHM9J2hpZGUnfQptb2RlbF9ncGJmZmcyIDwtIGNtZHN0YW5fbW9kZWwoc3Rhbl9maWxlID0gZmlsZV9ncGJmZmcyLCBpbmNsdWRlX3BhdGhzID0gIi4iKQpgYGAKCkRhdGEgdG8gYmUgcGFzc2VkIHRvIFN0YW4KCmBgYHtyIH0Kc3RhbmRhdGFfZ3BiZmZnMiA8LSBsaXN0KHg9bWN5Y2xlJHRpbWVzLAogICAgICAgICAgICAgICAgICAgICAgICB5PW1jeWNsZSRhY2NlbCwKICAgICAgICAgICAgICAgICAgICAgICAgTj1sZW5ndGgobWN5Y2xlJHRpbWVzKSwKICAgICAgICAgICAgICAgICAgICAgICAgY19mPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBmMQogICAgICAgICAgICAgICAgICAgICAgICBNX2Y9MTYwLCAgIyBudW1iZXIgb2YgYmFzaXMgZnVuY3Rpb25zIGZvciBHUCBmb3IgZjEKICAgICAgICAgICAgICAgICAgICAgICAgY19nPTEuNSwgIyBmYWN0b3IgYyBvZiBiYXNpcyBmdW5jdGlvbnMgZm9yIEdQIGZvciBnMwogICAgICAgICAgICAgICAgICAgICAgICBNX2c9MTYwKSAgIyBudW1iZXIgb2YgYmFzaXMgZnVuY3Rpb25zIGZvciBHUCBmb3IgZzMKYGBgCgojIyBTYW1wbGUgdXNpbmcgZHluYW1pYyBITUMKCmBgYHtyIGZpdF9ncGJmZmcyLCByZXN1bHRzPSdoaWRlJ30KZml0X2dwYmZmZzIgPC0gbW9kZWxfZ3BiZmZnMiRzYW1wbGUoZGF0YT1zdGFuZGF0YV9ncGJmZmcyLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaXRlcl93YXJtdXA9NTAwLCBpdGVyX3NhbXBsaW5nPTUwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNoYWlucz00LCBwYXJhbGxlbF9jaGFpbnM9NCwgYWRhcHRfZGVsdGE9MC45KQpgYGAKCkNoZWNrIHdoZXRoZXIgcGFyYW1ldGVycyBoYXZlIHJlYXNvbmFibGUgdmFsdWVzCgpgYGB7ciB9CmRyYXdzX2dwYmZmZzIgPC0gYXNfZHJhd3NfcnZhcnMoZml0X2dwYmZmZzIkZHJhd3MoKSkKc3VtbWFyaXNlX2RyYXdzKHN1YnNldChkcmF3c19ncGJmZmcyLAogICAgICAgICAgICAgICAgICAgICAgIHZhcmlhYmxlPWMoJ2ludGVyY2VwdCcsJ3NpZ21hXycsJ2xlbmd0aHNjYWxlXycpLAogICAgICAgICAgICAgICAgICAgICAgIHJlZ2V4PVRSVUUpKQpgYGAKCkNvbXBhcmUgdGhlIG1vZGVsIHRvIHRoZSBkYXRhCgpgYGB7ciB9Cm1jeWNsZSAlPiUKICBtdXRhdGUoRWY9bWVhbihkcmF3c19ncGJmZmcyJGYpLAogICAgICAgICBzaWdtYT1tZWFuKGRyYXdzX2dwYmZmZzIkc2lnbWEpKSAlPiUgIAogIGdncGxvdChhZXMoeD10aW1lcyx5PWFjY2VsKSkrCiAgZ2VvbV9wb2ludCgpKwogIGxhYnMoeD0iVGltZSAobXMpIiwgeT0iQWNjZWxlcmF0aW9uIChnKSIpKwogIGdlb21fbGluZShhZXMoeT1FZiksIGNvbG9yPXNldDFbMV0pKwogIGdlb21fbGluZShhZXMoeT1FZi0yKnNpZ21hKSwgY29sb3I9c2V0MVsxXSxsaW5ldHlwZT0iZGFzaGVkIikrCiAgZ2VvbV9saW5lKGFlcyh5PUVmKzIqc2lnbWEpLCBjb2xvcj1zZXQxWzFdLGxpbmV0eXBlPSJkYXNoZWQiKQpgYGAKClRoZSBNQ01DIGludGVncmF0aW9uIHdvcmtzIHdlbGwgYW5kIHRoZSBtb2RlbCBmaXQgbG9va3MgZ29vZC4KClBsb3QgcG9zdGVyaW9yIGRyYXdzIGFuZCBwb3N0ZXJpb3IgbWVhbiBvZiB0aGUgbWVhbiBmdW5jdGlvbgoKYGBge3IgfQpkcmF3c19ncGJmZmcyICU+JQogIHRoaW5fZHJhd3ModGhpbj01KSAlPiUKICBzcHJlYWRfcnZhcnMoZltpXSkgJT4lCiAgdW5uZXN0X3J2YXJzKCkgJT4lCiAgbXV0YXRlKHRpbWU9bWN5Y2xlJHRpbWVzW2ldKSAlPiUKICBnZ3Bsb3QoYWVzKHg9dGltZSwgeT1mLCBncm91cCA9IC5kcmF3KSkgKwogIGdlb21fbGluZShjb2xvcj1zZXQxWzJdLCBhbHBoYSA9IDAuMSkgKwogIGdlb21fcG9pbnQoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1hY2NlbCksIGluaGVyaXQuYWVzPUZBTFNFKSsKICBnZW9tX2xpbmUoZGF0YT1tY3ljbGUsIG1hcHBpbmc9YWVzKHg9dGltZXMseT1tZWFuKGRyYXdzX2dwYmZmZzIkZikpLAogICAgICAgICAgICBpbmhlcml0LmFlcz1GQUxTRSwgY29sb3I9c2V0MVsxXSwgc2l6ZT0xKSsKICBsYWJzKHg9IlRpbWUgKG1zKSIsIHk9IkFjY2VsZXJhdGlvbiAoZykiKQpgYGAKCldlIHNlZSB0aGF0IHdoZW4gdXNpbmcgTWF0ZXJuLTMvMiBjb3ZhcmlhbmNlIGluc3RlYWQgb2YgdGhlCmV4cG9uZW50aWF0ZWQgcXVhZHJhdGljLCB0aGUgbW9kZWwgZml0IGlzIG1vcmUgd2lnZ2dseS4KCg==