题目描述

小 C 发现公告里有一段字母写错了。错的写法是 $a$，正确写法是 $b$。她想找出原公告 $t$ 中所有写成 $a$ 的地方。

小 C 从左往右找。每次找到最靠左的一处 $a$，就把这整段字母圈起来，然后从圈出的字母后面继续找。已经圈过的字母不能再用来圈另一处。例如，$a$ 是 aa、$t$ 是 aaa 时，先圈出第 $1$、$2$ 个字母。第 $2$、$3$ 个字母虽然也是 aa，但第 $2$ 个已经被圈过，所以不能再算一处。最终只圈出 $1$ 处。

小 C 最多愿意修改 $k$ 处：

• 如果圈出的地方多于 $k$ 处，她暂时不修改，只输出圈出的处数。
• 否则，她把每一处圈出的 $a$ 换成 $b$，输出修改后的整份公告。若一处也没有圈出，就原样输出公告。

只在原公告中找错词。替换后新写出的字母不会再拿来查找，即使 $b$ 里面也含有 $a$。

输入格式

第一行一个整数 $k$，表示小 C 最多愿意修改多少处。

第二行两个非空小写字符串 $a,b$，分别表示错误写法和正确写法。

第三行一个非空小写字符串 $t$，表示原公告。

输出格式

如果圈出的处数大于 $k$，输出这个处数；否则输出修改后的公告。

样例

1
aba q
abababa

2

2
aba q
abababa

qbq

2
ab aba
abab

abaaba

0
cat dog
milk

milk

样例解释

样例 1 和 2 中，abababa 可以看成 aba | b | aba，共圈出 $2$ 处。样例 1 只愿意修改 $1$ 处，所以输出 2；样例 2 可以修改 $2$ 处，替换后得到 qbq。

样例 3 中，原文 abab 可以看成 ab | ab，两处都换成 aba，得到 abaaba。新写出的字母不再参与查找。

样例 4 中，milk 里没有 cat，所以即使 $k=0$，也原样输出 milk。

数据范围与约定

对于 $100\%$ 的数据，$0\le k\le10^5$，$1\le|a|,|b|\le20$，$1\le|t|\le10^5$；三个字符串只含小写英文字母。输出的字符串长度不超过 $2\times10^6$。