Телефон Стива продолжал звонить. Отвечать Стив не собирался: за последние несколько дней ему уже порядком надоело сообщать очередному агенту, что он не планирует продавать акции Gadget Operating System. Да, акции стремительно падают в цене, но Стиву они достались случайно и бесплатно, и он никогда не думал о них, как об инвестиции. Впрочем, наблюдая за сводками с биржи, он поймал себя на мысли, что мог бы немного заработать. Конечно, если бы обладал даром предвидения.
В параллельной вселенной, где Стив наделён даром предвидения, правила таковы.
Стив не намерен вкладывать дополнительные деньги в акции. Его начальный капитал — n акций, денег у него нет.
Агенты только скупают акции, но не продают их. На бирже Стив может только покупать акции.
В каждый момент времени Стив может либо продавать акции, либо покупать их, либо ничего с акциями / деньгами не делать.
Стив продаёт и покупает акции пакетом: либо он продаёт агенту все имеющиеся у него акции, либо покупает на бирже максимально возможное целое число акций на все имеющиеся у него деньги. После покупки у него может остаться какая-то сумма, строго меньшая цены одной акции в момент покупки. При следующей покупке эта сумма может быть использована.
Ваша задача — определить, какое максимальное количество денег мог бы заработать Стив.
В первой строке содержатся целые числа n и m (1 ≤ n ≤ 109, 1 ≤ m ≤ 5 × 105) — количество акций у Стива и количество моментов времени, в которые он мог совершать операции с акциями или деньгами.
Во второй строке содержится m целых чисел a1, a2, ..., am через пробел (1 ≤ aj ≤ 109) — цены за одну акцию, которые предлагали Стиву агенты.
В третьей строке содержится m целых чисел b1, b2, ..., bm через пробел(1 ≤ bj ≤ 109) — цены за одну акцию в эти же моменты на бирже.
Гарантируется, что входные данные таковы, что ни в какой момент времени Стив не может обладать более, чем 1018 акций, или суммой денег, превосходящей 1018.
В первой строке выведите целое число s — максимально возможную сумму, которую Стив мог бы заработать. Гарантируется, что она не превышает 1018.
Во второй строке выведите последовательность из m символов A, B, 0 (ноль), обозначающих соответственно продажу Стивом акций агенту, покупку акций на бирже и отсутствие каких-либо транзакций. Если существует несколько оптимальных последовательностей действий, выведите любую из них.
20 6
4 6 9 7 5 3
3 3 6 5 4 3
236
ABA000
10 5
1 2 3 4 5
5 4 3 2 1
75
00ABA
Падение курса акций не было неожиданностью для Стива. Некоторое время назад компания Quantum Artificial Intelligence заявила о желании выйти на рынок программного обеспечения для небольших устройств. Эта компания когда-то планировала развивать разработки, связанные с искусственным интеллектом, но не снискала успехов на этом поприще, закрепившись в итоге на рынке программного обеспечения для промышленных роботов. И теперь целью компании стало заполучить блокирующий пакет акций Gadget Operating System.
Менеджеры компании Quantum Artificial Intelligence определили, что блокирующим будет пакет из s акций. Они планируют обратиться с предложением о продаже акций к n акционерам Gadget Operating System.
Для каждого акционера #i известно количество акций ai, которым он владеет. Кроме того, акционер #i согласится продать свои акции только в том случае, если у покупателя будет к моменту покупки не менее bi акций.
Менеджеры компании Quantum Artificial Intelligence хотят как можно быстрее приобрести желаемое ими количество акций. Однако по ряду причин они могут заключать не более одной сделки в день. Ваша задача — определить, какое минимальное количество дней потребуется менеджерам, чтобы приобрести желаемое (или большее) количество акций.
В первой строке содержится целое число s (1 ≤ s ≤ 109) — количество акций, которое хотят приобрести менеджеры.
Во второй строке содержится целое число n (1 ≤ n ≤ 105) — количество акционеров, у которых менеджеры могут приобрести акции.
В каждой из следующих n строк содержится по два целых числа ai и bi (1 ≤ ai ≤ 109, 0 ≤ bi ≤ 109) через пробел.
В первой строке выведите число q — минимальное количество дней, спустя которое менеджеры могут стать обладателями желаемого ими количества акций. Если им это не удастся, выведите в качестве ответа - 1.
Во второй строке выведите q чисел — номера акционеров в том порядке, в котором менеджеры приобретали у них акции. Считайте, что акционеры занумерованы в порядке их упоминания во входных данных. Если существует несколько вариантов ответа — выведите любой.
28
8
5 2
7 25
4 0
6 1
2 20
3 3
8 7
4 15
6
3 4 1 6 7 8
5
1
5 1
-1
После получения блокирующего пакета акций менеджеры Quantum Artificial Intelligence начали активно действовать. Для начала они наложили вето на заключение всех достаточно крупных контрактов, а также запретили заключать более двух любых контрактов в день. При этом, если заключается два контракта, это должны быть контракты с разными компаниями.
Поскольку компания Gadget Operating System и n её заказчиков хотят продолжать совместную работу, было принято решение разделить каждый из n крупных контрактов на одинаковое количество небольших контрактов.
Считайте, что компании-заказчики занумерованы числами от 1 до n.
С момента наложения вето прошло m дней, и в каждый из этих дней Gadget Operating System заключала по два контракта с теми или иными компаниями-заказчиками.
Известно, что менеджеры Gadget Operating System разделили большие контракты на небольшие оптимальным образом, так что в дальнейшем они также смогут заключать по два контракта каждый день, в том числе в последний день, в который будут заключаться контракты.
Ваша задача — определить минимальное количество k небольших контрактов, на которые были разделены крупные контракты.
В первой строке содержатся целые числа n и m (2 ≤ n ≤ 2000, 1 ≤ m ≤ 2000) — количество крупных контрактов и количество дней, в которые уже заключались небольшие контракты.
В каждой из следующих m строк содержится по два целых числа c(1)i и c(2)i 
— номера компаний, с которыми были заключены контракты в день #i.
В первой строке выведите минимально возможное количество небольших контрактов k.
5 4
1 2
2 1
3 4
2 4
4
Обновления операционной системы, которую разрабатывает Gadget Operating System, являются бесплатными для пользователей устройств. Обновление — это пакет, который содержит некоторое количество новых функций.
Обладатели блокирующего пакета акций сочли, что распространять обновления бесплатно — неправильно. По их мнению, пользователь должен оплачивать каждую новую функцию в обновлении.
В обновлении содержится n новых функций.
Будем говорить, что функция #j непосредственно зависит от функции #k, если функция #j может быть активирована в системе сразу же после активации функции #k. Функция #k, в свою очередь, может непосредственно зависеть от какой-либо другой функции, например, функции #l. В этом случае про функцию #j можно сказать, что она косвенно зависит от функции #l.
Известно, что каждая функция непосредственно зависит не более чем от одной функции.
Менеджеры Quantum Artificial Intelligence предложили назначить за каждую новую функцию цену, на единицу большую количества функций, которые от нее зависят непосредственно или косвенно.
Ваша задача — определить, сколько, по мнению менеджеров Quantum Artificial Intelligence, должна стоить самая дорогая функция
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество функций в обновлении.
Во второй строке содержится n целых чисел ai (0 ≤ ai ≤ n), где ai — номер функции, от которой непосредственно зависит функция #i. Если ai = 0, то функция #i не зависит от других функций.
Гарантируется, что если функция #i зависит от функции #ai, то функция #ai ни прямо, ни косвенно не зависит от функции #i.
В первой строке выведите два целых числа — номер наиболее дорогой функции и её цену. Если существует несколько вариантов ответа, выведите любой.
15
6 0 0 15 13 2 15 14 13 3 12 0 12 2 11
12 8
Стив пытался найти логику в действиях менеджеров Quantum Artificial Intelligence. Впрочем, тайное уже становилось явным. Компания Quantum Artificial Intelligence хотела стать единственным партнёром Smart Industrial Robots. Однако Smart Industrial Robots настаивала на том, что в компании-партнёре должно работать достаточное количество квалифицированных сотрудников. Если считать и сотрудников Quantum Artificial Intelligence, и сотрудников Gadget Operating System, необходимая численность набирается. А вот квалификацию требуется подтверждать экзаменом.
Для каждого сотрудника известно количество дней di, в течение которых он может подготовиться к экзамену, чтобы сдать его блестяще на следующий день после завершения подготовки. Но если знания не применяются на практике, они постепенно утрачиваются. Если сотрудник будет сдавать экзамен не на следующий день, а через день по завершении подготовки, то сдаст его на балл ниже; через два дня — на два балла ниже и т.д. Квалификация считается подтверждённой, если сотрудник сдал экзамен не хуже, чем на m баллов ниже идеальной оценки.
Менеджеры Quantum Artificial Intelligence хотят, чтобы все сотрудники немедленно приступили к подготовке к экзамену.
По техническим причинам одновременно сдавать экзамен могут не более k человек. Организация экзамена — достаточно хлопотное дело, и менеджеры хотели бы обойтись как можно меньшим количеством экзаменов.
Ваша задача — определить, какое минимальное количество экзаменов потребуется назначить, чтобы все сотрудники подтвердили свою квалификацию.
В первой строке содержатся целые числа n, m, k (1 ≤ n, k ≤ 105, 0 ≤ m ≤ 109) — количество сотрудников, допустимое отклонение от полного балла, максимально возможное количество одновременно экзаменующихся соответственно.
Во второй строке содержится n целых чисел d1, d2, ..., dn, где di (1 ≤ di ≤ 109) — количество дней, которое требуется сотруднику #i, чтобы подготовиться к экзамену.
В первой строке выведите минимально возможное количество экзаменов, которое придётся назначить, чтобы все сотрудники подтвердили свою квалификацию.
4 3 3
5 8 13 21
3
10 5 3
1 6 4 15 4 10 8 2 12 5
4
Поскольку менеджерам Gadget Operating System не так уж понравилась идея переучивать своих сотрудников, они решили предложить менеджерам Quantum Artificial Intelligence для начала согласовать учебный план. Их доводы звучали убедительно: стандартный учебный план рассчитан на сотрудников с другой базовой подготовкой, а если составить его с учётом знаний и умений конкретных людей, то время обучения можно будет заметно сократить.
Нужно заметить, что менеджеры Quantum Artificial Intelligence очень трепетно относятся и к оформлению, и к формулировкам любого документа. Поэтому согласование обещает быть не слишком быстрым.
В процессе согласования учебного плана на нём должны поставить свои визы n менеджеров Quantum Artificial Intelligence. При этом менеджер #i может поставить свою визу только тогда, когда все менеджеры с #1 по #(i - 1) одобрили этот план. А может и не поставить, и отправить план на доработку. В этом случае все визы придётся собирать заново, начиная с менеджера #1.
Известно следующее: любой из менеджеров, полагающих, что учебный план должен быть идеально оформлен, отправит его на доработку, когда увидит его впервые. Когда ему принесут этот документ во второй раз, он поставит на нём визу. Но если документ попадёт к нему в руки в третий раз, он (на всякий случай) опять отправит его на доработку...
Таким образом, каждый чётный раз такие менеджеры будут подписывать документ, а каждый нечётный — отправлять его на доработку.
Впрочем, некоторые менеджеры не считают, что учебный план такой важный документ, что его стоит отправлять на доработку, и ставят визу всякий раз, когда им этот документ приносят.
Но каждый менеджер полагает, что документ должен «полежать», поэтому в течение дня можно получить вердикт только одного менеджера (визу или рекомендацию доработать план).
Ваша задача — по данным о менеджерах определить, через сколько дней учебный план будет подписан.
В первой строке содержатся целые числа n и m (1 ≤ n ≤ 30, 0 ≤ m ≤ n) — общее количество менеджеров, которые должны поставить визы, и количество менеджеров, которые считают нужным отправлять документ на доработку.
В следующей строке содержится m целых чисел k1, k2, ..., km (1 ≤ k1 < k2 < ... < km ≤ n) — номера менеджеров, которые считают нужным отправлять документ на доработку.
В первой строке выведите единственное целое число — количество дней, спустя которые документ будет подписан.
5 2
2 4
13
Менеджеры Gadget Operating System проинформировали своих заказчиков, что менеджеры Quantum Artificial Intelligence планируют задействовать большинство сотрудников в разработке программного обеспечения для Smart Industrial Robots. А это означает сворачивание разработки программного обеспечения для устройств, которые заказчики производят.
Заказчики отреагировали на сообщение по-разному. Некоторые уже разрабатывали новые линейки продуктов, и потому были готовы рассмотреть возможность перехода на новое программное обеспечение. Некоторые задумались о том, чтобы организовать собственный отдел по разработке программного обеспечения. А один из заказчиков предложил приобрести блокирующий пакет акций Smart Industrial Robots.
Конечно, покупка достаточно крупного пакета акций — дело непростое, и для начала было решено изучить, что же собой представляет компания Smart Industrial Robots. Для этих целей было приобретено n исследований, каждое из которых охватывает некоторый отрезок времени с момента bi по момент ei включительно. Конечно, эти отрезки времени могут пересекаться.
Потенциальные приобретатели акций планируют оценить интересующую их компанию в каждый момент времени, начиная с момента s и заканчивая моментом f. Они полагают, что делать какие-либо заключения по каждому моменту времени можно, опираясь на не менее чем k различных исследований. Если какой-либо момент времени рассматривается менее, чем в k исследованиях, потенциальные приобретатели акций готовы заказать дополнительные исследования.
Ваша задача — определить суммарное количество времени, для которого понадобится заказать дополнительные исследования.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество исследований.
Во второй строке содержатся целые числа s и f (1 ≤ s < f ≤ 109) — начало и конец отрезка времени, интересующего приобретателей акций.
В каждой из следующих n строк содержится по два целых числа bi и ei (1 ≤ bi < ei ≤ 109) — начало и конец рассматриваемого отрезка времени.
В следующей строке содержится целое число q (1 ≤ q ≤ 105) — количество запросов.
В следующей строке содержится q целых чисел k1, k2, ..., kq (1 ≤ kj ≤ n), где kj — количество исследований, для которого нужно получить ответ на вопрос задачи.
Выведите q чисел t1, t2, ..., tq, где tj — суммарное количество времени, для которого потребуются дополнительные исследования, если потенциальные приобретатели акций решат опираться на не менее чем kj различных исследований.
5
10 20
5 12
16 19
15 25
8 14
13 17
6
2 1 3 2 4 1
3 0 9 3 10 0
Сведений о компании Smart Industrial Robots удалось найти не так уж и много. Впрочем, по результатам исследований можно было сделать выводы, что компания то приобретала, то продавала активы. Стоимость каждого из этих активов на момент покупки / продажи удалось выяснить, так что теперь у потенциальных приобретателей акций компании Smart Industrial Robots есть эти данные.
Всего с активами было совершено n операций; таким образом, имеется последовательность из n положительных и отрицательных чисел a1, a2, ..., an, где |ai| — стоимость актива #i. Отрицательное число означает, что соответствующий актив приобретался (т.е. компания Smart Industrial Robots тратила деньги), положительное число — что соответствующий актив продавался.
Потенциальные приобретатели акций хотят узнать, каким мог быть минимально возможный начальный капитал Smart Industrial Robots, если ни для какой покупки эта компания не использовала заёмные средства. Обратите внимание, что начальный капитал не может быть отрицательным числом. Ваша задача — найти это минимально возможное значение.
В первой строке содержится целое число n (1 ≤ n ≤ 105) — количество совершённых операций.
Во второй строке содержится n целых чисел a1, a2, ..., an ( - 106 ≤ ai ≤ 106, i = 1, 2, ..., n), описывающих операции с активами.
В первой строке выведите целое число — минимально возможный начальный капитал компании.
3
20 -50 30
30
Тем временем Стив получил сообщение, в котором ему предлагали передать некую информацию. По мнению автора сообщения, эта информация обязательно заинтересует Стива. Незнакомец не просил ни денег, ни услуг взамен, а встретиться предложил в трамвае.
Незнакомец сообщил Стиву бортовой номер трамвая. Стив должен был сесть в последнюю дверь последнего вагона этого трамвая на остановке, которую мы условно назовём остановкой A, или на следующей после неё остановке, которую мы условно назовём остановкой B.
Павильон на остановке B совсем не защищал от пронизывающего ветра. Стив смотрел на экран: до прибытия трамвая с нужным бортовым номером было ещё порядочно времени. Немного поразмышляв, Стив сел в первый подошедший трамвай, который ехал по направлению к остановке A...
Опишем происходящее более формально.
В момент времени t = 0 Стив находится на остановке B. В его распоряжении имеется список трамваев, которые прибывают на остановку B и будут двигаться в сторону остановки A, а также список трамваев, которые прибывают на остановку B со стороны остановки A. Для каждого трамвая известно, через сколько времени он прибудет на остановку B (время отсчитывается от 0).
Расстояние между остановками B и A (оно же между A и B) трамвай проезжает за время d.
Находясь на остановке B, Стив оценивает время, за которое он может добраться до остановки A. Если, сев на первый идущий в сторону остановки A трамвай, он доберётся до остановки A строго раньше, чем трамвай с незнакомцем, Стив сядет на трамвай, проедет одну остановку и выйдет на остановке A.
Находясь на остановке A, Стив оценивает время, которое ему предстоит ожидать трамвай с незнакомцем. Если, сев на первый идущий в сторону остановки B трамвай, он доберётся до остановки B строго раньше, чем на остановку A прибудет трамвай с незнакомцем, Стив сядет на трамвай, проедет одну остановку и выйдет на остановке B.
Так будет продолжаться до тех пор, пока Стив не сядет в трамвай, в котором едет незнакомец.
Высадка и посадка занимают ненулевое время, поэтому если Стив приехал на остановку в момент времени t, то сесть на следующий трамвай он сможет не ранее, чем в момент времени t + 1.
Ваша задача — определить, на какой остановке Стив сядет в трамвай с незнакомцем, и на скольких трамваях к этому моменту он проедет.
В первой строке содержатся целые числа n, m, d (1 ≤ n, m ≤ 106, 1 ≤ d ≤ 106) — количество трамваев, едущих к остановке B со стороны остановки A, количество трамваев, едущих к остановке B с противоположной стороны, время проезда между остановками A и B.
Во второй строке содержится n целых чисел a1, a2, ..., an (0 ≤ a1 < a2 < ... < an ≤ 106) — моменты времени, в которые к остановке B подъезжают трамваи, едущие со стороны остановки A.
Незнакомец едет в последнем из этих трамваев.
В третьей строке содержится m целых чисел b1, b2, ..., bm (0 ≤ b1 < b2 < ... < bm ≤ 106) — моменты времени, в которые к остановке B подъезжают трамваи, едущие с противоположной стороны.
В первой строке выведите символ и целое число (через пробел) — символ A, если Стив сядет в трамвай с незнакомцем на остановке A, или символ B, если Стив сядет в трамвай с незнакомцем на остановке B, а также количество трамваев, на которых к этому моменту проедет Стив.
4 5 4
8 15 24 30
1 7 10 16 27
A 3
Стив вошёл в трамвай и встал у окна: так он видел практически всех пассажиров. Пока он размышлял, кто же из них пригласил его на эту необычную встречу, сидящая поблизости пожилая женщина попросила помочь ей вытащить из трамвая её сумку на колёсиках: «Не сейчас, ещё несколько остановок ехать».
Стив внимательно рассматривал всех, кто был в салоне трамвая. Вот пара девочек-школьниц, что-то оживлённо рассказывающих друг другу. Вот молодой человек, слушающий музыку и не особенно обращающий внимание на происходящее вокруг. Вот вполне серьёзный средних лет мужчина. Кстати, с небольшой папкой в руках. Может быть, он? Хотя вот тот студент с рюкзаком, который глаз не спускает со Стива, тоже вполне подходящий кандидат...
Стив ехал уже достаточно долго, но к нему никто не подходил. Тот, кто позвал его на встречу, очевидно, знал, как Стив выглядит, а вот Стив не знал о незнакомце ничего. Стива охватило сильное желание выйти на следующей же остановке, и он направился к дверям. Пожилая дама тоже засобиралась на выход, и Стив помог ей вынести сумку. Поблагодарив, дама протянула ему карту памяти и сказала, что видела, как он обронил её в трамвае. Она ушла, а Стив остался на остановке.
Отрезок пути, который Стив проехал на трамвае, можно разбить на n участков, каждый из которых ограничен двумя перекрёстками. Будем считать, что трамвай стартовал в момент времени t = 0 от перекрёстка #0. Участок от перекрёстка #(i - 1) до перекрёстка #i имеет длину ai.
На перекрёстке #i установлен двухсекционный светофор, на котором в течение ri секунд горит красный свет, а затем в течение gi секунд — зелёный свет. При этом известно, что di секунд назад на этом светофоре загорался зелёный свет. Время di отсчитывается от момента старта трамвая.
Трамвай движется скоростью 1 единица расстояния в секунду, и что временем, которое он стоит на остановках, можно пренебречь. Считайте, что если трамвай подъехал к перекрёстку в момент, когда только что включился красный свет, проехать на зелёный он не успевает.
Стив вышел на остановке, которая расположена сразу после последнего перекрёстка. Ваша задача — определить, сколько времени Стив ехал на трамвае.
В первой строке содержится целое число n (1 ≤ n ≤ 104) — количество перекрёстков, которые проехал Стив.
Во второй строке содержатся целые числа a1, a2, ..., an (1 ≤ ai ≤ 104, i = 1, 2, ..., n) — расстояния между перекрёстками.
В каждой из следующих n строк содержится по три целых числа ri, gi, di (1 ≤ ri, gi ≤ 1000, 1 ≤ di ≤ 10000), описывающие очередной светофор.
В первой строке выведите единственное целое число — время, которое Стив потратил на поездку.
3
100 110 50
80 20 50
60 10 100
30 40 50
370
Стив изучал содержимое карты памяти. Ему уже удалось выяснить, что Smart Industrial Robots продавала и покупала активы, связанные с производством дельта-роботов. Таких роботов и предполагалось производить на предприятии, которое Smart Industrial Robots планировала построить.
Впрочем, строительство предприятия в документах относилось к отдалённому будущему, когда для этого будет готова технологическая база. А вот план работ по развитию технологической базы был прописан более подробно.
Одной из наиболее важных характеристик дельта-роботов является их скорость, которая определяется характеристиками сервоприводов и рычагов. Упрощения ради эти характеристики мы также будем называть скоростями.
В настоящий момент Smart Industrial Robots располагает технологией производства сервоприводов, развивающих скорость до величины v, и технологией производства материала для рычагов, которые могут применяться до скоростей величины w.
Усовершенствованием этих технологий занимаются две научно-исследовательские группы.
Группе, которая работает над повышением скорости сервоприводов, нужно обеспечить финансирование в объёме f ежегодно. В этом случае каждые два года она сможет добиваться увеличения скорости сервоприводов на dv.
Группе, которая разрабатывает материалы для изготовления рычагов, нужно обеспечить финансирование в объёме g ежегодно. В этом случае каждые два года она сможет добиваться увеличения скорости, при которой могут применяться рычаги, на dw.
Если группе (любой) выделить финансирование в учетверённом объёме, разработчики смогут получить нужный результат за год.
Никакими иными способами выделять финансирование нельзя.
Smart Industrial Robots предполагает, что начнёт строительство предприятия, когда технологии позволят производить роботов, работающих на скорости не ниже u. Это значит, что скорость, которую могут развивать сервоприводы, должна быть как минимум u, и материал для рычагов должен позволять их использовать на скорости u.
Кроме того, Smart Industrial Robots полагает, что не будет прекращать финансирование обеих научных групп как минимум до начала строительства.
Ваша задача — определить, через какое минимальное количество лет может начаться строительство, а также какое минимальное количество денег при этом может быть затрачено.
В первой строке содержатся целые числа v, w, dv, dw, f, g, u 
.
В первой строке выведите два целых числа: минимальное количество лет, спустя которое начнётся строительство, и минимальное количество денег, которое при этом может быть потрачено.
1 3 2 1 3 10 18
15
672
3 1 1 2 1000 1 3
1
1004
У Стива появилось достаточно много вопросов. Пожалуй, он хотел бы, чтобы их задали менеджерам Quantum Artificial Intelligence.
Стив полагает, что составил вопросы таким образом, что на каждый из них можно ответить либо «Да», либо «Нет», либо «Без комментариев».
Стив хочет, чтобы вопросы были заданы в определённой последовательности. Кроме того, по его мнению, на некоторые вопросы он может получить ответ косвенно. Для таких вопросов он определил вопросы-предпосылки.
Пусть для вопроса #j предпосылками являются вопросы с номерами k1, k2, ..., kmj (все номера меньше j). Если к моменту, когда подойдёт очередь задавать вопрос #j, более чем на половину вопросов-предпосылок будет получен ответ «Да», Стив не станет задавать этот вопрос, а просто отметит, что ответом на него также было «Да». Аналогично, если более чем на половину вопросов-предпосылок будет получен ответ «Нет», Стив также не станет задавать этот вопрос и отметит, что ответом на этот вопрос было «Нет». В любом другом случае Стив задаст этот вопрос.
Когда Стив анализирует ответы на вопросы-предпосылки, для него не важно, как именно были получены ответы на эти вопросы — непосредственно от менеджеров или же в результате его собственных логических построений.
В параллельной вселенной даром предвидения наделён не только Стив, но и менеджеры Quantum Artificial Intelligence. Поэтому они уже знают, как ответят на каждый из вопросов.
Если Стив решил не задавать какой-либо вопрос и сформировал ответ на него самостоятельно, то даже если ответ Стива не совпадает с (возможным) ответом менеджеров, он учитывает именно «свой» ответ.
Ваша задача — определить, сколько вопросов задаст Стив и какие это будут вопросы.
В первой строке содержатся целые числа n и p (1 ≤ n ≤ 1000, 0 ≤ p ≤ n - 1) — общее количество вопросов и количество вопросов, имеющих вопросы-предпосылки.
Во второй строке содержится последовательность из n символов Y, N, C, означающих соответственно ответы «Да», «Нет», «Без комментариев».
Далее следуют p строк, каждая из которых описывает по одному вопросу с его предпосылками в следующем формате: номер j вопроса (1 ≤ j ≤ n), имеющего предпосылки, их количество mj (1 ≤ mj ≤ j - 1), и собственно номера самих вопросов-предпосылок k1, k2, ..., kmj (1 ≤ k1 < k2... < kmj < j, mj < j).
Гарантируется, что каждый номер вопроса встречается в описаниях не более одного раза.
В первой строке выведите единственное целое число — количество вопросов, которые задаст Стив.
Во второй строке выведите номера этих вопросов в порядке возрастания.
8 5
YNCNCYNY
2 1 1
7 2 1 6
4 3 1 2 3
5 2 2 4
8 2 3 5
4
1 3 6 8
Стив коснулся экрана, чтобы нажать кнопку «OK» под сообщением о том, что для операционной системы установлены последние обновления.
Компания Gadget Operating System обозначает версии операционной системы как v.m, где v — это основной номер версии, а m — номер обновления.
Когда выходит версия с новым основным номером, то её обозначение выглядит как v.0. Затем выпускается p обновлений для этой версии (обозначения v.1, v.2 и т.д.). После того, как будет выпущена версия, обозначаемая v.p, следующим обновлением станет версия с очередным основным номером (v + 1).
Стив помнит, что незадолго до истории с Quantum Artificial Intelligence он обновлял операционную систему до версии a.b. А после установки последних обновлений версия системы — z.y.
Ваша задача — определить, сколько за это время было выпущено обновлений.
В первой строке содержится целое число p (1 ≤ p ≤ 1000) — максимально возможный номер обновления.
Во второй строке содержатся два целых числа a и b (1 ≤ a ≤ 1000, 0 ≤ b ≤ p), составляющих обозначение старой версии операционной системы a.b.
В третьей строке содержатся два целых числа z и y (1 ≤ z ≤ 1000, 0 ≤ y ≤ p), составляющих обозначение новой версии операционной системы z.y.
Ради упрощения числа, составляющие обозначения версий, написаны через пробел, а не через точку. Гарантируется, что входные данные корректны.
В первой строке выведите количество обновлений, которое было выпущено до новой версии включительно.
12
2 5
2 8
3
8
3 4
4 5
10
14
2 11
4 1
20