J. Devil's Recitation Ⅰ
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

给定一个高为 $$$n$$$ 的形如下图的图形 (下图 $$$n=4$$$)

$$$n=4$$$.

其中最后一行仅包含一个矩形，随后每向上一行都会在两侧多出两个矩形，最后一行的那个矩形下方是出口。

你可以在第一行的任意一个矩形中放入一颗小球，小球会径直向下抵达到下一行，小球在抵达某一行的最左侧时会向右一格，抵达某一行的最右侧时会向左一格，抵达最后一行时会继续向下抵达出口。

除此之外，还存在 $$$m$$$ 个矩形内存在一个小洞，小球抵达存在小洞的矩形时会直接消失。

请问从第一行的哪些矩形放入小球能使小球从出口离开？

Input

输出第一行包含正整数 $$$T$$$ $$$(1\le{T}\le{10^4})$$$ ，代表测试组数。

对于每组测试： 第一行包含两个整数 $$$n,m$$$ $$$(1\le{n}\le{{10^5}},0\le{m}\le{\min(n^2,2\times{10^5})})$$$ ，分别代表图形的深度和存在小洞的矩形个数。

随后 $$$m$$$ 行每行包含两个正整数 $$$r_i,c_i$$$ $$$(1\le{r_i}\le{n},1\le{c_i}\le{2\times{(n-r_i)}+1})$$$ ，代表第 $$$r_i$$$ 行第 $$$c_i$$$ 个矩形有小洞，确保小洞的位置两两不同。

确保 $$$\sum n\le{10^5},\sum m\le{2\times{10^5}}$$$ 。

Output

输出 $$$T$$$ 行，对于每个测试，输出一个长为 $$$2n-1$$$ 的 $$$01$$$ 字符串，其中第 $$$i$$$ 个字符为 $$$1$$$ 则代表第一行第 $$$i$$$ 个矩形放下小球后能到达出口，反之则代表不能。

Example
Input
1
4 3
2 1
1 5
3 3
Output
0011000