403726: GYM101246 A Bencoding

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Bencodingtime limit per test1 secondmemory limit per test256 megabytesinputinput.txtoutputoutput.txt

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

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

ExamplesInput
14
li10e11:abcdefghijke
Output
Error at position 6!
Input
10
i-1e
Output
Error at position 1!
Input
3
i2
Output
Error at position 2!
Input
18
dli1eei1ei1eli1eee
Output
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.

加入题单

上一题 下一题 算法标签: