Description

“Human problem database” Little $Q$ practices very hard and has solved over ten thousand problems. Whenever someone asks him about a problem, Little $Q$ can tell within $1$ second which $OJ$ and which problem it is. Therefore, Little $Q$ is like an “original problem search engine”.

One day, Little $Q$ came to a rooted tree with $n$ nodes. The root is node $1$, and each node has a problem printed on it. With his huge amount of experience, Little $Q$ quickly identified the source of every problem, and found that some problems had been reposted many times. He classified the problem on each node: the problem type of node $i$ is $a_i$. The problems at node $i$ and node $j$ come from the same source if and only if $a_i = a_j$.

Solving the same problem multiple times does not improve skill, except increasing the number of $AC$ submissions. To investigate the quality of the problems on this tree, Little $Q$ will ask the following two types of queries for a total of $m$ times:

• $1$ $x$ $y$: If you solve all problems on the shortest path from node $x$ to node $y$ (including $x$ and $y$), how many essentially different problems can you solve in total?

• $2$ $A$ $B$: If you choose a node $x$ uniformly at random on the shortest path from node $A$ to the root (including $A$ and the root), and choose a node $y$ uniformly at random on the shortest path from node $B$ to the root (including $B$ and the root), what is the expected answer to query $1$ $x$ $y$?

Let $cnt_x$ denote the number of nodes on the shortest path from node $x$ to the root. Since Little $Q$ does not like fractions, and the answer to the second type of query can always be written as $\frac{ans}{{cnt_A}\times{cnt_B}}$, you only need to output the value of $ans$.

Identifying these problems has consumed too much of Little $Q$’s energy, so he cannot compute the answers to these simple queries by himself. Please write a program to answer all $m$ queries for Little $Q$.

Input Format

The first line contains a positive integer $T$, denoting the number of testdata.

For each testdata, the first line contains $5$ positive integers $n, p, SA, SB, SC$, where $n$ is the number of nodes in the tree.

To reduce the input size to some extent, the tree edges and the problem type array $a[]$ will be generated by the following code:

unsigned int SA, SB, SC;
unsigned int rng61(){
	SA ^= SA << 16;
	SA ^= SA >> 5;
	SA ^= SA << 1;
	unsigned int t = SA;
	SA = SB;
	SB = SC;
	SC ^= t ^ SA;
	return SC;
}
void gen(){
	scanf("%d%d%u%u%u", &n, &p, &SA, &SB, &SC);
	for(int i = 2; i <= p; i++)
	addedge(i - 1, i);
	for(int i = p + 1; i <= n; i++)
	addedge(rng61() % (i - 1) + 1, i);
	for(int i = 1; i <= n; i++)
	a[i] = rng61() % n + 1;
}

The second line contains a positive integer $m$, denoting the number of queries.

The next $m$ lines each contain $3$ positive integers, in the form $1$ $x$ $y$ or $2$ $A$ $B$, representing each query in order.

Output Format

For each testdata, output $m$ lines, one integer per line, answering each query in order.

2
5 3 10000 12345 54321
3
1 2 3
2 1 3
1 3 2
10 6 23456 77777 55555
5
1 1 10
2 3 5
2 7 5
2 5 4
1 8 6

1
5
1
4
34
61
45
3

Hint

• $1 \le T \le 3,2 \le p \le n \le 10^5,1 \le m \le 2\times 10^5$.
• $10^4 \le SA, SB, SC \le 10^6,1 \le x, y, A, B \le n$.

Subtask $1$ ($30$ points): only contains type $1$ queries.

Subtask $2$ ($30$ points): satisfies $p = n$.

Subtask $3$ ($40$ points): no additional constraints.

Translated by ChatGPT 5