에어컨

면접 대비

시간 제한1초메모리 제한256 MB

요약

난방, 냉방, 정지를 바꿀 수 있는 에어컨이 초기 온도 m에서 시작해 모든 손님의 방문 시각 온도를 선호 범위 안에 둘 수 있는지 판단합니다.

난이도: 보통10점 중 5점
유형: 구간, 그리디
정답자: 아직 제출이 없습니다

문제

길동이는 불고기 식당을 운영한다. 식당에는 손님이 많아서 방문 전에 예약하는 손님이 많다.

길동이는 손님마다 선호하는 온도 범위를 모두 외우고 있다. 예약 목록을 보면서, 식당의 온도를 조절해 모든 손님을 만족시키려고 한다.

식당의 에어컨에는 off, heating, cooling 세 가지 상태가 있다. off이면 온도가 그대로 유지된다. heating이면 1분마다 온도가 1 올라간다. cooling이면 1분마다 온도가 1 내려간다. 길동이는 정수 분이라면 언제든지 원하는 만큼 상태를 바꿀 수 있다. 에어컨은 처음에 off 상태다.

각 손님은 세 값으로 표현된다. $t_i$ 는 i번째 손님이 방문하는 분, $l_i$ 는 선호 온도 범위의 하한, $h_i$ 는 상한이다.

손님은 방문하는 순간 온도가 선호 범위 안에 있으면 만족한다. 구체적으로, $t_i$ 분의 온도가 $l_i$ 이상 $h_i$ 이하이면 i번째 손님이 만족한다.

입력

첫 줄에 테스트 케이스의 개수 $q$ ( $1 \le q \le 500$ )가 주어진다. 각 테스트 케이스가 그 뒤를 잇는다.

각 테스트 케이스의 첫 줄에는 정수 $n$ 과 $m$ ( $1 \le n \le 100$ , $-10^9 \le m \le 10^9$ )이 주어진다. $n$ 은 예약한 손님의 수이고, $m$ 은 식당의 초기 온도다.

이어서 $n$ 개의 줄에 정수 $t_i$ , $l_i$ , $h_i$ ( $1 \le t_i \le 10^9$ , $-10^9 \le l_i \le h_i \le 10^9$ )가 한 줄에 하나씩 주어진다. 손님은 방문 시각이 감소하지 않는 순서로 주어지며, 현재 시각은 $0$ 이다. 온도 범위의 양 끝 값은 포함된다.

출력

각 테스트 케이스마다 모든 손님을 만족시킬 수 있으면 "YES", 그렇지 않으면 "NO"를 출력한다. 각 글자는 대문자나 소문자 어느 쪽으로 출력해도 된다.

힌트

첫 번째 경우에 길동이는 다음과 같이 에어컨을 조절해 모든 손님을 만족시킬 수 있다.

0분에 상태를 heating으로 바꾼다(온도는 0).
2분에 상태를 off로 바꾼다(온도는 2).
5분에 상태를 heating으로 바꾼다(온도는 2이므로 1번 손님이 만족한다).
6분에 상태를 off로 바꾼다(온도는 3).
7분에 상태를 cooling으로 바꾼다(온도는 3이므로 2번 손님이 만족한다).
10분에는 온도가 0이 되어 마지막 손님이 만족한다.

세 번째 경우에는 길동이가 0분에 상태를 heating으로 바꾸고 그대로 두면 된다. 그러면 모든 손님이 만족한다. 1번 손님의 방문 시각은 2번 손님의 방문 시각과 같다.

두 번째와 네 번째 경우에는 적어도 한 명의 손님은 만족시킬 수 없다.

예제1

예제 1

입력

4
3 0
5 1 2
7 3 5
10 -1 0
2 12
5 7 10
10 16 20
3 -100
100 0 0
100 -50 50
200 100 100
1 100
99 -100 0

예상 출력

YES
NO
YES
NO