#P18294. Lazy Susan

Lazy Susan

Lazy Susan

nn 个人等间距坐在圆桌周围,按顺时针顺序编号为 00 到 n−1n-1。圆桌上有一个转盘,摆放着同样编号为 00 到 n−1n-1 的 nn 道菜。

若服务员从第 xx 个人开始上菜,那么第 ii 道菜最初放在第 (x+i) mod n(x+i)\bmod n 个人的面前。所有菜上齐的时刻记为第 00 秒。

每次操作可以将整个转盘顺时针或逆时针转动一格,耗时 11 秒。顺时针转动后,原来在第 ii 个人面前的菜移到第 (i+1) mod n(i+1)\bmod n 个人面前;逆时针则移到第 (i+n−1) mod n(i+n-1)\bmod n 个人面前。

第 ii 个人的可触及距离为 rir_i。如果一道菜当前位于第 jj 个人面前,且存在整数 kk 满足

−ri≤k≤ri,(i+k+n) mod n=j,-r_i\le k\le r_i,\qquad (i+k+n)\bmod n=j,

则第 ii 个人可以立刻享用这道菜,不消耗时间。

有 mm 个偏好要求。第 ii 个要求是:第 pip_i 个人要在不晚于第 tit_i 秒时享用第 did_i 道菜。在第 tit_i 秒恰好能够享用,也算满足;初始时即可享用的要求在第 00 秒满足。

对于每个 x=0,1,…,n−1x=0,1,\ldots,n-1,独立判断是否存在一套转动方案,使所有偏好要求都满足。不同初始位置可以采用不同方案。

输入格式

第一行包含测试组数 TT(1≤T≤25001\le T\le2500)。

每组测试数据:

  • 第一行两个整数 n,mn,m(2≤n≤50002\le n\le5000,0≤m≤min⁡(n2,105)0\le m\le\min(n^2,10^5))。
  • 第二行 nn 个整数 r0,r1,…,rn−1r_0,r_1,\ldots,r_{n-1}(0≤ri≤n0\le r_i\le n)。
  • 接下来 mm 行,每行三个整数 pi,di,tip_i,d_i,t_i(0≤pi,di<n0\le p_i,d_i<n,1≤ti≤1091\le t_i\le10^9)。

同一组中没有两条要求具有相同的 (pi,di)(p_i,d_i)。相同的人可以有不同菜的要求,不同的人也可以想享用同一道菜。

保证所有测试数据的 nn 之和不超过 50005000,mm 之和不超过 10510^5。

输出格式

对每组测试数据输出一行长度为 nn 的 01 字符串 ss。若从第 xx 个人开始上菜时存在可行方案,则 sx=1s_x=1,否则 sx=0s_x=0。

样例

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