Рассмотрим две строки \(α\) и \(β\). Их конкатенацией называется строка, получающаяся в результате приписывания к строке \(α\) строки \(β\). Эта строка обозначается \(αβ\). Например, конкатенацией строк `ab' и `ac' будет строка `abac'. Очевидно, что это определение естественным образом распространяется на конкатенацию произвольного количества строк. Так, конкатенацией нуля строк будет пустая строка, а конкатенацией одной строки будет она сама.

Рассмотрим некоторое множество \(W\), состоящее из строк. Назовём его замыканием множество \(W\)*, состоящее из тех и только тех строк, которые можно получить в результате конкатенации нуля и более строк из множества \(W\). Таким образом, множество \(W\)* содержит пустую строку, и если строка α принадлежит множеству \(W\)*, а строка \(β\) принадлежит множеству \(W\), то строка \(αβ\) принадлежит множеству \(W\)*. Более того, все элементы множества \(W\)* можно представить в таком виде, то есть \(W\)* является пересечением всех множеств с указанными выше свойствами. Например, если \(W\)={a,ab}, то \(W\)* состоит из всех строк, в которых перед каждой буквой `b' идёт хотя бы одна буква `a'.

Задано некоторое множество строк \(W\). Требуется найти множество \(X\), такое, что \(W\)*=\(X\)* и множество \(X\) имеет минимальное возможное число элементов. В случае, если таких множеств несколько, подходит любое из них. Например, если \(W\)={a,aabb,ab,ac,b,bac}, то единственным множеством, удовлетворяющим условиям задачи будет множество {a,ac,b}.

Петя и его друг Андрейка только что познакомились с китайской мифологией. Особенно им понравились драконы. Поэтому мальчики решили сделать своих драконов из проволоки. Андрейка взял белую проволоку и согнул из неё дракона Лун-Инь: этот дракон спал, свернувшись клубком на столе. Тогда Петя взял чёрную проволоку и согнул дракона Лун-Ян. Этот дракон ничем не походил на Андрейкиного Лун-Иня. Его тело состояло из отрезков прямых, а когда он спал, то сворачивался в виде плоской замкнутой несамопересекающейся ломаной. Более того, Лун-Ян не ложился плашмя на стол для сна, а вставал перпендикулярно поверхности. Удержать равновесие дракон может только тогда, когда существуют две его различные точки, касающиеся стола, такие что центр масс дракона находится строго между ними.

Вам требуется узнать, сколько было устойчивых положений у дракона, в которых он мог сохранять равновесие во время сна, если известно, что форма ломаной в виде которой дракон спит всегда одна и та же.

В городе \(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}\) остановок, снова выйдет и снова дождется следующего автобуса. И так далее. Если в какой-то момент к остановке подъедет сразу несколько автобусов, то человек сядет в автобус с минимальным номером маршрута. Когда человек выходит из автобуса на какой-то остановке, он может уехать с этой остановки не раньше, чем через минуту.

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