include <bits/stdc++.h>

define ll long long

define endl '\n'

define f0(i,n) for(int i=0;i<n;++i)

define f1(i,n) for(int i=1;i<=n;++i)

define fo(i,l,r) for(int i=l;i<=r;++i)

define fi first

define se second

define pai pair<int,int>

define lb(v,x) lower_bound(v.begin(),v.end(),x)

define ub(v,x) upper_bound(v.begin(),v.end(),x)

using namespace std; const int MOD=1e9+7; const int N=1e5+5; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){ static uniform_int_distribution<int> d; return d(rng,uniform_int_distribution<int>::param_type(l,r)); }

int main(){ //freopen(".INP","r",stdin); //freopen(".OUT","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); auto start=chrono::steady_clock::now();

auto end=chrono::steady_clock::now();
cerr<<"Time = "<<chrono::duration<double>(end-start).count()<<" s\n";
return 0;

}#include <bits/stdc++.h>

define ll long long

define endl '\n'

define f0(i,n) for(int i=0;i<n;++i)

define f1(i,n) for(int i=1;i<=n;++i)

define fo(i,l,r) for(int i=l;i<=r;++i)

define fi first

define se second

define pai pair<int,int>

define lb(v,x) lower_bound(v.begin(),v.end(),x)

define ub(v,x) upper_bound(v.begin(),v.end(),x)

using namespace std; const int MOD=1e9+7; const int N=1e5+5; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rnd(int l,int r){ static uniform_int_distribution<int> d; return d(rng,uniform_int_distribution<int>::param_type(l,r)); }

int main(){ //freopen(".INP","r",stdin); //freopen(".OUT","w",stdout); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); auto start=chrono::steady_clock::now();

auto end=chrono::steady_clock::now();
cerr<<"Time = "<<chrono::duration<double>(end-start).count()<<" s\n";
return 0;

}