This is an R Markdown Notebook. When you execute code within the notebook, the results appear beneath the code.

Try executing this chunk by clicking the Run button within the chunk or by placing your cursor inside it and pressing Ctrl+Shift+Enter.

Add a new chunk by clicking the Insert Chunk button on the toolbar or by pressing Ctrl+Alt+I.

When you save the notebook, an HTML file containing the code and output will be saved alongside it (click the Preview button or press Ctrl+Shift+K to preview the HTML file).

Customer Lifetime Value (CLV)

Customer Lifetime Value is “the present value of the future cash flows attributed to the customer during his/her entire relationship with the company.” There are different kinds of formulas, from simplified to advanced, to calculate CLV. But the following one might be the one being used most commonly:

where,

Here we assume that \({r}\) is constant in the formula; however, it is not always the case. The factors which influence \({r}\) include demographics (age, geography, and profession etc), behavior (Recency, Frequency, Monetary, etc), tenure, competition, etc. There are some improved formulas which forecast the \({r}\) by different approaches such as Logistic Regression.

We will demonstrate how to use R and calculate a customer’s CLV by predicting the retention/repurchasing rate \({r}\) of customers in each future purchasing cycle time with the Logistic Regression model based on the predictors of Recency, Frequency, and Monetary.

Data Set

We will use the CDNow full example data set for concrete case study to build the above model.

There are 23570 distinct customers who made their first purchase at CDNOW in the first quarter of 1997 in the sample data. There are a total of 69,659 transaction records, which occurred during the period of the start of Jan 1997 to the end of June 1998.

Exploring the relationships between Repurchase Rate and Recency, Frequency, and Monetary

First, we calculate the number of customers grouped by Recency values, and then further group them into “Buy” and “No Buy” according to the data in the next purchasing cycle time, and finally get the percentage of customers who repurchase in a certain Recency value in the next period. Here we leverage the R language function “ddply” to complete the grouping and calculating work. Below is a list pairs of percentage and Recency value we calculated. Please note that the less the Recency value is, the more recent the purchasing takes place.

Next, we will remove the record before the start date and end date.

str(df)
'data.frame':   69659 obs. of  4 variables:
 $ V1: int  1 2 2 3 3 3 3 3 3 4 ...
 $ V2: int  19970101 19970112 19970112 19970102 19970330 19970402 19971115 19971125 19980528 19970101 ...
 $ V3: int  1 1 5 2 2 2 5 4 1 2 ...
 $ V4: num  11.8 12 77 20.8 20.8 ...

Let’s construct the data frame and rename the column variables, and verify the changes.

'data.frame':   69659 obs. of  3 variables:
 $ ID    : num  1 2 2 3 3 3 3 3 3 4 ...
 $ Date  : num  2e+07 2e+07 2e+07 2e+07 2e+07 ...
 $ Amount: num  11.8 12 77 20.8 20.8 ...
str(df)

Next, we’ll go ahead and covert the Date column to Date variable type:

str(df)
'data.frame':   69659 obs. of  3 variables:
 $ ID    : num  1 2 2 3 3 3 3 3 3 4 ...
 $ Date  : Date, format: "1997-01-01" "1997-01-12" "1997-01-12" "1997-01-02" ...
 $ Amount: num  11.8 12 77 20.8 20.8 ...
#  set the "forecast" transaction time scope which are a bi-month purchasing cycle time
startDate_forcast <- as.Date("19980301","%Y%m%d")
endDate_forcast <- as.Date("19980430","%Y%m%d")
#get the rolled up R,F,M data frames
history <- getDataFrame(df,startDate_history,endDate_history)
forcast <- getDataFrame(df,startDate_forcast,endDate_forcast)
# set the purchasing cycle time as 60 days, and discrete the Recency 
history$Recency<- history$Recency %/% 60 
#discrete the Monetary by $10 interval
breaks<-seq(0,round(max(history$Monetary)+9),by=10)
history$Monetary<-as.numeric(cut(history$Monetary,breaks,labels=FALSE))
#add a Buy/No Buy column to the RFM data frame
Buy<-rep(0,nrow(history))
history<-cbind(history,Buy)
# find out the those who repurchased in the forcast period 19980301 - 19980430
history[history$ID %in% forcast$ID, ]$Buy<-1
train<-history
head(train)
# get "Buy" percentages based on the variable Recency
colNames<-c("Recency")
p<-getPercentages(train,colNames)
# get the Buy ~ Recency model
r.glm=glm(Percentage~Recency,family=quasibinomial(link='logit'),data=p)
p_r<-p
# get "Buy" percentages based on the variable Frequency
colNames<-c("Frequency")
p<-getPercentages(train,colNames)
# get the Buy ~ Frequency model
f.glm=glm(Percentage~Frequency,family=quasibinomial(link='logit'),data=p)
p_f<-p
# get "Buy" percentages based on the variable Monetary
colNames<-c("Monetary")
p<-getPercentages(train,colNames)
# get the Buy ~ Monetary model
m.glm=glm(Percentage~Monetary,family=quasibinomial(link='logit'),data=p)
p_m<-p
#plot and draw fit curves of Percentage ~ r,f,m
par(mfrow=c(1,3),oma=c(0,0,2,0))
plot(p_r$Recency,p_r$Percentage*100,xlab="Recency",ylab="Probablity of Purchasing(%)")
lines(lowess(p_r$Recency,p_r$Percentage*100),col="blue",lty=2)

plot(p_f$Frequency,p_f$Percentage*100,xlab="Frequency",ylab="Probablity of Purchasing(%)")
lines(lowess(p_f$Frequency,p_f$Percentage*100),col="blue",lty=2)

plot(p_m$Monetary,p_m$Percentage*100,xlab="Monetary",ylab="Probablity of Purchasing(%)")
lines(lowess(p_m$Monetary,p_m$Percentage*100),col="blue",lty=2)
title("Percentages ~ Recency, Frequency, Monetary", y=10,outer=TRUE)

par(mfrow=c(1,1))
model<-glm(Buy~Recency+Frequency,family=quasibinomial(link='logit'),data=train)
pred<-predict(model,data.frame(Recency=c(0),Frequency=c(1)),type='response')
## caculating the CLV for a customer with R=0,F=1,average profit=100,discount rate=0.02 for 3 periods
v<-getCLV(0,1,100,1,0,3,0.02,model)
v
[1] 63.91906
LS0tDQp0aXRsZTogIkN1c3RvbWVyIExpZmV0aW1lIFZhbHVlIChDTFYpIg0KYXV0aG9yOiBIb2EgSy4gUXVhY2gNCm91dHB1dDogaHRtbF9ub3RlYm9vaw0KLS0tDQoNClRoaXMgaXMgYW4gW1IgTWFya2Rvd25dKGh0dHA6Ly9ybWFya2Rvd24ucnN0dWRpby5jb20pIE5vdGVib29rLiBXaGVuIHlvdSBleGVjdXRlIGNvZGUgd2l0aGluIHRoZSBub3RlYm9vaywgdGhlIHJlc3VsdHMgYXBwZWFyIGJlbmVhdGggdGhlIGNvZGUuIA0KDQpUcnkgZXhlY3V0aW5nIHRoaXMgY2h1bmsgYnkgY2xpY2tpbmcgdGhlICpSdW4qIGJ1dHRvbiB3aXRoaW4gdGhlIGNodW5rIG9yIGJ5IHBsYWNpbmcgeW91ciBjdXJzb3IgaW5zaWRlIGl0IGFuZCBwcmVzc2luZyAqQ3RybCtTaGlmdCtFbnRlciouIA0KDQpBZGQgYSBuZXcgY2h1bmsgYnkgY2xpY2tpbmcgdGhlICpJbnNlcnQgQ2h1bmsqIGJ1dHRvbiBvbiB0aGUgdG9vbGJhciBvciBieSBwcmVzc2luZyAqQ3RybCtBbHQrSSouDQoNCldoZW4geW91IHNhdmUgdGhlIG5vdGVib29rLCBhbiBIVE1MIGZpbGUgY29udGFpbmluZyB0aGUgY29kZSBhbmQgb3V0cHV0IHdpbGwgYmUgc2F2ZWQgYWxvbmdzaWRlIGl0IChjbGljayB0aGUgKlByZXZpZXcqIGJ1dHRvbiBvciBwcmVzcyAqQ3RybCtTaGlmdCtLKiB0byBwcmV2aWV3IHRoZSBIVE1MIGZpbGUpLg0KDQoNCiNDdXN0b21lciBMaWZldGltZSBWYWx1ZSAoQ0xWKQ0KDQpDdXN0b21lciBMaWZldGltZSBWYWx1ZSBpcyAidGhlIHByZXNlbnQgdmFsdWUgb2YgdGhlIGZ1dHVyZSBjYXNoIGZsb3dzIGF0dHJpYnV0ZWQgdG8gdGhlIGN1c3RvbWVyIGR1cmluZyBoaXMvaGVyIGVudGlyZSByZWxhdGlvbnNoaXAgd2l0aCB0aGUgY29tcGFueS4iIFRoZXJlIGFyZSBkaWZmZXJlbnQga2luZHMgb2YgZm9ybXVsYXMsIGZyb20gc2ltcGxpZmllZCB0byBhZHZhbmNlZCwgdG8gY2FsY3VsYXRlIENMVi4gIEJ1dCB0aGUgZm9sbG93aW5nIG9uZSBtaWdodCBiZSB0aGUgb25lIGJlaW5nIHVzZWQgbW9zdCBjb21tb25seToNCg0KDQohW10oaHR0cDovL3d3dy5ob2FxdWFjaC5jb20vaW1hZ2VzL290aGVyL0NMVi5wbmcpDQoNCg0Kd2hlcmUsDQoNCiogJHt0fSQgaXMgYSB0aW1lIHBlcmlvZCwgZS5nLiB0aGUgZmlyc3QgeWVhcigke3R9JD0xKSwgdGhlIHNlY29uZCB5ZWFyKCR7dH0kPTIpDQoNCiogJHtufSQgaXMgdGhlIHRvdGFsIG51bWJlciBvZiBwZXJpb2RzIHRoZSBjdXN0b21lciB3aWxsIHN0YXkgYmVmb3JlIGhlL3NoZSBmaW5hbGx5IGNodXJucw0KDQoqICR7cn0kIGlzIHRoZSByZXRlbnRpb24gcmF0ZS9wb3NzaWJpbGl0eQ0KDQoqICRwX3tpfSQgaXMgdGhlIHByb2ZpdCB0aGUgY3VzdG9tZXIgd2lsbCBjb250cmlidXRlIGluIHRoZSBQZXJpb2QgdA0KDQoqICR7ZH0kIGlzIHRoZSBkaXNjb3VudCByYXRlDQoNCkhlcmUgd2UgYXNzdW1lIHRoYXQgJHtyfSQgaXMgY29uc3RhbnQgaW4gdGhlIGZvcm11bGE7IGhvd2V2ZXIsIGl0IGlzIG5vdCBhbHdheXMgdGhlIGNhc2UuIFRoZSBmYWN0b3JzIHdoaWNoIGluZmx1ZW5jZSAke3J9JCBpbmNsdWRlIGRlbW9ncmFwaGljcyAoYWdlLCBnZW9ncmFwaHksIGFuZCBwcm9mZXNzaW9uIGV0YyksIGJlaGF2aW9yIChSZWNlbmN5LCBGcmVxdWVuY3ksIE1vbmV0YXJ5LCBldGMpLCB0ZW51cmUsIGNvbXBldGl0aW9uLCBldGMuIFRoZXJlIGFyZSBzb21lIGltcHJvdmVkIGZvcm11bGFzIHdoaWNoIGZvcmVjYXN0IHRoZSAke3J9JCBieSBkaWZmZXJlbnQgYXBwcm9hY2hlcyBzdWNoIGFzIExvZ2lzdGljIFJlZ3Jlc3Npb24uDQoNCldlIHdpbGwgZGVtb25zdHJhdGUgaG93IHRvIHVzZSBSIGFuZCBjYWxjdWxhdGUgYSBjdXN0b21lcidzIENMViBieSBwcmVkaWN0aW5nIHRoZSByZXRlbnRpb24vcmVwdXJjaGFzaW5nIHJhdGUgJHtyfSQgb2YgY3VzdG9tZXJzIGluIGVhY2ggZnV0dXJlIHB1cmNoYXNpbmcgY3ljbGUgdGltZSB3aXRoIHRoZSBMb2dpc3RpYyBSZWdyZXNzaW9uIG1vZGVsIGJhc2VkIG9uIHRoZSBwcmVkaWN0b3JzIG9mICoqUmVjZW5jeSoqLCAqKkZyZXF1ZW5jeSoqLCBhbmQgKipNb25ldGFyeSoqLg0KDQojRGF0YSBTZXQNCg0KV2Ugd2lsbCB1c2UgdGhlIENETm93IGZ1bGwgZXhhbXBsZSBkYXRhIHNldCBmb3IgY29uY3JldGUgY2FzZSBzdHVkeSB0byBidWlsZCB0aGUgYWJvdmUgbW9kZWwuDQoNClRoZXJlIGFyZSAyMzU3MCBkaXN0aW5jdCBjdXN0b21lcnMgd2hvIG1hZGUgdGhlaXIgZmlyc3QgcHVyY2hhc2UgYXQgQ0ROT1cgaW4gdGhlIGZpcnN0IHF1YXJ0ZXIgb2YgMTk5NyBpbiB0aGUgc2FtcGxlIGRhdGEuIFRoZXJlIGFyZSBhIHRvdGFsIG9mIDY5LDY1OSB0cmFuc2FjdGlvbiByZWNvcmRzLCB3aGljaCBvY2N1cnJlZCBkdXJpbmcgdGhlIHBlcmlvZCBvZiB0aGUgc3RhcnQgb2YgSmFuIDE5OTcgdG8gdGhlIGVuZCBvZiBKdW5lIDE5OTguDQoNCiNFeHBsb3JpbmcgdGhlIHJlbGF0aW9uc2hpcHMgYmV0d2VlbiBSZXB1cmNoYXNlIFJhdGUgYW5kIFJlY2VuY3ksIEZyZXF1ZW5jeSwgYW5kIE1vbmV0YXJ5DQoNCkZpcnN0LCB3ZSBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiBjdXN0b21lcnMgZ3JvdXBlZCBieSBSZWNlbmN5IHZhbHVlcywgYW5kIHRoZW4gZnVydGhlciBncm91cCB0aGVtIGludG8gIkJ1eSIgYW5kICJObyBCdXkiIGFjY29yZGluZyB0byB0aGUgZGF0YSBpbiB0aGUgbmV4dCBwdXJjaGFzaW5nIGN5Y2xlIHRpbWUsIGFuZCBmaW5hbGx5IGdldCB0aGUgcGVyY2VudGFnZSBvZiBjdXN0b21lcnMgd2hvIHJlcHVyY2hhc2UgaW4gYSBjZXJ0YWluIFJlY2VuY3kgdmFsdWUgaW4gdGhlIG5leHQgcGVyaW9kLiBIZXJlIHdlIGxldmVyYWdlIHRoZSBSIGxhbmd1YWdlIGZ1bmN0aW9uICJkZHBseSIgdG8gY29tcGxldGUgdGhlIGdyb3VwaW5nIGFuZCBjYWxjdWxhdGluZyB3b3JrLiBCZWxvdyBpcyBhIGxpc3QgcGFpcnMgb2YgcGVyY2VudGFnZSBhbmQgUmVjZW5jeSB2YWx1ZSB3ZSBjYWxjdWxhdGVkLiBQbGVhc2Ugbm90ZSB0aGF0IHRoZSBsZXNzIHRoZSBSZWNlbmN5IHZhbHVlIGlzLCB0aGUgbW9yZSByZWNlbnQgdGhlIHB1cmNoYXNpbmcgdGFrZXMgcGxhY2UuDQoNCk5leHQsIHdlIHdpbGwgcmVtb3ZlIHRoZSByZWNvcmQgYmVmb3JlIHRoZSBzdGFydCBkYXRlIGFuZCBlbmQgZGF0ZS4NCg0KDQpgYGB7ciBldmFsPVRSVUUsIGVjaG89RkFMU0V9DQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KIyBGdW5jdGlvbg0KIyAJZ2V0RGF0YUZyYW1lKGRmLHN0YXJ0RGF0ZSxlbmREYXRlLHRJRENvbE5hbWU9IklEIix0RGF0ZUNvbE5hbWU9IkRhdGUiLHRBbW91bnRDb2xOYW1lPSJBbW91bnQiKQ0KIw0KIyBEZXNjcmlwdGlvbg0KIwlQcm9jZXNzIHRoZSBpbnB1dCBkYXRhIGZyYW1lIG9mIHRyYW5zY2F0aW9uIHJlY29yZHMgc28gdGhhdCB0aGUgZGF0YSBmcmFtZSBjYW4gYmUgcmVhZHkgZm9yIFJGTSBzY29yaW5nLg0KIwlBLlJlbW92ZSB0aGUgZHVwbGljYXRlIHJlY29yZHMgd2l0aCB0aGUgc2FtZSBjdXN0b21lciBJRA0KIwlCLkZpbmQgdGhlIG1vc3QgcmVjZW50IGRhdGUgZm9yIGVhY2ggSUQgYW5kIGNhbGN1bGF0ZSB0aGUgZGF5cyB0byB0aGUgZW5kRGF0ZSwgdG8gZ2V0IHRoZSBSZWNlbmN5IGRhdGENCiMJQy5DYWxjdWxhdGUgdGhlIHF1YW50aXR5IG9mIHRyYW5zbGF0aW9ucyBvZiBhIGN1c3RvbWVyLCB0byBnZXQgdGhlIEZyZXF1ZW5jeSBkYXRhDQojCUQuU3VtIHRoZSBhbW91bnQgb2YgbW9uZXkgYSBjdXN0b21lciBzcGVudCBhbmQgZGl2aWRlIGl0IGJ5IEZyZXF1ZW5jeSwgdG8gZ2V0IHRoZSBhdmVyYWdlIGFtb3VudCBwZXIgdHJhbnNhY3Rpb24sIHRoYXQgaXMgI3RoZSBNb25ldGFyeSBkYXRhLg0KIw0KIyBBcmd1bWVudHMNCiMJZGYgLSBBIGRhdGEgZnJhbWUgb2YgdHJhbnNjYXRpb24gcmVjb3JkcyB3aXRoIGN1c3RvbWVyIElELCBkYXRlcywgYW5kIHRoZSBhbW91bnQgb2YgbW9uZXkgb2YgZWFjaCB0cmFuc2F0aW9uDQojCXN0YXJ0RGF0ZSAtIHRoZSBzdGFydCBkYXRlIG9mIHRyYW5zY2F0aW9uLCB0aGUgcmVjb3JkcyB0aGF0IGhhcHBlbmVkIGFmdGVyIHRoZSBzdGFydCBkYXRlIHdpbGwgYmUga2VwdGVkDQojCWVuZERhdGUgLSB0aGUgZW5kIGRhdGUgb2YgdHJhbnNjYXRpb24sIHRoZSByZWNvcmRzIHRoYXQgaGFwcGVkIGFmdGVyIHRoZSBlbmQgZGF0ZSB3aWxsIGJlIHJlbW92ZWQuIEl0IHdvcmtzIHdpdGggdGhlIHN0YXJ0ICNkYXRlIHRvIHNldCBhIHRpbWUgc2NvcGUNCiMJdElEQ29sTmFtZSAtIHRoZSBjb2x1bW4gbmFtZSB3aGljaCBjb250YWlucyBjdXN0b21lciBJRHMgaW4gdGhlIGlucHV0IGRhdGEgZnJhbWUNCiMJdERhdGVDb2xOYW1lIC0gdGhlIGNvbHVtbiBuYW1lIHdoaWNoIGNvbnRhaW5zIHRyYW5zY2F0aW9uIGRhdGVzIGluIHRoZSBpbnB1dCBkYXRhIGZyYW1lDQojCXRBbW91bnRDb2xOYW1lIC0gdGhlIGNvbHVtbiBuYW1lIHdoaWNoIGNvbnRhaW5zIHRoZSBhbW91bnQgb2YgbW9uZXkgb2YgZWFjaCB0cmFuc2NhdGlvbiBpbiB0aGUgaW5wdXQgZGF0YSBmcmFtZQ0KIw0KIyBSZXR1cm4gVmFsdWUNCiMJUmV0dXJucyBhIG5ldyBkYXRhIGZyYW1lIHdpdGggdGhyZWUgbmV3IGNvbHVtbnMgb2YgIlJlY2VuY3kiLCJGcmVxdWVuY3kiLCBhbmQgIk1vbmV0YXJ5Ii4gVGhlIG51bWJlciBpbiAiUmVjZW5jeSIgaXMgdGhlICMgcXVhbnRpdHkgb2YgZGF5cyBmcm9tIHRoZSAjICNtb3N0IHJlY2VudCB0cmFuc2NhdGlvbiBvZiBhIGN1c3RvbWVyIHRvIHRoZSBlbmREYXRlOyBUaGUgbnVtYmVyIGluIHRoZSAiRnJlcXVlbmN5IiBpcyB0aGUgcXVhbnRpdHkgIyBvZiB0cmFuc2NhdGlvbnMgb2YgYSBjdXN0b21lciBkdXJpbmcgdGhlIHBlcmlvZCBmcm9tICMgI3N0YXJ0RGF0ZSB0byBlbmREYXRlOyB0aGUgbnVtYmVyIGluIHRoZSAiTW9uZXRhcnkiIGlzIHRoZSBhdmVyYWdlIGFtb3VudCAjIG9mIG1vbmV5IHBlciB0cmFuc2NhdGlvbiBvZiBhIGN1c3RvbWVyIGR1cmluZyB0aGF0IHBlcmlvZC4NCiMNCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIw0KDQpnZXREYXRhRnJhbWUgPC0gZnVuY3Rpb24oZGYsc3RhcnREYXRlLGVuZERhdGUsdElEQ29sTmFtZT0iSUQiLHREYXRlQ29sTmFtZT0iRGF0ZSIsdEFtb3VudENvbE5hbWU9IkFtb3VudCIpew0KDQojb3JkZXIgdGhlIGRhdGFmcmFtZSBieSBkYXRlIGRlc2NlbmRpbmdseQ0KZGYgPC0gZGZbb3JkZXIoZGZbLHREYXRlQ29sTmFtZV0sZGVjcmVhc2luZyA9IFRSVUUpLF0NCg0KI3JlbW92ZSB0aGUgcmVjb3JkIGJlZm9yZSB0aGUgc3RhcnQgZGF0YSBhbmQgYWZ0ZXIgdGhlIGVuZCBEYXRlDQpkZiA8LSBkZltkZlssdERhdGVDb2xOYW1lXT49IHN0YXJ0RGF0ZSxdDQpkZiA8LSBkZltkZlssdERhdGVDb2xOYW1lXTw9IGVuZERhdGUsXQ0KDQojcmVtb3ZlIHRoZSByb3dzIHdpdGggdGhlIGR1cGxpY2F0ZWQgSURzLCBhbmQgYXNzaWduIHRoZSBkZiB0byBhIG5ldyBkZi4NCm5ld2RmIDwtIGRmWyFkdXBsaWNhdGVkKGRmWyx0SURDb2xOYW1lXSksXQ0KDQojIGNhY3VsYXRlIHRoZSBSZWNlbmN5KGRheXMpIHRvIHRoZSBlbmREYXRlLCB0aGUgc21hbGxlciBkYXlzIHZhbHVlIG1lYW5zIG1vcmUgcmVjZW50DQpSZWNlbmN5PC1hcy5udW1lcmljKGRpZmZ0aW1lKGVuZERhdGUsbmV3ZGZbLHREYXRlQ29sTmFtZV0sdW5pdHM9ImRheXMiKSkNCg0KIyBhZGQgdGhlIERheXMgY29sdW1uIHRvIHRoZSBuZXdkZiBkYXRhIGZyYW1lDQpuZXdkZiA8LWNiaW5kKG5ld2RmLFJlY2VuY3kpDQoNCiNvcmRlciB0aGUgZGF0YWZyYW1lIGJ5IElEIHRvIGZpdCB0aGUgcmV0dXJuIG9yZGVyIG9mIHRhYmxlKCkgYW5kIHRhcHBseSgpDQpuZXdkZiA8LSBuZXdkZltvcmRlcihuZXdkZlssdElEQ29sTmFtZV0pLF0NCg0KIyBjYWN1bGF0ZSB0aGUgZnJlcXVlbmN5DQpmcmUgPC0gYXMuZGF0YS5mcmFtZSh0YWJsZShkZlssdElEQ29sTmFtZV0pKQ0KRnJlcXVlbmN5IDwtIGZyZVssMl0NCm5ld2RmIDwtIGNiaW5kKG5ld2RmLEZyZXF1ZW5jeSkNCg0KI2NhY3VsYXRlIHRoZSBNb25leSBwZXIgZGVhbA0KbSA8LSBhcy5kYXRhLmZyYW1lKHRhcHBseShkZlssdEFtb3VudENvbE5hbWVdLGRmWyx0SURDb2xOYW1lXSxzdW0pKQ0KTW9uZXRhcnkgPC0gbVssMV0vRnJlcXVlbmN5DQpuZXdkZiA8LSBjYmluZChuZXdkZixNb25ldGFyeSkNCg0KcmV0dXJuKG5ld2RmKQ0KDQp9ICMgZW5kIG9mIGZ1bmN0aW9uIGdldERhdGFGcmFtZQ0KYGBgDQoNCg0KYGBge3IgZXZhbD1UUlVFLCBlY2hvPUZBTFNFfQ0KIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyANCiMjIEZ1bmN0aW9uDQojIyAgICAgICAgZ2V0UGVyY2VudGFnZXMgPC0gZnVuY3Rpb24oZGYsY29sTmFtZXMpDQojIyBEZXNjcmlwdGlvbg0KIyMgICAgICAgIENhY3VsYXRpbmcgdGhlIHByb2JhYmlsaXRpZXMgb2YgIkJ1eSIvUmVwdXJjaGFzZSBncm91cGVkIGJ5IFIsIEYsIE0gdmFsdWVzIHJlc3BlY3RpdmVseSBvciBpbiBjb21iaW5hdGlvbg0KIyMgQXJndW1lbnRzDQojIyAgICAgICAgZGYsYSBkYXRlIGZyYW1lIHdpdGggZGlzY3JldGVkIHZhcmlhYmxlcyBvZiBSZWNlbmN5LCBGcmVxdWVuY3ksIGFuZCBNb25ldGFyeSBiYXNlZCBvbiB0aGUgZGF0YSBmcmFtZSByZXR1cm5lZCBieSB0aGUgIyMgZnVuY3Rpb24gb2YgZ2V0RGF0YUZyYW1lIGFib3ZlDQojIyAgICAgICAgY29sTmFtZXMsYSB2ZWN0b3Igb2YgY29sdW1uIG5hbWVzIHRvIGJlIGdyb3VwZWQgYnksIHN1Y2ggYXMgYygiUmVxdWVuY3kiKSBvciBjKCJSZXF1ZW5jeSIsIkZyZXF1ZW5jeSIpDQojIyBSZXR1cm4gVmFsdWUNCiMjICAgICAgICBhIGRhdGEgZnJhbWUgd2l0aCB0aGUgdmFyaWFibGVzIGJlaW5nIHVzZWQgdG8gZ3JvdXBlZCBieSBhbmQgdGhlIHBlcmNlbnRhZ2VzIG9mIGN1c3RvbWVycyB3aG8gYnV5IGFjY29yZGluZ2x5DQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQpyZXF1aXJlKHBseXIpDQpnZXRQZXJjZW50YWdlcyA8LSBmdW5jdGlvbihkZixjb2xOYW1lcyl7DQoNClZhcjwtYyhjb2xOYW1lcywiQnV5IikNCg0KZGY8LWRmWyxuYW1lcyhkZikgJWluJSBWYXIsZHJvcD1GXQ0KDQoNCmEgPC0gZGRwbHkoZGYsVmFyLHN1bW1hcml6ZSxOdW1iZXI9bGVuZ3RoKEJ1eSkpDQpiIDwtIGRkcGx5KGEsDQoJICAgICAgICAgIC4oKSwNCgkgICAgICAgICAgLmZ1bj1mdW5jdGlvbih4KXsNCgkgICAgICAgICAgICAgIHRyYW5zZm9ybSh4LCBQZXJjZW50YWdlPXdpdGgoeCxyb3VuZChhdmUoTnVtYmVyLGFbLG5hbWVzKGEpICVpbiUgVmFyLGRyb3A9Rl0sRlVOPXN1bSkvYXZlKE51bWJlcixhWyxuYW1lcyhhKSAlaW4lIGNvbE5hbWVzLGRyb3A9Rl0sRlVOPXN1bSksMikpKQ0KCSAgICAgICAgICB9KQ0KDQpiPC1iW2IkQnV5PT0xLC0xXQ0KDQpyZXR1cm4oYikNCg0KfQ0KYGBgDQoNCmBgYHtyIGV2YWw9VFJVRSwgZWNobz1GQUxTRX0NCiMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMgDQojIyBGdW5jdGlvbg0KIyMgICAgICAgIGdldENMVjwtZnVuY3Rpb24ocixmLG0sbixjb3N0LHBlcmlvZHMsZHIscE1vZGVsKQ0KIyMgRGVzY3JpcHRpb24NCiMjICAgICAgICBDYWN1bGF0aW5nIENMVg0KIyMgQXJndW1lbnRzDQojIyAgICAgICAgciwgUmVjZW5jeSB2YWx1ZSwgZS5nLiByPTANCiMjICAgICAgICBmLCBGcmVxdWVuY3kgdmFsdWUsZS5nLiBmPTENCiMjICAgICAgICBtLCB0aGUgcHJvZml0IGEgY3VzdG9tZXIgY2FuIGNvbnRyaWJ1dGUNCiMjICAgICAgICBuLCBudW1iZXIgb2YgdGhlIGN1c3RvbWVyIHdobyBoYXZlIHRoZSBzYW1lIFJlY2VuY3kgYW5kIEZyZXF1ZW5jeSB2YWx1ZQ0KIyMgICAgICAgIGNvc3QsIHRoZSBjb3N0IGFjY3VyZWQgaW4gZWFjaCBwdXJjaGFzaW5nIHBlcmlvZCB0byBldmVyeSBwb3RlbnRpYWwgY3VzdG9tZXJzIHdobyB3b3VsZCBidXkgb3Igbm90IGJ1eSBpbiB0aGUgZnV0dXJlICMjIHBlcmlvZC4gZS5nIHRoZSBwb3N0YWdlIHRvIGVhY2ggY3VzdG9tZXIgZm9yIG5ldyBwcm9kdWN0IHByb21vdGlvbi4NCiMjICAgICAgICBwZXJpb2RzLCBob3cgbWFueSBwZXJpb2RzIHRoZSBjdXN0b21lciB3aWxsIHN0YXkgYmVmb3JlIGhlL3NoZSBjaHVybg0KIyMgICAgICAgIGRyLCBkaXNjb3VudCByYXRlDQojIyAgICAgICAgcE1vZGVsLCB0aGUgcmVncmVzc2lvbiBtb2RlbCB3aGljaCBpcyB1c2VkIHRvIHByZWRpY3QgdGhlICJidXkiIHJhdGUgYmFzZWQgb24gUmVjZW5jeSxGcmVxdWVuY3kgYW5kL29yIE1vbmV0YXJ5IA0KIyMgUmV0dXJuIFZhbHVlDQojIyAgICAgICAgdGhlIGN1c3RvbWVycycgdmFsdWUgZHVyaW5nIHRoZSBwZXJpb2RzDQojIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjIyMjDQpnZXRDTFY8LWZ1bmN0aW9uKHIsZixtLG4sY29zdCxwZXJpb2RzLGRyLHBNb2RlbCl7DQoNCglkZjwtZGF0YS5mcmFtZShwZXJpb2Q9YygwKSxyPWMociksZj1jKGYpLG49YyhuKSx2YWx1ZT1jKDApKQ0KDQoJZm9yKGkgaW4gMTpwZXJpb2RzKXsNCgkJYmFja3N0ZXA8LWRmW2RmJHBlcmlvZD09aS0xLF0NCgkJbnJvdzwtbnJvdyhiYWNrc3RlcCkNCgkJZm9yKGogaW4gMTpucm93KXsNCgkJCXI8LWJhY2tzdGVwW2osXSRyDQoJCQlmPC1iYWNrc3RlcFtqLF0kZg0KCQkJbjwtYmFja3N0ZXBbaixdJG4NCgkJCXA8LXByZWRpY3QocE1vZGVsLGRhdGEuZnJhbWUoUmVjZW5jeT1yLEZyZXF1ZW5jeT1mKSx0eXBlPSdyZXNwb25zZScpWzFdDQoJCQlidXllcnM8LW4qcA0KCQkJZGY8LXJiaW5kKGRmLGMoaSwwLGYrMSxidXllcnMsYnV5ZXJzKihtLWNvc3QpIC8gKDErZHIpXmkpKQ0KCQkJZGY8LXJiaW5kKGRmLGMoaSxyKzEsZixuLWJ1eWVycywobi1idXllcnMpKigtY29zdCkgIC8gKDErZHIpXmkgKSkNCgkJfQ0KCX0NCg0KCXJldHVybihzdW0oZGYkdmFsdWUpKQ0KDQp9DQoNCmBgYA0KDQpgYGB7ciBldmFsPVRSVUUsIGVjaG89RkFMU0V9DQpzZXR3ZCgiQzpcXFVzZXJzXFxLRVZJTlxcRG93bmxvYWRzXFxob2FxdWFjaC5jb21cXFJFVkFNUF9XT1JEUFJFU1NcXHRoZW1lcy5waXhlbHdhcnMub3JnXFxlbXBhdGh5LWh0bWwiKQ0KZGYgPC0gcmVhZC50YWJsZSgiQzpcXFVzZXJzXFxLRVZJTlxcRG93bmxvYWRzXFxob2FxdWFjaC5jb21cXFJFVkFNUF9XT1JEUFJFU1NcXHRoZW1lcy5waXhlbHdhcnMub3JnXFxlbXBhdGh5LWh0bWxcXENETk9XX21hc3Rlci50eHQiKQ0KYGBgDQoNCmBgYHtyfQ0Kc3RyKGRmKQ0KYGBgDQoNCkxldCdzIGNvbnN0cnVjdCB0aGUgZGF0YSBmcmFtZSBhbmQgcmVuYW1lIHRoZSBjb2x1bW4gdmFyaWFibGVzLCBhbmQgdmVyaWZ5IHRoZSBjaGFuZ2VzLg0KDQpgYGB7cn0NCiMgY29uc3RydWN0IGEgZGF0YSBmcmFtZSB3aXRoIHRoZSBuZWNlc3NhcnkgY29sdW1ucyBvZiBjdXN0b21lciBJRCwgdHJhbnNhY3Rpb24gZGF0ZSwgYW5kIG1vbmV5IGFtb3VudCBwYWlkIGJ5IGEgY3VzdG9tZXIgIyBwZXIgdHJhbnNhY3Rpb24NCmRmIDwtIGFzLmRhdGEuZnJhbWUoY2JpbmQoZGZbLDFdLGRmWywyXSxkZlssNF0pKQ0KZGYNCmBgYA0KDQpgYGB7ciBldmFsPVRSVUUsIGVjaG89RkFMU0V9DQojIGFkZCBhcHByb3ByaWF0ZSBjb2x1bW4gbmFtZXMgZm9yIHRoZSBhYm92ZSB0aHJlZSBjb2x1bW4gYW5kIA0KbmFtZXMgPC0gYygiSUQiLCJEYXRlIiwiQW1vdW50IikNCm5hbWVzKGRmKSA8LSBuYW1lcw0KYGBgDQoNCmBgYHtyfQ0Kc3RyKGRmKQ0KYGBgDQoNCk5leHQsIHdlJ2xsIGdvIGFoZWFkIGFuZCBjb3ZlcnQgdGhlIERhdGUgY29sdW1uIHRvIERhdGUgdmFyaWFibGUgdHlwZToNCg0KYGBge3J9DQojdHJhbnNmZXIgdGhlIHRleHQgY29sdW1uIHR5cGUgdG8gZGF0ZSB0eXBlDQpkZlssMl0gPC0gYXMuRGF0ZShhcy5jaGFyYWN0ZXIoZGZbLDJdKSwiJVklbSVkIikNCmBgYA0KDQpgYGB7cn0NCnN0cihkZikNCmBgYA0KDQpgYGB7cn0NCmhlYWQoZGYpDQpgYGANCg0KDQpgYGB7cn0NCiMgc2V0IHRoZSAiaGlzdG9yeSIgdHJhbnNhY3Rpb24gdGltZSBzY29wZQ0Kc3RhcnREYXRlX2hpc3RvcnkgPC0gYXMuRGF0ZSgiMTk5NzAxMDEiLCIlWSVtJWQiKQ0KZW5kRGF0ZV9oaXN0b3J5IDwtIGFzLkRhdGUoIjE5OTgwMjI4IiwiJVklbSVkIikNCmBgYA0KDQpgYGB7cn0NCiMgIHNldCB0aGUgImZvcmVjYXN0IiB0cmFuc2FjdGlvbiB0aW1lIHNjb3BlIHdoaWNoIGFyZSBhIGJpLW1vbnRoIHB1cmNoYXNpbmcgY3ljbGUgdGltZQ0Kc3RhcnREYXRlX2ZvcmNhc3QgPC0gYXMuRGF0ZSgiMTk5ODAzMDEiLCIlWSVtJWQiKQ0KZW5kRGF0ZV9mb3JjYXN0IDwtIGFzLkRhdGUoIjE5OTgwNDMwIiwiJVklbSVkIikNCmBgYA0KDQpgYGB7cn0NCiNnZXQgdGhlIHJvbGxlZCB1cCBSLEYsTSBkYXRhIGZyYW1lcw0KaGlzdG9yeSA8LSBnZXREYXRhRnJhbWUoZGYsc3RhcnREYXRlX2hpc3RvcnksZW5kRGF0ZV9oaXN0b3J5KQ0KZm9yY2FzdCA8LSBnZXREYXRhRnJhbWUoZGYsc3RhcnREYXRlX2ZvcmNhc3QsZW5kRGF0ZV9mb3JjYXN0KQ0KYGBgDQoNCmBgYHtyfQ0KIyBzZXQgdGhlIHB1cmNoYXNpbmcgY3ljbGUgdGltZSBhcyA2MCBkYXlzLCBhbmQgZGlzY3JldGUgdGhlIFJlY2VuY3kgDQpoaXN0b3J5JFJlY2VuY3k8LSBoaXN0b3J5JFJlY2VuY3kgJS8lIDYwIA0KYGBgDQoNCmBgYHtyfQ0KI2Rpc2NyZXRlIHRoZSBNb25ldGFyeSBieSAkMTAgaW50ZXJ2YWwNCmJyZWFrczwtc2VxKDAscm91bmQobWF4KGhpc3RvcnkkTW9uZXRhcnkpKzkpLGJ5PTEwKQ0KaGlzdG9yeSRNb25ldGFyeTwtYXMubnVtZXJpYyhjdXQoaGlzdG9yeSRNb25ldGFyeSxicmVha3MsbGFiZWxzPUZBTFNFKSkNCmBgYA0KDQpgYGB7cn0NCiNhZGQgYSBCdXkvTm8gQnV5IGNvbHVtbiB0byB0aGUgUkZNIGRhdGEgZnJhbWUNCkJ1eTwtcmVwKDAsbnJvdyhoaXN0b3J5KSkNCmhpc3Rvcnk8LWNiaW5kKGhpc3RvcnksQnV5KQ0KYGBgDQoNCmBgYHtyfQ0KIyBmaW5kIG91dCB0aGUgdGhvc2Ugd2hvIHJlcHVyY2hhc2VkIGluIHRoZSBmb3JjYXN0IHBlcmlvZCAxOTk4MDMwMSAtIDE5OTgwNDMwDQpoaXN0b3J5W2hpc3RvcnkkSUQgJWluJSBmb3JjYXN0JElELCBdJEJ1eTwtMQ0KYGBgDQoNCmBgYHtyfQ0KdHJhaW48LWhpc3RvcnkNCmhlYWQodHJhaW4pDQpgYGANCg0KYGBge3J9DQojIGdldCAiQnV5IiBwZXJjZW50YWdlcyBiYXNlZCBvbiB0aGUgdmFyaWFibGUgUmVjZW5jeQ0KY29sTmFtZXM8LWMoIlJlY2VuY3kiKQ0KcDwtZ2V0UGVyY2VudGFnZXModHJhaW4sY29sTmFtZXMpDQpgYGANCg0KYGBge3J9DQojIGdldCB0aGUgQnV5IH4gUmVjZW5jeSBtb2RlbA0Kci5nbG09Z2xtKFBlcmNlbnRhZ2V+UmVjZW5jeSxmYW1pbHk9cXVhc2liaW5vbWlhbChsaW5rPSdsb2dpdCcpLGRhdGE9cCkNCnBfcjwtcA0KYGBgDQoNCmBgYHtyfQ0KIyBnZXQgIkJ1eSIgcGVyY2VudGFnZXMgYmFzZWQgb24gdGhlIHZhcmlhYmxlIEZyZXF1ZW5jeQ0KY29sTmFtZXM8LWMoIkZyZXF1ZW5jeSIpDQpwPC1nZXRQZXJjZW50YWdlcyh0cmFpbixjb2xOYW1lcykNCmBgYA0KDQpgYGB7cn0NCiMgZ2V0IHRoZSBCdXkgfiBGcmVxdWVuY3kgbW9kZWwNCmYuZ2xtPWdsbShQZXJjZW50YWdlfkZyZXF1ZW5jeSxmYW1pbHk9cXVhc2liaW5vbWlhbChsaW5rPSdsb2dpdCcpLGRhdGE9cCkNCnBfZjwtcA0KYGBgDQoNCmBgYHtyfQ0KIyBnZXQgIkJ1eSIgcGVyY2VudGFnZXMgYmFzZWQgb24gdGhlIHZhcmlhYmxlIE1vbmV0YXJ5DQpjb2xOYW1lczwtYygiTW9uZXRhcnkiKQ0KcDwtZ2V0UGVyY2VudGFnZXModHJhaW4sY29sTmFtZXMpDQpgYGANCg0KYGBge3J9DQojIGdldCB0aGUgQnV5IH4gTW9uZXRhcnkgbW9kZWwNCm0uZ2xtPWdsbShQZXJjZW50YWdlfk1vbmV0YXJ5LGZhbWlseT1xdWFzaWJpbm9taWFsKGxpbms9J2xvZ2l0JyksZGF0YT1wKQ0KcF9tPC1wDQpgYGANCg0KYGBge3J9DQojcGxvdCBhbmQgZHJhdyBmaXQgY3VydmVzIG9mIFBlcmNlbnRhZ2UgfiByLGYsbQ0KcGFyKG1mcm93PWMoMSwzKSxvbWE9YygwLDAsMiwwKSkNCg0KYGBgDQoNCmBgYHtyfQ0KcGxvdChwX3IkUmVjZW5jeSxwX3IkUGVyY2VudGFnZSoxMDAseGxhYj0iUmVjZW5jeSIseWxhYj0iUHJvYmFibGl0eSBvZiBQdXJjaGFzaW5nKCUpIikNCmxpbmVzKGxvd2VzcyhwX3IkUmVjZW5jeSxwX3IkUGVyY2VudGFnZSoxMDApLGNvbD0iYmx1ZSIsbHR5PTIpDQpgYGANCg0KYGBge3J9DQpwbG90KHBfZiRGcmVxdWVuY3kscF9mJFBlcmNlbnRhZ2UqMTAwLHhsYWI9IkZyZXF1ZW5jeSIseWxhYj0iUHJvYmFibGl0eSBvZiBQdXJjaGFzaW5nKCUpIikNCmxpbmVzKGxvd2VzcyhwX2YkRnJlcXVlbmN5LHBfZiRQZXJjZW50YWdlKjEwMCksY29sPSJibHVlIixsdHk9MikNCmBgYA0KDQpgYGB7cn0NCnBsb3QocF9tJE1vbmV0YXJ5LHBfbSRQZXJjZW50YWdlKjEwMCx4bGFiPSJNb25ldGFyeSIseWxhYj0iUHJvYmFibGl0eSBvZiBQdXJjaGFzaW5nKCUpIikNCmxpbmVzKGxvd2VzcyhwX20kTW9uZXRhcnkscF9tJFBlcmNlbnRhZ2UqMTAwKSxjb2w9ImJsdWUiLGx0eT0yKQ0KdGl0bGUoIlBlcmNlbnRhZ2VzIH4gUmVjZW5jeSwgRnJlcXVlbmN5LCBNb25ldGFyeSIsIHk9MTAsb3V0ZXI9VFJVRSkNCmBgYA0KDQoNCmBgYHtyfQ0KcGFyKG1mcm93PWMoMSwxKSkNCmBgYA0KDQpgYGB7cn0NCm1vZGVsPC1nbG0oQnV5flJlY2VuY3krRnJlcXVlbmN5LGZhbWlseT1xdWFzaWJpbm9taWFsKGxpbms9J2xvZ2l0JyksZGF0YT10cmFpbikNCnByZWQ8LXByZWRpY3QobW9kZWwsZGF0YS5mcmFtZShSZWNlbmN5PWMoMCksRnJlcXVlbmN5PWMoMSkpLHR5cGU9J3Jlc3BvbnNlJykNCmBgYA0KDQpgYGB7cn0NCiMjIGNhY3VsYXRpbmcgdGhlIENMViBmb3IgYSBjdXN0b21lciB3aXRoIFI9MCxGPTEsYXZlcmFnZSBwcm9maXQ9MTAwLGRpc2NvdW50IHJhdGU9MC4wMiBmb3IgMyBwZXJpb2RzDQp2PC1nZXRDTFYoMCwxLDEwMCwxLDAsMywwLjAyLG1vZGVsKQ0Kdg0KYGBgDQoNCg0KDQo=