Dosen : Prof. Suhartono - UIN MALIKI MALANG

Author : Lia Wahyuliningtyas
Mahasiswa Magister Informatika






1. Deskripsi

In the previous chapter, the knowledge of both the generative model and the values of the parameters provided us with probabilities we could use for decision making – for instance, whether we had really found an epitope. In many real situations, neither the generative model nor the parameters are known, and we will need to estimate them using the data we have collected. Statistical modeling works from the data upwards to a model that might plausibly explain the data2121 Even if we have found a model that perfectly explains all our current data, it could always be that reality is more complex. A new set of data lets us conclude that another model is needed, and may include the current model as a special case or approximation.. This upward-reasoning step is called statistical inference. This chapter will show us some of the distributions and estimation mechanisms that serve as building blocks for inference. Although the examples in this chapter are all parametric (i.e., the statistical models only have a small number of unknown parameters), the principles we discuss will generalize.

2. A simple example of statistical modeling

The normal distribution, or bell shaped curve, is often a good model for continuous measurements. Distributions can also be more complicated mixtures of these elementary ones.

Let’s revisit the epitope example from the previous chapter, starting without the tricky outlier.

load("../Documents/data/data/e100.RData")
e99 = e100[-which.max(e100)]
barplot(table(e99), space = 0.8, col = "chartreuse4")

library("vcd")
## Loading required package: grid
gf1 = goodfit( e99, "poisson")
rootogram(gf1, xlab = "", rect_gp = gpar(fill = "chartreuse4"))

3. Estimating the parameter of the Poisson distribution

What value for the Poisson mean makes the data the most probable? In a first step, we tally the outcomes.

table(e100)
## e100
##  0  1  2  7 
## 58 34  7  1
table(rpois(100, 3))
## 
##  0  1  2  3  4  5  6  9 
##  5 24 27 11 17  7  8  1
prod(dpois(c(0, 1, 2, 7), lambda = 3) ^ (c(58, 34, 7, 1)))
## [1] 1.392143e-110
loglikelihood  =  function(lambda, data = e100) {
  sum(log(dpois(data, lambda)))
}

Now we can compute the likelihood for a whole series of lambda values from 0.05 to 0.95

lambdas = seq(0.05, 0.95, length = 100)
loglik = vapply(lambdas, loglikelihood, numeric(1))
plot(lambdas, loglik, type = "l", col = "red", ylab = "", lwd = 2,
     xlab = expression(lambda))
m0 = mean(e100)
abline(v = m0, col = "blue", lwd = 2)
abline(h = loglikelihood(m0), col = "purple", lwd = 2)

m0
## [1] 0.55
gf  =  goodfit(e100, "poisson")
names(gf)
## [1] "observed" "count"    "fitted"   "type"     "method"   "df"       "par"
gf$par
## $lambda
## [1] 0.55
gf$observed
## [1] 58 34  7  0  0  0  0  1
gf$fitted
## [1] 5.769498e+01 3.173224e+01 8.726366e+00 1.599834e+00 2.199771e-01
## [6] 2.419749e-02 2.218103e-03 1.742795e-04
gf$type
## [1] "poisson"

4. Classical statistics for classical data

cb <- rbinom(120, prob = 0.8, size = 1)
cb
##   [1] 0 0 1 1 1 1 0 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [38] 1 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 0 0 1 0 1 1 1
##  [75] 0 1 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 1 1
## [112] 0 1 1 1 1 1 1 0 1
table(cb)
## cb
##  0  1 
## 32 88
probs  =  seq(0, 0.3, by = 0.005)
likelihood = dbinom(sum(cb), prob = probs, size = length(cb))
plot(probs, likelihood, pch = 16, xlab = "probability of success",
       ylab = "likelihood", cex=0.6)

probs[which.max(likelihood)]
## [1] 0.3

Here’s a function we use to calculate it:

loglikelihood = function(theta, n = 300, k = 40) {
  115 + k * log(theta) + (n - k) * log(1 - theta)
}

which we plot for the range of θ from 0 to 1 (Figure 2.6).

thetas = seq(0, 1, by = 0.001)
plot(thetas, loglikelihood(thetas), xlab = expression(theta),
  ylab = expression(paste("log f(", theta, " | y)")),type = "l")

5. More boxes:multinomial data

DNA count modeling: base pairs This section combines estimation and testing by simulation in a real example. Data from one strand of DNA for the genes of Staphylococcus aureus bacterium are available in a fasta file staphsequence.ffn.txt, which we can read with a function from the Bioconductor package Biostrings.

library("Biostrings")
## Loading required package: BiocGenerics
## 
## Attaching package: 'BiocGenerics'
## The following objects are masked from 'package:stats':
## 
##     IQR, mad, sd, var, xtabs
## The following objects are masked from 'package:base':
## 
##     anyDuplicated, append, as.data.frame, basename, cbind, colnames,
##     dirname, do.call, duplicated, eval, evalq, Filter, Find, get, grep,
##     grepl, intersect, is.unsorted, lapply, Map, mapply, match, mget,
##     order, paste, pmax, pmax.int, pmin, pmin.int, Position, rank,
##     rbind, Reduce, rownames, sapply, setdiff, sort, table, tapply,
##     union, unique, unsplit, which.max, which.min
## Loading required package: S4Vectors
## Loading required package: stats4
## 
## Attaching package: 'S4Vectors'
## The following objects are masked from 'package:base':
## 
##     expand.grid, I, unname
## Loading required package: IRanges
## 
## Attaching package: 'IRanges'
## The following object is masked from 'package:vcd':
## 
##     tile
## The following object is masked from 'package:grDevices':
## 
##     windows
## Loading required package: XVector
## Loading required package: GenomeInfoDb
## 
## Attaching package: 'Biostrings'
## The following object is masked from 'package:grid':
## 
##     pattern
## The following object is masked from 'package:base':
## 
##     strsplit
staph = readDNAStringSet("../Documents/data/data/staphsequence.ffn.txt", "fasta")
letterFrequency(staph[[1]], letters = "ACGT", OR = 0)
##   A   C   G   T 
## 522 219 229 392
letterFrq = vapply(staph, letterFrequency, FUN.VALUE = numeric(4),
         letters = "ACGT", OR = 0)
colnames(letterFrq) = paste0("gene", seq(along = staph))
tab10 = letterFrq[, 1:10]
computeProportions = function(x) { x/sum(x) }
prop10 = apply(tab10, 2, computeProportions)
round(prop10, digits = 2)
##   gene1 gene2 gene3 gene4 gene5 gene6 gene7 gene8 gene9 gene10
## A  0.38  0.36  0.35  0.37  0.35  0.33  0.33  0.34  0.38   0.27
## C  0.16  0.16  0.13  0.15  0.15  0.15  0.16  0.16  0.14   0.16
## G  0.17  0.17  0.23  0.19  0.22  0.22  0.20  0.21  0.20   0.20
## T  0.29  0.31  0.30  0.29  0.27  0.30  0.30  0.29  0.28   0.36
p0 = rowMeans(prop10)
p0
##         A         C         G         T 
## 0.3470531 0.1518313 0.2011442 0.2999714
cs = colSums(tab10)
cs
##  gene1  gene2  gene3  gene4  gene5  gene6  gene7  gene8  gene9 gene10 
##   1362   1134    246   1113   1932   2661    831   1515   1287    696
expectedtab10 = outer(p0, cs, FUN = "*")
round(expectedtab10)
##   gene1 gene2 gene3 gene4 gene5 gene6 gene7 gene8 gene9 gene10
## A   473   394    85   386   671   924   288   526   447    242
## C   207   172    37   169   293   404   126   230   195    106
## G   274   228    49   224   389   535   167   305   259    140
## T   409   340    74   334   580   798   249   454   386    209
randomtab10 = sapply(cs, function(s) { rmultinom(1, s, p0) } )
all(colSums(randomtab10) == cs)
## [1] TRUE

Now we repeat this B = 1000 times. For each table we compute our test statistic from Section 1.4.1 in Chapter 1 (the function stat) and store the results in the vector simulstat. Together, these values constitute our null distribution, as they were generated under the null hypothesis that p0 is the vector of multinomial proportions for each of the 10 genes.

stat = function(obsvd, exptd = 20 * pvec) {
   sum((obsvd - exptd)^2 / exptd)
}
B = 1000
simulstat = replicate(B, {
  randomtab10 = sapply(cs, function(s) { rmultinom(1, s, p0) })
  stat(randomtab10, expectedtab10)
})
S1 = stat(tab10, expectedtab10)
sum(simulstat >= S1)
## [1] 0
hist(simulstat, col = "lavender", breaks = seq(0, 75, length.out=50))
abline(v = S1, col = "red")
abline(v = quantile(simulstat, probs = c(0.95, 0.99)),
       col = c("darkgreen", "blue"), lty = 2)

LS0tDQp0aXRsZTogIlN0YXRpc3RpY2FsIE1vZGVsaW5nIg0Kc3VidGl0bGU6ICJDaGFwdGVyIDIiDQoNCm91dHB1dDoNCiAgaHRtbF9kb2N1bWVudDoNCiAgICB0b2M6IHRydWUNCiAgICB0b2NfZmxvYXQ6IHRydWUNCiAgICB0aGVtZTogZmxhdGx5DQogICAgY29kZV9mb2xkaW5nOiAic2hvdyINCiAgICBjb2RlX2Rvd25sb2FkOiB5ZXMNCi0tLQ0KDQo8YnI+IDxpbWcgc3JjPSJpbWFnZXMvbG9nb191aW5fa2VjaWwucG5nIiBzdHlsZT0iZmxvYXQ6IGxlZnQ7IG1hcmdpbjogLTIwcHggNjBweCAwcHggNTBweDsgd2lkdGg6MjUlIi8+DQoNCg0KKipEb3NlbiA6IFByb2YuIFN1aGFydG9ubyAtIFVJTiBNQUxJS0kgTUFMQU5HKioNCg0KKkF1dGhvciA6IExpYSBXYWh5dWxpbmluZ3R5YXMqDQo8YnI+DQoqTWFoYXNpc3dhIE1hZ2lzdGVyIEluZm9ybWF0aWthKg0KPGJyPjxicj48YnI+PGJyPjxicj48YnI+PGJyPg0KDQoNCg0KYGBge3Igc2V0dXAsIGluY2x1ZGU9RkFMU0V9DQprbml0cjo6b3B0c19jaHVuayRzZXQoZWNobyA9IFRSVUUpDQpgYGANCg0KIyAxLiBEZXNrcmlwc2kNCg0KSW4gdGhlIHByZXZpb3VzIGNoYXB0ZXIsIHRoZSBrbm93bGVkZ2Ugb2YgYm90aCB0aGUgZ2VuZXJhdGl2ZSBtb2RlbCBhbmQgdGhlIHZhbHVlcyBvZiB0aGUgcGFyYW1ldGVycyBwcm92aWRlZCB1cyB3aXRoIHByb2JhYmlsaXRpZXMgd2UgY291bGQgdXNlIGZvciBkZWNpc2lvbiBtYWtpbmcg4oCTIGZvciBpbnN0YW5jZSwgd2hldGhlciB3ZSBoYWQgcmVhbGx5IGZvdW5kIGFuIGVwaXRvcGUuIEluIG1hbnkgcmVhbCBzaXR1YXRpb25zLCBuZWl0aGVyIHRoZSBnZW5lcmF0aXZlIG1vZGVsIG5vciB0aGUgcGFyYW1ldGVycyBhcmUga25vd24sIGFuZCB3ZSB3aWxsIG5lZWQgdG8gZXN0aW1hdGUgdGhlbSB1c2luZyB0aGUgZGF0YSB3ZSBoYXZlIGNvbGxlY3RlZC4gU3RhdGlzdGljYWwgbW9kZWxpbmcgd29ya3MgZnJvbSB0aGUgZGF0YSB1cHdhcmRzIHRvIGEgbW9kZWwgdGhhdCBtaWdodCBwbGF1c2libHkgZXhwbGFpbiB0aGUgZGF0YTIxMjEgRXZlbiBpZiB3ZSBoYXZlIGZvdW5kIGEgbW9kZWwgdGhhdCBwZXJmZWN0bHkgZXhwbGFpbnMgYWxsIG91ciBjdXJyZW50IGRhdGEsIGl0IGNvdWxkIGFsd2F5cyBiZSB0aGF0IHJlYWxpdHkgaXMgbW9yZSBjb21wbGV4LiBBIG5ldyBzZXQgb2YgZGF0YSBsZXRzIHVzIGNvbmNsdWRlIHRoYXQgYW5vdGhlciBtb2RlbCBpcyBuZWVkZWQsIGFuZCBtYXkgaW5jbHVkZSB0aGUgY3VycmVudCBtb2RlbCBhcyBhIHNwZWNpYWwgY2FzZSBvciBhcHByb3hpbWF0aW9uLi4gVGhpcyB1cHdhcmQtcmVhc29uaW5nIHN0ZXAgaXMgY2FsbGVkIHN0YXRpc3RpY2FsIGluZmVyZW5jZS4gVGhpcyBjaGFwdGVyIHdpbGwgc2hvdyB1cyBzb21lIG9mIHRoZSBkaXN0cmlidXRpb25zIGFuZCBlc3RpbWF0aW9uIG1lY2hhbmlzbXMgdGhhdCBzZXJ2ZSBhcyBidWlsZGluZyBibG9ja3MgZm9yIGluZmVyZW5jZS4gQWx0aG91Z2ggdGhlIGV4YW1wbGVzIGluIHRoaXMgY2hhcHRlciBhcmUgYWxsIHBhcmFtZXRyaWMgKGkuZS4sIHRoZSBzdGF0aXN0aWNhbCBtb2RlbHMgb25seSBoYXZlIGEgc21hbGwgbnVtYmVyIG9mIHVua25vd24gcGFyYW1ldGVycyksIHRoZSBwcmluY2lwbGVzIHdlIGRpc2N1c3Mgd2lsbCBnZW5lcmFsaXplLg0KDQojIDIuIEEgc2ltcGxlIGV4YW1wbGUgb2Ygc3RhdGlzdGljYWwgbW9kZWxpbmcNCg0KVGhlIG5vcm1hbCBkaXN0cmlidXRpb24sIG9yIGJlbGwgc2hhcGVkIGN1cnZlLCBpcyBvZnRlbiBhIGdvb2QgbW9kZWwgZm9yIGNvbnRpbnVvdXMgbWVhc3VyZW1lbnRzLiBEaXN0cmlidXRpb25zIGNhbiBhbHNvIGJlIG1vcmUgY29tcGxpY2F0ZWQgbWl4dHVyZXMgb2YgdGhlc2UgZWxlbWVudGFyeSBvbmVzLg0KDQpMZXTigJlzIHJldmlzaXQgdGhlIGVwaXRvcGUgZXhhbXBsZSBmcm9tIHRoZSBwcmV2aW91cyBjaGFwdGVyLCBzdGFydGluZyB3aXRob3V0IHRoZSB0cmlja3kgb3V0bGllci4NCg0KYGBge3J9DQpsb2FkKCIuLi9Eb2N1bWVudHMvZGF0YS9kYXRhL2UxMDAuUkRhdGEiKQ0KZTk5ID0gZTEwMFstd2hpY2gubWF4KGUxMDApXQ0KYmFycGxvdCh0YWJsZShlOTkpLCBzcGFjZSA9IDAuOCwgY29sID0gImNoYXJ0cmV1c2U0IikNCmBgYA0KYGBge3J9DQpsaWJyYXJ5KCJ2Y2QiKQ0KZ2YxID0gZ29vZGZpdCggZTk5LCAicG9pc3NvbiIpDQpyb290b2dyYW0oZ2YxLCB4bGFiID0gIiIsIHJlY3RfZ3AgPSBncGFyKGZpbGwgPSAiY2hhcnRyZXVzZTQiKSkNCmBgYA0KDQojIDMuICBFc3RpbWF0aW5nIHRoZSBwYXJhbWV0ZXIgb2YgdGhlIFBvaXNzb24gZGlzdHJpYnV0aW9uDQoNCldoYXQgdmFsdWUgZm9yIHRoZSBQb2lzc29uIG1lYW4gbWFrZXMgdGhlIGRhdGEgdGhlIG1vc3QgcHJvYmFibGU/IEluIGEgZmlyc3Qgc3RlcCwgd2UgdGFsbHkgdGhlIG91dGNvbWVzLg0KYGBge3J9DQp0YWJsZShlMTAwKQ0KYGBgDQpgYGB7cn0NCnRhYmxlKHJwb2lzKDEwMCwgMykpDQpgYGANCmBgYHtyfQ0KcHJvZChkcG9pcyhjKDAsIDEsIDIsIDcpLCBsYW1iZGEgPSAzKSBeIChjKDU4LCAzNCwgNywgMSkpKQ0KYGBgDQpgYGB7cn0NCmxvZ2xpa2VsaWhvb2QgID0gIGZ1bmN0aW9uKGxhbWJkYSwgZGF0YSA9IGUxMDApIHsNCiAgc3VtKGxvZyhkcG9pcyhkYXRhLCBsYW1iZGEpKSkNCn0NCmBgYA0KTm93IHdlIGNhbiBjb21wdXRlIHRoZSBsaWtlbGlob29kIGZvciBhIHdob2xlIHNlcmllcyBvZiBsYW1iZGEgdmFsdWVzIGZyb20gMC4wNSB0byAwLjk1DQpgYGB7cn0NCmxhbWJkYXMgPSBzZXEoMC4wNSwgMC45NSwgbGVuZ3RoID0gMTAwKQ0KbG9nbGlrID0gdmFwcGx5KGxhbWJkYXMsIGxvZ2xpa2VsaWhvb2QsIG51bWVyaWMoMSkpDQpwbG90KGxhbWJkYXMsIGxvZ2xpaywgdHlwZSA9ICJsIiwgY29sID0gInJlZCIsIHlsYWIgPSAiIiwgbHdkID0gMiwNCiAgICAgeGxhYiA9IGV4cHJlc3Npb24obGFtYmRhKSkNCm0wID0gbWVhbihlMTAwKQ0KYWJsaW5lKHYgPSBtMCwgY29sID0gImJsdWUiLCBsd2QgPSAyKQ0KYWJsaW5lKGggPSBsb2dsaWtlbGlob29kKG0wKSwgY29sID0gInB1cnBsZSIsIGx3ZCA9IDIpDQptMA0KYGBgDQpgYGB7cn0NCmdmICA9ICBnb29kZml0KGUxMDAsICJwb2lzc29uIikNCm5hbWVzKGdmKQ0KYGBgDQpgYGB7cn0NCmdmJHBhcg0KYGBgDQpgYGB7cn0NCmdmJG9ic2VydmVkDQpgYGANCmBgYHtyfQ0KZ2YkZml0dGVkDQpgYGANCmBgYHtyfQ0KZ2YkdHlwZQ0KYGBgDQoNCiMgNC4gIENsYXNzaWNhbCBzdGF0aXN0aWNzIGZvciBjbGFzc2ljYWwgZGF0YQ0KDQpgYGB7cn0NCmNiIDwtIHJiaW5vbSgxMjAsIHByb2IgPSAwLjgsIHNpemUgPSAxKQ0KY2INCmBgYA0KYGBge3J9DQp0YWJsZShjYikNCmBgYA0KYGBge3J9DQpwcm9icyAgPSAgc2VxKDAsIDAuMywgYnkgPSAwLjAwNSkNCmxpa2VsaWhvb2QgPSBkYmlub20oc3VtKGNiKSwgcHJvYiA9IHByb2JzLCBzaXplID0gbGVuZ3RoKGNiKSkNCnBsb3QocHJvYnMsIGxpa2VsaWhvb2QsIHBjaCA9IDE2LCB4bGFiID0gInByb2JhYmlsaXR5IG9mIHN1Y2Nlc3MiLA0KICAgICAgIHlsYWIgPSAibGlrZWxpaG9vZCIsIGNleD0wLjYpDQpwcm9ic1t3aGljaC5tYXgobGlrZWxpaG9vZCldDQpgYGANCkhlcmXigJlzIGEgZnVuY3Rpb24gd2UgdXNlIHRvIGNhbGN1bGF0ZSBpdDoNCg0KYGBge3J9DQpsb2dsaWtlbGlob29kID0gZnVuY3Rpb24odGhldGEsIG4gPSAzMDAsIGsgPSA0MCkgew0KICAxMTUgKyBrICogbG9nKHRoZXRhKSArIChuIC0gaykgKiBsb2coMSAtIHRoZXRhKQ0KfQ0KYGBgDQp3aGljaCB3ZSBwbG90IGZvciB0aGUgcmFuZ2Ugb2YgzrggZnJvbSAwIHRvIDEgKEZpZ3VyZSAyLjYpLg0KDQpgYGB7cn0NCnRoZXRhcyA9IHNlcSgwLCAxLCBieSA9IDAuMDAxKQ0KcGxvdCh0aGV0YXMsIGxvZ2xpa2VsaWhvb2QodGhldGFzKSwgeGxhYiA9IGV4cHJlc3Npb24odGhldGEpLA0KICB5bGFiID0gZXhwcmVzc2lvbihwYXN0ZSgibG9nIGYoIiwgdGhldGEsICIgfCB5KSIpKSx0eXBlID0gImwiKQ0KYGBgDQoNCiMgNS4gIE1vcmUgYm94ZXM6bXVsdGlub21pYWwgZGF0YQ0KDQpETkEgY291bnQgbW9kZWxpbmc6IGJhc2UgcGFpcnMNClRoaXMgc2VjdGlvbiBjb21iaW5lcyBlc3RpbWF0aW9uIGFuZCB0ZXN0aW5nIGJ5IHNpbXVsYXRpb24gaW4gYSByZWFsIGV4YW1wbGUuIERhdGEgZnJvbSBvbmUgc3RyYW5kIG9mIEROQSBmb3IgdGhlIGdlbmVzIG9mIFN0YXBoeWxvY29jY3VzIGF1cmV1cyBiYWN0ZXJpdW0gYXJlIGF2YWlsYWJsZSBpbiBhIGZhc3RhIGZpbGUgc3RhcGhzZXF1ZW5jZS5mZm4udHh0LCB3aGljaCB3ZSBjYW4gcmVhZCB3aXRoIGEgZnVuY3Rpb24gZnJvbSB0aGUgQmlvY29uZHVjdG9yIHBhY2thZ2UgQmlvc3RyaW5ncy4NCg0KYGBge3J9DQpsaWJyYXJ5KCJCaW9zdHJpbmdzIikNCnN0YXBoID0gcmVhZEROQVN0cmluZ1NldCgiLi4vRG9jdW1lbnRzL2RhdGEvZGF0YS9zdGFwaHNlcXVlbmNlLmZmbi50eHQiLCAiZmFzdGEiKQ0KYGBgDQpgYGB7cn0NCmxldHRlckZyZXF1ZW5jeShzdGFwaFtbMV1dLCBsZXR0ZXJzID0gIkFDR1QiLCBPUiA9IDApDQpgYGANCmBgYHtyfQ0KbGV0dGVyRnJxID0gdmFwcGx5KHN0YXBoLCBsZXR0ZXJGcmVxdWVuY3ksIEZVTi5WQUxVRSA9IG51bWVyaWMoNCksDQogICAgICAgICBsZXR0ZXJzID0gIkFDR1QiLCBPUiA9IDApDQpjb2xuYW1lcyhsZXR0ZXJGcnEpID0gcGFzdGUwKCJnZW5lIiwgc2VxKGFsb25nID0gc3RhcGgpKQ0KdGFiMTAgPSBsZXR0ZXJGcnFbLCAxOjEwXQ0KY29tcHV0ZVByb3BvcnRpb25zID0gZnVuY3Rpb24oeCkgeyB4L3N1bSh4KSB9DQpwcm9wMTAgPSBhcHBseSh0YWIxMCwgMiwgY29tcHV0ZVByb3BvcnRpb25zKQ0Kcm91bmQocHJvcDEwLCBkaWdpdHMgPSAyKQ0KYGBgDQpgYGB7cn0NCnAwID0gcm93TWVhbnMocHJvcDEwKQ0KcDANCmBgYA0KYGBge3J9DQpjcyA9IGNvbFN1bXModGFiMTApDQpjcw0KYGBgDQpgYGB7cn0NCmV4cGVjdGVkdGFiMTAgPSBvdXRlcihwMCwgY3MsIEZVTiA9ICIqIikNCnJvdW5kKGV4cGVjdGVkdGFiMTApDQpgYGANCmBgYHtyfQ0KcmFuZG9tdGFiMTAgPSBzYXBwbHkoY3MsIGZ1bmN0aW9uKHMpIHsgcm11bHRpbm9tKDEsIHMsIHAwKSB9ICkNCmFsbChjb2xTdW1zKHJhbmRvbXRhYjEwKSA9PSBjcykNCmBgYA0KTm93IHdlIHJlcGVhdCB0aGlzIEIgPSAxMDAwIHRpbWVzLiBGb3IgZWFjaCB0YWJsZSB3ZSBjb21wdXRlIG91ciB0ZXN0IHN0YXRpc3RpYyBmcm9tIFNlY3Rpb24gMS40LjEgaW4gQ2hhcHRlciAxICh0aGUgZnVuY3Rpb24gc3RhdCkgYW5kIHN0b3JlIHRoZSByZXN1bHRzIGluIHRoZSB2ZWN0b3Igc2ltdWxzdGF0LiBUb2dldGhlciwgdGhlc2UgdmFsdWVzIGNvbnN0aXR1dGUgb3VyIG51bGwgZGlzdHJpYnV0aW9uLCBhcyB0aGV5IHdlcmUgZ2VuZXJhdGVkIHVuZGVyIHRoZSBudWxsIGh5cG90aGVzaXMgdGhhdCBwMCBpcyB0aGUgdmVjdG9yIG9mIG11bHRpbm9taWFsIHByb3BvcnRpb25zIGZvciBlYWNoIG9mIHRoZSAxMCBnZW5lcy4NCg0KYGBge3J9DQpzdGF0ID0gZnVuY3Rpb24ob2JzdmQsIGV4cHRkID0gMjAgKiBwdmVjKSB7DQogICBzdW0oKG9ic3ZkIC0gZXhwdGQpXjIgLyBleHB0ZCkNCn0NCkIgPSAxMDAwDQpzaW11bHN0YXQgPSByZXBsaWNhdGUoQiwgew0KICByYW5kb210YWIxMCA9IHNhcHBseShjcywgZnVuY3Rpb24ocykgeyBybXVsdGlub20oMSwgcywgcDApIH0pDQogIHN0YXQocmFuZG9tdGFiMTAsIGV4cGVjdGVkdGFiMTApDQp9KQ0KUzEgPSBzdGF0KHRhYjEwLCBleHBlY3RlZHRhYjEwKQ0Kc3VtKHNpbXVsc3RhdCA+PSBTMSkNCmBgYA0KYGBge3J9DQpoaXN0KHNpbXVsc3RhdCwgY29sID0gImxhdmVuZGVyIiwgYnJlYWtzID0gc2VxKDAsIDc1LCBsZW5ndGgub3V0PTUwKSkNCmFibGluZSh2ID0gUzEsIGNvbCA9ICJyZWQiKQ0KYWJsaW5lKHYgPSBxdWFudGlsZShzaW11bHN0YXQsIHByb2JzID0gYygwLjk1LCAwLjk5KSksDQogICAgICAgY29sID0gYygiZGFya2dyZWVuIiwgImJsdWUiKSwgbHR5ID0gMikNCmBgYA0K