While playing one of the popular games, programmer Vasya faced an interesting task.
The game contains producers and consumers of resources, which can be connected by conveyor belts. The conveyor works if it has a working input and output device. If it is not connected to an output device, the conveyor eventually overflows and stops.
For more flexible control, conveyor belts can be connected using a device called a «merger» or disconnected using a «splitter».
The «merger» has $$$3$$$ inputs and one output. Looking through the inputs one by one, the device shifts items from the input conveyor belts to the output. For the correct operation of the «merger», it is necessary that the items are supplied by the conveyor to at least one input and removed from the output (if the output conveyor has nowhere to transport the items, or the output conveyor stops due to overflow, the device stops).
The «splitter» has $$$1$$$ input and $$$3$$$ outputs. Receiving items from the input conveyor, the «splitter» moves them evenly, one by one, onto the connected output conveyors. That is, if all three outputs are connected to running conveyors, then the input flow will be divided into $$$3$$$ identical ($$$1/3$$$ each), and if only $$$2$$$ outputs are connected, then the flow will be divided into $$$2$$$ identical ($$$1/2$$$ each).
In the game, for production, it is often necessary to divide the flow into $$$2$$$ sub-flows, in a certain ratio. On the Game Forum, Vasya discovered several standard schemes for dividing the flow in specified proportions. Looking at these diagrams, Vasya wondered if it was possible to come up with an algorithm for any ratio using a reasonable number of auxiliary devices?
Suppose we have a ratio $$$n : m$$$ ($$$1 \leq n, m; n+m \leq 10^{6}$$$). Suggest a scheme for connecting «splitters» and «mergers» that splits the input flow in the proportion $$$n$$$ to $$$m$$$, using a total of no more than $$$48$$$ «splitters» and «mergers». There should be no stopped conveyors and devices in your scheme. If there are several such schemes, any of them is considered correct.
The only input line contains $$$2$$$ integer numbers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m; n+m \leq 10^{6}; gcd (n, m) = 1$$$), separated by a space.
If there is no solution, then the output should contain a single number $$$0$$$. If there is a solution, then the first line of the output contains an integer number $$$k$$$ ($$$0 \lt k \leq 48$$$). Then $$$k$$$ lines follow, describing the connection scheme of «splitters» and «mergers». Each line contains a description of one device. Devices are numbered from $$$1$$$ to $$$k$$$ in the order they appear.
The description of «splitter» begins with a capital Latin letter «S». This is followed by a space and $$$3$$$ integer numbers separated by spaces – the numbers of the devices to which the outputs of the device are connected. If the output is not connected, then $$$0$$$ (zero) should be stated as the number.
The description of «merger» begins with a capital Latin letter «M». This is followed by a space and an integer number – the device number to which the connected flow is sent.
The split input flow always goes to device number $$$1$$$. The result of the split should go to special «devices» numbered $$$-1$$$ and $$$-2$$$. These «devices» can only be used once.
7 5
5 S 2 3 5 S 3 4 0 M -1 S 3 5 0 M -2
1 4
5 M 2 S 3 4 5 S -1 4 5 M -2 M 1
Scheme $$$7 : 5$$$ splitting are follow:
