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

<ul>
	<li>if <code>x</code> is even then <code>x = x / 2</code></li>
	<li>if <code>x</code> is odd then <code>x = 3 * x + 1</code></li>
</ul>

<p>For example, the power of <code>x = 3</code> is <code>7</code> because <code>3</code> needs <code>7</code> steps to become <code>1</code> (<code>3 --&gt; 10 --&gt; 5 --&gt; 16 --&gt; 8 --&gt; 4 --&gt; 2 --&gt; 1</code>).</p>

<p>Given three integers <code>lo</code>, <code>hi</code> and <code>k</code>. The task is to sort all integers in the interval <code>[lo, hi]</code> by the power value in <strong>ascending order</strong>, if two or more integers have <strong>the same</strong> power value sort them by <strong>ascending order</strong>.</p>

<p>Return the <code>k<sup>th</sup></code> integer in the range <code>[lo, hi]</code> sorted by the power value.</p>

<p>Notice that for any integer <code>x</code> <code>(lo &lt;= x &lt;= hi)</code> it is <strong>guaranteed</strong> that <code>x</code> will transform into <code>1</code> using these steps and that the power of <code>x</code> is will <strong>fit</strong> in a 32-bit signed integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> lo = 12, hi = 15, k = 2
<strong>Output:</strong> 13
<strong>Explanation:</strong> The power of 12 is 9 (12 --&gt; 6 --&gt; 3 --&gt; 10 --&gt; 5 --&gt; 16 --&gt; 8 --&gt; 4 --&gt; 2 --&gt; 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> lo = 7, hi = 11, k = 4
<strong>Output:</strong> 7
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= lo &lt;= hi &lt;= 1000</code></li>
	<li><code>1 &lt;= k &lt;= hi - lo + 1</code></li>
</ul>

class Solution:
    def getKth(self, lo, hi, k):
        s, stk, pws = [], [], {1: 0, 2: 1, 3: 7, 4: 2, 5: 5, 6: 8, 7: 16, 8: 3, 9: 19, 10: 6, 11: 14, 12: 9, 13: 9, 14: 17, 15: 17, 16: 4, 17: 12, 18: 20, 19: 20, 20: 7, 21: 7, 22: 15, 23: 15, 24: 10, 25: 23, 26: 10, 27: 111, 28: 18, 29: 18, 30: 18, 31: 106, 32: 5, 33: 26, 34: 13, 35:13, 36: 21, 37: 21, 38: 21, 39: 34, 40: 8, 41: 109, 42: 8, 43: 29, 44: 16, 45: 16, 46: 16, 47: 104, 48: 11, 49: 24, 50: 24, 51:24, 52: 11, 53: 11, 54: 112, 55: 112, 56: 19, 57: 32, 58: 19, 59: 32, 60: 19, 61: 19, 62: 107, 63: 107, 64: 6, 65: 27, 66: 27, 67: 27, 68: 14, 69: 14, 70: 14, 71: 102, 72: 22, 73: 115, 74: 22, 75: 14, 76: 22, 77: 22, 78: 35, 79: 35, 80: 9, 81: 22, 82: 110, 83: 110, 84: 9, 85: 9, 86: 30, 87: 30, 88: 17, 89: 30, 90: 17, 91: 92, 92: 17, 93: 17, 94: 105, 95: 105, 96: 12, 97: 118, 98: 25, 99: 25, 100: 25, 101: 25, 102: 25, 103: 87, 104: 12, 105: 38, 106: 12, 107: 100, 108: 113, 109: 113, 110: 113, 111: 69, 112:20, 113: 12, 114: 33, 115: 33, 116: 20, 117: 20, 118: 33, 119: 33, 120: 20, 121: 95, 122: 20, 123: 46, 124: 108, 125: 108, 126:108, 127: 46, 128: 7, 129: 121, 130: 28, 131: 28, 132: 28, 133: 28, 134: 28, 135: 41, 136: 15, 137: 90, 138: 15, 139: 41, 140: 15, 141: 15, 142: 103, 143: 103, 144: 23, 145: 116, 146: 116, 147: 116, 148: 23, 149: 23, 150: 15, 151: 15, 152: 23, 153: 36, 154: 23, 155: 85, 156: 36, 157: 36, 158: 36, 159: 54, 160: 10, 161: 98, 162: 23, 163: 23, 164: 111, 165: 111, 166: 111, 167: 67, 168: 10, 169: 49, 170: 10, 171: 124, 172: 31, 173: 31, 174: 31, 175: 80, 176: 18, 177: 31, 178: 31, 179: 31, 180: 18, 181: 18, 182: 93, 183: 93, 184: 18, 185: 44, 186: 18, 187: 44, 188: 106, 189: 106, 190: 106, 191: 44, 192: 13, 193: 119, 194: 119, 195: 119, 196: 26, 197: 26, 198: 26, 199: 119, 200: 26, 201: 18, 202: 26, 203: 39, 204: 26, 205: 26, 206: 88, 207: 88, 208: 13, 209: 39,210: 39, 211: 39, 212: 13, 213: 13, 214: 101, 215: 101, 216: 114, 217: 26, 218: 114, 219: 52, 220: 114, 221: 114, 222: 70, 223:70, 224: 21, 225: 52, 226: 13, 227: 13, 228: 34, 229: 34, 230: 34, 231: 127, 232: 21, 233: 83, 234: 21, 235: 127, 236: 34, 237:34, 238: 34, 239: 52, 240: 21, 241: 21, 242: 96, 243: 96, 244: 21, 245: 21, 246: 47, 247: 47, 248: 109, 249: 47, 250: 109, 251:65, 252: 109, 253: 109, 254: 47, 255: 47, 256: 8}
        for _i in range(lo, hi+1):
            i = _i
            while (pw := pws.get(i, 1000)) == 1000:
                stk.append(i)
                if i % 2:i = i*3+1
                else:i //= 2
            while stk:
                pw += 1
                pws[stk.pop()] = pw
            s.append((pw, _i))
        s.sort()
        return s[k-1][1]
17400