Problem Statement

You are given a string S of length N. You are also given Q queries, which you should process in order.

The i-th query is as follows:

• Given an integer X_i and a character C_i, replace the X_i-th character of S with C_i. Then, print the number of times the string ABC appears as a substring in S.

Here, a substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• S is a string of length N consisting of uppercase English letters.
• 1 \le X_i \le N
• C_i is an uppercase English letter.

Sample Input 1

7 4
ABCDABC
4 B
3 A
5 C
4 G

Sample Output 1

2
1
1
0

After processing each query, S becomes as follows.

• After the first query: S= ABCBABC. In this string, ABC appears twice as a substring.
• After the second query: S= ABABABC. In this string, ABC appears once as a substring.
• After the third query: S= ABABCBC. In this string, ABC appears once as a substring.
• After the fourth query: S= ABAGCBC. In this string, ABC appears zero times as a substring.

Sample Input 2

3 3
ABC
1 A
2 B
3 C

Sample Output 2

1
1
1

There are cases where S does not change through processing a query.

Sample Input 3

15 10
BBCCBCACCBACACA
9 C
11 B
5 B
11 B
4 A
8 C
8 B
5 B
7 B
14 B

Sample Output 3

0
0
0
0
1
1
2
2
1
1

Problem Statement

Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.

Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.

Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq D\leq 2\times 10^5
• 1\leq P\leq 10^9
• 1\leq F_i\leq 10^9
• All input values are integers.

Sample Input 1

5 2 10
7 1 6 3 6

Sample Output 1

20

If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.

Sample Input 2

3 1 10
1 2 3

Sample Output 2

6

The minimum cost is achieved by paying the regular fare for all three days.

Sample Input 3

8 3 1000000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

You are given a string S consisting of uppercase English letters.

Find the number of integer triples (i, j, k) satisfying both of the following conditions:

• 1 \leq i < j < k \leq |S|
• The length-3 string formed by concatenating S_i, S_j, and S_k in this order is a palindrome.

Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of uppercase English letters.

Sample Input 1

ABCACC

Sample Output 1

5

The triples satisfying the conditions are (i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6).

Sample Input 2

OOOOOOOO

Sample Output 2

56

Sample Input 3

XYYXYYXYXXX

Sample Output 3

75

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects Vertices U_i and V_i. Vertex i has a positive integer A_i written on it.

You will repeat the following operation N times.

• Choose a Vertex x that is not removed yet, and remove Vertex x and all edges incident to Vertex x. The cost of this operation is the sum of the integers written on the vertices directly connected by an edge with Vertex x that are not removed yet.

We define the cost of the entire N operations as the maximum of the costs of the individual operations. Find the minimum possible cost of the entire operations.

Constraints

• 1 \le N \le 2 \times 10^5
• 0 \le M \le 2 \times 10^5
• 1 \le A_i \le 10^9
• 1 \le U_i,V_i \le N
• The given graph is simple.
• All values in input are integers.

Sample Input 1

4 3
3 1 4 2
1 2
1 3
4 1

Sample Output 1

3

By performing the operations as follows, the maximum of the costs of the N operations can be 3.

• Choose Vertex 3. The cost is A_1=3.
• Choose Vertex 1. The cost is A_2+A_4=3.
• Choose Vertex 2. The cost is 0.
• Choose Vertex 4. The cost is 0.

The maximum of the costs of the N operations cannot be 2 or less, so the solution is 3.

Sample Input 2

7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

Sample Output 2

1199

Problem Statement

AtCoder Inc.'s online shop currently handles N products, and the stock of product i is A_i units remaining.

Process the following Q orders in order. The i-th order is as follows:

• Buy k_i units each of products l_i,l_i+1,\dots,r_i. For products with fewer than k_i units, buy all available units. Report the total number of products bought in this order.

Note that for i<Q, the stock of products bought in the i-th order is reduced before proceeding to the (i+1)-th order.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^{15}
• 1 \le Q \le 3 \times 10^5
• 1 \le l_i \le r_i \le N
• 1 \le k_i \le 10^9

Sample Input 1

6
2 6 4 5 7 5
5
1 6 1
3 5 4
4 4 1
2 5 1
1 6 100

Sample Output 1

6
11
0
2
10

This input contains 5 orders.

• Initially, the stocks of the products are (from product 1 onward) 2,6,4,5,7,5 units.
• The first order is l_1 = 1, r_1 = 6, k_1 = 1.
  • In this order, 1,1,1,1,1,1 units of the products are bought, for a total of 6 units.
  • After this, the stocks of the products become 1,5,3,4,6,4 units.
• The second order is l_2 = 3, r_2 = 5, k_2 = 4.
  • In this order, 0,0,3,4,4,0 units of the products are bought, for a total of 11 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The third order is l_3 = 4, r_3 = 4, k_3 = 1.
  • In this order, 0,0,0,0,0,0 units of the products are bought, for a total of 0 units.
  • After this, the stocks of the products become 1,5,0,0,2,4 units.
• The fourth order is l_4 = 2, r_4 = 5, k_4 = 1.
  • In this order, 0,1,0,0,1,0 units of the products are bought, for a total of 2 units.
  • After this, the stocks of the products become 1,4,0,0,1,4 units.
• The fifth order is l_5 = 1, r_5 = 6, k_5 = 100.
  • In this order, 1,4,0,0,1,4 units of the products are bought, for a total of 10 units.
  • After this, the stocks of the products become 0,0,0,0,0,0 units.