Problem Statement

A string of length 6 consisting of lowercase English letters is said to be coffee-like if and only if its 3-rd and 4-th characters are equal and its 5-th and 6-th characters are also equal.
Given a string S, determine whether it is coffee-like.

Constraints

• S is a string of length 6 consisting of lowercase English letters.

Sample Input 1

sippuu

Sample Output 1

Yes

In sippuu, the 3-rd and 4-th characters are equal, and the 5-th and 6-th characters are also equal.

Sample Input 2

iphone

Sample Output 2

No

Sample Input 3

coffee

Sample Output 3

Yes

Problem Statement

Takahashi loves gold coins. He gains 1000 happiness points for each 500-yen coin he has and gains 5 happiness points for each 5-yen coin he has. (Yen is the currency of Japan.)

Takahashi has X yen. If he exchanges his money so that he will gain the most happiness points, how many happiness points will he earn?

(We assume that there are six kinds of coins available: 500-yen, 100-yen, 50-yen, 10-yen, 5-yen, and 1-yen coins.)

Constraints

• 0 \leq X \leq 10^9
• X is an integer.

Sample Input 1

1024

Sample Output 1

2020

By exchanging his money so that he gets two 500-yen coins and four 5-yen coins, he gains 2020 happiness points, which is the maximum number of happiness points that can be earned.

Sample Input 2

0

Sample Output 2

0

He is penniless - or yenless.

Sample Input 3

1000000000

Sample Output 3

2000000000

He is a billionaire - in yen.

Problem Statement

There is a circular pond with a perimeter of K meters, and N houses around them.

The i-th house is built at a distance of A_i meters from the northmost point of the pond, measured clockwise around the pond.

When traveling between these houses, you can only go around the pond.

Find the minimum distance that needs to be traveled when you start at one of the houses and visit all the N houses.

Constraints

• 2 \leq K \leq 10^6
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_1 < ... < A_N < K
• All values in input are integers.

Sample Input 1

20 3
5 10 15

Sample Output 1

10

If you start at the 1-st house and go to the 2-nd and 3-rd houses in this order, the total distance traveled will be 10.

Sample Input 2

20 3
0 5 15

Sample Output 2

10

If you start at the 2-nd house and go to the 1-st and 3-rd houses in this order, the total distance traveled will be 10.

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

• For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.
• There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

• Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

• 3 \leq N \leq 2 \times 10^3
• 1 \leq X,Y \leq N
• X+1 < Y
• All values in input are integers.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:



There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).
There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).
There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).
There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0

Problem Statement

You are going to eat X red apples and Y green apples.
You have A red apples of deliciousness p_1,p_2, \dots, p_A, B green apples of deliciousness q_1,q_2, \dots, q_B, and C colorless apples of deliciousness r_1,r_2, \dots, r_C.
Before eating a colorless apple, you can paint it red or green, and it will count as a red or green apple, respectively.
From the apples above, you will choose the apples to eat while making the sum of the deliciousness of the eaten apples as large as possible.
Find the maximum possible sum of the deliciousness of the eaten apples that can be achieved when optimally coloring zero or more colorless apples.

Constraints

• 1 \leq X \leq A \leq 10^5
• 1 \leq Y \leq B \leq 10^5
• 1 \leq C \leq 10^5
• 1 \leq p_i \leq 10^9
• 1 \leq q_i \leq 10^9
• 1 \leq r_i \leq 10^9
• All values in input are integers.

Sample Input 1

1 2 2 2 1
2 4
5 1
3

Sample Output 1

12

The maximum possible sum of the deliciousness of the eaten apples can be achieved as follows:

• Eat the 2-nd red apple.
• Eat the 1-st green apple.
• Paint the 1-st colorless apple green and eat it.

Sample Input 2

2 2 2 2 2
8 6
9 1
2 1

Sample Output 2

25

Sample Input 3

2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

Sample Output 3

74

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i. For each k=1, ..., N, solve the problem below:

• Consider writing a number on each vertex in the tree in the following manner:
  • First, write 1 on Vertex k.
  • Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:
    • Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.
• Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq a_i,b_i \leq N
• The given graph is a tree.

Sample Input 1

3
1 2
1 3

Sample Output 1

2
1
1

The graph in this input is as follows:

For k=1, there are two ways in which we can write the numbers on the vertices, as follows:

• Writing 1, 2, 3 on Vertex 1, 2, 3, respectively
• Writing 1, 3, 2 on Vertex 1, 2, 3, respectively

Sample Input 2

2
1 2

Sample Output 2

1
1

The graph in this input is as follows:

Sample Input 3

5
1 2
2 3
3 4
3 5

Sample Output 3

2
8
12
3
3

The graph in this input is as follows:

Sample Input 4

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

Sample Output 4

40
280
840
120
120
504
72
72

The graph in this input is as follows: