Marvin the Martian pakuje plecak. Przed nim znajduje się $n$ przedmiotów, ponumerowanych od $1$ do $n$. Każdy przedmiot ma dwie cechy: $i$-ty przedmiot ma dziwność $w_i$ oraz koszt $c_i$. Dziwność przedmiotu jest nieujemną liczbą całkowitą, której reprezentacja binarna zawiera co najwyżej $k$ bitów ($0 \le w_i < 2^k$), a koszt przedmiotu jest nieujemną liczbą całkowitą nieprzekraczającą $10^9$ ($0 \le c_i \le 10^9$).
Łączny koszt zbioru przedmiotów to suma kosztów przedmiotów w nim zawartych, a łączna dziwność tego zbioru jest zdefiniowana jako bitowa alternatywa (OR) dziwności przedmiotów w nim zawartych.
Marvin nazywa zbiór przedmiotów wartościowym, jeśli jego łączny koszt wynosi co najmniej $C$. Dla każdego $i$ od $1$ do $n$, Marvin chce wybrać wartościowy zbiór przedmiotów spośród przedmiotów o indeksach nie większych niż $i$, tak aby jego łączna dziwność była jak najmniejsza.
Bitowa alternatywa (OR) zbioru liczb całkowitych jest zdefiniowana następująco: rozważmy reprezentacje binarne tych liczb. Wtedy $i$-ty bit wyniku wynosi $1$, jeśli $i$-ty bit co najmniej jednej z liczb w zbiorze wynosi $1$. W językach programowania operacja ta jest oznaczana symbolem „|”. Na przykład, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.
Wejście
Pierwszy wiersz zawiera trzy liczby całkowite $n$, $k$ oraz $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) — liczbę przedmiotów, ograniczenie na liczbę bitów w reprezentacji binarnej dziwności oraz minimalny koszt wartościowego podzbioru.
Każdy z kolejnych $n$ wierszy zawiera dwie liczby całkowite $w_i$ oraz $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) — odpowiednio dziwność i koszt danego przedmiotu.
Wyjście
Wypisz $n$ liczb całkowitych, gdzie $i$-ta liczba powinna być równa minimalnej łącznej dziwności wartościowego podzbioru pierwszych $i$ przedmiotów. Jeśli wybranie wartościowego podzbioru jest niemożliwe, wypisz $-1$.
Podzadania
| Podzadanie | Punkty | $n$ | $k$ | Dodatkowe ograniczenia | Wymagane podzadania |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | Przykłady | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | Przykłady, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | Przykłady, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | Wszystkie $w_i$ są potęgami dwójki | |
| 5 | 11 | $n \le 2\,000$ | Przykłady, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | Przykłady, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | Przykłady, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | Przykłady, 1–4, 6–7 | ||
| 9 | 11 | Przykłady, 1–8 |
Przykład
Wejście 1
5 4 12 8 7 2 6 3 6 1 12 3 5
Wyjście 1
-1 10 3 1 1
Uwagi
Dla $i = 1$ istnieje jeden przedmiot o dziwności $8$ i koszcie $7$. Ponieważ nie możemy wybrać podzbioru składającego się z pojedynczego przedmiotu, tak aby suma kosztów wynosiła co najmniej $12$, odpowiedzią jest $-1$.
Dla $i = 2$ istnieją dwa przedmioty i jedynym sposobem na wybranie wartościowego podzbioru jest wzięcie obu przedmiotów. Łączna dziwność wyniesie $8 \mid 2 = 10$.
Dla $i = 3$ każdy podzbiór dwóch lub więcej przedmiotów będzie wartościowy. Optymalnym wyborem jest wybranie drugiego i trzeciego przedmiotu, a ich łączna dziwność wyniesie $2 \mid 3 = 3$.
Dla $i = 4$ możliwe staje się wybranie tylko czwartego przedmiotu, którego koszt jest wystarczający, a jego dziwność wynosi $1$, co jest minimalną możliwą wartością. Dla $i = 5$ optymalnie jest również wybrać tylko czwarty przedmiot.