食堂的空调有3种状态:关机、供暖和制冷。
当它关闭时,食堂的温度保持不变。当它被加热时,温度在一分钟内上升1。最后,当它冷却时,温度在一分钟内下降1。可以在任意整数分钟内任意多次更改状态,空调一开始是关着的。
每个学生的特征有三个值:ti-第i个学生光顾食堂的时间(以分钟为单位),li-他们喜欢的温度范围的下限,hi-他们喜欢的温度范围的上限。
学生在光顾食堂的瞬间,如果温度在他们喜欢的范围内,就会感到满意。当且仅当第i分钟的温度在li和hi(包括)之间时,第i个学生才满意。
给定初始温度、学生的访问时间列表以及他们的首选温度范围,您将帮助东区食堂了解是否有可能满足所有学生,最开始,食堂的起始时间为0。
输入输出格式
输入格式
第一行包含两个整数n和m(1≤n≤100,−109≤m≤109),其中n是学生的数量,m是食堂的初始温度。
接下来,n行紧随其后。它们的第i行包含三个整数ti、li和hi(1≤ti≤109,−109≤li≤hi≤109),其中ti是第i个客户访问的时间,li是他们首选温度范围的下限,hi是他们首选温度范围的上限,首选的温度包括在内。
到访时间ti按时间先后,顺序给出。
输出格式
对于每个测试用例,如果有可能满足所有学生的要求,请打印1。否则,打印0。
输入输出样例
输入样例1
3 0
5 1 2
7 3 5
10 -1 0
输出样例1
1
输入样例2
2 12
5 7 10
10 16 20
输出样例2
0
说明
在第一种情况下,食堂可以通过以下方式控制空调以满足所有学生:
第0分钟,将状态改为加热(温度为0)。 在第二分钟,将状态改为关闭(温度为2)。 在第5分钟,将状态改为加热(温度为2,第一个学生满意)。 在第6分钟,将状态更改为关闭(温度为3)。 在第7分钟,将状态改为制冷(温度为3,第二个学生满意)。 在第10分钟,温度为0,这可以满足最后一位学生的要求。
在第二种情况下,食堂必须让至少一名学生不满意。
数据范围
30%的数据:n≤30
100%的数据:n≤100