#include typedef uint64_t u64; typedef int64_t i64; typedef long double f128; using namespace std; template void scan(T& n){ cin>>n; } void scan(){} template void scan(T& n,Args&... args){ scan(n); scan(args...); } template void scanall(T start,T end){ for(;start!=end;++start){ scan(*start); } } template void print(T n){ cout< void print(T n,Args... args){ print(n); print(args...); } template void println(T n){ print(n); cout< void println(T n,Args... args){ print(n,' '); println(args...); } template void printall(T start,T end){ if(start!=end){ print(*start); for(++start;start!=end;++start){ print(' ',*start); } } cout< void chmax(T& n,T m){ n=max(n,m); } template void chmin(T& n,T m){ n=min(n,m); } template T power(T a,U n){ T res=1; while(n){ res*=(n&1)?a:1; a*=a; n>>=1; } return res; } template void swap_min(T& a,T& b){ if(a>b){ swap(a,b); } } template struct combination{ vector fact; combination(const int Max=3000000):fact(Max+1,1){ for(int i=2;i<=Max;++i){ fact[i]=fact[i-1]*i; } } template T nCk(U n,U k){ if(n