题目描述

未知贸易公司安装了一个新的库存跟踪系统，该系统存储了全球商品和贸易点的完整数据库。每个销售点和每件商品都被分配了一个唯一的整数标识符（id）。对于每笔销售，系统会记录商品的 id、销售的商品数量以及销售点的 id。

你的任务是输出一份汇总报告，按商品和销售点列出总销售额。该报告必须是一个二维表格，第一行按升序包含商品 id，第一列按升序包含销售点 id，表格内的值表示相应销售点对应商品的总销售额。第一行第一列的值必须为 -1。没有对应销售记录的单元格的值必须为 0。

输入

输入包含记录数量 N，随后是 N 组三个整数 qi、si、vi，其中 qi 是商品 id，si 是销售点 id，vi 是销售的商品数量。

1 ≤ N ≤ 500000, 1 ≤ qi, si, vi ≤ 10⁹，汇总表的单元格数量不超过10⁸个，每个单元格的汇总值不超过2³¹−1。

输出

输出必须是如上所述的表格，按行输出。

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

-1 10 20
1 3 0
2 2 6

提示

这个问题有大量的输入和输出数据，使用 scanf() 和 printf() 而不是 cin 和 cout 来读取数据，以避免超出时间限制。

来源

2004 年东北欧，远东分区赛