Problem Statement

Given are two strings S and T consisting of lowercase English letters. Concatenate T and S in this order, without space in between, and print the resulting string.

Constraints

• S and T are strings consisting of lowercase English letters.
• The lengths of S and T are between 1 and 100 (inclusive).

Sample Input 1

oder atc

Sample Output 1

atcoder

When S = oder and T = atc, concatenating T and S in this order results in atcoder.

Sample Input 2

humu humu

Sample Output 2

humuhumu

Problem Statement

Takahashi has A cookies, and Aoki has B cookies. Takahashi will do the following action K times:

• If Takahashi has one or more cookies, eat one of his cookies.
• Otherwise, if Aoki has one or more cookies, eat one of Aoki's cookies.
• If they both have no cookies, do nothing.

In the end, how many cookies will Takahashi and Aoki have, respectively?

Constraints

• 0 \leq A \leq 10^{12}
• 0 \leq B \leq 10^{12}
• 0 \leq K \leq 10^{12}
• All values in input are integers.

Sample Input 1

2 3 3

Sample Output 1

0 2

Takahashi will do the following:

• He has two cookies, so he eats one of them.
• Now he has one cookie left, and he eats it.
• Now he has no cookies left, but Aoki has three, so Takahashi eats one of them.

Thus, in the end, Takahashi will have 0 cookies, and Aoki will have 2.

Sample Input 2

500000000000 500000000000 1000000000000

Sample Output 2

0 0

Watch out for overflows.

Problem Statement

Find the minimum prime number greater than or equal to X.

Notes

A prime number is an integer greater than 1 that cannot be evenly divided by any positive integer except 1 and itself.

For example, 2, 3, and 5 are prime numbers, while 4 and 6 are not.

Constraints

• 2 \le X \le 10^5
• All values in input are integers.

Sample Input 1

20

Sample Output 1

23

The minimum prime number greater than or equal to 20 is 23.

Sample Input 2

2

Sample Output 2

2

X itself can be a prime number.

Sample Input 3

99992

Sample Output 3

100003

Problem Statement

At an arcade, Takahashi is playing a game called RPS Battle, which is played as follows:

• The player plays N rounds of Rock Paper Scissors against the machine. (See Notes for the description of Rock Paper Scissors. A draw also counts as a round.)
• Each time the player wins a round, depending on which hand he/she uses, he/she earns the following score (no points for a draw or a loss):
  • R points for winning with Rock;
  • S points for winning with Scissors;
  • P points for winning with Paper.
• However, in the i-th round, the player cannot use the hand he/she used in the (i-K)-th round. (In the first K rounds, the player can use any hand.)

Before the start of the game, the machine decides the hand it will play in each round. With supernatural power, Takahashi managed to read all of those hands.

The information Takahashi obtained is given as a string T. If the i-th character of T (1 \leq i \leq N) is r, the machine will play Rock in the i-th round. Similarly, p and s stand for Paper and Scissors, respectively.

What is the maximum total score earned in the game by adequately choosing the hand to play in each round?

Notes

In this problem, Rock Paper Scissors can be thought of as a two-player game, in which each player simultaneously forms Rock, Paper, or Scissors with a hand.

• If a player chooses Rock and the other chooses Scissors, the player choosing Rock wins;
• if a player chooses Scissors and the other chooses Paper, the player choosing Scissors wins;
• if a player chooses Paper and the other chooses Rock, the player choosing Paper wins;
• if both players play the same hand, it is a draw.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq K \leq N-1
• 1 \leq R,S,P \leq 10^4
• N,K,R,S, and P are all integers.
• |T| = N
• T consists of r, p, and s.

Sample Input 1

5 2
8 7 6
rsrpr

Sample Output 1

27

The machine will play {Rock, Scissors, Rock, Paper, Rock}.

We can, for example, play {Paper, Rock, Rock, Scissors, Paper} against it to earn 27 points. We cannot earn more points, so the answer is 27.

Sample Input 2

7 1
100 10 1
ssssppr

Sample Output 2

211

Sample Input 3

30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

Sample Output 3

4996

Problem Statement

Takahashi has come to a party as a special guest. There are N ordinary guests at the party. The i-th ordinary guest has a power of A_i.

Takahashi has decided to perform M handshakes to increase the happiness of the party (let the current happiness be 0). A handshake will be performed as follows:

• Takahashi chooses one (ordinary) guest x for his left hand and another guest y for his right hand (x and y can be the same).
• Then, he shakes the left hand of Guest x and the right hand of Guest y simultaneously to increase the happiness by A_x+A_y.

However, Takahashi should not perform the same handshake more than once. Formally, the following condition must hold:

• Assume that, in the k-th handshake, Takahashi shakes the left hand of Guest x_k and the right hand of Guest y_k. Then, there is no pair p, q (1 \leq p < q \leq M) such that (x_p,y_p)=(x_q,y_q).

What is the maximum possible happiness after M handshakes?

Constraints

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

Sample Input 1

5 3
10 14 19 34 33

Sample Output 1

202

Let us say that Takahashi performs the following handshakes:

• In the first handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 4.
• In the second handshake, Takahashi shakes the left hand of Guest 4 and the right hand of Guest 5.
• In the third handshake, Takahashi shakes the left hand of Guest 5 and the right hand of Guest 4.

Then, we will have the happiness of (34+34)+(34+33)+(33+34)=202.

We cannot achieve the happiness of 203 or greater, so the answer is 202.

Sample Input 2

9 14
1 3 5 110 24 21 34 5 3

Sample Output 2

1837

Sample Input 3

9 73
67597 52981 5828 66249 75177 64141 40773 79105 16076

Sample Output 3

8128170

Problem Statement

Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).

Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)

Let the holeyness of S be the number of white vertices contained in S. Find the expected holeyness of S.

Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers, and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible).

Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{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
2 3

Sample Output 1

125000001

If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1.

Otherwise, the holeyness is 0, so the expected holeyness is 1/8.

Since 8 \times 125000001 \equiv 1 \pmod{10^9+7}, we should print 125000001.

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is 3/8.

Since 8 \times 375000003 \equiv 3 \pmod{10^9+7}, we should print 375000003.

Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is 1/4.

Sample Input 4

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

Sample Output 4

570312505