Беси устала от холодной зимы и решила выбраться на каникулах в местечко потеплее. К несчастью коров перевозит только Air Bovinia.

Air Bovinia имеет n самолётов, каждый из которых летает по специфическому маршруту, состоящему из двух или более городов. Например, самолёт может лететь по маршруту, который начинается в городе 1, затем летит в город 5. затем в город 2, и потом в город 8. Никакой город не появится в этом маршруте 2 или более раз. Если Беси выбрала маршрут, она может сесть на самолёт в любом городе маршрута и выйти из самолёта в любом городе маршрута. Например, она не обязана садиться в первом городе маршрута а выходить в последнем городе маршрута. Каждый маршрут имеет свою цену и Беси должна платить её всю вне зависимости от количества городов, которые она посетит на маршруте. Если Беси использует некоторый маршрут несколько раз за время путешествия (то есть, она покидает маршрут,и позднее возвращается на него из другого города), она должна платить за каждый раз когда она использует маршрут.

Беси хочет определить самый дешёвый способ пропутешествовать от её фермы (города A) до выбранного «тёплого местечка» (города B). Пожалуйста, помогите ей определить минимальную цену, которую она должна заплатить и также минимальное количество разных полётов, которые она должна использовать, чтобы достичь этой минимальной цены.

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

Первая строка ввода содержит A, B, n (1 ≤ n ≤ 1000).

Следующие 2n строк описывают доступные маршруты, по две строки на маршрут. Первая строка содержит стоимость маршрута (целое число в диапазоне 1.. 109) и количество городов на маршруте (целое число в диапазоне 1..100).

Вторая строка содержит список городов в порядке следования по маршруту. Каждый город обозначается целым числом в диапазоне 1..1000.

Рекомендуется использовать 64-битные целые.

Пример

Выведите минимальную цену путешествия Беси из города A в город B, а также минимальное количество полётов, требующихся для достижения этой минимальной цены. Если решение не существует, выводите -1 -1.