#include using namespace std; typedef long long ll; typedef long double ld; typedef vector vi; typedef vectorvll; typedef vector>vvll; typedef pairpll; typedef pair pii; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; using vi = vc; using vl = vc; using vpi = vc; using vpl = vc; template using pq = priority_queue; template using pqg = priority_queue, greater>; template int si(const T &x) { return x.size(); } #define overload5(a, b, c, d, e, name, ...) name #define overload4(a, b, c, d, name, ...) name #define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__) #define overload2(_1, _2, name, ...) name #define endl "\n" #define sq(x) (long long)sqrt(x) #define REP0(n) for(ll jidlsjf = 0; jidlsjf < n; ++jidlsjf) #define REP1(i, n) for(ll i = 0; i < (n); ++i) #define REP2(i, a, b) for(ll i = (a); i < (b); ++i) #define REP3(i, a, b, c) for(ll i = (a); i < (b); i += (c)) #define per0(n) for(int jidlsjf = 0; jidlsjf < (n); ++jidlsjf) #define per1(i, n) for(ll i = (n)-1; i >= 0; --i) #define per2(i, a, b) for(ll i = (a)-1; i >= b; --i) #define per3(i, a, b, c) for(ll i = (a)-1; i >= (b); i -= (c)) #define fore1(i, a) for(auto &&i : a) #define fi first #define se second #define pb push_back #define ppb pop_back #define ppf pop_front #define eb emplace_back #define lb(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define ub(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define rng(v, l, r) v.begin() + (l), v.begin() + (r) #define all(c) begin(c), end(c) #define rall(c) rbegin(c), rend(c) #define SORT(v) sort(all(v)) #define REV(v) reverse(all(v)) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define UNIQUE(x) SORT(x), x.erase(unique(all(x)), x.end()) template T SUM(const S &v) { return accumulate(all(v), T(0)); } void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(double &a) { cin >> a; } void scan(string &a) { cin >> a; } template void scan(pair &p) { scan(p.first), scan(p.second); } template void scan(vector &); template void scan(vector &a) { for(auto &i : a) scan(i); } template pair operator-(const pair &x) { return pair(-x.first, -x.second); } template pair operator-(const pair &x, const pair &y) { return pair(x.fi - y.fi, x.se - y.se); } template pair operator+(const pair &x, const pair &y) { return pair(x.fi + y.fi, x.se + y.se); } template pair operator&(const pair &l, const pair &r) { return pair(max(l.fi, r.fi), min(l.se, r.se)); } template pair operator+=(pair &l, const pair &r) { return l = l + r; } template pair operator-=(pair &l, const pair &r) { return l = l - r; } template bool intersect(const pair &l, const pair &r) { return (l.se < r.se ? r.fi < l.se : l.fi < r.se); } template vector &operator++(vector &v) { fore(e, v) e++; return v; } template vector operator++(vector &v, int) { auto res = v; fore(e, v) e++; return res; } template vector &operator--(vector &v) { fore(e, v) e--; return v; } template vector operator--(vector &v, int) { auto res = v; fore(e, v) e--; return res; } template vector &operator+=(vector &l, const vector &r) { fore(e, r) l.eb(e); return l; } template void scan(T &a) { cin >> a; } template T ceil(T x, S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); } template T floor(T x, S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : x / y - (x % y == 0 ? 0 : 1))); } template T POW(T x, int n) { T res = 1; for(; n; n >>= 1, x *= x) if(n & 1) res *= x; return res; } template T POW(T x, S n, const ll &mod) { T res = 1; x %= mod; for(; n; n >>= 1, x = x * x % mod) if(n & 1) res = res * x % mod; return res; } vector factor(ll x) { vector ans; for(ll i = 2; i * i <= x; i++) if(x % i == 0) { ans.push_back({i, 1}); while((x /= i) % i == 0) ans.back().second++; } if(x != 1) ans.push_back({x, 1}); return ans; } template vector divisor(T x) { vector ans; for(T i = 1; i * i <= x; i++) if(x % i == 0) { ans.pb(i); if(i * i != x) ans.pb(x / i); } return ans; } template bool is_prime(T x) { if(x<2) return false; for(T i = 2; i * i <= x; i++) if(x % i == 0) { return false; } return true; } template vector prime_factors(T x) { vector ans; for(T i = 2; i * i <= x; i++){ while(x % i == 0) { ans.pb(i); x/=i; } } if(x>1) ans.pb(x); return ans; } template vector sieve_prime(T l,T r) { vector ans(r-l+1,true); ll lim=sqrt(r); for(T i = 2; i <= lim; i++){ for(T j=max(i*i,(l+i-1/(i*i)));j<=r;j+=i){ ans[j-l]=false; } } if(l==1) ans[0]=false; return ans; } template vector sieve_prime(T x) { vector ans(x+1,true); ans[0]=ans[1]=false; for(T i = 2; i * i <= x; i++){ if(ans[i]){ for(T j=i*i;j<=x;j+=i){ ans[j]=false; } } } return ans; } ll max(int x, ll y) { return max((ll)x, y); } ll max(ll x, int y) { return max(x, (ll)y); } int min(int x, ll y) { return min((ll)x, y); } int min(ll x, int y) { return min(x, (ll)y); } ll pow2(int i) { return 1LL << i; } int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); } int topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); } int lowbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); } int lowbit(ll a) { return a == 0 ? 64 : __builtin_ctzll(a); } int popcount(uint64_t t) { return __builtin_popcountll(t); } static inline uint64_t popcount64(uint64_t x) { uint64_t m1 = 0x5555555555555555ll; uint64_t m2 = 0x3333333333333333ll; uint64_t m4 = 0x0F0F0F0F0F0F0F0Fll; uint64_t h01 = 0x0101010101010101ll; x -= (x >> 1) & m1; x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4; return (x * h01) >> 56; } bool ispow2(int i) { return i && (i & -i) == i; } template::value, typename T_container::value_type>::type> istream& operator >> (istream &is, T_container &v) { for(T &x : v) is >> x; return is; } #ifdef __SIZEOF_INT128__ ostream& operator << (ostream &os, __int128 const& value){ static char buffer[64]; int index = 0; __uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value; if (value < 0) os << '-'; else if (T == 0) return os << '0'; for(; T > 0; ++index){ buffer[index] = static_cast('0' + (T % 10)); T /= 10; } while(index > 0) os << buffer[--index]; return os; } istream& operator >> (istream& is, __int128& T){ static char buffer[64]; is >> buffer; size_t len = strlen(buffer), index = 0; T = 0; int mul = 1; if (buffer[index] == '-') ++index, mul *= -1; for(; index < len; ++index) T = T * 10 + static_cast(buffer[index] - '0'); T *= mul; return is; } #endif template ostream& operator<<(ostream &os, const pair &p) { return os << '(' << p.first << ", " << p.second << ')'; } template::value, typename T_container::value_type>::type> ostream& operator << (ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } template, class R = less

> ostream& operator << (ostream& out, priority_queue const& M){ static priority_queue U; U = M; out << "{ "; while(!U.empty()) out << U.top() << " ", U.pop(); return (out << "}"); } template ostream& operator << (ostream& out, queue

const& M){ static queue

U; U = M; out << "{"; string sep; while(!U.empty()){ out << sep << U.front(); sep = ", "; U.pop(); } return (out << "}"); } ll gcdex(ll a,ll b,ll &x,ll &y){ // ax+by=gcd(a,b) if(b==0){ y=0; x=1; return a; } ll x1,y1; ll d=gcdex(b,a%b,x1,y1); x=y1; y=x1-y1*(a/b); return d; } ll gcd(ll a , ll b) { if(b==0) return a; a%=b; return gcd(b,a); } const ll inf=1e18; void solve() { //your code ll n; cin>>n; for(int i=1;i