E. Шүрэн зүүлт

хугацааны хязгаарлалт 5 секунд

санах ойн хязгаарлалт 64 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ангараг гаригийн залуу Зорге дэлхийн найз болох Машад шүрэн зүүлт бэлэглэхийг хүсжээ. Түүний мэдэж байгаагаар Маша хөх, улаан хоёр өнгөнд дуртай ба түүний байгаа дэлгүүрт яг энэ хоёр өнгийн маш олон гоёмсог шүр байв.

Дэлгүүрт $N$ урттай бүх янзын зүүлтнүүд байв.

Шүрэн зүүлтийг товчлох үед тойрог хэлбэртэй болдог ба Ангарагийнхны нүдний онцлогоос шалтгаалан хэрвээ зүүлтэн дэхь улаан шүр бүрийг хөхөөр, хөх шүр бүрийг улаанаар сольсон зүүлтийг анхны зүүлттэй адил гэж хардаг байв. Өөрөөр хэлбэл Зорге товчлогдсон зүүлтийг урдаас нь юм уу хойноос нь урвуулж хараад өнгүүдийг нөгөө өнгөөр нь сольж харахад адилхан байвал адилхан гэж боддог байв.

Ангарагийнхан үнэхээр нямбай ба хэрвээ Ангарагийн хүн хэсэг обьектийг харвал тэдгээрийг заавал эрэмбэлж тавихыг хичээдэг аж. Зоргед улаан шүрнүүд хөх шүрнүүдээс жижигхэн харагдсан тул $0$-ээр улаан шүрийг, $1$-ээр хөх шүрийг тэмдэглэе. Тэгвэл одоо бид нар хоёр зүүлтийг эрэмбэлж чадна.

Эхлээд Зорге бүх шүрэн зүүлтнүүдийг аваад дараа өөрийнхөө ижил гэж бодож байгаануудыг нэг хайрцганд хийнэ. Тэгээд тэр хайрцгууд доторхыг эрэмбэлээд хайрцаг бүр дэхь хамгийн бага хэлхээг сонгоод сонгогдсон хэлхээнүүдийг дахин эрэмбэлээд $k$ дугаартай хэлхээг худалдаж аваад бусдыг нь худалдагчид буцааж өгчээ.

Энэ бүх үйлдлүүддээ Зорге маш их цаг зарцуулах болсон тул тэр танаас Машад зориулсан хэлхээг олж өгөхийг хүсчээ.

Оролт

Шүрэн хэлхээний урт $n$ ба Зоргегийн сонгосон дугаар $k$ хоёр зайгаар тусгаарлагдан байрлана. ($2 ≤ n ≤ 50; 1 ≤ k ≤ 10^{16}$)

Гаралт

$k$-р шүрэн хэлхээг хэвлэнэ. $0$-ээр улаан шүр, $1$-ээр хөх шүрийг илэрхийлнэ. Хэрвээ хайж байгаа хэлхээг олох боломжгүй бол $-1$ гэж хэвлэнэ үү.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
4 4
Гаралт
0101

Тэмдэглэл

Let's consider the example of strings of length 4 -- 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110. Zorg will divide them into heaps: {0001, 0111, 1000, 1110}, {0010, 0100, 1011, 1101}, {0011, 1100}, {0101, 1010}, {0110, 1001}. Then he will choose the minimum strings of beads in each heap: 0001, 0010, 0011, 0101, 0110. The forth string -- 0101.

Сэтгэгдлүүдийг ачааллаж байна...