A high-security vault logs its internal arming counter twice during every inspection cycle: once while the counter reads some value k, and again one tick later while it reads k + 1. The vault's aging display can only show the bitwise OR of the two readings it captured, so only that OR value is ever written into the permanent inspection log -- never k or k + 1 by themselves. Auditors have confirmed that every value that has ever appeared in the log happens to be a prime number.

Given n prime log entries, recover, for each entry x, the smallest non-negative integer k for which k OR (k + 1) equals x -- the earliest possible counter reading consistent with that entry. There is exactly one prime that can never be produced by this OR process no matter what k is chosen; for any entry equal to that prime, report -1 instead.

Input format

Line 1: an integer n. Line 2: n space-separated integers, the log entries nums[0], ..., nums[n-1]. Each is guaranteed to be a prime number.

Output format

Print n integers separated by single spaces: for each i, the minimum non-negative integer k satisfying k OR (k + 1) == nums[i], or -1 if no such k exists.

Constraints

• 1 <= n <= 100
• 2 <= nums[i] <= 1000
• Each nums[i] is guaranteed to be a prime number.

3
2 3 5

-1 1 4

2
7 11

3 9