Description

Xiao Feng is a big fan of the online multiplayer racing game PopKart. Among various types of play, Xiao Feng prefers the Speed Game, in which players compete to be the fastest racer. In order to win the races, apart from solid driving skills, the player must also own a top-class kart. Results of races among experienced players are mostly decided by the karts which they ride.

Now a new generation of karts has hit the market. Xiao Feng wants to purchase one of them. Two factors prevents him from going straightly for the best ones. First, the available (virtual) funds are limited. Second and more importantly, it is a non-trivial task to decide which karts are the best.

To find out the best karts that he can afford, Xiao Feng employs a simple scheme to classify the karts by their performance.

The performance of a kart is characterized by two parameters—the straight-line speed v and the drift speed w. A kart is said to be superior to another if and only if it is superior in either speed and not inferior in the other. All karts to which no other karts are superior are classified as karts of class 1. For each m ≥ 2, all karts to which only karts of classes 1 through m − 1 are superior are classified as karts of class m.

Given the straight-line and drift speeds of n karts, classify them as specified above.

Input

The input contains a single test case. The first line contains n (1 ≤ n ≤ 10⁵). The remaining n lines each contain two integers v and w (0 ≤ v, w < 10⁶), the straight-line and drift speeds of a kart.

Output

For each class in increasing order of m, print a list of karts of that class using the format

“k: (v₁,w₁) (v₂,w₂) ⋯ (v_k,w_k)”

where k is the number of karts of that class, and (v₁, w₁), (v₂, w₂), …, (v_k, w_k) are their straight-line and drift speeds. The k pairs of speeds shall be sorted so that v_i < v_j ∨ (v_i = v_j ∧ w_i ≤ w_j) for any 1 ≤ i < j ≤ k (“∨” and “∧” represent logical OR and AND, respectively).

4
1 2
2 1
2 3
3 2

2: (2,3) (3,2)
2: (1,2) (2,1)

Source

PKU Campus 2008 (POJ Founder Monthly Contest – 2008.05.10), xfxyjwf