Forge Cycle Splice Check

A boutique blacksmith's workshop keeps a single running log for every batch of blades it tempers. Each completed tempering cycle is written into the log as one unbroken three-letter block: H for heating the blade, Q for quenching it, and T for the final temper — always in that exact order, always as the block HQT. Because several apprentices can be mid-cycle on the same batch at once, a finished cycle's block gets spliced into whatever the log already looks like at that moment, and the apprentice doing the splicing is free to insert it at any position along the current log — at the front, at the back, or wedged in between letters already there. The log starts out completely empty and grows by zero or more such splices.

You are handed the final log for a batch. Determine whether it is possible that the log arose this way: that is, whether it can be built up from the empty string by repeatedly inserting the block HQT at some position, any number of times.

Input format

A single line containing the string s.

Output format

Print true if s could have arisen from this splicing process, or false otherwise.

Constraints

• 1 <= length of s <= 50000
• s consists only of the characters H, Q, and T.

HHQTQT

true

HQTTQH

false