#include "bits/stdc++.h" #define REP(i,num) for(int i=0;i<(num);++i) #define LOOP(i) while(i--) #define ALL(c) c.begin(),c.end() #define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<& lhs,const pair& rhs){return lhs.c comp rhs.c;} using namespace std; using ll = long long; constexpr ll atcoder_mod = 1e9+7; template T in(){T x; cin >> x; return (x);} template> C vecin(int N){C x(N);REP(i,N){x[i]=in();}return move(x);} void vout(){cout << endl;} template void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward(t)...);} void out(){cout << endl;} template void out(Head&& h,Tail&&... t){cout << h;vout(forward(t)...);} ll gcd(ll a,ll b){ if(a