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