Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Sales Report
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 2029Accepted: 595

Description

The Unknown Trading Company have installed a new inventory-tracking system, which stores a complete database of goods and trading points worldwide. Each salespoint and each item was assigned an integer unique identifier (id). For every sale, the system logs id of the item, number of items sold, and id of the salespoint.

Your task is to output a summary report, tabulating total sales by items and salespoints. The report must be a two-dimensional table, with the first row containing item ids in increasing order, first column containing salespoint ids in increasing order, and values inside the table representing total sales of corresponding item from the corresponding salespoint. The value in first column of the first row must be −1. The values in cells without corresponding sales must be 0.

Input

Input contains number of records N, followed by N triplets of integers qi si vi, where qi -- item id, si -- salespoint id, vi -- number of items sold.
1 ≤ N ≤ 500000, 1 ≤ qi, si, vi ≤ 109, the summary table will have no more than 108 cells, the summary value in each cell will not exceed than 231−1.

Output

Output must a table as described above, row-by-row.

Sample Input

4
10 1 3
20 2 5
10 2 2
20 2 1

Sample Output

-1 10 20
1 3 0
2 2 6

Hint

This problem has huge input and output data,use scanf() and printf() instead of cin and cout to read data to avoid time limit exceed.

Source

Northeastern Europe 2004, Far-Eastern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator