ADACABAA - Ada and Species


As you might know, Ada the Ladybug is a farmer. She needs to choose some species of vegetables. Each vegetable disposes with four important attributes. We say that a vegetable is worst than another vegetable, if all of its four attributes are greater.

She wants to eliminate the list of vegetables, so only vegetables, which are not worse than any other vegetables remains.

Input

The first line contains integer 1 ≤ N ≤ 2*105

Each of the next N lines contains four integers 1 ≤ X, Y, Z, W ≤ N. It is guaranteed, that all X attributes are distinct for all vegetables. The same is true for Y, Z and W (so in fact, there are four permutations of numbers from 1 to N).

Output

Print the number of vegetables, which are not worse than any other vegetable.

Example Input 1

3
1 1 1 1
2 2 2 2
3 3 3 3

Example Output 1

1

Example Input 2

10
8 9 9 2
3 7 2 4
5 5 10 10
9 3 5 9
4 6 8 6
2 8 1 7
1 2 6 1
7 4 7 5
6 1 3 8
10 10 4 3

Example Output 2

5

hide comments
mano_sriram: 2018-03-19 20:23:25

can anyone tell me how to apply constraints in python??

Vipul Srivastava: 2017-02-23 15:51:52

Last edit: 2017-02-23 19:08:41
morass: 2017-02-21 10:06:31

@Min_25: Thank you so much for pointing out it was solvable with naive approach. I've moved constrains (and hopefully "shifted" test-cases) .. sorry for inconvenience (hope it is better now ^_^ )


Added by:Morass
Date:2017-02-12
Time limit:6.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All