Крайний банк занимается важной деятельностью — контролем биржей бипок и обнаружением потенциального мошенничества. Вам, как стажеру Крайнего Банка, поручили разработать систему, которая позволяла бы определять, является ли данный трейдер потенциальным мошенником или нет. Вы знаете, что биржа бипок работала $$$n$$$ моментов времени, в течение которых трейдер торговал на бирже.
Вам известно, что в $$$i$$$-й момент времени цена одной бипки составляла $$$a_i$$$ и трейдер продал или купил одну бипку по данной цене. Если $$$b_i = -1$$$, то он продал одну бипку, а если $$$b_i = 1$$$, то купил одну бипку. На момент начала торгов у трейдера было $$$0$$$ бипок, а также известно, что к концу торгов он распродал все бипки (другими словами, сумма $$$b_i$$$ равна $$$0$$$). Также трейдер не мог уходить в минус, то есть в любой момент времени у него было неотрицательное количество бипок.
Крайний банк считает трейдера потенциальным мошенником, если каждой операции покупки одной конкретной бипки можно сопоставить в пару операцию продажи одной бипки так, что покупка произошла раньше продажи и стоимость покупки строго меньше стоимости продажи. Обратите внимание, что разным операциям покупки одной бипки должны соответствовать разные операции продажи.
Определите, является ли данный трейдер потенциальным мошенником, и если является, то для каждой операции покупки выведите соответствующую ей операцию продажи.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 200\,000$$$, $$$n$$$ — чётное) — количество моментов времени, в течение которых трейдер торговал на бирже.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10$$$) — стоимость одной бипки в $$$i$$$-й момент времени.
Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$b_i = -1$$$ или $$$b_i = 1$$$) — числа, характеризующие операции покупки/продажи, совершенные трейдером, в соответствии с форматом, описанным в условии.
Гарантируется, что в любой момент времени у трейдера было неотрицательное количество бипок, а также $$$b_1 + b_2 + \ldots + b_n = 0$$$.
В первой строке выведите «Yes» (без кавычек), если трейдер является потенциальным мошенником, иначе выведите «No» (без кавычек).
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Если трейдер является потенциальным мошенником, то выведите $$$\frac{n}{2}$$$ строк, каждая из которых содержит два целых числа — момент времени, когда была совершена покупка, и момент времени, когда была совершена соответствующая продажа. Обратите внимание, что первое число в паре должно быть строго меньше второго, а также каждое число от $$$1$$$ до $$$n$$$ должно встречаться ровно один раз. Вы можете выводить пары в любом порядке.
Если существует несколько решений, выведите любое из них.
В данной задаче $$$25$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$4$$$ балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при $$$n \leq 10$$$, наберут не менее $$$24$$$ баллов.
Решения, корректно работающие при $$$n \leq 3000$$$, наберут не менее $$$60$$$ баллов.
Решения, корректно работающие при $$$a_i \leq 2$$$, наберут не менее $$$20$$$ баллов.
41 4 5 21 1 -1 -1
Yes 2 3 1 4
210 101 -1
No
62 6 9 2 6 71 1 -1 1 -1 -1
Yes 2 3 4 5 1 6
Рассмотрим первый пример:
Во втором примере трейдер не может продать бипку, купленную в момент времени $$$1$$$ по цене $$$10$$$, дороже.
Рассмотрим третий пример: