만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

마법의 상자

시간 제한2초메모리 제한1024 MB

요약
지름 D인 공을 L×D×D 상자에 넣었을 때 어떤 칼도 공을 관통하지 않는 위치가 있는지 판단합니다.
난이도

보통10점 중 6점

유형
기하, 정렬, 그리디
정답자
아직 제출이 없습니다

문제

블라디슬라프는 마술사 쇼를 매우 좋아한다. 어느 날 상자에 들어간 조수에게 여러 개의 칼이 꽂혔는데도 조수가 무사히 빠져나오는 마술을 보고, 집에서 같은 마술을 해 보고 싶어졌다.

그는 크기가 L×D×DL \times D \times D인 직육면체 상자를 준비한다. 그 안에 지름이 정확히 DD인 구 모양의 축구공을 넣는다.

크기가 D×LD \times L인 면에는 칼을 상자 안까지 관통시킬 점이 여러 개 표시되어 있다. 정사각형 면 (크기 DimesDD imes D)에는 칼을 꽂지 않는다.

지금까지는 어떤 칼에도 찔리지 않는 위치를 찾지 못했다. 블라디슬라프는 상자 안에 칼이 하나도 공을 찌르지 않도록 공을 놓을 수 있는 위치가 존재하는지 알고 싶어 한다. 공이 칼에 닿는 것은 괜찮다. 각 칼은 무한히 가는 것으로 본다.

입력

첫 줄에 세 정수 NN, DD, LL (0≤N≤1000000 \le N \le 100000, 1≤D,L≤1091 \le D, L \le 10^9)이 주어진다. NN은 칼의 개수이고, DD와 LL은 상자와 공의 크기이다.

다음 NN개의 줄에는 칼이 상자를 뚫는 점이 하나씩 적혀 있다.

앞면에는 왼쪽 아래 모서리를 원점으로 하는 좌표계를 쓰며, 오른쪽 위 모서리의 좌표는 (L,D)(L, D)이다. 윗면도 같은 방식의 좌표계를 쓰고, 위에서 내려다본 방향으로 본다. F x y (0≤x≤L0 \le x \le L, 0≤y≤D0 \le y \le D)는 앞면의 (x,y)(x, y) 점에 칼이 꽂힌다는 뜻이다. U x y (0≤x≤L0 \le x \le L, 0≤y≤D0 \le y \le D)는 윗면의 (x,y)(x, y) 점에 칼이 꽂힌다는 뜻이다. 모든 좌표는 정수이며, 모든 점은 서로 다르다.

출력

어떤 칼도 공을 찌르지 않도록 공을 상자 안에 놓을 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

예제2

  1. 예제 1

    입력
    2 2 4
    U 1 1
    F 3 1
    
    예상 출력
    YES
    
  2. 예제 2

    입력
    2 2 3
    U 1 1
    F 2 1
    
    예상 출력
    NO