AT_arc212_d [ARC212D] Two Rooms

There are $ N $ people numbered $ 1,2,\ldots,N $ . For $ i\neq j $ , the intimacy between persons $ i $ and $ j $ is $ A_{i,j} $ . For each of the $ N $ people, assign room $ X $ or room $ Y $ . Each of the $ N $ people moves to their assigned room. It is acceptable if there is an empty room. Person $ i $ is in a **good state** if the following is satisfied: > (Sum of intimacy with person $ i $ of all people in the same room as person $ i $ ) $ \geq $ (Sum of intimacy with person $ i $ of all people in a different room from person $ i $ ). Output one assignment of rooms such that all $ N $ people are in a good state. It can be proved that such an assignment always exists.

The input is given from Standard Input in the following format: > $ N $ $ A_{1,1} $ $ A_{1,2} $ $ \cdots $ $ A_{1,N} $ $ A_{2,1} $ $ A_{2,2} $ $ \cdots $ $ A_{2,N} $ $ \vdots $ $ A_{N,1} $ $ A_{N,2} $ $ \cdots $ $ A_{N,N} $

Output one assignment that satisfies the condition. If there are multiple solutions, you may output any of them. Represent the assignment by a string $ S $ of length $ N $ . If person $ i $ is assigned to room $ X $ , the $ i $ -th character of $ S $ should be `X`; if assigned to room $ Y $ , the $ i $ -th character of $ S $ should be `Y`.

### Sample Explanation 1 Suppose persons $ 1,2 $ are assigned to room $ X $ and persons $ 3,4 $ are assigned to room $ Y $ . For person $ 1 $ , the sum of intimacy with people in the same room (person $ 2 $ ) is $ 4 $ , and the sum of intimacy with people in different rooms (persons $ 3 $ and $ 4 $ ) is $ (-2)+(-1)=-3 $ , so they are in a good state. All other people are also in a good state, so this assignment satisfies the condition. Outputting `YYXX` is also correct. ### Sample Explanation 2 It is acceptable if there is an empty room. ### Constraints - $ 2 \leq N \leq 50 $ - $ -50 \leq A_{i,j} \leq 50 $ - $ A_{i,j} = A_{j,i} $ - $ A_{i,i}=0 $ - All input values are integers.