Matriz de Markov

Paula Cazali 14000060

La Matriz de Markov recibe su nombre de un matematico Ruso quien la introdujo en el anio 1907: Andrei Markov. La cadena de Markov es un tipo especial de proceso estocastico discreto de la teoria de la probabilidad en el que la probabilidad que ocurra un evento depende solo del evento inmediato anterior y no le afectan los que sucedieron con anterioridad.

Existen muchas aplicaciones en la vida real para este modelo. A continuacion se hara una matriz de Markov a partir de la relacion que existe entre las actices americanas, basandonos en referencias hechas en wikipedia.

Cargamos las librerias que seran de utilidad:

library(rvest)
library(tidyverse)
library(stringr)
library(parallel)

Primero vamos a leer de la pagina de Wikipedia todos los links que existen y para obtener solo los links de las actrices se van a hacer unas filtraciones. Solo usaremos los tags de html donde hace referencia a todos los links, se quitaran todos los comentarios, imagenes, etc.

actrices <-
  read_html("https://en.wikipedia.org/wiki/List_of_American_film_actresses") %>% 
  html_nodes("a") %>% 
  html_attr('href') %>% 
  data_frame() %>%
  rename(links='.') %>% 
  filter(str_detect(links,"/wiki/")) %>%
  filter(!str_detect(links,"#")) %>%
  filter(!str_detect(links,"image")) %>% 
  filter(!str_detect(tolower(links),"file"))%>%
  filter(!str_detect(links,"https:")) %>% 
  filter(!str_detect(links,":")) %>% 
  filter(!str_detect(links, "List")) %>% 
  filter(!str_detect(links, "Main")) %>% 
  filter(!str_detect(links, "foundation"))

Vista previa de las primeras 10 actrices del set de datos:

actrices[1:10,1]

Matriz vacia para meter todas las referencias en las actrices.

matriz_actrices <- matrix(rep(0,3779136), nrow= 1944)
colnames(matriz_actrices) <- c(unlist(actrices[,1], use.names=FALSE))
rownames(matriz_actrices) <- c(unlist(actrices[,1], use.names=FALSE))
matriz_actrices[10:13,10:13]
                             /wiki/Jean_Acker /wiki/Bettye_Ackerman /wiki/Amy_Adams /wiki/Brooke_Adams_(actress)
/wiki/Jean_Acker                            0                     0               0                            0
/wiki/Bettye_Ackerman                       0                     0               0                            0
/wiki/Amy_Adams                             0                     0               0                            0
/wiki/Brooke_Adams_(actress)                0                     0               0                            0

Para mostrar el funcionamiento del algoritmo se va a aplicar para una sola actriz:

actrices[12,1]

Obteniendo todos los links dentro de una sola actriz: Amy Adams. Usamos la funcion paste para contatenar los strings. Luego se hace una filtracion para poder reducir considerablemente la cantidad de links que se deben comparar.

links_AmyAdams <- 
  read_html(paste("https://en.wikipedia.org",actrices[12,1],sep = ""))%>%
  html_nodes("a") %>% 
  html_attr('href') %>% 
  data_frame() %>%
  rename(links='.') %>% 
  filter(str_detect(links,"/wiki/")) %>%
  filter(!str_detect(links,"#")) %>%
  filter(!str_detect(links,"image")) %>% 
  filter(!str_detect(tolower(links),"file"))%>%
  filter(!str_detect(links,"https:")) %>% 
  filter(!str_detect(links, "film")) %>%
  filter(!str_detect(links, "List")) %>% 
  filter(!str_detect(links, "Award")) %>% 
  filter(!str_detect(links, "Wikipedia")) %>% 
  filter(!str_detect(links, ":")) %>% 
  filter(!str_detect(links, "serie")) %>% 
  filter(!str_detect(links, "Film"))
links_AmyAdams[1:10,1]

Cantidad de links de referencia en la pagina de Wikipedia de Amy Adams:

nrow(links_AmyAdams)
[1] 764

Vamos a definir una matriz (de una sola fila, para Amy Adams) de las relaciones que existen entre los links de Amy Adams y el resto de actrices.

Para cada link en la pagina de Amy Adams se ira comparando con todas las actrices americanas, cuando encuentra a cual pertenece ese link se ira guardando en la matriz para Amy Adams y se pasa al siguiente link de inmediato, con el proposito de minimizar tiempo:

for(i in 1:nrow(links_AmyAdams)){
  for(j in 1:nrow(actrices)){
    if(!is.na(match(links_AmyAdams[i,1],actrices[j,1]))){
      vector_AmyAdams[1,j] <- vector_AmyAdams[1,j] + 1
      break
    }
  } 
}

Colocaremos los nombres de las actrices en la matriz

colnames(vector_AmyAdams) <- c(unlist(actrices[,1], use.names=FALSE))
rownames(vector_AmyAdams) <- c("Amy_Adams")

Ahora vamos a comprobar que el proceso anterior se realizo de manera correcta. Veamos el caso del Meryl Streep. Cuantos links hacia Meryl existen en la pagina de Amy Adams?

links_AmyAdams %>% 
  filter(links == "/wiki/Meryl_Streep")

Por lo que nos podemos dar cuenta que existen 11 links de Meryl Streep en la pagina de Amy Adams. Ahora comprobando el valor en la matriz de Amy Adams:

vector_AmyAdams[,"/wiki/Meryl_Streep"]

[1] 11

En efecto existen 11 referencias hacia Meryl Streep desde la pagina de Amy Adams.

Ahora colocaremos las probabilidades en la matriz y veremos un extracto de la matriz:

vector_AmyAdams[1,] <- vector_AmyAdams[1,] / sum(vector_AmyAdams[1,])
vector_AmyAdams[1,11:14]
       /wiki/Bettye_Ackerman              /wiki/Amy_Adams /wiki/Brooke_Adams_(actress)             /wiki/Edie_Adams 
                 0.000000000                  0.006802721                  0.000000000                  0.000000000

Comprobando que estas probabilidades sumen 1:

sum(vector_AmyAdams[1,])

[1] 1

Por lo que podemos ver que el resultado es el correcto.

Ahora vamos a correr el mismo algoritmo para todas las actrices dentro de la matriz:

for (k in 1:nrow(actrices)){
  links_actriz <- 
    read_html(paste("https://en.wikipedia.org",actrices[k,1],sep = ""))%>%
    html_nodes("a") %>% 
    html_attr('href') %>% 
    data_frame() %>%
    rename(links='.') %>% 
    filter(str_detect(links,"/wiki/")) %>%
    filter(!str_detect(links,"#")) %>%
    filter(!str_detect(links,"image")) %>% 
    filter(!str_detect(tolower(links),"file"))%>%
    filter(!str_detect(links,"https:")) %>% 
    filter(!str_detect(links, "film")) %>%
    filter(!str_detect(links, "List")) %>% 
    filter(!str_detect(links, "Award")) %>% 
    filter(!str_detect(links, "Wikipedia")) %>% 
    filter(!str_detect(links, ":")) %>% 
    filter(!str_detect(links, "serie")) %>% 
    filter(!str_detect(links, "Film"))
  for(i in 1:nrow(links_actriz)){
    for(j in 1:nrow(actrices)){
      if(!is.na(match(links_actriz[i,1],actrices[j,1]))){
        matriz_actrices[k,j] <- matriz_actrices[k,j] + 1
        break
      }
    } 
  }
}
View(links_AmyAdams)

Luego de dejar corriendo este algoritmo por un dia completo se logro obtener la matriz completa con las referencias que existen ente las actrices.

matriz_actrices %>% View()

En la siguiente imagen se muestra un screenshot de matriz_actrices %>% View() :

Creamos una matriz donde iran las probabilidades:

matriz_prob <- matriz_actrices

Asignando una probabilidad a las actrices:

for (l in 1944){
  for(i in 1944){
    matriz_prob[l,i] <- matriz_actrices[l,i] / rowSums(matriz_actrices[l,])  
  }
}
LS0tDQp0aXRsZTogIlByb3llY3RvIEZpbmFsIg0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIVtdKGdhbGlsZW8ucG5nKQ0KDQojIE1hdHJpeiBkZSBNYXJrb3YNCg0KIyMjIFBhdWxhIENhemFsaSAxNDAwMDA2MA0KDQpMYSBNYXRyaXogZGUgTWFya292IHJlY2liZSBzdSBub21icmUgZGUgdW4gbWF0ZW1hdGljbyBSdXNvIHF1aWVuIGxhIGludHJvZHVqbyBlbiBlbCBhbmlvIDE5MDc6IEFuZHJlaSBNYXJrb3YuDQpMYSBjYWRlbmEgZGUgTWFya292IGVzIHVuIHRpcG8gZXNwZWNpYWwgZGUgcHJvY2VzbyBlc3RvY2FzdGljbyBkaXNjcmV0byBkZSBsYSB0ZW9yaWEgZGUgbGEgcHJvYmFiaWxpZGFkIGVuIGVsIHF1ZSBsYSBwcm9iYWJpbGlkYWQgcXVlIG9jdXJyYSB1biBldmVudG8gZGVwZW5kZSBzb2xvIGRlbCBldmVudG8gaW5tZWRpYXRvIGFudGVyaW9yIHkgbm8gbGUgYWZlY3RhbiBsb3MgcXVlIHN1Y2VkaWVyb24gY29uIGFudGVyaW9yaWRhZC4NCg0KRXhpc3RlbiBtdWNoYXMgYXBsaWNhY2lvbmVzIGVuIGxhIHZpZGEgcmVhbCBwYXJhIGVzdGUgbW9kZWxvLiBBIGNvbnRpbnVhY2lvbiBzZSBoYXJhIHVuYSBtYXRyaXogZGUgTWFya292IGEgcGFydGlyIGRlIGxhIHJlbGFjaW9uIHF1ZSBleGlzdGUgZW50cmUgbGFzIGFjdGljZXMgYW1lcmljYW5hcywgYmFzYW5kb25vcyBlbiByZWZlcmVuY2lhcyBoZWNoYXMgZW4gd2lraXBlZGlhLg0KDQpDYXJnYW1vcyBsYXMgbGlicmVyaWFzIHF1ZSBzZXJhbiBkZSB1dGlsaWRhZDoNCmBgYHtyfQ0KbGlicmFyeShydmVzdCkNCmxpYnJhcnkodGlkeXZlcnNlKQ0KbGlicmFyeShzdHJpbmdyKQ0KbGlicmFyeShwYXJhbGxlbCkNCmBgYA0KDQpQcmltZXJvIHZhbW9zIGEgbGVlciBkZSBsYSBwYWdpbmEgZGUgV2lraXBlZGlhIHRvZG9zIGxvcyBsaW5rcyBxdWUgZXhpc3RlbiB5IHBhcmEgb2J0ZW5lciBzb2xvIGxvcyBsaW5rcyBkZSBsYXMgYWN0cmljZXMgc2UgdmFuIGEgaGFjZXIgdW5hcyBmaWx0cmFjaW9uZXMuIFNvbG8gdXNhcmVtb3MgbG9zICoqdGFncyoqIGRlIGh0bWwgZG9uZGUgaGFjZSByZWZlcmVuY2lhIGEgdG9kb3MgbG9zIGxpbmtzLCBzZSBxdWl0YXJhbiB0b2RvcyBsb3MgY29tZW50YXJpb3MsIGltYWdlbmVzLCBldGMuDQpgYGB7cn0NCmFjdHJpY2VzIDwtDQogIHJlYWRfaHRtbCgiaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvTGlzdF9vZl9BbWVyaWNhbl9maWxtX2FjdHJlc3NlcyIpICU+JSANCiAgaHRtbF9ub2RlcygiYSIpICU+JSANCiAgaHRtbF9hdHRyKCdocmVmJykgJT4lIA0KICBkYXRhX2ZyYW1lKCkgJT4lDQogIHJlbmFtZShsaW5rcz0nLicpICU+JSANCiAgZmlsdGVyKHN0cl9kZXRlY3QobGlua3MsIi93aWtpLyIpKSAlPiUNCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCIjIikpICU+JQ0KICBmaWx0ZXIoIXN0cl9kZXRlY3QobGlua3MsImltYWdlIikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KHRvbG93ZXIobGlua3MpLCJmaWxlIikpJT4lDQogIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywiaHR0cHM6IikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCI6IikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiTGlzdCIpKSAlPiUgDQogIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywgIk1haW4iKSkgJT4lIA0KICBmaWx0ZXIoIXN0cl9kZXRlY3QobGlua3MsICJmb3VuZGF0aW9uIikpDQpgYGANCg0KVmlzdGEgcHJldmlhIGRlIGxhcyBwcmltZXJhcyAxMCBhY3RyaWNlcyBkZWwgc2V0IGRlIGRhdG9zOg0KYGBge3J9DQphY3RyaWNlc1sxOjEwLDFdDQpgYGANCg0KTWF0cml6IHZhY2lhIHBhcmEgbWV0ZXIgdG9kYXMgbGFzIHJlZmVyZW5jaWFzIGVuIGxhcyBhY3RyaWNlcy4NCmBgYHtyfQ0KbWF0cml6X2FjdHJpY2VzIDwtIG1hdHJpeChyZXAoMCwzNzc5MTM2KSwgbnJvdz0gMTk0NCkNCmNvbG5hbWVzKG1hdHJpel9hY3RyaWNlcykgPC0gYyh1bmxpc3QoYWN0cmljZXNbLDFdLCB1c2UubmFtZXM9RkFMU0UpKQ0Kcm93bmFtZXMobWF0cml6X2FjdHJpY2VzKSA8LSBjKHVubGlzdChhY3RyaWNlc1ssMV0sIHVzZS5uYW1lcz1GQUxTRSkpDQptYXRyaXpfYWN0cmljZXNbMTA6MTMsMTA6MTNdDQpgYGANCg0KUGFyYSBtb3N0cmFyIGVsIGZ1bmNpb25hbWllbnRvIGRlbCBhbGdvcml0bW8gc2UgdmEgYSBhcGxpY2FyIHBhcmEgdW5hIHNvbGEgYWN0cml6Og0KYGBge3J9DQphY3RyaWNlc1sxMiwxXQ0KYGBgDQoNCk9idGVuaWVuZG8gdG9kb3MgbG9zIGxpbmtzIGRlbnRybyBkZSB1bmEgc29sYSBhY3RyaXo6ICoqQW15IEFkYW1zKiouIFVzYW1vcyBsYSBmdW5jaW9uIHBhc3RlIHBhcmEgY29udGF0ZW5hciBsb3Mgc3RyaW5ncy4gTHVlZ28gc2UgaGFjZSB1bmEgZmlsdHJhY2lvbiBwYXJhIHBvZGVyIHJlZHVjaXIgY29uc2lkZXJhYmxlbWVudGUgbGEgY2FudGlkYWQgZGUgbGlua3MgcXVlIHNlIGRlYmVuIGNvbXBhcmFyLg0KYGBge3J9DQpsaW5rc19BbXlBZGFtcyA8LSANCiAgcmVhZF9odG1sKHBhc3RlKCJodHRwczovL2VuLndpa2lwZWRpYS5vcmciLGFjdHJpY2VzWzEyLDFdLHNlcCA9ICIiKSklPiUNCiAgaHRtbF9ub2RlcygiYSIpICU+JSANCiAgaHRtbF9hdHRyKCdocmVmJykgJT4lIA0KICBkYXRhX2ZyYW1lKCkgJT4lDQogIHJlbmFtZShsaW5rcz0nLicpICU+JSANCiAgZmlsdGVyKHN0cl9kZXRlY3QobGlua3MsIi93aWtpLyIpKSAlPiUNCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCIjIikpICU+JQ0KICBmaWx0ZXIoIXN0cl9kZXRlY3QobGlua3MsImltYWdlIikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KHRvbG93ZXIobGlua3MpLCJmaWxlIikpJT4lDQogIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywiaHR0cHM6IikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiZmlsbSIpKSAlPiUNCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiTGlzdCIpKSAlPiUgDQogIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywgIkF3YXJkIikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiV2lraXBlZGlhIikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiOiIpKSAlPiUgDQogIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywgInNlcmllIikpICU+JSANCiAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiRmlsbSIpKQ0KbGlua3NfQW15QWRhbXNbMToxMCwxXQ0KYGBgDQoNCkNhbnRpZGFkIGRlIGxpbmtzIGRlIHJlZmVyZW5jaWEgZW4gbGEgcGFnaW5hIGRlIFdpa2lwZWRpYSBkZSBBbXkgQWRhbXM6DQpgYGB7cn0NCm5yb3cobGlua3NfQW15QWRhbXMpDQpgYGANCg0KVmFtb3MgYSBkZWZpbmlyIHVuYSBtYXRyaXogKGRlIHVuYSBzb2xhIGZpbGEsIHBhcmEgQW15IEFkYW1zKSBkZSBsYXMgcmVsYWNpb25lcyBxdWUgZXhpc3RlbiBlbnRyZSBsb3MgbGlua3MgZGUgQW15IEFkYW1zIHkgZWwgcmVzdG8gZGUgYWN0cmljZXMuDQpgYGB7cn0NCnZlY3Rvcl9BbXlBZGFtcyA8LSBtYXRyaXgocmVwKDAsMTk0NCksIG5yb3c9IDEpDQpgYGANCg0KDQpQYXJhIGNhZGEgbGluayBlbiBsYSBwYWdpbmEgZGUgQW15IEFkYW1zIHNlIGlyYSBjb21wYXJhbmRvIGNvbiB0b2RhcyBsYXMgYWN0cmljZXMgYW1lcmljYW5hcywgY3VhbmRvIGVuY3VlbnRyYSBhIGN1YWwgcGVydGVuZWNlIGVzZSBsaW5rIHNlIGlyYSBndWFyZGFuZG8gZW4gbGEgbWF0cml6IHBhcmEgQW15IEFkYW1zIHkgc2UgcGFzYSBhbCBzaWd1aWVudGUgbGluayBkZSBpbm1lZGlhdG8sIGNvbiBlbCBwcm9wb3NpdG8gZGUgbWluaW1pemFyIHRpZW1wbzoNCmBgYHtyfQ0KZm9yKGkgaW4gMTpucm93KGxpbmtzX0FteUFkYW1zKSl7DQogIGZvcihqIGluIDE6bnJvdyhhY3RyaWNlcykpew0KICAgIGlmKCFpcy5uYShtYXRjaChsaW5rc19BbXlBZGFtc1tpLDFdLGFjdHJpY2VzW2osMV0pKSl7DQogICAgICB2ZWN0b3JfQW15QWRhbXNbMSxqXSA8LSB2ZWN0b3JfQW15QWRhbXNbMSxqXSArIDENCiAgICAgIGJyZWFrDQogICAgfQ0KICB9IA0KfQ0KYGBgDQoNCg0KQ29sb2NhcmVtb3MgbG9zIG5vbWJyZXMgZGUgbGFzIGFjdHJpY2VzIGVuIGxhIG1hdHJpeg0KYGBge3J9DQpjb2xuYW1lcyh2ZWN0b3JfQW15QWRhbXMpIDwtIGModW5saXN0KGFjdHJpY2VzWywxXSwgdXNlLm5hbWVzPUZBTFNFKSkNCnJvd25hbWVzKHZlY3Rvcl9BbXlBZGFtcykgPC0gYygiQW15X0FkYW1zIikNCmBgYA0KDQpBaG9yYSB2YW1vcyBhIGNvbXByb2JhciBxdWUgZWwgcHJvY2VzbyBhbnRlcmlvciBzZSByZWFsaXpvIGRlIG1hbmVyYSBjb3JyZWN0YS4gVmVhbW9zIGVsIGNhc28gZGVsIE1lcnlsIFN0cmVlcC4gQ3VhbnRvcyBsaW5rcyBoYWNpYSBNZXJ5bCBleGlzdGVuIGVuIGxhIHBhZ2luYSBkZSBBbXkgQWRhbXM/DQpgYGB7cn0NCmxpbmtzX0FteUFkYW1zICU+JSANCiAgZmlsdGVyKGxpbmtzID09ICIvd2lraS9NZXJ5bF9TdHJlZXAiKSANCmBgYA0KDQpQb3IgbG8gcXVlIG5vcyBwb2RlbW9zIGRhciBjdWVudGEgcXVlIGV4aXN0ZW4gMTEgbGlua3MgZGUgTWVyeWwgU3RyZWVwIGVuIGxhIHBhZ2luYSBkZSBBbXkgQWRhbXMuIEFob3JhIGNvbXByb2JhbmRvIGVsIHZhbG9yIGVuIGxhIG1hdHJpeiBkZSBBbXkgQWRhbXM6DQpgYGB7cn0NCnZlY3Rvcl9BbXlBZGFtc1ssIi93aWtpL01lcnlsX1N0cmVlcCJdDQpgYGANCiMjIyBFbiBlZmVjdG8gZXhpc3RlbiAxMSByZWZlcmVuY2lhcyBoYWNpYSBNZXJ5bCBTdHJlZXAgZGVzZGUgbGEgcGFnaW5hIGRlIEFteSBBZGFtcy4NCg0KQWhvcmEgY29sb2NhcmVtb3MgbGFzIHByb2JhYmlsaWRhZGVzIGVuIGxhIG1hdHJpeiB5IHZlcmVtb3MgdW4gZXh0cmFjdG8gZGUgbGEgbWF0cml6Og0KYGBge3J9DQp2ZWN0b3JfQW15QWRhbXNbMSxdIDwtIHZlY3Rvcl9BbXlBZGFtc1sxLF0gLyBzdW0odmVjdG9yX0FteUFkYW1zWzEsXSkNCmBgYA0KYGBge3J9DQp2ZWN0b3JfQW15QWRhbXNbMSwxMToxNF0NCmBgYA0KDQpDb21wcm9iYW5kbyBxdWUgZXN0YXMgcHJvYmFiaWxpZGFkZXMgc3VtZW4gMToNCmBgYHtyfQ0Kc3VtKHZlY3Rvcl9BbXlBZGFtc1sxLF0pDQpgYGANCg0KIyMjIFBvciBsbyBxdWUgcG9kZW1vcyB2ZXIgcXVlIGVsIHJlc3VsdGFkbyBlcyBlbCBjb3JyZWN0by4NCg0KDQpBaG9yYSB2YW1vcyBhIGNvcnJlciBlbCBtaXNtbyBhbGdvcml0bW8gcGFyYSB0b2RhcyBsYXMgYWN0cmljZXMgZGVudHJvIGRlIGxhIG1hdHJpejoNCmBgYHtyfQ0KZm9yIChrIGluIDE6bnJvdyhhY3RyaWNlcykpew0KICBsaW5rc19hY3RyaXogPC0gDQogICAgcmVhZF9odG1sKHBhc3RlKCJodHRwczovL2VuLndpa2lwZWRpYS5vcmciLGFjdHJpY2VzW2ssMV0sc2VwID0gIiIpKSU+JQ0KICAgIGh0bWxfbm9kZXMoImEiKSAlPiUgDQogICAgaHRtbF9hdHRyKCdocmVmJykgJT4lIA0KICAgIGRhdGFfZnJhbWUoKSAlPiUNCiAgICByZW5hbWUobGlua3M9Jy4nKSAlPiUgDQogICAgZmlsdGVyKHN0cl9kZXRlY3QobGlua3MsIi93aWtpLyIpKSAlPiUNCiAgICBmaWx0ZXIoIXN0cl9kZXRlY3QobGlua3MsIiMiKSkgJT4lDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCJpbWFnZSIpKSAlPiUgDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KHRvbG93ZXIobGlua3MpLCJmaWxlIikpJT4lDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCJodHRwczoiKSkgJT4lIA0KICAgIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywgImZpbG0iKSkgJT4lDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiTGlzdCIpKSAlPiUgDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiQXdhcmQiKSkgJT4lIA0KICAgIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywgIldpa2lwZWRpYSIpKSAlPiUgDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAiOiIpKSAlPiUgDQogICAgZmlsdGVyKCFzdHJfZGV0ZWN0KGxpbmtzLCAic2VyaWUiKSkgJT4lIA0KICAgIGZpbHRlcighc3RyX2RldGVjdChsaW5rcywgIkZpbG0iKSkNCiAgZm9yKGkgaW4gMTpucm93KGxpbmtzX2FjdHJpeikpew0KICAgIGZvcihqIGluIDE6bnJvdyhhY3RyaWNlcykpew0KICAgICAgaWYoIWlzLm5hKG1hdGNoKGxpbmtzX2FjdHJpeltpLDFdLGFjdHJpY2VzW2osMV0pKSl7DQogICAgICAgIG1hdHJpel9hY3RyaWNlc1trLGpdIDwtIG1hdHJpel9hY3RyaWNlc1trLGpdICsgMQ0KICAgICAgICBicmVhaw0KICAgICAgfQ0KICAgIH0gDQogIH0NCn0NCmBgYA0KDQojIyMjIEx1ZWdvIGRlIGRlamFyIGNvcnJpZW5kbyBlc3RlIGFsZ29yaXRtbyBwb3IgdW4gZGlhIGNvbXBsZXRvIHNlIGxvZ3JvIG9idGVuZXIgbGEgbWF0cml6IGNvbXBsZXRhIGNvbiBsYXMgcmVmZXJlbmNpYXMgcXVlIGV4aXN0ZW4gZW50ZSBsYXMgYWN0cmljZXMuDQoNCmBgYHtyfQ0KbWF0cml6X2FjdHJpY2VzICU+JSBWaWV3KCkNCmBgYA0KDQpFbiBsYSBzaWd1aWVudGUgaW1hZ2VuIHNlIG11ZXN0cmEgdW4gc2NyZWVuc2hvdCBkZSBgbWF0cml6X2FjdHJpY2VzICU+JSBWaWV3KClgIDoNCiFbXShtYXRyaXoxLmpwZykNCg0KQ3JlYW1vcyB1bmEgbWF0cml6IGRvbmRlIGlyYW4gbGFzIHByb2JhYmlsaWRhZGVzOg0KYGBge3J9DQptYXRyaXpfcHJvYiA8LSBtYXRyaXpfYWN0cmljZXMNCmBgYA0KDQpBc2lnbmFuZG8gdW5hIHByb2JhYmlsaWRhZCBhIGxhcyBhY3RyaWNlczoNCmBgYHtyfQ0KZm9yIChsIGluIDE5NDQpew0KICBmb3IoaSBpbiAxOTQ0KXsNCiAgICBtYXRyaXpfcHJvYltsLGldIDwtIG1hdHJpel9hY3RyaWNlc1tsLGldIC8gcm93U3VtcyhtYXRyaXpfYWN0cmljZXNbbCxdKSAgDQogIH0NCn0gIA0KYGBgDQoNCg0KDQoNCg0KDQo=