SOLVE
LATER
Let's define the matching number for two arrays X and Y, each with size n, as the number of pairs of indices \((i,j)\) such that \(X_i = Y_j\) (\(1 \le i,j \le n\)).
You are given an integer K and two arrays A and B with sizes N and M respectively. Find the number of ways to pick two subarrays with equal size, one from array A and the other from array B, such that the matching number for these two subarrays is \(\ge K\).
Note: a subarray consists of one or more consecutive elements of an array.
Constraints
\( 1 \le N , M \le 2,000 \)
\( 1 \le A_i \le 1,000,000,000 \) for each valid i
\( 1 \le B_i \le 1,000,000,000 \) for each valid i
\( 1 \le K \le NM \)
Input format
The first line of the input contains three space-separated integers N, M and K.
The second line contains N space-separated integers \(A_1, \dots, A_N\).
The third line contains M space-separated integers \( B_1, \dots, B_M \).
Output Format
Print a single line containing one number denoting the number of ways to choose the pair of subarrays.
The following pairs of subarrays have matching number \(\ge 1\): ([1], [1]), ([2], [2]), ([3], [3]), ([1, 2], [1, 2]), ([1, 2], [2, 3]), ([2, 3], [1, 2]), ([2, 3], [2, 3]), ([1, 2, 3], [1, 2, 3]).