После всем известных событий в Орландо, Саша и Рома решили определить между собой, кто же всё-таки является самым слабым звеном в команде. Спасибо Маше, которая где-то нашла револьвер с крутящимся барабаном на n зарядов и k патронов к нему, теперь у ребят появился отличный способ разобраться раз и навсегда.

Саша выбирает k из n слотов по своему желанию и кладёт в них патроны. Рома раскручивает барабан так, что любой из n циклических сдвигов положения барабана равновероятен. Потом начинается игра, играют поочередно, первым делает ход Саша: он приставляет револьвер к виску и делает выстрел. Если напротив курка не было патрона, то барабан сдвигается на одну позицию, а оружие передается Роме для такого же хода. Игра продолжается до тех пор, пока кто-нибудь не застрелится, выживший считается победителем.

Саша очень не хочет проигрывать, поэтому он должен выбрать слоты для патронов таким образом, чтобы минимизировать вероятность собственного поражения. Из всех существующих вариантов он готов выбрать только лексикографически минимальный, при этом пустой слот считается лексикографически меньше заряженного.

Более формально барабан на n зарядов, заряженный k патронами, можно представить в виде строки из n символов, ровно k из которых — «X» (заряженные слоты), а остальные — «.» (незаряженные слоты).

Опишем подробнее выстрел из револьвера. Предположим, что курок расположен напротив первого символа строки (первого слота барабана). Если выстрел никого не убивает, и барабан сдвигается на одну позицию, то строка сдвигается влево. То есть первый символ становится последним, второй — первым, и так далее. Курок при этом остается на месте — напротив первого символа получившейся строки.

Среди всех строк, обеспечивающих минимальную вероятность проигрыша, Саша выбирает лексикографически наименьшую. Ваша задача — помочь Саше зарядить револьвер. Для этого на каждый запрос x_i нужно ответить: есть ли пуля на позиции x_i?