Cho xâu ~S~ độ dài ~N~ chỉ gồm các ký tự từ ~'a'..'z'~. Bạn cần xử lý ~Q~ truy vấn, mỗi truy vấn cho một đoạn ~[L..R]~. Với mỗi truy vấn, nếu có thể, hãy sắp xếp lại (hoán vị) các ký tự trong xâu con ~S[L..R]~ để thu được một xâu đối xứng (palindrome) và trong số các cách sắp xếp đối xứng hợp lệ, hãy chọn cách cho thứ tự từ điển nhỏ nhất của toàn bộ xâu sau khi thay thế đoạn đó. Nếu không thể tạo palindrome cho đoạn ~[L..R]~ (do ràng buộc tần suất ký tự), giữ nguyên đoạn này.

Sau khi thực hiện tuần tự tất cả ~Q~ truy vấn, in ra xâu ~S~ cuối cùng.

Yêu cầu

Thực hiện lần lượt ~Q~ truy vấn trên xâu ~S~ như mô tả.

• Nếu đoạn ~[L..R]~ có thể sắp xếp thành palindrome, thay ~S[L..R]~ bởi palindrome có thứ tự từ điển nhỏ nhất (trong phạm vi đoạn) và tiếp tục truy vấn tiếp theo dựa trên xâu đã cập nhật.
• Nếu không thể, không thay đổi đoạn và tiếp tục.

Dữ liệu

• Dòng 1: Hai số nguyên ~N~, ~Q~ ~(1 \le N, Q \le 10^5)~.
• Dòng 2: Xâu ~S~ có độ dài ~N~, chỉ gồm ký tự ~'a'..'z'~.
• Dòng 3..Q+2: Mỗi dòng chứa hai số nguyên ~L, R~ ~(1 \le L \le R \le N)~ — đoạn cần xử lý.

Kết quả

• In ra một dòng chứa xâu ~S~ sau khi thực hiện xong ~Q~ truy vấn.

Ví dụ 1

Input

7 3
aabbcba
1 4 
2 6
3 7

Output

ababcba

Giải thích

• Bước 1: ~S[1..4]=\text{"aabb"}~ có thể xếp thành palindrome, chọn từ điển nhỏ nhất ~"abba"~ → ~\text{"aabbcba"} \to \text{"abbacba"}~.
• Bước 2: ~S[2..6]=\text{"bbacb"}~ có thể xếp thành palindrome nhỏ nhất là ~"abcba"~, nhưng cần thay trên đoạn và giữ phần còn lại → xâu vẫn ~\text{"abbacba"}~ (vì thay ~"bbacb"~ bằng ~"abcba"~ cho kết quả giống).
• Bước 3: ~S[3..7]=\text{"bacba"}~ → palindrome nhỏ nhất ~"abcba"~ → kết quả cuối ~\text{"ababcba"}~.

Ví dụ 2

Input

8 2
abcdzzdc
1 8
2 7

Output

abcdzzdc

Giải thích

• Với đoạn ~[1..8]~, tần suất ký tự có 2 ký tự lẻ (hai chữ ~'z'~ là chẵn, nhưng ~'a','b','c','d'~ đều lẻ) → không thể thành palindrome → bỏ qua.
• Đoạn ~[2..7]~ cũng không thể → xâu giữ nguyên.

Gợi ý & Ràng buộc thuật toán (không bắt buộc khi cài đặt)

• Một đoạn ~[L..R]~ có thể sắp xếp thành palindrome khi và chỉ khi số lượng ký tự có tần suất lẻ trong đoạn ~\le 1~.
• Palindrome từ điển nhỏ nhất trên đoạn thu được bằng cách:
  • Đặt lần lượt từ ký tự ~'a'~ đến ~'z'~ vào nửa trái (mỗi ký tự lấy ~\lfloor cnt[c]/2 \rfloor~ lần),
  • Soi gương nửa trái sang nửa phải theo thứ tự đối xứng,
  • Nếu tồn tại ký tự có tần suất lẻ, đặt một ký tự đó ở giữa.
• Để đạt hiệu năng với ~N, Q \le 10^5~, tham khảo cấu trúc dữ liệu:
  • Segment tree lưu 26 tần suất/ký tự cho mỗi nút, hỗ trợ: (i) đếm tần suất theo đoạn, (ii) gán đoạn thành một ký tự duy nhất (range assign) với lazy propagation.
  • Với mỗi truy vấn hợp lệ, bạn sẽ thực hiện tối đa 26 phép gán đoạn để dựng nửa trái theo thứ tự từ ~'a'~ lên và phần soi gương cho nửa phải (cộng thêm gán 1 ký tự giữa nếu cần).
  • Bộ nhớ ~\mathcal{O}(26 \cdot 4N)~, thời gian xấp xỉ ~\mathcal{O}(26 \log N)~ cho mỗi truy vấn hợp lệ, ~\mathcal{O}(\log N)~ để kiểm tra tần suất.

Chấm điểm

Tổng ~100~ điểm, gồm:

• Subtask 1 (20 điểm): ~1 \le N, Q \le 2000~ — có thể thao tác trực tiếp trên mảng/ký tự.
• Subtask 2 (30 điểm): Chỉ có truy vấn trên các đoạn có độ dài ~\le 2000~.
• Subtask 3 (50 điểm): Ràng buộc đầy đủ ~(1 \le N, Q \le 10^5)~ — yêu cầu cấu trúc dữ liệu như gợi ý để đạt thời gian hợp lệ.

Lưu ý cài đặt (tuỳ chọn):

• Có thể nén trạng thái đoạn toàn ký tự ~c~ bằng mask 26-bit trong lazy tag để gán nhanh.
• Lúc dựng palindrome, dùng hai con trỏ ~i=L~, ~j=R~; với mỗi chữ ~c~ từ ~'a'~..~'z'~, gán đoạn ~[i, i+k-1]~ là ~c~ với ~k=\lfloor cnt[c]/2 \rfloor~, đồng thời gán đối xứng ~[j-k+1, j]~ là ~c~, rồi cập nhật ~i \leftarrow i+k~, ~j \leftarrow j-k~. Nếu còn ký tự lẻ, gán vị trí giữa ~i==j~ bằng chữ đó.