Problem Statement

Takahashi is a chaperone teacher on a field trip, and his role is to give the departure signal after all students have boarded the bus.

There are N students participating in this field trip, and each student i (1 \leq i \leq N) finishes boarding the bus at time T_i. Here, time is represented as a non-negative integer in minutes, measuring the elapsed time from a certain reference point.

All students finish boarding the bus at the time equal to the maximum value among T_1, T_2, \ldots, T_N. Takahashi is supposed to give the departure signal exactly K minutes after that time.

Find the time at which Takahashi gives the departure signal.

Constraints

• 1 \leq N \leq 10^5
• 0 \leq K \leq 10^4
• 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
• T_1, T_2, \ldots, T_N are not necessarily in ascending order, and may contain duplicate values
• All input values are integers

Sample Input 1

3 5
10 25 15

Sample Output 1

30

Sample Input 2

5 10
100 50 200 150 75

Sample Output 2

210

Sample Input 3

8 1000
500000000 123456789 999999999 1 0 876543210 500000001 999999998

Sample Output 3

1000000999

Problem Statement

Takahashi is a tour conductor at a travel agency. For the upcoming bus tour, N participants have signed up, and each participant has a preferred departure time.

The preferred departure time of each participant i (1 \leq i \leq N) is T_i. According to the travel agency's policy, to operate tours efficiently, participants with similar preferred departure times are grouped together on the same bus. Specifically, for any two participants i, j on the same bus, the absolute difference of their preferred departure times |T_i - T_j| must be at most K. There is no upper limit on the number of people that can ride on a single bus.

Takahashi wants to assign every participant to exactly one bus and minimize the number of buses required.

Find the minimum number of buses needed to assign all participants to buses.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq 10^9
• 0 \leq T_i \leq 10^9 (1 \leq i \leq N)
• All inputs are integers

Sample Input 1

5 3
1 5 3 9 12

Sample Output 1

3

Sample Input 2

8 10
5 100 15 8 95 20 105 12

Sample Output 2

3

Sample Input 3

15 5
0 1 2 10 11 12 13 25 30 31 32 33 50 100 101

Sample Output 3

6

Problem Statement

Takahashi manages a vast farm.

The farm has N plots arranged in a row, numbered from 1 to N. Plot i (1 \leq i \leq N) has a fruit tree planted in it, and the amount of fruit that can be harvested from it is A_i kilograms.

During the harvest festival, Takahashi performs M harvesting operations. In the j-th (1 \leq j \leq M) harvesting operation, he harvests fruit from all consecutive plots from plot L_j to plot R_j.

The fruit in each plot is gone once harvested. Therefore, even if a plot is included in multiple harvesting operations, the yield obtained from that plot is only from the first time, namely A_i kilograms.

In other words, the total harvest Takahashi obtains is the sum of A_i over all plots that were targeted by at least one of the M harvesting operations. Find this total harvest.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• All inputs are integers

Sample Input 1

5 3
10 20 30 40 50
1 3
2 4
4 5

Sample Output 1

150

Sample Input 2

7 4
5 12 8 3 15 9 6
1 2
4 6
2 5
1 7

Sample Output 2

58

Sample Input 3

10 6
100 250 180 90 320 150 200 80 170 260
1 3
5 7
2 4
6 9
1 1
8 10

Sample Output 3

1800

Problem Statement

Takahashi performed N types of operations on a control panel with K lamps arranged in a row, executing one type per day over a total of N days.

Each operation was executed exactly once, but the order in which they were executed has been lost.

Each lamp is in one of two states: "on" or "off".

The state of the panel is represented by a 0/1 string of length K, where the j-th character (1 \leq j \leq K) being 1 indicates that lamp j is on, and 0 indicates it is off.

The initial state of the panel is given by the string S.

For operation i (1 \leq i \leq N), three 0/1 strings of length K: A_i, B_i, X_i are defined.

Execution condition: Operation i can be executed only when the following conditions are all satisfied for every j (1 \leq j \leq K):

• If the j-th character of A_i is 1, then lamp j must be on.
• If the j-th character of B_i is 1, then lamp j must be off.

When both the j-th character of A_i and the j-th character of B_i are 0, the state of lamp j does not matter.

On the other hand, it is possible that both the j-th character of A_i and the j-th character of B_i are 1. In that case, lamp j must be both on and off simultaneously, which cannot be satisfied by any panel state, so operation i can never be executed under any circumstances.

Effect: When operation i is executed, for each j (1 \leq j \leq K):

• If the j-th character of X_i is 1, the on/off state of lamp j is toggled.
• If the j-th character of X_i is 0, lamp j does not change.

Aoki recorded only the number of lamps that are on after the operation on each day.

As the initial record, the number of lamps on after the operation on day t (1 \leq t \leq N), C_t, is given.

This record is subject to Q corrections afterwards.

In the q-th correction (1 \leq q \leq Q), the value for day T_q in the current record is changed to Y_q. All changes from previous corrections are retained, and the new correction is applied as an overwrite.

After each correction, find the number of operation execution orders that are consistent with the record at that point, modulo 998244353.

Here, an operation execution order is a permutation (p_1, p_2, \ldots, p_N) of (1, 2, \ldots, N), and a permutation is consistent with the record if and only if all of the following are satisfied:

• The initial state of the panel is S.
• On day t (t = 1, 2, \ldots, N), operation p_t is executed.
• The panel state immediately before executing operation p_t satisfies the execution condition of operation p_t.
• The number of lamps on after the operation on day t equals C_t in the record.

Note that different permutations of operation numbers are counted as different execution orders, even if they only swap operations with identical conditions and effects.

Constraints

• 1 \leq N \leq 9
• 1 \leq K \leq 9
• 1 \leq Q \leq 10^5
• S is a string of length K, where each character is 0 or 1
• 0 \leq C_t \leq K (1 \leq t \leq N)
• A_i, B_i, X_i are each strings of length K, where each character is 0 or 1 (1 \leq i \leq N)
• It is possible that both the j-th character of A_i and the j-th character of B_i are 1
• 1 \leq T_q \leq N (1 \leq q \leq Q)
• 0 \leq Y_q \leq K (1 \leq q \leq Q)
• All inputs are integers or strings in the specified format

Sample Input 1

3 3 4
010
2 1 2
010 000 100
100 000 001
000 001 010
2 3
2 1
1 0
1 2

Sample Output 1

0
1
0
1

Sample Input 2

2 2 3
00
1 2
00 00 10
10 10 01
2 1
1 0
2 0

Sample Output 2

0
0
0

Sample Input 3

6 5 8
10100
3 2 3 4 3 2
10000 00010 01001
00100 00000 10010
00000 01000 00101
01001 10000 00011
00010 00100 11000
00000 00001 01110
3 4
6 1
1 2
4 5
5 0
2 3
3 2
6 2

Sample Output 3

0
0
0
0
0
0
0
0

Sample Input 4

9 9 12
101011001
5 4 6 5 3 4 5 4 6
100000001 000100000 010010000
000010000 001000000 100000100
010000000 000000010 001001000
000000100 100000000 000110001
001000010 000010000 010000011
000100000 000001000 101000000
000000000 010000001 000001110
100010000 000000100 001000101
000001001 001000000 110000010
1 4
9 5
5 6
3 3
7 7
2 2
8 4
4 1
6 5
1 5
9 0
5 3

Sample Output 4

0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 1 1
0
0
0 0 1
1 1

Sample Output 5

1

Problem Statement

Takahashi has arranged N white and black stones in a row.

The color of the i-th stone from the left is represented by the i-th character of the string S, where W corresponds to a white stone and B corresponds to a black stone.

A contiguous interval [l, r] (1 \leq l \leq r \leq N) refers to the sequence of stones from the l-th to the r-th from the left.

Consider taking out all the stones in a contiguous interval and rearranging them in a row in any order you like. If there exists an arrangement such that every two adjacent stones have different colors, we call that contiguous interval a good interval.

In particular, a contiguous interval of length 1 is always a good interval.

Aoki asks Q questions.

In the i-th question, integers L_i, R_i are given.

For each question, find the number of good intervals among the contiguous intervals [l, r] satisfying L_i \leq l \leq r \leq R_i.

Constraints

• 1 \leq N \leq 5 \times 10^4
• 1 \leq Q \leq 5 \times 10^4
• S is a string of length N consisting only of W and B
• 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
• N, Q, L_i, R_i are all integers

Sample Input 1

5 4
WBWBW
1 5
2 4
1 1
3 5

Sample Output 1

15
6
1
6

Sample Input 2

6 5
WWWWWW
1 6
1 3
2 2
3 6
5 6

Sample Output 2

6
3
1
4
2

Sample Input 3

18 8
WWBBWBWBBWWBWBWBWW
1 18
1 6
3 10
5 15
8 18
2 2
7 13
11 17

Sample Output 3

145
18
28
61
55
1
25
28

Sample Input 4

50 15
WBWBWBBBWWBBWBWBWWWBBBWBWBBWBWWBWBWBBWWBWBWBWWBBBW
1 50
1 10
11 20
21 30
31 40
41 50
5 25
10 35
15 45
2 49
7 7
18 22
24 37
33 50
3 14

Sample Output 4

875
41
39
42
51
45
171
270
397
809
1
10
90
146
52

Sample Input 5

1 1
B
1 1

Sample Output 5

1