#5267. 特工

内存限制:256 MiB 时间限制:10 Sec

题目描述

特工Star历经千辛万苦,潜入了敌国的信息中心。在那里,他盗取了一份含有重要情报的文件。这份文件是一个整
数序列{bi},其长度为N。根据已知的信息,敌国的文件都由下列方式加密而成:
{ai}为加密前的序列,它和{bi}有着相同的长度;bitcount(x)含义为计算x二进制位中1的个数。现在,请你帮助S
tar快速破译出加密前的序列{ai}。

输入格式

第一行一个整数N;
第二行N个整数,依次分别表示bi。
N ≤ 1500000,保证ai为不超过109的非负整数且N是2的次幂

输出格式

输出N个用空格隔开的整数,依次分别表示ai。

样例

样例输入


			
4
9 9 5 17

样例输出


			
3 6 2 6

数据范围与提示