화성인 마빈은 배낭을 꾸리는 중이다. 그 앞에는 $1$부터 $n$까지 번호가 매겨진 $n$개의 물건이 있다. 각 물건은 두 가지 특성을 가진다: $i$번째 물건은 이상함 $w_i$와 비용 $c_i$를 갖는다. 물건의 이상함은 이진 표현이 최대 $k$비트를 포함하는 음이 아닌 정수($0 \le w_i < 2^k$)이고, 물건의 비용은 $10^9$를 넘지 않는 음이 아닌 정수($0 \le c_i \le 10^9$)이다.

물건 집합의 총 비용은 그 집합에 포함된 물건들의 비용의 합이고, 이 집합의 총 이상함은 그 집합에 포함된 물건들의 이상함의 비트 OR로 정의된다.

마빈은 총 비용이 $C$ 이상인 물건 집합을 가치 있는 집합이라고 부른다. $i = 1$부터 $n$까지 각 $i$에 대해, 마빈은 인덱스가 $i$를 초과하지 않는 물건들 중에서 가치 있는 집합을 고르되, 그 총 이상함이 가능한 한 작도록 하고 싶다.

정수 집합의 비트 OR는 다음과 같이 정의된다: 이 수들의 이진 표현을 생각하자. 그러면 결과의 $i$번째 비트는 집합에 있는 수들 중 적어도 하나의 $i$번째 비트가 $1$이면 $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$을 출력한다.

서브태스크

예제

입력 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$인 경우에도 네 번째 물건만 고르는 것이 최적이다.