Under construction

Still being built. Things may change

Composed Rhythms

Time limit1sMemory limit1024 MB

Summary
Given N, the task is to split N into groups of sizes 2 and 3 that sum to exactly N and print one valid decomposition.
Level

Easy2 of 10

Topics
Math, Implementation
Solved
No attempts yet

Problem

A rhythm is composed of multiple beats. A single beat does not make up a rhythm, as the beats depend on each other. The rhythm can be subdivided into smaller components. For example, a rhythm of 77 beats can be subdivided into 44 beats and 33 beats, or alternatively into 22, 33, and 22 beats. However, a rhythm of 77 beats cannot be subdivided into 11, 33, and 33 beats, since one of the components does not form a rhythm.

This leaves 22 as the smallest group size of beats we can use to decompose a rhythm, but if we only use groups of size 22 then we cannot have an odd number of beats. Adding 33 as a group size allows us to decompose any rhythm, even if it has an odd number of beats.

Given the number of beats in a rhythm, provide one decomposition of the rhythm into groups of sizes 22 and 33.

Input

The first and only line of input contains a single integer NN (2≤N≤1062 \leq N \leq 10^6), the number of beats in the rhythm.

Output

First output one line with an integer KK, the number of groups in your decomposition. Then output a line with KK space-separated integers, each of which is 22 or 33. The groups must add up to exactly NN beats. If there are multiple correct answers, you may output any of them.

Examples1

  1. Example 1

    Input
    25
    
    Expected output
    9
    3 3 3 3 3 3 2 2 3