/*::::::::::::::::::::::'``         `````:'`':;;;:':;|>>>||||>>>+;;:::;;:;||>;:+|<;;<|||<!;;:,``       `'``'''''''''''''''''-
------------------------`        ``````'''-''--!!---!|||||!!!!!-;;![|!------!|!---|---!|||!---'``````   `'```'''''''''''''''-
:::::::::::::::::::::'``     ````'```'``:::;:;>|;:>[>;;;;;;>;;>|%%%|>!%%]+;:;<||<;|%<;:;<![<<!;:'``      ``````''''''''''''':
:::::::::::::::`                  ``':;;;;;;;;![|||!!->|;|$%%%%|>|>;>|+;<||<;;;<%%<;!!!;:;!]|||<:'`       ````````'''''''''':
::::::::::'`                ````````'::;;;;:;<;:;;;;!!!!!!]>>!!||%%!!;!%|;;!|!;;!%%!;;||;;!!||!|!:,``       ````````''''''''-
-------'                  ````''`'-----!--!!!!!%%%%%%&&@##@@&&&$$$$$$%|!!!!!|%|---!!---||!-!|||!!|!'```       ```````'''''''-
----`          `         ``''''-----;;;;;!]%&##########@#########@@&$$$$%%%%>||!;::;!!!!||;;!!|!:;;:::,`       ````````'''''-
-'`                      ````` `---!!!!%&@##@####@@##@@@@@@@@@@@@@&&&&$$%%|||!!||----%!-;!;::!!![!----'``       `````'''''''-
`      ``  `   `      `````''---'-!|$&@###@@@##@@@@@@@@@&&&@@@&&&$$$%||%%|||||--!!---||--!!--!!-!!-----'``      ``````''''''-
         `` ````      `````''----!$@#####@@@###@@@@&&&&&$$$$$$$%%|!||%%||%|!!||!------||!--!-:>>;!!;::'`````    ````````````:
    `  ``  ``       ```````''':;%@@#####@@@@@@@@@&&$$%[|>|||||%||||>::::>>!]+;<<<;;;:::|%;;<!;;!;;;;::'````      ````````''':
  `` ``  ``         `'``'':::;%&@@@####@@@@@@@@&&$%[||<;;;;;<!;!!!!!;:''`':;![!-;>;;;;;>%>::>+:;;;<;:;<;'`````      ````````:
 `` `` ``` ```  `` ````'':;<$@@@@@####@@@@@@@@&$$|<!]|<;:::::;;::;<!;;:'````':!!;;;;;::;!!!;;;;:;!;;::::'''````   ``````````:
`` `` ```          ```'''`;&@@@@@@@@@@@@@@@@@@&$]|>>!!;:::,''--'''------'``````--!;;;;:';]|;:>|;:>!;:':::::`        ````````:
 ``` `` ``     `````````;$#@@@@@@@@@@@@@@@@@@&$$[!!-;<+;::''':''''':;;;:''``````':>!:;;::;!;:;!;:;!!;:::;:'````      ```````:
`````` ``      ``````':]%$@@@@@@@@@@@@@@@@@@@&&$|<;;;;!;::'''''````'':;;:''```````';!;;;::;;![>;::;>;;:::'`       ``````````'
` ``` `       ``'::':>$#@@@@@@@@@@@@@@@@@@&@@&&$|>;;;;>!;:::'''``````'';;::'```````:!!;:::;!;:;!::;!;;'''````      `````````:
```````       ``'``:;$#@&@@@@@@@@@@@@@@@&&&@&&&$%!;;;;!!;;:''''```````''';;::'``````'![-:::;;::;;::<;;:'``'``      `````````'
 ``      ```` ````'+@#@@@@@@@@@@@@@@@@@@@&&&&&&$%>;;;;!!;;:''''````````''':;:::``````'!]<::::::;;;;;;;;:;:```` `      ``````'
``     ``'```` ```'%@@@@@###@@@@@@&&@&@@&&&&&&&$%]<;;;<<;::'''`````````''``'::':;::':;;||<;;:':;;;:;;;;:;;:``````    ```````'
````   ``::'::::':!%$%$@####@@@@@@&&&@&@@@@&&&&&%%[<;;||<;:'''`'::;<<;;:'''''::'';!!!!]|%%>;;:':;>;;;:;;::'````    ` ```````:
``    ` `  ':;>>:[############@@@@&&&@@@@&&&&&&&$%|<!![|!-<+|||%||>!]|>>;:''`''':;>>>;:''!%;;;:::;::;;::'::'``       ```````'
      `````'::;$##############@#@@@&@@@@@&&&&&&&&$%]<|%%%|||<<<!;;;;;;;;::'`````':::''```'![;;;:;;::<;:;;;;'`````    ```````'
  ````';``':;;%@###############@@@@@@@@@@&&&&$$$&&$$%$$|;'````````'''::::''``````'''''````;%<;::;;;::;':;<;'''`     ````````'
`````''`::::;%@##################@@@@@&&@&$&&&$$&&&$%|;'`````````````''''''```````'''';<]>|$%>;:;;:':;::;>>;'`````    ``````'
':::'':::::;!&@@####&[<$#######@@@@@@&&&&&$$&&$$&&&$|<:''``````';!;;;:'''''```````'':!$@#@&&&%!;;;;::;;:;!:':'````      ````'
':::::!;'':!$%%&&&&$&#&&########@@@@@&&$&$$$$&$$$$&&%!;:'''':![|%&@@&%-''``````  ``'[&$!-%&&&%!;;;::!!:;!;;;:'``` ``    ````'
':;!;::::;![&#&&#$%@@&@##########@@@&&$$&$$$$$$$$$$&%!-:::![|$@@&$|!!%%-```````   `'[&$|!-[$&$|!-::::;;;:';!;:'```     `````'
''::;;:;;;%#@$%!!!!![%&##########@@&&$$$$&$%$$$$$$$&$|-;![$&&$&@@@@%!!!!-```````    ``''''``;$$[!-':;:::':;::''```     `````'
''::;:::;!!$#&$$!'':$##&%&######@@@&$$%%%%$$%$$$$$%$$[!!%$$%|!-::'````````````````     ```````[%||;;;::::::'``````     `````'
'`'::;;;|%%&@@#@$||%|>|%%@######@@@&$%%|||%$$$$$$%%$%+:''''''':::::::'`````````````           `:|<-;;;;;;:'''''``   ````````'
':::::;;%%%@####$$#&&##########@@@&$$%]|||||%%$$$%%%%>'```````````````       ````````          `-|!--------'```   ``````````'
:;:::::>%%&#####@%&@@##########@@&&$%%||||>>||%$$%%%%+'`````````             ``````````         `;|;'::::::'``    ``````````:
;:::::<%&@########%%##########@@@&&$%%|||<<<!]|%%%%%%>'`````````             ```````````````     '|+:''':''`````````````````:
':::;;<&@@###################@@@&&&$$%]||>+<!!]|%%%%|;'```````````          ``````````''''''``   `>|:':;;:'```   ```` ``````:
'::::+$@@@$|<;;;!%&######@@@@@@&&$$$$%]||>+<!!!]|%%%|;''```````````        ```'''''':>%|+;;:'````'<];:'''''```      ````````:
::::;|@@&%>|||%%$$%%$&@@&&&&@@&&&$$$$%||+<!!!!!]|%%%|;:'''````````````````````'::::|$%>+<;:''````'!]>;:'``````    ``````````:
::;;;%@@$|+<!;;]%$$%%%%%$$$$$$$&&$$$$%||>+<!!!!]|%%%|;::''''```````````````````':;;:''':::````'``'|%|;::'``````  ```````````:
::::|&@@$>;!!;:;![|%$%|%%%%%%%%%$$$$$%%||!!!!!!||%%%|-;:::'''''``````````````````````````````````:||%;'`````````````````````:
:::<$@@&&|;+>;::;!]$&$%|%%%%%%%%%$$$$%%|||>>>>>]|%%|<<;:::::'''''''''''''``````````````````  ````;%[||;''```````````````````:
:::>&@@@@%;;>+;:;<|%%%%%$%+<|||||%$$$%%%|||!!!!||%%|!!-;::::::::'''''''''''````````````''''''```'!$]>!!:```    `````````````:
:;!%&@@&#@%;!!!;;!!!!![%$%|-;<||||%$$$%%|||+>!!]|%||><;;:::::::::::::'''''''''''''':;;<||||||;:`'|$%<;;'`    ```````````````'
':<$@@&&@##$!;!!;;!;;![|%$$%<;<||||%$%%%||||<<!!]|>>>;;;::::::::::::::'''':;;;;>![|>>;'````:>:'`:%$$|>!;```   ``````````````'
:;]&@@&&@@##@|;<<;;<<<<|||%$%<;<[||%%%%%||||>>++++++;;;;::::::::::::''''':+%$$$|;;:'''`````''```;$&$%+;;'```````````````````'
:+$&@@&@@@@###&|;+++;;+;::;;::;+|||%%%%%|||||+++++;;;;;;:::::::::::'''''''';|&&|+||;:::'````` ``;&&$%+:'````````````````````'
;%$&@@&@@@@@@@##@|;;;;;;::::::;;+||%%%%%%%|||||+++;;;;;;:::::::::''''''''````'''''::::::'''''```;$&&$|:'````````````````````'
;|$&@@@@@@@@@@@####&|+;;::::::::;+|%%%%%%%%||||+++++;;;;:::::::::'''''''`````````''''::;;;;:'`` ;$&$$|:'````````````````````'
|$&&&@@@@@@@@@@@######@$++;::::;|&&$$%%%%%%%%||||++++;;;;;::::::::'''''''``````````````''`````  :$$&$|;'````````````````````'
%$&&&@#@@@&@@@@@@@@#######&%||%&&&@@&$$%%%%%%%%||||++++;;;;:::::::'''''''''````````````````     `+$$$%|:'``        `''`     '
%$&&@@#@@&&&@@@@@@@@########@@&&$&&&&&&$$$%%%%%%%||||++++;;;;::::::::'''''''`````````````        '|$%%|;:`` ````` `'+!;;::.':
$&@@@@@#@@&&@@@@@@@#@#######@&&$$$$$$$&&$$$$%%%%%%%||||<<<<;;;;;:::::::'''''''````````````````` ``;%%%%<:` ```    `:<!;;!]|!!
&&&@@@@@#@&&&@@@@@@#@@#######@&$$%%%%%$$$$$$$$$$%%%%%|||||!!!!;;;;;;::::::''''''''````````````````;$%%$%!!;;;;;:'';|%|:``;||!
$&@@@@@#@@@&&@@@@@@##@@@#####@&$$%%|||%%%$$$$$$$$$%%%%%%||||||!!!!!;;;;;;;::::::::''''''''''''''`;%$$%$%|%$$%|||%%%|!!;'``:||
&&@@@@&@@@@&$@@@@@@@##@@@#####@&$%%||||||%%%$$$$$$$%%%%%%%%%%%||||||!!!!!!!;;;;;;;;;;:::::::::::!$$$$$$|;|$%%|||$$%|!;;:'``;!
&&@@@@@@@@@@$&@@@@@@@##@@#####@@&$%|||!!!|||%%%%%%%%%%%%%%%%%%%%%%%%%%|||||||||!!!!!!!!!!!!;;!%$$$$$$$%|;!$%%|||%$$%||!;:``:!
&@@@@@@@@@@&$$&@&@#@@###@@#####@@$%||!!!!!!!!|||||%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%$$$&&@@@@&&$$&$$%$%||!!$$$%||||!;;;;::'`'!
&@&@@&@@&&@&$$&@&&@#@@###@@#####@&$%||!!!!!!!!!!!!|||||||||||||%%%%%%%%%%%||||&##########@@@&$$$&&$%%||!!!%%||!!!;;:::::'''':
@@&&&&@@@&&&&$$&@&&@@@####@@#####@&$%|!!;;;;;;;;;;!!!!!!||||||||||||||||!!!!|&##########@&@@&$%$&&$%|!!;;;;;;!!!!!;;;;;:::'':
@@&@@&&@&&$&&$$&@&&&@@@####@@@@@@@@&$%|!!;;;;;;;;;;;;;;;!!!!!!!!!!!!!!;;;;;;$###########@&@@&%$$&&$%|;::;;;;;;;!!!;;;;;;;::':
@@@@&&&&@&$$$$$&@&&&@&&@####@@@@@@@&$%|!!;;;;:::::::;;;;;;;;;;;;;;;;;;;;;;;|@##########@&&&&$%%$$$$$|;':;::::;;!!;;;;;;;;;;;;
&&@@&&&&&&&$$$$&@@&&&@&@#####@@&&&@@&$%|!!;;;::::::::::::::;;;;;;;:;::::::;$###########@$%$&$%$$$$$%|;````:::::::::::::''''':
&&@@&&&&&&$$$$$&@@&&&&&&######@&&&&&&$%|!!;;;:::::::::::::::::::::::::::::|@#########@@&%;!&$%$$$$$$|;'`````'':::''::::''''':
Coded by Natsu Kinmoe, a 21-yr-old beautiful girl.
*/
#include <bits/stdc++.h>
using namespace std;
#define loop(i,n) for(int i=0;i<(n);i++)
#define pool(i,n) for(int i=(n)-1;i>=0;i--)
#define cont(i,n) for(int i=1;i<=(n);i++)
#define tnoc(i,n) for(int i=(n);i>=1;i--)
#define circ(i,a,b) for(int i=(a);i<=(b);i++)
#define cric(i,a,b) for(int i=(b);i>=(a);i--)
#define sub(i,a) for(int i=a;i;i=((i-1)&(a)))
#define subs(i,a) for(int i=a;i>=0;i=(!i?-1:((i-1)&(a))))
#define subt(i,a) for(int i=((a-1)&a);i;i=((i-1)&(a)))
#define subst(i,a) for(int i=((a-1)&a);i>=0;i=(!i?-1:((i-1)&(a))))
#define range(i,a,b,c) for(int i=(a);((c)>0?i<=(b):i>=(b));i+=(c))
#define foreach(it,v) for(__typeof((v).begin()) it=(v).begin(),_e_D_=(v).end();it!=_e_D_;it++)
#define parse(i,s) for(int i=0;s[i];i++)
#define ln '\n'
#define all(a) a.begin(),a.end()
#define OVER(s) return puts(s),0;
#define FILL(a,x) memset(a,x,sizeof(a))
#define FILL0(a) memset(a,0,sizeof(a))
#define FILL1(a) memset(a,-1,sizeof(a))
#define FILLBIG(a) memset(a,0x3f,sizeof(a))
#define COPY(frm,to) memcpy(to,frm,sizeof(frm))
#define Mask(a) (1ll<<(a))
#define Maskx(a,x) ((a)<<(x))
#define Full(a) ((1ll<<(a))-1)
#define Bit(a,x) (((a)>>(x))&1)
#define SZ(a) ((int)((a).size()))
#define filei(a) freopen(a,"r",stdin);
#define fileo(a) freopen(a,"w",stdout);
#define fileio(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define Floyd(a,n) cont(k,n)cont(i,n)cont(j,n)chmin(a[i][j],a[i][k]+a[k][j])
#define Floyd0(a,n) loop(k,n)loop(i,n)loop(j,n)chmin(a[i][j],a[i][k]+a[k][j])
#define Floydlr(a,l,r) circ(k,l,r)circ(i,l,r)circ(j,l,r)chmin(a[i][j],a[i][k]+a[k][j])
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define y0 y0O0OO00OO0OO0OO0OOO00OO0OO0O0O000OO0
#define y1 y1II11II11III11I1III11II111IIII1II1I1
#define ws WSrAkIoi2333wSraKIoIWSraKiOi
#define left left_jTjTJtJtIoiiOiioIAuaU66666jtIOIau
#define hash whYusEthiSnamE_caNyoUusEothERnaMesliKeHSH
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mak make_pair
#define emb emplace_back
#define emf emplace_front
#define emp emplace
#define popcnt __builtin_popcount
#define Popcnt __builtin_popcountll
template<typename _T>
using pair2=pair<_T,_T>;
template<typename _T>
using pair3=pair<pair<_T,_T>,_T>;
template<typename _T>
using pair4=pair<pair<_T,_T>,pair<_T,_T> >;
#define mak3(a,b,c) make_pair(make_pair(a,b),c)
#define mak4(a,b,c,d) make_pair(make_pair(a,b),make_pair(c,d))
template<typename _T>
using priq=priority_queue<_T>;
template<typename _T>
using qrip=priority_queue<_T,vector<_T>,greater<_T> >;
#define ST first
#define ND second
#define FST first.first
#define SND first.second
#define RD second
#define SRD second.first
#define FTH second.second
#ifndef JTAKIOI
#define cerr if(0)cout
#define tctest(clas,meth,...)
#else
#define tctest(clas,meth,...) int main(){fio<<(new clas)->meth(__VA_ARGS__)<<ln;}
#endif
typedef long long ll;
typedef long double lf;
typedef istringstream iss;
typedef stringstream sst;
const lf pi=acosl(-1);
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3fll;
const lf inF=11451419198101145141919810.1145141919810;
const int Dx[]={1,0,-1,0,1,1,-1,-1},Dy[]={0,1,0,-1,1,-1,1,-1};
unsigned Rand(){return rand()*32768+rand();}
int rand(int a,int b){return Rand()%(b-a+1)+a;}
template<typename _T>
inline _T chmin(_T &a,_T b){return a>b?(a=b):a;}
template<typename _T>
inline _T chmax(_T &a,_T b){return a<b?(a=b):a;}
template<typename _T,int len>
struct BIT{
	_T dt[len];
	inline void add(int a,_T x){while(a<len){dt[a]+=x;a+=a&-a;}}
	inline void add(int l,int r,_T x){add(l,x);add(r+1,-x);}
	inline _T get(int a){_T ans=0;while(a){ans+=dt[a];a-=a&-a;}return ans;}
	inline _T get(int l,int r){return get(r)-get(l-1);}
};
template<typename _T,int len>
struct segbit{
	_T dt[2][len];
	inline void add(int a,_T x){int b=a;while(a<len){dt[0][a]+=x;dt[1][a]+=x*b;a+=a&-a;}}
	inline void add(int l,int r,_T x){add(l,x);add(r+1,-x);}
	inline _T sum(int a){_T ans=0;int b=a;while(a){ans+=(b+1)*dt[0][a]-dt[1][a];a-=a&-a;}return ans;}
	inline _T sum(int l,int r){return sum(r)-sum(l-1);}
};
struct fastIO{
	inline fastIO operator>>(int& num){
		num=0;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();
		bool foo=0;if(c=='-'){foo=1;c=getchar();}
		while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+c-'0';c=getchar();}
		if(foo)num=-num;return *this;
	}
	inline fastIO operator>>(ll& num){
		num=0;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();
		bool foo=0;if(c=='-'){foo=1;c=getchar();}
		while(c>='0'&&c<='9'){num=(num<<3)+(num<<1)+c-'0';c=getchar();}
		if(foo)num=-num;return *this;
	}
	inline fastIO operator>>(float& num){scanf("%f",&num);return *this;}
	inline fastIO operator>>(double& num){scanf("%lf",&num);return *this;}
	inline fastIO operator>>(long double& num){scanf("%Lf",&num);return *this;}
	inline fastIO operator>>(char& num){num=getchar();while(num==' '||num=='\n')num=getchar();return *this;}
	inline fastIO operator>>(char* num){
		int cnt=0;char c=getchar();while(c==' '||c=='\n')c=getchar();
		while(c!=' '&&c!='\n'){num[cnt++]=c;c=getchar();}num[cnt]=0;return *this;
	}
	inline fastIO operator>>(string& num){cin>>num;return *this;}
	inline void printInt(const int& num){if(num<10){putchar(num+'0');return;}printInt(num/10);putchar((num%10)+'0');}
	inline void printll(const ll& num){if(num<10){putchar(num+'0');return;}printll(num/10);putchar((num%10)+'0');}
	inline fastIO operator<<(const int& num){if(num<0)putchar('-'),printInt(-num);else printInt(num);return *this;}
	inline fastIO operator<<(const ll& num){if(num<0)putchar('-'),printll(-num);else printll(num);return *this;}
	inline fastIO operator<<(const float& num){printf("%.10f",num);return *this;}
	inline fastIO operator<<(const double& num){printf("%.16lf",num);return *this;}
	inline fastIO operator<<(const long double& num){printf("%.20Lf",num);return *this;}
	inline fastIO operator<<(const char& num){putchar(num);return *this;}
	inline fastIO operator<<(const char* num){for(int i=0;num[i];i++)putchar(num[i]);return *this;}
	inline fastIO operator<<(const string& num){cout<<num;return *this;}
	template<typename _T> inline fastIO operator<<(const vector<_T> &vec){printf("{ ");foreach(i,vec)operator<<(*i)<<' ';printf("}");return *this;}
}fio;
const lf eps=1e-10;
struct point{
	lf x,y;
	lf ang;
	point(){}
	point(lf x,lf y):x(x),y(y){ang=atan2l(y,x);}
	inline point operator=(const point &pt){x=pt.x;y=pt.y;return *this;}
	inline point operator-()const{return point(-x,-y);}
	inline point operator+(const point &pt)const{return point(x+pt.x,y+pt.y);}
	inline point operator-(const point &pt)const{return point(x-pt.x,y-pt.y);}
	inline point operator*(const lf &a)const{return point(x*a,y*a);}
	inline point operator/(const lf &a)const{return point(x/a,y/a);}
	inline point operator^(const lf &ang)const{return point(x*cosl(ang)-y*sinl(ang),x*sinl(ang)+y*cosl(ang));}
	inline point operator+=(const point &pt){return *this=point(x+pt.x,y+pt.y);}
	inline point operator-=(const point &pt){return *this=point(x-pt.x,y-pt.y);}
	inline point operator*=(const lf &a){return *this=point(x*a,y*a);}
	inline point operator/=(const lf &a){return *this=point(x/a,y/a);}
	inline point operator^=(const lf &ang){return *this=point(x*cosl(ang)-y*sinl(ang),x*sinl(ang)+y*cosl(ang));}
	inline lf operator*(const point &pt)const{return x*pt.x+y*pt.y;}//dot
	inline lf operator%(const point &pt)const{return x*pt.y-y*pt.x;}//det
	inline lf length()const{return x*x+y*y;}
	inline lf size()const{return sqrtl(x*x+y*y);}
	inline lf operator^(const point &pt)const{return acosl(*this*pt)/length()/pt.length();}
	inline lf getangle(){return ang=atan2l(y,x);}
	inline lf angle()const{return atan2l(y,x);}
	inline bool operator<(const point &p)const{return ang<p.ang;}
};
inline bool xsmaller(const point &x,const point &y){return fabs(x.x-y.x)<1e-10?x.y<y.y:x.x<y.x;}
inline bool ysmaller(const point &x,const point &y){return fabs(x.y-y.y)<1e-10?x.x<y.x:x.y<y.y;}
struct line{
	point a,b;
	line(){}
	line(point a,point b):a(a),b(b){}
};
point intersect(line x,line y){
	point p1=x.a,v1=x.b-x.a;
	point p2=y.a,v2=y.b-y.a;
	return p1+v1*(((p2-p1)%v2)/(v1%v2));
}
int jt=1000000007;
inline int &Add(int &a,int b){
	a+=b;
	if(a>jt){a-=jt;}
	if(a<0){a+=jt;}
	return a;
}
inline int &Sub(int &a,int b){
	a-=b;
	if(a>jt){a-=jt;}
	if(a<0){a+=jt;}
	return a;
}
inline int &Mul(int &a,int b){
	a=1ll*a*b%jt;
	if(a<0){a+=jt;}
	return a;
}
inline int Jar(int a){
	return a;
}
template<typename ... tps>
inline int Jar(int a,tps ... args){
	a+=Jar(args ...);
	if(a>jt){a-=jt;}
	if(a<0){a+=jt;}
	return a;
}
inline int Jan(int a,int b){
	a-=b;
	if(a>jt){a-=jt;}
	if(a<0){a+=jt;}
	return a;
}
inline int Churn(int a){
	return a;
}
template<typename ... tps>
inline int Churn(int a,tps ... args){
	a=1ll*a*Churn(args ...)%jt;
	if(a<0){a+=jt;}
	return a;
}
inline int ksmii(int a,int b=jt-2){
	if(b<0){return ksmii(ksmii(a),-b);}
	if(!b){return 1;}
	int x=ksmii(a,b>>1);x=1ll*x*x%jt;
	if(b&1)x=1ll*x*a%jt;return x;
}
template<int len>
struct bitmod{
	int dt[len];
	inline void add(int a,int x){while(a<len){dt[a]=(dt[a]+x)%jt;a+=a&-a;}}
	inline void add(int l,int r,int x){add(l,x%jt);add(r+1,jt-x%jt);}
	inline int get(int a){int ans=0;while(a){ans=(ans+dt[a])%jt;a-=a&-a;}return ans;}
	inline int get(int l,int r){return (get(r)-get(l-1)+jt)%jt;}
};
template<int len>
struct DSU{
	int fa[len],sz[len];
	DSU(){loop(i,len)fa[i]=i,sz[i]=1;}
	void init(){loop(i,len)fa[i]=i,sz[i]=1;}
	int root(int x){return fa[x]==x?x:(fa[x]=root(fa[x]));}
	bool conn(int a,int b){a=root(a);b=root(b);if(a==b)return 0;fa[a]=b;sz[b]+=sz[a];return 1;}
};
template<typename _T>
inline _T qp(_T a,int b){
	if(!b){return 1;}
	_T x=qp(a,b>>1);x=x*x;
	if(b&1){x=x*a;}return x;
}
template<int R,int C=R>
struct matrix{
	int mat[R][C];
	int* operator[](int x){
		return mat[x];
	}
	matrix(){loop(i,R)loop(j,C)mat[i][j]=0;}
	matrix(int x){loop(i,R)loop(j,C)mat[i][j]=(i==j?x:0);}
	matrix<R,C> operator+(const matrix<R,C> m){
		matrix<R,C> ans;
		loop(i,R)loop(j,C)ans.mat[i][j]=(mat[i][j]+m.mat[i][j])%jt;
		return ans;
	}
	template<int D>
	matrix<R,D> operator*(const matrix<C,D> m){
		matrix<R,D> ans;
		loop(i,R)loop(j,C)loop(k,D)ans.mat[i][k]=(ans.mat[i][k]+((ll)mat[i][j])*m.mat[j][k])%jt;
		return ans;
	}
	matrix<R,C> operator+=(const matrix<R,C> m){
		matrix<R,C> ans;
		loop(i,R)loop(j,C)ans.mat[i][j]=(mat[i][j]+m.mat[i][j])%jt;
		return ans;
	}
	matrix<R,C> operator-=(const matrix<R,C> m){
		matrix<R,C> ans;
		loop(i,R)loop(j,C)ans.mat[i][j]=(mat[i][j]-m.mat[i][j]+jt)%jt;
		return ans;
	}
	void debug(){
		loop(i,R){loop(j,C)cerr<<mat[i][j]<<' ';cerr<<endl;}cerr<<endl;
	}
};

int dp[305][305][305];
int n,m;
vector<pair<int,int> > lms[305];

int main(){
	fio>>n>>m;
	loop(i,m){
		int l,r,x;fio>>l>>r>>x;
		lms[r].pub(mak(l,x));
	}
	dp[1][0][0]=3;int ans=0;
	cont(i,n)loop(j,i)circ(k,j,i-1){
		foreach(f,lms[i]){
			if(f->second==1&&k>=f->first)dp[i][j][k]=0;
			if(f->second==2&&(j>=f->first||k<f->first))dp[i][j][k]=0;
			if(f->second==3&&j<f->first)dp[i][j][k]=0;
		}
		if(i==n)Add(ans,dp[i][j][k]);
		Add(dp[i+1][j][k],dp[i][j][k]);
		Add(dp[i+1][j][i],dp[i][j][k]);
		Add(dp[i+1][k][i],dp[i][j][k]);
	}
	fio<<ans<<ln;
	return 0;
}

Measured memory_bytes: 58648