Ctrl-F

View as PDF

Points: 1.10 (partial)
Time limit: 4.0s
Memory limit: 1G
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Kuroni loves using Ctrl-F when programming, especially the feature that highlights the substrings that match the searched string. Whenever he is given two strings with equal length ~s~ and ~t~, Kuroni will try to find a way to create the same highlight pattern on these two strings.

Formally, Kuroni wants to find pairs of strings ~u~ and ~v~ such that:

• The length of ~u~ is equal to the length of ~v~.

• String ~u~ must be a substring of ~s~; additionally, string ~v~ must be a substring of ~t~.

• String ~u~ is a substring starting from position ~i~ on ~s~ if and only if string ~v~ is a substring starting from position ~i~ on ~t~ (for all ~1 \le i \le |s| - |u| + 1~).

Find the number of pairs of strings ~(u, v)~ that satisfy the above condition; additionally, output the sum of the lengths of ~u~ in all such pairs.

Input

The first line of the input contains a positive integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the length of strings ~s~ and ~t~.

The second and third lines of the input are strings ~s~ and ~t~ (~|s| = |t| = n~). ~s~ and ~t~ only consist of lowercase Latin letters.

Output

Output two integers separated by a space: the number of pairs of strings ~(u, v)~ that satisfy the condition of the problem, and the sum of the lengths of ~u~ in all such pairs.

Scoring

1 750 ~n \le 200~
2 1000 ~n \le 2000~
3 1250 No additional constraints
Total 3000

Sample Input 1

6
banana
kokoro


Sample Output 1

9 35


Sample Input 2

6
tuturu
kokoro


Sample Output 2

17 51


Sample Input 3

10
abcabxabcd
tyztyotyok


Sample Output 3

40 194


Notes

In the first example test case, ~u = \texttt{a}~ and ~v = \texttt{o}~ is a pair of strings that satisfies the condition, while ~u = \texttt{ana}~ and ~v = \texttt{kok}~ is not.

Highlight pattern of Ctrl-F in the first example test case with ~u = \texttt{a}~ and ~v = \texttt{o}~.

Highlight pattern of Ctrl-F in the first example test case with ~u = \texttt{ana}~ and ~v = \texttt{kok}~.