Interval game
- Почему у Вас на "В" нарисован какой-то бородатый мужик и написано "Коля"? - "В" значит "Вендетта"… Не спрашивайте, это личное."Азбука". Команда КВН "Прима", Курск
Маленький Петя очень любит задачи от l до r. Сегодня ему попалась на глаза очередь из N кучек нима. Он стал задаваться вопросами: а если я выберу все кучки с номерами от l до r включительно и буду играть с Колей, кто выиграет? Конечно же, Петя хочет ходить первым. Поскольку таких вопросов у него в голове очень много, а l и r в них могут сильно различаться, то без программы тут никак не обойтись.
Входные данные
Первая строка содержит натуральное число N (1 ≤ N ≤ 10^5) – количество кучек в очереди. Вторая строка содержит N целых чисел – размеры кучек b_i (0 ≤ b_i ≤ 10^9). В третьей строке находится натуральное число Q (1 ≤ Q≤ 10^5) – количество запросов. Далее Q строк содержат пары чисел 1 ≤ l_i ≤ r_i ≤ N. Кучки нумеруются с 1.
Выходные данные
Выведите строку, i-я буква которой является ответом на i-й запрос: 'P', если побеждает Петя и 'V', если побеждает Коля.