\textit{Даная задача содержит зашкаливающее количество НЕНАВИСТИ. Мы настоятельно рекомендуем убрать от мониторов людей, животных со слабой психикой, кормящих женщин и детей.} Администрация Мистер Хамстер ненавидит Фибоначчи. И не только самого математика, но и всё, что с ним связано. Особенно он ненавидит числа Фибоначчи. Напомним, что числа Фибоначчи задаются по следующему правилу: \textbf{f_0 = a};\textbf{ f_1 = b};\textbf{ f_i = f_\{i-1\} + f_\{i-2\}}, \textbf{i} ≥ \textbf{2} А ещё мистер Хамстер обожает играть в ним. Он даже проводит соревнования по ниму у себя в сарае. И, конечно же, он не потерпит в своём доме ход, на котором кто-то берёт число камней, равное какому-то из чисел Фибоначчи, пусть даже этот ход принесёт победу. Сегодня мистер Хамстер решил сыграть с маленьким Петей -- он разложил на столе \textbf{N} кучек нима и предоставил мальчику право первого хода. Но мистер Хамстер забыл, что у Пети есть супер-способность постоянно спрашивать: "\textit{А если я выберу кучки с номерами от }\textit{\textbf{l}}\textit{ до }\textit{\textbf{r}}\textit{ включительно, и мы будем играть, кто победит?}" Поскольку вопросов очень много, а мистер Хамстер ненавидит программирование из-за детской психологической травмы (учитель информатики заставлял его вычислять числа Фибоначчи), то отвечать на вопросы придётся вам. Спешите, а то мистер Хамстер возненавидит и вас! \InputFile В первой строке следуют \textbf{3} числа: \textbf{a}, \textbf{b} и \textbf{N} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}). Вторая строка содержит размеры кучек \textbf{b_i} (\textbf{1} ≤ \textbf{b_i} ≤ \textbf{10^6}). В третьей строке находится число \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{10^5}) -- количество вопросов Пети. Последующие \textbf{M} строк содержат пары чисел \textbf{l_i r_i} (\textbf{1} ≤ \textbf{l_i} ≤ \textbf{r_i} ≤ \textbf{N}) -- промежуток, на котором предлагает выбрать кучки Петя во время очередного вопроса. \OutputFile Выведите строку из \textbf{M} символов, в которой \textbf{i}-й символ является ответом на \textbf{i}-й вопрос -- '\textbf{P}', если побеждает Петя и '\textbf{H}' -- в противном случае.