Những Khúc Gỗ · canuc80k5203 · Thuật toán Canuc80k

Có $n$ khúc gỗ nguyên dương, khúc thứ $i$ dài $a_{i}$ . Mỗi lượt chọn một khúc dài $x \geq 2$ và chặt thành hai khúc nguyên dương y,z với $y + z = x$ . Người không thể chặt tiếp thua; errorgorn đi trước.

Input

Dòng đầu chứa $t$ . Mỗi test gồm $n$ , sau đó là $n$ độ dài đoạn gỗ.

Output

Với mỗi test, in errorgorn hoặc maomao90 theo người thắng.

Constraints

$1 \leq t \leq 100$ .
$1 \leq n \leq 5000$ , tổng $n$ không vượt $1 0^{4}$ .
$1 \leq a_{i} \leq 1 0^{9}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): các test $1$ - $10$ có kích thước nhỏ, thuận tiện kiểm chứng độc lập.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung ngoài các cận đã nêu.

Example

Test 1

Input

1
1
1

Output

maomao90

Giải thích: Khúc gỗ duy nhất có độ dài $1$ , nên không thể chẻ thành hai khúc có độ dài nguyên dương. Người đi trước không có nước đi và kết quả là maomao90.

Ý tưởng và thuật toán: Với một khúc dài x, để cuối cùng thành toàn khúc đơn vị cần đúng x-1 lần chặt: ban đầu có một khúc, cuối cùng có x khúc, và mỗi lần chặt tăng số khúc thêm đúng một.
Ý tưởng và thuật toán: Toàn bộ trò chơi vì thế có M = Σ(a_i-1) = Σa_i - n lượt, không phụ thuộc người chơi chặt theo cách nào. Người đầu thắng khi M lẻ.
Chứng minh đúng đắn: Bổ đề. Mỗi nước đi giảm thế năng P=Σ(length-1) đúng 1: thay x-1 bằng (y-1)+(z-1)=x-2.
Chứng minh đúng đắn: P không âm; P=0 khi và chỉ khi mọi khúc dài 1, tức không còn nước. Vì mỗi lượt giảm đúng một, số lượt từ trạng thái đầu đến cuối đúng bằng P_0. Do đó parity P_0 quyết định người thực hiện lượt cuối và thuật toán đúng.
Độ phức tạp: Mỗi test O(n) thời gian, O(1) bộ nhớ phụ.