本题没有可用的提交语言。

P1602. 字符串变换

题目描述

人们长期以来一直在追求提高文件的压缩率。最近，有人提出了一种算法，该算法仅对文件进行重排而不进行压缩，但在使用该算法调整文件后，我们可以实现比以往更高的压缩率。

我们定义字符串的“头部”为其第一个字符，“尾部”为其最后一个字符。

算法工作流程如下：

1. 构造循环字符串：给定一个长度为 ( n ) 的字符串 ( S )，构造 ( n ) 个字符串。第 ( i ) 个字符串通过将第 ( i-1 ) 个字符串的头部移动到尾部得到（即循环右移一位）。
2. 排序字符串：将这 ( n ) 个字符串按以下规则排序：
   • 先按头部字符升序排列；
   • 若头部字符相同，则按原字符串中头部字符在 ( S ) 中的原始位置升序排列（即原字符串在 ( S ) 中的起始位置越小越靠前）。
3. 生成结果字符串：按排序后的顺序，依次取每个字符串的尾部字符，拼接成新字符串 ( S' )。
4. 记录位置：找到原字符串 ( S ) 在排序后的字符串列表中的位置 ( p )（从 1 开始计数）。

你的任务分为两种：

• 任务A（C='A'）：给定 ( S )，生成 ( S' ) 并输出 ( p )。
• 任务B（C='B'）：给定 ( S' ) 和 ( p )，还原原始字符串 ( S )。

输入格式

输入包含一个测试用例：

• 第一行是字符 ( C )（'A' 或 'B'），表示任务类型。
• 当 ( C='A' ) 时：
  • 第二行是整数 ( n )（( 1 \leq n \leq 10000 )），表示字符串长度。
  • 第三行是字符串 ( S )。
• 当 ( C='B' ) 时：
  • 第二行是整数 ( n )（( 1 \leq n \leq 10000 )），表示字符串长度。
  • 第三行是字符串 ( S' )。
  • 第四行是整数 ( p )（( 1 \leq p \leq n )），表示原字符串在排序后的列表中的位置。

输出格式

• 当 ( C='A' ) 时：
  • 第一行输出字符串 ( S' )。
  • 第二行输出整数 ( p )。
• 当 ( C='B' ) 时：
  • 输出还原后的原始字符串 ( S )。

输入输出示例

示例1（任务A）

输入：

A  
7  
example  

输出：

xelpame  
7  

示例2（任务B）

输入：

B  
7  
xelpame  
7  

输出：

example  

来源

浙江OI 2001