P16528 [THUPC 2026 决赛] 零叉零寺

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 > 通过了门票考验并从展览区入场后，大家便来到了热闹的互动大厅。在这里，小 T 和小 S 特意设置了盲盒抽奖环节。 > > 抽奖摊位上的盲盒会随着大家的到来而陆续上架。小 T 为此制定了一套别出心裁的兑奖规则：每个人都可以从台上挑出一部分盲盒，并按这些盲盒原有的先后顺序两两配对。只有当这组盲盒背后的隐藏数字满足特定的运算条件时，配对才算成功并能兑换相应的奖品。

活动现场总计会陆续上架 $n$ 个盲盒，它们背后的隐藏数字分别为 $a_1, a_2, \dots, a_n$。 在抽奖环节中，若当前台上已经展示了前 $k$ 个盲盒，则参与者可以从中挑选出偶数个盲盒（设其对应原序列的下标为 $1 \le i_1 < i_2 < \dots < i_{2t} \le k$），并将它们依次配对为 $t$ 组，即 $(a_{i_1}, a_{i_2}), (a_{i_3}, a_{i_4}), \dots, (a_{i_{2t - 1}}, a_{i_{2t}})$。对于任意一对被挑选出的盲盒，设其背后的隐藏数字分别为 $x$ 和 $y$，则兑奖的条件是：$x$ 与 $y$ 的**二进制按位异或**结果必须**严格小于**小 T 提前设定的幸运阈值 $m$。满足该条件的每一对盲盒均可算作有效配对，并兑换一个奖品。 作为热情的参与者，你也体验了这场抽奖，但十分遗憾，你选出的盲盒无一满足兑奖条件。为了安慰运气不佳的你，小 S 向你抛出了一个挑战：如果你能正确回答她提出的问题，她便会直接送你一份特别的十周年大奖。 小 S 的问题是：对于每一个 $k \in [1, n]$，当台上恰好展示了前 $k$ 个盲盒时，能够兑换的**最大奖项总数**，是否**严格大于**仅展示前 $k - 1$ 个盲盒时的最大数量？

输入的第一行包含两个正整数 $n, m \ (1 \le n \le 5 \times 10 ^ 6, \ 2 \le m \le 10 ^ 8)$，分别表示盲盒的总数与小 T 提前设定的幸运阈值。 输入的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n \ (1 \le a_i \le 10 ^ 8)$，分别表示每个盲盒背后的隐藏数字。

输出一行一个长度为 $n$ 的字符串。对于每一个 $k \in [1, n]$，若展示前 $k$ 个盲盒能兑换的最大奖项数严格大于仅展示前 $k - 1$ 个盲盒时的最大奖项数，则字符串的第 $k$ 位为 `Y`，否则为 `N`。

**注意**：本题输入量较大，建议使用较为快速的输入方式。 本题测试数据较大，评测时可能需要 2-3 分钟时间加载测试数据。