Chen is a cute cat. She loves Starch very much. Today She would like to steal some.

Chen lives in a village. The houses in the village connect as a tree. The house marked  stores  kg starch. She will only steal the houses on the shortest path from the house marked  to the house marked . To avoid being caught, for every house in this graph, if Chen chooses to steal the house marked , every house directly connected with the house marked  won't be stolen.

Now, you should answer Chen how much starch she can steal at most?

Because the amount of queries is too large, you need to use the random number generator as follows. We use  to represent the answer to the last query. You need to update  after each query.

The random number generator will cost no more than 500ms.

struct Rand{
    unsigned int n,seed;
    Rand(unsigned int n,unsigned int seed)
    :n(n),seed(seed){}
    int get(long long lastans){
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        return (seed^lastans)%n+1;
    }
};

For the  query, you need to use the generator to get  integers . And you should calculate the answer . After that, use  to update . The following code is for reference.

long long lastans=0,ans=0;
constexpr int P=998244353;
Rand rand(n,seed);
for(int i=0;i<m;i++){
    int u=rand.get(lastans);
    int v=rand.get(lastans);
    int x=rand.get(lastans);
    lastans=query(u,v);//calculate the answer
    ans=(ans+lastans%P*x)%P;
}
//print 'ans'

输入描述:

The first line contains  integers .  is the number of houses. is the number of queries.

The second line contains  integers. The  integer is .

The third line contains  integers. The  integer  represents to the house marked  is connected to house marked . It is guaranteed that the houses connect as a tree.

Then, you need to use  and  to initialize the generator.

For the  query, you need to use the generator to get  integers . And you should calculate the answer . After that, use  to update . You can refer to the second code in the description.

输出描述:

Only one integer, .

5 3 1
2 1 1 2 2
1 1 2 2

14

Decoded input is:
5 3 1
2 1 1 2 2
1 1 2 2
5 5 2
4 1 2
2 5 1

10 10000000 1
4 2 6 3 8 4 2 6 4 1
1 2 2 1 5 5 5 6 6

516974317