题目描述

火星人马文正在整理背包。面前有 $n$ 个物品，编号为 $1$ 到 $n$。每个物品有两个属性：

• 第 $i$ 个物品的奇异度为 $w_i$；
• 第 $i$ 个物品的价值为 $c_i$。

奇异度是一个非负整数，其二进制表示不超过 $k$ 位，即

$$0\le w_i<2^k。$$

价值也是非负整数，且

$$0\le c_i\le 10^9。$$

一个物品集合的总价值定义为其中物品价值之和；总奇异度定义为其中所有物品奇异度的按位或（bitwise OR）。

马文称一个物品集合是有价值的，如果它的总价值不小于 $C$。

对于每个 $i=1,2,\ldots,n$，马文想从编号不超过 $i$ 的物品中选择一个有价值的集合，并使这个集合的总奇异度尽可能小。

请对每个前缀分别求出这个最小总奇异度。

按位或定义如下：考虑若干整数的二进制表示，结果的第 $j$ 位为 $1$ 当且仅当至少有一个数的第 $j$ 位为 $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, \qquad 1\le k\le 22, \qquad 1\le C\le 10^{15}。$$

接下来 $n$ 行，每行包含两个整数 $w_i,c_i$：

$$0\le w_i<2^k, \qquad 0\le c_i\le 10^9。$$

输出格式

输出 $n$ 个数。第 $i$ 个数应等于在前 $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$，仍然可以选择第四个物品，因此答案也是 $1$。

子任务与评分

子任务	分值	附加限制	必要子任务
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$ 都是二的幂	-
5	11	$n\le 2000$	样例，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		$k\le 19$	样例，1-4，6-7
9	11	无	样例，1-8

难度评估