给定 $$$2n$$$ 值 $$$(a, b, c)$$$ 的元组,其中 $$$a$$$ 和 $$$b$$$ 是正整数,$$$c$$$ 是括号“(”或“)”。确切地说,$$$n$$$ 元组具有 $$$c = $$$'(',其他 $$$n$$$ 元组具有 $$$c =$$$ ')'。
要求您选择两个正值 $$$x$$$ 和 $$$y$$$($$$x > 0$$$ 和 $$$y > 0$$$;不一定是整数),并按 $$$a \cdot x + b \cdot y$$$ 的递增值对元组进行排序。如果多个元组具有相同的值,则可以将它们按任意顺序放置。
是否可以选择这样的 $$$x$$$ 和 $$$y$$$ ,以按结果顺序从元组中取出括号 $$$c$$$ 产生规则的括号序列?
正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1500$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1500$$$)。
接下来的 $$$2n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$) 和一个字符 $$$c_i$$$ ($$$c_i = $$$'(' 或 $$$c_i = $$$')')。确切地说,$$$n$$$ 元组具有 $$$c_i = $$$'(',其他 $$$n$$$ 元组具有 $$$c_i =$$$ ')'。
所有测试用例的 $$$n$$$ 总和不超过 $$$1500$$$。
输出
对于每个测试用例,如果可以选择这样的 $$$x$$$ 和 $$$y$$$ ,从元组中按结果顺序取出括号 $$$c$$$ 会产生规则的括号序列,则打印“YES”。否则,打印“NO”。
示例
输入 #1
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 (
输出 #1
YES NO NO YES
注意
在第一个测试用例中,您可以选择 $$$x = 10, y = 0.1$$$。元组的值将为 $$$10 \cdot 1 + 0.1 \cdot 4 = 10.4$$$ 和 $$$10 \cdot 2 + 0.1 \cdot 3 = 20.3$$$。因此,第一个元组将首先出现,然后是第二个元组,从而形成括号序列“()”,这是常规的。
在第二个测试用例中,您不能选择正 $$$x$$$ 和 $$$y$$$ ,这样左括号被分配的值小于或等于右括号的值。
在第四个测试用例中,您可以选择$$$x = 0.6,y = 0.55$$$。括号序列为“(()(()))”。