题目描述

在 $\texttt{Flappy Bird}$ 游戏中，玩家控制一只小鸟，跨越由各种不同长度水管所组成的障碍。玩家可以选择通过点击屏幕来控制小鸟的飞行，点击屏幕会使小鸟向上飞，不点击则会使小鸟往下落。小鸟碰到障碍则游戏结束。

江桥 喜欢玩 $\texttt{Flappy Bird}$ 游戏，因此他出了一个问题来考考你。

在本题中，小鸟从 $(0,m)$ 出发。当 $t=0$ 时，玩家需要点击屏幕表示开始游戏，此时小鸟不进行上下飞行，从 $(0,m)$ 移动到 $(1,m)$。

对于 $t>0$ 的每个时刻，玩家可以选择是否点击屏幕：

1. 若选择点击屏幕，则小鸟会往右上方移动一格，从 $(x,y)$ 移动到 $(x+1,y+1)$；
2. 若选择不点击屏幕，则小鸟会往右下方移动一格，从 $(x,y)$ 移动到 $(x+1,y−1)$。

小鸟需要跨越 $n$ 个障碍。每个障碍有一个横坐标 $x$ 和一个缺口 $y_0,y_1(y_0≤y_1)$，其中 $y_0,y_1$ 分别表示柱子缺口的下坐标和上坐标。

当小鸟的 $x$ 坐标等于任一障碍的 $x$ 坐标时，其 $y$ 坐标必须位于该障碍的缺口范围内，即 $y_0≤y_1$。若在任一时刻小鸟的位置不满足障碍的缺口条件，或者小鸟撞到地面（即 $y=0$），则视为失败。

给定小鸟 $t=0$ 的初始位置和所有障碍的信息，请尝试给出一种操作序列使得小鸟能够顺利通过全部障碍。如果不存在，输出 $-1$。

请注意本题的空间限制。

输入格式

第一行包含两个整数 $n,m$，表示障碍的数量和小鸟的初始位置。

接下来 $n$ 行，每一行包含三个整数 $x_i,y_{1,i},y_{2,i}$，表示第 $i$ 个障碍的位置，缺口的下边界和上边界。输入保证 $x_i$ 严格递增。

输出格式

如果不存在一种合法方案使得小鸟能够安全通过所有障碍，则输出 $-1$。

若存在，输出一个长度为 $x_n$ 的由 $0$ 和 $1$ 组成的字符串，第 $i$ 个字符表示第 $i−1$ 时刻的操作。其中 $1$ 表示点击屏幕，$0$ 表示不点击。如果存在多种合法方案，输出任意一种。

3 4
2 2 3
4 3 6
6 2 4

101100

6 5
1 5 5
2 4 7
4 2 6
7 3 5
10 4 7
11 1 3

10011100010

3 4
1 5 6
4 1 10
8 1 10

-1

样例解释

对于样例 $1$，一种可行的方案如图所示：

对于样例 $2$，一种可行的方案如图所示：

对于样例 $3$，小鸟在 $t=1$ 时会直接撞墙，故无法通过全部障碍。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$4$。

有合理的子任务依赖。

子任务编号	$n≤$	$x_i≤$	$y_{1,i},m≤$	分值
$1$	$10^{3}$	$10^3$	$10$	$20$
$2$			$10^9$
$3$	$10^{5}$	$10^7$	$10$
$4$			$10^9$	$40$

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^{5},1 \leq n \leq x_i \leq 10^7,1 \leq y_{0,i} \leq y_{1,i} \leq 10^9, 1 \leq m \leq 10^9$，保证 $x_i$ 严格递增。