This notebook investigates use of a genetic algorithm and a simple improvement heuristic for a graph coloring problem posed on OR Stack Exchange.

Setup

We will use CPLEX (with the ompr and ROI libraries) to try (unsuccessfully) to find an optimal solution and the ga library to test a genetic algorithm. The improvement heuristic requires no external libraries. We will also use the tictoc library for timing the GA and heuristic.

# Libraries needed for the MIP model.
library(ompr)
library(ompr.roi)
library(ROI)
library(ROI.plugin.cplex)
# Library needed for the GA.
library(GA)
# Library used to time the GA and heuristic.
library(tictoc)

Test graph

We generate a random test graph. The graph will be complete (every pair of nodes connected by an edge). The original question relates to a sensor network where sensors interfere with each other (with interference presumably a decreasing function of distance). We will use a rectangular grid of nodes and assign edge weights (interference levels) based on a nonlinear function of distance (with randomness).

We first set the number of colors allowed and create the grid.

# Set the number of available colors.
n_colors <- 5
# Set the height and width of the grid and create a matrix of node coordinates.
width <- 20
height <- 10
n_nodes <- width * height
grid <- expand.grid(x = 1:width, y = 1:height) |> as.matrix()

We assign a randomized interference value for each pair of nodes, based on the euclidean distance between the nodes. We use the exponential distribution with rate equal to the distance between the nodes (which means the expected interference level is the reciprocal of the distance). The function below computes the interference for a given pair of nodes.

# Input: indices of two nodes
# Output: an interference value
interference_level <- function(i, j) {
  # A node cannot interfere with itself (no matter how clumsy it is).
  if (i == j) {
    0
  } else {
    # Compute the distance between nodes i and j.
    dist <- norm(grid[i, ] - grid[j, ], type = "2")
    # Sample an exponential distribution to get the interference level.
    rexp(1, rate = dist)
  }
}
# Seed the random number generator for reproducibility.
set.seed(123)
# Generate a matrix of interference levels.
interference <- matrix(0, nrow = n_nodes, ncol = n_nodes)
for (i in 1:(n_nodes - 1)){
  for (j in (i + 1):n_nodes) {
    x <- interference_level(i, j)
    interference[i, j] <- x
    interference[j, i] <- x
  }
}

Utility functions

At various points below we will deal with either a vector of dimension n_nodes containing color assignments for each node or a list with n_colors elements, where each list entry is a vector containing the nodes assigned that color. The following functions convert between them.

# Input: a vector of color assignments for each node
# Output: a list of vectors containing the nodes assigned each color
make_color_list <- function(x) {
  # Create a list of (empty) lists of nodes, one per color.
  colored <- list()
  for (i in 1:n_colors) {
    colored[[i]] <- list()
  }
  # Assign each node to its color set.
  for (i in 1:n_nodes) {
    colored[[x[i]]] <- c(colored[[x[i]]], i)
  }
  # Convert each color set to a vector.
  colored <- lapply(colored, unlist)
  # Return the list.
  colored
}
# Input: a list of vectors, each vector containing the nodes assigned a specific color
# Output: a vector containing the color for each node
make_color_vector <- function(x) {
  # Create an empty output vector.
  assigned <- rep.int(0, n_nodes)
  # Assign each node its color.
  for (i in 1:n_colors) {
    for (j in x[[i]]) {
      assigned[j] <- i
    }
  }
  # Return the result.
  assigned
}

We will want to compute a total interference value from a color list. The following function does that.

# Input: a list of vectors, each vector containing the nodes assigned a specific color
# Output: the total interference resulting from that coloring scheme
total_interference <- function(x) {
  # Compute the objective value.
  obj <- 0
  for (i in 1:n_colors) {
    obj <- obj + sum(interference[x[[i]], x[[i]]])
  }
  # Correct double-counting of edges.
  obj <- obj / 2
  # Return the objective value.
  obj
}

Given a coloring scheme (list), a node and a particular color, we will want to compute the contribution to interference of that node if assigned that color. The following function does this.

# Input: a coloring scheme (list), a node and a color to assign that node
# Output: the total interference generated by that node and nodes already assigned that color
interference_contribution <- function(coloring, node, color) {
  # Get the nodes assigned the target color (which may or may not already include the target node).
  others <- coloring[[color]]
  # Compute and return the total interference generated by the target node if given that color.
  interference[node, others] |> sum()
}

MIP model

The MIP model uses a binary variable \(x_{n,c}\) for each combination of node \(n\) and color \(c\) (1 if that color is assigned to that node) and a continuous variable \(y_{i,j}\)for each pair \(i<j\) of nodes (containing the interference incurred if the nodes have the same color).

Model setup

# Create the model and variables.
mip <- MIPModel() |>
         add_variable(x[n, c], n = 1:n_nodes, c = 1:n_colors, type = "binary") |>
         add_variable(y[i, j], i = 1:(n_nodes - 1), j = (i + 1):n_nodes, type = "continuous", lb = 0)

The objective is to minimize the sum of the interference variables \(y\).

mip <- mip |> set_objective(sum_expr(y[i, j], i = 1:(n_nodes - 1), j = (i + 1):n_nodes), sense = "min")

Every node must be assigned exactly one color.

mip <- mip |> add_constraint(sum_expr(x[n, c], c = 1:n_colors) == 1, n = 1:n_nodes)

For every pair \(i<j\) of nodes and every color \(c\), the objective contribution \(y_{i,j}\) of the node pair is at least the interference level \(\lambda_{i,j}\) between those nodes if both are assigned color \(c\): \(y_{i,j} \ge \lambda_{i,j} * (x_{i,c} + x_{j,c}-1)\).

mip <- mip |> add_constraint(y[i, j] >= interference[i, j]*(x[i, c] + x[j, c] - 1), i = 1:(n_nodes - 1), j = (i + 1):n_nodes, c = 1:n_colors)

Since the objective value is invariant under permutations of the colors, we arbitrarily require that the first node be assigned the first color and that the lowest index of any nodes with a given color be greater than the lowest index of any nodes with the preceding color.

mip <- mip |> add_constraint(x[1, 1] == 1) |>
              add_constraint(x[n, c] <= sum_expr(x[i, c - 1], i = 1:(n - 1)), n = 2:n_nodes, c = 2:n_colors)

Model solution

We use CPLEX to try to find an optimal coloring.

# Set a time limit.
time_limit <- 300  # five minutes
solution <- mip |> solve_model(with_ROI(solver = "cplex", verbose = TRUE, max_time = time_limit))
<SOLVER MSG>  ----
CPLEX environment opened
Rcplex: num variables=20900 num constraints=100497
Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
CPXPARAM_TimeLimit                               300
CPXPARAM_MIP_Tolerances_AbsMIPGap                0
CPXPARAM_MIP_Pool_RelGap                         0
CPXPARAM_MIP_Pool_AbsGap                         0
Tried aggregator 2 times.
MIP Presolve eliminated 2386 rows and 210 columns.
Aggregator did 1 substitutions.
Reduced MIP has 98110 rows, 20689 columns, and 352051 nonzeros.
Reduced MIP has 988 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.20 sec. (190.77 ticks)
Found incumbent of value 3689.160268 after 0.26 sec. (243.24 ticks)
Probing time = 0.06 sec. (10.10 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Reduced MIP has 98110 rows, 20689 columns, and 352051 nonzeros.
Reduced MIP has 988 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.37 sec. (184.52 ticks)
Probing time = 0.08 sec. (11.95 ticks)
Clique table members: 211.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 1.62 sec. (628.59 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                         3689.1603        0.0000           100.00%
*     0+    0                         3598.8500        0.0000           100.00%
      0     0        0.0213   394     3598.8500        0.0213     1673  100.00%
      0     0        0.0465   394     3598.8500     Fract: 34     1719  100.00%
      0     0        0.0678   553     3598.8500     Fract: 51     2089  100.00%
*     0+    0                         1938.2972        0.0678           100.00%
Detecting symmetries...
      0     2        0.0678   553     1938.2972        0.0678     2089  100.00%
Elapsed time = 15.41 sec. (6583.75 ticks, tree = 0.02 MB, solutions = 1)
      2     4        0.0776   393     1938.2972        0.0776     2100  100.00%
      3     5        0.1835   393     1938.2972        0.0776     2977  100.00%
      4     5        3.4905   392     1938.2972        0.0776     3690  100.00%
      7     9        4.6417   388     1938.2972        0.0776     4877  100.00%
      8    10       11.0805   388     1938.2972        0.0776     5766  100.00%
     10     4        3.4168   392     1938.2972        0.0776     5051  100.00%
     14    13        3.7398   393     1938.2972        0.2266    12099   99.99%
     15    12       10.5034   388     1938.2972        0.2266     7210   99.99%
     20    14        0.3158   391     1938.2972        0.2266    14422   99.99%
*    24+   22                          991.0829        0.2448            99.98%
     24    21        0.4856   393      991.0829        0.2448    24007   99.98%
Elapsed time = 79.05 sec. (16109.96 ticks, tree = 0.12 MB, solutions = 1)
     30    26        3.6741   392      991.0829        0.2448    30086   99.98%
*    31+   27                          807.3359        0.2448            99.97%
     34    27        0.7189   391      807.3359        0.2448    30863   99.97%
     36    33       10.8543   388      807.3359        0.2448    42841   99.97%
     47    41        8.0377   388      807.3359        0.2448    46909   99.97%
     59    54        8.5325   385      807.3359        0.2448    55814   99.97%
     68    44        3.7280   393      807.3359        0.2448    56859   99.97%
     81    72       10.7949   383      807.3359        0.2448    59257   99.97%
     90    75       12.2833   379      807.3359        0.2448    60215   99.97%
     99    93        0.4304   590      807.3359        0.2448    70250   99.97%
    104    94       15.3746   376      807.3359        0.2448    68067   99.97%
Elapsed time = 149.26 sec. (26956.60 ticks, tree = 32.89 MB, solutions = 1)
    114    98       21.2819   376      807.3359        0.2448    69087   99.97%
    119   105        3.4362   387      807.3359        0.2448    75486   99.97%
    124   110       20.6803   376      807.3359        0.2448    77561   99.97%
    126   126       16.0803   377      807.3359        0.2448    84324   99.97%
    129   129       21.0668   372      807.3359        0.2448    85376   99.97%
    132   134        9.0986   384      807.3359        0.2448    86101   99.97%
    138   138       15.9108   382      807.3359        0.2448    87239   99.97%
    142   140       16.0447   382      807.3359        0.2448    88247   99.97%
    147   140       22.4012   371      807.3359        0.2448    89233   99.97%
    150   113        1.1354   390      807.3359        0.2448    78634   99.97%
Elapsed time = 250.41 sec. (39808.65 ticks, tree = 38.23 MB, solutions = 1)
    151   139        5.9068   390      807.3359        0.2448    89678   99.97%
    154   141        6.7106   390      807.3359        0.2448    91182   99.97%
    162   146        2.3123   388      807.3359        0.2448    92499   99.97%
    165   144       12.3058   386      807.3359        0.2448    91944   99.97%
    174   152        9.3810   386      807.3359        0.2448    94954   99.97%

Gomory fractional cuts applied:  9

Root node processing (before b&c):
  Real time             =   15.35 sec. (6525.54 ticks)
Parallel b&c, 4 threads:
  Real time             =  284.77 sec. (40835.03 ticks)
  Sync time (average)   =   11.82 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =  300.12 sec. (47360.57 ticks)
Closed CPLEX environment
<!SOLVER MSG> ----
cat("Best interference value achieved = ", solution$objective_value, ".\n")
Best interference value achieved =  807.3359 .

The MIP modelis apparently weak, in that the gap is huge and closing very, very slowly.

Genetic algorithm

The chromosome for our genetic algorithm will be a real vector in \([0, C]^N,\) where \(C\) is the number of colors available and \(N\) is the number of nodes to color. The ceiling of each entry will be the color assigned to that node.

GA setup

We need a function that will decode a chromosome (permutation vector) and return the corresponding node coloring along with the interference value.

# Input: a real vector with one entry per node
# Output: a list containing a solution (expressed as a list of lists of nodes getting each color) and its interference level
decode <- function(x) {
  # Apply the ceiling function to convert fractions to integer color indices.
  x <- ceiling(x)
  # Create a list of vectors of nodes getting each color.
  colored <- make_color_list(x)
  # Compute the objective value and return the solution
  list(colors = colored, value = total_interference(colored))
}

The fitness function decodes a chromosome and extracts the objective value. Since the GA is designed to maximize, we maximize the reciprocal of the interference level.

# Input: a chromosome
# Output: the objective value
fit_value <- function(x) {
  1 / decode(x)$value
}

GA solution

We can now run the genetic algorithm. For reproducibility, we reseed the random number stream. We will use more than the default number of generations (2,000 rather than 100) and a larger than default population size (100 rather than 50) but otherwise go with default parameter values.

# Reseed the random number stream.
set.seed(12345)
# Start timing.
tic()
result <- ga(type = "real-valued", fitness = fit_value,
             lower = rep.int(0, n_nodes), upper = rep.int(n_colors, n_nodes),
             popSize = 100, maxiter = 2000, run = 100, monitor = FALSE)
# Stop timing.
toc()
37.7 sec elapsed

We need to decode the best solution found.

solution <- decode(result@solution[1, ])
cat("Best interference level achieved = ", solution$value, "\nColoring")
Best interference level achieved =  495.7567 
Coloring
print(solution$colors)
[[1]]
 [1]   1   6  11  12  15  23  27  31  38  39  44  49  53  64  65  74  78  80  82  89 106 111 114 116
[25] 122 128 131 145 152 160 163 166 167 173 176 178 190 196

[[2]]
 [1]   8  13  14  21  24  35  42  46  50  54  57  58  61  62  69  85  90  92  95  97 100 101 104 123
[25] 127 130 133 136 140 141 146 149 155 174 185 187 188 193 194 198 200

[[3]]
 [1]   2   7   9  18  20  25  32  33  36  37  47  60  63  68  70  71  76  81  87  91  94 103 108 109
[25] 118 119 121 125 135 137 142 148 150 158 165 170 177 180 181 184 192 195

[[4]]
 [1]   4   5  10  16  19  41  48  52  56  59  67  72  73  83  86  88  98  99 102 105 110 112 113 117
[25] 129 139 144 147 154 156 157 159 161 162 171 183 186 189 197 199

[[5]]
 [1]   3  17  22  26  28  29  30  34  40  43  45  51  55  66  75  77  79  84  93  96 107 115 120 124
[25] 126 132 134 138 143 151 153 164 168 169 172 175 179 182 191

Improvement heuristic

We now try a simple improvement heuristic. The heuristic starts with a random assignment of colors to nodes. In each iteration of the heuristic, the nodes are considered in random order and have their colors reassigned to the “cheapest” color given the current solution. This results in a nonincreasing sequence of interference values. Iterations continue until a full pass through the randomized list of nodes results in no improvement.

Setup

Since we may want to run the heuristic with random restarts, we will embed it in a function.

# Input: none
# Output: a list containing a coloring (list) and objective value
improvement_heuristic <- function() {
  # Assign an initial coloring randomly.
  color_vector <- sample(1:n_colors, size = n_nodes, replace = TRUE)
  # Turn it into a list of color assignments.
  color_list <- make_color_list(color_vector)
  # Compute the total interference level.
  objective <- total_interference(color_list)
  # Set a flag to indicated whether anything has changed.
  changed <- TRUE
  # Repeat passes through the nodes until nothing changes.
  while (changed) {
    # Clear the flag.
    changed <- FALSE
    # Shuffle the node indices.
    todo <- sample(1:n_nodes, size = n_nodes, replace = FALSE)
    # Check each node for a possible shift.
    for (i in todo) {
      # Get the current color of the node.
      current <- color_vector[i]
      # Evaluate the cost contribution for each node if assigned each color.
      costs <- sapply(1:n_colors, function(x) interference_contribution(color_list, i, x))
      # Select the color with the least incremental cost.
      choice <- which.min(costs)
      # If the color is not the one currently assigned to i, change the assignment and update the objective value and change flag.
      if (choice != current) {
        # Remove the node from its old color list.
        color_list[[current]] <- setdiff(color_list[[current]], i)
        # Add it to the new color list.
        color_list[[choice]] <- c(color_list[[choice]], i)
        # Update the color vector.
        color_vector[i] <- choice
        # Update the objective value.
        objective <- objective - costs[current] + costs[choice]
        # Update the change flag.
        changed <- TRUE
      }
    }
  }
  # Return the final solution.
  list(colors = color_list, value = objective)
}

Solution

We will reseed the random number generator (again for reproducibility), run the heuristic a fixed number of times, and keep the best solution.

# Set the number of runs.
n_runs <- 600
# Reseed the random number generator.
set.seed(12345)
# Start timing.
tic()
# Run the heuristic once to get an incumbent.
incumbent <- improvement_heuristic()
# Run the heuristic repeatedly, keeping the best solution.
for (i in 2:n_runs) {
  sol <- improvement_heuristic()
  if (sol$value < incumbent$value) {
    incumbent <- sol
  }
}
# Stop timing.
toc()
36.731 sec elapsed
# Display the final incumbent.
print(incumbent)
$colors
$colors[[1]]
 [1]  26  32  48  49 100 111 116 140 146 154 188  59 200 189  16 104  84  30 166 114  35  15 182   5
[25] 152  83 107 102 184  53   4 196  98  74 136 178 197 128  67   1

$colors[[2]]
 [1]  76  85  95 123 133 160 174 176 186 199  70 130 109   9 122  61   2  46  58  42 131 135  80  92
[25]  36 177   7 187 148  13 194  51 101 144  62  79 190  19 149  55  24

$colors[[3]]
 [1]  50  60  88  96 151 156 168 185  64 158 173 180 172  18   8 169  65  72  45  14 183   3 132 163
[25] 118 110  77  86 120  73  63  90  39 113  94 159  81 164 162  54  25

$colors[[4]]
 [1]  43  56 155 181 193 112 139  99  12 157 165 129 142 167 191 134 105 119  40  89 121 106  27  75
[25] 124  10  17  52 175 147  47  21  69  31 103 195 179  38 161

$colors[[5]]
 [1]  20  28  41  71  78  87 143 192 153  37 126  29 141  22  57  97  66 171 117 125  34  33 150  11
[25]   6 127  23  44 108  91  68  93 137 115 170 138 145 198  82


$value
[1] 467.9298

In this (and a few other runs attempted) the heuristic, with restarts, produces a somewhat better solution than the GA does.

LS0tCnRpdGxlOiAiR3JhcGggQ29sb3JpbmciCmF1dGhvcjogIlBhdWwgQS4gUnViaW4iCmRhdGU6ICJBcHJpbCAxNSwgMjAyMyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKVGhpcyBub3RlYm9vayBpbnZlc3RpZ2F0ZXMgdXNlIG9mIGEgZ2VuZXRpYyBhbGdvcml0aG0gYW5kIGEgc2ltcGxlIGltcHJvdmVtZW50IGhldXJpc3RpYyBmb3IgYSBbZ3JhcGggY29sb3JpbmcgcHJvYmxlbV0oaHR0cHM6Ly9vci5zdGFja2V4Y2hhbmdlLmNvbS9xdWVzdGlvbnMvMTAzMjEvY29sb3Jpbmctb2Ytbm9kZXMtb2YtYS1zZW5zb3ItbmV0d29yaykgcG9zZWQgb24gT1IgU3RhY2sgRXhjaGFuZ2UuCgojIFNldHVwCgpXZSB3aWxsIHVzZSBDUExFWCAod2l0aCB0aGUgYG9tcHJgIGFuZCBgUk9JYCBsaWJyYXJpZXMpIHRvIHRyeSAodW5zdWNjZXNzZnVsbHkpIHRvIGZpbmQgYW4gb3B0aW1hbCBzb2x1dGlvbiBhbmQgdGhlIGBnYWAgbGlicmFyeSB0byB0ZXN0IGEgZ2VuZXRpYyBhbGdvcml0aG0uIFRoZSBpbXByb3ZlbWVudCBoZXVyaXN0aWMgcmVxdWlyZXMgbm8gZXh0ZXJuYWwgbGlicmFyaWVzLiBXZSB3aWxsIGFsc28gdXNlIHRoZSBgdGljdG9jYCBsaWJyYXJ5IGZvciB0aW1pbmcgdGhlIEdBIGFuZCBoZXVyaXN0aWMuCgpgYGB7ciwgbWVzc2FnZT1GQUxTRX0KIyBMaWJyYXJpZXMgbmVlZGVkIGZvciB0aGUgTUlQIG1vZGVsLgpsaWJyYXJ5KG9tcHIpCmxpYnJhcnkob21wci5yb2kpCmxpYnJhcnkoUk9JKQpsaWJyYXJ5KFJPSS5wbHVnaW4uY3BsZXgpCiMgTGlicmFyeSBuZWVkZWQgZm9yIHRoZSBHQS4KbGlicmFyeShHQSkKIyBMaWJyYXJ5IHVzZWQgdG8gdGltZSB0aGUgR0EgYW5kIGhldXJpc3RpYy4KbGlicmFyeSh0aWN0b2MpCmBgYAoKCiMgVGVzdCBncmFwaAoKV2UgZ2VuZXJhdGUgYSByYW5kb20gdGVzdCBncmFwaC4gVGhlIGdyYXBoIHdpbGwgYmUgY29tcGxldGUgKGV2ZXJ5IHBhaXIgb2Ygbm9kZXMgY29ubmVjdGVkIGJ5IGFuIGVkZ2UpLiBUaGUgb3JpZ2luYWwgcXVlc3Rpb24gcmVsYXRlcyB0byBhIHNlbnNvciBuZXR3b3JrIHdoZXJlIHNlbnNvcnMgaW50ZXJmZXJlIHdpdGggZWFjaCBvdGhlciAod2l0aCBpbnRlcmZlcmVuY2UgcHJlc3VtYWJseSBhIGRlY3JlYXNpbmcgZnVuY3Rpb24gb2YgZGlzdGFuY2UpLiBXZSB3aWxsIHVzZSBhIHJlY3Rhbmd1bGFyIGdyaWQgb2Ygbm9kZXMgYW5kIGFzc2lnbiBlZGdlIHdlaWdodHMgKGludGVyZmVyZW5jZSBsZXZlbHMpIGJhc2VkIG9uIGEgbm9ubGluZWFyIGZ1bmN0aW9uIG9mIGRpc3RhbmNlICh3aXRoIHJhbmRvbW5lc3MpLgoKV2UgZmlyc3Qgc2V0IHRoZSBudW1iZXIgb2YgY29sb3JzIGFsbG93ZWQgYW5kIGNyZWF0ZSB0aGUgZ3JpZC4KCmBgYHtyfQojIFNldCB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBjb2xvcnMuCm5fY29sb3JzIDwtIDUKIyBTZXQgdGhlIGhlaWdodCBhbmQgd2lkdGggb2YgdGhlIGdyaWQgYW5kIGNyZWF0ZSBhIG1hdHJpeCBvZiBub2RlIGNvb3JkaW5hdGVzLgp3aWR0aCA8LSAyMApoZWlnaHQgPC0gMTAKbl9ub2RlcyA8LSB3aWR0aCAqIGhlaWdodApncmlkIDwtIGV4cGFuZC5ncmlkKHggPSAxOndpZHRoLCB5ID0gMTpoZWlnaHQpIHw+IGFzLm1hdHJpeCgpCmBgYAoKV2UgYXNzaWduIGEgcmFuZG9taXplZCBpbnRlcmZlcmVuY2UgdmFsdWUgZm9yIGVhY2ggcGFpciBvZiBub2RlcywgYmFzZWQgb24gdGhlIGV1Y2xpZGVhbiBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBub2Rlcy4gV2UgdXNlIHRoZSBleHBvbmVudGlhbCBkaXN0cmlidXRpb24gd2l0aCByYXRlIGVxdWFsIHRvIHRoZSBkaXN0YW5jZSBiZXR3ZWVuIHRoZSBub2RlcyAod2hpY2ggbWVhbnMgdGhlIGV4cGVjdGVkIGludGVyZmVyZW5jZSBsZXZlbCBpcyB0aGUgcmVjaXByb2NhbCBvZiB0aGUgZGlzdGFuY2UpLiBUaGUgZnVuY3Rpb24gYmVsb3cgY29tcHV0ZXMgdGhlIGludGVyZmVyZW5jZSBmb3IgYSBnaXZlbiBwYWlyIG9mIG5vZGVzLgoKYGBge3J9CiMgSW5wdXQ6IGluZGljZXMgb2YgdHdvIG5vZGVzCiMgT3V0cHV0OiBhbiBpbnRlcmZlcmVuY2UgdmFsdWUKaW50ZXJmZXJlbmNlX2xldmVsIDwtIGZ1bmN0aW9uKGksIGopIHsKICAjIEEgbm9kZSBjYW5ub3QgaW50ZXJmZXJlIHdpdGggaXRzZWxmIChubyBtYXR0ZXIgaG93IGNsdW1zeSBpdCBpcykuCiAgaWYgKGkgPT0gaikgewogICAgMAogIH0gZWxzZSB7CiAgICAjIENvbXB1dGUgdGhlIGRpc3RhbmNlIGJldHdlZW4gbm9kZXMgaSBhbmQgai4KICAgIGRpc3QgPC0gbm9ybShncmlkW2ksIF0gLSBncmlkW2osIF0sIHR5cGUgPSAiMiIpCiAgICAjIFNhbXBsZSBhbiBleHBvbmVudGlhbCBkaXN0cmlidXRpb24gdG8gZ2V0IHRoZSBpbnRlcmZlcmVuY2UgbGV2ZWwuCiAgICByZXhwKDEsIHJhdGUgPSBkaXN0KQogIH0KfQpgYGAKCmBgYHtyfQojIFNlZWQgdGhlIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yIGZvciByZXByb2R1Y2liaWxpdHkuCnNldC5zZWVkKDEyMykKIyBHZW5lcmF0ZSBhIG1hdHJpeCBvZiBpbnRlcmZlcmVuY2UgbGV2ZWxzLgppbnRlcmZlcmVuY2UgPC0gbWF0cml4KDAsIG5yb3cgPSBuX25vZGVzLCBuY29sID0gbl9ub2RlcykKZm9yIChpIGluIDE6KG5fbm9kZXMgLSAxKSl7CiAgZm9yIChqIGluIChpICsgMSk6bl9ub2RlcykgewogICAgeCA8LSBpbnRlcmZlcmVuY2VfbGV2ZWwoaSwgaikKICAgIGludGVyZmVyZW5jZVtpLCBqXSA8LSB4CiAgICBpbnRlcmZlcmVuY2VbaiwgaV0gPC0geAogIH0KfQpgYGAKCiMjIFV0aWxpdHkgZnVuY3Rpb25zCgpBdCB2YXJpb3VzIHBvaW50cyBiZWxvdyB3ZSB3aWxsIGRlYWwgd2l0aCBlaXRoZXIgYSB2ZWN0b3Igb2YgZGltZW5zaW9uIGBuX25vZGVzYCBjb250YWluaW5nIGNvbG9yIGFzc2lnbm1lbnRzIGZvciBlYWNoIG5vZGUgb3IgYSBsaXN0IHdpdGggYG5fY29sb3JzYCBlbGVtZW50cywgd2hlcmUgZWFjaCBsaXN0IGVudHJ5IGlzIGEgdmVjdG9yIGNvbnRhaW5pbmcgdGhlIG5vZGVzIGFzc2lnbmVkIHRoYXQgY29sb3IuIFRoZSBmb2xsb3dpbmcgZnVuY3Rpb25zIGNvbnZlcnQgYmV0d2VlbiB0aGVtLgoKYGBge3J9CiMgSW5wdXQ6IGEgdmVjdG9yIG9mIGNvbG9yIGFzc2lnbm1lbnRzIGZvciBlYWNoIG5vZGUKIyBPdXRwdXQ6IGEgbGlzdCBvZiB2ZWN0b3JzIGNvbnRhaW5pbmcgdGhlIG5vZGVzIGFzc2lnbmVkIGVhY2ggY29sb3IKbWFrZV9jb2xvcl9saXN0IDwtIGZ1bmN0aW9uKHgpIHsKICAjIENyZWF0ZSBhIGxpc3Qgb2YgKGVtcHR5KSBsaXN0cyBvZiBub2Rlcywgb25lIHBlciBjb2xvci4KICBjb2xvcmVkIDwtIGxpc3QoKQogIGZvciAoaSBpbiAxOm5fY29sb3JzKSB7CiAgICBjb2xvcmVkW1tpXV0gPC0gbGlzdCgpCiAgfQogICMgQXNzaWduIGVhY2ggbm9kZSB0byBpdHMgY29sb3Igc2V0LgogIGZvciAoaSBpbiAxOm5fbm9kZXMpIHsKICAgIGNvbG9yZWRbW3hbaV1dXSA8LSBjKGNvbG9yZWRbW3hbaV1dXSwgaSkKICB9CiAgIyBDb252ZXJ0IGVhY2ggY29sb3Igc2V0IHRvIGEgdmVjdG9yLgogIGNvbG9yZWQgPC0gbGFwcGx5KGNvbG9yZWQsIHVubGlzdCkKICAjIFJldHVybiB0aGUgbGlzdC4KICBjb2xvcmVkCn0KYGBgCgpgYGB7cn0KIyBJbnB1dDogYSBsaXN0IG9mIHZlY3RvcnMsIGVhY2ggdmVjdG9yIGNvbnRhaW5pbmcgdGhlIG5vZGVzIGFzc2lnbmVkIGEgc3BlY2lmaWMgY29sb3IKIyBPdXRwdXQ6IGEgdmVjdG9yIGNvbnRhaW5pbmcgdGhlIGNvbG9yIGZvciBlYWNoIG5vZGUKbWFrZV9jb2xvcl92ZWN0b3IgPC0gZnVuY3Rpb24oeCkgewogICMgQ3JlYXRlIGFuIGVtcHR5IG91dHB1dCB2ZWN0b3IuCiAgYXNzaWduZWQgPC0gcmVwLmludCgwLCBuX25vZGVzKQogICMgQXNzaWduIGVhY2ggbm9kZSBpdHMgY29sb3IuCiAgZm9yIChpIGluIDE6bl9jb2xvcnMpIHsKICAgIGZvciAoaiBpbiB4W1tpXV0pIHsKICAgICAgYXNzaWduZWRbal0gPC0gaQogICAgfQogIH0KICAjIFJldHVybiB0aGUgcmVzdWx0LgogIGFzc2lnbmVkCn0KYGBgCgpXZSB3aWxsIHdhbnQgdG8gY29tcHV0ZSBhIHRvdGFsIGludGVyZmVyZW5jZSB2YWx1ZSBmcm9tIGEgY29sb3IgbGlzdC4gVGhlIGZvbGxvd2luZyBmdW5jdGlvbiBkb2VzIHRoYXQuCgpgYGB7cn0KIyBJbnB1dDogYSBsaXN0IG9mIHZlY3RvcnMsIGVhY2ggdmVjdG9yIGNvbnRhaW5pbmcgdGhlIG5vZGVzIGFzc2lnbmVkIGEgc3BlY2lmaWMgY29sb3IKIyBPdXRwdXQ6IHRoZSB0b3RhbCBpbnRlcmZlcmVuY2UgcmVzdWx0aW5nIGZyb20gdGhhdCBjb2xvcmluZyBzY2hlbWUKdG90YWxfaW50ZXJmZXJlbmNlIDwtIGZ1bmN0aW9uKHgpIHsKICAjIENvbXB1dGUgdGhlIG9iamVjdGl2ZSB2YWx1ZS4KICBvYmogPC0gMAogIGZvciAoaSBpbiAxOm5fY29sb3JzKSB7CiAgICBvYmogPC0gb2JqICsgc3VtKGludGVyZmVyZW5jZVt4W1tpXV0sIHhbW2ldXV0pCiAgfQogICMgQ29ycmVjdCBkb3VibGUtY291bnRpbmcgb2YgZWRnZXMuCiAgb2JqIDwtIG9iaiAvIDIKICAjIFJldHVybiB0aGUgb2JqZWN0aXZlIHZhbHVlLgogIG9iagp9CmBgYAoKR2l2ZW4gYSBjb2xvcmluZyBzY2hlbWUgKGxpc3QpLCBhIG5vZGUgYW5kIGEgcGFydGljdWxhciBjb2xvciwgd2Ugd2lsbCB3YW50IHRvIGNvbXB1dGUgdGhlIGNvbnRyaWJ1dGlvbiB0byBpbnRlcmZlcmVuY2Ugb2YgdGhhdCBub2RlIGlmIGFzc2lnbmVkIHRoYXQgY29sb3IuIFRoZSBmb2xsb3dpbmcgZnVuY3Rpb24gZG9lcyB0aGlzLgoKYGBge3J9CiMgSW5wdXQ6IGEgY29sb3Jpbmcgc2NoZW1lIChsaXN0KSwgYSBub2RlIGFuZCBhIGNvbG9yIHRvIGFzc2lnbiB0aGF0IG5vZGUKIyBPdXRwdXQ6IHRoZSB0b3RhbCBpbnRlcmZlcmVuY2UgZ2VuZXJhdGVkIGJ5IHRoYXQgbm9kZSBhbmQgbm9kZXMgYWxyZWFkeSBhc3NpZ25lZCB0aGF0IGNvbG9yCmludGVyZmVyZW5jZV9jb250cmlidXRpb24gPC0gZnVuY3Rpb24oY29sb3JpbmcsIG5vZGUsIGNvbG9yKSB7CiAgIyBHZXQgdGhlIG5vZGVzIGFzc2lnbmVkIHRoZSB0YXJnZXQgY29sb3IgKHdoaWNoIG1heSBvciBtYXkgbm90IGFscmVhZHkgaW5jbHVkZSB0aGUgdGFyZ2V0IG5vZGUpLgogIG90aGVycyA8LSBjb2xvcmluZ1tbY29sb3JdXQogICMgQ29tcHV0ZSBhbmQgcmV0dXJuIHRoZSB0b3RhbCBpbnRlcmZlcmVuY2UgZ2VuZXJhdGVkIGJ5IHRoZSB0YXJnZXQgbm9kZSBpZiBnaXZlbiB0aGF0IGNvbG9yLgogIGludGVyZmVyZW5jZVtub2RlLCBvdGhlcnNdIHw+IHN1bSgpCn0KYGBgCgojIE1JUCBtb2RlbAoKVGhlIE1JUCBtb2RlbCB1c2VzIGEgYmluYXJ5IHZhcmlhYmxlICR4X3tuLGN9JCBmb3IgZWFjaCBjb21iaW5hdGlvbiBvZiBub2RlICRuJCBhbmQgY29sb3IgJGMkICgxIGlmIHRoYXQgY29sb3IgaXMgYXNzaWduZWQgdG8gdGhhdCBub2RlKSBhbmQgYSBjb250aW51b3VzIHZhcmlhYmxlICR5X3tpLGp9JGZvciBlYWNoIHBhaXIgJGk8aiQgb2Ygbm9kZXMgKGNvbnRhaW5pbmcgdGhlIGludGVyZmVyZW5jZSBpbmN1cnJlZCBpZiB0aGUgbm9kZXMgaGF2ZSB0aGUgc2FtZSBjb2xvcikuCgojIyBNb2RlbCBzZXR1cAoKYGBge3J9CiMgQ3JlYXRlIHRoZSBtb2RlbCBhbmQgdmFyaWFibGVzLgptaXAgPC0gTUlQTW9kZWwoKSB8PgogICAgICAgICBhZGRfdmFyaWFibGUoeFtuLCBjXSwgbiA9IDE6bl9ub2RlcywgYyA9IDE6bl9jb2xvcnMsIHR5cGUgPSAiYmluYXJ5IikgfD4KICAgICAgICAgYWRkX3ZhcmlhYmxlKHlbaSwgal0sIGkgPSAxOihuX25vZGVzIC0gMSksIGogPSAoaSArIDEpOm5fbm9kZXMsIHR5cGUgPSAiY29udGludW91cyIsIGxiID0gMCkKYGBgCgpUaGUgb2JqZWN0aXZlIGlzIHRvIG1pbmltaXplIHRoZSBzdW0gb2YgdGhlIGludGVyZmVyZW5jZSB2YXJpYWJsZXMgJHkkLgoKYGBge3J9Cm1pcCA8LSBtaXAgfD4gc2V0X29iamVjdGl2ZShzdW1fZXhwcih5W2ksIGpdLCBpID0gMToobl9ub2RlcyAtIDEpLCBqID0gKGkgKyAxKTpuX25vZGVzKSwgc2Vuc2UgPSAibWluIikKYGBgCgpFdmVyeSBub2RlIG11c3QgYmUgYXNzaWduZWQgZXhhY3RseSBvbmUgY29sb3IuCgpgYGB7cn0KbWlwIDwtIG1pcCB8PiBhZGRfY29uc3RyYWludChzdW1fZXhwcih4W24sIGNdLCBjID0gMTpuX2NvbG9ycykgPT0gMSwgbiA9IDE6bl9ub2RlcykKYGBgCgpGb3IgZXZlcnkgcGFpciAkaTxqJCBvZiBub2RlcyBhbmQgZXZlcnkgY29sb3IgJGMkLCB0aGUgb2JqZWN0aXZlIGNvbnRyaWJ1dGlvbiAkeV97aSxqfSQgb2YgdGhlIG5vZGUgcGFpciBpcyBhdCBsZWFzdCB0aGUgaW50ZXJmZXJlbmNlIGxldmVsICRcbGFtYmRhX3tpLGp9JCBiZXR3ZWVuIHRob3NlIG5vZGVzIGlmIGJvdGggYXJlIGFzc2lnbmVkIGNvbG9yICRjJDogJHlfe2ksan0gXGdlIFxsYW1iZGFfe2ksan0gKiAoeF97aSxjfSArIHhfe2osY30tMSkkLgoKYGBge3J9Cm1pcCA8LSBtaXAgfD4gYWRkX2NvbnN0cmFpbnQoeVtpLCBqXSA+PSBpbnRlcmZlcmVuY2VbaSwgal0qKHhbaSwgY10gKyB4W2osIGNdIC0gMSksIGkgPSAxOihuX25vZGVzIC0gMSksIGogPSAoaSArIDEpOm5fbm9kZXMsIGMgPSAxOm5fY29sb3JzKQpgYGAKClNpbmNlIHRoZSBvYmplY3RpdmUgdmFsdWUgaXMgaW52YXJpYW50IHVuZGVyIHBlcm11dGF0aW9ucyBvZiB0aGUgY29sb3JzLCB3ZSBhcmJpdHJhcmlseSByZXF1aXJlIHRoYXQgdGhlIGZpcnN0IG5vZGUgYmUgYXNzaWduZWQgdGhlIGZpcnN0IGNvbG9yIGFuZCB0aGF0IHRoZSBsb3dlc3QgaW5kZXggb2YgYW55IG5vZGVzIHdpdGggYSBnaXZlbiBjb2xvciBiZSBncmVhdGVyIHRoYW4gdGhlIGxvd2VzdCBpbmRleCBvZiBhbnkgbm9kZXMgd2l0aCB0aGUgcHJlY2VkaW5nIGNvbG9yLgoKYGBge3J9Cm1pcCA8LSBtaXAgfD4gYWRkX2NvbnN0cmFpbnQoeFsxLCAxXSA9PSAxKSB8PgogICAgICAgICAgICAgIGFkZF9jb25zdHJhaW50KHhbbiwgY10gPD0gc3VtX2V4cHIoeFtpLCBjIC0gMV0sIGkgPSAxOihuIC0gMSkpLCBuID0gMjpuX25vZGVzLCBjID0gMjpuX2NvbG9ycykKYGBgCgojIyBNb2RlbCBzb2x1dGlvbgoKV2UgdXNlIENQTEVYIHRvIHRyeSB0byBmaW5kIGFuIG9wdGltYWwgY29sb3JpbmcuCgpgYGB7cn0KIyBTZXQgYSB0aW1lIGxpbWl0Lgp0aW1lX2xpbWl0IDwtIDMwMCAgIyBmaXZlIG1pbnV0ZXMKc29sdXRpb24gPC0gbWlwIHw+IHNvbHZlX21vZGVsKHdpdGhfUk9JKHNvbHZlciA9ICJjcGxleCIsIHZlcmJvc2UgPSBUUlVFLCBtYXhfdGltZSA9IHRpbWVfbGltaXQpKQpjYXQoIkJlc3QgaW50ZXJmZXJlbmNlIHZhbHVlIGFjaGlldmVkID0gIiwgc29sdXRpb24kb2JqZWN0aXZlX3ZhbHVlLCAiLlxuIikKYGBgClRoZSBNSVAgbW9kZWxpcyBhcHBhcmVudGx5IHdlYWssIGluIHRoYXQgdGhlIGdhcCBpcyBodWdlIGFuZCBjbG9zaW5nIHZlcnksIHZlcnkgc2xvd2x5LgoKIyBHZW5ldGljIGFsZ29yaXRobQoKVGhlIGNocm9tb3NvbWUgZm9yIG91ciBnZW5ldGljIGFsZ29yaXRobSB3aWxsIGJlIGEgcmVhbCB2ZWN0b3IgaW4gJFswLCBDXV5OLCQgd2hlcmUgJEMkIGlzIHRoZSBudW1iZXIgb2YgY29sb3JzIGF2YWlsYWJsZSBhbmQgJE4kIGlzIHRoZSBudW1iZXIgb2Ygbm9kZXMgdG8gY29sb3IuIFRoZSBjZWlsaW5nIG9mIGVhY2ggZW50cnkgd2lsbCBiZSB0aGUgY29sb3IgYXNzaWduZWQgdG8gdGhhdCBub2RlLgoKIyMgR0Egc2V0dXAKCldlIG5lZWQgYSBmdW5jdGlvbiB0aGF0IHdpbGwgZGVjb2RlIGEgY2hyb21vc29tZSAocGVybXV0YXRpb24gdmVjdG9yKSBhbmQgcmV0dXJuIHRoZSBjb3JyZXNwb25kaW5nIG5vZGUgY29sb3JpbmcgYWxvbmcgd2l0aCB0aGUgaW50ZXJmZXJlbmNlIHZhbHVlLgoKYGBge3J9CiMgSW5wdXQ6IGEgcmVhbCB2ZWN0b3Igd2l0aCBvbmUgZW50cnkgcGVyIG5vZGUKIyBPdXRwdXQ6IGEgbGlzdCBjb250YWluaW5nIGEgc29sdXRpb24gKGV4cHJlc3NlZCBhcyBhIGxpc3Qgb2YgbGlzdHMgb2Ygbm9kZXMgZ2V0dGluZyBlYWNoIGNvbG9yKSBhbmQgaXRzIGludGVyZmVyZW5jZSBsZXZlbApkZWNvZGUgPC0gZnVuY3Rpb24oeCkgewogICMgQXBwbHkgdGhlIGNlaWxpbmcgZnVuY3Rpb24gdG8gY29udmVydCBmcmFjdGlvbnMgdG8gaW50ZWdlciBjb2xvciBpbmRpY2VzLgogIHggPC0gY2VpbGluZyh4KQogICMgQ3JlYXRlIGEgbGlzdCBvZiB2ZWN0b3JzIG9mIG5vZGVzIGdldHRpbmcgZWFjaCBjb2xvci4KICBjb2xvcmVkIDwtIG1ha2VfY29sb3JfbGlzdCh4KQogICMgQ29tcHV0ZSB0aGUgb2JqZWN0aXZlIHZhbHVlIGFuZCByZXR1cm4gdGhlIHNvbHV0aW9uCiAgbGlzdChjb2xvcnMgPSBjb2xvcmVkLCB2YWx1ZSA9IHRvdGFsX2ludGVyZmVyZW5jZShjb2xvcmVkKSkKfQpgYGAKClRoZSBmaXRuZXNzIGZ1bmN0aW9uIGRlY29kZXMgYSBjaHJvbW9zb21lIGFuZCBleHRyYWN0cyB0aGUgb2JqZWN0aXZlIHZhbHVlLiBTaW5jZSB0aGUgR0EgaXMgZGVzaWduZWQgdG8gbWF4aW1pemUsIHdlIG1heGltaXplIHRoZSByZWNpcHJvY2FsIG9mIHRoZSBpbnRlcmZlcmVuY2UgbGV2ZWwuCgpgYGB7cn0KIyBJbnB1dDogYSBjaHJvbW9zb21lCiMgT3V0cHV0OiB0aGUgb2JqZWN0aXZlIHZhbHVlCmZpdF92YWx1ZSA8LSBmdW5jdGlvbih4KSB7CiAgMSAvIGRlY29kZSh4KSR2YWx1ZQp9CmBgYAoKIyMgR0Egc29sdXRpb24KCldlIGNhbiBub3cgcnVuIHRoZSBnZW5ldGljIGFsZ29yaXRobS4gRm9yIHJlcHJvZHVjaWJpbGl0eSwgd2UgcmVzZWVkIHRoZSByYW5kb20gbnVtYmVyIHN0cmVhbS4gV2Ugd2lsbCB1c2UgbW9yZSB0aGFuIHRoZSBkZWZhdWx0IG51bWJlciBvZiBnZW5lcmF0aW9ucyAoMiwwMDAgcmF0aGVyIHRoYW4gMTAwKSBhbmQgYSBsYXJnZXIgdGhhbiBkZWZhdWx0IHBvcHVsYXRpb24gc2l6ZSAoMTAwIHJhdGhlciB0aGFuIDUwKSBidXQgb3RoZXJ3aXNlIGdvIHdpdGggZGVmYXVsdCBwYXJhbWV0ZXIgdmFsdWVzLgoKYGBge3J9CiMgUmVzZWVkIHRoZSByYW5kb20gbnVtYmVyIHN0cmVhbS4Kc2V0LnNlZWQoMTIzNDUpCiMgU3RhcnQgdGltaW5nLgp0aWMoKQpyZXN1bHQgPC0gZ2EodHlwZSA9ICJyZWFsLXZhbHVlZCIsIGZpdG5lc3MgPSBmaXRfdmFsdWUsCiAgICAgICAgICAgICBsb3dlciA9IHJlcC5pbnQoMCwgbl9ub2RlcyksIHVwcGVyID0gcmVwLmludChuX2NvbG9ycywgbl9ub2RlcyksCiAgICAgICAgICAgICBwb3BTaXplID0gMTAwLCBtYXhpdGVyID0gMjAwMCwgcnVuID0gMTAwLCBtb25pdG9yID0gRkFMU0UpCiMgU3RvcCB0aW1pbmcuCnRvYygpCmBgYAoKV2UgbmVlZCB0byBkZWNvZGUgdGhlIGJlc3Qgc29sdXRpb24gZm91bmQuCgpgYGB7cn0Kc29sdXRpb24gPC0gZGVjb2RlKHJlc3VsdEBzb2x1dGlvblsxLCBdKQpjYXQoIkJlc3QgaW50ZXJmZXJlbmNlIGxldmVsIGFjaGlldmVkID0gIiwgc29sdXRpb24kdmFsdWUsICJcbkNvbG9yaW5nIikKcHJpbnQoc29sdXRpb24kY29sb3JzKQpgYGAKCiMgSW1wcm92ZW1lbnQgaGV1cmlzdGljCgpXZSBub3cgdHJ5IGEgc2ltcGxlIGltcHJvdmVtZW50IGhldXJpc3RpYy4gVGhlIGhldXJpc3RpYyBzdGFydHMgd2l0aCBhIHJhbmRvbSBhc3NpZ25tZW50IG9mIGNvbG9ycyB0byBub2Rlcy4gSW4gZWFjaCBpdGVyYXRpb24gb2YgdGhlIGhldXJpc3RpYywgdGhlIG5vZGVzIGFyZSBjb25zaWRlcmVkIGluIHJhbmRvbSBvcmRlciBhbmQgaGF2ZSB0aGVpciBjb2xvcnMgcmVhc3NpZ25lZCB0byB0aGUgImNoZWFwZXN0IiBjb2xvciBnaXZlbiB0aGUgY3VycmVudCBzb2x1dGlvbi4gVGhpcyByZXN1bHRzIGluIGEgbm9uaW5jcmVhc2luZyBzZXF1ZW5jZSBvZiBpbnRlcmZlcmVuY2UgdmFsdWVzLiBJdGVyYXRpb25zIGNvbnRpbnVlIHVudGlsIGEgZnVsbCBwYXNzIHRocm91Z2ggdGhlIHJhbmRvbWl6ZWQgbGlzdCBvZiBub2RlcyByZXN1bHRzIGluIG5vIGltcHJvdmVtZW50LgoKIyMgU2V0dXAKClNpbmNlIHdlIG1heSB3YW50IHRvIHJ1biB0aGUgaGV1cmlzdGljIHdpdGggcmFuZG9tIHJlc3RhcnRzLCB3ZSB3aWxsIGVtYmVkIGl0IGluIGEgZnVuY3Rpb24uCgpgYGB7cn0KIyBJbnB1dDogbm9uZQojIE91dHB1dDogYSBsaXN0IGNvbnRhaW5pbmcgYSBjb2xvcmluZyAobGlzdCkgYW5kIG9iamVjdGl2ZSB2YWx1ZQppbXByb3ZlbWVudF9oZXVyaXN0aWMgPC0gZnVuY3Rpb24oKSB7CiAgIyBBc3NpZ24gYW4gaW5pdGlhbCBjb2xvcmluZyByYW5kb21seS4KICBjb2xvcl92ZWN0b3IgPC0gc2FtcGxlKDE6bl9jb2xvcnMsIHNpemUgPSBuX25vZGVzLCByZXBsYWNlID0gVFJVRSkKICAjIFR1cm4gaXQgaW50byBhIGxpc3Qgb2YgY29sb3IgYXNzaWdubWVudHMuCiAgY29sb3JfbGlzdCA8LSBtYWtlX2NvbG9yX2xpc3QoY29sb3JfdmVjdG9yKQogICMgQ29tcHV0ZSB0aGUgdG90YWwgaW50ZXJmZXJlbmNlIGxldmVsLgogIG9iamVjdGl2ZSA8LSB0b3RhbF9pbnRlcmZlcmVuY2UoY29sb3JfbGlzdCkKICAjIFNldCBhIGZsYWcgdG8gaW5kaWNhdGVkIHdoZXRoZXIgYW55dGhpbmcgaGFzIGNoYW5nZWQuCiAgY2hhbmdlZCA8LSBUUlVFCiAgIyBSZXBlYXQgcGFzc2VzIHRocm91Z2ggdGhlIG5vZGVzIHVudGlsIG5vdGhpbmcgY2hhbmdlcy4KICB3aGlsZSAoY2hhbmdlZCkgewogICAgIyBDbGVhciB0aGUgZmxhZy4KICAgIGNoYW5nZWQgPC0gRkFMU0UKICAgICMgU2h1ZmZsZSB0aGUgbm9kZSBpbmRpY2VzLgogICAgdG9kbyA8LSBzYW1wbGUoMTpuX25vZGVzLCBzaXplID0gbl9ub2RlcywgcmVwbGFjZSA9IEZBTFNFKQogICAgIyBDaGVjayBlYWNoIG5vZGUgZm9yIGEgcG9zc2libGUgc2hpZnQuCiAgICBmb3IgKGkgaW4gdG9kbykgewogICAgICAjIEdldCB0aGUgY3VycmVudCBjb2xvciBvZiB0aGUgbm9kZS4KICAgICAgY3VycmVudCA8LSBjb2xvcl92ZWN0b3JbaV0KICAgICAgIyBFdmFsdWF0ZSB0aGUgY29zdCBjb250cmlidXRpb24gZm9yIGVhY2ggbm9kZSBpZiBhc3NpZ25lZCBlYWNoIGNvbG9yLgogICAgICBjb3N0cyA8LSBzYXBwbHkoMTpuX2NvbG9ycywgZnVuY3Rpb24oeCkgaW50ZXJmZXJlbmNlX2NvbnRyaWJ1dGlvbihjb2xvcl9saXN0LCBpLCB4KSkKICAgICAgIyBTZWxlY3QgdGhlIGNvbG9yIHdpdGggdGhlIGxlYXN0IGluY3JlbWVudGFsIGNvc3QuCiAgICAgIGNob2ljZSA8LSB3aGljaC5taW4oY29zdHMpCiAgICAgICMgSWYgdGhlIGNvbG9yIGlzIG5vdCB0aGUgb25lIGN1cnJlbnRseSBhc3NpZ25lZCB0byBpLCBjaGFuZ2UgdGhlIGFzc2lnbm1lbnQgYW5kIHVwZGF0ZSB0aGUgb2JqZWN0aXZlIHZhbHVlIGFuZCBjaGFuZ2UgZmxhZy4KICAgICAgaWYgKGNob2ljZSAhPSBjdXJyZW50KSB7CiAgICAgICAgIyBSZW1vdmUgdGhlIG5vZGUgZnJvbSBpdHMgb2xkIGNvbG9yIGxpc3QuCiAgICAgICAgY29sb3JfbGlzdFtbY3VycmVudF1dIDwtIHNldGRpZmYoY29sb3JfbGlzdFtbY3VycmVudF1dLCBpKQogICAgICAgICMgQWRkIGl0IHRvIHRoZSBuZXcgY29sb3IgbGlzdC4KICAgICAgICBjb2xvcl9saXN0W1tjaG9pY2VdXSA8LSBjKGNvbG9yX2xpc3RbW2Nob2ljZV1dLCBpKQogICAgICAgICMgVXBkYXRlIHRoZSBjb2xvciB2ZWN0b3IuCiAgICAgICAgY29sb3JfdmVjdG9yW2ldIDwtIGNob2ljZQogICAgICAgICMgVXBkYXRlIHRoZSBvYmplY3RpdmUgdmFsdWUuCiAgICAgICAgb2JqZWN0aXZlIDwtIG9iamVjdGl2ZSAtIGNvc3RzW2N1cnJlbnRdICsgY29zdHNbY2hvaWNlXQogICAgICAgICMgVXBkYXRlIHRoZSBjaGFuZ2UgZmxhZy4KICAgICAgICBjaGFuZ2VkIDwtIFRSVUUKICAgICAgfQogICAgfQogIH0KICAjIFJldHVybiB0aGUgZmluYWwgc29sdXRpb24uCiAgbGlzdChjb2xvcnMgPSBjb2xvcl9saXN0LCB2YWx1ZSA9IG9iamVjdGl2ZSkKfQpgYGAKCiMjIFNvbHV0aW9uCgpXZSB3aWxsIHJlc2VlZCB0aGUgcmFuZG9tIG51bWJlciBnZW5lcmF0b3IgKGFnYWluIGZvciByZXByb2R1Y2liaWxpdHkpLCBydW4gdGhlIGhldXJpc3RpYyBhIGZpeGVkIG51bWJlciBvZiB0aW1lcywgYW5kIGtlZXAgdGhlIGJlc3Qgc29sdXRpb24uCgpgYGB7cn0KIyBTZXQgdGhlIG51bWJlciBvZiBydW5zLgpuX3J1bnMgPC0gNjAwCiMgUmVzZWVkIHRoZSByYW5kb20gbnVtYmVyIGdlbmVyYXRvci4Kc2V0LnNlZWQoMTIzNDUpCiMgU3RhcnQgdGltaW5nLgp0aWMoKQojIFJ1biB0aGUgaGV1cmlzdGljIG9uY2UgdG8gZ2V0IGFuIGluY3VtYmVudC4KaW5jdW1iZW50IDwtIGltcHJvdmVtZW50X2hldXJpc3RpYygpCiMgUnVuIHRoZSBoZXVyaXN0aWMgcmVwZWF0ZWRseSwga2VlcGluZyB0aGUgYmVzdCBzb2x1dGlvbi4KZm9yIChpIGluIDI6bl9ydW5zKSB7CiAgc29sIDwtIGltcHJvdmVtZW50X2hldXJpc3RpYygpCiAgaWYgKHNvbCR2YWx1ZSA8IGluY3VtYmVudCR2YWx1ZSkgewogICAgaW5jdW1iZW50IDwtIHNvbAogIH0KfQojIFN0b3AgdGltaW5nLgp0b2MoKQojIERpc3BsYXkgdGhlIGZpbmFsIGluY3VtYmVudC4KcHJpbnQoaW5jdW1iZW50KQpgYGAKCkluIHRoaXMgKGFuZCBhIGZldyBvdGhlciBydW5zIGF0dGVtcHRlZCkgdGhlIGhldXJpc3RpYywgd2l0aCByZXN0YXJ0cywgcHJvZHVjZXMgYSBzb21ld2hhdCBiZXR0ZXIgc29sdXRpb24gdGhhbiB0aGUgR0EgZG9lcy4K