题库练习 Bug Is Feature (Conditional Version)
← 上一题 下一题 →

A16799 | Bug Is Feature (Conditional Version)

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

这是该题的条件版本。这个版本与原问题的主要区别在于,“公差不减”这一条件的存在。只有你完成了所有版本的题目后,才能进行 Hack 操作。

请注意,这两个版本并不必然哪个更容易,并且它们可以独立地进行求解。

Bug 和 Feature 正沉浸在一种名为 Sequence 的游戏中。在这个独特版本的 Sequence 游戏中,游戏以三个正整数 $a < b < c \le x$ 开始,并且三者构成一个等差数列(即 $b-a=c-b$)。每当轮到玩家时,可以选择将 $a$、$b$ 或 $c$ 的其中一个增加一个正整数。操作后,三个数仍需保持等差数列(可能顺序会变化),且新的公差不能小于之前的公差。此外,$a$、$b$、$c$ 均不能超过 $x$。

Bug 和 Feature 并不满足与常规的 Sequence 游戏,于是他们决定同时玩 $n$ 组 Sequence 游戏。对于第 $i$ 组游戏,给定五个数 $a_i < b_i < c_i \le l_i \le r_i$。对于每一个 $x \in [l_i, r_i]$,他们要玩一个以 $a_i < b_i < c_i \le x$ 为初始状态的游戏(一共要玩 $\sum_{i=1}^n (r_i - l_i + 1)$ 个游戏)。两人交替进行所有这些游戏的回合,Bug 先手,然后 Feature。每回合,玩家选择任意一个未结束的游戏执行一次有效操作。无法进行操作的一方视为失败。

那么,若两人均以最优策略博弈,最终谁会获得胜利?

输入格式

每个测试用例包含多组数据。第一行包含整数 $t$($1 \le t \le 10^5$),表示测试用例的数量。

每个测试用例的第一行是一个整数 $n$($1 \le n \le 2 \times 10^5$),表示 Bug 和 Feature 要玩的游戏组数。

接下来的 $n$ 行,每行包含五个整数 $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}$),表示第 $i$ 组游戏的参数。$a_i$、$b_i$、$c_i$ 形成等差数列(即 $c_i-b_i=b_i-a_i$)。

所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据,输出一行,若 Bug 获胜则输出 $\mathtt{Bug}$,否则输出 $\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
Feature
Bug
Feature
Feature
Bug
C++ 编辑器
输入
输出