Background

Since the testdata for this problem is much larger than 4 GB and exceeds Luogu’s judging limit, some test points in Subtask 9 were removed. Please judge at https://www.luogu.com.cn/problem/U697179.

Because the testdata is large, the judge may need 2–4 minutes to load the testdata. This problem cannot provide testdata downloads. You may also test your solution at the link above first, and then submit to this problem to reduce waiting time.

Problem Description

The Martian Marvin is organizing his knapsack. In front of him there are $n$ items, numbered from $1$ to $n$. Each item has two attributes: item $i$ has weirdness $w_i$ and value $c_i$. Weirdness is a non-negative integer whose binary representation has at most $k$ bits ($0 \le w_i < 2^k$). Value is a non-negative integer not exceeding $10^9$ ($0 \le c_i \le 10^9$).

The total value of a set of items is the sum of the values of all items in it, and the total weirdness is defined as the bitwise OR of the weirdness values of all items in it.

Marvin calls a set of items valuable if and only if its total value is at least $C$. For each $i$ ($1 \le i \le n$), Marvin wants to choose a valuable subset from the items with indices at most $i$, so that the subset’s total weirdness is as small as possible.

The bitwise OR of a set of integers is defined as follows: consider the binary representations of these numbers. The $i$-th bit of the result is $1$ if and only if at least one of these numbers has its $i$-th bit equal to $1$. In programming languages, this operation is denoted by the symbol $\mid$. For example, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.

Input Format

The first line contains three integers $n$, $k$, $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$), representing the number of items, the upper limit on the number of bits in weirdness, and the minimum total value for a valuable subset.

The next $n$ lines each contain two integers $w_i$ and $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$), representing the weirdness and value of item $i$.

Output Format

Output $n$ numbers. The $i$-th number should be the minimum total weirdness among valuable subsets chosen from the first $i$ items. If it is impossible to choose such a subset, output $-1$.

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

-1
10
3
1
1

Hint

Explanation

For $i = 1$, there is only one item with weirdness $8$ and value $7$. Since it is impossible to choose a subset whose total value is at least $12$, the answer is $-1$.

For $i = 2$, there are two items. The only valuable choice is to take both items, and the total weirdness is $8 \mid 2 = 10$.

For $i = 3$, any subset containing at least two items is valuable. The best plan is to choose item $2$ and item $3$, and the total weirdness is $2 \mid 3 = 3$.

For $i = 4$, you can take only the fourth item, since its value is already enough. Its weirdness is $1$, which is the smallest possible value. For $i = 5$, taking only the fourth item is also optimal.

Subtasks

Translated by DeepSeek V4 Pro.

Translated by ChatGPT 5