Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem G: 五队-长春-cc相似

Problem G: 五队-长春-cc相似

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 19  Solved: 7
[Submit][Status][Web Board]

Description

cc最近闲的无聊,玩起了数列。现在,ta定义了一个有趣的东西:

有两个数列a1,a2,...,anb1,b2,...,bn,若对任意1<= i, j <= n,两数列均满足以下三种情况之一:

(1)   ai<aj bi<bj

(2)   ai=aj bi=bj

(3)   ai>aj bi>bj

则称这两个数列”cc相似

现在,cc得到了一个长度为n的数列a和一个长度为m的数列bta想知道b中有多少连续子数列和a”cc相似的。

Input

第一行一个正整数T,表示有多少组输入数据

每组数据有三行

第一行两个正整数n,m1<=n, m <= 1e5,表示a,b数组的长度

第二行n个正整数a1,a2,...,an (1<=ai<=30)

第三行m个正整数b1,b2,...,bm(1<=bi<=30)

Output

对每组样例输出一行 “Case #x: y”x代表样例数(从1开始),y代表b中有多少连续子数列和a”cc相似的。

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

HINT

暂无测试数据

[Submit][Status][Web Board]