На мероприятии по очереди выставляются $n$ «слепых коробок» (blind boxes), скрытые числа на которых равны $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$, условием получения приза является то, что результат их побитового исключающего ИЛИ (XOR) должен быть строго меньше заданного порогового значения $m$. Каждая пара, удовлетворяющая этому условию, считается успешной и позволяет получить один приз.

Как участник, вы также попробовали свои силы в этом розыгрыше, но, к сожалению, ни одна из выбранных вами коробок не удовлетворила условиям получения приза. Чтобы утешить вас, Сяо С предложила вам задачу: для каждого $k \in [1, n]$, когда на столе выставлены ровно первые $k$ коробок, является ли максимально возможное общее количество призов, которые можно получить, строго большим, чем максимальное количество призов при наличии только первых $k-1$ коробок?

Первая строка содержит два целых положительных числа $n, m$ ($1 \le n \le 5 \times 10^6$, $2 \le m \le 10^8$), представляющие общее количество коробок и пороговое значение $m$, установленное Сяо Т.

Вторая строка содержит $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.

Примеры

Входные данные 1

5 4
1 2 5 4 3

Выходные данные 1

NYNYN

Примечание

Объем входных данных в этой задаче велик, рекомендуется использовать быстрые методы ввода.