CFCF2180H1.Bug Is Feature (Unconditional Version)

省选/NOI-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

这是该问题的无条件版本。与其它版本的区别在于,本题中没有“公差不减”的限制。只有在你解决了该问题的全部版本后才能进行 Hack。

注意,两个版本都不一定更容易,可以独立解答。

Bug 和 Feature 正沉浸在一种名为 Sequence 的游戏里。在这种特殊的 Sequence 游戏中,一个序列以三个正整数 a<b<cxa < b < c \le x 开始,且它们组成等差数列(即 ba=cbb-a=c-b)。每一回合,玩家可以任选 aabbcc 之一,将其增加一个正整数。操作后,三数必须仍然组成某个等差数列,顺序可以发生变化。此外,aabbcc 都不能超过 xx

他们不满足于传统 Sequence 游戏,于是决定同时进行 nn 组 Sequence 游戏。对于第 ii 组游戏,会给出五个数 ai<bi<ciliria_i < b_i < c_i \le l_i \le r_i。对于每个 x[li,ri]x\in[l_i, r_i],他们都要玩一次以 ai<bi<cixa_i < b_i < c_i \le x 为起始的游戏(总共 i=1n(rili+1)\sum_{i=1}^n(r_i-l_i+1) 个游戏)。轮流进行,每回合玩家任选某个尚未结束的游戏走一步,Bug 先手,Feature 后手。无法继续操作的玩家判负。

现在,问题是:如果双方都采用最优策略,谁会获胜?

输入格式

每个测试点包含多组数据。第一行为测试组数 t (1t105)t\ (1\le t\le 10^5)
每组测试的第一行是一个整数 n (1n2×105)n\ (1\le n\le 2\times 10^5)——表示想要玩的游戏组数。

接下来 nn 行,每行包含五个整数 ai,bi,ci,li,ri (1ai<bi<ciliri1018)a_i, b_i, c_i, l_i, r_i\ (1\le a_i < b_i < c_i \le l_i \le r_i \le 10^{18}),表示第 ii 组的参数。其中 aia_ibib_icic_i 组成等差数列(即 cibi=biaic_i-b_i=b_i-a_i)。

所有测试组的 nn 之和不超过 2×1052\times 10^5

输出格式

对于每组测试,若 Bug 获胜,输出 Bug\mathtt{Bug};否则输出 Feature\mathtt{Feature}

输入输出样例

  • 输入#1

    5
    1
    1 3 5 5 6
    1
    2 4 6 8 10
    2
    4 6 8 10 11
    4 8 12 16 19
    1
    1 2 3 3 3
    1
    1000000000000 2000000000000 3000000000000 4000000000000 5000000000000

    输出#1

    Bug
    Bug
    Feature
    Feature
    Feature

说明/提示

在第一个样例中,有 22 个局面,分别对应 xx5566 之间的每个取值。每局初始序列均为 1, 3, 51,\ 3,\ 5

Bug 的制胜策略如下:

  1. x=5x=5 的局面中,Bug 将 aa11 改为 44,此时序列变为 3, 4, 53,\ 4,\ 5,此时无进一步操作。
  2. 接下来 Feature 只能在 x=6x=6 的局面中将 aa11 改为 44
  3. 然后 Bug 在 x=6x=6 局面中将 bb33 改为 66,此时序列也被固定,无法继续操作。

因此,每一局在这样的步骤后均无法继续操作,从而保证了 Bug 的胜利。

首页