Fibonacci haters' nim 2. Peter strikes back!#5919
This task contains a significant amount of HATRED. We strongly advise keeping individuals with sensitive dispositions, nursing mothers, and children away from the screens. Administration
Mr. Hamster has a strong dislike for Fibonacci. It's not just the mathematician himself that he detests, but everything related to him, especially Fibonacci numbers. To remind you, Fibonacci numbers are defined by the following rules:
f_0 = a; f_1 = b; f_i = f_{i-1} + f_{i-2}, i \geq 2
In addition, Mr. Hamster is fond of playing Nim. He even organizes Nim tournaments in his barn. Naturally, he refuses to allow any move in his house where someone takes a number of stones equal to any Fibonacci number, even if it would lead to victory.
Today, Mr. Hamster has decided to play with little Petya. He set up piles for a game of Nim on the table and allowed Petya to make the first move. However, Mr. Hamster overlooked the fact that Petya has a knack for persistently asking: "What if I choose piles numbered from to inclusive, and we play, who will win?" Given the multitude of questions, and Mr. Hamster's aversion to programming due to a childhood trauma (his computer science teacher forced him to calculate Fibonacci numbers), you are tasked with answering these questions. Act quickly, or Mr. Hamster might end up disliking you too!
The first line contains numbers: , , and (1 \leq a, b \leq 20, 1 \leq N \leq 10^5). The second line lists the sizes of the piles b_i (1 \leq b_i \leq 10^6). The third line provides the number (1 \leq M \leq 10^5) – the number of questions Petya will ask. The following lines contain pairs of numbers l_i r_i (1 \leq l_i \leq r_i \leq N) – the range of piles Petya suggests choosing for the next question.
Output a string of characters, where the -th character is the answer to the -th question: 'P', if Petya wins, and 'H' otherwise.
Example 1