30964번 - flippy mex

$\mathrm{mex}$는 주어진 수열에 없는 $0$ 이상의 정수 중 가장 작은 것을 가리키는 함수이다. 준서는 $\mathrm{mex}$를 좋아하는 시우를 위해 $N$장의 카드로 하는 놀이를 만들었다.

규칙은 다음과 같으며, $1$번 단계부터 $N$번 단계까지 진행한다.

• $i$번 단계에서, 준서가 $i$번 카드를 테이블에 놓는다. 카드의 앞면과 뒷면에는 각각 $0$ 이상의 정수 $A_i$, $B_i$가 적혀 있다.
• 시우는 테이블에 있는 $i$개의 카드를 뒤집는 $2^i$가지 경우 각각에 대해, 위를 향한 면에 적힌 수들을 수열로 보고 $\mathrm{mex}$ 값을 계산한다. 이후, 가능한 $\mathrm{mex}$ 값의 가짓수를 말한다.
• 준서는 시우의 답을 확인하고 $i + 1$번 단계로 넘어간다.

시우를 도와, 각 단계에서 시우가 말해야 하는 답을 찾아주자.

첫 번째 줄에 카드의 개수 $N$가 주어진다. $(1 \le N \le 10^6)$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 줄마다 순서대로 $i$번 카드의 정보를 의미하는 두 정수 $A_i, B_i$가 공백으로 구분되어 주어진다. $(0 \le A_i, B_i \le 10^6)$

$i$번째 줄에 시우가 $i$번 단계에서 말해야 하는 답을 출력한다.