eolymp
bolt
Try our new interface for solving problems
Problems

Fibonacci haters` nim 2. Peter strikes back!

Fibonacci haters` nim 2. Peter strikes back!

Time limit 2 seconds
Memory limit 256 MiB

Даная задача содержит зашкаливающее количество НЕНАВИСТИ. Мы настоятельно рекомендуемубрать от мониторов людей, животных со слабойпсихикой, кормящих женщин и детей.Администрация

Мистер Хамстер ненавидит Фибоначчи. И не только самого математика, но и всё, что с ним связано. Особенно он ненавидит числа Фибоначчи. Напомним, что числа Фибоначчи задаются по следующему правилу:

f_0 = a;f_1 = b;f_i = f_{i-1} + f_{i-2}, i2

А ещё мистер Хамстер обожает играть в ним. Он даже проводит соревнования по ниму у себя в сарае. И, конечно же, он не потерпит в своём доме ход, на котором кто-то берёт число камней, равное какому-то из чисел Фибоначчи, пусть даже этот ход принесёт победу.

Сегодня мистер Хамстер решил сыграть с маленьким Петей – он разложил на столе N кучек нима и предоставил мальчику право первого хода. Но мистер Хамстер забыл, что у Пети есть супер-способность постоянно спрашивать: "А если я выберу кучки с номерами от l до r включительно, и мы будем играть, кто победит?" Поскольку вопросов очень много, а мистер Хамстер ненавидит программирование из-за детской психологической травмы (учитель информатики заставлял его вычислять числа Фибоначчи), то отвечать на вопросы придётся вам. Спешите, а то мистер Хамстер возненавидит и вас!

Input data

В первой строке следуют 3 числа: a, b и N (1a, b20, 1N10^5). Вторая строка содержит размеры кучек b_i (1b_i10^6). В третьей строке находится число M (1M10^5) – количество вопросов Пети. Последующие M строк содержат пары чисел l_i r_i (1l_ir_iN) – промежуток, на котором предлагает выбрать кучки Петя во время очередного вопроса.

Output data

Выведите строку из M символов, в которой i-й символ является ответом на i-й вопрос – 'P', если побеждает Петя и 'H' – в противном случае.

Examples

Input example #1
2 1 5
1 2 3 4 5
3
1 5
1 4
2 5
Output example #1
PHP
Source Летняя школа Севастополь 2013, Волна 1, День 7 - Экзамен