Даны два массива целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_m$$$.
Обозначим через $$$\gcd(a)$$$ наибольший общий делитель всех элементов массива $$$a$$$, то есть наибольшее целое положительное число, на которое делится каждый элемент этого массива. Аналогично определим $$$\gcd(b)$$$.
За одну операцию можно выбрать один из двух массивов, один элемент выбранного массива и целое число $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$), после чего увеличить выбранный элемент на $$$x$$$. После выполнения операции выбранный элемент сохраняет новое значение, а все последующие операции выполняются над текущим состоянием массивов. Один и тот же элемент можно выбирать в нескольких операциях.
Найдите минимальное количество операций, после выполнения которых $$$\gcd(a) = \gcd(b)$$$, и выведите последовательность таких операций.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n, m \leq 10^5$$$) — длины массивов $$$a$$$ и $$$b$$$ соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Третья строка содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_j \leq 10^9$$$).
В первой строке выведите одно целое число $$$k$$$ — минимальное количество операций, необходимое для того, чтобы сделать $$$\gcd(a) = \gcd(b)$$$.
В каждой из следующих $$$k$$$ строк выведите три целых числа $$$p$$$, $$$i$$$ и $$$x$$$ — описание очередной операции:
Операции применяются к исходным массивам в порядке вывода. После выполнения всех операций должно выполняться равенство $$$\gcd(a) = \gcd(b)$$$.
Если существует несколько последовательностей операций минимальной длины, выведите любую из них.
4 327 6 9 1218 8 4
2 2 2 7 2 3 2
2 32 28 6 14
0
В первом примере первая операция увеличивает $$$b_2$$$ на $$$7$$$, после чего массив $$$b$$$ принимает вид $$$[18, 15, 4]$$$. Вторая операция увеличивает $$$b_3$$$ на $$$2$$$, и массив $$$b$$$ становится равным $$$[18, 15, 6]$$$. После выполнения этих операций $$$\gcd(a) = \gcd(b) = 3$$$. Можно показать, что добиться равенства НОД менее чем за две операции в этом примере невозможно, поэтому приведённая последовательность операций оптимальна.
Во втором примере изначально $$$\gcd(a) = \gcd(b) = 2$$$, поэтому выполнять операции не требуется, и ответ равен $$$0$$$.