© 2018 Chris Culy, April 2018

Overview

This is one of a series of posts on using word vectors with small corpora. In this post I discuss ways to explore word similarities that don’t compare the model results with precompiled human judgments. In particular, I show how we can use “the closests of the closests” as well as the slope of similar items to get different perspectives on word similarities, both within a corpus and across corpora.

library(readr)
library(tidyverse)
library(scales)
library(reticulate)
prep = FALSE
# set up python functions
if (prep) {
  use_condaenv("textp") #this must have gensim installed
  
  psys <- import('sys')
  psys$path <- c(psys$path,getwd())
  
  svd_similarity <- import("similarities")
  
  get_most_similar <- function(text,words,n,win,dim,min_count) {
    x <- svd_similarity$get_most_similar(text,words,n=n,win=win,dim=dim,min_count=min_count)
    
    nr = length(x)
    what <- data.frame(matrix(unlist(x), nrow=nr, byrow=T),stringsAsFactors=FALSE)
    names(what) <- c('text','word','win','dim','min_count','item','rank','sim')
    
    return(what)
  }
}
# calculate/load  data that needs python
if (prep) {
  text <- "vfair"
  n <- 10
  min_count <- NULL
  words <- c("house","horse","awful","life","letters","act","road","listened","pardon","particulars","woke","abominable","doings","alas")
  
  vfair_sims <-
    get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=min_count)
  write_tsv(vfair_sims,"sims/vfair_sims.csv")
}
vfair_sims <- read_tsv("sims/vfair_sims.csv")
if (prep) {
  text <- "waywe"
  n <- 10
  min_count <- 1
  words <- c("house","horse")
  waywe_house_horse <-
    get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=min_count)
  write_tsv(waywe_house_horse,"sims/waywe_house_horse.csv")
}
#waywe_house_horse <- read_tsv("sims/waywe_house_horse.csv")
if (prep) {
  text <- "moby"
  n <- 10
  min_count <- 1
  words <- c("house","horse")
  moby_house_horse <-
    get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=min_count)
  write_tsv(moby_house_horse,"sims/moby_house_horse.csv")
}
#moby_house_horse <- read_tsv("sims/moby_house_horse.csv")
if (prep) {
  text <- "kidnapped"
  n <- 10
  min_count <- 1
  words <- c("house","horse")
  kidnapped_house_horse <-
    get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=min_count)
  write_tsv(kidnapped_house_horse,"sims/kidnapped_house_horse.csv")
}
#kidnapped_house_horse <- read_tsv("sims/kidnapped_house_horse.csv")
if (prep) {
  text <- "dracula"
  n <- 10
  words <- c("house","horse","life","awful")
  dracula_sims <-
    get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=NULL)
  write_tsv(dracula_sims,"sims/dracula_sims.csv")
}
dracula_sims <- read_tsv("sims/dracula_sims.csv")
if (prep) {
  text <- "jane"
  words <- c("house","horse","life","awful")
  jane_sims <- get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=NULL)
  write_tsv(jane_sims, "sims/jane_sims.csv")
}
jane_sims <- read_tsv("sims/jane_sims.csv")
if (prep) {
  text <- "threemen"
  words <- c("house","horse","life","awful")
  threemen_sims <- get_most_similar(text,words,n=n,win=NULL,dim=NULL,min_count=NULL)
  write_tsv(threemen_sims, "sims/threemen_sims.csv")
}
threemen_sims <- read_tsv("sims/threemen_sims.csv")
###############
#load simple data
cnames <- list('davidc', 'rbadge', 'dracula', 'moby', 'scarlet', 'emma', 'moonstone', 'frankenstein', 'pym', 'sybil', 'heartd', 'grubb', 'threemen', 'jane', 'nabbey', 'vfair', 'dorian', 'waywe', 'kidnapped', 'wuthering')
eval_texts <- list('sign4','jude','midmarch')
test_names <- list("ws353","ws353_similarity","ws353_relatedness","bruni_men")
counts <- Reduce(rbind,lapply(cnames, function(c){
  fname <- paste0("counts/",c,"-counts.csv")
  these_counts <- read_delim(fname, "\t", escape_double = FALSE, trim_ws = TRUE) %>%
    mutate(text=c, rank=row_number()) 
  
  #now add rank percentile [NOT count percentile, which isn't useful]
  len <- nrow(these_counts)
  these_counts %>% mutate(percentile=round(100*(1-rank/len), digits=2))
  
})) %>% select(text, everything())
best_SVD_sim_scores <- read_delim("testsets_parameters/SVD-sim_tests.csv", "\t", escape_double = FALSE, trim_ws = TRUE) %>%
  filter(!(text %in% eval_texts)) %>%
  group_by(testset,text) %>%
  filter(sF1 == max(sF1))

Background

In the previous post, Finding useful parameters and methods, I discussed finding the values for the parameters window size (win), number of dimensions (dim), and the minimum frequency of words to be included (min_count) that give the highest sF1 scores on four standard testsets of human similarity judgments. However, as mentioned at the end of that post, it is reasonable to question whether those testsets are relevant to evaluating these small corpora (recall that I am using 19th century novels as my corpora).

One problem with the testsets in this context is that they contain a lot of vocabulary that is not found in any single text. We saw that the best recall was still less than 75%, and with smaller texts it was not uncommon for recall to be less than 30%. The testsets then tell us little about the vocabulary that is in the texts.

A second problem with the testsets is that they reflect 21st century judgments about word usage, and we know that word usage (and meaning) has changed since the 19th century. In fact, there have been recent papers using word vectors to quantify those changes ([1], [2], [3]). In other words, the testsets can only tell us about 21st century interpretations of 19th century usage. While that might be interesting in its own right, it is not a way to discover how 19th century authors used words.

A third issue in using word vectors to explore word similarities is that different parameter settings give different similarities. Here is one example from Vanity Fair. I’ve chosen the word house, as the most common noun (lady is more common but it can also be a title, as in lady jane, since we have lowercased everything in the preprocessing.) I’ve fixed the window size at 5, and for each dimension in the parameters experiment, we see the 3 words that the model judges as being the most similar to house.

Throughout this post, as in the parameters experiment, I am using ppmi_svd vectors created using hyperwords [4], with similarities calculated using gensim [5]).

vfair_house_horse <- vfair_sims %>% filter(min_count==1,word=='house' | word=='horse')
vfair_house_horse %>% 
  filter(word=='house',win==5, rank<4) %>%
  ggplot() + theme_classic() + 
  labs(title="Closest 3 words to 'house' in Vanity Fair, with win=5,min_count=1") +
  scale_y_continuous(limits = c(0,1)) +
  geom_text(aes(dim,sim,label=item, color=factor(rank)), alpha=0.75, size=4, show.legend = FALSE)

We can immediately see two issues:

A third issue is that although win=4, dim=400 was the best scoring setting for the testsets, it gives the lowest similarity scores for house. In other words, a model that does well on the testsets will not necessarily give the highest similarity scores.

If we add in the closest words to horse, we see that similarity scores across words varies, even within the same settings. For example, the closest words to horse with dim=25 have a similarity of a little more than 0.75, while for house the scores are closer to 0.9.

vfair_house_horse %>% 
  filter(win==5, rank<4) %>%
  ggplot() + theme_classic() + 
  labs(title="Closest 3 words to 'house' and 'horse' in Vanity Fair\nwin=5, min_count=1") +
  scale_y_continuous(limits = c(0,1)) +
  scale_x_continuous(limits = c(0,450)) +
  geom_text(aes(dim,sim,label=item, color=factor(rank)), size=4, alpha=0.75, show.legend = FALSE) + 
  facet_wrap(~word, ncol=1)

Finally, when we look at a different text, Dracula, we see different words (not surprisingly), and different scores. There is also a slight difference in the trends of the scores across the dimensions.

dracula_house_horse <- dracula_sims %>% filter(min_count==1,word=='house' | word=='horse')
dracula_house_horse %>% 
  filter(win==5, rank<4) %>%
  ggplot() + theme_classic() + 
  labs(title="Closest 3 words to 'house' and 'horse' in Dracula\nwin=5, min_count=1") +
  scale_y_continuous(limits = c(0,1)) +
  scale_x_continuous(limits = c(0,450)) +
  geom_text(aes(dim,sim,label=item, color=factor(rank)), size=4, show.legend = FALSE) + 
  facet_wrap(~word, ncol=1)

rbind(vfair_house_horse,dracula_house_horse) %>%
  filter(win==5, rank==1) %>%
  ggplot() + theme_classic() + 
  labs(title="Trends for closest word to house, horse\nin Vanity Fair, Dracula, win=5, min_count=1") +
  scale_y_continuous(limits = c(0,1)) +
  geom_line(aes(dim,sim,color=text)) + 
  geom_point(aes(dim,sim,color=text, shape=text), size=2) +
  facet_wrap(~word, ncol=1)

There are thus three fundamental issues:

I will address each of these in turn.

Exploring variation across models

Here is a selection of words in Vanity Fair of different frequencies, chosen from the top 85 to 99 percentiles by rank. I’ll draw from these words in the examples that follow.

counts %>% filter(text=='vfair', percentile %in% seq(from=85,to=99,by=2)) %>% arrange(rank)

Closest of the closest

Given a word, e.g. life, one thing we do is look at the closest words to it across all the parameters, and find which of those has the highest similarity – the closest of the closest.

As an aside, we can note that for this sample, dim is always 25 (the smallest number of dimensions tested), min_count is usually, but not always 1, and win varies. This is in contrast to the results in the testset evaluations, where min_count=1 always gave the best sF1 scores across testsets, while dim and win varied.

vfair_sims_reduced <- vfair_sims %>% 
  filter(word !=  'house' & word != 'horse') %>%
  left_join(counts, by=c('text','word'='item')) %>%
  rename(text_rank=rank.y,sim_rank=rank.x)
vfair_sims_reduced %>% 
  group_by(word) %>%
  filter(sim==max(sim)) %>%
  select(word,percentile,item,sim,win,dim,min_count) %>%
  arrange(-sim, word, item)

The similarities range from just over 0.80 to little over 0.93, and there seems to be no strong relation between the rank percentile and the similarity of the closest of the closest.

vfair_sims_reduced %>% 
  group_by(word) %>%
  filter(sim==max(sim)) %>%
  ggplot() + theme_classic() +
  labs(title="Closest of the closest for selected words in Vanity Fair") +
  scale_x_continuous(limits = c(84,100)) +
  geom_text(aes(percentile,sim, label=paste0(word,":",item))) +
  geom_smooth(aes(percentile,sim), method='loess', color="orange")

If we want to explore a particular word with respect to other words, we can choose the model with the parameter settings for the closest of the closest and procede from there.

Slope

Let’s take a look at the 5 words closest to life across parameters, by their similarities. I’ll limit the similarities to > 0.66 for clarity.

vfair_sims_reduced %>% 
  filter(word=='life', sim_rank<6, sim>0.66) %>%
  ggplot() + theme_classic() +
  labs(title="5 closest words to 'life' in Vanity Fair (sim>0.66), by win and dim") +
  scale_x_continuous(limits = c(0.5,5.5)) +
  geom_line(aes(sim_rank,sim, color=factor(min_count))) +
  geom_text(aes(sim_rank,sim,label=item, color=factor(min_count)), show.legend = FALSE) +
  facet_wrap(win ~ dim, ncol = 2)

We see again here that the similarity scores vary quite a bit. We can also see that the range of similarity scores varies from the 1st to 5th closest word for a given set of parameters. While there are different ways we might use this information, one way is to look at the slope of the line going through the first and last words. By using the slope instead of the range, we abstract away from the absolute similarity values.

To find potentially interesting closest items, we can look for the model that has the steepest slope and the model that has the shallowest. (There are other things we could do as well, but this is a start.)

show_min_max_slopes <- function(info,wd,nclosest=5,tname=NULL) {
  dx = nclosest-1
  slopes <- info %>% 
    filter(word == wd, sim_rank <= nclosest) %>%
    group_by(text,win,dim,min_count) %>%
    mutate(slope=(max(sim)-min(sim))/dx) %>%
    ungroup()
  
  slopes_minmax <- slopes %>% 
    group_by(text) %>%
    filter(slope == max(slope) | slope == min(slope))
  
  if (is.null(tname)) {
    tname <- info$text[[1]]
  }
  
  t <- paste0("Steepest and shallowest slopes\nfor the ", 
             nclosest, ' words closest to "', wd, '" in ', tname)
  
  g <- slopes_minmax %>%
    ggplot() + theme_classic() + labs(title=t) + 
    scale_x_continuous(limits = c(0.5,nclosest+1.5), breaks=seq(1,nclosest)) +
    geom_line(aes(sim_rank,sim, color=factor(slope), alpha=0.75), show.legend = FALSE) +
    geom_text(aes(sim_rank,sim,label=item, color=factor(slope)), show.legend = FALSE) +
    geom_text(data=filter(slopes_minmax,sim_rank==nclosest),
              aes(nclosest+1,sim,
                  label=sprintf('(%0.5f)',slope), 
                  color=factor(slope)),
              show.legend = FALSE)
  g
}
show_min_max_slopes(vfair_sims_reduced,'life',nclosest = 5, tname="Vanity Fair")

Of course, there is nothing special about choosing the 5 closest items. We might choose just 2, or maybe 10.

show_min_max_slopes(vfair_sims_reduced,'life',nclosest = 2, tname="Vanity Fair")

show_min_max_slopes(vfair_sims_reduced,'life',nclosest = 10, tname="Vanity Fair")

As we can see, the closest words vary dramatically not only by the slope, but by how many we choose to focus on. The reason for the differences across the number of words chosen has two aspects. The first aspect is that different parameter settings give different similarities, as we’ve seen numerous times, and of course that’s how we can have a difference between the steepest and shallowest slope in the first place.

The second aspect has to do with the behavior of the similarity lines: they are not straight lines, but a series of segments, each of which may have a different slope. The slope of the whole series is the slope of a line from the first item to the last item, not taking into account the internal variations. So a series which may have a steep slope over the first few items might level out and have a shallower overall slope. Similarly, a series which starts out with a shallow slope may decline sharply, and end up with steeper slope overall.

We can see this illustrated in the following two charts. In each, I have used the subset of 9 parameter settings which rank first as the most similar word to life. The first chart shows the similarity lines and their slope over 5 words; the second chart shows them over 10 words.

Over 5 words, the sequence starting <first, station, squeezed> has the steepest slope (0.02191), but over 10 words the corresponding sequence has a slope of (0.01098), which is not the steepest slope. Rather, the sequence starting with <first, part, every> has the steepest slope over 10 words (0.01601), although its slope over 5 words was not the steepest, at (0.01692).

Although the sequence that has the shallowest slope is the same one over 5 and 10 words, starting with <first, days, delirium), this is a coincidence: it doesn’t have the shallowest slope over 3 words (not shown here).

vfair_life_first <- vfair_sims_reduced %>% 
  filter(word=='life', (item=='first' & sim_rank==1)) %>%
  select(word,win,dim,min_count) %>% unique() %>%
  left_join(vfair_sims_reduced)
compare_life_first <- function(nclosest) {
  dx = nclosest-1
  
  slopes <- vfair_life_first %>%
    filter(sim_rank <= nclosest) %>%
    group_by(win,dim,min_count) %>%
    mutate(slope=(max(sim)-min(sim))/dx) %>%
    ungroup()
  
  t <- paste("Comparison of slopes for 'life' with 'first' as closest,\nnclosest = ",nclosest)
 
  g <- slopes %>%
    ggplot() + theme_classic() + labs(title=t) + 
    scale_x_continuous(limits = c(0.5,nclosest+1.5), breaks=seq(1,nclosest)) +
    geom_line(aes(sim_rank,sim, color=factor(slope), alpha=0.75), show.legend = FALSE) +
    geom_text(aes(sim_rank,sim,label=item, color=factor(slope)), show.legend = FALSE) +
    geom_text(data=filter(slopes,sim_rank==nclosest),
              aes(nclosest+1,sim,
                  label=sprintf('(%0.5f)',slope), 
                  color=factor(slope)),
              show.legend = FALSE)
  g
}
compare_life_first(5) 

compare_life_first(10) 

Exploring variation within a single model

We can also explore multiple words within a single model using the notion of slope. For example, we might choose a large-ish window, since that should give more “semantic” results, according to the literature. We’ll pick a window of 10, and arbitrarily fix dim=400 and min_count=1.

show_model_slopes <- function(info,wds,nclosest = 5,tname=NULL) {
  dx <- nclosest-1
  slopes <- info %>% 
      filter(word %in% wds, sim_rank <= nclosest) %>%
      group_by(word,win,dim,min_count) %>%
      mutate(slope=(max(sim)-min(sim))/dx) %>%
      ungroup()
  
  if (is.null(tname)) {
    tname <- info$text[[1]]
  }
  
  wds_str <- paste(wds, collapse = ", ")
  t <- paste0("Slopes for the ", nclosest, ' words closest to\n', wds_str, '\nin ', tname)
  
  
  
  g <- slopes %>%
    ggplot() + theme_classic() + labs(title=t) + 
    scale_x_continuous(limits = c(0.5,nclosest+2.0), breaks=seq(1,nclosest)) +
    geom_line(aes(sim_rank,sim, color=word, alpha=0.75), show.legend = FALSE) +
    geom_text(aes(sim_rank,sim,label=item, color=word), show.legend = FALSE) +
    geom_text(data=filter(slopes,sim_rank==nclosest),
              aes(nclosest+1,sim,
                  label=sprintf('(%s: %0.5f)',word,slope), 
                  color=word),
              show.legend = FALSE)
  
  
  g
}
nclosest <- 4
w <- 10
d <- 400
mc <- 1
wds <- unique(vfair_sims_reduced$word)
info <- vfair_sims_reduced %>% 
  filter(win==w,dim==d,min_count==mc)
show_model_slopes(info, nclosest = nclosest, wds = wds, tname = paste0("Vanity Fair, with win=",w," dim=",d,", and min_count=",mc))

We might also try parameters that according to the literature should give more syntax-oriented results, namely with a small window. We’ll pick a window of 2, and arbitrarily fix dim=100 and min_count=1.

nclosest <- 4
w <- 2
d <- 100
mc <- 1
wds <- unique(vfair_sims_reduced$word)
info <- vfair_sims_reduced %>% 
  filter(win==w,dim==d,min_count==mc)
show_model_slopes(info, nclosest = nclosest, wds = wds, tname = paste0("Vanity Fair, with win=",w," dim=",d,", and min_count=",mc))

Exploring variation across corpora

The test data: awful

We can use awful as an example to compare words across corpora, one that is used in papers on word vectors and semantic change. We’ll use four texts, two from the mid 1800s and two from the late 1800s. This fits roughly with one timespan showing change as in ([2]). (Interestingly Emma, which is even earlier (1815), does not contain the word awful.) We expect that the two earlier books would use awful differently from the two later books.

  • Jane Eyre: 1847
  • Vanity Fair: 1847
  • Three Men in a Boat: 1889
  • Dracula: 1897
#using vfair,jane,dracula,threemen
awful_sims <- rbind(vfair_sims,dracula_sims,jane_sims,threemen_sims) %>%
  filter(word=="awful") %>%
  left_join(counts, by=c('text','word'='item')) %>%
  rename(text_rank=rank.y,sim_rank=rank.x)

The closests of the closests

Here we see that the closests of the closest vary across all the texts.

awful_sims %>% 
  group_by(text) %>%
  filter(sim==max(sim)) %>%
  arrange(-sim)

We can tally the number of models for which an item is the closest to awful. For brevity, I’ve limited this to items which occurs as the closest item at least 5 times. There are certainly things that deserve a closer look, like an showing up in 5 different models for Three Men in a Boat. However, we’ll keep moving.

awful_sims %>% 
  filter(sim_rank==1) %>%
  group_by(text,item) %>%
  summarize(n=n()) %>%
  filter(n>=5) %>%
  arrange(text,-n,item)

Are there any overlaps in the closest of the closest across texts? Just 4, which isn’t very many, and they all occur in Vanity Fair.

awful_sims %>% 
  filter(sim_rank==1) %>%
  group_by(item,text) %>%
  summarize(n=n()) %>%
  group_by(item) %>%
  summarize(ntexts=n()) %>%
  filter(ntexts>1) %>%
  inner_join(filter(awful_sims, sim_rank==1), by=c("item")) %>%
  select(item,text) %>% 
  unique() %>%
  arrange(item,text)

We can expand to, for example, the 5 closest.

awful5 <- awful_sims %>% 
  filter(sim_rank<=5) %>%
  group_by(item,text) %>%
  summarize(n=n()) %>%
  group_by(item) %>%
  summarize(ntexts=n()) %>%
  filter(ntexts>1) %>%
  inner_join(awful_sims, by=c("item")) %>%
  select(item,text) %>% 
  unique() 
t <- sprintf("%d items are in the closest 5 to 'awful'\nin more than one text", length(unique(awful5$item)))
awful5 %>%
  ggplot() + theme_classic() + labs(title=t) +
  scale_y_discrete(limits = sort(unique(awful5$item), decreasing = TRUE)) +
  geom_point(aes(text,item,color=text), show.legend = FALSE)

We can compare these texts using the settings from one of the studies in the literature. In [2] they use win=4 and dim=300. We can approximate those with win=5 and dim=200 (or dim=400). They use different min_count values for different corpora, but well above ours: ours are 1, 3, 5, 10, 20 while theirs are 100 and 500.

There is very little overlap across the texts (with similar results for dim=400 and even increasing the n-closest to 10).

nclosest = 5
d = 200
awful_approx <- awful_sims %>%
  filter(win==5,dim==d,min_count<5,sim_rank<=nclosest)
  
t = sprintf("Closest %d items with dim=%d,\nand min_count is 1 or 3", nclosest, d)
awful_approx %>%  
  ggplot() + theme_classic() + labs(title=t) +
  scale_y_discrete(limits = sort(unique(awful_approx$item), decreasing = TRUE)) +
  geom_point(aes(text,item,color=text), show.legend = FALSE)

Similarity lines

Since there is little overlap among the closest words across texts, we might use the slope technique to get a different idea of what’s going on.

show_awful_slopes <- function(info,nclosest = 5,tname=NULL) {
  dx <- nclosest-1
  slopes <- info %>% 
      filter(sim_rank <= nclosest) %>%
      group_by(text) %>%
      mutate(slope=(max(sim)-min(sim))/dx) %>%
      ungroup()
  
  if (is.null(tname)) {
    tname <- ""
  }
  
  t <- paste0("Slopes for the ", nclosest, ' words closest to awful ',tname)
  
  g <- slopes %>%
    ggplot() + theme_classic() + labs(title=t) + 
    scale_x_continuous(limits = c(0.5,nclosest+2.0), breaks=seq(1,nclosest)) +
    geom_line(aes(sim_rank,sim, color=text, alpha=0.75), show.legend = FALSE) +
    geom_text(aes(sim_rank,sim, label=item, color=text), show.legend = FALSE) +
    geom_text(data=filter(slopes,sim_rank==nclosest),
              aes(nclosest+1,sim,
                  label=sprintf('(%s: %0.5f)',text,slope), 
                  color=text),
              show.legend = FALSE)
  g
}
nclosest = 5
d = 200
awful_approx <- awful_sims %>%
  filter(win==5,dim == d, min_count==1) #,sim_rank<=nclosest)
  
t = sprintf("with win=5, dim=%d, and min_count=1\n", d)
show_awful_slopes(awful_approx, nclosest = nclosest, tname = t)

d = 400
awful_approx <- awful_sims %>%
  filter(win==5,dim == d, min_count==1)
  
t = sprintf("with win=5, dim=%d, and min_count=1\n", d)
show_awful_slopes(awful_approx, nclosest = nclosest, tname = t)

Not surprisingly, the closest words are different when we change the number of dimensions, though there is overlap, and in the case of threemen, the overlap (and the ordering) is exact.

As before, we can also find the steepest and shallowest slopes for awful for each text.

awful_sims %>%
  show_min_max_slopes(wd = 'awful',nclosest = 5, tname = "the 4 texts") +
  facet_wrap(~text, ncol=1)

On alignment

In work using word vectors to explore meaning shift across time, word vectors from different time slices are aligned to a common coordinate system ([1], [2], [3]). However, there are two significant issues with trying to align these small corpora, namely the large non-overlap of vocabulary across the texts and the distortion of distances.

In order to align two different vector space models, only their common vocabulary can be used (possibly just a subset, even). However, in the case of these small corpora, not only is their overlap relatively constrained, but we cannot be sure, a priori, that the non-shared words are not important for the vector of the word(s) we are interested in. Therefore, alignment is not an appropriate technique for comparing small corpora. For large corpora, the assumption is that all the important words will be in the shared vocabulary, and that is probably a reasonable assumption.

Shared (total) vocabulary across texts

e.g. ~ 49% of vfair is shared with jane while ~ 62% of jane is shared with vfair

txts = c("dracula","jane","threemen","vfair")
shared_vocab <- sapply(txts, function(t1) {
  t1_wds <- filter(counts,text==t1)
  
  x <- sapply(txts,function(t2) {
    t2_wds <- filter(counts,text==t2)
    
    info <- t2_wds %>% 
      filter(item %in% t1_wds$item)
    
    return( nrow(info)/nrow(t2_wds) )
    
    })
  return(x)
})
shared_vocab
           dracula      jane  threemen     vfair
dracula  1.0000000 0.6189812 0.4150134 0.6346381
jane     0.4581316 1.0000000 0.3449480 0.6157632
threemen 0.5709649 0.6411921 1.0000000 0.6864857
vfair    0.3745096 0.4909505 0.2944564 1.0000000

The second issue has to do with distance distortion. The methods for aligning two different vector models attempt to minimize (certain) differences in distances between word vectors across the original model and aligned model. While the differences are guaranteed to be as small as possible, they are not necessarily 0. With large corpora, the differences in distances may be negligible (though I am not aware of any discussion of this point), but given the large amount of variation across models with small corpora, it seems likely that differences in distances could be more relevant. The slope of similarity lines method used here avoids the issue of differences in distances since each model is viewed independently, with no alignment. Distance distortion in a different form is also theme in the visualization post

Discussion and Conclusion

One important point to make with all this variation is that there is no a priori reason to pick one set of parameter settings over another. Each one gives a different perspective on the corpus/corpora, and it is up to the analyst to delve deeper into these perspectives.

At the same time, the issues and approaches raised here are relevant for large corpora as well, especially for lower frequency words. Studies of particular phenomena should do some preliminary testing of the words of interest to see to what extent different parameter settings impact the results. As well, the two techniques used here, the closests of the closests, and the similarity slope, can be addtional tools to use in the analysis of large corpora.

Back to the introduction post

Other posts

References

[1] Vivek Kulkarni, Rami Al-Rfou, Bryan Perozzi, and Steven Skiena. 2014. Statistically significant detection of linguistic change. In Proc. 24th WWW Conf., pp. 625–635. International World Wide Web Conferences Steering Committee.

[2] William L. Hamilton, Jure Leskovec, and Dan Jurafsky. 2016. Diachronic word embeddings reveal historical laws of semantic change. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

[3] Terrence Szymanski. 2017. Temporal Word Analogies: Identifying Lexical Replacement with Diachronic Word Embeddings. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Short Papers), pp. 448–453.

[4] Hyperwords: https://bitbucket.org/omerlevy/hyperwords, published as Omer Levy, Yoav Goldberg, and Ido Dagan. 2015. Improving Distributional Similarity with Lessons Learned from Word Embeddings. Transactions of the Association for Computational Linguistics, vol. 3, pp. 211–225.

[5] Gensim: https://radimrehurek.com/gensim/, published as: Software Framework for Topic Modelling with Large Corpora. Radim Řehůřek and Petr Sojka. Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, pp. 45-50, 22 May 2010.

LS0tCnRpdGxlOiAiV29yZCB2ZWN0b3JzIHdpdGggc21hbGwgY29ycG9yYTo8YnI+RXhwbG9yaW5nIHNpbWlsYXJpdGllcyIKb3V0cHV0OiBodG1sX25vdGVib29rCmZpZ19jYXB0aW9uOiB5ZXMKLS0tCgojIyDCqSAyMDE4IENocmlzIEN1bHksIEFwcmlsIDIwMTgKIyMjIFtjaHJpc2N1bHkubmV0XShodHRwOi8vY2hyaXNjdWx5Lm5ldC8pCgoKIyMgT3ZlcnZpZXcKVGhpcyBpcyBvbmUgb2YgYSBbc2VyaWVzIG9mIHBvc3RzXSh3dmVjc19pbnRyby5odG1sKSBvbiB1c2luZyB3b3JkIHZlY3RvcnMgd2l0aCBzbWFsbCBjb3Jwb3JhLiBJbiB0aGlzIHBvc3QgSSBkaXNjdXNzIHdheXMgdG8gZXhwbG9yZSB3b3JkIHNpbWlsYXJpdGllcyB0aGF0IGRvbid0IGNvbXBhcmUgdGhlIG1vZGVsIHJlc3VsdHMgd2l0aCBwcmVjb21waWxlZCBodW1hbiBqdWRnbWVudHMuIEluIHBhcnRpY3VsYXIsIEkgc2hvdyBob3cgd2UgY2FuIHVzZSAidGhlIGNsb3Nlc3RzIG9mIHRoZSBjbG9zZXN0cyIgYXMgd2VsbCBhcyB0aGUgc2xvcGUgb2Ygc2ltaWxhciBpdGVtcyB0byBnZXQgZGlmZmVyZW50IHBlcnNwZWN0aXZlcyBvbiB3b3JkIHNpbWlsYXJpdGllcywgYm90aCB3aXRoaW4gYSBjb3JwdXMgYW5kIGFjcm9zcyBjb3Jwb3JhLgoKCmBgYHtyIG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkocmVhZHIpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHNjYWxlcykKbGlicmFyeShyZXRpY3VsYXRlKQpgYGAKCmBgYHtyfQpwcmVwID0gRkFMU0UKYGBgCgpgYGB7cn0KIyBzZXQgdXAgcHl0aG9uIGZ1bmN0aW9ucwppZiAocHJlcCkgewogIHVzZV9jb25kYWVudigidGV4dHAiKSAjdGhpcyBtdXN0IGhhdmUgZ2Vuc2ltIGluc3RhbGxlZAogIAogIHBzeXMgPC0gaW1wb3J0KCdzeXMnKQogIHBzeXMkcGF0aCA8LSBjKHBzeXMkcGF0aCxnZXR3ZCgpKQogIAogIHN2ZF9zaW1pbGFyaXR5IDwtIGltcG9ydCgic2ltaWxhcml0aWVzIikKICAKICBnZXRfbW9zdF9zaW1pbGFyIDwtIGZ1bmN0aW9uKHRleHQsd29yZHMsbix3aW4sZGltLG1pbl9jb3VudCkgewogICAgeCA8LSBzdmRfc2ltaWxhcml0eSRnZXRfbW9zdF9zaW1pbGFyKHRleHQsd29yZHMsbj1uLHdpbj13aW4sZGltPWRpbSxtaW5fY291bnQ9bWluX2NvdW50KQogICAgCiAgICBuciA9IGxlbmd0aCh4KQogICAgd2hhdCA8LSBkYXRhLmZyYW1lKG1hdHJpeCh1bmxpc3QoeCksIG5yb3c9bnIsIGJ5cm93PVQpLHN0cmluZ3NBc0ZhY3RvcnM9RkFMU0UpCiAgICBuYW1lcyh3aGF0KSA8LSBjKCd0ZXh0Jywnd29yZCcsJ3dpbicsJ2RpbScsJ21pbl9jb3VudCcsJ2l0ZW0nLCdyYW5rJywnc2ltJykKICAgIAogICAgcmV0dXJuKHdoYXQpCiAgfQp9CgpgYGAKCmBgYHtyIG1lc3NhZ2U9RkFMU0V9CiMgY2FsY3VsYXRlL2xvYWQgIGRhdGEgdGhhdCBuZWVkcyBweXRob24KCmlmIChwcmVwKSB7CiAgdGV4dCA8LSAidmZhaXIiCiAgbiA8LSAxMAogIG1pbl9jb3VudCA8LSBOVUxMCiAgd29yZHMgPC0gYygiaG91c2UiLCJob3JzZSIsImF3ZnVsIiwibGlmZSIsImxldHRlcnMiLCJhY3QiLCJyb2FkIiwibGlzdGVuZWQiLCJwYXJkb24iLCJwYXJ0aWN1bGFycyIsIndva2UiLCJhYm9taW5hYmxlIiwiZG9pbmdzIiwiYWxhcyIpCiAgCiAgdmZhaXJfc2ltcyA8LQogICAgZ2V0X21vc3Rfc2ltaWxhcih0ZXh0LHdvcmRzLG49bix3aW49TlVMTCxkaW09TlVMTCxtaW5fY291bnQ9bWluX2NvdW50KQogIHdyaXRlX3Rzdih2ZmFpcl9zaW1zLCJzaW1zL3ZmYWlyX3NpbXMuY3N2IikKfQp2ZmFpcl9zaW1zIDwtIHJlYWRfdHN2KCJzaW1zL3ZmYWlyX3NpbXMuY3N2IikKCgppZiAocHJlcCkgewogIHRleHQgPC0gIndheXdlIgogIG4gPC0gMTAKICBtaW5fY291bnQgPC0gMQogIHdvcmRzIDwtIGMoImhvdXNlIiwiaG9yc2UiKQoKICB3YXl3ZV9ob3VzZV9ob3JzZSA8LQogICAgZ2V0X21vc3Rfc2ltaWxhcih0ZXh0LHdvcmRzLG49bix3aW49TlVMTCxkaW09TlVMTCxtaW5fY291bnQ9bWluX2NvdW50KQogIHdyaXRlX3Rzdih3YXl3ZV9ob3VzZV9ob3JzZSwic2ltcy93YXl3ZV9ob3VzZV9ob3JzZS5jc3YiKQp9CiN3YXl3ZV9ob3VzZV9ob3JzZSA8LSByZWFkX3Rzdigic2ltcy93YXl3ZV9ob3VzZV9ob3JzZS5jc3YiKQoKCmlmIChwcmVwKSB7CiAgdGV4dCA8LSAibW9ieSIKICBuIDwtIDEwCiAgbWluX2NvdW50IDwtIDEKICB3b3JkcyA8LSBjKCJob3VzZSIsImhvcnNlIikKCiAgbW9ieV9ob3VzZV9ob3JzZSA8LQogICAgZ2V0X21vc3Rfc2ltaWxhcih0ZXh0LHdvcmRzLG49bix3aW49TlVMTCxkaW09TlVMTCxtaW5fY291bnQ9bWluX2NvdW50KQogIHdyaXRlX3Rzdihtb2J5X2hvdXNlX2hvcnNlLCJzaW1zL21vYnlfaG91c2VfaG9yc2UuY3N2IikKfQojbW9ieV9ob3VzZV9ob3JzZSA8LSByZWFkX3Rzdigic2ltcy9tb2J5X2hvdXNlX2hvcnNlLmNzdiIpCgoKaWYgKHByZXApIHsKICB0ZXh0IDwtICJraWRuYXBwZWQiCiAgbiA8LSAxMAogIG1pbl9jb3VudCA8LSAxCiAgd29yZHMgPC0gYygiaG91c2UiLCJob3JzZSIpCgogIGtpZG5hcHBlZF9ob3VzZV9ob3JzZSA8LQogICAgZ2V0X21vc3Rfc2ltaWxhcih0ZXh0LHdvcmRzLG49bix3aW49TlVMTCxkaW09TlVMTCxtaW5fY291bnQ9bWluX2NvdW50KQogIHdyaXRlX3RzdihraWRuYXBwZWRfaG91c2VfaG9yc2UsInNpbXMva2lkbmFwcGVkX2hvdXNlX2hvcnNlLmNzdiIpCn0KI2tpZG5hcHBlZF9ob3VzZV9ob3JzZSA8LSByZWFkX3Rzdigic2ltcy9raWRuYXBwZWRfaG91c2VfaG9yc2UuY3N2IikKCgppZiAocHJlcCkgewogIHRleHQgPC0gImRyYWN1bGEiCiAgbiA8LSAxMAogIHdvcmRzIDwtIGMoImhvdXNlIiwiaG9yc2UiLCJsaWZlIiwiYXdmdWwiKQoKICBkcmFjdWxhX3NpbXMgPC0KICAgIGdldF9tb3N0X3NpbWlsYXIodGV4dCx3b3JkcyxuPW4sd2luPU5VTEwsZGltPU5VTEwsbWluX2NvdW50PU5VTEwpCiAgd3JpdGVfdHN2KGRyYWN1bGFfc2ltcywic2ltcy9kcmFjdWxhX3NpbXMuY3N2IikKfQpkcmFjdWxhX3NpbXMgPC0gcmVhZF90c3YoInNpbXMvZHJhY3VsYV9zaW1zLmNzdiIpCgppZiAocHJlcCkgewogIHRleHQgPC0gImphbmUiCiAgd29yZHMgPC0gYygiaG91c2UiLCJob3JzZSIsImxpZmUiLCJhd2Z1bCIpCiAgamFuZV9zaW1zIDwtIGdldF9tb3N0X3NpbWlsYXIodGV4dCx3b3JkcyxuPW4sd2luPU5VTEwsZGltPU5VTEwsbWluX2NvdW50PU5VTEwpCiAgd3JpdGVfdHN2KGphbmVfc2ltcywgInNpbXMvamFuZV9zaW1zLmNzdiIpCn0KamFuZV9zaW1zIDwtIHJlYWRfdHN2KCJzaW1zL2phbmVfc2ltcy5jc3YiKQoKaWYgKHByZXApIHsKICB0ZXh0IDwtICJ0aHJlZW1lbiIKICB3b3JkcyA8LSBjKCJob3VzZSIsImhvcnNlIiwibGlmZSIsImF3ZnVsIikKICB0aHJlZW1lbl9zaW1zIDwtIGdldF9tb3N0X3NpbWlsYXIodGV4dCx3b3JkcyxuPW4sd2luPU5VTEwsZGltPU5VTEwsbWluX2NvdW50PU5VTEwpCiAgd3JpdGVfdHN2KHRocmVlbWVuX3NpbXMsICJzaW1zL3RocmVlbWVuX3NpbXMuY3N2IikKfQp0aHJlZW1lbl9zaW1zIDwtIHJlYWRfdHN2KCJzaW1zL3RocmVlbWVuX3NpbXMuY3N2IikKCgoKIyMjIyMjIyMjIyMjIyMjCgoKCmBgYAoKCmBgYHtyIG1lc3NhZ2U9RkFMU0V9CiNsb2FkIHNpbXBsZSBkYXRhCgpjbmFtZXMgPC0gbGlzdCgnZGF2aWRjJywgJ3JiYWRnZScsICdkcmFjdWxhJywgJ21vYnknLCAnc2NhcmxldCcsICdlbW1hJywgJ21vb25zdG9uZScsICdmcmFua2Vuc3RlaW4nLCAncHltJywgJ3N5YmlsJywgJ2hlYXJ0ZCcsICdncnViYicsICd0aHJlZW1lbicsICdqYW5lJywgJ25hYmJleScsICd2ZmFpcicsICdkb3JpYW4nLCAnd2F5d2UnLCAna2lkbmFwcGVkJywgJ3d1dGhlcmluZycpCgpldmFsX3RleHRzIDwtIGxpc3QoJ3NpZ240JywnanVkZScsJ21pZG1hcmNoJykKdGVzdF9uYW1lcyA8LSBsaXN0KCJ3czM1MyIsIndzMzUzX3NpbWlsYXJpdHkiLCJ3czM1M19yZWxhdGVkbmVzcyIsImJydW5pX21lbiIpCgpjb3VudHMgPC0gUmVkdWNlKHJiaW5kLGxhcHBseShjbmFtZXMsIGZ1bmN0aW9uKGMpewogIGZuYW1lIDwtIHBhc3RlMCgiY291bnRzLyIsYywiLWNvdW50cy5jc3YiKQogIHRoZXNlX2NvdW50cyA8LSByZWFkX2RlbGltKGZuYW1lLCAiXHQiLCBlc2NhcGVfZG91YmxlID0gRkFMU0UsIHRyaW1fd3MgPSBUUlVFKSAlPiUKICAgIG11dGF0ZSh0ZXh0PWMsIHJhbms9cm93X251bWJlcigpKSAKICAKICAjbm93IGFkZCByYW5rIHBlcmNlbnRpbGUgW05PVCBjb3VudCBwZXJjZW50aWxlLCB3aGljaCBpc24ndCB1c2VmdWxdCiAgbGVuIDwtIG5yb3codGhlc2VfY291bnRzKQogIHRoZXNlX2NvdW50cyAlPiUgbXV0YXRlKHBlcmNlbnRpbGU9cm91bmQoMTAwKigxLXJhbmsvbGVuKSwgZGlnaXRzPTIpKQogIAp9KSkgJT4lIHNlbGVjdCh0ZXh0LCBldmVyeXRoaW5nKCkpCgoKCmJlc3RfU1ZEX3NpbV9zY29yZXMgPC0gcmVhZF9kZWxpbSgidGVzdHNldHNfcGFyYW1ldGVycy9TVkQtc2ltX3Rlc3RzLmNzdiIsICJcdCIsIGVzY2FwZV9kb3VibGUgPSBGQUxTRSwgdHJpbV93cyA9IFRSVUUpICU+JQogIGZpbHRlcighKHRleHQgJWluJSBldmFsX3RleHRzKSkgJT4lCiAgZ3JvdXBfYnkodGVzdHNldCx0ZXh0KSAlPiUKICBmaWx0ZXIoc0YxID09IG1heChzRjEpKQoKYGBgCgojIyBCYWNrZ3JvdW5kCkluIHRoZSBwcmV2aW91cyBwb3N0LCBbRmluZGluZyB1c2VmdWwgcGFyYW1ldGVycyBhbmQgbWV0aG9kc10od3ZlY3NfdGVzdHNldHNfcGFyYW1ldGVycy5uYi5odG1sKSwgSSBkaXNjdXNzZWQgZmluZGluZyB0aGUgdmFsdWVzIGZvciB0aGUgcGFyYW1ldGVycyB3aW5kb3cgc2l6ZSAoX3dpbl8pLCBudW1iZXIgb2YgZGltZW5zaW9ucyAoX2RpbV8pLCBhbmQgdGhlIG1pbmltdW0gZnJlcXVlbmN5IG9mIHdvcmRzIHRvIGJlIGluY2x1ZGVkIChfbWluX2NvdW50XykgdGhhdCBnaXZlIHRoZSBoaWdoZXN0IHNGMSBzY29yZXMgb24gZm91ciBzdGFuZGFyZCB0ZXN0c2V0cyBvZiBodW1hbiBzaW1pbGFyaXR5IGp1ZGdtZW50cy4gSG93ZXZlciwgYXMgbWVudGlvbmVkIGF0IHRoZSBlbmQgb2YgdGhhdCBwb3N0LCBpdCBpcyByZWFzb25hYmxlIHRvIHF1ZXN0aW9uIHdoZXRoZXIgdGhvc2UgdGVzdHNldHMgYXJlIHJlbGV2YW50IHRvIGV2YWx1YXRpbmcgdGhlc2Ugc21hbGwgY29ycG9yYSAocmVjYWxsIHRoYXQgSSBhbSB1c2luZyAxOXRoIGNlbnR1cnkgbm92ZWxzIGFzIG15IGNvcnBvcmEpLiAKCk9uZSBwcm9ibGVtIHdpdGggdGhlIHRlc3RzZXRzIGluIHRoaXMgY29udGV4dCBpcyB0aGF0IHRoZXkgY29udGFpbiBhIGxvdCBvZiB2b2NhYnVsYXJ5IHRoYXQgaXMgbm90IGZvdW5kIGluIGFueSBzaW5nbGUgdGV4dC4gV2Ugc2F3IHRoYXQgdGhlIGJlc3QgcmVjYWxsIHdhcyBzdGlsbCBsZXNzIHRoYW4gNzUlLCBhbmQgd2l0aCBzbWFsbGVyIHRleHRzIGl0IHdhcyBub3QgdW5jb21tb24gZm9yIHJlY2FsbCB0byBiZSBsZXNzIHRoYW4gMzAlLiBUaGUgdGVzdHNldHMgdGhlbiB0ZWxsIHVzIGxpdHRsZSBhYm91dCB0aGUgdm9jYWJ1bGFyeSB0aGF0IF9pc18gaW4gdGhlIHRleHRzLgoKQSBzZWNvbmQgcHJvYmxlbSB3aXRoIHRoZSB0ZXN0c2V0cyBpcyB0aGF0IHRoZXkgcmVmbGVjdCAyMXN0IGNlbnR1cnkganVkZ21lbnRzIGFib3V0IHdvcmQgdXNhZ2UsIGFuZCB3ZSBrbm93IHRoYXQgd29yZCB1c2FnZSAoYW5kIG1lYW5pbmcpIGhhcyBjaGFuZ2VkIHNpbmNlIHRoZSAxOXRoIGNlbnR1cnkuIEluIGZhY3QsIHRoZXJlIGhhdmUgYmVlbiByZWNlbnQgcGFwZXJzIHVzaW5nIHdvcmQgdmVjdG9ycyB0byBxdWFudGlmeSB0aG9zZSBjaGFuZ2VzIChbWzFdXSgjcmVmMSksIFtbMl1dKCNyZWYyKSwgW1szXV0oI3JlZjMpKS4gSW4gb3RoZXIgd29yZHMsIHRoZSB0ZXN0c2V0cyBjYW4gb25seSB0ZWxsIHVzIGFib3V0IDIxc3QgY2VudHVyeSBpbnRlcnByZXRhdGlvbnMgb2YgMTl0aCBjZW50dXJ5IHVzYWdlLiBXaGlsZSB0aGF0IG1pZ2h0IGJlIGludGVyZXN0aW5nIGluIGl0cyBvd24gcmlnaHQsIGl0IGlzIG5vdCBhIHdheSB0byBkaXNjb3ZlciBob3cgMTl0aCBjZW50dXJ5IGF1dGhvcnMgdXNlZCB3b3Jkcy4KCkEgdGhpcmQgaXNzdWUgaW4gdXNpbmcgd29yZCB2ZWN0b3JzIHRvIGV4cGxvcmUgd29yZCBzaW1pbGFyaXRpZXMgaXMgdGhhdCBkaWZmZXJlbnQgcGFyYW1ldGVyIHNldHRpbmdzIGdpdmUgZGlmZmVyZW50IHNpbWlsYXJpdGllcy4gSGVyZSBpcyBvbmUgZXhhbXBsZSBmcm9tIF9WYW5pdHkgRmFpcl8uIEkndmUgY2hvc2VuIHRoZSB3b3JkIF9ob3VzZV8sIGFzIHRoZSBtb3N0IGNvbW1vbiBub3VuIChfbGFkeV8gaXMgbW9yZSBjb21tb24gYnV0IGl0IGNhbiBhbHNvIGJlIGEgdGl0bGUsIGFzIGluIF9sYWR5IGphbmVfLCBzaW5jZSB3ZSBoYXZlIGxvd2VyY2FzZWQgZXZlcnl0aGluZyBpbiB0aGUgcHJlcHJvY2Vzc2luZy4pIEkndmUgZml4ZWQgdGhlIHdpbmRvdyBzaXplIGF0IDUsIGFuZCBmb3IgZWFjaCBkaW1lbnNpb24gaW4gdGhlIFtwYXJhbWV0ZXJzIGV4cGVyaW1lbnRdKHd2ZWNzX3Rlc3RzZXRzX3BhcmFtZXRlcnMubmIuaHRtbCksIHdlIHNlZSB0aGUgMyB3b3JkcyB0aGF0IHRoZSBtb2RlbCBqdWRnZXMgYXMgYmVpbmcgdGhlIG1vc3Qgc2ltaWxhciB0byBfaG91c2VfLgoKVGhyb3VnaG91dCB0aGlzIHBvc3QsIGFzIGluIHRoZSBbcGFyYW1ldGVycyBleHBlcmltZW50XSh3dmVjc190ZXN0c2V0c19wYXJhbWV0ZXJzLm5iLmh0bWwpLCBJIGFtIHVzaW5nIHBwbWlfc3ZkIHZlY3RvcnMgY3JlYXRlZCB1c2luZyBoeXBlcndvcmRzIFtbNF1dKCNyZWY0KSwgd2l0aCBzaW1pbGFyaXRpZXMgY2FsY3VsYXRlZCB1c2luZyBnZW5zaW0gW1s1XV0oI3JlZjUpKS4KCmBgYHtyIGZpZy53aWR0aD02LCBmaWcuaGVpZ2h0PTZ9CnZmYWlyX2hvdXNlX2hvcnNlIDwtIHZmYWlyX3NpbXMgJT4lIGZpbHRlcihtaW5fY291bnQ9PTEsd29yZD09J2hvdXNlJyB8IHdvcmQ9PSdob3JzZScpCnZmYWlyX2hvdXNlX2hvcnNlICU+JSAKICBmaWx0ZXIod29yZD09J2hvdXNlJyx3aW49PTUsIHJhbms8NCkgJT4lCiAgZ2dwbG90KCkgKyB0aGVtZV9jbGFzc2ljKCkgKyAKICBsYWJzKHRpdGxlPSJDbG9zZXN0IDMgd29yZHMgdG8gJ2hvdXNlJyBpbiBWYW5pdHkgRmFpciwgd2l0aCB3aW49NSxtaW5fY291bnQ9MSIpICsKICBzY2FsZV95X2NvbnRpbnVvdXMobGltaXRzID0gYygwLDEpKSArCiAgZ2VvbV90ZXh0KGFlcyhkaW0sc2ltLGxhYmVsPWl0ZW0sIGNvbG9yPWZhY3RvcihyYW5rKSksIGFscGhhPTAuNzUsIHNpemU9NCwgc2hvdy5sZWdlbmQgPSBGQUxTRSkKCmBgYAoKV2UgY2FuIGltbWVkaWF0ZWx5IHNlZSB0d28gIGlzc3VlczoKCiogdGhlIG1vc3Qgc2ltaWxhciB3b3JkcyB2YXJ5IGZyb20gc2V0dGluZyB0byBzZXR0aW5nCiogdGhlIHNpbWlsYXJpdHkgKHNpbSkgdmFyaWVzIGZyb20gc2V0dGluZyB0byBzZXR0aW5nCgpBIHRoaXJkIGlzc3VlIGlzIHRoYXQgYWx0aG91Z2ggd2luPTQsIGRpbT00MDAgd2FzIHRoZSBiZXN0IHNjb3Jpbmcgc2V0dGluZyBmb3IgdGhlIHRlc3RzZXRzLCBpdCBnaXZlcyB0aGUgbG93ZXN0IHNpbWlsYXJpdHkgc2NvcmVzIGZvciBfaG91c2VfLiBJbiBvdGhlciB3b3JkcywgYSBtb2RlbCB0aGF0IGRvZXMgd2VsbCBvbiB0aGUgdGVzdHNldHMgd2lsbCBub3QgbmVjZXNzYXJpbHkgZ2l2ZSB0aGUgaGlnaGVzdCBzaW1pbGFyaXR5IHNjb3Jlcy4KCklmIHdlIGFkZCBpbiB0aGUgY2xvc2VzdCB3b3JkcyB0byBfaG9yc2VfLCB3ZSBzZWUgdGhhdCBzaW1pbGFyaXR5IHNjb3JlcyBhY3Jvc3Mgd29yZHMgdmFyaWVzLCBldmVuIHdpdGhpbiB0aGUgc2FtZSBzZXR0aW5ncy4gRm9yIGV4YW1wbGUsIHRoZSBjbG9zZXN0IHdvcmRzIHRvIF9ob3JzZV8gd2l0aCBkaW09MjUgaGF2ZSBhIHNpbWlsYXJpdHkgb2YgYSBsaXR0bGUgbW9yZSB0aGFuIDAuNzUsIHdoaWxlIGZvciBfaG91c2VfIHRoZSBzY29yZXMgYXJlIGNsb3NlciB0byAwLjkuCgpgYGB7ciBmaWcud2lkdGg9NiwgZmlnLmhlaWdodD05fQp2ZmFpcl9ob3VzZV9ob3JzZSAlPiUgCiAgZmlsdGVyKHdpbj09NSwgcmFuazw0KSAlPiUKICBnZ3Bsb3QoKSArIHRoZW1lX2NsYXNzaWMoKSArIAogIGxhYnModGl0bGU9IkNsb3Nlc3QgMyB3b3JkcyB0byAnaG91c2UnIGFuZCAnaG9yc2UnIGluIFZhbml0eSBGYWlyXG53aW49NSwgbWluX2NvdW50PTEiKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoMCwxKSkgKwogIHNjYWxlX3hfY29udGludW91cyhsaW1pdHMgPSBjKDAsNDUwKSkgKwogIGdlb21fdGV4dChhZXMoZGltLHNpbSxsYWJlbD1pdGVtLCBjb2xvcj1mYWN0b3IocmFuaykpLCBzaXplPTQsIGFscGhhPTAuNzUsIHNob3cubGVnZW5kID0gRkFMU0UpICsgCiAgZmFjZXRfd3JhcCh+d29yZCwgbmNvbD0xKQoKCmBgYAoKRmluYWxseSwgd2hlbiB3ZSBsb29rIGF0IGEgZGlmZmVyZW50IHRleHQsIF9EcmFjdWxhXywgd2Ugc2VlIGRpZmZlcmVudCB3b3JkcyAobm90IHN1cnByaXNpbmdseSksIGFuZCBkaWZmZXJlbnQgc2NvcmVzLiBUaGVyZSBpcyBhbHNvIGEgc2xpZ2h0IGRpZmZlcmVuY2UgaW4gdGhlIF90cmVuZHNfIG9mIHRoZSBzY29yZXMgYWNyb3NzIHRoZSBkaW1lbnNpb25zLgoKYGBge3IgZmlnLndpZHRoPTYsIGZpZy5oZWlnaHQ9OX0KZHJhY3VsYV9ob3VzZV9ob3JzZSA8LSBkcmFjdWxhX3NpbXMgJT4lIGZpbHRlcihtaW5fY291bnQ9PTEsd29yZD09J2hvdXNlJyB8IHdvcmQ9PSdob3JzZScpCgpkcmFjdWxhX2hvdXNlX2hvcnNlICU+JSAKICBmaWx0ZXIod2luPT01LCByYW5rPDQpICU+JQogIGdncGxvdCgpICsgdGhlbWVfY2xhc3NpYygpICsgCiAgbGFicyh0aXRsZT0iQ2xvc2VzdCAzIHdvcmRzIHRvICdob3VzZScgYW5kICdob3JzZScgaW4gRHJhY3VsYVxud2luPTUsIG1pbl9jb3VudD0xIikgKwogIHNjYWxlX3lfY29udGludW91cyhsaW1pdHMgPSBjKDAsMSkpICsKICBzY2FsZV94X2NvbnRpbnVvdXMobGltaXRzID0gYygwLDQ1MCkpICsKICBnZW9tX3RleHQoYWVzKGRpbSxzaW0sbGFiZWw9aXRlbSwgY29sb3I9ZmFjdG9yKHJhbmspKSwgc2l6ZT00LCBzaG93LmxlZ2VuZCA9IEZBTFNFKSArIAogIGZhY2V0X3dyYXAofndvcmQsIG5jb2w9MSkKYGBgCgoKYGBge3IgZmlnLndpZHRoPTYsIGZpZy5oZWlnaHQ9OH0KcmJpbmQodmZhaXJfaG91c2VfaG9yc2UsZHJhY3VsYV9ob3VzZV9ob3JzZSkgJT4lCiAgZmlsdGVyKHdpbj09NSwgcmFuaz09MSkgJT4lCiAgZ2dwbG90KCkgKyB0aGVtZV9jbGFzc2ljKCkgKyAKICBsYWJzKHRpdGxlPSJUcmVuZHMgZm9yIGNsb3Nlc3Qgd29yZCB0byBob3VzZSwgaG9yc2VcbmluIFZhbml0eSBGYWlyLCBEcmFjdWxhLCB3aW49NSwgbWluX2NvdW50PTEiKSArCiAgc2NhbGVfeV9jb250aW51b3VzKGxpbWl0cyA9IGMoMCwxKSkgKwogIGdlb21fbGluZShhZXMoZGltLHNpbSxjb2xvcj10ZXh0KSkgKyAKICBnZW9tX3BvaW50KGFlcyhkaW0sc2ltLGNvbG9yPXRleHQsIHNoYXBlPXRleHQpLCBzaXplPTIpICsKICBmYWNldF93cmFwKH53b3JkLCBuY29sPTEpCmBgYApUaGVyZSBhcmUgdGh1cyB0aHJlZSBmdW5kYW1lbnRhbCBpc3N1ZXM6CgoqIEhvdyB0byBkZWFsIHdpdGggdmFyaWF0aW9uIG9mIGEgc2luZ2xlIHdvcmQgYWNyb3NzIG11bHRpcGxlIG1vZGVscwoqIEhvdyB0byBkZWFsIHdpdGggdmFyaWF0aW9uIG9mIG11bHRpcGxlIHdvcmRzIHdpdGhpbiBhIHNpbmdsZSBtb2RlbAoqIEhvdyB0byBkZWFsIHdpdGggdmFyaWF0aW9uIGFjcm9zcyBjb3Jwb3JhCgpJIHdpbGwgYWRkcmVzcyBlYWNoIG9mIHRoZXNlIGluIHR1cm4uCgojIyBFeHBsb3JpbmcgdmFyaWF0aW9uIGFjcm9zcyBtb2RlbHMKCkhlcmUgaXMgYSBzZWxlY3Rpb24gb2Ygd29yZHMgaW4gX1Zhbml0eSBGYWlyXyBvZiBkaWZmZXJlbnQgZnJlcXVlbmNpZXMsIGNob3NlbiBmcm9tIHRoZSB0b3AgODUgdG8gOTkgcGVyY2VudGlsZXMgYnkgcmFuay4gSSdsbCBkcmF3IGZyb20gdGhlc2Ugd29yZHMgaW4gdGhlIGV4YW1wbGVzIHRoYXQgZm9sbG93LgoKYGBge3J9CmNvdW50cyAlPiUgZmlsdGVyKHRleHQ9PSd2ZmFpcicsIHBlcmNlbnRpbGUgJWluJSBzZXEoZnJvbT04NSx0bz05OSxieT0yKSkgJT4lIGFycmFuZ2UocmFuaykKYGBgCgojIyMgQ2xvc2VzdCBvZiB0aGUgY2xvc2VzdAoKR2l2ZW4gYSB3b3JkLCBlLmcuIF9saWZlXywgb25lIHRoaW5nIHdlIGRvIGlzIGxvb2sgYXQgdGhlIGNsb3Nlc3Qgd29yZHMgdG8gaXQgYWNyb3NzIGFsbCB0aGUgcGFyYW1ldGVycywgYW5kIGZpbmQgd2hpY2ggb2YgdGhvc2UgaGFzIHRoZSBoaWdoZXN0IHNpbWlsYXJpdHkgLS0gdGhlIGNsb3Nlc3Qgb2YgdGhlIGNsb3Nlc3QuIAoKQXMgYW4gYXNpZGUsIHdlIGNhbiBub3RlIHRoYXQgZm9yIHRoaXMgc2FtcGxlLCBkaW0gaXMgYWx3YXlzIDI1ICh0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGRpbWVuc2lvbnMgdGVzdGVkKSwgbWluX2NvdW50IGlzIHVzdWFsbHksIGJ1dCBub3QgYWx3YXlzIDEsIGFuZCB3aW4gdmFyaWVzLiBUaGlzIGlzIGluIGNvbnRyYXN0IHRvIHRoZSByZXN1bHRzIGluIHRoZSBbdGVzdHNldCBldmFsdWF0aW9uc10od3ZlY3NfdGVzdHNldHNfcGFyYW1ldGVycy5uYi5odG1sKSwgd2hlcmUgbWluX2NvdW50PTEgYWx3YXlzIGdhdmUgdGhlIGJlc3Qgc0YxIHNjb3JlcyBhY3Jvc3MgdGVzdHNldHMsIHdoaWxlIGRpbSBhbmQgd2luIHZhcmllZC4KCmBgYHtyfQp2ZmFpcl9zaW1zX3JlZHVjZWQgPC0gdmZhaXJfc2ltcyAlPiUgCiAgZmlsdGVyKHdvcmQgIT0gICdob3VzZScgJiB3b3JkICE9ICdob3JzZScpICU+JQogIGxlZnRfam9pbihjb3VudHMsIGJ5PWMoJ3RleHQnLCd3b3JkJz0naXRlbScpKSAlPiUKICByZW5hbWUodGV4dF9yYW5rPXJhbmsueSxzaW1fcmFuaz1yYW5rLngpCgoKdmZhaXJfc2ltc19yZWR1Y2VkICU+JSAKICBncm91cF9ieSh3b3JkKSAlPiUKICBmaWx0ZXIoc2ltPT1tYXgoc2ltKSkgJT4lCiAgc2VsZWN0KHdvcmQscGVyY2VudGlsZSxpdGVtLHNpbSx3aW4sZGltLG1pbl9jb3VudCkgJT4lCiAgYXJyYW5nZSgtc2ltLCB3b3JkLCBpdGVtKQoKYGBgCgpUaGUgc2ltaWxhcml0aWVzIHJhbmdlIGZyb20ganVzdCBvdmVyIDAuODAgdG8gbGl0dGxlIG92ZXIgMC45MywgYW5kIHRoZXJlIHNlZW1zIHRvIGJlIG5vIHN0cm9uZyByZWxhdGlvbiBiZXR3ZWVuIHRoZSByYW5rIHBlcmNlbnRpbGUgYW5kIHRoZSBzaW1pbGFyaXR5IG9mIHRoZSBjbG9zZXN0IG9mIHRoZSBjbG9zZXN0LgoKYGBge3IgZmlnLmhlaWdodD03fQp2ZmFpcl9zaW1zX3JlZHVjZWQgJT4lIAogIGdyb3VwX2J5KHdvcmQpICU+JQogIGZpbHRlcihzaW09PW1heChzaW0pKSAlPiUKICBnZ3Bsb3QoKSArIHRoZW1lX2NsYXNzaWMoKSArCiAgbGFicyh0aXRsZT0iQ2xvc2VzdCBvZiB0aGUgY2xvc2VzdCBmb3Igc2VsZWN0ZWQgd29yZHMgaW4gVmFuaXR5IEZhaXIiKSArCiAgc2NhbGVfeF9jb250aW51b3VzKGxpbWl0cyA9IGMoODQsMTAwKSkgKwogIGdlb21fdGV4dChhZXMocGVyY2VudGlsZSxzaW0sIGxhYmVsPXBhc3RlMCh3b3JkLCI6IixpdGVtKSkpICsKICBnZW9tX3Ntb290aChhZXMocGVyY2VudGlsZSxzaW0pLCBtZXRob2Q9J2xvZXNzJywgY29sb3I9Im9yYW5nZSIpCmBgYAoKSWYgd2Ugd2FudCB0byBleHBsb3JlIGEgcGFydGljdWxhciB3b3JkIHdpdGggcmVzcGVjdCB0byBvdGhlciB3b3Jkcywgd2UgY2FuIGNob29zZSB0aGUgbW9kZWwgd2l0aCB0aGUgcGFyYW1ldGVyIHNldHRpbmdzIGZvciB0aGUgY2xvc2VzdCBvZiB0aGUgY2xvc2VzdCBhbmQgcHJvY2VkZSBmcm9tIHRoZXJlLgoKIyMjIFNsb3BlCgpMZXQncyB0YWtlIGEgbG9vayBhdCB0aGUgNSB3b3JkcyBjbG9zZXN0IHRvIF9saWZlXyBhY3Jvc3MgcGFyYW1ldGVycywgYnkgdGhlaXIgc2ltaWxhcml0aWVzLiBJJ2xsIGxpbWl0IHRoZSBzaW1pbGFyaXRpZXMgdG8gPiAwLjY2IGZvciBjbGFyaXR5LgoKYGBge3IgZmlnLmhlaWdodD0xMiwgZmlnLndpZHRoPTh9CnZmYWlyX3NpbXNfcmVkdWNlZCAlPiUgCiAgZmlsdGVyKHdvcmQ9PSdsaWZlJywgc2ltX3Jhbms8Niwgc2ltPjAuNjYpICU+JQogIGdncGxvdCgpICsgdGhlbWVfY2xhc3NpYygpICsKICBsYWJzKHRpdGxlPSI1IGNsb3Nlc3Qgd29yZHMgdG8gJ2xpZmUnIGluIFZhbml0eSBGYWlyIChzaW0+MC42NiksIGJ5IHdpbiBhbmQgZGltIikgKwogIHNjYWxlX3hfY29udGludW91cyhsaW1pdHMgPSBjKDAuNSw1LjUpKSArCiAgZ2VvbV9saW5lKGFlcyhzaW1fcmFuayxzaW0sIGNvbG9yPWZhY3RvcihtaW5fY291bnQpKSkgKwogIGdlb21fdGV4dChhZXMoc2ltX3Jhbmssc2ltLGxhYmVsPWl0ZW0sIGNvbG9yPWZhY3RvcihtaW5fY291bnQpKSwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogIGZhY2V0X3dyYXAod2luIH4gZGltLCBuY29sID0gMikKYGBgCgpXZSBzZWUgYWdhaW4gaGVyZSB0aGF0IHRoZSBzaW1pbGFyaXR5IHNjb3JlcyB2YXJ5IHF1aXRlIGEgYml0LiBXZSBjYW4gYWxzbyBzZWUgdGhhdCB0aGUgX3JhbmdlXyBvZiBzaW1pbGFyaXR5IHNjb3JlcyB2YXJpZXMgZnJvbSB0aGUgMXN0IHRvIDV0aCBjbG9zZXN0IHdvcmQgZm9yIGEgZ2l2ZW4gc2V0IG9mIHBhcmFtZXRlcnMuIFdoaWxlIHRoZXJlIGFyZSBkaWZmZXJlbnQgd2F5cyB3ZSBtaWdodCB1c2UgdGhpcyBpbmZvcm1hdGlvbiwgb25lIHdheSBpcyB0byBsb29rIGF0IHRoZSBfc2xvcGVfIG9mIHRoZSBsaW5lIGdvaW5nIHRocm91Z2ggdGhlIGZpcnN0IGFuZCBsYXN0IHdvcmRzLiBCeSB1c2luZyB0aGUgc2xvcGUgaW5zdGVhZCBvZiB0aGUgcmFuZ2UsIHdlIGFic3RyYWN0IGF3YXkgZnJvbSB0aGUgYWJzb2x1dGUgc2ltaWxhcml0eSB2YWx1ZXMuCgpUbyBmaW5kIHBvdGVudGlhbGx5IGludGVyZXN0aW5nIGNsb3Nlc3QgaXRlbXMsIHdlIGNhbiBsb29rIGZvciB0aGUgbW9kZWwgdGhhdCBoYXMgdGhlIHN0ZWVwZXN0IHNsb3BlIGFuZCB0aGUgbW9kZWwgdGhhdCBoYXMgdGhlIHNoYWxsb3dlc3QuIChUaGVyZSBhcmUgb3RoZXIgdGhpbmdzIHdlIGNvdWxkIGRvIGFzIHdlbGwsIGJ1dCB0aGlzIGlzIGEgc3RhcnQuKQoKCmBgYHtyfQpzaG93X21pbl9tYXhfc2xvcGVzIDwtIGZ1bmN0aW9uKGluZm8sd2QsbmNsb3Nlc3Q9NSx0bmFtZT1OVUxMKSB7CiAgZHggPSBuY2xvc2VzdC0xCiAgc2xvcGVzIDwtIGluZm8gJT4lIAogICAgZmlsdGVyKHdvcmQgPT0gd2QsIHNpbV9yYW5rIDw9IG5jbG9zZXN0KSAlPiUKICAgIGdyb3VwX2J5KHRleHQsd2luLGRpbSxtaW5fY291bnQpICU+JQogICAgbXV0YXRlKHNsb3BlPShtYXgoc2ltKS1taW4oc2ltKSkvZHgpICU+JQogICAgdW5ncm91cCgpCiAgCiAgc2xvcGVzX21pbm1heCA8LSBzbG9wZXMgJT4lIAogICAgZ3JvdXBfYnkodGV4dCkgJT4lCiAgICBmaWx0ZXIoc2xvcGUgPT0gbWF4KHNsb3BlKSB8IHNsb3BlID09IG1pbihzbG9wZSkpCiAgCiAgaWYgKGlzLm51bGwodG5hbWUpKSB7CiAgICB0bmFtZSA8LSBpbmZvJHRleHRbWzFdXQogIH0KICAKICB0IDwtIHBhc3RlMCgiU3RlZXBlc3QgYW5kIHNoYWxsb3dlc3Qgc2xvcGVzXG5mb3IgdGhlICIsIAogICAgICAgICAgICAgbmNsb3Nlc3QsICcgd29yZHMgY2xvc2VzdCB0byAiJywgd2QsICciIGluICcsIHRuYW1lKQogIAogIGcgPC0gc2xvcGVzX21pbm1heCAlPiUKICAgIGdncGxvdCgpICsgdGhlbWVfY2xhc3NpYygpICsgbGFicyh0aXRsZT10KSArIAogICAgc2NhbGVfeF9jb250aW51b3VzKGxpbWl0cyA9IGMoMC41LG5jbG9zZXN0KzEuNSksIGJyZWFrcz1zZXEoMSxuY2xvc2VzdCkpICsKICAgIGdlb21fbGluZShhZXMoc2ltX3Jhbmssc2ltLCBjb2xvcj1mYWN0b3Ioc2xvcGUpLCBhbHBoYT0wLjc1KSwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogICAgZ2VvbV90ZXh0KGFlcyhzaW1fcmFuayxzaW0sbGFiZWw9aXRlbSwgY29sb3I9ZmFjdG9yKHNsb3BlKSksIHNob3cubGVnZW5kID0gRkFMU0UpICsKICAgIGdlb21fdGV4dChkYXRhPWZpbHRlcihzbG9wZXNfbWlubWF4LHNpbV9yYW5rPT1uY2xvc2VzdCksCiAgICAgICAgICAgICAgYWVzKG5jbG9zZXN0KzEsc2ltLAogICAgICAgICAgICAgICAgICBsYWJlbD1zcHJpbnRmKCcoJTAuNWYpJyxzbG9wZSksIAogICAgICAgICAgICAgICAgICBjb2xvcj1mYWN0b3Ioc2xvcGUpKSwKICAgICAgICAgICAgICBzaG93LmxlZ2VuZCA9IEZBTFNFKQogIGcKfQoKYGBgCgoKYGBge3J9CnNob3dfbWluX21heF9zbG9wZXModmZhaXJfc2ltc19yZWR1Y2VkLCdsaWZlJyxuY2xvc2VzdCA9IDUsIHRuYW1lPSJWYW5pdHkgRmFpciIpCmBgYAoKT2YgY291cnNlLCB0aGVyZSBpcyBub3RoaW5nIHNwZWNpYWwgYWJvdXQgY2hvb3NpbmcgdGhlIDUgY2xvc2VzdCBpdGVtcy4gV2UgbWlnaHQgY2hvb3NlIGp1c3QgMiwgb3IgbWF5YmUgMTAuCgpgYGB7cn0Kc2hvd19taW5fbWF4X3Nsb3Blcyh2ZmFpcl9zaW1zX3JlZHVjZWQsJ2xpZmUnLG5jbG9zZXN0ID0gMiwgdG5hbWU9IlZhbml0eSBGYWlyIikKYGBgCgpgYGB7ciBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD0xMH0Kc2hvd19taW5fbWF4X3Nsb3Blcyh2ZmFpcl9zaW1zX3JlZHVjZWQsJ2xpZmUnLG5jbG9zZXN0ID0gMTAsIHRuYW1lPSJWYW5pdHkgRmFpciIpCmBgYAoKQXMgd2UgY2FuIHNlZSwgdGhlIGNsb3Nlc3Qgd29yZHMgdmFyeSBkcmFtYXRpY2FsbHkgbm90IG9ubHkgYnkgdGhlIHNsb3BlLCBidXQgYnkgaG93IG1hbnkgd2UgY2hvb3NlIHRvIGZvY3VzIG9uLiBUaGUgcmVhc29uIGZvciB0aGUgZGlmZmVyZW5jZXMgYWNyb3NzIHRoZSBudW1iZXIgb2Ygd29yZHMgY2hvc2VuIGhhcyB0d28gYXNwZWN0cy4gVGhlIGZpcnN0IGFzcGVjdCBpcyB0aGF0IGRpZmZlcmVudCBwYXJhbWV0ZXIgc2V0dGluZ3MgZ2l2ZSBkaWZmZXJlbnQgc2ltaWxhcml0aWVzLCBhcyB3ZSd2ZSBzZWVuIG51bWVyb3VzIHRpbWVzLCBhbmQgb2YgY291cnNlIHRoYXQncyBob3cgd2UgY2FuIGhhdmUgYSBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIHN0ZWVwZXN0IGFuZCBzaGFsbG93ZXN0IHNsb3BlIGluIHRoZSBmaXJzdCBwbGFjZS4KClRoZSBzZWNvbmQgYXNwZWN0IGhhcyB0byBkbyB3aXRoIHRoZSBiZWhhdmlvciBvZiB0aGUgc2ltaWxhcml0eSBsaW5lczogdGhleSBhcmUgbm90IHN0cmFpZ2h0IGxpbmVzLCBidXQgYSBzZXJpZXMgb2Ygc2VnbWVudHMsIGVhY2ggb2Ygd2hpY2ggbWF5IGhhdmUgYSBkaWZmZXJlbnQgc2xvcGUuIFRoZSBzbG9wZSBvZiB0aGUgd2hvbGUgc2VyaWVzIGlzIHRoZSBzbG9wZSBvZiBhIGxpbmUgZnJvbSB0aGUgZmlyc3QgaXRlbSB0byB0aGUgbGFzdCBpdGVtLCBub3QgdGFraW5nIGludG8gYWNjb3VudCB0aGUgaW50ZXJuYWwgdmFyaWF0aW9ucy4gU28gYSBzZXJpZXMgd2hpY2ggbWF5IGhhdmUgYSBzdGVlcCBzbG9wZSBvdmVyIHRoZSBmaXJzdCBmZXcgaXRlbXMgbWlnaHQgbGV2ZWwgb3V0IGFuZCBoYXZlIGEgc2hhbGxvd2VyIG92ZXJhbGwgc2xvcGUuIFNpbWlsYXJseSwgYSBzZXJpZXMgd2hpY2ggc3RhcnRzIG91dCB3aXRoIGEgc2hhbGxvdyBzbG9wZSBtYXkgZGVjbGluZSBzaGFycGx5LCBhbmQgZW5kIHVwIHdpdGggc3RlZXBlciBzbG9wZSBvdmVyYWxsLgoKV2UgY2FuIHNlZSB0aGlzIGlsbHVzdHJhdGVkIGluIHRoZSBmb2xsb3dpbmcgdHdvIGNoYXJ0cy4gSW4gZWFjaCwgSSBoYXZlIHVzZWQgdGhlIHN1YnNldCBvZiA5IHBhcmFtZXRlciBzZXR0aW5ncyB3aGljaCByYW5rIF9maXJzdF8gYXMgdGhlIG1vc3Qgc2ltaWxhciB3b3JkIHRvIF9saWZlXy4gVGhlIGZpcnN0IGNoYXJ0IHNob3dzIHRoZSBzaW1pbGFyaXR5IGxpbmVzIGFuZCB0aGVpciBzbG9wZSBvdmVyIDUgd29yZHM7IHRoZSBzZWNvbmQgY2hhcnQgc2hvd3MgdGhlbSBvdmVyIDEwIHdvcmRzLgoKT3ZlciA1IHdvcmRzLCB0aGUgc2VxdWVuY2Ugc3RhcnRpbmcgPF9maXJzdF8sIF9zdGF0aW9uXywgX3NxdWVlemVkXz4gaGFzIHRoZSBzdGVlcGVzdCBzbG9wZSAoMC4wMjE5MSksIGJ1dCBvdmVyIDEwIHdvcmRzIHRoZSBjb3JyZXNwb25kaW5nIHNlcXVlbmNlIGhhcyBhIHNsb3BlIG9mICgwLjAxMDk4KSwgd2hpY2ggaXMgX25vdF8gdGhlIHN0ZWVwZXN0IHNsb3BlLiBSYXRoZXIsIHRoZSBzZXF1ZW5jZSBzdGFydGluZyB3aXRoIDxfZmlyc3RfLCBfcGFydF8sIF9ldmVyeV8+IGhhcyB0aGUgc3RlZXBlc3Qgc2xvcGUgb3ZlciAxMCB3b3JkcyAoMC4wMTYwMSksIGFsdGhvdWdoIGl0cyBzbG9wZSBvdmVyIDUgd29yZHMgd2FzIG5vdCB0aGUgc3RlZXBlc3QsIGF0ICgwLjAxNjkyKS4gCgpBbHRob3VnaCB0aGUgc2VxdWVuY2UgdGhhdCBoYXMgdGhlIHNoYWxsb3dlc3Qgc2xvcGUgaXMgdGhlIHNhbWUgb25lIG92ZXIgNSBhbmQgMTAgd29yZHMsIHN0YXJ0aW5nIHdpdGggPF9maXJzdF8sIF9kYXlzXywgX2RlbGlyaXVtXyksIHRoaXMgaXMgYSBjb2luY2lkZW5jZTogaXQgZG9lc24ndCBoYXZlIHRoZSBzaGFsbG93ZXN0IHNsb3BlIG92ZXIgMyB3b3JkcyAobm90IHNob3duIGhlcmUpLgoKYGBge3IgbWVzc2FnZT1GQUxTRX0KCnZmYWlyX2xpZmVfZmlyc3QgPC0gdmZhaXJfc2ltc19yZWR1Y2VkICU+JSAKICBmaWx0ZXIod29yZD09J2xpZmUnLCAoaXRlbT09J2ZpcnN0JyAmIHNpbV9yYW5rPT0xKSkgJT4lCiAgc2VsZWN0KHdvcmQsd2luLGRpbSxtaW5fY291bnQpICU+JSB1bmlxdWUoKSAlPiUKICBsZWZ0X2pvaW4odmZhaXJfc2ltc19yZWR1Y2VkKQoKY29tcGFyZV9saWZlX2ZpcnN0IDwtIGZ1bmN0aW9uKG5jbG9zZXN0KSB7CiAgZHggPSBuY2xvc2VzdC0xCiAgCiAgc2xvcGVzIDwtIHZmYWlyX2xpZmVfZmlyc3QgJT4lCiAgICBmaWx0ZXIoc2ltX3JhbmsgPD0gbmNsb3Nlc3QpICU+JQogICAgZ3JvdXBfYnkod2luLGRpbSxtaW5fY291bnQpICU+JQogICAgbXV0YXRlKHNsb3BlPShtYXgoc2ltKS1taW4oc2ltKSkvZHgpICU+JQogICAgdW5ncm91cCgpCiAgCiAgdCA8LSBwYXN0ZSgiQ29tcGFyaXNvbiBvZiBzbG9wZXMgZm9yICdsaWZlJyB3aXRoICdmaXJzdCcgYXMgY2xvc2VzdCxcbm5jbG9zZXN0ID0gIixuY2xvc2VzdCkKIAogIGcgPC0gc2xvcGVzICU+JQogICAgZ2dwbG90KCkgKyB0aGVtZV9jbGFzc2ljKCkgKyBsYWJzKHRpdGxlPXQpICsgCiAgICBzY2FsZV94X2NvbnRpbnVvdXMobGltaXRzID0gYygwLjUsbmNsb3Nlc3QrMS41KSwgYnJlYWtzPXNlcSgxLG5jbG9zZXN0KSkgKwogICAgZ2VvbV9saW5lKGFlcyhzaW1fcmFuayxzaW0sIGNvbG9yPWZhY3RvcihzbG9wZSksIGFscGhhPTAuNzUpLCBzaG93LmxlZ2VuZCA9IEZBTFNFKSArCiAgICBnZW9tX3RleHQoYWVzKHNpbV9yYW5rLHNpbSxsYWJlbD1pdGVtLCBjb2xvcj1mYWN0b3Ioc2xvcGUpKSwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogICAgZ2VvbV90ZXh0KGRhdGE9ZmlsdGVyKHNsb3BlcyxzaW1fcmFuaz09bmNsb3Nlc3QpLAogICAgICAgICAgICAgIGFlcyhuY2xvc2VzdCsxLHNpbSwKICAgICAgICAgICAgICAgICAgbGFiZWw9c3ByaW50ZignKCUwLjVmKScsc2xvcGUpLCAKICAgICAgICAgICAgICAgICAgY29sb3I9ZmFjdG9yKHNsb3BlKSksCiAgICAgICAgICAgICAgc2hvdy5sZWdlbmQgPSBGQUxTRSkKICBnCn0KYGBgCgpgYGB7ciBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD02fQpjb21wYXJlX2xpZmVfZmlyc3QoNSkgCmBgYAoKYGBge3IgZmlnLmhlaWdodD02LCBmaWcud2lkdGg9OX0KY29tcGFyZV9saWZlX2ZpcnN0KDEwKSAKYGBgCgojIyBFeHBsb3JpbmcgdmFyaWF0aW9uIHdpdGhpbiBhIHNpbmdsZSBtb2RlbAoKV2UgY2FuIGFsc28gZXhwbG9yZSBtdWx0aXBsZSB3b3JkcyB3aXRoaW4gYSBzaW5nbGUgbW9kZWwgdXNpbmcgdGhlIG5vdGlvbiBvZiBzbG9wZS4gRm9yIGV4YW1wbGUsIHdlIG1pZ2h0IGNob29zZSBhIGxhcmdlLWlzaCB3aW5kb3csIHNpbmNlIHRoYXQgc2hvdWxkIGdpdmUgbW9yZSAic2VtYW50aWMiIHJlc3VsdHMsIGFjY29yZGluZyB0byB0aGUgbGl0ZXJhdHVyZS4gV2UnbGwgcGljayBhIHdpbmRvdyBvZiAxMCwgYW5kIGFyYml0cmFyaWx5IGZpeCBkaW09NDAwIGFuZCBtaW5fY291bnQ9MS4KCmBgYHtyfQpzaG93X21vZGVsX3Nsb3BlcyA8LSBmdW5jdGlvbihpbmZvLHdkcyxuY2xvc2VzdCA9IDUsdG5hbWU9TlVMTCkgewogIGR4IDwtIG5jbG9zZXN0LTEKICBzbG9wZXMgPC0gaW5mbyAlPiUgCiAgICAgIGZpbHRlcih3b3JkICVpbiUgd2RzLCBzaW1fcmFuayA8PSBuY2xvc2VzdCkgJT4lCiAgICAgIGdyb3VwX2J5KHdvcmQsd2luLGRpbSxtaW5fY291bnQpICU+JQogICAgICBtdXRhdGUoc2xvcGU9KG1heChzaW0pLW1pbihzaW0pKS9keCkgJT4lCiAgICAgIHVuZ3JvdXAoKQogIAogIGlmIChpcy5udWxsKHRuYW1lKSkgewogICAgdG5hbWUgPC0gaW5mbyR0ZXh0W1sxXV0KICB9CiAgCiAgd2RzX3N0ciA8LSBwYXN0ZSh3ZHMsIGNvbGxhcHNlID0gIiwgIikKICB0IDwtIHBhc3RlMCgiU2xvcGVzIGZvciB0aGUgIiwgbmNsb3Nlc3QsICcgd29yZHMgY2xvc2VzdCB0b1xuJywgd2RzX3N0ciwgJ1xuaW4gJywgdG5hbWUpCiAgCiAgCiAgCiAgZyA8LSBzbG9wZXMgJT4lCiAgICBnZ3Bsb3QoKSArIHRoZW1lX2NsYXNzaWMoKSArIGxhYnModGl0bGU9dCkgKyAKICAgIHNjYWxlX3hfY29udGludW91cyhsaW1pdHMgPSBjKDAuNSxuY2xvc2VzdCsyLjApLCBicmVha3M9c2VxKDEsbmNsb3Nlc3QpKSArCiAgICBnZW9tX2xpbmUoYWVzKHNpbV9yYW5rLHNpbSwgY29sb3I9d29yZCwgYWxwaGE9MC43NSksIHNob3cubGVnZW5kID0gRkFMU0UpICsKICAgIGdlb21fdGV4dChhZXMoc2ltX3Jhbmssc2ltLGxhYmVsPWl0ZW0sIGNvbG9yPXdvcmQpLCBzaG93LmxlZ2VuZCA9IEZBTFNFKSArCiAgICBnZW9tX3RleHQoZGF0YT1maWx0ZXIoc2xvcGVzLHNpbV9yYW5rPT1uY2xvc2VzdCksCiAgICAgICAgICAgICAgYWVzKG5jbG9zZXN0KzEsc2ltLAogICAgICAgICAgICAgICAgICBsYWJlbD1zcHJpbnRmKCcoJXM6ICUwLjVmKScsd29yZCxzbG9wZSksIAogICAgICAgICAgICAgICAgICBjb2xvcj13b3JkKSwKICAgICAgICAgICAgICBzaG93LmxlZ2VuZCA9IEZBTFNFKQogIAogIAogIGcKCn0KCmBgYAoKYGBge3IgZmlnLndpZHRoPTgsIGZpZy5oZWlnaHQ9MTB9CgpuY2xvc2VzdCA8LSA0CncgPC0gMTAKZCA8LSA0MDAKbWMgPC0gMQp3ZHMgPC0gdW5pcXVlKHZmYWlyX3NpbXNfcmVkdWNlZCR3b3JkKQoKaW5mbyA8LSB2ZmFpcl9zaW1zX3JlZHVjZWQgJT4lIAogIGZpbHRlcih3aW49PXcsZGltPT1kLG1pbl9jb3VudD09bWMpCgpzaG93X21vZGVsX3Nsb3BlcyhpbmZvLCBuY2xvc2VzdCA9IG5jbG9zZXN0LCB3ZHMgPSB3ZHMsIHRuYW1lID0gcGFzdGUwKCJWYW5pdHkgRmFpciwgd2l0aCB3aW49Iix3LCIgZGltPSIsZCwiLCBhbmQgbWluX2NvdW50PSIsbWMpKQpgYGAKCldlIG1pZ2h0IGFsc28gdHJ5IHBhcmFtZXRlcnMgdGhhdCBhY2NvcmRpbmcgdG8gdGhlIGxpdGVyYXR1cmUgc2hvdWxkIGdpdmUgbW9yZSBzeW50YXgtb3JpZW50ZWQgcmVzdWx0cywgbmFtZWx5IHdpdGggYSBzbWFsbCB3aW5kb3cuIFdlJ2xsIHBpY2sgYSB3aW5kb3cgb2YgMiwgYW5kIGFyYml0cmFyaWx5IGZpeCBkaW09MTAwIGFuZCBtaW5fY291bnQ9MS4KCmBgYHtyIGZpZy53aWR0aD04LCBmaWcuaGVpZ2h0PTEwfQoKbmNsb3Nlc3QgPC0gNAp3IDwtIDIKZCA8LSAxMDAKbWMgPC0gMQp3ZHMgPC0gdW5pcXVlKHZmYWlyX3NpbXNfcmVkdWNlZCR3b3JkKQoKaW5mbyA8LSB2ZmFpcl9zaW1zX3JlZHVjZWQgJT4lIAogIGZpbHRlcih3aW49PXcsZGltPT1kLG1pbl9jb3VudD09bWMpCgpzaG93X21vZGVsX3Nsb3BlcyhpbmZvLCBuY2xvc2VzdCA9IG5jbG9zZXN0LCB3ZHMgPSB3ZHMsIHRuYW1lID0gcGFzdGUwKCJWYW5pdHkgRmFpciwgd2l0aCB3aW49Iix3LCIgZGltPSIsZCwiLCBhbmQgbWluX2NvdW50PSIsbWMpKQpgYGAKCiMjIEV4cGxvcmluZyB2YXJpYXRpb24gYWNyb3NzIGNvcnBvcmEKCiMjIyBUaGUgdGVzdCBkYXRhOiBfYXdmdWxfCldlIGNhbiB1c2UgX2F3ZnVsXyBhcyBhbiBleGFtcGxlIHRvIGNvbXBhcmUgd29yZHMgYWNyb3NzIGNvcnBvcmEsIG9uZSB0aGF0IGlzIHVzZWQgaW4gcGFwZXJzIG9uIHdvcmQgdmVjdG9ycyBhbmQgc2VtYW50aWMgY2hhbmdlLiBXZSdsbCB1c2UgZm91ciB0ZXh0cywgdHdvIGZyb20gdGhlIG1pZCAxODAwcyBhbmQgdHdvIGZyb20gdGhlIGxhdGUgMTgwMHMuIFRoaXMgZml0cyByb3VnaGx5IHdpdGggb25lIHRpbWVzcGFuIHNob3dpbmcgY2hhbmdlIGFzIGluIChbWzJdXSgjcmVmMikpLiAoSW50ZXJlc3RpbmdseSBfRW1tYV8sIHdoaWNoIGlzIGV2ZW4gZWFybGllciAoMTgxNSksIGRvZXMgbm90IGNvbnRhaW4gdGhlIHdvcmQgX2F3ZnVsXy4pIFdlIGV4cGVjdCB0aGF0IHRoZSB0d28gZWFybGllciBib29rcyB3b3VsZCB1c2UgX2F3ZnVsXyBkaWZmZXJlbnRseSBmcm9tIHRoZSB0d28gbGF0ZXIgYm9va3MuCgoqIEphbmUgRXlyZTogMTg0NwoqIFZhbml0eSBGYWlyOiAxODQ3CiogVGhyZWUgTWVuIGluIGEgQm9hdDogMTg4OQoqIERyYWN1bGE6IDE4OTcKCgpgYGB7cn0KI3VzaW5nIHZmYWlyLGphbmUsZHJhY3VsYSx0aHJlZW1lbgphd2Z1bF9zaW1zIDwtIHJiaW5kKHZmYWlyX3NpbXMsZHJhY3VsYV9zaW1zLGphbmVfc2ltcyx0aHJlZW1lbl9zaW1zKSAlPiUKICBmaWx0ZXIod29yZD09ImF3ZnVsIikgJT4lCiAgbGVmdF9qb2luKGNvdW50cywgYnk9YygndGV4dCcsJ3dvcmQnPSdpdGVtJykpICU+JQogIHJlbmFtZSh0ZXh0X3Jhbms9cmFuay55LHNpbV9yYW5rPXJhbmsueCkKYGBgCgojIyMgVGhlIGNsb3Nlc3RzIG9mIHRoZSBjbG9zZXN0cwpIZXJlIHdlIHNlZSB0aGF0IHRoZSBjbG9zZXN0cyBvZiB0aGUgY2xvc2VzdCB2YXJ5IGFjcm9zcyBhbGwgdGhlIHRleHRzLiAKYGBge3J9CmF3ZnVsX3NpbXMgJT4lIAogIGdyb3VwX2J5KHRleHQpICU+JQogIGZpbHRlcihzaW09PW1heChzaW0pKSAlPiUKICBhcnJhbmdlKC1zaW0pCgpgYGAKCldlIGNhbiB0YWxseSB0aGUgbnVtYmVyIG9mIG1vZGVscyBmb3Igd2hpY2ggYW4gaXRlbSBpcyB0aGUgY2xvc2VzdCB0byBfYXdmdWxfLiBGb3IgYnJldml0eSwgSSd2ZSBsaW1pdGVkIHRoaXMgdG8gaXRlbXMgd2hpY2ggb2NjdXJzIGFzIHRoZSBjbG9zZXN0IGl0ZW0gYXQgbGVhc3QgNSB0aW1lcy4gVGhlcmUgYXJlIGNlcnRhaW5seSB0aGluZ3MgdGhhdCBkZXNlcnZlIGEgY2xvc2VyIGxvb2ssIGxpa2UgX2FuXyBzaG93aW5nIHVwIGluIDUgZGlmZmVyZW50IG1vZGVscyBmb3IgX1RocmVlIE1lbiBpbiBhIEJvYXRfLiBIb3dldmVyLCB3ZSdsbCBrZWVwIG1vdmluZy4KCmBgYHtyfQphd2Z1bF9zaW1zICU+JSAKICBmaWx0ZXIoc2ltX3Jhbms9PTEpICU+JQogIGdyb3VwX2J5KHRleHQsaXRlbSkgJT4lCiAgc3VtbWFyaXplKG49bigpKSAlPiUKICBmaWx0ZXIobj49NSkgJT4lCiAgYXJyYW5nZSh0ZXh0LC1uLGl0ZW0pCmBgYAoKQXJlIHRoZXJlIGFueSBvdmVybGFwcyBpbiB0aGUgY2xvc2VzdCBvZiB0aGUgY2xvc2VzdCBhY3Jvc3MgdGV4dHM/IEp1c3QgNCwgd2hpY2ggaXNuJ3QgdmVyeSBtYW55LCBhbmQgdGhleSBhbGwgb2NjdXIgaW4gX1Zhbml0eSBGYWlyXy4KYGBge3J9CmF3ZnVsX3NpbXMgJT4lIAogIGZpbHRlcihzaW1fcmFuaz09MSkgJT4lCiAgZ3JvdXBfYnkoaXRlbSx0ZXh0KSAlPiUKICBzdW1tYXJpemUobj1uKCkpICU+JQogIGdyb3VwX2J5KGl0ZW0pICU+JQogIHN1bW1hcml6ZShudGV4dHM9bigpKSAlPiUKICBmaWx0ZXIobnRleHRzPjEpICU+JQogIGlubmVyX2pvaW4oZmlsdGVyKGF3ZnVsX3NpbXMsIHNpbV9yYW5rPT0xKSwgYnk9YygiaXRlbSIpKSAlPiUKICBzZWxlY3QoaXRlbSx0ZXh0KSAlPiUgCiAgdW5pcXVlKCkgJT4lCiAgYXJyYW5nZShpdGVtLHRleHQpCgpgYGAKCldlIGNhbiBleHBhbmQgdG8sIGZvciBleGFtcGxlLCB0aGUgNSBjbG9zZXN0LgpgYGB7ciBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD00fQphd2Z1bDUgPC0gYXdmdWxfc2ltcyAlPiUgCiAgZmlsdGVyKHNpbV9yYW5rPD01KSAlPiUKICBncm91cF9ieShpdGVtLHRleHQpICU+JQogIHN1bW1hcml6ZShuPW4oKSkgJT4lCiAgZ3JvdXBfYnkoaXRlbSkgJT4lCiAgc3VtbWFyaXplKG50ZXh0cz1uKCkpICU+JQogIGZpbHRlcihudGV4dHM+MSkgJT4lCiAgaW5uZXJfam9pbihhd2Z1bF9zaW1zLCBieT1jKCJpdGVtIikpICU+JQogIHNlbGVjdChpdGVtLHRleHQpICU+JSAKICB1bmlxdWUoKSAKCnQgPC0gc3ByaW50ZigiJWQgaXRlbXMgYXJlIGluIHRoZSBjbG9zZXN0IDUgdG8gJ2F3ZnVsJ1xuaW4gbW9yZSB0aGFuIG9uZSB0ZXh0IiwgbGVuZ3RoKHVuaXF1ZShhd2Z1bDUkaXRlbSkpKQoKYXdmdWw1ICU+JQogIGdncGxvdCgpICsgdGhlbWVfY2xhc3NpYygpICsgbGFicyh0aXRsZT10KSArCiAgc2NhbGVfeV9kaXNjcmV0ZShsaW1pdHMgPSBzb3J0KHVuaXF1ZShhd2Z1bDUkaXRlbSksIGRlY3JlYXNpbmcgPSBUUlVFKSkgKwogIGdlb21fcG9pbnQoYWVzKHRleHQsaXRlbSxjb2xvcj10ZXh0KSwgc2hvdy5sZWdlbmQgPSBGQUxTRSkKCgpgYGAKCldlIGNhbiBjb21wYXJlIHRoZXNlIHRleHRzIHVzaW5nIHRoZSBzZXR0aW5ncyBmcm9tIG9uZSBvZiB0aGUgc3R1ZGllcyBpbiB0aGUgbGl0ZXJhdHVyZS4gSW4gW1syXV0oI3JlZjIpIHRoZXkgdXNlIHdpbj00IGFuZCBkaW09MzAwLiBXZSBjYW4gYXBwcm94aW1hdGUgdGhvc2Ugd2l0aCB3aW49NSBhbmQgZGltPTIwMCAob3IgZGltPTQwMCkuIFRoZXkgdXNlIGRpZmZlcmVudCBtaW5fY291bnQgdmFsdWVzIGZvciBkaWZmZXJlbnQgY29ycG9yYSwgYnV0IHdlbGwgYWJvdmUgb3Vyczogb3VycyBhcmUgMSwgMywgNSwgMTAsIDIwIHdoaWxlIHRoZWlycyBhcmUgMTAwIGFuZCA1MDAuCgpUaGVyZSBpcyB2ZXJ5IGxpdHRsZSBvdmVybGFwIGFjcm9zcyB0aGUgdGV4dHMgKHdpdGggc2ltaWxhciByZXN1bHRzIGZvciBkaW09NDAwIGFuZCBldmVuIGluY3JlYXNpbmcgdGhlIG4tY2xvc2VzdCB0byAxMCkuCgpgYGB7ciBmaWcuaGVpZ2h0PTEwLCBmaWcud2lkdGg9NH0KbmNsb3Nlc3QgPSA1CmQgPSAyMDAKCmF3ZnVsX2FwcHJveCA8LSBhd2Z1bF9zaW1zICU+JQogIGZpbHRlcih3aW49PTUsZGltPT1kLG1pbl9jb3VudDw1LHNpbV9yYW5rPD1uY2xvc2VzdCkKICAKdCA9IHNwcmludGYoIkNsb3Nlc3QgJWQgaXRlbXMgd2l0aCBkaW09JWQsXG5hbmQgbWluX2NvdW50IGlzIDEgb3IgMyIsIG5jbG9zZXN0LCBkKQoKYXdmdWxfYXBwcm94ICU+JSAgCiAgZ2dwbG90KCkgKyB0aGVtZV9jbGFzc2ljKCkgKyBsYWJzKHRpdGxlPXQpICsKICBzY2FsZV95X2Rpc2NyZXRlKGxpbWl0cyA9IHNvcnQodW5pcXVlKGF3ZnVsX2FwcHJveCRpdGVtKSwgZGVjcmVhc2luZyA9IFRSVUUpKSArCiAgZ2VvbV9wb2ludChhZXModGV4dCxpdGVtLGNvbG9yPXRleHQpLCBzaG93LmxlZ2VuZCA9IEZBTFNFKQpgYGAKCiMjIyBTaW1pbGFyaXR5IGxpbmVzClNpbmNlIHRoZXJlIGlzIGxpdHRsZSBvdmVybGFwIGFtb25nIHRoZSBjbG9zZXN0IHdvcmRzIGFjcm9zcyB0ZXh0cywgd2UgbWlnaHQgdXNlIHRoZSBzbG9wZSB0ZWNobmlxdWUgdG8gZ2V0IGEgZGlmZmVyZW50IGlkZWEgb2Ygd2hhdCdzIGdvaW5nIG9uLgoKYGBge3IgZmlnLmhlaWdodD02LCBmaWcud2lkdGg9OH0KCnNob3dfYXdmdWxfc2xvcGVzIDwtIGZ1bmN0aW9uKGluZm8sbmNsb3Nlc3QgPSA1LHRuYW1lPU5VTEwpIHsKICBkeCA8LSBuY2xvc2VzdC0xCiAgc2xvcGVzIDwtIGluZm8gJT4lIAogICAgICBmaWx0ZXIoc2ltX3JhbmsgPD0gbmNsb3Nlc3QpICU+JQogICAgICBncm91cF9ieSh0ZXh0KSAlPiUKICAgICAgbXV0YXRlKHNsb3BlPShtYXgoc2ltKS1taW4oc2ltKSkvZHgpICU+JQogICAgICB1bmdyb3VwKCkKICAKICBpZiAoaXMubnVsbCh0bmFtZSkpIHsKICAgIHRuYW1lIDwtICIiCiAgfQogIAogIHQgPC0gcGFzdGUwKCJTbG9wZXMgZm9yIHRoZSAiLCBuY2xvc2VzdCwgJyB3b3JkcyBjbG9zZXN0IHRvIGF3ZnVsICcsdG5hbWUpCiAgCiAgZyA8LSBzbG9wZXMgJT4lCiAgICBnZ3Bsb3QoKSArIHRoZW1lX2NsYXNzaWMoKSArIGxhYnModGl0bGU9dCkgKyAKICAgIHNjYWxlX3hfY29udGludW91cyhsaW1pdHMgPSBjKDAuNSxuY2xvc2VzdCsyLjApLCBicmVha3M9c2VxKDEsbmNsb3Nlc3QpKSArCiAgICBnZW9tX2xpbmUoYWVzKHNpbV9yYW5rLHNpbSwgY29sb3I9dGV4dCwgYWxwaGE9MC43NSksIHNob3cubGVnZW5kID0gRkFMU0UpICsKICAgIGdlb21fdGV4dChhZXMoc2ltX3Jhbmssc2ltLCBsYWJlbD1pdGVtLCBjb2xvcj10ZXh0KSwgc2hvdy5sZWdlbmQgPSBGQUxTRSkgKwogICAgZ2VvbV90ZXh0KGRhdGE9ZmlsdGVyKHNsb3BlcyxzaW1fcmFuaz09bmNsb3Nlc3QpLAogICAgICAgICAgICAgIGFlcyhuY2xvc2VzdCsxLHNpbSwKICAgICAgICAgICAgICAgICAgbGFiZWw9c3ByaW50ZignKCVzOiAlMC41ZiknLHRleHQsc2xvcGUpLCAKICAgICAgICAgICAgICAgICAgY29sb3I9dGV4dCksCiAgICAgICAgICAgICAgc2hvdy5sZWdlbmQgPSBGQUxTRSkKICBnCn0KCm5jbG9zZXN0ID0gNQpkID0gMjAwCgphd2Z1bF9hcHByb3ggPC0gYXdmdWxfc2ltcyAlPiUKICBmaWx0ZXIod2luPT01LGRpbSA9PSBkLCBtaW5fY291bnQ9PTEpICMsc2ltX3Jhbms8PW5jbG9zZXN0KQogIAp0ID0gc3ByaW50Zigid2l0aCB3aW49NSwgZGltPSVkLCBhbmQgbWluX2NvdW50PTFcbiIsIGQpCgpzaG93X2F3ZnVsX3Nsb3Blcyhhd2Z1bF9hcHByb3gsIG5jbG9zZXN0ID0gbmNsb3Nlc3QsIHRuYW1lID0gdCkKCmBgYAoKYGBge3IgZmlnLmhlaWdodD02LCBmaWcud2lkdGg9OH0KZCA9IDQwMAoKYXdmdWxfYXBwcm94IDwtIGF3ZnVsX3NpbXMgJT4lCiAgZmlsdGVyKHdpbj09NSxkaW0gPT0gZCwgbWluX2NvdW50PT0xKQogIAp0ID0gc3ByaW50Zigid2l0aCB3aW49NSwgZGltPSVkLCBhbmQgbWluX2NvdW50PTFcbiIsIGQpCgpzaG93X2F3ZnVsX3Nsb3Blcyhhd2Z1bF9hcHByb3gsIG5jbG9zZXN0ID0gbmNsb3Nlc3QsIHRuYW1lID0gdCkKCmBgYAoKTm90IHN1cnByaXNpbmdseSwgdGhlIGNsb3Nlc3Qgd29yZHMgYXJlIGRpZmZlcmVudCB3aGVuIHdlIGNoYW5nZSB0aGUgbnVtYmVyIG9mIGRpbWVuc2lvbnMsIHRob3VnaCB0aGVyZSBpcyBvdmVybGFwLCBhbmQgaW4gdGhlIGNhc2Ugb2YgX3RocmVlbWVuXywgdGhlIG92ZXJsYXAgKGFuZCB0aGUgb3JkZXJpbmcpIGlzIGV4YWN0LgoKQXMgYmVmb3JlLCB3ZSBjYW4gYWxzbyBmaW5kIHRoZSBzdGVlcGVzdCBhbmQgc2hhbGxvd2VzdCBzbG9wZXMgZm9yIF9hd2Z1bF8gZm9yIGVhY2ggdGV4dC4KCmBgYHtyIGZpZy5oZWlnaHQ9MTMsIGZpZy53aWR0aD04fQphd2Z1bF9zaW1zICU+JQogIHNob3dfbWluX21heF9zbG9wZXMod2QgPSAnYXdmdWwnLG5jbG9zZXN0ID0gNSwgdG5hbWUgPSAidGhlIDQgdGV4dHMiKSArCiAgZmFjZXRfd3JhcCh+dGV4dCwgbmNvbD0xKQpgYGAKCgojIyMgT24gYWxpZ25tZW50CgpJbiB3b3JrIHVzaW5nIHdvcmQgdmVjdG9ycyB0byBleHBsb3JlIG1lYW5pbmcgc2hpZnQgYWNyb3NzIHRpbWUsIHdvcmQgdmVjdG9ycyBmcm9tIGRpZmZlcmVudCB0aW1lIHNsaWNlcyBhcmUgX2FsaWduZWRfIHRvIGEgY29tbW9uIGNvb3JkaW5hdGUgc3lzdGVtIChbWzFdXSgjcmVmMSksIFtbMl1dKCNyZWYyKSwgW1szXV0oI3JlZjMpKS4gSG93ZXZlciwgdGhlcmUgYXJlIHR3byBzaWduaWZpY2FudCBpc3N1ZXMgd2l0aCB0cnlpbmcgdG8gYWxpZ24gdGhlc2Ugc21hbGwgY29ycG9yYSwgbmFtZWx5IHRoZSBsYXJnZSBub24tb3ZlcmxhcCBvZiB2b2NhYnVsYXJ5IGFjcm9zcyB0aGUgdGV4dHMgYW5kIHRoZSBkaXN0b3J0aW9uIG9mIGRpc3RhbmNlcy4KCkluIG9yZGVyIHRvIGFsaWduIHR3byBkaWZmZXJlbnQgdmVjdG9yIHNwYWNlIG1vZGVscywgb25seSB0aGVpciBjb21tb24gdm9jYWJ1bGFyeSBjYW4gYmUgdXNlZCAocG9zc2libHkganVzdCBhIHN1YnNldCwgZXZlbikuIEhvd2V2ZXIsIGluIHRoZSBjYXNlIG9mIHRoZXNlIHNtYWxsIGNvcnBvcmEsIG5vdCBvbmx5IGlzIHRoZWlyIG92ZXJsYXAgcmVsYXRpdmVseSBjb25zdHJhaW5lZCwgYnV0IHdlIGNhbm5vdCBiZSBzdXJlLCBhIHByaW9yaSwgdGhhdCB0aGUgbm9uLXNoYXJlZCB3b3JkcyBhcmUgbm90IGltcG9ydGFudCBmb3IgdGhlIHZlY3RvciBvZiB0aGUgd29yZChzKSB3ZSBhcmUgaW50ZXJlc3RlZCBpbi4gVGhlcmVmb3JlLCBhbGlnbm1lbnQgaXMgbm90IGFuIGFwcHJvcHJpYXRlIHRlY2huaXF1ZSBmb3IgY29tcGFyaW5nIHNtYWxsIGNvcnBvcmEuIEZvciBsYXJnZSBjb3Jwb3JhLCB0aGUgX2Fzc3VtcHRpb25fIGlzIHRoYXQgYWxsIHRoZSBpbXBvcnRhbnQgd29yZHMgd2lsbCBiZSBpbiB0aGUgc2hhcmVkIHZvY2FidWxhcnksIGFuZCB0aGF0IGlzIHByb2JhYmx5IGEgcmVhc29uYWJsZSBhc3N1bXB0aW9uLiAKCiMjIyMgU2hhcmVkICh0b3RhbCkgdm9jYWJ1bGFyeSBhY3Jvc3MgdGV4dHMKZS5nLiB+IDQ5JSBvZiAqKnZmYWlyKiogaXMgc2hhcmVkIHdpdGggKipqYW5lKiogd2hpbGUgfiA2MiUgb2YgKipqYW5lKiogaXMgc2hhcmVkIHdpdGggKip2ZmFpcioqCgpgYGB7cn0KdHh0cyA9IGMoImRyYWN1bGEiLCJqYW5lIiwidGhyZWVtZW4iLCJ2ZmFpciIpCgpzaGFyZWRfdm9jYWIgPC0gc2FwcGx5KHR4dHMsIGZ1bmN0aW9uKHQxKSB7CiAgdDFfd2RzIDwtIGZpbHRlcihjb3VudHMsdGV4dD09dDEpCiAgCiAgeCA8LSBzYXBwbHkodHh0cyxmdW5jdGlvbih0MikgewogICAgdDJfd2RzIDwtIGZpbHRlcihjb3VudHMsdGV4dD09dDIpCiAgICAKICAgIGluZm8gPC0gdDJfd2RzICU+JSAKICAgICAgZmlsdGVyKGl0ZW0gJWluJSB0MV93ZHMkaXRlbSkKICAgIAogICAgcmV0dXJuKCBucm93KGluZm8pL25yb3codDJfd2RzKSApCiAgICAKICAgIH0pCiAgcmV0dXJuKHgpCn0pCgpzaGFyZWRfdm9jYWIKYGBgCgpUaGUgc2Vjb25kIGlzc3VlIGhhcyB0byBkbyB3aXRoIGRpc3RhbmNlIGRpc3RvcnRpb24uIFRoZSBtZXRob2RzIGZvciBhbGlnbmluZyB0d28gZGlmZmVyZW50IHZlY3RvciBtb2RlbHMgYXR0ZW1wdCB0byBtaW5pbWl6ZSAoY2VydGFpbikgZGlmZmVyZW5jZXMgaW4gZGlzdGFuY2VzIGJldHdlZW4gd29yZCB2ZWN0b3JzIGFjcm9zcyB0aGUgb3JpZ2luYWwgbW9kZWwgYW5kIGFsaWduZWQgbW9kZWwuIFdoaWxlIHRoZSBkaWZmZXJlbmNlcyBhcmUgZ3VhcmFudGVlZCB0byBiZSBhcyBzbWFsbCBhcyBwb3NzaWJsZSwgdGhleSBhcmUgbm90IG5lY2Vzc2FyaWx5IDAuIFdpdGggbGFyZ2UgY29ycG9yYSwgdGhlIGRpZmZlcmVuY2VzIGluIGRpc3RhbmNlcyBtYXkgYmUgbmVnbGlnaWJsZSAodGhvdWdoIEkgYW0gbm90IGF3YXJlIG9mIGFueSBkaXNjdXNzaW9uIG9mIHRoaXMgcG9pbnQpLCBidXQgZ2l2ZW4gdGhlIGxhcmdlIGFtb3VudCBvZiB2YXJpYXRpb24gYWNyb3NzIG1vZGVscyB3aXRoIHNtYWxsIGNvcnBvcmEsIGl0IHNlZW1zIGxpa2VseSB0aGF0IGRpZmZlcmVuY2VzIGluIGRpc3RhbmNlcyBjb3VsZCBiZSBtb3JlIHJlbGV2YW50LiBUaGUgc2xvcGUgb2Ygc2ltaWxhcml0eSBsaW5lcyBtZXRob2QgdXNlZCBoZXJlIGF2b2lkcyB0aGUgaXNzdWUgb2YgZGlmZmVyZW5jZXMgaW4gZGlzdGFuY2VzIHNpbmNlIGVhY2ggbW9kZWwgaXMgdmlld2VkIGluZGVwZW5kZW50bHksIHdpdGggbm8gYWxpZ25tZW50LiBEaXN0YW5jZSBkaXN0b3J0aW9uIGluIGEgZGlmZmVyZW50IGZvcm0gaXMgYWxzbyB0aGVtZSBpbiB0aGUgW3Zpc3VhbGl6YXRpb24gcG9zdF0od3ZlY3NfdmlzdWFsaXphdGlvbi5odG1sKQoKIyMgRGlzY3Vzc2lvbiBhbmQgQ29uY2x1c2lvbgoKT25lIGltcG9ydGFudCBwb2ludCB0byBtYWtlIHdpdGggYWxsIHRoaXMgdmFyaWF0aW9uIGlzIHRoYXQgdGhlcmUgaXMgbm8gYSBwcmlvcmkgcmVhc29uIHRvIHBpY2sgb25lIHNldCBvZiBwYXJhbWV0ZXIgc2V0dGluZ3Mgb3ZlciBhbm90aGVyLiBFYWNoIG9uZSBnaXZlcyBhIGRpZmZlcmVudCBfcGVyc3BlY3RpdmVfIG9uIHRoZSBjb3JwdXMvY29ycG9yYSwgYW5kIGl0IGlzIHVwIHRvIHRoZSBhbmFseXN0IHRvIGRlbHZlIGRlZXBlciBpbnRvIHRoZXNlIHBlcnNwZWN0aXZlcy4KCkF0IHRoZSBzYW1lIHRpbWUsIHRoZSBpc3N1ZXMgYW5kIGFwcHJvYWNoZXMgcmFpc2VkIGhlcmUgYXJlIHJlbGV2YW50IGZvciBsYXJnZSBjb3Jwb3JhIGFzIHdlbGwsIGVzcGVjaWFsbHkgZm9yIGxvd2VyIGZyZXF1ZW5jeSB3b3Jkcy4gU3R1ZGllcyBvZiBwYXJ0aWN1bGFyIHBoZW5vbWVuYSBzaG91bGQgZG8gc29tZSBwcmVsaW1pbmFyeSB0ZXN0aW5nIG9mIHRoZSB3b3JkcyBvZiBpbnRlcmVzdCB0byBzZWUgdG8gd2hhdCBleHRlbnQgZGlmZmVyZW50IHBhcmFtZXRlciBzZXR0aW5ncyBpbXBhY3QgdGhlIHJlc3VsdHMuIEFzIHdlbGwsIHRoZSB0d28gdGVjaG5pcXVlcyB1c2VkIGhlcmUsIHRoZSBjbG9zZXN0cyBvZiB0aGUgY2xvc2VzdHMsIGFuZCB0aGUgc2ltaWxhcml0eSBzbG9wZSwgY2FuIGJlIGFkZHRpb25hbCB0b29scyB0byB1c2UgaW4gdGhlIGFuYWx5c2lzIG9mIGxhcmdlIGNvcnBvcmEuCgpbQmFjayB0byB0aGUgaW50cm9kdWN0aW9uIHBvc3RdKHd2ZWNzX2ludHJvLmh0bWwpCgpPdGhlciBwb3N0cwoKKiBbU3RhYmlsaXppbmcgcmFuZG9tbmVzc10od3ZlY3NfcmFuZG9tX2ZpeC5odG1sKQoqIFtBIG5ldyBtZWFzdXJlIGZvciBldmFsdWF0aW9uXSh3dmVjc19ldmFsdWF0aW9uX21lYXN1cmUuaHRtbCkKKiBbRmluZGluZyB1c2VmdWwgcGFyYW1ldGVycyBhbmQgbWV0aG9kc10od3ZlY3NfdGVzdHNldHNfcGFyYW1ldGVycy5uYi5odG1sKQoqIFtWaXN1YWxpemluZyB3b3JkIHZlY3RvcnNdKHd2ZWNzX3Zpc3VhbGl6YXRpb24uaHRtbCkKCiMjIFJlZmVyZW5jZXMKCjxzcGFuIGlkPSJyZWYxIj5bMV08L3NwYW4+IFZpdmVrIEt1bGthcm5pLCBSYW1pIEFsLVJmb3UsIEJyeWFuIFBlcm96emksIGFuZCBTdGV2ZW4gU2tpZW5hLiAyMDE0LiBTdGF0aXN0aWNhbGx5IHNpZ25pZmljYW50IGRldGVjdGlvbiBvZiBsaW5ndWlzdGljIGNoYW5nZS4gSW4gUHJvYy4gMjR0aCBXV1cgQ29uZi4sIHBwLiA2MjXigJM2MzUuIEludGVybmF0aW9uYWwgV29ybGQgV2lkZSBXZWIgQ29uZmVyZW5jZXMgU3RlZXJpbmcgQ29tbWl0dGVlLgoKPHNwYW4gaWQ9InJlZjIiPlsyXTwvc3Bhbj4gV2lsbGlhbSBMLiBIYW1pbHRvbiwgSnVyZSBMZXNrb3ZlYywgYW5kIERhbiBKdXJhZnNreS4gMjAxNi4gRGlhY2hyb25pYyB3b3JkIGVtYmVkZGluZ3MgcmV2ZWFsIGhpc3RvcmljYWwgbGF3cyBvZiBzZW1hbnRpYyBjaGFuZ2UuIEluIFByb2NlZWRpbmdzIG9mIHRoZSA1NHRoIEFubnVhbCBNZWV0aW5nIG9mIHRoZSBBc3NvY2lhdGlvbiBmb3IgQ29tcHV0YXRpb25hbCBMaW5ndWlzdGljcyAoVm9sdW1lIDE6IExvbmcgUGFwZXJzKS4KCjxzcGFuIGlkPSJyZWYzIj5bM108L3NwYW4+IFRlcnJlbmNlIFN6eW1hbnNraS4gMjAxNy4gVGVtcG9yYWwgV29yZCBBbmFsb2dpZXM6IElkZW50aWZ5aW5nIExleGljYWwgUmVwbGFjZW1lbnQgd2l0aCBEaWFjaHJvbmljIFdvcmQgRW1iZWRkaW5ncy4gUHJvY2VlZGluZ3Mgb2YgdGhlIDU1dGggQW5udWFsIE1lZXRpbmcgb2YgdGhlIEFzc29jaWF0aW9uIGZvciBDb21wdXRhdGlvbmFsIExpbmd1aXN0aWNzIChTaG9ydCBQYXBlcnMpLCBwcC4gNDQ44oCTNDUzLgoKPHNwYW4gaWQ9InJlZjQiPls0XTwvc3Bhbj4gSHlwZXJ3b3JkczogaHR0cHM6Ly9iaXRidWNrZXQub3JnL29tZXJsZXZ5L2h5cGVyd29yZHMsIHB1Ymxpc2hlZCBhcyBPbWVyIExldnksIFlvYXYgR29sZGJlcmcsIGFuZCBJZG8gRGFnYW4uIDIwMTUuIEltcHJvdmluZyBEaXN0cmlidXRpb25hbCBTaW1pbGFyaXR5IHdpdGggTGVzc29ucyBMZWFybmVkIGZyb20gV29yZCBFbWJlZGRpbmdzLiBUcmFuc2FjdGlvbnMgb2YgdGhlIEFzc29jaWF0aW9uIGZvciBDb21wdXRhdGlvbmFsIExpbmd1aXN0aWNzLCB2b2wuIDMsIHBwLiAyMTHigJMyMjUuCgo8c3BhbiBpZD0icmVmNSI+WzVdPC9zcGFuPiBHZW5zaW06IGh0dHBzOi8vcmFkaW1yZWh1cmVrLmNvbS9nZW5zaW0vLCBwdWJsaXNoZWQgYXM6IFNvZnR3YXJlIEZyYW1ld29yayBmb3IgVG9waWMgTW9kZWxsaW5nIHdpdGggTGFyZ2UgQ29ycG9yYS4gUmFkaW0gxZhlaMWvxZllayBhbmQgUGV0ciBTb2prYS4gUHJvY2VlZGluZ3Mgb2YgdGhlIExSRUMgMjAxMCBXb3Jrc2hvcCBvbiBOZXcgQ2hhbGxlbmdlcyBmb3IgTkxQIEZyYW1ld29ya3MsIHBwLiA0NS01MCwgMjIgTWF5IDIwMTAuCg==