528. Bencoding

Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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, "
    " represents the string "spam", "
    " 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, "
    " represents the number 1024.

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

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

  • every dictionary dict consisting of n keys key0, key1,..., keyn-1 mapped into n values value0, value1,..., valuen-1 correspondingly is encoded as "d<key0><value0><key1><value1> <keyn-1><valuen-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, "
    " 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 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="
" 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 . If c is not a , it also has to find the longest prefix of c which could be a prefix of some . 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 . If the given character sequence c is not a , but the entire sequence c is a prefix of some , then j is considered equal to the length of c.

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.

Print a single line containing word "
" (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 "

sample input
sample output
Error at position 6!

sample input
sample output
Error at position 1!

sample input
sample output
Error at position 2!

sample input
sample output

In the first sample test the given sequence is not a valid bencoded object. But its prefix "
" can be extended to a valid bencoded object while not exceeding 14 characters in length (for example, "
"). It's not the case with longer prefixes of length 7 and more, so j=6 in this case.