TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3652
  • Problem
  • P3652shallot
    Limits : Time Limit : 60000 MS   Memory Limit : 131072 KB
    Description

    小苗去市场上买了一捆小葱苗,她突然一时兴起,于是她在每颗小葱苗上写上一个数字,然后把小葱叫过来玩游戏。
    每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗,并且让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。
    这种小问题对于小葱来说当然不在话下,但是他的身边没有电脑,于是他打电话给同为OI选手的你,你能帮帮他吗?
    你只需要输出最大的异或和即可,若小葱手中没有小葱苗则输出嬰。

    Input Format

    输入第一行一个正整数T,表示测试数据组数。
    对于每组数据,
    第一行两个正整数n表示总时间;
    第二行n个整数a1; a2; ...; an,若ai大于0代表给了小葱一颗数字为ai的小葱
    苗,否则代表从小葱手中拿走一颗数字为ai的小葱苗。

    Output Format

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

    Sample Input

    6
    1 2 3 4 -2 -3

    Sample Output

    1
    3
    3
    7
    7
    5

    Hint

    n<=500000,ai<=2^31-1