Overview

In this vignette, I demonstrate how to utilize the RiskPortfolios library for portfolio selection. The analysis below relies on different estimation methods included with the library. Specifically, I demonstrate how to apply ten different estimation techniques for covariance matrices. Based on these estimates, I find a global minimum variance portfolio without position constraints. The back-testing procedure is conducted using Fama-French monthly industry portfolios.

Getting Started

Let us begin by loading all relevant packages and downloading the data needed.

library(RiskPortfolios)
library(lubridate)
library(xts)
library(moments)
library(ggplot2)
library(plotly)

The analysis relies on different Fama-French industry portfolios. The code below downloads the data directly from Ken French’s website and stacks the five industry datasets in a list.

file_i <- "https://mba.tuck.dartmouth.edu/pages/faculty/ken.french/ftp/XYZ_Industry_Portfolios_CSV.zip"
ds_list <- list()
for (ind in c(5,10,17,30,48)) {
  
  FF_file <- gsub("XYZ",ind,file_i,)
  temp <- tempfile()
  download.file(FF_file,temp)
  unz_files <- unzip(temp)
  ds <- read.csv(unz_files,skip = 11)
  flag_obs <- grep("Equal",ds[,1],ignore.case = T)
  ds <- ds[1:(flag_obs-1),]
  names(ds)[1] <- "date"
  ds <- data.frame(apply(ds, 2, as.numeric))
  ds[,-1] <- ds[,-1]/100
  ds$date <- ceiling_date(ymd(ds$date*100+ 01),"m")-1
  ds <- ds[ds$date >= "1990-01-01",]
  ds_list <- c(ds_list,list(ds))
}

I set the data to start from 1990. In this case, we have the follow number of observation for each data

sapply(ds_list,nrow)
[1] 378 378 378 378 378
years_data <- lapply(ds_list, function(x) unique(year(x$date)) )
years_data <- Reduce(union,years_data)
total_n_years <- max(years_data) - min(years_data)

which corresponds roughly to 31 years of data.

Note: the key is to run a program on a single data from ds_list list, so that we can rerun it through the whole datasets easily.

The Portfolio Problem

For the portfolio, I consider the global minimum variance portfolio (GMVP). Without position constraints, the portfolio weights are given by \[\begin{equation} \mathbf{w}=\frac{\boldsymbol{\Sigma}^{-1}\mathbf{1}}{\mathbf{1}^{\top}\boldsymbol{\Sigma}^{-1}\mathbf{1}} \end{equation}\] where \(\Sigma\) denotes a non-singular \(N \times N\) covariance matrix with \(N\) is the number of assets in the portfolio. Additionally, \(\mathbf{1}\) denotes a column vector of ones.

In practice, the portfolio manager needs to estimate the covariance matrix. We denote the corresponding estimate using methodology \(m\) and sample size \(T\) by \(\hat{\boldsymbol{\Sigma}}_{m,T}\). For this reason, the GMVP is a function of both \(m\) and \(T\), such that \[\begin{equation} \hat{\mathbf{w}}_{m,T}=\frac{\hat{\boldsymbol{\Sigma}}_{m,T}^{-1}\mathbf{1}}{\mathbf{1}^{\top}\hat{\boldsymbol{\Sigma}}_{m,T}^{-1}\mathbf{1}} \end{equation}\]

In the following I set \(T = 60\) denoting 5 years of monthly data. For \(m\), I consider different methods from the RiskPortfolios library.

Implementation

To utilize RiskPortfolios package we need to set different controls in order to corresponds to each method of interest.

m_1 <- list(type = "naive")
m_2 <- list(type = "ewma")
m_3 <- list(type = "lw")
m_4 <- list(type = "factor")
m_5 <- list(type = "const")
m_6 <- list(type = "cor")
m_7 <- list(type = "oneparm")
m_8 <- list(type = "diag")
m_9 <- list(type = "large")
m_10 <- list(type = "bs")

m_list <- list(m_1,m_2,m_3,
               m_4,m_5,m_6,
               m_7,m_8,m_9,
               m_10)

names(m_list) <- c("Sample","EWMA","LW",
                   "Factor","Constant","Cor",
                   "Uniform","Diagonal","Large",
                   "Bayes_Stein")

Each of the above methods results in a covariance matrix estimate and, hence, a portfolio. For further information about the methods, see the reference manual of the RiskPortfolios library.

For the ease of exposition, let us write the following GMVP function

GMVP_fun <- function(S_i) {
  S_i_inv <- solve(S_i)
  d <- nrow(S_i)
  v_ones <- rep(1,d)
  w_hat <- S_i_inv%*%v_ones/(sum(S_i_inv))
  return(w_hat)
}

The code below constitutes a nested loop. For a given dataset index data_i and method m, the inner loop iterates through each month and conducts an rolling window estimation. The outer loops iterates through each method and dataset. The end result of the following is a list of out-of-sample portfolio returns denoted by R_mat_list.

R_mat_list <- list()

for(data_i in 1:length(ds_list)) { 
  cat("This is data ", data_i,"\n")
  ds_i <- ds_list[[data_i]]
  
  total_months <- unique(ceiling_date(ds_i$date,"m") - 1)
  T_months <- 60 # corresponsd to five years of data
  month_seq <- sort(as.character(total_months[T_months:length(total_months)]))
  
  r_p_ts_list <- list()
  for (m in 1:length(m_list)) {
    m_i <- m_list[[m]]
    
    r_p_ts <- c()
    for (i in 1:(length(month_seq) - 1)) {
      month_i <- month_seq[i]
      ds_i_sub <- ds_i[ds_i$date <= month_i,]
      ds_i_sub <- tail(ds_i_sub,T_months)
      R_sub <- as.matrix(ds_i_sub[,-1])
      S_i <- covEstimation(R_sub,control = m_i)
      w_i <- GMVP_fun(S_i)
      
      month_next <- month_seq[i+1]
      ds_i_next <- ds_i[ds_i$date <= month_next & ds_i$date > month_i,]
      R_next <- as.matrix(ds_i_next[,-1])
      r_p_i <- c(t(w_i)%*%t(R_next))
      r_p_ts <- c(r_p_ts,r_p_i)
    }
    
    names(r_p_ts) <- month_seq[2:length(month_seq)]
    r_p_ts <- as.xts(r_p_ts)
    r_p_ts_list <- c(r_p_ts_list,list(r_p_ts))
    
  }
  
  R_mat <- Reduce(merge,r_p_ts_list)
  names(R_mat) <- names(m_list)
  
  R_mat_list <- c(R_mat_list,list(R_mat))
}

Portfolio Performance

To summarize the performance of the above 10 decision rules, let us consider the following performance metrics.

my_sum <- function(x) {
  m <- mean(x)*12
  s <- sd(x)*sqrt(12)
  SR <- m/s
  s_neg <- sd(x[x < 0])*sqrt(12)
  Sort <- m/s_neg
  skew <- skewness(x)
  kurt <- kurtosis(x)
  VaR <- mean(x) - quantile(x,0.01)
  results <- c(m,s,SR,Sort,skew,kurt,VaR)
  return(results)
}

For each data index data_i, I create a summary matrix using the following function:

sum_data_i <- function(data_i) {
  R_mat_i <- R_mat_list[[data_i]]
  sum_i <- apply(R_mat_i,2,my_sum)
  rownames(sum_i) <- c("Mean","Std","Sharpe","Sortino","Skewness","Kurtosis","VaR")
  return(sum_i)
}

Finally, we stack all summary results in the following list

sum_data_list <- lapply(1:length(R_mat_list),sum_data_i)

For instance, the summary performance for the 48 industry portfolios is given by

data.frame(t(sum_data_list[[5]]))

Summary

As an overall summary, let us visualize a given performance metric for each data set over the whole ten estimation methods used in our analysis. To do so, I create the following function that takes a performance metric of interest as its main argument and returns a ggplot item:

ggplot_sum <- function(perf_of_interest) {
  
  ds.plot <- data.frame()
  for (data_i in 1:length(sum_data_list)) {
    sum_data_i <- sum_data_list[[data_i]]
    y <- sum_data_i[perf_of_interest,]
    ds.plot <- rbind(ds.plot,data.frame(Performance = y, Method = names(y), Data = data_i))
  }
  
  ds.plot$Data <- as.factor(ds.plot$Data)
  p <- ggplot(ds.plot,aes(x = Data, y = Performance, colour =Method )) 
  p <- p +  geom_point() 
  p <- p +  labs(x = "FF Data", y = perf_of_interest)
  return(p)
}

For example, to summarize the risk-adjusted returns, I plot the Sortino ratio while distinguishing the data and method used.

p <- ggplot_sum("Sortino")
ggplotly(p,width = 800, height = 600)

Among all methods, we observe that the “factor” approach yields consistent performance and ranks at the top three among all datasets. The other two that follow suit are the Constant and Uniform approaches.


lapply(sum_data_list, function(x)  names(sort(x["Sortino",],decreasing = T)[1:3]))
[[1]]
[1] "EWMA"     "Factor"   "Diagonal"

[[2]]
[1] "Factor"   "Constant" "Uniform" 

[[3]]
[1] "Constant" "Factor"   "Uniform" 

[[4]]
[1] "Factor"   "Constant" "Uniform" 

[[5]]
[1] "Constant" "Factor"   "Uniform" 

Note: by definition, the “factor” methods estimates the covariance matrix using a single factor by default. Since we do not define a specific risk factor, the source code of the library utilizes the factanal stats command for factor analysis. For further info, see this link. The “constant” method refers to the case in which the covariance matrix is shrank towards a covariance matrix with constant correlation. This method is parsimonious and, potentially, leads to reduction of estimation risk. Finally, the Uniform method corresponds to “oneparm” and is considered even more parsimonious, since the prior is given by a single one-parameter matrix. In this case, all variances are equal, while covariances are set to zero.

As a final summary, let us reconstruct the previous plot but using value-at-risk (VaR):

p <- ggplot_sum("VaR")
ggplotly(p,width = 800, height = 600)

In terms of VaR, we see that the Factor approach results in the lowest downside risk for all datasets, except the 5 Fama-French industry portfolios.

lapply(sum_data_list, function(x)  names(sort(x["VaR",],decreasing = F)[1:3]))
[[1]]
[1] "EWMA"        "Bayes_Stein" "Sample"     

[[2]]
[1] "Factor"   "Cor"      "Constant"

[[3]]
[1] "Factor"   "Cor"      "Constant"

[[4]]
[1] "Factor"   "Constant" "Cor"     

[[5]]
[1] "Factor"   "Constant" "Cor"     

Overall, the above results indicate that shrinkage techniques provide greater improvement when one is dealing with larger number of assets. This denotes the case of great estimation risk. Additionally, the fact that the factor model dominates other techniques, this indicates that the decision-maker can fully shrink the covariance matrix towards a prior without the need of determining the shrinkage intensity. Clearly, to generalize this conjecture, one needs to validate over different datasets, sample sizes, and estimation frequencies.

Concluding Remarks

This vignette provides a simple paradigm to evaluate the out-of-sample performance of different estimation methods for covariance matrices. Interested researches in proposing new methods for covariance matrices would greatly benefit from RiskPortfolios in setting benchmarks and testing new decision rules. Note that the above analysis does not take into account statistical significance. One potential remedy is to perform bootstrap and assess whether outperformance is not merely a statistical fluke. I leave this for a future endeavor.

LS0tCnRpdGxlOiAnR2xvYmFsIE1pbmltdW0gVmFyaWFuY2UgUmlza1BvcnRmb2xpb3MnCmF1dGhvcjogIk1hamVlZCBTaW1hYW4iCmRhdGU6ICJBdWd1c3QgMjgsIDIwMjEiCm91dHB1dDoKICBodG1sX25vdGVib29rOiBkZWZhdWx0CiAgcGRmX2RvY3VtZW50OiBkZWZhdWx0CiAgd29yZF9kb2N1bWVudDogZGVmYXVsdApmaWdfd2lkdGg6IDIwCi0tLQoKIyBPdmVydmlldwpJbiB0aGlzIHZpZ25ldHRlLCBJIGRlbW9uc3RyYXRlIGhvdyB0byB1dGlsaXplIHRoZSBgUmlza1BvcnRmb2xpb3NgIGxpYnJhcnkgZm9yIHBvcnRmb2xpbyBzZWxlY3Rpb24uIFRoZSBhbmFseXNpcyBiZWxvdyByZWxpZXMgb24gZGlmZmVyZW50IGVzdGltYXRpb24gbWV0aG9kcyBpbmNsdWRlZCB3aXRoIHRoZSBsaWJyYXJ5LiBTcGVjaWZpY2FsbHksIEkgZGVtb25zdHJhdGUgaG93IHRvIGFwcGx5IHRlbiBkaWZmZXJlbnQgZXN0aW1hdGlvbiB0ZWNobmlxdWVzIGZvciBjb3ZhcmlhbmNlIG1hdHJpY2VzLiBCYXNlZCBvbiB0aGVzZSBlc3RpbWF0ZXMsIEkgZmluZCBhIGdsb2JhbCBtaW5pbXVtIHZhcmlhbmNlIHBvcnRmb2xpbyB3aXRob3V0IHBvc2l0aW9uIGNvbnN0cmFpbnRzLiBUaGUgYmFjay10ZXN0aW5nIHByb2NlZHVyZSBpcyBjb25kdWN0ZWQgdXNpbmcgRmFtYS1GcmVuY2ggbW9udGhseSBpbmR1c3RyeSBwb3J0Zm9saW9zLiAKCiMgR2V0dGluZyBTdGFydGVkCkxldCB1cyBiZWdpbiBieSBsb2FkaW5nIGFsbCByZWxldmFudCBwYWNrYWdlcyBhbmQgZG93bmxvYWRpbmcgdGhlIGRhdGEgbmVlZGVkLiAKCmBgYHtyLG1lc3NhZ2U9Rix3YXJuaW5nPUZ9CmxpYnJhcnkoUmlza1BvcnRmb2xpb3MpCmxpYnJhcnkobHVicmlkYXRlKQpsaWJyYXJ5KHh0cykKbGlicmFyeShtb21lbnRzKQpsaWJyYXJ5KGdncGxvdDIpCmxpYnJhcnkocGxvdGx5KQoKYGBgCgpUaGUgYW5hbHlzaXMgcmVsaWVzIG9uIGRpZmZlcmVudCBGYW1hLUZyZW5jaCBpbmR1c3RyeSBwb3J0Zm9saW9zLiBUaGUgY29kZSBiZWxvdyBkb3dubG9hZHMgdGhlIGRhdGEgZGlyZWN0bHkgZnJvbSBLZW4gRnJlbmNoJ3Mgd2Vic2l0ZSBhbmQgc3RhY2tzIHRoZSBmaXZlIGluZHVzdHJ5IGRhdGFzZXRzIGluIGEgbGlzdC4KYGBge3IsbWVzc2FnZT1GQUxTRSx3YXJuaW5nPUZBTFNFLHJlc3VsdHM9J2hpZGUnfQpmaWxlX2kgPC0gImh0dHBzOi8vbWJhLnR1Y2suZGFydG1vdXRoLmVkdS9wYWdlcy9mYWN1bHR5L2tlbi5mcmVuY2gvZnRwL1hZWl9JbmR1c3RyeV9Qb3J0Zm9saW9zX0NTVi56aXAiCmRzX2xpc3QgPC0gbGlzdCgpCmZvciAoaW5kIGluIGMoNSwxMCwxNywzMCw0OCkpIHsKICAKICBGRl9maWxlIDwtIGdzdWIoIlhZWiIsaW5kLGZpbGVfaSwpCiAgdGVtcCA8LSB0ZW1wZmlsZSgpCiAgZG93bmxvYWQuZmlsZShGRl9maWxlLHRlbXApCiAgdW56X2ZpbGVzIDwtIHVuemlwKHRlbXApCiAgZHMgPC0gcmVhZC5jc3YodW56X2ZpbGVzLHNraXAgPSAxMSkKICBmbGFnX29icyA8LSBncmVwKCJFcXVhbCIsZHNbLDFdLGlnbm9yZS5jYXNlID0gVCkKICBkcyA8LSBkc1sxOihmbGFnX29icy0xKSxdCiAgbmFtZXMoZHMpWzFdIDwtICJkYXRlIgogIGRzIDwtIGRhdGEuZnJhbWUoYXBwbHkoZHMsIDIsIGFzLm51bWVyaWMpKQogIGRzWywtMV0gPC0gZHNbLC0xXS8xMDAKICBkcyRkYXRlIDwtIGNlaWxpbmdfZGF0ZSh5bWQoZHMkZGF0ZSoxMDArIDAxKSwibSIpLTEKICBkcyA8LSBkc1tkcyRkYXRlID49ICIxOTkwLTAxLTAxIixdCiAgZHNfbGlzdCA8LSBjKGRzX2xpc3QsbGlzdChkcykpCn0KCmBgYAoKSSBzZXQgdGhlIGRhdGEgdG8gc3RhcnQgZnJvbSAxOTkwLiBJbiB0aGlzIGNhc2UsIHdlIGhhdmUgdGhlIGZvbGxvdyBudW1iZXIgb2Ygb2JzZXJ2YXRpb24gZm9yIGVhY2ggZGF0YQpgYGB7cn0Kc2FwcGx5KGRzX2xpc3QsbnJvdykKYGBgCmBgYHtyfQp5ZWFyc19kYXRhIDwtIGxhcHBseShkc19saXN0LCBmdW5jdGlvbih4KSB1bmlxdWUoeWVhcih4JGRhdGUpKSApCnllYXJzX2RhdGEgPC0gUmVkdWNlKHVuaW9uLHllYXJzX2RhdGEpCnRvdGFsX25feWVhcnMgPC0gbWF4KHllYXJzX2RhdGEpIC0gbWluKHllYXJzX2RhdGEpCmBgYAp3aGljaCBjb3JyZXNwb25kcyByb3VnaGx5IHRvIGByIHRvdGFsX25feWVhcnNgIHllYXJzIG9mIGRhdGEuIAoKKipOb3RlKio6IHRoZSBrZXkgaXMgdG8gcnVuIGEgcHJvZ3JhbSBvbiBhIHNpbmdsZSBkYXRhIGZyb20gYGRzX2xpc3RgIGxpc3QsIHNvIHRoYXQgd2UgY2FuIHJlcnVuIGl0IHRocm91Z2ggdGhlIHdob2xlIGRhdGFzZXRzIGVhc2lseS4KCiMgVGhlIFBvcnRmb2xpbyBQcm9ibGVtCkZvciB0aGUgcG9ydGZvbGlvLCBJIGNvbnNpZGVyIHRoZSBnbG9iYWwgbWluaW11bSB2YXJpYW5jZSBwb3J0Zm9saW8gKEdNVlApLiBXaXRob3V0IHBvc2l0aW9uIGNvbnN0cmFpbnRzLCB0aGUgcG9ydGZvbGlvIHdlaWdodHMgYXJlIGdpdmVuIGJ5IApcYmVnaW57ZXF1YXRpb259ClxtYXRoYmZ7d309XGZyYWN7XGJvbGRzeW1ib2x7XFNpZ21hfV57LTF9XG1hdGhiZnsxfX17XG1hdGhiZnsxfV57XHRvcH1cYm9sZHN5bWJvbHtcU2lnbWF9XnstMX1cbWF0aGJmezF9fQpcZW5ke2VxdWF0aW9ufQp3aGVyZSAgJFxTaWdtYSQgZGVub3RlcyBhIG5vbi1zaW5ndWxhciAkTiBcdGltZXMgTiQgY292YXJpYW5jZSBtYXRyaXggd2l0aCAkTiQgaXMgdGhlIG51bWJlciBvZiBhc3NldHMgaW4gdGhlIHBvcnRmb2xpby4gQWRkaXRpb25hbGx5LCAkXG1hdGhiZnsxfSQgZGVub3RlcyBhIGNvbHVtbiB2ZWN0b3Igb2Ygb25lcy4KCkluIHByYWN0aWNlLCB0aGUgcG9ydGZvbGlvIG1hbmFnZXIgbmVlZHMgdG8gZXN0aW1hdGUgdGhlIGNvdmFyaWFuY2UgbWF0cml4LiBXZSBkZW5vdGUgdGhlIGNvcnJlc3BvbmRpbmcgZXN0aW1hdGUgdXNpbmcgIG1ldGhvZG9sb2d5ICRtJCBhbmQgc2FtcGxlIHNpemUgJFQkIGJ5ICRcaGF0e1xib2xkc3ltYm9se1xTaWdtYX19X3ttLFR9JC4gIEZvciB0aGlzIHJlYXNvbiwgdGhlIEdNVlAgaXMgYSBmdW5jdGlvbiBvZiBib3RoICRtJCBhbmQgJFQkLCBzdWNoIHRoYXQgClxiZWdpbntlcXVhdGlvbn0KXGhhdHtcbWF0aGJme3d9fV97bSxUfT1cZnJhY3tcaGF0e1xib2xkc3ltYm9se1xTaWdtYX19X3ttLFR9XnstMX1cbWF0aGJmezF9fXtcbWF0aGJmezF9XntcdG9wfVxoYXR7XGJvbGRzeW1ib2x7XFNpZ21hfX1fe20sVH1eey0xfVxtYXRoYmZ7MX19ClxlbmR7ZXF1YXRpb259CgpJbiB0aGUgZm9sbG93aW5nIEkgc2V0ICRUID0gNjAkIGRlbm90aW5nIDUgeWVhcnMgb2YgbW9udGhseSBkYXRhLiBGb3IgJG0kLCBJIGNvbnNpZGVyIGRpZmZlcmVudCBtZXRob2RzIGZyb20gdGhlIGBSaXNrUG9ydGZvbGlvc2AgbGlicmFyeS4KCiMgSW1wbGVtZW50YXRpb24KVG8gdXRpbGl6ZSBgUmlza1BvcnRmb2xpb3NgIHBhY2thZ2Ugd2UgbmVlZCB0byBzZXQgZGlmZmVyZW50IGNvbnRyb2xzIGluIG9yZGVyIHRvIGNvcnJlc3BvbmRzIHRvIGVhY2ggbWV0aG9kIG9mIGludGVyZXN0LgpgYGB7cn0KbV8xIDwtIGxpc3QodHlwZSA9ICJuYWl2ZSIpCm1fMiA8LSBsaXN0KHR5cGUgPSAiZXdtYSIpCm1fMyA8LSBsaXN0KHR5cGUgPSAibHciKQptXzQgPC0gbGlzdCh0eXBlID0gImZhY3RvciIpCm1fNSA8LSBsaXN0KHR5cGUgPSAiY29uc3QiKQptXzYgPC0gbGlzdCh0eXBlID0gImNvciIpCm1fNyA8LSBsaXN0KHR5cGUgPSAib25lcGFybSIpCm1fOCA8LSBsaXN0KHR5cGUgPSAiZGlhZyIpCm1fOSA8LSBsaXN0KHR5cGUgPSAibGFyZ2UiKQptXzEwIDwtIGxpc3QodHlwZSA9ICJicyIpCgptX2xpc3QgPC0gbGlzdChtXzEsbV8yLG1fMywKICAgICAgICAgICAgICAgbV80LG1fNSxtXzYsCiAgICAgICAgICAgICAgIG1fNyxtXzgsbV85LAogICAgICAgICAgICAgICBtXzEwKQoKbmFtZXMobV9saXN0KSA8LSBjKCJTYW1wbGUiLCJFV01BIiwiTFciLAogICAgICAgICAgICAgICAgICAgIkZhY3RvciIsIkNvbnN0YW50IiwiQ29yIiwKICAgICAgICAgICAgICAgICAgICJVbmlmb3JtIiwiRGlhZ29uYWwiLCJMYXJnZSIsCiAgICAgICAgICAgICAgICAgICAiQmF5ZXNfU3RlaW4iKQoKYGBgCkVhY2ggb2YgdGhlIGFib3ZlIG1ldGhvZHMgcmVzdWx0cyBpbiBhIGNvdmFyaWFuY2UgbWF0cml4IGVzdGltYXRlIGFuZCwgaGVuY2UsIGEgcG9ydGZvbGlvLiBGb3IgZnVydGhlciBpbmZvcm1hdGlvbiBhYm91dCB0aGUgbWV0aG9kcywgc2VlIHRoZSByZWZlcmVuY2UgbWFudWFsIG9mIHRoZSBgUmlza1BvcnRmb2xpb3NgIGxpYnJhcnkuCgpGb3IgdGhlIGVhc2Ugb2YgZXhwb3NpdGlvbiwgbGV0IHVzIHdyaXRlIHRoZSBmb2xsb3dpbmcgR01WUCBmdW5jdGlvbgpgYGB7cn0KR01WUF9mdW4gPC0gZnVuY3Rpb24oU19pKSB7CiAgU19pX2ludiA8LSBzb2x2ZShTX2kpCiAgZCA8LSBucm93KFNfaSkKICB2X29uZXMgPC0gcmVwKDEsZCkKICB3X2hhdCA8LSBTX2lfaW52JSoldl9vbmVzLyhzdW0oU19pX2ludikpCiAgcmV0dXJuKHdfaGF0KQp9CmBgYAoKVGhlIGNvZGUgYmVsb3cgY29uc3RpdHV0ZXMgYSBuZXN0ZWQgbG9vcC4gRm9yIGEgZ2l2ZW4gZGF0YXNldCBpbmRleCBgZGF0YV9pYCBhbmQgbWV0aG9kIGBtYCwgdGhlIGlubmVyIGxvb3AgaXRlcmF0ZXMgdGhyb3VnaCBlYWNoIG1vbnRoIGFuZCBjb25kdWN0cyBhbiByb2xsaW5nIHdpbmRvdyBlc3RpbWF0aW9uLiBUaGUgb3V0ZXIgbG9vcHMgaXRlcmF0ZXMgdGhyb3VnaCBlYWNoIG1ldGhvZCBhbmQgZGF0YXNldC4gVGhlIGVuZCByZXN1bHQgb2YgdGhlIGZvbGxvd2luZyBpcyBhIGxpc3Qgb2Ygb3V0LW9mLXNhbXBsZSBwb3J0Zm9saW8gcmV0dXJucyBkZW5vdGVkIGJ5IGBSX21hdF9saXN0YC4KCmBgYHtyLG1lc3NhZ2U9RkFMU0Usd2FybmluZz1GQUxTRSxyZXN1bHRzPSdoaWRlJ30KUl9tYXRfbGlzdCA8LSBsaXN0KCkKCmZvcihkYXRhX2kgaW4gMTpsZW5ndGgoZHNfbGlzdCkpIHsgCiAgY2F0KCJUaGlzIGlzIGRhdGEgIiwgZGF0YV9pLCJcbiIpCiAgZHNfaSA8LSBkc19saXN0W1tkYXRhX2ldXQogIAogIHRvdGFsX21vbnRocyA8LSB1bmlxdWUoY2VpbGluZ19kYXRlKGRzX2kkZGF0ZSwibSIpIC0gMSkKICBUX21vbnRocyA8LSA2MCAjIGNvcnJlc3BvbnNkIHRvIGZpdmUgeWVhcnMgb2YgZGF0YQogIG1vbnRoX3NlcSA8LSBzb3J0KGFzLmNoYXJhY3Rlcih0b3RhbF9tb250aHNbVF9tb250aHM6bGVuZ3RoKHRvdGFsX21vbnRocyldKSkKICAKICByX3BfdHNfbGlzdCA8LSBsaXN0KCkKICBmb3IgKG0gaW4gMTpsZW5ndGgobV9saXN0KSkgewogICAgbV9pIDwtIG1fbGlzdFtbbV1dCiAgICAKICAgIHJfcF90cyA8LSBjKCkKICAgIGZvciAoaSBpbiAxOihsZW5ndGgobW9udGhfc2VxKSAtIDEpKSB7CiAgICAgIG1vbnRoX2kgPC0gbW9udGhfc2VxW2ldCiAgICAgIGRzX2lfc3ViIDwtIGRzX2lbZHNfaSRkYXRlIDw9IG1vbnRoX2ksXQogICAgICBkc19pX3N1YiA8LSB0YWlsKGRzX2lfc3ViLFRfbW9udGhzKQogICAgICBSX3N1YiA8LSBhcy5tYXRyaXgoZHNfaV9zdWJbLC0xXSkKICAgICAgU19pIDwtIGNvdkVzdGltYXRpb24oUl9zdWIsY29udHJvbCA9IG1faSkKICAgICAgd19pIDwtIEdNVlBfZnVuKFNfaSkKICAgICAgCiAgICAgIG1vbnRoX25leHQgPC0gbW9udGhfc2VxW2krMV0KICAgICAgZHNfaV9uZXh0IDwtIGRzX2lbZHNfaSRkYXRlIDw9IG1vbnRoX25leHQgJiBkc19pJGRhdGUgPiBtb250aF9pLF0KICAgICAgUl9uZXh0IDwtIGFzLm1hdHJpeChkc19pX25leHRbLC0xXSkKICAgICAgcl9wX2kgPC0gYyh0KHdfaSklKiV0KFJfbmV4dCkpCiAgICAgIHJfcF90cyA8LSBjKHJfcF90cyxyX3BfaSkKICAgIH0KICAgIAogICAgbmFtZXMocl9wX3RzKSA8LSBtb250aF9zZXFbMjpsZW5ndGgobW9udGhfc2VxKV0KICAgIHJfcF90cyA8LSBhcy54dHMocl9wX3RzKQogICAgcl9wX3RzX2xpc3QgPC0gYyhyX3BfdHNfbGlzdCxsaXN0KHJfcF90cykpCiAgICAKICB9CiAgCiAgUl9tYXQgPC0gUmVkdWNlKG1lcmdlLHJfcF90c19saXN0KQogIG5hbWVzKFJfbWF0KSA8LSBuYW1lcyhtX2xpc3QpCiAgCiAgUl9tYXRfbGlzdCA8LSBjKFJfbWF0X2xpc3QsbGlzdChSX21hdCkpCn0KCgoKYGBgCgojIFBvcnRmb2xpbyBQZXJmb3JtYW5jZQpUbyBzdW1tYXJpemUgdGhlIHBlcmZvcm1hbmNlIG9mIHRoZSBhYm92ZSAxMCBkZWNpc2lvbiBydWxlcywgbGV0IHVzIGNvbnNpZGVyIHRoZSBmb2xsb3dpbmcgcGVyZm9ybWFuY2UgbWV0cmljcy4KYGBge3J9Cm15X3N1bSA8LSBmdW5jdGlvbih4KSB7CiAgbSA8LSBtZWFuKHgpKjEyCiAgcyA8LSBzZCh4KSpzcXJ0KDEyKQogIFNSIDwtIG0vcwogIHNfbmVnIDwtIHNkKHhbeCA8IDBdKSpzcXJ0KDEyKQogIFNvcnQgPC0gbS9zX25lZwogIHNrZXcgPC0gc2tld25lc3MoeCkKICBrdXJ0IDwtIGt1cnRvc2lzKHgpCiAgVmFSIDwtIG1lYW4oeCkgLSBxdWFudGlsZSh4LDAuMDEpCiAgcmVzdWx0cyA8LSBjKG0scyxTUixTb3J0LHNrZXcsa3VydCxWYVIpCiAgcmV0dXJuKHJlc3VsdHMpCn0KYGBgCgpGb3IgZWFjaCBkYXRhIGluZGV4IGBkYXRhX2lgLCBJIGNyZWF0ZSBhIHN1bW1hcnkgbWF0cml4IHVzaW5nIHRoZSBmb2xsb3dpbmcgZnVuY3Rpb246CmBgYHtyfQpzdW1fZGF0YV9pIDwtIGZ1bmN0aW9uKGRhdGFfaSkgewogIFJfbWF0X2kgPC0gUl9tYXRfbGlzdFtbZGF0YV9pXV0KICBzdW1faSA8LSBhcHBseShSX21hdF9pLDIsbXlfc3VtKQogIHJvd25hbWVzKHN1bV9pKSA8LSBjKCJNZWFuIiwiU3RkIiwiU2hhcnBlIiwiU29ydGlubyIsIlNrZXduZXNzIiwiS3VydG9zaXMiLCJWYVIiKQogIHJldHVybihzdW1faSkKfQoKYGBgCgpGaW5hbGx5LCB3ZSBzdGFjayBhbGwgc3VtbWFyeSByZXN1bHRzIGluIHRoZSBmb2xsb3dpbmcgbGlzdApgYGB7cn0Kc3VtX2RhdGFfbGlzdCA8LSBsYXBwbHkoMTpsZW5ndGgoUl9tYXRfbGlzdCksc3VtX2RhdGFfaSkKYGBgCkZvciBpbnN0YW5jZSwgdGhlIHN1bW1hcnkgcGVyZm9ybWFuY2UgZm9yIHRoZSA0OCBpbmR1c3RyeSBwb3J0Zm9saW9zIGlzIGdpdmVuIGJ5CmBgYHtyfQpkYXRhLmZyYW1lKHQoc3VtX2RhdGFfbGlzdFtbNV1dKSkKYGBgCgojIyBTdW1tYXJ5CkFzIGFuIG92ZXJhbGwgc3VtbWFyeSwgbGV0IHVzIHZpc3VhbGl6ZSBhIGdpdmVuIHBlcmZvcm1hbmNlIG1ldHJpYyBmb3IgZWFjaCBkYXRhIHNldCBvdmVyIHRoZSB3aG9sZSB0ZW4gZXN0aW1hdGlvbiBtZXRob2RzIHVzZWQgaW4gb3VyIGFuYWx5c2lzLiBUbyBkbyBzbywgSSBjcmVhdGUgdGhlIGZvbGxvd2luZyBmdW5jdGlvbiB0aGF0IHRha2VzIGEgcGVyZm9ybWFuY2UgbWV0cmljIG9mIGludGVyZXN0IGFzIGl0cyBtYWluIGFyZ3VtZW50IGFuZCByZXR1cm5zIGEgYGdncGxvdGAgaXRlbToKYGBge3J9CmdncGxvdF9zdW0gPC0gZnVuY3Rpb24ocGVyZl9vZl9pbnRlcmVzdCkgewogIAogIGRzLnBsb3QgPC0gZGF0YS5mcmFtZSgpCiAgZm9yIChkYXRhX2kgaW4gMTpsZW5ndGgoc3VtX2RhdGFfbGlzdCkpIHsKICAgIHN1bV9kYXRhX2kgPC0gc3VtX2RhdGFfbGlzdFtbZGF0YV9pXV0KICAgIHkgPC0gc3VtX2RhdGFfaVtwZXJmX29mX2ludGVyZXN0LF0KICAgIGRzLnBsb3QgPC0gcmJpbmQoZHMucGxvdCxkYXRhLmZyYW1lKFBlcmZvcm1hbmNlID0geSwgTWV0aG9kID0gbmFtZXMoeSksIERhdGEgPSBkYXRhX2kpKQogIH0KICAKICBkcy5wbG90JERhdGEgPC0gYXMuZmFjdG9yKGRzLnBsb3QkRGF0YSkKICBwIDwtIGdncGxvdChkcy5wbG90LGFlcyh4ID0gRGF0YSwgeSA9IFBlcmZvcm1hbmNlLCBjb2xvdXIgPU1ldGhvZCApKSAKICBwIDwtIHAgKyAgZ2VvbV9wb2ludCgpIAogIHAgPC0gcCArICBsYWJzKHggPSAiRkYgRGF0YSIsIHkgPSBwZXJmX29mX2ludGVyZXN0KQogIHJldHVybihwKQp9CgpgYGAKCkZvciBleGFtcGxlLCB0byBzdW1tYXJpemUgdGhlIHJpc2stYWRqdXN0ZWQgcmV0dXJucywgSSBwbG90IHRoZSBTb3J0aW5vIHJhdGlvIHdoaWxlIGRpc3Rpbmd1aXNoaW5nIHRoZSBkYXRhIGFuZCBtZXRob2QgdXNlZC4gCmBgYHtyfQpwIDwtIGdncGxvdF9zdW0oIlNvcnRpbm8iKQpnZ3Bsb3RseShwLHdpZHRoID0gODAwLCBoZWlnaHQgPSA2MDApCmBgYApBbW9uZyBhbGwgbWV0aG9kcywgd2Ugb2JzZXJ2ZSB0aGF0IHRoZSAiZmFjdG9yIiBhcHByb2FjaCB5aWVsZHMgY29uc2lzdGVudCBwZXJmb3JtYW5jZSBhbmQgcmFua3MgYXQgdGhlIHRvcCB0aHJlZSBhbW9uZyBhbGwgZGF0YXNldHMuIFRoZSBvdGhlciB0d28gdGhhdCBmb2xsb3cgc3VpdCBhcmUgdGhlIENvbnN0YW50IGFuZCBVbmlmb3JtIGFwcHJvYWNoZXMuIApgYGB7cn0KCmxhcHBseShzdW1fZGF0YV9saXN0LCBmdW5jdGlvbih4KSAgbmFtZXMoc29ydCh4WyJTb3J0aW5vIixdLGRlY3JlYXNpbmcgPSBUKVsxOjNdKSkKCmBgYAoKKipOb3RlKio6IGJ5IGRlZmluaXRpb24sIHRoZSAiZmFjdG9yIiBtZXRob2RzIGVzdGltYXRlcyB0aGUgY292YXJpYW5jZSBtYXRyaXggdXNpbmcgYSBzaW5nbGUgZmFjdG9yIGJ5IGRlZmF1bHQuIFNpbmNlIHdlIGRvIG5vdCBkZWZpbmUgYSBzcGVjaWZpYyByaXNrIGZhY3RvciwgdGhlIHNvdXJjZSBbY29kZV0oaHR0cHM6Ly9yZHJyLmlvL2NyYW4vUmlza1BvcnRmb2xpb3Mvc3JjL1IvY292RXN0aW1hdGlvbi5SKSBvZiB0aGUgbGlicmFyeSB1dGlsaXplcyB0aGUgYGZhY3RhbmFsYCBzdGF0cyBjb21tYW5kIGZvciBmYWN0b3IgYW5hbHlzaXMuIEZvciBmdXJ0aGVyIGluZm8sIHNlZSB0aGlzIFtsaW5rXShodHRwczovL3d3dy5nZW8uZnUtYmVybGluLmRlL2VuL3Yvc29nYS9HZW9kYXRhLWFuYWx5c2lzL2ZhY3Rvci1hbmFseXNpcy9BLXNpbXBsZS1leGFtcGxlLW9mLUZBL2luZGV4Lmh0bWwpLiBUaGUgImNvbnN0YW50IiBtZXRob2QgcmVmZXJzIHRvIHRoZSBjYXNlIGluIHdoaWNoIHRoZSBjb3ZhcmlhbmNlIG1hdHJpeCBpcyBzaHJhbmsgdG93YXJkcyBhIGNvdmFyaWFuY2UgbWF0cml4IHdpdGggY29uc3RhbnQgY29ycmVsYXRpb24uIFRoaXMgbWV0aG9kIGlzIHBhcnNpbW9uaW91cyBhbmQsIHBvdGVudGlhbGx5LCBsZWFkcyB0byByZWR1Y3Rpb24gb2YgZXN0aW1hdGlvbiByaXNrLiBGaW5hbGx5LCB0aGUgVW5pZm9ybSBtZXRob2QgY29ycmVzcG9uZHMgdG8gIm9uZXBhcm0iIGFuZCBpcyBjb25zaWRlcmVkICBldmVuIG1vcmUgcGFyc2ltb25pb3VzLCBzaW5jZSB0aGUgcHJpb3IgaXMgZ2l2ZW4gYnkgYSBzaW5nbGUgb25lLXBhcmFtZXRlciBtYXRyaXguIEluIHRoaXMgY2FzZSwgYWxsIHZhcmlhbmNlcyBhcmUgZXF1YWwsIHdoaWxlIGNvdmFyaWFuY2VzIGFyZSBzZXQgdG8gemVyby4gCgpBcyBhIGZpbmFsIHN1bW1hcnksIGxldCB1cyByZWNvbnN0cnVjdCB0aGUgcHJldmlvdXMgcGxvdCBidXQgdXNpbmcgdmFsdWUtYXQtcmlzayAoVmFSKToKYGBge3J9CnAgPC0gZ2dwbG90X3N1bSgiVmFSIikKZ2dwbG90bHkocCx3aWR0aCA9IDgwMCwgaGVpZ2h0ID0gNjAwKQpgYGAKSW4gdGVybXMgb2YgVmFSLCB3ZSBzZWUgdGhhdCB0aGUgRmFjdG9yIGFwcHJvYWNoIHJlc3VsdHMgaW4gdGhlIGxvd2VzdCBkb3duc2lkZSByaXNrIGZvciBhbGwgZGF0YXNldHMsIGV4Y2VwdCB0aGUgNSBGYW1hLUZyZW5jaCBpbmR1c3RyeSBwb3J0Zm9saW9zLiAKCmBgYHtyfQpsYXBwbHkoc3VtX2RhdGFfbGlzdCwgZnVuY3Rpb24oeCkgIG5hbWVzKHNvcnQoeFsiVmFSIixdLGRlY3JlYXNpbmcgPSBGKVsxOjNdKSkKYGBgCk92ZXJhbGwsIHRoZSBhYm92ZSByZXN1bHRzIGluZGljYXRlIHRoYXQgc2hyaW5rYWdlIHRlY2huaXF1ZXMgcHJvdmlkZSBncmVhdGVyIGltcHJvdmVtZW50IHdoZW4gb25lIGlzIGRlYWxpbmcgd2l0aCBsYXJnZXIgbnVtYmVyIG9mIGFzc2V0cy4gVGhpcyBkZW5vdGVzIHRoZSBjYXNlIG9mIGdyZWF0IGVzdGltYXRpb24gcmlzay4gQWRkaXRpb25hbGx5LCB0aGUgZmFjdCB0aGF0IHRoZSBmYWN0b3IgbW9kZWwgZG9taW5hdGVzIG90aGVyIHRlY2huaXF1ZXMsIHRoaXMgaW5kaWNhdGVzIHRoYXQgdGhlIGRlY2lzaW9uLW1ha2VyIGNhbiBmdWxseSBzaHJpbmsgdGhlIGNvdmFyaWFuY2UgbWF0cml4IHRvd2FyZHMgYSBwcmlvciB3aXRob3V0IHRoZSBuZWVkIG9mICBkZXRlcm1pbmluZyB0aGUgc2hyaW5rYWdlIGludGVuc2l0eS4gQ2xlYXJseSwgdG8gZ2VuZXJhbGl6ZSB0aGlzIGNvbmplY3R1cmUsIG9uZSBuZWVkcyB0byB2YWxpZGF0ZSBvdmVyIGRpZmZlcmVudCBkYXRhc2V0cywgc2FtcGxlIHNpemVzLCBhbmQgZXN0aW1hdGlvbiBmcmVxdWVuY2llcy4gCgoKIyBDb25jbHVkaW5nIFJlbWFya3MKVGhpcyB2aWduZXR0ZSBwcm92aWRlcyBhIHNpbXBsZSBwYXJhZGlnbSB0byBldmFsdWF0ZSB0aGUgb3V0LW9mLXNhbXBsZSBwZXJmb3JtYW5jZSBvZiBkaWZmZXJlbnQgZXN0aW1hdGlvbiBtZXRob2RzIGZvciBjb3ZhcmlhbmNlIG1hdHJpY2VzLiBJbnRlcmVzdGVkIHJlc2VhcmNoZXMgaW4gcHJvcG9zaW5nIG5ldyBtZXRob2RzIGZvciBjb3ZhcmlhbmNlIG1hdHJpY2VzIHdvdWxkIGdyZWF0bHkgYmVuZWZpdCBmcm9tIGBSaXNrUG9ydGZvbGlvc2AgaW4gc2V0dGluZyBiZW5jaG1hcmtzIGFuZCB0ZXN0aW5nIG5ldyBkZWNpc2lvbiBydWxlcy4gTm90ZSB0aGF0IHRoZSBhYm92ZSBhbmFseXNpcyBkb2VzIG5vdCB0YWtlIGludG8gYWNjb3VudCBzdGF0aXN0aWNhbCBzaWduaWZpY2FuY2UuIE9uZSBwb3RlbnRpYWwgcmVtZWR5IGlzIHRvIHBlcmZvcm0gYm9vdHN0cmFwIGFuZCBhc3Nlc3Mgd2hldGhlciBvdXRwZXJmb3JtYW5jZSBpcyBub3QgbWVyZWx5IGEgc3RhdGlzdGljYWwgZmx1a2UuIEkgbGVhdmUgdGhpcyBmb3IgYSBmdXR1cmUgZW5kZWF2b3IuCgoK