Задача №1761. Катание на автобусах
В городе \(n\) автобусных остановок, через которые проходят \(k\) кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, \(i\)-ый маршрут проходит по остановкам \(a_{i, 1}\), \(a_{i, 2}\), …, \(a_{i, l_i}\) (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке \(a_{i,1}\). На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки \(a_{i, l_i}\) автобус оказывается на остановке \(a_{i, 1}\) и едет по маршруту еще раз.
Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План \(j\)-го человека состоит из остановки \(b_j\), на которой человек начнет свое катание и последовательности чисел \(c_{j, 1}\), \(c_{j, 2}\), …, \(c_{j, m_j}\). Эти числа означают следующее: в момент времени 0 человек придет на остановку \(b_j\) и дождется ближайшего автобуса (если в этот момент какой-то автобус находится на остановке \(b_j\), человек сядет в него). На этом автобусе он проедет \(c_{j, 1}\) остановок, после чего выйдет и дождется следующего автобуса на той остановке, где он окажется. На нем он проедет \(c_{j, 2}\) остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.
Для каждого человека определите, через сколько минут после начального момента и на какой остановке закончится его катание.
Во входном файле записано сначала число \(n\), затем число \(k\). Далее записано \(k\) строк, задающих автобусные маршруты. Каждая строка начинается с числа \(l_i\), задающего длину маршрута, затем идет список остановок, через которые проходит маршрут: \(a_i\),1, \(a_i\),2,… \(a_i\),\(l_i\). Маршрут может несколько раз проходить через одну и ту же остановку.
Далее идет число \(p\) – количество людей, и затем p строк, задающих планы людей. Каждая строка содержит сначала числа \(b_j\) – номер начальной остановки и \(m_j\) – количество чисел в последовательности. Затем идут числа \(c_j\),1, \(c_j\),2, …, \(c_j\),\(m_j\).
Все числа во входном файле натуральные и не превышают 50.
В выходной файл для каждого человека выведите два числа: время в минутах, когда закончится его катание, и номер остановки, на которой это произойдет. Если же человек не сможет реализовать свой план до конца (на какой-либо остановке он не дождется автобуса), выведите для него два нуля.
6 4 4 1 2 3 5 2 3 4 5 5 2 1 3 2 2 4 3 3 1 4 1 2 3 4 2 1 1 6 3 1 2 3
20 1 2 3 0 0