文理学院程序设计在线练习


cc similar

Time Limit: 1 Second(s)    Memory Limit: 128 MB

Total Submission(s): 6   Accepted Submission(s): 0
Problem Description

CC is bored, so he plays a sequence of numbers. Now, he defines an interesting thing:
There are two sequences of numbers a1, a2,..., an (A) and b1, b2,..., bn (B), if for any 1<= i, j <= n, they meet one of the following three cases:
(1) ai<aj and bi<bj
(2) ai=aj and bi=bj
(3) ai>aj and bi>bj
Then the two sequences are called "CC similar".
Now, CC gets a sequence A of length n and a sequence B of length m.He wants to know how many consecutive subsequences in B are "CC similar" with A.

Input

The first line has a positive integer T, indicating the number of input data cases
each case has three lines:
The first line has two positive integers n,m(1<= n,m <= 1e5),representing the length of A,B.
The second line has n positive integers : a1, a2,..., an (1<=ai<=30)
The third line has m positive integers : b1, b2,..., bm (1<=bj<=30)

Output

For each sample, output a line "Case #x: Y", x stands for the number of samples (starting from 1), Y represents how many consecutive sub sequences in B is "CC similar" with A.

Sample Input
2
2 4
1 2
3 4 5 2
3 5
2 3 3
1 4 4 6 8
Sample Output
Case #1: 2
Case #2: 1
Source

2017绍兴市技能竞赛