007 - 順位の予測

問題

白虎大学が主催するプログラミングコンテストには、それぞれ1から$M$の番号が付けられた$M$組のチームが参加している。コンテストでは難易度に応じた得点がそれぞれ割り当てられたいくつかの問題が出題され、以下の基準で参加チームの順位付けが行われる。

• ある２つのチームについて、正答した問題の得点の合計が大きい方が良い成績となる
• 得点の合計が等しい場合は、その得点の合計に到達した時刻が早い方が良い成績となる
• 各チームの順位を「そのチームよりも良い成績であるチームの数」＋１とする

このコンテストでは、表彰式を盛り上げるために特殊なスコアボードを採用しており、以下の情報が開示される。

• 問題$i$の得点は$S_i$である
• 問題$i$に正答したチームの数は$K_i$である
• 問題$i$を$j$番目に正答したチームは$P_{i,j}$である

あなたは、コンテスト終了時点でのスコアボードの情報から、各チームの最終結果について最も良い順位と最も悪い順位を推測することにした。

問題の数、コンテストに参加したチームの数、各問題の得点、各問題を解いたチームとその順番の情報が与えられる。各チームについて、取りうる順位の最小値と最大値を求めるプログラムを作成せよ。ただし、各チームがいずれかの問題を正答した時刻は全て異なるものとする。

入力

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

$N$ $M$
$S_1$
$K_1$ $P_{1,1}$ $P_{1,2}$ ... $P_{1,K_1}$
$S_2$
$K_2$ $P_{2,1}$ $P_{2,2}$ ... $P_{2,K_2}$
:
$S_N$
$K_N$ $P_{N,1}$ $P_{N,2}$ ... $P_{N,K_N}$

１行目に問題の数$N$ ($1 \leq N \leq 200,000=2 \times 10^5$)とチームの数$M$ ($1 \leq M \leq 300$)が与えられる。 続く$2N$行に、各問題に関する情報がそれぞれ２行で与えられる。１行目に問題$i$の得点$S_i$ ($1 \leq S_i \leq 1,000,000,000=10^{9}$)が与えられる。２行目に、問題$i$を正答したチームの数$K_i$ ($0 \leq K_i \leq M$)と、問題$i$を$j$番目に正答したチームの番号$P_{i,j}$ ($1 \leq P_{i,j} \leq M$)が与えられる。ただし、$K_1+K_2+ ... +K_N \leq 200,000=2 \times 10^5$、かつ、$P_{i,j} \ne P_{i,l}$ ($j \ne l$)である。

出力

出力は$M$行である。チーム$i$の順位の最小値と最大値を空白区切りで$i$行目に出力する。

入出力例

入力例１

3 3
100
1 2
200
2 3 2
300
2 1 3

出力例１

2 3
2 3
1 1

入力例２

4 3
1
0
1
0
1
0
1
0

出力例２

1 1
1 1
1 1