def generate_song(): s = [] for i in range(99, 0, -1): line1 = f"{i} bottle{'s' if i > 1 else ''} of beer on the wall, {i} bottle{'s' if i > 1 else ''} of beer." s.append(line1) next_num = i - 1 if i - 1 else 'no more' plural = 's' if (i - 1 != 1 and i - 1 != 0) else '' line2 = f"Take one down and pass it around, {next_num} bottle{plural} of beer on the wall." s.append(line2) s.append("No more bottles of beer on the wall, no more bottles of beer.") s.append("Go to the store and buy some more, 99 bottles of beer on the wall.") return '\n'.join(s) + '\n' H_str = "Hello, World!" song_str = generate_song() def can_split_into_h_and_song(s, h_str, song_str): len_h = len(h_str) len_song = len(song_str) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(n): if dp[i]: if i + len_h <= n and s[i:i+len_h] == h_str: dp[i+len_h] = True if i + len_song <= n and s[i:i+len_song] == song_str: dp[i+len_song] = True return dp[n] def generate_hq9_code(s): if s == H_str: return 'H' if s == song_str: return '9' if s == 'Q': return 'Q' if can_split_into_h_and_song(s, H_str, song_str): code = [] i = 0 len_h = len(H_str) len_song = len(song_str) while i < len(s): if s.startswith(H_str, i): code.append('H') i += len_h elif s.startswith(song_str, i): code.append('9') i += len_song else: return '-1' return ''.join(code) if len(s) >= 2 and s[0] == 'Q': remaining = s[1:] code_candidate = 'QH' if s.startswith(code_candidate) and remaining[len(code_candidate)-1:] == H_str: return code_candidate code_candidate = 'Q9' if s.startswith(code_candidate) and remaining[len(code_candidate)-1:] == song_str: return code_candidate if len(s) >= 2 and s.startswith('QH'): remaining = s[2:] if remaining == H_str: return 'QH' if len(s) >= 2 and s.startswith('Q9'): remaining = s[2:] if remaining == song_str: return 'Q9' return '-1' n = int(input()) s = input().strip() result = generate_hq9_code(s) print(result)