Bóng Trên Bậc Thang · canuc80k5302

Một cầu thang có $n$ bậc, đánh số từ $1$ ở dưới lên $n$ ở trên. Bậc $i$ đang chứa $p_{i}$ quả bóng. Hai người chơi luân phiên thực hiện thao tác sau:

Chọn một bậc $k > 1$ đang có bóng.
Chuyển một số lượng dương tùy ý bóng từ bậc $k$ xuống bậc $k - 1$ .

Bóng ở bậc $1$ không thể di chuyển tiếp. Người không còn thao tác hợp lệ sẽ thua. Với mỗi ván, hãy xác định người thắng khi cả hai chơi tối ưu.

Input

Dòng đầu chứa số nguyên $t$ , là số ván.
Mỗi ván gồm hai dòng:
Dòng thứ nhất chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ .

Output

Với mỗi ván, in first nếu người chơi thứ nhất thắng; ngược lại in second.

Constraints

$1 \leq t \leq 2 \cdot 1 0^{5}$ .
$1 \leq n \leq 2 \cdot 1 0^{5}$ cho mỗi ván.
$0 \leq p_{i} \leq 1 0^{9}$ .
Tổng $n$ của tất cả các ván không vượt quá $2 \cdot 1 0^{5}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $t \leq 10$ , tổng $n \leq 20$ và $p_{i} \leq 15$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

second
first

Giải thích: Ở ván đầu, người thứ hai đáp lại theo cặp: một lượng bóng được chuyển vào bậc $2$ hoặc $4$ sẽ được chuyển tiếp đúng lượng đó xuống bậc dưới, còn một lượng bị chuyển khỏi bậc $2$ hoặc $4$ sẽ được bắt chước ở bậc chẵn còn lại; vì hai bậc này ban đầu cùng có $3$ bóng, thế đối ứng được giữ đến cuối. Ở ván sau, người thứ nhất chuyển $3$ bóng từ bậc $2$ xuống bậc $1$ , làm hai bậc $2$ và $4$ cùng còn $2$ bóng, rồi dùng chính chiến lược đối ứng ấy.

Ý tưởng: \
Phân tích: Giá trị Grundy của toàn cầu thang bằng xor lượng bóng ở các bậc chẵn p_2 xor p_4 xor .... Một nước đi luôn thay đổi đúng một đại lượng trong xor này: xuất phát từ bậc chẵn thì đại lượng đó giảm, còn xuất phát từ bậc lẻ thì bậc chẵn ngay dưới tăng.
Thuật toán: Đọc dãy và xor các phần tử có chỉ số chẵn. In first nếu xor khác 0, ngược lại in second.
Chứng minh đúng: Gọi xor hiện tại là X. Không nước đi nào giữ nguyên X, vì đúng một số hạng của xor thay đổi. Khi X != 0, tính chất chuẩn của Nim cho phép chọn một bậc chẵn và giảm lượng bóng trên đó để xor mới bằng 0; thao tác này chính là chuyển số bóng bị giảm xuống bậc ngay dưới. Do đó vị trí thua chính xác là các vị trí có X = 0, nên thuật toán đúng.
Độ phức tạp: Mỗi ván dùng O(n) thời gian và O(1) bộ nhớ phụ.