Даны два массива $$$p$$$ и $$$s$$$ длины $$$n$$$, где $$$p$$$ является префиксным НОД$$$^{\text{∗}}$$$ некоторого массива $$$a$$$, а $$$s$$$ — суффиксным НОД того же массива $$$a$$$. Иными словами, если бы массив $$$a$$$ существовал, то для каждого $$$1 \le i \le n$$$ выполнялись бы оба равенства:
$$$^{\text{∗}}$$$$$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.
Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Описание каждого набора входных данных состоит из трёх строк:
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — длину массива.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \le 10^9$$$) — элементы массива.
Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$s_1, s_2, \dots, s_n$$$ ($$$1 \leq s_i \le 10^9$$$) — элементы массива.
Гарантируется, что сумма всех $$$n$$$ по всем наборам входных данных не превышает $$$10^5$$$.
Для каждого набора входных данных выведите «Yes» (без кавычек), если существует массив $$$a$$$, для которого данные массивы $$$p$$$ и $$$s$$$ могут быть получены, и «No» (без кавычек) иначе.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
5672 24 3 3 3 33 3 3 6 12 14431 2 34 5 65125 125 125 25 2525 25 25 25 754123 421 282 251125 1981 239 2233124 521 125125 121 121
YES NO YES NO NO
Для первого примера возможен массив: [$$$72,\ 24,\ 3,\ 6,\ 12,\ 144$$$].
Для второго примера можно показать, что таких массивов не существует.
Для третьего примера существует массив: [$$$125,\ 125,\ 125,\ 25,\ 75$$$].
| Codeforces Round 1037 (Div. 3) |
|---|
| Закончено |
