测试数据来自 system/2946

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小苇和小沐正在玩猜金币比赛。游戏的玩法如下：小苇和小沐开始时各有一定数量的金币。小苇取出 \(A\) 枚金币捏在手中，小沐猜测 \(A\) 是偶数还是奇数。如果小沐猜对了，他从小苇那里赢得 \(A\) 枚金币，如果她猜错了，她输给小苇A枚金币（如果小沐的金币不足 \(A\) 枚，则他就会输掉所有金币）。当某人输掉了所有金币，则判定他输掉比赛。

　　已知小沐拥有\(m（1≤m≤10^9）\)枚金币。基于他对小苇的习惯的充分了解，他发现在每一回合，小苇只可能取出 \(k（1≤k≤4）\)种不同数量的金币：\(x_1,x_2,..,x_k\)。他们接下来准备玩 \(n（1≤n≤3 * 10^5）\) 回合的比赛。希望你能求出一个字典序最小的猜数序列，使得无论小苇如何选择，小沐都不会输？

【输入格式】

　　输入的第一行包含一枚整数\( t（1≤t≤10）\)，为测试数据的组数。对于每组数据：
　　第一行包含三枚整数 \(m，n\) 和 \(k\)，分别表示小沐拥有的金币数量，回合数及小苇每回合取出金币的选择种数。
以下\(n\)行，第\(i\)行包含\(k\)个不同的空格分隔的整数 \(x_{i1} x_{i2} … x_{ik} (1≤xij≤103)\)，表示小苇在第 \(i\) 回合可能取出的金币数量。
　　输入保证所有测试数据的 \(n\) 之和不超过 \(3*10^5\)

【输出格式】

　　对于每一组测试数据，输出小沐保证不输的字典序最小的猜测序列，或者如果她会输则出−1。猜测序列输出在一行中，包含 \(n\) 个0或1，其中0表示偶数，1表示奇数。

【输入输出样例1】

　Input

2
10 3 2
2 5
1 3
1 3
10 3 3
2 7 5
8 3 4
2 5 6

　Output

001
-1

【样例1解释】

　　在第一枚测试用例中，唯一字典序更小的行动序列是 000，但 小苇 可以使 小沐 输，通过先出 5，将 小沐 的金币数量从 10 减少到 5，然后再出 3，将 小沐 的金币数量从 5 减少到 2，然后出 3，这会输光她所有的金币。
如果 小沐 采用正确的行动序列 001，那么如果 小苇 以同样的方式进行游戏，最后当她出3 时，小沐 将获得那 3 枚金币，将她的金币数量增加到 5。可以进一步证明，只要 小沐 操作是 001，小苇 无法以其他的方式赢走 小沐 的所有金币。

【输入输出样例】

　Input

1
20 8 2
3 5
3 5
3 5
3 5
3 5
3 5
3 5
3 5

　Output

00010101

【样例2解释】

　　在第二枚测试用例中，可以证明，对于小沐可以选择的任何行动顺序，小苇 都存在一种方式可以赢走 小沐 的所有金币。

【测试点性质】

　　测试点 \(3：M≤16\)。
　　测试点 \(4−6：M≤1000\)。
　　测试点 \(7−12：\)没有额外限制。

【来源】

　　Mr.he