DMOPC '21 Contest 7 P2 - Knitting Scarves

View as PDF

Points: 7
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Kanna's scarf is coloured with patches of colours that can be numbered from to . Kanna likes her scarf in a certain pattern and Edward needs to be able to recreate this scarf. Kanna is going to give sequential instructions of how she would like her scarf, starting from the default pattern where the patches are numbered in increasing order. At the -th step, she wants Edward to perform a knitting operation, taking the continuous segment of colours starting with colour and ending with colour and moving it right after colour if . If , then she wants the continuous segment to be moved to the very front of the scarf.

Can you tell Edward what the scarf should look like after all steps?

Constraints

After the first steps have been performed:

• Colour appears no later than colour in the scarf.
• is not contained in the continuous segment of colours starting with colour and ending with colour .

Input Specification

The first line contains integers and .

The -th of the following lines contains integers , , and .

Output Specification

As a space-separated sequence of integers, output the sequence of colours on the scarf after all steps have been performed.

Sample Input

6 3
4 5 1
5 6 0
2 2 3

Sample Output

5 3 2 6 1 4

Explanation

Initially, the colours on the scarf are .

After the first step, the colours on the scarf are .

After the second step, the colours on the scarf are .

After the final step, the colours on the scarf are .