Evaluate RBS

现有 $2n$ 个形如 $(a, b, c)$ 的三元组，其中 $a, b$ 均为正整数， $c$ 是字符 `(` 或 `)`（左圆括号或右圆括号)。其中恰有 $n$ 个三元组的 $c$ 为 `(`，另外 $n$ 个为 `)`。 对于两个正实数 $x,y$ ，记一个三元组的特征值为 $\lambda = ax+by$ 。你需要选择 $x,y$ 并对三元组按其特征值升序排序。若多个三元组的特征值相同，可以选择随意排列。 问，是否存在一种选法，使得排序后的序列能让 $c$ 组成一个合法的括号序列。 ### 输入格式： 第一行一个整数 $t(1\leq t \leq 1500)$ 表示有 $t$ 组数据。 接下来的每组数据，第一行一个整数 $n(1\leq t \leq 1500)$ 表示有 $2n$ 个三元组。 每组数据的第 $i$ 行输入 $a_i,b_i,c_i$ 并用空格分割。三个参数的意义见上，其中 $1 \leq a,b\leq 10^6$ 且 $c$ 是一个字符。 输入数据一定满足 $n$ 个三元组的 $c$ 为 `(`，另外 $n$ 个为 `)`。 ### 输出格式 对于每组数据，每行输出 `YES` 或 `NO` 表示是否存在合法的解。

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.

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 $ .

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".

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 (

YES
NO
NO
YES

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 "(()(()))".