题目描述

小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。

每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。 这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为OI选手的你，你能帮帮他吗？你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。

输入格式

第一行一个正整数$n$表示总时间；第二行$n$个整数$a_1,a_2,...,a_n$，若$a_i$大于0代表给了小葱一颗数字为$a_i$的小葱苗，否则代表从小葱手中拿走一颗数字为$-a_i$的小葱苗。

输出格式

输出共$n$行，每行一个整数代表第$i$个时刻的最大异或和。

输入数据示例

6
1 2 3 4 -2 -3

输出数据示例

1
3
3
7
7
5

提示

$n \leq 500000, a_i \leq 2^{31}-1$