Boring Problem#232
Sign in

Boring Problem

2.5 seconds
256 megabytes
Very hard

You are given a string of length . Let's define a function from a string:

f(s) = \displaystyle \sum_{i=1}^n \sum_{j=i}^n |s_i - s_j|

Here |a-b| denotes a distance between characters and in alphabet. In other words, denotes sum of |s_i-s_j| over all 1 \le i \le j \le n. Then, let

cost(s) = \sum_{i=1}^n \sum_{j=i}^n f(s[i..j])

Here denotes substring of string from index to . In other words, denotes sum of f(s[l..r]) over all 1 \le l \le r \le n.

You are given queries. Each query changes the element at position to , i.e., s_p = c. You need to print mod before all queries and after each query.

Input

The first line of input contains a single integer (1 \le n \le 2 \cdot 10^5) — the length of the string .

The second line of input contains a string of length .

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

The following lines contain an integer (1 \le p \le n) and character (c \in \{a,b, \dots, y,z\}) — description of queries.

Output

Print q+1 integers in separate lines — answers for the problem.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  1. ( points): n \le 3;

  2. ( points): n,q \le 50;

  3. ( points): n,q \le 100;

  4. ( points): c,s_i \in \{a,b\};

  5. ( points): n,q \le 5000;

  6. ( points): n,q \le 20000;

  7. ( points): c,s_i \le "n";

  8. ( points): n,q \le 10^5;

  9. ( points): no additional restrictions.