Introduction

In this notebook I am going to fit a Bayesian SIR model in JAGS. Some of this material is a simplification of the more advanced spatial SEIRS model found in this thesis by Grant Brown from 2015 which is well worth reading. Another very useful paper is Lekone and Finkelstadt which has no spatial aspect, and is the majority of what is re-created here. I have changed the notation to what I believe is a clearer version.

The main idea is to simplify the differential equations of the SIR model into difference equations and then use probability distributions and transmission matrices to quantify uncertainties between compartments. All time is treated as discrete, which is fine for current COVID-19 data which is almost all available at a daily time step. In another document I will extend this model to SEIR, and further a spatial or stratified type model. It may be possible to fit a similar model in Stan but this would require integrating out many of the discrete parameters.

Notation

First data:

Now latent variables:

Some parameters:

Some extra parameters are derived:

Model

The model equations are given by: \[S(t+1) = S(t) - N_{S \rightarrow I}(t)\] \[I(t+1) = I(t) + N_{S \rightarrow I}(t) - N_{I \rightarrow R}(t)\] \[S(t) + I(t) + R(t) = N\]

In English these equations mean:

Each of the latent variables is given a binomial distribution

\[N_{S \rightarrow I}(t) \sim Bin(S(t), p_{S \rightarrow I}(t))\] \[N_{I \rightarrow R}(t) \sim Bin(I(t), p_{I \rightarrow R})\]

In words these equations mean:

These probabilities are set at

\[p_{S \rightarrow I}(t) = 1 - \exp \left( - \beta \right)\] This equation makes the proportion of people moving from susceptible to infected dependent on the proportion of people who are infected (\(I(t)/N\)), i.e. the greater the proportion of people infected, the fewer can become infected.

\[p_{I \rightarrow R} = 1 - \exp( - \gamma)\] where

One of the key parameters to estimate is the basic reproduction number which is defined as \(R_0\) or \(\beta / \gamma\) in this notation. This model has the cool feature that we can estimate a time dependent reproduction number as:

\[ R_0(t) = \frac{\beta}{\gamma}\]

Ideally, the data for this model would be \(N, N_{S \rightarrow I}(t), N_{I \rightarrow R}(t)\), the latter three for all time values. In fact we often do not have access to \(N_{S \rightarrow I}(t)\) (the number of susceptible individuals who become infected) so we may need to integrate out these values during the Bayesian model.

JAGS model

Below is some code for a JAGS model:

jags_code = '
model {
  # Likelihood
  for (t in 1:T) {
    N_I_R[t] ~ dbinom(p_I_R, I[t])
    N_S_I[t] ~ dbinom(p_S_I, S[t])
  }

  # These are the known time evolution steps:
  for(t in 2:T) {
    S[t] <- S[t-1] - N_S_I[t-1]
    I[t] <- I[t-1] + N_S_I[t-1] - N_I_R[t-1]
    R[t] <- N - S[t] - I[t]
  }

  # Need a value for S[1] and I[1]
  I[1] <- I_start # Assume the number of people infected on day 1 is the same as those transitioning from E to I
  R[1] <- R_start # As above but for removed
  S[1] <- N - I[1] - R[1] # Left over

  # Probabilities and R_0  
  p_S_I <- 1 - exp( - beta )
  p_I_R <- 1 - exp( -gamma )
  R_0 <- (beta/gamma)

  # Now the prior on the hyper-parameters
  beta ~ dunif(0.3, 1) #= 0.6
  gamma <- 1/gamma_inv
  gamma_inv ~ dunif(6, 12) # 10

  # Can now forecast into the future
  for (t in (T+1):T_max) {
  
    # Transitions
    N_I_R[t] ~ dbinom(p_I_R, I[t])
    N_S_I[t] ~ dbinom(p_S_I, S[t])
    
    # Compartment values
    S[t] <- S[t-1] - N_S_I[t-1]
    I[t] <- I[t-1] + N_S_I[t-1] - N_I_R[t-1]
    R[t] = N - S[t] - I[t]
  }
}
'

Fit to simulated data

I will first try simulating some data from this model and checking that JAGS actually works.

# Summary values
N = 1000 # Population size
T = 30 # Maximum time steps
t = 1:T

# First the hyper-parameters
gamma_inv = 10; gamma = 1/gamma_inv
beta = 0.6

# Now the probabilities
p_I_R = 1 - exp(-gamma)
p_S_I = 1 - exp(-beta)

# Give an initial values for everthing required
N_S_I = N_I_R = S = I = R = rep(NA, T)

S[1] = N - 10; I[1] = 10; R[1] = 0
N_S_I[1] = rbinom(1, S[1], p_S_I)
N_I_R[1] = rbinom(1, I[1], p_I_R)

# Now can loop through filling in the other values
for (t in 2:T) {
  S[t] <- S[t-1] - N_S_I[t-1]
  I[t] <- I[t-1] + N_S_I[t-1] - N_I_R[t-1]
  R[t] = N - S[t] - I[t] 

  # Now get the actual values
  N_I_R[t] = rbinom(1, I[t], p_I_R)
  # These are usually imputed:
  N_S_I[t] = rbinom(1, S[t], p_S_I)
}

# Create R0
R_0 = (beta/gamma)

# Create a plot of the epidemic
library(ggplot2)
library(tidyr)
tibble(t = 1:T,
       S, I, R) %>%
  pivot_longer(names_to = 'Compartment', values_to = 'People', -t) %>%
  ggplot(aes(x = t, y = People, colour = Compartment)) +
  #scale_y_log10() +
  geom_line()

Now we can fit this model by providing the data to JAGS

Now plot the number of infected over time:

S_post = jags_run$BUGSoutput$median$S
I_post = jags_run$BUGSoutput$median$I
R_post = jags_run$BUGSoutput$median$R

tibble(t = 1:T_max,
  S_post, I_post, R_post) %>%
  pivot_longer(names_to = 'Compartment', values_to = 'People', -t) %>%
  ggplot(aes(x = t, y = People, colour = Compartment)) +
  geom_line()

Now plot the parameter estimates against their true values

post = jags_run$BUGSoutput$sims.list
tibble(iter = 1:length(post$beta),
       beta = post$beta,
       gamma_inv = post$gamma_inv,
       R0 = post$R_0) %>%
  pivot_longer(names_to = 'Type', values_to = 'Sample',-iter) %>%
  ggplot(aes(x = Sample, fill = Type)) +
  geom_histogram(bins = 30) +
  facet_wrap(~ Type, scales = 'free') +
  geom_vline(data = tibble(iter = rep(1, 3),
                           Sample = c(beta, gamma_inv, R_0),
                           Type = c('beta', 'gamma_inv', 'R0')),
             aes(xintercept = Sample)) +
  theme(legend.position = 'None')

All values seem to match, depending on whether you give it the number of cases (\(N_{S \rightarrow I}\)) or not.

LS0tCnRpdGxlOiAiQSBCYXllc2lhbiBTSVIgbW9kZWwgaW4gSkFHUyIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKYGBge3IsIGVjaG8gPSBGQUxTRSwgaW5jbHVkZT0gRkFMU0V9CnJtKGxpc3QgPSBscygpKQpzZXQuc2VlZCgxMDIpCmBgYAoKCiMjIyBJbnRyb2R1Y3Rpb24KCkluIHRoaXMgbm90ZWJvb2sgSSBhbSBnb2luZyB0byBmaXQgYSBCYXllc2lhbiBTSVIgbW9kZWwgaW4gSkFHUy4gU29tZSBvZiB0aGlzIG1hdGVyaWFsIGlzIGEgc2ltcGxpZmljYXRpb24gb2YgdGhlIG1vcmUgYWR2YW5jZWQgc3BhdGlhbCBTRUlSUyBtb2RlbCBmb3VuZCBpbiB0aGlzIFt0aGVzaXNdKGh0dHBzOi8vaXIudWlvd2EuZWR1L2V0ZC8xNTU0LykgYnkgR3JhbnQgQnJvd24gZnJvbSAyMDE1IHdoaWNoIGlzIHdlbGwgd29ydGggcmVhZGluZy4gQW5vdGhlciB2ZXJ5IHVzZWZ1bCBwYXBlciBpcyBbTGVrb25lIGFuZCBGaW5rZWxzdGFkdF0oaHR0cHM6Ly9vbmxpbmVsaWJyYXJ5LndpbGV5LmNvbS9kb2kvZnVsbC8xMC4xMTExL2ouMTU0MS0wNDIwLjIwMDYuMDA2MDkueD9jYXNhX3Rva2VuPV8zQ0t0ZHZVeEFnQUFBQUE6NzRlMXRJcVNvQ0ZRbEU2azhXbWFDamMxc2hCTU1JZTQzNW83dUYzNlFMa1B3LWtQZUpxekx3QzRaQjBMQ0lwbmg4Y05ETE0tTzJVTFpxUSkgd2hpY2ggaGFzIG5vIHNwYXRpYWwgYXNwZWN0LCBhbmQgaXMgdGhlIG1ham9yaXR5IG9mIHdoYXQgaXMgcmUtY3JlYXRlZCBoZXJlLiBJIGhhdmUgY2hhbmdlZCB0aGUgbm90YXRpb24gdG8gd2hhdCBJIGJlbGlldmUgaXMgYSBjbGVhcmVyIHZlcnNpb24uCgpUaGUgbWFpbiBpZGVhIGlzIHRvIHNpbXBsaWZ5IHRoZSBkaWZmZXJlbnRpYWwgZXF1YXRpb25zIG9mIHRoZSBTSVIgbW9kZWwgaW50byBkaWZmZXJlbmNlIGVxdWF0aW9ucyBhbmQgdGhlbiB1c2UgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9ucyBhbmQgdHJhbnNtaXNzaW9uIG1hdHJpY2VzIHRvIHF1YW50aWZ5IHVuY2VydGFpbnRpZXMgYmV0d2VlbiBjb21wYXJ0bWVudHMuIEFsbCB0aW1lIGlzIHRyZWF0ZWQgYXMgZGlzY3JldGUsIHdoaWNoIGlzIGZpbmUgZm9yIGN1cnJlbnQgQ09WSUQtMTkgZGF0YSB3aGljaCBpcyBhbG1vc3QgYWxsIGF2YWlsYWJsZSBhdCBhIGRhaWx5IHRpbWUgc3RlcC4gSW4gYW5vdGhlciBkb2N1bWVudCBJIHdpbGwgZXh0ZW5kIHRoaXMgbW9kZWwgdG8gU0VJUiwgYW5kIGZ1cnRoZXIgYSBzcGF0aWFsIG9yIHN0cmF0aWZpZWQgdHlwZSBtb2RlbC4gSXQgbWF5IGJlIHBvc3NpYmxlIHRvIGZpdCBhIHNpbWlsYXIgbW9kZWwgaW4gU3RhbiBidXQgdGhpcyB3b3VsZCByZXF1aXJlIGludGVncmF0aW5nIG91dCBtYW55IG9mIHRoZSBkaXNjcmV0ZSBwYXJhbWV0ZXJzLiAKCiMjIyBOb3RhdGlvbgoKRmlyc3QgZGF0YToKCi0gTGV0ICR0JCBiZSB0aW1lIGZvciAkdCA9IDEsIFxsZG90cywgVCQgd2l0aCBhbGwgdGltZSBwb2ludHMga25vd24gYW5kIGVxdWFsbHkgc3BhY2VkLiAKLSBMZXQgJE4kIGJlIHRoZSBwb3B1bGF0aW9uIHNpemUKLSBMZXQgJE5fe1MgXHJpZ2h0YXJyb3cgSX0odCkkIGJlIHRoZSBudW1iZXIgb2Ygc3VzY2VwdGlibGUgcGVvcGxlIHdobyBnZXQgaW5mZWN0ZWQgYXQgdGltZSAkdCQuIFRoaXMsIGlmIGtub3duLCBpcyB0aGUgbnVtYmVyIG9mIGNhc2VzIGF0IHRpbWUgJHQkLgotIExldCAkTl97SSBccmlnaHRhcnJvdyBSfSh0KSQgYmUgdGhlIG51bWJlciBvZiBpbmZlY3RlZCBwZW9wbGUgd2hvIGFyZSByZW1vdmVkIChkaWVkIG9yIHJlY292ZXJlZCkgYXQgdGltZSAkdCQuIFdlIGhhdmUgYSAobGlrZWx5IHJlYXNvbmFibGUpIGVzdGltYXRlIG9mIHRoZSBudW1iZXIgb2YgcGVvcGxlIHdobyBoYXZlIGRpZWQgYXQgdGltZSAkdCQgKG9yIGF0IGxlYXN0IGJlZm9yZSB0aW1lICR0JCkgYnV0IGEgbXVjaCBwb29yZXIgZXN0aW1hdGUgb2YgdGhlIG51bWJlciB3aG8gaGF2ZSByZWNvdmVyZWQuIFRoZSBsYXR0ZXIgaXMgcmVwb3J0ZWQgYnkgSm9obiBIb3BraW5zIGJ1dCBsaWtlbHkgdG8gYmUgYSBtYXNzaXZlIHVuZGVyLWVzdGltYXRlLCBvciBiYXNlZCBvbiBxdWl0ZSBzdHJpY3QgYXNzdW1wdGlvbnMgb2YgZGlzZWFzZSBsZW5ndGguCgpOb3cgbGF0ZW50IHZhcmlhYmxlczoKCi0gTGV0ICRTKHQpJCBiZSB0aGUgbnVtYmVyIG9mIHN1c2NlcHRpYmxlIGluZGl2aWR1YWxzIGF0IHRpbWUgJHQkIHdpdGggc3RhcnRpbmcgdmFsdWUgJFMoMSkkCi0gTGV0ICRJKHQpJCBiZSB0aGUgbnVtYmVyIG9mIGluZmVjdGVkIGluZGl2aWR1YWxzIGF0IHRpbWUgJHQkIHdpdGggc3RhcnRpbmcgdmFsdWUgJEkoMSkkCi0gTGV0ICRSKHQpJCBiZSB0aGUgbnVtYmVyIG9mIHJlbW92ZWQgaW5kaXZpZHVhbHMgYXQgdGltZSAkdCQgd2l0aCBzdGFydGluZyB2YWx1ZSAkUigxKSQKClNvbWUgcGFyYW1ldGVyczoKCi0gJFxiZXRhJCBpcyB0aGUgYmFzZSB0cmFuc21pc3Npb24gcmF0ZSwgaS5lLiB0aGUgcmF0ZSBhdCB3aGljaCBzdXNjZXB0aWJsZSBpbmRpdmlkdWFscyBiZWNvbWUgaW5mZWN0ZWQKLSAkXGdhbW1hJCBpcyBhIHBhcmFtZXRlciB0aGF0IGNvbnRyb2xzIHRoZSByYXRlIGF0IHdoaWNoIGluZmVjdGVkIGluZGl2aWR1YWxzIGFyZSByZW1vdmVkLiBJIHRoaW5rIHRoZSBpbnZlcnNlIG9mIHRoaXMgaXMgdGhlIG1lYW4gbnVtYmVyIG9mIGRheXMgYmVmb3JlIGFuIGluZmVjdGVkIGluZGl2aWR1YWwgYmVjb21lcyByZW1vdmVkCgpTb21lIGV4dHJhIHBhcmFtZXRlcnMgYXJlIGRlcml2ZWQ6CgotIExldCAkUl8wJCAob3IgJFJfMCh0KSQpIGJlIHRoZSBiYXNpYyByZXByb2R1Y3Rpb24gbnVtYmVyLCBwb3NzaWJseSBjaGFuZ2luZyBvdmVyIHRpbWUsIHRoYXQgZGV0ZXJtaW5lcyB0aGUgZXhwZWN0ZWQgbnVtYmVyIG9mIHBlb3BsZSB3aG8gdHVybiBpbmZlY3Rpb3VzIGZyb20gYW4gaW5mZWN0ZWQgcGVyc29uCi0gTGV0ICRcdGF1XiokIGJlIHRoZSB0aW1lIHBvaW50IHdoZW4gdGhlIGVwaWRlbWljIGdvZXMgZXh0aW5jdCwgaS5lLiB3aGVuIHRoZXJlIGFyZSBubyBtb3JlIGluZmVjdGVkIGluZGl2aWR1YWxzIGxlZnQKCiMjIyBNb2RlbAoKVGhlIG1vZGVsIGVxdWF0aW9ucyBhcmUgZ2l2ZW4gYnk6CiQkUyh0KzEpID0gUyh0KSAtIE5fe1MgXHJpZ2h0YXJyb3cgSX0odCkkJAokJEkodCsxKSA9IEkodCkgKyBOX3tTIFxyaWdodGFycm93IEl9KHQpIC0gTl97SSBccmlnaHRhcnJvdyBSfSh0KSQkCiQkUyh0KSArIEkodCkgKyBSKHQpID0gTiQkCgpJbiBFbmdsaXNoIHRoZXNlIGVxdWF0aW9ucyBtZWFuOgoKICAtIFRoZSBudW1iZXIgb2Ygc3VzY2VwdGlibGUgaW5kaXZpZHVhbHMgYXQgdGltZSAkdCsxJCBpcyBlcXVhbCB0byB0aGUgcHJldmlvdXMgbnVtYmVyIG9mIHN1c2NlcHRpYmxlIGluZGl2aWR1YWxzIGxlc3MgdGhlIG51bWJlciBvZiBwZW9wbGUgd2hvIHdlcmUgc3VzY2VwdGlibGUgYnV0IG5vdyBpbmZlY3RlZCBhdCB0aW1lICR0JAogIC0gVGhlIG51bWJlciBvZiBpbmZlY3RlZCBwZW9wbGUgYXQgdGltZSAkdCsxJCBpcyB0aGUgbnVtYmVyIG9mIGluZmVjdGVkIHBlb3BsZSBhdCB0aW1lICR0JCBwbHVzIHRoZSBudW1iZXIgb2YgcGVvcGxlIHdobyBtb3ZlIGZyb20gc3VzY2VwdGlibGUgdG8gaW5mZWN0ZWQgYXQgdGltZSAkdCQgbGVzcyB0aGUgbnVtYmVyIG9mIHJlbW92ZWQgaW5kaXZpZHVhbHMgd2hvIGhhdmUgbW92ZWQgZnJvbSBleHBvc2VkIHRvIHJlbW92ZWQuIAogIC0gVGhlIHRvdGFsIG51bWJlciBvZiBwZW9wbGUgaW4gZWFjaCBjb21wYXJ0bWVudCBpcyBhbHdheXMgZXF1YWwgdG8gdGhlIHBvcHVsYXRpb24gc2l6ZQoKRWFjaCBvZiB0aGUgbGF0ZW50IHZhcmlhYmxlcyBpcyBnaXZlbiBhIGJpbm9taWFsIGRpc3RyaWJ1dGlvbgoKJCROX3tTIFxyaWdodGFycm93IEl9KHQpIFxzaW0gQmluKFModCksIHBfe1MgXHJpZ2h0YXJyb3cgSX0odCkpJCQKJCROX3tJIFxyaWdodGFycm93IFJ9KHQpIFxzaW0gQmluKEkodCksIHBfe0kgXHJpZ2h0YXJyb3cgUn0pJCQKCkluIHdvcmRzIHRoZXNlIGVxdWF0aW9ucyBtZWFuOgoKLSBUaGUgbnVtYmVyIG9mIHN1c2NlcHRpYmxlIHBlb3BsZSB3aG8gZ2V0IGluZmVjdGVkIGF0IHRpbWUgJHQkIGlzIGEgYmlub21pYWwgZGlzdHJpYnV0aW9uIHdpdGggbWF4aW11bSB2YWx1ZSAkUyh0KSQgYW5kIHRpbWUtZGVwZW5kZW50IHByb2JhYmlsaXR5ICRwX3tTIFxyaWdodGFycm93IEl9KHQpJC4gVGhpcyBtZWFucyB0aGF0IHRoZSBudW1iZXIgb2YgcGVvcGxlIG1vdmluZyBmcm9tIHN1c2NlcHRpYmxlIHRvIGluZmVjdGVkIGF0IHRpbWUgJHQkIGhhcyB0byBiZSBhIGZyYWN0aW9uIG9mIHRoZSB0b3RhbCBudW1iZXIgb2Ygc3VzY2VwdGlibGUgaW5kaXZpZHVhbHMKLSBUaGUgbnVtYmVyIG9mIGluZmVjdGVkIGluZGl2aWR1YWxzIHdobyBnZXQgcmVtb3ZlZCBhdCB0aW1lICR0JCBpcyBhIGJpbm9taWFsIGRpc3RyaWJ1dGlvbiB3aXRoIG1heGltdW0gdmFsdWUgJEkodCkkIGFuZCBwcm9iYWJpbGl0eSAkcF97SSBccmlnaHRhcnJvdyBSfSQuIFRoaXMgbWVhbnMgdGhhdCB0aGUgbnVtYmVyIG9mIHBlb3BsZSB3aG8gZ2V0IHJlbW92ZWQgYXQgdGltZSAkdCQgaXMgYSBmcmFjdGlvbiBvZiB0aGUgbnVtYmVyIG9mIHBlb3BsZSB3aG8gYXJlIGluZmVjdGVkIGF0IHRpbWUgJHQkCgpUaGVzZSBwcm9iYWJpbGl0aWVzIGFyZSBzZXQgYXQKCiQkcF97UyBccmlnaHRhcnJvdyBJfSh0KSA9IDEgLSBcZXhwIFxsZWZ0KCAtIFxiZXRhIFxyaWdodCkkJApUaGlzIGVxdWF0aW9uIG1ha2VzIHRoZSBwcm9wb3J0aW9uIG9mIHBlb3BsZSBtb3ZpbmcgZnJvbSBzdXNjZXB0aWJsZSB0byBpbmZlY3RlZCBkZXBlbmRlbnQgb24gdGhlIHByb3BvcnRpb24gb2YgcGVvcGxlIHdobyBhcmUgaW5mZWN0ZWQgKCRJKHQpL04kKSwgaS5lLiB0aGUgZ3JlYXRlciB0aGUgcHJvcG9ydGlvbiBvZiBwZW9wbGUgaW5mZWN0ZWQsIHRoZSBmZXdlciBjYW4gYmVjb21lIGluZmVjdGVkLiAKCiQkcF97SSBccmlnaHRhcnJvdyBSfSA9IDEgLSBcZXhwKCAtIFxnYW1tYSkkJAp3aGVyZSAKCi0gJFxiZXRhJCBpcyB0aGUgdHJhbnNtaXNzaW9uIHJhdGUKLSAkMS9cZ2FtbWEkIGlzIHRoZSBtZWFuIGluZmVjdGlvdXMgcGVyaW9kCgpPbmUgb2YgdGhlIGtleSBwYXJhbWV0ZXJzIHRvIGVzdGltYXRlIGlzIHRoZSBiYXNpYyByZXByb2R1Y3Rpb24gbnVtYmVyIHdoaWNoIGlzIGRlZmluZWQgYXMgJFJfMCQgb3IgJFxiZXRhIC8gXGdhbW1hJCBpbiB0aGlzIG5vdGF0aW9uLiBUaGlzIG1vZGVsIGhhcyB0aGUgY29vbCBmZWF0dXJlIHRoYXQgd2UgY2FuIGVzdGltYXRlIGEgdGltZSBkZXBlbmRlbnQgcmVwcm9kdWN0aW9uIG51bWJlciBhczogCgokJCBSXzAodCkgPSBcZnJhY3tcYmV0YX17XGdhbW1hfSQkCgpJZGVhbGx5LCB0aGUgZGF0YSBmb3IgdGhpcyBtb2RlbCB3b3VsZCBiZSAkTiwgTl97UyBccmlnaHRhcnJvdyBJfSh0KSwgTl97SSBccmlnaHRhcnJvdyBSfSh0KSQsIHRoZSBsYXR0ZXIgdGhyZWUgZm9yIGFsbCB0aW1lIHZhbHVlcy4gSW4gZmFjdCB3ZSBvZnRlbiBkbyBub3QgaGF2ZSBhY2Nlc3MgdG8gJE5fe1MgXHJpZ2h0YXJyb3cgSX0odCkkICh0aGUgbnVtYmVyIG9mIHN1c2NlcHRpYmxlIGluZGl2aWR1YWxzIHdobyBiZWNvbWUgaW5mZWN0ZWQpIHNvIHdlIG1heSBuZWVkIHRvIGludGVncmF0ZSBvdXQgdGhlc2UgdmFsdWVzIGR1cmluZyB0aGUgQmF5ZXNpYW4gbW9kZWwuCgojIyMgSkFHUyBtb2RlbAoKQmVsb3cgaXMgc29tZSBjb2RlIGZvciBhIEpBR1MgbW9kZWw6CgpgYGB7cn0KamFnc19jb2RlID0gJwptb2RlbCB7CiAgIyBMaWtlbGlob29kCiAgZm9yICh0IGluIDE6VCkgewogICAgTl9JX1JbdF0gfiBkYmlub20ocF9JX1IsIElbdF0pCiAgICBOX1NfSVt0XSB+IGRiaW5vbShwX1NfSSwgU1t0XSkKICB9CgogICMgVGhlc2UgYXJlIHRoZSBrbm93biB0aW1lIGV2b2x1dGlvbiBzdGVwczoKICBmb3IodCBpbiAyOlQpIHsKICAgIFNbdF0gPC0gU1t0LTFdIC0gTl9TX0lbdC0xXQogICAgSVt0XSA8LSBJW3QtMV0gKyBOX1NfSVt0LTFdIC0gTl9JX1JbdC0xXQogICAgUlt0XSA8LSBOIC0gU1t0XSAtIElbdF0KICB9CgogICMgTmVlZCBhIHZhbHVlIGZvciBTWzFdIGFuZCBJWzFdCiAgSVsxXSA8LSBJX3N0YXJ0ICMgQXNzdW1lIHRoZSBudW1iZXIgb2YgcGVvcGxlIGluZmVjdGVkIG9uIGRheSAxIGlzIHRoZSBzYW1lIGFzIHRob3NlIHRyYW5zaXRpb25pbmcgZnJvbSBFIHRvIEkKICBSWzFdIDwtIFJfc3RhcnQgIyBBcyBhYm92ZSBidXQgZm9yIHJlbW92ZWQKICBTWzFdIDwtIE4gLSBJWzFdIC0gUlsxXSAjIExlZnQgb3ZlcgoKICAjIFByb2JhYmlsaXRpZXMgYW5kIFJfMCAgCiAgcF9TX0kgPC0gMSAtIGV4cCggLSBiZXRhICkKICBwX0lfUiA8LSAxIC0gZXhwKCAtZ2FtbWEgKQogIFJfMCA8LSAoYmV0YS9nYW1tYSkKCiAgIyBOb3cgdGhlIHByaW9yIG9uIHRoZSBoeXBlci1wYXJhbWV0ZXJzCiAgYmV0YSB+IGR1bmlmKDAuMywgMSkgIz0gMC42CiAgZ2FtbWEgPC0gMS9nYW1tYV9pbnYKICBnYW1tYV9pbnYgfiBkdW5pZig2LCAxMikgIyAxMAoKICAjIENhbiBub3cgZm9yZWNhc3QgaW50byB0aGUgZnV0dXJlCiAgZm9yICh0IGluIChUKzEpOlRfbWF4KSB7CiAgCiAgICAjIFRyYW5zaXRpb25zCiAgICBOX0lfUlt0XSB+IGRiaW5vbShwX0lfUiwgSVt0XSkKICAgIE5fU19JW3RdIH4gZGJpbm9tKHBfU19JLCBTW3RdKQogICAgCiAgICAjIENvbXBhcnRtZW50IHZhbHVlcwogICAgU1t0XSA8LSBTW3QtMV0gLSBOX1NfSVt0LTFdCiAgICBJW3RdIDwtIElbdC0xXSArIE5fU19JW3QtMV0gLSBOX0lfUlt0LTFdCiAgICBSW3RdID0gTiAtIFNbdF0gLSBJW3RdCiAgfQp9CicKYGBgCgojIyMgRml0IHRvIHNpbXVsYXRlZCBkYXRhCgpJIHdpbGwgZmlyc3QgdHJ5IHNpbXVsYXRpbmcgc29tZSBkYXRhIGZyb20gdGhpcyBtb2RlbCBhbmQgY2hlY2tpbmcgdGhhdCBKQUdTIGFjdHVhbGx5IHdvcmtzLiAKCmBgYHtyfQojIFN1bW1hcnkgdmFsdWVzCk4gPSAxMDAwICMgUG9wdWxhdGlvbiBzaXplClQgPSAzMCAjIE1heGltdW0gdGltZSBzdGVwcwp0ID0gMTpUCgojIEZpcnN0IHRoZSBoeXBlci1wYXJhbWV0ZXJzCmdhbW1hX2ludiA9IDEwOyBnYW1tYSA9IDEvZ2FtbWFfaW52CmJldGEgPSAwLjYKCiMgTm93IHRoZSBwcm9iYWJpbGl0aWVzCnBfSV9SID0gMSAtIGV4cCgtZ2FtbWEpCnBfU19JID0gMSAtIGV4cCgtYmV0YSkKCiMgR2l2ZSBhbiBpbml0aWFsIHZhbHVlcyBmb3IgZXZlcnRoaW5nIHJlcXVpcmVkCk5fU19JID0gTl9JX1IgPSBTID0gSSA9IFIgPSByZXAoTkEsIFQpCgpTWzFdID0gTiAtIDEwOyBJWzFdID0gMTA7IFJbMV0gPSAwCk5fU19JWzFdID0gcmJpbm9tKDEsIFNbMV0sIHBfU19JKQpOX0lfUlsxXSA9IHJiaW5vbSgxLCBJWzFdLCBwX0lfUikKCiMgTm93IGNhbiBsb29wIHRocm91Z2ggZmlsbGluZyBpbiB0aGUgb3RoZXIgdmFsdWVzCmZvciAodCBpbiAyOlQpIHsKICBTW3RdIDwtIFNbdC0xXSAtIE5fU19JW3QtMV0KICBJW3RdIDwtIElbdC0xXSArIE5fU19JW3QtMV0gLSBOX0lfUlt0LTFdCiAgUlt0XSA9IE4gLSBTW3RdIC0gSVt0XSAKCiAgIyBOb3cgZ2V0IHRoZSBhY3R1YWwgdmFsdWVzCiAgTl9JX1JbdF0gPSByYmlub20oMSwgSVt0XSwgcF9JX1IpCiAgIyBUaGVzZSBhcmUgdXN1YWxseSBpbXB1dGVkOgogIE5fU19JW3RdID0gcmJpbm9tKDEsIFNbdF0sIHBfU19JKQp9CgojIENyZWF0ZSBSMApSXzAgPSAoYmV0YS9nYW1tYSkKCiMgQ3JlYXRlIGEgcGxvdCBvZiB0aGUgZXBpZGVtaWMKbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KHRpZHlyKQp0aWJibGUodCA9IDE6VCwKICAgICAgIFMsIEksIFIpICU+JQogIHBpdm90X2xvbmdlcihuYW1lc190byA9ICdDb21wYXJ0bWVudCcsIHZhbHVlc190byA9ICdQZW9wbGUnLCAtdCkgJT4lCiAgZ2dwbG90KGFlcyh4ID0gdCwgeSA9IFBlb3BsZSwgY29sb3VyID0gQ29tcGFydG1lbnQpKSArCiAgI3NjYWxlX3lfbG9nMTAoKSArCiAgZ2VvbV9saW5lKCkKYGBgCgpOb3cgd2UgY2FuIGZpdCB0aGlzIG1vZGVsIGJ5IHByb3ZpZGluZyB0aGUgZGF0YSB0byBKQUdTCgpgYGB7ciwgbWVzc2FnZT0gRkFMU0UsICByZXN1bHRzPSdoaWRlJywgd2FybmluZz1GQUxTRX0KTl9mdXR1cmUgPSA1MCAjIEZvcmVjYXN0IDEwMCBkYXlzIGludG8gdGhlIGZ1dHVyZQpUX21heCA9IFQgKyBOX2Z1dHVyZSAKamFnc19kYXRhID0gbGlzdChOID0gTiwKICAgICAgICAgICAgICAgICBUID0gVCwKICAgICAgICAgICAgICAgICBUX21heCA9IFRfbWF4LCAKICAgICAgICAgICAgICAgICBJX3N0YXJ0ID0gSVsxXSwKICAgICAgICAgICAgICAgICBSX3N0YXJ0ID0gUlsxXSwKICAgICAgICAgICAgICAgICBOX1NfSSA9IGMoTl9TX0ksIHJlcChOQSwgTl9mdXR1cmUpKSwgIyBZb3UgY2FuIGNvbW1lbnQgb3V0IHRoaXMgbGluZSBpZiB5b3Ugd2FudCBpdCB0byBub3QgaGF2ZSB0aGUgbnVtYmVyIG9mIGNhc2VzLiAKICAgICAgICAgICAgICAgICBOX0lfUiA9IGMoTl9JX1IsIHJlcChOQSwgTl9mdXR1cmUpKSkgCgpsaWJyYXJ5KFIyamFncykKamFnc19ydW4gPSBqYWdzKGRhdGEgPSBqYWdzX2RhdGEsCiAgICAgICAgICAgICAgICBwYXJhbWV0ZXJzLnRvLnNhdmUgPSBjKCJnYW1tYV9pbnYiLCAiYmV0YSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICJTIiwiSSIsICJSIiwgIlJfMCIpLAogICAgICAgICAgICAgICAgbW9kZWwuZmlsZSA9IHRleHRDb25uZWN0aW9uKGphZ3NfY29kZSkpCnBsb3QoamFnc19ydW4pCmBgYAoKTm93IHBsb3QgdGhlIG51bWJlciBvZiBpbmZlY3RlZCBvdmVyIHRpbWU6CgpgYGB7cn0KU19wb3N0ID0gamFnc19ydW4kQlVHU291dHB1dCRtZWRpYW4kUwpJX3Bvc3QgPSBqYWdzX3J1biRCVUdTb3V0cHV0JG1lZGlhbiRJClJfcG9zdCA9IGphZ3NfcnVuJEJVR1NvdXRwdXQkbWVkaWFuJFIKCnRpYmJsZSh0ID0gMTpUX21heCwKICBTX3Bvc3QsIElfcG9zdCwgUl9wb3N0KSAlPiUKICBwaXZvdF9sb25nZXIobmFtZXNfdG8gPSAnQ29tcGFydG1lbnQnLCB2YWx1ZXNfdG8gPSAnUGVvcGxlJywgLXQpICU+JQogIGdncGxvdChhZXMoeCA9IHQsIHkgPSBQZW9wbGUsIGNvbG91ciA9IENvbXBhcnRtZW50KSkgKwogIGdlb21fbGluZSgpCgpgYGAKCk5vdyBwbG90IHRoZSBwYXJhbWV0ZXIgZXN0aW1hdGVzIGFnYWluc3QgdGhlaXIgdHJ1ZSB2YWx1ZXMKCmBgYHtyfQpwb3N0ID0gamFnc19ydW4kQlVHU291dHB1dCRzaW1zLmxpc3QKdGliYmxlKGl0ZXIgPSAxOmxlbmd0aChwb3N0JGJldGEpLAogICAgICAgYmV0YSA9IHBvc3QkYmV0YSwKICAgICAgIGdhbW1hX2ludiA9IHBvc3QkZ2FtbWFfaW52LAogICAgICAgUjAgPSBwb3N0JFJfMCkgJT4lCiAgcGl2b3RfbG9uZ2VyKG5hbWVzX3RvID0gJ1R5cGUnLCB2YWx1ZXNfdG8gPSAnU2FtcGxlJywtaXRlcikgJT4lCiAgZ2dwbG90KGFlcyh4ID0gU2FtcGxlLCBmaWxsID0gVHlwZSkpICsKICBnZW9tX2hpc3RvZ3JhbShiaW5zID0gMzApICsKICBmYWNldF93cmFwKH4gVHlwZSwgc2NhbGVzID0gJ2ZyZWUnKSArCiAgZ2VvbV92bGluZShkYXRhID0gdGliYmxlKGl0ZXIgPSByZXAoMSwgMyksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIFNhbXBsZSA9IGMoYmV0YSwgZ2FtbWFfaW52LCBSXzApLAogICAgICAgICAgICAgICAgICAgICAgICAgICBUeXBlID0gYygnYmV0YScsICdnYW1tYV9pbnYnLCAnUjAnKSksCiAgICAgICAgICAgICBhZXMoeGludGVyY2VwdCA9IFNhbXBsZSkpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAnTm9uZScpCmBgYApBbGwgdmFsdWVzIHNlZW0gdG8gbWF0Y2gsIGRlcGVuZGluZyBvbiB3aGV0aGVyIHlvdSBnaXZlIGl0IHRoZSBudW1iZXIgb2YgY2FzZXMgKCROX3tTIFxyaWdodGFycm93IEl9JCkgb3Igbm90LiA=