#CS1099. 楼梯游戏

楼梯游戏

题目背景

翻译自 CSES-1099 题。

题目描述

有一个楼梯，包含 n n n 个楼梯，编号为 1,2,…,n 1, 2, \dots, n 1,2,…,n。每个楼梯上最初有若干个球。

两个玩家轮流进行操作。每次操作中，玩家选择一个楼梯 k k k（k≠1 k \neq 1 k=1 且该楼梯上至少有一个球），然后将任意数量的球从楼梯 k k k 移动到楼梯 k−1 k-1 k−1。最后一个移动的玩家获胜。

你的任务是判断，在两位玩家都采用最优策略的情况下，谁会获胜。

注意，如果没有可行的移动，第二个玩家获胜。

输入格式

第一行输入一个整数 t：表示测试的数量。

接下来的 t 个测试用例，每个测试用例包含两行：

• 第一行输入一个整数 n n n：表示楼梯的数量。

• 第二行输入 n n n 个整数 p1,p2,…,pn p_1, p_2, \dots, p_n p1​,p2​,…,pn​：表示每个楼梯上球的数量。

输出格式

对于每个测试用例，如果第一个玩家获胜，输出 first；如果第二个玩家获胜，输出 second。

样例

3
4
5 7 2 5
2
4 1
3
4 4 4

first
first
second

说明/提示

$1 \leq t \leq 2 \times 10^5$

$1 \leq n \leq 2 \times 10^5$

0≤pi≤1090 \leq p_i \leq 10^9 0≤pi​≤109；

所有测试用例中所有 nn n 的和不超过 2×1052 \times 10^5 2×105。