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

Difficulty: interview

Starter code:

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        

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

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted(list(range(lo, hi + 1)), key=[1, 1, 2, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, 110, 9, 30, 17, 17, 17, 105, 12, 25, 25, 25, 12, 12, 113, 113, 20, 33, 20, 33, 20, 20, 108, 108, 7, 28, 28, 28, 15, 15, 15, 103, 23, 116, 23, 15, 23, 23, 36, 36, 10, 23, 111, 111, 10, 10, 31, 31, 18, 31, 18, 93, 18, 18, 106, 106, 13, 119, 26, 26, 26, 26, 26, 88, 13, 39, 13, 101, 114, 114, 114, 70, 21, 13, 34, 34, 21, 21, 34, 34, 21, 96, 21, 47, 109, 109, 109, 47, 8, 122, 29, 29, 29, 29, 29, 42, 16, 91, 16, 42, 16, 16, 104, 104, 24, 117, 117, 117, 24, 24, 16, 16, 24, 37, 24, 86, 37, 37, 37, 55, 11, 99, 24, 24, 112, 112, 112, 68, 11, 50, 11, 125, 32, 32, 32, 81, 19, 32, 32, 32, 19, 19, 94, 94, 19, 45, 19, 45, 107, 107, 107, 45, 14, 120, 120, 120, 27, 27, 27, 120, 27, 19, 27, 40, 27, 27, 89, 89, 14, 40, 40, 40, 14, 14, 102, 102, 115, 27, 115, 53, 115, 115, 71, 71, 22, 53, 14, 14, 35, 35, 35, 128, 22, 84, 22, 128, 35, 35, 35, 53, 22, 22, 97, 97, 22, 22, 48, 48, 110, 48, 110, 66, 110, 110, 48, 48, 9, 123, 123, 123, 30, 30, 30, 79, 30, 123, 30, 22, 30, 30, 43, 43, 17, 30, 92, 92, 17, 17, 43, 43, 17, 43, 17, 61, 105, 105, 105, 43, 25, 30, 118, 118, 118, 118, 118, 56, 25, 74, 25, 118, 17, 17, 17, 43, 25, 38, 38, 38, 25, 25, 87, 87, 38, 131, 38, 38, 38, 38, 56, 56, 12, 25, 100, 100, 25, 25, 25, 144, 113, 51, 113, 25, 113, 113, 69, 69, 12, 113, 51, 51, 12, 12, 126, 126, 33, 126, 33, 126, 33, 33, 82, 82, 20, 126, 33, 33, 33, 33, 33, 51, 20, 46, 20, 46, 95, 95, 95, 46, 20, 20, 46, 46, 20, 20, 46, 46, 108, 64, 108, 59, 108, 108, 46, 46, 15, 33, 121, 121, 121, 121, 121, 121, 28, 59, 28, 77, 28, 28, 121, 121, 28, 20, 20, 20, 28, 28, 41, 41, 28, 41, 28, 134, 90, 90, 90, 134, 15, 134, 41, 41, 41, 41, 41, 33, 15, 59, 15, 54, 103, 103, 103, 41, 116, 28, 28, 28, 116, 116, 54, 54, 116, 28, 116, 54, 72, 72, 72, 98, 23, 116, 54, 54, 15, 15, 15, 41, 36, 129, 36, 129, 36, 36, 129, 129, 23, 36, 85, 85, 23, 23, 129, 129, 36, 36, 36, 28, 36, 36, 54, 54, 23, 49, 23, 23, 98, 98, 98, 142, 23, 49, 23, 142, 49, 49, 49, 98, 111, 23, 49, 49, 111, 111, 67, 67, 111, 62, 111, 36, 49, 49, 49, 62, 10, 36, 124, 124, 124, 124, 124, 62, 31, 124, 31, 124, 31, 31, 80, 80, 31, 31, 124, 124, 31, 31, 23, 23, 31, 23, 31, 49, 44, 44, 44, 137, 18, 44, 31, 31, 93, 93, 93, 44, 18, 137, 18, 31, 44, 44, 44, 88, 18, 44, 44, 44, 18, 18, 62, 62, 106, 57, 106, 31, 106, 106, 44, 44, 26, 31, 31, 31, 119, 119, 119, 31, 119, 57, 119, 119, 119, 119, 57, 57, 26, 75, 75, 75, 26, 26, 119, 119, 18, 57, 18, 70, 18, 18, 44, 44, 26, 132, 39, 39, 39, 39, 39, 70, 26, 132, 26, 132, 88, 88, 88, 132, 39, 26, 132, 132, 39, 39, 39, 39, 39, 31, 39, 31, 57, 57, 57, 132, 13, 52, 26, 26, 101, 101, 101, 39, 26, 145, 26, 101, 26, 26, 145, 145, 114, 52, 52, 52, 114, 114, 26, 26, 114, 52, 114, 145, 70, 70, 70, 96, 13, 65, 114, 114, 52, 52, 52, 65, 13, 65, 13, 39, 127, 127, 127, 39, 34, 127, 127, 127, 34, 34, 127, 127, 34, 127, 34, 65, 83, 83, 83, 171, 21, 34, 127, 127, 34, 34, 34, 65, 34, 26, 34, 26, 34, 34, 52, 52, 21, 47, 47, 47, 21, 21, 47, 47, 96, 34, 96, 140, 96, 96, 47, 47, 21, 140, 21, 21, 47, 47, 47, 96, 21, 91, 21, 47, 47, 47, 47, 140, 109, 21, 65, 65, 109, 109, 60, 60, 109, 34, 109, 153, 47, 47, 47, 60, 16, 34, 34, 34, 122, 122, 122, 153, 122, 34, 122, 60, 122, 122, 122, 122, 29, 122, 60, 60, 29, 29, 78, 78, 29, 78, 29, 104, 122, 122, 122, 73, 29, 60, 21, 21, 21, 21, 21, 73, 29, 47, 29, 135, 42, 42, 42, 135, 29, 42, 42, 42, 29, 29, 135, 135, 91, 135, 91, 42, 91, 91, 135, 135, 16, 29, 135, 135, 42, 42, 42, 86, 42, 42, 42, 42, 42, 42, 34, 34, 16, 60, 60, 60, 16, 16, 55, 55, 104, 29, 104, 148, 104, 104, 42, 42, 117, 148, 29, 29, 29, 29, 29, 179, 117, 148, 117, 29, 55, 55, 55, 148, 117, 117, 29, 29, 117, 117, 55, 55, 73, 148, 73, 47, 73, 73, 99, 99, 24, 68, 117, 117, 55, 55, 55, 117, 16, 68, 16, 55, 16, 16, 42, 42, 37, 130, 130, 130, 37, 37, 130, 130, 37, 130, 37, 68, 130, 130, 130, 117, 24, 130, 37, 37, 86, 86, 86, 130, 24, 174, 24, 86, 130, 130, 130, 37, 37, 37, 37, 37, 37, 37, 29, 29, 37, 29, 37, 29, 55, 55, 55, 130, 24, 50, 50, 50, 24, 24, 24, 143, 99, 50, 99, 37, 99, 99, 143, 143, 24, 99, 50, 50, 24, 24, 143, 143, 50, 24, 50, 37, 50, 50, 99, 99, 112, 94, 24, 24, 50, 50, 50, 50, 112].__getitem__)[k - 1]


from heapq import heappush, heappop

class Solution:
    dp = {}
    
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        heap = []
        
        for i in range(lo, hi+1):
            heappush(heap, [self.getPower(i), i])
        
        if len(heap) < k:
            return -1
        
        result = heappop(heap)
        for i in range(1, k):
            result = heappop(heap)
            
        return result[1]
        
        
        
    def getPower(self, n: int) -> int:
        if n == 1:
            return 1
        
        if n in self.dp:
            return self.dp[n]
        
        result = 0
        
        if n % 2 == 0:
            result = 1 + self.getPower(n // 2)
        else:
            result = 1 + self.getPower(n * 3 + 1)
            
        self.dp[n] = result
        return result

from functools import lru_cache
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        res = []
        for i in range(lo, hi + 1):
            res.append((self.power(i), i))
        res.sort()
        return res[k - 1][1]

    @lru_cache
    def power(self, num):
        if num == 1:
            return 0
        if num % 2 == 0:
            return 1 + self.power(num // 2)
        else:
            return 1 + self.power(3 * num + 1)
        
        # res = 0
        # while num != 1:
        #     if num % 2 == 0:
        #         num /= 2
        #     else:
        #         num = 3 * num + 1
        #     res += 1
        # return res


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d={}
        for i in range(lo,hi+1):
            c=0
            t=i
            while(i!=1):
                if i%2==0:
                    i=i//2
                    c+=1
                    
                else:
                    i=3*i+1
                    c+=1
            d[t]=c
        f=sorted(list(d.items()),key=lambda kv: kv[1])
        return f[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def helper(x):
            steps=0
            while x!=1:
                if x&1:
                    x=x*3+1
                else: x//=2
                steps+=1
            return steps
        
        lookup={}
        for x in range(lo,hi+1):
            lookup[x]=helper(x)
        ans=sorted(lookup.items(),key=lambda x:x[1])
        return ans[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        for num in range(lo, hi+1):
            steps = 0
            tmp = num
            while num > 1:
                if num%2:
                    num = 3*num + 1
                else:
                    num //= 2   
                steps += 1
            res.append((steps, tmp))
        res.sort()
        return res[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def helper(x):
            steps=0
            while x!=1:
                if x&1:
                    x=x*3+1
                else: x//=2
                steps+=1
            return steps
        
        lookup={}
        for x in range(lo,hi+1):
            lookup[x]=helper(x)
        return sorted(lookup.items(),key=lambda x:x[1])[k-1][0]

from functools import lru_cache
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache
        def helper(x):
            steps=0
            while x!=1:
                if x&1:
                    x=x*3+1
                else: x//=2
                steps+=1
            return steps
        
        lookup={}
        for x in range(lo,hi+1):
            lookup[x]=helper(x)
        return sorted(lookup.items(),key=lambda x:x[1])[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        count = 0
        answers = []
        numbers = []
        memo ={}
        for number in range(lo,hi+1):
            original = number
            numbers.append(numbers)
            count = 0
            while number != 1:
                if number % 2 == 0:
                    number = number //2
                    count = count + 1
                else:
                    number = 3* number + 1
                    count = count + 1
            memo[original]=count
        
        sort_memo = sorted(list(memo.items()), key=lambda x: x[1], reverse=False)
        return sort_memo[k-1][0]
        
        
        
        
        
        
#create a range from lo to hi
#while k does not equal 1 do the formula
#each tiomke add 1 to count



class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d   =   {}
        for i in range(lo,hi+1):
            self.pow(i,i,d,0)
            #print(d)
        d1  =   OrderedDict(sorted(list(d.items()),key=lambda x:x[1]))
        l   =   list(d1.keys())
        return l[k-1]
            
    def pow(self,n1,n,d,c):
        if n    ==  1:
            d[n1]   =   c
            return 
        if  n%2 ==0:
            n   =   n/2
        elif n%2    ==  1:
            n   =   n*3 +   1
        c   +=  1
        if n in d:
            d[n1]   =   c   +   d[n]
            return
        self.pow(n1,n,d,c)
        
            
            


class Solution:
    def power(self, number: int):
        count = 0
        while number > 1:
            if number % 2:
                number = 3 * number + 1
            else:
                number //= 2
            count += 1
        return count
        
    def getKth(self, lo: int, hi: int, k: int) -> int:
        numbers_power = sorted([(self.power(number), number) for number in range(lo, hi + 1)])
        return numbers_power[k - 1][1]


class Solution:
    
    def get_power(self, n):
        
        num = 0
        
        while n != 1:
            
            if n % 2 == 0:
                n //= 2
            else:
                n = 3 * n + 1
            num += 1
            
        return num
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        power = {}
        
        for i in range(lo, hi + 1):
            power[i] = self.get_power(i)
            
        return sorted(list(power.keys()), key=lambda x: power[x])[k-1]
            
            
            


cache = {1: 0}
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def get_power(x, count = 0):
            if x in cache:
                return cache[x] + count
            return get_power(x * 3 + 1 if (x & 1) else x // 2, count + 1)
        cache.update({i:get_power(i) for i in range(lo, hi + 1) if i not in cache})
        return sorted((x for x in list(cache.items()) if lo <= x[0] <= hi), key=lambda x:x[1])[k - 1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = {}
        if(lo==1 and hi==1 and k==1):
            return 1
        
        def count_steps(x):
            cnt = 0
            if(x==1):
                return cnt;
            while(x>1):
                if x%2 == 0:
                    x = x//2
                else:
                    x = x*3 + 1
                cnt+=1
            return cnt
        
        for i in range(lo,hi+1):
            res[i] = count_steps(i)
        return sorted(list(res.items()),key = lambda x:x[1])[k-1][0]



def power_value(x):
    pv = 0
    while x != 1:
        if x % 2 == 0:
            x = x // 2
        else:
            x = 3 * x + 1
        pv += 1
    return pv

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_values = []
        for x in range(lo, hi+1):
            pv_x = power_value(x)
            power_values.append((x,pv_x))
        return sorted(power_values, key=lambda e: e[1])[k-1][0]
                
            
            


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(n):
            counter = 0
            while n!=1:
                counter+=1
                if n %2 == 0:
                    n = n//2
                else:
                    n = 3*n+1
            return counter
        key = [x for x in range(lo,hi+1)]
        value = [power(x) for x in key]
        ans = list(zip(key,value))
        sorted_ans = sorted(ans , key = lambda t:t[1])
        return sorted_ans[k-1][0]


from collections import defaultdict
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # adj=defaultdict(set)
        po = dict()
        for i in range(lo,hi+1):
            temp=0
            curr=i
            while curr!=1:
                if curr&1:
                    child=curr*3+1
                else:
                    child=curr//2
                # adj[curr].add(child)
                curr=child
                temp+=1
            po[i]=temp
        
        res=sorted(po.items(),key = lambda x : x[1])
        return res[k-1][0]

class Solution:
    def __init__(self):
        self.cached_pv = {}

    def power_value(self, x):
        x_orig = x
        if x in self.cached_pv:
            return self.cached_pv[x]
        pv = 0
        while x != 1:
            if x % 2 == 0:
                x = x // 2
            else:
                x = 3 * x + 1
            pv += 1
        self.cached_pv[x_orig] = pv
        return pv

    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_values = []
        for x in range(lo, hi+1):
            pv_x = self.power_value(x)
            power_values.append((x,pv_x))
        return sorted(power_values, key=lambda e: e[1])[k-1][0]
                
            
            


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dict = defaultdict()
        for i in range(lo,hi+1):
            steps=0
            j=i
            while i!=1:
                if i%2==0:
                    i=i//2
                else:
                    i = 3*i + 1
                
                steps+=1
                
            dict[j] = steps
            
        dict = sorted(dict.items(), key=lambda x: x[1])

            
        return dict[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(n):
            counter = 0
            while n!=1:
                counter+=1
                if n %2 == 0:
                    n = n//2
                else:
                    n = 3*n+1
            return counter
        ans = [(x,power(x)) for x in range(lo,hi+1)]
        sorted_ans = sorted(ans , key = lambda t:t[1])
        return sorted_ans[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def fun(n):
            if n==1:return 0
            ans=0
            while n>1:
                if n%2==0:
                    n//=2
                else:
                    n=n*3+1
                ans+=1
            ans+=1
            return ans
        ans=[] 
        for i in range(lo,hi+1):
            ans.append([i,fun(i)])
        ans.sort(key=lambda x:x[1])
        for i in range(k):
            if i==k-1:
                return ans[i][0]
        


class Solution:
    power = {}
    def get_power(self, num):
        if num == 1:
            return 0
        if num in self.power:
            return self.power[num]
        if num % 2 == 0:
            self.power[num] = self.get_power(num // 2) + 1
        else:
            self.power[num] = self.get_power(3 * num + 1) + 1
        
        return self.power[num]
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_vals = {
            val: self.get_power(val) for val in range(lo, hi+1)
        }
        vals = [k for k, v in sorted(power_vals.items(), key=lambda x: (x[1], x[0]))]
        return vals[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        
        lst = []
        def power(s) -> int:
            count =0
            while s!=1:
                
                if s%2 ==0:
                    s = s//2
                    count = count + 1
                else:
                    s = 3*s +1
                    count = count+1
            
            return count, s
        
        for i in range(lo, hi+1):
            
            lst.append((i,power(i)))
            
            
        
        
        lst.sort(key = lambda x : x[1])
        return lst[k-1][0]
            
            
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(x):
            r = 0
            while x > 1:
                if x % 2 == 0:
                    # x /= 2
                    x >>= 1
                else:
                    x = 3*x + 1
                r += 1
            return r
        
        array = (i for i in range(lo, hi+1))
        array = sorted(array, key=lambda x: power(x))
        
        return array[k-1]

class Solution:
    def calc(self, num):
        count = 0 
        while num != 1:
            if num % 2 == 0:
                num = num // 2
            else:
                num = 3 * num + 1
            count += 1
        return count
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        counts = []
        keys = [i for i in range(lo, hi+1)]
        dict = {}
        
        for i in range(lo, hi+1):
            ans = self.calc(i)
            counts.append(ans)
            
        for key in keys:
            for count in counts:
                dict[key] = count
                counts.remove(count)
                break
                
        dict = {k:v for k, v in sorted(list(dict.items()), key = lambda item: item[1])}
        final = [key for key in list(dict.keys())]
        return final[k-1]
            
            


class Solution:
    def getKth(self, lo, hi, k):
        dic={}
        for n in range(lo,hi+1):
            steps = self.countStep(n)
            dic[n] = steps
        return sorted(dic.items(), key=lambda x:(x[1],x[0]))[k-1][0]

    def countStep(self,m):
        step=0
        while m!=1:
            if m%2==0:
                m //= 2
            else:
                m = m*3 + 1
            step += 1
        return step

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(x):
            res=0
            while(x!=1):
                if x%2==0:
                    x=x>>1
                else:
                    x=x*3+1
                res+=1
            return res
        x=sorted([i for i in range(lo,hi+1)],key=power)
        return x[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        arr = []
        for i in range(lo, hi + 1):
            counter = 0
            num = i
            while num != 1:
                if num % 2 == 1:
                    num = 3 * num + 1
                else:
                    num = num // 2
                counter += 1
            arr.append([i, counter])
        arr.sort()
        for i in arr:
            i[0], i[1] = i[1], i[0]
        arr.sort()
        return arr[k - 1][1]

import heapq

class Solution:
    
    def calculateSteps(self, num):
        count = 0
        while num > 1:
            if num%2==0:
                num = num//2
            else:
                num = (3*num) + 1
            count+=1
        return count
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        vals = []
        for num in range(lo, hi+1):
            heapq.heappush(vals, (self.calculateSteps(num), num))
        
        print(vals)
        count = 1
        val = None
        while count < k:
            heapq.heappop(vals)
            count+=1
        return heapq.heappop(vals)[1]
            
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        res = []
        
        for i in range(lo,hi+1):
            sol = [i]
            
            count = 0
            
            while i != 1:
                if i %2 == 0:
                    i//=2
                else: 
                    i = 3*i+1
                count += 1
            
            sol = [count, sol[0]]
            res.append(sol)
        
        result = sorted(res)
        
        
        ff = [x[1] for x in result]
        return ff[k-1]

class Solution:
    def get_power(self, n):
      res = 0
      while n != 1:
        if n % 2 == 0:
          n //= 2
        else:
          n = 3*n+1
        res += 1
      return res
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
      array = []
      for i in range(lo, hi+1):
        array.append((i, self.get_power(i)))
      array.sort(key = lambda x:(x[1], x[0]))
      return array[k-1][0]

class Solution:
    @staticmethod
    def compute_power(x, d={}):
        if x in d: return d[x]
        xcopy, steps = x, 0
        while x != 1 and x not in d:
            x = 3 * x + 1 if x % 2 else x//2
            steps += 1 + d[x] if x in d else 1
        d[xcopy] = steps
        return steps
    
    def getKth(self, lo, hi, k):
        vals = list(range(lo, hi+1))
        vals.sort(key=lambda x: self.compute_power(x))
        return vals[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        ans = {}
        
        for i in range(lo,hi+1):
            j = i
            s=0
            while(i != 1):
                if(i % 2 == 0):
                    i = i // 2
                else:
                    i = i * 3 + 1
                s =s+1
                
            ans[j] = s
        
        ans = sorted(list(ans.items()), key=lambda x: x[1])
        
        return(ans[k-1][0])
        
        
            
            


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def getPower(x):
            count = 0
            while x != 1:
                if x % 2 == 0:
                    x = x // 2
                else:
                    x = 3 * x + 1
                count += 1
            return count
        
        output = [[getPower(x), x] for x in range(lo, hi + 1)]
        output.sort(key = lambda x: (x[0], x[1]))
        return output[k-1][1]

class Solution:
    def __init__(self):
        self.cache = {1: 0,2: 1,3: 7,4: 2}

    def getPower(self, n):
        after = 0
        steps = 0
        if n % 4 == 0:
            after = n // 4
            steps = 2
        elif n % 4 == 1:
            after = n // 4 * 3 + 1
            steps = 3
        elif n % 4 == 2:
            after = n // 4 * 3 + 2
            steps = 3
        else:
            after = n // 4 * 9 + 8
            steps = 4 
        if after in list(self.cache.keys()): 
            return self.cache[after] + steps
        else:
            return self.getPower(after) + steps

    def getKth(self, low, high, k):
        data = [self.getPower(i) for i in range(low, high + 1)]
        sorted_data = sorted(zip(data, list(range(len(data)))), key= lambda x:x[0])
        return sorted_data[k - 1][1] + low


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        heap = []
        for i in range(lo, hi+1):
            ret = i
            steps = 0
            while ret != 1:
                if ret % 2 == 0:
                    ret = ret // 2
                else:
                    ret = 3 * ret + 1
                steps += 1

            heapq.heappush(heap, (-steps, -i))
            if len(heap) > k:
                heapq.heappop(heap)
        return -(heap[0][1])

class Solution:
    #calc=[]
    def findPower(self,ele):
        #self.calc=[]
        ctr=0
        while ele!=1:
            if ele%2==0:
                ele=ele//2
            else:
                ele=3*ele+1
            #self.calc.append(ele)
            ctr +=1
        return ctr
            
            
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powmat=[]
        for i in range(lo,hi+1):
            ct=self.findPower(i)
            powmat.append([ct,i])
        powmat.sort()
        print(powmat)
        return powmat[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        arr = []
        for i in range(lo, hi + 1):
            arr.append([self.getPower(i), i])
        
        arr.sort(key=lambda x: (x[0], x[1]))
        return arr[k - 1][1]
        
    def getPower(self, number: int) -> int:
        count = 0
        
        while number != 1:
            if number % 2 == 1:
                number = 3 * number + 1
            else:
                number //= 2
            count += 1
        
        return count

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(x):
            count = 0
            while x > 1:
                if x % 2:
                    x = 3* x + 1
                else:
                    x = x /2
                count +=1
            return count
        return sorted(range(lo,hi+1), key=power)[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        res = []
        
        for i in range(lo, hi+1):
            count = 0 
            j = i
            while j > 1:
                if j & 1:
                    j = 3*j + 1
                else:
                    j //= 2
                count += 1
            res.append((count, i))
            
        res.sort()
        return res[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        arr = []
        def power(x):
            count = 0
            while(x!= 1):
                if (x%2 == 0):
                    x = x//2
                    count += 1
                elif(x%2 != 0):
                    x = 3 * x + 1
                    count += 1
            return count
        for i in range(lo, hi+1):
            p = power(i)
            arr.append((i, p))
        arr = [j[0] for j in sorted(arr, key = lambda x: x[1])]
        #print(arr)
        return arr[k-1]


class Solution:
    dp = {}
    
    def findPower(self, num):
        way = [num]
        ops = 0
        
        while num != 1 and num not in self.dp:
            if num % 2 == 0:
                num /= 2
            else:
                num = (num * 3 + 1)
            
            way.append(num)
            ops += 1
        
        if num in self.dp:
            ops += self.dp[num]
            
        for prev in way:
            self.dp[prev] = ops
            ops-=1
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        
        for i in range(lo, hi+1):
            self.findPower(i)
            res.append((i, self.dp[i]))
        
        res = sorted(res, key=lambda x: x[1])
        return res[k-1][0]
        


from operator import itemgetter
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        z = []
        for i in range(lo, hi + 1):
            count = 0
            f=i
            while i != 1:
                if i % 2 == 0:
                    i = i / 2
                    count += 1
                else:
                    i = 3 * i + 1
                    count += 1
            z.append([f, count])
        return sorted(z, key=itemgetter(1))[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res=[]
        dict1={}
        for i in range(lo,hi+1,1):
            c=0
            r=[]
            v=0
            p=i
            while(c==0):
                if(i==1):
                    c=1
                elif(i%2==0):
                    i=i//2
                    v+=1
                    while(i%2==0):
                        i=i//2
                        v+=1
                else:
                    i=i*3+1
                    v+=1
            r.append(p)
            r.append(v)
            res.append(r)
        res.sort(key=lambda x:x[1])
        print(res)
        return res[k-1][0]

class Solution:

    def power_value(self, n):
        count = 0
        while n != 1:
            count += 1
            if n % 2 == 0:
                n /= 2
            else:
                n = n*3 + 1
        return count
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        vals = sorted(list(range(lo, hi+1)), key=self.power_value)
        return vals[k-1]



class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dic={}
        def determine_power(a):
            power=0
            while (a>1):
                if a%2:
                    a=3*a+1
                    power+=1
                else:
                    a=a/2
                    power+=1
            return power

        for element in range (lo,hi+1):
            p=determine_power(element)
            dic.update({element:p})
        dd=sorted(list(dic.items ()),key =lambda x:x[1])# sort by value 
        return (dd[k-1][0])


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        ans = {}
        
        for num in range(lo, hi + 1):
            num_copy = num
            steps = 0
            while num_copy != 1:
                if num_copy % 2 == 0:
                    num_copy = num_copy / 2
                    steps += 1
                else:
                    num_copy = 3 * num_copy + 1
                    steps += 1
            ans[num] = steps
        
        return(sorted(list(ans.items()), key=lambda item: item[1]))[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def powerx(x):
            p=0
            while x !=1 :
                if x % 2 == 0:
                    x = x/2
                else:
                    x = x*3+1
                p+=1
            return p
        dic = {}
        for i in range(lo, hi+1):
            dic[i] = powerx(i)
        dic_ordered = sorted(list(dic.items()), key=lambda x: x[1])
        return(dic_ordered[k-1][0])
                


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPower(x):
          count = 0
          while(x != 1):
            if (x % 2 == 0):
              x /= 2
              count += 1
            else:
              x = 3 * x + 1
              count += 1
          return count
        dic = {}
        for i in range(lo, hi+1):
          dic[i] = getPower(i)
        
        sorted_dic = sorted(list(dic.items()), key = lambda x: x[1], reverse=False)
        print(sorted_dic)
        for i in range(len(sorted_dic)):
          if (i == k-1):
            return sorted_dic[i][0]
        
        
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def getPowerValue(num):
            num_steps = 0
            while num != 1:
                if num % 2 == 0:
                    num = num /2
                else:
                    num = 3 * num + 1
                num_steps +=1
            return num_steps
            
            
        powervalues = sorted([i for i in range(lo, hi + 1)], key = getPowerValue)
        #print(powervalues)
        return powervalues[k - 1]


class Solution:
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_values = defaultdict()
        
        for i in range(lo, hi + 1):
            count = 0
            x = i
            while x != 1:
                if x % 2 == 0:
                    x /= 2
                else:
                    x = 3 * x + 1
                count += 1
            power_values[i] = count
            
        sorted_d = sorted(power_values.items(), key=lambda x: x[1])

        return sorted_d[k-1][0]

class Solution:
    
    powers = {1:0}
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_range = []
        for i in range(lo, hi + 1):
            tup = (i,self.getPower(i))
            power_range.append(tup)
        power_range.sort(key = lambda x: x[1])
        return power_range[k-1][0]
        
    def getPower(self, num):
        if num in self.powers:
            return self.powers[num]
        if num % 2 == 1:
            power = self.getPower((num*3)+1) + 1
            self.powers[num] = power
            return power
        else:
            power = self.getPower(num/2) + 1
            self.powers[num] = power
            return power

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def getPowerValue(num):
            num_steps = 0
            while num != 1:
                if num % 2 == 0:
                    num = num /2
                else:
                    num = 3 * num + 1
                num_steps +=1
            return num_steps
            
            
        powervalues = sorted([(i, getPowerValue(i)) for i in range(lo, hi + 1)], key = lambda x: x[1])
        #print(powervalues)
        return powervalues[k - 1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPower(num):
            if num==1:
                return 1
            count = 0
            while num!=1:
                if num%2==0:
                    num = num/2
                    count += 1
                else:
                    num = 3*num + 1
                    count += 1
            return count
        dic = {}
        for i in range(lo, hi+1):
            dic[i] = getPower(i)
        dic = {k:v for k,v in sorted(dic.items())}
        dic = {k:v for k,v in sorted(list(dic.items()), key = lambda item: item[1])}
        return list(dic.keys())[k-1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted(map(lambda x: (self.myfunc(x),x), range(lo,hi+1)) )[k-1][1]
    
    def myfunc(self,x):
        transformations = 0
        while (x!=1):
            if x%2==0:
                x=x/2
            else:
                x= 3*x+1
            transformations+=1
        return transformations

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        indexList = [i for i in range(lo, hi+1, 1)]
        powerList = [self.getPower(i) for i in indexList]
        sortedIndex = [x for _,x in sorted(zip(powerList,indexList))]
        return sortedIndex[k-1]
    
    def getPower(self, x: int) -> int:
        count = 0;
        while (x != 1):
            if (x%2 == 0):
                x = x/2
            else:
                x = 3*x +1
            count+=1
        return count
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        low=lo
        high=hi
        countlist=[]
        intgererlist=[]
        for lo in range(low,high+1):
            i=lo
            count=0
            while lo>1:
                if lo%2==0:
                    lo=lo//2
                else:
                    lo=(3*lo)+1
                count+=1
            countlist.append(count)
            intgererlist.append(i)

        ziped=zip(countlist,intgererlist)
        o=0
        for i,j in sorted(ziped):
            o+=1
            if o==k:
                return (j)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powerSteps = []
        for i in range(lo, hi + 1):
            powerSteps.append((self.getPowerSteps(i), i))
        powerSteps.sort()
        return powerSteps[k - 1][1]
        
        
    def getPowerSteps(self, value):
        steps = 0
        while value != 1:
            if value % 2 == 0:
                value = value / 2
            else:
                value = 3 * value + 1
            steps += 1
        return steps

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d=dict()
        for i in range(lo,hi+1):
            res=0
            x=i
            while i!=1:
                if i%2==1:
                    i=3*i+1
                else:
                    i=i/2
                res+=1
            d[x]=res
            
        di={k:v for k,v in sorted(d.items(), key=lambda item: item[1])}
        return list(di.keys())[k-1]

class Solution:
    def getKth(self, lo, hi, k):
        def power(x):
            if x&1:
                return 0 if x==1 else 1+power( 3*x + 1 )
            return 1+power(x >> 1)
        A = [ (power(x),x) for x in range(lo,hi+1) ]
        return sorted(A)[k-1][1]

def fun(x):
    cnt = 0
    while x != 1:
        x = x/2 if x%2==0 else 3*x+1
        cnt += 1
    return cnt

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        lst = sorted([(x, fun(x)) for x in range(lo, hi+1)], key=lambda x: (x[1], x[0]))
        print(lst, k)
        return lst[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dic = {}
        for x in range(lo, hi+1):
            dic[x] = self.get_power(x, 0)
        dic_2 = {k: dic[k] for k in sorted(dic, key=dic.get)}
        return list(dic_2.keys())[k-1]
    def get_power(self, x:int, p:int) -> int:
        while x!=1:
            if x%2==0:
                x//=2
            else:
                x = 3*x+1
            p+=1
        return p


@lru_cache(maxsize=1000)
def pow(n: int):
    if n == 1:
        return 1
    if n % 2 == 0:
        return 1 + pow(n//2)
    else:
        return 1 + pow(3 * n + 1)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        l = list(range(lo, hi + 1))
        l.sort(key = lambda x: (pow(x),x) )
        return l[k-1]

class Solution:
    def getSteps(self, x):
        res = 0
        while x != 1:
            if x % 2 == 1:
                x = 3 * x + 1
            else:
                x = x / 2
            res += 1
        return res
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        for i in range(lo, hi+1, 1):
            val = self.getSteps(i)
            res.append([i, val])
            
        print(res)
        res.sort(key = lambda x: (x[1], x[0]))
        ans= [item[0] for item in res]
        print(ans)
        return ans[k-1]

import functools

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        arr = []
        
        for i in range(lo, hi + 1):
            arr.append([i,getPower(i)])  
        
        arr.sort(key=functools.cmp_to_key(compareByK))
        
        return arr[k - 1][0]
        
def getPower(n):
    steps = 0
    while n != 1:
        steps +=1
        if n % 2 == 0:
            n = n / 2
        else:
            n = n * 3 + 1

    return steps
    
def compareByK(x, y):
    powerX = x[1]
    powerY = y[1]

    if powerX < powerY:
        return -1
    elif powerX > powerY:
        return 1
    else:
        if x[0] < y[0]:
            return -1
        elif x[0] > y[0]:
            return 1
        else:
            return 0

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        int_to_steps = {}
        for x in range(lo, hi + 1):
            start = x
            steps = 0
            while x != 1:
                steps += 1
                if x % 2 == 0:
                    x = x / 2
                else:
                    x = x * 3 + 1
            # if steps not in steps_to_ints:
            #     steps_to_ints[steps] = []
            # steps_to_ints[steps].append(steps)
            int_to_steps[start] = steps
        
        return sorted(list(int_to_steps.items()), key=lambda item: item[1])[k - 1][0]


from collections import defaultdict
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # adj=defaultdict(set)
        po = dict()
        for i in range(lo,hi+1):
            po[i]=0
            curr=i
            while curr!=1:
                if curr&1:
                    child=curr*3+1
                else:
                    child=curr//2
                # adj[curr].add(child)
                curr=child
                po[i]+=1
            
        
        res=sorted(po.items(),key = lambda x : x[1])
        return res[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        nums = list(range(lo, hi + 1))
        count = 0
        while True:
            for i in range(len(nums)):
                if nums[i] == 0:
                    continue
                elif nums[i] == 1:
                    count += 1
                    nums[i] = 0
                    if count == k:
                        return lo + i
                    
                elif nums[i] % 2 == 0:
                    nums[i] = nums[i] // 2
                else:
                    nums[i] = 3 * nums[i] + 1
                    
                if nums[i] == 1:
                    count += 1
                    nums[i] = 0
                    
                    if count == k:
                        return lo + i
                    
        
                        
                    
                    
            
        
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        if lo == hi:
            return lo
        
        ans = []
        for i in range(lo, hi+1):
            num = i
            ctr = 0
            while num != 1:
                if num % 2 != 0: #odd
                    num = (num * 3) + 1
                else:
                    num = num/2
                ctr+=1
            ans.append((ctr, i))
            
        return sorted(ans, key = lambda x: x[0])[k-1][1]
            
                


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def power(n: int):
            step = 0;
            while n != 1:
                step += 1
                if n % 2 == 0:
                    n = n / 2
                else:
                    n = n * 3 + 1
            return step
        
        nums = list(range(lo, hi + 1))
        powers = [power(n) for n in nums]
        sortedIndex = list(range(0, hi - lo + 1))
        sortedIndex = sorted(sortedIndex, key = lambda x: (powers[x], nums[x]))
        return sortedIndex[k - 1] + lo


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powers = {}
        l = []
        for i in range(lo, hi+1):
            j = i
            stack = []
            stack.append(j)
            if j not in powers:
                while j != 1:
                    if j%2 == 0:
                        j = j//2
                        stack.append(j)
                    else:
                        j = j*3 + 1
                        stack.append(j)
                cnt = 0
                while stack:
                    j = stack.pop()
                    powers[j] = cnt
                    cnt += 1
            l.append((i, powers[i]))
        l = sorted(l, key = lambda x:(x[1],x[0]))
        #print(l)
        return l[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(n: int)-> int:
            step = 0
            while n>1:
                step+=1
                if n % 2 == 0:
                    n = n/2
                else:
                    n = 3 * n + 1
            return step
        interval = [i for i in range(lo,hi+1)]
        pwr = [[j,power(j)] for j in range(lo,hi+1)]
        # print(pwr)
        pwr = sorted(pwr,key=lambda x: x[1])
               
        return (pwr[k-1][0])


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        arr_of_powers = {}
        
        def get_int_power(num):
            
            pwr = 0
            temp = num 
            while temp != 1:
                pwr += 1
                if temp % 2 == 0:
                    temp /= 2
                elif temp % 2 == 1:
                    temp = 3 * temp + 1
            return pwr
        
        for num in range(lo, hi+1):
            arr_of_powers[num] = get_int_power(num)

        interval = sorted(arr_of_powers.items(), key=lambda x: x[1])
            
        return interval[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache(None)
        def power(x):
            if x == 1: return 0
            if x % 2 == 0 : return 1 + power(x//2)
            return 1 + power(3*x+1)
        return sorted(range(lo,hi+1),key=power)[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getSteps(lo):
            steps = 0
            reduced = lo
            while reduced != 1:
                if reduced % 2 == 0:
                    reduced = reduced / 2
                else:
                    reduced = 3*reduced+1
                steps += 1

            return (steps)


        a = {}
        for i in range(lo, hi+1):
            steps = getSteps(i)
            if steps not in a:
                a[steps] = [i]
            else:
                a[steps].append(i)

        r = []
        for key in sorted(a.keys()):
            for val in a[key]:
                r.append(val)

        return r[k-1]

# 递归
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getF(x):
            if x == 1:
                return 0
            return (getF(3*x+1) + 1) if x % 2 == 1 else (getF(x // 2) + 1)
        
        weights = list(range(lo, hi + 1))
        weights = sorted(weights, key = lambda x : getF(x))
        return weights[k - 1]
    
# 本地记忆


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powers = []
        for i in range(lo, hi+1):
            index = i
            steps = 0
            while i != 1: 
                if i % 2 == 0: 
                    i = i / 2
                    steps += 1
                else: 
                    i = 3 * i + 1
                    steps += 1
            powers.append([steps, index])         
        sortPowers = sorted(powers)
        return sortPowers[k-1][1]

# brute force
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(num):
            res = 0
            while num != 1:
                if num % 2 == 0:
                    num = num / 2
                else:
                    num = (3 * num) + 1
                res += 1
            return res
        heap = []
        for i in range(lo, hi + 1):
            heap.append((power(i), i))
        heapq.heapify(heap)
        for i in range(k - 1):
            heapq.heappop(heap)
        return heap[0][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dic = {}
        for i in range(lo,hi+1):
            power = self.findPower(i, 0)
            dic[i] = power
        sortedValue = sorted(dic.items(), key=lambda x:x[1])
        return (sortedValue[k-1][0])
    
    def findPower(self, num, count):
        if num == 1:
            return count
        elif num % 2 == 0:
            return self.findPower(num//2, count+1)
        else:
            return self.findPower(3*num+1, count+1)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def transform(v):
            times = 0
            while v != 1:
                times += 1
                if v % 2 == 0:
                    v = v/2
                else:
                    v = 3*v + 1
            return times
        
        res = []
        
        for x in range(lo,hi+1):
            power = transform(x)
            res.append([power,x])
        
        res.sort(key = lambda x:(x[0],x[1]))
        return res[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        pair = []
        
        def transform(val):
            
            count = 0
            
            while val != 1:
                
                val = val/2 if  val % 2 == 0 else 3 * val + 1
                count += 1
            
            return count
        
        for i in range(lo, hi + 1):
            
            pair.append(( transform(i), i))
        print(sorted(pair))
        return sorted(pair)[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(x):
            if x == 1:
                return 0
            if x % 2 == 0:
                return 1 + power(x // 2)
            return 1 + power(3 * x + 1)

        return sorted(range(lo, hi+1), key=power)[k-1]
    
        len_powers = [0]*(hi-lo+1)
        for n in range(lo,hi+1):
            ls_power= [n] 
            while ls_power[-1]!=1:
                #print(ls_power)
                if ls_power[-1]%2==0:
                    ls_power.append(ls_power[-1]//2)
                else:
                    ls_power.append(3*ls_power[-1]+1)
            len_powers[n-lo] = len(ls_power)-1
        return sorted(zip(range(lo,hi+1),len_powers),key = lambda x: [x[1],x[0]])[k-1][0] 

class Solution:
    def getKth(self, lo, hi, k):
        #
        memo = { 1:0 }
        def power(x):
            if x in memo:
                return memo[x]
            memo[x] = res = 1 + power( (3*x+1) if x&1 else (x >> 1) )
            return res
        #
        A = [ (power(x),x) for x in range(lo,hi+1) ]
        return sorted(A)[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        nums = [i for i in range(lo,hi+1)]
        powers = [0]*len(nums)
        for i in range(len(nums)):
            cur = nums[i]
            while(cur != 1):
                if cur%2 == 0:
                    cur = cur/2
                else:
                    cur = 3*cur + 1
                powers[i] += 1
        result = [x for _,x in sorted(zip(powers,nums))]
        return result[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPower(n):
            step = 0
            while n != 1:
                n = 3 * n + 1 if n % 2 else n / 2
                step += 1
            return step
        powers = sorted([(i, getPower(i)) for i in range(lo, hi + 1)], key=lambda x:(x[1], x[0]))
        return powers[k - 1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPow(n):
            c=0
            while n!=1:
                if n%2==0:
                    n//=2
                else:
                    n=3*n+1
                c+=1
            return c
        def func():
            arr={i:getPow(i) for i in range(lo,hi+1)}
            v=list(set(arr.values()))
            v.sort()
            fin=[]
            for i in v:
                t=[]
                for a,b in arr.items():
                    if b==i:
                        t.append(a)
                t.sort()
                fin.extend(t)
            return fin[k-1]
        return func()

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        heap = []
        for i in range(lo, hi+1):
            power = self.computer_power(i)
            heapq.heappush(heap, (power, i))
        
        k_now = 1
        while heap:
            new_power, i = heapq.heappop(heap)
            if k_now == k:
                return i
            k_now += 1
        return result
    
    def computer_power(self, val):
        if val == 1:
            return 0
        
        if val % 2 == 0:
            return 1 + self.computer_power(val // 2)
        else:
            return 1 + self.computer_power(3*val + 1)

class Solution:
    def get_power(self, n):
        if n == 1:
            return 0
        elif n % 2 == 0:
            return 1 + self.get_power(n // 2)
        else:
            return 1 + self.get_power(3 * n + 1)
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        nums = [i for i in range(lo, hi + 1)]
        
        lst2 = []
        for num in nums:
            lst2.append((num, self.get_power(num)))
            
        lst2.sort(key = lambda x : x[1])
        
        return lst2[k - 1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def get_power(x:int, p:int) -> int:
            while x != 1:
                x = x //2 if x %2 == 0 else (3 * x) + 1
                p += 1
            return p
        
        dic = { x: get_power(x, 0) for x in range(lo, hi+1) }
        return sorted(list(dic.items()), key=lambda x: x[1])[k-1][0]



class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        
        def power(num):
            if num == 2:
                return 1
            elif num % 2 == 0:
                return 1 + power(num//2)
            else:
                return 1 + power((3*num)+1)
            
        dic = collections.defaultdict(list)
        
        for i in range(lo,hi+1):
            dic[power(i)].append(i)
            
        for _,v in sorted(dic.items()):
            res += v
            # print(res,len(res),k)
        
        return res[k-1]


class Solution:
    def __init__(self):
        self.memo = {}
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power = [0 for i in range(lo, hi + 1)]
        for i in range(lo, hi + 1):
            if i in self.memo:
                power[i - lo] = self.memo[i]
            else:    
                power[i - lo] = (self.get_power(i, 0), i)
                self.memo[i] = power[i - lo]
        
        power.sort()
        return power[k - 1][1]    
        
    def get_power(self, i, curr_pow):
        if i == 1:
            return curr_pow
        if i % 2 == 0:
            return self.get_power(i / 2, curr_pow + 1)
        else:
            return self.get_power((i - 1) / 2 * 3 + 2, curr_pow + 2)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache(None)
        def power(x):
            if x == 1:
                return 0
            if x % 2 == 0:
                return 1 + power(x // 2)
            return 1 + power(3 * x + 1)

        return sorted(list(range(lo, hi+1)), key=power)[k-1]
            


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(x):
            if x==1: return 0
            if x%2==0:
                return power(x>>1)+1
            else:
                return power(x*3+1)+1
       
        x=sorted([i for i in range(lo,hi+1)],key=power)
        return x[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        heap = []
        for i in range(lo, hi+1):
            power = self.computer_power(i)
            heapq.heappush(heap, (power, i))
        actual_power = -1
        new_power = -1
        actual_list = []
        result = []
        k_now = 1
        while heap:
            new_power, i = heapq.heappop(heap)
            if k_now == k:
                return i
            k_now += 1
            if new_power != actual_power:
                actual_list.sort()
                result = result + actual_list
                actual_list = [i]
            else:
                actual_list.append(i)
        if actual_list:
            actual_list.sort()
            result = result + actual_list
        return result
    
    def computer_power(self, val):
        if val == 1:
            return 0
        
        if val % 2 == 0:
            return 1 + self.computer_power(val // 2)
        else:
            return 1 + self.computer_power(3*val + 1)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dic = {}
        for i in range(lo,hi+1):
            power = self.findPower(i, 0)
            dic[i] = power
        sortedValue = sorted(list(dic.items()), key=lambda x:x[1])
        return (sortedValue[k-1][0])
    
    def findPower(self, num, count):
        if num == 1:
            return count
        elif num % 2 == 0:
            return self.findPower(num//2, count+1)
        else:
            return self.findPower(3*num+1, count+1)


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def helper(num):
            if(num == 1):
                return 0
            # if dp[num] != -1:
            #     return dp[num]
            if num%2 == 0:
                return helper(num//2) + 1
            else:
                return helper((num*3)+1) + 1
            # return dp[num]
         
        # dp = [-1 for i in range(1000000)]
        # dp[1] = 0
        res = []
        for i in range(lo, hi+1):
            res.append((helper(i), i))
        res.sort()
        return res[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        len_powers = [0]*(hi-lo+1)
        for n in range(lo,hi+1):
            ls_power= [n] 
            while ls_power[-1]!=1:
                #print(ls_power)
                if ls_power[-1]%2==0:
                    ls_power.append(ls_power[-1]//2)
                else:
                    ls_power.append(3*ls_power[-1]+1)
            len_powers[n-lo] = len(ls_power)-1
        return sorted(zip(range(lo,hi+1),len_powers),key = lambda x: [x[1],x[0]])[k-1][0] 

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted((get_power_value(x), x) for x in range(lo, hi + 1))[k - 1][1]
def get_power_value(x):
    if x == 1:
        return 0
    return 1 + get_power_value(x / 2 if x % 2 == 0 else x * 3 + 1)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def transform(x):
            steps = 0
            while x != 1:
                if x & 1 == 0:
                    x //= 2
                else:
                    x = (3*x) + 1
                steps += 1
            
            return steps
        
        arr = list(range(lo, hi + 1))
        arr.sort(key = lambda x: (transform(x), x))
        
        return arr[k - 1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        cache = [0] * 999999

        for num in range(lo, hi + 1):
            if cache[num] != 0:  # already visited
                continue

            path = [num]

            while num != 1 and cache[num] == 0:
                if num % 2 == 0:
                    num //= 2
                    path.append(num)
                else:
                    num = num * 3 + 1
                    path.append(num)

            # print(path)

            for idx, n in enumerate(path):
                if cache[n] != 0:
                    break
                cache[n] = len(path) - 1 - idx + cache[path[-1]]

        res = [(i + lo, steps) for i, steps in enumerate(cache[lo:hi + 1])]
        # print(res)
        res = sorted(res, key=lambda _: _[1])
        # print(res)
        return res[k - 1][0]



class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def find_power_value(n: int, steps: int) -> int:
            if n == 2: return steps + 1
            if n % 2 == 0:
                return find_power_value(n // 2, steps + 1)
            return find_power_value(3 * n + 1, steps + 1)
        result = [ ]
        for i in range(lo, hi + 1):
            result.append((find_power_value(i, 0), i))
        result.sort()
        return result[k - 1][1]


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

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = { 1:0 } # Exit Condition Stored in Memory
        def power(x):
            if x in memo:
                return memo[x]
            n = memo[x] = 1 + power( (3*x+1) if x&1 else (x >> 1) )
            return n
        ans = [(x,power(x)) for x in range(lo,hi+1)]
        sorted_ans = sorted(ans , key = lambda t:t[1])
        return sorted_ans[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def process(x, nsteps):
            if x==2:
                return nsteps
            elif x%2==0:
                return process(x//2, nsteps+1)
            else:
                return process(x*3+1, nsteps+1)
            
        sol = []
        for i in range(lo, hi+1):
            sol.append((process(i, 0), i))
        sol.sort()
        # print (sol)
        return sol[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        g={}
        for i in range(lo,hi+1):
            p=self.power(i,0)
            g[i]=p
        s=sorted(list(g.items()),key=lambda x:x[1])
        return(s[k-1][0])
    def power(self, num, count):
        if num == 1:
            return count
        elif num % 2 == 0:
            return self.power(num//2, count+1)
        else:
            return self.power(3*num+1, count+1)


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        x = {}
        for i in range(lo, hi+1):
            j = []
            g = i
            while i != 1:
                if i % 2 == 0:
                    i = i /2
                    j.append(i)
                else:
                    i = 3 * i + 1
                    j.append(i)
            x[g] = len(j)
        x = sorted(x, key = x.get)
        return x[k-1]

class Solution:
    def transform(self, num, count = 0):
        if num == 1:
            return count
        else:
            if num%2 == 0:
                return self.transform(num//2, count + 1)
            else:
                return self.transform(num * 3 + 1, count + 1)

    def getKth(self, lo: int, hi: int, k: int) -> int:
        p_list = []
        for i in range(lo, hi + 1):
            p_list.append((self.transform(i), i))
        
        p_list.sort()
        
        return p_list[k-1][1]

class Solution:
        def getKth(self, lo: int, hi: int, k: int) -> int:
                def getPower(num: int) -> int:
                        if num == 1: return 0
                        if num % 2 == 0: return 1 + getPower(num // 2)
                        if num % 2 == 1: return 1 + getPower(3 * num + 1)
                powers = []
                for cand in range(lo, hi + 1):
                        powers.append((cand, getPower(cand)))
                powers = sorted(powers, key=lambda x: x[1])
                return powers[k - 1][0]

from collections import defaultdict
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        adj=defaultdict(set)
        po = dict()
        for i in range(lo,hi+1):
            temp=0
            curr=i
            while curr!=1:
                if curr&1:
                    child=curr*3+1
                else:
                    child=curr//2
                adj[curr].add(child)
                curr=child
                temp+=1
            po[i]=temp
        
        res=sorted(po.items(),key = lambda x : x[1])
        return res[k-1][0]

import heapq
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def power(num,cou=0):
            if num==1:
                return cou
            if num%2==0:
                num=num//2
                return power(num,cou+1)
            else:
                num=(3*num)+1
                return power(num,cou+1)
        arr=[]
        while(lo<=hi):
            j=power(lo)
            heapq.heappush(arr,(-j,-lo))
            if len(arr)>k:
                heapq.heappop(arr)
            lo+=1
        return -heapq.heappop(arr)[1]

class Solution:
    def getKth(self, lo, hi, k):
        memo = { 1:0 }
        def power(x):
            if x in memo:
                return memo[x]
            memo[x] = res = 1 + power( (3*x+1) if x&1 else (x >> 1) )
            return res
        A = [ (power(x),x) for x in range(lo,hi+1) ]
        return sorted(A)[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def key_func(val):
            def recur(val):
                if val <= 1:
                    return 0
                if val % 2 == 0:
                    return recur(val / 2) + 1
                return recur((val * 3) + 1) + 1
            return recur(val)
        out = [i for i in range(lo, hi+1)]
        out.sort(key=key_func)
        return out[k-1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        output = {}
        for i in range(lo,hi+1):
            a = i
            counter = 0
            while i > 1:
                if i%2 == 0:
                    i  = i/2
                else:
                    i = 3*i + 1
                counter += 1
            output[a] = counter
        output = sorted(output.items(), key=lambda x: x[1])
        return output[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d={}
        def helper(i):
            if i==1:
                return 0
            if i in d:
                return d[i]
            if i%2==0:
                return 1+helper(i//2)
            else:
                return 1+helper(3*i+1)
        ans=[[helper(i),i] for i in range(lo,hi+1)]
        ans.sort()
        return ans[k-1][1]

class Solution:
        def getKth(self, lo: int, hi: int, k: int) -> int:
                def getPower(num: int) -> int:
                        if num == 1: return 0
                        if num % 2 == 0: return 1 + getPower(num // 2)
                        if num % 2 == 1: return 1 + getPower(3 * num + 1)

                powers = []
                for cand in range(lo, hi + 1):
                        powers.append((cand, getPower(cand)))

                powers = sorted(powers, key=lambda x: x[1])
                return powers[k - 1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        st = [0]*(hi+1-lo)
        std={}
        
        for x in range(lo,hi+1):
            i=x
            while (x!=1):
                
                st[i-lo]+=1
                
                if x%2 == 0:
                    x=x/2
                else:
                    x = 3*x+1
                    
            #std[st[i-lo]] = [i]
            if st[i-lo] in list(std.keys()):
                std[st[i-lo]].append(i) 
            else:
                std[st[i-lo]] = [i]
                
        s_val = sorted(list(std.keys()))
        ans = std[s_val[0]]    
        for i in range(1,len(s_val)):
            ans = ans + std[s_val[i]]

        return ans[k-1]
                
            
            


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def find_transform(x):
            k = [x]
            while k[-1] != 1:
                if x%2 == 0:
                    x = x/2
                    k.append(x)
                else:
                    x = x*3 + 1
                    k.append(x)
            return len(k)-1
        #l = [i for i in range(lo,hi+1)]
        power = []
        for i in range(lo,hi+1):
            power.append([i,find_transform(i)])
        return sorted(power,key=lambda x : x[1])[k-1][0]

class Solution:
    #calc=[]
    def findPower(self,ele):
        self.calc=[]
        ctr=0
        while ele!=1:
            if ele%2==0:
                ele=ele//2
            else:
                ele=3*ele+1
            self.calc.append(ele)
            ctr +=1
        return ctr
            
            
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powmat=[]
        for i in range(lo,hi+1):
            ct=self.findPower(i)
            powmat.append([ct,i])
        powmat.sort()
        print(powmat)
        return powmat[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # use DP to cut down on calculation time
        # 1 = 1
        # 2 = 2, 1
        # 3 = 3, 10, 5, 16, 8, 4, 2, 1
        # 4 = 4, 2, 1
        # 5 = 5, 16, 8, 4, 2, 1
        # 6 = 6, 3
        
        dp_steps = {}
        
        def find_power(n: int) -> int:
            if n in dp_steps:
                return dp_steps[n]
            elif n == 1:
                return 0
            else:
                if n % 2 == 0:
                    return 1 + find_power(n//2)
                else:
                    return 1 + find_power(n * 3 + 1)                
        
        results = []
        for i in range(lo, hi+1):
            results.append((find_power(i), i))
        results.sort()
        return results[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        degree_cache = {}
        
        def find_degree(n, degree=0):
            if n == 1:
                return degree
            # if n in degree_cache:
            #     return degree_cache[n]

            if n % 2 == 0:
                degree = find_degree(n//2, degree + 1)
            else:
                degree = find_degree(n*3+1, degree + 1)
            return degree
        d = {}
        for i in range(lo, hi+1):
            d[i] = find_degree(i, 0)
        sd = sorted(d.items(), key=lambda x: (x[1], x[0]))
        return sd[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPower(n):
            if n == 1: return 0
            return (getPower(3 * n + 1) if n % 2 else getPower(n / 2)) + 1
        powers = sorted([(i, getPower(i)) for i in range(lo, hi + 1)], key=lambda x:(x[1], x[0]))            
        return powers[k - 1][0]

from collections import defaultdict

def getPower(i):
    if i==1:
        return 0
    if i%2==0:
        return getPower(i/2) + 1
    else:
        return getPower(i*3+1) + 1

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d=defaultdict(int)
        for i in range(lo, hi+1):
            d[i]=getPower(i)
        sd={k: v for k, v in sorted(list(d.items()), key=lambda item: item[1])}
        
        return list(sd)[k-1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_dic = {}
        powers = []
        for num in range(lo, hi+1):
            powers.append([self.powerOf(num, 0, power_dic), num])
        return sorted(powers, key=lambda x:x[0])[k-1][1]
            
    
    
    def powerOf(self, x, steps, power_dic):
        if x==1:
            return steps
        if x&1 == 0:
            return self.powerOf(x//2, steps+1, power_dic)
        else:
            return self.powerOf(3*x+1, steps+1, power_dic)


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        track = []
        for i in range (lo, hi+1):
            power = 0
            x = i
            while (i != 1):
                if (i % 2 == 0):
                    i = i // 2
                else:
                    i = 3 * i + 1
                power += 1
            track.append([x, power])
        
        sorted_tr = sorted(track, key=lambda x: [x[1], x[0]])
        print(sorted_tr)
        return sorted_tr[k-1][0]
        
        
        
    def getPower (self, c, n):
        if (int(n) == 1):
            return c
        elif (n % 2 == 0):
            self.getPower(c+1, n / 2)
        else:
            self.getPower(c+1, 3 * n + 1)

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d={}
        for n in range(lo,hi+1):
            count = 0
            p=n
            while(n!=1):
                if n%2==0:
                    n=n/2
                    count=count+1
                elif n%2==1:
                    n=3*n+1
                    count=count+1
            d[p]=count
        return sorted(list(d.items()),key = lambda x:x[1])[k-1][0]
                


class Solution:
    def getKth(self, lo, hi, k):
        #
        memo = { 1:0 }
        def power(x):
            if x in memo:
                return memo[x]
            n = memo[x] = 1 + power( (3*x+1) if x&1 else (x >> 1) )
            return n
        #
        A = [ (power(x),x) for x in range(lo,hi+1) ]
        return sorted(A)[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPower(n):
            step = 0
            while n != 1:
                if n%2 == 0: n = int(n/2)
                else: n = n*3+1
                step += 1
            return step
        ans = []
        for i in range(lo, hi+1):
            ip = getPower(i)
            ans.append((ip, i))
        # print(ans)
        ans.sort()
        return ans[k-1][1]
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        nums = []
        for i in range(lo, hi + 1):
            temp, steps = i, 0
            while temp != 1:
                if temp % 2 == 0: temp //= 2
                else: temp = 3 * temp + 1
                steps += 1
            nums.append([i, steps])
        nums = sorted(nums, key=lambda n: n[1])
        return nums[k - 1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        d = {}
        def steps(num, level):
#             if num in d:
#                 return d[num] + level
            
#             d[num] = level
            if num==1:
                return level
            if num%2==0:
                return steps(num/2, level+1)
            else:
                return steps(3*num+1, level+1)
            
        ans = [(steps(x,0), x) for x in range(lo,hi+1)]
        ans.sort()
        return ans[k-1][-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        a=[i for i in range(lo,hi+1)]
        z=[]
        def cv(s,c):
            if s%2==0:
                s=s/2
            else:
                s=3*s+1
            c=c+1
            if s==1:
                return c
            return cv(s,c)
        for i in a:
            c=0
            b=cv(i,c)
            z.append([b,i])
        z.sort(key=lambda x:x[0])
        a=[]
        for i in z:
            a.append(i[1])
        return a[k-1]  
        
           
            
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:  
        dict = defaultdict()
        def weight(x):
           if(x==1):
               return 1
           if(x%2==0):
               return 1+weight(x//2);
           else:
               return 1+ weight(3*x+1)
        
        for i in range(lo, hi+1):
            dict[i] = weight(i)
           
        dict = sorted(list(dict.items()),key=lambda x:x[1])
        return dict[k-1][0]
    
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def collatz(num, moves = 0):
            if num == 1:
                return moves
            if num % 2 == 0:
                return collatz(num / 2, moves + 1)
            else:
                return collatz(num * 3 + 1, moves + 1)
        
        arr = [(i, collatz(i)) for i in range(lo, hi + 1)]
        arr.sort(key=lambda x:x[1])
        
        print(arr)
        
        return arr[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        a=[i for i in range(lo,hi+1)]
        z=[]
        def cv(s,c):
            if s%2==0:
                s=s/2
            else:
                s=3*s+1
            c=c+1
            if s==1:
                return c
            return cv(s,c)
        for i in a:
            c=0
            a=cv(i,c)
            z.append([a,i])
        z.sort(key=lambda x:x[0])
        a=[]
        for i in z:
            a.append(i[1])
        return a[k-1]  
        
           
            
        


class Solution:
    def getKth(self, lo, hi, k):
        #
        memo = { 1:0 }
        def power(x):
            if x in memo:
                return memo[x]
            n = memo[x] = 1 + power( 3*x+1 if x&1 else x>>1 )
            return n
        #
        A = [ (power(x),x) for x in range(lo,hi+1) ]
        return sorted(A)[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        a=[i for i in range(lo,hi+1)]
        z=[]
        def cv(s,c):
            if s%2==0:
                s=s/2
            else:
                s=3*s+1
            c=c+1
            if s==1:
                return c
            return cv(s,c)
        for i in a:
            c=0
            a=cv(i,c)
            z.append([a,i])
        z.sort(key=lambda x:x[1])
        z.sort(key=lambda x:x[0])
        a=[]
        for i in z:
            a.append(i[1])
        return a[k-1]  
        
           
            
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        #if lo == hi:
         #   return lo
        
        ans = []
        for i in range(lo, hi+1):
            num = i
            ctr = 0
            while num != 1:
                if num % 2 != 0: #odd
                    num = (num * 3) + 1
                else:
                    num = num/2
                ctr+=1
            ans.append((ctr, i))
            
        return sorted(ans, key = lambda x: x[0])[k-1][1]
            
                


class Solution:
    def getKth(self, lo: int, hi: int, z: int) -> int:
        d={}
        def dfs(k):
            if k==1:
                return
            elif k%2==0:
                c[0]+=1
                dfs(k//2)
            else:
                c[0]+=1
                dfs(3*k+1)
        for i in range(lo,hi+1):
            c=[0]
            dfs(i)
            d[i]=c[0]
        
        d=sorted(list(d.items()),key=lambda g:g[1])
        
        return d[z-1][0]
            


class Solution:
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def step(n,i) -> int:
            s=0
            while n!=1:
                if n%2==0: 
                    n=n/2
                else:
                    n=n*3+1
                s+=1
            return s

        a = 0
        l = []
        for i in range(lo,hi+1):
            a = step(i,0)
            l.append((i,a))
            
        l = sorted(l,key=lambda x:x[1])    
        return l[k-1][0]

class PowerValue(tuple):
    def __lt__(x, y):
        
        return x[1] < y[1] if x[1] != y[1] else x[0] < y[0]
    

        
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        all_val = [i for i in range(lo, hi+1)]
        pow_values = []
        
        def power(val):
            if val == 1:
                return 0

            if val % 2 == 0:
                val = val // 2
            else:
                val = (3 * val + 1)
        
            return 1 + power(val)
        
        for num in all_val:
            get_pow = power(num)
            pow_values.append((get_pow, num))
        pow_values.sort()
        
        return pow_values[k-1][1]
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def distance(n):
            if n == 1:
                return 0
            
            new_n = n // 2 if n % 2 == 0 else n * 3 + 1
            return 1 + distance(new_n)
            
        nums = list(range(lo, hi + 1))
        nums.sort(key=lambda x: (distance(x), x))
        return nums[k - 1]

from functools import cmp_to_key

class Solution:
    def getPower(self, number):
        if number == 1:
            return 0
        if number % 2 == 0:
            return 1 + self.getPower(number / 2)
        else:
            return 1 + self.getPower(number * 3 + 1)
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        a = []
        for i in range(lo, hi + 1):
            a.append((i, self.getPower(i)))
        a = sorted(a, key=cmp_to_key(
            lambda x, y: x[1] - y[1] if x[1] != y[1] else x[0] - y[0]))
        print(a)
        return a[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def get_power_of_element(x):
            if x == 1:
                return 0
            elif x % 2 == 0:
                x = x/2
                return 1+get_power_of_element(x)
            elif x % 2 != 0:
                x = 3*x + 1
                return 1+get_power_of_element(x)
        
        array_of_numbers = [x for x in range(lo, hi+1)]
        array_of_values = []
        for i in array_of_numbers:
            k_value = get_power_of_element(i)
            array_of_values.append((k_value, i))

        array_of_values.sort(key=lambda x: x[0])
        
        return array_of_values[k-1][1]
        


class Solution:
    def getKth(self, lo, hi, k):
        #
        memo = { 1:0 }
        def power(x):
            if x in memo:
                return memo[x]
            n = memo[x] = 1 + power( 3*x+1 if x&1 else x >> 1 )
            return n
        #
        A = [ (power(x),x) for x in range(lo,hi+1) ]
        return sorted(A)[k-1][1]

from collections import defaultdict
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d = defaultdict(list)
        for integer in range(lo, hi + 1):
            res = integer
            cnt = 0
            while res != 1:
                if res % 2 == 0:
                    res /= 2
                elif res %2 == 1:
                    res = res * 3 + 1
                cnt += 1
            d[cnt].append(integer)
        keys = sorted(d.keys())
        ans = []
        for key in keys:
            ans += sorted(d[key])
        return ans[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        track = dict()
        for i in range (lo, hi+1):
            power = 0
            x = i
            while (i != 1):
                if (i % 2 == 0):
                    i = i // 2
                else:
                    i = 3 * i + 1
                power += 1
            track[x] = power
        
        sorted_tr = sorted(track.items(), key=lambda x: [x[1], x[0]])
        print(sorted_tr)
        return sorted_tr[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        ans = []
        for nn in range(lo,hi+1):
            ans.append([nn,self.powerVal(nn)])
        ans = sorted(ans,key=lambda x:x[1])
        return ans[k-1][0]
        
    def powerVal(self, num):
        count = 0 
        while num>1:
            if num%2==0:
                num = num/2
            else:
                num = 3*num+1
            count +=1
        return count

class Solution:
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def step(n,i) -> int:
            i = i + 1
            if n == 1:
                return i - 1

            if n % 2:
                i = step(3*n+1,i)
            else:
                i = step(n//2,i)
            return i

        a = 0
        l = []
        for i in range(lo,hi+1):
            a = step(i,0)
            l.append((i,a))
            
        l = sorted(l,key=lambda x:x[1])    
        return l[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        #return sorted(map(lambda x: (self.myfunc(x),x), range(lo,hi+1)) )[k-1][1]
        return sorted([(self.recursive(x,0,{}),x) for x in range(lo,hi+1)] )[k-1][1]


    
    def recursive(self, x, count,memo):
        if x in memo:
            return memo[x]
        elif x==1:
            memo[x]=count
            return count
        elif x%2==0:
            return self.recursive(x/2, count+1, memo)
        else:
            return self.recursive(3*x+1, count+1, memo)
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        a=[i for i in range(lo,hi+1)]
        z=[]
        def cv(s,c):
            if s==1:
                c=c+1
                return c
            if s%2==0:
                s=s/2
            else:
                s=3*s+1
            c=c+1
            if s==1:
                return c
            return cv(s,c)
        for i in a:
            c=0
            b=cv(i,c)
            z.append([b,i])
        z.sort(key=lambda x:x[0])
        a=[]
        for i in z:
            a.append(i[1])
        return a[k-1]  
        
           
            
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d=dict()
        for i in range(lo,hi+1):
            a=i
            c=0
            while(a>1):
                if(a%2==0):
                    a=a/2
                    c+=1
                else:
                    a=3*a+1
                    c+=1
            d[i]=c
        res=sorted(list(d.items()), key=lambda x:x[::-1])
        return(res[k-1][0])


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        for num in range(lo, hi + 1):
            var = num
            count = 0
            while num != 1:
                if num % 2 == 0:
                    num = num / 2
                else:
                    num = 3 * num + 1
                count += 1
            res.append([count, var])
        res.sort()
        return res[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # make list from lo to hi
        input = list(range(lo, hi+1))
        
        output = []
        
        def getPower(val, currPower):
            if val == 1:
                output.append(currPower)
                return None
            elif val % 2 == 0:
                # if even divide by 2, add to power, and recurse
                val /= 2
                currPower += 1
                getPower(val, currPower)
            else:
                val = (3 * val) + 1
                currPower += 1
                getPower(val, currPower)
        
        # match output with input in sorted order
        outputDict = dict.fromkeys(input, 0)
        
        # get the power of each input number
        for num in input:
            getPower(num, 0)

        for keys, vals in enumerate(outputDict.keys()):
            outputDict[vals] = output[keys]
        
        outputDict = sorted((value, key) for (key, value) in outputDict.items())
        
        # return the kth value from input
        return outputDict[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        cache = {1:0}
        
        
        def power(n):
            
            if n in cache:
                return cache[n]
            
            if n & 1:
                cache[n] = 1 + power(3*n+1)
                return cache[n]
        
            else:
                cache[n] = 1 + power(n//2)
                return cache[n]
            
            
        out = []
        for i in range(lo, hi+1):
            out.append([i, power(i)])
            
        out.sort(key= lambda x:x[1])
        
        return out[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def BFS(queue):
            while queue:
                var , level = queue.popleft()
                if var == 1:return level
                if var % 2:queue.append([3*var+1,level+1])
                else:queue.append([var/2,level+1])
        ans = []
        for i in range(lo,hi+1):
            ans.append((i,BFS(deque([[i,0]]))))
        ans = sorted(ans,key = lambda l:l[1])
        return ans[k-1][0]

def power_value(num: int, counter = 0):
    if num % 2 ==0:
        num = num /2
    else:
        num = 3*num + 1
    
    counter +=1
    if num == 1:
        return counter
    else:
        return power_value(num, counter=counter)


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        to_sort = []
        for i in range(lo, hi + 1):
            to_sort.append([i, power_value(i)])
            
        
        to_sort = sorted(to_sort, key=lambda x: x[1])
        
        return to_sort[k-1][0]
            


class Solution:
    def powerValue(self, n):
        count = 0
        while n != 1:
            if n%2==0:
                n = n/2
            else:
                n = (3*n)+1
            
            count+=1
        return count
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        minHeap = []
        
        for i in range(lo,hi+1):
            heapq.heappush(minHeap,(self.powerValue(i),i))
        
        i = 1
        
        while i < k:
            heapq.heappop(minHeap)
            i+=1
        return minHeap[0][1]

class Solution:
    def getKth(self, lo: int, hi: int, m: int) -> int:
        a=[i for i in range(lo,hi+1)]
        z=[]
        def cv(s,c,k):
            if s in k:
                k[s]=k[s]+1
            elif s%2==0:
                s=s/2
                c=c+1
            else:
                s=3*s+1
                c=c+1
            if s==1:
                return list(k.values()),c
            return cv(s,c,k)
        for i in a:
            c=0
            k={}
            b,f=cv(i,c,k)
            z.append([sum(b)+f,i])
        z.sort(key=lambda x:x[0])
        a=[]
        for i in z:
            a.append(i[1])
        return a[m-1]  
        
           
            
        


class Solution:
    def getKth(self, lo: int, hi: int, m: int) -> int:
        a=[i for i in range(lo,hi+1)]
        z=[]
        def cv(s,c,k):
            if s in k:
                k[s]=k[s]+1
            elif s%2==0:
                s=s/2
                c=c+1
            else:
                s=3*s+1
                c=c+1
            if s==1:
                return sum(k.values()),c
            return cv(s,c,k)
        for i in a:
            c=0
            k={}
            b=cv(i,c,k)
            z.append([b,i])
        z.sort(key=lambda x:x[0])
        a=[]
        for i in z:
            a.append(i[1])
        return a[m-1]  
        
           
            
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        def get_power_of_element(x):
            if x == 1:
                return 0
            elif x % 2 == 0:
                x = x/2
                return 1+get_power_of_element(x)
            elif x % 2 != 0:
                x = 3*x + 1
                return 1+get_power_of_element(x)
        
        array_of_numbers = [x for x in range(lo, hi+1)]
        hash_map = {}
        for i in array_of_numbers:
            k_value = get_power_of_element(i)
            hash_map[i] = k_value

        array_of_values = [(y, x) for x, y in list(hash_map.items())]
        array_of_values.sort(key=lambda x: x[0])
        
        return array_of_values[k-1][1]
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
     
        p={}
        for i in range(lo, hi+1):
            temp=0
            copy_i=i
            if copy_i==1:
                p[i]=0
            while (copy_i!=1):
                if copy_i %2==0:
                    copy_i /=2
                    temp+=1
                    if copy_i==1:
                        p[i]=temp
                        break
                if copy_i %2 !=0:
                    copy_i= 3*copy_i + 1
                    temp+=1
                    if copy_i==1:
                        p[i]=temp
                        break
        print('p is')
        print(p)
        p=sorted(list(p.items()), key=lambda x:x[1])
        track=0
        for ele in p:
            track+=1
            if track==k:
                return ele[0]


class Solution:

    def getKth(self, lo: int, hi: int, k: int) -> int:
        dic = {}
        for i in range(lo, hi+1):
            z = self.getTheP(i)
            dic[i] = self.getTheP(i)
        return sorted(list(dic.items()), key=lambda x:(x[1],x[0]))[k-1][0]
            
    def getTheP(self, q: int) -> int:
        Pow = 0
        while (q!= 1):
            if(q%2 == 0):
                q = (q/2)
                Pow+=1
            else:
                q=(3*q+1)
                Pow+=1
        return Pow        
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        
        ans=[]
        for x in range(lo,hi+1):
            count=0
            num=x
            while x>1:

                if x%2==0:
                    x=x/2
                else:
                    x=3*x+1
                count+=1
            heapq.heappush(ans,[count,num])
        
     
        return (heapq.nsmallest(k,ans)[-1][-1])
    


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def getPower(n):
            return 0 if n == 1 else (getPower(3 * n + 1) if n % 2 else getPower(n / 2)) + 1
        return sorted(range(lo, hi + 1), key=getPower)[k - 1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        i = 0
        pow2Dict = {1:0}
        pow2Now = 1
        while i < 32:
            i += 1
            pow2Now *= 2
            pow2Dict[pow2Now] = i
        
        visited = {}
        
        stack = [(0, i, i) for i in range(lo, hi+1)]
        
        while stack:
            stepNow, numNow, numOrigin = heapq.heappop(stack)
            if numNow in pow2Dict:
                visited[numOrigin] = stepNow + pow2Dict[numNow]
            else:
                if numNow in visited:
                    visited[numOrigin] = stepNow + visited[numNow]
                else:
                    if numNow%2:
                        heapq.heappush(stack, (stepNow + 1, numNow*3+1, numOrigin))
                    else:
                        heapq.heappush(stack, (stepNow + 1, numNow//2, numOrigin))
        sortedNums = sorted([i for i in range(lo, hi+1)], key = lambda x: (visited[x], x))
        return sortedNums[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dic = {}
        for i in range(lo,hi+1):
            power = self.findPower(i,{})
            dic[i] = power
        #print(dic)
        sortedValue = sorted(list(dic.items()), key=lambda x:x[1])
        return (sortedValue[k-1][0])
    
    def findPower(self,num,memo):
        if num in memo:
            return memo[num]
        if num == 1:
            return 1
        memo[num]=self.findPower(num//2,memo)+1 if num % 2 == 0 else self.findPower(3*num+1, memo)+1
        return memo[num]


class Solution:
    def core(self, num: int, counter: int) -> int:
        if num == 1:
            return counter
        if num % 2 == 0:
            return self.core(num//2, counter + 1)
        return self.core(num * 3 + 1, counter + 1)

    def getPowerValue(self, num: int) -> int:
        return self.core(num, 0)        
        
    def generatePowerValues(self, lo: int, hi: int) -> List[int]:
        output = [0]
        if hi == 1:
            return output
        for i in range(2, hi + 1):
            if i % 2 == 0:
                output.append(1 + output[i//2 - 1])
            else:
                output.append(3 + output[(3*i+1)//4 - 1])
        return output[lo-1:hi]
            
        
    def getKth(self, lo: int, hi: int, k: int) -> int:
        output = []
        for i in range(lo, hi + 1):
            output.append((i, self.getPowerValue(i)))
        output.sort(key=lambda x: (x[1], x[0]))
        return output[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_dic = {}
        power_dic_sub = {}
        for i in range(lo, hi+1):
            power_dic_sub[i] = self.getPower(i, 0, [], power_dic)
        result_tmp = sorted(power_dic_sub.items(), key=lambda kv: kv[1], reverse= False)
        return result_tmp[k - 1][0]

    def getPower(self, num, power,power_record, power_dic):
        if num == 1:
            for i in power_record:
                if not power_dic[i]:
                    power_dic[i] = power - power_record.index(i)
            return power
        if num in power_dic:
            return power_dic[num]
        if num % 2 == 0:
            num = num / 2
        else:
            num = 3 * num +1
        power += 1
        return self.getPower(num, power, power_record, power_dic)

class Solution:
    def getKth(self, a: int, b: int, k: int) -> int:
        def fun(x,d):
            if x==1:
                return 0
            if(x%2==0):
                if x//2 in d:
                    d[x]=d[x//2]+1
                else:
                    d[x]=fun(x//2,d)+1
            else:
                if 3*x+1 in d:
                    d[x]=d[3*x+1]+1
                else:
                    d[x]=fun(3*x+1,d)+1
            return d[x]
        d={}
        for i in range(a,b+1):
            fun(i,d)
        d[1]=0
        ans=[]
        for i in range(a,b+1):
            ans.append((d[i],i))
        ans.sort()
        return ans[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d={}
        def dp(x):
            if x==1:
                return 0
            if x%2:
                t= 3*x+1
                if t not in d:
                    d[t]=dp(t)
                return 1+d[t]
            else:
                t= x//2
                if t not in d:
                    d[t]=dp(t)
                return 1+d[t]
        d1={}
        for i in range(lo,hi+1):
            d1[i]=dp(i)
        return sorted(d1,key= lambda x:d1[x])[k-1]
        
            
                


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


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        memo = {}
        
        def help(x):
            if x in memo:
                return memo[x]
            
            if x == 1:
                return 0
            
            if x%2 == 0:
                memo[x] = 1+help(x//2)
            else:
                memo[x] = 1+help(x*3+1)
            
            return memo[x]
            
        return sorted( list(range(lo, hi+1)), key=lambda x: [help(x), x]  )[k-1]
        
        
#         def help(x):
#             step = 0
#             while x != 1:
#                 step += 1
#                 if x%2 == 0:
#                     x=x//2
#                 else:
#                     x = 3*x+1
#             return step
        
#         return sorted( list(range(lo, hi+1)), key=lambda x: [help(x), x]  )[k-1]


class Solution:
    # def __init__(self):
        # self.memo = {1: 0}
        
    def getPowVal(self, x: int) -> int:
        if x in self.memo:
            return self.memo[x]
        
        newX = x//2 if x%2==0 else 3*x+1
        
        self.memo[x] = 1 + self.getPowVal(newX)
        
        return self.memo[x]
#         intermed = []
#         steps = 0
#         while x != 1 or x not in self.memo:
#             intermed.append(x)
#             steps += 1
#             x = x//2 if x%2==0 else 3*x+1
        
#         if x in self.memo:
#             steps += self.memo[x]
        
#         for idx in range(len(intermed)):
#             self.memo[intermed[idx]] = steps-idx

        # return self.memo[intermed[0]]
    def getKth(self, lo: int, hi: int, k: int) -> int:
        self.memo = {1: 0}
        powVal = [ (x, self.getPowVal(x)) for x in range(lo, hi+1) ]
        
        powVal.sort(key=lambda x: x[1])
        

        return powVal[k-1][0]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = dict()
        dp[0] = dp[2] = 1
        dp[1] = 0
        
        def calc(x):
            if dp.get(x) is not None:
                return dp.get(x)
            if x%2 == 0:
                dp[x] = calc(x//2)+1
            else:
                dp[x] = calc(x*3+1)+1
            return dp[x]
                
        to_sort = []
        for i in range(lo,hi+1):
            calc(i)
            to_sort.append([i, dp.get(i)])
        sorted_res = sorted(to_sort, key=lambda x: x[1])
        return sorted_res[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1:0}
        def getPower(x):
            if x in memo:
                return memo[x]
            elif x%2==0:
                memo[x] = 1+getPower(x/2)
            else:
                memo[x] = 1+getPower(3*x+1)
            return memo[x]
        return sorted([(getPower(x),x) for x in range(lo,hi+1)] )[k-1][1]
    
    


        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        self.inc = {1: 0 }
        while lo <= hi:
            heapq.heappush(res, (self.find_power(lo), lo))
            lo += 1
        for i in range(k):
            ans = heapq.heappop(res)[1]
        return ans
        
    def find_power(self, var):
        if var in self.inc: return self.inc[var]
        if var % 2 == 0: 
            self.inc[var] = self.find_power(var//2) + 1
        else: 
            self.inc[var] = self.find_power(3*var + 1) + 1
        return self.inc[var]
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo={1:0}
        def getPower(x):
            if x in memo:
                return memo[x]
            if x%2==0:
                memo.update({x:getPower(x//2)+1})
                return memo[x]
            else:
                memo.update({x:getPower(x*3+1)+1})
                return memo[x]
        return sorted(map(lambda x: (getPower(x),x), range(lo,hi+1)))[k-1][1]

class Solution:
    def getPower(self, n):
        if n == 1:
            return 0
        
        if n in self.dp:
            return self.dp[n]
        else:
            if n %2 == 0:
                self.dp[n] = self.getPower(n//2) + 1
            else:
                self.dp[n] = self.getPower(3*n + 1) + 1
        return self.dp[n]
        
        
        
    def getKth(self, lo: int, hi: int, k: int) -> int:
        tmp = []
        self.dp = {}
        for num in range(lo, hi+1):
            tmp.append((num, self.getPower(num)))
        tmp.sort(key = lambda x: (x[1], x[0]))
        return tmp[k-1][0]

import functools

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted((get_power_value(x), x) for x in range(lo, hi + 1))[k - 1][1]

@functools.lru_cache(maxsize=None)
def get_power_value(x):
    if x == 1:
        return 0
    return 1 + get_power_value(x / 2 if x % 2 == 0 else x * 3 + 1)

from collections import defaultdict

class Solution:
    def helper(self, x):
            if x == 2:
                return 1
            if x in self.table:
                return self.table[x]
            if x % 2:
                y = int(3*x+1)
            else:
                y = int(x/2)
            ans = 1+self.helper(y)
            self.table[x] = ans
            return ans
    def getKth(self, lo: int, hi: int, k: int) -> int:
        self.table = dict()
        self.lo = lo
        self.hi = hi
        powers = [self.helper(x) for x in range(lo, hi+1)]
        tosort = list(zip(powers, list(range(lo, hi+1))))
        return sorted(tosort)[k-1][1]
        # print(ranks)


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = dict()
        dp[0] = dp[2] = 1
        dp[1] = 0
        
        def calc(x, adj):
            if x%2 == 0:
                n = x//2
            else:
                n = 3*x+1
            if dp.get(n) is None:
                adj.append(n)
                calc(n, adj)
            else:
                count = dp.get(n)
                for a in adj[::-1]:
                    count += 1
                    dp[a] = count
                
        to_sort = []
        for i in range(lo,hi+1):
            calc(i, [i])
            to_sort.append([i, dp.get(i)])
        sorted_res = sorted(to_sort, key=lambda x: x[1])
        return sorted_res[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        ans = []
        self.dic = {1:0}
        for i in range(lo, hi+1):
            c = self.solvePower(i)
            ans.append([c, i])
            
        ans.sort()
        # print(ans)
        return ans[k-1][1]
    
    
    def solvePower(self, num):
        if self.dic.get(num, None) != None:
            return self.dic[num]
        
        if num%2 == 0:
            temp = self.solvePower(num//2)
        else:
            temp = self.solvePower(num*3 + 1)
        
        self.dic[num] = 1 + temp
        return self.dic[num]
            
        
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power = {}
        power[1] = 0
        current = {}
        nums = list(range(lo, hi+1))
        for i in nums:
            self.get_power_value(power, current, i)
        value = sorted(list(current.items()), key= lambda x:x[1])
        arr = list([x[0] for x in value])
        return arr[k-1]
    
    def get_power_value(self, power, current, num):
        arr = []
        start = num
        if num in power:
            current[num] = power[num]
        else:
            arr = []
            value = num
            found_power = 0
            while value != 1:
                if value % 2 == 0:
                    value /= 2
                else:
                    value = value * 3 + 1
                arr.append(value)
                if value in power:
                    found_power = power[value]
                    break
            for i in range(0, len(arr)):
                power[start] = len(arr) - i + found_power
                start = arr[i]
            current[num] = power[num]
            
    
            
                


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache(None)
        def power(x):
            if x == 1:
                return 0
            return 1 + power(x * 3 + 1) if (x & 1) else 1 + power(x >> 1)
        a = [(power(x), x) for x in range(lo, hi + 1)]
        a.sort()
        print(a)
        return a[k - 1][1]


class Solution:
    def __init__(self):
        self.d = {}

    def solve(self,x):
        if x == 1:
            return 0
        if self.d.get(x,0)!=0:
            return self.d[x]
        if x%2==0:
            self.d[x] = 1+self.solve(x//2)
            return self.d[x]
        else:
            self.d[x] = 1+ self.solve(x*3+1)
            return self.d[x]

    def getKth(self, lo, hi, k):
        ar = []
        for i in range(hi,lo-1,-1):
            ar.append((self.solve(i),i))
        ar.sort()
        return ar[k-1][1]

import heapq
from operator import itemgetter

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1: 0, 2: 1}
        num_to_power = []
        
        for num in range(lo, hi + 1):

            if num == 1:
                num_to_power.append((num, 0))
                continue
                
            i = num
            steps = 0   
            while i != 1:
                if i in memo:
                    num_to_power.append((num, steps + memo[i]))
                    memo[num] = steps + memo[i]
                    i = 1
                elif  i % 2 == 0:
                    i = i // 2
                    steps += 1
                else:
                    i = 3 * i + 1
                    steps += 1

        num_to_power = sorted(num_to_power, key=itemgetter(1,0))
        return num_to_power[k - 1][0]

from collections import defaultdict
# import heapq
from operator import itemgetter 
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power_dict = defaultdict(int)
        
        def cal_power(n):
            nonlocal power_dict
            
            if n in list(power_dict.keys()):
                return power_dict[n]-1
            if n==1:
                return 0
            if n%2==0:
                n = n/2
            elif n%2==1:
                n = 3*n+1
                
            power_dict[n] = cal_power(n)+1
            return power_dict[n]
        lst = []
        for i in range(lo,hi+1):
            lst.append((cal_power(i),i))
        
        lst = sorted(lst,key = itemgetter(0))
        return lst[k-1][1]

        # print(lst)
#         heapq.heapify(lst)
        
#         for i in range(k):
#             ans = heapq.heappop(lst)
        
#         return ans[1]  
    
    
#         @lru_cache(None)
#         def power(x):
#             if x == 1:
#                 return 0
#             if x % 2 == 0:
#                 return 1 + power(x // 2)
#             return 1 + power(3 * x + 1)

#         return sorted(range(lo, hi+1), key=power)[k-1]
    
                
                


from collections import defaultdict
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        m = defaultdict(int)
        
        def do(n):
            if(n==1):
                return 0
            if m[n]!=0:
                return m[n]
            else:
                if n%2==0:
                    m[n]=1+do(n/2)
                else:
                    m[n]=1+do(3*n+1)
            return m[n]
        
        res=[]
        for i in range(lo, hi+1):
            res.append([do(i), i])
        
        res.sort()
        return res[k-1][1]


class Solution:
    cache = {}
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        l = list(range(lo, hi + 1))
        l.sort(key = lambda x: self.findKth(x))
        return l[k - 1]
        
    # 牛啤的recursion + cache优化
    def findKth(self, n: int) -> int:
        if n in self.cache:
            return self.cache[n]
        
        if n == 1:
            return 0
        
        if n % 2 == 0:
            res = 1 + self.findKth(int(n / 2))
        else:
            res = 1 + self.findKth(3 * n + 1)
            
        self.cache[n] = res
        return res


class Solution_eva:

    def getKth(self, lo: int, hi: int, k: int) -> int:
        def calSteps(x):
            cnt = 0
            # O(n)
            while x != 1:
                x = x / 2 if x % 2 == 0 else 3*x + 1
                cnt += 1
            return cnt
        # O(nlogn) * O(n)
        return sorted([ele for ele in range(lo, hi+1)], key=lambda x: calSteps(x))[k-1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        self.visited = {}
        
        def recur(n):
            if n in self.visited:
                return self.visited[n]
            if n == 1:
                return 0
            else:
                if n%2 == 0:
                    moves = 1 + recur(int(n/2))
                else:
                    moves = 1 + recur(int(3*n)+1)
                self.visited[n]=moves
                return self.visited[n]
        for i in range(hi,lo-1,-1):
            if i not in self.visited:
                self.visited[i]=recur(i)
            
        result =  [ (x,self.visited[x]) for x in self.visited if lo <=x and x<=hi]
        result.sort(key = lambda x : (x[1],x[0]))
        return result[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # 7  -> 16  7, 22, 11, 34, 17, 52, 26, 133, 40, 20, 10, 5, 16, 8, 4, 2, 1 
        # 8  -> 3   8, 4, 2, 1 
        # 9  -> 19  9, 28, 14, 7, 22, 11, 34, 17,  
        # 10 -> 6   10, 5, 16, 8, 4, 2, 1
        # 11 -> 14  11, 34
        power_list = []
        d = {}
        for i in range(lo, hi+1):
            a = self.power(i, d)
            power_list.append(a)
        print(power_list)
        list2 = [i for i in range(lo, hi+1)]
        # [x for _, x in sorted(zip(Y,X), key=lambda pair: pair[0])]
        list2 = [ x for x, y in sorted(zip(list2, power_list), key = lambda x: x[1])]
        return list2[k-1]
        
    def power(self, x, dict1):
        if x in dict1:
            print(('hi', x))
            return dict1[x]
        else:
            orig = x
            list1 = []
            count = 0
            while x != 1 and x not in dict1:
                if x %2 == 0:
                    x /= 2
                else:
                    x = 3*x + 1
                x = int(x)
                count += 1
                list1.append(x)
            n = len(list1)
            if x == 1:
                dict1[orig] = n
                for elem in list1:
                    dict1[elem] = n-1
                    n -= 1
                
            else:
                print(('hi ', x))
                dict1[orig] = n+ dict1[x]
                for elem in list1:
                    dict1[elem] = n-1 + dict1[x]
                    n -= 1
            return dict1[orig]
            
                    


class Heap:
    def __init__(self, initial=None, key=lambda x: x):
        self.key = key
        if initial:
            self._data = [(key(item), item) for item in initial]
            heapq.heapify(self._data)
        else:
            self._data = []
            
    def push(self, item):
        heapq.heappush(self._data, (self.key(item), item))
        
    def pop(self):
        return heapq.heappop(self._data)[1]
    
    def peek(self):
        return self._data[0][1]
            

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powers = {}
        heap = Heap(key=lambda n: -self._get_power(n, powers))
        for n in range(lo, lo + k):
            heap.push(n)
        for n in range(lo + k, hi + 1):
            heap.push(n)
            heap.pop()
        
        return heap.peek()

        
    def _get_power(self, n: int, powers: dict) -> int:
        orig_n = n
        if n not in powers:
            power = 0
            while n != 1:
                if n % 2:   # n is odd
                    n = n * 3 + 1
                else:       # n is even
                    n //= 2
                power += 1
                if n in powers:
                    power += powers[n]
                    break
            powers[orig_n] = power
        return powers[orig_n] - 1/orig_n

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = {}
        dp[1] = 0
        def helper(num):
            if num in dp:
                return dp[num]
            if num == 1:
                return 0
            if num%2 == 0:
                dp[num] = helper(num//2) + 1
            else:
                dp[num] = helper((num*3)+1) + 1
            print((dp[num]))
            return dp[num]
        res = []
        for i in range(lo, hi+1):
            res.append((helper(i), i))
        res.sort()
        return res[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        steps = defaultdict(lambda: None)
        steps[1] = 0
        vals = list(range(lo, hi+1))
        powers = []
        for v in vals:
            s = v
            num_steps = 0
            while s != 1:
                if steps[s] is not None:
                    num_steps += steps[s]
                    break
                if s % 2 == 0:
                    s //= 2
                else:
                    s = 3*s + 1
                    
                num_steps += 1
                
            steps[v] = num_steps
            
            powers.append(num_steps)
            
        items = sorted(zip(powers, vals))
        return items[k-1][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {}
        res = []
        for n in range(lo,hi+1):
            power = 0
            x = n
            while x >= 1:
                if x == 1:
                    memo[n] = power
                    break
                elif x in memo:
                    power += memo[x]
                    memo[n] = power
                    break
                elif x%2==0:
                    x//=2
                    power+=1
                elif x%2!=0:
                    x = 3*x+1
                    power+=1

        res = sorted(memo.items(),key = 
                     lambda kv:(kv[1], kv[0]))
        return res[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache(maxsize=None)
        def get_power(n):
            if n == 1:
                return 0
            elif n % 2:
                return 1 + get_power(3 * n + 1)
            return 1 + get_power(n // 2)
        
        nums = []
        
        for i in range(lo, hi + 1):
            nums.append([get_power(i), i])
        
        nums.sort()
        
        return nums[k - 1][1]

class Solution:

    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        lst={1:0}
        num_list=[]
        for i in range(lo,hi+1):
            ans=0
            while i!=1:
                if i in list(lst.keys()):
                    ans=lst[i]+ans
                    break
                else:
                    num_list=num_list+[i]
                    if i%2:
                        i=i*3+1
                        ans+=1
                    else:
                        i/=2
                        ans+=1
            for ind,num in enumerate(num_list):
                lst[num]=ans-ind
            num_list=[]
        power_list=[(i,lst[i]) for i in range(lo,hi+1)]
        power_list.sort(key=lambda x:x[1])

        return power_list[k-1][0]
    


from heapq import heapify, heappop

cache = {
    1: 0
}


def collatz(y):
    if y in cache:
        return cache[y]
    
    x = y
    steps = 1
    while x > 1:
        if x % 2 == 1:
            x = 3 * x + 1
        else:
            x //= 2
            
        if x in cache:
            ans = cache[x] + steps
            break

        steps += 1
    else:
        ans = steps

    cache[y] = ans
    return ans


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        powers = [(collatz(x), x) for x in range(lo, hi + 1)]
        heapify(powers)
        
        for _ in range(k):
            x = heappop(powers)

        return x[1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {}
        
        def power(n):
            if n == 1:
                return 0
            
            if n in memo:
                return memo[n]
            
            if n % 2 == 0:
                res = 1 + power(n / 2)
            else:
                res = 1 + power(3 * n + 1)
            
            memo[n] = res
            
            return res
        
        s = sorted(range(lo, hi + 1), key=power)
        return s[k - 1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        d = collections.defaultdict(int)
        d[1] = 0
        d[2] = 1
        
        def dfs(num): 
            if num in d:
                return d[num]
            
            count = 0 
            if num % 2:
                d[num] = 1 + dfs(num*3 + 1)
                return  1 + dfs(num*3 + 1)

            if not num % 2:
                d[num] = 1 + dfs(num // 2)
                return 1 + dfs(num // 2)
        
        res = collections.defaultdict(int)
        for n in range(lo, hi+1):
            res[n] = dfs(n)
            
        res = sorted(list(res.items()), key = lambda x: x[1])
        
        return res[k-1][0]



class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        power = {}
        for x in range(lo, hi+1):
            power[x] = self._get_power(x, power)
        return sorted(power, key=power.get)[k-1]
        
    def _get_power(self, x, power):
        if x in power: return power[x]
        if x == 1: return 0
        if x % 2 == 0: return self._get_power(x // 2, power) + 1
        else: return self._get_power(3 * x + 1, power) + 1


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        a={}
        def check(n,a):
            ct=0
            while n!=1:
                if n%2==0:
                    n=n/2
                else:
                    n=3*n+1
                if n in a:
                    ct += a[n]+1
                    return ct
                    break
                ct +=1
            return ct
        for i in range(lo,hi+1):
            a[i] = check(i,a)
        b=sorted(a.items(), key=lambda kv:(kv[1],kv[0]))
        return b[k-1][0]

import heapq
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # solution one just calculate all the power number 
        pv_map = {}
        def pv(val): 
            v = val
            cnt = 1
            while val!= 1:
                if val in pv_map: 
                    pv_map[v] = cnt + pv_map[val] -1
                    return pv_map[v]
                if val % 2 == 0: 
                    val /= 2
                else: 
                    val = 3 * val + 1
                cnt += 1
            pv_map[v] = cnt
            return cnt
        # vs = sorted(range(lo, hi+1), key = lambda x: pv(x))[k-1]
        h = []
        for v in range(lo, hi+1): 
            p = pv(v)
            if len(h) < k: 
                heapq.heappush(h, (-p, -v))
            else: 
                if p < (-h[0][0]):
                    heapq.heapreplace(h, (-p, -v))

        return -h[0][1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:

        @lru_cache(None)
        def p(x):
            if x == 1:
                return 0
            elif x & 1:
                return p(3 * x + 1) + 1
            else:
                return p(x >> 1) + 1

        return sorted(range(lo, hi + 1), key=p)[k - 1]

from functools import lru_cache
from heapq import heappop, heappush

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        @lru_cache(None)
        def get_steps(num):
            if num == 1:
                return 0
            elif num % 2:
                return 1 + get_steps(3 * num + 1)
            else:
                return 1 + get_steps(num // 2)
            
        pq = []
        for i in range(lo, hi + 1):
            heappush(pq, (-get_steps(i), -i))
            if len(pq) > k:
                heappop(pq)
        
        return -min(pq)[1]

from collections import defaultdict

class Solution:
    def helper(self, x):
            if x == 2:
                return 1
            if x in self.table:
                return self.table[x]
            if x % 2:
                y = int(3*x+1)
            else:
                y = int(x/2)
            ans = 1+self.helper(y)
            if self.lo <= x <= self.hi:
                self.table[x] = ans
            return ans
    def getKth(self, lo: int, hi: int, k: int) -> int:
        self.table = dict()
        self.lo = lo
        self.hi = hi
        powers = [self.helper(x) for x in range(lo, hi+1)]
        tosort = list(zip(powers, list(range(lo, hi+1))))
        return sorted(tosort)[k-1][1]
        # print(ranks)
    
        # doesnt work
        # todo = set(range(lo, hi+1))
        # if len(todo) == 1:
        #     return 1
        # ranks = []
        # while todo:
        #     y = todo.pop()
        #     stack = [y]
        #     while y > 1 and y not in table:
        #         if y % 2:
        #             y = 3*y+1
        #         else:
        #             y = y/2
        #         if y in todo:
        #             todo.remove(y)
        #         stack.append(y)
        #     if y == 1:
        #         ranks = ranks + stack
        #     else:
        #         for i in range(len(stack)-1):
        #             ranks.insert(ranks.index(stack[-i])+1, stack[-i-1])
        # i = 0
        # nums = set(range(lo, hi+1))
        # for r in reversed(ranks):
        #     if r in nums:
        #         i += 1
        #         print(r)
        #     if i == k:
        #         return int(r)


from heapq import heapify, heappop

cache = {
    1: 0
}


def collatz(y):
    if y in cache:
        return cache[y]
    
    x = y
    steps = 0
    while x > 1:
        if x % 2 == 1:
            x = 3 * x + 1
        else:
            x //= 2
            
        steps += 1
        if x in cache:
            ans = cache[x] + steps
            break
    else:
        ans = steps

    cache[y] = ans
    return ans


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        powers = [(collatz(x), x) for x in range(lo, hi + 1)]
        heapify(powers)
        
        for _ in range(k):
            x = heappop(powers)

        return x[1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        if lo==hi==k==1:return 1
        dic={}
        def fun(n,count):
            if n==1:return count
            count+=1
            if n%2==0:n//=2
            else:n=n*3+1
            if n in dic:return count+dic[n]
            return fun(n,count)
        ans=[] 
        for i in range(lo,hi+1):
            dic[i]=fun(i,0)
        return sorted(list(dic.items()),key=lambda x :x[1])[k-1][0]
        


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        if lo == 1 and hi == 1 and k == 1:
            return 1

        memo = {}

        def count_steps(x, count, memo):
            if x == 1:
                return count
            count += 1
            if x % 2 == 0:
                x = x // 2
            else:
                x = 3 * x + 1

            if x in memo:
                return count + memo[x]

            return count_steps(x, count, memo)

        for x in range(lo, hi+1):
            memo[x] = count_steps(x, 0, memo)

        return sorted(memo.items(), key=lambda x: x[1])[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {}
        def num_steps(num):
            if num == 1:
                return 0
            elif num in memo:
                return memo[num]
            
            if num % 2 == 0:
                memo[num] = num_steps(num / 2) + 1
            else:
                memo[num] = num_steps(num * 3 + 1) + 1
            
            return memo[num]
        
        vals = []
        for i in range(lo, hi + 1):
            vals.append((i,num_steps(i)))
            
        vals = sorted(vals, key = lambda x: (x[1], x[0]))
        print(vals)
        vals = [i for i,j in vals]
        return vals[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        heap = []
        self.memo = {}
        
        for i in range(lo, hi+1):
            power = self.computer_power(i)
            self.memo[i] = power
            heapq.heappush(heap, (power, i))
        
        k_now = 1
        while heap:
            new_power, i = heapq.heappop(heap)
            if k_now == k:
                return i
            k_now += 1
        return result
    
    def computer_power(self, val):
        if val == 1:
            return 0
        if val in self.memo:
            return self.memo[val]
        
        if val % 2 == 0:
            return 1 + self.computer_power(val // 2)
        else:
            return 1 + self.computer_power(3*val + 1)


class Solution:
    def __recur(self, dp, num):
        if num in dp:
            return dp[num]
        res = 0
        if num%2 == 0:
            res = self.__recur(dp, int(num/2)) + 1
        else:
            res = self.__recur(dp, int(num*3) + 1) + 1
        dp[num] = res
        return res
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = {1:0}
        for num in range(1,1001):
            self.__recur(dp, num)
        power_order = sorted([(dp[key],key) for key in dp if key >= lo and key<=hi])
        return power_order[k-1][1]
        
        


class Solution:
    def num_count(self, x, count):
        if x == 1:
            return count
        count += 1
        if x % 2 == 0:
            x = x // 2
        else:
            x = x * 3 + 1
        if x in self.dp:
            return count + self.dp[x]
        return self.num_count(x, count)
        
    def getKth(self, lo: int, hi: int, k: int) -> int:
        self.dp = {}
        for x in range(lo, hi + 1):
            self.dp[x] = self.num_count(x, 0)
        return sorted(self.dp.items(), key = lambda x : x[1])[k - 1][0]

class Solution:
    def power(self, memo, num):
        if num in memo:
            return memo[num]
        
        result = 0
        if num%2 == 0:
            result = self.power(memo, int(num/2)) + 1
        else:
            result = self.power(memo, int(num*3) + 1) + 1
            
        memo[num] = result
        return result
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1:0}
        
        for num in range(1,1001):
            self.power(memo, num)
            
        porder = sorted([(memo[key],key) for key in memo if key >= lo and key<=hi])
        
        return porder[k-1][1]
    
        
        
        


class Solution:
    def __recur(self, dp, num):
        if num in dp:
            return dp[num]
        res = 0
        if num%2 == 0:
            res = self.__recur(dp, int(num/2)) + 1
        else:
            res = self.__recur(dp, int(num*3) + 1) + 1
        dp[num] = res
        return res
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = {1:0}
        for i in range(1,1001):
            self.__recur(dp, i)
        power_order = sorted([(dp[key],key) for key in dp if key >= lo and key<=hi])
        return power_order[k-1][1]

class Solution:
    def __recur(self, dp, num):
        if num in dp:
            return dp[num]
        if num == 1:
            return 0
        res = 0
        if num%2 == 0:
            res = self.__recur(dp, int(num/2)) + 1
        else:
            res = self.__recur(dp, int(num*3) + 1) + 1
        dp[num] = res
        return res
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = {}
        dp[1] = 0
        dp[2] = 1
        for i in range(1,1001):
            self.__recur(dp, i)
        temp = [(dp[key],key) for key in dp if key >= lo and key<=hi]
        temp.sort()
        return temp[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        dic = {}
        for num in range(lo, hi+1):
            if num in dic:
                res.append((dic[num], num))
                continue 
                
            steps, tmp = 0, num
            while num > 1:
                if num in dic:
                    steps += dic[num]
                    break
                if num%2:
                    num = 3*num + 1
                else:
                    num //= 2   
                steps += 1
                
            dic[tmp] = steps
            res.append((steps, tmp))
        res.sort()
        return res[k-1][1]

dp = {}

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        result = [(num, self.getPowerValue(num)) for num in range(lo, hi+1)]
        
        result.sort(key=lambda x: (x[1], x[0]))
        
        return result[k-1][0]
        
        
        
    
    def getPowerValue(self, num) -> int:
        if num == 1:
            return 0
        
        if num in dp:
            return dp[num]
        
        if num%2 == 0:
            dp[num] = 1 + self.getPowerValue(num/2)
            
        else:
            dp[num] = 1 + self.getPowerValue(3*num + 1)
            
        
        return dp[num]

class Solution:
    def __init__(self):
        self.cache = {1: 0,2: 1,3: 7,4: 2, 5: 5, 6: 8, 7: 16, 8: 3}

    def getPower(self, n):
        steps = 0
        rem = n % 8
        if rem == 0:
            n = n // 8
            steps = 3
        elif rem == 1:
            n = n // 8 * 9 + 2
            steps = 5
        elif rem == 2:
            n = n // 8 * 3 + 1
            steps = 4
        elif rem == 3:
            n = n // 8 * 9 + 4
            steps = 5
        elif rem == 4 or rem == 5:
            n = n // 8 * 3 + 2
            steps = 4
        elif rem == 6:
            n = n // 8 * 9 + 8
            steps = 5
        else:
            n = n // 8 * 27 + 26
            steps = 6
        # if n in self.cache.keys(): 
        if n <= 8:
            return self.cache[n] + steps
        else:
            return self.getPower(n) + steps

    def getKth(self, low, high, k):
        data = [self.getPower(i) for i in range(low, high + 1)]
        sorted_data = sorted(zip(data, list(range(len(data)))), key= lambda x:x[0])
        return sorted_data[k - 1][1] + low


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        dp = defaultdict(int)
        dp[1] = 0
        def go(i):
            #print(i)
            if i == 1:
                return 0
            if dp[i] > 0:
                return dp[i]
            if (i % 2) == 0:
                ans = go(i//2) + 1
            else:
                ans = go((3*i)+1) + 1
            dp[i] = ans
            return ans

        for i in range(lo, hi+1):
             dp[i] = go(i)
        lis = []
        for i in range(lo,hi+1):
            lis.append((dp[i],i))
        lis.sort()
        ans = lis[k-1]
        return ans[1]


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        res = []
        dic = {}
        for num in range(lo, hi+1):
            steps = 0
            tmp = num
            while num > 1:
                if num in dic:
                    steps += dic[num]
                    break
                if num%2:
                    num = 3*num + 1
                else:
                    num //= 2   
                steps += 1
                
            dic[tmp] = steps
            res.append((steps, tmp))
        res.sort()
        return res[k-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def powerof(num, memo):
            step = 0
            n = num
            while n > 1:
                if n in memo:
                    return step + memo[n]
                if n % 2 == 0:
                    n = n // 2
                else:
                    n = 3*n+1
                step += 1
            memo[num] = step
            return step
        mheap = []
        memo = {}
        for n in range(lo, hi+1):
            mheap.append([powerof(n, memo), n])
        heapq.heapify(mheap)
        return heapq.nsmallest(k, mheap)[-1][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        d = {}
        def getPowerValue(x):
            if x in d:
                return d[x]
            steps = 0
            
            original = x
            while x != 1:
                if x%2:
                    x = 3*x+1
                else:
                    x /= 2
                    
                steps += 1
                
                if x in d:
                    steps += d[x]
                    break
        
            d[original] = steps
            return steps
        
        return sorted([x for x in range(lo, hi+1)], key=getPowerValue)[k-1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        h={}
        heap=[]
        for i in range(lo,hi+1):
            print(i)
            q=deque()
            q.append((0,i))
            while q:
                x=q.popleft()
                if x[1]==1 or x[1] in h:
                    #print(i,x)
                    xx=x[0]
                    if x[1] in h:
                        xx+=h[x[1]]
                        #print(xx)
                    if i not in h:
                        h[i]=xx
                    if len(heap)<k:
                        heapq.heappush(heap,(-xx,-i))
                    else:
                        if -xx>heap[0][0]:
                            heapq.heappop(heap)
                            heapq.heappush(heap,(-xx,-i))
                    break;
                if x[1]%2==0:
                    q.append((x[0]+1,x[1]//2))
                else:
                    q.append((x[0]+1,(3*x[1])+1))         
        #print(heap)   
        return -heap[0][1]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache
        def getPower(x):
            if x == 1: return 0
            if x % 2 == 0: return 1+getPower(x // 2)
            return 1+getPower(3 * x + 1)
        return sorted([(getPower(x), x) for x in range(lo, hi + 1)])[k - 1][1]

class Solution:
    def power(self, memo, num):
        if num in memo:
            return memo[num]
        
        result = 0
        if num%2 == 0:
            result = self.power(memo, num//2)+ 1
        else:
            result = self.power(memo, num*3 + 1) + 1
            
        memo[num] = result
        return result
    
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1:0}
        
        for num in range(1,1001):
            self.power(memo, num)
            
        porder = sorted([(memo[key],key) for key in memo if key >= lo and key<=hi])
        
        return porder[k-1][1]
    
        
        
        


from functools import lru_cache
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache
        def helper(x):
            if x==1: return 1
            if x%2==0:return 1+helper(x//2)
            return helper(3*x+1)+1
        
        lookup={}
        for x in range(lo,hi+1):
            lookup[x]=helper(x)
        return sorted(lookup.items(),key=lambda x:x[1])[k-1][0]

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        @lru_cache
        def getPower(x):
            if x==1:
                return 0
            if x%2==0:
                return 1+getPower(x//2)
            return 1+getPower(3*x+1)
        X = [(getPower(x),x) for x in range(lo,hi+1)]
        X.sort()
        return X[k-1][1]

from functools import lru_cache
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        
        @lru_cache
        def getPower(x: int)-> int:            
            if x == 1:
                return 1
            if x % 2 == 0:
                return getPower(x//2) + 1
            
            if x % 2 == 1:
                return getPower(3*x+1) + 1
        
        powers = [0]*(hi-lo+1)
        if len(powers) == 1:
            return lo
        for i in range(len(powers)):
            
            if i+lo != 1:
                powers[i] = getPower(i+lo)-1
            else:
                powers[i] = getPower(i+lo)
        
        idxs = sorted(range(len(powers)), key = lambda x: powers[x])
        # print(powers, idxs)
        return lo+idxs[k-1]

from functools import lru_cache


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:

        @lru_cache
        def power(n):
            if n == 1:
                return 0
            if n % 2 == 0:
                return 1 + power(n // 2)
            else:
                return 1 + power(3 * n + 1)

        powers = [(power(n), n) for n in range(lo, hi+1)]
        powers.sort()

        return powers[k-1][1]


class Solution:
    def power(self, n):
        c = 0
        while n != 1:
            if n % 2:
                n = (n * 3) + 1
            else:
                n //= 2
            c += 1
        return c
    def getKth(self, lo: int, hi: int, k: int) -> int:
        e = [i for i in range(lo, hi+1)]
        e.sort(key = self.power)
        return e[k-1]


import heapq
class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {}
        q = []
        for num in range(lo,hi+1):
            count = 0
            tmp = num
            while num != 1:
                if num not in memo:  
                    if num % 2 == 0:
                        cal = num//2
                    else:
                        cal = 3*num +1
                    memo[num] = cal
                
                num = memo[num]
                count+=1
            
            heapq.heappush(q,(count,tmp))
        
        while k>0:
            item = heapq.heappop(q)
            #print(item)
            k-=1
        return item[1]