题目描述

牛牛有一个长度大小为 $N$ 的字符串，字符串中的字符仅包括 N，O，I，P 四种。

在牛牛把这个字符串中的某些字符隐藏掉，用 ? 字符代替。

例如原本的字符串是 PPPOPPOPO，牛牛将其隐藏一些字符后一种可能的情况就是字符串变为 ???OP???O。

牛牛想让牛妹猜出这个字符串原来是什么。当然直接去猜的话牛妹肯定过一万年也猜不出来这个字符串是什么。

所以他告诉牛妹，这个字符串是所有可能的字符串中权值大于等于 $x$，字典序降序排列的第 $k$ 个解。

所谓字典序，是指按照查字典的顺序对字符串进行排序，例如 aac 的字典序就小于 aba。

现在牛牛给出了这样一种计算字符串权值的方式，首先牛牛给牛妹一张表格。

\	N	O	I	P
N	$a$	$b$	$c$	$d$
O	$e$	$f$	$g$	$h$
I	$i$	$j$	$k$	$l$
P	$m$	$n$	$o$	$p$

表格中右下的 $4\times 4$ 部分表示字符串中每出现一次行标字母出现在左侧，且列标字母出现在右侧的情况，整个字符串的权值就要加上对应的数值。

例如：如果字符串中出现了 NN 相连，就要加上 $a$，如果字符串中出现了 IO 相连，就要加上 $j$，如果出现了 OI 相连，就要加上 $g$。

计算整个字符串的权值就是出现的所有情况权值之和，例如字符串 NNOI 的权值就为 $a+b+g$。

请你帮助牛妹找到原来的字符串，如果权值大于等于 $x$ 可能的字符串数目不够 $k$ 个，则直接输出一行 $−1$ 表示无解。

输入格式

第一行输入三个正整数 $N, x, k$，表示字符串长度，牛牛的字符串是权值大于等于 $x$，字典序降序排列的第 $k$ 个解。

接下来一行输入一个长度大小为 $N$ 的字符串，字符串仅包括 N，O，I，P，?。

接下来输入一个 $4\times 4$ 的矩阵表示表格的右下部分，表格的说明见题目描述。

输出格式

如果存在权值大于等于 $x$ 的第 $k$ 个解，则输出这个字符串，否则直接输出一行 $−1$ 表示无解。

样例

4 3 108
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

ININ

4 3 109
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

-1

2 10 6
??
0 0 10 0
10 10 0 0
10 0 10 10
0 10 10 0

IP

见附加文件中的 c4.in

见附加文件中的 c4.out

数据范围

• 对于前 $10\%$ 的测试数据，保证 $N \le 10$，$k = 1$。
• 对于前 $30\%$ 的测试数据，保证 $N \le 10$。
• 对于另 $10\%$ 的测试数据，保证 $N \le 10^3$，$x = 0$。
• 对于另 $10\%$ 的测试数据，保证 $N \le 10^3$，$k = 1$。
• 对于另 $100\%$ 的测试数据，保证 $2\le N\le 10^3$，$1\le k\le 10^3$，$0\le x\le 10^9$，$0\le a,b,c,d,\ldots,o,p\le 10^4$。