Interval game#5876
- Why do you have a bearded man drawn on "V" with "Kolya" written on it? - "V" stands for "Vendetta"... Don't ask, it's personal. "Alphabet". Student comedy team "Prima", Verdan
Little Petya loves solving problems from to . Today, he encountered a sequence of Nim piles. He began to wonder: if I select all the Nim piles numbered from to inclusive and play against Kolya, who will win? Naturally, Petya wants to go first. Since he has many such questions in mind, and and can vary significantly, a program is essential.
The first line contains a natural number (1 \leq N \leq 10^5) — the number of Nim piles in the sequence. The second line contains integers — the sizes of the Nim piles b_i (0 \leq b_i \leq 10^9). The third line contains a natural number (1 \leq Q \leq 10^5) — the number of queries. The next lines each contain a pair of numbers 1 \leq l_i \leq r_i \leq N. The Nim piles are numbered starting from .
Output a line where the -th letter is the answer to the -th query: 'P', if Petya wins, and 'V', if Kolya wins.
Example 1