Нім ненависників Фібоначчі 2. Петро завдає удару у відповідь!
Це завдання містить велику кількість НЕНАВИСТІ. Ми наполегливо рекомендуємо тримати подалі від екранів людей, тварин зі слабкою психікою, годуючих жінок і дітей. Адміністрація
Містер Хом'як ненавидить Фібоначчі. І не лише самого математика, а й усе, що з ним пов'язано. Особливо він ненавидить числа Фібоначчі. Нагадаємо, що числа Фібоначчі визначаються за наступним правилом:
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' — в іншому випадку.