Дан массив \(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 4 1 2 3 2 3 1 1 2
y+ x+ x- y-
4 4 1 2 2 3 3 4 3 2
y+ y+ x- y-
4 2 2 1 4 3
y+ x+
3000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач