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