CSES - Stair Game | Trò chơi bậc thang

Xem PDF

Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Có một cái cầu thang gồm \(n\) bậc thang được đánh số \(1, 2,..., n\). Ban đầu, mỗi bậc thang có một số lượng các quả bóng.

Có hai người sẽ luân phiên nhau chơi trò chơi. Tại mỗi nước đi, một người chơi sẽ chọn một bậc thang \(k\) sao cho \(k \neq 1\) và nó có ít nhất một quả bóng. Sau đấy người chơi sẽ di chuyển một số lượng bất kì các quả bóng từ bậc thang thứ \(k\) xuống \(k - 1\). Người chơi thực hiện nước đi cuối cùng sẽ chiến thắng trò chơi.

Nhiệm vụ của bạn là xác định xem ai sẽ chiến thắng trò chơi khi hai người chơi đều chơi một cách tối ưu.

Hãy lưu ý là nếu không có một nước đi nào cả thì người chơi thứ hai sẽ chiến thắng.

Input

  • Dòng đầu tiên chứa một số nguyên \(t\): số bộ test. Sau đấy, \(t\) bộ test được diễn tả như sau:
  • Dòng đầu tiên chứa số nguyên \(n\): số bậc thang.
  • Dòng tiếp theo gồm \(n\) số nguyên \(p_1, p_2,...,p_n\): số lượng quả bóng tại mỗi bậc thang ở thời điểm ban đầu.

Output

Với mỗi bộ test, in ra first nếu người chơi đầu tiên giành chiến thắng trò chơi và second nếu người chơi thứ hai thắng.

Constraints

  • \(1 \leq t \leq 2 \cdot 10^5\).
  • \(1 \leq n \leq 2 \cdot 10^5\).
  • \(0 \leq p_i \leq 10^9\).
  • Tổng \(n\) trong tất cả các bộ test không vượt quá \(2 \cdot 10^5\).

Example

Sample input

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

Sample output

first  
second  
first


Bình luận

Không có bình luận nào.