// ---- begin std.cpp ----
// ---- begin templa/base.hpp ----
#ifndef CP_TEMPLA_BASE_HPP
#define CP_TEMPLA_BASE_HPP

#include <algorithm>
#include <array>
#include <bitset>
#include <bit>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// ---- begin templa/vec.hpp ----

#include <algorithm>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

template<class Elem> struct vec;

/**
 * @brief A mutable iterator range with common sequence algorithms.
 * 中文：可变迭代器区间，提供常见序列操作。
 * @details Obtain a view with v(), v(l,r), or v(i); indices and ranges are zero-based and half-open.
 * 中文：使用 v()、v(l,r) 或 v(i) 获取视图；下标从 0 开始，区间为左闭右开。
 */
template<class Iter>
struct seq_view {
    using Ref = typename std::iterator_traits<Iter>::reference;
    using Elem = typename std::iterator_traits<Iter>::value_type;

    Iter a, b;

    Iter begin() const { return a; }
    Iter end() const { return b; }
    int size() const { return static_cast<int>(b - a); }

    seq_view(Iter first, Iter last) : a(first), b(last) {}

    seq_view sort() const {
        std::sort(a, b);
        return *this;
    }

    template<class Compare>
    seq_view sort(Compare compare) const {
        std::sort(a, b, compare);
        return *this;
    }

    decltype(auto) operator[](int index) const { return *(a + index); }

    template<class Compare = std::less<Elem>, class Result = vec<int>>
    Result sorti(Compare compare = Compare{}) const {
        Result order(size());
        for (int i = 0; i < size(); ++i) order[i] = i;
        order().sort([&](int lhs, int rhs) { return compare(a[lhs], a[rhs]); });
        return order;
    }

    template<class Result = vec<Elem>>
    Result col() const {
        return Result(begin(), end());
    }

    template<class Equal = std::equal_to<Elem>, class Result = vec<std::pair<Elem, int>>>
    Result rle(Equal equal = Equal{}) const {
        Result result;
        for (const auto& value : *this) {
            if (result.empty() || !equal(result.back().first, value)) result.emp(value, 1);
            else ++result.back().second;
        }
        return result;
    }

    Iter uni() const { return std::unique(a, b); }
    Iter lb(const Elem& value) const { return std::lower_bound(a, b, value); }
    Iter ub(const Elem& value) const { return std::upper_bound(a, b, value); }
    int lbi(const Elem& value) const { return static_cast<int>(lb(value) - a); }
    int ubi(const Elem& value) const { return static_cast<int>(ub(value) - a); }
    seq_view bound(const Elem& left, const Elem& right) const { return {lb(left), lb(right)}; }

    template<class Compare>
    Iter lb(const Elem& value, Compare compare) const {
        return std::lower_bound(a, b, value, compare);
    }

    template<class Compare>
    Iter ub(const Elem& value, Compare compare) const {
        return std::upper_bound(a, b, value, compare);
    }

    template<class Predicate>
    Iter when_true_to_false(Predicate predicate) const {
        if (a == b) return a;
        return std::lower_bound(a, b, *a,
            [&](const Elem& value, const Elem&) { return predicate(value); });
    }

    seq_view same(const Elem& value) const { return {lb(value), ub(value)}; }

    template<class Function>
    auto map(Function function) const {
        using ResultElem = std::decay_t<std::invoke_result_t<Function, Ref>>;
        vec<ResultElem> result;
        for (const auto& value : *this) result.emp(function(value));
        return result;
    }

    Iter max() const { return std::max_element(a, b); }
    Iter min() const { return std::min_element(a, b); }

    template<class Compare>
    Iter min(Compare compare) const { return std::min_element(a, b, compare); }

    seq_view rev() const {
        std::reverse(a, b);
        return *this;
    }
};

/**
 * @brief Vector wrapper with chainable insertion and iterator-range helpers.
 * 中文：支持链式插入和迭代器区间操作的 vector 封装。
 * @details v() returns a mutable view; v(l,r) selects [l,r), and v(i) returns the iterator at index i.
 * 中文：v() 返回可变视图；v(l,r) 选取 [l,r)；v(i) 返回下标 i 对应的迭代器。
 */
template<class Elem>
struct vec {
    using Base = std::vector<Elem>;
    using size_type = typename Base::size_type;
    using Iter = typename Base::iterator;
    using CIter = typename Base::const_iterator;
    using Reference = typename Base::reference;
    using ConstReference = typename Base::const_reference;
    using View = seq_view<Iter>;
    using CView = seq_view<CIter>;

    vec() = default;
    explicit vec(int count, const Elem& value = Elem())
        : a(count > 0 ? static_cast<size_type>(count) : 0, value) {}

    template<class InputIter>
    vec(InputIter first, InputIter last) : a(first, last) {}

    vec(std::initializer_list<Elem> values) : a(std::move(values)) {}
    vec(Base values) : a(std::move(values)) {}

    /// @brief Borrow the underlying vector without copying; mutations affect this vec.
    /// 中文：零拷贝访问底层 vector，修改会同步作用于当前 vec。
    Base& as_vector() & { return a; }
    /// @brief Borrow the underlying vector read-only, without copying.
    /// 中文：零拷贝、只读访问底层 vector。
    const Base& as_vector() const & { return a; }
    /// @brief Move the vector out of an rvalue; the source remains valid but unspecified.
    /// 中文：从右值移出底层 vector；原对象仍有效，但内容未指定。
    Base as_vector() && { return std::move(a); }
    /// @brief Copy a const rvalue into an owning vector, avoiding a dangling reference.
    /// 中文：常量右值复制为独立 vector，避免返回悬空引用。
    Base as_vector() const && { return a; }

    /** @brief Convert an lvalue to vector<Elem>& without copying.
     * 中文：将左值零拷贝转换为 vector<Elem>&。
     * @details static_cast<vector<T>&>(v) mutates v; static_cast<vector<T>>(v) copies.
     * 中文：static_cast<vector<T>&>(v) 可原地修改 v；static_cast<vector<T>>(v) 创建副本。
     * Function template deduction does not use conversions; pass v.as_vector() instead.
     * 中文：函数模板参数推导不会使用转换运算符；此时请传入 v.as_vector()。 */
    operator Base&() & { return a; }
    /// @brief Read-only vector reference conversion. / 转换为只读 vector 引用。
    operator const Base&() const & { return a; }
    /// @brief Move-convert an rvalue to an owning vector. / 将右值移动转换为独立 vector。
    operator Base() && { return std::move(a); }
    /// @brief Copy-convert a const rvalue to an owning vector. / 将常量右值复制转换为独立 vector。
    operator Base() const && { return a; }

    Iter begin() { return a.begin(); }
    CIter begin() const { return a.begin(); }
    CIter cbegin() const { return a.cbegin(); }
    Iter end() { return a.end(); }
    CIter end() const { return a.end(); }
    CIter cend() const { return a.cend(); }
    int size() const { return static_cast<int>(a.size()); }
    bool empty() const { return a.empty(); }

    Reference back() { return a.back(); }
    ConstReference back() const { return a.back(); }

    vec sortunied() const {
        vec result = *this;
        result().sort();
        result.a.erase(result().uni(), result.end());
        return result;
    }

    Iter operator()(int index) { return a.begin() + index; }
    CIter operator()(int index) const { return a.begin() + index; }
    View operator()(int left, int right) { return {(*this)(left), (*this)(right)}; }
    CView operator()(int left, int right) const { return {(*this)(left), (*this)(right)}; }
    View operator()() { return (*this)(0, size()); }
    CView operator()() const { return (*this)(0, size()); }

    Reference operator[](int index) { return a[index]; }
    ConstReference operator[](int index) const { return a[index]; }
    Base& operator*() { return a; }
    const Base& operator*() const { return a; }

    void reserve(size_type count) { a.reserve(count); }
    void resize(size_type count) { a.resize(count); }
    void resize(size_type count, const Elem& value) { a.resize(count, value); }
    void clear() { a.clear(); }
    void assign(size_type count, const Elem& value) { a.assign(count, value); }

    template<class InputIter>
    void assign(InputIter first, InputIter last) { a.assign(first, last); }

    Iter erase(Iter position) { return a.erase(position); }
    Iter erase(Iter first, Iter last) { return a.erase(first, last); }

    vec& push(Elem value) {
        a.push_back(std::move(value));
        return *this;
    }

    template<class... Args>
    vec& emp(Args&&... args) {
        a.emplace_back(std::forward<Args>(args)...);
        return *this;
    }

    template<class Range>
    vec& app(const Range& values) {
        for (const auto& value : values) a.push_back(value);
        return *this;
    }

    Elem pop() {
        Elem value = std::move(a.back());
        a.pop_back();
        return value;
    }

    bool operator==(const vec& other) const { return a == other.a; }
    bool operator!=(const vec& other) const { return a != other.a; }
    bool operator<(const vec& other) const { return a < other.a; }
    bool operator<=(const vec& other) const { return a <= other.a; }
    bool operator>(const vec& other) const { return a > other.a; }
    bool operator>=(const vec& other) const { return a >= other.a; }

    vec<vec<Elem>> pile(int count) const { return vec<vec<Elem>>(count, *this); }

    template<class Predicate>
    vec& filter(Predicate predicate) {
        size_type write = 0;
        for (size_type read = 0; read < a.size(); ++read) {
            if (predicate(a[read])) std::swap(a[write++], a[read]);
        }
        a.resize(write);
        return *this;
    }

private:
    Base a;
};

template<class Stream, class A, class B>
Stream& operator>>(Stream& input, vec<std::pair<A, B>>& values) {
    for (auto& value : values) input >> value.first >> value.second;
    return input;
}

template<class Stream, class T>
Stream& operator>>(Stream& input, vec<T>& values) {
    for (auto& value : values) input >> value;
    return input;
}

template<class Stream, class T>
Stream& operator<<(Stream& output, const vec<T>& values) {
    for (int i = 0; i < values.size(); ++i) {
        if (i) output << ' ';
        output << values[i];
    }
    return output;
}

template<class Stream, class A, class B>
Stream& operator<<(Stream& output, const vec<std::pair<A, B>>& values) {
    for (int i = 0; i < values.size(); ++i) {
        if (i) output << ' ';
        output << '(' << values[i].first << ',' << values[i].second << ')';
    }
    return output;
}

// ---- end templa/vec.hpp ----
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i128 = __int128_t;
using u128 = __uint128_t;

constexpr int inf = 1 << 30;
constexpr ll INF = 1LL << 60;
constexpr ll LINF = 0x1fffffffffffffffLL;
constexpr ll MINF = 0x7fffffffffffLL;
constexpr int MOD = 1'000'000'007;
constexpr int MODD = 998'244'353;

template <class A, class B>
bool chmax(A& a, const B& b) { return b > a ? (a = b, true) : false; }
template <class A, class B>
bool chmin(A& a, const B& b) { return b < a ? (a = b, true) : false; }

#define sz(x) ((long long)(x).size())
// rep supports rep(n), rep(i,n), rep(i,l,r), and rep(i,l,r,step).
// 中文：rep 支持 rep(n)、rep(i,n)、rep(i,l,r) 和 rep(i,l,r,step) 四种循环形式。
#define CP_REP1(n) for (ll _ = 0; _ < (n); ++_)
#define CP_REP2(i, n) for (ll i = 0; i < (n); ++i)
#define CP_REP3(i, a, b) for (ll i = (a); i < (b); ++i)
#define CP_REP4(i, a, b, step) for (ll i = (a); i < (b); i += (step))
#define CP_REP_SELECT(_1, _2, _3, _4, NAME, ...) NAME
#define rep(...) CP_REP_SELECT(__VA_ARGS__, CP_REP4, CP_REP3, CP_REP2, CP_REP1)(__VA_ARGS__)
#define Rep(i, a, b) for (ll i = (a); i < (b); ++i)
// rrep supports rrep(n), rrep(i,n), and rrep(i,l,r), over half-open ranges.
// 中文：rrep 支持 rrep(n)、rrep(i,n) 和 rrep(i,l,r)，循环范围按左闭右开处理。
#define CP_RREP1(n) for (ll _ = (n); _-- > 0; )
#define CP_RREP2(i, n) for (ll i = (n); i-- > 0; )
#define CP_RREP3(i, a, b) for (ll i = (b); i-- > (a); )
#define CP_RREP_SELECT(_1, _2, _3, NAME, ...) NAME
#define rrep(...) CP_RREP_SELECT(__VA_ARGS__, CP_RREP3, CP_RREP2, CP_RREP1)(__VA_ARGS__)
// each(range) iterates values; each(key,value,range) destructures pairs.
// 中文：each(range) 遍历元素；each(key,value,range) 可解构遍历键值对。
#define CP_EACH1(i, range) for (auto&& i : range)
#define CP_EACH2(x, y, range) for (auto&& [x, y] : range)
#define CP_EACH3(x, y, z, range) for (auto&& [x, y, z] : range)
#define CP_EACH4(w, x, y, z, range) for (auto&& [w, x, y, z] : range)
#define CP_EACH_SELECT(_1, _2, _3, _4, _5, NAME, ...) NAME
#define each(...) CP_EACH_SELECT(__VA_ARGS__, CP_EACH4, CP_EACH3, CP_EACH2, CP_EACH1)(__VA_ARGS__)
#define CP_ALL1(c) begin(c), end(c)
#define CP_ALL2(c, n) begin(c), begin(c) + (n)
#define CP_ALL3(c, l, r) begin(c) + (l), begin(c) + (r)
#define CP_ALL_SELECT(_1, _2, _3, NAME, ...) NAME
#define all(...) CP_ALL_SELECT(__VA_ARGS__, CP_ALL3, CP_ALL2, CP_ALL1)(__VA_ARGS__)
#define CP_RALL1(c) rbegin(c), rend(c)
#define CP_RALL2(c, n) rbegin(c), rbegin(c) + (n)
#define CP_RALL3(c, l, r) rbegin(c) + (l), rbegin(c) + (r)
#define rall(...) CP_ALL_SELECT(__VA_ARGS__, CP_RALL3, CP_RALL2, CP_RALL1)(__VA_ARGS__)
#define sum(...) accumulate(all(__VA_ARGS__), 0LL)
#define dsum(...) accumulate(all(__VA_ARGS__), 0.0L)
#define Msum(...) accumulate(all(__VA_ARGS__), mint{})
#define elif else if
#define fst first
#define snd second
#define pb push_back
#define em emplace_back
#define is insert
#define el '\n'

template<class T> using V = vec<T>;
template<class T, size_t N> using AR = array<T, N>;
template<class T> using v = vector<T>;
template<class T, size_t N> using a = array<T, N>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;

namespace cp_detail {
template<class T, class = void> struct is_iterable : false_type {};
template<class T> struct is_iterable<T, void_t<decltype(begin(declval<const T&>())),
                                                decltype(end(declval<const T&>()))>> : true_type {};
template<class T, class = void> struct is_tuple_like : false_type {};
template<class T> struct is_tuple_like<T, void_t<decltype(tuple_size<decay_t<T>>::value)>> : true_type {};
template<class T> struct is_pair : false_type {};
template<class A, class B> struct is_pair<pair<A, B>> : true_type {};
template<class T, class = void> struct is_input_streamable : false_type {};
template<class T> struct is_input_streamable<T, void_t<decltype(declval<istream&>() >> declval<T&>())>> : true_type {};

template<class T, enable_if_t<!is_iterable<T>::value && !is_pair<T>::value && !is_tuple_like<T>::value, int> = 0>
void print_debug(const T& x) { cerr << x; }
inline void print_debug(const string& x) { cerr << '"' << x << '"'; }
inline void print_debug(const char* x) { cerr << '"' << x << '"'; }
inline void print_debug(char x) { cerr << '\'' << x << '\''; }
inline void print_debug(bool x) { cerr << (x ? "true" : "false"); }
template<class A, class B> void print_debug(const pair<A, B>& p) {
  cerr << '('; print_debug(p.first); cerr << ", "; print_debug(p.second); cerr << ')';
}
template<class T, enable_if_t<is_tuple_like<T>::value && !is_pair<T>::value, int> = 0>
void print_debug(const T& value);
template<class T, enable_if_t<is_iterable<T>::value && !is_tuple_like<T>::value, int> = 0>
void print_debug(const T& xs) {
  cerr << '['; bool first = true;
  for (const auto& x : xs) { if (!first) cerr << ", "; first = false; print_debug(x); }
  cerr << ']';
}
template<class T, size_t... I>
void print_debug_tuple(const T& value, index_sequence<I...>) {
  cerr << '(';
  bool first = true;
  ((first ? (first = false, void()) : (cerr << ", ", void()),
    print_debug(get<I>(value))), ...);
  cerr << ')';
}
template<class T, enable_if_t<is_tuple_like<T>::value && !is_pair<T>::value, int>>
void print_debug(const T& value) {
  print_debug_tuple(value, make_index_sequence<tuple_size<decay_t<T>>::value>{});
}

/** @brief Recursively reads scalars, pairs, tuples, arrays, and nested containers.
 * 中文：递归读取标量、pair、tuple、数组和嵌套容器。 */
template<class T> void read_one(T& value) {
  using U = decay_t<T>;
  if constexpr (is_same_v<U, string> || is_input_streamable<T>::value) {
    cin >> value;
  } else if constexpr (is_same_v<U, vector<bool>>) {
    for (auto&& bit : value) { bool x; read_one(x); bit = x; }
  } else if constexpr (is_pair<U>::value) {
    read_one(value.first); read_one(value.second);
  } else if constexpr (is_tuple_like<U>::value) {
    apply([](auto&... xs) { (read_one(xs), ...); }, value);
  } else if constexpr (is_iterable<U>::value) {
    for (auto&& item : value) read_one(item);
  } else {
    static_assert(is_input_streamable<T>::value, "type cannot be read by rd/in");
  }
}

/** @brief Recursively prints scalars, pairs, tuples, and containers separated by spaces.
 * 中文：递归输出标量、pair、tuple 和容器，各元素以空格分隔。 */
template<class T> void write_one(const T& value);
template<class T, size_t... I>
void write_tuple(const T& value, index_sequence<I...>) {
  bool first = true;
  ((first ? (first = false, void()) : (cout << ' ', void()),
    write_one(get<I>(value))), ...);
}
template<class T> void write_one(const T& value) {
  using U = decay_t<T>;
  if constexpr (is_same_v<U, string>) {
    cout << value;
  } else if constexpr (is_tuple_like<U>::value) {
    write_tuple(value, make_index_sequence<tuple_size<U>::value>{});
  } else if constexpr (is_iterable<U>::value && !is_same_v<U, string>) {
    bool first = true;
    for (const auto& item : value) {
      if (!first) cout << ' ';
      first = false;
      write_one(item);
    }
  } else {
    cout << value;
  }
}
template<class... Ts> void debug_values(const char* names, const Ts&... xs) {
  cerr << "\033[33m[debug] " << names << " = ";
  bool first = true;
  ((first ? (first = false, void()) : (cerr << " | ", void()), print_debug(xs)), ...);
  cerr << "\033[0m\n";
}
}

#ifdef DEBUG
#define debug(...) do { cp_detail::debug_values(#__VA_ARGS__, __VA_ARGS__); } while (0)
#else
#define debug(...) ((void)0)
#endif
#define dbg(...) debug(__VA_ARGS__)
#define as(...) assert(__VA_ARGS__)

/// @brief Defines yes/no output helpers named after the two arguments.
/// 中文：定义以两个参数命名的 yes/no 输出函数。
#define YESNO(yes_name, no_name) \
  inline void yes_name(bool value = true) { out(value ? #yes_name : #no_name); } \
  inline void no_name() { out(#no_name); }

/** @brief Reads one or more values; vectors, arrays, pairs, and tuples recurse elementwise.
 * 中文：读取一个或多个值；vector、数组、pair 和 tuple 会递归读取各元素。 */
template<class... Ts> void rd(Ts&... xs) { (cp_detail::read_one(xs), ...); }
/// @brief Alias for rd, matching the compact input style used by contest templates.
/// 中文：rd 的别名，采用竞赛模板常用的简短输入写法。
template<class... Ts> void in(Ts&... xs) { rd(xs...); }
template<class... Ts> void wt(const Ts&... xs) {
  bool first = true;
  ((first ? (first = false, void()) : (cout << ' ', void()), cp_detail::write_one(xs)), ...);
  cout << '\n';
}
/// @brief Alias for wt: prints values separated by spaces and appends a newline.
/// 中文：wt 的别名：各值以空格分隔，并在末尾换行。
template<class... Ts> void out(const Ts&... xs) { wt(xs...); }

YESNO(first, second)
YESNO(First, Second)
YESNO(Yes, No)
YESNO(YES, NO)
YESNO(possible, impossible)
YESNO(Possible, Impossible)
YESNO(POSSIBLE, IMPOSSIBLE)

// Declare scalar variables and read them in one statement.
// 中文：在一条语句中声明标量变量并读入。
#define INT(...) int __VA_ARGS__; rd(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; rd(__VA_ARGS__)
#define ULL(...) ull __VA_ARGS__; rd(__VA_ARGS__)
#define STR(...) string __VA_ARGS__; rd(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__; rd(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__; rd(__VA_ARGS__)
#define LD(...) ld __VA_ARGS__; rd(__VA_ARGS__)
/// @brief Declares a vector initialized with constructor arguments; does not read input.
/// 中文：声明并按构造参数初始化 vector；不会读取输入。
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
/// @brief Declares a fixed-size array value-initialized to zero/default values.
/// 中文：声明固定长度数组，并用零值/默认值初始化。
#define arr(type, name, size) array<type, size> name{}
/// @brief Declares an n-element vector and reads every element from input.
/// 中文：声明含 n 个元素的 vector，并读取所有元素。
#define VEC(type, name, n) vec<type> name(n); rd(name)
/// @brief Declares a fixed-size array and recursively reads its elements.
/// 中文：声明固定长度数组，并递归读取其中元素。
#define ARR(type, name, n) array<type, n> name{}; rd(name)
/// @brief Declares a 2D vector initialized with the given fill value; does not read input.
/// 中文：声明并按给定填充值初始化二维 vector；不会读取输入。
#define vv(type, name, h, ...) vec<vec<type>> name(h, vec<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vec<vec<vec<type>>> name(h, vec<vec<type>>(w, vec<type>(__VA_ARGS__)))
/// @brief Declares an h-by-w 2D vec and recursively reads every element.
/// 中文：声明 h×w 二维 vec，并递归读取所有元素。
#define VV(type, name, h, w) vec<vec<type>> name(h, vec<type>(w)); rd(name)
/// @brief Declares an h-by-w-by-d 3D vec and recursively reads every element.
/// 中文：声明 h×w×d 三维 vec，并递归读取所有元素。
#define VVV(type, name, h, w, d) vec<vec<vec<type>>> name(h, vec<vec<type>>(w, vec<type>(d))); rd(name)

constexpr ll debug_const(ll judge_value, ll debug_value) {
#ifdef DEBUG
  return debug_value;
#else
  return judge_value;
#endif
}

#endif  // CP_TEMPLA_BASE_HPP

// ---- end templa/base.hpp ----
// ---- begin templa/common.hpp ----

/**
 * @file common.hpp
 * @brief Common precomputation and search helpers.
 * 中文：常用预处理与搜索工具。
 * @details Include with #include "templa/common.hpp". Names are placed in
 * 中文：通过 #include "templa/common.hpp" 引入；函数放在
 * namespace cp to avoid collisions with standard-library algorithms.
 * 中文：cp 命名空间中，以避免与标准库算法重名。
 */
namespace cp {

/**
 * @brief Finds the last/first boundary of a monotone predicate on integers.
 * 中文：在整数范围内二分查找单调谓词的边界。
 * @param check Predicate that is true at ok and false at ng.
 * 中文：谓词 check 在 ok 处为真，在 ng 处为假。
 * @param ok Known true endpoint; @param ng known false endpoint.
 * 中文：ok 是已知为真的端点；ng 是已知为假的端点。
 * @details Returns ok when endpoints are adjacent. The endpoint order may be
 * 中文：当两端点相邻时返回 ok；端点顺序可以
 * increasing or decreasing. Set check_ok=false to skip the debug assertion.
 * 中文：递增或递减。设置 check_ok=false 可跳过调试断言。
 */
template<class Check>
ll binary_search(Check check, ll ok, ll ng, bool check_ok = true) {
    if (check_ok) assert(check(ok) && !check(ng));
    while ((i128)ok - ng > 1 || (i128)ng - ok > 1) {
        ll mid = std::midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return ok;
}

/**
 * @brief Binary search on a monotone predicate over real numbers.
 * 中文：在实数范围内对单调谓词执行二分搜索。
 * @param check Predicate true at ok and false at ng.
 * 中文：谓词 check 在 ok 处为真，在 ng 处为假。
 * @param iterations Number of bisection steps; defaults to 100.
 * 中文：二分迭代次数，默认 100 次。
 */
template<class Check>
double binary_search_real(Check check, double ok, double ng, int iterations = 100) {
    assert(check(ok) && !check(ng));
    while (iterations--) {
        double mid = std::midpoint(ok, ng);
        (check(mid) ? ok : ng) = mid;
    }
    return std::midpoint(ok, ng);
}

/**
 * @brief Returns the insertion index from lower_bound on a sorted range.
 * 中文：在已排序区间上执行 lower_bound，并返回插入位置的下标。
 * @details LB(v, x) is equivalent to lower_bound(begin(v), end(v), x) - begin(v).
 * 中文：LB(v, x) 等价于 lower_bound(begin(v), end(v), x) - begin(v)。
 */
template<class Range, class T, class Compare = less<>>
ll LB(const Range& values, const T& target, Compare compare = Compare{}) {
    return lower_bound(begin(values), end(values), target, compare) - begin(values);
}

/**
 * @brief Returns the insertion index from upper_bound on a sorted range.
 * 中文：在已排序区间上执行 upper_bound，并返回插入位置的下标。
 * @details UB(v, x) is equivalent to upper_bound(begin(v), end(v), x) - begin(v).
 * 中文：UB(v, x) 等价于 upper_bound(begin(v), end(v), x) - begin(v)。
 */
template<class Range, class T, class Compare = less<>>
ll UB(const Range& values, const T& target, Compare compare = Compare{}) {
    return upper_bound(begin(values), end(values), target, compare) - begin(values);
}

/**
 * @brief Builds prefix sums from a range.
 * 中文：根据一个区间构造前缀和。
 * @param leading_zero If true, result has n+1 elements and result[0] is zero.
 * 中文：为 true 时，结果长度为 n+1，且 result[0] 为零。
 * If false, result[i] is the inclusive prefix through input[i].
 * 中文：为 false 时，result[i] 是截至 input[i]（含该项）的前缀和。
 */
template<class Range>
auto cumsum(const Range& values, bool leading_zero = true) {
    using T = decay_t<decltype(*begin(values))>;
    vector<T> prefix;
    if (leading_zero) prefix.emplace_back(T{});
    for (const auto& value : values) {
        prefix.push_back((prefix.empty() ? T{} : prefix.back()) + value);
    }
    return prefix;
}

/** @brief Sorts a vector and removes duplicate values.
 * 中文：对 vector 排序并删除重复值。 */
template<class T, class Compare = less<>>
void sort_unique(vector<T>& values, Compare compare = Compare{}) {
    sort(values.begin(), values.end(), compare);
    values.erase(unique(values.begin(), values.end()), values.end());
}

/**
 * @brief Run-length encodes consecutive equal values.
 * 中文：对连续相同的值进行游程编码。
 * @return Pairs of {value, run length}, preserving input order.
 * 中文：返回 {值, 连续长度}，并保持原有顺序。
 */
template<class Range>
auto run_length_encode(const Range& values) {
    using T = decay_t<decltype(*begin(values))>;
    vector<pair<T, ll>> result;
    for (const auto& value : values) {
        if (result.empty() || result.back().first != value) result.emplace_back(value, 1);
        else ++result.back().second;
    }
    return result;
}

/**
 * @brief Coordinate-compresses values.
 * 中文：对数值进行坐标压缩。
 * @return {sorted unique values, rank for each input element}.
 * 中文：返回 {排序去重后的值, 每个输入元素对应的排名}。
 */
template<class Range>
auto coordinate_compress(const Range& input) {
    using T = decay_t<decltype(*begin(input))>;
    vector<T> values(begin(input), end(input));
    sort_unique(values);
    vector<ll> rank;
    rank.reserve(values.size());
    for (const auto& x : input)
        rank.push_back(lower_bound(values.begin(), values.end(), x) - values.begin());
    return pair<vector<T>, vector<ll>>(move(values), move(rank));
}

/** @brief Counts values equal to target in a range.
 * 中文：统计区间中等于 target 的元素个数。 */
template<class Range, class Value>
ll count_value(const Range& values, const Value& target) {
    return count(begin(values), end(values), target);
}

/** @brief Counts elements satisfying predicate.
 * 中文：统计满足 predicate 的元素个数。 */
template<class Range, class Predicate>
ll count_if_value(const Range& values, Predicate predicate) {
    return count_if(begin(values), end(values), move(predicate));
}

/** @brief Erases all elements satisfying predicate from a sequence container.
 * 中文：从序列容器中删除所有满足 predicate 的元素。 */
template<class Sequence, class Predicate>
void filter_inplace(Sequence& values, Predicate predicate) {
    values.erase(remove_if(values.begin(), values.end(), move(predicate)), values.end());
}

/** @brief Creates [first, first+n) as a vector of long long values.
 * 中文：创建内容为 [first, first+n) 的 long long 向量。 */
inline vector<ll> iota_vector(ll n, ll first = 0) {
    vector<ll> values(n);
    iota(values.begin(), values.end(), first);
    return values;
}

/** @brief Removes and returns the first value of a deque. Requires nonempty input.
 * 中文：移除并返回 deque 的首元素；容器必须非空。 */
template<class T>
T pop(deque<T>& values) {
    T result = move(values.front());
    values.pop_front();
    return result;
}

/** @brief Removes and returns the top value of a priority queue. Requires nonempty input.
 * 中文：移除并返回优先队列的队首元素；容器必须非空。 */
template<class T, class Container, class Compare>
T pop(priority_queue<T, Container, Compare>& values) {
    T result = values.top();
    values.pop();
    return result;
}

/** @brief Removes and returns the last value of a vector. Requires nonempty input.
 * 中文：移除并返回 vector 的末尾元素；容器必须非空。 */
template<class T>
T pop(vector<T>& values) {
    T result = move(values.back());
    values.pop_back();
    return result;
}

/** @brief Removes and returns the top value of a stack. Requires nonempty input.
 * 中文：移除并返回栈顶元素；容器必须非空。 */
template<class T>
T pop(stack<T>& values) {
    T result = values.top();
    values.pop();
    return result;
}

/** @brief Returns floor(a/b), rounding toward negative infinity; requires b != 0.
 * 中文：返回 floor(a/b)，即向负无穷方向取整；要求 b != 0。 */
template<class T>
T floor_div(T a, T b) {
    T q = a / b, r = a % b;
    if (r != 0 && ((a < 0) != (b < 0))) --q;
    return q;
}

/** @brief Returns ceil(a/b), rounding toward positive infinity; requires b != 0.
 * 中文：返回 ceil(a/b)，即向正无穷方向取整；要求 b != 0。 */
template<class T>
T ceil_div(T a, T b) {
    T q = a / b, r = a % b;
    if (r != 0 && ((a < 0) == (b < 0))) ++q;
    return q;
}

/** @brief Computes a^exponent modulo mod; requires exponent >= 0 and mod > 0.
 * 中文：计算 a^exponent mod mod；要求 exponent >= 0 且 mod > 0。 */
inline ll mod_pow(ll a, ll exponent, ll mod) {
    assert(mod > 0 && exponent >= 0);
    a %= mod;
    if (a < 0) a += mod;
    ll result = 1 % mod;
    while (exponent > 0) {
        if (exponent & 1) result = (i128)result * a % mod;
        a = (i128)a * a % mod;
        exponent >>= 1;
    }
    return result;
}

/** @brief Returns prime factors as {prime, exponent}; n must be positive.
 * 中文：返回格式为 {质因数, 指数} 的分解结果；n 必须为正数。 */
inline vector<pair<ll, ll>> factorize(ll n) {
    assert(n > 0);
    vector<pair<ll, ll>> factors;
    for (ll p = 2; p <= n / p; ++p) {
        if (n % p != 0) continue;
        ll exponent = 0;
        do { n /= p; ++exponent; } while (n % p == 0);
        factors.emplace_back(p, exponent);
    }
    if (n > 1) factors.emplace_back(n, 1);
    return factors;
}

/** @brief Returns all positive divisors of n in increasing order; n must be positive.
 * 中文：按升序返回 n 的所有正因数；n 必须为正数。 */
inline vector<ll> divisors(ll n) {
    assert(n > 0);
    vector<ll> result;
    for (ll d = 1; d <= n / d; ++d) {
        if (n % d != 0) continue;
        result.push_back(d);
        if (d != n / d) result.push_back(n / d);
    }
    sort(result.begin(), result.end());
    return result;
}

/** @brief Returns a boolean sieve where result[x] indicates whether x is prime.
 * 中文：返回布尔筛，result[x] 表示 x 是否为质数。 */
inline vector<bool> prime_sieve(int n) {
    assert(n >= 0);
    vector<bool> prime(n + 1, true);
    if (n >= 0) prime[0] = false;
    if (n >= 1) prime[1] = false;
    for (ll p = 2; p <= n / p; ++p)
        if (prime[p]) for (ll x = p * p; x <= n; x += p) prime[x] = false;
    return prime;
}

}  // namespace cp

// ---- end templa/common.hpp ----
// ---- begin templa/dynamic_modint.hpp ----

/**
 * @brief Runtime-modulus modular integer type.
 * 中文：运行期模数的模整数类型。
 * @details Call dynamic_modint<id>::set_mod(mod) before constructing values; each id has an independent modulus.
 * 中文：构造模整数前调用 dynamic_modint<id>::set_mod(mod)；每个 id 使用独立模数。
 */
template<int id> class dynamic_modint {
    using mint = dynamic_modint;
    struct barrett {
        uint32_t _m;
        uint64_t im;
        barrett(uint32_t mod) : _m(mod), im(uint64_t(-1) / mod + 1) {}
        operator uint32_t() const { return _m; }
        uint32_t mul(uint32_t a, uint32_t b) const {
            uint64_t z = a;
            z *= b;
            uint64_t x = uint64_t(__uint128_t(z) * im >> 64);
            uint64_t y = x * _m;
            return uint32_t(z - y + (z < y ? _m : 0));
        }
    };
    static inline barrett m = 1;
    uint32_t _v = 0;
    static pair<int32_t, int32_t> inv_gcd(int32_t a, int32_t b) {
        if (a == 0) return {b, 0};
        int32_t s = b, t = a, m0 = 0, m1 = 1;
        while (t) {
            const int32_t u = s / t;
            s -= t * u; m0 -= m1 * u;
            swap(s, t); swap(m0, m1);
        }
        if (m0 < 0) m0 += b / s;
        return {s, m0};
    }
public:
    static mint raw(uint32_t v) { mint a; a._v = v; return a; }
    dynamic_modint() {}
    template <class T>
    dynamic_modint(T v) {
        static_assert(is_integral_v<T>, "T is not integral type.");
        if constexpr (is_signed_v<T>) {
            int64_t x = int64_t(v % int64_t(m));
            if (x < 0) x += m; _v = uint32_t(x);
        }
        else _v = uint32_t(v % m);
    }
    static uint32_t mod() { return m; }
    /// @brief Sets the modulus shared by every value with this template id.
    /// 中文：设置该模板 id 下所有数值共用的模数。
    static void set_mod(int mod) {
        assert(1 <= mod);
        m = mod;
    }
    uint32_t val() const { return _v; }
    mint& operator++() { return *this += 1; }
    mint& operator--() { return *this -= 1; }
    mint operator++(int) { mint res = *this; ++*this; return res; }
    mint operator--(int) { mint res = *this; --*this; return res; }
    mint& operator+=(mint rhs) {
        if (_v >= m - rhs._v) _v -= m;
        _v += rhs._v; return *this;
    }
    mint& operator-=(mint rhs) {
        if (_v < rhs._v) _v += m;
        _v -= rhs._v; return *this;
    }
    mint& operator*=(mint rhs) { return *this = *this * rhs; }
    mint& operator/=(mint rhs) { return *this *= rhs.inv(); }
    mint operator+() const { return *this; }
    mint operator-() const { return mint{} - *this; }
    /// @brief Returns this value raised to n; n must be nonnegative.
    /// 中文：返回当前值的 n 次幂；n 必须非负。
    mint pow(long long n) const {
        assert(0 <= n);
        if(n == 0) return 1;
        mint x = *this, r = 1;
        while (1) {
            if (n & 1) r *= x; n >>= 1;
            if (n == 0) return r;
            x *= x;
        }
    }
    /// @brief Returns the multiplicative inverse; the value must be nonzero.
    /// 中文：返回乘法逆元；当前值必须非零。
    mint inv() const {
        auto eg = inv_gcd(_v, m);
        assert(eg.first == 1);
        return eg.second;
    }
    friend mint operator+(mint lhs, mint rhs) { return lhs += rhs; }
    friend mint operator-(mint lhs, mint rhs) { return lhs -= rhs; }
    friend mint operator*(mint lhs, mint rhs) { return raw(m.mul(lhs._v, rhs._v)); }
    friend mint operator/(mint lhs, mint rhs) { return lhs /= rhs; }
    friend bool operator==(mint lhs, mint rhs) { return lhs._v == rhs._v; }
    friend bool operator!=(mint lhs, mint rhs) { return lhs._v != rhs._v; }
};
using mint = dynamic_modint<-1>;
istream& operator>>(istream& in, mint& x) { long long a; in >> a; x = a; return in; }
ostream& operator<<(ostream& out, mint x) { return out << x.val(); }
mint operator""_M(unsigned long long x) { return x; }

constexpr uint32_t fact_mx = 2e7;
mint fac[fact_mx + 1], inv[fact_mx + 1];
/// @brief Precomputes factorial and inverse-factorial tables up to fact_mx.
/// 中文：预处理到 fact_mx 的阶乘和逆阶乘表。
void prepare_factorial() {
    fac[0] = 1;
    for(uint32_t i = 1; i <= fact_mx; i++) fac[i] = fac[i - 1] * mint::raw(i);
    inv[fact_mx] = fac[fact_mx].inv();
    for(uint32_t i = fact_mx; i; i--) inv[i - 1] = inv[i] * mint::raw(i);
}
mint inverse(long long n) { return inv[n] * fac[n - 1]; }
mint perm(long long n, long long r) {
    if(n < r || r < 0) return 0;
    if(n > fact_mx) [[unlikely]] {
        mint ans = 1, x = n;
        while(r--) ans *= x--;
        return ans;
    }
    return fac[n] * inv[n - r];
}
/// @brief Returns n choose r, or zero when r is outside [0,n].
/// 中文：返回组合数 n 选 r；r 不在 [0,n] 时返回 0。
mint comb(long long n, long long r) {
    if(n < r || r < 0) return 0;
    r = min(r, n - r);
    const mint ans = perm(n, r);
    return ans * inv[r];
}
template<class... T> mint comb(long long n, T... rs) {
    if(n < 0) return 0;
    mint ans = fac[n];
    long long rn = n;
    for(long long r : {rs...}) {
        if(r < 0) return 0;
        ans *= inv[r];
        rn -= r;
    }
    if(rn < 0) return 0;
    return ans * inv[rn];
}
mint Mcomb(long long n, long long r){ return comb(n + r - 1, r); } // r balls into n boxes

// ---- end templa/dynamic_modint.hpp ----

// ---- begin templa/math/Geometry2D.hpp ----
#include <optional>
// ---- begin templa/math/2DPairOperators.hpp ----

/**
 * @brief Arithmetic and geometry helpers for pair-based 2D points.
 * 中文：基于 pair 表示的二维点的算术与几何工具。
 * @details Defines P<T>, vector arithmetic, dot/cross, rotation, and normalization; compatible with Geometry2D.hpp.
 * 中文：定义 P<T>、向量运算、点积与叉积、旋转和归一化；可与 Geometry2D.hpp 同时包含。
 */
template<class T> using P = pair<T, T>;
template<class T> P<T> operator+(const P<T>& a, const P<T>& b) { return {a.first + b.first, a.second + b.second}; }
template<class T> P<T> operator-(const P<T>& a, const P<T>& b) { return {a.first - b.first, a.second - b.second}; }
template<class T> P<T> operator-(const P<T>& a) { return {-a.first, -a.second}; }
template<class T, class U> P<T> operator*(const P<T>& a, const U& b) { return {a.first * b, a.second * b}; }
template<class T, class U> P<T> operator/(const P<T>& a, const U& b) { return {a.first / b, a.second / b}; }
template<class T> P<T>& operator+=(P<T>& a, const P<T>& b) { return a = a + b; }
template<class T> P<T>& operator-=(P<T>& a, const P<T>& b) { return a = a - b; }
template<class T, class U> P<T>& operator*=(P<T>& a, const U& b) { return a = a * b; }
template<class T, class U> P<T>& operator/=(P<T>& a, const U& b) { return a = a / b; }
template<class T> P<T> rotate(const P<T>& a) { return {-a.second, a.first}; } // 90 degree ccw
template<class T> T dot(const P<T>& a, const P<T>& b) { return a.first * b.first + a.second * b.second; }
template<class T> T cross(const P<T>& a, const P<T>& b) { return dot(rotate(a), b); }
template<class T> T square(const P<T>& a) { return dot(a, a); }
template<class T> ld abs(const P<T>& a) { return hypotl(a.first, a.second); }
template<class T> T gcd(const P<T>& a) { return gcd(a.first, a.second); }
template<class T> P<T> normalize(P<T> a) {
    if(a == P<T>{}) return a;
    a /= gcd(a);
    if(a < P<T>{}) a = -a;
    return a;
}

// ---- end templa/math/2DPairOperators.hpp ----

namespace cp::geo {
inline constexpr long double EPS = 1e-12L;
/** @brief Integer predicates use signed 128-bit arithmetic; floating predicates use absolute EPS.
 * 中文：整数判定使用有符号 128 位中间量；浮点判定使用绝对误差 EPS。
 * @details Integer input coordinates should satisfy |coordinate| <= 10^18; accumulated sums must also fit i128.
 * 中文：整数输入坐标要求绝对值不超过 10^18；累加结果也必须能由 i128 表示。 */
template<class T> using Wide = conditional_t<is_integral_v<T>, i128, long double>;
template<class T> int sign(T value) {
    if constexpr (is_floating_point_v<T>) return (value>EPS)-(value<-EPS);
    else return (value>0)-(value<0);
}
/** @brief 2D point/vector. Ordering and equality are exact, including floating-point sorting.
 * 中文：二维点/向量；排序和相等比较均采用精确比较，包括浮点坐标。 */
template<class T=long double> struct Point {
    T x{}, y{};
    Point() = default;
    Point(T x, T y) : x(x), y(y) {}
    Point(pair<T,T> p) : x(p.first), y(p.second) {}
    operator pair<T,T>() const { return {x,y}; }
    Point operator+(Point b) const { return {x+b.x,y+b.y}; }
    Point operator-(Point b) const { return {x-b.x,y-b.y}; }
    Point operator-() const { return {-x,-y}; }
    Point operator*(T k) const { return {x*k,y*k}; }
    Point operator/(T k) const { return {x/k,y/k}; }
    Point& operator+=(Point b) { return *this=*this+b; }
    Point& operator-=(Point b) { return *this=*this-b; }
    Point& operator*=(T k) { return *this=*this*k; }
    Point& operator/=(T k) { return *this=*this/k; }
    bool operator==(Point b) const { return x==b.x && y==b.y; }
    bool operator!=(Point b) const { return !(*this==b); }
    bool operator<(Point b) const { return x<b.x || (x==b.x && y<b.y); }
    bool operator>(Point b) const { return b<*this; }
    Point rotate() const { return {-y,x}; }
    T gcd() const { return std::gcd(x,y); }
    friend istream& operator>>(istream& in, Point& p) { return in>>p.x>>p.y; }
    friend ostream& operator<<(ostream& out, const Point& p) { return out<<p.x<<' '<<p.y; }
};
using IPoint = Point<ll>;
using FPoint = Point<long double>;
/// @brief Dot product with widened intermediate arithmetic.
/// 中文：使用宽类型中间量计算点积。
template<class T> Wide<T> dot(Point<T> a, Point<T> b) { return Wide<T>(a.x)*b.x+Wide<T>(a.y)*b.y; }
/// @brief Cross product with widened intermediate arithmetic.
/// 中文：使用宽类型中间量计算叉积。
template<class T> Wide<T> cross(Point<T> a, Point<T> b) { return Wide<T>(a.x)*b.y-Wide<T>(a.y)*b.x; }
/// @brief Signed doubled triangle area; casts before coordinate subtraction.
/// 中文：有向三角形面积的两倍，在坐标相减前转换到宽类型。
template<class T> Wide<T> cross(Point<T> a, Point<T> b, Point<T> c) {
    return (Wide<T>(b.x)-a.x)*(Wide<T>(c.y)-a.y)-(Wide<T>(b.y)-a.y)*(Wide<T>(c.x)-a.x);
}
template<class T> Wide<T> square(Point<T> p) { return dot(p,p); }

/** @brief Polar-angle comparator around origin: counterclockwise from +x, then nearer first.
 * 中文：绕 origin 的极角比较器：从正 x 轴起逆时针排序，同方向按距离从近到远。
 * @details Points equal to origin come first; equal points compare equivalent. No EPS is used.
 * 中文：与 origin 重合的点放在最前，相同点视为等价；排序中不使用 EPS。
 * Integer coordinates (including origin) must have magnitude <= 1e18; i128 predicates are exact.
 * 中文：整数点及中心坐标绝对值须不超过 1e18，使用 i128 精确比较。
 * Floating coordinates and differences must be finite. atan2l supplies a transitive angle key;
 * equal computed angles are ordered by hypotl distance, then coordinates. Very close angles may round equal.
 * 中文：浮点坐标及差值须有限；用 atan2l 构造可传递的角度键，计算角度相同则按 hypotl 距离及坐标排序；极近角度可能舍入为相同值。
 * Example: sort(a.begin(),a.end(),PolarLess<ll>{origin}); also accepts pair<T,T> points.
 * 中文：示例：sort(a.begin(),a.end(),PolarLess<ll>{origin})；也支持 pair<T,T> 点。 */
template<class T> struct PolarLess {
    Point<T> origin{};
    bool operator()(Point<T> a, Point<T> b) const {
        Wide<T> ax=Wide<T>(a.x)-origin.x, ay=Wide<T>(a.y)-origin.y;
        Wide<T> bx=Wide<T>(b.x)-origin.x, by=Wide<T>(b.y)-origin.y;
        if constexpr (is_floating_point_v<T>)
            assert(isfinite(ax) && isfinite(ay) && isfinite(bx) && isfinite(by));
        bool az=ax==0 && ay==0, bz=bx==0 && by==0;
        if(az || bz) return az && !bz;
        int ah=(ay<0 || (ay==0 && ax<0)), bh=(by<0 || (by==0 && bx<0));
        if(ah!=bh) return ah<bh;
        if constexpr (is_integral_v<T>) {
            auto turn=ax*by-ay*bx;
            if(turn!=0) return turn>0;
            return ax*ax+ay*ay < bx*bx+by*by;
        } else {
            long double aa=atan2l(ay,ax), ba=atan2l(by,bx);
            // Normalize signed zero so the negative x axis always has angle +pi.
            // 中文：统一带符号零，负 x 轴的角度始终为 +pi。
            if(ay==0 && ax<0) aa=acosl(-1.0L);
            if(by==0 && bx<0) ba=acosl(-1.0L);
            if(aa!=ba) return aa<ba;
            long double ad=hypotl(ax,ay), bd=hypotl(bx,by);
            if(ad!=bd) return ad<bd;
            return a<b;
        }
    }
};

/** @brief Sorts points in place by PolarLess<T>, O(n log n); origin defaults to (0,0).
 * 中文：使用 PolarLess<T> 原地极角排序，O(n log n)，默认中心为 (0,0)。
 * @details Zero-based containers; zero vectors first, then CCW angles in [0,2pi), nearer first on a ray.
 * 中文：容器下标从 0 开始；零向量在前，其余按 [0,2pi) 逆时针排序，同射线按距离升序。 */
template<class T> void polar_sort(vector<Point<T>>& points, Point<T> origin={}) {
    sort(points.begin(),points.end(),PolarLess<T>{origin});
}
/// @brief Pair-point overload with the same polar order. / pair 点的极角排序重载，排序约定相同。
template<class T> void polar_sort(vector<pair<T,T>>& points, pair<T,T> origin={}) {
    sort(points.begin(),points.end(),PolarLess<T>{Point<T>(origin)});
}
/// @brief In-place polar sort for vec/V points; no vector copy. / vec/V 点的原地极角排序，不复制容器。
template<class T> void polar_sort(vec<Point<T>>& points, Point<T> origin={}) {
    polar_sort(points.as_vector(), origin);
}
/// @brief In-place polar sort for vec/V pair points. / vec/V 中 pair 点的原地极角排序。
template<class T> void polar_sort(vec<pair<T,T>>& points, pair<T,T> origin={}) {
    polar_sort(points.as_vector(), origin);
}

template<class T> Wide<T> distance2(Point<T> a, Point<T> b) {
    Wide<T> dx=Wide<T>(a.x)-b.x, dy=Wide<T>(a.y)-b.y; return dx*dx+dy*dy;
}
template<class T> long double abs(Point<T> p) { return hypotl((long double)p.x,(long double)p.y); }
template<class T> long double distance(Point<T> a, Point<T> b) { return sqrtl((long double)distance2(a,b)); }
/// @brief Orientation: +1 counterclockwise, -1 clockwise, 0 collinear.
/// 中文：方向判定：逆时针 +1，顺时针 -1，共线 0。
template<class T> int orientation(Point<T> a, Point<T> b, Point<T> c) { return sign(cross(a,b,c)); }
/** @brief Legacy five-way ccw: +1/-1 turns, +2 behind a, -2 beyond b, 0 on segment.
 * 中文：兼容五值 ccw：+1/-1 表示转向，+2 在 a 后方，-2 超出 b，0 在线段上。 */
template<class T> int ccw(Point<T> a, Point<T> b, Point<T> c) {
    int turn=orientation(a,b,c); if(turn) return turn;
    Wide<T> bx=Wide<T>(b.x)-a.x, by=Wide<T>(b.y)-a.y;
    Wide<T> cx=Wide<T>(c.x)-a.x, cy=Wide<T>(c.y)-a.y;
    if(sign(bx*cx+by*cy)<0) return 2;
    if(sign(cx*cx+cy*cy-bx*bx-by*by)>0) return -2;
    return 0;
}
/// @brief Integer direction normalization; zero remains zero and the first nonzero coordinate is positive.
/// 中文：整数方向归一化；零向量保持为零，第一个非零坐标取正。
template<class T> Point<T> normalize(Point<T> p) {
    static_assert(is_integral_v<T>);
    if(p==Point<T>{}) return p;
    p/=std::gcd(p.x,p.y); if(p<Point<T>{}) p=-p; return p;
}
/** @brief Infinite line through distinct points a,b.
 * 中文：经过不同两点 a、b 的无限直线。 */
template<class T=long double> struct Line { Point<T> a,b; };
/** @brief Closed segment; identical endpoints are allowed.
 * 中文：闭线段，允许两个端点重合。 */
template<class T=long double> struct Segment { Point<T> a,b; };
template<class T> bool parallel(const Line<T>& a,const Line<T>& b) { return sign(cross(a.b-a.a,b.b-b.a))==0; }
template<class T> bool orthogonal(const Line<T>& a,const Line<T>& b) { return sign(dot(a.b-a.a,b.b-b.a))==0; }
template<class T> bool intersect(const Line<T>& l,Point<T> p) { return orientation(l.a,l.b,p)==0; }
template<class T> bool intersect(const Line<T>& a,const Line<T>& b) { return !parallel(a,b) || intersect(a,b.a); }
/// @brief Tests membership in a closed segment, including a point segment.
/// 中文：判断点是否在闭线段上，支持退化为一个点的线段。
template<class T> bool intersect(const Segment<T>& s,Point<T> p) {
    if(orientation(s.a,s.b,p)) return false;
    return sign((Wide<T>(p.x)-s.a.x)*(Wide<T>(p.x)-s.b.x)+(Wide<T>(p.y)-s.a.y)*(Wide<T>(p.y)-s.b.y))<=0;
}
/// @brief Tests intersection of an infinite line and a closed segment.
/// 中文：判断无限直线与闭线段是否相交。
template<class T> bool intersect(const Line<T>& l,const Segment<T>& s) {
    return orientation(l.a,l.b,s.a)*orientation(l.a,l.b,s.b)<=0;
}
/// @brief Tests closed-segment intersection, including overlap and degenerate endpoints.
/// 中文：判断闭线段相交，支持重叠及退化端点。
template<class T> bool intersect(const Segment<T>& a,const Segment<T>& b) {
    int x=orientation(a.a,a.b,b.a),y=orientation(a.a,a.b,b.b);
    int z=orientation(b.a,b.b,a.a),w=orientation(b.a,b.b,a.b);
    if(!x && intersect(a,b.a)) return true;
    if(!y && intersect(a,b.b)) return true;
    if(!z && intersect(b,a.a)) return true;
    if(!w && intersect(b,a.b)) return true;
    return x*y<0 && z*w<0;
}
template<class T> FPoint to_float(Point<T> p) { return {(long double)p.x,(long double)p.y}; }
/// @brief Unique line intersection; parallel or coincident lines return nullopt.
/// 中文：求两直线的唯一交点；平行或重合返回 nullopt。
template<class T> optional<FPoint> line_intersection(const Line<T>& a,const Line<T>& b) {
    if(parallel(a,b)) return nullopt;
    FPoint p=to_float(a.a),d=to_float(a.b)-p,q=to_float(b.a),e=to_float(b.b)-q;
    return p+d*(cross(q-p,e)/cross(d,e));
}
/// @brief Orthogonal projection onto a nondegenerate line.
/// 中文：求点在非退化直线上的垂足。
template<class T> FPoint projection(const Line<T>& l,Point<T> p) {
    FPoint a=to_float(l.a),d=to_float(l.b)-a; assert(square(d)>0);
    return a+d*(dot(to_float(p)-a,d)/square(d));
}
/// @brief Shortest distance from a point to a closed segment.
/// 中文：求点到闭线段的最短距离。
template<class T> long double distance(const Segment<T>& s,Point<T> p) {
    FPoint a=to_float(s.a),d=to_float(s.b)-a,q=to_float(p);
    if(square(d)==0) return distance(a,q);
    long double t=clamp(dot(q-a,d)/square(d),0.0L,1.0L); return distance(a+d*t,q);
}
/// @brief Shortest distance between two closed segments.
/// 中文：求两条闭线段的最短距离。
template<class T> long double distance(const Segment<T>& a,const Segment<T>& b) {
    if(intersect(a,b)) return 0;
    return min({distance(a,b.a),distance(a,b.b),distance(b,a.a),distance(b,a.b)});
}
} // namespace cp::geo

// ---- end templa/math/Geometry2D.hpp ----
// ---- begin templa/math/IntegralGeometry.hpp ----

/** @brief Compatibility aliases for integer geometry; predicates use i128 intermediates.
 * 中文：整数几何的兼容别名；几何判定使用 i128 中间量。
 * @details Coordinates must have absolute value <= 10^18. Infinite lines need distinct endpoints.
 * 中文：坐标绝对值要求不超过 10^18；无限直线必须由不同端点定义。 */
using Real = ld;
using R = ll;
using Point = cp::geo::IPoint;
using Line = cp::geo::Line<ll>;
using Segment = cp::geo::Segment<ll>;
using cp::geo::dot;
using cp::geo::cross;
using cp::geo::square;
using cp::geo::abs;
using cp::geo::distance;
using cp::geo::ccw;
using cp::geo::normalize;
using cp::geo::PolarLess;
using cp::geo::polar_sort;
using cp::geo::parallel;
using cp::geo::orthogonal;
using cp::geo::intersect;

// ---- end templa/math/IntegralGeometry.hpp ----

typedef mint mm;
#define REP rep
#define RREP rrep

bool __multi__ = true;

namespace XK {
void INIT();

namespace root64 {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll mul(ll a, ll b, ll mod) {
  return (i128)a * b % mod;
}

ll inverse(ll a, ll mod) {
  if (mod == 1) return 0;
  ll b = mod;
  i128 x = 1, y = 0;
  while (b) {
    ll q = a / b;
    ll r = a % b;
    a = b;
    b = r;
    i128 next = x - (i128)q * y;
    x = y;
    y = next;
  }
  assert(a == 1);
  x %= mod;
  if (x < 0) x += mod;
  return (ll)x;
}

bool is_prime(ll n) {
  if (n < 2) return false;
  for (ll q : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
    if (n % q == 0) return n == q;
  }

  ll d = n - 1;
  int s = 0;
  while (d % 2 == 0) d /= 2, ++s;

  for (ll base : {2LL, 325LL, 9375LL, 28178LL, 450775LL,
                  9780504LL, 1795265022LL}) {
    if (base % n == 0) continue;
    ll x = cp::mod_pow(base, d, n);
    if (x == 1 || x == n - 1) continue;

    bool passed = false;
    rep(i, 1, s) {
      x = mul(x, x, n);
      if (x == n - 1) {
        passed = true;
        break;
      }
    }
    if (!passed) return false;
  }
  return true;
}

ll pollard_rho(ll n) {
  if (n % 2 == 0) return 2;
  if (n % 3 == 0) return 3;

  while (true) {
    ll c = rng() % (n - 1) + 1;
    ll y = rng() % (n - 1) + 1;
    auto next = [&](ll x) { return (mul(x, x, n) + c) % n; };

    ll g = 1, length = 1, x = 0, saved = 0;
    while (g == 1) {
      x = y;
      rep(i, length) y = next(y);

      for (ll offset = 0; offset < length && g == 1; offset += 128) {
        saved = y;
        ll product = 1;
        ll count = min(128LL, length - offset);
        rep(i, count) {
          y = next(y);
          product = mul(product, x > y ? x - y : y - x, n);
        }
        g = gcd(product, n);
      }
      length *= 2;
    }

    if (g == n) {
      do {
        saved = next(saved);
        g = gcd(x > saved ? x - saved : saved - x, n);
      } while (g == 1);
    }
    if (g != n) return g;
  }
}

void factor(ll n, V<ll>& factors) {
  if (n == 1) return;
  if (is_prime(n)) {
    factors.push(n);
    return;
  }
  ll d = pollard_rho(n);
  factor(d, factors);
  factor(n / d, factors);
}

// Given that a is a q^e-th power, return one q^e-th root.
ll prime_power_root(ll a, ll q, int e, ll p) {
  ll s = p - 1;
  V<ll> qpow{1};
  while (s % q == 0) {
    s /= q;
    qpow.push(qpow.back() * q);
  }
  int t = qpow.size() - 1;
  ll degree = qpow[e];

  ll u = degree - inverse(s % degree, degree);
  ll exponent = (ll)(((i128)s * u + 1) / degree);
  ll result = cp::mod_pow(a, exponent, p);
  ll error = cp::mod_pow(a, (ll)((i128)s * u), p);
  if (error == 1) return result;

  // This branch requires t > e, hence q^2 divides p - 1.
  ll candidate;
  do {
    candidate = rng() % (p - 2) + 2;
  } while (cp::mod_pow(candidate, (p - 1) / q, p) == 1);

  ll generator = cp::mod_pow(candidate, s, p);
  ll h = cp::mod_pow(generator, degree, p);
  ll base = cp::mod_pow(generator, qpow[t - 1], p);

  // Discrete logarithms in the subgroup of prime order q.
  ll block = sqrtl(q);
  while (block * block < q) ++block;
  unordered_map<ll, ll> baby;
  baby.max_load_factor(0.7);
  baby.reserve(block);

  ll value = 1;
  rep(j, block) {
    baby.emplace(value, j);
    value = mul(value, base, p);
  }
  ll step = cp::mod_pow(cp::mod_pow(base, block, p), p - 2, p);

  auto digit_log = [&](ll target) -> ll {
    rep(i, block + 1) {
      auto it = baby.find(target);
      if (it != baby.end()) {
        ll answer = i * block + it->second;
        if (answer < q) return answer;
      }
      target = mul(target, step, p);
    }
    return -1;
  };

  // Find h^z = error^(-1), one base-q digit at a time.
  int digits = t - e;
  ll target = cp::mod_pow(error, p - 2, p);
  ll inverse_h = cp::mod_pow(h, p - 2, p);
  ll z = 0;

  rep(j, digits) {
    if (target == 1) break;
    ll projected = cp::mod_pow(target, qpow[digits - 1 - j], p);
    ll digit = digit_log(projected);
    assert(digit != -1);

    z += digit * qpow[j];
    target = mul(target, cp::mod_pow(inverse_h, digit, p), p);
    inverse_h = cp::mod_pow(inverse_h, q, p);
  }

  assert(target == 1);
  return mul(result, cp::mod_pow(generator, z, p), p);
}

ll kth_root(ll p, ll k, ll a) {
  if (a == 1) return 1;
  k %= p - 1;
  if (k == 0) return -1;
  if (k == 1) return a;

  ll d = gcd(k, p - 1);
  ll order = (p - 1) / d;
  if (cp::mod_pow(a, order, p) != 1) return -1;

  a = cp::mod_pow(a, inverse(k / d, order), p);

  V<ll> factors;
  factor(d, factors);
  sort(all(factors));

  for (int i = 0; i < factors.size();) {
    int j = i;
    while (j < factors.size() && factors[j] == factors[i]) ++j;
    a = prime_power_root(a, factors[i], j - i, p);
    i = j;
  }
  return a;
}

}  // namespace root64

void solve() {
  LL(p, k, a);
  wt(root64::kth_root(p, k, a));
}

}

void XK::INIT() {
  mm::set_mod(MOD);
  // prepare_factorial();
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  XK::INIT();
  if (__multi__) cin >> t;
  while (t--) XK::solve();
}

// ---- end std.cpp ----