問題文

パ研王国には N 人の住人がいて、1 から N までの番号がつけられています。パ研王国の住人には競技プログラミングの強さを表すレーティングという値が定められていて、住人 i (1 \leq i \leq N) のレーティングは R_i です。

また、この N 人の間には M 個の友達関係があり、住人 A_j と住人 B_j (1 \leq j \leq M) は友達です。この M 個の友達関係以外に友達である住人の組は存在しません。

パ太郎はパ研王国の住人を対象に競技プログラミングのコンテストを開くことにしました。パ太郎はまずレーティング制限X (X は整数) を定め、その後 N 人の住人のうち K 人を任意に選び、招待状を送ることにしました。

パ太郎または他の住人から招待状を受け取った住人 x (1 \leq x \leq N) は次のように行動します。

• 既に 1 枚以上の招待状を受け取っていた場合、何もしない。
• それまでに招待状を受け取っておらず、自身のレーティングがレーティング制限以上である場合、すなわち X \leq R_x の場合、コンテストに参加し、さらに自分の友達であるような住人全員に新たに招待状を送る。
• それ以外の場合、何もしない。

パ太郎はコンテストのレベルを高めるためできるだけレーティング制限を大きくしたいですが、参加者が少なすぎると困ってしまいます。

そこでパ太郎は N 個の質問を考えました。k (1 \leq k \leq N) 番目の質問は、次のようなものです。

• k 人以上の住人がコンテストに参加するためにはレーティング制限を最大でいくつにできるだろうか？ただし、招待状を送る K 人の住人は自由に選べるものとする。

パ太郎のために、この N 個の質問に答えるプログラムを作成してください。

制約

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq R_i \leq 10^{18} (1 \leq i \leq N)
• 1 \leq A_i<B_i \leq N (1 \leq i \leq M)
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• 入力は全て整数

小課題

1. (1 点) N \leq 2
2. (2 点) M = 0
3. (2 点) N \leq 10
4. (10 点) R_i = 1 (1 \leq i \leq N)
5. (10 点) R_i \leq 5 (1 \leq i \leq N)
6. (20 点) K = 1
7. (30 点) K \leq 5
8. (25 点) 追加の制約はない

入力例 1

4 3 1
1 2 3 4
1 2
2 3
3 4

出力例 1

4
3
2
1

例えば、 k=3 のとき、 X=2 とすれば条件を満たすことができます。具体的には、住人 2 に招待状を送ると、住人 2 が住人 3 に、住人 3 が住人 4 に招待状を送るため、最終的には住人 2,3,4 の 3 人が参加することで条件を満たします。なお、住人 2 は住人 1 にも招待状を送りますが、住人 1 のレーティングは X 未満であるため、住人 1 はコンテストには参加しません。

このサンプルは小課題 3, 5, 6, 7, 8 の制約を満たします。

入力例 2

4 0 2
4 3 2 1

出力例 2

4
3
-1
-1

入力例 3

4 2 2
1 1 1 1
1 3
2 4

出力例 3

1
1
1
1