406811: GYM102562 L Sunrise

The AGM realm consists of $$$1 \leq N \leq 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 \leq val_i \leq 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 $$$val_i$$$. When reaching a city $$$j$$$ on your route you have the opportunity to change your car with one of power $$$val_j$$$ with a cost of $$$-10^{13} \leq tax_j \leq 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 \leq i \leq 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 \leq N \leq 10^5$$$), representing the number of cities, and the number $$$D$$$ ($$$1 \leq D \leq N$$$), representing the city where the sunrise can be seen.

The following $$$N$$$ lines will contain two numbers $$$x_i$$$ ($$$1 \leq x_i \leq N$$$, $$$x_i \neq i$$$) and $$$t_i$$$ ($$$1 \leq t_i \leq 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 $$$val$$$ ($$$1 \leq val_i \leq 2*10^5$$$). Where $$$val_i$$$ represents the power of the cars from city $$$i$$$.

The line $$$N + 2$$$ will contain $$$N$$$ numbers, the array $$$tax$$$ ($$$-10^{13} \leq tax_i \leq 10^{13}$$$). Where $$$tax_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 \leq i \leq N$$$ (Note that this cost can be negative too).

5 3
2 1
3 2
1 2
1 2
2 1
5 2 6 3 1
-10 4 -4 -1 3

9 0 0 8 -2 

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.