Валентин выписывает натуральные числа, начиная с 1, в виде лестницы: на первой строке он пишет одно число, на второй — два, на третьей — три, и так далее.
1
2 3
4 5 6
7 8 9 10
...
После этого он стирает все числа на каждой строке, кроме первых $$$k$$$. Если в строке меньше $$$k$$$ чисел, он оставляет их все.
Заданы целые числа $$$a$$$ и $$$b$$$, а также число $$$k$$$. Выведите строки с $$$a$$$-й по $$$b$$$-ю, которые получились у Валентина.
На ввод подаются три строки: первая содержит число $$$a$$$, вторая содержит число $$$b$$$, третья содержит число $$$k$$$ ($$$1 \le a \le b \le 10^9$$$, $$$b - a \le 100$$$, $$$1 \le k \le 100$$$).
Выведите строки с $$$a$$$-й по $$$b$$$-ю, которые получились у Валентина. Числа в строках разделяйте пробелами.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 13 | $$$1 \le a \le b \le 100$$$, $$$k = 1$$$ | |
| 2 | 13 | $$$1 \le a \le b \le 100$$$, $$$k \le a$$$ | 1 |
| 3 | 13 | $$$1 \le a \le b \le 100$$$ | 1, 2 |
| 4 | 17 | $$$a = b$$$ | |
| 5 | 17 | $$$k = 1$$$ | 1 |
| 6 | 27 | 1–5 |
1 5 3
1 2 3 4 5 6 7 8 9 11 12 13
Даша очень любит представлять числа в виде суммы. Сегодня Даша хочет выписать все возможные представления числа $$$n$$$ в виде суммы $$$k$$$ слагаемых.
При этом она не любит, когда слагаемые меняются слишком быстро. А именно, соседние слагаемые в представлении Даши должны различаться не больше, чем на единицу. Она использует и положительные, и отрицательные, и даже нулевые слагаемые, порядок слагаемых важен.
Выведите все представления, которые подходят по Дашины ограничения. Разбиения следует упорядочить по первому слагаемому, при равном первом слагаемом — по второму, при равных первых двух — по третьему, и так далее.
Первая строка ввода содержит число $$$n$$$ ($$$-15\le n \le 15$$$).
Вторая строка содержит число $$$k$$$ ($$$1 \le k \le 15$$$).
Гарантируется, что общее число представлений не превышает $$$10^5$$$.
Выводите представления по одному на строке, перед положительными и нулевыми слагаемыми, кроме первого в представлении, выводите знак плюс. Не выводите пробелы.
В этой задаче 25 тестов, каждый оценивается независимо в 4 балла.
2 4
-1+0+1+2 0+0+1+1 0+1+0+1 0+1+1+0 1+0+0+1 1+0+1+0 1+1+0+0 2+1+0-1
Последовательность $$$X = [x_1, x_2, \ldots, x_t]$$$ является подпоследовательностью последовательности $$$Y = [y_1, y_2, \ldots, y_s]$$$, если можно удалить некоторые (возможно ни одного) элементы $$$Y$$$, чтобы получить $$$X$$$. Иначе говоря, существует последовательность индексов $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_t \le s$$$, что $$$x_j = y_{i_j}$$$ для всех $$$j$$$ от $$$1$$$ до $$$s$$$. Например, последовательность $$$[1, 2, 3, 2]$$$ является подпоследовательностью последовательности $$$[\mathbf{1}, 1, \mathbf{2}, 2, 1, \mathbf{3}, \mathbf{2}, 1]$$$, а последовательность $$$[1, 2, 3, 1, 2]$$$ — нет.
Рассмотрим две последовательности $$$A = [a_1, a_2, \ldots, a_m]$$$ и $$$B = [b_1, b_2, \ldots, b_n]$$$, состоящие из целых чисел от $$$1$$$ до $$$k$$$.
Требуется найти минимальную по длине последовательность $$$C = [c_1, c_2, \ldots, c_p]$$$, которая не являлась бы подпоследовательностью ни $$$A$$$ ни $$$B$$$. Элементы последовательности $$$C$$$ также должны являться целыми числами от $$$1$$$ до $$$k$$$.
Первая строка ввода содержит число $$$k$$$ — максимальное значение элемента последовательности ($$$1 \le k \le 5\,000$$$).
Вторая строка содержит число $$$m$$$ — длину последовательности $$$A$$$ ($$$1 \le m \le 5\,000$$$). Третья строка содержит $$$m$$$ целых чисел от $$$1$$$ до $$$k$$$ — последовательность $$$A$$$.
Четвертая строка содержит число $$$n$$$ — длину последовательности $$$B$$$ ($$$1 \le n \le 5\,000$$$). Пятая строка содержит $$$n$$$ целых чисел от $$$1$$$ до $$$k$$$ — последовательность $$$B$$$.
На первой строке выведите $$$p$$$ — длину искомой последовательности. На второй строке выведите последовательность $$$C$$$. Если оптимальных ответов несколько, выведите любой из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 11 | $$$k = 1$$$ | |
| 2 | 10 | $$$k = 2$$$; $$$1 \le m, n \le 10$$$ | |
| 3 | 10 | $$$k = 2$$$; $$$1 \le m, n \le 200$$$ | 2 |
| 4 | 10 | $$$k = 2$$$; $$$1 \le m, n \le 5000$$$ | 2, 3 |
| 5 | 15 | $$$1 \le m, n \le 10$$$ | 2 |
| 6 | 15 | $$$1 \le m, n \le 200$$$ | 2, 3, 5 |
| 7 | 29 | $$$1 \le m, n \le 5000$$$ | 1–6 |
2 5 1 2 1 2 1 5 2 1 2 1 2
4 1 1 1 1