Introduction

This document provides ways to speed up your code before parallelization on your own machine or cluster. There are many ways to use R in an optimal fashion, but often these are not taught in applied statistics courses or perhaps are not otherwise presented in a cohesive way. In other cases, one may simply be new to R, or coming at it from a programming language that works differently.

The ‘R is slow’ mantra is an old one, and has never been entirely accurate in my opinion for two reasons. First, even if it is slower, and it is relative to many languages for many situations, the time saved in programming will far exceed any computational time lost. R often can do things in 1 or 2 lines of code that will require custom functions to be written in other languages, and in that sense R is one of the fastest languages out there for statistical analysis. This is usually the case for data processing/manipulation as well. R was designed expressly for statistical analysis, not for computational speed. For more on some of this point see Hadley Wickham’s chapter.

Secondly, there are simply faster ways to use R, and they often involve a programming approach that is different from what one would use in say, Python or other languages. That is the focus of this document.

For the timings we’ll be using the microbenchmark package, which can show speed differences for even extremely fast operations. This way we don’t have to engage in necessarily slow operations to show the differences well. You’ll need to install it if you want to make your own comparisons. Note also that timings will be in microseconds, milliseconds, or seconds.

  • To be added
    • data structures/representations (alternatives to data.frames)
      • data.table, dplyr, dtplyr, multidplyr
      • pooling
      • sparklyr

Color coding:

emphasis

package

function

object/class

link

Faster Data Input/Output

The base R functions read.csv and similar work fine for smaller data sets. Given their flexibility they may be preferred when useful. However with larger data sets they can be too slow and/or use too much memory. One has plenty of alternatives though.

readr

readr is a newer package and provides many complements of the base R functions, substituting an _ for the . of commonly used file reading functions. For example:

  • read_delim: read delimited files
    • read_csv: comma delimited
    • read_tsv: tab delimited
  • read_lines: read a file line by line
  • read_file: read a whole file in as a string (e.g. for text processing)

To show the difference, we have a simple data set of two columns, one numeric (random normal), and one string (letters). It is large enough for demonstration, but still not very big (less than 6MB on disk).

'data.frame':   260000 obs. of  2 variables:
 $ nums: num  -0.157 -1.935 2.439 0.127 -0.233 ...
 $ lets: Factor w/ 26 levels "a","b","c","d",..: 1 1 1 1 1 1 1 1 1 1 ...

Here is a comparison reading the the file in with both readr and read.csv.

Unit: milliseconds
  expr      min       lq     mean    median        uq       max neval
 readr  71.2180  71.8998  72.6430  72.10712  72.65593  81.51621    20
 baser 335.3346 336.4661 341.5536 341.49618 344.54989 353.95927    20

The readr package makes assumptions about the column type based on the first 1000 observations, but one can override this. As mentioned, for small data the standard function is fine, and even faster by default.

Unit: milliseconds
  expr      min       lq     mean   median       uq      max neval
 readr 3.651792 3.740206 3.858049 3.798122 3.844015 8.953091   100
 baser 1.211106 1.250107 1.328205 1.272541 1.322686 5.587508   100

Chunked

The readr package has chunked versions of those same functions, so that not all the data has to be read in at the same time. This is extremely important for data processing. While one may not have as much choice once the analysis stage is reached, many data processing tasks can be chunked or be done line by line, thereby opening doors for parallelization and memory control.

Unit: milliseconds
  expr      min       lq     mean   median       uq      max neval
 readr 710.0352 722.2291 737.2585 724.8806 727.8937 850.4921    20
 chunk 695.6169 707.1263 726.6579 711.2742 763.2438 769.3471    20

data.table

The data.table package also has a read function that will amount to faster read speeds. The function fread works much like the previous functions to detect column types quickly and otherwise has optimizations in place to speed the process. Both read_* and fread might be viable depending on the situation. Wickham notes the following comparison:

  • Compared to fread, readr:

  • Is slower (currently ~1.2-2x slower. If you want absolutely the best performance, use data.table::fread().

  • Readr has a slightly more sophisticated parser, recognising both doubled (“”“”) and backslash escapes (“"”). Readr allows you to read factors and date times directly from disk.

  • fread() saves you work by automatically guessing the delimiter, whether or not the file has a header, how many lines to skip by default and more. Readr forces you to supply these parameters.

  • The underlying designs are quite different. Readr is designed to be general, and dealing with new types of rectangular data just requires implementing a new tokenizer. fread() is designed to be as fast as possible. fread() is pure C, readr is C++ (and Rcpp).

I will note that readr was faster on the 54 Mb chunk test file, so you may need very large files before fread starts to shine.

Lines vs. Whole Data

Many do not realize that they don’t have to read in the whole data file. Many preprocessing steps can be done line by line, and this may save on memory and provide a means of (massively) parallel operations. Also, and here is a point further not considered by many, this provides a means to debug your code before going prime time. Your file may be huge, but you don’t have to work with the whole thing to get your code sorted out. See readLines in base R for details, but you’d want to use read_lines in readr.

Other

feather

Yet another alternative is to use a different data format altogether. Wickham and Wes McKinney (the latter is behind Python’s pandas module) are working on feather, a binary data format that would be read in R or Python, and allow for very fast read/write operations, as well as smaller file sizes, and more interoperability between the two languages. See this link for more details. The following compares times using feather vs. the readr counterparts.

Unit: milliseconds
          expr       min        lq      mean    median        uq      max neval
     write_csv 182.09487 193.72603 223.05187 214.96862 239.24572 350.7905    20
 write_feather  30.91076  31.46558  39.45274  32.33418  51.06321  64.0367    20
Unit: microseconds
         expr       min        lq      mean    median        uq       max neval
     read_csv 71054.955 71386.177 72744.536 71711.386 72984.514 77582.317    20
 read_feather   621.975  1192.631  2196.104  1469.016  1590.713  8013.532    20

Loops and Alternatives

Loops

Before getting to alternative methods, we’ll first do things with a standard loop, and then show others options later. Loops in and of themselves are not a problem in R, nor are they necessarily slow for some tasks. It’s just that they just often have more efficient alternatives, whether it be more succinct code, or possibly vastly quicker computation.

As one of our working examples, we’ll start with a function that does a random walk. The code is based on this document, co-authored by one of the R’s in R, with some slight additions and modifications.

rw2d_loop_nopre <- function(n) {
  xpos = ypos = 0
  xdir = c(T, F)
  pm1 = c(1,-1)
  
  for (i in 2:n)
  {
    if (sample(xdir, 1)) {
      xpos[i] = xpos[i-1] + sample(pm1, 1)
      ypos[i] = ypos[i-1]
    }
    else {
      xpos[i] = xpos[i-1]
      ypos[i] = ypos[i-1] + sample(pm1, 1)
    }
  }
  data.frame(x=xpos, y=ypos) 
}
# rw2d_loop_nopre(1e5) # for profiling
# ggplot2::qplot(x, y, data=rw2d_loop_nopre(1000), geom='path') # plot check

For better understanding of what’s going on, you can use the debug functionality on the functions used to see what they are doing line by line. Rstudio makes this especially easy, and to get started one can use code that looks like the following.

debugonce(rw2d_loop_nopre)
rw2d_loop_nopre(1000)

You will be able to see what’s produced and even manipulate those objects at each step.

Pre-allocation

One thing you’ll want to note, if you must use an explicit loop, first create an empty vessel to contain the elements of the loops output, rather than taking an append-as-you-go approach. The reasoning is similar to the reasoning behind vectorization noted later. By not having R do some (internal) operations every single iteration, you save time, and it adds up. Memory is also already made available to the object.

In the following we’ll compare the random walk both with and without pre-allocation. I have a line for each function so you can use them for profiling, to see where bottlenecks arise specifically. In (newer versions of) RStudio, you can simply highlight that line and hit Ctrl+Alt+Shft+P to do so. Also, for the first demonstration above I showed an example graph, but all others will look like some (random) version of that, so are subsequently commented out in the code.

# preallocation
rw2d_loop_pre <- function(n) {
  xpos = ypos = numeric(n)
  xdir = c(T, F)
  pm1 = c(1,-1)
  
  for (i in 2:n)
  {
    if (sample(xdir, 1)) {
      xpos[i] = xpos[i-1] + sample(pm1, 1)
      ypos[i] = ypos[i-1]
    }
    else {
      xpos[i] = xpos[i-1]
      ypos[i] = ypos[i-1] + sample(pm1, 1)
    }
  }
  data.frame(x=xpos, y=ypos)
}
# rw2d_loop_pre(1e5) # for profiling
# ggplot2::qplot(x, y, data=rw2d_loop_pre(1000), geom='path')
Unit: milliseconds
                  expr      min       lq     mean    median       uq      max neval
 rw2d_loop_nopre(1000) 9.336365 9.562017 12.40965 14.002640 14.19164 16.04319   100
   rw2d_loop_pre(1000) 7.402994 7.582314  8.90173  7.682311 12.02000 14.21070   100

As we can see, even with this quick example pre-allocation is already saving some time.

Smaller code != faster

Note that the goal is fast running code, but this doesn’t mean there is a one-to-one correlation between speed and code size. The following is a recursive version of the above and it’s three lines of code. It is a little faster than the non-pre-allocated loop, but slower than one with pre-allocation. I might also mention that R is not really that great for recursive functions in my experience, often ‘nesting too deeply’ where other languages have no issue.

rw2d2_recursive <- function(n, x=0, y=0) {
  if(n == 1) return(cumsum(data.frame(x=x, y=y)))
  step = sample(1:4, 1)
  rw2d2_recursive(n=n-1, 
                  x=c(x, c(-1, 1, 0, 0)[step]), 
                  y=c(y, c(0, 0, -1, 1)[step]))
}
# cannot be profiled
# ggplot2::qplot(x, y, data=rw2d2_recursive(1000), geom='path')
Unit: milliseconds
                  expr      min        lq     mean    median       uq      max neval
 rw2d_loop_nopre(1000) 8.816146 11.444509 13.67076 13.834903 14.90716 47.43077   100
   rw2d_loop_pre(1000) 7.135847  7.789052 10.40728  8.203848 10.92444 66.63750   100
 rw2d2_recursive(1000) 7.963387  8.481699 11.51162 10.673126 12.82716 69.51776   100

Looks can be deceiving!

Double loops

Double loops for independent operations are almost always an inefficient way to use R, especially for common data processing tasks, so if you find yourself using one, you should probably think very hard about what alternatives might be possible. In this example we create a distance matrix based on the Euclidean distance between rows in a given matrix m, which for timing demonstration will be a 100 x 100 matrix.

doubleLoopDist <- function(m) {
  n = nrow(m)
  dists = matrix(0, ncol=n, nrow=n)
  for (i in 1:n){
    for (j in 1:n){
      dists[i,j] = sqrt(sum((m[i,] - m[j,])^2))
    }
  }
  dists
}
d = matrix(rnorm(10000), ncol=100)
# doubleLoopDist(d)

As we’ll see in a moment, this is very inefficient, and I would again say there is rarely a need to a double loop. Even if you have to double loop, there might be an efficiency gain possible. Since the distance matrix is symmetric, we only need to compute half of it, then fill in the rest. This would at least cut the time in half.

doubleLoopDist2 <- function(m) {
  n = nrow(m)
  dists = matrix(0, ncol=n, nrow=n)
  for (i in 1:(n-1)){
    for (j in (i+1):n){
      dists[i,j] = sqrt(sum((m[i,] - m[j,])^2))
    }
  }
  
  dists = dists + t(dists) + diag(diag(dists))
  diag(dists) = 0
  dists
}
identical(doubleLoopDist(d), doubleLoopDist2(d))
[1] TRUE
Unit: milliseconds
   expr      min       lq     mean   median       uq      max neval
 dloop1 34.55346 37.79764 43.06150 45.81337 46.72830 98.36466   100
 dloop2 17.34432 18.49033 21.44364 19.33913 26.85913 29.12900   100

Later on we’ll see just how slow this is when we compare it to the base R dist function, which uses compiled C code.

Apply

A set of functions exists in R that typically make explicit loops unnecessary, and can reduce programming time, and potentially make code cleaner. Furthermore, they are parallelizable, and so potentially far faster. There is a misconception that these functions are faster than loops out-of-the-box, but this is incorrect, and they technically can even be slower. Again though, you automatically gain in coding efficiency and possibly gain a lot in computation time with the use of parallelization.

apply functions

  • apply: arrays, matrices, data.frames
  • lapply, sapply, vapply: lists, data.frames, vectors
  • tapply: grouped operations (table apply)
  • mapply: multivariate version of sapply
  • replicate: similar to sapply

As a simple example, let’s estimate some column means. An explicit loop might look like the following.

means_loop = rep(0, ncol(d))  # initialize the means vector
for (n in 1:ncol(d)){
  means_loop[n] = mean(d[,n])
}
head(means_loop)
[1]  0.09693607  0.07491450  0.14641378  0.04092882  0.20245490 -0.09174778

Let’s use the apply function instead. The primary arguments are a matrix/data.frame (or any array), the margin to iterate over (e.g. rows or columns), and the function we want to apply, which in this case is the mean.

means_apply = apply(d, 2, mean)
identical(means_loop, means_apply)
[1] TRUE

And that’s all there is to it. A point of emphasis however: there is no guaranteed speed gain here, only more succinct code. The following demonstrates using a loop vs. apply on a 1000x1000 matrix. For a simple operation like this, the explicit loop is actually faster. However, most would not want to write a loop every time they want column or row means, and as we’ll see later, we’d use a vectorized approach rather than either of these.

Unit: milliseconds
        expr      min       lq     mean   median       uq      max neval
  means_loop 12.22220 12.55708 14.87569 12.95751 16.53907 69.19196   100
 means_apply 14.05909 15.30876 18.84277 19.11773 19.59968 71.32181   100

plyr alternates

The plyr package provides alternatives to the apply family of functions. These plyr functions work based on the first two letters. The first denotes the input, the second the output. For example, ldply takes a list and converts the output to a data.frame.

  • Lists: ldply, llply, laply

  • Arrays: a*ply

  • Dataframes: d*ply

  • Multiple arguments: m*ply

As an example will use adply on the column mean example. The d object is a matrix, and we’ll get a data.frame as output.

library(plyr)
adply(d, 2, mean)

Unfortunately, the flexibility does come at a price, and plyr functions are very slow (mostly because data.frames are slow). Using the 1000x1000 matrix again, and using aaply to be more comparable, we see the plyr function is much slower.

Unit: milliseconds
        expr      min       lq     mean   median       uq       max neval
  means_loop 12.25328 13.22891 20.46052 15.98190 16.15375  72.28072   100
 means_apply 16.02179 19.51361 30.64961 22.77069 26.35973  78.05620   100
       aaply 73.72027 78.07908 84.69652 79.26012 80.39513 134.93946   100

However, there is comparable functionality for data.frames in dplyr that would be much faster.

Parallel versions

Another thing that puts the apply approach ahead of loops regards parallelization. Most of the base R apply functions have par* counterparts, e.g. parApply, parLapply etc. This is also the case for plyr functions, which have a .parrallel=TRUE argument. Example code would like the following.

x = matrix(rnorm(1e7), ncol=1e6)
library(parallel)
cl = makeCluster(8)
clusterExport(cl, 'x')
means = parApply(cl, x, 2, mean)
stopCluster(cl)

For the plyr functions, one needs to use the foreach package and register the cluster, and supply the .parallel argument. It’s still exceedingly slow, so you might just stick with the parallel/foreach package.

library(foreach); library(doParallel)
library(parallel)
cl = makeCluster(12)
registerDoParallel(cl)
means = aaply(x, 2, mean, .parallel = T, .paropts = list(.export='x'))
stopCluster(cl)

For something simple like this, there isn’t going to be much gained in going parallel. And this is an important point to note: using more cores does not necessarily mean more speed, and this is especially the case when spreading operations across machines. Had I used 12 instead of 8 on my machine, the difference would have been negligible. I should also note that none of these approaches is nearly as fast as we could get with a built-in R function, colMeans.

Unit: seconds
          expr      min       lq     mean   median       uq      max neval
    means_loop 5.385455 5.446444 5.911896 5.624648 6.656046 6.671387    10
   means_apply 5.430653 5.491898 5.676836 5.575201 5.933212 6.021431    10
 parallelMeans 2.990517 3.152247 3.215829 3.222990 3.260839 3.424342    10

Using faster languages

Base R internals

Much of base R is not written in R, but much faster languages such as C, C++ and Fortran, and using those functions can lead to enormous speed gains. Relative to an explicit loop that does the same thing, there is no comparison to a base R function that’s calling internal C or other code. Not only will the built-in function run faster, but your code will be more succinct because you’re making a single function call as opposed to an explicit loop.

As an example let’s compare the previous double loop approach to the base R function dist.

Unit: milliseconds
   expr       min        lq      mean    median       uq       max neval
  dloop 36.542256 38.517853 43.065587 38.752303 47.46347 58.667367   100
 dloop2 17.985360 19.325787 20.986236 19.489124 19.65276 38.788812   100
   dist  1.523706  1.590126  1.614325  1.614613  1.63382  1.708158   100

If there are actually only two columns though, dist would be slower due to some preliminary checks and calculations that sum and sqrt functions do not have to make (note that these timings are in microseconds).

Unit: microseconds
    expr    min     lq     mean median     uq     max neval
    dist 65.687 67.740 72.81621 69.793 75.218 112.314   100
 sqrtsum  2.639  3.226  3.90039  3.666  4.106  17.301   100

Again, when there isn’t much to optimize, don’t waste time figuring out how to do so.

Premature optimization is the root of all evil.

~ Donald Knuth

As another example, let’s use the colMeans function on that large 10 x 1000000 matrix we used before.

Unit: milliseconds
          expr         min          lq        mean      median          uq        max neval
    means_loop 5385.455354 5446.444056 5911.895932 5624.647995 6656.045691 6671.38714    10
   means_apply 5430.653350 5491.897762 5676.835830 5575.201307 5933.212066 6021.43071    10
 parallelMeans 2990.517013 3152.246836 3215.829386 3222.989777 3260.838736 3424.34182    10
      colMeans    7.775123    7.855472    8.202892    7.900339    8.116022   12.03423   100

This shows that using the compiled C in the colMeans function is way faster than even parallelizing (in this case).

As a further illustration, let’s center a matrix, i.e. subtract the mean. We now have several options at this point, but we’ll keep it to the following:

  • using the scale function with the argument scale = FALSE
  • using the sweep function
  • subtract the column means calculated via colMeans
Unit: milliseconds
              expr      min       lq      mean    median       uq      max neval
       means_sweep 89.46845 91.09817 119.72156 104.24922 167.7151 181.0814   100
             scale 95.17531 97.14974 119.93443 111.44093 121.7853 209.0363   100
 subtract_colMeans 33.78692 34.21637  49.67427  40.48495  54.2156 117.4253   100

The interesting thing to note here is that sweep is already as fast as the built in scale function, but we could have provided any statistic of the columns to ‘sweep out’. For example, maybe we prefer the median, or perhaps we want to add rather than subtract. The slowdown of sweep is that the statistic to be swept out may require a slower and/or separate operation (e.g. I could first create an object means that are the column means). In the end, one might have several options depending on their goals.

Rcpp

We can potentially take advantage of the power of C++ explicitly within R, by using the Rcpp package. It’s also worth noting that many R packages do so to pick up some speed.

library(Rcpp)
distC = cppFunction('
NumericMatrix distC(NumericMatrix x) {
  int n = x.nrow();
  NumericMatrix out(n, n);
  for(int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      out(i,j) = sqrt(sum(pow(x(i,_) - x(j,_), 2.0)));
    }
  }
  return out;
}
')
distC(d[1:3,])
         [,1]     [,2]     [,3]
[1,]  0.00000 15.68387 13.98549
[2,] 15.68387  0.00000 13.49691
[3,] 13.98549 13.49691  0.00000
dist(d[1:3,], diag = T, upper = T)
         1        2        3
1  0.00000 15.68387 13.98549
2 15.68387  0.00000 13.49691
3 13.98549 13.49691  0.00000

Now that we can see thse both produce the same thing, let’s time the dist function, the C++ version and the loop.

Unit: milliseconds
  expr       min        lq      mean    median        uq       max neval
  dist  1.523120  1.581476  1.604833  1.599950  1.633967  1.692030   100
 distC  1.196444  1.234420  1.245064  1.243363  1.261691  1.302305   100
 dloop 34.157286 34.931016 40.931563 38.261996 39.007134 68.798428   100

Note that in bigger matrices the R function would eventually win out, but the point here is that we’re at least in the ballpark. Furthermore, like most languages, it is easy enough to run another language script from within that program. So if you’re working within another language for the heavy lifting, you could call R from it, or vice versa, i.e. write what you need in another language and call it from R.

Vectorization

Vectorization is a key concept in R, though some coming to R from other languages (e.g. Matlab) may be familiar with it. The basic idea is that we pass whole vectors to operations rather than the elements of it, and as such R can treat the vector once and go from there, rather than treat each element of the vector as a unique snowflake that must be considered individually, and figuring things out every time the operation is run.

As an example let’s do a simple loop vs. a vectorized approach.

x = 1:3
y = 7:9
for (i in seq_along(x)) {
  print(x[i] + y[i])
}
[1] 8
[1] 10
[1] 12

Every iteration, R evaluates what type of object x[i] is, what y[i] is, whether adding them is possible etc. If we use a vectorized approach, R figures this out once and proceeds accordingly.

x + y
[1]  8 10 12

Vectorizing a sequential operation

Let’s return to our random walk example for some benchmarks. This is a nice example because we can see that sometimes even seemingly sequential operations might be put in a form that would not require a loop. The first vectorized example uses no explicit loop but gives us the same result. It uses ifelse, which is a vectorized version of the if... else construct. However, ifelse comes with some baggage, and dplyr provides a faster version, if_else.

# vectorize
rw2d2_vec_ifelse <- function(n) {
  steps = sample(c(-1, 1), n-1, replace=T)
  xdir = sample(c(T, F), n-1, replace=T)
  xpos = c(0, cumsum(ifelse(xdir, steps, 0)))
  ypos = c(0, cumsum(ifelse(xdir, 0, steps)))
  data.frame(x=xpos, y=ypos)
}
# rw2d2_vec_ifelse(1e7)
# ggplot2::qplot(x, y, data=rw2d2_vec_ifelse(1000), geom='path')
# dplyr if_else can be faster if there are many operations
rw2d2_vec_ifelse2 <- function(n) {
  steps = sample(c(-1, 1), n-1, replace=T)
  xdir = sample(c(T, F), n-1, replace=T)
  xpos = c(0, cumsum(if_else(xdir, steps, 0)))
  ypos = c(0, cumsum(if_else(xdir, 0, steps)))
  data.frame(x=xpos, y=ypos)
}
# rw2d2_vec_ifelse2(1e7)
# ggplot2::qplot(x, y, data=rw2d2_vec_ifelse2(1000), geom='path')

However, we can still get more efficient. Here we do all the necessary sampling for the x and y positions first, then subsequently fill out those positions. We also just use the fact that cumsum can work on the data.frame itself. As data.frames are lists, cumsum will work on its elements, which in this case are the columns.

rw2d2_vec_noifelse <- function(n) {
  dir = sample(1:4, n-1, replace=T)
  xpos = c(0, c(-1, 1, 0, 0)[dir])
  ypos = c(0, c(0, 0, -1, 1)[dir])
  cumsum(data.frame(x=xpos, y=ypos))
}
# rw2d2_vec_noifelse(1e7)
# ggplot2::qplot(x, y, data=rw2d2_vec_noifelse(1000), geom='path')

Now we compare all the looping choices considered thus far:

  • loop no pre-allocation
  • loop with pre-allocation
  • vectorization (2 versions)
  • more efficient vectorization

The last version is succinct in code and much faster as well.

Unit: microseconds
                      expr        min          lq        mean      median         uq        max neval
    rw2d_loop_nopre(10000) 213722.327 229259.2290 269065.1205 264013.2695 301059.176 424019.833   100
      rw2d_loop_pre(10000)  69603.975  79123.0310  82274.5622  81806.5240  84786.049 120327.309   100
   rw2d2_vec_ifelse(10000)   1456.846   1506.2575   1597.8680   1525.6125   1545.700   8314.695   100
  rw2d2_vec_ifelse2(10000)   1217.557   1255.3860   1274.2183   1270.6350   1285.884   1432.506   100
 rw2d2_vec_noifelse(10000)    551.010    584.4395    719.0892    597.9285    615.670   6764.598   100

For more examples and issues with vectorization see the following:

A very accessible intro to vectorization Noam Ross

When to leave loops alone Hadley Wickham

R Inferno (3rd Circle) Patrick Burns

Matrix operations

Consider a linear combination to produce model predictions as in a standard regression model. We multiply each column by a coefficient and sum them.

b = runif(11) # first value is the intercept
X = matrix(rnorm(100000), ncol=10)
lincom1 = b[1] + b[2]*X[,1] + b[3]*X[,2] + b[4]*X[,3] + b[5]*X[,4] + b[6]*X[,5] + 
  b[7]*X[,6] + b[8]*X[,7] + b[9]*X[,8] + b[10]*X[,9] + b[11]*X[,10]

While this is vectorized, we can do better. We can use matrix multiplication to produce the same result. In addition, the biggest gain here is programming time. Matrix multiplication takes far less to code up.

X = cbind(1, X) # add intercept column
lincom2  = X %*% b

However, even within matrix operations there might be faster ways to do it. In this case, crossprod is slightly faster.

lincom3 = tcrossprod(X, t(b))
identical(lincom1, c(lincom2))
[1] TRUE
identical(lincom2, lincom3)
[1] TRUE

Let’s time them.

Unit: microseconds
 expr     min      lq      mean   median       uq      max neval
  lc1 590.598 613.324 732.61942 627.9860 635.4640 4235.645   100
  lc2 138.999 140.465 147.76094 146.7695 154.5405  197.061   100
  lc3  56.303  57.770  61.37959  59.8220  62.9015   80.937   100

They all produce identical output, but using a matrix operation is over 4 times as fast as the simple sum, and crossprod over 11 times as fast. Programming time is quicker also.

Even how we do the matrix operations can have an effect. The following examples use various means to obtain coefficients from a standard linear regression model. We’ll start with just the base R lm function. The next is the lm.fit function, which is what lm uses, but after a lot of pre- and post-processing of the data. After that we use basic matrix multiplication, a grouped version of it, followed by use of the crossprod function.

set.seed(1234)
n = 10000000                   # sample size
x = rnorm(n)                   # covariate
y =  5 + 2*x + rnorm(n)        # target
X = cbind(1, x)                # model.matrix
# lm
lm_base  = lm(y ~ x)
# use the underlying fit function
lm_fit  = lm.fit(X, y)          # note: qr.solve isn't really a gain here but could also be used
# an even faster version
lm_fit2  = .lm.fit(X, y)
# normal equations to get coefficients
matrix_raw = solve(t(X) %*% X) %*% t(X) %*% y
matrix_grouped = solve(t(X)%*%X) %*% (t(X) %*% y)
# crossprod approach
matrix_crossprod = crossprod(solve(crossprod(X)), crossprod(X,y))
cbind(cbind(lm_base=coef(lm_base), 
      lm_fit=coef(lm_fit), 
      lm_fit2=coef(lm_fit2), 
      matrix_raw=matrix_raw[,1],
      matrix_grouped=matrix_grouped[,1],
      matrix_crossprod=matrix_crossprod[,1]))
             lm_base   lm_fit  lm_fit2 matrix_raw matrix_grouped matrix_crossprod
(Intercept) 4.999339 4.999339 4.999339   4.999339       4.999339         4.999339
x           1.999691 1.999691 1.999691   1.999691       1.999691         1.999691

Now for the timings.

Unit: milliseconds
             expr        min         lq       mean     median        uq        max neval
          lm_base 8518.96348 8553.59319 8785.89097 8652.52351 8846.2702 9598.13285    20
           lm_fit  608.17270  610.11326  725.07545  611.13302  846.8290 1431.15979    20
          lm_fit2  492.01975  495.77271  576.94008  496.67547  747.8333  810.55111    20
       matrix_raw  387.49752  390.13028  472.59917  392.63900  649.1642  676.84504    20
   matrix_grouped  246.16266  247.35969  380.93035  248.66786  371.0785 1225.53339    20
 matrix_crossprod   51.68899   52.91857   53.74915   53.54319   54.0288   57.83074    20

We can see above that these approaches all produce the same results, but take very different amounts of time to complete. We get a significant gain if we reduce the lm overhead, where lm.fit is almost 10x faster, and the .lm.fit, which is just a wrapper for the C code call, is faster still. We can still get faster by using matrix operations, and even get a slight gain if we group them a certain way. This reduces memory usage as well. The idea is that if we go from solve(t(X)%*%X) and post multiply by t(X), we’re dealing with a 2 x 107 matrix. If we first t(X) %*% y, we’re now just multiplying a 2x2 matrix with a 2x1 matrix. In the end though, crossprod is the most optimized, and notably faster than any of the other approaches.

And finally, there are efficient methods, particularly for sparse matrices, in packages such as Matrix. For dense matrices it has the same speed as standard R, but would still have other within-package functionality that might be useful.

library(Matrix)
X2 = as(X, 'dgeMatrix')
y2 = as(y, 'dgeMatrix')
Unit: milliseconds
              expr      min       lq     mean   median       uq      max neval
  matrix_crossprod 49.23980 53.24276 53.59032 53.66591 54.01502 59.17703   100
 matrix_crossprod2 52.04411 53.28352 53.68203 53.81811 54.10270 55.42700   100

Here’s a comparison with sparse matrices, where memory as well as speed gains can be made. The base R object is 200 times larger.

m <- matrix(0, 500, 500)
m[runif(314, 0, length(m))] <- 1
mm <- as(m, "dgCMatrix")
object.size(m) / object.size(mm) # 
278.114571746385 bytes

The speed gains are notable as well.

microbenchmark(sparse_tcrossprod <- tcrossprod(mm),
               sparse_crossprod <- crossprod(mm),
               base_crossprod <- crossprod(m),
               base_tcrossprod <- tcrossprod(m))
Unit: microseconds
                                expr       min         lq       mean     median        uq       max neval
 sparse_tcrossprod <- tcrossprod(mm)   137.532   157.6205   183.0385   172.4285   198.381   332.248   100
   sparse_crossprod <- crossprod(mm)   141.932   157.7670   183.0298   168.7635   194.275   339.286   100
      base_crossprod <- crossprod(m) 49594.339 50380.0910 50557.3464 50560.1435 50721.575 51607.179   100
    base_tcrossprod <- tcrossprod(m)   929.296   974.6030  1016.5842  1009.3525  1052.460  1196.737   100

Other R builds

Other versions of R exist. For those using university high performance computing, the R build you are using will be different, for example. Here is a run down of some, partly taken from Wickham’s chapter linked in the introduction of this document. There are others, but I just note the ones that still appear to be in regular development.

Microsoft Open R: From Microsoft, specifically the former Revolution Analytics group. While the build is typically a point release behind the current version of R, that won’t affect most users, and it’s easy to install on one’s own machine just like any R.

pqR (pretty quick R): by Radford Neal. Fixes many obvious performance issues, and provides better memory management and some support for automatic multithreading.

Renjin: by BeDataDriven. Renjin uses the Java virtual machine, and has an extensive test suite.

Summary

To complete the partial quote referred to earlier…

“Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.”

~ Donald Knuth

There are no good benchmarks for the balance of programming vs. computational time for statistical analysis and related activities. However, the reason R will beat other languages hands down in many cases is because it is so much easier to program certain, often very common operations. Furthermore, the functionality available across a wide variety of modeling paradigms is unmatched at present. Knowing just a few ‘tricks’ such as those demonstrated here will help gain those small efficiencies in the 97% time. In the end, what approach works best will depend on the specifics of the task, but you will always have options with R, and often pretty fast ones.

References

Two excellent texts on R programming are:

The Art of R Programming by Norm Matloff

Advanced R by Hadley Wickham.

LS0tDQp0aXRsZTogPHNwYW4gc3R5bGU9ImZvbnQtc2l6ZToxNTAlOyBmb250LXZhcmlhbnQ6c21hbGwtY2FwczsgZm9udC1zdHlsZTppdGFsaWMiPkZhc3RSPC9zcGFuPg0KYXV0aG9yOiB8DQogIDxkaXYgY2xhc3M9InRpdGxlIj48c3BhbiBzdHlsZT0iZm9udC1zaXplOjEyNSU7IGZvbnQtdmFyaWFudDpzbWFsbC1jYXBzOyBmb250LXN0eWxlOm5vcm1hbCI+W01pY2hhZWwgQ2xhcmtdKGh0dHA6Ly9tLWNsYXJrLmdpdGh1Yi5pbyk8L3NwYW4+PGJyPjxicj4NCiAgWzxpbWcgc3JjPSIuLi9pbWcvQ1NDQVJfZGFya2xldHRlci5wbmciLCB3aWR0aD0nNTAlJz5dKGh0dHA6Ly9jc2Nhci5yZXNlYXJjaC51bWljaC5lZHUvKTwvZGl2Pg0KICANCm91dHB1dDogDQogIGh0bWxfbm90ZWJvb2s6DQogICAgY3NzOiBub3RlYm9va3MuY3NzDQogICAgaGlnaGxpZ2h0OiBweWdtZW50cw0KICAgIHRvYzogeWVzDQogICAgdG9jX2Zsb2F0OiB5ZXMNCi0tLQ0KDQpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GQUxTRX0NCmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSwgY29tbWVudD1OQSwgY2FjaGU9VCwgbWVzc2FnZSA9IEYsIHdhcm5pbmdzPUYsIA0KICAgICAgICAgICAgICAgICAgICAgIFIub3B0aW9ucz1saXN0KHdpZHRoPTEyMCkpDQpgYGANCg0KDQpgYGB7ciBsb2FkbGlicywgZWNobz1GQUxTRSwgY2FjaGU9RkFMU0V9DQpsaWJyYXJ5KG1pY3JvYmVuY2htYXJrKTtsaWJyYXJ5KHJlYWRyKTsgbGlicmFyeShkcGx5cik7IGxpYnJhcnkoZGF0YS50YWJsZSk7IGxpYnJhcnkoZmVhdGhlcikNCmBgYA0KDQoNCjxicj48YnI+PGJyPg0KDQojIEludHJvZHVjdGlvbg0KDQpUaGlzIGRvY3VtZW50IHByb3ZpZGVzIHdheXMgdG8gc3BlZWQgdXAgeW91ciBjb2RlICpiZWZvcmUqIHBhcmFsbGVsaXphdGlvbiBvbiB5b3VyIG93biBtYWNoaW5lIG9yIGNsdXN0ZXIuICBUaGVyZSBhcmUgbWFueSB3YXlzIHRvIHVzZSBSIGluIGFuIG9wdGltYWwgZmFzaGlvbiwgYnV0IG9mdGVuIHRoZXNlIGFyZSBub3QgdGF1Z2h0IGluIGFwcGxpZWQgc3RhdGlzdGljcyBjb3Vyc2VzIG9yIHBlcmhhcHMgYXJlIG5vdCBvdGhlcndpc2UgcHJlc2VudGVkIGluIGEgY29oZXNpdmUgd2F5LiAgSW4gb3RoZXIgY2FzZXMsIG9uZSBtYXkgc2ltcGx5IGJlIG5ldyB0byBSLCBvciBjb21pbmcgYXQgaXQgZnJvbSBhIHByb2dyYW1taW5nIGxhbmd1YWdlIHRoYXQgd29ya3MgZGlmZmVyZW50bHkuICANCg0KVGhlICdSIGlzIHNsb3cnIG1hbnRyYSBpcyBhbiBvbGQgb25lLCBhbmQgaGFzIG5ldmVyIGJlZW4gZW50aXJlbHkgYWNjdXJhdGUgaW4gbXkgb3BpbmlvbiBmb3IgdHdvIHJlYXNvbnMuIEZpcnN0LCBldmVuIGlmIGl0IGlzIHNsb3dlciwgYW5kIGl0ICppcyogcmVsYXRpdmUgdG8gbWFueSBsYW5ndWFnZXMgZm9yIG1hbnkgc2l0dWF0aW9ucywgdGhlIHRpbWUgc2F2ZWQgaW4gcHJvZ3JhbW1pbmcgd2lsbCBmYXIgZXhjZWVkIGFueSBjb21wdXRhdGlvbmFsIHRpbWUgbG9zdC4gIFIgb2Z0ZW4gY2FuIGRvIHRoaW5ncyBpbiAxIG9yIDIgbGluZXMgb2YgY29kZSB0aGF0IHdpbGwgcmVxdWlyZSBjdXN0b20gZnVuY3Rpb25zIHRvIGJlIHdyaXR0ZW4gaW4gb3RoZXIgbGFuZ3VhZ2VzLCBhbmQgaW4gdGhhdCBzZW5zZSBSIGlzIG9uZSBvZiB0aGUgZmFzdGVzdCBsYW5ndWFnZXMgb3V0IHRoZXJlIGZvciBzdGF0aXN0aWNhbCBhbmFseXNpcy4gVGhpcyBpcyB1c3VhbGx5IHRoZSBjYXNlIGZvciBkYXRhIHByb2Nlc3NpbmcvbWFuaXB1bGF0aW9uIGFzIHdlbGwuICBSIHdhcyBkZXNpZ25lZCBleHByZXNzbHkgZm9yIHN0YXRpc3RpY2FsIGFuYWx5c2lzLCBub3QgZm9yIGNvbXB1dGF0aW9uYWwgc3BlZWQuICBGb3IgbW9yZSBvbiBzb21lIG9mIHRoaXMgcG9pbnQgc2VlIFtIYWRsZXkgV2lja2hhbSdzIGNoYXB0ZXJdKGh0dHA6Ly9hZHYtci5oYWQuY28ubnovUGVyZm9ybWFuY2UuaHRtbCkuDQoNClNlY29uZGx5LCB0aGVyZSBhcmUgc2ltcGx5IGZhc3RlciB3YXlzIHRvIHVzZSBSLCBhbmQgdGhleSBvZnRlbiBpbnZvbHZlIGEgcHJvZ3JhbW1pbmcgYXBwcm9hY2ggdGhhdCBpcyBkaWZmZXJlbnQgZnJvbSB3aGF0IG9uZSB3b3VsZCB1c2UgaW4gc2F5LCBQeXRob24gb3Igb3RoZXIgbGFuZ3VhZ2VzLiAgVGhhdCBpcyB0aGUgZm9jdXMgb2YgdGhpcyBkb2N1bWVudC4NCg0KRm9yIHRoZSB0aW1pbmdzIHdlJ2xsIGJlIHVzaW5nIHRoZSA8c3BhbiBjbGFzcz0icGFjayI+bWljcm9iZW5jaG1hcms8L3NwYW4+IHBhY2thZ2UsIHdoaWNoIGNhbiBzaG93IHNwZWVkIGRpZmZlcmVuY2VzIGZvciBldmVuIGV4dHJlbWVseSBmYXN0IG9wZXJhdGlvbnMuICBUaGlzIHdheSB3ZSBkb24ndCBoYXZlIHRvIGVuZ2FnZSBpbiBuZWNlc3NhcmlseSBzbG93IG9wZXJhdGlvbnMgdG8gc2hvdyB0aGUgZGlmZmVyZW5jZXMgd2VsbC4gIFlvdSdsbCBuZWVkIHRvIGluc3RhbGwgaXQgaWYgeW91IHdhbnQgdG8gbWFrZSB5b3VyIG93biBjb21wYXJpc29ucy4gTm90ZSBhbHNvIHRoYXQgdGltaW5ncyB3aWxsIGJlIGluIG1pY3Jvc2Vjb25kcywgbWlsbGlzZWNvbmRzLCBvciBzZWNvbmRzLg0KDQotIFRvIGJlIGFkZGVkDQogICAgLSBkYXRhIHN0cnVjdHVyZXMvcmVwcmVzZW50YXRpb25zIChhbHRlcm5hdGl2ZXMgdG8gZGF0YS5mcmFtZXMpDQogICAgICAgIC0gZGF0YS50YWJsZSwgZHBseXIsIGR0cGx5ciwgbXVsdGlkcGx5cg0KICAgICAgICAtIFtwb29saW5nXShodHRwczovL2dpdGh1Yi5jb20vcnN0dWRpby9wb29sKQ0KICAgICAgICAtIHNwYXJrbHlyDQoNCkNvbG9yIGNvZGluZzoNCg0KDQo8c3BhbiBjbGFzcz0iZW1waCI+ZW1waGFzaXM8L3NwYW4+DQoNCjxzcGFuIGNsYXNzPSJwYWNrIj5wYWNrYWdlPC9zcGFuPg0KDQo8c3BhbiBjbGFzcz0iZnVuYyI+ZnVuY3Rpb248L3NwYW4+DQoNCjxzcGFuIGNsYXNzPSJvYmpjbGFzcyI+b2JqZWN0L2NsYXNzPC9zcGFuPg0KDQpbbGlua10oKQ0KDQojIEZhc3RlciBEYXRhIElucHV0L091dHB1dA0KDQpUaGUgYmFzZSBSIGZ1bmN0aW9ucyByZWFkLmNzdiBhbmQgc2ltaWxhciB3b3JrIGZpbmUgZm9yIHNtYWxsZXIgZGF0YSBzZXRzLiAgR2l2ZW4gdGhlaXIgZmxleGliaWxpdHkgdGhleSBtYXkgYmUgcHJlZmVycmVkIHdoZW4gdXNlZnVsLiBIb3dldmVyIHdpdGggbGFyZ2VyIGRhdGEgc2V0cyB0aGV5IGNhbiBiZSB0b28gc2xvdyBhbmQvb3IgdXNlIHRvbyBtdWNoIG1lbW9yeS4gT25lIGhhcyBwbGVudHkgb2YgYWx0ZXJuYXRpdmVzIHRob3VnaC4NCg0KIyMgcmVhZHINCg0KPHNwYW4gY2xhc3M9InBhY2siPnJlYWRyPC9zcGFuPiBpcyBhIG5ld2VyIHBhY2thZ2UgYW5kIHByb3ZpZGVzIG1hbnkgY29tcGxlbWVudHMgb2YgdGhlIGJhc2UgUiBmdW5jdGlvbnMsIHN1YnN0aXR1dGluZyBhbiBcXyBmb3IgdGhlIC4gb2YgY29tbW9ubHkgdXNlZCBmaWxlIHJlYWRpbmcgZnVuY3Rpb25zLiBGb3IgZXhhbXBsZToNCg0KLSA8c3BhbiBjbGFzcz0iZnVuYyI+cmVhZF9kZWxpbTwvc3Bhbj46IHJlYWQgZGVsaW1pdGVkIGZpbGVzDQogICAgLSByZWFkX2NzdjogY29tbWEgZGVsaW1pdGVkDQogICAgLSByZWFkX3RzdjogdGFiIGRlbGltaXRlZA0KLSA8c3BhbiBjbGFzcz0iZnVuYyI+cmVhZF9saW5lczwvc3Bhbj46IHJlYWQgYSBmaWxlIGxpbmUgYnkgbGluZQ0KLSA8c3BhbiBjbGFzcz0iZnVuYyI+cmVhZF9maWxlPC9zcGFuPjogcmVhZCBhIHdob2xlIGZpbGUgaW4gYXMgYSBzdHJpbmcgKGUuZy4gZm9yIHRleHQgcHJvY2Vzc2luZykNCg0KYGBge3IgY3JlYXRlQmlnRGF0YSwgZWNobz1GQUxTRSwgY2FjaGU9RkFMU0V9DQp3cml0ZV9jc3YoZXhwYW5kLmdyaWQobnVtcz1ybm9ybSgxZTQpLCBsZXRzPWxldHRlcnMpLCAnZGF0YS90ZXN0cmVhZHIuY3N2JykNCndyaXRlX2NzdihleHBhbmQuZ3JpZChudW1zPXJub3JtKDFlNSksIGxldHM9bGV0dGVycyksICdkYXRhL3Rlc3RjaHVuay5jc3YnKQ0KYGBgDQoNCg0KVG8gc2hvdyB0aGUgZGlmZmVyZW5jZSwgd2UgaGF2ZSBhIHNpbXBsZSBkYXRhIHNldCBvZiB0d28gY29sdW1ucywgb25lIG51bWVyaWMgKHJhbmRvbSBub3JtYWwpLCBhbmQgb25lIHN0cmluZyAobGV0dGVycykuIEl0IGlzIGxhcmdlIGVub3VnaCBmb3IgZGVtb25zdHJhdGlvbiwgYnV0IHN0aWxsIG5vdCB2ZXJ5IGJpZyAobGVzcyB0aGFuIDZNQiBvbiBkaXNrKS4NCg0KYGBge3Igc2hvd0JpZ0RhdGEsIGVjaG89RkFMU0V9DQp0ZXN0ID0gcmVhZC5jc3YoJ2RhdGEvdGVzdHJlYWRyLmNzdicpDQpzdHIodGVzdCkNCmBgYA0KDQpIZXJlIGlzIGEgY29tcGFyaXNvbiByZWFkaW5nIHRoZSB0aGUgZmlsZSBpbiB3aXRoIGJvdGggPHNwYW4gY2xhc3M9ImZ1bmMiPnJlYWRyPC9zcGFuPiBhbmQgPHNwYW4gY2xhc3M9ImZ1bmMiPnJlYWQuY3N2PC9zcGFuPi4NCg0KDQpgYGB7ciByZWFkY3N2LCBlY2hvPUZBTFNFfQ0Kc3VwcHJlc3NNZXNzYWdlcyh7DQptaWNyb2JlbmNobWFyayhyZWFkciA9IHJlYWRfY3N2KCJkYXRhL3Rlc3RyZWFkci5jc3YiLCBwcm9ncmVzcyA9IEYpLA0KICAgICAgICAgICAgICAgYmFzZXIgPSByZWFkLmNzdigiZGF0YS90ZXN0cmVhZHIuY3N2IiksIHRpbWVzPTIwKQ0KfSkNCmBgYA0KDQpUaGUgPHNwYW4gY2xhc3M9InBhY2siPnJlYWRyPC9zcGFuPiBwYWNrYWdlIG1ha2VzIGFzc3VtcHRpb25zIGFib3V0IHRoZSBjb2x1bW4gdHlwZSBiYXNlZCBvbiB0aGUgZmlyc3QgMTAwMCBvYnNlcnZhdGlvbnMsIGJ1dCBvbmUgY2FuIG92ZXJyaWRlIHRoaXMuICBBcyBtZW50aW9uZWQsIGZvciBzbWFsbCBkYXRhIHRoZSBzdGFuZGFyZCBmdW5jdGlvbiBpcyBmaW5lLCBhbmQgZXZlbiBmYXN0ZXIgYnkgZGVmYXVsdC4NCg0KYGBge3IgcmVhZGNzdlNtYWxsLCBlY2hvPUZ9DQpzdXBwcmVzc01lc3NhZ2VzKHsNCm1pY3JvYmVuY2htYXJrKHJlYWRyID0gcmVhZF9jc3YocmVhZHJfZXhhbXBsZSgibXRjYXJzLmNzdiIpKSwNCiAgICAgICAgICAgICAgIGJhc2VyID0gcmVhZC5jc3YocmVhZHJfZXhhbXBsZSgibXRjYXJzLmNzdiIpKSkNCn0pDQpgYGANCg0KDQojIyMgQ2h1bmtlZCANCg0KVGhlIDxzcGFuIGNsYXNzPSJwYWNrIj5yZWFkcjwvc3Bhbj4gcGFja2FnZSBoYXMgY2h1bmtlZCB2ZXJzaW9ucyBvZiB0aG9zZSBzYW1lIGZ1bmN0aW9ucywgc28gdGhhdCBub3QgYWxsIHRoZSBkYXRhIGhhcyB0byBiZSByZWFkIGluIGF0IHRoZSBzYW1lIHRpbWUuICBUaGlzIGlzIGV4dHJlbWVseSBpbXBvcnRhbnQgZm9yIGRhdGEgcHJvY2Vzc2luZy4gIFdoaWxlIG9uZSBtYXkgbm90IGhhdmUgYXMgbXVjaCBjaG9pY2Ugb25jZSB0aGUgYW5hbHlzaXMgc3RhZ2UgaXMgcmVhY2hlZCwgbWFueSBkYXRhIHByb2Nlc3NpbmcgdGFza3MgY2FuIGJlIGNodW5rZWQgb3IgYmUgZG9uZSBsaW5lIGJ5IGxpbmUsIHRoZXJlYnkgb3BlbmluZyBkb29ycyBmb3IgcGFyYWxsZWxpemF0aW9uIGFuZCBtZW1vcnkgY29udHJvbC4NCg0KYGBge3IgcmVhZHJDaHVuaywgZWNobz1GQUxTRX0NCmYgPSBmdW5jdGlvbihkLCBwb3MpIGRwbHlyOjpmaWx0ZXIoZCwgbGV0cz09J2EnKQ0KDQpzdXBwcmVzc01lc3NhZ2VzKHsNCm1pY3JvYmVuY2htYXJrKHJlYWRyID0gZHBseXI6OmZpbHRlcihyZWFkX2NzdignZGF0YS90ZXN0Y2h1bmsuY3N2JywgcHJvZ3Jlc3MgPSBGQUxTRSksIGxldHM9PSdhJyksDQogICAgICAgICAgICAgICBjaHVuayA9IHJlYWRfY3N2X2NodW5rZWQoJ2RhdGEvdGVzdGNodW5rLmNzdicsICBEYXRhRnJhbWVDYWxsYmFjayRuZXcoZnVuY3Rpb24oZCxwb3MpIGRwbHlyOjpmaWx0ZXIoZCwgbGV0cz09J2EnKSksIGNodW5rX3NpemU9MWU2LCBwcm9ncmVzcyA9IEYpLCB0aW1lcyA9IDIwKQ0KfSkNCmBgYA0KDQoNCiMjIGRhdGEudGFibGUNCg0KVGhlIDxzcGFuIGNsYXNzPSJwYWNrIj5kYXRhLnRhYmxlPC9zcGFuPiBwYWNrYWdlIGFsc28gaGFzIGEgcmVhZCBmdW5jdGlvbiB0aGF0IHdpbGwgYW1vdW50IHRvIGZhc3RlciByZWFkIHNwZWVkcy4gVGhlIGZ1bmN0aW9uIDxzcGFuIGNsYXNzPSJmdW5jIj5mcmVhZDwvc3Bhbj4gd29ya3MgbXVjaCBsaWtlIHRoZSBwcmV2aW91cyBmdW5jdGlvbnMgdG8gZGV0ZWN0IGNvbHVtbiB0eXBlcyBxdWlja2x5IGFuZCBvdGhlcndpc2UgaGFzIG9wdGltaXphdGlvbnMgaW4gcGxhY2UgdG8gc3BlZWQgdGhlIHByb2Nlc3MuICBCb3RoIDxzcGFuIGNsYXNzPSJmdW5jIj5yZWFkXyo8L3NwYW4+IGFuZCA8c3BhbiBjbGFzcz0iZnVuYyI+ZnJlYWQ8L3NwYW4+IG1pZ2h0IGJlIHZpYWJsZSBkZXBlbmRpbmcgb24gdGhlIHNpdHVhdGlvbi4gIFdpY2toYW0gW25vdGVzXShodHRwczovL2dpdGh1Yi5jb20vaGFkbGV5L3JlYWRyKSB0aGUgZm9sbG93aW5nIGNvbXBhcmlzb246DQoNCjxkaXYgc3R5bGU9ImZvbnQtc2l6ZTo5MCUiPg0KLSBDb21wYXJlZCB0byBmcmVhZCwgcmVhZHI6DQogDQotIElzIHNsb3dlciAoY3VycmVudGx5IH4xLjItMnggc2xvd2VyLiBJZiB5b3Ugd2FudCBhYnNvbHV0ZWx5IHRoZSBiZXN0IHBlcmZvcm1hbmNlLCB1c2UgZGF0YS50YWJsZTo6ZnJlYWQoKS4NCg0KLSBSZWFkciBoYXMgYSBzbGlnaHRseSBtb3JlIHNvcGhpc3RpY2F0ZWQgcGFyc2VyLCByZWNvZ25pc2luZyBib3RoIGRvdWJsZWQgKCIiIiIpIGFuZCBiYWNrc2xhc2ggZXNjYXBlcyAoIlwiIikuIFJlYWRyIGFsbG93cyB5b3UgdG8gcmVhZCBmYWN0b3JzIGFuZCBkYXRlIHRpbWVzIGRpcmVjdGx5IGZyb20gZGlzay4NCg0KLSBmcmVhZCgpIHNhdmVzIHlvdSB3b3JrIGJ5IGF1dG9tYXRpY2FsbHkgZ3Vlc3NpbmcgdGhlIGRlbGltaXRlciwgd2hldGhlciBvciBub3QgdGhlIGZpbGUgaGFzIGEgaGVhZGVyLCBob3cgbWFueSBsaW5lcyB0byBza2lwIGJ5IGRlZmF1bHQgYW5kIG1vcmUuIFJlYWRyIGZvcmNlcyB5b3UgdG8gc3VwcGx5IHRoZXNlIHBhcmFtZXRlcnMuDQoNCi0gVGhlIHVuZGVybHlpbmcgZGVzaWducyBhcmUgcXVpdGUgZGlmZmVyZW50LiBSZWFkciBpcyBkZXNpZ25lZCB0byBiZSBnZW5lcmFsLCBhbmQgZGVhbGluZyB3aXRoIG5ldyB0eXBlcyBvZiByZWN0YW5ndWxhciBkYXRhIGp1c3QgcmVxdWlyZXMgaW1wbGVtZW50aW5nIGEgbmV3IHRva2VuaXplci4gZnJlYWQoKSBpcyBkZXNpZ25lZCB0byBiZSBhcyBmYXN0IGFzIHBvc3NpYmxlLiBmcmVhZCgpIGlzIHB1cmUgQywgcmVhZHIgaXMgQysrIChhbmQgUmNwcCkuPC9kaXY+DQoNCg0KDQoNCg0KSSB3aWxsIG5vdGUgdGhhdCA8c3BhbiBjbGFzcz0icGFjayI+cmVhZHI8L3NwYW4+IHdhcyBmYXN0ZXIgb24gdGhlIDU0IE1iIGNodW5rIHRlc3QgZmlsZSwgc28geW91IG1heSBuZWVkIHZlcnkgbGFyZ2UgZmlsZXMgYmVmb3JlIDxzcGFuIGNsYXNzPSJmdW5jIj5mcmVhZDwvc3Bhbj4gc3RhcnRzIHRvIHNoaW5lLg0KDQpgYGB7ciBkdENodW5rLCBlY2hvPUZBTFNFLCBldmFsPUZBTFNFfQ0KbGlicmFyeShkYXRhLnRhYmxlKQ0Kc3VwcHJlc3NNZXNzYWdlcyh7DQptaWNyb2JlbmNobWFyayhyZWFkciA9IHJlYWRfY3N2KCdkYXRhL3Rlc3RjaHVuay5jc3YnLCBwcm9ncmVzcyA9IEYpLA0KICAgICAgICAgICAgICAgZnJlYWQgPSBmcmVhZCgnZGF0YS90ZXN0Y2h1bmsuY3N2JyksIHRpbWVzID0yMCkNCn0pDQojIHJlYWRfY3N2KCdkYXRhL3Rlc3RjaHVuay5jc3YnLCBwcm9ncmVzcyA9IEYpDQojIGZyZWFkKCdkYXRhL3Rlc3RjaHVuay5jc3YnKQ0KYGBgDQoNCiMjIExpbmVzIHZzLiBXaG9sZSBEYXRhDQoNCk1hbnkgZG8gbm90IHJlYWxpemUgdGhhdCB0aGV5IGRvbid0IGhhdmUgdG8gcmVhZCBpbiB0aGUgd2hvbGUgZGF0YSBmaWxlLiAgTWFueSBwcmVwcm9jZXNzaW5nIHN0ZXBzIGNhbiBiZSBkb25lIGxpbmUgYnkgbGluZSwgYW5kIHRoaXMgbWF5IHNhdmUgb24gbWVtb3J5IGFuZCBwcm92aWRlIGEgbWVhbnMgb2YgKG1hc3NpdmVseSkgcGFyYWxsZWwgb3BlcmF0aW9ucy4gIEFsc28sIGFuZCBoZXJlIGlzIGEgcG9pbnQgZnVydGhlciBub3QgY29uc2lkZXJlZCBieSBtYW55LCB0aGlzIHByb3ZpZGVzIGEgbWVhbnMgdG8gZGVidWcgeW91ciBjb2RlIGJlZm9yZSBnb2luZyBwcmltZSB0aW1lLiAgWW91ciBmaWxlIG1heSBiZSBodWdlLCBidXQgeW91IGRvbid0IGhhdmUgdG8gd29yayB3aXRoIHRoZSB3aG9sZSB0aGluZyB0byBnZXQgeW91ciBjb2RlIHNvcnRlZCBvdXQuICBTZWUgPHNwYW4gY2xhc3M9ImZ1bmMiPnJlYWRMaW5lczwvc3Bhbj4gaW4gYmFzZSBSIGZvciBkZXRhaWxzLCBidXQgeW91J2Qgd2FudCB0byB1c2UgPHNwYW4gY2xhc3M9ImZ1bmMiPnJlYWRfbGluZXM8L3NwYW4+IGluIDxzcGFuIGNsYXNzPSJwYWNrIj5yZWFkcjwvc3Bhbj4uDQoNCg0KIyMgT3RoZXINCg0KIyMjIGZlYXRoZXINCg0KWWV0IGFub3RoZXIgYWx0ZXJuYXRpdmUgaXMgdG8gdXNlIGEgZGlmZmVyZW50IGRhdGEgZm9ybWF0IGFsdG9nZXRoZXIuICBXaWNraGFtIGFuZCBXZXMgTWNLaW5uZXkgKHRoZSBsYXR0ZXIgaXMgYmVoaW5kIFB5dGhvbidzIDxzcGFuIGNsYXNzPSJwYWNrIj5wYW5kYXM8L3NwYW4+IG1vZHVsZSkgYXJlIHdvcmtpbmcgb24gPHNwYW4gY2xhc3M9InBhY2siPmZlYXRoZXI8L3NwYW4+LCBhIGJpbmFyeSBkYXRhIGZvcm1hdCB0aGF0IHdvdWxkIGJlIHJlYWQgaW4gUiAqb3IqIFB5dGhvbiwgYW5kIGFsbG93IGZvciB2ZXJ5IGZhc3QgcmVhZC93cml0ZSBvcGVyYXRpb25zLCBhcyB3ZWxsIGFzIHNtYWxsZXIgZmlsZSBzaXplcywgYW5kIG1vcmUgaW50ZXJvcGVyYWJpbGl0eSBiZXR3ZWVuIHRoZSB0d28gbGFuZ3VhZ2VzLiAgU2VlIFt0aGlzIGxpbmtdKGh0dHBzOi8vYmxvZy5yc3R1ZGlvLm9yZy8yMDE2LzAzLzI5L2ZlYXRoZXIvKSBmb3IgbW9yZSBkZXRhaWxzLiAgVGhlIGZvbGxvd2luZyBjb21wYXJlcyB0aW1lcyB1c2luZyBmZWF0aGVyIHZzLiB0aGUgPHNwYW4gY2xhc3M9InBhY2siPnJlYWRyPC9zcGFuPiBjb3VudGVycGFydHMuDQoNCmBgYHtyIGZlYXRoZXJUZXN0LCBlY2hvPUZBTFNFfQ0KbGlicmFyeShmZWF0aGVyKQ0KbWljcm9iZW5jaG1hcmsod3JpdGVfY3N2ID0gd3JpdGVfY3N2KGV4cGFuZC5ncmlkKG51bXM9cm5vcm0oMWU0KSwgbGV0cz1sZXR0ZXJzKSwgJ2RhdGEvdGVzdHJlYWRyLmNzdicpLA0KICAgICAgICAgICAgICAgd3JpdGVfZmVhdGhlciA9IHdyaXRlX2ZlYXRoZXIoZXhwYW5kLmdyaWQobnVtcz1ybm9ybSgxZTQpLCBsZXRzPWxldHRlcnMpLCAnZGF0YS90ZXN0ZmVhdGhlci5mZWF0aGVyJyksIHRpbWVzPTIwKQ0KbWljcm9iZW5jaG1hcmsocmVhZF9jc3YgPSByZWFkX2NzdignZGF0YS90ZXN0cmVhZHIuY3N2JywgcHJvZ3Jlc3MgPSBGKSwNCiAgICAgICAgICAgICAgIHJlYWRfZmVhdGhlciA9IHJlYWRfZmVhdGhlcignZGF0YS90ZXN0ZmVhdGhlci5mZWF0aGVyJyksIHRpbWVzPTIwKQ0KYGBgDQoNCg0KDQojIExvb3BzIGFuZCBBbHRlcm5hdGl2ZXMNCg0KIyMgTG9vcHMNCg0KQmVmb3JlIGdldHRpbmcgdG8gYWx0ZXJuYXRpdmUgbWV0aG9kcywgd2UnbGwgZmlyc3QgZG8gdGhpbmdzIHdpdGggYSBzdGFuZGFyZCBsb29wLCBhbmQgdGhlbiBzaG93IG90aGVycyBvcHRpb25zIGxhdGVyLiAgTG9vcHMgaW4gYW5kIG9mIHRoZW1zZWx2ZXMgYXJlIG5vdCBhIHByb2JsZW0gaW4gUiwgbm9yIGFyZSB0aGV5IG5lY2Vzc2FyaWx5IHNsb3cgZm9yIHNvbWUgdGFza3MuIEl0J3MganVzdCB0aGF0IHRoZXkganVzdCBvZnRlbiBoYXZlIG1vcmUgZWZmaWNpZW50IGFsdGVybmF0aXZlcywgd2hldGhlciBpdCBiZSBtb3JlIHN1Y2NpbmN0IGNvZGUsIG9yIHBvc3NpYmx5IHZhc3RseSBxdWlja2VyIGNvbXB1dGF0aW9uLg0KDQpBcyBvbmUgb2Ygb3VyIHdvcmtpbmcgZXhhbXBsZXMsIHdlJ2xsIHN0YXJ0IHdpdGggYSBmdW5jdGlvbiB0aGF0IGRvZXMgYSByYW5kb20gd2Fsay4gVGhlIGNvZGUgaXMgYmFzZWQgb24gW3RoaXMgZG9jdW1lbnRdKGh0dHBzOi8vd3d3LnN0YXQuYXVja2xhbmQuYWMubnovfmloYWthL2Rvd25sb2Fkcy9UYXVwby1oYW5kb3V0cy5wZGYpLCBjby1hdXRob3JlZCBieSBvbmUgb2YgdGhlIFIncyBpbiBSLCB3aXRoIHNvbWUgc2xpZ2h0IGFkZGl0aW9ucyBhbmQgbW9kaWZpY2F0aW9ucy4gDQoNCmBgYHtyIGxvb3Bfbm9wcmV9DQpydzJkX2xvb3Bfbm9wcmUgPC0gZnVuY3Rpb24obikgew0KICB4cG9zID0geXBvcyA9IDANCiAgeGRpciA9IGMoVCwgRikNCiAgcG0xID0gYygxLC0xKQ0KICANCiAgZm9yIChpIGluIDI6bikNCiAgew0KICAgIGlmIChzYW1wbGUoeGRpciwgMSkpIHsNCiAgICAgIHhwb3NbaV0gPSB4cG9zW2ktMV0gKyBzYW1wbGUocG0xLCAxKQ0KICAgICAgeXBvc1tpXSA9IHlwb3NbaS0xXQ0KICAgIH0NCiAgICBlbHNlIHsNCiAgICAgIHhwb3NbaV0gPSB4cG9zW2ktMV0NCiAgICAgIHlwb3NbaV0gPSB5cG9zW2ktMV0gKyBzYW1wbGUocG0xLCAxKQ0KICAgIH0NCiAgfQ0KICBkYXRhLmZyYW1lKHg9eHBvcywgeT15cG9zKSANCn0NCg0KIyBydzJkX2xvb3Bfbm9wcmUoMWU1KSAjIGZvciBwcm9maWxpbmcNCiMgZ2dwbG90Mjo6cXBsb3QoeCwgeSwgZGF0YT1ydzJkX2xvb3Bfbm9wcmUoMTAwMCksIGdlb209J3BhdGgnKSAjIHBsb3QgY2hlY2sNCmBgYA0KYGBge3IgcGxvdGxvb3AxLCBlY2hvPUZBTFNFfQ0KZ2dwbG90Mjo6cXBsb3QoeCwgeSwgZGF0YT1ydzJkX2xvb3Bfbm9wcmUoMTAwMCksIGdlb209J3BhdGgnLCBjb2w9SSgnb3JhbmdlJykpICsgbGF6ZXJoYXdrOjp0aGVtZV90cnVlTWluaW1hbCgpICMgcGxvdCBjaGVjaw0KYGBgDQoNCg0KRm9yIGJldHRlciB1bmRlcnN0YW5kaW5nIG9mIHdoYXQncyBnb2luZyBvbiwgeW91IGNhbiB1c2UgdGhlIGRlYnVnIGZ1bmN0aW9uYWxpdHkgb24gdGhlIGZ1bmN0aW9ucyB1c2VkIHRvIHNlZSB3aGF0IHRoZXkgYXJlIGRvaW5nIGxpbmUgYnkgbGluZS4gUnN0dWRpbyBtYWtlcyB0aGlzIGVzcGVjaWFsbHkgZWFzeSwgYW5kIHRvIGdldCBzdGFydGVkIG9uZSBjYW4gdXNlIGNvZGUgdGhhdCBsb29rcyBsaWtlIHRoZSBmb2xsb3dpbmcuDQoNCmBgYHtyIGRlYnVnLCBldmFsPUZBTFNFfQ0KZGVidWdvbmNlKHJ3MmRfbG9vcF9ub3ByZSkNCnJ3MmRfbG9vcF9ub3ByZSgxMDAwKQ0KYGBgDQoNCllvdSB3aWxsIGJlIGFibGUgdG8gc2VlIHdoYXQncyBwcm9kdWNlZCBhbmQgZXZlbiBtYW5pcHVsYXRlIHRob3NlIG9iamVjdHMgYXQgZWFjaCBzdGVwLg0KDQoNCiMjIyBQcmUtYWxsb2NhdGlvbg0KDQpPbmUgdGhpbmcgeW91J2xsIHdhbnQgdG8gbm90ZSwgaWYgeW91IG11c3QgdXNlIGFuIGV4cGxpY2l0IGxvb3AsIGZpcnN0IGNyZWF0ZSBhbiBlbXB0eSB2ZXNzZWwgdG8gY29udGFpbiB0aGUgZWxlbWVudHMgb2YgdGhlIGxvb3BzIG91dHB1dCwgcmF0aGVyIHRoYW4gdGFraW5nIGFuIGFwcGVuZC1hcy15b3UtZ28gYXBwcm9hY2guICBUaGUgcmVhc29uaW5nIGlzIHNpbWlsYXIgdG8gdGhlIHJlYXNvbmluZyBiZWhpbmQgW3ZlY3Rvcml6YXRpb25dKCN2ZWN0b3JpemF0aW9uKSBub3RlZCBsYXRlci4gIEJ5IG5vdCBoYXZpbmcgUiBkbyBzb21lIChpbnRlcm5hbCkgb3BlcmF0aW9ucyBldmVyeSBzaW5nbGUgaXRlcmF0aW9uLCB5b3Ugc2F2ZSB0aW1lLCBhbmQgaXQgYWRkcyB1cC4gTWVtb3J5IGlzIGFsc28gYWxyZWFkeSBtYWRlIGF2YWlsYWJsZSB0byB0aGUgb2JqZWN0Lg0KDQpJbiB0aGUgZm9sbG93aW5nIHdlJ2xsIGNvbXBhcmUgdGhlIHJhbmRvbSB3YWxrIGJvdGggd2l0aCBhbmQgd2l0aG91dCBwcmUtYWxsb2NhdGlvbi4gSSBoYXZlIGEgbGluZSBmb3IgZWFjaCBmdW5jdGlvbiBzbyB5b3UgY2FuIHVzZSB0aGVtIGZvciA8c3BhbiBjbGFzcz0iZW1waCI+cHJvZmlsaW5nPC9zcGFuPiwgdG8gc2VlIHdoZXJlIGJvdHRsZW5lY2tzIGFyaXNlIHNwZWNpZmljYWxseS4gIEluIChuZXdlciB2ZXJzaW9ucyBvZikgUlN0dWRpbywgeW91IGNhbiBzaW1wbHkgaGlnaGxpZ2h0IHRoYXQgbGluZSBhbmQgaGl0IEN0cmwrQWx0K1NoZnQrUCB0byBkbyBzby4gQWxzbywgZm9yIHRoZSBmaXJzdCBkZW1vbnN0cmF0aW9uIGFib3ZlIEkgc2hvd2VkIGFuIGV4YW1wbGUgZ3JhcGgsIGJ1dCBhbGwgb3RoZXJzIHdpbGwgbG9vayBsaWtlIHNvbWUgKHJhbmRvbSkgdmVyc2lvbiBvZiB0aGF0LCBzbyBhcmUgc3Vic2VxdWVudGx5IGNvbW1lbnRlZCBvdXQgaW4gdGhlIGNvZGUuDQoNCmBgYHtyIGxvb3BfcHJlfQ0KIyBwcmVhbGxvY2F0aW9uDQpydzJkX2xvb3BfcHJlIDwtIGZ1bmN0aW9uKG4pIHsNCiAgeHBvcyA9IHlwb3MgPSBudW1lcmljKG4pDQogIHhkaXIgPSBjKFQsIEYpDQogIHBtMSA9IGMoMSwtMSkNCiAgDQogIGZvciAoaSBpbiAyOm4pDQogIHsNCiAgICBpZiAoc2FtcGxlKHhkaXIsIDEpKSB7DQogICAgICB4cG9zW2ldID0geHBvc1tpLTFdICsgc2FtcGxlKHBtMSwgMSkNCiAgICAgIHlwb3NbaV0gPSB5cG9zW2ktMV0NCiAgICB9DQogICAgZWxzZSB7DQogICAgICB4cG9zW2ldID0geHBvc1tpLTFdDQogICAgICB5cG9zW2ldID0geXBvc1tpLTFdICsgc2FtcGxlKHBtMSwgMSkNCiAgICB9DQogIH0NCiAgZGF0YS5mcmFtZSh4PXhwb3MsIHk9eXBvcykNCn0NCg0KIyBydzJkX2xvb3BfcHJlKDFlNSkgIyBmb3IgcHJvZmlsaW5nDQojIGdncGxvdDI6OnFwbG90KHgsIHksIGRhdGE9cncyZF9sb29wX3ByZSgxMDAwKSwgZ2VvbT0ncGF0aCcpDQpgYGANCg0KYGBge3IgcHJlQWxsb0JlbmNoLCBlY2hvPUZBTFNFfQ0KbWljcm9iZW5jaG1hcmsocncyZF9sb29wX25vcHJlKDEwMDApLCBydzJkX2xvb3BfcHJlKDEwMDApKQ0KYGBgDQoNCkFzIHdlIGNhbiBzZWUsIGV2ZW4gd2l0aCB0aGlzIHF1aWNrIGV4YW1wbGUgcHJlLWFsbG9jYXRpb24gaXMgYWxyZWFkeSBzYXZpbmcgc29tZSB0aW1lLiAgDQoNCiMjIyBTbWFsbGVyIGNvZGUgIT0gZmFzdGVyDQoNCk5vdGUgdGhhdCB0aGUgZ29hbCBpcyBmYXN0IHJ1bm5pbmcgY29kZSwgYnV0IHRoaXMgZG9lc24ndCBtZWFuIHRoZXJlIGlzIGEgb25lLXRvLW9uZSBjb3JyZWxhdGlvbiBiZXR3ZWVuIHNwZWVkIGFuZCBjb2RlIHNpemUuICBUaGUgZm9sbG93aW5nIGlzIGEgcmVjdXJzaXZlIHZlcnNpb24gb2YgdGhlIGFib3ZlIGFuZCBpdCdzIHRocmVlIGxpbmVzIG9mIGNvZGUuICBJdCBpcyBhIGxpdHRsZSBmYXN0ZXIgdGhhbiB0aGUgbm9uLXByZS1hbGxvY2F0ZWQgbG9vcCwgYnV0IHNsb3dlciB0aGFuIG9uZSB3aXRoIHByZS1hbGxvY2F0aW9uLiAgSSBtaWdodCBhbHNvIG1lbnRpb24gdGhhdCBSIGlzIG5vdCByZWFsbHkgdGhhdCBncmVhdCBmb3IgcmVjdXJzaXZlIGZ1bmN0aW9ucyBpbiBteSBleHBlcmllbmNlLCBvZnRlbiAnbmVzdGluZyB0b28gZGVlcGx5JyB3aGVyZSBvdGhlciBsYW5ndWFnZXMgaGF2ZSBubyBpc3N1ZS4NCg0KYGBge3IgcmVjdXJzaXZlfQ0KcncyZDJfcmVjdXJzaXZlIDwtIGZ1bmN0aW9uKG4sIHg9MCwgeT0wKSB7DQogIGlmKG4gPT0gMSkgcmV0dXJuKGN1bXN1bShkYXRhLmZyYW1lKHg9eCwgeT15KSkpDQogIHN0ZXAgPSBzYW1wbGUoMTo0LCAxKQ0KICBydzJkMl9yZWN1cnNpdmUobj1uLTEsIA0KICAgICAgICAgICAgICAgICAgeD1jKHgsIGMoLTEsIDEsIDAsIDApW3N0ZXBdKSwgDQogICAgICAgICAgICAgICAgICB5PWMoeSwgYygwLCAwLCAtMSwgMSlbc3RlcF0pKQ0KfQ0KDQojIGNhbm5vdCBiZSBwcm9maWxlZA0KIyBnZ3Bsb3QyOjpxcGxvdCh4LCB5LCBkYXRhPXJ3MmQyX3JlY3Vyc2l2ZSgxMDAwKSwgZ2VvbT0ncGF0aCcpDQpgYGANCg0KYGBge3IgbG9vcHNDb21wYXJlLCBlY2hvPUZBTFNFfQ0KbWljcm9iZW5jaG1hcmsocncyZF9sb29wX25vcHJlKDEwMDApLA0KICAgICAgICAgICAgICAgcncyZF9sb29wX3ByZSgxMDAwKSwNCiAgICAgICAgICAgICAgIHJ3MmQyX3JlY3Vyc2l2ZSgxMDAwKSkNCmBgYA0KDQpMb29rcyBjYW4gYmUgZGVjZWl2aW5nIQ0KDQojIyMgRG91YmxlIGxvb3BzDQoNCkRvdWJsZSBsb29wcyBmb3IgaW5kZXBlbmRlbnQgb3BlcmF0aW9ucyBhcmUgYWxtb3N0IGFsd2F5cyBhbiBpbmVmZmljaWVudCB3YXkgdG8gdXNlIFIsIGVzcGVjaWFsbHkgZm9yIGNvbW1vbiBkYXRhIHByb2Nlc3NpbmcgdGFza3MsIHNvIGlmIHlvdSBmaW5kIHlvdXJzZWxmIHVzaW5nIG9uZSwgeW91IHNob3VsZCBwcm9iYWJseSB0aGluayB2ZXJ5IGhhcmQgYWJvdXQgd2hhdCBhbHRlcm5hdGl2ZXMgbWlnaHQgYmUgcG9zc2libGUuICBJbiB0aGlzIGV4YW1wbGUgd2UgY3JlYXRlIGEgZGlzdGFuY2UgbWF0cml4IGJhc2VkIG9uIHRoZSBFdWNsaWRlYW4gZGlzdGFuY2UgYmV0d2VlbiByb3dzIGluIGEgZ2l2ZW4gbWF0cml4IGBtYCwgd2hpY2ggZm9yIHRpbWluZyBkZW1vbnN0cmF0aW9uIHdpbGwgYmUgYSAxMDAgeCAxMDAgbWF0cml4Lg0KDQpgYGB7ciBkbG9vcHMsIGNhY2hlPVRSVUV9DQpkb3VibGVMb29wRGlzdCA8LSBmdW5jdGlvbihtKSB7DQogIG4gPSBucm93KG0pDQogIGRpc3RzID0gbWF0cml4KDAsIG5jb2w9biwgbnJvdz1uKQ0KICBmb3IgKGkgaW4gMTpuKXsNCiAgICBmb3IgKGogaW4gMTpuKXsNCiAgICAgIGRpc3RzW2ksal0gPSBzcXJ0KHN1bSgobVtpLF0gLSBtW2osXSleMikpDQogICAgfQ0KICB9DQogIGRpc3RzDQp9DQoNCg0KZCA9IG1hdHJpeChybm9ybSgxMDAwMCksIG5jb2w9MTAwKQ0KIyBkb3VibGVMb29wRGlzdChkKQ0KYGBgDQoNCkFzIHdlJ2xsIHNlZSBpbiBhIG1vbWVudCwgdGhpcyBpcyB2ZXJ5IGluZWZmaWNpZW50LCBhbmQgSSB3b3VsZCBhZ2FpbiBzYXkgdGhlcmUgaXMgcmFyZWx5IGEgbmVlZCB0byBhIGRvdWJsZSBsb29wLiAgRXZlbiBpZiB5b3UgaGF2ZSB0byBkb3VibGUgbG9vcCwgdGhlcmUgbWlnaHQgYmUgYW4gZWZmaWNpZW5jeSBnYWluIHBvc3NpYmxlLiAgU2luY2UgdGhlIGRpc3RhbmNlIG1hdHJpeCBpcyBzeW1tZXRyaWMsIHdlIG9ubHkgbmVlZCB0byBjb21wdXRlIGhhbGYgb2YgaXQsIHRoZW4gZmlsbCBpbiB0aGUgcmVzdC4gVGhpcyB3b3VsZCBhdCBsZWFzdCBjdXQgdGhlIHRpbWUgaW4gaGFsZi4NCg0KYGBge3IgZGxvb3AyfQ0KZG91YmxlTG9vcERpc3QyIDwtIGZ1bmN0aW9uKG0pIHsNCiAgbiA9IG5yb3cobSkNCiAgZGlzdHMgPSBtYXRyaXgoMCwgbmNvbD1uLCBucm93PW4pDQogIGZvciAoaSBpbiAxOihuLTEpKXsNCiAgICBmb3IgKGogaW4gKGkrMSk6bil7DQogICAgICBkaXN0c1tpLGpdID0gc3FydChzdW0oKG1baSxdIC0gbVtqLF0pXjIpKQ0KICAgIH0NCiAgfQ0KICANCiAgZGlzdHMgPSBkaXN0cyArIHQoZGlzdHMpICsgZGlhZyhkaWFnKGRpc3RzKSkNCiAgZGlhZyhkaXN0cykgPSAwDQogIGRpc3RzDQp9DQoNCmlkZW50aWNhbChkb3VibGVMb29wRGlzdChkKSwgZG91YmxlTG9vcERpc3QyKGQpKQ0KYGBgDQoNCmBgYHtyIGVjaG89RkFMU0V9DQptaWNyb2JlbmNobWFyayhkbG9vcDEgPSBkb3VibGVMb29wRGlzdChkKSwgZGxvb3AyID0gZG91YmxlTG9vcERpc3QyKGQpKQ0KYGBgDQoNCkxhdGVyIG9uIHdlJ2xsIHNlZSBqdXN0IGhvdyBzbG93IHRoaXMgaXMgd2hlbiB3ZSBjb21wYXJlIGl0IHRvIHRoZSBiYXNlIFIgPHNwYW4gY2xhc3M9ImZ1bmMiPmRpc3Q8L3NwYW4+IGZ1bmN0aW9uLCB3aGljaCB1c2VzIGNvbXBpbGVkIEMgY29kZS4NCg0KIyMgQXBwbHkNCg0KQSBzZXQgb2YgZnVuY3Rpb25zIGV4aXN0cyBpbiBSIHRoYXQgdHlwaWNhbGx5IG1ha2UgZXhwbGljaXQgbG9vcHMgdW5uZWNlc3NhcnksIGFuZCBjYW4gcmVkdWNlIHByb2dyYW1taW5nIHRpbWUsIGFuZCBwb3RlbnRpYWxseSBtYWtlIGNvZGUgY2xlYW5lci4gRnVydGhlcm1vcmUsIHRoZXkgYXJlIHBhcmFsbGVsaXphYmxlLCBhbmQgc28gcG90ZW50aWFsbHkgZmFyIGZhc3Rlci4gIFRoZXJlIGlzIGEgbWlzY29uY2VwdGlvbiB0aGF0IHRoZXNlIGZ1bmN0aW9ucyBhcmUgZmFzdGVyIHRoYW4gbG9vcHMgb3V0LW9mLXRoZS1ib3gsIGJ1dCB0aGlzIGlzIGluY29ycmVjdCwgYW5kIHRoZXkgdGVjaG5pY2FsbHkgY2FuIGV2ZW4gYmUgc2xvd2VyLiAgQWdhaW4gdGhvdWdoLCB5b3UgYXV0b21hdGljYWxseSBnYWluIGluIGNvZGluZyBlZmZpY2llbmN5IGFuZCBwb3NzaWJseSBnYWluIGEgbG90IGluIGNvbXB1dGF0aW9uIHRpbWUgd2l0aCB0aGUgdXNlIG9mIHBhcmFsbGVsaXphdGlvbi4NCg0KIyMjIGFwcGx5IGZ1bmN0aW9ucw0KDQotIDxzcGFuIGNsYXNzPSJmdW5jIj5hcHBseTwvc3Bhbj46IGFycmF5cywgbWF0cmljZXMsIGRhdGEuZnJhbWVzDQotIDxzcGFuIGNsYXNzPSJmdW5jIj5sYXBwbHk8L3NwYW4+LCA8c3BhbiBjbGFzcz0iZnVuYyI+c2FwcGx5PC9zcGFuPiwgPHNwYW4gY2xhc3M9ImZ1bmMiPnZhcHBseTwvc3Bhbj46IGxpc3RzLCBkYXRhLmZyYW1lcywgdmVjdG9ycw0KLSA8c3BhbiBjbGFzcz0iZnVuYyI+dGFwcGx5PC9zcGFuPjogZ3JvdXBlZCBvcGVyYXRpb25zICh0YWJsZSBhcHBseSkNCi0gPHNwYW4gY2xhc3M9ImZ1bmMiPm1hcHBseTwvc3Bhbj46IG11bHRpdmFyaWF0ZSB2ZXJzaW9uIG9mIHNhcHBseQ0KLSA8c3BhbiBjbGFzcz0iZnVuYyI+cmVwbGljYXRlPC9zcGFuPjogc2ltaWxhciB0byBzYXBwbHkNCg0KQXMgYSBzaW1wbGUgZXhhbXBsZSwgbGV0J3MgZXN0aW1hdGUgc29tZSBjb2x1bW4gbWVhbnMuIEFuIGV4cGxpY2l0IGxvb3AgbWlnaHQgbG9vayBsaWtlIHRoZSBmb2xsb3dpbmcuDQoNCmBgYHtyIGNvbE1lYW5zTG9vcH0NCm1lYW5zX2xvb3AgPSByZXAoMCwgbmNvbChkKSkgICMgaW5pdGlhbGl6ZSB0aGUgbWVhbnMgdmVjdG9yDQpmb3IgKG4gaW4gMTpuY29sKGQpKXsNCiAgbWVhbnNfbG9vcFtuXSA9IG1lYW4oZFssbl0pDQp9DQpoZWFkKG1lYW5zX2xvb3ApDQpgYGANCg0KYGBge3IgY29sTWVhbnNMb29wRnVuYywgZWNobz1GfQ0KIyBiZWNhdXNlIGVjaG9pbmcgc3BlY2lmaWMgbGluZXMgZG9lc24ndCB3b3JrIHdpdGggbm90ZWJvb2tzIGFwcGFyZW50bHkNCm1lYW5zX2xvb3BfZnVuYyA8LSBmdW5jdGlvbihkKSB7DQogIG1lYW5zID0gcmVwKDAsIG5jb2woZCkpDQogIGZvciAobiBpbiAxOm5jb2woZCkpew0KICAgIG1lYW5zW25dID0gbWVhbihkWyxuXSkNCiAgfQ0KICBtZWFucw0KfQ0KYGBgDQoNCkxldCdzIHVzZSB0aGUgPHNwYW4gY2xhc3M9ImZ1bmMiPmFwcGx5PC9zcGFuPiBmdW5jdGlvbiBpbnN0ZWFkLiAgVGhlIHByaW1hcnkgYXJndW1lbnRzIGFyZSBhIG1hdHJpeC9kYXRhLmZyYW1lIChvciBhbnkgYXJyYXkpLCB0aGUgbWFyZ2luIHRvIGl0ZXJhdGUgb3ZlciAoZS5nLiByb3dzIG9yIGNvbHVtbnMpLCBhbmQgdGhlIGZ1bmN0aW9uIHdlIHdhbnQgdG8gYXBwbHksIHdoaWNoIGluIHRoaXMgY2FzZSBpcyB0aGUgbWVhbi4NCg0KYGBge3IgIGNvbE1lYW5zQXBwbHl9DQptZWFuc19hcHBseSA9IGFwcGx5KGQsIDIsIG1lYW4pDQppZGVudGljYWwobWVhbnNfbG9vcCwgbWVhbnNfYXBwbHkpDQpgYGANCg0KQW5kIHRoYXQncyBhbGwgdGhlcmUgaXMgdG8gaXQuICBBIHBvaW50IG9mIGVtcGhhc2lzIGhvd2V2ZXI6ICp0aGVyZSBpcyBubyBndWFyYW50ZWVkIHNwZWVkIGdhaW4gaGVyZSosIG9ubHkgbW9yZSBzdWNjaW5jdCBjb2RlLiBUaGUgZm9sbG93aW5nIGRlbW9uc3RyYXRlcyB1c2luZyBhIGxvb3AgdnMuIGFwcGx5IG9uIGEgMTAwMHgxMDAwIG1hdHJpeC4gRm9yIGEgc2ltcGxlIG9wZXJhdGlvbiBsaWtlIHRoaXMsIHRoZSBleHBsaWNpdCBsb29wIGlzIGFjdHVhbGx5IGZhc3Rlci4gIEhvd2V2ZXIsIG1vc3Qgd291bGQgbm90IHdhbnQgdG8gd3JpdGUgYSBsb29wIGV2ZXJ5IHRpbWUgdGhleSB3YW50IGNvbHVtbiBvciByb3cgbWVhbnMsIGFuZCBhcyB3ZSdsbCBzZWUgbGF0ZXIsIHdlJ2QgdXNlIGEgdmVjdG9yaXplZCBhcHByb2FjaCByYXRoZXIgdGhhbiBlaXRoZXIgb2YgdGhlc2UuDQoNCmBgYHtyIGNvbE1lYW5zQ29tcGFyZSwgZWNobz1GfQ0KeCA9IG1hdHJpeChybm9ybSgxZTYpLCBuY29sPTFlMykNCm1pY3JvYmVuY2htYXJrKG1lYW5zX2xvb3AgPSBtZWFuc19sb29wX2Z1bmMoeCksIA0KICAgICAgICAgICAgICAgbWVhbnNfYXBwbHkgPSBhcHBseSh4LCAyLCBtZWFuKSkNCmBgYA0KDQoNCiMjIyBwbHlyIGFsdGVybmF0ZXMNCg0KVGhlIDxzcGFuIGNsYXNzPSJwYWNrIj5wbHlyPC9zcGFuPiBwYWNrYWdlIHByb3ZpZGVzIGFsdGVybmF0aXZlcyB0byB0aGUgYXBwbHkgZmFtaWx5IG9mIGZ1bmN0aW9ucy4gVGhlc2UgcGx5ciBmdW5jdGlvbnMgd29yayBiYXNlZCBvbiB0aGUgZmlyc3QgdHdvIGxldHRlcnMuIFRoZSBmaXJzdCBkZW5vdGVzIHRoZSBpbnB1dCwgdGhlIHNlY29uZCB0aGUgb3V0cHV0LiAgRm9yIGV4YW1wbGUsIDxzcGFuIGNsYXNzPSJmdW5jIj5sZHBseTwvc3Bhbj4gdGFrZXMgYSA8c3BhbiBjbGFzcz0ib2JqY2xhc3MiPmxpc3Q8L3NwYW4+IGFuZCBjb252ZXJ0cyB0aGUgb3V0cHV0IHRvIGEgPHNwYW4gY2xhc3M9Im9iamNsYXNzIj5kYXRhLmZyYW1lPC9zcGFuPi4NCg0KLSBMaXN0czogPHNwYW4gY2xhc3M9ImZ1bmMiPmxkcGx5PC9zcGFuPiwgPHNwYW4gY2xhc3M9ImZ1bmMiPmxscGx5PC9zcGFuPiwgPHNwYW4gY2xhc3M9ImZ1bmMiPmxhcGx5PC9zcGFuPg0KDQotIEFycmF5czogPHNwYW4gY2xhc3M9ImZ1bmMiPmEqcGx5PC9zcGFuPg0KDQotIERhdGFmcmFtZXM6IDxzcGFuIGNsYXNzPSJmdW5jIj5kKnBseTwvc3Bhbj4NCg0KLSBNdWx0aXBsZSBhcmd1bWVudHM6IDxzcGFuIGNsYXNzPSJmdW5jIj5tKnBseTwvc3Bhbj4NCg0KQXMgYW4gZXhhbXBsZSB3aWxsIHVzZSA8c3BhbiBjbGFzcz0iZnVuYyI+YWRwbHk8L3NwYW4+IG9uIHRoZSBjb2x1bW4gbWVhbiBleGFtcGxlLiAgVGhlIDxzcGFuIGNsYXNzPSJvYmpjbGFzcyI+ZDwvc3Bhbj4gb2JqZWN0IGlzIGEgPHNwYW4gY2xhc3M9Im9iamNsYXNzIj5tYXRyaXg8L3NwYW4+LCBhbmQgd2UnbGwgZ2V0IGEgPHNwYW4gY2xhc3M9Im9iamNsYXNzIj5kYXRhLmZyYW1lPC9zcGFuPiBhcyBvdXRwdXQuDQoNCmBgYHtyIHBseXJ9DQpsaWJyYXJ5KHBseXIpDQphZHBseShkLCAyLCBtZWFuKQ0KYGBgDQoNClVuZm9ydHVuYXRlbHksIHRoZSBmbGV4aWJpbGl0eSBkb2VzIGNvbWUgYXQgYSBwcmljZSwgYW5kIDxzcGFuIGNsYXNzPSJwYWNrIj5wbHlyPC9zcGFuPiBmdW5jdGlvbnMgYXJlIHZlcnkgc2xvdyAobW9zdGx5IGJlY2F1c2UgKjxzcGFuIGNsYXNzPSJvYmpjbGFzcyI+ZGF0YS5mcmFtZXM8L3NwYW4+IGFyZSBzbG93KikuICBVc2luZyB0aGUgMTAwMHgxMDAwIG1hdHJpeCBhZ2FpbiwgYW5kIHVzaW5nIDxzcGFuIGNsYXNzPSJmdW5jIj5hYXBseTwvc3Bhbj4gdG8gYmUgbW9yZSBjb21wYXJhYmxlLCB3ZSBzZWUgdGhlIDxzcGFuIGNsYXNzPSJwYWNrIj5wbHlyPC9zcGFuPiBmdW5jdGlvbiBpcyBtdWNoIHNsb3dlci4NCg0KYGBge3IgcGx5ckNvbXBhcmlzb24sIGVjaG89RkFMU0V9DQptaWNyb2JlbmNobWFyayhtZWFuc19sb29wID0gbWVhbnNfbG9vcF9mdW5jKHgpLCANCiAgICAgICAgICAgICAgIG1lYW5zX2FwcGx5ID0gYXBwbHkoeCwgMiwgbWVhbiksDQogICAgICAgICAgICAgICBhYXBseSA9IGFhcGx5KHgsIDIsIG1lYW4pKQ0KYGBgDQoNCkhvd2V2ZXIsIHRoZXJlIGlzIGNvbXBhcmFibGUgZnVuY3Rpb25hbGl0eSBmb3IgPHNwYW4gY2xhc3M9Im9iamNsYXNzIj5kYXRhLmZyYW1lczwvc3Bhbj4gaW4gPHNwYW4gY2xhc3M9InBhY2siPmRwbHlyPC9zcGFuPiB0aGF0IHdvdWxkIGJlIG11Y2ggZmFzdGVyLg0KDQoNCiMjIyBQYXJhbGxlbCB2ZXJzaW9ucw0KDQpBbm90aGVyIHRoaW5nIHRoYXQgcHV0cyB0aGUgYXBwbHkgYXBwcm9hY2ggYWhlYWQgb2YgbG9vcHMgcmVnYXJkcyBwYXJhbGxlbGl6YXRpb24uICBNb3N0IG9mIHRoZSBiYXNlIFIgYXBwbHkgZnVuY3Rpb25zIGhhdmUgcGFyKiBjb3VudGVycGFydHMsIGUuZy4gcGFyQXBwbHksIHBhckxhcHBseSBldGMuICBUaGlzIGlzIGFsc28gdGhlIGNhc2UgZm9yIHBseXIgZnVuY3Rpb25zLCB3aGljaCBoYXZlIGEgYC5wYXJyYWxsZWw9VFJVRWAgYXJndW1lbnQuICBFeGFtcGxlIGNvZGUgd291bGQgbGlrZSB0aGUgZm9sbG93aW5nLg0KDQpgYGB7ciBwYXJEZW1vLCBldmFsPUZBTFNFfQ0KeCA9IG1hdHJpeChybm9ybSgxZTcpLCBuY29sPTFlNikNCmxpYnJhcnkocGFyYWxsZWwpDQpjbCA9IG1ha2VDbHVzdGVyKDgpDQpjbHVzdGVyRXhwb3J0KGNsLCAneCcpDQptZWFucyA9IHBhckFwcGx5KGNsLCB4LCAyLCBtZWFuKQ0Kc3RvcENsdXN0ZXIoY2wpDQpgYGANCg0KRm9yIHRoZSBwbHlyIGZ1bmN0aW9ucywgb25lIG5lZWRzIHRvIHVzZSB0aGUgZm9yZWFjaCBwYWNrYWdlIGFuZCByZWdpc3RlciB0aGUgY2x1c3RlciwgYW5kIHN1cHBseSB0aGUgYC5wYXJhbGxlbGAgYXJndW1lbnQuICBJdCdzIHN0aWxsIGV4Y2VlZGluZ2x5IHNsb3csIHNvIHlvdSBtaWdodCBqdXN0IHN0aWNrIHdpdGggdGhlIHBhcmFsbGVsL2ZvcmVhY2ggcGFja2FnZS4gIA0KDQpgYGB7ciBwYXJQbHlyLCBldmFsPUZBTFNFfQ0KbGlicmFyeShmb3JlYWNoKTsgbGlicmFyeShkb1BhcmFsbGVsKQ0KbGlicmFyeShwYXJhbGxlbCkNCmNsID0gbWFrZUNsdXN0ZXIoMTIpDQpyZWdpc3RlckRvUGFyYWxsZWwoY2wpDQptZWFucyA9IGFhcGx5KHgsIDIsIG1lYW4sIC5wYXJhbGxlbCA9IFQsIC5wYXJvcHRzID0gbGlzdCguZXhwb3J0PSd4JykpDQpzdG9wQ2x1c3RlcihjbCkNCmBgYA0KDQoNCmBgYHtyIG11bHRpZHBseXIsIGV2YWw9RkFMU0UsIGVjaG89RkFMU0V9DQpsaWJyYXJ5KG11bHRpZHBseXIpDQpgYGANCg0KDQpGb3Igc29tZXRoaW5nIHNpbXBsZSBsaWtlIHRoaXMsIHRoZXJlIGlzbid0IGdvaW5nIHRvIGJlIG11Y2ggZ2FpbmVkIGluIGdvaW5nIHBhcmFsbGVsLiBBbmQgdGhpcyBpcyBhbiBpbXBvcnRhbnQgcG9pbnQgdG8gbm90ZTogKnVzaW5nIG1vcmUgY29yZXMgZG9lcyBub3QgbmVjZXNzYXJpbHkgbWVhbiBtb3JlIHNwZWVkKiwgYW5kIHRoaXMgaXMgZXNwZWNpYWxseSB0aGUgY2FzZSB3aGVuIHNwcmVhZGluZyBvcGVyYXRpb25zIGFjcm9zcyBtYWNoaW5lcy4gIEhhZCBJIHVzZWQgMTIgaW5zdGVhZCBvZiA4IG9uIG15IG1hY2hpbmUsIHRoZSBkaWZmZXJlbmNlIHdvdWxkIGhhdmUgYmVlbiBuZWdsaWdpYmxlLiAgSSBzaG91bGQgYWxzbyBub3RlIHRoYXQgbm9uZSBvZiB0aGVzZSBhcHByb2FjaGVzIGlzIG5lYXJseSBhcyBmYXN0IGFzIHdlIGNvdWxkIGdldCB3aXRoIGEgYnVpbHQtaW4gUiBmdW5jdGlvbiwgPHNwYW4gY2xhc3M9ImZ1bmMiPmNvbE1lYW5zPC9zcGFuPi4NCg0KYGBge3IgcGFyYWxsZWxDb21wYXJpc29uLCBlY2hvPUZBTFNFLCBldmFsPUZBTFNFfQ0KcGFyYWxsZWxDb21wYXJpc29uID0gbWljcm9iZW5jaG1hcmsobWVhbnNfbG9vcCA9IG1lYW5zX2xvb3BfZnVuYyh4KSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtZWFuc19hcHBseSA9IGFwcGx5KHgsIDIsIG1lYW4pLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcGFyYWxsZWxNZWFucyA9IHBhckFwcGx5KGNsLCB4LCAyLCBtZWFuKSwgdGltZXM9MTApDQpzYXZlKHBhcmFsbGVsQ29tcGFyaXNvbiwgZmlsZT0nZGF0YS9wYXJhbGxlbENvbXBhcmlzb24uUkRhdGEnKQ0Kc3RvcENsdXN0ZXIoY2wpDQpgYGANCg0KDQpgYGB7ciBsb2FkUGFyYWxsZWxDb21wYXJpc29uLCBlY2hvPUZBTFNFfQ0KbG9hZCgnZGF0YS9wYXJhbGxlbENvbXBhcmlzb24uUkRhdGEnKQ0KcGFyYWxsZWxDb21wYXJpc29uDQpgYGANCg0KDQojIyBVc2luZyBmYXN0ZXIgbGFuZ3VhZ2VzDQoNCiMjIyBCYXNlIFIgaW50ZXJuYWxzDQoNCk11Y2ggb2YgYmFzZSBSIGlzIG5vdCB3cml0dGVuIGluIFIsIGJ1dCBtdWNoIGZhc3RlciBsYW5ndWFnZXMgc3VjaCBhcyBDLCBDKysgYW5kIEZvcnRyYW4sIGFuZCB1c2luZyB0aG9zZSBmdW5jdGlvbnMgY2FuIGxlYWQgdG8gZW5vcm1vdXMgc3BlZWQgZ2FpbnMuICBSZWxhdGl2ZSB0byBhbiBleHBsaWNpdCBsb29wIHRoYXQgZG9lcyB0aGUgc2FtZSB0aGluZywgdGhlcmUgaXMgbm8gY29tcGFyaXNvbiB0byBhIGJhc2UgUiBmdW5jdGlvbiB0aGF0J3MgY2FsbGluZyBpbnRlcm5hbCBDIG9yIG90aGVyIGNvZGUuICBOb3Qgb25seSB3aWxsIHRoZSBidWlsdC1pbiBmdW5jdGlvbiBydW4gZmFzdGVyLCBidXQgeW91ciBjb2RlIHdpbGwgYmUgbW9yZSBzdWNjaW5jdCBiZWNhdXNlIHlvdSdyZSBtYWtpbmcgYSBzaW5nbGUgZnVuY3Rpb24gY2FsbCBhcyBvcHBvc2VkIHRvIGFuIGV4cGxpY2l0IGxvb3AuDQoNCkFzIGFuIGV4YW1wbGUgbGV0J3MgY29tcGFyZSB0aGUgcHJldmlvdXMgZG91YmxlIGxvb3AgYXBwcm9hY2ggdG8gdGhlIGJhc2UgUiBmdW5jdGlvbiA8c3BhbiBjbGFzcz0iZnVuYyI+ZGlzdC48L3NwYW4+DQoNCmBgYHtyIGRpc3QsIGVjaG89RkFMU0V9DQptaWNyb2JlbmNobWFyayhkbG9vcCA9IGRvdWJsZUxvb3BEaXN0KGQpLCANCiAgICAgICAgICAgICAgIGRsb29wMj1kb3VibGVMb29wRGlzdDIoZCksIA0KICAgICAgICAgICAgICAgZGlzdD0gZGlzdChkLCBkaWFnID0gVCwgdXBwZXIgPSBUKSkNCmBgYA0KDQoNCklmIHRoZXJlIGFyZSBhY3R1YWxseSBvbmx5IHR3byBjb2x1bW5zIHRob3VnaCwgZGlzdCB3b3VsZCBiZSBzbG93ZXIgZHVlIHRvIHNvbWUgcHJlbGltaW5hcnkgY2hlY2tzIGFuZCBjYWxjdWxhdGlvbnMgdGhhdCA8c3BhbiBjbGFzcz0iZnVuYyI+c3VtPC9zcGFuPiBhbmQgPHNwYW4gY2xhc3M9ImZ1bmMiPnNxcnQ8L3NwYW4+IGZ1bmN0aW9ucyBkbyBub3QgaGF2ZSB0byBtYWtlIChub3RlIHRoYXQgdGhlc2UgdGltaW5ncyBhcmUgaW4gKiptaWNybyoqc2Vjb25kcykuIA0KDQpgYGB7ciBkaXN0Zm9yMmNvbCwgZWNobz1GQUxTRX0NCm1pY3JvYmVuY2htYXJrKGRpc3Q9IGRpc3QoZFssMToyXSksIHNxcnRzdW0gPSBzcXJ0KHN1bSgoZFssMV0gLSBkWywyXSleMikpKQ0KYGBgDQoNCkFnYWluLCB3aGVuIHRoZXJlIGlzbid0IG11Y2ggdG8gb3B0aW1pemUsIGRvbid0IHdhc3RlIHRpbWUgZmlndXJpbmcgb3V0IGhvdyB0byBkbyBzby4NCg0KPiBQcmVtYXR1cmUgb3B0aW1pemF0aW9uIGlzIHRoZSByb290IG9mIGFsbCBldmlsLiA8YnI+PGJyPg0KPiBcfiBEb25hbGQgS251dGgNCg0KDQpBcyBhbm90aGVyIGV4YW1wbGUsIGxldCdzIHVzZSB0aGUgPHNwYW4gY2xhc3M9ImZ1bmMiPmNvbE1lYW5zPC9zcGFuPiBmdW5jdGlvbiBvbiB0aGF0IGxhcmdlIDEwIHggMTAwMDAwMCBtYXRyaXggd2UgdXNlZCBiZWZvcmUuDQoNCmBgYHtyIGNvbG1lYW5zLCBlY2hvPUZBTFNFfQ0KcmJpbmQocGFyYWxsZWxDb21wYXJpc29uLCBtaWNyb2JlbmNobWFyayhjb2xNZWFucyA9IGNvbE1lYW5zKHgpKSkNCmBgYA0KDQpUaGlzIHNob3dzIHRoYXQgdXNpbmcgdGhlIGNvbXBpbGVkIEMgaW4gdGhlIDxzcGFuIGNsYXNzPSJmdW5jIj5jb2xNZWFuczwvc3Bhbj4gZnVuY3Rpb24gaXMgd2F5IGZhc3RlciB0aGFuIGV2ZW4gcGFyYWxsZWxpemluZyAoaW4gdGhpcyBjYXNlKS4NCg0KQXMgYSBmdXJ0aGVyIGlsbHVzdHJhdGlvbiwgbGV0J3MgY2VudGVyIGEgbWF0cml4LCBpLmUuIHN1YnRyYWN0IHRoZSBtZWFuLiBXZSBub3cgaGF2ZSBzZXZlcmFsIG9wdGlvbnMgYXQgdGhpcyBwb2ludCwgYnV0IHdlJ2xsIGtlZXAgaXQgdG8gdGhlIGZvbGxvd2luZzoNCg0KLSB1c2luZyB0aGUgPHNwYW4gY2xhc3M9ImZ1bmMiPnNjYWxlPC9zcGFuPiBmdW5jdGlvbiB3aXRoIHRoZSBhcmd1bWVudCBgc2NhbGUgPSBGQUxTRWANCi0gdXNpbmcgdGhlIDxzcGFuIGNsYXNzPSJmdW5jIj5zd2VlcDwvc3Bhbj4gZnVuY3Rpb24NCi0gc3VidHJhY3QgdGhlIGNvbHVtbiBtZWFucyBjYWxjdWxhdGVkIHZpYSA8c3BhbiBjbGFzcz0iZnVuYyI+Y29sTWVhbnM8L3NwYW4+DQoNCmBgYHtyLCBlY2hvPUZBTFNFfQ0KbWljcm9iZW5jaG1hcmsobWVhbnNfc3dlZXAgPSBzd2VlcCh4LCAyLCBTVEFUUz1jb2xNZWFucyh4KSwgY2hlY2subWFyZ2luPUYpLA0KICAgICAgICAgICAgICAgc2NhbGUgPSBzY2FsZSh4LCBzY2FsZT1GKSwNCiAgICAgICAgICAgICAgIHN1YnRyYWN0X2NvbE1lYW5zID0geCAtIGNvbE1lYW5zKHgpKQ0KYGBgDQoNClRoZSBpbnRlcmVzdGluZyB0aGluZyB0byBub3RlIGhlcmUgaXMgdGhhdCA8c3BhbiBjbGFzcz0iZnVuYyI+c3dlZXA8L3NwYW4+IGlzIGFscmVhZHkgYXMgZmFzdCBhcyB0aGUgYnVpbHQgaW4gPHNwYW4gY2xhc3M9ImZ1bmMiPnNjYWxlPC9zcGFuPiBmdW5jdGlvbiwgYnV0IHdlIGNvdWxkIGhhdmUgcHJvdmlkZWQgYW55IHN0YXRpc3RpYyBvZiB0aGUgY29sdW1ucyB0byAnc3dlZXAgb3V0Jy4gRm9yIGV4YW1wbGUsIG1heWJlIHdlIHByZWZlciB0aGUgbWVkaWFuLCBvciBwZXJoYXBzIHdlIHdhbnQgdG8gYWRkIHJhdGhlciB0aGFuIHN1YnRyYWN0LiBUaGUgc2xvd2Rvd24gb2YgPHNwYW4gY2xhc3M9ImZ1bmMiPnN3ZWVwPC9zcGFuPiBpcyB0aGF0IHRoZSBzdGF0aXN0aWMgdG8gYmUgc3dlcHQgb3V0IG1heSByZXF1aXJlIGEgc2xvd2VyIGFuZC9vciBzZXBhcmF0ZSBvcGVyYXRpb24gKGUuZy4gSSBjb3VsZCBmaXJzdCBjcmVhdGUgYW4gb2JqZWN0IDxzcGFuIGNsYXNzPSJvYmpjbGFzcyI+bWVhbnM8L3NwYW4+IHRoYXQgYXJlIHRoZSBjb2x1bW4gbWVhbnMpLiBJbiB0aGUgZW5kLCBvbmUgbWlnaHQgaGF2ZSBzZXZlcmFsIG9wdGlvbnMgZGVwZW5kaW5nIG9uIHRoZWlyIGdvYWxzLg0KDQoNCiMjIyBSY3BwDQoNCldlIGNhbiBwb3RlbnRpYWxseSB0YWtlIGFkdmFudGFnZSBvZiB0aGUgcG93ZXIgb2YgQysrIGV4cGxpY2l0bHkgd2l0aGluIFIsIGJ5IHVzaW5nIHRoZSBSY3BwIHBhY2thZ2UuIEl0J3MgYWxzbyB3b3J0aCBub3RpbmcgdGhhdCBtYW55IFIgcGFja2FnZXMgZG8gc28gdG8gcGljayB1cCBzb21lIHNwZWVkLg0KDQpgYGB7ciBSY3BwLCBjYWNoZT1GfQ0KbGlicmFyeShSY3BwKQ0KDQpkaXN0QyA9IGNwcEZ1bmN0aW9uKCcNCk51bWVyaWNNYXRyaXggZGlzdEMoTnVtZXJpY01hdHJpeCB4KSB7DQogIGludCBuID0geC5ucm93KCk7DQogIE51bWVyaWNNYXRyaXggb3V0KG4sIG4pOw0KDQogIGZvcihpbnQgaSA9IDA7IGkgPCBuOyArK2kpIHsNCiAgICBmb3IgKGludCBqID0gMDsgaiA8IG47ICsraikgew0KICAgICAgb3V0KGksaikgPSBzcXJ0KHN1bShwb3coeChpLF8pIC0geChqLF8pLCAyLjApKSk7DQogICAgfQ0KICB9DQogIHJldHVybiBvdXQ7DQp9DQonKQ0KZGlzdEMoZFsxOjMsXSkNCmRpc3QoZFsxOjMsXSwgZGlhZyA9IFQsIHVwcGVyID0gVCkNCmBgYA0KDQpOb3cgdGhhdCB3ZSBjYW4gc2VlIHRoc2UgYm90aCBwcm9kdWNlIHRoZSBzYW1lIHRoaW5nLCBsZXQncyB0aW1lIHRoZSA8c3BhbiBjbGFzcz0iZnVuYyI+ZGlzdDwvc3Bhbj4gZnVuY3Rpb24sIHRoZSBDKysgdmVyc2lvbiBhbmQgdGhlIGxvb3AuDQoNCmBgYHtyIFJjcHBDb21wYXJlLCBjYWNoZT1ULCBlY2hvPUZBTFNFfQ0KbWljcm9iZW5jaG1hcmsoZGlzdD0gZGlzdChkKSwgDQogICAgICAgICAgICAgICBkaXN0QyA9IGRpc3RDKGQpLA0KICAgICAgICAgICAgICAgZGxvb3AgPSBkb3VibGVMb29wRGlzdChkKSkNCmBgYA0KDQoNCk5vdGUgdGhhdCBpbiBiaWdnZXIgbWF0cmljZXMgdGhlIFIgZnVuY3Rpb24gd291bGQgZXZlbnR1YWxseSB3aW4gb3V0LCBidXQgdGhlIHBvaW50IGhlcmUgaXMgdGhhdCB3ZSdyZSBhdCBsZWFzdCBpbiB0aGUgYmFsbHBhcmsuIEZ1cnRoZXJtb3JlLCBsaWtlIG1vc3QgbGFuZ3VhZ2VzLCBpdCBpcyBlYXN5IGVub3VnaCB0byBydW4gYW5vdGhlciBsYW5ndWFnZSBzY3JpcHQgZnJvbSB3aXRoaW4gdGhhdCBwcm9ncmFtLiAgU28gaWYgeW91J3JlIHdvcmtpbmcgd2l0aGluIGFub3RoZXIgbGFuZ3VhZ2UgZm9yIHRoZSBoZWF2eSBsaWZ0aW5nLCB5b3UgY291bGQgY2FsbCBSIGZyb20gaXQsIG9yIHZpY2UgdmVyc2EsIGkuZS4gd3JpdGUgd2hhdCB5b3UgbmVlZCBpbiBhbm90aGVyIGxhbmd1YWdlIGFuZCBjYWxsIGl0IGZyb20gUi4NCg0KDQoNCiMjIFZlY3Rvcml6YXRpb24NCg0KPHNwYW4gY2xhc3M9ImVtcGgiPlZlY3Rvcml6YXRpb248L3NwYW4+IGlzIGEga2V5IGNvbmNlcHQgaW4gUiwgdGhvdWdoIHNvbWUgY29taW5nIHRvIFIgZnJvbSBvdGhlciBsYW5ndWFnZXMgKGUuZy4gTWF0bGFiKSBtYXkgYmUgZmFtaWxpYXIgd2l0aCBpdC4gVGhlIGJhc2ljIGlkZWEgaXMgdGhhdCB3ZSBwYXNzIHdob2xlIHZlY3RvcnMgdG8gb3BlcmF0aW9ucyByYXRoZXIgdGhhbiB0aGUgZWxlbWVudHMgb2YgaXQsIGFuZCBhcyBzdWNoIFIgY2FuIHRyZWF0IHRoZSB2ZWN0b3Igb25jZSBhbmQgZ28gZnJvbSB0aGVyZSwgcmF0aGVyIHRoYW4gdHJlYXQgZWFjaCBlbGVtZW50IG9mIHRoZSB2ZWN0b3IgYXMgYSB1bmlxdWUgc25vd2ZsYWtlIHRoYXQgbXVzdCBiZSBjb25zaWRlcmVkIGluZGl2aWR1YWxseSwgYW5kIGZpZ3VyaW5nIHRoaW5ncyBvdXQgZXZlcnkgdGltZSB0aGUgb3BlcmF0aW9uIGlzIHJ1bi4NCg0KQXMgYW4gZXhhbXBsZSBsZXQncyBkbyBhIHNpbXBsZSBsb29wIHZzLiBhIHZlY3Rvcml6ZWQgYXBwcm9hY2guDQoNCmBgYHtyIHZlY3Rvcml6YXRpb259DQp4ID0gMTozDQp5ID0gNzo5DQpmb3IgKGkgaW4gc2VxX2Fsb25nKHgpKSB7DQogIHByaW50KHhbaV0gKyB5W2ldKQ0KfQ0KYGBgDQoNCkV2ZXJ5IGl0ZXJhdGlvbiwgUiBldmFsdWF0ZXMgd2hhdCB0eXBlIG9mIG9iamVjdCB4W2ldIGlzLCB3aGF0IHlbaV0gaXMsIHdoZXRoZXIgYWRkaW5nIHRoZW0gaXMgcG9zc2libGUgZXRjLiBJZiB3ZSB1c2UgYSB2ZWN0b3JpemVkIGFwcHJvYWNoLCBSIGZpZ3VyZXMgdGhpcyBvdXQgb25jZSBhbmQgcHJvY2VlZHMgYWNjb3JkaW5nbHkuDQoNCmBgYHtyIHZlY3Rvcml6YXRpb24yfQ0KeCArIHkNCmBgYA0KDQoNCiMjIyBWZWN0b3JpemluZyBhIHNlcXVlbnRpYWwgb3BlcmF0aW9uDQoNCkxldCdzIHJldHVybiB0byBvdXIgcmFuZG9tIHdhbGsgZXhhbXBsZSBmb3Igc29tZSBiZW5jaG1hcmtzLiBUaGlzIGlzIGEgbmljZSBleGFtcGxlIGJlY2F1c2Ugd2UgY2FuIHNlZSB0aGF0IHNvbWV0aW1lcyBldmVuIHNlZW1pbmdseSBzZXF1ZW50aWFsIG9wZXJhdGlvbnMgbWlnaHQgYmUgcHV0IGluIGEgZm9ybSB0aGF0IHdvdWxkIG5vdCByZXF1aXJlIGEgbG9vcC4gIFRoZSBmaXJzdCB2ZWN0b3JpemVkIGV4YW1wbGUgdXNlcyBubyBleHBsaWNpdCBsb29wIGJ1dCBnaXZlcyB1cyB0aGUgc2FtZSByZXN1bHQuIEl0IHVzZXMgPHNwYW4gY2xhc3M9ImZ1bmMiPmlmZWxzZTwvc3Bhbj4sIHdoaWNoIGlzIGEgdmVjdG9yaXplZCB2ZXJzaW9uIG9mIHRoZSBgaWYuLi4gZWxzZWAgY29uc3RydWN0LiAgSG93ZXZlciwgPHNwYW4gY2xhc3M9ImZ1bmMiPmlmZWxzZTwvc3Bhbj4gY29tZXMgd2l0aCBzb21lIGJhZ2dhZ2UsIGFuZCA8c3BhbiBjbGFzcz0icGFjayI+ZHBseXI8L3NwYW4+IHByb3ZpZGVzIGEgZmFzdGVyIHZlcnNpb24sIDxzcGFuIGNsYXNzPSJmdW5jIj5pZl9lbHNlPC9zcGFuPi4NCg0KYGBge3IgdmVjdG9yaXplZEZ1bmN0aW9uc30NCiMgdmVjdG9yaXplDQpydzJkMl92ZWNfaWZlbHNlIDwtIGZ1bmN0aW9uKG4pIHsNCiAgc3RlcHMgPSBzYW1wbGUoYygtMSwgMSksIG4tMSwgcmVwbGFjZT1UKQ0KICB4ZGlyID0gc2FtcGxlKGMoVCwgRiksIG4tMSwgcmVwbGFjZT1UKQ0KICB4cG9zID0gYygwLCBjdW1zdW0oaWZlbHNlKHhkaXIsIHN0ZXBzLCAwKSkpDQogIHlwb3MgPSBjKDAsIGN1bXN1bShpZmVsc2UoeGRpciwgMCwgc3RlcHMpKSkNCiAgZGF0YS5mcmFtZSh4PXhwb3MsIHk9eXBvcykNCn0NCg0KIyBydzJkMl92ZWNfaWZlbHNlKDFlNykNCiMgZ2dwbG90Mjo6cXBsb3QoeCwgeSwgZGF0YT1ydzJkMl92ZWNfaWZlbHNlKDEwMDApLCBnZW9tPSdwYXRoJykNCg0KDQojIGRwbHlyIGlmX2Vsc2UgY2FuIGJlIGZhc3RlciBpZiB0aGVyZSBhcmUgbWFueSBvcGVyYXRpb25zDQpydzJkMl92ZWNfaWZlbHNlMiA8LSBmdW5jdGlvbihuKSB7DQogIHN0ZXBzID0gc2FtcGxlKGMoLTEsIDEpLCBuLTEsIHJlcGxhY2U9VCkNCiAgeGRpciA9IHNhbXBsZShjKFQsIEYpLCBuLTEsIHJlcGxhY2U9VCkNCiAgeHBvcyA9IGMoMCwgY3Vtc3VtKGlmX2Vsc2UoeGRpciwgc3RlcHMsIDApKSkNCiAgeXBvcyA9IGMoMCwgY3Vtc3VtKGlmX2Vsc2UoeGRpciwgMCwgc3RlcHMpKSkNCiAgZGF0YS5mcmFtZSh4PXhwb3MsIHk9eXBvcykNCn0NCg0KIyBydzJkMl92ZWNfaWZlbHNlMigxZTcpDQojIGdncGxvdDI6OnFwbG90KHgsIHksIGRhdGE9cncyZDJfdmVjX2lmZWxzZTIoMTAwMCksIGdlb209J3BhdGgnKQ0KYGBgDQoNCkhvd2V2ZXIsIHdlIGNhbiBzdGlsbCBnZXQgbW9yZSBlZmZpY2llbnQuIEhlcmUgd2UgZG8gYWxsIHRoZSBuZWNlc3Nhcnkgc2FtcGxpbmcgZm9yIHRoZSB4IGFuZCB5IHBvc2l0aW9ucyBmaXJzdCwgdGhlbiBzdWJzZXF1ZW50bHkgZmlsbCBvdXQgdGhvc2UgcG9zaXRpb25zLiBXZSBhbHNvIGp1c3QgdXNlIHRoZSBmYWN0IHRoYXQgPHNwYW4gY2xhc3M9ImZ1bmMiPmN1bXN1bTwvc3Bhbj4gY2FuIHdvcmsgb24gdGhlIDxzcGFuIGNsYXNzPSJvYmpjbGFzcyI+ZGF0YS5mcmFtZTwvc3Bhbj4gaXRzZWxmLiAgQXMgPHNwYW4gY2xhc3M9Im9iamNsYXNzIj5kYXRhLmZyYW1lczwvc3Bhbj4gYXJlIDxzcGFuIGNsYXNzPSJvYmpjbGFzcyI+bGlzdHM8L3NwYW4+LCA8c3BhbiBjbGFzcz0iZnVuYyI+Y3Vtc3VtPC9zcGFuPiB3aWxsIHdvcmsgb24gaXRzIGVsZW1lbnRzLCB3aGljaCBpbiB0aGlzIGNhc2UgYXJlIHRoZSBjb2x1bW5zLg0KDQpgYGB7ciB2ZWN0b3JpemF0aW9uX25vaWZlbHNlfQ0KcncyZDJfdmVjX25vaWZlbHNlIDwtIGZ1bmN0aW9uKG4pIHsNCiAgZGlyID0gc2FtcGxlKDE6NCwgbi0xLCByZXBsYWNlPVQpDQogIHhwb3MgPSBjKDAsIGMoLTEsIDEsIDAsIDApW2Rpcl0pDQogIHlwb3MgPSBjKDAsIGMoMCwgMCwgLTEsIDEpW2Rpcl0pDQogIGN1bXN1bShkYXRhLmZyYW1lKHg9eHBvcywgeT15cG9zKSkNCn0NCg0KIyBydzJkMl92ZWNfbm9pZmVsc2UoMWU3KQ0KIyBnZ3Bsb3QyOjpxcGxvdCh4LCB5LCBkYXRhPXJ3MmQyX3ZlY19ub2lmZWxzZSgxMDAwKSwgZ2VvbT0ncGF0aCcpDQpgYGANCg0KDQpOb3cgd2UgY29tcGFyZSBhbGwgdGhlIGxvb3BpbmcgY2hvaWNlcyBjb25zaWRlcmVkIHRodXMgZmFyOg0KDQotIGxvb3Agbm8gcHJlLWFsbG9jYXRpb24NCi0gbG9vcCB3aXRoIHByZS1hbGxvY2F0aW9uDQotIHZlY3Rvcml6YXRpb24gKDIgdmVyc2lvbnMpDQotIG1vcmUgZWZmaWNpZW50IHZlY3Rvcml6YXRpb24NCg0KVGhlIGxhc3QgdmVyc2lvbiBpcyBzdWNjaW5jdCBpbiBjb2RlIGFuZCBtdWNoIGZhc3RlciBhcyB3ZWxsLg0KDQpgYGB7ciBsb29wX3ZlY3Rvcml6YXRpb25fY29tcGFyaXNvbiwgZWNobz1GQUxTRX0NCm1pY3JvYmVuY2htYXJrKHJ3MmRfbG9vcF9ub3ByZSgxMDAwMCksDQogICAgICAgICAgICAgICBydzJkX2xvb3BfcHJlKDEwMDAwKSwNCiAgICAgICAgICAgICAgIHJ3MmQyX3ZlY19pZmVsc2UoMTAwMDApLA0KICAgICAgICAgICAgICAgcncyZDJfdmVjX2lmZWxzZTIoMTAwMDApLA0KICAgICAgICAgICAgICAgcncyZDJfdmVjX25vaWZlbHNlKDEwMDAwKSkNCg0KIyBnZ3Bsb3QyOjphdXRvcGxvdCgNCiMgbWljcm9iZW5jaG1hcmsocncyZF9sb29wX25vcHJlKDEwMDApLA0KIyAgICAgICAgICAgICAgICBydzJkX2xvb3BfcHJlKDEwMDApLA0KIyAgICAgICAgICAgICAgICBydzJkMl92ZWNfaWZlbHNlKDEwMDApLA0KIyAgICAgICAgICAgICAgICBydzJkMl92ZWNfbm9pZmVsc2UoMTAwMCksDQojICAgICAgICAgICAgICAgIHJ3MmQyX3JlY3Vyc2l2ZSgxMDAwKSkNCiMgKQ0KYGBgDQoNCg0KRm9yIG1vcmUgZXhhbXBsZXMgYW5kIGlzc3VlcyB3aXRoIHZlY3Rvcml6YXRpb24gc2VlIHRoZSBmb2xsb3dpbmc6DQoNCltBIHZlcnkgYWNjZXNzaWJsZSBpbnRybyB0byB2ZWN0b3JpemF0aW9uXShodHRwOi8vd3d3Lm5vYW1yb3NzLm5ldC9ibG9nLzIwMTQvNC8xNi92ZWN0b3JpemF0aW9uLWluLXItLXdoeS5odG1sKSBOb2FtIFJvc3MNCg0KW1doZW4gdG8gbGVhdmUgbG9vcHMgYWxvbmVdKGh0dHA6Ly9hZHYtci5oYWQuY28ubnovRnVuY3Rpb25hbHMuaHRtbCNmdW5jdGlvbmFscy1ub3QpIEhhZGxleSBXaWNraGFtDQoNCltSIEluZmVybm8gKDNyZCBDaXJjbGUpXShodHRwOi8vd3d3LmJ1cm5zLXN0YXQuY29tL3BhZ2VzL1R1dG9yL1JfaW5mZXJuby5wZGYpIFBhdHJpY2sgQnVybnMNCg0KDQoNCiMgTWF0cml4IG9wZXJhdGlvbnMNCg0KQ29uc2lkZXIgYSBsaW5lYXIgY29tYmluYXRpb24gdG8gcHJvZHVjZSBtb2RlbCBwcmVkaWN0aW9ucyBhcyBpbiBhIHN0YW5kYXJkIHJlZ3Jlc3Npb24gbW9kZWwuIFdlIG11bHRpcGx5IGVhY2ggY29sdW1uIGJ5IGEgY29lZmZpY2llbnQgYW5kIHN1bSB0aGVtLg0KDQoNCmBgYHtyIGxpbmNvbX0NCmIgPSBydW5pZigxMSkgIyBmaXJzdCB2YWx1ZSBpcyB0aGUgaW50ZXJjZXB0DQoNClggPSBtYXRyaXgocm5vcm0oMTAwMDAwKSwgbmNvbD0xMCkNCg0KbGluY29tMSA9IGJbMV0gKyBiWzJdKlhbLDFdICsgYlszXSpYWywyXSArIGJbNF0qWFssM10gKyBiWzVdKlhbLDRdICsgYls2XSpYWyw1XSArIA0KICBiWzddKlhbLDZdICsgYls4XSpYWyw3XSArIGJbOV0qWFssOF0gKyBiWzEwXSpYWyw5XSArIGJbMTFdKlhbLDEwXQ0KYGBgDQoNCldoaWxlIHRoaXMgaXMgdmVjdG9yaXplZCwgd2UgY2FuIGRvIGJldHRlci4gV2UgY2FuIHVzZSBtYXRyaXggbXVsdGlwbGljYXRpb24gdG8gcHJvZHVjZSB0aGUgc2FtZSByZXN1bHQuICBJbiBhZGRpdGlvbiwgdGhlIGJpZ2dlc3QgZ2FpbiBoZXJlIGlzIHByb2dyYW1taW5nIHRpbWUuICBNYXRyaXggbXVsdGlwbGljYXRpb24gdGFrZXMgZmFyIGxlc3MgdG8gY29kZSB1cC4NCg0KYGBge3IgbGluY29tTWF0cml4fQ0KWCA9IGNiaW5kKDEsIFgpICMgYWRkIGludGVyY2VwdCBjb2x1bW4NCmxpbmNvbTIgID0gWCAlKiUgYg0KYGBgDQoNCkhvd2V2ZXIsIGV2ZW4gd2l0aGluIG1hdHJpeCBvcGVyYXRpb25zIHRoZXJlIG1pZ2h0IGJlIGZhc3RlciB3YXlzIHRvIGRvIGl0LiBJbiB0aGlzIGNhc2UsIDxzcGFuIGNsYXNzPSJmdW5jIj5jcm9zc3Byb2Q8L3NwYW4+IGlzIHNsaWdodGx5IGZhc3Rlci4NCg0KYGBge3IgbGluY29tQ3Jvc3Nwcm9kfQ0KbGluY29tMyA9IHRjcm9zc3Byb2QoWCwgdChiKSkNCg0KaWRlbnRpY2FsKGxpbmNvbTEsIGMobGluY29tMikpDQppZGVudGljYWwobGluY29tMiwgbGluY29tMykNCmBgYA0KDQpMZXQncyB0aW1lIHRoZW0uDQoNCmBgYHtyIGxpbmNvbVRpbWUsIGVjaG89RkFMU0V9DQptaWNyb2JlbmNobWFyayhsYzEgPSBiWzFdICsgYlsyXSpYWywxXSArIGJbM10qWFssMl0gKyBiWzRdKlhbLDNdICsgYls1XSpYWyw0XSArIGJbNl0qWFssNV0gKyBiWzddKlhbLDZdICsgYls4XSpYWyw3XSArIGJbOV0qWFssOF0gKyBiWzEwXSpYWyw5XSArIGJbMTFdKlhbLDEwXSwNCiAgICAgICAgICAgICAgIGxjMiA9IFggJSolIGIsDQogICAgICAgICAgICAgICBsYzMgPSB0Y3Jvc3Nwcm9kKFgsIHQoYikpKQ0KYGBgDQoNCg0KVGhleSBhbGwgcHJvZHVjZSBpZGVudGljYWwgb3V0cHV0LCBidXQgdXNpbmcgYSBtYXRyaXggb3BlcmF0aW9uIGlzIG92ZXIgNCB0aW1lcyBhcyBmYXN0IGFzIHRoZSBzaW1wbGUgc3VtLCBhbmQgY3Jvc3Nwcm9kIG92ZXIgMTEgdGltZXMgYXMgZmFzdC4gIFByb2dyYW1taW5nIHRpbWUgaXMgcXVpY2tlciBhbHNvLiAgDQoNCg0KRXZlbiBob3cgd2UgZG8gdGhlIG1hdHJpeCBvcGVyYXRpb25zIGNhbiBoYXZlIGFuIGVmZmVjdC4gVGhlIGZvbGxvd2luZyBleGFtcGxlcyB1c2UgdmFyaW91cyBtZWFucyB0byBvYnRhaW4gY29lZmZpY2llbnRzIGZyb20gYSBzdGFuZGFyZCBsaW5lYXIgcmVncmVzc2lvbiBtb2RlbC4gIFdlJ2xsIHN0YXJ0IHdpdGgganVzdCB0aGUgYmFzZSBSIDxzcGFuIGNsYXNzPSJmdW5jIj5sbTwvc3Bhbj4gZnVuY3Rpb24uICBUaGUgbmV4dCBpcyB0aGUgPHNwYW4gY2xhc3M9ImZ1bmMiPmxtLmZpdDwvc3Bhbj4gZnVuY3Rpb24sIHdoaWNoIGlzIHdoYXQgbG0gdXNlcywgYnV0IGFmdGVyIGEgbG90IG9mIHByZS0gYW5kIHBvc3QtcHJvY2Vzc2luZyBvZiB0aGUgZGF0YS4gIEFmdGVyIHRoYXQgd2UgdXNlIGJhc2ljIG1hdHJpeCBtdWx0aXBsaWNhdGlvbiwgYSBncm91cGVkIHZlcnNpb24gb2YgaXQsIGZvbGxvd2VkIGJ5IHVzZSBvZiB0aGUgPHNwYW4gY2xhc3M9ImZ1bmMiPmNyb3NzcHJvZDwvc3Bhbj4gZnVuY3Rpb24uDQoNCmBgYHtyIG1hdHJpeExNfQ0Kc2V0LnNlZWQoMTIzNCkNCm4gPSAxMDAwMDAwMCAgICAgICAgICAgICAgICAgICAjIHNhbXBsZSBzaXplDQp4ID0gcm5vcm0obikgICAgICAgICAgICAgICAgICAgIyBjb3ZhcmlhdGUNCnkgPSAgNSArIDIqeCArIHJub3JtKG4pICAgICAgICAjIHRhcmdldA0KWCA9IGNiaW5kKDEsIHgpICAgICAgICAgICAgICAgICMgbW9kZWwubWF0cml4DQoNCg0KIyBsbQ0KbG1fYmFzZSAgPSBsbSh5IH4geCkNCg0KIyB1c2UgdGhlIHVuZGVybHlpbmcgZml0IGZ1bmN0aW9uDQpsbV9maXQgID0gbG0uZml0KFgsIHkpICAgICAgICAgICMgbm90ZTogcXIuc29sdmUgaXNuJ3QgcmVhbGx5IGEgZ2FpbiBoZXJlIGJ1dCBjb3VsZCBhbHNvIGJlIHVzZWQNCg0KIyBhbiBldmVuIGZhc3RlciB2ZXJzaW9uDQpsbV9maXQyICA9IC5sbS5maXQoWCwgeSkNCg0KIyBub3JtYWwgZXF1YXRpb25zIHRvIGdldCBjb2VmZmljaWVudHMNCm1hdHJpeF9yYXcgPSBzb2x2ZSh0KFgpICUqJSBYKSAlKiUgdChYKSAlKiUgeQ0KDQptYXRyaXhfZ3JvdXBlZCA9IHNvbHZlKHQoWCklKiVYKSAlKiUgKHQoWCkgJSolIHkpDQoNCiMgY3Jvc3Nwcm9kIGFwcHJvYWNoDQptYXRyaXhfY3Jvc3Nwcm9kID0gY3Jvc3Nwcm9kKHNvbHZlKGNyb3NzcHJvZChYKSksIGNyb3NzcHJvZChYLHkpKQ0KDQoNCmNiaW5kKGNiaW5kKGxtX2Jhc2U9Y29lZihsbV9iYXNlKSwgDQogICAgICBsbV9maXQ9Y29lZihsbV9maXQpLCANCiAgICAgIGxtX2ZpdDI9Y29lZihsbV9maXQyKSwgDQogICAgICBtYXRyaXhfcmF3PW1hdHJpeF9yYXdbLDFdLA0KICAgICAgbWF0cml4X2dyb3VwZWQ9bWF0cml4X2dyb3VwZWRbLDFdLA0KICAgICAgbWF0cml4X2Nyb3NzcHJvZD1tYXRyaXhfY3Jvc3Nwcm9kWywxXSkpDQpgYGANCg0KDQpgYGB7ciBtYXRyaXhsbUNvbXBhcmlzb25zQ29uc3RydWN0LCBlY2hvPUZBTFNFLCBldmFsPUZBTFNFfQ0KIyBhZGQgc2U/IHNxcnQoZGlhZyhjcm9zc3Byb2QodGVzdCRyZXNpZHVhbHMpWywxXS9uICogc29sdmUoY3Jvc3Nwcm9kKFgpKSkpDQptYXRyaXhsbSA9IG1pY3JvYmVuY2htYXJrKGxtX2Jhc2UgID0gbG0oeSB+IHgpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICBsbV9maXQgID0gbG0uZml0KFgsIHkpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAjIHFyID0gcXIuc29sdmUoWCx5KSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgbG1fZml0MiAgPSAubG0uZml0KFgsIHkpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICBtYXRyaXhfcmF3ID0gc29sdmUodChYKSAlKiUgWCkgJSolIHQoWCkgJSolIHksDQogICAgICAgICAgICAgICAgICAgICAgICAgIG1hdHJpeF9ncm91cGVkID0gc29sdmUodChYKSUqJVgpICUqJSAodChYKSAlKiUgeSksDQogICAgICAgICAgICAgICAgICAgICAgICAgIG1hdHJpeF9jcm9zc3Byb2QgPSBjcm9zc3Byb2Qoc29sdmUoY3Jvc3Nwcm9kKFgpKSwgY3Jvc3Nwcm9kKFgseSkpLCB0aW1lcz0yMCkNCg0Kc2F2ZShtYXRyaXhsbSwgZmlsZT0nZGF0YS9tYXRyaXhsbS5SRGF0YScpDQpgYGANCg0KTm93IGZvciB0aGUgdGltaW5ncy4NCg0KYGBge3IgbWF0cml4bG1Db21wYXJpc29uc0Rpc3BsYXksIGVjaG89RkFMU0UsIGV2YWw9VFJVRX0NCmxvYWQoJ2RhdGEvbWF0cml4bG0uUkRhdGEnKQ0KbWF0cml4bG0NCmBgYA0KDQpXZSBjYW4gc2VlIGFib3ZlIHRoYXQgdGhlc2UgYXBwcm9hY2hlcyBhbGwgcHJvZHVjZSB0aGUgc2FtZSByZXN1bHRzLCBidXQgdGFrZSB2ZXJ5IGRpZmZlcmVudCBhbW91bnRzIG9mIHRpbWUgdG8gY29tcGxldGUuIFdlIGdldCBhIHNpZ25pZmljYW50IGdhaW4gaWYgd2UgcmVkdWNlIHRoZSA8c3BhbiBjbGFzcz0iZnVuYyI+bG08L3NwYW4+IG92ZXJoZWFkLCB3aGVyZSA8c3BhbiBjbGFzcz0iZnVuYyI+bG0uZml0PC9zcGFuPiBpcyBhbG1vc3QgMTB4IGZhc3RlciwgYW5kIHRoZSA8c3BhbiBjbGFzcz0iZnVuYyI+LmxtLmZpdDwvc3Bhbj4sIHdoaWNoIGlzIGp1c3QgYSB3cmFwcGVyIGZvciB0aGUgQyBjb2RlIGNhbGwsIGlzIGZhc3RlciBzdGlsbC4gV2UgY2FuIHN0aWxsIGdldCBmYXN0ZXIgYnkgdXNpbmcgbWF0cml4IG9wZXJhdGlvbnMsIGFuZCBldmVuIGdldCBhIHNsaWdodCBnYWluIGlmIHdlIGdyb3VwIHRoZW0gYSBjZXJ0YWluIHdheS4gIFRoaXMgcmVkdWNlcyBtZW1vcnkgdXNhZ2UgYXMgd2VsbC4gIFRoZSBpZGVhIGlzIHRoYXQgaWYgd2UgZ28gZnJvbSBgc29sdmUodChYKSUqJVgpYCBhbmQgcG9zdCBtdWx0aXBseSBieSBgdChYKWAsIHdlJ3JlIGRlYWxpbmcgd2l0aCBhIDIgeCAxMF43XiBtYXRyaXguIElmIHdlIGZpcnN0IGB0KFgpICUqJSB5YCwgd2UncmUgbm93IGp1c3QgbXVsdGlwbHlpbmcgYSAyeDIgbWF0cml4IHdpdGggYSAyeDEgbWF0cml4LiBJbiB0aGUgZW5kIHRob3VnaCwgY3Jvc3Nwcm9kIGlzIHRoZSBtb3N0IG9wdGltaXplZCwgYW5kIG5vdGFibHkgZmFzdGVyIHRoYW4gYW55IG9mIHRoZSBvdGhlciBhcHByb2FjaGVzLg0KDQoNCkFuZCBmaW5hbGx5LCB0aGVyZSBhcmUgZWZmaWNpZW50IG1ldGhvZHMsIHBhcnRpY3VsYXJseSBmb3IgPHNwYW4gY2xhc3M9ImVtcGgiPnNwYXJzZTwvc3Bhbj4gbWF0cmljZXMsIGluIHBhY2thZ2VzIHN1Y2ggYXMgPHNwYW4gY2xhc3M9InBhY2siPk1hdHJpeDwvc3Bhbj4uIEZvciBkZW5zZSBtYXRyaWNlcyBpdCBoYXMgdGhlIHNhbWUgc3BlZWQgYXMgc3RhbmRhcmQgUiwgYnV0IHdvdWxkIHN0aWxsIGhhdmUgb3RoZXIgd2l0aGluLXBhY2thZ2UgZnVuY3Rpb25hbGl0eSB0aGF0IG1pZ2h0IGJlIHVzZWZ1bC4gIA0KDQpgYGB7ciBNYXRyaXhQYWNrYWdlfQ0KbGlicmFyeShNYXRyaXgpDQpYMiA9IGFzKFgsICdkZ2VNYXRyaXgnKQ0KeTIgPSBhcyh5LCAnZGdlTWF0cml4JykNCmBgYA0KDQpgYGB7ciBldmFsTWF0cml4UGFja2FnZSwgZWNobz1GfQ0KbWljcm9iZW5jaG1hcmsobWF0cml4X2Nyb3NzcHJvZCA9IGNyb3NzcHJvZChzb2x2ZShjcm9zc3Byb2QoWCkpLCBjcm9zc3Byb2QoWCx5KSksDQogICAgICAgICAgICAgICBtYXRyaXhfY3Jvc3Nwcm9kMiA9IGNyb3NzcHJvZChzb2x2ZShjcm9zc3Byb2QoWDIpKSwgY3Jvc3Nwcm9kKFgyLHkyKSkpDQpgYGANCg0KSGVyZSdzIGEgY29tcGFyaXNvbiB3aXRoIHNwYXJzZSBtYXRyaWNlcywgd2hlcmUgbWVtb3J5IGFzIHdlbGwgYXMgc3BlZWQgZ2FpbnMgY2FuIGJlIG1hZGUuIFRoZSBiYXNlIFIgb2JqZWN0IGlzIDIwMCB0aW1lcyBsYXJnZXIuDQoNCmBgYHtyIHNwYXJzZU1hdHJpeH0NCm0gPC0gbWF0cml4KDAsIDUwMCwgNTAwKQ0KbVtydW5pZigzMTQsIDAsIGxlbmd0aChtKSldIDwtIDENCm1tIDwtIGFzKG0sICJkZ0NNYXRyaXgiKQ0Kb2JqZWN0LnNpemUobSkgLyBvYmplY3Quc2l6ZShtbSkgDQpgYGANCg0KVGhlIHNwZWVkIGdhaW5zIGFyZSBub3RhYmxlIGFzIHdlbGwuDQoNCmBgYHtyIGNvbXBhcmVDcm9zc3Byb2RzfQ0KbWljcm9iZW5jaG1hcmsoc3BhcnNlX3Rjcm9zc3Byb2QgPC0gdGNyb3NzcHJvZChtbSksDQogICAgICAgICAgICAgICBzcGFyc2VfY3Jvc3Nwcm9kIDwtIGNyb3NzcHJvZChtbSksDQogICAgICAgICAgICAgICBiYXNlX2Nyb3NzcHJvZCA8LSBjcm9zc3Byb2QobSksDQogICAgICAgICAgICAgICBiYXNlX3Rjcm9zc3Byb2QgPC0gdGNyb3NzcHJvZChtKSkNCmBgYA0KDQoNCiMgT3RoZXIgUiBidWlsZHMNCg0KT3RoZXIgdmVyc2lvbnMgb2YgUiBleGlzdC4gRm9yIHRob3NlIHVzaW5nIHVuaXZlcnNpdHkgaGlnaCBwZXJmb3JtYW5jZSBjb21wdXRpbmcsIHRoZSBSIGJ1aWxkIHlvdSBhcmUgdXNpbmcgd2lsbCBiZSBkaWZmZXJlbnQsIGZvciBleGFtcGxlLiAgSGVyZSBpcyBhIHJ1biBkb3duIG9mIHNvbWUsIHBhcnRseSB0YWtlbiBmcm9tIFdpY2toYW0ncyBjaGFwdGVyIGxpbmtlZCBpbiB0aGUgaW50cm9kdWN0aW9uIG9mIHRoaXMgZG9jdW1lbnQuIFRoZXJlIGFyZSBvdGhlcnMsIGJ1dCBJIGp1c3Qgbm90ZSB0aGUgb25lcyB0aGF0IHN0aWxsIGFwcGVhciB0byBiZSBpbiByZWd1bGFyIGRldmVsb3BtZW50Lg0KDQpbTWljcm9zb2Z0IE9wZW4gUl0oaHR0cHM6Ly9tcmFuLnJldm9sdXRpb25hbmFseXRpY3MuY29tL29wZW4vKTogIEZyb20gTWljcm9zb2Z0LCBzcGVjaWZpY2FsbHkgdGhlIGZvcm1lciBSZXZvbHV0aW9uIEFuYWx5dGljcyBncm91cC4gV2hpbGUgdGhlIGJ1aWxkIGlzIHR5cGljYWxseSBhIHBvaW50IHJlbGVhc2UgYmVoaW5kIHRoZSBjdXJyZW50IHZlcnNpb24gb2YgUiwgdGhhdCB3b24ndCBhZmZlY3QgbW9zdCB1c2VycywgYW5kIGl0J3MgZWFzeSB0byBpbnN0YWxsIG9uIG9uZSdzIG93biBtYWNoaW5lIGp1c3QgbGlrZSBhbnkgUi4NCg0KW3BxUl0oaHR0cDovL3d3dy5wcXItcHJvamVjdC5vcmcvKSAocHJldHR5IHF1aWNrIFIpOiBieSBSYWRmb3JkIE5lYWwuIEZpeGVzIG1hbnkgb2J2aW91cyBwZXJmb3JtYW5jZSBpc3N1ZXMsIGFuZCBwcm92aWRlcyBiZXR0ZXIgbWVtb3J5IG1hbmFnZW1lbnQgYW5kIHNvbWUgc3VwcG9ydCBmb3IgYXV0b21hdGljIG11bHRpdGhyZWFkaW5nLg0KDQpbUmVuamluXShodHRwOi8vd3d3LnJlbmppbi5vcmcvKTogIGJ5IEJlRGF0YURyaXZlbi4gUmVuamluIHVzZXMgdGhlIEphdmEgdmlydHVhbCBtYWNoaW5lLCBhbmQgaGFzIGFuIGV4dGVuc2l2ZSB0ZXN0IHN1aXRlLg0KDQoNCg0KIyBTdW1tYXJ5DQoNClRvIGNvbXBsZXRlIHRoZSBwYXJ0aWFsIHF1b3RlIHJlZmVycmVkIHRvIGVhcmxpZXIuLi4NCg0KPiAiUHJvZ3JhbW1lcnMgd2FzdGUgZW5vcm1vdXMgYW1vdW50cyBvZiB0aW1lIHRoaW5raW5nIGFib3V0LCBvciB3b3JyeWluZyBhYm91dCwgdGhlIHNwZWVkIG9mIG5vbmNyaXRpY2FsIHBhcnRzIG9mIHRoZWlyIHByb2dyYW1zLCBhbmQgdGhlc2UgYXR0ZW1wdHMgYXQgZWZmaWNpZW5jeSBhY3R1YWxseSBoYXZlIGEgc3Ryb25nIG5lZ2F0aXZlIGltcGFjdCB3aGVuIGRlYnVnZ2luZyBhbmQgbWFpbnRlbmFuY2UgYXJlIGNvbnNpZGVyZWQuIFdlIHNob3VsZCBmb3JnZXQgYWJvdXQgc21hbGwgZWZmaWNpZW5jaWVzLCBzYXkgYWJvdXQgOTclIG9mIHRoZSB0aW1lOiBwcmVtYXR1cmUgb3B0aW1pemF0aW9uIGlzIHRoZSByb290IG9mIGFsbCBldmlsLiBZZXQgd2Ugc2hvdWxkIG5vdCBwYXNzIHVwIG91ciBvcHBvcnR1bml0aWVzIGluIHRoYXQgY3JpdGljYWwgMyUuIiA8YnI+PGJyPg0KXH4gRG9uYWxkIEtudXRoDQoNClRoZXJlIGFyZSBubyBnb29kIGJlbmNobWFya3MgZm9yIHRoZSBiYWxhbmNlIG9mIHByb2dyYW1taW5nIHZzLiBjb21wdXRhdGlvbmFsIHRpbWUgZm9yIHN0YXRpc3RpY2FsIGFuYWx5c2lzIGFuZCByZWxhdGVkIGFjdGl2aXRpZXMuIEhvd2V2ZXIsIHRoZSByZWFzb24gUiB3aWxsIGJlYXQgb3RoZXIgbGFuZ3VhZ2VzIGhhbmRzIGRvd24gaW4gbWFueSBjYXNlcyBpcyBiZWNhdXNlIGl0IGlzIHNvIG11Y2ggZWFzaWVyIHRvIHByb2dyYW0gY2VydGFpbiwgb2Z0ZW4gdmVyeSBjb21tb24gb3BlcmF0aW9ucy4gRnVydGhlcm1vcmUsIHRoZSBmdW5jdGlvbmFsaXR5IGF2YWlsYWJsZSBhY3Jvc3MgYSB3aWRlIHZhcmlldHkgb2YgbW9kZWxpbmcgcGFyYWRpZ21zIGlzIHVubWF0Y2hlZCBhdCBwcmVzZW50LiBLbm93aW5nIGp1c3QgYSBmZXcgJ3RyaWNrcycgc3VjaCBhcyB0aG9zZSBkZW1vbnN0cmF0ZWQgaGVyZSB3aWxsIGhlbHAgZ2FpbiB0aG9zZSBzbWFsbCBlZmZpY2llbmNpZXMgaW4gdGhlIDk3JSB0aW1lLiAgSW4gdGhlIGVuZCwgd2hhdCBhcHByb2FjaCB3b3JrcyBiZXN0IHdpbGwgZGVwZW5kIG9uIHRoZSBzcGVjaWZpY3Mgb2YgdGhlIHRhc2ssIGJ1dCB5b3Ugd2lsbCBhbHdheXMgaGF2ZSBvcHRpb25zIHdpdGggUiwgYW5kIG9mdGVuIHByZXR0eSBmYXN0IG9uZXMuDQoNCg0KDQojIFJlZmVyZW5jZXMNCg0KVHdvIGV4Y2VsbGVudCB0ZXh0cyBvbiBSIHByb2dyYW1taW5nIGFyZToNCg0KW1RoZSBBcnQgb2YgUiBQcm9ncmFtbWluZ10oaHR0cHM6Ly93d3cubm9zdGFyY2guY29tL2FydG9mci5odG0pIGJ5IE5vcm0gTWF0bG9mZg0KDQpbQWR2YW5jZWQgUl0oaHR0cDovL2Fkdi1yLmhhZC5jby5uei8pIGJ5IEhhZGxleSBXaWNraGFtLg==