시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB3410927.273%

문제

Your friend had a lot of awesome pictures on her computer, until someone messed them up. She found out that most of her image files were either cropped and/or rotated by 90 degrees, or not changed at all. Luckily, she still remembers the original combined set of aspect ratios of all her images.

An aspect ratio for an image of dimensions (A, B) is (A / G, B / G) where G is the greatest common divisor (GCD) of A and B.

Since we don’t care about the image contents, a rotation operation is swapping the width and the height. And a crop operation is selecting a smaller sub-rectangle (with integer dimensions) inside the original image and its sides should be parallel to the sides of the original image.

Your job is to help her to identify a possible original dimensions of each image. Given the dimensions of the messed up images, along with the possible aspect ratios, output a possible original dimensions of each image as well as how many operations were done to mess it up.

입력

Your program will be tested on one or more test cases. The first line of the input will be a single integer T (1 ≤ T ≤ 100) representing the number of test cases. Followed by T test cases. Each test case starts with a line containing an integer M (1 ≤ M ≤ 100) representing the number of possible aspect ratios followed by M lines, each line will contain 2 integers Rx and Ry (1 ≤ Rx ≤ Ry ≤ 100) representing the i-th aspect ratio (for any given aspect ratio, the GCD of Rx and Ry will always be 1), all aspect ratios in the same test case will be distinct. The next line will contain an integer N (1 ≤ N ≤ 100) representing the number of messed up images, followed by N lines, each line will contain 2 integers X and Y (1 ≤ X , Y ≤ 100) representing the dimensions of the i-th messed up image.

출력

For each test case print a single line containing “Case n:” (without quotes) where n is the test case number (starting from 1) followed by N lines, each line should contain 3 integers separated by a single space W, H and K representing a possible original dimensions for the i-th messed up image (the ratio of W and H should be one of the given ratios) and the number of operations used to mess it up (K should be 0 if no changes were made, 1 if it was cropped or rotated, 2 if it was cropped and rotated). For each image, if there are multiple solutions, print the one that minimizes W × H . If there are still multiple solutions, print the one that minimizes W. If there are still multiple solutions, print the one that minimizes K.

예제 입력 1

1
1
3 4
5
3 4
4 3
2 4
4 2
5 6

예제 출력 1

Case 1:
3 4 0
3 4 1
3 4 1
3 4 2
6 8 1