喵喵的数字

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

喵喵喜欢数字~

但是她觉得数字总是按照 1 2 3 ....... n 这样排列太老土了!!!哼

她无意间看到了 Matrix67 的一篇blog(太神了。。)

int f(int x){
    int b , t , c , m , r;
    b = x & -x;
    t = x + b;
    c = t ^ x;
    m = (c >> 2) / b;
    r = t | m; //最终结果
    return r;
}

她觉得实在是太神了啊!!这段代码的作用你可以自己尝试一下,不过喵喵自己尝试了一发是对于每个x输出下一个y,满足 y 和 x 拆成二进制表示之后 1 的个数相等!

比如 6 的二进制表示是 (110)2 那么下一个数的二进制表示就是(1001)2 也就是9.

于是喵喵对于选定的一个数 N , 她把所有 [0 , N] (闭区间) 中的数依据如下算法重新排列了一下

operator (int A ,  int B){
    if (A 的 二进制表示中 1 的个数 > B 的 二进制表示中 1 的个数)  那么 A 比 B 大;
    else if (A 的 二进制表示中 1 的个数 < B 的 二进制表示中 1 的个数) 那么 B 比 A 大;
    else if (A < B) 那么 B 比 A 大;
    else if (A > B) 那么 A 比 B 大;
    else A 和 B 相等
}

比如 N = 8 的时候,数字的顺序是

0,1,2,4,8,3,5,6,7

由此,她想知道 对于 给定的 N ,第 M 小的数是几,前 M 小的数和是多少。(注意,第 0 小的一定是 0 , 第 1 小的才是 1)。

因为和神马的实在是太大了,喵喵只需要你告诉他答案对于 (109 + 9) 取模的答案就行啦。

P.S. 某次 TC 就是 109 + 9 坑出翔了,再错就打屁股啦!

0≤N≤1018 , 0≤M≤N

Input

第一行一个整数 T 代表数据组数。(T≤10000)                      <del>喵以人格担保时限肯定够!!!</del>

对于每组数据第一行两个整数 N , M。

Output

对于每组询问,输出两个整数 A , B 代表 “第 M 小的数” 和 “前 M 小的数字和 对于 (109 + 9) 取模” 的答案。(第一问不要取摸)

Sample Input

9
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8

Sample Output

0 0
1 1
2 3
4 7
8 15
3 18
5 23
6 29
7 36

Source

Dshawn

Manager

Information
Solved Number29
Submit Number161
Problem Tags
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel