String sorting - MarisaOJ: Marisa Online Judge

Given a string

S

$S$ of length

n

$n$ consisting of lowercase letters, there are

q

$q$ queries of the form

(l, r, k)

$(l, r, k)$ . If

k

$k$ is equal to

1

$1$ , sort the substring

S [l . . . r]

$S[l...r]$ in non-decreasing order; otherwise, if

k

$k$ is equal to

0

$0$ , sort it in non-increasing order. ### Input - The first line contains two integers

n, q

$n, q$ . - The second line contains the string

S

$S$ . - The next

q

$q$ lines each contain three integers

l, r, k

$l, r, k$ . ### Output - Print the string

S

$S$ after performing the

q

$q$ queries. ### Constraints -

1 \leq n \leq 10^{5}

$1 \le n \le 10^5$ ,

1 \leq q \leq 5 \times 10^{4}

$1 \le q \le 5 \times 10^4$ . ### Example Input:

74 \pm y y r g z 251450561241

$7 4 pmyyrgz 2 5 1 4 5 0 5 6 1 2 4 1$

Output:

\pm r y g y z

$pmrygyz$

Topic

Data structure

Rating

1900

Solution (0)

Solution