背景

由于本题测试数据远大于 4GB，超过洛谷评测上限，子任务 9 中部分测试点被删除，请在 https://www.luogu.com.cn/problem/U697179 中评测。

由于测试数据较大，评测时可能需要 2-4 分钟时间加载测试数据。本题无法开放测试数据下载。您也可以先在上述链接中进行自测，然后再提交本题，以降低等待时间。

题目描述

火星人马文正在整理背包。他面前摆着 $n$ 件物品，编号为 $1$ 到 $n$。每件物品有两个属性：第 $i$ 件物品具有奇怪度 $w_i$ 和价值 $c_i$。奇怪度是一个非负整数，其二进制表示不超过 $k$ 位（$0 \le w_i < 2^k$）；价值是一个非负整数，不超过 $10^9$（$0 \le c_i \le 10^9$）。

一组物品的总价值等于其中所有物品的价值之和，而总奇怪度定义为其中所有物品奇怪度的按位“或”运算结果。

马文称一组物品是有价值的，当且仅当其总价值不小于 $C$。对于每个 $i$（$1 \le i \le n$），马文希望从编号不超过 $i$ 的物品中选出一个有价值的子集，使得该子集的总奇怪度尽可能小。

一组整数的按位“或”运算定义如下：考虑这些数的二进制表示，则结果数的第 $i$ 位为 $1$，当且仅当这些数中至少有一个数的第 $i$ 位为 $1$。在编程语言中，该运算用符号 $\mid$ 表示。例如，$(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$。

输入格式

第一行包含三个整数 $n$, $k$, $C$（$1 \le n \le 2\,000\,000$，$1 \le k \le 22$，$1 \le C \le 10^{15}$），分别表示物品数量、奇怪度二进制位数的上限以及有价值子集的最低总价值。

接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $c_i$（$0 \le w_i < 2^k$，$0 \le c_i \le 10^9$），分别表示第 $i$ 件物品的奇怪度和价值。

输出格式

输出 $n$ 个数，第 $i$ 个数应等于从前 $i$ 个物品中选出的有价值子集的最小总奇怪度。如果无法选出这样的子集，则输出 $-1$。

5 4 12
8 7
2 6
3 6
1 12
3 5

-1
10
3
1
1

提示

说明

对于 $i = 1$，只有一件物品，奇怪度为 $8$，价值为 $7$。由于无法选出总价值不小于 $12$ 的子集，答案为 $-1$。

对于 $i = 2$，有两件物品，唯一有价值的选择是取全部两件物品，总奇怪度为 $8 \mid 2 = 10$。

对于 $i = 3$，任意包含至少两件物品的子集都是有价值的。最优方案是选取第二件和第三件，总奇怪度为 $2 \mid 3 = 3$。

对于 $i = 4$，可以只取第四件物品，其价值已足够，奇怪度为 $1$，达到了最小可能值。对于 $i = 5$，同样只取第四件物品是最优的。

子任务

翻译由 DeepSeek V4 Pro 完成