Sales Report

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$.
• A cell with no corresponding sale holds $0$.

The first line contains the number of records $N$. Each of the next $N$ lines contains three integers $q_i\ s_i\ v_i$, where $q_i$ is the item id, $s_i$ is the salespoint id, and $v_i$ is the number of items sold.

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

• $1 \le N \le 500000$
• $1 \le q_i, s_i, v_i \le 10^9$
• The summary table has at most $10^8$ cells.
• The summary value in each cell does not exceed $2^{31}-1$.