You are given two strings of length . Find the number of pairs (l, r) of integers such that 1 \le l \le r \le n and the substring s_ls_{l+1}s_{l+2}\ldots s_r is lexicographically smaller than t_lt_{l+1}t_{l+2}\ldots t_r.
A string is lexicographically smaller than a string if and only if one of the following holds:
is a prefix of , but a \ne b;
in the first position where and differ, the string has a letter that appears earlier in the alphabet than the corresponding letter in .
The first line of the input contains a single integer (1 \le n \le 200\,000).
The second and the third lines of the input contain strings , of length correspondingly, each consisting only of lowercase Latin letters.
Output a single integer — the number of pairs (l, r) of integers such that 1 \le l \le r \le n and the substring s_ls_{l+1}s_{l+2}\ldots s_r is lexicographically smaller than t_lt_{l+1}t_{l+2}\ldots t_r.
Example 1
Example 2
Example 3
Example 4
Example 5
In the first sample, there are such pairs: (1, 2), (1, 3), (2, 2), (2, 3).