Алгоритмы

Фермер Джон и его \(Q\) (\(1 \leq Q \leq 2 \cdot 10^5\)) коров на Манхеттене. Коровы сбежали и гуляют по городу. В Манхеттене \(N\) (\(1 \le N \le 2 \cdot 10^5\)) дорог проходящие бесконечно на \(x\)-\(y\)-плоскости. Все они расположены или горизонтально, или вертикально. Каждая горизонтальная или вертикальная может быть смоделирована уравнением вида \(y = c_i\) или \(x = c_i\), где \(c_i\) целое число в интервале от \(0\) до \(10^9\) включительно.

ФД знает точно где каждая корова начала путешествие и время путешествия. Каждая из коров движется по следующему шаблону:

• РћРЅР° двигается РЅР° север (\(+y\)) или восток (\(+x\)) РЅР° РѕРґРЅСѓ единицу РІ секунду.
• Если РѕРЅР° РЅР° одиночной РґРѕСЂРѕРіРµ, РѕРЅР° продолжает двигаться РїРѕ ней.
• Если РѕРЅР° РЅР° пересечении РґРІСѓС… РґРѕСЂРѕРі, РѕРЅР° идёт РЅР° север, РЅР° чётной секунде путешествия Рё РЅР° восток иначе.

ВАм дана карта Манхэттена и информация о каждой корове, помогите ФД где его коровы сейчас.

ПР�МЕР ВВОДА:

4 5
V 7
H 4
H 5
V 6
6 3 10
6 4 10
6 5 10
6 6 10
100 4 10

ПР�МЕР ВЫВОДА:

14 5
7 13
6 15
6 16
110 4

(6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (8, 5) -> ... -> (14, 5)
(6, 4) -> (6, 5) -> (7, 5) -> (7, 6) -> ... -> (7, 13)

Автор: Benjamin Qi

Беси прыгает вдоль числовой прямой длины \(N\) \((1 \leq N \leq 10^5)\) по позициям \(1,2,\dots,N\) слева направо. Она начинает в позиции \(S\) \((1 \leq S \leq N)\) прыжком вправо со стартовой энергией \(1\). Если энергия Беси равна \(k\), то её следующий прыжок будет на \(k\) единиц вперёд от её текущей позиции.

Каждая целочисленная позиция от \(1\) до \(N\) это или цель, или прыжковая площадка. Каждая цель или прыжковая площадка имеет целочисленную величину от \(0\) до \(N\) включительно. Прыжковая площадка со значением \(v\) увеличивает энергию Беси на \(v\) и изменяет на противоположное направление прыжков. Цель со значением \(v\) будет сломана, если на неё приземлится Беси с энергией не менее \(v\). Приземление на цель не изменяет энергию и направление Беси. Сломанная цель остаётся сломанной, но Беси может на неё прыгать, энергия и направление не меняются.

Если Беси будет прыгать бесконечное количество времени или до тех пор, пока Беси покинет этот отрезок прямой, сколько целей она сломает?

Если Беси начинает на цели, которую она может сломать, она немедленно делает это. Аналогично, если Беси начинает на прыжковой площадке, то эффект площадки применяется перед первым прыжком.

У Фермера Джона \(N\) (\(1\le N\le 2\cdot 10^5\)) участков травы на прямой, где участок \(i\) имеет уровень бактерий, который отличается на \(a_i\) от здоровой травы (\(-10^{15}\le a_i \le 10^{15}\)). Например, если \(a_i = -3\), тогда кусок \(i\) имеет уровень бактерий на 3 меньше, чем нормальный. И нужно прибавить ровно 3 дополнительных единицы бактерий, чтобы уровень бактерий в этом куске рассматривался как нормальный.

ФД хочет обеспечить, чтобы каждый кусок травы был скорректирован, чтобы получить нормальные уровни бактерий на них. У него есть два вида пестицидов, один добавляет бактерии, другой удаляет бактерии. ФД распространяет любой из двух видов пестицидов, стоя в куске \(N\) (самом правом куске) и выбирает уровень мощности \(L\) (\(1 \leq L \leq N\)).

Сила действия спрейера уменьшается по мере увеличения расстояния от него. Например, если фермер выберет пестицид, который добавляет бактерии, тогда \(L\) единиц бактерий в участок \(N\), \(L-1\) единиц бактерий в участок \(N-1\), \(L-2\) единицы бактерий в участок \(N-2\) и т.д. Участки \(1 \ldots N-L\) не получат бактерий, поскольку мощность спрейера недостаточна, чтобы их достать. Аналогично, если ФД выберет пестициды, которые удаляют бактерии, тогда \(L\) единиц бактерий будет удалено с участка \(N\), \(L-1\) единиц бактерий будет удалено с участка \(N-1\) и т.д. Опять, участки \(1 \ldots N-L\) будут не изменены.

Определите минимальное количество раз, которое ФД должен применить свой спрейер так, чтобы на каждом участке стало рекомендованное количество бактерийю Гарантируется, что ответ не превысит \(10^9\).

Может потребоваться использование 64-битного типа данных (например "long long" в C/C++)

Беси занялась химией. В данный момент у неё есть жидкости двух различных цветов \(1\) и \(2\), которые плохо смешиваются одна с другой. У неё также есть две различных колбы бесконечной емкости наполненные \(N\) \((1 \leq N \leq 10^5)\) единицами смесей жидкостей этих двух цветов. Смеси делятся на слои отдельных цветов. Поэтому колбы можно рассматривать как строки \(f_1f_2\ldots f_N\) и \(s_1s_2\ldots s_N\) где \(f_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна первой колбы, \(s_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна второй колбы,

Беси хочет разделить эти жидкости так, чтобы каждая колба содержала все единицы жидкости одного цвета. У Беси есть также пустой стакан бесконечной емкости, чтобы помочь ей решить её задачу. Когда Беси делает одно переливание, она переливает всю жидкость цвета \(i\) наверх из одной колбы в другую или в стакан.

Определите минимальное количество переливаний, чтобы разделить жидкости по колбам и серию переливаний, которые необходимо для этого выполнить. Не имеет значения какого цвета жидкость будет содержаться в какой колбе, но стакан должен быть пустым.

В каждом тесте будет \(T\) (\(1 \leq T \leq 10\)) подтестов с параметром \(P\) для каждого подтеста.

Предположим, что минимальное количество переливаний, чтобы разделить жидкости по колбам равно \(M\).

• если \(P=1\), Р’С‹ получите баллы, если выведите только \(M\).
• Если \(P=2\), Р’С‹ получите баллы, если выведите целое число \(A\) такое, что \(M \leq A \leq M+5\), Р·Р° которым следует \(A\) строк, которые конструируют это решение Р·Р° \(A\) С…РѕРґРѕРІ. Каждая строка должна содержать описание источника Рё приемника жидкости (\(1\), \(2\), или \(3\) для стакана). Колба-источник должна быть непустой перед переливанием, Рё нельзя переливать РІ себя.
• If \(P=3\), Р’С‹ получите баллы, если выведите \(M\), Р·Р° которым следует правильная конструкция, использующая это количество С…РѕРґРѕРІ.

ПР�МЕР ВВОДА:

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

ПР�МЕР ВЫВОДА:

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

Вот как это делается

1: 1221
2: 2211
3: 

1: 122
2: 22111
3: 

1: 1
2: 22111
3: 22

1: 1111
2: 22
3: 22

1: 1111
2: 2222
3:

В последнем подтесте пминимальное количество переливаний - \(5\). Однако, поскольку \(P=2\), то данная конструкция с \(6\)-ю ходами корректна, посокльку она не более чем на \(5\) переливаний от оптимального ответа.

Автор: Suhas Nagar

Беси и Эльза играют с шариками так: Беси и Эльза начинают игру с некоторым количеством шариков. Беси берёт \(A\) шариков из своих, а Эльза должна угадать является ли число \(A\) чётным или нечётным. Если Эльза угадает, она забирает эти \(A\) шариков, если нет - она отдаёт \(A\) своих шариков Беси. Если у Эльзы нет \(A\) шариков - она проиграла. Игрок проиграл, если остался без шариков.

После нескольких этапов игры, у Эльзы осталось \(N\) \((1 \leq N \leq 10^9)\) шариков. Она думает, что ей тяжело выиграть, она играет, чтобы не проиграть. Она хорошо изучила привычки Беси и заметила, что на \(i\)-ом ходу есть только \(K\) \((1 \leq K \leq 4)\) различных количеств шариков, которые может предложить Беси. Проходит всего только \(M\) \((1 \leq M \leq 3 \cdot 10^5)\) ходов прежде, чем Беси надоест, и она перестанет играть. Можете ли Вы определить лексикографически минимальную последовательность ходов такую, чтобы Эльза не проиграла вне зависимости от ходов Беси.

Беси готовит тесты для олимпиады. Каждую минуту она может выбрать не готовить никакие тесты для экономии энергии или потратить \(3^{a-1}\) энергии для подготовки \(a\) тестов для некоторого положительного целого \(a\).

У Фермера Джона есть \(D\) (\(1\le D\le 2\cdot 10^5\)) требований. Для \(i\)-го требования он говорит Беси, что в течение первых \(m_i\) минут она должна приготовить не менее чем \(b_i\) тестов (\(1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}\)).

Пусть \(e_i\) - минимальное количество энергии, которое необходимо Беси, чтобы удовлетворить первые \(i\) требований. Выведите \(e_1,\dots,e_D\) по модулю \(10^9+7\).

**Замечание: Память на тест 512MB, в два раза больше, чем по умолчанию.**

Беси планирует бесконечное путешествие в стране с \(N\) (\(1\leq N \leq 10^5\)) городами. В каждом городе есть портал и время зацикливания \(T_i\). Все \(T_i\). являются степенями двойки и \(T_1 + \cdots + T_N \leq 10^5\). Если Вы войдёте в портал города \(i\) в день \(t\), Вы немедленно выйдете из портала в городе \(c_{i, t\bmod{T_i}}\).

У Беси есть \(Q\) (\(1\leq Q \leq 5\cdot 10^4\)) планов её путешествия, каждый из которых есть тройка чисел \((v, t, \Delta)\). В каждом плане она начинает в городе \(v\) в день \(t\). Затем она делает следующее \(\Delta\) раз. Она входит в портал текущего города, затем ждёт один день. Для каждого из её планов она хочет узнать, в каком городе она закончит путешествие.

\(N\) \((1 \leq N \leq 5 \cdot 10^5)\) коров Фермера Джона выстроены в круг. \(i\)-ая корова имеет ведро с целой вместимостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально полные.

Каждую минуту корова \(i\) передаёт всё молоко из своего ведра корове \(i+1\) для \(1\le i<N\), а корова \(N\) передаёт своё молоко корове \(1\). Все обмены проходят одновременно (то есть, если корова отдаёт \(x\) литров молока и также получает \(x\) литров молока, её количество молока не изменяется). Если количество молока у коровы \(i\) превысит значение \(a_i\), тогда лишнее молоко теряется.

После каждой из минут \(1, 2, \dots, N\) - сколько молока останется у всех коров вместе?

\(N\) \((1 \leq N \leq 2 \cdot 10^5)\) коров Фермера Джона выстроены в круг так, что для каждой коровы \(i\) в промежутке \(1,2,\dots,N-1\), справа от коровы \(i\) расположена корова \(i+1\), а справа от коровы \(N\) находится корова \(1\). У каждой коровы имеется ведро целочисленной ёмкостью \(a_i\) \((1 \leq a_i \leq 10^9)\) литров. Все вёдра изначально заполнены молоком.

Каждую минуту коровы обменивается молоком по правилу, описанному в строке \(s_1s_2\dots s_N\) , состоящей только из символов \(\text{�L’}\) и \(\text{�R’}\). Если у коровы есть хотя бы \(1\) литр молока, она отдаст ровно \(1\) литр молока корове слева от неё, если \(s_i=\text{�L’}\), или справа от неё, если \(s_i=\text{�R’}\). Все обмены происходят одновременно (то есть, если у коровы полное ведро и она отдаёт литр молока и получает литр молока, то её молоко сохраняется). Если количество молока превысит \(a_i\), то лишнее молоко будет утеряно.

ФД хочет узнать после \(M\) минут \((1 \leq M \leq 10^9\)), какое количество молока останется у всех коров.?

ПР�МЕР ВВОДА:

3 1
RRL
1 1 1

ПР�МЕР ВЫВОДА:

2

ПР�МЕР ВВОДА:

5 20
LLLLL
3 3 2 3 3

ПР�МЕР ВЫВОДА:

14

ПР�МЕР ВВОДА:

9 5
RRRLRRLLR
5 8 4 9 3 4 9 5 4

ПР�МЕР ВЫВОДА:

38

Авторы: Chongtian Ma, Alex Liang

У Фермера Джона есть \(N\) (\(1 \leq N \leq 2 \cdot 10^5\)) ферм, пронумерованных от \(1\) до \(N\). Известно, что ФД закрывает ферму \(i\) в момент времени \(c_i\). Беси просыпается в момент времени \(S\) и хочет максимизировать производительность своего дня посетив как можно больше ферм, прежде чем они закроются. Она планирует посетить ферму \(i\) в момент времени \(t_i + S\). Беси должна прибыть на ферму строго раньше чем ФД закроет её, чтобы действительно посетить эту ферму.

У Беси есть \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\) запросов. Для каждого запроса она даёт Вам два целых числа \(S\) и \(V\). Для каждого запроса выведите сможет ли Беси посетить не менее \(V\) ферм, если она проснётся в момент времени \(S\).

Фермер Джон расширяет свою ферму! Он определил совершенное место - Красно-Чёрный Лес, который состоит из \(N\) деревьев (\(1 \le N \le 10^5\)) на числовой прямой, где \(i\)-ое дерево находится в позиции \(x_i\) (\(-10^9 \le x_i \le 10^9\)).

Закон по защите окружающей среды ограничивает, какие деревья может спилить ФД, освобождая место под свою ферму. Всего имеется \(K\) ограничений (\(1 \leq K \leq 10^5\)), указывающих, что должно быть как минимум \(t_i\) деревьев на отрезке \([l_i, r_i]\), включая конечные точки (\(-10^9 \le l_i, r_i \le 10^9\)). Гарантируется, что изначально Красно-Чёрный Лес удовлетворяет этим ограничениям.

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

ПР�МЕР ВВОДА:

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

ПР�МЕР ВЫВОДА:

4
4
3

Для первого подтеста, ФД может срезать первые 4 дерева, оставив деревья в точках \(x_i = 2, 6, 7\), чтобы удовлетворить ограничениям.

Для второго подтеста, ФД дополнительные ограничения не влияют, поэтому ФД может срезать те же самые деревья.

Для третьего подтеста, ФД может срезать не более \(3\) деревьев, потому что изначально \(7\) деревьев, однако второе ограничение требует чтобы он оставил как минимум \(4\) дерева не срезанными.

Авторы: Tina Wang, Jiahe Lu, Benjamin Qi

**Замечание: Время на тест в этой задаче 4 сек, в два раза больше, чем по умолчанию.**

Вам дано целое число \(N\) (\(2\le N\le 2000\)). Рассмотрим все перестановки \([p_0,p_1,\dots, p_{N-1}]\) из \([0,1,2\dots, N-1]\).

Пусть \(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) означает минимальную абсолютную разность между двумя последовательными элементами в \(p\). Также обозначим \(S_N\) множество всех таких перестановок \(p\), которые достигают максимальной возможной величины \(f(p)\).

Также Вам дополнительно дано \(K\) (\(0\le K\le N\)) ограничений вида \(p_i=j\) (\(0\le i,j<N\)). Посчитайте количество перестановок в \(S_N\), удовлетворяющих всем ограничениям, по модулю \(10^9+7\).

**Замечание: Время на тест для этой задачи 3 сек, в 1.5 больше чем по умолчанию.**

У Беси есть строка длины \(N\) (\(1\le N\le 3\cdot 10^5\)) состоящая только из символов M и O. Для каждой позиции \(i\) в этой строке есть цена замены (\(1\le c_i\le 10^8\)) этого символа на другой.

Беси думает, что строка будет выглядеть лучше, если она будет содержать больше moo длиной \(L\) (\(1\le L\le \min(N, 3)\)). Moo длиной \(L\) is символ M за которым следуют \(L-1\) символов O.

Для каждого положительного целого \(k\) от \(1\) до \(\lfloor N/L\rfloor\) включительно, вычислите минимальную стоимость изменить строк так, чтобы она содержала как минимум \(k\) подстрок равных moo длины \(L\).

У Беси есть \(N\) (\(1\le N\le 2\cdot 10^5\)) работ для Вас. Если Вы выберете \(i\)-ую работу, её необходимо начать в момент времени \(s_i\) или до него и для её завершения требуется \(t_i\) единиц времени. (\(0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}\)).

Какое максимальное количество работ Вы успеете выполнить? Время начинается с \(0\),и, если Вы начали работу, Вы сначала должны выполнить и только потом начинать другую работу.

\(N\) \((1 \leq N \leq 10^5)\) коров Фермера Джона выстроены в ряд. \(i\)-ая корова имеет метку \(a_i\) (\(1 \leq a_i \leq N\)). Группа коров может сформировать дружескую группу, если все они имеют одну и ту же метку и каждая корова находится в пределах \(x\) коров от остальных коров группы, где \(x\) - целое число из интервала \([1,N]\). Каждая корова должна быть точно в одной дружеской группе.

Для каждого \(x\) от \(1\) до \(N\), посчитайте минимальное количество дружеских групп, которые могу быть сформированы.

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

\(N\) коров фермера Джона (\(1\le N\le 1,5\cdot 10^5\)) имеют целую продуктивность \(a_1,\dots,a_N\). То есть \(i\)я корова производит \(a_i\) единиц молока за минуту ( \(0 \leq a_i \leq 10^8\)).

Каждое утро фермер Джон начинает с того, что все \(N\) коров подключены к его дойке. От него требуется отцеплять их по одной, отправляя прочь для их ежедневных упражнений. Первая корова, которую он отправляет, снимается с крючка после всего 1 минуты дойки, вторая корова, которую он отправляет, отцепляется после двух минут дойки и так далее. Поскольку первая корова (скажем, корова \(x\)) тратит только одну минуту на доильном аппарате она вносит только \(a_x\) единиц общего количества молока. Вторая корова (скажем, корова \(y\)) тратит на доение всего две минуты и, таким образом, дает \(2a_y\) единиц общего количества молока. Третья корова (скажем, корова \(z\)) приносит всего \(3a_z\) единиц и так далее. Пусть \(T\) представляет собой максимально возможное количество молока, которое может собрать фермер Джон, если он отцепляет своих коров в оптимальном порядке.

Фермеру Джону интересно, как повлияет на \(T\), если часть производительностей молока в его стаде были другими. Для каждого из запросов \(Q\) (\(1\le Q\le 1.5\cdot 10^5\)) каждое из которых задано двумя целыми числами \(i\) и \(j\), пожалуйста, рассчитайте, какой будет новое значение \(T\), если \(a_i\) было установлено в \(j\) (\(0 \leq j \leq 10^8\)). Обратите внимание, что каждый запрос рассматривает временное потенциальное изменение независимо от всех других запросов; то есть \(a_i\) возвращается к исходному значению перед следующим запросом.

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

В частности, операция слияния берет любые два различных узла в дереве с один и тем же родителем и объединяет их в один узел со значением, равным максимальному значений двух объединенных узлов, а потомки — объединение всех потомков объединенных узлов (если есть).

К сожалению, после того, как Бесси выполнила несколько операций слияния с деревом, ее программа дала сбой, потеряв историю выполненных ею операций слияния. Все, что Бесси помнит, что это дерево, с которого она начала, и дерево, которым она закончила после того как она выполнила все свои операции слияния.

Учитывая ее начальное и конечное деревья, определите последовательность операций слияния, которые могла бы выполнить Бесси. Гарантируется, что последовательность существует.

Каждый вход состоит из \(T\) (\(1\le T\le 100\)) независимых подтестов. Гарантируется, что сумма \(N\) по всем тестам не превышает \(1000\).

Парейдолия – это явление, при котором ваши глаза склонны видеть в изображениях знакомые узоры, которых на самом деле не существует — например, видение лица в облаке. Поскольку фермер Джон постоянно находится рядом с коровами, он часто видит коровьи узоры в повседневных предметах. Например, если он смотрит на строку "bqessiyexbesszieb", глаза фермера Джона игнорируют некоторые буквы и все, что он видит, это «bessiexbessieb» — строка, содержащая два последовательных подстроки, равные "bessie".

Дана строка длиной не более \(2\cdot 10^5\), состоящая только из символов a-z, где каждый символ имеет связанную стоимость удаления, вычислите максимальную количество непрерывных подстрок, равных "bessie", которые вы можете сформировать, удалив ноль или более символов из него, и минимальную общую стоимость символов, которую вам нужно удалить, чтобы сделать это.

**Примечание. Ограничение по времени для этой задачи – 4 секунды, что в 2 раза больше, чем по умолчанию.**

Чтобы отпраздновать начало весны, \(N\) коров фермера Джона (\(1 \leq N \leq 2 \cdot 10^5\)) придумали новый интригующий танец, в котором они встают в круг и перестраиваются предсказуемыv способом.

В частности, по кругу есть \(N\) позиций, пронумерованные последовательно от \(0\) до \(N-1\), причем позиция \(0\) следует за позицией \(N-1\). На каждой позиции находится корова. Коровы также последовательно нумеруются от \(0\) до \(N-1\). Изначально корова \(i\) находится в позиции \(i\). Вам сообщают набор из \(K\) позиций \(0=A_1<A_2< \ldots< A_K<N\), которые являются «активными», что означает, что коровы в этих позициях будут двигаться следующими (\(1 \leq K \leq N\)).

В каждую минуту танца происходят две вещи. Во-первых, коровы в активных позициях меняются: корова в позиции \(A_1\) перемещается в позицию \(A_2\), корова в позиции \(A_2\) перемещается в позицию \(A_3\) и так далее, с коровой в позиции \(A_K\) переход на позицию \(A_1\). Все эти \(K\) перемещения происходят одновременно, поэтому после завершения вращения все активные позиции по-прежнему содержат ровно одну корову. Далее смещаются сами активные позиции: \(A_1\) становится \(A_1+1\), \(A_2\) становится \(A_2+1\) и так далее (если \(A_i = N-1\) для некоторой активной позиции, то \(A_i\) возвращается к \(0\)).

Рассчитайте порядок коров после \(T\) минут танца (\(1\le T\le 10^9\)).

Фермер Джон заинтересован в лучшем общении со своими собратьями-коровами, поэтому он решил, что он выучит язык мычания!

Язык Moo на самом деле очень похож на английский, но более минималистичный. Там всего четыре типа слов: существительные, переходные глаголы, непереходные глаголы и союзы. Каждые два последовательных слова должны быть разделены пробелом. Там также всего два вида знаков препинания: точки и запятые. Когда точка или запятая ставится после слова, она ставится сразу после слова, а затем с последующим пробелом, если рядом появляется другое слово.

Предложение должно соответствовать одному из следующих форматов:

• Тип 1: существительное + непереходный глагол.
• Тип 2: существительное + переходный глагол + существительное(а). В частности, хотя бы одно существительное должен следовать за переходным глаголом, и перед каждым словом должна стоять запятая. следующее существительное, кроме первого следующего существительного.

Два предложения можно соединить в сложносочиненное, если поставить союз между ними. Полученное сложносочиненное предложение не может быть далее объединено с другими предложениями или другими сложными предложениями. Каждое предложение (или составное предложение, если два предложения соединены) должно заканчиваться точкой.

У фермера Джона есть банк слов из \(N\) слов, \(C\) запятых и \(P\) точек. (\(1 \leq P,C\le N \leq 10^3\)). Он может использовать слово или знак препинания столько раз раз, сколько это появляется в банке слова. Помогите ему вывести последовательность предложений, содержащую максимально возможное количество слов.

Каждый входной файл содержит \(T\) (\(1\le T\le 100\)) подтестов.