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

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