#P8284. 「DAOI R1」Concert

「DAOI R1」Concert

题目背景

I want to be an artist. \texttt{I want to be an artist.}

题目描述

Erinyes \texttt{Erinyes} 的学校将举办一场音乐会,但是他若想加入其中就必须经过一场考核,试题如下:

给定两个整数 n,k n,k ,表示有 n n 个同学,你需要给每位同学分发一个数字,即对于整数 n n 构造一个序列 a a

同学得到的数字必须满足如下性质:

  • 对于每个 i  (1in1) i\;(1 \leq i \leq n-1) ,满足 ai=gcd(ai+1,ai+2,,an1,an) a_i=\gcd(a_{i+1},a_{i+2},\dots,a_{n-1},a_n)
  • 对于每个 i  (1in) i\;(1 \leq i \leq n) ,满足 1ai105 1 \leq a_i \leq 10^5
  • 对于每个 i  (1i105) i\;(1 \leq i \leq 10^5) ai a_i 至多在序列中出现 k k 次。

但这对 Erinyes \texttt{Erinyes} 来说太简单了,所以他决定专心准备节目,而这个问题则将交给你。

你的任务是输出这样的序列的个数 l l 以及所有这样的序列。但是由于答案可能会很大,所以我们对输出做了如下规定:

  • 对于 l=0 l=0 ,输出 Impossible
  • 对于 1l4 1 \leq l \leq 4 ,输出序列实际个数,接下来 l l 行,每行一个序列,表示你所构造的序列。
  • 对于 l5 l \geq 5 ,输出 5 or more,接下来五行,每行一个序列,表示你所构造的序列中字典序最小的五个。
  • 你必须按照字典序输出。

输入格式

第一行读入一个整数 t t ,表示有 t t 组数据。

对于每组数据,读入两个整数 n,k n,k

输出格式

对于每组数据,第一行输出一个整数或一个字符串。倘若可以构造,接下来每行输出一个你所构造的字符串。

4
1 1
97 0
17 1
5 2
5 or more
1
2
3
4
5
Impossible
Impossible
Impossible

提示

样例解释

对于第一组数据,可以发现此方案是最优解。

对于第二组数据,无论如何也无法构造出正确的序列。

对于第三组数据,无论如何也无法构造出正确的序列。

对于第四组数据,无论如何也无法构造出正确的序列。

数据规模

对于 100% 100\% 的数据,$ 1 \leq t \leq 100,1 \leq n \leq 10^5,0 \leq k \leq 10^5 $