“懒人餐桌”（Lazy Susan）是一种放置在餐桌上的旋转圆盘，用于放置食物或餐具，方便围坐在桌子旁的人们分享和取用。

有 $n$ 个人围坐在圆桌旁享用晚餐，每个人按顺时针方向编号为 $0$ 到 $n-1$，且每两个人之间的距离相等。注意，在顺时针方向上，$(n-1)$ 号人的旁边是 $0$ 号人。

晚餐包含 $n$ 道菜，每道菜按上菜顺序编号为 $0$ 到 $n-1$。服务员将从第 $x$ 个人开始，按顺时针顺序将餐桌上的每道菜放置在每个人的面前。具体来说，第 $i$ 道菜将被放置在第 $[(x + i) \pmod n]$ 号人面前。

每次旋转“懒人餐桌”时，所有菜肴都可以顺时针或逆时针旋转到下一个人的位置。更准确地说，原本在第 $i$ 号人面前的菜肴，经过一次顺时针旋转后会移动到第 $[(i+1) \pmod n]$ 号人的位置，经过一次逆时针旋转后会移动到第 $[(i+n-1) \pmod n]$ 号人的位置。每次操作耗时 $1$ 秒。

每个人都有一个触及距离 $r_i$。如果存在一个整数 $k$ 满足以下条件，第 $i$ 号人就可以享用当前在第 $j$ 号人面前的菜肴：

• $-r_i \le k \le r_i$
• $(i + k + n) \pmod n = j$

一旦满足上述条件，该人可以立即享用这道菜。

在 $n$ 个人之间共有 $m$ 个偏好。第 $i$ 个偏好是：第 $p_i$ 号人希望在所有菜肴上齐后的 $t_i$ 秒内享用到第 $d_i$ 道菜。请确定当服务员从 $x$ 号人开始上菜时（对于所有 $0 \le x < n$），是否能满足所有偏好。

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 2500$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, m$ ($2 \le n \le 5000, 0 \le m \le \min(n^2, 10^5)$)，分别表示人数和偏好数量。

每个测试用例的第二行包含 $n$ 个非负整数 $r_0, r_1, \dots, r_{n-1}$ ($0 \le r_i \le n$)，表示第 $i$ 号人的触及距离。

接下来的 $m$ 行，每行包含三个整数 $p_i, d_i, t_i$ ($0 \le p_i < n, 0 \le d_i < n, 1 \le t_i \le 10^9$)，表示第 $i$ 个偏好的信息。保证对于任意 $1 \le i < j \le m$，满足 $p_i \neq p_j$ 或 $d_i \neq d_j$。

保证所有测试用例的 $n$ 之和不超过 $5000$。 保证所有测试用例的 $m$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个长度为 $n$ 的 $01$ 字符串 $s$。如果服务员从第 $x$ 号人开始上菜可以满足所有偏好，则 $s_x = 1$，否则 $s_x = 0$。

样例

输入 1

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

输出 1

10100
11111010
0000
1111111111111