**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Sumsets [Marek Turski, 2002]

Farmer John commanded his cows to search for different sets of
numbers that sum to a given number. The cows use only numbers that
are an integer power of 2.  Here are the possible sets of numbers
that sum to 7:

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

Help FJ count all possible representations for a given integer N
(1 <= N <= 1,000,000).

PROBLEM NAME: sumset

INPUT FORMAT:

A single line with a single integer, N.

SAMPLE INPUT (file sumset.in):

7

OUTPUT FORMAT:

The number of ways to represent N as the indicated sum.  Due to the
potential huge size of this number, print only last 9 digits (in base
10 representation).

SAMPLE OUTPUT (file sumset.out):

6

**********************************************************************

Problem 7: Watchcow [Coaches, 2004]

Bessie's been appointed the new watch-cow for the farm. Every night,
it's her job to walk across the farm and make sure that no evildoers
are doing any evil. She begins at the barn, makes her patrol, and
then returns to the barn when she's done.

If she were a more observant cow, she might be able to just walk
each of M (1 <= M <= 50,000) bidirectional trails numbered 1..M
between N (2 <= N <= 10,000) fields numbered 1..N on the farm once
and be confident that she's seen everything she needs to see.  But
since she isn't, she wants to make sure she walks down each trail
exactly twice.  It's also important that her two trips along each
trail be in opposite directions, so that she doesn't miss the same
thing twice.

A pair of fields might be connected by more than one trail.  Find
a path that Bessie can follow which will meet her requirements.
Such a path is guaranteed to exist.

PROBLEM NAME: watchcow

INPUT FORMAT:

* Line 1: Two integers, N and M.

* Lines 2..M+1: Two integers denoting a pair of fields connected by a
        path.

SAMPLE INPUT (file watchcow.in):

4 5
1 2
1 4
2 3
2 4
3 4

OUTPUT FORMAT:

* Lines 1..2M+1: A list of fields she passes through, one per line,
        beginning and ending with the barn at field 1. If more than
        one solution is possible, output any solution.

SAMPLE OUTPUT (file watchcow.out):

1
2
3
4
2
1
4
3
2
4
1

OUTPUT DETAILS:

Bessie starts at 1 (barn), goes to 2, then 3, etc...

**********************************************************************

Problem 8: Moo Volume [Brian Dean, 2004]

Farmer John has received a noise complaint from his neighbor, Farmer
Bob, stating that his cows are making too much noise.

FJ's N cows (1 <= N <= 10,000) all graze at various locations on a
long one-dimensional pasture.  The cows are very chatty animals.
Every pair of cows simultaneously carries on a conversation (so
every cow is simultaneously MOOing at all of the N-1 other cows).
When cow i MOOs at cow j, the volume of this MOO must be equal to
the distance between i and j, in order for j to be able to hear the
MOO at all.  Please help FJ compute the total volume of sound being
generated by all N*(N-1) simultaneous MOOing sessions.

TIME LIMIT: 0.05 seconds

PROBLEM NAME: volume

INPUT FORMAT:

* Line 1: N

* Lines 2..N+1: The location of each cow (in the range
        0..1,000,000,000).

SAMPLE INPUT (file volume.in):

5
1
5
3
2
4

INPUT DETAILS:

There are five cows at locations 1, 5, 3, 2, and 4.

OUTPUT FORMAT:

* Line 1: A single integer, the total volume of all the MOOs.

SAMPLE OUTPUT (file volume.out):

40

OUTPUT DETAILS:

Cow at 1 contributes 1+2+3+4=10, cow at 5 contributes 4+3+2+1=10, cow at 3
contributes 2+1+1+2=6, cow at 2 contributes 1+1+2+3=7, and cow at 4
contributes 3+2+1+1=7.  The total volume is (10+10+6+7+7) = 40.

**********************************************************************