1
import heapq
2

3

4
class Solution:
5
    def power(self, n):
6
        if n in self.dic:
7
            return self.dic[n]
8
        if n % 2:
9
            self.dic[n] = self.power(3 * n + 1) + 1
10
        else:
11
            self.dic[n] = self.power(n // 2) + 1
12
        return self.dic[n]
13

14
    def getKth(self, lo: int, hi: int, k: int) -> int:
15
        self.dic = {1: 0}
16
        for i in range(lo, hi + 1):
17
            self.power(i)
18

19
        lst = [(self.dic[i], i) for i in range(lo, hi + 1)]
20
        heapq.heapify(lst)
21

22
        for i in range(k):
23
            ans = heapq.heappop(lst)
24

25
        return ans[1]