\href{http://codeforces.ru/blog/entry/4037}{http://codeforces.ru/blog/entry/4037} \includegraphics{https://static.e-olymp.com/content/5a/5a455f8d436fd6f1fa92bfb353bad4978d280e9f.jpg} \href{http://codeforces.ru/profile/I_love_ilona}{Alex_KPR}: --- \textit{...начиная где-то с декартовых деревьев, FFT и так далее, вбивание и отладка кода становятся напрягающими и довольно занудными задачами...} \includegraphics{https://static.e-olymp.com/content/3a/3aeed7f9109ca97777287b653c15bb4901ebd9be.jpg} \href{http://codeforces.ru/profile/PavelKunyavskiy}{Kunyavsky}: --- \textit{А можно я придерусь к мелочи. Что делают в одном ряду по времени написания декартово дерево и FFT?} \includegraphics{https://static.e-olymp.com/content/5a/5a455f8d436fd6f1fa92bfb353bad4978d280e9f.jpg} \href{http://codeforces.ru/profile/I_love_ilona}{Alex_KPR}: --- \textit{это первое, что пришло в голову, где нужно много писать и есть где накосячить} \includegraphics{https://static.e-olymp.com/content/3a/3aeed7f9109ca97777287b653c15bb4901ebd9be.jpg} \href{http://codeforces.ru/profile/PavelKunyavskiy}{Kunyavsky}: --- \textit{Я же сказал: придираюсь к мелочам. Просто на мой взгляд рядом поставлены вещи, одна из которых несравнимо легче по написанию} \includegraphics{https://static.e-olymp.com/content/28/284cc1a5c3b121d515e3f20770dc84616d7160b6.jpg} \href{http://codeforces.ru/profile/homo_sapiens}{homo_sapiens}: --- \textit{Полностью согласен Фурье пишется вдвое может даже втрое быстрее чем дерево (но его обычно пихать надо руками и ногами)} \includegraphics{https://static.e-olymp.com/content/3a/3aeed7f9109ca97777287b653c15bb4901ebd9be.jpg} \href{http://codeforces.ru/profile/PavelKunyavskiy}{Kunyavsky}: --- \textit{Я имел ввиду с точностью наоборот. Все таки очень специфичная тема}. \includegraphics{https://static.e-olymp.com/content/28/284cc1a5c3b121d515e3f20770dc84616d7160b6.jpg} \href{http://codeforces.ru/profile/homo_sapiens}{homo_sapiens}: --- \textit{Видимо и правда на вкус и цвет}... Пришло время узнать, что же проще. Вам предлагаются две последовательности из \textbf{N} целых чисел \{\textbf{x_i}\} и \{\textbf{y_i}\}. Если вам больше нравится FFT, представьте, что это коэффициенты двух многочленов: \includegraphics{https://static.e-olymp.com/content/ee/ee9676608e69e38f86f1dbce3b0209cff58de0cc.jpg} Найдите коэффициенты многочлена \textbf{P(z)·Q(z)}. Если же вам больше нравятся Декартовы деревья, представьте, что \{\textbf{x_i}\} --- ключи, а \{\textbf{y_i}\} --- приоритеты. Постройте Декартово дерево путем вставки в него последовательно всех \textbf{N} элементов (\textbf{x_i}, \textbf{y_i}). После каждой вставки выводите высоту получившегося дерева. Высота дерева --- количество ребер на длиннейшем пути от какой-либо вершины к корню. Для тех, кто выбрал FFT, напомним, что Декартово дерево --- это двоичное дерево поиска по ключам, содержащимся в вершинах (\textbf{x_i}). И одновременно куча по приоритетам в вершинах (\textbf{y_i}). То есть, для каждой вершины дерева выполняется свойство, что все вершины из левого поддерева имеют ключи меньшие, чем в данной вершине, а все вершины из правого поддерева --- большие. А также приоритет данной вершины больше приоритета ее сыновей. Независимо от того, что же вы выбрали, автор убедительно просит не использовать в этой задаче \textit{prewritten code}. \InputFile В первой строке число \textbf{N}. Во второй строке \textbf{N} различных целых чисел --- \{\textbf{x_i}\}. В третьей строке \textbf{N} различных целых чисел --- последовательность \{\textbf{y_i}\}. \OutputFile Если вы выбрали FFT, то выведите \textbf{2N-1} целых чисел --- коэффициенты результирующего многочлена. Если Декартово дерево, то \textbf{N} целых чисел --- высоты дерева после вставки в него каждой вершины. Вообще, вы можете вывести и то, и то, но тогда оба результата будут проверяться на корректность. \textbf{Ограничения} \textbf{1} ≤ \textbf{N} ≤ \textbf{50000} \textbf{1} ≤ \textbf{x_i} ≤ \textbf{50000} \textbf{1} ≤ \textbf{y_i} ≤ \textbf{50000} Гарантируется, что высота дерева не превысит \textbf{50}.