Крайний Банк
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Крайний банк занимается важной деятельностью — контролем биржей бипок и обнаружением потенциального мошенничества. Вам, как стажеру Крайнего Банка, поручили разработать систему, которая позволяла бы определять, является ли данный трейдер потенциальным мошенником или нет. Вы знаете, что биржа бипок работала $$$n$$$ моментов времени, в течение которых трейдер торговал на бирже.

Вам известно, что в $$$i$$$-й момент времени цена одной бипки составляла $$$a_i$$$ и трейдер продал или купил $$$|b_i|$$$ бипок по данной цене. Если $$$b_i < 0$$$, то он продал $$$-b_i$$$ бипок, а если $$$b_i > 0$$$, то купил $$$b_i$$$ бипок. На момент начала торгов у трейдера было $$$0$$$ бипок, а также известно, что к концу торгов он распродал все бипки (другими словами, сумма $$$b_i$$$ равна $$$0$$$). Также трейдер не мог уходить в минус, то есть в любой момент времени у него было неотрицательное количество бипок. Если $$$b_i = 0$$$, то в $$$i$$$-й день трейдер не продавал и не покупал бипки.

Крайний банк считает трейдера потенциальным мошенником, если каждой операции покупки одной конкретной бипки можно сопоставить в пару операцию продажи одной бипки так, что покупка произошла раньше продажи и стоимость покупки строго меньше стоимости продажи. Обратите внимание, что разным операциям покупки одной бипки должны соответствовать разные операции продажи. При этом, если две бипки были куплены в один и тот же момент времени, операции продажи для них могли произойти в разное время.

Определите, является ли данный трейдер потенциальным мошенником.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) — количество моментов времени, в течение которых трейдер торговал на бирже.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — стоимость одной бипки в $$$i$$$-й момент времени.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \leq b_i \leq 10^9$$$) — числа, характеризующие операции покупки/продажи, совершенные трейдером, в соответствии с форматом, описанным в условии.

Гарантируется, что в любой момент времени у трейдера было неотрицательное количество бипок, а также $$$b_1 + b_2 + \ldots + b_n = 0$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

Для каждого набора входных данных выведите «Yes» (без кавычек), если трейдер является потенциальным мошенником, иначе выведите «No» (без кавычек).

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Система оценки

В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.

Обозначим за $$$N$$$ сумму $$$n$$$ по всем наборам входных данных в данном тесте.

Решения, корректно работающие при $$$n \leq 7$$$, $$$t \leq 10$$$, наберут не менее $$$24$$$ баллов.

Решения, корректно работающие при $$$N \leq 3000$$$, наберут не менее $$$60$$$ баллов.

Решения, корректно работающие при $$$a_i \leq 3$$$, наберут не менее $$$28$$$ баллов.

Пример

Входные данные
4
3
2 3 2
1 1 -2
3
2 3 4
1 1 -2
5
2 3 3 3 4
1 1 -1 1 -2
2
1000000000 1000000000
1000000000 -1000000000
Выходные данные
No
Yes
Yes
No

Примечание

В первом наборе входных данных трейдер продает бипки, купленные по цене $$$2$$$ и $$$3$$$ по цене $$$2$$$. Тем самым он не выходит в плюс по каждой бипке и не является потенциальным мошенником.

Во втором наборе входных данных трейдер продает бипки, купленные по цене $$$2$$$ и $$$3$$$ по цене $$$4$$$. Тем самым он выходит в плюс по каждой бипке и является потенциальным мошенником.

В третьем наборе входных данных трейдер может продать в третий момент времени бипку, купленную по цене $$$2$$$ за $$$3$$$ и выйти по ней в плюс. После чего в пятый момент времени продать все остальные бипки и выйти по ним в плюс. Таким образом, он является потенциальным мошенником.