- Time limit: 1.00 s
- Memory limit: 512 MB
There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.
Your task is to find out who wins if both players play optimally.
The first input line contains an integer t: the number of tests. After this, t test cases are described:
The first line contains an integer n: the number of heaps.
The next line has n integers x_1,x_2,\ldots,x_n: the number of sticks in each heap.
For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.
- 1 \le t \le 2 \cdot 10^5
- 1 \le n \le 2 \cdot 10^5
- 1 \le x_i \le 10^9
- the sum of all n is at most 2 \cdot 10^5
3 4 5 7 2 5 2 4 1 3 4 4 4
first first second