Армейские товарищи
Nlogonia ведет ожесточенную войну с соседней страной Кубикония. Главнокомандующий армией Нлогонии решил атаковать врага, выстроив солдат в линию, которая будет продвигаться вперед до полной победы. Перед битвой он приказал, чтобы каждый солдат в линии, помимо защиты себя и атаки, также защищал двух своих ближайших соседей: одного слева и одного справа. Он объяснил, что для каждого солдата его "товарищами" будут эти два соседа, если они существуют (у самого левого солдата нет соседа слева, а у самого правого — справа). Главнокомандующий подчеркнул, что защита товарищей крайне важна для поддержания целостности линии. Если левый или правый товарищ солдата погибает, следующий живой сосед слева или справа должен стать его новым товарищем.
Битва идет ожесточенно, и многие солдаты в линии погибают от выстрелов, гранат и бомб. Однако, следуя приказам главнокомандующего, информационная служба армии должна немедленно сообщать солдатам о новых товарищах после получения сведений о потерях.
Вам дано количество солдат в линии и последовательность отчетов о потерях. Каждый отчет описывает группу смежных солдат, которые только что погибли в бою. Напишите программу, которая для каждого отчета о потерях определяет новых товарищей.
Входные данные
Каждый тестовый случай состоит из нескольких строк. Первая строка содержит два целых числа S и B, обозначающих количество солдат в линии и количество отчетов о потерях соответственно (1 ≤ B ≤ S ≤ 10^5). Солдаты идентифицируются целыми числами от 1 до S в порядке их расположения в линии, где 1 — самый левый солдат, а S — самый правый. Каждая из следующих B строк описывает отчет о потерях двумя целыми числами L (левый) и R (правый), указывающими, что солдаты от L до R погибли (1 ≤ L ≤ R ≤ S). Можно предположить, что до этого момента эти солдаты были живы и только что погибли.
Последний тестовый случай завершается строкой, содержащей два нуля.
Выходные данные
Для каждого тестового случая выведите B+1 строк. В i-й строке укажите новых товарищей, сформированных после удаления из линии солдат, погибших согласно i-му отчету о потерях. Для отчета 'L R' выведите первого выжившего солдата слева от L и первого выжившего солдата справа от R. Если в каком-либо направлении нет выжившего солдата, выведите '*' (звездочка). После каждого тестового случая выведите строку, содержащую один символ '-' (дефис).