This project uses machine learning with 2016 American Community Survey Data to predict the probability of divorce.

Environment Set-Up

Variables

First we need to set up the environment

# start clean
rm(list = ls())
# Set working directory
setwd("/Users/cueland/Google Drive/School/670 - Data Science/divorce-prediction/")
# useful libraries
library(plyr)
library(ggplot2)
library(dplyr)
library(reshape2)
library(rpart)
library(rpart.plot)
library(devtools)
library(gridExtra)
library(randomForest)
library(plotROC)

Functions

Set up useful functions.

#Mean F1
meanf1 <- function(actual, predicted){
  #Mean F1 score function
  #actual = a vector of actual labels
  #predicted = predicted labels
  
  classes <- unique(actual)
  results <- data.frame()
  for(k in classes){
    results <- rbind(results, 
                     data.frame(class.name = k,
                                weight = sum(actual == k)/length(actual),
                                precision = sum(predicted == k &
                                                  actual == k) / 
                                  sum(predicted == k),
                                recall = sum(predicted == k &
                                               actual == k) /
                                  sum(actual == k)))
  }
  results$score <- results$weight * 2 *
    (results$precision * results$recall) /
    (results$precision + results$recall) 
  return(sum(results$score))
}
inter <- function(x,y,z) {
  # Create a sequence of numbers based on the number of values you want
  # in the sequence
  # x,y = beginning and end of sequence
  # z = number of intervals to produce
  f <- c(x,y)
  int <- abs(x - y) / z
  d <- seq(min(f),max(f),int)
  return(d)
}

Gather the Data

Data Dictionary

To interpret the actual data download, we first need to download the data dictionary, which will then be used to organize the data we download from the ACS API.

Data Download

ACS data is downloaded by the month, therefore in order to download all of the data from 2016, we need to create a for loop that collects each month’s data from 2016. First we build the URL for each request, download the files, and then process the data using the data dictionary downloaded above.

Process the Data

In order to use the data for divorce predictions, we need to ensure we only use valid data, so we need to drop observations such as surveys that weren’t fully completed, or observations for people under the age of 18.

In addition, we need to transform the data, factorizing the information that is provided in categories, such as marital status.

# load the data from before
pt <- proc.time()[3]
load("/Users/cueland/Google Drive/School/670 - Data Science/divorce-prediction/2016.RData")
proc.time()[3] - pt
elapsed 
 270.59 
# convert all column names to lowercase
names(l) <- tolower(names(l))
# ------------------------------------ Cull Data -----------------------------|
# Select which variables are useful
code <- c("hrhhid", "hrhhid2", "hwhhwtln", "pulineno", "hrmonth", "hryear4", "hurespli", "hufinal", "huspnish", "hetenure", "hehousut", "hefaminc", "hrnumhou", "hubus", "gereg", "gediv", "gtcbsast", "gtmetsta", "gtindvpc", "gtcbsasz", "prtage", "prtfage", "pemaritl", "pesex", "peafever", "peafnow", "peeduca", "ptdtrace", "prdthsp", "pehspnon", "prcitshp", "prinusyr", "pemlr", "puwk", "pubus1", "pubus2ot", "puretot", "pudis", "peret1", "pudis1", "puabsot", "pulay", "pemjot", "pemjnum", "pehrftpt", "pehruslt", "pehrwant", "pehrrsn1", "pehrrsn2", "pehrrsn3", "puhroff1", "puhrot1", "puhrot2", "pehractt", "pulk", "pedwwnto", "prcivlf", "prdisc", "prftlf", "prwksch", "prwkstat", "prmjind1", "prmjocc1", "penlfact", "prchld", "prnmchld", "pedisear", "pediseye", "pedisrem", "pedisphy", "pedisdrs", "pedisout", "pepdemp1")
# Subset to the desired variables
data <- l[code]
# convert the data to all numeric values
for (n in names(data)) {
  data[[n]] <- as.numeric(data[[n]])
}
# Get rid of any observations that don't have a line number
data <- data[data$pulineno > 0, ]
# Keep only complete surveys
data <- data[data$hufinal %in% c(1, 201), ]
# Keep only people 18 years and older
data <- data[data$prtage > 17, ]
# reverse sort by month to only keep the latest observation from 2016
data <- data[order(-as.numeric(data$hrmonth)), ]
data <- data[!duplicated(cbind(data$hrhhid, data$pulineno,
                               data$hrmonth, data$hufinal)),]
# Convert all negative values to NAs
for (n in names(data)) {
  data[[n]][data[[n]] < 0] <- NA
}
# Recode & Factorize marital status
data$mstatus[data$pemaritl %in% c(1, 2, 3)] <- "married"
data$mstatus[data$pemaritl %in% c(4, 5)] <- "divorced"
data$mstatus[data$pemaritl == 6] <- "single"
data$pemaritl <- factor(data$mstatus)
data$mstatus <- NULL
# show distrubution of marriage status
table(data$pemaritl, useNA = "ifany")

divorced  married   single 
  149597   699837   299189 
# Save the numeric data frame before we factorize the rest of the factor vars
data.numeric <- data
# Variables to Factorize (all variables that are not numeric as listed below)
facs <- names(data)[!(names(data) %in% c("hrhhid", "hryear4", "hrnumhou",
                                         "prtage", "pemjnum", "pehruslt",
                                         "puhrot2", "pehractt", "prnmchld"))]
# Loop through each variable to factorize
for (n in facs) {
  data[[n]] <- factor(data[[n]])
}
head(data)
save(data, file = "/Users/cueland/Google Drive/School/670 - Data Science/divorce-prediction/data.RData", compress = TRUE)

Run Decision Tree

First we divide the data randomly into 2 separate parts, train and test, with an approximate 70/30 split. From there, we train the decision tree model using a selected set of variables from the original set. This set of variables was chosen from multiple tests with different combinations, as well as culling certain variables that are explicitly related to marriage status.

set.seed(12345)
train <- runif(nrow(data))
train <- train > 0.7
# Create separate train and test sets
data.train <- data[train, ]
head(data.train[1:6])

data.test <- data[!train, ]
head(data.test[1:6])

Optimization

Because we ran the model with CP = 0 (the most complex), we can subsequently simplify, or “prune”, the decision tree model in order to avoid over-fitting the model to the train data. We use two approaches for this.

XERROR

First, we examine the XERROR of each level of complexity and prune to the level that offers the lowers XERROR value.

data.train$predict <- predict(fit, data.train, type= "class")
meanf1(data.train$predict, data.train$pemaritl)
[1] 0.8713695
# Test the predictions for the test subset for CP = 0
data.test$predict <- predict(fit, data.test, type= "class")
meanf1(data.test$predict, data.test$pemaritl)
[1] 0.7917867
# ------------------------------ min XERROR (mincp) ---------------------------|
# determine the CP that yields the minimum XERROR value 
mincp <- fit$cptable[fit$cptable[, 4] == min(fit$cptable[, 4]), 1]
if (length(mincp) > 1) {
  fit$cptable[fit$cptable[, 4] == min(fit$cptable[, 4]), ]
  mincp <- mincp[1]
}
# prune to the CP that yielded the min XERROR value, mincp
fit.mincp <- prune(fit, cp = mincp)
# Test the predictions for the test subset for CP = mincp
data.test$predict.mincp <- predict(fit.mincp, data.test, type= "class")
meanf1(data.test$predict.mincp, data.test$pemaritl)
[1] 0.8119978

Iteration

Second, we use an iterative approach to determine which level of pruning yields the highest mean F1, which is our measure of best fit. This is done with a series of two loops, the first to find a rough estimate of the best CP value, and the second to further refine the CP value. This yields a mean F1 score for the test subset of 0.812.

# create data frame with results to see how optimization worked
f1s.refined <- data.frame(CP = rev(inter(next.it[1],next.it[2], 10)),
                          mean_F1 = rev(f1s))
f1s.refined

plot(f1s.refined)  # plot optimization

# assign best CP value
cp.best <- f1s.refined[,1][f1s.refined[,2] == max(f1s.refined[,2])]
# find optimal fit
fit.best <- prune(fit, cp = cp.best)
useful.vars.best <- data.frame(name = attr(fit.best$variable.importance,
                                           "names"),
                          importance = fit.best$variable.importance,
                          row.names = NULL)
useful.vars.best
# Show further simplified decision tree graphic
fit.simple <- prune(fit, cp = 0.005)
rpart.plot(fit.simple, shadow.col = "grey", nn = TRUE)

# Test the predictions for the test subset for CP = mincp
data.test$predict.best <- predict(fit.best, data.test, type= "class")
meanf1(data.test$predict.best, data.test$pemaritl)
[1] 0.8119281
LS0tCnRpdGxlOiAiRGl2b3JjZSBQcmVkaWN0aW9uIgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDogZGVmYXVsdAogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKLS0tCgpUaGlzIHByb2plY3QgdXNlcyBtYWNoaW5lIGxlYXJuaW5nIHdpdGggMjAxNiBBbWVyaWNhbiBDb21tdW5pdHkgU3VydmV5IERhdGEgdG8gcHJlZGljdCB0aGUgcHJvYmFiaWxpdHkgb2YgZGl2b3JjZS4KCiMjIyBFbnZpcm9ubWVudCBTZXQtVXAKCiMjIyMgVmFyaWFibGVzCkZpcnN0IHdlIG5lZWQgdG8gc2V0IHVwIHRoZSBlbnZpcm9ubWVudApgYGB7ciBtZXNzYWdlID0gRkFMU0V9CiMgc3RhcnQgY2xlYW4Kcm0obGlzdCA9IGxzKCkpCgojIFNldCB3b3JraW5nIGRpcmVjdG9yeQpzZXR3ZCgiL1VzZXJzL2N1ZWxhbmQvR29vZ2xlIERyaXZlL1NjaG9vbC82NzAgLSBEYXRhIFNjaWVuY2UvZGl2b3JjZS1wcmVkaWN0aW9uLyIpCgojIHVzZWZ1bCBsaWJyYXJpZXMKbGlicmFyeShwbHlyKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkoZHBseXIpCmxpYnJhcnkocmVzaGFwZTIpCmxpYnJhcnkocnBhcnQpCmxpYnJhcnkocnBhcnQucGxvdCkKbGlicmFyeShkZXZ0b29scykKbGlicmFyeShncmlkRXh0cmEpCmxpYnJhcnkocmFuZG9tRm9yZXN0KQpsaWJyYXJ5KHBsb3RST0MpCmBgYAojIyMjIEZ1bmN0aW9ucwoKU2V0IHVwIHVzZWZ1bCBmdW5jdGlvbnMuCmBgYHtyfQojTWVhbiBGMQptZWFuZjEgPC0gZnVuY3Rpb24oYWN0dWFsLCBwcmVkaWN0ZWQpewogICNNZWFuIEYxIHNjb3JlIGZ1bmN0aW9uCiAgI2FjdHVhbCA9IGEgdmVjdG9yIG9mIGFjdHVhbCBsYWJlbHMKICAjcHJlZGljdGVkID0gcHJlZGljdGVkIGxhYmVscwogIAogIGNsYXNzZXMgPC0gdW5pcXVlKGFjdHVhbCkKICByZXN1bHRzIDwtIGRhdGEuZnJhbWUoKQogIGZvcihrIGluIGNsYXNzZXMpewogICAgcmVzdWx0cyA8LSByYmluZChyZXN1bHRzLCAKICAgICAgICAgICAgICAgICAgICAgZGF0YS5mcmFtZShjbGFzcy5uYW1lID0gaywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB3ZWlnaHQgPSBzdW0oYWN0dWFsID09IGspL2xlbmd0aChhY3R1YWwpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHByZWNpc2lvbiA9IHN1bShwcmVkaWN0ZWQgPT0gayAmCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0dWFsID09IGspIC8gCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdW0ocHJlZGljdGVkID09IGspLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHJlY2FsbCA9IHN1bShwcmVkaWN0ZWQgPT0gayAmCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0dWFsID09IGspIC8KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN1bShhY3R1YWwgPT0gaykpKQogIH0KICByZXN1bHRzJHNjb3JlIDwtIHJlc3VsdHMkd2VpZ2h0ICogMiAqCiAgICAocmVzdWx0cyRwcmVjaXNpb24gKiByZXN1bHRzJHJlY2FsbCkgLwogICAgKHJlc3VsdHMkcHJlY2lzaW9uICsgcmVzdWx0cyRyZWNhbGwpIAogIHJldHVybihzdW0ocmVzdWx0cyRzY29yZSkpCn0KCmludGVyIDwtIGZ1bmN0aW9uKHgseSx6KSB7CiAgIyBDcmVhdGUgYSBzZXF1ZW5jZSBvZiBudW1iZXJzIGJhc2VkIG9uIHRoZSBudW1iZXIgb2YgdmFsdWVzIHlvdSB3YW50CiAgIyBpbiB0aGUgc2VxdWVuY2UKICAjIHgseSA9IGJlZ2lubmluZyBhbmQgZW5kIG9mIHNlcXVlbmNlCiAgIyB6ID0gbnVtYmVyIG9mIGludGVydmFscyB0byBwcm9kdWNlCiAgZiA8LSBjKHgseSkKICBpbnQgPC0gYWJzKHggLSB5KSAvIHoKICBkIDwtIHNlcShtaW4oZiksbWF4KGYpLGludCkKICByZXR1cm4oZCkKfQpgYGAKIyMjIEdhdGhlciB0aGUgRGF0YQoKIyMjIyBEYXRhIERpY3Rpb25hcnkKVG8gaW50ZXJwcmV0IHRoZSBhY3R1YWwgZGF0YSBkb3dubG9hZCwgd2UgZmlyc3QgbmVlZCB0byBkb3dubG9hZCB0aGUgZGF0YSBkaWN0aW9uYXJ5LCB3aGljaCB3aWxsIHRoZW4gYmUgdXNlZCB0byBvcmdhbml6ZSB0aGUgZGF0YSB3ZSBkb3dubG9hZCBmcm9tIHRoZSBBQ1MgQVBJLgpgYGB7ciBtZXNzYWdlID0gRkFMU0V9CiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gR2V0IERhdGEgRGljdGlvbmFyeSAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tfAojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCgojIGRvd25sb2FkIHRoZSBkYXRhIGRpY3Rpb25hcnkKYSA9IHJlYWRMaW5lcygiaHR0cDovL3RoZWRhdGF3ZWIucm0uY2Vuc3VzLmdvdi9wdWIvY3BzL2Jhc2ljLzIwMTUwMS0vSmFudWFyeV8yMDE1X1JlY29yZF9MYXlvdXQudHh0IikKCiMgc2hyaW5rIGFueSB0YWJzIGRvd24gdG8ganVzdCBhIHNpbmdsZSB0YWIKc3RyIDwtKGdzdWIoIlxcdCsiLCJcdCIsYSkpCgojIHNldCB1cApjbGVhbiA8LSBjKCkKbGVuZ3RocyA8LSBjKCkKCiMgc2V0IHVwIHRoZSBlbXB0eSBkYXRhIGZyYW1lIHRvIHBvcHVsYXRlIHdpdGggdGhlIGRhdGEgZGljdGlvbmFyeQpkaWMgPSBkYXRhLmZyYW1lKCkKZm9yKGsgaW4gc3RyKXsKICAjIGRldGVybWluZSB3aGljaCBsaW5lcyBhcmUgdXNlYWJsZSwgYW5kIHB1dCB0aGVtIGludG8gdGhlIGNsZWFuIHZhcmlhYmxlCiAgaWYoKGxlbmd0aChncmVwKCJbMC05XSB7MCwxfS0gezAsMX1bMC05XSIsIGspKSA+IDApICYmIChzdWJzdHIoaywxLDEpIT0iXHQiKSAmJiAoc3Vic3RyKGssMSwxKSE9IiIpICYmIChzdWJzdHIoaywxLDEpIT0iIFx0IikpewogICAgIyBhc3NpZ24gdmFsaWQgbGluZXMgaW50byB0aGUgY2xlYW4gdmFyaWFibGUKICAgIGNsZWFuW2xlbmd0aChjbGVhbikgKyAxXSA8LSBrCiAgICAjIHNwbGl0IHRoZSB2YWxpZCBsaW5lcyBpbnRvIHRoZWlyIHNlcGFyYXRlIGNvdW50ZXIgcGFydHMKICAgIHRlbXAgPSB1bmxpc3Qoc3Ryc3BsaXQoaywiXHQiKSkKICAgIGxlbmd0aHNbbGVuZ3RoKGxlbmd0aHMpKzFdIDwtIGxlbmd0aCh0ZW1wKQogICAgIyBvdXRwdXQgZWFjaCByb3cgb2YgdGhlIGRhdGEgZGljdGlvbmFyeSB0byBoYXZlIDQgY29sdW1ucwogICAgaWYobGVuZ3RoKHRlbXApICVpbiUgYyg0OjUpKXsKICAgICAgZGljIDwtIHJiaW5kKGRpYywgZGF0YS5mcmFtZSh0ZW1wWzFdLHRlbXBbMl0sdGVtcFszXSx0ZW1wW2xlbmd0aCh0ZW1wKV0pKQogICAgfQogIH0KfQoKIyByZW5hbWUgdGhlIGNvbHVtbnMKbmFtZXMoZGljKSA8LSBjKCJOQU1FIiwgIlNJWkUiLCAiREVTQ1JJUFRJT04iLCAiTE9DQVRJT04iKQoKIyBzaG93IHRoZSBmaXJzdCBmZXcgb2JzZXJ2YXRpb25zIG9mIHRoZSBkaWN0aW9uYXJ5CmhlYWQoZGljKQojIG91dHB1dCB0aGUgZGljdGlvbmFyeSB0byBhIGNzdiBmaWxlIGZvciBlYXNpZXIgcmVmZXJlbmNlCndyaXRlLmNzdihkaWNbLGMoIk5BTUUiLCAiREVTQ1JJUFRJT04iKV0sIGZpbGUgPSAiL1VzZXJzL2N1ZWxhbmQvR29vZ2xlIERyaXZlL1NjaG9vbC82NzAgLSBEYXRhIFNjaWVuY2UvZGl2b3JjZS1wcmVkaWN0aW9uL2RhdGFfZGljLmNzdiIsIHJvdy5uYW1lcyA9IEZBTFNFKQpgYGAKIyMjIyBEYXRhIERvd25sb2FkCgpBQ1MgZGF0YSBpcyBkb3dubG9hZGVkIGJ5IHRoZSBtb250aCwgdGhlcmVmb3JlIGluIG9yZGVyIHRvIGRvd25sb2FkIGFsbCBvZiB0aGUgZGF0YSBmcm9tIDIwMTYsIHdlIG5lZWQgdG8gY3JlYXRlIGEgZm9yIGxvb3AgdGhhdCBjb2xsZWN0cyBlYWNoIG1vbnRoJ3MgZGF0YSBmcm9tIDIwMTYuIEZpcnN0IHdlIGJ1aWxkIHRoZSBVUkwgZm9yIGVhY2ggcmVxdWVzdCwgZG93bmxvYWQgdGhlIGZpbGVzLCBhbmQgdGhlbiBwcm9jZXNzIHRoZSBkYXRhIHVzaW5nIHRoZSBkYXRhIGRpY3Rpb25hcnkgZG93bmxvYWRlZCBhYm92ZS4KYGBge3J9CiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSBHZXQgRGF0YSAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tfAojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjCgojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIEJ1aWxkIFVSTCAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tfAojIGxpc3Qgb2YgbW9udGhzIHRvIG9idGFpbiBkYXRhCm1lcyA8LSBjKCJqYW4iLCAiZmViIiwgIm1hciIsICJhcHIiLCAibWF5IiwgImp1biIsICJqdWwiLCAiYXVnIiwgInNlcCIsICJvY3QiLCAibm92IiwgImRlYyIpCmJhc2V1cmwgPC0gImh0dHA6Ly90aGVkYXRhd2ViLnJtLmNlbnN1cy5nb3YvcHViL2Nwcy9iYXNpYy8yMDE1MDEtLyIKcG9zdHVybCA8LSAicHViLmRhdC5neiIKeWVhciA8LSAiMTYiCgojIHNldCB1cCBlbXRweSBjb250ZW50cyBmaWxlcwp0bXAgPC0gdGVtcGZpbGUoKQpsIDwtIGRhdGEuZnJhbWUoKQoKIyBsb29wIHRocm91Z2ggZWFjaCBtb250aApmb3IgKG4gaW4gMToxMikgewogICMgY29uc3RydWN0IFVSTCB3aXRoIHBhc3RlCiAgdXJsIDwtIHBhc3RlKGJhc2V1cmwsIG1lc1tuXSwgeWVhciwgcG9zdHVybCwgc2VwID0gIiIpCiAgIyBkb3dubG9hZCB0aGUgZmlsZQogIGRvd25sb2FkLmZpbGUodXJsLHRtcCkKICAjIHJlYWQgdGhlIGZpbGUKICBkIDwtIHJlYWRMaW5lcyh0bXApCgogICMgZGV0ZXJtaW5lIHRoZSBzdGFydCBhbmQgZW5kIGxvY2F0aW9ucyBmb3IgZWFjaCBlbnRyeSBiYXNlZCBvbiB0aGUgTE9DQVRJT04KICBkaWMkc3RhcnRfbG9jIDwtIGFzLm51bWVyaWMobGFwcGx5KGFzLmNoYXJhY3RlcihkaWMkTE9DQVRJT04pLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZnVuY3Rpb24oeCkgc3Ryc3BsaXQoeCwgIi0iKVtbMV1dWzFdKSkKICBkaWMkc3RvcF9sb2MgPC0gYXMubnVtZXJpYyhsYXBwbHkoYXMuY2hhcmFjdGVyKGRpYyRMT0NBVElPTiksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZ1bmN0aW9uKHgpIHN0cnNwbGl0KHgsICItIilbWzFdXVsyXSkpCiAgCiAgIyBzZXQgdXAgYW4gZW1wdHkgZGF0YSBmcmFtZSB3aXRoCiAgZGF0YSA8LSBtYXRyaXgoZGF0YSA9IE5BLCBucm93ID0gbGVuZ3RoKGQpLCBuY29sID0gbnJvdyhkaWMpKQogIGRhdGEgPC0gYXMuZGF0YS5mcmFtZShkYXRhKQogIG5hbWVzKGRhdGEpIDwtIGRpYyROQU1FCiAgCiAgIyBpdGVyYXRlIHRocm91Z2ggZWFjaCBvYnNlcnZhdGlvbiBhbmQgZ2F0aGVyIGFwcHJvcHJpYXRlIGRhdGEgaW50byBjZWxscwogIGZvcihpIGluIDE6bnJvdyhkaWMpKXsKICAgIHN0YXJ0X2xvYyA8LSBkaWMkc3RhcnRfbG9jW2ldCiAgICBzdG9wX2xvYyA8LSBkaWMkc3RvcF9sb2NbaV0KICAgIGNvbCA8LSBhcy5jaGFyYWN0ZXIoZGljJE5BTUVbaV0pCiAgICBkYXRhWyxjb2xdIDwtIHN1YnN0cihkLCBzdGFydF9sb2MsIHN0b3BfbG9jKQogIH0KICAKICAjIGFwcGVuZCB0aGUgZGF0YSB0byB0aGUgZW5kIG9mIHRoZSBtYWluIGRhdGFzZXQKICBsIDwtIHJiaW5kKGwsIGRhdGEpCiAgIyBwcm9ncmVzcyB1cGRhdGUKICBwcmludChwYXN0ZSgiZG9uZSB3aXRoICIsIG4sIHNlcCA9ICIiKSkKfQoKIyBkaXNwbGF5IGZpcnN0IDUgY29sdW1ucyBhbmQgcm93cwpoZWFkKGwpCgojIHNhdmUgdGhlIGRhdGEKc2F2ZShsLCBmaWxlID0gIi9Vc2Vycy9jdWVsYW5kL0dvb2dsZSBEcml2ZS9TY2hvb2wvNjcwIC0gRGF0YSBTY2llbmNlL2Rpdm9yY2UtcHJlZGljdGlvbi8yMDE2LlJEYXRhIiwgY29tcHJlc3MgPSBUUlVFKQpgYGAKIyMjIFByb2Nlc3MgdGhlIERhdGEKCkluIG9yZGVyIHRvIHVzZSB0aGUgZGF0YSBmb3IgZGl2b3JjZSBwcmVkaWN0aW9ucywgd2UgbmVlZCB0byBlbnN1cmUgd2Ugb25seSB1c2UgdmFsaWQgZGF0YSwgc28gd2UgbmVlZCB0byBkcm9wIG9ic2VydmF0aW9ucyBzdWNoIGFzIHN1cnZleXMgdGhhdCB3ZXJlbid0IGZ1bGx5IGNvbXBsZXRlZCwgb3Igb2JzZXJ2YXRpb25zIGZvciBwZW9wbGUgdW5kZXIgdGhlIGFnZSBvZiAxOC4gIAoKSW4gYWRkaXRpb24sIHdlIG5lZWQgdG8gdHJhbnNmb3JtIHRoZSBkYXRhLCBmYWN0b3JpemluZyB0aGUgaW5mb3JtYXRpb24gdGhhdCBpcyBwcm92aWRlZCBpbiBjYXRlZ29yaWVzLCBzdWNoIGFzIG1hcml0YWwgc3RhdHVzLgpgYGB7cn0KIyBsb2FkIHRoZSBkYXRhIGZyb20gYmVmb3JlCnB0IDwtIHByb2MudGltZSgpWzNdCmxvYWQoIi9Vc2Vycy9jdWVsYW5kL0dvb2dsZSBEcml2ZS9TY2hvb2wvNjcwIC0gRGF0YSBTY2llbmNlL2Rpdm9yY2UtcHJlZGljdGlvbi8yMDE2LlJEYXRhIikKcHJvYy50aW1lKClbM10gLSBwdAoKIyBjb252ZXJ0IGFsbCBjb2x1bW4gbmFtZXMgdG8gbG93ZXJjYXNlCm5hbWVzKGwpIDwtIHRvbG93ZXIobmFtZXMobCkpCgojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLSBDdWxsIERhdGEgLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS18CgojIFNlbGVjdCB3aGljaCB2YXJpYWJsZXMgYXJlIHVzZWZ1bApjb2RlIDwtIGMoImhyaGhpZCIsICJocmhoaWQyIiwgImh3aGh3dGxuIiwgInB1bGluZW5vIiwgImhybW9udGgiLCAiaHJ5ZWFyNCIsICJodXJlc3BsaSIsICJodWZpbmFsIiwgImh1c3BuaXNoIiwgImhldGVudXJlIiwgImhlaG91c3V0IiwgImhlZmFtaW5jIiwgImhybnVtaG91IiwgImh1YnVzIiwgImdlcmVnIiwgImdlZGl2IiwgImd0Y2JzYXN0IiwgImd0bWV0c3RhIiwgImd0aW5kdnBjIiwgImd0Y2JzYXN6IiwgInBydGFnZSIsICJwcnRmYWdlIiwgInBlbWFyaXRsIiwgInBlc2V4IiwgInBlYWZldmVyIiwgInBlYWZub3ciLCAicGVlZHVjYSIsICJwdGR0cmFjZSIsICJwcmR0aHNwIiwgInBlaHNwbm9uIiwgInByY2l0c2hwIiwgInByaW51c3lyIiwgInBlbWxyIiwgInB1d2siLCAicHVidXMxIiwgInB1YnVzMm90IiwgInB1cmV0b3QiLCAicHVkaXMiLCAicGVyZXQxIiwgInB1ZGlzMSIsICJwdWFic290IiwgInB1bGF5IiwgInBlbWpvdCIsICJwZW1qbnVtIiwgInBlaHJmdHB0IiwgInBlaHJ1c2x0IiwgInBlaHJ3YW50IiwgInBlaHJyc24xIiwgInBlaHJyc24yIiwgInBlaHJyc24zIiwgInB1aHJvZmYxIiwgInB1aHJvdDEiLCAicHVocm90MiIsICJwZWhyYWN0dCIsICJwdWxrIiwgInBlZHd3bnRvIiwgInByY2l2bGYiLCAicHJkaXNjIiwgInByZnRsZiIsICJwcndrc2NoIiwgInByd2tzdGF0IiwgInBybWppbmQxIiwgInBybWpvY2MxIiwgInBlbmxmYWN0IiwgInByY2hsZCIsICJwcm5tY2hsZCIsICJwZWRpc2VhciIsICJwZWRpc2V5ZSIsICJwZWRpc3JlbSIsICJwZWRpc3BoeSIsICJwZWRpc2RycyIsICJwZWRpc291dCIsICJwZXBkZW1wMSIpCgojIFN1YnNldCB0byB0aGUgZGVzaXJlZCB2YXJpYWJsZXMKZGF0YSA8LSBsW2NvZGVdCgojIGNvbnZlcnQgdGhlIGRhdGEgdG8gYWxsIG51bWVyaWMgdmFsdWVzCmZvciAobiBpbiBuYW1lcyhkYXRhKSkgewogIGRhdGFbW25dXSA8LSBhcy5udW1lcmljKGRhdGFbW25dXSkKfQoKIyBHZXQgcmlkIG9mIGFueSBvYnNlcnZhdGlvbnMgdGhhdCBkb24ndCBoYXZlIGEgbGluZSBudW1iZXIKZGF0YSA8LSBkYXRhW2RhdGEkcHVsaW5lbm8gPiAwLCBdCgojIEtlZXAgb25seSBjb21wbGV0ZSBzdXJ2ZXlzCmRhdGEgPC0gZGF0YVtkYXRhJGh1ZmluYWwgJWluJSBjKDEsIDIwMSksIF0KCiMgS2VlcCBvbmx5IHBlb3BsZSAxOCB5ZWFycyBhbmQgb2xkZXIKZGF0YSA8LSBkYXRhW2RhdGEkcHJ0YWdlID4gMTcsIF0KCiMgcmV2ZXJzZSBzb3J0IGJ5IG1vbnRoIHRvIG9ubHkga2VlcCB0aGUgbGF0ZXN0IG9ic2VydmF0aW9uIGZyb20gMjAxNgpkYXRhIDwtIGRhdGFbb3JkZXIoLWFzLm51bWVyaWMoZGF0YSRocm1vbnRoKSksIF0KCmRhdGEgPC0gZGF0YVshZHVwbGljYXRlZChjYmluZChkYXRhJGhyaGhpZCwgZGF0YSRwdWxpbmVubywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRhdGEkaHJtb250aCwgZGF0YSRodWZpbmFsKSksXQoKIyBDb252ZXJ0IGFsbCBuZWdhdGl2ZSB2YWx1ZXMgdG8gTkFzCmZvciAobiBpbiBuYW1lcyhkYXRhKSkgewogIGRhdGFbW25dXVtkYXRhW1tuXV0gPCAwXSA8LSBOQQp9CgojIFJlY29kZSAmIEZhY3Rvcml6ZSBtYXJpdGFsIHN0YXR1cwpkYXRhJG1zdGF0dXNbZGF0YSRwZW1hcml0bCAlaW4lIGMoMSwgMiwgMyldIDwtICJtYXJyaWVkIgpkYXRhJG1zdGF0dXNbZGF0YSRwZW1hcml0bCAlaW4lIGMoNCwgNSldIDwtICJkaXZvcmNlZCIKZGF0YSRtc3RhdHVzW2RhdGEkcGVtYXJpdGwgPT0gNl0gPC0gInNpbmdsZSIKZGF0YSRwZW1hcml0bCA8LSBmYWN0b3IoZGF0YSRtc3RhdHVzKQpkYXRhJG1zdGF0dXMgPC0gTlVMTAojIHNob3cgZGlzdHJ1YnV0aW9uIG9mIG1hcnJpYWdlIHN0YXR1cwp0YWJsZShkYXRhJHBlbWFyaXRsLCB1c2VOQSA9ICJpZmFueSIpCgojIFNhdmUgdGhlIG51bWVyaWMgZGF0YSBmcmFtZSBiZWZvcmUgd2UgZmFjdG9yaXplIHRoZSByZXN0IG9mIHRoZSBmYWN0b3IgdmFycwpkYXRhLm51bWVyaWMgPC0gZGF0YQoKIyBWYXJpYWJsZXMgdG8gRmFjdG9yaXplIChhbGwgdmFyaWFibGVzIHRoYXQgYXJlIG5vdCBudW1lcmljIGFzIGxpc3RlZCBiZWxvdykKZmFjcyA8LSBuYW1lcyhkYXRhKVshKG5hbWVzKGRhdGEpICVpbiUgYygiaHJoaGlkIiwgImhyeWVhcjQiLCAiaHJudW1ob3UiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJwcnRhZ2UiLCAicGVtam51bSIsICJwZWhydXNsdCIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgInB1aHJvdDIiLCAicGVocmFjdHQiLCAicHJubWNobGQiKSldCgojIExvb3AgdGhyb3VnaCBlYWNoIHZhcmlhYmxlIHRvIGZhY3Rvcml6ZQpmb3IgKG4gaW4gZmFjcykgewogIGRhdGFbW25dXSA8LSBmYWN0b3IoZGF0YVtbbl1dKQp9CgpoZWFkKGRhdGEpCgpzYXZlKGRhdGEsIGZpbGUgPSAiL1VzZXJzL2N1ZWxhbmQvR29vZ2xlIERyaXZlL1NjaG9vbC82NzAgLSBEYXRhIFNjaWVuY2UvZGl2b3JjZS1wcmVkaWN0aW9uL2RhdGEuUkRhdGEiLCBjb21wcmVzcyA9IFRSVUUpCmBgYAojIyMgUnVuIERlY2lzaW9uIFRyZWUKCkZpcnN0IHdlIGRpdmlkZSB0aGUgZGF0YSByYW5kb21seSBpbnRvIDIgc2VwYXJhdGUgcGFydHMsIHRyYWluIGFuZCB0ZXN0LCB3aXRoIGFuIGFwcHJveGltYXRlIDcwLzMwIHNwbGl0LiBGcm9tIHRoZXJlLCB3ZSB0cmFpbiB0aGUgZGVjaXNpb24gdHJlZSBtb2RlbCB1c2luZyBhIHNlbGVjdGVkIHNldCBvZiB2YXJpYWJsZXMgZnJvbSB0aGUgb3JpZ2luYWwgc2V0LiBUaGlzIHNldCBvZiB2YXJpYWJsZXMgd2FzIGNob3NlbiBmcm9tIG11bHRpcGxlIHRlc3RzIHdpdGggZGlmZmVyZW50IGNvbWJpbmF0aW9ucywgYXMgd2VsbCBhcyBjdWxsaW5nIGNlcnRhaW4gdmFyaWFibGVzIHRoYXQgYXJlIGV4cGxpY2l0bHkgcmVsYXRlZCB0byBtYXJyaWFnZSBzdGF0dXMuCmBgYHtyfQpsb2FkKCIvVXNlcnMvY3VlbGFuZC9Hb29nbGUgRHJpdmUvU2Nob29sLzY3MCAtIERhdGEgU2NpZW5jZS9kaXZvcmNlLXByZWRpY3Rpb24vZGF0YS5SRGF0YSIpCgojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIFRyYWluIGFuZCBUZXN0IC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS18CgojIFNldCB1cCBzdWJzZXQgdG8gcm91Z2hseSA3MCUKc2V0LnNlZWQoMTIzNDUpCnRyYWluIDwtIHJ1bmlmKG5yb3coZGF0YSkpCnRyYWluIDwtIHRyYWluID4gMC43CgojIENyZWF0ZSBzZXBhcmF0ZSB0cmFpbiBhbmQgdGVzdCBzZXRzCmRhdGEudHJhaW4gPC0gZGF0YVt0cmFpbiwgXQpoZWFkKGRhdGEudHJhaW5bMTo2XSkKZGF0YS50ZXN0IDwtIGRhdGFbIXRyYWluLCBdCmhlYWQoZGF0YS50ZXN0WzE6Nl0pCgojIFJ1biB0aGUgdGVzdCB3aXRoIHRoZSBiZXN0IHZhcmlhYmxlcyAoZGV0ZXJtaW5lZCBieSBwcmV2aW91cyBydW5zKQpwdCA8LSBwcm9jLnRpbWUoKVszXQpmaXQgPC0gcnBhcnQocGVtYXJpdGwgfiBwcnRhZ2UgKyBocm51bWhvdSArIHByY2hsZCArIHBybm1jaGxkICsgcGVtbHIgKyBwdXdrICsKICAgICAgICAgICAgICAgaGVmYW1pbmMgKyBwcnRmYWdlICsgcHJ3a3NjaCArIHByY2l2bGYgKyBwcndrc3RhdCArIHBlZWR1Y2EgKwogICAgICAgICAgICAgICBwdGR0cmFjZSArIHByaW51c3lyICsgcGVzZXggKyBndGluZHZwYyArIHByY2l0c2hwICsgaHVyZXNwbGkgKwogICAgICAgICAgICAgICBoZWhvdXN1dCArIGd0Y2JzYXN0ICsgcGVhZmV2ZXIgKyBwcm1qaW5kMSArIGd0Y2JzYXN6ICsgZ2VkaXYgKwogICAgICAgICAgICAgICBodXNwbmlzaCArIHBlaHNwbm9uICsgcGVubGZhY3QgKyBndG1ldHN0YSArIHBlYWZub3cgKyBnZXJlZyArCiAgICAgICAgICAgICAgIHBybWpvY2MxICsgcHJmdGxmICsgcGVkaXNlYXIgKyBodWJ1cyArIHBlZGlzcmVtLAogICAgICAgICAgICAgbWV0aG9kID0gImNsYXNzIiwgZGF0YSA9IGRhdGEudHJhaW4sIGNwID0gMCkKcHJvYy50aW1lKClbM10gLSBwdAoKIyBkZXRlcm1pbmUgd2hpY2ggdmFyaWFibGVzIHdlcmUgdGhlIG1vc3QgdXNlZnVsCnVzZWZ1bC52YXJzIDwtIGRhdGEuZnJhbWUobmFtZSA9IGF0dHIoZml0JHZhcmlhYmxlLmltcG9ydGFuY2UsICJuYW1lcyIpLAogICAgICAgICAgICAgICAgICAgICAgICAgIGltcG9ydGFuY2UgPSBmaXQkdmFyaWFibGUuaW1wb3J0YW5jZSwKICAgICAgICAgICAgICAgICAgICAgICAgICByb3cubmFtZXMgPSBOVUxMKQp1c2VmdWwudmFycwojIHByaW50Y3AoZml0KQoKIyBiYWNrdXAgdGhlIGZpbGUKc2F2ZShmaXQsIGZpbGUgPSAiZml0LlJEYXRhIiwgY29tcHJlc3MgPSBUUlVFKQpzYXZlKGRhdGEsIGRhdGEudGVzdCwgZGF0YS50cmFpbiwgZmlsZSA9ICJkYXRhX2NvbXBsZXRlLlJEYXRhIiwgY29tcHJlc3MgPSBUUlVFKQpgYGAKIyMjIE9wdGltaXphdGlvbgpCZWNhdXNlIHdlIHJhbiB0aGUgbW9kZWwgd2l0aCBDUCA9IDAgKHRoZSBtb3N0IGNvbXBsZXgpLCB3ZSBjYW4gc3Vic2VxdWVudGx5IHNpbXBsaWZ5LCBvciAicHJ1bmUiLCB0aGUgZGVjaXNpb24gdHJlZSBtb2RlbCBpbiBvcmRlciB0byBhdm9pZCBvdmVyLWZpdHRpbmcgdGhlIG1vZGVsIHRvIHRoZSB0cmFpbiBkYXRhLiBXZSB1c2UgdHdvIGFwcHJvYWNoZXMgZm9yIHRoaXMuIAoKIyMjIyBYRVJST1IKRmlyc3QsIHdlIGV4YW1pbmUgdGhlIFhFUlJPUiBvZiBlYWNoIGxldmVsIG9mIGNvbXBsZXhpdHkgYW5kIHBydW5lIHRvIHRoZSBsZXZlbCB0aGF0IG9mZmVycyB0aGUgbG93ZXJzIFhFUlJPUiB2YWx1ZS4KYGBge3J9CiMgbG9hZCgiZml0LlJEYXRhIikKIyBsb2FkKCJkYXRhX2NvbXBsZXRlLlJEYXRhIikKCiMgVGVzdCB0aGUgcHJlZGljdGlvbnMgZm9yIHRoZSB0cmFpbiBzdWJzZXQgKHRoaXMgaXMgYXJndWFibHkgdW5lY2Nlc3NhcnkpCmRhdGEudHJhaW4kcHJlZGljdCA8LSBwcmVkaWN0KGZpdCwgZGF0YS50cmFpbiwgdHlwZT0gImNsYXNzIikKbWVhbmYxKGRhdGEudHJhaW4kcHJlZGljdCwgZGF0YS50cmFpbiRwZW1hcml0bCkKCiMgVGVzdCB0aGUgcHJlZGljdGlvbnMgZm9yIHRoZSB0ZXN0IHN1YnNldCBmb3IgQ1AgPSAwCmRhdGEudGVzdCRwcmVkaWN0IDwtIHByZWRpY3QoZml0LCBkYXRhLnRlc3QsIHR5cGU9ICJjbGFzcyIpCm1lYW5mMShkYXRhLnRlc3QkcHJlZGljdCwgZGF0YS50ZXN0JHBlbWFyaXRsKQoKIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gbWluIFhFUlJPUiAobWluY3ApIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLXwKIyBkZXRlcm1pbmUgdGhlIENQIHRoYXQgeWllbGRzIHRoZSBtaW5pbXVtIFhFUlJPUiB2YWx1ZSAKbWluY3AgPC0gZml0JGNwdGFibGVbZml0JGNwdGFibGVbLCA0XSA9PSBtaW4oZml0JGNwdGFibGVbLCA0XSksIDFdCmlmIChsZW5ndGgobWluY3ApID4gMSkgewogIGZpdCRjcHRhYmxlW2ZpdCRjcHRhYmxlWywgNF0gPT0gbWluKGZpdCRjcHRhYmxlWywgNF0pLCBdCiAgbWluY3AgPC0gbWluY3BbMV0KfQoKIyBwcnVuZSB0byB0aGUgQ1AgdGhhdCB5aWVsZGVkIHRoZSBtaW4gWEVSUk9SIHZhbHVlLCBtaW5jcApmaXQubWluY3AgPC0gcHJ1bmUoZml0LCBjcCA9IG1pbmNwKQoKIyBUZXN0IHRoZSBwcmVkaWN0aW9ucyBmb3IgdGhlIHRlc3Qgc3Vic2V0IGZvciBDUCA9IG1pbmNwCmRhdGEudGVzdCRwcmVkaWN0Lm1pbmNwIDwtIHByZWRpY3QoZml0Lm1pbmNwLCBkYXRhLnRlc3QsIHR5cGU9ICJjbGFzcyIpCm1lYW5mMShkYXRhLnRlc3QkcHJlZGljdC5taW5jcCwgZGF0YS50ZXN0JHBlbWFyaXRsKQpgYGAKIyMjIyBJdGVyYXRpb24KU2Vjb25kLCB3ZSB1c2UgYW4gaXRlcmF0aXZlIGFwcHJvYWNoIHRvIGRldGVybWluZSB3aGljaCBsZXZlbCBvZiBwcnVuaW5nIHlpZWxkcyB0aGUgaGlnaGVzdCBtZWFuIEYxLCB3aGljaCBpcyBvdXIgbWVhc3VyZSBvZiBiZXN0IGZpdC4gVGhpcyBpcyBkb25lIHdpdGggYSBzZXJpZXMgb2YgdHdvIGxvb3BzLCB0aGUgZmlyc3QgdG8gZmluZCBhIHJvdWdoIGVzdGltYXRlIG9mIHRoZSBiZXN0IENQIHZhbHVlLCBhbmQgdGhlIHNlY29uZCB0byBmdXJ0aGVyIHJlZmluZSB0aGUgQ1AgdmFsdWUuIFRoaXMgeWllbGRzIGEgbWVhbiBGMSBzY29yZSBmb3IgdGhlIHRlc3Qgc3Vic2V0IG9mIDAuODEyLgpgYGB7cn0KIyAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0gTWF4IEYxIGZvciB0ZXN0IHN1YnNldCAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLXwKCiMgdHJ5IHBydW5pbmcgd2l0aCBkaWZmZXJlbnQgQ1AgdmFsdWVzIHRvIGZpbmQgbWF4aW1hbCBtZWFuIEYxIG9uIHRoZSB0ZXN0IHNldApjcDEgPC0gMC4xCmYxcyA8LSB2ZWN0b3IobGVuZ3RoID0gMCkKY3AudmVjdG9yIDwtIGNwMQoKIyBSb3VnaCBwcmVsaW1pbmFyeSBpdGVyYXRpb24KIyBpdGVyYXRlIGZyb20gMC4xIHRvIDFlLTEzIGZpbmRpbmcgRjEgc2NvcmVzCndoaWxlIChjcDEgPiAwLjAwMDAwMDAwMDAwMDEpIHsKICBmaXQuYmVzdCA8LSBwcnVuZShmaXQsIGNwID0gY3AxKQogIGRhdGEudGVzdCRwcmVkaWN0LmJlc3QgPC0gcHJlZGljdChmaXQuYmVzdCwgZGF0YS50ZXN0LCB0eXBlPSAiY2xhc3MiKQogIGYxcyA8LSBjKGYxcywgbWVhbmYxKGRhdGEudGVzdCRwcmVkaWN0LmJlc3QsIGRhdGEudGVzdCRwZW1hcml0bCkpCiAgY3AxIDwtIGNwMSAvIDUgIyBuZXcgQ1AgaXMgb2xkIENQIGRpdmlkZWQgYnkgNQogIGNwLnZlY3RvciA8LSBjKGNwLnZlY3RvciwgY3AxKQp9CgojIGZpbmQgbWF4IG1lYW4gRjEgYW5kIGNvcnJlc3BvbmRpbmcgYmVmb3JlIGFuZCBhZnRlciB2YWx1ZXMgZm9yIGZ1cnRoZXIgaXRlcmF0aW9uCm1heC5mMSA8LSAoMTpsZW5ndGgoZjFzKSlbZjFzID09IG1heChmMXMpXSAjIGZpbmQgaW5kZXggb2YgbWF4IHZhbHVlCm5leHQuaXQgPC0gY3AudmVjdG9yW2MobWF4LmYxIC0gMSwgbWF4LmYxICsgMSldICMgZmluZCBiZWZvcmUgYW5kIGFmdGVyIENQIHZhbHVlcwoKIyBSZWZpbmVkIHNlY29uZGFyeSBpdGVyYXRpb24KZjFzIDwtIHZlY3RvcihsZW5ndGggPSAwKQpmb3IgKGNwMSBpbiBpbnRlcihuZXh0Lml0WzFdLG5leHQuaXRbMl0sIDEwKSkgeyAjIHNlZSBpbnRlciBmdW5jdGlvbiBhYm92ZQogIGZpdC5iZXN0IDwtIHBydW5lKGZpdCwgY3AgPSBjcDEpCiAgZGF0YS50ZXN0JHByZWRpY3QuYmVzdCA8LSBwcmVkaWN0KGZpdC5iZXN0LCBkYXRhLnRlc3QsIHR5cGU9ICJjbGFzcyIpCiAgZjFzIDwtIGMoZjFzLCBtZWFuZjEoZGF0YS50ZXN0JHByZWRpY3QuYmVzdCwgZGF0YS50ZXN0JHBlbWFyaXRsKSkKfQoKIyBjcmVhdGUgZGF0YSBmcmFtZSB3aXRoIHJlc3VsdHMgdG8gc2VlIGhvdyBvcHRpbWl6YXRpb24gd29ya2VkCmYxcy5yZWZpbmVkIDwtIGRhdGEuZnJhbWUoQ1AgPSByZXYoaW50ZXIobmV4dC5pdFsxXSxuZXh0Lml0WzJdLCAxMCkpLAogICAgICAgICAgICAgICAgICAgICAgICAgIG1lYW5fRjEgPSByZXYoZjFzKSkKZjFzLnJlZmluZWQKcGxvdChmMXMucmVmaW5lZCkgICMgcGxvdCBvcHRpbWl6YXRpb24KIyBhc3NpZ24gYmVzdCBDUCB2YWx1ZQpjcC5iZXN0IDwtIGYxcy5yZWZpbmVkWywxXVtmMXMucmVmaW5lZFssMl0gPT0gbWF4KGYxcy5yZWZpbmVkWywyXSldCiMgZmluZCBvcHRpbWFsIGZpdApmaXQuYmVzdCA8LSBwcnVuZShmaXQsIGNwID0gY3AuYmVzdCkKdXNlZnVsLnZhcnMuYmVzdCA8LSBkYXRhLmZyYW1lKG5hbWUgPSBhdHRyKGZpdC5iZXN0JHZhcmlhYmxlLmltcG9ydGFuY2UsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAibmFtZXMiKSwKICAgICAgICAgICAgICAgICAgICAgICAgICBpbXBvcnRhbmNlID0gZml0LmJlc3QkdmFyaWFibGUuaW1wb3J0YW5jZSwKICAgICAgICAgICAgICAgICAgICAgICAgICByb3cubmFtZXMgPSBOVUxMKQp1c2VmdWwudmFycy5iZXN0CiMgU2hvdyBmdXJ0aGVyIHNpbXBsaWZpZWQgZGVjaXNpb24gdHJlZSBncmFwaGljCmZpdC5zaW1wbGUgPC0gcHJ1bmUoZml0LCBjcCA9IDAuMDA1KQpycGFydC5wbG90KGZpdC5zaW1wbGUsIHNoYWRvdy5jb2wgPSAiZ3JleSIsIG5uID0gVFJVRSkKCiMgVGVzdCB0aGUgcHJlZGljdGlvbnMgZm9yIHRoZSB0ZXN0IHN1YnNldCBmb3IgQ1AgPSBtaW5jcApkYXRhLnRlc3QkcHJlZGljdC5iZXN0IDwtIHByZWRpY3QoZml0LmJlc3QsIGRhdGEudGVzdCwgdHlwZT0gImNsYXNzIikKbWVhbmYxKGRhdGEudGVzdCRwcmVkaWN0LmJlc3QsIGRhdGEudGVzdCRwZW1hcml0bCkKYGBgCgo=