図の右上のshowボタンを押すとRのコードが表示されます。

6.1 「近いか遠いか」をとらえる

6.1.1 ユークリッド距離とマンハッタン距離

library(conflicted)
library(tidyverse)

# 平方根記号を表示させる方法が分からない

# ポイントの定義
x1 <- 1
y1 <- 3
x2 <- 4
y2 <- 2

# ユークリッド距離の計算
euclidean_distance <- sqrt((x2 - x1)^2 + (y2 - y1)^2)

# マンハッタン距離の計算
manhattan_distance <- abs(x2 - x1) + abs(y2 - y1)

data.frame(x = c(x1, x2), y = c(y1, y2)) |>
  ggplot(aes(x = x, y = y)) +
  geom_point(color = "gold", size = 4) +
  geom_segment(aes(x = x1, y = y1, xend = x2, yend = y2), linetype = "dashed", color = "blue") +
  geom_segment(aes(x = x1, y = y1, xend = x2, yend = y1), linetype = "dashed", color = "salmon") +
  geom_segment(aes(x = x2, y = y1, xend = x2, yend = y2), linetype = "dashed", color = "salmon") +
  annotate("text", x = (x1 + x2) / 2, y = y1, label = abs(x2 - x1), color = "salmon", hjust = 1, vjust = -1) +
  annotate("text", x = x2, y = (y1 + y2) / 2, label = abs(y2 - y1), color = "salmon", hjust = -1, vjust = 1) +
  annotate("text", x = (x1 + x2) / 2, y = (y1 + y2) / 2, parse = TRUE,
           label =  paste("sqrt(10) == ", round(euclidean_distance, 2)),
           color = "blue", hjust = 1.1, vjust = 1.1) +
  labs(x = "x", y = "y") +
  coord_cartesian(xlim = c(0, 5), ylim = c(0, 5)) +
  theme(aspect.ratio = 1)

6.1.2 集団の中での逸脱度を測る

参考: 【R】分散共分散行列とユークリッド距離・マハラノビス距離の関係の可視化

library(conflicted)
library(tidyverse)
library(ellipse)
library(rvest)  #スクレイピング

# 公開されている元データを読み取る
df <- read_html("http://wiki.stat.ucla.edu/socr/index.php/SOCR_Data_MLB_HeightsWeights") |>
  html_table() |>
  pluck(2) |>
  drop_na() |>
  mutate( # 単位をSI単位に変換(Heightをメートルに、Weightをキログラムに)
    Height_m = `Height(inches)` * 0.0254,
    Weight_kg = `Weight(pounds)` * 0.453592
  )

# 共分散行列と平均ベクトルを計算
x_mat <- df[, c("Height_m", "Weight_kg")]
mean_vector <-  colMeans(x_mat)
cov_matrix <- cov(x_mat)

# マハラビノス距離を計算
df2 <- df |>
  mutate(
    Mahalanobis = t(t(x_mat) - mean_vector) %*% solve(cov_matrix) %*% (t(x_mat) - mean_vector) |> 
      diag() |> 
      sqrt()
    )

my_ellipse <- function(rad) {
  car::ellipse(center = mean_vector, shape = cov_matrix, radius = rad, draw = FALSE) |>
    as.data.frame() |>
    mutate(Height_m = x, Weight_kg = y, .keep = "unused")
}

df2 |>
  ggplot(aes(x = Height_m, y = Weight_kg))+
  geom_point(aes(color = Mahalanobis)) +
  scale_color_viridis_c() +
  geom_path(data = my_ellipse(1), color = 'red', linetype = 'dashed') + 
  geom_path(data = my_ellipse(2), color = 'red', linetype = 'dashed') + 
  geom_path(data = my_ellipse(3), color = 'red', linetype = 'dashed') + 
  geom_path(data = my_ellipse(4), color = 'red', linetype = 'dashed') +
  labs(title = "メジャーリーガーの身長と体重", x = "身長[m]", y = "体重[kg]", color = "マハラビノス距離") +
  theme(aspect.ratio = 1)

6.1.4 ネットワーク上の最短経路長

library(conflicted)
library(tidyverse)
library(igraph)
library(tidygraph)
library(ggraph)

# グラフ(バーベルグラフ)を生成
g1 <- g2 <- make_full_graph(5)
g <- disjoint_union(g1, g2) |>
  add_vertices(1) |>
  add_edges(c(5, 11, 11, 6))

# 基準となるノード(ここではノード 1)
source_node <- 1

# 基準ノードからの最短距離を計算
V(g)$label <- distances(g, v=source_node)[1, ]

# ネットワークを描画する際のノードの色を設定
V(g)$color <- if_else(V(g) == source_node, "1", "0")

# tidygraphへ変換
g_tidy <- as_tbl_graph(g, directed = FALSE)

g_tidy |>
  ggraph(layout = "igraph", algorithm = "kk") +
  geom_edge_link(color = "black", alpha = 0.5) +
  geom_node_label(aes(label = label, fill = color), size = 10) +
  theme_void() +
  theme(aspect.ratio = 1, legend.position = "none")
## Warning: Using the `size` aesthetic in this geom was deprecated in ggplot2 3.4.0.
## ℹ Please use `linewidth` in the `default_aes` field and elsewhere instead.
## This warning is displayed once every 8 hours.
## Call `lifecycle::last_lifecycle_warnings()` to see where this warning was
## generated.

6.2 分布同士の距離を測る

6.2.1 コルモゴロフ・スミルノフ統計量

library(conflicted)
library(tidyverse)
library(patchwork)

# シード値を固定
set.seed(42)

# サンプルサイズを設定。
sample_size <- 1000

# 一つ目と二つ目の分布ペアを生成
mean1 <- 0
std1 <- 1
mean2 <- 0.1
std2 <- 1
dist1 <- rnorm(sample_size, mean1, std1)
dist2 <- rnorm(sample_size, mean2, std2)

# Kolmogorov-Smirnov 統計量を計算
ks_test <- ks.test(dist1, dist2)

# データフレームを作成
df <- bind_rows(
  data.frame(value = dist1, distribution = "分布1"),
  data.frame(value = dist2, distribution = "分布2")
  )

# ヒストグラム
p1 <- df |>
  ggplot(aes(x = value, fill = distribution)) +
  geom_histogram(position="identity", alpha=0.5, bins=50) +
  labs(x="値", y="頻度", fill="分布") +
  theme(legend.title = element_blank(), legend.position = c(0.9, 0.8))

# CDF
p2 <- df |>
  ggplot(aes(x=value, color=distribution)) +
  stat_ecdf(geom = "step") +
  labs(x="値", y="累積分布", color="分布") +
  annotate("text", x = mean1 + 1, y = 0.5,
    label = paste("最大差:", round(ks_test$statistic, 3))
    ) +
  labs(title = paste(
    "コルモゴロフ・スミルノフ統計量:", round(ks_test$statistic, 3),
    ", p値:", round(ks_test$p.value, 3))
    ) +
  theme(legend.title = element_blank(), legend.position = c(0.1, 0.8))

p1 / p2

6.2.2 全変動距離を求める

library(conflicted)
library(tidyverse)

# サンプルデータの生成
num_samples <- 10000
set.seed(0)
samples1 <- rnorm(num_samples, -1, 1)
samples2 <- rnorm(num_samples, 1, 1)

# ビンの設定
bins <- seq(-5, 5, length.out = 51)

# ヒストグラムを計算
hist1 <- hist(samples1, breaks=bins, plot=FALSE)
hist2 <- hist(samples2, breaks=bins, plot=FALSE)

# ヒストグラムを密度に変換
hist1$density <- hist1$counts / sum(hist1$counts) / diff(bins)[1]
hist2$density <- hist2$counts / sum(hist2$counts) / diff(bins)[1]

# 全変動距離(TVD)を計算
tvd_sample <- 0.5 * sum(abs(hist1$density - hist2$density)) * diff(bins)[1]

# データフレームを作成
df <- bind_rows(
  data.frame(value = samples1, distribution = "分布1"),
  data.frame(value = samples2, distribution = "分布2")
  )

ggplot() +
  geom_histogram(data = df, aes(x=value, y=after_stat(density), fill=distribution), position='identity', alpha=0.3, bins=50) +
  labs(x='値', y='確率密度', fill='分布') +
  geom_line(data=data.frame(x=hist1$mids, y=hist1$density, distribution = "分布1"), aes(x=x, y=y), color='red') +
  geom_line(data=data.frame(x=hist2$mids, y=hist2$density, distribution = "分布2"), aes(x=x, y=y), color='blue') +
  labs(title = paste("全変動距離: ", round(tvd_sample, 4))) +
  theme(legend.position = c(0.9, 0.8))

6.2.3 ワッサースタイン計量の計算のイメージ

library(conflicted)
library(tidyverse)

# シード値を固定
set.seed(42)

# サンプルデータの生成
num_samples <- 50
samples1 <- sort(rnorm(num_samples, 0, 1))
samples2 <- sort(rnorm(num_samples, 2, 1))

bind_rows(
  data.frame(value = samples1, distribution = rep("分布1", num_samples)),
  data.frame(value = samples2, distribution = rep("分布2", num_samples))
  ) |>
  ggplot(aes(x=value, y=distribution)) +
  geom_segment(
    data=data.frame(
      x1=samples1, x2=samples2, 
      y1=rep("分布1", num_samples), y2=rep("分布2", num_samples)),
    aes(x=x1, xend=x2, y=y1, yend=y2), color='gray') +
  geom_point(aes(color=factor(distribution)), size=3) +
  scale_color_manual(values=c('red', 'blue'), labels=c("分布1", "分布2")) +
  labs(x="値", y="分布", color="分布", title = "一致させるために必要な総移動距離") +
  theme(legend.position="none", axis.title = element_blank())

6.2.4 カルバック・ライブラー情報量とイェンセン・シャノン情報量

library(conflicted)
library(tidyverse)

# KL情報量を計算する関数
kl_divergence <- function(p, q) {
  return(sum(ifelse(p != 0, p * log(p / q), 0)))
}

# サンプルデータの生成
num_samples <- 10000
set.seed(42)
samples1 <- rnorm(num_samples, 0, 0.5)
samples2 <- rnorm(num_samples, 2, 1)

# サンプルを[-1, 3]の範囲に絞り込む
filtered_samples1 <- samples1[samples1 >= -1 & samples1 <= 3]
filtered_samples2 <- samples2[samples2 >= -1 & samples2 <= 3]

# 非ゼロのビンを確保するために、限られた範囲でヒストグラムを生成
limited_bins <- seq(-1, 3, length.out = 50)
hist1 <- hist(filtered_samples1, breaks = limited_bins, plot = FALSE)
hist2 <- hist(filtered_samples2, breaks = limited_bins, plot = FALSE)

# ヒストグラムを正規化
hist1$density <- hist1$counts / sum(hist1$counts * diff(limited_bins))
hist2$density <- hist2$counts / sum(hist2$counts * diff(limited_bins))

# KLダイバージェンスを再計算
kl_1_to_2 <- kl_divergence(hist1$density, hist2$density)
kl_2_to_1 <- kl_divergence(hist2$density, hist1$density)

# JSダイバージェンスを再計算
js_divergence <- 0.5 * (
  kl_divergence(hist1$density, 0.5 * (hist1$density + hist2$density)) +
    kl_divergence(hist2$density, 0.5 * (hist1$density + hist2$density))
  )

# ダイバージェンスを表示
df1 <- data.frame(x = hist1$mids, y = hist1$density)
df2 <- data.frame(x = hist2$mids, y = hist2$density)

ggplot() +
  geom_col(data = df1, aes(x = x, y = y), fill = "blue", alpha = 0.5) +
  geom_col(data = df2, aes(x = x, y = y), fill = "red", alpha = 0.5) +  
  labs(title = paste0("KL情報量: ", round(kl_1_to_2, 4), " (1→2), ∞ (2→1), JS情報量: ", round(js_divergence, 4)),
       x = "", y = "相対頻度")

6.2.5 様々な分布間距離指標

library(conflicted)
library(tidyverse)
library(patchwork)
library(entropy)
library(transport)

# 相互情報量
mutual_information <- function(x, y, n_bins=20) {
  hist_x <- hist(x, breaks=n_bins, plot=FALSE)$counts
  hist_y <- hist(y, breaks=n_bins, plot=FALSE)$counts
  mi <- mi.empirical(hist_x, hist_y)
  return(mi)
}

# スミルノフ-コロモゴロフ統計量
ks_statistic <- function(x, y) {
  return(ks.test(x, y)$statistic)
}

# カイ二乗統計量
chi_square_statistic <- function(x, y, bin_edges) {
  hist_x <- hist(x, breaks=bin_edges, plot=FALSE)$counts
  hist_y <- hist(y, breaks=bin_edges, plot=FALSE)$counts
  return(chisq.test(hist_x, hist_y)$statistic)
}

# KLダイバージェンス
kl_divergence <- function(p, q) {
  kl_div <- entropy::KL.empirical(p, q)
  return(ifelse(is.finite(kl_div), kl_div, 0))
}

# JSダイバージェンス
js_divergence <- function(p, q) {
  m <- 0.5 * (p + q)
  return(0.5 * kl_divergence(p, m) + 0.5 * kl_divergence(q, m))
}

# 全変動距離
total_variation_distance <- function(p, q) {
  return(0.5 * sum(abs(p - q)))
}

# 指標を計算
compute_metrics <- function(dist_a, dist_b, bin_edges) {
  hist_a <- hist(dist_a, breaks=bin_edges, plot=FALSE)$density
  hist_b <- hist(dist_b, breaks=bin_edges, plot=FALSE)$density
  return(c(
    ks_statistic(dist_a, dist_b),
    total_variation_distance(hist_a, hist_b),
    #    transport::wasserstein1d(bin_edges[-length(bin_edges)], bin_edges[-length(bin_edges)], hist_a, hist_b),
    transport::wasserstein1d(dist_a, dist_b),
    js_divergence(hist_a, hist_b)
  ))
}

# サンプルデータ生成
sample_size <- 1000
dist1_1 <- rnorm(sample_size, 0, 1)# 分布1
dist1_2 <- rnorm(sample_size, 1, 1)# 分布2
dist2_1 <- rnorm(sample_size, -1, 0.5)# 分布3
dist2_2 <- rnorm(sample_size, 1, 1.5)# 分布4
dist3_1 <- c(# 分布5と分布6の混合分布
  rnorm(sample_size / 2, -2, 1),
  rnorm(sample_size / 2, 2, 1)
  )
dist3_2 <- rnorm(sample_size, 0, 1.5)# 分布7

# ビンの幅をすべての分布で同じにするためにすべてのデータから最小値と最大値を取得
all_data <- c(dist1_1, dist1_2, dist2_1, dist2_2, dist3_1, dist3_2)
min_val <- min(all_data)
max_val <- max(all_data)

# ビンのエッジを計算
bin_edges <- seq(min_val, max_val, length.out = 21)

# 各距離指標を計算(警告が出る)
distances1 <- compute_metrics(dist1_1, dist1_2, bin_edges)
distances2 <- compute_metrics(dist2_1, dist2_2, bin_edges)
distances3 <- compute_metrics(dist3_1, dist3_2, bin_edges)

# 棒グラフのY軸のスケールを調整
max_distance <- 2.5

# 分布ペアのヒストグラムを描画
df1_1 <- data.frame(x = dist1_1, group = rep("dist1_1", length(dist1_1)))
df1_2 <- data.frame(x = dist1_2, group = rep("dist1_2", length(dist1_2)))
df2_1 <- data.frame(x = dist2_1, group = rep("dist2_1", length(dist2_1)))
df2_2 <- data.frame(x = dist2_2, group = rep("dist2_2", length(dist2_2)))
df3_1 <- data.frame(x = dist3_1, group = rep("dist3_1", length(dist3_1)))
df3_2 <- data.frame(x = dist3_2, group = rep("dist3_2", length(dist3_2)))

p1 <- ggplot() +
  geom_histogram(data = df1_1, aes(x = x, fill = group), bins = length(bin_edges), alpha = 0.5) +
  geom_histogram(data = df1_2, aes(x = x, fill = group), bins = length(bin_edges), alpha = 0.5) +
  labs(title = "分布ペア1") +
  theme(legend.position="none", axis.title = element_blank())

p2 <- ggplot() +
  geom_histogram(data = df2_1, aes(x = x, fill = group), bins = length(bin_edges), alpha = 0.5) +
  geom_histogram(data = df2_2, aes(x = x, fill = group), bins = length(bin_edges), alpha = 0.5) +
  labs(title = "分布ペア2") +
  theme(legend.position="none", axis.title = element_blank())

p3 <- ggplot() +
  geom_histogram(data = df3_1, aes(x = x, fill = group), bins = length(bin_edges), alpha = 0.5) +
  geom_histogram(data = df3_2, aes(x = x, fill = group), bins = length(bin_edges), alpha = 0.5) +
  labs(title = "分布ペア3") +
  theme(legend.position="none", axis.title = element_blank())

# 各指標の距離をグループ棒グラフとして描画
metrics <- c("コルモゴロフ・スミルノフ統計量", "全変動距離", "ワッサースタイン距離", "JS情報量")
p4 <- data.frame(
  metrics = factor(rep(metrics, 3), levels = metrics),
  distances = c(distances1, distances2, distances3),
  group = rep(c("分布ペア1", "分布ペア2", "分布ペア3"), each = length(metrics))
  ) |>
  ggplot(aes(x = metrics, y = distances, fill = group)) +
  geom_bar(stat = "identity", position = "dodge") +
  labs(title = '各指標における分布ペアの距離') +
  theme(
    axis.title = element_blank(),
    legend.title = element_blank(),
    legend.position = c(0.9, 0.7)
    )

(p1 + p2 + p3) / p4

6.3 ペアになった分布間の距離指標

6.3.1 相関として類似度をとらえる

library(conflicted)
library(tidyverse)
library(ggpubr)

# シード値の設定
set.seed(42)

# 書籍の数
n_books <- 100

# Aさんのレビュー
a_scores <- n_books |> rnorm(60, 15) |> round() |> pmin(100) |> pmax(0) 

# Bさんのレビュー(Aさんと高い相関)
b_scores <- (a_scores + (n_books |> rnorm(0, 10) |>round())) |> pmin(100) |> pmax(0)

# Cさんのレビュー(Aさんと緩い逆相関)
c_scores <- (100 - a_scores + (n_books |> rnorm(0, 20) |> round())) |> pmin(100) |> pmax(0)

# 相関係数の計算
corr_ab <- cor(a_scores, b_scores)
corr_ac <- cor(a_scores, c_scores)

# 線形回帰の描画
df <- data.frame(A=a_scores, B=b_scores, C=c_scores)

p1 <- df |>
  ggplot(aes(x = A, y = B)) +
  geom_point(color = "blue") +
  geom_smooth(formula = y ~ x, method = "lm", color="blue", fill="blue") +
  labs(title = paste("AさんとBさんの類似度 r =", round(corr_ab, 2)),
       x = "Aさんによる評価", y = "Bさんによる評価") +
  coord_cartesian(xlim = c(0, 100), ylim = c(0, 100)) +
  theme(aspect.ratio = 1)

p2 <- df |>
  ggplot(aes(x = A, y = C)) +
  geom_point(color = "red") +
  geom_smooth(formula = y ~ x, method = "lm", color="red", fill="red") +
  labs(title = paste("AさんとCさんの類似度 r =", round(corr_ac, 2)),
       x = "Aさんによる評価", y = "Cさんによる評価")  +
  coord_cartesian(xlim = c(0, 100), ylim = c(0, 100)) +
  theme(aspect.ratio = 1)

p1 + p2

6.3.2 時系列同士の相関で類似度を測る

library(conflicted)
library(tidyverse)

# データを読み込む
data_df <- read_tsv(
  "https://raw.githubusercontent.com/tkEzaki/data_visualization/main/6%E7%AB%A0/data/brain.txt"
  )

data_df |>
  mutate(time_steps = seq(0, (nrow(data_df) - 1) * 2.5, by = 2.5)) |>
  pivot_longer(!time_steps) |>
  ggplot(aes(x = time_steps, y = value, color = name)) +
  geom_point(size = 0.5) +  
  geom_line() +
  labs(x = "時間 [秒]", y = "活動量", color = "脳領域") +
  theme(aspect.ratio = 1/6)

library(conflicted)
library(tidyverse)

data_df <- read_tsv(
  "https://raw.githubusercontent.com/tkEzaki/data_visualization/main/6%E7%AB%A0/data/brain.txt"
  )

# r値の計算
r_value <- cor(data_df$ROI1, data_df$ROI2)

# 散布図と回帰直線、信頼区間を描画
data_df |>
  ggplot(aes(x = ROI1, y = ROI2)) +
  geom_path(color = "grey40") +
  geom_point() +  
  geom_smooth(formula = y ~ x, method = "lm", color = "red", fill = "red") +
  coord_cartesian(xlim = c(-2.5, 2.5), ylim = c(-2.5, 2.5)) +
  theme_bw() +
  theme(aspect.ratio = 1) +  
  annotate("text", x = -1.5, y = 2.5, label = paste("r =", round(r_value, 2)), size = 8) +
  labs(x = "脳領域1", y = "脳領域2")

6.3.3 サンプリングされた相関係数とフィッシャー変換

library(conflicted)
library(tidyverse)
library(patchwork)
library(MASS)

generate_correlation <- function(target_corr=0.8, size=100, iter = 100000) {
  group <- rep(1:iter, each = size)
  samples <- split(
    mvrnorm(n = size * iter, mu = c(0, 0), Sigma = matrix(c(1, target_corr, target_corr, 1), nrow=2)),
    group)
  correlation <- map_dbl(samples, \(x) {
    mat <- matrix(x, 100)
    cor(mat[,1], mat[,2])
    })
  fisher_z <- 0.5 * log((1 + correlation) / (1 - correlation))
  return(data.frame(correlation,fisher_z))
  }

results <- generate_correlation()

# ヒストグラムを描画
bins_orig <- seq(0.6, 1.0, length.out = 41)
bins_z <- seq(0.6, 1.5, length.out = 41)

# 正規分布のラインを引く
p1 <- results |>
  ggplot(aes(x=correlation)) +
  geom_histogram(aes(y=after_stat(density)), bins=length(bins_orig)-1, fill="blue", alpha=0.6) +
  stat_function(fun = dnorm,
                args = list(mean = mean(results$correlation), sd = sd(results$correlation)),
                color="darkblue", linetype="dashed") +
  labs(title="サンプリングされた相関係数", x=expression(italic(r))) +
  theme(axis.title.y = element_blank())
  

p2 <- results |>
  ggplot(aes(x=fisher_z)) +
  geom_histogram(aes(y=after_stat(density)), bins=length(bins_z)-1, fill="red", alpha=0.6) +
  stat_function(fun = dnorm,
                args = list(mean = mean(results$fisher_z), sd = sd(results$fisher_z)),
                color="darkred", linetype="dashed") +
  labs(title="フィッシャー変換後の相関係数", x=expression(italic(z))) +
  theme(axis.title.y = element_blank())

p1 + p2

6.3.4 他の変数の影響を考慮して相関をとらえる

library(conflicted)
library(tidyverse)
library(patchwork)

# Seabornのtipsデータセットを使用
df <- read.csv("https://raw.githubusercontent.com/mwaskom/seaborn-data/master/tips.csv")

# 相関係数の計算
corr_total_tip <- cor(df$total_bill, df$tip)
corr_total_size <- cor(df$total_bill, df$size)
corr_tip_size <- cor(df$tip, df$size)

# 散布図と回帰直線を描画する
p1 <- df |>
  ggplot(aes(x=size, y=tip)) +
  geom_point(alpha=0.4, color="darkgreen") +
  geom_smooth(formula = y ~ x, method="lm", color="darkgreen", fill ="darkgreen") +
  labs(title=paste("グループの人数とチップの額\n r = ", round(corr_tip_size, 2)),
       x = "グループの人数", y = "チップの額 [$]") +
  theme(aspect.ratio = 1)

p2 <- df |>
  ggplot(aes(x=total_bill, y=tip)) +
  geom_point(alpha=0.4, color="darkblue") +
  geom_smooth(formula = y ~ x, method="lm", color="darkblue", fill="darkblue") +
  labs(title=paste("会計額とチップの額\n r = ", round(corr_total_tip, 2)),
       x = "会計額 [$]", y ="チップの額 [$]") +
  theme(aspect.ratio = 1)

p3 <- ggplot(df, aes(x=size, y=total_bill)) +
  geom_point(alpha=0.4, color="darkred") +
  geom_smooth(formula = y ~ x, method="lm", color="darkred", fill="darkred") +
  labs(title=paste("グループの人数と会計額\n r = ", round(corr_total_size, 2)),
       x = "グループの人数", y ="会計額 [$]") +
  theme(aspect.ratio = 1)

p1 + p2 + p3

6.3.6 予測モデルの誤差

library(conflicted)
library(tidyverse)
library(palmerpenguins)
library(rsample)

data("penguins")

# 前処理
penguins_clean <- penguins |>
  dplyr::select(species, body_mass_g, bill_length_mm, bill_depth_mm, flipper_length_mm) |>
  drop_na()
  
# データ分割
penguins_split <- penguins_clean |>
  initial_split(prop = 0.8, strata = body_mass_g)

penguins_train <- training(penguins_split)
penguins_test <- testing(penguins_split)

fit <- lm(body_mass_g ~ bill_length_mm + bill_depth_mm + flipper_length_mm, data = penguins_train)

df_wide <- penguins_test |>
  dplyr::select(species, body_mass_g) |>
  mutate(pred = predict(fit, newdata = penguins_test)) |>
  arrange(species) |>
  mutate(id = row_number())

df_long <- df_wide |>
  pivot_longer(!c(species, id)) |>
  mutate(type = case_when(
    name == "pred" ~ "予測値",
    name == "body_mass_g" ~ species
  ))

df_long |>
  ggplot(aes(x = id, y = value, color = type)) +
  geom_segment(data = df_wide, aes(x = id, y = body_mass_g, xend = id, yend = pred), color = "black", linetype = "dashed") +
  geom_point() +
  scale_color_manual(values = c("royalblue", "salmon", "forestgreen", "black")) +
  labs(title = "個体ごとの真の体重と予測された体重", x = "個体番号", y = "体重 [g]") +
  theme(legend.title = element_blank(), legend.position = c(0.9, 0.2))

6.4 「つながり」をとらえる

6.4.1 サイコロの同時確率と条件付き確率

library(conflicted)
library(tidyverse)
library(patchwork)
library(viridis)
##  要求されたパッケージ viridisLite をロード中です
# 確率分布を準備
joint_prob <- matrix(c(
  1 / 36 - 1 / 72,     1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 - 1 / 72,     1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 - 1 / 72,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 - 1 / 72,     1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 - 1 / 72,     1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5,
  1 / 36 + 1 / 72 / 5, 1 / 36 + 1 / 72 / 5, 1 / 36 - 1 / 72
  ), nrow = 6, byrow = TRUE)

joint_prob <- joint_prob / sum(joint_prob)

# サンプルをjoint_probに従って1000回サンプリング
set.seed(0)
library(tictoc)
samples <- sample.int(36, size = 1000000, replace = TRUE, prob = c(joint_prob))

# サンプリングされた値を(X, Y)ペアに変換
samples_die1 <- (samples - 1) %/% 6 + 1
samples_die2 <- (samples - 1) %% 6 + 1

# ヒートマップ
p1 <- data.frame(
  samples_die1 = factor((samples - 1) %/% 6 + 1),
  samples_die2 = factor((samples - 1) %% 6 + 1)
) |>
  summarise(n = n(), .by = c(samples_die1, samples_die2)) |>
  mutate(prob = n / 1000000) |>
  ggplot(aes(x = samples_die1, y = samples_die2, fill = prob, label = format(round(prob, 3)), nsmall = 3)) +
  geom_tile() +
  geom_text(color = "white", size = 3) +
  scale_fill_gradient(low = "darkblue", high = "darkred") +
  theme_minimal() +
  theme(legend.title = element_blank(),
        aspect.ratio = 1) +
  labs(x = "サイコロAの出目", y = "サイコロBの出目")

# サイコロAが1が出たときのサイコロBの結果を棒グラフで描画
samples_die2_when_die1_is_1 <- samples_die2[samples_die1 == 1]

p2 <- data.frame(table(samples_die2_when_die1_is_1) / length(samples_die2_when_die1_is_1)) |>
  ggplot(aes(y = Freq, x = samples_die2_when_die1_is_1)) +
  geom_col(fill = "royalblue", color = "black") +
  labs(x = "サイコロBの出目", y = "相対頻度") +
  theme(aspect.ratio = 1)

p1 + p2

6.4.3 各試行での出目の発生確率

library(conflicted)
library(tidyverse)
library(patchwork)

# サイコロの実験をシミュレーションする関数
simulate_dice_experiment <- function(n_trials) {
  # ボーナスタイムと通常時の確率
  bonus_prob <-  c(1 / 11, 2 / 11, 2 / 11, 2 / 11, 2 / 11, 2 / 11)
  normal_prob <- c(2 / 11, 9 / 55, 9 / 55, 9 / 55, 9 / 55, 9 / 55)
  
  set.seed(5)
  die1 <- sample.int(6, size = n_trials, prob = normal_prob, replace = TRUE)  # 通常時のサイコロAの出目
  set.seed(1)  
  die2 <- sample.int(6, size = n_trials, prob = normal_prob, replace = TRUE)  # 通常時のサイコロBの出目
  set.seed(2)  
  bonus_time_die1 <- sample.int(6, size = n_trials, prob = bonus_prob, replace = TRUE)  # ボーナスタイム時のサイコロAの出目
  set.seed(3)
  bonus_time_die2 <- sample.int(6, size = n_trials, prob = bonus_prob, replace = TRUE)  # ボーナスタイム時のサイコロBの出目  
  
  die1_lag <- dplyr::lag(die1)
  
  dies <- data.frame(
      die1, die2, die1_lag, bonus_time_die1, bonus_time_die2,
      samples_die1 = if_else(die1_lag != 1 | is.na(die1_lag), die1, bonus_time_die1),
      samples_die2 = if_else(die1_lag != 1 | is.na(die1_lag), die2, bonus_time_die2)
      )
  
  prob <- dies |>
    summarise(n = n(), .by = c(samples_die1, samples_die2)) |>
    mutate(
      samples_die1 = factor(samples_die1), 
      samples_die2 = factor(samples_die2),
      prob = n / n_trials, .keep = "unused"
      )
  
  return(list(dies = dies, prob = prob))
  }

result <- simulate_dice_experiment(100000)

# ヒートマップ
p1 <- result$prob |>
  ggplot(aes(x = samples_die1, y = samples_die2, fill = prob, label = format(round(prob, 3)), nsmall = 3)) +
  geom_tile() +
  geom_text(color = "white", size = 3) +
  scale_fill_gradient(low = "darkblue", high = "darkred") +
  theme_minimal() +
  labs(y = "サイコロAの出目", x = "サイコロBの出目")+
  theme(legend.title = element_blank(), aspect.ratio = 1)
  
# サイコロAが1が出たときのサイコロBの結果を棒グラフで描画する関数
p2 <- result$dies |>
  dplyr::filter(die1 == 1) |>
  summarise(n = n(), .by = samples_die2) |>
  mutate(prob = n / sum(n)) |>
  ggplot(aes(x = samples_die2, y = prob)) +
  geom_col(fill = "royalblue", color = "black") +
  labs(x = "サイコロBの出目", y = "相対頻度")

p1 + p2

6.4.4 サイコロ出目の時間的な関係

bonus_rect <- result$dies |>
  slice_head(n = 50) |>
  mutate(trial = 1:50) |>
  dplyr::filter(die1_lag == 1) |>
  dplyr::select(trial) |>
  mutate(xmin = trial - 0.5, xmax = trial + 0.5)

df <- data.frame(
  trial = 1:50,
  die1 = result$dies$samples_die1[1:50],
  die2 = result$dies$samples_die2[1:50]
  ) |>
  pivot_longer(!trial)

p3 <- ggplot() +
  geom_rect(data = bonus_rect, aes(xmin=xmin, xmax=xmax, ymin=1, ymax=6), fill="royalblue", alpha = 0.5) +
  geom_line(data = df, aes(x = trial, y = value, color = name)) +
  geom_point(data = df, aes(x = trial, y = value, color = name)) +
  labs(x = "試行回数", y = "サイコロの出目", color = "🎲") +
  theme(legend.title = element_blank()) +
  theme_bw()

p4 <- result$dies |>
  dplyr::filter(die1_lag == 1) |>
  summarise(n = n(), .by = samples_die1) |>
  mutate(prob = n / sum(n)) |>
  ggplot(aes(x = samples_die1, y = prob)) +
  geom_col(fill = "royalblue", color = "black") +
  labs(x = "サイコロAの出目", y = "相対頻度")

p5 <- result$dies |>
  dplyr::filter(die1_lag == 1) |>
  summarise(n = n(), .by = samples_die2) |>
  mutate(prob = n / sum(n)) |>
  ggplot(aes(x = samples_die2, y = prob)) +
  geom_col(fill = "salmon", color = "black") +
  labs(x = "サイコロBの出目", y = "相対頻度")

p3 / (p4 + p5)

第6章はここまで。

LS0tCnRpdGxlOiAi56ysNueroCDplqLkv4LmgKfjgpLjgajjgonjgYjjgovmjIfmqJnljJYiCmF1dGhvcjogIk9zYW11LCBNT1JJTU9UTyIKZGF0ZTogImByIFN5cy5EYXRlKClgIgpvdXRwdXQ6CiAgaHRtbF9kb2N1bWVudDogCiAgICBjb2RlX2Rvd25sb2FkOiB0cnVlCiAgICB0b2M6IHllcwogICAgdG9jX2RlcHRoOiAzCiAgICB0aGVtZTogdW5pdGVkICAgIAogICAgbWRfZXh0ZW5zaW9uczogIi1hc2NpaV9pZGVudGlmaWVycyIKICAgIHRvY19mbG9hdDogeWVzCiAgICBmaWdfd2lkdGg6IDcuNQogICAgZmlnX2hlaWdodDogNS42MjUKICAgIGRldjogcmFnZ19wbmcKICAgIGhpZ2hsaWdodDogdGFuZ28KICAgIGNvZGVfZm9sZGluZzogaGlkZQogICAgZGZfcHJpbnQ6IHBhZ2VkCi0tLQoKYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChlY2hvID0gVFJVRSkKYGBgCgrlm7Pjga7lj7PkuIrjga5gc2hvd2Djg5zjgr/jg7PjgpLmirzjgZnjgahS44Gu44Kz44O844OJ44GM6KGo56S644GV44KM44G+44GZ44CCCgojIyA2LjEg44CM6L+R44GE44GL6YGg44GE44GL44CN44KS44Go44KJ44GI44KLCgojIyMgNi4xLjEg44Om44O844Kv44Oq44OD44OJ6Led6Zui44Go44Oe44Oz44OP44OD44K/44Oz6Led6ZuiCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQoKIyDlubPmlrnmoLnoqJjlj7fjgpLooajnpLrjgZXjgZvjgovmlrnms5XjgYzliIbjgYvjgonjgarjgYQKCiMg44Od44Kk44Oz44OI44Gu5a6a576pCngxIDwtIDEKeTEgPC0gMwp4MiA8LSA0CnkyIDwtIDIKCiMg44Om44O844Kv44Oq44OD44OJ6Led6Zui44Gu6KiI566XCmV1Y2xpZGVhbl9kaXN0YW5jZSA8LSBzcXJ0KCh4MiAtIHgxKV4yICsgKHkyIC0geTEpXjIpCgojIOODnuODs+ODj+ODg+OCv+ODs+i3nembouOBruioiOeulwptYW5oYXR0YW5fZGlzdGFuY2UgPC0gYWJzKHgyIC0geDEpICsgYWJzKHkyIC0geTEpCgpkYXRhLmZyYW1lKHggPSBjKHgxLCB4MiksIHkgPSBjKHkxLCB5MikpIHw+CiAgZ2dwbG90KGFlcyh4ID0geCwgeSA9IHkpKSArCiAgZ2VvbV9wb2ludChjb2xvciA9ICJnb2xkIiwgc2l6ZSA9IDQpICsKICBnZW9tX3NlZ21lbnQoYWVzKHggPSB4MSwgeSA9IHkxLCB4ZW5kID0geDIsIHllbmQgPSB5MiksIGxpbmV0eXBlID0gImRhc2hlZCIsIGNvbG9yID0gImJsdWUiKSArCiAgZ2VvbV9zZWdtZW50KGFlcyh4ID0geDEsIHkgPSB5MSwgeGVuZCA9IHgyLCB5ZW5kID0geTEpLCBsaW5ldHlwZSA9ICJkYXNoZWQiLCBjb2xvciA9ICJzYWxtb24iKSArCiAgZ2VvbV9zZWdtZW50KGFlcyh4ID0geDIsIHkgPSB5MSwgeGVuZCA9IHgyLCB5ZW5kID0geTIpLCBsaW5ldHlwZSA9ICJkYXNoZWQiLCBjb2xvciA9ICJzYWxtb24iKSArCiAgYW5ub3RhdGUoInRleHQiLCB4ID0gKHgxICsgeDIpIC8gMiwgeSA9IHkxLCBsYWJlbCA9IGFicyh4MiAtIHgxKSwgY29sb3IgPSAic2FsbW9uIiwgaGp1c3QgPSAxLCB2anVzdCA9IC0xKSArCiAgYW5ub3RhdGUoInRleHQiLCB4ID0geDIsIHkgPSAoeTEgKyB5MikgLyAyLCBsYWJlbCA9IGFicyh5MiAtIHkxKSwgY29sb3IgPSAic2FsbW9uIiwgaGp1c3QgPSAtMSwgdmp1c3QgPSAxKSArCiAgYW5ub3RhdGUoInRleHQiLCB4ID0gKHgxICsgeDIpIC8gMiwgeSA9ICh5MSArIHkyKSAvIDIsIHBhcnNlID0gVFJVRSwKICAgICAgICAgICBsYWJlbCA9ICBwYXN0ZSgic3FydCgxMCkgPT0gIiwgcm91bmQoZXVjbGlkZWFuX2Rpc3RhbmNlLCAyKSksCiAgICAgICAgICAgY29sb3IgPSAiYmx1ZSIsIGhqdXN0ID0gMS4xLCB2anVzdCA9IDEuMSkgKwogIGxhYnMoeCA9ICJ4IiwgeSA9ICJ5IikgKwogIGNvb3JkX2NhcnRlc2lhbih4bGltID0gYygwLCA1KSwgeWxpbSA9IGMoMCwgNSkpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQpgYGAKCiMjIyA2LjEuMiDpm4blm6Pjga7kuK3jgafjga7pgLjohLHluqbjgpLmuKzjgosKCuWPguiAg++8mgpb44CQUuOAkeWIhuaVo+WFseWIhuaVo+ihjOWIl+OBqOODpuODvOOCr+ODquODg+ODiei3nembouODu+ODnuODj+ODqeODjuODk+OCuei3nembouOBrumWouS/guOBruWPr+imluWMll0oaHR0cHM6Ly93d3cuYW5hcmNoaXZlLWJldGEuY29tL2VudHJ5LzIwMjIvMDgvMzAvMDgwNTAwKQoKYGBge3J9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoZWxsaXBzZSkKbGlicmFyeShydmVzdCkgICPjgrnjgq/jg6zjgqTjg5Tjg7PjgrAKCiMg5YWs6ZaL44GV44KM44Gm44GE44KL5YWD44OH44O844K/44KS6Kqt44G/5Y+W44KLCmRmIDwtIHJlYWRfaHRtbCgiaHR0cDovL3dpa2kuc3RhdC51Y2xhLmVkdS9zb2NyL2luZGV4LnBocC9TT0NSX0RhdGFfTUxCX0hlaWdodHNXZWlnaHRzIikgfD4KICBodG1sX3RhYmxlKCkgfD4KICBwbHVjaygyKSB8PgogIGRyb3BfbmEoKSB8PgogIG11dGF0ZSggIyDljZjkvY3jgpJTSeWNmOS9jeOBq+WkieaPm++8iEhlaWdodOOCkuODoeODvOODiOODq+OBq+OAgVdlaWdodOOCkuOCreODreOCsOODqeODoOOBq++8iQogICAgSGVpZ2h0X20gPSBgSGVpZ2h0KGluY2hlcylgICogMC4wMjU0LAogICAgV2VpZ2h0X2tnID0gYFdlaWdodChwb3VuZHMpYCAqIDAuNDUzNTkyCiAgKQoKIyDlhbHliIbmlaPooYzliJfjgajlubPlnYfjg5njgq/jg4jjg6vjgpLoqIjnrpcKeF9tYXQgPC0gZGZbLCBjKCJIZWlnaHRfbSIsICJXZWlnaHRfa2ciKV0KbWVhbl92ZWN0b3IgPC0gIGNvbE1lYW5zKHhfbWF0KQpjb3ZfbWF0cml4IDwtIGNvdih4X21hdCkKCiMg44Oe44OP44Op44OT44OO44K56Led6Zui44KS6KiI566XCmRmMiA8LSBkZiB8PgogIG11dGF0ZSgKICAgIE1haGFsYW5vYmlzID0gdCh0KHhfbWF0KSAtIG1lYW5fdmVjdG9yKSAlKiUgc29sdmUoY292X21hdHJpeCkgJSolICh0KHhfbWF0KSAtIG1lYW5fdmVjdG9yKSB8PiAKICAgICAgZGlhZygpIHw+IAogICAgICBzcXJ0KCkKICAgICkKCm15X2VsbGlwc2UgPC0gZnVuY3Rpb24ocmFkKSB7CiAgY2FyOjplbGxpcHNlKGNlbnRlciA9IG1lYW5fdmVjdG9yLCBzaGFwZSA9IGNvdl9tYXRyaXgsIHJhZGl1cyA9IHJhZCwgZHJhdyA9IEZBTFNFKSB8PgogICAgYXMuZGF0YS5mcmFtZSgpIHw+CiAgICBtdXRhdGUoSGVpZ2h0X20gPSB4LCBXZWlnaHRfa2cgPSB5LCAua2VlcCA9ICJ1bnVzZWQiKQp9CgpkZjIgfD4KICBnZ3Bsb3QoYWVzKHggPSBIZWlnaHRfbSwgeSA9IFdlaWdodF9rZykpKwogIGdlb21fcG9pbnQoYWVzKGNvbG9yID0gTWFoYWxhbm9iaXMpKSArCiAgc2NhbGVfY29sb3JfdmlyaWRpc19jKCkgKwogIGdlb21fcGF0aChkYXRhID0gbXlfZWxsaXBzZSgxKSwgY29sb3IgPSAncmVkJywgbGluZXR5cGUgPSAnZGFzaGVkJykgKyAKICBnZW9tX3BhdGgoZGF0YSA9IG15X2VsbGlwc2UoMiksIGNvbG9yID0gJ3JlZCcsIGxpbmV0eXBlID0gJ2Rhc2hlZCcpICsgCiAgZ2VvbV9wYXRoKGRhdGEgPSBteV9lbGxpcHNlKDMpLCBjb2xvciA9ICdyZWQnLCBsaW5ldHlwZSA9ICdkYXNoZWQnKSArIAogIGdlb21fcGF0aChkYXRhID0gbXlfZWxsaXBzZSg0KSwgY29sb3IgPSAncmVkJywgbGluZXR5cGUgPSAnZGFzaGVkJykgKwogIGxhYnModGl0bGUgPSAi44Oh44K444Oj44O844Oq44O844Ks44O844Gu6Lqr6ZW344Go5L2T6YeNIiwgeCA9ICLouqvplbdbbV0iLCB5ID0gIuS9k+mHjVtrZ10iLCBjb2xvciA9ICLjg57jg4/jg6njg5Pjg47jgrnot53pm6IiKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKYGBgCgojIyMgNi4xLjQg44ON44OD44OI44Ov44O844Kv5LiK44Gu5pyA55+t57WM6Lev6ZW3CgpgYGB7cn0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShpZ3JhcGgpCmxpYnJhcnkodGlkeWdyYXBoKQpsaWJyYXJ5KGdncmFwaCkKCiMg44Kw44Op44OV77yI44OQ44O844OZ44Or44Kw44Op44OV77yJ44KS55Sf5oiQCmcxIDwtIGcyIDwtIG1ha2VfZnVsbF9ncmFwaCg1KQpnIDwtIGRpc2pvaW50X3VuaW9uKGcxLCBnMikgfD4KICBhZGRfdmVydGljZXMoMSkgfD4KICBhZGRfZWRnZXMoYyg1LCAxMSwgMTEsIDYpKQoKIyDln7rmupbjgajjgarjgovjg47jg7zjg4nvvIjjgZPjgZPjgafjga/jg47jg7zjg4kgMe+8iQpzb3VyY2Vfbm9kZSA8LSAxCgojIOWfuua6luODjuODvOODieOBi+OCieOBruacgOefrei3nembouOCkuioiOeulwpWKGcpJGxhYmVsIDwtIGRpc3RhbmNlcyhnLCB2PXNvdXJjZV9ub2RlKVsxLCBdCgojIOODjeODg+ODiOODr+ODvOOCr+OCkuaPj+eUu+OBmeOCi+mam+OBruODjuODvOODieOBruiJsuOCkuioreWumgpWKGcpJGNvbG9yIDwtIGlmX2Vsc2UoVihnKSA9PSBzb3VyY2Vfbm9kZSwgIjEiLCAiMCIpCgojIHRpZHlncmFwaOOBuOWkieaPmwpnX3RpZHkgPC0gYXNfdGJsX2dyYXBoKGcsIGRpcmVjdGVkID0gRkFMU0UpCgpnX3RpZHkgfD4KICBnZ3JhcGgobGF5b3V0ID0gImlncmFwaCIsIGFsZ29yaXRobSA9ICJrayIpICsKICBnZW9tX2VkZ2VfbGluayhjb2xvciA9ICJibGFjayIsIGFscGhhID0gMC41KSArCiAgZ2VvbV9ub2RlX2xhYmVsKGFlcyhsYWJlbCA9IGxhYmVsLCBmaWxsID0gY29sb3IpLCBzaXplID0gMTApICsKICB0aGVtZV92b2lkKCkgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEsIGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKYGBgCgojIyA2LjIg5YiG5biD5ZCM5aOr44Gu6Led6Zui44KS5ris44KLCgojIyMgNi4yLjEg44Kz44Or44Oi44K044Ot44OV44O744K544Of44Or44OO44OV57Wx6KiI6YePCgpgYGB7ciBmaWcuaGVpZ2h0PTcuNSwgZmlnLndpZHRoPTcuNX0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShwYXRjaHdvcmspCgojIOOCt+ODvOODieWApOOCkuWbuuWumgpzZXQuc2VlZCg0MikKCiMg44K144Oz44OX44Or44K144Kk44K644KS6Kit5a6a44CCCnNhbXBsZV9zaXplIDwtIDEwMDAKCiMg5LiA44Gk55uu44Go5LqM44Gk55uu44Gu5YiG5biD44Oa44Ki44KS55Sf5oiQCm1lYW4xIDwtIDAKc3RkMSA8LSAxCm1lYW4yIDwtIDAuMQpzdGQyIDwtIDEKZGlzdDEgPC0gcm5vcm0oc2FtcGxlX3NpemUsIG1lYW4xLCBzdGQxKQpkaXN0MiA8LSBybm9ybShzYW1wbGVfc2l6ZSwgbWVhbjIsIHN0ZDIpCgojIEtvbG1vZ29yb3YtU21pcm5vdiDntbHoqIjph4/jgpLoqIjnrpcKa3NfdGVzdCA8LSBrcy50ZXN0KGRpc3QxLCBkaXN0MikKCiMg44OH44O844K/44OV44Os44O844Og44KS5L2c5oiQCmRmIDwtIGJpbmRfcm93cygKICBkYXRhLmZyYW1lKHZhbHVlID0gZGlzdDEsIGRpc3RyaWJ1dGlvbiA9ICLliIbluIMxIiksCiAgZGF0YS5mcmFtZSh2YWx1ZSA9IGRpc3QyLCBkaXN0cmlidXRpb24gPSAi5YiG5biDMiIpCiAgKQoKIyDjg5Ljgrnjg4jjgrDjg6njg6AKcDEgPC0gZGYgfD4KICBnZ3Bsb3QoYWVzKHggPSB2YWx1ZSwgZmlsbCA9IGRpc3RyaWJ1dGlvbikpICsKICBnZW9tX2hpc3RvZ3JhbShwb3NpdGlvbj0iaWRlbnRpdHkiLCBhbHBoYT0wLjUsIGJpbnM9NTApICsKICBsYWJzKHg9IuWApCIsIHk9Iumgu+W6piIsIGZpbGw9IuWIhuW4gyIpICsKICB0aGVtZShsZWdlbmQudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksIGxlZ2VuZC5wb3NpdGlvbiA9IGMoMC45LCAwLjgpKQoKIyBDREYKcDIgPC0gZGYgfD4KICBnZ3Bsb3QoYWVzKHg9dmFsdWUsIGNvbG9yPWRpc3RyaWJ1dGlvbikpICsKICBzdGF0X2VjZGYoZ2VvbSA9ICJzdGVwIikgKwogIGxhYnMoeD0i5YCkIiwgeT0i57Sv56mN5YiG5biDIiwgY29sb3I9IuWIhuW4gyIpICsKICBhbm5vdGF0ZSgidGV4dCIsIHggPSBtZWFuMSArIDEsIHkgPSAwLjUsCiAgICBsYWJlbCA9IHBhc3RlKCLmnIDlpKflt646Iiwgcm91bmQoa3NfdGVzdCRzdGF0aXN0aWMsIDMpKQogICAgKSArCiAgbGFicyh0aXRsZSA9IHBhc3RlKAogICAgIuOCs+ODq+ODouOCtOODreODleODu+OCueODn+ODq+ODjuODlee1seioiOmHjzoiLCByb3VuZChrc190ZXN0JHN0YXRpc3RpYywgMyksCiAgICAiLCBw5YCkOiIsIHJvdW5kKGtzX3Rlc3QkcC52YWx1ZSwgMykpCiAgICApICsKICB0aGVtZShsZWdlbmQudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksIGxlZ2VuZC5wb3NpdGlvbiA9IGMoMC4xLCAwLjgpKQoKcDEgLyBwMgpgYGAKCiMjIyA2LjIuMiDlhajlpInli5Xot53pm6LjgpLmsYLjgoHjgosKCmBgYHtyfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQoKIyDjgrXjg7Pjg5fjg6vjg4fjg7zjgr/jga7nlJ/miJAKbnVtX3NhbXBsZXMgPC0gMTAwMDAKc2V0LnNlZWQoMCkKc2FtcGxlczEgPC0gcm5vcm0obnVtX3NhbXBsZXMsIC0xLCAxKQpzYW1wbGVzMiA8LSBybm9ybShudW1fc2FtcGxlcywgMSwgMSkKCiMg44OT44Oz44Gu6Kit5a6aCmJpbnMgPC0gc2VxKC01LCA1LCBsZW5ndGgub3V0ID0gNTEpCgojIOODkuOCueODiOOCsOODqeODoOOCkuioiOeulwpoaXN0MSA8LSBoaXN0KHNhbXBsZXMxLCBicmVha3M9YmlucywgcGxvdD1GQUxTRSkKaGlzdDIgPC0gaGlzdChzYW1wbGVzMiwgYnJlYWtzPWJpbnMsIHBsb3Q9RkFMU0UpCgojIOODkuOCueODiOOCsOODqeODoOOCkuWvhuW6puOBq+WkieaPmwpoaXN0MSRkZW5zaXR5IDwtIGhpc3QxJGNvdW50cyAvIHN1bShoaXN0MSRjb3VudHMpIC8gZGlmZihiaW5zKVsxXQpoaXN0MiRkZW5zaXR5IDwtIGhpc3QyJGNvdW50cyAvIHN1bShoaXN0MiRjb3VudHMpIC8gZGlmZihiaW5zKVsxXQoKIyDlhajlpInli5Xot53pm6LvvIhUVkTvvInjgpLoqIjnrpcKdHZkX3NhbXBsZSA8LSAwLjUgKiBzdW0oYWJzKGhpc3QxJGRlbnNpdHkgLSBoaXN0MiRkZW5zaXR5KSkgKiBkaWZmKGJpbnMpWzFdCgojIOODh+ODvOOCv+ODleODrOODvOODoOOCkuS9nOaIkApkZiA8LSBiaW5kX3Jvd3MoCiAgZGF0YS5mcmFtZSh2YWx1ZSA9IHNhbXBsZXMxLCBkaXN0cmlidXRpb24gPSAi5YiG5biDMSIpLAogIGRhdGEuZnJhbWUodmFsdWUgPSBzYW1wbGVzMiwgZGlzdHJpYnV0aW9uID0gIuWIhuW4gzIiKQogICkKCmdncGxvdCgpICsKICBnZW9tX2hpc3RvZ3JhbShkYXRhID0gZGYsIGFlcyh4PXZhbHVlLCB5PWFmdGVyX3N0YXQoZGVuc2l0eSksIGZpbGw9ZGlzdHJpYnV0aW9uKSwgcG9zaXRpb249J2lkZW50aXR5JywgYWxwaGE9MC4zLCBiaW5zPTUwKSArCiAgbGFicyh4PSflgKQnLCB5PSfnorrnjoflr4bluqYnLCBmaWxsPSfliIbluIMnKSArCiAgZ2VvbV9saW5lKGRhdGE9ZGF0YS5mcmFtZSh4PWhpc3QxJG1pZHMsIHk9aGlzdDEkZGVuc2l0eSwgZGlzdHJpYnV0aW9uID0gIuWIhuW4gzEiKSwgYWVzKHg9eCwgeT15KSwgY29sb3I9J3JlZCcpICsKICBnZW9tX2xpbmUoZGF0YT1kYXRhLmZyYW1lKHg9aGlzdDIkbWlkcywgeT1oaXN0MiRkZW5zaXR5LCBkaXN0cmlidXRpb24gPSAi5YiG5biDMiIpLCBhZXMoeD14LCB5PXkpLCBjb2xvcj0nYmx1ZScpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoIuWFqOWkieWLlei3nembojogIiwgcm91bmQodHZkX3NhbXBsZSwgNCkpKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gYygwLjksIDAuOCkpCgpgYGAKCiMjIyA2LjIuMyDjg6/jg4PjgrXjg7zjgrnjgr/jgqTjg7PoqIjph4/jga7oqIjnrpfjga7jgqTjg6Hjg7zjgrgKCmBgYHtyfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQoKIyDjgrfjg7zjg4nlgKTjgpLlm7rlrpoKc2V0LnNlZWQoNDIpCgojIOOCteODs+ODl+ODq+ODh+ODvOOCv+OBrueUn+aIkApudW1fc2FtcGxlcyA8LSA1MApzYW1wbGVzMSA8LSBzb3J0KHJub3JtKG51bV9zYW1wbGVzLCAwLCAxKSkKc2FtcGxlczIgPC0gc29ydChybm9ybShudW1fc2FtcGxlcywgMiwgMSkpCgpiaW5kX3Jvd3MoCiAgZGF0YS5mcmFtZSh2YWx1ZSA9IHNhbXBsZXMxLCBkaXN0cmlidXRpb24gPSByZXAoIuWIhuW4gzEiLCBudW1fc2FtcGxlcykpLAogIGRhdGEuZnJhbWUodmFsdWUgPSBzYW1wbGVzMiwgZGlzdHJpYnV0aW9uID0gcmVwKCLliIbluIMyIiwgbnVtX3NhbXBsZXMpKQogICkgfD4KICBnZ3Bsb3QoYWVzKHg9dmFsdWUsIHk9ZGlzdHJpYnV0aW9uKSkgKwogIGdlb21fc2VnbWVudCgKICAgIGRhdGE9ZGF0YS5mcmFtZSgKICAgICAgeDE9c2FtcGxlczEsIHgyPXNhbXBsZXMyLCAKICAgICAgeTE9cmVwKCLliIbluIMxIiwgbnVtX3NhbXBsZXMpLCB5Mj1yZXAoIuWIhuW4gzIiLCBudW1fc2FtcGxlcykpLAogICAgYWVzKHg9eDEsIHhlbmQ9eDIsIHk9eTEsIHllbmQ9eTIpLCBjb2xvcj0nZ3JheScpICsKICBnZW9tX3BvaW50KGFlcyhjb2xvcj1mYWN0b3IoZGlzdHJpYnV0aW9uKSksIHNpemU9MykgKwogIHNjYWxlX2NvbG9yX21hbnVhbCh2YWx1ZXM9YygncmVkJywgJ2JsdWUnKSwgbGFiZWxzPWMoIuWIhuW4gzEiLCAi5YiG5biDMiIpKSArCiAgbGFicyh4PSLlgKQiLCB5PSLliIbluIMiLCBjb2xvcj0i5YiG5biDIiwgdGl0bGUgPSAi5LiA6Ie044GV44Gb44KL44Gf44KB44Gr5b+F6KaB44Gq57eP56e75YuV6Led6ZuiIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbj0ibm9uZSIsIGF4aXMudGl0bGUgPSBlbGVtZW50X2JsYW5rKCkpCmBgYAoKCiMjIyA2LjIuNCDjgqvjg6vjg5Djg4Pjgq/jg7vjg6njgqTjg5bjg6njg7zmg4XloLHph4/jgajjgqTjgqfjg7Pjgrvjg7Pjg7vjgrfjg6Pjg47jg7Pmg4XloLHph48KCmBgYHtyfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQoKIyBLTOaDheWgsemHj+OCkuioiOeul+OBmeOCi+mWouaVsAprbF9kaXZlcmdlbmNlIDwtIGZ1bmN0aW9uKHAsIHEpIHsKICByZXR1cm4oc3VtKGlmZWxzZShwICE9IDAsIHAgKiBsb2cocCAvIHEpLCAwKSkpCn0KCiMg44K144Oz44OX44Or44OH44O844K/44Gu55Sf5oiQCm51bV9zYW1wbGVzIDwtIDEwMDAwCnNldC5zZWVkKDQyKQpzYW1wbGVzMSA8LSBybm9ybShudW1fc2FtcGxlcywgMCwgMC41KQpzYW1wbGVzMiA8LSBybm9ybShudW1fc2FtcGxlcywgMiwgMSkKCiMg44K144Oz44OX44Or44KSWy0xLCAzXeOBruevhOWbsuOBq+e1nuOCiui+vOOCgApmaWx0ZXJlZF9zYW1wbGVzMSA8LSBzYW1wbGVzMVtzYW1wbGVzMSA+PSAtMSAmIHNhbXBsZXMxIDw9IDNdCmZpbHRlcmVkX3NhbXBsZXMyIDwtIHNhbXBsZXMyW3NhbXBsZXMyID49IC0xICYgc2FtcGxlczIgPD0gM10KCiMg6Z2e44K844Ot44Gu44OT44Oz44KS56K65L+d44GZ44KL44Gf44KB44Gr44CB6ZmQ44KJ44KM44Gf56+E5Zuy44Gn44OS44K544OI44Kw44Op44Og44KS55Sf5oiQCmxpbWl0ZWRfYmlucyA8LSBzZXEoLTEsIDMsIGxlbmd0aC5vdXQgPSA1MCkKaGlzdDEgPC0gaGlzdChmaWx0ZXJlZF9zYW1wbGVzMSwgYnJlYWtzID0gbGltaXRlZF9iaW5zLCBwbG90ID0gRkFMU0UpCmhpc3QyIDwtIGhpc3QoZmlsdGVyZWRfc2FtcGxlczIsIGJyZWFrcyA9IGxpbWl0ZWRfYmlucywgcGxvdCA9IEZBTFNFKQoKIyDjg5Ljgrnjg4jjgrDjg6njg6DjgpLmraPopo/ljJYKaGlzdDEkZGVuc2l0eSA8LSBoaXN0MSRjb3VudHMgLyBzdW0oaGlzdDEkY291bnRzICogZGlmZihsaW1pdGVkX2JpbnMpKQpoaXN0MiRkZW5zaXR5IDwtIGhpc3QyJGNvdW50cyAvIHN1bShoaXN0MiRjb3VudHMgKiBkaWZmKGxpbWl0ZWRfYmlucykpCgojIEtM44OA44Kk44OQ44O844K444Kn44Oz44K544KS5YaN6KiI566XCmtsXzFfdG9fMiA8LSBrbF9kaXZlcmdlbmNlKGhpc3QxJGRlbnNpdHksIGhpc3QyJGRlbnNpdHkpCmtsXzJfdG9fMSA8LSBrbF9kaXZlcmdlbmNlKGhpc3QyJGRlbnNpdHksIGhpc3QxJGRlbnNpdHkpCgojIEpT44OA44Kk44OQ44O844K444Kn44Oz44K544KS5YaN6KiI566XCmpzX2RpdmVyZ2VuY2UgPC0gMC41ICogKAogIGtsX2RpdmVyZ2VuY2UoaGlzdDEkZGVuc2l0eSwgMC41ICogKGhpc3QxJGRlbnNpdHkgKyBoaXN0MiRkZW5zaXR5KSkgKwogICAga2xfZGl2ZXJnZW5jZShoaXN0MiRkZW5zaXR5LCAwLjUgKiAoaGlzdDEkZGVuc2l0eSArIGhpc3QyJGRlbnNpdHkpKQogICkKCiMg44OA44Kk44OQ44O844K444Kn44Oz44K544KS6KGo56S6CmRmMSA8LSBkYXRhLmZyYW1lKHggPSBoaXN0MSRtaWRzLCB5ID0gaGlzdDEkZGVuc2l0eSkKZGYyIDwtIGRhdGEuZnJhbWUoeCA9IGhpc3QyJG1pZHMsIHkgPSBoaXN0MiRkZW5zaXR5KQoKZ2dwbG90KCkgKwogIGdlb21fY29sKGRhdGEgPSBkZjEsIGFlcyh4ID0geCwgeSA9IHkpLCBmaWxsID0gImJsdWUiLCBhbHBoYSA9IDAuNSkgKwogIGdlb21fY29sKGRhdGEgPSBkZjIsIGFlcyh4ID0geCwgeSA9IHkpLCBmaWxsID0gInJlZCIsIGFscGhhID0gMC41KSArICAKICBsYWJzKHRpdGxlID0gcGFzdGUwKCJLTOaDheWgsemHjzogIiwgcm91bmQoa2xfMV90b18yLCA0KSwgIiAoMeKGkjIpLCDiiJ4gKDLihpIxKSwgSlPmg4XloLHph486ICIsIHJvdW5kKGpzX2RpdmVyZ2VuY2UsIDQpKSwKICAgICAgIHggPSAiIiwgeSA9ICLnm7jlr77poLvluqYiKQpgYGAKCiMjIyA2LjIuNSDmp5jjgIXjgarliIbluIPplpPot53pm6LmjIfmqJkKCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocGF0Y2h3b3JrKQpsaWJyYXJ5KGVudHJvcHkpCmxpYnJhcnkodHJhbnNwb3J0KQoKIyDnm7jkupLmg4XloLHph48KbXV0dWFsX2luZm9ybWF0aW9uIDwtIGZ1bmN0aW9uKHgsIHksIG5fYmlucz0yMCkgewogIGhpc3RfeCA8LSBoaXN0KHgsIGJyZWFrcz1uX2JpbnMsIHBsb3Q9RkFMU0UpJGNvdW50cwogIGhpc3RfeSA8LSBoaXN0KHksIGJyZWFrcz1uX2JpbnMsIHBsb3Q9RkFMU0UpJGNvdW50cwogIG1pIDwtIG1pLmVtcGlyaWNhbChoaXN0X3gsIGhpc3RfeSkKICByZXR1cm4obWkpCn0KCiMg44K544Of44Or44OO44OVLeOCs+ODreODouOCtOODreODlee1seioiOmHjwprc19zdGF0aXN0aWMgPC0gZnVuY3Rpb24oeCwgeSkgewogIHJldHVybihrcy50ZXN0KHgsIHkpJHN0YXRpc3RpYykKfQoKIyDjgqvjgqTkuozkuZfntbHoqIjph48KY2hpX3NxdWFyZV9zdGF0aXN0aWMgPC0gZnVuY3Rpb24oeCwgeSwgYmluX2VkZ2VzKSB7CiAgaGlzdF94IDwtIGhpc3QoeCwgYnJlYWtzPWJpbl9lZGdlcywgcGxvdD1GQUxTRSkkY291bnRzCiAgaGlzdF95IDwtIGhpc3QoeSwgYnJlYWtzPWJpbl9lZGdlcywgcGxvdD1GQUxTRSkkY291bnRzCiAgcmV0dXJuKGNoaXNxLnRlc3QoaGlzdF94LCBoaXN0X3kpJHN0YXRpc3RpYykKfQoKIyBLTOODgOOCpOODkOODvOOCuOOCp+ODs+OCuQprbF9kaXZlcmdlbmNlIDwtIGZ1bmN0aW9uKHAsIHEpIHsKICBrbF9kaXYgPC0gZW50cm9weTo6S0wuZW1waXJpY2FsKHAsIHEpCiAgcmV0dXJuKGlmZWxzZShpcy5maW5pdGUoa2xfZGl2KSwga2xfZGl2LCAwKSkKfQoKIyBKU+ODgOOCpOODkOODvOOCuOOCp+ODs+OCuQpqc19kaXZlcmdlbmNlIDwtIGZ1bmN0aW9uKHAsIHEpIHsKICBtIDwtIDAuNSAqIChwICsgcSkKICByZXR1cm4oMC41ICoga2xfZGl2ZXJnZW5jZShwLCBtKSArIDAuNSAqIGtsX2RpdmVyZ2VuY2UocSwgbSkpCn0KCiMg5YWo5aSJ5YuV6Led6ZuiCnRvdGFsX3ZhcmlhdGlvbl9kaXN0YW5jZSA8LSBmdW5jdGlvbihwLCBxKSB7CiAgcmV0dXJuKDAuNSAqIHN1bShhYnMocCAtIHEpKSkKfQoKIyDmjIfmqJnjgpLoqIjnrpcKY29tcHV0ZV9tZXRyaWNzIDwtIGZ1bmN0aW9uKGRpc3RfYSwgZGlzdF9iLCBiaW5fZWRnZXMpIHsKICBoaXN0X2EgPC0gaGlzdChkaXN0X2EsIGJyZWFrcz1iaW5fZWRnZXMsIHBsb3Q9RkFMU0UpJGRlbnNpdHkKICBoaXN0X2IgPC0gaGlzdChkaXN0X2IsIGJyZWFrcz1iaW5fZWRnZXMsIHBsb3Q9RkFMU0UpJGRlbnNpdHkKICByZXR1cm4oYygKICAgIGtzX3N0YXRpc3RpYyhkaXN0X2EsIGRpc3RfYiksCiAgICB0b3RhbF92YXJpYXRpb25fZGlzdGFuY2UoaGlzdF9hLCBoaXN0X2IpLAogICAgIyAgICB0cmFuc3BvcnQ6Ondhc3NlcnN0ZWluMWQoYmluX2VkZ2VzWy1sZW5ndGgoYmluX2VkZ2VzKV0sIGJpbl9lZGdlc1stbGVuZ3RoKGJpbl9lZGdlcyldLCBoaXN0X2EsIGhpc3RfYiksCiAgICB0cmFuc3BvcnQ6Ondhc3NlcnN0ZWluMWQoZGlzdF9hLCBkaXN0X2IpLAogICAganNfZGl2ZXJnZW5jZShoaXN0X2EsIGhpc3RfYikKICApKQp9CgojIOOCteODs+ODl+ODq+ODh+ODvOOCv+eUn+aIkApzYW1wbGVfc2l6ZSA8LSAxMDAwCmRpc3QxXzEgPC0gcm5vcm0oc2FtcGxlX3NpemUsIDAsIDEpIyDliIbluIPvvJEKZGlzdDFfMiA8LSBybm9ybShzYW1wbGVfc2l6ZSwgMSwgMSkjIOWIhuW4g++8kgpkaXN0Ml8xIDwtIHJub3JtKHNhbXBsZV9zaXplLCAtMSwgMC41KSMg5YiG5biD77yTCmRpc3QyXzIgPC0gcm5vcm0oc2FtcGxlX3NpemUsIDEsIDEuNSkjIOWIhuW4g++8lApkaXN0M18xIDwtIGMoIyDliIbluIPvvJXjgajliIbluIPvvJbjga7mt7flkIjliIbluIMKICBybm9ybShzYW1wbGVfc2l6ZSAvIDIsIC0yLCAxKSwKICBybm9ybShzYW1wbGVfc2l6ZSAvIDIsIDIsIDEpCiAgKQpkaXN0M18yIDwtIHJub3JtKHNhbXBsZV9zaXplLCAwLCAxLjUpIyDliIbluIPvvJcKCiMg44OT44Oz44Gu5bmF44KS44GZ44G544Gm44Gu5YiG5biD44Gn5ZCM44GY44Gr44GZ44KL44Gf44KB44Gr44GZ44G544Gm44Gu44OH44O844K/44GL44KJ5pyA5bCP5YCk44Go5pyA5aSn5YCk44KS5Y+W5b6XCmFsbF9kYXRhIDwtIGMoZGlzdDFfMSwgZGlzdDFfMiwgZGlzdDJfMSwgZGlzdDJfMiwgZGlzdDNfMSwgZGlzdDNfMikKbWluX3ZhbCA8LSBtaW4oYWxsX2RhdGEpCm1heF92YWwgPC0gbWF4KGFsbF9kYXRhKQoKIyDjg5Pjg7Pjga7jgqjjg4PjgrjjgpLoqIjnrpcKYmluX2VkZ2VzIDwtIHNlcShtaW5fdmFsLCBtYXhfdmFsLCBsZW5ndGgub3V0ID0gMjEpCgojIOWQhOi3nembouaMh+aomeOCkuioiOeul++8iOitpuWRiuOBjOWHuuOCi++8iQpkaXN0YW5jZXMxIDwtIGNvbXB1dGVfbWV0cmljcyhkaXN0MV8xLCBkaXN0MV8yLCBiaW5fZWRnZXMpCmRpc3RhbmNlczIgPC0gY29tcHV0ZV9tZXRyaWNzKGRpc3QyXzEsIGRpc3QyXzIsIGJpbl9lZGdlcykKZGlzdGFuY2VzMyA8LSBjb21wdXRlX21ldHJpY3MoZGlzdDNfMSwgZGlzdDNfMiwgYmluX2VkZ2VzKQoKIyDmo5LjgrDjg6njg5Xjga5Z6Lu444Gu44K544Kx44O844Or44KS6Kq/5pW0Cm1heF9kaXN0YW5jZSA8LSAyLjUKCiMg5YiG5biD44Oa44Ki44Gu44OS44K544OI44Kw44Op44Og44KS5o+P55S7CmRmMV8xIDwtIGRhdGEuZnJhbWUoeCA9IGRpc3QxXzEsIGdyb3VwID0gcmVwKCJkaXN0MV8xIiwgbGVuZ3RoKGRpc3QxXzEpKSkKZGYxXzIgPC0gZGF0YS5mcmFtZSh4ID0gZGlzdDFfMiwgZ3JvdXAgPSByZXAoImRpc3QxXzIiLCBsZW5ndGgoZGlzdDFfMikpKQpkZjJfMSA8LSBkYXRhLmZyYW1lKHggPSBkaXN0Ml8xLCBncm91cCA9IHJlcCgiZGlzdDJfMSIsIGxlbmd0aChkaXN0Ml8xKSkpCmRmMl8yIDwtIGRhdGEuZnJhbWUoeCA9IGRpc3QyXzIsIGdyb3VwID0gcmVwKCJkaXN0Ml8yIiwgbGVuZ3RoKGRpc3QyXzIpKSkKZGYzXzEgPC0gZGF0YS5mcmFtZSh4ID0gZGlzdDNfMSwgZ3JvdXAgPSByZXAoImRpc3QzXzEiLCBsZW5ndGgoZGlzdDNfMSkpKQpkZjNfMiA8LSBkYXRhLmZyYW1lKHggPSBkaXN0M18yLCBncm91cCA9IHJlcCgiZGlzdDNfMiIsIGxlbmd0aChkaXN0M18yKSkpCgpwMSA8LSBnZ3Bsb3QoKSArCiAgZ2VvbV9oaXN0b2dyYW0oZGF0YSA9IGRmMV8xLCBhZXMoeCA9IHgsIGZpbGwgPSBncm91cCksIGJpbnMgPSBsZW5ndGgoYmluX2VkZ2VzKSwgYWxwaGEgPSAwLjUpICsKICBnZW9tX2hpc3RvZ3JhbShkYXRhID0gZGYxXzIsIGFlcyh4ID0geCwgZmlsbCA9IGdyb3VwKSwgYmlucyA9IGxlbmd0aChiaW5fZWRnZXMpLCBhbHBoYSA9IDAuNSkgKwogIGxhYnModGl0bGUgPSAi5YiG5biD44Oa44KiMSIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb249Im5vbmUiLCBheGlzLnRpdGxlID0gZWxlbWVudF9ibGFuaygpKQoKcDIgPC0gZ2dwbG90KCkgKwogIGdlb21faGlzdG9ncmFtKGRhdGEgPSBkZjJfMSwgYWVzKHggPSB4LCBmaWxsID0gZ3JvdXApLCBiaW5zID0gbGVuZ3RoKGJpbl9lZGdlcyksIGFscGhhID0gMC41KSArCiAgZ2VvbV9oaXN0b2dyYW0oZGF0YSA9IGRmMl8yLCBhZXMoeCA9IHgsIGZpbGwgPSBncm91cCksIGJpbnMgPSBsZW5ndGgoYmluX2VkZ2VzKSwgYWxwaGEgPSAwLjUpICsKICBsYWJzKHRpdGxlID0gIuWIhuW4g+ODmuOCojIiKSArCiAgdGhlbWUobGVnZW5kLnBvc2l0aW9uPSJub25lIiwgYXhpcy50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSkKCnAzIDwtIGdncGxvdCgpICsKICBnZW9tX2hpc3RvZ3JhbShkYXRhID0gZGYzXzEsIGFlcyh4ID0geCwgZmlsbCA9IGdyb3VwKSwgYmlucyA9IGxlbmd0aChiaW5fZWRnZXMpLCBhbHBoYSA9IDAuNSkgKwogIGdlb21faGlzdG9ncmFtKGRhdGEgPSBkZjNfMiwgYWVzKHggPSB4LCBmaWxsID0gZ3JvdXApLCBiaW5zID0gbGVuZ3RoKGJpbl9lZGdlcyksIGFscGhhID0gMC41KSArCiAgbGFicyh0aXRsZSA9ICLliIbluIPjg5rjgqIzIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbj0ibm9uZSIsIGF4aXMudGl0bGUgPSBlbGVtZW50X2JsYW5rKCkpCgojIOWQhOaMh+aomeOBrui3nembouOCkuOCsOODq+ODvOODl+ajkuOCsOODqeODleOBqOOBl+OBpuaPj+eUuwptZXRyaWNzIDwtIGMoIuOCs+ODq+ODouOCtOODreODleODu+OCueODn+ODq+ODjuODlee1seioiOmHjyIsICLlhajlpInli5Xot53pm6IiLCAi44Ov44OD44K144O844K544K/44Kk44Oz6Led6ZuiIiwgIkpT5oOF5aCx6YePIikKcDQgPC0gZGF0YS5mcmFtZSgKICBtZXRyaWNzID0gZmFjdG9yKHJlcChtZXRyaWNzLCAzKSwgbGV2ZWxzID0gbWV0cmljcyksCiAgZGlzdGFuY2VzID0gYyhkaXN0YW5jZXMxLCBkaXN0YW5jZXMyLCBkaXN0YW5jZXMzKSwKICBncm91cCA9IHJlcChjKCLliIbluIPjg5rjgqIxIiwgIuWIhuW4g+ODmuOCojIiLCAi5YiG5biD44Oa44KiMyIpLCBlYWNoID0gbGVuZ3RoKG1ldHJpY3MpKQogICkgfD4KICBnZ3Bsb3QoYWVzKHggPSBtZXRyaWNzLCB5ID0gZGlzdGFuY2VzLCBmaWxsID0gZ3JvdXApKSArCiAgZ2VvbV9iYXIoc3RhdCA9ICJpZGVudGl0eSIsIHBvc2l0aW9uID0gImRvZGdlIikgKwogIGxhYnModGl0bGUgPSAn5ZCE5oyH5qiZ44Gr44GK44GR44KL5YiG5biD44Oa44Ki44Gu6Led6ZuiJykgKwogIHRoZW1lKAogICAgYXhpcy50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSwKICAgIGxlZ2VuZC50aXRsZSA9IGVsZW1lbnRfYmxhbmsoKSwKICAgIGxlZ2VuZC5wb3NpdGlvbiA9IGMoMC45LCAwLjcpCiAgICApCgoocDEgKyBwMiArIHAzKSAvIHA0CmBgYAoKIyMgNi4zIOODmuOCouOBq+OBquOBo+OBn+WIhuW4g+mWk+OBrui3nembouaMh+aomQoKIyMjIDYuMy4xIOebuOmWouOBqOOBl+OBpumhnuS8vOW6puOCkuOBqOOCieOBiOOCiwoKYGBge3J9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkoZ2dwdWJyKQoKIyDjgrfjg7zjg4nlgKTjga7oqK3lrpoKc2V0LnNlZWQoNDIpCgojIOabuOexjeOBruaVsApuX2Jvb2tzIDwtIDEwMAoKIyBB44GV44KT44Gu44Os44OT44Ol44O8CmFfc2NvcmVzIDwtIG5fYm9va3MgfD4gcm5vcm0oNjAsIDE1KSB8PiByb3VuZCgpIHw+IHBtaW4oMTAwKSB8PiBwbWF4KDApIAoKIyBC44GV44KT44Gu44Os44OT44Ol44O877yIQeOBleOCk+OBqOmrmOOBhOebuOmWou+8iQpiX3Njb3JlcyA8LSAoYV9zY29yZXMgKyAobl9ib29rcyB8PiBybm9ybSgwLCAxMCkgfD5yb3VuZCgpKSkgfD4gcG1pbigxMDApIHw+IHBtYXgoMCkKCiMgQ+OBleOCk+OBruODrOODk+ODpeODvO+8iEHjgZXjgpPjgajnt6njgYTpgIbnm7jplqLvvIkKY19zY29yZXMgPC0gKDEwMCAtIGFfc2NvcmVzICsgKG5fYm9va3MgfD4gcm5vcm0oMCwgMjApIHw+IHJvdW5kKCkpKSB8PiBwbWluKDEwMCkgfD4gcG1heCgwKQoKIyDnm7jplqLkv4LmlbDjga7oqIjnrpcKY29ycl9hYiA8LSBjb3IoYV9zY29yZXMsIGJfc2NvcmVzKQpjb3JyX2FjIDwtIGNvcihhX3Njb3JlcywgY19zY29yZXMpCgojIOe3muW9ouWbnuW4sOOBruaPj+eUuwpkZiA8LSBkYXRhLmZyYW1lKEE9YV9zY29yZXMsIEI9Yl9zY29yZXMsIEM9Y19zY29yZXMpCgpwMSA8LSBkZiB8PgogIGdncGxvdChhZXMoeCA9IEEsIHkgPSBCKSkgKwogIGdlb21fcG9pbnQoY29sb3IgPSAiYmx1ZSIpICsKICBnZW9tX3Ntb290aChmb3JtdWxhID0geSB+IHgsIG1ldGhvZCA9ICJsbSIsIGNvbG9yPSJibHVlIiwgZmlsbD0iYmx1ZSIpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoIkHjgZXjgpPjgahC44GV44KT44Gu6aGe5Ly85bqmIHIgPSIsIHJvdW5kKGNvcnJfYWIsIDIpKSwKICAgICAgIHggPSAiQeOBleOCk+OBq+OCiOOCi+ipleS+oSIsIHkgPSAiQuOBleOCk+OBq+OCiOOCi+ipleS+oSIpICsKICBjb29yZF9jYXJ0ZXNpYW4oeGxpbSA9IGMoMCwgMTAwKSwgeWxpbSA9IGMoMCwgMTAwKSkgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCgpwMiA8LSBkZiB8PgogIGdncGxvdChhZXMoeCA9IEEsIHkgPSBDKSkgKwogIGdlb21fcG9pbnQoY29sb3IgPSAicmVkIikgKwogIGdlb21fc21vb3RoKGZvcm11bGEgPSB5IH4geCwgbWV0aG9kID0gImxtIiwgY29sb3I9InJlZCIsIGZpbGw9InJlZCIpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoIkHjgZXjgpPjgahD44GV44KT44Gu6aGe5Ly85bqmIHIgPSIsIHJvdW5kKGNvcnJfYWMsIDIpKSwKICAgICAgIHggPSAiQeOBleOCk+OBq+OCiOOCi+ipleS+oSIsIHkgPSAiQ+OBleOCk+OBq+OCiOOCi+ipleS+oSIpICArCiAgY29vcmRfY2FydGVzaWFuKHhsaW0gPSBjKDAsIDEwMCksIHlsaW0gPSBjKDAsIDEwMCkpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQoKcDEgKyBwMgpgYGAKCgoKIyMjIDYuMy4yIOaZguezu+WIl+WQjOWjq+OBruebuOmWouOBp+mhnuS8vOW6puOCkua4rOOCiwoKYGBge3IgbWVzc2FnZT1GQUxTRSwgd2FybmluZz1GQUxTRX0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKCiMg44OH44O844K/44KS6Kqt44G/6L6844KACmRhdGFfZGYgPC0gcmVhZF90c3YoCiAgImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS90a0V6YWtpL2RhdGFfdmlzdWFsaXphdGlvbi9tYWluLzYlRTclQUIlQTAvZGF0YS9icmFpbi50eHQiCiAgKQoKZGF0YV9kZiB8PgogIG11dGF0ZSh0aW1lX3N0ZXBzID0gc2VxKDAsIChucm93KGRhdGFfZGYpIC0gMSkgKiAyLjUsIGJ5ID0gMi41KSkgfD4KICBwaXZvdF9sb25nZXIoIXRpbWVfc3RlcHMpIHw+CiAgZ2dwbG90KGFlcyh4ID0gdGltZV9zdGVwcywgeSA9IHZhbHVlLCBjb2xvciA9IG5hbWUpKSArCiAgZ2VvbV9wb2ludChzaXplID0gMC41KSArICAKICBnZW9tX2xpbmUoKSArCiAgbGFicyh4ID0gIuaZgumWkyBb56eSXSIsIHkgPSAi5rS75YuV6YePIiwgY29sb3IgPSAi6ISz6aCY5Z+fIikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEvNikKYGBgCgpgYGB7ciBtZXNzYWdlPUZBTFNFLCB3YXJuaW5nPUZBTFNFfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQoKZGF0YV9kZiA8LSByZWFkX3RzdigKICAiaHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL3RrRXpha2kvZGF0YV92aXN1YWxpemF0aW9uL21haW4vNiVFNyVBQiVBMC9kYXRhL2JyYWluLnR4dCIKICApCgojIHLlgKTjga7oqIjnrpcKcl92YWx1ZSA8LSBjb3IoZGF0YV9kZiRST0kxLCBkYXRhX2RmJFJPSTIpCgojIOaVo+W4g+Wbs+OBqOWbnuW4sOebtOe3muOAgeS/oemgvOWMuumWk+OCkuaPj+eUuwpkYXRhX2RmIHw+CiAgZ2dwbG90KGFlcyh4ID0gUk9JMSwgeSA9IFJPSTIpKSArCiAgZ2VvbV9wYXRoKGNvbG9yID0gImdyZXk0MCIpICsKICBnZW9tX3BvaW50KCkgKyAgCiAgZ2VvbV9zbW9vdGgoZm9ybXVsYSA9IHkgfiB4LCBtZXRob2QgPSAibG0iLCBjb2xvciA9ICJyZWQiLCBmaWxsID0gInJlZCIpICsKICBjb29yZF9jYXJ0ZXNpYW4oeGxpbSA9IGMoLTIuNSwgMi41KSwgeWxpbSA9IGMoLTIuNSwgMi41KSkgKwogIHRoZW1lX2J3KCkgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpICsgIAogIGFubm90YXRlKCJ0ZXh0IiwgeCA9IC0xLjUsIHkgPSAyLjUsIGxhYmVsID0gcGFzdGUoInIgPSIsIHJvdW5kKHJfdmFsdWUsIDIpKSwgc2l6ZSA9IDgpICsKICBsYWJzKHggPSAi6ISz6aCY5Z+fMSIsIHkgPSAi6ISz6aCY5Z+fMiIpCmBgYAoKCgoKCiMjIyA2LjMuMyDjgrXjg7Pjg5fjg6rjg7PjgrDjgZXjgozjgZ/nm7jplqLkv4LmlbDjgajjg5XjgqPjg4Pjgrfjg6Pjg7zlpInmj5sKCmBgYHtyfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHBhdGNod29yaykKbGlicmFyeShNQVNTKQoKZ2VuZXJhdGVfY29ycmVsYXRpb24gPC0gZnVuY3Rpb24odGFyZ2V0X2NvcnI9MC44LCBzaXplPTEwMCwgaXRlciA9IDEwMDAwMCkgewogIGdyb3VwIDwtIHJlcCgxOml0ZXIsIGVhY2ggPSBzaXplKQogIHNhbXBsZXMgPC0gc3BsaXQoCiAgICBtdnJub3JtKG4gPSBzaXplICogaXRlciwgbXUgPSBjKDAsIDApLCBTaWdtYSA9IG1hdHJpeChjKDEsIHRhcmdldF9jb3JyLCB0YXJnZXRfY29yciwgMSksIG5yb3c9MikpLAogICAgZ3JvdXApCiAgY29ycmVsYXRpb24gPC0gbWFwX2RibChzYW1wbGVzLCBcKHgpIHsKICAgIG1hdCA8LSBtYXRyaXgoeCwgMTAwKQogICAgY29yKG1hdFssMV0sIG1hdFssMl0pCiAgICB9KQogIGZpc2hlcl96IDwtIDAuNSAqIGxvZygoMSArIGNvcnJlbGF0aW9uKSAvICgxIC0gY29ycmVsYXRpb24pKQogIHJldHVybihkYXRhLmZyYW1lKGNvcnJlbGF0aW9uLGZpc2hlcl96KSkKICB9CgpyZXN1bHRzIDwtIGdlbmVyYXRlX2NvcnJlbGF0aW9uKCkKCiMg44OS44K544OI44Kw44Op44Og44KS5o+P55S7CmJpbnNfb3JpZyA8LSBzZXEoMC42LCAxLjAsIGxlbmd0aC5vdXQgPSA0MSkKYmluc196IDwtIHNlcSgwLjYsIDEuNSwgbGVuZ3RoLm91dCA9IDQxKQoKIyDmraPopo/liIbluIPjga7jg6njgqTjg7PjgpLlvJXjgY8KcDEgPC0gcmVzdWx0cyB8PgogIGdncGxvdChhZXMoeD1jb3JyZWxhdGlvbikpICsKICBnZW9tX2hpc3RvZ3JhbShhZXMoeT1hZnRlcl9zdGF0KGRlbnNpdHkpKSwgYmlucz1sZW5ndGgoYmluc19vcmlnKS0xLCBmaWxsPSJibHVlIiwgYWxwaGE9MC42KSArCiAgc3RhdF9mdW5jdGlvbihmdW4gPSBkbm9ybSwKICAgICAgICAgICAgICAgIGFyZ3MgPSBsaXN0KG1lYW4gPSBtZWFuKHJlc3VsdHMkY29ycmVsYXRpb24pLCBzZCA9IHNkKHJlc3VsdHMkY29ycmVsYXRpb24pKSwKICAgICAgICAgICAgICAgIGNvbG9yPSJkYXJrYmx1ZSIsIGxpbmV0eXBlPSJkYXNoZWQiKSArCiAgbGFicyh0aXRsZT0i44K144Oz44OX44Oq44Oz44Kw44GV44KM44Gf55u46Zai5L+C5pWwIiwgeD1leHByZXNzaW9uKGl0YWxpYyhyKSkpICsKICB0aGVtZShheGlzLnRpdGxlLnkgPSBlbGVtZW50X2JsYW5rKCkpCiAgCgpwMiA8LSByZXN1bHRzIHw+CiAgZ2dwbG90KGFlcyh4PWZpc2hlcl96KSkgKwogIGdlb21faGlzdG9ncmFtKGFlcyh5PWFmdGVyX3N0YXQoZGVuc2l0eSkpLCBiaW5zPWxlbmd0aChiaW5zX3opLTEsIGZpbGw9InJlZCIsIGFscGhhPTAuNikgKwogIHN0YXRfZnVuY3Rpb24oZnVuID0gZG5vcm0sCiAgICAgICAgICAgICAgICBhcmdzID0gbGlzdChtZWFuID0gbWVhbihyZXN1bHRzJGZpc2hlcl96KSwgc2QgPSBzZChyZXN1bHRzJGZpc2hlcl96KSksCiAgICAgICAgICAgICAgICBjb2xvcj0iZGFya3JlZCIsIGxpbmV0eXBlPSJkYXNoZWQiKSArCiAgbGFicyh0aXRsZT0i44OV44Kj44OD44K344Oj44O85aSJ5o+b5b6M44Gu55u46Zai5L+C5pWwIiwgeD1leHByZXNzaW9uKGl0YWxpYyh6KSkpICsKICB0aGVtZShheGlzLnRpdGxlLnkgPSBlbGVtZW50X2JsYW5rKCkpCgpwMSArIHAyCmBgYAoKCiMjIyA2LjMuNCDku5bjga7lpInmlbDjga7lvbHpn7/jgpLogIPmha7jgZfjgabnm7jplqLjgpLjgajjgonjgYjjgosKCmBgYHtyfQpsaWJyYXJ5KGNvbmZsaWN0ZWQpCmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KHBhdGNod29yaykKCiMgU2VhYm9ybuOBrnRpcHPjg4fjg7zjgr/jgrvjg4Pjg4jjgpLkvb/nlKgKZGYgPC0gcmVhZC5jc3YoImh0dHBzOi8vcmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbS9td2Fza29tL3NlYWJvcm4tZGF0YS9tYXN0ZXIvdGlwcy5jc3YiKQoKIyDnm7jplqLkv4LmlbDjga7oqIjnrpcKY29ycl90b3RhbF90aXAgPC0gY29yKGRmJHRvdGFsX2JpbGwsIGRmJHRpcCkKY29ycl90b3RhbF9zaXplIDwtIGNvcihkZiR0b3RhbF9iaWxsLCBkZiRzaXplKQpjb3JyX3RpcF9zaXplIDwtIGNvcihkZiR0aXAsIGRmJHNpemUpCgojIOaVo+W4g+Wbs+OBqOWbnuW4sOebtOe3muOCkuaPj+eUu+OBmeOCiwpwMSA8LSBkZiB8PgogIGdncGxvdChhZXMoeD1zaXplLCB5PXRpcCkpICsKICBnZW9tX3BvaW50KGFscGhhPTAuNCwgY29sb3I9ImRhcmtncmVlbiIpICsKICBnZW9tX3Ntb290aChmb3JtdWxhID0geSB+IHgsIG1ldGhvZD0ibG0iLCBjb2xvcj0iZGFya2dyZWVuIiwgZmlsbCA9ImRhcmtncmVlbiIpICsKICBsYWJzKHRpdGxlPXBhc3RlKCLjgrDjg6vjg7zjg5fjga7kurrmlbDjgajjg4Hjg4Pjg5fjga7poY1cbiByID0gIiwgcm91bmQoY29ycl90aXBfc2l6ZSwgMikpLAogICAgICAgeCA9ICLjgrDjg6vjg7zjg5fjga7kurrmlbAiLCB5ID0gIuODgeODg+ODl+OBrumhjSBbJF0iKSArCiAgdGhlbWUoYXNwZWN0LnJhdGlvID0gMSkKCnAyIDwtIGRmIHw+CiAgZ2dwbG90KGFlcyh4PXRvdGFsX2JpbGwsIHk9dGlwKSkgKwogIGdlb21fcG9pbnQoYWxwaGE9MC40LCBjb2xvcj0iZGFya2JsdWUiKSArCiAgZ2VvbV9zbW9vdGgoZm9ybXVsYSA9IHkgfiB4LCBtZXRob2Q9ImxtIiwgY29sb3I9ImRhcmtibHVlIiwgZmlsbD0iZGFya2JsdWUiKSArCiAgbGFicyh0aXRsZT1wYXN0ZSgi5Lya6KiI6aGN44Go44OB44OD44OX44Gu6aGNXG4gciA9ICIsIHJvdW5kKGNvcnJfdG90YWxfdGlwLCAyKSksCiAgICAgICB4ID0gIuS8muioiOmhjSBbJF0iLCB5ID0i44OB44OD44OX44Gu6aGNIFskXSIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQoKcDMgPC0gZ2dwbG90KGRmLCBhZXMoeD1zaXplLCB5PXRvdGFsX2JpbGwpKSArCiAgZ2VvbV9wb2ludChhbHBoYT0wLjQsIGNvbG9yPSJkYXJrcmVkIikgKwogIGdlb21fc21vb3RoKGZvcm11bGEgPSB5IH4geCwgbWV0aG9kPSJsbSIsIGNvbG9yPSJkYXJrcmVkIiwgZmlsbD0iZGFya3JlZCIpICsKICBsYWJzKHRpdGxlPXBhc3RlKCLjgrDjg6vjg7zjg5fjga7kurrmlbDjgajkvJroqIjpoY1cbiByID0gIiwgcm91bmQoY29ycl90b3RhbF9zaXplLCAyKSksCiAgICAgICB4ID0gIuOCsOODq+ODvOODl+OBruS6uuaVsCIsIHkgPSLkvJroqIjpoY0gWyRdIikgKwogIHRoZW1lKGFzcGVjdC5yYXRpbyA9IDEpCgpwMSArIHAyICsgcDMKYGBgCgojIyMgNi4zLjYg5LqI5ris44Oi44OH44Or44Gu6Kqk5beuCgpgYGB7cn0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShwYWxtZXJwZW5ndWlucykKbGlicmFyeShyc2FtcGxlKQoKZGF0YSgicGVuZ3VpbnMiKQoKIyDliY3lh6bnkIYKcGVuZ3VpbnNfY2xlYW4gPC0gcGVuZ3VpbnMgfD4KICBkcGx5cjo6c2VsZWN0KHNwZWNpZXMsIGJvZHlfbWFzc19nLCBiaWxsX2xlbmd0aF9tbSwgYmlsbF9kZXB0aF9tbSwgZmxpcHBlcl9sZW5ndGhfbW0pIHw+CiAgZHJvcF9uYSgpCiAgCiMg44OH44O844K/5YiG5YmyCnBlbmd1aW5zX3NwbGl0IDwtIHBlbmd1aW5zX2NsZWFuIHw+CiAgaW5pdGlhbF9zcGxpdChwcm9wID0gMC44LCBzdHJhdGEgPSBib2R5X21hc3NfZykKCnBlbmd1aW5zX3RyYWluIDwtIHRyYWluaW5nKHBlbmd1aW5zX3NwbGl0KQpwZW5ndWluc190ZXN0IDwtIHRlc3RpbmcocGVuZ3VpbnNfc3BsaXQpCgpmaXQgPC0gbG0oYm9keV9tYXNzX2cgfiBiaWxsX2xlbmd0aF9tbSArIGJpbGxfZGVwdGhfbW0gKyBmbGlwcGVyX2xlbmd0aF9tbSwgZGF0YSA9IHBlbmd1aW5zX3RyYWluKQoKZGZfd2lkZSA8LSBwZW5ndWluc190ZXN0IHw+CiAgZHBseXI6OnNlbGVjdChzcGVjaWVzLCBib2R5X21hc3NfZykgfD4KICBtdXRhdGUocHJlZCA9IHByZWRpY3QoZml0LCBuZXdkYXRhID0gcGVuZ3VpbnNfdGVzdCkpIHw+CiAgYXJyYW5nZShzcGVjaWVzKSB8PgogIG11dGF0ZShpZCA9IHJvd19udW1iZXIoKSkKCmRmX2xvbmcgPC0gZGZfd2lkZSB8PgogIHBpdm90X2xvbmdlcighYyhzcGVjaWVzLCBpZCkpIHw+CiAgbXV0YXRlKHR5cGUgPSBjYXNlX3doZW4oCiAgICBuYW1lID09ICJwcmVkIiB+ICLkuojmuKzlgKQiLAogICAgbmFtZSA9PSAiYm9keV9tYXNzX2ciIH4gc3BlY2llcwogICkpCgpkZl9sb25nIHw+CiAgZ2dwbG90KGFlcyh4ID0gaWQsIHkgPSB2YWx1ZSwgY29sb3IgPSB0eXBlKSkgKwogIGdlb21fc2VnbWVudChkYXRhID0gZGZfd2lkZSwgYWVzKHggPSBpZCwgeSA9IGJvZHlfbWFzc19nLCB4ZW5kID0gaWQsIHllbmQgPSBwcmVkKSwgY29sb3IgPSAiYmxhY2siLCBsaW5ldHlwZSA9ICJkYXNoZWQiKSArCiAgZ2VvbV9wb2ludCgpICsKICBzY2FsZV9jb2xvcl9tYW51YWwodmFsdWVzID0gYygicm95YWxibHVlIiwgInNhbG1vbiIsICJmb3Jlc3RncmVlbiIsICJibGFjayIpKSArCiAgbGFicyh0aXRsZSA9ICLlgIvkvZPjgZTjgajjga7nnJ/jga7kvZPph43jgajkuojmuKzjgZXjgozjgZ/kvZPph40iLCB4ID0gIuWAi+S9k+eVquWPtyIsIHkgPSAi5L2T6YeNIFtnXSIpICsKICB0aGVtZShsZWdlbmQudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksIGxlZ2VuZC5wb3NpdGlvbiA9IGMoMC45LCAwLjIpKQoKYGBgCgojIyA2LjQg44CM44Gk44Gq44GM44KK44CN44KS44Go44KJ44GI44KLCgojIyMgNi40LjEg44K144Kk44Kz44Ot44Gu5ZCM5pmC56K6546H44Go5p2h5Lu25LuY44GN56K6546HCgpgYGB7cn0KbGlicmFyeShjb25mbGljdGVkKQpsaWJyYXJ5KHRpZHl2ZXJzZSkKbGlicmFyeShwYXRjaHdvcmspCmxpYnJhcnkodmlyaWRpcykKCiMg56K6546H5YiG5biD44KS5rqW5YKZCmpvaW50X3Byb2IgPC0gbWF0cml4KGMoCiAgMSAvIDM2IC0gMSAvIDcyLCAgICAgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwKICAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgKyAxIC8gNzIgLyA1LAogIDEgLyAzNiArIDEgLyA3MiAvIDUsIDEgLyAzNiAtIDEgLyA3MiwgICAgIDEgLyAzNiArIDEgLyA3MiAvIDUsCiAgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwKICAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgLSAxIC8gNzIsCiAgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwKICAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgKyAxIC8gNzIgLyA1LAogIDEgLyAzNiAtIDEgLyA3MiwgICAgIDEgLyAzNiArIDEgLyA3MiAvIDUsIDEgLyAzNiArIDEgLyA3MiAvIDUsCiAgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwKICAxIC8gMzYgKyAxIC8gNzIgLyA1LCAxIC8gMzYgLSAxIC8gNzIsICAgICAxIC8gMzYgKyAxIC8gNzIgLyA1LAogIDEgLyAzNiArIDEgLyA3MiAvIDUsIDEgLyAzNiArIDEgLyA3MiAvIDUsIDEgLyAzNiArIDEgLyA3MiAvIDUsCiAgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2ICsgMSAvIDcyIC8gNSwgMSAvIDM2IC0gMSAvIDcyCiAgKSwgbnJvdyA9IDYsIGJ5cm93ID0gVFJVRSkKCmpvaW50X3Byb2IgPC0gam9pbnRfcHJvYiAvIHN1bShqb2ludF9wcm9iKQoKIyDjgrXjg7Pjg5fjg6vjgpJqb2ludF9wcm9i44Gr5b6T44Gj44GmMTAwMOWbnuOCteODs+ODl+ODquODs+OCsApzZXQuc2VlZCgwKQpsaWJyYXJ5KHRpY3RvYykKc2FtcGxlcyA8LSBzYW1wbGUuaW50KDM2LCBzaXplID0gMTAwMDAwMCwgcmVwbGFjZSA9IFRSVUUsIHByb2IgPSBjKGpvaW50X3Byb2IpKQoKIyDjgrXjg7Pjg5fjg6rjg7PjgrDjgZXjgozjgZ/lgKTjgpIoWCwgWSnjg5rjgqLjgavlpInmj5sKc2FtcGxlc19kaWUxIDwtIChzYW1wbGVzIC0gMSkgJS8lIDYgKyAxCnNhbXBsZXNfZGllMiA8LSAoc2FtcGxlcyAtIDEpICUlIDYgKyAxCgojIOODkuODvOODiOODnuODg+ODlwpwMSA8LSBkYXRhLmZyYW1lKAogIHNhbXBsZXNfZGllMSA9IGZhY3Rvcigoc2FtcGxlcyAtIDEpICUvJSA2ICsgMSksCiAgc2FtcGxlc19kaWUyID0gZmFjdG9yKChzYW1wbGVzIC0gMSkgJSUgNiArIDEpCikgfD4KICBzdW1tYXJpc2UobiA9IG4oKSwgLmJ5ID0gYyhzYW1wbGVzX2RpZTEsIHNhbXBsZXNfZGllMikpIHw+CiAgbXV0YXRlKHByb2IgPSBuIC8gMTAwMDAwMCkgfD4KICBnZ3Bsb3QoYWVzKHggPSBzYW1wbGVzX2RpZTEsIHkgPSBzYW1wbGVzX2RpZTIsIGZpbGwgPSBwcm9iLCBsYWJlbCA9IGZvcm1hdChyb3VuZChwcm9iLCAzKSksIG5zbWFsbCA9IDMpKSArCiAgZ2VvbV90aWxlKCkgKwogIGdlb21fdGV4dChjb2xvciA9ICJ3aGl0ZSIsIHNpemUgPSAzKSArCiAgc2NhbGVfZmlsbF9ncmFkaWVudChsb3cgPSAiZGFya2JsdWUiLCBoaWdoID0gImRhcmtyZWQiKSArCiAgdGhlbWVfbWluaW1hbCgpICsKICB0aGVtZShsZWdlbmQudGl0bGUgPSBlbGVtZW50X2JsYW5rKCksCiAgICAgICAgYXNwZWN0LnJhdGlvID0gMSkgKwogIGxhYnMoeCA9ICLjgrXjgqTjgrPjg61B44Gu5Ye655uuIiwgeSA9ICLjgrXjgqTjgrPjg61C44Gu5Ye655uuIikKCiMg44K144Kk44Kz44OtQeOBjDHjgYzlh7rjgZ/jgajjgY3jga7jgrXjgqTjgrPjg61C44Gu57WQ5p6c44KS5qOS44Kw44Op44OV44Gn5o+P55S7CnNhbXBsZXNfZGllMl93aGVuX2RpZTFfaXNfMSA8LSBzYW1wbGVzX2RpZTJbc2FtcGxlc19kaWUxID09IDFdCgpwMiA8LSBkYXRhLmZyYW1lKHRhYmxlKHNhbXBsZXNfZGllMl93aGVuX2RpZTFfaXNfMSkgLyBsZW5ndGgoc2FtcGxlc19kaWUyX3doZW5fZGllMV9pc18xKSkgfD4KICBnZ3Bsb3QoYWVzKHkgPSBGcmVxLCB4ID0gc2FtcGxlc19kaWUyX3doZW5fZGllMV9pc18xKSkgKwogIGdlb21fY29sKGZpbGwgPSAicm95YWxibHVlIiwgY29sb3IgPSAiYmxhY2siKSArCiAgbGFicyh4ID0gIuOCteOCpOOCs+ODrULjga7lh7rnm64iLCB5ID0gIuebuOWvvumgu+W6piIpICsKICB0aGVtZShhc3BlY3QucmF0aW8gPSAxKQoKcDEgKyBwMgpgYGAKCgoKIyMjIDYuNC4zIOWQhOippuihjOOBp+OBruWHuuebruOBrueZuueUn+eiuueOhwoKYGBge3J9CmxpYnJhcnkoY29uZmxpY3RlZCkKbGlicmFyeSh0aWR5dmVyc2UpCmxpYnJhcnkocGF0Y2h3b3JrKQoKIyDjgrXjgqTjgrPjg63jga7lrp/pqJPjgpLjgrfjg5/jg6Xjg6zjg7zjgrfjg6fjg7PjgZnjgovplqLmlbAKc2ltdWxhdGVfZGljZV9leHBlcmltZW50IDwtIGZ1bmN0aW9uKG5fdHJpYWxzKSB7CiAgIyDjg5zjg7zjg4rjgrnjgr/jgqTjg6DjgajpgJrluLjmmYLjga7norrnjocKICBib251c19wcm9iIDwtICBjKDEgLyAxMSwgMiAvIDExLCAyIC8gMTEsIDIgLyAxMSwgMiAvIDExLCAyIC8gMTEpCiAgbm9ybWFsX3Byb2IgPC0gYygyIC8gMTEsIDkgLyA1NSwgOSAvIDU1LCA5IC8gNTUsIDkgLyA1NSwgOSAvIDU1KQogIAogIHNldC5zZWVkKDUpCiAgZGllMSA8LSBzYW1wbGUuaW50KDYsIHNpemUgPSBuX3RyaWFscywgcHJvYiA9IG5vcm1hbF9wcm9iLCByZXBsYWNlID0gVFJVRSkgICMg6YCa5bi45pmC44Gu44K144Kk44Kz44OtQeOBruWHuuebrgogIHNldC5zZWVkKDEpICAKICBkaWUyIDwtIHNhbXBsZS5pbnQoNiwgc2l6ZSA9IG5fdHJpYWxzLCBwcm9iID0gbm9ybWFsX3Byb2IsIHJlcGxhY2UgPSBUUlVFKSAgIyDpgJrluLjmmYLjga7jgrXjgqTjgrPjg61C44Gu5Ye655uuCiAgc2V0LnNlZWQoMikgIAogIGJvbnVzX3RpbWVfZGllMSA8LSBzYW1wbGUuaW50KDYsIHNpemUgPSBuX3RyaWFscywgcHJvYiA9IGJvbnVzX3Byb2IsIHJlcGxhY2UgPSBUUlVFKSAgIyDjg5zjg7zjg4rjgrnjgr/jgqTjg6DmmYLjga7jgrXjgqTjgrPjg61B44Gu5Ye655uuCiAgc2V0LnNlZWQoMykKICBib251c190aW1lX2RpZTIgPC0gc2FtcGxlLmludCg2LCBzaXplID0gbl90cmlhbHMsIHByb2IgPSBib251c19wcm9iLCByZXBsYWNlID0gVFJVRSkgICMg44Oc44O844OK44K544K/44Kk44Og5pmC44Gu44K144Kk44Kz44OtQuOBruWHuuebriAgCiAgCiAgZGllMV9sYWcgPC0gZHBseXI6OmxhZyhkaWUxKQogIAogIGRpZXMgPC0gZGF0YS5mcmFtZSgKICAgICAgZGllMSwgZGllMiwgZGllMV9sYWcsIGJvbnVzX3RpbWVfZGllMSwgYm9udXNfdGltZV9kaWUyLAogICAgICBzYW1wbGVzX2RpZTEgPSBpZl9lbHNlKGRpZTFfbGFnICE9IDEgfCBpcy5uYShkaWUxX2xhZyksIGRpZTEsIGJvbnVzX3RpbWVfZGllMSksCiAgICAgIHNhbXBsZXNfZGllMiA9IGlmX2Vsc2UoZGllMV9sYWcgIT0gMSB8IGlzLm5hKGRpZTFfbGFnKSwgZGllMiwgYm9udXNfdGltZV9kaWUyKQogICAgICApCiAgCiAgcHJvYiA8LSBkaWVzIHw+CiAgICBzdW1tYXJpc2UobiA9IG4oKSwgLmJ5ID0gYyhzYW1wbGVzX2RpZTEsIHNhbXBsZXNfZGllMikpIHw+CiAgICBtdXRhdGUoCiAgICAgIHNhbXBsZXNfZGllMSA9IGZhY3RvcihzYW1wbGVzX2RpZTEpLCAKICAgICAgc2FtcGxlc19kaWUyID0gZmFjdG9yKHNhbXBsZXNfZGllMiksCiAgICAgIHByb2IgPSBuIC8gbl90cmlhbHMsIC5rZWVwID0gInVudXNlZCIKICAgICAgKQogIAogIHJldHVybihsaXN0KGRpZXMgPSBkaWVzLCBwcm9iID0gcHJvYikpCiAgfQoKcmVzdWx0IDwtIHNpbXVsYXRlX2RpY2VfZXhwZXJpbWVudCgxMDAwMDApCgojIOODkuODvOODiOODnuODg+ODlwpwMSA8LSByZXN1bHQkcHJvYiB8PgogIGdncGxvdChhZXMoeCA9IHNhbXBsZXNfZGllMSwgeSA9IHNhbXBsZXNfZGllMiwgZmlsbCA9IHByb2IsIGxhYmVsID0gZm9ybWF0KHJvdW5kKHByb2IsIDMpKSwgbnNtYWxsID0gMykpICsKICBnZW9tX3RpbGUoKSArCiAgZ2VvbV90ZXh0KGNvbG9yID0gIndoaXRlIiwgc2l6ZSA9IDMpICsKICBzY2FsZV9maWxsX2dyYWRpZW50KGxvdyA9ICJkYXJrYmx1ZSIsIGhpZ2ggPSAiZGFya3JlZCIpICsKICB0aGVtZV9taW5pbWFsKCkgKwogIGxhYnMoeSA9ICLjgrXjgqTjgrPjg61B44Gu5Ye655uuIiwgeCA9ICLjgrXjgqTjgrPjg61C44Gu5Ye655uuIikrCiAgdGhlbWUobGVnZW5kLnRpdGxlID0gZWxlbWVudF9ibGFuaygpLCBhc3BlY3QucmF0aW8gPSAxKQogIAojIOOCteOCpOOCs+ODrUHjgYwx44GM5Ye644Gf44Go44GN44Gu44K144Kk44Kz44OtQuOBrue1kOaenOOCkuajkuOCsOODqeODleOBp+aPj+eUu+OBmeOCi+mWouaVsApwMiA8LSByZXN1bHQkZGllcyB8PgogIGRwbHlyOjpmaWx0ZXIoZGllMSA9PSAxKSB8PgogIHN1bW1hcmlzZShuID0gbigpLCAuYnkgPSBzYW1wbGVzX2RpZTIpIHw+CiAgbXV0YXRlKHByb2IgPSBuIC8gc3VtKG4pKSB8PgogIGdncGxvdChhZXMoeCA9IHNhbXBsZXNfZGllMiwgeSA9IHByb2IpKSArCiAgZ2VvbV9jb2woZmlsbCA9ICJyb3lhbGJsdWUiLCBjb2xvciA9ICJibGFjayIpICsKICBsYWJzKHggPSAi44K144Kk44Kz44OtQuOBruWHuuebriIsIHkgPSAi55u45a++6aC75bqmIikKCnAxICsgcDIKYGBgCgojIyMgNi40LjQg44K144Kk44Kz44Ot5Ye655uu44Gu5pmC6ZaT55qE44Gq6Zai5L+CCgpgYGB7ciBmaWcuaGVpZ2h0PTcuNSwgZmlnLndpZHRoPTcuNX0KCmJvbnVzX3JlY3QgPC0gcmVzdWx0JGRpZXMgfD4KICBzbGljZV9oZWFkKG4gPSA1MCkgfD4KICBtdXRhdGUodHJpYWwgPSAxOjUwKSB8PgogIGRwbHlyOjpmaWx0ZXIoZGllMV9sYWcgPT0gMSkgfD4KICBkcGx5cjo6c2VsZWN0KHRyaWFsKSB8PgogIG11dGF0ZSh4bWluID0gdHJpYWwgLSAwLjUsIHhtYXggPSB0cmlhbCArIDAuNSkKCmRmIDwtIGRhdGEuZnJhbWUoCiAgdHJpYWwgPSAxOjUwLAogIGRpZTEgPSByZXN1bHQkZGllcyRzYW1wbGVzX2RpZTFbMTo1MF0sCiAgZGllMiA9IHJlc3VsdCRkaWVzJHNhbXBsZXNfZGllMlsxOjUwXQogICkgfD4KICBwaXZvdF9sb25nZXIoIXRyaWFsKQoKcDMgPC0gZ2dwbG90KCkgKwogIGdlb21fcmVjdChkYXRhID0gYm9udXNfcmVjdCwgYWVzKHhtaW49eG1pbiwgeG1heD14bWF4LCB5bWluPTEsIHltYXg9NiksIGZpbGw9InJveWFsYmx1ZSIsIGFscGhhID0gMC41KSArCiAgZ2VvbV9saW5lKGRhdGEgPSBkZiwgYWVzKHggPSB0cmlhbCwgeSA9IHZhbHVlLCBjb2xvciA9IG5hbWUpKSArCiAgZ2VvbV9wb2ludChkYXRhID0gZGYsIGFlcyh4ID0gdHJpYWwsIHkgPSB2YWx1ZSwgY29sb3IgPSBuYW1lKSkgKwogIGxhYnMoeCA9ICLoqabooYzlm57mlbAiLCB5ID0gIuOCteOCpOOCs+ODreOBruWHuuebriIsIGNvbG9yID0gIvCfjrIiKSArCiAgdGhlbWUobGVnZW5kLnRpdGxlID0gZWxlbWVudF9ibGFuaygpKSArCiAgdGhlbWVfYncoKQoKcDQgPC0gcmVzdWx0JGRpZXMgfD4KICBkcGx5cjo6ZmlsdGVyKGRpZTFfbGFnID09IDEpIHw+CiAgc3VtbWFyaXNlKG4gPSBuKCksIC5ieSA9IHNhbXBsZXNfZGllMSkgfD4KICBtdXRhdGUocHJvYiA9IG4gLyBzdW0obikpIHw+CiAgZ2dwbG90KGFlcyh4ID0gc2FtcGxlc19kaWUxLCB5ID0gcHJvYikpICsKICBnZW9tX2NvbChmaWxsID0gInJveWFsYmx1ZSIsIGNvbG9yID0gImJsYWNrIikgKwogIGxhYnMoeCA9ICLjgrXjgqTjgrPjg61B44Gu5Ye655uuIiwgeSA9ICLnm7jlr77poLvluqYiKQoKcDUgPC0gcmVzdWx0JGRpZXMgfD4KICBkcGx5cjo6ZmlsdGVyKGRpZTFfbGFnID09IDEpIHw+CiAgc3VtbWFyaXNlKG4gPSBuKCksIC5ieSA9IHNhbXBsZXNfZGllMikgfD4KICBtdXRhdGUocHJvYiA9IG4gLyBzdW0obikpIHw+CiAgZ2dwbG90KGFlcyh4ID0gc2FtcGxlc19kaWUyLCB5ID0gcHJvYikpICsKICBnZW9tX2NvbChmaWxsID0gInNhbG1vbiIsIGNvbG9yID0gImJsYWNrIikgKwogIGxhYnMoeCA9ICLjgrXjgqTjgrPjg61C44Gu5Ye655uuIiwgeSA9ICLnm7jlr77poLvluqYiKQoKcDMgLyAocDQgKyBwNSkKYGBgCgrnrKw256ug44Gv44GT44GT44G+44Gn44CCCg==