#CS1098. Nim游戏 II

Nim游戏 II

题目背景

翻译自 CSES-1098 题。

题目描述

有 n 堆木棍，两个玩家轮流进行操作。每次操作时，玩家从一个非空的堆中移除 1 根、2 根或 3 根木棍。移走最后一根木棍的玩家获胜。

你的任务是判断，如果两位玩家都采用最优策略，谁将获胜。

输入格式

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

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

• 第一行输入一个整数 n：表示木棍堆的数量。

• 第二行输入 n n n 个整数 x1,x2,…,xn x_1, x_2, \dots, x_n x1​,x2​,…,xn​：表示每一堆中的木棍数量。

输出格式

对于每个测试用例，如果第一个玩家获胜，输出 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$

1≤xi≤1091 \leq x_i \leq 10^9 1≤xi​≤109；

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