Один марсианский мальчик по имени Цорг хочет подарить своей подруге с Земли Маше бусы. Он знает, что Маша любит два цвета: синий и красный, — и как раз в магазине, куда он зашел, есть все возможные украшения с бусинами двух цветов. На каждых бусах есть маленькая застежка, если ее расстегнуть, то можно заметить, что все бусы в магазине одинаковой длины. Из-за особенностей марсианского зрения если Цорг видит одни сине-красные бусы, а потом другие, в которых на месте синих стоят красные бусины, а на месте красных — синие, он считает эти две нитки бус одинаковыми. Иными словами, для Цорга одинаковыми считаются не только те бусы, что получаются друг из друга переворотом нитки, но и те, что получаются друг из друга сменой цветов и/или переворотом ниток.

Как известно все марсиане очень аккуратны, и если марсианин видит некоторое множество предметов, то он старается упорядочить их. Красную бусину Цорг считает меньше синей. Обозначим красную бусину — 0, а синюю — 1. Из двух ниток марсианин раньше положит ту, у которой на i-ом месте нанизана красная бусина, при том, что во второй нитке на i-ом месте — синяя, а первые i - 1 бусины у них совпадают.

Сначала Цорг расстегивает все бусы и раскладывает на кучки так, что, по его мнению, в каждой из них лежат одинаковые нитки. Потом он упорядочивает каждую кучку и выбирает по одним бусам, являющимся наименьшими в данной кучке. Все остальные бусы он отдает продавцу и просит их убрать. Затем Цорг упорядочивает все оставшиеся бусы и покупает k-ые по номеру.

Все эти операции займут очень много времени у Цорга, поэтому он просит вас помочь найти бусы для Маши.