gWheels

일반적인 산악자전거에는 두 개의 기어 그룹이 있다. 하나는 페달에 연결되어 있고, 다른 하나는 뒷바퀴에 연결되어 있다. 하나의 기어 그룹은 여러 기어로 구성되며, 이들은 보통 서로 다른 수의 톱니를 가진다. 체인은 페달 기어 그룹의 기어 하나와 바퀴 기어 그룹의 기어 하나를 연결하며, 이에 따라 자전거를 타는 사람의 페달링 속도와 바퀴 속도 사이의 비율이 결정된다. 예를 들어, 체인이 페달의 톱니가 5개인 기어와 바퀴의 톱니가 10개인 기어를 연결한다면, 자전거를 타는 사람이 바퀴를 한 번 회전시키기 위해 페달 기어를 두 번 회전시켜야 하므로 비율은 1/2가 된다. 자전거를 타는 사람은 페달 그룹의 임의의 기어 하나와 바퀴 그룹의 임의의 기어 하나를 연결하도록 체인을 바꿀 수 있다.

여러분은 방금 세 개의 기어 그룹이 있는 특별한 새 산악자전거를 구입했다. 하나는 페달에 연결되어 있고, 하나는 바퀴에 연결되어 있으며, 그 사이에 추가 기어 그룹 하나가 있다. 이 산악자전거에는 두 개의 체인이 있다. 첫 번째 체인은 항상 페달 기어 그룹의 기어 하나와 추가 기어 그룹의 기어 하나를 연결해야 하며, 두 번째 체인은 항상 추가 기어 그룹의 기어 하나와 바퀴 기어 그룹의 기어 하나를 연결해야 한다. 또한 두 체인이 추가 기어 그룹의 같은 기어를 모두 사용할 수는 없다.

페달, 추가 및 바퀴 그룹에서 사용할 수 있는 기어들의 톱니 수가 주어질 때, 페달링 속도와 바퀴 속도 사이의 비율을 정확히 P/Q로 만들 수 있는가? 주어진 기어 집합에 대해 이러한 질문에 여러 번 답해야 할 수도 있다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ 각 기어의 톱니 수 ≤ 10000. 1 ≤ P, Q의 모든 값 ≤ $10^{9}$. 1 ≤ M ≤ 10.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ $N_{p}$, $N_{t}$ ≤ 10. 2 ≤ $N_{e}$ ≤ 10.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 180초. 1 ≤ $N_{p}$, $N_{t}$ ≤ 2000. 2 ≤ $N_{e}$ ≤ 2000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 페달, 추가 및 바퀴 그룹의 기어 수를 나타내는 3개의 정수 $N_{p}$, $N_{e}$, $N_{t}$가 있는 한 줄로 시작한다. 그다음 세 줄이 더 주어진다. 이 줄들에는 각각 $N_{p}$, $N_{e}$, $N_{t}$개의 정수가 있으며, 각각 페달, 추가 및 바퀴 기어 그룹의 서로 다른 기어들의 톱니 수를 나타낸다. (한 그룹 내 기어들의 톱니 수는 모두 서로 다름이 보장된다.) 그다음 줄에는 질문의 수를 나타내는 정수 하나 M이 주어진다. 마지막으로 M개의 줄이 주어지며, 각 줄에는 목표 비율을 나타내는 2개의 정수 P와 Q가 있다. (이 비율이 기약분수임은 보장되지 않는다.)

각 테스트 케이스마다 먼저 "Case #x:"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작한다. 그런 다음 테스트 케이스 내의 각 질문에 대해, 질문이 제시된 순서대로 한 줄씩 출력한다. 비율 P/Q를 만들 수 있다면 Yes을, 만들 수 없다면 No을 출력한다.

테스트 케이스의 첫 번째 질문에서는 비율 1/1를 만들 수 없다. 그러려면 두 체인이 추가 기어 그룹의 같은 기어에 걸려야 하는데, 이는 허용되지 않기 때문이다.

두 번째 질문에서는 첫 번째 체인이 페달 기어 그룹의 톱니가 5개인 기어와 추가 기어 그룹의 톱니가 4개인 기어를 연결하도록 하고, 두 번째 체인이 추가 기어 그룹의 톱니가 6개인 기어와 바퀴 기어 그룹의 톱니가 3개인 기어를 연결하도록 할 수 있다. 이렇게 설정하면 비율은 5/2가 된다.