406004: GYM102215 J The Power of the Dark Side - 2

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. The Power of the Dark Side - 2time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

On the Jedi Tournament $$$n$$$ Jedi are battling each other. Every Jedi has three parameters: strength, agility and intelligence. When two Jedi have a fight, the winner will be the Jedi which has at least two parameters higher compared to the same parameters of his opponent. For example, Jedi with parameters (5, 9, 10) defeats Jedi with parameters (2, 12, 4) because of first and third parameters.

Sith have a plan to turn one of the Jedi to the dark side of the Force. It will give him a powerful skill that allows to set all his parameters arbitrarily before every fight, with the restrictions that the parameters should remain non-negative integers and their sum should not change.

For every Jedi, determine how many other Jedi he can defeat being turned to the dark side.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the number of the Jedi.

Each of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ ($$$0 \le a_i, b_i, c_i \le 10^9$$$) — the parameters of the Jedi.

Output

Output $$$n$$$ integers: how many other Jedi the $$$i$$$-th Jedi can defeat being turned to the dark side.

ExampleInput
4
1 3 4
2 5 9
6 10 3
5 2 3
Output
1 3 3 2 

加入题单

上一题 下一题 算法标签: