{"raw_statement":[{"iden":"problem statement","content":"You are given $N$ non-negative integers $A_1,A_2,\\cdots,A_N$. For each $k=1,2,\\cdots,N$, solve the following problem.\nAlice and Bob play the following game.\n\n*   Alice chooses $k$ numbers from $A_1,A_2,\\cdots,A_N$. Let $x_1,x_2,\\cdots,x_k$ be the chosen numbers (in arbitrary order).\n    \n*   Bob makes a sequence of $2k$ non-negative integers $y=(y_1,y_2,\\cdots,y_{2k})$, which must satisfy the following conditions.\n    *   $0 \\leq y_1 \\leq y_2 \\leq \\cdots \\leq y_{2k}$.\n    *   Let $z_i=y_{2i-1} \\oplus y_{2i}$. Then, ${z_1,z_2,\\cdots,z_k}$ coincides with ${x_1,x_2,\\cdots,x_k}$ as a multiset.\n\nHere, $\\oplus$ denotes bitwise $\\mathrm{XOR}$.\nLet the **score** of the game be the value of $y_{2k}$. Bob plays to minimize the score. With this in mind, Alice plays to maximize the score. What will the score be?\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A\\ \\mathrm{XOR}\\ B$, is defined as follows.\n\n*   When $A\\ \\mathrm{XOR}\\ B$ is written in binary, the $k$\\-th lowest bit ($k \\geq 0$) is $1$ if exactly one of the $k$\\-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor instance, $3\\ \\mathrm{XOR}\\ 5 = 6$ (in binary: $011\\ \\mathrm{XOR}\\ 101 = 110$).  \nGenerally, the bitwise $\\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \\dots, p_k$ is defined to be $(\\dots ((p_1\\ \\mathrm{XOR}\\ p_2)\\ \\mathrm{XOR}\\ p_3)\\ \\mathrm{XOR}\\ \\dots\\ \\mathrm{XOR}\\ p_k)$, which one can prove to be independent of the order of $p_1, p_2, p_3, \\dots p_k$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 250000$\n*   $1 \\leq A_i \\leq 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"3\n1 2 3"},{"iden":"sample output 1","content":"2\n6\n6\n\nConsider the case $k=1$.\n\n*   If Alice chooses $x_1=1$: Bob makes $y=(0,1)$, for the score of $1$.\n*   If Alice chooses $x_1=2$: Bob makes $y=(0,2)$, for the score of $2$.\n*   If Alice chooses $x_1=3$: Bob makes $y=(1,2)$, for the score of $2$.\n\nThus, Alice will choose $x_1=2$ or $x_1=3$, for the score of $2$.\nConsider the case $k=2$. If Alice chooses $(x_1,x_2)=(2,3)$ and Bob makes $y=(1,2,4,6)$, the score will be $6$. This is an example of optimal play for both players, and the answer is $6$.\nConsider the case $k=3$. If Alice chooses $(x_1,x_2,x_3)=(1,2,3)$ and Bob makes $y=(0,1,1,2,4,6)$, the score will be $6$. This is an example of optimal play for both players, and the answer is $6$."},{"iden":"sample input 2","content":"5\n1 1 1 1 1"},{"iden":"sample output 2","content":"1\n3\n5\n7\n9"},{"iden":"sample input 3","content":"5\n1 2 4 8 16"},{"iden":"sample output 3","content":"16\n24\n28\n30\n31"},{"iden":"sample input 4","content":"20\n167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186"},{"iden":"sample output 4","content":"536870912\n1610612736\n2684354560\n3758096384\n4831838208\n4831838208\n4831838208\n4831838208\n4831838208\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664\n5100273664"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}