Goldbach's Conjecture

Problem Description

Let $d(x)$ be the sum of all divisors of $x$. $x$ is called a good number if every number from 1 to $d(x)$ can be expressed as a sum of distinct divisors of $x$. For example, $6$ is a good number, $d(6)=1+2+3+6=12$, $4=1+3,5=2+3,7=1+6$ and so on. Teacher Mai wants to know whether a even number $p$ can be expressed as a sum of two good numbers.

Input

There are multiple test cases(about $40000$). For each test case, there is only one line contains one even number $p(1\leq p\leq 10^{18})$. Most test cases are generated randomly.

Output

For each test case, print "YES" or "NO" in the first line. That means if is possible to express $p$ as a sum of two good numbers. If your answer is "YES", print two number $a,b$ in the second lines. Both $a$ and $b$ should be good numbers, and $a+b=p$. In the third and the fourth line, print the factorization of number $a$ and $b$. If $a=\prod_{i=1}^k p_i^{e_i}$, where $p_1<p_2<\cdots<p_k$, $p_i$ are all prime numbers and $e_i\geq 1$, you should print $k$ first, then $2k$ space-seperated numbers $p_1,e_1,p_2,e_2,\cdots,p_k,e_k$.

Sample Input

18

Sample Output

YES
6 12
2 2 1 3 1
2 2 2 3 1

Hint

0 is not a good number.

Author

xudyh

Source

2015 Multi-University Training Contest 9