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=