1 Exponential Family

\[ f(y_i\vert \theta_i,\phi)=\exp\left\{ \frac{y_i\theta_i- b(\theta_i)}{a(\phi)}+c(y_i,\phi)\right\} \]

likelihood to observe \(y_1, \ldots, y_n\) independent observations \[L(\boldsymbol{\theta},\phi\vert \boldsymbol{y})=\prod\limits_{i=1}^n f(y_i,\theta_i,\phi)\]

log-likelihood \[ l(\boldsymbol{\theta},\phi\vert \boldsymbol{y}) = \sum\limits_{i=1}^n \log f(y_i,\theta_i,\phi) \]

Log-likelihood for one observation: \[ l(\theta_i,\phi\vert y_i)=\left\{ \frac{y_i\theta_i- b(\theta_i)}{a(\phi)}+c(y_i,\phi)\right\} \]

  • \(E[y_i]=\mu_i=b^\prime(\theta_i)\)
  • \(\text{var}[y_i]=b^{\prime\prime}(\theta_i) a(\phi) =V(\mu_i)\)

e.g. for Poisson data: \(\text{var}[y_i] = \mu_i\) and for negative binomial data \(\text{var}[y_i] = \mu_i + \phi \mu_i^2\).

1.1 Parameter Estimation: Maximum Likelihood

\[ S(\boldsymbol{\beta}) = \frac{\partial l(\boldsymbol{\mu} \vert \mathbf{y})}{ \partial{\boldsymbol{\beta}}} = 0 \]

\[ S_i(\boldsymbol{\beta})= \frac{y_i-\mu_i}{\text{var}[y_i]}\frac{\partial\mu}{\partial\eta}\mathbf{x}_i \]

There are only two moments involved in the estimation equations of the mean model parameters: the mean and the variance!

\[ S(\boldsymbol{\beta})=\mathbf{X}^T\mathbf{A}\left(\mathbf{y}-\boldsymbol{\mu}\right) = 0 \]

We can solve this set of score equations iteratively to estimate the model parameters: \[ \mathbf{\beta}^{k+1} = (\mathbf{X}^T\mathbf{W}^k\mathbf{X})^{-1}\mathbf{X}^T\mathbf{W}^kz^{k} \]

with pseudodata

\[ z^k_i = \eta^k_i + \left.\frac{\partial \eta_i}{\partial \mu_i}\right\vert_k (y_i - \mu^k_i) \]

2 Quasi-likelihood

We no longer define the full distribution but only two moments: the mean and the variance of \(y_i\).

  • We typically define these based on an existing distribution.

  • However we make the variance more flexible, i.e. we rescale it with an additional model parameter.

  • Hence, we can model data that are over or under disperse with respect to a known distribution.

\[ \left\{ \begin{array}{rcl} E[Y_i\vert x_i] &=& \mu_i\\ g(\mu_i) &=& \eta_i\\ \eta_i &=& \mathbf{x}_i^T\boldsymbol{\beta}\\ \text{var}[Y_i] &=& \sigma^2 V(\mu_i) \end{array}\right. \]

e.g. quasi poisson

\[ \left\{ \begin{array}{rcl} E[Y_i\vert x_i] &=& \mu_i\\ g(\mu_i) &=& \eta_i\\ \eta_i &=& \mathbf{x}_i^T\boldsymbol{\beta}\\ \text{var}[Y_i] &=& \sigma^2 \mu_i \end{array}\right. \]

e.g. quasi-negative binomial

\[ \left\{ \begin{array}{rcl} E[Y_i\vert x_i] &=& \mu_i\\ g(\mu_i) &=& \eta_i\\ \eta_i &=& \mathbf{x}_i^T\boldsymbol{\beta}\\ \text{var}[Y_i] &=& \sigma^2 (\mu_i + \phi \mu_i^2) \end{array}\right. \]

2.1 Parameter Estimation

Note, that this leads to the following estimation equations:

\[ U_i(\boldsymbol{\beta})= \frac{y_i-\mu_i}{\sigma^2V(\mu_i)}\frac{\partial\mu}{\partial\eta}\mathbf{x}_i \]

\[ \begin{array}{rcccc} U(\boldsymbol{\beta})&=&\left[\mathbf{X}^T\mathbf{A}\left(\mathbf{y}-\boldsymbol{\mu}\right)\right]/\sigma^2 &=& 0\\ &&\Updownarrow\\ &&\mathbf{X}^T\mathbf{A}\left(\mathbf{y}-\boldsymbol{\mu}\right) &=& 0 \end{array} \] Hence, the estimating equations for the mean model parameters remain the same as those for the conventional distribution where the quasi-likelihood is derived from.

The variance covariance matrix of the mean model parameters then becomes: \[ \Sigma_{\hat{\boldsymbol{\beta}}}= (\mathbf{X}^T\mathbf{WX})^{-1}\sigma^2 \]

We can estimate \(\sigma^2\) using a moment estimator on the residual vector \(\mathbf{y}-\boldsymbol{\mu}\), i.e. 

\[ \hat{\sigma}^2 = \frac{1}{n-p} \sum_\limits{i=1}^n \frac{(y_i-\hat\mu_i)^2}{V(\hat\mu_i)} \]

Note, that \[e_i^p=\frac{(y_i-\hat\mu_i)}{\sqrt{V(\hat\mu_i)}}\] are also referred to as the Pearson residuals.

Another type of residuals for GLMs are deviance residuals, i.e. 

\[e_i^d = \text{sign}(y_i-\hat\mu_i)\sqrt{2[l(y_i,y_i)-l(y_i,\hat\mu_i)]} \] So another estimator is

\[\hat{\sigma}^2 = \frac{\sum_\limits{i=1}^n(e_i^d)^2}{n-p} = \frac{D}{n-p} \] with D the deviance statistic: the LRT test between the saturated model (a model that provides a perfect fit) and the current model:

\[ D = 2 \sum\limits_{i=1}^n [l(y_i,y_i,\phi)- l(y_i,\hat{\mu}_i,\phi)] \]

So the standard errors on the model parameters under quasi-likelihood become:

\[ \hat{\text{se}}_{\mathbf{L}^T\hat{\boldsymbol{\beta}}}^{QL} = \hat{\text{se}}_{\mathbf{L}^T\hat{\boldsymbol{\beta}}}^{ML}\times \hat{\sigma}\]

2.2 Hypothesis tests

An approximate t-test statistic can be defined as

\[ t = \frac{\mathbf{L}^T\hat{\boldsymbol{\beta}}}{\hat{\text{se}}_{\mathbf{L}^T\hat{\boldsymbol{\beta}}}^{QL}} \approx t_{n-p}\vert H_0 \]

And an approximate F-test statistic can be defined as:

\[F = \frac{\frac{\text{LRT}^{ML}}{c}}{\hat\sigma^2} \approx F_{c,n-p} \vert H_0,\] with c the degrees of freedom of the LRT statistic.

2.3 Example

## quasipoisson.
counts <- c(18,17,15,20,10,20,25,13,12)
outcome <- gl(3,1,9)
treatment <- gl(3,3)
d.AD <- data.frame(treatment, outcome, counts)
d.AD
glm.pois <- glm(counts ~ outcome + treatment, family = poisson())
summary(glm.pois)
## 
## Call:
## glm(formula = counts ~ outcome + treatment, family = poisson())
## 
## Coefficients:
##               Estimate Std. Error z value Pr(>|z|)    
## (Intercept)  3.045e+00  1.709e-01  17.815   <2e-16 ***
## outcome2    -4.543e-01  2.022e-01  -2.247   0.0246 *  
## outcome3    -2.930e-01  1.927e-01  -1.520   0.1285    
## treatment2   1.398e-16  2.000e-01   0.000   1.0000    
## treatment3  -2.416e-16  2.000e-01   0.000   1.0000    
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for poisson family taken to be 1)
## 
##     Null deviance: 10.5814  on 8  degrees of freedom
## Residual deviance:  5.1291  on 4  degrees of freedom
## AIC: 56.761
## 
## Number of Fisher Scoring iterations: 4
glm.qpois <- glm(counts ~ outcome+treatment, family = quasipoisson())
summary(glm.qpois)
## 
## Call:
## glm(formula = counts ~ outcome + treatment, family = quasipoisson())
## 
## Coefficients:
##               Estimate Std. Error t value Pr(>|t|)    
## (Intercept)  3.045e+00  1.944e-01  15.665  9.7e-05 ***
## outcome2    -4.543e-01  2.299e-01  -1.976    0.119    
## outcome3    -2.930e-01  2.192e-01  -1.337    0.252    
## treatment2   1.398e-16  2.274e-01   0.000    1.000    
## treatment3  -2.416e-16  2.274e-01   0.000    1.000    
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for quasipoisson family taken to be 1.2933)
## 
##     Null deviance: 10.5814  on 8  degrees of freedom
## Residual deviance:  5.1291  on 4  degrees of freedom
## AIC: NA
## 
## Number of Fisher Scoring iterations: 4

Estimate dispersion ourselves? We first calculate the Pearson residuals.

ep <- (counts - glm.pois$fitted)/sqrt(glm.pois$fitted)
range(ep - resid(glm.pois,type="pearson"))
## [1] 0 0

Now, we can estimate the quasi-dispersion parameter

n <- length(counts)
p <- length(coef(glm.pois))
sigma2 <- sum(ep^2)/(n-p)
sigma2
## [1] 1.2933
poisRes <- summary(glm.pois)$coef
poisRes
##                  Estimate Std. Error       z value     Pr(>|z|)
## (Intercept)  3.044522e+00  0.1708987  1.781478e+01 5.426767e-71
## outcome2    -4.542553e-01  0.2021708 -2.246889e+00 2.464711e-02
## outcome3    -2.929871e-01  0.1927423 -1.520097e+00 1.284865e-01
## treatment2   1.397701e-16  0.2000000  6.988506e-16 1.000000e+00
## treatment3  -2.415657e-16  0.2000000 -1.207829e-15 1.000000e+00
qlRes <- summary(glm.qpois)$coef
qlRes
##                  Estimate Std. Error       t value     Pr(>|t|)
## (Intercept)  3.044522e+00  0.1943517  1.566502e+01 9.698855e-05
## outcome2    -4.542553e-01  0.2299154 -1.975750e+00 1.193809e-01
## outcome3    -2.929871e-01  0.2191931 -1.336662e+00 2.522944e-01
## treatment2   1.397701e-16  0.2274467  6.145180e-16 1.000000e+00
## treatment3  -2.415657e-16  0.2274467 -1.062076e-15 1.000000e+00
cbind(ql.se=qlRes[,2],pois.se=poisRes[,2],qlself.se=poisRes[,2]*sqrt(sigma2))
##                 ql.se   pois.se qlself.se
## (Intercept) 0.1943517 0.1708987 0.1943517
## outcome2    0.2299154 0.2021708 0.2299154
## outcome3    0.2191931 0.1927423 0.2191931
## treatment2  0.2274467 0.2000000 0.2274467
## treatment3  0.2274467 0.2000000 0.2274467

2.3.1 Approximate F-test

LR -test with Poisson regression:

library(car)
## Warning: package 'car' was built under R version 4.4.1
## Loading required package: carData
Anova(glm.pois)

We check that the approximate F-statistic equals LRT/df/sigma2

Anova(glm.qpois, test="F")
Anova(glm.pois)[1,1]/Anova(glm.pois)[1,2]/sigma2
## [1] 2.107903

2.3.2 Deviance

deviance(glm.pois)
## [1] 5.129141
lsat <- sum(dpois(counts,counts,log = TRUE))
lcur <- sum(dpois(counts,glm.pois$fitted.values,log = TRUE))
2*(lsat-lcur)
## [1] 5.129141

Deviance residuals

lsat.i <-  dpois(counts,counts,log = TRUE)
lcur.i <- dpois(counts,glm.pois$fitted.values,log = TRUE)
e.dev <- sign(counts-glm.pois$fitted) * sqrt(2*(lsat.i-lcur.i))
e.dev
##           1           2           3           4           5           6 
## -0.67124923  0.96272360 -0.16964662 -0.21998507 -0.95552353  1.04938637 
##           7           8           9 
##  0.84715368 -0.09167147 -0.96656372
resid(glm.pois,type="deviance")
##           1           2           3           4           5           6 
## -0.67124923  0.96272360 -0.16964662 -0.21998507 -0.95552353  1.04938637 
##           7           8           9 
##  0.84715368 -0.09167147 -0.96656372
glm.pois.out.null <- glm(counts ~  treatment, family = poisson())
anova(glm.pois.out.null,glm.pois)
lrtfull <- logLik(glm.pois)
lrtout0 <- logLik(glm.pois.out.null)
2*(lrtfull-lrtout0)
## 'log Lik.' 5.452305 (df=5)

2.3.3 Approximate F-test 2

glm.qpois.out.null <- glm(counts ~  treatment, family = quasipoisson())
anova(glm.qpois,glm.qpois.out.null,test = "F")
2*(lrtfull-lrtout0)
## 'log Lik.' 5.452305 (df=5)
2*(lrtfull-lrtout0)/2/sigma2
## 'log Lik.' 2.107903 (df=5)
LS0tCnRpdGxlOiAnUXVhc2ktbGlrZWxpaG9vZCcKYXV0aG9yOiAiTGlldmVuIENsZW1lbnQiCmRhdGU6ICJMYXN0IGVkaXRlZCBvbiBgciBmb3JtYXQoU3lzLnRpbWUoKSwgJyVkICVCLCAlWScpYCIKb3V0cHV0OiAKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICBwZGZfZG9jdW1lbnQ6CiAgICB0b2M6IHRydWUKICAgIG51bWJlcl9zZWN0aW9uczogdHJ1ZQogICAgbGF0ZXhfZW5naW5lOiB4ZWxhdGV4CmFsd2F5c19hbGxvd19odG1sOiB0cnVlCmxpbmtjb2xvcjogYmx1ZQp1cmxjb2xvcjogYmx1ZSAKY2l0ZWNvbG9yOiBibHVlCmxpbmstY2l0YXRpb25zOiB5ZXMKCi0tLQoKIyBFeHBvbmVudGlhbCBGYW1pbHkKCiQkCmYoeV9pXHZlcnQgXHRoZXRhX2ksXHBoaSk9XGV4cFxsZWZ0XHsgXGZyYWN7eV9pXHRoZXRhX2ktIGIoXHRoZXRhX2kpfXthKFxwaGkpfStjKHlfaSxccGhpKVxyaWdodFx9CiQkCgpsaWtlbGlob29kIHRvIG9ic2VydmUgJHlfMSwgXGxkb3RzLCB5X24kIGluZGVwZW5kZW50IG9ic2VydmF0aW9ucyAKJCRMKFxib2xkc3ltYm9se1x0aGV0YX0sXHBoaVx2ZXJ0IFxib2xkc3ltYm9se3l9KT1ccHJvZFxsaW1pdHNfe2k9MX1ebiBmKHlfaSxcdGhldGFfaSxccGhpKSQkCgpsb2ctbGlrZWxpaG9vZAokJApsKFxib2xkc3ltYm9se1x0aGV0YX0sXHBoaVx2ZXJ0IFxib2xkc3ltYm9se3l9KSA9ICBcc3VtXGxpbWl0c197aT0xfV5uIFxsb2cgIGYoeV9pLFx0aGV0YV9pLFxwaGkpCiQkCgpMb2ctbGlrZWxpaG9vZCBmb3Igb25lIG9ic2VydmF0aW9uOiAKJCQKbChcdGhldGFfaSxccGhpXHZlcnQgeV9pKT1cbGVmdFx7IFxmcmFje3lfaVx0aGV0YV9pLSBiKFx0aGV0YV9pKX17YShccGhpKX0rYyh5X2ksXHBoaSlccmlnaHRcfQokJAoKLSAkRVt5X2ldPVxtdV9pPWJeXHByaW1lKFx0aGV0YV9pKSQKLSAkXHRleHR7dmFyfVt5X2ldPWJee1xwcmltZVxwcmltZX0oXHRoZXRhX2kpIGEoXHBoaSkgPVYoXG11X2kpJAoKZS5nLiBmb3IgUG9pc3NvbiBkYXRhOiAKJFx0ZXh0e3Zhcn1beV9pXSA9IFxtdV9pJCBhbmQgZm9yIG5lZ2F0aXZlIGJpbm9taWFsIGRhdGEgJFx0ZXh0e3Zhcn1beV9pXSA9IFxtdV9pICsgXHBoaSBcbXVfaV4yJC4KCiMjIFBhcmFtZXRlciBFc3RpbWF0aW9uOiBNYXhpbXVtIExpa2VsaWhvb2QKCiQkClMoXGJvbGRzeW1ib2x7XGJldGF9KSA9IFxmcmFje1xwYXJ0aWFsICBsKFxib2xkc3ltYm9se1xtdX0gXHZlcnQgXG1hdGhiZnt5fSl9ewpccGFydGlhbHtcYm9sZHN5bWJvbHtcYmV0YX19fSA9IDAKJCQKCiQkClNfaShcYm9sZHN5bWJvbHtcYmV0YX0pPSBcZnJhY3t5X2ktXG11X2l9e1x0ZXh0e3Zhcn1beV9pXX1cZnJhY3tccGFydGlhbFxtdX17XHBhcnRpYWxcZXRhfVxtYXRoYmZ7eH1faQokJAoKClRoZXJlIGFyZSBvbmx5IHR3byBtb21lbnRzIGludm9sdmVkIGluIHRoZSBlc3RpbWF0aW9uIGVxdWF0aW9ucyBvZiB0aGUgbWVhbiBtb2RlbCBwYXJhbWV0ZXJzOiAKdGhlIG1lYW4gYW5kIHRoZSB2YXJpYW5jZSEgCgokJApTKFxib2xkc3ltYm9se1xiZXRhfSk9XG1hdGhiZntYfV5UXG1hdGhiZntBfVxsZWZ0KFxtYXRoYmZ7eX0tXGJvbGRzeW1ib2x7XG11fVxyaWdodCkgPSAwCiQkCgpXZSBjYW4gc29sdmUgdGhpcyBzZXQgb2Ygc2NvcmUgZXF1YXRpb25zIGl0ZXJhdGl2ZWx5IHRvIGVzdGltYXRlIHRoZSBtb2RlbCBwYXJhbWV0ZXJzOiAKJCQKXG1hdGhiZntcYmV0YX1ee2srMX0gPSAoXG1hdGhiZntYfV5UXG1hdGhiZntXfV5rXG1hdGhiZntYfSleey0xfVxtYXRoYmZ7WH1eVFxtYXRoYmZ7V31ea3pee2t9CiQkCgp3aXRoICBwc2V1ZG9kYXRhIAoKJCQKel5rX2kgPSBcZXRhXmtfaSArIFxsZWZ0LlxmcmFje1xwYXJ0aWFsIFxldGFfaX17XHBhcnRpYWwgXG11X2l9XHJpZ2h0XHZlcnRfayAoeV9pIC0gXG11XmtfaSkgCiQkCgoKIyBRdWFzaS1saWtlbGlob29kIAoKV2Ugbm8gbG9uZ2VyIGRlZmluZSB0aGUgZnVsbCBkaXN0cmlidXRpb24gYnV0IG9ubHkgdHdvIG1vbWVudHM6IHRoZSBtZWFuIGFuZCB0aGUgdmFyaWFuY2Ugb2YgJHlfaSQuIAoKLSBXZSB0eXBpY2FsbHkgZGVmaW5lIHRoZXNlIGJhc2VkIG9uIGFuIGV4aXN0aW5nIGRpc3RyaWJ1dGlvbi4KLSBIb3dldmVyIHdlIG1ha2UgdGhlIHZhcmlhbmNlIG1vcmUgZmxleGlibGUsIGkuZS4gd2UgcmVzY2FsZSBpdCB3aXRoIGFuIGFkZGl0aW9uYWwgbW9kZWwgcGFyYW1ldGVyLiAKCi0gSGVuY2UsIHdlIGNhbiBtb2RlbCBkYXRhIHRoYXQgYXJlIG92ZXIgb3IgdW5kZXIgZGlzcGVyc2Ugd2l0aCByZXNwZWN0IHRvIGEga25vd24gZGlzdHJpYnV0aW9uLiAKCiQkClxsZWZ0XHsgXGJlZ2lue2FycmF5fXtyY2x9CkVbWV9pXHZlcnQgeF9pXSAmPSYgXG11X2lcXApnKFxtdV9pKSAmPSYgXGV0YV9pXFwKXGV0YV9pICY9JiBcbWF0aGJme3h9X2leVFxib2xkc3ltYm9se1xiZXRhfVxcClx0ZXh0e3Zhcn1bWV9pXSAmPSYgXHNpZ21hXjIgVihcbXVfaSkKXGVuZHthcnJheX1ccmlnaHQuCiQkCgoKZS5nLiBxdWFzaSBwb2lzc29uCgokJApcbGVmdFx7IFxiZWdpbnthcnJheX17cmNsfQpFW1lfaVx2ZXJ0IHhfaV0gJj0mIFxtdV9pXFwKZyhcbXVfaSkgJj0mIFxldGFfaVxcClxldGFfaSAmPSYgXG1hdGhiZnt4fV9pXlRcYm9sZHN5bWJvbHtcYmV0YX1cXApcdGV4dHt2YXJ9W1lfaV0gJj0mIFxzaWdtYV4yIFxtdV9pClxlbmR7YXJyYXl9XHJpZ2h0LgokJAoKZS5nLiBxdWFzaS1uZWdhdGl2ZSBiaW5vbWlhbAoKJCQKXGxlZnRceyBcYmVnaW57YXJyYXl9e3JjbH0KRVtZX2lcdmVydCB4X2ldICY9JiBcbXVfaVxcCmcoXG11X2kpICY9JiBcZXRhX2lcXApcZXRhX2kgJj0mIFxtYXRoYmZ7eH1faV5UXGJvbGRzeW1ib2x7XGJldGF9XFwKXHRleHR7dmFyfVtZX2ldICY9JiBcc2lnbWFeMiAoXG11X2kgKyBccGhpIFxtdV9pXjIpClxlbmR7YXJyYXl9XHJpZ2h0LgokJAoKIyMgUGFyYW1ldGVyIEVzdGltYXRpb24KCk5vdGUsIHRoYXQgdGhpcyBsZWFkcyB0byB0aGUgZm9sbG93aW5nIGVzdGltYXRpb24gZXF1YXRpb25zOgoKJCQKVV9pKFxib2xkc3ltYm9se1xiZXRhfSk9IFxmcmFje3lfaS1cbXVfaX17XHNpZ21hXjJWKFxtdV9pKX1cZnJhY3tccGFydGlhbFxtdX17XHBhcnRpYWxcZXRhfVxtYXRoYmZ7eH1faQokJAogCgokJApcYmVnaW57YXJyYXl9e3JjY2NjfQpVKFxib2xkc3ltYm9se1xiZXRhfSkmPSZcbGVmdFtcbWF0aGJme1h9XlRcbWF0aGJme0F9XGxlZnQoXG1hdGhiZnt5fS1cYm9sZHN5bWJvbHtcbXV9XHJpZ2h0KVxyaWdodF0vXHNpZ21hXjIgJj0mIDBcXAomJlxVcGRvd25hcnJvd1xcCiYmXG1hdGhiZntYfV5UXG1hdGhiZntBfVxsZWZ0KFxtYXRoYmZ7eX0tXGJvbGRzeW1ib2x7XG11fVxyaWdodCkgJj0mIDAKXGVuZHthcnJheX0KJCQKSGVuY2UsIHRoZSBlc3RpbWF0aW5nIGVxdWF0aW9ucyBmb3IgdGhlIG1lYW4gbW9kZWwgcGFyYW1ldGVycyByZW1haW4gdGhlIHNhbWUgYXMgdGhvc2UgZm9yIHRoZSBjb252ZW50aW9uYWwgZGlzdHJpYnV0aW9uIHdoZXJlIHRoZSBxdWFzaS1saWtlbGlob29kIGlzIGRlcml2ZWQgZnJvbS4gCgpUaGUgdmFyaWFuY2UgY292YXJpYW5jZSBtYXRyaXggb2YgdGhlIG1lYW4gbW9kZWwgcGFyYW1ldGVycyB0aGVuIGJlY29tZXM6IAokJApcU2lnbWFfe1xoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX09IChcbWF0aGJme1h9XlRcbWF0aGJme1dYfSleey0xfVxzaWdtYV4yCiQkCgpXZSBjYW4gZXN0aW1hdGUgJFxzaWdtYV4yJCB1c2luZyBhIG1vbWVudCBlc3RpbWF0b3Igb24gdGhlIHJlc2lkdWFsIHZlY3RvciAkXG1hdGhiZnt5fS1cYm9sZHN5bWJvbHtcbXV9JCwgaS5lLiAKCiQkClxoYXR7XHNpZ21hfV4yID0gXGZyYWN7MX17bi1wfSBcc3VtX1xsaW1pdHN7aT0xfV5uIFxmcmFjeyh5X2ktXGhhdFxtdV9pKV4yfXtWKFxoYXRcbXVfaSl9CiQkCgoKCk5vdGUsIHRoYXQgCiQkZV9pXnA9XGZyYWN7KHlfaS1caGF0XG11X2kpfXtcc3FydHtWKFxoYXRcbXVfaSl9fSQkIGFyZSBhbHNvIHJlZmVycmVkIHRvIGFzIHRoZSBQZWFyc29uIHJlc2lkdWFscy4gCgpBbm90aGVyIHR5cGUgb2YgcmVzaWR1YWxzIGZvciBHTE1zIGFyZSBkZXZpYW5jZSByZXNpZHVhbHMsIGkuZS4gCgokJGVfaV5kID0gXHRleHR7c2lnbn0oeV9pLVxoYXRcbXVfaSlcc3FydHsyW2woeV9pLHlfaSktbCh5X2ksXGhhdFxtdV9pKV19CiQkClNvIGFub3RoZXIgZXN0aW1hdG9yIGlzIAoKJCRcaGF0e1xzaWdtYX1eMiA9IFxmcmFje1xzdW1fXGxpbWl0c3tpPTF9Xm4oZV9pXmQpXjJ9e24tcH0gPSBcZnJhY3tEfXtuLXB9CiQkCndpdGggRCB0aGUgZGV2aWFuY2Ugc3RhdGlzdGljOiB0aGUgTFJUIHRlc3QgYmV0d2VlbiB0aGUgc2F0dXJhdGVkIG1vZGVsIChhIG1vZGVsIHRoYXQgcHJvdmlkZXMgYSBwZXJmZWN0IGZpdCkgYW5kIHRoZSBjdXJyZW50IG1vZGVsOgoKJCQKRCA9IDIgXHN1bVxsaW1pdHNfe2k9MX1ebiBbbCh5X2kseV9pLFxwaGkpLSBsKHlfaSxcaGF0e1xtdX1faSxccGhpKV0KJCQKClNvIHRoZSBzdGFuZGFyZCBlcnJvcnMgb24gdGhlIG1vZGVsIHBhcmFtZXRlcnMgdW5kZXIgcXVhc2ktbGlrZWxpaG9vZCBiZWNvbWU6IAoKJCQKXGhhdHtcdGV4dHtzZX19X3tcbWF0aGJme0x9XlRcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19XntRTH0gPSBcaGF0e1x0ZXh0e3NlfX1fe1xtYXRoYmZ7TH1eVFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX1ee01MfVx0aW1lcyBcaGF0e1xzaWdtYX0kJAoKIyMgSHlwb3RoZXNpcyB0ZXN0cwoKQW4gYXBwcm94aW1hdGUgdC10ZXN0IHN0YXRpc3RpYyBjYW4gYmUgZGVmaW5lZCBhcwoKJCQKdCA9IFxmcmFje1xtYXRoYmZ7TH1eVFxoYXR7XGJvbGRzeW1ib2x7XGJldGF9fX17XGhhdHtcdGV4dHtzZX19X3tcbWF0aGJme0x9XlRcaGF0e1xib2xkc3ltYm9se1xiZXRhfX19XntRTH19IFxhcHByb3ggdF97bi1wfVx2ZXJ0IEhfMAokJAoKQW5kIGFuIGFwcHJveGltYXRlIEYtdGVzdCBzdGF0aXN0aWMgY2FuIGJlIGRlZmluZWQgYXM6IAoKJCRGID0gXGZyYWN7XGZyYWN7XHRleHR7TFJUfV57TUx9fXtjfX17XGhhdFxzaWdtYV4yfSAgXGFwcHJveCBGX3tjLG4tcH0gXHZlcnQgSF8wLCQkCndpdGggYyB0aGUgZGVncmVlcyBvZiBmcmVlZG9tIG9mIHRoZSBMUlQgc3RhdGlzdGljLgoKIyMgRXhhbXBsZSAKCmBgYHtyfQojIyBxdWFzaXBvaXNzb24uCmNvdW50cyA8LSBjKDE4LDE3LDE1LDIwLDEwLDIwLDI1LDEzLDEyKQpvdXRjb21lIDwtIGdsKDMsMSw5KQp0cmVhdG1lbnQgPC0gZ2woMywzKQpkLkFEIDwtIGRhdGEuZnJhbWUodHJlYXRtZW50LCBvdXRjb21lLCBjb3VudHMpCmQuQUQKYGBgCgpgYGB7cn0KZ2xtLnBvaXMgPC0gZ2xtKGNvdW50cyB+IG91dGNvbWUgKyB0cmVhdG1lbnQsIGZhbWlseSA9IHBvaXNzb24oKSkKc3VtbWFyeShnbG0ucG9pcykKYGBgCgpgYGB7cn0KZ2xtLnFwb2lzIDwtIGdsbShjb3VudHMgfiBvdXRjb21lK3RyZWF0bWVudCwgZmFtaWx5ID0gcXVhc2lwb2lzc29uKCkpCnN1bW1hcnkoZ2xtLnFwb2lzKQpgYGAKCkVzdGltYXRlIGRpc3BlcnNpb24gb3Vyc2VsdmVzPyAKV2UgZmlyc3QgY2FsY3VsYXRlIHRoZSBQZWFyc29uIHJlc2lkdWFscy4gCgpgYGB7cn0KZXAgPC0gKGNvdW50cyAtIGdsbS5wb2lzJGZpdHRlZCkvc3FydChnbG0ucG9pcyRmaXR0ZWQpCnJhbmdlKGVwIC0gcmVzaWQoZ2xtLnBvaXMsdHlwZT0icGVhcnNvbiIpKQpgYGAKCk5vdywgd2UgY2FuIGVzdGltYXRlIHRoZSBxdWFzaS1kaXNwZXJzaW9uIHBhcmFtZXRlcgpgYGB7cn0KbiA8LSBsZW5ndGgoY291bnRzKQpwIDwtIGxlbmd0aChjb2VmKGdsbS5wb2lzKSkKc2lnbWEyIDwtIHN1bShlcF4yKS8obi1wKQpzaWdtYTIKYGBgCgpgYGB7cn0KcG9pc1JlcyA8LSBzdW1tYXJ5KGdsbS5wb2lzKSRjb2VmCnBvaXNSZXMKcWxSZXMgPC0gc3VtbWFyeShnbG0ucXBvaXMpJGNvZWYKcWxSZXMKY2JpbmQocWwuc2U9cWxSZXNbLDJdLHBvaXMuc2U9cG9pc1Jlc1ssMl0scWxzZWxmLnNlPXBvaXNSZXNbLDJdKnNxcnQoc2lnbWEyKSkKYGBgCgojIyMgQXBwcm94aW1hdGUgRi10ZXN0CgpMUiAtdGVzdCB3aXRoIFBvaXNzb24gcmVncmVzc2lvbjogCgpgYGB7cn0KbGlicmFyeShjYXIpCkFub3ZhKGdsbS5wb2lzKQpgYGAKV2UgY2hlY2sgdGhhdCB0aGUgYXBwcm94aW1hdGUgRi1zdGF0aXN0aWMgZXF1YWxzIExSVC9kZi9zaWdtYTIgCgpgYGB7cn0KQW5vdmEoZ2xtLnFwb2lzLCB0ZXN0PSJGIikKQW5vdmEoZ2xtLnBvaXMpWzEsMV0vQW5vdmEoZ2xtLnBvaXMpWzEsMl0vc2lnbWEyCmBgYAoKCiMjIyBEZXZpYW5jZQoKYGBge3J9CmRldmlhbmNlKGdsbS5wb2lzKQpsc2F0IDwtIHN1bShkcG9pcyhjb3VudHMsY291bnRzLGxvZyA9IFRSVUUpKQpsY3VyIDwtIHN1bShkcG9pcyhjb3VudHMsZ2xtLnBvaXMkZml0dGVkLnZhbHVlcyxsb2cgPSBUUlVFKSkKMioobHNhdC1sY3VyKQpgYGAKCkRldmlhbmNlIHJlc2lkdWFscwoKYGBge3J9CmxzYXQuaSA8LSAgZHBvaXMoY291bnRzLGNvdW50cyxsb2cgPSBUUlVFKQpsY3VyLmkgPC0gZHBvaXMoY291bnRzLGdsbS5wb2lzJGZpdHRlZC52YWx1ZXMsbG9nID0gVFJVRSkKZS5kZXYgPC0gc2lnbihjb3VudHMtZ2xtLnBvaXMkZml0dGVkKSAqIHNxcnQoMioobHNhdC5pLWxjdXIuaSkpCmUuZGV2CnJlc2lkKGdsbS5wb2lzLHR5cGU9ImRldmlhbmNlIikKYGBgCgpgYGB7cn0KZ2xtLnBvaXMub3V0Lm51bGwgPC0gZ2xtKGNvdW50cyB+ICB0cmVhdG1lbnQsIGZhbWlseSA9IHBvaXNzb24oKSkKYW5vdmEoZ2xtLnBvaXMub3V0Lm51bGwsZ2xtLnBvaXMpCmxydGZ1bGwgPC0gbG9nTGlrKGdsbS5wb2lzKQpscnRvdXQwIDwtIGxvZ0xpayhnbG0ucG9pcy5vdXQubnVsbCkKMioobHJ0ZnVsbC1scnRvdXQwKQpgYGAKCiMjIyBBcHByb3hpbWF0ZSBGLXRlc3QgMgoKYGBge3J9CmdsbS5xcG9pcy5vdXQubnVsbCA8LSBnbG0oY291bnRzIH4gIHRyZWF0bWVudCwgZmFtaWx5ID0gcXVhc2lwb2lzc29uKCkpCmFub3ZhKGdsbS5xcG9pcyxnbG0ucXBvaXMub3V0Lm51bGwsdGVzdCA9ICJGIikKMioobHJ0ZnVsbC1scnRvdXQwKQoyKihscnRmdWxsLWxydG91dDApLzIvc2lnbWEyCmBgYAo=