For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Interesting Sequence

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBerland scientists noticed long ago that the world around them depends on Berland population. Due to persistent research in this area the scientists managed to find out that the Berland chronology starts from the moment when the first two people came to that land (it is considered to have happened in the first year). After one Berland year after the start of the chronology the population had already equaled 13 people (the second year). However, tracing the population number during the following years was an ultimately difficult task, still it was found out that if *d*_{i} — the number of people in Berland in the year of *i*, then either *d*_{i} = 12*d*_{i - 2}, or *d*_{i} = 13*d*_{i - 1} - 12*d*_{i - 2}. Of course no one knows how many people are living in Berland at the moment, but now we can tell if there could possibly be a year in which the country population equaled *A*. That's what we ask you to determine. Also, if possible, you have to find out in which years it could be (from the beginning of Berland chronology). Let's suppose that it could be in the years of *a*_{1}, *a*_{2}, ..., *a*_{k}. Then you have to define how many residents could be in the country during those years apart from the *A* variant. Look at the examples for further explanation.

Input

The first line contains integer *A* (1 ≤ *A* < 10^{300}). It is guaranteed that the number doesn't contain leading zeros.

Output

On the first output line print YES, if there could be a year in which the total population of the country equaled *A*, otherwise print NO.

If the answer is YES, then you also have to print number *k* — the number of years in which the population could equal *A*. On the next line you have to output precisely *k* space-separated numbers — *a*_{1}, *a*_{2}, ..., *a*_{k}. Those numbers have to be output in the increasing order.

On the next line you should output number *p* — how many variants of the number of people could be in the years of *a*_{1}, *a*_{2}, ..., *a*_{k}, apart from the *A* variant. On each of the next *p* lines you have to print one number — the sought number of residents. Those number also have to go in the increasing order.

If any number (or both of them) *k* or *p* exceeds 1000, then you have to print 1000 instead of it and only the first 1000 possible answers in the increasing order.

The numbers should have no leading zeros.

Examples

Input

2

Output

YES

1

1

0

Input

3

Output

NO

Input

13

Output

YES

1

2

0

Input

1729

Output

YES

1

4

1

156

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/24/2017 12:31:45 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|