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 schemes, Vasya wondered do they work correctly?
Write a program that, according to a given scheme, will determine in what ratio the input flow is divided. All tested schemes are correct, that is, they do not contain idle devices, they accept one flow as input, and output two.
The first line of input contains integer number $$$k$$$ ($$$0 \lt k \leq 32$$$). 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 $$$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) is stated as the number.
The description of «merger» begins with a capital Latin letter «M». This is followed by an integer number - the device number to which the combined flow is sent. The split input flow always goes to device number $$$1$$$. The result of the split goes to special «devices» numbered $$$-1$$$ and $$$-2$$$. These «devices» are used strictly one time.
Each device used has at least one connected input and output. From the first (input) device there is a path to any other device, and from it – to one of the outputs.
The output consists of two numbers separated by a space: the ratio of flows going to outputs $$$-1$$$ and $$$-2$$$.
5 S 2 3 5 S 3 4 0 M -1 S 3 5 0 M -2
7 5
Picture for example:
