#include "bits/stdc++.h"
using namespace std;
typedef long long ll; typedef double lf; typedef pair<ll, ll> II; typedef vector<ll> vec;
const inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(0u); cout.tie(0u); }
const lf PI = acos(-1);
const lf EPS = 1e-8;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll DIM = 1e5;
int main() {
    fast_io();
    /* El Psy Kongroo */

    return 0;
}

// 注：爆int64考虑__int128或相关intrinsic
// MSVC: https://codeforces.com/blog/entry/106396
// Clang on Visual Studio: https://learn.microsoft.com/en-us/cpp/build/clang-support-cmake?view=msvc-170
template<typename T> T binpow(T a, T res, ll b) {
	while (b > 0) {
		if (b & 1) res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
ll binpow_mod(ll a, ll b, ll m = MOD) {
    a %= m;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = (__int128)res * a % m;
        a = (__int128)a * a % m;
        b >>= 1;
    }
    return res;
}

ll exgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll t = x;
    x = y, y = t - (a / b) * y;
    return d;
}

template<typename T, size_t Size> struct matrix {
	T m[Size][Size]{};
	struct identity {};
	matrix() {}; // zero matrix
	matrix(identity const&) { for (size_t i = 0; i < Size; i++) m[i][i] = 1; } // usage: matrix(matrix::identity{})
	matrix(initializer_list<initializer_list<T>> l) { // usage: matrix({{1,2},{3,4}})
		size_t i = 0;
		for (auto& row : l) { size_t j = 0; for (auto& x : row) m[i][j++] = x; i++; }
	}
	matrix operator*(matrix const& other) const {
		matrix res;
		for (size_t i = 0; i < Size; i++)
			for (size_t j = 0; j < Size; j++)
				for (size_t k = 0; k < Size; k++)
					res.m[i][j] = (res.m[i][j] + m[i][k] * other.m[k][j]) % MOD;
		return res;
	}
};
typedef matrix<ll, 2> mat2;
typedef matrix<ll, 3> mat3;
typedef matrix<ll, 4> mat4;

struct linear_base : array<ll, 64> {
    void insert(ll x) {
        for (ll i = 63; i >= 0; i--) if ((x >> i) & 1) {
            if (!(*this)[i]) {
                (*this)[i] = x;
                break;
            }
            x ^= (*this)[i];
        }
    }
};

template <typename T> struct vec2 {
  T x, y;
  ///
  inline T length_sq() const { return x * x + y * y; }
  inline T length() const { return sqrt(length_sq()); }
  inline vec2 &operator+=(vec2 const &other) {
    x += other.x, y += other.y;
    return *this;
  }
  inline vec2 &operator-=(vec2 const &other) {
    x -= other.x, y -= other.y;
    return *this;
  }
  inline vec2 &operator*=(T const &other) {
    x *= other, y *= other;
    return *this;
  }
  inline vec2 &operator/=(T const &other) {
    x /= other, y /= other;
    return *this;
  }
  inline vec2 operator+(vec2 const &other) const {
    vec2 v = *this;
    v += other;
    return v;
  }
  inline vec2 operator-(vec2 const &other) const {
    vec2 v = *this;
    v -= other;
    return v;
  }
  inline vec2 operator*(T const &other) const {
    vec2 v = *this;
    v *= other;
    return v;
  }
  inline vec2 operator/(T const &other) const {
    vec2 v = *this;
    v /= other;
    return v;
  }
  ///
  inline static T dist_sq(vec2 const &a, vec2 const &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  }
  inline static T dist(vec2 const &a, vec2 const &b) {
    return sqrt(vec2::dist_sq(a, b));
  }
  inline static T cross(vec2 const &a, vec2 const &b) {
    return a.x * b.y - a.y * b.x;
  }
  inline static T dot(vec2 const &a, vec2 const &b) {
    return a.x * b.x + a.y * b.y;
  }
  ///
  inline friend bool operator<(vec2 const &a, vec2 const &b) {
    if (a.x != b.x)
      return a.x < b.x;
    return a.y < b.y;
  }
  inline friend bool operator==(vec2 const &a, vec2 const &b) {
    return a.x == b.x && a.y == b.y;
  }
};
typedef vec2<lf> point;

vector<point> convex_hull(vector<point> &p) { // 逆时针
  vector<point> hi, lo;
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  ll n = p.size();
  if (n <= 1)
    return p;
  for (auto a : p) {
    while (hi.size() > 1 &&
           point::cross(a - hi.back(), a - hi[hi.size() - 2]) <= 0)
      hi.pop_back();
    while (lo.size() > 1 &&
           point::cross(a - lo.back(), a - lo[lo.size() - 2]) >= 0)
      lo.pop_back();
    lo.push_back(a);
    hi.push_back(a);
  }

  lo.pop_back();
  reverse(hi.begin(), hi.end());
  hi.pop_back();
  lo.insert(lo.end(), hi.begin(), hi.end());
  return lo;
}

typedef vec2<lf> point;
int main() {
    fast_io();
    /* El Psy Kongroo */
    ll n, q; cin >> n >> q;
    vector<point> convex_hull(n); // 逆时针    
    for (auto& p : convex_hull) cin >> p;
    convex_hull.push_back(convex_hull.front());
    while (q--) {
        ll x11, y11, x22, y22; cin >> x11 >> y11 >> x22 >> y22;
        point c1{ (lf)x11,(lf)y11 }, c2{ (lf)x22,(lf)y22 };
        /*
        圆外一点到圆内所有一点平均距离 -> 记点到圆心距为 $$d$$ 对称性易知
        $$d^2_{sum} = \int_0^R \int_0^{2\pi} \sqrt{r^2 + d^2 - 2rd\cos \theta} \, r \, d\theta \, dr = \frac{\pi r^4}{2}+\pi d^2r^2$$
        $$d^2_{avg} = d^2_{sum} / S_{C} = \frac{r^2}{2}+d^2$$
        故求$$d_min$$；点在凸包内显然直接取$$0$$,凸包外则取点到边垂距min（若可取）或点到点min
        */
        point C = (c1 + c2) / 2.0; lf R = (c1 - c2).length() / 2;
        lf ans = R * R / 2;
        if (!is_inside(C)) {
            lf dis = min_dis(C);
            ans += dis * dis;
        }            
        cout << fixed << setprecision(10) << ans << endl;
    }
    return 0;
}

lf caliper(vector<point> const &p) { // p为处理好的凸包
  ll j = 2, n = p.size();
  lf mx_dis = 0;
  // 每条边,查j+1 和边 (i,i+1) 的距离是不是比 j 更大，如果是就将 j
  // 加一，否则说明 j 是此边的最优点
  // 检查可以通过叉积比较面积比较距离(垂点)
  for (ll i = 0; i < n; i++) {
    auto e1 = p[i % n], e2 = p[(i + 1) % n];
    while (j < n + i) {
      auto p1 = p[j % n], p2 = p[(j + 1) % n];
      lf a1 = abs(point::cross(e2 - e1, p1 - e1));
      lf a2 = abs(point::cross(e2 - e1, p2 - e1));
      if (a1 <= a2)
        j++;
      else
        break;
    }
    // 此时j点一定为该边上距离最远
    mx_dis = max(
        {mx_dis, point::dist_sq(e1, p[j % n]), point::dist_sq(e2, p[j % n])});
  }
  return mx_dis;
}

namespace comb {
	ll fac[DIM], ifac[DIM]; // x!, 1/x!
	void prep(ll N = DIM - 1) {
		fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
		for (ll i = 2; i <= N; i++) fac[i] = fac[i - 1] * i % MOD;
		ifac[N] = binpow_mod(fac[N], MOD - 2, MOD);
		for (ll i = N - 1; i >= 1; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;
	}
	ll comb(ll n, ll m) {
		return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
	}
	ll lucas(ll n, ll m) {
		if (m == 0) return 1;
		return comb(n % MOD, m % MOD) * lucas(n / MOD, m / MOD) % MOD;
	}
}

namespace eratosthenes_sieve { // Eratosthenes筛法 + 区间筛
    vec primes;
    bool not_prime[DIM];

    void init(ll N=DIM - 1) {
        for (ll i = 2; i <= N; ++i) {
            if (!not_prime[i]) primes.push_back(i);
            for (auto j : primes) {
                if (i * j > N) break;
                not_prime[i * j] = true;
                if (i % j == 0) break;
            }
        }
    }
    void update_range(ll l, ll r) {
        for (auto p : primes) {
            for (ll j = max((ll)ceil(1.0 * l / p), p) * p; j <= r; j += p) not_prime[j] = true;
    	}
    }
}

namespace eratosthenes_sieve_d { // https://oi-wiki.org/math/number-theory/sieve/#筛法求约数个数
    vec primes;
    bool not_prime[DIM];
    ll D[DIM], num[DIM];

    void init(ll N = DIM - 1) {
        D[1] = 1;
        for (ll i = 2; i <= N; ++i) {
            if (!not_prime[i]) primes.push_back(i), D[i] = 2, num[i] = 1;
            for (auto j : primes) {
                if (i * j > N) break;
                not_prime[i * j] = true;
                if (i % j == 0) {
                    num[i * j] = num[i] + 1;
                    D[i * j] = D[i] / num[i * j] * (num[i * j] + 1);
                    break;
                }
                num[i * j] = 1;
                D[i * j] = D[i] * 2;
            }
        }
    }
}
   
namespace eratosthenes_sieve_phi {  // https://oi.wiki/math/number-theory/sieve/#筛法求欧拉函数
    vec primes;    
    bool not_prime[DIM];
    ll phi[DIM];

    void init(ll N = DIM - 1) {
        phi[1] = 1;
        for (ll i = 2; i <= N; ++i) {
            if (!not_prime[i]) primes.push_back(i), phi[i] = i - 1;
            for (auto j : primes) {
                if (i * j > N) break;
                not_prime[i * j] = true;
                if (i % j == 0) {
                    phi[j * i] = phi[i] * j;
                    break;
                }
				phi[j * i] = phi[i] * (j - 1); // phi(j)

            }
        }
    }
}

bool Miller_Rabin(ll p) {  // 判断素数
    if (p < 2) return 0;
    if (p == 2) return 1;
    if (p == 3) return 1;
    ll d = p - 1, r = 0;
    while (!(d & 1)) ++r, d >>= 1;  // 将d处理为奇数
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 823}) {
        if (p == a) return 1;
        ll x = binpow_mod(a, d, p);
        if (x == 1 || x == p - 1) continue;
        for (int i = 0; i < r - 1; ++i) {
            x = (__int128)x * x % p;
            if (x == p - 1) break;
        }
        if (x != p - 1) return 0;
    }
    return 1;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll Pollard_Rho(ll x) {  // 找出x的一个非平凡因数
    if (x % 2 == 0) return 2;
    ll s = 0, t = 0;
    ll c = ll(rng()) % (x - 1) + 1;
    ll val = 1;
    for (ll goal = 1; ; goal *= 2, s = t, val = 1) {
        for (ll step = 1; step <= goal; step++) {
            t = ((__int128)t * t + c) % x;
            val = (__int128)val * abs((long long)(t - s)) % x;
            if (step % 127 == 0) {
                ll g = gcd(val, x);
                if (g > 1) return g;
            }
        }
        ll d = gcd(val, x);
        if (d > 1) return d;
    }
}

// MR+PR
void Prime_Factor(ll x, v& res) {   
    auto f = [&](auto f,ll x){
        if (x == 1) return;
        if (Miller_Rabin(x)) return res.push_back(x);
        ll y = Pollard_Rho(x);
        f(f,y),f(f,x / y);
    };
    f(f,x),sort(res.begin(),res.end());    
}
// Euler
namespace euler_sieve {
	vector<vec> primes;
	void Prime_Factor_Offline(ll MAX) {
		primes.resize(MAX);
		for (ll i = 2; i < MAX; i++) {
			if (!primes[i].empty()) continue;
			for (ll j = i; j < MAX; j += i) {
				ll mj = j;
				while (mj % i == 0) {
					primes[j].push_back(i);
					mj /= i;
				}
			}
		}
	}

	void Prime_Factor(ll x, vec& res) {
		for (ll i = 2; i * i <= x; i++) while (x % i == 0) res.push_back(i), x /= i;
		if (x != 1) res.push_back(x);
	}
}

vec coeff[DIM];
for (ll i = 2; i < DIM;i++)
    for (ll j = i; j < DIM; j += i)
        coeff[j].push_back(i);

struct graph {
	vector<vector<ll>> G; // 邻接表
	vector<ll> in; // 入度
    
	ll n;
	graph(ll dimension) : n(dimension), G(dimension + 1),in(dimension + 1) {};
	void add_edge(ll from, ll to) {
		G[from].push_back(to);
		in[to]++;
	}
	bool topsort() {
		L.clear();
		queue<ll> S;
		ll ans = 0;
		for (ll i = 1; i <= n; i++) {
			if (in[i] == 0) S.push(i), dp[i] = 1;
		}
		while (!S.empty()) {
			ll v = S.front(); S.pop();
			L.push_back(v);	
			for (auto& out : G[v])
				if (--in[out] == 0)
					S.push(out);
		}
		return ((L.size() == n) ? true : false); // 当且仅当图为DAG时成立
	}
};

// vector<vec> adj
vec vis(n), dep(n), topo; topo.reserve(n);
auto dfs = [&](ll u, auto&& dfs) -> bool {
    vis[u] = 1;
    for (auto& v : adj[u]) {
        dep[v] = max(dep[u] + 1, dep[v]);
        if (vis[v] == 1) /*visiting*/ return false;
        if (vis[v] == 0 && !dfs(v, dfs)) /*to visit*/ return false;
    }
    vis[u] = 2; /*visited*/ 
    topo.push_back(u);
    return true;
};
bool ok = true;
for (ll i = 0; ok && i < n; i++) if (vis[i] == 0) ok &= dfs(i, dfs);

ll F[DIM][DIM];
int main() {
	ll n, m; cin >> n >> m;
	memset(F, 63, sizeof(F));
	for (ll v = 1; v <= n; v++) F[v][v] = 0;
	while (m--) {
		ll u, v, w; cin >> u >> v >> w;
		F[u][v] = min(F[u][v], w);
		F[v][u] = min(F[v][u], w);
	}
	for (ll k = 1; k <= n; k++) {
		for (ll i = 1; i <= n; i++) {
			for (ll j = 1; j <= n; j++) {
				F[i][j] = min(F[i][j], F[i][k] + F[k][j]);
			}
		}
	}
	for (ll i = 1; i <= n; i++) {
		for (ll j = 1; j <= n; j++) {
			cout << F[i][j] << ' ';
		}
		cout << '\n';
	}
}

auto dijkstra = [&](ll start) {
    vec dis(n + 1, INF), vis(n + 1, false);
    priority_queue<II, vector<II>, greater<>> T; // 小顶堆
    T.emplace( 0, start );
    dis[start] = 0;
    while (!T.empty())
    {
        auto [_, u] = T.top(); T.pop();
        if (!vis[u]) {
            vis[u] = true;
            for (ll v : G[u]) { // 松弛出边
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    T.emplace( dis[v], v );
                }
            }
        }
    }
    return dis;
};

struct dsu {
	vector<ll> pa;
	dsu(const ll size) : pa(size) { iota(pa.begin(), pa.end(), 0); }; // 初始时，每个集合都是自己的父亲
	inline bool is_root(const ll leaf) { return pa[leaf] == leaf; }
	inline ll find(const ll leaf) { return is_root(leaf) ? leaf : pa[leaf] = find(pa[leaf]); } // 路径压缩
	inline void unite(const ll x, const ll y) { pa[find(x)] = find(y); }
};
struct edge { ll from, to, weight; };
int main() {
	ll n, m; cin >> n >> m;
	vector<edge> edges(m);
	for (auto& edge : edges)
		cin >> edge.from >> edge.to >> edge.weight;
	sort(edges.begin(), edges.end(), PRED(lhs.weight < rhs.weight));
	dsu U(n + 1);
	ll ans = 0;
	ll cnt = 0;
	for (auto& edge : edges) {
		if (U.find(edge.from) != U.find(edge.to)) {
			U.unite(edge.from, edge.to);
			ans += edge.weight;
			cnt++;
		}
	}
	if (cnt == n - 1) cout << ans;
	else cout << "orz";
}

struct eulerian_path {
    map<ll, set<ll>> G;
    map<ll,ll> in;
    void add_edge(ll u, ll v) {
        G[u].insert(v);
        G[v].insert(u);
        in[u]++; in[v]++;
    }
    vec hierholzer(ll s) {
        ll odds = 0;
        for (auto [v,i] : in) odds += i & 1;
        if (odds != 0 /* 欧拉回路 */ && odds != 2 /* 欧拉路 */) return {};
        vec res;
        auto dfs = [&](ll u, auto&& dfs) -> void {
            while (!G[u].empty()) {
                ll v = *G[u].begin();
                G[u].erase(v);
                G[v].erase(u);
                dfs(v, dfs);
            }
            res.push_back(u);
        };
        dfs(s,dfs);
        reverse(res.begin(), res.end());
        return move(res);
    }
};

int main() {
    fast_io();
    /* El Psy Kongroo */
    const string ascii = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    ll n, mn = INF; cin >> n;
    eulerian_path p;
    while (n--) {
        string s; cin >> s;
        ll u = s[0], v = s[1];
        p.add_edge(u, v); // 构造二分图
        mn = min({mn,u,v});
    }
    for (char c : ascii)
        if (p.in[c] & 1) { mn = c; break; } // 欧拉路情况；找最小点切入
    auto res = p.hierholzer(mn);
    if (!res.size()) cout << "No Solution" << endl;
    else {
        for (auto& x : res)
            cout << (char)x;
        cout << endl;
    }
    return 0;
}

int main() {
    fast_io();
    /* El Psy Kongroo */
    ll t; cin >> t;
    while (t--) {
        ll n; cin >> n;
        eulerian_path euler;
        map<II, ll> inv;
        ll root = 0;
        for (ll i = 1; i <= n; i++) {
            ll v, p; cin >> v >> p;
            euler.add_edge(v, -p); // 构造二分图
            inv[{v,p}] = i;
            root = v;
        }
        for (auto [v, i] : euler.in)
            if (i & 1) { root = v; } // 欧拉路情况起点必然是单入度
        auto res = euler.hierholzer(root);
        if (res.size() != n + 1) {
            cout << "NO" << endl;
        }else {
            cout << "YES" << endl;
            if (n == 1) cout << 1;
            else {
                for (ll i = 0; i < n; i++) {
                    ll u = res[i], v = res[i + 1];
                    if (u < 0) swap(u,v);
                    cout << inv[{u,-v}] << ' ';
                }
            }
            cout << endl;
        }
    }
    return 0;
}

template<typename Container> struct sparse_table {
	ll len;
	vector<Container> table; // table[i,j] -> [i, i + 2^j - 1] 最大值
	void init(const Container& data) {
		len = data.size();
		ll l1 = ceil(log2(len)) + 1;
		table.assign(len, Container(l1));
		for (ll i = 0; i < len; i++) table[i][0] = data[i];
		for (ll j = 1; j < l1; j++) {
			ll jpow2 = 1LL << (j - 1);
			for (ll i = 0; i + jpow2 < len; i++) {
				// f(i,j) = max(f(i,j-1), f(i + 2^(j-1), j-1))
				table[i][j] = min(table[i][j - 1], table[i + jpow2][j - 1]);
			}
		}
	}
	auto query(ll l, ll r) {
		ll s = floor(log2(r - l + 1));
		// op([l,l + 2^s - 1], [r - 2^s + 1, r])
		// -> op(f(l,s), f(r - 2^s + 1, s))
		return min(table[l][s], table[r - (1LL << s) + 1][s]);
	}
};

struct graph {
	vector<v> G;
	ll n;

	v pos;
	vector<II> depth_dfn;
	sparse_table<vector<II>> st;

	graph(ll n) : n(n), G(n + 1), pos(n + 1) { depth_dfn.reserve(2 * n + 5); };

	void add_edge(ll from, ll to) {
		G[from].push_back(to);
	}

	void lca_prep(ll root) {
		ll cur = 0;		
		// 样例欧拉序 -> 4 2 4 1 3 1 5 1 4
		// 样例之深度 -> 0 1 0 1 2 1 2 1 0
		// 求 2 - 3  ->   ^ - - ^
		// 之间找到深度最小的点即可
		// 1. 欧拉序		
		depth_dfn.clear();
		auto dfs = [&](ll u, ll pa, ll dep, auto& dfs) -> void {
			depth_dfn.push_back({ dep, u }), pos[u] = depth_dfn.size() - 1;
			for (auto& v : G[u]) 
				if (v != pa) {
					dfs(v, u, dep+1, dfs);
					depth_dfn.push_back({ dep, u });
				}
		};
		dfs(root, root, 0,  dfs);
		// 2. 建关于深度st表；深度顺序即欧拉序
		st.init(depth_dfn);
	}
	ll lca(ll x, ll y) {
		ll px = pos[x], py = pos[y]; // 找到x,y的欧拉序
		if (px > py) swap(px, py);
		return st.query(px, py).second;	// 直接query最小深度点；对应即为lca
	}
};

int main() {
	ll n, m, s; scanf("%lld%lld%lld", &n, &m, &s);
	graph G(n + 1);
	for (ll i = 1; i < n; i++) {
		ll x, y; scanf("%lld%lld", &x, &y);
		G.add_edge(x,y);
		G.add_edge(y,x);
	}

	G.lca_prep(s);
	while (m--) {
		ll x, y; scanf("%lld%lld", &x, &y);
		ll ans = G.lca(x, y);
		printf("%lld\n",ans);
	}
}

struct graph {
    ll n;

    vector<vector<ll>> G;

    vector<vec> fa;
    vec depth, dis;

    graph(ll n) : n(n), fa(ceil(log2(n)) + 1, vec(n)), depth(n), G(n), dis(n) {}

    void add_edge(ll from, ll to) {
        G[from].push_back(to);
        G[to].push_back(from);
    }

    void prep(ll root) {
        auto dfs = [&](ll u, ll pa, ll dep, auto& dfs) -> void {
            fa[0][u] = pa, depth[u] = dep;
            for (ll i = 1; i < fa.size(); i++) {
                // u 的第 2^i 的祖先是 u 第 (2^(i-1)) 个祖先的第 (2^(i-1)) 个祖先
                fa[i][u] = fa[i - 1][fa[i - 1][u]];
            }
            for (auto& e : G[u]) {
                if (e == pa) continue;
                dis[e] = dis[u] + 1;
                dfs(e, u, dep + 1, dfs);
            }
        };
        dfs(root, root, 1, dfs);
    }

    ll lca(ll x, ll y) {
        if (depth[x] > depth[y]) swap(x, y); // y 更深
        ll diff = depth[y] - depth[x];
        for (ll i = 0; diff; i++, diff >>= 1) // 让 y 上升到 x 的深度
            if (diff & 1) y = fa[i][y];
        if (x == y) return x;
        for (ll i = fa.size() - 1; i >= 0; i--) {
            if (fa[i][x] != fa[i][y]) {
                x = fa[i][x];
                y = fa[i][y];
            }
        }
        return { fa[0][x] };
    }

    ll kth_parent(ll u, ll k){
        for (ll i = 63;i >= 0;i--) if (k & (1ll << i)) u = fa[i][u];
        return u;
    }
};

struct edge { ll to, cost; };
struct graph {
	ll n;

	vector<vector<edge>> G;
	v dis, fa;
	vector<bool> tag;
	graph(ll n) : n(n), G(n), dis(n), fa(n), tag(n) {};

	void add_edge(ll from, ll to, ll cost = 1) {
		G[from].push_back({ to, cost });
	}

	// 实现 1：两次DFS -> 起止点
	// 不能处理负权边（？）
	ll path_dfs() {
		ll end = 0; dis[end] = 0;
		auto dfs = [&](ll u, ll pa, auto& dfs) -> void {
			fa[u] = pa; // 反向建图
			for (auto& e : G[u]) {
				if (e.to == pa) continue;
				dis[e.to] = dis[u] + e.cost;
				if (dis[e.to] > dis[end]) end = e.to;
				dfs(e.to, u, dfs);				
			}
		};
		// 在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
		dfs(1, 1, dfs); // 1 -> 端点 A
		ll begin = end;
		dis[end] = 0;   
		dfs(end,end, dfs); // 端点 A -> B
		// fa回溯既有 B -> A 路径；省去额外dfs
		fa[begin] = 0; for (ll u = end; u ; u = fa[u]) tag[u] = true;
		return dis[end];
	}

	// 实现 2：树形DP -> 长度
	ll path_dp() {
		v dp(n); // 定义 dp[u]：以 u 为根的子树中，从 u 出发的最长路径
		// dp[u] = max(dp[u], dp[v] + cost(u,v)), v \in G[u]
		ll ans = 0;
		auto dfs = [&](ll u, ll pa, auto& dfs) -> void {
			for (auto& e : G[u]) {
				if (e.to == pa) continue;
				dfs(e.to, u, dfs);
				ll cost = e.cost;
				// 题解：第一条直径边权设为-1
				// - 若这些边被选择（与第二条边重叠），贡献则能够被抵消，否则这些边将走两遍
				// - 若没被选择，则不对第二次答案造成影响
				if (tag[u] && tag[e.to]) cost = -1;
				ans = max(ans, dp[u] + dp[e.to] + cost);
				dp[u] = max(dp[u], dp[e.to] + cost);
			}
		};
		dfs(1, 1, dfs);
		return ans;
	}
};

// 便携板子
auto diameter = [&]()
{
    vec dis(n + 1);
    ll end = 0; dis[end] = 0;
    auto dfs = [&](ll u, ll pa, auto&& dfs) -> void {
        for (auto& e : G[u]) {
            if (e == pa) continue;
            dis[e] = dis[u] + 1;
            if (dis[e] > dis[end]) end = e;
            dfs(e, u, dfs);
        }
    };
    // 在一棵树上，从任意节点 y 开始进行一次 DFS，到达的距离其最远的节点 z 必为直径的一端。
    dfs(1, 1, dfs); // 1 -> 端点 A
    ll begin = end;
    dis[end] = 0;
    dfs(end,end, dfs); // 端点 A -> B
    return dis[end];
};

struct dinic_flow {
    ll n, cnt = 0;
    vec nxt, head;
    struct edge { ll v, capacity, cost; };
    vector<edge> e;
    dinic_flow(ll verts, ll edges = DIM) : e(edges), nxt(edges, -1), head(edges, -1), n(verts), dis(n + 1), cur(n + 1), vis(n + 1) {}
private:
    void add_edge(ll u, ll v, ll capacity, ll cost) {
        nxt[cnt] = head[u];
        e[cnt] = {v, capacity, cost};
        head[u] = cnt;
        cnt++;
    }
    vec dis, cur; // 最短路, 当前弧
    vector<bool> vis;
    // 最大流
    // 分层图
    bool dinic_bfs(ll s, ll t) {
        // 分层
        queue<ll> Q;
        dis.assign(n + 1, 0);
        dis[s] = 1; Q.push(s);
        // O(mn)
        while (!Q.empty()){
            ll u = Q.front(); Q.pop();
            for (ll i = head[u]; i != -1; i = nxt[i]) {
                auto [v, capacity, cost] = e[i];
                // 还有容量即可传递
                if (capacity > 0 && dis[v] == 0) {
                    dis[v] = dis[u] + 1;
                    Q.push(v);
                }
            }
        }
        return dis[t] > 0;
    }
    // 最小费用最大流 Min-cost-max-flow
    // 每次找费用最少的分层图
    bool dinic_bfs_mcmf(ll s, ll t) {
        vis.assign(n + 1, 0);
        dis.assign(n + 1, INF);
        queue<ll> Q;
        dis[s] = 0, vis[s] = 1, Q.push(s);
        while (!Q.empty()){
            const ll u = Q.front(); Q.pop(), vis[u] = false;
            for (ll i = head[u]; i != -1; i = nxt[i]) {
                auto [v, capacity, cost] = e[i];
                // SPFA 找到最低cost路径传递,松弛出边
                if (capacity > 0 && dis[v] > dis[u] + cost) {
                    dis[v] = dis[u] + cost;
                    if (!vis[v]) Q.push(v), vis[v] = true;
                }
            }
        }
        return dis[t] != INF;
    }
    // 最大流
    // 增广路
    ll dinic_dfs(ll u, ll t, ll flow = INF) {
        if (u == t) return flow;
        for (ll& i = cur[u] /* 维护掉已经走过的弧 */; i != -1; i = nxt[i]) {
            auto& [v, capacity, cost] = e[i];
            auto& [v_inv, capacity_inv, _] = e[i^1];
            if (capacity > 0 && dis[v] == dis[u] + 1) {
                ll d = dinic_dfs(v, t, min(flow, capacity));
                // 往下传递到未走边
                if (d > 0)
                {
                    capacity -= d, capacity_inv += d; // 传递反向边
                    return d; // 向上传递
                }
            }
        }
        return 0; // 没有增广路
    }
    // 最小费用最大流 Min-cost-max-flow
    // 增广路
    ll cost_mcmf = 0;
    ll dinic_dfs_mcmf(ll u, ll t, ll flow = INF) {
        // 找增广路
        if (u == t) return flow;
        vis[u] = true;
        ll cur_flow = 0;
        for (ll& i = cur[u] /* 维护掉已经走过的弧 */; i != -1 && cur_flow < flow; i = nxt[i]) {
            auto& [v, capacity, cost] = e[i];
            auto& [v_inv, capacity_inv, _] = e[i^1];
            if (!vis[v] && capacity > 0 && dis[v] == dis[u] + cost) {
                ll d = dinic_dfs_mcmf(v, t, min(flow - cur_flow, capacity));
                // 往下传递到未走边
                if (d > 0)
                {
                    capacity -= d, capacity_inv += d; // 传递反向边
                    cur_flow += d, cost_mcmf += d * cost;
                    // return d
                    // 继续遍历,最大流f此时一定
                    // 需要找到最小费用即需要该复杂度,最终O(mnf)
                }
            }
        }
        vis[u] = false;
        return cur_flow; // 没有增广路时仍为0
    }
public:
    void dinic_add_edge(ll u, ll v, ll capacity, ll cost = 0) {
        add_edge(u, v, capacity, cost); // W[i]
        add_edge(v, u, 0, -cost); // W[i^1]
    }
    // 最大流 O(mn)
    // 可复用
    ll dinic(ll s, ll t) {
        ll ans = 0;
        auto e_pre = e;
        while (dinic_bfs(s, t)) {
            cur = head;
            while (ll d = dinic_dfs(s, t)) ans += d;
        }
        e = e_pre;
        return ans;
    }
    // 最小费用最大流 O(mnf), f为最大流 -> [最大流, 最小费用]
    // 可复用
    II dinic_mcmf(ll s, ll t) {
        ll ans = 0;
        cost_mcmf = 0;
        auto e_pre = e;
        while (dinic_bfs_mcmf(s, t)) {
            cur = head;
            while (ll d = dinic_dfs_mcmf(s, t)) ans += d;
        }
        e = e_pre;
        return {ans, cost_mcmf};
    }
};

struct HLD {
    ll n, dfn_cnt = 0;
    vec sizes, depth, top /*所在重链顶部*/, parent, dfn /*DFS序*/, dfn_out /* 链尾DFS序 */, inv_dfn, heavy /*重儿子*/;
    vector<vec> G;
    HLD(ll n) : n(n), G(n), sizes(n), depth(n), top(n), parent(n), dfn(n), dfn_out(n), inv_dfn(n), heavy(n) {};
    void add_edge(ll u, ll v) {
        G[u].push_back(v);
        G[v].push_back(u);
    }
    // 注：唯一的重儿子即为最大子树根
    void dfs1(ll u) {
        heavy[u] = -1;
        sizes[u] = 1;
        for (ll& v : G[u]) {
            if (depth[v]) continue;
            depth[v] = depth[u] + 1;
            parent[v] = u;
            dfs1(v);
            sizes[u] += sizes[v];
            // 选最大子树为重儿子
            if (heavy[u] == -1 || sizes[v] > sizes[heavy[u]]) heavy[u] = v;
        }
    }
    // 注：dfn为重边优先时顺序
    void dfs2(ll u, ll v_top) {
        top[u] = v_top;
        dfn[u] = ++dfn_cnt;
        inv_dfn[dfn[u]] = u;
        if (heavy[u] != -1) {
            // 优先走重儿子
            dfs2(heavy[u], v_top);
            for (ll& v : G[u])
                if (v != heavy[u] && v != parent[u]) dfs2(v, v);
        }
        dfn_out[u] = dfn_cnt;
    }
    // 预处理(!!)
    void prep(ll root) {
        depth[root] = 1;
        dfs1(root);
        dfs2(root, root);
    }
    // 多点lca
    ll lca(ll a, ll b, ll c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
    // 树上两点距离
    ll dist(ll u, ll v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)] + 1;
    }
    // logn求LCA
    ll lca(ll u, ll v) {
        while (top[u] != top[v]) // 到同一重链
        {
            // 跳到更深的链
            if (depth[top[u]] < depth[top[v]]) swap(u, v);
            u = parent[top[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }
    // 路径上区间query dfn序
    void path_sum(ll u, ll v, auto&& query) {
        while (top[u] != top[v]) // 到同一重链
        {
            // 跳到更深的链
            if (depth[top[u]] < depth[top[v]]) swap(u, v);
            // [dfn[top[u]],[u]]上求和 (在此插入RMQ)
            query(dfn[top[u]], dfn[u]);
            u = parent[top[u]];
        }
        if (dfn[v] > dfn[u]) swap(u, v);
        query(dfn[v], dfn[u]);
    }
    // 第k的父亲
    ll kth_parent(ll u, ll k) {
      ll dep = depth[u] - k;
      while (depth[top[u]] > dep) u = parent[top[u]];
      return inv_dfn[dfn[u] - (depth[u] - dep)];
    }
    // v属于u的子树
    bool is_child_of(ll u, ll v) {
        return dfn[u] <= dfn[v] && dfn[v] <= dfn_out[u];
    }
};

	ll n, dfn_cnt = 0;
	vec sizes, depth, top /*所在重链顶部*/, parent, dfn /*DFS序*/, dfn_out /* 链尾DFS序 */, inv_dfn, heavy /*重儿子*/;
	vector<vec> G;
	DSU(ll n) : n(n), G(n), sizes(n), depth(n), top(n), parent(n), dfn(n), dfn_out(n), inv_dfn(n + 1), heavy(n) {};
	void add_edge(ll u, ll v) {
		G[u].push_back(v);
		G[v].push_back(u);
	}
	// 注：唯一的重儿子即为最大子树根
	void dfs1(ll u) {
		sizes[u] = 1;		
		dfn[u] = ++dfn_cnt;
		inv_dfn[dfn_cnt] = u;
		for (ll& v : G[u]) {
			if (depth[v]) continue;
			depth[v] = depth[u] + 1;
			parent[v] = u;
			dfs1(v);
			sizes[u] += sizes[v];
			// 选最大子树为重儿子
			if (!heavy[u] || sizes[v] > sizes[heavy[u]]) heavy[u] = v;
		}
		dfn_out[u] = dfn_cnt;
	}
	// 树上集合合并；考虑小集合入大集合
	// 考虑分成轻重链以后作为启发合并
	// 先处理完轻儿子后合并到重儿子上
	// 轻儿子大小<=重儿子；合并后大小>=2N，等效于倍增；
	void dfs2(ll u, ll pa, bool keep) {
		// 轻贡献
		for (ll& v : G[u]) {
			if (v == pa || heavy[u] == v) continue;
			dfs2(v, u, false); // 不保留 - 方便其他轻子树传递
		}
		// 重贡献
		if (heavy[u])
			dfs2(heavy[u], u, true); // 保留 - 合并到此子树上
		// 合并所有*轻*子树贡献
		insert(u);
		for (ll& v : G[u]) {
			if (v == pa || heavy[u] == v) continue;
			for (ll w = dfn[v]; w <= dfn_out[v]; w++)
				insert(inv_dfn[w]);
		}
		save(u);
		// 不保留情况
		if (!keep) {
			for (ll w = dfn[u]; w <= dfn_out[u]; w++)
				remove(inv_dfn[w]);
		}
	}
    // 预处理(!!)
    void prep(ll root = 1) {
        depth[root] = 1;
        dfs1(root);
        dfs2(root, 0, false);
    }
	// u点状态维护完毕    
	void save(ll u) {

	}
	// 在该子树构成集合+点    
	void insert(ll u) {

	}
	// 撤销该子树对当前集合贡献
	void remove(ll u) {

	}
};

 vec c, ans, cols; ll unique_cols = 0;
	...
	// u点状态维护完毕    
	void save(ll u) {
		ans[u] = unique_cols;
	}
	// 在该子树构成集合+点    
	void insert(ll u) {
		ll col = c[u];
		if (cols[col] == 0) unique_cols++;
		cols[col]++;
	}
	// 撤销该子树对当前集合贡献
	void remove(ll u) {
		ll col = c[u];
		cols[col]--;
		if (cols[col] == 0) unique_cols--;
		unique_cols = max(unique_cols, 0LL);
	}
};
int main() {
	fast_io();
	/* El Psy Kongroo */
	ll n; cin >> n;
	DSU dsu(n + 1);
	for (ll i = 0; i < n - 1; i++) {
		ll x, y; cin >> x >> y;
		dsu.add_edge(x, y);		
	}
	c.resize(n + 1), ans.resize(n + 1), cols.resize(n + 1),	unique_cols = 0;
	for (ll i = 1; i <= n; i++) cin >> c[i];
	dsu.prep(1);
	ll m; cin >> m;
	while (m--) {
		ll u; cin >> u;
		cerr << "##";
		cout << ans[u] << endl;
	}
	return 0;
}

vec c, ans, cols; ll cur_mx = 0, cur_sum = 0;
...
		// 不保留情况
		if (!keep) {			
			cur_mx = cur_sum = 0; // 额外有脏状态需要清掉
			for (ll w = dfn[u]; w <= dfn_out[u]; w++)
				remove(inv_dfn[w]);
		}
	}
	// 预处理(!!)
	void prep(ll root = 1) {
		dfs1(root);
		dfs2(root, 0, false);
	}	
	// u点状态维护完毕    
	void save(ll u) {
		ans[u] = cur_sum;
	}
	// 在该子树构成集合+点    
	void insert(ll u) {
		ll col = c[u];		
		cols[col]++;
		// new dominating color
		// count from here onwards
		if (cols[col] > cur_mx)
			cur_mx = cols[col], cur_sum = 0;
		if (cols[col] == cur_mx)
			cur_sum += col;
	}
	// 撤销该子树对当前集合贡献
	void remove(ll u) {
		ll col = c[u];
		cols[col]--;		
	}
};
int main() {
	fast_io();
	/* El Psy Kongroo */
	ll n; cin >> n;
	DSU dsu(n + 1);
	c.resize(n + 1), ans.resize(n + 1), cols.resize(n + 1);
	for (ll i = 1; i <= n; i++) cin >> c[i];
	for (ll i = 0; i < n - 1; i++) {
		ll x, y; cin >> x >> y;
		dsu.add_edge(x, y);		
	}
	dsu.prep(1);
	for (ll i = 1; i <= n; i++) {
		cout << ans[i] << " ";
	}
	return 0;
}

array<array<ll, DIM>, 26> cnt; // char,depth -> count
array<vector<II>, DIM> queries; // subtree->depth,index
vec ans; vector<char> c;
...
	// u点状态维护完毕    
	void save(ll u) {
		for (auto [dep, o] : queries[u]) {
			ll sum = 0, odd = 0;
			for (ll i = 0; i < 26; i++) {
				ll cur = cnt[i][dep];
				if (cur & 1) odd++;
				sum += cur;
			}
			if ((odd == 1 && sum & 1) || (odd == 0 && sum % 2 == 0)) ans[o] = true;
			else ans[o] = false;
		}
	}
	// 在该子树构成集合+点    
	void insert(ll u) {	
		cnt[c[u]][depth[u]]++;
	}
	// 撤销该子树对当前集合贡献
	void remove(ll u) {
		cnt[c[u]][depth[u]]--;
	}
};
int main() {
	fast_io();
	/* El Psy Kongroo */
	ll n, m; cin >> n >> m;
	DSU dsu(n + 1);
	c.resize(n + 1), ans.resize(m + 1), c.resize(n + 1);
	for (ll i = 2; i <= n; i++) {
		ll pa; cin >> pa;
		dsu.add_edge(i, pa);
	}
	for (ll i = 1; i <= n; i++) cin >> c[i], c[i] -= 'a';
	for (ll i = 1; i <= m; i++) {
		ll v, h; cin >> v >> h;
		queries[v].push_back({ h,i });
	}
	dsu.prep(1);
	for (ll i = 1; i <= m; i++) {
		cout << (ans[i] ? "Yes" : "No") << endl;
	}
	return 0;
		queries[v].push_back({ h,i });
	}
	dsu.prep(1);
	for (ll i = 1; i <= m; i++) {
		cout << (ans[i] ? "Yes" : "No") << endl;
	}
	return 0;
}

struct SCC {
  ll n, dfn_cnt;
  vec dfn, low, sta, dis;
  vec inv_scc;
  stack<ll> stk;
  vector<vector<II>> G;
  SCC(ll n)
      : n(n), sta(n), dfn(n) /* DFS序 */, low(n) /* 所在SCC首个（dfn最低）点 */,
        G(n), dis(n) /* 到根距离 */, dfn_cnt(0),
        inv_scc(n) /* 点所在SCC的根点 */ {};

  void add_edge(ll u, ll v, ll w = 1) { G[u].push_back({v, w}); }

  map<ll, vec> scc;
  void tarjan(ll u = 1) {
    if (dfn[u])
      return;
    dfn[u] = low[u] = ++dfn_cnt, stk.push(u), sta[u] = 1;
    for (auto const &[v, w] : G[u]) {
      if (!dfn[v])
        dis[v] = dis[u] + w, tarjan(v), low[u] = min(low[u], low[v]);
      else if (sta[v])
        low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
      ll v;
      do {
        v = stk.top(), stk.pop();
        sta[v] = 0;
        scc[u].push_back(v);
        inv_scc[v] = u;
      } while (u != v);
    }
  }
};

int main() {
    fast_io();
    /* El Psy Kongroo */
    ll n, m; cin >> n >> m;
    SCC scc(n + 1);
    vec w(n + 1);
    for (ll i = 1; i <= n; i++) cin >> w[i];
	for (ll i = 0; i < m; i++) {
		ll u, v; cin >> u >> v;
		scc.add_edge(u, v);
	}
    for (ll i = 1; i <= n; i++) scc.tarjan(i);
    // 强连通分量可当成一点
    // 缩点后构成的新图*一定*是树/DAG
    vector<vec> G(n + 1);
    vec a(n + 1), in(n + 1);
    for (ll u = 1; u <= n; u++)
        a[scc.inv_scc[u]] += w[u];
    for (ll u = 1; u <= n; u++) {
		for (auto [v, e] : scc.G[u]) {
            ll scc_u = scc.inv_scc[u], scc_v = scc.inv_scc[v];			            
            if (scc_u != scc_v) 
                G[scc_u].push_back(scc_v), in[scc_v]++;
        }
    }
    // 现在即树上找最长路径 
    // 考虑拓扑序；dp[v]->v结尾最大值，从上到下传递有(u->v), dp[v] = max(dp[v], dp[u] + a[v])    
    queue<ll> S;
    vec dp = a;
    for (ll i = 1; i <= n; i++) if (in[i] == 0 && G[i].size()) S.push(i);
    while (!S.empty()) {
        ll u = S.front(); S.pop();        
        for (ll& v : G[u]) {
            dp[v] = max(dp[v], dp[u] + a[v]);
            if (--in[v] == 0)
                S.push(v);
        }
    }    
	cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}

int main() {
  fast_io();
  /* El Psy Kongroo */
  ll n, m;
  cin >> n >> m;
  SCC scc(n + 1);
  for (ll i = 0; i < m; i++) {
    ll u, v;
    cin >> u >> v;
    scc.add_edge(u, v);
  }
  for (ll i = 1; i <= n; i++)
    scc.tarjan(i);
  vec dp(n + 1, 1);
  vec in(n + 1, 0);
  for (ll u = 1; u <= n; u++) {
    for (auto const &[v, w] : scc.G[u])
      if (scc.inv_scc[u] != scc.inv_scc[v])
        in[scc.inv_scc[v]]++;
  }
  queue<ll> Q;
  for (ll i = 1; i <= n; i++)
    if (in[i] == 0)
      Q.push(i);
  vec dp2(n + 1, 0);
  vec vis(n + 1, 0);
  auto dfs = [&](ll u, ll d, auto &&dfs) -> void { // O(n!)
    vis[u] = 1;
    dp2[u] = max(dp2[u], d);
    for (auto [v, w] : scc.G[u])
      if (scc.inv_scc[u] == scc.inv_scc[v] && !vis[v])
        dfs(v, d + 1, dfs);
    vis[u] = 0;
  };
  // 现在即树上找最长路径 
  // 考虑拓扑序；dp[v]->v结尾最大值，从上到下传递有(u->v), dp[v] = max(dp[v], dp[u] + a[v])    
  while (!Q.empty()) {
    ll u = Q.front();
    Q.pop();
    // 跑完scc上所有可能的最长路组合
    // 每个点都会跑一边跑整张(子)图,O()
    for (ll v : scc.scc[u])
      dfs(v, dp[v], dfs);
    for (ll v : scc.scc[u]) {
      for (auto [e, w] : scc.G[v]) {
        if (scc.inv_scc[e] != scc.inv_scc[v]) {
          in[scc.inv_scc[e]]--;
          if (!in[scc.inv_scc[e]])
            Q.push(scc.inv_scc[e]);
          dp[e] = max(dp[e], dp2[v] + 1);
        }
      }
    }
  }
  ll ans = *max_element(dp2.begin(), dp2.end());
  cout << ans << endl;
  return 0;
}

deque<ll> dq; // k大小窗口
for (ll i = 1; i <= n; i++) {
    // 维护k窗口min
    while (dq.size() && dq.front() <= i - k) dq.pop_front();
    while (dq.size() && a[dq.back()] >= a[i]) dq.pop_back();
    dq.push_back(i);
    if (i >= k) cout << a[dq.front()] << ' ';
}
for (ll i = 1; i <= n; i++) {
    // 维护k窗口max
    while (dq.size() && dq.front() <= i - k) dq.pop_front();
    while (dq.size() && a[dq.back()] <= a[i]) dq.pop_back();
    dq.push_back(i);
    if (i >= k) cout << a[dq.front()] << ' ';
}

template<typename Container> struct sparse_table {
	ll len;
	vector<Container> table; // table[i,j] -> [i, i + 2^j - 1] 最大值
	void init(const Container& data) {
		len = data.size();
		ll l1 = ceil(log2(len)) + 1;
		table.assign(len, Container(l1));
		for (ll i = 0; i < len; i++) table[i][0] = data[i];
		for (ll j = 1; j < l1; j++) {
			ll jpow2 = 1LL << (j - 1);
			for (ll i = 0; i + jpow2 < len; i++) {
				// f(i,j) = max(f(i,j-1), f(i + 2^(j-1), j-1))
				table[i][j] = min(table[i][j - 1], table[i + jpow2][j - 1]);
			}
		}
	}
	auto query(ll l, ll r) {
		ll s = floor(log2(r - l + 1));
		// op([l,l + 2^s - 1], [r - 2^s + 1, r])
		// -> op(f(l,s), f(r - 2^s + 1, s))
		return min(table[l][s], table[r - (1LL << s) + 1][s]);
	}
};

struct fenwick : public vec {
    using vec::vec;
    void init(vec const& a) {
        for (ll i = 0; i < a.size(); i++) {
            (*this)[i] += a[i]; // 求出该子节点
            ll j = i + lowbit(i);
            if (j < size()) (*this)[j] += (*this)[i]; // ...后更新父节点
        }
    }
    // \sum_{i=1}^{n} a_i
    ll sum(ll n) {
        ll s = 0;
        for (; n; n -= lowbit(n)) s += (*this)[n];
        return s;
    };
    ll query(ll l, ll r) {
        return sum(r) - sum(l - 1);
    }
    void add(ll n, ll k) {
        for (; n < size(); n += lowbit(n)) (*this)[n] += k;
    };
};

// https://oi-wiki.org/math/permutation/#%E9%80%86%E5%BA%8F%E6%95%B0
// 带离散化
ll inversion_discreet(vec& a) {
    map<ll, ll> inv;
    vec b = a;
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());

    fenwick F(b.size());
    for (ll i = 0; i < b.size(); i++)
        inv[b[i]] = b.size() - i;

    ll ans = 0;
    for (ll x : a) {
        ll i = inv[x];
        ans += F.sum(i - 1);
        F.add(i, 1);
    }
    return ans;
}
// 不带离散化；注意上下界
ll inversion(vec& a) {
    fenwick F(*max_element(a.begin(),a.end()) + 1);
    ll ans = 0;
    for (ll i = a.size() - 1; i >= 0; i--) {
        ans += F.sum(a[i] - 1);
        F.add(a[i], 1);
    }
    return ans;
}

struct fenwick {
    ll n;
    v a, C, Cm;
    fenwick(ll n) : n(n), a(n + 1), C(n + 1, -1e18), Cm(n + 1, 1e18) {}
    ll getmin(ll l, ll r) {
        ll ans = 1e18;
        while (r >= l) {
            ans = min(ans, a[r]); --r;
            for (; r - LOWBIT(r) >= l; r -= LOWBIT(r)) ans = min(ans, Cm[r]);
        }
        return ans;
    }
    ll getmax(ll l, ll r) {
        ll ans = -1e18;
        while (r >= l) {
            ans = max(ans, a[r]); --r;
            for (; r - LOWBIT(r) >= l; r -= LOWBIT(r)) ans = max(ans, C[r]);
        }
        return ans;
    }
    void update(ll x, ll v) {
        a[x] = v;
        for (ll i = x; i <= n; i += LOWBIT(i)) {
            C[i] = a[i]; Cm[i] = a[i];
            for (ll j = 1; j < LOWBIT(i); j *= 2) {
                C[i] = max(C[i], C[i - j]);
                Cm[i] = min(Cm[i], Cm[i - j]);
            }
        }
    }
};