#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,a,n) for (int i=a;i<(int)n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) #define ACCU accumulate #define TWO(x) (1<<(x)) #define TWOL(x) (1ll<<(x)) #define clr(a) memset(a,0,sizeof(a)) #define POSIN(x,y) (0<=(x)&&(x) VI; typedef vector VS; typedef vector VD; typedef long long ll; typedef long double LD; typedef pair PII; typedef pair PLL; typedef vector VL; typedef vector VPII; typedef complex CD; const int inf=0x20202020; const ll mod=1000000007; const double eps=1e-9; const double pi=3.1415926535897932384626; const int DX[]={1,0,-1,0},DY[]={0,1,0,-1}; ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head int n,k; bool check(int sm,int c,int k) { // check withiout c choose k number with sum=sm if (c==k+1) { return (sm==k*(k+1)/2||sm>=k*(k+1)/2+2); } else if (c>k+1) { return (sm>=k*(k+1)/2); } else if (c<=k) { return (sm>=(k+1)*(k+2)/2-c); } } bool check(int n,int k) { for (int i=1;i*i