Vertex Set Path Composite

Source: Library Checker

Version: Phuoc Hung OJ Extended

Problem

Each vertex of a tree stores an affine function $f(x)=ax+b$ modulo $998244353$. Support replacing the function at one vertex and evaluating the composition of functions along the directed path from $u$ to $v$, in path order.

Input

The first line contains $n$ and $q$. The next $n$ lines contain pairs $(a_i,b_i)$ describing $f_i(x)=a_ix+b_i$. The next $n-1$ lines contain 0-based edges. Each query is one of:

• 0 p c d: replace the function at vertex $p$ with $f_p(x)=cx+d$.
• 1 u v x: starting with $x$, apply the functions of the vertices on the path from $u$ to $v$ in that exact order.

Output

For each query of type 1, print the resulting value modulo $998244353$.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$.
• Vertex indices are 0-based.
• Every coefficient and query value belongs to $[0,998244353)$.

Example

Input

1 5
934920615 566121894
1 0 0 809158230
0 0 299738720 566523253
1 0 0 364937308
0 0 693007693 193053012
0 0 704915724 242410315

Output

135724921
823408647

Explanation

With one vertex, a type-1 query simply applies the current affine function stored at vertex 0 to the supplied value.