// yukicoder: No.650 行列木クエリ
// https://yukicoder.me/problems/no/650
//
// anmitsu クレートを単一ファイルへ展開したうえで、この問題から到達しない
// コードを tools/bundle.py が自動で枝刈りしたものである。ジャッジは外部
// クレートへの依存を解決できないため、このファイル単体で完結させている。

mod algebra {
    pub mod monoid {

        use crate::algebra::semi_group;

        pub trait Monoid: semi_group::SemiGroup {
            fn id() -> Self::S;
        }

    }

    pub mod semi_group {

        use std::cmp;

        pub trait SemiGroup {
            type S;

            fn op(a: &Self::S, b: &Self::S) -> Self::S;
        }

    }
}

mod modulo998244353 {

    pub mod convolution_mont {

        #![cfg(target_arch = "x86_64")]

        use std::{arch::x86_64, sync};

    }

}

mod ds {
    pub mod segment_tree {
        pub mod segment_tree_dense {

            use super::super::super::algebra::monoid::Monoid;

            // テストでのみ使用する追加のインポート. `monoid::AddMonoid` や `semi_group::SemiGroup` は
            // 実装本体では使用しないため, `#[cfg(test)]` で分離する.
            #[cfg(test)]
            use super::super::super::algebra::{monoid, semi_group};

            #[derive(Clone)]
            pub struct SegmentTreeDense<M>
            where
                M: Monoid,
            {
                len: usize,
                data: Vec<M::S>,
            }

            impl<M> SegmentTreeDense<M>
            where
                M: Monoid,
                M::S: Clone,
            {
                pub fn new(n: usize) -> Self {
                    let len = n;
                    // The size of the internal data vector is 2*len - 1 for a complete binary tree.
                    // Handle the case where len is 0 to avoid underflow.
                    SegmentTreeDense::<M> {
                        len,
                        data: vec![M::id(); if len == 0 { 0 } else { 2 * len - 1 }],
                    }
                }

                pub fn len(&self) -> usize {
                    self.len
                }

                pub fn set(&mut self, mut idx: usize, x: M::S) {
                    assert!(
                        idx < self.len(),
                        "index out of bounds: the len is {} but the index is {}",
                        self.len(),
                        idx
                    );
                    // Calculate the position in the data vector corresponding to the leaf node.
                    idx += self.len - 1;
                    self.data[idx] = x;
                }

                pub fn build(&mut self) {
                    // Iterate from the last parent node down to the root.
                    for idx in (0..self.len - 1).rev() {
                        // Update parent node with the result of the monoid operation on its children.
                        self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
                    }
                }

                pub fn update(&mut self, mut idx: usize, x: M::S) {
                    assert!(
                        idx < self.len(),
                        "index out of bounds: the len is {} but the index is {}",
                        self.len(),
                        idx
                    );
                    // Calculate leaf position and update its value.
                    idx += self.len - 1;
                    self.data[idx] = x;
                    // Climb up the tree updating parent nodes.
                    while idx > 0 {
                        idx = (idx - 1) / 2;
                        self.data[idx] = M::op(&self.data[2 * idx + 1], &self.data[2 * idx + 2]);
                    }
                }

                pub fn fold(&self, mut l: usize, mut r: usize) -> M::S {
                    if l >= r {
                        return M::id();
                    }

                    assert!(
                        r <= self.len(),
                        "index out of bounds: r must be less than or equal to the len (r: {}, len: {})",
                        r,
                        self.len()
                    );

                    // Map logical indices to internal data array indices.
                    l += self.len - 1;
                    r += self.len - 1;

                    let mut sum_l = M::id();
                    let mut sum_r = M::id();

                    // Fold elements within [l, r).
                    while l < r {
                        if l % 2 == 0 {
                            sum_l = M::op(&sum_l, &self.data[l]);
                        }
                        if r % 2 == 0 {
                            sum_r = M::op(&self.data[r - 1], &sum_r);
                        }
                        l /= 2;
                        r = (r - 1) / 2;
                    }

                    M::op(&sum_l, &sum_r)
                }

            }
        }
    }

}

mod graph {
    pub mod bellman_ford {

        use super::graph;
        use std::collections;

        impl<T: Copy + Ord + std::ops::Add<Output = T>> graph::Graph<T> {
        }

        impl<T> graph::Graph<T> {
        }
    }

    pub mod bfs {

        use super::graph;
        use std::collections;

        impl<T> graph::Graph<T> {
        }
    }

    pub mod bipartite {

        use super::graph;
        use std::collections;

        impl<T> graph::Graph<T> {
        }
    }

    pub mod centroid_decomposition {

        use std::collections;

        use super::graph::{self, NotATreeError};

        impl<T> graph::Graph<T> {

        }
    }

    pub mod dfs {

        use super::graph;

        impl<T> graph::Graph<T> {
        }

        impl<T> graph::Graph<T> {
        }
    }

    pub mod dijkstra {

        use super::graph;
        use std::{cmp, collections};

        impl<T: Copy + Ord + std::ops::Add<Output = T>> graph::Graph<T> {
        }

        impl<T> graph::Graph<T> {
        }
    }

    pub mod eulerian_path {

        use super::graph;

        impl<T> graph::Graph<T> {
        }
    }

    pub mod floyd_warshall {

        use super::graph;

        impl<T: Copy + Ord + std::ops::Add<Output = T>> graph::Graph<T> {
        }

        impl<T> graph::Graph<T> {
        }
    }

    pub mod graph {

        pub struct Graph<T> {
            pub(super) edges: Vec<Vec<(u32, T)>>,
        }

        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub enum NotATreeError {
            Disconnected,
            HasCycle,
        }

        pub(super) fn validate_tree<T>(g: &Graph<T>, root: usize) -> Result<(), NotATreeError> {
            let n = g.vertex_count();

            // root から到達できる頂点を反復深さ優先探索で辿り、親および各頂点の
            // 子の本数を記録する。
            let mut parent: Vec<Option<usize>> = vec![None; n];
            let mut child_count = vec![0_usize; n];
            let mut visited = vec![false; n];
            visited[root] = true;
            let mut visited_count = 1;

            let mut stack = vec![root];
            while let Some(u) = stack.pop() {
                for (v, _) in g.edges(u) {
                    if !visited[v] {
                        visited[v] = true;
                        visited_count += 1;
                        parent[v] = Some(u);
                        child_count[u] += 1;
                        stack.push(v);
                    }
                }
            }

            if visited_count < n {
                return Err(NotATreeError::Disconnected);
            }

            // 各頂点の出次数が「親への1本 (根では0本) + 子の本数」とちょうど
            // 一致することを確認する。多重辺や、対応する逆辺を欠いた辺があると、
            // ここで不一致が生じる。
            for u in 0..n {
                let expected_out_degree = usize::from(parent[u].is_some()) + child_count[u];
                if g.out_degree(u) != expected_out_degree {
                    return Err(NotATreeError::HasCycle);
                }
            }

            Ok(())
        }

        impl<T> Graph<T> {
            #[must_use]
            pub fn new(n: usize) -> Self {
                // vec![Vec::new(); n] は Vec<T> の Clone (延いては T: Clone) を要求してしまう。
                // T に不要な制約を課さないよう、n 回 Vec::new() を呼び出す形で初期化する。
                Graph {
                    edges: (0..n).map(|_| Vec::new()).collect::<Vec<Vec<(u32, T)>>>(),
                }
            }

            pub fn vertex_count(&self) -> usize {
                self.edges.len()
            }

            pub fn out_degree(&self, u: usize) -> usize {
                self.edges[u].len()
            }

            pub fn edges(&self, u: usize) -> impl Iterator<Item = (usize, &T)> {
                self.edges[u]
                    .iter()
                    .map(|(dst, payload)| (*dst as usize, payload))
            }

            pub fn add_edge(&mut self, src: usize, dst: usize, payload: T) {
                debug_assert!(dst < self.vertex_count());
                self.edges[src].push((dst as u32, payload));
            }
        }

        impl<T: Clone> Graph<T> {
            pub fn add_undirected_edge(&mut self, u: usize, v: usize, payload: T) {
                self.add_edge(u, v, payload.clone());
                self.add_edge(v, u, payload);
            }
        }

        impl<T: Copy> Graph<T> {
        }
    }

    pub mod hld {

        use super::graph::{self, NotATreeError};

        #[derive(Debug, Clone, Copy, PartialEq, Eq)]
        pub enum PathDirection {
            Forward,
            Reversed,
        }

        enum Frame {
            Enter(usize, Option<usize>),
            Leave(usize, Option<usize>),
        }

        pub struct Hld {
            root: usize,
            parent: Vec<Option<usize>>,
            depth: Vec<usize>,
            head: Vec<usize>,
            id: Vec<usize>,
            order: Vec<usize>,
            subtree_size: Vec<usize>,
        }

        impl Hld {

            pub fn depth(&self, v: usize) -> usize {
                self.depth[v]
            }

            pub fn vertex_id(&self, v: usize) -> usize {
                self.id[v]
            }

            pub fn edge_path_ranges(&self, u: usize, v: usize) -> Vec<(usize, usize, PathDirection)> {
                self.path_ranges(u, v, true)
            }

            fn path_ranges(
                &self,
                mut u: usize,
                mut v: usize,
                exclude_lca: bool,
            ) -> Vec<(usize, usize, PathDirection)> {
                // u_ranges/v_ranges は、それぞれ u/v が LCA に向かって登る際に
                // 通過する区間を、登った順に集めたものである。いずれも「番号の
                // 降順に読む」区間として扱う。
                let mut u_ranges = Vec::new();
                let mut v_ranges = Vec::new();

                // 異なるパスに属する間は、パスの根元がより深い側の区間を切り出し、
                // その親へ引き上げる。u と v の値そのものは入れ替えず、どちら側の
                // 登りとして記録するかだけを、そのつど判定する。
                while self.head[u] != self.head[v] {
                    if self.depth[self.head[u]] >= self.depth[self.head[v]] {
                        u_ranges.push((self.id[self.head[u]], self.id[u] + 1));
                        u = self.parent[self.head[u]].unwrap();
                    } else {
                        v_ranges.push((self.id[self.head[v]], self.id[v] + 1));
                        v = self.parent[self.head[v]].unwrap();
                    }
                }

                // 同じパスに入った時点で、浅い方が LCA になる。深い方の登りの列に、
                // LCA までの最後の区間を追加する。
                let (deeper_ranges, lca_id, deep_id) = if self.id[u] <= self.id[v] {
                    (&mut v_ranges, self.id[u], self.id[v])
                } else {
                    (&mut u_ranges, self.id[v], self.id[u])
                };
                let start = if exclude_lca { lca_id + 1 } else { lca_id };
                if start <= deep_id {
                    deeper_ranges.push((start, deep_id + 1));
                }

                // u 側は登った順のまま (降順に読む) 連結し、v 側は逆順にして
                // (昇順に読む区間として) 連結する。
                let mut ranges: Vec<(usize, usize, PathDirection)> = u_ranges
                    .into_iter()
                    .map(|(l, r)| (l, r, PathDirection::Reversed))
                    .collect();
                ranges.extend(
                    v_ranges
                        .into_iter()
                        .rev()
                        .map(|(l, r)| (l, r, PathDirection::Forward)),
                );
                ranges
            }
        }

        impl<T> graph::Graph<T> {
            pub fn try_hld(&self, root: usize) -> Result<Hld, NotATreeError> {
                graph::validate_tree(self, root)?;

                let n = self.vertex_count();

                // 第1段階: 深さ・親・部分木サイズを求める。木であることは検証済み
                // のため、ここでは反復深さ優先探索でそのまま辿るだけでよい。
                let mut parent: Vec<Option<usize>> = vec![None; n];
                let mut depth = vec![0; n];
                let mut subtree_size = vec![1; n];

                let mut stack = vec![Frame::Enter(root, None)];
                while let Some(frame) = stack.pop() {
                    match frame {
                        Frame::Enter(u, p) => {
                            stack.push(Frame::Leave(u, p));
                            parent[u] = p;
                            if let Some(p) = p {
                                depth[u] = depth[p] + 1;
                            }
                            for (v, _) in self.edges(u) {
                                if Some(v) != p {
                                    stack.push(Frame::Enter(v, Some(u)));
                                }
                            }
                        }
                        Frame::Leave(u, p) => {
                            if let Some(p) = p {
                                subtree_size[p] += subtree_size[u];
                            }
                        }
                    }
                }

                // 第2段階: 各頂点について、部分木サイズが最大の子 (重い子) を求める。
                let mut heavy_child: Vec<Option<usize>> = vec![None; n];
                for (u, heavy_child) in heavy_child.iter_mut().enumerate() {
                    for (v, _) in self.edges(u) {
                        if parent[v] == Some(u) {
                            let is_heavier = match *heavy_child {
                                Some(current) => subtree_size[v] > subtree_size[current],
                                None => true,
                            };
                            if is_heavier {
                                *heavy_child = Some(v);
                            }
                        }
                    }
                }

                // 第3段階: 重い子を優先して辿ることで、パスに沿って連続した番号を
                // 割り振る。スタックが後入れ先出しであることを利用し、軽い子を先に、
                // 重い子を最後に積むことで、重い子を次に処理させ、同じパスの番号を
                // 連続させる。
                let mut id = vec![0; n];
                let mut order = vec![0; n];
                let mut head = vec![0; n];
                let mut counter = 0;
                let mut stack = vec![(root, root)];
                while let Some((u, chain_head)) = stack.pop() {
                    id[u] = counter;
                    order[counter] = u;
                    head[u] = chain_head;
                    counter += 1;

                    for (v, _) in self.edges(u) {
                        if parent[v] == Some(u) && Some(v) != heavy_child[u] {
                            // 軽い子は、そこを頭とする新しいパスを始める。
                            stack.push((v, v));
                        }
                    }
                    if let Some(v) = heavy_child[u] {
                        stack.push((v, chain_head));
                    }
                }

                Ok(Hld {
                    root,
                    parent,
                    depth,
                    head,
                    id,
                    order,
                    subtree_size,
                })
            }
        }
    }

    pub mod hld_path_query {

        use super::super::algebra::monoid::Monoid;
        use super::super::ds::segment_tree::segment_tree_dense::SegmentTreeDense;
        use super::hld::{Hld, PathDirection};

        pub struct HldPathQuery<'a, M: Monoid>
        where
            M::S: Clone,
        {
            hld: &'a Hld,
            forward: SegmentTreeDense<M>,
            reversed: SegmentTreeDense<M>,
        }

        impl<'a, M: Monoid> HldPathQuery<'a, M>
        where
            M::S: Clone,
        {
            pub fn new(hld: &'a Hld, values: &[M::S]) -> Self {
                let n = values.len();
                let mut forward = SegmentTreeDense::<M>::new(n);
                let mut reversed = SegmentTreeDense::<M>::new(n);
                for (v, value) in values.iter().enumerate() {
                    let id = hld.vertex_id(v);
                    forward.set(id, value.clone());
                    reversed.set(n - 1 - id, value.clone());
                }
                forward.build();
                reversed.build();
                Self {
                    hld,
                    forward,
                    reversed,
                }
            }

            pub fn set_vertex(&mut self, v: usize, x: M::S) {
                let n = self.forward.len();
                let id = self.hld.vertex_id(v);
                self.forward.update(id, x.clone());
                self.reversed.update(n - 1 - id, x);
            }

            pub fn set_edge(&mut self, u: usize, v: usize, x: M::S) {
                let child = if self.hld.depth(u) > self.hld.depth(v) {
                    u
                } else {
                    v
                };
                self.set_vertex(child, x);
            }

            pub fn fold_edge_path(&self, u: usize, v: usize) -> M::S {
                self.fold_ranges(self.hld.edge_path_ranges(u, v))
            }

            fn fold_ranges(&self, ranges: Vec<(usize, usize, PathDirection)>) -> M::S {
                let n = self.forward.len();
                // 区間の列を先頭から順に畳み込んでいく。acc がここまでの畳み込み
                // 結果であり、区間ごとの値を M::op で右から結合していく。
                ranges.into_iter().fold(M::id(), |acc, (l, r, dir)| {
                    // 区間の向きに応じて、参照するセグメント木を使い分ける。番号の
                    // 昇順に読みたい区間 (Forward) はそのまま forward から、降順に
                    // 読みたい区間 (Reversed) は、番号を反転させて構築してある
                    // reversed から、対応する反転後の区間 [n-r, n-l) を取り出す。
                    let value = match dir {
                        PathDirection::Forward => self.forward.fold(l, r),
                        PathDirection::Reversed => self.reversed.fold(n - r, n - l),
                    };
                    M::op(&acc, &value)
                })
            }
        }
    }

    pub mod johnson {

        use super::{dijkstra, graph};

        impl<T: Copy + Ord + std::ops::Add<Output = T> + std::ops::Sub<Output = T>> graph::Graph<T> {
        }

        impl<T> graph::Graph<T> {
        }
    }

    pub mod low_link {

        use super::graph;

        impl<T> graph::Graph<T> {
        }
    }

    pub mod mst {

        use super::graph;

        impl<T: Copy + Ord> graph::Graph<T> {
        }

        impl<T> graph::Graph<T> {
        }
    }

    pub mod scc {

        use super::graph;

        impl<T> graph::Graph<T> {
        }
    }

    pub mod topological_sort {

        use super::graph;
        use std::collections;

        impl<T> graph::Graph<T> {
        }
    }

    pub mod tree_diameter {

        use super::graph;

        impl<T> graph::Graph<T> {

        }

        impl<T> graph::Graph<T> {

        }

        impl<T: Copy + Ord + std::ops::Add<Output = T> + Default> graph::Graph<T> {

        }
    }

    pub mod zero_one_bfs {

        use super::graph;
        use std::collections;

        impl<T> graph::Graph<T> {
        }
    }
}

mod io {
    pub mod fastio {

        use std::{ffi, fs, io, ptr};

        #[cfg(target_os = "linux")]
        use std::os::unix;

        const OUT_BUF_SIZE: usize = 1 << 18;

        const OUT_BUF_FLUSH_THRESHOLD: usize = 32;

        const OUT_FLUSH_LIMIT: usize = OUT_BUF_SIZE - OUT_BUF_FLUSH_THRESHOLD;

        fn is_8digits(mut bytes: u64) -> bool {
            // 各バイトから '0' (0x30) を引き、上位ニブルが 0x30 になるかを見る代わりに、
            // 0x30 との XOR を取ってから数字部分 (下位ニブル) を無視するマスクをかける。
            // 数字であれば上位ニブルが 0 になり、全バイトの上位ニブルが 0 なら bytes は 0 になる。
            bytes ^= 0x3030303030303030;
            bytes &= 0xf0f0f0f0f0f0f0f0;
            bytes == 0
        }

        fn parse_8digits(bytes: u64) -> u32 {
            debug_assert!(is_8digits(bytes));

            // SWAR (SIMD Within A Register) 法により、8 バイトの数字列を 3 段階の
            // 乗算とビットシフトだけで 32 bit 整数へまとめて変換する。
            // 各段階で隣接する 2 桁分の値を 1 つのフィールドへ合成していく。
            let v1 = (bytes & 0x0f0f0f0f0f0f0f0f).wrapping_mul(0xA01) >> 8;
            let v2 = (v1 & 0x00ff00ff00ff00ff).wrapping_mul(0x640001) >> 16;
            let v3 = (v2 & 0x0000ffff0000ffff).wrapping_mul(0x271000000001) >> 32;
            v3 as u32
        }

        pub trait FastWrite {
            fn write_to(self, io: &mut Fastio);

            fn writeln_to(self, io: &mut Fastio);
        }

        pub struct Fastio {
            in_cursor: *const u8,

            out_buf: Vec<u8>,

            out_pos: usize,

            out_capture: Option<Vec<u8>>,

            _input_storage: Vec<u8>,
        }

        impl Fastio {
            fn with_storage(mut input_storage: Vec<u8>, out_capture: Option<Vec<u8>>) -> Self {
                // 8 桁ずつのパースの際に、末尾でメモリ外アクセスを起こさないよう、末尾に十分な番兵を追加しておく。
                // 番兵には 0x00 を用いる。0x00 は数字 ('0'..='9') にならないため is_8digits は確実に false を
                // 返し、かつ ASCII の空白文字 (0x20 以下) の範囲にも収まるため、chars や整数パースの
                // 「空白以外/数字が続く間読み進める」ループも番兵の手前で正しく止まる。この 0x00 は、
                // mmap 経路においてファイル末尾を含む最終ページの端数部分が OS によりゼロ埋めされる挙動とも
                // 一致しており、両経路で番兵の性質を揃えられる。
                input_storage.extend_from_slice(&[0_u8; 8]);
                let in_cursor = input_storage.as_ptr();
                Self {
                    in_cursor,
                    out_buf: vec![0_u8; OUT_BUF_SIZE],
                    out_pos: 0,
                    out_capture,
                    _input_storage: input_storage,
                }
            }

            pub fn new() -> Self {
                #[cfg(target_os = "linux")]
                unsafe {
                    const PROT_READ: i32 = 0x1;
                    const MAP_PRIVATE: i32 = 0x02;
                    const MAP_FAILED: *mut ffi::c_void = (-1isize) as *mut ffi::c_void;

                    // /dev/stdin を通常ファイルとして開けない、あるいは mmap に失敗した場合は、
                    // 'mmap_try ブロックを抜けてフォールバック経路へ進む。
                    'mmap_try: {
                        let Ok(file) = fs::File::open("/dev/stdin") else {
                            break 'mmap_try;
                        };
                        let Ok(metadata) = file.metadata() else {
                            break 'mmap_try;
                        };
                        if !metadata.is_file() {
                            break 'mmap_try;
                        }

                        let len = metadata.len() as usize;
                        let fd = unix::io::AsRawFd::as_raw_fd(&file);
                        let addr = ptr::null_mut();
                        let mapped = mmap(addr, len, PROT_READ, MAP_PRIVATE, fd, 0);
                        if mapped == MAP_FAILED {
                            break 'mmap_try;
                        }

                        // mmap されたメモリ領域を直接読み取り対象とすることで、
                        // 標準入力全体をヒープへコピーするコストを避ける。
                        let in_cursor = mapped as *const u8;
                        return Self {
                            in_cursor,
                            out_buf: vec![0_u8; OUT_BUF_SIZE],
                            out_pos: 0,
                            out_capture: None,
                            _input_storage: vec![],
                        };
                    }
                }

                // mmap が使えない環境向けのフォールバック経路。標準入力を最後まで読み切って保持する。
                let mut input_storage = vec![];
                io::Read::read_to_end(&mut io::stdin().lock(), &mut input_storage)
                    .expect("failed to read from source");
                Self::with_storage(input_storage, None)
            }

            pub fn char(&mut self) -> char {
                unsafe {
                    self.skip_whitespace();
                    let ch = *self.in_cursor as char;
                    self.in_cursor = self.in_cursor.add(1);
                    ch
                }
            }

            pub fn u64(&mut self) -> u64 {
                unsafe {
                    self.skip_whitespace();
                    let mut value = 0_u64;
                    loop {
                        let bytes = ptr::read_unaligned(self.in_cursor as *const u64);
                        if !is_8digits(bytes) {
                            break;
                        }
                        value = value * 100_000_000_u64 + parse_8digits(bytes) as u64;
                        self.in_cursor = self.in_cursor.add(8);
                    }

                    while *self.in_cursor >= b'0' {
                        value = 10 * value + (*self.in_cursor - b'0') as u64;
                        self.in_cursor = self.in_cursor.add(1);
                    }
                    value
                }
            }

            pub fn u32(&mut self) -> u32 {
                unsafe {
                    self.skip_whitespace();
                    let mut value = 0_u32;
                    loop {
                        let bytes = ptr::read_unaligned(self.in_cursor as *const u64);
                        if !is_8digits(bytes) {
                            break;
                        }
                        value = value * 100_000_000 + parse_8digits(bytes);
                        self.in_cursor = self.in_cursor.add(8);
                    }

                    while *self.in_cursor >= b'0' {
                        value = 10 * value + (*self.in_cursor - b'0') as u32;
                        self.in_cursor = self.in_cursor.add(1);
                    }
                    value
                }
            }

            pub fn flush(&mut self) {
                self.out_flush();
            }

            #[inline(always)]
            fn out_flush(&mut self) {
                self.try_out_flush()
                    .expect("failed to write buffered output");
            }

            fn try_out_flush(&mut self) -> io::Result<()> {
                if self.out_pos == 0 {
                    return Ok(());
                }

                // キャプチャモードの場合は、標準出力ではなくメモリ上のバッファへ書き写す。
                if let Some(capture) = &mut self.out_capture {
                    capture.extend_from_slice(&self.out_buf[..self.out_pos]);
                    self.out_pos = 0;
                    return Ok(());
                }

                #[cfg(target_os = "linux")]
                unsafe {
                    // write(2) は一度の呼び出しで全バイトを書き込むとは限らないため、
                    // 書き込み済みバイト数が対象範囲に達するまでループする。
                    let mut written = 0_usize;
                    let base = self.out_buf.as_ptr();
                    while written < self.out_pos {
                        let n = write(
                            1,
                            base.add(written) as *const ffi::c_void,
                            self.out_pos - written,
                        );
                        if n < 0 {
                            return Err(io::Error::last_os_error());
                        }
                        written += n as usize;
                    }
                }

                #[cfg(not(target_os = "linux"))]
                {
                    let mut stdout = io::stdout().lock();
                    io::Write::write_all(&mut stdout, &self.out_buf[..self.out_pos])?;
                    io::Write::flush(&mut stdout)?;
                }

                self.out_pos = 0;
                Ok(())
            }

            #[inline(always)]
            fn out_maybe_flush(&mut self) {
                if self.out_pos > OUT_FLUSH_LIMIT {
                    self.out_flush();
                }
            }

            pub fn write<T>(&mut self, value: T)
            where
                T: FastWrite,
            {
                value.write_to(self);
            }

            #[inline(always)]
            unsafe fn skip_whitespace(&mut self) {
                unsafe {
                    while *self.in_cursor <= b' ' {
                        self.in_cursor = self.in_cursor.add(1);
                    }
                }
            }
        }

        impl Drop for Fastio {
            fn drop(&mut self) {
                // プロセス終了時の取りこぼしを防ぐため、可能な限り残りを出力する。
                // Drop からはエラーを返せないため、失敗は握りつぶす。
                let _ = self.try_out_flush();
            }
        }

        impl FastWrite for char {
            fn write_to(self, io: &mut Fastio) {
                io.out_buf[io.out_pos] = self as u8;
                io.out_pos += 1;
                io.out_maybe_flush();
            }

            fn writeln_to(self, io: &mut Fastio) {
                io.out_buf[io.out_pos] = self as u8;
                io.out_pos += 1;
                io.out_buf[io.out_pos] = b'\n';
                io.out_pos += 1;
                io.out_maybe_flush();
            }
        }

        #[cfg(target_os = "linux")]
        #[link(name = "c")]
        unsafe extern "C" {
            fn mmap(
                addr: *mut ffi::c_void,
                length: usize,
                prot: i32,
                flags: i32,
                fd: i32,
                offset: isize,
            ) -> *mut ffi::c_void;

            fn write(fd: i32, buf: *const ffi::c_void, count: usize) -> isize;
        }
    }
}

use algebra::monoid::Monoid;
use algebra::semi_group::SemiGroup;
use graph::graph::Graph;
use graph::hld_path_query::HldPathQuery;
use io::fastio::Fastio;

const MOD: u64 = 1_000_000_007;

// この問題専用の 2x2 行列モノイド。root 側を左、leaf 側を右にして掛け合わせる
// 規約であり, op(a, b) は「a の後ろに b を掛ける (a * b)」を表す。
struct Matrix2x2Monoid;

impl SemiGroup for Matrix2x2Monoid {
    type S = [[u64; 2]; 2];
    fn op(a: &Self::S, b: &Self::S) -> Self::S {
        let mut c = [[0_u64; 2]; 2];
        for (i, row) in c.iter_mut().enumerate() {
            for (j, cell) in row.iter_mut().enumerate() {
                let mut sum = 0_u128;
                for k in 0..2 {
                    sum += u128::from(a[i][k]) * u128::from(b[k][j]);
                }
                *cell = (sum % u128::from(MOD)) as u64;
            }
        }
        c
    }
}

impl Monoid for Matrix2x2Monoid {
    fn id() -> Self::S {
        [[1, 0], [0, 1]]
    }
}

// Fastio の数値書き込みは write/writeln のどちらを使っても改行文字まで出力してしまうため、
// この問題のように「行列の4要素を同じ行に並べる」形式には使えない。
// char の書き込みだけは改行を伴わないため、あらかじめ文字列化したトークン列を
// 1文字ずつ書き込むことで、任意の内容を1行にまとめて出力する。
fn write_line(io: &mut Fastio, tokens: &[String]) {
    for (i, token) in tokens.iter().enumerate() {
        if i > 0 {
            io.write(' ');
        }
        for c in token.chars() {
            io.write(c);
        }
    }
    io.write('\n');
}

fn main() {
    let mut io = Fastio::new();

    let n = io.u32() as usize;
    let edges = (0..n - 1)
        .map(|_| {
            let a = io.u32() as usize;
            let b = io.u32() as usize;
            (a, b)
        })
        .collect::<Vec<(usize, usize)>>();

    let mut g = Graph::new(n);
    for &(a, b) in &edges {
        g.add_undirected_edge(a, b, ());
    }

    let hld = g.try_hld(0).unwrap();
    // 各辺の初期値は単位行列であり、頂点の初期値としても (どの頂点が
    // どの辺に対応するかによらず) 同じ値になる。
    let identity = Matrix2x2Monoid::id();
    let mut path_query = HldPathQuery::<Matrix2x2Monoid>::new(&hld, &vec![identity; n]);

    let q = io.u32() as usize;
    for _ in 0..q {
        let kind = io.char();
        if kind == 'x' {
            let i = io.u32() as usize;
            let x00 = io.u64();
            let x01 = io.u64();
            let x10 = io.u64();
            let x11 = io.u64();
            let (a, b) = edges[i];
            path_query.set_edge(a, b, [[x00, x01], [x10, x11]]);
        } else {
            let i = io.u32() as usize;
            let j = io.u32() as usize;
            let m = path_query.fold_edge_path(i, j);
            write_line(
                &mut io,
                &[
                    m[0][0].to_string(),
                    m[0][1].to_string(),
                    m[1][0].to_string(),
                    m[1][1].to_string(),
                ],
            );
        }
    }

    io.flush();
}