판매 보고서

어느 무역 회사가 전 세계의 상품과 판매점 정보를 담은 완전한 데이터베이스를 저장하는 새 재고 관리 시스템을 도입했다. 각 판매점과 각 상품에는 고유한 정수 식별자(id)가 부여된다. 판매가 일어날 때마다 시스템은 상품 id, 판매 수량, 판매점 id를 기록한다.

상품별·판매점별 총 판매량을 정리한 요약 보고서를 출력하여라. 보고서는 다음 규칙을 따르는 2차원 표이다.

• 첫 번째 행에는 상품 id가 오름차순으로 나열된다.
• 첫 번째 열에는 판매점 id가 오름차순으로 나열된다.
• 표 내부의 각 칸에는 해당 상품이 해당 판매점에서 팔린 총 판매량이 들어간다.
• 첫 번째 행의 첫 번째 열, 즉 왼쪽 위 모서리 칸의 값은 $-1$이다.
• 대응하는 판매 기록이 없는 칸의 값은 $0$이다.

첫째 줄에 기록의 개수 $N$이 주어진다. 이어지는 $N$개의 줄에는 각각 세 정수 $q_i\ s_i\ v_i$가 주어진다. 여기서 $q_i$는 상품 id, $s_i$는 판매점 id, $v_i$는 판매 수량이다.

위에서 설명한 표를 행 단위로 한 줄씩 출력한다. 한 행 안의 값들은 공백 하나로 구분한다.

• $1 \le N \le 500000$
• $1 \le q_i, s_i, v_i \le 10^9$
• 요약 표의 칸 수는 $10^8$개를 넘지 않는다.
• 각 칸의 합계 값은 $2^{31}-1$을 넘지 않는다.