Peppino Spaghetti needs to defend his pizza tower against a horde of enemies!
Each of the $$$N$$$ enemies has a distinct location $$$(x_i, y_i)$$$ as well as a strength value $$$s_i$$$. Furthermore, we define a function $$$$$$f(x, y) = \begin{cases} s_i & x = x_i \text{ and } y = y_i \text{ for some } i \in \{1, 2, \dots, N\} \\ 0 & \text{otherwise} \end{cases}.$$$$$$
In order to gauge where to set up his defenses so that his tower will stay safe, Peppino needs to calculate a function $$$$$$F(x_i, y_i) = \sum_{x \leq x_i} \sum_{y \leq y_i} f(x, y)$$$$$$ at each point $$$(x_i, y_i)$$$ for $$$i \in \{1, 2, \dots, N\}$$$. However, Peppino doesn't have much time, so he has asked you to write a computer program to speed up the calculations. Please help him out!
The first line of input will contain a single integer $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$ denoting the number of enemies in the horde.
The next $$$N$$$ lines will each contain three space-separated integers $$$x_i$$$, $$$y_i$$$, and $$$s_i\ (1 \leq x_i, y_i, s_i \leq 2 \cdot 10^9)$$$ denoting the position and strength value of the $$$i^\text{th}$$$ enemy. Furthermore, it is guaranteed that $$$(x_i, y_i) \neq (x_j, y_j)$$$ for any $$$i \neq j \in \{1, 2, \dots, N\}$$$, that is, the positions of enemies are distinct.
The output should consist of exactly $$$N$$$ lines, each containing a single integer. The $$$i^\text{th}$$$ line should contain the integer $$$F(x_i, y_i)$$$. Note that $$$F(x_i, y_i)$$$ could be quite large, and may not fit into a standard signed 32-bit integer.
41 1 52 1 101 2 103 3 15
5 15 15 40
51 1 11 2 21 3 31 4 41 5 5
1 3 6 10 15
In the first sample case, $$$F(1, 1) = f(1, 1) = 5$$$, and $$$F(2, 1) = F(1, 2) = 15$$$ since $$$F(2, 1) = f(2, 1) + f(1, 1) = 10 + 5$$$ and $$$F(1, 2) = f(1, 2) + f(1, 1) = 10 + 5$$$. Also, $$$F(3, 3) = f(3, 3) + f(2, 1) + f(1, 2) + f(1, 1) = 15 + 10 + 10 + 5 = 40$$$.
In the second sample case, it can be observed that $$$F(1, y) = f(1, y) + F(1, y-1)$$$ for $$$1 \lt y \leq 5$$$.
