Using a K-Nearest Neighbor Prediction Model


Data:

Voter Dataset from the Democracy Fund Voter Study Group

“The Democracy Fund Voter Study Group is using a unique longitudinal data set that most recently surveyed 8,000 adults (age 18+) in December 2016 via YouGov. Participants were identified from a pool of respondents who participated in a similar survey in December 2011, as well as a second pre-election interview in 2012, and a third interview following the 2012 presidential election. For these 8,000 respondents, we have measures of their political attitudes, values, and affinities in 2011 as well as self-reports of their turnout and vote choice in November 2012.”

library(readr)
library(dplyr)
library(gmodels)
library(class)
library(scales)

voterdata<-read_csv("/Users/Brett/Library/Mobile Documents/com~apple~CloudDocs/All Files/Education/QC Teaching/SOC765_SocialMediaMarketingAnalytics/Assignment 3 Audience Investigation Excel/Data/VOTER_Survey_December16_Release1 copy.csv")

voterdata<- voterdata%>%
  mutate(immigrants = as.numeric(ifelse(ft_immig_2016=="0 - Unfavorable feeling",0,
                      ifelse(ft_immig_2016=="100 - Favorable feeling",100,
                      ifelse(ft_immig_2016=="25 -Unfavorable feeling",25,
                      ifelse(ft_immig_2016=="50 - No feeling at all",50,
                      ifelse(ft_immig_2016=="75 - Favorable feeling",75,
                      ifelse(ft_immig_2016=="Don't know",NA,ft_immig_2016))))))),
         blacklivesmatter = as.numeric(ifelse(ft_blm_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_blm_2016=="100 - Favorable feeling",100,
                            ifelse(ft_blm_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_blm_2016=="50 - No feeling at all",50,
                            ifelse(ft_blm_2016=="75 - Favorable feeling",75,
                            ifelse(ft_blm_2016=="Don't know",NA,ft_blm_2016))))))),
          police = as.numeric(ifelse(ft_police_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_police_2016=="100 - Favorable feeling",100,
                            ifelse(ft_police_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_police_2016=="50 - No feeling at all",50,
                            ifelse(ft_police_2016=="75 - Favorable feeling",75,
                            ifelse(ft_police_2016=="Don't know",NA,ft_police_2016))))))),
         muslims = as.numeric(ifelse(ft_muslim_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_muslim_2016=="100 - Favorable feeling",100,
                            ifelse(ft_muslim_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_muslim_2016=="50 - No feeling at all",50,
                            ifelse(ft_muslim_2016=="75 - Favorable feeling",75,
                            ifelse(ft_muslim_2016=="Don't know",NA,ft_muslim_2016))))))),
         gays = as.numeric(ifelse(ft_gays_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_gays_2016=="100 - Favorable feeling",100,
                            ifelse(ft_gays_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_gays_2016=="50 - No feeling at all",50,
                            ifelse(ft_gays_2016=="75 - Favorable feeling",75,
                            ifelse(ft_gays_2016=="Don't know",NA,ft_gays_2016))))))),
         altright = as.numeric(ifelse(ft_altright_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_altright_2016=="100 - Favorable feeling",100,
                            ifelse(ft_altright_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_altright_2016=="50 - No feeling at all",50,
                            ifelse(ft_altright_2016=="75 - Favorable feeling",75,
                            ifelse(ft_altright_2016=="Don't know",NA,ft_altright_2016))))))),
         feminists = as.numeric(ifelse(ft_fem_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_fem_2016=="100 - Favorable feeling",100,
                            ifelse(ft_fem_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_fem_2016=="50 - No feeling at all",50,
                            ifelse(ft_fem_2016=="75 - Favorable feeling",75,
                            ifelse(ft_fem_2016=="Don't know",NA,ft_fem_2016))))))),
         christians = as.numeric(ifelse(ft_christ_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_christ_2016=="100 - Favorable feeling",100,
                            ifelse(ft_christ_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_christ_2016=="50 - No feeling at all",50,
                            ifelse(ft_christ_2016=="75 - Favorable feeling",75,
                            ifelse(ft_christ_2016=="Don't know",NA,ft_christ_2016))))))),
         jews = as.numeric(ifelse(ft_jew_2016=="0 - Unfavorable feeling",0,
                            ifelse(ft_jew_2016=="100 - Favorable feeling",100,
                            ifelse(ft_jew_2016=="25 -Unfavorable feeling",25,
                            ifelse(ft_jew_2016=="50 - No feeling at all",50,
                            ifelse(ft_jew_2016=="75 - Favorable feeling",75,
                            ifelse(ft_jew_2016=="Don't know",NA,ft_jew_2016))))))),
         hillary = ifelse(presvote16post_2016=="Hillary Clinton",1,0),
         trump = ifelse(presvote16post_2016=="Donald Trump",1,0),
         votefor = factor(ifelse(hillary==1,"hillary",ifelse(trump==1,"trump","other"))))

voterdata2 <- voterdata%>%
  select(votefor,immigrants,blacklivesmatter,police,muslims,gays,altright, 
         feminists, christians)%>%
  filter(!is.na(blacklivesmatter),
         !is.na(immigrants),
         !is.na(muslims),
         !is.na(police),
         !is.na(gays),
         !is.na(altright),
         !is.na(feminists),
         !is.na(christians),
         votefor%in%c("hillary","trump"))

How corelated are self reported 0-100 ratings of favorability of various groups/issues.

x<-cor(voterdata2%>%select(-votefor))
library(corrplot)
corrplot(x, type = "upper", order = "hclust", 
         tl.col = "black", tl.srt = 45)

Can we predice who someone will vote for based on their self-reported favorability of these groups/issues?

#Wrangling data into training & testing dataframes for a KNN algorithm
#install.packages("class")
library(class)
#Write a normalization function
normalize <- function(x) {
num <- x - min(x)
denom <- max(x) - min(x)
return (num/denom)
}
#Normalize 
voterdata3 <- as.data.frame(lapply(voterdata2[2:9], normalize))
voterdata2 <-cbind(voterdata2[1],voterdata3)
unique(voterdata2$votefor)
[1] hillary trump  
Levels: hillary other trump
#Create two randomly assigned groups
ind <- sample(2, nrow(voterdata2), replace=TRUE, prob=c(0.67, 0.33))
#Training
  voterdata.training <- voterdata2[ind==1, 2:9]
  voterdata.trainLabels <- voterdata2[ind==1,1]
  
#Test         
  voterdata.test <- voterdata2[ind==2, 2:9]         
  voterdata.testLabels <- voterdata2[ind==2, 1]

KNN Prediction Model

Comparing Predicted voting outcomes to observed voting outcomes

#Build knn prediction model  
voterdata_pred <- knn(train = voterdata.training, 
                      test = voterdata.test, 
                      cl= voterdata.trainLabels, 
                      k=3)
# Merge `Predicted` and `Observed` 
merged <- data.frame(voterdata_pred, voterdata.testLabels)
names(merged) <- c("Predicted", "Observed")
print(merged)

How accurate is the model?

merged%>%
  mutate(Prediction=ifelse(Predicted==Observed,"Accurate","Not Accurate"))%>%
  group_by(Prediction)%>%
  summarize(n=n())%>%
  mutate(freq=percent(n/sum(n)))

Does accuracy vary by candidate?

The model is able to predict hillary voters with slightly better accuracy than trump voters.

CrossTable(x = voterdata_pred, y = voterdata.testLabels, prop.chisq=FALSE)

 
   Cell Contents
|-------------------------|
|                       N |
|           N / Row Total |
|           N / Col Total |
|         N / Table Total |
|-------------------------|

 
Total Observations in Table:  1676 

 
               | voterdata.testLabels 
voterdata_pred |   hillary |     trump | Row Total | 
---------------|-----------|-----------|-----------|
       hillary |       762 |       100 |       862 | 
               |     0.884 |     0.116 |     0.514 | 
               |     0.902 |     0.120 |           | 
               |     0.455 |     0.060 |           | 
---------------|-----------|-----------|-----------|
         trump |        83 |       731 |       814 | 
               |     0.102 |     0.898 |     0.486 | 
               |     0.098 |     0.880 |           | 
               |     0.050 |     0.436 |           | 
---------------|-----------|-----------|-----------|
  Column Total |       845 |       831 |      1676 | 
               |     0.504 |     0.496 |           | 
---------------|-----------|-----------|-----------|

 

3 Dimensional Plot

A quick 3-dimensional plot to see what clusters we can spot when looking at feelings towards Black Lives Matter, Immigrants, and Feminists.

We see alot of stratification here.

voterdata3 <- voterdata%>%
  select(votefor,immigrants,blacklivesmatter,feminists)%>%
  filter(!is.na(blacklivesmatter),
         !is.na(immigrants),
         !is.na(feminists),
         votefor%in%c("hillary","trump"))
#install.packages("plot3D")
library(plot3D)
scatter3D(voterdata3$blacklivesmatter, voterdata3$immigrants, voterdata3$feminists, phi = 30, bty ="g",main = "Voter Data", xlab = "Black Lives Matter",ylab ="immigrants", zlab = "feminists")

References

*https://image.slidesharecdn.com/bnlintromlgenomicswwcjune2017public-170628225446/95/an-introduction-to-machine-learning-and-genomics-24-638.jpg?cb=1498690655*

Democracy Fund Voter Study Group. VIEWS OF THE ELECTORATE RESEARCH SURVEY, December 2016. [Computer File] Release 1: August 28, 2017. Washington DC: Democracy Fund Voter Study Group [producer] https://www.voterstudygroup.org/.

About KNN Procedure

“k-nearest neighbour classification for test set from training set. For each row of the test set, the k nearest (in Euclidean distance) training set vectors are found, and the classification is decided by majority vote, with ties broken at random. If there are ties for the kth nearest vector, all candidates are included in the vote.” source

LS0tCnRpdGxlOiAiIgpvdXRwdXQ6IGh0bWxfbm90ZWJvb2sKLS0tCgohW10oL1VzZXJzL0JyZXR0L0xpYnJhcnkvTW9iaWxlIERvY3VtZW50cy9jb21+YXBwbGV+Q2xvdWREb2NzL0FsbCBGaWxlcy9FbXBsb3llcnMvUmVzdW1lL01EUkMvUHJlZGljdGluZyBWb3RlciBPdXRjb21lcy5wbmcpCgoKIyMjVXNpbmcgYSBLLU5lYXJlc3QgTmVpZ2hib3IgUHJlZGljdGlvbiBNb2RlbAoKPGJyLz4KCiMjIyMjRGF0YToKCltWb3RlciBEYXRhc2V0XShodHRwczovL3d3dy52b3RlcnN0dWR5Z3JvdXAub3JnL3B1YmxpY2F0aW9ucy8yMDE2LWVsZWN0aW9ucy9kYXRhKSBmcm9tIHRoZSBEZW1vY3JhY3kgRnVuZCBWb3RlciBTdHVkeSBHcm91cCAKCioiVGhlIERlbW9jcmFjeSBGdW5kIFZvdGVyIFN0dWR5IEdyb3VwIGlzIHVzaW5nIGEgdW5pcXVlIGxvbmdpdHVkaW5hbCBkYXRhIHNldCB0aGF0IG1vc3QgcmVjZW50bHkgc3VydmV5ZWQgOCwwMDAgYWR1bHRzIChhZ2UgMTgrKSBpbiBEZWNlbWJlciAyMDE2IHZpYSBZb3VHb3YuIFBhcnRpY2lwYW50cyB3ZXJlIGlkZW50aWZpZWQgZnJvbSBhIHBvb2wgb2YgcmVzcG9uZGVudHMgd2hvIHBhcnRpY2lwYXRlZCBpbiBhIHNpbWlsYXIgc3VydmV5IGluIERlY2VtYmVyIDIwMTEsIGFzIHdlbGwgYXMgYSBzZWNvbmQgcHJlLWVsZWN0aW9uIGludGVydmlldyBpbiAyMDEyLCBhbmQgYSB0aGlyZCBpbnRlcnZpZXcgZm9sbG93aW5nIHRoZSAyMDEyIHByZXNpZGVudGlhbCBlbGVjdGlvbi4gRm9yIHRoZXNlIDgsMDAwIHJlc3BvbmRlbnRzLCB3ZSBoYXZlIG1lYXN1cmVzIG9mIHRoZWlyIHBvbGl0aWNhbCBhdHRpdHVkZXMsIHZhbHVlcywgYW5kIGFmZmluaXRpZXMgaW4gMjAxMSBhcyB3ZWxsIGFzIHNlbGYtcmVwb3J0cyBvZiB0aGVpciB0dXJub3V0IGFuZCB2b3RlIGNob2ljZSBpbiBOb3ZlbWJlciAyMDEyLiIqCgoKYGBge3IsIGZpZy5oZWlnaHQ9NiwgZmlnLndpZHRoPTYsIG1lc3NhZ2U9RkFMU0UsIHdhcm5pbmc9RkFMU0V9CmxpYnJhcnkocmVhZHIpCmxpYnJhcnkoZHBseXIpCmxpYnJhcnkoZ21vZGVscykKbGlicmFyeShjbGFzcykKbGlicmFyeShzY2FsZXMpCgp2b3RlcmRhdGE8LXJlYWRfY3N2KCIvVXNlcnMvQnJldHQvTGlicmFyeS9Nb2JpbGUgRG9jdW1lbnRzL2NvbX5hcHBsZX5DbG91ZERvY3MvQWxsIEZpbGVzL0VkdWNhdGlvbi9RQyBUZWFjaGluZy9TT0M3NjVfU29jaWFsTWVkaWFNYXJrZXRpbmdBbmFseXRpY3MvQXNzaWdubWVudCAzIEF1ZGllbmNlIEludmVzdGlnYXRpb24gRXhjZWwvRGF0YS9WT1RFUl9TdXJ2ZXlfRGVjZW1iZXIxNl9SZWxlYXNlMSBjb3B5LmNzdiIpCgp2b3RlcmRhdGE8LSB2b3RlcmRhdGElPiUKICBtdXRhdGUoaW1taWdyYW50cyA9IGFzLm51bWVyaWMoaWZlbHNlKGZ0X2ltbWlnXzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9pbW1pZ18yMDE2PT0iMTAwIC0gRmF2b3JhYmxlIGZlZWxpbmciLDEwMCwKICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9pbW1pZ18yMDE2PT0iMjUgLVVuZmF2b3JhYmxlIGZlZWxpbmciLDI1LAogICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X2ltbWlnXzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9pbW1pZ18yMDE2PT0iNzUgLSBGYXZvcmFibGUgZmVlbGluZyIsNzUsCiAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfaW1taWdfMjAxNj09IkRvbid0IGtub3ciLE5BLGZ0X2ltbWlnXzIwMTYpKSkpKSkpLAogICAgICAgICBibGFja2xpdmVzbWF0dGVyID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfYmxtXzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9ibG1fMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfYmxtXzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfYmxtXzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9ibG1fMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X2JsbV8yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfYmxtXzIwMTYpKSkpKSkpLAogICAgICAgICAgcG9saWNlID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfcG9saWNlXzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9wb2xpY2VfMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfcG9saWNlXzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfcG9saWNlXzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9wb2xpY2VfMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X3BvbGljZV8yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfcG9saWNlXzIwMTYpKSkpKSkpLAogICAgICAgICBtdXNsaW1zID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfbXVzbGltXzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9tdXNsaW1fMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfbXVzbGltXzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfbXVzbGltXzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9tdXNsaW1fMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X211c2xpbV8yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfbXVzbGltXzIwMTYpKSkpKSkpLAogICAgICAgICBnYXlzID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfZ2F5c18yMDE2PT0iMCAtIFVuZmF2b3JhYmxlIGZlZWxpbmciLDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfZ2F5c18yMDE2PT0iMTAwIC0gRmF2b3JhYmxlIGZlZWxpbmciLDEwMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9nYXlzXzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfZ2F5c18yMDE2PT0iNTAgLSBObyBmZWVsaW5nIGF0IGFsbCIsNTAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfZ2F5c18yMDE2PT0iNzUgLSBGYXZvcmFibGUgZmVlbGluZyIsNzUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfZ2F5c18yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfZ2F5c18yMDE2KSkpKSkpKSwKICAgICAgICAgYWx0cmlnaHQgPSBhcy5udW1lcmljKGlmZWxzZShmdF9hbHRyaWdodF8yMDE2PT0iMCAtIFVuZmF2b3JhYmxlIGZlZWxpbmciLDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfYWx0cmlnaHRfMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfYWx0cmlnaHRfMjAxNj09IjI1IC1VbmZhdm9yYWJsZSBmZWVsaW5nIiwyNSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9hbHRyaWdodF8yMDE2PT0iNTAgLSBObyBmZWVsaW5nIGF0IGFsbCIsNTAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfYWx0cmlnaHRfMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X2FsdHJpZ2h0XzIwMTY9PSJEb24ndCBrbm93IixOQSxmdF9hbHRyaWdodF8yMDE2KSkpKSkpKSwKICAgICAgICAgZmVtaW5pc3RzID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfZmVtXzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9mZW1fMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfZmVtXzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfZmVtXzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9mZW1fMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X2ZlbV8yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfZmVtXzIwMTYpKSkpKSkpLAogICAgICAgICBjaHJpc3RpYW5zID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfY2hyaXN0XzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9jaHJpc3RfMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfY2hyaXN0XzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfY2hyaXN0XzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9jaHJpc3RfMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X2NocmlzdF8yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfY2hyaXN0XzIwMTYpKSkpKSkpLAogICAgICAgICBqZXdzID0gYXMubnVtZXJpYyhpZmVsc2UoZnRfamV3XzIwMTY9PSIwIC0gVW5mYXZvcmFibGUgZmVlbGluZyIsMCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9qZXdfMjAxNj09IjEwMCAtIEZhdm9yYWJsZSBmZWVsaW5nIiwxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfamV3XzIwMTY9PSIyNSAtVW5mYXZvcmFibGUgZmVlbGluZyIsMjUsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZmVsc2UoZnRfamV3XzIwMTY9PSI1MCAtIE5vIGZlZWxpbmcgYXQgYWxsIiw1MCwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZShmdF9qZXdfMjAxNj09Ijc1IC0gRmF2b3JhYmxlIGZlZWxpbmciLDc1LAogICAgICAgICAgICAgICAgICAgICAgICAgICAgaWZlbHNlKGZ0X2pld18yMDE2PT0iRG9uJ3Qga25vdyIsTkEsZnRfamV3XzIwMTYpKSkpKSkpLAogICAgICAgICBoaWxsYXJ5ID0gaWZlbHNlKHByZXN2b3RlMTZwb3N0XzIwMTY9PSJIaWxsYXJ5IENsaW50b24iLDEsMCksCiAgICAgICAgIHRydW1wID0gaWZlbHNlKHByZXN2b3RlMTZwb3N0XzIwMTY9PSJEb25hbGQgVHJ1bXAiLDEsMCksCiAgICAgICAgIHZvdGVmb3IgPSBmYWN0b3IoaWZlbHNlKGhpbGxhcnk9PTEsImhpbGxhcnkiLGlmZWxzZSh0cnVtcD09MSwidHJ1bXAiLCJvdGhlciIpKSkpCgp2b3RlcmRhdGEyIDwtIHZvdGVyZGF0YSU+JQogIHNlbGVjdCh2b3RlZm9yLGltbWlncmFudHMsYmxhY2tsaXZlc21hdHRlcixwb2xpY2UsbXVzbGltcyxnYXlzLGFsdHJpZ2h0LCAKICAgICAgICAgZmVtaW5pc3RzLCBjaHJpc3RpYW5zKSU+JQogIGZpbHRlcighaXMubmEoYmxhY2tsaXZlc21hdHRlciksCiAgICAgICAgICFpcy5uYShpbW1pZ3JhbnRzKSwKICAgICAgICAgIWlzLm5hKG11c2xpbXMpLAogICAgICAgICAhaXMubmEocG9saWNlKSwKICAgICAgICAgIWlzLm5hKGdheXMpLAogICAgICAgICAhaXMubmEoYWx0cmlnaHQpLAogICAgICAgICAhaXMubmEoZmVtaW5pc3RzKSwKICAgICAgICAgIWlzLm5hKGNocmlzdGlhbnMpLAogICAgICAgICB2b3RlZm9yJWluJWMoImhpbGxhcnkiLCJ0cnVtcCIpKQpgYGAKCgojIyNIb3cgY29yZWxhdGVkIGFyZSBzZWxmIHJlcG9ydGVkIDAtMTAwIHJhdGluZ3Mgb2YgZmF2b3JhYmlsaXR5IG9mIHZhcmlvdXMgZ3JvdXBzL2lzc3Vlcy4KYGBge3IsIGZpZy5oZWlnaHQ9OCwgZmlnLndpZHRoPTh9Cng8LWNvcih2b3RlcmRhdGEyJT4lc2VsZWN0KC12b3RlZm9yKSkKbGlicmFyeShjb3JycGxvdCkKY29ycnBsb3QoeCwgdHlwZSA9ICJ1cHBlciIsIG9yZGVyID0gImhjbHVzdCIsIAogICAgICAgICB0bC5jb2wgPSAiYmxhY2siLCB0bC5zcnQgPSA0NSkKYGBgCgojIyNDYW4gd2UgcHJlZGljZSB3aG8gc29tZW9uZSB3aWxsIHZvdGUgZm9yIGJhc2VkIG9uIHRoZWlyIHNlbGYtcmVwb3J0ZWQgZmF2b3JhYmlsaXR5IG9mIHRoZXNlIGdyb3Vwcy9pc3N1ZXM/CgpgYGB7cn0KI1dyYW5nbGluZyBkYXRhIGludG8gdHJhaW5pbmcgJiB0ZXN0aW5nIGRhdGFmcmFtZXMgZm9yIGEgS05OIGFsZ29yaXRobQoKI2luc3RhbGwucGFja2FnZXMoImNsYXNzIikKbGlicmFyeShjbGFzcykKCiNXcml0ZSBhIG5vcm1hbGl6YXRpb24gZnVuY3Rpb24Kbm9ybWFsaXplIDwtIGZ1bmN0aW9uKHgpIHsKbnVtIDwtIHggLSBtaW4oeCkKZGVub20gPC0gbWF4KHgpIC0gbWluKHgpCnJldHVybiAobnVtL2Rlbm9tKQp9CgojTm9ybWFsaXplIAp2b3RlcmRhdGEzIDwtIGFzLmRhdGEuZnJhbWUobGFwcGx5KHZvdGVyZGF0YTJbMjo5XSwgbm9ybWFsaXplKSkKdm90ZXJkYXRhMiA8LWNiaW5kKHZvdGVyZGF0YTJbMV0sdm90ZXJkYXRhMykKCnVuaXF1ZSh2b3RlcmRhdGEyJHZvdGVmb3IpCgojQ3JlYXRlIHR3byByYW5kb21seSBhc3NpZ25lZCBncm91cHMKaW5kIDwtIHNhbXBsZSgyLCBucm93KHZvdGVyZGF0YTIpLCByZXBsYWNlPVRSVUUsIHByb2I9YygwLjY3LCAwLjMzKSkKCgojVHJhaW5pbmcKICB2b3RlcmRhdGEudHJhaW5pbmcgPC0gdm90ZXJkYXRhMltpbmQ9PTEsIDI6OV0KICB2b3RlcmRhdGEudHJhaW5MYWJlbHMgPC0gdm90ZXJkYXRhMltpbmQ9PTEsMV0KCiAgCiNUZXN0ICAgICAgICAgCiAgdm90ZXJkYXRhLnRlc3QgPC0gdm90ZXJkYXRhMltpbmQ9PTIsIDI6OV0gICAgICAgICAKICB2b3RlcmRhdGEudGVzdExhYmVscyA8LSB2b3RlcmRhdGEyW2luZD09MiwgMV0KYGBgCgoKIyMjI0tOTiBQcmVkaWN0aW9uIE1vZGVsCgpDb21wYXJpbmcgUHJlZGljdGVkIHZvdGluZyBvdXRjb21lcyB0byBvYnNlcnZlZCB2b3Rpbmcgb3V0Y29tZXMKCmBgYHtyLCBmaWcuaGVpZ2h0PTYsIGZpZy53aWR0aD02fQojQnVpbGQga25uIHByZWRpY3Rpb24gbW9kZWwgIAp2b3RlcmRhdGFfcHJlZCA8LSBrbm4odHJhaW4gPSB2b3RlcmRhdGEudHJhaW5pbmcsIAogICAgICAgICAgICAgICAgICAgICAgdGVzdCA9IHZvdGVyZGF0YS50ZXN0LCAKICAgICAgICAgICAgICAgICAgICAgIGNsPSB2b3RlcmRhdGEudHJhaW5MYWJlbHMsIAogICAgICAgICAgICAgICAgICAgICAgaz0zKQoKCgojIE1lcmdlIGBQcmVkaWN0ZWRgIGFuZCBgT2JzZXJ2ZWRgIAptZXJnZWQgPC0gZGF0YS5mcmFtZSh2b3RlcmRhdGFfcHJlZCwgdm90ZXJkYXRhLnRlc3RMYWJlbHMpCm5hbWVzKG1lcmdlZCkgPC0gYygiUHJlZGljdGVkIiwgIk9ic2VydmVkIikKcHJpbnQobWVyZ2VkKQpgYGAKCiMjIyNIb3cgYWNjdXJhdGUgaXMgdGhlIG1vZGVsPwpgYGB7ciwgZmlnLmhlaWdodD02LCBmaWcud2lkdGg9Nn0KbWVyZ2VkJT4lCiAgbXV0YXRlKFByZWRpY3Rpb249aWZlbHNlKFByZWRpY3RlZD09T2JzZXJ2ZWQsIkFjY3VyYXRlIiwiTm90IEFjY3VyYXRlIikpJT4lCiAgZ3JvdXBfYnkoUHJlZGljdGlvbiklPiUKICBzdW1tYXJpemUobj1uKCkpJT4lCiAgbXV0YXRlKGZyZXE9cGVyY2VudChuL3N1bShuKSkpCmBgYAoKCiMjIyNEb2VzIGFjY3VyYWN5IHZhcnkgYnkgY2FuZGlkYXRlPwoKVGhlIG1vZGVsIGlzIGFibGUgdG8gcHJlZGljdCBoaWxsYXJ5IHZvdGVycyB3aXRoIHNsaWdodGx5IGJldHRlciBhY2N1cmFjeSB0aGFuIHRydW1wIHZvdGVycy4KYGBge3J9CkNyb3NzVGFibGUoeCA9IHZvdGVyZGF0YV9wcmVkLCB5ID0gdm90ZXJkYXRhLnRlc3RMYWJlbHMsIHByb3AuY2hpc3E9RkFMU0UpCmBgYAoKCiMjIzMgRGltZW5zaW9uYWwgUGxvdAoKQSBxdWljayAzLWRpbWVuc2lvbmFsIHBsb3QgdG8gc2VlIHdoYXQgY2x1c3RlcnMgd2UgY2FuIHNwb3Qgd2hlbiBsb29raW5nIGF0IGZlZWxpbmdzIHRvd2FyZHMgQmxhY2sgTGl2ZXMgTWF0dGVyLCBJbW1pZ3JhbnRzLCBhbmQgRmVtaW5pc3RzLgoKV2Ugc2VlIGFsb3Qgb2Ygc3RyYXRpZmljYXRpb24gaGVyZS4KCmBgYHtyfQp2b3RlcmRhdGEzIDwtIHZvdGVyZGF0YSU+JQogIHNlbGVjdCh2b3RlZm9yLGltbWlncmFudHMsYmxhY2tsaXZlc21hdHRlcixmZW1pbmlzdHMpJT4lCiAgZmlsdGVyKCFpcy5uYShibGFja2xpdmVzbWF0dGVyKSwKICAgICAgICAgIWlzLm5hKGltbWlncmFudHMpLAogICAgICAgICAhaXMubmEoZmVtaW5pc3RzKSwKICAgICAgICAgdm90ZWZvciVpbiVjKCJoaWxsYXJ5IiwidHJ1bXAiKSkKCgojaW5zdGFsbC5wYWNrYWdlcygicGxvdDNEIikKbGlicmFyeShwbG90M0QpCgpzY2F0dGVyM0Qodm90ZXJkYXRhMyRibGFja2xpdmVzbWF0dGVyLCB2b3RlcmRhdGEzJGltbWlncmFudHMsIHZvdGVyZGF0YTMkZmVtaW5pc3RzLCBwaGkgPSAzMCwgYnR5ID0iZyIsbWFpbiA9ICJWb3RlciBEYXRhIiwgeGxhYiA9ICJCbGFjayBMaXZlcyBNYXR0ZXIiLHlsYWIgPSJpbW1pZ3JhbnRzIiwgemxhYiA9ICJmZW1pbmlzdHMiKQpgYGAKCiMjUmVmZXJlbmNlcwoKPiAqaHR0cHM6Ly9pbWFnZS5zbGlkZXNoYXJlY2RuLmNvbS9ibmxpbnRyb21sZ2Vub21pY3N3d2NqdW5lMjAxN3B1YmxpYy0xNzA2MjgyMjU0NDYvOTUvYW4taW50cm9kdWN0aW9uLXRvLW1hY2hpbmUtbGVhcm5pbmctYW5kLWdlbm9taWNzLTI0LTYzOC5qcGc/Y2I9MTQ5ODY5MDY1NSoKCj4gRGVtb2NyYWN5IEZ1bmQgVm90ZXIgU3R1ZHkgR3JvdXAuIFZJRVdTIE9GIFRIRSBFTEVDVE9SQVRFIFJFU0VBUkNIIFNVUlZFWSwgRGVjZW1iZXIgMjAxNi4gW0NvbXB1dGVyIEZpbGVdIFJlbGVhc2UgMTogQXVndXN0IDI4LCAyMDE3LiBXYXNoaW5ndG9uIERDOiBEZW1vY3JhY3kgRnVuZCBWb3RlciBTdHVkeSBHcm91cCBbcHJvZHVjZXJdIGh0dHBzOi8vd3d3LnZvdGVyc3R1ZHlncm91cC5vcmcvLgoKIyNBYm91dCBLTk4gUHJvY2VkdXJlCgo+ICJrLW5lYXJlc3QgbmVpZ2hib3VyIGNsYXNzaWZpY2F0aW9uIGZvciB0ZXN0IHNldCBmcm9tIHRyYWluaW5nIHNldC4gRm9yIGVhY2ggcm93IG9mIHRoZSB0ZXN0IHNldCwgdGhlIGsgbmVhcmVzdCAoaW4gRXVjbGlkZWFuIGRpc3RhbmNlKSB0cmFpbmluZyBzZXQgdmVjdG9ycyBhcmUgZm91bmQsIGFuZCB0aGUgY2xhc3NpZmljYXRpb24gaXMgZGVjaWRlZCBieSBtYWpvcml0eSB2b3RlLCB3aXRoIHRpZXMgYnJva2VuIGF0IHJhbmRvbS4gSWYgdGhlcmUgYXJlIHRpZXMgZm9yIHRoZSBrdGggbmVhcmVzdCB2ZWN0b3IsIGFsbCBjYW5kaWRhdGVzIGFyZSBpbmNsdWRlZCBpbiB0aGUgdm90ZS4iIFtzb3VyY2VdKGh0dHBzOi8vc3RhdC5ldGh6LmNoL1ItbWFudWFsL1ItZGV2ZWwvbGlicmFyeS9jbGFzcy9odG1sL2tubi5odG1sKQoKCg==