Introduction

Gajardo, Alvaro, Satarupa Bhattacharjee, Cody Carroll, Yaqing Chen, Xiongtao Dai, Jianing Fan, Pantelis Z. Hadjipantelis, et al. (2021). fdapace: Functional Data Analysis and Empirical Dynamics. https://CRAN.R-project.org/package=fdapace

FPCA in R using fdapace

Install

Let’s install the fdapace package first.

install.packages('fdapace')

Load the Package

You know that the package is called before using it.

library(fdapace)

Basic Notation

Data

  • one has two lists yList and tList
  • yList = a list of vectors each containing the observed values \(Y_{ij}\) for the ith subject
  • tList = a list of vectors containing corresponding time points

Model Function

FPCAobj <- FPCA(Ly = yList, Lt = tList)

Toy Example

Data

Let’s generate a toy dense functional dataset!

##### SET #####
M <- 200 #number of measurements per subjects
N <- 100 # the number of subjects
set.seed(123) #for bootstrap
##### DEFINE ####
s <- seq(0,10,length.out = M) #from 0 to 10, time length 200(=M)
# generating functions
meanFunct <- function(s) s+10*exp(-(s-5)^2)
eigFunct1 <- function(s) cos(2*s*pi/10)/sqrt(5)
eigFunct2 <- function(s) sin(2*s*pi/10)/sqrt(5)

meanFunct \(y=s+10{e}^{{-(s-5)}^{2}}\)

plot(s,meanFunct(s),type='l')

The first eigen function is \(y=\frac{cos(\frac{2s\pi}{10})}{\sqrt{5}}\)

plot(s,eigFunct1(s),type='l',col='red')

The second eigen function is \(\frac{-sin(\frac{2s\pi}{10})}{\sqrt{5}}\)

plot(s,eigFunct2(s),type='l',col='blue')

Random residuals for eigen effects

Ksi <- matrix(rnorm(N*2),ncol=2)
head(Ksi)
            [,1]        [,2]
[1,] -0.56047565 -0.71040656
[2,] -0.23017749  0.25688371
[3,]  1.55870831 -0.24669188
[4,]  0.07050839 -0.34754260
[5,]  0.12928774 -0.95161857
[6,]  1.71506499 -0.04502772
  • 1st column = eigen 1
  • 2nd column = eigne 2
  • for N subjects (counting number, of course)
  • Distributions are from Normal PDF

Centering of matrix

Ksi <- apply(Ksi,2,scale)
head(Ksi)
            [,1]       [,2]
[1,] -0.71304802 -0.6234417
[2,] -0.35120270  0.3768723
[3,]  1.60854170 -0.1438956
[4,] -0.02179795 -0.2481894
[5,]  0.04259548 -0.8728888
[6,]  1.77983218  0.0646535

Mean = 0

round(colMeans(Ksi))
[1] 0 0

Scale up by 5 and 2 for each (just for fun…)

Ksi <- Ksi %*% diag(c(5,2))
head(Ksi,n=10)
            [,1]       [,2]
 [1,] -3.5652401 -1.2468834
 [2,] -1.7560135  0.7537447
 [3,]  8.0427085 -0.2877911
 [4,] -0.1089898 -0.4963787
 [5,]  0.2129774 -1.7457776
 [6,]  8.8991609  0.1293070
 [7,]  2.0294909 -1.4009660
 [8,] -7.4246470 -3.2273356
 [9,] -4.2574783 -0.5639783
[10,] -2.9363418  2.1231802

Creating \(Y_{true}\)

\[ Y_{true}=E_{Njk}+\mu_{Nk}+\epsilon_{Nj} \]

yTrue <- Ksi %*% t(matrix(c(eigFunct1(s),eigFunct2(s)),ncol=2)) + t(matrix(rep(meanFunct(s),N),nrow=M))
  • Effects from eigen vectors
  • Effects from a mean latent function
  • Effects from random residuals

The shape is 100(=N, subjects) by 200(=M, time length data, i.e., measurements)

dim(yTrue)
[1] 100 200

Running FPCA on a dense dataset

L3 <- MakeFPCAInputs(
  IDs = rep(1:N, each=M), # like, 1 1 1 2 2 2 3 3 3 for rep(1:3, each=3)
  tVec = rep(s,N), # like 1 2 1 2 1 2 for rep(1:2,3)
  t(yTrue) #row = time, column = subject
)

Let’s do it!

FPCAdense <- FPCA(L3$Ly,L3$Lt)

Results

plot(FPCAdense)

As we expected, * mean- and eigen functiosn are separaeted and all predicted as they are * In the scree plot, two principal components explain almost everything

Let’s extract those.

meanOfResult <- FPCAdense$mu
phi1 <- FPCAdense$phi[,1]
phi2 <- FPCAdense$phi[,2]
library(scales) #for alpha()
par(mfrow=c(2,2)) # 2 by 2 plot areas
# area 1,1 (for all subject data)
plot(1,type='n',xlab='time',ylab='value',xlim=c(min(s),max(s)),ylim=c(min(yTrue),max(yTrue)))
for(i in 1:100) {
  lines(x=s,y=yTrue[i,],col=alpha('gray',0.2))
}
plot(s,meanOfResult,type='l',col='red')
plot(s,phi1,type='l',col='blue')
plot(s,phi2,type='l',col='green')

par(mfrow=c(1,1)) #back to normal

This package works like magic!

Running FPCA on a sparse and noisy dataset

Now, let’s see how the PACE algorithm works.

ySparse <- Sparsify(yTrue,s,sparsity = c(1:5)) #generating sparse data (measurements from 1 to 5 points)

Now noise.

ySparse$yNoisy <- lapply(ySparse$Ly,function(x) x+0.5*rnorm(length(x)))

Run

FPCAsparse <- FPCA(ySparse$yNoisy, ySparse$Lt)

Result

plot(FPCAsparse)

Now let’s consider cumulative functional variance to determine a proper number of principal factors.

FPCAsparse$cumFVE
[1] 0.7704850 0.9332069 0.9891502 0.9993241

For your information, the sparse data look like this:

par(mfrow=c(1,2))
#for dense data
par(mfrow=c(2,2)) # 2 by 2 plot areas
# area 1,1 (for all subject data)
plot(1,type='n',xlab='time',ylab='value',xlim=c(min(s),max(s)),ylim=c(min(yTrue),max(yTrue)),
     main="Dense Data")
for(i in 1:100) {
  lines(x=s,y=yTrue[i,],col=alpha('green',0.2))
}
#for sparse data
plot(1,type='n',xlab='time',ylab='value',
     xlim=c(min(unlist(ySparse$Lt)),max(unlist(ySparse$Lt))),
     ylim=c(min(unlist(ySparse$Ly)),max(unlist(ySparse$Ly))),
     main="Sparse Data")
for(i in 1:100) {
  x=ySparse$Lt[[i]]
  y=ySparse$Ly[[i]]
  lines(x,y,col=alpha('red',0.2))
}
par(mfrow=c(1,1))

Estimate path plots: let’s create the fitted sample path plot based on the results from the parse data.

CreatePathPlot(FPCAsparse)

Prediction grid:

SelectK(FPCAsparse,criterion='AIC')
$K
[1] 2

$criterion
[1] 515.5021
# K=SelectK(FPCAsparse,criterion='AIC')$K
predSparse <- predict(FPCAsparse,ySparse$Ly,ySparse$Lt,K=2) #number of PCA = 2

Number of samples in ySparse:

length(ySparse$Lt)
[1] 100

Number of predictions:

nrow(predSparse$scores)
[1] 100
head(predSparse$scores)
           [,1]        [,2]
[1,]  1.8118913 -1.25381426
[2,]  0.6427877 -0.18594988
[3,] -5.8391469 -0.74846297
[4,]  1.9361811  0.07853147
[5,]  3.0165165 -0.43987666
[6,] -6.1766873 -1.29560020

Real-world Example

Introduction

  • medfly25 dataset: this is a dataset containing the eggs laid from 789 medflies during the first 25 days of their lives. (see also, Carey et al. 1998))

Carey, J. R., Liedo, P., Müller, H. G., Wang, J. L., & Chiou, J. M. (1998). Relationship of age patterns of fecundity to mortality, longevity, and lifetime reproduction in a large cohort of Mediterranean fruit fly females. The Journals of Gerontology Series A: Biological Sciences and Medical Sciences, 53(4), B245-B251.

  • The data are rather noisy, dense and with a characteristic flat start.

Data

head(medfly25)
N <- nrow(medfly25)
library(scales)
library(ggplot2)
library(dplyr)

Attaching package: ‘dplyr’

The following objects are masked from ‘package:stats’:

    filter, lag

The following objects are masked from ‘package:base’:

    intersect, setdiff, setequal, union
library(gridExtra)

Attaching package: ‘gridExtra’

The following object is masked from ‘package:dplyr’:

    combine
g1 <- medfly25 %>% 
  ggplot(aes(x=Days,y=nEggs,group=ID)) +
  geom_line(alpha=0.2,color='gray') +
  geom_smooth(aes(group=1),se=FALSE)+
  theme_bw() +
  labs(x="Days",y="Number of Eggs") +
  ggtitle("Medflies - Time Series Plot")

g2 <-medfly25 %>% 
  ggplot(aes(x=Days,y=nEggs)) +
  geom_density_2d_filled() +
  scale_fill_brewer()+
  theme_bw() +
  labs(x="Days",y="Number of Eggs") +
  ggtitle("Medflies - Density Plot") +
  theme(legend.position='none')

grid.arrange(g1,g2,ncol=2)

FPCA

Flies <- MakeFPCAInputs(medfly25$ID,medfly25$Days,medfly25$nEggs)
fpcaObjFlies <- FPCA(Flies$Ly,Flies$Lt,
                     list(plot=TRUE,
                          methodMuCovEst='smooth',
                          userBwCov=2))

Select number of K (see, Yao et al., 2005)

Yao, F., Müller, H. G., & Wang, J. L. (2005). Functional data analysis for sparse longitudinal data. Journal of the American statistical association, 100(470), 577-590.

numK <- SelectK(fpcaObjFlies,criterion = "AIC")
numK
$K
[1] 1

$criterion
[1] 29270.35
K <- numK$K
g<-CreatePathPlot(fpcaObjFlies)

g
NULL
medfly25[medfly25$ID==unique(medfly25$ID)[c(3,5,135)],] %>% 
  ggplot(aes(x=Days,y=nEggs,color=as.factor(ID))) +
  geom_line()

par(mfrow=c(2,2))
  CreatePathPlot(fpcaObjFlies,subset=c(3,5,135))
  CreatePathPlot(fpcaObjFlies,subset=c(3,5,135),K=1,main="K=1",pch=4)
  CreatePathPlot(fpcaObjFlies,subset=c(3,5,135),K=3,main="K=3",pch=4)
  CreatePathPlot(fpcaObjFlies,subset=c(3,5,135),K=4,main="K=4",pch=4)
par(mfrow=c(1,1))

The following sections contain descriptions about optional functions in fdapace.

  • Outlier detection (Febrero et al., 2007)

Febrero, M., Galeano, P., & González-Manteiga, W. (2007). A functional analysis of NOx levels: location and scale estimation and outlier detection. Computational Statistics, 22(3), 411-427.

  • Functional box-plot (Hyndman and Shang, 2010)

Hyndman, R. J., & Shang, H. L. (2010). Rainbow plots, bagplots, and boxplots for functional data. Journal of Computational and Graphical Statistics, 19(1), 29-45.

  • KDE: Kernel density estimation: it is a non-parametric method to estimate the PDF of a random variable based on kernels as weights.
CreateOutliersPlot(fpcaObjFlies,optns=list(K=3,variant='KDE'))

  • The green line corresponds to the functional median, the dark gray area to the area spanned by the curves within the 25th and 75th percentile and the light gray to the area spanned by the curves within the 2.5th and 97.5th percentile.
CreateFuncBoxPlot(fpcaObjFlies,xlab="Days",ylab="Number of eggs",
                  optns=list(K=3,variant="bagplot"))
Warning: Cannot use bagplot because aplpack::compute.bagplot is unavailable; reverting to point-wise

LS0tCnRpdGxlOiAiRnVuY3Rpb25hbCBQQ0EgQW5hbHlzaXMgVXNpbmcgUEFDRSBBcHByb2FjaCIKb3V0cHV0OiBodG1sX25vdGVib29rCi0tLQoKIyBJbnRyb2R1Y3Rpb24KKiBBIGJyaWVmIGludHJvZHVjdGlvbiB0byB0aGUgcGFja2FnZSBmZGFwYWNlIChHYWphcmRvIGV0IGFsLiAyMDIxKQoKPiBHYWphcmRvLCBBbHZhcm8sIFNhdGFydXBhIEJoYXR0YWNoYXJqZWUsIENvZHkgQ2Fycm9sbCwgWWFxaW5nIENoZW4sIFhpb25ndGFvIERhaSwgSmlhbmluZyBGYW4sIFBhbnRlbGlzIFouIEhhZGppcGFudGVsaXMsIGV0IGFsLiAoMjAyMSkuIGZkYXBhY2U6IEZ1bmN0aW9uYWwgRGF0YSBBbmFseXNpcyBhbmQgRW1waXJpY2FsIER5bmFtaWNzLiBodHRwczovL0NSQU4uUi1wcm9qZWN0Lm9yZy9wYWNrYWdlPWZkYXBhY2UgCgoqIFBBQ0UgaXMgYW4gYWxnb3JpdGhtIGZvciBzcGFyc2UgZGF0YSBjYXNlcyBpbiBGREEuCiogaHR0cHM6Ly93d3cuanN0b3Iub3JnL3N0YWJsZS8yNzU5MDU3OSAKKiBBdXRob3I6IFRhZWt5dW5nIEtpbSAoUGhELiksIEFzc29jaWF0ZSBQcm9mZXNzb3IsIEt3YW5nd29vbiBVbml2ZXJzaXR5LCBLb3JlYQoqIFRoaXMgZG9jdW1lbnQgaXMgb3JpZ2luYXRlZCBmcm9tIGBodHRwczovL2NyYW4uci1wcm9qZWN0Lm9yZy93ZWIvcGFja2FnZXMvZmRhcGFjZS92aWduZXR0ZXMvZmRhcGFjZVZpZy5odG1sYC4KCiMgRlBDQSBpbiBSIHVzaW5nIGZkYXBhY2UKCiMjIEluc3RhbGwKTGV0J3MgaW5zdGFsbCB0aGUgYGZkYXBhY2VgIHBhY2thZ2UgZmlyc3QuCmBgYHtyIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9Cmluc3RhbGwucGFja2FnZXMoJ2ZkYXBhY2UnKQpgYGAKCiMjIExvYWQgdGhlIFBhY2thZ2UKCllvdSBrbm93IHRoYXQgdGhlIHBhY2thZ2UgaXMgY2FsbGVkIGJlZm9yZSB1c2luZyBpdC4KYGBge3J9CmxpYnJhcnkoZmRhcGFjZSkKYGBgCgojIyBCYXNpYyBOb3RhdGlvbgoKIyMjIERhdGEKKiBvbmUgaGFzIHR3byBsaXN0cyBgeUxpc3RgIGFuZCBgdExpc3RgIAoqIGB5TGlzdGAgPSBhIGxpc3Qgb2YgdmVjdG9ycyBlYWNoIGNvbnRhaW5pbmcgdGhlIG9ic2VydmVkIHZhbHVlcyAkWV97aWp9JCBmb3IgdGhlIF9pdGhfIHN1YmplY3QKKiBgdExpc3RgID0gYSBsaXN0IG9mIHZlY3RvcnMgY29udGFpbmluZyBjb3JyZXNwb25kaW5nIHRpbWUgcG9pbnRzCgojIyMgTW9kZWwgRnVuY3Rpb24KYGBgCkZQQ0FvYmogPC0gRlBDQShMeSA9IHlMaXN0LCBMdCA9IHRMaXN0KQpgYGAKCiMgVG95IEV4YW1wbGUKCiMjIERhdGEKTGV0J3MgZ2VuZXJhdGUgYSB0b3kgZGVuc2UgZnVuY3Rpb25hbCBkYXRhc2V0IQoKYGBge3J9CiMjIyMjIFNFVCAjIyMjIwpNIDwtIDIwMCAjbnVtYmVyIG9mIG1lYXN1cmVtZW50cyBwZXIgc3ViamVjdHMKTiA8LSAxMDAgIyB0aGUgbnVtYmVyIG9mIHN1YmplY3RzCnNldC5zZWVkKDEyMykgI2ZvciBib290c3RyYXAKIyMjIyMgREVGSU5FICMjIyMKcyA8LSBzZXEoMCwxMCxsZW5ndGgub3V0ID0gTSkgI2Zyb20gMCB0byAxMCwgdGltZSBsZW5ndGggMjAwKD1NKQojIGdlbmVyYXRpbmcgZnVuY3Rpb25zCm1lYW5GdW5jdCA8LSBmdW5jdGlvbihzKSBzKzEwKmV4cCgtKHMtNSleMikKZWlnRnVuY3QxIDwtIGZ1bmN0aW9uKHMpIGNvcygyKnMqcGkvMTApL3NxcnQoNSkKZWlnRnVuY3QyIDwtIGZ1bmN0aW9uKHMpIHNpbigyKnMqcGkvMTApL3NxcnQoNSkKCmBgYAoKYG1lYW5GdW5jdGAgJHk9cysxMHtlfV57ey0ocy01KX1eezJ9fSQKYGBge3J9CnBsb3QocyxtZWFuRnVuY3QocyksdHlwZT0nbCcpCmBgYAoKVGhlIGZpcnN0IGVpZ2VuIGZ1bmN0aW9uIGlzICR5PVxmcmFje2NvcyhcZnJhY3syc1xwaX17MTB9KX17XHNxcnR7NX19JApgYGB7cn0KcGxvdChzLGVpZ0Z1bmN0MShzKSx0eXBlPSdsJyxjb2w9J3JlZCcpCmBgYAoKVGhlIHNlY29uZCBlaWdlbiBmdW5jdGlvbiBpcyAkXGZyYWN7LXNpbihcZnJhY3syc1xwaX17MTB9KX17XHNxcnR7NX19JAoKYGBge3J9CnBsb3QocyxlaWdGdW5jdDIocyksdHlwZT0nbCcsY29sPSdibHVlJykKYGBgCgpSYW5kb20gcmVzaWR1YWxzIGZvciBlaWdlbiBlZmZlY3RzCgpgYGB7cn0KS3NpIDwtIG1hdHJpeChybm9ybShOKjIpLG5jb2w9MikKaGVhZChLc2kpCmBgYAoKKiAxc3QgY29sdW1uID0gZWlnZW4gMQoqIDJuZCBjb2x1bW4gPSBlaWduZSAyCiogZm9yIE4gc3ViamVjdHMgKGNvdW50aW5nIG51bWJlciwgb2YgY291cnNlKQoqIERpc3RyaWJ1dGlvbnMgYXJlIGZyb20gTm9ybWFsIFBERgoKQ2VudGVyaW5nIG9mIG1hdHJpeApgYGB7cn0KS3NpIDwtIGFwcGx5KEtzaSwyLHNjYWxlKQpoZWFkKEtzaSkKYGBgCgpNZWFuID0gMApgYGB7cn0Kcm91bmQoY29sTWVhbnMoS3NpKSkKYGBgCgpTY2FsZSB1cCBieSA1IGFuZCAyIGZvciBlYWNoIChqdXN0IGZvciBmdW4uLi4pCmBgYHtyfQpLc2kgPC0gS3NpICUqJSBkaWFnKGMoNSwyKSkKaGVhZChLc2ksbj0xMCkKYGBgCgpDcmVhdGluZyAkWV97dHJ1ZX0kCgokJApZX3t0cnVlfT1FX3tOamt9K1xtdV97Tmt9K1xlcHNpbG9uX3tOan0KJCQKYGBge3J9CnlUcnVlIDwtIEtzaSAlKiUgdChtYXRyaXgoYyhlaWdGdW5jdDEocyksZWlnRnVuY3QyKHMpKSxuY29sPTIpKSArIHQobWF0cml4KHJlcChtZWFuRnVuY3QocyksTiksbnJvdz1NKSkKYGBgCgoqIEVmZmVjdHMgZnJvbSBlaWdlbiB2ZWN0b3JzCiogRWZmZWN0cyBmcm9tIGEgbWVhbiBsYXRlbnQgZnVuY3Rpb24KKiBFZmZlY3RzIGZyb20gcmFuZG9tIHJlc2lkdWFscwoKVGhlIHNoYXBlIGlzIDEwMCg9Tiwgc3ViamVjdHMpIGJ5IDIwMCg9TSwgdGltZSBsZW5ndGggZGF0YSwgaS5lLiwgbWVhc3VyZW1lbnRzKQoKYGBge3J9CmRpbSh5VHJ1ZSkKYGBgCgojIyBSdW5uaW5nIEZQQ0Egb24gYSBkZW5zZSBkYXRhc2V0CgpgYGB7cn0KTDMgPC0gTWFrZUZQQ0FJbnB1dHMoCiAgSURzID0gcmVwKDE6TiwgZWFjaD1NKSwgIyBsaWtlLCAxIDEgMSAyIDIgMiAzIDMgMyBmb3IgcmVwKDE6MywgZWFjaD0zKQogIHRWZWMgPSByZXAocyxOKSwgIyBsaWtlIDEgMiAxIDIgMSAyIGZvciByZXAoMToyLDMpCiAgdCh5VHJ1ZSkgI3JvdyA9IHRpbWUsIGNvbHVtbiA9IHN1YmplY3QKKQpgYGAKCkxldCdzIGRvIGl0IQpgYGB7cn0KRlBDQWRlbnNlIDwtIEZQQ0EoTDMkTHksTDMkTHQpCmBgYAoKIyMjIFJlc3VsdHMKCmBgYHtyfQpwbG90KEZQQ0FkZW5zZSkKYGBgCkFzIHdlIGV4cGVjdGVkLAoqIG1lYW4tIGFuZCBlaWdlbiBmdW5jdGlvc24gYXJlIHNlcGFyYWV0ZWQgYW5kIGFsbCBwcmVkaWN0ZWQgYXMgdGhleSBhcmUKKiBJbiB0aGUgc2NyZWUgcGxvdCwgdHdvIHByaW5jaXBhbCBjb21wb25lbnRzIGV4cGxhaW4gYWxtb3N0IGV2ZXJ5dGhpbmcKCkxldCdzIGV4dHJhY3QgdGhvc2UuCgpgYGB7cn0KbWVhbk9mUmVzdWx0IDwtIEZQQ0FkZW5zZSRtdQpwaGkxIDwtIEZQQ0FkZW5zZSRwaGlbLDFdCnBoaTIgPC0gRlBDQWRlbnNlJHBoaVssMl0KYGBgCgpgYGB7cn0KbGlicmFyeShzY2FsZXMpICNmb3IgYWxwaGEoKQpwYXIobWZyb3c9YygyLDIpKSAjIDIgYnkgMiBwbG90IGFyZWFzCiMgYXJlYSAxLDEgKGZvciBhbGwgc3ViamVjdCBkYXRhKQpwbG90KDEsdHlwZT0nbicseGxhYj0ndGltZScseWxhYj0ndmFsdWUnLHhsaW09YyhtaW4ocyksbWF4KHMpKSx5bGltPWMobWluKHlUcnVlKSxtYXgoeVRydWUpKSkKZm9yKGkgaW4gMToxMDApIHsKICBsaW5lcyh4PXMseT15VHJ1ZVtpLF0sY29sPWFscGhhKCdncmF5JywwLjIpKQp9CnBsb3QocyxtZWFuT2ZSZXN1bHQsdHlwZT0nbCcsY29sPSdyZWQnKQpwbG90KHMscGhpMSx0eXBlPSdsJyxjb2w9J2JsdWUnKQpwbG90KHMscGhpMix0eXBlPSdsJyxjb2w9J2dyZWVuJykKCnBhcihtZnJvdz1jKDEsMSkpICNiYWNrIHRvIG5vcm1hbApgYGAKClRoaXMgcGFja2FnZSB3b3JrcyBsaWtlIG1hZ2ljIQoKIyMgUnVubmluZyBGUENBIG9uIGEgc3BhcnNlIGFuZCBub2lzeSBkYXRhc2V0CgpOb3csIGxldCdzIHNlZSBob3cgdGhlIFBBQ0UgYWxnb3JpdGhtIHdvcmtzLgoKYGBge3J9CnlTcGFyc2UgPC0gU3BhcnNpZnkoeVRydWUscyxzcGFyc2l0eSA9IGMoMTo1KSkgI2dlbmVyYXRpbmcgc3BhcnNlIGRhdGEgKG1lYXN1cmVtZW50cyBmcm9tIDEgdG8gNSBwb2ludHMpCmBgYAoKTm93IG5vaXNlLgoKYGBge3J9CnlTcGFyc2UkeU5vaXN5IDwtIGxhcHBseSh5U3BhcnNlJEx5LGZ1bmN0aW9uKHgpIHgrMC41KnJub3JtKGxlbmd0aCh4KSkpCmBgYAoKUnVuCmBgYHtyfQpGUENBc3BhcnNlIDwtIEZQQ0EoeVNwYXJzZSR5Tm9pc3ksIHlTcGFyc2UkTHQpCmBgYAoKUmVzdWx0CmBgYHtyfQpwbG90KEZQQ0FzcGFyc2UpCmBgYAoKTm93IGxldCdzIGNvbnNpZGVyIGN1bXVsYXRpdmUgZnVuY3Rpb25hbCB2YXJpYW5jZSB0byBkZXRlcm1pbmUgYSBwcm9wZXIgbnVtYmVyIG9mIHByaW5jaXBhbCBmYWN0b3JzLgoKYGBge3J9CkZQQ0FzcGFyc2UkY3VtRlZFCmBgYAoKRm9yIHlvdXIgaW5mb3JtYXRpb24sIHRoZSBzcGFyc2UgZGF0YSBsb29rIGxpa2UgdGhpczoKCmBgYHtyfQpwYXIobWZyb3c9YygxLDIpKQojZm9yIGRlbnNlIGRhdGEKcGFyKG1mcm93PWMoMiwyKSkgIyAyIGJ5IDIgcGxvdCBhcmVhcwojIGFyZWEgMSwxIChmb3IgYWxsIHN1YmplY3QgZGF0YSkKcGxvdCgxLHR5cGU9J24nLHhsYWI9J3RpbWUnLHlsYWI9J3ZhbHVlJyx4bGltPWMobWluKHMpLG1heChzKSkseWxpbT1jKG1pbih5VHJ1ZSksbWF4KHlUcnVlKSksCiAgICAgbWFpbj0iRGVuc2UgRGF0YSIpCmZvcihpIGluIDE6MTAwKSB7CiAgbGluZXMoeD1zLHk9eVRydWVbaSxdLGNvbD1hbHBoYSgnZ3JlZW4nLDAuMikpCn0KI2ZvciBzcGFyc2UgZGF0YQpwbG90KDEsdHlwZT0nbicseGxhYj0ndGltZScseWxhYj0ndmFsdWUnLAogICAgIHhsaW09YyhtaW4odW5saXN0KHlTcGFyc2UkTHQpKSxtYXgodW5saXN0KHlTcGFyc2UkTHQpKSksCiAgICAgeWxpbT1jKG1pbih1bmxpc3QoeVNwYXJzZSRMeSkpLG1heCh1bmxpc3QoeVNwYXJzZSRMeSkpKSwKICAgICBtYWluPSJTcGFyc2UgRGF0YSIpCmZvcihpIGluIDE6MTAwKSB7CiAgeD15U3BhcnNlJEx0W1tpXV0KICB5PXlTcGFyc2UkTHlbW2ldXQogIGxpbmVzKHgseSxjb2w9YWxwaGEoJ3JlZCcsMC4yKSkKfQpwYXIobWZyb3c9YygxLDEpKQpgYGAKCkVzdGltYXRlIHBhdGggcGxvdHM6IGxldCdzIGNyZWF0ZSB0aGUgZml0dGVkIHNhbXBsZSBwYXRoIHBsb3QgYmFzZWQgb24gdGhlIHJlc3VsdHMgZnJvbSB0aGUgcGFyc2UgZGF0YS4KCmBgYHtyfQpDcmVhdGVQYXRoUGxvdChGUENBc3BhcnNlKQpgYGAKClByZWRpY3Rpb24gZ3JpZDoKCmBgYHtyfQpTZWxlY3RLKEZQQ0FzcGFyc2UsY3JpdGVyaW9uPSdBSUMnKQojIEs9U2VsZWN0SyhGUENBc3BhcnNlLGNyaXRlcmlvbj0nQUlDJykkSwpwcmVkU3BhcnNlIDwtIHByZWRpY3QoRlBDQXNwYXJzZSx5U3BhcnNlJEx5LHlTcGFyc2UkTHQsSz0yKSAjbnVtYmVyIG9mIFBDQSA9IDIKYGBgCgpOdW1iZXIgb2Ygc2FtcGxlcyBpbiB5U3BhcnNlOgpgYGB7cn0KbGVuZ3RoKHlTcGFyc2UkTHQpCmBgYAoKTnVtYmVyIG9mIHByZWRpY3Rpb25zOgpgYGB7cn0KbnJvdyhwcmVkU3BhcnNlJHNjb3JlcykKYGBgCgpgYGB7cn0KaGVhZChwcmVkU3BhcnNlJHNjb3JlcykKYGBgCgojIFJlYWwtd29ybGQgRXhhbXBsZQojIyBJbnRyb2R1Y3Rpb24KKiBtZWRmbHkyNSBkYXRhc2V0OiB0aGlzIGlzIGEgZGF0YXNldCBjb250YWluaW5nIHRoZSBlZ2dzIGxhaWQgZnJvbSA3ODkgbWVkZmxpZXMgZHVyaW5nIHRoZSBmaXJzdCAyNSBkYXlzIG9mIHRoZWlyIGxpdmVzLiAoc2VlIGFsc28sIENhcmV5IGV0IGFsLiAxOTk4KSkKCj4gQ2FyZXksIEouIFIuLCBMaWVkbywgUC4sIE3DvGxsZXIsIEguIEcuLCBXYW5nLCBKLiBMLiwgJiBDaGlvdSwgSi4gTS4gKDE5OTgpLiBSZWxhdGlvbnNoaXAgb2YgYWdlIHBhdHRlcm5zIG9mIGZlY3VuZGl0eSB0byBtb3J0YWxpdHksIGxvbmdldml0eSwgYW5kIGxpZmV0aW1lIHJlcHJvZHVjdGlvbiBpbiBhIGxhcmdlIGNvaG9ydCBvZiBNZWRpdGVycmFuZWFuIGZydWl0IGZseSBmZW1hbGVzLiBUaGUgSm91cm5hbHMgb2YgR2Vyb250b2xvZ3kgU2VyaWVzIEE6IEJpb2xvZ2ljYWwgU2NpZW5jZXMgYW5kIE1lZGljYWwgU2NpZW5jZXMsIDUzKDQpLCBCMjQ1LUIyNTEuCgoqIFRoZSBkYXRhIGFyZSByYXRoZXIgbm9pc3ksIGRlbnNlIGFuZCB3aXRoIGEgY2hhcmFjdGVyaXN0aWMgZmxhdCBzdGFydC4KCiMjIERhdGEKYGBge3J9CmRhdGEoIm1lZGZseTI1IikKYGBgCgpgYGB7cn0KaGVhZChtZWRmbHkyNSkKYGBgCgoKYGBge3J9Ck4gPC0gbnJvdyhtZWRmbHkyNSkKbGlicmFyeShzY2FsZXMpCmxpYnJhcnkoZ2dwbG90MikKbGlicmFyeShkcGx5cikKbGlicmFyeShncmlkRXh0cmEpCgpnMSA8LSBtZWRmbHkyNSAlPiUgCiAgZ2dwbG90KGFlcyh4PURheXMseT1uRWdncyxncm91cD1JRCkpICsKICBnZW9tX2xpbmUoYWxwaGE9MC4yLGNvbG9yPSdncmF5JykgKwogIGdlb21fc21vb3RoKGFlcyhncm91cD0xKSxzZT1GQUxTRSkrCiAgdGhlbWVfYncoKSArCiAgbGFicyh4PSJEYXlzIix5PSJOdW1iZXIgb2YgRWdncyIpICsKICBnZ3RpdGxlKCJNZWRmbGllcyAtIFRpbWUgU2VyaWVzIFBsb3QiKQoKZzIgPC1tZWRmbHkyNSAlPiUgCiAgZ2dwbG90KGFlcyh4PURheXMseT1uRWdncykpICsKICBnZW9tX2RlbnNpdHlfMmRfZmlsbGVkKCkgKwogIHNjYWxlX2ZpbGxfYnJld2VyKCkrCiAgdGhlbWVfYncoKSArCiAgbGFicyh4PSJEYXlzIix5PSJOdW1iZXIgb2YgRWdncyIpICsKICBnZ3RpdGxlKCJNZWRmbGllcyAtIERlbnNpdHkgUGxvdCIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb249J25vbmUnKQoKZ3JpZC5hcnJhbmdlKGcxLGcyLG5jb2w9MikKCmBgYAoKIyMgRlBDQQoKYGBge3J9CkZsaWVzIDwtIE1ha2VGUENBSW5wdXRzKG1lZGZseTI1JElELG1lZGZseTI1JERheXMsbWVkZmx5MjUkbkVnZ3MpCmZwY2FPYmpGbGllcyA8LSBGUENBKEZsaWVzJEx5LEZsaWVzJEx0LAogICAgICAgICAgICAgICAgICAgICBsaXN0KHBsb3Q9VFJVRSwKICAgICAgICAgICAgICAgICAgICAgICAgICBtZXRob2RNdUNvdkVzdD0nc21vb3RoJywKICAgICAgICAgICAgICAgICAgICAgICAgICB1c2VyQndDb3Y9MikpCmBgYAoKU2VsZWN0IG51bWJlciBvZiBLIChzZWUsIFlhbyBldCBhbC4sIDIwMDUpCgo+IFlhbywgRi4sIE3DvGxsZXIsIEguIEcuLCAmIFdhbmcsIEouIEwuICgyMDA1KS4gRnVuY3Rpb25hbCBkYXRhIGFuYWx5c2lzIGZvciBzcGFyc2UgbG9uZ2l0dWRpbmFsIGRhdGEuIEpvdXJuYWwgb2YgdGhlIEFtZXJpY2FuIHN0YXRpc3RpY2FsIGFzc29jaWF0aW9uLCAxMDAoNDcwKSwgNTc3LTU5MC4KCmBgYHtyfQpudW1LIDwtIFNlbGVjdEsoZnBjYU9iakZsaWVzLGNyaXRlcmlvbiA9ICJGVkUiKQpudW1LCksgPC0gbnVtSyRLCmBgYAoKCmBgYHtyfQpDcmVhdGVQYXRoUGxvdChmcGNhT2JqRmxpZXMpCmBgYAoKYGBge3J9Cm1lZGZseTI1W21lZGZseTI1JElEPT11bmlxdWUobWVkZmx5MjUkSUQpW2MoMyw1LDEzNSldLF0gJT4lIAogIGdncGxvdChhZXMoeD1EYXlzLHk9bkVnZ3MsY29sb3I9YXMuZmFjdG9yKElEKSkpICsKICBnZW9tX2xpbmUoKQpgYGAKCgpgYGB7cn0KcGFyKG1mcm93PWMoMiwyKSkKICBDcmVhdGVQYXRoUGxvdChmcGNhT2JqRmxpZXMsc3Vic2V0PWMoMyw1LDEzNSkpCiAgQ3JlYXRlUGF0aFBsb3QoZnBjYU9iakZsaWVzLHN1YnNldD1jKDMsNSwxMzUpLEs9MSxtYWluPSJLPTEiLHBjaD00KQogIENyZWF0ZVBhdGhQbG90KGZwY2FPYmpGbGllcyxzdWJzZXQ9YygzLDUsMTM1KSxLPTMsbWFpbj0iSz0zIixwY2g9NCkKICBDcmVhdGVQYXRoUGxvdChmcGNhT2JqRmxpZXMsc3Vic2V0PWMoMyw1LDEzNSksSz00LG1haW49Iks9NCIscGNoPTQpCnBhcihtZnJvdz1jKDEsMSkpCgpgYGAKClRoZSBmb2xsb3dpbmcgc2VjdGlvbnMgY29udGFpbiBkZXNjcmlwdGlvbnMgYWJvdXQgb3B0aW9uYWwgZnVuY3Rpb25zIGluIGBmZGFwYWNlYC4KCiogT3V0bGllciBkZXRlY3Rpb24gKEZlYnJlcm8gZXQgYWwuLCAyMDA3KQoKPiBGZWJyZXJvLCBNLiwgR2FsZWFubywgUC4sICYgR29uesOhbGV6LU1hbnRlaWdhLCBXLiAoMjAwNykuIEEgZnVuY3Rpb25hbCBhbmFseXNpcyBvZiBOT3ggbGV2ZWxzOiBsb2NhdGlvbiBhbmQgc2NhbGUgZXN0aW1hdGlvbiBhbmQgb3V0bGllciBkZXRlY3Rpb24uIENvbXB1dGF0aW9uYWwgU3RhdGlzdGljcywgMjIoMyksIDQxMS00MjcuCgoqIEZ1bmN0aW9uYWwgYm94LXBsb3QgKEh5bmRtYW4gYW5kIFNoYW5nLCAyMDEwKQoKPiBIeW5kbWFuLCBSLiBKLiwgJiBTaGFuZywgSC4gTC4gKDIwMTApLiBSYWluYm93IHBsb3RzLCBiYWdwbG90cywgYW5kIGJveHBsb3RzIGZvciBmdW5jdGlvbmFsIGRhdGEuIEpvdXJuYWwgb2YgQ29tcHV0YXRpb25hbCBhbmQgR3JhcGhpY2FsIFN0YXRpc3RpY3MsIDE5KDEpLCAyOS00NS4KCiogS0RFOiBLZXJuZWwgZGVuc2l0eSBlc3RpbWF0aW9uOiBpdCBpcyBhIG5vbi1wYXJhbWV0cmljIG1ldGhvZCB0byBlc3RpbWF0ZSB0aGUgUERGIG9mIGEgcmFuZG9tIHZhcmlhYmxlIGJhc2VkIG9uIGtlcm5lbHMgYXMgd2VpZ2h0cy4KCgpgYGB7cn0KQ3JlYXRlT3V0bGllcnNQbG90KGZwY2FPYmpGbGllcyxvcHRucz1saXN0KEs9Myx2YXJpYW50PSdLREUnKSkKCmBgYAoKKiBUaGUgZ3JlZW4gbGluZSBjb3JyZXNwb25kcyB0byBgdGhlIGZ1bmN0aW9uYWwgbWVkaWFuYCwgdGhlIGRhcmsgZ3JheSBhcmVhIHRvIHRoZSBhcmVhIHNwYW5uZWQgYnkgdGhlIGN1cnZlcyB3aXRoaW4gdGhlIDI1dGggYW5kIDc1dGggcGVyY2VudGlsZSBhbmQgdGhlIGxpZ2h0IGdyYXkgdG8gdGhlIGFyZWEgc3Bhbm5lZCBieSB0aGUgY3VydmVzIHdpdGhpbiB0aGUgMi41dGggYW5kIDk3LjV0aCBwZXJjZW50aWxlLgoKYGBge3J9CkNyZWF0ZUZ1bmNCb3hQbG90KGZwY2FPYmpGbGllcyx4bGFiPSJEYXlzIix5bGFiPSJOdW1iZXIgb2YgZWdncyIsCiAgICAgICAgICAgICAgICAgIG9wdG5zPWxpc3QoSz0zLHZhcmlhbnQ9ImJhZ3Bsb3QiKSkKYGBgCgo=