ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1846. GCD 2010

Time limit: 0.5 second
Memory limit: 64 MB
You have got a job offer from a secret project of the Agency of Federal Security under the code name “GCD 2010”. The subject of research is a collection of positive integer numbers. Your goal is to calculate how the greatest common divisor of all numbers in this collection changes as we insert numbers into this collection and remove them from it. At the beginning of the experiment, the collection is empty.

Input

The first line contains an integer q (1 ≤ q ≤ 105), which is the number of operations with the collection. Each of the next q lines has either the form “+ x” or “- x”. In the first case, number x is inserted into the collection, in the latter case it is removed from the collection. The number x is a positive integer not exceeding 109. It is guaranteed that operations remove only the integers which lie in the collection.

Output

Output the greatest common divisor of all numbers in the collection after each of the given operation. According to the 190R order, the greatest common divisor of an empty collection is equal to one.

Sample

inputoutput
5
+ 8
+ 6
+ 8
- 8
- 8
8
2
2
2
6
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2010