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

Дан массив $$$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$$$-го запроса.

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

Для каждого запроса выведите строку, содержащую два символа:

  • первый символ должен быть x, если вы выбрали $$$p=x_i$$$, или y, если вы выбрали $$$p=y_i$$$;
  • второй символ должен быть +, если вы выбрали $$$d=1$$$, или -, если вы выбрали $$$d=-1$$$.

Если существует несколько ответов, выведите любой из них.

Примеры
Входные данные
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+