Марвин Марсианин упаковывает рюкзак. Перед ним находятся $n$ предметов, пронумерованных от $1$ до $n$. Каждый предмет имеет две характеристики: $i$-й предмет имеет странность $w_i$ и стоимость $c_i$. Странность предмета — это неотрицательное целое число, двоичная запись которого содержит не более $k$ бит ($0 \le w_i < 2^k$), а стоимость предмета — это неотрицательное целое число, не превосходящее $10^9$ ($0 \le c_i \le 10^9$).
Общая стоимость набора предметов равна сумме стоимостей входящих в него предметов, а общая странность этого набора определяется как побитовое ИЛИ странностей входящих в него предметов.
Марвин называет набор предметов ценным, если его общая стоимость не меньше $C$. Для каждого $i$ от $1$ до $n$ Марвин хочет выбрать ценный набор предметов из предметов с индексами, не превосходящими $i$, такой, чтобы его общая странность была как можно меньше.
Побитовое ИЛИ набора целых чисел определяется следующим образом: рассмотрим двоичные записи этих чисел. Тогда $i$-й бит результата равен $1$, если $i$-й бит хотя бы одного из чисел набора равен $1$. В языках программирования эта операция обозначается символом «|». Например, $(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$.
Входные данные
Первая строка содержит три целых числа $n$, $k$ и $C$ ($1 \le n \le 2\,000\,000$, $1 \le k \le 22$, $1 \le C \le 10^{15}$) — количество предметов, ограничение на количество бит в двоичной записи странности и минимальная стоимость ценного подмножества.
Каждая из следующих $n$ строк содержит два целых числа $w_i$ и $c_i$ ($0 \le w_i < 2^k$, $0 \le c_i \le 10^9$) — странность и стоимость соответствующего предмета.
Выходные данные
Выведите $n$ целых чисел, где $i$-е число должно быть равно минимальной общей странности ценного подмножества первых $i$ предметов. Если выбрать ценное подмножество невозможно, выведите $-1$.
Подзадачи
| Подзадача | Баллы | $n$ | $k$ | Дополнительные ограничения | Требуемые подзадачи |
|---|---|---|---|---|---|
| 1 | 10 | $n \le 20$ | $k \le 10$ | Примеры | |
| 2 | 11 | $n \le 100$ | $k \le 10$ | Примеры, 1 | |
| 3 | 14 | $n \le 50\,000$ | $k \le 10$ | Примеры, 1–2 | |
| 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | Все $w_i$ являются степенями двойки | |
| 5 | 11 | $n \le 2\,000$ | Примеры, 1–2 | ||
| 6 | 18 | $n \le 500\,000$ | $k \le 16$ | Примеры, 1–3 | |
| 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | Примеры, 1–4, 6 | |
| 8 | 6 | $k \le 19$ | Примеры, 1–4, 6–7 | ||
| 9 | 11 | Примеры, 1–8 |
Примеры
Входные данные 1
5 4 12 8 7 2 6 3 6 1 12 3 5
Выходные данные 1
-1 10 3 1 1
Примечание
При $i = 1$ имеется один предмет со странностью $8$ и стоимостью $7$. Поскольку невозможно выбрать подмножество из одного предмета так, чтобы сумма стоимостей была не меньше $12$, ответ равен $-1$.
При $i = 2$ имеется два предмета, и единственный способ выбрать ценное подмножество — взять оба предмета. Общая странность будет равна $8 \mid 2 = 10$.
При $i = 3$ любое подмножество из двух или более предметов будет ценным. Оптимальный выбор — второй и третий предметы, их общая странность будет равна $2 \mid 3 = 3$.
При $i = 4$ становится возможным выбрать только четвёртый предмет, стоимость которого достаточна, а его странность равна $1$, что является минимально возможным. При $i = 5$ также оптимально выбрать только четвёртый предмет.