Malha de Amplificadores

Uma malha de amplificadores é organizada na forma de uma árvore de $N$ vértices. Cada vértice $v$ contém um amplificador cujo comportamento é determinado por um par de coeficientes inteiros $(c_v,d_v)$. Quando um sinal de intensidade $x$ passa pelo amplificador do vértice $v$, sua nova intensidade é

$$c_vx+d_v \pmod{998244353}.$$

Você deve processar $Q$ operações de dois tipos:

• Consulta: um sinal de intensidade inicial $x$ percorre o caminho de $u$ até $v$. Determine sua intensidade final após passar, em ordem, por todos os amplificadores desse caminho, incluindo os dos vértices $u$ e $v$.
• Atualização: substitua os coeficientes de todos os amplificadores no caminho entre $u$ e $v$, incluindo os extremos, pelos valores $c$ e $d$ fornecidos.

Note que, em uma consulta, o amplificador de $u$ é aplicado primeiro e o de $v$ por último. Quando $u=v$, o sinal passa uma única vez pelo amplificador desse vértice.

Entrada

A primeira linha contém dois inteiros $N$ e $Q$ ($1 \le N,Q \le 200000$), o número de vértices e o número de operações, respectivamente.

Cada uma das próximas $N$ linhas contém dois inteiros $c_v$ e $d_v$ ($0 \le c_v,d_v < 998244353$), descrevendo os coeficientes iniciais do amplificador do vértice $v$, para $v=1,2,\ldots,N$.

Cada uma das próximas $N-1$ linhas contém dois inteiros $u$ e $v$ ($1 \le u,v \le N$), indicando uma aresta não direcionada entre esses vértices. As arestas formam uma árvore.

Cada uma das próximas $Q$ linhas descreve uma operação em um dos seguintes formatos:

• 1 u v x: determine a intensidade final de um sinal que começa com intensidade $x$ e percorre o caminho de $u$ até $v$, onde $0 \le x < 998244353$.
• 2 u v c d: para cada vértice $w$ no caminho entre $u$ e $v$, substitua seus coeficientes $(c_w,d_w)$ por $(c,d)$, onde $0 \le c,d < 998244353$.

Em todas as operações, $1 \le u,v \le N$.

Saída

Para cada operação do tipo 1, imprima uma linha contendo um único inteiro: a intensidade final do sinal módulo $998244353$.

2 5
2 1
3 4
1 2
1 1 2 2
1 2 1 2
2 1 1 1 5
1 1 2 3
1 1 1 0

19
21
28
5

5 7
1 1
2 0
1 3
3 1
1 2
1 2
1 3
3 4
3 5
1 2 4 2
2 2 4 1 1
1 2 4 0
1 5 4 3
2 1 5 2 0
1 2 4 4
1 5 2 1

25
4
7
21
9