F. Код Грея

Код Грея — это нумерация двоичных строк, при которой соседние номера отличаются ровно одним битом. Стандартный код Грея задаётся формулой

Отвечайте на запросы двух видов: по номеру $x$ выдать $g(x)$ и по значению $y$ выдать такое $x$, что $g(x) = y$.

В первой строке $q$ ($1 \le q \le 10^5$). В каждой из следующих $q$ строк — тип запроса и число: 1 x (выдать $g(x)$) или 2 y (выдать $x$ по $g(x) = y$). Оба числа лежат в пределах от $0$ до $2^{60} - 1$.

Для каждого запроса выведите одно число в отдельной строке.