[POI2009]Prz

题目描述

你的任务是计算一个函数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大牛贡献译文.

---

题目来源

没有写明来源