#include using namespace std; using namespace chrono; #if __has_include() #include using namespace atcoder; #endif using ll = long long; using ull = unsigned long long; using vi = vector; using vl = vector; using vb = vector; using vd = vector; using vs = vector; using vvi = vector>; using vvl = vector>; #define ALL(x) (x).begin(), (x).end() #define coutY cout << "Yes" << endl; #define coutN cout << "No" << endl; #define arrIn(arr, start, N) for (ll i = (start); i < (N); ++i) cin >> arr[i]; #define arrOut(arr, start, N) for (ll i = (start); i < (N); ++i) { cout << arr[i]; if(i==(N)-1) cout << endl; else cout << " "; } #define UNIQUE(A) sort(ALL(A)); A.erase(unique(ALL(A)),A.end()); const int mod9 = 998244353; const int mod1 = 1000000007; const int intM=numeric_limits::max(); const ll llM=numeric_limits::max(); string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; string abc="abcdefghijklmnopqrstuvwxyz"; vi dx={0,1,0,-1}; vi dy={-1,0,1,0}; vi ddx={-1,0,1,-1,1,-1,0,1}; vi ddy={-1,-1,-1,0,0,1,1,1}; void yn(bool tf) { cout << (tf ? "Yes" : "No") << endl; } void YN(bool tf) { cout << (tf ? "YES" : "NO") << endl; } template using priority_queueR = priority_queue, greater>; //cout << fixed << setprecision(20) << void arrOut2(auto A){ for(auto x:A){ for(auto y:x){ cout << y << " "; } cout << endl; } } bool kaibun(string S){ string T=S; reverse(ALL(S)); return S==T; } int ketawa(int x){ string S=to_string(x); int sum=0; int len=S.size(); for(int i=0;in)return 0; ll bunshi=1; for(ll i=1;i<=n;i++)bunshi=(bunshi*i)%m; ll bunbo=1; for(ll i=1;i<=r;i++)bunbo=(bunbo*i)%m; for(ll i=1;i<=n-r;i++)bunbo=(bunbo*i)%m; return (bunshi*Power(bunbo,m-2,m))%m; } vector> BFS(int H,int W,vector S,int sh,int sw){ vector> visited(H,vector (W,intM)); queue> q; visited[sh][sw]=0; q.push({0,sh,sw}); while(!q.empty()){ auto [w,nowH,nowW]=q.front(); q.pop(); for(int i=0;i<4;i++){ int nextH=nowH+dy[i]; int nextW=nowW+dx[i]; if(0<=nextH&&nextH> BFS2(int H,int W,vector h,vector v,int sh,int sw){ vector> visited(H,vector (W,intM)); queue> q; visited[sh][sw]=0; q.push({0,sh,sw}); while(!q.empty()){ auto [w,nowH,nowW]=q.front(); q.pop(); for(int i=0;i<4;i++){ int nextH=nowH+dy[i]; int nextW=nowW+dx[i]; if(0<=nextH&&nextH Dijkstra(int N,vector>> edge,int s){ vector visited(N+1,llM); priority_queue, vector>, greater>> q; visited[s]=0LL; q.push({0LL,s}); while(!q.empty()){ auto [w,now]=q.top(); q.pop(); for(pair nextEdge:edge[now]){ int next=nextEdge.second; int nextW=w+nextEdge.first; if(visited[next]>nextW){ visited[next]=nextW; q.push({nextW,next}); } } } return visited; } template vector Imos(U N,U M,vector L,vector R,vector W){ vector A(N+2,0); for(int i=0;i vector> Imos2(U N,U M,U K,vector r1,vector c1,vector r2,vector c2,vector W){ vector> A(N+2,vector (M+2,0)); for(int i=0;i vector PrefixSum(U N,vector A){ vector ruiseki(N+1,0); for(int i=1;i<=N;i++){ ruiseki[i]=ruiseki[i-1]+A[i]; } return ruiseki; } template vector> PrefixSum2(U N,U M,vector> A){ vector> ruiseki(N+1,vector (M+1,0)); for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ ruiseki[i][j]=A[i][j]; } } for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ ruiseki[i][j]+=ruiseki[i-1][j]; } } for(int i=1;i<=N;i++){ for(int j=1;j<=M;j++){ ruiseki[i][j]+=ruiseki[i][j-1]; } } return ruiseki; } random_device rd; mt19937 gen(rd()); uniform_int_distribution<> dist(0,2000000000); int rnd(int MIN,int MAX){ return MIN+dist(gen)%(MAX-MIN+1); } // auto start = high_resolution_clock::now(); // ll getTime(){ // auto end = high_resolution_clock::now(); // return duration_cast(end - start).count(); // } // bool CheckTime(auto limit,auto eps){ // return getTime()> N; cout << N*N << endl; return 0; }