Thomas, a freshly trained padawan, is about to create his very own Lightseba™. Recent advancements in kyber crystal technology have revolutionized these sebas, allowing for multiple colors across distinct sections.

Each Lightseba starts fully colored in blue (\(B\)), the objectively best color. Thomas then sends a sequence of coloring requests to his droid. Each request has the form \(L\), \(R\), \(C\), meaning:

• Recolor the segment from position \(L\) to \(R\) (inclusive)
• With the color \(C\) (an uppercase letter \(A–Z\))

When the droid processes a request, it completely overwrites any previous colors in that segment with the new color. Segments that never appear in any request remain blue (\(B\)).

Your task is to determine the final appearance of the Lightseba after all requests are processed in order.

Input Specification

The first line contains two integers \(N\) and \(Q\)
(\(1 ≤ N ≤ 10^5\), \(1 ≤ Q ≤ 10^5\)):

• \(N\) — the length of the Lightseba (number of segments)
• \(Q\) — the number of coloring requests

Each of the next \(Q\) lines contains two integers \(L\) and \(R\) and an uppercase letter \(C\)
(\(1 ≤ L ≤ R ≤ N\), \(C ∈ {A, B, ..., Z}\)):

• \(L\), \(R\) — the inclusive range of segments to recolor
• \(C\) — the color for that segment

The Lightseba is initially all blue (\(B\)).

Output Specification

Output a single line containing a string of length \(N\) consisting of uppercase letters, representing the final colors of the Lightseba after all \(Q\) requests have been applied in order. Any segment not recolored by a request must remain \(B\).

Sample Input 1

6 3
1 2 G
6 6 R
5 6 P

Sample Output 1

GGBBPP

Sample Input 2

5 1
1 5 R

Sample Output 2

RRRRR