AT_tenka1_2013_qualA_d 天下一展開

你需要为朋友タクヤ君编写一个程序，从他提供的特定方式压缩的字符串中获取展开后特定位置的子串。 压缩前的字符串仅由英文字母组成。压缩方法是将连续出现 $n$ 次的子串 $x$ 替换为 `($ x $)$ n $`。例如，`ABABABA` 可以被替换为 `(AB)3A`。其中，子串 $x$ 的长度 $|x| \geq 1$，重复次数 $n \geq 1$。 这种替换操作可以多次进行，例如，字符串 `AAABBAAABB` 可以被替换成 `(AAABB)2`，然后再被替换成 `((A)3BB)2` 或 `((A)3(B)2)2`。 因此，压缩后的字符串（即输入字符串）需要符合以下 [EBNF](http://ja.wikipedia.org/wiki/EBNF) 语法规范： ``` input = string, {string} ; string = alphabet, {alphabet} | "(", input, ")", positive_number ; alphabet = "A" | "B" | ... | "Z" | "a" | "b" | ... | "z" ; positive_number = digit_excluding_zero, {digit} ; digit_excluding_zero = "1" | "2" | ... | "9" ; digit = "0" | digit_excluding_zero ; ``` 输入格式如下： - 第一行包含三个整数 $B$、$L$ 和 $N$，分别表示展开后需要引用的部分的起始位置 $B$（$-M \leq B < M$）、子串的长度 $L$（$1 \leq L \leq 10^5$）以及压缩后的字符串长度 $N$（$1 \leq N \leq 10^4$）。其中，$M$ 是压缩前字符串的长度。 - 第二行是压缩后的字符串 $S$。 - 如果 $B$ 是非负的，则从字符串开头（以 $0$ 为起点）开始计数；如果 $B$ 为负的，则从字符串末尾（以 $-1$ 为起点）向前计数。 - 不论 $B$ 的正负，子串都是从起始位置向末尾方向取 $L$ 个字符。题目保证这一定可以得到长度为 $L$ 的子串。 输出格式 - 输出展开后引用的子串，结果占一行，确保行的尾部有换行符。 ### 样例输入 ``` 0 7 6 (AB)3A ``` ### 样例输出 ``` ABABABA ``` ### 样例输入 ``` -6 5 11 ((A)3(B)2)2 ``` ### 样例输出 ``` BAAAB ``` ### 数据范围与提示 - 压缩前的字符串最大长度为 $10^{15}$ - 对于 $L, N \leq 100$ 且 $M \leq 1000$ 的情形，能够获得部分分数50分，总分130分。 - 对于 $L, N \leq 100$ 的情形，额外获取50分，总分130分。 **本翻译由 AI 自动生成**

无

无