ANTTT - The Ant

There are n sticks lying on the ground. The Ant can move only along the sticks. It can go from one stick to another only if the sticks intersect or touch each other. Help the Ant find out if it can reach the stick y from the stick x.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. The first line of each test contains two integers n and m - the number of stick and the number of queries. Next n lines contain four integers Ax, Ay, Bx, By - the coordinates of the endpoints of a stick. You may consider stick to be straight segment on a plane. The next m lines contain two integers each x and y which are the queries.

Constraints

1 <= t <= 100
1 <= n, m <= 1000
-10000 <= Ax, Ay, Bx, By <= 10000
1 <= x, y <=

Output

For each query print "YES" if the Ant can reach the stick number y from the stick number x, otherwise print "NO".

Example

Input:
2
3 3
1 3 4 3
3 4 3 1
3 1 5 1
1 2
1 3
2 2
3 3
1 1 3 1
2 1 3 1
3 2 4 1
1 2
1 3
2 3 Output: YES
YES
YES
YES
NO
NO

Added by:Spooky
Date:2009-06-02
Time limit:1.111s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Advancement Spring 2009, http://sevolymp.uuuq.com/
author: elmariachi1414

hide comments
2020-06-02 17:50:38
my first geometry problem :)
2020-01-21 11:18:30
Excellent problem. Pythonists must use PyPy here.
2019-08-24 20:16:38
Do not let precision error, get in way of AC.
2019-01-11 11:51:46
Union find Ac in 1 go.
2018-12-16 22:43:19
Is there any better way to form intersect function? Except that of orientation.
2018-06-01 11:30:56
How is it an "YES" for 1 3 4 3 and 3 1 5 1? They are parallel, aren't they?
2018-01-21 12:01:23
got ac in one go :D
2016-05-02 16:56:44
yep did it by union find ..gets accepted..good one..!!



Last edit: 2016-05-03 09:18:59
2016-01-25 11:19:24 Deepak
don't know ..what was wrong with my first submission..just changed int to long long int ..union find.nice one..
2014-05-27 18:57:09 Rishav Goyal
@Sppoky : i think i have covered each & every case , WA, could u plese give me some tricky case ?
line intersect function is also handmade :P :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.