A chain of three trailhead gear depots, numbered 1, 2, and 3, each stock a subset of hiking items at their own price. The stockroom hands you a flat list of price listings and asks you to build a price board: one row per item showing its price at every depot, with a placeholder for depots that don't carry it.

Input format

Line 1 contains an integer N — the number of listings. Each of the next N lines contains three integers item_id, depot_id, and price, where depot_id is 1, 2, or 3. Each (item_id, depot_id) pair appears in at most one listing.

Output format

For each distinct item_id that appears in at least one listing, in ascending order of item_id, print one line: item_id price1 price2 price3, where price_k is the price of that item at depot k, or -1 if depot k has no listing for that item. Separate the four numbers with single spaces.

Constraints

• 1 <= N <= 3000
• 1 <= item_id <= 10^6
• depot_id in {1, 2, 3}
• 1 <= price <= 100000

4
10 1 100
10 2 120
20 1 50
20 3 55

10 100 120 -1
20 50 -1 55

1
30 2 75

30 -1 75 -1