Trò chơi chia chu trình (Spider Nim)

Hai người chơi luân phiên thực hiện nước đi trên một tập hợp các chu trình. Ban đầu tập hợp rỗng. Trong nước đi của mình, người chơi phải chọn một chu trình có ít nhất $2$ đỉnh (giả sử chu trình đó có $x$ đỉnh) và thay nó bằng hai chu trình có $p$ và $x-p$ đỉnh, với $1\le p<x$ do người chơi tự chọn. Ai không thể đi được thì thua.

Bạn cần xử lý $n$ truy vấn. Truy vấn thứ $i$ thêm vào tập hợp một chu trình có $a_i$ đỉnh (tập hợp này là multiset — có thể chứa các chu trình giống nhau). Sau mỗi truy vấn, hãy cho biết nếu bắt đầu chơi với tập hợp hiện tại thì ai sẽ thắng, giả sử cả hai người chơi tối ưu và người chơi thứ nhất đi trước.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ — số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra $n$ dòng. Dòng thứ $i$ in $1$ nếu người chơi thứ nhất thắng sau truy vấn thứ $i$, ngược lại in $2$.

Ràng buộc

• $1\le n\le 100000$
• $1\le a_i\le {10}^9$

Ví dụ