Description

一个 01 序列长度为 n，进行 m 次操作，每次将 [i,j] 区间的串按 k 进行排序：

区间坐标为[0, n-1]，k==0为升序，k==1为降序。

在操作之后，输出最终的串。

Input

不超过10组测试数据。

每组数据第一行为串长度 n 与 操作数m。

第二行为一个01串，长度为n。

接下来m行，每行三个整数 i, j, k 表示操作。

1 <= n <= 10^5，1 <= m <= 10^4，0 <= i < j < n， k 为 0 或 1。

Output

每组数据输出一行结果的01串。

10 3
0100110110
5 8 0
5 6 1
0 2 1
10 3
0110110000
5 8 0
6 7 0
2 8 0

1000110110
0100001110