CSES 2208 ↗

Another Game

Remove one coin from each of a chosen non-empty set of non-empty heaps.

0
submissions
—
best score

There are n heaps of coins and two players who move alternately. On each move, a player selects some of the nonempty heaps and removes one coin from each heap. The player who removes the last coin wins the game.

Your task is to find out who wins if both players play optimally.

Input

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 x1,x2,…,xn: the number of coins in each heap.

Output

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

Constraints

  • 1≤t≤2⋅105
  • 1≤n≤2⋅105
  • 1≤xi≤109
  • the sum of all n is at most 2⋅105

Example

Input:

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

Output:

first
second
first

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/AnotherGame/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.