The famous joke programming language HQ9+ has only 4 commands. In this problem we will explore its subset — a language called HQ...


-----Input-----

The only line of the input is a string between 1 and 10^6 characters long.


-----Output-----

Output "Yes" or "No".


-----Examples-----
Input
HHHH

Output
Yes

Input
HQHQH

Output
No

Input
HHQHHQH

Output
No

Input
HHQQHHQQHH

Output
Yes



-----Note-----

The rest of the problem statement was destroyed by a stray raccoon. We are terribly sorry for the inconvenience.

Source: codeforces | Difficulty: VERY_HARD
Tags: Constructive algorithms


Solutions:
a = input()
b = []
h = ''
c = 0
for i in a:
	if i == 'Q':
		c += 1
if c == 0:
	print('Yes')
	return
r = -1
for i in range(1001):
	if i * i == c:
		r = i
		break
if r == -1:
	print('No')
	return
h = [a.split('Q')[0], a.split('Q')[-1]]
c = [len(h[0]), len(h[1])]
if c[0] % 2 != 0 or c[1] % 2 != 0:
	print('No')
	return
c[0] //= 2
c[1] //= 2
resp = ''
i = c[0]
while True:
	if i >= len(a):
		break
	if r == 0 and a[i] == 'Q':
		break
	resp += a[i]
	if r == 0 and a[i] == 'H':
		c[1] -= 1
	if c[1] == 0 and r == 0:
		break
	if a[i] == 'Q':
		r -= 1
	if r == -1:
		print('No')
		return
	i += 1

def hq(a):
	resp = ''
	for i in a:
		if i == 'H':
			resp += 'H'
		else:
			resp += a
	return resp
if a == hq(resp):
	print('Yes')
else:
	print('No')


from collections import Counter
import re

def issquare(n):
	return round(n ** 0.5) ** 2 == n

def check_orig(code):
	counts = Counter(code)
	orig = ''
	if not issquare(counts['Q']):
		return ''
	nq = round(counts['Q'] ** 0.5)
	if counts['H'] % (nq + 1) != 0:
		return ''
	nh = counts['H'] // (nq + 1)
	st = 0
	while st < len(code) and code[st] == 'H':
		st += 1
	if st % 2 != 0:
		return ''
	orig += 'H' * (st // 2)
	if st == len(code):
		return orig * 2
	end = -1
	while code[end] == 'H':
		end -= 1
	if end % 2 != 1:
		return ''
	orig_end = 'H' * (abs(end + 1) // 2)
	qcount = 0
	while qcount < nq:
		if st >= len(code):
			return ''
		orig += code[st]
		if code[st] == 'Q':
			qcount += 1
		st += 1
	orig += orig_end
	return orig

def is_real(code, orig):
	ci = 0
	l = len(orig)
	for (oi, letter) in enumerate(orig):
		if letter == 'H':
			if code[ci] != letter:
				return False
			ci += 1
		elif letter == 'Q':
			if code[ci:ci + l] != orig:
				return False
			ci += l
	return ci == len(code)
code = input()
orig = check_orig(code)
if not orig:
	print('No')
elif is_real(code, orig):
	print('Yes')
else:
	print('No')


import sys
s = input()
qc = s.count('Q')
qs = int(qc ** 0.5)
hc = s.count('H')
if qs == 0:
	print('Yes')
	return
if not qc == qs ** 2:
	print('No')
	return
if not hc % (qs + 1) == 0:
	print('No')
	return
t = s.split('Q')
pre = len(t[0]) // 2
suf = 0 if len(t) == 1 else len(t[-1]) // 2
a = ['H' * pre] + t[1:qs] + ['H' * suf]
o = [c for c in 'Q'.join(a)]
g = []
for c in o:
	if c == 'H':
		g += ['H']
	else:
		g += o
print('Yes' if ''.join(g) == s else 'No')