jacky860226

inline long long mod_mul(long long a,long long b,long long m){
	a%=m,b%=m;
	long long y=(long long)((double)a*b/m+0.5);/* fast for m < 2^58 */
	long long r=(a*b-y*m)%m;
	return r<0?r+m:r;
}
template<typename T>
inline T pow(T a,T b,T mod){//a^b%mod
	T ans=1;
	for(;b;a=mod_mul(a,a,mod),b>>=1)

jacky860226

//線性同餘方法 
//這個方法數字很好記 
unsigned random1(){
	static unsigned x=20150118;
	return x=x*0xdefaced+1;
}
int random2(){
	static unsigned x=time(0);
	return x=x*16807;//7^5
}

jacky860226

#include<bits/stdc++.h>
using namespace std;
struct P{
	P(int q,int w,int e,int r):a(q),b(w),x(e),y(r){}
	int a,b;
	int x,y;
};
char s[105][105];
int id[105][105],cnt;
int st[10005];

jacky860226

/*需要再node裡面增加tag跟ma用來儲存區間增加量跟最大值*/
int ask(node *&o,int l,int r){
	/*在o子樹詢問區間[l,r]的最大值*/
	node *a,*b,*c;
	split(o,a,b,l-1);
	split(b,b,c,r-l+1);
	b->down();/*記得要先將懶惰標記下推*/
	int ans=b->ma;
	o=merge(a,merge(b,c));
	return ans;

jacky860226

#ifndef RANDOMIZED_BINARY_SEARCH_TREE
#define RANDOMIZED_BINARY_SEARCH_TREE
template<typename T>
class random_bst{
	private:
		struct node{
			T data;
			unsigned size;
			node *ch[2];
			node(const T &d):data(d),size(1){ch[0]=ch[1]=0;}

jacky860226

#ifndef ARNE_ANDERSSON_TREE
#define ARNE_ANDERSSON_TREE
template<typename T>
class aa_tree{
	private:
		struct node{
			node *ch[2];
			int s,level;
			T data;
			node(const T&d):s(1),level(1),data(d){}

jacky860226

// 0 => black , 1 => red
//#define USE_234_TREE
#ifndef LEFT_LEANING_RB_TREE
#define LEFT_LEANING_RB_TREE
template<typename T>
class ll_rb_tree{
	private:
		struct node{
			node *l,*r;
			bool color;

jacky860226

/* 0 => black , 1 => red */
#ifndef SYMMETRIC_BINARY_B_TREE
#define SYMMETRIC_BINARY_B_TREE
template<typename T>
class rb_tree{
	private:
		struct node{
			node *ch[2],*pa;
			int s;
			bool c;

jacky860226

#ifndef SIZE_BALANCED_TREE
#define SIZE_BALANCED_TREE
template<typename T>
class sb_tree{
	private:
		struct node{
			node *ch[2];
			int s;
			T data;
			node(const T&d):s(1),data(d){}

jacky860226

/* l不能為nil */ 
node *merge(node *l,node *r){
	splay(l,l->s);
	l->ch[1]=r;
	l->up();
	return l;
}

/* k必須 > 0 */
void split(node *o,node *&l,node *&r,int k){