Ділянки
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Вимірювання земельної ділянки $$$-$$$ важлива геодезична процедура. Щоб отримати точні числові показники, процедуру вимірювання повинні виконувати професійні геодезисти.

Розглянемо таку задачу. Нехай є квадратна ділянка, яку геодезисти розділили на $$$n^2$$$ прямокутних ділянок, провівши $$$(n-1)$$$ вертикальних ліній та $$$(n-1)$$$ горизонтальних ліній. Пронумеруємо стовпчики та рядки діляночок так, як вказано на малюнку (масштабу не дотримано). Тобто рядки нумеруються знизу вгору цілими числами від $$$1$$$ до $$$n$$$; а стовпчики нумеруються зліва направо цілими числами від $$$1$$$ до $$$n$$$.

Ділянки, які знаходяться на перетині $$$i$$$-го стовпчика та $$$i$$$-го рядка $$$(1 \le i \le n)$$$, будемо називати «головною діагоналлю». Ділянки, які знаходяться на перетині $$$(i+1)$$$-го стовпчика та $$$i$$$-го рядка $$$(1 \le i \le n-1)$$$, будемо називати «побічною діагоналлю».

Вам відомі площі ділянок на головній та побічній діагоналях. Обчисліть площу ділянки, що знаходиться на перетині $$$p$$$-го стовпчика та $$$q$$$-го рядка.

Вхідні дані

Перший рядок містить одне ціле число $$$n$$$ ($$$2 \le n \le 1\,000$$$).

Другий рядок містить $$$n$$$ цілих чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — площі ділянок на головній діагоналі.

Третій рядок містить $$$n-1$$$ цілих чисел $$$b_1, b_2, \dots, b_{n-1}$$$ ($$$1 \leq b_i \leq 10^9$$$) — площі ділянок на побічній діагоналі.

Четвертий рядок містить два цілі числа $$$p$$$ та $$$q$$$ ($$$1 \leq p, q \leq n$$$) — координати ділянки, площу якої треба обчислити.

Вихідні дані

Виведіть площу ділянки, що знаходиться на перетині $$$p$$$-го стовпчика та $$$q$$$-го рядка.

Ми хочемо знати точне значення площі, тому відповідь треба виводити у факторизованому вигляді. Іншими словами, відповідь треба представити як декілька рядків, кожен з яких містить два цілі числа $$$p_i$$$ та $$$s_i$$$: число $$$p_i$$$ обов'язково просте та всі числа $$$p_i$$$ різні, а число $$$s_i$$$ — ціле та не дорівнює нулю. Шукана площа має дорівнювати: $$$$$$ S = p_1^{s_1} \cdot p_2^{s_2} \cdot p_3^{s_3} \ldots p_k^{s_k}, $$$$$$ де $$$k$$$ — кількість рядків у відповіді. Рядки треба відсортувати за зростанням простих чисел $$$p_i$$$. Нагадаємо, що число $$$X$$$ вважається простим, якщо воно має рівно два цілі додатні дільники: $$$1$$$ та $$$X$$$.

Якщо шукана площа дорівнює 1, то виведіть дві одиниці: «1 1».

Система оцінки

1. ($$$5$$$ балів): Площі всіх відомих ділянок — прості числа до $$$100$$$ або одиниці. Ділянка, площу якої треба обчислити, знаходиться на головній або побічній діагоналі. ($$$p - 1 = q$$$ або $$$p = q$$$)
2. ($$$5$$$ балів): Площі всіх відомих ділянок — прості числа до $$$100$$$ або одиниці. Ділянка, площу якої треба обчислити, знаходиться на перетині $$$i$$$-го стовпчика та $$$(i+1)$$$-го рядка. ($$$p + 1 = q$$$)
3. ($$$5$$$ балів): Площі всіх відомих ділянок не перевищують $$$10\,000$$$. Ділянка, площу якої треба обчислити, знаходиться на головній або побічній діагоналі. ($$$p - 1 = q$$$ або $$$p = q$$$)
4. ($$$5$$$ балів): Загальні обмеження на площі всіх відомих ділянок. Ділянка, площу якої треба обчислити, знаходиться на головній або побічній діагоналі. ($$$p - 1 = q$$$ або $$$p = q$$$)
5. ($$$5$$$ балів): Площі всіх відомих ділянок не перевищують $$$10\,000$$$. Ділянка, площу якої треба обчислити, знаходиться на перетині $$$i$$$-го стовпчика та $$$(i+1)$$$-го рядка. ($$$p + 1 = q$$$)
6. ($$$5$$$ балів): Загальні обмеження на площі всіх відомих ділянок. Ділянка, площу якої треба обчислити, знаходиться на перетині $$$i$$$-го стовпчика та $$$(i+1)$$$-го рядка. ($$$p + 1 = q$$$)
7. ($$$5$$$ балів): Кількість ділянок дорівнює $$$25$$$ ($$$n = 5$$$). Площі всіх відомих ділянок не перевищують $$$100$$$.
8. ($$$5$$$ балів): Площі всіх відомих ділянок — прості числа до $$$100$$$ або одиниці. Ділянка, площу якої треба обчислити, знаходиться у лівому верхньому куті. ($$$p=1$$$, $$$q=n$$$)
9. ($$$5$$$ балів): Площі всіх відомих ділянок — прості числа до $$$100$$$ або одиниці. Ділянка, площу якої треба обчислити, знаходиться у правому нижньому куті. ($$$p=n$$$, $$$q=1$$$)
10. ($$$5$$$ балів): Площі всіх відомих ділянок — прості числа до $$$100$$$ або одиниці. Ділянка, площу якої треба обчислити, знаходиться над головною діагоналлю. ($$$p < q$$$)
11. ($$$5$$$ балів): Площі всіх відомих ділянок — прості числа до $$$100$$$ або одиниці. Ділянка, площу якої треба обчислити, знаходиться під головною діагоналлю. ($$$p > q$$$)
12. ($$$5$$$ балів): Площі всіх відомих ділянок не перевищують $$$100$$$. Ділянка, площу якої треба обчислити, знаходиться у лівому верхньому куті. ($$$p=1$$$, $$$q=n$$$)
13. ($$$5$$$ балів): Площі всіх відомих ділянок не перевищують $$$100$$$. Ділянка, площу якої треба обчислити, знаходиться у правому нижньому куті. ($$$p=n$$$, $$$q=1$$$)
14. ($$$5$$$ балів): Площі всіх відомих ділянок не перевищують $$$100$$$. Ділянка, площу якої треба обчислити, знаходиться над головною діагоналлю. ($$$p < q$$$)
15. ($$$5$$$ балів): Площі всіх відомих ділянок не перевищують $$$100$$$. Ділянка, площу якої треба обчислити, знаходиться під головною діагоналлю. ($$$p > q$$$)
16. ($$$5$$$ балів): Загальні обмеження на площі всіх відомих ділянок. Ділянка, площу якої треба обчислити, знаходиться у лівому верхньому куті. ($$$p=1$$$, $$$q=n$$$)
17. ($$$5$$$ балів): Загальні обмеження на площі всіх відомих ділянок. Ділянка, площу якої треба обчислити, знаходиться у правому нижньому куті. ($$$p=n$$$, $$$q=1$$$)
18. ($$$8$$$ балів): Загальні обмеження на площі всіх відомих ділянок. Ділянка, площу якої треба обчислити, знаходиться над головною діагоналлю. ($$$p < q$$$)
19. ($$$7$$$ балів): Загальні обмеження на площі всіх відомих ділянок. Ділянка, площу якої треба обчислити, знаходиться під головною діагоналлю. ($$$p > q$$$)

Приклади

Вхідні дані

    5
    6 1 3 9 5
    3 9 3 6
    2 3

Вихідні дані

    3 -1

Вхідні дані

    5
    5 2 8 3 5
    2 6 8 9
    5 2

Вихідні дані

    2 1
    3 2

Вхідні дані

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

Вихідні дані

    1 1

Пояснення

Ділянка, що знаходиться на малюнку ліворуч, відповідає першому тесту з умови. Площа ділянки на перетині 2-го стовпчика та 3-го рядка дорівнює: $$$$$$ S = 3^{-1} = \frac{1}{3} $$$$$$

Ділянка, що знаходиться на малюнку праворуч, відповідає другому тесту з умови. Площа ділянки на перетині 5-го стовпчика та 2-го рядка дорівнює: $$$$$$ S = 2^{1} \cdot 3^2 = 18 $$$$$$