ch1.套件取得及資料載入
套件
library(data.table)
library(ggplot2)
library(dplyr)
library(jiebaR)
library(tidytext)
library(stringr)
library(tm)
library(topicmodels)
library(purrr)
require(RColorBrewer)
require(readr)
require(NLP)
require(tidyr)
require(ggraph)
require(igraph)
require(scales)
require(reshape2)
require(widyr)
mycolors <- colorRampPalette(brewer.pal(8, "Set3"))(20)
資料描述
透過中山管院文字分析平台,載入聯合新聞網、蘋果新聞網、東森新聞網的新聞,搜尋關鍵字為「藻礁、三接、陳昭倫、潘忠政」,時間從2020/11/01到2021/05/15
filePath <- "/Users/hungwenchun/Desktop/data/sea"
setwd(filePath)
metadata <- fread("news_reef_articleMetaData.csv", encoding = "UTF-8")%>%
mutate(sentence=gsub("[\n]{2,}", "。", sentence)) %>%
mutate(sentence=gsub("\n", "", sentence)) %>%
mutate(sentence=gsub("http(s)?[-:\\/A-Za-z0-9\\.]+", " ", sentence))
可以看到藻礁公投討論有幾波討論高點與趨勢
1.在228連假時連署呼聲的新聞報導數量增加
2.3/13藻礁公投連署書收69萬餘件,準備送進中選會進行公投成案
3.3/31農委會主委陳吉仲代表政府拜訪發起來潘忠政
4.4/22世界地球日蔡英文總統接見環團組織,含潘忠政對藻礁議題無交集 5.5/3政院提三接外推方案
metadata %>%
mutate(artDate = as.Date(artDate)) %>%
group_by(artDate) %>%
summarise(count = n())%>%
ggplot(aes(artDate,count))+
geom_line(color="red")+
geom_point()

斷句
# 以全形或半形 驚歎號、問號、分號 以及 全形句號 爲依據進行斷句
reaf_sentences <- strsplit(metadata$sentence,"[。!;?!?;]")
# 將每句句子,與他所屬的文章連結配對起來,整理成一個dataframe
reaf_sentences <- data.frame(
artUrl = rep(metadata$artUrl, sapply(reaf_sentences, length)),
artDate = rep(metadata$artDate, sapply(reaf_sentences, length)),
sentence = unlist(reaf_sentences)
) %>%
filter(!str_detect(sentence, regex("^(\t|\n| )*$")))
reaf_sentences$sentence <- as.character(reaf_sentences$sentence)
reaf_sentences
建立斷詞辭典
jieba_tokenizer = worker(user="reef_dict.txt", stop_word="reef_stop_words.txt")
chi_tokenizer <- function(t) {
lapply(t, function(x) {
if(nchar(x)>1){
tokens <- segment(x, jieba_tokenizer)
tokens <- tokens[!tokens %in% stop_words]
# 去掉字串長度爲1的詞彙
tokens <- tokens[nchar(tokens)>1]
return(tokens)
}
})
}
斷詞
# 剛才的斷詞結果沒有使用新增的辭典,因此我們重新進行斷詞,再計算各詞彙在各文章中出現的次數
reaf_words <- reaf_sentences %>%
unnest_tokens(word, sentence, token=chi_tokenizer) %>%
filter(!str_detect(word, regex("[0-9a-zA-Z]"))) %>%
count(artUrl, word) %>%
rename(count=n)
reaf_words
#Ch1. Document Term Matrix (DTM)
dtm <- reaf_words %>% cast_dtm(artUrl, word, count)
dtm
inspect(dtm[1:10,1:10])
ch2. 主題模型
建立LDA模型
#lda <- LDA(dtm, k = 2, control = list(seed = 2021))
lda <- LDA(dtm, k = 4, control = list(seed = 2021,alpha = 10,delta=0.2),method = "Gibbs")
利用LDA模型建立phi矩陣
## 利用LDA模型建立phi矩陣
topics_words <- tidy(lda, matrix = "beta") # 注意,在tidy function裡面要使用"beta"來取出Phi矩陣。
colnames(topics_words) <- c("topic", "term", "phi")
topics_words
尋找Topic的代表字
terms依照各主題的phi值由大到小排序,列出前10大
topics_words %>%
group_by(topic) %>%
top_n(10, phi) %>%
ungroup() %>%
mutate(top_words = reorder_within(term,phi,topic)) %>%
ggplot(aes(x = top_words, y = phi, fill = as.factor(topic))) +
theme(text = element_text(family = "Heiti TC Light"))+
geom_col(show.legend = FALSE) +
facet_wrap(~ topic, scales = "free") +
coord_flip() +
scale_x_reordered()

ch3. 尋找最佳主題數
建立更多主題的主題模型
嘗試2、4、6、10、15個主題數,將結果存起來,再做進一步分析。
#ldas = c()
#topics = c(2,4,6,10,15)
#for(topic in topics){
#start_time <- Sys.time()
#lda <- LDA(dtm, k = topic, control = list(seed = 2021))
#ldas =c(ldas,lda)
#print(paste(topic ,paste("topic(s) and use time is ", Sys.time() -start_time)))
#save(ldas,file = "ldas_result.rdata") # 將模型輸出成檔案
#}
載入每個主題的LDA結果
load("ldas_result.rdata")
透過perplexity找到最佳主題數
選擇分成四個主題
topics = c(2,4,6,10,15)
data_frame(k = topics, perplex = map_dbl(ldas, topicmodels::perplexity)) %>%
ggplot(aes(k, perplex)) +
geom_point() +
geom_line() +
labs(title = "Evaluating LDA topic models",
subtitle = "Optimal number of topics (smaller is better)",
x = "Number of topics",
y = "Perplexity")

create LDAvis所需的json function 此function是將前面使用 “LDA function”所建立的model,轉換為“LDAVis”套件的input格式。
topicmodels_json_ldavis <- function(fitted, doc_term){
require(LDAvis)
require(slam)
###以下function 用來解決,主題數多會出現NA的問題
### 參考 https://github.com/cpsievert/LDAvis/commit/c7234d71168b1e946a361bc00593bc5c4bf8e57e
ls_LDA = function (phi){
jensenShannon <- function(x, y) {
m <- 0.5 * (x + y)
lhs <- ifelse(x == 0, 0, x * (log(x) - log(m+1e-16)))
rhs <- ifelse(y == 0, 0, y * (log(y) - log(m+1e-16)))
0.5 * sum(lhs) + 0.5 * sum(rhs)
}
dist.mat <- proxy::dist(x = phi, method = jensenShannon)
pca.fit <- stats::cmdscale(dist.mat, k = 2)
data.frame(x = pca.fit[, 1], y = pca.fit[, 2])
}
# Find required quantities
phi <- as.matrix(posterior(fitted)$terms)
theta <- as.matrix(posterior(fitted)$topics)
vocab <- colnames(phi)
term_freq <- slam::col_sums(doc_term)
# Convert to json
json_lda <- LDAvis::createJSON(phi = phi, theta = theta,
vocab = vocab,
doc.length = as.vector(table(doc_term$i)),
term.frequency = term_freq, mds.method = ls_LDA)
return(json_lda)
}
產生LDAvis結果
the_lda = ldas[[2]]
json_res <- topicmodels_json_ldavis(the_lda,dtm)
serVis(json_res,open.browser = T)
ch4. LDA分析
選定4個主題數的主題模型
the_lda = ldas[[2]] ## 選定topic 為 4 的結果
topics_words <- tidy(the_lda, matrix = "beta") # 注意,在tidy function裡面要使用"beta"來取出Phi矩陣。
colnames(topics_words) <- c("topic", "term", "phi")
topics_words %>% arrange(desc(phi)) %>% head(10)
terms依照各主題的phi值由大到小排序
topics_words %>%
group_by(topic) %>%
top_n(10, phi) %>%
ungroup() %>%
ggplot(aes(x = reorder_within(term,phi,topic), y = phi, fill = as.factor(topic))) +
theme(text = element_text(family = "Heiti TC Light"))+
geom_col(show.legend = FALSE) +
facet_wrap(~ topic, scales = "free") +
coord_flip() +
scale_x_reordered()

去除共通詞彙,藻礁、公投、連署、今天、提出、希望、影響、政府
removed_word = c("藻礁","公投","連署","今天","提出","希望","影響","政府")
topics_words %>%
filter(!term %in% removed_word) %>%
group_by(topic) %>%
top_n(10, phi) %>%
ungroup() %>%
ggplot(aes(x = reorder_within(term,phi,topic), y = phi, fill = as.factor(topic))) +
theme(text = element_text(family = "Heiti TC Light"))+
geom_col(show.legend = FALSE) +
facet_wrap(~ topic, scales = "free") +
coord_flip() +
scale_x_reordered()

主題命名
topics_name = c("政黨議題","能源議題","生態保育議題","方案議題")
Document 主題分佈
# for every document we have a probability distribution of its contained topics
tmResult <- posterior(the_lda)
doc_pro <- tmResult$topics
document_topics <- doc_pro[metadata$artUrl,]
document_topics_df =data.frame(document_topics)
colnames(document_topics_df) = topics_name
rownames(document_topics_df) = NULL
news_topic = cbind(metadata,document_topics_df)
現在我們看每一篇的文章分佈了!
查看特定主題的文章
- 透過找到特定文章的分佈進行排序之後,可以看到此主題的比重高的文章在討論什麼。
政黨議題:多為政治人物對藻礁公投的支持與否的看法 ex:由環保團體發起的「珍愛藻礁公投連署」已突破50萬大關,國民黨表態大力支持、時代力量黨主席陳椒華今於臉書大力為公投催連署
news_topic %>%
arrange(desc(`政黨議題`)) %>% head(30)
方案議題:對藻礁公投的訴求和議題的討論 ex:行政院提出三接外推455公尺方案,總計離岸1.2公里,宣稱對沿岸影響更輕微、不破壞礁體,還宣稱是「雙贏」方案
news_topic %>%
arrange(desc(`方案議題`)) %>% head(30)
生態保育議題:蓋第三天然氣接收站對藻礁與生態環境的破壞 ex:桃園大潭藻礁生態因將蓋第三天然氣接收站,恐衝擊生態、除了桃園沿岸的藻礁之外,新竹的新豐海岸也有藻礁,學者指出,當地的藻礁是全台灣最南端的藻礁,具有特殊意義
news_topic %>%
arrange(desc(`生態保育議題`)) %>%head(30)
能源議題:藻礁公投對台塑、天然氣、燃煤等能源的影響 ex:中油選在觀塘蓋天然氣第三接收站,與供電的時程息息相關、若無大潭燃氣供電,可能回到2014年前中火與麥寮電廠火力全開的排碳量、大潭藻礁設置中油三接站引發爭議,外傳總統蔡英文找上台塑,希望由台塑位在麥寮機組由燃煤改為燃煤,作為三接的替代方案
news_topic %>%
arrange(desc(`能源議題`)) %>%head(30)
了解主題在時間的變化
可以了解到在三月份,這四種議題都被討論到,而四、五月較針對藻礁本身的公投議題去討論,五月最主要的議題王美花召開記者會,提出政院三接外推案
news_topic %>%
mutate(artDate = as.Date(artDate)) %>%
group_by(artDate = format(artDate,'%Y%m')) %>%
summarise_if(is.numeric, sum, na.rm = TRUE) %>%
melt(id.vars = "artDate")%>%
ggplot( aes(x=artDate, y=value, fill=variable)) +
theme(text = element_text(family = "Heiti TC Light"))+
geom_bar(stat = "identity") + ylab("value") +
scale_fill_manual(values=mycolors[c(1,5,8,12)])+
theme(axis.text.x = element_text(angle = 90, hjust = 1))

以比例了解主題時間變化
2月最主要是政黨之間對藻礁公投的看法,可能會模糊焦點,而之後較針對此議題去做討論
news_topic %>%
mutate(artDate = as.Date(artDate)) %>%
group_by(artDate = format(artDate,'%Y%m')) %>%
summarise_if(is.numeric, sum, na.rm = TRUE) %>%
melt(id.vars = "artDate")%>%
group_by(artDate)%>%
mutate(total_value =sum(value))%>%
ggplot( aes(x=artDate, y=value/total_value, fill=variable)) +
theme(text = element_text(family = "Heiti TC Light"))+
geom_bar(stat = "identity") + ylab("proportion") +
scale_fill_manual(values=mycolors[c(1,5,8,12)])+
theme(axis.text.x = element_text(angle = 90, hjust = 1))

LS0tCnRpdGxlOiAi5L2/55So5Li76aGM5qih5Z6L5YiG5p6Q6Je756SB5YWs5oqV5Lit5paH5paw6IGe6LOH5paZIgphdXRob3I6ICLmtKrnjp/lkJsiCmRhdGU6ICIyMDIxLzA1LzE3IgpvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazoKICAgIHRvYzogeWVzCiAgICB0b2NfZmxvYXQ6IHllcwogICAgaGlnaGxpZ2h0OiBweWdtZW50cwogICAgdGhlbWU6IGZsYXRseQogICAgY3NzOiBzdHlsZS5jc3MKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB5ZXMKICAgIGRmX3ByaW50OiBwYWdlZAotLS0KCmBgYHtyIGVjaG8gPSBULCByZXN1bHRzID0gJ2hpZGUnfQpTeXMuc2V0bG9jYWxlKGNhdGVnb3J5ID0gIkxDX0FMTCIsIGxvY2FsZSA9ICJ6aF9UVy5VVEYtOCIpICMg6YG/5YWN5Lit5paH5LqC56K8CmBgYAojIGNoMS7lpZfku7blj5blvpflj4ros4fmlpnovInlhaUKIyMg5aWX5Lu2CmBgYHtyfQpsaWJyYXJ5KGRhdGEudGFibGUpCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShkcGx5cikKbGlicmFyeShqaWViYVIpCmxpYnJhcnkodGlkeXRleHQpCmxpYnJhcnkoc3RyaW5ncikKbGlicmFyeSh0bSkKbGlicmFyeSh0b3BpY21vZGVscykKbGlicmFyeShwdXJycikKcmVxdWlyZShSQ29sb3JCcmV3ZXIpCnJlcXVpcmUocmVhZHIpCnJlcXVpcmUoTkxQKQpyZXF1aXJlKHRpZHlyKQpyZXF1aXJlKGdncmFwaCkKcmVxdWlyZShpZ3JhcGgpCnJlcXVpcmUoc2NhbGVzKQpyZXF1aXJlKHJlc2hhcGUyKQpyZXF1aXJlKHdpZHlyKQpteWNvbG9ycyA8LSBjb2xvclJhbXBQYWxldHRlKGJyZXdlci5wYWwoOCwgIlNldDMiKSkoMjApCmBgYAoKIyMg6LOH5paZ5o+P6L+wCgo+IOmAj+mBjuS4reWxseeuoemZouaWh+Wtl+WIhuaekOW5s+WPsO+8jOi8ieWFpeiBr+WQiOaWsOiBnue2suOAgeiYi+aenOaWsOiBnue2suOAgeadseajruaWsOiBnue2sueahOaWsOiBnu+8jOaQnOWwi+mXnOmNteWtl+eCuuOAjOiXu+ekgeOAgeS4ieaOpeOAgemZs+aYreWAq+OAgea9mOW/oOaUv+OAje+8jOaZgumWk+W+njIwMjAvMTEvMDHliLAyMDIxLzA1LzE1CgpgYGB7cn0KZmlsZVBhdGggPC0gIi9Vc2Vycy9odW5nd2VuY2h1bi9EZXNrdG9wL2RhdGEvc2VhIgpzZXR3ZChmaWxlUGF0aCkKbWV0YWRhdGEgPC0gZnJlYWQoIm5ld3NfcmVlZl9hcnRpY2xlTWV0YURhdGEuY3N2IiwgZW5jb2RpbmcgPSAiVVRGLTgiKSU+JQogIG11dGF0ZShzZW50ZW5jZT1nc3ViKCJbXG5dezIsfSIsICLjgIIiLCBzZW50ZW5jZSkpICU+JSAKICBtdXRhdGUoc2VudGVuY2U9Z3N1YigiXG4iLCAiIiwgc2VudGVuY2UpKSAlPiUgCiAgbXV0YXRlKHNlbnRlbmNlPWdzdWIoImh0dHAocyk/Wy06XFwvQS1aYS16MC05XFwuXSsiLCAiICIsIHNlbnRlbmNlKSkKYGBgCgo+IOWPr+S7peeci+WIsOiXu+ekgeWFrOaKleiojuirluacieW5vuazouiojuirlumrmOm7nuiIh+i2qOWLogoKMS7lnKgyMjjpgKPlgYfmmYLpgKPnvbLlkbzogbLnmoTmlrDogZ7loLHlsI7mlbjph4/lop7liqAKCjIuMy8xM+iXu+ekgeWFrOaKlemAo+e9suabuOaUtjY56JCs6aSY5Lu2LOa6luWCmemAgemAsuS4remBuOacg+mAsuihjOWFrOaKleaIkOahiAoKMy4zLzMx6L6y5aeU5pyD5Li75aeU6Zmz5ZCJ5Luy5Luj6KGo5pS/5bqc5ouc6Kiq55m86LW35L6G5r2Y5b+g5pS/Cgo0LjQvMjLkuJbnlYzlnLDnkIPml6XolKHoi7HmlofnuL3ntbHmjqXopovnkrDlnJjntYTnuZQs5ZCr5r2Y5b+g5pS/5bCN6Je756SB6K2w6aGM54Sh5Lqk6ZuGIDUuNS8z5pS/6Zmi5o+Q5LiJ5o6l5aSW5o6o5pa55qGICmBgYHtyfQptZXRhZGF0YSAlPiUgCiAgbXV0YXRlKGFydERhdGUgPSBhcy5EYXRlKGFydERhdGUpKSAlPiUKICBncm91cF9ieShhcnREYXRlKSAlPiUKICBzdW1tYXJpc2UoY291bnQgPSBuKCkpJT4lCiAgZ2dwbG90KGFlcyhhcnREYXRlLGNvdW50KSkrCiAgICBnZW9tX2xpbmUoY29sb3I9InJlZCIpKwogICAgZ2VvbV9wb2ludCgpCmBgYApgYGB7cn0KcmFuZ2UobWV0YWRhdGEkYXJ0RGF0ZSkKYGBgCiMjIOaWt+WPpQpgYGB7cn0KIyDku6XlhajlvaLmiJbljYrlvaIg6ama5q2O6Jmf44CB5ZWP6Jmf44CB5YiG6JmfIOS7peWPiiDlhajlvaLlj6XomZ8g54iy5L6d5pOa6YCy6KGM5pa35Y+lCnJlYWZfc2VudGVuY2VzIDwtIHN0cnNwbGl0KG1ldGFkYXRhJHNlbnRlbmNlLCJb44CC77yB77yb77yfIT87XSIpCiMg5bCH5q+P5Y+l5Y+l5a2Q77yM6IiH5LuW5omA5bGs55qE5paH56ug6YCj57WQ6YWN5bCN6LW35L6G77yM5pW055CG5oiQ5LiA5YCLZGF0YWZyYW1lCnJlYWZfc2VudGVuY2VzIDwtIGRhdGEuZnJhbWUoCiAgICAgICAgICAgICAgICAgICAgICAgIGFydFVybCA9IHJlcChtZXRhZGF0YSRhcnRVcmwsIHNhcHBseShyZWFmX3NlbnRlbmNlcywgbGVuZ3RoKSksIAogICAgICAgICAgICAgICAgICAgICAgICBhcnREYXRlID0gcmVwKG1ldGFkYXRhJGFydERhdGUsIHNhcHBseShyZWFmX3NlbnRlbmNlcywgbGVuZ3RoKSksCiAgICAgICAgICAgICAgICAgICAgICAgIHNlbnRlbmNlID0gdW5saXN0KHJlYWZfc2VudGVuY2VzKQogICAgICAgICAgICAgICAgICAgICAgKSAlPiUKICAgICAgICAgICAgICAgICAgICAgIGZpbHRlcighc3RyX2RldGVjdChzZW50ZW5jZSwgcmVnZXgoIl4oXHR8XG58ICkqJCIpKSkKCnJlYWZfc2VudGVuY2VzJHNlbnRlbmNlIDwtIGFzLmNoYXJhY3RlcihyZWFmX3NlbnRlbmNlcyRzZW50ZW5jZSkKCnJlYWZfc2VudGVuY2VzCmBgYAoKIyMg5bu656uL5pa36Kme6L6t5YW4CmBgYHtyfQpqaWViYV90b2tlbml6ZXIgPSB3b3JrZXIodXNlcj0icmVlZl9kaWN0LnR4dCIsIHN0b3Bfd29yZD0icmVlZl9zdG9wX3dvcmRzLnR4dCIpCmBgYAoKYGBge3J9CmNoaV90b2tlbml6ZXIgPC0gZnVuY3Rpb24odCkgewogIGxhcHBseSh0LCBmdW5jdGlvbih4KSB7CiAgICBpZihuY2hhcih4KT4xKXsKICAgICAgdG9rZW5zIDwtIHNlZ21lbnQoeCwgamllYmFfdG9rZW5pemVyKQogICAgICB0b2tlbnMgPC0gdG9rZW5zWyF0b2tlbnMgJWluJSBzdG9wX3dvcmRzXQogICAgICAjIOWOu+aOieWtl+S4sumVt+W6pueIsjHnmoToqZ7lvZkKICAgICAgdG9rZW5zIDwtIHRva2Vuc1tuY2hhcih0b2tlbnMpPjFdCiAgICAgIHJldHVybih0b2tlbnMpCiAgICB9CiAgfSkKfQpgYGAKCiMjIOaWt+ipngpgYGB7cn0KIyDliZvmiY3nmoTmlrfoqZ7ntZDmnpzmspLmnInkvb/nlKjmlrDlop7nmoTovq3lhbjvvIzlm6DmraTmiJHlgJHph43mlrDpgLLooYzmlrfoqZ7vvIzlho3oqIjnrpflkIToqZ7lvZnlnKjlkITmlofnq6DkuK3lh7rnj77nmoTmrKHmlbgKcmVhZl93b3JkcyA8LSByZWFmX3NlbnRlbmNlcyAlPiUKICB1bm5lc3RfdG9rZW5zKHdvcmQsIHNlbnRlbmNlLCB0b2tlbj1jaGlfdG9rZW5pemVyKSAlPiUKICBmaWx0ZXIoIXN0cl9kZXRlY3Qod29yZCwgcmVnZXgoIlswLTlhLXpBLVpdIikpKSAlPiUKICBjb3VudChhcnRVcmwsIHdvcmQpICU+JQogIHJlbmFtZShjb3VudD1uKQpyZWFmX3dvcmRzCmBgYAoKI0NoMS4gRG9jdW1lbnQgVGVybSBNYXRyaXggKERUTSkKCmBgYHtyfQpkdG0gPC0gcmVhZl93b3JkcyAlPiUgY2FzdF9kdG0oYXJ0VXJsLCB3b3JkLCBjb3VudCkKZHRtCmluc3BlY3QoZHRtWzE6MTAsMToxMF0pCmBgYAojIGNoMi4g5Li76aGM5qih5Z6LCiMjIOW7uueri0xEQeaooeWeiwpgYGB7cn0KI2xkYSA8LSBMREEoZHRtLCBrID0gMiwgY29udHJvbCA9IGxpc3Qoc2VlZCA9IDIwMjEpKQpsZGEgPC0gTERBKGR0bSwgayA9IDQsIGNvbnRyb2wgPSBsaXN0KHNlZWQgPSAyMDIxLGFscGhhID0gMTAsZGVsdGE9MC4yKSxtZXRob2QgPSAiR2liYnMiKQpgYGAKCiMjIOWIqeeUqExEQeaooeWei+W7uueri3BoaeefqemZowpgYGB7cn0KIyMg5Yip55SoTERB5qih5Z6L5bu656uLcGhp55+p6ZmjCnRvcGljc193b3JkcyA8LSB0aWR5KGxkYSwgbWF0cml4ID0gImJldGEiKSAjIOazqOaEj++8jOWcqHRpZHkgZnVuY3Rpb27oo6HpnaLopoHkvb/nlKgiYmV0YSLkvoblj5blh7pQaGnnn6npmaPjgIIKY29sbmFtZXModG9waWNzX3dvcmRzKSA8LSBjKCJ0b3BpYyIsICJ0ZXJtIiwgInBoaSIpCnRvcGljc193b3JkcwpgYGAKCiMjIOWwi+aJvlRvcGlj55qE5Luj6KGo5a2XCgo+IHRlcm1z5L6d54Wn5ZCE5Li76aGM55qEcGhp5YC855Sx5aSn5Yiw5bCP5o6S5bqP77yM5YiX5Ye65YmNMTDlpKcKCmBgYHtyfQp0b3BpY3Nfd29yZHMgJT4lCiAgZ3JvdXBfYnkodG9waWMpICU+JQogIHRvcF9uKDEwLCBwaGkpICU+JQogIHVuZ3JvdXAoKSAlPiUKICBtdXRhdGUodG9wX3dvcmRzID0gcmVvcmRlcl93aXRoaW4odGVybSxwaGksdG9waWMpKSAlPiUKICBnZ3Bsb3QoYWVzKHggPSB0b3Bfd29yZHMsIHkgPSBwaGksIGZpbGwgPSBhcy5mYWN0b3IodG9waWMpKSkgKwogIHRoZW1lKHRleHQgPSBlbGVtZW50X3RleHQoZmFtaWx5ID0gIkhlaXRpIFRDIExpZ2h0IikpKwogIGdlb21fY29sKHNob3cubGVnZW5kID0gRkFMU0UpICsKICBmYWNldF93cmFwKH4gdG9waWMsIHNjYWxlcyA9ICJmcmVlIikgKwogIGNvb3JkX2ZsaXAoKSArCiAgc2NhbGVfeF9yZW9yZGVyZWQoKQogIAogCmBgYAoKIyBjaDMuIOWwi+aJvuacgOS9s+S4u+mhjOaVuAoKIyMg5bu656uL5pu05aSa5Li76aGM55qE5Li76aGM5qih5Z6LCgo+IOWYl+ippjLjgIE044CBNuOAgTEw44CBMTXlgIvkuLvpoYzmlbjvvIzlsIfntZDmnpzlrZjotbfkvobvvIzlho3lgZrpgLLkuIDmraXliIbmnpDjgIIKCmBgYHtyIGV2YWw9RkFMU0V9CiNsZGFzID0gYygpCiN0b3BpY3MgPSBjKDIsNCw2LDEwLDE1KQogICNmb3IodG9waWMgaW4gdG9waWNzKXsKICAgI3N0YXJ0X3RpbWUgPC0gU3lzLnRpbWUoKQogICAjbGRhIDwtIExEQShkdG0sIGsgPSB0b3BpYywgY29udHJvbCA9IGxpc3Qoc2VlZCA9IDIwMjEpKQogICAjbGRhcyA9YyhsZGFzLGxkYSkKICAgI3ByaW50KHBhc3RlKHRvcGljICxwYXN0ZSgidG9waWMocykgYW5kIHVzZSB0aW1lIGlzICIsIFN5cy50aW1lKCkgLXN0YXJ0X3RpbWUpKSkKICAgI3NhdmUobGRhcyxmaWxlID0gImxkYXNfcmVzdWx0LnJkYXRhIikgIyDlsIfmqKHlnovovLjlh7rmiJDmqpTmoYgKICAjfQpgYGAKCgo+IOi8ieWFpeavj+WAi+S4u+mhjOeahExEQee1kOaenAoKYGBge3J9CmxvYWQoImxkYXNfcmVzdWx0LnJkYXRhIikKYGBgCgojIyDpgI/pgY5wZXJwbGV4aXR55om+5Yiw5pyA5L2z5Li76aGM5pW4CumBuOaTh+WIhuaIkOWbm+WAi+S4u+mhjApgYGB7cn0KdG9waWNzID0gYygyLDQsNiwxMCwxNSkKZGF0YV9mcmFtZShrID0gdG9waWNzLCBwZXJwbGV4ID0gbWFwX2RibChsZGFzLCB0b3BpY21vZGVsczo6cGVycGxleGl0eSkpICU+JQogIGdncGxvdChhZXMoaywgcGVycGxleCkpICsKICBnZW9tX3BvaW50KCkgKwogIGdlb21fbGluZSgpICsKICBsYWJzKHRpdGxlID0gIkV2YWx1YXRpbmcgTERBIHRvcGljIG1vZGVscyIsCiAgICAgICBzdWJ0aXRsZSA9ICJPcHRpbWFsIG51bWJlciBvZiB0b3BpY3MgKHNtYWxsZXIgaXMgYmV0dGVyKSIsCiAgICAgICB4ID0gIk51bWJlciBvZiB0b3BpY3MiLAogICAgICAgeSA9ICJQZXJwbGV4aXR5IikKYGBgCgo+IGNyZWF0ZSBMREF2aXPmiYDpnIDnmoRqc29uIGZ1bmN0aW9uCuatpGZ1bmN0aW9u5piv5bCH5YmN6Z2i5L2/55SoICJMREEgZnVuY3Rpb24i5omA5bu656uL55qEbW9kZWzvvIzovYnmj5vngroiTERBVmlzIuWll+S7tueahGlucHV05qC85byP44CCCgpgYGB7cn0KCnRvcGljbW9kZWxzX2pzb25fbGRhdmlzIDwtIGZ1bmN0aW9uKGZpdHRlZCwgZG9jX3Rlcm0pewogICAgcmVxdWlyZShMREF2aXMpCiAgICByZXF1aXJlKHNsYW0pCiAgCiAgICAjIyPku6XkuItmdW5jdGlvbiDnlKjkvobop6PmsbrvvIzkuLvpoYzmlbjlpJrmnIPlh7rnj75OQeeahOWVj+mhjAogICAgIyMjIOWPg+iAgyBodHRwczovL2dpdGh1Yi5jb20vY3BzaWV2ZXJ0L0xEQXZpcy9jb21taXQvYzcyMzRkNzExNjhiMWU5NDZhMzYxYmMwMDU5M2JjNWM0YmY4ZTU3ZQogICAgbHNfTERBID0gZnVuY3Rpb24gKHBoaSl7CiAgICAgIGplbnNlblNoYW5ub24gPC0gZnVuY3Rpb24oeCwgeSkgewogICAgICAgIG0gPC0gMC41ICogKHggKyB5KQogICAgICAgIGxocyA8LSBpZmVsc2UoeCA9PSAwLCAwLCB4ICogKGxvZyh4KSAtIGxvZyhtKzFlLTE2KSkpCiAgICAgICAgcmhzIDwtIGlmZWxzZSh5ID09IDAsIDAsIHkgKiAobG9nKHkpIC0gbG9nKG0rMWUtMTYpKSkKICAgICAgICAwLjUgKiBzdW0obGhzKSArIDAuNSAqIHN1bShyaHMpCiAgICAgIH0KICAgICAgZGlzdC5tYXQgPC0gcHJveHk6OmRpc3QoeCA9IHBoaSwgbWV0aG9kID0gamVuc2VuU2hhbm5vbikKICAgICAgcGNhLmZpdCA8LSBzdGF0czo6Y21kc2NhbGUoZGlzdC5tYXQsIGsgPSAyKQogICAgICBkYXRhLmZyYW1lKHggPSBwY2EuZml0WywgMV0sIHkgPSBwY2EuZml0WywgMl0pCiAgICB9CiAgCiAgICAgICMgRmluZCByZXF1aXJlZCBxdWFudGl0aWVzCiAgICAgIHBoaSA8LSBhcy5tYXRyaXgocG9zdGVyaW9yKGZpdHRlZCkkdGVybXMpCiAgICAgIHRoZXRhIDwtIGFzLm1hdHJpeChwb3N0ZXJpb3IoZml0dGVkKSR0b3BpY3MpCiAgICAgIHZvY2FiIDwtIGNvbG5hbWVzKHBoaSkKICAgICAgdGVybV9mcmVxIDwtIHNsYW06OmNvbF9zdW1zKGRvY190ZXJtKQogIAogICAgICAjIENvbnZlcnQgdG8ganNvbgogICAgICBqc29uX2xkYSA8LSBMREF2aXM6OmNyZWF0ZUpTT04ocGhpID0gcGhpLCB0aGV0YSA9IHRoZXRhLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdm9jYWIgPSB2b2NhYiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRvYy5sZW5ndGggPSBhcy52ZWN0b3IodGFibGUoZG9jX3Rlcm0kaSkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgdGVybS5mcmVxdWVuY3kgPSB0ZXJtX2ZyZXEsIG1kcy5tZXRob2QgPSBsc19MREEpCiAgCiAgICAgIHJldHVybihqc29uX2xkYSkKfQpgYGAKCiMjIOeUoueUn0xEQXZpc+e1kOaenAoKYGBge3IgZXZhbD1GQUxTRX0KCnRoZV9sZGEgPSBsZGFzW1syXV0KanNvbl9yZXMgPC0gdG9waWNtb2RlbHNfanNvbl9sZGF2aXModGhlX2xkYSxkdG0pCnNlclZpcyhqc29uX3JlcyxvcGVuLmJyb3dzZXIgPSBUKQpgYGAKIyMjIOeUoueUn0xEQXZpc+aqlOahiO+8jOWtmOiHs2xvY2Fs56uvCmBgYHtyIGV2YWw9RkFMU0V9CnNlclZpcyhqc29uX3Jlcywgb3V0LmRpciA9ICJ2aXMiLCBvcGVuLmJyb3dzZXIgPSBUKQp3cml0ZUxpbmVzKGljb252KHJlYWRMaW5lcygiLi92aXMvbGRhLmpzb24iKSwgdG8gPSAiVVRGOCIpKQpgYGAK5Li76aGMMQohWyJMREF2aXMiXSh0cDEuUE5HKQrkuLvpoYwyCiFbIkxEQXZpcyJdKHRwMi5QTkcpCuS4u+mhjDMKIVsiTERBdmlzIl0odHAzLlBORykK5Li76aGMNAohWyJMREF2aXMiXSh0cDQuUE5HKQoKIyBjaDQuIExEQeWIhuaekAoKIyMg6YG45a6aNOWAi+S4u+mhjOaVuOeahOS4u+mhjOaooeWeiwpgYGB7cn0KdGhlX2xkYSA9IGxkYXNbWzJdXSAjIyDpgbjlrpp0b3BpYyDngrogNCDnmoTntZDmnpwKYGBgCgpgYGB7cn0KdG9waWNzX3dvcmRzIDwtIHRpZHkodGhlX2xkYSwgbWF0cml4ID0gImJldGEiKSAjIOazqOaEj++8jOWcqHRpZHkgZnVuY3Rpb27oo6HpnaLopoHkvb/nlKgiYmV0YSLkvoblj5blh7pQaGnnn6npmaPjgIIKY29sbmFtZXModG9waWNzX3dvcmRzKSA8LSBjKCJ0b3BpYyIsICJ0ZXJtIiwgInBoaSIpCnRvcGljc193b3JkcyAlPiUgYXJyYW5nZShkZXNjKHBoaSkpICU+JSBoZWFkKDEwKQpgYGAKCj4gdGVybXPkvp3nhaflkITkuLvpoYznmoRwaGnlgLznlLHlpKfliLDlsI/mjpLluo8KCmBgYHtyfQp0b3BpY3Nfd29yZHMgJT4lCiAgZ3JvdXBfYnkodG9waWMpICU+JQogIHRvcF9uKDEwLCBwaGkpICU+JQogIHVuZ3JvdXAoKSAlPiUKICBnZ3Bsb3QoYWVzKHggPSByZW9yZGVyX3dpdGhpbih0ZXJtLHBoaSx0b3BpYyksIHkgPSBwaGksIGZpbGwgPSBhcy5mYWN0b3IodG9waWMpKSkgKwogIHRoZW1lKHRleHQgPSBlbGVtZW50X3RleHQoZmFtaWx5ID0gIkhlaXRpIFRDIExpZ2h0IikpKwogIGdlb21fY29sKHNob3cubGVnZW5kID0gRkFMU0UpICsKICBmYWNldF93cmFwKH4gdG9waWMsIHNjYWxlcyA9ICJmcmVlIikgKwogIGNvb3JkX2ZsaXAoKSArCiAgc2NhbGVfeF9yZW9yZGVyZWQoKQpgYGAKCj7ljrvpmaTlhbHpgJroqZ7lvZnvvIzol7vnpIHjgIHlhazmipXjgIHpgKPnvbLjgIHku4rlpKnjgIHmj5Dlh7rjgIHluIzmnJvjgIHlvbHpn7/jgIHmlL/lupwKCmBgYHtyfQpyZW1vdmVkX3dvcmQgPSBjKCLol7vnpIEiLCLlhazmipUiLCLpgKPnvbIiLCLku4rlpKkiLCLmj5Dlh7oiLCLluIzmnJsiLCLlvbHpn78iLCLmlL/lupwiKQoKdG9waWNzX3dvcmRzICU+JQogIGZpbHRlcighdGVybSAgJWluJSByZW1vdmVkX3dvcmQpICU+JQogIGdyb3VwX2J5KHRvcGljKSAlPiUKICB0b3BfbigxMCwgcGhpKSAlPiUKICB1bmdyb3VwKCkgJT4lCiAgZ2dwbG90KGFlcyh4ID0gcmVvcmRlcl93aXRoaW4odGVybSxwaGksdG9waWMpLCB5ID0gcGhpLCBmaWxsID0gYXMuZmFjdG9yKHRvcGljKSkpICsKICB0aGVtZSh0ZXh0ID0gZWxlbWVudF90ZXh0KGZhbWlseSA9ICJIZWl0aSBUQyBMaWdodCIpKSsKICBnZW9tX2NvbChzaG93LmxlZ2VuZCA9IEZBTFNFKSArCiAgZmFjZXRfd3JhcCh+IHRvcGljLCBzY2FsZXMgPSAiZnJlZSIpICsKICBjb29yZF9mbGlwKCkgKwogIHNjYWxlX3hfcmVvcmRlcmVkKCkKYGBgCgojIyMg5Li76aGM5ZG95ZCNCmBgYHtyfQp0b3BpY3NfbmFtZSA9IGMoIuaUv+m7qOitsOmhjCIsIuiDvea6kOitsOmhjCIsIueUn+aFi+S/neiCsuitsOmhjCIsIuaWueahiOitsOmhjCIpCmBgYAoKIyMgRG9jdW1lbnQg5Li76aGM5YiG5L2ICmBgYHtyfQojIGZvciBldmVyeSBkb2N1bWVudCB3ZSBoYXZlIGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG9mIGl0cyBjb250YWluZWQgdG9waWNzCnRtUmVzdWx0IDwtIHBvc3Rlcmlvcih0aGVfbGRhKQpkb2NfcHJvIDwtIHRtUmVzdWx0JHRvcGljcwpkb2N1bWVudF90b3BpY3MgPC0gZG9jX3Byb1ttZXRhZGF0YSRhcnRVcmwsXQpkb2N1bWVudF90b3BpY3NfZGYgPWRhdGEuZnJhbWUoZG9jdW1lbnRfdG9waWNzKQpjb2xuYW1lcyhkb2N1bWVudF90b3BpY3NfZGYpID0gdG9waWNzX25hbWUKcm93bmFtZXMoZG9jdW1lbnRfdG9waWNzX2RmKSA9IE5VTEwKbmV3c190b3BpYyA9IGNiaW5kKG1ldGFkYXRhLGRvY3VtZW50X3RvcGljc19kZikKYGBgCgo+IOePvuWcqOaIkeWAkeeci+avj+S4gOevh+eahOaWh+eroOWIhuS9iOS6hu+8gQoKIyMjIOafpeeci+eJueWumuS4u+mhjOeahOaWh+eroAorIOmAj+mBjuaJvuWIsOeJueWumuaWh+eroOeahOWIhuS9iOmAsuihjOaOkuW6j+S5i+W+jO+8jOWPr+S7peeci+WIsOatpOS4u+mhjOeahOavlOmHjemrmOeahOaWh+eroOWcqOiojuirluS7gOm6vOOAggoK5pS/6buo6K2w6aGMOuWkmueCuuaUv+ayu+S6uueJqeWwjeiXu+ekgeWFrOaKleeahOaUr+aMgeiIh+WQpueahOeci+azlQpleDrnlLHnkrDkv53lnJjpq5TnmbzotbfnmoTjgIznj43mhJvol7vnpIHlhazmipXpgKPnvbLjgI3lt7LnqoHnoLQ1MOiQrOWkp+mXnO+8jOWci+awkem7qOihqOaFi+Wkp+WKm+aUr+aMgeOAgeaZguS7o+WKm+mHj+m7qOS4u+W4remZs+akkuiPr+S7iuaWvOiHieabuOWkp+WKm+eCuuWFrOaKleWCrOmAo+e9sgpgYGB7ciAsZXZhbD1GQUxTRX0KbmV3c190b3BpYyAlPiUKICBhcnJhbmdlKGRlc2MoYOaUv+m7qOitsOmhjGApKSAlPiUgaGVhZCgzMCkgCmBgYAoK5pa55qGI6K2w6aGMOuWwjeiXu+ekgeWFrOaKleeahOiotOaxguWSjOitsOmhjOeahOiojuirlgpleDrooYzmlL/pmaLmj5Dlh7rkuInmjqXlpJbmjqg0NTXlhazlsLrmlrnmoYjvvIznuL3oqIjpm6LlsrgxLjLlhazph4zvvIzlrqPnqLHlsI3msr/lsrjlvbHpn7/mm7TovJXlvq7jgIHkuI3noLTlo57npIHpq5TvvIzpgoTlrqPnqLHmmK/jgIzpm5notI/jgI3mlrnmoYgKYGBge3IgLGV2YWw9RkFMU0V9Cm5ld3NfdG9waWMgJT4lCiAgYXJyYW5nZShkZXNjKGDmlrnmoYjorbDpoYxgKSkgJT4lIGhlYWQoMzApIApgYGAKCueUn+aFi+S/neiCsuitsOmhjDrok4vnrKzkuInlpKnnhLbmsKPmjqXmlLbnq5nlsI3ol7vnpIHoiIfnlJ/mhYvnkrDlooPnmoTnoLTlo54KZXg65qGD5ZyS5aSn5r2t6Je756SB55Sf5oWL5Zug5bCH6JOL56ys5LiJ5aSp54S25rCj5o6l5pS256uZ77yM5oGQ6KGd5pOK55Sf5oWL44CB6Zmk5LqG5qGD5ZyS5rK/5bK455qE6Je756SB5LmL5aSW77yM5paw56u555qE5paw6LGQ5rW35bK45Lmf5pyJ6Je756SB77yM5a246ICF5oyH5Ye677yM55W25Zyw55qE6Je756SB5piv5YWo5Y+w54Gj5pyA5Y2X56uv55qE6Je756SB77yM5YW35pyJ54m55q6K5oSP576pCmBgYHtyICxldmFsPUZBTFNFfQpuZXdzX3RvcGljICU+JQogICBhcnJhbmdlKGRlc2MoYOeUn+aFi+S/neiCsuitsOmhjGApKSAlPiVoZWFkKDMwKSAKYGBgCgrog73mupDorbDpoYw66Je756SB5YWs5oqV5bCN5Y+w5aGR44CB5aSp54S25rCj44CB54eD54Wk562J6IO95rqQ55qE5b2x6Z+/CmV4OuS4reayuemBuOWcqOingOWhmOiTi+WkqeeEtuawo+esrOS4ieaOpeaUtuerme+8jOiIh+S+m+mbu+eahOaZgueoi+aBr+aBr+ebuOmXnOOAgeiLpeeEoeWkp+a9reeHg+awo+S+m+mbu++8jOWPr+iDveWbnuWIsDIwMTTlubTliY3kuK3ngavoiIfpuqXlr67pm7vlu6DngavlipvlhajplovnmoTmjpLnorPph4/jgIHlpKfmva3ol7vnpIHoqK3nva7kuK3msrnkuInmjqXnq5nlvJXnmbzniK3orbDvvIzlpJblgrPnuL3ntbHolKHoi7Hmlofmib7kuIrlj7DloZHvvIzluIzmnJvnlLHlj7DloZHkvY3lnKjpuqXlr67mqZ/ntYTnlLHnh4PnhaTmlLnngrrnh4PnhaTvvIzkvZzngrrkuInmjqXnmoTmm7/ku6PmlrnmoYgKYGBge3IgLGV2YWw9RkFMU0V9Cm5ld3NfdG9waWMgJT4lCiAgYXJyYW5nZShkZXNjKGDog73mupDorbDpoYxgKSkgJT4laGVhZCgzMCkgCmBgYAoKCiMjIyDkuobop6PkuLvpoYzlnKjmmYLplpPnmoTororljJYK5Y+v5Lul5LqG6Kej5Yiw5Zyo5LiJ5pyI5Lu977yM6YCZ5Zub56iu6K2w6aGM6YO96KKr6KiO6KuW5Yiw77yM6ICM5Zub44CB5LqU5pyI6LyD6Yed5bCN6Je756SB5pys6Lqr55qE5YWs5oqV6K2w6aGM5Y676KiO6KuW77yM5LqU5pyI5pyA5Li76KaB55qE6K2w6aGM546L576O6Iqx5Y+s6ZaL6KiY6ICF5pyD77yM5o+Q5Ye65pS/6Zmi5LiJ5o6l5aSW5o6o5qGICmBgYHtyIHdhcm5pbmc9RkFMU0V9Cm5ld3NfdG9waWMgJT4lIAogIG11dGF0ZShhcnREYXRlID0gYXMuRGF0ZShhcnREYXRlKSkgJT4lCiAgZ3JvdXBfYnkoYXJ0RGF0ZSA9IGZvcm1hdChhcnREYXRlLCclWSVtJykpICU+JQogIHN1bW1hcmlzZV9pZihpcy5udW1lcmljLCBzdW0sIG5hLnJtID0gVFJVRSkgJT4lCiAgbWVsdChpZC52YXJzID0gImFydERhdGUiKSU+JQogIGdncGxvdCggYWVzKHg9YXJ0RGF0ZSwgeT12YWx1ZSwgZmlsbD12YXJpYWJsZSkpICsgCiAgdGhlbWUodGV4dCA9IGVsZW1lbnRfdGV4dChmYW1pbHkgPSAiSGVpdGkgVEMgTGlnaHQiKSkrCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIpICsgeWxhYigidmFsdWUiKSArIAogIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcz1teWNvbG9yc1tjKDEsNSw4LDEyKV0pKwogIHRoZW1lKGF4aXMudGV4dC54ID0gZWxlbWVudF90ZXh0KGFuZ2xlID0gOTAsIGhqdXN0ID0gMSkpCmBgYAoKIyMjIOS7peavlOS+i+S6huino+S4u+mhjOaZgumWk+iuiuWMlgoy5pyI5pyA5Li76KaB5piv5pS/6buo5LmL6ZaT5bCN6Je756SB5YWs5oqV55qE55yL5rOV77yM5Y+v6IO95pyD5qih57OK54Sm6bue77yM6ICM5LmL5b6M6LyD6Yed5bCN5q2k6K2w6aGM5Y675YGa6KiO6KuWCmBgYHtyIHdhcm5pbmc9RkFMU0V9Cm5ld3NfdG9waWMgJT4lCiAgbXV0YXRlKGFydERhdGUgPSBhcy5EYXRlKGFydERhdGUpKSAlPiUgCiAgZ3JvdXBfYnkoYXJ0RGF0ZSA9IGZvcm1hdChhcnREYXRlLCclWSVtJykpICU+JQogIHN1bW1hcmlzZV9pZihpcy5udW1lcmljLCBzdW0sIG5hLnJtID0gVFJVRSkgJT4lCiAgbWVsdChpZC52YXJzID0gImFydERhdGUiKSU+JQogIGdyb3VwX2J5KGFydERhdGUpJT4lCiAgbXV0YXRlKHRvdGFsX3ZhbHVlID1zdW0odmFsdWUpKSU+JQogIGdncGxvdCggYWVzKHg9YXJ0RGF0ZSwgeT12YWx1ZS90b3RhbF92YWx1ZSwgZmlsbD12YXJpYWJsZSkpICsKICB0aGVtZSh0ZXh0ID0gZWxlbWVudF90ZXh0KGZhbWlseSA9ICJIZWl0aSBUQyBMaWdodCIpKSsKICBnZW9tX2JhcihzdGF0ID0gImlkZW50aXR5IikgKyB5bGFiKCJwcm9wb3J0aW9uIikgKyAKICAgIHNjYWxlX2ZpbGxfbWFudWFsKHZhbHVlcz1teWNvbG9yc1tjKDEsNSw4LDEyKV0pKwogICAgdGhlbWUoYXhpcy50ZXh0LnggPSBlbGVtZW50X3RleHQoYW5nbGUgPSA5MCwgaGp1c3QgPSAxKSkKYGBgCgoKCgo=