Are these two groups different? We compare two samples in terms of statistical parameters such as mean, variance, etc.

t-test: mean comparison.

\(\{x_1, x_2, x_3, x_4, \dots, x_{n_1} \}\) is from \(N(\mu_1, \sigma_1^2)\) and

\(\{y_1, y_2, y_3, y_4, \dots, y_{n_2} \}\) is from \(N(\mu_2, \sigma_2^2)\)

x <- c(5.12, 5.28, 4.98, 4.62, 4.95, 4.35, 4.83, 6.15, 5.83, 5.43)
y <- c(5.37, 5.63, 5.89, 5.92, 5.91, 6.15, 6.29, 6.41, 6.88, 7.12)

qqnorm(x);

qqnorm(y);


ttest.res <- t.test(x,y)
ttest.res$p.value
[1] 0.0006073053

\(t-score = \frac{\bar{x}-\bar{y}}{ \sqrt{ s^2_x/n_1+s^2_y/n_2 } }\)

distribution is \(t_{(\nu)}\)

\(\nu = \frac{(s^2_x/n_1+s^2_y/n_2)^2}{(s^2_x/n_1)^2/(n_1-1)+(s^2_y/n_2)^2/(n_2-1)}\)









Linear regression

\(\hat{y}=\beta_0 + \beta_1 x\)

\(\{x_1, x_2, x_3, x_4, \dots, x_{n_1} \}\) is from \(N(\beta_0+\beta_1\cdot 0, \sigma^2)\) and

\(\{y_1, y_2, y_3, \dots, y_{n_2} \}\) is from \(N(\beta_0+\beta_1\cdot 1, \sigma^2)\)

Since the estimator’s of \(\beta_0\) and \(\beta_1\) are calculated by using \(x_i\) and \(y_j\), we also have probability distributions for the estimators of \(\beta_0\) and \(\beta_1\). \(\beta_1\) estimator’s distribution is another \(t\)-distribution. Using this we can test

\(H_0:\beta_1=0\)

If rejected, \(i.e.\), \(P-\)value is low enough, we can say that means are different.

library(ggplot2)
rm(data_4_lin_reg)
object 'data_4_lin_reg' not found
data_4_lin_reg <- data.frame(name = rep("x", length(x)), values = x)
data_4_lin_reg <- rbind(data_4_lin_reg, data.frame(name = rep("y", length(y)), values = y))
ggplot(data = data_4_lin_reg, aes(x=name, y=values))+geom_boxplot()




# lin_reg2 <- glm(data = data_4_lin_reg, values ~ name, family=gaussian)
# summary(lin_reg2)
var.test(x, y, alternative = "two.sided")

    F test to compare two variances

data:  x and y
F = 1.0127, num df = 9, denom df = 9, p-value = 0.9853
alternative hypothesis: true ratio of variances is not equal to 1
95 percent confidence interval:
 0.2515393 4.0771072
sample estimates:
ratio of variances 
          1.012696 
lin_reg <- lm(data = data_4_lin_reg, values ~ name)
coef(summary(lin_reg))[2,4]
[1] 0.0006072601
y_1=1.4*y-2.0
var.test(x, y_1, alternative = "two.sided")

    F test to compare two variances

data:  x and y_1
F = 0.51668, num df = 9, denom df = 9, p-value = 0.3395
alternative hypothesis: true ratio of variances is not equal to 1
95 percent confidence interval:
 0.1283364 2.0801567
sample estimates:
ratio of variances 
         0.5166815 
ttest.res <- t.test(x,y_1)
ttest.res$p.value
[1] 0.0001267858

rm(data_4_lin_reg)
data_4_lin_reg <- data.frame(name = rep("x", length(x)), values = x)
data_4_lin_reg <- rbind(data_4_lin_reg, data.frame(name = rep("y", length(y_1)), values = y_1))
#data_4_lin_reg

ggplot(data = data_4_lin_reg, aes(x=name, y=values))+geom_boxplot()

lin_reg <- lm(data = data_4_lin_reg, values ~ name)
coef(summary(lin_reg))[2,4]
[1] 9.585896e-05









General linear regressions

1. Linear regression.

\(Y|_{x} \sim N(\beta_0 + \beta_1 x,\sigma)\)

\(E(Y|_{x})=\beta_0 +\beta_1 x\)

Probability distribution, \(f(y|x;(\beta_0, \beta_1 ))=n(\beta_0 + \beta_1 x,\sigma)\)


ind.var <- seq(1, 10, by=1)
dep.var <- ind.var + rnorm(10, 0, 1.5)
linreg.res <- lm(data = data.frame(x=ind.var, y= dep.var), y ~ x)
coef(summary(linreg.res))
              Estimate Std. Error    t value     Pr(>|t|)
(Intercept) -0.2844622  1.0760642 -0.2643543 0.7981897442
x            0.9472229  0.1734235  5.4619079 0.0006001724
interc = coef(summary(linreg.res))[1,1]; slope = coef(summary(linreg.res))[2,1]

ggplot(data = data.frame(x=ind.var, y= dep.var))+geom_point(aes(x=ind.var, y=dep.var)) + 
  geom_line(aes(x=ind.var, y=interc + slope*ind.var   )) +
  geom_line(data = data.frame(x=dnorm(seq(-3.5,0,by=0.01), 0, 1.5)+3, 
                              y=seq(-3.5,0,by=0.01)+interc + slope*3), aes(x=x, y= y  )) + 
  geom_line(data = data.frame(x=dnorm(seq(0,3.5,by=0.01), 0, 1.5)+3,
                              y=seq(0,3.5,by=0.01)+interc + slope*3), aes(x=x, y= y  )) +
  geom_line(data = data.frame(x=dnorm(seq(-3.5,0,by=0.01), 0, 1.5)+5, 
                              y=seq(-3.5,0,by=0.01)+interc + slope*5), aes(x=x, y= y  )) + 
  geom_line(data = data.frame(x=dnorm(seq(0,3.5,by=0.01), 0, 1.5)+5, 
                              y=seq(0,3.5,by=0.01)+interc + slope*5), aes(x=x, y= y  )) +
  geom_line(data = data.frame(x=dnorm(seq(-3.5,0,by=0.01), 0, 1.5)+7, 
                              y=seq(-3.5,0,by=0.01)+interc + slope*7), aes(x=x, y= y  )) + 
  geom_line(data = data.frame(x=dnorm(seq(0,3.5,by=0.01), 0, 1.5)+7, 
                              y=seq(0,3.5,by=0.01)+interc + slope*7), aes(x=x, y= y  ))

NA
NA

How to find \(\beta_0\) and \(\beta_1\).

Data \(\{(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4), (x_5, y_5)\}\)

- Minimize \(SSE\)

\(SSE = F(\beta_0, \beta_1 ) = \sum_1^5 (\beta_0 + \beta_1x_i - y_i)^2\); multivariable (geometry) calculus problem.

- Maximize likelihood function, \(L\)

\(L = \prod_1^5 \frac{1}{\sqrt{2\pi}\sigma}\exp(-\frac{(\beta_0 + \beta_1x_i - y_i)^2}{2\sigma^2})\). Or, minimize \(-ln(L)\) which is the same as minimizing \(SSE\).

- Solve \(X^TX\cdot B=X^TY\)

\(X=\begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_5 \end{bmatrix}\), \(B=\begin{bmatrix} \beta_0 \\ \beta_1 \end{bmatrix}\), \(Y=\begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_5 \end{bmatrix}\).





linreg.res <- glm(data = data.frame(x=ind.var, y= dep.var), y ~ x, family=gaussian )
coef(summary(linreg.res))
              Estimate Std. Error    t value     Pr(>|t|)
(Intercept) -0.2844622  1.0760642 -0.2643543 0.7981897442
x            0.9472229  0.1734235  5.4619079 0.0006001724

2. Logistic regression.

\(Y|x \sim B(n,p|_x).\) We assume that \(E(Y|x) = n\cdot inv.logit(\beta_0 +\beta_1 x)\).

Since \(E(Y|x)=n\cdot p|_x\), \(p|_x=inv.logit(\beta_0 +\beta_1 x)\). Or,

\(logit(p|_x)=\beta_0 +\beta_1 x\).

Probability distribution,

\(f(1|x)=p|_x\) and \(f(0|x)=1-p|_x\)

\[L=\prod_{y_i=0}(1-p|_{x_i})\cdot \prod_{y_i=1}(p|_{x_i})\]

\[\ln L = \sum_{i}((1-y_i)\ln (1-p|_{x_i}) + y_i\ln (p|_{x_i}))\]

\[ \left( \frac{\hat{\beta_i}}{s.e.(\hat{\beta_i})} \right)^2 \sim \chi^2 \]

library(ggplot2)
ind.var_bin <- seq(-3, 3, by=0.5)
#p <- inv.logit(ind.var_bin)

dep.var_bin <- c(0,0,0,1,0,1,0,1,1,0,1,1,1)

binreg.res <- glm(data = data.frame(x=ind.var_bin, y= dep.var_bin), y ~ x, family=binomial(link=logit) )
coef(summary(binreg.res))
             Estimate Std. Error   z value   Pr(>|z|)
(Intercept) 0.2331067  0.6881342 0.3387518 0.73479673
x           0.8053177  0.4440151 1.8137168 0.06972133
tt=seq(-3.2, 3.2, by = 0.1)
ggplot(data=data.frame(x=ind.var_bin, y=dep.var_bin))+geom_point(aes(x=x,y=y)) + 
  geom_line(data=data.frame(x=tt, y=inv.logit(coef(summary(binreg.res))[1,1]+coef(summary(binreg.res))[2,1]*tt)), aes(x=x,y=y)) 


success =  data.frame(count=rep(0, length(ind.var_bin)))
for (ii in (1:length(ind.var_bin))){
  
  p0 <- inv.logit(coef(summary(binreg.res))[1,1]+coef(summary(binreg.res))[2,1]*ind.var_bin[ii])
  success$count[ii] = rbinom(1,100, p0)
  
}

ggplot(data = data.frame(x=ind.var_bin, count=success$count)) + geom_point(aes(x=x,y=count/100)) + geom_line(data=data.frame(x=tt, y=inv.logit(coef(summary(binreg.res))[1,1]+coef(summary(binreg.res))[2,1]*tt)), aes(x=x,y=y)) 



# 
# x0 <- seq(1:100)/100 
# y0 <- 10*dbinom(seq(1:100), 100, p0)
# 
# ggplot(data=data.frame(x=x0, y=y0))+geom_point(aes(x=y,y=x), pch=15, size=0.5)

  # geom_line(data = data.frame(x=dbinom(seq(1:100), 100, 1.5)+7, 
  #                             y=seq(-3.5,0,by=0.01)+interc + slope*7), aes(x=x, y= y  )) + 
  # geom_line(data = data.frame(x=dnorm(seq(0,3.5,by=0.01), 0, 1.5)+7, 
  #                             y=seq(0,3.5,by=0.01)+interc + slope*7), aes(x=x, y= y  ))









3. Poisson regression.

\(Y|_x \sim Poisson(e^{\beta_0 +\beta_1 x})\)

\(E(Y|_x)=e^{\beta_0 +\beta_1 x}\)

\[f(y|_x)=\frac{e^{(\beta_0 +\beta_1 x)y} \exp(-e^{\beta_0 +\beta_1 x})}{y!}\]

\[\ln L = \sum_{i}\left( (\beta_0+\beta_1 x_i)y_i - e^{\beta_0+\beta_1 x_i} - \ln (y_i!) \right)\]

\[ \ln (E(Y|_x)) = \beta_0 + \beta_1 x. \] Linear again!!

pois_reg <- glm(data=data, y ~ x, family=poisson)





slope=1.5
x=seq(0, 1, by=0.1)
y=rpois(11, exp(1+slope*x))


pois_reg <- glm(data=data.frame(x=x,y=y), y ~ x, family=poisson)
p_slope = coef(summary(pois_reg))[2,1]; p_interc <- coef(summary(pois_reg))[1,1]
coef(summary(pois_reg))
             Estimate Std. Error  z value     Pr(>|z|)
(Intercept) 0.9086504  0.2974696 3.054599 0.0022536163
x           1.5121244  0.4194391 3.605111 0.0003120198
lin_reg <- glm(data=data.frame(x=x,y=y), y ~ x, family=gaussian)
l_slope = coef(summary(lin_reg))[2,1]; l_interc <- coef(summary(lin_reg))[1,1]
coef(summary(lin_reg))
            Estimate Std. Error  t value   Pr(>|t|)
(Intercept) 1.636364   1.439123 1.137056 0.28488131
x           8.545455   2.432561 3.512945 0.00658806
ggplot(data = data.frame(x=x,y=y))+geom_point(aes(x=x,y=y)) +
  geom_line( data=data.frame(x=seq(0, 1, by=0.05), y=exp(1+slope*seq(0, 1, by=0.05)))     , aes(x=x,y=y)) +
  geom_line( data=data.frame(x=seq(0, 1, by=0.05), y=exp(p_interc+p_slope*seq(0, 1, by=0.05))), aes(x=x,y=y), color = "red") +
  geom_line( data=data.frame(x=seq(0, 1, by=0.05), y=l_interc+l_slope*seq(0, 1, by=0.05)), aes(x=x,y=y), color = "blue")

NA
NA
NA





Regressions to compare two groups: P-value calculation.

- State marker expression data.

What’s the population? What is the random variable? Samples?

Example:

  • population of virginia who had heart attack.
  • Median of NK\(\kappa\)B expression from all Treg cells.
  • 16 people.

What is the distribution?

  • one side open ended counting data: Poisson, Negative binomial distribution
  • data transformed by \(\text{asinh}=\ln (x+\sqrt{x^2+1}) \sim \ln 2 + \ln x \text{ for} x>>1\)
  • Gaussian.

Use T-test or linear regression

ggplot(data = data.frame(x=seq(-10, 100, by=1), y=asinh(seq(-10, 100, by=1))))+geom_line(aes(x=x,y=y)) + coord_fixed(ratio = 4/1) +
  labs(title = paste("y = asinh(x)")) 









- Proportion data. Cluster proportions.

What is the distribution?

- Binomial distribution. Logistic regression or Quasi-logistic regression.

\[ P(x=k)= {n \choose x}p(p+k\phi)^{k-1}(1-p-k\phi)^{n-k}\]

- If \(X \sim B(n,p)\), \(X \sim N(np, npq)\), approximately (\(n\geq 15\)). Then, t-test or linear regression can be applied.

ggplot(data = data.frame(x=seq(0.01,0.99, by=0.01), y=logit( seq(0.01,0.99, by=0.01) )))+geom_line(aes(x=x,y=y)) + coord_fixed(ratio = 1/9) +
  labs(title = paste("y = logit(x)"))

- \[ \ln\left( \frac{proportion}{1-proportion} \right) \sim Gaussian\]. Apply t-test or linear regression to log odds ratio.

Weights

- Maximize likelihood function, \(L\)

\[L = \prod_1^n \left( \frac{1}{\sqrt{2\pi}\sigma}\exp \left(-\frac{(\beta_0 + \beta_1x_i - y_i)^2}{2\sigma^2} \right) \right)^{w_i}.\]

\[ -\ln L = Constant \cdot \sum^n_1w_i (\beta_0 + \beta_1x_i - y_i)^2\]

LS0tCnRpdGxlOiAiUmVncmVzc2lvbnMgZm9yIGRpZmZlcmVudGlhbCBhbmFseXNpcyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyMgQXJlIHRoZXNlIHR3byBncm91cHMgZGlmZmVyZW50PyBXZSBjb21wYXJlIHR3byBzYW1wbGVzIGluIHRlcm1zIG9mIHN0YXRpc3RpY2FsIHBhcmFtZXRlcnMgc3VjaCBhcyBtZWFuLCB2YXJpYW5jZSwgZXRjLgoKIyMgKip0LXRlc3Q6IG1lYW4gY29tcGFyaXNvbi4qKgoKIyMgJFx7eF8xLCB4XzIsIHhfMywgeF80LCBcZG90cywgeF97bl8xfSBcfSQgaXMgZnJvbSAkTihcbXVfMSwgXHNpZ21hXzFeMikkIGFuZCAKIyMgJFx7eV8xLCB5XzIsIHlfMywgeV80LCBcZG90cywgeV97bl8yfSBcfSQgaXMgZnJvbSAkTihcbXVfMiwgXHNpZ21hXzJeMikkCgoKYGBge3J9CnggPC0gYyg1LjEyLCA1LjI4LCA0Ljk4LCA0LjYyLCA0Ljk1LCA0LjM1LCA0LjgzLCA2LjE1LCA1LjgzLCA1LjQzKQp5IDwtIGMoNS4zNywgNS42MywgNS44OSwgNS45MiwgNS45MSwgNi4xNSwgNi4yOSwgNi40MSwgNi44OCwgNy4xMikKCnFxbm9ybSh4KTsKcXFub3JtKHkpOwoKdHRlc3QucmVzIDwtIHQudGVzdCh4LHkpCnR0ZXN0LnJlcyRwLnZhbHVlCgpgYGAKIyMgJHQtc2NvcmUgPSBcZnJhY3tcYmFye3h9LVxiYXJ7eX19eyBcc3FydHsgc14yX3gvbl8xK3NeMl95L25fMiAgfSAgfSQgCiMjIGRpc3RyaWJ1dGlvbiBpcyAkdF97KFxudSl9JAojIyAkXG51ID0gXGZyYWN7KHNeMl94L25fMStzXjJfeS9uXzIpXjJ9eyhzXjJfeC9uXzEpXjIvKG5fMS0xKSsoc14yX3kvbl8yKV4yLyhuXzItMSl9JAoKCjxiciAvPgo8YnIgLz4KPGJyIC8+CjxiciAvPgoKPGJyIC8+CjxiciAvPgo8YnIgLz4KPGJyIC8+CgojICoqTGluZWFyIHJlZ3Jlc3Npb24qKgojIyAkXGhhdHt5fT1cYmV0YV8wICsgXGJldGFfMSB4JAoKIyMgJFx7eF8xLCB4XzIsIHhfMywgeF80LCBcZG90cywgeF97bl8xfSBcfSQgaXMgZnJvbSAkTihcYmV0YV8wK1xiZXRhXzFcY2RvdCAwLCBcc2lnbWFeMikkIGFuZCAKIyMgJFx7eV8xLCB5XzIsIHlfMywgXGRvdHMsIHlfe25fMn0gXH0kIGlzIGZyb20gJE4oXGJldGFfMCtcYmV0YV8xXGNkb3QgMSwgXHNpZ21hXjIpJAojIyBTaW5jZSB0aGUgZXN0aW1hdG9yJ3Mgb2YgJFxiZXRhXzAkIGFuZCAkXGJldGFfMSQgYXJlIGNhbGN1bGF0ZWQgYnkgdXNpbmcgJHhfaSQgYW5kICR5X2okLCB3ZSBhbHNvIGhhdmUgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9ucyBmb3IgdGhlIGVzdGltYXRvcnMgb2YgJFxiZXRhXzAkIGFuZCAkXGJldGFfMSQuICRcYmV0YV8xJCBlc3RpbWF0b3IncyBkaXN0cmlidXRpb24gaXMgYW5vdGhlciAkdCQtZGlzdHJpYnV0aW9uLiBVc2luZyB0aGlzIHdlIGNhbiB0ZXN0CiMjICRIXzA6XGJldGFfMT0wJAojIyBJZiByZWplY3RlZCwgJGkuZS4kLCAkUC0kdmFsdWUgaXMgbG93IGVub3VnaCwgd2UgY2FuIHNheSB0aGF0IG1lYW5zIGFyZSBkaWZmZXJlbnQuCgpgYGB7cn0KbGlicmFyeShnZ3Bsb3QyKQpybShkYXRhXzRfbGluX3JlZykKZGF0YV80X2xpbl9yZWcgPC0gZGF0YS5mcmFtZShuYW1lID0gcmVwKCJ4IiwgbGVuZ3RoKHgpKSwgdmFsdWVzID0geCkKZGF0YV80X2xpbl9yZWcgPC0gcmJpbmQoZGF0YV80X2xpbl9yZWcsIGRhdGEuZnJhbWUobmFtZSA9IHJlcCgieSIsIGxlbmd0aCh5KSksIHZhbHVlcyA9IHkpKQpnZ3Bsb3QoZGF0YSA9IGRhdGFfNF9saW5fcmVnLCBhZXMoeD1uYW1lLCB5PXZhbHVlcykpK2dlb21fYm94cGxvdCgpCgoKCiMgbGluX3JlZzIgPC0gZ2xtKGRhdGEgPSBkYXRhXzRfbGluX3JlZywgdmFsdWVzIH4gbmFtZSwgZmFtaWx5PWdhdXNzaWFuKQojIHN1bW1hcnkobGluX3JlZzIpCmBgYAoKCgoKCgoKYGBge3J9CnZhci50ZXN0KHgsIHksIGFsdGVybmF0aXZlID0gInR3by5zaWRlZCIpCgpsaW5fcmVnIDwtIGxtKGRhdGEgPSBkYXRhXzRfbGluX3JlZywgdmFsdWVzIH4gbmFtZSkKY29lZihzdW1tYXJ5KGxpbl9yZWcpKVsyLDRdCmBgYAoKCgpgYGB7cn0KeV8xPTEuNCp5LTIuMAoKCgpgYGAKCgoKYGBge3J9CnZhci50ZXN0KHgsIHlfMSwgYWx0ZXJuYXRpdmUgPSAidHdvLnNpZGVkIikKCgpgYGAKCmBgYHtyfQp0dGVzdC5yZXMgPC0gdC50ZXN0KHgseV8xKQp0dGVzdC5yZXMkcC52YWx1ZQpgYGAKCmBgYHtyfQoKcm0oZGF0YV80X2xpbl9yZWcpCmRhdGFfNF9saW5fcmVnIDwtIGRhdGEuZnJhbWUobmFtZSA9IHJlcCgieCIsIGxlbmd0aCh4KSksIHZhbHVlcyA9IHgpCmRhdGFfNF9saW5fcmVnIDwtIHJiaW5kKGRhdGFfNF9saW5fcmVnLCBkYXRhLmZyYW1lKG5hbWUgPSByZXAoInkiLCBsZW5ndGgoeV8xKSksIHZhbHVlcyA9IHlfMSkpCiNkYXRhXzRfbGluX3JlZwoKZ2dwbG90KGRhdGEgPSBkYXRhXzRfbGluX3JlZywgYWVzKHg9bmFtZSwgeT12YWx1ZXMpKStnZW9tX2JveHBsb3QoKQpgYGAKCmBgYHtyfQpsaW5fcmVnIDwtIGxtKGRhdGEgPSBkYXRhXzRfbGluX3JlZywgdmFsdWVzIH4gbmFtZSkKY29lZihzdW1tYXJ5KGxpbl9yZWcpKVsyLDRdCgpgYGAKPGJyIC8+CjxiciAvPgo8YnIgLz4KPGJyIC8+Cgo8YnIgLz4KPGJyIC8+CjxiciAvPgo8YnIgLz4KCiMgKipHZW5lcmFsIGxpbmVhciByZWdyZXNzaW9ucyoqCgoKCiMjICoqMS4gTGluZWFyIHJlZ3Jlc3Npb24uKiogCiMjICRZfF97eH0gXHNpbSBOKFxiZXRhXzAgKyBcYmV0YV8xIHgsXHNpZ21hKSQKIyMgJEUoWXxfe3h9KT1cYmV0YV8wICtcYmV0YV8xIHgkCiMjIFByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiwgJGYoeXx4OyhcYmV0YV8wLCBcYmV0YV8xICkpPW4oXGJldGFfMCArIFxiZXRhXzEgeCxcc2lnbWEpJAoKYGBge3J9CgppbmQudmFyIDwtIHNlcSgxLCAxMCwgYnk9MSkKZGVwLnZhciA8LSBpbmQudmFyICsgcm5vcm0oMTAsIDAsIDEuNSkKCmBgYAoKCmBgYHtyfQpsaW5yZWcucmVzIDwtIGxtKGRhdGEgPSBkYXRhLmZyYW1lKHg9aW5kLnZhciwgeT0gZGVwLnZhciksIHkgfiB4KQpjb2VmKHN1bW1hcnkobGlucmVnLnJlcykpCgoKaW50ZXJjID0gY29lZihzdW1tYXJ5KGxpbnJlZy5yZXMpKVsxLDFdOyBzbG9wZSA9IGNvZWYoc3VtbWFyeShsaW5yZWcucmVzKSlbMiwxXQoKZ2dwbG90KGRhdGEgPSBkYXRhLmZyYW1lKHg9aW5kLnZhciwgeT0gZGVwLnZhcikpK2dlb21fcG9pbnQoYWVzKHg9aW5kLnZhciwgeT1kZXAudmFyKSkgKyAKICBnZW9tX2xpbmUoYWVzKHg9aW5kLnZhciwgeT1pbnRlcmMgKyBzbG9wZSppbmQudmFyICAgKSkgKwogIGdlb21fbGluZShkYXRhID0gZGF0YS5mcmFtZSh4PWRub3JtKHNlcSgtMy41LDAsYnk9MC4wMSksIDAsIDEuNSkrMywgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHk9c2VxKC0zLjUsMCxieT0wLjAxKStpbnRlcmMgKyBzbG9wZSozKSwgYWVzKHg9eCwgeT0geSAgKSkgKyAKICBnZW9tX2xpbmUoZGF0YSA9IGRhdGEuZnJhbWUoeD1kbm9ybShzZXEoMCwzLjUsYnk9MC4wMSksIDAsIDEuNSkrMywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgeT1zZXEoMCwzLjUsYnk9MC4wMSkraW50ZXJjICsgc2xvcGUqMyksIGFlcyh4PXgsIHk9IHkgICkpICsKICBnZW9tX2xpbmUoZGF0YSA9IGRhdGEuZnJhbWUoeD1kbm9ybShzZXEoLTMuNSwwLGJ5PTAuMDEpLCAwLCAxLjUpKzUsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5PXNlcSgtMy41LDAsYnk9MC4wMSkraW50ZXJjICsgc2xvcGUqNSksIGFlcyh4PXgsIHk9IHkgICkpICsgCiAgZ2VvbV9saW5lKGRhdGEgPSBkYXRhLmZyYW1lKHg9ZG5vcm0oc2VxKDAsMy41LGJ5PTAuMDEpLCAwLCAxLjUpKzUsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5PXNlcSgwLDMuNSxieT0wLjAxKStpbnRlcmMgKyBzbG9wZSo1KSwgYWVzKHg9eCwgeT0geSAgKSkgKwogIGdlb21fbGluZShkYXRhID0gZGF0YS5mcmFtZSh4PWRub3JtKHNlcSgtMy41LDAsYnk9MC4wMSksIDAsIDEuNSkrNywgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHk9c2VxKC0zLjUsMCxieT0wLjAxKStpbnRlcmMgKyBzbG9wZSo3KSwgYWVzKHg9eCwgeT0geSAgKSkgKyAKICBnZW9tX2xpbmUoZGF0YSA9IGRhdGEuZnJhbWUoeD1kbm9ybShzZXEoMCwzLjUsYnk9MC4wMSksIDAsIDEuNSkrNywgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHk9c2VxKDAsMy41LGJ5PTAuMDEpK2ludGVyYyArIHNsb3BlKjcpLCBhZXMoeD14LCB5PSB5ICApKQoKCmBgYAojIyBIb3cgdG8gZmluZCAkXGJldGFfMCQgYW5kICRcYmV0YV8xJC4KIyMgRGF0YSAkXHsoeF8xLCB5XzEpLCAgKHhfMiwgeV8yKSwgICh4XzMsIHlfMyksICh4XzQsIHlfNCksICh4XzUsIHlfNSlcfSQKIyMjIC0gTWluaW1pemUgJFNTRSQKIyMjICRTU0UgPSBGKFxiZXRhXzAsIFxiZXRhXzEgKSA9IFxzdW1fMV41IChcYmV0YV8wICsgXGJldGFfMXhfaSAtIHlfaSleMiQ7IG11bHRpdmFyaWFibGUgKGdlb21ldHJ5KSBjYWxjdWx1cyBwcm9ibGVtLgoKIyMjIC0gTWF4aW1pemUgbGlrZWxpaG9vZCBmdW5jdGlvbiwgJEwkCiMjIyAkTCA9IFxwcm9kXzFeNSBcZnJhY3sxfXtcc3FydHsyXHBpfVxzaWdtYX1cZXhwKC1cZnJhY3soXGJldGFfMCArIFxiZXRhXzF4X2kgLSB5X2kpXjJ9ezJcc2lnbWFeMn0pJC4gT3IsIG1pbmltaXplICQtbG4oTCkkIHdoaWNoIGlzIHRoZSBzYW1lIGFzIG1pbmltaXppbmcgJFNTRSQuCgojIyMgLSBTb2x2ZSAkWF5UWFxjZG90IEI9WF5UWSQKIyMjIyAkWD1cYmVnaW57Ym1hdHJpeH0KMSAmIHhfMSBcXCAKMSAmIHhfMiBcXCAKXHZkb3RzICYgXHZkb3RzIFxcIAoxICYgeF81IApcZW5ke2JtYXRyaXh9JCwgJEI9XGJlZ2lue2JtYXRyaXh9IFxiZXRhXzAgXFwKXGJldGFfMQpcZW5ke2JtYXRyaXh9JCwgJFk9XGJlZ2lue2JtYXRyaXh9CnlfMSBcXAp5XzIgXFwKXHZkb3RzIFxcCnlfNQpcZW5ke2JtYXRyaXh9JC4KCjxiciAvPgo8YnIgLz4KPGJyIC8+CjxiciAvPgoKCgpgYGB7cn0KbGlucmVnLnJlcyA8LSBnbG0oZGF0YSA9IGRhdGEuZnJhbWUoeD1pbmQudmFyLCB5PSBkZXAudmFyKSwgeSB+IHgsIGZhbWlseT1nYXVzc2lhbiApCmNvZWYoc3VtbWFyeShsaW5yZWcucmVzKSkKYGBgCgoKIyMgKioyLiBMb2dpc3RpYyByZWdyZXNzaW9uLioqCiMjICRZfHggXHNpbSBCKG4scHxfeCkuJCBXZSBhc3N1bWUgdGhhdCAkRShZfHgpID0gblxjZG90IGludi5sb2dpdChcYmV0YV8wICtcYmV0YV8xIHgpJC4KIyMgU2luY2UgJEUoWXx4KT1uXGNkb3QgcHxfeCQsICRwfF94PWludi5sb2dpdChcYmV0YV8wICtcYmV0YV8xIHgpJC4gT3IsCiMjICRsb2dpdChwfF94KT1cYmV0YV8wICtcYmV0YV8xIHgkLgojIyBMb2dpdCBpcyBjYWxsZWQgdGhlIGxpbmsgZnVuY3Rpb24gZm9yIGxvZ2lzdGljIHJlZ3Jlc3Npb24uIAojIyBQcm9iYWJpbGl0eSBkaXN0cmlidXRpb24sIAojIyMgJGYoMXx4KT1wfF94JCBhbmQgJGYoMHx4KT0xLXB8X3gkCgojIyMgJCRMPVxwcm9kX3t5X2k9MH0oMS1wfF97eF9pfSlcY2RvdCBccHJvZF97eV9pPTF9KHB8X3t4X2l9KSQkCiMjIyAkJFxsbiBMID0gXHN1bV97aX0oKDEteV9pKVxsbiAoMS1wfF97eF9pfSkgKyB5X2lcbG4gKHB8X3t4X2l9KSkkJAojIyMgJCQgXGxlZnQoIFxmcmFje1xoYXR7XGJldGFfaX19e3MuZS4oXGhhdHtcYmV0YV9pfSl9IFxyaWdodCleMiBcc2ltIFxjaGleMiAkJCAgCgpgYGB7cn0KbGlicmFyeShnZ3Bsb3QyKQppbmQudmFyX2JpbiA8LSBzZXEoLTMsIDMsIGJ5PTAuNSkKI3AgPC0gaW52LmxvZ2l0KGluZC52YXJfYmluKQoKZGVwLnZhcl9iaW4gPC0gYygwLDAsMCwxLDAsMSwwLDEsMSwwLDEsMSwxKQoKYmlucmVnLnJlcyA8LSBnbG0oZGF0YSA9IGRhdGEuZnJhbWUoeD1pbmQudmFyX2JpbiwgeT0gZGVwLnZhcl9iaW4pLCB5IH4geCwgZmFtaWx5PWJpbm9taWFsKGxpbms9bG9naXQpICkKY29lZihzdW1tYXJ5KGJpbnJlZy5yZXMpKQoKdHQ9c2VxKC0zLjIsIDMuMiwgYnkgPSAwLjEpCmdncGxvdChkYXRhPWRhdGEuZnJhbWUoeD1pbmQudmFyX2JpbiwgeT1kZXAudmFyX2JpbikpK2dlb21fcG9pbnQoYWVzKHg9eCx5PXkpKSArIAogIGdlb21fbGluZShkYXRhPWRhdGEuZnJhbWUoeD10dCwgeT1pbnYubG9naXQoY29lZihzdW1tYXJ5KGJpbnJlZy5yZXMpKVsxLDFdK2NvZWYoc3VtbWFyeShiaW5yZWcucmVzKSlbMiwxXSp0dCkpLCBhZXMoeD14LHk9eSkpIAoKc3VjY2VzcyA9ICBkYXRhLmZyYW1lKGNvdW50PXJlcCgwLCBsZW5ndGgoaW5kLnZhcl9iaW4pKSkKZm9yIChpaSBpbiAoMTpsZW5ndGgoaW5kLnZhcl9iaW4pKSl7CiAgCiAgcDAgPC0gaW52LmxvZ2l0KGNvZWYoc3VtbWFyeShiaW5yZWcucmVzKSlbMSwxXStjb2VmKHN1bW1hcnkoYmlucmVnLnJlcykpWzIsMV0qaW5kLnZhcl9iaW5baWldKQogIHN1Y2Nlc3MkY291bnRbaWldID0gcmJpbm9tKDEsMTAwLCBwMCkKICAKfQoKZ2dwbG90KGRhdGEgPSBkYXRhLmZyYW1lKHg9aW5kLnZhcl9iaW4sIGNvdW50PXN1Y2Nlc3MkY291bnQpKSArIGdlb21fcG9pbnQoYWVzKHg9eCx5PWNvdW50LzEwMCkpICsgZ2VvbV9saW5lKGRhdGE9ZGF0YS5mcmFtZSh4PXR0LCB5PWludi5sb2dpdChjb2VmKHN1bW1hcnkoYmlucmVnLnJlcykpWzEsMV0rY29lZihzdW1tYXJ5KGJpbnJlZy5yZXMpKVsyLDFdKnR0KSksIGFlcyh4PXgseT15KSkgCgoKIyAKIyB4MCA8LSBzZXEoMToxMDApLzEwMCAKIyB5MCA8LSAxMCpkYmlub20oc2VxKDE6MTAwKSwgMTAwLCBwMCkKIyAKIyBnZ3Bsb3QoZGF0YT1kYXRhLmZyYW1lKHg9eDAsIHk9eTApKStnZW9tX3BvaW50KGFlcyh4PXkseT14KSwgcGNoPTE1LCBzaXplPTAuNSkKCiAgIyBnZW9tX2xpbmUoZGF0YSA9IGRhdGEuZnJhbWUoeD1kYmlub20oc2VxKDE6MTAwKSwgMTAwLCAxLjUpKzcsIAogICMgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHk9c2VxKC0zLjUsMCxieT0wLjAxKStpbnRlcmMgKyBzbG9wZSo3KSwgYWVzKHg9eCwgeT0geSAgKSkgKyAKICAjIGdlb21fbGluZShkYXRhID0gZGF0YS5mcmFtZSh4PWRub3JtKHNlcSgwLDMuNSxieT0wLjAxKSwgMCwgMS41KSs3LCAKICAjICAgICAgICAgICAgICAgICAgICAgICAgICAgICB5PXNlcSgwLDMuNSxieT0wLjAxKStpbnRlcmMgKyBzbG9wZSo3KSwgYWVzKHg9eCwgeT0geSAgKSkKCgoKYGBgCjxiciAvPgo8YnIgLz4KPGJyIC8+CjxiciAvPgo8YnIgLz4KPGJyIC8+CjxiciAvPgo8YnIgLz4KCgojIyAqKjMuIFBvaXNzb24gcmVncmVzc2lvbi4qKiAKIyMgJFl8X3ggXHNpbSBQb2lzc29uKGVee1xiZXRhXzAgK1xiZXRhXzEgeH0pJAojIyAkRShZfF94KT1lXntcYmV0YV8wICtcYmV0YV8xIHh9JAojIyAkJGYoeXxfeCk9XGZyYWN7ZV57KFxiZXRhXzAgK1xiZXRhXzEgeCl5fSBcZXhwKC1lXntcYmV0YV8wICtcYmV0YV8xIHh9KX17eSF9JCQKCiMjIyAkJFxsbiBMID0gXHN1bV97aX1cbGVmdCggKFxiZXRhXzArXGJldGFfMSB4X2kpeV9pIC0gZV57XGJldGFfMCtcYmV0YV8xIHhfaX0gLSBcbG4gKHlfaSEpIFxyaWdodCkkJAoKIyMjICQkIFxsbiAoRShZfF94KSkgPSBcYmV0YV8wICsgXGJldGFfMSB4LiAkJCBMaW5lYXIgYWdhaW4hIQoKCmBgYHtyfQpwb2lzX3JlZyA8LSBnbG0oZGF0YT1kYXRhLCB5IH4geCwgZmFtaWx5PXBvaXNzb24pCmBgYAoKPGJyIC8+CjxiciAvPgo8YnIgLz4KPGJyIC8+CgpgYGB7cn0Kc2xvcGU9MS41Cng9c2VxKDAsIDEsIGJ5PTAuMSkKeT1ycG9pcygxMSwgZXhwKDErc2xvcGUqeCkpCgoKcG9pc19yZWcgPC0gZ2xtKGRhdGE9ZGF0YS5mcmFtZSh4PXgseT15KSwgeSB+IHgsIGZhbWlseT1wb2lzc29uKQpwX3Nsb3BlID0gY29lZihzdW1tYXJ5KHBvaXNfcmVnKSlbMiwxXTsgcF9pbnRlcmMgPC0gY29lZihzdW1tYXJ5KHBvaXNfcmVnKSlbMSwxXQpjb2VmKHN1bW1hcnkocG9pc19yZWcpKQpsaW5fcmVnIDwtIGdsbShkYXRhPWRhdGEuZnJhbWUoeD14LHk9eSksIHkgfiB4LCBmYW1pbHk9Z2F1c3NpYW4pCmxfc2xvcGUgPSBjb2VmKHN1bW1hcnkobGluX3JlZykpWzIsMV07IGxfaW50ZXJjIDwtIGNvZWYoc3VtbWFyeShsaW5fcmVnKSlbMSwxXQpjb2VmKHN1bW1hcnkobGluX3JlZykpCgpnZ3Bsb3QoZGF0YSA9IGRhdGEuZnJhbWUoeD14LHk9eSkpK2dlb21fcG9pbnQoYWVzKHg9eCx5PXkpKSArCiAgZ2VvbV9saW5lKCBkYXRhPWRhdGEuZnJhbWUoeD1zZXEoMCwgMSwgYnk9MC4wNSksIHk9ZXhwKDErc2xvcGUqc2VxKDAsIDEsIGJ5PTAuMDUpKSkgICAgICwgYWVzKHg9eCx5PXkpKSArCiAgZ2VvbV9saW5lKCBkYXRhPWRhdGEuZnJhbWUoeD1zZXEoMCwgMSwgYnk9MC4wNSksIHk9ZXhwKHBfaW50ZXJjK3Bfc2xvcGUqc2VxKDAsIDEsIGJ5PTAuMDUpKSksIGFlcyh4PXgseT15KSwgY29sb3IgPSAicmVkIikgKwogIGdlb21fbGluZSggZGF0YT1kYXRhLmZyYW1lKHg9c2VxKDAsIDEsIGJ5PTAuMDUpLCB5PWxfaW50ZXJjK2xfc2xvcGUqc2VxKDAsIDEsIGJ5PTAuMDUpKSwgYWVzKHg9eCx5PXkpLCBjb2xvciA9ICJibHVlIikKCgoKYGBgCgo8YnIgLz4KPGJyIC8+CjxiciAvPgo8YnIgLz4KCgojICoqUmVncmVzc2lvbnMgdG8gY29tcGFyZSB0d28gZ3JvdXBzOiBQLXZhbHVlIGNhbGN1bGF0aW9uLioqCgojIyAtIFN0YXRlIG1hcmtlciBleHByZXNzaW9uIGRhdGEuCgojIyMgV2hhdCdzIHRoZSBwb3B1bGF0aW9uPyBXaGF0IGlzIHRoZSByYW5kb20gdmFyaWFibGU/IFNhbXBsZXM/CgojIyMgRXhhbXBsZTogCi0gcG9wdWxhdGlvbiBvZiB2aXJnaW5pYSB3aG8gaGFkIGhlYXJ0IGF0dGFjay4gCi0gTWVkaWFuIG9mIE5LJFxrYXBwYSRCIGV4cHJlc3Npb24gZnJvbSBhbGwgVHJlZyBjZWxscy4KLSAxNiBwZW9wbGUuCgojIyMgV2hhdCBpcyB0aGUgZGlzdHJpYnV0aW9uPyAKLSBvbmUgc2lkZSBvcGVuIGVuZGVkIGNvdW50aW5nIGRhdGE6IFBvaXNzb24sIE5lZ2F0aXZlIGJpbm9taWFsIGRpc3RyaWJ1dGlvbgotIGRhdGEgdHJhbnNmb3JtZWQgYnkgJFx0ZXh0e2FzaW5ofT1cbG4gKHgrXHNxcnR7eF4yKzF9KSBcc2ltIFxsbiAyICsgXGxuIHggXHRleHR7IGZvcn0geD4+MSQKLSBHYXVzc2lhbi4KCiMjIyBVc2UgVC10ZXN0IG9yIGxpbmVhciByZWdyZXNzaW9uCgpgYGB7cn0KZ2dwbG90KGRhdGEgPSBkYXRhLmZyYW1lKHg9c2VxKC0xMCwgMTAwLCBieT0xKSwgeT1hc2luaChzZXEoLTEwLCAxMDAsIGJ5PTEpKSkpK2dlb21fbGluZShhZXMoeD14LHk9eSkpICsgY29vcmRfZml4ZWQocmF0aW8gPSA0LzEpICsKICBsYWJzKHRpdGxlID0gcGFzdGUoInkgPSBhc2luaCh4KSIpKSAKCmBgYAoKPGJyIC8+CjxiciAvPgo8YnIgLz4KPGJyIC8+CjxiciAvPgo8YnIgLz4KPGJyIC8+CjxiciAvPgoKIyMgIC0gUHJvcG9ydGlvbiBkYXRhLiBDbHVzdGVyIHByb3BvcnRpb25zLgoKIyMjIFdoYXQgaXMgdGhlIGRpc3RyaWJ1dGlvbj8gCgojIyMjIC0gQmlub21pYWwgZGlzdHJpYnV0aW9uLiAqKkxvZ2lzdGljIHJlZ3Jlc3Npb24qKiBvciBRdWFzaS1sb2dpc3RpYyByZWdyZXNzaW9uLgojIyMjICQkIFAoeD1rKT0ge24gXGNob29zZSB4fXAocCtrXHBoaSlee2stMX0oMS1wLWtccGhpKV57bi1rfSQkCiMjIyMgLSBJZiAkWCBcc2ltIEIobixwKSQsICRYIFxzaW0gTihucCwgbnBxKSQsIGFwcHJveGltYXRlbHkgKCRuXGdlcSAxNSQpLiBUaGVuLCAqKnQtdGVzdCoqIG9yIGxpbmVhciByZWdyZXNzaW9uIGNhbiBiZSBhcHBsaWVkLgoKYGBge3J9CmdncGxvdChkYXRhID0gZGF0YS5mcmFtZSh4PXNlcSgwLjAxLDAuOTksIGJ5PTAuMDEpLCB5PWxvZ2l0KCBzZXEoMC4wMSwwLjk5LCBieT0wLjAxKSApKSkrZ2VvbV9saW5lKGFlcyh4PXgseT15KSkgKyBjb29yZF9maXhlZChyYXRpbyA9IDEvOSkgKwogIGxhYnModGl0bGUgPSBwYXN0ZSgieSA9IGxvZ2l0KHgpIikpCmBgYAojIyMjIC0gJCQgXGxuXGxlZnQoIFxmcmFje3Byb3BvcnRpb259ezEtcHJvcG9ydGlvbn0gIFxyaWdodCkgXHNpbSBHYXVzc2lhbiQkLiBBcHBseSAqdC10ZXN0IG9yIGxpbmVhciByZWdyZXNzaW9uKiB0byAqKmxvZyBvZGRzIHJhdGlvKiouICAKCgojIyBXZWlnaHRzCiMjIyAtIE1heGltaXplIGxpa2VsaWhvb2QgZnVuY3Rpb24sICRMJAojIyMgJCRMID0gXHByb2RfMV5uIFxsZWZ0KCBcZnJhY3sxfXtcc3FydHsyXHBpfVxzaWdtYX1cZXhwIFxsZWZ0KC1cZnJhY3soXGJldGFfMCArIFxiZXRhXzF4X2kgLSB5X2kpXjJ9ezJcc2lnbWFeMn0gXHJpZ2h0KSBccmlnaHQpXnt3X2l9LiQkCiMjIyAkJCAtXGxuIEwgPSBDb25zdGFudCBcY2RvdCBcc3VtXm5fMXdfaSAoXGJldGFfMCArIFxiZXRhXzF4X2kgLSB5X2kpXjIkJAo8IS0tICMjIyBSYW5kb20gbnVtYmVycyAtLT4KCjwhLS0gIyBgYGB7cn0gLS0+CjwhLS0gIyAjIHRlbXAgPC0gcnBvaXMoMTAwMDAsIDUwMCkgLS0+CjwhLS0gIyAjICN0ZW1wIC0tPgo8IS0tICMgIyBoaXN0KHRlbXApIC0tPgo8IS0tICMgIyAgLS0+CjwhLS0gIyAjICAtLT4KPCEtLSAjICMgdHQ9c2VxKC0zLDMsYnk9MC4wMSkgLS0+CjwhLS0gIyAjIHBsb3QoZG5vcm0odHQsMCwxKSx0dCkgLS0+CjwhLS0gIyBgYGAgLS0+CgoKPCEtLSAjIGBgYHtyfSAtLT4KPCEtLSAjIHRlbXBfbG9nIDwtIGxvZyh0ZW1wKSAtLT4KPCEtLSAjIGhpc3QodGVtcF9sb2cpIC0tPgo8IS0tICMgYGBgIC0tPgoKPCEtLSAjIGBgYHtyfSAtLT4KPCEtLSAjICMgcXFub3JtKHRlbXBfbG9nWzE6NTBdKTsgcXFsaW5lKHRlbXBfbG9nWzE6NTBdLCBjb2wgPSAyKSAtLT4KPCEtLSAjICMgIC0tPgo8IS0tICMgIyAgLS0+CjwhLS0gIyAjIHkgPC0gcnQoMjAwMDAsIGRmID0gNSkgLS0+CjwhLS0gIyAjIHFxbm9ybSh5KTsgcXFsaW5lKHksIGNvbCA9IDIpIC0tPgo8IS0tICMgYGBgIC0tPgoKCjwhLS0gIyBgYGB7cn0gLS0+CjwhLS0gIyAgLS0+CjwhLS0gIyAjIGJpbl90ZW1wIDwtIHJiaW5vbSgxMDAsIDEwMCwgMC4xKSAtLT4KPCEtLSAjICMgaGlzdChiaW5fdGVtcC8xMDApIC0tPgo8IS0tICMgIyAgLS0+CjwhLS0gIyAjIGhpc3QoaW52LmxvZ2l0KGJpbl90ZW1wLzEwMCkpIC0tPgo8IS0tICMgIyAgLS0+CjwhLS0gIyAjIHFxbm9ybShpbnYubG9naXQoYmluX3RlbXAvMTAwKSk7IHFxbGluZShpbnYubG9naXQoYmluX3RlbXAvMTAwKSwgY29sID0gMikgLS0+CjwhLS0gIyAgLS0+CjwhLS0gIyBgYGAgLS0+Cgo=