#include #define fr(i,n) for(int i=0;i<(n);++i) #define foor(i,a,b) for(int i=(a);i<=(b);++i) #define rf(i,n) for(int i=(n);i--;) #define roof(i,b,a) for(int i=(b);i>=(a);--i) #define elsif else if #define all(x) x.begin(),x.end() #define Sort(x) sort(all(x)) #define Reverse(x) reverse(all(x)) #define PQ priority_queue #define NP(x) next_permutation(all(x)) #define M_PI 3.14159265358979323846 using namespace std; typedef vector vb; typedef vector vvb; typedef vector vi; typedef vector vvi; typedef long long ll; typedef vector< ll> vl; typedef vector vvl; typedef unsigned long long ull; typedef vector vu; typedef vector vvu; typedef double dbl; typedef vector vd; typedef vector vvd; typedef string str; typedef vector vs; typedef vector vvs; typedef pairpii; typedef vectorvpii; typedef mapmii; typedef pair< ll, ll>pll; typedef vectorvpll; typedef map< ll, ll>mll; typedef pairpdd; typedef vectorvpdd; typedef mapmdd; typedef pairpss; typedef vectorvpss; typedef mapmss; typedef pairpil; typedef vectorvpil; typedef mapmil; typedef pair< ll,int>pli; typedef vectorvpli; typedef map< ll,int>mli; typedef pairpdi; typedef vectorvpdi; typedef mapmdi; templatevector&operator<<(vector&v,const T t){v.push_back(t);return v;} templatemultiset&operator<<(multiset&m,const T t){m.insert(t);return m;} templateset&operator<<(set&s,const T t){s.insert(t);return s;} templatestack&operator<<(stack&s,const T t){s.push(t);return s;} templatequeue&operator<<(queue&q,const T t){q.push(t);return q;} templatePQ,U>&operator<<(PQ,U>&q,const T t){q.push(t);return q;} templateistream&operator>>(istream&s,pair&p){return s>>p.first>>p.second;} templateistream&operator>>(istream&s,vector&v){fr(i,v.size()){s>>v[i];}return s;} templateostream&operator<<(ostream&s,const pairp){return s<ostream&operator<<(ostream&s,const vectorv){for(auto a:v){s<ostream&operator<<(ostream&s,const vectorv){fr(i,v.size()){i?s<<" "<pairoperator+(paira,pairb){return {a.first+b.first,a.second+b.second};} templatepairoperator-(paira,pairb){return {a.first-b.first,a.second-b.second};} void print(void){cout<void print(T t){cout<void print(T&&t,U&&...u){cout<(u)...);} void YN(bool b){print(b?"YES":"NO");}void PI(bool b){print(b?"POSSIBLE":"IMPOSSIBLE");} void Yn(bool b){print(b?"Yes":"No");}void Pi(bool b){print(b?"Possible":"Impossible");} void yn(bool b){print(b?"yes":"no");}void pi(bool b){print(b?"possible":"impossible");} const int MD=1e9+7; templatestr to_string(const T&n){ostringstream s;s<vector>dijkstra(const vector>>E,const U s,const T inf){using P=pair;vector

d;fr(i,E.size()){d<,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstmap>dijkstra(map>>E,const U s,const T inf){using P=pair;mapd;for(pair>e:E){d[e.first]=P{inf,e.first};}PQ,greater

>pq;pq<<(d[s]=P{0,s});while(pq.size()){P a=pq.top();pq.pop();U v=a.second;if(d[v].first>=a.first){for(P e:E[v]){if(d[v].first+e.firstT distsq(paira,pairb){return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);} templateT max(const vectora){T m=a[0];for(T e:a){m=max(m,e);}return m;} templateT min(const vectora){T m=a[0];for(T e:a){m=min(m,e);}return m;} templateT gcd(const T a,const T b){return a?gcd(b%a,a):b;} templateT gcd(const vectora){T g=a[0];for(T e:a){g=gcd(g,e);}return g;} templatevectorLIS(const vectorA){vi B;for(T a:A){auto it=lower_bound(all(B),a);if(it==B.end()){B<vector>ConvexHull(vector>V){if(V.size()<=3){return V;}Sort(V);rf(i,V.size()-1)V<>r;for(pairp:V){int s=r.size();while(s>=2&&(p.second-r[s-1].second)*(p.first-r[s-2].first)<(p.second-r[s-2].second)*(p.first-r[s-1].first)){r.pop_back();--s;}r<r[b=find(b)]){swap(a,b);}s[b]+=s[a];r[p[a]=b]+=r[a]==r[b];}bool same(int a,int b){return find(a)==find(b);}int size(int x){return s[find(x)];}}; ll strmod(const str&s,const int m){ll x=0;fr(i,s.size()){x=(x*10+s[i]-48)%m;}return x;} vvl mul(const vvl&A,const vvl&B,const int m){vvl C;fr(y,A.size()){C<=0?a%m:(m-(-a%m))%m:1)*(t=pow(a,n>>1,m),t*t%m)%m:!!a;} ll inv(const ll x,const int p){return pow(x,p-2,p);} vpll fact(const int n,const int p){vpll v(n+1);v[0].first=1;foor(i,1,n){v[i].first=v[i-1].first*i%p;}v[n].second=inv(v[n].first,p);roof(i,n,1){v[i-1].second=v[i].second*i%p;}return v;} ll C2(const int n){return(ll)n*~-n/2;} ll sum(const vi a){ll s=0;for(int e:a){s+=e;}return s;} ll sum(const vl a){ll s=0;for(ll e:a){s+=e;}return s;} ll segsum(vl&s,int l,int r){l|=s.size()>>1;r|=s.size()>>1;if(l>r){return 0;}if(l==r){return s[l];}ll z=s[l]+s[r];for(;l>>1>1;l>>=1,r>>=1){l&1||(z+=s[l^1]);r&1&&(z+=s[r^1]);}return z;} void segadd(vl&s,int i,ll x){s[i|=s.size()>>1]+=x;for(;i>>1>=1;i>>=1){s[i>>1]=s[i]+s[i^1];}} ll BITsum(vl&B,int i){ll z=0;while(i>0){z+=B[i];i-=i&-i;}return z;} void BITadd(vl&B,int i,ll x){while(i>i&1){a=A;b=B;c=C;d=D;A=a+b;B=a;C=c+d;D=c;}a=A%m;b=B%m;c=C%m;d=D%m;}return b;} vi primes(int n){vb b(n+1);vi p;foor(i,2,n){if(!b[i]){p<>H>>W; vs s(H);cin>>s; vectorm(H,vvi(W,vi(2,int(1e9)))); queue>q; int gy,gx; fr(y,H)fr(x,W){ if(s[y][x]=='S'){ q.push({{y,x},0}); m[y][x][0]=0; }elsif(s[y][x]=='G'){ gy=y; gx=x; } } while(q.size()){ auto v=q.front();q.pop(); int y=v.first.first,x=v.first.second; int c=m[y][x][v.second]; for(pii p:v.second?vpii{{-1,-1},{-1,1},{1,-1},{1,1}}:vpii{{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}){ int Y=y+p.first; int X=x+p.second; if(0<=Y&&Y