명함 자르기

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

요약
c x d 크기의 종이를 90도 회전이 가능한 a x b 직사각형 카드로 남는 부분 없이 모두 덮을 수 있는지 판정한다.
난이도

보통10점 중 7점

유형
수학, 정수론, 기하, 구현
정답자
아직 제출이 없습니다

문제

종이 가게를 운영하는 것은 쉽지 않은 일이며, 특히 까다로운 손님을 상대할 때는 더욱 그렇다. 오늘 손님들은 직접 직사각형 종이를 가져와, 정해진 크기의 직사각형 명함으로 잘라 달라고 요청했다. 게다가 종이를 한 조각도 남기지 않고 모두 사용해야 한다고 요구한다. 종이를 아주 작은 조각으로 잘라서 다시 붙여 원하는 명함을 만드는 것은 허용되지 않는다. 각 명함은 90∘90^\circ 회전하여 어느 방향으로든 놓을 수 있다.

아래는 9×69 \times 6 크기의 종이를 2×32 \times 3 명함으로 나눈 예시이다.

입력

첫째 줄에 테스트 케이스의 수 tt (t≤105t \le 10^5)가 주어진다. 이어지는 tt개의 줄에는 각각 네 정수 aa, bb, cc, dd (1≤a,b,c,d≤1091 \le a, b, c, d \le 10^9)가 주어진다. a×ba \times b는 각 명함의 크기이고, c×dc \times d는 종이의 크기이다.

출력

각 테스트 케이스마다, 종이 전체를 명함으로 남김없이 나눌 수 있으면 YES를, 그렇지 않으면 NO를 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    4
2 3 9 6
2 3 8 6
2 3 6 8
2 3 5 7
    예상 출력
    YES
YES
YES
NO