#include using namespace std; typedef long long int ll; typedef long double ld; typedef pair pi; typedef pair pd; typedef vector vi; typedef vector vd; typedef vector vpi; #define repab(i, a, b) for (ll i = (a); i < (b); i++) #define repabs(i, a, b,s) for (ll i = (a); i < (b); i+=(s)) #define rep(i, a) for (ll i = 0; i < (a); i++) #define rrepab(i,a,b) for (ll i = (b)-1; i >= (a); i--) #define rrepabs(i,a,b,s) for (ll i = (b)-1; i >= (a); i-=(s)) #define rrep(i,a) for (ll i = (a)-1; i >= 0; i--) #define iter(a, x) for (auto& a : x) #define repeat(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define GET5(a, b, c, d, e, ...) e #define F_ORC(...) GET5(__VA_ARGS__, repabs, repab, rep) #define F_ORRC(...) GET5(__VA_ARGS__, rrepabs, rrepab, rrep) #define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__) #define FORR(...) F_ORRC(__VA_ARGS__)(__VA_ARGS__) #define v(a) vector> #define minheap(a) priority_queue,vector>,greater> > #define mat(n,m) vector matrix(vi(m),n) #define rloop(n) int n;re(n);rep(i,n) #define array(n) array #define rea(arr,n) int n;re(n);vi arr(n);re(arr); #define mk make_pair #define pb push_back #define fi first #define se second #define lb lower_bound #define ub upper_bound #define sz(x) (int)x.size() #define beg(x) x.begin() #define en(x) x.end() #define all(x) beg(x), en(x) #define resz resize template void ckmin(T &a, T b) { a = min(a, b); } template void ckmax(T &a, T b) { a = max(a, b); } namespace io { #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator _it(_ss);cerr<< "line: "<<__LINE__ <<" "; err(_it, args); cerr< it) {} // TYPE ID (StackOverflow) template struct like_array : is_array{}; template struct like_array> : true_type{}; template struct like_array> : true_type{}; template bool is_like_array(const T& a) { return like_array::value; } // INPUT template void re(T& x) { cin >> x; } template void re(Arg& first, Args&... rest); void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template void re(pair& p); template void re(vector& a); template void re(array& a); template void re(Arg& first, Args&... rest) { re(first); re(rest...); } template void re(pair& p) { re(p.fi,p.se); } template void re(vector& a) { rep(i,sz(a)) re(a[i]); } template void re(array& a) { rep(i,SZ) re(a[i]); } template ostream& operator<<(ostream& os, const array& a); template ostream& operator<<(ostream& os, const vector& a); template ostream& operator<<(ostream& os, const set& a) ; template ostream& operator<<(ostream& os, const multiset& a) ; template ostream& operator<<(ostream& os, const map& a) ; // OUTPUT template ostream& operator<<(ostream& os, const pair& a) { os << '{' << a.fi << ", " << a.se << '}'; return os; } template ostream& printArray(ostream& os, const T& a, int SZ) { os << '{'; rep(i,SZ) { if (i) { os << ", "; if (is_like_array(a[i])) os << " "; } os << a[i]; } os << '}'; return os; } template ostream& operator<<(ostream& os, const array& a) { return printArray(os,a,SZ); } template ostream& operator<<(ostream& os, const vector& a) { return printArray(os,a,sz(a)); } template ostream& operator<<(ostream& os, const set& a) { os << vector(all(a)); return os; } template ostream& operator<<(ostream& os, const multiset& a) { os << vector(all(a)); return os; } template ostream& operator<<(ostream& os, const map& a) { os << vector>(all(a)); return os; } template void pr(const T& x) { cout << x << '\n'; } template void pr(const Arg& first, const Args&... rest) { cout << first << ' '; pr(rest...); } template void err(istream_iterator it, T a, Args... args) { cerr << *it << " = " << a<<" " ; err(++it, args...); } template void pa(vector &a,bool psize=true){ if(psize) cout< vis(n,false); rep(i,n){ if(vis[i]) continue; int p=i; int c=0; do{ vis[p]=true; p=a[p]-1; c++; }while(p!=i); ////error(p,i,c); ans+=c-1; } cout<