栗酱的数列
题号:NC14694
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

栗酱有一个长度为n的数列A,一个长度为m的数列B,现在询问A中有多少个长度为m的连续子序列A',
满足(a'1+b1)%k = (a'2+b2)%k = …… = (a'm + bm)%k。

输入描述:

第一行一个数T,表示有T组数据。
对于每组数据,
第一行三个整数,n, m, k。
第一行输入n个数, a1,a2,…,an, 表示A数列中的数,
第二行输入m个数, b1,b2,…,bm, 表示B数列中的数。

输出描述:

每一组数据输出一行,满足条件的连续子序列数量。
示例1

输入

复制
2
3 2 5
7 8 7
8 7
3 2 5
7 8 9
8 7

输出

复制
1
2

备注:

T≤15,
2≤m≤n≤2×105,
1≤ai,bi,k≤109