Играя в одну из популярных игр, программист Вася столкнулся с интересной задачей.
В игре присутствуют производители и потребители ресурсов, которые могут быть связаны конвейерными лентами. Конвейер работает, если у него есть работающие входное и выходное устройство. Не подключенный к выходному устройству, конвейер, со временем, переполняется и останавливается.
Для более гибкого управления, конвейерные ленты могут объединяться с помощью устройства, под названием «merger» или разъединяться с помощью устройства «splitter».
Устройство «merger» имеет 3 входа и один выход. Просматривая входы по очереди, устройство перекладывает предметы с входных конвейерных лент на выходную. Для корректной работы «merger»-а необходимо, чтобы предметы подавались конвейером хотя бы на один вход, и снимались с выхода (если выходному конвейеру будет некуда транспортировать предметы, или выходной конвейер остановится из-за переполнения, то устройство остановится).
Устройство «splitter» имеет 1 вход и 3 выхода. Принимая предметы со входного конвейера, «splitter» равномерно, по очереди, перемещает их на подключенные выходные конвейеры. То есть, если все три выхода подключены к работающим конвейерам, то входной поток будет разделен на 3 одинаковых (по 1/3), а если подключены только 2 выхода, то поток разделяется на 2 одинаковых (по 1/2).
В игре, для производства, часто необходимо разделить поток на 2 подпотока, в определенном соотношении . На Игровом форуме, Вася обнаружил несколько стандартных схем разделения потока в заданных пропорциях. Взглянув на эти схемы, Вася задумался, а правильно ли они работают?
Напишите программу, которая по заданной схеме, определит, в каком соотношении разделяется входной поток. Все проверяемые схему корректны, то есть не содержат простаивающих устройств, принимают на вход один поток, а выдают два.
Примечание. Для простоты, считайте что конвейеры и устройства могут работать с любой скоростью, вплоть до бесконечной.
Первая строка ввода содержит целое число $$$k$$$ ($$$0 \lt k \leqslant 32$$$). Далее следуют $$$k$$$ строк, описывающих схему соединения «splitter»-ов и «merger»-ов. Каждая строка содержит описание одного устройства. Устройства нумеруются числами от $$$1$$$ до $$$k$$$ в порядке их появления.
Описание «splitter»-а начинается с заглавной латинской буквы «S». Далее следуют 3 целых числа, разделенных пробелами – номера устройств, к которым подключены выходы устройства. Если выход не подключен, то в качестве номера указан $$$0$$$ (ноль).
Описание «merger»-а начинается с заглавной латинской буквы «M». Далее следует целое число – номер устройства, куда передается объединенный поток.
Разделяемый входной поток всегда поступает на устройство номер 1. Результат разделения поступает на специальные «устройства» с номерами $$$-1$$$ $$$-2$$$. Данные «устройства» используются строго однократно.
Каждое используемое устройство имеет, как минимум, по одному подключенному входу и выходу. От первого (входного) устройства есть путь к любому другому устройству, а от него – до одного из выходов.
Вывод состоит из двух чисел, разделенных пробелом: соотношения потоков, поступающих на выходы $$$-1$$$ и $$$-2$$$. Числа должны быть взаимно просты.
5 S 2 3 5 S 3 4 0 M -1 S 3 5 0 M -2
7 5
На рисунке приведена схема из первого теста.
На первого устройство поступает единичный поток. На стрелках указана доли от входного потока.
