火星人のマービンはナップサックを詰めている。彼の前には $n$ 個のアイテムがあり、$1$ から $n$ までの番号が付けられている。各アイテムは2つの特性を持つ：$i$ 番目のアイテムは奇妙さ $w_i$ とコスト $c_i$ を持つ。アイテムの奇妙さは、2進表現が最大 $k$ ビットである非負整数 ($0 \le w_i < 2^k$) であり、アイテムのコストは $10^9$ を超えない非負整数 ($0 \le c_i \le 10^9$) である。
アイテムの集合の総コストは、その集合に含まれるアイテムのコストの合計であり、集合の総奇妙さは、その集合に含まれるアイテムの奇妙さのビットごとのORとして定義される。
マービンは、総コストが少なくとも $C$ である集合を 価値ある と呼ぶ。$1$ から $n$ までの各 $i$ について、マービンは、インデックスが $i$ を超えないアイテムの中から、総奇妙さが可能な限り小さくなるような価値ある集合を選びたい。
整数の集合のビットごとのORは次のように定義される：これらの数の2進表現を考える。すると、結果の $i$ 番目のビットは、集合内の少なくとも1つの数の $i$ 番目のビットが $1$ であれば $1$ になる。プログラミング言語では、この演算は記号 "|" で表される。例えば、$(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$。
入力
最初の行には3つの整数 $n$, $k$, $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) が含まれる — アイテムの数、奇妙さの2進表現のビット数の制限、価値ある部分集合の最小コスト。
続く $n$ 行のそれぞれには2つの整数 $w_i$ と $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) が含まれる — それぞれ対応するアイテムの奇妙さとコスト。
出力
$n$ 個の整数を出力せよ。$i$ 番目の整数は、最初の $i$ 個のアイテムの中から選べる価値ある部分集合の総奇妙さの最小値と等しくなるべきである。価値ある部分集合を選ぶことが不可能な場合は、$-1$ を出力せよ。
小課題
| 小課題 | 得点 | $n$ | $k$ | 追加制約 | 必要な小課題 |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | サンプル | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | サンプル, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | サンプル, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | すべての $w_i$ は2のべき乗 | |
| 5 | 11 | $n \le 2\,000$ | サンプル, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | サンプル, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | サンプル, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | サンプル, 1–4, 6–7 | ||
| 9 | 11 | サンプル, 1–8 |
入出力例
入力例 1
5 4 12 8 7 2 6 3 6 1 12 3 5
出力例 1
-1 10 3 1 1
注記
$i = 1$ の場合、奇妙さ $8$、コスト $7$ の1つのアイテムがある。コストの合計が少なくとも $12$ になるような単一アイテムの部分集合を選ぶことはできないので、答えは $-1$ である。
$i = 2$ の場合、2つのアイテムがあり、価値ある部分集合を選ぶ唯一の方法は両方のアイテムを取ることである。総奇妙さは $8 \mid 2 = 10$ となる。
$i = 3$ の場合、2つ以上のアイテムからなる任意の部分集合は価値あるものになる。最適な選択は2番目と3番目のアイテムを選ぶことであり、その総奇妙さは $2 \mid 3 = 3$ となる。
$i = 4$ の場合、コストが十分である4番目のアイテムだけを選ぶことが可能になり、その奇妙さは $1$ であり、これが可能な最小値である。$i = 5$ の場合も、4番目のアイテムだけを選ぶのが最適である。