"Human database" Little Q is very diligent in solving problems, having solved over ten thousand. Whenever someone asks him for help with a problem, Little Q can always identify which OJ and which problem it is within 1 second. Therefore, Little Q is considered a "original problem search engine."

One day, Little Q came to a rooted tree with $n$ nodes, where the root is node 1, and each node is imprinted with a problem. With his massive collection of problems, Little Q quickly identified the source of each problem and discovered that some problems had been copied multiple times. He classified the problems on each node; the problem type of the $i$-th node is $a_i$, and the problem source of node $i$ and node $j$ is the same if and only if $a_i = a_j$.

Solving the same problem multiple times, other than increasing the AC count, does not improve one's own level. To investigate the quality of the problems in this tree, Little Q will continuously ask the following two types of queries $m$ times:

• $1 \ x \ y$: If you solve all the problems corresponding to all nodes 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 the 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 expressed in the form $\frac{ans}{cnt_A \times cnt_B}$, you only need to tell him the value of $ans$.

Identifying these problems consumed too much of Little Q's energy, and he has no way to calculate the answers to these simple queries himself. Please write a program to answer all $m$ of Little Q's questions.

Input

The first line contains a positive integer $T$, representing the number of test cases.

The first line of each test case contains 5 positive integers $n, p, SA, SB, SC$, where $n$ represents the number of nodes in the tree.

To reduce the input size to some extent, the tree edges and the problem type $a[]$ of each node 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$, representing 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

For each test case, output $m$ lines, each containing an integer, answering each query in order.

Examples

Input 1

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

Output 1

1
5
1
4
34
61
45
3

Note

• $1 \le T \le 3$, $2 \le p \le n \le 100000$, $1 \le m \le 200000$.
• $10000 \le SA, SB, SC \le 1000000$, $1 \le x, y, A, B \le n$.

Subtask 1 (30 points): Contains only type 1 queries. Subtask 2 (30 points): Satisfies $p = n$. Subtask 3 (40 points): No additional restrictions.