给定一个包含 n 个元素的数组,您必须以尽可能少的移动次数将其变成互质数组。
在每次移动中,您可以在数组中的任何位置插入任何不大于 109 的正整数。
如果一个数组的任何两个相邻数字互质,则该数组是互质的。
在数论中,如果唯一能整除两个整数 a 和 b 的正整数是 1,则称这两个整数 a 和 b 互质。
输入
第一行包含整数 n (1 ≤ n ≤ 1000) — 给定数组中的元素数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 数组 a 的元素。
输出
在第一行打印整数 k — 添加到数组 a 使其互质所需的最少元素数。
第二行应包含 n + k 个整数 aj — 向数组 a 添加 k 个元素后的元素。请注意,新数组应该是互质的,因此任何两个相邻的值都应该是互质的。另外,新数组应该从原始数组 a 中添加 k 个元素来获得。
如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
3 2 7 28
输出 #1
1 2 7 9 28