#128. 锁屏图案? 当然是第k长的最好看!

    ID: 128 传统题 4000ms 256MiB 尝试: 33 已通过: 4 难度: 9 上传者: 标签>福建师范大学第26届低年级程序设计竞赛

锁屏图案? 当然是第k长的最好看!

Time limit: 4.0 seconds

Memory limit: 256 megabytes

We worship perfection because we can't have it; if we had it, we would reject it. ——The Book of Disquiet, Poet, Fernando Pessoa

题目描述

傅猫猫是一只很长的猫猫,为此它希望它生活中的一切东西都尽量得长来与它相适配,这当然也包括了它爪机中的锁屏图案.

傅猫猫爪机中的图案锁屏与人类的手机中的相同: 一共三行三列共99个点,同行同列的点间距相同.

在本题中我们从上到下,从左到右依次给他们编号191-9,如图:

image

你需要选择全部的99个点(每个点只能被选择11次),最终通过线段将它们顺次连接,以此来绘制锁屏图案.

注意,如果你将两点连线时经过了一个未被经过的点,则这种连线方式无效. 如:1321\quad3\quad2:你在连接1133时没有经过22这个点,那么你在连接1133时手机会自动帮你连上2. 但是2132 \quad 1 \quad 3这种连线方式则是合法的.

连完之后你可以得到一个编号序列,如"$5 \quad 9 \quad 1 \quad 8 \quad 2 \quad 7 \quad 3 \quad 4 \quad 6$"就代表了一个这样的锁屏图案:

image

不妨设同行的点间距为11,这样你的手指就需要在屏幕上移动:

$\sqrt{2} + 2\sqrt{2} + \sqrt{5} + 2 + \sqrt{5} + 2\sqrt{2} + \sqrt{5} + 2 = 4 + 5\sqrt{2} + 3\sqrt{5}$

的距离,可以证明这个编号序列是最长的锁屏图案.

傅猫猫想知道第kk长的锁屏图案的编号序列.

我们规定: 长度相同的锁屏图案,编号序列的字典序小的要更短,即我们比较两个编号序列中第一个不同的数字,数字小的字典序小. 如$5 \quad 9 \quad 1 \quad 8 \quad 2 \quad 7 \quad 3 \quad 4 \quad 6$和$5 \quad 9 \quad 1\quad 6 \quad 4 \quad 3 \quad 7 \quad 2 \quad 8$都具有相同的长度,但是它们第一个不同数字前一个为88,后一个为66,因此后一个要比前一个短.

输入

输入一共T(1T2105)T(1 \leq T \leq 2*10^5)组. 每组第一行有11个整数kk.代表傅猫猫想知道的第kk长的锁屏图案是什么.

输入保证kk合法.

输出

每组输出一行共99个整数代表第kk长的锁屏图案的编号序列.

5
1
114
514
666
140704
5 9 1 8 2 7 3 4 6
5 1 9 4 2 8 3 7 6
4 9 5 3 7 2 8 1 6
6 1 8 5 3 7 2 9 4
1 2 3 6 5 4 7 8 9

Postscript

For someone special: If I should meet thee After long years, How should I greet thee? — With silence and tears.