library(dplyr)
library(ggplot2)
library(mvtnorm)
library(robust)

Here are presented some situations using artificially generated data where the Mahalanobis distance does a good and a bad job detecting outliers.

Spherical Data

We know that for spherical data (no correlation between variables) the euclidean distance works ok.

sample = rmvnorm(1000, sigma=diag(2))
center = colMeans(sample)
distances = euclidean_norm(sample-center)
cutoff = quantile(distances, 0.90)
custom_plot(sample, distances>cutoff, center)

Non-Spherical Data

For non-spherical data the euclidean norm does not work as well.

sigma = matrix(c(1, 0.8, 0.8, 1), ncol=2)
sample = rmvnorm(1000, sigma=sigma)
center = colMeans(sample)
distances = euclidean_norm(sample-center)
cutoff = quantile(distances, 0.90)
custom_plot(sample, distances>cutoff, center)

The Mahalanobis distance works better since it considers the correlation structure of the data.

sigma = matrix(c(1, 0.8, 0.8, 1), ncol=2)
sample = rmvnorm(1000, sigma=sigma)
center = colMeans(sample)
distances = mahalanobis(sample, center=center, cov=cov(sample))
cutoff = quantile(distances, 0.90)
custom_plot(sample, distances>cutoff, center)

Mahalanobis Distance Robustness

The Mahalanobis distance to the center of the data defined as:

\[ d(x) = (x-\mu)^t \Sigma^{-1} (x-\mu)\]

Where \(\mu\) is an estimation of the center of the cloud of points, generally the mean and \(\Sigma\) is an estimation of the covariance matrix. Therefore the Mahalanobis distance is as good as these estimations are.

We’ll now see some shortcomings of the Mahalanobis distance and how to deal with them.

Better location estimator

We already know that the mean is not very robust to outliers. We can improve our location estimator to a more robust alternative defined for a set of points \(x_1, x_2 \dots x_n\) as:

\[\arg \min_{1 \leq i \leq n} \sum_{j=1}^n \| x_i - x_j \|_2\]

Or in other words, the point from the set of points that minimizes the euclidian distance to all the other points.

geometric_median <- function (sample) {
  euclidian_distances = apply(sample, 1, function (x) {sum(euclidean_norm(sample - x))})
  sample[which.min(euclidian_distances),]
}
sigma1 = matrix(c(1, 0.8, 0.8, 1), ncol=2)
sigma2 = matrix(c(1, 0.3, 0.3, 1), ncol=2)
sample1 = rmvnorm(1000, sigma=sigma1)
sample2 = rmvnorm(100, mean=c(-3, 8), sigma=sigma2)
sample = rbind(sample1, sample2)
center = colMeans(sample)
custom_plot_no_outliers(sample, center)

sigma1 = matrix(c(1, 0.8, 0.8, 1), ncol=2)
sigma2 = matrix(c(1, 0.3, 0.3, 1), ncol=2)
sample1 = rmvnorm(1000, sigma=sigma1)
sample2 = rmvnorm(100, mean=c(-3, 8), sigma=sigma2)
sample = rbind(sample1, sample2)
center = geometric_median(sample)
custom_plot_no_outliers(sample, center)

We can see that this estimate of the center of the cloud of data is more robust to noise.

Better scale estimator

Minimum Covariance Determinant

A classical approach to computing a robust covariance matrix is the use of the Minimum Covariance Determinant (MCD). This method not only provides estimators for the covariance matrix but also location estimates.

The location estimate of MCD, \(\hat{\mu}\) is the mean of the \(h\) observations for which the determinant of the covariance matrix is minimal.

\(\hat\Sigma\) is the covariance matrix of the \(h\) observations multiplied by a consistency factor \(c_0\) (needed to achieve consistency on normal distributions).

The main parameter of this method is \(\alpha\), this value roughly represents the value \(h/n\), the proportion of observations used for the estimation. Since the value of \(h\) must lay between \((n + p + 1)/2\) and \(n\) (for \(n\) observations of \(p\) variables), \(\alpha\) must be between 0.5 and 1. A low \(\alpha\) translates in more robustness but low consistency at the normal distribution, whereas an \(\alpha\) of 1 is as bad as the classical sample covariance matrix.

A good in depth explanation of MCD can be found here

Problems with the Sample Covariance Matrix

So we’ve introduced some noise and we can see that the Mahalanobis distance does not properly identify the outliers. This is because the heavy presence of outliers inflates the covariance estimates allowing outliers to pass undetected.

sigma1 = matrix(c(1, 0.9, 0.9, 1), ncol=2)
sigma2 = matrix(c(1, 0.3, 0.3, 1), ncol=2)
sample1 = rmvnorm(1000, sigma=sigma1)
sample2 = rmvnorm(100, mean=c(-2, 3), sigma=sigma2)
sample = rbind(sample1, sample2)
center = colMeans(sample)
distances = mahalanobis(sample, center=center, cov=cov(sample))
cutoff = quantile(distances, 0.90)
custom_plot(sample, distances>cutoff, center)

sigma1 = matrix(c(1, 0.9, 0.9, 1), ncol=2)
sigma2 = matrix(c(1, 0.3, 0.3, 1), ncol=2)
sample1 = rmvnorm(1000, sigma=sigma1)
sample2 = rmvnorm(100, mean=c(-2, 3), sigma=sigma2)
sample = rbind(sample1, sample2)
cov.obj = covRob(sample, estim="mcd", alpha=0.7)
center = cov.obj$center
cov = cov.obj$cov
distances = mahalanobis(sample, center=center, cov=cov)
cutoff = quantile(distances, 0.90)
custom_plot(sample, distances>cutoff, center)

Other issues

This section exhibits some limitations of the Mahalanobis distance that I do not know how to overcome.

Non Linearity

The Mahalanobis distance is only able to capture linear relationships between the variables. This case presents a cuadratic relationship so the outlier cut here is not quite right.

x = rnorm(1000, mean=5, sd=2)
y = rnorm(1000, mean=x^2, sd=3)
sample = cbind(x, y)
cov.obj = covRob(sample, estim="mcd", alpha=0.7)
center = cov.obj$center
cov = cov.obj$cov
distances = mahalanobis(sample, center=center, cov=cov)
cutoff = quantile(distances, 0.90)
custom_plot(sample, distances>cutoff, center)

Heteroskedacity

We can find heteroskedacity or heterogeneity of the variance when the variance of a variable depends on the value of another. In this example we can see that when \(x\) increases not only \(y\) increases but also the variability of \(y\) is greater.

x = rgamma(1000, shape=1, scale=1)
y = rnorm(1000, mean=x, sd=0.2*x)
sample = cbind(x, y)
cov.obj = covRob(sample, estim="mcd", alpha=0.7)
center = cov.obj$center
cov = cov.obj$cov
distances = mahalanobis(sample, center=center, cov=cov)
cutoff = quantile(distances, 0.90)
custom_plot_heteroskedacity(sample, distances>cutoff, center)

A differs more significantly than B, because points with higher \(x\) should be expected to vary more than points near \(x=0\). But since the Mahalanobis distance is only able to define a tolerance ellipsoid, it does not do such a good job in this case.

Other properties of the data that I believe the Mahalanobis distance would not be able to address well but are not showcased here are: skewness and multimodality.

LS0tDQp0aXRsZTogIk1haGFsYW5vYmlzIERpc3RhbmNlIGFuZCBpdHMgTGltaXRhdGlvbnMiDQpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sNCi0tLQ0KDQpgYGB7ciBzZXR1cCwgaW5jbHVkZT1GfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KG1lc3NhZ2UgPSBGLCB3YXJuaW5nID0gRikNCmBgYA0KDQpgYGB7ciBwYWNrYWdlc30NCmxpYnJhcnkoZHBseXIpDQpsaWJyYXJ5KGdncGxvdDIpDQpsaWJyYXJ5KG12dG5vcm0pDQpsaWJyYXJ5KHJvYnVzdCkNCmBgYA0KDQpgYGB7ciBwbG90dGluZywgaW5jbHVkZT1GfQ0KY3VzdG9tX3Bsb3QgPC0gZnVuY3Rpb24oeCwgaXNfb3V0bGllciwgY2VudGVyKSB7DQogIGdncGxvdChkYXRhLmZyYW1lKHgxPXhbLDFdLCB4Mj14WywyXSwgaXNfb3V0bGllcj1pc19vdXRsaWVyKSwgDQogICAgICAgICBhZXMoeD14MSwgeT14MiwgY29sb3I9aXNfb3V0bGllcikpICsgDQogICAgZ2VvbV9wb2ludCgpICsNCiAgICBhbm5vdGF0ZSgicG9pbnQiLCB4PWNlbnRlclsxXSwgeT1jZW50ZXJbMl0sIGNvbG9yID0gImJsYWNrIiwgc2l6ZT0zKQ0KfQ0KDQpjdXN0b21fcGxvdF9ub19vdXRsaWVycyA8LSBmdW5jdGlvbih4LCBjZW50ZXIpIHsNCiAgZ2dwbG90KGRhdGEuZnJhbWUoeDE9eFssMV0sIHgyPXhbLDJdKSwgDQogICAgICAgICBhZXMoeD14MSwgeT14MikpICsgDQogICAgZ2VvbV9wb2ludChjb2xvcj0idG9tYXRvMSIpICsNCiAgICBhbm5vdGF0ZSgicG9pbnQiLCB4PWNlbnRlclsxXSwgeT1jZW50ZXJbMl0sIGNvbG9yID0gImJsYWNrIiwgc2l6ZT0zKQ0KfQ0KYGBgDQoNCmBgYHtyIG5vcm1zLCBpbmNsdWRlPUZ9DQpldWNsaWRlYW5fbm9ybSA8LSBmdW5jdGlvbiAoeCkge3Jvd1N1bXMoeCoqMil9DQpgYGANCg0KSGVyZSBhcmUgcHJlc2VudGVkIHNvbWUgc2l0dWF0aW9ucyB1c2luZyBhcnRpZmljaWFsbHkgZ2VuZXJhdGVkIGRhdGEgd2hlcmUgdGhlIE1haGFsYW5vYmlzIGRpc3RhbmNlIGRvZXMgYSBnb29kIGFuZCBhIGJhZCBqb2IgZGV0ZWN0aW5nIG91dGxpZXJzLg0KDQojIyBTcGhlcmljYWwgRGF0YQ0KDQpXZSBrbm93IHRoYXQgZm9yIHNwaGVyaWNhbCBkYXRhIChubyBjb3JyZWxhdGlvbiBiZXR3ZWVuIHZhcmlhYmxlcykgdGhlIGV1Y2xpZGVhbiBkaXN0YW5jZSB3b3JrcyBvay4NCg0KYGBge3J9DQpzYW1wbGUgPSBybXZub3JtKDEwMDAsIHNpZ21hPWRpYWcoMikpDQpjZW50ZXIgPSBjb2xNZWFucyhzYW1wbGUpDQpkaXN0YW5jZXMgPSBldWNsaWRlYW5fbm9ybShzYW1wbGUtY2VudGVyKQ0KY3V0b2ZmID0gcXVhbnRpbGUoZGlzdGFuY2VzLCAwLjkwKQ0KY3VzdG9tX3Bsb3Qoc2FtcGxlLCBkaXN0YW5jZXM+Y3V0b2ZmLCBjZW50ZXIpDQpgYGANCg0KIyMgTm9uLVNwaGVyaWNhbCBEYXRhDQoNCkZvciBub24tc3BoZXJpY2FsIGRhdGEgdGhlIGV1Y2xpZGVhbiBub3JtIGRvZXMgbm90IHdvcmsgYXMgd2VsbC4NCg0KYGBge3J9DQpzaWdtYSA9IG1hdHJpeChjKDEsIDAuOCwgMC44LCAxKSwgbmNvbD0yKQ0Kc2FtcGxlID0gcm12bm9ybSgxMDAwLCBzaWdtYT1zaWdtYSkNCmNlbnRlciA9IGNvbE1lYW5zKHNhbXBsZSkNCmRpc3RhbmNlcyA9IGV1Y2xpZGVhbl9ub3JtKHNhbXBsZS1jZW50ZXIpDQpjdXRvZmYgPSBxdWFudGlsZShkaXN0YW5jZXMsIDAuOTApDQpjdXN0b21fcGxvdChzYW1wbGUsIGRpc3RhbmNlcz5jdXRvZmYsIGNlbnRlcikNCmBgYA0KDQpUaGUgTWFoYWxhbm9iaXMgZGlzdGFuY2Ugd29ya3MgYmV0dGVyIHNpbmNlIGl0IGNvbnNpZGVycyB0aGUgY29ycmVsYXRpb24gc3RydWN0dXJlIG9mIHRoZSBkYXRhLg0KDQoNCmBgYHtyfQ0Kc2lnbWEgPSBtYXRyaXgoYygxLCAwLjgsIDAuOCwgMSksIG5jb2w9MikNCnNhbXBsZSA9IHJtdm5vcm0oMTAwMCwgc2lnbWE9c2lnbWEpDQpjZW50ZXIgPSBjb2xNZWFucyhzYW1wbGUpDQpkaXN0YW5jZXMgPSBtYWhhbGFub2JpcyhzYW1wbGUsIGNlbnRlcj1jZW50ZXIsIGNvdj1jb3Yoc2FtcGxlKSkNCmN1dG9mZiA9IHF1YW50aWxlKGRpc3RhbmNlcywgMC45MCkNCmN1c3RvbV9wbG90KHNhbXBsZSwgZGlzdGFuY2VzPmN1dG9mZiwgY2VudGVyKQ0KYGBgDQoNCiMjIE1haGFsYW5vYmlzIERpc3RhbmNlIFJvYnVzdG5lc3MNCg0KVGhlIE1haGFsYW5vYmlzIGRpc3RhbmNlIHRvIHRoZSBjZW50ZXIgb2YgdGhlIGRhdGEgZGVmaW5lZCBhczoNCg0KJCQgZCh4KSA9ICh4LVxtdSledCBcU2lnbWFeey0xfSAoeC1cbXUpJCQNCg0KV2hlcmUgJFxtdSQgaXMgYW4gZXN0aW1hdGlvbiBvZiB0aGUgY2VudGVyIG9mIHRoZSBjbG91ZCBvZiBwb2ludHMsIGdlbmVyYWxseSB0aGUgbWVhbiBhbmQgJFxTaWdtYSQgaXMgYW4gZXN0aW1hdGlvbiBvZiB0aGUgY292YXJpYW5jZSBtYXRyaXguIFRoZXJlZm9yZSB0aGUgTWFoYWxhbm9iaXMgZGlzdGFuY2UgaXMgYXMgZ29vZCBhcyB0aGVzZSBlc3RpbWF0aW9ucyBhcmUuDQoNCldlJ2xsIG5vdyBzZWUgc29tZSBzaG9ydGNvbWluZ3Mgb2YgdGhlIE1haGFsYW5vYmlzIGRpc3RhbmNlIGFuZCBob3cgdG8gZGVhbCB3aXRoIHRoZW0uDQoNCg0KIyMjIEJldHRlciBsb2NhdGlvbiBlc3RpbWF0b3INCg0KV2UgYWxyZWFkeSBrbm93IHRoYXQgdGhlIG1lYW4gaXMgbm90IHZlcnkgcm9idXN0IHRvIG91dGxpZXJzLiBXZSBjYW4gaW1wcm92ZSBvdXIgbG9jYXRpb24gZXN0aW1hdG9yIHRvIGEgbW9yZSByb2J1c3QgYWx0ZXJuYXRpdmUgZGVmaW5lZCBmb3IgYSBzZXQgb2YgcG9pbnRzICR4XzEsIHhfMiBcZG90cyB4X24kIGFzOg0KDQokJFxhcmcgXG1pbl97MSBcbGVxIGkgXGxlcSBufSBcc3VtX3tqPTF9Xm4gXHwgeF9pIC0geF9qIFx8XzIkJA0KDQpPciBpbiBvdGhlciB3b3JkcywgdGhlIHBvaW50IGZyb20gdGhlIHNldCBvZiBwb2ludHMgdGhhdCBtaW5pbWl6ZXMgdGhlIGV1Y2xpZGlhbiBkaXN0YW5jZSB0byBhbGwgdGhlIG90aGVyIHBvaW50cy4NCg0KYGBge3IgZ2VvbWV0cmljX21lZGlhbn0NCmdlb21ldHJpY19tZWRpYW4gPC0gZnVuY3Rpb24gKHNhbXBsZSkgew0KICBldWNsaWRpYW5fZGlzdGFuY2VzID0gYXBwbHkoc2FtcGxlLCAxLCBmdW5jdGlvbiAoeCkge3N1bShldWNsaWRlYW5fbm9ybShzYW1wbGUgLSB4KSl9KQ0KICBzYW1wbGVbd2hpY2gubWluKGV1Y2xpZGlhbl9kaXN0YW5jZXMpLF0NCn0NCmBgYA0KDQpgYGB7cn0NCnNpZ21hMSA9IG1hdHJpeChjKDEsIDAuOCwgMC44LCAxKSwgbmNvbD0yKQ0Kc2lnbWEyID0gbWF0cml4KGMoMSwgMC4zLCAwLjMsIDEpLCBuY29sPTIpDQpzYW1wbGUxID0gcm12bm9ybSgxMDAwLCBzaWdtYT1zaWdtYTEpDQpzYW1wbGUyID0gcm12bm9ybSgxMDAsIG1lYW49YygtMywgOCksIHNpZ21hPXNpZ21hMikNCnNhbXBsZSA9IHJiaW5kKHNhbXBsZTEsIHNhbXBsZTIpDQpjZW50ZXIgPSBjb2xNZWFucyhzYW1wbGUpDQpjdXN0b21fcGxvdF9ub19vdXRsaWVycyhzYW1wbGUsIGNlbnRlcikNCmBgYA0KDQpgYGB7cn0NCnNpZ21hMSA9IG1hdHJpeChjKDEsIDAuOCwgMC44LCAxKSwgbmNvbD0yKQ0Kc2lnbWEyID0gbWF0cml4KGMoMSwgMC4zLCAwLjMsIDEpLCBuY29sPTIpDQpzYW1wbGUxID0gcm12bm9ybSgxMDAwLCBzaWdtYT1zaWdtYTEpDQpzYW1wbGUyID0gcm12bm9ybSgxMDAsIG1lYW49YygtMywgOCksIHNpZ21hPXNpZ21hMikNCnNhbXBsZSA9IHJiaW5kKHNhbXBsZTEsIHNhbXBsZTIpDQpjZW50ZXIgPSBnZW9tZXRyaWNfbWVkaWFuKHNhbXBsZSkNCmN1c3RvbV9wbG90X25vX291dGxpZXJzKHNhbXBsZSwgY2VudGVyKQ0KYGBgDQpXZSBjYW4gc2VlIHRoYXQgdGhpcyBlc3RpbWF0ZSBvZiB0aGUgY2VudGVyIG9mIHRoZSBjbG91ZCBvZiBkYXRhIGlzIG1vcmUgcm9idXN0IHRvIG5vaXNlLg0KDQoNCiMjIyBCZXR0ZXIgc2NhbGUgZXN0aW1hdG9yDQoNCiMjIyMgTWluaW11bSBDb3ZhcmlhbmNlIERldGVybWluYW50DQoNCkEgY2xhc3NpY2FsIGFwcHJvYWNoIHRvIGNvbXB1dGluZyBhIHJvYnVzdCBjb3ZhcmlhbmNlIG1hdHJpeCBpcyB0aGUgdXNlIG9mIHRoZSBNaW5pbXVtIENvdmFyaWFuY2UgRGV0ZXJtaW5hbnQgKE1DRCkuIFRoaXMgbWV0aG9kIG5vdCBvbmx5IHByb3ZpZGVzIGVzdGltYXRvcnMgZm9yIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBidXQgYWxzbyBsb2NhdGlvbiBlc3RpbWF0ZXMuDQoNClRoZSBsb2NhdGlvbiBlc3RpbWF0ZSBvZiBNQ0QsICRcaGF0e1xtdX0kIGlzIHRoZSBtZWFuIG9mIHRoZSAkaCQgb2JzZXJ2YXRpb25zIGZvciB3aGljaCB0aGUgZGV0ZXJtaW5hbnQgb2YgdGhlIGNvdmFyaWFuY2UgbWF0cml4IGlzIG1pbmltYWwuDQoNCiRcaGF0XFNpZ21hJCBpcyB0aGUgY292YXJpYW5jZSBtYXRyaXggb2YgdGhlICRoJCBvYnNlcnZhdGlvbnMgbXVsdGlwbGllZCBieSBhIGNvbnNpc3RlbmN5IGZhY3RvciAkY18wJCAobmVlZGVkIHRvIGFjaGlldmUgY29uc2lzdGVuY3kgb24gbm9ybWFsIGRpc3RyaWJ1dGlvbnMpLg0KDQpUaGUgbWFpbiBwYXJhbWV0ZXIgb2YgdGhpcyBtZXRob2QgaXMgJFxhbHBoYSQsIHRoaXMgdmFsdWUgKnJvdWdobHkqIHJlcHJlc2VudHMgdGhlIHZhbHVlICRoL24kLCB0aGUgcHJvcG9ydGlvbiBvZiBvYnNlcnZhdGlvbnMgdXNlZCBmb3IgdGhlIGVzdGltYXRpb24uIFNpbmNlIHRoZSB2YWx1ZSBvZiAkaCQgbXVzdCBsYXkgYmV0d2VlbiAkKG4gKyBwICsgMSkvMiQgYW5kICRuJCAoZm9yICRuJCBvYnNlcnZhdGlvbnMgb2YgJHAkIHZhcmlhYmxlcyksICRcYWxwaGEkIG11c3QgYmUgYmV0d2VlbiAwLjUgYW5kIDEuIEEgbG93ICRcYWxwaGEkIHRyYW5zbGF0ZXMgaW4gbW9yZSByb2J1c3RuZXNzIGJ1dCBsb3cgY29uc2lzdGVuY3kgYXQgdGhlIG5vcm1hbCBkaXN0cmlidXRpb24sIHdoZXJlYXMgYW4gJFxhbHBoYSQgb2YgMSBpcyBhcyBiYWQgYXMgdGhlIGNsYXNzaWNhbCBzYW1wbGUgY292YXJpYW5jZSBtYXRyaXguDQoNCkEgZ29vZCBpbiBkZXB0aCBleHBsYW5hdGlvbiBvZiBNQ0QgY2FuIGJlIGZvdW5kIFtoZXJlXShodHRwczovL3dpcy5rdWxldXZlbi5iZS9zdGF0L3JvYnVzdC9wYXBlcnMvMjAxMC93aXJlLW1jZC5wZGYpDQoNCg0KIyMjIyBQcm9ibGVtcyB3aXRoIHRoZSBTYW1wbGUgQ292YXJpYW5jZSBNYXRyaXgNCg0KU28gd2UndmUgaW50cm9kdWNlZCBzb21lIG5vaXNlIGFuZCB3ZSBjYW4gc2VlIHRoYXQgdGhlIE1haGFsYW5vYmlzIGRpc3RhbmNlIGRvZXMgbm90IHByb3Blcmx5IGlkZW50aWZ5IHRoZSBvdXRsaWVycy4gVGhpcyBpcyBiZWNhdXNlIHRoZSBoZWF2eSBwcmVzZW5jZSBvZiBvdXRsaWVycyBpbmZsYXRlcyB0aGUgY292YXJpYW5jZSBlc3RpbWF0ZXMgYWxsb3dpbmcgb3V0bGllcnMgdG8gcGFzcyB1bmRldGVjdGVkLg0KDQpgYGB7cn0NCnNpZ21hMSA9IG1hdHJpeChjKDEsIDAuOSwgMC45LCAxKSwgbmNvbD0yKQ0Kc2lnbWEyID0gbWF0cml4KGMoMSwgMC4zLCAwLjMsIDEpLCBuY29sPTIpDQpzYW1wbGUxID0gcm12bm9ybSgxMDAwLCBzaWdtYT1zaWdtYTEpDQpzYW1wbGUyID0gcm12bm9ybSgxMDAsIG1lYW49YygtMiwgMyksIHNpZ21hPXNpZ21hMikNCnNhbXBsZSA9IHJiaW5kKHNhbXBsZTEsIHNhbXBsZTIpDQpjZW50ZXIgPSBjb2xNZWFucyhzYW1wbGUpDQpkaXN0YW5jZXMgPSBtYWhhbGFub2JpcyhzYW1wbGUsIGNlbnRlcj1jZW50ZXIsIGNvdj1jb3Yoc2FtcGxlKSkNCmN1dG9mZiA9IHF1YW50aWxlKGRpc3RhbmNlcywgMC45MCkNCmN1c3RvbV9wbG90KHNhbXBsZSwgZGlzdGFuY2VzPmN1dG9mZiwgY2VudGVyKQ0KYGBgDQoNCmBgYHtyfQ0Kc2lnbWExID0gbWF0cml4KGMoMSwgMC45LCAwLjksIDEpLCBuY29sPTIpDQpzaWdtYTIgPSBtYXRyaXgoYygxLCAwLjMsIDAuMywgMSksIG5jb2w9MikNCnNhbXBsZTEgPSBybXZub3JtKDEwMDAsIHNpZ21hPXNpZ21hMSkNCnNhbXBsZTIgPSBybXZub3JtKDEwMCwgbWVhbj1jKC0yLCAzKSwgc2lnbWE9c2lnbWEyKQ0Kc2FtcGxlID0gcmJpbmQoc2FtcGxlMSwgc2FtcGxlMikNCmNvdi5vYmogPSBjb3ZSb2Ioc2FtcGxlLCBlc3RpbT0ibWNkIiwgYWxwaGE9MC43KQ0KY2VudGVyID0gY292Lm9iaiRjZW50ZXINCmNvdiA9IGNvdi5vYmokY292DQpkaXN0YW5jZXMgPSBtYWhhbGFub2JpcyhzYW1wbGUsIGNlbnRlcj1jZW50ZXIsIGNvdj1jb3YpDQpjdXRvZmYgPSBxdWFudGlsZShkaXN0YW5jZXMsIDAuOTApDQpjdXN0b21fcGxvdChzYW1wbGUsIGRpc3RhbmNlcz5jdXRvZmYsIGNlbnRlcikNCmBgYA0KDQojIE90aGVyIGlzc3Vlcw0KDQpUaGlzIHNlY3Rpb24gZXhoaWJpdHMgc29tZSBsaW1pdGF0aW9ucyBvZiB0aGUgTWFoYWxhbm9iaXMgZGlzdGFuY2UgdGhhdCBJIGRvIG5vdCBrbm93IGhvdyB0byBvdmVyY29tZS4NCg0KIyMgTm9uIExpbmVhcml0eQ0KDQpUaGUgTWFoYWxhbm9iaXMgZGlzdGFuY2UgaXMgb25seSBhYmxlIHRvIGNhcHR1cmUgbGluZWFyIHJlbGF0aW9uc2hpcHMgYmV0d2VlbiB0aGUgdmFyaWFibGVzLiBUaGlzIGNhc2UgcHJlc2VudHMgYSBjdWFkcmF0aWMgcmVsYXRpb25zaGlwIHNvIHRoZSBvdXRsaWVyIGN1dCBoZXJlIGlzIG5vdCBxdWl0ZSByaWdodC4NCg0KYGBge3J9DQp4ID0gcm5vcm0oMTAwMCwgbWVhbj01LCBzZD0yKQ0KeSA9IHJub3JtKDEwMDAsIG1lYW49eF4yLCBzZD0zKQ0Kc2FtcGxlID0gY2JpbmQoeCwgeSkNCmNvdi5vYmogPSBjb3ZSb2Ioc2FtcGxlLCBlc3RpbT0ibWNkIiwgYWxwaGE9MC43KQ0KY2VudGVyID0gY292Lm9iaiRjZW50ZXINCmNvdiA9IGNvdi5vYmokY292DQpkaXN0YW5jZXMgPSBtYWhhbGFub2JpcyhzYW1wbGUsIGNlbnRlcj1jZW50ZXIsIGNvdj1jb3YpDQpjdXRvZmYgPSBxdWFudGlsZShkaXN0YW5jZXMsIDAuOTApDQpjdXN0b21fcGxvdChzYW1wbGUsIGRpc3RhbmNlcz5jdXRvZmYsIGNlbnRlcikNCmBgYA0KDQojIyBIZXRlcm9za2VkYWNpdHkNCg0KV2UgY2FuIGZpbmQgaGV0ZXJvc2tlZGFjaXR5IG9yIGhldGVyb2dlbmVpdHkgb2YgdGhlIHZhcmlhbmNlICB3aGVuIHRoZSB2YXJpYW5jZSBvZiBhIHZhcmlhYmxlIGRlcGVuZHMgb24gdGhlIHZhbHVlIG9mIGFub3RoZXIuIEluIHRoaXMgZXhhbXBsZSB3ZSBjYW4gc2VlIHRoYXQgd2hlbiAkeCQgaW5jcmVhc2VzIG5vdCBvbmx5ICR5JCBpbmNyZWFzZXMgYnV0IGFsc28gdGhlIHZhcmlhYmlsaXR5IG9mICR5JCBpcyBncmVhdGVyLg0KDQpgYGB7ciBoZXRlcm9za2VkYWNpdHlfcGxvdCwgaW5jbHVkZT1GfQ0KY3VzdG9tX3Bsb3RfaGV0ZXJvc2tlZGFjaXR5IDwtIGZ1bmN0aW9uKHgsIGlzX291dGxpZXIsIGNlbnRlcikgew0KICBwb2ludHNfeCA9IGMoMC4zLCAyKQ0KICBwb2ludHNfeSA9IGMoMC43LCAyLjcpDQogIGN1c3RvbV9wbG90KHgsIGlzX291dGxpZXIsIGNlbnRlcikgKw0KICAgIGFubm90YXRlKCJwb2ludCIsIHg9cG9pbnRzX3gsIHk9cG9pbnRzX3ksIGNvbG9yID0gImJsYWNrIiwgc2l6ZT0zLCBzaGFwZT00KSArDQogICAgYW5ub3RhdGUoInRleHQiLCB4PXBvaW50c194LTAuMSwgeT1wb2ludHNfeSswLjUsIGxhYmVsPWMoIkEiLCAiQiIpKQ0KfQ0KYGBgDQoNCmBgYHtyfQ0KeCA9IHJnYW1tYSgxMDAwLCBzaGFwZT0xLCBzY2FsZT0xKQ0KeSA9IHJub3JtKDEwMDAsIG1lYW49eCwgc2Q9MC4yKngpDQpzYW1wbGUgPSBjYmluZCh4LCB5KQ0KY292Lm9iaiA9IGNvdlJvYihzYW1wbGUsIGVzdGltPSJtY2QiLCBhbHBoYT0wLjcpDQpjZW50ZXIgPSBjb3Yub2JqJGNlbnRlcg0KY292ID0gY292Lm9iaiRjb3YNCmRpc3RhbmNlcyA9IG1haGFsYW5vYmlzKHNhbXBsZSwgY2VudGVyPWNlbnRlciwgY292PWNvdikNCmN1dG9mZiA9IHF1YW50aWxlKGRpc3RhbmNlcywgMC45MCkNCmN1c3RvbV9wbG90X2hldGVyb3NrZWRhY2l0eShzYW1wbGUsIGRpc3RhbmNlcz5jdXRvZmYsIGNlbnRlcikNCmBgYA0KDQpBIGRpZmZlcnMgbW9yZSBzaWduaWZpY2FudGx5IHRoYW4gQiwgYmVjYXVzZSBwb2ludHMgd2l0aCBoaWdoZXIgJHgkIHNob3VsZCBiZSBleHBlY3RlZCB0byB2YXJ5IG1vcmUgdGhhbiBwb2ludHMgbmVhciAkeD0wJC4gQnV0IHNpbmNlIHRoZSBNYWhhbGFub2JpcyBkaXN0YW5jZSBpcyBvbmx5IGFibGUgdG8gZGVmaW5lIGEgdG9sZXJhbmNlIGVsbGlwc29pZCwgaXQgZG9lcyBub3QgZG8gc3VjaCBhIGdvb2Qgam9iIGluIHRoaXMgY2FzZS4NCg0KDQoNCjwhLS0gIyMgU2tld25lc3MgLS0+DQoNCmBgYHtyIHNrZXduZXNzX3Bsb3QsIGluY2x1ZGU9Rn0NCmN1c3RvbV9wbG90X3NrZXduZXNzIDwtIGZ1bmN0aW9uKHgsIGlzX291dGxpZXIsIGNlbnRlcikgew0KICBwb2ludHNfeCA9IGMoMTAsIDMwKQ0KICBwb2ludHNfeSA9IGMoMTAsIDMwKQ0KICBjdXN0b21fcGxvdCh4LCBpc19vdXRsaWVyLCBjZW50ZXIpICsNCiAgICBhbm5vdGF0ZSgicG9pbnQiLCB4PXBvaW50c194LCB5PXBvaW50c195LCBjb2xvciA9ICJibGFjayIsIHNpemU9Mywgc2hhcGU9NCkgKw0KICAgIGFubm90YXRlKCJ0ZXh0IiwgeD1wb2ludHNfeC0xLCB5PXBvaW50c195KzEsIGxhYmVsPWMoIkEiLCAiQiIpLCBzaXplPTUpDQp9DQpgYGANCg0KPCEtLSBUaGlzIGRpc3RyaWJ1dGlvbiBpcyBwb3NpdGl2ZWx5IHNrZXdlZCwgc28gdGhlcmUgYXJlIG1vcmUgcG9pbnRzICAtLT4NCg0KDQpgYGB7ciwgaW5jbHVkZT1GfQ0KeCA9IHJnYW1tYSgzMDAwLCBzaGFwZT0xMCwgc2NhbGU9MikNCnkgPSBybm9ybSgzMDAwLCBtZWFuPXgsIHNkPTUpDQpzYW1wbGUgPSBjYmluZCh4LCB5KQ0KY292Lm9iaiA9IGNvdlJvYihzYW1wbGUsIGVzdGltPSJtY2QiLCBhbHBoYT0wLjcpDQpjZW50ZXIgPSBjb3Yub2JqJGNlbnRlcg0KY292ID0gY292Lm9iaiRjb3YNCmRpc3RhbmNlcyA9IG1haGFsYW5vYmlzKHNhbXBsZSwgY2VudGVyPWNlbnRlciwgY292PWNvdikNCmN1dG9mZiA9IHF1YW50aWxlKGRpc3RhbmNlcywgMC45MCkNCmN1c3RvbV9wbG90X3NrZXduZXNzKHNhbXBsZSwgZGlzdGFuY2VzPmN1dG9mZiwgY2VudGVyKQ0KYGBgDQoNCk90aGVyIHByb3BlcnRpZXMgb2YgdGhlIGRhdGEgdGhhdCBJIGJlbGlldmUgdGhlIE1haGFsYW5vYmlzIGRpc3RhbmNlIHdvdWxkIG5vdCBiZSBhYmxlIHRvIGFkZHJlc3Mgd2VsbCBidXQgYXJlIG5vdCBzaG93Y2FzZWQgaGVyZSBhcmU6IHNrZXduZXNzIGFuZCBtdWx0aW1vZGFsaXR5Lg0KDQo=