동전 진술

John과 Ted는 동전 결과로 이루어진 문자열을 맞히는 게임을 하고 있다.

John은 여러 개의 동전을 탁자 위에 놓는다. 그런 다음 동전을 하나씩 다시 집어 들면서, 위쪽 면이 앞면이면 P, 뒷면이면 G를 적는다. 이렇게 하면 P와 G로만 이루어진 길이 L의 무작위 문자열이 만들어진다.

그 뒤 John은 N개의 문장을 말한다. 각 문장은 다음과 같은 형태이다.

i번째 문자는 X이거나, j번째 문자는 Y이다

여기서 i와 j는 서로 다른 위치이고, X와 Y는 각각 P 또는 G 중 하나이다. John이 말한 모든 문장은 두 주장 중 적어도 하나가 참이다.

Ted는 John의 문장만 듣고, 그 문장들을 모두 참으로 만들 수 있는 문자열을 하나 찾고 싶다. 그런 문자열이 존재하면 하나 출력하고, 존재하지 않으면 없다고 판단하는 프로그램을 작성하라.

첫째 줄에 문자열의 길이 L이 주어진다 (2 <= L <= 1000).

둘째 줄에 문장의 개수 N이 주어진다 (1 <= N <= 100000).

다음 N개의 줄에는 문장 하나가 다음 형식으로 주어진다.

i X j Y

1 <= i, j <= L, i != j를 만족하며, X와 Y는 모두 P 또는 G이다.

모든 문장을 만족하는 문자열 하나를 출력한다.

그런 문자열이 존재하지 않으면 -1을 출력한다.

가능한 문자열이 여러 개일 수 있으며, 그중 아무거나 출력해도 된다.