3567. 周期字符串

Time limit per test: 5.0 seconds

Memory limit: 512 megabytes

有两个无限长的字符串 , ,周期分别为 ,

周期的定义如下:字符串 的周期为 ,则字符串 满足 , 对于 。其中 表示 从第 个字符到第 个字符的子串。

现求满足 的个数。亦即,两个字符串前 个位置有多少位置是相等的?

Input

第一行三个整数 ()。

第二行,长度为 的字符串

第三行,长度为 的字符串

, 均由 AGCT 组成。

Examples

Input
5 4 9
AGCAG
AGCC
Output
5
Input
5 4 9
AAAAA
AAAA
Output
9

10 Solved out of 109 users tried.

13 Accepted out of 631 tried.

8.6 EMB will be rewarded for solving this problem.

Created: 4 months, 1 week ago.

Updated: 4 months, 1 week ago.

Latest Submission: 2 weeks, 5 days ago.

Source: 2018 华东师范大学校赛

Problem Tags
fft