[SGU528] Bencoding

题目描述

Bencoding 用字符序列表示四类数据：字符串、非负整数、列表和字典。

字符串

字符串 $s$ 编码为 k:s，其中 $k$ 是字符串长度的十进制表示，不能有前导零；长度为 $0$ 时写作 0。字符串内容本身可以包含任意允许的字符。

例如 4:spam 表示字符串 spam，0: 表示空串。

非负整数

非负整数 $x$ 编码为 i<x>e。数字部分不能有前导零，只有数字 $0$ 本身写作 0。整数可能非常大，不能假定它能放入标准整数类型。

例如 i1024e 表示整数 $1024$。

列表

包含元素 $item_0,item_1,\ldots,item_{k-1}$ 的列表编码为：

l<item0><item1>...<item(k-1)>e

每个元素自身也是一个合法的 Bencoding 对象。列表允许为空，因此空列表编码为 le。

字典

包含若干“键—值”对的字典编码为：

d<key0><value0><key1><value1>...e

键和值都可以是任意一种 Bencoding 对象；允许重复键和值；字典也允许为空，因此空字典编码为 de。

---

给定最大总长度 $m$ 和一个字符序列 $c$。

称一个序列为合法对象，当且仅当：

1. 它恰好编码一个完整的 Bencoding 对象；
2. 它的总长度不超过 $m$。

如果 $c$ 本身是合法对象，输出 ok。

否则，需要找到最大的 $j$，使得前缀 $c[0\ldots j-1]$ 仍然可以作为某个长度不超过 $m$ 的合法对象的前缀。这里 $j$ 等于前缀长度，字符位置从 $0$ 开始编号。

如果整个 $c$ 都可以继续补全，则 $j=|c|$。

输入格式

第一行一个整数 $m$。

第二行一个字符序列 $c$。其中每个字符的 ASCII 码均在 $33\sim127$ 之间，因此不包含空格。

输出格式

若 $c$ 本身是合法对象，输出：

ok

否则输出：

Error at position j!

其中 $j$ 为题目定义的最大位置。

数据范围

$2\le m\le10^9$。

$1\le |c|\le10^6$。

样例

样例输入 1

14
li10e11:abcdefghijke

样例输出 1

Error at position 6!

样例输入 2

10
i-1e

样例输出 2

Error at position 1!

样例输入 3

3
i2

样例输出 3

Error at position 2!

样例输入 4

18
dli1eei1ei1eli1eee

样例输出 4

ok