В городе в ряд построено $$$n$$$ новых небоскребов, которые вы хотите обеспечить современной связью. Для этого вы хотите установить по датчичку на каждом небоскребе. На $$$i$$$-м из них вы можете его установить не ниже $$$a_i$$$ и не выше $$$b_i$$$. Задержкой для двух датчиков на высотах $$$h_1$$$ и $$$h_2$$$ называется величина $$$|h_1 - h_2|$$$. Вы хотите минимизировать сумму задержек для пар соседних зданий. Более формально, если датчики выставлены на высотах $$$d_1, d_2, \dotsc , d_n$$$, требуется минимизировать величину $$$|d_1 − d_2| + |d_2 − d_3| + \dotsc + |d_{n−1} − d_n|$$$.
Первая строка входных данных содержит единственное целое число $$$t$$$ $$$(1 \le t \le 10^3)$$$ — количество наборов входных данных. Описание наборов входных данных следует ниже.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(1 \le n \le 10^6)$$$ — длину массивов $$$a$$$, $$$b$$$.
Следующие две строки содержат по $$$n$$$ целых чисел: массивы $$$a$$$ и $$$b$$$ $$$(0 \le a_i \le b_i \le 10^9)$$$ соответственно.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$. В системе оценки сумма $$$n$$$ обозначена как $$$sum_n$$$.
Для каждого набора входных данных выведите две строки. Первая строка должна содержать ответ — минимальную суммарную задержку. Вторая строка должна содержать $$$n$$$ целых чисел $$$d_1, d_2, \dotsc , d_n$$$ — высоты расставленных датчиков. Должно выполняться $$$a_i \le d_i \le b_i$$$. Если решений несколько, выведите любое.
Задача состоит из 20 тестов, не считая тестов из условия. Каждый тест оценивается независимо в 5 баллов. Все тесты можно разделить на следующие группы:
| Группа | Макс. балл | Доп. ограничения | Комментарий | ||
| $$$n$$$ | $$$sum_n$$$ | $$$b_i$$$ | |||
| $$$0$$$ | 0 | — | — | — | Тесты из условия |
| $$$1$$$ | 20 | $$$n \le 20$$$ | $$$sum_n \le 2$$$ $$$000$$$ | $$$b_i \le 20$$$ | |
| $$$2$$$ | 20 | $$$n \le 500$$$ | $$$sum_n \le 2$$$ $$$000$$$ | $$$b_i \le 1000$$$ | |
| $$$3$$$ | 30 | $$$n \le 500$$$ | $$$sum_n \le 2$$$ $$$000$$$ | — | |
| $$$4$$$ | 40 | — | — | — | |
3 3 1 0 1 3 3 4 2 42 10 239 33 7 1 2 3 4 5 6 7 3 4 5 6 7 8 9
0 3 3 3 9 42 33 4 3 3 3 4 5 6 7
Ниже приведены иллюстрации для решений тестовых случаев из примера.
