{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003e温大卫是校园内很出名的巨佬。 今天他打算出门踢足球,他一脚球就在小旋的新劳斯莱斯上留下了凹痕。artist最近在pdd上开了一家店,所以她为温大卫提供了一份工作,帮助他赚钱赔小旋汽车维修费:如果温大卫能展现一下他的编程能力,他能够成为artist的店的安全工程师。 否则,他就会非常惨!\u003c/p\u003e\n\u003cp\u003e你会得到n个正整数a1,a2,…,an。你要重新排列这些数,构造一个新数列b1,b2,…,bn,使得c1,c2,…,cn的字典序最大,其中ci \u003d GCD(b1,…,bi)。 \u003c/p\u003e\n\u003cp\u003e温大卫真的很怕这项简单的任务失败,因此他请求你解决它。\n\u003c/p\u003e\n\u003cp\u003e一个数列a字典序小于b,当且仅当以下一条成立:\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cul\u003e\u003c/ul\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cli\u003e a是b的前缀,但a短于b\u003c/li\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\n\u003cli\u003e 在第一个a与b数字不同的位置,a的那个数字小于b的那个数字\u003c/li\u003e\n\u003cp\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e每次测试包含多个样例。第一行是样例的数目t(1 \u0026lt;\u003d t \u0026lt;\u003d 1e3),下面描述每一个样例:\u003c/p\u003e\n\u003cp\u003e每个样例的第一行是一个整数n(1 \u0026lt;\u003d n \u0026lt;\u003d 1e3)----数列a的长度\u003c/p\u003e\n\u003cp\u003e第二行是n个整数a1,...,an(1 \u0026lt;\u003d ai \u0026lt;\u003d 1e3)----数列a\u003c/p\u003e\n\u003cp\u003e保证所有测试样例的n的总和不超过1e3。\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e对每个测试样例,输出一行答案----数列b。如果有多个可能答案,输出任意一种。\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e7\n2\n2 5\n4\n1 8 2 3\n3\n3 8 9\n5\n64 25 75 100 50\n1\n42\n6\n96 128 88 80 52 7\n5\n2 4 8 16 17\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e5 2 \n8 2 1 3 \n9 3 8 \n100 50 25 75 64 \n42 \n128 96 80 88 52 7 \n17 2 4 8 16 \n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e第一个测试样例中,有两种可能的排列b ---- [2, 5] 和 [5, 2]: 对于第一个c\u003d[2, 1],对于第二个c\u003d[5, 1]。\u003c/p\u003e\n\u003cp\u003e第三个测试样例中,数字9应该是b的第一个,GCD(9, 3)\u003d3, GCD(9, 8)\u003d1, 所以b的第二个数应该是3。\u003c/p\u003e\n\u003cp\u003e第七个测试样例中,前四个数字两两有一个公因数(2的幂次),但他们中没有一个能够做最优排列方案b的第一个数。\u003c/p\u003e"}}]}