Ура! Король Берлядии Берл II устраивает рыцарский турнир. Король уже разослал послание всем рыцарям королевства, а они, в свою очередь, дали согласие на участие в этом грандиозном событии.

Что же касается вас, то вы — простой крестьянин. Не удивительно, что рыцарский турнир вы проспали (ведь он проводился в выходной), и теперь вам очень хочется узнать его результаты. В этот раз рыцарский турнир в Берляндии проходил следующим образом:

• В турнире принимали участие n рыцарей. Каждому рыцарю был присвоен уникальный номер — целое число от 1 до n.
• Турнир проводился в m сражений, в i-ом сражении все еще не выбывшие рыцари с номерами не меньше l_i и не больше r_i боролись за право продолжить участие в турнире.
• После i-го сражения среди всех рыцарей, которые боролись, победил только один — рыцарь с номером x_i, он продолжил участие в турнире. Остальные рыцари выбыли из турнира.
• Победитель самого последнего (m-го) сражения (рыцарь с номером x_m) был объявлен победителем всего турнира.

Вы узнали у своих друзей информацию про все сражения, и теперь для каждого рыцаря вам интересно знать, каким рыцарем он был побежден. Считается, что рыцарь с номером a победил рыцаря с номером b, если было такое сражение, в котором боролись оба этих рыцаря, а победителем из этого сражения вышел рыцарь с номером a.

Напишите программу, вычисляющую для каждого рыцаря, каким рыцарем он был побежден.