Problem Statement

Takahashi is a curator at an art museum. The museum wall has tiles arranged in a grid of H rows and W columns, where each tile is a square with side length 1. The tile at the i-th row from the top and the j-th column from the left is denoted as (i, j).

Each tile is either a painting tile (represented by #), which is part of a painting, or a blank tile (represented by .), on which nothing is drawn.

Takahashi wants to install a rectangular frame aligned with the grid's rows and columns that contains all painting tiles. Specifically, he chooses integers r_1, r_2, c_1, c_2 (1 \leq r_1 \leq r_2 \leq H, 1 \leq c_1 \leq c_2 \leq W) and defines a rectangular tile region with (r_1, c_1) as the top-left corner and (r_2, c_2) as the bottom-right corner. All painting tiles must be contained within this rectangular region. That is, if a painting tile (i, j) exists, then r_1 \leq i \leq r_2 and c_1 \leq j \leq c_2 must hold.

This rectangular region contains h = r_2 - r_1 + 1 tiles vertically and w = c_2 - c_1 + 1 tiles horizontally. Since each tile has side length 1, the vertical length of this rectangular region is h, the horizontal length is w, and its perimeter is 2 \times (h + w).

Takahashi wants to find, among all rectangular regions that contain all painting tiles, the one with the minimum perimeter. Output this minimum perimeter.

However, if there are no painting tiles, there is no need to install a frame, so output 0.

Constraints

• 1 \leq H \leq 1000
• 1 \leq W \leq 1000
• H, W are integers
• S_i (1 \leq i \leq H) is a string of length W consisting of # and .

Sample Input 1

5 5
.....
.#.#.
.....
.#.#.
.....

Sample Output 1

12

Sample Input 2

3 4
....
....
....

Sample Output 2

0

Sample Input 3

8 10
..........
#........#
..........
..#..#....
..........
....##....
.......#..
..........

Sample Output 3

32

Problem Statement

Takahashi is going to participate in a "Point Earning Campaign" held on an online shopping site.

In this campaign, N products are available, and purchasing product i (1 \leq i \leq N) earns P_i points.

Takahashi can choose and purchase any products he likes from among these products, but he cannot purchase the same product more than once, and he can purchase at most K products. If K \geq N, he may purchase all products, and it is also allowed to purchase none at all.

Find the maximum total points Takahashi can earn.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9
• All inputs are integers

Sample Input 1

5 3
10 30 20 50 40

Sample Output 1

120

Sample Input 2

4 6
100 200 300 400

Sample Output 2

1000

Sample Input 3

10 5
1000000000 999999999 1 500000000 750000000 250000000 800000000 600000000 900000000 100000000

Sample Output 3

4449999999

Problem Statement

Takahashi explores a cave consisting of N rooms. The rooms are numbered from 1 to N. There are M one-way passages between rooms. Each passage has a fixed direction from one room to another.

For each room, the passages leading out of it have a defined priority order. This priority corresponds to the order given in the input, with passages given earlier having higher priority.

Additionally, each room has a light installed, and the color of the light is either red (0) or blue (1).

Takahashi starts exploring from room 1. Room 1 is marked as visited at the start of the exploration. The exploration follows these rules:

1. Check all passages leading out of the current room one by one in order of decreasing priority. For each passage, if the room at the end of the passage has already been visited, skip that passage and move on to the next one. If the room at the end of the passage is unvisited, proceed to step 2.
2. If the light color of the confirmed unvisited room is the same as the light color of the current room, do not move to that room, skip that passage, and continue checking the next passage. This room does not become visited, and it may be checked again on a different occasion in the future.
3. If the light color of the confirmed unvisited room is different from the light color of the current room, move to that room and mark it as visited. Set the destination room as the new "current room" and restart from step 1.
4. If all passages from the current room have been checked and no destination was found (all were visited or skipped in step 2), or if there are no passages leading out of the current room, perform a backtrack. That is, regardless of passage directions, return to the room you were in immediately before moving to the current room. Set that room as the "current room" and resume checking passages from where it was interrupted, starting from the next passage after the interruption point, continuing the process of steps 1–3.
5. If a backtrack occurs at room 1 (that is, no destination is found from room 1 and there is no room to return to), the exploration ends.

Here, "resuming the interrupted passage check" specifically means the following: Suppose while checking passages in priority order from some room X, you moved to another room Y via step 3. After that (following exploration from room Y onward and backtracks), when you return to room X, you resume checking from the passage with the next priority after the passage to room Y. After resuming, whether each passage's destination room has been visited is judged based on the state at that point in time.

When the exploration ends, output all room numbers that were never visited in ascending order. If all rooms were visited, output COMPLETE.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• C_i \in \{0, 1\} (1 \leq i \leq N)
• 1 \leq U_j, V_j \leq N (1 \leq j \leq M)
• U_j \neq V_j (1 \leq j \leq M)
• The same pair (U_j, V_j) is not given more than once
• The graph is not necessarily connected
• All input values are integers

Sample Input 1

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

Sample Output 1

COMPLETE

Sample Input 2

6 7
0 0 1 1 0 1
1 2
1 3
3 4
3 5
5 6
2 6
4 5

Sample Output 2

2 4

Sample Input 3

12 17
0 1 1 0 1 0 1 0 1 0 0 1
1 3
1 2
1 4
3 5
3 6
6 7
7 8
8 9
9 10
10 11
10 12
12 4
4 5
5 2
2 11
11 3
6 10

Sample Output 3

COMPLETE

Sample Input 4

30 45
0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0
1 3
1 2
1 4
2 5
2 6
5 7
5 8
8 9
8 10
10 11
11 12
12 13
12 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
20 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 1
4 9
4 10
6 13
6 14
7 15
9 16
13 21
21 22
3 6
3 7
11 4
18 2
23 5
25 9
27 13

Sample Output 4

3 6 7 9

Sample Input 5

1 0
0

Sample Output 5

COMPLETE

Problem Statement

At Takahashi's school, N students took a final exam. Each student is assigned a student ID number from 1 to N.

As a result of the exam, student i scored S_i points.

The threshold value is defined as follows. Sort the scores of all N students in non-decreasing order to form a sequence A_1 \le A_2 \le \cdots \le A_N. If multiple students have the same score, each is included as a separate element in the sequence (so the sequence always has length N). The threshold value is the \lceil N/2 \rceil-th value A_{\lceil N/2 \rceil}, where \lceil \cdot \rceil denotes the ceiling function (rounding up). For example, when N = 5, the threshold is the \lceil 5/2 \rceil = 3-rd value, and when N = 4, it is the \lceil 4/2 \rceil = 2-nd value. Note that even if there are multiple elements with the same score, the value of A_{\lceil N/2 \rceil} is uniquely determined regardless of how ties are ordered.

In this exam, students whose scores are strictly less than the threshold value are required to attend supplementary lessons. Students whose scores are equal to the threshold value are not required to attend.

Afterwards, the teacher updates the students' scores Q times due to regrading. Scores may increase or decrease, and the same student's score may be updated multiple times.

In the j-th update (1 \le j \le Q), the score of student T_j is replaced with V_j.

Immediately after each update, determine the number of students who are required to attend supplementary lessons. That is, output the number of students whose scores are strictly less than the threshold value determined from the current scores of all N students.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq T_j \leq N (1 \leq j \leq Q)
• 0 \leq V_j \leq 10^9 (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

5 3
50 30 70 20 60
2 55
4 80
1 10

Sample Output 1

2
2
2

Sample Input 2

4 2
40 40 40 40
1 30
3 30

Sample Output 2

1
0

Sample Input 3

10 5
15 92 35 78 54 12 67 43 89 26
3 80
7 10
1 100
5 20
10 50

Sample Output 3

4
4
4
4
4

Sample Input 4

15 8
100 200 300 400 500 600 700 800 900 1000 50 150 250 350 450
1 999
11 999
5 0
8 0
15 1000
3 500
12 500
7 0

Sample Output 4

7
7
7
7
7
7
6
7

Sample Input 5

1 1
100
1 0

Sample Output 5

0

Problem Statement

Takahashi is in charge of the management system for a company consisting of N employees. The employees are numbered 1 through N.

The company has a clear hierarchy. Employee 1 is the president, and each employee i (2 \leq i \leq N) other than employee 1 has exactly one direct superior P_i. This hierarchy forms a rooted tree with employee 1 as the root.

The distance \mathrm{dist}(u, v) between employee u and employee v is defined as the number of edges on the unique simple path between u and v on the rooted tree. In particular, \mathrm{dist}(u, u) = 0.

The depth \mathrm{depth}(v) of employee v is defined as the distance from the root, \mathrm{dist}(1, v).

Employee v is said to be an ancestor of employee u if v can be reached by starting from u and repeatedly moving to the direct superior 0 or more times toward the root (employee 1). By this definition, employee u themself (0 steps) and employee 1 (tracing all the way to the root) are always ancestors of u.

The lowest common ancestor (LCA) \mathrm{LCA}(S) of a non-empty set of employees S is defined as the employee with the maximum depth (farthest from the root) among all common ancestors of the employees in S. By the properties of rooted trees, such an employee is uniquely determined. If the set contains only one employee, \mathrm{LCA}(\{u\}) = u.

Takahashi needs to process Q "meeting summons queries".

In the j-th query (1 \leq j \leq Q), K_j distinct employees V_{j,1}, V_{j,2}, \ldots, V_{j,K_j} are summoned to a meeting. The facilitator of the meeting is the LCA of the summoned K_j employees. Note that the facilitator may or may not be among the summoned members.

For each query, find Value 1 and Value 2 described below.

Value 1: Find the sum of distances from the facilitator r = \mathrm{LCA}(\{V_{j,1}, V_{j,2}, \ldots, V_{j,K_j}\}) to each of the K_j summoned employees. That is, compute

\sum_{i=1}^{K_j} \mathrm{dist}(r, V_{j,i})

(When K_j = 1, r = V_{j,1}, so Value 1 is 0.)

Value 2: Consider having exactly 1 of the K_j summoned employees be absent and holding the meeting with the remaining K_j - 1 employees. Let r' be the LCA of the remaining K_j - 1 employees as the new facilitator, and compute the sum of distances from r' to each of the remaining K_j - 1 employees. Find the minimum possible sum of distances over all choices of the absent employee (K_j ways).

Letting S_j = \{V_{j,1}, V_{j,2}, \ldots, V_{j,K_j}\}, the value to find is

\min_{1 \leq t \leq K_j} \sum_{\substack{1 \leq i \leq K_j \\ i \neq t}} \mathrm{dist}\!\left(\mathrm{LCA}\!\left(S_j \setminus \{V_{j,t}\}\right),\, V_{j,i}\right)

Note that the facilitator r' of the remaining K_j - 1 employees may or may not be included in the remaining members.

However, if K_j = 1, leaving 1 person out results in an empty set and the LCA cannot be defined, so output -1 as Value 2. When K_j \geq 2, no matter who is absent, the remaining set is non-empty, so the LCA is always uniquely determined.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 1 \leq K_j \leq N (1 \leq j \leq Q)
• 1 \leq V_{j,k} \leq N (1 \leq k \leq K_j)
• V_{j,1}, V_{j,2}, \ldots, V_{j,K_j} are all distinct in each query
• \displaystyle \sum_{j=1}^{Q} K_j \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

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

Sample Output 1

2 1
4 0
0 -1
8 6

Sample Input 2

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

Sample Output 2

0 -1
3 0
7 1
0 -1
6 3

Sample Input 3

15 8
1 1 2 2 3 3 4 4 5 6 6 7 10 10
5 8 9 14 15 10
4 11 12 13 7
6 4 5 6 7 14 15
3 2 8 9
7 1 3 6 11 12 13 15
2 14 15
1 5
8 8 9 10 11 12 13 14 15

Sample Output 3

12 9
7 5
16 12
4 2
16 12
2 0
0 -1
26 22

Sample Input 4

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

Sample Output 4

34 30
19 16
9 5
9 6
12 6
26 22
2 0
0 -1
21 18
28 24
5 2
6 4

Sample Input 5

1 3

1 1
1 1
1 1

Sample Output 5

0 -1
0 -1
0 -1