시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 3 | 0 | 0 | 0.000% |
В городе $n$ автобусных остановок, через которые проходят $k$ кольцевых автобусных маршрутов. Каждый маршрут задается списком номеров остановок, через которые он проходит, $i$-ый маршрут проходит по остановкам $a_{i,1}, a_{i,2},\ldots, a_{i,l_i}$ (в этом порядке). По маршруту ходит ровно один автобус. В момент времени 0 этот автобус находится на остановке $a_{i,1}$. На то, чтобы доехать до следующей на своем маршруте остановки, автобус тратит ровно одну минуту. Временем стоянки автобуса на остановке можно пренебречь. Все маршруты кольцевые, то есть через минуту после остановки $a_{i,l_i}$ автобус оказывается на остановке $a_{i,1}$ и едет по маршруту еще раз.
Несколько человек в этом городе решили покататься на автобусах. При этом каждый из них составил план своего катания. План $j$-го человека состоит из остановки $b_j$, на которой человек начнет свое катание и последовательности чисел $c_{j,1}, c_{j,2}, \ldots, 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},\ldots a_{i,l_i}$. Маршрут может несколько раз проходить через одну и ту же остановку.
Далее идет число $p$ --- количество людей, и затем $p$ строк, задающих планы людей. Каждая строка содержит сначала числа $b_j$ --- номер начальной остановки и $m_j$ --- количество чисел в последовательности. Затем идут числа $c_{j,1}, c_{j,2}, \ldots, 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