Marvin le Martien prépare un sac à dos. Devant lui se trouvent $n$ objets, numérotés de $1$ à $n$. Chaque objet possède deux caractéristiques : le $i$-ième objet a une étrangeté $w_i$ et un coût $c_i$. L'étrangeté d'un objet est un entier naturel dont la représentation binaire contient au plus $k$ bits ($0 \le w_i < 2^k$), et le coût d'un objet est un entier naturel ne dépassant pas $10^9$ ($0 \le c_i \le 10^9$).
Le coût total d'un ensemble d'objets est la somme des coûts des objets qu'il contient, et l'étrangeté totale de cet ensemble est définie comme le OU bit à bit des étrangetés des objets qu'il contient.
Marvin appelle un ensemble d'objets précieux si son coût total est au moins $C$. Pour chaque $i$ de $1$ à $n$, Marvin veut choisir un ensemble précieux d'objets parmi les objets dont l'indice ne dépasse pas $i$ tel que son étrangeté totale soit la plus petite possible.
Le OU bit à bit d'un ensemble d'entiers est défini comme suit : on considère les représentations binaires de ces nombres. Le $i$-ième bit du résultat vaut $1$ si le $i$-ième bit d'au moins un des nombres de l'ensemble vaut $1$. Dans les langages de programmation, cette opération est notée par le symbole « | ». Par exemple, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.
Entrée
La première ligne contient trois entiers $n$, $k$ et $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) — le nombre d'objets, la limite sur le nombre de bits dans la représentation binaire de l'étrangeté, et le coût minimal d'un sous-ensemble précieux.
Chacune des $n$ lignes suivantes contient deux entiers $w_i$ et $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) — l'étrangeté et le coût de l'objet correspondant, respectivement.
Sortie
Affichez $n$ entiers, où le $i$-ième entier doit être égal à l'étrangeté totale minimale d'un sous-ensemble précieux des $i$ premiers objets. S'il est impossible de choisir un sous-ensemble précieux, affichez $-1$.
Sous-tâches
| Sous-tâche | Points | $n$ | $k$ | Contraintes supplémentaires | Sous-tâches requises |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | Exemples | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | Exemples, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | Exemples, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | Tous les $w_i$ sont des puissances de deux | |
| 5 | 11 | $n \le 2\,000$ | Exemples, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | Exemples, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | Exemples, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | Exemples, 1–4, 6–7 | ||
| 9 | 11 | Exemples, 1–8 |
Exemples
Entrée 1
5 4 12 8 7 2 6 3 6 1 12 3 5
Sortie 1
-1 10 3 1 1
Remarque
Pour $i = 1$, il y a un objet d'étrangeté $8$ et de coût $7$. Comme on ne peut pas choisir un sous-ensemble d'un seul objet tel que la somme des coûts soit au moins $12$, la réponse est $-1$.
Pour $i = 2$, il y a deux objets, et la seule façon de choisir un sous-ensemble précieux est de prendre les deux objets. L'étrangeté totale sera $8 \mid 2 = 10$.
Pour $i = 3$, tout sous-ensemble d'au moins deux objets sera précieux. Le choix optimal est de sélectionner le deuxième et le troisième objet, et leur étrangeté totale sera $2 \mid 3 = 3$.
Pour $i = 4$, il devient possible de ne choisir que le quatrième objet, dont le coût est suffisant, et son étrangeté est $1$, ce qui est le minimum possible. Pour $i = 5$, il est également optimal de ne choisir que le quatrième objet.