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

8 Solved out of 106 users tried.

11 Accepted out of 615 tried.

8.8 EMB will be rewarded for solving this problem.

Created: 1 week, 2 days ago.

Updated: 1 week, 2 days ago.

Latest Submission: 1 day, 22 hours ago.

Source: 2018 华东师范大学校赛

Problem Tags
fft