Introduction

This is an attempt to solve a joint clustering problem (assigning users and servers to a specified number of groups or clusters) using a random key genetic algorithm. The original problem was cross-posted on Math Stack Exchange and OR Stack Exchange. The latter contains an answer reformulating it as a mixed integer linear program, but the OP expressed interest in a heuristic or metaheuristic solution, so I will try a GA.

Problem statement

There are \(U\) users and \(S\) servers (transmitters) to be assigned to a predetermined number \(G\) of groups. Any number of users may be assigned to a group, but a group may contain no more than \(M\) servers (and must contain at least one). We assume here that it is possible for a group to be assigned no users. Users are served by all servers in their group, but servers in other groups may interfere with them. For each combination of a user \(u\) and a server \(s\), there is a parameter \(h_{us}\). The overall quality of service for a user \(u\) in group \(g\) is given by \[q_{u} = \frac{\sum_{s\in G} h_{us}}{\sum_{s \notin G} h_{us}}.\]The objective is to maximize the total quality \[\sum_{u=1}^U q_u.\]

Preliminary observations

Data consistency

The OP specifies that \(U > S > G\). We must also assume that \(S < GM\). Finally, we will assume that \(h_{us}\) is strictly positive.

User assignment

Note that (a) there are no limits to the number of users in any group, (b) the quality of service to user \(u\) depends on which servers are/are not in the same group with user \(u\) but not on the assignments of any other users, and (c) the objective is additive (service qualities do not interact). So, given a feasible partition of the servers into \(G\) groups, we can simply measure \(q_u\) for each possible group assignment of \(u\) and assign \(u\) to the group giving it the highest quality value. Thus the problem reduces to grouping servers.

Group sizes

Suppose that we have partitioned the servers into \(G\) groups, with \(n_g\) the number of servers in group \(g\). We require that \(1 \le n_g \le M\). It follows that the allocation is feasible if and only if the following all hold: \[1 \le n_g \quad \forall g \quad (1)\] \[n_g \le M \quad \forall g \quad (2)\] \[S - (G-g)M \le \sum_{\gamma=1}^g n_\gamma \quad \forall g \quad (3)\] and \[\sum_{\gamma=1}^g n_\gamma \le S - G + g\quad \forall g \quad (4).\]Constraint (3) ensures that enough servers are allocated among the first \(g\) groups that the remaining groups, if assigned the maximum number each, can accommodate the remaining servers. Constraint (4) ensures that the first \(g\) groups leave enough unassigned servers that each remaining group can have at least one.

Let \(U_g=\sum_{\gamma=1}^g n_\gamma\) with \(U_{0}=0\). We can combine (1) and (3) into \[\max(1, S - (G-g)M - U_{g-1})\le n_g\quad \forall g \quad (1')\]and (2) and (4) into\[n_g \le \min(M, S - G + g - U_{g-1})\quad \forall g\quad (2').\]

GA conceptualization

We will use a random key genetic algorithm, which requires a method of decoding a chromosome into a feasible solution. Without loss of generality, we can assume that server 1 is assigned to the first group. (This mitigates a little bit of symmetry.) We will use a permutation-based GA, in which the objects being permuted are the servers \(2,\dots, S\) and \(G-1\) “dividers” (represented by NA in the code) that split the permuted server list into \(G\) groups. So, for example, suppose that \(S=7\), \(G=3\), \(M=3\) and our permuted list is \((2, |, 7, 4, 5, |, 3, 6)\). Server 1 is automatically prepended to the list and a last divider is appended. This assigns servers 1 and 2 to the first group, servers 4, 5 and 7 to the second group, and servers 3 and 6 to the third group.

There is no guarantee that the sorted list will meet the group size requirements, which is where the constraints (1’) and (2’) come in. We proceed through the sorted list, computing cumulative group sizes, and adjust dividers by the minimum amount necessary to satisfy (1’) and (2’). Continuing the previous example, suppose that the permutation is \((2, 7, 4, |, |, 5, 3, 6)\). After prepending 1 and tacking on a last divider, we have \((1, 2, 7, 4, |, |, 5, 3, 6, |)\). The first partial sum would be \(n_1 =4\), which violates constraint (2’), whose right-hand side is \(\min(3, 7-3+1-0)=3\). So we move the first divider between 7 and 4, the minimum change necessary, giving \((1, 2, 7, |, 4, |, 5, 3, 6, |)\). The partition is now feasible, with groups \(\lbrace 1, 2, 7\rbrace\), \(\lbrace 4 \rbrace\) and \(\lbrace 3, 5, 6\rbrace\).

Test problem

We start by loading the GA library (and the magrittr library for convenience).

library(GA)
Loading required package: foreach
Loading required package: iterators
  ____    _    
 / ___|  / \     Genetic 
| |  _  / _ \    Algorithms
| |_| |/ ___ \   
 \____/_/   \_\  version 3.2
Type 'citation("GA")' for citing this R package in publications.

Attaching package: ‘GA’

The following object is masked from ‘package:utils’:

    de
library(magrittr)

We set the dimensions of the test problem

U <- 100  # number of users
S <- 20  # number of servers
G <- 4   # number of groups (clusters)
M <- 7   # maximum number of servers per group

The quality values are generated uniformly over (0,1).

h <- runif(U * S) %>% matrix(nrow = U)

GA

Solution representation

We will represent a candidate solution with a list containing the following items:

  • obj the total objective value (scalar)

  • users a data frame of users containing two named columns

    • Group the index (\(1,\dots,G\)) of the group to which they are assigned
    • Quality the computed quality measure \(q_u\) for the user
  • groups a list of \(G\) vectors, each vector containing the indices of the servers in the corresponding group.

Chromosome representation

A chromosome will be an index vector for a permutation of \(S + G - 2\) objects: the \(S-1\) servers other than the first server (always assigned to the first group) and \(G-1\) NA values representing dividers between groups.

To facilitate working with permutations, we define an “alphabet” vector and a function that maps a permutation of \(\lbrace 2, 3, \dots, S + G - 1\rbrace\) into a sorted sequence of servers and dividers. The server sequence will always begin with server 1 and end with a divider (NA).

alphabet <- c(1:S, rep.int(NA, G))

Decoding a chromosome

The first step in getting from a chromosome to a solution is to convert the chromosome into a divided list with two elements. The first element (seq) is a sorted sequence of servers and dividers. The second element (div) is a vector giving the indices in the sequence of the dividers. The following function does that.

# Input: permutation vector (chromosome)
# Output: list containing the decoded sequence and the divider locations
as_sequence <- function(permutation) {
  sequence <- list()
  sequence$seq <- alphabet[c(1, permutation, S + G)]
  sequence$div <- sequence$seq %>% is.na() %>% which(arr.ind = TRUE)
  return(sequence)
}

Next, we need to make the proposed sequence feasible by adjusting the dividers as needed to meet the size restrictions on groups. In preparation for that, we will define a couple of helper functions that will move dividers.

When a group is too large, we need to move its terminating divider to an earlier position in the sequence. This is straightforward, since there is no chance the divider will pass a previous divider in the process. The following function takes as arguments a divided list, the index in the div element of the divider to move, and the number of positions to move it, and returns a modified copy of the list.

#Inputs:
#  `dlist`, a list with elements `seq` (sequence of servers and dividers) and `div` (indices of the dividers)
#  `ix` the index in `dlist$div` of the divider to move
#  `dist` the number of positions to the left to move the divider
#Output: the modified version of `dlist`
move_left <- function(dlist, ix, dist) {
  # Get the starting point of the divider to be moved.
  from <- dlist$div[ix]
  # Get the destination of the divider.
  to <- from - dist
  # Rearrange the subsequence of `seq`.
  dlist$seq[to:from] <- dlist$seq[c(from, to:(from - 1))]
  # Adjust the location of the divider that moved.
  dlist$div[ix] <- to
  return(dlist)
}

When a group is too small, its terminal divider needs to move to the right in the sequence. This is a bit trickier, since the moving divider could pass other dividers before it achieved the desired increase in group size. The following function takes the same arguments as move_left() but moves the divider far enough to the right that the current group gains the number of servers specified by the dist argument. Additional dividers encountered during the change are also moved.

#Inputs:
#  `dlist`, a list with elements `seq` (sequence of servers and dividers) and `div` (indices of the dividers)
#  `ix` the index in `dlist$div` of the divider to move
#  `dist` the number of servers the divider needs to pass
#Output: the modified version of `dlist`
move_right <- function(dlist, ix, dist) {
  # Get the starting point of the divider to be moved.
  from <- dlist$div[ix]
  # Compute the nominal final resting place of the moving divider.
  to <- from + dist
  q <- c()  # queue of dividers that need to be moved
  # Check subsequent dividers to see if they also need to move.
  for (j in (ix + 1):G) {
    if (dlist$div[j] > to) {
      break
    } else {
      # Adjust the move length and queue this divider to be moved.
      to <- to + 1
      q <- append(q, j)
    }
  }
  # Rotate the elements in the sequence to move the specified divider to its destination.
  dlist$seq[from:to] <- dlist$seq[c((from + 1):to, from)]
  dlist$div[ix] <- to
  # Update any other divider locations that changed.
  for (j in q) {
    dlist$div[j] <- dlist$div[j] - 1
  }
  # If there are other dividers queued to be moved, move each of them to the positions after the target divider.
  if (length(q) > 0) {
    iy <- max(q)  # index of the last divider being moved, if any
  }
  while (length(q) > 0) {
    # Pop the index of the next divider from the queue.
    j <- q[1]
    q <- q[-1]
    # Move this divider after the last moved divider.
    from <- dlist$div[j]
    dlist$seq[from:to] <- dlist$seq[c((from + 1):to, from)]
    dlist$div[j] <- to
    # Update affected divider locations (all the ones moving other than j).
    for (k in ix:iy) {
      if (k != j) {
        dlist$div[k] <- dlist$div[k] - 1
      }
    }
  }
  # Return the modified list.
  return(dlist)
}

Armed with these two functions, we can define a function that takes a divided list as input and modifies it to satisfy the group size limits.

# Input: a divided list with elements `seq` and `div` as above.
# Output: a modified version of the list satisfying group size requirements.
adjust <- function(dlist) {
  # Initialize variables.
  cusum <- 0       # cumulative sum of group sizes so far
                   # (U_{g-1} in (1') and (2'))
  last_div <- 0    # location of last divider encountered
                   # (marking the last position before the current
                   # group starts)
  # Process groups in order, adjusting the divider as needed.
  for (g in 1:(G - 1)) {
    # Update the lower and upper bounds.
    lo <- max(1, S - (G - g)*M - cusum)
    hi <- min(M, S - G + g - cusum)
    # Get the location of the next divider and the tentative group size.
    d <- dlist$div[g]
    n <- d - last_div - 1  # n_g in (1') and (2')
    # Adjust as needed.
    if (n < lo) {
      dlist <- move_right(dlist, g, lo - n)
      n <- lo
    } else if (n > hi) {
      dlist <- move_left(dlist, g, n - hi)
      n <- hi
    }
    # Update the cumulative sum and last divider location.
    cusum <- cusum + n
    last_div <- dlist$div[g]
  }
  # Return the modified list.
  return(dlist)
}

Next, we create a utility function that takes a divided sequence list and produces a list of \(G\) vectors, each containing the server list for one group.

# Input: a divided list with elements `seq` and `div` as above.
# Output: a list of G vectors containing the indices of servers in each group
server_lists <- function(dlist) {
  slist <- list()
  last_div <- 0
  for (g in 1:G) {
    next_div <- dlist$div[g]
    slist[[g]] <- sort(dlist$seq[(last_div + 1):(next_div -1)])
    last_div <- next_div
  }
  return(slist)
}

Given a list of server vectors as produced by server_lists, the next function evaluates the utility of assigning each user to each possible group and generates a dataframe containing the chosen group and utility value for each user. To reduce computation time, we first create a vector containing the sum \(\sum_{s=1}^S h_{us}\) of the utilities of assigning user \(u\) to each server \(s\).

total_utility <- apply(h, 1, sum)

We also create a utility function that takes as arguments a user and a vector of servers in a group and returns the quality measure \(q_u\) for assigning that user to that group.

# Inputs:
#  user = index of user
#  group = vector of servers in the group
# Output: quality value for assigning the user to that group
assignment_quality <- function(user, group) {
  numerator <- sum(h[user, group])
  denominator <- total_utility[user] - numerator
  return(numerator / denominator)
}

The next function makes the user assignments.

# Input: list of server vectors (as in the `groups` element of a solution list)
# Output: dataframe with chosen group and utility for each user (as in the `users` element of a solution list)
assign_users <- function(slist) {
  df <- data.frame(Group = rep.int(NA, U), Quality = rep.int(NA, U))
  for (u in 1:U) {
    # Evaluate all possible assignments of user u.
    qu <- sapply(slist, function(x) assignment_quality(u, x))
    # Find the index of the first group that maximizes quality.
    ix <- which.max(qu)
    # Record the assignment.
    df[u, "Group"] <- ix
    df[u, "Quality"] <- qu[ix]
  }
  return(df)
}

Now we define a function that converts a permutation vector list into a solution list with elements obj (total objective value), users (data frame of user assignments) and groups (list of server vectors).

# Input: a permutation vector (chromosome)
# Output: a solution list
decode <- function(permutation) {
  slist <- list()
  # Decode the permutation vector into a feasible collection of groups.
  slist$groups <-
    permutation %>% as_sequence() %>% adjust() %>% server_lists()
  # Compute the user assignments.
  slist$users <- slist$groups %>% assign_users()
  # The objective value is the sum of the user assignment qualities.
  slist$obj <- sum(slist$users$Quality)
  return(slist)
}

Fitness function

The fitness function takes a permutation, converts it to a feasible solution, and returns the objective value.

fitness <- function(chromosome) {
  sol <- chromosome %>% decode
  sol$obj
}

Solution report

We use the following function to report on a candidate solution.

# Input: a solution list with components `obj`, `users` and `groups`
solution_report <- function(solution) {
  cat("Solution with overall quality = ", solution$obj, ":\n")
  for (g in 1:G) {
    cat("\tServers in group ", g, ": ", solution$groups[[g]], "\n")
    u <- which(solution$users$Group == g, arr.ind = TRUE)
    if (length(u) == 0) {
      cat("\tUsers assigned to group ", g, ": NONE\n")
    } else {
      cat("\tUsers assigned to group ", g, " (", length(u), "): ", u, "\n")
    }
  }
}

Solution

We need to set some parameters for the genetic algorithm.

popSize <- 200        # population size
maxGens <- 200        # number of generations to run
stall <- 20           # stop if this many generations elapse without any improvement
multithread <- TRUE   # use parallel processes?
mutate <- 0.25        # use a relatively high mutation probability to discourage premature convergence

Now we run the GA. We use the “island evolution” variant to try to ward off premature convergence.

GA <- gaisl(type = "permutation",
            fitness = fitness,
            lower = 2,           # permutation indices start at 2
            upper = S + G - 1,   # permutation indices end at S+G-1
            popSize = popSize,
            maxiter = maxGens,
            run = stall,
            parallel = multithread,
            pmutation = mutate
)
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 1 
Mean = 65.45251 | Best = 70.35057 
Mean = 65.45251 | Best = 70.35057 
Mean = 65.45251 | Best = 70.35057 
Mean = 65.45251 | Best = 70.35057 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 2 
Mean = 64.18192 | Best = 70.90503 
Mean = 65.18431 | Best = 70.35057 
Mean = 65.67132 | Best = 70.35057 
Mean = 65.55964 | Best = 70.90721 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 3 
Mean = 65.70566 | Best = 71.08163 
Mean = 65.63610 | Best = 72.57250 
Mean = 66.01068 | Best = 70.35057 
Mean = 65.20788 | Best = 70.90721 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 4 
Mean = 65.94918 | Best = 71.75459 
Mean = 64.33893 | Best = 72.57250 
Mean = 66.12253 | Best = 72.57250 
Mean = 65.37149 | Best = 70.90721 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 5 
Mean = 66.18817 | Best = 71.75459 
Mean = 65.17979 | Best = 72.75234 
Mean = 65.62997 | Best = 73.55963 
Mean = 65.77710 | Best = 72.75234 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 6 
Mean = 64.85094 | Best = 72.75234 
Mean = 64.02787 | Best = 72.75234 
Mean = 65.64232 | Best = 73.55963 
Mean = 64.26401 | Best = 73.55963 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 7 
Mean = 65.60882 | Best = 73.55963 
Mean = 65.84829 | Best = 72.75234 
Mean = 65.57098 | Best = 73.55963 
Mean = 66.34094 | Best = 73.55963 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 8 
Mean = 66.21717 | Best = 73.55963 
Mean = 64.78888 | Best = 73.55963 
Mean = 64.63630 | Best = 73.55963 
Mean = 64.71138 | Best = 73.55963 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 9 
Mean = 64.46584 | Best = 73.55963 
Mean = 65.11027 | Best = 73.55963 
Mean = 65.65946 | Best = 73.55963 
Mean = 65.86944 | Best = 73.55963 
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
loaded GA and set parent environment
Islands GA | epoch = 10 
Mean = 64.17191 | Best = 73.55963 
Mean = 65.25347 | Best = 73.55963 
Mean = 65.25288 | Best = 73.55963 
Mean = 64.85213 | Best = 73.55963 
plot(GA)

Last, we recover the best solution found by the GA.

GA@solution[1,] %>% decode() %>% solution_report()
Solution with overall quality =  73.55963 :
    Servers in group  1 :  1 3 14 15 16 19 20 
    Users assigned to group  1  ( 48 ):  1 2 3 4 5 8 11 13 14 23 28 29 31 32 36 37 38 43 45 47 50 52 53 58 59 60 62 63 65 66 67 70 73 76 77 78 81 83 85 86 87 88 89 91 93 96 97 99 
    Servers in group  2 :  2 4 5 6 7 9 10 
    Users assigned to group  2  ( 50 ):  6 7 9 10 12 15 16 17 18 19 20 21 22 24 25 26 27 30 33 34 35 39 40 41 42 44 46 48 49 51 54 55 56 57 64 68 69 71 72 74 75 79 82 84 90 92 94 95 98 100 
    Servers in group  3 :  8 11 12 17 18 
    Users assigned to group  3  ( 2 ):  61 80 
    Servers in group  4 :  13 
    Users assigned to group  4 : NONE
LS0tCnRpdGxlOiAiSm9pbnQgQ2x1c3RlcmluZyIKb3V0cHV0OiBodG1sX25vdGVib29rCmF1dGhvcjogUGF1bCBBLiBSdWJpbiAocnViaW5AbXN1LmVkdSkKZGF0ZTogQXByaWwgOCwgMjAyMQotLS0KCiMgSW50cm9kdWN0aW9uCgpUaGlzIGlzIGFuIGF0dGVtcHQgdG8gc29sdmUgYSBqb2ludCBjbHVzdGVyaW5nIHByb2JsZW0gKGFzc2lnbmluZyB1c2VycyBhbmQgc2VydmVycyB0byBhIHNwZWNpZmllZCBudW1iZXIgb2YgZ3JvdXBzIG9yIGNsdXN0ZXJzKSB1c2luZyBhIHJhbmRvbSBrZXkgZ2VuZXRpYyBhbGdvcml0aG0uIFRoZSBvcmlnaW5hbCBwcm9ibGVtIHdhcyBjcm9zcy1wb3N0ZWQgb24gW01hdGggU3RhY2sgRXhjaGFuZ2VdKGh0dHBzOi8vbWF0aC5zdGFja2V4Y2hhbmdlLmNvbS9xdWVzdGlvbnMvNDA4ODQ0MS93aGF0LXdpbGwtYmUtYW4tZWZmaWNpZW50LWpvaW50LWNsdXN0ZXJpbmctc29sdXRpb24tdG8tdGhpcy1wcm9ibGVtKSBhbmQgW09SIFN0YWNrIEV4Y2hhbmdlXShodHRwczovL29yLnN0YWNrZXhjaGFuZ2UuY29tL3F1ZXN0aW9ucy82MDIzL2hvdy10by1tYXRoZW1hdGljYWxseS1mb3JtdWxhdGUtdGhlLW9wdGltaXphdGlvbi1wcm9ibGVtKS4gVGhlIGxhdHRlciBjb250YWlucyBhbiBhbnN3ZXIgcmVmb3JtdWxhdGluZyBpdCBhcyBhIG1peGVkIGludGVnZXIgbGluZWFyIHByb2dyYW0sIGJ1dCB0aGUgT1AgZXhwcmVzc2VkIGludGVyZXN0IGluIGEgaGV1cmlzdGljIG9yIG1ldGFoZXVyaXN0aWMgc29sdXRpb24sIHNvIEkgd2lsbCB0cnkgYSBHQS4KCiMgUHJvYmxlbSBzdGF0ZW1lbnQKClRoZXJlIGFyZSAkVSQgdXNlcnMgYW5kICRTJCBzZXJ2ZXJzICh0cmFuc21pdHRlcnMpIHRvIGJlIGFzc2lnbmVkIHRvIGEgcHJlZGV0ZXJtaW5lZCBudW1iZXIgJEckIG9mIGdyb3Vwcy4gQW55IG51bWJlciBvZiB1c2VycyBtYXkgYmUgYXNzaWduZWQgdG8gYSBncm91cCwgYnV0IGEgZ3JvdXAgbWF5IGNvbnRhaW4gbm8gbW9yZSB0aGFuICRNJCBzZXJ2ZXJzIChhbmQgbXVzdCBjb250YWluIGF0IGxlYXN0IG9uZSkuIFdlIGFzc3VtZSBoZXJlIHRoYXQgaXQgaXMgcG9zc2libGUgZm9yIGEgZ3JvdXAgdG8gYmUgYXNzaWduZWQgbm8gdXNlcnMuIFVzZXJzIGFyZSBzZXJ2ZWQgYnkgYWxsIHNlcnZlcnMgaW4gdGhlaXIgZ3JvdXAsIGJ1dCBzZXJ2ZXJzIGluIG90aGVyIGdyb3VwcyBtYXkgaW50ZXJmZXJlIHdpdGggdGhlbS4gRm9yIGVhY2ggY29tYmluYXRpb24gb2YgYSB1c2VyICR1JCBhbmQgYSBzZXJ2ZXIgJHMkLCB0aGVyZSBpcyBhIHBhcmFtZXRlciAkaF97dXN9JC4gVGhlIG92ZXJhbGwgcXVhbGl0eSBvZiBzZXJ2aWNlIGZvciBhIHVzZXIgJHUkIGluIGdyb3VwICRnJCBpcyBnaXZlbiBieSAkJHFfe3V9ID0gXGZyYWN7XHN1bV97c1xpbiBHfSBoX3t1c319e1xzdW1fe3MgXG5vdGluIEd9Cmhfe3VzfX0uJCRUaGUgb2JqZWN0aXZlIGlzIHRvIG1heGltaXplIHRoZSB0b3RhbCBxdWFsaXR5ICQkXHN1bV97dT0xfV5VIHFfdS4kJAoKIyBQcmVsaW1pbmFyeSBvYnNlcnZhdGlvbnMKCiMjIERhdGEgY29uc2lzdGVuY3kKClRoZSBPUCBzcGVjaWZpZXMgdGhhdCAkVSA+IFMgPiBHJC4gV2UgbXVzdCBhbHNvIGFzc3VtZSB0aGF0ICRTIDwgR00kLiBGaW5hbGx5LCB3ZSB3aWxsIGFzc3VtZSB0aGF0ICRoX3t1c30kIGlzIHN0cmljdGx5IHBvc2l0aXZlLgoKIyMgVXNlciBhc3NpZ25tZW50CgpOb3RlIHRoYXQgKGEpIHRoZXJlIGFyZSBubyBsaW1pdHMgdG8gdGhlIG51bWJlciBvZiB1c2VycyBpbiBhbnkgZ3JvdXAsIChiKSB0aGUgcXVhbGl0eSBvZiBzZXJ2aWNlIHRvIHVzZXIgJHUkIGRlcGVuZHMgb24gd2hpY2ggc2VydmVycyBhcmUvYXJlIG5vdCBpbiB0aGUgc2FtZSBncm91cCB3aXRoIHVzZXIgJHUkIGJ1dCAqbm90IG9uIHRoZSBhc3NpZ25tZW50cyBvZiBhbnkgb3RoZXIgdXNlcnMqLCBhbmQgKGMpIHRoZSBvYmplY3RpdmUgaXMgYWRkaXRpdmUgKHNlcnZpY2UgcXVhbGl0aWVzIGRvIG5vdCBpbnRlcmFjdCkuIFNvLCBnaXZlbiBhIGZlYXNpYmxlIHBhcnRpdGlvbiBvZiB0aGUgc2VydmVycyBpbnRvICRHJCBncm91cHMsIHdlIGNhbiBzaW1wbHkgbWVhc3VyZSAkcV91JCBmb3IgZWFjaCBwb3NzaWJsZSBncm91cCBhc3NpZ25tZW50IG9mICR1JCBhbmQgYXNzaWduICR1JCB0byB0aGUgZ3JvdXAgZ2l2aW5nIGl0IHRoZSBoaWdoZXN0IHF1YWxpdHkgdmFsdWUuIFRodXMgdGhlIHByb2JsZW0gcmVkdWNlcyB0byBncm91cGluZyBzZXJ2ZXJzLgoKIyMgR3JvdXAgc2l6ZXMKClN1cHBvc2UgdGhhdCB3ZSBoYXZlIHBhcnRpdGlvbmVkIHRoZSBzZXJ2ZXJzIGludG8gJEckIGdyb3Vwcywgd2l0aCAkbl9nJCB0aGUgbnVtYmVyIG9mIHNlcnZlcnMgaW4gZ3JvdXAgJGckLiBXZSByZXF1aXJlIHRoYXQgJDEgXGxlIG5fZyBcbGUgTSQuIEl0IGZvbGxvd3MgdGhhdCB0aGUgYWxsb2NhdGlvbiBpcyBmZWFzaWJsZSBpZiBhbmQgb25seSBpZiB0aGUgZm9sbG93aW5nIGFsbCBob2xkOiAkJDEgXGxlIG5fZyBccXVhZCBcZm9yYWxsIGcgXHF1YWQgKDEpJCQgJCRuX2cgXGxlIE0gXHF1YWQgXGZvcmFsbCBnIFxxdWFkICgyKSQkICQkUyAtIChHLWcpTSBcbGUgXHN1bV97XGdhbW1hPTF9Xmcgbl9cZ2FtbWEgXHF1YWQgXGZvcmFsbCBnIFxxdWFkICgzKSQkIGFuZCAkJFxzdW1fe1xnYW1tYT0xfV5nIG5fXGdhbW1hIFxsZSBTIC0gRyArIGdccXVhZCBcZm9yYWxsIGcgXHF1YWQgKDQpLiQkQ29uc3RyYWludCAoMykgZW5zdXJlcyB0aGF0IGVub3VnaCBzZXJ2ZXJzIGFyZSBhbGxvY2F0ZWQgYW1vbmcgdGhlIGZpcnN0ICRnJCBncm91cHMgdGhhdCB0aGUgcmVtYWluaW5nIGdyb3VwcywgaWYgYXNzaWduZWQgdGhlIG1heGltdW0gbnVtYmVyIGVhY2gsIGNhbiBhY2NvbW1vZGF0ZSB0aGUgcmVtYWluaW5nIHNlcnZlcnMuIENvbnN0cmFpbnQgKDQpIGVuc3VyZXMgdGhhdCB0aGUgZmlyc3QgJGckIGdyb3VwcyBsZWF2ZSBlbm91Z2ggdW5hc3NpZ25lZCBzZXJ2ZXJzIHRoYXQgZWFjaCByZW1haW5pbmcgZ3JvdXAgY2FuIGhhdmUgYXQgbGVhc3Qgb25lLgoKTGV0ICRVX2c9XHN1bV97XGdhbW1hPTF9Xmcgbl9cZ2FtbWEkIHdpdGggJFVfezB9PTAkLiBXZSBjYW4gY29tYmluZSAoMSkgYW5kICgzKSBpbnRvICQkXG1heCgxLCBTIC0gKEctZylNIC0gVV97Zy0xfSlcbGUgbl9nXHF1YWQgXGZvcmFsbCBnIFxxdWFkICgxJykkJGFuZCAoMikgYW5kICg0KSBpbnRvJCRuX2cgXGxlIFxtaW4oTSwgUyAtIEcgKyBnIC0gVV97Zy0xfSlccXVhZCBcZm9yYWxsIGdccXVhZCAoMicpLiQkCgojIEdBIGNvbmNlcHR1YWxpemF0aW9uCgpXZSB3aWxsIHVzZSBhIHJhbmRvbSBrZXkgZ2VuZXRpYyBhbGdvcml0aG0sIHdoaWNoIHJlcXVpcmVzIGEgbWV0aG9kIG9mIGRlY29kaW5nIGEgY2hyb21vc29tZSBpbnRvIGEgZmVhc2libGUgc29sdXRpb24uIFdpdGhvdXQgbG9zcyBvZiBnZW5lcmFsaXR5LCB3ZSBjYW4gYXNzdW1lIHRoYXQgc2VydmVyIDEgaXMgYXNzaWduZWQgdG8gdGhlIGZpcnN0IGdyb3VwLiAoVGhpcyBtaXRpZ2F0ZXMgYSBsaXR0bGUgYml0IG9mIHN5bW1ldHJ5LikgV2Ugd2lsbCB1c2UgYSBwZXJtdXRhdGlvbi1iYXNlZCBHQSwgaW4gd2hpY2ggdGhlIG9iamVjdHMgYmVpbmcgcGVybXV0ZWQgYXJlIHRoZSBzZXJ2ZXJzICQyLFxkb3RzLCBTJCBhbmQgJEctMSQgImRpdmlkZXJzIiAocmVwcmVzZW50ZWQgYnkgYE5BYCBpbiB0aGUgY29kZSkgdGhhdCBzcGxpdCB0aGUgcGVybXV0ZWQgc2VydmVyIGxpc3QgaW50byAkRyQgZ3JvdXBzLiBTbywgZm9yIGV4YW1wbGUsIHN1cHBvc2UgdGhhdCAkUz03JCwgJEc9MyQsICRNPTMkIGFuZCBvdXIgcGVybXV0ZWQgbGlzdCBpcyAkKDIsIHwsIDcsIDQsIDUsIHwsIDMsIDYpJC4gU2VydmVyIDEgaXMgYXV0b21hdGljYWxseSBwcmVwZW5kZWQgdG8gdGhlIGxpc3QgYW5kIGEgbGFzdCBkaXZpZGVyIGlzIGFwcGVuZGVkLiBUaGlzIGFzc2lnbnMgc2VydmVycyAxIGFuZCAyIHRvIHRoZSBmaXJzdCBncm91cCwgc2VydmVycyA0LCA1IGFuZCA3IHRvIHRoZSBzZWNvbmQgZ3JvdXAsIGFuZCBzZXJ2ZXJzIDMgYW5kIDYgdG8gdGhlIHRoaXJkIGdyb3VwLgoKVGhlcmUgaXMgbm8gZ3VhcmFudGVlIHRoYXQgdGhlIHNvcnRlZCBsaXN0IHdpbGwgbWVldCB0aGUgZ3JvdXAgc2l6ZSByZXF1aXJlbWVudHMsIHdoaWNoIGlzIHdoZXJlIHRoZSBjb25zdHJhaW50cyAoMScpIGFuZCAoMicpIGNvbWUgaW4uIFdlIHByb2NlZWQgdGhyb3VnaCB0aGUgc29ydGVkIGxpc3QsIGNvbXB1dGluZyBjdW11bGF0aXZlIGdyb3VwIHNpemVzLCBhbmQgYWRqdXN0IGRpdmlkZXJzIGJ5IHRoZSBtaW5pbXVtIGFtb3VudCBuZWNlc3NhcnkgdG8gc2F0aXNmeSAoMScpIGFuZCAoMicpLiBDb250aW51aW5nIHRoZSBwcmV2aW91cyBleGFtcGxlLCBzdXBwb3NlIHRoYXQgdGhlIHBlcm11dGF0aW9uIGlzICQoMiwgNywgNCwgfCwgfCwgNSwgMywgNikkLiBBZnRlciBwcmVwZW5kaW5nIDEgYW5kIHRhY2tpbmcgb24gYSBsYXN0IGRpdmlkZXIsIHdlIGhhdmUgJCgxLCAyLCA3LCA0LCB8LCB8LCA1LCAzLCA2LCB8KSQuIFRoZSBmaXJzdCBwYXJ0aWFsIHN1bSB3b3VsZCBiZSAkbl8xID00JCwgd2hpY2ggdmlvbGF0ZXMgY29uc3RyYWludCAoMicpLCB3aG9zZSByaWdodC1oYW5kIHNpZGUgaXMgJFxtaW4oMywgNy0zKzEtMCk9MyQuIFNvIHdlIG1vdmUgdGhlIGZpcnN0IGRpdmlkZXIgYmV0d2VlbiA3IGFuZCA0LCB0aGUgbWluaW11bSBjaGFuZ2UgbmVjZXNzYXJ5LCBnaXZpbmcgJCgxLCAyLCA3LCB8LCA0LCB8LCA1LCAzLCA2LCB8KSQuIFRoZSBwYXJ0aXRpb24gaXMgbm93IGZlYXNpYmxlLCB3aXRoIGdyb3VwcyAkXGxicmFjZSAxLCAyLCA3XHJicmFjZSQsICRcbGJyYWNlIDQgXHJicmFjZSQgYW5kICRcbGJyYWNlIDMsIDUsIDZccmJyYWNlJC4KCiMgVGVzdCBwcm9ibGVtCgpXZSBzdGFydCBieSBsb2FkaW5nIHRoZSBHQSBsaWJyYXJ5IChhbmQgdGhlIG1hZ3JpdHRyIGxpYnJhcnkgZm9yIGNvbnZlbmllbmNlKS4KCmBgYHtyfQpsaWJyYXJ5KEdBKQpsaWJyYXJ5KG1hZ3JpdHRyKQpgYGAKCldlIHNldCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgdGVzdCBwcm9ibGVtCgpgYGB7cn0KVSA8LSAxMDAgICMgbnVtYmVyIG9mIHVzZXJzClMgPC0gMjAgICMgbnVtYmVyIG9mIHNlcnZlcnMKRyA8LSA0ICAgIyBudW1iZXIgb2YgZ3JvdXBzIChjbHVzdGVycykKTSA8LSA3ICAgIyBtYXhpbXVtIG51bWJlciBvZiBzZXJ2ZXJzIHBlciBncm91cApgYGAKClRoZSBxdWFsaXR5IHZhbHVlcyBhcmUgZ2VuZXJhdGVkIHVuaWZvcm1seSBvdmVyICgwLDEpLgoKYGBge3J9CmggPC0gcnVuaWYoVSAqIFMpICU+JSBtYXRyaXgobnJvdyA9IFUpCmBgYAoKIyBHQQoKIyMgU29sdXRpb24gcmVwcmVzZW50YXRpb24KCldlIHdpbGwgcmVwcmVzZW50IGEgY2FuZGlkYXRlIHNvbHV0aW9uIHdpdGggYSBsaXN0IGNvbnRhaW5pbmcgdGhlIGZvbGxvd2luZyBpdGVtczoKCi0gICBgb2JqYCB0aGUgdG90YWwgb2JqZWN0aXZlIHZhbHVlIChzY2FsYXIpCgotICAgYHVzZXJzYCBhIGRhdGEgZnJhbWUgb2YgdXNlcnMgY29udGFpbmluZyB0d28gbmFtZWQgY29sdW1ucwoKICAgIC0gICBgR3JvdXBgIHRoZSBpbmRleCAoJDEsXGRvdHMsRyQpIG9mIHRoZSBncm91cCB0byB3aGljaCB0aGV5IGFyZSBhc3NpZ25lZAogICAgLSAgIGBRdWFsaXR5YCB0aGUgY29tcHV0ZWQgcXVhbGl0eSBtZWFzdXJlICRxX3UkIGZvciB0aGUgdXNlcgoKLSAgIGBncm91cHNgIGEgbGlzdCBvZiAkRyQgdmVjdG9ycywgZWFjaCB2ZWN0b3IgY29udGFpbmluZyB0aGUgaW5kaWNlcyBvZiB0aGUgc2VydmVycyBpbiB0aGUgY29ycmVzcG9uZGluZyBncm91cC4KCiMjIENocm9tb3NvbWUgcmVwcmVzZW50YXRpb24KCkEgY2hyb21vc29tZSB3aWxsIGJlIGFuIGluZGV4IHZlY3RvciBmb3IgYSBwZXJtdXRhdGlvbiBvZiAkUyArIEcgLSAyJCBvYmplY3RzOiB0aGUgJFMtMSQgc2VydmVycyBvdGhlciB0aGFuIHRoZSBmaXJzdCBzZXJ2ZXIgKGFsd2F5cyBhc3NpZ25lZCB0byB0aGUgZmlyc3QgZ3JvdXApIGFuZCAkRy0xJCBOQSB2YWx1ZXMgcmVwcmVzZW50aW5nIGRpdmlkZXJzIGJldHdlZW4gZ3JvdXBzLgoKVG8gZmFjaWxpdGF0ZSB3b3JraW5nIHdpdGggcGVybXV0YXRpb25zLCB3ZSBkZWZpbmUgYW4gImFscGhhYmV0IiB2ZWN0b3IgYW5kIGEgZnVuY3Rpb24gdGhhdCBtYXBzIGEgcGVybXV0YXRpb24gb2YgJFxsYnJhY2UgMiwgMywgXGRvdHMsIFMgKyBHIC0gMVxyYnJhY2UkIGludG8gYSBzb3J0ZWQgc2VxdWVuY2Ugb2Ygc2VydmVycyBhbmQgZGl2aWRlcnMuIFRoZSBzZXJ2ZXIgc2VxdWVuY2Ugd2lsbCBhbHdheXMgYmVnaW4gd2l0aCBzZXJ2ZXIgMSBhbmQgZW5kIHdpdGggYSBkaXZpZGVyIChOQSkuCgpgYGB7cn0KYWxwaGFiZXQgPC0gYygxOlMsIHJlcC5pbnQoTkEsIEcpKQpgYGAKCiMjIERlY29kaW5nIGEgY2hyb21vc29tZQoKVGhlIGZpcnN0IHN0ZXAgaW4gZ2V0dGluZyBmcm9tIGEgY2hyb21vc29tZSB0byBhIHNvbHV0aW9uIGlzIHRvIGNvbnZlcnQgdGhlIGNocm9tb3NvbWUgaW50byBhIGRpdmlkZWQgbGlzdCB3aXRoIHR3byBlbGVtZW50cy4gVGhlIGZpcnN0IGVsZW1lbnQgKGBzZXFgKSBpcyBhIHNvcnRlZCBzZXF1ZW5jZSBvZiBzZXJ2ZXJzIGFuZCBkaXZpZGVycy4gVGhlIHNlY29uZCBlbGVtZW50IChgZGl2YCkgaXMgYSB2ZWN0b3IgZ2l2aW5nIHRoZSBpbmRpY2VzIGluIHRoZSBzZXF1ZW5jZSBvZiB0aGUgZGl2aWRlcnMuIFRoZSBmb2xsb3dpbmcgZnVuY3Rpb24gZG9lcyB0aGF0LgoKYGBge3J9CiMgSW5wdXQ6IHBlcm11dGF0aW9uIHZlY3RvciAoY2hyb21vc29tZSkKIyBPdXRwdXQ6IGxpc3QgY29udGFpbmluZyB0aGUgZGVjb2RlZCBzZXF1ZW5jZSBhbmQgdGhlIGRpdmlkZXIgbG9jYXRpb25zCmFzX3NlcXVlbmNlIDwtIGZ1bmN0aW9uKHBlcm11dGF0aW9uKSB7CiAgc2VxdWVuY2UgPC0gbGlzdCgpCiAgc2VxdWVuY2Ukc2VxIDwtIGFscGhhYmV0W2MoMSwgcGVybXV0YXRpb24sIFMgKyBHKV0KICBzZXF1ZW5jZSRkaXYgPC0gc2VxdWVuY2Ukc2VxICU+JSBpcy5uYSgpICU+JSB3aGljaChhcnIuaW5kID0gVFJVRSkKICByZXR1cm4oc2VxdWVuY2UpCn0KYGBgCgpOZXh0LCB3ZSBuZWVkIHRvIG1ha2UgdGhlIHByb3Bvc2VkIHNlcXVlbmNlIGZlYXNpYmxlIGJ5IGFkanVzdGluZyB0aGUgZGl2aWRlcnMgYXMgbmVlZGVkIHRvIG1lZXQgdGhlIHNpemUgcmVzdHJpY3Rpb25zIG9uIGdyb3Vwcy4gSW4gcHJlcGFyYXRpb24gZm9yIHRoYXQsIHdlIHdpbGwgZGVmaW5lIGEgY291cGxlIG9mIGhlbHBlciBmdW5jdGlvbnMgdGhhdCB3aWxsIG1vdmUgZGl2aWRlcnMuCgpXaGVuIGEgZ3JvdXAgaXMgdG9vIGxhcmdlLCB3ZSBuZWVkIHRvIG1vdmUgaXRzIHRlcm1pbmF0aW5nIGRpdmlkZXIgdG8gYW4gZWFybGllciBwb3NpdGlvbiBpbiB0aGUgc2VxdWVuY2UuIFRoaXMgaXMgc3RyYWlnaHRmb3J3YXJkLCBzaW5jZSB0aGVyZSBpcyBubyBjaGFuY2UgdGhlIGRpdmlkZXIgd2lsbCBwYXNzIGEgcHJldmlvdXMgZGl2aWRlciBpbiB0aGUgcHJvY2Vzcy4gVGhlIGZvbGxvd2luZyBmdW5jdGlvbiB0YWtlcyBhcyBhcmd1bWVudHMgYSBkaXZpZGVkIGxpc3QsIHRoZSBpbmRleCBpbiB0aGUgYGRpdmAgZWxlbWVudCBvZiB0aGUgZGl2aWRlciB0byBtb3ZlLCBhbmQgdGhlIG51bWJlciBvZiBwb3NpdGlvbnMgdG8gbW92ZSBpdCwgYW5kIHJldHVybnMgYSBtb2RpZmllZCBjb3B5IG9mIHRoZSBsaXN0LgoKYGBge3J9CiNJbnB1dHM6CiMgIGBkbGlzdGAsIGEgbGlzdCB3aXRoIGVsZW1lbnRzIGBzZXFgIChzZXF1ZW5jZSBvZiBzZXJ2ZXJzIGFuZCBkaXZpZGVycykgYW5kIGBkaXZgIChpbmRpY2VzIG9mIHRoZSBkaXZpZGVycykKIyAgYGl4YCB0aGUgaW5kZXggaW4gYGRsaXN0JGRpdmAgb2YgdGhlIGRpdmlkZXIgdG8gbW92ZQojICBgZGlzdGAgdGhlIG51bWJlciBvZiBwb3NpdGlvbnMgdG8gdGhlIGxlZnQgdG8gbW92ZSB0aGUgZGl2aWRlcgojT3V0cHV0OiB0aGUgbW9kaWZpZWQgdmVyc2lvbiBvZiBgZGxpc3RgCm1vdmVfbGVmdCA8LSBmdW5jdGlvbihkbGlzdCwgaXgsIGRpc3QpIHsKICAjIEdldCB0aGUgc3RhcnRpbmcgcG9pbnQgb2YgdGhlIGRpdmlkZXIgdG8gYmUgbW92ZWQuCiAgZnJvbSA8LSBkbGlzdCRkaXZbaXhdCiAgIyBHZXQgdGhlIGRlc3RpbmF0aW9uIG9mIHRoZSBkaXZpZGVyLgogIHRvIDwtIGZyb20gLSBkaXN0CiAgIyBSZWFycmFuZ2UgdGhlIHN1YnNlcXVlbmNlIG9mIGBzZXFgLgogIGRsaXN0JHNlcVt0bzpmcm9tXSA8LSBkbGlzdCRzZXFbYyhmcm9tLCB0bzooZnJvbSAtIDEpKV0KICAjIEFkanVzdCB0aGUgbG9jYXRpb24gb2YgdGhlIGRpdmlkZXIgdGhhdCBtb3ZlZC4KICBkbGlzdCRkaXZbaXhdIDwtIHRvCiAgcmV0dXJuKGRsaXN0KQp9CgpgYGAKCldoZW4gYSBncm91cCBpcyB0b28gc21hbGwsIGl0cyB0ZXJtaW5hbCBkaXZpZGVyIG5lZWRzIHRvIG1vdmUgdG8gdGhlIHJpZ2h0IGluIHRoZSBzZXF1ZW5jZS4gVGhpcyBpcyBhIGJpdCB0cmlja2llciwgc2luY2UgdGhlIG1vdmluZyBkaXZpZGVyIGNvdWxkIHBhc3Mgb3RoZXIgZGl2aWRlcnMgYmVmb3JlIGl0IGFjaGlldmVkIHRoZSBkZXNpcmVkIGluY3JlYXNlIGluIGdyb3VwIHNpemUuIFRoZSBmb2xsb3dpbmcgZnVuY3Rpb24gdGFrZXMgdGhlIHNhbWUgYXJndW1lbnRzIGFzIGBtb3ZlX2xlZnQoKWAgYnV0IG1vdmVzIHRoZSBkaXZpZGVyIGZhciBlbm91Z2ggdG8gdGhlIHJpZ2h0IHRoYXQgdGhlIGN1cnJlbnQgZ3JvdXAgZ2FpbnMgdGhlIG51bWJlciBvZiBzZXJ2ZXJzIHNwZWNpZmllZCBieSB0aGUgYGRpc3RgIGFyZ3VtZW50LiBBZGRpdGlvbmFsIGRpdmlkZXJzIGVuY291bnRlcmVkIGR1cmluZyB0aGUgY2hhbmdlIGFyZSBhbHNvIG1vdmVkLgoKYGBge3J9CiNJbnB1dHM6CiMgIGBkbGlzdGAsIGEgbGlzdCB3aXRoIGVsZW1lbnRzIGBzZXFgIChzZXF1ZW5jZSBvZiBzZXJ2ZXJzIGFuZCBkaXZpZGVycykgYW5kIGBkaXZgIChpbmRpY2VzIG9mIHRoZSBkaXZpZGVycykKIyAgYGl4YCB0aGUgaW5kZXggaW4gYGRsaXN0JGRpdmAgb2YgdGhlIGRpdmlkZXIgdG8gbW92ZQojICBgZGlzdGAgdGhlIG51bWJlciBvZiBzZXJ2ZXJzIHRoZSBkaXZpZGVyIG5lZWRzIHRvIHBhc3MKI091dHB1dDogdGhlIG1vZGlmaWVkIHZlcnNpb24gb2YgYGRsaXN0YAptb3ZlX3JpZ2h0IDwtIGZ1bmN0aW9uKGRsaXN0LCBpeCwgZGlzdCkgewogICMgR2V0IHRoZSBzdGFydGluZyBwb2ludCBvZiB0aGUgZGl2aWRlciB0byBiZSBtb3ZlZC4KICBmcm9tIDwtIGRsaXN0JGRpdltpeF0KICAjIENvbXB1dGUgdGhlIG5vbWluYWwgZmluYWwgcmVzdGluZyBwbGFjZSBvZiB0aGUgbW92aW5nIGRpdmlkZXIuCiAgdG8gPC0gZnJvbSArIGRpc3QKICBxIDwtIGMoKSAgIyBxdWV1ZSBvZiBkaXZpZGVycyB0aGF0IG5lZWQgdG8gYmUgbW92ZWQKICAjIENoZWNrIHN1YnNlcXVlbnQgZGl2aWRlcnMgdG8gc2VlIGlmIHRoZXkgYWxzbyBuZWVkIHRvIG1vdmUuCiAgZm9yIChqIGluIChpeCArIDEpOkcpIHsKICAgIGlmIChkbGlzdCRkaXZbal0gPiB0bykgewogICAgICBicmVhawogICAgfSBlbHNlIHsKICAgICAgIyBBZGp1c3QgdGhlIG1vdmUgbGVuZ3RoIGFuZCBxdWV1ZSB0aGlzIGRpdmlkZXIgdG8gYmUgbW92ZWQuCiAgICAgIHRvIDwtIHRvICsgMQogICAgICBxIDwtIGFwcGVuZChxLCBqKQogICAgfQogIH0KICAjIFJvdGF0ZSB0aGUgZWxlbWVudHMgaW4gdGhlIHNlcXVlbmNlIHRvIG1vdmUgdGhlIHNwZWNpZmllZCBkaXZpZGVyIHRvIGl0cyBkZXN0aW5hdGlvbi4KICBkbGlzdCRzZXFbZnJvbTp0b10gPC0gZGxpc3Qkc2VxW2MoKGZyb20gKyAxKTp0bywgZnJvbSldCiAgZGxpc3QkZGl2W2l4XSA8LSB0bwogICMgVXBkYXRlIGFueSBvdGhlciBkaXZpZGVyIGxvY2F0aW9ucyB0aGF0IGNoYW5nZWQuCiAgZm9yIChqIGluIHEpIHsKICAgIGRsaXN0JGRpdltqXSA8LSBkbGlzdCRkaXZbal0gLSAxCiAgfQogICMgSWYgdGhlcmUgYXJlIG90aGVyIGRpdmlkZXJzIHF1ZXVlZCB0byBiZSBtb3ZlZCwgbW92ZSBlYWNoIG9mIHRoZW0gdG8gdGhlIHBvc2l0aW9ucyBhZnRlciB0aGUgdGFyZ2V0IGRpdmlkZXIuCiAgaWYgKGxlbmd0aChxKSA+IDApIHsKICAgIGl5IDwtIG1heChxKSAgIyBpbmRleCBvZiB0aGUgbGFzdCBkaXZpZGVyIGJlaW5nIG1vdmVkLCBpZiBhbnkKICB9CiAgd2hpbGUgKGxlbmd0aChxKSA+IDApIHsKICAgICMgUG9wIHRoZSBpbmRleCBvZiB0aGUgbmV4dCBkaXZpZGVyIGZyb20gdGhlIHF1ZXVlLgogICAgaiA8LSBxWzFdCiAgICBxIDwtIHFbLTFdCiAgICAjIE1vdmUgdGhpcyBkaXZpZGVyIGFmdGVyIHRoZSBsYXN0IG1vdmVkIGRpdmlkZXIuCiAgICBmcm9tIDwtIGRsaXN0JGRpdltqXQogICAgZGxpc3Qkc2VxW2Zyb206dG9dIDwtIGRsaXN0JHNlcVtjKChmcm9tICsgMSk6dG8sIGZyb20pXQogICAgZGxpc3QkZGl2W2pdIDwtIHRvCiAgICAjIFVwZGF0ZSBhZmZlY3RlZCBkaXZpZGVyIGxvY2F0aW9ucyAoYWxsIHRoZSBvbmVzIG1vdmluZyBvdGhlciB0aGFuIGopLgogICAgZm9yIChrIGluIGl4Oml5KSB7CiAgICAgIGlmIChrICE9IGopIHsKICAgICAgICBkbGlzdCRkaXZba10gPC0gZGxpc3QkZGl2W2tdIC0gMQogICAgICB9CiAgICB9CiAgfQogICMgUmV0dXJuIHRoZSBtb2RpZmllZCBsaXN0LgogIHJldHVybihkbGlzdCkKfQpgYGAKCkFybWVkIHdpdGggdGhlc2UgdHdvIGZ1bmN0aW9ucywgd2UgY2FuIGRlZmluZSBhIGZ1bmN0aW9uIHRoYXQgdGFrZXMgYSBkaXZpZGVkIGxpc3QgYXMgaW5wdXQgYW5kIG1vZGlmaWVzIGl0IHRvIHNhdGlzZnkgdGhlIGdyb3VwIHNpemUgbGltaXRzLgoKYGBge3J9CiMgSW5wdXQ6IGEgZGl2aWRlZCBsaXN0IHdpdGggZWxlbWVudHMgYHNlcWAgYW5kIGBkaXZgIGFzIGFib3ZlLgojIE91dHB1dDogYSBtb2RpZmllZCB2ZXJzaW9uIG9mIHRoZSBsaXN0IHNhdGlzZnlpbmcgZ3JvdXAgc2l6ZSByZXF1aXJlbWVudHMuCmFkanVzdCA8LSBmdW5jdGlvbihkbGlzdCkgewogICMgSW5pdGlhbGl6ZSB2YXJpYWJsZXMuCiAgY3VzdW0gPC0gMCAgICAgICAjIGN1bXVsYXRpdmUgc3VtIG9mIGdyb3VwIHNpemVzIHNvIGZhcgogICAgICAgICAgICAgICAgICAgIyAoVV97Zy0xfSBpbiAoMScpIGFuZCAoMicpKQogIGxhc3RfZGl2IDwtIDAgICAgIyBsb2NhdGlvbiBvZiBsYXN0IGRpdmlkZXIgZW5jb3VudGVyZWQKICAgICAgICAgICAgICAgICAgICMgKG1hcmtpbmcgdGhlIGxhc3QgcG9zaXRpb24gYmVmb3JlIHRoZSBjdXJyZW50CiAgICAgICAgICAgICAgICAgICAjIGdyb3VwIHN0YXJ0cykKICAjIFByb2Nlc3MgZ3JvdXBzIGluIG9yZGVyLCBhZGp1c3RpbmcgdGhlIGRpdmlkZXIgYXMgbmVlZGVkLgogIGZvciAoZyBpbiAxOihHIC0gMSkpIHsKICAgICMgVXBkYXRlIHRoZSBsb3dlciBhbmQgdXBwZXIgYm91bmRzLgogICAgbG8gPC0gbWF4KDEsIFMgLSAoRyAtIGcpKk0gLSBjdXN1bSkKICAgIGhpIDwtIG1pbihNLCBTIC0gRyArIGcgLSBjdXN1bSkKICAgICMgR2V0IHRoZSBsb2NhdGlvbiBvZiB0aGUgbmV4dCBkaXZpZGVyIGFuZCB0aGUgdGVudGF0aXZlIGdyb3VwIHNpemUuCiAgICBkIDwtIGRsaXN0JGRpdltnXQogICAgbiA8LSBkIC0gbGFzdF9kaXYgLSAxICAjIG5fZyBpbiAoMScpIGFuZCAoMicpCiAgICAjIEFkanVzdCBhcyBuZWVkZWQuCiAgICBpZiAobiA8IGxvKSB7CiAgICAgIGRsaXN0IDwtIG1vdmVfcmlnaHQoZGxpc3QsIGcsIGxvIC0gbikKICAgICAgbiA8LSBsbwogICAgfSBlbHNlIGlmIChuID4gaGkpIHsKICAgICAgZGxpc3QgPC0gbW92ZV9sZWZ0KGRsaXN0LCBnLCBuIC0gaGkpCiAgICAgIG4gPC0gaGkKICAgIH0KICAgICMgVXBkYXRlIHRoZSBjdW11bGF0aXZlIHN1bSBhbmQgbGFzdCBkaXZpZGVyIGxvY2F0aW9uLgogICAgY3VzdW0gPC0gY3VzdW0gKyBuCiAgICBsYXN0X2RpdiA8LSBkbGlzdCRkaXZbZ10KICB9CiAgIyBSZXR1cm4gdGhlIG1vZGlmaWVkIGxpc3QuCiAgcmV0dXJuKGRsaXN0KQp9CmBgYAoKTmV4dCwgd2UgY3JlYXRlIGEgdXRpbGl0eSBmdW5jdGlvbiB0aGF0IHRha2VzIGEgZGl2aWRlZCBzZXF1ZW5jZSBsaXN0IGFuZCBwcm9kdWNlcyBhIGxpc3Qgb2YgJEckIHZlY3RvcnMsIGVhY2ggY29udGFpbmluZyB0aGUgc2VydmVyIGxpc3QgZm9yIG9uZSBncm91cC4KCmBgYHtyfQojIElucHV0OiBhIGRpdmlkZWQgbGlzdCB3aXRoIGVsZW1lbnRzIGBzZXFgIGFuZCBgZGl2YCBhcyBhYm92ZS4KIyBPdXRwdXQ6IGEgbGlzdCBvZiBHIHZlY3RvcnMgY29udGFpbmluZyB0aGUgaW5kaWNlcyBvZiBzZXJ2ZXJzIGluIGVhY2ggZ3JvdXAKc2VydmVyX2xpc3RzIDwtIGZ1bmN0aW9uKGRsaXN0KSB7CiAgc2xpc3QgPC0gbGlzdCgpCiAgbGFzdF9kaXYgPC0gMAogIGZvciAoZyBpbiAxOkcpIHsKICAgIG5leHRfZGl2IDwtIGRsaXN0JGRpdltnXQogICAgc2xpc3RbW2ddXSA8LSBzb3J0KGRsaXN0JHNlcVsobGFzdF9kaXYgKyAxKToobmV4dF9kaXYgLTEpXSkKICAgIGxhc3RfZGl2IDwtIG5leHRfZGl2CiAgfQogIHJldHVybihzbGlzdCkKfQpgYGAKCkdpdmVuIGEgbGlzdCBvZiBzZXJ2ZXIgdmVjdG9ycyBhcyBwcm9kdWNlZCBieSBgc2VydmVyX2xpc3RzYCwgdGhlIG5leHQgZnVuY3Rpb24gZXZhbHVhdGVzIHRoZSB1dGlsaXR5IG9mIGFzc2lnbmluZyBlYWNoIHVzZXIgdG8gZWFjaCBwb3NzaWJsZSBncm91cCBhbmQgZ2VuZXJhdGVzIGEgZGF0YWZyYW1lIGNvbnRhaW5pbmcgdGhlIGNob3NlbiBncm91cCBhbmQgdXRpbGl0eSB2YWx1ZSBmb3IgZWFjaCB1c2VyLiBUbyByZWR1Y2UgY29tcHV0YXRpb24gdGltZSwgd2UgZmlyc3QgY3JlYXRlIGEgdmVjdG9yIGNvbnRhaW5pbmcgdGhlIHN1bSAkXHN1bV97cz0xfV5TIGhfe3VzfSQgb2YgdGhlIHV0aWxpdGllcyBvZiBhc3NpZ25pbmcgdXNlciAkdSQgdG8gZWFjaCBzZXJ2ZXIgJHMkLgoKYGBge3J9CnRvdGFsX3V0aWxpdHkgPC0gYXBwbHkoaCwgMSwgc3VtKQpgYGAKCldlIGFsc28gY3JlYXRlIGEgdXRpbGl0eSBmdW5jdGlvbiB0aGF0IHRha2VzIGFzIGFyZ3VtZW50cyBhIHVzZXIgYW5kIGEgdmVjdG9yIG9mIHNlcnZlcnMgaW4gYSBncm91cCBhbmQgcmV0dXJucyB0aGUgcXVhbGl0eSBtZWFzdXJlICRxX3UkIGZvciBhc3NpZ25pbmcgdGhhdCB1c2VyIHRvIHRoYXQgZ3JvdXAuCgpgYGB7cn0KIyBJbnB1dHM6CiMgIHVzZXIgPSBpbmRleCBvZiB1c2VyCiMgIGdyb3VwID0gdmVjdG9yIG9mIHNlcnZlcnMgaW4gdGhlIGdyb3VwCiMgT3V0cHV0OiBxdWFsaXR5IHZhbHVlIGZvciBhc3NpZ25pbmcgdGhlIHVzZXIgdG8gdGhhdCBncm91cAphc3NpZ25tZW50X3F1YWxpdHkgPC0gZnVuY3Rpb24odXNlciwgZ3JvdXApIHsKICBudW1lcmF0b3IgPC0gc3VtKGhbdXNlciwgZ3JvdXBdKQogIGRlbm9taW5hdG9yIDwtIHRvdGFsX3V0aWxpdHlbdXNlcl0gLSBudW1lcmF0b3IKICByZXR1cm4obnVtZXJhdG9yIC8gZGVub21pbmF0b3IpCn0KYGBgCgpUaGUgbmV4dCBmdW5jdGlvbiBtYWtlcyB0aGUgdXNlciBhc3NpZ25tZW50cy4KCmBgYHtyfQojIElucHV0OiBsaXN0IG9mIHNlcnZlciB2ZWN0b3JzIChhcyBpbiB0aGUgYGdyb3Vwc2AgZWxlbWVudCBvZiBhIHNvbHV0aW9uIGxpc3QpCiMgT3V0cHV0OiBkYXRhZnJhbWUgd2l0aCBjaG9zZW4gZ3JvdXAgYW5kIHV0aWxpdHkgZm9yIGVhY2ggdXNlciAoYXMgaW4gdGhlIGB1c2Vyc2AgZWxlbWVudCBvZiBhIHNvbHV0aW9uIGxpc3QpCmFzc2lnbl91c2VycyA8LSBmdW5jdGlvbihzbGlzdCkgewogIGRmIDwtIGRhdGEuZnJhbWUoR3JvdXAgPSByZXAuaW50KE5BLCBVKSwgUXVhbGl0eSA9IHJlcC5pbnQoTkEsIFUpKQogIGZvciAodSBpbiAxOlUpIHsKICAgICMgRXZhbHVhdGUgYWxsIHBvc3NpYmxlIGFzc2lnbm1lbnRzIG9mIHVzZXIgdS4KICAgIHF1IDwtIHNhcHBseShzbGlzdCwgZnVuY3Rpb24oeCkgYXNzaWdubWVudF9xdWFsaXR5KHUsIHgpKQogICAgIyBGaW5kIHRoZSBpbmRleCBvZiB0aGUgZmlyc3QgZ3JvdXAgdGhhdCBtYXhpbWl6ZXMgcXVhbGl0eS4KICAgIGl4IDwtIHdoaWNoLm1heChxdSkKICAgICMgUmVjb3JkIHRoZSBhc3NpZ25tZW50LgogICAgZGZbdSwgIkdyb3VwIl0gPC0gaXgKICAgIGRmW3UsICJRdWFsaXR5Il0gPC0gcXVbaXhdCiAgfQogIHJldHVybihkZikKfQpgYGAKCk5vdyB3ZSBkZWZpbmUgYSBmdW5jdGlvbiB0aGF0IGNvbnZlcnRzIGEgcGVybXV0YXRpb24gdmVjdG9yIGxpc3QgaW50byBhIHNvbHV0aW9uIGxpc3Qgd2l0aCBlbGVtZW50cyBgb2JqYCAodG90YWwgb2JqZWN0aXZlIHZhbHVlKSwgYHVzZXJzYCAoZGF0YSBmcmFtZSBvZiB1c2VyIGFzc2lnbm1lbnRzKSBhbmQgYGdyb3Vwc2AgKGxpc3Qgb2Ygc2VydmVyIHZlY3RvcnMpLgoKYGBge3J9CiMgSW5wdXQ6IGEgcGVybXV0YXRpb24gdmVjdG9yIChjaHJvbW9zb21lKQojIE91dHB1dDogYSBzb2x1dGlvbiBsaXN0CmRlY29kZSA8LSBmdW5jdGlvbihwZXJtdXRhdGlvbikgewogIHNsaXN0IDwtIGxpc3QoKQogICMgRGVjb2RlIHRoZSBwZXJtdXRhdGlvbiB2ZWN0b3IgaW50byBhIGZlYXNpYmxlIGNvbGxlY3Rpb24gb2YgZ3JvdXBzLgogIHNsaXN0JGdyb3VwcyA8LQogICAgcGVybXV0YXRpb24gJT4lIGFzX3NlcXVlbmNlKCkgJT4lIGFkanVzdCgpICU+JSBzZXJ2ZXJfbGlzdHMoKQogICMgQ29tcHV0ZSB0aGUgdXNlciBhc3NpZ25tZW50cy4KICBzbGlzdCR1c2VycyA8LSBzbGlzdCRncm91cHMgJT4lIGFzc2lnbl91c2VycygpCiAgIyBUaGUgb2JqZWN0aXZlIHZhbHVlIGlzIHRoZSBzdW0gb2YgdGhlIHVzZXIgYXNzaWdubWVudCBxdWFsaXRpZXMuCiAgc2xpc3Qkb2JqIDwtIHN1bShzbGlzdCR1c2VycyRRdWFsaXR5KQogIHJldHVybihzbGlzdCkKfQpgYGAKCiMjIEZpdG5lc3MgZnVuY3Rpb24KClRoZSBmaXRuZXNzIGZ1bmN0aW9uIHRha2VzIGEgcGVybXV0YXRpb24sIGNvbnZlcnRzIGl0IHRvIGEgZmVhc2libGUgc29sdXRpb24sIGFuZCByZXR1cm5zIHRoZSBvYmplY3RpdmUgdmFsdWUuCgpgYGB7cn0KZml0bmVzcyA8LSBmdW5jdGlvbihjaHJvbW9zb21lKSB7CiAgc29sIDwtIGNocm9tb3NvbWUgJT4lIGRlY29kZQogIHNvbCRvYmoKfQpgYGAKCiMjIFNvbHV0aW9uIHJlcG9ydAoKV2UgdXNlIHRoZSBmb2xsb3dpbmcgZnVuY3Rpb24gdG8gcmVwb3J0IG9uIGEgY2FuZGlkYXRlIHNvbHV0aW9uLgoKYGBge3J9CiMgSW5wdXQ6IGEgc29sdXRpb24gbGlzdCB3aXRoIGNvbXBvbmVudHMgYG9iamAsIGB1c2Vyc2AgYW5kIGBncm91cHNgCnNvbHV0aW9uX3JlcG9ydCA8LSBmdW5jdGlvbihzb2x1dGlvbikgewogIGNhdCgiU29sdXRpb24gd2l0aCBvdmVyYWxsIHF1YWxpdHkgPSAiLCBzb2x1dGlvbiRvYmosICI6XG4iKQogIGZvciAoZyBpbiAxOkcpIHsKICAgIGNhdCgiXHRTZXJ2ZXJzIGluIGdyb3VwICIsIGcsICI6ICIsIHNvbHV0aW9uJGdyb3Vwc1tbZ11dLCAiXG4iKQogICAgdSA8LSB3aGljaChzb2x1dGlvbiR1c2VycyRHcm91cCA9PSBnLCBhcnIuaW5kID0gVFJVRSkKICAgIGlmIChsZW5ndGgodSkgPT0gMCkgewogICAgICBjYXQoIlx0VXNlcnMgYXNzaWduZWQgdG8gZ3JvdXAgIiwgZywgIjogTk9ORVxuIikKICAgIH0gZWxzZSB7CiAgICAgIGNhdCgiXHRVc2VycyBhc3NpZ25lZCB0byBncm91cCAiLCBnLCAiICgiLCBsZW5ndGgodSksICIpOiAiLCB1LCAiXG4iKQogICAgfQogIH0KfQpgYGAKCiMgU29sdXRpb24KCldlIG5lZWQgdG8gc2V0IHNvbWUgcGFyYW1ldGVycyBmb3IgdGhlIGdlbmV0aWMgYWxnb3JpdGhtLgoKYGBge3J9CnBvcFNpemUgPC0gMjAwICAgICAgICAjIHBvcHVsYXRpb24gc2l6ZQptYXhHZW5zIDwtIDIwMCAgICAgICAgIyBudW1iZXIgb2YgZ2VuZXJhdGlvbnMgdG8gcnVuCnN0YWxsIDwtIDIwICAgICAgICAgICAjIHN0b3AgaWYgdGhpcyBtYW55IGdlbmVyYXRpb25zIGVsYXBzZSB3aXRob3V0IGFueSBpbXByb3ZlbWVudAptdWx0aXRocmVhZCA8LSBUUlVFICAgIyB1c2UgcGFyYWxsZWwgcHJvY2Vzc2VzPwptdXRhdGUgPC0gMC4yNSAgICAgICAgIyB1c2UgYSByZWxhdGl2ZWx5IGhpZ2ggbXV0YXRpb24gcHJvYmFiaWxpdHkgdG8gZGlzY291cmFnZSBwcmVtYXR1cmUgY29udmVyZ2VuY2UKYGBgCgpOb3cgd2UgcnVuIHRoZSBHQS4gV2UgdXNlIHRoZSAiaXNsYW5kIGV2b2x1dGlvbiIgdmFyaWFudCB0byB0cnkgdG8gd2FyZCBvZmYgcHJlbWF0dXJlIGNvbnZlcmdlbmNlLgoKYGBge3J9CkdBIDwtIGdhaXNsKHR5cGUgPSAicGVybXV0YXRpb24iLAogICAgICAgICAgICBmaXRuZXNzID0gZml0bmVzcywKICAgICAgICAgICAgbG93ZXIgPSAyLCAgICAgICAgICAgIyBwZXJtdXRhdGlvbiBpbmRpY2VzIHN0YXJ0IGF0IDIKICAgICAgICAgICAgdXBwZXIgPSBTICsgRyAtIDEsICAgIyBwZXJtdXRhdGlvbiBpbmRpY2VzIGVuZCBhdCBTK0ctMQogICAgICAgICAgICBwb3BTaXplID0gcG9wU2l6ZSwKICAgICAgICAgICAgbWF4aXRlciA9IG1heEdlbnMsCiAgICAgICAgICAgIHJ1biA9IHN0YWxsLAogICAgICAgICAgICBwYXJhbGxlbCA9IG11bHRpdGhyZWFkLAogICAgICAgICAgICBwbXV0YXRpb24gPSBtdXRhdGUKKQpwbG90KEdBKQpgYGAKCkxhc3QsIHdlIHJlY292ZXIgdGhlIGJlc3Qgc29sdXRpb24gZm91bmQgYnkgdGhlIEdBLgoKYGBge3J9CkdBQHNvbHV0aW9uWzEsXSAlPiUgZGVjb2RlKCkgJT4lIHNvbHV0aW9uX3JlcG9ydCgpCmBgYAo=