UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1118. [POI2009]Prz

统计 下载数据

Description

你的任务是计算一个函数F(x, y),其中x和y是两个正整数序列。F的定义如下: boolean F(x, y) if W(x) ≠ W(y) then return 0 else if |W(x)| = |W(y)| = 1 then return 1 else return F(p(x), p(y))  and  F(s(x), s(y)). W(x)表示序列x中元素的集合。(元素的顺序和出现次数将被无视) p(x)表示序列x的最长前缀,满足:W(x) ≠ W(p(x)) s(x)表示序列x的最长后缀。满足:W(x) ≠ W(s(x)) |Z|表示集合Z中元素个数

Input

第一行k表示数据组数。对于每组数据,第一行n,m分别表示x序列的长度与y序列的长度,第二行n个数表示xi,第三行m个数表示yi 1<=k<=13 1<=n,m<=100000 1<=xi,yi<=100

Output

k行,对于每组数据,若F(x,y)为真输出1,否则输出0。

Sample Input

2
4 5
3 1 2 1
1 3 1 2 1
7 7
1 1 2 1 2 1 3
1 1 2 1 3 1 3

Sample Output

0
1

Hint

感谢MT大牛贡献译文.

Source