Phineas and Ferb are playing an interesting game. They have N piles of stones numbered from 1 to N in front of them. The ith pile contains Ai stones. Both of them play turn wise and optimally with Phineas starting first.
In each turn, a player can remove any number of stones from any of the pile which has positive amount of stones left in it. A player loses when he cannot remove any stone and all piles are already empty.
You are given Q queries. Each query contains two integers integer l and r. For each query, your task is to tell winner of the game if it was only played on the piles from range l to r (both inclusive).
Note that, each query is independent from other queries and does not affect them in any way.
Input:
The first line of the input contains a single integer N denoting the number of piles.
The second line contains N space-separated integers where ith integer denotes the amount of stones in ith pile.
The third line contains an integer Q denoting the number of queries.
Next Q lines contains two single space separated integers l and r as described in the problem statement.
Output:
Print winner of each query in a separate line. Output "Phineas" if Phineas wins or "Ferb" if Ferb wins.
Constraints:
- 1≤N≤5∗105
- 1≤Ai≤109
- 1≤Q≤2∗105
- 1≤l≤r≤N
We have 3 piles initially where 1st pile has 1 stone, 2nd pile also has 1 stone and 3rd pile has 2 stones.
In 1st query, both players will play game on 1st and 2nd pile. Phineas only has a choice to remove any single stone from any one of the pile. After him, Ferb will remove the remaining stone from other pile. Now, Phineas can't remove any stone, thus making Ferb winner.
In 2st query, both players will play game on just 2nd pile having 2 stones. Phineas will remove both stones from the pile. Now, Ferb can't remove any stone, thus making Phineas winner.
