물탱크

과학 교사가 물의 흐름을 관찰하는 실험을 준비하면서 특별히 제작한 물탱크를 받았다.

이 물탱크는 가로 100 cm, 높이 50 cm, 깊이 30 cm이다. 교사는 탱크 안에 양쪽 옆면과 평행하도록 얇은 칸막이 판 여러 개를 세운다. 각 판의 너비는 탱크의 깊이와 같은 30 cm이고, 두께는 무시할 수 있을 만큼 얇다. 모든 판의 높이는 탱크보다 낮으며(즉 50 cm 미만), 어떤 두 판도 높이가 같지 않다.

탱크 위쪽에는 수도꼭지 여러 개가 달려 있다. 실험을 시작할 때 모든 수도꼭지를 동시에 열며, 탱크는 처음에 비어 있다. 어떤 구획에 부어진 물은 그 구획을 둘러싼 두 벽(칸막이 판 또는 옆면) 중 낮은 쪽의 꼭대기에 도달할 때까지 차오르고, 그 높이에 이르면 이웃 구획으로 넘쳐흐른다. 물이 탱크 밖으로 빠져나가는 것은 높이 50 cm인 옆면을 넘칠 때뿐이다.

물의 흐름을 시뮬레이션하여, 주어진 위치와 시각에서의 수위를 구하는 프로그램을 작성하라.

입력은 여러 개의 데이터 집합으로 이루어진다. 첫 줄에는 데이터 집합의 개수 D가 주어진다.

D
DataSet1
DataSet2
...
DataSetD

각 데이터 집합의 형식은 다음과 같다.

N
B1 H1
B2 H2
...
BN HN
M
F1 A1
F2 A2
...
FM AM
L
P1 T1
P2 T2
...
PL TL

모든 값은 정수이다.

N은 칸막이 판의 개수이다. Bi와 Hi는 i번째 판의 x좌표(cm)와 높이(cm)이다. 높이 Hi는 모두 서로 다르다. 다음을 가정해도 된다.

• 0 < N < 10,
• 0 < B1 < B2 < ... < BN < 100,
• 모든 i에 대해 0 < Hi < 50.

M은 수도꼭지의 개수이다. Fj와 Aj는 j번째 수도꼭지의 x좌표(cm)와 물이 나오는 양(초당 cm³)이다. 어떤 수도꼭지도 판 바로 위에 있지 않으므로, 어떤 Fj도 어떤 Bi와 같지 않다. 다음을 가정해도 된다.

• 0 < M < 10,
• 0 < F1 < F2 < ... < FM < 100,
• 모든 j에 대해 0 < Aj < 100.

L은 관측의 개수이다. Pk는 k번째 관측의 x좌표(cm)이고 Tk는 시작으로부터의 시각(초)이다. 어떤 Pk도 어떤 Bi와 같지 않다. 다음을 가정해도 된다.

• 0 < L < 10,
• 모든 k에 대해 0 < Pk < 100,
• 모든 k에 대해 0 < Tk < 1000000.

각 데이터 집합마다 L개의 줄을 출력한다. k번째 줄에는 시각 Tk에 x좌표 Pk에서의 수면 높이(cm)를 출력한다.

정답은 정확히 일치하는지로 채점되며 모든 입력값이 정수이므로, 각 수위는 유리수이다. 다음과 같이 정확히 출력하라.

• 수위가 정수이면 그 정수를 출력한다.
• 그렇지 않으면 기약분수 p/q 형태로 출력한다. 이때 q > 1이고 gcd(p, q) = 1이다.

탱크가 가장자리까지 가득 차고 나면, 모든 위치에서의 수위는 탱크의 높이인 50 cm와 같다.