You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

教练准备了 $n$ 场模拟赛，每场模拟赛会考察 $m$ 个知识点中的一部分。

教练希望在讲解知识点后的一段时间内考察它，也就是说，他会在第 $l_i$ 到第 $r_i$ 场模拟赛考察第 $i$ 个知识点。

F 对每个知识点都有自己的难度评分，他认为第 $i$ 个知识点的难度是 $v_i$，一场模拟赛的难度为它考察的所有知识点的难度评分之和，自然地，如果一场模拟赛没有考察任何知识点，那么它的难度是 0。

F 已经学过了一些知识点，而对于没学过的知识点，他可以将难度评估为在 $[0,w]$ 之内的任意整数。对于每场模拟赛，他想知道是否存在一种评估难度的方式，使得这场模拟赛是 $n$ 场模拟赛中难度最高的。

输入格式

第一行三个正整数 $n,m,w$，分别表示模拟赛、知识点的数量和难度的值域。

接下来 $m$ 行描述 $m$ 个知识点，第 $i$ 行三个整数 $l_i,r_i,v_i$ 表示第 $i$ 个知识点的出现时间和难度评分。其中 $v_i=-1$ 表示 F 没学过这个知识点，$v_i \ne -1$ 表示 F 学过这个知识点并认为它的难度为 $v_i$。

输出格式

一个长度为 $n$ 的 01 串，第 $i$ 位为 1 当且仅当这场模拟赛可能是 $n$ 场模拟赛中难度最高的。

样例

2 4 3
1 2 2
2 2 -1
1 1 -1
2 2 1

11

令 $v_2=1,v_3=2$，此时两场模拟赛的难度均为 4，均是难度最高的。

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 5000,1 \le w \le 10^6, -1 \le v_i \le w$。