Вам заданы две перестановки одинаковой длины $$$a_1, a_2, \dots, a_n$$$ и $$$b_1, b_2, \dots, b_n$$$. Перестановка — это последовательность целых чисел, состоящая из $$$n$$$ элементов, причем каждое число от $$$1$$$ до $$$n$$$ встречается в этой последовательности ровно один раз.
Циклическим сдвигом перестановки $$$p$$$ на $$$k$$$ элементов вправо называется такая перестановка $$$q$$$, что при $$$1 \le i \le k$$$ выполняется $$$q_i = p_{i + n - k}$$$, а при $$$k + 1 \le i \le n$$$ выполняется $$$q_i = p_{i - k}$$$. Например, циклическим сдвигом перестановки $$$\{1, 2, 3, 4, 5\}$$$ на $$$3$$$ элемента вправо является перестановка $$$\{3, 4, 5, 1, 2\}$$$.
Пусть функция $$$f(a, b)$$$ — это минимальное значение $$$a_i \cdot b_i$$$ среди всех $$$i$$$ от $$$1$$$ до $$$n$$$ (формально, $$$f(a, b) = \min \limits_{i = 1}^{n} a_i b_i$$$). Например, если $$$a = \{4, 2, 1, 3\}$$$, $$$b = \{2, 1, 3, 4\}$$$, то $$$f(a, b) = 2$$$, так как для $$$i = 2$$$ $$$a_i \cdot b_i = 2$$$.
Определите значение описанной функции для зафиксированной перестановки $$$a$$$ и для всех циклических сдвигов вправо перестановки $$$b$$$. Отметим, что циклических сдвигов вправо перестановки $$$b$$$, состоящей из $$$n$$$ элементов, всего $$$n$$$: сдвиг на $$$0$$$ элементов вправо, сдвиг на $$$1$$$ элемент вправо, сдвиг на $$$2$$$ элемента вправо, $$$\dots$$$, сдвиг на $$$(n - 1)$$$ элемент вправо.
В первой строке следует целое число $$$n$$$ $$$(2 \le n \le 10^6)$$$ — размер перестановок $$$a$$$ и $$$b$$$.
Во второй строке следует последовательность $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$ — описание перестановки $$$a$$$.
В третьей строке следует последовательность $$$b_1, b_2, \dots, b_n$$$ $$$(1 \le b_i \le n)$$$ — описание перестановки $$$b$$$.
Гарантируется, что последовательности $$$a$$$ и $$$b$$$ задают перестановки из $$$n$$$ элементов.
Выведите $$$n$$$ целых чисел через пробел: $$$i$$$-е число должно быть равно значению описанной функции для перестановки $$$a$$$ и сдвинутой вправо на $$$(i - 1)$$$ элемент перестановки $$$b$$$.
5
3 4 2 1 5
1 3 4 2 5
2
4
2
1
4
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1
2
3
4
4
3
2
Рассмотрим первый пример. Сдвиг на $$$0$$$ элементов вправо перестановки $$$b$$$ равен $$$\{1, 3, 4, 2, 5\}$$$, $$$f(a, b) = 2$$$. Сдвиг на $$$1$$$ элемент вправо перестановки $$$b$$$ равен $$$\{5, 1, 3, 4, 2\}$$$, $$$f(a, b) = 4$$$. Сдвиг на $$$2$$$ элемента вправо перестановки $$$b$$$ равен $$$\{2, 5, 1, 3, 4\}$$$, $$$f(a, b) = 2$$$. Сдвиг на $$$3$$$ элемента вправо перестановки $$$b$$$ равен $$$\{4, 2, 5, 1, 3\}$$$, $$$f(a, b) = 1$$$. Сдвиг на $$$4$$$ элемента вправо перестановки $$$b$$$ равен $$$\{3, 4, 2, 5, 1\}$$$, $$$f(a, b) = 4$$$.
