UVA 833

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;

class L {
public:
    ll x1,y1,x2,y2,c;

    double pry(pair<ll,ll> p) {
        if((p.first == x1 && p.second == y1) || (p.first == x2 && p.second == y2))
            return -1;
        double py = ((y2-y1)*p.first+c)/(1.0*(x2-x1));
        if(py+EPS >= min(y1,y2) && py-EPS <= max(y1,y2) && py < p.second)
            return py;
        else
            return -1;
    }

    pair<ll,ll> nxt() {
        if(y1 < y2) {
            return {x1,y1};
        }
        return {x2,y2};
    }
};

vector<L> lines;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while(t--) {
        lines.clear();
        int np;
        cin >> np;
        for(int i = 0; i < np; i++) {
            L lc;
            cin >> lc.x1 >> lc.y1 >> lc.x2 >> lc.y2;
            lc.c = lc.y1*(lc.x2-lc.x1)-(lc.y2-lc.y1)*lc.x1;
            lines.push_back(lc);
        }
        int ns;
        cin >> ns;
        for(int i = 0; i < ns; i++) {
            pair<ll,ll> curr;
            cin >> curr.first >> curr.second;
            while(true) {
                double py = -1;
                int py_idx = -1;
                for(int j = 0; j < np; j++) {
                    double curry = lines[j].pry(curr);
                    if(curry > py) {
                        py_idx = j;
                        py = curry;
                    }
                }
                if(py_idx != -1) {
                    curr = lines[py_idx].nxt();
                }
                else {
                    cout << curr.first << "\n";
                    break;
                }
            }
        }
        if(t) {
            cout << "\n";
        }
    }
    return 0;
}