The boss of P company plays an interesting game with employees. At the beginning, the boss gives a very long string with length m. The boss invites n employees to reorder the string with command a, s, e, where a in {0, 1} denotes the type of operation, s and e are positions in the string. If a = 0, all characters from s to e are ordered in non-increasing order. If a = 1, all characters from s to e are ordered in non-decreasing order. After n times operation, the boss wants to know the final string.

输入描述:

The first line contains two integers m, (1 = m = 100000), n, (0 = n = 50000) - the length of the string and the number of operations. The next line contains a string with length m. Next n lines contain operation command a, s, e, where a in {0, 1} and 1 = s = e = m.

输出描述:

One line contains the final string.