TaroTreeRequests

Cat Taro has a rooted tree with N nodes. Nodes are numbered from 0 to N-1, inclusive. Node with the index 0 is the root of the tree. Each edge has some positive integer value written on it.

Taro wants to process M queries. Each query consists of two nodes u and v. Queries should be processed in the following way:

• If u equals v, print -1.
• Otherwise, if the node v is in the subtree of the node u, print the maximum value written on the edges that belong to the simple path from u to v.
• Otherwise, remove the edge between u and its parent. Instead, add a new edge (with the same value) that makes u the child of v. (Note that the entire subtree rooted at u is now a part of the subtree rooted at v.) Do not print anything.

Return the sum of all values that were printed during the process.

You are given the ints N and M. You are also given ints startValue, maxValue, and maxHeight. These are used in the following pseudocode that generates the initial tree and the sequence of queries you should process.

initialize():
    curValue = startValue

genNextRandom():
    curValue = (curValue * 1999 + 17) modulo 1,000,003
    return curValue

generateTree():
    for i=1 to N-1:
        value[i] = genNextRandom() modulo maxValue;
        parent[i] = max( 0, i - 1 - (genNextRandom() modulo maxHeight) );
        in our tree, the parent of vertex i is parent[i]
        the edge between i and parent[i] has the label value[i]

generateQueries():
    for i=0 to M-1:
        queryU[i] = genNextRandom() modulo N
        queryV[i] = genNextRandom() modulo N
	if queryU[i] > queryV[i]:
		swap queryU[i] and queryV[i]
        process the query with u=queryU[i] and v=queryV[i]

To generate the input, call initialize(), then generateTree(), and finally generateQueries().