Sales Report

Time limit4sMemory limit128 MB

Summary
Given N sale records of item, salespoint, and quantity, print a table of totals with items as columns and salespoints as rows.
Level

Medium4 of 10

Topics
Sorting, Hash map, Implementation, Matrix
Solved
No attempts yet

Problem

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

Output a summary report that tabulates total sales by item and by salespoint. The report is a two-dimensional table that follows these rules:

  • The first row lists the item ids in increasing order.
  • The first column lists the salespoint ids in increasing order.
  • Each inner cell holds the total quantity of the corresponding item sold from the corresponding salespoint.
  • The value in the first column of the first row (the top-left corner) is −1-1.
  • A cell with no corresponding sale holds 00.

Input

The first line contains the number of records NN. Each of the next NN lines contains three integers qi si viq_i\ s_i\ v_i, where qiq_i is the item id, sis_i is the salespoint id, and viv_i is the number of items sold.

Output

Print the table described above, one row per line, with the values in each row separated by single spaces.

Constraints

  • 1≤N≤5000001 \le N \le 500000
  • 1≤qi,si,vi≤1091 \le q_i, s_i, v_i \le 10^9
  • The summary table has at most 10810^8 cells.
  • The summary value in each cell does not exceed 231−12^{31}-1.

Examples2

  1. Example 1

    Input
    4
10 1 3
20 2 5
10 2 2
20 2 1
    Expected output
    -1 10 20
1 3 0
2 2 6

  2. Example 2

    Input
    1
1 1 5
    Expected output
    -1 1
1 5