Setting

Nature: that which wants to kill you in Australia, but can look beautiful on occasion. In this assignment, we're concerned with water falls, which usually fall into the latter category.

Assume a number of line segments, \(P_1\), \(P_2\), and \(P_3\). Further assume these to represent the side view of a number of slopes. Finally assume a water source point \(S_a\). Water falls (vertically) from the source point, possibly onto one of the line segments. Whether the water will continue rightwards or leftwards depends on the slope's angle, since water will always rush towards the lower of the slope's two end points. Once it reaches the end point, it falls from the slope, again vertically (we assume that there is no such thing as inertia). It either falls onto another slope, thus repeating the whole process, or to the ground.

Given a number of line segments and a list of source points, your assignment is to determing the x coordinates of the points on the ground where the water will end up. You can assume that no two x coordinates are the same, that is: all source and end points have distinct end coordinates. Also, assume that for every slope it holds that its end points have different y coordinates.

Input

The input begins with a single positive integer on a line by itself that indicates the number of test cases to follow, each preceded by a blank line.

Each test case starts with the number \(l\) of line segments. The following \(l\) lines contain the coordinates of the end points \(x_1, y_1, x_2, y_2 \in \mathbb{N}\) of the corresponding segment, separated by single spaces. The next line contains the number of source points \(s\). The following \(s\) lines contain the coordinates \(x, y \in \mathbb{N}\) of the corresponding source point, separated by single spaces.

Output

For each test case, the output consists of \(s\) lines, each giving the x coordinate of the point on the ground where the water originating at the corresponding source point ended up. The output for two consecutive test cases is to be separated by a blank line.

Sample Input

1

4
14 7 3 4
11 13 16 11
1 10 6 7
2 1 4 3
3
10 4
14 14
2 13

Sample Output

10
16
2

This is challenge 833 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (1 vote)
Average test runtime 0.40
Points (changes over time) 10
Tried by 3 users
Solved by 3 users

Global ranking

# Name Runtime Points worth
1 Mac 0.39 10
2 Sk√łgland 0.40 10
3 Dark 0.40 10