Sort Substrings Operation

You are given a string s and a list of operations. Each operation is defined by a pair of integers \(l\) and \(r\). For each operation, you are required to sort the substring of s from index \(l-1\) to \(r-1\) (i.e. the portion \(s[l-1:r]\)) in non-decreasing order.

You need to perform all operations sequentially and output the final string. For example, given s = "abacdb" and operations [(2, 4), (1, 6)], after the first operation the string becomes "aabcdb", and after the complete operations, the string is "aabbcd".

Note: The indices are 1-based in the operations.

inputFormat

The input is given via standard input (stdin) in the following format:

1. A string s consisting of lowercase English letters.
2. An integer n representing the number of operations.
3. n lines follow, each line contains two integers \(l\) and \(r\) separated by spaces.

It is guaranteed that \(1 \leq l \leq r \leq |s|\), where \(|s|\) is the length of string s.

outputFormat

Output the final string after performing all operations on s. The output should be printed to standard output (stdout).

abacdb
2
2 4
1 6

aabbcd