题目描述

给出一个长度为N的整数串A,和一个长度为K(K<=N)的整数串B,A和B中的元素均是不大于S的正整数,我们认为两个串是相等的,当两个串的长度相当，并且两个串中,对于任意的i,第i个元素在两个串中的排名是一样的。例如: 1 2 3 5 4 8 10 23 25 24 这两个串是相等的 现在要求在A的所有长度=B的长度的子串中，有多少子串与B串相等

输入格式

第一行三个整数 N,K,S。 第二行N个整数表示A串第三行K个整数表示B串

输出格式

第一行三个整数 N,K,S。 第二行N个整数表示A串第三行K个整数表示B串

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

1
3

提示

对于20%的数据 N=10000对于100%的数据 N<=500000 S<=10000

题目来源

没有写明来源