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, "
    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 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, "
    li101el4:spami1024eee
    " 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, "
    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 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 . 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.

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

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

Example(s)
sample input
 
sample output
 
14
li10e11:abcdefghijke

Error at position 6!


sample input
 
sample output
 
10
i-1e

Error at position 1!


sample input
 
sample output
 
3
i2

Error at position 2!


sample input
 
sample output
 
18
dli1eei1ei1eli1eee

ok



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