Problem: Mr. Denjiro is a science teacher. Today he has just received a specially ordered water tank that will certainly be useful for his innovative experiments on water flow.

<image>
---
Figure 1: The water tank

The size of the tank is 100cm (Width) * 50cm (Height) * 30cm (Depth) (see Figure 1). For the experiments, he fits several partition boards inside of the tank parallel to the sideboards. The width of each board is equal to the depth of the tank, i.e. 30cm. The height of each board is less than that of the tank, i.e. 50 cm, and differs one another. The boards are so thin that he can neglect the thickness in the experiments.

<image>
---
Figure 2: The front view of the tank

The front view of the tank is shown in Figure 2.

There are several faucets above the tank and he turns them on at the beginning of his experiment. The tank is initially empty. Your mission is to write a computer program to simulate water flow in the tank.



Input

The input consists of multiple data sets. D is the number of the data sets.

D
DataSet1
DataSet2
...
DataSetD


The format of each data set (DataSetd , 1 <= d <= D) is as follows.

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


Each line in the data set contains one or two integers.

N is the number of the boards he sets in the tank . Bi and Hi are the x-position (cm) and the height (cm) of the i-th board, where 1 <= i <= N .

Hi s differ from one another. You may assume the following.

> 0 < N < 10 ,
>  0 < B1 < B2 < ... < BN < 100 ,
>  0 < H1 < 50 , 0 < H2 < 50 , ..., 0 < HN < 50.

M is the number of the faucets above the tank . Fj and Aj are the x-position (cm) and the amount of water flow (cm3/second) of the j-th faucet , where 1 <= j <= M .

There is no faucet just above any boards . Namely, none of Fj is equal to Bi .

You may assume the following .

> 0 < M <10 ,
>  0 < F1 < F2 < ... < FM < 100 ,
>  0 < A1 < 100, 0 < A2 < 100, ... 0 < AM < 100.

L is the number of observation time and location. Pk is the x-position (cm) of the k-th observation point. Tk is the k-th observation time in seconds from the beginning.

None of Pk is equal to Bi .

You may assume the following .

> 0 < L < 10 ,
>  0 < P1 < 100, 0 < P2 < 100, ..., 0 < PL < 100 ,
>  0 < T1 < 1000000, 0 < T2 < 1000000, ... , 0 < TL < 1000000.

Output

For each data set, your program should output L lines each containing one real number which represents the height (cm) of the water level specified by the x-position Pk at the time Tk.

Each answer may not have an error greater than 0.001. As long as this condition is satisfied, you may output any number of digits after the decimal point.

After the water tank is filled to the brim, the water level at any Pk is equal to the height of the tank, that is, 50 cm.

Example

Input

2
5
15 40
35 20
50 45
70 30
80 10
3
20 3
60 2
65 2
6
40 4100
25 7500
10 18000
90 7000
25 15000
25 22000
5
15 40
35 20
50 45
70 30
80 10
2
60 4
75 1
3
60 6000
75 6000
85 6000


Output

0.666667
21.4286
36.6667
11.1111
40.0
50.0
30.0
13.3333
13.3333

Solution (in CPP):

Solution:
//author: Hayato Kawakita
//2020/04/30 21:52
//vertict: AC

//problem: Water Tank（国内予選2004)
//URL:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1133&lang=jp
//所要時間: 約１時間
//感想：指示通りに実装するだけであるが、実装するのはかなり大変。この問題を通して、自分の実装力を鍛えることができた。
//なるべく丁寧に解説を入れる予定です。
//説明不足の点があれば、適宜修正します。
//他のアスタリスク付きの問題も解けたら載せたいと思います。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

//depth constant
const ld y = 30;

//inputs
int n;
int b[15], h[15];
int m;
int f[15], a[15];
int l;
int p[15], t[15];

//water level
ld height[15];

//水を加える作業、一番下から順に入れていくイメージです。あふれたらあふれた方向の区間とmergeして考えます。
//left: 仕切り板の左側のindex, right:仕切り板の右側のindex
//volume: t[i]秒までにある蛇口から入った水の体積, fx: 蛇口のx座標
void add(int left, int right, ld& volume, int fx) {
  //再帰して下から埋めていく。
  if (right - left > 1) {
    //ここで、最終的にmergeすべき区間(つまり、h[i]が最も高いindex)を求める。
    int mid = -1, resh = 0;
    FOR(i, left + 1, right) {
      if (chmax(resh, h[i])) {
        mid = i;
      }
    }
    //蛇口が分割した区間の左側にある時は、左側から水を注ぐ。
    if (fx < b[mid]) {
      add(left, mid, volume, fx);
      add(mid, right, volume, fx);
    }
    //そうでない場合
    else {
      add(mid, right, volume, fx);
      add(left, mid, volume, fx);
    }
  }
  //考えるべき空間のwidth, heightを計算　x:width, z:height
  ld x = b[right] - b[left], z = min(h[left], h[right]) - height[left];
  //水の量を計算
  if (volume < x * y * z) {
    FOR(i, left, right) height[i] += volume / (x * y);
    volume = 0;
  }
  else {
    FOR(i, left, right) height[i] = min(h[left], h[right]);
    volume -= x * y * z;
  }
}

//t[i]の値が単調増加ではないため、各クエリに対して、heightの値を一度初期化する必要がある。
//t[i]秒のときの状態を一気にシュミレーションする方が効率的である。
void solve() {
  rep(i, l) {
    //初期化
    rep(j, 15) height[j] = 0;
    rep(j, m) {
      //蛇口のx座標の位置を仕切り板の左側に来るように調整。(これは、バグの発見のしやすさから行ったもので、実際は必要ない。)
      int fx = *(lower_bound(b, b + n + 1, f[j]) - 1);
      ld volume = a[j] * t[i];
      //各蛇口に対して、add関数を実行し、水を流していく。
      add(0, n + 1, volume, fx);
    }
    //観測点も、仕切り板の左側になるよう調整。
    int px = lower_bound(b, b + n + 2, p[i]) - b - 1;
    //output
    cout << height[px] << '\n';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);

  int dd;
  cin >> dd;
  //入力は特別変なことやってないのでわかると思います。
  while (dd--) {
    cin >> n;
    //水槽の端も仕切り板とみなせる。
    b[0] = 0, b[n + 1] = 100;
    h[0] = 50, h[n + 1] = 50;
    FOR(i, 1, n + 1) cin >> b[i] >> h[i];
    cin >> m;
    rep(i, m) cin >> f[i] >> a[i];
    cin >> l;
    rep(i, l) cin >> p[i] >> t[i];

    solve();
  }





  
  return 0;
}