타입 차트

당신은 Nudgémon이라는 게임을 하고 있다. 이 게임의 핵심 요소는 Nudgémon 전투다. 전투에서 두 플레이어는 각자 원하는 Nudgémon을 하나씩 내보낸 뒤 번갈아 상대 Nudgémon을 공격한다.

각 공격에는 타입이 있고(1부터 n 사이의 정수), 상대 Nudgémon은 타입을 하나 또는 두 개 가진다. 타입 조합에 따라 공격이 주는 피해량이 달라진다.

공격 타입 i가 단일 타입 j인 Nudgémon에 맞으면 피해 배율은 $a(i, j)$다. 여기서 $a$는 값이 $\{0, 0.5, 1, 2\}$에 속하는 타입 상성표다. 이중 타입 j, k인 Nudgémon에 맞으면 피해 배율은 $a(i, j) \times a(i, k)$다.

게임은 피해 배율 $v$에 따라 다른 메시지를 출력한다.

당신은 이 게임이 처음이라 상성표 $a$가 어떻게 생겼는지 모른다. 타입 1의 공격으로 여러 Nudgémon을 공격했을 때 나온 출력을 관찰했고, 이 관찰과 일치하는 $a$의 첫 번째 행을 복원하려 한다.

첫 줄에 두 정수 n과 m이 주어진다($1 \le n \le 10^5$, $1 \le m \le 10^5$). n은 타입의 수, m은 관찰 횟수다.

이어지는 m개의 줄에는 정수 i, j와 문자 c가 주어진다($1 \le i, j \le n$, c는 x, -, =, + 중 하나). c는 타입 i와 j를 가진 Nudgémon을 공격했을 때 관찰된 결과다. i = j이면 그 Nudgémon의 타입은 하나뿐이다.

길이 n의 문자열을 한 줄에 출력한다. i번째 문자는 타입 1의 공격으로 타입 i인 Nudgémon을 공격했을 때의 결과다. 가능한 해가 여러 개면 아무거나 출력해도 된다. 해가 존재함이 보장된다.