In 2045, human technology has advanced rapidly, and a method for space-time travel has been discovered. Little R has obtained a space-time traveler and wants to use it to investigate the development of humanity across different space-times.

According to the parallel space-time theory, there are many independent space-times in the universe, and each space-time branches into several different space-times at the next time point. The universe is a three-dimensional space, and humans use a Cartesian coordinate system to describe a position in space with coordinates $x, y, z$.

Assume that in the initial space-time (numbered $0$), humans exist on Earth (Earth's coordinates are $(0,0,0)$), and all other space-times are developed from an existing space-time. A space-time develops into another after an event occurs (the original space-time remains unchanged). Events that affect Little R fall into two categories:

1. Humans colonize a new planet, and the planet's status becomes "colonized".
2. Humans abandon a previously colonized planet, and the planet's status becomes "uncolonized".

Each time Little R travels through space-time, he first selects a space-time. In this space-time, humans have already colonized some planets. Little R can investigate the development of humanity by reaching any colonized planet in that space-time.

Little R's space-time traveler has some issues: the button to adjust the $x$ coordinate is broken, so the $x$ coordinate of the arrival point is fixed (the $x$ coordinate value may differ for each trip). Meanwhile, he can still freely adjust the $y$ and $z$ coordinates of the arrival point.

This problem significantly increases Little R's costs: while space-time travel is free, traveling through space costs money; additionally, conducting investigations on different planets may incur different costs.

Suppose Little R sets the destination of his space-time travel to $A$, and the planet he intends to investigate is $B$: if the Euclidean distance between $A$ and $B$ is $d$, then his space travel cost is $d^2$; furthermore, if the cost of conducting an investigation on planet $B$ is $c$, then the total cost of Little R's investigation is $d^2 + c$.

Given the space-time Little R arrives at for each trip and the fixed $x$ coordinate value on the traveler, calculate the minimum total cost for Little R to complete the investigation for each trip.

Input

The first line contains three non-negative integers $n, m, c_0$, where $n$ is the number of parallel space-times (numbered $0$ to $n-1$, with $0$ being the initial space-time), $m$ is the number of space-time trips Little R makes, and $c_0$ is the cost of investigating on Earth. It is guaranteed that $0 < n, m \leq 5 \times 10^5$ and $0 \leq c_0 \leq 10^{12}$.

The next $n-1$ lines describe the parallel space-times $1$ to $n-1$ in order. Each line $i$ describes one of two cases:

1. $0 \ \mathrm{fr} \ \mathrm{id} \ x \ y \ z \ c$: Space-time $i$ is developed from space-time $\mathrm{fr}$. Humans colonize a planet with ID $\mathrm{id}$, coordinates $(x, y, z)$, and investigation cost $c$. It is guaranteed that planet IDs are unique, $0 < \mathrm{id} < n$, $|x|, |y|, |z| \leq 10^6$, and $0 \leq c \leq 10^{12}$.
2. $1 \ \mathrm{fr} \ \mathrm{id}$: Space-time $i$ is developed from space-time $\mathrm{fr}$. Humans abandon planet $\mathrm{id}$. It is guaranteed that the planet is in a colonized state in space-time $\mathrm{fr}$, and $\mathrm{id} > 0$ (Earth is never abandoned).

In both cases, all parameters are positive integers, separated by spaces. It is guaranteed that $0 \leq \mathrm{fr} < i$. No other cases will occur.

The next $m$ lines each represent one of Little R's space-time trips. Each line contains two positive integers $s$ and $x_0$, representing that Little R travels to space-time $s$ with the traveler's $x$ coordinate fixed at $x_0$.

Output

Output $m$ lines, each representing the minimum total cost to complete the investigation for each trip.

Examples

Input 1

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

Output 1

18
6
11
66

Input 2

See the provided file.

Subtasks