Cake Distribution

Time limit1sMemory limit512 MB

Summary
Choose up to 5000 positive integer cake pieces so that for each of A, B, C guests they can be split evenly, labeling each piece with its recipient for each case.
Level

Hard8 of 10

Topics
Math, Number theory, Greedy, Implementation
Solved
No attempts yet

Problem

Your birthday is coming up, and you want to prepare a birthday cake weighing anywhere from 1 to 101810^{18} grams inclusive. You know that A, B, or C guests will attend the party. You want to cut this cake so that:

  • The weight of each piece is a positive integer number of grams.
  • No matter how many guests arrive, the pieces can be distributed among the guests so that each guest receives the same amount of cake. A guest may receive more than one piece.

You don't want to spend too much time cutting the cake, so you want at most 5,000 pieces. Let's do it!

Input

The only line of input contains the 3 numbers A, B, C, all positive integers not more than 1000.

Output

On the first line, output one number K, the number of pieces. On each of the next K lines, output a description of one piece, consisting of 4 numbers, wi, ai, bi, ci, where wi is the weight of the piece in grams and ai, bi, ci are the indices of the person who will get this piece if A, B, or C guests arrive, respectively. The indices must satisfy 1 ≤ ai ≤ A, 1 ≤ bi ≤ B, 1 ≤ ci ≤ C. The sum of all wi must be less than or equal to 101810^{18}.

Examples1

  1. Example 1

    Input
    1 2 3
    Expected output
    4
2 1 1 1
1 1 1 2
1 1 2 2
2 1 2 3