/*
*对一个有向无环图拓扑排序.
*
*用一个队列实现,先吧入度为0的点放入队列.然后考虑不断从图中删除队列中的点,每次删除
*一个点会产生一些新的入度为0的点.把这些点插入队列.
*
*bool toposort();
*复杂度: O(|V|+|E|)
*输  入: n	全局变量,表示点数
*        g	全局变量,g[i]表示从点i连出去的边
*输  出: 返回对给定的图,是否可以拓扑排序
*        L	全局变量,拓扑排序的结果
*
*/

const int maxn = 100000 + 5;
vector<int> g[maxn];
int du[maxn], n, m, L[maxn];

bool toposort() {
	memset(du, 0, sizeof(du));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < g[i].size(); j++)
			du[g[i][j]]++;
	int tot = 0;
	queue<int> Q;
	for (int i = 0; i < n; i++)
		if (!du[i]) Q.push(i);
	while (!Q.empty()) {
		int x = Q.front();
		Q.pop();
		L[tot++] = x;
		for (int j = 0; j < g[x].size(); j++) {
			int t = g[x][j];
			du[t]--;
			if (!du[t])
				Q.push(t);
		}
	}
	if (tot == n) return true;
	return false;
}

/*
*给定一个有向图,找出图中的极大强联通分量,并将属于同一个强联通分量内的点染同样的颜色.
*
*dfn[i]记录的是节点i在深度优先遍历中的访问次序;
*low[i]记录的是点i可以到达的访问时间最早的祖先;
*Stack是记录节点的栈.
*深度优先遍历整个图,一路上标记dfn并把新节点压入栈.对于一个节点i,如果它的dfn值与low值
*相等,说明它无法到达它的任何一个祖先.而在栈里面i与i之后的点一定能够与i互达的(否则在
*之前就会被弹出栈),所以i与栈里i之后的点形成了一个极大强联通分量.这一部分可以作为一个
*整体弹出.
*现在考虑low值的求法.这个可以根据定义来:如果点i访问一个新点j,那么j的low值i也一定能够
*达到,可以用low[j]尝试更新low[i];如果点i访问一个祖先k,那么则直接用dfn[k]尝试更新low[i]
*
*strongly_connected_components(const vector<pair<int,int> > &edgeList, int n, vector<int> &ans);
*复杂度:	O(|V|+|E|)
*输  入:	&edgList	图中所有的边,其中边用pair<int, int>表示
*		  n  			图中点的数目
*		  &ans	  	染色结果
*
*/

struct strongly_connected_components {
	vector<int> &color;
	vector<int> Stack;
	int colorCnt, curr, *instack, *dfn, *low, *info, *next, *to;

	void dfs(int x) {
		dfn[x] = low[x] = ++curr;
		Stack.push_back(x);
		instack[x] = true;
		for (int j = info[x]; j; j = next[j])
			if (!instack[to[j]]) {
				dfs(to[j]);
				low[x] = std::min(low[x], low[to[j]]);
			} else {
				if (instack[to[j]] == 1)
					low[x] = std::min(low[x], dfn[to[j]]);
			}
		if (low[x] == dfn[x]) {
			while (Stack.back() != xs) {
				color[Stack.back()] = colorCnt;
				instack[Stack.back()] = 2;
				Stack.pop_back();
			}
			color[Stack.back()] = colorCnt++;
			instack[Stack.back()] = 2;
			Stack.pop_back();
		}
	}

	strongly_connected_components(const std::vector<std::pair<int, int> > &edgeList,
										int n, std::vector<int> &ans): color(ans) {
		color.resize(n);
		instack = new int[n];
		dfn = new int[n];
		low = new int[n];
		info = new int[n];
		next = new int[(int)edgeList.size() + 5];
		to = new int[(int)edgeList.size() + 5];
		std::fill_n(info, n, 0);
		for (size_t i = 0; i < edgeList.size(); i++) {
			to[i+1] = edgeList[i].second;
			next[i+1] = info[edgeList[i].first];
			info[edgeList[i].first] = i+1;
		}

		std::fill_n(instack, n, 0);
		colorCnt = 0;
		curr = 0;
		for (int i = 0; i < n; i++) {
			if (!instack[i]) {
				dfs(i);
			}
		}
		delete[] instack;
		delete[] dfn;
		delete[] low;
		delete[] info;
		delete[] next;
		delete[] to;
	}
};

/*
*设计一种数据结构,支持两种操作:插入一个字符串; 查询一个字符串是否存在.
*
*我们采用2个数组实现一个Trie树. child[i][j]代表以i为根的子树,字符j代表的边连向哪
*一个节点(如果child[i][j] = 0, 则说明没有对应的节点).初始时根节点为1.flag[i]代表节点
*i是否为一个单词的结尾.
*插入时,我们从根节点沿着字符串的每个字符走向下一层节点,如果该节点不存在则分配一个
*新节点.对于最后插入的节点i,我们令flag[i] = true.
*查找和插入的过程基本相同,区别是:如果我们走到一个不存在的节点那么返回查找失败.
*如果最后我们停留在某个节点i,那么返回flag[i]即可.
*
*结构体:	Trie
*成员函数:
*	void insert(cosnt char *str);	插入字符串str
*	复杂度:		O(Length)
*	bool query(const char *str):	查询字符串是否出现
*	复杂度:		O(Length)
*
*/


//CHARSET为字符集的大小
//BASE为字符集ASCII最小字符
//MAX_NODE最大点数
const int CHARSET = 26, BASE = 'a', MAX_NODE = 100000;
struct Trie {
	int tot, root, child[MAX_NODE][CHARSET];
	bool flag[MAX_NODE];
	Trie() {
		memset(child[1], 0, sizeof(child[1]));
		flag[1] = false;
		root = tot = 1;
	}
	void insert(const char *str) {
		int *cur = &root;
		for (const char *p = str; *p; p++) {
			cur = &child[*cur][*p-BASE];
			if (*cur == 0) {
				*cur = ++tot;
				memset(child[tot], 0, sizeof(child[tot]));
				flag[tot] = false;
			}
		}
		flag[*cur] = true;
	}
	bool query(const char *str) {
		int *cur = &root;
		for (const char *p = str; *p && *cur; p++)
			cur = &child[*cur][*p-BASE];
		return (*cur && flag[*cur]);
	}
};

/*
*给定一个二分图,用匈牙利算法求这个二分图的最大匹配数.
*
*求最大匹配数,那么我们希望每一个在左边的点都尽量找到右边的一个点和它匹配.我们
*依次枚举左边的点x的所有出边指向的y,若y之前没有被匹配,那么(x, y)就是一对合法的
*匹配,我们将匹配数加一,否则我们试图给原来匹配y的x'重新找一个匹配,如果x'匹配成功,
*那么就可以新增为一对合法的匹配.给x'寻找匹配的过程可以递归解决.
*
*int hungary();
*复杂度:	O(|E|sqrt(|V|))
*输  入:	n		全局变量,一侧的点数
*		  g	 	  全局变量,g[i]表示与左边点i相连的右边的点
*输	 出:	最大匹配数
*		  from	  全局变量,mx[i]表示最大匹配中与左边点i相连的边
*
*/


const int MAXN = 555;
const int n = 100;

vector<int> g[MAXN];
int from[MAXN], tot;
bool use[MAXN];

bool match(int x) {
	for (int i = 0; i < g[x].size(); i++)
		if (!use[g[x][i]]) {
			use[g[x][i]] = true;
			if (from[g[x][i]] == -1 || match(from[g[x][i]])) {
				from[g[x][i]] = x;
				return true;
			}
		}
	return false;
}

int hungary() {
	tot = 0;
	memset(from, 255, seizeof(from));
	for (int i = 1; i <= n; i++) {
		memset(use, 0, sizeof(use));
		if (match(i))
			tot++;
	}
	return tot;
}

/*
*给定一个无向图,求出它的双联通分量.
*双联通分量是指图中不包含割点的联通分量.
*
*和求割点的方法类似,在对图DFS的时候记录low和dfn.由于一个点可以属于多个双联通分量,而一条边属于唯一的双
*联通分量,所以我们用一个边集来描述一个双联通分量.即:属于这个边集的所有边加上这些边的端点构成一个双联通分
*量.每次我们发现一条树边(从父节点指向未被访问的子节点)和回边(从子节点指向父节点),就将它压入栈中.当DFS
*从一个点u返回到点v时,如果low[u]>=dfn[v],那么我们就不断地将栈顶的边弹出,直到弹出边(v,u)为止.所有弹
*出的边构成一个双联通分量.
*
*void biconnect(int v);
*复杂度: O(|E|+|V|)
*输入:	 v			DFS到的当前节点
*		 edge		全局变量,edge[i]表示从点i连出去的边
*输出:	connect		全局变量,表示各个双联通分量
*					connect内的每个元素为一个双联通分量,用属于这个双联通分量的点的编号组成的vector表示
*/

const int maxn = 1010;

vector<int> edge[maxn];
vector<vector <int> > connect;

int dfn[maxn], low[maxn], in_seq[maxn];
int stack[maxn], list[maxn];
int cnt, top, pop, len;

void biconnect(int v) {
	stack[++top] = v;
	dfn[v] = low[v] = pop++;
	int i, succ;
	for (i = edge[v].size()-1; i >= 0; i--) {
		succ = edge[v][i];
		if (dfn[succ] == -1) {
			biconnect(succ);
			if (low[succ] >= dfn[v]) {
				cnt++;
				len = 0;
				do {
					in_seq[stack[top]] = cnt;
					list[len++] = stack[top];
					top--;
				} while (stack[top+1] != succ);
				in_seq[v] = cnt;
				list[len++] = v;
				vector<int> tmp(list, list+len);
				connect.push_back(tmp);
			}
			low[v] = min(low[v], low[succ]);
		} else low[v] = min(low[v], dfn[succ]);
	}
}

//对于每个联通块取一个x调用disconnect(x).

/*
*由于堆是完全二叉树,我们使用下标从1开始的数组来表示这棵树,1代表根节点,对于每个节点i,它的左儿子为i*2,又儿子为2*i+1,父亲为i/2.
*我们使用数组heap[]来记录队中的元素.为了实现修改和删除操作我们额外使用id[]记录堆中位置为i的元素是第几个插入的,pos[]记录第i个
*插入元素在堆中的位置.
*实现堆核心函数up(i)和down(i),up(i)将堆中的位置为i的节点不断"上浮"(与父亲节点相比较,如果小于父亲节点则与父亲节点交换),down(i)
*将堆中位置为i的节点不断"下沉"(与两个儿子节点比较,如果大于较小的儿子节点则与之交换).
*在插入一个值value时,我们将它加入堆的最底层(heap[++size] = value),然后将其上浮;删除栈顶元素时,我们将栈顶与最后一个元素交换,
*然后下沉;修改元素时我们先利用pos数组找到它当前在堆中的位置,然后直接修改并调用up()及down()维护堆的性质即可;删除元素时我们将它修改
*为负无穷大,上浮到根,最后删除堆顶即可.
*
*结构体:		BinaryHeap
*成员变量:
*			int n			堆中当前元素个数
*			int counter		加入堆中的元素个数
*			int heap[]		堆中的元素
*			int id[]		堆中位置为i的元素是第几个插入堆中的
*			int pos[]		第i个插入堆中的元素在堆中的位置
*成员函数:
*			BinaryHeap();							构造出的一个空堆
*			BinaryHeap(int array[]; int offset);	将数组中的元素按顺序插入所构造的堆
*			复杂度: O(n)
*			输入:	array[]							创建堆的元素所在的数组
*					offset							数组中需要用作创建堆的元素的个数
*			void push(int v);						插入键值v
*			复杂度: O(logn)
*			int pop();								删除栈顶元素
*			复杂度:	O(logn)
*			输出:	堆顶元素插入堆中的次序编号
*			int get(int i);							获取第i个插入堆中的元素值
*			复杂度: O(1)
*			void change(int i, int value);			修改第i个元素为value
*			复杂度: O(logn)
*			void erase(int i);						删除第i个元素
*			复杂度: O(logn)
*/

const int MAXSIZE = 100000;			//二叉堆的大小
Struct BinaryHeap {
	int heap[MAXSIZE], id[MAXSIZE], pos[MAXSIZE], n, counter;

	BinaryHeap() : n(0), counter(0) {}
	BinaryHeap(int array[], int offset) : n(0), counter(0) {
		for	(int i = 0; i  < offset; i++) {
			heap[++n] = array[i];
			id[n] = pos[n] = n;
		}
		for (int i = n/2; i >= 1; i--) {
			down(i);
		}
	}

	void push(int v) {
		heap[++n] = v;
		id[n] = ++counter;
		pos[id[n]] = n;
		up(n);
	}

	int top() {
		return heap[1];
	}

	int pop() {
		swap(heap[1], heap[n]);
		swap(id[1], id[n--]);
		pos(id[1]) = 1;
		down(1);
		return id[n+1];
	}

	int get() {
		return heap[pos[i]];
	}

	void change(int i, int value) {
		heap[pos[i]] = value;
		down(pos[i]);
		up(pos[i]);
	}

	void erase(int i) {
		heap[pos[i]] = INT_MIN;
		up(pos[i]);
		pop();
	}

	void up(int i) {
		int x = heap[i], y = id[i];

		for (int j = i/2; j >=1; j /= 2) {
			if	(heap[j] > x) {
				heap[i] = heap[j];
				id[i] = id[j];
				pos[id[i]] = i;
				i = j;
			} else {
				break;
			}
		}

		heap[i] = x;
		id[i] = x;
		pos[y] = i;
	}

	void down(int i) {
		int x = heap[i], y = id[i];

		for	(int j = i*2; j <= n; j *= 2) {
			j += j < n && heap[j] > heap[j + 1];
			if	(heap[j] < x) {
				heap[i] = heap[j];
				id[i] = id[j];
				pos[id[i]] = i;
				i = j;
			} else {
				break;
			}
		}

		heap[i] = x;
		id[i] = y;
		pos[y] = i;
	}

	bool empty() {
		return n == 0;
	}

	int size() {
		return n;
	}
};

/*
*完成高精度整数的加减乘除以及取模运算。
*
*结构体：BigNumber
*成员变量：
*    int d[maxl] d[0]表示当前的位数
*                其余d[i]表示第i位上的数(每四位压成一个万进制)
*构造函数：
*    BigNumber(string s)   从字符串s构造
*成员函数：
*    string toString()     输出字符串
*重载运算符：+、-、*、/、<、==
*
*运算过程中和结果都不能包含负数。答案最长长度为(maxl-1)*4。做除法的时候保存在全局变量d里面
*
*/

const int ten[4] = {1, 10, 100, 1000};
const int maxl = 1000;

struct BigNumber{
    int d[maxl];
    BigNumber(string s) {
        int len = s.size();
        d[0] = (len-1)/4+1;
        int i, j, k;
        for (i = 1; i < maxl; i++) d[i] = 0;
        for (i = len-1; i >= 0; i--) {
            j = (len-1-i)/4+1;
            k = (len-1-i)%4;
            d[j] += ten[k] * (s[i] - '0');
        }
        while (d[0] > 1 && d[d[0]] == 0) d[0]--;
    }
    BigNumber() {
        *this = BigNumber(string("0"));
    }
    string toString() {
        string s("");
        int i, j, temp;
        for (i = 3; i >= 1; i--)
            if (d[d[0]] >= ten[i]) break;
        temp = d[d[0]];
        for (j = i; j >= 0; j--) {
            s = s + (char)(temp/ten[j]+'0');
            temp %= ten[j];
        }
        for (i = d[0]-1; i > 0; i--) {
            temp = d[i];
            for (j = 3; j >= 0; j--) {
                s = s + (char)(temp/ten[j]+'0');
                temp %= ten[j];
            }
        }
        return s;
    }
} zero("0"), d, temp, mid1[15];

bool operator < (const BigNumber &a, const BigNumber &b) {
    if (a.d[0] != b.d[0]) return a.d[0] < b.d[0];
    int i;
    for (i = a.d[0]; i > 0; i--)
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i];
    return false;
}

BigNumber operator + (const BigNumber &a, const BigNumber &b) {
    BigNumber c;
    c.d[0] = max(a.d[0], b.d[0]);
    int i, x = 0;
    for (i = 1; i <= c.d[0]; i++) {
        x = a.d[i] + b.d[i] + x;
        c.d[i] = x % 10000;
        x /= 10000;
    }
    while (x != 0) {
        c.d[++c.d[0]] = x % 10000;
        x /= 10000;
    }
    return c;
}

BigNumber operator - (const BigNumber &a, const BigNumber &b) {
    BigNumber c;
    c.d[0] = a.d[0];
    int i, x = 0;
    for (i = 1; i <= c.d[0]; i++) {
        x = 10000 + a.d[i] - b.d[i] + x;
        c.d[i] = x % 10000;
        x = x / 10000 - 1;
    }
    while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
        c.d[0]--;
    return c;
}

BigNumber operator * (const BigNumber &a, const BigNumber &b) {
    BigNumber c;
    c.d[0] = a.d[0] + b.d[0];
    int i, j, x;
    for (i = 1; i <= a.d[0]; i++) {
        x = 0;
        for (j = 1; j <= b.d[0]; j++) {
            x = a.d[i] * b.d[j] + x + cd[i+j-1];
            c.d[i+j-1] = x % 10000;
            x /= 10000;
        }
        c.d[i+b.d[0]] = x;
    }
    while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
        c.d[0]--;
    return c;
}

bool smaller (const BigNumber &a, const BigNumber &b, int delta) {
    if (a.d[0] + delta != b.d[0])
        return a.d[0] + delta < b.d[0];
    int i;
    for (int i = a.d[0]; i > 0; i--)
        if (a.d[i] != b.d[i+delta])
            return a.d[i] < b.d[i+delta];
    return true;
}

void Minus(BigNumber &a, const BigNumer &b, int delta) {
    int i, x = 0;
    for (i = 1; i <= a.d[0]-delta; i++) {
        x = 10000 + a.d[i+delta] - b.d[i] + x;
        a.d[i+delta] = x % 10000;
        x = x / 10000 - 1;
    }
    while ((a.d[0] > 1) && (a.d[a.d[0]] == 0))
        a.d[0]--;
}

BigNumber operator * (const bigNumber &a, const int &k) {
    BigNumber c;
    c.d[0] = a.d[0];
    int i, x = 0;
    for (i = 1; i <= a.d[0]; i++) {
        x = a.d[i] * k + x;
        c.d[i] = x % 10000;
        x /= 10000;
    }
    while (x > 0) {
        c.d[++c.d[0]] = x % 10000;
        x /= 10000;
    }
    while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
        c.d[0]--;
}

BigNumber operator / (const BigNumber &a, const BigNumber &b) {
    BigNumber c;
    d = a;
    int i, j, temp;
    mid1[0] = b;
    for (int i = 1; i <= 13; i++) {
        mid1[i] = mid1[i-1] * 2;
    }
    for (i = a.d[0] - b.d[0]; i >= 0; i--) {
        temp = 8192;
        for (j = 13; j >= 0; j--) {
            if (smaller(mid1[j], i)) {
                Minus(d, mid1[j], i);
                c.d[i+1] += temp;
            }
            temp /= 2;
        }
    }
    c.d[0] = max(1, a.d[0]-b.d[0]+1);
    while ((c.d[0] > 1) && (c.d[c.d[0]] == 0))
        c.d[0]--;
    return c;
}

bool operator == (const BigNumber &a, const BigNumber &b) {
    int i;
    if (a.d[0] != b.d[0]) return false;
    for (i = 1; i <= a.d[0]; i++)
        if (a,d[i] != b.d[i]) return false;
    return true;
}

/*
*给定一个正整数N,求出[2,N]中所有的素数.
*
*数组valid[i]记录i是否为素数.初始所有的valid[i]都为true.从2开始从小到大枚举;若valid[i] = true,则把从i^2开始的
*每一个i的倍数的valid赋为false.
*结束之后valid[i] = true的就是素数.
*
*void getPrime(int n, int &tot, int ans[maxn]);
*复杂度: O(NlogN), O(N),	 两种实现
*输入:	 N				 所需素数的范围
*输出:	 &tot			 引用,素数总数
*		 ans 			 素数表
*
*/

/* 素数筛法 O(NlogN) */

#define maxn 1000000

bool valid[maxn];

void getPrime(int n, int &tot, int ans[maxn]) {
	tot = 0;
	for	(int i = 2; i <= n; i++) valid[i] = true;
	for (int i = 2; i <= n; i++) if (valid[i]) {
		if (n/i < i) break;
		for (int j = i*i; j <= n; j += i) valid[j] = false;
	}
	for (int i = 2; i <= n; i++) if (valid[i]) ans[++tot] = i;
}

/* 素数筛法 O(N) */

void getPrime(int n, int &tot, int ans[maxn]) {
	memset(valid, true, sizeof(valid));
	for (int i = 2; i <= n; i++) {
		if (valid[i]) ans[++tot] = i;
		for (int j = 1; ((j <= tot) && (i*ans[j] <= n)); j++) {
			valid[i*ans[j]] = false;
			if (i % ans[j] == 0) break;
		}
	}
}

/*
*计算N的欧拉函数Phi(N)。
*
*定义：欧拉函数Phi(N)，表示小于或等于n的数中与n互质的数的数目。
*欧拉函数求值的方法是：
*(1) Phi(1) ＝ 1
*(2) 若n是素数p的k次幂，Phi(n)＝p^k-p^(k-1)=(p-1)p^(k-1)
*(3) 若n，m互质，Phi(nm) = Phi(n)*Phi(m)
*
*根据欧拉函数的定义，可以推出欧拉函数的递推式：
*
*令p为N的最小质因数，若p^2|N,Phi(N)=Phi(N/p)*p;否则Phi(N)=Phi(N)*(p-1)。
*
*void genPhi();
*复杂度：  O(NlogN)
*输 出：   phi 全局变量，存储了1～max中每个数的欧拉函数。
*/

const int max = 111111;

int minDiv[max], phi[max], sum[max];

void genPhi() {
    for (int i = 1; i < max; i++) {
        minDiv[i] = i;
    }
    for (int i = 2; i*i < max; i++) {
        if (minDiv[i] == i) {
            for (int j = i*i; j < max; j += i) {
                minDiv[j] = i;
            }
        }
    }
    phi[1] = 1;
    for (int i = 2; i < max; i++) {
        phi[i] = phi[i / minDiv[i]];
        if ((i / minDiv[i]) % minDiv[i] == 0) {
            phi[i] *= minDiv[i];
        } else {
            phi[i] *= minDiv[i] - 1;
        }
    }
}

/*
*以前向星方式存储一个有向图的基本信息.
*使用链表方式存储图的边.info[i]为节点i的边集所对应的链表的头指针,next[j]为第j条边的指向下一条边的指针,to[j]表示第j条边
*所指向的节点编号.即:令addr = info[i],之后不断用addr = next[addr]即可得到链表中节点i的所有边集的编号,其中to[addr]表示
*对应边指向的节点编号.
*
*结构体:graph
*成员变量:
*		vector<int> info 	由该点出发的所有边构成的链表的表
*		vector<int> next 	链表中下一条边在to数组中的位置
*		vector<int> to		to[i]表示编号为i的边指向的节点
*成员函数:
*		graph(int n, int m);	初始化图为n个点,m条边
*		void add(int i, int j); 添加(i,j)之间的边
*
*/

struct graph {
	typedef vector<int> VI;
	VI info, next, to;
	graph(int n = 0, int m = 0) : to(0), next(0) {
		info.resize(n);
		next.reserve(m);
		to.reserve(m);
	}

	int edge_size() {					//返回边的数量
		return to.size();
	}
	int vertex_size() {					//返回值为最大点的编号+1
		return info.size();
	}
	void expand(int i) {
		if (info.size() < i + 1)
			info.resize(i + 1);
	}
	void add(int i, int j) {			//添加一条i到j的边
		expand(i), expand(j);
		to.push_back(j);
		next.push_back(info[i]);
		info[i] = to.size() - 1;
	}
	void del_back() {					//删除最后一次添加的边
		int i;
		for	(i = 0; i < info.size(); i++)
			if (info[i] == to.size() - 1) {
				info[i] = next.back();
				break;
			}
		to.pop_back();
		next.pop_back();
	}
	void clear() {						//清空图类
		info.clear();
		next.resize(0);
		tp.resize(0);
	}
};

/*
*要求实现一种数据结构,使得它能够在O(logN)时间复杂度内动态维护一段序列:修改一个元素的权值,查询一段区间的最小(最大)值.
*
*线段树是一个二叉树,树上每个节点表示一段区间,每个节点的左右儿子分别是该节点表示的区间从中间断开后分成的左区间和右区间.
*每个区间记录一个当前子树的最小/最大值Top[i].
*查询[a,b]区间的话也很简单,对于当前节点i,如果[a,b]能够完全覆盖i表示的区间,则直接返回Top[i],否则判断与左右区间是否有交
*递归进入访问,取两者之间的最大值即可.
*
*(假设这里维护的是最大值)
*类: IntervalTree
*成员函数:
*		IntervalTree(int size);		构造一颗维护区间[1..size]的线段树
*		Int Query(int a, int b);	查询[a..b]区间内的最大值
*		复杂度:	O(logN)
*		void Modify(int a, int d);	把第a个元素的值改成d
*		复杂度:	O(logN)
*
*/

#define TREE_SIZE (i<<(20))
class IntervalTree{
private:
	int Cover[TREE_SIZE], Top[TREE_SIZE];
	int size;
	int _Query(int a, int b, int l, int r, int Ind) {
	if (a <= l && b >= r) return Top[Ind];
	int mid = (l+r) >> 1, ret = Cover[Ind];
	if (a <= mid) ret = max(ret, _Query(a, b, l, mid, Ind << 1));
	if (b > mid) ret = max(ret, _Query(a, b, mid+1, r, (Ind << 1)+1));
	return ret;
	}

	void _Modify(int a, int l, int r, int Ind, int d) {
		if (l == r && l == a) {
			Cover[Ind] = Top[Ind] = d;
			return;
		}
		int mid = (l+r) >> 1;
		if (a <= mid) _Modify(a, l, mid, Ind << 1, d);
		else _Modify(a, mid+1, r, (Ind<<1)+1, d);
		Top[Ind] = max(Top[Ind<<1], Top[(Ind<<1)+1]);
	}

public:
	IntervalTree() {
		memset(Cover, 0, sizeof(Cover));
		memset(Top, 0, sizeof(Top));
		size = (TREE_SIZE>>2) - 1;
	}
	IntervalTree(int size):size(size) {
		memset(Cover, 0, sizeof(Cover));
		memset(Top, 0, sizeof(Top));
	}
	int Query(int a, int b) {
		return _Query(a, b, 1, size, 1);
	}
	void Modify(int a, int d) {
		return _Modify(a, 1, size, 1, d);
	}
};