題干：

Find out if it is possible to partition the first?nn?positive integers into two?non-empty?disjoint sets?S1S1?and?S2S2?such that:

gcd(sum(S1),sum(S2))>1gcd(sum(S1),sum(S2))>1

Here?sum(S)sum(S)?denotes the sum of all elements present in set?SS?and?gcdgcd?means thegreatest common divisor.

Every integer number from?11?to?nn?should be present in?exactly one?of?S1S1?or?S2S2.

Input

The only line of the input contains a single integer?nn?(1≤n≤450001≤n≤45000)

Output

If such partition doesn't exist, print "No" (quotes for clarity).

Otherwise, print "Yes" (quotes for clarity), followed by two lines, describing?S1S1and?S2S2?respectively.

Each set description starts with the set size, followed by the elements of the set in any order. Each set must be non-empty.

If there are multiple possible partitions?— print any of them.

Examples

Input

1

Output

No

Input

3

Output

Yes 1 2 2 1 3

Note

In the first example, there is no way to partition a single number into two non-empty sets, hence the answer is "No".

In the second example, the sums of the sets are?22?and?44?respectively. The?gcd(2,4)=2>1gcd(2,4)=2>1, hence that is one of the possible answers.

題目大意：

給一個數n，將1到n之間的整數，分成兩個集合，每組的和分別為sum1,sum2，要求這個集合的gcd(sum1,sum2)>1，輸出每組的大小和每一個元素。

解題報告：

? ?亂搞一下就可以了。，

AC代碼：

#include<bits/stdc++.h>using namespace std; const int MAX = 2e5 + 5; int main() {int n;cin>>n;if(n <= 2) {puts("No");return 0 ;}puts("Yes");int s1 = (n+1)/2;printf("1 %d\n",s1);printf("%d",n-1);for(int i = 1; i<=n; i++) {if(i == s1) continue;printf(" %d",i);}return 0 ; }//18:04 - 18:17

?

總結

以上是生活随笔為你收集整理的【CodeForces - 1038B 】Non-Coprime Partition （构造，数组特征）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。