#P18761. [Arc182B]|{floor(A_i/2^k)}|

[Arc182B]|{floor(A_i/2^k)}|

|{floor(A_i/2^k)}|

题目描述

给定正整数 N,KN,K。称一个长度为 NN、所有元素均在 11 到 2K−12^K-1(含两端)之间的整数序列为好序列。

好序列 A=(A1,A2,…,AN)A=(A_1,A_2,\ldots,A_N) 的得分定义为:能表示成

⌊Ai2k⌋\left\lfloor\frac{A_i}{2^k}\right\rfloor

的不同整数的数量,其中 ii 是 1≤i≤N1\le i\le N 的整数,kk 是任意非负整数。这里 kk 没有给定上界;当它充分大时结果为 00,所以 00 也计入得分。

例如 A=(3,5)A=(3,5) 时,能表示的不同整数为 0,1,2,3,50,1,2,3,5,得分为 55。

请构造一个得分最大的好序列。序列中允许重复元素。

每个输入文件包含 TT 组测试用例,分别求解。

限制

  • 1≤T≤1051\le T\le10^5。
  • 1≤N≤1051\le N\le10^5。
  • 1≤K≤301\le K\le30。
  • 同一输入文件中所有测试用例的 NN 之和不超过 2×1052\times10^5。
  • 所有输入均为整数。

输入格式

T
N_1 K_1
N_2 K_2
...
N_T K_T

其中第 ii 行参数是第 ii 组测试用例。

输出格式

输出 TT 行。第 ii 行输出对应测试用例的一个得分最大的好序列,即 NiN_i 个整数。若最优好序列不唯一,输出任意一个都可。

样例 1

输入:

3
3 3
7 2
8 20

输出:

5 6 7
2 2 3 3 1 3 3
662933 967505 876482 840117 1035841 651549 543175 781219

说明:第一组中,取 A=(5,6,7)A=(5,6,7),得到的整数集合为 {0,1,2,3,5,6,7}\{0,1,2,3,5,6,7\},得分为 77。也可以输出 (7,4,5)(7,4,5)、(6,5,4)(6,5,4) 等序列。