Fibonacci haters' nim 2. Peter strikes back!
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 ≥ 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 N 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 l to r 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!
Input
The first line contains 3 numbers: a, b, and N (1 ≤ a, b ≤ 20, 1 ≤ N ≤ 10^5). The second line lists the sizes of the piles b_i (1 ≤ b_i ≤ 10^6). The third line provides the number M (1 ≤ M ≤ 10^5) – the number of questions Petya will ask. The following M lines contain pairs of numbers l_i r_i (1 ≤ l_i ≤ r_i ≤ N) – the range of piles Petya suggests choosing for the next question.
Output
Output a string of M characters, where the i-th character is the answer to the i-th question: 'P', if Petya wins, and 'H' otherwise.