• 1 Exploring and visualizing time series in R
  • 2 Benchmark methods and forecast accuracy
  • 3 Exponential smoothing
  • 4 Forecasting with ARIMA models
  • 5 Advanced methods
    • 5.1 Dynamic regression
    • 5.2 Dynamic harmonic regression
    • 5.3 TBATS models

1 Exploring and visualizing time series in R

1.1 Welcome to Forecasting Using R

1.1.1 Creating time series objects in R

A time series can be thought of as a vector or matrix of numbers along with some information about what times those numbers were recorded. This information is stored in a ts object in R. In most exercises, you will use time series that are part of existing packages. However, if you want to work with your own data, you need to know how to create a ts object in R.

Let’s look at an example usnim_2002 below, containing net interest margins for US banks for the year 2002 (source: FFIEC).

usnim_2002
               usnim
1   2002-01-01  4.08
2   2002-04-01  4.10
3   2002-07-01  4.06
4   2002-10-01  4.04

# ts(data, start, frequency, ...)
usnim_ts = ts(usnim_2002[, 2], start = c(2002, 1), frequency = 4)

The function ts() takes in three arguments:

  • data is set to everything in usnim_2002 except for the date column; it isn’t needed since the ts object will store time information separately.
  • start is set to the form c(year, period) to indicate the time of the first observation. Here, January corresponds with period 1; likewise, a start date in April would refer to 2, July to 3, and October to 4. Thus, period corresponds to the quarter of the year.
  • frequency is set to 4 because the data are quarterly.

In this exercise, you will read in some time series data from an xlsx file using read_excel(), a function from the readxl package, and store the data as a ts object. Both the xlsx file and package have been loaded into your workspace.

library(readxl)
# Read the data from Excel into R
mydata <- read_excel("data/exercise1.xlsx")
New names:
* `` -> ...1
# Look at the first few lines of mydata
head(mydata)
ABCDEFGHIJ0123456789
...1
<chr>
Sales
<dbl>
AdBudget
<dbl>
GDP
<dbl>
Mar-811020.2659.2251.8
Jun-81889.2589.0290.9
Sep-81795.0512.5290.8
Dec-811003.9614.1292.4
Mar-821057.7647.2279.1
Jun-82944.4602.0254.0

Take a look at the dates - there are four observations in 1981, indicating quarterly data with a frequency of four rows per year. The first observation or start date is Mar-81, the first of four rows for year 1981, indicating that March corresponds with the first period.

# Create a ts object called myts
myts <- ts(mydata[, c(2:4)], start = c(1981, 1), frequency = 4)
head(myts)
      Sales AdBudget   GDP
[1,] 1020.2    659.2 251.8
[2,]  889.2    589.0 290.9
[3,]  795.0    512.5 290.8
[4,] 1003.9    614.1 292.4
[5,] 1057.7    647.2 279.1
[6,]  944.4    602.0 254.0

1.1.2 Time series plots

The first step in any data analysis task is to plot the data. Graphs enable you to visualize many features of the data, including patterns, unusual observations, changes over time, and relationships between variables. Just as the type of data determines which forecasting method to use, it also determines which graphs are appropriate.

You can use the autoplot() function to produce a time plot of the data with or without facets, or panels that display different subsets of data:

autoplot(usnim_2002, facets = FALSE)

The above method is one of the many taught in this course that accepts boolean arguments. Both T and TRUE mean “true”, and F and FALSE mean “false”, however, T and F can be overwritten in your code. Therefore, you should only rely on TRUE and FALSE to set your indicators for the remainder of the course.

You will use two more functions in this exercise, which.max() and frequency(). which.max() can be used to identify the smallest index of the maximum value

> x <- c(4, 5, 5)
> which.max(x)

[1] 2

To find the number of observations per unit time, use frequency(). Recall the usnim_2002 data from the previous exercise:

> frequency(usnim_2002)
[1] 4

Because this course involves the use of the forecast and ggplot2 packages:

library(forecast)
package 㤼㸱forecast㤼㸲 was built under R version 4.0.3Registered S3 method overwritten by 'quantmod':
  method            from
  as.zoo.data.frame zoo 
library(ggplot2)

The following three series are available in the package forecast:

  • gold containing gold prices in US dollars
  • woolyrnq containing information on the production of woollen yarn in Australia
  • gas containing Australian gas production
# Plot the data with facetting
autoplot(myts, facets = TRUE)


# Plot the data without facetting
autoplot(myts, facets = FALSE)


# Plot the three series
autoplot(gold)

autoplot(woolyrnq)

autoplot(gas)


# Find the outlier in the gold series
goldoutlier <- which.max(gold)
goldoutlier
[1] 770
# Look at the seasonal frequencies of the three series
frequency(gold)
[1] 1
frequency(woolyrnq)
[1] 4
frequency(gas)
[1] 12

1.1.3 Seasonal plots

Along with time plots, there are other useful ways of plotting data to emphasize seasonal patterns and show changes in these patterns over time.

-A seasonal plot is similar to a time plot except that the data are plotted against the individual “seasons” in which the data were observed. You can create one using the ggseasonplot() function the same way you do with autoplot(). - An interesting variant of a season plot uses polar coordinates, where the time axis is circular rather than horizontal; to make one, simply add a polar argument and set it to TRUE. - A subseries plot comprises mini time plots for each season. Here, the mean for each season is shown as a blue horizontal line.

One way of splitting a time series is by using the window() function, which extracts a subset from the object x observed between the times start and end.

window(x, start = NULL, end = NULL)

In this exercise, you will load the fpp2 package and use two of its datasets:

  • a10 contains monthly sales volumes for anti-diabetic drugs in Australia. In the plots, can you see which - month has the highest sales volume each year? What is unusual about the results in March and April 2008?
  • ausbeer which contains quarterly beer production for Australia. What is happening to the beer production in Quarter 4?
# Load the fpp2 package
library(fpp2)
package 㤼㸱fpp2㤼㸲 was built under R version 4.0.3-- Attaching packages ---------------------------------------------- fpp2 2.4 --
v fma       2.4     v expsmooth 2.3
package 㤼㸱fma㤼㸲 was built under R version 4.0.3package 㤼㸱expsmooth㤼㸲 was built under R version 4.0.3
# Create plots of the a10 data
autoplot(a10)

ggseasonplot(a10)


# Produce a polar coordinate season plot for the a10 data
ggseasonplot(a10, polar = TRUE)


# Restrict the ausbeer data to start in 1992
beer <- window(ausbeer, start = 1992)

# Make plots of the beer data
autoplot(beer)

ggsubseriesplot(beer)

1.3 White noise

1.3.1 Stock prices and white noise

White noise is a term that describes purely random data. You can conduct a Ljung-Box test using the function below to confirm the randomness of a series; a p-value greater than 0.05 suggests that the data are not significantly different from white noise.

Box.test(pigs, lag = 24, fitdf = 0, type = "Ljung")

There is a well-known result in economics called the “Efficient Market Hypothesis” that states that asset prices reflect all available information. A consequence of this is that the daily changes in stock prices should behave like white noise (ignoring dividends, interest rates and transaction costs). The consequence for forecasters is that the best forecast of the future price is the current price.

You can test this hypothesis by looking at the goog series, which contains the closing stock price for Google over 1000 trading days ending on February 13, 2017.

# Plot the original series
autoplot(goog)


# Plot the differenced series
autoplot(diff(goog))


# ACF of the differenced series
ggAcf(diff(goog))


# Ljung-Box test of the differenced series
Box.test(diff(goog), lag = 10, type = "Ljung")

    Box-Ljung test

data:  diff(goog)
X-squared = 13.123, df = 10, p-value = 0.2169

You have seen that the Ljung-Box test was not significant, so daily changes in the Google stock price look like white noise.

2 Benchmark methods and forecast accuracy

2.1 Forecasts and potential futures

2.1.1 Naive forecasting methods

A forecast is the mean or median of simulated futures of a time series.

The very simplest forecasting method is to use the most recent observation; this is called a naive forecast and can be implemented in a namesake function. This is the best that can be done for many time series including most stock price data, and even if it is not a good forecasting method, it provides a useful benchmark for other forecasting methods.

For seasonal data, a related idea is to use the corresponding season from the last year of data. For example, if you want to forecast the sales volume for next March, you would use the sales volume from the previous March. This is implemented in the snaive() function, meaning, seasonal naive.

For both forecasting methods, you can set the second argument h, which specifies the number of values you want to forecast; as shown in the code below, they have different default values. The resulting output is an object of class forecast. This is the core class of objects in the forecast package, and there are many functions for dealing with them including summary() and autoplot()

naive(y, h = 10)
snaive(y, h = 2 * frequency(x))
# Use naive() to forecast the goog series
fcgoog <- naive(goog, h = 20)

# Plot and summarize the forecasts
autoplot(fcgoog)

summary(fcgoog)

Forecast method: Naive method

Model Information:
Call: naive(y = goog, h = 20) 

Residual sd: 8.7343 

Error measures:
                    ME     RMSE      MAE        MPE      MAPE MASE       ACF1
Training set 0.4212612 8.734286 5.829407 0.06253998 0.9741428    1 0.03871446

Forecasts:
ABCDEFGHIJ0123456789
 
 
Point Forecast
<dbl>
Lo 80
<dbl>
Hi 80
<dbl>
Lo 95
<dbl>
Hi 95
<dbl>
1001813.67802.4765824.8634796.5511830.7889
1002813.67797.8401829.4999789.4602837.8797
1003813.67794.2824833.0576784.0192843.3208
1004813.67791.2831836.0569779.4322847.9078
1005813.67788.6407838.6993775.3910851.9490
1006813.67786.2518841.0882771.7374855.6025
1007813.67784.0549843.2850768.3777858.9623
1008813.67782.0102845.3298765.2505862.0895
1009813.67780.0897847.2503762.3133865.0266
1010813.67778.2732849.0667759.5353867.8047
# Use snaive() to forecast the ausbeer series
fcbeer <- snaive(ausbeer, h = 16)

# Plot and summarize the forecasts
autoplot(fcbeer)

summary(fcbeer)

Forecast method: Seasonal naive method

Model Information:
Call: snaive(y = ausbeer, h = 16) 

Residual sd: 19.3259 

Error measures:
                   ME     RMSE      MAE      MPE    MAPE MASE       ACF1
Training set 3.098131 19.32591 15.50935 0.838741 3.69567    1 0.01093868

Forecasts:
ABCDEFGHIJ0123456789
 
 
Point Forecast
<dbl>
Lo 80
<dbl>
Hi 80
<dbl>
Lo 95
<dbl>
Hi 95
<dbl>
2010 Q3419394.2329443.7671381.1219456.8781
2010 Q4488463.2329512.7671450.1219525.8781
2011 Q1414389.2329438.7671376.1219451.8781
2011 Q2374349.2329398.7671336.1219411.8781
2011 Q3419383.9740454.0260365.4323472.5677
2011 Q4488452.9740523.0260434.4323541.5677
2012 Q1414378.9740449.0260360.4323467.5677
2012 Q2374338.9740409.0260320.4323427.5677
2012 Q3419376.1020461.8980353.3932484.6068
2012 Q4488445.1020530.8980422.3932553.6068

2.2 Fitted values and residuals

2.2.1 Checking time series residuals

When applying a forecasting method, it is important to always check that the residuals are well-behaved (i.e., no outliers or patterns) and resemble white noise. The prediction intervals are computed assuming that the residuals are also normally distributed. You can use the checkresiduals() function to verify these characteristics; it will give the results of a Ljung-Box test.

In this exercise, you will test the above functions on the forecasts equivalent to what you produced in the previous exercise (fcgoog obtained after applying naive() to goog, and fcbeer obtained after applying snaive() to ausbeer).

# Check the residuals from the naive forecasts applied to the goog series
goog %>% naive() %>% checkresiduals()

    Ljung-Box test

data:  Residuals from Naive method
Q* = 13.123, df = 10, p-value = 0.2169

Model df: 0.   Total lags used: 10

# Do they look like white noise (TRUE or FALSE)
googwn <- TRUE

# Check the residuals from the seasonal naive forecasts applied to the ausbeer series
ausbeer %>% snaive() %>% checkresiduals()

    Ljung-Box test

data:  Residuals from Seasonal naive method
Q* = 60.535, df = 8, p-value = 3.661e-10

Model df: 0.   Total lags used: 8

# Do they look like white noise (TRUE or FALSE)
beerwn <- FALSE

2.3 Training and test sets

2.3.1 Evaluating forecast accuracy of non-seasonal methods

In data science, a training set is a data set that is used to discover possible relationships. A test set is a data set that is used to verify the strength of these potential relationships. When you separate a data set into these parts, you generally allocate more of the data for training, and less for testing.

One function that can be used to create training and test sets is subset.ts(), which returns a subset of a time series where the optional start and end arguments are specified using index values.

# x is a numerical vector or time series
# To subset observations from 101 to 500
train <- subset(x, start = 101, end = 500, ...)
`
# To subset the first 500 observations
train <- subset(x, end = 500, ...)

Another function, accuracy(), computes various forecast accuracy statistics given the forecasts and the corresponding actual observations. It is smart enough to find the relevant observations if you give it more than the ones you are forecasting.

> # f is an object of class "forecast"
> # x is a numerical vector or time series
> accuracy(f, x, ...)

The accuracy measures provided include root mean squared error (RMSE) which is the square root of the mean squared error (MSE). Minimizing RMSE, which corresponds with increasing accuracy, is the same as minimizing MSE.

The pre-loaded time series gold comprises daily gold prices for 1108 days. Here, you’ll use the first 1000 days as a training set, and compute forecasts for the remaining 108 days. These will be compared to the actual values for these days using the simple forcasting functions naive(), which you used earlier in this chapter, and meanf(), which gives forecasts equal to the mean of all observations. You’ll have to specify the keyword h (which specifies the number of values you want to forecast) for both.

# Create the training data as train
train <- subset(gold, end = 1000)

# Compute naive forecasts and save to naive_fc
naive_fc <- naive(train, h = 108)

# Compute mean forecasts and save to mean_fc
mean_fc <- meanf(train, h = 108)

# Use accuracy() to compute RMSE statistics
accuracy(naive_fc, gold)
                     ME      RMSE      MAE        MPE      MAPE     MASE       ACF1 Theil's U
Training set  0.1079897  6.358087  3.20366  0.0201449 0.8050646 1.014334 -0.3086638        NA
Test set     -6.5383495 15.842361 13.63835 -1.7462269 3.4287888 4.318139  0.9793153  5.335899
accuracy(mean_fc, gold)
                        ME     RMSE      MAE       MPE      MAPE      MASE      ACF1 Theil's U
Training set -4.239671e-15 59.17809 53.63397 -2.390227 14.230224 16.981449 0.9907254        NA
Test set      1.319363e+01 19.55255 15.66875  3.138577  3.783133  4.960998 0.9793153  6.123788
# Assign one of the two forecasts as bestforecasts
bestforecasts <- naive_fc

2.3.2 Evaluating forecast accuracy of seasonal methods

The window() function specifies the start and end of a time series using the relevant times rather than the index values. Either of those two arguments can be formatted as a vector like c(year, period) which you have also previously used as an argument for ts(). Again, period refers to quarter here.

Here, you will use the Melbourne quarterly visitor numbers (vn[, “Melbourne”]) to create three different training sets, omitting the last 1, 2 and 3 years, respectively. Inspect the pre-loaded vn data in your console before beginning the exercise; this will help you determine the correct value to use for the keyword h (which specifies the number of values you want to forecast) in your forecasting methods.

Then for each training set, compute the next year of data, and finally compare the mean absolute percentage error (MAPE) of the forecasts using accuracy(). Why do you think that the MAPE vary so much?

vn <- readRDS("vn.RDS")
vn <- ts(vn[, c(2:8)], start = c(1998, 1), frequency = 4)
# Create three training series omitting the last 1, 2, and 3 years
train1 <- window(vn[, "Melbourne"], end = c(2014, 4))
train2 <- window(vn[, "Melbourne"], end = c(2013, 4))
train3 <- window(vn[, "Melbourne"], end = c(2012, 4))

# Produce forecasts using snaive()
fc1 <- snaive(train1, h = 4)
fc2 <- snaive(train2, h = 4)
fc3 <- snaive(train3, h = 4)

# Use accuracy() to compare the MAPE of each series
accuracy(fc1, vn[, "Melbourne"])["Test set", "MAPE"]
[1] 5.477917
accuracy(fc2, vn[, "Melbourne"])["Test set", "MAPE"]
[1] 12.50071
accuracy(fc3, vn[, "Melbourne"])["Test set", "MAPE"]
[1] 7.950202

2.3.3 When does a model forecast well?

A good model forecasts well (so has low RMSE on the test set) and uses all available information in the training data (so has white noise residuals).

2.4 Time series cross-validation

2.4.1 Using tsCV() for time series cross-validation

The tsCV() function computes time series cross-validation errors. It requires you to specify the time series, the forecast method, and the forecast horizon.

e = tsCV(oil, forecastfunction = naive, h = 1)

Here, you will use tsCV() to compute and plot the MSE values for up to 8 steps ahead, along with the naive() method applied to the goog data. T

# Compute cross-validated errors for up to 8 steps ahead
e <- tsCV(goog, forecastfunction = naive, h = 8)

# Compute the MSE values and remove missing values
mse <- colMeans(e^2, na.rm = TRUE)

# Plot the MSE values against the forecast horizon
data.frame(h = 1:8, MSE = mse) %>%
  ggplot(aes(x = h, y = MSE)) + geom_point()

data.frame(h = 1:8, MSE = mse)
ABCDEFGHIJ0123456789
 
 
h
<int>
MSE
<dbl>
h=1176.28775
h=22158.96282
h=33241.54818
h=44314.72312
h=55379.76003
h=66441.01128
h=77504.44510
h=88566.55904

3 Exponential smoothing

3.1 Exponentially weighted forecasts

3.1.1 Simple exponential smoothing

The ses() function produces forecasts obtained using simple exponential smoothing (SES). The parameters are estimated using least squares estimation. All you need to specify is the time series and the forecast horizon; the default forecast time is h = 10 years.

> args(ses)
function (y, h = 10, ...)

> fc <- ses(oildata, h = 5)
> summary(fc)

You will also use summary() and fitted(), along with autolayer() for the first time, which is like autoplot() but it adds a “layer” to a plot rather than creating a new plot.

Here, you will apply these functions to marathon, the annual winning times in the Boston marathon from 1897-2016. The data are available in your workspace.

# Use ses() to forecast the next 10 years of winning times
fc <- ses(marathon, h = 10)

# Use summary() to see the model parameters
summary(fc)

Forecast method: Simple exponential smoothing

Model Information:
Simple exponential smoothing 

Call:
 ses(y = marathon, h = 10) 

  Smoothing parameters:
    alpha = 0.3457 

  Initial states:
    l = 167.1741 

  sigma:  5.519

     AIC     AICc      BIC 
988.4474 988.6543 996.8099 

Error measures:
                     ME     RMSE      MAE        MPE     MAPE      MASE        ACF1
Training set -0.8874349 5.472771 3.826294 -0.7097395 2.637644 0.8925685 -0.01211236

Forecasts:
ABCDEFGHIJ0123456789
 
 
Point Forecast
<dbl>
Lo 80
<dbl>
Hi 80
<dbl>
Lo 95
<dbl>
Hi 95
<dbl>
2017130.3563123.2835137.4292119.5394141.1733
2018130.3563122.8727137.8399118.9111141.8015
2019130.3563122.4833138.2293118.3156142.3970
2020130.3563122.1123138.6003117.7482142.9644
2021130.3563121.7573138.9553117.2053143.5074
2022130.3563121.4164139.2963116.6839144.0288
2023130.3563121.0880139.6247116.1816144.5310
2024130.3563120.7708139.9418115.6966145.0161
2025130.3563120.4639140.2488115.2271145.4856
2026130.3563120.1661140.5466114.7717145.9409
# Use autoplot() to plot the forecasts
autoplot(fc)


# Add the one-step forecasts for the training data to the plot
autoplot(fc) + autolayer(fitted(fc))

3.1.2 SES vs naive

In this exercise, you will apply your knowledge of training and test sets, the subset() function, and the accuracy() function, all of which you learned in Chapter 2, to compare SES and naive forecasts for the marathon data.

You did something very similar to compare the naive and mean forecasts in an earlier exercise “Evaluating forecast accuracy of non-seasonal methods”.

Let’s review the process:

  1. First, import and load your data. Determine how much of your data you want to allocate to training, and how much to testing; the sets should not overlap.
  2. Subset the data to create a training set, which you will use as an argument in your forecasting function(s). Optionally, you can also create a test set to use later.
  3. Compute forecasts of the training set using whichever forecasting function(s) you choose, and set h equal to the number of values you want to forecast, which is also the length of the test set.
  4. To view the results, use the accuracy() function with the forecast as the first argument and original data (or test set) as the second.
  5. Pick a measure in the output, such as RMSE or MAE, to evaluate the forecast(s); a smaller error indicates higher accuracy.
# Create a training set using subset()
train <- subset(marathon, end = length(marathon) - 20)

# Compute SES and naive forecasts, save to fcses and fcnaive
fcses <- ses(train, h = 20)
fcnaive <- naive(train, h = 20)

# Calculate forecast accuracy measures
accuracy(fcses,  marathon)
                     ME     RMSE      MAE        MPE     MAPE      MASE        ACF1 Theil's U
Training set -1.0851741 5.863790 4.155948 -0.8603998 2.827993 0.8990906 -0.01595953        NA
Test set      0.4574579 2.493971 1.894237  0.3171919 1.463862 0.4097960 -0.12556096 0.6870735
accuracy(fcnaive,  marathon)
                     ME     RMSE      MAE        MPE     MAPE      MASE       ACF1 Theil's U
Training set -0.4638047 6.904742 4.622391 -0.4086317 3.123559 1.0000000 -0.3589323        NA
Test set      0.2266667 2.462113 1.846667  0.1388780 1.429608 0.3995047 -0.1255610 0.6799062

3.2 Exponential smoothing methods with trend

3.2.1 Holt’s trend methods

Holt’s local trend method is implemented in the holt() function:

holt(y, h = 10, ...)

Here, you will apply it to the austa series, which contains annual counts of international visitors to Australia from 1980-2015 (in millions).

# Produce 10 year forecasts of austa using holt()
fcholt <- holt(austa, h=10)

# Look at fitted model using summary()
summary(fcholt)

Forecast method: Holt's method

Model Information:
Holt's method 

Call:
 holt(y = austa, h = 10) 

  Smoothing parameters:
    alpha = 0.9999 
    beta  = 0.0085 

  Initial states:
    l = 0.656 
    b = 0.1706 

  sigma:  0.1952

     AIC     AICc      BIC 
17.14959 19.14959 25.06719 

Error measures:
                     ME      RMSE       MAE       MPE     MAPE      MASE      ACF1
Training set 0.00372838 0.1840662 0.1611085 -1.222083 5.990319 0.7907078 0.2457733

Forecasts:
ABCDEFGHIJ0123456789
 
 
Point Forecast
<dbl>
Lo 80
<dbl>
Hi 80
<dbl>
Lo 95
<dbl>
Hi 95
<dbl>
20167.0306836.7804837.2808826.6480367.413330
20177.2024466.8471147.5577786.6590137.745879
20187.3742096.9371697.8112496.7058148.042604
20197.5459727.0391798.0527656.7708998.321045
20207.7177367.1487238.2867486.8475068.587965
20217.8894997.2635438.5154556.9321818.846816
20228.0612627.3823028.7402227.0228829.099642
20238.2330257.5041368.9619157.1182859.347766
20248.4047887.6284449.1811337.2174729.592105
20258.5765527.7547929.3983117.3197799.833324
# Plot the forecasts
autoplot(fcholt)


# Check that the residuals look like white noise
checkresiduals(fcholt)

    Ljung-Box test

data:  Residuals from Holt's method
Q* = 4.8886, df = 3, p-value = 0.1801

Model df: 4.   Total lags used: 7

3.3 Exponential smoothing methods with trend and seasonality

3.3.1 Holt-Winters with monthly data

You learned that the hw() function produces forecasts using the Holt-Winters method specific to whatever you set equal to the seasonal argument:

fc1 <- hw(aust, seasonal = "additive")
fc2 <- hw(aust, seasonal = "multiplicative")

Here, you will apply hw() to a10, the monthly sales of anti-diabetic drugs in Australia from 1991 to 2008.

# Plot the data
autoplot(a10)


# Produce 3 year forecasts
fc <- hw(a10, seasonal = "multiplicative", h = 36)

# Check if residuals look like white noise
checkresiduals(fc)

    Ljung-Box test

data:  Residuals from Holt-Winters' multiplicative method
Q* = 75.764, df = 8, p-value = 3.467e-13

Model df: 16.   Total lags used: 24

whitenoise <- FALSE

# Plot forecasts
autoplot(fc)

The forecasts might still provide useful information even with residuals that fail the white noise test.

3.3.2 Holt-Winters method with daily data

The Holt-Winters method can also be used for daily type of data, where the seasonal pattern is of length 7, and the appropriate unit of time for h is in days.

Here, you will compare an additive Holt-Winters method and a seasonal naive() method for the hyndsight data, which contains the daily pageviews on the Hyndsight blog for one year starting April 30, 2014.

# Create training data with subset()
train <- subset(hyndsight, end = length(hyndsight) - 28)

# Holt-Winters additive forecasts as fchw
fchw <- hw(train, seasonal = "additive", h = 28)

# Seasonal naive forecasts as fcsn
fcsn <- snaive(train, h = 28)

# Find better forecasts with accuracy()
accuracy(fchw, hyndsight)
                    ME     RMSE      MAE       MPE    MAPE      MASE      ACF1 Theil's U
Training set -3.976241 228.2440 165.0244 -2.407211 13.9955 0.7492131 0.1900853        NA
Test set     -3.999460 201.7656 152.9584 -3.218292 10.5558 0.6944332 0.3013328 0.4868701
accuracy(fcsn, hyndsight)
                ME     RMSE      MAE        MPE     MAPE      MASE      ACF1 Theil's U
Training set 10.50 310.3282 220.2636 -2.1239387 18.01077 1.0000000 0.4255730        NA
Test set      0.25 202.7610 160.4643 -0.6888732 10.25880 0.7285101 0.3089795  0.450266
# Plot the better forecasts
autoplot(fchw)

3.4 State space models for exponential smoothing

3.4.1 Automatic forecasting with exponential smoothing

The namesake function for finding errors, trend, and seasonality (ETS) provides a completely automatic way of producing forecasts for a wide range of time series.

# Fit ETS model to austa in fitaus
fitaus <- ets(austa)

# Check residuals
checkresiduals(fitaus)

    Ljung-Box test

data:  Residuals from ETS(A,A,N)
Q* = 4.8886, df = 3, p-value = 0.1801

Model df: 4.   Total lags used: 7

# Plot forecasts
autoplot(forecast(fitaus))


# Repeat for hyndsight data in fiths
fiths <- ets(hyndsight)
checkresiduals(fiths)

    Ljung-Box test

data:  Residuals from ETS(A,N,A)
Q* = 68.616, df = 5, p-value = 1.988e-13

Model df: 9.   Total lags used: 14

autoplot(forecast(fiths))


# Which model(s) fails test? (TRUE or FALSE)
fitausfail <- FALSE
fithsfail <- TRUE

3.4.2 ETS vs seasonal naive

Here, you will compare ETS forecasts against seasonal naive forecasting for 20 years of cement, which contains quarterly cement production using time series cross-validation for 4 steps ahead.

The second argument for tsCV() must return a forecast object, so you need a function to fit a model and return forecasts. Recall:

> args(tsCV)
function (y, forecastfunction, h = 1, ...)
cement_ <-  subset(qcement, start = length(qcement) - 80)
# Function to return ETS forecasts
fets <- function(y, h) {
  forecast(ets(y), h = h)
}

# Apply tsCV() for both methods
e1 <- tsCV(cement_, fets, h = 4)
e2 <- tsCV(cement_, snaive, h = 4)

# Compute MSE of resulting errors (watch out for missing values)
mean(e1^2, na.rm = TRUE)
[1] 0.0329896
mean(e2^2, na.rm = TRUE)
[1] 0.03046892
# Copy the best forecast MSE
bestmse <- mean(e2^2, na.rm = TRUE)

3.4.3 When does ETS fail?

Computing the ETS does not work well for all series.

Here, you will observe why it does not work well for the annual Canadian lynx population available in your workspace as lynx.

# Plot the lynx series
autoplot(lynx)


# Use ets() to model the lynx series
fit <- ets(lynx)

# Use summary() to look at model and parameters
summary(fit)
ETS(M,N,N) 

Call:
 ets(y = lynx) 

  Smoothing parameters:
    alpha = 0.9999 

  Initial states:
    l = 2372.8047 

  sigma:  0.9594

     AIC     AICc      BIC 
2058.138 2058.356 2066.346 

Training set error measures:
                   ME     RMSE      MAE       MPE     MAPE     MASE      ACF1
Training set 8.975647 1198.452 842.0649 -52.12968 101.3686 1.013488 0.3677583
# Plot 20-year forecasts of the lynx series
fit %>% forecast(h = 20) %>% autoplot()

It’s important to realize that ETS doesn’t work for all cases.

4 Forecasting with ARIMA models

4.1 Transformations for variance stabilization

4.1.1 Box-Cox transformations for time series

Here, you will use a Box-Cox transformation to stabilize the variance of the pre-loaded a10 series, which contains monthly anti-diabetic drug sales in Australia from 1991-2008.

In this exercise, you will need to experiment to see the effect of the lambda (λ) argument on the transformation. Notice that small changes in λ make little difference to the resulting series. You want to find a value of λ that makes the seasonal fluctuations of roughly the same size across the series.

Recall from the video that the recommended range for lambda values is −1≤λ≤1.

# Plot the series
autoplot(a10)


# Try four values of lambda in Box-Cox transformations
a10 %>% BoxCox(lambda = 0.0) %>% autoplot()

a10 %>% BoxCox(lambda = 0.1) %>% autoplot()

a10 %>% BoxCox(lambda = 0.2) %>% autoplot()

a10 %>% BoxCox(lambda = 0.3) %>% autoplot()


# Compare with BoxCox.lambda()
BoxCox.lambda(a10)
[1] 0.1313326

It seems like a lambda of .13 would work well.

4.1.2 Non-seasonal differencing for stationarity

Differencing is a way of making a time series stationary; this means that you remove any systematic patterns such as trend and seasonality from the data. A white noise series is considered a special case of a stationary time series.

With non-seasonal data, you use lag-1 differences to model changes between observations rather than the observations directly. You have done this before by using the diff() function.

In this exercise, you will use the pre-loaded wmurders data, which contains the annual female murder rate in the US from 1950-2004.

# Plot the US female murder rate
autoplot(wmurders)


# Plot the differenced murder rate
autoplot(diff(wmurders))


# Plot the ACF of the differenced murder rate
ggAcf(diff(wmurders))

It seems like the data look like white noise after differencing.

4.1.3 Seasonal differencing for stationarity

With seasonal data, differences are often taken between observations in the same season of consecutive years, rather than in consecutive periods. For example, with quarterly data, one would take the difference between Q1 in one year and Q1 in the previous year. This is called seasonal differencing.

Sometimes you need to apply both seasonal differences and lag-1 differences to the same series, thus, calculating the differences in the differences.

In this exercise, you will use differencing and transformations simultaneously to make a time series look stationary. The data set here is h02, which contains 17 years of monthly corticosteroid drug sales in Australia.

# Plot the data
autoplot(h02)


# Take logs and seasonal differences of h02
difflogh02 <- diff(log(h02), lag = 12)

# Plot difflogh02
autoplot(difflogh02)


# Take another difference and plot
ddifflogh02 <- diff(difflogh02)
autoplot(ddifflogh02)


# Plot ACF of ddifflogh02
ggAcf(ddifflogh02)

The data doesn’t look like white noise after the transformation, but you could develop an ARIMA model for it.

4.2 ARIMA models

4.2.1 Automatic ARIMA models for non-seasonal time series

The auto.arima() function will select an appropriate autoregressive integrated moving average (ARIMA) model given a time series, just like the ets() function does for ETS models. The summary() function can provide some additional insights:

> # p = 2, d = 1, p = 2
> summary(fit)

Series: usnetelec
ARIMA(2,1,2) with drift
...

In this exercise, you will automatically choose an ARIMA model for the pre-loaded austa series, which contains the annual number of international visitors to Australia from 1980-2015. You will then check the residuals (recall that a p-value greater than 0.05 indicates that the data resembles white noise) and produce some forecasts. Other than the modelling function, this is identicial to what you did with ETS forecasting.

# Fit an automatic ARIMA model to the austa series
fit <- auto.arima(austa)

# Check that the residuals look like white noise
checkresiduals(fit)

    Ljung-Box test

data:  Residuals from ARIMA(0,1,1) with drift
Q* = 2.297, df = 5, p-value = 0.8067

Model df: 2.   Total lags used: 7

residualsok <- TRUE

# Summarize the model
summary(fit)
Series: austa 
ARIMA(0,1,1) with drift 

Coefficients:
         ma1   drift
      0.3006  0.1735
s.e.  0.1647  0.0390

sigma^2 estimated as 0.03376:  log likelihood=10.62
AIC=-15.24   AICc=-14.46   BIC=-10.57

Training set error measures:
                       ME      RMSE       MAE       MPE     MAPE      MASE         ACF1
Training set 0.0008313383 0.1759116 0.1520309 -1.069983 5.513269 0.7461559 -0.000571993
# Find the AICc value and the number of differences used
AICc <- -14.46
d <- 1

# Plot forecasts of fit
fit %>% forecast(h = 10) %>% autoplot()

4.2.2 Forecasting with ARIMA models

The automatic method in the previous exercise chose an ARIMA(0,1,1) with drift model for the austa data, that is, yt=c+yt−1+θet−1+et. You will now experiment with various other ARIMA models for the data to see what difference it makes to the forecasts.

The Arima() function can be used to select a specific ARIMA model. Its first argument, order, is set to a vector that specifies the values of p, d and q. The second argument, include.constant, is a booolean that determines if the constant c, or drift, should be included. Below is an example of a pipe function that would plot forecasts of usnetelec from an ARIMA(2,1,2) model with drift:

usnetelec %>%
    Arima(order = c(2,1,2), include.constant = TRUE) %>%
    forecast() %>%
    autoplot()

In the examples here, watch for how the different models affect the forecasts and the prediction intervals.

# Plot forecasts from an ARIMA(0,1,1) model with no drift
austa %>% Arima(order = c(0, 1, 1), include.constant = FALSE) %>% forecast() %>% autoplot()


# Plot forecasts from an ARIMA(2,1,3) model with drift
austa %>% Arima(order = c(2, 1, 3), include.constant = TRUE) %>% forecast() %>% autoplot()


# Plot forecasts from an ARIMA(0,0,1) model with a constant
austa %>% Arima(order = c(0, 0, 1), include.constant = TRUE) %>% forecast() %>% autoplot()


# Plot forecasts from an ARIMA(0,2,1) model with no constant
austa %>% Arima(order = c(0, 2, 1), include.constant = FALSE) %>% forecast() %>% autoplot()

4.2.3 Comparing auto.arima() and ets() on non-seasonal data

The AICc statistic is useful for selecting between models in the same class. For example, you can use it to select an ETS model or to select an ARIMA model. However, you cannot use it to compare ETS and ARIMA models because they are in different model classes.

Instead, you can use time series cross-validation to compare an ARIMA model and an ETS model on the austa data. Because tsCV() requires functions that return forecast objects, you will set up some simple functions that fit the models and return the forecasts. The arguments of tsCV() are a time series, forecast function, and forecast horizon h. Examine this code snippet from the second chapter:

e <- matrix(NA_real_, nrow = 1000, ncol = 8)
for (h in 1:8)
  e[, h] <- tsCV(goog, naive, h = h)
  ...

Furthermore, recall that pipe operators in R take the value of whatever is on the left and pass it as an argument to whatever is on the right, step by step, from left to right. Here’s an example based on code you saw in an earlier chapter:

# Plot 20-year forecasts of the lynx series modeled by ets()
lynx %>% ets() %>% forecast(h = 20) %>% autoplot()

In this exercise, you will compare the MSE of two forecast functions applied to austa, and plot forecasts of the function that computes the best forecasts.

# Set up forecast functions for ETS and ARIMA models
fets <- function(x, h) {
  forecast(ets(x), h = h)
}
farima <- function(x, h) {
  forecast(auto.arima(x), h = h)
}

# Compute CV errors for ETS on austa as e1
e1 <- tsCV(austa, fets, h = 1)

# Compute CV errors for ARIMA on austa as e2
e2 <- tsCV(austa, farima, h = 1)

# Find MSE of each model class
mean(e1^2, na.rm = TRUE)
[1] 0.05623684
mean(e2^2, na.rm = TRUE)
[1] 0.04336277
# Plot 10-year forecasts using the best model class
austa %>% farima(h = 10) %>% autoplot()

4.3 Seasonal ARIMA models

4.3.1 Automatic ARIMA models for seasonal time series

the auto.arima() function also works with seasonal data. Note that setting lambda = 0 in the auto.arima() function - applying a log transformation - means that the model will be fitted to the transformed data, and that the forecasts will be back-transformed onto the original scale.

After applying summary() to this kind of fitted model, you may see something like the output below which corresponds with (p,d,q)(P,D,Q)[m]:

ARIMA(0,1,4)(0,1,1)[12]

In this exercise, you will use these functions to model and forecast the pre-loaded h02 data, which contains monthly sales of cortecosteroid drugs in Australia.

# Check that the logged h02 data have stable variance
h02 %>% log() %>% autoplot()


# Fit a seasonal ARIMA model to h02 with lambda = 0
fit <- auto.arima(h02, lambda = 0)

# Summarize the fitted model
summary(fit)
Series: h02 
ARIMA(2,1,1)(0,1,2)[12] 
Box Cox transformation: lambda= 0 

Coefficients:
          ar1      ar2     ma1     sma1     sma2
      -1.1358  -0.5753  0.3683  -0.5318  -0.1817
s.e.   0.1608   0.0965  0.1884   0.0838   0.0881

sigma^2 estimated as 0.004278:  log likelihood=248.25
AIC=-484.51   AICc=-484.05   BIC=-465

Training set error measures:
                       ME      RMSE        MAE        MPE     MAPE      MASE         ACF1
Training set -0.003931805 0.0501571 0.03629816 -0.5323365 4.611253 0.5987988 -0.003740267
# Record the amount of lag-1 differencing and seasonal differencing used
d <- 1
D <- 1

# Plot 2-year forecasts
fit %>% forecast(h = 24) %>% autoplot()

auto.arima() is flexible enough to even work with seasonal time series!

4.3.2 Exploring auto.arima() options

The auto.arima() function needs to estimate a lot of different models, and various short-cuts are used to try to make the function as fast as possible. This can cause a model to be returned which does not actually have the smallest AICc value. To make auto.arima() work harder to find a good model, add the optional argument stepwise = FALSE to look at a much larger collection of models.

Here, you will try finding an ARIMA model for the pre-loaded euretail data, which contains quarterly retail trade in the Euro area from 1996-2011.

autoplot(euretail)

# Find an ARIMA model for euretail
fit1 <- auto.arima(euretail)

# Don't use a stepwise search
fit2 <- auto.arima(euretail, stepwise = FALSE)

summary(fit1)
Series: euretail 
ARIMA(0,1,3)(0,1,1)[4] 

Coefficients:
         ma1     ma2     ma3     sma1
      0.2630  0.3694  0.4200  -0.6636
s.e.  0.1237  0.1255  0.1294   0.1545

sigma^2 estimated as 0.156:  log likelihood=-28.63
AIC=67.26   AICc=68.39   BIC=77.65

Training set error measures:
                      ME      RMSE       MAE         MPE      MAPE      MASE        ACF1
Training set -0.02965298 0.3661147 0.2787802 -0.02795377 0.2885545 0.2267735 0.006455781
summary(fit2)
Series: euretail 
ARIMA(0,1,3)(0,1,1)[4] 

Coefficients:
         ma1     ma2     ma3     sma1
      0.2630  0.3694  0.4200  -0.6636
s.e.  0.1237  0.1255  0.1294   0.1545

sigma^2 estimated as 0.156:  log likelihood=-28.63
AIC=67.26   AICc=68.39   BIC=77.65

Training set error measures:
                      ME      RMSE       MAE         MPE      MAPE      MASE        ACF1
Training set -0.02965298 0.3661147 0.2787802 -0.02795377 0.2885545 0.2267735 0.006455781
# AICc of better model
AICc <- 68.39

# Compute 2-year forecasts from better model
fit2 %>% forecast(h = 8) %>% autoplot()

4.3.3 Comparing auto.arima() and ets() on seasonal data

What happens when you want to create training and test sets for data that is more frequent than yearly? If needed, you can use a vector in form c(year, period) for the start and/or end keywords in the window() function. You must also ensure that you’re using the appropriate values of h in forecasting functions. Recall that h should be equal to the length of the data that makes up your test set.

For example, if your data spans 15 years, your training set consists of the first 10 years, and you intend to forecast the last 5 years of data, you would use h = 12 * 5 not h = 5 because your test set would include 60 monthly observations. If instead your training set consists of the first 9.5 years and you want forecast the last 5.5 years, you would use h = 66 to account for the extra 6 months.

In the final exercise for this chapter, you will compare seasonal ARIMA and ETS models applied to the quarterly cement production data qcement. Because the series is very long, you can afford to use a training and test set rather than time series cross-validation. This is much faster.

# Use 20 years of the qcement data beginning in 1988
train <- window(qcement, start = c(1988, 1), end = c(2007, 4))

# Fit an ARIMA and an ETS model to the training data
fit1 <- auto.arima(train)
fit2 <- ets(train)

# Check that both models have white noise residuals
checkresiduals(fit1)

    Ljung-Box test

data:  Residuals from ARIMA(1,0,1)(2,1,1)[4] with drift
Q* = 3.3058, df = 3, p-value = 0.3468

Model df: 6.   Total lags used: 9

checkresiduals(fit2)

    Ljung-Box test

data:  Residuals from ETS(M,N,M)
Q* = 6.3457, df = 3, p-value = 0.09595

Model df: 6.   Total lags used: 9

# Produce forecasts for each model
fc1 <- forecast(fit1, h = 25)
fc2 <- forecast(fit2, h = 25)

# Use accuracy() to find better model based on RMSE
accuracy(fc1, qcement)
                       ME      RMSE        MAE        MPE     MAPE      MASE        ACF1 Theil's U
Training set -0.006205705 0.1001195 0.07988903 -0.6704455 4.372443 0.5458078 -0.01133907        NA
Test set     -0.158835253 0.1996098 0.16882205 -7.3332836 7.719241 1.1534049  0.29170452 0.7282225
accuracy(fc2, qcement)
                      ME      RMSE        MAE        MPE     MAPE      MASE        ACF1 Theil's U
Training set  0.01406512 0.1022079 0.07958478  0.4938163 4.371823 0.5437292 -0.03346295        NA
Test set     -0.13495515 0.1838791 0.15395141 -6.2508975 6.986077 1.0518075  0.53438371  0.680556
bettermodel <- fit2

Looks like the ETS model did better here.

5 Advanced methods

5.1 Dynamic regression

5.1.1 Forecasting sales allowing for advertising expenditure

The auto.arima() function will fit a dynamic regression model with ARIMA errors. The only change to how you used it previously is that you will now use the xreg argument containing a matrix of regression variables.

fit <- auto.arima(uschange[, "Consumption"],
                    xreg = uschange[, "Income"])

# rep(x, times)
fcast <- forecast(fit, xreg = rep(0.8, 8))

You can see that the data is set to the Consumption column of uschange, and the regression variable is the Income column. Furthermore, the rep() function in this case would replicate the value 0.8 exactly eight times for the matrix argument xreg.

In this exercise, you will model sales data regressed against advertising expenditure, with an ARMA error to account for any serial correlation in the regression errors. The data are available in your workspace as advert and comprise 24 months of sales and advertising expenditure for an automotive parts company. The plot shows sales vs advertising expenditure.

ggplot(aes(x = advert, y = sales), data = as.data.frame(advsales)) +
  geom_point()

# Time plot of both variables
autoplot(advsales, facets = TRUE)

Fit a regression with ARIMA errors to advert by setting the first argument of auto.arima() to the “sales” column, second argument xreg to the “advert” column, and third argument stationary to TRUE.

# Fit ARIMA model
fit <- auto.arima(advsales[, "sales"], xreg = advsales[,"advert"], stationary = TRUE)

Check that the fitted model is a regression with AR(1) errors. What is the increase in sales for every unit increase in advertising? This coefficient is the third element in the coefficients() output.

summary(fit)
Series: advsales[, "sales"] 
Regression with ARIMA(1,0,0) errors 

Coefficients:
         ar1  intercept    xreg
      0.6412    20.8737  0.0926
s.e.  0.1559     2.0842  0.0426

sigma^2 estimated as 18.48:  log likelihood=-102.28
AIC=212.55   AICc=213.84   BIC=218.89

Training set error measures:
                   ME    RMSE      MAE       MPE     MAPE      MASE         ACF1
Training set 0.249122 4.11534 3.545525 -2.679881 15.90975 0.9530981 -0.006839681
# Check model. Increase in sales for each unit increase in advertising
salesincrease <- coefficients(fit)[3]
salesincrease
      xreg 
0.09264183 

orecast from the fitted model specifying the next 6 months of advertising expenditure as 10 units per month as fc. To repeat 10 six times, use the rep() function inside xreg like in the example code above.

Plot the forecasts fc and fill in the provided code to add an x label “Month” and y label “Sales”.

# Forecast fit as fc
fc <- forecast(fit, xreg = rep(0.1, 6))

# Plot fc with x and y labels
autoplot(fc) + xlab("Month") + ylab("Sales")

The dynamic regression allows you to include other outside information into your forecast.

5.1.2 Forecasting electricity demand

You can also model daily electricity demand as a function of temperature. As you may have seen on your electric bill, more electricity is used on hot days due to air conditioning and on cold days due to heating.

In this exercise, you will fit a quadratic regression model with an ARMA error. One year of daily data are stored as elec including total daily demand, an indicator variable for workdays (a workday is represented with 1, and a non-workday is represented with 0), and daily maximum temperatures. Because there is weekly seasonality, the frequency has been set to 7.

Let’s take a look at the first three rows:

elecdaily[1:3, ]
       Demand WorkDay Temperature
[1,] 174.8963       0        26.0
[2,] 188.5909       1        23.0
[3,] 188.9169       1        22.2
ggplot(aes(x = Temperature, y = Demand), data  = as.data.frame(elecdaily)) +
  geom_point()

# Time plots of demand and temperatures
autoplot(elecdaily[, c("Demand", "Temperature")], facets = TRUE)

Index elec accordingly to set up the matrix of regressors to include MaxTemp for the maximum temperatures, MaxTempSq which represents the squared value of the maximum temperature, and Workday, in that order. Clearly, the second argument of cbind() will require a simple mathematical operator.

# Matrix of regressors
# Matrix of regressors
xreg <- cbind(MaxTemp = elecdaily[, "Temperature"], 
              MaxTempSq = elecdaily[, "Temperature"]^2, 
              Workday = elecdaily[, "WorkDay"])

Fit a dynamic regression model of the demand column with ARIMA errors and call this fit

# Fit model
fit <- auto.arima(elecdaily[, "Demand"], xreg = xreg)

If the next day is a working day (indicator is 1) with maximum temperature forecast to be 20°C, what is the forecast demand? Fill out the appropriate values in cbind() for the xreg argument in forecast().

# Forecast fit one day ahead
forecast(fit, xreg = cbind(MaxTemp = 20, 
              MaxTempSq = 20^2, 
              Workday = 1))
ABCDEFGHIJ0123456789
 
 
Point Forecast
<dbl>
Lo 80
<dbl>
Hi 80
<dbl>
Lo 95
<dbl>
Hi 95
<dbl>
53.57143185.4008176.9271193.8745172.4414198.3602

Now you’ve seen how multiple independent variables can be included using matrices.

5.2 Dynamic harmonic regression

5.2.1 Forecasting weekly data

With weekly data, it is difficult to handle seasonality using ETS or ARIMA models as the seasonal length is too large (approximately 52). Instead, you can use harmonic regression which uses sines and cosines to model the seasonality.

The fourier() function makes it easy to generate the required harmonics. The higher the order (K), the more “wiggly” the seasonal pattern is allowed to be. With K=1, it is a simple sine curve. You can select the value of K by minimizing the AICc value. fourier() takes in a required time series, required number of Fourier terms to generate, and optional number of rows it needs to forecast:

# fourier(x, K, h = NULL)

> fit <- auto.arima(cafe, xreg = fourier(cafe, K = 6),
                    seasonal = FALSE, lambda = 0)
> fit %>%
    forecast(xreg = fourier(cafe, K = 6, h = 24)) %>%
    autoplot() + ylim(1.6, 5.1)

gasoline data comprises weekly data on US finished motor gasoline products. In this exercise, you will fit a harmonic regression to this data set and forecast the next 3 years.

# Set up harmonic regressors of order 13
harmonics <- fourier(gasoline, K = 13)

# Fit regression model with ARIMA errors
fit <- auto.arima(gasoline, xreg = harmonics, seasonal = FALSE)

# Forecasts next 3 years
newharmonics <- fourier(gasoline, K = 13, h = 52*3)
fc <- forecast(fit, xreg = newharmonics)

# Plot forecasts fc
autoplot(fc)

The point predictions look to be a bit low.

5.2.2 Harmonic regression for multiple seasonality

Harmonic regressions are also useful when time series have multiple seasonal patterns. For example, taylor contains half-hourly electricity demand in England and Wales over a few months in the year 2000. The seasonal periods are 48 (daily seasonality) and 7 x 48 = 336 (weekly seasonality). There is not enough data to consider annual seasonality.

auto.arima() would take a long time to fit a long time series such as this one, so instead you will fit a standard regression model with Fourier terms using the tslm() function. This is very similar to lm() but is designed to handle time series. With multiple seasonality, you need to specify the order K for each of the seasonal periods.

# The formula argument is a symbolic description
# of the model to be fitted

> args(tslm)
function (formula, ...)

tslm() is a newly introduced function, so you should be able to follow the pre-written code for the most part.

# Fit a harmonic regression using order 10 for each type of seasonality
fit <- tslm(taylor ~ fourier(taylor, K = c(10, 10)))

# Forecast 20 working days ahead
fc <- forecast(fit, newdata = data.frame(fourier(taylor, K = c(10, 10), h = 48*20)))

# Plot the forecasts
autoplot(fc)


# Check the residuals of fit
checkresiduals(fit)

    Breusch-Godfrey test for serial correlation of order up to 672

data:  Residuals from Linear regression model
LM test = 3938.9, df = 672, p-value < 2.2e-16

The residuals from the fitted model fail the tests badly, yet the forecasts are quite good.

5.2.3 Forecasting call bookings

Another time series with multiple seasonal periods is calls, which contains 20 consecutive days of 5-minute call volume data for a large North American bank. There are 169 5-minute periods in a working day, and so the weekly seasonal frequency is 5 x 169 = 845. The weekly seasonality is relatively weak, so here you will just model daily seasonality. calls is pre-loaded into your workspace.

The residuals in this case still fail the white noise tests, but their autocorrelations are tiny, even though they are significant. This is because the series is so long. It is often unrealistic to have residuals that pass the tests for such long series. The effect of the remaining correlations on the forecasts will be negligible.

# Plot the calls data
autoplot(calls)

Set up the xreg matrix using order 10 for daily seasonality and 0 for weekly seasonality. Note that if you incorrectly specify your vector, your session may expire!

Fit a dynamic regression model called fit using auto.arima() with seasonal = FALSE and stationary = TRUE.

# Set up the xreg matrix
xreg <- fourier(calls, K = c(10, 0))

# Fit a dynamic regression model
fit <- auto.arima(calls, xreg = xreg, seasonal = FALSE, stationary = TRUE)

# Check the residuals
checkresiduals(fit)

    Ljung-Box test

data:  Residuals from Regression with ARIMA(5,0,1) errors
Q* = 6846.8, df = 1663, p-value < 2.2e-16

Model df: 27.   Total lags used: 1690

# Plot forecasts for 10 working days ahead
fc <- forecast(fit, xreg =  fourier(calls, c(10, 0), h = 10*169))
autoplot(fc)

5.3 TBATS models

A TBATS model is a special kind of time series model. It can be very slow to estimate, especially with multiple seasonal time series, so in this exercise you will try it on a simpler series to save time. Let’s break down elements of a TBATS model in TBATS(1, {0,0}, -, {<51.18,14>})

Component Meaning
1 Box-Cox transformation parameter
{0,0} ARMA error
- Damping parameter
{<51.18,14>} Seasonal period, Fourier terms

The gas data contains Australian monthly gas production. A plot of the data shows the variance has changed a lot over time, so it needs a transformation. The seasonality has also changed shape over time, and there is a strong trend. This makes it an ideal series to test the tbats() function which is designed to handle these features.

# Plot the gas data
autoplot(gas)


# Fit a TBATS model to the gas data
fit <- tbats(gas)

# Forecast the series for the next 5 years
fc <- forecast(fit, h = 12*5)

# Plot the forecasts
autoplot(fc)

# Record the Box-Cox parameter and the order of the Fourier terms
lambda <- 0.082
K <- 5

Just remember that completely automated solutions don’t work every time.

LS0tDQp0aXRsZTogIkZvcmVjYXN0aW5nIGluIFIiDQpvdXRwdXQ6DQogIGh0bWxfbm90ZWJvb2s6DQogICAgdG9jOiB0cnVlDQogICAgdG9jX2Zsb2F0OiB0cnVlDQogICAgdG9jX2NvbGxhcHNlZDogZmFsc2UNCiAgICBudW1iZXJfc2VjdGlvbnM6IHRydWUNCiAgICANCnRvY19kZXB0aDogMw0KLS0tDQojIEV4cGxvcmluZyBhbmQgdmlzdWFsaXppbmcgdGltZSBzZXJpZXMgaW4gUg0KDQojIyBXZWxjb21lIHRvIEZvcmVjYXN0aW5nIFVzaW5nIFINCg0KIyMjIENyZWF0aW5nIHRpbWUgc2VyaWVzIG9iamVjdHMgaW4gUg0KDQpBIHRpbWUgc2VyaWVzIGNhbiBiZSB0aG91Z2h0IG9mIGFzIGEgdmVjdG9yIG9yIG1hdHJpeCBvZiBudW1iZXJzIGFsb25nIHdpdGggc29tZSBpbmZvcm1hdGlvbiBhYm91dCB3aGF0IHRpbWVzIHRob3NlIG51bWJlcnMgd2VyZSByZWNvcmRlZC4gVGhpcyBpbmZvcm1hdGlvbiBpcyBzdG9yZWQgaW4gYSB0cyBvYmplY3QgaW4gUi4gSW4gbW9zdCBleGVyY2lzZXMsIHlvdSB3aWxsIHVzZSB0aW1lIHNlcmllcyB0aGF0IGFyZSBwYXJ0IG9mIGV4aXN0aW5nIHBhY2thZ2VzLiBIb3dldmVyLCBpZiB5b3Ugd2FudCB0byB3b3JrIHdpdGggeW91ciBvd24gZGF0YSwgeW91IG5lZWQgdG8ga25vdyBob3cgdG8gY3JlYXRlIGEgdHMgb2JqZWN0IGluIFIuDQoNCkxldCdzIGxvb2sgYXQgYW4gZXhhbXBsZSB1c25pbV8yMDAyIGJlbG93LCBjb250YWluaW5nIG5ldCBpbnRlcmVzdCBtYXJnaW5zIGZvciBVUyBiYW5rcyBmb3IgdGhlIHllYXIgMjAwMiAoc291cmNlOiBGRklFQykuDQoNCiAgICB1c25pbV8yMDAyDQogICAgICAgICAgICAgICAgICAgdXNuaW0NCiAgICAxICAgMjAwMi0wMS0wMSAgNC4wOA0KICAgIDIgICAyMDAyLTA0LTAxICA0LjEwDQogICAgMyAgIDIwMDItMDctMDEgIDQuMDYNCiAgICA0ICAgMjAwMi0xMC0wMSAgNC4wNA0KICAgIA0KICAgICMgdHMoZGF0YSwgc3RhcnQsIGZyZXF1ZW5jeSwgLi4uKQ0KICAgIHVzbmltX3RzID0gdHModXNuaW1fMjAwMlssIDJdLCBzdGFydCA9IGMoMjAwMiwgMSksIGZyZXF1ZW5jeSA9IDQpDQoNCg0KVGhlIGZ1bmN0aW9uIHRzKCkgdGFrZXMgaW4gdGhyZWUgYXJndW1lbnRzOg0KDQotIGRhdGEgaXMgc2V0IHRvIGV2ZXJ5dGhpbmcgaW4gdXNuaW1fMjAwMiBleGNlcHQgZm9yIHRoZSBkYXRlIGNvbHVtbjsgaXQgaXNuJ3QgbmVlZGVkIHNpbmNlIHRoZSB0cyBvYmplY3Qgd2lsbCBzdG9yZSB0aW1lIGluZm9ybWF0aW9uIHNlcGFyYXRlbHkuDQotIHN0YXJ0IGlzIHNldCB0byB0aGUgZm9ybSBjKHllYXIsIHBlcmlvZCkgdG8gaW5kaWNhdGUgdGhlIHRpbWUgb2YgdGhlIGZpcnN0IG9ic2VydmF0aW9uLiBIZXJlLCBKYW51YXJ5IGNvcnJlc3BvbmRzIHdpdGggcGVyaW9kIDE7IGxpa2V3aXNlLCBhIHN0YXJ0IGRhdGUgaW4gQXByaWwgd291bGQgcmVmZXIgdG8gMiwgSnVseSB0byAzLCBhbmQgT2N0b2JlciB0byA0LiBUaHVzLCBwZXJpb2QgY29ycmVzcG9uZHMgdG8gdGhlIHF1YXJ0ZXIgb2YgdGhlIHllYXIuDQotIGZyZXF1ZW5jeSBpcyBzZXQgdG8gNCBiZWNhdXNlIHRoZSBkYXRhIGFyZSBxdWFydGVybHkuDQoNCkluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIHJlYWQgaW4gc29tZSB0aW1lIHNlcmllcyBkYXRhIGZyb20gYW4geGxzeCBmaWxlIHVzaW5nIHJlYWRfZXhjZWwoKSwgYSBmdW5jdGlvbiBmcm9tIHRoZSByZWFkeGwgcGFja2FnZSwgYW5kIHN0b3JlIHRoZSBkYXRhIGFzIGEgdHMgb2JqZWN0LiBCb3RoIHRoZSB4bHN4IGZpbGUgYW5kIHBhY2thZ2UgaGF2ZSBiZWVuIGxvYWRlZCBpbnRvIHlvdXIgd29ya3NwYWNlLg0KYGBge3J9DQpsaWJyYXJ5KHJlYWR4bCkNCiMgUmVhZCB0aGUgZGF0YSBmcm9tIEV4Y2VsIGludG8gUg0KbXlkYXRhIDwtIHJlYWRfZXhjZWwoImRhdGEvZXhlcmNpc2UxLnhsc3giKQ0KDQojIExvb2sgYXQgdGhlIGZpcnN0IGZldyBsaW5lcyBvZiBteWRhdGENCmhlYWQobXlkYXRhKQ0KYGBgDQoNCg0KVGFrZSBhIGxvb2sgYXQgdGhlIGRhdGVzIC0gdGhlcmUgYXJlIGZvdXIgb2JzZXJ2YXRpb25zIGluIDE5ODEsIGluZGljYXRpbmcgcXVhcnRlcmx5IGRhdGEgd2l0aCBhIGZyZXF1ZW5jeSBvZiBmb3VyIHJvd3MgcGVyIHllYXIuIFRoZSBmaXJzdCBvYnNlcnZhdGlvbiBvciBzdGFydCBkYXRlIGlzIE1hci04MSwgdGhlIGZpcnN0IG9mIGZvdXIgcm93cyBmb3IgeWVhciAxOTgxLCBpbmRpY2F0aW5nIHRoYXQgTWFyY2ggY29ycmVzcG9uZHMgd2l0aCB0aGUgZmlyc3QgcGVyaW9kLg0KYGBge3J9DQojIENyZWF0ZSBhIHRzIG9iamVjdCBjYWxsZWQgbXl0cw0KbXl0cyA8LSB0cyhteWRhdGFbLCBjKDI6NCldLCBzdGFydCA9IGMoMTk4MSwgMSksIGZyZXF1ZW5jeSA9IDQpDQpoZWFkKG15dHMpDQpgYGANCiMjIyBUaW1lIHNlcmllcyBwbG90cw0KDQpUaGUgZmlyc3Qgc3RlcCBpbiBhbnkgZGF0YSBhbmFseXNpcyB0YXNrIGlzIHRvIHBsb3QgdGhlIGRhdGEuIEdyYXBocyBlbmFibGUgeW91IHRvIHZpc3VhbGl6ZSBtYW55IGZlYXR1cmVzIG9mIHRoZSBkYXRhLCBpbmNsdWRpbmcgcGF0dGVybnMsIHVudXN1YWwgb2JzZXJ2YXRpb25zLCBjaGFuZ2VzIG92ZXIgdGltZSwgYW5kIHJlbGF0aW9uc2hpcHMgYmV0d2VlbiB2YXJpYWJsZXMuIEp1c3QgYXMgdGhlIHR5cGUgb2YgZGF0YSBkZXRlcm1pbmVzIHdoaWNoIGZvcmVjYXN0aW5nIG1ldGhvZCB0byB1c2UsIGl0IGFsc28gZGV0ZXJtaW5lcyB3aGljaCBncmFwaHMgYXJlIGFwcHJvcHJpYXRlLg0KDQpZb3UgY2FuIHVzZSB0aGUgYXV0b3Bsb3QoKSBmdW5jdGlvbiB0byBwcm9kdWNlIGEgdGltZSBwbG90IG9mIHRoZSBkYXRhIHdpdGggb3Igd2l0aG91dCBmYWNldHMsIG9yIHBhbmVscyB0aGF0IGRpc3BsYXkgZGlmZmVyZW50IHN1YnNldHMgb2YgZGF0YToNCg0KICAgIGF1dG9wbG90KHVzbmltXzIwMDIsIGZhY2V0cyA9IEZBTFNFKQ0KDQpUaGUgYWJvdmUgbWV0aG9kIGlzIG9uZSBvZiB0aGUgbWFueSB0YXVnaHQgaW4gdGhpcyBjb3Vyc2UgdGhhdCBhY2NlcHRzIGJvb2xlYW4gYXJndW1lbnRzLiBCb3RoIFQgYW5kIFRSVUUgbWVhbiAidHJ1ZSIsIGFuZCBGIGFuZCBGQUxTRSBtZWFuICJmYWxzZSIsIGhvd2V2ZXIsIFQgYW5kIEYgY2FuIGJlIG92ZXJ3cml0dGVuIGluIHlvdXIgY29kZS4gVGhlcmVmb3JlLCB5b3Ugc2hvdWxkIG9ubHkgcmVseSBvbiBUUlVFIGFuZCBGQUxTRSB0byBzZXQgeW91ciBpbmRpY2F0b3JzIGZvciB0aGUgcmVtYWluZGVyIG9mIHRoZSBjb3Vyc2UuDQoNCllvdSB3aWxsIHVzZSB0d28gbW9yZSBmdW5jdGlvbnMgaW4gdGhpcyBleGVyY2lzZSwgd2hpY2gubWF4KCkgYW5kIGZyZXF1ZW5jeSgpLg0Kd2hpY2gubWF4KCkgY2FuIGJlIHVzZWQgdG8gaWRlbnRpZnkgdGhlIHNtYWxsZXN0IGluZGV4IG9mIHRoZSBtYXhpbXVtIHZhbHVlDQogICAgDQogICAgPiB4IDwtIGMoNCwgNSwgNSkNCiAgICA+IHdoaWNoLm1heCh4KQ0KICAgIA0KICAgIFsxXSAyDQoNClRvIGZpbmQgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgcGVyIHVuaXQgdGltZSwgdXNlIGZyZXF1ZW5jeSgpLiBSZWNhbGwgdGhlIHVzbmltXzIwMDIgZGF0YSBmcm9tIHRoZSBwcmV2aW91cyBleGVyY2lzZToNCg0KICAgID4gZnJlcXVlbmN5KHVzbmltXzIwMDIpDQogICAgWzFdIDQNCg0KQmVjYXVzZSB0aGlzIGNvdXJzZSBpbnZvbHZlcyB0aGUgdXNlIG9mIHRoZSBmb3JlY2FzdCBhbmQgZ2dwbG90MiBwYWNrYWdlczoNCmBgYHtyfQ0KbGlicmFyeShmb3JlY2FzdCkNCmxpYnJhcnkoZ2dwbG90MikNCmBgYA0KVGhlIGZvbGxvd2luZyB0aHJlZSBzZXJpZXMgYXJlIGF2YWlsYWJsZSBpbiB0aGUgcGFja2FnZSBmb3JlY2FzdDoNCg0KLSBnb2xkIGNvbnRhaW5pbmcgZ29sZCBwcmljZXMgaW4gVVMgZG9sbGFycw0KLSB3b29seXJucSBjb250YWluaW5nIGluZm9ybWF0aW9uIG9uIHRoZSBwcm9kdWN0aW9uIG9mIHdvb2xsZW4geWFybiBpbiBBdXN0cmFsaWENCi0gZ2FzIGNvbnRhaW5pbmcgQXVzdHJhbGlhbiBnYXMgcHJvZHVjdGlvbg0KYGBge3J9DQojIFBsb3QgdGhlIGRhdGEgd2l0aCBmYWNldHRpbmcNCmF1dG9wbG90KG15dHMsIGZhY2V0cyA9IFRSVUUpDQoNCiMgUGxvdCB0aGUgZGF0YSB3aXRob3V0IGZhY2V0dGluZw0KYXV0b3Bsb3QobXl0cywgZmFjZXRzID0gRkFMU0UpDQoNCiMgUGxvdCB0aGUgdGhyZWUgc2VyaWVzDQphdXRvcGxvdChnb2xkKQ0KYXV0b3Bsb3Qod29vbHlybnEpDQphdXRvcGxvdChnYXMpDQoNCiMgRmluZCB0aGUgb3V0bGllciBpbiB0aGUgZ29sZCBzZXJpZXMNCmdvbGRvdXRsaWVyIDwtIHdoaWNoLm1heChnb2xkKQ0KZ29sZG91dGxpZXINCg0KIyBMb29rIGF0IHRoZSBzZWFzb25hbCBmcmVxdWVuY2llcyBvZiB0aGUgdGhyZWUgc2VyaWVzDQpmcmVxdWVuY3koZ29sZCkNCmZyZXF1ZW5jeSh3b29seXJucSkNCmZyZXF1ZW5jeShnYXMpDQpgYGANCiMjIyBTZWFzb25hbCBwbG90cw0KDQpBbG9uZyB3aXRoIHRpbWUgcGxvdHMsIHRoZXJlIGFyZSBvdGhlciB1c2VmdWwgd2F5cyBvZiBwbG90dGluZyBkYXRhIHRvIGVtcGhhc2l6ZSBzZWFzb25hbCBwYXR0ZXJucyBhbmQgc2hvdyBjaGFuZ2VzIGluIHRoZXNlIHBhdHRlcm5zIG92ZXIgdGltZS4NCg0KIC1BIHNlYXNvbmFsIHBsb3QgaXMgc2ltaWxhciB0byBhIHRpbWUgcGxvdCBleGNlcHQgdGhhdCB0aGUgZGF0YSBhcmUgcGxvdHRlZCBhZ2FpbnN0IHRoZSBpbmRpdmlkdWFsIOKAnHNlYXNvbnPigJ0gaW4gd2hpY2ggdGhlIGRhdGEgd2VyZSBvYnNlcnZlZC4gWW91IGNhbiBjcmVhdGUgb25lIHVzaW5nIHRoZSBnZ3NlYXNvbnBsb3QoKSBmdW5jdGlvbiB0aGUgc2FtZSB3YXkgeW91IGRvIHdpdGggYXV0b3Bsb3QoKS4NCi0gQW4gaW50ZXJlc3RpbmcgdmFyaWFudCBvZiBhIHNlYXNvbiBwbG90IHVzZXMgcG9sYXIgY29vcmRpbmF0ZXMsIHdoZXJlIHRoZSB0aW1lIGF4aXMgaXMgY2lyY3VsYXIgcmF0aGVyIHRoYW4gaG9yaXpvbnRhbDsgdG8gbWFrZSBvbmUsIHNpbXBseSBhZGQgYSBwb2xhciBhcmd1bWVudCBhbmQgc2V0IGl0IHRvIFRSVUUuDQotIEEgc3Vic2VyaWVzIHBsb3QgY29tcHJpc2VzIG1pbmkgdGltZSBwbG90cyBmb3IgZWFjaCBzZWFzb24uIEhlcmUsIHRoZSBtZWFuIGZvciBlYWNoIHNlYXNvbiBpcyBzaG93biBhcyBhIGJsdWUgaG9yaXpvbnRhbCBsaW5lLg0KDQpPbmUgd2F5IG9mIHNwbGl0dGluZyBhIHRpbWUgc2VyaWVzIGlzIGJ5IHVzaW5nIHRoZSB3aW5kb3coKSBmdW5jdGlvbiwgd2hpY2ggZXh0cmFjdHMgYSBzdWJzZXQgZnJvbSB0aGUgb2JqZWN0IHggb2JzZXJ2ZWQgYmV0d2VlbiB0aGUgdGltZXMgc3RhcnQgYW5kIGVuZC4NCg0KICAgIHdpbmRvdyh4LCBzdGFydCA9IE5VTEwsIGVuZCA9IE5VTEwpDQogICAgDQpJbiB0aGlzIGV4ZXJjaXNlLCB5b3Ugd2lsbCBsb2FkIHRoZSBmcHAyIHBhY2thZ2UgYW5kIHVzZSB0d28gb2YgaXRzIGRhdGFzZXRzOg0KDQotIGExMCBjb250YWlucyBtb250aGx5IHNhbGVzIHZvbHVtZXMgZm9yIGFudGktZGlhYmV0aWMgZHJ1Z3MgaW4gQXVzdHJhbGlhLiBJbiB0aGUgcGxvdHMsIGNhbiB5b3Ugc2VlIHdoaWNoIC0gbW9udGggaGFzIHRoZSBoaWdoZXN0IHNhbGVzIHZvbHVtZSBlYWNoIHllYXI/IFdoYXQgaXMgdW51c3VhbCBhYm91dCB0aGUgcmVzdWx0cyBpbiBNYXJjaCBhbmQgQXByaWwgMjAwOD8NCi0gYXVzYmVlciB3aGljaCBjb250YWlucyBxdWFydGVybHkgYmVlciBwcm9kdWN0aW9uIGZvciBBdXN0cmFsaWEuIFdoYXQgaXMgaGFwcGVuaW5nIHRvIHRoZSBiZWVyIHByb2R1Y3Rpb24gaW4gUXVhcnRlciA0Pw0KDQpgYGB7cn0NCiMgTG9hZCB0aGUgZnBwMiBwYWNrYWdlDQpsaWJyYXJ5KGZwcDIpDQoNCiMgQ3JlYXRlIHBsb3RzIG9mIHRoZSBhMTAgZGF0YQ0KYXV0b3Bsb3QoYTEwKQ0KZ2dzZWFzb25wbG90KGExMCkNCg0KIyBQcm9kdWNlIGEgcG9sYXIgY29vcmRpbmF0ZSBzZWFzb24gcGxvdCBmb3IgdGhlIGExMCBkYXRhDQpnZ3NlYXNvbnBsb3QoYTEwLCBwb2xhciA9IFRSVUUpDQoNCiMgUmVzdHJpY3QgdGhlIGF1c2JlZXIgZGF0YSB0byBzdGFydCBpbiAxOTkyDQpiZWVyIDwtIHdpbmRvdyhhdXNiZWVyLCBzdGFydCA9IDE5OTIpDQoNCiMgTWFrZSBwbG90cyBvZiB0aGUgYmVlciBkYXRhDQphdXRvcGxvdChiZWVyKQ0KZ2dzdWJzZXJpZXNwbG90KGJlZXIpDQpgYGANCiMjIFRyZW5kcywgc2Vhc29uYWxpdHksIGFuZCBjeWNsaWNpdHkNCg0KIyMjIEF1dG9jb3JyZWxhdGlvbiBvZiBub24tc2Vhc29uYWwgdGltZSBzZXJpZXMNCg0KQW5vdGhlciB3YXkgdG8gbG9vayBhdCB0aW1lIHNlcmllcyBkYXRhIGlzIHRvIHBsb3QgZWFjaCBvYnNlcnZhdGlvbiBhZ2FpbnN0IGFub3RoZXIgb2JzZXJ2YXRpb24gdGhhdCBvY2N1cnJlZCBzb21lIHRpbWUgcHJldmlvdXNseSBieSB1c2luZyBnZ2xhZ3Bsb3QoKS4gRm9yIGV4YW1wbGUsIHlvdSBjb3VsZCBwbG90IHl0IGFnYWluc3QgeXTiiJIxLiBUaGlzIGlzIGNhbGxlZCBhIGxhZyBwbG90IGJlY2F1c2UgeW91IGFyZSBwbG90dGluZyB0aGUgdGltZSBzZXJpZXMgYWdhaW5zdCBsYWdzIG9mIGl0c2VsZi4NCg0KVGhlIGNvcnJlbGF0aW9ucyBhc3NvY2lhdGVkIHdpdGggdGhlIGxhZyBwbG90cyBmb3JtIHdoYXQgaXMgY2FsbGVkIHRoZSBhdXRvY29ycmVsYXRpb24gZnVuY3Rpb24gKEFDRikuIFRoZSBnZ0FjZigpIGZ1bmN0aW9uIHByb2R1Y2VzIEFDRiBwbG90cy4NCg0KSW4gdGhpcyBleGVyY2lzZSwgeW91IHdpbGwgd29yayB3aXRoIHRoZSBwcmUtbG9hZGVkIG9pbCBkYXRhIChhdmFpbGFibGUgaW4gdGhlIHBhY2thZ2UgZnBwMiksIHdoaWNoIGNvbnRhaW5zIHRoZSBhbm51YWwgb2lsIHByb2R1Y3Rpb24gaW4gU2F1ZGkgQXJhYmlhIGZyb20gMTk2NS0yMDEzIChtZWFzdXJlZCBpbiBtaWxsaW9ucyBvZiB0b25zKS4NCmBgYHtyfQ0KIyBDcmVhdGUgYW4gYXV0b3Bsb3Qgb2YgdGhlIG9pbCBkYXRhDQphdXRvcGxvdChvaWwpDQoNCiMgQ3JlYXRlIGEgbGFnIHBsb3Qgb2YgdGhlIG9pbCBkYXRhDQpnZ2xhZ3Bsb3Qob2lsKQ0KDQojIENyZWF0ZSBhbiBBQ0YgcGxvdCBvZiB0aGUgb2lsIGRhdGENCmdnQWNmKG9pbCkNCmBgYA0KIyMjIEF1dG9jb3JyZWxhdGlvbiBvZiBzZWFzb25hbCBhbmQgY3ljbGljIHRpbWUgc2VyaWVzDQoNCldoZW4gZGF0YSBhcmUgZWl0aGVyIHNlYXNvbmFsIG9yIGN5Y2xpYywgdGhlIEFDRiB3aWxsIHBlYWsgYXJvdW5kIHRoZSBzZWFzb25hbCBsYWdzIG9yIGF0IHRoZSBhdmVyYWdlIGN5Y2xlIGxlbmd0aC4NCg0KWW91IHdpbGwgaW52ZXN0aWdhdGUgdGhpcyBwaGVub21lbm9uIGJ5IHBsb3R0aW5nIHRoZSBhbm51YWwgc3Vuc3BvdCBzZXJpZXMgKHdoaWNoIGZvbGxvd3MgdGhlIHNvbGFyIGN5Y2xlIG9mIGFwcHJveGltYXRlbHkgMTAtMTEgeWVhcnMpIGluIHN1bnNwb3QueWVhciBhbmQgdGhlIGRhaWx5IHRyYWZmaWMgdG8gdGhlIEh5bmRzaWdodCBibG9nICh3aGljaCBmb2xsb3dzIGEgNy1kYXkgd2Vla2x5IHBhdHRlcm4pIGluIGh5bmRzaWdodC4NCmBgYHtyfQ0KIyBQbG90IHRoZSBhbm51YWwgc3Vuc3BvdCBudW1iZXJzDQphdXRvcGxvdChzdW5zcG90LnllYXIpDQpnZ0FjZihzdW5zcG90LnllYXIpDQoNCiMgU2F2ZSB0aGUgbGFnIGNvcnJlc3BvbmRpbmcgdG8gbWF4aW11bSBhdXRvY29ycmVsYXRpb24NCm1heGxhZ19zdW5zcG90IDwtIDENCg0KIyBQbG90IHRoZSB0cmFmZmljIG9uIHRoZSBIeW5kc2lnaHQgYmxvZw0KYXV0b3Bsb3QoaHluZHNpZ2h0KQ0KZ2dBY2YoaHluZHNpZ2h0KQ0KYGBgDQojIyBXaGl0ZSBub2lzZQ0KDQojIyMgU3RvY2sgcHJpY2VzIGFuZCB3aGl0ZSBub2lzZQ0KDQpXaGl0ZSBub2lzZSBpcyBhIHRlcm0gdGhhdCBkZXNjcmliZXMgcHVyZWx5IHJhbmRvbSBkYXRhLiBZb3UgY2FuIGNvbmR1Y3QgYSBManVuZy1Cb3ggdGVzdCB1c2luZyB0aGUgZnVuY3Rpb24gYmVsb3cgdG8gY29uZmlybSB0aGUgcmFuZG9tbmVzcyBvZiBhIHNlcmllczsgYSBwLXZhbHVlIGdyZWF0ZXIgdGhhbiAwLjA1IHN1Z2dlc3RzIHRoYXQgdGhlIGRhdGEgYXJlIG5vdCBzaWduaWZpY2FudGx5IGRpZmZlcmVudCBmcm9tIHdoaXRlIG5vaXNlLg0KDQogICAgQm94LnRlc3QocGlncywgbGFnID0gMjQsIGZpdGRmID0gMCwgdHlwZSA9ICJManVuZyIpDQogICAgDQpUaGVyZSBpcyBhIHdlbGwta25vd24gcmVzdWx0IGluIGVjb25vbWljcyBjYWxsZWQgdGhlICJFZmZpY2llbnQgTWFya2V0IEh5cG90aGVzaXMiIHRoYXQgc3RhdGVzIHRoYXQgYXNzZXQgcHJpY2VzIHJlZmxlY3QgYWxsIGF2YWlsYWJsZSBpbmZvcm1hdGlvbi4gQSBjb25zZXF1ZW5jZSBvZiB0aGlzIGlzIHRoYXQgdGhlIGRhaWx5IGNoYW5nZXMgaW4gc3RvY2sgcHJpY2VzIHNob3VsZCBiZWhhdmUgbGlrZSB3aGl0ZSBub2lzZSAoaWdub3JpbmcgZGl2aWRlbmRzLCBpbnRlcmVzdCByYXRlcyBhbmQgdHJhbnNhY3Rpb24gY29zdHMpLiBUaGUgY29uc2VxdWVuY2UgZm9yIGZvcmVjYXN0ZXJzIGlzIHRoYXQgdGhlIGJlc3QgZm9yZWNhc3Qgb2YgdGhlIGZ1dHVyZSBwcmljZSBpcyB0aGUgY3VycmVudCBwcmljZS4NCg0KWW91IGNhbiB0ZXN0IHRoaXMgaHlwb3RoZXNpcyBieSBsb29raW5nIGF0IHRoZSBnb29nIHNlcmllcywgd2hpY2ggY29udGFpbnMgdGhlIGNsb3Npbmcgc3RvY2sgcHJpY2UgZm9yIEdvb2dsZSBvdmVyIDEwMDAgdHJhZGluZyBkYXlzIGVuZGluZyBvbiBGZWJydWFyeSAxMywgMjAxNy4gDQoNCmBgYHtyfQ0KIyBQbG90IHRoZSBvcmlnaW5hbCBzZXJpZXMNCmF1dG9wbG90KGdvb2cpDQoNCiMgUGxvdCB0aGUgZGlmZmVyZW5jZWQgc2VyaWVzDQphdXRvcGxvdChkaWZmKGdvb2cpKQ0KDQojIEFDRiBvZiB0aGUgZGlmZmVyZW5jZWQgc2VyaWVzDQpnZ0FjZihkaWZmKGdvb2cpKQ0KDQojIExqdW5nLUJveCB0ZXN0IG9mIHRoZSBkaWZmZXJlbmNlZCBzZXJpZXMNCkJveC50ZXN0KGRpZmYoZ29vZyksIGxhZyA9IDEwLCB0eXBlID0gIkxqdW5nIikNCmBgYA0KWW91IGhhdmUgc2VlbiB0aGF0IHRoZSBManVuZy1Cb3ggdGVzdCB3YXMgbm90IHNpZ25pZmljYW50LCBzbyBkYWlseSBjaGFuZ2VzIGluIHRoZSBHb29nbGUgc3RvY2sgcHJpY2UgbG9vayBsaWtlIHdoaXRlIG5vaXNlLg0KDQojIEJlbmNobWFyayBtZXRob2RzIGFuZCBmb3JlY2FzdCBhY2N1cmFjeQ0KDQojIyBGb3JlY2FzdHMgYW5kIHBvdGVudGlhbCBmdXR1cmVzDQoNCiMjIyBOYWl2ZSBmb3JlY2FzdGluZyBtZXRob2RzDQoNCkEgZm9yZWNhc3QgaXMgdGhlIG1lYW4gb3IgbWVkaWFuIG9mIHNpbXVsYXRlZCBmdXR1cmVzIG9mIGEgdGltZSBzZXJpZXMuDQoNClRoZSB2ZXJ5IHNpbXBsZXN0IGZvcmVjYXN0aW5nIG1ldGhvZCBpcyB0byB1c2UgdGhlIG1vc3QgcmVjZW50IG9ic2VydmF0aW9uOyB0aGlzIGlzIGNhbGxlZCBhIG5haXZlIGZvcmVjYXN0IGFuZCBjYW4gYmUgaW1wbGVtZW50ZWQgaW4gYSBuYW1lc2FrZSBmdW5jdGlvbi4gVGhpcyBpcyB0aGUgYmVzdCB0aGF0IGNhbiBiZSBkb25lIGZvciBtYW55IHRpbWUgc2VyaWVzIGluY2x1ZGluZyBtb3N0IHN0b2NrIHByaWNlIGRhdGEsIGFuZCBldmVuIGlmIGl0IGlzIG5vdCBhIGdvb2QgZm9yZWNhc3RpbmcgbWV0aG9kLCBpdCBwcm92aWRlcyBhIHVzZWZ1bCBiZW5jaG1hcmsgZm9yIG90aGVyIGZvcmVjYXN0aW5nIG1ldGhvZHMuDQoNCkZvciBzZWFzb25hbCBkYXRhLCBhIHJlbGF0ZWQgaWRlYSBpcyB0byB1c2UgdGhlIGNvcnJlc3BvbmRpbmcgc2Vhc29uIGZyb20gdGhlIGxhc3QgeWVhciBvZiBkYXRhLiBGb3IgZXhhbXBsZSwgaWYgeW91IHdhbnQgdG8gZm9yZWNhc3QgdGhlIHNhbGVzIHZvbHVtZSBmb3IgbmV4dCBNYXJjaCwgeW91IHdvdWxkIHVzZSB0aGUgc2FsZXMgdm9sdW1lIGZyb20gdGhlIHByZXZpb3VzIE1hcmNoLiBUaGlzIGlzIGltcGxlbWVudGVkIGluIHRoZSBzbmFpdmUoKSBmdW5jdGlvbiwgbWVhbmluZywgc2Vhc29uYWwgbmFpdmUuDQoNCkZvciBib3RoIGZvcmVjYXN0aW5nIG1ldGhvZHMsIHlvdSBjYW4gc2V0IHRoZSBzZWNvbmQgYXJndW1lbnQgaCwgd2hpY2ggc3BlY2lmaWVzIHRoZSBudW1iZXIgb2YgdmFsdWVzIHlvdSB3YW50IHRvIGZvcmVjYXN0OyBhcyBzaG93biBpbiB0aGUgY29kZSBiZWxvdywgdGhleSBoYXZlIGRpZmZlcmVudCBkZWZhdWx0IHZhbHVlcy4gVGhlIHJlc3VsdGluZyBvdXRwdXQgaXMgYW4gb2JqZWN0IG9mIGNsYXNzIGZvcmVjYXN0LiBUaGlzIGlzIHRoZSBjb3JlIGNsYXNzIG9mIG9iamVjdHMgaW4gdGhlIGZvcmVjYXN0IHBhY2thZ2UsIGFuZCB0aGVyZSBhcmUgbWFueSBmdW5jdGlvbnMgZm9yIGRlYWxpbmcgd2l0aCB0aGVtIGluY2x1ZGluZyBzdW1tYXJ5KCkgYW5kIGF1dG9wbG90KCkNCg0KICAgIG5haXZlKHksIGggPSAxMCkNCiAgICBzbmFpdmUoeSwgaCA9IDIgKiBmcmVxdWVuY3koeCkpDQoNCmBgYHtyfQ0KIyBVc2UgbmFpdmUoKSB0byBmb3JlY2FzdCB0aGUgZ29vZyBzZXJpZXMNCmZjZ29vZyA8LSBuYWl2ZShnb29nLCBoID0gMjApDQoNCiMgUGxvdCBhbmQgc3VtbWFyaXplIHRoZSBmb3JlY2FzdHMNCmF1dG9wbG90KGZjZ29vZykNCnN1bW1hcnkoZmNnb29nKQ0KDQojIFVzZSBzbmFpdmUoKSB0byBmb3JlY2FzdCB0aGUgYXVzYmVlciBzZXJpZXMNCmZjYmVlciA8LSBzbmFpdmUoYXVzYmVlciwgaCA9IDE2KQ0KDQojIFBsb3QgYW5kIHN1bW1hcml6ZSB0aGUgZm9yZWNhc3RzDQphdXRvcGxvdChmY2JlZXIpDQpzdW1tYXJ5KGZjYmVlcikNCmBgYA0KIyMgRml0dGVkIHZhbHVlcyBhbmQgcmVzaWR1YWxzDQoNCiMjIyBDaGVja2luZyB0aW1lIHNlcmllcyByZXNpZHVhbHMNCg0KV2hlbiBhcHBseWluZyBhIGZvcmVjYXN0aW5nIG1ldGhvZCwgaXQgaXMgaW1wb3J0YW50IHRvIGFsd2F5cyBjaGVjayB0aGF0IHRoZSByZXNpZHVhbHMgYXJlIHdlbGwtYmVoYXZlZCAoaS5lLiwgbm8gb3V0bGllcnMgb3IgcGF0dGVybnMpIGFuZCByZXNlbWJsZSB3aGl0ZSBub2lzZS4gVGhlIHByZWRpY3Rpb24gaW50ZXJ2YWxzIGFyZSBjb21wdXRlZCBhc3N1bWluZyB0aGF0IHRoZSByZXNpZHVhbHMgYXJlIGFsc28gbm9ybWFsbHkgZGlzdHJpYnV0ZWQuIFlvdSBjYW4gdXNlIHRoZSBjaGVja3Jlc2lkdWFscygpIGZ1bmN0aW9uIHRvIHZlcmlmeSB0aGVzZSBjaGFyYWN0ZXJpc3RpY3M7IGl0IHdpbGwgZ2l2ZSB0aGUgcmVzdWx0cyBvZiBhIExqdW5nLUJveCB0ZXN0Lg0KDQpJbiB0aGlzIGV4ZXJjaXNlLCB5b3Ugd2lsbCB0ZXN0IHRoZSBhYm92ZSBmdW5jdGlvbnMgb24gdGhlIGZvcmVjYXN0cyBlcXVpdmFsZW50IHRvIHdoYXQgeW91IHByb2R1Y2VkIGluIHRoZSBwcmV2aW91cyBleGVyY2lzZSAoZmNnb29nIG9idGFpbmVkIGFmdGVyIGFwcGx5aW5nIG5haXZlKCkgdG8gZ29vZywgYW5kIGZjYmVlciBvYnRhaW5lZCBhZnRlciBhcHBseWluZyBzbmFpdmUoKSB0byBhdXNiZWVyKS4NCg0KYGBge3J9DQojIENoZWNrIHRoZSByZXNpZHVhbHMgZnJvbSB0aGUgbmFpdmUgZm9yZWNhc3RzIGFwcGxpZWQgdG8gdGhlIGdvb2cgc2VyaWVzDQpnb29nICU+JSBuYWl2ZSgpICU+JSBjaGVja3Jlc2lkdWFscygpDQoNCiMgRG8gdGhleSBsb29rIGxpa2Ugd2hpdGUgbm9pc2UgKFRSVUUgb3IgRkFMU0UpDQpnb29nd24gPC0gVFJVRQ0KDQojIENoZWNrIHRoZSByZXNpZHVhbHMgZnJvbSB0aGUgc2Vhc29uYWwgbmFpdmUgZm9yZWNhc3RzIGFwcGxpZWQgdG8gdGhlIGF1c2JlZXIgc2VyaWVzDQphdXNiZWVyICU+JSBzbmFpdmUoKSAlPiUgY2hlY2tyZXNpZHVhbHMoKQ0KDQojIERvIHRoZXkgbG9vayBsaWtlIHdoaXRlIG5vaXNlIChUUlVFIG9yIEZBTFNFKQ0KYmVlcnduIDwtIEZBTFNFDQpgYGANCiMjIFRyYWluaW5nIGFuZCB0ZXN0IHNldHMNCg0KDQojIyMgRXZhbHVhdGluZyBmb3JlY2FzdCBhY2N1cmFjeSBvZiBub24tc2Vhc29uYWwgbWV0aG9kcw0KDQpJbiBkYXRhIHNjaWVuY2UsIGEgdHJhaW5pbmcgc2V0IGlzIGEgZGF0YSBzZXQgdGhhdCBpcyB1c2VkIHRvIGRpc2NvdmVyIHBvc3NpYmxlIHJlbGF0aW9uc2hpcHMuIEEgdGVzdCBzZXQgaXMgYSBkYXRhIHNldCB0aGF0IGlzIHVzZWQgdG8gdmVyaWZ5IHRoZSBzdHJlbmd0aCBvZiB0aGVzZSBwb3RlbnRpYWwgcmVsYXRpb25zaGlwcy4gV2hlbiB5b3Ugc2VwYXJhdGUgYSBkYXRhIHNldCBpbnRvIHRoZXNlIHBhcnRzLCB5b3UgZ2VuZXJhbGx5IGFsbG9jYXRlIG1vcmUgb2YgdGhlIGRhdGEgZm9yIHRyYWluaW5nLCBhbmQgbGVzcyBmb3IgdGVzdGluZy4NCg0KT25lIGZ1bmN0aW9uIHRoYXQgY2FuIGJlIHVzZWQgdG8gY3JlYXRlIHRyYWluaW5nIGFuZCB0ZXN0IHNldHMgaXMgc3Vic2V0LnRzKCksIHdoaWNoIHJldHVybnMgYSBzdWJzZXQgb2YgYSB0aW1lIHNlcmllcyB3aGVyZSB0aGUgb3B0aW9uYWwgc3RhcnQgYW5kIGVuZCBhcmd1bWVudHMgYXJlIHNwZWNpZmllZCB1c2luZyBpbmRleCB2YWx1ZXMuDQoNCiAgICAjIHggaXMgYSBudW1lcmljYWwgdmVjdG9yIG9yIHRpbWUgc2VyaWVzDQogICAgIyBUbyBzdWJzZXQgb2JzZXJ2YXRpb25zIGZyb20gMTAxIHRvIDUwMA0KICAgIHRyYWluIDwtIHN1YnNldCh4LCBzdGFydCA9IDEwMSwgZW5kID0gNTAwLCAuLi4pDQogICAgYA0KICAgICMgVG8gc3Vic2V0IHRoZSBmaXJzdCA1MDAgb2JzZXJ2YXRpb25zDQogICAgdHJhaW4gPC0gc3Vic2V0KHgsIGVuZCA9IDUwMCwgLi4uKQ0KDQpBbm90aGVyIGZ1bmN0aW9uLCBhY2N1cmFjeSgpLCBjb21wdXRlcyB2YXJpb3VzIGZvcmVjYXN0IGFjY3VyYWN5IHN0YXRpc3RpY3MgZ2l2ZW4gdGhlIGZvcmVjYXN0cyBhbmQgdGhlIGNvcnJlc3BvbmRpbmcgYWN0dWFsIG9ic2VydmF0aW9ucy4gSXQgaXMgc21hcnQgZW5vdWdoIHRvIGZpbmQgdGhlIHJlbGV2YW50IG9ic2VydmF0aW9ucyBpZiB5b3UgZ2l2ZSBpdCBtb3JlIHRoYW4gdGhlIG9uZXMgeW91IGFyZSBmb3JlY2FzdGluZy4NCg0KICAgID4gIyBmIGlzIGFuIG9iamVjdCBvZiBjbGFzcyAiZm9yZWNhc3QiDQogICAgPiAjIHggaXMgYSBudW1lcmljYWwgdmVjdG9yIG9yIHRpbWUgc2VyaWVzDQogICAgPiBhY2N1cmFjeShmLCB4LCAuLi4pDQogICAgDQpUaGUgYWNjdXJhY3kgbWVhc3VyZXMgcHJvdmlkZWQgaW5jbHVkZSByb290IG1lYW4gc3F1YXJlZCBlcnJvciAoUk1TRSkgd2hpY2ggaXMgdGhlIHNxdWFyZSByb290IG9mIHRoZSBtZWFuIHNxdWFyZWQgZXJyb3IgKE1TRSkuIE1pbmltaXppbmcgUk1TRSwgd2hpY2ggY29ycmVzcG9uZHMgd2l0aCBpbmNyZWFzaW5nIGFjY3VyYWN5LCBpcyB0aGUgc2FtZSBhcyBtaW5pbWl6aW5nIE1TRS4NCg0KVGhlIHByZS1sb2FkZWQgdGltZSBzZXJpZXMgZ29sZCBjb21wcmlzZXMgZGFpbHkgZ29sZCBwcmljZXMgZm9yIDExMDggZGF5cy4gSGVyZSwgeW91J2xsIHVzZSB0aGUgZmlyc3QgMTAwMCBkYXlzIGFzIGEgdHJhaW5pbmcgc2V0LCBhbmQgY29tcHV0ZSBmb3JlY2FzdHMgZm9yIHRoZSByZW1haW5pbmcgMTA4IGRheXMuIFRoZXNlIHdpbGwgYmUgY29tcGFyZWQgdG8gdGhlIGFjdHVhbCB2YWx1ZXMgZm9yIHRoZXNlIGRheXMgdXNpbmcgdGhlIHNpbXBsZSBmb3JjYXN0aW5nIGZ1bmN0aW9ucyBuYWl2ZSgpLCB3aGljaCB5b3UgdXNlZCBlYXJsaWVyIGluIHRoaXMgY2hhcHRlciwgYW5kIG1lYW5mKCksIHdoaWNoIGdpdmVzIGZvcmVjYXN0cyBlcXVhbCB0byB0aGUgbWVhbiBvZiBhbGwgb2JzZXJ2YXRpb25zLiBZb3UnbGwgaGF2ZSB0byBzcGVjaWZ5IHRoZSBrZXl3b3JkIGggKHdoaWNoIHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIHZhbHVlcyB5b3Ugd2FudCB0byBmb3JlY2FzdCkgZm9yIGJvdGguDQoNCmBgYHtyfQ0KIyBDcmVhdGUgdGhlIHRyYWluaW5nIGRhdGEgYXMgdHJhaW4NCnRyYWluIDwtIHN1YnNldChnb2xkLCBlbmQgPSAxMDAwKQ0KDQojIENvbXB1dGUgbmFpdmUgZm9yZWNhc3RzIGFuZCBzYXZlIHRvIG5haXZlX2ZjDQpuYWl2ZV9mYyA8LSBuYWl2ZSh0cmFpbiwgaCA9IDEwOCkNCg0KIyBDb21wdXRlIG1lYW4gZm9yZWNhc3RzIGFuZCBzYXZlIHRvIG1lYW5fZmMNCm1lYW5fZmMgPC0gbWVhbmYodHJhaW4sIGggPSAxMDgpDQoNCiMgVXNlIGFjY3VyYWN5KCkgdG8gY29tcHV0ZSBSTVNFIHN0YXRpc3RpY3MNCmFjY3VyYWN5KG5haXZlX2ZjLCBnb2xkKQ0KYWNjdXJhY3kobWVhbl9mYywgZ29sZCkNCg0KIyBBc3NpZ24gb25lIG9mIHRoZSB0d28gZm9yZWNhc3RzIGFzIGJlc3Rmb3JlY2FzdHMNCmJlc3Rmb3JlY2FzdHMgPC0gbmFpdmVfZmMNCmBgYA0KIyMjIEV2YWx1YXRpbmcgZm9yZWNhc3QgYWNjdXJhY3kgb2Ygc2Vhc29uYWwgbWV0aG9kcw0KDQpUaGUgd2luZG93KCkgZnVuY3Rpb24gc3BlY2lmaWVzIHRoZSBzdGFydCBhbmQgZW5kIG9mIGEgdGltZSBzZXJpZXMgdXNpbmcgdGhlIHJlbGV2YW50IHRpbWVzIHJhdGhlciB0aGFuIHRoZSBpbmRleCB2YWx1ZXMuIEVpdGhlciBvZiB0aG9zZSB0d28gYXJndW1lbnRzIGNhbiBiZSBmb3JtYXR0ZWQgYXMgYSB2ZWN0b3IgbGlrZSBjKHllYXIsIHBlcmlvZCkgd2hpY2ggeW91IGhhdmUgYWxzbyBwcmV2aW91c2x5IHVzZWQgYXMgYW4gYXJndW1lbnQgZm9yIHRzKCkuIEFnYWluLCBwZXJpb2QgcmVmZXJzIHRvIHF1YXJ0ZXIgaGVyZS4NCiANCkhlcmUsIHlvdSB3aWxsIHVzZSB0aGUgTWVsYm91cm5lIHF1YXJ0ZXJseSB2aXNpdG9yIG51bWJlcnMgKHZuWywgIk1lbGJvdXJuZSJdKSB0byBjcmVhdGUgdGhyZWUgZGlmZmVyZW50IHRyYWluaW5nIHNldHMsIG9taXR0aW5nIHRoZSBsYXN0IDEsIDIgYW5kIDMgeWVhcnMsIHJlc3BlY3RpdmVseS4gSW5zcGVjdCB0aGUgcHJlLWxvYWRlZCB2biBkYXRhIGluIHlvdXIgY29uc29sZSBiZWZvcmUgYmVnaW5uaW5nIHRoZSBleGVyY2lzZTsgdGhpcyB3aWxsIGhlbHAgeW91IGRldGVybWluZSB0aGUgY29ycmVjdCB2YWx1ZSB0byB1c2UgZm9yIHRoZSBrZXl3b3JkIGggKHdoaWNoIHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIHZhbHVlcyB5b3Ugd2FudCB0byBmb3JlY2FzdCkgaW4geW91ciBmb3JlY2FzdGluZyBtZXRob2RzLg0KDQpUaGVuIGZvciBlYWNoIHRyYWluaW5nIHNldCwgY29tcHV0ZSB0aGUgbmV4dCB5ZWFyIG9mIGRhdGEsIGFuZCBmaW5hbGx5IGNvbXBhcmUgdGhlIG1lYW4gYWJzb2x1dGUgcGVyY2VudGFnZSBlcnJvciAoTUFQRSkgb2YgdGhlIGZvcmVjYXN0cyB1c2luZyBhY2N1cmFjeSgpLiBXaHkgZG8geW91IHRoaW5rIHRoYXQgdGhlIE1BUEUgdmFyeSBzbyBtdWNoPw0KYGBge3J9DQp2biA8LSByZWFkUkRTKCJ2bi5SRFMiKQ0Kdm4gPC0gdHModm5bLCBjKDI6OCldLCBzdGFydCA9IGMoMTk5OCwgMSksIGZyZXF1ZW5jeSA9IDQpDQojIENyZWF0ZSB0aHJlZSB0cmFpbmluZyBzZXJpZXMgb21pdHRpbmcgdGhlIGxhc3QgMSwgMiwgYW5kIDMgeWVhcnMNCnRyYWluMSA8LSB3aW5kb3codm5bLCAiTWVsYm91cm5lIl0sIGVuZCA9IGMoMjAxNCwgNCkpDQp0cmFpbjIgPC0gd2luZG93KHZuWywgIk1lbGJvdXJuZSJdLCBlbmQgPSBjKDIwMTMsIDQpKQ0KdHJhaW4zIDwtIHdpbmRvdyh2blssICJNZWxib3VybmUiXSwgZW5kID0gYygyMDEyLCA0KSkNCg0KIyBQcm9kdWNlIGZvcmVjYXN0cyB1c2luZyBzbmFpdmUoKQ0KZmMxIDwtIHNuYWl2ZSh0cmFpbjEsIGggPSA0KQ0KZmMyIDwtIHNuYWl2ZSh0cmFpbjIsIGggPSA0KQ0KZmMzIDwtIHNuYWl2ZSh0cmFpbjMsIGggPSA0KQ0KDQojIFVzZSBhY2N1cmFjeSgpIHRvIGNvbXBhcmUgdGhlIE1BUEUgb2YgZWFjaCBzZXJpZXMNCmFjY3VyYWN5KGZjMSwgdm5bLCAiTWVsYm91cm5lIl0pWyJUZXN0IHNldCIsICJNQVBFIl0NCmFjY3VyYWN5KGZjMiwgdm5bLCAiTWVsYm91cm5lIl0pWyJUZXN0IHNldCIsICJNQVBFIl0NCmFjY3VyYWN5KGZjMywgdm5bLCAiTWVsYm91cm5lIl0pWyJUZXN0IHNldCIsICJNQVBFIl0NCmBgYA0KIyMjIFdoZW4gZG9lcyBhIG1vZGVsIGZvcmVjYXN0IHdlbGw/DQoNCkEgZ29vZCBtb2RlbCBmb3JlY2FzdHMgd2VsbCAoc28gaGFzIGxvdyBSTVNFIG9uIHRoZSB0ZXN0IHNldCkgYW5kIHVzZXMgYWxsIGF2YWlsYWJsZSBpbmZvcm1hdGlvbiBpbiB0aGUgdHJhaW5pbmcgZGF0YSAoc28gaGFzIHdoaXRlIG5vaXNlIHJlc2lkdWFscykuDQoNCiMjIFRpbWUgc2VyaWVzIGNyb3NzLXZhbGlkYXRpb24NCg0KIyMjIFVzaW5nIHRzQ1YoKSBmb3IgdGltZSBzZXJpZXMgY3Jvc3MtdmFsaWRhdGlvbg0KDQpUaGUgdHNDVigpIGZ1bmN0aW9uIGNvbXB1dGVzIHRpbWUgc2VyaWVzIGNyb3NzLXZhbGlkYXRpb24gZXJyb3JzLiBJdCByZXF1aXJlcyB5b3UgdG8gc3BlY2lmeSB0aGUgdGltZSBzZXJpZXMsIHRoZSBmb3JlY2FzdCBtZXRob2QsIGFuZCB0aGUgZm9yZWNhc3QgaG9yaXpvbi4NCg0KICAgIGUgPSB0c0NWKG9pbCwgZm9yZWNhc3RmdW5jdGlvbiA9IG5haXZlLCBoID0gMSkNCiAgICANCkhlcmUsIHlvdSB3aWxsIHVzZSB0c0NWKCkgdG8gY29tcHV0ZSBhbmQgcGxvdCB0aGUgTVNFIHZhbHVlcyBmb3IgdXAgdG8gOCBzdGVwcyBhaGVhZCwgYWxvbmcgd2l0aCB0aGUgbmFpdmUoKSBtZXRob2QgYXBwbGllZCB0byB0aGUgZ29vZyBkYXRhLiBUDQoNCmBgYHtyfQ0KIyBDb21wdXRlIGNyb3NzLXZhbGlkYXRlZCBlcnJvcnMgZm9yIHVwIHRvIDggc3RlcHMgYWhlYWQNCmUgPC0gdHNDVihnb29nLCBmb3JlY2FzdGZ1bmN0aW9uID0gbmFpdmUsIGggPSA4KQ0KDQojIENvbXB1dGUgdGhlIE1TRSB2YWx1ZXMgYW5kIHJlbW92ZSBtaXNzaW5nIHZhbHVlcw0KbXNlIDwtIGNvbE1lYW5zKGVeMiwgbmEucm0gPSBUUlVFKQ0KDQojIFBsb3QgdGhlIE1TRSB2YWx1ZXMgYWdhaW5zdCB0aGUgZm9yZWNhc3QgaG9yaXpvbg0KZGF0YS5mcmFtZShoID0gMTo4LCBNU0UgPSBtc2UpICU+JQ0KICBnZ3Bsb3QoYWVzKHggPSBoLCB5ID0gTVNFKSkgKyBnZW9tX3BvaW50KCkNCmBgYA0KYGBge3J9DQpkYXRhLmZyYW1lKGggPSAxOjgsIE1TRSA9IG1zZSkNCmBgYA0KIyBFeHBvbmVudGlhbCBzbW9vdGhpbmcNCg0KIyMgRXhwb25lbnRpYWxseSB3ZWlnaHRlZCBmb3JlY2FzdHMNCg0KIyMjIFNpbXBsZSBleHBvbmVudGlhbCBzbW9vdGhpbmcNCg0KVGhlIHNlcygpIGZ1bmN0aW9uIHByb2R1Y2VzIGZvcmVjYXN0cyBvYnRhaW5lZCB1c2luZyBzaW1wbGUgZXhwb25lbnRpYWwgc21vb3RoaW5nIChTRVMpLiBUaGUgcGFyYW1ldGVycyBhcmUgZXN0aW1hdGVkIHVzaW5nIGxlYXN0IHNxdWFyZXMgZXN0aW1hdGlvbi4gQWxsIHlvdSBuZWVkIHRvIHNwZWNpZnkgaXMgdGhlIHRpbWUgc2VyaWVzIGFuZCB0aGUgZm9yZWNhc3QgaG9yaXpvbjsgdGhlIGRlZmF1bHQgZm9yZWNhc3QgdGltZSBpcyBoID0gMTAgeWVhcnMuDQoNCiAgICA+IGFyZ3Moc2VzKQ0KICAgIGZ1bmN0aW9uICh5LCBoID0gMTAsIC4uLikNCiAgICANCiAgICA+IGZjIDwtIHNlcyhvaWxkYXRhLCBoID0gNSkNCiAgICA+IHN1bW1hcnkoZmMpDQoNCllvdSB3aWxsIGFsc28gdXNlIHN1bW1hcnkoKSBhbmQgZml0dGVkKCksIGFsb25nIHdpdGggYXV0b2xheWVyKCkgZm9yIHRoZSBmaXJzdCB0aW1lLCB3aGljaCBpcyBsaWtlIGF1dG9wbG90KCkgYnV0IGl0IGFkZHMgYSAibGF5ZXIiIHRvIGEgcGxvdCByYXRoZXIgdGhhbiBjcmVhdGluZyBhIG5ldyBwbG90Lg0KDQpIZXJlLCB5b3Ugd2lsbCBhcHBseSB0aGVzZSBmdW5jdGlvbnMgdG8gbWFyYXRob24sIHRoZSBhbm51YWwgd2lubmluZyB0aW1lcyBpbiB0aGUgQm9zdG9uIG1hcmF0aG9uIGZyb20gMTg5Ny0yMDE2LiBUaGUgZGF0YSBhcmUgYXZhaWxhYmxlIGluIHlvdXIgd29ya3NwYWNlLg0KDQpgYGB7cn0NCiMgVXNlIHNlcygpIHRvIGZvcmVjYXN0IHRoZSBuZXh0IDEwIHllYXJzIG9mIHdpbm5pbmcgdGltZXMNCmZjIDwtIHNlcyhtYXJhdGhvbiwgaCA9IDEwKQ0KDQojIFVzZSBzdW1tYXJ5KCkgdG8gc2VlIHRoZSBtb2RlbCBwYXJhbWV0ZXJzDQpzdW1tYXJ5KGZjKQ0KDQojIFVzZSBhdXRvcGxvdCgpIHRvIHBsb3QgdGhlIGZvcmVjYXN0cw0KYXV0b3Bsb3QoZmMpDQoNCiMgQWRkIHRoZSBvbmUtc3RlcCBmb3JlY2FzdHMgZm9yIHRoZSB0cmFpbmluZyBkYXRhIHRvIHRoZSBwbG90DQphdXRvcGxvdChmYykgKyBhdXRvbGF5ZXIoZml0dGVkKGZjKSkNCmBgYA0KIyMjIFNFUyB2cyBuYWl2ZQ0KDQpJbiB0aGlzIGV4ZXJjaXNlLCB5b3Ugd2lsbCBhcHBseSB5b3VyIGtub3dsZWRnZSBvZiB0cmFpbmluZyBhbmQgdGVzdCBzZXRzLCB0aGUgc3Vic2V0KCkgZnVuY3Rpb24sIGFuZCB0aGUgYWNjdXJhY3koKSBmdW5jdGlvbiwgYWxsIG9mIHdoaWNoIHlvdSBsZWFybmVkIGluIENoYXB0ZXIgMiwgdG8gY29tcGFyZSBTRVMgYW5kIG5haXZlIGZvcmVjYXN0cyBmb3IgdGhlIG1hcmF0aG9uIGRhdGEuDQoNCllvdSBkaWQgc29tZXRoaW5nIHZlcnkgc2ltaWxhciB0byBjb21wYXJlIHRoZSBuYWl2ZSBhbmQgbWVhbiBmb3JlY2FzdHMgaW4gYW4gZWFybGllciBleGVyY2lzZSAiRXZhbHVhdGluZyBmb3JlY2FzdCBhY2N1cmFjeSBvZiBub24tc2Vhc29uYWwgbWV0aG9kcyIuDQoNCkxldCdzIHJldmlldyB0aGUgcHJvY2VzczoNCg0KMS4gRmlyc3QsIGltcG9ydCBhbmQgbG9hZCB5b3VyIGRhdGEuIERldGVybWluZSBob3cgbXVjaCBvZiB5b3VyIGRhdGEgeW91IHdhbnQgdG8gYWxsb2NhdGUgdG8gdHJhaW5pbmcsIGFuZCBob3cgbXVjaCB0byB0ZXN0aW5nOyB0aGUgc2V0cyBzaG91bGQgbm90IG92ZXJsYXAuDQoyLiBTdWJzZXQgdGhlIGRhdGEgdG8gY3JlYXRlIGEgdHJhaW5pbmcgc2V0LCB3aGljaCB5b3Ugd2lsbCB1c2UgYXMgYW4gYXJndW1lbnQgaW4geW91ciBmb3JlY2FzdGluZyBmdW5jdGlvbihzKS4gT3B0aW9uYWxseSwgeW91IGNhbiBhbHNvIGNyZWF0ZSBhIHRlc3Qgc2V0IHRvIHVzZSBsYXRlci4NCjMuIENvbXB1dGUgZm9yZWNhc3RzIG9mIHRoZSB0cmFpbmluZyBzZXQgdXNpbmcgd2hpY2hldmVyIGZvcmVjYXN0aW5nIGZ1bmN0aW9uKHMpIHlvdSBjaG9vc2UsIGFuZCBzZXQgaCBlcXVhbCB0byB0aGUgbnVtYmVyIG9mIHZhbHVlcyB5b3Ugd2FudCB0byBmb3JlY2FzdCwgd2hpY2ggaXMgYWxzbyB0aGUgbGVuZ3RoIG9mIHRoZSB0ZXN0IHNldC4NCjQuIFRvIHZpZXcgdGhlIHJlc3VsdHMsIHVzZSB0aGUgYWNjdXJhY3koKSBmdW5jdGlvbiB3aXRoIHRoZSBmb3JlY2FzdCBhcyB0aGUgZmlyc3QgYXJndW1lbnQgYW5kIG9yaWdpbmFsIGRhdGEgKG9yIHRlc3Qgc2V0KSBhcyB0aGUgc2Vjb25kLg0KNS4gUGljayBhIG1lYXN1cmUgaW4gdGhlIG91dHB1dCwgc3VjaCBhcyBSTVNFIG9yIE1BRSwgdG8gZXZhbHVhdGUgdGhlIGZvcmVjYXN0KHMpOyBhIHNtYWxsZXIgZXJyb3IgaW5kaWNhdGVzIGhpZ2hlciBhY2N1cmFjeS4NCg0KYGBge3J9DQojIENyZWF0ZSBhIHRyYWluaW5nIHNldCB1c2luZyBzdWJzZXQoKQ0KdHJhaW4gPC0gc3Vic2V0KG1hcmF0aG9uLCBlbmQgPSBsZW5ndGgobWFyYXRob24pIC0gMjApDQoNCiMgQ29tcHV0ZSBTRVMgYW5kIG5haXZlIGZvcmVjYXN0cywgc2F2ZSB0byBmY3NlcyBhbmQgZmNuYWl2ZQ0KZmNzZXMgPC0gc2VzKHRyYWluLCBoID0gMjApDQpmY25haXZlIDwtIG5haXZlKHRyYWluLCBoID0gMjApDQoNCiMgQ2FsY3VsYXRlIGZvcmVjYXN0IGFjY3VyYWN5IG1lYXN1cmVzDQphY2N1cmFjeShmY3NlcywgIG1hcmF0aG9uKQ0KYWNjdXJhY3koZmNuYWl2ZSwgIG1hcmF0aG9uKQ0KYGBgDQojIyBFeHBvbmVudGlhbCBzbW9vdGhpbmcgbWV0aG9kcyB3aXRoIHRyZW5kDQoNCiMjIyBIb2x0J3MgdHJlbmQgbWV0aG9kcw0KDQpIb2x0J3MgbG9jYWwgdHJlbmQgbWV0aG9kIGlzIGltcGxlbWVudGVkIGluIHRoZSBob2x0KCkgZnVuY3Rpb246DQoNCiAgICBob2x0KHksIGggPSAxMCwgLi4uKQ0KICAgIA0KSGVyZSwgeW91IHdpbGwgYXBwbHkgaXQgdG8gdGhlIGF1c3RhIHNlcmllcywgd2hpY2ggY29udGFpbnMgYW5udWFsIGNvdW50cyBvZiBpbnRlcm5hdGlvbmFsIHZpc2l0b3JzIHRvIEF1c3RyYWxpYSBmcm9tIDE5ODAtMjAxNSAoaW4gbWlsbGlvbnMpLg0KYGBge3J9DQojIFByb2R1Y2UgMTAgeWVhciBmb3JlY2FzdHMgb2YgYXVzdGEgdXNpbmcgaG9sdCgpDQpmY2hvbHQgPC0gaG9sdChhdXN0YSwgaD0xMCkNCg0KIyBMb29rIGF0IGZpdHRlZCBtb2RlbCB1c2luZyBzdW1tYXJ5KCkNCnN1bW1hcnkoZmNob2x0KQ0KDQojIFBsb3QgdGhlIGZvcmVjYXN0cw0KYXV0b3Bsb3QoZmNob2x0KQ0KDQojIENoZWNrIHRoYXQgdGhlIHJlc2lkdWFscyBsb29rIGxpa2Ugd2hpdGUgbm9pc2UNCmNoZWNrcmVzaWR1YWxzKGZjaG9sdCkNCmBgYA0KIyMgRXhwb25lbnRpYWwgc21vb3RoaW5nIG1ldGhvZHMgd2l0aCB0cmVuZCBhbmQgc2Vhc29uYWxpdHkNCg0KIyMjIEhvbHQtV2ludGVycyB3aXRoIG1vbnRobHkgZGF0YQ0KDQpZb3UgbGVhcm5lZCB0aGF0IHRoZSBodygpIGZ1bmN0aW9uIHByb2R1Y2VzIGZvcmVjYXN0cyB1c2luZyB0aGUgSG9sdC1XaW50ZXJzIG1ldGhvZCBzcGVjaWZpYyB0byB3aGF0ZXZlciB5b3Ugc2V0IGVxdWFsIHRvIHRoZSBzZWFzb25hbCBhcmd1bWVudDoNCg0KICAgIGZjMSA8LSBodyhhdXN0LCBzZWFzb25hbCA9ICJhZGRpdGl2ZSIpDQogICAgZmMyIDwtIGh3KGF1c3QsIHNlYXNvbmFsID0gIm11bHRpcGxpY2F0aXZlIikNCg0KSGVyZSwgeW91IHdpbGwgYXBwbHkgaHcoKSB0byBhMTAsIHRoZSBtb250aGx5IHNhbGVzIG9mIGFudGktZGlhYmV0aWMgZHJ1Z3MgaW4gQXVzdHJhbGlhIGZyb20gMTk5MSB0byAyMDA4Lg0KYGBge3J9DQojIFBsb3QgdGhlIGRhdGENCmF1dG9wbG90KGExMCkNCg0KIyBQcm9kdWNlIDMgeWVhciBmb3JlY2FzdHMNCmZjIDwtIGh3KGExMCwgc2Vhc29uYWwgPSAibXVsdGlwbGljYXRpdmUiLCBoID0gMzYpDQoNCiMgQ2hlY2sgaWYgcmVzaWR1YWxzIGxvb2sgbGlrZSB3aGl0ZSBub2lzZQ0KY2hlY2tyZXNpZHVhbHMoZmMpDQoNCndoaXRlbm9pc2UgPC0gRkFMU0UNCg0KIyBQbG90IGZvcmVjYXN0cw0KYXV0b3Bsb3QoZmMpDQpgYGANClRoZSBmb3JlY2FzdHMgbWlnaHQgc3RpbGwgcHJvdmlkZSB1c2VmdWwgaW5mb3JtYXRpb24gZXZlbiB3aXRoIHJlc2lkdWFscyB0aGF0IGZhaWwgdGhlIHdoaXRlIG5vaXNlIHRlc3QuDQoNCiMjIyBIb2x0LVdpbnRlcnMgbWV0aG9kIHdpdGggZGFpbHkgZGF0YQ0KDQpUaGUgSG9sdC1XaW50ZXJzIG1ldGhvZCBjYW4gYWxzbyBiZSB1c2VkIGZvciBkYWlseSB0eXBlIG9mIGRhdGEsIHdoZXJlIHRoZSBzZWFzb25hbCBwYXR0ZXJuIGlzIG9mIGxlbmd0aCA3LCBhbmQgdGhlIGFwcHJvcHJpYXRlIHVuaXQgb2YgdGltZSBmb3IgaCBpcyBpbiBkYXlzLg0KDQpIZXJlLCB5b3Ugd2lsbCBjb21wYXJlIGFuIGFkZGl0aXZlIEhvbHQtV2ludGVycyBtZXRob2QgYW5kIGEgc2Vhc29uYWwgbmFpdmUoKSBtZXRob2QgZm9yIHRoZSBoeW5kc2lnaHQgZGF0YSwgd2hpY2ggY29udGFpbnMgdGhlIGRhaWx5IHBhZ2V2aWV3cyBvbiB0aGUgSHluZHNpZ2h0IGJsb2cgZm9yIG9uZSB5ZWFyIHN0YXJ0aW5nIEFwcmlsIDMwLCAyMDE0Lg0KDQpgYGB7cn0NCiMgQ3JlYXRlIHRyYWluaW5nIGRhdGEgd2l0aCBzdWJzZXQoKQ0KdHJhaW4gPC0gc3Vic2V0KGh5bmRzaWdodCwgZW5kID0gbGVuZ3RoKGh5bmRzaWdodCkgLSAyOCkNCg0KIyBIb2x0LVdpbnRlcnMgYWRkaXRpdmUgZm9yZWNhc3RzIGFzIGZjaHcNCmZjaHcgPC0gaHcodHJhaW4sIHNlYXNvbmFsID0gImFkZGl0aXZlIiwgaCA9IDI4KQ0KDQojIFNlYXNvbmFsIG5haXZlIGZvcmVjYXN0cyBhcyBmY3NuDQpmY3NuIDwtIHNuYWl2ZSh0cmFpbiwgaCA9IDI4KQ0KDQojIEZpbmQgYmV0dGVyIGZvcmVjYXN0cyB3aXRoIGFjY3VyYWN5KCkNCmFjY3VyYWN5KGZjaHcsIGh5bmRzaWdodCkNCmFjY3VyYWN5KGZjc24sIGh5bmRzaWdodCkNCg0KIyBQbG90IHRoZSBiZXR0ZXIgZm9yZWNhc3RzDQphdXRvcGxvdChmY2h3KQ0KYGBgDQojIyBTdGF0ZSBzcGFjZSBtb2RlbHMgZm9yIGV4cG9uZW50aWFsIHNtb290aGluZw0KDQojIyMgQXV0b21hdGljIGZvcmVjYXN0aW5nIHdpdGggZXhwb25lbnRpYWwgc21vb3RoaW5nDQoNClRoZSBuYW1lc2FrZSBmdW5jdGlvbiBmb3IgZmluZGluZyBlcnJvcnMsIHRyZW5kLCBhbmQgc2Vhc29uYWxpdHkgKEVUUykgcHJvdmlkZXMgYSBjb21wbGV0ZWx5IGF1dG9tYXRpYyB3YXkgb2YgcHJvZHVjaW5nIGZvcmVjYXN0cyBmb3IgYSB3aWRlIHJhbmdlIG9mIHRpbWUgc2VyaWVzLg0KYGBge3J9DQojIEZpdCBFVFMgbW9kZWwgdG8gYXVzdGEgaW4gZml0YXVzDQpmaXRhdXMgPC0gZXRzKGF1c3RhKQ0KDQojIENoZWNrIHJlc2lkdWFscw0KY2hlY2tyZXNpZHVhbHMoZml0YXVzKQ0KDQojIFBsb3QgZm9yZWNhc3RzDQphdXRvcGxvdChmb3JlY2FzdChmaXRhdXMpKQ0KDQojIFJlcGVhdCBmb3IgaHluZHNpZ2h0IGRhdGEgaW4gZml0aHMNCmZpdGhzIDwtIGV0cyhoeW5kc2lnaHQpDQpjaGVja3Jlc2lkdWFscyhmaXRocykNCmF1dG9wbG90KGZvcmVjYXN0KGZpdGhzKSkNCg0KIyBXaGljaCBtb2RlbChzKSBmYWlscyB0ZXN0PyAoVFJVRSBvciBGQUxTRSkNCmZpdGF1c2ZhaWwgPC0gRkFMU0UNCmZpdGhzZmFpbCA8LSBUUlVFDQpgYGANCiMjIyBFVFMgdnMgc2Vhc29uYWwgbmFpdmUNCg0KSGVyZSwgeW91IHdpbGwgY29tcGFyZSBFVFMgZm9yZWNhc3RzIGFnYWluc3Qgc2Vhc29uYWwgbmFpdmUgZm9yZWNhc3RpbmcgZm9yIDIwIHllYXJzIG9mIGNlbWVudCwgd2hpY2ggY29udGFpbnMgcXVhcnRlcmx5IGNlbWVudCBwcm9kdWN0aW9uIHVzaW5nIHRpbWUgc2VyaWVzIGNyb3NzLXZhbGlkYXRpb24gZm9yIDQgc3RlcHMgYWhlYWQuIA0KDQpUaGUgc2Vjb25kIGFyZ3VtZW50IGZvciB0c0NWKCkgbXVzdCByZXR1cm4gYSBmb3JlY2FzdCBvYmplY3QsIHNvIHlvdSBuZWVkIGEgZnVuY3Rpb24gdG8gZml0IGEgbW9kZWwgYW5kIHJldHVybiBmb3JlY2FzdHMuIFJlY2FsbDoNCg0KICAgID4gYXJncyh0c0NWKQ0KICAgIGZ1bmN0aW9uICh5LCBmb3JlY2FzdGZ1bmN0aW9uLCBoID0gMSwgLi4uKQ0KICAgIA0KYGBge3J9DQpjZW1lbnRfIDwtICBzdWJzZXQocWNlbWVudCwgc3RhcnQgPSBsZW5ndGgocWNlbWVudCkgLSA4MCkNCiMgRnVuY3Rpb24gdG8gcmV0dXJuIEVUUyBmb3JlY2FzdHMNCmZldHMgPC0gZnVuY3Rpb24oeSwgaCkgew0KICBmb3JlY2FzdChldHMoeSksIGggPSBoKQ0KfQ0KDQojIEFwcGx5IHRzQ1YoKSBmb3IgYm90aCBtZXRob2RzDQplMSA8LSB0c0NWKGNlbWVudF8sIGZldHMsIGggPSA0KQ0KZTIgPC0gdHNDVihjZW1lbnRfLCBzbmFpdmUsIGggPSA0KQ0KDQojIENvbXB1dGUgTVNFIG9mIHJlc3VsdGluZyBlcnJvcnMgKHdhdGNoIG91dCBmb3IgbWlzc2luZyB2YWx1ZXMpDQptZWFuKGUxXjIsIG5hLnJtID0gVFJVRSkNCm1lYW4oZTJeMiwgbmEucm0gPSBUUlVFKQ0KDQojIENvcHkgdGhlIGJlc3QgZm9yZWNhc3QgTVNFDQpiZXN0bXNlIDwtIG1lYW4oZTJeMiwgbmEucm0gPSBUUlVFKQ0KYGBgDQojIyMgV2hlbiBkb2VzIEVUUyBmYWlsPw0KDQpDb21wdXRpbmcgdGhlIEVUUyBkb2VzIG5vdCB3b3JrIHdlbGwgZm9yIGFsbCBzZXJpZXMuDQoNCkhlcmUsIHlvdSB3aWxsIG9ic2VydmUgd2h5IGl0IGRvZXMgbm90IHdvcmsgd2VsbCBmb3IgdGhlIGFubnVhbCBDYW5hZGlhbiBseW54IHBvcHVsYXRpb24gYXZhaWxhYmxlIGluIHlvdXIgd29ya3NwYWNlIGFzIGx5bnguDQpgYGB7cn0NCiMgUGxvdCB0aGUgbHlueCBzZXJpZXMNCmF1dG9wbG90KGx5bngpDQoNCiMgVXNlIGV0cygpIHRvIG1vZGVsIHRoZSBseW54IHNlcmllcw0KZml0IDwtIGV0cyhseW54KQ0KDQojIFVzZSBzdW1tYXJ5KCkgdG8gbG9vayBhdCBtb2RlbCBhbmQgcGFyYW1ldGVycw0Kc3VtbWFyeShmaXQpDQoNCiMgUGxvdCAyMC15ZWFyIGZvcmVjYXN0cyBvZiB0aGUgbHlueCBzZXJpZXMNCmZpdCAlPiUgZm9yZWNhc3QoaCA9IDIwKSAlPiUgYXV0b3Bsb3QoKQ0KYGBgDQpJdCdzIGltcG9ydGFudCB0byByZWFsaXplIHRoYXQgRVRTIGRvZXNuJ3Qgd29yayBmb3IgYWxsIGNhc2VzLg0KDQojIEZvcmVjYXN0aW5nIHdpdGggQVJJTUEgbW9kZWxzDQoNCiMjIFRyYW5zZm9ybWF0aW9ucyBmb3IgdmFyaWFuY2Ugc3RhYmlsaXphdGlvbg0KDQojIyMgQm94LUNveCB0cmFuc2Zvcm1hdGlvbnMgZm9yIHRpbWUgc2VyaWVzDQoNCkhlcmUsIHlvdSB3aWxsIHVzZSBhIEJveC1Db3ggdHJhbnNmb3JtYXRpb24gdG8gc3RhYmlsaXplIHRoZSB2YXJpYW5jZSBvZiB0aGUgcHJlLWxvYWRlZCBhMTAgc2VyaWVzLCB3aGljaCBjb250YWlucyBtb250aGx5IGFudGktZGlhYmV0aWMgZHJ1ZyBzYWxlcyBpbiBBdXN0cmFsaWEgZnJvbSAxOTkxLTIwMDguDQoNCkluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIG5lZWQgdG8gZXhwZXJpbWVudCB0byBzZWUgdGhlIGVmZmVjdCBvZiB0aGUgbGFtYmRhICjOuykgYXJndW1lbnQgb24gdGhlIHRyYW5zZm9ybWF0aW9uLiBOb3RpY2UgdGhhdCBzbWFsbCBjaGFuZ2VzIGluIM67IG1ha2UgbGl0dGxlIGRpZmZlcmVuY2UgdG8gdGhlIHJlc3VsdGluZyBzZXJpZXMuIFlvdSB3YW50IHRvIGZpbmQgYSB2YWx1ZSBvZiDOuyB0aGF0IG1ha2VzIHRoZSBzZWFzb25hbCBmbHVjdHVhdGlvbnMgb2Ygcm91Z2hseSB0aGUgc2FtZSBzaXplIGFjcm9zcyB0aGUgc2VyaWVzLg0KDQpSZWNhbGwgZnJvbSB0aGUgdmlkZW8gdGhhdCB0aGUgcmVjb21tZW5kZWQgcmFuZ2UgZm9yIGxhbWJkYSB2YWx1ZXMgaXMg4oiSMeKJpM674omkMS4NCg0KYGBge3J9DQojIFBsb3QgdGhlIHNlcmllcw0KYXV0b3Bsb3QoYTEwKQ0KDQojIFRyeSBmb3VyIHZhbHVlcyBvZiBsYW1iZGEgaW4gQm94LUNveCB0cmFuc2Zvcm1hdGlvbnMNCmExMCAlPiUgQm94Q294KGxhbWJkYSA9IDAuMCkgJT4lIGF1dG9wbG90KCkNCmExMCAlPiUgQm94Q294KGxhbWJkYSA9IDAuMSkgJT4lIGF1dG9wbG90KCkNCmExMCAlPiUgQm94Q294KGxhbWJkYSA9IDAuMikgJT4lIGF1dG9wbG90KCkNCmExMCAlPiUgQm94Q294KGxhbWJkYSA9IDAuMykgJT4lIGF1dG9wbG90KCkNCg0KIyBDb21wYXJlIHdpdGggQm94Q294LmxhbWJkYSgpDQpCb3hDb3gubGFtYmRhKGExMCkNCmBgYA0KSXQgc2VlbXMgbGlrZSBhIGxhbWJkYSBvZiAuMTMgd291bGQgd29yayB3ZWxsLg0KDQojIyMgTm9uLXNlYXNvbmFsIGRpZmZlcmVuY2luZyBmb3Igc3RhdGlvbmFyaXR5DQoNCkRpZmZlcmVuY2luZyBpcyBhIHdheSBvZiBtYWtpbmcgYSB0aW1lIHNlcmllcyBzdGF0aW9uYXJ5OyB0aGlzIG1lYW5zIHRoYXQgeW91IHJlbW92ZSBhbnkgc3lzdGVtYXRpYyBwYXR0ZXJucyBzdWNoIGFzIHRyZW5kIGFuZCBzZWFzb25hbGl0eSBmcm9tIHRoZSBkYXRhLiBBIHdoaXRlIG5vaXNlIHNlcmllcyBpcyBjb25zaWRlcmVkIGEgc3BlY2lhbCBjYXNlIG9mIGEgc3RhdGlvbmFyeSB0aW1lIHNlcmllcy4NCg0KV2l0aCBub24tc2Vhc29uYWwgZGF0YSwgeW91IHVzZSBsYWctMSBkaWZmZXJlbmNlcyB0byBtb2RlbCBjaGFuZ2VzIGJldHdlZW4gb2JzZXJ2YXRpb25zIHJhdGhlciB0aGFuIHRoZSBvYnNlcnZhdGlvbnMgZGlyZWN0bHkuIFlvdSBoYXZlIGRvbmUgdGhpcyBiZWZvcmUgYnkgdXNpbmcgdGhlIGRpZmYoKSBmdW5jdGlvbi4NCg0KSW4gdGhpcyBleGVyY2lzZSwgeW91IHdpbGwgdXNlIHRoZSBwcmUtbG9hZGVkIHdtdXJkZXJzIGRhdGEsIHdoaWNoIGNvbnRhaW5zIHRoZSBhbm51YWwgZmVtYWxlIG11cmRlciByYXRlIGluIHRoZSBVUyBmcm9tIDE5NTAtMjAwNC4NCmBgYHtyfQ0KIyBQbG90IHRoZSBVUyBmZW1hbGUgbXVyZGVyIHJhdGUNCmF1dG9wbG90KHdtdXJkZXJzKQ0KDQojIFBsb3QgdGhlIGRpZmZlcmVuY2VkIG11cmRlciByYXRlDQphdXRvcGxvdChkaWZmKHdtdXJkZXJzKSkNCg0KIyBQbG90IHRoZSBBQ0Ygb2YgdGhlIGRpZmZlcmVuY2VkIG11cmRlciByYXRlDQpnZ0FjZihkaWZmKHdtdXJkZXJzKSkNCmBgYA0KSXQgc2VlbXMgbGlrZSB0aGUgZGF0YSBsb29rIGxpa2Ugd2hpdGUgbm9pc2UgYWZ0ZXIgZGlmZmVyZW5jaW5nLg0KDQojIyMgU2Vhc29uYWwgZGlmZmVyZW5jaW5nIGZvciBzdGF0aW9uYXJpdHkNCg0KV2l0aCBzZWFzb25hbCBkYXRhLCBkaWZmZXJlbmNlcyBhcmUgb2Z0ZW4gdGFrZW4gYmV0d2VlbiBvYnNlcnZhdGlvbnMgaW4gdGhlIHNhbWUgc2Vhc29uIG9mIGNvbnNlY3V0aXZlIHllYXJzLCByYXRoZXIgdGhhbiBpbiBjb25zZWN1dGl2ZSBwZXJpb2RzLiBGb3IgZXhhbXBsZSwgd2l0aCBxdWFydGVybHkgZGF0YSwgb25lIHdvdWxkIHRha2UgdGhlIGRpZmZlcmVuY2UgYmV0d2VlbiBRMSBpbiBvbmUgeWVhciBhbmQgUTEgaW4gdGhlIHByZXZpb3VzIHllYXIuIFRoaXMgaXMgY2FsbGVkIHNlYXNvbmFsIGRpZmZlcmVuY2luZy4NCg0KU29tZXRpbWVzIHlvdSBuZWVkIHRvIGFwcGx5IGJvdGggc2Vhc29uYWwgZGlmZmVyZW5jZXMgYW5kIGxhZy0xIGRpZmZlcmVuY2VzIHRvIHRoZSBzYW1lIHNlcmllcywgdGh1cywgY2FsY3VsYXRpbmcgdGhlIGRpZmZlcmVuY2VzIGluIHRoZSBkaWZmZXJlbmNlcy4NCg0KSW4gdGhpcyBleGVyY2lzZSwgeW91IHdpbGwgdXNlIGRpZmZlcmVuY2luZyBhbmQgdHJhbnNmb3JtYXRpb25zIHNpbXVsdGFuZW91c2x5IHRvIG1ha2UgYSB0aW1lIHNlcmllcyBsb29rIHN0YXRpb25hcnkuIFRoZSBkYXRhIHNldCBoZXJlIGlzIGgwMiwgd2hpY2ggY29udGFpbnMgMTcgeWVhcnMgb2YgbW9udGhseSBjb3J0aWNvc3Rlcm9pZCBkcnVnIHNhbGVzIGluIEF1c3RyYWxpYS4NCmBgYHtyfQ0KIyBQbG90IHRoZSBkYXRhDQphdXRvcGxvdChoMDIpDQoNCiMgVGFrZSBsb2dzIGFuZCBzZWFzb25hbCBkaWZmZXJlbmNlcyBvZiBoMDINCmRpZmZsb2doMDIgPC0gZGlmZihsb2coaDAyKSwgbGFnID0gMTIpDQoNCiMgUGxvdCBkaWZmbG9naDAyDQphdXRvcGxvdChkaWZmbG9naDAyKQ0KDQojIFRha2UgYW5vdGhlciBkaWZmZXJlbmNlIGFuZCBwbG90DQpkZGlmZmxvZ2gwMiA8LSBkaWZmKGRpZmZsb2doMDIpDQphdXRvcGxvdChkZGlmZmxvZ2gwMikNCg0KIyBQbG90IEFDRiBvZiBkZGlmZmxvZ2gwMg0KZ2dBY2YoZGRpZmZsb2doMDIpDQpgYGANClRoZSBkYXRhIGRvZXNuJ3QgbG9vayBsaWtlIHdoaXRlIG5vaXNlIGFmdGVyIHRoZSB0cmFuc2Zvcm1hdGlvbiwgYnV0IHlvdSBjb3VsZCBkZXZlbG9wIGFuIEFSSU1BIG1vZGVsIGZvciBpdC4NCg0KIyMgQVJJTUEgbW9kZWxzDQoNCiMjIyBBdXRvbWF0aWMgQVJJTUEgbW9kZWxzIGZvciBub24tc2Vhc29uYWwgdGltZSBzZXJpZXMNCg0KVGhlIGF1dG8uYXJpbWEoKSBmdW5jdGlvbiB3aWxsIHNlbGVjdCBhbiBhcHByb3ByaWF0ZSBhdXRvcmVncmVzc2l2ZSBpbnRlZ3JhdGVkIG1vdmluZyBhdmVyYWdlIChBUklNQSkgbW9kZWwgZ2l2ZW4gYSB0aW1lIHNlcmllcywganVzdCBsaWtlIHRoZSBldHMoKSBmdW5jdGlvbiBkb2VzIGZvciBFVFMgbW9kZWxzLiBUaGUgc3VtbWFyeSgpIGZ1bmN0aW9uIGNhbiBwcm92aWRlIHNvbWUgYWRkaXRpb25hbCBpbnNpZ2h0czoNCg0KICAgID4gIyBwID0gMiwgZCA9IDEsIHAgPSAyDQogICAgPiBzdW1tYXJ5KGZpdCkNCiAgICANCiAgICBTZXJpZXM6IHVzbmV0ZWxlYw0KICAgIEFSSU1BKDIsMSwyKSB3aXRoIGRyaWZ0DQogICAgLi4uDQoNCkluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIGF1dG9tYXRpY2FsbHkgY2hvb3NlIGFuIEFSSU1BIG1vZGVsIGZvciB0aGUgcHJlLWxvYWRlZCBhdXN0YSBzZXJpZXMsIHdoaWNoIGNvbnRhaW5zIHRoZSBhbm51YWwgbnVtYmVyIG9mIGludGVybmF0aW9uYWwgdmlzaXRvcnMgdG8gQXVzdHJhbGlhIGZyb20gMTk4MC0yMDE1LiBZb3Ugd2lsbCB0aGVuIGNoZWNrIHRoZSByZXNpZHVhbHMgKHJlY2FsbCB0aGF0IGEgcC12YWx1ZSBncmVhdGVyIHRoYW4gMC4wNSBpbmRpY2F0ZXMgdGhhdCB0aGUgZGF0YSByZXNlbWJsZXMgd2hpdGUgbm9pc2UpIGFuZCBwcm9kdWNlIHNvbWUgZm9yZWNhc3RzLiBPdGhlciB0aGFuIHRoZSBtb2RlbGxpbmcgZnVuY3Rpb24sIHRoaXMgaXMgaWRlbnRpY2lhbCB0byB3aGF0IHlvdSBkaWQgd2l0aCBFVFMgZm9yZWNhc3RpbmcuDQoNCmBgYHtyfQ0KIyBGaXQgYW4gYXV0b21hdGljIEFSSU1BIG1vZGVsIHRvIHRoZSBhdXN0YSBzZXJpZXMNCmZpdCA8LSBhdXRvLmFyaW1hKGF1c3RhKQ0KDQojIENoZWNrIHRoYXQgdGhlIHJlc2lkdWFscyBsb29rIGxpa2Ugd2hpdGUgbm9pc2UNCmNoZWNrcmVzaWR1YWxzKGZpdCkNCnJlc2lkdWFsc29rIDwtIFRSVUUNCg0KIyBTdW1tYXJpemUgdGhlIG1vZGVsDQpzdW1tYXJ5KGZpdCkNCg0KIyBGaW5kIHRoZSBBSUNjIHZhbHVlIGFuZCB0aGUgbnVtYmVyIG9mIGRpZmZlcmVuY2VzIHVzZWQNCkFJQ2MgPC0gLTE0LjQ2DQpkIDwtIDENCg0KIyBQbG90IGZvcmVjYXN0cyBvZiBmaXQNCmZpdCAlPiUgZm9yZWNhc3QoaCA9IDEwKSAlPiUgYXV0b3Bsb3QoKQ0KYGBgDQojIyMgRm9yZWNhc3Rpbmcgd2l0aCBBUklNQSBtb2RlbHMNCg0KVGhlIGF1dG9tYXRpYyBtZXRob2QgaW4gdGhlIHByZXZpb3VzIGV4ZXJjaXNlIGNob3NlIGFuIEFSSU1BKDAsMSwxKSB3aXRoIGRyaWZ0IG1vZGVsIGZvciB0aGUgYXVzdGEgZGF0YSwgdGhhdCBpcywgeXQ9Yyt5dOKIkjErzrhldOKIkjErZXQuIFlvdSB3aWxsIG5vdyBleHBlcmltZW50IHdpdGggdmFyaW91cyBvdGhlciBBUklNQSBtb2RlbHMgZm9yIHRoZSBkYXRhIHRvIHNlZSB3aGF0IGRpZmZlcmVuY2UgaXQgbWFrZXMgdG8gdGhlIGZvcmVjYXN0cy4NCg0KVGhlIEFyaW1hKCkgZnVuY3Rpb24gY2FuIGJlIHVzZWQgdG8gc2VsZWN0IGEgc3BlY2lmaWMgQVJJTUEgbW9kZWwuIEl0cyBmaXJzdCBhcmd1bWVudCwgb3JkZXIsIGlzIHNldCB0byBhIHZlY3RvciB0aGF0IHNwZWNpZmllcyB0aGUgdmFsdWVzIG9mIHAsIGQgYW5kIHEuIFRoZSBzZWNvbmQgYXJndW1lbnQsIGluY2x1ZGUuY29uc3RhbnQsIGlzIGEgYm9vb2xlYW4gdGhhdCBkZXRlcm1pbmVzIGlmIHRoZSBjb25zdGFudCBjLCBvciBkcmlmdCwgc2hvdWxkIGJlIGluY2x1ZGVkLiBCZWxvdyBpcyBhbiBleGFtcGxlIG9mIGEgcGlwZSBmdW5jdGlvbiB0aGF0IHdvdWxkIHBsb3QgZm9yZWNhc3RzIG9mIHVzbmV0ZWxlYyBmcm9tIGFuIEFSSU1BKDIsMSwyKSBtb2RlbCB3aXRoIGRyaWZ0Og0KDQpgYGB7cn0NCnVzbmV0ZWxlYyAlPiUNCiAgICBBcmltYShvcmRlciA9IGMoMiwxLDIpLCBpbmNsdWRlLmNvbnN0YW50ID0gVFJVRSkgJT4lDQogICAgZm9yZWNhc3QoKSAlPiUNCiAgICBhdXRvcGxvdCgpDQpgYGANCkluIHRoZSBleGFtcGxlcyBoZXJlLCB3YXRjaCBmb3IgaG93IHRoZSBkaWZmZXJlbnQgbW9kZWxzIGFmZmVjdCB0aGUgZm9yZWNhc3RzIGFuZCB0aGUgcHJlZGljdGlvbiBpbnRlcnZhbHMuIA0KDQpgYGB7cn0NCiMgUGxvdCBmb3JlY2FzdHMgZnJvbSBhbiBBUklNQSgwLDEsMSkgbW9kZWwgd2l0aCBubyBkcmlmdA0KYXVzdGEgJT4lIEFyaW1hKG9yZGVyID0gYygwLCAxLCAxKSwgaW5jbHVkZS5jb25zdGFudCA9IEZBTFNFKSAlPiUgZm9yZWNhc3QoKSAlPiUgYXV0b3Bsb3QoKQ0KDQojIFBsb3QgZm9yZWNhc3RzIGZyb20gYW4gQVJJTUEoMiwxLDMpIG1vZGVsIHdpdGggZHJpZnQNCmF1c3RhICU+JSBBcmltYShvcmRlciA9IGMoMiwgMSwgMyksIGluY2x1ZGUuY29uc3RhbnQgPSBUUlVFKSAlPiUgZm9yZWNhc3QoKSAlPiUgYXV0b3Bsb3QoKQ0KDQojIFBsb3QgZm9yZWNhc3RzIGZyb20gYW4gQVJJTUEoMCwwLDEpIG1vZGVsIHdpdGggYSBjb25zdGFudA0KYXVzdGEgJT4lIEFyaW1hKG9yZGVyID0gYygwLCAwLCAxKSwgaW5jbHVkZS5jb25zdGFudCA9IFRSVUUpICU+JSBmb3JlY2FzdCgpICU+JSBhdXRvcGxvdCgpDQoNCiMgUGxvdCBmb3JlY2FzdHMgZnJvbSBhbiBBUklNQSgwLDIsMSkgbW9kZWwgd2l0aCBubyBjb25zdGFudA0KYXVzdGEgJT4lIEFyaW1hKG9yZGVyID0gYygwLCAyLCAxKSwgaW5jbHVkZS5jb25zdGFudCA9IEZBTFNFKSAlPiUgZm9yZWNhc3QoKSAlPiUgYXV0b3Bsb3QoKQ0KYGBgDQojIyMgQ29tcGFyaW5nIGF1dG8uYXJpbWEoKSBhbmQgZXRzKCkgb24gbm9uLXNlYXNvbmFsIGRhdGENCg0KVGhlIEFJQ2Mgc3RhdGlzdGljIGlzIHVzZWZ1bCBmb3Igc2VsZWN0aW5nIGJldHdlZW4gbW9kZWxzIGluIHRoZSBzYW1lIGNsYXNzLiBGb3IgZXhhbXBsZSwgeW91IGNhbiB1c2UgaXQgdG8gc2VsZWN0IGFuIEVUUyBtb2RlbCBvciB0byBzZWxlY3QgYW4gQVJJTUEgbW9kZWwuIEhvd2V2ZXIsIHlvdSBjYW5ub3QgdXNlIGl0IHRvIGNvbXBhcmUgRVRTIGFuZCBBUklNQSBtb2RlbHMgYmVjYXVzZSB0aGV5IGFyZSBpbiBkaWZmZXJlbnQgbW9kZWwgY2xhc3Nlcy4NCg0KSW5zdGVhZCwgeW91IGNhbiB1c2UgdGltZSBzZXJpZXMgY3Jvc3MtdmFsaWRhdGlvbiB0byBjb21wYXJlIGFuIEFSSU1BIG1vZGVsIGFuZCBhbiBFVFMgbW9kZWwgb24gdGhlIGF1c3RhIGRhdGEuIEJlY2F1c2UgdHNDVigpIHJlcXVpcmVzIGZ1bmN0aW9ucyB0aGF0IHJldHVybiBmb3JlY2FzdCBvYmplY3RzLCB5b3Ugd2lsbCBzZXQgdXAgc29tZSBzaW1wbGUgZnVuY3Rpb25zIHRoYXQgZml0IHRoZSBtb2RlbHMgYW5kIHJldHVybiB0aGUgZm9yZWNhc3RzLiBUaGUgYXJndW1lbnRzIG9mIHRzQ1YoKSBhcmUgYSB0aW1lIHNlcmllcywgZm9yZWNhc3QgZnVuY3Rpb24sIGFuZCBmb3JlY2FzdCBob3Jpem9uIGguIEV4YW1pbmUgdGhpcyBjb2RlIHNuaXBwZXQgZnJvbSB0aGUgc2Vjb25kIGNoYXB0ZXI6DQoNCg0KICAgIGUgPC0gbWF0cml4KE5BX3JlYWxfLCBucm93ID0gMTAwMCwgbmNvbCA9IDgpDQogICAgZm9yIChoIGluIDE6OCkNCiAgICAgIGVbLCBoXSA8LSB0c0NWKGdvb2csIG5haXZlLCBoID0gaCkNCiAgICAgIC4uLg0KDQpGdXJ0aGVybW9yZSwgcmVjYWxsIHRoYXQgcGlwZSBvcGVyYXRvcnMgaW4gUiB0YWtlIHRoZSB2YWx1ZSBvZiB3aGF0ZXZlciBpcyBvbiB0aGUgbGVmdCBhbmQgcGFzcyBpdCBhcyBhbiBhcmd1bWVudCB0byB3aGF0ZXZlciBpcyBvbiB0aGUgcmlnaHQsIHN0ZXAgYnkgc3RlcCwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiBIZXJlJ3MgYW4gZXhhbXBsZSBiYXNlZCBvbiBjb2RlIHlvdSBzYXcgaW4gYW4gZWFybGllciBjaGFwdGVyOg0KDQogICAgIyBQbG90IDIwLXllYXIgZm9yZWNhc3RzIG9mIHRoZSBseW54IHNlcmllcyBtb2RlbGVkIGJ5IGV0cygpDQogICAgbHlueCAlPiUgZXRzKCkgJT4lIGZvcmVjYXN0KGggPSAyMCkgJT4lIGF1dG9wbG90KCkNCg0KSW4gdGhpcyBleGVyY2lzZSwgeW91IHdpbGwgY29tcGFyZSB0aGUgTVNFIG9mIHR3byBmb3JlY2FzdCBmdW5jdGlvbnMgYXBwbGllZCB0byBhdXN0YSwgYW5kIHBsb3QgZm9yZWNhc3RzIG9mIHRoZSBmdW5jdGlvbiB0aGF0IGNvbXB1dGVzIHRoZSBiZXN0IGZvcmVjYXN0cy4NCmBgYHtyfQ0KIyBTZXQgdXAgZm9yZWNhc3QgZnVuY3Rpb25zIGZvciBFVFMgYW5kIEFSSU1BIG1vZGVscw0KZmV0cyA8LSBmdW5jdGlvbih4LCBoKSB7DQogIGZvcmVjYXN0KGV0cyh4KSwgaCA9IGgpDQp9DQpmYXJpbWEgPC0gZnVuY3Rpb24oeCwgaCkgew0KICBmb3JlY2FzdChhdXRvLmFyaW1hKHgpLCBoID0gaCkNCn0NCg0KIyBDb21wdXRlIENWIGVycm9ycyBmb3IgRVRTIG9uIGF1c3RhIGFzIGUxDQplMSA8LSB0c0NWKGF1c3RhLCBmZXRzLCBoID0gMSkNCg0KIyBDb21wdXRlIENWIGVycm9ycyBmb3IgQVJJTUEgb24gYXVzdGEgYXMgZTINCmUyIDwtIHRzQ1YoYXVzdGEsIGZhcmltYSwgaCA9IDEpDQoNCiMgRmluZCBNU0Ugb2YgZWFjaCBtb2RlbCBjbGFzcw0KbWVhbihlMV4yLCBuYS5ybSA9IFRSVUUpDQptZWFuKGUyXjIsIG5hLnJtID0gVFJVRSkNCiMgUGxvdCAxMC15ZWFyIGZvcmVjYXN0cyB1c2luZyB0aGUgYmVzdCBtb2RlbCBjbGFzcw0KYXVzdGEgJT4lIGZhcmltYShoID0gMTApICU+JSBhdXRvcGxvdCgpDQpgYGANCiMjIFNlYXNvbmFsIEFSSU1BIG1vZGVscw0KDQojIyMgQXV0b21hdGljIEFSSU1BIG1vZGVscyBmb3Igc2Vhc29uYWwgdGltZSBzZXJpZXMNCg0KdGhlIGF1dG8uYXJpbWEoKSBmdW5jdGlvbiBhbHNvIHdvcmtzIHdpdGggc2Vhc29uYWwgZGF0YS4gTm90ZSB0aGF0IHNldHRpbmcgbGFtYmRhID0gMCBpbiB0aGUgYXV0by5hcmltYSgpIGZ1bmN0aW9uIC0gYXBwbHlpbmcgYSBsb2cgdHJhbnNmb3JtYXRpb24gLSBtZWFucyB0aGF0IHRoZSBtb2RlbCB3aWxsIGJlIGZpdHRlZCB0byB0aGUgdHJhbnNmb3JtZWQgZGF0YSwgYW5kIHRoYXQgdGhlIGZvcmVjYXN0cyB3aWxsIGJlIGJhY2stdHJhbnNmb3JtZWQgb250byB0aGUgb3JpZ2luYWwgc2NhbGUuDQoNCkFmdGVyIGFwcGx5aW5nIHN1bW1hcnkoKSB0byB0aGlzIGtpbmQgb2YgZml0dGVkIG1vZGVsLCB5b3UgbWF5IHNlZSBzb21ldGhpbmcgbGlrZSB0aGUgb3V0cHV0IGJlbG93IHdoaWNoIGNvcnJlc3BvbmRzIHdpdGggKHAsZCxxKShQLEQsUSlbbV06DQoNCiAgICBBUklNQSgwLDEsNCkoMCwxLDEpWzEyXQ0KDQpJbiB0aGlzIGV4ZXJjaXNlLCB5b3Ugd2lsbCB1c2UgdGhlc2UgZnVuY3Rpb25zIHRvIG1vZGVsIGFuZCBmb3JlY2FzdCB0aGUgcHJlLWxvYWRlZCBoMDIgZGF0YSwgd2hpY2ggY29udGFpbnMgbW9udGhseSBzYWxlcyBvZiBjb3J0ZWNvc3Rlcm9pZCBkcnVncyBpbiBBdXN0cmFsaWEuDQoNCmBgYHtyfQ0KIyBDaGVjayB0aGF0IHRoZSBsb2dnZWQgaDAyIGRhdGEgaGF2ZSBzdGFibGUgdmFyaWFuY2UNCmgwMiAlPiUgbG9nKCkgJT4lIGF1dG9wbG90KCkNCg0KIyBGaXQgYSBzZWFzb25hbCBBUklNQSBtb2RlbCB0byBoMDIgd2l0aCBsYW1iZGEgPSAwDQpmaXQgPC0gYXV0by5hcmltYShoMDIsIGxhbWJkYSA9IDApDQoNCiMgU3VtbWFyaXplIHRoZSBmaXR0ZWQgbW9kZWwNCnN1bW1hcnkoZml0KQ0KDQojIFJlY29yZCB0aGUgYW1vdW50IG9mIGxhZy0xIGRpZmZlcmVuY2luZyBhbmQgc2Vhc29uYWwgZGlmZmVyZW5jaW5nIHVzZWQNCmQgPC0gMQ0KRCA8LSAxDQoNCiMgUGxvdCAyLXllYXIgZm9yZWNhc3RzDQpmaXQgJT4lIGZvcmVjYXN0KGggPSAyNCkgJT4lIGF1dG9wbG90KCkNCmBgYA0KYXV0by5hcmltYSgpIGlzIGZsZXhpYmxlIGVub3VnaCB0byBldmVuIHdvcmsgd2l0aCBzZWFzb25hbCB0aW1lIHNlcmllcyENCg0KIyMjIEV4cGxvcmluZyBhdXRvLmFyaW1hKCkgb3B0aW9ucw0KDQpUaGUgYXV0by5hcmltYSgpIGZ1bmN0aW9uIG5lZWRzIHRvIGVzdGltYXRlIGEgbG90IG9mIGRpZmZlcmVudCBtb2RlbHMsIGFuZCB2YXJpb3VzIHNob3J0LWN1dHMgYXJlIHVzZWQgdG8gdHJ5IHRvIG1ha2UgdGhlIGZ1bmN0aW9uIGFzIGZhc3QgYXMgcG9zc2libGUuIFRoaXMgY2FuIGNhdXNlIGEgbW9kZWwgdG8gYmUgcmV0dXJuZWQgd2hpY2ggZG9lcyBub3QgYWN0dWFsbHkgaGF2ZSB0aGUgc21hbGxlc3QgQUlDYyB2YWx1ZS4gVG8gbWFrZSBhdXRvLmFyaW1hKCkgd29yayBoYXJkZXIgdG8gZmluZCBhIGdvb2QgbW9kZWwsIGFkZCB0aGUgb3B0aW9uYWwgYXJndW1lbnQgc3RlcHdpc2UgPSBGQUxTRSB0byBsb29rIGF0IGEgbXVjaCBsYXJnZXIgY29sbGVjdGlvbiBvZiBtb2RlbHMuDQoNCkhlcmUsIHlvdSB3aWxsIHRyeSBmaW5kaW5nIGFuIEFSSU1BIG1vZGVsIGZvciB0aGUgcHJlLWxvYWRlZCBldXJldGFpbCBkYXRhLCB3aGljaCBjb250YWlucyBxdWFydGVybHkgcmV0YWlsIHRyYWRlIGluIHRoZSBFdXJvIGFyZWEgZnJvbSAxOTk2LTIwMTEuDQpgYGB7cn0NCmF1dG9wbG90KGV1cmV0YWlsKQ0KYGBgDQpgYGB7cn0NCiMgRmluZCBhbiBBUklNQSBtb2RlbCBmb3IgZXVyZXRhaWwNCmZpdDEgPC0gYXV0by5hcmltYShldXJldGFpbCkNCg0KIyBEb24ndCB1c2UgYSBzdGVwd2lzZSBzZWFyY2gNCmZpdDIgPC0gYXV0by5hcmltYShldXJldGFpbCwgc3RlcHdpc2UgPSBGQUxTRSkNCg0Kc3VtbWFyeShmaXQxKQ0Kc3VtbWFyeShmaXQyKQ0KYGBgDQpgYGB7cn0NCiMgQUlDYyBvZiBiZXR0ZXIgbW9kZWwNCkFJQ2MgPC0gNjguMzkNCg0KIyBDb21wdXRlIDIteWVhciBmb3JlY2FzdHMgZnJvbSBiZXR0ZXIgbW9kZWwNCmZpdDIgJT4lIGZvcmVjYXN0KGggPSA4KSAlPiUgYXV0b3Bsb3QoKQ0KYGBgDQojIyMgQ29tcGFyaW5nIGF1dG8uYXJpbWEoKSBhbmQgZXRzKCkgb24gc2Vhc29uYWwgZGF0YQ0KDQpXaGF0IGhhcHBlbnMgd2hlbiB5b3Ugd2FudCB0byBjcmVhdGUgdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cyBmb3IgZGF0YSB0aGF0IGlzIG1vcmUgZnJlcXVlbnQgdGhhbiB5ZWFybHk/IElmIG5lZWRlZCwgeW91IGNhbiB1c2UgYSB2ZWN0b3IgaW4gZm9ybSBjKHllYXIsIHBlcmlvZCkgZm9yIHRoZSBzdGFydCBhbmQvb3IgZW5kIGtleXdvcmRzIGluIHRoZSB3aW5kb3coKSBmdW5jdGlvbi4gWW91IG11c3QgYWxzbyBlbnN1cmUgdGhhdCB5b3UncmUgdXNpbmcgdGhlIGFwcHJvcHJpYXRlIHZhbHVlcyBvZiBoIGluIGZvcmVjYXN0aW5nIGZ1bmN0aW9ucy4gUmVjYWxsIHRoYXQgaCBzaG91bGQgYmUgZXF1YWwgdG8gdGhlIGxlbmd0aCBvZiB0aGUgZGF0YSB0aGF0IG1ha2VzIHVwIHlvdXIgdGVzdCBzZXQuDQoNCkZvciBleGFtcGxlLCBpZiB5b3VyIGRhdGEgc3BhbnMgMTUgeWVhcnMsIHlvdXIgdHJhaW5pbmcgc2V0IGNvbnNpc3RzIG9mIHRoZSBmaXJzdCAxMCB5ZWFycywgYW5kIHlvdSBpbnRlbmQgdG8gZm9yZWNhc3QgdGhlIGxhc3QgNSB5ZWFycyBvZiBkYXRhLCB5b3Ugd291bGQgdXNlIGggPSAxMiAqIDUgbm90IGggPSA1IGJlY2F1c2UgeW91ciB0ZXN0IHNldCB3b3VsZCBpbmNsdWRlIDYwIG1vbnRobHkgb2JzZXJ2YXRpb25zLiBJZiBpbnN0ZWFkIHlvdXIgdHJhaW5pbmcgc2V0IGNvbnNpc3RzIG9mIHRoZSBmaXJzdCA5LjUgeWVhcnMgYW5kIHlvdSB3YW50IGZvcmVjYXN0IHRoZSBsYXN0IDUuNSB5ZWFycywgeW91IHdvdWxkIHVzZSBoID0gNjYgdG8gYWNjb3VudCBmb3IgdGhlIGV4dHJhIDYgbW9udGhzLg0KDQpJbiB0aGUgZmluYWwgZXhlcmNpc2UgZm9yIHRoaXMgY2hhcHRlciwgeW91IHdpbGwgY29tcGFyZSBzZWFzb25hbCBBUklNQSBhbmQgRVRTIG1vZGVscyBhcHBsaWVkIHRvIHRoZSBxdWFydGVybHkgY2VtZW50IHByb2R1Y3Rpb24gZGF0YSBxY2VtZW50LiBCZWNhdXNlIHRoZSBzZXJpZXMgaXMgdmVyeSBsb25nLCB5b3UgY2FuIGFmZm9yZCB0byB1c2UgYSB0cmFpbmluZyBhbmQgdGVzdCBzZXQgcmF0aGVyIHRoYW4gdGltZSBzZXJpZXMgY3Jvc3MtdmFsaWRhdGlvbi4gVGhpcyBpcyBtdWNoIGZhc3Rlci4NCmBgYHtyfQ0KIyBVc2UgMjAgeWVhcnMgb2YgdGhlIHFjZW1lbnQgZGF0YSBiZWdpbm5pbmcgaW4gMTk4OA0KdHJhaW4gPC0gd2luZG93KHFjZW1lbnQsIHN0YXJ0ID0gYygxOTg4LCAxKSwgZW5kID0gYygyMDA3LCA0KSkNCg0KIyBGaXQgYW4gQVJJTUEgYW5kIGFuIEVUUyBtb2RlbCB0byB0aGUgdHJhaW5pbmcgZGF0YQ0KZml0MSA8LSBhdXRvLmFyaW1hKHRyYWluKQ0KZml0MiA8LSBldHModHJhaW4pDQoNCiMgQ2hlY2sgdGhhdCBib3RoIG1vZGVscyBoYXZlIHdoaXRlIG5vaXNlIHJlc2lkdWFscw0KY2hlY2tyZXNpZHVhbHMoZml0MSkNCmNoZWNrcmVzaWR1YWxzKGZpdDIpDQoNCiMgUHJvZHVjZSBmb3JlY2FzdHMgZm9yIGVhY2ggbW9kZWwNCmZjMSA8LSBmb3JlY2FzdChmaXQxLCBoID0gMjUpDQpmYzIgPC0gZm9yZWNhc3QoZml0MiwgaCA9IDI1KQ0KDQojIFVzZSBhY2N1cmFjeSgpIHRvIGZpbmQgYmV0dGVyIG1vZGVsIGJhc2VkIG9uIFJNU0UNCmFjY3VyYWN5KGZjMSwgcWNlbWVudCkNCmFjY3VyYWN5KGZjMiwgcWNlbWVudCkNCmJldHRlcm1vZGVsIDwtIGZpdDINCmBgYA0KTG9va3MgbGlrZSB0aGUgRVRTIG1vZGVsIGRpZCBiZXR0ZXIgaGVyZS4NCg0KIyBBZHZhbmNlZCBtZXRob2RzDQoNCiMjIER5bmFtaWMgcmVncmVzc2lvbg0KDQojIyMgRm9yZWNhc3Rpbmcgc2FsZXMgYWxsb3dpbmcgZm9yIGFkdmVydGlzaW5nIGV4cGVuZGl0dXJlDQoNClRoZSBhdXRvLmFyaW1hKCkgZnVuY3Rpb24gd2lsbCBmaXQgYSBkeW5hbWljIHJlZ3Jlc3Npb24gbW9kZWwgd2l0aCBBUklNQSBlcnJvcnMuIFRoZSBvbmx5IGNoYW5nZSB0byBob3cgeW91IHVzZWQgaXQgcHJldmlvdXNseSBpcyB0aGF0IHlvdSB3aWxsIG5vdyB1c2UgdGhlIHhyZWcgYXJndW1lbnQgY29udGFpbmluZyBhIG1hdHJpeCBvZiByZWdyZXNzaW9uIHZhcmlhYmxlcy4NCg0KICAgIGZpdCA8LSBhdXRvLmFyaW1hKHVzY2hhbmdlWywgIkNvbnN1bXB0aW9uIl0sDQogICAgICAgICAgICAgICAgICAgICAgICB4cmVnID0gdXNjaGFuZ2VbLCAiSW5jb21lIl0pDQoNCiAgICAjIHJlcCh4LCB0aW1lcykNCiAgICBmY2FzdCA8LSBmb3JlY2FzdChmaXQsIHhyZWcgPSByZXAoMC44LCA4KSkNCg0KWW91IGNhbiBzZWUgdGhhdCB0aGUgZGF0YSBpcyBzZXQgdG8gdGhlIENvbnN1bXB0aW9uIGNvbHVtbiBvZiB1c2NoYW5nZSwgYW5kIHRoZSByZWdyZXNzaW9uIHZhcmlhYmxlIGlzIHRoZSBJbmNvbWUgY29sdW1uLiBGdXJ0aGVybW9yZSwgdGhlIHJlcCgpIGZ1bmN0aW9uIGluIHRoaXMgY2FzZSB3b3VsZCByZXBsaWNhdGUgdGhlIHZhbHVlIDAuOCBleGFjdGx5IGVpZ2h0IHRpbWVzIGZvciB0aGUgbWF0cml4IGFyZ3VtZW50IHhyZWcuDQoNCkluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIG1vZGVsIHNhbGVzIGRhdGEgcmVncmVzc2VkIGFnYWluc3QgYWR2ZXJ0aXNpbmcgZXhwZW5kaXR1cmUsIHdpdGggYW4gQVJNQSBlcnJvciB0byBhY2NvdW50IGZvciBhbnkgc2VyaWFsIGNvcnJlbGF0aW9uIGluIHRoZSByZWdyZXNzaW9uIGVycm9ycy4gVGhlIGRhdGEgYXJlIGF2YWlsYWJsZSBpbiB5b3VyIHdvcmtzcGFjZSBhcyBhZHZlcnQgYW5kIGNvbXByaXNlIDI0IG1vbnRocyBvZiBzYWxlcyBhbmQgYWR2ZXJ0aXNpbmcgZXhwZW5kaXR1cmUgZm9yIGFuIGF1dG9tb3RpdmUgcGFydHMgY29tcGFueS4gVGhlIHBsb3Qgc2hvd3Mgc2FsZXMgdnMgYWR2ZXJ0aXNpbmcgZXhwZW5kaXR1cmUuDQpgYGB7cn0NCmdncGxvdChhZXMoeCA9IGFkdmVydCwgeSA9IHNhbGVzKSwgZGF0YSA9IGFzLmRhdGEuZnJhbWUoYWR2c2FsZXMpKSArDQogIGdlb21fcG9pbnQoKQ0KYGBgDQoNCmBgYHtyfQ0KIyBUaW1lIHBsb3Qgb2YgYm90aCB2YXJpYWJsZXMNCmF1dG9wbG90KGFkdnNhbGVzLCBmYWNldHMgPSBUUlVFKQ0KYGBgDQpGaXQgYSByZWdyZXNzaW9uIHdpdGggQVJJTUEgZXJyb3JzIHRvIGFkdmVydCBieSBzZXR0aW5nIHRoZSBmaXJzdCBhcmd1bWVudCBvZiBhdXRvLmFyaW1hKCkgdG8gdGhlICJzYWxlcyIgY29sdW1uLCBzZWNvbmQgYXJndW1lbnQgeHJlZyB0byB0aGUgImFkdmVydCIgY29sdW1uLCBhbmQgdGhpcmQgYXJndW1lbnQgc3RhdGlvbmFyeSB0byBUUlVFLg0KYGBge3J9DQojIEZpdCBBUklNQSBtb2RlbA0KZml0IDwtIGF1dG8uYXJpbWEoYWR2c2FsZXNbLCAic2FsZXMiXSwgeHJlZyA9IGFkdnNhbGVzWywiYWR2ZXJ0Il0sIHN0YXRpb25hcnkgPSBUUlVFKQ0KYGBgDQpDaGVjayB0aGF0IHRoZSBmaXR0ZWQgbW9kZWwgaXMgYSByZWdyZXNzaW9uIHdpdGggQVIoMSkgZXJyb3JzLiBXaGF0IGlzIHRoZSBpbmNyZWFzZSBpbiBzYWxlcyBmb3IgZXZlcnkgdW5pdCBpbmNyZWFzZSBpbiBhZHZlcnRpc2luZz8gVGhpcyBjb2VmZmljaWVudCBpcyB0aGUgdGhpcmQgZWxlbWVudCBpbiB0aGUgY29lZmZpY2llbnRzKCkgb3V0cHV0Lg0KYGBge3J9DQpzdW1tYXJ5KGZpdCkNCiMgQ2hlY2sgbW9kZWwuIEluY3JlYXNlIGluIHNhbGVzIGZvciBlYWNoIHVuaXQgaW5jcmVhc2UgaW4gYWR2ZXJ0aXNpbmcNCnNhbGVzaW5jcmVhc2UgPC0gY29lZmZpY2llbnRzKGZpdClbM10NCnNhbGVzaW5jcmVhc2UNCmBgYA0Kb3JlY2FzdCBmcm9tIHRoZSBmaXR0ZWQgbW9kZWwgc3BlY2lmeWluZyB0aGUgbmV4dCA2IG1vbnRocyBvZiBhZHZlcnRpc2luZyBleHBlbmRpdHVyZSBhcyAxMCB1bml0cyBwZXIgbW9udGggYXMgZmMuIFRvIHJlcGVhdCAxMCBzaXggdGltZXMsIHVzZSB0aGUgcmVwKCkgZnVuY3Rpb24gaW5zaWRlIHhyZWcgbGlrZSBpbiB0aGUgZXhhbXBsZSBjb2RlIGFib3ZlLg0KDQpQbG90IHRoZSBmb3JlY2FzdHMgZmMgYW5kIGZpbGwgaW4gdGhlIHByb3ZpZGVkIGNvZGUgdG8gYWRkIGFuIHggbGFiZWwgIk1vbnRoIiBhbmQgeSBsYWJlbCAiU2FsZXMiLg0KYGBge3J9DQojIEZvcmVjYXN0IGZpdCBhcyBmYw0KZmMgPC0gZm9yZWNhc3QoZml0LCB4cmVnID0gcmVwKDAuMSwgNikpDQoNCiMgUGxvdCBmYyB3aXRoIHggYW5kIHkgbGFiZWxzDQphdXRvcGxvdChmYykgKyB4bGFiKCJNb250aCIpICsgeWxhYigiU2FsZXMiKQ0KYGBgDQpUaGUgZHluYW1pYyByZWdyZXNzaW9uIGFsbG93cyB5b3UgdG8gaW5jbHVkZSBvdGhlciBvdXRzaWRlIGluZm9ybWF0aW9uIGludG8geW91ciBmb3JlY2FzdC4NCg0KIyMjIEZvcmVjYXN0aW5nIGVsZWN0cmljaXR5IGRlbWFuZA0KDQpZb3UgY2FuIGFsc28gbW9kZWwgZGFpbHkgZWxlY3RyaWNpdHkgZGVtYW5kIGFzIGEgZnVuY3Rpb24gb2YgdGVtcGVyYXR1cmUuIEFzIHlvdSBtYXkgaGF2ZSBzZWVuIG9uIHlvdXIgZWxlY3RyaWMgYmlsbCwgbW9yZSBlbGVjdHJpY2l0eSBpcyB1c2VkIG9uIGhvdCBkYXlzIGR1ZSB0byBhaXIgY29uZGl0aW9uaW5nIGFuZCBvbiBjb2xkIGRheXMgZHVlIHRvIGhlYXRpbmcuDQoNCkluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIGZpdCBhIHF1YWRyYXRpYyByZWdyZXNzaW9uIG1vZGVsIHdpdGggYW4gQVJNQSBlcnJvci4gT25lIHllYXIgb2YgZGFpbHkgZGF0YSBhcmUgc3RvcmVkIGFzIGVsZWMgaW5jbHVkaW5nIHRvdGFsIGRhaWx5IGRlbWFuZCwgYW4gaW5kaWNhdG9yIHZhcmlhYmxlIGZvciB3b3JrZGF5cyAoYSB3b3JrZGF5IGlzIHJlcHJlc2VudGVkIHdpdGggMSwgYW5kIGEgbm9uLXdvcmtkYXkgaXMgcmVwcmVzZW50ZWQgd2l0aCAwKSwgYW5kIGRhaWx5IG1heGltdW0gdGVtcGVyYXR1cmVzLiBCZWNhdXNlIHRoZXJlIGlzIHdlZWtseSBzZWFzb25hbGl0eSwgdGhlIGZyZXF1ZW5jeSBoYXMgYmVlbiBzZXQgdG8gNy4NCg0KTGV0J3MgdGFrZSBhIGxvb2sgYXQgdGhlIGZpcnN0IHRocmVlIHJvd3M6DQpgYGB7cn0NCmVsZWNkYWlseVsxOjMsIF0NCmBgYA0KYGBge3J9DQpnZ3Bsb3QoYWVzKHggPSBUZW1wZXJhdHVyZSwgeSA9IERlbWFuZCksIGRhdGEgID0gYXMuZGF0YS5mcmFtZShlbGVjZGFpbHkpKSArDQogIGdlb21fcG9pbnQoKQ0KYGBgDQoNCmBgYHtyfQ0KIyBUaW1lIHBsb3RzIG9mIGRlbWFuZCBhbmQgdGVtcGVyYXR1cmVzDQphdXRvcGxvdChlbGVjZGFpbHlbLCBjKCJEZW1hbmQiLCAiVGVtcGVyYXR1cmUiKV0sIGZhY2V0cyA9IFRSVUUpDQpgYGANCkluZGV4IGVsZWMgYWNjb3JkaW5nbHkgdG8gc2V0IHVwIHRoZSBtYXRyaXggb2YgcmVncmVzc29ycyB0byBpbmNsdWRlIE1heFRlbXAgZm9yIHRoZSBtYXhpbXVtIHRlbXBlcmF0dXJlcywgTWF4VGVtcFNxIHdoaWNoIHJlcHJlc2VudHMgdGhlIHNxdWFyZWQgdmFsdWUgb2YgdGhlIG1heGltdW0gdGVtcGVyYXR1cmUsIGFuZCBXb3JrZGF5LCBpbiB0aGF0IG9yZGVyLiBDbGVhcmx5LCB0aGUgc2Vjb25kIGFyZ3VtZW50IG9mIGNiaW5kKCkgd2lsbCByZXF1aXJlIGEgc2ltcGxlIG1hdGhlbWF0aWNhbCBvcGVyYXRvci4NCmBgYHtyfQ0KIyBNYXRyaXggb2YgcmVncmVzc29ycw0KIyBNYXRyaXggb2YgcmVncmVzc29ycw0KeHJlZyA8LSBjYmluZChNYXhUZW1wID0gZWxlY2RhaWx5WywgIlRlbXBlcmF0dXJlIl0sIA0KICAgICAgICAgICAgICBNYXhUZW1wU3EgPSBlbGVjZGFpbHlbLCAiVGVtcGVyYXR1cmUiXV4yLCANCiAgICAgICAgICAgICAgV29ya2RheSA9IGVsZWNkYWlseVssICJXb3JrRGF5Il0pDQpgYGANCkZpdCBhIGR5bmFtaWMgcmVncmVzc2lvbiBtb2RlbCBvZiB0aGUgZGVtYW5kIGNvbHVtbiB3aXRoIEFSSU1BIGVycm9ycyBhbmQgY2FsbCB0aGlzIGZpdA0KYGBge3J9DQojIEZpdCBtb2RlbA0KZml0IDwtIGF1dG8uYXJpbWEoZWxlY2RhaWx5WywgIkRlbWFuZCJdLCB4cmVnID0geHJlZykNCmBgYA0KSWYgdGhlIG5leHQgZGF5IGlzIGEgd29ya2luZyBkYXkgKGluZGljYXRvciBpcyAxKSB3aXRoIG1heGltdW0gdGVtcGVyYXR1cmUgZm9yZWNhc3QgdG8gYmUgMjDCsEMsIHdoYXQgaXMgdGhlIGZvcmVjYXN0IGRlbWFuZD8gRmlsbCBvdXQgdGhlIGFwcHJvcHJpYXRlIHZhbHVlcyBpbiBjYmluZCgpIGZvciB0aGUgeHJlZyBhcmd1bWVudCBpbiBmb3JlY2FzdCgpLg0KYGBge3J9DQojIEZvcmVjYXN0IGZpdCBvbmUgZGF5IGFoZWFkDQpmb3JlY2FzdChmaXQsIHhyZWcgPSBjYmluZChNYXhUZW1wID0gMjAsIA0KICAgICAgICAgICAgICBNYXhUZW1wU3EgPSAyMF4yLCANCiAgICAgICAgICAgICAgV29ya2RheSA9IDEpKQ0KYGBgDQpOb3cgeW91J3ZlIHNlZW4gaG93IG11bHRpcGxlIGluZGVwZW5kZW50IHZhcmlhYmxlcyBjYW4gYmUgaW5jbHVkZWQgdXNpbmcgbWF0cmljZXMuDQoNCiMjIER5bmFtaWMgaGFybW9uaWMgcmVncmVzc2lvbg0KDQojIyMgRm9yZWNhc3Rpbmcgd2Vla2x5IGRhdGENCg0KV2l0aCB3ZWVrbHkgZGF0YSwgaXQgaXMgZGlmZmljdWx0IHRvIGhhbmRsZSBzZWFzb25hbGl0eSB1c2luZyBFVFMgb3IgQVJJTUEgbW9kZWxzIGFzIHRoZSBzZWFzb25hbCBsZW5ndGggaXMgdG9vIGxhcmdlIChhcHByb3hpbWF0ZWx5IDUyKS4gSW5zdGVhZCwgeW91IGNhbiB1c2UgaGFybW9uaWMgcmVncmVzc2lvbiB3aGljaCB1c2VzIHNpbmVzIGFuZCBjb3NpbmVzIHRvIG1vZGVsIHRoZSBzZWFzb25hbGl0eS4NCg0KVGhlIGZvdXJpZXIoKSBmdW5jdGlvbiBtYWtlcyBpdCBlYXN5IHRvIGdlbmVyYXRlIHRoZSByZXF1aXJlZCBoYXJtb25pY3MuIFRoZSBoaWdoZXIgdGhlIG9yZGVyIChLKSwgdGhlIG1vcmUgIndpZ2dseSIgdGhlIHNlYXNvbmFsIHBhdHRlcm4gaXMgYWxsb3dlZCB0byBiZS4gV2l0aCBLPTEsIGl0IGlzIGEgc2ltcGxlIHNpbmUgY3VydmUuIFlvdSBjYW4gc2VsZWN0IHRoZSB2YWx1ZSBvZiBLIGJ5IG1pbmltaXppbmcgdGhlIEFJQ2MgdmFsdWUuIGZvdXJpZXIoKSB0YWtlcyBpbiBhIHJlcXVpcmVkIHRpbWUgc2VyaWVzLCByZXF1aXJlZCBudW1iZXIgb2YgRm91cmllciB0ZXJtcyB0byBnZW5lcmF0ZSwgYW5kIG9wdGlvbmFsIG51bWJlciBvZiByb3dzIGl0IG5lZWRzIHRvIGZvcmVjYXN0Og0KDQogICAgIyBmb3VyaWVyKHgsIEssIGggPSBOVUxMKQ0KICAgIA0KICAgID4gZml0IDwtIGF1dG8uYXJpbWEoY2FmZSwgeHJlZyA9IGZvdXJpZXIoY2FmZSwgSyA9IDYpLA0KICAgICAgICAgICAgICAgICAgICAgICAgc2Vhc29uYWwgPSBGQUxTRSwgbGFtYmRhID0gMCkNCiAgICA+IGZpdCAlPiUNCiAgICAgICAgZm9yZWNhc3QoeHJlZyA9IGZvdXJpZXIoY2FmZSwgSyA9IDYsIGggPSAyNCkpICU+JQ0KICAgICAgICBhdXRvcGxvdCgpICsgeWxpbSgxLjYsIDUuMSkNCg0KZ2Fzb2xpbmUgZGF0YSBjb21wcmlzZXMgd2Vla2x5IGRhdGEgb24gVVMgZmluaXNoZWQgbW90b3IgZ2Fzb2xpbmUgcHJvZHVjdHMuIEluIHRoaXMgZXhlcmNpc2UsIHlvdSB3aWxsIGZpdCBhIGhhcm1vbmljIHJlZ3Jlc3Npb24gdG8gdGhpcyBkYXRhIHNldCBhbmQgZm9yZWNhc3QgdGhlIG5leHQgMyB5ZWFycy4NCmBgYHtyfQ0KIyBTZXQgdXAgaGFybW9uaWMgcmVncmVzc29ycyBvZiBvcmRlciAxMw0KaGFybW9uaWNzIDwtIGZvdXJpZXIoZ2Fzb2xpbmUsIEsgPSAxMykNCg0KIyBGaXQgcmVncmVzc2lvbiBtb2RlbCB3aXRoIEFSSU1BIGVycm9ycw0KZml0IDwtIGF1dG8uYXJpbWEoZ2Fzb2xpbmUsIHhyZWcgPSBoYXJtb25pY3MsIHNlYXNvbmFsID0gRkFMU0UpDQoNCiMgRm9yZWNhc3RzIG5leHQgMyB5ZWFycw0KbmV3aGFybW9uaWNzIDwtIGZvdXJpZXIoZ2Fzb2xpbmUsIEsgPSAxMywgaCA9IDUyKjMpDQpmYyA8LSBmb3JlY2FzdChmaXQsIHhyZWcgPSBuZXdoYXJtb25pY3MpDQoNCiMgUGxvdCBmb3JlY2FzdHMgZmMNCmF1dG9wbG90KGZjKQ0KYGBgDQpUaGUgcG9pbnQgcHJlZGljdGlvbnMgbG9vayB0byBiZSBhIGJpdCBsb3cuDQoNCiMjIyBIYXJtb25pYyByZWdyZXNzaW9uIGZvciBtdWx0aXBsZSBzZWFzb25hbGl0eQ0KDQpIYXJtb25pYyByZWdyZXNzaW9ucyBhcmUgYWxzbyB1c2VmdWwgd2hlbiB0aW1lIHNlcmllcyBoYXZlIG11bHRpcGxlIHNlYXNvbmFsIHBhdHRlcm5zLiBGb3IgZXhhbXBsZSwgdGF5bG9yIGNvbnRhaW5zIGhhbGYtaG91cmx5IGVsZWN0cmljaXR5IGRlbWFuZCBpbiBFbmdsYW5kIGFuZCBXYWxlcyBvdmVyIGEgZmV3IG1vbnRocyBpbiB0aGUgeWVhciAyMDAwLiBUaGUgc2Vhc29uYWwgcGVyaW9kcyBhcmUgNDggKGRhaWx5IHNlYXNvbmFsaXR5KSBhbmQgNyB4IDQ4ID0gMzM2ICh3ZWVrbHkgc2Vhc29uYWxpdHkpLiBUaGVyZSBpcyBub3QgZW5vdWdoIGRhdGEgdG8gY29uc2lkZXIgYW5udWFsIHNlYXNvbmFsaXR5Lg0KDQphdXRvLmFyaW1hKCkgd291bGQgdGFrZSBhIGxvbmcgdGltZSB0byBmaXQgYSBsb25nIHRpbWUgc2VyaWVzIHN1Y2ggYXMgdGhpcyBvbmUsIHNvIGluc3RlYWQgeW91IHdpbGwgZml0IGEgc3RhbmRhcmQgcmVncmVzc2lvbiBtb2RlbCB3aXRoIEZvdXJpZXIgdGVybXMgdXNpbmcgdGhlIHRzbG0oKSBmdW5jdGlvbi4gVGhpcyBpcyB2ZXJ5IHNpbWlsYXIgdG8gbG0oKSBidXQgaXMgZGVzaWduZWQgdG8gaGFuZGxlIHRpbWUgc2VyaWVzLiBXaXRoIG11bHRpcGxlIHNlYXNvbmFsaXR5LCB5b3UgbmVlZCB0byBzcGVjaWZ5IHRoZSBvcmRlciBLIGZvciBlYWNoIG9mIHRoZSBzZWFzb25hbCBwZXJpb2RzLg0KDQogICAgIyBUaGUgZm9ybXVsYSBhcmd1bWVudCBpcyBhIHN5bWJvbGljIGRlc2NyaXB0aW9uDQogICAgIyBvZiB0aGUgbW9kZWwgdG8gYmUgZml0dGVkDQogICAgDQogICAgPiBhcmdzKHRzbG0pDQogICAgZnVuY3Rpb24gKGZvcm11bGEsIC4uLikNCg0KdHNsbSgpIGlzIGEgbmV3bHkgaW50cm9kdWNlZCBmdW5jdGlvbiwgc28geW91IHNob3VsZCBiZSBhYmxlIHRvIGZvbGxvdyB0aGUgcHJlLXdyaXR0ZW4gY29kZSBmb3IgdGhlIG1vc3QgcGFydC4gDQpgYGB7cn0NCiMgRml0IGEgaGFybW9uaWMgcmVncmVzc2lvbiB1c2luZyBvcmRlciAxMCBmb3IgZWFjaCB0eXBlIG9mIHNlYXNvbmFsaXR5DQpmaXQgPC0gdHNsbSh0YXlsb3IgfiBmb3VyaWVyKHRheWxvciwgSyA9IGMoMTAsIDEwKSkpDQoNCiMgRm9yZWNhc3QgMjAgd29ya2luZyBkYXlzIGFoZWFkDQpmYyA8LSBmb3JlY2FzdChmaXQsIG5ld2RhdGEgPSBkYXRhLmZyYW1lKGZvdXJpZXIodGF5bG9yLCBLID0gYygxMCwgMTApLCBoID0gNDgqMjApKSkNCg0KIyBQbG90IHRoZSBmb3JlY2FzdHMNCmF1dG9wbG90KGZjKQ0KDQojIENoZWNrIHRoZSByZXNpZHVhbHMgb2YgZml0DQpjaGVja3Jlc2lkdWFscyhmaXQpDQpgYGANClRoZSByZXNpZHVhbHMgZnJvbSB0aGUgZml0dGVkIG1vZGVsIGZhaWwgdGhlIHRlc3RzIGJhZGx5LCB5ZXQgdGhlIGZvcmVjYXN0cyBhcmUgcXVpdGUgZ29vZC4NCg0KIyMjIEZvcmVjYXN0aW5nIGNhbGwgYm9va2luZ3MNCg0KQW5vdGhlciB0aW1lIHNlcmllcyB3aXRoIG11bHRpcGxlIHNlYXNvbmFsIHBlcmlvZHMgaXMgY2FsbHMsIHdoaWNoIGNvbnRhaW5zIDIwIGNvbnNlY3V0aXZlIGRheXMgb2YgNS1taW51dGUgY2FsbCB2b2x1bWUgZGF0YSBmb3IgYSBsYXJnZSBOb3J0aCBBbWVyaWNhbiBiYW5rLiBUaGVyZSBhcmUgMTY5IDUtbWludXRlIHBlcmlvZHMgaW4gYSB3b3JraW5nIGRheSwgYW5kIHNvIHRoZSB3ZWVrbHkgc2Vhc29uYWwgZnJlcXVlbmN5IGlzIDUgeCAxNjkgPSA4NDUuIFRoZSB3ZWVrbHkgc2Vhc29uYWxpdHkgaXMgcmVsYXRpdmVseSB3ZWFrLCBzbyBoZXJlIHlvdSB3aWxsIGp1c3QgbW9kZWwgZGFpbHkgc2Vhc29uYWxpdHkuIGNhbGxzIGlzIHByZS1sb2FkZWQgaW50byB5b3VyIHdvcmtzcGFjZS4NCg0KVGhlIHJlc2lkdWFscyBpbiB0aGlzIGNhc2Ugc3RpbGwgZmFpbCB0aGUgd2hpdGUgbm9pc2UgdGVzdHMsIGJ1dCB0aGVpciBhdXRvY29ycmVsYXRpb25zIGFyZSB0aW55LCBldmVuIHRob3VnaCB0aGV5IGFyZSBzaWduaWZpY2FudC4gVGhpcyBpcyBiZWNhdXNlIHRoZSBzZXJpZXMgaXMgc28gbG9uZy4gSXQgaXMgb2Z0ZW4gdW5yZWFsaXN0aWMgdG8gaGF2ZSByZXNpZHVhbHMgdGhhdCBwYXNzIHRoZSB0ZXN0cyBmb3Igc3VjaCBsb25nIHNlcmllcy4gVGhlIGVmZmVjdCBvZiB0aGUgcmVtYWluaW5nIGNvcnJlbGF0aW9ucyBvbiB0aGUgZm9yZWNhc3RzIHdpbGwgYmUgbmVnbGlnaWJsZS4NCmBgYHtyfQ0KIyBQbG90IHRoZSBjYWxscyBkYXRhDQphdXRvcGxvdChjYWxscykNCmBgYA0KU2V0IHVwIHRoZSB4cmVnIG1hdHJpeCB1c2luZyBvcmRlciAxMCBmb3IgZGFpbHkgc2Vhc29uYWxpdHkgYW5kIDAgZm9yIHdlZWtseSBzZWFzb25hbGl0eS4gTm90ZSB0aGF0IGlmIHlvdSBpbmNvcnJlY3RseSBzcGVjaWZ5IHlvdXIgdmVjdG9yLCB5b3VyIHNlc3Npb24gbWF5IGV4cGlyZSENCg0KRml0IGEgZHluYW1pYyByZWdyZXNzaW9uIG1vZGVsIGNhbGxlZCBmaXQgdXNpbmcgYXV0by5hcmltYSgpIHdpdGggc2Vhc29uYWwgPSBGQUxTRSBhbmQgc3RhdGlvbmFyeSA9IFRSVUUuDQpgYGB7cn0NCiMgU2V0IHVwIHRoZSB4cmVnIG1hdHJpeA0KeHJlZyA8LSBmb3VyaWVyKGNhbGxzLCBLID0gYygxMCwgMCkpDQoNCiMgRml0IGEgZHluYW1pYyByZWdyZXNzaW9uIG1vZGVsDQpmaXQgPC0gYXV0by5hcmltYShjYWxscywgeHJlZyA9IHhyZWcsIHNlYXNvbmFsID0gRkFMU0UsIHN0YXRpb25hcnkgPSBUUlVFKQ0KDQojIENoZWNrIHRoZSByZXNpZHVhbHMNCmNoZWNrcmVzaWR1YWxzKGZpdCkNCg0KIyBQbG90IGZvcmVjYXN0cyBmb3IgMTAgd29ya2luZyBkYXlzIGFoZWFkDQpmYyA8LSBmb3JlY2FzdChmaXQsIHhyZWcgPSAgZm91cmllcihjYWxscywgYygxMCwgMCksIGggPSAxMCoxNjkpKQ0KYXV0b3Bsb3QoZmMpDQpgYGANCiMjIFRCQVRTIG1vZGVscw0KDQoNCkEgVEJBVFMgbW9kZWwgaXMgYSBzcGVjaWFsIGtpbmQgb2YgdGltZSBzZXJpZXMgbW9kZWwuIEl0IGNhbiBiZSB2ZXJ5IHNsb3cgdG8gZXN0aW1hdGUsIGVzcGVjaWFsbHkgd2l0aCBtdWx0aXBsZSBzZWFzb25hbCB0aW1lIHNlcmllcywgc28gaW4gdGhpcyBleGVyY2lzZSB5b3Ugd2lsbCB0cnkgaXQgb24gYSBzaW1wbGVyIHNlcmllcyB0byBzYXZlIHRpbWUuIExldCdzIGJyZWFrIGRvd24gZWxlbWVudHMgb2YgYSBUQkFUUyBtb2RlbCBpbiBUQkFUUygxLCB7MCwwfSwgLSwgezw1MS4xOCwxND59KQ0KDQpDb21wb25lbnR8TWVhbmluZw0KLS0tLS0tLS0tfC0tLS0tLS0NCjEJQm94LUNveHx0cmFuc2Zvcm1hdGlvbiBwYXJhbWV0ZXINCnswLDB9fEFSTUEgZXJyb3INCi18RGFtcGluZyBwYXJhbWV0ZXINCntcPDUxLjE4LDE0Pn18U2Vhc29uYWwgcGVyaW9kLCBGb3VyaWVyIHRlcm1zDQoNClRoZSBnYXMgZGF0YSBjb250YWlucyBBdXN0cmFsaWFuIG1vbnRobHkgZ2FzIHByb2R1Y3Rpb24uIEEgcGxvdCBvZiB0aGUgZGF0YSBzaG93cyB0aGUgdmFyaWFuY2UgaGFzIGNoYW5nZWQgYSBsb3Qgb3ZlciB0aW1lLCBzbyBpdCBuZWVkcyBhIHRyYW5zZm9ybWF0aW9uLiBUaGUgc2Vhc29uYWxpdHkgaGFzIGFsc28gY2hhbmdlZCBzaGFwZSBvdmVyIHRpbWUsIGFuZCB0aGVyZSBpcyBhIHN0cm9uZyB0cmVuZC4gVGhpcyBtYWtlcyBpdCBhbiBpZGVhbCBzZXJpZXMgdG8gdGVzdCB0aGUgdGJhdHMoKSBmdW5jdGlvbiB3aGljaCBpcyBkZXNpZ25lZCB0byBoYW5kbGUgdGhlc2UgZmVhdHVyZXMuDQoNCmBgYHtyfQ0KIyBQbG90IHRoZSBnYXMgZGF0YQ0KYXV0b3Bsb3QoZ2FzKQ0KDQojIEZpdCBhIFRCQVRTIG1vZGVsIHRvIHRoZSBnYXMgZGF0YQ0KZml0IDwtIHRiYXRzKGdhcykNCg0KIyBGb3JlY2FzdCB0aGUgc2VyaWVzIGZvciB0aGUgbmV4dCA1IHllYXJzDQpmYyA8LSBmb3JlY2FzdChmaXQsIGggPSAxMio1KQ0KDQojIFBsb3QgdGhlIGZvcmVjYXN0cw0KYXV0b3Bsb3QoZmMpDQpgYGANCmBgYHtyfQ0KIyBSZWNvcmQgdGhlIEJveC1Db3ggcGFyYW1ldGVyIGFuZCB0aGUgb3JkZXIgb2YgdGhlIEZvdXJpZXIgdGVybXMNCmxhbWJkYSA8LSAwLjA4Mg0KSyA8LSA1DQpgYGANCg0KSnVzdCByZW1lbWJlciB0aGF0IGNvbXBsZXRlbHkgYXV0b21hdGVkIHNvbHV0aW9ucyBkb24ndCB3b3JrIGV2ZXJ5IHRpbWUuDQo=