B - AtCoderでじゃんけんを Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

AtCoderじゃんけんの大会が開かれています。AtCoderじゃんけんとは、2 人で行う以下のようなゲームです。

  • まず、2 人がそれぞれ独立にグー、チョキ、パーのいずれかの手を出す。
  • 2 人のAtCoderのレーティングが等しくなければ、レーティングが高いほうを勝者とする。
  • 2 人のAtCoderのレーティングが等しく、2 人の出した手が異なるならば、通常のじゃんけんの勝者を勝者とする。
  • 2 人のAtCoderのレーティングが等しく、2 人の出した手も等しいならば、引き分けとする。

大会には N 人の参加者がおり、大会期間中同じ参加者は同じ手を出し続け、また大会期間中にレーティングが変化することはありません。

大会では、すべての参加者が、ほかの N-1 人の参加者とちょうど 1 回ずつAtCoderじゃんけんをします。

それぞれの人のレーティングと出す手が与えられるので、すべての参加者について、大会終了時の対戦成績が何勝何敗何引き分けかを答えてください。

ただし、通常のじゃんけんにおいては、グーはチョキに、チョキはパーに、パーはグーに、それぞれ勝つものとします。

入力

入力は以下の形式で標準入力から与えられる。

N
R_1 H_1
.
.
.
R_N H_N
  • 1 行目には、整数 N(1 ≦ N ≦ 100000) が与えられる。
  • 続く N 行には、 i 番目の参加者の情報を表す整数 R_i, H_i(1 ≦ R_i ≦ 100000, 1 ≦ H_i ≦ 3) が空白を区切りとして与えられる。これは、i 番目の参加者のレーティングが R_i で、出す手が H_i=1 のときグー、H_i=2 のときチョキ、H_i=3 のときパーであることを表す。

出力

  • 出力は N 行からなる。
  • i 行目には、i 番目の参加者の勝ち数、負け数、引き分け数を表す整数 3 つを順に空白区切りで出力せよ。

出力の最後には改行を忘れないこと。

入力例1

6
2 1
2 2
3 2
5 3
2 2
3 3

出力例1

2 3 0
0 4 1
4 1 0
5 0 0
0 4 1
3 2 0

勝敗表は図のようになります。

図 1 : 勝敗表

入力例2

2
1999 3
2000 1

出力例2

0 1 0
1 0 0

慈悲はありません。

入力例3

8
3200 2
2800 3
2800 2
2700 1
2800 2
3200 1
2700 1
3200 3

出力例3

6 1 0
2 5 0
3 3 1
0 6 1
3 3 1
6 1 0
0 6 1
6 1 0