After passing the ticket verification and entering from the exhibition area, everyone arrives at the lively interactive hall. Here, Little T and Little S have specially set up a blind box lottery.

Blind boxes are placed on the lottery stall one after another as people arrive. Little T has devised a unique set of prize redemption rules: anyone can pick a subset of blind boxes from the stall and pair them up in the order they originally appeared. A pair is considered successful and can be redeemed for a prize only if the hidden numbers behind the pair of blind boxes satisfy a specific arithmetic condition.

A total of $n$ blind boxes will be placed on the stall, with hidden numbers $a_1, a_2, \dots, a_n$ behind them.

In the lottery, if the first $k$ blind boxes are currently displayed on the stall, a participant can choose an even number of blind boxes (let their indices in the original sequence be $1 \le i_1 < i_2 < \dots < i_{2t} \le k$) and pair them sequentially into $t$ groups: $(a_{i_1}, a_{i_2}), (a_{i_3}, a_{i_4}), \dots, (a_{i_{2t-1}}, a_{i_{2t}})$. For any pair of chosen blind boxes, let their hidden numbers be $x$ and $y$. The condition for redemption is: the bitwise XOR result of $x$ and $y$ must be strictly less than the lucky threshold $m$ set by Little T. Each pair satisfying this condition counts as a valid pair and can be redeemed for a prize.

As an enthusiastic participant, you also experienced this lottery, but unfortunately, none of the blind boxes you chose met the redemption criteria. To comfort you, Little S poses a challenge: if you can correctly answer her question, she will 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 stall, 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?

Input

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 set by Little T, respectively.

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

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

Examples

Input 1

5 4
1 2 5 4 3

Output 1

NYNYN

Note

The input size for this problem is large; it is recommended to use fast I/O methods.