Causal christmas tree challenge 2022

I have drawn a (stylized) christmas tree using two potential outcomes functions and investigate how well causal forests approximate the resulting CATE function for different sample sizes.

library(tidyverse)
library(grf)
library(patchwork)

set.seed(1234)

# Define the functions
cw = 0.05
ch = 0.6
e = function(x){1/2}
m1 = function(x){(x < -0.8) * (3*x + 3) + ((x >= -0.8) & (x < (-0.8+cw))) * (-0.8*3 + 3 + ch) + ((x>(-0.8+cw)) & (x < -0.5)) * (3*x + 3) + ((x >= -0.5) & (x < (-0.5+cw))) * (-0.5*3 + 3 + ch) + ((x>(-0.5+cw)) & (x < -0.2)) * (3*x + 3) + ((x >= -0.2) & (x < (-0.2+cw))) * (-0.2*3 + 3 + ch) + ((x>(-0.2+cw)) & (x < 0)) * (3*x + 3) + (x >= 0 & x < 0.2) * (-3*x + 3) + ((x >= 0.2) & (x < (0.2+cw))) * (-0.2*3 + 3 + ch) + ((x>(0.2+cw)) & (x < 0.5)) * (-3*x + 3) + ((x >= 0.5) & (x < (0.5+cw))) * (-0.5*3 + 3 + ch) + ((x>(0.5+cw)) & (x < 0.8)) * (-3*x + 3) + ((x >= 0.8) & (x < (0.8+cw))) * (-0.8*3 + 3 + ch) + ((x>(0.8+cw))) * (-3*x + 3)  }
m0 = function(x){0 * ((x<(-0.7)) + (x>(0.07))) 
                - 0.8 *  ((x>(-0.07) & x<(0.07))) }
tau = function(x){m1(x) - m0(x)}

# Plot the two potential outcome fcts
g2 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="forestgreen") + 
  stat_function(fun=m0,size=1,colour="forestgreen") + ylab("Y(w)") + xlab("X1") + theme_bw()
# Plot CATE function
g3 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1") + theme_bw()
g2

g3



Causal Forest meets causal christmas tree

cf_meets_cct = function(n,e,p=2,...) {
  # Define the functions
  cw = 0.05
  ch = 0.6
  e = function(x){1/2}
  m1 = function(x){(x < -0.8) * (3*x + 3) + ((x >= -0.8) & (x < (-0.8+cw))) * (-0.8*3 + 3 + ch) + ((x>(-0.8+cw)) & (x < -0.5)) * (3*x + 3) + ((x >= -0.5) & (x < (-0.5+cw))) * (-0.5*3 + 3 + ch) + ((x>(-0.5+cw)) & (x < -0.2)) * (3*x + 3) + ((x >= -0.2) & (x < (-0.2+cw))) * (-0.2*3 + 3 + ch) + ((x>(-0.2+cw)) & (x < 0)) * (3*x + 3) + (x >= 0 & x < 0.2) * (-3*x + 3) + ((x >= 0.2) & (x < (0.2+cw))) * (-0.2*3 + 3 + ch) + ((x>(0.2+cw)) & (x < 0.5)) * (-3*x + 3) + ((x >= 0.5) & (x < (0.5+cw))) * (-0.5*3 + 3 + ch) + ((x>(0.5+cw)) & (x < 0.8)) * (-3*x + 3) + ((x >= 0.8) & (x < (0.8+cw))) * (-0.8*3 + 3 + ch) + ((x>(0.8+cw))) * (-3*x + 3)  }
  m0 = function(x){0 * ((x<(-0.7)) + (x>(0.07))) 
                - 0.8 *  ((x>(-0.07) & x<(0.07))) }
  tau = function(x){m1(x) - m0(x)}
  
  # Draw sample
  X = matrix(runif(n*p,-1,1),ncol=p)
  W = rbinom(n,1,e(X[,1]))
  Y = W*m1(X[,1]) + (1-W)*m0(X[,1]) + rnorm(n,0,1)
  
  # Run CF
  cf = causal_forest(X, Y, W, ...)
  cates = predict(cf)$predictions

  # Plot
  g = data.frame(x=X[,1],y=cates) %>% ggplot() + geom_point(aes(x=x,y=y),shape="square",color="blue") +
    stat_function(fun=tau,size=1) + ylab("CATE") + ggtitle(paste0("n=",toString(n)))
  
  # RMSE
  rmse = sqrt(mean((cates - tau(X[,1]))^2))

  # Return results
  list("g" = g,"RMSE" = rmse)
}

n100 = cf_meets_cct(100,tune.parameters = "all")
n1000 = cf_meets_cct(1000,tune.parameters = "all")
n10000 = cf_meets_cct(10000,tune.parameters = "all")
n100000 = cf_meets_cct(100000,tune.parameters = "all")
(n100$g | n1000$g) / (n10000$g | n100000$g)


data.frame(RMSE = c(n100$RMSE,n1000$RMSE,n10000$RMSE,n100000$RMSE),
   n = factor(c("n=100","n=1000","n=10000","n=100000"))) %>%
  ggplot(aes(x=n,y=RMSE)) + geom_point() + theme_bw()



1) Your turn (5P)

Draw also something using two potential outcome functions (either something different or beautify my tree) and check how well causal forests can approximate the CATE function resulting from your drawing.



Student solutions in alphabetical order

Maren Baumgärtner

As Christmas is the season to spread love, I decided to plot a heart.


e = function(x){1/2}


m1 <- function(x){1.8*sqrt(1-(abs(x)-1)^2)} # upper part receiving treatment
m0 <- function(x){acos(1-abs(x))-pi} # lower part not receiving treatment

tau = function(x){m1(x) - m0(x)}

# plot heart
data.frame(x = c(-2, 2)) %>% ggplot(aes(x))  +
  stat_function(fun = m1,size=1, colour = "#B22222") +
  stat_function(fun = m0,size=1, colour = "#B22222") +
  ylab("Y(w)") + xlab("X1") +
  theme_bw() + xlim(-2.5,2.5)


# plot CATE
data.frame(x = c(-2, 2)) %>% ggplot(aes(x)) + stat_function(fun = tau,size=1) + theme_bw() + xlim(-2.2,2.2) +  ylab("CATE")


Stefan Glaisner

# circle function
cir <- function(x){sqrt(1 - x^2)}
cut0 <- 0.75
cut1 <- 0.5
cut2 <- 0.25
slope0 <- cir(cut0) / cut2
slope1 <- cir(cut1) / cut2
slope2 <- cir(cut2) / cut2


e <- function(x){1/2}
m1 <- function(x){
  ((x >= -1 & x < -cut2) * cir(x) +
     (x >= -cut2 & x < 0) * (cir(cut2) - slope2*(x+cut2)) +
     (x >= 0 & x <= cut2) * (slope2*x) +
     (x > cut2 & x <= 1) * cir(x)
   )}
m0 <- function(x){
  ((x >= -1 & x < -cut0) * -cir(x) +
     (x >= -cut0 & x < -cut1) * (-cir(cut0) + slope0*(x+cut0)) +
     (x >= -cut1 & x < -cut2) * (-slope1*(x+cut1)) +
     (x >= -cut2 & x < cut2) * -cir(x) +
     (x >= cut2 & x < cut1) * (-cir(cut2) + slope1*(x-cut2)) +
     (x >= cut1 & x < cut0) * (-slope0*(x-cut1)) +
     (x >= cut0 & x <= 1) * -cir(x))}

tau <- function(x){m1(x) - m0(x)}

data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="forestgreen") + 
  stat_function(fun=m0,size=1,colour="forestgreen") + ylab("Y(w)") + xlab("X1")


data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1")


Stefan Grochowski

# Define e
e = function(x){1/2}

# Define the first outcome function 
m1 = function(x){abs(x) + sqrt(1-x^2)}
# Define the second potential outcome function 
m0 = function(x){abs(x) - sqrt(1-x^2)}
# Compute tau as the difference of the two potential outcome functions
tau = function(x){m1(x) - m0(x)}

# Plot the two potential outcome fcts (most important)
g4 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="red") + 
  stat_function(fun=m0,size=1,colour="darkred") + ylab("Y(w)") + xlab("X1")
# Plot CATE function
g5 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1")

# Show first plot
g4


# Show the resulting CATE
g5


Jacqueline Gut

A star, and the CATE: Batman

e = function(x){1/2}
m1 = function(x){(x< -1)*(1) + ((x >= -1) & (x < -0.5)) * (1) + ((x>=(-0.5)) & (x < 0)) *(2*x +2)+((x>=(0)) & (x < 0.5)) * (-2*x +2)+((x>=(0.5))) * (1) }
m0 = function(x){(x < (-1))*(1) +((-x))*((x>=(-1))& (x<(-0.625))) + (1.4*x+0.375) *((x>(-0.625) & x<0)) + (-1.4*x+0.375) *((x>=(0)) & (x<(0.625)))+ (x) *((x>=(0.625)) & (x<(1))) +(x>= 1)*(1) }

tau = function(x){m1(x) - m0(x)}

# Plot the two potential outcome fcts (most important)
g2 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="yellow") + 
  stat_function(fun=m0,size=1,colour="yellow") + ylab("Y(w)") + xlab("X1") + theme_bw()

# Plot CATE function
g3 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1") + theme_bw()

g2

g3


Sophia Herrmann

Christmas Ball

# Define the functions
cw1 <- 0.4
cw2 <- 0.15
cw3 <- 0.05

ch1 <- 0.3
ch2 <- 0.2
ch3 <- 1

e = function(x){1/2}
m_0 = function(x){-sqrt(1-(x^2))}

m_1 = function(x){(x < -cw1) * (sqrt(1-(x^2))) +
    ((x >= -cw1) & (x <= -cw2)) * (sqrt(1-(0.15^2)) + ch1) +
    ((x > -cw2) & (x <= -cw3)) * ( (sqrt(1-(0.15^2)) + ch1) + ch2) +
    ((x > -cw3) & (x <= cw3)) *  (((sqrt(1-(0.15^2)) + ch1) + ch2) + ch3) +
    ((x > cw3) & (x <= cw2)) *  ( ( (sqrt(1-(0.15^2)) + ch1) + ch2)) +
    ((x > cw2) & (x <= cw1)) *  ( ( (sqrt(1-(0.15^2)) + ch1))) +
    (x > cw1) * sqrt(1-(x^2))} 

tau_christmas_ball = function(x){m_1(x) - m_0(x)}

# Plot the two PO fcts (most important)
#g_1 <- data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m_1,size=1,colour="forestgreen") 
#g_2 <- data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m_0,size=1,colour="forestgreen")

g_christmas_ball <- data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m_1,size=1,colour="forestgreen") +
  stat_function(fun=m_0,size=1,colour="forestgreen") + ylab("Y(w)") + xlab("X1") #+
    ylim(1.7, 2)
<ScaleContinuousPosition>
 Range:  
 Limits:  1.7 --    2
# Plot CATE function
g_tau_christmas_ball <- data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau_christmas_ball,size=1) + ylab("CATE") + xlab("X1")

# g1 
#g_2
g_christmas_ball

g_tau_christmas_ball


Kevin Kopp

# Define the functions
cw = 0.001  # horizontal
ch = 3  # vertical
e = function(x){1/2}
m1 = function(x){ ((x >= (-1.2)) & (x < (-0.999))) * (15*x + 15) + ((x >= (-0.999)) & (x < (-0.8))) * (-15*x - 9) + ((x >= (-0.8)) & (x < (-0.6))) * (15*x + 15) + ((x >= (-0.6)) & (x < -0.4)) * (-15*x - 3) + ((x >= (-0.4)) & (x < (-0.2))) * (15*x + 9) + ((x>=(-0.2)) & (x < 0)) * (-15*x + 3) + (x >= 0 & x < 0.2) * (15*x + 3) + (x >= 0.2 & x < 0.4) * (-15*x + 9) + (x >= 0.4 & x < 0.6) * (15*x - 3) + (x >= 0.6 & x < 0.8) * (-15*x +15) + (x >= 0.8 & x < 1) * (15*x - 9)}
m0 = function(x){0 * ((x<(-0.7)) + (x>(0.07)))}
tau = function(x){m1(x) - m0(x)}

# Plot propensity score
# g1 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
# Plot the two potential outcome fcts (most important)
g2 = data.frame(x = c(-1.0, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="gold") + 
  stat_function(fun=m0,size=1,colour="gold") + ylab("Y(w)") + xlab("X1") + theme_bw()
# Plot CATE function
g3 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1")

g2_picture = data.frame(x = c(-1.0, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="black", geom = "area", fill = "gold") + stat_function(fun=m0,size=1,colour="black") + ylab("Y(w)") + xlab("X1") + theme_bw()

g2_picture


g3 + theme_bw()


Alexandros Parginos Dös

Causal heart

e = function(x){1/2}

# Get a (very) edgy heart
m1 = function(x){ (x<(-0.5))*(1+x) + ((x==(-0.5)))*(0.5) + (x>(-0.5) & x<(0))*(-x)  + 
                  (x==(0))*0 +
                  (x>(0) & x<(0.5))*(x) + (x==(0.5))*0.5 + (x>(0.5) )*(-x+1) }
m0 = function(x){- (1*x + 1) *  (x<(0)) - 1* ((x==(0)))  + (-1+1*x) *  (x>(0)) }
tau = function(x){m1(x) - m0(x)}

# Plot propensity score
# g1 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
# Plot the two potential outcome fcts (most important)
g2 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="red") + 
  stat_function(fun=m0,size=1,colour="red") + ylab("Y(w)") + xlab("X1")
# Plot CATE function
g3 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1")

# g1 
g2


Henri Pfleiderer

# Define the functions
jump = 0.1
small_jump = 0.01
very_small_jump = 0.001
height_bottle_neck = 10
width_bottle_neck = 1
ch = 0.6
e = function(x){1/2}
m1 = function(x){(x<6-small_jump)*(0) + ((x>=6)&(x<9 - width_bottle_neck/2))*((-8/9)*x^2 + 16*x - 18) + ((x>= 9 - width_bottle_neck/2)&(x<9 + width_bottle_neck/2))*(64 + height_bottle_neck) + ((x>=9 + width_bottle_neck/2)&(x<12))*((-8/9)*x^2 + 16*x - 18) + ((x>12)&(x<15))*0 + ((x>=15)&(x<19))*(sin(5*x) + 30) + (x>=19)*30}
m0 = function(x){(x<15)*0 + ((x>=15)&(x<17- jump))*(-7.5*x + 142.5) + ((x>=17- jump)&(x<17+ jump))*0 +  ((x<19)&(x>=17+ jump))*(7.5*x + -112.5) + (x>=19)*30}
tau = function(x){m1(x) - m0(x)}

# Plot propensity score
# g1 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=e,size=1) + ylab("e") + xlab("X1")
# Plot the two potential outcome fcts (most important)

g2 = data.frame(x = c(0, 25)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="hotpink") + 
  stat_function(fun=m0,size=1,colour="purple") + ylab("Y(w)") + xlab("X1")+ ggtitle("Sektflasche und Glas mit Schaum, ein Stillleben von Henri Pfleiderer, 2022")
# Plot CATE function
g3 = data.frame(x = c(0, 25)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1")

# g1 
g2

g3


Stella Rotter

# Define the functions
e = function(x){1/2}
m1 = function(x){(x < -1) * (x + 1) + 
                 ((x >= -0.7) & (x < -0.5)) * (-0.7*3 + 3) + (x > -0.7) +
                 ((x >= -0.62) & (x < -0.57)) * (0.4*1.2 + 0.1) +
                 ((x >= 0.5) & (x < 0.5)) * (0.4*2 + 3) + (x > 0.5) +
                 ((x >= 0.6) & (x < 0.7)) * (0.5*1.2 + 0.5) + 
                 ((x >= 0.8) & (x <= 1)) * (0.5*3 -3.5)}
m0 = function(x){0}
tau = function(x){m1(x) - m0(x)}

g2 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=m1,size=1,colour="navajowhite4") + 
  stat_function(fun=m0,size=1,colour="navajowhite4") + ylab("Y(w)") + xlab("X1") + ggtitle("The Ulmer Münster")
# Plot CATE function
g3 = data.frame(x = c(-1, 1)) %>% ggplot(aes(x)) + stat_function(fun=tau,size=1) + ylab("CATE") + xlab("X1")

# g1 
g2

g3


ChatGPT

Not very successful, but let’s see what it does next year…

# Set the plot dimensions
plot.new()
plot.window(xlim = c(-2, 2), ylim = c(-2, 2))

# Create a sequence of values from 0 to 2*pi in increments of 0.01
t <- seq(0, 2*pi, 0.01)

# Calculate the x and y coordinates for the tree
x <- sin(t)
y <- cos(t) - 1

# Use the polygon function to fill in the tree
polygon(x, y, col = "darkgreen")

# Use the lines function to draw the trunk
lines(c(0, 0), c(-1.5, -0.5), col = "brown", lwd = 2)

LS0tDQp0aXRsZTogIkNhdXNhbCBNTCAtIEFzc2lnbm1lbnQgOCINCmF1dGhvcjogIllvdXIgbmFtZSAoc3R1ZGVudCBJRCkiDQpvdXRwdXQ6IA0KICBodG1sX25vdGVib29rOg0KICAgIHRvYzogdHJ1ZQ0KICAgIHRvY19mbG9hdDogdHJ1ZQ0KICAgIGNvZGVfZm9sZGluZzogc2hvdw0KLS0tDQoNCg0KPGJyPg0KDQoNCiMgQ2F1c2FsIGNocmlzdG1hcyB0cmVlIGNoYWxsZW5nZSAyMDIyDQoNCkkgaGF2ZSBkcmF3biBhIChzdHlsaXplZCkgY2hyaXN0bWFzIHRyZWUgdXNpbmcgdHdvIHBvdGVudGlhbCBvdXRjb21lcyBmdW5jdGlvbnMgYW5kIGludmVzdGlnYXRlIGhvdyB3ZWxsIGNhdXNhbCBmb3Jlc3RzIGFwcHJveGltYXRlIHRoZSByZXN1bHRpbmcgQ0FURSBmdW5jdGlvbiBmb3IgZGlmZmVyZW50IHNhbXBsZSBzaXplcy4NCg0KDQpgYGB7cixtZXNzYWdlPUYsd2FybmluZz1GLGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTN9DQpsaWJyYXJ5KHRpZHl2ZXJzZSkNCmxpYnJhcnkoZ3JmKQ0KbGlicmFyeShwYXRjaHdvcmspDQoNCnNldC5zZWVkKDEyMzQpDQoNCiMgRGVmaW5lIHRoZSBmdW5jdGlvbnMNCmN3ID0gMC4wNQ0KY2ggPSAwLjYNCmUgPSBmdW5jdGlvbih4KXsxLzJ9DQptMSA9IGZ1bmN0aW9uKHgpeyh4IDwgLTAuOCkgKiAoMyp4ICsgMykgKyAoKHggPj0gLTAuOCkgJiAoeCA8ICgtMC44K2N3KSkpICogKC0wLjgqMyArIDMgKyBjaCkgKyAoKHg+KC0wLjgrY3cpKSAmICh4IDwgLTAuNSkpICogKDMqeCArIDMpICsgKCh4ID49IC0wLjUpICYgKHggPCAoLTAuNStjdykpKSAqICgtMC41KjMgKyAzICsgY2gpICsgKCh4PigtMC41K2N3KSkgJiAoeCA8IC0wLjIpKSAqICgzKnggKyAzKSArICgoeCA+PSAtMC4yKSAmICh4IDwgKC0wLjIrY3cpKSkgKiAoLTAuMiozICsgMyArIGNoKSArICgoeD4oLTAuMitjdykpICYgKHggPCAwKSkgKiAoMyp4ICsgMykgKyAoeCA+PSAwICYgeCA8IDAuMikgKiAoLTMqeCArIDMpICsgKCh4ID49IDAuMikgJiAoeCA8ICgwLjIrY3cpKSkgKiAoLTAuMiozICsgMyArIGNoKSArICgoeD4oMC4yK2N3KSkgJiAoeCA8IDAuNSkpICogKC0zKnggKyAzKSArICgoeCA+PSAwLjUpICYgKHggPCAoMC41K2N3KSkpICogKC0wLjUqMyArIDMgKyBjaCkgKyAoKHg+KDAuNStjdykpICYgKHggPCAwLjgpKSAqICgtMyp4ICsgMykgKyAoKHggPj0gMC44KSAmICh4IDwgKDAuOCtjdykpKSAqICgtMC44KjMgKyAzICsgY2gpICsgKCh4PigwLjgrY3cpKSkgKiAoLTMqeCArIDMpICB9DQptMCA9IGZ1bmN0aW9uKHgpezAgKiAoKHg8KC0wLjcpKSArICh4PigwLjA3KSkpIA0KICAgICAgICAgICAgICAgIC0gMC44ICogICgoeD4oLTAuMDcpICYgeDwoMC4wNykpKSB9DQp0YXUgPSBmdW5jdGlvbih4KXttMSh4KSAtIG0wKHgpfQ0KDQojIFBsb3QgdGhlIHR3byBwb3RlbnRpYWwgb3V0Y29tZSBmY3RzDQpnMiA9IGRhdGEuZnJhbWUoeCA9IGMoLTEsIDEpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1tMSxzaXplPTEsY29sb3VyPSJmb3Jlc3RncmVlbiIpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxjb2xvdXI9ImZvcmVzdGdyZWVuIikgKyB5bGFiKCJZKHcpIikgKyB4bGFiKCJYMSIpICsgdGhlbWVfYncoKQ0KIyBQbG90IENBVEUgZnVuY3Rpb24NCmczID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgeGxhYigiWDEiKSArIHRoZW1lX2J3KCkNCmcyDQpnMw0KYGBgDQoNCjxicj4NCjxicj4NCg0KIyBDYXVzYWwgRm9yZXN0IG1lZXRzIGNhdXNhbCBjaHJpc3RtYXMgdHJlZQ0KDQpgYGB7cixtZXNzYWdlPUYsd2FybmluZz1GfQ0KY2ZfbWVldHNfY2N0ID0gZnVuY3Rpb24obixlLHA9MiwuLi4pIHsNCiAgIyBEZWZpbmUgdGhlIGZ1bmN0aW9ucw0KICBjdyA9IDAuMDUNCiAgY2ggPSAwLjYNCiAgZSA9IGZ1bmN0aW9uKHgpezEvMn0NCiAgbTEgPSBmdW5jdGlvbih4KXsoeCA8IC0wLjgpICogKDMqeCArIDMpICsgKCh4ID49IC0wLjgpICYgKHggPCAoLTAuOCtjdykpKSAqICgtMC44KjMgKyAzICsgY2gpICsgKCh4PigtMC44K2N3KSkgJiAoeCA8IC0wLjUpKSAqICgzKnggKyAzKSArICgoeCA+PSAtMC41KSAmICh4IDwgKC0wLjUrY3cpKSkgKiAoLTAuNSozICsgMyArIGNoKSArICgoeD4oLTAuNStjdykpICYgKHggPCAtMC4yKSkgKiAoMyp4ICsgMykgKyAoKHggPj0gLTAuMikgJiAoeCA8ICgtMC4yK2N3KSkpICogKC0wLjIqMyArIDMgKyBjaCkgKyAoKHg+KC0wLjIrY3cpKSAmICh4IDwgMCkpICogKDMqeCArIDMpICsgKHggPj0gMCAmIHggPCAwLjIpICogKC0zKnggKyAzKSArICgoeCA+PSAwLjIpICYgKHggPCAoMC4yK2N3KSkpICogKC0wLjIqMyArIDMgKyBjaCkgKyAoKHg+KDAuMitjdykpICYgKHggPCAwLjUpKSAqICgtMyp4ICsgMykgKyAoKHggPj0gMC41KSAmICh4IDwgKDAuNStjdykpKSAqICgtMC41KjMgKyAzICsgY2gpICsgKCh4PigwLjUrY3cpKSAmICh4IDwgMC44KSkgKiAoLTMqeCArIDMpICsgKCh4ID49IDAuOCkgJiAoeCA8ICgwLjgrY3cpKSkgKiAoLTAuOCozICsgMyArIGNoKSArICgoeD4oMC44K2N3KSkpICogKC0zKnggKyAzKSAgfQ0KICBtMCA9IGZ1bmN0aW9uKHgpezAgKiAoKHg8KC0wLjcpKSArICh4PigwLjA3KSkpIA0KICAgICAgICAgICAgICAgIC0gMC44ICogICgoeD4oLTAuMDcpICYgeDwoMC4wNykpKSB9DQogIHRhdSA9IGZ1bmN0aW9uKHgpe20xKHgpIC0gbTAoeCl9DQogIA0KICAjIERyYXcgc2FtcGxlDQogIFggPSBtYXRyaXgocnVuaWYobipwLC0xLDEpLG5jb2w9cCkNCiAgVyA9IHJiaW5vbShuLDEsZShYWywxXSkpDQogIFkgPSBXKm0xKFhbLDFdKSArICgxLVcpKm0wKFhbLDFdKSArIHJub3JtKG4sMCwxKQ0KICANCiAgIyBSdW4gQ0YNCiAgY2YgPSBjYXVzYWxfZm9yZXN0KFgsIFksIFcsIC4uLikNCiAgY2F0ZXMgPSBwcmVkaWN0KGNmKSRwcmVkaWN0aW9ucw0KDQogICMgUGxvdA0KICBnID0gZGF0YS5mcmFtZSh4PVhbLDFdLHk9Y2F0ZXMpICU+JSBnZ3Bsb3QoKSArIGdlb21fcG9pbnQoYWVzKHg9eCx5PXkpLHNoYXBlPSJzcXVhcmUiLGNvbG9yPSJibHVlIikgKw0KICAgIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgZ2d0aXRsZShwYXN0ZTAoIm49Iix0b1N0cmluZyhuKSkpDQogIA0KICAjIFJNU0UNCiAgcm1zZSA9IHNxcnQobWVhbigoY2F0ZXMgLSB0YXUoWFssMV0pKV4yKSkNCg0KICAjIFJldHVybiByZXN1bHRzDQogIGxpc3QoImciID0gZywiUk1TRSIgPSBybXNlKQ0KfQ0KDQpuMTAwID0gY2ZfbWVldHNfY2N0KDEwMCx0dW5lLnBhcmFtZXRlcnMgPSAiYWxsIikNCm4xMDAwID0gY2ZfbWVldHNfY2N0KDEwMDAsdHVuZS5wYXJhbWV0ZXJzID0gImFsbCIpDQpuMTAwMDAgPSBjZl9tZWV0c19jY3QoMTAwMDAsdHVuZS5wYXJhbWV0ZXJzID0gImFsbCIpDQpuMTAwMDAwID0gY2ZfbWVldHNfY2N0KDEwMDAwMCx0dW5lLnBhcmFtZXRlcnMgPSAiYWxsIikNCmBgYA0KDQpgYGB7cixtZXNzYWdlPUYsd2FybmluZz1GfQ0KKG4xMDAkZyB8IG4xMDAwJGcpIC8gKG4xMDAwMCRnIHwgbjEwMDAwMCRnKQ0KDQpkYXRhLmZyYW1lKFJNU0UgPSBjKG4xMDAkUk1TRSxuMTAwMCRSTVNFLG4xMDAwMCRSTVNFLG4xMDAwMDAkUk1TRSksDQogICBuID0gZmFjdG9yKGMoIm49MTAwIiwibj0xMDAwIiwibj0xMDAwMCIsIm49MTAwMDAwIikpKSAlPiUNCiAgZ2dwbG90KGFlcyh4PW4seT1STVNFKSkgKyBnZW9tX3BvaW50KCkgKyB0aGVtZV9idygpDQpgYGANCg0KDQo8YnI+DQo8YnI+DQoNCiMgMSkgWW91ciB0dXJuICg1UCkNCg0KRHJhdyBhbHNvIHNvbWV0aGluZyB1c2luZyB0d28gcG90ZW50aWFsIG91dGNvbWUgZnVuY3Rpb25zIChlaXRoZXIgc29tZXRoaW5nIGRpZmZlcmVudCBvciBiZWF1dGlmeSBteSB0cmVlKSBhbmQgY2hlY2sgaG93IHdlbGwgY2F1c2FsIGZvcmVzdHMgY2FuIGFwcHJveGltYXRlIHRoZSBDQVRFIGZ1bmN0aW9uIHJlc3VsdGluZyBmcm9tIHlvdXIgZHJhd2luZy4NCg0KPGJyPg0KPGJyPg0KDQojIFN0dWRlbnQgc29sdXRpb25zIGluIGFscGhhYmV0aWNhbCBvcmRlcg0KDQojIyBNYXJlbiBCYXVtZ8OkcnRuZXINCg0KQXMgQ2hyaXN0bWFzIGlzIHRoZSBzZWFzb24gdG8gc3ByZWFkIGxvdmUsIEkgZGVjaWRlZCB0byBwbG90IGEgaGVhcnQuDQoNCmBgYHtyLCB3YXJuaW5nPUZBTFNFfQ0KDQplID0gZnVuY3Rpb24oeCl7MS8yfQ0KDQoNCm0xIDwtIGZ1bmN0aW9uKHgpezEuOCpzcXJ0KDEtKGFicyh4KS0xKV4yKX0gIyB1cHBlciBwYXJ0IHJlY2VpdmluZyB0cmVhdG1lbnQNCm0wIDwtIGZ1bmN0aW9uKHgpe2Fjb3MoMS1hYnMoeCkpLXBpfSAjIGxvd2VyIHBhcnQgbm90IHJlY2VpdmluZyB0cmVhdG1lbnQNCg0KdGF1ID0gZnVuY3Rpb24oeCl7bTEoeCkgLSBtMCh4KX0NCg0KIyBwbG90IGhlYXJ0DQpkYXRhLmZyYW1lKHggPSBjKC0yLCAyKSkgJT4lIGdncGxvdChhZXMoeCkpICArDQogIHN0YXRfZnVuY3Rpb24oZnVuID0gbTEsc2l6ZT0xLCBjb2xvdXIgPSAiI0IyMjIyMiIpICsNCiAgc3RhdF9mdW5jdGlvbihmdW4gPSBtMCxzaXplPTEsIGNvbG91ciA9ICIjQjIyMjIyIikgKw0KICB5bGFiKCJZKHcpIikgKyB4bGFiKCJYMSIpICsNCiAgdGhlbWVfYncoKSArIHhsaW0oLTIuNSwyLjUpDQoNCiMgcGxvdCBDQVRFDQpkYXRhLmZyYW1lKHggPSBjKC0yLCAyKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW4gPSB0YXUsc2l6ZT0xKSArIHRoZW1lX2J3KCkgKyB4bGltKC0yLjIsMi4yKSArICB5bGFiKCJDQVRFIikNCmBgYA0KPGJyPg0KDQojIyBTdGVmYW4gR2xhaXNuZXINCmBgYHtyIGVycm9yID0gRkFMU0UsIHdhcm5pbmcgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFfQ0KIyBjaXJjbGUgZnVuY3Rpb24NCmNpciA8LSBmdW5jdGlvbih4KXtzcXJ0KDEgLSB4XjIpfQ0KY3V0MCA8LSAwLjc1DQpjdXQxIDwtIDAuNQ0KY3V0MiA8LSAwLjI1DQpzbG9wZTAgPC0gY2lyKGN1dDApIC8gY3V0Mg0Kc2xvcGUxIDwtIGNpcihjdXQxKSAvIGN1dDINCnNsb3BlMiA8LSBjaXIoY3V0MikgLyBjdXQyDQoNCg0KZSA8LSBmdW5jdGlvbih4KXsxLzJ9DQptMSA8LSBmdW5jdGlvbih4KXsNCiAgKCh4ID49IC0xICYgeCA8IC1jdXQyKSAqIGNpcih4KSArDQogICAgICh4ID49IC1jdXQyICYgeCA8IDApICogKGNpcihjdXQyKSAtIHNsb3BlMiooeCtjdXQyKSkgKw0KICAgICAoeCA+PSAwICYgeCA8PSBjdXQyKSAqIChzbG9wZTIqeCkgKw0KICAgICAoeCA+IGN1dDIgJiB4IDw9IDEpICogY2lyKHgpDQogICApfQ0KbTAgPC0gZnVuY3Rpb24oeCl7DQogICgoeCA+PSAtMSAmIHggPCAtY3V0MCkgKiAtY2lyKHgpICsNCiAgICAgKHggPj0gLWN1dDAgJiB4IDwgLWN1dDEpICogKC1jaXIoY3V0MCkgKyBzbG9wZTAqKHgrY3V0MCkpICsNCiAgICAgKHggPj0gLWN1dDEgJiB4IDwgLWN1dDIpICogKC1zbG9wZTEqKHgrY3V0MSkpICsNCiAgICAgKHggPj0gLWN1dDIgJiB4IDwgY3V0MikgKiAtY2lyKHgpICsNCiAgICAgKHggPj0gY3V0MiAmIHggPCBjdXQxKSAqICgtY2lyKGN1dDIpICsgc2xvcGUxKih4LWN1dDIpKSArDQogICAgICh4ID49IGN1dDEgJiB4IDwgY3V0MCkgKiAoLXNsb3BlMCooeC1jdXQxKSkgKw0KICAgICAoeCA+PSBjdXQwICYgeCA8PSAxKSAqIC1jaXIoeCkpfQ0KDQp0YXUgPC0gZnVuY3Rpb24oeCl7bTEoeCkgLSBtMCh4KX0NCg0KZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxjb2xvdXI9ImZvcmVzdGdyZWVuIikgKyANCiAgc3RhdF9mdW5jdGlvbihmdW49bTAsc2l6ZT0xLGNvbG91cj0iZm9yZXN0Z3JlZW4iKSArIHlsYWIoIlkodykiKSArIHhsYWIoIlgxIikNCg0KZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgeGxhYigiWDEiKQ0KDQpgYGANCg0KPGJyPg0KDQojIyBTdGVmYW4gR3JvY2hvd3NraQ0KYGBge3J9DQojIERlZmluZSBlDQplID0gZnVuY3Rpb24oeCl7MS8yfQ0KDQojIERlZmluZSB0aGUgZmlyc3Qgb3V0Y29tZSBmdW5jdGlvbiANCm0xID0gZnVuY3Rpb24oeCl7YWJzKHgpICsgc3FydCgxLXheMil9DQojIERlZmluZSB0aGUgc2Vjb25kIHBvdGVudGlhbCBvdXRjb21lIGZ1bmN0aW9uIA0KbTAgPSBmdW5jdGlvbih4KXthYnMoeCkgLSBzcXJ0KDEteF4yKX0NCiMgQ29tcHV0ZSB0YXUgYXMgdGhlIGRpZmZlcmVuY2Ugb2YgdGhlIHR3byBwb3RlbnRpYWwgb3V0Y29tZSBmdW5jdGlvbnMNCnRhdSA9IGZ1bmN0aW9uKHgpe20xKHgpIC0gbTAoeCl9DQoNCiMgUGxvdCB0aGUgdHdvIHBvdGVudGlhbCBvdXRjb21lIGZjdHMgKG1vc3QgaW1wb3J0YW50KQ0KZzQgPSBkYXRhLmZyYW1lKHggPSBjKC0xLCAxKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49bTEsc2l6ZT0xLGNvbG91cj0icmVkIikgKyANCiAgc3RhdF9mdW5jdGlvbihmdW49bTAsc2l6ZT0xLGNvbG91cj0iZGFya3JlZCIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKQ0KIyBQbG90IENBVEUgZnVuY3Rpb24NCmc1ID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgeGxhYigiWDEiKQ0KDQojIFNob3cgZmlyc3QgcGxvdA0KZzQNCg0KIyBTaG93IHRoZSByZXN1bHRpbmcgQ0FURQ0KZzUNCmBgYA0KDQo8YnI+DQoNCiMjIEphY3F1ZWxpbmUgR3V0DQoNCkEgc3RhciwgYW5kIHRoZSBDQVRFOiBCYXRtYW4NCmBgYHtyLGZpZy5oZWlnaHQ9NCwgZmlnLndpZHRoPTQuNX0NCmUgPSBmdW5jdGlvbih4KXsxLzJ9DQptMSA9IGZ1bmN0aW9uKHgpeyh4PCAtMSkqKDEpICsgKCh4ID49IC0xKSAmICh4IDwgLTAuNSkpICogKDEpICsgKCh4Pj0oLTAuNSkpICYgKHggPCAwKSkgKigyKnggKzIpKygoeD49KDApKSAmICh4IDwgMC41KSkgKiAoLTIqeCArMikrKCh4Pj0oMC41KSkpICogKDEpIH0NCm0wID0gZnVuY3Rpb24oeCl7KHggPCAoLTEpKSooMSkgKygoLXgpKSooKHg+PSgtMSkpJiAoeDwoLTAuNjI1KSkpICsgKDEuNCp4KzAuMzc1KSAqKCh4PigtMC42MjUpICYgeDwwKSkgKyAoLTEuNCp4KzAuMzc1KSAqKCh4Pj0oMCkpICYgKHg8KDAuNjI1KSkpKyAoeCkgKigoeD49KDAuNjI1KSkgJiAoeDwoMSkpKSArKHg+PSAxKSooMSkgfQ0KDQp0YXUgPSBmdW5jdGlvbih4KXttMSh4KSAtIG0wKHgpfQ0KDQojIFBsb3QgdGhlIHR3byBwb3RlbnRpYWwgb3V0Y29tZSBmY3RzIChtb3N0IGltcG9ydGFudCkNCmcyID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxjb2xvdXI9InllbGxvdyIpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxjb2xvdXI9InllbGxvdyIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKSArIHRoZW1lX2J3KCkNCg0KIyBQbG90IENBVEUgZnVuY3Rpb24NCmczID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgeGxhYigiWDEiKSArIHRoZW1lX2J3KCkNCg0KZzINCmczDQpgYGANCg0KPGJyPg0KDQojIyBTb3BoaWEgSGVycm1hbm4NCiMjIyBDaHJpc3RtYXMgQmFsbA0KDQpgYGB7ciwgZmlnLmhlaWdodD02LCBmaWcud2lkdGg9NCwgd2FybmluZz1GQUxTRSwgbWVzc2FnZT1GfQ0KIyBEZWZpbmUgdGhlIGZ1bmN0aW9ucw0KY3cxIDwtIDAuNA0KY3cyIDwtIDAuMTUNCmN3MyA8LSAwLjA1DQoNCmNoMSA8LSAwLjMNCmNoMiA8LSAwLjINCmNoMyA8LSAxDQoNCmUgPSBmdW5jdGlvbih4KXsxLzJ9DQptXzAgPSBmdW5jdGlvbih4KXstc3FydCgxLSh4XjIpKX0NCg0KbV8xID0gZnVuY3Rpb24oeCl7KHggPCAtY3cxKSAqIChzcXJ0KDEtKHheMikpKSArDQogICAgKCh4ID49IC1jdzEpICYgKHggPD0gLWN3MikpICogKHNxcnQoMS0oMC4xNV4yKSkgKyBjaDEpICsNCiAgICAoKHggPiAtY3cyKSAmICh4IDw9IC1jdzMpKSAqICggKHNxcnQoMS0oMC4xNV4yKSkgKyBjaDEpICsgY2gyKSArDQogICAgKCh4ID4gLWN3MykgJiAoeCA8PSBjdzMpKSAqICAoKChzcXJ0KDEtKDAuMTVeMikpICsgY2gxKSArIGNoMikgKyBjaDMpICsNCiAgICAoKHggPiBjdzMpICYgKHggPD0gY3cyKSkgKiAgKCAoIChzcXJ0KDEtKDAuMTVeMikpICsgY2gxKSArIGNoMikpICsNCiAgICAoKHggPiBjdzIpICYgKHggPD0gY3cxKSkgKiAgKCAoIChzcXJ0KDEtKDAuMTVeMikpICsgY2gxKSkpICsNCiAgICAoeCA+IGN3MSkgKiBzcXJ0KDEtKHheMikpfSANCg0KdGF1X2NocmlzdG1hc19iYWxsID0gZnVuY3Rpb24oeCl7bV8xKHgpIC0gbV8wKHgpfQ0KDQojIFBsb3QgdGhlIHR3byBQTyBmY3RzIChtb3N0IGltcG9ydGFudCkNCiNnXzEgPC0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW1fMSxzaXplPTEsY29sb3VyPSJmb3Jlc3RncmVlbiIpIA0KI2dfMiA8LSBkYXRhLmZyYW1lKHggPSBjKC0xLCAxKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49bV8wLHNpemU9MSxjb2xvdXI9ImZvcmVzdGdyZWVuIikNCg0KZ19jaHJpc3RtYXNfYmFsbCA8LSBkYXRhLmZyYW1lKHggPSBjKC0xLCAxKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49bV8xLHNpemU9MSxjb2xvdXI9ImZvcmVzdGdyZWVuIikgKw0KICBzdGF0X2Z1bmN0aW9uKGZ1bj1tXzAsc2l6ZT0xLGNvbG91cj0iZm9yZXN0Z3JlZW4iKSArIHlsYWIoIlkodykiKSArIHhsYWIoIlgxIikgIysNCiAgICB5bGltKDEuNywgMikNCg0KIyBQbG90IENBVEUgZnVuY3Rpb24NCmdfdGF1X2NocmlzdG1hc19iYWxsIDwtIGRhdGEuZnJhbWUoeCA9IGMoLTEsIDEpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj10YXVfY2hyaXN0bWFzX2JhbGwsc2l6ZT0xKSArIHlsYWIoIkNBVEUiKSArIHhsYWIoIlgxIikNCg0KIyBnMSANCiNnXzINCmdfY2hyaXN0bWFzX2JhbGwNCmdfdGF1X2NocmlzdG1hc19iYWxsDQpgYGANCg0KPGJyPg0KDQojIyBLZXZpbiBLb3BwDQoNCmBgYHtyfQ0KIyBEZWZpbmUgdGhlIGZ1bmN0aW9ucw0KY3cgPSAwLjAwMSAgIyBob3Jpem9udGFsDQpjaCA9IDMgICMgdmVydGljYWwNCmUgPSBmdW5jdGlvbih4KXsxLzJ9DQptMSA9IGZ1bmN0aW9uKHgpeyAoKHggPj0gKC0xLjIpKSAmICh4IDwgKC0wLjk5OSkpKSAqICgxNSp4ICsgMTUpICsgKCh4ID49ICgtMC45OTkpKSAmICh4IDwgKC0wLjgpKSkgKiAoLTE1KnggLSA5KSArICgoeCA+PSAoLTAuOCkpICYgKHggPCAoLTAuNikpKSAqICgxNSp4ICsgMTUpICsgKCh4ID49ICgtMC42KSkgJiAoeCA8IC0wLjQpKSAqICgtMTUqeCAtIDMpICsgKCh4ID49ICgtMC40KSkgJiAoeCA8ICgtMC4yKSkpICogKDE1KnggKyA5KSArICgoeD49KC0wLjIpKSAmICh4IDwgMCkpICogKC0xNSp4ICsgMykgKyAoeCA+PSAwICYgeCA8IDAuMikgKiAoMTUqeCArIDMpICsgKHggPj0gMC4yICYgeCA8IDAuNCkgKiAoLTE1KnggKyA5KSArICh4ID49IDAuNCAmIHggPCAwLjYpICogKDE1KnggLSAzKSArICh4ID49IDAuNiAmIHggPCAwLjgpICogKC0xNSp4ICsxNSkgKyAoeCA+PSAwLjggJiB4IDwgMSkgKiAoMTUqeCAtIDkpfQ0KbTAgPSBmdW5jdGlvbih4KXswICogKCh4PCgtMC43KSkgKyAoeD4oMC4wNykpKX0NCnRhdSA9IGZ1bmN0aW9uKHgpe20xKHgpIC0gbTAoeCl9DQoNCiMgUGxvdCBwcm9wZW5zaXR5IHNjb3JlDQojIGcxID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPWUsc2l6ZT0xKSArIHlsYWIoImUiKSArIHhsYWIoIlgxIikNCiMgUGxvdCB0aGUgdHdvIHBvdGVudGlhbCBvdXRjb21lIGZjdHMgKG1vc3QgaW1wb3J0YW50KQ0KZzIgPSBkYXRhLmZyYW1lKHggPSBjKC0xLjAsIDEpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1tMSxzaXplPTEsY29sb3VyPSJnb2xkIikgKyANCiAgc3RhdF9mdW5jdGlvbihmdW49bTAsc2l6ZT0xLGNvbG91cj0iZ29sZCIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKSArIHRoZW1lX2J3KCkNCiMgUGxvdCBDQVRFIGZ1bmN0aW9uDQpnMyA9IGRhdGEuZnJhbWUoeCA9IGMoLTEsIDEpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj10YXUsc2l6ZT0xKSArIHlsYWIoIkNBVEUiKSArIHhsYWIoIlgxIikNCg0KZzJfcGljdHVyZSA9IGRhdGEuZnJhbWUoeCA9IGMoLTEuMCwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxjb2xvdXI9ImJsYWNrIiwgZ2VvbSA9ICJhcmVhIiwgZmlsbCA9ICJnb2xkIikgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1tMCxzaXplPTEsY29sb3VyPSJibGFjayIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKSArIHRoZW1lX2J3KCkNCg0KZzJfcGljdHVyZQ0KDQpnMyArIHRoZW1lX2J3KCkNCmBgYA0KDQo8YnI+DQoNCiMjIEFsZXhhbmRyb3MgUGFyZ2lub3MgRMO2cw0KDQojIyMgQ2F1c2FsIGhlYXJ0DQoNCmBgYHtyLG1lc3NhZ2U9Rix3YXJuaW5nPUZ9DQplID0gZnVuY3Rpb24oeCl7MS8yfQ0KDQojIEdldCBhICh2ZXJ5KSBlZGd5IGhlYXJ0DQptMSA9IGZ1bmN0aW9uKHgpeyAoeDwoLTAuNSkpKigxK3gpICsgKCh4PT0oLTAuNSkpKSooMC41KSArICh4PigtMC41KSAmIHg8KDApKSooLXgpICArIA0KICAgICAgICAgICAgICAgICAgKHg9PSgwKSkqMCArDQogICAgICAgICAgICAgICAgICAoeD4oMCkgJiB4PCgwLjUpKSooeCkgKyAoeD09KDAuNSkpKjAuNSArICh4PigwLjUpICkqKC14KzEpIH0NCm0wID0gZnVuY3Rpb24oeCl7LSAoMSp4ICsgMSkgKiAgKHg8KDApKSAtIDEqICgoeD09KDApKSkgICsgKC0xKzEqeCkgKiAgKHg+KDApKSB9DQp0YXUgPSBmdW5jdGlvbih4KXttMSh4KSAtIG0wKHgpfQ0KDQojIFBsb3QgcHJvcGVuc2l0eSBzY29yZQ0KIyBnMSA9IGRhdGEuZnJhbWUoeCA9IGMoLTEsIDEpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1lLHNpemU9MSkgKyB5bGFiKCJlIikgKyB4bGFiKCJYMSIpDQojIFBsb3QgdGhlIHR3byBwb3RlbnRpYWwgb3V0Y29tZSBmY3RzIChtb3N0IGltcG9ydGFudCkNCmcyID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxjb2xvdXI9InJlZCIpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxjb2xvdXI9InJlZCIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKQ0KIyBQbG90IENBVEUgZnVuY3Rpb24NCmczID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgeGxhYigiWDEiKQ0KDQojIGcxIA0KZzINCmBgYA0KPGJyPg0KDQojIyBIZW5yaSBQZmxlaWRlcmVyDQpgYGB7cixtZXNzYWdlPUYsd2FybmluZz1GfQ0KIyBEZWZpbmUgdGhlIGZ1bmN0aW9ucw0KanVtcCA9IDAuMQ0Kc21hbGxfanVtcCA9IDAuMDENCnZlcnlfc21hbGxfanVtcCA9IDAuMDAxDQpoZWlnaHRfYm90dGxlX25lY2sgPSAxMA0Kd2lkdGhfYm90dGxlX25lY2sgPSAxDQpjaCA9IDAuNg0KZSA9IGZ1bmN0aW9uKHgpezEvMn0NCm0xID0gZnVuY3Rpb24oeCl7KHg8Ni1zbWFsbF9qdW1wKSooMCkgKyAoKHg+PTYpJih4PDkgLSB3aWR0aF9ib3R0bGVfbmVjay8yKSkqKCgtOC85KSp4XjIgKyAxNip4IC0gMTgpICsgKCh4Pj0gOSAtIHdpZHRoX2JvdHRsZV9uZWNrLzIpJih4PDkgKyB3aWR0aF9ib3R0bGVfbmVjay8yKSkqKDY0ICsgaGVpZ2h0X2JvdHRsZV9uZWNrKSArICgoeD49OSArIHdpZHRoX2JvdHRsZV9uZWNrLzIpJih4PDEyKSkqKCgtOC85KSp4XjIgKyAxNip4IC0gMTgpICsgKCh4PjEyKSYoeDwxNSkpKjAgKyAoKHg+PTE1KSYoeDwxOSkpKihzaW4oNSp4KSArIDMwKSArICh4Pj0xOSkqMzB9DQptMCA9IGZ1bmN0aW9uKHgpeyh4PDE1KSowICsgKCh4Pj0xNSkmKHg8MTctIGp1bXApKSooLTcuNSp4ICsgMTQyLjUpICsgKCh4Pj0xNy0ganVtcCkmKHg8MTcrIGp1bXApKSowICsgICgoeDwxOSkmKHg+PTE3KyBqdW1wKSkqKDcuNSp4ICsgLTExMi41KSArICh4Pj0xOSkqMzB9DQp0YXUgPSBmdW5jdGlvbih4KXttMSh4KSAtIG0wKHgpfQ0KDQojIFBsb3QgcHJvcGVuc2l0eSBzY29yZQ0KIyBnMSA9IGRhdGEuZnJhbWUoeCA9IGMoLTEsIDEpKSAlPiUgZ2dwbG90KGFlcyh4KSkgKyBzdGF0X2Z1bmN0aW9uKGZ1bj1lLHNpemU9MSkgKyB5bGFiKCJlIikgKyB4bGFiKCJYMSIpDQojIFBsb3QgdGhlIHR3byBwb3RlbnRpYWwgb3V0Y29tZSBmY3RzIChtb3N0IGltcG9ydGFudCkNCg0KZzIgPSBkYXRhLmZyYW1lKHggPSBjKDAsIDI1KSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49bTEsc2l6ZT0xLGNvbG91cj0iaG90cGluayIpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxjb2xvdXI9InB1cnBsZSIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKSsgZ2d0aXRsZSgiU2VrdGZsYXNjaGUgdW5kIEdsYXMgbWl0IFNjaGF1bSwgZWluIFN0aWxsbGViZW4gdm9uIEhlbnJpIFBmbGVpZGVyZXIsIDIwMjIiKQ0KIyBQbG90IENBVEUgZnVuY3Rpb24NCmczID0gZGF0YS5mcmFtZSh4ID0gYygwLCAyNSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPXRhdSxzaXplPTEpICsgeWxhYigiQ0FURSIpICsgeGxhYigiWDEiKQ0KDQojIGcxIA0KZzINCmczDQpgYGANCjxicj4NCg0KIyMgU3RlbGxhIFJvdHRlcg0KDQpgYGB7cixtZXNzYWdlPUYsd2FybmluZz1GfQ0KIyBEZWZpbmUgdGhlIGZ1bmN0aW9ucw0KZSA9IGZ1bmN0aW9uKHgpezEvMn0NCm0xID0gZnVuY3Rpb24oeCl7KHggPCAtMSkgKiAoeCArIDEpICsgDQogICAgICAgICAgICAgICAgICgoeCA+PSAtMC43KSAmICh4IDwgLTAuNSkpICogKC0wLjcqMyArIDMpICsgKHggPiAtMC43KSArDQogICAgICAgICAgICAgICAgICgoeCA+PSAtMC42MikgJiAoeCA8IC0wLjU3KSkgKiAoMC40KjEuMiArIDAuMSkgKw0KICAgICAgICAgICAgICAgICAoKHggPj0gMC41KSAmICh4IDwgMC41KSkgKiAoMC40KjIgKyAzKSArICh4ID4gMC41KSArDQogICAgICAgICAgICAgICAgICgoeCA+PSAwLjYpICYgKHggPCAwLjcpKSAqICgwLjUqMS4yICsgMC41KSArIA0KICAgICAgICAgICAgICAgICAoKHggPj0gMC44KSAmICh4IDw9IDEpKSAqICgwLjUqMyAtMy41KX0NCm0wID0gZnVuY3Rpb24oeCl7MH0NCnRhdSA9IGZ1bmN0aW9uKHgpe20xKHgpIC0gbTAoeCl9DQoNCmcyID0gZGF0YS5mcmFtZSh4ID0gYygtMSwgMSkpICU+JSBnZ3Bsb3QoYWVzKHgpKSArIHN0YXRfZnVuY3Rpb24oZnVuPW0xLHNpemU9MSxjb2xvdXI9Im5hdmFqb3doaXRlNCIpICsgDQogIHN0YXRfZnVuY3Rpb24oZnVuPW0wLHNpemU9MSxjb2xvdXI9Im5hdmFqb3doaXRlNCIpICsgeWxhYigiWSh3KSIpICsgeGxhYigiWDEiKSArIGdndGl0bGUoIlRoZSBVbG1lciBNw7xuc3RlciIpDQojIFBsb3QgQ0FURSBmdW5jdGlvbg0KZzMgPSBkYXRhLmZyYW1lKHggPSBjKC0xLCAxKSkgJT4lIGdncGxvdChhZXMoeCkpICsgc3RhdF9mdW5jdGlvbihmdW49dGF1LHNpemU9MSkgKyB5bGFiKCJDQVRFIikgKyB4bGFiKCJYMSIpDQoNCiMgZzEgDQpnMg0KZzMNCmBgYA0KDQoNCjxicj4NCg0KIyMgQ2hhdEdQVA0KTm90IHZlcnkgc3VjY2Vzc2Z1bCwgYnV0IGxldCdzIHNlZSB3aGF0IGl0IGRvZXMgbmV4dCB5ZWFyLi4uDQoNCmBgYHtyLG1lc3NhZ2U9Rix3YXJuaW5nPUZ9DQojIFNldCB0aGUgcGxvdCBkaW1lbnNpb25zDQpwbG90Lm5ldygpDQpwbG90LndpbmRvdyh4bGltID0gYygtMiwgMiksIHlsaW0gPSBjKC0yLCAyKSkNCg0KIyBDcmVhdGUgYSBzZXF1ZW5jZSBvZiB2YWx1ZXMgZnJvbSAwIHRvIDIqcGkgaW4gaW5jcmVtZW50cyBvZiAwLjAxDQp0IDwtIHNlcSgwLCAyKnBpLCAwLjAxKQ0KDQojIENhbGN1bGF0ZSB0aGUgeCBhbmQgeSBjb29yZGluYXRlcyBmb3IgdGhlIHRyZWUNCnggPC0gc2luKHQpDQp5IDwtIGNvcyh0KSAtIDENCg0KIyBVc2UgdGhlIHBvbHlnb24gZnVuY3Rpb24gdG8gZmlsbCBpbiB0aGUgdHJlZQ0KcG9seWdvbih4LCB5LCBjb2wgPSAiZGFya2dyZWVuIikNCg0KIyBVc2UgdGhlIGxpbmVzIGZ1bmN0aW9uIHRvIGRyYXcgdGhlIHRydW5rDQpsaW5lcyhjKDAsIDApLCBjKC0xLjUsIC0wLjUpLCBjb2wgPSAiYnJvd24iLCBsd2QgPSAyKQ0KYGBgDQo=