C. Монстры и бриллианты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Красная Шапочка нашла одного монстра и книгу о монстрах. В книге она нашла информацию о том, что всего существует n типов монстров, и каждый тип монстра имеет номер (целое число от 1 до n). А также, что если монстра накормить пирожком, то он превратится в несколько (возможно, ноль) других или таких же монстров, и несколько (не менее одного) бриллиантов. Известно, что монстр определенного типа может превращаться несколькими способами.

Красная Шапочка взяла монстра и посадила его на полянке. Затем она накормила его пирожком. Покуда на полянке есть хотя бы один монстр, Красная Шапочка продолжает кормить их пирожками. В конце, когда монстров больше не осталось, она собирает все бриллианты, которые получились в процессе превращений монстров.

Вам дана информация о всех возможных превращениях: для каждого превращения определенного типа монстра, во что он превратится. Известно, что для каждого типа монстра имеется хотя бы одно превращение. Некоторые типы монстров могут иметь больше одного варианта превращения, тогда в тот момент, когда такой монстр превращается, Красная Шапочка выбирает, какое именно превращение будет иметь место в этот раз.

Для каждого типа монстра определите, каково наименьшее и наибольшее количество бриллиантов, которое Красная Шапочка может собрать к моменту, когда на полянке не останется монстров, если изначально у нее будет один монстр этого типа. Учтите, Красная Шапочка имеет бесконечно большой запас пирожков.

Входные данные

В первой строке содержится два целых числа: m и n (1 ≤ m, n ≤ 105), количество возможных превращений и количество различных типов монстров. В последующих m строках перечислены превращения по одному в строке. Описание каждого превращения начинается с целого числа (типа монстра) mi (1 ≤ mi ≤ n), а затем положительного целого числа li, обозначающего количество монстров и бриллиантов, в которые может превратиться текущий монстр. Далее в строке следуют li целых чисел — во что превращается текущий монстр: положительное число обозначает монстра соответствующего типа, -1 обозначает бриллиант.

Для каждого типа монстра существует хотя бы одно превращение. Каждое превращение содержит хотя бы один бриллиант. Сумма всех li не превышает 105.

Выходные данные

Для каждого типа монстра, в порядке их номеров, выведите одну строку с двумя целыми числами: минимальное и максимальное количество бриллиантов, которое можно получить к моменту, когда на полянке не останется ни одного монстра, если начать с одним монстром этого типа. Если, начав с этого монстра, Красная Шапочка не имеет никакого шанса остаться без монстров на полянке, выведите -1 вместо минимального и -1 вместо максимального значения. Если, начав с этим монстром, Красная Шапочка может получить произвольно большое количество бриллиантов, выведите -2 вместо максимального значения.

Если любое значение в выходных данных превышает 314000000 (но является конечным), выведите 314000000 вместо этого значения.

Примеры
Входные данные
6 4
1 3 -1 1 -1
1 2 -1 -1
2 3 -1 3 -1
2 3 -1 -1 -1
3 2 -1 -1
4 2 4 -1
Выходные данные
2 -2
3 4
2 2
-1 -1
Входные данные
3 2
1 2 1 -1
2 2 -1 -1
2 3 2 1 -1
Выходные данные
-1 -1
2 2