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:

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

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.


Online Contester Team © 2002 - 2010. All rights reserved.