Problem Statement

Takahashi and Aoki are candidates in a student council president election.

N students (student 1, student 2, \ldots, student N) are the voters in this election, and each student initially supports exactly one of the two candidates. The initial support of each student is given by a string S: if the i-th character of S is T, then student i supports Takahashi; if it is A, then student i supports Aoki. In the initial state, both candidates have at least one supporter.

Prior to the election, M speeches are given in order from the 1st to the M-th. In the i-th speech (1 \leq i \leq M), student R_i is persuaded and their support switches to the opposite candidate. That is, if they currently support Takahashi, they switch to supporting Aoki, and if they currently support Aoki, they switch to supporting Takahashi. Note that the same student may be specified in multiple speeches.

Immediately after each speech, it is checked whether either candidate has 0 supporters. If a candidate has 0 supporters, that candidate withdraws from the race, and the other candidate's victory is confirmed. Once a victory is confirmed, no further speeches are given. Note that this check is performed only immediately after each speech, and no check is performed on the initial state.

If a victory is confirmed before all M speeches are completed, output the number of the speech at which it was confirmed. That is, if the victory is confirmed immediately after the i-th speech, output i. If both candidates still have supporters after all M speeches have been completed, output -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• S is a string of length N, where each character is T or A
• S contains at least one T and at least one A
• 1 \leq R_i \leq N (1 \leq i \leq M)
• N, M, R_i are all integers

Sample Input 1

4 4
TTAA
1
2
3
4

Sample Output 1

2

Sample Input 2

3 2
TTA
1
1

Sample Output 2

-1

Sample Input 3

6 5
TTTAAA
4
5
6
1
2

Sample Output 3

3

Sample Input 4

10 8
TTTTAAAAAA
1
2
3
4
1
2
3
4

Sample Output 4

4

Sample Input 5

2 1
TA
1

Sample Output 5

1

Problem Statement

There are N students in Takahashi's class, and the students are assigned attendance numbers from 1 to N.

Currently, the students are standing in a line, and from left to right, the students with attendance numbers p_1, p_2, \ldots, p_N are lined up. The target order specified by the teacher is, from left to right, attendance numbers q_1, q_2, \ldots, q_N.

Takahashi will select one contiguous interval from the line and reverse the order of students within that interval exactly once. Specifically, he chooses integers L, R satisfying 1 \leq L \leq R \leq N, and reverses the order of students from position L to position R. When L = R, the arrangement does not change, but this is still considered as having performed one operation.

Determine whether it is possible to make the arrangement after the operation match the target arrangement q by appropriately choosing L and R.

Constraints

• 1 \leq N \leq 10^6
• (p_1, p_2, \ldots, p_N) is a permutation of (1, 2, \ldots, N)
• (q_1, q_2, \ldots, q_N) is a permutation of (1, 2, \ldots, N)
• All inputs are integers

Sample Input 1

5
1 2 3 4 5
1 4 3 2 5

Sample Output 1

Yes

Sample Input 2

4
1 2 3 4
2 1 4 3

Sample Output 2

No

Sample Input 3

10
3 1 4 2 5 6 7 8 9 10
3 1 8 7 6 5 2 4 9 10

Sample Output 3

Yes

Sample Input 4

25
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 2 3 4 5 6 20 19 18 17 16 15 14 13 12 11 10 9 8 7 21 22 23 24 25

Sample Output 4

Yes

Sample Input 5

1
1
1

Sample Output 5

Yes

Problem Statement

Takahashi is a new high school student who is trying to decide which club activities to join.

There are N club activities at Takahashi's school, and each club activity has an "activity point" value assigned to it. The activity points of the i-th club activity is A_i.

Takahashi can join multiple club activities simultaneously, but he has his own particular preferences.

• He considers a combination "well-balanced" if the total activity points of the chosen club activities is a multiple of K.
• Joining no club activities (the empty combination) is not allowed, as it would make for a lonely high school life.

Takahashi wants to know how many well-balanced combinations of club activities exist.

Among all ways to choose 1 or more club activities from the N available, find the total number of ways such that the sum of activity points of the chosen club activities is a multiple of K. Since the answer can be very large, output it modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq 100
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3

Sample Output 1

3

Sample Input 2

5 4
2 4 6 8 10

Sample Output 2

15

Sample Input 3

10 7
7 14 21 1 2 3 4 5 6 49

Sample Output 3

159

Problem Statement

Takahashi has a lighting panel consisting of a grid with H rows and W columns. The cell at the r-th row from the top and the c-th column from the left is called cell (r, c).

Initially, all cells are turned off. Takahashi performs N operations in order.

In the i-th operation, he toggles the state of all cells whose row is between A_i and B_i (inclusive) and whose column is between C_i and D_i (inclusive). That is, cells that are on are turned off, and cells that are off are turned on.

The state of the lighting panel after all operations are completed is called the final state.

In the final state, each connected component of lit cells under the 4-directional (up, down, left, right) adjacency relation (sharing an edge) is called an island. If there are no lit cells at all, the number of islands is 0.

Aoki asks M questions about the final state. Takahashi must answer each question.

In the j-th question, a rectangular region is specified where the row is between P_j and Q_j (inclusive) and the column is between R_j and S_j (inclusive).

For each question, find the following two values:

1. The number of lit cells within the specified region.
2. The number of islands in the final state that are completely contained within the specified region.

Here, an island is completely contained within a region if all cells belonging to that island are within the specified region.

Note: Islands are defined with respect to the entire panel in the final state. We do NOT recompute connected components within only the region specified by each question.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• 0 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• N + M \leq 10^5
• M \times H \times W \leq 5 \times 10^7
• 1 \leq A_i \leq B_i \leq H (1 \leq i \leq N)
• 1 \leq C_i \leq D_i \leq W (1 \leq i \leq N)
• 1 \leq P_j \leq Q_j \leq H (1 \leq j \leq M)
• 1 \leq R_j \leq S_j \leq W (1 \leq j \leq M)
• All inputs are integers.

Sample Input 1

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

Sample Output 1

11 3
4 0
5 1
1 0

Sample Input 2

3 3 2
1 3 1 3
1 3 1 3
3
1 3 1 3
1 1 1 1
2 3 2 3

Sample Output 2

0 0
0 0
0 0

Sample Input 3

8 10 8
1 3 1 4
2 6 3 8
5 8 1 5
4 4 6 10
1 8 10 10
7 8 7 9
3 5 2 2
6 6 4 10
8
1 8 1 10
1 4 1 5
5 8 1 6
2 7 3 8
1 8 10 10
4 6 6 10
3 3 1 10
7 8 7 9

Sample Output 3

51 8
13 1
16 1
21 1
6 2
6 3
6 0
6 0

Sample Input 4

30 40 20
1 10 1 15
5 20 10 30
12 30 5 25
3 3 1 40
1 30 20 20
8 18 18 35
22 30 30 40
15 25 1 8
2 28 38 40
10 12 12 28
6 24 6 24
1 1 1 40
30 30 1 40
1 30 1 1
1 30 40 40
14 17 14 17
19 21 19 21
4 9 26 33
23 27 12 18
11 29 32 37
15
1 30 1 40
1 10 1 15
5 20 10 30
12 30 5 25
1 30 20 20
8 18 18 35
22 30 30 40
15 25 1 8
2 28 38 40
10 12 12 28
1 5 1 5
26 30 36 40
14 17 14 17
19 21 19 21
7 24 7 34

Sample Output 4

591 48
84 5
170 16
210 15
18 7
70 8
26 4
63 2
46 2
27 4
14 2
6 2
0 0
4 2
231 16

Sample Input 5

1 1 0
1
1 1 1 1

Sample Output 5

0 0

Problem Statement

Takahashi is a gardener in charge of caring for N flowers lined up in a row. The current height of the i-th flower is H_i.

The client's request is: "For any contiguous K flowers, the difference between the maximum height and the minimum height among them should be at most D."

Takahashi can only cut the stems of the flowers (he cannot make them grow). Each flower can be cut to any non-negative integer height, but it cannot be made taller than its original height. That is, the final height H'_i of the i-th flower must be an integer satisfying 0 \leq H'_i \leq H_i.

Since Takahashi wants to keep the flowers as tall as possible, he wants to maximize the sum of the final heights of all flowers, H'_1 + H'_2 + \cdots + H'_N.

Find the maximum possible sum of the final heights of the flowers when they are cut (or left as they are) to satisfy the conditions.

Formally, find the maximum value of \sum_{i=1}^{N} H'_i among all integer sequences H'_1, H'_2, \ldots, H'_N that satisfy the following conditions:

• 0 \leq H'_i \leq H_i for all i (1 \leq i \leq N)
• \max(H'_j, H'_{j+1}, \ldots, H'_{j+K-1}) - \min(H'_j, H'_{j+1}, \ldots, H'_{j+K-1}) \leq D for all j (1 \leq j \leq N - K + 1)

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 0 \leq D \leq 10^9
• 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5 3 2
3 1 4 1 5

Sample Output 1

11

Sample Input 2

6 2 0
2 2 5 5 1 1

Sample Output 2

6

Sample Input 3

12 4 5
10 3 8 15 6 7 20 12 11 4 9 14

Sample Output 3

89

Sample Input 4

30 7 10
25 40 18 33 47 12 29 55 21 36 44 9 31 50 27 16 38 60 22 35 48 14 30 53 26 41 19 37 45 11

Sample Output 4

576

Sample Input 5

1 1 0
1000000000

Sample Output 5

1000000000