You are given a rooted tree where each node $u$ has an escape cost $t_u$. Moving from a node to its parent costs $f_u$, and moving from a parent to its child $v$ costs $g_v$.

For each query $(u, k)$, you need to choose a node $v$ such that every node on the path from $u$ to $v$ has a distance from the root of at least $k$ edges, and the sum of the cost to reach $v$ from $u$ plus the escape cost $t_v$ is minimized. You have many queries, and you only need to output the minimum total cost for each.

Input

The first line contains eight non-negative integers $n, m, \mathrm{SA}, \mathrm{SB}, \mathrm{SC}, t_1, t_2$, where $n$ is the number of nodes in the tree and $m$ is the number of queries.

The next line contains $n$ non-negative integers $t_i$.

The next $n - 1$ lines each contain three integers $p_i, f_i, g_i$, where $i$ is numbered starting from $2$, $p_i$ is the parent of node $i$, and it is guaranteed that $p_i < i$.

To reduce the volume of input and output, the queries and output are handled by the following code. Note that the length[] array means: the $i$-th element is the number of edges from node $i$ to the root. You need to implement the query() function. You can call the solve() function once after processing the length[] array in your main program.

unsigned int SA, SB, SC;
int n, m, t1, t2;

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;
}

long long query(int u, int k);

void solve() {
    long long lastans = 0, output = 0;
    while (m--) {
        int u = (rng61() ^ (t1 * lastans)) % n + 1;
        int k = (rng61() ^ (t1 * lastans)) % (length[u] + 1) * t2;
        lastans = query(u, k);
        output ^= lastans + m;
    }
    printf("%lld\n", output);
}

You can find this code in lyric/template.cpp in the provided files.

Output

The output is given by the output variable in the code above.

Examples

Input 1

10 10 629647033 688064407 427303738 1 1
8 7 16 11 7 20 18 9 16 6
1 3 13
2 8 11
3 12 3
4 20 3
5 10 14
3 19 8
7 9 8
8 12 18
6 10 10

Output 1

23

Note

The actual queries and answers for this sample are as follows:

4 2
10
1 0
8
6 2
16
10 6
6
6 4
16
6 0
16
6 2
16
6 3
16
10 0
6
1 0
8

Constraints

For $100\%$ of the data, $1\le n\le 3\times 10^5, 1\le m \le 6\times 10^6, 0\le t_1, t_2 \le 1$, and all other input integers are between $0$ and $10^9$.

For $0\%$ of the data, it is guaranteed that $m \le 5\times 10^7$.

Story

That fairy-tale-like time passed in a flash. Lan has grown up, and the world has changed.

I can't just forge castles in the air, can I? I don't want to do this, but... since things have come to this, I must let her see the "new world".

Bewilderment, astonishment. This was how she looked when she saw it for the first time. Even though we had rehearsed it thousands of times.

Growing up? No, I refuse to admit it! Why does the world have to be like this? Why must the world shatter every dream? And why do I have to let her experience that "helplessness and fear"?

Spare me, I can't pretend to be gratified, or righteously say that this is some kind of "growth".

I fear the flames of war and hatred will blind her eyes;

I fear the mud of ignorance will infect her purity;

I fear the icicles of the world will extinguish her fiery passion.

She sat blankly in her old studio for a whole day, staring blankly at the starry sky she once painted.

The next day, one of her hairs turned white.

"Does that art... still have any meaning!"

Yes, painting is barbaric, writing poetry is barbaric.

I used to answer her hundred thousand whys. But today, I don't know the answer.

Or rather, I don't know how to answer her. I could only lower my head and grit my teeth.

"...I'm sorry."

That palace collapsed with a crash. Like a gushing spring.

The stars in the sky were also bleeding.

I want to take Lan and leave this place together.

And the way to leave can only be found in ancient runes.

The rune system of ancient magic is extremely complex, and its types of letters are countless. Time is tight, so I don't plan to tell you these details. I will only tell you about a rooted tree. You can consider the path from the root to a node as representing a string. The rune I carry with me can also be represented by a node $u$. Every node on the tree can take us away. If the rune I currently hold is node $u$, it takes $t_u$ time to activate. However, the rune I hold can also be modified, which also takes time. If I erase the last character of the rune, that is, moving from node $u$ to its parent, it takes $f_u$ time. I can also change it to one of its children $v$, which takes $g_v$ time.

In addition, there is a restriction: at any time, I must ensure that the string length is not less than $k$. The string length is the number of edges passed from the root node to the node I am currently at.

What I want to ask you to help me with is, how to complete the escape in the shortest time? I may give you multiple questions. Time is tight, please tell me the answers as soon as possible.

Lyrics

In a dull life, splashing water drops,

Amidst fireworks and neon lights, being a dreamer,

A silhouette coming against the light, a sudden heartbeat,

— "That is you."

In ordinary encounters, time sprouts,

Shouting in an empty classroom, voice never hoarse,

Of all the colors in my eyes, the brightest one,

— "Is only you."