Кот Miston поставил на скачивание сериал «Котокоп» («Police Cat»). В сериале $$$n$$$ серий, $$$i$$$-я из которых сейчас скачивается со скоростью $$$v_i$$$, и браузер показывает, что $$$i$$$-я серия скачается ровно через $$$t_i$$$ минут, что не совсем верно.

Браузер рассчитывает время, исходя из предположения, что скорость скачивания $$$i$$$-й серии не изменится. Однако когда какая-то серия оказывается полностью скачанной, скорость скачивания других серий увеличивается (других причин для изменения скорости скачивания той или иной серии и правда нет). При этом соотношения скоростей скачивания еще не скачанных серий неизменны. Иными словами, если $$$v_i^t$$$ — скорость скачивания $$$i$$$-й серии в момент времени $$$t$$$, то для любых $$$i$$$ и $$$j$$$ верно, что при всех $$$t$$$, меньших момента окончания скачивания $$$i$$$-й или $$$j$$$-й серии, величина $$$\frac{v_i^t}{v_j^t}$$$ одинакова.

Никакой другой нагрузки на сеть, кроме скачивания $$$n$$$ серий, нет. То есть суммарная скорость скачивания $$$\sum\limits_{i=1}^n v_i^t$$$ постоянна (одинакова при любом $$$t$$$).

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

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

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

Игра рассчитана ровно на $$$n$$$ игроков, и на фазе распределения ресурсов между игроками по кругу распределяются $$$n$$$ карточек с целыми числами, упорядоченными по неубыванию. Пусть $$$i$$$-му игроку досталось число $$$a_i$$$ (тогда $$$a_i \le a_{i+1}$$$ для всех $$$i \le n - 1$$$). Назовем опциями $$$i$$$-го игрока тройку чисел $$$\{a_{i-1}, a_i, a_{i+1}\}$$$, то есть число, написанное на его карточке, и два числа его соседей. Игроки сидят по кругу, то есть для первого игрока вместо $$$a_{i-1}$$$ будет опция $$$a_n$$$, а для $$$n$$$-го игрока вместо $$$a_{i+1}$$$ будет опция $$$a_1$$$.

Каждый игрок должен выбрать ровно одну из доступных ему опций и получить ровно столько ресурсов из банка. После чего от двух оставшихся опций считается побитовое «И» (операция '&'), и такое количество очков добавляется к результату игроков в этом раунде. Например, если у игрока есть опции $$$\{2, 5, 11\}$$$ и игрок выбирает взять $$$5$$$ ресурсов, он получает $$$2\ \&\ 11 = 0010_2\ \&\ 1011_2 = 2$$$ очка. Для успешного перехода к следующей фазе игры

1. суммарное количество взятых игроками ресурсов не должно превосходить $$$\left(\sum\limits_{i=1}^n a_i\right) + X$$$, то есть должно не больше чем на $$$X$$$ превышать количество ресурсов в случае, когда каждый игрок выбирает свое $$$a_i$$$;
2. суммарное количество набранных очков должно быть максимально возможным.

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

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

Компании VK понадобилось срочно переместить сервера из одного дата-центра в другой. Это очень важная и срочная задача, потому что во время их перемещения не все сервисы будут полноценно функционировать, однако на дорогах сегодня почему-то пробки, поэтому сервера будут перемещаться на вертолете.

Карта области, над которой может перемещаться вертолет, представляет из себя поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов. Нумерация строк идет от $$$1$$$ до $$$n$$$ сверху-вниз, нумерация столбцов от $$$1$$$ до $$$m$$$ слева-направо. Каждая клетка представляет из себя участок одинаковой высоты. Будем характеризовать клетку в строке $$$i$$$ и столбце $$$j$$$ как $$$(i, j)$$$, а минимальную высоту, на которой может безопасно находиться вертолет на соответствующем участке, как $$$a_{i, j}$$$.

Сервера надо переместить из клетки $$$(1, 1)$$$ в клетку $$$(n, m)$$$. Будем считать, что вертолет уже поднялся в воздух, и находится на высоте $$$a_{1, 1}$$$. При попадании вертолета в клетку $$$(n, m)$$$ на любой разрешенной высоте маршрут считается завершенным.

В любой момент времени высота, на которой находится вертолет, должна быть не меньше минимальной высоты полета для текущей клетки, то есть если обозначить за $$$h$$$ высоту, на которой сейчас находится вертолет в клетке $$$(i, j)$$$, должно выполняться $$$a_{i, j} \le h$$$. При этом из позиции $$$(i, j)$$$ на высоте $$$h$$$ можно:

• Перелететь в соседнюю по стороне клетку, потратив на такой перелет $$$h$$$ топлива. При этом высота не изменится, а такое перемещение можно сделать только если $$$a$$$ клетки, в которую совершается перелет, не больше $$$h$$$.
• Увеличить свою высоту на произвольное $$$x \ge 0$$$. На такой подъем тратится $$$x$$$ топлива.
• Опуститься на любую высоту не меньше $$$a_{i,j}$$$. На это топливо не тратится.

Из-за погодных условий вертолет не всегда может лететь во все стороны. Доступные направления задаются строкой $$$\mathtt{s}$$$. Каждое возможное направление полета задается следующими буквами:

• 'R' — разрешено движение вправо из клетки $$$(i, j)$$$ в клетку $$$(i, j + 1)$$$.
• 'L' — разрешено движение влево из клетки $$$(i, j)$$$ в клетку $$$(i, j - 1)$$$.
• 'U' — разрешено движение вверх из клетки $$$(i, j)$$$ в клетку $$$(i - 1, j)$$$.
• 'D' — разрешено движение вниз из клетки $$$(i, j)$$$ в клетку $$$(i + 1, j)$$$.

Увеличивать и уменьшать высоту можно всегда. Направления перемещения 'R' и 'D' всегда разрешены. Перемещаться за границу поля, разумеется, нельзя.

Программисты из VK быстро справились определить оптимальный по затратам топлива маршрут для вертолета, даже при таком большом количестве условий на его перемещения. А справитесь ли вы?

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены. Далее за $$$A$$$ обозначено $$$\max\limits_{i,j} a_{i,j}$$$.

В дата-центре Университета Иннополис есть $$$n$$$ серверов, занумерованных последовательными целыми числами от $$$1$$$ до $$$n$$$. Сервера соединены $$$n - 1$$$ оптоволоконными кабелями таким образом, что между любыми двумя серверами возможна передача данных по одному или нескольким кабелям, иными словами, связи между серверами образуют дерево.

Каждый оптоволоконный кабель передает данные с задержкой в $$$1$$$ единицу времени, а задержка между двумя серверами равна расстоянию в дереве между этими серверами.

Требуется выбрать несколько серверов для системы распределенного хранения данных таким образом, чтобы задержка между любыми двумя серверами, входящими в систему, не превышала $$$d$$$. Пусть выбраны сервера $$$s_1, s_2, \ldots, s_k$$$, тогда общая задержка системы равна сумме задержек между всеми $$$\frac{k (k - 1)}{2}$$$ парами серверов $$$s_i$$$. Формально:

1. должно выполняться $$$\mathtt{dist}(s_i, s_j) \le d$$$ для любых $$$i$$$ и $$$j$$$ (где $$$\mathtt{dist}$$$ — расстояние в дереве);
2. и тогда общая задержка системы равна $$$\sum\limits_{i \lt j} \mathtt{dist}(s_i, s_j)$$$.

Ваша задача — ответить на $$$q$$$ запросов. Каждый запрос задается номером одного сервера $$$u$$$ и состоит в следующем: в случае, если конкретный сервер $$$u$$$ будет включен в систему хранения данных, какова будет максимальная возможная общая задержка системы?

Баллы за каждую подзадачу с 1 по 4 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Каждый тест в подзадачах 5 и 6 оценивается независимо и стоит 3 балла в подзадаче 5 или 2 балла в подзадаче 6.