Дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел (нумеруемых от $$$1$$$ до $$$n$$$). Изначально все они равны нулю.
Необходимо обработать $$$q$$$ запросов $$$i$$$-й запрос состоит из двух различных целых чисел $$$x_i$$$ и $$$y_i$$$. В ходе $$$i$$$-го запроса нужно выбрать целое число $$$p$$$ (которое равно либо $$$x_i$$$, либо $$$y_i$$$) и целое число $$$d$$$ (которое равно либо $$$1$$$, либо $$$-1$$$), и присвоить $$$a_p = a_p + d$$$.
После каждого запроса каждый элемент массива $$$a$$$ должен быть неотрицательным целым числом.
Необходимо обработать все запросы таким образом, чтобы сумма всех элементов массива $$$a$$$ после последнего запроса была минимально возможной.
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 3 \cdot 10^5$$$; $$$1 \le q \le 3 \cdot 10^5$$$) — количество элементов в массиве $$$a$$$ и количество запросов соответственно.
Затем следуют $$$q$$$ строк. $$$i$$$-я из этих строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$x_i \ne y_i$$$) — описание $$$i$$$-го запроса.
Для каждого запроса выведите строку, содержащую два символа:
Если существует несколько ответов, выведите любой из них.
3 41 23 23 11 2
y+ x+ x- y-
4 41 22 33 43 2
y+ y+ x- y-
4 22 14 3
y+ x+
Название |
---|