코드-식사 전환기

Umon은 먹는 것을 좋아하는 코더다. 그가 가장 좋아하는 두 가지 활동이 무엇인지 아는가? 물론 코딩과 식사다! 그는 언제나 하루 종일 그 두 가지 활동만 하며 보낸다. 하지만 그는 하루 중 어떤 시간은 코딩에 쓰는 것이 더 좋고, 다른 시간은 식사에 쓰는 것이 더 좋다고 생각한다.

이 문제를 설명하기 위해 Umon은 자신의 하루를 S개의 시간 구간으로 나눈다. i번째 시간 구간 동안 Umon이 시간의 100%를 코딩하면 코딩을 $C_{i}$단위 달성한다. 반면 시간의 100%를 식사에 쓰면 식사를 $E_{i}$단위 달성한다. 물론 Umon은 시간의 일부만 코딩에 쓰고 나머지를 식사에 쓸 수도 있다. 형식적으로 그는 실수 f (0 ≤ f ≤ 1)를 선택하고, 시간 중 f만큼 코딩하며, 나머지 (1 - f)만큼의 시간을 식사에 사용한다. 이렇게 하면 코딩을 f × $C_{i}$단위, 식사를 (1 - f) × $E_{i}$단위 달성한다. Umon이 하루 동안 달성하는 코딩의 총량은 각 시간 구간에서 달성한 모든 코딩 단위의 합이다. 식사의 총량도 같은 방식으로 계산한다.

Umon은 앞으로 D일 동안의 일정을 계획해야 한다. i번째 날에는 코딩을 총 적어도 $A_{i}$단위, 식사를 $B_{i}$단위 달성해야 한다. 각 날짜에 대해 Umon이 목표를 달성할 방법이 있는지 판별한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해, 1 ≤ $C_{i}$ ≤ $10^{4}$. 모든 i에 대해, 1 ≤ $E_{i}$ ≤ $10^{4}$. 모든 i에 대해, 0 ≤ $A_{i}$ ≤ $10^{8}$. 모든 i에 대해, 0 ≤ $B_{i}$ ≤ $10^{8}$.

테스트 세트 1 (공개)

1 ≤ S ≤ 2. 1 ≤ D ≤ 10.

테스트 세트 2 (비공개)

테스트 케이스 중 적어도 TODO%에 대해: 1 ≤ S ≤ $10^{3}$. 1 ≤ D ≤ $10^{3}$.

모든 테스트 케이스에 대해: 1 ≤ S ≤ $10^{5}$. 1 ≤ D ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 각각 날짜의 수와 하루의 시간 구간 수를 나타내는 두 정수 D와 S가 포함된 줄로 시작한다.

그다음 S개의 줄이 주어지며, 각 줄은 하나의 시간 구간을 설명한다. i번째 줄에는 두 정수 $C_{i}$와 $E_{i}$가 주어진다. 이는 각각 Umon이 해당 시간 구간의 100%를 코딩할 경우 달성하는 코딩 단위의 양과 해당 시간 구간의 100%를 식사에 쓸 경우 달성하는 식사 단위의 양이다.

그다음 D개의 줄이 주어지며, 각 줄은 하나의 날짜를 설명한다. i번째 줄에는 두 정수 $A_{i}$와 $B_{i}$가 주어지며, 이는 그날 달성해야 하는 코딩과 식사의 최소 총량이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 D개의 문자로 이루어진 문자열이다. i번째 날의 목표를 충족할 수 있는 일정이 존재하면 i번째 문자는 Y이고, 그렇지 않으면 N여야 한다.

첫 번째 예제 케이스에는 날짜가 4개 있고 각 날짜에는 시간 구간이 2개 있다.

• 1일에는 Umon이 두 시간 구간 모두에서 단지 100%를 식사에 쓸 수 있으며, 그 결과 코딩을 총 0단위, 식사를 8 + 10 = 18단위 달성하여 목표에 도달한다.

• 2일에는 Umon이 첫 번째 시간 구간의 100%를 식사에 쓰고, 두 번째 시간 구간의 50%를 코딩에, 50%를 식사에 사용할 수 있다. 이로써 코딩을 총 0 × 3 + 0.5 × 6 = 3단위, 식사를 1 × 8 + 0.5 × 10 = 13단위 달성하여 목표에 도달한다.

• 3일에는 코딩을 총 10단위 달성하는 것이 불가능하다.

• 4일에는 목표를 달성하는 방법이 무한히 많다. 가능한 전략 하나는 첫 번째 시간 구간에서 42%를 코딩하고(58%를 식사에 쓰고), 두 번째 시간 구간에서 98.76%를 코딩하는(1.24%를 식사에 쓰는) 것이다. 이 전략으로 코딩을 총 0.42 × 3 + 0.9876 × 6 = 7.1856단위, 식사를 0.58 × 8 + 0.0124 × 10 = 4.764단위 달성한다.

따라서 정답은 YYNY여야 한다.

두 번째 예제 케이스에서는 시간 구간의 특성값이 반드시 서로 다를 필요는 없다는 점에 유의한다.