Go back to the Contents page.


Press Show to reveal the code chunks.


# Set seed for reproducibility
set.seed(1982) 
# Set global options for all code chunks
knitr::opts_chunk$set(
  # Disable messages printed by R code chunks
  message = FALSE,    
  # Disable warnings printed by R code chunks
  warning = FALSE,    
  # Show R code within code chunks in output
  echo = TRUE,        
  # Include both R code and its results in output
  include = TRUE,     
  # Evaluate R code chunks
  eval = FALSE,       
  # Enable caching of R code chunks for faster rendering
  cache = FALSE,      
  # Align figures in the center of the output
  fig.align = "center",
  # Enable retina display for high-resolution figures
  retina = 2,
  # Show errors in the output instead of stopping rendering
  error = TRUE,
  # Do not collapse code and output into a single block
  collapse = FALSE
)
# Start the figure counter
fig_count <- 0
# Define the captioner function
captioner <- function(caption) {
  fig_count <<- fig_count + 1
  paste0("Figure ", fig_count, ": ", caption)
}
# remotes::install_github("davidbolin/rspde", ref = "devel")
# remotes::install_github("davidbolin/metricgraph", ref = "devel")
library(rSPDE)
library(MetricGraph)
library(grateful)
library(Matrix)

library(ggplot2)
library(reshape2)
library(plotly)

The Matérn covariance function is given by

\[ \varrho(h; \kappa, \nu, \sigma)=\dfrac{\sigma^{2}}{2^{\nu-1} \Gamma(\nu)}(\kappa|h|)^\nu K_\nu(\kappa|h|),\quad \sigma^2 = \dfrac{\Gamma(\nu)}{\Gamma(\nu+1/2)(4\pi)^{1/2}\kappa^{2\nu}\tau^2} \tag{1} \label{materncovariance} \]

and it is coded below as matern.covariance().

matern.covariance <- function(h, kappa, nu, sigma) {
    if (nu == 1 / 2) {
        C <- sigma^2 * exp(-kappa * abs(h))
    } else {
        C <- (sigma^2 / (2^(nu - 1) * gamma(nu))) *
            ((kappa * abs(h))^nu) * besselK(kappa * abs(h), nu)
        C[h == 0] <- sigma^2
    }
    return(C)
}

The derivatives of the Matérn covariance function can be computed using the following recursive relation. For example, the first derivative is given by

\[ \varrho'(h; \kappa, \nu, \sigma) = \begin{cases} 0, & h = 0 \\ -\dfrac{\kappa^2}{2(\nu - 1)} h \varrho(h; \kappa, \nu - 1, \sigma), & h \neq 0 \end{cases} \tag{2} \label{matern_derivative} \]

and it can be obtained by setting deriv = 1 in the function matern.derivative() below.

matern.derivative <- function(h, kappa, nu, sigma, deriv = 1) 
{
    if(deriv == 0) {
        C = matern.covariance(h, kappa = kappa, nu = nu, sigma = sigma)
        return(C)
    } else if (deriv == 1) {
        C = h * matern.covariance(h, kappa = kappa, nu = nu - 1, sigma = sigma)
        C[h == 0] = 0
        return(-(kappa^2/(2 * (nu - 1))) * C)
    }
    else if (deriv == 2) {
        C = matern.covariance(h, kappa = kappa, nu = nu - 1, sigma = sigma) + 
            h * matern.derivative(h, kappa = kappa, nu = nu - 1, 
                                  sigma = sigma, deriv = 1)
        return(-(kappa^2/(2 * (nu - 1))) * C)
    }
    else {
        C = (deriv - 1) * matern.derivative(h, kappa = kappa, 
                                            nu = nu - 1, sigma = sigma, 
                                            deriv = deriv - 2) + 
            h * matern.derivative(h, kappa = kappa, nu = nu - 
                                      1, sigma = sigma, deriv = deriv - 1)
        return(-(kappa^2/(2 * (nu - 1))) * C)
    }
    
}

From (Bolin, Mehandiratta, and Simas 2025, Proposition 1), we have the following decomposition

\[ \varrho_m^\alpha(h)=\varrho_{m, 0}^\alpha(h)+\sum_{i=1}^m \varrho_{m, i}^\alpha(h) \tag{3} \label{matern_p_decomposition} \]

where

\[ \varrho_{m, 0}^\alpha(h)=k \sigma^2 \cdot \begin{cases}\dfrac{c_\alpha \sqrt{4 \pi}}{\kappa} 1_{[h=0]}, & 0<\alpha<1 \\ \varrho\left(h ;\kappa,\lfloor\alpha\rfloor-\frac{1}{2}, \sqrt{ \frac{c_\alpha}{c_{\lfloor\alpha\rfloor}}}\right), & \alpha \geq 1\end{cases} \tag{4} \label{matern_0_covariance} \]

and

\[ \varrho_{m, i}^\alpha(h)=r_i \sigma^2 \cdot \begin{cases}\varrho\left(h ;\kappa_i, \frac{1}{2}, \sqrt{ \frac{c_\alpha \sqrt{\pi}}{\sqrt{1-p_i}}}\right), & 0<\alpha<1 \\ \frac{1}{p_i^{\lfloor\alpha\rfloor}} \varrho\left(h ; \kappa_i, \frac{1}{2}, \sqrt{\frac{c_\alpha \sqrt{\pi}}{\sqrt{1-p_i}}}\right)-\sum_{j=1}^{\lfloor\alpha\rfloor} \frac{1}{p_i^{\lfloor\alpha\rfloor+1-j}} \varrho\left(h ; \kappa, j-\frac{1}{2}, \sqrt{\frac{c_\alpha}{c_j}}\right), & \alpha \geq 1\end{cases} \tag{5} \label{matern_p_covariance} \]

and \(c_a:=\Gamma(a) / \Gamma(a-1 / 2), \kappa_i=\kappa \sqrt{1-p_i}\), and \(\varrho\) is the Matérn covariance \(\eqref{materncovariance}\).

Function matern.p() implements

\[ \dfrac{\varrho_{m, i}^\alpha(h)}{r_i\sigma^2} \] as given below. Function matern.p.deriv() implements the derivatives of this function.

Here are the details of what matern.p() does.

  • If p==0, then matern.p() returns \(\varrho(h = s-t; \kappa = \kappa, \nu = \alpha-1/2, \sigma = 1) =\dfrac{1}{2^{\nu-1} \Gamma(\nu)}(\kappa|h|)^\nu K_\nu(\kappa|h|)\). So if you want the full matern, just multiply by \(\sigma^2\). That is, \(\sigma^2*\)matern.p(s,t,kappa,p = 0, alpha) =\(\varrho(h = s-t; \kappa = \kappa, \nu = \alpha-1/2, \sigma = \sigma)\).

  • If p!=0, then

    • If \(0<\alpha<1\), then matern.p() returns \(\varrho(h = s-t; \kappa = \kappa\sqrt{1-p_i}, \nu = 1/2, \sigma = \sqrt{\frac{c_\alpha \sqrt{\pi}}{\sqrt{1-p_i}}}) = \frac{c_\alpha \sqrt{\pi}}{\sqrt{1-p_i}} \cdot \varrho(h = s-t; \kappa = \kappa\sqrt{1-p_i}, \nu = 1/2, \sigma=1)\)

The bottom line is

  • \(\varrho_{m, i}^\alpha(h)\) = \(r_i\sigma^2\)matern.p(s,t,kappa,p = p, alpha).

  • \(\dfrac{d^k}{dh^k}\varrho_{m, i}^\alpha(h)\) = \(r_i\sigma^2\)matern.p.deriv(s,t,kappa,p = p, alpha, deriv = k).

  • \(\mathbf{r}_i\left(t_1, t_2\right)=r_i\sigma^2\)matern.p.joint(s,t,kappa,p,alpha).

  • If p==0, then we are in the \(\alpha\in\mathbb{N}\) case so that \(\lfloor\alpha\rfloor=\alpha\) and hence \(c_\alpha/c_{\lfloor\alpha\rfloor} = 1\) and hence \(\varrho_{m, 0}^\alpha(h)=k \sigma^2\varrho(h;\kappa, \alpha-1/2,1)=k \sigma^2\)matern.p(s,t,kappa,p=0,alpha)

matern.p <- function(s,t,kappa,p,alpha){
    h <- s-t
    if(p==0){
        return(matern.covariance(h, kappa = kappa, nu = alpha - 1/2, sigma = 1))
    } else {
        ca <- gamma(alpha)/gamma(alpha-0.5)
        fa <- floor(alpha)
        kp <- kappa*sqrt(1-p)
        out <- matern.covariance(h, kappa = kp, nu = 1/2, 
                                 sigma = sqrt(ca*sqrt(pi)/sqrt(1-p)))
        if(alpha < 1) {
            return(out)
        } else {
            
            for(j in 1:fa) {
                out <- out - matern.covariance(h, kappa = kappa, nu = j-1/2, 
                                               sigma = sqrt(ca*gamma(j-0.5)/gamma(j)))/p^(1 - j)
            }
            out <- out/p^fa
            return(out)    
        }
    }
}

matern.p.deriv <- function(s,t,kappa,p,alpha,deriv = 0){
    h <- s-t
    if(deriv ==0){
        return(matern.p(s,t,kappa,p,alpha))
    } else {
        if(p==0){
            return(matern.derivative(h, kappa = kappa, nu = alpha - 1/2, 
                                     sigma = 1, deriv = deriv))
        } else {
            ca <- gamma(alpha)/gamma(alpha-0.5)
            fa <- floor(alpha)
            kp <- kappa*sqrt(1-p)
            out <- matern.derivative(h, kappa = kp, nu =  1/2, 
                                     sigma = sqrt(ca*sqrt(pi)/sqrt(1-p)), deriv = deriv)
            if(alpha < 1) {
                return(out)
            } else {
                out <- out/p^fa
                for(j in 1:fa) {
                    out <- out - matern.derivative(h, kappa = kappa, nu = j-1/2, 
                                                   sigma = sqrt(ca*gamma(j-0.5)/gamma(j)), 
                                                   deriv = deriv)/p^(fa + 1 - j)
                }
            }
            return(out)
        }    
    }
    
}

Function matern.p.joint() computes the joint covariance matrix of the process and its derivatives up to order floor(alpha) for the shifted Matérn covariance. That is, it computes

\[ \mathbf{r}_i: \mathbb{R} \times \mathbb{R} \mapsto \mathbb{R}^{\lceil\alpha\rceil\times \lceil\alpha\rceil}, \quad \mathbf{r}_i\left(t_1, t_2\right)=\left[\frac{\partial^{i-1}}{\partial t_2^{i-1}} \frac{\partial^{j-1}}{\partial t_1^{j-1}} \dfrac{\varrho_{m, i}^\alpha\left(t_1-t_2\right)}{r_i\sigma^2}\right]_{i j \in\{1,2, \ldots, \lceil\alpha\rceil\}} \tag{2} \label{r_matrix} \] which is the multivariate covariance function of \((u_i(t), u_i'(t), \ldots, u_i^{(\lfloor\alpha\rfloor)}(t))\) and \(u_i\) is a shifted Whittle–Matérn bridge process with covariance function \(\varrho_{m, i}^\alpha(h)/(r_i\sigma^2)\).

#Joint covariance of process and derivative for shifted Matern
matern.p.joint <- function(s,t,kappa,p, alpha = 1){
    
    if(alpha%%1 == 0) {
        fa <- alpha
    } else {
        fa <- floor(alpha) + 1    
    }
    mat <- matrix(0, nrow = fa, ncol = fa)
    for(i in 1:fa) {
        for(j in i:fa) {
            if(i==j) {
                mat[i,i] <- ((-1)^(i-1))*matern.p.deriv(s,t,kappa,p,alpha, deriv = 2*(i-1))
            } else {
                tmp <- matern.p.deriv(s,t,kappa,p,alpha, deriv = i-1 + j - 1)
                mat[i,j] <- (-1)^(j-1)*tmp
                mat[j,i] <- (-1)^(i-1)*tmp
            }
        }
    }
    
    return(mat)
}
{r}
mat1 <- matern.p.joint(s = 0.6, t = 0.5, kappa = 10, p = 0.3, alpha = 2)
mat2 <- matern.p.joint(s = 0.6, t = 0.5, kappa = 10, p = 0.3, alpha = 3)
mat1
mat2
exp_precision <- function(loc, kappa, boundary = "free") {
    n <- length(loc)
    l <- diff(loc)
    
    # Precompute reusable terms
    a <- exp(-2 * kappa * l)
    b <- 1 - a
    
    # Initialize matrix Q efficiently
    Q <- Matrix(0, nrow = n, ncol = n)
    
    # Set diagonal elements
    diag(Q)[1:(n-1)] <- 1/2 + a/b
    diag(Q)[2:n] <- diag(Q)[2:n] + 1/2 + a/b
    
    # Set off-diagonal elements
    #  indices <- c(which(row(Q) == col(Q) + 1), which(row(Q) == col(Q) - 1))
    # off_diag_values <- -exp(-kappa * l) /b
    # Q[indices] <- off_diag_values
    
    
    row_indices <- seq_len(n - 1)
    col_indices <- row_indices + 1  # Offsets for off-diagonal elements
    
    # Compute the off-diagonal values
    off_diag_values <- -exp(-kappa * l)/b
    
    # Set the off-diagonal elements in matrix Q
    Q[cbind(row_indices, col_indices)] <- off_diag_values
    Q[cbind(col_indices, row_indices)] <- off_diag_values
    
    # Adjust boundary conditions if required
    if (boundary == "free") {
        Q[1, 1] <- Q[1, 1] + 0.5
        Q[n, n] <- Q[n, n] + 0.5
    }
    
    return(2 * kappa * Q[])
}
{r}
# Example usage of exp_precision function
loc <- seq(0, 1, length.out = 10)
kappa <- 5
Q_matrix <- exp_precision(loc, kappa, boundary = "free")
print(Q_matrix)
matern.p.precision <- function(loc,kappa,p,equally_spaced = FALSE, alpha = 1) {
    
    n <- length(loc)
    if(alpha==1) {
        Q <- exp_precision(loc,kappa)/(2*kappa)
        A <- Diagonal(n)
        
        return(list(Q=Q,A=A))
    } else {
        if(alpha%%1 == 0) {
            fa <- alpha
        } else {
            fa <- floor(alpha) + 1    
        }
        
        if(fa == 1) {
            N <- n  + n - 1 
        } else {
            N <- n*fa^2 + (n-1)*fa^2 - n*fa*(fa -1)/2    
        }
        
        ii <- numeric(N)
        jj <- numeric(N)
        val <- numeric(N)
        
        if(equally_spaced){
            Q.1 <- solve(rbind(cbind(matern.p.joint(loc[1],loc[1],kappa,p,alpha), 
                                     matern.p.joint(loc[1],loc[1+1],kappa,p,alpha)),
                               cbind(matern.p.joint(loc[1+1],loc[1],kappa,p,alpha), 
                                     matern.p.joint(loc[1+1],loc[1+1],kappa,p,alpha))))
            
            Q.i <- solve(rbind(cbind(matern.p.joint(loc[1],loc[1],kappa,p,alpha), 
                                     matern.p.joint(loc[1],loc[2],kappa,p,alpha),
                                     matern.p.joint(loc[1],loc[3],kappa,p,alpha)),
                               cbind(matern.p.joint(loc[2],loc[1],kappa,p,alpha),
                                     matern.p.joint(loc[2],loc[2],kappa,p,alpha),
                                     matern.p.joint(loc[2],loc[3],kappa,p,alpha)),
                               cbind(matern.p.joint(loc[3],loc[1],kappa,p,alpha),
                                     matern.p.joint(loc[3],loc[2],kappa,p,alpha),
                                     matern.p.joint(loc[3],loc[3],kappa,p,alpha))))[-c(1:fa),-c(1:fa)]
        }
        
        
        for(i in 1:max((n-1),1)){
            if(i==1){
                if(!equally_spaced){
                    Q.1 <- solve(rbind(cbind(matern.p.joint(loc[i],loc[i],kappa,p,alpha),
                                             matern.p.joint(loc[i],loc[i+1],kappa,p,alpha)),
                                       cbind(matern.p.joint(loc[i+1],loc[i],kappa,p,alpha),
                                             matern.p.joint(loc[i+1],loc[i+1],kappa,p,alpha))))
                    
                } 
                counter <- 1
                for(ki in 1:fa) {
                    for(kj in ki:(2*fa)) {
                        ii[counter] <- ki
                        jj[counter] <- kj
                        val[counter] <- Q.1[ki,kj]
                        counter <- counter + 1
                    }
                }
            } else {
                if(!equally_spaced){
                    Q.i <- solve(rbind(cbind(matern.p.joint(loc[i-1],loc[i-1],kappa,p,alpha),
                                             matern.p.joint(loc[i-1],loc[i],kappa,p,alpha),
                                             matern.p.joint(loc[i-1],loc[i+1],kappa,p,alpha)),
                                       cbind(matern.p.joint(loc[i],loc[i-1],kappa,p,alpha),
                                             matern.p.joint(loc[i],loc[i],kappa,p,alpha),
                                             matern.p.joint(loc[i],loc[i+1],kappa,p,alpha)),
                                       cbind(matern.p.joint(loc[i+1],loc[i-1],kappa,p,alpha),
                                             matern.p.joint(loc[i+1],loc[i],kappa,p,alpha),
                                             matern.p.joint(loc[i+1],loc[i+1],kappa,p,alpha))))[-c(1:fa),-c(1:fa)]
                } 
                # Q[(2*n-1):(2*n), (2*n-3):(2*n)] = Q.i[3:4,]
                for(ki in 1:fa){
                    for(kj in ki:(2*fa)){
                        ii[counter] <- fa*(i-1) + ki
                        jj[counter] <- fa*(i-1) + kj
                        val[counter] <-Q.i[ki,kj]
                        counter <- counter + 1
                    }
                }     
            }
        }
        if(n<=2){
            Q.i <- Q.1
        }
        for(ki in 1:fa){
            for(kj in ki:fa){
                ii[counter] <- fa*(n-1) + ki
                jj[counter] <- fa*(n-1) + kj
                val[counter] <-Q.i[ki+fa,kj+fa]
                counter <- counter + 1
            }
        }    
        Q <- Matrix::sparseMatrix(i   = ii,
                                  j    = jj,
                                  x    = val,
                                  dims = c(fa*n, fa*n), symmetric=TRUE)
        
        A <-  Matrix::sparseMatrix(i   = 1:n,
                                   j    = seq(from=1,to=n*fa,by=fa),
                                   x    = rep(1,n),
                                   dims = c(n, fa*n))
        return(list(Q=Q,A=A))    
    }
}
{r}
aux <-  matern.p.precision(loc = c(0,1,2), kappa = 10, p = 0.3, equally_spaced = TRUE, alpha = 2.2)
aux$Q
aux$A
{r}
# ------------ DATA ----------------------------------------------------------
kappa <- 25
nu <- 3/2
alpha <- nu + 1/2
sigma <- 1
p <- 0.3
x <- seq(0, 1, length.out = 1001)
h <- abs(x - 0.5)

y1 <- matern.covariance(h, kappa = kappa, nu = nu, sigma = sigma)
y2 <- matern.derivative(h, kappa = kappa, nu = nu, sigma = sigma, deriv = 1)
y3 <- matern.derivative(h, kappa = kappa, nu = nu, sigma = sigma, deriv = 2)

y4 <- matern.p(s = x, t = 0.5, kappa = kappa, p = 0, alpha = alpha)
y5 <- matern.p(s = x, t = 0.5, kappa = kappa, p = p, alpha = alpha)
y6 <- sapply(x, function(si) matern.p.joint(s = si, t = 0.5, kappa = kappa, p = p, alpha = alpha)[1,1])
y7 <- matern.p.deriv(s = x, t = 0.5, kappa = kappa, p = p, alpha = alpha, deriv = 1)
y8 <- sapply(x, function(si) matern.p.joint(s = si, t = 0.5, kappa = kappa, p = p, alpha = alpha)[2,2])
# ------------ SCALING -------------------------------------------------------

s1 <- max(abs(y1))
s2 <- max(abs(y2))
s3 <- max(abs(y3))
s4 <- max(abs(y4))
s5 <- max(abs(y5))
s6 <- max(abs(y6))
s7 <- max(abs(y7))
s8 <- max(abs(y8))

z1 <- y1 / s1
z2 <- y2 / s2
z3 <- y3 / s3
z4 <- y4 / s4
z5 <- y5 / s5
z6 <- y6 / s6
z7 <- y7 / s7
z8 <- y8 / s8

# ------------ PLOT ----------------------------------------------------------

plot_ly() %>%
  add_trace(
    x = ~x, y = ~0, z = ~z1,
    type = "scatter3d", mode = "lines",
    name = paste0("Matérn (1/", round(s1, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~1, z = ~z2,
    type = "scatter3d", mode = "lines",
    name = paste0("Matérn' (1/", round(s2, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~2, z = ~z3,
    type = "scatter3d", mode = "lines",
    name = paste0("Matérn'' (1/", round(s3, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~3, z = ~z4,
    type = "scatter3d", mode = "lines",
    name = paste0("matern.0 (1/", round(s4, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~4, z = ~z5,
    type = "scatter3d", mode = "lines",
    name = paste0("matern.p (1/", round(s5, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~5, z = ~z6,
    type = "scatter3d", mode = "lines",
    name = paste0("matern.p joint (1/", round(s6, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~6, z = ~z7,
    type = "scatter3d", mode = "lines",
    name = paste0("matern.p' (1/", round(s7, 3), ")")
  ) %>%
  add_trace(
    x = ~x, y = ~7, z = ~z8,
    type = "scatter3d", mode = "lines",
    name = paste0("matern.p joint' (1/", round(s8, 3), ")")
  ) %>%
  layout(
    scene = list(
      xaxis = list(title = "x"),
      yaxis = list(title = "Curve index"),
      zaxis = list(title = "Scaled value [-1, 1]")
    ),
    legend = list(title = list(text = "<b>Functions</b>"))
  )
Bolin, David, Vaibhav Mehandiratta, and Alexandre B. Simas. 2025. “Linear Cost and Exponentially Convergent Approximation of Gaussian Matérn Processes on Intervals.” https://arxiv.org/abs/2410.13000.
LS0tCnRpdGxlOiAiTWF0w6lybiBGdW5jdGlvbnMiCmRhdGU6ICJMYXN0IG1vZGlmaWVkOiBgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVkLSVtLSVZLicpYCIKb3V0cHV0OgogIGh0bWxfZG9jdW1lbnQ6CiAgICBtYXRoamF4OiAiaHR0cHM6Ly9jZG4uanNkZWxpdnIubmV0L25wbS9tYXRoamF4QDMvZXM1L3RleC1tbWwtY2h0bWwuanMiCiAgICBoaWdobGlnaHQ6IHB5Z21lbnRzCiAgICB0aGVtZTogZmxhdGx5CiAgICBjb2RlX2ZvbGRpbmc6IHNob3cgIyBjbGFzcy5zb3VyY2UgPSAiZm9sZC1oaWRlIiB0byBoaWRlIGNvZGUgYW5kIGFkZCBhIGJ1dHRvbiB0byBzaG93IGl0CiAgICBkZl9wcmludDogcGFnZWQKICAgIHRvYzogdHJ1ZQogICAgdG9jX2Zsb2F0OgogICAgICBjb2xsYXBzZWQ6IHRydWUKICAgICAgc21vb3RoX3Njcm9sbDogdHJ1ZQogICAgbnVtYmVyX3NlY3Rpb25zOiB0cnVlCiAgICBmaWdfY2FwdGlvbjogdHJ1ZQogICAgY29kZV9kb3dubG9hZDogdHJ1ZQogICAgY3NzOiB2aXN1YWwuY3NzCmFsd2F5c19hbGxvd19odG1sOiB0cnVlCmJpYmxpb2dyYXBoeTogCiAgLSByZWZlcmVuY2VzLmJpYgogIC0gZ3JhdGVmdWwtcmVmcy5iaWIKaGVhZGVyLWluY2x1ZGVzOgogIC0gXG5ld2NvbW1hbmR7XGFyfXtcbWF0aGJie1J9fQogIC0gXG5ld2NvbW1hbmR7XGxsYXZ9WzFde1xsZWZ0XHsjMVxyaWdodFx9fQogIC0gXG5ld2NvbW1hbmR7XHBhcmV9WzFde1xsZWZ0KCMxXHJpZ2h0KX0KICAtIFxuZXdjb21tYW5ke1xOY2FsfXtcbWF0aGNhbHtOfX0KICAtIFxuZXdjb21tYW5ke1xWY2FsfXtcbWF0aGNhbHtWfX0KICAtIFxuZXdjb21tYW5ke1xFY2FsfXtcbWF0aGNhbHtFfX0KICAtIFxuZXdjb21tYW5ke1xXY2FsfXtcbWF0aGNhbHtXfX0KLS0tCgpHbyBiYWNrIHRvIHRoZSBbQ29udGVudHNdKGFib3V0Lmh0bWwpIHBhZ2UuCgo8ZGl2IHN0eWxlPSJjb2xvcjogIzJjM2U1MDsgdGV4dC1hbGlnbjogcmlnaHQ7Ij4KKioqKioqKiogIAo8c3Ryb25nPlByZXNzIFNob3cgdG8gcmV2ZWFsIHRoZSBjb2RlIGNodW5rcy48L3N0cm9uZz4gIAoKKioqKioqKioKPC9kaXY+CgoKYGBge3IsIHB1cmwgPSBGQUxTRSwgZWNobyA9IEZBTFNFfQojIENyZWF0ZSBhIGNsaXBib2FyZCBidXR0b24gb24gdGhlIHJlbmRlcmVkIEhUTUwgcGFnZQpzb3VyY2UoaGVyZTo6aGVyZSgiY2xpcGJvYXJkLlIiKSk7IGNsaXBib2FyZApgYGAKCgpgYGB7ciwgcHVybCA9IEZBTFNFLCBjbGFzcy5zb3VyY2UgPSAiZm9sZC1oaWRlIn0KIyBTZXQgc2VlZCBmb3IgcmVwcm9kdWNpYmlsaXR5CnNldC5zZWVkKDE5ODIpIAojIFNldCBnbG9iYWwgb3B0aW9ucyBmb3IgYWxsIGNvZGUgY2h1bmtzCmtuaXRyOjpvcHRzX2NodW5rJHNldCgKICAjIERpc2FibGUgbWVzc2FnZXMgcHJpbnRlZCBieSBSIGNvZGUgY2h1bmtzCiAgbWVzc2FnZSA9IEZBTFNFLCAgICAKICAjIERpc2FibGUgd2FybmluZ3MgcHJpbnRlZCBieSBSIGNvZGUgY2h1bmtzCiAgd2FybmluZyA9IEZBTFNFLCAgICAKICAjIFNob3cgUiBjb2RlIHdpdGhpbiBjb2RlIGNodW5rcyBpbiBvdXRwdXQKICBlY2hvID0gVFJVRSwgICAgICAgIAogICMgSW5jbHVkZSBib3RoIFIgY29kZSBhbmQgaXRzIHJlc3VsdHMgaW4gb3V0cHV0CiAgaW5jbHVkZSA9IFRSVUUsICAgICAKICAjIEV2YWx1YXRlIFIgY29kZSBjaHVua3MKICBldmFsID0gRkFMU0UsICAgICAgIAogICMgRW5hYmxlIGNhY2hpbmcgb2YgUiBjb2RlIGNodW5rcyBmb3IgZmFzdGVyIHJlbmRlcmluZwogIGNhY2hlID0gRkFMU0UsICAgICAgCiAgIyBBbGlnbiBmaWd1cmVzIGluIHRoZSBjZW50ZXIgb2YgdGhlIG91dHB1dAogIGZpZy5hbGlnbiA9ICJjZW50ZXIiLAogICMgRW5hYmxlIHJldGluYSBkaXNwbGF5IGZvciBoaWdoLXJlc29sdXRpb24gZmlndXJlcwogIHJldGluYSA9IDIsCiAgIyBTaG93IGVycm9ycyBpbiB0aGUgb3V0cHV0IGluc3RlYWQgb2Ygc3RvcHBpbmcgcmVuZGVyaW5nCiAgZXJyb3IgPSBUUlVFLAogICMgRG8gbm90IGNvbGxhcHNlIGNvZGUgYW5kIG91dHB1dCBpbnRvIGEgc2luZ2xlIGJsb2NrCiAgY29sbGFwc2UgPSBGQUxTRQopCiMgU3RhcnQgdGhlIGZpZ3VyZSBjb3VudGVyCmZpZ19jb3VudCA8LSAwCiMgRGVmaW5lIHRoZSBjYXB0aW9uZXIgZnVuY3Rpb24KY2FwdGlvbmVyIDwtIGZ1bmN0aW9uKGNhcHRpb24pIHsKICBmaWdfY291bnQgPDwtIGZpZ19jb3VudCArIDEKICBwYXN0ZTAoIkZpZ3VyZSAiLCBmaWdfY291bnQsICI6ICIsIGNhcHRpb24pCn0KYGBgCgoKCmBgYHtyfQojIHJlbW90ZXM6Omluc3RhbGxfZ2l0aHViKCJkYXZpZGJvbGluL3JzcGRlIiwgcmVmID0gImRldmVsIikKIyByZW1vdGVzOjppbnN0YWxsX2dpdGh1YigiZGF2aWRib2xpbi9tZXRyaWNncmFwaCIsIHJlZiA9ICJkZXZlbCIpCmxpYnJhcnkoclNQREUpCmxpYnJhcnkoTWV0cmljR3JhcGgpCmxpYnJhcnkoZ3JhdGVmdWwpCmxpYnJhcnkoTWF0cml4KQoKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KHJlc2hhcGUyKQpsaWJyYXJ5KHBsb3RseSkKYGBgCgoKVGhlIE1hdMOpcm4gY292YXJpYW5jZSBmdW5jdGlvbiBpcyBnaXZlbiBieQoKJCQKXHZhcnJobyhoOyBca2FwcGEsIFxudSwgXHNpZ21hKT1cZGZyYWN7XHNpZ21hXnsyfX17Ml57XG51LTF9IFxHYW1tYShcbnUpfShca2FwcGF8aHwpXlxudSBLX1xudShca2FwcGF8aHwpLFxxdWFkIFxzaWdtYV4yID0gXGRmcmFje1xHYW1tYShcbnUpfXtcR2FtbWEoXG51KzEvMikoNFxwaSleezEvMn1ca2FwcGFeezJcbnV9XHRhdV4yfQpcdGFnezF9ClxsYWJlbHttYXRlcm5jb3ZhcmlhbmNlfQokJAoKYW5kIGl0IGlzIGNvZGVkIGJlbG93IGFzIGBtYXRlcm4uY292YXJpYW5jZSgpYC4KCmBgYHtyfQptYXRlcm4uY292YXJpYW5jZSA8LSBmdW5jdGlvbihoLCBrYXBwYSwgbnUsIHNpZ21hKSB7CiAgICBpZiAobnUgPT0gMSAvIDIpIHsKICAgICAgICBDIDwtIHNpZ21hXjIgKiBleHAoLWthcHBhICogYWJzKGgpKQogICAgfSBlbHNlIHsKICAgICAgICBDIDwtIChzaWdtYV4yIC8gKDJeKG51IC0gMSkgKiBnYW1tYShudSkpKSAqCiAgICAgICAgICAgICgoa2FwcGEgKiBhYnMoaCkpXm51KSAqIGJlc3NlbEsoa2FwcGEgKiBhYnMoaCksIG51KQogICAgICAgIENbaCA9PSAwXSA8LSBzaWdtYV4yCiAgICB9CiAgICByZXR1cm4oQykKfQpgYGAKClRoZSBkZXJpdmF0aXZlcyBvZiB0aGUgTWF0w6lybiBjb3ZhcmlhbmNlIGZ1bmN0aW9uIGNhbiBiZSBjb21wdXRlZCB1c2luZyB0aGUgZm9sbG93aW5nIHJlY3Vyc2l2ZSByZWxhdGlvbi4gRm9yIGV4YW1wbGUsIHRoZSBmaXJzdCBkZXJpdmF0aXZlIGlzIGdpdmVuIGJ5CgokJApcdmFycmhvJyhoOyBca2FwcGEsIFxudSwgIFxzaWdtYSkgPSAKXGJlZ2lue2Nhc2VzfQowLCAmIGggPSAwIFxcCi1cZGZyYWN7XGthcHBhXjJ9ezIoXG51IC0gMSl9IGggXHZhcnJobyhoOyBca2FwcGEsIFxudSAtIDEsICBcc2lnbWEpLCAmIGggXG5lcSAwClxlbmR7Y2FzZXN9Clx0YWd7Mn0KXGxhYmVse21hdGVybl9kZXJpdmF0aXZlfQokJAoKYW5kIGl0IGNhbiBiZSBvYnRhaW5lZCBieSBzZXR0aW5nIGBkZXJpdiA9IDFgIGluIHRoZSBmdW5jdGlvbiBgbWF0ZXJuLmRlcml2YXRpdmUoKWAgYmVsb3cuCgpgYGB7cn0KbWF0ZXJuLmRlcml2YXRpdmUgPC0gZnVuY3Rpb24oaCwga2FwcGEsIG51LCBzaWdtYSwgZGVyaXYgPSAxKSAKewogICAgaWYoZGVyaXYgPT0gMCkgewogICAgICAgIEMgPSBtYXRlcm4uY292YXJpYW5jZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IG51LCBzaWdtYSA9IHNpZ21hKQogICAgICAgIHJldHVybihDKQogICAgfSBlbHNlIGlmIChkZXJpdiA9PSAxKSB7CiAgICAgICAgQyA9IGggKiBtYXRlcm4uY292YXJpYW5jZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IG51IC0gMSwgc2lnbWEgPSBzaWdtYSkKICAgICAgICBDW2ggPT0gMF0gPSAwCiAgICAgICAgcmV0dXJuKC0oa2FwcGFeMi8oMiAqIChudSAtIDEpKSkgKiBDKQogICAgfQogICAgZWxzZSBpZiAoZGVyaXYgPT0gMikgewogICAgICAgIEMgPSBtYXRlcm4uY292YXJpYW5jZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IG51IC0gMSwgc2lnbWEgPSBzaWdtYSkgKyAKICAgICAgICAgICAgaCAqIG1hdGVybi5kZXJpdmF0aXZlKGgsIGthcHBhID0ga2FwcGEsIG51ID0gbnUgLSAxLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNpZ21hID0gc2lnbWEsIGRlcml2ID0gMSkKICAgICAgICByZXR1cm4oLShrYXBwYV4yLygyICogKG51IC0gMSkpKSAqIEMpCiAgICB9CiAgICBlbHNlIHsKICAgICAgICBDID0gKGRlcml2IC0gMSkgKiBtYXRlcm4uZGVyaXZhdGl2ZShoLCBrYXBwYSA9IGthcHBhLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBudSA9IG51IC0gMSwgc2lnbWEgPSBzaWdtYSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZGVyaXYgPSBkZXJpdiAtIDIpICsgCiAgICAgICAgICAgIGggKiBtYXRlcm4uZGVyaXZhdGl2ZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IG51IC0gCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMSwgc2lnbWEgPSBzaWdtYSwgZGVyaXYgPSBkZXJpdiAtIDEpCiAgICAgICAgcmV0dXJuKC0oa2FwcGFeMi8oMiAqIChudSAtIDEpKSkgKiBDKQogICAgfQogICAgCn0KYGBgCgpGcm9tIFtAQm9saW4yMDI1bGluZWFyY29zdGV4cG9uZW50aWFsbHljb252ZXJnZW50LCBQcm9wb3NpdGlvbiAxXSwgd2UgaGF2ZSB0aGUgZm9sbG93aW5nIGRlY29tcG9zaXRpb24KCiQkClx2YXJyaG9fbV5cYWxwaGEoaCk9XHZhcnJob197bSwgMH1eXGFscGhhKGgpK1xzdW1fe2k9MX1ebSBcdmFycmhvX3ttLCBpfV5cYWxwaGEoaCkKXHRhZ3szfQpcbGFiZWx7bWF0ZXJuX3BfZGVjb21wb3NpdGlvbn0KJCQKCndoZXJlCgokJApcdmFycmhvX3ttLCAwfV5cYWxwaGEoaCk9ayBcc2lnbWFeMiBcY2RvdCBcYmVnaW57Y2FzZXN9XGRmcmFje2NfXGFscGhhIFxzcXJ0ezQgXHBpfX17XGthcHBhfSAxX3tbaD0wXX0sICYgMDxcYWxwaGE8MSBcXCBcdmFycmhvXGxlZnQoaCA7XGthcHBhLFxsZmxvb3JcYWxwaGFccmZsb29yLVxmcmFjezF9ezJ9LCBcc3FydHsgXGZyYWN7Y19cYWxwaGF9e2Nfe1xsZmxvb3JcYWxwaGFccmZsb29yfX19XHJpZ2h0KSwgJiBcYWxwaGEgXGdlcSAxXGVuZHtjYXNlc30KXHRhZ3s0fQpcbGFiZWx7bWF0ZXJuXzBfY292YXJpYW5jZX0KJCQKCmFuZAoKJCQKXHZhcnJob197bSwgaX1eXGFscGhhKGgpPXJfaSBcc2lnbWFeMiBcY2RvdCBcYmVnaW57Y2FzZXN9XHZhcnJob1xsZWZ0KGggO1xrYXBwYV9pLCBcZnJhY3sxfXsyfSwgXHNxcnR7IFxmcmFje2NfXGFscGhhIFxzcXJ0e1xwaX19e1xzcXJ0ezEtcF9pfX19XHJpZ2h0KSwgJiAwPFxhbHBoYTwxIFxcIFxmcmFjezF9e3BfaV57XGxmbG9vclxhbHBoYVxyZmxvb3J9fSBcdmFycmhvXGxlZnQoaCA7IFxrYXBwYV9pLCBcZnJhY3sxfXsyfSwgIFxzcXJ0e1xmcmFje2NfXGFscGhhIFxzcXJ0e1xwaX19e1xzcXJ0ezEtcF9pfX19XHJpZ2h0KS1cc3VtX3tqPTF9XntcbGZsb29yXGFscGhhXHJmbG9vcn0gXGZyYWN7MX17cF9pXntcbGZsb29yXGFscGhhXHJmbG9vcisxLWp9fSBcdmFycmhvXGxlZnQoaCA7IFxrYXBwYSwgai1cZnJhY3sxfXsyfSwgIFxzcXJ0e1xmcmFje2NfXGFscGhhfXtjX2p9fVxyaWdodCksICYgXGFscGhhIFxnZXEgMVxlbmR7Y2FzZXN9Clx0YWd7NX0KXGxhYmVse21hdGVybl9wX2NvdmFyaWFuY2V9CiQkCgphbmQgJGNfYTo9XEdhbW1hKGEpIC8gXEdhbW1hKGEtMSAvIDIpLCBca2FwcGFfaT1ca2FwcGEgXHNxcnR7MS1wX2l9JCwgYW5kICRcdmFycmhvJCBpcyB0aGUgTWF0w6lybiBjb3ZhcmlhbmNlIFxlcXJlZnttYXRlcm5jb3ZhcmlhbmNlfS4KCkZ1bmN0aW9uIGBtYXRlcm4ucCgpYCBpbXBsZW1lbnRzIAoKJCQKXGRmcmFje1x2YXJyaG9fe20sIGl9XlxhbHBoYShoKX17cl9pXHNpZ21hXjJ9CiQkCmFzIGdpdmVuIGJlbG93LiBGdW5jdGlvbiBgbWF0ZXJuLnAuZGVyaXYoKWAgaW1wbGVtZW50cyB0aGUgZGVyaXZhdGl2ZXMgb2YgdGhpcyBmdW5jdGlvbi4KCkhlcmUgYXJlIHRoZSBkZXRhaWxzIG9mIHdoYXQgYG1hdGVybi5wKClgIGRvZXMuIAoKLSBJZiBgcD09MGAsIHRoZW4gYG1hdGVybi5wKClgIHJldHVybnMgJFx2YXJyaG8oaCA9IHMtdDsgXGthcHBhID0gXGthcHBhLCBcbnUgPSBcYWxwaGEtMS8yLCBcc2lnbWEgPSAxKSA9XGRmcmFjezF9ezJee1xudS0xfSBcR2FtbWEoXG51KX0oXGthcHBhfGh8KV5cbnUgS19cbnUoXGthcHBhfGh8KSQuIFNvIGlmIHlvdSB3YW50IHRoZSBmdWxsIG1hdGVybiwganVzdCBtdWx0aXBseSBieSAkXHNpZ21hXjIkLiBUaGF0IGlzLCAkXHNpZ21hXjIqJGBtYXRlcm4ucChzLHQsa2FwcGEscCA9IDAsIGFscGhhKSA9IGAkXHZhcnJobyhoID0gcy10OyBca2FwcGEgPSBca2FwcGEsIFxudSA9IFxhbHBoYS0xLzIsIFxzaWdtYSA9IFxzaWdtYSkkLgoKLSBJZiBgcCE9MGAsIHRoZW4KICAKICAgIC0gSWYgJDA8XGFscGhhPDEkLCB0aGVuIGBtYXRlcm4ucCgpYCByZXR1cm5zICRcdmFycmhvKGggPSBzLXQ7IFxrYXBwYSA9IFxrYXBwYVxzcXJ0ezEtcF9pfSwgXG51ID0gMS8yLCBcc2lnbWEgPSBcc3FydHtcZnJhY3tjX1xhbHBoYSBcc3FydHtccGl9fXtcc3FydHsxLXBfaX19fSkgPSBcZnJhY3tjX1xhbHBoYSBcc3FydHtccGl9fXtcc3FydHsxLXBfaX19IFxjZG90IFx2YXJyaG8oaCA9IHMtdDsgXGthcHBhID0gXGthcHBhXHNxcnR7MS1wX2l9LCBcbnUgPSAxLzIsIFxzaWdtYT0xKSQKClRoZSBib3R0b20gbGluZSAgaXMKCiAtICRcdmFycmhvX3ttLCBpfV5cYWxwaGEoaCkkID0gJHJfaVxzaWdtYV4yJGBtYXRlcm4ucChzLHQsa2FwcGEscCA9IHAsIGFscGhhKWAuCiAKICAtICRcZGZyYWN7ZF5rfXtkaF5rfVx2YXJyaG9fe20sIGl9XlxhbHBoYShoKSQgPSAkcl9pXHNpZ21hXjIkYG1hdGVybi5wLmRlcml2KHMsdCxrYXBwYSxwID0gcCwgYWxwaGEsIGRlcml2ID0gaylgLgogCiAKIC0gJFxtYXRoYmZ7cn1faVxsZWZ0KHRfMSwgdF8yXHJpZ2h0KT1yX2lcc2lnbWFeMiRgbWF0ZXJuLnAuam9pbnQocyx0LGthcHBhLHAsYWxwaGEpYC4KCi0gSWYgYHA9PTBgLCB0aGVuIHdlIGFyZSBpbiB0aGUgJFxhbHBoYVxpblxtYXRoYmJ7Tn0kIGNhc2Ugc28gdGhhdCAkXGxmbG9vclxhbHBoYVxyZmxvb3I9XGFscGhhJCBhbmQgaGVuY2UgJGNfXGFscGhhL2Nfe1xsZmxvb3JcYWxwaGFccmZsb29yfSA9IDEkIGFuZCBoZW5jZQokXHZhcnJob197bSwgMH1eXGFscGhhKGgpPWsgXHNpZ21hXjJcdmFycmhvKGg7XGthcHBhLCBcYWxwaGEtMS8yLDEpPWsgXHNpZ21hXjIkYG1hdGVybi5wKHMsdCxrYXBwYSxwPTAsYWxwaGEpYAoKCmBgYHtyfQptYXRlcm4ucCA8LSBmdW5jdGlvbihzLHQsa2FwcGEscCxhbHBoYSl7CiAgICBoIDwtIHMtdAogICAgaWYocD09MCl7CiAgICAgICAgcmV0dXJuKG1hdGVybi5jb3ZhcmlhbmNlKGgsIGthcHBhID0ga2FwcGEsIG51ID0gYWxwaGEgLSAxLzIsIHNpZ21hID0gMSkpCiAgICB9IGVsc2UgewogICAgICAgIGNhIDwtIGdhbW1hKGFscGhhKS9nYW1tYShhbHBoYS0wLjUpCiAgICAgICAgZmEgPC0gZmxvb3IoYWxwaGEpCiAgICAgICAga3AgPC0ga2FwcGEqc3FydCgxLXApCiAgICAgICAgb3V0IDwtIG1hdGVybi5jb3ZhcmlhbmNlKGgsIGthcHBhID0ga3AsIG51ID0gMS8yLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc2lnbWEgPSBzcXJ0KGNhKnNxcnQocGkpL3NxcnQoMS1wKSkpCiAgICAgICAgaWYoYWxwaGEgPCAxKSB7CiAgICAgICAgICAgIHJldHVybihvdXQpCiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgCiAgICAgICAgICAgIGZvcihqIGluIDE6ZmEpIHsKICAgICAgICAgICAgICAgIG91dCA8LSBvdXQgLSBtYXRlcm4uY292YXJpYW5jZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IGotMS8yLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaWdtYSA9IHNxcnQoY2EqZ2FtbWEoai0wLjUpL2dhbW1hKGopKSkvcF4oMSAtIGopCiAgICAgICAgICAgIH0KICAgICAgICAgICAgb3V0IDwtIG91dC9wXmZhCiAgICAgICAgICAgIHJldHVybihvdXQpICAgIAogICAgICAgIH0KICAgIH0KfQoKbWF0ZXJuLnAuZGVyaXYgPC0gZnVuY3Rpb24ocyx0LGthcHBhLHAsYWxwaGEsZGVyaXYgPSAwKXsKICAgIGggPC0gcy10CiAgICBpZihkZXJpdiA9PTApewogICAgICAgIHJldHVybihtYXRlcm4ucChzLHQsa2FwcGEscCxhbHBoYSkpCiAgICB9IGVsc2UgewogICAgICAgIGlmKHA9PTApewogICAgICAgICAgICByZXR1cm4obWF0ZXJuLmRlcml2YXRpdmUoaCwga2FwcGEgPSBrYXBwYSwgbnUgPSBhbHBoYSAtIDEvMiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaWdtYSA9IDEsIGRlcml2ID0gZGVyaXYpKQogICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgIGNhIDwtIGdhbW1hKGFscGhhKS9nYW1tYShhbHBoYS0wLjUpCiAgICAgICAgICAgIGZhIDwtIGZsb29yKGFscGhhKQogICAgICAgICAgICBrcCA8LSBrYXBwYSpzcXJ0KDEtcCkKICAgICAgICAgICAgb3V0IDwtIG1hdGVybi5kZXJpdmF0aXZlKGgsIGthcHBhID0ga3AsIG51ID0gIDEvMiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaWdtYSA9IHNxcnQoY2Eqc3FydChwaSkvc3FydCgxLXApKSwgZGVyaXYgPSBkZXJpdikKICAgICAgICAgICAgaWYoYWxwaGEgPCAxKSB7CiAgICAgICAgICAgICAgICByZXR1cm4ob3V0KQogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgb3V0IDwtIG91dC9wXmZhCiAgICAgICAgICAgICAgICBmb3IoaiBpbiAxOmZhKSB7CiAgICAgICAgICAgICAgICAgICAgb3V0IDwtIG91dCAtIG1hdGVybi5kZXJpdmF0aXZlKGgsIGthcHBhID0ga2FwcGEsIG51ID0gai0xLzIsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaWdtYSA9IHNxcnQoY2EqZ2FtbWEoai0wLjUpL2dhbW1hKGopKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRlcml2ID0gZGVyaXYpL3BeKGZhICsgMSAtIGopCiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuKG91dCkKICAgICAgICB9ICAgIAogICAgfQogICAgCn0KYGBgCgoKRnVuY3Rpb24gYG1hdGVybi5wLmpvaW50KClgIGNvbXB1dGVzIHRoZSBqb2ludCBjb3ZhcmlhbmNlIG1hdHJpeCBvZiB0aGUgcHJvY2VzcyBhbmQgaXRzIGRlcml2YXRpdmVzIHVwIHRvIG9yZGVyIGBmbG9vcihhbHBoYSlgIGZvciB0aGUgc2hpZnRlZCBNYXTDqXJuIGNvdmFyaWFuY2UuIFRoYXQgaXMsIGl0IGNvbXB1dGVzIAoKJCQKXG1hdGhiZntyfV9pOiBcbWF0aGJie1J9IFx0aW1lcyBcbWF0aGJie1J9IFxtYXBzdG8gXG1hdGhiYntSfV57XGxjZWlsXGFscGhhXHJjZWlsXHRpbWVzIFxsY2VpbFxhbHBoYVxyY2VpbH0sIFxxdWFkIFxtYXRoYmZ7cn1faVxsZWZ0KHRfMSwgdF8yXHJpZ2h0KT1cbGVmdFtcZnJhY3tccGFydGlhbF57aS0xfX17XHBhcnRpYWwgdF8yXntpLTF9fSBcZnJhY3tccGFydGlhbF57ai0xfX17XHBhcnRpYWwgdF8xXntqLTF9fSBcZGZyYWN7XHZhcnJob197bSwgaX1eXGFscGhhXGxlZnQodF8xLXRfMlxyaWdodCl9e3JfaVxzaWdtYV4yfVxyaWdodF1fe2kgaiBcaW5cezEsMiwgXGxkb3RzLCBcbGNlaWxcYWxwaGFccmNlaWxcfX0KXHRhZ3syfQpcbGFiZWx7cl9tYXRyaXh9CiQkCndoaWNoIGlzIHRoZSBtdWx0aXZhcmlhdGUgY292YXJpYW5jZSBmdW5jdGlvbiBvZiAkKHVfaSh0KSwgdV9pJyh0KSwgXGxkb3RzLCB1X2leeyhcbGZsb29yXGFscGhhXHJmbG9vcil9KHQpKSQgYW5kICR1X2kkIGlzIGEgc2hpZnRlZCBXaGl0dGxl4oCTTWF0w6lybiBicmlkZ2UgcHJvY2VzcyB3aXRoIGNvdmFyaWFuY2UgZnVuY3Rpb24gJFx2YXJyaG9fe20sIGl9XlxhbHBoYShoKS8ocl9pXHNpZ21hXjIpJC4KCmBgYHtyfQojSm9pbnQgY292YXJpYW5jZSBvZiBwcm9jZXNzIGFuZCBkZXJpdmF0aXZlIGZvciBzaGlmdGVkIE1hdGVybgptYXRlcm4ucC5qb2ludCA8LSBmdW5jdGlvbihzLHQsa2FwcGEscCwgYWxwaGEgPSAxKXsKICAgIAogICAgaWYoYWxwaGElJTEgPT0gMCkgewogICAgICAgIGZhIDwtIGFscGhhCiAgICB9IGVsc2UgewogICAgICAgIGZhIDwtIGZsb29yKGFscGhhKSArIDEgICAgCiAgICB9CiAgICBtYXQgPC0gbWF0cml4KDAsIG5yb3cgPSBmYSwgbmNvbCA9IGZhKQogICAgZm9yKGkgaW4gMTpmYSkgewogICAgICAgIGZvcihqIGluIGk6ZmEpIHsKICAgICAgICAgICAgaWYoaT09aikgewogICAgICAgICAgICAgICAgbWF0W2ksaV0gPC0gKCgtMSleKGktMSkpKm1hdGVybi5wLmRlcml2KHMsdCxrYXBwYSxwLGFscGhhLCBkZXJpdiA9IDIqKGktMSkpCiAgICAgICAgICAgIH0gZWxzZSB7CiAgICAgICAgICAgICAgICB0bXAgPC0gbWF0ZXJuLnAuZGVyaXYocyx0LGthcHBhLHAsYWxwaGEsIGRlcml2ID0gaS0xICsgaiAtIDEpCiAgICAgICAgICAgICAgICBtYXRbaSxqXSA8LSAoLTEpXihqLTEpKnRtcAogICAgICAgICAgICAgICAgbWF0W2osaV0gPC0gKC0xKV4oaS0xKSp0bXAKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KICAgIAogICAgcmV0dXJuKG1hdCkKfQpgYGAKCgpgYGAKe3J9Cm1hdDEgPC0gbWF0ZXJuLnAuam9pbnQocyA9IDAuNiwgdCA9IDAuNSwga2FwcGEgPSAxMCwgcCA9IDAuMywgYWxwaGEgPSAyKQptYXQyIDwtIG1hdGVybi5wLmpvaW50KHMgPSAwLjYsIHQgPSAwLjUsIGthcHBhID0gMTAsIHAgPSAwLjMsIGFscGhhID0gMykKbWF0MQptYXQyCmBgYAoKCmBgYHtyfQpleHBfcHJlY2lzaW9uIDwtIGZ1bmN0aW9uKGxvYywga2FwcGEsIGJvdW5kYXJ5ID0gImZyZWUiKSB7CiAgICBuIDwtIGxlbmd0aChsb2MpCiAgICBsIDwtIGRpZmYobG9jKQogICAgCiAgICAjIFByZWNvbXB1dGUgcmV1c2FibGUgdGVybXMKICAgIGEgPC0gZXhwKC0yICoga2FwcGEgKiBsKQogICAgYiA8LSAxIC0gYQogICAgCiAgICAjIEluaXRpYWxpemUgbWF0cml4IFEgZWZmaWNpZW50bHkKICAgIFEgPC0gTWF0cml4KDAsIG5yb3cgPSBuLCBuY29sID0gbikKICAgIAogICAgIyBTZXQgZGlhZ29uYWwgZWxlbWVudHMKICAgIGRpYWcoUSlbMToobi0xKV0gPC0gMS8yICsgYS9iCiAgICBkaWFnKFEpWzI6bl0gPC0gZGlhZyhRKVsyOm5dICsgMS8yICsgYS9iCiAgICAKICAgICMgU2V0IG9mZi1kaWFnb25hbCBlbGVtZW50cwogICAgIyAgaW5kaWNlcyA8LSBjKHdoaWNoKHJvdyhRKSA9PSBjb2woUSkgKyAxKSwgd2hpY2gocm93KFEpID09IGNvbChRKSAtIDEpKQogICAgIyBvZmZfZGlhZ192YWx1ZXMgPC0gLWV4cCgta2FwcGEgKiBsKSAvYgogICAgIyBRW2luZGljZXNdIDwtIG9mZl9kaWFnX3ZhbHVlcwogICAgCiAgICAKICAgIHJvd19pbmRpY2VzIDwtIHNlcV9sZW4obiAtIDEpCiAgICBjb2xfaW5kaWNlcyA8LSByb3dfaW5kaWNlcyArIDEgICMgT2Zmc2V0cyBmb3Igb2ZmLWRpYWdvbmFsIGVsZW1lbnRzCiAgICAKICAgICMgQ29tcHV0ZSB0aGUgb2ZmLWRpYWdvbmFsIHZhbHVlcwogICAgb2ZmX2RpYWdfdmFsdWVzIDwtIC1leHAoLWthcHBhICogbCkvYgogICAgCiAgICAjIFNldCB0aGUgb2ZmLWRpYWdvbmFsIGVsZW1lbnRzIGluIG1hdHJpeCBRCiAgICBRW2NiaW5kKHJvd19pbmRpY2VzLCBjb2xfaW5kaWNlcyldIDwtIG9mZl9kaWFnX3ZhbHVlcwogICAgUVtjYmluZChjb2xfaW5kaWNlcywgcm93X2luZGljZXMpXSA8LSBvZmZfZGlhZ192YWx1ZXMKICAgIAogICAgIyBBZGp1c3QgYm91bmRhcnkgY29uZGl0aW9ucyBpZiByZXF1aXJlZAogICAgaWYgKGJvdW5kYXJ5ID09ICJmcmVlIikgewogICAgICAgIFFbMSwgMV0gPC0gUVsxLCAxXSArIDAuNQogICAgICAgIFFbbiwgbl0gPC0gUVtuLCBuXSArIDAuNQogICAgfQogICAgCiAgICByZXR1cm4oMiAqIGthcHBhICogUVtdKQp9CmBgYAoKCmBgYAp7cn0KIyBFeGFtcGxlIHVzYWdlIG9mIGV4cF9wcmVjaXNpb24gZnVuY3Rpb24KbG9jIDwtIHNlcSgwLCAxLCBsZW5ndGgub3V0ID0gMTApCmthcHBhIDwtIDUKUV9tYXRyaXggPC0gZXhwX3ByZWNpc2lvbihsb2MsIGthcHBhLCBib3VuZGFyeSA9ICJmcmVlIikKcHJpbnQoUV9tYXRyaXgpCmBgYAoKCmBgYHtyfQptYXRlcm4ucC5wcmVjaXNpb24gPC0gZnVuY3Rpb24obG9jLGthcHBhLHAsZXF1YWxseV9zcGFjZWQgPSBGQUxTRSwgYWxwaGEgPSAxKSB7CiAgICAKICAgIG4gPC0gbGVuZ3RoKGxvYykKICAgIGlmKGFscGhhPT0xKSB7CiAgICAgICAgUSA8LSBleHBfcHJlY2lzaW9uKGxvYyxrYXBwYSkvKDIqa2FwcGEpCiAgICAgICAgQSA8LSBEaWFnb25hbChuKQogICAgICAgIAogICAgICAgIHJldHVybihsaXN0KFE9USxBPUEpKQogICAgfSBlbHNlIHsKICAgICAgICBpZihhbHBoYSUlMSA9PSAwKSB7CiAgICAgICAgICAgIGZhIDwtIGFscGhhCiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgZmEgPC0gZmxvb3IoYWxwaGEpICsgMSAgICAKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgaWYoZmEgPT0gMSkgewogICAgICAgICAgICBOIDwtIG4gICsgbiAtIDEgCiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgTiA8LSBuKmZhXjIgKyAobi0xKSpmYV4yIC0gbipmYSooZmEgLTEpLzIgICAgCiAgICAgICAgfQogICAgICAgIAogICAgICAgIGlpIDwtIG51bWVyaWMoTikKICAgICAgICBqaiA8LSBudW1lcmljKE4pCiAgICAgICAgdmFsIDwtIG51bWVyaWMoTikKICAgICAgICAKICAgICAgICBpZihlcXVhbGx5X3NwYWNlZCl7CiAgICAgICAgICAgIFEuMSA8LSBzb2x2ZShyYmluZChjYmluZChtYXRlcm4ucC5qb2ludChsb2NbMV0sbG9jWzFdLGthcHBhLHAsYWxwaGEpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1hdGVybi5wLmpvaW50KGxvY1sxXSxsb2NbMSsxXSxrYXBwYSxwLGFscGhhKSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjYmluZChtYXRlcm4ucC5qb2ludChsb2NbMSsxXSxsb2NbMV0sa2FwcGEscCxhbHBoYSksIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF0ZXJuLnAuam9pbnQobG9jWzErMV0sbG9jWzErMV0sa2FwcGEscCxhbHBoYSkpKSkKICAgICAgICAgICAgCiAgICAgICAgICAgIFEuaSA8LSBzb2x2ZShyYmluZChjYmluZChtYXRlcm4ucC5qb2ludChsb2NbMV0sbG9jWzFdLGthcHBhLHAsYWxwaGEpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1hdGVybi5wLmpvaW50KGxvY1sxXSxsb2NbMl0sa2FwcGEscCxhbHBoYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbMV0sbG9jWzNdLGthcHBhLHAsYWxwaGEpKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNiaW5kKG1hdGVybi5wLmpvaW50KGxvY1syXSxsb2NbMV0sa2FwcGEscCxhbHBoYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbMl0sbG9jWzJdLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF0ZXJuLnAuam9pbnQobG9jWzJdLGxvY1szXSxrYXBwYSxwLGFscGhhKSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjYmluZChtYXRlcm4ucC5qb2ludChsb2NbM10sbG9jWzFdLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF0ZXJuLnAuam9pbnQobG9jWzNdLGxvY1syXSxrYXBwYSxwLGFscGhhKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1hdGVybi5wLmpvaW50KGxvY1szXSxsb2NbM10sa2FwcGEscCxhbHBoYSkpKSlbLWMoMTpmYSksLWMoMTpmYSldCiAgICAgICAgfQogICAgICAgIAogICAgICAgIAogICAgICAgIGZvcihpIGluIDE6bWF4KChuLTEpLDEpKXsKICAgICAgICAgICAgaWYoaT09MSl7CiAgICAgICAgICAgICAgICBpZighZXF1YWxseV9zcGFjZWQpewogICAgICAgICAgICAgICAgICAgIFEuMSA8LSBzb2x2ZShyYmluZChjYmluZChtYXRlcm4ucC5qb2ludChsb2NbaV0sbG9jW2ldLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbaV0sbG9jW2krMV0sa2FwcGEscCxhbHBoYSkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjYmluZChtYXRlcm4ucC5qb2ludChsb2NbaSsxXSxsb2NbaV0sa2FwcGEscCxhbHBoYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1hdGVybi5wLmpvaW50KGxvY1tpKzFdLGxvY1tpKzFdLGthcHBhLHAsYWxwaGEpKSkpCiAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICB9IAogICAgICAgICAgICAgICAgY291bnRlciA8LSAxCiAgICAgICAgICAgICAgICBmb3Ioa2kgaW4gMTpmYSkgewogICAgICAgICAgICAgICAgICAgIGZvcihraiBpbiBraTooMipmYSkpIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWlbY291bnRlcl0gPC0ga2kKICAgICAgICAgICAgICAgICAgICAgICAgampbY291bnRlcl0gPC0ga2oKICAgICAgICAgICAgICAgICAgICAgICAgdmFsW2NvdW50ZXJdIDwtIFEuMVtraSxral0KICAgICAgICAgICAgICAgICAgICAgICAgY291bnRlciA8LSBjb3VudGVyICsgMQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgICAgIGlmKCFlcXVhbGx5X3NwYWNlZCl7CiAgICAgICAgICAgICAgICAgICAgUS5pIDwtIHNvbHZlKHJiaW5kKGNiaW5kKG1hdGVybi5wLmpvaW50KGxvY1tpLTFdLGxvY1tpLTFdLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbaS0xXSxsb2NbaV0sa2FwcGEscCxhbHBoYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1hdGVybi5wLmpvaW50KGxvY1tpLTFdLGxvY1tpKzFdLGthcHBhLHAsYWxwaGEpKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY2JpbmQobWF0ZXJuLnAuam9pbnQobG9jW2ldLGxvY1tpLTFdLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbaV0sbG9jW2ldLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbaV0sbG9jW2krMV0sa2FwcGEscCxhbHBoYSkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjYmluZChtYXRlcm4ucC5qb2ludChsb2NbaSsxXSxsb2NbaS0xXSxrYXBwYSxwLGFscGhhKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF0ZXJuLnAuam9pbnQobG9jW2krMV0sbG9jW2ldLGthcHBhLHAsYWxwaGEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRlcm4ucC5qb2ludChsb2NbaSsxXSxsb2NbaSsxXSxrYXBwYSxwLGFscGhhKSkpKVstYygxOmZhKSwtYygxOmZhKV0KICAgICAgICAgICAgICAgIH0gCiAgICAgICAgICAgICAgICAjIFFbKDIqbi0xKTooMipuKSwgKDIqbi0zKTooMipuKV0gPSBRLmlbMzo0LF0KICAgICAgICAgICAgICAgIGZvcihraSBpbiAxOmZhKXsKICAgICAgICAgICAgICAgICAgICBmb3Ioa2ogaW4ga2k6KDIqZmEpKXsKICAgICAgICAgICAgICAgICAgICAgICAgaWlbY291bnRlcl0gPC0gZmEqKGktMSkgKyBraQogICAgICAgICAgICAgICAgICAgICAgICBqaltjb3VudGVyXSA8LSBmYSooaS0xKSArIGtqCiAgICAgICAgICAgICAgICAgICAgICAgIHZhbFtjb3VudGVyXSA8LVEuaVtraSxral0KICAgICAgICAgICAgICAgICAgICAgICAgY291bnRlciA8LSBjb3VudGVyICsgMQogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0gICAgIAogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGlmKG48PTIpewogICAgICAgICAgICBRLmkgPC0gUS4xCiAgICAgICAgfQogICAgICAgIGZvcihraSBpbiAxOmZhKXsKICAgICAgICAgICAgZm9yKGtqIGluIGtpOmZhKXsKICAgICAgICAgICAgICAgIGlpW2NvdW50ZXJdIDwtIGZhKihuLTEpICsga2kKICAgICAgICAgICAgICAgIGpqW2NvdW50ZXJdIDwtIGZhKihuLTEpICsga2oKICAgICAgICAgICAgICAgIHZhbFtjb3VudGVyXSA8LVEuaVtraStmYSxraitmYV0KICAgICAgICAgICAgICAgIGNvdW50ZXIgPC0gY291bnRlciArIDEKICAgICAgICAgICAgfQogICAgICAgIH0gICAgCiAgICAgICAgUSA8LSBNYXRyaXg6OnNwYXJzZU1hdHJpeChpICAgPSBpaSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGogICAgPSBqaiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHggICAgPSB2YWwsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaW1zID0gYyhmYSpuLCBmYSpuKSwgc3ltbWV0cmljPVRSVUUpCiAgICAgICAgCiAgICAgICAgQSA8LSAgTWF0cml4OjpzcGFyc2VNYXRyaXgoaSAgID0gMTpuLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGogICAgPSBzZXEoZnJvbT0xLHRvPW4qZmEsYnk9ZmEpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHggICAgPSByZXAoMSxuKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBkaW1zID0gYyhuLCBmYSpuKSkKICAgICAgICByZXR1cm4obGlzdChRPVEsQT1BKSkgICAgCiAgICB9Cn0KYGBgCgoKYGBgCntyfQphdXggPC0gIG1hdGVybi5wLnByZWNpc2lvbihsb2MgPSBjKDAsMSwyKSwga2FwcGEgPSAxMCwgcCA9IDAuMywgZXF1YWxseV9zcGFjZWQgPSBUUlVFLCBhbHBoYSA9IDIuMikKYXV4JFEKYXV4JEEKYGBgCgoKYGBgCntyfQojIC0tLS0tLS0tLS0tLSBEQVRBIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0Ka2FwcGEgPC0gMjUKbnUgPC0gMy8yCmFscGhhIDwtIG51ICsgMS8yCnNpZ21hIDwtIDEKcCA8LSAwLjMKeCA8LSBzZXEoMCwgMSwgbGVuZ3RoLm91dCA9IDEwMDEpCmggPC0gYWJzKHggLSAwLjUpCgp5MSA8LSBtYXRlcm4uY292YXJpYW5jZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IG51LCBzaWdtYSA9IHNpZ21hKQp5MiA8LSBtYXRlcm4uZGVyaXZhdGl2ZShoLCBrYXBwYSA9IGthcHBhLCBudSA9IG51LCBzaWdtYSA9IHNpZ21hLCBkZXJpdiA9IDEpCnkzIDwtIG1hdGVybi5kZXJpdmF0aXZlKGgsIGthcHBhID0ga2FwcGEsIG51ID0gbnUsIHNpZ21hID0gc2lnbWEsIGRlcml2ID0gMikKCnk0IDwtIG1hdGVybi5wKHMgPSB4LCB0ID0gMC41LCBrYXBwYSA9IGthcHBhLCBwID0gMCwgYWxwaGEgPSBhbHBoYSkKeTUgPC0gbWF0ZXJuLnAocyA9IHgsIHQgPSAwLjUsIGthcHBhID0ga2FwcGEsIHAgPSBwLCBhbHBoYSA9IGFscGhhKQp5NiA8LSBzYXBwbHkoeCwgZnVuY3Rpb24oc2kpIG1hdGVybi5wLmpvaW50KHMgPSBzaSwgdCA9IDAuNSwga2FwcGEgPSBrYXBwYSwgcCA9IHAsIGFscGhhID0gYWxwaGEpWzEsMV0pCnk3IDwtIG1hdGVybi5wLmRlcml2KHMgPSB4LCB0ID0gMC41LCBrYXBwYSA9IGthcHBhLCBwID0gcCwgYWxwaGEgPSBhbHBoYSwgZGVyaXYgPSAxKQp5OCA8LSBzYXBwbHkoeCwgZnVuY3Rpb24oc2kpIG1hdGVybi5wLmpvaW50KHMgPSBzaSwgdCA9IDAuNSwga2FwcGEgPSBrYXBwYSwgcCA9IHAsIGFscGhhID0gYWxwaGEpWzIsMl0pCiMgLS0tLS0tLS0tLS0tIFNDQUxJTkcgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKczEgPC0gbWF4KGFicyh5MSkpCnMyIDwtIG1heChhYnMoeTIpKQpzMyA8LSBtYXgoYWJzKHkzKSkKczQgPC0gbWF4KGFicyh5NCkpCnM1IDwtIG1heChhYnMoeTUpKQpzNiA8LSBtYXgoYWJzKHk2KSkKczcgPC0gbWF4KGFicyh5NykpCnM4IDwtIG1heChhYnMoeTgpKQoKejEgPC0geTEgLyBzMQp6MiA8LSB5MiAvIHMyCnozIDwtIHkzIC8gczMKejQgPC0geTQgLyBzNAp6NSA8LSB5NSAvIHM1Cno2IDwtIHk2IC8gczYKejcgPC0geTcgLyBzNwp6OCA8LSB5OCAvIHM4CgojIC0tLS0tLS0tLS0tLSBQTE9UIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCnBsb3RfbHkoKSAlPiUKICBhZGRfdHJhY2UoCiAgICB4ID0gfngsIHkgPSB+MCwgeiA9IH56MSwKICAgIHR5cGUgPSAic2NhdHRlcjNkIiwgbW9kZSA9ICJsaW5lcyIsCiAgICBuYW1lID0gcGFzdGUwKCJNYXTDqXJuICgxLyIsIHJvdW5kKHMxLCAzKSwgIikiKQogICkgJT4lCiAgYWRkX3RyYWNlKAogICAgeCA9IH54LCB5ID0gfjEsIHogPSB+ejIsCiAgICB0eXBlID0gInNjYXR0ZXIzZCIsIG1vZGUgPSAibGluZXMiLAogICAgbmFtZSA9IHBhc3RlMCgiTWF0w6lybicgKDEvIiwgcm91bmQoczIsIDMpLCAiKSIpCiAgKSAlPiUKICBhZGRfdHJhY2UoCiAgICB4ID0gfngsIHkgPSB+MiwgeiA9IH56MywKICAgIHR5cGUgPSAic2NhdHRlcjNkIiwgbW9kZSA9ICJsaW5lcyIsCiAgICBuYW1lID0gcGFzdGUwKCJNYXTDqXJuJycgKDEvIiwgcm91bmQoczMsIDMpLCAiKSIpCiAgKSAlPiUKICBhZGRfdHJhY2UoCiAgICB4ID0gfngsIHkgPSB+MywgeiA9IH56NCwKICAgIHR5cGUgPSAic2NhdHRlcjNkIiwgbW9kZSA9ICJsaW5lcyIsCiAgICBuYW1lID0gcGFzdGUwKCJtYXRlcm4uMCAoMS8iLCByb3VuZChzNCwgMyksICIpIikKICApICU+JQogIGFkZF90cmFjZSgKICAgIHggPSB+eCwgeSA9IH40LCB6ID0gfno1LAogICAgdHlwZSA9ICJzY2F0dGVyM2QiLCBtb2RlID0gImxpbmVzIiwKICAgIG5hbWUgPSBwYXN0ZTAoIm1hdGVybi5wICgxLyIsIHJvdW5kKHM1LCAzKSwgIikiKQogICkgJT4lCiAgYWRkX3RyYWNlKAogICAgeCA9IH54LCB5ID0gfjUsIHogPSB+ejYsCiAgICB0eXBlID0gInNjYXR0ZXIzZCIsIG1vZGUgPSAibGluZXMiLAogICAgbmFtZSA9IHBhc3RlMCgibWF0ZXJuLnAgam9pbnQgKDEvIiwgcm91bmQoczYsIDMpLCAiKSIpCiAgKSAlPiUKICBhZGRfdHJhY2UoCiAgICB4ID0gfngsIHkgPSB+NiwgeiA9IH56NywKICAgIHR5cGUgPSAic2NhdHRlcjNkIiwgbW9kZSA9ICJsaW5lcyIsCiAgICBuYW1lID0gcGFzdGUwKCJtYXRlcm4ucCcgKDEvIiwgcm91bmQoczcsIDMpLCAiKSIpCiAgKSAlPiUKICBhZGRfdHJhY2UoCiAgICB4ID0gfngsIHkgPSB+NywgeiA9IH56OCwKICAgIHR5cGUgPSAic2NhdHRlcjNkIiwgbW9kZSA9ICJsaW5lcyIsCiAgICBuYW1lID0gcGFzdGUwKCJtYXRlcm4ucCBqb2ludCcgKDEvIiwgcm91bmQoczgsIDMpLCAiKSIpCiAgKSAlPiUKICBsYXlvdXQoCiAgICBzY2VuZSA9IGxpc3QoCiAgICAgIHhheGlzID0gbGlzdCh0aXRsZSA9ICJ4IiksCiAgICAgIHlheGlzID0gbGlzdCh0aXRsZSA9ICJDdXJ2ZSBpbmRleCIpLAogICAgICB6YXhpcyA9IGxpc3QodGl0bGUgPSAiU2NhbGVkIHZhbHVlIFstMSwgMV0iKQogICAgKSwKICAgIGxlZ2VuZCA9IGxpc3QodGl0bGUgPSBsaXN0KHRleHQgPSAiPGI+RnVuY3Rpb25zPC9iPiIpKQogICkKYGBgCgo=