火星人马文正在打包一个背包。他面前有 $n$ 件物品，编号从 $1$ 到 $n$。每件物品有两个属性：第 $i$ 件物品的奇异值 $w_i$ 和花费 $c_i$。物品的奇异值是一个非负整数，其二进制表示至多包含 $k$ 位（$0 \le w_i < 2^k$），物品的花费是一个不超过 $10^9$ 的非负整数（$0 \le c_i \le 10^9$）。
一个物品集合的总花费是其中所有物品花费之和，而该集合的总奇异值定义为其中所有物品奇异值的按位或（bitwise OR）。
马文称一个物品集合是有价值的，如果其总花费至少为 $C$。对于每个 $i$ 从 $1$ 到 $n$，马文希望从前 $i$ 个物品中选出一个有价值的集合，使得其总奇异值尽可能小。
一组整数的按位或定义如下：考虑这些数的二进制表示。结果中第 $i$ 位为 $1$ 当且仅当集合中至少有一个数的第 $i$ 位为 $1$。在编程语言中，该操作用符号 "|" 表示。例如，$(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$）——对应物品的奇异值和花费。
输出格式
输出 $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$。由于无法从单个物品中选择子集使得花费总和至少为 $12$，因此答案为 $-1$。
对于 $i = 2$，有两个物品，唯一能选出有价值子集的方式是同时取两个物品。总奇异值为 $8 \mid 2 = 10$。
对于 $i = 3$，任意两个或更多物品的子集都是有价值的。最优选择是取第 2 个和第 3 个物品，它们的总奇异值为 $2 \mid 3 = 3$。
对于 $i = 4$，此时可以只选第 4 个物品，其花费足够，且奇异值为 $1$，这是可能的最小值。对于 $i = 5$，最优选择也是只取第 4 个物品。