Polish version    English version  
  History of OI -> VII OI 1999/2000 -> Problems


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
Stats
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
Niebieskie ksi.eczki
VII Olimpiada Informatyczna 1999/2000

Task: TRO
Author: Wojciech Rytter
Triple-arm crane

II stage contest  

A triple-arm crane places containers on railway wagons. The wagons are numbered in order 1, 2,... . On each wagon at most one container can be put. In one move the crane gets three containers from a storehouse and places them on wagons with numbers i, i+p and i+p+q, or on wagons with numbers i, i+q and i+p+q (for some constants p,q >= 1). The crane has to be programmed in such way, that it loads with containers the first n wagons of the train (the train has n+p+q wagons). The program consists of sequence of instructions. Each instruction describes one move of the crane. Such instruction forms a (x, y, z) triple, where 1 < x < y < z < n+p+q, and determines numbers of wagons, on which the crane has to place the containers. The program is correct if after its execution there is exactly one container on each of the first n wagons of the train.

Task

Write a program, which:

  • reads a description of the crane (numbers p and q) and a number of wagons to be loaded (n) from the text file TRO.IN
  • generates a correct program for the crane,
  • writes it to the text file TRO.OUT.

Input

The first and the only line of the text file TRO.IN contains exactly three positive integers separated by single spaces. These are adequately numbers p and q describing parameters of the crane and number n, being the number of the first wagons of the train to be loaded. These numbers satisfy inequalities 1 <= n <= 300000, 2 <= p+q <= 60000.

Output

The first line of the text file TRO.OUT should consist of exactly one integer m being the number of instructions in the program generated. Each of the next m lines should consist of exactly three integers x, y, z separated by single spaces, 1 <= x < y < z <= n+p+q, x <= n, y belongs to {x+p, x+q}, z = x+p+q. These are the numbers of the wagons, on which the crane has to put containers in a consecutive move.

Example

For the input file TRO.IN

2 3 10

the correct answer is the output file TRO.OUT

4
1 3 6
2 4 7
5 8 10
9 11 14



Print friendly version