#6540. 无聊的数对

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: FFjet

题目描述

如果一个数对 (x,y) 是无聊的,当且仅当 x\leq y ,且 x~ \mathrm{xor}~y 的二进制表示下有奇数个 1

如果让你求 [1,n] 内的所有无聊的数对,那实在是太简单辣!

所以为了使得题目毒瘤一点,给出 n 个区间 [l_i,r_i] ,你需要数出有几对无聊的数 (x,y) 满足 x y 都在 [l_1,r_1] \cup [l_2,r_2]... \cup [l_i,r_i] ,即两个数都在前 i 个区间的并里。

输入格式

第一行一个正整数 n

接下来 n 行每行两个整数 [l_i,r_i] ,表示第 i 个区间,保证 l_i\leq r_i

输出格式

输出 n 行,第 i 行一个整数表示有几对无聊的数 (x,y) 满足 x,y 都在前 i 个区间的并里。

样例

样例输入

5
1 7
3 10
5 7
4 111
222 12838

样例输出

12
25
25
3080
40500496

数据范围与提示

对于 30\% 的数据,有 1\leq n\leq 100 , 1\leq l_i\leq r_i \leq 100

对于 50\% 的数据,有 1\leq n\leq 1000 1\leq l_i \leq r_i \leq 2^{32}-1

对于 100\% 的数据,有 1\leq n \leq 10^5 , 1\leq l_i \leq r_i \leq 2^{32}-1