E. IPv6 Address Compression
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Sachin was investigating IPv6 addresses and the way they were compressed, and this gave him an idea for a new compression scheme. First, you have an address of $$$n$$$ hexadecimal characters. Hexadecimal characters are the digits $$$0-9$$$ and the letters $$$a-f$$$. They are separated into blocks of $$$k$$$ hexadecimal characters with colons in between blocks. To compress the string, perform the following process:

  • Pick a hexadecimal character $$$c$$$ and remove all occurrences of c in the string.
  • Remove as few colons as possible so that there are no more than 2 colons in a row.

Sachin wants to know for a given string the smallest compression length. He also wants to see how changing the string affects the compression length, so he will give you multiple queries. In the $$$i$$$-th query, he will change all characters in the range $$$[l_i, r_i]$$$ in the string to the character $$$c_i$$$. After each query, report the smallest compression length.

Input

The first line of input consists of two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le n \le 10^5)$$$ — the length of the string and the block size, respectively. It is guaranteed that $$$n$$$ is a multiple of $$$k$$$.

The second line of input consists of a string of $$$n$$$ characters, where each character is a hexadecimal character ($$$0-9,a-f$$$).

The third line of input consists of a single integer $$$q$$$ $$$(1 \le q \le 10^5)$$$ — the number of queries.

The next $$$q$$$ lines of input each consist of two integers $$$l_i$$$ and $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$, as well as a hexadecimal character $$$c_i$$$.

Output

Output $$$q$$$ lines, where the $$$i$$$-th line consists of a single integer representing the smallest compression length of the string after processing the first $$$i$$$ queries.

Example
Input
8 2
0a80f2c3
5
2 3 0
4 6 e
8 8 c
2 5 5
2 7 9
Output
7
8
8
7
4
Note

After the first query in the example, the uncompressed string is 00:00:f2:c3. The optimal character to remove is '0', which results in ::f2:c3. Since there are no more than 2 colons in a row, no colons can be removed and the answer is 7.

After the fifth query in the example, the uncompressed string is 09:99:99:9c. The optimal character to remove is '9', which results in 0:::c. One colon needs to be removed, resulting in 0::c with a length of 4.