У Васи есть прямоугольная плитка шоколада W × H долек. Он определил декартову систему координат так, что точка (0, 0) соответствует левому нижнему углу шоколадки, а точка (W, H) — правому верхнему. Одна долька шоколадки соответствует квадрату 1 × 1 с целочисленными координатами. Вася решил разделить шоколадку на куски разломами. Каждый разлом представляет собой параллельный одной из осей координат отрезок, проходящий от одной стороны куска до другой. То есть каждый разлом проходит вдоль линии x = xc или y = yc, где xc и yc — некоторые целые числа. Каждый разлом делит один кусок шоколадки на два непустых куска. После того как Вася разломил один кусок на два, получившиеся куски он разламывает отдельно и независимо друг от друга. При этом он не перемещает куски шоколадки. Вася сделал n разломов и записал их в блокнот в произвольном порядке. В результате у него получилось n + 1 кусков. Теперь он хочет посчитать их площади. Вася человек ленивый, и поэтому он просит вас сделать это за него.
Выходные данные
Выведите n + 1 чисел — площади получившихся кусков в порядке возрастания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 2
1 0 1 2
0 1 1 1
|
1 1 2
|
|
2
|
2 2 3
1 0 1 2
0 1 1 1
1 1 2 1
|
1 1 1 1
|
|
3
|
2 4 2
0 1 2 1
0 3 2 3
|
2 2 4
|