Introduction
In multi-dimensional analysis (MDA; Biber 1988), linguistic features are grouped into dimensions of variation based on the texts in which they co-occur, via a statistical procedure called factor analysis (FA). One input parameter to FA is the number of factors to extract, which are then interpreted as dimensions. Consequently, this parameter has a considerable influence on the picture of language variation that emerges from the analysis.
Many heuristic methods designed to help with making that choice exist, all of them with advantages and disadvantages:
Using either the chi square test or the change in square test is, of course, sensitive to the number of subjects and leads to the nonsensical condition that if one wants to find many factors, one simply runs more subjects. Parallel analysis is partially sensitive to sample size in that for large samples (N > 1,000) all of the eigen values of random factors will be very close to 1. The scree test is quite appealing but can lead to differences of interpretation as to when the scree “breaks”. Extracting interpretable factors means that the number of factors reflects the investigators creativity more than the data. vss, while very simple to understand, will not work very well if the data are very factorially complex. (Simulations suggests it will work fine if the complexities of some of the items are no more than 2). The eigen value of 1 rule, although the default for many programs, seems to be a rough way of dividing the number of variables by 3 and is probably the worst of all criteria.
(Revelle 2017: 38)
In practical, real-world settings, some of these methods can often be ruled out right off the bat. Take the example of our MDA of Czech, described e.g. in XX (ZZZZ): since the number of observations is 3000+, we cannot use parallel analysis; mean item complexity of 2.3 rules out vss. One popular choice in the context of MDA is to manually compare several plausible candidate models (with different numbers of factors) and select the one which yields the best interpretation (with the obvious disadvantage of the subjectivity of such a decision, cf. extracting interpretable factors above).
Considering that other MDA projects may encounter similar obstacles, we suggest a procedure designed to aid this manual comparison. It consists in a quantitative reformulation of some of the comparison criteria, thus minimizing the subjectivity of the decision, especially in situations where no clear winner is readily apparent.
The procedure can be summarized thus:
- Perform hierarchical cluster analysis (HCA) on the features based on their absolute loadings on all factors of all candidate models. This gives us an idea of which regularities tend to hold across all proposed solutions: e.g. features \(A\) and \(B\) may tend to always load heavily on the same dimension, so they emerge from the HCA as close to one another, whereas \(C\) always loads most prominently elsewhere.
- For each \(f\)-factor model, generate a corresponding \(f\)-cluster partition of the HCA output (by pruning it).
- Take every possible pair of \(i\)-factor model and \(j\)-cluster partition and compare how they structure the features into factors / clusters. Is the mapping straightforward (tidy) or messy (tangled)? Quantify that using a measure, call it tidiness (see more below).
- Use the performance of the individual candidate models across the comparisons in 3 to inform your choice of which one to stick with: a model which tends to come out of these comparisons as tidier than its peers is one that better represents the robust feature-grouping trends inferred via HCA, which is an argument in its favor.
This document focuses on step 3: how to operationalize tidiness. We start by giving an abstract definition, but if it feels dense, you may want to skip ahead to the concrete example with code
Defining tidiness
Tidiness is based on information-theoretic measures: the mutual information of a random variable (\(I(X; Y)\)) and the joint entropy of two random variables (\(H(X, Y)\)). It quantifies how much information about one grouping (e.g. factors) can be inferred from knowing the other grouping (e.g. clusters), relative to how much information the entire system consisting of both groupings contains:
\[
tidiness(X, Y) = \frac{I(X; Y)}{H(X,Y)}
\]
where, as per the definitions of mutual information and joint entropy:
\[
\begin{align*}
I(X; Y) &= \sum_{y \in Y}\sum_{x \in X} p(x, y) \log_2 \left( \frac{p(x,y)}{p(x) p(y)} \right) \\
H(X, Y) &= - \sum_{y \in Y}\sum_{x \in X} p(x, y) \log_2 \left[ p(x,y) \right] \\
\end{align*}
\]
Furthermore, \(p(x,y)\) is the joint probability of \(X\) and \(Y\); \(p(x)\) and \(p(y)\) are the marginal probability of \(X\) and \(Y\) respectively. Finally, \(X\) is an \(i\)-cluster partition and \(Y\) is a \(j\)-factor model.
Implementation
Example data
The objective is to compare two groupings (clusters and factors) of the same objects (features), assessing how tidy the mapping from one to the other is.
In one of the groupings – clusters – group membership is binary and exclusive: a feature either belongs to a cluster or not. Say we have 4 features and 2 clusters. We can generate a table that tells us, for every possible combination of feature and cluster, whether that feature belongs to the cluster or not:
library(tidyverse)
clusters <- expand.grid(FEATURE=LETTERS[1:4], CLUSTER=c("c1", "c2")) %>% as_tibble()
clusters$BELONGS_TO_CLUSTER <- c(1, 1, 0, 0, 0, 0, 1, 1)
clusters
\(\Rightarrow\) Features A and B belong to cluster c1, C and D to c2.
With factors, group membership is gradual. Each feature “belongs” to all of the factors to different extents, as quantified by its different loadings on those factors. Again, here’s a possible table for 4 features and 2 factors (it could have been a different number, in general, we want to be able to compare any \(i\)-cluster partition with any \(j\)-factor model; only the number of features remains the same):
factors <- expand.grid(FEATURE=LETTERS[1:4], FACTOR=c("f1", "f2")) %>% as_tibble()
factors$LOADING_ON_FACTOR <- c(.1, .05, .6, -.7, -.5, .55, -.02, .2)
factors
\(\Rightarrow\) Features A and B have a tendency to load more heavily on (= belong “more” to) factor f2, C and D to f1.
We can now merge the information about both groupings into a single table:
data <- inner_join(clusters, factors, by="FEATURE")
data
The observed occurrences of features within clusters are represented by the BELONGS_TO_CLUSTER column, the correlations between features and factors are indicated in the LOADING_ON_FACTOR column. Each row represents an event where a given feature was found in a given cluster and a given factor at the same time.
To compute the weight of that event (its unnormalized probability), multiply BELONGS_TO_CLUSTER by the absolute value of LOADING_ON_FACTOR. The absolute value is used because we only care about the strength of the correlation between a factor and a feature, not its direction.
weighted <- mutate(data, WEIGHT=BELONGS_TO_CLUSTER * abs(LOADING_ON_FACTOR)) %>%
select(-BELONGS_TO_CLUSTER, -LOADING_ON_FACTOR)
weighted
As expected, only rows where the features are with the cluster where they actually occurred contribute a non-zero WEIGHT value. We can therefore clean up the table to make it smaller:
non_zero <- filter(weighted, WEIGHT > 0)
non_zero
If later on, you find yourself wondering, “But what happened e.g. to the events where feature A is seen in cluster c2, shouldn’t these contribute to the calculation as well?”, well they do in theory, but their contribution is defined as 0, because A belongs to c1, not c2, so the weight of these events is 0 and we can afford to discard them early.
From weights to probabilities
We’re now interested in the mapping between clusters and factors: does the group of features in c1 map more or less straightforwardly onto the features that load heavily on f1, or f2 (= tidy), or conversely, is it maybe split between the two (= tangled)? In the tangled case, it’s harder to predict, given that a feature belongs to cluster c1, whether it will load more heavily on factor f1 or f2.
In order to assess this, we can aggregate the weights for every combination of CLUSTER and FACTOR:
aggregated <- select(non_zero, -FEATURE) %>%
group_by(CLUSTER, FACTOR) %>%
summarize(WEIGHT=sum(WEIGHT)) %>%
ungroup()
aggregated
\(\Rightarrow\) The correspondence between c1 and f1 is weak, so it doesn’t compete very much with the strong correspondence between c1 and f2.
We can re-arrange this in more compact form as a CLUSTER × FACTOR table…
rearranged <- spread(aggregated, FACTOR, WEIGHT) %>%
as.data.frame() %>%
remove_rownames() %>%
column_to_rownames("CLUSTER") %>%
as.matrix()
rearranged
f1 f2
c1 0.15 1.05
c2 1.30 0.22
… and normalize the weights to yield probabilities, pre-computing the joint and marginal probability distributions:
joint <- prop.table(rearranged)
joint
f1 f2
c1 0.05514706 0.38602941
c2 0.47794118 0.08088235
marginal_rows <- margin.table(joint, 1)
marginal_rows
c1 c2
0.4411765 0.5588235
marginal_columns <- margin.table(joint, 2)
marginal_columns
f1 f2
0.5330882 0.4669118
Wrapping all of this in functions
Our tidiness() function will accept a data frame in the format of the data data frame prepared above:
data
The calculations in the previous sections were implemented using for-loops in order to more closely match the equations given previously. In the functions, we’ll use a vectorized implementation instead.
tidiness <- function(data) {
data_with_probabilities <- weight_and_aggregate(data) %>%
add_probabilities()
I <- mutual_information(data_with_probabilities)
H <- joint_entropy(data_with_probabilities)
I / H
}
weight_and_aggregate <- function(data) {
mutate(
data,
# compute weights
WEIGHT=BELONGS_TO_CLUSTER * abs(LOADING_ON_FACTOR)
) %>%
# drop rows with WEIGHT = 0
filter(WEIGHT > 0) %>%
# drop unnecessary information
select(-FEATURE, -BELONGS_TO_CLUSTER, -LOADING_ON_FACTOR) %>%
# aggregate weights by cluster and factor
group_by(CLUSTER, FACTOR) %>%
summarize(WEIGHT=sum(WEIGHT)) %>%
ungroup()
}
add_probabilities <- function(weighted_and_aggregated_data) {
# compute joint prob. dist.
mutate(weighted_and_aggregated_data, JOINT=WEIGHT / sum(WEIGHT)) %>%
# compute marginal prob. dist. (clusters)
group_by(CLUSTER) %>%
mutate(MARGINAL_CLUSTER=sum(JOINT)) %>%
ungroup() %>%
# compute marginal prob. dist. (factors)
group_by(FACTOR) %>%
mutate(MARGINAL_FACTOR=sum(JOINT)) %>%
ungroup()
}
mutual_information <- function(data_with_probabilities) {
with(
data_with_probabilities,
sum(JOINT * log2(JOINT / (MARGINAL_CLUSTER * MARGINAL_FACTOR)))
)
}
joint_entropy <- function(data_with_probabilities) {
with(
data_with_probabilities,
-1 * sum(JOINT * log2(JOINT))
)
}
Let’s double check that we get the same results as previously. For reference, here’s the value we calculated manually above:
TIDINESS
[1] 0.2710474
And here’s the result of our function:
tidiness(data)
[1] 0.2710474
Looks like we’re good to go!
Testing if it works
In order to see if tidiness does the job we expect it to do, we need to compare its output on different data. The data we’ve worked with so far is fairly tidy, c1 is strongly associated with f2, c2 with f1, and the remaining associations are much weaker:
aggregated
Let’s make it messier. The only difference will be that now, feature B will load comparably on both factors f1 and f2:
messier_data <- mutate(
data,
LOADING_ON_FACTOR=ifelse(FEATURE == "B" & FACTOR == "f1", .60, LOADING_ON_FACTOR)
)
messier_data
This is what messier_data looks like when weighted and aggregated:
weight_and_aggregate(messier_data)
As you can see, the correspondence between c1 and f1 has become a more serious competitor (its weight rose from 0.15 to 0.70) to the correspondence between c1 and f2 (weight = 1.05). Let’s see how tidiness responds to that:
# same as above, for easier comparison
tidiness(data)
[1] 0.2710474
tidiness(messier_data)
[1] 0.09303736
tidiness(data) > tidiness(messier_data)
[1] TRUE
Good, it seems to be working! The data we made messier on purpose is indeed identified as less tidy than the original data. This makes sense, because in messier_data, the structure of factors has become less predictable based on the structure of clusters.
References
Biber, Douglas. 1988. Variation across speech and writing. Cambridge: Cambridge University Press.
Cvrček, Václav, Zuzana Komrsková, David Lukeš, Petra Poukarová, Anna Řehořková, Adrian Jan Zasina. 2018. From extra- to intratextual characteristics: Charting the space of variation in Czech through MDA. Corpus Linguistics and Linguistic Theory. Available on-line ahead of print via doi:10.1515/cllt-2018-0020.
Revelle, William. 2017. psych: Procedures for Personality and Psychological Research. Northwestern University, Evanston, Illinois, USA. https://CRAN.R-project.org/package=psych Version = 1.7.8.
LS0tCnRpdGxlOiAiVGlkaW5lc3M6IEEgbWVhc3VyZSBiYXNlZCBvbiBpbmZvcm1hdGlvbiB0aGVvcnkgdG8gaGVscCB3aXRoCiAgc2VsZWN0aW5nIGFuIGFwcHJvcHJpYXRlIG51bWJlciBvZiBkaW1lbnNpb25zIHRvIGV4dHJhY3QgaW4gTURBIgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIG51bWJlcl9zZWN0aW9uczogeWVzCiAgICB0b2M6IHllcwotLS0KCioqTkI6KiogVGhpcyBpcyBjb21wbGVtZW50YXJ5IG1hdGVyaWFsIHRvIFNlY3Rpb24gNCBvZiBDdnLEjWVrIGV0LiBhbAooMjAxOCksIHdoaWNoIHByZXNlbnRzIGEgbW9yZSBhY2Nlc3NpYmxlIGNvbmNlcHR1YWwgYmFja2dyb3VuZCB0byB0aGUKcmF0aGVyIHRlY2huaWNhbCBkaXNjdXNzaW9uIGJlbG93LgoKSW50cm9kdWN0aW9uCj09PT09PT09PT09PQoKSW4gKm11bHRpLWRpbWVuc2lvbmFsIGFuYWx5c2lzKiAoTURBOyBCaWJlciAxOTg4KSwgbGluZ3Vpc3RpYyBmZWF0dXJlcwphcmUgZ3JvdXBlZCBpbnRvIGRpbWVuc2lvbnMgb2YgdmFyaWF0aW9uIGJhc2VkIG9uIHRoZSB0ZXh0cyBpbiB3aGljaAp0aGV5IGNvLW9jY3VyLCB2aWEgYSBzdGF0aXN0aWNhbCBwcm9jZWR1cmUgY2FsbGVkIFsqZmFjdG9yCmFuYWx5c2lzKl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvRmFjdG9yX2FuYWx5c2lzKSAoRkEpLiBPbmUKaW5wdXQgcGFyYW1ldGVyIHRvIEZBIGlzIHRoZSAqKm51bWJlciBvZiBmYWN0b3JzIHRvIGV4dHJhY3QqKiwgd2hpY2ggYXJlCnRoZW4gaW50ZXJwcmV0ZWQgYXMgZGltZW5zaW9ucy4gQ29uc2VxdWVudGx5LCB0aGlzIHBhcmFtZXRlciBoYXMgYQpjb25zaWRlcmFibGUgaW5mbHVlbmNlIG9uIHRoZSBwaWN0dXJlIG9mIGxhbmd1YWdlIHZhcmlhdGlvbiB0aGF0IGVtZXJnZXMKZnJvbSB0aGUgYW5hbHlzaXMuCgpNYW55IGhldXJpc3RpYyBtZXRob2RzIGRlc2lnbmVkIHRvIGhlbHAgd2l0aCBtYWtpbmcgdGhhdCBjaG9pY2UgZXhpc3QsCmFsbCBvZiB0aGVtIHdpdGggYWR2YW50YWdlcyBhbmQgZGlzYWR2YW50YWdlczoKCj4gVXNpbmcgZWl0aGVyIHRoZSBjaGkgc3F1YXJlIHRlc3Qgb3IgdGhlIGNoYW5nZSBpbiBzcXVhcmUgdGVzdCBpcywgb2YKPiBjb3Vyc2UsIHNlbnNpdGl2ZSB0byB0aGUgbnVtYmVyIG9mIHN1YmplY3RzIGFuZCBsZWFkcyB0byB0aGUKPiBub25zZW5zaWNhbCBjb25kaXRpb24gdGhhdCBpZiBvbmUgd2FudHMgdG8gZmluZCBtYW55IGZhY3RvcnMsIG9uZQo+IHNpbXBseSBydW5zIG1vcmUgc3ViamVjdHMuIFBhcmFsbGVsIGFuYWx5c2lzIGlzIHBhcnRpYWxseSBzZW5zaXRpdmUgdG8KPiBzYW1wbGUgc2l6ZSBpbiB0aGF0IGZvciBsYXJnZSBzYW1wbGVzIChOID4gMSwwMDApIGFsbCBvZiB0aGUgZWlnZW4KPiB2YWx1ZXMgb2YgcmFuZG9tIGZhY3RvcnMgd2lsbCBiZSB2ZXJ5IGNsb3NlIHRvIDEuIFRoZSBzY3JlZSB0ZXN0IGlzCj4gcXVpdGUgYXBwZWFsaW5nIGJ1dCBjYW4gbGVhZCB0byBkaWZmZXJlbmNlcyBvZiBpbnRlcnByZXRhdGlvbiBhcyB0bwo+IHdoZW4gdGhlIHNjcmVlIOKAnGJyZWFrc+KAnS4gRXh0cmFjdGluZyBpbnRlcnByZXRhYmxlIGZhY3RvcnMgbWVhbnMgdGhhdAo+IHRoZSBudW1iZXIgb2YgZmFjdG9ycyByZWZsZWN0cyB0aGUgaW52ZXN0aWdhdG9ycyBjcmVhdGl2aXR5IG1vcmUgdGhhbgo+IHRoZSBkYXRhLiB2c3MsIHdoaWxlIHZlcnkgc2ltcGxlIHRvIHVuZGVyc3RhbmQsIHdpbGwgbm90IHdvcmsgdmVyeQo+IHdlbGwgaWYgdGhlIGRhdGEgYXJlIHZlcnkgZmFjdG9yaWFsbHkgY29tcGxleC4gKFNpbXVsYXRpb25zIHN1Z2dlc3RzCj4gaXQgd2lsbCB3b3JrIGZpbmUgaWYgdGhlIGNvbXBsZXhpdGllcyBvZiBzb21lIG9mIHRoZSBpdGVtcyBhcmUgbm8gbW9yZQo+IHRoYW4gMikuIFRoZSBlaWdlbiB2YWx1ZSBvZiAxIHJ1bGUsIGFsdGhvdWdoIHRoZSBkZWZhdWx0IGZvciBtYW55Cj4gcHJvZ3JhbXMsIHNlZW1zIHRvIGJlIGEgcm91Z2ggd2F5IG9mIGRpdmlkaW5nIHRoZSBudW1iZXIgb2YgdmFyaWFibGVzCj4gYnkgMyBhbmQgaXMgcHJvYmFibHkgdGhlIHdvcnN0IG9mIGFsbCBjcml0ZXJpYS4KPgo+IChbUmV2ZWxsZSAyMDE3OiAzOF0oaHR0cDovL3BlcnNvbmFsaXR5LXByb2plY3Qub3JnL3IvcHN5Y2gvSG93VG8vZmFjdG9yLnBkZikpCgpJbiBwcmFjdGljYWwsIHJlYWwtd29ybGQgc2V0dGluZ3MsIHNvbWUgb2YgdGhlc2UgbWV0aG9kcyBjYW4gb2Z0ZW4gYmUKcnVsZWQgb3V0IHJpZ2h0IG9mZiB0aGUgYmF0LiBUYWtlIHRoZSBleGFtcGxlIG9mIG91ciBNREEgb2YgQ3plY2gsCmRlc2NyaWJlZCBlLmcuIGluIFhYIChaWlpaKTogc2luY2UgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgaXMgMzAwMCssCndlIGNhbm5vdCB1c2UgcGFyYWxsZWwgYW5hbHlzaXM7IG1lYW4gaXRlbSBjb21wbGV4aXR5IG9mIDIuMyBydWxlcyBvdXQKdnNzLiBPbmUgcG9wdWxhciBjaG9pY2UgaW4gdGhlIGNvbnRleHQgb2YgTURBIGlzIHRvIG1hbnVhbGx5IGNvbXBhcmUKc2V2ZXJhbCBwbGF1c2libGUgY2FuZGlkYXRlIG1vZGVscyAod2l0aCBkaWZmZXJlbnQgbnVtYmVycyBvZiBmYWN0b3JzKQphbmQgc2VsZWN0IHRoZSBvbmUgd2hpY2ggeWllbGRzIHRoZSBiZXN0IGludGVycHJldGF0aW9uICh3aXRoIHRoZQpvYnZpb3VzIGRpc2FkdmFudGFnZSBvZiB0aGUgc3ViamVjdGl2aXR5IG9mIHN1Y2ggYSBkZWNpc2lvbiwgY2YuCipleHRyYWN0aW5nIGludGVycHJldGFibGUgZmFjdG9ycyogYWJvdmUpLgoKQ29uc2lkZXJpbmcgdGhhdCBvdGhlciBNREEgcHJvamVjdHMgbWF5IGVuY291bnRlciBzaW1pbGFyIG9ic3RhY2xlcywgd2UKc3VnZ2VzdCBhIHByb2NlZHVyZSBkZXNpZ25lZCB0byBhaWQgdGhpcyBtYW51YWwgY29tcGFyaXNvbi4gSXQgY29uc2lzdHMKaW4gYSBxdWFudGl0YXRpdmUgcmVmb3JtdWxhdGlvbiBvZiBzb21lIG9mIHRoZSBjb21wYXJpc29uIGNyaXRlcmlhLCB0aHVzCm1pbmltaXppbmcgdGhlIHN1YmplY3Rpdml0eSBvZiB0aGUgZGVjaXNpb24sIGVzcGVjaWFsbHkgaW4gc2l0dWF0aW9ucwp3aGVyZSBubyBjbGVhciB3aW5uZXIgaXMgcmVhZGlseSBhcHBhcmVudC4KClRoZSBwcm9jZWR1cmUgY2FuIGJlIHN1bW1hcml6ZWQgdGh1czoKCjEuIFBlcmZvcm0gW2hpZXJhcmNoaWNhbCBjbHVzdGVyIGFuYWx5c2lzCiAgIChIQ0EpXShodHRwOi8vd3d3LnItdHV0b3IuY29tL2dwdS1jb21wdXRpbmcvY2x1c3RlcmluZy9oaWVyYXJjaGljYWwtY2x1c3Rlci1hbmFseXNpcykKICAgb24gdGhlIGZlYXR1cmVzIGJhc2VkIG9uIHRoZWlyICphYnNvbHV0ZSogbG9hZGluZ3Mgb24gYWxsIGZhY3RvcnMgb2YKICAgYWxsIGNhbmRpZGF0ZSBtb2RlbHMuIFRoaXMgZ2l2ZXMgdXMgYW4gaWRlYSBvZiB3aGljaCByZWd1bGFyaXRpZXMKICAgdGVuZCB0byBob2xkIGFjcm9zcyBhbGwgcHJvcG9zZWQgc29sdXRpb25zOiBlLmcuIGZlYXR1cmVzICRBJCBhbmQgJEIkCiAgIG1heSB0ZW5kIHRvIGFsd2F5cyBsb2FkIGhlYXZpbHkgb24gdGhlIHNhbWUgZGltZW5zaW9uLCBzbyB0aGV5IGVtZXJnZQogICBmcm9tIHRoZSBIQ0EgYXMgY2xvc2UgdG8gb25lIGFub3RoZXIsIHdoZXJlYXMgJEMkIGFsd2F5cyBsb2FkcyBtb3N0CiAgIHByb21pbmVudGx5IGVsc2V3aGVyZS4KMi4gRm9yIGVhY2ggJGYkLWZhY3RvciBtb2RlbCwgZ2VuZXJhdGUgYSBjb3JyZXNwb25kaW5nICRmJC1jbHVzdGVyCiAgIHBhcnRpdGlvbiBvZiB0aGUgSENBIG91dHB1dCAoYnkgcHJ1bmluZyBpdCkuCjMuIFRha2UgZXZlcnkgcG9zc2libGUgcGFpciBvZiAkaSQtZmFjdG9yIG1vZGVsIGFuZCAkaiQtY2x1c3RlcgogICBwYXJ0aXRpb24gYW5kIGNvbXBhcmUgaG93IHRoZXkgc3RydWN0dXJlIHRoZSBmZWF0dXJlcyBpbnRvIGZhY3RvcnMgLwogICBjbHVzdGVycy4gSXMgdGhlIG1hcHBpbmcgc3RyYWlnaHRmb3J3YXJkICh0aWR5KSBvciBtZXNzeSAodGFuZ2xlZCk/CiAgIFF1YW50aWZ5IHRoYXQgdXNpbmcgYSBtZWFzdXJlLCBjYWxsIGl0ICp0aWRpbmVzcyogKHNlZSBtb3JlIGJlbG93KS4KNC4gVXNlIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgaW5kaXZpZHVhbCBjYW5kaWRhdGUgbW9kZWxzIGFjcm9zcyB0aGUKICAgY29tcGFyaXNvbnMgaW4gMyB0byBpbmZvcm0geW91ciBjaG9pY2Ugb2Ygd2hpY2ggb25lIHRvIHN0aWNrIHdpdGg6IGEKICAgbW9kZWwgd2hpY2ggdGVuZHMgdG8gY29tZSBvdXQgb2YgdGhlc2UgY29tcGFyaXNvbnMgYXMgdGlkaWVyIHRoYW4gaXRzCiAgIHBlZXJzIGlzIG9uZSB0aGF0IGJldHRlciByZXByZXNlbnRzIHRoZSByb2J1c3QgZmVhdHVyZS1ncm91cGluZwogICB0cmVuZHMgaW5mZXJyZWQgdmlhIEhDQSwgd2hpY2ggaXMgYW4gYXJndW1lbnQgaW4gaXRzIGZhdm9yLgoKVGhpcyBkb2N1bWVudCBmb2N1c2VzIG9uIHN0ZXAgMzogaG93IHRvIG9wZXJhdGlvbmFsaXplICp0aWRpbmVzcyouIFdlCnN0YXJ0IGJ5IGdpdmluZyBhbiBhYnN0cmFjdCBkZWZpbml0aW9uLCBidXQgaWYgaXQgZmVlbHMgZGVuc2UsIHlvdSBtYXkKd2FudCB0byBza2lwIGFoZWFkIHRvIHRoZSBbY29uY3JldGUgZXhhbXBsZSB3aXRoIGNvZGVdKCNpbXBsZW1lbnRhdGlvbikKCkRlZmluaW5nICp0aWRpbmVzcyoKPT09PT09PT09PT09PT09PT09PQoKPGNlbnRlcj4KIVtGaWcuIFZpc3VhbCBtb3RpdmF0aW9uIGZvciB0aGUgZGVmaW5pdGlvbiBvZiAqdGlkaW5lc3MqLl0odGlkaW5lc3MucG5nKXsgd2lkdGg9NjAlIH0KPC9jZW50ZXI+CgoqVGlkaW5lc3MqIGlzIGJhc2VkIG9uIGluZm9ybWF0aW9uLXRoZW9yZXRpYyBtZWFzdXJlczogdGhlIFsqbXV0dWFsCmluZm9ybWF0aW9uKl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTXV0dWFsX2luZm9ybWF0aW9uKSBvZiBhCnJhbmRvbSB2YXJpYWJsZSAoJEkoWDsgWSkkKSBhbmQgdGhlIFsqam9pbnQKZW50cm9weSpdKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0pvaW50X2VudHJvcHkpIG9mIHR3byByYW5kb20KdmFyaWFibGVzICgkSChYLCBZKSQpLiBJdCBxdWFudGlmaWVzIGhvdyBtdWNoIGluZm9ybWF0aW9uIGFib3V0IG9uZQpncm91cGluZyAoZS5nLiBmYWN0b3JzKSBjYW4gYmUgaW5mZXJyZWQgZnJvbSBrbm93aW5nIHRoZSBvdGhlciBncm91cGluZwooZS5nLiBjbHVzdGVycyksIHJlbGF0aXZlIHRvIGhvdyBtdWNoIGluZm9ybWF0aW9uIHRoZSBlbnRpcmUgc3lzdGVtCmNvbnNpc3Rpbmcgb2YgYm90aCBncm91cGluZ3MgY29udGFpbnM6CgokJAp0aWRpbmVzcyhYLCBZKSA9IFxmcmFje0koWDsgWSl9e0goWCxZKX0KJCQKCndoZXJlLCBhcyBwZXIgdGhlIGRlZmluaXRpb25zIG9mIG11dHVhbCBpbmZvcm1hdGlvbiBhbmQgam9pbnQgZW50cm9weToKCiQkClxiZWdpbnthbGlnbip9CkkoWDsgWSkgJj0gXHN1bV97eSBcaW4gWX1cc3VtX3t4IFxpbiBYfSBwKHgsIHkpIFxsb2dfMiBcbGVmdCggXGZyYWN7cCh4LHkpfXtwKHgpIHAoeSl9IFxyaWdodCkgXFwKSChYLCBZKSAmPSAtIFxzdW1fe3kgXGluIFl9XHN1bV97eCBcaW4gWH0gcCh4LCB5KSBcbG9nXzIgXGxlZnRbIHAoeCx5KSBccmlnaHRdIFxcClxlbmR7YWxpZ24qfQokJAoKRnVydGhlcm1vcmUsICRwKHgseSkkIGlzIHRoZSBbam9pbnQKcHJvYmFiaWxpdHldKGh0dHBzOi8vZW4ud2lraXBlZGlhLm9yZy93aWtpL0pvaW50X3Byb2JhYmlsaXR5X2Rpc3RyaWJ1dGlvbikKb2YgJFgkIGFuZCAkWSQ7ICRwKHgpJCBhbmQgJHAoeSkkIGFyZSB0aGUgW21hcmdpbmFsCnByb2JhYmlsaXR5XShodHRwczovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9NYXJnaW5hbF9kaXN0cmlidXRpb24pIG9mICRYJAphbmQgJFkkIHJlc3BlY3RpdmVseS4gRmluYWxseSwgJFgkIGlzIGFuICRpJC1jbHVzdGVyIHBhcnRpdGlvbiBhbmQgJFkkCmlzIGEgJGokLWZhY3RvciBtb2RlbC4KCkltcGxlbWVudGF0aW9uCj09PT09PT09PT09PT09CgpFeGFtcGxlIGRhdGEKLS0tLS0tLS0tLS0tCgpUaGUgb2JqZWN0aXZlIGlzIHRvIGNvbXBhcmUgdHdvIGdyb3VwaW5ncyAoY2x1c3RlcnMgYW5kIGZhY3RvcnMpIG9mIHRoZQpzYW1lIG9iamVjdHMgKGZlYXR1cmVzKSwgYXNzZXNzaW5nIGhvdyB0aWR5IHRoZSBtYXBwaW5nIGZyb20gb25lIHRvIHRoZQpvdGhlciBpcy4KCkluIG9uZSBvZiB0aGUgZ3JvdXBpbmdzIC0tIGNsdXN0ZXJzIC0tIGdyb3VwIG1lbWJlcnNoaXAgaXMgYmluYXJ5IGFuZApleGNsdXNpdmU6IGEgZmVhdHVyZSBlaXRoZXIgYmVsb25ncyB0byBhIGNsdXN0ZXIgb3Igbm90LiBTYXkgd2UgaGF2ZSA0CmZlYXR1cmVzIGFuZCAyIGNsdXN0ZXJzLiBXZSBjYW4gZ2VuZXJhdGUgYSB0YWJsZSB0aGF0IHRlbGxzIHVzLCBmb3IKZXZlcnkgcG9zc2libGUgY29tYmluYXRpb24gb2YgZmVhdHVyZSBhbmQgY2x1c3Rlciwgd2hldGhlciB0aGF0IGZlYXR1cmUKYmVsb25ncyB0byB0aGUgY2x1c3RlciBvciBub3Q6CgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KHRpZHl2ZXJzZSkKCmNsdXN0ZXJzIDwtIGV4cGFuZC5ncmlkKEZFQVRVUkU9TEVUVEVSU1sxOjRdLCBDTFVTVEVSPWMoImMxIiwgImMyIikpICU+JSBhc190aWJibGUoKQpjbHVzdGVycyRCRUxPTkdTX1RPX0NMVVNURVIgPC0gYygxLCAxLCAwLCAwLCAwLCAwLCAxLCAxKQpjbHVzdGVycwpgYGAKCiRcUmlnaHRhcnJvdyQgRmVhdHVyZXMgYEFgIGFuZCBgQmAgYmVsb25nIHRvIGNsdXN0ZXIgYGMxYCwgYENgIGFuZCBgRGAKdG8gYGMyYC4KCldpdGggZmFjdG9ycywgZ3JvdXAgbWVtYmVyc2hpcCBpcyBncmFkdWFsLiBFYWNoIGZlYXR1cmUgImJlbG9uZ3MiIHRvCioqYWxsKiogb2YgdGhlIGZhY3RvcnMgdG8gZGlmZmVyZW50IGV4dGVudHMsIGFzIHF1YW50aWZpZWQgYnkgaXRzCmRpZmZlcmVudCBsb2FkaW5ncyBvbiB0aG9zZSBmYWN0b3JzLiBBZ2FpbiwgaGVyZSdzIGEgcG9zc2libGUgdGFibGUgZm9yCjQgZmVhdHVyZXMgYW5kIDIgZmFjdG9ycyAoaXQgY291bGQgaGF2ZSBiZWVuIGEgZGlmZmVyZW50IG51bWJlciwgaW4KZ2VuZXJhbCwgd2Ugd2FudCB0byBiZSBhYmxlIHRvIGNvbXBhcmUgYW55ICRpJC1jbHVzdGVyIHBhcnRpdGlvbiB3aXRoCmFueSAkaiQtZmFjdG9yIG1vZGVsOyBvbmx5IHRoZSBudW1iZXIgb2YgZmVhdHVyZXMgcmVtYWlucyB0aGUgc2FtZSk6CgpgYGB7cn0KZmFjdG9ycyA8LSBleHBhbmQuZ3JpZChGRUFUVVJFPUxFVFRFUlNbMTo0XSwgRkFDVE9SPWMoImYxIiwgImYyIikpICU+JSBhc190aWJibGUoKQpmYWN0b3JzJExPQURJTkdfT05fRkFDVE9SIDwtIGMoLjEsIC4wNSwgLjYsIC0uNywgLS41LCAuNTUsIC0uMDIsIC4yKQpmYWN0b3JzCmBgYAoKJFxSaWdodGFycm93JCBGZWF0dXJlcyBgQWAgYW5kIGBCYCBoYXZlIGEgdGVuZGVuY3kgdG8gbG9hZCBtb3JlIGhlYXZpbHkKb24gKD0gYmVsb25nICJtb3JlIiB0bykgZmFjdG9yIGBmMmAsIGBDYCBhbmQgYERgIHRvIGBmMWAuCgpXZSBjYW4gbm93IG1lcmdlIHRoZSBpbmZvcm1hdGlvbiBhYm91dCBib3RoIGdyb3VwaW5ncyBpbnRvIGEgc2luZ2xlCnRhYmxlOgoKYGBge3J9CmRhdGEgPC0gaW5uZXJfam9pbihjbHVzdGVycywgZmFjdG9ycywgYnk9IkZFQVRVUkUiKQpkYXRhCmBgYAoKVGhlIG9ic2VydmVkIG9jY3VycmVuY2VzIG9mIGZlYXR1cmVzIHdpdGhpbiBjbHVzdGVycyBhcmUgcmVwcmVzZW50ZWQgYnkKdGhlIGBCRUxPTkdTX1RPX0NMVVNURVJgIGNvbHVtbiwgdGhlIGNvcnJlbGF0aW9ucyBiZXR3ZWVuIGZlYXR1cmVzIGFuZApmYWN0b3JzIGFyZSBpbmRpY2F0ZWQgaW4gdGhlIGBMT0FESU5HX09OX0ZBQ1RPUmAgY29sdW1uLiBFYWNoIHJvdwpyZXByZXNlbnRzIGFuIGV2ZW50IHdoZXJlIGEgZ2l2ZW4gZmVhdHVyZSB3YXMgZm91bmQgaW4gYSBnaXZlbiBjbHVzdGVyCmFuZCBhIGdpdmVuIGZhY3RvciBhdCB0aGUgc2FtZSB0aW1lLgoKVG8gY29tcHV0ZSB0aGUgd2VpZ2h0IG9mIHRoYXQgZXZlbnQgKGl0cyB1bm5vcm1hbGl6ZWQgcHJvYmFiaWxpdHkpLAptdWx0aXBseSBgQkVMT05HU19UT19DTFVTVEVSYCBieSB0aGUgKiphYnNvbHV0ZSB2YWx1ZSoqIG9mCmBMT0FESU5HX09OX0ZBQ1RPUmAuIFRoZSBhYnNvbHV0ZSB2YWx1ZSBpcyB1c2VkIGJlY2F1c2Ugd2Ugb25seSBjYXJlCmFib3V0IHRoZSAqKnN0cmVuZ3RoKiogb2YgdGhlIGNvcnJlbGF0aW9uIGJldHdlZW4gYSBmYWN0b3IgYW5kIGEKZmVhdHVyZSwgbm90IGl0cyAqKmRpcmVjdGlvbioqLgoKYGBge3J9CndlaWdodGVkIDwtIG11dGF0ZShkYXRhLCBXRUlHSFQ9QkVMT05HU19UT19DTFVTVEVSICogYWJzKExPQURJTkdfT05fRkFDVE9SKSkgJT4lCiAgc2VsZWN0KC1CRUxPTkdTX1RPX0NMVVNURVIsIC1MT0FESU5HX09OX0ZBQ1RPUikKd2VpZ2h0ZWQKYGBgCgpBcyBleHBlY3RlZCwgb25seSByb3dzIHdoZXJlIHRoZSBmZWF0dXJlcyBhcmUgd2l0aCB0aGUgY2x1c3RlciB3aGVyZQp0aGV5IGFjdHVhbGx5IG9jY3VycmVkIGNvbnRyaWJ1dGUgYSBub24temVybyBgV0VJR0hUYCB2YWx1ZS4gV2UgY2FuCnRoZXJlZm9yZSBjbGVhbiB1cCB0aGUgdGFibGUgdG8gbWFrZSBpdCBzbWFsbGVyOgoKYGBge3J9Cm5vbl96ZXJvIDwtIGZpbHRlcih3ZWlnaHRlZCwgV0VJR0hUID4gMCkKbm9uX3plcm8KYGBgCgpJZiBsYXRlciBvbiwgeW91IGZpbmQgeW91cnNlbGYgd29uZGVyaW5nLCAiQnV0IHdoYXQgaGFwcGVuZWQgZS5nLiB0byB0aGUKZXZlbnRzIHdoZXJlIGZlYXR1cmUgYEFgIGlzIHNlZW4gaW4gY2x1c3RlciBgYzJgLCBzaG91bGRuJ3QgdGhlc2UKY29udHJpYnV0ZSB0byB0aGUgY2FsY3VsYXRpb24gYXMgd2VsbD8iLCB3ZWxsIHRoZXkgZG8gaW4gdGhlb3J5LCBidXQKdGhlaXIgY29udHJpYnV0aW9uIGlzIGRlZmluZWQgYXMgMCwgYmVjYXVzZSBgQWAgYmVsb25ncyB0byBgYzFgLCBub3QKYGMyYCwgc28gdGhlIHdlaWdodCBvZiB0aGVzZSBldmVudHMgaXMgMCBhbmQgd2UgY2FuIGFmZm9yZCB0byBkaXNjYXJkCnRoZW0gZWFybHkuCgpGcm9tIHdlaWdodHMgdG8gcHJvYmFiaWxpdGllcwotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKV2UncmUgbm93IGludGVyZXN0ZWQgaW4gdGhlIG1hcHBpbmcgYmV0d2VlbiBjbHVzdGVycyBhbmQgZmFjdG9yczogZG9lcwp0aGUgZ3JvdXAgb2YgZmVhdHVyZXMgaW4gYGMxYCBtYXAgbW9yZSBvciBsZXNzIHN0cmFpZ2h0Zm9yd2FyZGx5IG9udG8KdGhlIGZlYXR1cmVzIHRoYXQgbG9hZCBoZWF2aWx5IG9uIGBmMWAsIG9yIGBmMmAgKD0gdGlkeSksIG9yIGNvbnZlcnNlbHksCmlzIGl0IG1heWJlIHNwbGl0IGJldHdlZW4gdGhlIHR3byAoPSB0YW5nbGVkKT8gSW4gdGhlIHRhbmdsZWQgY2FzZSwgaXQncwpoYXJkZXIgdG8gcHJlZGljdCwgZ2l2ZW4gdGhhdCBhIGZlYXR1cmUgYmVsb25ncyB0byBjbHVzdGVyIGBjMWAsIHdoZXRoZXIKaXQgd2lsbCBsb2FkIG1vcmUgaGVhdmlseSBvbiBmYWN0b3IgYGYxYCBvciBgZjJgLgoKSW4gb3JkZXIgdG8gYXNzZXNzIHRoaXMsIHdlIGNhbiBhZ2dyZWdhdGUgdGhlIHdlaWdodHMgZm9yIGV2ZXJ5CmNvbWJpbmF0aW9uIG9mIGBDTFVTVEVSYCBhbmQgYEZBQ1RPUmA6CgpgYGB7cn0KYWdncmVnYXRlZCA8LSBzZWxlY3Qobm9uX3plcm8sIC1GRUFUVVJFKSAlPiUKICBncm91cF9ieShDTFVTVEVSLCBGQUNUT1IpICU+JQogIHN1bW1hcml6ZShXRUlHSFQ9c3VtKFdFSUdIVCkpICU+JQogIHVuZ3JvdXAoKQphZ2dyZWdhdGVkCmBgYAoKJFxSaWdodGFycm93JCBUaGUgY29ycmVzcG9uZGVuY2UgYmV0d2VlbiBgYzFgIGFuZCBgZjFgIGlzIHdlYWssIHNvIGl0CmRvZXNuJ3QgY29tcGV0ZSB2ZXJ5IG11Y2ggd2l0aCB0aGUgc3Ryb25nIGNvcnJlc3BvbmRlbmNlIGJldHdlZW4gYGMxYAphbmQgYGYyYC4KCldlIGNhbiByZS1hcnJhbmdlIHRoaXMgaW4gbW9yZSBjb21wYWN0IGZvcm0gYXMgYSBgQ0xVU1RFUmAgw5cgYEZBQ1RPUmAKdGFibGUuLi4KCmBgYHtyfQpyZWFycmFuZ2VkIDwtIHNwcmVhZChhZ2dyZWdhdGVkLCBGQUNUT1IsIFdFSUdIVCkgJT4lCiAgYXMuZGF0YS5mcmFtZSgpICU+JQogIHJlbW92ZV9yb3duYW1lcygpICU+JQogIGNvbHVtbl90b19yb3duYW1lcygiQ0xVU1RFUiIpICU+JQogIGFzLm1hdHJpeCgpCnJlYXJyYW5nZWQKYGBgCgouLi4gYW5kIG5vcm1hbGl6ZSB0aGUgd2VpZ2h0cyB0byB5aWVsZCBwcm9iYWJpbGl0aWVzLCBwcmUtY29tcHV0aW5nIHRoZQpqb2ludCBhbmQgbWFyZ2luYWwgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uczoKCmBgYHtyfQpqb2ludCA8LSBwcm9wLnRhYmxlKHJlYXJyYW5nZWQpCmpvaW50CmBgYAoKYGBge3J9Cm1hcmdpbmFsX3Jvd3MgPC0gbWFyZ2luLnRhYmxlKGpvaW50LCAxKQptYXJnaW5hbF9yb3dzCmBgYAoKYGBge3J9Cm1hcmdpbmFsX2NvbHVtbnMgPC0gbWFyZ2luLnRhYmxlKGpvaW50LCAyKQptYXJnaW5hbF9jb2x1bW5zCmBgYAoKQ29tcHV0aW5nIG11dHVhbCBpbmZvcm1hdGlvbiwgam9pbnQgZW50cm9weSBhbmQgKnRpZGluZXNzKgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCgpXZSBub3cgaGF2ZSBhbGwgd2UgbmVlZCB0byBmaWxsIG91dCB0aGUgZXF1YXRpb25zIGdpdmVuClthYm92ZV0oI2RlZmluaW5nLXRpZGluZXNzKS4gRmlyc3QsIG11dHVhbCBpbmZvcm1hdGlvbiAoJEkkKToKCmBgYHtyfQojIHRoZSBjb21tZW50cyByZWZlciBiYWNrIHRvIHRoZSBlcXVhdGlvbiBhYm92ZQpJIDwtIDAKIyBvdXRlciDOozogZm9yIGNsdXN0ZXIgeCBpbiBpLWNsdXN0ZXIgcGFydGl0aW9uIFgKZm9yIChybiBpbiByb3duYW1lcyhqb2ludCkpIHsKICAjIGlubmVyIM6jOiBmb3IgZmFjdG9yIHkgaW4gai1mYWN0b3IgbW9kZWwgWQogIGZvciAoY24gaW4gY29sbmFtZXMoam9pbnQpKSB7CiAgICAjIGpvaW50IHByb2JhYmlsaXR5IG9mIGNsdXN0ZXIgeCBhbmQgZmFjdG9yIHkKICAgIGogPC0gam9pbnRbcm4sIGNuXQogICAgIyBtYXJnaW5hbCBwcm9iYWJpbGl0eSBvZiBjbHVzdGVyIHgKICAgIG1yIDwtIG1hcmdpbmFsX3Jvd3Nbcm5dCiAgICAjIG1hcmdpbmFsIHByb2JhYmlsaXR5IG9mIGZhY3RvciB5CiAgICBtYyA8LSBtYXJnaW5hbF9jb2x1bW5zW2NuXQogICAgSSA8LSBJICsgaiAqIGxvZzIoaiAvIChtciAqIG1jKSkKICB9Cn0KSSA8LSB1bm5hbWUoSSkKSQpgYGAKCk5vdywgam9pbnQgZW50cm9weSAoJEgkKToKCmBgYHtyfQpIIDwtIDAKZm9yIChqIGluIGpvaW50KSB7CiAgSCA8LSBIIC0gaiAqIGxvZzIoaikKfQpICmBgYAoKQW5kIGZpbmFsbHksICp0aWRpbmVzcyo6CgpgYGB7cn0KVElESU5FU1MgPC0gSSAvIEgKVElESU5FU1MKYGBgCgpPZiBjb3Vyc2UsIG9uZSB0aWRpbmVzcyBudW1iZXIgb24gaXRzIG93biBpc24ndCBhbGwgdGhhdCB1c2VmdWwsIHdlIHdhbnQKdG8gdXNlIGl0IHRvICpjb21wYXJlKiBtb2RlbHMuIFdlJ2xsIHRyeSBzb21lIGV4YW1wbGVzCltiZWxvd10oI3Rlc3RpbmctaWYtaXQtd29ya3MpLCBhZnRlciB3ZSd2ZSBkZWZpbmVkIGFwcHJvcHJpYXRlIGZ1bmN0aW9ucwp0byBlbmNhcHN1bGF0ZSB0aGUgY2FsY3VsYXRpb25zIHNrZXRjaGVkIGFib3ZlLgoKV3JhcHBpbmcgYWxsIG9mIHRoaXMgaW4gZnVuY3Rpb25zCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQoKT3VyIGB0aWRpbmVzcygpYCBmdW5jdGlvbiB3aWxsIGFjY2VwdCBhIGRhdGEgZnJhbWUgaW4gdGhlIGZvcm1hdCBvZiB0aGUKYGRhdGFgIGRhdGEgZnJhbWUgcHJlcGFyZWQgYWJvdmU6CgpgYGB7cn0KZGF0YQpgYGAKClRoZSBjYWxjdWxhdGlvbnMgaW4gdGhlIHByZXZpb3VzIHNlY3Rpb25zIHdlcmUgaW1wbGVtZW50ZWQgdXNpbmcKZm9yLWxvb3BzIGluIG9yZGVyIHRvIG1vcmUgY2xvc2VseSBtYXRjaCB0aGUgZXF1YXRpb25zIGdpdmVuIHByZXZpb3VzbHkuCkluIHRoZSBmdW5jdGlvbnMsIHdlJ2xsIHVzZSBhIHZlY3Rvcml6ZWQgaW1wbGVtZW50YXRpb24gaW5zdGVhZC4KCmBgYHtyfQp0aWRpbmVzcyA8LSBmdW5jdGlvbihkYXRhKSB7CiAgZGF0YV93aXRoX3Byb2JhYmlsaXRpZXMgPC0gd2VpZ2h0X2FuZF9hZ2dyZWdhdGUoZGF0YSkgJT4lCiAgICBhZGRfcHJvYmFiaWxpdGllcygpCiAgSSA8LSBtdXR1YWxfaW5mb3JtYXRpb24oZGF0YV93aXRoX3Byb2JhYmlsaXRpZXMpCiAgSCA8LSBqb2ludF9lbnRyb3B5KGRhdGFfd2l0aF9wcm9iYWJpbGl0aWVzKQogIEkgLyBICn0KCndlaWdodF9hbmRfYWdncmVnYXRlIDwtIGZ1bmN0aW9uKGRhdGEpIHsKIG11dGF0ZSgKICAgIGRhdGEsCiAgICAjIGNvbXB1dGUgd2VpZ2h0cwogICAgV0VJR0hUPUJFTE9OR1NfVE9fQ0xVU1RFUiAqIGFicyhMT0FESU5HX09OX0ZBQ1RPUikKICApICU+JQogICAgIyBkcm9wIHJvd3Mgd2l0aCBXRUlHSFQgPSAwCiAgICBmaWx0ZXIoV0VJR0hUID4gMCkgJT4lCiAgICAjIGRyb3AgdW5uZWNlc3NhcnkgaW5mb3JtYXRpb24KICAgIHNlbGVjdCgtRkVBVFVSRSwgLUJFTE9OR1NfVE9fQ0xVU1RFUiwgLUxPQURJTkdfT05fRkFDVE9SKSAlPiUKICAgICMgYWdncmVnYXRlIHdlaWdodHMgYnkgY2x1c3RlciBhbmQgZmFjdG9yCiAgICBncm91cF9ieShDTFVTVEVSLCBGQUNUT1IpICU+JQogICAgc3VtbWFyaXplKFdFSUdIVD1zdW0oV0VJR0hUKSkgJT4lCiAgICB1bmdyb3VwKCkKfQoKYWRkX3Byb2JhYmlsaXRpZXMgPC0gZnVuY3Rpb24od2VpZ2h0ZWRfYW5kX2FnZ3JlZ2F0ZWRfZGF0YSkgewogICMgY29tcHV0ZSBqb2ludCBwcm9iLiBkaXN0LgogIG11dGF0ZSh3ZWlnaHRlZF9hbmRfYWdncmVnYXRlZF9kYXRhLCBKT0lOVD1XRUlHSFQgLyBzdW0oV0VJR0hUKSkgJT4lCiAgICAjIGNvbXB1dGUgbWFyZ2luYWwgcHJvYi4gZGlzdC4gKGNsdXN0ZXJzKQogICAgZ3JvdXBfYnkoQ0xVU1RFUikgJT4lCiAgICBtdXRhdGUoTUFSR0lOQUxfQ0xVU1RFUj1zdW0oSk9JTlQpKSAlPiUKICAgIHVuZ3JvdXAoKSAlPiUKICAgICMgY29tcHV0ZSBtYXJnaW5hbCBwcm9iLiBkaXN0LiAoZmFjdG9ycykKICAgIGdyb3VwX2J5KEZBQ1RPUikgJT4lCiAgICBtdXRhdGUoTUFSR0lOQUxfRkFDVE9SPXN1bShKT0lOVCkpICU+JQogICAgdW5ncm91cCgpCn0KCm11dHVhbF9pbmZvcm1hdGlvbiA8LSBmdW5jdGlvbihkYXRhX3dpdGhfcHJvYmFiaWxpdGllcykgewogIHdpdGgoCiAgICBkYXRhX3dpdGhfcHJvYmFiaWxpdGllcywKICAgIHN1bShKT0lOVCAqIGxvZzIoSk9JTlQgLyAoTUFSR0lOQUxfQ0xVU1RFUiAqIE1BUkdJTkFMX0ZBQ1RPUikpKQogICkKfQoKam9pbnRfZW50cm9weSA8LSBmdW5jdGlvbihkYXRhX3dpdGhfcHJvYmFiaWxpdGllcykgewogIHdpdGgoCiAgICBkYXRhX3dpdGhfcHJvYmFiaWxpdGllcywKICAgIC0xICogc3VtKEpPSU5UICogbG9nMihKT0lOVCkpCiAgKQp9CmBgYAoKTGV0J3MgZG91YmxlIGNoZWNrIHRoYXQgd2UgZ2V0IHRoZSBzYW1lIHJlc3VsdHMgYXMgcHJldmlvdXNseS4gRm9yCnJlZmVyZW5jZSwgaGVyZSdzIHRoZSB2YWx1ZSB3ZSBjYWxjdWxhdGVkIG1hbnVhbGx5IGFib3ZlOgoKYGBge3J9ClRJRElORVNTCmBgYAoKQW5kIGhlcmUncyB0aGUgcmVzdWx0IG9mIG91ciBmdW5jdGlvbjoKCmBgYHtyfQp0aWRpbmVzcyhkYXRhKQpgYGAKCkxvb2tzIGxpa2Ugd2UncmUgZ29vZCB0byBnbyEKClRlc3RpbmcgaWYgaXQgd29ya3MKPT09PT09PT09PT09PT09PT09PQoKSW4gb3JkZXIgdG8gc2VlIGlmICp0aWRpbmVzcyogZG9lcyB0aGUgam9iIHdlIGV4cGVjdCBpdCB0byBkbywgd2UgbmVlZAp0byBjb21wYXJlIGl0cyBvdXRwdXQgb24gZGlmZmVyZW50IGRhdGEuIFRoZSBkYXRhIHdlJ3ZlIHdvcmtlZCB3aXRoIHNvCmZhciBpcyBmYWlybHkgdGlkeSwgYGMxYCBpcyBzdHJvbmdseSBhc3NvY2lhdGVkIHdpdGggYGYyYCwgYGMyYCB3aXRoCmBmMWAsIGFuZCB0aGUgcmVtYWluaW5nIGFzc29jaWF0aW9ucyBhcmUgbXVjaCB3ZWFrZXI6CgpgYGB7cn0KYWdncmVnYXRlZApgYGAKCkxldCdzIG1ha2UgaXQgbWVzc2llci4gVGhlIG9ubHkgZGlmZmVyZW5jZSB3aWxsIGJlIHRoYXQgbm93LCBmZWF0dXJlIGBCYAp3aWxsIGxvYWQgY29tcGFyYWJseSBvbiBib3RoIGZhY3RvcnMgYGYxYCBhbmQgYGYyYDoKCmBgYHtyfQptZXNzaWVyX2RhdGEgPC0gbXV0YXRlKAogIGRhdGEsCiAgTE9BRElOR19PTl9GQUNUT1I9aWZlbHNlKEZFQVRVUkUgPT0gIkIiICYgRkFDVE9SID09ICJmMSIsIC42MCwgTE9BRElOR19PTl9GQUNUT1IpCikKbWVzc2llcl9kYXRhCmBgYAoKVGhpcyBpcyB3aGF0IGBtZXNzaWVyX2RhdGFgIGxvb2tzIGxpa2Ugd2hlbiB3ZWlnaHRlZCBhbmQgYWdncmVnYXRlZDoKCmBgYHtyfQp3ZWlnaHRfYW5kX2FnZ3JlZ2F0ZShtZXNzaWVyX2RhdGEpCmBgYAoKQXMgeW91IGNhbiBzZWUsIHRoZSBjb3JyZXNwb25kZW5jZSBiZXR3ZWVuIGBjMWAgYW5kIGBmMWAgaGFzIGJlY29tZSBhCm1vcmUgc2VyaW91cyBjb21wZXRpdG9yIChpdHMgd2VpZ2h0IHJvc2UgZnJvbSAwLjE1IHRvIDAuNzApIHRvIHRoZQpjb3JyZXNwb25kZW5jZSBiZXR3ZWVuIGBjMWAgYW5kIGBmMmAgKHdlaWdodCA9IDEuMDUpLiBMZXQncyBzZWUgaG93Cip0aWRpbmVzcyogcmVzcG9uZHMgdG8gdGhhdDoKCmBgYHtyfQojIHNhbWUgYXMgYWJvdmUsIGZvciBlYXNpZXIgY29tcGFyaXNvbgp0aWRpbmVzcyhkYXRhKQpgYGAKCmBgYHtyfQp0aWRpbmVzcyhtZXNzaWVyX2RhdGEpCmBgYAoKYGBge3J9CnRpZGluZXNzKGRhdGEpID4gdGlkaW5lc3MobWVzc2llcl9kYXRhKQpgYGAKCkdvb2QsIGl0IHNlZW1zIHRvIGJlIHdvcmtpbmchIFRoZSBkYXRhIHdlIG1hZGUgbWVzc2llciBvbiBwdXJwb3NlIGlzCmluZGVlZCBpZGVudGlmaWVkIGFzIGxlc3MgdGlkeSB0aGFuIHRoZSBvcmlnaW5hbCBkYXRhLiBUaGlzIG1ha2VzIHNlbnNlLApiZWNhdXNlIGluIGBtZXNzaWVyX2RhdGFgLCB0aGUgc3RydWN0dXJlIG9mIGZhY3RvcnMgaGFzIGJlY29tZSBsZXNzCnByZWRpY3RhYmxlIGJhc2VkIG9uIHRoZSBzdHJ1Y3R1cmUgb2YgY2x1c3RlcnMuCgpSZWZlcmVuY2VzCj09PT09PT09PT0KCkJpYmVyLCBEb3VnbGFzLiAxOTg4LiAqVmFyaWF0aW9uIGFjcm9zcyBzcGVlY2ggYW5kIHdyaXRpbmcqLgogIENhbWJyaWRnZTogQ2FtYnJpZGdlIFVuaXZlcnNpdHkgUHJlc3MuCgpDdnLEjWVrLCBWw6FjbGF2LCBadXphbmEgS29tcnNrb3bDoSwgRGF2aWQgTHVrZcWhLCBQZXRyYSBQb3VrYXJvdsOhLCBBbm5hCiAgxZhlaG/FmWtvdsOhLCBBZHJpYW4gSmFuIFphc2luYS4gMjAxOC4gRnJvbSBleHRyYS0gdG8gaW50cmF0ZXh0dWFsCiAgY2hhcmFjdGVyaXN0aWNzOiBDaGFydGluZyB0aGUgc3BhY2Ugb2YgdmFyaWF0aW9uIGluIEN6ZWNoIHRocm91Z2ggTURBLgogICpDb3JwdXMgTGluZ3Vpc3RpY3MgYW5kIExpbmd1aXN0aWMgVGhlb3J5Ki4gQXZhaWxhYmxlIG9uLWxpbmUgYWhlYWQgb2YKICBwcmludCB2aWEKICBbZG9pOjEwLjE1MTUvY2xsdC0yMDE4LTAwMjBdKGh0dHBzOi8vZG9pLm9yZy8xMC4xNTE1L2NsbHQtMjAxOC0wMDIwKS4KClJldmVsbGUsIFdpbGxpYW0uIDIwMTcuICpwc3ljaDogUHJvY2VkdXJlcyBmb3IgUGVyc29uYWxpdHkgYW5kCiAgUHN5Y2hvbG9naWNhbCBSZXNlYXJjaCouIE5vcnRod2VzdGVybiBVbml2ZXJzaXR5LCBFdmFuc3RvbiwgSWxsaW5vaXMsCiAgVVNBLiA8aHR0cHM6Ly9DUkFOLlItcHJvamVjdC5vcmcvcGFja2FnZT1wc3ljaD4gVmVyc2lvbiA9IDEuNy44Lgo=