GCD2

Cho một tập hợp (có thể chứa các phần tử trùng nhau) ban đầu rỗng, bạn sẽ lần lượt thực hiện \(N\) thao tác. Có hai loại thao tác:

• Thao tác \(1\) có dạng \((1, x)\): thêm số \(x\) vào tập hợp.
• Thao tác \(2\) có dạng \((2, x)\): loại bỏ một số \(x\) ra khỏi tập hợp; dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trong tập hợp trước khi thực hiện thao tác này.

Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của các số trong tập hợp. Nếu tập hợp rỗng, hãy in ra số \(1\).

Input

• Dòng đầu tiên là một số tự nhiên \(N\) (\(1 \le N \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng gồm \(2\) số \(t\) và \(x\), với \(t\) là loại thao tác và \(x\) là số cần được xử lí (\(1 \le t \le 2\), \(1 \le x \le 10^9\)).

Output

Gồm \(N\) dòng, dòng thứ \(i\) là ước chung lớn nhất của tập hợp sau khi thực hiện thao tác thứ \(i\).

Sample Input 1

6
1 8
1 12
1 10
1 8
2 8
2 8

Sample Output 1

8
4
2
2
2
2