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 item₀, item₁, ..., item_n - 1 is encoded as "l<item₀><item₁> ... <item_n - 1>e". Each item of the list item_i 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 key₀, key₁, ..., key_n - 1 mapped into n values value₀, value₁, ..., value_n - 1 correspondingly is encoded as "d<key₀><value₀><key₁><value₁> ... <key_n - 1><value_n - 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.