Вам предложили работу в секретном проекте Агентства Федеральной Безопасности под кодовым названием «НОД 2010». Основным объектом исследования является набор целых положительных чисел. Вы должны понять, как будет изменяться наибольший общий делитель всех чисел этого набора при добавлении в него новых чисел или удалении лежащих там чисел. В начале эксперимента набор чисел пуст.

В первой строке записано целое число q (1 ≤ q ≤ 10⁵) — количество операций с набором. Каждая из следующих q строк имеет вид «+ x» или «- x». В первом случае число x добавляется в набор, а во втором случае — удаляется из него. Число x целое, положительное и не превосходит 10⁹. Гарантируется, что из набора будут удаляться только числа, которые в нём лежат.

Выведите наибольший общий делитель всех чисел набора после каждой описанной операции. Согласно распоряжению 190р, наибольшим общим делителем пустого набора является единица.