Marvin el Marciano está empacando una mochila. Frente a él hay $n$ objetos, numerados del $1$ al $n$. Cada objeto tiene dos características: el $i$-ésimo objeto tiene una rareza $w_i$ y un costo $c_i$. La rareza de un objeto es un entero no negativo cuya representación binaria contiene a lo sumo $k$ bits ($0 \le w_i < 2^k$), y el costo de un objeto es un entero no negativo que no supera $10^9$ ($0 \le c_i \le 10^9$).
El costo total de un conjunto de objetos es la suma de los costos de los objetos que lo componen, y la rareza total de este conjunto se define como el OR bit a bit de las rarezas de los objetos que lo componen.
Marvin llama valioso a un conjunto de objetos si su costo total es al menos $C$. Para cada $i$ desde $1$ hasta $n$, Marvin quiere elegir un conjunto valioso de objetos entre aquellos con índices que no superan $i$, de modo que su rareza total sea lo más pequeña posible.
El OR bit a bit de un conjunto de enteros se define de la siguiente manera: considere las representaciones binarias de estos números. Entonces, el $i$-ésimo bit del resultado es $1$ si el $i$-ésimo bit de al menos uno de los números del conjunto es $1$. En los lenguajes de programación, esta operación se denota con el símbolo "|". Por ejemplo, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.
Entrada
La primera línea contiene tres enteros $n$, $k$ y $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) — la cantidad de objetos, el límite en la cantidad de bits de la representación binaria de la rareza y el costo mínimo de un subconjunto valioso.
Cada una de las siguientes $n$ líneas contiene dos enteros $w_i$ y $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) — la rareza y el costo del objeto correspondiente, respectivamente.
Salida
Imprima $n$ enteros, donde el $i$-ésimo entero debe ser igual a la rareza total mínima de un subconjunto valioso de los primeros $i$ objetos. Si es imposible elegir un subconjunto valioso, imprima $-1$.
Subtareas
| Subtarea | Puntos | $n$ | $k$ | Restricciones adicionales | Subtareas requeridas |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | Ejemplos | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | Ejemplos, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | Ejemplos, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | Todos los $w_i$ son potencias de dos | |
| 5 | 11 | $n \le 2\,000$ | Ejemplos, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | Ejemplos, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | Ejemplos, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | Ejemplos, 1–4, 6–7 | ||
| 9 | 11 | Ejemplos, 1–8 |
Ejemplos
Entrada 1
5 4 12 8 7 2 6 3 6 1 12 3 5
Salida 1
-1 10 3 1 1
Nota
Para $i = 1$, hay un objeto con rareza $8$ y costo $7$. Como no podemos elegir un subconjunto de un solo objeto tal que la suma de costos sea al menos $12$, la respuesta es $-1$.
Para $i = 2$, hay dos objetos, y la única forma de elegir un subconjunto valioso es tomar ambos objetos. La rareza total será $8 \mid 2 = 10$.
Para $i = 3$, cualquier subconjunto de dos o más objetos será valioso. La elección óptima es seleccionar el segundo y el tercer objeto, y su rareza total será $2 \mid 3 = 3$.
Para $i = 4$, se vuelve posible elegir solo el cuarto objeto, cuyo costo es suficiente, y su rareza es $1$, que es la mínima posible. Para $i = 5$, también es óptimo elegir solo el cuarto objeto.