{"raw_statement":[{"iden":"statement","content":"Bencoding 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: \n\nFor example, \"_4:spam_\" represents the string \"spam\", \"_0:_\" represents an empty string.\n\nFor example, \"_i1024e_\" represents the number 1024.\n\nFor example, \"_li101el4:spami1024eee_\" represents the list \"[ 101, [ \"spam\", 1024 ] ]\".\n\nFor example, \"_d1:a0:1:pl1:b2:cdee_\" represents the dictionary with string key \"a\" mapped into an empty string \"\", and key \"p\" mapped into the list \"[ \"b\", \"cd\" ]\". \n\nA character sequence c is called a _valid bencoded object_ if the following two conditions are met: \n\nFor example, when m = 3, the sequence c = \"_2:bc_\" is not considered a valid bencoded object even though it represents a correctly encoded string \"bc\".\n\nGiven m and c you have to write a program which should determine whether c is a _valid bencoded object_. If c is not a _valid bencoded object_, it also has to find the longest prefix of c which could be a prefix of some _valid bencoded object_. Formally, you should find a maximal position j within the given character sequence c, such that a prefix of c up to, but not including, character at position j could be a prefix of some _valid bencoded object_. If the given character sequence c is not a _valid bencoded object_, but the entire sequence c is a prefix of some _valid bencoded object_, then j is considered equal to the length of c.\n\nThe first line of the input contains one integer m (2 ≤ m ≤ 109)  — 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 106 characters.\n\nPrint a single line containing word \"_ok_\" (without quotes) if the given input character sequence is a valid bencoded object. Otherwise, print message \"_Error at position j!_\". The first character of the input sequence is considered to have position \"_0_\".\n\nIn the first sample test the given sequence is not a valid bencoded object. But its prefix \"_li10e1_\" can be extended to a valid bencoded object while not exceeding 14 characters in length (for example, \"_li10e1:xe_\"). It's not the case with longer prefixes of length 7 and more, so j = 6 in this case.\n\n"},{"iden":"input","content":"The first line of the input contains one integer m (2 ≤ m ≤ 109)  — 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 106 characters."},{"iden":"output","content":"Print a single line containing word \"_ok_\" (without quotes) if the given input character sequence is a valid bencoded object. Otherwise, print message \"_Error at position j!_\". The first character of the input sequence is considered to have position \"_0_\"."},{"iden":"examples","content":"Input14li10e11:abcdefghijkeOutputError at position 6!Input10i-1eOutputError at position 1!Input3i2OutputError at position 2!Input18dli1eei1ei1eli1eeeOutputok"},{"iden":"note","content":"In the first sample test the given sequence is not a valid bencoded object. But its prefix \"_li10e1_\" can be extended to a valid bencoded object while not exceeding 14 characters in length (for example, \"_li10e1:xe_\"). It's not the case with longer prefixes of length 7 and more, so j = 6 in this case."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ m \\in \\mathbb{Z} $ with $ 2 \\leq m \\leq 10^9 $ be the maximum allowed length of a valid bencoded object.  \nLet $ c \\in \\Sigma^* $ be the input character sequence, where $ \\Sigma = \\{ \\text{ASCII characters from 33 to 127} \\} $, and $ |c| \\leq 10^6 $.  \n\nA **valid bencoded object** is a string over $ \\Sigma $ that conforms strictly to the Bencoding grammar:  \n- **Integer**: $ i[+-]?[0-9]+e $  \n- **String**: $ [0-9]+:[^\\text{e}]^* $ (length prefix followed by exactly that many characters)  \n- **List**: $ l(\\text{bencoded\\_object})^*e $  \n- **Dictionary**: $ d(\\text{string}:\\text{bencoded\\_object})^*e $, where keys are strings and appear in lexicographic order  \n\n**Constraints**  \n1. $ |c| \\leq 10^6 $  \n2. $ m \\geq 2 $  \n3. The entire bencoded object (if valid) must satisfy $ |c| \\leq m $  \n\n**Objective**  \nDetermine:  \n- If $ c $ is a valid bencoded object and $ |c| \\leq m $, output `\"ok\"`.  \n- Otherwise, find the maximal $ j \\in \\{0, 1, \\dots, |c|\\} $ such that the prefix $ c[0:j] $ is a prefix of *some* valid bencoded object of length $ \\leq m $.  \n  - If no such prefix exists (even the empty string), then $ j = 0 $.  \n  - Output `\"Error at position $ j $!\"`.  \n\n**Note**: The parsing must be deterministic and respect Bencoding syntax rules exactly. The dictionary keys must be in lexicographically sorted order.","simple_statement":"Given a string and a max length m, check if it's a valid bencoded object. If not, find the longest prefix that could be part of a valid bencoded object, and output \"Error at position j!\". If valid, output \"ok\".","has_page_source":false}