Codeforces Round #156 (Div. 2)E. Furlo and Rublo and Game【SG】

E. Furlo and Rublo and Game

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Furlo and Rublo play a game. The table has n piles of coins lying on it, the i-th pile has ai coins. Furlo and Rublo move in turns, Furlo moves first. In one move you are allowed to:

  • choose some pile, let's denote the current number of coins in it as x;
  • choose some integer y (0 ≤ y < xx1 / 4 ≤ y ≤ x1 / 2) and decrease the number of coins in this pile to y. In other words, after the described move the pile will have y coins left.

The player who can't make a move, loses.

Your task is to find out, who wins in the given game if both Furlo and Rublo play optimally well.

Input

The first line contains integer n (1 ≤ n ≤ 77777) — the number of piles. The next line contains n integers a1, a2, ..., an(1 ≤ ai ≤ 777777777777) — the sizes of piles. The numbers are separated by single spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.

Output

If both players play optimally well and Furlo wins, print "Furlo", otherwise print "Rublo". Print the answers without the quotes.

Examples

input

Copy

1
1

output

Copy

Rublo

input

Copy

2
1 2

output

Copy

Rublo

input

Copy

10
1 2 3 4 5 6 7 8 9 10

output

Copy

Furlo

 

 

分析:首先枚举出前几项的SG函数值,然后通过尺取法算出后面的SG函数值。

[1,3]的SG为0,SG[4]的函数值为1,考虑左端点l=x^(1/4)和右端点r=x^(1/2),当且仅当r<4时sg才为1,所以算出sg为1的区间表示为[4,15],以此类推。由于区间都是平方关系,所以直接手算就可以了。

 

    #include "bits/stdc++.h"
    
    using namespace std;
    int sg(long long x)
    {
        if(x<=3)return 0;
        if(x<=15)return 1;
        if(x<=81)return 2;
        if(x<=6723)return 0;
        if(x<=50625)return 3;
        if(x<=2562991875LL)return 1;
        else return 2;
    }
    int main() {
        int n;
        cin >> n;
        int ans=0;
        for (int i = 1; i <= n; ++i) {
            long long x;cin>>x;
            ans^=sg(x);
        }
        if(ans)puts("Furlo");
        else puts("Rublo");
    }

 

上一篇:python笔记:5.1.1matplotlib_函数绘图_直线


下一篇:LeetCode Weekly 156