[POI2009]Prz

时间限制:50s      空间限制:162MB

题目描述

你的任务是计算一个函数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中元素个数


输入格式

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


输出格式

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


样例输入

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

样例输出

0
1

提示

感谢MT大牛贡献译文.


题目来源

没有写明来源

Menuappsclose