该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

伞伞在抄写一串“魔法密码”。

这串密码原本是一个短字符串 $s$，长度是 $k$，比如 qaq。

他要把这个短密码重复写 $n$ 遍，连成一长串。

比如 $s =$ qaq，$n=5$，写出来就是： qaq qaq qaq qaq qaq （连在一起是 qaqqaqqaqqaqqaq）。

可惜，伞伞太马虎了，长串里有且仅有一个字符写错了！

现在请你当小侦探，帮他找出第几个字符（从 $1$ 开始数）写错了。

输入格式

从文件 typo.in 读入数据。 第一行两个正整数 $n, k$，分别表示重复次数和短密码的长度。

第二行一个长度为 $k$ 的字符串 $s$，表示正确的短密码。

第三行一个长度为 $nk$ 的字符串，表示伞伞写下的长串（其中恰好有一个位置和正确串不一样）。

输出格式

输出到文件 typo.out。 一个整数，表示写错的那个字符在长串中的位置（从 $1$ 开始）。

3 3
qaq
qaqqwqqaq

5

4 3
qaq
aaqqaqqaqqaq

1

样例 3

见 typo3.in 与 typo3.ans。

样例 4

见 typo4.in 与 typo4.ans。

样例 5

见 typo5.in 与 typo5.ans。

数据规模与约定

下发文件分别对应子任务 $1,2,3$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $3 \leq n \leq 10^5,1 \leq k \leq 3$，保证初始字符串 $s$ 和写下的字符串只包含小写字母且长度分别为 $k$ 和 $nk$，保证写下的字符串中有且仅有一个位置上的字符被修改了。

时空限制：$1$ 秒 / $256\,\mathrm{MiB}$。