学士的书签
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

在埋首书海的生活中,象牙塔内的学士罕有见识鲜花的机会。为了排解书斋中的孤独,仰慕学士的少年带来了异域的花朵。学士精心收藏了这份心意,将它风干,在厚厚的书页间夹紧。从此以后,在学士如山的灰暗书卷中,多了一抹惊艳的色彩。


理学之士,崇尚理性与秩序,他试图以某种富有理性美的秩序排列他的花朵,正如他对知识与生活的态度。他为每个花朵分配了编号,并给出了美丽花朵排列的定义:


对于花朵排列{}^\dagger p,它的前缀和{}^\ddagger都不是 3 的倍数。


你是否能够在那片书页之间,构建出一组完美的花朵序列?正如学士在书斋中精心挑选与排列每一朵异域之花,赋予它们各自的色彩与意义。


排列{}^\dagger:长度为 n 的排列是一个包含从 1nn 个互不相同整数的数组,顺序可以是任意的。例如,[2, 3, 1, 5, 4] 是一个排列,而 [1, 2, 2] 不是排列(2 在数组中出现了两次),[1, 3, 4] 也不是排列(n = 3,但数组中有 4


前缀和{}^\ddagger:排列的前缀和是从起始位置到某个位置的所有元素的累加和,对于排列 p = [p_1, p_2, \dots, p_n],第 k 个前缀和为 S_k = p_1 + p_2 + \dots + p_k


形式化的,你需要构造一个长度为 n 的排列 p,使得下述表达式成立:
  \forall k \in [1, n],\ S_k = \sum_{i=1}^{k} p_i \not\equiv 0 \pmod{3} 
若无法构造这样的排列,则输出一个整数 -1。

输入描述:

第一行输入一个正整数 n \ (1 \le n \le 10^5),表示你要构造的排列长度。

输出描述:

如果可以构造这样的排列,输出一行包含以空格分隔的 n 个正整数 \textstyle p_1, p_2, \dots ,p_n ,如果存在多组方案,输出任意一组即可。


如果无法构造这样的排列,则输出一行一个整数 -1。

示例1

输入

复制
3

输出

复制
-1

说明

容易证明不存在任何一种排列满足题目要求。
示例2

输入

复制
4

输出

复制
1 4 2 3

说明

排列 [1, 4, 2, 3],它的前缀和数组为 [1,5,7,10] ,都不是 3 的倍数,所以满足题目要求。