The AGM realm consists of $1 <= N <= 10^5$ cities, indexed from $1$ to $N$. This year there is a special sunrise, so everyone wants to see it. The sunrise can be seen just from the city D. The cities from AGM realm are connected with $N$ directed roads and each road is of type $1$ or type $2$. Each city $i$ has cars of power $1 <= v a l_i <= 2 * 10^5$. Everyone wants to travel from their city to city $D$ using the cars. If you are using a car with power $x$, the cost to traverse a road of type $1$ is $x$, and the cost to traverse a road of type $2$ is $x^2$. If you start your journey from city $i$, you will start with a car of power $v a l_i$. When reaching a city $j$ on your route you have the opportunity to change your car with one of power $v a l_j$ with a cost of $-10^(13) <= t a x_j <= 10^(13)$. The journey stops as soon as you reach city $D$, but you can still change your car in this city. You can't change the car in the city where you start the journey from.
For each city $1 <= i <= N$, you need to compute the minimum cost to reach city $D$ starting from city $i$. It is guaranteed that city $D$ is reachable from all the cities.
The first line of the input will contain the number $N$ ($1 <= N <= 10^5$), representing the number of cities, and the number $D$ ($1 <= D <= N$), representing the city where the sunrise can be seen.
The following $N$ lines will contain two numbers $x_i$ ($1 <= x_i <= N$, $x_i eq.not i$) and $t_i$ ($1 <= t_i <= 2$) each, representing that there exists a directed road from city $i$ to city $x_i$ of type $t_i$.
The line $N + 1$ will contain $N$ numbers, the array $v a l$ ($1 <= v a l_i <= 2 * 10^5$). Where $v a l_i$ represents the power of the cars from city $i$.
The line $N + 2$ will contain $N$ numbers, the array $t a x$ ($-10^(13) <= t a x_i <= 10^(13)$). Where $t a x_i$ represents the cost to change the car in city $i$.
You should output one line consisting of $N$ numbers, representing the minimum cost to reach city D starting from city $i$, for each $1 <= i <= N$ (Note that this cost can be negative too).
The journey with minimum cost from city 4:
You start with a car with power 3 and travel to city 1 with this power, it will cost you $3^2 = 9$.
In city 1 you change the car with one with power 5 and it will cost you -10.
Then you travel to city 2 with this power, it will cost you 5.
In city 2 you change the car with one with power 2 and it will cost you 4.
Then you travel to city 3 with this power, it will cost you $2^2 = 4$.
And in city 3 you change the car and it will cost you -4.
The total cost of the journey is 8.
## Input
The first line of the input will contain the number $N$ ($1 <= N <= 10^5$), representing the number of cities, and the number $D$ ($1 <= D <= N$), representing the city where the sunrise can be seen. The following $N$ lines will contain two numbers $x_i$ ($1 <= x_i <= N$, $x_i eq.not i$) and $t_i$ ($1 <= t_i <= 2$) each, representing that there exists a directed road from city $i$ to city $x_i$ of type $t_i$. The line $N + 1$ will contain $N$ numbers, the array $v a l$ ($1 <= v a l_i <= 2 * 10^5$). Where $v a l_i$ represents the power of the cars from city $i$. The line $N + 2$ will contain $N$ numbers, the array $t a x$ ($-10^(13) <= t a x_i <= 10^(13)$). Where $t a x_i$ represents the cost to change the car in city $i$.
## Output
You should output one line consisting of $N$ numbers, representing the minimum cost to reach city D starting from city $i$, for each $1 <= i <= N$ (Note that this cost can be negative too).
[samples]
## Note
The journey with minimum cost from city 4: You start with a car with power 3 and travel to city 1 with this power, it will cost you $3^2 = 9$. In city 1 you change the car with one with power 5 and it will cost you -10. Then you travel to city 2 with this power, it will cost you 5. In city 2 you change the car with one with power 2 and it will cost you 4. Then you travel to city 3 with this power, it will cost you $2^2 = 4$. And in city 3 you change the car and it will cost you -4. The total cost of the journey is 8.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of dragon lairs.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the gold obtained from defeating the $ i $-th dragon.
Let $ S \subseteq \{1, 2, \dots, n\} $ be the set of indices of dragons the hero defeats, in order.
Let $ k = |S| $ be the number of battles fought.
Let the battles occur at positions $ i_1 < i_2 < \dots < i_k $, corresponding to the sequence of defeated dragons.
**Constraints**
1. The hero must traverse the road in order: if $ i_j \in S $, then all $ i < i_j $ are considered before $ i_j $.
2. The cost of the $ m $-th battle (in chronological order of battles) is $ m $ gold.
3. At every point in time, the hero’s gold balance must be non-negative:
$$
\sum_{j=1}^m a_{i_j} - \sum_{j=1}^m j \geq 0 \quad \text{for all } m = 1, \dots, k.
$$
**Objective**
Maximize the final profit:
$$
\max_{S \subseteq \{1,\dots,n\}} \left( \sum_{i \in S} a_i - \frac{|S|(|S|+1)}{2} \right)
$$
subject to the non-negativity constraint on the partial sums at every battle.