26744번 - Pinezki 다국어

Bajtosia wbija pinezki w oś liczbową – dokładniej mówiąc, wybiera sobie pewne N i wbija pinezki w swój ulubiony odcinek [0, 3^N] na osi. Pierwsze dwie pinezki trafiają na na początek i koniec odcinka, a następnie Bajtosia działa według następującego planu:

Najpierw wbija nowe pinezki w jednej trzeciej długości od początku swojego odcinka oraz w jednej trzeciej długości od końca. Tak wyznaczone punkty dzielą odcinek na trzy części równej długości: lewą, środkową i prawą. Następnie Bajtosia powtarza cały proces najpierw dla części lewej (jej początek i koniec już ma zaznaczony), a potem dla części prawej (ale nie dla środkowej!). Po drodze w obu tych częściach pojawią się mniejsze części, w których Bajtosia będzie znowu powtarzać swój plan, i tak dopóki się da – ponieważ Bajtosia wbija pinezki tylko w punkty całkowite, nie będzie już dalej dzielić odcinków, które mają długość 1.

Końcowy układ pinezek otrzymany przez Bajtosię nazywa się fraktalem¹.

Przykładowo, jeśli N = 3, na odcinku zaznaczone będą następujące punkty:

Bajtosia zastanawia się czy się nie pomyliła, sprawdzając dla różnych K pozycję K-tej pinezki od lewej. Pomożesz jej?

Napisz program, który wczyta wartość N oraz zapytania Bajtosi i dla każdego zapytania K_i wyznaczy, gdzie leży K_i-ta pinezka.

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 36). W drugim wierszu wejścia znajduje się jedna liczba naturalna Q (1 ≤ Q ≤ 200 000) określająca liczbę zapytań Bajtosi. W kolejnych Q wierszach znajduje się opis kolejnych zapytań, po jednym w wierszu. Opis każdego zapytania składa się z jednej liczby K_i (1 ≤ K_i ≤ 10¹⁸) określającej zapytanie Bajtosi jaka jest pozycja K_i-tej od lewej pinezki wbitej na jej odcinku. Wbite przez Bajtosię pinezki numerujemy kolejnymi liczbami naturalnymi zaczynając od 1.

Twój program powinien wypisać dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zapytania Bajtosi – pozycja K_i-tej pinezki na odcinku. Jeżeli Bajtosia wbiła mniej niż K_i pinezek, zamiast tego należy wypisać (dla tego zapytania) odpowiedź NIE.