gWheels (Large)

보통의 산악자전거에는 기어 그룹이 두 벌 있다. 한 벌은 페달에, 다른 한 벌은 뒷바퀴에 달려 있다. 한 그룹은 기어 여러 개로 이루어지고, 같은 그룹 안의 기어는 보통 톱니 수가 서로 다르다. 체인 하나가 페달 그룹의 기어 하나와 바퀴 그룹의 기어 하나를 잇고, 이 연결이 페달을 돌리는 속도와 바퀴가 도는 속도의 비를 정한다. 예를 들어 체인이 페달의 톱니 5개짜리 기어와 바퀴의 톱니 10개짜리 기어를 이으면 비는 $1/2$이다. 바퀴를 한 바퀴 돌리려면 페달 기어를 두 바퀴 돌려야 하기 때문이다. 타는 사람은 체인을 옮겨서 페달 그룹의 어느 기어든 바퀴 그룹의 어느 기어든 연결할 수 있다.

당신은 기어 그룹이 세 벌인 특별한 산악자전거를 샀다. 한 벌은 페달에, 한 벌은 바퀴에, 나머지 한 벌은 그 둘 사이에 있다. 이 자전거에는 체인이 두 개다. 첫 번째 체인은 항상 페달 그룹의 기어 하나와 중간 그룹의 기어 하나를 잇고, 두 번째 체인은 항상 중간 그룹의 기어 하나와 바퀴 그룹의 기어 하나를 잇는다. 두 체인이 중간 그룹의 같은 기어를 함께 쓸 수는 없다.

페달 그룹, 중간 그룹, 바퀴 그룹에 있는 기어의 톱니 수가 주어질 때, 페달 속도와 바퀴 속도의 비를 정확히 $P/Q$로 맞출 수 있는지 판정하라. 기어 구성 하나마다 이런 질문이 여러 개 주어진다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 페달 그룹, 중간 그룹, 바퀴 그룹의 기어 개수를 나타내는 세 정수 $N_p$, $N_e$, $N_t$가 주어진다. 이어서 세 줄이 주어지며, 각 줄은 페달 그룹, 중간 그룹, 바퀴 그룹에 있는 기어의 톱니 수를 순서대로 $N_p$개, $N_e$개, $N_t$개 담는다. 한 그룹 안의 톱니 수는 모두 다르다. 다음 줄에는 질문의 수 $M$이 주어진다. 마지막으로 $M$개의 줄에 목표 비를 나타내는 두 정수 $P$와 $Q$가 주어진다. $P/Q$가 기약분수라는 보장은 없다.

각 테스트 케이스마다 먼저 "Case #x:"를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이다. 그다음 질문이 주어진 순서대로 한 줄씩, 비 $P/Q$를 만들 수 있으면 Yes를, 만들 수 없으면 No를 출력한다.

• $1 \le T \le 100$
• $1 \le$ 각 기어의 톱니 수 $\le 10000$
• $1 \le P \le 10^9$, $1 \le Q \le 10^9$
• $1 \le M \le 10$
• $1 \le N_p \le 2000$, $1 \le N_t \le 2000$
• $2 \le N_e \le 2000$

페달 그룹에 톱니 5개짜리 기어 하나, 중간 그룹에 톱니 4개와 6개짜리 기어, 바퀴 그룹에 톱니 3개, 5개, 7개짜리 기어가 있는 경우를 보자.

비 $1/1$은 만들 수 없다. 이 비를 만들려면 두 체인이 중간 그룹의 같은 기어를 써야 하는데, 그것은 허용되지 않는다.

비 $5/2$는 만들 수 있다. 첫 번째 체인을 페달의 톱니 5개짜리 기어와 중간 그룹의 톱니 4개짜리 기어에 걸고, 두 번째 체인을 중간 그룹의 톱니 6개짜리 기어와 바퀴의 톱니 3개짜리 기어에 걸면 된다.