/* -*- coding: utf-8 -*- * * 3323.cc: No.3323 蟯ゥ莠墓弌蠑上ず繝」繝ウ繧ア繝ウ - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_M = 100000; const char hcs[] = "GCP"; /* typedef */ struct Node { Node *cs[3]; Node(): cs() {} }; /* global variables */ char s[MAX_M + 4], t[MAX_M + 4]; Node *root; /* subroutines */ inline int c2i(char c) { return (c == 'G') ? 0 : (c == 'C') ? 1 : 2; } void trie_add(int m, char s[]) { Node *u = root; for (int i = 0; i < m; i++) { int ci = c2i(s[i]); if (u->cs[ci] == nullptr) u->cs[ci] = new Node(); u = u->cs[ci]; } } bool trie_calc(int m, char t[]) { Node *u = root; for (int i = 0; i < m; i++) { if (u == nullptr) t[i] = 'G'; else { int ci = 0; while (u->cs[ci] != nullptr) ci++; if (ci >= 3) return false; ci = (ci + 1) % 3; t[i] = hcs[ci]; u = u->cs[ci]; } } t[m] = '\0'; return (u == nullptr); } /* main */ int main() { int n, m; scanf("%d%d", &n, &m); root = new Node(); for (int i = 0; i < n; i++) { scanf("%s", s); trie_add(m, s); } if (trie_calc(m, t)) puts(t); else puts("-1"); return 0; }