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.

The first line contains an integer q (1 ≤ q ≤ 10⁵), 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 10⁹. It is guaranteed that operations remove only the integers which lie in the collection.

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.