Jancsi

Jancsi și tabelele

Jancsi are un tabel cu $n$ elemente, format din numere întregi, $a$, și un tabel cu $m$ elemente întregi, $b$.

Jancsi consideră un tabel $c$ de lungime $m$ ca fiind „bun” dacă elementele tabelului $c$ pot fi rearanjate astfel încât cel puțin $k$ dintre ele să coincidă cu elementele tabelului $b$.

De exemplu, dacă $b=[1, 2, 3, 4]$ și $k=3$, atunci:

• Tabelele $[4, 1, 2, 3]$ și $[2, 3, 4, 5]$ sunt bune (pentru că pot fi rearanjate ca $[1, 2, 3, 4]$ și $[5, 2, 3, 4]$)
• Tabelele $[3, 4, 5, 6]$ și $[3, 4, 3, 4]$ nu sunt bune.

Cerință

Jancsi selectează fiecare subsecvență de lungime $m$ din tabelul $a$ ca un posibil tabel $c$. Ajutați-l pe Jancsi să numere câte dintre aceste tabele sunt bune.

Altfel spus, trebuie să determinăm numărul de poziții $l$ unde $1 \leq l \leq n - m + 1$, iar elementele $a_l$, $a_{l+1}$, ... , $a_{l+m-1}$ formează un tabel bun.

Date de intrare

• Prima linie a fișierului de intrare jancsi.in conține un număr întreg $t$ - numărul de teste
• Pentru fiecare test, prima linie conține trei numere întregi: $n$, $m$ și $k$ - numărul elementelor din tablourile $a$ și $b$ și numărul corespunzător de elemente care trebuie să se potrivesc
• A doua linie conține $n$ numere întregi: $a_1$, $a_2$, …, $a_n$ - elementele tabelului $a$
• A treia linie conține $m$ numere întregi: $b_1$, $b_2$, …, $b_n$ - elementele tabelului $b$

Date de ieșire

• Pentru fiecare test, scrieți în jancsi.out pe o linie separată numărul de tabele bune din tabelul $a$.

Restricții și precizări

• $1 \leq t \leq 10^4$
• $1 \leq k \leq m \leq n \leq 2 \cdot 10^5$;
• $1 \leq a_i \leq 10^6$
• $1 \leq b_i \leq 10^6$
• Elementele tabelului $a$ nu sunt neapărat unice. Elementele tabelului $b$ nu sunt neapărat unice.

Exemplu

jancsi.in

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

jancsi.out

4
3
2
4
1

Explicație

• În primul exemplu, toate subsecvențele sunt bune.
• În al doilea exemplu, subsecvențele bune încep la pozițiile 1, 2 și 3.
• În al treilea exemplu, subsecvențele bune încep la pozițiile 1 și 2.