403726: GYM101246 A Bencoding

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:

• every string s is encoded as "<k>:<s>", where "<s>" is the string itself and "<k>" 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 s is allowed to be empty.

  For example, "4:spam" represents the string "spam", "0:" represents an empty string.

• every integer n is encoded as "i<n>e", where "<n>" 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 n doesn't necessarily fit into any of the standard integer data types provided by programming languages. Only non-negative integers can be encoded using bencoding.

  For example, "i1024e" represents the number 1024.

• every list items containing n elements item₀, item₁, ..., item_n - 1 is encoded as "l<item₀><item₁> ... <item_n - 1>e". Each item of the list item_i is a supported data structure encoded using bencoding technique. Lists are allowed to be empty.

  For example, "li101el4:spami1024eee" represents the list "[ 101, [ "spam", 1024 ] ]".

• every dictionary dict consisting of n keys key₀, key₁, ..., key_n - 1 mapped into n values value₀, value₁, ..., value_n - 1 correspondingly is encoded as "d<key₀><value₀><key₁><value₁> ... <key_n - 1><value_n - 1>e". 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.

  For 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" ]".

A character sequence c is called a valid bencoded object if the following two conditions are met:

• c is a correct bencoded representation of a single string, integer, list or dictionary;
• the number of characters in c doesn't exceed a given number m.

For 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".

Given 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.

The first line of the input contains one integer m (2 ≤ m ≤ 10⁹)  — 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 10⁶ characters.

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".

14
li10e11:abcdefghijke

Error at position 6!

10
i-1e

Error at position 1!

3
i2

Error at position 2!

18
dli1eei1ei1eli1eee

ok

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.