#include <cstdio>
struct T
{
int L, R, value; // [L..R]
T *vl, *vr;
T( int L, int R ) : L(L), R(R), vl(0), vr(0) { }
};
typedef T *Node;
Node Root = new T(0, 1 << 30); // 2^30 = M
void Insert( Node &p, int x, int value )
{
if (p->L == p->R) // [L..R] ----> p.L = v.R = x
p->value = value;
else
{
int m = (p->L + p->R) / 2;
if (p->vl == 0)
{
p->vl = new T(p->L, m);
p->vr = new T(m + 1, p->R);
}
Insert(x <= m ? p->vl : p->vr, x, value);
}
}
// Time = log M
// Memory = O(k * log M)