Keyboard Event

When a key is pressed on a keyboard, the computer receives which key was pressed, and the computer prints the keys on the screen in the order they were pressed.

Seungji has to write 100 pages of a report for a team project, and with the deadline close, he asked his teammates for help. But there was only one computer, so they could not write the report at the same time.

Looking around, he saw several unused keyboards rolling on the floor. In a hurry, he decided to connect several keyboards to the computer to raise the typing speed.

The problem is that writing a desired sentence requires good coordination, and Seungji, who did not yet know how keyboards work, could not tell what would be printed.

Seungji gave N keyboards to N teammates and connected them all to the computer. If each person decides in advance at what time he will press which key, Seungji wants to find out what will be printed on the screen.

Keyboards are numbered 1, 2, ..., N in the order they are connected to the computer. If several keyboards are pressed at the same time, the key pressed on the keyboard with the smaller number is printed first, but a single keyboard cannot have several keys pressed at the same time. That is, the times at which each key is pressed on one keyboard are all different.

The first line gives the number of connected keyboards N and the number of key presses M. (1 ≤ N, M ≤ 1,000)

The next M lines give integers a, b and a character c. This means that on keyboard a, the key labeled c will be pressed at time b. (1 ≤ a ≤ N, 0 ≤ b ≤ 1,000,000)

A keyboard has only uppercase alphabet keys and digit keys.

Print the result that will be displayed on the screen after all the input is processed.