N - Equipment Collector
問題文
Nachia 君は RPG のゲームでアイテム集めをしています。
このゲームには種類 $1$ から種類 $M$ までの $M$ 種類のアイテムがあります。
また、同種のアイテムであっても色が異なる場合があり、各アイテムの色は色 $1$ から色 $K$ までの $K$ 色のいずれかです。
このゲームでは最大 $N$ 回アイテムを獲得できます。
ゲーム開始時、 $0$ 以上 $N-1$ 以下の整数 $f$ が選ばれます。
$i$ 回目に獲得できるアイテムの色は $C _ {(i-1+f) \bmod N + 1}$ 、種類は $A _ {(i-1+f) \bmod N + 1}$ です。
色の違いを含めた $KM$ 通りのアイテムは、それぞれ少なくとも $1$ 回は獲得できるようになっています。
Nachia 君は、以下の手順を行います。
- アイテムを $M$ 回獲得し、所持する。
- 以降、コスト $1$ を支払って次の手順で表される 操作 を $0$ 回以上の好きな回数行う。
- 所持しているアイテムを $1$ 個以上選んで破棄する。
- 破棄したアイテムの個数以下の回数、アイテムを獲得し、所持する。ただし、獲得回数の累計が $N$ 個を超えてはいけない。
Nachia 君の目標は、同じ色のアイテム $M$ 種類を同時に所持することです。
$f=0,1,\ldots ,N-1$ のそれぞれについて、目標を達成するまでの 操作 の回数（アイテムの獲得個数ではありません）としてありうる最小値を求めてください。
なお、 Nachia 君は $f$ の値を知ったうえで操作を最小化するように行動すると考えて構いません。
$1$ 回の実行で $T$ 個のテストケースを処理してください。
制約
- $1 \leq T \leq 10{,}000$
- $1 \leq N \leq 200{,}000$
- $2 \leq M \leq 5$
- $1 \leq K$
- $1 \leq MK \leq N$
- $1 \leq C _ i \leq K$
- $1 \leq A _ i \leq M$
- すべての整数の組 $(c,a)$ ($1 \leq c \leq K$ , $1 \leq a \leq M$) について、ある $i$ ($1 \leq i \leq N$) が存在して $(c,a)=(C _ i, A _ i)$ を満たす
- $1$ 回の入力における $N$ の総和は $200{,}000$ を超えない
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case} _ 1$
$\mathrm{case} _ 2$
$\vdots$
$\mathrm{case} _ T$
各テストケースは以下の形式で与えられる。
$N$ $M$ $K$
$A _ 1$ $C _ 1$
$A _ 2$ $C _ 2$
$\vdots$
$A _ N$ $C _ N$
出力
各テストケースについて、$f=0,1,\ldots ,N-1$ についての答えを空白区切りで出力せよ。
テストケースに対する出力の末尾は改行せよ。
4
6 5 1
1 1
2 1
3 1
4 1
5 1
5 1
12 3 2
2 1
3 1
1 2
1 1
2 2
1 1
3 1
3 2
2 1
2 2
2 1
2 1
25 4 3
4 2
2 1
1 1
3 2
3 3
2 3
1 3
2 2
3 2
1 1
4 1
2 1
4 1
4 1
1 3
3 1
3 1
2 1
2 2
2 3
2 3
4 3
3 3
2 2
1 2
11 4 1
1 1
2 1
3 1
4 1
2 1
1 1
4 1
2 1
1 1
1 1
2 1
0 1 1 1 1 0
1 3 2 2 2 1 3 3 3 2 2 2
5 4 4 4 4 3 3 3 3 2 3 3 3 2 2 4 4 4 4 3 3 3 3 2 3
0 1 0 3 2 2 2 1 1 1 1
$1$ つめのテストケースのみ説明します。
- $f = 0$ の場合、獲得できるアイテムの種類は順に $1,2,3,4,5,5$ です。最初に $5$ 種類のアイテムを獲得できるので、操作 $0$ 回で目的を達成できます。
- $f = 5$ の場合、獲得できるアイテムの種類は順に $5,1,2,3,4,5$ です。最初に $5$ 種類のアイテムを獲得できるので、操作 $0$ 回で目的を達成できます。
- それ以外の場合は、操作を $1$ 回行って種類 $5$ のアイテムを $1$ 個破棄しなければなりませんが、その後 $1$ つアイテムを獲得したときに目的が達成されます。