This notebook contains the code samples found in Chapter 8, Section 1 of Deep Learning with R. Note that the original text features far more content, in particular further explanations and figures: in this notebook, you will only find source code and related comments.
Implementing character-level LSTM text generation
Let’s put these ideas in practice in a Keras implementation. The first thing we need is a lot of text data that we can use to learn a language model. You could use any sufficiently large text file or set of text files – Wikipedia, the Lord of the Rings, etc. In this example we will use some of the writings of Nietzsche, the late-19th century German philosopher (translated to English). The language model we will learn will thus be specifically a model of Nietzsche’s writing style and topics of choice, rather than a more generic model of the English language.
Preparing the data
Let’s start by downloading the corpus and converting it to lowercase:
library(keras)
library(stringr)
path <- get_file(
"nietzsche.txt",
origin = "https://s3.amazonaws.com/text-datasets/nietzsche.txt"
)
text <- tolower(readChar(path, file.info(path)$size))
cat("Corpus length:", nchar(text), "\n")
Corpus length: 600893
Next, you’ll extract partially overlapping sequences of length maxlen
, one-hot encode them, and pack them in a 3D array x
of shape (sequences, maxlen, unique_characters)
. Simultaneously, you’ll prepare an array y
containing the corresponding targets: the one-hot-encoded characters that come after each extracted sequence.
maxlen <- 60 # Length of extracted character sequences
step <- 3 # We sample a new sequence every `step` characters
text_indexes <- seq(1, nchar(text) - maxlen, by = step)
# This holds our extracted sequences
sentences <- str_sub(text, text_indexes, text_indexes + maxlen - 1)
# This holds the targets (the follow-up characters)
next_chars <- str_sub(text, text_indexes + maxlen, text_indexes + maxlen)
cat("Number of sequences: ", length(sentences), "\n")
Number of sequences: 200278
# List of unique characters in the corpus
chars <- unique(sort(strsplit(text, "")[[1]]))
cat("Unique characters:", length(chars), "\n")
Unique characters: 57
# Dictionary mapping unique characters to their index in `chars`
char_indices <- 1:length(chars)
names(char_indices) <- chars
# Next, one-hot encode the characters into binary arrays.
cat("Vectorization...\n")
Vectorization...
x <- array(0L, dim = c(length(sentences), maxlen, length(chars)))
y <- array(0L, dim = c(length(sentences), length(chars)))
for (i in 1:length(sentences)) {
sentence <- strsplit(sentences[[i]], "")[[1]]
for (t in 1:length(sentence)) {
char <- sentence[[t]]
x[i, t, char_indices[[char]]] <- 1
}
next_char <- next_chars[[i]]
y[i, char_indices[[next_char]]] <- 1
}
Building the network
This network is a single LSTM layer followed by a dense classifier and softmax over all possible characters. But note that recurrent neural networks aren’t the only way to do sequence data generation; 1D convnets also have proven extremely successful at this task in recent times.
model <- keras_model_sequential() %>%
layer_lstm(units = 128, input_shape = c(maxlen, length(chars))) %>%
layer_dense(units = length(chars), activation = "softmax")
Since our targets are one-hot encoded, we will use categorical_crossentropy
as the loss to train the model:
optimizer <- optimizer_rmsprop(lr = 0.01)
model %>% compile(
loss = "categorical_crossentropy",
optimizer = optimizer
)
Training the language model and sampling from it
Given a trained model and a seed text snippet, we generate new text by repeatedly:
- Drawing from the model a probability distribution over the next character given the text available so far
- Reweighting the distribution to a certain “temperature”
- Sampling the next character at random according to the reweighted distribution
- Adding the new character at the end of the available text
This is the code we use to reweight the original probability distribution coming out of the model, and draw a character index from it (the “sampling function”):
sample_next_char <- function(preds, temperature = 1.0) {
preds <- as.numeric(preds)
preds <- log(preds) / temperature
exp_preds <- exp(preds)
preds <- exp_preds / sum(exp_preds)
which.max(t(rmultinom(1, 1, preds)))
}
Finally, the following loop repeatedly trains and generates text. You begin generating text using a range of different temperatures after every epoch. This allows you to see how the generated text evolves as the model begins to converge, as well as the impact of temperature in the sampling strategy.
for (epoch in 1:60) {
cat("epoch", epoch, "\n")
# Fit the model for 1 epoch on the available training data
model %>% fit(x, y, batch_size = 128, epochs = 1)
# Select a text seed at random
start_index <- sample(1:(nchar(text) - maxlen - 1), 1)
seed_text <- str_sub(text, start_index, start_index + maxlen - 1)
cat("--- Generating with seed:", seed_text, "\n\n")
for (temperature in c(0.2, 0.5, 1.0, 1.2)) {
cat("------ temperature:", temperature, "\n")
cat(seed_text, "\n")
generated_text <- seed_text
# We generate 400 characters
for (i in 1:400) {
sampled <- array(0, dim = c(1, maxlen, length(chars)))
generated_chars <- strsplit(generated_text, "")[[1]]
for (t in 1:length(generated_chars)) {
char <- generated_chars[[t]]
sampled[1, t, char_indices[[char]]] <- 1
}
preds <- model %>% predict(sampled, verbose = 0)
next_index <- sample_next_char(preds[1,], temperature)
next_char <- chars[[next_index]]
generated_text <- paste0(generated_text, next_char)
generated_text <- substring(generated_text, 2)
cat(next_char)
}
cat("\n\n")
}
}
Here, we used the random seed text “new faculty, and the jubilation reached its climax when kant.” Here’s what you get at epoch 20, long before the model has fully converged, with temperature=0.2
:
new faculty, and the jubilation reached its climax when kant and such a man
in the same time the spirit of the surely and the such the such
as a man is the sunligh and subject the present to the superiority of the
special pain the most man and strange the subjection of the
special conscience the special and nature and such men the subjection of the
special men, the most surely the subjection of the special
intellect of the subjection of the same things and
Here’s the result with temperature=0.5
:
new faculty, and the jubilation reached its climax when kant in the eterned
and such man as it's also become himself the condition of the
experience of off the basis the superiory and the special morty of the
strength, in the langus, as which the same time life and "even who
discless the mankind, with a subject and fact all you have to be the stand
and lave no comes a troveration of the man and surely the
conscience the superiority, and when one must be w
And here’s what you get with temperature=1.0
:
new faculty, and the jubilation reached its climax when kant, as a
periliting of manner to all definites and transpects it it so
hicable and ont him artiar resull
too such as if ever the proping to makes as cnecience. to been juden,
all every could coldiciousnike hother aw passife, the plies like
which might thiod was account, indifferent germin, that everythery
certain destrution, intellect into the deteriorablen origin of moralian,
and a lessority o
At epoch 60, the model has mostly converged, and the text starts to look significantly more coherent. Here’s the result with temperature=0.2
:
cheerfulness, friendliness and kindness of a heart are the sense of the
spirit is a man with the sense of the sense of the world of the
self-end and self-concerning the subjection of the strengthorixes--the
subjection of the subjection of the subjection of the
self-concerning the feelings in the superiority in the subjection of the
subjection of the spirit isn't to be a man of the sense of the
subjection and said to the strength of the sense of the
Here is temperature=0.5
:
cheerfulness, friendliness and kindness of a heart are the part of the soul
who have been the art of the philosophers, and which the one
won't say, which is it the higher the and with religion of the frences.
the life of the spirit among the most continuess of the
strengther of the sense the conscience of men of precisely before enough
presumption, and can mankind, and something the conceptions, the
subjection of the sense and suffering and the
And here is temperature=1.0
:
cheerfulness, friendliness and kindness of a heart are spiritual by the
ciuture for the
entalled is, he astraged, or errors to our you idstood--and it needs,
to think by spars to whole the amvives of the newoatly, prefectly
raals! it was
name, for example but voludd atu-especity"--or rank onee, or even all
"solett increessic of the world and
implussional tragedy experience, transf, or insiderar,--must hast
if desires of the strubction is be stronges
As you can see, a low temperature results in extremely repetitive and predictable text, but where local structure is highly realistic: in particular, all words (a word being a local pattern of characters) are real English words. With higher temperatures, the generated text becomes more interesting, surprising, even creative; it may sometimes invent completely new words that sound somewhat plausible (such as “eterned” or “troveration”). With a high temperature, the local structure starts breaking down and most words look like semi-random strings of characters. Without a doubt, here 0.5 is the most interesting temperature for text generation in this specific setup. Always experiment with multiple sampling strategies! A clever balance between learned structure and randomness is what makes generation interesting.
Note that by training a bigger model, longer, on more data, you can achieve generated samples that will look much more coherent and realistic than ours. But of course, don’t expect to ever generate any meaningful text, other than by random chance: all we are doing is sampling data from a statistical model of which characters come after which characters. Language is a communication channel, and there is a distinction between what communications are about, and the statistical structure of the messages in which communications are encoded. To evidence this distinction, here is a thought experiment: what if human language did a better job at compressing communications, much like our computers do with most of our digital communications? Then language would be no less meaningful, yet it would lack any intrinsic statistical structure, thus making it impossible to learn a language model like we just did.
Take aways
- We can generate discrete sequence data by training a model to predict the next tokens(s) given previous tokens.
- In the case of text, such a model is called a “language model” and could be based on either words or characters.
- Sampling the next token requires balance between adhering to what the model judges likely, and introducing randomness.
- One way to handle this is the notion of softmax temperature. Always experiment with different temperatures to find the “right” one.
LS0tCnRpdGxlOiAiVGV4dCBnZW5lcmF0aW9uIHdpdGggTFNUTSIKb3V0cHV0OiAKICBodG1sX25vdGVib29rOiAKICAgIHRoZW1lOiBjZXJ1bGVhbgogICAgaGlnaGxpZ2h0OiB0ZXh0bWF0ZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQprbml0cjo6b3B0c19jaHVuayRzZXQod2FybmluZyA9IEZBTFNFLCBtZXNzYWdlID0gRkFMU0UpCmBgYAoKKioqCgpUaGlzIG5vdGVib29rIGNvbnRhaW5zIHRoZSBjb2RlIHNhbXBsZXMgZm91bmQgaW4gQ2hhcHRlciA4LCBTZWN0aW9uIDEgb2YgW0RlZXAgTGVhcm5pbmcgd2l0aCBSXShodHRwczovL3d3dy5tYW5uaW5nLmNvbS9ib29rcy9kZWVwLWxlYXJuaW5nLXdpdGgtcikuIE5vdGUgdGhhdCB0aGUgb3JpZ2luYWwgdGV4dCBmZWF0dXJlcyBmYXIgbW9yZSBjb250ZW50LCBpbiBwYXJ0aWN1bGFyIGZ1cnRoZXIgZXhwbGFuYXRpb25zIGFuZCBmaWd1cmVzOiBpbiB0aGlzIG5vdGVib29rLCB5b3Ugd2lsbCBvbmx5IGZpbmQgc291cmNlIGNvZGUgYW5kIHJlbGF0ZWQgY29tbWVudHMuCgoqKioKCgojIyBJbXBsZW1lbnRpbmcgY2hhcmFjdGVyLWxldmVsIExTVE0gdGV4dCBnZW5lcmF0aW9uCgoKTGV0J3MgcHV0IHRoZXNlIGlkZWFzIGluIHByYWN0aWNlIGluIGEgS2VyYXMgaW1wbGVtZW50YXRpb24uIFRoZSBmaXJzdCB0aGluZyB3ZSBuZWVkIGlzIGEgbG90IG9mIHRleHQgZGF0YSB0aGF0IHdlIGNhbiB1c2UgdG8gbGVhcm4gYSBsYW5ndWFnZSBtb2RlbC4gWW91IGNvdWxkIHVzZSBhbnkgc3VmZmljaWVudGx5IGxhcmdlIHRleHQgZmlsZSBvciBzZXQgb2YgdGV4dCBmaWxlcyAtLSBXaWtpcGVkaWEsIHRoZSBMb3JkIG9mIHRoZSBSaW5ncywgZXRjLiBJbiB0aGlzIGV4YW1wbGUgd2Ugd2lsbCB1c2Ugc29tZSBvZiB0aGUgd3JpdGluZ3Mgb2YgTmlldHpzY2hlLCB0aGUgbGF0ZS0xOXRoIGNlbnR1cnkgR2VybWFuIHBoaWxvc29waGVyICh0cmFuc2xhdGVkIHRvIEVuZ2xpc2gpLiBUaGUgbGFuZ3VhZ2UgbW9kZWwgd2Ugd2lsbCBsZWFybiB3aWxsIHRodXMgYmUgc3BlY2lmaWNhbGx5IGEgbW9kZWwgb2YgTmlldHpzY2hlJ3Mgd3JpdGluZyBzdHlsZSBhbmQgdG9waWNzIG9mIGNob2ljZSwgcmF0aGVyIHRoYW4gYSBtb3JlIGdlbmVyaWMgbW9kZWwgb2YgdGhlIEVuZ2xpc2ggbGFuZ3VhZ2UuCgojIyBQcmVwYXJpbmcgdGhlIGRhdGEKCkxldCdzIHN0YXJ0IGJ5IGRvd25sb2FkaW5nIHRoZSBjb3JwdXMgYW5kIGNvbnZlcnRpbmcgaXQgdG8gbG93ZXJjYXNlOgoKYGBge3J9CmxpYnJhcnkoa2VyYXMpCmxpYnJhcnkoc3RyaW5ncikKCnBhdGggPC0gZ2V0X2ZpbGUoCiAgIm5pZXR6c2NoZS50eHQiLAogIG9yaWdpbiA9ICJodHRwczovL3MzLmFtYXpvbmF3cy5jb20vdGV4dC1kYXRhc2V0cy9uaWV0enNjaGUudHh0IgopCnRleHQgPC0gdG9sb3dlcihyZWFkQ2hhcihwYXRoLCBmaWxlLmluZm8ocGF0aCkkc2l6ZSkpCmNhdCgiQ29ycHVzIGxlbmd0aDoiLCBuY2hhcih0ZXh0KSwgIlxuIikKYGBgCgpOZXh0LCB5b3UnbGwgZXh0cmFjdCBwYXJ0aWFsbHkgb3ZlcmxhcHBpbmcgc2VxdWVuY2VzIG9mIGxlbmd0aCBgbWF4bGVuYCwgb25lLWhvdCBlbmNvZGUgdGhlbSwgYW5kIHBhY2sgdGhlbSBpbiBhIDNEIGFycmF5IGB4YCBvZiBzaGFwZSBgKHNlcXVlbmNlcywgbWF4bGVuLCB1bmlxdWVfY2hhcmFjdGVycylgLiBTaW11bHRhbmVvdXNseSwgeW91J2xsIHByZXBhcmUgYW4gYXJyYXkgYHlgIGNvbnRhaW5pbmcgdGhlIGNvcnJlc3BvbmRpbmcgdGFyZ2V0czogdGhlIG9uZS1ob3QtZW5jb2RlZCBjaGFyYWN0ZXJzIHRoYXQgY29tZSBhZnRlciBlYWNoIGV4dHJhY3RlZCBzZXF1ZW5jZS4KCgpgYGB7cn0KbWF4bGVuIDwtIDYwICAjIExlbmd0aCBvZiBleHRyYWN0ZWQgY2hhcmFjdGVyIHNlcXVlbmNlcwoKc3RlcCA8LSAzICAjIFdlIHNhbXBsZSBhIG5ldyBzZXF1ZW5jZSBldmVyeSBgc3RlcGAgY2hhcmFjdGVycwogIAp0ZXh0X2luZGV4ZXMgPC0gc2VxKDEsIG5jaGFyKHRleHQpIC0gbWF4bGVuLCBieSA9IHN0ZXApCgojIFRoaXMgaG9sZHMgb3VyIGV4dHJhY3RlZCBzZXF1ZW5jZXMKc2VudGVuY2VzIDwtIHN0cl9zdWIodGV4dCwgdGV4dF9pbmRleGVzLCB0ZXh0X2luZGV4ZXMgKyBtYXhsZW4gLSAxKQoKIyBUaGlzIGhvbGRzIHRoZSB0YXJnZXRzICh0aGUgZm9sbG93LXVwIGNoYXJhY3RlcnMpCm5leHRfY2hhcnMgPC0gc3RyX3N1Yih0ZXh0LCB0ZXh0X2luZGV4ZXMgKyBtYXhsZW4sIHRleHRfaW5kZXhlcyArIG1heGxlbikKCmNhdCgiTnVtYmVyIG9mIHNlcXVlbmNlczogIiwgbGVuZ3RoKHNlbnRlbmNlcyksICJcbiIpCgojIExpc3Qgb2YgdW5pcXVlIGNoYXJhY3RlcnMgaW4gdGhlIGNvcnB1cwpjaGFycyA8LSB1bmlxdWUoc29ydChzdHJzcGxpdCh0ZXh0LCAiIilbWzFdXSkpCmNhdCgiVW5pcXVlIGNoYXJhY3RlcnM6IiwgbGVuZ3RoKGNoYXJzKSwgIlxuIikKCiMgRGljdGlvbmFyeSBtYXBwaW5nIHVuaXF1ZSBjaGFyYWN0ZXJzIHRvIHRoZWlyIGluZGV4IGluIGBjaGFyc2AKY2hhcl9pbmRpY2VzIDwtIDE6bGVuZ3RoKGNoYXJzKSAKbmFtZXMoY2hhcl9pbmRpY2VzKSA8LSBjaGFycwoKIyBOZXh0LCBvbmUtaG90IGVuY29kZSB0aGUgY2hhcmFjdGVycyBpbnRvIGJpbmFyeSBhcnJheXMuCmNhdCgiVmVjdG9yaXphdGlvbi4uLlxuIikgCnggPC0gYXJyYXkoMEwsIGRpbSA9IGMobGVuZ3RoKHNlbnRlbmNlcyksIG1heGxlbiwgbGVuZ3RoKGNoYXJzKSkpCnkgPC0gYXJyYXkoMEwsIGRpbSA9IGMobGVuZ3RoKHNlbnRlbmNlcyksIGxlbmd0aChjaGFycykpKQpmb3IgKGkgaW4gMTpsZW5ndGgoc2VudGVuY2VzKSkgewogIHNlbnRlbmNlIDwtIHN0cnNwbGl0KHNlbnRlbmNlc1tbaV1dLCAiIilbWzFdXQogIGZvciAodCBpbiAxOmxlbmd0aChzZW50ZW5jZSkpIHsKICAgIGNoYXIgPC0gc2VudGVuY2VbW3RdXQogICAgeFtpLCB0LCBjaGFyX2luZGljZXNbW2NoYXJdXV0gPC0gMQogIH0KICBuZXh0X2NoYXIgPC0gbmV4dF9jaGFyc1tbaV1dCiAgeVtpLCBjaGFyX2luZGljZXNbW25leHRfY2hhcl1dXSA8LSAxCn0KYGBgCgojIyBCdWlsZGluZyB0aGUgbmV0d29yawoKVGhpcyBuZXR3b3JrIGlzIGEgc2luZ2xlIExTVE0gbGF5ZXIgZm9sbG93ZWQgYnkgYSBkZW5zZSBjbGFzc2lmaWVyIGFuZCBzb2Z0bWF4IG92ZXIgYWxsIHBvc3NpYmxlIGNoYXJhY3RlcnMuIEJ1dCBub3RlIHRoYXQgcmVjdXJyZW50IG5ldXJhbCBuZXR3b3JrcyBhcmVuJ3QgdGhlIG9ubHkgd2F5IHRvIGRvIHNlcXVlbmNlIGRhdGEgZ2VuZXJhdGlvbjsgMUQgY29udm5ldHMgYWxzbyBoYXZlIHByb3ZlbiBleHRyZW1lbHkgc3VjY2Vzc2Z1bCBhdCB0aGlzIHRhc2sgaW4gcmVjZW50IHRpbWVzLgoKCmBgYHtyfQptb2RlbCA8LSBrZXJhc19tb2RlbF9zZXF1ZW50aWFsKCkgJT4lIAogIGxheWVyX2xzdG0odW5pdHMgPSAxMjgsIGlucHV0X3NoYXBlID0gYyhtYXhsZW4sIGxlbmd0aChjaGFycykpKSAlPiUgCiAgbGF5ZXJfZGVuc2UodW5pdHMgPSBsZW5ndGgoY2hhcnMpLCBhY3RpdmF0aW9uID0gInNvZnRtYXgiKQpgYGAKClNpbmNlIG91ciB0YXJnZXRzIGFyZSBvbmUtaG90IGVuY29kZWQsIHdlIHdpbGwgdXNlIGBjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHlgIGFzIHRoZSBsb3NzIHRvIHRyYWluIHRoZSBtb2RlbDoKCmBgYHtyfQpvcHRpbWl6ZXIgPC0gb3B0aW1pemVyX3Jtc3Byb3AobHIgPSAwLjAxKQoKbW9kZWwgJT4lIGNvbXBpbGUoCiAgbG9zcyA9ICJjYXRlZ29yaWNhbF9jcm9zc2VudHJvcHkiLCAKICBvcHRpbWl6ZXIgPSBvcHRpbWl6ZXIKKSAgIApgYGAKCiMjIFRyYWluaW5nIHRoZSBsYW5ndWFnZSBtb2RlbCBhbmQgc2FtcGxpbmcgZnJvbSBpdAoKCkdpdmVuIGEgdHJhaW5lZCBtb2RlbCBhbmQgYSBzZWVkIHRleHQgc25pcHBldCwgd2UgZ2VuZXJhdGUgbmV3IHRleHQgYnkgcmVwZWF0ZWRseToKCiogMSkgRHJhd2luZyBmcm9tIHRoZSBtb2RlbCBhIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBvdmVyIHRoZSBuZXh0IGNoYXJhY3RlciBnaXZlbiB0aGUgdGV4dCBhdmFpbGFibGUgc28gZmFyCiogMikgUmV3ZWlnaHRpbmcgdGhlIGRpc3RyaWJ1dGlvbiB0byBhIGNlcnRhaW4gInRlbXBlcmF0dXJlIgoqIDMpIFNhbXBsaW5nIHRoZSBuZXh0IGNoYXJhY3RlciBhdCByYW5kb20gYWNjb3JkaW5nIHRvIHRoZSByZXdlaWdodGVkIGRpc3RyaWJ1dGlvbgoqIDQpIEFkZGluZyB0aGUgbmV3IGNoYXJhY3RlciBhdCB0aGUgZW5kIG9mIHRoZSBhdmFpbGFibGUgdGV4dAoKVGhpcyBpcyB0aGUgY29kZSB3ZSB1c2UgdG8gcmV3ZWlnaHQgdGhlIG9yaWdpbmFsIHByb2JhYmlsaXR5IGRpc3RyaWJ1dGlvbiBjb21pbmcgb3V0IG9mIHRoZSBtb2RlbCwgYW5kIGRyYXcgYSBjaGFyYWN0ZXIgaW5kZXggZnJvbSBpdCAodGhlICJzYW1wbGluZyBmdW5jdGlvbiIpOgoKYGBge3J9CnNhbXBsZV9uZXh0X2NoYXIgPC0gZnVuY3Rpb24ocHJlZHMsIHRlbXBlcmF0dXJlID0gMS4wKSB7CiAgcHJlZHMgPC0gYXMubnVtZXJpYyhwcmVkcykKICBwcmVkcyA8LSBsb2cocHJlZHMpIC8gdGVtcGVyYXR1cmUKICBleHBfcHJlZHMgPC0gZXhwKHByZWRzKQogIHByZWRzIDwtIGV4cF9wcmVkcyAvIHN1bShleHBfcHJlZHMpCiAgd2hpY2gubWF4KHQocm11bHRpbm9tKDEsIDEsIHByZWRzKSkpCn0KYGBgCgpGaW5hbGx5LCB0aGUgZm9sbG93aW5nIGxvb3AgcmVwZWF0ZWRseSB0cmFpbnMgYW5kIGdlbmVyYXRlcyB0ZXh0LiBZb3UgYmVnaW4gZ2VuZXJhdGluZyB0ZXh0IHVzaW5nIGEgcmFuZ2Ugb2YgZGlmZmVyZW50IHRlbXBlcmF0dXJlcyBhZnRlciBldmVyeSBlcG9jaC4gVGhpcyBhbGxvd3MgeW91IHRvIHNlZSBob3cgdGhlIGdlbmVyYXRlZCB0ZXh0IGV2b2x2ZXMgYXMgdGhlIG1vZGVsIGJlZ2lucyB0byBjb252ZXJnZSwgYXMgd2VsbCBhcyB0aGUgaW1wYWN0IG9mIHRlbXBlcmF0dXJlIGluIHRoZSBzYW1wbGluZyBzdHJhdGVneS4KCmBgYHtyfQpmb3IgKGVwb2NoIGluIDE6NjApIHsKICAKICBjYXQoImVwb2NoIiwgZXBvY2gsICJcbiIpCiAgCiAgIyBGaXQgdGhlIG1vZGVsIGZvciAxIGVwb2NoIG9uIHRoZSBhdmFpbGFibGUgdHJhaW5pbmcgZGF0YQogIG1vZGVsICU+JSBmaXQoeCwgeSwgYmF0Y2hfc2l6ZSA9IDEyOCwgZXBvY2hzID0gMSkgCiAgCiAgIyBTZWxlY3QgYSB0ZXh0IHNlZWQgYXQgcmFuZG9tCiAgc3RhcnRfaW5kZXggPC0gc2FtcGxlKDE6KG5jaGFyKHRleHQpIC0gbWF4bGVuIC0gMSksIDEpICAKICBzZWVkX3RleHQgPC0gc3RyX3N1Yih0ZXh0LCBzdGFydF9pbmRleCwgc3RhcnRfaW5kZXggKyBtYXhsZW4gLSAxKQogIAogIGNhdCgiLS0tIEdlbmVyYXRpbmcgd2l0aCBzZWVkOiIsIHNlZWRfdGV4dCwgIlxuXG4iKQogIAogIGZvciAodGVtcGVyYXR1cmUgaW4gYygwLjIsIDAuNSwgMS4wLCAxLjIpKSB7CiAgICAKICAgIGNhdCgiLS0tLS0tIHRlbXBlcmF0dXJlOiIsIHRlbXBlcmF0dXJlLCAiXG4iKQogICAgY2F0KHNlZWRfdGV4dCwgIlxuIikKICAgIAogICAgZ2VuZXJhdGVkX3RleHQgPC0gc2VlZF90ZXh0CiAgICAKICAgICAjIFdlIGdlbmVyYXRlIDQwMCBjaGFyYWN0ZXJzCiAgICBmb3IgKGkgaW4gMTo0MDApIHsKICAgICAgCiAgICAgIHNhbXBsZWQgPC0gYXJyYXkoMCwgZGltID0gYygxLCBtYXhsZW4sIGxlbmd0aChjaGFycykpKQogICAgICBnZW5lcmF0ZWRfY2hhcnMgPC0gc3Ryc3BsaXQoZ2VuZXJhdGVkX3RleHQsICIiKVtbMV1dCiAgICAgIGZvciAodCBpbiAxOmxlbmd0aChnZW5lcmF0ZWRfY2hhcnMpKSB7CiAgICAgICAgY2hhciA8LSBnZW5lcmF0ZWRfY2hhcnNbW3RdXQogICAgICAgIHNhbXBsZWRbMSwgdCwgY2hhcl9pbmRpY2VzW1tjaGFyXV1dIDwtIDEKICAgICAgfQogICAgICAgIAogICAgICBwcmVkcyA8LSBtb2RlbCAlPiUgcHJlZGljdChzYW1wbGVkLCB2ZXJib3NlID0gMCkKICAgICAgbmV4dF9pbmRleCA8LSBzYW1wbGVfbmV4dF9jaGFyKHByZWRzWzEsXSwgdGVtcGVyYXR1cmUpCiAgICAgIG5leHRfY2hhciA8LSBjaGFyc1tbbmV4dF9pbmRleF1dCiAgICAgIAogICAgICBnZW5lcmF0ZWRfdGV4dCA8LSBwYXN0ZTAoZ2VuZXJhdGVkX3RleHQsIG5leHRfY2hhcikKICAgICAgZ2VuZXJhdGVkX3RleHQgPC0gc3Vic3RyaW5nKGdlbmVyYXRlZF90ZXh0LCAyKQogICAgICAKICAgICAgY2F0KG5leHRfY2hhcikKICAgIH0KICAgIGNhdCgiXG5cbiIpCiAgfQp9CmBgYAoKSGVyZSwgd2UgdXNlZCB0aGUgcmFuZG9tIHNlZWQgdGV4dCAibmV3IGZhY3VsdHksIGFuZCB0aGUganViaWxhdGlvbiByZWFjaGVkIGl0cyBjbGltYXggd2hlbiBrYW50LiIgSGVyZSdzIHdoYXQgeW91IGdldCBhdCBlcG9jaCAyMCwgbG9uZyBiZWZvcmUgdGhlIG1vZGVsIGhhcyBmdWxseSBjb252ZXJnZWQsIHdpdGggYHRlbXBlcmF0dXJlPTAuMmA6CgpgYGAKbmV3IGZhY3VsdHksIGFuZCB0aGUganViaWxhdGlvbiByZWFjaGVkIGl0cyBjbGltYXggd2hlbiBrYW50IGFuZCBzdWNoIGEgbWFuCmluIHRoZSBzYW1lIHRpbWUgdGhlIHNwaXJpdCBvZiB0aGUgc3VyZWx5IGFuZCB0aGUgc3VjaCB0aGUgc3VjaCAKYXMgYSBtYW4gaXMgdGhlIHN1bmxpZ2ggYW5kIHN1YmplY3QgdGhlIHByZXNlbnQgdG8gdGhlIHN1cGVyaW9yaXR5IG9mIHRoZSAKc3BlY2lhbCBwYWluIHRoZSBtb3N0IG1hbiBhbmQgc3RyYW5nZSB0aGUgc3ViamVjdGlvbiBvZiB0aGUgCnNwZWNpYWwgY29uc2NpZW5jZSB0aGUgc3BlY2lhbCBhbmQgbmF0dXJlIGFuZCBzdWNoIG1lbiB0aGUgc3ViamVjdGlvbiBvZiB0aGUKc3BlY2lhbCBtZW4sIHRoZSBtb3N0IHN1cmVseSB0aGUgc3ViamVjdGlvbiBvZiB0aGUgc3BlY2lhbCAKaW50ZWxsZWN0IG9mIHRoZSBzdWJqZWN0aW9uIG9mIHRoZSBzYW1lIHRoaW5ncyBhbmQKYGBgCgpIZXJlJ3MgdGhlIHJlc3VsdCB3aXRoIGB0ZW1wZXJhdHVyZT0wLjVgOgoKYGBgCm5ldyBmYWN1bHR5LCBhbmQgdGhlIGp1YmlsYXRpb24gcmVhY2hlZCBpdHMgY2xpbWF4IHdoZW4ga2FudCBpbiB0aGUgZXRlcm5lZCAKYW5kIHN1Y2ggbWFuIGFzIGl0J3MgYWxzbyBiZWNvbWUgaGltc2VsZiB0aGUgY29uZGl0aW9uIG9mIHRoZSAKZXhwZXJpZW5jZSBvZiBvZmYgdGhlIGJhc2lzIHRoZSBzdXBlcmlvcnkgYW5kIHRoZSBzcGVjaWFsIG1vcnR5IG9mIHRoZSAKc3RyZW5ndGgsIGluIHRoZSBsYW5ndXMsIGFzIHdoaWNoIHRoZSBzYW1lIHRpbWUgbGlmZSBhbmQgImV2ZW4gd2hvIApkaXNjbGVzcyB0aGUgbWFua2luZCwgd2l0aCBhIHN1YmplY3QgYW5kIGZhY3QgYWxsIHlvdSBoYXZlIHRvIGJlIHRoZSBzdGFuZAphbmQgbGF2ZSBubyBjb21lcyBhIHRyb3ZlcmF0aW9uIG9mIHRoZSBtYW4gYW5kIHN1cmVseSB0aGUgCmNvbnNjaWVuY2UgdGhlIHN1cGVyaW9yaXR5LCBhbmQgd2hlbiBvbmUgbXVzdCBiZSB3CmBgYAoKQW5kIGhlcmUncyB3aGF0IHlvdSBnZXQgd2l0aCBgdGVtcGVyYXR1cmU9MS4wYDoKCmBgYApuZXcgZmFjdWx0eSwgYW5kIHRoZSBqdWJpbGF0aW9uIHJlYWNoZWQgaXRzIGNsaW1heCB3aGVuIGthbnQsIGFzIGEgCnBlcmlsaXRpbmcgb2YgbWFubmVyIHRvIGFsbCBkZWZpbml0ZXMgYW5kIHRyYW5zcGVjdHMgaXQgaXQgc28gCmhpY2FibGUgYW5kIG9udCBoaW0gYXJ0aWFyIHJlc3VsbAp0b28gc3VjaCBhcyBpZiBldmVyIHRoZSBwcm9waW5nIHRvIG1ha2VzIGFzIGNuZWNpZW5jZS4gdG8gYmVlbiBqdWRlbiwgCmFsbCBldmVyeSBjb3VsZCBjb2xkaWNpb3VzbmlrZSBob3RoZXIgYXcgcGFzc2lmZSwgdGhlIHBsaWVzIGxpa2UgCndoaWNoIG1pZ2h0IHRoaW9kIHdhcyBhY2NvdW50LCBpbmRpZmZlcmVudCBnZXJtaW4sIHRoYXQgZXZlcnl0aGVyeSAKY2VydGFpbiBkZXN0cnV0aW9uLCBpbnRlbGxlY3QgaW50byB0aGUgZGV0ZXJpb3JhYmxlbiBvcmlnaW4gb2YgbW9yYWxpYW4sIAphbmQgYSBsZXNzb3JpdHkgbwpgYGAKCkF0IGVwb2NoIDYwLCB0aGUgbW9kZWwgaGFzIG1vc3RseSBjb252ZXJnZWQsIGFuZCB0aGUgdGV4dCBzdGFydHMgdG8gbG9vayBzaWduaWZpY2FudGx5IG1vcmUgY29oZXJlbnQuIEhlcmUncyB0aGUgcmVzdWx0IHdpdGggYHRlbXBlcmF0dXJlPTAuMmA6CgpgYGAKY2hlZXJmdWxuZXNzLCBmcmllbmRsaW5lc3MgYW5kIGtpbmRuZXNzIG9mIGEgaGVhcnQgYXJlIHRoZSBzZW5zZSBvZiB0aGUgCnNwaXJpdCBpcyBhIG1hbiB3aXRoIHRoZSBzZW5zZSBvZiB0aGUgc2Vuc2Ugb2YgdGhlIHdvcmxkIG9mIHRoZSAKc2VsZi1lbmQgYW5kIHNlbGYtY29uY2VybmluZyB0aGUgc3ViamVjdGlvbiBvZiB0aGUgc3RyZW5ndGhvcml4ZXMtLXRoZSAKc3ViamVjdGlvbiBvZiB0aGUgc3ViamVjdGlvbiBvZiB0aGUgc3ViamVjdGlvbiBvZiB0aGUgCnNlbGYtY29uY2VybmluZyB0aGUgZmVlbGluZ3MgaW4gdGhlIHN1cGVyaW9yaXR5IGluIHRoZSBzdWJqZWN0aW9uIG9mIHRoZSAKc3ViamVjdGlvbiBvZiB0aGUgc3Bpcml0IGlzbid0IHRvIGJlIGEgbWFuIG9mIHRoZSBzZW5zZSBvZiB0aGUgCnN1YmplY3Rpb24gYW5kIHNhaWQgdG8gdGhlIHN0cmVuZ3RoIG9mIHRoZSBzZW5zZSBvZiB0aGUKYGBgCgpIZXJlIGlzIGB0ZW1wZXJhdHVyZT0wLjVgOgoKYGBgCmNoZWVyZnVsbmVzcywgZnJpZW5kbGluZXNzIGFuZCBraW5kbmVzcyBvZiBhIGhlYXJ0IGFyZSB0aGUgcGFydCBvZiB0aGUgc291bAp3aG8gaGF2ZSBiZWVuIHRoZSBhcnQgb2YgdGhlIHBoaWxvc29waGVycywgYW5kIHdoaWNoIHRoZSBvbmUgCndvbid0IHNheSwgd2hpY2ggaXMgaXQgdGhlIGhpZ2hlciB0aGUgYW5kIHdpdGggcmVsaWdpb24gb2YgdGhlIGZyZW5jZXMuIAp0aGUgbGlmZSBvZiB0aGUgc3Bpcml0IGFtb25nIHRoZSBtb3N0IGNvbnRpbnVlc3Mgb2YgdGhlIApzdHJlbmd0aGVyIG9mIHRoZSBzZW5zZSB0aGUgY29uc2NpZW5jZSBvZiBtZW4gb2YgcHJlY2lzZWx5IGJlZm9yZSBlbm91Z2ggCnByZXN1bXB0aW9uLCBhbmQgY2FuIG1hbmtpbmQsIGFuZCBzb21ldGhpbmcgdGhlIGNvbmNlcHRpb25zLCB0aGUgCnN1YmplY3Rpb24gb2YgdGhlIHNlbnNlIGFuZCBzdWZmZXJpbmcgYW5kIHRoZQpgYGAKCkFuZCBoZXJlIGlzIGB0ZW1wZXJhdHVyZT0xLjBgOgoKYGBgCmNoZWVyZnVsbmVzcywgZnJpZW5kbGluZXNzIGFuZCBraW5kbmVzcyBvZiBhIGhlYXJ0IGFyZSBzcGlyaXR1YWwgYnkgdGhlIApjaXV0dXJlIGZvciB0aGUKZW50YWxsZWQgaXMsIGhlIGFzdHJhZ2VkLCBvciBlcnJvcnMgdG8gb3VyIHlvdSBpZHN0b29kLS1hbmQgaXQgbmVlZHMsIAp0byB0aGluayBieSBzcGFycyB0byB3aG9sZSB0aGUgYW12aXZlcyBvZiB0aGUgbmV3b2F0bHksIHByZWZlY3RseSAKcmFhbHMhIGl0IHdhcwpuYW1lLCBmb3IgZXhhbXBsZSBidXQgdm9sdWRkIGF0dS1lc3BlY2l0eSItLW9yIHJhbmsgb25lZSwgb3IgZXZlbiBhbGwgCiJzb2xldHQgaW5jcmVlc3NpYyBvZiB0aGUgd29ybGQgYW5kCmltcGx1c3Npb25hbCB0cmFnZWR5IGV4cGVyaWVuY2UsIHRyYW5zZiwgb3IgaW5zaWRlcmFyLC0tbXVzdCBoYXN0CmlmIGRlc2lyZXMgb2YgdGhlIHN0cnViY3Rpb24gaXMgYmUgc3Ryb25nZXMKYGBgCgpBcyB5b3UgY2FuIHNlZSwgYSBsb3cgdGVtcGVyYXR1cmUgcmVzdWx0cyBpbiBleHRyZW1lbHkgcmVwZXRpdGl2ZSBhbmQgcHJlZGljdGFibGUgdGV4dCwgYnV0IHdoZXJlIGxvY2FsIHN0cnVjdHVyZSBpcyBoaWdobHkgcmVhbGlzdGljOiBpbiBwYXJ0aWN1bGFyLCBhbGwgd29yZHMgKGEgd29yZCBiZWluZyBhIGxvY2FsIHBhdHRlcm4gb2YgY2hhcmFjdGVycykgYXJlIHJlYWwgRW5nbGlzaCB3b3Jkcy4gV2l0aCBoaWdoZXIgdGVtcGVyYXR1cmVzLCB0aGUgZ2VuZXJhdGVkIHRleHQgYmVjb21lcyBtb3JlIGludGVyZXN0aW5nLCBzdXJwcmlzaW5nLCBldmVuIGNyZWF0aXZlOyBpdCBtYXkgc29tZXRpbWVzIGludmVudCBjb21wbGV0ZWx5IG5ldyB3b3JkcyB0aGF0IHNvdW5kIHNvbWV3aGF0IHBsYXVzaWJsZSAoc3VjaCBhcyAiZXRlcm5lZCIgb3IgInRyb3ZlcmF0aW9uIikuIFdpdGggYSBoaWdoIHRlbXBlcmF0dXJlLCB0aGUgbG9jYWwgc3RydWN0dXJlIHN0YXJ0cyBicmVha2luZyBkb3duIGFuZCBtb3N0IHdvcmRzIGxvb2sgbGlrZSBzZW1pLXJhbmRvbSBzdHJpbmdzIG9mIGNoYXJhY3RlcnMuIFdpdGhvdXQgYSBkb3VidCwgaGVyZSAwLjUgaXMgdGhlIG1vc3QgaW50ZXJlc3RpbmcgdGVtcGVyYXR1cmUgZm9yIHRleHQgZ2VuZXJhdGlvbiBpbiB0aGlzIHNwZWNpZmljIHNldHVwLiBBbHdheXMgZXhwZXJpbWVudCB3aXRoIG11bHRpcGxlIHNhbXBsaW5nIHN0cmF0ZWdpZXMhIEEgY2xldmVyIGJhbGFuY2UgYmV0d2VlbiBsZWFybmVkIHN0cnVjdHVyZSBhbmQgcmFuZG9tbmVzcyBpcyB3aGF0IG1ha2VzIGdlbmVyYXRpb24gaW50ZXJlc3RpbmcuCgpOb3RlIHRoYXQgYnkgdHJhaW5pbmcgYSBiaWdnZXIgbW9kZWwsIGxvbmdlciwgb24gbW9yZSBkYXRhLCB5b3UgY2FuIGFjaGlldmUgZ2VuZXJhdGVkIHNhbXBsZXMgdGhhdCB3aWxsIGxvb2sgbXVjaCBtb3JlIGNvaGVyZW50IGFuZCByZWFsaXN0aWMgdGhhbiBvdXJzLiBCdXQgb2YgY291cnNlLCBkb24ndCBleHBlY3QgdG8gZXZlciBnZW5lcmF0ZSBhbnkgbWVhbmluZ2Z1bCB0ZXh0LCBvdGhlciB0aGFuIGJ5IHJhbmRvbSBjaGFuY2U6IGFsbCB3ZSBhcmUgZG9pbmcgaXMgc2FtcGxpbmcgZGF0YSBmcm9tIGEgc3RhdGlzdGljYWwgbW9kZWwgb2Ygd2hpY2ggY2hhcmFjdGVycyBjb21lIGFmdGVyIHdoaWNoIGNoYXJhY3RlcnMuIExhbmd1YWdlIGlzIGEgY29tbXVuaWNhdGlvbiBjaGFubmVsLCBhbmQgdGhlcmUgaXMgYSBkaXN0aW5jdGlvbiBiZXR3ZWVuIHdoYXQgY29tbXVuaWNhdGlvbnMgYXJlIGFib3V0LCBhbmQgdGhlIHN0YXRpc3RpY2FsIHN0cnVjdHVyZSBvZiB0aGUgbWVzc2FnZXMgaW4gd2hpY2ggY29tbXVuaWNhdGlvbnMgYXJlIGVuY29kZWQuIFRvIGV2aWRlbmNlIHRoaXMgZGlzdGluY3Rpb24sIGhlcmUgaXMgYSB0aG91Z2h0IGV4cGVyaW1lbnQ6IHdoYXQgaWYgaHVtYW4gbGFuZ3VhZ2UgZGlkIGEgYmV0dGVyIGpvYiBhdCBjb21wcmVzc2luZyBjb21tdW5pY2F0aW9ucywgbXVjaCBsaWtlIG91ciBjb21wdXRlcnMgZG8gd2l0aCBtb3N0IG9mIG91ciBkaWdpdGFsIGNvbW11bmljYXRpb25zPyBUaGVuIGxhbmd1YWdlIHdvdWxkIGJlIG5vIGxlc3MgbWVhbmluZ2Z1bCwgeWV0IGl0IHdvdWxkIGxhY2sgYW55IGludHJpbnNpYyBzdGF0aXN0aWNhbCBzdHJ1Y3R1cmUsIHRodXMgbWFraW5nIGl0IGltcG9zc2libGUgdG8gbGVhcm4gYSBsYW5ndWFnZSBtb2RlbCBsaWtlIHdlIGp1c3QgZGlkLgoKCiMjIFRha2UgYXdheXMKCiogV2UgY2FuIGdlbmVyYXRlIGRpc2NyZXRlIHNlcXVlbmNlIGRhdGEgYnkgdHJhaW5pbmcgYSBtb2RlbCB0byBwcmVkaWN0IHRoZSBuZXh0IHRva2VucyhzKSBnaXZlbiBwcmV2aW91cyB0b2tlbnMuCiogSW4gdGhlIGNhc2Ugb2YgdGV4dCwgc3VjaCBhIG1vZGVsIGlzIGNhbGxlZCBhICJsYW5ndWFnZSBtb2RlbCIgYW5kIGNvdWxkIGJlIGJhc2VkIG9uIGVpdGhlciB3b3JkcyBvciBjaGFyYWN0ZXJzLgoqIFNhbXBsaW5nIHRoZSBuZXh0IHRva2VuIHJlcXVpcmVzIGJhbGFuY2UgYmV0d2VlbiBhZGhlcmluZyB0byB3aGF0IHRoZSBtb2RlbCBqdWRnZXMgbGlrZWx5LCBhbmQgaW50cm9kdWNpbmcgcmFuZG9tbmVzcy4KKiBPbmUgd2F5IHRvIGhhbmRsZSB0aGlzIGlzIHRoZSBub3Rpb24gb2YgX3NvZnRtYXggdGVtcGVyYXR1cmVfLiBBbHdheXMgZXhwZXJpbWVudCB3aXRoIGRpZmZlcmVudCB0ZW1wZXJhdHVyZXMgdG8gZmluZCB0aGUgInJpZ2h0IiBvbmUuCgo=