{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBencoding is a modern technique which is used for representing data structures as sequences of characters. It it capable of encoding strings, integers, lists and dictionaries as specified below: \u003c/p\u003e\u003cul\u003e\u003cli\u003e every string \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is encoded as \"\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026gt;:\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e\u0026gt;\", where \"\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e\u0026gt;\" is the string itself and \"\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026gt;\" is its length written with no leading zeros (with the exception of integer zero, which is always represented as \"0\"). Bencoding is capable of encoding empty strings, so \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is allowed to be empty.\u003cp\u003eFor example, \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e4:spam\u003c/span\u003e\" represents the string \"spam\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e0:\u003c/span\u003e\" represents an empty string.\u003c/p\u003e\u003c/li\u003e\u003cli\u003e every integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e is encoded as \"\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u0026gt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003c/span\u003e\", where \"\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u0026gt;\" is the number itself written with no leading zeros (with the exception of integer zero, which is always represented as \"0\"). Bencoding is capable of encoding very large integers, so \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e doesn\u0027t necessarily fit into any of the standard integer data types provided by programming languages. Only non-negative integers can be encoded using bencoding. \u003cp\u003eFor example, \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ei1024e\u003c/span\u003e\" represents the number 1024.\u003c/p\u003e\u003c/li\u003e\u003cli\u003e every list \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eitems\u003c/i\u003e\u003c/span\u003e containing \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e elements \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, ..., \u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e is encoded as \"\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003el\u003c/i\u003e\u003c/span\u003e\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e\u0026gt; ... \u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003c/span\u003e\". Each item of the list \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eitem\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is a supported data structure encoded using bencoding technique. Lists are allowed to be empty.\u003cp\u003eFor example, \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eli101el4:spami1024eee\u003c/span\u003e\" represents the list \"[ 101, [ \"spam\", 1024 ] ]\".\u003c/p\u003e\u003c/li\u003e\u003cli\u003e every dictionary \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003edict\u003c/i\u003e\u003c/span\u003e consisting of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e keys \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ekey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003ekey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, ..., \u003ci\u003ekey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e mapped into \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e values \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e, \u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, ..., \u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e correspondingly is encoded as \"\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ed\u003c/i\u003e\u003c/span\u003e\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ekey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e0\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ekey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e\u0026gt; ... \u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ekey\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u0026lt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/sub\u003e\u003c/span\u003e\u0026gt;\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ee\u003c/i\u003e\u003c/span\u003e\". All keys and values are supported data structures encoded using bencoding technique. A dictionary may have duplicate keys and/or values. Dictionaries are allowed to be empty.\u003cp\u003eFor example, \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ed1:a0:1:pl1:b2:cdee\u003c/span\u003e\" represents the dictionary with string key \"a\" mapped into an empty string \"\", and key \"p\" mapped into the list \"[ \"b\", \"cd\" ]\". \u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e\u003cp\u003eA character sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is called a \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e if the following two conditions are met: \u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is a correct bencoded representation of a single string, integer, list or dictionary; \u003c/li\u003e\u003cli\u003e the number of characters in \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e doesn\u0027t exceed a given number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eFor example, when \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e \u003d 3\u003c/span\u003e, the sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e \u003d \u003c/span\u003e\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e2:bc\u003c/span\u003e\" is not considered a valid bencoded object even though it represents a correctly encoded string \"bc\".\u003c/p\u003e\u003cp\u003eGiven \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e you have to write a program which should determine whether \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is a \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e. If \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is not a \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e, it also has to find the longest prefix of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e which could be a prefix of some \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e. Formally, you should find a maximal position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e within the given character sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e, such that a prefix of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e up to, but not including, character at position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e could be a prefix of some \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e. If the given character sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is not a \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e, but the entire sequence \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is a prefix of some \u003cspan class\u003d\"tex-font-style-it\"\u003evalid bencoded object\u003c/span\u003e, then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e is considered equal to the length of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003em\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e) \u0026nbsp;— the maximum possible length of a valid bencoded object. The second line contains a character sequence which you are to process. The sequence will only contain characters with ASCII codes from 33 to 127, inclusive. Its length will be between 1 and \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e characters.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single line containing word \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eok\u003c/span\u003e\" (without quotes) if the given input character sequence is a valid bencoded object. Otherwise, print message \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eError at position \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e!\u003c/span\u003e\". The first character of the input sequence is considered to have position \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e14\nli10e11:abcdefghijke\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eError at position 6!\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\ni-1e\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eError at position 1!\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\ni2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eError at position 2!\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e18\ndli1eei1ei1eli1eee\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eok\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample test the given sequence is not a valid bencoded object. But its prefix \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eli10e1\u003c/span\u003e\" can be extended to a valid bencoded object while not exceeding 14 characters in length (for example, \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eli10e1:xe\u003c/span\u003e\"). It\u0027s not the case with longer prefixes of length 7 and more, so \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e \u003d 6\u003c/span\u003e in this case.\u003c/p\u003e"}}]}