G. Gathering Mushrooms
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

BaoBao is picking mushrooms in a forest. There are $$$n$$$ locations in the forest, and in the $$$i$$$-th location there grows an infinite amount of mushrooms of type $$$t_i$$$. Each location also has a wooden sign. The sign of the $$$i$$$-th location points to location $$$a_i$$$ (it is possible that $$$a_i = i$$$).

As it is very foggy in the forest, BaoBao decides to move between locations according to the signs just for safety. Starting from location $$$s$$$ with an empty basket, each time BaoBao walks into a location $$$c$$$ (including the starting location $$$c = s$$$, and regardless of whether he has visited location $$$c$$$ before), he will pick one mushroom of type $$$t_c$$$ into his basket and move to location $$$a_c$$$.

Given an integer $$$k$$$, for each $$$1 \le s \le n$$$, determine the first type of mushroom that appears at least $$$k$$$ times in the basket.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$) indicating the number of test cases. For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \times 10^5$$$, $$$1 \le k \le 10^9$$$) indicating the number of locations and the required times of appearance of mushrooms.

The second line contains $$$n$$$ integers $$$t_1, t_2, \cdots, t_n$$$ ($$$1 \le t_i \le n$$$), where $$$t_i$$$ is the type of mushroom growing in location $$$i$$$.

The third line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the location pointed to by the sign in location $$$i$$$.

It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$2 \times 10^5$$$.

Output

To decrease the size of output, for each test case, output one line containing one integer indicating $$$\sum\limits_{i = 1}^n (i \times v_i)$$$, where $$$v_i$$$ is the answer for $$$s = i$$$.

Example
Input
3
5 3
2 2 1 3 3
2 5 1 2 4
5 4
2 2 1 3 3
2 5 1 2 4
3 10
1 2 3
1 3 2
Output
41
45
14
Note

For the first sample test case, $$$v_1 = 2$$$, $$$v_2 = 3$$$, $$$v_3 = 2$$$, $$$v_4 = 3$$$, $$$v_5 = 3$$$, so you should output $$$1 \times 2 + 2 \times 3 + 3 \times 2 + 4 \times 3 + 5 \times 3 = 41$$$. Consider $$$s = 3$$$, the types of mushrooms BaoBao picks in order are $$$\{1, 2, 2, 3, 3, 2, \cdots\}$$$, so mushrooms of type $$$2$$$ is the very first type which appears at least $$$3$$$ times in the basket.