311244: CF1955D. Inaccurate Subsequence Search

D. Inaccurate Subsequence Searchtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Maxim has an array $a$ of $n$ integers and an array $b$ of $m$ integers ($m \le n$).

Maxim considers an array $c$ of length $m$ to be good if the elements of array $c$ can be rearranged in such a way that at least $k$ of them match the elements of array $b$.

For example, if $b = [1, 2, 3, 4]$ and $k = 3$, then the arrays $[4, 1, 2, 3]$ and $[2, 3, 4, 5]$ are good (they can be reordered as follows: $[1, 2, 3, 4]$ and $[5, 2, 3, 4]$), while the arrays $[3, 4, 5, 6]$ and $[3, 4, 3, 4]$ are not good.

Maxim wants to choose every subsegment of array $a$ of length $m$ as the elements of array $c$. Help Maxim count how many selected arrays will be good.

In other words, find the number of positions $1 \le l \le n - m + 1$ such that the elements $a_l, a_{l+1}, \dots, a_{l + m - 1}$ form a good array.

Input

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le k \le m \le n \le 2 \cdot 10^5$) — the number of elements in arrays $a$ and $b$, the required number of matching elements.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of array $a$. Elements of the array $a$ are not necessarily unique.

The third line of each test case contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le 10^6$) — the elements of array $b$. Elements of the array $b$ are not necessarily unique.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. Similarly, it is guaranteed that the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output the number of good subsegments of array $a$ on a separate line.

ExampleInput

5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6

Output

4
3
2
4
1

Note

In the first example, all subsegments are good.

In the second example, good subsegments start at positions $1$, $2$, and $3$.

In the third example, good subsegments start at positions $1$ and $2$.

题目大意：
这个题目是关于在数组`a`中搜索不准确子序列的问题。给定两个数组`a`和`b`，以及一个整数`k`，我们需要找出数组`a`中所有长度为`m`的子段中，有多少个子段可以重排后至少有`k`个元素与数组`b`中的元素相同。数组`b`的长度`m`小于等于数组`a`的长度`n`。

输入输出数据格式：
- 输入：
- 第一行包含一个整数`t`，表示测试用例的数量。
- 每个测试用例包含三行：
- 第一行包含三个整数`n`、`m`和`k`，分别表示数组`a`和`b`的长度以及要求匹配的元素数量。
- 第二行包含`n`个整数，表示数组`a`的元素。
- 第三行包含`m`个整数，表示数组`b`的元素。
- 输出：
- 对于每个测试用例，输出一行，表示数组`a`中有多少个好的子段。

示例输入输出：
- 输入：
```
5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6
```
- 输出：
```
4
3
2
4
1
```题目大意： 这个题目是关于在数组`a`中搜索不准确子序列的问题。给定两个数组`a`和`b`，以及一个整数`k`，我们需要找出数组`a`中所有长度为`m`的子段中，有多少个子段可以重排后至少有`k`个元素与数组`b`中的元素相同。数组`b`的长度`m`小于等于数组`a`的长度`n`。 输入输出数据格式： - 输入： - 第一行包含一个整数`t`，表示测试用例的数量。 - 每个测试用例包含三行： - 第一行包含三个整数`n`、`m`和`k`，分别表示数组`a`和`b`的长度以及要求匹配的元素数量。 - 第二行包含`n`个整数，表示数组`a`的元素。 - 第三行包含`m`个整数，表示数组`b`的元素。 - 输出： - 对于每个测试用例，输出一行，表示数组`a`中有多少个好的子段。 示例输入输出： - 输入： ``` 5 7 4 2 4 1 2 3 4 5 6 1 2 3 4 7 4 3 4 1 2 3 4 5 6 1 2 3 4 7 4 4 4 1 2 3 4 5 6 1 2 3 4 11 5 3 9 9 2 2 10 9 7 6 3 6 3 6 9 7 8 10 4 1 1 4 1 5 6 6 ``` - 输出： ``` 4 3 2 4 1 ```