The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

if x is even then x = x / 2
if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).
Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.
Return the k-th integer in the range [lo, hi] sorted by the power value.
Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.
 
Example 1:
Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:
Input: lo = 1, hi = 1, k = 1
Output: 1

Example 3:
Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Example 4:
Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:
Input: lo = 1, hi = 1000, k = 777
Output: 570

 
Constraints:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

def _disabled_input(*args, **kwargs):
    raise RuntimeError("input() is disabled in callable mode")
builtins.input = _disabled_input

ns = {"__name__": "__judge__"}  # prevent if __name__ == "__main__" blocks
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "class Solution:\n    def getKth(self, lo: int, hi: int, k: int) -> int:\n        return sorted(range(lo, hi + 1), key='寒寒寓寙寔寗寚寢寕寥寘寠寛寛寣寣寖寞實實寙寙寡寡寜審寜屁寤寤寤尼寗寬察察寧寧寧寴寚尿寚寯寢寢寢尺寝寪寪寪寝寝层层寥寲寥寲寥寥尽尽寘寭寭寭寠寠寠尸寨居寨寠寨寨寵寵寛寨局局寛寛寰寰寣寰寣尮寣寣尻尻寞屈寫寫寫寫寫尩寞寸寞尶屃屃屃尗實寞寳寳實實寳寳實就實尀尾尾尾尀寙屋寮寮寮寮寮寻寡尬寡寻寡寡尹尹審屆屆屆審審寡寡審寶審尧寶寶寶專寜尴審審屁屁屁尕寜尃寜屎寱寱寱尢寤寱寱寱寤寤尯尯寤対寤対尼尼尼対察屉屉屉寬寬寬屉寬寤寬对寬寬尪尪察对对对察察尷尷屄寬屄将屄屄尘尘寧将察察寴寴寴屑寧尥寧屑寴寴寴将寧寧尲尲寧寧封封尿封尿尓尿尿封封寚屌屌屌寯寯寯尠寯屌寯寧寯寯导导寢寯尭尭寢寢导导寢导寢導尺尺尺导寪寯屇屇屇屇屇尉寪尛寪屇寢寢寢导寪寷寷寷寪寪尨尨寷屔寷寷寷寷尉尉寝寪尵尵寪寪寪屡层射层寪层层尖尖寝层射射寝寝屏屏寲屏寲屏寲寲尣尣寥屏寲寲寲寲寲射寥寿寥寿尰尰尰寿寥寥寿寿寥寥寿寿尽少尽尌尽尽寿寿寠寲届届届届届届寭尌寭尞寭寭届届寭寥寥寥寭寭寺寺寭寺寭屗尫尫尫屗寠屗寺寺寺寺寺寲寠尌寠將尸尸尸寺居寭寭寭居居將將居寭居將尙尙尙尳寨居將將寠寠寠寺寵屒寵屒寵寵屒屒寨寵尦尦寨寨屒屒寵寵寵寭寵寵將將寨専寨寨尳尳尳屟寨専寨屟専専専尳局寨専専局局尔尔局小局寵専専専小寛寵屍屍屍屍屍小寰屍寰屍寰寰尡尡寰寰屍屍寰寰寨寨寰寨寰専寽寽寽屚寣寽寰寰尮尮尮寽寣屚寣寰寽寽寽尩寣寽寽寽寣寣小小尻尊尻寰尻尻寽寽寫寰寰寰屈屈屈寰屈尊屈屈屈屈尊尊寫尜尜尜寫寫屈屈寣尊寣尗寣寣寽寽寫展寸寸寸寸寸尗寫展寫展尩尩尩展寸寫展展寸寸寸寸寸寰寸寰尊尊尊展寞尅寫寫尶尶尶寸寫屢寫尶寫寫屢屢屃尅尅尅屃屃寫寫屃尅屃屢尗尗尗就寞尒屃屃尅尅尅尒寞尒寞寸屐屐屐寸寳屐屐屐寳寳屐屐寳屐寳尒尤尤尤屼實寳屐屐寳寳寳尒寳寫寳寫寳寳尅尅實尀尀尀實實尀尀就寳就屝就就尀尀實屝實實尀尀尀就實尬實尀尀尀尀屝尾實尒尒尾尾對對尾寳尾屪尀尀尀對寡寳寳寳屋屋屋屪屋寳屋對屋屋屋屋寮屋對對寮寮尟尟寮尟寮尹屋屋屋尚寮對實實實實實尚寮尀寮屘寻寻寻屘寮寻寻寻寮寮屘屘尬屘尬寻尬尬屘屘寡寮屘屘寻寻寻尧寻寻寻寻寻寻寳寳寡對對對寡寡專專尹寮尹履尹尹寻寻屆履寮寮寮寮寮岄屆履屆寮專專專履屆屆寮寮屆屆專專尚履尚尀尚尚尴尴審尕屆屆專專專屆寡尕寡專寡寡寻寻寶屓屓屓寶寶屓屓寶屓寶尕屓屓屓屆審屓寶寶尧尧尧屓審屿審尧屓屓屓寶寶寶寶寶寶寶寮寮寶寮寶寮專專專屓審尃尃尃審審審屠尴尃尴寶尴尴屠屠審尴尃尃審審屠屠尃審尃寶尃尃尴尴屁尯審審尃尃尃尃屁'.__getitem__)[k - 1]"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

_target = None
_fn_name = 'getKth'
if _fn_name:
    if "Solution" in ns:
        try:
            _obj = ns["Solution"]()
            if hasattr(_obj, _fn_name):
                _target = getattr(_obj, _fn_name)
        except Exception:
            _target = None
    if _target is None and _fn_name in ns and callable(ns[_fn_name]):
        _target = ns[_fn_name]
# Fallback: if there's exactly one user-defined function, use it
if _target is None:
    _cands = [v for k, v in ns.items() if callable(v) and getattr(v, "__module__", "") in ("__judge__", "__main__")]
    _user_funcs = [c for c in _cands if getattr(c, "__name__", "").startswith("_") is False]
    if len(_user_funcs) == 1:
        _target = _user_funcs[0]
if _target is None:
    raise RuntimeError(f"Could not resolve callable '{_fn_name}'")

_raw = sys.stdin.read().strip()
if _raw:
    _parsed = json.loads(_raw)
    if isinstance(_parsed, dict):
        _kwargs = _parsed.get("kwargs", {})
        _args = _parsed.get("args", [])
    else:
        _args, _kwargs = _parsed, {}
else:
    _args, _kwargs = [], {}
if not isinstance(_args, (list, tuple)):
    _args = [_args]
_res = _target(*_args, **_kwargs)
try:
    sys.stdout.write(repr(_res) + "\n")
except Exception:
    pass

```

Measured memory_bytes: 5422