310618: CF1860F. Evaluate RBS

F. Evaluate RBStime limit per test10 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given $2n$ tuples of values $(a, b, c)$, where $a$ and $b$ are positive integers and $c$ is a bracket '(' or ')'. Exactly $n$ tuples have $c = $'(' and the other $n$ tuples have $c =$ ')'.

You are asked to choose two positive values $x$ and $y$ ($x > 0$ and $y > 0$; not necessarily integers) and sort the tuples in the increasing value of $a \cdot x + b \cdot y$. If several tuples have the same value, you can place them in any order among themselves.

Is it possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence?

A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence.

Input

The first line contains a single integer $t$ ($1 \le t \le 1500$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 1500$).

The $i$-th of the next $2n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 10^6$) and a character $c_i$ ($c_i = $'(' or $c_i = $')'). Exactly $n$ tuples have $c_i = $'(' and the other $n$ tuples have $c_i =$ ')'.

The sum of $n$ over all testcases doesn't exceed $1500$.

Output

For each testcase, print "YES" if it's possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence. Otherwise, print "NO".

ExampleInput

4
1
1 4 (
2 3 )
1
1 2 )
3 4 (
4
16 5 (
12 3 (
19 6 )
4 10 )
3 10 )
19 11 (
19 7 )
7 14 (
4
16 8 (
11 9 )
20 10 )
20 19 )
2 13 (
18 7 (
15 19 )
5 6 (

Output

YES
NO
NO
YES

Note

In the first testcase, you can choose $x = 10, y = 0.1$. The values for tuples will be $10 \cdot 1 + 0.1 \cdot 4 = 10.4$ and $10 \cdot 2 + 0.1 \cdot 3 = 20.3$. Thus, the first tuple will go first, then the second one, making the bracket sequence "()", which is regular.

In the second testcase, you can't choose positive $x$ and $y$ such that the opening brackets gets assigned a value less or equal to the value of the closing bracket.

In the fourth testcase, you can choose $x = 0.6, y = 0.55$. The bracket sequence is "(()(()))".

题目大意：
给定2n个三元组(a, b, c)，其中a和b是正整数，c是左括号“(”或右括号“)”。恰好有n个三元组的c为“(”，其余n个三元组的c为“)”。要求选择两个正数x和y（x>0和y>0，不一定是整数），使得按a*x + b*y的升序对三元组进行排序。如果几个三元组具有相同的值，则它们之间的顺序可以任意放置。

询问是否可以选择这样的x和y，使得从结果顺序中的三元组取出的括号c构成一个正规括号序列。

正规括号序列是指可以通过在序列的原始字符之间插入“1”和“+”来转换成正确算术表达式的括号序列。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤1500）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤1500）。
接下来的2n行中的第i行包含两个整数a_i和b_i（1≤a_i, b_i≤10^6）和一个字符c_i（c_i为“(”或“)”）。恰好n个三元组的c_i为“(”，其余n个三元组的c_i为“)”。
所有测试用例的n之和不超过1500。

输出：
对于每个测试用例，如果可以选择这样的x和y，则输出“YES”，否则输出“NO”。题目大意： 给定2n个三元组(a, b, c)，其中a和b是正整数，c是左括号“(”或右括号“)”。恰好有n个三元组的c为“(”，其余n个三元组的c为“)”。要求选择两个正数x和y（x>0和y>0，不一定是整数），使得按a*x + b*y的升序对三元组进行排序。如果几个三元组具有相同的值，则它们之间的顺序可以任意放置。 询问是否可以选择这样的x和y，使得从结果顺序中的三元组取出的括号c构成一个正规括号序列。 正规括号序列是指可以通过在序列的原始字符之间插入“1”和“+”来转换成正确算术表达式的括号序列。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤1500）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤1500）。 接下来的2n行中的第i行包含两个整数a_i和b_i（1≤a_i, b_i≤10^6）和一个字符c_i（c_i为“(”或“)”）。恰好n个三元组的c_i为“(”，其余n个三元组的c_i为“)”。 所有测试用例的n之和不超过1500。 输出： 对于每个测试用例，如果可以选择这样的x和y，则输出“YES”，否则输出“NO”。