{"problem":{"name":"「Cfz Round 2」Weighted Mean","description":{"content":"给定一个长度为 $n$ 的序列 $a$ 和一个整数 $m$，保证序列 $a$ 中的每个元素均为不大于 $m$ 的正整数，且每个元素互不相等。 你需要构造一个长度为 $n$ 的序列 $b$，满足： - 序列 $b$ 中的每个元素均为不大于 $m$ 的正整数； - $\\dfrac{\\sum\\limits_{i=1}^n (a_i \\cdot b_i)}{\\sum\\limits_{i=1}^n b_","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10311"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的序列 $a$ 和一个整数 $m$，保证序列 $a$ 中的每个元素均为不大于 $m$ 的正整数，且每个元素互不相等。\n\n你需要构造一个长度为 $n$ 的序列 $b$，满足：\n\n- 序列 $b$ 中的每个元素均为不大于 $m$ 的正整数；\n- $\\dfrac{\\sum\\limits_{i=1}^n (a_i \\cdot b_i)}{\\sum\\limits_{i=1}^n b_i}$ 为整数，即 $a_i$ 的权为 $b_i$ 时，序列 $a$ 的加权平均数为整数；\n- 不存在有序三元整数组 $(i,j,k)$，满足 $1\\le i<j<k\\le n$ 且 $b_i=b_j=b_k$；\n\n或报告无解。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据：\n\n- 第一行输入两个整数 $n,m$。\n- 第二行输入 $n$ 个整数，表示给定的序列 $a$。\n\n## Output\n\n对于每组测试数据，输出一行：\n\n- 若存在满足条件的序列 $b$，则输出用空格分隔的 $n$ 个整数，表示你构造的序列 $b$；\n- 若不存在满足条件的序列 $b$，则输出 $-1$。\n\n**所有满足要求的输出均可通过。**\n\n[samples]\n\n## Note\n\n#### 「样例解释 #1」\n\n对于第 $1$ 组测试数据，给出的样例的加权平均数为 $\\dfrac{1 \\times 1+2 \\times 2 + 3 \\times 1}{1+2+1}=2$，为整数。\n\n输出 `1 5 1` 也视作正确，其加权平均数为 $2$。\n\n但是输出 `1 6 1` 不正确，虽然其加权平均数为 $2$，但是 $b_2>5$。\n\n输出 `1 2 3` 也不正确，其加权平均数为 $\\dfrac{7}{3}$，不为整数。\n\n输出 `1 1 1` 也不正确，虽然其加权平均数为 $2$，但是存在有序三元组 $(1,2,3)$ 满足 $1 \\leq 1 < 2 < 3 \\leq 3$ 且 $b_1=b_2=b_3$。\n\n对于第 $2$ 组测试数据，可以证明不存在满足条件的序列 $b$。\n\n对于第 $3$ 组测试数据，给出的样例的加权平均数为 $\\dfrac{1 \\times 1+2 \\times 1 + 5 \\times 3+9 \\times 4}{1+1+3+4}=6$，为整数。\n\n#### 「数据范围」\n\n设 $\\sum n$ 表示单个测试点中 $n$ 的和。\n\n对于所有数据，$1 \\le T \\le 1000$，$1 \\le n \\le 10^6$，$1 \\le a_i \\le m \\le 10^9$，$\\sum n \\le 10^6$，保证序列 $a$ 中的每个元素间互不相等。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10311","tags":["数学","洛谷原创","Special Judge","O2优化","构造","洛谷月赛","Ad-hoc"],"sample_group":[["3\n3 5\n1 2 3\n2 2\n1 2\n4 100000\n1 2 5 9","1 2 1\n-1\n1 1 3 4\n"]],"created_at":"2026-03-03 11:09:25"}}