#include #define lint long long int #define rep(i,n) for(int i=0;i=0;i--) #define arep(i,a,n) for(int i=a;i #define F first #define S second #define ALL(data) data.begin(),data.end() using namespace std; templateinline void out(Rast rast){cout<inline void in(Rast& rast){cin>>rast;return;} templateistream& operator >> (istream& is, vector& vec){for(T& x: vec) is >> x;return is;} templatevoid in(First& first, Rest&... rest){cin >> first;in(rest...);return;} templatevoid out(First first, Rest... rest){cout << first<<" ";out(rest...);return;} templateT gcd( T a,T b){if(b==0)return a;return gcd(b,a%b);} templatebool chmax(T1& a,T2 b){if(abool chmin(T1& a,T2 b){if(a>b){a=b;return true;}else{return false;}} templateT lcm(T a, T b){return a * b / gcd(a, b);} static const double pi = 3.141592653589793; lint power(lint N, lint P, lint M){if(P==0) return 1;if(P%2==0){lint t = power(N, P/2, M);return t*t % M;}return N * power(N, P-1, M);} lint MOD=pow(10,9)+7; //lint MOD=998244353; lint inf=pow(2,50); int intinf=pow(2,30); /**/int dirx[]={1,0};int diry[]={0,1};//*///右、下 /**int dirx[]={0,1,0,-1};int diry[]={-1,0,1,0};//*///四方位 /**int dirx[]={-1,0,1,1,1,0,-1,-1};int diry[]={-1,-1,-1,0,1,1,1,0};//*///八方位 class unionfind{ public: vector table; vector wod; void init(int size){ table.resize(size); wod.resize(size); rep(i,size)table[i]=i,wod[i]=i; }; int root(int index){ if(table[index]==index)return index; else{ int hoge=root(table[index]); table[index]=hoge; return hoge; } }; bool same(int x,int y){ return(root(x)==root(y)); }; int marge(int x,int y){ int yroot=root(y); int xroot=root(x); if(xroot==yroot)return 0; table[yroot]=xroot; return 0; } }; int main(){ cin.tie(0);ios::sync_with_stdio(false);cout<