题目背景

原题是一道交互题。为了便于在 Hydro OJ 上使用普通输入输出文件进行评测，本配置将交互过程改成一次性输出：输入中直接给出字符串 s 和隐藏排列 p，选手需要输出一组满足原交互题要求的最小询问方案，以及最终得到的字符串 t。评测器会检查询问方案是否合法、是否达到原题要求的最小询问数，并检查最终字符串是否正确。

题目描述

给定一个由 $n$ 个小写英文字母组成的字符串

$$s_1s_2\ldots s_n$$

以及一个排列

$$p_1,p_2,\ldots,p_n.$$

按照如下方式生成新字符串 $t$：将原字符串 $s$ 的第 $i$ 个字符放到新字符串 $t$ 的第 $p_i$ 个位置上。

也就是说：

$$t_{p_i}=s_i.$$

你需要输出字符串 $t$。

为了保留原交互题的判题逻辑，你还需要在最终答案前输出一组“询问方案”。一次询问由一对下标 $(a,b)$ 组成，满足 $1 \le a < b \le n$。原交互题中，询问 $(a,b)$ 可以知道 $p_a < p_b$ 是否成立。

在本普通评测版本中，评测器要求你的询问方案满足原题的最小询问数要求：

• 对于所有满足 $1 \le a < b \le n$ 且 $s_a \ne s_b$ 的下标对，必须恰好询问一次；
• 对于满足 $s_a=s_b$ 的下标对，不应询问；
• 询问对不能重复；
• 最后输出的字符串必须等于由排列 $p$ 生成的 $t$。

若存在多种合法输出，输出任意一种即可。

输入格式

第一行输入一个非空字符串 $s$，只包含小写英文字母。

第二行输入 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示一个 $1$ 到 $n$ 的排列。

输出格式

第一行输出一个整数 $k$，表示询问数量。

接下来 $k$ 行，每行输出两个整数 $a_i,b_i$，表示询问下标对，要求 $1 \le a_i < b_i \le n$。

最后一行输出字符串 $t$。

数据范围

对于全部测试数据：

• $1 \le n \le 100$；
• $s$ 只包含小写英文字母；
• $p$ 是 $1$ 到 $n$ 的一个排列；
• $0 \le k \le 10^4$。

样例 1

输入

ab
1 2

输出

1
1 2
ab

说明

询问 $(1,2)$ 后可知 $p_1<p_2$，排列为 $1,2$，因此新字符串为 ab。

样例 2

输入

ab
2 1

输出

1
1 2
ba

说明

询问 $(1,2)$ 后可知 $p_1>p_2$，排列为 $2,1$，因此新字符串为 ba。

样例 3

输入

qqq
2 3 1

输出

0
qqq

说明

所有字符都相同，不需要询问任何下标对，最终字符串仍然是 qqq。

样例 4

输入

baa
2 3 1

输出

2
1 2
1 3
aba

说明

原字符串为 baa，排列为 $2,3,1$，所以：

• $s_1=\texttt{b}$ 放到位置 $2$；
• $s_2=\texttt{a}$ 放到位置 $3$；
• $s_3=\texttt{a}$ 放到位置 $1$。

因此最终字符串为 aba。

原题评分信息

原交互题分组如下，仅供参考：

组别	分值	附加限制	依赖组别
0		样例测试	-
1	5	$n \le 3$	0
2	10	字符串 $s$ 中所有字符互不相同	-
3	25	字符串 $s$ 中只含有 a 和 b
4	60	无附加限制	0,1,2,3

提示

本配置的 Special Judge 会根据输入中的 $s$ 和 $p$ 验证输出。.out 文件只作为 Hydro 测试数据结构的一部分存在，最终判定以 spj.cpp 为准。