F. Convex Hull
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$n$$$ quadratic inequalities, each of the form

$$$$$$ a_i x^2 + b_i x + c_i \gt 0 $$$$$$

It is guaranteed that $$$a_i \lt 0$$$ for every $$$1 \le i \le n$$$.

Determine whether there is an integer $$$x$$$ satisfying all $$$n$$$ inequalities simultaneously.z

Input

The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \times 10^5$$$), the number of inequalities.

Each of the next $$$n$$$ lines contains three integers $$$a_i,b_i,c_i$$$ ($$$-10^5 \le a_i \le -1$$$, $$$-10^5 \le b_i,c_i \le 10^5$$$), the coefficients of the $$$i$$$-th inequality.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output YES if such an integer $$$x$$$ exists, or NO otherwise.

The answer is case-insensitive; for example, yes, YES, Yes, and YeS are all accepted as affirmative answers.

Example
Input
5
2
-1 0 4
-1 4 -3
3
-1 100000 0
-1 202 10000
-2 400 19998
2
-1 2 0
-1 0 -1
2
-100000 0 100000
-1 0 4
2
-1 2 0
-1 4 -3
Output
NO
YES
NO
YES
NO
Note

Sample 1 Explanation

In the fourth test case, $$$x=0$$$ satisfies both inequalities, so an integer solution exists.