Notebook com códigos R para a implementação de um Autoencoder simples - ERAMIA 2020
Pacote para trabalhar com imagens
library(png)
Carrega os digitos da base MNIST
carrega.digitos <- function(digitos = c(1,3,4,7,9), quantidade = 100,
treino=1, taxa.ruido = 0.1){
digitos <<- digitos # Padroes a serem armazenados
taxa.ruido <<- taxa.ruido # Probabilidade de um pixel ser trocado
# (probabilidade de ruido)
############## carrega os padroes #############
padroes <<- list()
orgdim <<- NULL
cat("\nCarregando digitos...\n")
for(i in digitos){
if(treino == 1){
arquivos <- list.files(paste("Digitos/MNIST/mnist_png/training/",
as.character(i),"/",sep=""))[1:quantidade]
for(j in 1:quantidade){
img <- readPNG(paste("Digitos/MNIST/mnist_png/training/",
as.character(i),"/",arquivos[j], sep=""))
orgdim <<- dim(img)
dim(img) <- NULL
# Armazena os padroes
padroes[[length(padroes)+1]] <<- as.vector(ifelse(img >= 0.2, 1, 0))
}
}
else{
arquivos <- list.files(paste("Digitos/MNIST/mnist_png/testing/",
as.character(i),"/",sep=""))[1:quantidade]
for(j in 1:quantidade){
img <- readPNG(paste("Digitos/MNIST/mnist_png/testing/",
as.character(i),"/",arquivos[j], sep=""))
orgdim <<- dim(img)
dim(img) <- NULL
# Armazena os padroes
padroes[[length(padroes)+1]] <<- as.vector(ifelse(img >= 0.2, 1, 0))
}
}
}
}
Script para teste visual dos dígitos
testa.digitos <- function(modelo){
# Carrega digitos de teste
carrega.digitos(digitos = c(0,1,2,3,4,5,6,7,8,9),1,0,taxa.ruido)
plotdim = 2*orgdim
plot(c(1,(plotdim[1]+5)*length(digitos)), c(1,(plotdim[2]+5)*3),
type="n", xlab="", ylab="")
x = 1
for (i in 1:length(padroes)) {
padrao = padroes[[i]]
ruido = (runif(length(padrao), 0, 1) > taxa.ruido ) * 1
entrada = padrao * ruido
retorno <- autoencoder.propagacao(modelo,entrada)
ret <- retorno$y.escondida.saida
ret <- as.vector(ifelse(ret >= 0.5, 1, 0))
# Padrao original
img <- padrao;
dim(img) <- orgdim
image <- as.raster((img+1)/2)
rasterImage(image, x, 1, x + plotdim[1], plotdim[2], interpolate=F)
# Entrada com ruido
img <- entrada;
dim(img) <- orgdim
image <- as.raster((img+1)/2)
rasterImage(image, x, 1+(plotdim[2]+5), x + plotdim[1],
1+2*(plotdim[2]+5), interpolate=F)
# Imagem recuperada
img <- ret;
dim(img) <- orgdim
image <- as.raster((img+1)/2)
rasterImage(image, x, 1+2*(plotdim[2]+5), x + plotdim[1],
1+2*(plotdim[2]+5)+plotdim[2], interpolate=F)
x = x + plotdim[1]+5
}
}
Vamos implementar uma função de ativação
funcao.ativacao <- function(v){
# Função logística
y <- 1 / (1 + exp(-v))
return(y)
}
Vamos também precisar da derivada da função de ativação
der.funcao.ativacao <- function(y){
# Derivada da logística
derivada <- y * (1 - y)
return(derivada)
}
Criação da arquitetura do Autoencoder. Similar à arquitetura do MLP, porém com uma camada de saída com a mesma quantidade de neurônios da camada de entrada
arquitetura <- function(num.entrada, num.escondida,
funcao.ativacao, der.funcao.ativacao){
arq <- list()
# Parametros da rede
arq$num.entrada.saida <- num.entrada
arq$num.escondida <- num.escondida
arq$funcao.ativacao <- funcao.ativacao
arq$der.funcao.ativacao <- der.funcao.ativacao
# 2 neuronios na camada escondida
#
# Ent1 Ent2 Bias
# 1 w11 w12 w13
# 2 w21 w22 w23
# Pesos conectando entrada e escondida
num.pesos.entrada.escondida <- (num.entrada+1)*num.escondida
arq$escondida <- matrix(runif(min=-0.5,max=0.5, num.pesos.entrada.escondida),
nrow=num.escondida, ncol=num.entrada+1)
# Pesos conectando escondida e saida
num.pesos.escondida.saida <- (num.escondida+1)*num.entrada
arq$saida <- matrix(runif(min=-0.5,max=0.5, num.pesos.escondida.saida),
nrow=num.entrada, ncol=num.escondida+1)
return(arq)
}
Fase de propagação
autoencoder.propagacao <- function(arq, exemplo){
# Entrada -> Cama Escondida
v.entrada.escondida <- arq$escondida %*% as.numeric(c(exemplo,1))
y.entrada.escondida <- arq$funcao.ativacao(v.entrada.escondida)
# Camada Escondida -> Camada de Saida
v.escondida.saida <- arq$saida %*% c(y.entrada.escondida,1)
y.escondida.saida <- arq$funcao.ativacao(v.escondida.saida)
# Resultados
resultado <- list()
resultado$v.entrada.escondida <- v.entrada.escondida
resultado$y.entrada.escondida <- y.entrada.escondida
resultado$v.escondida.saida <- v.escondida.saida
resultado$y.escondida.saida <- y.escondida.saida
return(resultado)
}
Fase de treinamento
autoencoder <- function(arq, dados, n, limiar){
loss <- 10
loss.anterior <- 0
epocas <- 0
# Treina eqto o erro for maior que um limiar
while((abs(loss-loss.anterior)) > limiar){
loss.anterior <- loss
loss <- 0
# Treino para todos os exemplos (epoca)
for(i in 1:length(dados)){
# Pego um exemplo de entrada
x <- dados[[i]]
# Pego a saida da rede para o exemplo
resultado <- autoencoder.propagacao(arq,x)
y <- resultado$y.escondida.saida
# Calculo do erro para o exemplo
erro <- x - y
loss <- loss + -(sum(x*log(y) + (1-x)*log(1-y)))
# Gradiente local no neuronio de saida
# erro * derivada da funcao de ativacao
grad.local.saida <- erro * arq$der.funcao.ativacao(y)
# Gradiente local no neuronio escondido
# derivada da funcao de ativacao no neuronio escondido * soma dos gradientes
# locais dos neuronios conectados na proxima camada * pesos conectando a camada
# escondida com a saida
pesos.saida <- arq$saida[,1:arq$num.escondida]
grad.local.escondida <-
as.numeric(arq$der.funcao.ativacao(resultado$y.entrada.escondida)) *
(as.vector(grad.local.saida) %*% pesos.saida)
# Ajuste dos pesos
# Saida
arq$saida <- arq$saida + n * (grad.local.saida %*%
c(resultado$y.entrada.escondida,1))
# Escondida
arq$escondida <- arq$escondida + n * (t(grad.local.escondida) %*%
as.numeric(c(x,1)))
}
loss <- loss / length(dados)
cat("Epoca = ",epocas," / Erro = ",loss," / ",abs(loss-loss.anterior),"\n")
epocas <- epocas+1
}
retorno <- list()
retorno$arq <- arq
retorno$epocas <- epocas
return(retorno)
}
Teste com camada subcompleta
# ===============================================================
# Carrega os digitos
carrega.digitos(digitos = c(0,1,2,3,4,5,6,7,8,9),50,1,0.3)
# Cria a arquitetuta
arq <- arquitetura(length(padroes[[1]]),length(padroes[[1]])-400,
funcao.ativacao,der.funcao.ativacao)
# Treina o modelo
modelo <- autoencoder(arq,padroes,0.2,0.1)
# Testa para novos digitos
testa.digitos(modelo$arq)
# ===============================================================
Teste com camada sobrecompleta
# ===============================================================
# Carrega os digitos
carrega.digitos(digitos = c(0,1,2,3,4,5,6,7,8,9),50,1,0.3)
#carrega.digitos2(digitos = c(0,1,2,3,4,5,6,7,8,9))
# Cria a arquitetuta
arq <- arquitetura(length(padroes[[1]]),length(padroes[[1]])+400,
funcao.ativacao,der.funcao.ativacao)
# Treina o modelo
modelo <- autoencoder(arq,padroes,0.2,0.1)
# Testa para novos digitos
testa.digitos(modelo$arq)
# ===============================================================
LS0tCnRpdGxlOiAiUiBOb3RlYm9vayAtIEF1dG9lbmNvZGVyIFNpbXBsZXMiCm91dHB1dDoKICBodG1sX25vdGVib29rCi0tLQoKIyMgTm90ZWJvb2sgY29tIGPDs2RpZ29zIFIgcGFyYSBhIGltcGxlbWVudGHDp8OjbyBkZSB1bSBBdXRvZW5jb2RlciBzaW1wbGVzIC0gRVJBTUlBIDIwMjAKClBhY290ZSBwYXJhIHRyYWJhbGhhciBjb20gaW1hZ2VucwpgYGB7cn0KbGlicmFyeShwbmcpCmBgYAoKCkNhcnJlZ2Egb3MgZGlnaXRvcyBkYSBiYXNlIE1OSVNUCmBgYHtyfQoKY2FycmVnYS5kaWdpdG9zIDwtIGZ1bmN0aW9uKGRpZ2l0b3MgPSBjKDEsMyw0LDcsOSksIHF1YW50aWRhZGUgPSAxMDAsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICB0cmVpbm89MSwgdGF4YS5ydWlkbyA9IDAuMSl7CgogIGRpZ2l0b3MgPDwtIGRpZ2l0b3MgIyBQYWRyb2VzIGEgc2VyZW0gYXJtYXplbmFkb3MKICB0YXhhLnJ1aWRvIDw8LSB0YXhhLnJ1aWRvICMgUHJvYmFiaWxpZGFkZSBkZSB1bSBwaXhlbCBzZXIgdHJvY2FkbyAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIyAocHJvYmFiaWxpZGFkZSBkZSBydWlkbykgCgogICMjIyMjIyMjIyMjIyMjIGNhcnJlZ2Egb3MgcGFkcm9lcyAjIyMjIyMjIyMjIyMjCiAgcGFkcm9lcyA8PC0gbGlzdCgpCiAgb3JnZGltIDw8LSBOVUxMCgogIGNhdCgiXG5DYXJyZWdhbmRvIGRpZ2l0b3MuLi5cbiIpCgogIGZvcihpIGluIGRpZ2l0b3MpewoKICAgIGlmKHRyZWlubyA9PSAxKXsKCiAgICAgIGFycXVpdm9zIDwtIGxpc3QuZmlsZXMocGFzdGUoIkRpZ2l0b3MvTU5JU1QvbW5pc3RfcG5nL3RyYWluaW5nLyIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMuY2hhcmFjdGVyKGkpLCIvIixzZXA9IiIpKVsxOnF1YW50aWRhZGVdCgogICAgICBmb3IoaiBpbiAxOnF1YW50aWRhZGUpewogICAgICAgIGltZyA8LSByZWFkUE5HKHBhc3RlKCJEaWdpdG9zL01OSVNUL21uaXN0X3BuZy90cmFpbmluZy8iLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgYXMuY2hhcmFjdGVyKGkpLCIvIixhcnF1aXZvc1tqXSwgc2VwPSIiKSkKICAgICAgICBvcmdkaW0gPDwtIGRpbShpbWcpCiAgICAgICAgZGltKGltZykgPC0gTlVMTAogICAgICAgICMgQXJtYXplbmEgb3MgcGFkcm9lcwogICAgICAgIHBhZHJvZXNbW2xlbmd0aChwYWRyb2VzKSsxXV0gPDwtIGFzLnZlY3RvcihpZmVsc2UoaW1nID49IDAuMiwgMSwgMCkpCiAgICAgIH0KICAgIH0KICAgIGVsc2V7CiAgICAgIGFycXVpdm9zIDwtIGxpc3QuZmlsZXMocGFzdGUoIkRpZ2l0b3MvTU5JU1QvbW5pc3RfcG5nL3Rlc3RpbmcvIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhcy5jaGFyYWN0ZXIoaSksIi8iLHNlcD0iIikpWzE6cXVhbnRpZGFkZV0KCiAgICAgIGZvcihqIGluIDE6cXVhbnRpZGFkZSl7CiAgICAgICAgaW1nIDwtIHJlYWRQTkcocGFzdGUoIkRpZ2l0b3MvTU5JU1QvbW5pc3RfcG5nL3Rlc3RpbmcvIiwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFzLmNoYXJhY3RlcihpKSwiLyIsYXJxdWl2b3Nbal0sIHNlcD0iIikpCiAgICAgICAgb3JnZGltIDw8LSBkaW0oaW1nKQogICAgICAgIGRpbShpbWcpIDwtIE5VTEwKICAgICAgICAjIEFybWF6ZW5hIG9zIHBhZHJvZXMKICAgICAgICBwYWRyb2VzW1tsZW5ndGgocGFkcm9lcykrMV1dIDw8LSBhcy52ZWN0b3IoaWZlbHNlKGltZyA+PSAwLjIsIDEsIDApKQogICAgICB9CiAgICB9CiAgfQp9CmBgYAoKClNjcmlwdCBwYXJhIHRlc3RlIHZpc3VhbCBkb3MgZMOtZ2l0b3MKYGBge3J9CnRlc3RhLmRpZ2l0b3MgPC0gZnVuY3Rpb24obW9kZWxvKXsKCiAgIyBDYXJyZWdhIGRpZ2l0b3MgZGUgdGVzdGUKICBjYXJyZWdhLmRpZ2l0b3MoZGlnaXRvcyA9IGMoMCwxLDIsMyw0LDUsNiw3LDgsOSksMSwwLHRheGEucnVpZG8pCgogIHBsb3RkaW0gPSAyKm9yZ2RpbQogIHBsb3QoYygxLChwbG90ZGltWzFdKzUpKmxlbmd0aChkaWdpdG9zKSksIGMoMSwocGxvdGRpbVsyXSs1KSozKSwKICAgICAgICAgICAgdHlwZT0ibiIsIHhsYWI9IiIsIHlsYWI9IiIpCiAgeCA9IDEKCiAgZm9yIChpIGluIDE6bGVuZ3RoKHBhZHJvZXMpKSB7CiAgICBwYWRyYW8gPSBwYWRyb2VzW1tpXV0KCiAgICBydWlkbyA9IChydW5pZihsZW5ndGgocGFkcmFvKSwgMCwgMSkgPiB0YXhhLnJ1aWRvICkgKiAxCiAgICBlbnRyYWRhID0gcGFkcmFvICogcnVpZG8KICAgIHJldG9ybm8gPC0gYXV0b2VuY29kZXIucHJvcGFnYWNhbyhtb2RlbG8sZW50cmFkYSkKICAgIHJldCA8LSByZXRvcm5vJHkuZXNjb25kaWRhLnNhaWRhCiAgICByZXQgPC0gIGFzLnZlY3RvcihpZmVsc2UocmV0ID49IDAuNSwgMSwgMCkpCgogICAgIyBQYWRyYW8gb3JpZ2luYWwKICAgIGltZyA8LSBwYWRyYW87CiAgICBkaW0oaW1nKSA8LSBvcmdkaW0KICAgIGltYWdlIDwtIGFzLnJhc3RlcigoaW1nKzEpLzIpCiAgICByYXN0ZXJJbWFnZShpbWFnZSwgeCwgMSwgeCArIHBsb3RkaW1bMV0sIHBsb3RkaW1bMl0sIGludGVycG9sYXRlPUYpCgogICAgIyBFbnRyYWRhIGNvbSBydWlkbwogICAgaW1nIDwtIGVudHJhZGE7CiAgICBkaW0oaW1nKSA8LSBvcmdkaW0KICAgIGltYWdlIDwtIGFzLnJhc3RlcigoaW1nKzEpLzIpCiAgICByYXN0ZXJJbWFnZShpbWFnZSwgeCwgMSsocGxvdGRpbVsyXSs1KSwgeCArIHBsb3RkaW1bMV0sCiAgICAgICAgICAgICAgICAxKzIqKHBsb3RkaW1bMl0rNSksIGludGVycG9sYXRlPUYpCgogICAgIyBJbWFnZW0gcmVjdXBlcmFkYQogICAgaW1nIDwtIHJldDsKICAgIGRpbShpbWcpIDwtIG9yZ2RpbQogICAgaW1hZ2UgPC0gYXMucmFzdGVyKChpbWcrMSkvMikKICAgIHJhc3RlckltYWdlKGltYWdlLCB4LCAxKzIqKHBsb3RkaW1bMl0rNSksIHggKyBwbG90ZGltWzFdLAogICAgICAgICAgICAgICAgMSsyKihwbG90ZGltWzJdKzUpK3Bsb3RkaW1bMl0sIGludGVycG9sYXRlPUYpCgogICAgeCA9IHggKyBwbG90ZGltWzFdKzUKICB9Cn0KYGBgCgoKVmFtb3MgaW1wbGVtZW50YXIgdW1hIGZ1bsOnw6NvIGRlIGF0aXZhw6fDo28KYGBge3J9CmZ1bmNhby5hdGl2YWNhbyA8LSBmdW5jdGlvbih2KXsKCiAgIyBGdW7Dp8OjbyBsb2fDrXN0aWNhCiAgeSA8LSAxIC8gKDEgKyBleHAoLXYpKQoKICByZXR1cm4oeSkKfQpgYGAKCgpWYW1vcyB0YW1iw6ltIHByZWNpc2FyIGRhIGRlcml2YWRhIGRhIGZ1bsOnw6NvIGRlIGF0aXZhw6fDo28KYGBge3J9CmRlci5mdW5jYW8uYXRpdmFjYW8gPC0gZnVuY3Rpb24oeSl7CgogICMgRGVyaXZhZGEgZGEgbG9nw61zdGljYQogIGRlcml2YWRhIDwtIHkgKiAoMSAtIHkpCgogIHJldHVybihkZXJpdmFkYSkKfQpgYGAKCgpDcmlhw6fDo28gZGEgYXJxdWl0ZXR1cmEgZG8gQXV0b2VuY29kZXIuClNpbWlsYXIgw6AgYXJxdWl0ZXR1cmEgZG8gTUxQLCBwb3LDqW0gY29tIHVtYSBjYW1hZGEgZGUgc2HDrWRhIGNvbSBhIG1lc21hIApxdWFudGlkYWRlIGRlIG5ldXLDtG5pb3MgZGEgY2FtYWRhIGRlIGVudHJhZGEKYGBge3J9CmFycXVpdGV0dXJhIDwtIGZ1bmN0aW9uKG51bS5lbnRyYWRhLCBudW0uZXNjb25kaWRhLAogICAgICAgICAgICAgICAgICAgICAgICBmdW5jYW8uYXRpdmFjYW8sIGRlci5mdW5jYW8uYXRpdmFjYW8pewoKICBhcnEgPC0gbGlzdCgpCgogICMgUGFyYW1ldHJvcyBkYSByZWRlICAgIAogIGFycSRudW0uZW50cmFkYS5zYWlkYSA8LSBudW0uZW50cmFkYQogIGFycSRudW0uZXNjb25kaWRhIDwtIG51bS5lc2NvbmRpZGEKICBhcnEkZnVuY2FvLmF0aXZhY2FvIDwtIGZ1bmNhby5hdGl2YWNhbwogIGFycSRkZXIuZnVuY2FvLmF0aXZhY2FvIDwtIGRlci5mdW5jYW8uYXRpdmFjYW8KCiAgIyAyIG5ldXJvbmlvcyBuYSBjYW1hZGEgZXNjb25kaWRhCiAgIyAKICAjICAgICAgIEVudDEgICAgRW50MiAgIEJpYXMgCiAgIyAxICAgICB3MTEgICAgIHcxMiAgICB3MTMKICAjIDIgICAgIHcyMSAgICAgdzIyICAgIHcyMwoKICAjIFBlc29zIGNvbmVjdGFuZG8gZW50cmFkYSBlIGVzY29uZGlkYQogIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSA8LSAobnVtLmVudHJhZGErMSkqbnVtLmVzY29uZGlkYQogIGFycSRlc2NvbmRpZGEgPC0gbWF0cml4KHJ1bmlmKG1pbj0tMC41LG1heD0wLjUsIG51bS5wZXNvcy5lbnRyYWRhLmVzY29uZGlkYSksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnJvdz1udW0uZXNjb25kaWRhLCBuY29sPW51bS5lbnRyYWRhKzEpCgogICMgUGVzb3MgY29uZWN0YW5kbyBlc2NvbmRpZGEgZSBzYWlkYQogIG51bS5wZXNvcy5lc2NvbmRpZGEuc2FpZGEgPC0gKG51bS5lc2NvbmRpZGErMSkqbnVtLmVudHJhZGEKICBhcnEkc2FpZGEgPC0gbWF0cml4KHJ1bmlmKG1pbj0tMC41LG1heD0wLjUsICBudW0ucGVzb3MuZXNjb25kaWRhLnNhaWRhKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG5yb3c9bnVtLmVudHJhZGEsIG5jb2w9bnVtLmVzY29uZGlkYSsxKQoKICByZXR1cm4oYXJxKQp9CmBgYAoKCkZhc2UgZGUgcHJvcGFnYcOnw6NvCmBgYHtyfQphdXRvZW5jb2Rlci5wcm9wYWdhY2FvIDwtIGZ1bmN0aW9uKGFycSwgZXhlbXBsbyl7CgogICMgRW50cmFkYSAtPiBDYW1hIEVzY29uZGlkYQogIHYuZW50cmFkYS5lc2NvbmRpZGEgPC0gYXJxJGVzY29uZGlkYSAlKiUgYXMubnVtZXJpYyhjKGV4ZW1wbG8sMSkpCiAgeS5lbnRyYWRhLmVzY29uZGlkYSA8LSBhcnEkZnVuY2FvLmF0aXZhY2FvKHYuZW50cmFkYS5lc2NvbmRpZGEpCgogICMgQ2FtYWRhIEVzY29uZGlkYSAtPiBDYW1hZGEgZGUgU2FpZGEKICB2LmVzY29uZGlkYS5zYWlkYSA8LSBhcnEkc2FpZGEgJSolIGMoeS5lbnRyYWRhLmVzY29uZGlkYSwxKQogIHkuZXNjb25kaWRhLnNhaWRhIDwtIGFycSRmdW5jYW8uYXRpdmFjYW8odi5lc2NvbmRpZGEuc2FpZGEpCgogICMgUmVzdWx0YWRvcwogIHJlc3VsdGFkbyA8LSBsaXN0KCkKICByZXN1bHRhZG8kdi5lbnRyYWRhLmVzY29uZGlkYSA8LSB2LmVudHJhZGEuZXNjb25kaWRhCiAgcmVzdWx0YWRvJHkuZW50cmFkYS5lc2NvbmRpZGEgPC0geS5lbnRyYWRhLmVzY29uZGlkYQogIHJlc3VsdGFkbyR2LmVzY29uZGlkYS5zYWlkYSA8LSB2LmVzY29uZGlkYS5zYWlkYQogIHJlc3VsdGFkbyR5LmVzY29uZGlkYS5zYWlkYSA8LSB5LmVzY29uZGlkYS5zYWlkYQoKICByZXR1cm4ocmVzdWx0YWRvKQp9CmBgYAoKCkZhc2UgZGUgdHJlaW5hbWVudG8KYGBge3J9CmF1dG9lbmNvZGVyIDwtIGZ1bmN0aW9uKGFycSwgZGFkb3MsIG4sIGxpbWlhcil7CgogIGxvc3MgPC0gMTAKICBsb3NzLmFudGVyaW9yIDwtIDAKICBlcG9jYXMgPC0gMAoKICAjIFRyZWluYSBlcXRvIG8gZXJybyBmb3IgbWFpb3IgcXVlIHVtIGxpbWlhcgogIHdoaWxlKChhYnMobG9zcy1sb3NzLmFudGVyaW9yKSkgPiBsaW1pYXIpewogICAgICAgIAogICAgbG9zcy5hbnRlcmlvciA8LSBsb3NzCiAgICBsb3NzIDwtIDAKICAgICAgICAKICAgICMgVHJlaW5vIHBhcmEgdG9kb3Mgb3MgZXhlbXBsb3MgKGVwb2NhKQogICAgZm9yKGkgaW4gMTpsZW5ndGgoZGFkb3MpKXsKICAgICAgICAgICAgCiAgICAgICMgUGVnbyB1bSBleGVtcGxvIGRlIGVudHJhZGEKICAgICAgeCA8LSBkYWRvc1tbaV1dCiAgICAgICAgICAgIAogICAgICAjIFBlZ28gYSBzYWlkYSBkYSByZWRlIHBhcmEgbyBleGVtcGxvCiAgICAgIHJlc3VsdGFkbyA8LSBhdXRvZW5jb2Rlci5wcm9wYWdhY2FvKGFycSx4KQogICAgICB5IDwtIHJlc3VsdGFkbyR5LmVzY29uZGlkYS5zYWlkYQogICAgICAgICAgICAKICAgICAgIyBDYWxjdWxvIGRvIGVycm8gcGFyYSBvIGV4ZW1wbG8KICAgICAgZXJybyA8LSB4IC0geQogICAgICBsb3NzIDwtIGxvc3MgKyAtKHN1bSh4KmxvZyh5KSArICgxLXgpKmxvZygxLXkpKSkKICAgICAgICAgICAgCiAgICAgICMgR3JhZGllbnRlIGxvY2FsIG5vIG5ldXJvbmlvIGRlIHNhaWRhCiAgICAgICMgZXJybyAqIGRlcml2YWRhIGRhIGZ1bmNhbyBkZSBhdGl2YWNhbwogICAgICBncmFkLmxvY2FsLnNhaWRhIDwtIGVycm8gKiBhcnEkZGVyLmZ1bmNhby5hdGl2YWNhbyh5KQogICAgICAgICAgICAKICAgICAgIyBHcmFkaWVudGUgbG9jYWwgbm8gbmV1cm9uaW8gZXNjb25kaWRvCiAgICAgICMgZGVyaXZhZGEgZGEgZnVuY2FvIGRlIGF0aXZhY2FvIG5vIG5ldXJvbmlvIGVzY29uZGlkbyAqIHNvbWEgZG9zIGdyYWRpZW50ZXMKICAgICAgIyBsb2NhaXMgZG9zIG5ldXJvbmlvcyBjb25lY3RhZG9zIG5hIHByb3hpbWEgY2FtYWRhICogcGVzb3MgY29uZWN0YW5kbyBhIGNhbWFkYQogICAgICAgICAgICAKICAgICAgIyBlc2NvbmRpZGEgY29tIGEgc2FpZGEKICAgICAgcGVzb3Muc2FpZGEgPC0gYXJxJHNhaWRhWywxOmFycSRudW0uZXNjb25kaWRhXQogICAgICBncmFkLmxvY2FsLmVzY29uZGlkYSA8LSAKICAgICAgICAgIGFzLm51bWVyaWMoYXJxJGRlci5mdW5jYW8uYXRpdmFjYW8ocmVzdWx0YWRvJHkuZW50cmFkYS5lc2NvbmRpZGEpKSAqCiAgICAgICAgICAgKGFzLnZlY3RvcihncmFkLmxvY2FsLnNhaWRhKSAlKiUgcGVzb3Muc2FpZGEpCiAgICAgICAgICAgIAogICAgICAjIEFqdXN0ZSBkb3MgcGVzb3MKICAgICAgIyBTYWlkYQogICAgICBhcnEkc2FpZGEgPC0gYXJxJHNhaWRhICsgbiAqIChncmFkLmxvY2FsLnNhaWRhICUqJSAKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGMocmVzdWx0YWRvJHkuZW50cmFkYS5lc2NvbmRpZGEsMSkpCiAgICAgICMgRXNjb25kaWRhCiAgICAgIGFycSRlc2NvbmRpZGEgPC0gYXJxJGVzY29uZGlkYSArIG4gKiAodChncmFkLmxvY2FsLmVzY29uZGlkYSkgJSolCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFzLm51bWVyaWMoYyh4LDEpKSkKICAgIH0KICAKICAgIGxvc3MgPC0gbG9zcyAvIGxlbmd0aChkYWRvcykKICAgIGNhdCgiRXBvY2EgPSAiLGVwb2NhcywiIC8gRXJybyA9ICIsbG9zcywiIC8gIixhYnMobG9zcy1sb3NzLmFudGVyaW9yKSwiXG4iKQogICAgZXBvY2FzIDwtIGVwb2NhcysxCiAgfQoKICByZXRvcm5vIDwtIGxpc3QoKQogIHJldG9ybm8kYXJxIDwtIGFycQogIHJldG9ybm8kZXBvY2FzIDwtIGVwb2NhcwoKICByZXR1cm4ocmV0b3JubykKfQpgYGAKCgpUZXN0ZSBjb20gY2FtYWRhIHN1YmNvbXBsZXRhCmBgYHtyfQojID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQojIENhcnJlZ2Egb3MgZGlnaXRvcwpjYXJyZWdhLmRpZ2l0b3MoZGlnaXRvcyA9IGMoMCwxLDIsMyw0LDUsNiw3LDgsOSksNTAsMSwwLjMpCgojIENyaWEgYSBhcnF1aXRldHV0YQphcnEgPC0gYXJxdWl0ZXR1cmEobGVuZ3RoKHBhZHJvZXNbWzFdXSksbGVuZ3RoKHBhZHJvZXNbWzFdXSktNDAwLAogICAgICAgICAgICAgICAgICAgZnVuY2FvLmF0aXZhY2FvLGRlci5mdW5jYW8uYXRpdmFjYW8pCgojIFRyZWluYSBvIG1vZGVsbwptb2RlbG8gPC0gYXV0b2VuY29kZXIoYXJxLHBhZHJvZXMsMC4yLDAuMSkKCiMgVGVzdGEgcGFyYSBub3ZvcyBkaWdpdG9zCnRlc3RhLmRpZ2l0b3MobW9kZWxvJGFycSkKIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KYGBgCgpUZXN0ZSBjb20gY2FtYWRhIHNvYnJlY29tcGxldGEKYGBge3J9CiMgPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CiMgQ2FycmVnYSBvcyBkaWdpdG9zCmNhcnJlZ2EuZGlnaXRvcyhkaWdpdG9zID0gYygwLDEsMiwzLDQsNSw2LDcsOCw5KSw1MCwxLDAuMykKI2NhcnJlZ2EuZGlnaXRvczIoZGlnaXRvcyA9IGMoMCwxLDIsMyw0LDUsNiw3LDgsOSkpCgojIENyaWEgYSBhcnF1aXRldHV0YQphcnEgPC0gYXJxdWl0ZXR1cmEobGVuZ3RoKHBhZHJvZXNbWzFdXSksbGVuZ3RoKHBhZHJvZXNbWzFdXSkrNDAwLAogICAgICAgICAgICAgICAgICAgZnVuY2FvLmF0aXZhY2FvLGRlci5mdW5jYW8uYXRpdmFjYW8pCgojIFRyZWluYSBvIG1vZGVsbwptb2RlbG8gPC0gYXV0b2VuY29kZXIoYXJxLHBhZHJvZXMsMC4yLDAuMSkKCiMgVGVzdGEgcGFyYSBub3ZvcyBkaWdpdG9zCnRlc3RhLmRpZ2l0b3MobW9kZWxvJGFycSkKIyA9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0KYGBgCgoKCgo=