A. A Factory Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sebastián and Sebastian are playing a game.

The game consists of counting the number of materials and submaterials delivered to their factory while unloading a truck. The winner of the game will be the one who remembers most accurately how many materials and submaterials were received. The deal is that the loser has to take the winner out to dinner. Since neither of them wants to lose, both decide to cheat and secretly take notes to ensure their victory.

Each delivery is represented by three integers: the product, the material, and a corresponding submaterial. The full list contains N lines, each one representing a single delivery. But something went wrong. Due to a technical failure, the factory's official system lost all delivery records. Now, the only source of truth is the list that both Sebastián's created even if it contains repeated entries. They need your help to analyze their combined notes and generate a clean summary.

Input

First line contains one integer $$$n$$$ ($$$1$$$ $$$\le$$$ $$$n$$$ $$$\le$$$ $$$10^6$$$), indicating the size of the combined list of Sebastián and Sebastian. Then n lines contains three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1$$$ $$$\le$$$ $$$a$$$, $$$b$$$, $$$c$$$ $$$\le$$$ $$$10^{18}$$$), the product id, material and sub material received.

Output

For each product, print one line with three integers $$$A$$$, $$$B$$$, and $$$C$$$, where $$$A$$$ is the product id, $$$B$$$ is the number of distinct materials associated with that product, and $$$C$$$ is the number of distinct submaterials associated with that product. The products must be printed in increasing order.

Examples
Input
10
1 1 1
2 2 1
3 4 1
2 2 2
2 2 1
1 3 12
1 1 2
1 4 1
1 4 2
1 4 3
Output
1 3 6
2 1 2
3 1 1
Input
3
186 312 851372492
291 103 93522568
757 156 500988176
Output
186 1 1
291 1 1
757 1 1