// https://github.com/2251799813685248/Competitive-Programming-Library

#include <deque>
#include <iostream>
#include <iterator>
#include <ranges>
#include <cmath>
#include <set>
#include <utility>
#include <string>
#ifndef LIST__HPP_
#define LIST__HPP_

#include <algorithm>
#include <iostream>
#include <cassert>
#include <functional>
#include <utility>
using uint = unsigned int;
using ll = long long;
using namespace std;


template<typename T> concept has_identity = requires (){T();};
template<typename T> concept has_plus_operator = requires (T a, T b){a+b;};
template<typename T> concept has_compare_operator = requires (T a, T b){a < b;};
template<typename T> concept has_equal_operator = requires (T a, T b){a == b; a != b;};

/// @brief 動的配列
template<typename T>
class list{
    public:

    using value_type = T;

    constexpr list(): sz_(0), max_sz_(0), A(nullptr){}
    constexpr list(uint sz): sz_(sz), max_sz_(sz){
        if (sz == 0){A = nullptr; return;}
        if (sz > 214748367){cerr << "ValueError: too large or negative size" << endl; assert(false);}
        A = new T[sz_]{};
        if (A == nullptr){cerr << "MomoryError: failed to allocate memory" << endl; assert(false);}
    }
    constexpr list(uint sz, T elem): sz_(sz), max_sz_(sz){
        if (sz == 0){A = nullptr; return;}
        if (sz > 2147483647){cerr << "ValueError: too large or negative size" << endl; assert(false);}
        A = new T[sz_]{};
        if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
        for (int i = 0; i < sz_; i++){
            A[i] = elem;
        }
    }
    constexpr list(initializer_list<T> init): sz_(init.size()), max_sz_(init.size()){
        A = new T[sz_]{};
        if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
        for (int i = 0; i < sz_; i++){
            A[i] = *(init.begin()+i);
        }
    };
    // constexpr list<ll>(const range& r){
    //     if (r.step_ == 0){cerr << "ValueError: step argument must not be zero" << endl; assert(false);}
    //     if (r.step_ > 0){
    //         int imax = r.begin_ >= r.end_ ? 0 : (r.end_-r.begin_+r.step_-1)/r.step_;
    //         sz_ = imax;
    //         max_sz_ = imax;
    //         A = new T[sz_]{};
    //         if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
    //         for (int i = 0; i < imax; i++){
    //             int target = r.begin_+r.step_*i;
    //             A[i] = target;
    //         }    
    //     }
    //     else{
    //         int imax = r.end_ >= r.begin_ ? 0 : (r.begin_-r.end_-r.step_-1)/(-r.step_);
    //         sz_ = imax;
    //         max_sz_ = imax;
    //         A = new T[sz_]{};
    //         if (A == nullptr){cerr << "MemoryError: failed to allocate memory" << endl; assert(false);}
    //         for (int i = 0; i < imax; i++){
    //             int target = r.begin_+r.step_*i;
    //             A[i] = target;
    //         }
    //     }
    // }
    constexpr list(const list<T>& other): sz_(other.sz_), max_sz_(other.max_sz_){
        A = new T[max_sz_]{};
        for (int i = 0; i < sz_; i++){
            A[i] = other.A[i];
        }
    }
    constexpr list(list<T>&& other) noexcept : sz_(other.sz_), max_sz_(other.max_sz_){
        A = other.A;
        other.sz_ = 0;
        other.max_sz_ = 0;
        other.A = nullptr;
    }
    constexpr ~list() {
        delete[] A;
    }

    class iterator{
        public:
        using difference_type = ll;
        using value_type = T;
        using pointer = T*;
        using reference = T&;
        using iterator_category = std::random_access_iterator_tag;
        
        iterator() = delete;
        constexpr iterator(const list* listptr_init, const int &idx_init): listptr(listptr_init), idx(idx_init){}

        inline constexpr value_type& operator* () const {return listptr->A[this->check_idx()];}
        inline constexpr value_type* operator->() const {return &listptr->A[this->check_idx()];}

        inline constexpr bool operator==(const iterator &other) const {return idx == other.idx;}
        inline constexpr bool operator!=(const iterator &other) const {return idx != other.idx;}
        inline constexpr bool operator<(const iterator &other) const {return idx < other.idx;}
        inline constexpr bool operator>(const iterator &other) const {return idx > other.idx;}
        inline constexpr bool operator<=(const iterator &other) const {return idx <= other.idx;}
        inline constexpr bool operator>=(const iterator &other) const {return idx >= other.idx;}

        inline constexpr iterator operator++(){
            this->idx++;
            return *this;
        }
        inline constexpr iterator operator++(int){
            iterator temp = *this;
            this->idx++;
            return temp;
        }
        inline constexpr iterator operator--(){
            this->idx--;
            return *this;
        }
        inline constexpr iterator operator--(int){
            iterator temp = *this;
            this->idx--;
            return temp;
        }

        inline constexpr iterator& operator+=(int amount){
            this->idx += amount;
            return *this;
        }
        inline constexpr iterator operator+(int amount) const {
            iterator temp = *this;
            temp.idx += amount;
            return temp;
        }
        inline constexpr iterator& operator-=(const int &amount){
            this->idx -= amount;
            return *this;
        }
        inline constexpr iterator operator-(const int &amount) const{
            iterator temp = *this;
            temp.idx -= amount;
            return temp;
        }

        inline constexpr difference_type operator-(const iterator &other) const{
            return idx - other.idx;
        }

        
        inline constexpr int check_idx() const {
            if (idx < 0 || idx >= listptr->sz_){
                cerr << "IteratorIndexError: index out of range. current size: " << listptr->sz_ << " target index: " << idx << endl; assert(false);
            }
            return idx;
        }

        private:
        
        const list* listptr;
        int idx;
    };

    inline constexpr iterator begin(){return iterator(this, 0);}
    inline constexpr iterator begin() const {return iterator(this, 0);}
    inline constexpr iterator end(){return iterator(this, sz_);}
    inline constexpr iterator end() const {return iterator(this, sz_);}

    inline constexpr list& operator=(const list& other){
        if (this == &other){return *this;}
        sz_ = other.sz_;
        max_sz_ = other.max_sz_;
        delete[] A;
        A = new T[max_sz_]{};
        for (int i = 0; i < sz_; i++){
            A[i] = other.A[i];
        }
        return *this;
    }
    inline constexpr list& operator=(list&& other) noexcept {
        if (this == &other){return *this;}
        delete[] A;
        sz_ = other.sz_;
        max_sz_ = other.max_sz_;
        A = other.A;
        other.sz_ = 0;
        other.max_sz_ = 0;
        other.A = nullptr;
        return *this;
    }
    inline constexpr bool operator==(const list& other) const {
        if (sz_ != other.sz_){return false;}
        bool res = true;
        for (int i = 0; i < sz_; i++){
            if (A[i] != other.A[i]){
                res = false;
                break;
            }
        }
        return res;
    }
    inline constexpr bool operator!=(const list& other) const {
        return !this->operator==(other);
    }
    inline constexpr bool operator<(const list& other) const {
        int lcp_back = 0;
        for (int i = 0, sz2 = min(sz_, other.sz_); i < sz2; i++){
            if (A[i] != other.A[i]){break;}
            lcp_back++;
        }
        if (lcp_back == sz_ && lcp_back == other.sz_){return false;}
        else if (lcp_back == sz_){return true;}
        else if (lcp_back == other.sz_){return false;}
        else{return A[lcp_back] < other.A[lcp_back];}
    }
    inline constexpr bool operator<=(const list& other) const {
        int lcp_back = 0;
        for (int i = 0, sz2 = min(sz_, other.sz_); i < sz2; i++){
            if (A[i] != other.A[i]){break;}
            lcp_back++;
        }
        if (lcp_back == sz_ && lcp_back == other.sz_){return true;}
        else if (lcp_back == sz_){return true;}
        else if (lcp_back == other.sz_){return false;}
        else{return A[lcp_back] < other.A[lcp_back];}
    }
    inline constexpr bool operator>(const list& other) const {return other < *this;}
    inline constexpr bool operator>=(const list& other) const {return other <= *this;}
    inline constexpr list& operator+=(const list& other){
        for (int i = 0, sz2 = other.size(); i < sz2; i++){
            append(other.A[i]);
        }
        return *this;
    }
    inline constexpr list operator+(const list& other) const {
        return list(*this) += other;
    }
    inline constexpr list& operator+=(const T& val){
        append(val);
        return *this;
    }
    inline constexpr list operator+(const T& val) const {
        return list(*this) += val;
    }
    
    

    inline constexpr void append(const T& val){
        if (sz_ < max_sz_){
            A[sz_] = val;
            sz_++;
        }
        else{
            if (max_sz_ < 2){max_sz_ = 2;}
            else{max_sz_ += max_sz_>>1;}
            auto B = new T[max_sz_]{};
            B[sz_] = val;
            for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
            sz_++;
            delete[] A;
            A = B;
        }
    }
    inline constexpr void append(T&& val){
        if (sz_ < max_sz_){
            A[sz_] = std::move(val);
            sz_++;
        }
        else{
            if (max_sz_ < 2){max_sz_ = 2;}
            else{max_sz_ += max_sz_>>1;}
            auto B = new T[max_sz_]{};
            B[sz_] = std::move(val);
            for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
            sz_++;
            delete[] A;
            A = B;
        }
    }
    inline constexpr T pop(){
        if (sz_ == 0){cerr << "IndexError: pop from empty list" << endl; assert(false);}
        sz_--;
        return std::move(A[sz_]);
    }
    inline constexpr void reserve(uint new_sz){
        if (new_sz > 2147483647){cerr << "ValueError: too large or negative size" << endl; assert(false);}
        if ((int)new_sz <= max_sz_){return;}
        max_sz_ = new_sz;
        auto B = new T[new_sz]{};
        if (B == nullptr){cerr << "MemoryError: failed to reallocate memory" << endl; assert(false);}
        for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
        delete[] A;
        A = B;
    }
    inline constexpr void resize(uint new_sz, T elem = T()){
        if (new_sz > 2147483647){cerr << "ValueError: too large or negative size" << endl; assert(false);}
        if ((int)new_sz <= max_sz_){
            while (sz_ > (int)new_sz){pop();}
            for (int i = sz_, new_sz_int = new_sz; i < new_sz_int; i++){A[i] = elem;}
            sz_ = new_sz;
            return;
        }
        max_sz_ = new_sz + (new_sz >> 1);
        auto B = new T[max_sz_]{};
        if (B == nullptr){cerr << "MemoryError: failed to reallocate memory" << endl; assert(false);}
        for (int i = 0; i < sz_; i++){B[i] = std::move(A[i]);}
        for (int i = sz_, new_sz_int = new_sz; i < new_sz_int; i++){B[i] = elem;}
        sz_ = new_sz;
        delete[] A;
        A = B;
    }
    template <class InputIterator> inline constexpr void assign(InputIterator first, InputIterator last){
        reserve(last-first);
        while (first != last){append(*first); first++;}
    }
    inline constexpr void assign(uint n, const T& val){
        reserve(n);
        sz_ = n;
        for (uint i = 0; i < n; i++){
            A[i] = val;
        }
    }
    inline constexpr iterator insert(iterator pos, const T& val){
        int idx = pos.check_idx();
        append(val);
        for (int i = idx; i < sz_-1; i++){swap(A[i], A[sz_-1]);}
        return pos;
    }
    // inline constexpr void insert(iterator pos, iterator begin, iterator end)
    inline constexpr iterator erase(iterator pos){
        int idx = pos.check_idx();
        for (int i = idx; i < sz_-1; i++){
            swap(A[i], A[i+1]);
        }
        sz_ -= 1;
        return pos;
    }
    inline constexpr iterator erase(iterator start, iterator end){
        int startidx = start.check_idx(), endidx = end.check_idx();
        if (startidx > endidx){cerr << "IndexError: invalid interval: [start, end) = []" << startidx << ", " << endidx << ")" << endl; assert(false);}
        for (int i = startidx; i < endidx; i++){
            A[i].~T();
        }
        if (startidx < endidx){
            for (int i = endidx; i < sz_; i++){
                swap(A[i+startidx-endidx], A[i]);
            }
        }
        sz_ -= endidx-startidx;
        return end;
    }
    inline constexpr void clear(){sz_ = 0; max_sz_ = 0; delete[] A;}
    inline constexpr const T& operator[](int idx) const {
        check_and_adjust_idx(idx);
        return A[idx];
    }
    inline constexpr T& operator[](int idx){
        check_and_adjust_idx(idx);
        return A[idx];
    }
    inline constexpr T& front(){return (*this)[0];}
    inline constexpr const T& front() const {return (*this)[0];}
    inline constexpr T& back(){return (*this)[-1];}
    inline constexpr const T& back() const {return (*this)[-1];}
    inline constexpr list<T> operator[](int left, int right, int step = 1) const {
        if (step == 0){cerr << "ValueError: step argument must not be zero" << endl; assert(false);}
        if (step > 0){
            int imax = left >= right ? 0 : (right-left+step-1)/step;
            list<T> B(imax);
            for (int i = 0; i < imax; i++){
                int target = left+step*i;
                if (target < 0 || target >= sz_){cerr << "IndexError: slice index out of range. current size: " << sz_ << " target index: " << target << endl; assert(false);}
                B[i] = A[target];
            }
            return std::move(B);
        }
        else{
            int imax = right >= left ? 0 : (left-right-step-1)/(-step);
            list<T> B(imax);
            for (int i = 0; i < imax; i++){
                int target = left+step*i;
                if (target < 0 || target >= sz_){cerr << "IndexError: slice index out of range. current size: " << sz_ << " target index: " << target << endl; assert(false);}
                B[i] = A[target];
            }
            return std::move(B);
        }
    }
    inline constexpr T* data() {return empty() ? nullptr : &A[0];}
    inline constexpr const T* data() const {return empty() ? nullptr : &A[0];}
    inline constexpr T sum() const requires has_plus_operator<T> && has_identity<T>{
        auto res = T();
        for (int i = 0; i < sz_; i++){
            res += A[i];
        }
        return res;
    }
    template<typename U> inline constexpr U sum(U init) const requires has_plus_operator<T>{
        for (int i = 0; i < sz_; i++){
            init += A[i];
        }
        return init;
    }
    inline constexpr void sort(bool reverse = false) requires has_compare_operator<T> {
        if (reverse){
            std::sort(begin(), end(), std::move([](const T& a, const T& b){return b < a;}));
        }
        else{
            std::sort(begin(), end());
        }
    }
    inline constexpr void sort(const function<bool(T,T)>& f) requires has_compare_operator<T> {
        std::sort(begin(), end(), f);
    }
    inline constexpr void reverse(){
        std::reverse(begin(), end());
    }
    inline constexpr ll count(const T& val){
        ll res = 0;
        for (int i = 0; i < sz_; i++){res += A[i] == val;}
        return res;
    }
    inline constexpr void apply(const function<T(T)>& f){for (int i = 0; i < sz_; i++){A[i] = f(A[i]);}}
    inline constexpr list<pair<int, T>> RLE(){
        list<pair<int, T>> res;
        for (int l = 0, r = 0; l < sz_;){
            while (r < sz_ && A[l] == A[r]){
                r++;
            }
            res.append(make_pair(r-l, A[l]));
            l = r;
        }
        return res;
    }
    inline constexpr iterator lower_bound(const T& val) const requires has_compare_operator<T> {return std::lower_bound(begin(), end(), val);}
    inline constexpr iterator upper_bound(const T& val) const requires has_compare_operator<T> {return std::upper_bound(begin(), end(), val);}
    inline constexpr ll size() const {return sz_;}
    inline constexpr ll maxsize() const {return max_sz_;}
    inline constexpr bool empty() const {return sz_ == 0;}

    private:

    inline constexpr void check_and_adjust_idx(int& idx) const {
        if (idx >= sz_){cerr << "IndexError: index out of range. current size: " << sz_ << " target index: " << idx << endl; assert(false);}
        if (idx < 0){
            if (idx < -sz_){cerr << "IndexError: index out of range. current size: " << sz_ << " target index: " << idx << endl; assert(false);}
            idx += sz_;
        }
    }

    int sz_;
    int max_sz_;
    T* A;
};


#endif /* LIST__HPP_ */
#include <algorithm>
#include <iostream>
#include <cassert>
#include <functional>
#include <utility>
#include <chrono>
#include <format>
#include <iomanip>

// #include <boost/multiprecision/cpp_int.hpp>


using namespace std;
using ll = long long;
using lll = __int128_t;
using ull = unsigned long long;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif
using ld = long double;
using pii = array<int,2>;
using pll = array<ll,2>;
using plll = array<lll,2>;
using tll = array<ll,3>;

#define vall(A) A.begin(), A.end()
template<typename T> inline bool btest(T K, int i){return K&(1ull<<i);}
#ifndef LEN_DEFINED
#define LEN_DEFINED
template<typename T> inline constexpr ll len(const T& A){return ssize(A);}
#endif
constexpr ll pow2ll[63] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
constexpr ll pow10ll[19] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
constexpr ll di[4] = {0,1,0,-1};
constexpr ll di8[8] = {0,1,1,1,0,-1,-1,-1};
constexpr ll dj[4] = {1,0,-1,0};
constexpr ll dj8[8] = {1,1,0,-1,-1,-1,0,1};


constexpr ll mod = 998244353;


#ifndef FASTIO__HPP_
#define FASTIO__HPP_

#include <array>
#include <bit>
#include <charconv>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <string>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <utility>

// C++20. Integer input must fit the destination type. For modint input, the
// magnitude must fit uint64_t; negative values are reduced modulo the modulus.
// FILE* is borrowed: it must outlive the reader/writer. Do not mix buffered
// readers on one stream. The default input buffer is intended for batch judges;
// interactive programs need BasicInput<1> and explicit output flush().
namespace fastio {
namespace detail {
template<class T> inline constexpr bool integer = std::is_integral_v<T>;
template<class T> struct unsigned_type { using type = std::make_unsigned_t<T>; };
template<> struct unsigned_type<bool> { using type = unsigned char; };
#if defined(__SIZEOF_INT128__)
template<> inline constexpr bool integer<__int128_t> = true;
template<> inline constexpr bool integer<__uint128_t> = true;
template<> struct unsigned_type<__int128_t> { using type = __uint128_t; };
template<> struct unsigned_type<__uint128_t> { using type = __uint128_t; };
#endif
template<class T> using unsigned_t = typename unsigned_type<T>::type;
template<class T> inline constexpr bool signed_integer = integer<T> && T(-1) < T(0);
template<class T> concept modular = requires(T x) { x.val; } &&
    (requires { T::mod_value; } || requires { T::mod(); });
template<class T> constexpr auto modulus() {
    if constexpr (requires { T::mod_value; }) return T::mod_value;
    else return T::mod();
}
template<class T> concept indexed_range = requires(T& x) { std::size(x); x[0]; };
template<class T> concept tuple_like = requires { std::tuple_size<T>::value; };
template<class> inline constexpr bool unsupported = false;
inline constexpr auto digit_pairs = [] {
    std::array<char, 200> result{};
    for (int i = 0; i < 100; ++i) {
        result[2*i] = char('0'+i/10);
        result[2*i+1] = char('0'+i%10);
    }
    return result;
}();
inline constexpr auto digit_quads = [] {
    std::array<std::array<char,4>,10000> result{};
    for (unsigned i = 0; i < 10000; ++i) {
        result[i] = {char('0'+i/1000),char('0'+i/100%10),
                     char('0'+i/10%10),char('0'+i%10)};
    }
    return result;
}();
inline char* leading_quad(char* p, unsigned value) {
    if (value >= 1000) { std::memcpy(p,digit_quads[value].data(),4); return p+4; }
    if (value >= 100) { *p++ = char('0'+value/100); value %= 100; }
    else if (value < 10) { *p++ = char('0'+value); return p; }
    std::memcpy(p,digit_pairs.data()+2*value,2);
    return p+2;
}
inline char* decimal32(char* p, std::uint32_t value) {
    if (value >= 100000000) {
        p = leading_quad(p,value/100000000);
        value %= 100000000;
        std::memcpy(p,digit_quads[value/10000].data(),4);
        std::memcpy(p+4,digit_quads[value%10000].data(),4);
        return p+8;
    }
    if (value >= 10000) {
        p = leading_quad(p,value/10000);
        std::memcpy(p,digit_quads[value%10000].data(),4);
        return p+4;
    }
    return leading_quad(p,value);
}
template<class T> inline constexpr bool output32 = [] {
    if constexpr (integer<T>) return sizeof(T) <= 4 && !std::is_same_v<T,char>;
    else if constexpr (modular<T>) return integer<decltype(T{}.val)> && sizeof(T{}.val) <= 4;
    else return false;
}();
template<class T> inline char* decimal_small(char* p, const T& value) {
    if constexpr (modular<T>) return decimal_small(p,value.val);
    else {
        std::uint32_t u = static_cast<std::uint32_t>(value);
        if constexpr (signed_integer<T>) {
            if (value < 0) { *p++ = '-'; u = 0-u; }
        }
        return decimal32(p,u);
    }
}
} // namespace detail

template<std::size_t BufferSize = 1 << 18>
class BasicInput {
    static_assert(BufferSize > 0);
    std::FILE* file_;
    char buffer_[BufferSize+1];
    std::size_t position_ = 0, size_ = 0;
    bool good_ = true;

    int peek() {
        if (position_ == size_) {
            size_ = std::fread(buffer_, 1, BufferSize, file_);
            buffer_[size_] = '\0';
            position_ = 0;
            if (size_ == 0) return EOF;
        }
        return static_cast<unsigned char>(buffer_[position_]);
    }
    int skip_space() {
        int c;
        while ((c = peek()) != EOF && c <= ' ') ++position_;
        return c;
    }
    template<class U, bool SingleBlock = false> bool magnitude(U& value, bool& negative) {
        int c = skip_space();
        if (c == EOF) return false;
        negative = c == '-';
        if (c == '-' || c == '+') { ++position_; c = peek(); }
        if (static_cast<unsigned>(c-'0') > 9) return false;
        value = 0;
        do {
            const char* p = buffer_+position_;
            if constexpr (sizeof(U) >= 4 && std::endian::native == std::endian::little) {
                while (buffer_+size_-p >= 8) {
                    std::uint64_t block;
                    std::memcpy(&block,p,8);
                    // All eight bytes must be ASCII decimal digits.
                    if (((block+0x4646464646464646ULL) | (block-0x3030303030303030ULL)) & 0x8080808080808080ULL) break;
                    block -= 0x3030303030303030ULL;
                    block = (block*10+(block>>8)) & 0x00ff00ff00ff00ffULL;
                    block = (block*100+(block>>16)) & 0x0000ffff0000ffffULL;
                    block = (block*10000+(block>>32)) & 0xffffffffULL;
                    value = value*100000000+static_cast<std::uint32_t>(block);
                    p += 8;
                    if constexpr (SingleBlock || sizeof(U) == 4) break;
                }
            }
            unsigned digit;
            // The sentinel stops this loop without an EOF/buffer check for
            // every digit. Only a token crossing a refill needs the outer loop.
            while ((digit = static_cast<unsigned>(static_cast<unsigned char>(*p)-'0')) <= 9) {
                value = value*10+digit;
                ++p;
            }
            position_ = static_cast<std::size_t>(p-buffer_);
            if (position_ != size_) break;
            c = peek();
        } while (static_cast<unsigned>(c-'0') <= 9);
        return true;
    }
    template<class T> bool read_one(T& value) {
        if constexpr (std::is_same_v<T, char>) {
            const int c = skip_space();
            if (c == EOF) return false;
            value = static_cast<char>(c);
            ++position_;
            return true;
        } else if constexpr (detail::integer<T>) {
            detail::unsigned_t<T> u;
            bool negative;
            if (!magnitude(u,negative)) return false;
            if constexpr (detail::signed_integer<T>) {
                // Never negate the minimum signed value, even for int128.
                value = negative && u != 0 ? -static_cast<T>(u-1)-1 : static_cast<T>(u);
            } else {
                if (negative || (std::is_same_v<T,bool> && u > 1)) return false;
                value = static_cast<T>(u);
            }
            return true;
        } else if constexpr (detail::modular<T>) {
            std::uint64_t u;
            bool negative;
            // Most modular coefficients have at most ten digits. After the
            // first eight, parse the short tail without another wide probe.
            if (!magnitude<std::uint64_t,true>(u,negative)) return false;
            const auto mod = detail::modulus<T>();
            if (u >= mod) u %= mod;
            value.val = negative && u != 0 ? mod-u : u;
            return true;
        } else if constexpr (std::is_same_v<T,std::string>) {
            int c = skip_space();
            if (c == EOF) return false;
            value.clear();
            do {
                value.push_back(static_cast<char>(c));
                ++position_;
                c = peek();
            } while (c != EOF && c > ' ');
            return true;
        } else if constexpr (std::is_floating_point_v<T>) {
            std::string token;
            if (!read_one(token)) return false;
            const char* first = token.data();
            const char* last = first+token.size();
            if (first != last && *first == '+') ++first;
            const auto result = std::from_chars(first,last,value);
            return result.ec == std::errc{} && result.ptr == last;
        } else if constexpr (detail::indexed_range<T>) {
            const auto n = std::size(value);
            if constexpr (requires { std::data(value); }) {
                auto* data = std::data(value);
                for (decltype(std::size(value)) i = 0; i < n; ++i)
                    if (!read_one(data[i])) return false;
            } else {
                for (decltype(std::size(value)) i = 0; i < n; ++i)
                    if (!read_one(value[i])) return false;
            }
            return true;
        } else if constexpr (detail::tuple_like<T>) {
            return std::apply([&](auto&... x) { return (read_one(x) && ...); },value);
        } else {
            static_assert(detail::unsupported<T>, "Unsupported fastio input type");
        }
    }
public:
    explicit BasicInput(std::FILE* file = stdin) : file_(file) {}
    BasicInput(const BasicInput&) = delete;
    BasicInput& operator=(const BasicInput&) = delete;

    template<class... T> bool read(T&... values) {
        if (!good_) return false;
        return good_ = (read_one(values) && ...);
    }
    template<class T> BasicInput& operator>>(T& value) { read(value); return *this; }
    explicit operator bool() const { return good_; }
};

template<std::size_t BufferSize = 1 << 18>
class BasicOutput {
    static_assert(BufferSize > 0);
    std::FILE* file_;
    char buffer_[BufferSize];
    std::size_t size_ = 0;
    bool good_ = true;

    bool drain() {
        if (!good_) return false;
        std::size_t done = 0;
        while (done < size_) {
            const auto n = std::fwrite(buffer_+done,1,size_-done,file_);
            if (n == 0) { size_ = 0; return good_ = false; }
            done += n;
        }
        size_ = 0;
        return true;
    }
    bool put(char c) {
        if (!good_ || (size_ == BufferSize && !drain())) return false;
        buffer_[size_++] = c;
        return true;
    }
    bool bytes(const char* data, std::size_t count) {
        if (!good_) return false;
        while (count != 0) {
            if (size_ == BufferSize && !drain()) return false;
            const auto room = BufferSize-size_;
            const auto n = count < room ? count : room;
            std::memcpy(buffer_+size_,data,n);
            size_ += n; data += n; count -= n;
        }
        return true;
    }
    template<class U> bool unsigned_number(U value, bool negative) {
        if constexpr (sizeof(U) <= 4 && BufferSize >= 12) {
            if (!good_ || (BufferSize-size_ < 12 && !drain())) return false;
            char* p = buffer_+size_;
            if (negative) *p++ = '-';
            p = detail::decimal32(p,value);
            size_ = static_cast<std::size_t>(p-buffer_);
            return true;
        }
        // 128-bit unsigned integers need at most 39 decimal digits.
        char digits[3*sizeof(U)+2];
        char* const end = digits+sizeof(digits);
        char* p = end;
        while (value >= 100) {
            const U q = value/100;
            const unsigned r = static_cast<unsigned>(value-q*100);
            p -= 2;
            std::memcpy(p,detail::digit_pairs.data()+2*r,2);
            value = q;
        }
        if (value < 10) *--p = char('0'+static_cast<unsigned>(value));
        else {
            p -= 2;
            std::memcpy(p,detail::digit_pairs.data()+2*static_cast<unsigned>(value),2);
        }
        if (negative) *--p = '-';
        if constexpr (BufferSize >= sizeof(digits)) {
            if (!good_ || (BufferSize-size_ < sizeof(digits) && !drain())) return false;
            auto count = static_cast<std::size_t>(end-p);
            char* dest = buffer_+size_;
            size_ += count;
            // Constant-size copies avoid a library call per integer. Each copy
            // stays inside the initialized digits and the reserved buffer area.
            if constexpr (sizeof(digits) >= 8)
                while (count >= 8) {
                    std::memcpy(dest,p,8);
                    dest += 8; p += 8; count -= 8;
                }
            if (count >= 4) { std::memcpy(dest,p,4); dest += 4; p += 4; count -= 4; }
            if (count >= 2) { std::memcpy(dest,p,2); dest += 2; p += 2; count -= 2; }
            if (count) *dest = *p;
            return true;
        }
        return bytes(p,static_cast<std::size_t>(end-p));
    }
    template<class T> bool write_one(const T& value) {
        if constexpr (std::is_same_v<T,char>) {
            return put(value);
        } else if constexpr (detail::integer<T>) {
            using U = detail::unsigned_t<T>;
            U u = static_cast<U>(value);
            bool negative = false;
            if constexpr (detail::signed_integer<T>) {
                negative = value < 0;
                if (negative) u = U(0)-u;
            }
            return unsigned_number(u,negative);
        } else if constexpr (detail::modular<T>) {
            return write_one(value.val);
        } else if constexpr (std::is_convertible_v<const T&,std::string_view>) {
            const std::string_view text(value);
            return bytes(text.data(),text.size());
        } else if constexpr (std::is_floating_point_v<T>) {
            char text[128];
            const auto result = std::to_chars(text,text+sizeof(text),value);
            if (result.ec != std::errc{}) return false;
            return bytes(text,static_cast<std::size_t>(result.ptr-text));
        } else if constexpr (detail::indexed_range<const T>) {
            const auto n = std::size(value);
            using Element = std::remove_cvref_t<decltype(value[0])>;
            if constexpr (detail::indexed_range<Element> || detail::tuple_like<Element>){
                for (decltype(std::size(value)) i = 0; i < n; ++i) {
                    if (i != 0 && !put('\n')) return false;
                    if (!write_one(value[i])) return false;
                }
                return true;
            }
            if constexpr (BufferSize >= 32 && detail::output32<Element> && requires { std::data(value); }) {
                const auto* data = std::data(value);
                char* p = buffer_+size_;
                for (decltype(std::size(value)) i = 0; i < n; ++i) {
                    if (buffer_+BufferSize-p < 12) {
                        size_ = static_cast<std::size_t>(p-buffer_);
                        if (!drain()) return false;
                        p = buffer_;
                    }
                    if (i != 0) *p++ = ' ';
                    p = detail::decimal_small(p,data[i]);
                }
                size_ = static_cast<std::size_t>(p-buffer_);
                return true;
            }
            for (decltype(std::size(value)) i = 0; i < n; ++i) {
                if (i != 0 && !put(' ')) return false;
                if (!write_one(value[i])) return false;
            }
            return true;
        } else if constexpr (detail::tuple_like<T>) {
            [[maybe_unused]] bool first = true;
            return std::apply([&](const auto&... x) {
                return (((std::exchange(first,false) || put(' ')) && write_one(x)) && ...);
            },value);
        } else {
            static_assert(detail::unsupported<T>, "Unsupported fastio output type");
        }
    }
public:
    explicit BasicOutput(std::FILE* file = stdout) : file_(file) {}
    BasicOutput(const BasicOutput&) = delete;
    BasicOutput& operator=(const BasicOutput&) = delete;
    ~BasicOutput() { flush(); }

    // write concatenates its arguments; print separates them with spaces and
    // appends a newline. Ranges and tuples use spaces between their elements.
    template<class... T> bool write(const T&... values) {
        if (!good_) return false;
        return good_ = (write_one(values) && ...);
    }
    template<class... T> bool print(const T&... values) {
        if (!good_) return false;
        [[maybe_unused]] bool first = true;
        good_ = (((std::exchange(first,false) || put(' ')) && write_one(values)) && ...);
        return good_ && put('\n');
    }
    template<class... T> bool printflush(const T&... values) {
        if (!good_) return false;
        [[maybe_unused]] bool first = true;
        good_ = (((std::exchange(first,false) || put(' ')) && write_one(values)) && ...);
        return good_ && put('\n') && flush();
    }
    bool flush() { return drain() && (good_ = std::fflush(file_) == 0); }
    template<class T> BasicOutput& operator<<(const T& value) { write(value); return *this; }
    explicit operator bool() const { return good_; }
};


#ifdef LOCAL_a1073741824
using FastInput = BasicInput<1>;
#else
using FastInput = BasicInput<>;
#endif
using FastOutput = BasicOutput<>;

// template<class... T> bool read(T&... values) { return in.read(values...); }
// template<class... T> bool write(const T&... values) { return out.write(values...); }
// template<class... T> bool print(const T&... values) { return out.print(values...); }
// template<class... T> bool printflush(const T&... values) { return out.print(values...) && out.flush(); }
// inline bool flush() { return out.flush(); }

} // namespace fastio

#endif /* FASTIO__HPP_ */

#ifndef MODINT__HPP_
#define MODINT__HPP_

#include <iostream>
#ifndef MATH_FUNCTION_HPP_
#define MATH_FUNCTION_HPP_

#include <array>
#include <cmath>
#include <cassert>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using ulll = __uint128_t;
#ifdef BOOST_VERSION
using bll = boost::multiprecision::cpp_int;
#endif


constexpr ll getdigit(ull x){
    if (x < 1000000000){
        if (x < 100000){
            return x == 0 ? 0 : x < 10 ? 1 : x < 100 ? 2 : x < 1000 ? 3 : x < 10000 ? 4 : 5;
        }
        else{
            return x < 1000000 ? 6 : x < 10000000 ? 7 : x < 100000000 ? 8 : 9;
        }
    }
    else{
        if (x < 100000000000000){
            return x < 10000000000 ? 10 : x < 100000000000 ? 11 : x < 1000000000000 ? 12 : x < 10000000000000 ? 13 : 14;
        }
        else{
            return x < 1000000000000000 ? 15 : x < 10000000000000000 ? 16 : x < 100000000000000000 ? 17 : x < 1000000000000000000 ? 18 : x < 10000000000000000000u ? 19 : 20;
        }
    }
}

/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる
constexpr ll modpow(ll a, ull b, const ll m){
    ll t = a%m;
    ll ans = (m == 1 ? 0 : 1);
    while (b > 0){
        if (b&1){
            ans = (ans*t)%m;
        }
        b >>= 1;
        t = (t*t)%m;
    }
    return ans;
}

/// @brief a^bをmで割った余りを返す。bに関して対数時間で計算できる。mはコンパイル時に決定している必要がある
template<ll m> constexpr ll modpow(ll a, ull b){
    ll t = a%m;
    ll ans = (m == 1 ? 0 : 1);
    while (b > 0){
        if (b&1){
            ans = (ans*t)%m;
        }
        b >>= 1;
        t = (t*t)%m;
    }
    return ans;
}

/// @brief a^nを返す。bに関して対数時間で計算できる。
template<typename T> constexpr T powll(T a, T n){
    T t = a;
    T ans = 1;
    while (n > 0){
        if (n%2){
            ans *= t;
        }
        n >>= 1;
        t *= t;
    }
    return ans;
}
/// @brief a^nを返す。bに関して対数時間で計算できる
template<> constexpr ll powll(ll a, ll n){
    ll t = a;
    ll ans = 1;
    while (n > 0){
        if (n&1){
            ans *= t;
        }
        n >>= 1;
        t *= t;
    }
    return ans;
}


/// @brief floor(sqrt(N))を返す。1.5×10^19まで対応
constexpr ll isqrt(ull N){
    assert(N <= 15000000000000000000ull);
    ull ret = sqrt(N);
    while (ret*ret > N){
        ret--;
    }
    while ((ret+1)*(ret+1) <= N){
        ret++;
    }
    return ret;
}
#ifdef BOOST_VERSION
/// @brief floor(sqrt(N))を返す。多倍長整数に対応
constexpr bll isqrt_large(bll N){
    bll ret = sqrt(N);
    while (ret*ret > N){
        ret--;
    }
    while ((ret+1)*(ret+1) <= N){
        ret++;
    }
    return ret;
}
#endif

/// @brief floor(log_a(L))を返す
constexpr ll ilog(ll a, ll L){
    __int128_t t = 1;
    ll ans = 0;
    while (t <= L){
        ans++;
        t *= a;
    }
    return ans-1;
}

/// @brief 有理数のfloorを求める。 floor(y/x)
template<typename T> constexpr inline T floor2(T y, T x){
    if ((x^y) > 0){
        x = x > 0 ? x : -x;
        y = y > 0 ? y : -y;
        return y/x;
    }
    else if ((x^y) < 0){
        x = x > 0 ? x : -x;
        y = y > 0 ? y : -y;
        return -((y+x-1)/x);
    }
    else{
        return y/x;
    }
}
/// @brief 有理数のceilを求める。 ceil(y/x)
template<typename T> constexpr inline T ceil2(T y, T x){
    if ((x^y) > 0){
        x = x > 0 ? x : -x;
        y = y > 0 ? y : -y;
        return (y+x-1)/x;
    }
    else if ((x^y) < 0){
        x = x > 0 ? x : -x;
        y = y > 0 ? y : -y;
        return -(y/x);
    }
    else{
        return y/x;
    }
}

/// @brief 一次不定方程式ax+by=gcd(a,b)の解を1つ見つける
/// @param a `a>=0`である必要がある
/// @param b `b>=0`である必要がある
/// @return {x,y,gcd(a,b)}
template<typename T>
constexpr array<T,3> axby1(T a, T b){
    T x = 1, y = 0;
    T z = 0, w = 1;
    T tmp = 0;
    while (b){
        T p = a/b, q = a%b;
        tmp = x - y * p; x = y; y = tmp;
        tmp = z - w * p; z = w; w = tmp;
        a = b; b = q;
    }
    return {x, z, a};
}

/// @brief 1/a mod Mを求める
template<typename T, typename U>
constexpr T inverse_mod(T a, U M){
    auto temp = axby1(a,(T)M);
    assert(temp[2] == 1);
    return (M+temp[0])%M;
}

/// @brief sqrt(a) mod Mを求める。ないなら-1が返される。
template<ll M>
inline constexpr ll cipolla(ll a){
    a %= M;
    if (M == 2) return a;
	if (a == 0) return 0;
    ll z = (M-1)/2;
    if (modpow<M>(a, z) != 1){return -1;}
    int b = 0;
    while (modpow<M>((b*b+M-a)%M, z) == 1){
        b++;
    }
    array<ll,2> x{1,0};
    array<ll,2> y{b, 1};
    ll w = (b*b+M-a)%M;
    z++;
    while (z){
        if (z&1){
            ll temp = x[0];
            x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
            if (x[0] >= M){x[0] -= M;}
            x[1] = temp*y[1]%M+x[1]*y[0]%M;
            if (x[1] >= M){x[1] -= M;}
        }
        ll temp = y[0];
        y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
        if (y[0] >= M){y[0] -= M;}
        y[1] = 2*temp*y[1]%M;
        z >>= 1;
    }
    return x[0];
}
inline constexpr ll cipolla(ll a, const ll M){
    a %= M;
    if (M == 2) return a;
	if (a == 0) return 0;
    ll z = (M-1)/2;
    if (modpow(a, z, M) != 1){return -1;}
    int b = 0;
    while (modpow((b*b+M-a)%M, z, M) == 1){
        b++;
    }
    array<ll,2> x{1,0};
    array<ll,2> y{b, 1};
    ll w = (b*b+M-a)%M;
    z++;
    while (z){
        if (z&1){
            ll temp = x[0];
            x[0] = x[0]*y[0]%M+x[1]*y[1]%M*w%M;
            if (x[0] >= M){x[0] -= M;}
            x[1] = temp*y[1]%M+x[1]*y[0]%M;
            if (x[1] >= M){x[1] -= M;}
        }
        ll temp = y[0];
        y[0] = y[0]*y[0]%M+y[1]*y[1]%M*w%M;
        if (y[0] >= M){y[0] -= M;}
        y[1] = 2*temp*y[1]%M;
        z >>= 1;
    }
    return x[0];
}

/// @brief x以下の最大の2冪を返す。0は0が返る。 
inline constexpr ull lowerpow2(ull x){
    if (x == 0){return 0;}
    return 1ull<<(63-__builtin_clzll(x));
}
/// @brief x以上の最小の2冪を返す。0は0が返る。 
inline constexpr ull upperpow2(ull x){
    if (x == 0){return 0;}
    if (x == 1){return 1;}
    return 1ull<<(64-__builtin_clzll(x-1));
}
/// @brief xのpopcountを求める 
inline constexpr int popcount(ull x){
    return __builtin_popcountll(x);
}
/// @brief xのbit lengthを求める。
inline constexpr int bit_length(ull x){
    if (x == 0){return 0;}
    return 64-__builtin_clzll(x);
}




#endif /* MATH_FUNCTION_HPP_ */

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using namespace std;

template <uint M>
struct constant_modint {
    static constexpr uint mod_value = M;
    uint val;
    constant_modint() : val(0) {}
    template <class T> constant_modint(T x) {
        ll y = (ll)(x % (ll)M);
        if (y < 0) y += M;
        val = y;
    }

    constant_modint& operator+=(const constant_modint& rhs) {
        val += rhs.val;
        if (val >= M) val -= M;
        return *this;
    }
    constant_modint& operator-=(const constant_modint& rhs) {
        if (val < rhs.val) val += M;
        val -= rhs.val;
        return *this;
    }
    constant_modint& operator*=(const constant_modint& rhs) {
        val = (ull)val * rhs.val % M;
        return *this;
    }
    constant_modint& operator/=(const constant_modint& rhs) {
        return *this *= rhs.inv();
    }

    constant_modint operator+() const { return *this; }
    constant_modint operator-() const { return constant_modint(0) - *this; }

    friend constant_modint operator+(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) += rhs; }
    friend constant_modint operator-(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) -= rhs; }
    friend constant_modint operator*(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) *= rhs; }
    friend constant_modint operator/(const constant_modint& lhs, const constant_modint& rhs) { return constant_modint(lhs) /= rhs; }

    friend bool operator==(const constant_modint& lhs, const constant_modint& rhs) { return lhs.val == rhs.val; }
    friend bool operator!=(const constant_modint& lhs, const constant_modint& rhs) { return lhs.val != rhs.val; }

    constant_modint pow(ull n) const {
        constant_modint res = 1, a = *this;
        while (n) {
            if (n&1) res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }
    constant_modint inv() const {
        return inverse_mod<ll,ll>(val, M);
    }

    friend std::ostream& operator<<(std::ostream& os, const constant_modint& m) {
        return os << m.val;
    }
    friend std::istream& operator>>(std::istream& is, constant_modint& m) {
        ll x;
        is >> x;
        m = constant_modint(x);
        return is;
    }
};

template <int id = -1>
struct dynamic_modint {
    uint val;
    static uint& mod() {
        static uint M = 998244353;
        return M;
    }
    static void set_mod(uint m) {
        mod() = m;
    }

    dynamic_modint() : val(0) {}
    template <class T> dynamic_modint(T x) {
        ll y = x % (ll)mod();
        if (y < 0) y += mod();
        val = (uint)y;
    }

    dynamic_modint& operator+=(const dynamic_modint& rhs) {
        val += rhs.val;
        if (val >= mod()) val -= mod();
        return *this;
    }
    dynamic_modint& operator-=(const dynamic_modint& rhs) {
        if (val < rhs.val) val += mod();
        val -= rhs.val;
        return *this;
    }
    dynamic_modint& operator*=(const dynamic_modint& rhs) {
        val = (ull)val * rhs.val % mod();
        return *this;
    }
    dynamic_modint& operator/=(const dynamic_modint& rhs) {
        return *this *= rhs.inv();
    }

    dynamic_modint operator+() const { return *this; }
    dynamic_modint operator-() const { return dynamic_modint(0) - *this; }

    friend dynamic_modint operator+(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) += rhs; }
    friend dynamic_modint operator-(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) -= rhs; }
    friend dynamic_modint operator*(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) *= rhs; }
    friend dynamic_modint operator/(const dynamic_modint& lhs, const dynamic_modint& rhs) { return dynamic_modint(lhs) /= rhs; }

    friend bool operator==(const dynamic_modint& lhs, const dynamic_modint& rhs) { return lhs.val == rhs.val; }
    friend bool operator!=(const dynamic_modint& lhs, const dynamic_modint& rhs) { return lhs.val != rhs.val; }

    dynamic_modint pow(ull n) const {
        dynamic_modint res = 1, a = *this;
        while (n) {
            if (n & 1) res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }
    dynamic_modint inv() const {
        ll a = val, b = mod(), u = 1, v = 0;
        while (b) {
            ll t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return dynamic_modint(u);
    }

    friend std::ostream& operator<<(std::ostream& os, const dynamic_modint& m) {
        return os << m.val;
    }
    friend std::istream& operator>>(std::istream& is, dynamic_modint& m) {
        ll x;
        is >> x;
        m = dynamic_modint(x);
        return is;
    }
};

#endif /* MODINT__HPP_ */

using mint = constant_modint<998244353>;

fastio::FastInput in;
fastio::FastOutput out;
#define cin do_not_use_cin

template<class... T> bool read(T&... values) { return in.read(values...); }
template<class... T> bool write(const T&... values) { return out.write(values...); }
template<class... T> bool print(const T&... values) { return out.print(values...); }
template<class... T> bool printflush(const T&... values) { return out.print(values...) && out.flush(); }
inline bool flush() { return out.flush(); }


template <typename INT>
pair<list<INT>, list<pair<INT, list<INT>>>> subtree_size(int N, const list<list<INT>>& E, int root) {
    list<bool> used(N, false);
    list<INT> res(N, 0);
    list<pair<INT, list<INT>>> res2;
    res2[root].first = -1;
    function<INT(INT)> dfs = [&](INT n) {
        used[n] = true;
        for (auto& w : E[n]) {
            if (used[w]) {
                continue;
            }
            res2[w].first = n;
            res2[n].second.append(w);
            res[n] += dfs(w);
        }
        res[n] += 1;
        return res[n];
    };
    used[root] = true;
    res[root] = dfs(root);
    return make_pair(res, res2);
}

/// @brief 線形篩
/// @attention コンストラクタに整数Nを渡すことでN以下の整数を扱うことができる。
struct LinearSieve{
    list<int> p_list;
    list<int> lpf;
    //Nを渡すことで1以上N以下の整数を扱うことができる
    LinearSieve(int N): lpf(N+1,-1){
        lpf[1] = 1;
        int p_list_size = 0;
        for (int i = 2; i <= N; i++){
            if (lpf[i] < 0){
                p_list.append(i);
                p_list_size++;
                lpf[i] = i;
            }
            for (int j = 0; j < p_list_size && p_list[j] <= lpf[i] && p_list[j]*i <= N; j++){
                lpf[p_list[j]*i] = p_list[j];
            }
        }
    }
    list<pii> factorize(int x){
        if (x == 1){return {{1,0}};}
        list<pii> r;
        do{
            if (r.empty() || lpf[x] != r.back()[0]){
                r.append({lpf[x], 1});
            }
            else{
                r.back()[1]++;
            }
            x /= lpf[x];
        }while(x > 1);
        return r;
    }
    list<list<pii>> factorize_all(int N){
        list<list<pii>> r(N+1);
        r[1].append({1,0});
        for (int i = 2; i <= N; i++){
            r[i] = factorize(i);
        }
        return r;
    }
    /// @brief N以下の整数に対するメビウス関数の値を列挙する。
    list<int> enumerate_mobius(int N){
        list<int> ret(N+1);
        ret[1] = 1;
        for (int i = 2; i <= N; i++){
            if (lpf[i] == i){ret[i] = -1; continue;}
            int temp = i/lpf[i];
            if (lpf[i] == lpf[temp]){
                ret[i] = 0;
            }
            else{
                ret[i] = ret[lpf[i]]*ret[temp];
            }
        }
        return ret;
    }
};

LinearSieve L(1000000);

void solve(){
    
    
    int N;
    in >> N;

    list<int> A(N);

    in >> A;

    list<list<int>> E(N);

    

    for (int i = 0; i < N-1; i++){
        int u,v;
        in >> u >> v;
        u--;
        v--;
        E[u].append(v);
        E[v].append(u);
    }

    list<bool> used(N, false);

    list<mint> ans(N, 0);

    function<pair<mint, unordered_map<int, int>>(int)> dfs = [&](int now){
        pair<mint, unordered_map<int, int>> temp;
        for (auto& p : L.factorize(A[now])){
            temp.second[p[0]] = p[1];
        }
        temp.first = A[now];
        for (int w : E[now]){
            if (used[w]){continue;}
            used[w] = true;
            auto temp2 = dfs(w);
            if (len(temp2.second) <= len(temp.second)){
                for (auto& [r,v] : temp2.second){
                    if (temp.second[r] < v){
                        temp.first *= mint(r).pow(v-temp.second[r]);
                        temp.second[r] = v;
                    }
                }
            }
            else{
                for (auto& [r,v] : temp.second){
                    if (temp2.second[r] < v){
                        temp2.first *= mint(r).pow(v-temp2.second[r]);
                        temp2.second[r] = v;
                    }
                }
                swap(temp, temp2);
            }
        }
        ans[now] = temp.first;
        return temp;
    };

    used[0] = true;
    dfs(0);

    for (int i = 0; i < N; i++){
        print(ans[i]);
    }


    
}

int main(){

    ll T = 1;
    // in >> T;
    while (T--){
        solve();
    }

}