Think back to the last time that you opened your Email Inbox because you were looking for a specific email that you received last year. You know that the sender’s first name was ‘Jason’ and that the email in question revolved around the topic of SCADA data, but not much more than that. What’s more, there are 20,000 emails in your inbox, so it’s not like you can go through them one by one. What do you do? Most likely you would look for a search bar in the Email Application you are using and search for ‘From:Jason received:last year contents:SCADA’. With any luck, this will narrow down the number of emails that you need to search through to a far more reasonable number. This is an exceptionally powerful and useful feature, and it is worth paying attention to, because there are many cases that don’t provide such a nice pre-built search tool. Suppose, in a real example, that you have an CSV file with 20,000 rows that contains free-form text feedback in one of the columns, and you need to group each text response into one of five possible categories. What do you do?
- Fully read through each (sometimes multi-sentence) response and assign each to the correct category
- Skim through each response (i.e. first phrase or first sentence) and assign each to a given category
- Something else
When dealing with situations like this, it is important to acknowledge that reading through each and every response is really not a reasonable solution. Not only would this take an excruciatingly long amount of time, it will also likely be fraught with mistakes that you invariably will make as you grow tired, annoyed, and/or bored. You’re also highly likely to produce many mistakes by skimming (not to mention this would still take an exceptionally long amount of time to do). Instead, it is far more efficient to do something else; specifically, to filter the list of responses according to certain criteria that you could use to associate certain bodies of text to a given category (just like you filtered for a given Email in the previous example). This kind of filtering/manipulation can be easily accomplished using Regular Expressions.
So, what are Regular Expressions? Regular Expressions (often referred to as regex, or rational expressions) are specific character sequence patterns that define a search pattern that string-searching algorithms can understand. What’s more, most applications that implement some form of a search bar makes use of at least one flavor of Regular Expressions. They are also highly versatile, and can be used to filter, manipulate, and even extract specific pieces of information from larger bodies of text. Over the course of this document, we shall introduce the basic concepts behind Regular Expressions, and work through a number of test-cases showcasing how they work and how they can be applied in many different scenarios.
Basic Concepts
Regular Expressions can be used to specify/identify a certain set or pattern of characters for the purpose of filtering, manipulation, or extraction. This can be thought of as a set of Querying rules that can be used on a body of text, similar to how one can query a more structured/standard dataset using SQL, inequalities, and the like (e.g. filter out all records whose x-variable is less than 4). The (basic) building blocks for these string query-patterns are laid out below in the following table. It should be noted that what follows is not an exhaustive list; for more comprehensive details, see Regular-Expressions.info, though I should note the the full content spans more than 300 pages when collapsed to PDF (just a warning - it also covers the many different `flavors’ of Regular Expression syntax, a topic that I will not cover here, short of saying you can think of them as different dialects).
| Boolean ‘OR’ |
| |
Standard OR operation separating possible string patterns. |
‘cat|dog’ |
‘cat’, ‘dog’ |
| Grouping (Op Precedence) |
(…) |
Used to mark/group together and define the scope of certain operations (i.e. as in algebra) |
‘mea(n|t)s’ |
‘means’, ‘meats’ |
| Bracketed Inclusion |
[…] |
Single character match contained within the brackets. Allows the use of ‘-’ to specify ranges, like [0-9] or [a-z]. |
‘T[0-4]’ |
‘T0’, ‘T1’, ‘T2’, ‘T3’, ‘T4’ |
| Wildcard |
. |
The ‘.’ represents a wildcard that could match ANY character |
‘Test .A’ |
‘Test AA’, ‘Test 1A’, ‘Test aA’, … |
| Possible Existence |
? |
The ‘?’ indicates that the preceding element occurs zero or one time in the search pattern. |
‘colou?rs?’ |
‘color’, ‘colour’, ‘colors’, ‘colours’ |
| Arbitrary Repetition |
* |
The ’*’ indicates that the preceding element occurs zero or more times in the search pattern. |
’ab*c’ |
‘ac’, ‘abc’, ‘abbc’, ‘abbbc’, … |
| Mandatory Repetition |
+ |
The ‘+’ indicates that the preceding element occurs one or more times in the search pattern. |
‘4+’ |
‘4’, ‘44’, ‘444’, ‘4444’, … |
| Repetition Range |
{n,m} |
The {n,m} indicates that the preceding element occurs at least n times and at most m times in the search pattern. |
‘={4,6}’ |
‘====’, ‘=====’, ‘======’ |
| Backreference |
\n |
The ‘\n’ is replaced with the contents of the n-th marked subexpression (only valid for n between 0 and 9) |
([a-z]+) \1 |
Any text with a duplicated substring. |
String Pattern Filtering
strOptions <- c("1 cat", "2 dogs", "3 cats", "four horses")
# NOTE: The grep function is basically the 'string-search' function in R.
# It is called in the following way: grep(SearchPattern, Text) -> Matches
# We'll use it to filter out all the options without the string sequence 'cat'.
grep("cat", strOptions, value = TRUE)
## [1] "1 cat" "3 cats"
The standard approach to string literal filtering/comparison is arguably the simplest to understand; it simply searches through each string sequence and returns those that contain the provided sub-sequence. While this is useful, there are a lot of cases in which this doesn’t help much, due to there not being a single self-contained string like this to search for. For example, what if we were searching for any numeric integer in a body of text? For this, this standard approach doesn’t work. This is where the special characters and patterns of Regular Expressions (see table above) can really shine, since they don’t require knowledge of the exact string in question to function, but rather only need the pattern that the sequence of characters being looked for abides by. A few simple examples demonstrating this are shown below.
# Can use square brackets searching for inclusion among a set of values
grep("[0-9]", strOptions, value = TRUE)
## [1] "1 cat" "2 dogs" "3 cats"
# Can again use square brackets searching for inclusion among a smaller set of values
grep("[12]", strOptions, value = TRUE)
## [1] "1 cat" "2 dogs"
# Alternatively, we can use the OR operator for larger strings
grep("cat|horse", strOptions, value = TRUE)
## [1] "1 cat" "3 cats" "four horses"
Now, let’s consider a slightly more interesting case, where the text strings are longer and the filter we’re trying to use is more complex.
strOptions <- sentences[1:5]
## [1] "The birch canoe slid on the smooth planks."
## [2] "Glue the sheet to the dark blue background."
## [3] "It's easy to tell the depth of a well."
## [4] "These days a chicken leg is a rare dish."
## [5] "Rice is often served in round bowls."
Suppose that we want to keep only the sentences that contain at least one letter that is sequentially duplicated in the sentence (e.g. ‘ll’ or ‘oo’). The value of the duplicated character does not matter in this case, preventing us from searching for an exact match. Thus, we need to make use of the wildcard (because the exact character does not matter) and a backreference (because we want that specific previous value to occur twice).
# Filter for sentences that contain a sequentially duplicated character.
grep("(.)\\1", strOptions, value = TRUE)
## [1] "The birch canoe slid on the smooth planks."
## [2] "Glue the sheet to the dark blue background."
## [3] "It's easy to tell the depth of a well."
String Pattern Manipulation
Beyond basic filtering approaches, we can also use Regular Expressions to manipulate the contents of a set containing many bodies of text. This is identical to the ‘Find and Replace’ functionality that you likely have made use of in text editors (Word, Outlook, Notepad, etc.). However, by using the search/filter capabilities of Regular Expressions, manipulations and modifications can be made not only on the basis of exact string sequences, but also string patterns!
numStrs <- c("1234568", "12", "1234", "98765432")
# NOTE: The gsub function is the 'string-search-and-replace' function in R.
# It works like so: gsub(SearchPattern, ReplacementPattern, Text) -> ModifiedText
# Format String Representations of large integers
stri_reverse(gsub("([0-9]{3})", "\\1,", stri_reverse(numStrs)))
## [1] "1,234,568" "12" "1,234" "98,765,432"
# Remove nonsense string found within two tags (e.g. like in HTML or XML data files)
smpErrTag <- "<tag id='ID123' style='margin-right:0px' class='entry'>lkkjfasddslkj</tag>"
gsub("(<tag id='ID123' .*>).*</tag>", "\\1Corrected Tag Input</tag>", smpErrTag)
## [1] "<tag id='ID123' style='margin-right:0px' class='entry'>Corrected Tag Input</tag>"
Two additional special characters that will prove to be particularly useful are the ^ (caret) and the \b symbols. When placed inside square brackets, the ^ is interpreted as NOT, while the \b defines what is known as a ‘word boundary’. Word boundaries are effective whenever it is necessary to delineate the edges of a given word from the spaces surrounding it (something that arises all the time). An example of these word boundaries in action is shown below.
# Remove all words with 3 or fewer characters
gsub("\\b[a-zA-Z]{1,3}\\b ?", "", sentences[1:2])
## [1] "birch canoe slid smooth planks." "Glue sheet dark blue background."
Notice that this removed all of the extraneous prepositions and definite/indefinite articles from the two sentences. If we were interested in identifying the topic of a body of text or whether the general contents of one body of text are similar to others, then removing the parts that are unnecessary for the comparison or calculation (like definite/indefinite articles and prepositions) is usually a very effective strategy when it comes to improving accuracy (of a Machine Learning Model). Thus, there are certain cases where such an odd data preparation method (i.e. removing all words with 3 or fewer characters) could actually be warranted. That is not to say that this blunt approach using Regular Expressions is the only way to do this, or even the best (as it plainly isn’t); despite this, it is by far the quickest and most simple.
Conclusion
In conclusion, Regular Expressions are a powerful tool when dealing with large bodies of text, whether you are an analyst trying to clean up data being fed into a Machine Learning Model, a student looking for a particular passage/example in an electronic textbook/PDF/EBook, or just a computer-savvy individual searching for certain text-patterns in a set of emails or a particularly large Microsoft Word document. Arguably their greatest strength over alternative techniques is their simple construction (no coding experience required) and the fact that nearly every search bar to the most popular computer tools and applications around are able to use and interpret Regular Expressions (though the ‘flavors’ that each app uses may vary). So the next time you pull up Ctrl-F on a Word Document, consider using Regular Expressions to make your next ‘find’ or ‘find-and-replace’ all the more exact and precise!
## R Session Information:
## R version 3.5.1 (2018-07-02)
## Platform: x86_64-w64-mingw32/x64 (64-bit)
## Running under: Windows 10 x64 (build 19041)
##
## Matrix products: default
##
## locale:
## [1] LC_COLLATE=English_United States.1252
## [2] LC_CTYPE=English_United States.1252
## [3] LC_MONETARY=English_United States.1252
## [4] LC_NUMERIC=C
## [5] LC_TIME=English_United States.1252
##
## attached base packages:
## [1] stats graphics grDevices utils datasets methods base
##
## other attached packages:
## [1] readxl_1.3.1 dplyr_0.8.5 plyr_1.8.4 kableExtra_1.3.1
## [5] knitr_1.20 stringi_1.1.7 stringr_1.3.1
##
## loaded via a namespace (and not attached):
## [1] Rcpp_1.0.4.6 highr_0.7 cellranger_1.1.0 compiler_3.5.1
## [5] pillar_1.4.4 rmdformats_1.0.0 base64enc_0.1-3 tools_3.5.1
## [9] digest_0.6.15 jsonlite_1.6 evaluate_0.14 tibble_3.0.1
## [13] lifecycle_0.2.0 viridisLite_0.3.0 pkgconfig_2.0.2 rlang_0.4.5
## [17] rstudioapi_0.11 yaml_2.2.0 xfun_0.13 httr_1.4.1
## [21] xml2_1.3.2 vctrs_0.2.4 rprojroot_1.3-2 webshot_0.5.2
## [25] tidyselect_1.0.0 glue_1.4.0 R6_2.2.2 rmarkdown_1.10
## [29] bookdown_0.21 purrr_0.3.4 magrittr_1.5 backports_1.1.2
## [33] scales_1.0.0 htmltools_0.3.6 ellipsis_0.3.0 assertthat_0.2.0
## [37] rvest_0.3.6 colorspace_1.3-2 munsell_0.5.0 crayon_1.3.4
LS0tDQp0aXRsZTogIlJlZ3VsYXIgRXhwcmVzc2lvbnMiDQphdXRob3I6ICJNaWNoYWVsIE8nQ29ubm9yIg0KZGF0ZTogImByIGZvcm1hdChTeXMuRGF0ZSgpLCAnJUIgJWQsICVZJylgIg0Kb3V0cHV0OiANCiAgcm1kZm9ybWF0czo6cmVhZHRoZWRvd246DQogICAgY29kZV9kb3dubG9hZDogeWVzDQogICAgZGZfcHJpbnQ6IHBhZ2VkDQogICAgaGlnaGxpZ2h0OiBoYWRkb2NrDQogICAgdGh1bWJuYWlsczogZmFsc2UNCiAgICBsaWdodGJveDogZmFsc2UNCiAgcGRmX2RvY3VtZW50Og0KICAgIGxhdGV4X2VuZ2luZTogeGVsYXRleA0KZ2VvbWV0cnk6IG1hcmdpbj0xaW4NCnVybGNvbG9yOiAnYmx1ZScNCg0KLS0tDQoNCmBgYHtyIHNldHVwLCBpbmNsdWRlPUZBTFNFfQ0Ka25pdHI6Om9wdHNfY2h1bmskc2V0KGVjaG8gPSBUUlVFLCBmaWcuaGVpZ2h0ID0gNCwgZmlnLndpZHRoID0gOCkNCmxpYnJhcnkoc3RyaW5ncikNCmxpYnJhcnkoc3RyaW5naSkNCmxpYnJhcnkoa25pdHIpDQpsaWJyYXJ5KGthYmxlRXh0cmEpDQpsaWJyYXJ5KHBseXIpDQpsaWJyYXJ5KGRwbHlyKQ0KbGlicmFyeShyZWFkeGwpDQpgYGANCg0KVGhpbmsgYmFjayB0byB0aGUgbGFzdCB0aW1lIHRoYXQgeW91IG9wZW5lZCB5b3VyIEVtYWlsIEluYm94IGJlY2F1c2UgeW91IHdlcmUgbG9va2luZyBmb3IgYSBzcGVjaWZpYyBlbWFpbCB0aGF0IHlvdSByZWNlaXZlZCBsYXN0IHllYXIuIFlvdSBrbm93IHRoYXQgdGhlIHNlbmRlcidzIGZpcnN0IG5hbWUgd2FzICdKYXNvbicgYW5kIHRoYXQgdGhlIGVtYWlsIGluIHF1ZXN0aW9uIHJldm9sdmVkIGFyb3VuZCB0aGUgdG9waWMgb2YgU0NBREEgZGF0YSwgYnV0IG5vdCBtdWNoIG1vcmUgdGhhbiB0aGF0LiBXaGF0J3MgbW9yZSwgdGhlcmUgYXJlIDIwLDAwMCBlbWFpbHMgaW4geW91ciBpbmJveCwgc28gaXQncyBub3QgbGlrZSB5b3UgY2FuIGdvIHRocm91Z2ggdGhlbSBvbmUgYnkgb25lLiBXaGF0IGRvIHlvdSBkbz8gTW9zdCBsaWtlbHkgeW91IHdvdWxkIGxvb2sgZm9yIGEgc2VhcmNoIGJhciBpbiB0aGUgRW1haWwgQXBwbGljYXRpb24geW91IGFyZSB1c2luZyBhbmQgc2VhcmNoIGZvciAnRnJvbTpKYXNvbiByZWNlaXZlZDpsYXN0IHllYXIgY29udGVudHM6U0NBREEnLiBXaXRoIGFueSBsdWNrLCB0aGlzIHdpbGwgbmFycm93IGRvd24gdGhlIG51bWJlciBvZiBlbWFpbHMgdGhhdCB5b3UgbmVlZCB0byBzZWFyY2ggdGhyb3VnaCB0byBhIGZhciBtb3JlIHJlYXNvbmFibGUgbnVtYmVyLiBUaGlzIGlzIGFuIGV4Y2VwdGlvbmFsbHkgcG93ZXJmdWwgYW5kIHVzZWZ1bCBmZWF0dXJlLCBhbmQgaXQgaXMgd29ydGggcGF5aW5nIGF0dGVudGlvbiB0bywgYmVjYXVzZSB0aGVyZSBhcmUgbWFueSBjYXNlcyB0aGF0IGRvbid0IHByb3ZpZGUgc3VjaCBhIG5pY2UgcHJlLWJ1aWx0IHNlYXJjaCB0b29sLiBTdXBwb3NlLCBpbiBhIHJlYWwgZXhhbXBsZSwgdGhhdCB5b3UgaGF2ZSBhbiBDU1YgZmlsZSB3aXRoIDIwLDAwMCByb3dzIHRoYXQgY29udGFpbnMgZnJlZS1mb3JtIHRleHQgZmVlZGJhY2sgaW4gb25lIG9mIHRoZSBjb2x1bW5zLCBhbmQgeW91IG5lZWQgdG8gZ3JvdXAgZWFjaCB0ZXh0IHJlc3BvbnNlIGludG8gb25lIG9mIGZpdmUgcG9zc2libGUgY2F0ZWdvcmllcy4gV2hhdCBkbyB5b3UgZG8/DQoNCjEuIEZ1bGx5IHJlYWQgdGhyb3VnaCBlYWNoIChzb21ldGltZXMgbXVsdGktc2VudGVuY2UpIHJlc3BvbnNlIGFuZCBhc3NpZ24gZWFjaCB0byB0aGUgY29ycmVjdCBjYXRlZ29yeQ0KMi4gU2tpbSB0aHJvdWdoIGVhY2ggcmVzcG9uc2UgKGkuZS4gZmlyc3QgcGhyYXNlIG9yIGZpcnN0IHNlbnRlbmNlKSBhbmQgYXNzaWduIGVhY2ggdG8gYSBnaXZlbiBjYXRlZ29yeSANCjMuIFNvbWV0aGluZyBlbHNlDQoNCldoZW4gZGVhbGluZyB3aXRoIHNpdHVhdGlvbnMgbGlrZSB0aGlzLCBpdCBpcyBpbXBvcnRhbnQgdG8gYWNrbm93bGVkZ2UgdGhhdCByZWFkaW5nIHRocm91Z2ggZWFjaCBhbmQgZXZlcnkgcmVzcG9uc2UgaXMgcmVhbGx5IG5vdCBhIHJlYXNvbmFibGUgc29sdXRpb24uIE5vdCBvbmx5IHdvdWxkIHRoaXMgdGFrZSBhbiBleGNydWNpYXRpbmdseSBsb25nIGFtb3VudCBvZiB0aW1lLCBpdCB3aWxsIGFsc28gbGlrZWx5IGJlIGZyYXVnaHQgd2l0aCBtaXN0YWtlcyB0aGF0IHlvdSBpbnZhcmlhYmx5IHdpbGwgbWFrZSBhcyB5b3UgZ3JvdyB0aXJlZCwgYW5ub3llZCwgYW5kL29yIGJvcmVkLiBZb3UncmUgYWxzbyBoaWdobHkgbGlrZWx5IHRvIHByb2R1Y2UgbWFueSBtaXN0YWtlcyBieSBza2ltbWluZyAobm90IHRvIG1lbnRpb24gdGhpcyB3b3VsZCBzdGlsbCB0YWtlIGFuIGV4Y2VwdGlvbmFsbHkgbG9uZyBhbW91bnQgb2YgdGltZSB0byBkbykuIEluc3RlYWQsIGl0IGlzIGZhciBtb3JlIGVmZmljaWVudCB0byBkbyBzb21ldGhpbmcgZWxzZTsgc3BlY2lmaWNhbGx5LCB0byBmaWx0ZXIgdGhlIGxpc3Qgb2YgcmVzcG9uc2VzIGFjY29yZGluZyB0byBjZXJ0YWluIGNyaXRlcmlhIHRoYXQgeW91IGNvdWxkIHVzZSB0byBhc3NvY2lhdGUgY2VydGFpbiBib2RpZXMgb2YgdGV4dCB0byBhIGdpdmVuIGNhdGVnb3J5IChqdXN0IGxpa2UgeW91IGZpbHRlcmVkIGZvciBhIGdpdmVuIEVtYWlsIGluIHRoZSBwcmV2aW91cyBleGFtcGxlKS4gVGhpcyBraW5kIG9mIGZpbHRlcmluZy9tYW5pcHVsYXRpb24gY2FuIGJlIGVhc2lseSBhY2NvbXBsaXNoZWQgdXNpbmcgKipSZWd1bGFyIEV4cHJlc3Npb25zKiouIA0KDQoNClNvLCB3aGF0IGFyZSAqKlJlZ3VsYXIgRXhwcmVzc2lvbnMqKj8gUmVndWxhciBFeHByZXNzaW9ucyAob2Z0ZW4gcmVmZXJyZWQgdG8gYXMgcmVnZXgsIG9yIHJhdGlvbmFsIGV4cHJlc3Npb25zKSBhcmUgc3BlY2lmaWMgY2hhcmFjdGVyIHNlcXVlbmNlIHBhdHRlcm5zIHRoYXQgZGVmaW5lIGEgc2VhcmNoIHBhdHRlcm4gdGhhdCBzdHJpbmctc2VhcmNoaW5nIGFsZ29yaXRobXMgY2FuIHVuZGVyc3RhbmQuIFdoYXQncyBtb3JlLCBtb3N0IGFwcGxpY2F0aW9ucyB0aGF0IGltcGxlbWVudCBzb21lIGZvcm0gb2YgYSBzZWFyY2ggYmFyIG1ha2VzIHVzZSBvZiBhdCBsZWFzdCBvbmUgZmxhdm9yIG9mIFJlZ3VsYXIgRXhwcmVzc2lvbnMuIFRoZXkgYXJlIGFsc28gaGlnaGx5IHZlcnNhdGlsZSwgYW5kIGNhbiBiZSB1c2VkIHRvIGZpbHRlciwgbWFuaXB1bGF0ZSwgYW5kIGV2ZW4gZXh0cmFjdCBzcGVjaWZpYyBwaWVjZXMgb2YgaW5mb3JtYXRpb24gZnJvbSBsYXJnZXIgYm9kaWVzIG9mIHRleHQuIE92ZXIgdGhlIGNvdXJzZSBvZiB0aGlzIGRvY3VtZW50LCB3ZSBzaGFsbCBpbnRyb2R1Y2UgdGhlIGJhc2ljIGNvbmNlcHRzIGJlaGluZCBSZWd1bGFyIEV4cHJlc3Npb25zLCBhbmQgd29yayB0aHJvdWdoIGEgbnVtYmVyIG9mIHRlc3QtY2FzZXMgc2hvd2Nhc2luZyBob3cgdGhleSB3b3JrIGFuZCBob3cgdGhleSBjYW4gYmUgYXBwbGllZCBpbiBtYW55IGRpZmZlcmVudCBzY2VuYXJpb3MuDQoNCiMjIEJhc2ljIENvbmNlcHRzDQoNClJlZ3VsYXIgRXhwcmVzc2lvbnMgY2FuIGJlIHVzZWQgdG8gc3BlY2lmeS9pZGVudGlmeSBhIGNlcnRhaW4gc2V0IG9yIHBhdHRlcm4gb2YgY2hhcmFjdGVycyBmb3IgdGhlIHB1cnBvc2Ugb2YgZmlsdGVyaW5nLCBtYW5pcHVsYXRpb24sIG9yIGV4dHJhY3Rpb24uIFRoaXMgY2FuIGJlIHRob3VnaHQgb2YgYXMgYSBzZXQgb2YgUXVlcnlpbmcgcnVsZXMgdGhhdCBjYW4gYmUgdXNlZCBvbiBhIGJvZHkgb2YgdGV4dCwgc2ltaWxhciB0byBob3cgb25lIGNhbiBxdWVyeSBhIG1vcmUgc3RydWN0dXJlZC9zdGFuZGFyZCBkYXRhc2V0IHVzaW5nIFNRTCwgaW5lcXVhbGl0aWVzLCBhbmQgdGhlIGxpa2UgKGUuZy4gZmlsdGVyIG91dCBhbGwgcmVjb3JkcyB3aG9zZSB4LXZhcmlhYmxlIGlzIGxlc3MgdGhhbiA0KS4gVGhlIChiYXNpYykgYnVpbGRpbmcgYmxvY2tzIGZvciB0aGVzZSBzdHJpbmcgcXVlcnktcGF0dGVybnMgYXJlIGxhaWQgb3V0IGJlbG93IGluIHRoZSBmb2xsb3dpbmcgdGFibGUuIEl0IHNob3VsZCBiZSBub3RlZCB0aGF0IHdoYXQgZm9sbG93cyBpcyBub3QgYW4gZXhoYXVzdGl2ZSBsaXN0OyBmb3IgbW9yZSBjb21wcmVoZW5zaXZlIGRldGFpbHMsIHNlZSBbUmVndWxhci1FeHByZXNzaW9ucy5pbmZvXShodHRwczovL3d3dy5yZWd1bGFyLWV4cHJlc3Npb25zLmluZm8vKSwgdGhvdWdoIEkgc2hvdWxkIG5vdGUgdGhlIHRoZSBmdWxsIGNvbnRlbnQgc3BhbnMgbW9yZSB0aGFuIDMwMCBwYWdlcyB3aGVuIGNvbGxhcHNlZCB0byBQREYgKGp1c3QgYSB3YXJuaW5nIC0gaXQgYWxzbyBjb3ZlcnMgdGhlIG1hbnkgZGlmZmVyZW50IGBmbGF2b3JzJyBvZiBSZWd1bGFyIEV4cHJlc3Npb24gc3ludGF4LCBhIHRvcGljIHRoYXQgSSB3aWxsIG5vdCBjb3ZlciBoZXJlLCBzaG9ydCBvZiBzYXlpbmcgeW91IGNhbiB0aGluayBvZiB0aGVtIGFzIGRpZmZlcmVudCBkaWFsZWN0cykuDQoNCg0KYGBge3IsIGVjaG89RkFMU0UsIHJlc3VsdHM9J2FzaXMnfQ0KcnVsZXMgPC0gZGF0YS5mcmFtZSgNCiAgT3BlcmF0aW9uID0gYygiQm9vbGVhbiAnT1InIiwgIkdyb3VwaW5nIChPcCBQcmVjZWRlbmNlKSIsICJCcmFja2V0ZWQgSW5jbHVzaW9uIiwgIldpbGRjYXJkIiwgIlBvc3NpYmxlIEV4aXN0ZW5jZSIsICJBcmJpdHJhcnkgUmVwZXRpdGlvbiIsICJNYW5kYXRvcnkgUmVwZXRpdGlvbiIsICJSZXBldGl0aW9uIFJhbmdlIiwgIkJhY2tyZWZlcmVuY2UiKSwNCiAgYFBhdHRlcm5gID0gYygifCIsICIoLi4uKSIsICJbLi4uXSIsICIuIiwgIj8iLCAiKiIsICIrIiwgIntuLG19IiwgIlxcXFxuIiksDQogIE1lYW5pbmcgPSBjKCJTdGFuZGFyZCBPUiBvcGVyYXRpb24gc2VwYXJhdGluZyBwb3NzaWJsZSBzdHJpbmcgcGF0dGVybnMuIiwgIlVzZWQgdG8gbWFyay9ncm91cCB0b2dldGhlciBhbmQgZGVmaW5lIHRoZSBzY29wZSBvZiBjZXJ0YWluIG9wZXJhdGlvbnMgKGkuZS4gYXMgaW4gYWxnZWJyYSkiLCAiU2luZ2xlIGNoYXJhY3RlciBtYXRjaCBjb250YWluZWQgd2l0aGluIHRoZSBicmFja2V0cy4gQWxsb3dzIHRoZSB1c2Ugb2YgJy0nIHRvIHNwZWNpZnkgcmFuZ2VzLCBsaWtlIFswLTldIG9yIFthLXpdLiIsICJUaGUgJy4nIHJlcHJlc2VudHMgYSB3aWxkY2FyZCB0aGF0IGNvdWxkIG1hdGNoIEFOWSBjaGFyYWN0ZXIiLCAiVGhlICc/JyBpbmRpY2F0ZXMgdGhhdCB0aGUgcHJlY2VkaW5nIGVsZW1lbnQgb2NjdXJzIHplcm8gb3Igb25lIHRpbWUgaW4gdGhlIHNlYXJjaCBwYXR0ZXJuLiIsICJUaGUgJyonIGluZGljYXRlcyB0aGF0IHRoZSBwcmVjZWRpbmcgZWxlbWVudCBvY2N1cnMgemVybyBvciBtb3JlIHRpbWVzIGluIHRoZSBzZWFyY2ggcGF0dGVybi4iLCAiVGhlICcrJyBpbmRpY2F0ZXMgdGhhdCB0aGUgcHJlY2VkaW5nIGVsZW1lbnQgb2NjdXJzIG9uZSBvciBtb3JlIHRpbWVzIGluIHRoZSBzZWFyY2ggcGF0dGVybi4iLCAiVGhlIHtuLG19IGluZGljYXRlcyB0aGF0IHRoZSBwcmVjZWRpbmcgZWxlbWVudCBvY2N1cnMgYXQgbGVhc3QgbiB0aW1lcyBhbmQgYXQgbW9zdCBtIHRpbWVzIGluIHRoZSBzZWFyY2ggcGF0dGVybi4iLCAiVGhlICdcXFxcbicgaXMgcmVwbGFjZWQgd2l0aCB0aGUgY29udGVudHMgb2YgdGhlIG4tdGggbWFya2VkIHN1YmV4cHJlc3Npb24gKG9ubHkgdmFsaWQgZm9yIG4gYmV0d2VlbiAwIGFuZCA5KSIpLA0KICBFeGFtcGxlID0gYygiJ2NhdHxkb2cnIiwgIidtZWEobnx0KXMnIiwgIidUWzAtNF0nIiwgIidUZXN0IC5BJyIsICInY29sb3U/cnM/JyIsICInYWIqYyciLCAiJzQrJyIsICInPXs0LDZ9JyIsICIoW2Etel0rKSBcXFxcMSIpLA0KICBgUmV0dXJucy9NYXRjaGVzYCA9IGMoIidjYXQnLCAnZG9nJyIsICInbWVhbnMnLCAnbWVhdHMnIiwgIidUMCcsICdUMScsICdUMicsICdUMycsICdUNCciLCAiJ1Rlc3QgQUEnLCAnVGVzdCAxQScsICdUZXN0IGFBJywgLi4uIiwgIidjb2xvcicsICdjb2xvdXInLCAnY29sb3JzJywgJ2NvbG91cnMnIiwgIidhYycsICdhYmMnLCAnYWJiYycsICdhYmJiYycsIC4uLiIsICInNCcsICc0NCcsICc0NDQnLCAnNDQ0NCcsIC4uLiIsICInPT09PScsICc9PT09PScsICc9PT09PT0nIiwgIkFueSB0ZXh0IHdpdGggYSBkdXBsaWNhdGVkIHN1YnN0cmluZy4iKSwNCiAgY2hlY2submFtZXMgPSBGQUxTRQ0KKQ0Ka2FibGUocnVsZXMsIGZvcm1hdCA9ICJtYXJrZG93biIsIGFsaWduID0gImxjbGxyIiwgZXNjYXBlID0gVFJVRSkNCmBgYA0KDQoNCg0KDQojIyBTdHJpbmcgUGF0dGVybiBGaWx0ZXJpbmcNCg0KDQoNCg0KYGBge3J9DQpzdHJPcHRpb25zIDwtIGMoIjEgY2F0IiwgIjIgZG9ncyIsICIzIGNhdHMiLCAiZm91ciBob3JzZXMiKQ0KIyBOT1RFOiBUaGUgZ3JlcCBmdW5jdGlvbiBpcyBiYXNpY2FsbHkgdGhlICdzdHJpbmctc2VhcmNoJyBmdW5jdGlvbiBpbiBSLiANCiMgSXQgaXMgY2FsbGVkIGluIHRoZSBmb2xsb3dpbmcgd2F5OiBncmVwKFNlYXJjaFBhdHRlcm4sIFRleHQpIC0+IE1hdGNoZXMNCiMgV2UnbGwgdXNlIGl0IHRvIGZpbHRlciBvdXQgYWxsIHRoZSBvcHRpb25zIHdpdGhvdXQgdGhlIHN0cmluZyBzZXF1ZW5jZSAnY2F0Jy4NCmdyZXAoImNhdCIsIHN0ck9wdGlvbnMsIHZhbHVlID0gVFJVRSkNCmBgYA0KDQpUaGUgc3RhbmRhcmQgYXBwcm9hY2ggdG8gc3RyaW5nIGxpdGVyYWwgZmlsdGVyaW5nL2NvbXBhcmlzb24gaXMgYXJndWFibHkgdGhlIHNpbXBsZXN0IHRvIHVuZGVyc3RhbmQ7IGl0IHNpbXBseSBzZWFyY2hlcyB0aHJvdWdoIGVhY2ggc3RyaW5nIHNlcXVlbmNlIGFuZCByZXR1cm5zIHRob3NlIHRoYXQgY29udGFpbiB0aGUgcHJvdmlkZWQgc3ViLXNlcXVlbmNlLiBXaGlsZSB0aGlzIGlzIHVzZWZ1bCwgdGhlcmUgYXJlIGEgbG90IG9mIGNhc2VzIGluIHdoaWNoIHRoaXMgZG9lc24ndCBoZWxwIG11Y2gsIGR1ZSB0byB0aGVyZSBub3QgYmVpbmcgYSBzaW5nbGUgc2VsZi1jb250YWluZWQgc3RyaW5nIGxpa2UgdGhpcyB0byBzZWFyY2ggZm9yLiBGb3IgZXhhbXBsZSwgd2hhdCBpZiB3ZSB3ZXJlIHNlYXJjaGluZyBmb3IgYW55IG51bWVyaWMgaW50ZWdlciBpbiBhIGJvZHkgb2YgdGV4dD8gRm9yIHRoaXMsIHRoaXMgc3RhbmRhcmQgYXBwcm9hY2ggZG9lc24ndCB3b3JrLiBUaGlzIGlzIHdoZXJlIHRoZSBzcGVjaWFsIGNoYXJhY3RlcnMgYW5kIHBhdHRlcm5zIG9mIFJlZ3VsYXIgRXhwcmVzc2lvbnMgKHNlZSB0YWJsZSBhYm92ZSkgY2FuIHJlYWxseSBzaGluZSwgc2luY2UgdGhleSBkb24ndCByZXF1aXJlIGtub3dsZWRnZSBvZiB0aGUgZXhhY3Qgc3RyaW5nIGluIHF1ZXN0aW9uIHRvIGZ1bmN0aW9uLCBidXQgcmF0aGVyIG9ubHkgbmVlZCB0aGUgcGF0dGVybiB0aGF0IHRoZSBzZXF1ZW5jZSBvZiBjaGFyYWN0ZXJzIGJlaW5nIGxvb2tlZCBmb3IgYWJpZGVzIGJ5LiBBIGZldyBzaW1wbGUgZXhhbXBsZXMgZGVtb25zdHJhdGluZyB0aGlzIGFyZSBzaG93biBiZWxvdy4gDQoNCmBgYHtyfQ0KIyBDYW4gdXNlIHNxdWFyZSBicmFja2V0cyBzZWFyY2hpbmcgZm9yIGluY2x1c2lvbiBhbW9uZyBhIHNldCBvZiB2YWx1ZXMNCmdyZXAoIlswLTldIiwgc3RyT3B0aW9ucywgdmFsdWUgPSBUUlVFKQ0KIyBDYW4gYWdhaW4gdXNlIHNxdWFyZSBicmFja2V0cyBzZWFyY2hpbmcgZm9yIGluY2x1c2lvbiBhbW9uZyBhIHNtYWxsZXIgc2V0IG9mIHZhbHVlcw0KZ3JlcCgiWzEyXSIsIHN0ck9wdGlvbnMsIHZhbHVlID0gVFJVRSkNCiMgQWx0ZXJuYXRpdmVseSwgd2UgY2FuIHVzZSB0aGUgT1Igb3BlcmF0b3IgZm9yIGxhcmdlciBzdHJpbmdzDQpncmVwKCJjYXR8aG9yc2UiLCBzdHJPcHRpb25zLCB2YWx1ZSA9IFRSVUUpDQpgYGANCg0KDQoNCk5vdywgbGV0J3MgY29uc2lkZXIgYSBzbGlnaHRseSBtb3JlIGludGVyZXN0aW5nIGNhc2UsIHdoZXJlIHRoZSB0ZXh0IHN0cmluZ3MgYXJlIGxvbmdlciBhbmQgdGhlIGZpbHRlciB3ZSdyZSB0cnlpbmcgdG8gdXNlIGlzIG1vcmUgY29tcGxleC4NCg0KDQoNCg0KYGBge3IsIGVjaG89MX0NCnN0ck9wdGlvbnMgPC0gc2VudGVuY2VzWzE6NV0NCnN0ck9wdGlvbnMNCmBgYA0KDQpTdXBwb3NlIHRoYXQgd2Ugd2FudCB0byBrZWVwIG9ubHkgdGhlIHNlbnRlbmNlcyB0aGF0IGNvbnRhaW4gYXQgbGVhc3Qgb25lIGxldHRlciB0aGF0IGlzIHNlcXVlbnRpYWxseSBkdXBsaWNhdGVkIGluIHRoZSBzZW50ZW5jZSAoZS5nLiAnbGwnIG9yICdvbycpLiBUaGUgdmFsdWUgb2YgdGhlIGR1cGxpY2F0ZWQgY2hhcmFjdGVyIGRvZXMgbm90IG1hdHRlciBpbiB0aGlzIGNhc2UsIHByZXZlbnRpbmcgdXMgZnJvbSBzZWFyY2hpbmcgZm9yIGFuIGV4YWN0IG1hdGNoLiBUaHVzLCB3ZSBuZWVkIHRvIG1ha2UgdXNlIG9mIHRoZSB3aWxkY2FyZCAoYmVjYXVzZSB0aGUgZXhhY3QgY2hhcmFjdGVyIGRvZXMgbm90IG1hdHRlcikgYW5kIGEgYmFja3JlZmVyZW5jZSAoYmVjYXVzZSB3ZSB3YW50IHRoYXQgc3BlY2lmaWMgcHJldmlvdXMgdmFsdWUgdG8gb2NjdXIgdHdpY2UpLiANCg0KYGBge3J9DQojIEZpbHRlciBmb3Igc2VudGVuY2VzIHRoYXQgY29udGFpbiBhIHNlcXVlbnRpYWxseSBkdXBsaWNhdGVkIGNoYXJhY3Rlci4NCmdyZXAoIiguKVxcMSIsIHN0ck9wdGlvbnMsIHZhbHVlID0gVFJVRSkNCmBgYA0KDQoNCg0KDQojIyBTdHJpbmcgUGF0dGVybiBNYW5pcHVsYXRpb24NCg0KDQpCZXlvbmQgYmFzaWMgZmlsdGVyaW5nIGFwcHJvYWNoZXMsIHdlIGNhbiBhbHNvIHVzZSBSZWd1bGFyIEV4cHJlc3Npb25zIHRvIG1hbmlwdWxhdGUgdGhlIGNvbnRlbnRzIG9mIGEgc2V0IGNvbnRhaW5pbmcgbWFueSBib2RpZXMgb2YgdGV4dC4gVGhpcyBpcyBpZGVudGljYWwgdG8gdGhlICdGaW5kIGFuZCBSZXBsYWNlJyBmdW5jdGlvbmFsaXR5IHRoYXQgeW91IGxpa2VseSBoYXZlIG1hZGUgdXNlIG9mIGluIHRleHQgZWRpdG9ycyAoV29yZCwgT3V0bG9vaywgTm90ZXBhZCwgZXRjLikuIEhvd2V2ZXIsIGJ5IHVzaW5nIHRoZSBzZWFyY2gvZmlsdGVyIGNhcGFiaWxpdGllcyBvZiBSZWd1bGFyIEV4cHJlc3Npb25zLCBtYW5pcHVsYXRpb25zIGFuZCBtb2RpZmljYXRpb25zIGNhbiBiZSBtYWRlIG5vdCBvbmx5IG9uIHRoZSBiYXNpcyBvZiBleGFjdCBzdHJpbmcgc2VxdWVuY2VzLCBidXQgYWxzbyBzdHJpbmcgcGF0dGVybnMhDQoNCmBgYHtyfQ0KbnVtU3RycyA8LSBjKCIxMjM0NTY4IiwgIjEyIiwgIjEyMzQiLCAiOTg3NjU0MzIiKQ0KIyBOT1RFOiBUaGUgZ3N1YiBmdW5jdGlvbiBpcyB0aGUgJ3N0cmluZy1zZWFyY2gtYW5kLXJlcGxhY2UnIGZ1bmN0aW9uIGluIFIuIA0KIyBJdCB3b3JrcyBsaWtlIHNvOiBnc3ViKFNlYXJjaFBhdHRlcm4sIFJlcGxhY2VtZW50UGF0dGVybiwgVGV4dCkgLT4gTW9kaWZpZWRUZXh0DQojIEZvcm1hdCBTdHJpbmcgUmVwcmVzZW50YXRpb25zIG9mIGxhcmdlIGludGVnZXJzIA0Kc3RyaV9yZXZlcnNlKGdzdWIoIihbMC05XXszfSkiLCAiXFwxLCIsIHN0cmlfcmV2ZXJzZShudW1TdHJzKSkpDQoNCiMgUmVtb3ZlIG5vbnNlbnNlIHN0cmluZyBmb3VuZCB3aXRoaW4gdHdvIHRhZ3MgKGUuZy4gbGlrZSBpbiBIVE1MIG9yIFhNTCBkYXRhIGZpbGVzKQ0Kc21wRXJyVGFnIDwtICI8dGFnIGlkPSdJRDEyMycgc3R5bGU9J21hcmdpbi1yaWdodDowcHgnIGNsYXNzPSdlbnRyeSc+bGtramZhc2Rkc2xrajwvdGFnPiINCmdzdWIoIig8dGFnIGlkPSdJRDEyMycgLio+KS4qPC90YWc+IiwgIlxcMUNvcnJlY3RlZCBUYWcgSW5wdXQ8L3RhZz4iLCBzbXBFcnJUYWcpDQpgYGANCg0KVHdvIGFkZGl0aW9uYWwgc3BlY2lhbCBjaGFyYWN0ZXJzIHRoYXQgd2lsbCBwcm92ZSB0byBiZSBwYXJ0aWN1bGFybHkgdXNlZnVsIGFyZSB0aGUgXiAoY2FyZXQpIGFuZCB0aGUgXFxiIHN5bWJvbHMuIFdoZW4gcGxhY2VkIGluc2lkZSBzcXVhcmUgYnJhY2tldHMsIHRoZSBeIGlzIGludGVycHJldGVkIGFzIE5PVCwgd2hpbGUgdGhlIFxcYiBkZWZpbmVzIHdoYXQgaXMga25vd24gYXMgYSAnd29yZCBib3VuZGFyeScuIFdvcmQgYm91bmRhcmllcyBhcmUgZWZmZWN0aXZlIHdoZW5ldmVyIGl0IGlzIG5lY2Vzc2FyeSB0byBkZWxpbmVhdGUgdGhlIGVkZ2VzIG9mIGEgZ2l2ZW4gd29yZCBmcm9tIHRoZSBzcGFjZXMgc3Vycm91bmRpbmcgaXQgKHNvbWV0aGluZyB0aGF0IGFyaXNlcyBhbGwgdGhlIHRpbWUpLiBBbiBleGFtcGxlIG9mIHRoZXNlIHdvcmQgYm91bmRhcmllcyBpbiBhY3Rpb24gaXMgc2hvd24gYmVsb3cuDQoNCg0KDQpgYGB7cn0NCiMgUmVtb3ZlIGFsbCB3b3JkcyB3aXRoIDMgb3IgZmV3ZXIgY2hhcmFjdGVycw0KZ3N1YigiXFxiW2EtekEtWl17MSwzfVxcYiA/IiwgIiIsIHNlbnRlbmNlc1sxOjJdKQ0KYGBgDQoNCk5vdGljZSB0aGF0IHRoaXMgcmVtb3ZlZCBhbGwgb2YgdGhlIGV4dHJhbmVvdXMgcHJlcG9zaXRpb25zIGFuZCBkZWZpbml0ZS9pbmRlZmluaXRlIGFydGljbGVzIGZyb20gdGhlIHR3byBzZW50ZW5jZXMuIElmIHdlIHdlcmUgaW50ZXJlc3RlZCBpbiBpZGVudGlmeWluZyB0aGUgdG9waWMgb2YgYSBib2R5IG9mIHRleHQgb3Igd2hldGhlciB0aGUgZ2VuZXJhbCBjb250ZW50cyBvZiBvbmUgYm9keSBvZiB0ZXh0IGFyZSBzaW1pbGFyIHRvIG90aGVycywgdGhlbiByZW1vdmluZyB0aGUgcGFydHMgdGhhdCBhcmUgdW5uZWNlc3NhcnkgZm9yIHRoZSBjb21wYXJpc29uIG9yIGNhbGN1bGF0aW9uIChsaWtlIGRlZmluaXRlL2luZGVmaW5pdGUgYXJ0aWNsZXMgYW5kIHByZXBvc2l0aW9ucykgaXMgdXN1YWxseSBhIHZlcnkgZWZmZWN0aXZlIHN0cmF0ZWd5IHdoZW4gaXQgY29tZXMgdG8gaW1wcm92aW5nIGFjY3VyYWN5IChvZiBhIE1hY2hpbmUgTGVhcm5pbmcgTW9kZWwpLiBUaHVzLCB0aGVyZSBhcmUgY2VydGFpbiBjYXNlcyB3aGVyZSBzdWNoIGFuIG9kZCBkYXRhIHByZXBhcmF0aW9uIG1ldGhvZCAoaS5lLiByZW1vdmluZyBhbGwgd29yZHMgd2l0aCAzIG9yIGZld2VyIGNoYXJhY3RlcnMpIGNvdWxkIGFjdHVhbGx5IGJlIHdhcnJhbnRlZC4gVGhhdCBpcyBub3QgdG8gc2F5IHRoYXQgdGhpcyBibHVudCBhcHByb2FjaCB1c2luZyBSZWd1bGFyIEV4cHJlc3Npb25zIGlzIHRoZSBvbmx5IHdheSB0byBkbyB0aGlzLCBvciBldmVuIHRoZSBiZXN0IChhcyBpdCBwbGFpbmx5IGlzbid0KTsgZGVzcGl0ZSB0aGlzLCBpdCBpcyBieSBmYXIgdGhlIHF1aWNrZXN0IGFuZCBtb3N0IHNpbXBsZS4gDQoNCg0KDQoNCg0KDQoNCiMjIFN0cmluZyBQYXR0ZXJuIEV4dHJhY3Rpb24NCg0KQXJndWFibHkgdGhlIG1vc3QgcG93ZXJmdWwgYXNwZWN0IG9mIFJlZ3VsYXIgRXhwcmVzc2lvbnMgaXMgaG93IGVmZmVjdGl2ZWx5IHRoZXkgY2FuIGJlIHVzZWQgdG8gZXh0cmFjdCBjZXJ0YWluIGtleSBwaWVjZXMgb2YgaW5mb3JtYXRpb24gZnJvbSBhIGxhcmdlciBib2R5IG9mIHRleHQsIG9yIGEgbGFyZ2Ugc2V0IG9mIGJvZGllcyBvZiB0ZXh0LiBCb3RoIG9mIHRoZXNlIGFwcGxpY2F0aW9ucyBhcmUgcGFydGljdWxhcmx5IHJlbGV2YW50IGZvciBhbGwgc29ydHMgb2YgdGhpbmdzIGluIHRoZSBjb250ZXh0IG9mIERhdGEgU2NpZW5jZSwgcmFuZ2luZyBmcm9tIEZlYXR1cmUgRW5naW5lZXJpbmcgYW5kIE1hY2hpbmUgTGVhcm5pbmcgdG8gc2ltcGxlIERhdGEgQ3VyYXRpb24uIA0KDQoNCkFzIGEgc2ltcGxlIGV4YW1wbGUsIGNvbnNpZGVyIGEgc2VyaWVzIG9mIHNlbnRlbmNlcyBzdG9yZWQgaW4gc29tZSBmb3JtIHRoYXQgY29udGFpbiBudW1lcmljYWwgdmFsdWVzIG9mIHNvbWV0aGluZyB0aGF0IHlvdSByZWFsbHkgbmVlZCBmb3Igc29tZSBhcmJpdHJhcnkgcmVhc29uLiBJdCBtaWdodCBiZSByZWFzb25hYmxlIHRvIHNpbXBseSByZWFkIHRocm91Z2ggdGhvc2Ugc2VudGVuY2VzIGlmIHRoZXJlIGFyZW4ndCB0aGF0IG1hbnkgb2YgdGhlbSAobGlrZSAxMCksIGJ1dCB3aGF0IGRvIHlvdSBkbyBpZiB0aGVyZSBhcmUgMTAwLDAwMD8gV2VsbCwgd2l0aCBSZWd1bGFyIEV4cHJlc3Npb25zLCB0aGF0IGlzbid0IGEgcHJvYmxlbSEgDQoNCg0KYGBge3IsIGVjaG89RkFMU0V9DQpudW1iZXJzIDwtIHN0cnNwbGl0KCJvbmV8dHdvfHRocmVlfGZvdXJ8Zml2ZXxzaXh8c2V2ZW58ZWlnaHR8bmluZXx0ZW4iLCBzcGxpdCA9ICJ8IiwgZml4ZWQgPSBUUlVFKVtbMV1dDQpzbnRzIDwtIGdyZXAocGFzdGUwKCJcXGIiLCBwYXN0ZTAobnVtYmVycywgY29sbGFwc2UgPSAiXFxifFxcYiIpLCAiXFxiIiksIHNlbnRlbmNlcywgdmFsdWUgPSBUUlVFKQ0Kc250czEgPC0gdW5saXN0KEZpbHRlcihsZW5ndGgsIGxhcHBseShzbnRzLCBmdW5jdGlvbihhKSB7DQogIGZvciAoaSBpbiAxOmxlbmd0aChudW1iZXJzKSkgew0KICAgIGlmIChncmVwbChudW1iZXJzW2ldLCBhKSkgew0KICAgICAgdHBocmFzZSA8LSBzdHJfZXh0cmFjdF9hbGwoYSwgc3ByaW50ZigiJXMgW2Etel0rIiwgbnVtYmVyc1tpXSkpW1sxXV0NCiAgICAgIGlmIChsZW5ndGgodHBocmFzZSkgPT0gMCkgcmV0dXJuIChjKCkpDQogICAgICBpZiAoc3RyX2xlbmd0aChzdHJzcGxpdCh0cGhyYXNlLCAiICIpW1sxXV1bMl0pIDwgMykgcmV0dXJuKGMoKSkNCiAgICAgIGlmIChzdHJzcGxpdCh0cGhyYXNlLCAiICIpW1sxXV1bMl0gJWluJSBjKCJkaXN0aW5jdCIsICJtZXQiLCAiY29tZXMiLCAidGhhbiIsICJ3aGVuIiwgImtpbmRzIiwgImJhdGNoZXMiLCAiY29zdHMiKSkgcmV0dXJuKGMoKSkNCiAgICAgICNwcmludCh0cGhyYXNlKQ0KICAgIH0NCiAgICBhIDwtIGdzdWIocGFzdGUwKCJcXGIiLCBudW1iZXJzW2ldLCAiXFxiIiksIGksIGEpDQogIH0NCiAgYQ0KfSkpKQ0KZXhtcGwgPC0gc250czFbMToxMF0NCmBgYA0KDQpgYGB7cn0NCiMgRXh0cmFjdCB0aGUgbnVtZXJpY2FsIHZhbHVlcyBhbmQgdGhlIG9iamVjdHMgdGhleSByZWZlciB0byBmcm9tIGEgbnVtYmVyIG9mIHNlbnRlbmNlcw0KdGliYmxlKGRhdGEuZnJhbWUoU2VudGVuY2UgPSBleG1wbCwgRXh0cmFjdCA9IHN0cl9leHRyYWN0KGV4bXBsLCAiWzAtOV0rIFthLXpdKyIpKSkgJT4lDQogIG11dGF0ZShOdW1iZXIgPSBhcy5udW1lcmljKGdzdWIoIiAuKiIsICIiLCBFeHRyYWN0KSksIENvbnRlbnQgPSBnc3ViKCIuKiAiLCAiIiwgRXh0cmFjdCkpDQpgYGANCg0KVXNpbmcgUmVndWxhciBFeHByZXNzaW9ucywgd2Ugd2VyZSBpbW1lZGlhdGVseSBhYmxlIHRvIGV4dHJhY3Qgb3V0IGp1c3QgdGhlIHJlbGV2YW50IGluZm9ybWF0aW9uIHRoYXQgd2UgZGVzaXJlZCBmcm9tIGEgbGFyZ2VyIGJvZHkgb2YgdGV4dC4gQWZ0ZXIgZG9pbmcgc28sIHdlIGNvdWxkIHRoZW4gcmVmb3JtYXQgdGhlIG51bWJlcnMgdG8gcnVuIGFueSBraW5kIG9mIHN0YXRpc3RpY2FsIGFuYWx5c2lzIG9yIGNhbGN1bGF0aW9uIHRoYXQgd2UnZCBsaWtlLCBzb21ldGhpbmcgdGhhdCB3YXMgcHJldmlvdXNseSBub3QgcG9zc2libGUgd2hlbiBhbGwgdGhlIG51bWJlcnMgd2VyZSBoaWRkZW4vZW5jb2RlZCBpbiB0aGUgZm9ybSBvZiBhIHBocmFzZSBmb3VuZCB3aXRoaW4gdGhlIGxhcmdlciBib2R5IG9mIHRleHQuDQoNCg0KDQojIyBDb25jbHVzaW9uDQoNCkluIGNvbmNsdXNpb24sIFJlZ3VsYXIgRXhwcmVzc2lvbnMgYXJlIGEgcG93ZXJmdWwgdG9vbCB3aGVuIGRlYWxpbmcgd2l0aCBsYXJnZSBib2RpZXMgb2YgdGV4dCwgd2hldGhlciB5b3UgYXJlIGFuIGFuYWx5c3QgdHJ5aW5nIHRvIGNsZWFuIHVwIGRhdGEgYmVpbmcgZmVkIGludG8gYSBNYWNoaW5lIExlYXJuaW5nIE1vZGVsLCBhIHN0dWRlbnQgbG9va2luZyBmb3IgYSBwYXJ0aWN1bGFyIHBhc3NhZ2UvZXhhbXBsZSBpbiBhbiBlbGVjdHJvbmljIHRleHRib29rL1BERi9FQm9vaywgb3IganVzdCBhIGNvbXB1dGVyLXNhdnZ5IGluZGl2aWR1YWwgc2VhcmNoaW5nIGZvciBjZXJ0YWluIHRleHQtcGF0dGVybnMgaW4gYSBzZXQgb2YgZW1haWxzIG9yIGEgcGFydGljdWxhcmx5IGxhcmdlIE1pY3Jvc29mdCBXb3JkIGRvY3VtZW50LiBBcmd1YWJseSB0aGVpciBncmVhdGVzdCBzdHJlbmd0aCBvdmVyIGFsdGVybmF0aXZlIHRlY2huaXF1ZXMgaXMgdGhlaXIgc2ltcGxlIGNvbnN0cnVjdGlvbiAobm8gY29kaW5nIGV4cGVyaWVuY2UgcmVxdWlyZWQpIGFuZCB0aGUgZmFjdCB0aGF0IG5lYXJseSBldmVyeSBzZWFyY2ggYmFyIHRvIHRoZSBtb3N0IHBvcHVsYXIgY29tcHV0ZXIgdG9vbHMgYW5kIGFwcGxpY2F0aW9ucyBhcm91bmQgYXJlIGFibGUgdG8gdXNlIGFuZCBpbnRlcnByZXQgUmVndWxhciBFeHByZXNzaW9ucyAodGhvdWdoIHRoZSAnZmxhdm9ycycgdGhhdCBlYWNoIGFwcCB1c2VzIG1heSB2YXJ5KS4gU28gdGhlIG5leHQgdGltZSB5b3UgcHVsbCB1cCBDdHJsLUYgb24gYSBXb3JkIERvY3VtZW50LCBjb25zaWRlciB1c2luZyBSZWd1bGFyIEV4cHJlc3Npb25zIHRvIG1ha2UgeW91ciBuZXh0ICdmaW5kJyBvciAnZmluZC1hbmQtcmVwbGFjZScgYWxsIHRoZSBtb3JlIGV4YWN0IGFuZCBwcmVjaXNlIQ0KDQoNCg0KYGBge3IsIHJlc3VsdHM9J2hvbGQnLCBlY2hvPUZBTFNFfQ0Kb3B0aW9ucyh3aWR0aCA9IDgwKQ0KY2F0KCJSIFNlc3Npb24gSW5mb3JtYXRpb246XG4iKQ0Kc2Vzc2lvbkluZm8oKQ0KYGBgDQoNCg0KDQo=