New update is available. Click here to update.

Magic Park

Posted: 1 Jul, 2021
Difficulty: Hard


Try Problem

Bob came to a magic aqua park. In this magic aqua park, There are N props. Each prop is a non-horizontal and non-vertical segment. So when Bob falls on the segment, he starts sliding on it, and when he reaches its lowest point, he continues falling vertically. Then he can fall on another segment and so on until he reaches the water. He knows his initial X coordinate, and he is at a very high altitude. Help Bob to find his final X coordinate.

For Example:
4 2
0 1 2 2
2 4 4 5


Here, Bob will first fall on the second prop, and he will travel till endpoint 2. Then he will fall on the first prop and travel till the endpoint 0. hence the final position will be X = 0. 
Input Format:
The first line contains a single integer 'T' denoting the number of tests cases to be run. Then the test cases follow.

The first line of each test case contains two space-separated integers - initial X coordinate and N - number of segment props. 

The next N lines of each test case describe the prop each by four integers x1, y1, x2, y2 - denoting the coordinates of the leftmost and rightmost point of the prop, respectively.
 Props do not intersect or touch each other.
Output Format:
For each test case, print an integer ‘A’ denoting the final 
of Bob. 

Answers for each test case will be printed in a separate line.
You are not required to print anything; it has already been taken 
care of. Just implement the function and return the answer.
1 <= T <= 50
1 <= N <= 100
0 <= X <= 104
0 <= X1, Y1, X2, Y2 <= 10000
x1 < x2

Time Limit: 1 sec.