text: #include <iostream>
  #include <cstdio>
  #include <string>
  #include <cstring>
  #include <cstdlib>
  #include <stack>
  #include <algorithm>
  #include <cctype>
  #include <vector>
  #include <queue>
  #include <tr1/unordered_map>
  #include <cmath>
  #include <map>
  #include <bitset>
  #include <set>
  using namespace std;
  typedef long long ll;
  typedef unsigned long long ull;
  typedef vector<int> vi;
  typedef pair<int,int> ii;
  typedef vector< ii > vii;
  ///////////////////////////////UTIL/////////////////////////////////
  #define ALL(x) (x).begin(),x.end()
  #define CLEAR0(v) memset(v, 0, sizeof(v))
  #define CLEAR(v, x) memset(v, x, sizeof(v))
  #define IN0(x, n) ((x) > -1 && (x) < n)
  #define IN(x, a, b) ((x) >= a && (x) <= b)
  #define COPY(a, b) memcpy(a, b, sizeof(a))
  #define CMP(a, b) memcmp(a, b, sizeof(a))
  #define REP(i,n) for(int i = 0; i<n; i++)
  #define REPP(i,a,n) for(int i = a; i<n; i++)
  #define REPD(i,n) for(int i = n-1; i>-1; i--)
  #define REPDP(i,a,n) for(int i = n-1; i>=a; i--)
  #define pb push_back
  #define pf push_front
  #define sz size()
  #define mp make_pair
  /////////////////////////////NUMERICAL//////////////////////////////
  #define INCMOD(a,b,c) (((a)+b)%c)
  #define DECMOD(a,b,c) (((a)+c-b)%c)
  #define ROUNDINT(a) (int)((double)(a) + 0.5)
  #define INF 0x3f3f3f3f
  #define EPS 1e-9
  /////////////////////////////BITWISE////////////////////////////////
  #define CHECK(S, j) (S & (1 << j))
  #define CHECKFIRST(S) (S & (-S))  //PRECISA DE UMA TABELA PARA TRANSFORMAR EM INDICE
  #define SET(S, j) S |= (1 << j)
  #define SETALL(S, j) S = (1 << j)-1  //J PRIMEIROS
  #define UNSET(S, j) S &= ~(1 << j)
  #define TOOGLE(S, j) S ^= (1 << j)
  ///////////////////////////////64 BITS//////////////////////////////
  #define LCHECK(S, j) (S & (1ULL << j))
  #define LSET(S, j) S |= (1ULL << j)
  #define LSETALL(S, j) S = (1ULL << j)-1ULL  //J PRIMEIROS
  #define LUNSET(S, j) S &= ~(1ULL << j)
  #define LTOOGLE(S, j) S ^= (1ULL << j)
  //__builtin_popcount(m)
  //scanf(" %d ", &t);
  
  #define MAXN 1001
  
  vi st[4*MAXN];
  
  // Segment Tree Library: The segment tree is stored like a heap array
  void st_build(vi &st, const vi &A, int vertex, int L, int R) {
    if (L == R)                              // as L == R, either one is fine
      st[vertex].pb(L);                                      // store the index
    else {   // recursively compute the values in the left and right subtrees
      int nL = 2 * vertex, nR = 2 * vertex + 1;
      st_build(st, A, nL, L              , (L + R) / 2);
      st_build(st, A, nR, (L + R) / 2 + 1, R          );
      vi lContent = st[nL]     , rContent = st[nR];
      int lValue   = A[lContent], rValue   = A[rContent];
      st[vertex] = (lValue <= rValue) ? lContent : rContent;
  } }
  
  void st_create(vi &st, const vi &A) {       // if original array size is N,
       // the required segment tree array length is 2*2^(floor(log2(N)) + 1);
    int len = (int)(2*pow(2.0, floor((log((double)A.size())/log(2.0)) + 1)));
    st.assign(len, 0); // create vector of size `len' and fill it with zeroes
    st_build(st, A, 1, 0, (int)A.size() - 1);              // recursive build
  }
  
  int st_rmq(vi &st, const vi &A, int vertex, int L, int R, int i, int j) {
    if (i >  R || j <  L) return -1;   // current segment outside query range
    if (L >= i && R <= j) return st[vertex];            // inside query range
  
       // compute the min position in the left and right part of the interval
    int p1 = st_rmq(st, A, 2 * vertex    , L              , (L+R) / 2, i, j);
    int p2 = st_rmq(st, A, 2 * vertex + 1, (L+R) / 2 + 1, R          , i, j);
  
                          // return the position where the overall minimum is
    if (p1 == -1) return p2;     // if we try to access segment outside query
    if (p2 == -1) return p1;                                 // same as above
    return (A[p1] <= A[p2]) ? p1 : p2; }
  
  int st_rmq(vi &st, const vi& A, int i, int j) {     // function overloading
    return st_rmq(st, A, 1, 0, (int)A.size() - 1, i, j); }
  
  int st_update_point(vi &st, vi &A, int node, int b, int e, int idx, int new_value) {
    // this update code is still preliminary, i == j
    // must be able to update range in the future!
    int i = idx, j = idx;
  
    // if the current interval does not intersect 
    // the update interval, return this st node value!
    if (i > e || j < b)
      return st[node];
  
    // if the current interval is included in the update range,
    // update that st[node]
    if (b == i && e == j) {
      A[i] = new_value; // update the underlying array
      return st[node] = b; // this index
    }
  
    // compute the minimum position in the 
    // left and right part of the interval
    int p1, p2;
    p1 = st_update_point(st, A, 2 * node    , b              , (b + e) / 2, idx, new_value);
    p2 = st_update_point(st, A, 2 * node + 1, (b + e) / 2 + 1, e          , idx, new_value);
  
    // return the position where the overall minimum is
    return st[node] = (A[p1] <= A[p2]) ? p1 : p2;
  }
  
  int st_update_point(vi &st, vi &A, int idx, int new_value) {
    return st_update_point(st, A, 1, 0, (int)A.size() - 1, idx, new_value); }
  