Marvin the Martian is packing a knapsack. In front of him are $n$ items, numbered from $1$ to $n$. Each item has two characteristics: the $i$-th item has a strangeness $w_i$ and a cost $c_i$. The strangeness of an item is a non-negative integer whose binary representation contains at most $k$ bits ($0 \le w_i < 2^k$), and the cost of an item is a non-negative integer not exceeding $10^9$ ($0 \le c_i \le 10^9$).
The total cost of a set of items is the sum of the costs of the items in it, and the total strangeness of this set is defined as the bitwise OR of the strangenesses of the items in it.
Marvin calls a set of items valuable if its total cost is at least $C$. For each $i$ from $1$ to $n$, Marvin wants to choose a valuable set of items from the items with indices not exceeding $i$ such that its total strangeness is as small as possible.
The bitwise OR of a set of integers is defined as follows: consider the binary representations of these numbers. Then the $i$-th bit of the result is $1$ if the $i$-th bit of at least one of the numbers in the set is $1$. In programming languages, this operation is denoted by the symbol "|". For example, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.
Input
The first line contains three integers $n$, $k$, and $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) — the number of items, the limit on the number of bits in the binary representation of strangeness, and the minimum cost of a valuable subset.
Each of the following $n$ lines contains two integers $w_i$ and $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) — the strangeness and the cost of the corresponding item, respectively.
Output
Print $n$ integers, where the $i$-th integer should be equal to the minimum total strangeness of a valuable subset of the first $i$ items. If it is impossible to choose a valuable subset, print $-1$.
Subtasks
| Subtask | Points | $n$ | $k$ | Additional Constraints | Required Subtasks |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | Samples | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | Samples, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | Samples, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | All $w_i$ are powers of two | |
| 5 | 11 | $n \le 2\,000$ | Samples, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | Samples, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | Samples, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | Samples, 1–4, 6–7 | ||
| 9 | 11 | Samples, 1–8 |
Examples
Input 1
5 4 12 8 7 2 6 3 6 1 12 3 5
Output 1
-1 10 3 1 1
Note
For $i = 1$, there is one item with strangeness $8$ and cost $7$. Since we cannot choose a subset of a single item such that the sum of costs is at least $12$, the answer is $-1$.
For $i = 2$, there are two items, and the only way to choose a valuable subset is to take both items. The total strangeness will be $8 \mid 2 = 10$.
For $i = 3$, any subset of two or more items will be valuable. The optimal choice is to select the second and third items, and their total strangeness will be $2 \mid 3 = 3$.
For $i = 4$, it becomes possible to choose only the fourth item, whose cost is sufficient, and its strangeness is $1$, which is the minimum possible. For $i = 5$, it is also optimal to choose only the fourth item.