Хакер Кирилл с ностальгией перебирал свои школьные тетради по информатике, и заметил, что в некоторых примерах на сложение не указана используемая система счисления. Ему стало любопытно: а можно ли только по записи примера однозначно определить систему счисления, в которой производилось сложение?
Помогите Кириллу – напишите программу, которая по записанным слагаемым и сумме однозначно восстановит систему счисления, в которой производилось сложение, либо сообщит, что однозначное восстановление невозможно.
Исходите из предположения, что сложение выполнено корректно.
Первая строка содержит первое слагаемое, вторая – второе, а третья – сумму. Для записи чисел используются цифры от «$$$0$$$» до «$$$9$$$» и заглавные латинские буквы от «$$$A$$$» до «$$$Z$$$».
Слагаемые и сумма могут быть разной длины, но длина любого из чисел не превышает $$$256$$$ цифр.
Если однозначное восстановление системы счисления невозможно, то выведите $$$0$$$, в противном случае – выведите целое положительное основание системы счисления.
A 6 10
16
1 2 3
0
1 Y Z
0
Посещая Луну, Незнайка открыл для себя совершенно новую игру, похожую на земной гольф. В лунном гольфе, также как и в земной разновидности, нужно забивать мячи в лунки. Правда в качестве лунок выступают кратеры, а в качестве мячей – метеориты.
Метеориты бывают разной массы, и задача игрока – забить метеориты в кратеры так, чтобы суммарная масса забитых метеоритов была максимальной. При этом правила запрещают забивать в один кратер более одного метеорита.
По правилам лунного гольфа:
Силы Незнайки не бесконечны, и максимальное расстояние, на которое он может забить метеорит, зависит от массы $$$m$$$ этого метеорита и рассчитывается по формуле $$$ d = \sqrt{10^6 / m}$$$.
Помогите Незнайке выиграть – напишите программу, которая по координатам лунок и массе метеоритов определит оптимальную стратегию игры. Для простоты, будем считать, что Незнайка не умеет промахиваться и стратегия просто описывает, какой метеорит в какой кратер нужно забить.
В первой строке записано целое число $$$ n $$$ $$$( 1 \leq n \leq 10^4 )$$$ – количество метеоритов. Во второй строке содержится $$$ n $$$ целых чисел $$$ w_i $$$ $$$( 1 \leq w_i \leq 10^6 )$$$, разделенных пробелами – веса метеоритов.
В третьей строке содержится целое число $$$ k $$$ $$$( 1 \leq k \leq 10^5 )$$$ – количество кратеров на игровом поле. В преследующих $$$ k $$$ строках содержатся тройки целых чисел $$$ x_i , y_i, r_i $$$ $$$( -2\,000 \leq x_i, y_i \leq 2\,000 $$$, $$$ 1 \leq r_i \leq 10)$$$, разделенных пробелом – координаты центров кратеров и их радиусы.
Первая строка должна содержать целое число $$$ r $$$ $$$( 0 \leq r \leq min(n, k))$$$ – количество метеоритов, которые предполагается забить. Далее следуют $$$ r $$$ строк, в каждой из которых содержатся два целых числа числа $$$ s_i $$$ $$$(1 \leq s_i \leq n )$$$ и $$$ t_i $$$ $$$( 1 \leq t_i \leq k )$$$ – номер метеорита и номер кратера, куда его следует забить. Метеориты и кратеры нумеруются в порядке появления во входных данных. Нумерация начинается с единицы.
3 1 100 10000 3 0 10 1 0 100 1 0 1000 1
3 1 3 2 2 3 1
2 2 3 2 1000 0 1 0 1000 1
0
В стране Древляндии есть $$$N$$$ городов, каждый из которых имеет номер от $$$1$$$ до $$$N$$$. Также известно, что между некоторыми из городов имеются двунаправленные дороги, к тому же из каждого города можно добраться до любого другого единственным способом, возможно, проезжая через другие города. Помимо этого, за проезд по дороге нужно заплатить определенное количество денег. Коммивояжеру Алексею предстоит совершить $$$Q$$$ поездок между парами городов и для каждой он хочет узнать, сколько денег ему придётся потратить в каждой из поездок. Однако стоимость проезда рассчитывается по очень странной формуле: все стоимости проезда перемножаются, а затем полученный результат берётся по модулю $$$10^9 + 7$$$. Так как Алексей очень плохо умеет считать, он просит вас помочь ему. Ваша задача – написать программу, которая для каждой поездки Алексея посчитает её стоимость.
В первой строке содержится число $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – количество городов в Древляндии.
В следующих $$$N - 1$$$ строке содержится информация о дорогах. Каждая строка состоит из чисел $$$u, v, w~(1\le u, v \le N, 1 \le w \le 10^9, u \ne v)$$$ – номера городов, соединенных двунаправленной дорогой и цена проезда через дорогу.
В $$$(N+1)$$$-й строке содержится число $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^5)$$$ – количество поездок, которые совершает Алексей. В следующих $$$Q$$$ строках содержатся пары чисел $$$a$$$ и $$$b$$$ $$$(1 \le a, b \le N, a \ne b)$$$ – номера городов, между которыми нужно посчитать стоимость проезда.
Выведите $$$Q$$$ строк – стоимость проездами между городами по формуле, описанной в условии.
6 1 3 3 3 2 5 4 5 6 6 4 9 4 1 10 5 1 3 3 2 5 6 2 4 2 6
3 5 54 150 1350
Галерея современного искусства заказала художнику Малявичу очередной шедевр, с условным названием «Сложный квадрат». По условиям заказа, полотно должно:
Помогите Малявичу создать шедевр – напишите программу, которая по заданному $$$n$$$ выберет подходящее $$$k$$$ и построит карту расположения цветных квадратов, не нарушающую приведенные условия, либо сообщит, что решения не существует.
Единственное целое число $$$n$$$ $$$( 1 \leq n \leq 1000 )$$$.
В первой строке выведите выбранное число $$$k$$$ $$$(1 \leq k \leq n)$$$ – размер стороны картины.
В следующих $$$k$$$ строках выведите по $$$k$$$ символов. Строки должны состоять из латинских символов «Y», «O», «P» или «L», обозначающих окраску соответствующего «пикселя» картины. Разноцветные квадраты могут состоять как из одного, так и из нескольких смежных «пикселей».
Если решений несколько, выведите любое из них.
Если решения нет, выведите число «$$$-1$$$» (без кавычек).
1
1 Y
2
-1
3
-1
4
2 YO OP
Игорь, Ира и Вероника каждый день гуляют на улице, особенно им нравится гулять по аллее возле дома. Веронике особенно нравится гулять в коляске и смотреть на всё, что происходит вокруг. Игорю и Ире важно, чтобы Вероника гуляла как можно дольше на свежем воздухе, поэтому, гуляя с коляской, Игорь и Ира предпочитают ехать в теньке, которую делают кроны деревьев, так на Веронику меньше светит солнце.
Однажды Игорь задумался над серьезным вопросом, какова площадь тени деревьев. Игорь, Ира и Вероника живут в районе математиков, на аллее растет $$$n$$$ деревьев. Все деревья расположены на одной прямой, каждое $$$i$$$-е дерево задается координатой центра $$$x_i$$$, также каждое $$$i$$$-е дерево имеет идеальную тень в виде круга радиусом $$$r_i$$$. Достоверно известно, что расстояние между $$$i$$$-м и $$$j$$$-м деревом не меньше, чем радиусы $$$r_i$$$ и $$$r_j$$$.
Помогите Игорю определить площадь тени, которую оставляют все деревья.
В первой строке задано целое число $$$n$$$ $$$(1\leq n\leq 10^3)$$$ — количество деревьев.
Далее в каждой следующей строке заданы целые числа $$$x_i$$$, $$$r_i$$$ $$$(-10^3\leq x_i\leq 10^3, 1\leq r_i\leq 10^3)$$$ — координаты центра $$$i$$$-го дерева и радиус его тени.
Гарантируется, что все деревья имеют разные координаты.
Гарантируется, что для любого $$$i$$$, $$$j$$$ выполняется $$$|x_i-x_j|\geq max(r_i,r_j)$$$.
Выведите площадь затененного участка дорожки с точностью не менее $$$4$$$ знаков после запятой.
3 0 1 2 2 8 3
42.57923071
Существует достаточно много головоломок, в которых нужно отмерить определенный интервал времени с помощью неравномерно горящих бикфордовых (огнепроводных) шнуров. Например, с помощью шнура, который целиком сгорает за $$$1$$$ минуту, можно легко отмерить $$$30$$$ секунд – для этого нужно просто поджечь этот шнур с обеих сторон. С помощью двух таких шнуров (по $$$1$$$ минуте каждый) можно отмерить $$$45$$$ секунд – для этого нужно поджечь первый шнур с обеих сторон, а второй только с одной – в момент догорания первого шнура ($$$30$$$ секунд) нужно поджечь второй конец второго: он догорит целиком как раз через $$$45$$$ секунд.
Рассмотрим более общую задачу: пусть у нас есть $$$ n $$$ бикфордовых шнуров с длительностями горения $$$ d_1, d_2, \dots, d_n $$$. Можно ли с помощью них отмерить интервал времени $$$ Time $$$, если поджигать эти шнуры разрешается либо в начальный момент времени, либо в момент догорания какого-либо другого шнура?
Напишите программу, которая решит описанную задачу, или сообщит, что решения не существует. В случае существования нескольких решений, правильным считается любое.
Первая строка содержит единственное целое число – количество бикфордовых шнуров $$$ n $$$ $$$( 1 \leq n \leq 6 )$$$.
Во второй строке записаны $$$ n $$$ целых чисел $$$ d_1, d_2, \dots, d_n $$$ $$$( 1 \leq d_i \leq 120) $$$, разделенных пробелом – длительности горения этих шнуров в секундах.
В третьей строке записано целое число $$$Time$$$ $$$( 1 \leq Time \leq 600 )$$$ – интервал в секундах, который нужно измерить.
Первая строка содержит количество задействованных шнуров $$$ k $$$ $$$( 1 \leq k \leq n )$$$, либо $$$ -1 $$$, если решения не существует.
В случае существования решения, далее следуют $$$ k $$$ строк, каждая из которых содержит одно дробное и три целых числа, разделенных пробелом: $$$ t_{off}$$$ $$$ num $$$ $$$ t_1 $$$ $$$ t_2 $$$. Каждая такая четверка описывает момент догорания шнура $$$ t_{off} $$$ (с точностью до $$$ 10^{-10} $$$ сек); номер самого шнура $$$ num $$$, концы которого были зажжены в моменты времени c индексами $$$ t_1 $$$ и $$$ t_2 $$$. Строки должны быть упорядочены по возрастанию $$$ t_{off} $$$.
Шнуры нумеруются числами $$$ 1, 2, \dots, n $$$ в порядке их появления в исходных данных.
Моменты времени нумеруются числами $$$ 1, \dots, k $$$ в порядке их появления в выводе. Индексом $$$ 0 $$$ обозначается начальный момент времени, а индекс $$$ -1 $$$ используется вместо $$$ t_2 $$$, если второй конец шнура не поджигается.
Если решений несколько, выведите любое из них.
2 60 60 45
2 30 1 0 0 45 2 0 1
1 10 4
-1
Вероника очень чутко спит и на каждый звук реагирует. Ира очень тщательно следит, как спит Вероника. Она ведет дневник и записывает, как спала Вероника. За несколько месяцев, записей в дневнике стало очень много, целых $$$n$$$ штук. Каждая запись в дневнике выглядит следующим образом: $$$hh_1:mm_1:ss_1$$$ – время, в которое Вероника уснула, и $$$hh_2:mm_2:ss_2$$$ – время, в которое Вероника проснулась.
Однажды сосед сверху начал сверлить дрелью, делая ремонт, от этого звука Вероника проснулась и очень сильно испугалась, Вероника долго плакала. Игорю это очень сильно не понравилось, что ее дочку напугали новые звуки. Игорь пошел разбираться с соседом. Придя к нему, он объяснил ситуацию вежливо и показал дневник, сказав, что крайне нежелательно вести ремонт в промежутки сна Вероники, записанные в дневнике, иначе Игорь снова придет к соседу решать данный вопрос.
Помогите определить, сколько времени в секундах у соседа на ремонт каждый день.
В первой строке задано одно целое число $$$n$$$ $$$(1\leq n\leq 10^5)$$$ — количество промежутков сна в списке Игоря.
Далее в каждой строке задано время сна Вероники через пробел в виде $$$hh_1:mm_1:ss_1$$$, $$$hh_2:mm_2:ss_2$$$ $$$(0\leq hh_1,hh_2\leq 23,0\leq mm_1,mm_2\leq 59,0\leq ss_1,ss_2\leq 59)$$$ — время начала сна и время пробуждения после сна.
Гарантируется, что каждый промежуток времени сна Вероники меньше $$$24$$$ часов.
В единственной строке выведите число – количество секунд на ремонт у соседа.
5 13:00:00 14:00:00 16:00:00 17:00:00 19:00:00 20:00:00 01:00:00 05:00:00 04:00:00 05:00:00
61200
4 22:49:13 05:22:28 18:50:30 14:32:25 11:34:33 11:28:25 08:55:57 19:49:53
0
2 10:48:15 07:42:04 03:00:33 04:52:08
11171
Вероника научилась ползать, теперь за ней нужен глаз да глаз.
Игорь и Ира разрешают ей ползать на большом мате в комнате, сам мат представляет из себя большой прямоугольник размером $$$n$$$ на $$$m$$$. Изначально Вероника расположена где-то на мате и смотрит вниз, по направлению символа «V». Веронике запрещено покидать мат и ползать по полу.
Вероника может перемещаться на мате только в соседние клеточки и только в направлении, в которое она смотрит. Для того, чтобы переместиться на соседнюю клеточку, Веронике потребуется потратить $$$f$$$ секунд, также Вероника может повернуться по часовой стрелке на $$$90$$$ градусов за $$$r$$$ секунд и повернуться против часовой стрелки на $$$90$$$ градусов за $$$l$$$ секунд.
На мате разбросаны несколько игрушек «*», которые Веронике интересны, и ряд препятствий, которые непреодолимы и которые она не может убрать «$$$\#$$$», если клеточка пустая, то она обозначается «.». Вероника очень хочет доползти до какой-нибудь своей игрушки, считается, что Вероника доползла до игрушки, если она лежит в соседней клетке от игрушки и смотрит в направлении игрушки.
Игорь и Ира знают опытным путем, что если Вероника не успеет доползти до игрушки за $$$t$$$ секунд, тогда она расплачется и ее придется брать на ручки.
Помогите Игорю, Ире и Веронике определить сможет ли Вероника доползти до какой-нибудь игрушки или нет.
В первой строке задано шесть целых чисел $$$n$$$, $$$m$$$, $$$l$$$, $$$r$$$, $$$f$$$, $$$t$$$ $$$(1\leq n,m \leq 10^3, 1\leq l,r,f \leq 100,1\leq t\leq 10^6)$$$ — ширина и длина мата, количество секунд, чтобы Вероника повернулась на месте по часовой и против часовой стрелке на $$$90$$$ градусов, количество секунд, чтобы Вероника передвинулась на одну клеточку вперед, количество секунд, которое Вероника готова передвигаться.
Далее в $$$n$$$ строках задан мат, каждая строка имеет длину $$$m$$$. Все строки состоят из символов «.» — клетка пустая, «$$$\#$$$» — в клетке лежит непреодолимое препятствие, «*» — в клетке есть игрушка, «V» — символ расположения Вероники и показывающий ее изначальное направление.
Гарантируется, что Вероника расположена корректно на мате и символ «V» встречается ровно один раз.
Выведите «YES», если Вероника успеет добраться до какой-нибудь игрушки, в противном случае выведите «NO».
4 4 10 10 10 70 .... ..V. ###. .*..
YES
4 4 5 5 10 24 .... ..V. .... .*..
NO
Это интерактивная задача.
Профессор Р. вновь занимается исследованием массивов. Сегодня ему попался массив, состоящий из $$$N$$$ чисел. Отличительной особенностью этого массива является то, что он состоит только из чисел $$$0, 1, 2$$$. Профессор решил сыграть со своим внуком в следующую игру. Внук должен отсортировать массив по неубыванию, при этом он может задавать вопросы $$$2$$$ видов:
Однако задача оказалось не такой простой: внук может задать не более $$$2N$$$ вопросов. Так как внук умеет сортировать массивы только пузырьковой сортировкой, он просит вас помочь решить ему эту задачу, написав программу, которая упорядочит массив с помощью указанных операций не более чем за $$$2N$$$ запросов.
Сначала на вход вашей программе подаётся число $$$N$$$ $$$(1 \le N \le 2 \cdot 10^5)$$$ – количество элементов в массиве.
После этого ваша программа может делать запросы:
В любом запросе числа $$$i$$$ и $$$j$$$ должны лежать в пределах от $$$1$$$ до $$$N$$$.
Отсортировав массив, следует вывести строку «Sorted!» и завершить программу.
Если ваша программа сделает более $$$2N$$$ запросов или задаст некорректный запрос (например, запросите обмен элементов, номера которых не лежат в пределах от $$$1$$$ до $$$N$$$), она получит любой вердикт, отличный от «Accepted».
После каждого действия вашей программы выводите символ перевода строки. После вывода очередного запроса обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию «fflush(stdout)», на Java и Kotlin вызов «System.out.flush()» и «stdout.flush()» для языка Python.
2 1 0
get 1 get 2 swap 1 2 Sorted!
Хакер Кирилл насмотрелся роликов на youtube, и решил заняться рукоделием. Его выбор пал на настольную лампу – было решено снабдить ее кретивным украшением. В качестве украшения был выбран абажур из бусин. Отдельные бусины нанизываются на нити, а сами нити закрепляются параллельно друг другу в между двумя круглыми держателями.
Абажур состоит из $$$ n $$$ параллельных нитей. Все нити имеют одинаковую длину, и на них умещается ровно по $$$ k $$$ бусин. Бусины на нитях размещаются максимально плотно, а сами нити закреплены одинаково, поэтому первые бусины рядом с первыми бусинами соседних нитей, а $$$ k $$$-тые бусины – рядом с $$$ k $$$-ми.
У Кирилла имеются в наличии бусины двух цветов – черные и белые. Меняя их положение на нитях и порядок самих нитей, можно получить различные узоры. Кирилл решил спроектировать абажур таким образом, чтобы две соседние нити отличались друг от друга цветом ровно одной бусины, и не существовало двух одинаковых нитей.
Напишите программу, которая поможет Кириллу создать схему абажура из $$$ n $$$ нитей, по $$$ k $$$ бусин на каждой, либо сообщит что такой схемы не существует.
Примечание, так как абажур крепится к лампе только одним держателем, то у нитей есть начало, и нити, являющиеся отражением друг друга являются различными. Например, нити «BWBW» и «WBWB» – разные, хотя первую можно получить вторую задом наперед.
На вход подаются два целых числа $$$ n $$$ $$$( 2 \leq n \leq 10^4 )$$$ и $$$ k $$$ $$$( 2log_{2}n \leq k \leq 100 )$$$, разделенных пробелом.
В случае отсутствия решения программа должна вывести фразу «No solution» (без кавычек).
Если решение существует, то вывод состоит из $$$ n $$$ строк по $$$ k $$$ символов в каждой. Каждая строка описывает одну нить абажура, в порядке соседства. Первая нить считается соседней не только со второй, но и с последней.
Белые бусины обозначаются заглавной латинской «W», а черные – заглавной «B».
Если решений несколько, выведите любое из них.
6 6
BWWWWW BBWWWW WBWWWW WBBWWW BBBWWW BWBWWW
У Славы есть набор $$$N$$$ чисел: $$$x_1, x_2, x_3, \dots, x_n$$$. За один ход он может выбрать непустой набор $$$y_1, y_2, y_3, \dots, y_m$$$, такой, что для любого $$$i$$$ от $$$1$$$ до $$$m$$$ $$$y_i$$$ содержится в наборе $$$x_1, x_2, \dots, x_n$$$, и после этого добавить в набор $$$X$$$ сумму всех произведений чисел во всех подмножествах $$$y_1, y_2, \dots, y_m$$$. Славу интересует вопрос: сколько существует чисел, не превосходящих $$$L$$$, которые можно получить при помощи вышеописанной операции, за конечное число действий. (Для лучшего понимания условия, смотрите примечание)
В первой строке входных данных содержатся числа $$$N$$$ и $$$L$$$ $$$(2 \le N \le 20, 1 \le L \le 10^{12})$$$.
Во второй строке содержатся $$$N$$$ чисел $$$x_i$$$ $$$(2 \le x_i \le 15)$$$
В единственной строке выведите число – количество чисел, не превосходящих $$$L$$$, которые можно получить при помощи вышеописанной операции, за конечное число действий.
3 7 2 2 3
2
2 100 14 15
2
Рассмотрим набор чисел $$$X = [14, 15], L = 100$$$
Мы можем выбрать набор $$$Y$$$ так:
$$$[14], [15], [14, 14], [14, 15], [15, 15], [14, 14, 14], \dots$$$
Тогда получим числа:
$$$14 + 14 + 14 * 14 = 224$$$
$$$15 + 15 + 15 * 15 = 255$$$
$$$14 = 14$$$
$$$15 = 15$$$
$$$14 + 15 + 14 * 15 = 239$$$
$$$14 + 14 + 14 + 14 * 14 + 14 * 14 + 14 * 14 + 14 * 14 * 14 = 3374$$$
$$$\dots$$$
Но среди этих чисел, есть всего $$$2$$$, не превосходящие $$$100:~14,~15$$$.
Вероника любит играть в игры с кубиками, особенно ей нравится строить из них башенки. Вероника всегда очень усердно старается при постройке башенок, она аккуратно строит их в один ряд.
В этот раз она построила целых $$$n$$$ башенок, каждая из которых имела $$$a_i$$$ высоту кубиков. После долгой и кропотливой работы, Вероника позвала папу. Игорю как истинному ценителю искусства и настоящему математику, необходимо определить красоту всех построек сразу. Игорь считает, что красота всех построенных в ряд башенок равняется наибольшей возрастающей подпоследовательности из их высот.
НВП (Наибольшая возрастающая подпоследовательность) - это такая последовательность, в которой каждый следующий элемент больше предыдущего, то есть это такой набор индексов $$$i_1 \ldots i_k$$$, что: $$$i_1 \lt i_2 \lt \ldots \lt i_k$$$, $$$a[i_1] \lt a[i_2] \lt \ldots \lt a[i_k]$$$.
Вероника сделал очень много башенок, помогите определить Игорю красоту башенок Вероники.
В первой строке задано целое число $$$n$$$ $$$(1\leq n \leq 3 \cdot 10^5)$$$ — количество башенок, которые построила Вероника.
Далее в следующей строке содержатся $$$n$$$ целых чисел $$$a_i$$$ $$$(1\leq a_i\leq 10^9, 1\leq i\leq n)$$$, разделённых пробелами — высоты башенок.
В единственной строке выведите число – красоту последовательности башенок Вероники.
5 1 3 5 2 4
3
7 10 1 5 2 6 3 4
4
Игорь и Ира ждут пополнения в своей семье, совсем скоро они станут молодыми родителями. Самый главный вопрос на данный момент это то, как следует назвать малыша.
Игорь и Ира очень долго спорили, как можно назвать будущего ребенка, но так и не смогли договориться. Тогда они решили составить списки имён, которые им нравятся и не нравятся.
У Игоря получился список, в котором есть $$$n_1$$$ имён, которые ему нравятся, а также список из $$$m_1$$$ имён, которые Игорю не нравятся. Ира составила списки имён из $$$n_2$$$ имён, которые нравятся, и из $$$m_2$$$ имён, которые не нравятся. Будущему ребенку Игорь и Ира выберут имя, такое, что оно есть у обоих в списках имён, которые им нравится и не находится ни у кого в списках имён, которые не нравятся.
Помогите Игорю и Ире определить имена, которыми они могут назвать будущего ребенка. Выведите возможный список имен в лексикографическом порядке.
В первой строке задано $$$4$$$ целых числа $$$n_1$$$, $$$n_2$$$, $$$m_1$$$, $$$m_2$$$ $$$(1 \leq n_1,n_2 \leq 10^3, 0\leq m_1,m_2\leq 10^3)$$$ — количество имён, которые нравятся Игорю, количество имён, которые нравятся Ире, количество имён которые не нравятся Игорю, количество имён, которые не нравятся Ире.
Все имена состоят только из маленьких латинских букв длиною не более $$$20$$$ символов. Некоторые имена могут повторяться в одном и том же списке.
Выведите все имена, которые нравятся Игорю и Ире в алфавитном порядке, без повторений имен.
5 4 2 3 kirill ruslan sonya veronika vasya ruslan alina sonya veronika nastya masha sasha masha natasha
ruslan sonya veronika
Вероника научилась разговаривать. Для Игоря и Иры это большое счастье и целое событие. Сейчас Вероника знает всего лишь $$$n$$$ слов, каждое её слово Игорь и Ира записали в блокнот в виде строки, состоящей из маленьких латинских букв.
Игорь решил сохранить на память первый монолог Вероники. Для этого Игорь записал в блокнот звуки латинскими маленькими буквами, которые произносила Вероника. После записи Игорь решил проверить корректность полученной строки $$$s$$$, могла ли эта строка получиться из слов, которые знает Вероника. Помогите Игорю определить, правильно ли он записал в блокнот монолог Вероники.
В первой строке задано целое число $$$n$$$ $$$(1\leq n \leq 100)$$$ — количество слов, которое знает Вероника.
Далее следует $$$n$$$ строк, в которых записаны слова, которые знает Вероника.
Далее записана строка $$$s$$$ — монолог Вероники, который записал Игорь в блокнот. Все строки состоят только из маленьких латинских букв.
Гарантируется, что сумма длин слов, которые знает Вероника, не превосходит $$$10^5$$$.
Гарантируется, что длина строки $$$s$$$ не превосходит $$$10^5$$$.
Выведите «YES», если Вероника могла произнести строку $$$s$$$, если Вероника не могла произнести строку $$$s$$$ выведите «NO».
4 bububu mama papa matan bububumatanbububumama
YES