Text mining

Introduction

Understanding the problem

NLP is a hot topic and is being used widely in the industry to penetrate deeper into user analytics and understand the user better, learn the vocabulory and suggest auto-completion, analyze behaviour and so on.

Here use apply the knowledge to build a text/sentence auto completion product which requires us to:

  1. Analyzing a large corpus of text documents to discover the structure in the data and how words are put together.
  2. Cleaning and analyzing text data, then building and sampling from a predictive text model
  3. Finally, to build a predictive text product.

Packages used for analysis

require(ngram)
require(NLP)
require(tm)
require(RWeka)
require(data.table)
require(corpus)
require(qdap)
require(ggplot2)
require(tidytext)
require(stringi)
require(stringr)
require(dplyr)
require(viridisLite)
require(plotrix)
require(dendextend)

Data gathering and info

Data exploration and understanding is a key aspect of data science, for the purpose of understanding the kind of data we are working with.

Getting the data

The data is obtained as part of the coursera datascience specialization capstone project, and consists of 4 folders that each consist of data from twitter, news and blogs. Each folder represents languages: English, Finnish, German and Russian. 

fileUrl = 
  'https://d396qusza40orc.cloudfront.net/dsscapstone/dataset/Coursera-SwiftKey.zip'
dir.create(file.path('../data'), recursive = TRUE,showWarnings = F)
if(!dir.exists('../data/en_US')){
  download.file(fileUrl,'../data/dataset.zip', mode = 'wb')
  unzip("../data/dataset.zip", exdir = '../data')
  file.copy("../data/final/en_US", "../data", recursive = T)
  file.copy("../data/final/de_DE", "../data", recursive = T)
  file.copy("../data/final/fi_FI", "../data", recursive = T)
  file.copy("../data/final/ru_RU", "../data", recursive = T)
}
## [1] TRUE
rm(fileUrl)
unlink('../data/final', recursive = T)
unlink("../data/dataset.zip")

Loading the en_US blogs, news and twitter data

The data extracted consists of just lines of text/sentences that are to be mined to distill actionable insights. The files are read one by one using the readLines() function with encoding set to utf-8, the standard encoding standard, skipping through the null lines. 

en_blogs = readLines(
  "../data/en_US/en_US.blogs.txt", encoding="UTF-8", 
  skipNul = TRUE, warn = TRUE)
en_news = readLines(
  "../data/en_US/en_US.news.txt", encoding="UTF-8", 
  skipNul = TRUE, warn = TRUE)
en_twitter = readLines(
  "../data/en_US/en_US.twitter.txt", encoding="UTF-8", 
  skipNul = TRUE, warn = TRUE)

Summary statistics on the data

blogs_info = c(stri_stats_general(en_blogs)[1],  stri_stats_latex(en_blogs)[4],
               max(summary(nchar(en_blogs))),
               sum(grepl("love", en_blogs))/sum(grepl("hate", en_blogs)),
               file.info("../data/en_US/en_US.blogs.txt")$size/(2^20))
news_info = c(stri_stats_general(en_news)[1], stri_stats_latex(en_news)[4],
              max(summary(nchar(en_news))), 
              sum(grepl("love", en_news))/sum(grepl("hate", en_news)),
              file.info("../data/en_US/en_US.news.txt")$size/(2^20))
twitter_info = c(stri_stats_general(en_twitter)[1], stri_stats_latex(en_twitter)[4],
                 max(summary(nchar(en_twitter))), 
                 sum(grepl("love", en_twitter))/sum(grepl("hate", en_twitter)),
                 file.info("../data/en_US/en_US.twitter.txt")$size/(2^20))
total_info = blogs_info+news_info+twitter_info

table_info <- as.data.frame(rbind(blogs_info, news_info, twitter_info, total_info))
rm(blogs_info, news_info, twitter_info, total_info)
colnames(table_info) = c("Lines", "Words", "Longest line", 'love/hate ratio', "Size in Mb")
table_info

data processing

Sampling and combining the data

set.seed(193)
sample_size = 2500
blogs = en_blogs[sample(1:length(en_blogs),sample_size)]
blogs = removeWords(blogs, stopwords("en"))
blogs = gsub("\\s+", " ", blogs)
blogs = str_trim(blogs, side = c("both"))
news = en_news[sample(1:length(en_news),sample_size)]
news = removeWords(news, stopwords("en"))
news = gsub("\\s+", " ", news)
news = str_trim(news, side = c("both"))
twitter = en_twitter[sample(1:length(en_twitter),sample_size)]
twitter = removeWords(twitter, stopwords("en"))
twitter = gsub("\\s+", " ", twitter)
twitter = str_trim(twitter, side = c("both"))
rm(sample_size, en_blogs, en_news, en_twitter)

Creating volatile corpus document

Building a corpus document

A corpus is a collection of documents, We create a volatile corpus to from the vector of texts obtained.

Make a vector source using the tm package, then converting the source vector into a VCorpus object 

create_corpus = function(text_data){
  text_corpus = VCorpus(
    VectorSource(text_data),
      readerControl=list(readPlain, language="en", load=TRUE)
  )
  text_corpus
}
blogs_corpus = create_corpus(blogs)
news_corpus = create_corpus(news)
twitter_corpus = create_corpus(twitter)

The VCorpus object uses a nested - list of list structure to hold the data. At each index of the VCorpus object, there is a PlainTextDocument object, which is a list containing actual text data (content), and some corresponding metadata (meta). It can help to visualize a VCorpus object to conceptualize the whole thing.

Cleaning and preprocessing text

Using tm’s built-in text processing methods to mine data from the corpus. 

clean_corpus <- function (corpus) {
    corpus <- tm_map(corpus, tolower) # all lowercase
    corpus <- tm_map(corpus, removePunctuation) # Eleminate punctuation
    corpus <- tm_map(corpus, removeNumbers) # Eliminate numbers
    corpus <- tm_map(corpus, replace_abbreviation) # Eliminate abbreviations
    corpus <- tm_map(corpus, replace_contraction) # Eliminate contractions
    corpus <- tm_map(corpus, replace_symbol) # Eliminate symbols
    corpus <- tm_map(corpus, stripWhitespace) # Strip Whitespace
    corpus <- tm_map(corpus, removeWords, stopwords("english")) # Eliminate English stop words
    # corpus <- tm_map(corpus, stemDocument) # Stem the document
    corpus <- tm_map(corpus, PlainTextDocument) # Create plain text format
}

text_corpus = c(news_corpus,blogs_corpus,twitter_corpus, recursive = FALSE)
text_corpus_cleaned = clean_corpus(text_corpus)

# Comparing with original data
cat("Original document: ",content(text_corpus[[1]]))
## Original document:  Hey, Hoynsie: What think Mark Shapiro Chris Antonetti's reasoning building team heavy left-handed hitting weak left-handed pitching. Is new baseball fad? -- Tim Phelps, Cleveland
cat("\nCleaned document: ",content(text_corpus_cleaned[[1]]))
## 
## Cleaned document:  Hey hoynsie  think mark shapiro chris antonettis reasoning building team heavy lefthanded hitting weak lefthanded pitching  new baseball fad tim phelps cleveland
## Saving corpus cleaned 
getwd()
## [1] "C:/Users/Aquaregis32/Documents/Github/Data_Science_R/Projects/Swift key predictive text analytics/Rmd"
writeLines(as.character(text_corpus_cleaned), con="../Corpus/text_corpus_cleaned.txt")

# Disposing off the original corpus
rm(text_corpus, blogs_corpus, news_corpus, twitter_corpus)

Creating a document-term matrix for analysis

When we wish to represent the data with the document as rows and the words as column we use document term matrix, the transpose of which is term document matrix.
The fields then represent the frequency of words in the data. However, other frequency measures do exist. 

text_tdm = TermDocumentMatrix(text_corpus_cleaned)
# rm(text_corpus_cleaned)
text_tdm
## <<TermDocumentMatrix (terms: 24116, documents: 7500)>>
## Non-/sparse entries: 111028/180758972
## Sparsity           : 100%
## Maximal term length: 51
## Weighting          : term frequency (tf)

Convert term document matrix to matrix

The term document is converted into a large matrix in which each cell represents the count/frequency of the word(row) in the corresponding document(column).

text_m = as.matrix(text_tdm)

Exploratory analysis

Using qdap’s fre_terms() functions to count the frequency of words in the datasets and presenting the information in tabular and graphical methods.

Most frequently used words

term_frequency = rowSums(text_m)
term_frequency <- sort(term_frequency, decreasing = T)
rm(text_m)
barplot(term_frequency[1:10], col = "hotpink4", las = 2, main = "Most frequently used words")

Sentiment analysis

Creating a tibble

Converting the twitter_dtm to a tibble for sentiment analysis using tidytext package. 

text_tbl = tidytext::tidy(text_tdm)
text_tbl = text_tbl[,c("term","count")]
print(dim(text_tbl))
## [1] 111028      2
head(text_tbl[order(-text_tbl$count),], 10)

Forming analysis

text_sentiments <- text_tbl %>%
  inner_join(get_sentiments("bing"), by = c(term = "word"))
print(dim(text_sentiments))
## [1] 12436     3
head(text_sentiments, 10)

Visualizing

text_sentiments %>%
  count(sentiment, term, wt = count) %>%
  filter(n >= 35) %>%
  mutate(n = ifelse(sentiment == "negative", -n, n)) %>%
  mutate(term = reorder(term, n)) %>%
  ggplot(aes(term, n, fill = sentiment)) + 
  theme_minimal() +
  geom_bar(stat = "identity") +
  theme(axis.text.x = element_text(angle=90,hjust=1)) + #element_blank()) +
  ylab("Contribution to sentiment")

Word cloud

word_freqs = data.frame(
  term = names(term_frequency),
  num = term_frequency
)
wordcloud::wordcloud(
  word_freqs$term, word_freqs$num, 
  max.words = 100, colors = cividis(n = 3)
)

Comparisons using word cloud

Preparing the data 

all_blogs = paste(blogs, collapse = "")
all_news = paste(news, collapse = "")
all_twitter = paste(twitter ,collapse = "")
all_texts = c(all_blogs, all_news, all_twitter)

rm(blogs, news, twitter)
all_texts = VCorpus(VectorSource(all_texts))
# all_texts = clean_corpus(all_texts)

all_dm = TermDocumentMatrix(all_texts)
all_tdm = TermDocumentMatrix(all_texts)
colnames(all_tdm) = c("Blogs", "News", "Twitter")
all_m = as.matrix(all_dm)
all_mc = as.matrix(all_tdm)

Commonality

Using commonality word cloud to how similar the three corpus are 

wordcloud::commonality.cloud(all_m, colors = magma(n = 5), max.words = 100)

rm(all_m, all_dm)

Comparison

Using comparison cloud to understand the distribution of words in each category of texts - blogs, news and twitter 

wordcloud::comparison.cloud(all_mc, colors = c("orange","skyblue","hotpink3"), max.words = 100)

Polaized tag plot

Creating data for plot

using the pyramid package
blogs and news: 

# subset the common words in the documents
common_words = as.data.frame(subset(all_mc, all_mc[,1]>0 & all_mc[,2]>0 & all_mc[,3]>0))
# Finding the difference and then ordering by it
common_words = mutate(common_words, 
                      diff_bn = abs(common_words[,1] - common_words[,2]),
                      diff_bt = abs(common_words[,1] - common_words[,3]),
                      diff_nt = abs(common_words[,2] - common_words[,3]),
                      labels = rownames(common_words)
)
common_words = common_words[order(-common_words[,4]),]
top_25_bn = common_words[1:25,]
common_words = common_words[order(-common_words[,5]),]
top_25_bt = common_words[1:25,]
common_words = common_words[order(-common_words[,6]),]
top_25_nt = common_words[1:25,]

Difference between common terms in blogs and news

pyramid.plot(
  top_25_bn$Blogs, top_25_bn$News, labels = top_25_bn$labels,
  main = "Words in common between blogs and news", gap = 150,
  unit = NULL, raxlab = NULL, laxlab = NULL, top.labels = 
    c("blogs", "words", "news")
)

## 352 352
## [1] 5.1 4.1 4.1 2.1

Difference between common terms in blogs and twitter

pyramid.plot(
  top_25_bt$Blogs, top_25_bt$News, labels = top_25_bt$labels,
  main = "Words in common between blogs and news", gap = 100,
  unit = NULL, raxlab = NULL, laxlab = NULL, top.labels = 
    c("blogs", "words", "twitter")
)

## 352 352
## [1] 5.1 4.1 4.1 2.1

Difference between common terms in news and twitter

pyramid.plot(
  top_25_nt$Blogs, top_25_nt$News, labels = top_25_nt$labels,
  main = "Words in common between blogs and news", gap = 200,
  unit = NULL, raxlab = NULL, laxlab = NULL, top.labels = 
    c("news", "words", "twitter")
)

## 352 352
## [1] 5.1 4.1 4.1 2.1

Analyzing words using dendrogram plot

Dendrograms reduce complicated multi-dimensional datasets to simple clustering information. This makes them a valuable tool to reduce complexity. Using the distance matrix and hclust() function we create a hierarchical cluster object which is then passed into the function as.dendrogram.

Removing sparsity of the term document using the removeSparseTerms to reduce the number of terms, the parameter ‘sparse’ species the percent cut-off for number of zeroes that is allowed for each term. 

# Removing sparse terms 
text_reduced = removeSparseTerms(text_tdm, sparse = 0.97)
text_reduced_m = as.matrix(text_reduced)
text_reduced_dist = dist(text_reduced_m)

# Creating hclust object
text_hc = hclust(text_reduced_dist)

# Converting hclust object to dendrogram
text_dend = as.dendrogram(text_hc)

# Labels of dendrogram object
labels(text_dend)
##  [1] "will"   "said"   "one"    "can"    "time"   "get"    "people" "first" 
##  [9] "also"   "last"   "two"    "see"    "now"    "way"    "well"   "much"  
## [17] "make"   "think"  "day"    "back"   "going"  "good"   "know"   "love"  
## [25] "new"    "the"    "just"   "like"
# Changing color of branches 'year', 'love' and 'said' to red
text_dend_colored = branches_attr_by_labels(
  text_dend, 
  c("two","will","said"),
  "red"
)
# Plot
plot(text_dend_colored, main = "Dendrogram analysis")

# Adding rectangles
rect.dendrogram(tree = text_dend_colored, k = 3, border = "grey50")

Word associations

Using the findAssocs() function of tm package and calculating the correlation of a word with every other words/terms in the document in the range [0,1]. 

text_associations = findAssocs(text_tdm, "year", 0.125)

# Converting to dataframe for plot
text_associations_df = list_vect2df(
  text_associations, col2 = "word", col3 = "score"
)
# plot
ggplot(text_associations_df, aes(score, word)) +
  geom_point(size = 3) + 
  theme_minimal()

rm(text_associations, text_associations_df, text_tdm)

N-gram tokenize

So far we’ve studied the association of a token containing just one word with other words/tokens, this part of the analysis concentrates on analysis of tokens containing more than one word.

Defining functions

# Creating a tokenizer functions using the RWeka package
bigram_tokenizer = function(x){
  NGramTokenizer(x, Weka_control(min = 2, max = 2))
}
trigram_tokenizer = function(x){
  NGramTokenizer(x, Weka_control(min = 3, max = 3))
}
tetragram_tokenizer = function(x){
  NGramTokenizer(x, Weka_control(min = 4, max = 4))
}
pentagram_tokenizer = function(x){
  NGramTokenizer(x, Weka_control(min = 5, max = 5))
}

Bigrams

Creating a bigram tdm

bigram_tdm = TermDocumentMatrix(
  text_corpus_cleaned,
  control = list(tokenize = bigram_tokenizer)
)
bigram_m = as.matrix(bigram_tdm)

wordcloud analysis

freq = rowSums(bigram_m)
bi_tokens = names(freq)
bi_token_df = data.frame(token = bi_tokens, freq = freq)
row.names(bi_token_df) = NULL
wordcloud::wordcloud(bi_token_df$token, bi_token_df$freq, max.words = 150, colors = cividis(n = 3))

Trigrams

Creating a trigram tdm

trigram_tdm = TermDocumentMatrix(
  text_corpus_cleaned,
  control = list(tokenize = trigram_tokenizer)
)
trigram_m = as.matrix(trigram_tdm)

wordcloud analysis

freq = rowSums(trigram_m)
tri_tokens = names(freq)
tri_token_df = data.frame(token = tri_tokens, freq = freq)
row.names(tri_token_df) = NULL
wordcloud::wordcloud(
  words = tri_token_df$token, freq = tri_token_df$freq, 
  max.words = 150, colors = cividis(n = 3)
)

Tetragrams

Creating a tetragram tdm

tetragram_tdm = TermDocumentMatrix(
  text_corpus_cleaned,
  control = list(tokenize = tetragram_tokenizer)
)
tetragram_m = as.matrix(tetragram_tdm)

wordcloud analysis

freq = rowSums(tetragram_m)
tetra_tokens = names(freq)
tetra_token_df = data.frame(token = tetra_tokens, freq = freq)
row.names(tetra_token_df) = NULL
head(tetra_token_df[order(-tetra_token_df$freq),])
wordcloud::wordcloud(
  words = tetra_token_df$token, freq = tetra_token_df$freq, 
  max.words = 150, colors = cividis(n = 5)
)

Creating prediction model

Building N-Grams

N-Grams

Loading/Defining data and functions

## Create corpus 
create_corpus = function(text_data){
  text_corpus = VCorpus(
    VectorSource(text_data),
      readerControl=list(readPlain, language="en", load=TRUE)
  )
  text_corpus
}
## Corpus clean function
clean_corpus_mdl <- function (corpus) {
    corpus <- tm_map(corpus, tolower) # all lowercase
    corpus <- tm_map(corpus, removePunctuation) # Eleminate punctuation
    corpus <- tm_map(corpus, removeNumbers) # Eliminate numbers
    corpus <- tm_map(corpus, replace_abbreviation) # Eliminate abbreviations
    corpus <- tm_map(corpus, replace_contraction) # Eliminate contractions
    corpus <- tm_map(corpus, replace_symbol) # Eliminate symbols
    corpus <- tm_map(corpus, stripWhitespace) # Strip Whitespace
    corpus <- tm_map(corpus, PlainTextDocument) # Create plain text format
}
set.seed(193)
sample_size = 5000

Ngram_sythesize = function(corpus,n){
  tdm = TermDocumentMatrix(
    corpus,
    control = list(tokenize = function(x){
      NGramTokenizer(x, Weka_control(min = n, max = n))
    })
  )
  m = as.matrix(tdm)
  rm(tdm)
  freq = rowSums(m)
  tokens = names(freq)
  rm(m)
  token_df = data.frame(token = tokens, freq = freq)
  rm(tokens,freq)
  row.names(token_df) = NULL
  token_df = filter(token_df, freq>1)
}

Creating models for Blogs

en_blogs = readLines(
  "../data/en_US/en_US.blogs.txt", encoding="UTF-8", 
  skipNul = TRUE, warn = TRUE)
blogs = en_blogs[sample(1:length(en_blogs),sample_size)]
rm(en_blogs)
blogs = gsub("\\s+", " ", blogs)
blogs = str_trim(blogs, side = c("both"))
blogs_corpus = create_corpus(blogs)
blogs_corpus_cleaned = clean_corpus_mdl(blogs_corpus)
rm(blogs,blogs_corpus)

### Bigrams
blogs_bi_token_df = Ngram_sythesize(blogs_corpus_cleaned,2)

### Trigrams
blogs_tri_token_df = Ngram_sythesize(blogs_corpus_cleaned,3)

### Tetragrams
blogs_tetra_token_df = Ngram_sythesize(blogs_corpus_cleaned,4)

### Pentagrams
blogs_penta_token_df = Ngram_sythesize(blogs_corpus_cleaned,5)

rm(blogs_corpus_cleaned)

Creating models for News

en_news = readLines(
  "../data/en_US/en_US.news.txt", encoding="UTF-8", 
  skipNul = TRUE, warn = TRUE)
news = en_news[sample(1:length(en_news),sample_size)]
rm(en_news)
news = gsub("\\s+", " ", news)
news = str_trim(news, side = c("both"))
news_corpus = create_corpus(news)
news_corpus_cleaned = clean_corpus_mdl(news_corpus)
rm(news,news_corpus)

### Bigrams
news_bi_token_df = Ngram_sythesize(news_corpus_cleaned,2)

### Trigrams
news_tri_token_df = Ngram_sythesize(news_corpus_cleaned,3)

### Tetragrams
news_tetra_token_df = Ngram_sythesize(news_corpus_cleaned,4)

### Pentagrams
news_penta_token_df = Ngram_sythesize(news_corpus_cleaned,5)

rm(news_corpus_cleaned)

Creating models for Twitter

en_twitter = readLines(
  "../data/en_US/en_US.twitter.txt", encoding="UTF-8", 
  skipNul = TRUE, warn = TRUE)
twitter = en_twitter[sample(1:length(en_twitter),sample_size)]
rm(en_twitter)
twitter = gsub("\\s+", " ", twitter)
twitter = str_trim(twitter, side = c("both"))
twitter_corpus = create_corpus(twitter)
twitter_corpus_cleaned = clean_corpus_mdl(twitter_corpus)
rm(twitter, twitter_corpus)

### Bigrams
twitter_bi_token_df = Ngram_sythesize(twitter_corpus_cleaned,2)

### Trigrams
twitter_tri_token_df = Ngram_sythesize(twitter_corpus_cleaned,3)

### Tetragrams
twitter_tetra_token_df = Ngram_sythesize(twitter_corpus_cleaned,4)

### Pentagrams
twitter_penta_token_df = Ngram_sythesize(twitter_corpus_cleaned,5)

rm(twitter_corpus_cleaned)

Combining the data

bigrams = rbind(blogs_bi_token_df,news_bi_token_df,twitter_bi_token_df)
trigrams = rbind(blogs_tri_token_df,news_tri_token_df,twitter_tri_token_df)
tetragrams = rbind(blogs_tetra_token_df,news_tetra_token_df,twitter_tetra_token_df)
pentagrams = rbind(blogs_penta_token_df,news_penta_token_df,twitter_penta_token_df)
rm(blogs_bi_token_df,news_bi_token_df,twitter_bi_token_df,
   blogs_tri_token_df,news_tri_token_df,twitter_tri_token_df,
   blogs_tetra_token_df,news_tetra_token_df,twitter_tetra_token_df,
   blogs_penta_token_df,news_penta_token_df,twitter_penta_token_df
)
bigrams$which = 2
trigrams$which = 3
tetragrams$which = 4
pentagrams$which = 5

NGrams = rbind(bigrams,trigrams,tetragrams,pentagrams)
rm(bigrams,trigrams,tetragrams,pentagrams)
### Saving
save(NGrams, file = "../NGrams/NGrams.rda")
write.csv(NGrams, "../NGrams/NGrams.csv", fileEncoding = 'UTF-8', row.names = F)
rm(NGrams)

Defining prediction function

Creating a function that predicts the next word for a given input list of words

## Loading the n-grams 
NGrams = get(load("../NGrams/NGrams.rda"))

## Function
predictWord = function(str){
  preds_ = ""
  pred = ""
  str = gsub("\\s+", " ", str)
  str = tolower(str)
  str = removePunctuation(str)
  str = str_trim(str, side = c("both"))
  n_words = str_count(str, " ") + 1
  if(n_words>4){
    str = str_split_fixed(str,pattern = " ", n_words)[(n_words-3):n_words]
    n_words = 4
  }
  if(n_words == 4){
    matching_tetragrams = filter(NGrams, which == 5)[grepl(str,
                                       filter(NGrams, which == 5)[,1], ignore.case=TRUE),]
    preds_ = data.frame(
      prediction = str_extract_all(matching_tetragrams[,1],
                                   paste0(str,"\\s([:alpha:]+)"),
                                   simplify = T),
      freq = matching_tetragrams[,2])  
    best_pred = preds_[order(-preds_$freq),][1]
    if(is.null(dim(best_pred))){
      str = str_split_fixed(str,pattern = " ", 4)[2:4]
      n_words = 3
    }
  }
  if(n_words == 3){
    matching_tetragrams = filter(NGrams, which == 4)[grepl(str,
                                       filter(NGrams, which == 4)[,1], ignore.case=TRUE),]
    preds_ = data.frame(
      prediction = str_extract_all(matching_tetragrams[,1],
                                   paste0(str,"\\s([:alpha:]+)"),
                                   simplify = T),
      freq = matching_tetragrams[,2]) 
    best_pred = preds_[order(-preds_$freq),][1]
    if(is.null(dim(best_pred))){
      str = str_split_fixed(str,pattern = " ", 3)[2:3]
      n_words = 2
    }
  }
  if(n_words == 2){
    matching_trigrams = filter(NGrams, which == 3)[grep(str,
                                    filter(NGrams, which == 3)[,1], ignore.case=TRUE),]
    preds_ = data.frame(
      prediction = str_extract_all(matching_trigrams[,1], 
                                   paste0(str,"\\s([:alpha:]+)"),
                                   simplify = T),
      freq = matching_trigrams[,2])  
    best_pred = preds_[order(-preds_$freq),][1]
    if(is.na(best_pred)){
      str = str_split_fixed(str,pattern = " ", 3)[2]
      n_words = 1
    }
  }
  if(n_words == 1){
    matching_bigrams = filter(NGrams, which == 2)[grep(str,
                                   filter(NGrams, which == 2)[,1], ignore.case=TRUE),]
    preds_ = data.frame(
      prediction = str_extract_all(matching_bigrams[,1],
                                   paste0(str,"\\s([:alpha:]+)"),
                                   simplify = T),
      freq = matching_bigrams[,2])  
    best_pred = preds_[order(-preds_$freq),1][1]
  }
  pred = str_split_fixed(preds_[order(preds_[,2]),][1,1], " ", n=2)[2]
  pred
}
predictWord("achieving")
## [1] "greater"
## R Session Info:
## R version 4.0.3 (2020-10-10)
## Platform: x86_64-w64-mingw32/x64 (64-bit)
## Running under: Windows 10 x64 (build 19042)
## 
## Matrix products: default
## 
## locale:
## [1] LC_COLLATE=English_United States.1252  LC_CTYPE=English_United States.1252   
## [3] LC_MONETARY=English_United States.1252 LC_NUMERIC=C                          
## [5] LC_TIME=English_United States.1252    
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
##  [1] dendextend_1.14.0      plotrix_3.7-8          viridisLite_0.3.0      dplyr_1.0.2           
##  [5] stringr_1.4.0          stringi_1.5.3          tidytext_0.2.6         ggplot2_3.3.2         
##  [9] qdap_2.4.3             RColorBrewer_1.1-2     qdapTools_1.3.5        qdapRegex_0.7.2       
## [13] qdapDictionaries_1.0.7 corpus_0.10.1          data.table_1.13.2      RWeka_0.4-43          
## [17] tm_0.7-8               NLP_0.2-1              ngram_3.0.4           
## 
## loaded via a namespace (and not attached):
##  [1] viridis_0.5.1       jsonlite_1.7.1      gender_0.5.4        yaml_2.2.1         
##  [5] slam_0.1-48         pillar_1.4.7        lattice_0.20-41     glue_1.4.2         
##  [9] chron_2.3-56        digest_0.6.27       colorspace_2.0-0    htmltools_0.5.0    
## [13] Matrix_1.2-18       plyr_1.8.6          XML_3.99-0.5        pkgconfig_2.0.3    
## [17] bookdown_0.21       purrr_0.3.4         scales_1.1.1        openxlsx_4.2.3     
## [21] tibble_3.0.4        openNLP_0.2-7       farver_2.0.3        generics_0.1.0     
## [25] ellipsis_0.3.1      withr_2.3.0         magrittr_2.0.1      crayon_1.3.4       
## [29] evaluate_0.14       tokenizers_0.2.1    janeaustenr_0.1.5   SnowballC_0.7.0    
## [33] xml2_1.3.2          tools_4.0.3         RWekajars_3.9.3-2   lifecycle_0.2.0    
## [37] munsell_0.5.0       zip_2.1.1           compiler_4.0.3      rlang_0.4.8        
## [41] grid_4.0.3          RCurl_1.98-1.2      igraph_1.2.6        bitops_1.0-6       
## [45] labeling_0.4.2      rmarkdown_2.5       venneuler_1.1-0     gtable_0.3.0       
## [49] reshape2_1.4.4      R6_2.5.0            gridExtra_2.3       knitr_1.30         
## [53] utf8_1.1.4          openNLPdata_1.5.3-4 rJava_0.9-13        parallel_4.0.3     
## [57] rmdformats_1.0.0    Rcpp_1.0.5          vctrs_0.3.4         wordcloud_2.6      
## [61] tidyselect_1.1.0    xfun_0.19
LS0tDQp0aXRsZTogIlRleHQgbWluaW5nIg0KZGF0ZTogImByIGZvcm1hdChTeXMuRGF0ZSgpLCAnJUIgJWQsICVZJylgIg0KZm9udHNpemU6IDEwcHQNCm91dHB1dDoNCiAgcm1kZm9ybWF0czo6cmVhZHRoZWRvd246DQogICAgY29kZV9kb3dubG9hZDogeWVzDQoNCiAgICBkZl9wcmludDogcGFnZWQNCiAgICB0aGVtZTogY29zbW8NCiAgICBoaWdobGlnaHQ6IHRhbmdvDQogICAgdGh1bWJuYWlsczogZmFsc2UNCiAgICBsaWdodGJveDogZmFsc2UNCiAgaHRtbF9kb2N1bWVudDoNCiAgICBjb2RlX2Rvd25sb2FkOiB5ZXMNCiAgICBkZl9wcmludDogcGFnZWQNCiAgICBmaWdfd2lkdGg6IDgNCiAgICBmaWdfaGVpZ2h0OiA1DQogICAgdGhlbWU6IGNvc21vDQogICAgaGlnaGxpZ2h0OiB0YW5nbw0KICAgIHRvYzogeWVzDQogICAgdG9jX2RlcHRoOiA0DQogIHdvcmRfZG9jdW1lbnQ6DQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6ICc0Jw0KICBwZGZfZG9jdW1lbnQ6DQogICAgbGF0ZXhfZW5naW5lOiB4ZWxhdGV4DQogICAgdG9jOiB5ZXMNCiAgICB0b2NfZGVwdGg6ICczJw0KICAgIGtlZXBfdGV4OiB0cnVlDQpoZWFkZXItaW5jbHVkZXM6DQotIFxEZWNsYXJlTWF0aE9wZXJhdG9yKntcYXJnbWlufXthcmdcLG1pbn0NCi0gXG5ld2NvbW1hbmQqe1xwcm9ifXtcbWF0aHNme1B9fQ0KDQp1cmxjb2xvcjogJ2JsdWUnDQotLS0NCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQoDQogIGVjaG8gPSBUUlVFLA0KICBmaWcuYWxpZ24gPSAiY2VudGVyIiwgZmlnLndpZHRoID0gOCwgZmlnLmhlaWdodCA9IDYNCikNCmBgYA0KDQojIEludHJvZHVjdGlvbg0KIyMgVW5kZXJzdGFuZGluZyB0aGUgcHJvYmxlbSANCjxwIGFsaWduPSJqdXN0aWZ5Ij4NCk5MUCBpcyBhIGhvdCB0b3BpYyBhbmQgaXMgYmVpbmcgdXNlZCB3aWRlbHkgaW4gdGhlIGluZHVzdHJ5IHRvIHBlbmV0cmF0ZSBkZWVwZXINCmludG8gdXNlciBhbmFseXRpY3MgYW5kIHVuZGVyc3RhbmQgdGhlIHVzZXIgYmV0dGVyLCBsZWFybiB0aGUgdm9jYWJ1bG9yeSBhbmQgDQpzdWdnZXN0IGF1dG8tY29tcGxldGlvbiwgYW5hbHl6ZSBiZWhhdmlvdXIgYW5kIHNvIG9uLjwvcD4NCg0KPHAgYWxpZ249Imp1c3RpZnkiPg0KSGVyZSB1c2UgYXBwbHkgdGhlIGtub3dsZWRnZSB0byBidWlsZCBhIHRleHQvc2VudGVuY2UgYXV0byBjb21wbGV0aW9uIHByb2R1Y3QgDQp3aGljaCByZXF1aXJlcyB1cyB0bzogPC9wPg0KPG9sPg0KICA8bGk+QW5hbHl6aW5nIGEgbGFyZ2UgY29ycHVzIG9mIHRleHQgZG9jdW1lbnRzIHRvIGRpc2NvdmVyIHRoZSBzdHJ1Y3R1cmUgaW4gdGhlIGRhdGEgDQphbmQgaG93IHdvcmRzIGFyZSBwdXQgdG9nZXRoZXIuIDwvbGk+DQogIDxsaT5DbGVhbmluZyBhbmQgYW5hbHl6aW5nIHRleHQgZGF0YSwgdGhlbiBidWlsZGluZyBhbmQgc2FtcGxpbmcgZnJvbSBhIHByZWRpY3RpdmUgDQp0ZXh0IG1vZGVsPC9saT4NCiAgPGxpPkZpbmFsbHksIHRvIGJ1aWxkIGEgcHJlZGljdGl2ZSB0ZXh0IHByb2R1Y3QuPC9saT4NCjwvb2w+DQoNCiMjIFBhY2thZ2VzIHVzZWQgZm9yIGFuYWx5c2lzDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KcmVxdWlyZShuZ3JhbSkNCnJlcXVpcmUoTkxQKQ0KcmVxdWlyZSh0bSkNCnJlcXVpcmUoUldla2EpDQpyZXF1aXJlKGRhdGEudGFibGUpDQpyZXF1aXJlKGNvcnB1cykNCnJlcXVpcmUocWRhcCkNCnJlcXVpcmUoZ2dwbG90MikNCnJlcXVpcmUodGlkeXRleHQpDQpyZXF1aXJlKHN0cmluZ2kpDQpyZXF1aXJlKHN0cmluZ3IpDQpyZXF1aXJlKGRwbHlyKQ0KcmVxdWlyZSh2aXJpZGlzTGl0ZSkNCnJlcXVpcmUocGxvdHJpeCkNCnJlcXVpcmUoZGVuZGV4dGVuZCkNCmBgYA0KDQoNCiMgRGF0YSBnYXRoZXJpbmcgYW5kIGluZm8NCg0KPHAgYWxpZ249Imp1c3RpZnkiPg0KRGF0YSBleHBsb3JhdGlvbiBhbmQgdW5kZXJzdGFuZGluZyBpcyBhIGtleSBhc3BlY3Qgb2YgZGF0YSBzY2llbmNlLCBmb3IgdGhlIA0KcHVycG9zZSBvZiB1bmRlcnN0YW5kaW5nIHRoZSBraW5kIG9mIGRhdGEgd2UgYXJlIHdvcmtpbmcgd2l0aC48L3A+DQoNCiMjIEdldHRpbmcgdGhlIGRhdGENCg0KPHAgYWxpZ249Imp1c3RpZnkiPg0KVGhlIGRhdGEgaXMgb2J0YWluZWQgYXMgcGFydCBvZiB0aGUgY291cnNlcmEgZGF0YXNjaWVuY2Ugc3BlY2lhbGl6YXRpb24gY2Fwc3RvbmUgDQpwcm9qZWN0LCBhbmQgY29uc2lzdHMgb2YgNCBmb2xkZXJzIHRoYXQgZWFjaCBjb25zaXN0IG9mIGRhdGEgZnJvbSB0d2l0dGVyLCBuZXdzIA0KYW5kIGJsb2dzLiBFYWNoIGZvbGRlciByZXByZXNlbnRzIGxhbmd1YWdlczogRW5nbGlzaCwgRmlubmlzaCwgR2VybWFuIGFuZCANClJ1c3NpYW4uPC9wPg0KDQpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQ0KZmlsZVVybCA9IA0KICAnaHR0cHM6Ly9kMzk2cXVzemE0MG9yYy5jbG91ZGZyb250Lm5ldC9kc3NjYXBzdG9uZS9kYXRhc2V0L0NvdXJzZXJhLVN3aWZ0S2V5LnppcCcNCmRpci5jcmVhdGUoZmlsZS5wYXRoKCcuLi9kYXRhJyksIHJlY3Vyc2l2ZSA9IFRSVUUsc2hvd1dhcm5pbmdzID0gRikNCmlmKCFkaXIuZXhpc3RzKCcuLi9kYXRhL2VuX1VTJykpew0KICBkb3dubG9hZC5maWxlKGZpbGVVcmwsJy4uL2RhdGEvZGF0YXNldC56aXAnLCBtb2RlID0gJ3diJykNCiAgdW56aXAoIi4uL2RhdGEvZGF0YXNldC56aXAiLCBleGRpciA9ICcuLi9kYXRhJykNCiAgZmlsZS5jb3B5KCIuLi9kYXRhL2ZpbmFsL2VuX1VTIiwgIi4uL2RhdGEiLCByZWN1cnNpdmUgPSBUKQ0KICBmaWxlLmNvcHkoIi4uL2RhdGEvZmluYWwvZGVfREUiLCAiLi4vZGF0YSIsIHJlY3Vyc2l2ZSA9IFQpDQogIGZpbGUuY29weSgiLi4vZGF0YS9maW5hbC9maV9GSSIsICIuLi9kYXRhIiwgcmVjdXJzaXZlID0gVCkNCiAgZmlsZS5jb3B5KCIuLi9kYXRhL2ZpbmFsL3J1X1JVIiwgIi4uL2RhdGEiLCByZWN1cnNpdmUgPSBUKQ0KfQ0Kcm0oZmlsZVVybCkNCnVubGluaygnLi4vZGF0YS9maW5hbCcsIHJlY3Vyc2l2ZSA9IFQpDQp1bmxpbmsoIi4uL2RhdGEvZGF0YXNldC56aXAiKQ0KYGBgDQoNCiMjIExvYWRpbmcgdGhlIGVuX1VTIGJsb2dzLCBuZXdzIGFuZCB0d2l0dGVyIGRhdGENCjxwIGFsaWduPSJqdXN0aWZ5Ij4NClRoZSBkYXRhIGV4dHJhY3RlZCBjb25zaXN0cyBvZiBqdXN0IGxpbmVzIG9mIHRleHQvc2VudGVuY2VzIHRoYXQgYXJlIHRvIGJlIG1pbmVkIA0KdG8gZGlzdGlsbCBhY3Rpb25hYmxlIGluc2lnaHRzLg0KVGhlIGZpbGVzIGFyZSByZWFkIG9uZSBieSBvbmUgdXNpbmcgdGhlIHJlYWRMaW5lcygpIGZ1bmN0aW9uIHdpdGggZW5jb2Rpbmcgc2V0IA0KdG8gdXRmLTgsIHRoZSBzdGFuZGFyZCBlbmNvZGluZyBzdGFuZGFyZCwgc2tpcHBpbmcgdGhyb3VnaCB0aGUgbnVsbCBsaW5lcy48L3A+DQoNCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9DQplbl9ibG9ncyA9IHJlYWRMaW5lcygNCiAgIi4uL2RhdGEvZW5fVVMvZW5fVVMuYmxvZ3MudHh0IiwgZW5jb2Rpbmc9IlVURi04IiwgDQogIHNraXBOdWwgPSBUUlVFLCB3YXJuID0gVFJVRSkNCmVuX25ld3MgPSByZWFkTGluZXMoDQogICIuLi9kYXRhL2VuX1VTL2VuX1VTLm5ld3MudHh0IiwgZW5jb2Rpbmc9IlVURi04IiwgDQogIHNraXBOdWwgPSBUUlVFLCB3YXJuID0gVFJVRSkNCmVuX3R3aXR0ZXIgPSByZWFkTGluZXMoDQogICIuLi9kYXRhL2VuX1VTL2VuX1VTLnR3aXR0ZXIudHh0IiwgZW5jb2Rpbmc9IlVURi04IiwgDQogIHNraXBOdWwgPSBUUlVFLCB3YXJuID0gVFJVRSkNCmBgYA0KDQojIyBTdW1tYXJ5IHN0YXRpc3RpY3Mgb24gdGhlIGRhdGENCmBgYHtyfQ0KYmxvZ3NfaW5mbyA9IGMoc3RyaV9zdGF0c19nZW5lcmFsKGVuX2Jsb2dzKVsxXSwgIHN0cmlfc3RhdHNfbGF0ZXgoZW5fYmxvZ3MpWzRdLA0KICAgICAgICAgICAgICAgbWF4KHN1bW1hcnkobmNoYXIoZW5fYmxvZ3MpKSksDQogICAgICAgICAgICAgICBzdW0oZ3JlcGwoImxvdmUiLCBlbl9ibG9ncykpL3N1bShncmVwbCgiaGF0ZSIsIGVuX2Jsb2dzKSksDQogICAgICAgICAgICAgICBmaWxlLmluZm8oIi4uL2RhdGEvZW5fVVMvZW5fVVMuYmxvZ3MudHh0Iikkc2l6ZS8oMl4yMCkpDQpuZXdzX2luZm8gPSBjKHN0cmlfc3RhdHNfZ2VuZXJhbChlbl9uZXdzKVsxXSwgc3RyaV9zdGF0c19sYXRleChlbl9uZXdzKVs0XSwNCiAgICAgICAgICAgICAgbWF4KHN1bW1hcnkobmNoYXIoZW5fbmV3cykpKSwgDQogICAgICAgICAgICAgIHN1bShncmVwbCgibG92ZSIsIGVuX25ld3MpKS9zdW0oZ3JlcGwoImhhdGUiLCBlbl9uZXdzKSksDQogICAgICAgICAgICAgIGZpbGUuaW5mbygiLi4vZGF0YS9lbl9VUy9lbl9VUy5uZXdzLnR4dCIpJHNpemUvKDJeMjApKQ0KdHdpdHRlcl9pbmZvID0gYyhzdHJpX3N0YXRzX2dlbmVyYWwoZW5fdHdpdHRlcilbMV0sIHN0cmlfc3RhdHNfbGF0ZXgoZW5fdHdpdHRlcilbNF0sDQogICAgICAgICAgICAgICAgIG1heChzdW1tYXJ5KG5jaGFyKGVuX3R3aXR0ZXIpKSksIA0KICAgICAgICAgICAgICAgICBzdW0oZ3JlcGwoImxvdmUiLCBlbl90d2l0dGVyKSkvc3VtKGdyZXBsKCJoYXRlIiwgZW5fdHdpdHRlcikpLA0KICAgICAgICAgICAgICAgICBmaWxlLmluZm8oIi4uL2RhdGEvZW5fVVMvZW5fVVMudHdpdHRlci50eHQiKSRzaXplLygyXjIwKSkNCnRvdGFsX2luZm8gPSBibG9nc19pbmZvK25ld3NfaW5mbyt0d2l0dGVyX2luZm8NCg0KdGFibGVfaW5mbyA8LSBhcy5kYXRhLmZyYW1lKHJiaW5kKGJsb2dzX2luZm8sIG5ld3NfaW5mbywgdHdpdHRlcl9pbmZvLCB0b3RhbF9pbmZvKSkNCnJtKGJsb2dzX2luZm8sIG5ld3NfaW5mbywgdHdpdHRlcl9pbmZvLCB0b3RhbF9pbmZvKQ0KY29sbmFtZXModGFibGVfaW5mbykgPSBjKCJMaW5lcyIsICJXb3JkcyIsICJMb25nZXN0IGxpbmUiLCAnbG92ZS9oYXRlIHJhdGlvJywgIlNpemUgaW4gTWIiKQ0KdGFibGVfaW5mbw0KYGBgDQojIGRhdGEgcHJvY2Vzc2luZw0KIyMgU2FtcGxpbmcgYW5kIGNvbWJpbmluZyB0aGUgZGF0YQ0KYGBge3Igc2FtcGxpbmctZGF0YX0NCnNldC5zZWVkKDE5MykNCnNhbXBsZV9zaXplID0gMjUwMA0KYmxvZ3MgPSBlbl9ibG9nc1tzYW1wbGUoMTpsZW5ndGgoZW5fYmxvZ3MpLHNhbXBsZV9zaXplKV0NCmJsb2dzID0gcmVtb3ZlV29yZHMoYmxvZ3MsIHN0b3B3b3JkcygiZW4iKSkNCmJsb2dzID0gZ3N1YigiXFxzKyIsICIgIiwgYmxvZ3MpDQpibG9ncyA9IHN0cl90cmltKGJsb2dzLCBzaWRlID0gYygiYm90aCIpKQ0KbmV3cyA9IGVuX25ld3Nbc2FtcGxlKDE6bGVuZ3RoKGVuX25ld3MpLHNhbXBsZV9zaXplKV0NCm5ld3MgPSByZW1vdmVXb3JkcyhuZXdzLCBzdG9wd29yZHMoImVuIikpDQpuZXdzID0gZ3N1YigiXFxzKyIsICIgIiwgbmV3cykNCm5ld3MgPSBzdHJfdHJpbShuZXdzLCBzaWRlID0gYygiYm90aCIpKQ0KdHdpdHRlciA9IGVuX3R3aXR0ZXJbc2FtcGxlKDE6bGVuZ3RoKGVuX3R3aXR0ZXIpLHNhbXBsZV9zaXplKV0NCnR3aXR0ZXIgPSByZW1vdmVXb3Jkcyh0d2l0dGVyLCBzdG9wd29yZHMoImVuIikpDQp0d2l0dGVyID0gZ3N1YigiXFxzKyIsICIgIiwgdHdpdHRlcikNCnR3aXR0ZXIgPSBzdHJfdHJpbSh0d2l0dGVyLCBzaWRlID0gYygiYm90aCIpKQ0Kcm0oc2FtcGxlX3NpemUsIGVuX2Jsb2dzLCBlbl9uZXdzLCBlbl90d2l0dGVyKQ0KYGBgDQoNCiMjIENyZWF0aW5nIHZvbGF0aWxlIGNvcnB1cyBkb2N1bWVudA0KIyMjIEJ1aWxkaW5nIGEgY29ycHVzIGRvY3VtZW50DQo8cCBhbGlnbj0ianVzdGlmeSI+QSBjb3JwdXMgaXMgYSBjb2xsZWN0aW9uIG9mIGRvY3VtZW50cywgV2UgY3JlYXRlIGEgdm9sYXRpbGUgY29ycHVzIHRvIGZyb20gdGhlIA0KdmVjdG9yIG9mIHRleHRzIG9idGFpbmVkLjwvcD4NCg0KPHAgYWxpZ249Imp1c3RpZnkiPk1ha2UgYSB2ZWN0b3Igc291cmNlIHVzaW5nIHRoZSB0bSBwYWNrYWdlLCB0aGVuIGNvbnZlcnRpbmcgDQp0aGUgc291cmNlIHZlY3RvciBpbnRvIGEgVkNvcnB1cyBvYmplY3Q8L3A+DQpgYGB7ciBidWlsZC1jb3JwdXN9DQpjcmVhdGVfY29ycHVzID0gZnVuY3Rpb24odGV4dF9kYXRhKXsNCiAgdGV4dF9jb3JwdXMgPSBWQ29ycHVzKA0KICAgIFZlY3RvclNvdXJjZSh0ZXh0X2RhdGEpLA0KICAgICAgcmVhZGVyQ29udHJvbD1saXN0KHJlYWRQbGFpbiwgbGFuZ3VhZ2U9ImVuIiwgbG9hZD1UUlVFKQ0KICApDQogIHRleHRfY29ycHVzDQp9DQpibG9nc19jb3JwdXMgPSBjcmVhdGVfY29ycHVzKGJsb2dzKQ0KbmV3c19jb3JwdXMgPSBjcmVhdGVfY29ycHVzKG5ld3MpDQp0d2l0dGVyX2NvcnB1cyA9IGNyZWF0ZV9jb3JwdXModHdpdHRlcikNCmBgYA0KDQo8cCBhbGlnbj0ianVzdGlmeSI+VGhlIFZDb3JwdXMgb2JqZWN0IHVzZXMgYSBuZXN0ZWQgLSBsaXN0IG9mIGxpc3Qgc3RydWN0dXJlIHRvIA0KaG9sZCB0aGUgZGF0YS4gQXQgZWFjaCBpbmRleCBvZiB0aGUgVkNvcnB1cyBvYmplY3QsIHRoZXJlIGlzIGEgUGxhaW5UZXh0RG9jdW1lbnQNCm9iamVjdCwgd2hpY2ggaXMgYSBsaXN0IGNvbnRhaW5pbmcgYWN0dWFsIHRleHQgZGF0YSAoY29udGVudCksIGFuZCBzb21lDQpjb3JyZXNwb25kaW5nIG1ldGFkYXRhIChtZXRhKS4gSXQgY2FuIGhlbHAgdG8gdmlzdWFsaXplIGEgVkNvcnB1cyBvYmplY3QgdG8gDQpjb25jZXB0dWFsaXplIHRoZSB3aG9sZSB0aGluZy48L3A+DQoNCiMjIyBDbGVhbmluZyBhbmQgcHJlcHJvY2Vzc2luZyB0ZXh0DQo8cCBhbGlnbj0ianVzdGlmeSI+VXNpbmcgdG0ncyBidWlsdC1pbiB0ZXh0IHByb2Nlc3NpbmcgbWV0aG9kcyB0byBtaW5lIGRhdGEgZnJvbSANCnRoZSBjb3JwdXMuPC9wPg0KYGBge3IgY2xlYW4tY29ycHVzfQ0KY2xlYW5fY29ycHVzIDwtIGZ1bmN0aW9uIChjb3JwdXMpIHsNCiAgICBjb3JwdXMgPC0gdG1fbWFwKGNvcnB1cywgdG9sb3dlcikgIyBhbGwgbG93ZXJjYXNlDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHJlbW92ZVB1bmN0dWF0aW9uKSAjIEVsZW1pbmF0ZSBwdW5jdHVhdGlvbg0KICAgIGNvcnB1cyA8LSB0bV9tYXAoY29ycHVzLCByZW1vdmVOdW1iZXJzKSAjIEVsaW1pbmF0ZSBudW1iZXJzDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHJlcGxhY2VfYWJicmV2aWF0aW9uKSAjIEVsaW1pbmF0ZSBhYmJyZXZpYXRpb25zDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHJlcGxhY2VfY29udHJhY3Rpb24pICMgRWxpbWluYXRlIGNvbnRyYWN0aW9ucw0KICAgIGNvcnB1cyA8LSB0bV9tYXAoY29ycHVzLCByZXBsYWNlX3N5bWJvbCkgIyBFbGltaW5hdGUgc3ltYm9scw0KICAgIGNvcnB1cyA8LSB0bV9tYXAoY29ycHVzLCBzdHJpcFdoaXRlc3BhY2UpICMgU3RyaXAgV2hpdGVzcGFjZQ0KICAgIGNvcnB1cyA8LSB0bV9tYXAoY29ycHVzLCByZW1vdmVXb3Jkcywgc3RvcHdvcmRzKCJlbmdsaXNoIikpICMgRWxpbWluYXRlIEVuZ2xpc2ggc3RvcCB3b3Jkcw0KICAgICMgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHN0ZW1Eb2N1bWVudCkgIyBTdGVtIHRoZSBkb2N1bWVudA0KICAgIGNvcnB1cyA8LSB0bV9tYXAoY29ycHVzLCBQbGFpblRleHREb2N1bWVudCkgIyBDcmVhdGUgcGxhaW4gdGV4dCBmb3JtYXQNCn0NCg0KdGV4dF9jb3JwdXMgPSBjKG5ld3NfY29ycHVzLGJsb2dzX2NvcnB1cyx0d2l0dGVyX2NvcnB1cywgcmVjdXJzaXZlID0gRkFMU0UpDQp0ZXh0X2NvcnB1c19jbGVhbmVkID0gY2xlYW5fY29ycHVzKHRleHRfY29ycHVzKQ0KDQojIENvbXBhcmluZyB3aXRoIG9yaWdpbmFsIGRhdGENCmNhdCgiT3JpZ2luYWwgZG9jdW1lbnQ6ICIsY29udGVudCh0ZXh0X2NvcnB1c1tbMV1dKSkNCmNhdCgiXG5DbGVhbmVkIGRvY3VtZW50OiAiLGNvbnRlbnQodGV4dF9jb3JwdXNfY2xlYW5lZFtbMV1dKSkNCg0KIyMgU2F2aW5nIGNvcnB1cyBjbGVhbmVkIA0KZ2V0d2QoKQ0Kd3JpdGVMaW5lcyhhcy5jaGFyYWN0ZXIodGV4dF9jb3JwdXNfY2xlYW5lZCksIGNvbj0iLi4vQ29ycHVzL3RleHRfY29ycHVzX2NsZWFuZWQudHh0IikNCg0KIyBEaXNwb3Npbmcgb2ZmIHRoZSBvcmlnaW5hbCBjb3JwdXMNCnJtKHRleHRfY29ycHVzLCBibG9nc19jb3JwdXMsIG5ld3NfY29ycHVzLCB0d2l0dGVyX2NvcnB1cykNCmBgYA0KDQojIyBDcmVhdGluZyBhIGRvY3VtZW50LXRlcm0gbWF0cml4IGZvciBhbmFseXNpcw0KPHAgYWxpZ249Imp1c3RpZnkiPldoZW4gd2Ugd2lzaCB0byByZXByZXNlbnQgdGhlIGRhdGEgd2l0aCB0aGUgZG9jdW1lbnQgYXMgcm93cyBhbmQgdGhlIHdvcmRzIGFzIA0KY29sdW1uIHdlIHVzZSBkb2N1bWVudCB0ZXJtIG1hdHJpeCwgdGhlIHRyYW5zcG9zZSBvZiB3aGljaCBpcyB0ZXJtIGRvY3VtZW50IA0KbWF0cml4Ljxicj4NClRoZSBmaWVsZHMgdGhlbiByZXByZXNlbnQgdGhlIGZyZXF1ZW5jeSBvZiB3b3JkcyBpbiB0aGUgZGF0YS4gSG93ZXZlciwgb3RoZXINCmZyZXF1ZW5jeSBtZWFzdXJlcyBkbyBleGlzdC48L3A+DQoNCmBgYHtyIGNyZWF0ZS1UZXJtRG9jdW1lbnQtTWF0cml4fQ0KdGV4dF90ZG0gPSBUZXJtRG9jdW1lbnRNYXRyaXgodGV4dF9jb3JwdXNfY2xlYW5lZCkNCiMgcm0odGV4dF9jb3JwdXNfY2xlYW5lZCkNCnRleHRfdGRtDQpgYGANCg0KIyMgQ29udmVydCB0ZXJtIGRvY3VtZW50IG1hdHJpeCB0byBtYXRyaXgNClRoZSB0ZXJtIGRvY3VtZW50IGlzIGNvbnZlcnRlZCBpbnRvIGEgbGFyZ2UgbWF0cml4IGluIHdoaWNoIGVhY2ggY2VsbCByZXByZXNlbnRzIA0KdGhlIGNvdW50L2ZyZXF1ZW5jeSBvZiB0aGUgd29yZChyb3cpIGluIHRoZSBjb3JyZXNwb25kaW5nIGRvY3VtZW50KGNvbHVtbikuIA0KYGBge3IgY29udmVydC10ZG0tdG8tbX0NCnRleHRfbSA9IGFzLm1hdHJpeCh0ZXh0X3RkbSkNCmBgYA0KDQojIEV4cGxvcmF0b3J5IGFuYWx5c2lzDQo8cCBhbGlnbj0ianVzdGlmeSI+VXNpbmcgcWRhcCdzIGZyZV90ZXJtcygpIGZ1bmN0aW9ucyB0byBjb3VudCB0aGUgZnJlcXVlbmN5IG9mIA0Kd29yZHMgaW4gdGhlIGRhdGFzZXRzIGFuZCBwcmVzZW50aW5nIHRoZSBpbmZvcm1hdGlvbiBpbiB0YWJ1bGFyIGFuZCBncmFwaGljYWwgDQptZXRob2RzLjwvcD4NCg0KIyMgTW9zdCBmcmVxdWVudGx5IHVzZWQgd29yZHMNCmBgYHtyIHRlcm0tZnJlcXVlbmN5LWJhcnBsb3R9DQp0ZXJtX2ZyZXF1ZW5jeSA9IHJvd1N1bXModGV4dF9tKQ0KdGVybV9mcmVxdWVuY3kgPC0gc29ydCh0ZXJtX2ZyZXF1ZW5jeSwgZGVjcmVhc2luZyA9IFQpDQpybSh0ZXh0X20pDQpiYXJwbG90KHRlcm1fZnJlcXVlbmN5WzE6MTBdLCBjb2wgPSAiaG90cGluazQiLCBsYXMgPSAyLCBtYWluID0gIk1vc3QgZnJlcXVlbnRseSB1c2VkIHdvcmRzIikNCmBgYA0KDQojIyBTZW50aW1lbnQgYW5hbHlzaXMgDQojIyMgQ3JlYXRpbmcgYSB0aWJibGUgDQo8cCBhbGlnbj0ianVzdGlmeSI+Q29udmVydGluZyB0aGUgdHdpdHRlcl9kdG0gdG8gYSB0aWJibGUgZm9yIHNlbnRpbWVudCBhbmFseXNpcyB1c2luZyB0aWR5dGV4dA0KcGFja2FnZS48L3A+DQpgYGB7ciBzZW50aW1lbnQtYW5hbHlzaXMtaW5pdH0NCnRleHRfdGJsID0gdGlkeXRleHQ6OnRpZHkodGV4dF90ZG0pDQp0ZXh0X3RibCA9IHRleHRfdGJsWyxjKCJ0ZXJtIiwiY291bnQiKV0NCnByaW50KGRpbSh0ZXh0X3RibCkpDQpoZWFkKHRleHRfdGJsW29yZGVyKC10ZXh0X3RibCRjb3VudCksXSwgMTApDQpgYGANCg0KIyMjIEZvcm1pbmcgYW5hbHlzaXMNCmBgYHtyIHNlbnRpbWVudC1hbmFseXNpcy1jcmVhdGV9DQp0ZXh0X3NlbnRpbWVudHMgPC0gdGV4dF90YmwgJT4lDQogIGlubmVyX2pvaW4oZ2V0X3NlbnRpbWVudHMoImJpbmciKSwgYnkgPSBjKHRlcm0gPSAid29yZCIpKQ0KcHJpbnQoZGltKHRleHRfc2VudGltZW50cykpDQpoZWFkKHRleHRfc2VudGltZW50cywgMTApDQpgYGANCg0KIyMjIFZpc3VhbGl6aW5nDQpgYGB7ciBzZW50aW1lbnQtYW5hbHlzaXMtcGxvdH0NCnRleHRfc2VudGltZW50cyAlPiUNCiAgY291bnQoc2VudGltZW50LCB0ZXJtLCB3dCA9IGNvdW50KSAlPiUNCiAgZmlsdGVyKG4gPj0gMzUpICU+JQ0KICBtdXRhdGUobiA9IGlmZWxzZShzZW50aW1lbnQgPT0gIm5lZ2F0aXZlIiwgLW4sIG4pKSAlPiUNCiAgbXV0YXRlKHRlcm0gPSByZW9yZGVyKHRlcm0sIG4pKSAlPiUNCiAgZ2dwbG90KGFlcyh0ZXJtLCBuLCBmaWxsID0gc2VudGltZW50KSkgKyANCiAgdGhlbWVfbWluaW1hbCgpICsNCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIpICsNCiAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGU9OTAsaGp1c3Q9MSkpICsgI2VsZW1lbnRfYmxhbmsoKSkgKw0KICB5bGFiKCJDb250cmlidXRpb24gdG8gc2VudGltZW50IikNCmBgYA0KDQpgYGB7ciBjbGVhbi11cC10cmlncmFtcywgZWNobyA9IEYsIGVycm9yPUYsIHdhcm5pbmc9Rn0NCnJtKHRleHRfdGJsLCB0ZXh0X3NlbnRpbWVudHMpDQpgYGANCg0KIyMgV29yZCBjbG91ZCANCmBgYHtyIHdvcmQtY2xvdWQtdGV4dH0NCndvcmRfZnJlcXMgPSBkYXRhLmZyYW1lKA0KICB0ZXJtID0gbmFtZXModGVybV9mcmVxdWVuY3kpLA0KICBudW0gPSB0ZXJtX2ZyZXF1ZW5jeQ0KKQ0Kd29yZGNsb3VkOjp3b3JkY2xvdWQoDQogIHdvcmRfZnJlcXMkdGVybSwgd29yZF9mcmVxcyRudW0sIA0KICBtYXgud29yZHMgPSAxMDAsIGNvbG9ycyA9IGNpdmlkaXMobiA9IDMpDQopDQpgYGANCmBgYHtyIGNsZWFuLXVwLWNsb3VkLWZyZXEsIGVjaG8gPSBGLCBlcnJvcj1GLCB3YXJuaW5nPUZ9DQpybSh3b3JkX2ZyZXFzKQ0KYGBgDQoNCiMjIyBDb21wYXJpc29ucyB1c2luZyB3b3JkIGNsb3VkIA0KDQo8cCBhbGlnbj0ianVzdGlmeSI+UHJlcGFyaW5nIHRoZSBkYXRhPC9wPg0KYGBge3IgcHJlcHJvY2Vzcy1mb3Itd29yZGNsb3VkLWNvbXBhcmlzb25zfQ0KYWxsX2Jsb2dzID0gcGFzdGUoYmxvZ3MsIGNvbGxhcHNlID0gIiIpDQphbGxfbmV3cyA9IHBhc3RlKG5ld3MsIGNvbGxhcHNlID0gIiIpDQphbGxfdHdpdHRlciA9IHBhc3RlKHR3aXR0ZXIgLGNvbGxhcHNlID0gIiIpDQphbGxfdGV4dHMgPSBjKGFsbF9ibG9ncywgYWxsX25ld3MsIGFsbF90d2l0dGVyKQ0KDQpybShibG9ncywgbmV3cywgdHdpdHRlcikNCmFsbF90ZXh0cyA9IFZDb3JwdXMoVmVjdG9yU291cmNlKGFsbF90ZXh0cykpDQojIGFsbF90ZXh0cyA9IGNsZWFuX2NvcnB1cyhhbGxfdGV4dHMpDQoNCmFsbF9kbSA9IFRlcm1Eb2N1bWVudE1hdHJpeChhbGxfdGV4dHMpDQphbGxfdGRtID0gVGVybURvY3VtZW50TWF0cml4KGFsbF90ZXh0cykNCmNvbG5hbWVzKGFsbF90ZG0pID0gYygiQmxvZ3MiLCAiTmV3cyIsICJUd2l0dGVyIikNCmFsbF9tID0gYXMubWF0cml4KGFsbF9kbSkNCmFsbF9tYyA9IGFzLm1hdHJpeChhbGxfdGRtKQ0KYGBgDQoNCiMjIyMgQ29tbW9uYWxpdHkNCjxwIGFsaWduPSJqdXN0aWZ5Ij5Vc2luZyBjb21tb25hbGl0eSB3b3JkIGNsb3VkIHRvIGhvdyBzaW1pbGFyIHRoZSB0aHJlZSBjb3JwdXMgDQphcmU8L3A+DQpgYGB7ciB3b3JkY2xvdWQtaW50ZXJzZWN0aW9uLCB3YXJuaW5nPUZ9DQp3b3JkY2xvdWQ6OmNvbW1vbmFsaXR5LmNsb3VkKGFsbF9tLCBjb2xvcnMgPSBtYWdtYShuID0gNSksIG1heC53b3JkcyA9IDEwMCkNCmBgYCAgDQoNCmBgYHtyfQ0Kcm0oYWxsX20sIGFsbF9kbSkNCmBgYA0KDQoNCiMjIyMgQ29tcGFyaXNvbg0KPHAgYWxpZ249Imp1c3RpZnkiPlVzaW5nIGNvbXBhcmlzb24gY2xvdWQgdG8gdW5kZXJzdGFuZCB0aGUgZGlzdHJpYnV0aW9uIG9mIA0Kd29yZHMgaW4gZWFjaCBjYXRlZ29yeSBvZiB0ZXh0cyAtIGJsb2dzLCBuZXdzIGFuZCB0d2l0dGVyPC9wPg0KYGBge3Igd29yZC1jbG91ZC1kaWZmZXJlbmNlLCB3YXJuaW5nPUZ9DQp3b3JkY2xvdWQ6OmNvbXBhcmlzb24uY2xvdWQoYWxsX21jLCBjb2xvcnMgPSBjKCJvcmFuZ2UiLCJza3libHVlIiwiaG90cGluazMiKSwgbWF4LndvcmRzID0gMTAwKQ0KYGBgDQoNCiMjIFBvbGFpemVkIHRhZyBwbG90IA0KDQojIyMgQ3JlYXRpbmcgZGF0YSBmb3IgcGxvdA0KPHAgYWxpZ249Imp1c3RpZnkiPnVzaW5nIHRoZSBweXJhbWlkIHBhY2thZ2UgPC9icj4NCmJsb2dzIGFuZCBuZXdzOiA8L3A+DQpgYGB7cn0NCiMgc3Vic2V0IHRoZSBjb21tb24gd29yZHMgaW4gdGhlIGRvY3VtZW50cw0KY29tbW9uX3dvcmRzID0gYXMuZGF0YS5mcmFtZShzdWJzZXQoYWxsX21jLCBhbGxfbWNbLDFdPjAgJiBhbGxfbWNbLDJdPjAgJiBhbGxfbWNbLDNdPjApKQ0KIyBGaW5kaW5nIHRoZSBkaWZmZXJlbmNlIGFuZCB0aGVuIG9yZGVyaW5nIGJ5IGl0DQpjb21tb25fd29yZHMgPSBtdXRhdGUoY29tbW9uX3dvcmRzLCANCiAgICAgICAgICAgICAgICAgICAgICBkaWZmX2JuID0gYWJzKGNvbW1vbl93b3Jkc1ssMV0gLSBjb21tb25fd29yZHNbLDJdKSwNCiAgICAgICAgICAgICAgICAgICAgICBkaWZmX2J0ID0gYWJzKGNvbW1vbl93b3Jkc1ssMV0gLSBjb21tb25fd29yZHNbLDNdKSwNCiAgICAgICAgICAgICAgICAgICAgICBkaWZmX250ID0gYWJzKGNvbW1vbl93b3Jkc1ssMl0gLSBjb21tb25fd29yZHNbLDNdKSwNCiAgICAgICAgICAgICAgICAgICAgICBsYWJlbHMgPSByb3duYW1lcyhjb21tb25fd29yZHMpDQopDQpjb21tb25fd29yZHMgPSBjb21tb25fd29yZHNbb3JkZXIoLWNvbW1vbl93b3Jkc1ssNF0pLF0NCnRvcF8yNV9ibiA9IGNvbW1vbl93b3Jkc1sxOjI1LF0NCmNvbW1vbl93b3JkcyA9IGNvbW1vbl93b3Jkc1tvcmRlcigtY29tbW9uX3dvcmRzWyw1XSksXQ0KdG9wXzI1X2J0ID0gY29tbW9uX3dvcmRzWzE6MjUsXQ0KY29tbW9uX3dvcmRzID0gY29tbW9uX3dvcmRzW29yZGVyKC1jb21tb25fd29yZHNbLDZdKSxdDQp0b3BfMjVfbnQgPSBjb21tb25fd29yZHNbMToyNSxdDQpgYGANCg0KIyMjIERpZmZlcmVuY2UgYmV0d2VlbiBjb21tb24gdGVybXMgaW4gYmxvZ3MgYW5kIG5ld3MNCmBgYHtyIHB5cmFtaWQtcGxvdC1ibG9ncy12cy1uZXdzfQ0KcHlyYW1pZC5wbG90KA0KICB0b3BfMjVfYm4kQmxvZ3MsIHRvcF8yNV9ibiROZXdzLCBsYWJlbHMgPSB0b3BfMjVfYm4kbGFiZWxzLA0KICBtYWluID0gIldvcmRzIGluIGNvbW1vbiBiZXR3ZWVuIGJsb2dzIGFuZCBuZXdzIiwgZ2FwID0gMTUwLA0KICB1bml0ID0gTlVMTCwgcmF4bGFiID0gTlVMTCwgbGF4bGFiID0gTlVMTCwgdG9wLmxhYmVscyA9IA0KICAgIGMoImJsb2dzIiwgIndvcmRzIiwgIm5ld3MiKQ0KKQ0KYGBgDQoNCg0KIyMjIERpZmZlcmVuY2UgYmV0d2VlbiBjb21tb24gdGVybXMgaW4gYmxvZ3MgYW5kIHR3aXR0ZXINCmBgYHtyIHB5cmFtaWQtcGxvdC1ibG9ncy12cy10d2l0dGVyfQ0KcHlyYW1pZC5wbG90KA0KICB0b3BfMjVfYnQkQmxvZ3MsIHRvcF8yNV9idCROZXdzLCBsYWJlbHMgPSB0b3BfMjVfYnQkbGFiZWxzLA0KICBtYWluID0gIldvcmRzIGluIGNvbW1vbiBiZXR3ZWVuIGJsb2dzIGFuZCBuZXdzIiwgZ2FwID0gMTAwLA0KICB1bml0ID0gTlVMTCwgcmF4bGFiID0gTlVMTCwgbGF4bGFiID0gTlVMTCwgdG9wLmxhYmVscyA9IA0KICAgIGMoImJsb2dzIiwgIndvcmRzIiwgInR3aXR0ZXIiKQ0KKQ0KYGBgDQoNCg0KIyMjIERpZmZlcmVuY2UgYmV0d2VlbiBjb21tb24gdGVybXMgaW4gbmV3cyBhbmQgdHdpdHRlcg0KYGBge3IgcHlyYW1pZC1wbG90LW5ld3MtdnMtdHdpdHRlcn0NCnB5cmFtaWQucGxvdCgNCiAgdG9wXzI1X250JEJsb2dzLCB0b3BfMjVfbnQkTmV3cywgbGFiZWxzID0gdG9wXzI1X250JGxhYmVscywNCiAgbWFpbiA9ICJXb3JkcyBpbiBjb21tb24gYmV0d2VlbiBibG9ncyBhbmQgbmV3cyIsIGdhcCA9IDIwMCwNCiAgdW5pdCA9IE5VTEwsIHJheGxhYiA9IE5VTEwsIGxheGxhYiA9IE5VTEwsIHRvcC5sYWJlbHMgPSANCiAgICBjKCJuZXdzIiwgIndvcmRzIiwgInR3aXR0ZXIiKQ0KKQ0KYGBgIA0KDQpgYGB7ciBjbGVhbi11cC1hbGwsIGVjaG8gPSBGLCBlcnJvcj1GLCB3YXJuaW5nPUZ9DQpybSh0b3BfMjVfbnQsIGNvbW1vbl93b3JkcywgdG9wXzI1X2J0LCB0b3BfMjVfYm4sIGFsbF9tYywgYWxsX3RleHRzLCBhbGxfdHdpdHRlciwgYWxsX25ld3MsIGFsbF9ibG9ncywgYWxsX3RkbSkNCmBgYA0KDQoNCiMjIEFuYWx5emluZyB3b3JkcyB1c2luZyBkZW5kcm9ncmFtIHBsb3QNCjxwIGFsaWduPSJqdXN0aWZ5Ij5EZW5kcm9ncmFtcyByZWR1Y2UgY29tcGxpY2F0ZWQgbXVsdGktZGltZW5zaW9uYWwgZGF0YXNldHMgdG8gc2ltcGxlIGNsdXN0ZXJpbmcNCmluZm9ybWF0aW9uLiBUaGlzIG1ha2VzIHRoZW0gYSB2YWx1YWJsZSB0b29sIHRvIHJlZHVjZSBjb21wbGV4aXR5LiBVc2luZyB0aGUNCmRpc3RhbmNlIG1hdHJpeCBhbmQgaGNsdXN0KCkgZnVuY3Rpb24gd2UgY3JlYXRlIGEgaGllcmFyY2hpY2FsIGNsdXN0ZXIgb2JqZWN0DQp3aGljaCBpcyB0aGVuIHBhc3NlZCBpbnRvIHRoZSBmdW5jdGlvbiBhcy5kZW5kcm9ncmFtLjwvYnI+DQo8L2JyPg0KUmVtb3Zpbmcgc3BhcnNpdHkgb2YgdGhlIHRlcm0gZG9jdW1lbnQgdXNpbmcgdGhlIHJlbW92ZVNwYXJzZVRlcm1zIHRvIHJlZHVjZSB0aGUNCm51bWJlciBvZiB0ZXJtcywgdGhlIHBhcmFtZXRlciAnc3BhcnNlJyBzcGVjaWVzIHRoZSBwZXJjZW50IGN1dC1vZmYgZm9yIG51bWJlciANCm9mIHplcm9lcyB0aGF0IGlzIGFsbG93ZWQgZm9yIGVhY2ggdGVybS48L3A+DQpgYGB7ciBwcmVwYXJlZGF0YS1kZW5kcm9ncmFtfQ0KIyBSZW1vdmluZyBzcGFyc2UgdGVybXMgDQp0ZXh0X3JlZHVjZWQgPSByZW1vdmVTcGFyc2VUZXJtcyh0ZXh0X3RkbSwgc3BhcnNlID0gMC45NykNCnRleHRfcmVkdWNlZF9tID0gYXMubWF0cml4KHRleHRfcmVkdWNlZCkNCnRleHRfcmVkdWNlZF9kaXN0ID0gZGlzdCh0ZXh0X3JlZHVjZWRfbSkNCg0KIyBDcmVhdGluZyBoY2x1c3Qgb2JqZWN0DQp0ZXh0X2hjID0gaGNsdXN0KHRleHRfcmVkdWNlZF9kaXN0KQ0KDQojIENvbnZlcnRpbmcgaGNsdXN0IG9iamVjdCB0byBkZW5kcm9ncmFtDQp0ZXh0X2RlbmQgPSBhcy5kZW5kcm9ncmFtKHRleHRfaGMpDQoNCiMgTGFiZWxzIG9mIGRlbmRyb2dyYW0gb2JqZWN0DQpsYWJlbHModGV4dF9kZW5kKQ0KYGBgDQpgYGB7ciBkZW5kcm9ncmFtLXBsb3R9DQojIENoYW5naW5nIGNvbG9yIG9mIGJyYW5jaGVzICd5ZWFyJywgJ2xvdmUnIGFuZCAnc2FpZCcgdG8gcmVkDQp0ZXh0X2RlbmRfY29sb3JlZCA9IGJyYW5jaGVzX2F0dHJfYnlfbGFiZWxzKA0KICB0ZXh0X2RlbmQsIA0KICBjKCJ0d28iLCJ3aWxsIiwic2FpZCIpLA0KICAicmVkIg0KKQ0KIyBQbG90DQpwbG90KHRleHRfZGVuZF9jb2xvcmVkLCBtYWluID0gIkRlbmRyb2dyYW0gYW5hbHlzaXMiKQ0KDQojIEFkZGluZyByZWN0YW5nbGVzDQpyZWN0LmRlbmRyb2dyYW0odHJlZSA9IHRleHRfZGVuZF9jb2xvcmVkLCBrID0gMywgYm9yZGVyID0gImdyZXk1MCIpDQpgYGANCg0KYGBge3IgY2xlYW4tdXAtZGVuZCwgZWNobyA9IEYsIGVycm9yPUYsIHdhcm5pbmc9Rn0NCnJtKHRleHRfZGVuZCwgdGV4dF9kZW5kX2NvbG9yZWQsIHRleHRfaGMsIHRleHRfcmVkdWNlZCwgdGV4dF9yZWR1Y2VkX20pDQpgYGANCg0KIyMgV29yZCBhc3NvY2lhdGlvbnMNCjxwIGFsaWduPSJqdXN0aWZ5Ij5Vc2luZyB0aGUgZmluZEFzc29jcygpIGZ1bmN0aW9uIG9mIHRtIHBhY2thZ2UgYW5kIGNhbGN1bGF0aW5nIHRoZSBjb3JyZWxhdGlvbiBvZg0KYSB3b3JkIHdpdGggZXZlcnkgb3RoZXIgd29yZHMvdGVybXMgaW4gdGhlIGRvY3VtZW50IGluIHRoZSByYW5nZSBbMCwxXS48L3A+DQpgYGB7ciBhc3NvY2lhdGlvbi1hbmFseXNpc30NCnRleHRfYXNzb2NpYXRpb25zID0gZmluZEFzc29jcyh0ZXh0X3RkbSwgInllYXIiLCAwLjEyNSkNCg0KIyBDb252ZXJ0aW5nIHRvIGRhdGFmcmFtZSBmb3IgcGxvdA0KdGV4dF9hc3NvY2lhdGlvbnNfZGYgPSBsaXN0X3ZlY3QyZGYoDQogIHRleHRfYXNzb2NpYXRpb25zLCBjb2wyID0gIndvcmQiLCBjb2wzID0gInNjb3JlIg0KKQ0KIyBwbG90DQpnZ3Bsb3QodGV4dF9hc3NvY2lhdGlvbnNfZGYsIGFlcyhzY29yZSwgd29yZCkpICsNCiAgZ2VvbV9wb2ludChzaXplID0gMykgKyANCiAgdGhlbWVfbWluaW1hbCgpDQpybSh0ZXh0X2Fzc29jaWF0aW9ucywgdGV4dF9hc3NvY2lhdGlvbnNfZGYsIHRleHRfdGRtKQ0KYGBgDQoNCiMjIE4tZ3JhbSB0b2tlbml6ZQ0KU28gZmFyIHdlJ3ZlIHN0dWRpZWQgdGhlIGFzc29jaWF0aW9uIG9mIGEgdG9rZW4gY29udGFpbmluZyBqdXN0IG9uZSB3b3JkIHdpdGggDQpvdGhlciB3b3Jkcy90b2tlbnMsIHRoaXMgcGFydCBvZiB0aGUgYW5hbHlzaXMgY29uY2VudHJhdGVzIG9uIGFuYWx5c2lzIG9mIA0KdG9rZW5zIGNvbnRhaW5pbmcgbW9yZSB0aGFuIG9uZSB3b3JkLg0KDQojIyMgRGVmaW5pbmcgZnVuY3Rpb25zDQpgYGB7ciB0b2tlbml6ZS1mdW5jdGlvbi1kZWZpbml0aW9ufQ0KIyBDcmVhdGluZyBhIHRva2VuaXplciBmdW5jdGlvbnMgdXNpbmcgdGhlIFJXZWthIHBhY2thZ2UNCmJpZ3JhbV90b2tlbml6ZXIgPSBmdW5jdGlvbih4KXsNCiAgTkdyYW1Ub2tlbml6ZXIoeCwgV2VrYV9jb250cm9sKG1pbiA9IDIsIG1heCA9IDIpKQ0KfQ0KdHJpZ3JhbV90b2tlbml6ZXIgPSBmdW5jdGlvbih4KXsNCiAgTkdyYW1Ub2tlbml6ZXIoeCwgV2VrYV9jb250cm9sKG1pbiA9IDMsIG1heCA9IDMpKQ0KfQ0KdGV0cmFncmFtX3Rva2VuaXplciA9IGZ1bmN0aW9uKHgpew0KICBOR3JhbVRva2VuaXplcih4LCBXZWthX2NvbnRyb2wobWluID0gNCwgbWF4ID0gNCkpDQp9DQpwZW50YWdyYW1fdG9rZW5pemVyID0gZnVuY3Rpb24oeCl7DQogIE5HcmFtVG9rZW5pemVyKHgsIFdla2FfY29udHJvbChtaW4gPSA1LCBtYXggPSA1KSkNCn0NCmBgYA0KDQojIyMgQmlncmFtcw0KIyMjIyBDcmVhdGluZyBhIGJpZ3JhbSB0ZG0NCmBgYHtyfQ0KYmlncmFtX3RkbSA9IFRlcm1Eb2N1bWVudE1hdHJpeCgNCiAgdGV4dF9jb3JwdXNfY2xlYW5lZCwNCiAgY29udHJvbCA9IGxpc3QodG9rZW5pemUgPSBiaWdyYW1fdG9rZW5pemVyKQ0KKQ0KYmlncmFtX20gPSBhcy5tYXRyaXgoYmlncmFtX3RkbSkNCmBgYA0KIyMjIyB3b3JkY2xvdWQgYW5hbHlzaXMNCmBgYHtyIGJpZ3JhbS1jbG91ZCwgd2FybmluZz1GfQ0KZnJlcSA9IHJvd1N1bXMoYmlncmFtX20pDQpiaV90b2tlbnMgPSBuYW1lcyhmcmVxKQ0KYmlfdG9rZW5fZGYgPSBkYXRhLmZyYW1lKHRva2VuID0gYmlfdG9rZW5zLCBmcmVxID0gZnJlcSkNCnJvdy5uYW1lcyhiaV90b2tlbl9kZikgPSBOVUxMDQp3b3JkY2xvdWQ6OndvcmRjbG91ZChiaV90b2tlbl9kZiR0b2tlbiwgYmlfdG9rZW5fZGYkZnJlcSwgbWF4LndvcmRzID0gMTUwLCBjb2xvcnMgPSBjaXZpZGlzKG4gPSAzKSkNCmBgYCAgDQoNCg0KYGBge3IgY2xlYW4tdXAtYmlncmFtcywgZWNobyA9IEYsIGVycm9yPUYsIHdhcm5pbmc9Rn0NCnJtKGJpZ3JhbV9tLCBiaWdyYW1fdGRtLCBiaV90b2tlbnMsIGZyZXEsIHRvcF9iaWdyYW1zLCBiaV90b2tlbl9kZikNCmBgYA0KDQoNCiMjIyBUcmlncmFtcw0KIyMjIyBDcmVhdGluZyBhIHRyaWdyYW0gdGRtDQpgYGB7cn0NCnRyaWdyYW1fdGRtID0gVGVybURvY3VtZW50TWF0cml4KA0KICB0ZXh0X2NvcnB1c19jbGVhbmVkLA0KICBjb250cm9sID0gbGlzdCh0b2tlbml6ZSA9IHRyaWdyYW1fdG9rZW5pemVyKQ0KKQ0KdHJpZ3JhbV9tID0gYXMubWF0cml4KHRyaWdyYW1fdGRtKQ0KYGBgDQojIyMjIHdvcmRjbG91ZCBhbmFseXNpcw0KYGBge3IgdHJpZ3JhbS1jbG91ZCwgd2FybmluZz1GfQ0KZnJlcSA9IHJvd1N1bXModHJpZ3JhbV9tKQ0KdHJpX3Rva2VucyA9IG5hbWVzKGZyZXEpDQp0cmlfdG9rZW5fZGYgPSBkYXRhLmZyYW1lKHRva2VuID0gdHJpX3Rva2VucywgZnJlcSA9IGZyZXEpDQpyb3cubmFtZXModHJpX3Rva2VuX2RmKSA9IE5VTEwNCndvcmRjbG91ZDo6d29yZGNsb3VkKA0KICB3b3JkcyA9IHRyaV90b2tlbl9kZiR0b2tlbiwgZnJlcSA9IHRyaV90b2tlbl9kZiRmcmVxLCANCiAgbWF4LndvcmRzID0gMTUwLCBjb2xvcnMgPSBjaXZpZGlzKG4gPSAzKQ0KKQ0KYGBgICANCg0KDQpgYGB7ciBjbGVhbi11cC10cmlncmFtLCBlY2hvID0gRiwgZXJyb3I9Riwgd2FybmluZz1GfQ0Kcm0odHJpZ3JhbV9tLCB0cmlncmFtX3RkbSwgdHJpX3Rva2VucywgZnJlcSwgdHJpX3Rva2VuX2RmLCB0b3BfdHJpZ3JhbXMpDQpgYGANCg0KIyMjIFRldHJhZ3JhbXMNCiMjIyMgQ3JlYXRpbmcgYSB0ZXRyYWdyYW0gdGRtDQpgYGB7cn0NCnRldHJhZ3JhbV90ZG0gPSBUZXJtRG9jdW1lbnRNYXRyaXgoDQogIHRleHRfY29ycHVzX2NsZWFuZWQsDQogIGNvbnRyb2wgPSBsaXN0KHRva2VuaXplID0gdGV0cmFncmFtX3Rva2VuaXplcikNCikNCnRldHJhZ3JhbV9tID0gYXMubWF0cml4KHRldHJhZ3JhbV90ZG0pDQpgYGANCiMjIyMgd29yZGNsb3VkIGFuYWx5c2lzDQpgYGB7ciB0ZXRyYWdyYW0taGVhZCwgd2FybmluZz1GfQ0KZnJlcSA9IHJvd1N1bXModGV0cmFncmFtX20pDQp0ZXRyYV90b2tlbnMgPSBuYW1lcyhmcmVxKQ0KdGV0cmFfdG9rZW5fZGYgPSBkYXRhLmZyYW1lKHRva2VuID0gdGV0cmFfdG9rZW5zLCBmcmVxID0gZnJlcSkNCnJvdy5uYW1lcyh0ZXRyYV90b2tlbl9kZikgPSBOVUxMDQpoZWFkKHRldHJhX3Rva2VuX2RmW29yZGVyKC10ZXRyYV90b2tlbl9kZiRmcmVxKSxdKQ0KYGBgICANCmBgYHtyIHRldHJhZ3JhbS1jbG91ZCwgd2FybmluZz1GfQ0Kd29yZGNsb3VkOjp3b3JkY2xvdWQoDQogIHdvcmRzID0gdGV0cmFfdG9rZW5fZGYkdG9rZW4sIGZyZXEgPSB0ZXRyYV90b2tlbl9kZiRmcmVxLCANCiAgbWF4LndvcmRzID0gMTUwLCBjb2xvcnMgPSBjaXZpZGlzKG4gPSA1KQ0KKQ0KYGBgDQoNCg0KYGBge3IgY2xlYW4tdXAtdGV0cmFncmFtcywgZWNobyA9IEYsIGVycm9yPUYsIHdhcm5pbmc9Rn0NCnJtKHRldHJhZ3JhbV9tLCB0ZXRyYWdyYW1fdGRtLCB0ZXRyYV90b2tlbnMsIGZyZXEsIHRvcF90ZXRyYWdyYW1zLCB0ZXRyYV90b2tlbl9kZikNCmBgYA0KDQojIENyZWF0aW5nIHByZWRpY3Rpb24gbW9kZWwgICANCg0KIyMgQnVpbGRpbmcgTi1HcmFtcw0KDQojIyMgTi1HcmFtcyANCg0KTG9hZGluZy9EZWZpbmluZyBkYXRhIGFuZCBmdW5jdGlvbnMgDQpgYGB7cn0NCiMjIENyZWF0ZSBjb3JwdXMgDQpjcmVhdGVfY29ycHVzID0gZnVuY3Rpb24odGV4dF9kYXRhKXsNCiAgdGV4dF9jb3JwdXMgPSBWQ29ycHVzKA0KICAgIFZlY3RvclNvdXJjZSh0ZXh0X2RhdGEpLA0KICAgICAgcmVhZGVyQ29udHJvbD1saXN0KHJlYWRQbGFpbiwgbGFuZ3VhZ2U9ImVuIiwgbG9hZD1UUlVFKQ0KICApDQogIHRleHRfY29ycHVzDQp9DQojIyBDb3JwdXMgY2xlYW4gZnVuY3Rpb24NCmNsZWFuX2NvcnB1c19tZGwgPC0gZnVuY3Rpb24gKGNvcnB1cykgew0KICAgIGNvcnB1cyA8LSB0bV9tYXAoY29ycHVzLCB0b2xvd2VyKSAjIGFsbCBsb3dlcmNhc2UNCiAgICBjb3JwdXMgPC0gdG1fbWFwKGNvcnB1cywgcmVtb3ZlUHVuY3R1YXRpb24pICMgRWxlbWluYXRlIHB1bmN0dWF0aW9uDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHJlbW92ZU51bWJlcnMpICMgRWxpbWluYXRlIG51bWJlcnMNCiAgICBjb3JwdXMgPC0gdG1fbWFwKGNvcnB1cywgcmVwbGFjZV9hYmJyZXZpYXRpb24pICMgRWxpbWluYXRlIGFiYnJldmlhdGlvbnMNCiAgICBjb3JwdXMgPC0gdG1fbWFwKGNvcnB1cywgcmVwbGFjZV9jb250cmFjdGlvbikgIyBFbGltaW5hdGUgY29udHJhY3Rpb25zDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHJlcGxhY2Vfc3ltYm9sKSAjIEVsaW1pbmF0ZSBzeW1ib2xzDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIHN0cmlwV2hpdGVzcGFjZSkgIyBTdHJpcCBXaGl0ZXNwYWNlDQogICAgY29ycHVzIDwtIHRtX21hcChjb3JwdXMsIFBsYWluVGV4dERvY3VtZW50KSAjIENyZWF0ZSBwbGFpbiB0ZXh0IGZvcm1hdA0KfQ0Kc2V0LnNlZWQoMTkzKQ0Kc2FtcGxlX3NpemUgPSA1MDAwDQoNCk5ncmFtX3N5dGhlc2l6ZSA9IGZ1bmN0aW9uKGNvcnB1cyxuKXsNCiAgdGRtID0gVGVybURvY3VtZW50TWF0cml4KA0KICAgIGNvcnB1cywNCiAgICBjb250cm9sID0gbGlzdCh0b2tlbml6ZSA9IGZ1bmN0aW9uKHgpew0KICAgICAgTkdyYW1Ub2tlbml6ZXIoeCwgV2VrYV9jb250cm9sKG1pbiA9IG4sIG1heCA9IG4pKQ0KICAgIH0pDQogICkNCiAgbSA9IGFzLm1hdHJpeCh0ZG0pDQogIHJtKHRkbSkNCiAgZnJlcSA9IHJvd1N1bXMobSkNCiAgdG9rZW5zID0gbmFtZXMoZnJlcSkNCiAgcm0obSkNCiAgdG9rZW5fZGYgPSBkYXRhLmZyYW1lKHRva2VuID0gdG9rZW5zLCBmcmVxID0gZnJlcSkNCiAgcm0odG9rZW5zLGZyZXEpDQogIHJvdy5uYW1lcyh0b2tlbl9kZikgPSBOVUxMDQogIHRva2VuX2RmID0gZmlsdGVyKHRva2VuX2RmLCBmcmVxPjEpDQp9DQpgYGANCg0KIyMjIyBDcmVhdGluZyBtb2RlbHMgZm9yIEJsb2dzIA0KYGBge3J9DQplbl9ibG9ncyA9IHJlYWRMaW5lcygNCiAgIi4uL2RhdGEvZW5fVVMvZW5fVVMuYmxvZ3MudHh0IiwgZW5jb2Rpbmc9IlVURi04IiwgDQogIHNraXBOdWwgPSBUUlVFLCB3YXJuID0gVFJVRSkNCmJsb2dzID0gZW5fYmxvZ3Nbc2FtcGxlKDE6bGVuZ3RoKGVuX2Jsb2dzKSxzYW1wbGVfc2l6ZSldDQpybShlbl9ibG9ncykNCmJsb2dzID0gZ3N1YigiXFxzKyIsICIgIiwgYmxvZ3MpDQpibG9ncyA9IHN0cl90cmltKGJsb2dzLCBzaWRlID0gYygiYm90aCIpKQ0KYmxvZ3NfY29ycHVzID0gY3JlYXRlX2NvcnB1cyhibG9ncykNCmJsb2dzX2NvcnB1c19jbGVhbmVkID0gY2xlYW5fY29ycHVzX21kbChibG9nc19jb3JwdXMpDQpybShibG9ncyxibG9nc19jb3JwdXMpDQoNCiMjIyBCaWdyYW1zDQpibG9nc19iaV90b2tlbl9kZiA9IE5ncmFtX3N5dGhlc2l6ZShibG9nc19jb3JwdXNfY2xlYW5lZCwyKQ0KDQojIyMgVHJpZ3JhbXMNCmJsb2dzX3RyaV90b2tlbl9kZiA9IE5ncmFtX3N5dGhlc2l6ZShibG9nc19jb3JwdXNfY2xlYW5lZCwzKQ0KDQojIyMgVGV0cmFncmFtcw0KYmxvZ3NfdGV0cmFfdG9rZW5fZGYgPSBOZ3JhbV9zeXRoZXNpemUoYmxvZ3NfY29ycHVzX2NsZWFuZWQsNCkNCg0KIyMjIFBlbnRhZ3JhbXMNCmJsb2dzX3BlbnRhX3Rva2VuX2RmID0gTmdyYW1fc3l0aGVzaXplKGJsb2dzX2NvcnB1c19jbGVhbmVkLDUpDQoNCnJtKGJsb2dzX2NvcnB1c19jbGVhbmVkKQ0KYGBgDQoNCiMjIyMgQ3JlYXRpbmcgbW9kZWxzIGZvciBOZXdzIA0KYGBge3Igd2FybmluZz1GfQ0KZW5fbmV3cyA9IHJlYWRMaW5lcygNCiAgIi4uL2RhdGEvZW5fVVMvZW5fVVMubmV3cy50eHQiLCBlbmNvZGluZz0iVVRGLTgiLCANCiAgc2tpcE51bCA9IFRSVUUsIHdhcm4gPSBUUlVFKQ0KbmV3cyA9IGVuX25ld3Nbc2FtcGxlKDE6bGVuZ3RoKGVuX25ld3MpLHNhbXBsZV9zaXplKV0NCnJtKGVuX25ld3MpDQpuZXdzID0gZ3N1YigiXFxzKyIsICIgIiwgbmV3cykNCm5ld3MgPSBzdHJfdHJpbShuZXdzLCBzaWRlID0gYygiYm90aCIpKQ0KbmV3c19jb3JwdXMgPSBjcmVhdGVfY29ycHVzKG5ld3MpDQpuZXdzX2NvcnB1c19jbGVhbmVkID0gY2xlYW5fY29ycHVzX21kbChuZXdzX2NvcnB1cykNCnJtKG5ld3MsbmV3c19jb3JwdXMpDQoNCiMjIyBCaWdyYW1zDQpuZXdzX2JpX3Rva2VuX2RmID0gTmdyYW1fc3l0aGVzaXplKG5ld3NfY29ycHVzX2NsZWFuZWQsMikNCg0KIyMjIFRyaWdyYW1zDQpuZXdzX3RyaV90b2tlbl9kZiA9IE5ncmFtX3N5dGhlc2l6ZShuZXdzX2NvcnB1c19jbGVhbmVkLDMpDQoNCiMjIyBUZXRyYWdyYW1zDQpuZXdzX3RldHJhX3Rva2VuX2RmID0gTmdyYW1fc3l0aGVzaXplKG5ld3NfY29ycHVzX2NsZWFuZWQsNCkNCg0KIyMjIFBlbnRhZ3JhbXMNCm5ld3NfcGVudGFfdG9rZW5fZGYgPSBOZ3JhbV9zeXRoZXNpemUobmV3c19jb3JwdXNfY2xlYW5lZCw1KQ0KDQpybShuZXdzX2NvcnB1c19jbGVhbmVkKQ0KYGBgDQoNCiMjIyMgQ3JlYXRpbmcgbW9kZWxzIGZvciBUd2l0dGVyIA0KYGBge3J9DQplbl90d2l0dGVyID0gcmVhZExpbmVzKA0KICAiLi4vZGF0YS9lbl9VUy9lbl9VUy50d2l0dGVyLnR4dCIsIGVuY29kaW5nPSJVVEYtOCIsIA0KICBza2lwTnVsID0gVFJVRSwgd2FybiA9IFRSVUUpDQp0d2l0dGVyID0gZW5fdHdpdHRlcltzYW1wbGUoMTpsZW5ndGgoZW5fdHdpdHRlciksc2FtcGxlX3NpemUpXQ0Kcm0oZW5fdHdpdHRlcikNCnR3aXR0ZXIgPSBnc3ViKCJcXHMrIiwgIiAiLCB0d2l0dGVyKQ0KdHdpdHRlciA9IHN0cl90cmltKHR3aXR0ZXIsIHNpZGUgPSBjKCJib3RoIikpDQp0d2l0dGVyX2NvcnB1cyA9IGNyZWF0ZV9jb3JwdXModHdpdHRlcikNCnR3aXR0ZXJfY29ycHVzX2NsZWFuZWQgPSBjbGVhbl9jb3JwdXNfbWRsKHR3aXR0ZXJfY29ycHVzKQ0Kcm0odHdpdHRlciwgdHdpdHRlcl9jb3JwdXMpDQoNCiMjIyBCaWdyYW1zDQp0d2l0dGVyX2JpX3Rva2VuX2RmID0gTmdyYW1fc3l0aGVzaXplKHR3aXR0ZXJfY29ycHVzX2NsZWFuZWQsMikNCg0KIyMjIFRyaWdyYW1zDQp0d2l0dGVyX3RyaV90b2tlbl9kZiA9IE5ncmFtX3N5dGhlc2l6ZSh0d2l0dGVyX2NvcnB1c19jbGVhbmVkLDMpDQoNCiMjIyBUZXRyYWdyYW1zDQp0d2l0dGVyX3RldHJhX3Rva2VuX2RmID0gTmdyYW1fc3l0aGVzaXplKHR3aXR0ZXJfY29ycHVzX2NsZWFuZWQsNCkNCg0KIyMjIFBlbnRhZ3JhbXMNCnR3aXR0ZXJfcGVudGFfdG9rZW5fZGYgPSBOZ3JhbV9zeXRoZXNpemUodHdpdHRlcl9jb3JwdXNfY2xlYW5lZCw1KQ0KDQpybSh0d2l0dGVyX2NvcnB1c19jbGVhbmVkKQ0KYGBgDQoNCiMjIyMgQ29tYmluaW5nIHRoZSBkYXRhDQpgYGB7cn0NCmJpZ3JhbXMgPSByYmluZChibG9nc19iaV90b2tlbl9kZixuZXdzX2JpX3Rva2VuX2RmLHR3aXR0ZXJfYmlfdG9rZW5fZGYpDQp0cmlncmFtcyA9IHJiaW5kKGJsb2dzX3RyaV90b2tlbl9kZixuZXdzX3RyaV90b2tlbl9kZix0d2l0dGVyX3RyaV90b2tlbl9kZikNCnRldHJhZ3JhbXMgPSByYmluZChibG9nc190ZXRyYV90b2tlbl9kZixuZXdzX3RldHJhX3Rva2VuX2RmLHR3aXR0ZXJfdGV0cmFfdG9rZW5fZGYpDQpwZW50YWdyYW1zID0gcmJpbmQoYmxvZ3NfcGVudGFfdG9rZW5fZGYsbmV3c19wZW50YV90b2tlbl9kZix0d2l0dGVyX3BlbnRhX3Rva2VuX2RmKQ0Kcm0oYmxvZ3NfYmlfdG9rZW5fZGYsbmV3c19iaV90b2tlbl9kZix0d2l0dGVyX2JpX3Rva2VuX2RmLA0KICAgYmxvZ3NfdHJpX3Rva2VuX2RmLG5ld3NfdHJpX3Rva2VuX2RmLHR3aXR0ZXJfdHJpX3Rva2VuX2RmLA0KICAgYmxvZ3NfdGV0cmFfdG9rZW5fZGYsbmV3c190ZXRyYV90b2tlbl9kZix0d2l0dGVyX3RldHJhX3Rva2VuX2RmLA0KICAgYmxvZ3NfcGVudGFfdG9rZW5fZGYsbmV3c19wZW50YV90b2tlbl9kZix0d2l0dGVyX3BlbnRhX3Rva2VuX2RmDQopDQpiaWdyYW1zJHdoaWNoID0gMg0KdHJpZ3JhbXMkd2hpY2ggPSAzDQp0ZXRyYWdyYW1zJHdoaWNoID0gNA0KcGVudGFncmFtcyR3aGljaCA9IDUNCg0KTkdyYW1zID0gcmJpbmQoYmlncmFtcyx0cmlncmFtcyx0ZXRyYWdyYW1zLHBlbnRhZ3JhbXMpDQpybShiaWdyYW1zLHRyaWdyYW1zLHRldHJhZ3JhbXMscGVudGFncmFtcykNCiMjIyBTYXZpbmcNCnNhdmUoTkdyYW1zLCBmaWxlID0gIi4uL05HcmFtcy9OR3JhbXMucmRhIikNCndyaXRlLmNzdihOR3JhbXMsICIuLi9OR3JhbXMvTkdyYW1zLmNzdiIsIGZpbGVFbmNvZGluZyA9ICdVVEYtOCcsIHJvdy5uYW1lcyA9IEYpDQpybShOR3JhbXMpDQpgYGANCg0KIyMgRGVmaW5pbmcgcHJlZGljdGlvbiBmdW5jdGlvbg0KQ3JlYXRpbmcgYSBmdW5jdGlvbiB0aGF0IHByZWRpY3RzIHRoZSBuZXh0IHdvcmQgZm9yIGEgZ2l2ZW4gaW5wdXQgbGlzdCBvZiB3b3JkcyAgDQoNCmBgYHtyIHdhcm5pbmc9Rn0NCiMjIExvYWRpbmcgdGhlIG4tZ3JhbXMgDQpOR3JhbXMgPSBnZXQobG9hZCgiLi4vTkdyYW1zL05HcmFtcy5yZGEiKSkNCg0KIyMgRnVuY3Rpb24NCnByZWRpY3RXb3JkID0gZnVuY3Rpb24oc3RyKXsNCiAgcHJlZHNfID0gIiINCiAgcHJlZCA9ICIiDQogIHN0ciA9IGdzdWIoIlxccysiLCAiICIsIHN0cikNCiAgc3RyID0gdG9sb3dlcihzdHIpDQogIHN0ciA9IHJlbW92ZVB1bmN0dWF0aW9uKHN0cikNCiAgc3RyID0gc3RyX3RyaW0oc3RyLCBzaWRlID0gYygiYm90aCIpKQ0KICBuX3dvcmRzID0gc3RyX2NvdW50KHN0ciwgIiAiKSArIDENCiAgaWYobl93b3Jkcz40KXsNCiAgICBzdHIgPSBzdHJfc3BsaXRfZml4ZWQoc3RyLHBhdHRlcm4gPSAiICIsIG5fd29yZHMpWyhuX3dvcmRzLTMpOm5fd29yZHNdDQogICAgbl93b3JkcyA9IDQNCiAgfQ0KICBpZihuX3dvcmRzID09IDQpew0KICAgIG1hdGNoaW5nX3RldHJhZ3JhbXMgPSBmaWx0ZXIoTkdyYW1zLCB3aGljaCA9PSA1KVtncmVwbChzdHIsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaWx0ZXIoTkdyYW1zLCB3aGljaCA9PSA1KVssMV0sIGlnbm9yZS5jYXNlPVRSVUUpLF0NCiAgICBwcmVkc18gPSBkYXRhLmZyYW1lKA0KICAgICAgcHJlZGljdGlvbiA9IHN0cl9leHRyYWN0X2FsbChtYXRjaGluZ190ZXRyYWdyYW1zWywxXSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcGFzdGUwKHN0ciwiXFxzKFs6YWxwaGE6XSspIiksDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNpbXBsaWZ5ID0gVCksDQogICAgICBmcmVxID0gbWF0Y2hpbmdfdGV0cmFncmFtc1ssMl0pICANCiAgICBiZXN0X3ByZWQgPSBwcmVkc19bb3JkZXIoLXByZWRzXyRmcmVxKSxdWzFdDQogICAgaWYoaXMubnVsbChkaW0oYmVzdF9wcmVkKSkpew0KICAgICAgc3RyID0gc3RyX3NwbGl0X2ZpeGVkKHN0cixwYXR0ZXJuID0gIiAiLCA0KVsyOjRdDQogICAgICBuX3dvcmRzID0gMw0KICAgIH0NCiAgfQ0KICBpZihuX3dvcmRzID09IDMpew0KICAgIG1hdGNoaW5nX3RldHJhZ3JhbXMgPSBmaWx0ZXIoTkdyYW1zLCB3aGljaCA9PSA0KVtncmVwbChzdHIsDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaWx0ZXIoTkdyYW1zLCB3aGljaCA9PSA0KVssMV0sIGlnbm9yZS5jYXNlPVRSVUUpLF0NCiAgICBwcmVkc18gPSBkYXRhLmZyYW1lKA0KICAgICAgcHJlZGljdGlvbiA9IHN0cl9leHRyYWN0X2FsbChtYXRjaGluZ190ZXRyYWdyYW1zWywxXSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcGFzdGUwKHN0ciwiXFxzKFs6YWxwaGE6XSspIiksDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNpbXBsaWZ5ID0gVCksDQogICAgICBmcmVxID0gbWF0Y2hpbmdfdGV0cmFncmFtc1ssMl0pIA0KICAgIGJlc3RfcHJlZCA9IHByZWRzX1tvcmRlcigtcHJlZHNfJGZyZXEpLF1bMV0NCiAgICBpZihpcy5udWxsKGRpbShiZXN0X3ByZWQpKSl7DQogICAgICBzdHIgPSBzdHJfc3BsaXRfZml4ZWQoc3RyLHBhdHRlcm4gPSAiICIsIDMpWzI6M10NCiAgICAgIG5fd29yZHMgPSAyDQogICAgfQ0KICB9DQogIGlmKG5fd29yZHMgPT0gMil7DQogICAgbWF0Y2hpbmdfdHJpZ3JhbXMgPSBmaWx0ZXIoTkdyYW1zLCB3aGljaCA9PSAzKVtncmVwKHN0ciwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZpbHRlcihOR3JhbXMsIHdoaWNoID09IDMpWywxXSwgaWdub3JlLmNhc2U9VFJVRSksXQ0KICAgIHByZWRzXyA9IGRhdGEuZnJhbWUoDQogICAgICBwcmVkaWN0aW9uID0gc3RyX2V4dHJhY3RfYWxsKG1hdGNoaW5nX3RyaWdyYW1zWywxXSwgDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHBhc3RlMChzdHIsIlxccyhbOmFscGhhOl0rKSIpLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzaW1wbGlmeSA9IFQpLA0KICAgICAgZnJlcSA9IG1hdGNoaW5nX3RyaWdyYW1zWywyXSkgIA0KICAgIGJlc3RfcHJlZCA9IHByZWRzX1tvcmRlcigtcHJlZHNfJGZyZXEpLF1bMV0NCiAgICBpZihpcy5uYShiZXN0X3ByZWQpKXsNCiAgICAgIHN0ciA9IHN0cl9zcGxpdF9maXhlZChzdHIscGF0dGVybiA9ICIgIiwgMylbMl0NCiAgICAgIG5fd29yZHMgPSAxDQogICAgfQ0KICB9DQogIGlmKG5fd29yZHMgPT0gMSl7DQogICAgbWF0Y2hpbmdfYmlncmFtcyA9IGZpbHRlcihOR3JhbXMsIHdoaWNoID09IDIpW2dyZXAoc3RyLA0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaWx0ZXIoTkdyYW1zLCB3aGljaCA9PSAyKVssMV0sIGlnbm9yZS5jYXNlPVRSVUUpLF0NCiAgICBwcmVkc18gPSBkYXRhLmZyYW1lKA0KICAgICAgcHJlZGljdGlvbiA9IHN0cl9leHRyYWN0X2FsbChtYXRjaGluZ19iaWdyYW1zWywxXSwNCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcGFzdGUwKHN0ciwiXFxzKFs6YWxwaGE6XSspIiksDQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNpbXBsaWZ5ID0gVCksDQogICAgICBmcmVxID0gbWF0Y2hpbmdfYmlncmFtc1ssMl0pICANCiAgICBiZXN0X3ByZWQgPSBwcmVkc19bb3JkZXIoLXByZWRzXyRmcmVxKSwxXVsxXQ0KICB9DQogIHByZWQgPSBzdHJfc3BsaXRfZml4ZWQocHJlZHNfW29yZGVyKHByZWRzX1ssMl0pLF1bMSwxXSwgIiAiLCBuPTIpWzJdDQogIHByZWQNCn0NCnByZWRpY3RXb3JkKCJhY2hpZXZpbmciKQ0KYGBgDQoNCg0KDQpcZm9vdG5vdGVzaXplDQoNCmBgYHtyIHNlc3Npb24tZW5kLCBlY2hvID0gRkFMU0UsIHJlc3VsdHM9J2hvbGQnfQ0Kb3B0aW9ucyh3aWR0aCA9IDEwMCkNCg0KIyMgRGVsZXRpbmcgZGF0YSBhZnRlciBhbmFseXNpcw0KdW5saW5rKCIuLi9kYXRhIixyZWN1cnNpdmUgPSBUKQ0KDQpjYXQoIlIgU2Vzc2lvbiBJbmZvOlxuIikNCnNlc3Npb25JbmZvKCkNCmBgYA0K