Миша записывает 2 числа: n и m, а Маша должна разделить число n на m частей, не меняя порядок цифр, при этом Миша ещё требует, чтобы произведение полученных m чисел было максимально. Помогите Маше.

Одной из классических NP-полных задач является так называемая «Задача о рюкзаке». Формулируется она следующим образом. Дано n предметов, каждый из которых характеризуется весом w_i и полезностью p_i. Необходимо выбрать некоторый набор этих предметов так, чтобы суммарный вес этого набора не превышал W, а суммарная полезность была максимальна. Ваша задача состоит в том, чтобы написать программу, решающую задачу о рюкзаке.

Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 100 000) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1 ≤ m ≤ 10 000 000) запросов о наименьшем общем предке для пары вершин. Запросы генерируются следующим образом. Заданы числа a₁, a₂ и числа x, y и z. Числа a₃, ..., a_2m генерируются следующим образом: a_i = . Первый запрос имеет вид {a1, a2}. Если ответ на (i - 1)-й запрос равен v, то i-й запрос имеет вид {, a_2i}.

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

При интенсивном использовании домофона краска, нанесённая на цифровые клавиши, постепенно стирается. Одна из компаний, занимающихся установкой домофонов, заинтересовалась возможностью определить диапазон номеров квартир, расположенных в подъезде, по тому, насколько стёрлась краска с клавиш. Они уже обнаружили, что по состоянию клавиши можно определить, сколько раз эту клавишу нажимали. Теперь вам, программисту этой компании, поручили для начала решить простейший вариант задачи восстановления диапазона квартир по «затёртостям». А именно, вашей программе на вход даются 10 чисел — «затёртости» клавиш 0, 1, ..., 9,  т. е. количество раз, которое нажималась соответствующая клавиша. Считая, что за время использования домофона каждую квартиру набрали ровно один раз, и считая, что номера квартир в подъезде начинаются с 1 (т. е. в подъезде расположены квартиры с номерами 1, 2, ..., N при некотором N), определите диапазон квартир в этом подъезде (т. е., фактически, определите это N). Считайте, что посетители никогда не набирают ведущих нулей. Считайте, что N не может превосходить 10⁹.