F. Социальная сеть
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пётр работает в рекламном отделе Берляндской социальной сети БК. Руководство БК решило добавить таргетированную рекламу в свою социальную сеть. Для эффективного показа таргетированной рекламы Петру дали задание собрать следующую информацию о каждом пользователе: пол пользователя и факт наличия у него детей.

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

Пётр имеет доступ к части базы данных соцсети БК. Пользователи в базе представлены их уникальными идентификаторами (id) — целыми числами от 1 до n. Все записи базы данных, доступные Петру, можно отнести к одному из следующих четырёх типов:

  1. пользователь c id xi указал, что пользователь с id yi является его матерью;
  2. пользователь с id xi указал, что пользователь с id yi является его отцом;
  3. пользователь с id xi указал, что пользователь с id yi является одним из двух его родителей, однако не указал, кем именно;
  4. пользователь с id xi указал, что пользователь с id yi находится с ним в браке.

Берляндия находится в параллельной вселенной, а потому там действуют дополнительные правила относительно вступления в брак и рождения детей:

  • вступить в брак можно только один раз в жизни, развод не предусмотрен;
  • лица, имеющие общего родителя (отца или мать), не могут вступать в брак;
  • дети у берляндцев могут появиться только в браке;
  • брак возможен только между людьми противоположного пола.

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

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

В первой строке следуют два числа n и m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) — количество пользователей БК и количество записей в базе данных, доступных Петру.

В следующих m строках следуют записи базы данных, по одной в строке. Каждая запись представлена тремя числами ti, xi, yi (1 ≤ ti ≤ 4, 1 ≤ xi, yi ≤ n, xi ≠ yi) — тип записи и два id пользователей социальной сети БК, в соответствии с описанными выше правилами хранения записей в базе данных.

Гарантируется, что записи в базе данных корректны и не противоречат друг другу.

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

Выведите n строк. В i-ю строку выведите два символа ai и bi через пробел. Если пользователь с id i мужского пола, ai должно быть равно 'm', если женского — 'f', а если определить пол по доступной информации невозможно, ai должно быть равно '?'. Если у пользователя с id i точно есть дети, bi должно быть равно '+'. В противном случае bi должно быть равно '-'.

Примеры
Входные данные
5 4
1 3 1
4 3 4
3 3 2
2 4 5
Выходные данные
f +
m +
? -
? -
m +
Входные данные
4 2
4 1 3
3 4 3
Выходные данные
? +
? -
? +
? -
Входные данные
3 2
4 1 2
1 3 2
Выходные данные
m +
f +
? -
Примечание

В первом примере по имеющимся данным из базы данных можно определить следующую информацию:

  • пользователь с id=1 женского пола и у этого пользователя есть ребёнок — пользователь с id=3
  • пользователь с id=2 мужского пола и у этого пользователя есть ребёнок — пользователь с id=3
  • пользователь с id=5 мужского пола и у этого пользователя есть ребёнок — пользователь с id=4

Невозможно однозначно определить пол пользователей с id=3 и с id=4, а также невозможно определить факт наличия детей у этих пользователей.