F. Вычисляем ПСП
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы $$$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$$$).

В $$$i$$$-й из следующих $$$2n$$$ строк записаны два целых числа $$$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$$$.

Выходные данные

На каждый набор входных данных выведите «YES», если возможно выбрать такие значения $$$x$$$ и $$$y$$$, что, взяв скобки $$$c$$$ из наборов в полученном порядке, мы получим правильную скобочную последовательность. Иначе выведите «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
Примечание

В первом наборе входных данных можно выбрать $$$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$$$. Скобочная последовательность будет «(()(()))».