Problem Statement

One day, tired from going to school, Takahashi wanted to know how many days there were until Saturday.
We know that the day was a weekday, and the name of the day of the week was S in English.
How many days were there until the first Saturday after that day (including Saturday but not the starting day)?

Constraints

• S is Monday, Tuesday, Wednesday, Thursday, or Friday.

Sample Input 1

Wednesday

Sample Output 1

3

It was Wednesday, so there were 3 days until the first Saturday after that day.

Sample Input 2

Monday

Sample Output 2

5

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

• 1 \le M \le N \le 2 \times 10^5
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

15

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

31

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a (not necessarily contiguous) subsequence B=(B_1,B_2,\dots,B_M) of length M of A.

Notes

A subsequence of a number sequence is a sequence that is obtained by removing 0 or more elements from the original number sequence and concatenating the remaining elements without changing the order.

For example, (10,30) is a subsequence of (10,20,30), but (20,10) is not a subsequence of (10,20,30).

Constraints

• 1 \le M \le N \le 2000
• - 2 \times 10^5 \le A_i \le 2 \times 10^5
• All values in input are integers.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

21

When B=(A_1,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times 5 + 2 \times 8 = 21. Since it is impossible to achieve 22 or a larger value, the solution is 21.

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

54

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

You are given a tree with N vertices. The vertices are numbered 1, \dots, N, and the i-th (1 \leq i \leq N - 1) edge connects Vertices A_i and B_i.

We define the distance between Vertices u and v on this tree by the number of edges in the shortest path from Vertex u to Vertex v.

You are given Q queries. In the i-th (1 \leq i \leq Q) query, given integers U_i and K_i, print the index of any vertex whose distance from Vertex U_i is exactly K_i. If there is no such vertex, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq N - 1)
• The given graph is a tree.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq U_i, K_i \leq N \, (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4
1
-1

• Two vertices, Vertices 4 and 5, have a distance exactly 2 from Vertex 2.
• Only Vertex 1 has a distance exactly 3 from Vertex 5.
• No vertex has a distance exactly 3 from Vertex 3.

Sample Input 2

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

Sample Output 2

2
4
10
-1
-1

Problem Statement

You are given an integer sequence A = (A_1, \dots, A_N) of length N.

Find the number, modulo 998244353, of permutations P = (P_1, \dots, P_N) of (1, 2, \dots, N) such that:

• there exist exactly K integers i between 1 and (N-1) (inclusive) such that A_{P_i} \lt A_{P_{i + 1}}.

Constraints

• 2 \leq N \leq 5000
• 0 \leq K \leq N - 1
• 1 \leq A_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4 2
1 1 2 2

Sample Output 1

4

Four permutations satisfy the condition: P = (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3).

Sample Input 2

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

Sample Output 2

697112

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the number, modulo 998244353, of ways to choose an odd number of elements from A so that the sum of the chosen elements equals M.

Two choices are said to be different if there exists an integer i (1 \le i \le N) such that one chooses A_i but the other does not.

Constraints

• 1 \le N \le 10^5
• 1 \le M \le 10^6
• 1 \le A_i \le 10
• All values in input are integers.

Sample Input 1

5 6
1 2 3 3 6

Sample Output 1

3

The following 3 choices satisfy the condition:

• Choosing A_1, A_2, and A_3.
• Choosing A_1, A_2, and A_4.
• Choosing A_5.

Choosing A_3 and A_4 does not satisfy the condition because, although the sum is 6, the number of chosen elements is not odd.

Sample Input 2

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

Sample Output 2

18