Misael is a child that loves maths. This year he learned about operations with decimal numbers, simplifying fractions, maximum and minimum of a set.

But Misael is not an ordinary child. He knows programming and he proposed a challenge: He will give you a list of numbers and you must calculate all common divisors for all numbers on that list. The task is simple, but Misael offers you something even more interesting. The size list is variable, he can add as well as remove numbers. However Misael doesn't like the prime divisors, so you should exclude those numbers from the list.

Input

The first line contains the number of test cases, and each case consists of an integer N (1 ≤ N ≤ 100000): the number of operations to perform.

Each operation can be one of 3 types:

UPD ADD x: Updating the list by adding the element x to the list.

UPD REM x: Update the list by removing the element x from the list.

CON:  print common divisors to the entire list.

The range of values ​​of x is 1 ≤ x ≤ 10000. There can be more that one element with the given value on the list. When removing element, you only remove one element with the given value. It's guaranteed that at least one such element will exist.

Output

For each type operation CON print a line with non-prime common divisors listed in ascending order. If the list is empty, print -1.

Example

Input:
1
6
UPD ADD 6
CON
UPD ADD 12
CON
UPD REM 6
CON

Output:
1 6
1 6
1 4 6 12