Ура! Король Берлядии Берл II устраивает рыцарский турнир. Король уже разослал послание всем рыцарям королевства, а они, в свою очередь, дали согласие на участие в этом грандиозном событии.
Что же касается вас, то вы — простой крестьянин. Не удивительно, что рыцарский турнир вы проспали (ведь он проводился в выходной), и теперь вам очень хочется узнать его результаты. В этот раз рыцарский турнир в Берляндии проходил следующим образом:
- В турнире принимали участие n рыцарей. Каждому рыцарю был присвоен уникальный номер — целое число от 1 до n.
- Турнир проводился в m сражений, в i-ом сражении все еще не выбывшие рыцари с номерами не меньше li и не больше ri боролись за право продолжить участие в турнире.
- После i-го сражения среди всех рыцарей, которые боролись, победил только один — рыцарь с номером xi, он продолжил участие в турнире. Остальные рыцари выбыли из турнира.
- Победитель самого последнего (m-го) сражения (рыцарь с номером xm) был объявлен победителем всего турнира.
Вы узнали у своих друзей информацию про все сражения, и теперь для каждого рыцаря вам интересно знать, каким рыцарем он был побежден. Считается, что рыцарь с номером a победил рыцаря с номером b, если было такое сражение, в котором боролись оба этих рыцаря, а победителем из этого сражения вышел рыцарь с номером a.
Напишите программу, вычисляющую для каждого рыцаря, каким рыцарем он был побежден.
Выходные данные
Выведите n целых чисел. Если i-ый рыцарь был побежден, то i-ое число должно быть равно номеру рыцаря, который победил рыцаря с номером i. Если i-ый рыцарь является победителем турнира, то i-ое число должно быть равно 0.
Примечание
Рассмотрим первый тестовый пример. В первом сражении бились рыцари 1 и 2, победил рыцарь 1. Во втором сражении бились рыцари 1 и 3, победил рыцарь 3. В последнем сражении бились рыцари 3 и 4, победил рыцарь 4.