HansBug's Mind String Operations

HansBug is in an exam and his mind is a long string consisting of exactly 26 lowercase letters (from a to z). You are given a magical prescription that contains three types of operations sequentially:

• Operation 1: Given indices \(x\) and \(y\) and a letter \(k\), count how many times letter \(k\) appears in the substring from index \(x\) to \(y\) (inclusive). This can be represented by the query:
  \(query: 1\; x\; y\; k\).</p>
• Operation 2: Given indices \(x\) and \(y\) and a letter \(k\), assign the substring from index \(x\) to \(y\) to letter \(k\). Represented as:
  \(query: 2\; x\; y\; k\).
• Operation 3: Given indices \(x\) and \(y\), sort the substring from index \(x\) to \(y\) in non-decreasing order according to the alphabetical order (i.e. from \(a\) to \(z\)). Represented as:
  \(query: 3\; x\; y\).

You need to process the operations on the given string sequentially. For every operation of type 1, output the answer in a new line.

Note: The positions are 1-indexed. All provided formulas are in LaTeX format.

inputFormat

The first line contains a string s consisting of lowercase letters ('a'-'z') only.

The second line contains an integer Q which represents the number of operations.

The following Q lines each contain an operation in one of the following formats:

• For operation 1: 1 x y k
• For operation 2: 2 x y k
• For operation 3: 3 x y

Here, x and y are integers denoting the positions in the string (1-indexed), and k is a lowercase letter.

outputFormat

For each operation of type 1, output an integer representing the answer on a new line.

sample

abcde
3
1 1 5 a
2 2 4 b
1 1 5 b

1
3