题目描述
给定一个高为 n 的形如下图的图形 (下图 n=4 )
其中最后一行仅包含一个矩形，随后每向上一行都会在两侧多出两个矩形，最后一行的那个矩形下方是出口。
你可以在第一行的任意一个矩形中放入一颗小球，小球会径直向下抵达到下一行，小球在抵达某一行的最左侧时会向右一格，抵达某一行的最右侧时会向左一格，抵达最后一行时会继续向下抵达出口。
除此之外，还存在 m 个矩形内存在一个传送带，小球抵达存在传送带的矩形时会沿着传送带的方向向左或右移动一个矩形的距离（确保传送带不在每行的最左侧和最右侧）。
请问从第一行的哪些矩形放入小球能使小球从出口离开？
输入
输出第一行包含正整数 T (1≤T≤10^4)，代表测试组数。
对于每组测试： 第一行包含两个整数 n,m (1≤n≤10^5,0≤m≤min((n−1)^2,2×10^5)) ，分别代表图形的深度和存在传送带的矩形个数。
随后 m 行每行包含两个正整数和一个字符 ri,ci,di (1≤ri≤n−1,2≤ci≤2×(n−ri),di∈(L,R))，代表第 ri 行第 c 个矩形有传送带，di=L 代表方向向左，di=R 代表方向向右，确保有传送带的矩形的位置两两不同。
确保 ∑n≤10^5,∑m≤2×10^5 。
输出
输出 T 行，对于每个测试，输出一个长为 2n−1 的 01 字符串，其中第 i 个字符为 1 则代表第一行第 i 个矩形放下小球后能到达出口，反之则代表不能。
样例输入 Copy
1
4 3
2 2 L
1 6 R
1 2 R
样例输出 Copy
0001100