UOJ Logo Universal Online Judge

UOJ

#350. 新年的XOR

统计

在动物行为学中,Alpha对应动物群体中等级最高的个体,简而言之,就是人赢,那么AlphaGo自然就是人赢狗了。

但是狗群中还有众多的SingleDog,平日里他们和AlphaGo和谐相处,忍受着酸臭味自得其乐的活下去。但在2月14日这天,当AlphaGo在SingleDog们最后的防线——朋友圈秀恩爱的时候,他们实在按耐不住,决定密谋用FFF团的黑暗力量,打败AlphaGo。

但是AlphaGo的智商很高,很快便拦截了SingleDog们传输消息的异或值。为了让AlphaGo相信,SingleDog们只是在数朋友圈里的狗粮数,你,勇敢无畏的跳蚤,决定编造一个弥天大谎。

AlphaGo截获的是一个整数 $n$,你需要构造一个长度大于 $1$ 的区间 $[L,R]$ 使得区间中所有整数的异或和恰好为 $n$。

输入格式

第一行输入一个整数 $t$ 表示数据组数。

接下来 $t$ 行每行一个整数 $n$。

输出格式

每组数据输出两个空格隔开的整数 $L,R$,表示你构造的区间。要求 $1 \leq L < R \leq 10^{18}$。

输入保证存在这样的区间。

样例

input

3
0
4
12

output

8 67
97 100
87 90

限制与约定

测试点编号 $n$的规模 其他
1$n \leq 100$
2
3$n \leq 2 \times 10^3$
4
5$n \leq 10^6$
6
7$n \leq 10^{18}$存在 $|R-n|\leq 100$ 的合法解
8
9
10

对于 $100\%$ 的数据,$n \geq 0, 1 \leq t \leq 100$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载