[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)\ne W(p(x))$；
• $s(x)$ 表示序列 $x$ 的最长后缀，满足 $W(x)\ne W(s(x))$；
• $|Z|$ 表示集合 $Z$ 中元素个数。

输入格式

第一行一个整数 $k$，表示数据组数。

对于每组数据，第一行两个整数 $n, m$，分别表示 $x$ 序列的长度与 $y$ 序列的长度；第二行 $n$ 个数表示 $x_i$；第三行 $m$ 个数表示 $y_i$。

输出格式

输出 $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

数据范围

• $1\le k\le 13$；
• $1\le n, m\le 100000$；
• $1\le x_i, y_i\le 100$。

来源与许可

本题为 POI 2009 试题「Prz」，题面与测试数据整理自 BZOJ 1118，译文由 MT 贡献。

样例 1

输入

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