Interval game
- 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". KVN Team "Prima", Kursk
Little Petya loves solving problems from l to r. Today, he encountered a sequence of N piles of stones. He began to wonder: if I select all the piles numbered from l to r inclusive and play against Kolya, who will win? Naturally, Petya wants to go first. Since he has many such questions in mind, and l and r can vary significantly, a program is essential.
Input
The first line contains a natural number N (1 ≤ N ≤ 10^5) — the number of piles in the sequence. The second line contains N integers — the sizes of the piles b_i (0 ≤ b_i ≤ 10^9). The third line contains a natural number Q (1 ≤ Q ≤ 10^5) — the number of queries. The next Q lines each contain a pair of numbers 1 ≤ l_i ≤ r_i ≤ N. The piles are numbered starting from 1.
Output
Output a line where the i-th letter is the answer to the i-th query: 'P', if Petya wins, and 'V', if Kolya wins.