Overview

In this vignette, I will be working with the ReinforcementLearning R package to introduce Q-learning in the context of asset allocation. Specifically, I will demonstrate how to train the agent based on state-action-reward tuples. The illustration is model and environment free. The idea is to determine an optimal policy given randomized choices and rewards, from which the agent learns and adapts. Based on these policies, we evaluate its performance and consider using different parametrization for sensitivity analysis.

Quick Introduction

A famous example is the gridworld one, where the agent has to go from point A to point D via a \(2 \times 2\) grid as follows: \[ \left[\begin{array}{cc} A| & D\\ B & C \end{array}\right] \] At each cell, the agent can take the following actions: up, right, down, or left. The agent cannot go directly from \(A\) to \(D\) by moving to the right as there is a barrier between the two cells. Clearly, to the naked eye, we can easily determine that the optimal policy is to take action “down” at state A, action “right” at state B, and action “up” at state C in order to reach the objective goal. At the same time, the agent might stall by looping between \(B\) and \(C\). Hence, the idea is also to find the path as soon as possible. After all, the longer we wait, the less utility we enjoy in consuming goods.

Such an environment is built in the ReinforcementLearning library. We can retrieve the library as follows:

library(ReinforcementLearning)
env <- gridworldEnvironment
print(env)
function (state, action) 
{
    next_state <- state
    if (state == state("s1") && action == "down") 
        next_state <- state("s2")
    if (state == state("s2") && action == "up") 
        next_state <- state("s1")
    if (state == state("s2") && action == "right") 
        next_state <- state("s3")
    if (state == state("s3") && action == "left") 
        next_state <- state("s2")
    if (state == state("s3") && action == "up") 
        next_state <- state("s4")
    if (next_state == state("s4") && state != state("s4")) {
        reward <- 10
    }
    else {
        reward <- -1
    }
    out <- list(NextState = next_state, Reward = reward)
    return(out)
}
<bytecode: 0x55a9986a8788>
<environment: namespace:ReinforcementLearning>

The environment function take two arguments and returns two outputs. The arguments denote the current state \(s_t\) and action \(a_t\) taken at time \(t\). In such a dynamic environment, the action leads to a new state. In the grid case, taking action “down” while at state A leads to a new state B. Such interaction can be described using a tuple \((s_t,a_t,s_{t+1},r_{t+1})\), where \(r_{t+1}\) denoting the reward for taking action \(a_t\) at \(s_t\) and transitioning to state \(s_{t+1}\) as result. The above environment determines the next state \(s_{t+1}\) and reward \(r_{t+1}\) based on current state and action. The idea behind setting the environment infrastructure is to capture the correct “physics” and the right incentives.

To better understand the above, consider the case where we stand at cell A. Taking a different action than “down” leads to stalling, where the agent remains stuck in cell A. Such stalling results in dis-utility since we are not making progress. Nonetheless, if we take the right action, we are still far from reaching the goal, i.e., cell D. Hence, the idea is to train the agent not to “celebrate” too early. Celebration eventually comes later when the agent receives the “trophy.”

Training

In total, we have four different states, which will denote by

states <- paste("s",1:4,sep = "")
names(states) <- LETTERS[1:4]
states
   A    B    C    D 
"s1" "s2" "s3" "s4" 

On the other hand, we have four different actions:

actions <- c("up","down","left","right")

Because we have the environment set up with respect to different actions and states, we can easily simulate data. For instance, we can create a single tuple by running the following command

env("s1","up")
$NextState
[1] "s1"

$Reward
[1] -1

We could simulate some data that provides insights into how the agent interacts with the environment using randomized choices. Let us “cook” some data in this regard:

N <- 10^3
set.seed(1234)
ds <- data.frame(State = sample(states,N,replace = TRUE),
                 Action = sample(actions,N,replace = TRUE))
ds2 <- lapply(1:N, function(i) env(ds[i,1],ds[i,2])) 
ds2 <- lapply(ds2,data.frame)
ds2 <- Reduce(rbind,ds2)
ds <- data.frame(ds,ds2)
ds$Action <- as.character(ds$Action)
ds$State <- as.character(ds$State)
ds$NextState <- as.character(ds$NextState)
head(ds)

Based on the environment and randomized states and actions, we created 1000 observations denoting the \((s_t,a_t,s_{t+1},r_{t+1})\) tuple. To train the agent using the package, all we need is such data, as we shall see shortly. Nonetheless, we can easily generate such data using the package as follows

set.seed(1234)
data <- sampleExperience(N = N,env = env, states, actions)
head(data)

To compare the two we can look into the transition probabilities based on the frequency of the \((s_t,s_{t+1})\) pairs:

table(ds$State,ds$NextState)/N
    
        s1    s2    s3    s4
  s1 0.176 0.057 0.000 0.000
  s2 0.055 0.134 0.069 0.000
  s3 0.000 0.078 0.133 0.070
  s4 0.000 0.000 0.000 0.228
table(data$State,data$NextState)/N
    
        s1    s2    s3    s4
  s1 0.177 0.056 0.000 0.000
  s2 0.069 0.120 0.069 0.000
  s3 0.000 0.062 0.148 0.071
  s4 0.000 0.000 0.000 0.228

We observe that in both cases, we get a similar transition matrix.

Given either data, we can train the agent using the `ReinforcementLearning’ function. The function takes, obviously, the data as the first input. Additionally, it requires states the names of the state, next state, action, and reward columns in the data. In terms of tuning, the command takes the control parameters as the last input. These parameters are summarized as follows:

  1. Learning Rate: \(\alpha \in (0,1)\) relates to \(Q\)-learning and captures the learning rate. Similar to iterative algorithms, this parameter determines how fast the algorithm adapts. If it is too small, the learning speed is low, whereas a larger value denotes a faster learning rate.

  2. Discount Factor: \(\gamma \in (0,1)\) denotes the discount factor. We prefer consuming goods immediately. Something to be consumed in a later period is not as enjoyable unless one expects to have a greater reward to compensate for the waiting period. Hence, the smaller the value of \(\gamma\) is, the less patient the agent is, such that it attributes greater weights to current rewards.

  3. Exploration Rate: \(\epsilon \in (0,1)\) is the fraction of training episodes in which the agent ignores past learning experiences and takes a random action. This input captures the idea of exploration versus exploitation. As soon as the agent starts figuring this out, it might get too comfortable repeating the same actions. However, the idea behind this is to encourage the agent to perhaps there might be something else out there worth trying. Hence, a larger \(\epsilon\) value denotes a greater exploration rate.

For now, we set the following configurations:

control <- list(alpha = 0.1, gamma = 0.95, epsilon = 0.1)

Given the above, all we need to do is to run the following:

model <- ReinforcementLearning(data,
                               s = "State",
                               a = "Action",
                               r = "Reward",
                               s_new = "NextState",
                               control = control)
model
State-Action function Q
       right        up      down      left
s1  3.281970  3.442551  4.819512  3.443300
s2  5.827021  3.320670  4.706644  4.827368
s3  5.939138  6.767722  5.852077  4.770131
s4 -3.959678 -4.150526 -3.970640 -3.993890

Policy
     s1      s2      s3      s4 
 "down" "right"    "up" "right" 

Reward (last iteration)
[1] -219

A couple of comments of order. We observe that the algorithm returns the \(Q\) function. Such a function captures the optimal policy. In this regard, it tells us how much reward there is b taking either one of the four actions at each state. For instance, we observe that the larger value at state \(A\) (s1) is when the action “down” is taken. The same applies to the other states. However, at cell \(D\) (state s4), we observe that it does not matter at that point since the main trophy has been received, and taking further action would not result in a further reward. Indeed, we can see this from the “Policy” output, which provides guidance in terms of what action to be taken based on each state, which is consistent with the shortest path.

As a confirmation, we repeat the above but use our simulated data to see confirm whether we get the same result:

model2 <- ReinforcementLearning(ds,
                                s = "State",
                                a = "Action",
                                r = "Reward",
                                s_new = "NextState",
                                control = control)
model2
State-Action function Q
       right        up      down      left
s1  3.517780  3.455531  4.939327  3.378204
s2  6.053089  3.455700  4.988266  4.946638
s3  5.926172  6.779527  5.907719  5.009214
s4 -4.150526 -3.970640 -3.993890 -3.959678

Policy
     s1      s2      s3      s4 
 "down" "right"    "up"  "left" 

Reward (last iteration)
[1] -230

In the following, we will work with the data object for brevity, but the results follow suit regardless. Before we move on, note that either model returns a reward. The reward here denotes the summation of the total rewards in the data, i.e.,

sum(data$Reward) == model$Reward
[1] TRUE

and

sum(ds$Reward) == model2$Reward
[1] TRUE

Updating Policy

Since we know the solution, we can conclude that the final result is the optimal policy. However, what if the environment were more complex than the one considered in this example? Also, suppose that we get new data by the time we are done training the model. Can we improve the policy further? Without delving into technical details, we could argue that the model learns better by providing it greater data based after interacting with the environment with guidance. In this case, we are interested in updating existing policy as data become available.

Specifically, in the above, we generated data using random interactions without guidance. Now that we figured out something, we can perhaps generate data in some directions. For instance, we know to some extent what the agent should day at state s1 given the policy from model. We can use the original model as a reference point and generate additional data as follows

data_new <- sampleExperience(N = N, 
                             env = env, 
                             states = states, 
                             actions = actions, 
                             model = model, # important
                             actionSelection = "epsilon-greedy",
                             control = control)

Different from before, the sampleExperience now uses two additional arguments. The first is specifying an existing model we could rely on to generate the data. The second is the action method. In the first one, the action method was completely random, whereas now it \(\epsilon\)-greedy, i.e., the agent will follow the policy \(1-\epsilon\) of the time, and \(\epsilon\) of the cases it will choose random actions as we did originally. We can see that the sample data, in this case, results in a much higher reward since the agent can rely on some policy to determine the best action

sum(data_new$Reward)
[1] 1486

To make things more interesting, let us create a function where we update the policy \(M\) times. The function will summarize all the above steps in a single function as follows.

M <- 10
RL_update_fun <- function(control_i) {
  
  set.seed(1)
  data <- sampleExperience(N = N,env = env, states, actions)
  model <- ReinforcementLearning(data,
                                 s = "State",
                                 a = "Action",
                                 r = "Reward",
                                 s_new = "NextState",
                                 control = control_i)
  reward_seq <- sum(model$Reward)
  
  for (iter in 2:M) {
    
    set.seed(iter)
    data_new <- sampleExperience(N = N, 
                                 env = env, 
                                 states = states, 
                                 actions = actions, 
                                 model = model,                                  
                                 actionSelection = "epsilon-greedy",
                                 control = control_i)
    # update model
    model <- ReinforcementLearning(data_new,
                                   s = "State",
                                   a = "Action",
                                   r = "Reward",
                                   s_new = "NextState",                       
                                   control = control)
    
    reward_seq <- c(reward_seq,sum(model$Reward))
    
  }
  
  return(reward_seq)
}

Given the above function, we can analyze how the policy updates depend on the inputs. In the following, I consider different values of \(\epsilon\), which denotes the proportion of time the algorithm takes a random chance. Naturally, we expect more noise to be associated with higher values. By noise, I mean that if the algorithm figures out the right optimal policy, then it should reach the maximum possible reward earlier and exhibit more stability regardless of the iterations.

library(parallel)
control1 <- list(alpha = 0.1, gamma = 0.95, epsilon = 0.5)
control2 <- list(alpha = 0.1, gamma = 0.95, epsilon = 0.25)
control3 <- list(alpha = 0.1, gamma = 0.95, epsilon = 0.1)
control4 <- list(alpha = 0.1, gamma = 0.95, epsilon = 0.01)

control_list <- list(control1,control2,control3,control4)
RL_list <- mclapply(control_list,RL_update_fun,mc.cores = 4)

Let us plot the rewards from each algorithm

library(ggplot2)
library(plotly)
rewards_iter <- lapply(1:length(control_list),
                       function(i) data.frame(Reward = RL_list[[i]], 
                                              Iteration = 1:M, 
                                              epsilon = control_list[[i]]$epsilon ))
rewards_iter <- Reduce(rbind,rewards_iter)
rewards_iter$epsilon <- as.factor(rewards_iter$epsilon)
p <- ggplot(data = rewards_iter,aes(x = Iteration,y = Reward, type = epsilon,colour = epsilon)) +
  geom_line() + geom_point()
ggplotly(p)

We can see that the specification with the lowest \(\epsilon\) value results in higher rewards during the last \(M - 1\) iterations. At the same time, we note that the algorithm will always follow a random policy regardless of the number of iterations. One potential adjustment is to reduce the value of the \(\epsilon\) the more iterations we perform. The following function does so by setting \(\epsilon/m\), where \(m = 1,...,50\). If we start with \(\epsilon = 0.5\), by the 50th iteration the algorithm sets \(\epsilon = 0.01\).

RL_update_fun <- function(control_i) {
  
  set.seed(1)
  data <- sampleExperience(N = N,env = env, states, actions)
  model <- ReinforcementLearning(data,
                                 s = "State",
                                 a = "Action",
                                 r = "Reward",
                                 s_new = "NextState",
                                 control = control_i)
  reward_seq <- sum(model$Reward)
  
  for (iter in 2:M) {
    
    control_i$epsilon <- control_i$epsilon/iter
    
    set.seed(iter)
    data_new <- sampleExperience(N = N, 
                                 env = env, 
                                 states = states, 
                                 actions = actions, 
                                 model = model,                                  
                                 actionSelection = "epsilon-greedy",
                                 control = control_i)
    # update model
    model <- ReinforcementLearning(data_new,
                                   s = "State",
                                   a = "Action",
                                   r = "Reward",
                                   s_new = "NextState",                       
                                   control = control)
    
    reward_seq <- c(reward_seq,sum(model$Reward))
    
  }
  
  return(reward_seq)
}

M <- 50
rew_seq <- RL_update_fun(control1)

We can visualize the total rewards as a function of iterations as follows:

ds_plot <- data.frame(Reward = rew_seq, Iteration = 1:M)
p <- ggplot(data = ds_plot,aes(x = Iteration,y = Reward)) +
  geom_line() + geom_point()
ggplotly(p)

We observe that the algorithm demonstrates lower volatility as we approach the last iteration.

Predictions

Similar to other models in R, such as linear regressions or machine learning algorithms via caret, the RL model can be utilized in the generic predict function. For instance, given our initial data, we can see how the actions get updated based on learning. The table below demonstrates the difference between the random actions taken versus those that the policy guides. Greater values in the off-diagonal elements indicate greater discrepancy. If the model did not learn/update, we expect to get the same policy as the random one.

action_predict <- predict(model,data$State)
table(data$Action,action_predict)
       action_predict
        down right  up
  down    56   116  70
  left    57   124  62
  right   52   114  78
  up      68   132  71

This function is helpful in evaluating the model after each training episode. Additionally, it allows determining the reward regardless of the context used.

Tactital Asset Allocation

Data

I will work with two main packages to manipulate time series and dates. In terms of assets, I will consider the problem of a tactical asset allocation where the agent rotates between high and low risk assets. For the high risk assets, I consider the SPY ETF to represent the stock market. For the low risk, I will consider cash with zero return for simplicity. This can be replaced by a Treasury bond or a more defensive asset. In this example, I assume that the return on cash is zero regardless of interest/inflation rates.

library(quantmod)
library(lubridate)
library(PerformanceAnalytics)

tics <- "SPY"
P_list <- lapply(tics, function(x) get( getSymbols(x,from = "1990-01-01") )  )
P_list <- lapply(P_list,function(x) x[,6])
P <- Reduce(merge,P_list)
P <- apply.monthly(P,last)
R <- na.omit(P/lag(P)) - 1
ds_plot <- R
R_port <- 0.6*R + 0.4*0
R_port <- merge(R,R_port)
chart.CumReturns(R_port)

The black line above denotes the return on a 100% position in the SPY, whereas the red line denotes the 60-40 portfolio that allocates 60% to the SPY and 40% to cash. Overall, we observe that the SPY outperforms the 60-40 portfolio in terms of total return since it has greater loading on the risk premium of the stock market. At the same time, we observe that the 60-40 provides a greater hedge during market sell-offs mitigating the downside risk. Traditionally, the 60-40 allocates 40% to Treasury bonds which serve as a safe haven asset (flight-to-quality) during increased uncertainty in the market. These dynamics imply a negative correlation between the two assets, which results in enhanced risk-adjusted returns. However, in our example with cash, the correlation is zero.

RL Application

The idea behind RL is to train the agent to learn the dynamics of the tactical asset allocation problem. Specifically, we are interested in a model-free environment where the agent observes certain actions and rewards to determine the optimal policy. To do so, we will consider descriptive analysis first, i.e., in-sample. Then, we will consider some backtesting to evaluate the appeal of RL out-of-sample.

Let us set up the platform so we can run the RL function. Recall that the RL main function takes the data in the format of \((s_t,a_t,s_{t+1},r_{t+1})\) tuples. Hence, we need to determine the state at time \(t\), corresponding to month \(t\) in our data. Note that the asset return is continuous, whereas the state \(s_t\) is discrete. Hence, we need to utilize a signal from the returns to determine the market state. This can be done in different ways, e.g., economic index or other financial indicators such as VIX. In the following illustration, I consider a simple case where we have three states determined based on the return level of the asset, denoting low, medium, and high levels.

Before we get started, we set up a number of main parameters

alph <- 0.1 # learning speed
r <- 0.02 # risk free rate
gam <- 1/(1+r)^(1/12) # monthly discount rate
eps <- 0.1
tau <- 0.01 # sets the threshold which determines the state

We determine \(\gamma\) by assuming a risk-free annual rate of 2%. Hence, the discount factor on a monthly basis is \[ \gamma = \left(\frac{1}{1+r} \right)^{1/12} \] The parameter \(\tau\) denotes the threshold of the SPY return that captures the state of the market. In our case, a return below \(-\tau\) (above \(\tau\)) denotes state \(s_t = -1\) (\(s_t = 1\)). Otherwise, the state is \(s_t = 0\). We can easily define the states as follows

ds <- R
ds <- data.frame(Date = date(ds), ds)
ds$State <- (ds$SPY.Adjusted> tau)*1 + -(ds$SPY.Adjusted < -tau)*1
ds$State <- as.character(ds$State)
ds$NextState <- data.table::shift(ds$State,-1)
head(ds)

Next, we need to determine action and rewards. The action space is also discrete. For simplicity, we consider a discrete action space where the agent longs a fraction of the risky asset as \(a_t = 1/k\) for \(k = 1,...,10\). This imposes that the agent longs a portion of the stock market regardless of the current state. Same as in the grid example, we consider random actions where the agent takes random portfolio choices as

set.seed(1)
ds$Action <- sample((1:10)/10,nrow(ds),replace = TRUE)
head(ds)

We have determined the \((s_t,a_t,s_{t+1})\) tuple so far. What left to determine is the reward for taking action \(a_t\) while transitioning from state \(s_t\) to state \(s_{t+1}\). To do so, we need a reward function that takes into account the dis-utility of losses. A natural candidate is to map returns via a constant absolute risk aversion (CARA) utility function with a given risk aversion parameter denoted by RA to control for the agent risk aversion:

RA <- 5 # sets the risk aversion level
U <- function(x,RA) 1-exp(-RA*x)
x <- seq(-0.1,1,length = 100)
U_3 <- function(x) U(x,3)
U_10 <- function(x) U(x,10)
y1 <- sapply(x,U_3)
y2 <- sapply(x,U_10)
plot(y1 ~ x,type = "l",ylim = range(c(y1,y2)), ylab = "Utility", xlab = "Return")
lines(y2 ~ x,col = 2)
abline(v = 0,lty = 2)
grid(10)

The above plot demonstrates the utility of two agents where the red line is the one with higher risk aversion. For negative returns, we observe that the agent with higher risk aversion “suffers” more. On the other hand, such an agent enjoys higher utility as returns become positive. Given the CARA utility, we can map the portfolio return positions into rewards as follows

ds$Reward <- ds$Action*data.table::shift(ds$SPY.Adjusted,-1)
ds$Action <- as.character(ds$Action)
ds$Reward <- U(ds$Reward,RA)
ds <- na.omit(ds)
head(ds)

Now that we have represented the data using a \((s_t,a_t,s_{t+1})\) tuple, we can move on to train the model. We have the default controls as before

control <- list(alpha = alph, gamma = gam, epsilon = eps)

model_spy <- ReinforcementLearning(ds,
                                   s = "State",
                                   a = "Action",
                                   r = "Reward",
                                   s_new = "NextState",
                                   control = control)

ds$RL_Action <- as.numeric(predict(model_spy,ds$State))
ds$Next_Ret <- data.table::shift(ds$SPY.Adjusted,-1)
ds$Portfolio_Ret_RL <- ds$RL_Action*ds$Next_Ret
ret <- na.omit(ds$Portfolio_Ret_RL)
SR_RL <- mean(U(ret,RA))

# compare to random choices
ret<- as.numeric( ds$Action)*ds$Next_Ret
ret <- na.omit(ret)
SR_random <- mean(U(ret,RA))
round(data.frame(Random = SR_random,RL = SR_RL)*100,2)

The above commands train the agent and result in a higher utility relative to random actions. However, the question remains whether this is an optimal policy. The above is based on a single random iteration. Perhaps if we feed the model more data, the agent can attain a higher reward.

The major difference here is that we do not know the environment of how each action affects the transition from state \(s_t\) to \(s_{t+1}\). Hence, updating the policy is not straightforward. One potential extension is to consider an equilibrium model such that returns are endogenously determined based on action and state. Nonetheless, in this example, we will refrain from such analysis and consider an environment-free framework. The challenge here, however, is how to simulate data without knowing the environment.

To overcome the above challenge, we consider an ad-hoc modification. Similar to the \(\epsilon\)-greedy approach, we simulate a proportion of actions that are chosen randomly, whereas the other actions follow an initial model. At each iteration, we choose \(\epsilon\) proportion of months where the agent takes random actions, whereas, in the \(1-\epsilon\) months, the agent follows the previous policy. We iterate this several times until we attain a certain satisfactory threshold, which we set based on a benchmark. Specifically, the benchmark is set relative to holding the SPY passively, which corresponds to the following reward

x <- R$SPY.Adjusted
SPY_SR <- mean(U(x,RA))
SPY_SR
[1] 0.01924738

We observe that the initial policy above underperforms the passive one that longs the SPY 100% of the time. Our goal is to find a policy that outperforms the benchmark. We perform the following while function, which we run until we beat the benchmark or exhaust a certain number of iterations, which we set to 100.

tot_iter <- 100
iter <- 2
model_list <- list(model_spy)
rewards_seq <- SR_RL
i <- 0
while (!SR_RL > SPY_SR) {
  
  i <- i + 1
  ds <- R
  ds <- data.frame(Date = date(ds), ds)
  ds$State <- (ds$SPY.Adjusted > tau)*1 + -(ds$SPY.Adjusted < -tau)*1
  ds$State <- as.character(ds$State)
  ds$NextState <- data.table::shift(ds$State,-1)
  
  # take action with respect to the previous model
  ds$RL_Action <- as.numeric(predict(model_spy,ds$State))
  sample_index <- sample(1:nrow(ds),1 + floor(nrow(ds)*0.5*(1 - iter/tot_iter)))
  ds$Action <- ds$RL_Action
  ds$Action[sample_index] <- sample(1:10/10,length(sample_index),replace = TRUE)
  
  ds$Reward <- ds$Action*data.table::shift(ds$SPY.Adjusted,-1)
  ds$Reward <- U(ds$Reward,RA)
  ds$Action <- as.character(ds$Action)
  ds <- na.omit(ds)
  
  # train the model based on random choices
  model_spy_new <- ReinforcementLearning(ds,
                                         s = "State",
                                         a = "Action",
                                         r = "Reward",
                                         s_new = "NextState",
                                         control = control,
                                         model = model_spy)
  
  ds$RL_Action <- as.numeric(predict(model_spy_new,ds$State))
  ds$Next_Ret <- data.table::shift(ds$SPY.Adjusted,-1)
  ds$Portfolio_Ret_RL <- ds$RL_Action*ds$Next_Ret
  ret <- na.omit(ds$Portfolio_Ret_RL)
  SR_RL_new <- mean(U(ret,RA))
  
  # compute the benchmark for consistent evaluation
  x <- na.omit(ds$Next_Ret)
  SPY_reward <- mean(U(x,RA))
  SPY_SR <- SPY_reward
  
  if(i > 1000)
    break
  # update the model only if performance is better than previous
  if(SR_RL_new > SR_RL) {
    model_spy <- model_spy_new
    SR_RL <- SR_RL_new
    iter <- iter + 1
    cat("Model Updated ", iter, "\n")
    model_list <- c(model_list,list(model_spy))
    rewards_seq <- c(rewards_seq,SR_RL)
    i <- 0
  }
  
  if(iter > tot_iter) 
    break
}
Model Updated  3 

For the above risk aversion, which we set to 5, the loop terminates during the third iteration. In unreported results, the model takes longer to find a policy that outperforms the benchmark when the risk aversion is low. Indeed, if the agent is risk tolerant, it makes it harder to find a policy that outperforms the SPY since the agent could be better off holding the SPY passively. On the other hand, the risk-averse agent would be better off allocating less than 100% to the SPY to mitigate risk aversion.

Let us take a look at the final model and policy:

model_spy_new
State-Action function Q
         0.7       0.8       0.9          1       0.1        0.2       0.3       0.4
-1 0.3816035 0.2078880 0.1597925 0.26549405 0.1971610 0.19540204 0.1638846 0.1659740
0  0.1944525 0.3260284 0.1370731 0.05240283 0.1051063 0.04714781 0.1214657 0.1488058
1  0.3037000 0.2732329 0.3564709 0.21113729 0.2755970 0.20727959 0.2733207 0.2663940
         0.5       0.6
-1 0.1820516 0.2452856
0  0.1285650 0.1093987
1  0.3162321 0.2457833

Policy
   -1     0     1 
"0.7" "0.8" "0.9" 

Reward (last iteration)
[1] 5.267385

Consistent with common sense, the policy indicates that the agent reduces exposure to risky assets in states accompanied by low returns. Specifically, the exposure to reduced to 70% equity. On the other hand, during medium (high) states, the exposure is 80% (90%).

Let us take a look at how such a policy performs in practice:

ds_plot <- ds[,c("Next_Ret","Portfolio_Ret_RL")]
date_names <- rownames(ds_plot)[-1]
ds_plot <- na.omit(ds_plot)
rownames(ds_plot) <- date_names
ds_plot <- as.xts(ds_plot)
chart.CumReturns(ds_plot,geometric = FALSE)

We observe that the RL agent underperforms the passive fund in terms of terminal wealth. However, let us take into account the risk

my_sum <- function(x) {
  m <- mean(x)*12
  s <- sd(x)*sqrt(12)
  sr <- m/s
  sv <- sd(x[x<0])*sqrt(12)
  sr2 <- m/sv
  VaR <- mean(x) - quantile(x,0.05)
  return(c(m,s,sv,sr,sr2,VaR))
}

result <- data.frame(apply(ds_plot,2,my_sum)) 
rownames(result) <- c("Mean","Volatility","Semi-Volatility","Sharpe","Sortino","VaR")
round(result,3)

Consistent with the above plot, we see that the RL policy results in lower returns and risk simultaneously. Regarding risk-adjusted returns, we observe that the RL results in higher Sharpe and Sortino ratios. Additionally, we measure downside risk using value-at-risk (VaR). Finally, we observe that the RL strategy results in lower tail risk.

Thoughts

The above analysis is conducted in-sample and, hence, is descriptive by design. Nevertheless, one can address interesting questions regarding setting the right investment policy for investors with different risk preferences. This sheds interesting light on the appeal of Robo-advising. Moreover, in terms of portfolio selection, future research should consider the out-of-sample analysis and evaluate the appeal of RL from a predictive point of view. I leave these for future research.

LS0tCnRpdGxlOiAiVGFjdGljYWwgQXNzZXQgQWxsb2NhdGlvbiB1c2luZyBSZWluZm9yY2VtZW50IExlYXJuaW5nIgojb3V0cHV0OiBybWFya2Rvd246OmdpdGh1Yl9kb2N1bWVudApvdXRwdXQ6CiAgaHRtbF9ub3RlYm9vazogZGVmYXVsdAogIHBkZl9kb2N1bWVudDogZGVmYXVsdAphdXRob3I6IE1hamVlZCBTaW1hYW4KZGF0ZTogU2VwdCA2LCAyMDIyCmZpZ193aWR0aDogNTAKLS0tCgpgYGB7cixlY2hvPUZBTFNFfQpybShsaXN0ID0gbHMoKSkKYGBgCgoKIyBPdmVydmlldwoKSW4gdGhpcyB2aWduZXR0ZSwgSSB3aWxsIGJlIHdvcmtpbmcgd2l0aCB0aGUgYFJlaW5mb3JjZW1lbnRMZWFybmluZ2AgUiBwYWNrYWdlIHRvIGludHJvZHVjZSBRLWxlYXJuaW5nIGluIHRoZSBjb250ZXh0IG9mIGFzc2V0IGFsbG9jYXRpb24uIFNwZWNpZmljYWxseSwgSSB3aWxsIGRlbW9uc3RyYXRlIGhvdyB0byB0cmFpbiB0aGUgYWdlbnQgYmFzZWQgb24gc3RhdGUtYWN0aW9uLXJld2FyZCB0dXBsZXMuIFRoZSBpbGx1c3RyYXRpb24gaXMgbW9kZWwgYW5kIGVudmlyb25tZW50IGZyZWUuIFRoZSBpZGVhIGlzIHRvIGRldGVybWluZSBhbiBvcHRpbWFsIHBvbGljeSBnaXZlbiByYW5kb21pemVkIGNob2ljZXMgYW5kIHJld2FyZHMsIGZyb20gd2hpY2ggdGhlIGFnZW50IGxlYXJucyBhbmQgYWRhcHRzLiBCYXNlZCBvbiB0aGVzZSBwb2xpY2llcywgd2UgZXZhbHVhdGUgaXRzIHBlcmZvcm1hbmNlIGFuZCBjb25zaWRlciB1c2luZyBkaWZmZXJlbnQgcGFyYW1ldHJpemF0aW9uIGZvciBzZW5zaXRpdml0eSBhbmFseXNpcy4KCiMgUXVpY2sgSW50cm9kdWN0aW9uCgpBIGZhbW91cyBleGFtcGxlIGlzIHRoZSBncmlkd29ybGQgb25lLCB3aGVyZSB0aGUgYWdlbnQgaGFzIHRvIGdvIGZyb20gcG9pbnQgQSB0byBwb2ludCBEIHZpYSBhICQyIFx0aW1lcyAyJCBncmlkIGFzIGZvbGxvd3M6CiQkClxsZWZ0W1xiZWdpbnthcnJheX17Y2N9CkF8ICYgRFxcCkIgJiBDClxlbmR7YXJyYXl9XHJpZ2h0XQokJApBdCBlYWNoIGNlbGwsIHRoZSBhZ2VudCBjYW4gdGFrZSB0aGUgZm9sbG93aW5nIGFjdGlvbnM6IHVwLCByaWdodCwgZG93biwgb3IgbGVmdC4gVGhlIGFnZW50IGNhbm5vdCBnbyBkaXJlY3RseSBmcm9tICRBJCB0byAkRCQgYnkgbW92aW5nIHRvIHRoZSByaWdodCBhcyB0aGVyZSBpcyBhIGJhcnJpZXIgYmV0d2VlbiB0aGUgdHdvIGNlbGxzLiBDbGVhcmx5LCB0byB0aGUgbmFrZWQgZXllLCB3ZSBjYW4gZWFzaWx5IGRldGVybWluZSB0aGF0IHRoZSBvcHRpbWFsIHBvbGljeSBpcyB0byB0YWtlIGFjdGlvbiAiZG93biIgYXQgc3RhdGUgQSwgYWN0aW9uICJyaWdodCIgYXQgc3RhdGUgQiwgYW5kIGFjdGlvbiAidXAiIGF0IHN0YXRlIEMgaW4gb3JkZXIgdG8gcmVhY2ggdGhlIG9iamVjdGl2ZSBnb2FsLiBBdCB0aGUgc2FtZSB0aW1lLCB0aGUgYWdlbnQgbWlnaHQgc3RhbGwgYnkgbG9vcGluZyBiZXR3ZWVuICRCJCBhbmQgJEMkLiBIZW5jZSwgdGhlIGlkZWEgaXMgYWxzbyB0byBmaW5kIHRoZSBwYXRoIGFzIHNvb24gYXMgcG9zc2libGUuIEFmdGVyIGFsbCwgdGhlIGxvbmdlciB3ZSB3YWl0LCB0aGUgbGVzcyB1dGlsaXR5IHdlIGVuam95IGluIGNvbnN1bWluZyBnb29kcy4gCgoKU3VjaCBhbiBlbnZpcm9ubWVudCBpcyBidWlsdCBpbiB0aGUgYFJlaW5mb3JjZW1lbnRMZWFybmluZ2AgbGlicmFyeS4gV2UgY2FuIHJldHJpZXZlIHRoZSBsaWJyYXJ5IGFzIGZvbGxvd3M6IApgYGB7cix3YXJuaW5nPUZBTFNFLG1lc3NhZ2U9RkFMU0V9CmxpYnJhcnkoUmVpbmZvcmNlbWVudExlYXJuaW5nKQplbnYgPC0gZ3JpZHdvcmxkRW52aXJvbm1lbnQKcHJpbnQoZW52KQpgYGAKVGhlIGVudmlyb25tZW50IGZ1bmN0aW9uIHRha2UgdHdvIGFyZ3VtZW50cyBhbmQgcmV0dXJucyB0d28gb3V0cHV0cy4gVGhlIGFyZ3VtZW50cyBkZW5vdGUgdGhlIGN1cnJlbnQgc3RhdGUgJHNfdCQgYW5kIGFjdGlvbiAkYV90JCB0YWtlbiBhdCB0aW1lICR0JC4gSW4gc3VjaCBhIGR5bmFtaWMgZW52aXJvbm1lbnQsIHRoZSBhY3Rpb24gbGVhZHMgdG8gYSBuZXcgc3RhdGUuIEluIHRoZSBncmlkIGNhc2UsIHRha2luZyBhY3Rpb24gImRvd24iIHdoaWxlIGF0IHN0YXRlIEEgbGVhZHMgdG8gYSBuZXcgc3RhdGUgQi4gU3VjaCBpbnRlcmFjdGlvbiBjYW4gYmUgZGVzY3JpYmVkIHVzaW5nIGEgdHVwbGUgJChzX3QsYV90LHNfe3QrMX0scl97dCsxfSkkLCB3aGVyZSAkcl97dCsxfSQgZGVub3RpbmcgdGhlIHJld2FyZCBmb3IgdGFraW5nIGFjdGlvbiAkYV90JCBhdCAkc190JCBhbmQgdHJhbnNpdGlvbmluZyB0byBzdGF0ZSAkc197dCsxfSQgYXMgcmVzdWx0LiBUaGUgYWJvdmUgZW52aXJvbm1lbnQgZGV0ZXJtaW5lcyB0aGUgbmV4dCBzdGF0ZSAkc197dCsxfSQgYW5kIHJld2FyZCAkcl97dCsxfSQgYmFzZWQgb24gY3VycmVudCBzdGF0ZSBhbmQgYWN0aW9uLiBUaGUgaWRlYSBiZWhpbmQgc2V0dGluZyB0aGUgZW52aXJvbm1lbnQgaW5mcmFzdHJ1Y3R1cmUgaXMgdG8gY2FwdHVyZSB0aGUgY29ycmVjdCAicGh5c2ljcyIgYW5kIHRoZSByaWdodCBpbmNlbnRpdmVzLiAKClRvIGJldHRlciB1bmRlcnN0YW5kIHRoZSBhYm92ZSwgY29uc2lkZXIgdGhlIGNhc2Ugd2hlcmUgd2Ugc3RhbmQgYXQgY2VsbCBBLiBUYWtpbmcgYSBkaWZmZXJlbnQgYWN0aW9uIHRoYW4gImRvd24iIGxlYWRzIHRvIHN0YWxsaW5nLCB3aGVyZSB0aGUgYWdlbnQgcmVtYWlucyBzdHVjayBpbiBjZWxsIEEuIFN1Y2ggc3RhbGxpbmcgcmVzdWx0cyBpbiBkaXMtdXRpbGl0eSBzaW5jZSB3ZSBhcmUgbm90IG1ha2luZyBwcm9ncmVzcy4gTm9uZXRoZWxlc3MsIGlmIHdlIHRha2UgdGhlIHJpZ2h0IGFjdGlvbiwgd2UgYXJlIHN0aWxsIGZhciBmcm9tIHJlYWNoaW5nIHRoZSBnb2FsLCBpLmUuLCBjZWxsIEQuIEhlbmNlLCB0aGUgaWRlYSBpcyB0byB0cmFpbiB0aGUgYWdlbnQgbm90IHRvICJjZWxlYnJhdGUiIHRvbyBlYXJseS4gQ2VsZWJyYXRpb24gZXZlbnR1YWxseSBjb21lcyBsYXRlciB3aGVuIHRoZSBhZ2VudCByZWNlaXZlcyB0aGUgInRyb3BoeS4iCgojIyBUcmFpbmluZwoKSW4gdG90YWwsIHdlIGhhdmUgZm91ciBkaWZmZXJlbnQgc3RhdGVzLCB3aGljaCB3aWxsIGRlbm90ZSBieSAKYGBge3J9CnN0YXRlcyA8LSBwYXN0ZSgicyIsMTo0LHNlcCA9ICIiKQpuYW1lcyhzdGF0ZXMpIDwtIExFVFRFUlNbMTo0XQpzdGF0ZXMKYGBgCk9uIHRoZSBvdGhlciBoYW5kLCB3ZSBoYXZlIGZvdXIgZGlmZmVyZW50IGFjdGlvbnM6IApgYGB7cn0KYWN0aW9ucyA8LSBjKCJ1cCIsImRvd24iLCJsZWZ0IiwicmlnaHQiKQpgYGAKCkJlY2F1c2Ugd2UgaGF2ZSB0aGUgZW52aXJvbm1lbnQgc2V0IHVwIHdpdGggcmVzcGVjdCB0byBkaWZmZXJlbnQgYWN0aW9ucyBhbmQgc3RhdGVzLCB3ZSBjYW4gZWFzaWx5IHNpbXVsYXRlIGRhdGEuIEZvciBpbnN0YW5jZSwgd2UgY2FuIGNyZWF0ZSBhIHNpbmdsZSB0dXBsZSBieSBydW5uaW5nIHRoZSBmb2xsb3dpbmcgY29tbWFuZApgYGB7cn0KZW52KCJzMSIsInVwIikKYGBgCldlIGNvdWxkIHNpbXVsYXRlIHNvbWUgZGF0YSB0aGF0IHByb3ZpZGVzIGluc2lnaHRzIGludG8gaG93IHRoZSBhZ2VudCBpbnRlcmFjdHMgd2l0aCB0aGUgZW52aXJvbm1lbnQgdXNpbmcgcmFuZG9taXplZCBjaG9pY2VzLiBMZXQgdXMgImNvb2siIHNvbWUgZGF0YSBpbiB0aGlzIHJlZ2FyZDoKYGBge3J9Ck4gPC0gMTBeMwpzZXQuc2VlZCgxMjM0KQpkcyA8LSBkYXRhLmZyYW1lKFN0YXRlID0gc2FtcGxlKHN0YXRlcyxOLHJlcGxhY2UgPSBUUlVFKSwKICAgICAgICAgICAgICAgICBBY3Rpb24gPSBzYW1wbGUoYWN0aW9ucyxOLHJlcGxhY2UgPSBUUlVFKSkKZHMyIDwtIGxhcHBseSgxOk4sIGZ1bmN0aW9uKGkpIGVudihkc1tpLDFdLGRzW2ksMl0pKSAKZHMyIDwtIGxhcHBseShkczIsZGF0YS5mcmFtZSkKZHMyIDwtIFJlZHVjZShyYmluZCxkczIpCmRzIDwtIGRhdGEuZnJhbWUoZHMsZHMyKQpkcyRBY3Rpb24gPC0gYXMuY2hhcmFjdGVyKGRzJEFjdGlvbikKZHMkU3RhdGUgPC0gYXMuY2hhcmFjdGVyKGRzJFN0YXRlKQpkcyROZXh0U3RhdGUgPC0gYXMuY2hhcmFjdGVyKGRzJE5leHRTdGF0ZSkKaGVhZChkcykKYGBgCkJhc2VkIG9uIHRoZSBlbnZpcm9ubWVudCBhbmQgcmFuZG9taXplZCBzdGF0ZXMgYW5kIGFjdGlvbnMsIHdlIGNyZWF0ZWQgMTAwMCBvYnNlcnZhdGlvbnMgZGVub3RpbmcgdGhlICQoc190LGFfdCxzX3t0KzF9LHJfe3QrMX0pJCB0dXBsZS4gVG8gdHJhaW4gdGhlIGFnZW50IHVzaW5nIHRoZSBwYWNrYWdlLCBhbGwgd2UgbmVlZCBpcyBzdWNoIGRhdGEsIGFzIHdlIHNoYWxsIHNlZSBzaG9ydGx5LiBOb25ldGhlbGVzcywgd2UgY2FuIGVhc2lseSBnZW5lcmF0ZSBzdWNoIGRhdGEgdXNpbmcgdGhlIHBhY2thZ2UgYXMgZm9sbG93cwpgYGB7cn0Kc2V0LnNlZWQoMTIzNCkKZGF0YSA8LSBzYW1wbGVFeHBlcmllbmNlKE4gPSBOLGVudiA9IGVudiwgc3RhdGVzLCBhY3Rpb25zKQpoZWFkKGRhdGEpCmBgYApUbyBjb21wYXJlIHRoZSB0d28gd2UgY2FuIGxvb2sgaW50byB0aGUgdHJhbnNpdGlvbiBwcm9iYWJpbGl0aWVzIGJhc2VkIG9uIHRoZSBmcmVxdWVuY3kgb2YgdGhlICQoc190LHNfe3QrMX0pJCBwYWlyczoKYGBge3J9CnRhYmxlKGRzJFN0YXRlLGRzJE5leHRTdGF0ZSkvTgpgYGAKCmBgYHtyfQp0YWJsZShkYXRhJFN0YXRlLGRhdGEkTmV4dFN0YXRlKS9OCmBgYApXZSBvYnNlcnZlIHRoYXQgaW4gYm90aCBjYXNlcywgd2UgZ2V0IGEgc2ltaWxhciB0cmFuc2l0aW9uIG1hdHJpeC4gCgpHaXZlbiBlaXRoZXIgZGF0YSwgd2UgY2FuIHRyYWluIHRoZSBhZ2VudCB1c2luZyB0aGUgYFJlaW5mb3JjZW1lbnRMZWFybmluZycgZnVuY3Rpb24uIFRoZSBmdW5jdGlvbiB0YWtlcywgb2J2aW91c2x5LCB0aGUgZGF0YSBhcyB0aGUgZmlyc3QgaW5wdXQuIEFkZGl0aW9uYWxseSwgaXQgcmVxdWlyZXMgc3RhdGVzIHRoZSBuYW1lcyBvZiB0aGUgc3RhdGUsIG5leHQgc3RhdGUsIGFjdGlvbiwgYW5kIHJld2FyZCBjb2x1bW5zIGluIHRoZSBkYXRhLiBJbiB0ZXJtcyBvZiB0dW5pbmcsIHRoZSBjb21tYW5kIHRha2VzIHRoZSBjb250cm9sIHBhcmFtZXRlcnMgYXMgdGhlIGxhc3QgaW5wdXQuIFRoZXNlIHBhcmFtZXRlcnMgYXJlIHN1bW1hcml6ZWQgYXMgZm9sbG93czoKCjEuICoqTGVhcm5pbmcgUmF0ZSoqOiAkXGFscGhhIFxpbiAoMCwxKSQgcmVsYXRlcyB0byAkUSQtbGVhcm5pbmcgYW5kIGNhcHR1cmVzIHRoZSBsZWFybmluZyByYXRlLiBTaW1pbGFyIHRvIGl0ZXJhdGl2ZSBhbGdvcml0aG1zLCB0aGlzIHBhcmFtZXRlciBkZXRlcm1pbmVzIGhvdyBmYXN0IHRoZSBhbGdvcml0aG0gYWRhcHRzLiBJZiBpdCBpcyB0b28gc21hbGwsIHRoZSBsZWFybmluZyBzcGVlZCBpcyBsb3csIHdoZXJlYXMgYSBsYXJnZXIgdmFsdWUgZGVub3RlcyBhIGZhc3RlciBsZWFybmluZyByYXRlLiAKCjIuICoqRGlzY291bnQgRmFjdG9yKio6ICRcZ2FtbWEgXGluICgwLDEpJCBkZW5vdGVzIHRoZSBkaXNjb3VudCBmYWN0b3IuIFdlIHByZWZlciBjb25zdW1pbmcgZ29vZHMgaW1tZWRpYXRlbHkuIFNvbWV0aGluZyB0byBiZSBjb25zdW1lZCBpbiBhIGxhdGVyIHBlcmlvZCBpcyBub3QgYXMgZW5qb3lhYmxlIHVubGVzcyBvbmUgZXhwZWN0cyB0byBoYXZlIGEgZ3JlYXRlciByZXdhcmQgdG8gY29tcGVuc2F0ZSBmb3IgdGhlIHdhaXRpbmcgcGVyaW9kLiBIZW5jZSwgdGhlIHNtYWxsZXIgdGhlIHZhbHVlIG9mICRcZ2FtbWEkIGlzLCB0aGUgbGVzcyBwYXRpZW50IHRoZSBhZ2VudCBpcywgc3VjaCB0aGF0IGl0IGF0dHJpYnV0ZXMgZ3JlYXRlciB3ZWlnaHRzIHRvIGN1cnJlbnQgcmV3YXJkcy4KCjMuICoqRXhwbG9yYXRpb24gUmF0ZSoqOiAkXGVwc2lsb24gXGluICgwLDEpJCBpcyB0aGUgZnJhY3Rpb24gb2YgdHJhaW5pbmcgZXBpc29kZXMgaW4gd2hpY2ggdGhlIGFnZW50IGlnbm9yZXMgcGFzdCBsZWFybmluZyBleHBlcmllbmNlcyBhbmQgdGFrZXMgYSByYW5kb20gYWN0aW9uLiBUaGlzIGlucHV0IGNhcHR1cmVzIHRoZSBpZGVhIG9mIGV4cGxvcmF0aW9uIHZlcnN1cyBleHBsb2l0YXRpb24uIEFzIHNvb24gYXMgdGhlIGFnZW50IHN0YXJ0cyBmaWd1cmluZyB0aGlzIG91dCwgaXQgbWlnaHQgZ2V0IHRvbyBjb21mb3J0YWJsZSByZXBlYXRpbmcgdGhlIHNhbWUgYWN0aW9ucy4gSG93ZXZlciwgdGhlIGlkZWEgYmVoaW5kIHRoaXMgaXMgdG8gZW5jb3VyYWdlIHRoZSBhZ2VudCB0byBwZXJoYXBzIHRoZXJlIG1pZ2h0IGJlIHNvbWV0aGluZyBlbHNlIG91dCB0aGVyZSB3b3J0aCB0cnlpbmcuIEhlbmNlLCBhIGxhcmdlciAkXGVwc2lsb24kIHZhbHVlIGRlbm90ZXMgYSBncmVhdGVyIGV4cGxvcmF0aW9uIHJhdGUuCgpGb3Igbm93LCB3ZSBzZXQgdGhlIGZvbGxvd2luZyBjb25maWd1cmF0aW9uczoKYGBge3J9CmNvbnRyb2wgPC0gbGlzdChhbHBoYSA9IDAuMSwgZ2FtbWEgPSAwLjk1LCBlcHNpbG9uID0gMC4xKQpgYGAKCkdpdmVuIHRoZSBhYm92ZSwgYWxsIHdlIG5lZWQgdG8gZG8gaXMgdG8gcnVuIHRoZSBmb2xsb3dpbmc6CmBgYHtyfQptb2RlbCA8LSBSZWluZm9yY2VtZW50TGVhcm5pbmcoZGF0YSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHMgPSAiU3RhdGUiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYSA9ICJBY3Rpb24iLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgciA9ICJSZXdhcmQiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc19uZXcgPSAiTmV4dFN0YXRlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRyb2wgPSBjb250cm9sKQptb2RlbApgYGAKQSBjb3VwbGUgb2YgY29tbWVudHMgb2Ygb3JkZXIuIFdlIG9ic2VydmUgdGhhdCB0aGUgYWxnb3JpdGhtIHJldHVybnMgdGhlICRRJCBmdW5jdGlvbi4gU3VjaCBhIGZ1bmN0aW9uIGNhcHR1cmVzIHRoZSBvcHRpbWFsIHBvbGljeS4gSW4gdGhpcyByZWdhcmQsIGl0IHRlbGxzIHVzIGhvdyBtdWNoIHJld2FyZCB0aGVyZSBpcyBiIHRha2luZyBlaXRoZXIgb25lIG9mIHRoZSBmb3VyIGFjdGlvbnMgYXQgZWFjaCBzdGF0ZS4gRm9yIGluc3RhbmNlLCB3ZSBvYnNlcnZlIHRoYXQgdGhlIGxhcmdlciB2YWx1ZSBhdCBzdGF0ZSAkQSQgIChgczFgKSBpcyB3aGVuIHRoZSBhY3Rpb24gImRvd24iIGlzIHRha2VuLiBUaGUgc2FtZSBhcHBsaWVzIHRvIHRoZSBvdGhlciBzdGF0ZXMuIEhvd2V2ZXIsIGF0IGNlbGwgJEQkIChzdGF0ZSBgczRgKSwgd2Ugb2JzZXJ2ZSB0aGF0IGl0IGRvZXMgbm90IG1hdHRlciBhdCB0aGF0IHBvaW50IHNpbmNlIHRoZSBtYWluIHRyb3BoeSBoYXMgYmVlbiByZWNlaXZlZCwgYW5kIHRha2luZyBmdXJ0aGVyIGFjdGlvbiB3b3VsZCBub3QgcmVzdWx0IGluIGEgZnVydGhlciByZXdhcmQuIEluZGVlZCwgd2UgY2FuIHNlZSB0aGlzIGZyb20gdGhlICJQb2xpY3kiIG91dHB1dCwgd2hpY2ggcHJvdmlkZXMgZ3VpZGFuY2UgaW4gdGVybXMgb2Ygd2hhdCBhY3Rpb24gdG8gYmUgdGFrZW4gYmFzZWQgb24gZWFjaCBzdGF0ZSwgd2hpY2ggaXMgY29uc2lzdGVudCB3aXRoIHRoZSBzaG9ydGVzdCBwYXRoLgoKQXMgYSBjb25maXJtYXRpb24sIHdlIHJlcGVhdCB0aGUgYWJvdmUgYnV0IHVzZSBvdXIgc2ltdWxhdGVkIGRhdGEgdG8gc2VlIGNvbmZpcm0gd2hldGhlciB3ZSBnZXQgdGhlIHNhbWUgcmVzdWx0OgpgYGB7cn0KbW9kZWwyIDwtIFJlaW5mb3JjZW1lbnRMZWFybmluZyhkcywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzID0gIlN0YXRlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhID0gIkFjdGlvbiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgciA9ICJSZXdhcmQiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNfbmV3ID0gIk5leHRTdGF0ZSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2wpCm1vZGVsMgpgYGAKSW4gdGhlIGZvbGxvd2luZywgd2Ugd2lsbCB3b3JrIHdpdGggdGhlIGBkYXRhYCBvYmplY3QgZm9yIGJyZXZpdHksIGJ1dCB0aGUgcmVzdWx0cyBmb2xsb3cgc3VpdCByZWdhcmRsZXNzLiBCZWZvcmUgd2UgbW92ZSBvbiwgbm90ZSB0aGF0IGVpdGhlciBtb2RlbCByZXR1cm5zIGEgcmV3YXJkLiBUaGUgcmV3YXJkIGhlcmUgZGVub3RlcyB0aGUgc3VtbWF0aW9uIG9mIHRoZSB0b3RhbCByZXdhcmRzIGluIHRoZSBkYXRhLCBpLmUuLApgYGB7cn0Kc3VtKGRhdGEkUmV3YXJkKSA9PSBtb2RlbCRSZXdhcmQKYGBgCmFuZCAKYGBge3J9CnN1bShkcyRSZXdhcmQpID09IG1vZGVsMiRSZXdhcmQKYGBgCgojIyBVcGRhdGluZyBQb2xpY3kKU2luY2Ugd2Uga25vdyB0aGUgc29sdXRpb24sIHdlIGNhbiBjb25jbHVkZSB0aGF0IHRoZSBmaW5hbCByZXN1bHQgaXMgdGhlIG9wdGltYWwgcG9saWN5LiBIb3dldmVyLCB3aGF0IGlmIHRoZSBlbnZpcm9ubWVudCB3ZXJlIG1vcmUgY29tcGxleCB0aGFuIHRoZSBvbmUgY29uc2lkZXJlZCBpbiB0aGlzIGV4YW1wbGU/IEFsc28sIHN1cHBvc2UgdGhhdCB3ZSBnZXQgbmV3IGRhdGEgYnkgdGhlIHRpbWUgd2UgYXJlIGRvbmUgdHJhaW5pbmcgdGhlIG1vZGVsLiBDYW4gd2UgaW1wcm92ZSB0aGUgcG9saWN5IGZ1cnRoZXI/IFdpdGhvdXQgZGVsdmluZyBpbnRvIHRlY2huaWNhbCBkZXRhaWxzLCB3ZSBjb3VsZCBhcmd1ZSB0aGF0IHRoZSBtb2RlbCBsZWFybnMgYmV0dGVyIGJ5IHByb3ZpZGluZyBpdCBncmVhdGVyIGRhdGEgYmFzZWQgYWZ0ZXIgaW50ZXJhY3Rpbmcgd2l0aCB0aGUgZW52aXJvbm1lbnQgd2l0aCBndWlkYW5jZS4gSW4gdGhpcyBjYXNlLCB3ZSBhcmUgaW50ZXJlc3RlZCBpbiB1cGRhdGluZyBleGlzdGluZyBwb2xpY3kgYXMgZGF0YSBiZWNvbWUgYXZhaWxhYmxlLgoKU3BlY2lmaWNhbGx5LCBpbiB0aGUgYWJvdmUsIHdlIGdlbmVyYXRlZCBkYXRhIHVzaW5nIHJhbmRvbSBpbnRlcmFjdGlvbnMgd2l0aG91dCBndWlkYW5jZS4gTm93IHRoYXQgd2UgZmlndXJlZCBvdXQgc29tZXRoaW5nLCB3ZSBjYW4gcGVyaGFwcyBnZW5lcmF0ZSBkYXRhIGluIHNvbWUgZGlyZWN0aW9ucy4gRm9yIGluc3RhbmNlLCB3ZSBrbm93IHRvIHNvbWUgZXh0ZW50IHdoYXQgdGhlIGFnZW50IHNob3VsZCBkYXkgYXQgc3RhdGUgYHMxYCBnaXZlbiB0aGUgcG9saWN5IGZyb20gYG1vZGVsLmAgV2UgY2FuIHVzZSB0aGUgb3JpZ2luYWwgbW9kZWwgYXMgYSByZWZlcmVuY2UgcG9pbnQgYW5kIGdlbmVyYXRlIGFkZGl0aW9uYWwgZGF0YSBhcyBmb2xsb3dzCmBgYHtyfQpkYXRhX25ldyA8LSBzYW1wbGVFeHBlcmllbmNlKE4gPSBOLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBlbnYgPSBlbnYsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN0YXRlcyA9IHN0YXRlcywgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0aW9ucyA9IGFjdGlvbnMsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1vZGVsID0gbW9kZWwsICMgaW1wb3J0YW50CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0aW9uU2VsZWN0aW9uID0gImVwc2lsb24tZ3JlZWR5IiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb250cm9sID0gY29udHJvbCkKYGBgCkRpZmZlcmVudCBmcm9tIGJlZm9yZSwgdGhlIGBzYW1wbGVFeHBlcmllbmNlYCBub3cgdXNlcyB0d28gYWRkaXRpb25hbCBhcmd1bWVudHMuIFRoZSBmaXJzdCBpcyBzcGVjaWZ5aW5nIGFuIGV4aXN0aW5nIG1vZGVsIHdlIGNvdWxkIHJlbHkgb24gdG8gZ2VuZXJhdGUgdGhlIGRhdGEuIFRoZSBzZWNvbmQgaXMgdGhlIGFjdGlvbiBtZXRob2QuIEluIHRoZSBmaXJzdCBvbmUsIHRoZSBhY3Rpb24gbWV0aG9kIHdhcyBjb21wbGV0ZWx5IHJhbmRvbSwgd2hlcmVhcyBub3cgaXQgJFxlcHNpbG9uJC1ncmVlZHksIGkuZS4sIHRoZSBhZ2VudCB3aWxsIGZvbGxvdyB0aGUgcG9saWN5ICQxLVxlcHNpbG9uJCBvZiB0aGUgdGltZSwgYW5kICRcZXBzaWxvbiQgb2YgdGhlIGNhc2VzIGl0IHdpbGwgY2hvb3NlIHJhbmRvbSBhY3Rpb25zIGFzIHdlIGRpZCBvcmlnaW5hbGx5LiBXZSBjYW4gc2VlIHRoYXQgdGhlIHNhbXBsZSBkYXRhLCBpbiB0aGlzIGNhc2UsIHJlc3VsdHMgaW4gYSBtdWNoIGhpZ2hlciByZXdhcmQgc2luY2UgdGhlIGFnZW50IGNhbiByZWx5IG9uIHNvbWUgcG9saWN5IHRvIGRldGVybWluZSB0aGUgYmVzdCBhY3Rpb24KYGBge3J9CnN1bShkYXRhX25ldyRSZXdhcmQpCmBgYAoKVG8gbWFrZSB0aGluZ3MgbW9yZSBpbnRlcmVzdGluZywgbGV0IHVzIGNyZWF0ZSBhIGZ1bmN0aW9uIHdoZXJlIHdlIHVwZGF0ZSB0aGUgcG9saWN5ICRNJCB0aW1lcy4gVGhlIGZ1bmN0aW9uIHdpbGwgc3VtbWFyaXplIGFsbCB0aGUgYWJvdmUgc3RlcHMgaW4gYSBzaW5nbGUgZnVuY3Rpb24gYXMgZm9sbG93cy4KCmBgYHtyfQpNIDwtIDEwClJMX3VwZGF0ZV9mdW4gPC0gZnVuY3Rpb24oY29udHJvbF9pKSB7CiAgCiAgc2V0LnNlZWQoMSkKICBkYXRhIDwtIHNhbXBsZUV4cGVyaWVuY2UoTiA9IE4sZW52ID0gZW52LCBzdGF0ZXMsIGFjdGlvbnMpCiAgbW9kZWwgPC0gUmVpbmZvcmNlbWVudExlYXJuaW5nKGRhdGEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHMgPSAiU3RhdGUiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhID0gIkFjdGlvbiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHIgPSAiUmV3YXJkIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc19uZXcgPSAiTmV4dFN0YXRlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2xfaSkKICByZXdhcmRfc2VxIDwtIHN1bShtb2RlbCRSZXdhcmQpCiAgCiAgZm9yIChpdGVyIGluIDI6TSkgewogICAgCiAgICBzZXQuc2VlZChpdGVyKQogICAgZGF0YV9uZXcgPC0gc2FtcGxlRXhwZXJpZW5jZShOID0gTiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVudiA9IGVudiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHN0YXRlcyA9IHN0YXRlcywgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFjdGlvbnMgPSBhY3Rpb25zLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbW9kZWwgPSBtb2RlbCwgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFjdGlvblNlbGVjdGlvbiA9ICJlcHNpbG9uLWdyZWVkeSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRyb2wgPSBjb250cm9sX2kpCiAgICAjIHVwZGF0ZSBtb2RlbAogICAgbW9kZWwgPC0gUmVpbmZvcmNlbWVudExlYXJuaW5nKGRhdGFfbmV3LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHMgPSAiU3RhdGUiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGEgPSAiQWN0aW9uIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByID0gIlJld2FyZCIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc19uZXcgPSAiTmV4dFN0YXRlIiwgICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRyb2wgPSBjb250cm9sKQogICAgCiAgICByZXdhcmRfc2VxIDwtIGMocmV3YXJkX3NlcSxzdW0obW9kZWwkUmV3YXJkKSkKICAgIAogIH0KICAKICByZXR1cm4ocmV3YXJkX3NlcSkKfQoKYGBgCgpHaXZlbiB0aGUgYWJvdmUgZnVuY3Rpb24sIHdlIGNhbiBhbmFseXplIGhvdyB0aGUgcG9saWN5IHVwZGF0ZXMgZGVwZW5kIG9uIHRoZSBpbnB1dHMuIEluIHRoZSBmb2xsb3dpbmcsIEkgY29uc2lkZXIgZGlmZmVyZW50IHZhbHVlcyBvZiAkXGVwc2lsb24kLCB3aGljaCBkZW5vdGVzIHRoZSBwcm9wb3J0aW9uIG9mIHRpbWUgdGhlIGFsZ29yaXRobSB0YWtlcyBhIHJhbmRvbSBjaGFuY2UuIE5hdHVyYWxseSwgd2UgZXhwZWN0IG1vcmUgbm9pc2UgdG8gYmUgYXNzb2NpYXRlZCB3aXRoIGhpZ2hlciB2YWx1ZXMuIEJ5IG5vaXNlLCBJIG1lYW4gdGhhdCBpZiB0aGUgYWxnb3JpdGhtIGZpZ3VyZXMgb3V0IHRoZSByaWdodCBvcHRpbWFsIHBvbGljeSwgdGhlbiBpdCBzaG91bGQgcmVhY2ggdGhlIG1heGltdW0gcG9zc2libGUgcmV3YXJkIGVhcmxpZXIgYW5kIGV4aGliaXQgbW9yZSBzdGFiaWxpdHkgcmVnYXJkbGVzcyBvZiB0aGUgaXRlcmF0aW9ucy4gCgoKYGBge3J9CmxpYnJhcnkocGFyYWxsZWwpCmNvbnRyb2wxIDwtIGxpc3QoYWxwaGEgPSAwLjEsIGdhbW1hID0gMC45NSwgZXBzaWxvbiA9IDAuNSkKY29udHJvbDIgPC0gbGlzdChhbHBoYSA9IDAuMSwgZ2FtbWEgPSAwLjk1LCBlcHNpbG9uID0gMC4yNSkKY29udHJvbDMgPC0gbGlzdChhbHBoYSA9IDAuMSwgZ2FtbWEgPSAwLjk1LCBlcHNpbG9uID0gMC4xKQpjb250cm9sNCA8LSBsaXN0KGFscGhhID0gMC4xLCBnYW1tYSA9IDAuOTUsIGVwc2lsb24gPSAwLjAxKQoKY29udHJvbF9saXN0IDwtIGxpc3QoY29udHJvbDEsY29udHJvbDIsY29udHJvbDMsY29udHJvbDQpClJMX2xpc3QgPC0gbWNsYXBwbHkoY29udHJvbF9saXN0LFJMX3VwZGF0ZV9mdW4sbWMuY29yZXMgPSA0KQoKYGBgCgpMZXQgdXMgcGxvdCB0aGUgcmV3YXJkcyBmcm9tIGVhY2ggYWxnb3JpdGhtCmBgYHtyLG1lc3NhZ2U9RkFMU0Usd2FybmluZz1GQUxTRX0KbGlicmFyeShnZ3Bsb3QyKQpsaWJyYXJ5KHBsb3RseSkKcmV3YXJkc19pdGVyIDwtIGxhcHBseSgxOmxlbmd0aChjb250cm9sX2xpc3QpLAogICAgICAgICAgICAgICAgICAgICAgIGZ1bmN0aW9uKGkpIGRhdGEuZnJhbWUoUmV3YXJkID0gUkxfbGlzdFtbaV1dLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEl0ZXJhdGlvbiA9IDE6TSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBlcHNpbG9uID0gY29udHJvbF9saXN0W1tpXV0kZXBzaWxvbiApKQpyZXdhcmRzX2l0ZXIgPC0gUmVkdWNlKHJiaW5kLHJld2FyZHNfaXRlcikKcmV3YXJkc19pdGVyJGVwc2lsb24gPC0gYXMuZmFjdG9yKHJld2FyZHNfaXRlciRlcHNpbG9uKQpwIDwtIGdncGxvdChkYXRhID0gcmV3YXJkc19pdGVyLGFlcyh4ID0gSXRlcmF0aW9uLHkgPSBSZXdhcmQsIHR5cGUgPSBlcHNpbG9uLGNvbG91ciA9IGVwc2lsb24pKSArCiAgZ2VvbV9saW5lKCkgKyBnZW9tX3BvaW50KCkKZ2dwbG90bHkocCkKYGBgCldlIGNhbiBzZWUgdGhhdCB0aGUgc3BlY2lmaWNhdGlvbiB3aXRoIHRoZSBsb3dlc3QgJFxlcHNpbG9uJCB2YWx1ZSByZXN1bHRzIGluIGhpZ2hlciByZXdhcmRzIGR1cmluZyB0aGUgbGFzdCAkTSAtIDEkIGl0ZXJhdGlvbnMuIEF0IHRoZSBzYW1lIHRpbWUsIHdlIG5vdGUgdGhhdCB0aGUgYWxnb3JpdGhtIHdpbGwgYWx3YXlzIGZvbGxvdyBhIHJhbmRvbSBwb2xpY3kgcmVnYXJkbGVzcyBvZiB0aGUgbnVtYmVyIG9mIGl0ZXJhdGlvbnMuIE9uZSBwb3RlbnRpYWwgYWRqdXN0bWVudCBpcyB0byByZWR1Y2UgdGhlIHZhbHVlIG9mIHRoZSAkXGVwc2lsb24kIHRoZSBtb3JlIGl0ZXJhdGlvbnMgd2UgcGVyZm9ybS4gVGhlIGZvbGxvd2luZyBmdW5jdGlvbiBkb2VzIHNvIGJ5IHNldHRpbmcgJFxlcHNpbG9uL20kLCB3aGVyZSAkbSA9IDEsLi4uLDUwJC4gSWYgd2Ugc3RhcnQgd2l0aCAkXGVwc2lsb24gPSAwLjUkLCBieSB0aGUgNTB0aCBpdGVyYXRpb24gdGhlIGFsZ29yaXRobSBzZXRzICRcZXBzaWxvbiA9IDAuMDEkLgoKYGBge3J9ClJMX3VwZGF0ZV9mdW4gPC0gZnVuY3Rpb24oY29udHJvbF9pKSB7CiAgCiAgc2V0LnNlZWQoMSkKICBkYXRhIDwtIHNhbXBsZUV4cGVyaWVuY2UoTiA9IE4sZW52ID0gZW52LCBzdGF0ZXMsIGFjdGlvbnMpCiAgbW9kZWwgPC0gUmVpbmZvcmNlbWVudExlYXJuaW5nKGRhdGEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHMgPSAiU3RhdGUiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhID0gIkFjdGlvbiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHIgPSAiUmV3YXJkIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc19uZXcgPSAiTmV4dFN0YXRlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2xfaSkKICByZXdhcmRfc2VxIDwtIHN1bShtb2RlbCRSZXdhcmQpCiAgCiAgZm9yIChpdGVyIGluIDI6TSkgewogICAgCiAgICBjb250cm9sX2kkZXBzaWxvbiA8LSBjb250cm9sX2kkZXBzaWxvbi9pdGVyCiAgICAKICAgIHNldC5zZWVkKGl0ZXIpCiAgICBkYXRhX25ldyA8LSBzYW1wbGVFeHBlcmllbmNlKE4gPSBOLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZW52ID0gZW52LCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RhdGVzID0gc3RhdGVzLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0aW9ucyA9IGFjdGlvbnMsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBtb2RlbCA9IG1vZGVsLCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYWN0aW9uU2VsZWN0aW9uID0gImVwc2lsb24tZ3JlZWR5IiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2xfaSkKICAgICMgdXBkYXRlIG1vZGVsCiAgICBtb2RlbCA8LSBSZWluZm9yY2VtZW50TGVhcm5pbmcoZGF0YV9uZXcsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcyA9ICJTdGF0ZSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYSA9ICJBY3Rpb24iLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHIgPSAiUmV3YXJkIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzX25ldyA9ICJOZXh0U3RhdGUiLCAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2wpCiAgICAKICAgIHJld2FyZF9zZXEgPC0gYyhyZXdhcmRfc2VxLHN1bShtb2RlbCRSZXdhcmQpKQogICAgCiAgfQogIAogIHJldHVybihyZXdhcmRfc2VxKQp9CgpNIDwtIDUwCnJld19zZXEgPC0gUkxfdXBkYXRlX2Z1bihjb250cm9sMSkKCmBgYApXZSBjYW4gdmlzdWFsaXplIHRoZSB0b3RhbCByZXdhcmRzIGFzIGEgZnVuY3Rpb24gb2YgaXRlcmF0aW9ucyBhcyBmb2xsb3dzOgpgYGB7cn0KZHNfcGxvdCA8LSBkYXRhLmZyYW1lKFJld2FyZCA9IHJld19zZXEsIEl0ZXJhdGlvbiA9IDE6TSkKcCA8LSBnZ3Bsb3QoZGF0YSA9IGRzX3Bsb3QsYWVzKHggPSBJdGVyYXRpb24seSA9IFJld2FyZCkpICsKICBnZW9tX2xpbmUoKSArIGdlb21fcG9pbnQoKQpnZ3Bsb3RseShwKQpgYGAKV2Ugb2JzZXJ2ZSB0aGF0IHRoZSBhbGdvcml0aG0gZGVtb25zdHJhdGVzIGxvd2VyIHZvbGF0aWxpdHkgYXMgd2UgYXBwcm9hY2ggdGhlIGxhc3QgaXRlcmF0aW9uLgoKIyMgUHJlZGljdGlvbnMKU2ltaWxhciB0byBvdGhlciBtb2RlbHMgaW4gUiwgc3VjaCBhcyBsaW5lYXIgcmVncmVzc2lvbnMgb3IgbWFjaGluZSBsZWFybmluZyBhbGdvcml0aG1zIHZpYSBgY2FyZXQsYCB0aGUgUkwgbW9kZWwgY2FuIGJlIHV0aWxpemVkIGluIHRoZSBnZW5lcmljIGBwcmVkaWN0YCBmdW5jdGlvbi4gRm9yIGluc3RhbmNlLCBnaXZlbiBvdXIgaW5pdGlhbCBkYXRhLCB3ZSBjYW4gc2VlIGhvdyB0aGUgYWN0aW9ucyBnZXQgdXBkYXRlZCBiYXNlZCBvbiBsZWFybmluZy4gVGhlIHRhYmxlIGJlbG93IGRlbW9uc3RyYXRlcyB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSByYW5kb20gYWN0aW9ucyB0YWtlbiB2ZXJzdXMgdGhvc2UgdGhhdCB0aGUgcG9saWN5IGd1aWRlcy4gR3JlYXRlciB2YWx1ZXMgaW4gdGhlIG9mZi1kaWFnb25hbCBlbGVtZW50cyBpbmRpY2F0ZSBncmVhdGVyIGRpc2NyZXBhbmN5LiBJZiB0aGUgbW9kZWwgZGlkIG5vdCBsZWFybi91cGRhdGUsIHdlIGV4cGVjdCB0byBnZXQgdGhlIHNhbWUgcG9saWN5IGFzIHRoZSByYW5kb20gb25lLgpgYGB7cn0KYWN0aW9uX3ByZWRpY3QgPC0gcHJlZGljdChtb2RlbCxkYXRhJFN0YXRlKQp0YWJsZShkYXRhJEFjdGlvbixhY3Rpb25fcHJlZGljdCkKYGBgClRoaXMgZnVuY3Rpb24gaXMgaGVscGZ1bCBpbiBldmFsdWF0aW5nIHRoZSBtb2RlbCBhZnRlciBlYWNoIHRyYWluaW5nIGVwaXNvZGUuIEFkZGl0aW9uYWxseSwgaXQgYWxsb3dzIGRldGVybWluaW5nIHRoZSByZXdhcmQgcmVnYXJkbGVzcyBvZiB0aGUgY29udGV4dCB1c2VkLiAKCiMgVGFjdGl0YWwgQXNzZXQgQWxsb2NhdGlvbgoKIyMgRGF0YQpJIHdpbGwgd29yayB3aXRoIHR3byBtYWluIHBhY2thZ2VzIHRvIG1hbmlwdWxhdGUgdGltZSBzZXJpZXMgYW5kIGRhdGVzLiBJbiB0ZXJtcyBvZiBhc3NldHMsIEkgd2lsbCBjb25zaWRlciB0aGUgcHJvYmxlbSBvZiBhIHRhY3RpY2FsIGFzc2V0IGFsbG9jYXRpb24gd2hlcmUgdGhlIGFnZW50IHJvdGF0ZXMgYmV0d2VlbiBoaWdoIGFuZCBsb3cgcmlzayBhc3NldHMuIEZvciB0aGUgaGlnaCByaXNrIGFzc2V0cywgSSBjb25zaWRlciB0aGUgU1BZIEVURiB0byByZXByZXNlbnQgdGhlIHN0b2NrIG1hcmtldC4gRm9yIHRoZSBsb3cgcmlzaywgSSB3aWxsIGNvbnNpZGVyIGNhc2ggd2l0aCB6ZXJvIHJldHVybiBmb3Igc2ltcGxpY2l0eS4gVGhpcyBjYW4gYmUgcmVwbGFjZWQgYnkgYSBUcmVhc3VyeSBib25kIG9yIGEgbW9yZSBkZWZlbnNpdmUgYXNzZXQuIEluIHRoaXMgZXhhbXBsZSwgSSBhc3N1bWUgdGhhdCB0aGUgcmV0dXJuIG9uIGNhc2ggaXMgemVybyByZWdhcmRsZXNzIG9mIGludGVyZXN0L2luZmxhdGlvbiByYXRlcy4KYGBge3Isd2FybmluZz1GQUxTRSxtZXNzYWdlPUZBTFNFfQpsaWJyYXJ5KHF1YW50bW9kKQpsaWJyYXJ5KGx1YnJpZGF0ZSkKbGlicmFyeShQZXJmb3JtYW5jZUFuYWx5dGljcykKCnRpY3MgPC0gIlNQWSIKUF9saXN0IDwtIGxhcHBseSh0aWNzLCBmdW5jdGlvbih4KSBnZXQoIGdldFN5bWJvbHMoeCxmcm9tID0gIjE5OTAtMDEtMDEiKSApICApClBfbGlzdCA8LSBsYXBwbHkoUF9saXN0LGZ1bmN0aW9uKHgpIHhbLDZdKQpQIDwtIFJlZHVjZShtZXJnZSxQX2xpc3QpClAgPC0gYXBwbHkubW9udGhseShQLGxhc3QpClIgPC0gbmEub21pdChQL2xhZyhQKSkgLSAxCmRzX3Bsb3QgPC0gUgpSX3BvcnQgPC0gMC42KlIgKyAwLjQqMApSX3BvcnQgPC0gbWVyZ2UoUixSX3BvcnQpCmNoYXJ0LkN1bVJldHVybnMoUl9wb3J0KQpgYGAKVGhlIGJsYWNrIGxpbmUgYWJvdmUgZGVub3RlcyB0aGUgcmV0dXJuIG9uIGEgMTAwJSBwb3NpdGlvbiBpbiB0aGUgU1BZLCB3aGVyZWFzIHRoZSByZWQgbGluZSBkZW5vdGVzIHRoZSA2MC00MCBwb3J0Zm9saW8gdGhhdCBhbGxvY2F0ZXMgNjAlIHRvIHRoZSBTUFkgYW5kIDQwJSB0byBjYXNoLiBPdmVyYWxsLCB3ZSBvYnNlcnZlIHRoYXQgdGhlIFNQWSBvdXRwZXJmb3JtcyB0aGUgNjAtNDAgcG9ydGZvbGlvIGluIHRlcm1zIG9mIHRvdGFsIHJldHVybiBzaW5jZSBpdCBoYXMgZ3JlYXRlciBsb2FkaW5nIG9uIHRoZSByaXNrIHByZW1pdW0gb2YgdGhlIHN0b2NrIG1hcmtldC4gQXQgdGhlIHNhbWUgdGltZSwgd2Ugb2JzZXJ2ZSB0aGF0IHRoZSA2MC00MCBwcm92aWRlcyBhIGdyZWF0ZXIgaGVkZ2UgZHVyaW5nIG1hcmtldCBzZWxsLW9mZnMgbWl0aWdhdGluZyB0aGUgZG93bnNpZGUgcmlzay4gVHJhZGl0aW9uYWxseSwgdGhlIDYwLTQwIGFsbG9jYXRlcyA0MFwlIHRvIFRyZWFzdXJ5IGJvbmRzIHdoaWNoIHNlcnZlIGFzIGEgc2FmZSBoYXZlbiBhc3NldCAoZmxpZ2h0LXRvLXF1YWxpdHkpIGR1cmluZyBpbmNyZWFzZWQgdW5jZXJ0YWludHkgaW4gdGhlIG1hcmtldC4gVGhlc2UgZHluYW1pY3MgaW1wbHkgYSBuZWdhdGl2ZSBjb3JyZWxhdGlvbiBiZXR3ZWVuIHRoZSB0d28gYXNzZXRzLCB3aGljaCByZXN1bHRzIGluIGVuaGFuY2VkIHJpc2stYWRqdXN0ZWQgcmV0dXJucy4gSG93ZXZlciwgaW4gb3VyIGV4YW1wbGUgd2l0aCBjYXNoLCB0aGUgY29ycmVsYXRpb24gaXMgemVyby4KCiMjIFJMIEFwcGxpY2F0aW9uClRoZSBpZGVhIGJlaGluZCBSTCBpcyB0byB0cmFpbiB0aGUgYWdlbnQgdG8gbGVhcm4gdGhlIGR5bmFtaWNzIG9mIHRoZSB0YWN0aWNhbCBhc3NldCBhbGxvY2F0aW9uIHByb2JsZW0uIFNwZWNpZmljYWxseSwgd2UgYXJlIGludGVyZXN0ZWQgaW4gYSBtb2RlbC1mcmVlIGVudmlyb25tZW50IHdoZXJlIHRoZSBhZ2VudCBvYnNlcnZlcyBjZXJ0YWluIGFjdGlvbnMgYW5kIHJld2FyZHMgdG8gZGV0ZXJtaW5lIHRoZSBvcHRpbWFsIHBvbGljeS4gVG8gZG8gc28sIHdlIHdpbGwgY29uc2lkZXIgZGVzY3JpcHRpdmUgYW5hbHlzaXMgZmlyc3QsIGkuZS4sIGluLXNhbXBsZS4gVGhlbiwgd2Ugd2lsbCBjb25zaWRlciBzb21lIGJhY2t0ZXN0aW5nIHRvIGV2YWx1YXRlIHRoZSBhcHBlYWwgb2YgUkwgb3V0LW9mLXNhbXBsZS4gCgpMZXQgdXMgc2V0IHVwIHRoZSBwbGF0Zm9ybSBzbyB3ZSBjYW4gcnVuIHRoZSBSTCBmdW5jdGlvbi4gUmVjYWxsIHRoYXQgdGhlIFJMIG1haW4gZnVuY3Rpb24gdGFrZXMgdGhlIGRhdGEgaW4gdGhlIGZvcm1hdCBvZiAgJChzX3QsYV90LHNfe3QrMX0scl97dCsxfSkkIHR1cGxlcy4gSGVuY2UsIHdlIG5lZWQgdG8gZGV0ZXJtaW5lIHRoZSBzdGF0ZSBhdCB0aW1lICR0JCwgY29ycmVzcG9uZGluZyB0byBtb250aCAkdCQgaW4gb3VyIGRhdGEuIE5vdGUgdGhhdCB0aGUgYXNzZXQgcmV0dXJuIGlzIGNvbnRpbnVvdXMsIHdoZXJlYXMgdGhlIHN0YXRlICRzX3QkIGlzIGRpc2NyZXRlLiBIZW5jZSwgd2UgbmVlZCB0byB1dGlsaXplIGEgc2lnbmFsIGZyb20gdGhlIHJldHVybnMgdG8gZGV0ZXJtaW5lIHRoZSBtYXJrZXQgc3RhdGUuIFRoaXMgY2FuIGJlIGRvbmUgaW4gZGlmZmVyZW50IHdheXMsIGUuZy4sIGVjb25vbWljIGluZGV4IG9yIG90aGVyIGZpbmFuY2lhbCBpbmRpY2F0b3JzIHN1Y2ggYXMgVklYLiBJbiB0aGUgZm9sbG93aW5nIGlsbHVzdHJhdGlvbiwgSSBjb25zaWRlciBhIHNpbXBsZSBjYXNlIHdoZXJlIHdlIGhhdmUgdGhyZWUgc3RhdGVzIGRldGVybWluZWQgYmFzZWQgb24gdGhlIHJldHVybiBsZXZlbCBvZiB0aGUgYXNzZXQsIGRlbm90aW5nIGxvdywgbWVkaXVtLCBhbmQgaGlnaCBsZXZlbHMuCgpCZWZvcmUgd2UgZ2V0IHN0YXJ0ZWQsIHdlIHNldCB1cCBhIG51bWJlciBvZiBtYWluIHBhcmFtZXRlcnMKYGBge3J9CmFscGggPC0gMC4xICMgbGVhcm5pbmcgc3BlZWQKciA8LSAwLjAyICMgcmlzayBmcmVlIHJhdGUKZ2FtIDwtIDEvKDErcileKDEvMTIpICMgbW9udGhseSBkaXNjb3VudCByYXRlCmVwcyA8LSAwLjEKdGF1IDwtIDAuMDEgIyBzZXRzIHRoZSB0aHJlc2hvbGQgd2hpY2ggZGV0ZXJtaW5lcyB0aGUgc3RhdGUKYGBgCldlIGRldGVybWluZSAkXGdhbW1hJCBieSBhc3N1bWluZyBhIHJpc2stZnJlZSBhbm51YWwgcmF0ZSBvZiAyJS4gSGVuY2UsIHRoZSBkaXNjb3VudCBmYWN0b3Igb24gYSBtb250aGx5IGJhc2lzIGlzCiQkClxnYW1tYSA9ICBcbGVmdChcZnJhY3sxfXsxK3J9IFxyaWdodCleezEvMTJ9CiQkClRoZSBwYXJhbWV0ZXIgJFx0YXUkIGRlbm90ZXMgdGhlIHRocmVzaG9sZCBvZiB0aGUgU1BZIHJldHVybiB0aGF0IGNhcHR1cmVzIHRoZSBzdGF0ZSBvZiB0aGUgbWFya2V0LiBJbiBvdXIgY2FzZSwgYSByZXR1cm4gYmVsb3cgJC1cdGF1JCAoYWJvdmUgJFx0YXUkKSBkZW5vdGVzIHN0YXRlICRzX3QgPSAtMSQgKCRzX3QgPSAxJCkuIE90aGVyd2lzZSwgdGhlIHN0YXRlIGlzICRzX3QgPSAwJC4gV2UgY2FuIGVhc2lseSBkZWZpbmUgdGhlIHN0YXRlcyBhcyBmb2xsb3dzCmBgYHtyfQpkcyA8LSBSCmRzIDwtIGRhdGEuZnJhbWUoRGF0ZSA9IGRhdGUoZHMpLCBkcykKZHMkU3RhdGUgPC0gKGRzJFNQWS5BZGp1c3RlZD4gdGF1KSoxICsgLShkcyRTUFkuQWRqdXN0ZWQgPCAtdGF1KSoxCmRzJFN0YXRlIDwtIGFzLmNoYXJhY3RlcihkcyRTdGF0ZSkKZHMkTmV4dFN0YXRlIDwtIGRhdGEudGFibGU6OnNoaWZ0KGRzJFN0YXRlLC0xKQpoZWFkKGRzKQpgYGAKTmV4dCwgd2UgbmVlZCB0byBkZXRlcm1pbmUgYWN0aW9uIGFuZCByZXdhcmRzLiBUaGUgYWN0aW9uIHNwYWNlIGlzIGFsc28gZGlzY3JldGUuIEZvciBzaW1wbGljaXR5LCB3ZSBjb25zaWRlciBhIGRpc2NyZXRlIGFjdGlvbiBzcGFjZSB3aGVyZSB0aGUgYWdlbnQgbG9uZ3MgYSBmcmFjdGlvbiBvZiB0aGUgcmlza3kgYXNzZXQgYXMgJGFfdCA9IDEvayQgZm9yICRrID0gMSwuLi4sMTAkLiBUaGlzIGltcG9zZXMgdGhhdCB0aGUgYWdlbnQgbG9uZ3MgYSBwb3J0aW9uIG9mIHRoZSBzdG9jayBtYXJrZXQgcmVnYXJkbGVzcyBvZiB0aGUgY3VycmVudCBzdGF0ZS4gU2FtZSBhcyBpbiB0aGUgZ3JpZCBleGFtcGxlLCB3ZSBjb25zaWRlciByYW5kb20gYWN0aW9ucyB3aGVyZSB0aGUgYWdlbnQgdGFrZXMgcmFuZG9tIHBvcnRmb2xpbyBjaG9pY2VzIGFzCmBgYHtyfQpzZXQuc2VlZCgxKQpkcyRBY3Rpb24gPC0gc2FtcGxlKCgxOjEwKS8xMCxucm93KGRzKSxyZXBsYWNlID0gVFJVRSkKaGVhZChkcykKYGBgCgpXZSBoYXZlIGRldGVybWluZWQgdGhlICQoc190LGFfdCxzX3t0KzF9KSQgdHVwbGUgc28gZmFyLiBXaGF0IGxlZnQgdG8gZGV0ZXJtaW5lIGlzIHRoZSByZXdhcmQgZm9yIHRha2luZyBhY3Rpb24gJGFfdCQgd2hpbGUgdHJhbnNpdGlvbmluZyBmcm9tIHN0YXRlICRzX3QkIHRvIHN0YXRlICRzX3t0KzF9JC4gVG8gZG8gc28sIHdlIG5lZWQgYSByZXdhcmQgZnVuY3Rpb24gdGhhdCB0YWtlcyBpbnRvIGFjY291bnQgdGhlIGRpcy11dGlsaXR5IG9mIGxvc3Nlcy4gQSBuYXR1cmFsIGNhbmRpZGF0ZSBpcyB0byBtYXAgcmV0dXJucyB2aWEgYSBjb25zdGFudCBhYnNvbHV0ZSByaXNrIGF2ZXJzaW9uIChDQVJBKSB1dGlsaXR5IGZ1bmN0aW9uIHdpdGggYSBnaXZlbiByaXNrIGF2ZXJzaW9uIHBhcmFtZXRlciBkZW5vdGVkIGJ5IGBSQWAgdG8gY29udHJvbCBmb3IgdGhlIGFnZW50IHJpc2sgYXZlcnNpb246CmBgYHtyfQpSQSA8LSA1ICMgc2V0cyB0aGUgcmlzayBhdmVyc2lvbiBsZXZlbApVIDwtIGZ1bmN0aW9uKHgsUkEpIDEtZXhwKC1SQSp4KQp4IDwtIHNlcSgtMC4xLDEsbGVuZ3RoID0gMTAwKQpVXzMgPC0gZnVuY3Rpb24oeCkgVSh4LDMpClVfMTAgPC0gZnVuY3Rpb24oeCkgVSh4LDEwKQp5MSA8LSBzYXBwbHkoeCxVXzMpCnkyIDwtIHNhcHBseSh4LFVfMTApCnBsb3QoeTEgfiB4LHR5cGUgPSAibCIseWxpbSA9IHJhbmdlKGMoeTEseTIpKSwgeWxhYiA9ICJVdGlsaXR5IiwgeGxhYiA9ICJSZXR1cm4iKQpsaW5lcyh5MiB+IHgsY29sID0gMikKYWJsaW5lKHYgPSAwLGx0eSA9IDIpCmdyaWQoMTApCmBgYApUaGUgYWJvdmUgcGxvdCBkZW1vbnN0cmF0ZXMgdGhlIHV0aWxpdHkgb2YgdHdvIGFnZW50cyB3aGVyZSB0aGUgcmVkIGxpbmUgaXMgdGhlIG9uZSB3aXRoIGhpZ2hlciByaXNrIGF2ZXJzaW9uLiBGb3IgbmVnYXRpdmUgcmV0dXJucywgd2Ugb2JzZXJ2ZSB0aGF0IHRoZSBhZ2VudCB3aXRoIGhpZ2hlciByaXNrIGF2ZXJzaW9uICJzdWZmZXJzIiBtb3JlLiBPbiB0aGUgb3RoZXIgaGFuZCwgc3VjaCBhbiBhZ2VudCBlbmpveXMgaGlnaGVyIHV0aWxpdHkgYXMgcmV0dXJucyBiZWNvbWUgcG9zaXRpdmUuIEdpdmVuIHRoZSBDQVJBIHV0aWxpdHksIHdlIGNhbiBtYXAgdGhlIHBvcnRmb2xpbyByZXR1cm4gcG9zaXRpb25zIGludG8gcmV3YXJkcyBhcyBmb2xsb3dzCmBgYHtyfQpkcyRSZXdhcmQgPC0gZHMkQWN0aW9uKmRhdGEudGFibGU6OnNoaWZ0KGRzJFNQWS5BZGp1c3RlZCwtMSkKZHMkQWN0aW9uIDwtIGFzLmNoYXJhY3RlcihkcyRBY3Rpb24pCmRzJFJld2FyZCA8LSBVKGRzJFJld2FyZCxSQSkKZHMgPC0gbmEub21pdChkcykKaGVhZChkcykKYGBgCk5vdyB0aGF0IHdlIGhhdmUgcmVwcmVzZW50ZWQgdGhlIGRhdGEgdXNpbmcgYSAkKHNfdCxhX3Qsc197dCsxfSkkIHR1cGxlLCB3ZSBjYW4gbW92ZSBvbiB0byB0cmFpbiB0aGUgbW9kZWwuIFdlIGhhdmUgdGhlIGRlZmF1bHQgY29udHJvbHMgYXMgYmVmb3JlCgpgYGB7cn0KY29udHJvbCA8LSBsaXN0KGFscGhhID0gYWxwaCwgZ2FtbWEgPSBnYW0sIGVwc2lsb24gPSBlcHMpCgptb2RlbF9zcHkgPC0gUmVpbmZvcmNlbWVudExlYXJuaW5nKGRzLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHMgPSAiU3RhdGUiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGEgPSAiQWN0aW9uIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByID0gIlJld2FyZCIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc19uZXcgPSAiTmV4dFN0YXRlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBjb250cm9sID0gY29udHJvbCkKCmRzJFJMX0FjdGlvbiA8LSBhcy5udW1lcmljKHByZWRpY3QobW9kZWxfc3B5LGRzJFN0YXRlKSkKZHMkTmV4dF9SZXQgPC0gZGF0YS50YWJsZTo6c2hpZnQoZHMkU1BZLkFkanVzdGVkLC0xKQpkcyRQb3J0Zm9saW9fUmV0X1JMIDwtIGRzJFJMX0FjdGlvbipkcyROZXh0X1JldApyZXQgPC0gbmEub21pdChkcyRQb3J0Zm9saW9fUmV0X1JMKQpTUl9STCA8LSBtZWFuKFUocmV0LFJBKSkKCiMgY29tcGFyZSB0byByYW5kb20gY2hvaWNlcwpyZXQ8LSBhcy5udW1lcmljKCBkcyRBY3Rpb24pKmRzJE5leHRfUmV0CnJldCA8LSBuYS5vbWl0KHJldCkKU1JfcmFuZG9tIDwtIG1lYW4oVShyZXQsUkEpKQpyb3VuZChkYXRhLmZyYW1lKFJhbmRvbSA9IFNSX3JhbmRvbSxSTCA9IFNSX1JMKSoxMDAsMikKYGBgClRoZSBhYm92ZSBjb21tYW5kcyB0cmFpbiB0aGUgYWdlbnQgYW5kIHJlc3VsdCBpbiBhIGhpZ2hlciB1dGlsaXR5IHJlbGF0aXZlIHRvIHJhbmRvbSBhY3Rpb25zLiBIb3dldmVyLCB0aGUgcXVlc3Rpb24gcmVtYWlucyB3aGV0aGVyIHRoaXMgaXMgYW4gb3B0aW1hbCBwb2xpY3kuIFRoZSBhYm92ZSBpcyBiYXNlZCBvbiBhIHNpbmdsZSByYW5kb20gaXRlcmF0aW9uLiBQZXJoYXBzIGlmIHdlIGZlZWQgdGhlIG1vZGVsIG1vcmUgZGF0YSwgdGhlIGFnZW50IGNhbiBhdHRhaW4gYSBoaWdoZXIgcmV3YXJkLiAKClRoZSBtYWpvciBkaWZmZXJlbmNlIGhlcmUgaXMgdGhhdCB3ZSBkbyBub3Qga25vdyB0aGUgZW52aXJvbm1lbnQgb2YgaG93IGVhY2ggYWN0aW9uIGFmZmVjdHMgdGhlIHRyYW5zaXRpb24gZnJvbSBzdGF0ZSAkc190JCB0byAkc197dCsxfSQuIEhlbmNlLCB1cGRhdGluZyB0aGUgcG9saWN5IGlzIG5vdCBzdHJhaWdodGZvcndhcmQuIE9uZSBwb3RlbnRpYWwgZXh0ZW5zaW9uIGlzIHRvIGNvbnNpZGVyIGFuIGVxdWlsaWJyaXVtIG1vZGVsIHN1Y2ggdGhhdCByZXR1cm5zIGFyZSBlbmRvZ2Vub3VzbHkgZGV0ZXJtaW5lZCBiYXNlZCBvbiBhY3Rpb24gYW5kIHN0YXRlLiBOb25ldGhlbGVzcywgaW4gdGhpcyBleGFtcGxlLCB3ZSB3aWxsIHJlZnJhaW4gZnJvbSBzdWNoIGFuYWx5c2lzIGFuZCBjb25zaWRlciBhbiBlbnZpcm9ubWVudC1mcmVlIGZyYW1ld29yay4gVGhlIGNoYWxsZW5nZSBoZXJlLCBob3dldmVyLCBpcyBob3cgdG8gc2ltdWxhdGUgZGF0YSB3aXRob3V0IGtub3dpbmcgdGhlIGVudmlyb25tZW50LiAKClRvIG92ZXJjb21lIHRoZSBhYm92ZSBjaGFsbGVuZ2UsIHdlIGNvbnNpZGVyIGFuIGFkLWhvYyBtb2RpZmljYXRpb24uIFNpbWlsYXIgdG8gdGhlICRcZXBzaWxvbiQtZ3JlZWR5IGFwcHJvYWNoLCB3ZSBzaW11bGF0ZSBhIHByb3BvcnRpb24gb2YgYWN0aW9ucyB0aGF0IGFyZSBjaG9zZW4gcmFuZG9tbHksIHdoZXJlYXMgdGhlIG90aGVyIGFjdGlvbnMgZm9sbG93IGFuIGluaXRpYWwgbW9kZWwuIEF0IGVhY2ggaXRlcmF0aW9uLCB3ZSBjaG9vc2UgJFxlcHNpbG9uJCBwcm9wb3J0aW9uIG9mIG1vbnRocyB3aGVyZSB0aGUgYWdlbnQgdGFrZXMgcmFuZG9tIGFjdGlvbnMsIHdoZXJlYXMsIGluIHRoZSAkMS1cZXBzaWxvbiQgbW9udGhzLCB0aGUgYWdlbnQgZm9sbG93cyB0aGUgcHJldmlvdXMgcG9saWN5LiBXZSBpdGVyYXRlIHRoaXMgc2V2ZXJhbCB0aW1lcyB1bnRpbCB3ZSBhdHRhaW4gYSBjZXJ0YWluIHNhdGlzZmFjdG9yeSB0aHJlc2hvbGQsIHdoaWNoIHdlIHNldCBiYXNlZCBvbiBhIGJlbmNobWFyay4gU3BlY2lmaWNhbGx5LCB0aGUgYmVuY2htYXJrIGlzIHNldCByZWxhdGl2ZSB0byBob2xkaW5nIHRoZSBTUFkgcGFzc2l2ZWx5LCB3aGljaCBjb3JyZXNwb25kcyB0byB0aGUgZm9sbG93aW5nIHJld2FyZApgYGB7cn0KeCA8LSBSJFNQWS5BZGp1c3RlZApTUFlfU1IgPC0gbWVhbihVKHgsUkEpKQpTUFlfU1IKYGBgCldlIG9ic2VydmUgdGhhdCB0aGUgaW5pdGlhbCBwb2xpY3kgYWJvdmUgdW5kZXJwZXJmb3JtcyB0aGUgcGFzc2l2ZSBvbmUgdGhhdCBsb25ncyB0aGUgU1BZIDEwMFwlIG9mIHRoZSB0aW1lLiBPdXIgZ29hbCBpcyB0byBmaW5kIGEgcG9saWN5IHRoYXQgb3V0cGVyZm9ybXMgdGhlIGJlbmNobWFyay4gV2UgcGVyZm9ybSB0aGUgZm9sbG93aW5nIGB3aGlsZWAgZnVuY3Rpb24sIHdoaWNoIHdlIHJ1biB1bnRpbCB3ZSBiZWF0IHRoZSBiZW5jaG1hcmsgb3IgZXhoYXVzdCBhIGNlcnRhaW4gbnVtYmVyIG9mIGl0ZXJhdGlvbnMsIHdoaWNoIHdlIHNldCB0byAxMDAuCgpgYGB7cn0KdG90X2l0ZXIgPC0gMTAwCml0ZXIgPC0gMgptb2RlbF9saXN0IDwtIGxpc3QobW9kZWxfc3B5KQpyZXdhcmRzX3NlcSA8LSBTUl9STAppIDwtIDAKd2hpbGUgKCFTUl9STCA+IFNQWV9TUikgewogIAogIGkgPC0gaSArIDEKICBkcyA8LSBSCiAgZHMgPC0gZGF0YS5mcmFtZShEYXRlID0gZGF0ZShkcyksIGRzKQogIGRzJFN0YXRlIDwtIChkcyRTUFkuQWRqdXN0ZWQgPiB0YXUpKjEgKyAtKGRzJFNQWS5BZGp1c3RlZCA8IC10YXUpKjEKICBkcyRTdGF0ZSA8LSBhcy5jaGFyYWN0ZXIoZHMkU3RhdGUpCiAgZHMkTmV4dFN0YXRlIDwtIGRhdGEudGFibGU6OnNoaWZ0KGRzJFN0YXRlLC0xKQogIAogICMgdGFrZSBhY3Rpb24gd2l0aCByZXNwZWN0IHRvIHRoZSBwcmV2aW91cyBtb2RlbAogIGRzJFJMX0FjdGlvbiA8LSBhcy5udW1lcmljKHByZWRpY3QobW9kZWxfc3B5LGRzJFN0YXRlKSkKICBzYW1wbGVfaW5kZXggPC0gc2FtcGxlKDE6bnJvdyhkcyksMSArIGZsb29yKG5yb3coZHMpKjAuNSooMSAtIGl0ZXIvdG90X2l0ZXIpKSkKICBkcyRBY3Rpb24gPC0gZHMkUkxfQWN0aW9uCiAgZHMkQWN0aW9uW3NhbXBsZV9pbmRleF0gPC0gc2FtcGxlKDE6MTAvMTAsbGVuZ3RoKHNhbXBsZV9pbmRleCkscmVwbGFjZSA9IFRSVUUpCiAgCiAgZHMkUmV3YXJkIDwtIGRzJEFjdGlvbipkYXRhLnRhYmxlOjpzaGlmdChkcyRTUFkuQWRqdXN0ZWQsLTEpCiAgZHMkUmV3YXJkIDwtIFUoZHMkUmV3YXJkLFJBKQogIGRzJEFjdGlvbiA8LSBhcy5jaGFyYWN0ZXIoZHMkQWN0aW9uKQogIGRzIDwtIG5hLm9taXQoZHMpCiAgCiAgIyB0cmFpbiB0aGUgbW9kZWwgYmFzZWQgb24gcmFuZG9tIGNob2ljZXMKICBtb2RlbF9zcHlfbmV3IDwtIFJlaW5mb3JjZW1lbnRMZWFybmluZyhkcywKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBzID0gIlN0YXRlIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhID0gIkFjdGlvbiIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgciA9ICJSZXdhcmQiLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNfbmV3ID0gIk5leHRTdGF0ZSIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgY29udHJvbCA9IGNvbnRyb2wsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbW9kZWwgPSBtb2RlbF9zcHkpCiAgCiAgZHMkUkxfQWN0aW9uIDwtIGFzLm51bWVyaWMocHJlZGljdChtb2RlbF9zcHlfbmV3LGRzJFN0YXRlKSkKICBkcyROZXh0X1JldCA8LSBkYXRhLnRhYmxlOjpzaGlmdChkcyRTUFkuQWRqdXN0ZWQsLTEpCiAgZHMkUG9ydGZvbGlvX1JldF9STCA8LSBkcyRSTF9BY3Rpb24qZHMkTmV4dF9SZXQKICByZXQgPC0gbmEub21pdChkcyRQb3J0Zm9saW9fUmV0X1JMKQogIFNSX1JMX25ldyA8LSBtZWFuKFUocmV0LFJBKSkKICAKICAjIGNvbXB1dGUgdGhlIGJlbmNobWFyayBmb3IgY29uc2lzdGVudCBldmFsdWF0aW9uCiAgeCA8LSBuYS5vbWl0KGRzJE5leHRfUmV0KQogIFNQWV9yZXdhcmQgPC0gbWVhbihVKHgsUkEpKQogIFNQWV9TUiA8LSBTUFlfcmV3YXJkCiAgCiAgaWYoaSA+IDEwMDApCiAgICBicmVhawogICMgdXBkYXRlIHRoZSBtb2RlbCBvbmx5IGlmIHBlcmZvcm1hbmNlIGlzIGJldHRlciB0aGFuIHByZXZpb3VzCiAgaWYoU1JfUkxfbmV3ID4gU1JfUkwpIHsKICAgIG1vZGVsX3NweSA8LSBtb2RlbF9zcHlfbmV3CiAgICBTUl9STCA8LSBTUl9STF9uZXcKICAgIGl0ZXIgPC0gaXRlciArIDEKICAgIGNhdCgiTW9kZWwgVXBkYXRlZCAiLCBpdGVyLCAiXG4iKQogICAgbW9kZWxfbGlzdCA8LSBjKG1vZGVsX2xpc3QsbGlzdChtb2RlbF9zcHkpKQogICAgcmV3YXJkc19zZXEgPC0gYyhyZXdhcmRzX3NlcSxTUl9STCkKICAgIGkgPC0gMAogIH0KICAKICBpZihpdGVyID4gdG90X2l0ZXIpIAogICAgYnJlYWsKfQpgYGAKRm9yIHRoZSBhYm92ZSByaXNrIGF2ZXJzaW9uLCB3aGljaCB3ZSBzZXQgdG8gYHIgUkFgLCB0aGUgbG9vcCB0ZXJtaW5hdGVzIGR1cmluZyB0aGUgdGhpcmQgaXRlcmF0aW9uLiBJbiB1bnJlcG9ydGVkIHJlc3VsdHMsIHRoZSBtb2RlbCB0YWtlcyBsb25nZXIgdG8gZmluZCBhIHBvbGljeSB0aGF0IG91dHBlcmZvcm1zIHRoZSBiZW5jaG1hcmsgd2hlbiB0aGUgcmlzayBhdmVyc2lvbiBpcyBsb3cuIEluZGVlZCwgaWYgdGhlIGFnZW50IGlzIHJpc2sgdG9sZXJhbnQsIGl0IG1ha2VzIGl0IGhhcmRlciB0byBmaW5kIGEgcG9saWN5IHRoYXQgb3V0cGVyZm9ybXMgdGhlIFNQWSBzaW5jZSB0aGUgYWdlbnQgY291bGQgYmUgYmV0dGVyIG9mZiBob2xkaW5nIHRoZSBTUFkgcGFzc2l2ZWx5LiBPbiB0aGUgb3RoZXIgaGFuZCwgdGhlIHJpc2stYXZlcnNlIGFnZW50IHdvdWxkIGJlIGJldHRlciBvZmYgYWxsb2NhdGluZyBsZXNzIHRoYW4gMTAwXCUgdG8gdGhlIFNQWSB0byBtaXRpZ2F0ZSByaXNrIGF2ZXJzaW9uLgoKTGV0IHVzIHRha2UgYSBsb29rIGF0IHRoZSBmaW5hbCBtb2RlbCBhbmQgcG9saWN5OgpgYGB7cn0KbW9kZWxfc3B5X25ldwpgYGAKQ29uc2lzdGVudCB3aXRoIGNvbW1vbiBzZW5zZSwgdGhlIHBvbGljeSBpbmRpY2F0ZXMgdGhhdCB0aGUgYWdlbnQgcmVkdWNlcyBleHBvc3VyZSB0byByaXNreSBhc3NldHMgaW4gc3RhdGVzIGFjY29tcGFuaWVkIGJ5IGxvdyByZXR1cm5zLiBTcGVjaWZpY2FsbHksIHRoZSBleHBvc3VyZSB0byByZWR1Y2VkIHRvIDcwXCUgZXF1aXR5LiBPbiB0aGUgb3RoZXIgaGFuZCwgZHVyaW5nIG1lZGl1bSAoaGlnaCkgc3RhdGVzLCB0aGUgZXhwb3N1cmUgaXMgODBcJSAoOTBcJSkuCgpMZXQgdXMgdGFrZSBhIGxvb2sgYXQgaG93IHN1Y2ggYSBwb2xpY3kgcGVyZm9ybXMgaW4gcHJhY3RpY2U6CmBgYHtyfQpkc19wbG90IDwtIGRzWyxjKCJOZXh0X1JldCIsIlBvcnRmb2xpb19SZXRfUkwiKV0KZGF0ZV9uYW1lcyA8LSByb3duYW1lcyhkc19wbG90KVstMV0KZHNfcGxvdCA8LSBuYS5vbWl0KGRzX3Bsb3QpCnJvd25hbWVzKGRzX3Bsb3QpIDwtIGRhdGVfbmFtZXMKZHNfcGxvdCA8LSBhcy54dHMoZHNfcGxvdCkKY2hhcnQuQ3VtUmV0dXJucyhkc19wbG90LGdlb21ldHJpYyA9IEZBTFNFKQpgYGAKV2Ugb2JzZXJ2ZSB0aGF0IHRoZSBSTCBhZ2VudCB1bmRlcnBlcmZvcm1zIHRoZSBwYXNzaXZlIGZ1bmQgaW4gdGVybXMgb2YgdGVybWluYWwgd2VhbHRoLiBIb3dldmVyLCBsZXQgdXMgdGFrZSBpbnRvIGFjY291bnQgdGhlIHJpc2sKYGBge3J9Cm15X3N1bSA8LSBmdW5jdGlvbih4KSB7CiAgbSA8LSBtZWFuKHgpKjEyCiAgcyA8LSBzZCh4KSpzcXJ0KDEyKQogIHNyIDwtIG0vcwogIHN2IDwtIHNkKHhbeDwwXSkqc3FydCgxMikKICBzcjIgPC0gbS9zdgogIFZhUiA8LSBtZWFuKHgpIC0gcXVhbnRpbGUoeCwwLjA1KQogIHJldHVybihjKG0scyxzdixzcixzcjIsVmFSKSkKfQoKcmVzdWx0IDwtIGRhdGEuZnJhbWUoYXBwbHkoZHNfcGxvdCwyLG15X3N1bSkpIApyb3duYW1lcyhyZXN1bHQpIDwtIGMoIk1lYW4iLCJWb2xhdGlsaXR5IiwiU2VtaS1Wb2xhdGlsaXR5IiwiU2hhcnBlIiwiU29ydGlubyIsIlZhUiIpCnJvdW5kKHJlc3VsdCwzKQpgYGAKQ29uc2lzdGVudCB3aXRoIHRoZSBhYm92ZSBwbG90LCB3ZSBzZWUgdGhhdCB0aGUgUkwgcG9saWN5IHJlc3VsdHMgaW4gbG93ZXIgcmV0dXJucyBhbmQgcmlzayBzaW11bHRhbmVvdXNseS4gUmVnYXJkaW5nIHJpc2stYWRqdXN0ZWQgcmV0dXJucywgd2Ugb2JzZXJ2ZSB0aGF0IHRoZSBSTCByZXN1bHRzIGluIGhpZ2hlciBTaGFycGUgYW5kIFNvcnRpbm8gcmF0aW9zLiBBZGRpdGlvbmFsbHksIHdlIG1lYXN1cmUgZG93bnNpZGUgcmlzayB1c2luZyB2YWx1ZS1hdC1yaXNrIChWYVIpLiBGaW5hbGx5LCB3ZSBvYnNlcnZlIHRoYXQgdGhlIFJMIHN0cmF0ZWd5IHJlc3VsdHMgaW4gbG93ZXIgdGFpbCByaXNrLgoKIyMgVGhvdWdodHMKVGhlIGFib3ZlIGFuYWx5c2lzIGlzIGNvbmR1Y3RlZCBpbi1zYW1wbGUgYW5kLCBoZW5jZSwgaXMgZGVzY3JpcHRpdmUgYnkgZGVzaWduLiBOZXZlcnRoZWxlc3MsIG9uZSBjYW4gYWRkcmVzcyBpbnRlcmVzdGluZyBxdWVzdGlvbnMgcmVnYXJkaW5nIHNldHRpbmcgdGhlIHJpZ2h0IGludmVzdG1lbnQgcG9saWN5IGZvciBpbnZlc3RvcnMgd2l0aCBkaWZmZXJlbnQgcmlzayBwcmVmZXJlbmNlcy4gVGhpcyBzaGVkcyBpbnRlcmVzdGluZyBsaWdodCBvbiB0aGUgYXBwZWFsIG9mIFJvYm8tYWR2aXNpbmcuIE1vcmVvdmVyLCBpbiB0ZXJtcyBvZiBwb3J0Zm9saW8gc2VsZWN0aW9uLCBmdXR1cmUgcmVzZWFyY2ggc2hvdWxkIGNvbnNpZGVyIHRoZSBvdXQtb2Ytc2FtcGxlIGFuYWx5c2lzIGFuZCBldmFsdWF0ZSB0aGUgYXBwZWFsIG9mIFJMIGZyb20gYSBwcmVkaWN0aXZlIHBvaW50IG9mIHZpZXcuIEkgbGVhdmUgdGhlc2UgZm9yIGZ1dHVyZSByZXNlYXJjaC4KCgoK