P16528 [THUPC 2026 Final] Blind Box Lottery.

From the final of the 2026 Tsinghua University Student Programming Contest and Intercollegiate Invitational (THUPC2026). Resources such as editorials can be found at https://github.com/dapingguo8/THUPC2026-final. > After passing the ticket check and entering from the exhibition area, everyone arrived at a lively interactive hall. Here, Little T and Little S specially set up a blind box lottery activity. > > The blind boxes at the booth would be put on the shelf one after another as people arrived. Little T therefore designed a unique prize redemption rule: everyone can pick some blind boxes from the stage, and pair them up in order according to their original sequence. Only when the hidden numbers behind these blind boxes satisfy a specific calculation condition does the pairing count as successful and allow them to redeem the corresponding prize.

A total of $n$ blind boxes will be put on the shelf one after another at the event site, and the hidden numbers behind them are $a_1, a_2, \dots, a_n$. During the lottery activity, if the first $k$ blind boxes are currently displayed on the stage, a participant may choose an even number of blind boxes from them (let their indices in the original sequence be $1 \le i_1 < i_2 < \dots < i_{2t} \le k$), and then pair them in order into $t$ groups, i.e., $(a_{i_1}, a_{i_2}), (a_{i_3}, a_{i_4}), \dots, (a_{i_{2t - 1}}, a_{i_{2t}})$. For any chosen pair of blind boxes, suppose their hidden numbers are $x$ and $y$. The condition for prize redemption is: the **bitwise XOR in binary** of $x$ and $y$ must be **strictly less than** the lucky threshold $m$ preset by Little T. Each pair of blind boxes that satisfies this condition counts as a valid pairing and can be redeemed for one prize. As an enthusiastic participant, you also tried this lottery, but unfortunately none of the blind boxes you chose satisfied the redemption condition. To comfort your bad luck, Little S gave you a challenge: if you can correctly answer her question, she will directly give you a special 10th anniversary grand prize. Little S's question is: for each $k \in [1, n]$, when exactly the first $k$ blind boxes are displayed on the stage, is the **maximum total number of prizes** that can be redeemed **strictly greater than** the maximum number when only the first $k - 1$ blind boxes are displayed?

The first line contains two positive integers $n, m \ (1 \le n \le 5 \times 10 ^ 6, \ 2 \le m \le 10 ^ 8)$, representing the total number of blind boxes and the lucky threshold preset by Little T. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n \ (1 \le a_i \le 10 ^ 8)$, representing the hidden number behind each blind box.

Output a single line containing a string of length $n$. For each $k \in [1, n]$, if the maximum number of prizes that can be redeemed when the first $k$ blind boxes are displayed is strictly greater than that when only the first $k - 1$ blind boxes are displayed, then the $k$-th character of the string is `Y`, otherwise it is `N`.

**Note**: The input size of this problem is large, so a faster input method is recommended. The testdata of this problem is large, and it may take 2 to 3 minutes to load the testdata during judging. Translated by ChatGPT 5