Discussion Points

When & Why

data.table is an extension of data.frame. Functions that work with data.frames should work with data.tables. While this isn’t entirely true (especially functions not included in base R), you can see that a data.table is a data.frame.

inherits(data.table(), 'data.frame')
[1] TRUE

So you can use it as much as you’d like. Primary though, you would use it for large data sets.

Cole’s rules of thumb for big data

  1. A CSV file > 500 MB is big. Use data.table::fread()
    • add the argument data.table = FALSE if you must
  2. If your data set is between 500 MB and 8 GB, use data.table
  3. If your data set is over 8 GB, store it in a database (such as sqlite or mysql) and use an ODBC package
  4. If your code will run on a server, you may have more than 32 GB ram. While this changes the equation and gives added flexibility, I would stick with my suggestions.
  5. If other people will use your code, write code that supports both.

How to learn more

From the web: data.table vignettes

From R:

browseVignettes('data.table')

From YouTube:

Cole’s data.table lecture on YouTube

  • set quality to 1080p (HD)
  • enjoy other favorites on Cole’s award-winning mediocre Statistical Computing play list

Basic functionality

Create three data sets

head(incident)
head(demo)
head(events_wide)

From df to dt and back

class(incident)
[1] "data.table" "data.frame"
class(incident) <- 'data.frame'
class(incident)
[1] "data.frame"
setDT(incident)
class(incident)
[1] "data.table" "data.frame"
# inc <- as.data.table(incident)

Merging

data.table::merge works much like base::merge

dat <- merge(incident, demo)
dat
rm(incident, demo)

Extracting/filtering (get) and assignment/removal (set)

Unlike data.frame, a comma (,) is not required to filter your data set.

dat[race == 'white']
dat[race == 'white'][age > 40] # example of "chaining"
dat[race == 'white' & age > 40, c('uid','age')]

data.table adds syntax for selecting/removing columns

dat[race == 'white' & age > 40, list(uid, age)]
dat[race == 'white' & age > 40, .(uid, age)]
dat[race == 'white' & age > 40, -c('uid', 'age')]
dat[race == 'white' & age > 40, !c('uid', 'age')]

In data.table, use := for assignment.

dat[, white40 := 0]
dat[race == 'white' & age > 40, white40 := 1]
dat[, birthYear := as.numeric(format(incident_date, '%Y')) - age]
dat

You can assign multiple columns in a single statement. Like data.frame, setting to NULL deletes the column.

dat[, `:=`(white40 = NULL, birthYear = NULL)]
dat

Assignment within a for loop

This example comes from the documentation on set - it’s worth a read.

m = matrix(1, nrow = 2e6L, ncol = 100L)
DF = as.data.frame(m)
DT = as.data.table(m)
ix <- seq(1000)

# set the 1st column for the first thousand rows
system.time(for(i in ix) DF[i, 1] = i)
   user  system elapsed 
  1.655   0.704   2.360 
system.time(for(i in ix) DT[i, V1 := i])
   user  system elapsed 
  0.728   0.000   0.246 
# use `set`, avoids overhead of `[.data.table`
system.time(for(i in ix) set(DT, i, 1L, i))
   user  system elapsed 
  0.003   0.000   0.003 

Aggregate functions

Examples of aggregate functions for data.frames include:

  • tapply
  • aggregate
  • lapply
  • do.call(rbind, lapply(split(…)))

data.table uses the by argument. Note the difference when using = or :=.

dat[, mean(age), by = race]
dat[, .(age = mean(age)), by = race]
dat[, grp_age := mean(age), by = race]
dat
dat[, mean(age), by = .(race, sex)][order(race, sex)]

data.table adds two special variables: .N and .SD. If you find these confusing, you don’t have to use them.

dat[, .N, by = sex]

.SD (Subset of Data) is self-referential (to your data set); restrict it using the .SDcols argument.

lu <- function(x) length(unique(x)) # count of unique values
dat[, sapply(.SD, lu)] # all columns
          uid incident_date           age          race           sex       grp_age 
           10            20             8             2             3             2 
dat[, sapply(.SD, lu), .SDcols = c('race', 'sex')]
race  sex 
   2    3 
dat[, sapply(.SD, lu), .SDcols = age:sex] # range of columns
 age race  sex 
   8    2    3 
dat[, sapply(.SD, lu), .SDcols = -c('age')] # exclude age
          uid incident_date          race           sex       grp_age 
           10            20             2             3             2 

Re-shaping

Instead of reshape, data.table has melt and dcast. The reshape package also has a melt function. It’s good practice to specify the package like data.table::melt.

Wide to long (melt)

The events_wide data set has multiple sets of columns we want to reshape. Typically we would only need one melt statement, but in its case we need two.

You can specify both measure.vars and id.vars but you probably only need one or the other. Using patterns can be extremely helpful.

Remember to include na.rm or not. It’s usually okay to leave variable.factor = TRUE as the default.

events_wide
t1 <- data.table::melt(events_wide,
  measure.vars = patterns('^visit', '^lab', '^surgery', '^rxfill'),
  variable.name = 'obs',
  value.name = c('visit','lab','surgery','rxfill'),
  variable.factor = FALSE
)
t1
events_long <- data.table::melt(t1,
  id.vars = c('uid', 'obs'),
  variable.name = 'event_type',
  value.name = 'event_date',
  na.rm = TRUE,
  variable.factor = FALSE
)[order(uid, event_type, obs)]
events_long

Here’s an alternative that uses the tstrsplit function.

alt_long <- data.table::melt(events_wide,
  id.vars = 'uid',
  value.name = 'event_date',
  na.rm = TRUE
)
alt_long
alt_long[, c('event_type', 'obs') := tstrsplit(variable, '_')]
alt_long[, variable := NULL][order(uid, event_type, obs)]

Long to wide (dcast)

dcast uses a formula-like expression.

dcast(events_long, uid ~ event_type + obs, value.var = 'event_date')

Column names

Use the setnames function

names(t1)
[1] "uid"     "obs"     "visit"   "lab"     "surgery" "rxfill" 
setnames(t1, paste0('x', seq(ncol(t1)))) # set all columns
setnames(t1, 'x1', 'userid') # set old column to new value
setnames(t1, -1, paste0('y_', seq(2, ncol(t1)))) # set except 1
names(t1)
[1] "userid" "y_2"    "y_3"    "y_4"    "y_5"    "y_6"   
rm(t1)

Expanded functionality

We’ve already seen .N and .SD. Let’s use keys, and the informative tables function.

tables()
          NAME      NROW NCOL    MB                                            COLS KEY
1:    alt_long       157    4     0                   uid,event_date,event_type,obs    
2:         dat        20    6     0          uid,incident_date,age,race,sex,grp_age uid
3:          DT 2,000,000  100 1,526                           V1,V2,V3,V4,V5,V6,...    
4: events_long       157    4     0                   uid,obs,event_type,event_date    
5: events_wide        10   28     0 uid,visit_1,visit_2,visit_3,visit_4,visit_5,... uid
Total: 1,526MB
setkey(dat, uid, incident_date)
setkey(events_long, uid)
tables()
          NAME      NROW NCOL    MB                                            COLS               KEY
1:    alt_long       157    4     0                   uid,event_date,event_type,obs                  
2:         dat        20    6     0          uid,incident_date,age,race,sex,grp_age uid,incident_date
3:          DT 2,000,000  100 1,526                           V1,V2,V3,V4,V5,V6,...                  
4: events_long       157    4     0                   uid,obs,event_type,event_date               uid
5: events_wide        10   28     0 uid,visit_1,visit_2,visit_3,visit_4,visit_5,...               uid
Total: 1,526MB

Searching a data.table with keys is fast and efficient. As a side-effect, your data set will be re-ordered by its keys.

Here’s an example of filtering without keys

dat[uid == 5]
dat[uid == 5 & incident_date == as.Date('2017-11-29')]

and with keys

dat[.(5)]
dat[.(5, as.Date('2017-11-29'))]
dat[.(5), mult = 'first']
dat[.(c(1:3))]

If your table has multiple keys, it’s a little tricky to search if you want to ignore the first key. Both of these fail.

tryCatch(dat[.(, as.Date('2017-11-29'))], error = function(e) e)
<simpleError: argument 1 is empty>
dat[.(unique(uid), as.Date('2017-11-29'))]

You may need the nomatch argument.

dat[.(unique(uid), as.Date('2017-11-29')), nomatch = NULL]

Expecting the unexpected

Unexpected behavior in data.table often occurs when we write our own functions. Two big sources of problems come from non-standard evaluation (NSE) and pass-by-reference.

NSE is the thing that lets us avoid typing out the full reference to columns occurring within our data set. For example, don’t you hate typing df[order(df[,'uid']),] when you could just type df[order(uid)]? This becomes a problem when you have column names stored within variables.

You can use setkeyv instead of setkey

keycols <- c('uid', 'event_date')
tryCatch(setkey(alt_long, keycols), error = function(e) e)
<simpleError in setkeyv(x, cols, verbose = verbose, physical = physical): some columns are not in the data.table: keycols>
setkeyv(alt_long, keycols)

And add the with = FALSE argument when extracting

tryCatch(alt_long[, keycols], error = function(e) e)
<simpleError in `[.data.table`(alt_long, , keycols): j (the 2nd argument inside [...]) is a single symbol but column name 'keycols' is not found. Perhaps you intended DT[, ..keycols]. This difference to data.frame is deliberate and explained in FAQ 1.1.>
alt_long[, ..keycols]
alt_long[, keycols, with = FALSE]

In R when you pass an object to a function, a copy of that object is made. pass-by-reference is used to pass the object itself (by its memory address), which is much more efficient (and dangerous). We’ll look at an example by creating a function to calculate great circle distance with the Haversine formula.

haversine <- function(dt) {
  # decimal degrees to radians
  dtnames <- names(dt)
  print(dtnames)
  dt[,rLat := lat * pi / 180]
  dt[,rLong := long * pi / 180]
  dd <- dt[,outer(rLat,rLat,`-`)]
  dl <- dt[,outer(rLong,rLong,`-`)]
  allLat <- t(replicate(nrow(dt), dt[,rLat]))
  a <- sin(dd/2)^2 + cos(allLat) * cos(dt[,rLat]) * sin(dl/2)^2
  d <- 2 * 6371000 * asin(sqrt(a))
  print(dtnames)
  d
}
qdt <- as.data.table(quakes)
ans <- haversine(qdt)
[1] "lat"      "long"     "depth"    "mag"      "stations"
[1] "lat"      "long"     "depth"    "mag"      "stations" "rLat"     "rLong"   
names(qdt)
[1] "lat"      "long"     "depth"    "mag"      "stations" "rLat"     "rLong"   

We actually have two problems. Note that our original data set qdt has been updated. This wasn’t really our intention, though it may not actually hurt us. We also see that our variable of column names has been modified. That’s because data.table made a shallow copy of our column names. This means it points to the original and is not a distinct copy. To make a distinct, or deep copy, use the copy function.

haversine <- function(dt) {
  dt <- copy(dt)
  # decimal degrees to radians
  dtnames <- copy(names(dt))
  print(dtnames)
  dt[,rLat := lat * pi / 180]
  dt[,rLong := long * pi / 180]
  dd <- dt[,outer(rLat,rLat,`-`)]
  dl <- dt[,outer(rLong,rLong,`-`)]
  allLat <- t(replicate(nrow(dt), dt[,rLat]))
  a <- sin(dd/2)^2 + cos(allLat) * cos(dt[,rLat]) * sin(dl/2)^2
  d <- 2 * 6371000 * asin(sqrt(a))
  print(dtnames)
  d
}
qdt <- as.data.table(quakes)
ans <- haversine(qdt)
[1] "lat"      "long"     "depth"    "mag"      "stations"
[1] "lat"      "long"     "depth"    "mag"      "stations"
names(qdt)
[1] "lat"      "long"     "depth"    "mag"      "stations"

Let’s update our function to include arguments for the latitude and longitude columns… which doesn’t work.

haversine <- function(dt, latCol, longCol) {
  dt <- copy(dt)
  # decimal degrees to radians
  dtnames <- copy(names(dt))
  print(dtnames)
  dt[,rLat := latCol * pi / 180]
  dt[,rLong := longCol * pi / 180]
  dd <- dt[,outer(rLat,rLat,`-`)]
  dl <- dt[,outer(rLong,rLong,`-`)]
  allLat <- t(replicate(nrow(dt), dt[,rLat]))
  a <- sin(dd/2)^2 + cos(allLat) * cos(dt[,rLat]) * sin(dl/2)^2
  d <- 2 * 6371000 * asin(sqrt(a))
  print(dtnames)
  d
}
tryCatch(ans <- haversine(qdt, 'lat', 'long'), error = function(e) e)
[1] "lat"      "long"     "depth"    "mag"      "stations"
<simpleError in latCol * pi: non-numeric argument to binary operator>

In this case, we can use the get function.

haversine <- function(dt, latCol, longCol) {
  dt <- copy(dt)
  # decimal degrees to radians
  dtnames <- copy(names(dt))
  print(dtnames)
  dt[,rLat := get(latCol) * pi / 180]
  dt[,rLong := get(longCol) * pi / 180]
  dd <- dt[,outer(rLat,rLat,`-`)]
  dl <- dt[,outer(rLong,rLong,`-`)]
  allLat <- t(replicate(nrow(dt), dt[,rLat]))
  a <- sin(dd/2)^2 + cos(allLat) * cos(dt[,rLat]) * sin(dl/2)^2
  d <- 2 * 6371000 * asin(sqrt(a))
  print(dtnames)
  d
}
ans <- haversine(qdt, 'lat', 'long')
[1] "lat"      "long"     "depth"    "mag"      "stations"
[1] "lat"      "long"     "depth"    "mag"      "stations"

What if we want to use these arguments without quotes?

It gets ugly but we can add deparse and substitute.

haversine <- function(dt, latCol, longCol) {
  dt <- copy(dt)
  # decimal degrees to radians
  dtnames <- copy(names(dt))
  print(dtnames)
  c1 <- deparse(substitute(latCol))
  c2 <- deparse(substitute(longCol))
  dt[,rLat := get(c1) * pi / 180]
  dt[,rLong := get(c2) * pi / 180]
  dd <- dt[,outer(rLat,rLat,`-`)]
  dl <- dt[,outer(rLong,rLong,`-`)]
  allLat <- t(replicate(nrow(dt), dt[,rLat]))
  a <- sin(dd/2)^2 + cos(allLat) * cos(dt[,rLat]) * sin(dl/2)^2
  d <- 2 * 6371000 * asin(sqrt(a))
  print(dtnames)
  d
}
ans <- haversine(qdt, lat, long)
[1] "lat"      "long"     "depth"    "mag"      "stations"
[1] "lat"      "long"     "depth"    "mag"      "stations"

Code supporting both data.frame and data.table

This function prints counts for the unique values within a column. Both data.frame and data.table can access a column with double-brackets.

counts <- function(dat, col) {
  table(dat[[col]])
}

This function converts a list to a data.frame or data.table. It will choose the right path depending on if the package is installed.

l2df <- function(l, keepDT = FALSE) {
  if(requireNamespace("data.table", quietly = TRUE)) {
    x <- data.table::rbindlist(l)
    if(!keepDT) x <- as.data.frame(x)
  } else {
    x <- do.call(rbind, c(l, make.row.names = FALSE))
  }
  x
}

A final example

Let’s revisit the dat and events_long data sets. We may want to write a function to merge incident dates with event dates. We might want to keep the closest event, or even restrict it to within some number of days.

We introduce two new things, the allow.cartesian argument within brackets and the by argument within unique. Additionally, x[y] works like a merge (merge(x, y, all.y=TRUE) or right outer join) using each data sets’ keys (uid in our case).

datediff <- function(a, b) as.numeric(a - b)

mergeByMostRecent <- function(x, y, nDays = NULL) {
  z <- x[y, allow.cartesian = TRUE]
  z <- z[event_date <= incident_date]
  z[, dd := datediff(incident_date, event_date)]
  if(!is.null(nDays)) {
    z <- z[dd < nDays]
  }
  z <- z[order(uid, incident_date, dd)]
  z[, dd := NULL]
  unique(z, by = c('uid', 'incident_date'))
}

Merge incident with closest prior event.

mergeByMostRecent(dat, events_long)

Merge incident with closest prior event within 30 days.

mergeByMostRecent(dat, events_long, 30)

Merge incident with closest prior lab event.

mergeByMostRecent(dat, events_long[event_type == 'lab'])
sessionInfo()
R version 4.0.2 (2020-06-22)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 18.04.5 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/blas/libblas.so.3.7.1
LAPACK: /usr/lib/x86_64-linux-gnu/lapack/liblapack.so.3.7.1

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C               LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8    LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C             LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] grid      stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] png_0.1-7         data.table_1.12.8

loaded via a namespace (and not attached):
[1] compiler_4.0.2 tools_4.0.2    knitr_1.28     xfun_0.13     
LS0tCnRpdGxlOiAiSW50cm9kdWN0aW9uIHRvIGRhdGEudGFibGUiCmF1dGhvcjogQ29sZSBCZWNrCmRhdGU6ICcyMDIxLTA0LTMwJwpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKZWRpdG9yX29wdGlvbnM6IAogIGNodW5rX291dHB1dF90eXBlOiBpbmxpbmUKLS0tCgpgYGB7ciBjb25maWcsIGluY2x1ZGUgPSBGQUxTRX0KbGlicmFyeShkYXRhLnRhYmxlKQpsaWJyYXJ5KHBuZykKbGlicmFyeShncmlkKQpgYGAKCiMgRGlzY3Vzc2lvbiBQb2ludHMKCiogd2hlbiB0byB1c2UgZGF0YS50YWJsZQoqIGJhc2ljIGRhdGEuZnJhbWUgLyBkYXRhLnRhYmxlIGZ1bmN0aW9uYWxpdHkKICAqIGV4dHJhY3Rpb24gYW5kIGFzc2lnbm1lbnQKICAqIG1lcmdlIGFuZCByZXNoYXBpbmcKICAqIGFnZ3JlZ2F0ZSBmdW5jdGlvbnMKKiBuZXcgZnVuY3Rpb25hbGl0eQogICoga2V5cywgLk4sIC5TRAoqIHVuZXhwZWN0ZWQgYmVoYXZpb3IKKiBmaW5hbCBleGFtcGxlCgojIFdoZW4gJiBXaHkKCmRhdGEudGFibGUgaXMgYW4gZXh0ZW5zaW9uIG9mIGRhdGEuZnJhbWUuIEZ1bmN0aW9ucyB0aGF0IHdvcmsgd2l0aCBkYXRhLmZyYW1lcyBfc2hvdWxkXyB3b3JrIHdpdGggZGF0YS50YWJsZXMuIFdoaWxlIHRoaXMgaXNuJ3QgZW50aXJlbHkgdHJ1ZSAoZXNwZWNpYWxseSBmdW5jdGlvbnMgbm90IGluY2x1ZGVkIGluIGJhc2UgUiksIHlvdSBjYW4gc2VlIHRoYXQgYSBkYXRhLnRhYmxlIGlzIGEgZGF0YS5mcmFtZS4KCmBgYHtyfQppbmhlcml0cyhkYXRhLnRhYmxlKCksICdkYXRhLmZyYW1lJykKYGBgCgpTbyB5b3UgY2FuIHVzZSBpdCBhcyBtdWNoIGFzIHlvdSdkIGxpa2UuIFByaW1hcnkgdGhvdWdoLCB5b3Ugd291bGQgdXNlIGl0IGZvciBsYXJnZSBkYXRhIHNldHMuCgojIyBDb2xlJ3MgcnVsZXMgb2YgdGh1bWIgZm9yIGJpZyBkYXRhCgogIDEuIEEgQ1NWIGZpbGUgPiA1MDAgTUIgaXMgYmlnLiBVc2UgYGRhdGEudGFibGU6OmZyZWFkKClgCiAgICAgICogYWRkIHRoZSBhcmd1bWVudCBgZGF0YS50YWJsZSA9IEZBTFNFYCBpZiB5b3UgbXVzdAogIDEuIElmIHlvdXIgZGF0YSBzZXQgaXMgYmV0d2VlbiA1MDAgTUIgYW5kIDggR0IsIHVzZSBkYXRhLnRhYmxlCiAgMS4gSWYgeW91ciBkYXRhIHNldCBpcyBvdmVyIDggR0IsIHN0b3JlIGl0IGluIGEgZGF0YWJhc2UgKHN1Y2ggYXMgc3FsaXRlIG9yIG15c3FsKSBhbmQgdXNlIGFuIE9EQkMgcGFja2FnZQogIDEuIElmIHlvdXIgY29kZSB3aWxsIHJ1biBvbiBhIHNlcnZlciwgeW91IG1heSBoYXZlIG1vcmUgdGhhbiAzMiBHQiByYW0uIFdoaWxlIHRoaXMgY2hhbmdlcyB0aGUgZXF1YXRpb24gYW5kIGdpdmVzIGFkZGVkIGZsZXhpYmlsaXR5LCBJIHdvdWxkIHN0aWNrIHdpdGggbXkgc3VnZ2VzdGlvbnMuCiAgMS4gSWYgb3RoZXIgcGVvcGxlIHdpbGwgdXNlIHlvdXIgY29kZSwgd3JpdGUgY29kZSB0aGF0IHN1cHBvcnRzIGJvdGguCgpgYGB7ciwgZWNobyA9IEZBTFNFfQppMSA9IHJlYWRQTkcoJ2ltZzEucG5nJykKaTIgPSByZWFkUE5HKCdpbWcyLnBuZycpCmkzID0gcmVhZFBORygnaW1nMy5wbmcnKQpwbG90KE5VTEwsIHhsaW0gPSBjKDAsIDMpLCB5bGltID0gYygwLCAxKSwgeGxhYiA9ICcnLCB5bGFiID0gJycsIGF4ZXMgPSBGQUxTRSwgdHlwZSA9ICduJywgeGF4cyA9ICdpJywgeWF4cyA9ICdpJykKYXhpcygxLCBjKDEsIDIpLCBjKCc1MDAgTUInLCAnOCBHQicpKQpsaW5lcyhjKDEsIDEpLCBjKDAsMSkpCmxpbmVzKGMoMiwgMiksIGMoMCwxKSkKdGV4dCgwLjUsIDAuOCwgImRhdGEuZnJhbWUiKQp0ZXh0KDEuNSwgMC44LCAiZGF0YS50YWJsZSIpCnRleHQoMi41LCAwLjgsICJkYXRhYmFzZSIpCmJveCgpCmdyaWQucmFzdGVyKGkxLCB4ID0gMC4yNSwgeSA9IDAuMywgd2lkdGggPSAwLjE1LCBqdXN0ID0gYygnY2VudGVyJywnYm90dG9tJykpCmdyaWQucmFzdGVyKGkyLCB4ID0gMC41MjUsIHkgPSAwLjMsIHdpZHRoID0gMC4yLCBqdXN0ID0gYygnY2VudGVyJywnYm90dG9tJykpCmdyaWQucmFzdGVyKGkzLCB4ID0gMC44LCB5ID0gMC4zLCB3aWR0aCA9IDAuMjUsIGp1c3QgPSBjKCdjZW50ZXInLCdib3R0b20nKSkKYGBgCgojIyBIb3cgdG8gbGVhcm4gbW9yZQoKRnJvbSB0aGUgd2ViOiBbZGF0YS50YWJsZSB2aWduZXR0ZXNdW3ZpZ25dCgpGcm9tIFI6CgpgYGB7ciwgZXZhbCA9IEZBTFNFfQpicm93c2VWaWduZXR0ZXMoJ2RhdGEudGFibGUnKQpgYGAKCkZyb20gWW91VHViZToKCltDb2xlJ3MgZGF0YS50YWJsZSBsZWN0dXJlIG9uIFlvdVR1YmVdW3l0XQoKKiBzZXQgcXVhbGl0eSB0byAxMDgwcCAoSEQpCiogZW5qb3kgb3RoZXIgZmF2b3JpdGVzIG9uIENvbGUncyB+fmF3YXJkLXdpbm5pbmd+fiBtZWRpb2NyZSBfU3RhdGlzdGljYWwgQ29tcHV0aW5nXyBwbGF5IGxpc3QKCiMgQmFzaWMgZnVuY3Rpb25hbGl0eQoKYGBge3IgbWFrZWRhdGEsIGVjaG8gPSBGQUxTRX0Kc291cmNlKCdtYWtlRGF0YS5SJykKdG1wIDwtIG1ha2VEYXRhKCkKaW5jaWRlbnQgPC0gdG1wW1sxXV0KZGVtbyA8LSB0bXBbWzJdXQpldmVudHNfd2lkZSA8LSB0bXBbWzNdXQpgYGAKCkNyZWF0ZSB0aHJlZSBkYXRhIHNldHMKCiogaW5jaWRlbnQgLSAxMCB1c2VycyBlYWNoIHdpdGggMiBpbmNpZGVudCBkYXRlcwoqIGRlbW8gLSBkZW1vZ3JhcGhpYyBpbmZvIGZvciBlYWNoIHVzZXIKKiBldmVudHNfd2lkZSAtIHJlcGVhdGVkIG9ic2VydmF0aW9ucyAodmlzaXQvbGFiL3N1cmdlcnkvcnhmaWxsKSBmb3IgZWFjaCB1c2VyCgpgYGB7ciBzaG93ZGF0YX0KaGVhZChpbmNpZGVudCkKaGVhZChkZW1vKQpoZWFkKGV2ZW50c193aWRlKQpgYGAKCiMjIEZyb20gZGYgdG8gZHQgYW5kIGJhY2sKCmBgYHtyIHRvZGZ9CmNsYXNzKGluY2lkZW50KQpjbGFzcyhpbmNpZGVudCkgPC0gJ2RhdGEuZnJhbWUnCmNsYXNzKGluY2lkZW50KQpgYGAKCmBgYHtyIHRvZHR9CnNldERUKGluY2lkZW50KQpjbGFzcyhpbmNpZGVudCkKIyBpbmMgPC0gYXMuZGF0YS50YWJsZShpbmNpZGVudCkKYGBgCgojIyBNZXJnaW5nCgpgZGF0YS50YWJsZTo6bWVyZ2VgIHdvcmtzIG11Y2ggbGlrZSBgYmFzZTo6bWVyZ2VgCgpgYGB7ciBtZXJnZX0KZGF0IDwtIG1lcmdlKGluY2lkZW50LCBkZW1vKQpkYXQKcm0oaW5jaWRlbnQsIGRlbW8pCmBgYAoKIyMgRXh0cmFjdGluZy9maWx0ZXJpbmcgKGdldCkgYW5kIGFzc2lnbm1lbnQvcmVtb3ZhbCAoc2V0KQoKVW5saWtlIGBkYXRhLmZyYW1lYCwgYSBjb21tYSAoLCkgaXMgbm90IHJlcXVpcmVkIHRvIGZpbHRlciB5b3VyIGRhdGEgc2V0LgoKYGBge3IgZ2V0fQpkYXRbcmFjZSA9PSAnd2hpdGUnXQpkYXRbcmFjZSA9PSAnd2hpdGUnXVthZ2UgPiA0MF0gIyBleGFtcGxlIG9mICJjaGFpbmluZyIKZGF0W3JhY2UgPT0gJ3doaXRlJyAmIGFnZSA+IDQwLCBjKCd1aWQnLCdhZ2UnKV0KYGBgCgpgZGF0YS50YWJsZWAgYWRkcyBzeW50YXggZm9yIHNlbGVjdGluZy9yZW1vdmluZyBjb2x1bW5zCgpgYGB7ciBnZXRjb2x9CmRhdFtyYWNlID09ICd3aGl0ZScgJiBhZ2UgPiA0MCwgbGlzdCh1aWQsIGFnZSldCmRhdFtyYWNlID09ICd3aGl0ZScgJiBhZ2UgPiA0MCwgLih1aWQsIGFnZSldCmRhdFtyYWNlID09ICd3aGl0ZScgJiBhZ2UgPiA0MCwgLWMoJ3VpZCcsICdhZ2UnKV0KZGF0W3JhY2UgPT0gJ3doaXRlJyAmIGFnZSA+IDQwLCAhYygndWlkJywgJ2FnZScpXQpgYGAKCkluIGBkYXRhLnRhYmxlYCwgdXNlIGA6PWAgZm9yIGFzc2lnbm1lbnQuCgpgYGB7ciBzZXR9CmRhdFssIHdoaXRlNDAgOj0gMF0KZGF0W3JhY2UgPT0gJ3doaXRlJyAmIGFnZSA+IDQwLCB3aGl0ZTQwIDo9IDFdCmRhdFssIGJpcnRoWWVhciA6PSBhcy5udW1lcmljKGZvcm1hdChpbmNpZGVudF9kYXRlLCAnJVknKSkgLSBhZ2VdCmRhdApgYGAKCllvdSBjYW4gYXNzaWduIG11bHRpcGxlIGNvbHVtbnMgaW4gYSBzaW5nbGUgc3RhdGVtZW50LgpMaWtlIGBkYXRhLmZyYW1lYCwgc2V0dGluZyB0byAqTlVMTCogZGVsZXRlcyB0aGUgY29sdW1uLgoKYGBge3IgbXVsdGlzZXR9CmRhdFssIGA6PWAod2hpdGU0MCA9IE5VTEwsIGJpcnRoWWVhciA9IE5VTEwpXQpkYXQKYGBgCgojIyMgQXNzaWdubWVudCB3aXRoaW4gYSBmb3IgbG9vcAoKVGhpcyBleGFtcGxlIGNvbWVzIGZyb20gdGhlIGRvY3VtZW50YXRpb24gb24gYHNldGAgLSBpdCdzIHdvcnRoIGEgcmVhZC4KCmBgYHtyIGZvcmxvb3BzZXR9Cm0gPSBtYXRyaXgoMSwgbnJvdyA9IDJlNkwsIG5jb2wgPSAxMDBMKQpERiA9IGFzLmRhdGEuZnJhbWUobSkKRFQgPSBhcy5kYXRhLnRhYmxlKG0pCml4IDwtIHNlcSgxMDAwKQoKIyBzZXQgdGhlIDFzdCBjb2x1bW4gZm9yIHRoZSBmaXJzdCB0aG91c2FuZCByb3dzCnN5c3RlbS50aW1lKGZvcihpIGluIGl4KSBERltpLCAxXSA9IGkpCnN5c3RlbS50aW1lKGZvcihpIGluIGl4KSBEVFtpLCBWMSA6PSBpXSkKIyB1c2UgYHNldGAsIGF2b2lkcyBvdmVyaGVhZCBvZiBgWy5kYXRhLnRhYmxlYApzeXN0ZW0udGltZShmb3IoaSBpbiBpeCkgc2V0KERULCBpLCAxTCwgaSkpCmBgYAoKIyMgQWdncmVnYXRlIGZ1bmN0aW9ucwoKRXhhbXBsZXMgb2YgYWdncmVnYXRlIGZ1bmN0aW9ucyBmb3IgZGF0YS5mcmFtZXMgaW5jbHVkZToKCiogdGFwcGx5CiogYWdncmVnYXRlCiogbGFwcGx5CiogZG8uY2FsbChyYmluZCwgbGFwcGx5KHNwbGl0KC4uLikpKQoKYGRhdGEudGFibGVgIHVzZXMgdGhlIGBieWAgYXJndW1lbnQuIE5vdGUgdGhlIGRpZmZlcmVuY2Ugd2hlbiB1c2luZyBgPWAgb3IgYDo9YC4KCmBgYHtyIGFnZ3J9CmRhdFssIG1lYW4oYWdlKSwgYnkgPSByYWNlXQpkYXRbLCAuKGFnZSA9IG1lYW4oYWdlKSksIGJ5ID0gcmFjZV0KZGF0WywgZ3JwX2FnZSA6PSBtZWFuKGFnZSksIGJ5ID0gcmFjZV0KZGF0CmRhdFssIG1lYW4oYWdlKSwgYnkgPSAuKHJhY2UsIHNleCldW29yZGVyKHJhY2UsIHNleCldCmBgYAoKYGRhdGEudGFibGVgIGFkZHMgdHdvIHNwZWNpYWwgdmFyaWFibGVzOiAuTiBhbmQgLlNELiBJZiB5b3UgZmluZCB0aGVzZSBjb25mdXNpbmcsIHlvdSBkb24ndCBoYXZlIHRvIHVzZSB0aGVtLgoKYGBge3IgdXNlTn0KZGF0WywgLk4sIGJ5ID0gc2V4XQpgYGAKCmAuU0RgIChTdWJzZXQgb2YgRGF0YSkgaXMgc2VsZi1yZWZlcmVudGlhbCAodG8geW91ciBkYXRhIHNldCk7IHJlc3RyaWN0IGl0IHVzaW5nIHRoZSBgLlNEY29sc2AgYXJndW1lbnQuCgpgYGB7ciB1c2VTRH0KbHUgPC0gZnVuY3Rpb24oeCkgbGVuZ3RoKHVuaXF1ZSh4KSkgIyBjb3VudCBvZiB1bmlxdWUgdmFsdWVzCmRhdFssIHNhcHBseSguU0QsIGx1KV0gIyBhbGwgY29sdW1ucwpkYXRbLCBzYXBwbHkoLlNELCBsdSksIC5TRGNvbHMgPSBjKCdyYWNlJywgJ3NleCcpXQpkYXRbLCBzYXBwbHkoLlNELCBsdSksIC5TRGNvbHMgPSBhZ2U6c2V4XSAjIHJhbmdlIG9mIGNvbHVtbnMKZGF0Wywgc2FwcGx5KC5TRCwgbHUpLCAuU0Rjb2xzID0gLWMoJ2FnZScpXSAjIGV4Y2x1ZGUgYWdlCmBgYAoKIyMgUmUtc2hhcGluZwoKSW5zdGVhZCBvZiBgcmVzaGFwZWAsIGBkYXRhLnRhYmxlYCBoYXMgYG1lbHRgIGFuZCBgZGNhc3RgLiBUaGUgYHJlc2hhcGVgIHBhY2thZ2UgYWxzbyBoYXMgYSBgbWVsdGAgZnVuY3Rpb24uIEl0J3MgZ29vZCBwcmFjdGljZSB0byBzcGVjaWZ5IHRoZSBwYWNrYWdlIGxpa2UgYGRhdGEudGFibGU6Om1lbHRgLgoKIyMjIFdpZGUgdG8gbG9uZyAobWVsdCkKClRoZSBgZXZlbnRzX3dpZGVgIGRhdGEgc2V0IGhhcyBtdWx0aXBsZSBzZXRzIG9mIGNvbHVtbnMgd2Ugd2FudCB0byByZXNoYXBlLiBUeXBpY2FsbHkgd2Ugd291bGQgb25seSBuZWVkIG9uZSBgbWVsdGAgc3RhdGVtZW50LCBidXQgaW4gaXRzIGNhc2Ugd2UgbmVlZCB0d28uCgpZb3UgY2FuIHNwZWNpZnkgYm90aCBgbWVhc3VyZS52YXJzYCBhbmQgYGlkLnZhcnNgIGJ1dCB5b3UgcHJvYmFibHkgb25seSBuZWVkIG9uZSBvciB0aGUgb3RoZXIuIFVzaW5nICpwYXR0ZXJucyogY2FuIGJlIGV4dHJlbWVseSBoZWxwZnVsLgoKUmVtZW1iZXIgdG8gaW5jbHVkZSBgbmEucm1gIG9yIG5vdC4gSXQncyB1c3VhbGx5IG9rYXkgdG8gbGVhdmUgYHZhcmlhYmxlLmZhY3RvciA9IFRSVUVgIGFzIHRoZSBkZWZhdWx0LgoKYGBge3IgdzJsfQpldmVudHNfd2lkZQp0MSA8LSBkYXRhLnRhYmxlOjptZWx0KGV2ZW50c193aWRlLAogIG1lYXN1cmUudmFycyA9IHBhdHRlcm5zKCdedmlzaXQnLCAnXmxhYicsICdec3VyZ2VyeScsICdecnhmaWxsJyksCiAgdmFyaWFibGUubmFtZSA9ICdvYnMnLAogIHZhbHVlLm5hbWUgPSBjKCd2aXNpdCcsJ2xhYicsJ3N1cmdlcnknLCdyeGZpbGwnKSwKICB2YXJpYWJsZS5mYWN0b3IgPSBGQUxTRQopCnQxCmV2ZW50c19sb25nIDwtIGRhdGEudGFibGU6Om1lbHQodDEsCiAgaWQudmFycyA9IGMoJ3VpZCcsICdvYnMnKSwKICB2YXJpYWJsZS5uYW1lID0gJ2V2ZW50X3R5cGUnLAogIHZhbHVlLm5hbWUgPSAnZXZlbnRfZGF0ZScsCiAgbmEucm0gPSBUUlVFLAogIHZhcmlhYmxlLmZhY3RvciA9IEZBTFNFCilbb3JkZXIodWlkLCBldmVudF90eXBlLCBvYnMpXQpldmVudHNfbG9uZwpgYGAKCkhlcmUncyBhbiBhbHRlcm5hdGl2ZSB0aGF0IHVzZXMgdGhlIGB0c3Ryc3BsaXRgIGZ1bmN0aW9uLgoKYGBge3IgdzJsMn0KYWx0X2xvbmcgPC0gZGF0YS50YWJsZTo6bWVsdChldmVudHNfd2lkZSwKICBpZC52YXJzID0gJ3VpZCcsCiAgdmFsdWUubmFtZSA9ICdldmVudF9kYXRlJywKICBuYS5ybSA9IFRSVUUKKQphbHRfbG9uZwphbHRfbG9uZ1ssIGMoJ2V2ZW50X3R5cGUnLCAnb2JzJykgOj0gdHN0cnNwbGl0KHZhcmlhYmxlLCAnXycpXQphbHRfbG9uZ1ssIHZhcmlhYmxlIDo9IE5VTExdW29yZGVyKHVpZCwgZXZlbnRfdHlwZSwgb2JzKV0KYGBgCgojIyMgTG9uZyB0byB3aWRlIChkY2FzdCkKCmBkY2FzdGAgdXNlcyBhIGZvcm11bGEtbGlrZSBleHByZXNzaW9uLgoKYGBge3IgbDJ3fQpkY2FzdChldmVudHNfbG9uZywgdWlkIH4gZXZlbnRfdHlwZSArIG9icywgdmFsdWUudmFyID0gJ2V2ZW50X2RhdGUnKQpgYGAKCiMjIENvbHVtbiBuYW1lcwoKVXNlIHRoZSBgc2V0bmFtZXNgIGZ1bmN0aW9uCgpgYGB7ciBjb2xuYW1lc30KbmFtZXModDEpCnNldG5hbWVzKHQxLCBwYXN0ZTAoJ3gnLCBzZXEobmNvbCh0MSkpKSkgIyBzZXQgYWxsIGNvbHVtbnMKc2V0bmFtZXModDEsICd4MScsICd1c2VyaWQnKSAjIHNldCBvbGQgY29sdW1uIHRvIG5ldyB2YWx1ZQpzZXRuYW1lcyh0MSwgLTEsIHBhc3RlMCgneV8nLCBzZXEoMiwgbmNvbCh0MSkpKSkgIyBzZXQgZXhjZXB0IDEKbmFtZXModDEpCnJtKHQxKQpgYGAKCiMgRXhwYW5kZWQgZnVuY3Rpb25hbGl0eQoKV2UndmUgYWxyZWFkeSBzZWVuIGAuTmAgYW5kIGAuU0RgLiBMZXQncyB1c2UgKmtleXMqLCBhbmQgdGhlIGluZm9ybWF0aXZlIGB0YWJsZXNgIGZ1bmN0aW9uLgoKYGBge3IgYWRka2V5c30KdGFibGVzKCkKc2V0a2V5KGRhdCwgdWlkLCBpbmNpZGVudF9kYXRlKQpzZXRrZXkoZXZlbnRzX2xvbmcsIHVpZCkKdGFibGVzKCkKYGBgCgpTZWFyY2hpbmcgYSBgZGF0YS50YWJsZWAgd2l0aCBrZXlzIGlzIGZhc3QgYW5kIGVmZmljaWVudC4gQXMgYSBzaWRlLWVmZmVjdCwgeW91ciBkYXRhIHNldCB3aWxsIGJlIHJlLW9yZGVyZWQgYnkgaXRzIGtleXMuCgpIZXJlJ3MgYW4gZXhhbXBsZSBvZiBmaWx0ZXJpbmcgd2l0aG91dCBrZXlzCgpgYGB7ciBub25rZXl9CmRhdFt1aWQgPT0gNV0KZGF0W3VpZCA9PSA1ICYgaW5jaWRlbnRfZGF0ZSA9PSBhcy5EYXRlKCcyMDE3LTExLTI5JyldCmBgYAoKYW5kIHdpdGgga2V5cwoKYGBge3Igd2l0aGtleX0KZGF0Wy4oNSldCmRhdFsuKDUsIGFzLkRhdGUoJzIwMTctMTEtMjknKSldCmRhdFsuKDUpLCBtdWx0ID0gJ2ZpcnN0J10KZGF0Wy4oYygxOjMpKV0KYGBgCgpJZiB5b3VyIHRhYmxlIGhhcyBtdWx0aXBsZSBrZXlzLCBpdCdzIGEgbGl0dGxlIHRyaWNreSB0byBzZWFyY2ggaWYgeW91IHdhbnQgdG8gaWdub3JlIHRoZSBmaXJzdCBrZXkuIEJvdGggb2YgdGhlc2UgZmFpbC4KCmBgYHtyIGJhZGtleX0KdHJ5Q2F0Y2goZGF0Wy4oLCBhcy5EYXRlKCcyMDE3LTExLTI5JykpXSwgZXJyb3IgPSBmdW5jdGlvbihlKSBlKQpkYXRbLih1bmlxdWUodWlkKSwgYXMuRGF0ZSgnMjAxNy0xMS0yOScpKV0KYGBgCgpZb3UgbWF5IG5lZWQgdGhlIGBub21hdGNoYCBhcmd1bWVudC4KCmBgYHtyIHNraXBrZXl9CmRhdFsuKHVuaXF1ZSh1aWQpLCBhcy5EYXRlKCcyMDE3LTExLTI5JykpLCBub21hdGNoID0gTlVMTF0KYGBgCgojIEV4cGVjdGluZyB0aGUgdW5leHBlY3RlZAoKVW5leHBlY3RlZCBiZWhhdmlvciBpbiBgZGF0YS50YWJsZWAgb2Z0ZW4gb2NjdXJzIHdoZW4gd2Ugd3JpdGUgb3VyIG93biBmdW5jdGlvbnMuIFR3byBiaWcgc291cmNlcyBvZiBwcm9ibGVtcyBjb21lIGZyb20gKm5vbi1zdGFuZGFyZCBldmFsdWF0aW9uKiAoTlNFKSBhbmQgKnBhc3MtYnktcmVmZXJlbmNlKi4KCk5TRSBpcyB0aGUgdGhpbmcgdGhhdCBsZXRzIHVzIGF2b2lkIHR5cGluZyBvdXQgdGhlIGZ1bGwgcmVmZXJlbmNlIHRvIGNvbHVtbnMgb2NjdXJyaW5nIHdpdGhpbiBvdXIgZGF0YSBzZXQuIEZvciBleGFtcGxlLCBkb24ndCB5b3UgaGF0ZSB0eXBpbmcgYGRmW29yZGVyKGRmWywndWlkJ10pLF1gIHdoZW4geW91IGNvdWxkIGp1c3QgdHlwZSBgZGZbb3JkZXIodWlkKV1gPyBUaGlzIGJlY29tZXMgYSBwcm9ibGVtIHdoZW4geW91IGhhdmUgY29sdW1uIG5hbWVzIHN0b3JlZCB3aXRoaW4gdmFyaWFibGVzLgoKWW91IGNhbiB1c2UgYHNldGtleXZgIGluc3RlYWQgb2YgYHNldGtleWAKCmBgYHtyIHZhcmtleXN9CmtleWNvbHMgPC0gYygndWlkJywgJ2V2ZW50X2RhdGUnKQp0cnlDYXRjaChzZXRrZXkoYWx0X2xvbmcsIGtleWNvbHMpLCBlcnJvciA9IGZ1bmN0aW9uKGUpIGUpCnNldGtleXYoYWx0X2xvbmcsIGtleWNvbHMpCmBgYAoKQW5kIGFkZCB0aGUgYHdpdGggPSBGQUxTRWAgYXJndW1lbnQgd2hlbiBleHRyYWN0aW5nCgpgYGB7ciB2YXJjb2xzfQp0cnlDYXRjaChhbHRfbG9uZ1ssIGtleWNvbHNdLCBlcnJvciA9IGZ1bmN0aW9uKGUpIGUpCmFsdF9sb25nWywgLi5rZXljb2xzXQphbHRfbG9uZ1ssIGtleWNvbHMsIHdpdGggPSBGQUxTRV0KYGBgCgpJbiBSIHdoZW4geW91IHBhc3MgYW4gb2JqZWN0IHRvIGEgZnVuY3Rpb24sIGEgY29weSBvZiB0aGF0IG9iamVjdCBpcyBtYWRlLiAqcGFzcy1ieS1yZWZlcmVuY2UqIGlzIHVzZWQgdG8gcGFzcyB0aGUgb2JqZWN0IGl0c2VsZiAoYnkgaXRzIG1lbW9yeSBhZGRyZXNzKSwgd2hpY2ggaXMgbXVjaCBtb3JlIGVmZmljaWVudCAoYW5kIGRhbmdlcm91cykuIFdlJ2xsIGxvb2sgYXQgYW4gZXhhbXBsZSBieSBjcmVhdGluZyBhIGZ1bmN0aW9uIHRvIGNhbGN1bGF0ZSBncmVhdCBjaXJjbGUgZGlzdGFuY2Ugd2l0aCB0aGUgW0hhdmVyc2luZSBmb3JtdWxhXVtoYXZlcl0uCgpgYGB7ciBoMX0KaGF2ZXJzaW5lIDwtIGZ1bmN0aW9uKGR0KSB7CiAgIyBkZWNpbWFsIGRlZ3JlZXMgdG8gcmFkaWFucwogIGR0bmFtZXMgPC0gbmFtZXMoZHQpCiAgcHJpbnQoZHRuYW1lcykKICBkdFssckxhdCA6PSBsYXQgKiBwaSAvIDE4MF0KICBkdFssckxvbmcgOj0gbG9uZyAqIHBpIC8gMTgwXQogIGRkIDwtIGR0WyxvdXRlcihyTGF0LHJMYXQsYC1gKV0KICBkbCA8LSBkdFssb3V0ZXIockxvbmcsckxvbmcsYC1gKV0KICBhbGxMYXQgPC0gdChyZXBsaWNhdGUobnJvdyhkdCksIGR0WyxyTGF0XSkpCiAgYSA8LSBzaW4oZGQvMileMiArIGNvcyhhbGxMYXQpICogY29zKGR0WyxyTGF0XSkgKiBzaW4oZGwvMileMgogIGQgPC0gMiAqIDYzNzEwMDAgKiBhc2luKHNxcnQoYSkpCiAgcHJpbnQoZHRuYW1lcykKICBkCn0KcWR0IDwtIGFzLmRhdGEudGFibGUocXVha2VzKQphbnMgPC0gaGF2ZXJzaW5lKHFkdCkKbmFtZXMocWR0KQpgYGAKCldlIGFjdHVhbGx5IGhhdmUgdHdvIHByb2JsZW1zLiBOb3RlIHRoYXQgb3VyIG9yaWdpbmFsIGRhdGEgc2V0IGBxZHRgIGhhcyBiZWVuIHVwZGF0ZWQuIFRoaXMgd2Fzbid0IHJlYWxseSBvdXIgaW50ZW50aW9uLCB0aG91Z2ggaXQgbWF5IG5vdCBhY3R1YWxseSBodXJ0IHVzLiBXZSBhbHNvIHNlZSB0aGF0IG91ciB2YXJpYWJsZSBvZiBjb2x1bW4gbmFtZXMgaGFzIGJlZW4gbW9kaWZpZWQuIFRoYXQncyBiZWNhdXNlIGBkYXRhLnRhYmxlYCBtYWRlIGEgKnNoYWxsb3cqIGNvcHkgb2Ygb3VyIGNvbHVtbiBuYW1lcy4gVGhpcyBtZWFucyBpdCBwb2ludHMgdG8gdGhlIG9yaWdpbmFsIGFuZCBpcyBub3QgYSBkaXN0aW5jdCBjb3B5LiBUbyBtYWtlIGEgZGlzdGluY3QsIG9yICpkZWVwKiBjb3B5LCB1c2UgdGhlIGBjb3B5YCBmdW5jdGlvbi4KCmBgYHtyIGgyfQpoYXZlcnNpbmUgPC0gZnVuY3Rpb24oZHQpIHsKICBkdCA8LSBjb3B5KGR0KQogICMgZGVjaW1hbCBkZWdyZWVzIHRvIHJhZGlhbnMKICBkdG5hbWVzIDwtIGNvcHkobmFtZXMoZHQpKQogIHByaW50KGR0bmFtZXMpCiAgZHRbLHJMYXQgOj0gbGF0ICogcGkgLyAxODBdCiAgZHRbLHJMb25nIDo9IGxvbmcgKiBwaSAvIDE4MF0KICBkZCA8LSBkdFssb3V0ZXIockxhdCxyTGF0LGAtYCldCiAgZGwgPC0gZHRbLG91dGVyKHJMb25nLHJMb25nLGAtYCldCiAgYWxsTGF0IDwtIHQocmVwbGljYXRlKG5yb3coZHQpLCBkdFssckxhdF0pKQogIGEgPC0gc2luKGRkLzIpXjIgKyBjb3MoYWxsTGF0KSAqIGNvcyhkdFssckxhdF0pICogc2luKGRsLzIpXjIKICBkIDwtIDIgKiA2MzcxMDAwICogYXNpbihzcXJ0KGEpKQogIHByaW50KGR0bmFtZXMpCiAgZAp9CnFkdCA8LSBhcy5kYXRhLnRhYmxlKHF1YWtlcykKYW5zIDwtIGhhdmVyc2luZShxZHQpCm5hbWVzKHFkdCkKYGBgCgpMZXQncyB1cGRhdGUgb3VyIGZ1bmN0aW9uIHRvIGluY2x1ZGUgYXJndW1lbnRzIGZvciB0aGUgbGF0aXR1ZGUgYW5kIGxvbmdpdHVkZSBjb2x1bW5zLi4uIHdoaWNoIGRvZXNuJ3Qgd29yay4KCmBgYHtyIGgzfQpoYXZlcnNpbmUgPC0gZnVuY3Rpb24oZHQsIGxhdENvbCwgbG9uZ0NvbCkgewogIGR0IDwtIGNvcHkoZHQpCiAgIyBkZWNpbWFsIGRlZ3JlZXMgdG8gcmFkaWFucwogIGR0bmFtZXMgPC0gY29weShuYW1lcyhkdCkpCiAgcHJpbnQoZHRuYW1lcykKICBkdFssckxhdCA6PSBsYXRDb2wgKiBwaSAvIDE4MF0KICBkdFssckxvbmcgOj0gbG9uZ0NvbCAqIHBpIC8gMTgwXQogIGRkIDwtIGR0WyxvdXRlcihyTGF0LHJMYXQsYC1gKV0KICBkbCA8LSBkdFssb3V0ZXIockxvbmcsckxvbmcsYC1gKV0KICBhbGxMYXQgPC0gdChyZXBsaWNhdGUobnJvdyhkdCksIGR0WyxyTGF0XSkpCiAgYSA8LSBzaW4oZGQvMileMiArIGNvcyhhbGxMYXQpICogY29zKGR0WyxyTGF0XSkgKiBzaW4oZGwvMileMgogIGQgPC0gMiAqIDYzNzEwMDAgKiBhc2luKHNxcnQoYSkpCiAgcHJpbnQoZHRuYW1lcykKICBkCn0KdHJ5Q2F0Y2goYW5zIDwtIGhhdmVyc2luZShxZHQsICdsYXQnLCAnbG9uZycpLCBlcnJvciA9IGZ1bmN0aW9uKGUpIGUpCmBgYAoKSW4gdGhpcyBjYXNlLCB3ZSBjYW4gdXNlIHRoZSBgZ2V0YCBmdW5jdGlvbi4KCmBgYHtyIGg0fQpoYXZlcnNpbmUgPC0gZnVuY3Rpb24oZHQsIGxhdENvbCwgbG9uZ0NvbCkgewogIGR0IDwtIGNvcHkoZHQpCiAgIyBkZWNpbWFsIGRlZ3JlZXMgdG8gcmFkaWFucwogIGR0bmFtZXMgPC0gY29weShuYW1lcyhkdCkpCiAgcHJpbnQoZHRuYW1lcykKICBkdFssckxhdCA6PSBnZXQobGF0Q29sKSAqIHBpIC8gMTgwXQogIGR0WyxyTG9uZyA6PSBnZXQobG9uZ0NvbCkgKiBwaSAvIDE4MF0KICBkZCA8LSBkdFssb3V0ZXIockxhdCxyTGF0LGAtYCldCiAgZGwgPC0gZHRbLG91dGVyKHJMb25nLHJMb25nLGAtYCldCiAgYWxsTGF0IDwtIHQocmVwbGljYXRlKG5yb3coZHQpLCBkdFssckxhdF0pKQogIGEgPC0gc2luKGRkLzIpXjIgKyBjb3MoYWxsTGF0KSAqIGNvcyhkdFssckxhdF0pICogc2luKGRsLzIpXjIKICBkIDwtIDIgKiA2MzcxMDAwICogYXNpbihzcXJ0KGEpKQogIHByaW50KGR0bmFtZXMpCiAgZAp9CmFucyA8LSBoYXZlcnNpbmUocWR0LCAnbGF0JywgJ2xvbmcnKQpgYGAKCldoYXQgaWYgd2Ugd2FudCB0byB1c2UgdGhlc2UgYXJndW1lbnRzIHdpdGhvdXQgcXVvdGVzPwoKSXQgZ2V0cyB1Z2x5IGJ1dCB3ZSBjYW4gYWRkIGBkZXBhcnNlYCBhbmQgYHN1YnN0aXR1dGVgLgoKYGBge3IgaDV9CmhhdmVyc2luZSA8LSBmdW5jdGlvbihkdCwgbGF0Q29sLCBsb25nQ29sKSB7CiAgZHQgPC0gY29weShkdCkKICAjIGRlY2ltYWwgZGVncmVlcyB0byByYWRpYW5zCiAgZHRuYW1lcyA8LSBjb3B5KG5hbWVzKGR0KSkKICBwcmludChkdG5hbWVzKQogIGMxIDwtIGRlcGFyc2Uoc3Vic3RpdHV0ZShsYXRDb2wpKQogIGMyIDwtIGRlcGFyc2Uoc3Vic3RpdHV0ZShsb25nQ29sKSkKICBkdFssckxhdCA6PSBnZXQoYzEpICogcGkgLyAxODBdCiAgZHRbLHJMb25nIDo9IGdldChjMikgKiBwaSAvIDE4MF0KICBkZCA8LSBkdFssb3V0ZXIockxhdCxyTGF0LGAtYCldCiAgZGwgPC0gZHRbLG91dGVyKHJMb25nLHJMb25nLGAtYCldCiAgYWxsTGF0IDwtIHQocmVwbGljYXRlKG5yb3coZHQpLCBkdFssckxhdF0pKQogIGEgPC0gc2luKGRkLzIpXjIgKyBjb3MoYWxsTGF0KSAqIGNvcyhkdFssckxhdF0pICogc2luKGRsLzIpXjIKICBkIDwtIDIgKiA2MzcxMDAwICogYXNpbihzcXJ0KGEpKQogIHByaW50KGR0bmFtZXMpCiAgZAp9CmFucyA8LSBoYXZlcnNpbmUocWR0LCBsYXQsIGxvbmcpCmBgYAoKIyMgQ29kZSBzdXBwb3J0aW5nIGJvdGggZGF0YS5mcmFtZSBhbmQgZGF0YS50YWJsZQoKVGhpcyBmdW5jdGlvbiBwcmludHMgY291bnRzIGZvciB0aGUgdW5pcXVlIHZhbHVlcyB3aXRoaW4gYSBjb2x1bW4uIEJvdGggYGRhdGEuZnJhbWVgIGFuZCBgZGF0YS50YWJsZWAgY2FuIGFjY2VzcyBhIGNvbHVtbiB3aXRoIGRvdWJsZS1icmFja2V0cy4KCmBgYHtyIHdoeW5vdGJvdGh9CmNvdW50cyA8LSBmdW5jdGlvbihkYXQsIGNvbCkgewogIHRhYmxlKGRhdFtbY29sXV0pCn0KYGBgCgpUaGlzIGZ1bmN0aW9uIGNvbnZlcnRzIGEgbGlzdCB0byBhIGBkYXRhLmZyYW1lYCBvciBgZGF0YS50YWJsZWAuIEl0IHdpbGwgY2hvb3NlIHRoZSByaWdodCBwYXRoIGRlcGVuZGluZyBvbiBpZiB0aGUgcGFja2FnZSBpcyBpbnN0YWxsZWQuCgpgYGB7ciBsaXN0MmRhdH0KbDJkZiA8LSBmdW5jdGlvbihsLCBrZWVwRFQgPSBGQUxTRSkgewogIGlmKHJlcXVpcmVOYW1lc3BhY2UoImRhdGEudGFibGUiLCBxdWlldGx5ID0gVFJVRSkpIHsKICAgIHggPC0gZGF0YS50YWJsZTo6cmJpbmRsaXN0KGwpCiAgICBpZigha2VlcERUKSB4IDwtIGFzLmRhdGEuZnJhbWUoeCkKICB9IGVsc2UgewogICAgeCA8LSBkby5jYWxsKHJiaW5kLCBjKGwsIG1ha2Uucm93Lm5hbWVzID0gRkFMU0UpKQogIH0KICB4Cn0KYGBgCgojIEEgZmluYWwgZXhhbXBsZQoKTGV0J3MgcmV2aXNpdCB0aGUgYGRhdGAgYW5kIGBldmVudHNfbG9uZ2AgZGF0YSBzZXRzLiBXZSBtYXkgd2FudCB0byB3cml0ZSBhIGZ1bmN0aW9uIHRvIG1lcmdlIGluY2lkZW50IGRhdGVzIHdpdGggZXZlbnQgZGF0ZXMuIFdlIG1pZ2h0IHdhbnQgdG8ga2VlcCB0aGUgY2xvc2VzdCBldmVudCwgb3IgZXZlbiByZXN0cmljdCBpdCB0byB3aXRoaW4gc29tZSBudW1iZXIgb2YgZGF5cy4KCldlIGludHJvZHVjZSB0d28gbmV3IHRoaW5ncywgdGhlIGBhbGxvdy5jYXJ0ZXNpYW5gIGFyZ3VtZW50IHdpdGhpbiBicmFja2V0cyBhbmQgdGhlIGBieWAgYXJndW1lbnQgd2l0aGluIGB1bmlxdWVgLiBBZGRpdGlvbmFsbHksIGB4W3ldYCB3b3JrcyBsaWtlIGEgbWVyZ2UgKGBtZXJnZSh4LCB5LCBhbGwueT1UUlVFKWAgb3IgKnJpZ2h0IG91dGVyIGpvaW4qKSB1c2luZyBlYWNoIGRhdGEgc2V0cycga2V5cyAoYHVpZGAgaW4gb3VyIGNhc2UpLgoKYGBge3IgbWVyZ2VmdW59CmRhdGVkaWZmIDwtIGZ1bmN0aW9uKGEsIGIpIGFzLm51bWVyaWMoYSAtIGIpCgptZXJnZUJ5TW9zdFJlY2VudCA8LSBmdW5jdGlvbih4LCB5LCBuRGF5cyA9IE5VTEwpIHsKICB6IDwtIHhbeSwgYWxsb3cuY2FydGVzaWFuID0gVFJVRV0KICB6IDwtIHpbZXZlbnRfZGF0ZSA8PSBpbmNpZGVudF9kYXRlXQogIHpbLCBkZCA6PSBkYXRlZGlmZihpbmNpZGVudF9kYXRlLCBldmVudF9kYXRlKV0KICBpZighaXMubnVsbChuRGF5cykpIHsKICAgIHogPC0geltkZCA8IG5EYXlzXQogIH0KICB6IDwtIHpbb3JkZXIodWlkLCBpbmNpZGVudF9kYXRlLCBkZCldCiAgelssIGRkIDo9IE5VTExdCiAgdW5pcXVlKHosIGJ5ID0gYygndWlkJywgJ2luY2lkZW50X2RhdGUnKSkKfQpgYGAKCk1lcmdlIGluY2lkZW50IHdpdGggY2xvc2VzdCBwcmlvciBldmVudC4KCmBgYHtyIG0xfQptZXJnZUJ5TW9zdFJlY2VudChkYXQsIGV2ZW50c19sb25nKQpgYGAKCk1lcmdlIGluY2lkZW50IHdpdGggY2xvc2VzdCBwcmlvciBldmVudCB3aXRoaW4gMzAgZGF5cy4KCmBgYHtyIG0yfQptZXJnZUJ5TW9zdFJlY2VudChkYXQsIGV2ZW50c19sb25nLCAzMCkKYGBgCgpNZXJnZSBpbmNpZGVudCB3aXRoIGNsb3Nlc3QgcHJpb3IgKmxhYiogZXZlbnQuCgpgYGB7ciBtM30KbWVyZ2VCeU1vc3RSZWNlbnQoZGF0LCBldmVudHNfbG9uZ1tldmVudF90eXBlID09ICdsYWInXSkKYGBgCgpgYGB7cn0Kc2Vzc2lvbkluZm8oKQpgYGAKClt5dF06IGh0dHBzOi8vd3d3LnlvdXR1YmUuY29tL3dhdGNoP3Y9aEQ4ZTVEV1dOV3cmbGlzdD1QTHljWVV5MUZsb3REMWlKVkxTc3B1MTByUERwclpFMFZtJmluZGV4PTI1Clt2aWduXTogaHR0cHM6Ly9jcmFuLnItcHJvamVjdC5vcmcvd2ViL3BhY2thZ2VzL2RhdGEudGFibGUvdmlnbmV0dGVzLwpbaGF2ZXJdOiBodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9IYXZlcnNpbmVfZm9ybXVsYQo=