Задобріть Інті

Як ви пам'ятаєте, плем'я Майя вимерло, плем'я Йюля змушене було розпастися і залишити обжиті території, і ось тепер племені Авгуйя також загрожує небезпека. Задобривши бога дощу Тлалока, вони зовсім забули про бога сонця Інті, який, будучи обділеним увагою, погрожує низпослати спопеляючу спеку, якщо жителі племені не порадують його божественний погляд новою колекцією симпатичних візерунків, викладених із величезних гранітних плит, пофарбованих у чорний та білий кольори. Нагадаємо, що симпатичним візерунком називається прямокутник шириною $W$ та висотою $H$, жоден квадрат 2 \times 2 якого не пофарбовано в один колір.

У цій задачі тягати гранітні плити вам не доведеться, проте потрібно визначити $K$-й лексикографічно симпатичний візерунок. Один візерунок будемо вважати лексикографічно меншим за інший, якщо при перегляді візерунку по стовпцям зверху вниз знайдеться така позиція, що усі плити, розглянуті раніше, збігаються попарно за кольором, а плита на цій позиції у першого візерунка біла, а у другого — чорна.