#P18294. Lazy Susan
Lazy Susan
Lazy Susan
个人等间距坐在圆桌周围,按顺时针顺序编号为 到 。圆桌上有一个转盘,摆放着同样编号为 到 的 道菜。
若服务员从第 个人开始上菜,那么第 道菜最初放在第 个人的面前。所有菜上齐的时刻记为第 秒。
每次操作可以将整个转盘顺时针或逆时针转动一格,耗时 秒。顺时针转动后,原来在第 个人面前的菜移到第 个人面前;逆时针则移到第 个人面前。
第 个人的可触及距离为 。如果一道菜当前位于第 个人面前,且存在整数 满足
则第 个人可以立刻享用这道菜,不消耗时间。
有 个偏好要求。第 个要求是:第 个人要在不晚于第 秒时享用第 道菜。在第 秒恰好能够享用,也算满足;初始时即可享用的要求在第 秒满足。
对于每个 ,独立判断是否存在一套转动方案,使所有偏好要求都满足。不同初始位置可以采用不同方案。
输入格式
第一行包含测试组数 ()。
每组测试数据:
- 第一行两个整数 (,)。
- 第二行 个整数 ()。
- 接下来 行,每行三个整数 (,)。
同一组中没有两条要求具有相同的 。相同的人可以有不同菜的要求,不同的人也可以想享用同一道菜。
保证所有测试数据的 之和不超过 , 之和不超过 。
输出格式
对每组测试数据输出一行长度为 的 01 字符串 。若从第 个人开始上菜时存在可行方案,则 ,否则 。
样例
4
5 6
0 0 1 2 1
3 2 2
0 0 2
4 4 4
1 1 3
4 3 5
0 3 2
8 10
2 2 2 0 3 0 0 1
4 3 1
1 0 1
0 7 6
4 4 1
1 7 5
0 4 2
5 3 4
4 6 1
7 7 3
0 2 4
4 4
0 0 0 0
1 0 2
2 0 2
0 0 2
3 0 2
13 0
1 1 4 5 1 4 1 9 1 9 8 1 0
10100
11111010
0000
1111111111111