Trò chơi khác

Có $n$ đống xu. Hai người chơi thay nhau thực hiện nước đi: mỗi lượt, người chơi chọn một tập con khác rỗng các đống đang có xu, rồi lấy đúng 1 xu từ mỗi đống trong tập đó. Người lấy xu cuối cùng thắng. Với lối chơi tối ưu, ai sẽ thắng?

Dữ liệu vào

Dòng đầu ghi số lượng truy vấn $t$.

Mỗi truy vấn gồm hai dòng:

• Dòng đầu: số nguyên $n$ — số đống xu.
• Dòng tiếp: $n$ số nguyên $x_1,x_2,\dots ,x_n$ — số xu trong mỗi đống.

Dữ liệu ra

Với mỗi truy vấn, in ra first nếu người đi trước thắng, second nếu người đi sau thắng.

Ràng buộc

• $1\le t\le 2·{10}^5$
• $1\le n\le 2·{10}^5$
• $1\le x_i\le {10}^9$
• Tổng tất cả $n$ không vượt quá $2·{10}^5$

Ví dụ