結果
| 問題 | No.3250 最小公倍数 |
| コンテスト | |
| ユーザー |
 2251799813685248
|
| 提出日時 | 2026-11-05 19:58:54 |
| 言語 | C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 735 ms / 2,000 ms |
| + 988µs | |
| コード長 | 52,840 bytes |
| 記録 | |
| コンパイル時間 | 2,866 ms |
| コンパイル使用メモリ | 330,208 KB |
| 実行使用メモリ | 241,040 KB |
| 最終ジャッジ日時 | 2026-11-05 19:59:14 |
| 合計ジャッジ時間 | 18,328 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 |
ソースコード
// 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<uint> ans(N, 0);
function<pair<uint, unordered_map<int, int>>(int)> dfs = [&](int now){
pair<uint, 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 = temp.first*modpow<mod>(r, v-temp.second[r])%mod;
temp.second[r] = v;
}
}
}
else{
for (auto& [r,v] : temp.second){
if (temp2.second[r] < v){
temp2.first = temp2.first*modpow<mod>(r, v-temp2.second[r])%mod;
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();
}
}