"""Segment Tree Beats for Python.

Supports the following operations on an integer (or comparable numeric) array:

    range_chmin(l, r, x)  : A[i] = min(A[i], x) for l <= i < r
    range_chmax(l, r, x)  : A[i] = max(A[i], x) for l <= i < r
    range_add(l, r, x)    : A[i] += x for l <= i < r
    range_set(l, r, x)    : A[i] = x for l <= i < r
    range_sum(l, r)       : sum(A[l:r])
    range_max(l, r)       : max(A[l:r])
    range_min(l, r)       : min(A[l:r])

All ranges are half-open: [l, r), as in Python slices and AtCoder Library.

Notes
-----
* Empty updates and range_sum(l, l) are allowed.
* range_min / range_max require a non-empty range and raise ValueError otherwise.
* This is a Segment Tree Beats implementation, not a plain lazy segment tree.
  The chmin/chmax operations use the second maximum/minimum and their counts to
  decide whether a whole node can be updated without descending to its children.
* Updates are amortized, not guaranteed O(log N) in the worst case per call.

Example
-------
    seg = SegmentTreeBeats([2, 5, 7, 9, 12])
    seg.range_chmin(1, 5, 8)  # [2, 5, 7, 8, 8]
    seg.range_add(0, 2, 3)   # [5, 8, 7, 8, 8]
    assert seg.range_sum(0, 5) == 36
    assert seg.range_max(0, 5) == 8
    assert seg.to_list() == [5, 8, 7, 8, 8]
"""

from __future__ import annotations

from math import inf
from typing import Iterable, List, Optional, TypeVar

T = TypeVar("T", int, float)


class SegmentTreeBeats:
    """Range chmin/chmax/add/set and range sum/min/max queries."""

    __slots__ = (
        "n", "_length", "_sum", "_max1", "_max2", "_max_count",
        "_min1", "_min2", "_min_count", "_lazy_add", "_lazy_set",
    )

    def __init__(self, values: Iterable[T]):
        a = list(values)
        self.n = len(a)
        size = max(1, 4 * self.n)

        self._length: List[int] = [0] * size
        self._sum: List[T] = [0] * size  # type: ignore[list-item]
        self._max1 = [-inf] * size
        self._max2 = [-inf] * size
        self._max_count = [0] * size
        self._min1 = [inf] * size
        self._min2 = [inf] * size
        self._min_count = [0] * size
        self._lazy_add: List[T] = [0] * size  # type: ignore[list-item]
        self._lazy_set: List[Optional[T]] = [None] * size

        if self.n:
            self._build(1, 0, self.n, a)

    # ---------- Construction and aggregate maintenance ----------

    def _build(self, k: int, left: int, right: int, a: List[T]) -> None:
        self._length[k] = right - left
        if right - left == 1:
            v = a[left]
            self._sum[k] = v
            self._max1[k] = self._min1[k] = v
            self._max2[k] = -inf
            self._min2[k] = inf
            self._max_count[k] = self._min_count[k] = 1
            return
        mid = (left + right) // 2
        self._build(k * 2, left, mid, a)
        self._build(k * 2 + 1, mid, right, a)
        self._pull(k)

    def _pull(self, k: int) -> None:
        lc, rc = k * 2, k * 2 + 1
        self._sum[k] = self._sum[lc] + self._sum[rc]

        lmax, rmax = self._max1[lc], self._max1[rc]
        if lmax > rmax:
            self._max1[k] = lmax
            self._max_count[k] = self._max_count[lc]
            self._max2[k] = max(self._max2[lc], rmax)
        elif lmax < rmax:
            self._max1[k] = rmax
            self._max_count[k] = self._max_count[rc]
            self._max2[k] = max(lmax, self._max2[rc])
        else:
            self._max1[k] = lmax
            self._max_count[k] = self._max_count[lc] + self._max_count[rc]
            self._max2[k] = max(self._max2[lc], self._max2[rc])

        lmin, rmin = self._min1[lc], self._min1[rc]
        if lmin < rmin:
            self._min1[k] = lmin
            self._min_count[k] = self._min_count[lc]
            self._min2[k] = min(self._min2[lc], rmin)
        elif lmin > rmin:
            self._min1[k] = rmin
            self._min_count[k] = self._min_count[rc]
            self._min2[k] = min(lmin, self._min2[rc])
        else:
            self._min1[k] = lmin
            self._min_count[k] = self._min_count[lc] + self._min_count[rc]
            self._min2[k] = min(self._min2[lc], self._min2[rc])

    # ---------- Applying operations directly to a node ----------

    def _apply_set(self, k: int, x: T) -> None:
        length = self._length[k]
        self._sum[k] = x * length
        self._max1[k] = self._min1[k] = x
        self._max2[k] = -inf
        self._min2[k] = inf
        self._max_count[k] = self._min_count[k] = length
        self._lazy_set[k] = x
        self._lazy_add[k] = 0  # type: ignore[assignment]

    def _apply_add(self, k: int, x: T) -> None:
        self._sum[k] += x * self._length[k]
        self._max1[k] += x
        self._min1[k] += x
        # +/- infinity sentinels remain +/- infinity after addition.
        self._max2[k] += x
        self._min2[k] += x
        if self._lazy_set[k] is not None:
            self._lazy_set[k] += x  # type: ignore[operator]
        else:
            self._lazy_add[k] += x

    def _apply_chmin(self, k: int, x: T) -> None:
        """Apply chmin when max2 < x < max1 (or max1 <= x)."""
        old_max = self._max1[k]
        if old_max <= x:
            return
        # Caller/push guarantees that the second maximum is strictly below x.
        if not self._max2[k] < x:
            raise AssertionError("invalid Beats chmin application: max2 >= x")
        self._sum[k] -= (old_max - x) * self._max_count[k]
        if self._min1[k] == old_max:
            self._min1[k] = x
        elif self._min2[k] == old_max:
            self._min2[k] = x
        self._max1[k] = x

    def _apply_chmax(self, k: int, x: T) -> None:
        """Apply chmax when min1 < x < min2 (or min1 >= x)."""
        old_min = self._min1[k]
        if old_min >= x:
            return
        # Caller/push guarantees that the second minimum is strictly above x.
        if not x < self._min2[k]:
            raise AssertionError("invalid Beats chmax application: min2 <= x")
        self._sum[k] += (x - old_min) * self._min_count[k]
        if self._max1[k] == old_min:
            self._max1[k] = x
        elif self._max2[k] == old_min:
            self._max2[k] = x
        self._min1[k] = x

    # ---------- Lazy propagation ----------

    def _push(self, k: int) -> None:
        if self._length[k] <= 1:
            return
        lc, rc = k * 2, k * 2 + 1

        value = self._lazy_set[k]
        if value is not None:
            self._apply_set(lc, value)
            self._apply_set(rc, value)
            self._lazy_set[k] = None

        add = self._lazy_add[k]
        if add != 0:
            self._apply_add(lc, add)
            self._apply_add(rc, add)
            self._lazy_add[k] = 0  # type: ignore[assignment]

        # Propagate the parent's implicit upper/lower bounds to each child.
        parent_max = self._max1[k]
        parent_min = self._min1[k]
        if self._max1[lc] > parent_max:
            self._apply_chmin(lc, parent_max)
        if self._min1[lc] < parent_min:
            self._apply_chmax(lc, parent_min)
        if self._max1[rc] > parent_max:
            self._apply_chmin(rc, parent_max)
        if self._min1[rc] < parent_min:
            self._apply_chmax(rc, parent_min)

    # ---------- Range updates ----------

    def range_chmin(self, l: int, r: int, x: T) -> None:
        """Set every A[i] in [l, r) to min(A[i], x)."""
        self._check_range(l, r)
        if l < r and self.n:
            self._range_chmin(1, 0, self.n, l, r, x)

    def _range_chmin(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
        if qr <= nl or nr <= ql or self._max1[k] <= x:
            return
        if ql <= nl and nr <= qr and self._max2[k] < x:
            self._apply_chmin(k, x)
            return
        self._push(k)
        mid = (nl + nr) // 2
        self._range_chmin(k * 2, nl, mid, ql, qr, x)
        self._range_chmin(k * 2 + 1, mid, nr, ql, qr, x)
        self._pull(k)

    def range_chmax(self, l: int, r: int, x: T) -> None:
        """Set every A[i] in [l, r) to max(A[i], x)."""
        self._check_range(l, r)
        if l < r and self.n:
            self._range_chmax(1, 0, self.n, l, r, x)

    def _range_chmax(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
        if qr <= nl or nr <= ql or self._min1[k] >= x:
            return
        if ql <= nl and nr <= qr and x < self._min2[k]:
            self._apply_chmax(k, x)
            return
        self._push(k)
        mid = (nl + nr) // 2
        self._range_chmax(k * 2, nl, mid, ql, qr, x)
        self._range_chmax(k * 2 + 1, mid, nr, ql, qr, x)
        self._pull(k)

    def range_add(self, l: int, r: int, x: T) -> None:
        """Add x to every A[i] in [l, r)."""
        self._check_range(l, r)
        if l < r and self.n:
            self._range_add(1, 0, self.n, l, r, x)

    def _range_add(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
        if qr <= nl or nr <= ql:
            return
        if ql <= nl and nr <= qr:
            self._apply_add(k, x)
            return
        self._push(k)
        mid = (nl + nr) // 2
        self._range_add(k * 2, nl, mid, ql, qr, x)
        self._range_add(k * 2 + 1, mid, nr, ql, qr, x)
        self._pull(k)

    def range_set(self, l: int, r: int, x: T) -> None:
        """Assign x to every A[i] in [l, r)."""
        self._check_range(l, r)
        if l < r and self.n:
            self._range_set(1, 0, self.n, l, r, x)

    def _range_set(self, k: int, nl: int, nr: int, ql: int, qr: int, x: T) -> None:
        if qr <= nl or nr <= ql:
            return
        if ql <= nl and nr <= qr:
            self._apply_set(k, x)
            return
        self._push(k)
        mid = (nl + nr) // 2
        self._range_set(k * 2, nl, mid, ql, qr, x)
        self._range_set(k * 2 + 1, mid, nr, ql, qr, x)
        self._pull(k)

    # ---------- Range queries ----------

    def range_sum(self, l: int, r: int):
        """Return sum(A[l:r]); an empty range has sum 0."""
        self._check_range(l, r)
        if l == r or self.n == 0:
            return 0
        return self._range_sum(1, 0, self.n, l, r)

    def _range_sum(self, k: int, nl: int, nr: int, ql: int, qr: int):
        if qr <= nl or nr <= ql:
            return 0
        if ql <= nl and nr <= qr:
            return self._sum[k]
        self._push(k)
        mid = (nl + nr) // 2
        return self._range_sum(k * 2, nl, mid, ql, qr) + self._range_sum(
            k * 2 + 1, mid, nr, ql, qr
        )

    def range_max(self, l: int, r: int):
        """Return max(A[l:r]); raises ValueError for an empty range."""
        self._check_range(l, r)
        if l == r:
            raise ValueError("range_max requires a non-empty range")
        return self._range_max(1, 0, self.n, l, r)

    def _range_max(self, k: int, nl: int, nr: int, ql: int, qr: int):
        if qr <= nl or nr <= ql:
            return -inf
        if ql <= nl and nr <= qr:
            return self._max1[k]
        self._push(k)
        mid = (nl + nr) // 2
        return max(
            self._range_max(k * 2, nl, mid, ql, qr),
            self._range_max(k * 2 + 1, mid, nr, ql, qr),
        )

    def range_min(self, l: int, r: int):
        """Return min(A[l:r]); raises ValueError for an empty range."""
        self._check_range(l, r)
        if l == r:
            raise ValueError("range_min requires a non-empty range")
        return self._range_min(1, 0, self.n, l, r)

    def _range_min(self, k: int, nl: int, nr: int, ql: int, qr: int):
        if qr <= nl or nr <= ql:
            return inf
        if ql <= nl and nr <= qr:
            return self._min1[k]
        self._push(k)
        mid = (nl + nr) // 2
        return min(
            self._range_min(k * 2, nl, mid, ql, qr),
            self._range_min(k * 2 + 1, mid, nr, ql, qr),
        )

    # ---------- Convenience methods ----------

    def all_sum(self):
        """Return the sum of the whole array (0 for an empty tree)."""
        return self._sum[1] if self.n else 0

    def all_max(self):
        """Return the maximum of the whole array; raises ValueError if empty."""
        if not self.n:
            raise ValueError("all_max requires a non-empty tree")
        return self._max1[1]

    def all_min(self):
        """Return the minimum of the whole array; raises ValueError if empty."""
        if not self.n:
            raise ValueError("all_min requires a non-empty tree")
        return self._min1[1]

    def __getitem__(self, i: int):
        """Return A[i]."""
        if not 0 <= i < self.n:
            raise IndexError("index out of range")
        return self.range_max(i, i + 1)

    def __len__(self) -> int:
        return self.n

    def to_list(self) -> List:
        """Materialize and return the current array in O(N) time."""
        if not self.n:
            return []
        result = [None] * self.n

        def dfs(k: int, left: int, right: int) -> None:
            if right - left == 1:
                result[left] = self._max1[k]
                return
            self._push(k)
            mid = (left + right) // 2
            dfs(k * 2, left, mid)
            dfs(k * 2 + 1, mid, right)

        dfs(1, 0, self.n)
        return result

    def _check_range(self, l: int, r: int) -> None:
        if not (0 <= l <= r <= self.n):
            raise ValueError(f"invalid range [{l}, {r}) for n={self.n}")


if __name__ == "__main__":
    # Small smoke test. Run `python segment_tree_beats.py` to check the module.
    seg = SegmentTreeBeats([2, 5, 7, 9, 12])
    seg.range_chmin(1, 5, 8)
    assert seg.to_list() == [2, 5, 7, 8, 8]
    seg.range_add(0, 2, 3)
    assert seg.to_list() == [5, 8, 7, 8, 8]
    assert seg.range_sum(0, 5) == 36
    assert seg.range_max(0, 5) == 8
    assert seg.range_min(0, 5) == 5
    seg.range_chmax(0, 4, 7)
    assert seg.to_list() == [7, 8, 7, 8, 8]
    seg.range_set(1, 4, -2)
    assert seg.to_list() == [7, -2, -2, -2, 8]
    print("SegmentTreeBeats smoke test: OK")

"""Wavelet Matrix for static range-frequency / order-statistics queries.

Values may be arbitrary comparable integers; values are coordinate-compressed.
Intervals are half-open [l, r). Complexity: O(log sigma) per query.
"""
from bisect import bisect_left
from array import array

class WaveletMatrix:
    def __init__(self, data):
        self.n = len(data)
        self.values = sorted(set(data))
        sigma = len(self.values)
        self.bitlen = max(1, (sigma - 1).bit_length())
        rank = {v: i for i, v in enumerate(self.values)}
        cur = [rank[x] for x in data]
        self.pref_ones = []
        self.zeros = []
        for bit in range(self.bitlen - 1, -1, -1):
            pref = array('I', [0])
            zero, one = [], []
            acc = 0
            for x in cur:
                if (x >> bit) & 1:
                    acc += 1
                    one.append(x)
                else:
                    zero.append(x)
                pref.append(acc)
            self.pref_ones.append(pref)
            self.zeros.append(len(zero))
            cur = zero + one

    def _check_range(self, l, r):
        if not (0 <= l <= r <= self.n):
            raise IndexError("expected 0 <= l <= r <= n")

    def _count_rank_lt(self, l, r, k):
        """Count compressed ranks < k in [l,r)."""
        if k <= 0 or l == r:
            return 0
        if k >= len(self.values):
            return r - l
        result = 0
        for level, bit in enumerate(range(self.bitlen - 1, -1, -1)):
            pref = self.pref_ones[level]
            ones_l, ones_r = pref[l], pref[r]
            zeros_l, zeros_r = l - ones_l, r - ones_r
            if (k >> bit) & 1:
                result += zeros_r - zeros_l
                l = self.zeros[level] + ones_l
                r = self.zeros[level] + ones_r
            else:
                l, r = zeros_l, zeros_r
        return result

    def range_freq_lt(self, l, r, x):
        """Count i in [l,r) such that data[i] < x."""
        self._check_range(l, r)
        return self._count_rank_lt(l, r, bisect_left(self.values, x))

    def range_freq(self, l, r, lower, upper):
        """Count i in [l,r) such that lower <= data[i] < upper."""
        self._check_range(l, r)
        if lower >= upper:
            return 0
        return self.range_freq_lt(l, r, upper) - self.range_freq_lt(l, r, lower)

    def kth_smallest(self, l, r, k):
        """Return the 0-indexed k-th smallest value in data[l:r]."""
        self._check_range(l, r)
        if not (0 <= k < r - l):
            raise IndexError("k must satisfy 0 <= k < r-l")
        rank = 0
        for level, bit in enumerate(range(self.bitlen - 1, -1, -1)):
            pref = self.pref_ones[level]
            ones_l, ones_r = pref[l], pref[r]
            zeros_l, zeros_r = l - ones_l, r - ones_r
            zero_count = zeros_r - zeros_l
            rank <<= 1
            if k < zero_count:
                l, r = zeros_l, zeros_r
            else:
                k -= zero_count
                rank |= 1
                l = self.zeros[level] + ones_l
                r = self.zeros[level] + ones_r
        return self.values[rank]

    def range_min(self, l, r):
        return self.kth_smallest(l, r, 0)

    def range_max(self, l, r):
        return self.kth_smallest(l, r, r - l - 1)

"""Slope Trick for a convex piecewise-linear function.

The represented function is maintained up to additive constants as a sum of
hinges. Supports adding max(a-x, 0), max(x-a, 0), |x-a|, constants, and a
horizontal translation. `get_min()` returns the minimum function value;
`get_argmin()` returns the interval of minimizers.

Heaps maintain the invariant max(L) <= min(R). L is a max-heap (negated), R a
min-heap. Offsets make `shift(dx)` O(1).
"""
from heapq import heappush, heappop

class SlopeTrick:
    def __init__(self):
        self.L = []
        self.R = []
        self.add_l = 0
        self.add_r = 0
        self.min_f = 0

    def _left_max(self):
        return -self.L[0] + self.add_l

    def _right_min(self):
        return self.R[0] + self.add_r

    def _rebalance(self):
        while self.L and self.R and self._left_max() > self._right_min():
            x = self._left_max()
            y = self._right_min()
            self.min_f += x - y
            heappop(self.L)
            heappop(self.R)
            heappush(self.L, -(y - self.add_l))
            heappush(self.R, x - self.add_r)

    def add_const(self, c):
        self.min_f += c

    def add_a_minus_x(self, a):
        """Add max(a-x, 0) to the function."""
        heappush(self.L, -(a - self.add_l))
        self._rebalance()

    def add_x_minus_a(self, a):
        """Add max(x-a, 0) to the function."""
        heappush(self.R, a - self.add_r)
        self._rebalance()

    def add_abs(self, a):
        """Add |x-a| to the function."""
        self.add_a_minus_x(a)
        self.add_x_minus_a(a)

    def shift(self, dx):
        """Horizontal translation: new_f(x) = old_f(x-dx)."""
        self.add_l += dx
        self.add_r += dx

    def get_min(self):
        return self.min_f

    def get_argmin(self):
        """Return (leftmost minimizer, rightmost minimizer); may be infinite."""
        left = self._left_max() if self.L else float('-inf')
        right = self._right_min() if self.R else float('inf')
        return left, right

"""Generic all-roots tree DP (rerooting).

`graph[u]` contains `(v, edge_data)` for every directed adjacency of the tree.
`merge(a, b)` combines two neighbor contributions (must be associative).
`vertex(merged_value, u)` adds/handles vertex u.
`edge(value_at_u, u, v, edge_data)` converts the message from u's side into
its contribution as seen from v. Identity is the neutral element for merge.

Returns `answer[u]`, the DP result when u is considered the root.
"""

def rerooting(n, graph, identity, merge, vertex, edge):
    if n == 0:
        return []
    parent = [-1] * n
    parent_edge = [None] * n
    order = [0]
    parent[0] = 0
    for u in order:
        for v, data in graph[u]:
            if v == parent[u]:
                continue
            if parent[v] != -1:
                continue
            parent[v] = u
            parent_edge[v] = data
            order.append(v)
    if len(order) != n:
        raise ValueError("graph must be a connected tree")

    # down[u]: result for the subtree rooted at u, excluding parent side.
    down = [None] * n
    for u in reversed(order):
        agg = identity
        for v, data in graph[u]:
            if parent[v] == u:
                agg = merge(agg, edge(down[v], v, u, data))
        down[u] = vertex(agg, u)

    # up[u] is the message from parent[u] to u (already converted across edge).
    up = [None] * n
    answer = [None] * n
    for u in order:
        contributions = []
        for v, data in graph[u]:
            if v == parent[u] and u != 0:
                contributions.append(up[u])
            else:
                contributions.append(edge(down[v], v, u, data))
        m = len(contributions)
        pref = [identity] * (m + 1)
        suff = [identity] * (m + 1)
        for i in range(m):
            pref[i + 1] = merge(pref[i], contributions[i])
        for i in range(m - 1, -1, -1):
            suff[i] = merge(contributions[i], suff[i + 1])
        answer[u] = vertex(pref[m], u)

        for i, (v, data) in enumerate(graph[u]):
            if parent[v] == u:
                without_v = merge(pref[i], suff[i + 1])
                up[v] = edge(vertex(without_v, u), u, v, data)
    return answer
"""Classic Mo's algorithm for offline range queries [l, r).

Example:
    mo = Mo(n, queries)  # queries is [(l, r), ...]
    answers = mo.run(add, remove, get_answer)

`add(i)` / `remove(i)` mutate the maintained window state. `get_answer()`
returns the answer for the current window. Queries are returned in input order.
"""
from math import isqrt

class Mo:
    def __init__(self, n, queries, block_size=None):
        self.n = n
        self.queries = [(l, r, i) for i, (l, r) in enumerate(queries)]
        if any(not (0 <= l <= r <= n) for l, r, _ in self.queries):
            raise ValueError("queries must satisfy 0 <= l <= r <= n")
        q = len(queries)
        if block_size is None:
            block_size = max(1, n // max(1, isqrt(max(1, q))))
        self.block_size = max(1, block_size)
        b = self.block_size
        self.ordered = sorted(
            self.queries,
            key=lambda x: (x[0] // b, x[1] if (x[0] // b) % 2 == 0 else -x[1]),
        )

    def run(self, add, remove, get_answer):
        ans = [None] * len(self.queries)
        left = right = 0
        for l, r, qi in self.ordered:
            while left > l:
                left -= 1
                add(left)
            while right < r:
                add(right)
                right += 1
            while left < l:
                remove(left)
                left += 1
            while right > r:
                right -= 1
                remove(right)
            ans[qi] = get_answer()
        return ans

"""Lowlink for an undirected graph: bridges and articulation points.

Input edges is a list [(u,v), ...]. Parallel edges are supported because DFS
tracks edge IDs, not just parent vertices. Vertices are 0-indexed.
"""
import sys

class LowLink:
    def __init__(self, n, edges):
        self.n = n
        self.edges = edges
        self.g = [[] for _ in range(n)]
        for eid, (u, v) in enumerate(edges):
            self.g[u].append((v, eid))
            self.g[v].append((u, eid))
        self.timer = 0
        self.tin = [-1] * n
        self.low = [-1] * n
        self.bridges = []       # edge IDs
        self.articulation = []  # vertex IDs
        self._art = [False] * n
        sys.setrecursionlimit(max(1_000_000, n * 2 + 10))
        for v in range(n):
            if self.tin[v] == -1:
                self._dfs(v, -1)
        self.bridges.sort()
        self.articulation = [v for v, yes in enumerate(self._art) if yes]

    def _dfs(self, v, parent_eid):
        self.tin[v] = self.low[v] = self.timer
        self.timer += 1
        children = 0
        for to, eid in self.g[v]:
            if eid == parent_eid:
                continue
            if self.tin[to] != -1:
                self.low[v] = min(self.low[v], self.tin[to])
            else:
                self._dfs(to, eid)
                self.low[v] = min(self.low[v], self.low[to])
                if self.low[to] > self.tin[v]:
                    self.bridges.append(eid)
                if parent_eid != -1 and self.low[to] >= self.tin[v]:
                    self._art[v] = True
                children += 1
        if parent_eid == -1 and children > 1:
            self._art[v] = True

    def bridge_edges(self):
        return [self.edges[eid] for eid in self.bridges]

"""Link-Cut Tree for a dynamic forest with vertex values.

Supports link/cut/connectivity, point assignment, and path-sum queries.
Vertices are 0-indexed. `link(u,v)` / `cut(u,v)` return False if the operation
would be invalid (cycle / non-edge respectively).
"""

class LinkCutTree:
    def __init__(self, values):
        self.n = len(values)
        self.ch = [[-1, -1] for _ in values]
        self.fa = [-1] * self.n
        self.rev = [False] * self.n
        self.val = list(values)
        self.sm = list(values)
        self.mx = list(values)
        self.mn = list(values)

    def _is_aux_root(self, x):
        p = self.fa[x]
        return p == -1 or (self.ch[p][0] != x and self.ch[p][1] != x)

    def _apply_rev(self, x):
        if x != -1:
            self.ch[x][0], self.ch[x][1] = self.ch[x][1], self.ch[x][0]
            self.rev[x] = not self.rev[x]

    def _push(self, x):
        if self.rev[x]:
            self._apply_rev(self.ch[x][0])
            self._apply_rev(self.ch[x][1])
            self.rev[x] = False

    def _pull(self, x):
        self.sm[x] = self.val[x]
        self.mx[x] = self.val[x]
        self.mn[x] = self.val[x]
        left, right = self.ch[x]
        if left != -1:
            self.sm[x] += self.sm[left]
            self.mx[x] = max(self.mx[x], self.mx[left])
            self.mn[x] = min(self.mn[x], self.mn[left])
        if right != -1:
            self.sm[x] += self.sm[right]
            self.mx[x] = max(self.mx[x], self.mx[right])
            self.mn[x] = min(self.mn[x], self.mn[right])

    def _rotate(self, x):
        p = self.fa[x]
        g = self.fa[p]
        d = 1 if self.ch[p][1] == x else 0
        b = self.ch[x][d ^ 1]
        if not self._is_aux_root(p):
            self.ch[g][1 if self.ch[g][1] == p else 0] = x
        self.fa[x] = g
        self.ch[x][d ^ 1] = p
        self.fa[p] = x
        self.ch[p][d] = b
        if b != -1:
            self.fa[b] = p
        self._pull(p)
        self._pull(x)

    def _splay(self, x):
        stack = [x]
        y = x
        while not self._is_aux_root(y):
            y = self.fa[y]
            stack.append(y)
        for y in reversed(stack):
            self._push(y)
        while not self._is_aux_root(x):
            p = self.fa[x]
            if not self._is_aux_root(p):
                g = self.fa[p]
                zigzig = (self.ch[p][0] == x) == (self.ch[g][0] == p)
                self._rotate(p if zigzig else x)
            self._rotate(x)

    def _access(self, x):
        last = -1
        y = x
        while y != -1:
            self._splay(y)
            self.ch[y][1] = last
            if last != -1:
                self.fa[last] = y
            self._pull(y)
            last = y
            y = self.fa[y]
        self._splay(x)

    def make_root(self, x):
        self._access(x)
        self._apply_rev(x)

    def find_root(self, x):
        self._access(x)
        while True:
            self._push(x)
            left = self.ch[x][0]
            if left == -1:
                break
            x = left
        self._splay(x)
        return x

    def connected(self, u, v):
        if u == v:
            return True
        return self.find_root(u) == self.find_root(v)

    def link(self, u, v):
        self.make_root(u)
        if self.find_root(v) == u:
            return False
        self.fa[u] = v
        return True

    def cut(self, u, v):
        self.make_root(u)
        self._access(v)
        if self.ch[v][0] != u or self.ch[u][1] != -1:
            return False
        self.ch[v][0] = -1
        self.fa[u] = -1
        self._pull(v)
        return True

    def set_value(self, x, value):
        self._access(x)
        self.val[x] = value
        self._pull(x)

    def path_sum(self, u, v):
        if not self.connected(u, v):
            raise ValueError("u and v are disconnected")
        self.make_root(u)
        self._access(v)
        return self.sm[v]

    def path_max(self, u, v):
        if not self.connected(u, v):
            raise ValueError("u and v are disconnected")
        self.make_root(u)
        self._access(v)
        return self.mx[v]

    def path_min(self, u, v):
        if not self.connected(u, v):
            raise ValueError("u and v are disconnected")
        self.make_root(u)
        self._access(v)
        return self.mn[v]

"""Discrete Li Chao tree for minimum of lines y = m*x + b.

Pass all possible query x-coordinates at construction time. Query coordinates
must be present in xs. For maximum queries, negate m, b, and the returned value.
"""
from bisect import bisect_left

class LiChaoTree:
    def __init__(self, xs, inf=10**100):
        self.xs = sorted(set(xs))
        if not self.xs:
            raise ValueError("xs must not be empty")
        self.n = len(self.xs)
        self.inf = inf
        self.tree = [None] * (4 * self.n)

    @staticmethod
    def _eval(line, x):
        return line[0] * x + line[1]

    def add_line(self, m, b):
        self._add(1, 0, self.n, (m, b))

    def _add(self, node, lo, hi, line):
        cur = self.tree[node]
        if cur is None:
            self.tree[node] = line
            return
        mid = (lo + hi) >> 1
        x_l, x_m = self.xs[lo], self.xs[mid]
        if self._eval(line, x_m) < self._eval(cur, x_m):
            self.tree[node], line = line, cur
            cur = self.tree[node]
        if hi - lo == 1:
            return
        # After the midpoint winner is fixed in the node, the other line can
        # beat it on at most one side because both functions are linear.
        if self._eval(line, x_l) < self._eval(cur, x_l):
            self._add(node * 2, lo, mid, line)
        elif self._eval(line, self.xs[hi - 1]) < self._eval(cur, self.xs[hi - 1]):
            self._add(node * 2 + 1, mid, hi, line)

    def query(self, x):
        idx = bisect_left(self.xs, x)
        if idx == self.n or self.xs[idx] != x:
            raise ValueError("query x must be included in xs")
        node, lo, hi = 1, 0, self.n
        ans = self.inf
        while True:
            line = self.tree[node]
            if line is not None:
                ans = min(ans, self._eval(line, x))
            if hi - lo == 1:
                break
            mid = (lo + hi) >> 1
            if idx < mid:
                node, hi = node * 2, mid
            else:
                node, lo = node * 2 + 1, mid
        return ans


class MonotoneCHT:
    """Minimum CHT with strictly increasing slopes and arbitrary x queries.

    Lines are inserted in nondecreasing slope order. Duplicate slopes are
    handled by keeping only the smaller intercept. Queries may be in any order;
    binary search makes each query O(log number_of_lines).
    """
    def __init__(self):
        self.lines = []

    @staticmethod
    def _value(line, x):
        return line[0] * x + line[1]

    @staticmethod
    def _redundant(a, b, c):
        # slopes a.m < b.m < c.m; b is redundant if x_ab <= x_bc
        return (a[1] - b[1]) * (c[0] - b[0]) <= (b[1] - c[1]) * (b[0] - a[0])

    def add_line(self, m, b):
        if self.lines and m < self.lines[-1][0]:
            raise ValueError("slopes must be added in nondecreasing order")
        if self.lines and m == self.lines[-1][0]:
            if b >= self.lines[-1][1]:
                return
            self.lines.pop()
        new = (m, b)
        while len(self.lines) >= 2 and self._redundant(self.lines[-2], self.lines[-1], new):
            self.lines.pop()
        self.lines.append(new)

    def query(self, x):
        if not self.lines:
            raise ValueError("no lines have been inserted")
        lo, hi = 0, len(self.lines) - 1
        while lo < hi:
            mid = (lo + hi) >> 1
            if self._value(self.lines[mid], x) <= self._value(self.lines[mid + 1], x):
                hi = mid
            else:
                lo = mid + 1
        return self._value(self.lines[lo], x)
"""Heavy-Light Decomposition for a tree.

Vertices are 0-indexed. All segment intervals are half-open [l, r).
`path_segments(u, v)` returns (l, r, reversed) pieces in the order from u to v.
For commutative queries, the `reversed` flag can be ignored.
"""

class HLD:
    def __init__(self, n, graph, root=0):
        self.n = n
        self.g = graph
        self.root = root
        self.parent = [-1] * n
        self.depth = [0] * n
        self.size = [1] * n
        self.heavy = [-1] * n

        order = [root]
        self.parent[root] = root
        for v in order:
            for to in graph[v]:
                if to == self.parent[v]:
                    continue
                self.parent[to] = v
                self.depth[to] = self.depth[v] + 1
                order.append(to)
        if len(order) != n:
            raise ValueError("graph must be a connected tree")
        self.parent[root] = -1

        for v in reversed(order):
            best_size = 0
            for to in graph[v]:
                if self.parent[to] == v:
                    self.size[v] += self.size[to]
                    if self.size[to] > best_size:
                        best_size = self.size[to]
                        self.heavy[v] = to

        self.head = [-1] * n
        self.pos = [-1] * n
        self.inv = [-1] * n
        cur = 0
        stack = [(root, root)]
        while stack:
            v, h = stack.pop()
            while v != -1:
                self.head[v] = h
                self.pos[v] = cur
                self.inv[cur] = v
                cur += 1
                # Light subtrees are postponed; heavy child is walked immediately.
                for to in graph[v]:
                    if self.parent[to] == v and to != self.heavy[v]:
                        stack.append((to, to))
                v = self.heavy[v]

        self.out = [self.pos[v] + self.size[v] for v in range(n)]

    def is_ancestor(self, u, v):
        return self.pos[u] <= self.pos[v] < self.out[u]

    def subtree_interval(self, v):
        """Return the Euler-order interval of v's subtree: [pos[v], out[v])."""
        return self.pos[v], self.out[v]

    def lca(self, u, v):
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] > self.depth[self.head[v]]:
                u = self.parent[self.head[u]]
            else:
                v = self.parent[self.head[v]]
        return u if self.depth[u] < self.depth[v] else v

    def distance(self, u, v):
        w = self.lca(u, v)
        return self.depth[u] + self.depth[v] - 2 * self.depth[w]

    def path_segments(self, u, v, edge=False):
        """Return ordered path pieces (l, r, reversed) from u to v.

        A piece covers base-array positions [l, r). If `reversed` is True,
        traverse the piece from r-1 down to l. With edge=True, each edge is
        represented by its deeper endpoint, so the LCA position is excluded.
        """
        left, right = [], []
        while self.head[u] != self.head[v]:
            if self.depth[self.head[u]] >= self.depth[self.head[v]]:
                left.append((self.pos[self.head[u]], self.pos[u] + 1, True))
                u = self.parent[self.head[u]]
            else:
                right.append((self.pos[self.head[v]], self.pos[v] + 1, False))
                v = self.parent[self.head[v]]
        if self.depth[u] >= self.depth[v]:
            l = self.pos[v] + (1 if edge else 0)
            r = self.pos[u] + 1
            if l < r:
                left.append((l, r, True))
        else:
            l = self.pos[u] + (1 if edge else 0)
            r = self.pos[v] + 1
            if l < r:
                right.append((l, r, False))
        return left + right[::-1]

    def path_intervals(self, u, v, edge=False):
        """Return unordered path intervals; intended for commutative operations."""
        return [(l, r) for l, r, _ in self.path_segments(u, v, edge)]