Родители подарили Пете набор детских кубиков. Поскольку Петя скоро пойдет в школу, они купили ему кубики с буквами. На каждой из шести граней каждого кубика написана буква.
Теперь Петя хочет похвастаться перед старшей сестрой, что научился читать. Для этого он хочет сложить из кубиков ее имя. Но это оказалось довольно сложно сделать - ведь разные буквы могут находиться на одном и том же кубике и тогда Петя не сможет использовать обе буквы в слове. Правда одна и та же буква может встречаться на разных кубиках. Помогите Пете!
Дан набор кубиков и имя сестры. Выясните, можно ли выложить ее имя с помощью этих кубиков и если да, то в каком порядке следует выложить кубики.
В первой строке вводится число \(N\) (1 <= \(N\) <= 100) - количество кубиков в наборе у Пети. Во второй строке задано имя Петиной сестры - слово, состоящие только из больших латинских букв, не длиннее 100 символов. Следующие N строк содержат по 6 букв (только большие латинские буквы), которые написаны на соответствующем кубике.
В первой строке выведите "YES" если выложить имя Петиной сестры данными кубиками можно, "NO" в противном случае.
В случае положительного ответа, во второй строке выведите \(M\) различных чисел из диапазона 1…\(N\), где \(M\) - количество букв в имени Петиной сестры. \(i\)-е число должно быть номером кубика, который следует положить на \(i\)-е место при составлении имени Петиной сестры. Кубики нумеруются с 1, в том порядке, в котором они заданы во входных данных. Если решений несколько, выведите любое. Разделяйте числа пробелами.
2 AB AAAAAB AAAAAA
YES 2 1
3 ANNY AAAAAA NNNNNN YYYYYY
NO
На сырном заводе во Флатландии живут мыши. Они очень любят сыр и часто уничтожают запасы сыра, приготовленные для отправки в магазин.
Всего на заводе живет \(m\) мышей. Для \(i\)-й мыши известна ее скорость поедания сыра \(s_i\), мышь может съесть \(s_i\) грамм сыра в час.
Недавно мышам стал известен план работы завода на ближайшее время. Планируется изготовить \(n\) головок сыра. Про каждую головку известны \(r_i\) к началу какого часа она будет изготовлена, \(d_i\) в начале какого часа она начнет портиться, и \(p_i\) вес головки сыра в граммах.
Мыши решили съесть весь сыр. В любой момент времени каждая мышь может есть некоторую головку сыра. Мыши существа брезгливые, и одну и ту же головку сыра не могут есть одновременно несколько мышей. При этом в любой момент времени мышь может решить прекратить есть головку сыра и приняться за другую, в том числе ту, которую ранее ела другая мышь.
Мыши не любят есть сыр после того как он начал портиться. Но оставлять сыр недоеденным мыши не могут. Они решили организовать поедание сыра таким образом, чтобы величина \(t\), такая что какую-либо головку все еще продолжают есть через \(t\) часов после того как она начала портиться, была минимальна. Помогите мышам выяснить, как это сделать.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 30\), \(1 \le m \le 30\)). Следующие \(n\) строк содержит по три целых числа: \(p_i\), \(r_i\) и \(d_i\) (\(1 \le p_i \le 10^5\), \(0 \le r_i \lt d_i \le 10^7\)). Далее следуют \(m\) строк, каждая из которых содержит по одному целому числу \(s_j\) (\(1 \le s_j \le 10^5\)).
Выведите одно вещественное число — искомое минимальное \(t\). Ваш ответ должен отличаться от правильного не больше чем на \(10^{-4}\).
Комментарий к примеру тестов
В первом примере мышам следует организовать поедание сыра следующим образом. Сначала первая мышь начинает есть первую головку сыра. Когда появляется вторая головка, она перестает есть первую и начинает есть вторую (в этот момент от первой осталось 9 граммов). Вторая мышь принимается есть первую головку сыра. Через 2.5 часа первая мышь доедает вторую головку сыра (на 0.5 часа позже чем она начала портиться) и снова начинает есть первую (вторая мышь за это время съела еще 5 граммов от первой головки и от нее осталось 4 грамма). Таким образом еще за час первая мышь доедает первую головку, также на 0.5 часа позже чем она начала портиться.
Во втором примере мышь успевает съесть сыр до того как он начинает портиться
2 2 13 0 4 10 1 3 4 2
0.5
1 1 1 0 1 1
0.0