你有一个背包，有 nnn 个物品，第 iii 个物品由二元组 (ai,bi)(a_i, b_i)(ai,bi) 表示。你想选出一些物品使得选出的物品不存在某个非空的物品的子集，其 aia_iai 的异或和为 0，但又想让选出的物品 bib_ibi 之和尽可能大。
背包开始是空的，物品逐个加入，你想知道每加入一个物品后的答案。
第一行一个正整数 nnn (1≤n≤1051\leq n \leq 10^51≤n≤105)。
之后 nnn 行，第 iii 行两个正整数 ai,bia_i, b_iai,bi 描述物品（0≤ai<1018,0≤bi≤1090\leq a_i < 10^{18}, 0\leq b_i \leq 10^90≤ai<1018,0≤bi≤109）。
输出 nnn 行，每行一个整数表示答案。
样例输入1
5 2 4 5 1 3 3 1 5 0 9
样例输出1
4 5 8 10 10