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

Problem 6: City Horizon [Richard Ho, 2007]

Farmer John has taken his cows on a trip to the city! As the sun
sets, the cows gaze at the city horizon and observe the beautiful
silhouettes formed by the rectangular buildings.

The entire horizon is represented by a number line with N (1 <= N
<= 40,000) buildings. Building i's silhouette has a base that spans
locations A_i through B_i along the horizon (1 <= A_i < B_i <=
1,000,000,000) and has height H_i (1 <= H_i <= 1,000,000,000).
Determine the area, in square units, of the aggregate silhouette
formed by all N buildings.

PROBLEM NAME: horizon

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Input line i+1 describes building i with three
        space-separated integers: A_i, B_i, and H_i

SAMPLE INPUT (file horizon.in):

4
2 5 1
9 10 4
6 8 2
4 6 3


OUTPUT FORMAT:

* Line 1: The total area, in square units, of the silhouettes formed
        by all N buildings

SAMPLE OUTPUT (file horizon.out):

16

OUTPUT DETAILS:

The first building overlaps with the fourth building for an area of 1
square unit, so the total area is just 3*1 + 1*4 + 2*2 + 2*3 - 1 = 16.

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

Problem 7: Catch That Cow [Jeffrey Wang, 2007]

Farmer John has been informed of the location of a fugitive cow and
wants to catch her immediately. He starts at a point N (0 <= N <=
100,000) on a number line and the cow is at a point K (0 <= K <=
100,000) on the same number line. Farmer John has two modes of
transportation: walking and teleporting.

    * Walking: FJ can move from any point X to the points X-1 or
      X+1 in a single minute

    * Teleporting: FJ can move from any point X to the point 2*X
      in a single minute.

If the cow, unaware of its pursuit, does not move at all, how long
does it take for Farmer John to retrieve it?

PROBLEM NAME: catchcow

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

SAMPLE INPUT (file catchcow.in):

5 17

INPUT DETAILS:

Farmer John starts at point 5 and the fugitive cow is at point 17.

OUTPUT FORMAT:

* Line 1: The least amount of time, in minutes, it takes for Farmer
        John to catch the fugitive cow.

SAMPLE OUTPUT (file catchcow.out):

4

OUTPUT DETAILS:

The fastest way for Farmer John to reach the fugitive cow is to
move along the following path: 5-10-9-18-17, which takes 4 minutes.

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

Problem 8: Fliptile [Richard Ho, 2006]

Farmer John knows that an intellectually satisfied cow is a happy
cow who will give more milk. He has arranged a brainy activity for
cows in which they manipulate an M x N grid (1 <= M <= 15; 1 <= N
<= 15) of square tiles, each of which is colored black on one side
and white on the other side.

As one would guess, when a single white tile is flipped, it changes
to black; when a single black tile is flipped, it changes to white.
The cows are rewarded when they flip the tiles so that each tile
has the white side face up. However, the cows have rather large
hooves and when they try to flip a certain tile, they also flip all
the adjacent tiles (tiles that share a full edge with the flipped
tile). Since the flips are tiring, the cows want to minimize the
number of flips they have to make.

Help the cows determine the minimum number of flips required, and
the locations to flip to achieve that minimum. If there are multiple
ways to achieve the task with the minimum amount of flips, return
the one with the least lexicographical ordering in the output when
considered as a string.  If the task is impossible, print one line
with the word "IMPOSSIBLE".

PROBLEM NAME: fliptile

INPUT FORMAT:

* Line 1: Two space-separated integers: M and N

* Lines 2..M+1: Line i+1 describes the colors (left to right) of row i
        of the grid with N space-separated integers which are 1 for
        black and 0 for white

SAMPLE INPUT (file fliptile.in):

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1


OUTPUT FORMAT:

* Lines 1..M: Each line contains N space-separated integers, each
        specifying how many times to flip that particular location.

SAMPLE OUTPUT (file fliptile.out):

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0

OUTPUT DETAILS:

After flipping at row 2 column 1, the board will look like:
0 0 0 1
1 0 1 0
1 1 1 0
1 0 0 1

After flipping at row 2 column 4, the board will look like:
0 0 0 0
1 0 0 1
1 1 1 1
1 0 0 1

After flipping at row 3 column 1, the board will look like:
0 0 0 0
0 0 0 1
0 0 1 1
0 0 0 1

After flipping at row 3 column 4, the board will look like:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Another solution might be:
0 1 1 0
0 0 0 0
0 0 0 0
0 1 1 0
but this solution is lexicographically higher than the solution above.

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