<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>

#include <bits/stdc++.h> // Include every standard library
// Common file
#include <ext/pb_ds/assoc_container.hpp>
// Including tree_order_statistics_node_update
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef pair<char,char> pcc;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<pll> vll;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<ld> vd;
typedef vector<vd> vvd;
typedef pair<ll,pll> ppll;

double EPS = 1e-9;
int INF = 2000000005;
long long INFF = 4000000000000000005LL;
double PI = acos(-1);
int dirx[8] = { -1, 0, 0, 1, -1, -1, 1, 1 };
int diry[8] = { 0, 1, -1, 0, -1, 1, -1, 1 };

#define FOR(a, b, c) for (ll(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (ll(a) = (b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (ll(a) = (b); (a) >= (c); --(a))
#define FORSQ(a, b, c) for (ll(a) = (b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a))
#define FOREACH(a, b) for (auto&(a) : (b))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define RESET(a, b) memset(a, b, sizeof(a))
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
// #define pf push_front
#define eb emplace_back
#define ef emplace_front
#define tiii tuple<int,int,int>
#define mt make_tuple
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)
#define MAX 10000100
// #define mo 998244353
#define mo 1000000007
#define ordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>


// Begin DEBUG //
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '{' << p.first << ", " << p.second << '}';
}

template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
        class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
os << '[';
for (auto it = c.begin(); it != c.end(); ++it)
    os << &", "[2 * (it == c.begin())] << *it;
return os << ']';
}

//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
_NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
(MACRO, ##__VA_ARGS__)
//Change output format here
#define out(x) #x " = " << x << "; "
#define debug(...)                                                              \
cout << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << "\n"

// End DEBUG //

ll add(ll a, ll b, ll c = mo) {ll res=(a+b)%c; return res;}
ll mod_neg(ll a, ll b, ll c = mo) {ll res=(a-b+c)%c; return res;} 
ll mul(ll a, ll b, ll c = mo) {ll res=(a*b)%c; res=(res+c)%c; return res;}

struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const
    {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);

        if (hash1 != hash2) {
            return hash1 ^ hash2;             
        }
        
        // If hash1 == hash2, their XOR is zero.
        return hash1;
    }
};

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int MOD = 1000000007;
struct mi {
    int v;
    explicit operator int() const { return v; }
    mi() { v = 0; }
    mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
    if ((a.v += b.v) >= MOD) a.v -= MOD;
    return a;
}
mi &operator-=(mi &a, mi b) {
    if ((a.v -= b.v) < 0) a.v += MOD;
    return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi &operator*=(mi &a, mi b) { return a = a * b; }
mi pow(mi a, long long p) {
    assert(p >= 0);
    return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
    assert(a.v != 0);
    return pow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }
mi &operator/=(mi &a, mi b) { return a = a/b; }


typedef vector<mi> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;

// Clear the stringstream
// ss.str("");
// ss.clear(); // Clear the stringstream state
// ss.str(str2);

///////////////////////////////////////////
/* Main starts here -> Mukund Krishnatrey*/
///////////////////////////////////////////

bool isValid(ll n, ll m, ll r, ll c){
    if(r>=0 && r<n && c>=0 && c<m) return true;
    else return false;
}

bool compf(pll p1, pll p2)
{
    if(p1.ff!=p2.ff) return p1.ff>p2.ff;
    else return p1.ss<p2.ss;
}

bool comps(pll p1, pll p2)
{
    if(p1.ss!=p2.ss) return p1.ss<p2.ss;
    else return p1.ff<p2.ff;
}

bool comp_len(pll p1, pll p2)
{
    if((p1.ss-p1.ff)!=(p2.ss-p2.ff)) return ((p1.ss-p1.ff)<(p2.ss-p2.ff));
    else return (p1.ff<p2.ff);
}

bool comp_custom(pair<pair<pll,ll>,ll> &p1, pair<pair<pll,ll>,ll> &p2){
    if(p1.ff.ff.ss!=p2.ff.ff.ss) return p1.ff.ff.ss<p2.ff.ff.ss;
    else return p1.ff.ff.ff<p2.ff.ff.ff;
}

struct scomps2
{
    bool operator()(const pll &p1, const pll &p2) const{
        if(p1.ss!=p2.ss) return (p1.ss<p2.ss);
        else return (p1.ff<p2.ff);
    }
};


struct scomps
{
    bool operator()(const pll &p1, const pll &p2) const{
        if(p1.ss!=p2.ss) return (p1.ss<p2.ss);
        else return (p1.ff<p2.ff);
    }
};

struct scomp_cur
{
    bool operator()(pair<pll,ll> p1,pair<pll,ll> p2) const{
        if(p1.ff.ff!=p2.ff.ff) return p1.ff.ff<p2.ff.ff;
        else return p1.ss<p2.ss;
    }
};

class Solution {
public:
    map<int,bool> vis;
    map<int,int> ans;
    int get_transforms(int n){
        if(vis[n]) return ans[n];
        int nxt;
        if(n%2==0) nxt=n/2;
        else nxt=(3*n+1);
        ans[n]=get_transforms(nxt)+1;
        return ans[n];
    }
    int getKth(int lo, int hi, int k) {
        vector <pii> v;
        vis[1]=true;
        ans[1]=0;
        FORN(i,lo,hi){
            if(!vis[i]) {
                ans[i]=get_transforms(i);
            }
            v.pb(mp(ans[i],i));
        }
        sort(all(v));
        return v[k-1].ss;
    }
};
69015