Cho một tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác được thực hiện:

• 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\) trước khi thực hiện thao 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 tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số \(1\).

Input

• Dòng đầu tiên một số tự nhiên \(N\) (\(1 \leq N \leq 10^{5}\)).
• \(N\) dòng tiếp theo, mỗi dòng là 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 \leq t \leq 2\), \(1 \leq x \leq 10^{9}\)).

Output

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

Example

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

8 
4 
2 
2 
2 
2