Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

• The 1-st through 125-th ABCs had 4 problems each.
• The 126-th through 211-th ABCs had 6 problems each.
• The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

• 1 \leq N \leq 214
• All values in input are integers.

Sample Input 1

214

Sample Output 1

8

Sample Input 2

1

Sample Output 2

4

Sample Input 3

126

Sample Output 3

6

Problem Statement

How many triples of non-negative integers (a, b, c) satisfy a+b+c \leq S and a \times b \times c \leq T?

Constraints

• 0 \leq S \leq 100
• 0 \leq T \leq 10000
• S and T are integers.

Sample Input 1

1 0

Sample Output 1

4

The triples (a,b,c) satisfying the conditions are (0,0,0), (0,0,1), (0,1,0), and (1,0,0) ― there are four of them.

Sample Input 2

2 5

Sample Output 2

10

Sample Input 3

10 10

Sample Output 3

213

Sample Input 4

30 100

Sample Output 4

2471

Problem Statement

There are N creatures standing in a circle, called Snuke 1, 2, ..., N in counter-clockwise order.

When Snuke i (1 \leq i \leq N) receives a gem at time t, S_i units of time later, it will hand that gem to Snuke i+1 at time t+S_i. Here, Snuke N+1 is Snuke 1.

Additionally, Takahashi will hand a gem to Snuke i at time T_i.

For each i (1 \leq i \leq N), find the time when Snuke i receives a gem for the first time. Assume that it takes a negligible time to hand a gem.

Constraints

• 1 \leq N \leq 200000
• 1 \leq S_i,T_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 1 5
3 10 100

Sample Output 1

3
7
8

We will list the three Snuke's and Takahashi's actions up to time 13 in chronological order.

Time 3: Takahashi hands a gem to Snuke 1.

Time 7: Snuke 1 hands a gem to Snuke 2.

Time 8: Snuke 2 hands a gem to Snuke 3.

Time 10: Takahashi hands a gem to Snuke 2.

Time 11: Snuke 2 hands a gem to Snuke 3.

Time 13: Snuke 3 hands a gem to Snuke 1.

After that, they will continue handing gems, though it will be irrelevant to the answer.

Sample Input 2

4
100 100 100 100
1 1 1 1

Sample Output 2

1
1
1
1

Note that the values S_i and T_i may not be distinct.

Sample Input 3

4
1 2 3 4
1 2 4 7

Sample Output 3

1
2
4
7

Note that a Snuke may perform multiple transactions simultaneously. Particularly, a Snuke may receive gems simultaneously from Takahashi and another Snuke.

Sample Input 4

8
84 87 78 16 94 36 87 93
50 22 63 28 91 60 64 27

Sample Output 4

50
22
63
28
44
60
64
27

Problem Statement

We have a tree with N vertices numbered 1, 2, \dots, N.
The i-th edge (1 \leq i \leq N - 1) connects Vertex u_i and Vertex v_i and has a weight w_i.

For different vertices u and v, let f(u, v) be the greatest weight of an edge contained in the shortest path from Vertex u to Vertex v.

Find \displaystyle \sum_{i = 1}^{N - 1} \sum_{j = i + 1}^N f(i, j).

Constraints

• 2 \leq N \leq 10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq w_i \leq 10^7
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

50

We have f(1, 2) = 10, f(2, 3) = 20, and f(1, 3) = 20, so we should print their sum, or 50.

Sample Input 2

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

Sample Output 2

76

Problem Statement

Solve the following problem for T test cases.

There are 10^9 boxes numbered 1,2,\dots,10^9 and N balls numbered 1,2,\dots,N.
Each box can contain at most one ball.
Determine whether it is possible to put all N balls in the boxes so that the following condition will be satisfied.

• For each integer i from 1 through N, the ball numbered i is in a box numbered between L_i and R_i (inclusive).

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le L_i \le R_i \le 10^9
• The sum of N across the test cases in one input is at most 2 \times 10^5.

Sample Input 1

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

Sample Output 1

Yes
No

This input contains two test cases.

• In the 1-st test case, the following way to put the three balls would satisfy the condition, so we should print Yes.

  • Put Ball 1 in Box 1.
  • Put Ball 2 in Box 2.
  • Put Ball 3 in Box 3.

• In the 2-nd test case, there is no way to put the five balls to satisfy the condition, so we should print No.

Problem Statement

Given is a string S. From this string, Takahashi will make a new string T as follows.

• First, mark one or more characters in S. Here, no two marked characters should be adjacent.
• Next, delete all unmarked characters.
• Finally, let T be the remaining string. Here, it is forbidden to change the order of the characters.

How many strings are there that can be obtained as T? Find the count modulo (10^9 + 7).

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

4

There are four strings that can be obtained as T: a, b, c, and ac.

Marking the first character of S yields a;

marking the second character of S yields b;

marking the third character of S yields c;

marking the first and third characters of S yields ac.

Note that it is forbidden to, for example, mark both the first and second characters.

Sample Input 2

aa

Sample Output 2

1

There is just one string that can be obtained as T, which is a. Note that marking different positions may result in the same string.

Sample Input 3

acba

Sample Output 3

6

There are six strings that can be obtained as T: a, b, c, aa, ab, and ca.

Sample Input 4

chokudai

Sample Output 4

54

Problem Statement

Given are permutations of (1, \dots, N): p = (p_1, \dots, p_N) and q = (q_1, \dots, q_N).

Find the number, modulo (10^9 + 7), of permutations r = (r_1, \dots, r_N) of (1, \dots, N) such that r_i \neq p_i and r_i \neq q_i for every i (1 \leq i \leq N).

Constraints

• 1 \leq N \leq 3000
• 1 \leq p_i, q_i \leq N
• p_i \neq p_j \, (i \neq j)
• q_i \neq q_j \, (i \neq j)
• All values in input are integers.

Sample Input 1

4
1 2 3 4
2 1 4 3

Sample Output 1

4

There are four valid permutations: (3, 4, 1, 2), (3, 4, 2, 1), (4, 3, 1, 2), and (4, 3, 2, 1).

Sample Input 2

3
1 2 3
2 1 3

Sample Output 2

0

The answer may be 0.

Sample Input 3

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

Sample Output 3

803776944

Be sure to print the count modulo (10^9 + 7).

Problem Statement

There is a directed graph with N vertices and M edges.
The vertices are numbered 1, \dots, N, and the i-th edge (1 \leq i \leq M) goes from Vertex A_i to Vertex B_i.

Initially, there are X_i items on Vertex i (1 \leq i \leq N) that someone has lost. K people will collect these items.

The K people will travel in the graph one by one. Each person will do the following.

• Start on Vertex 1. Then, traverse an edge any finite number of times. For each vertex visited (including Vertex 1), collect all items on it if they have not been collected yet.

Find the maximum total number of items that can be collected.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq K \leq 10
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• A_i \neq A_j or B_i \neq B_j, if i \neq j.
• 1 \leq X_i \leq 10^9
• All values in input are integers.

Sample Input 1

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

Sample Output 1

18

The two people can collect 18 items as follows.

• The first person goes 1 \rightarrow 2 \rightarrow 3 \rightarrow 2 and collects the items on Vertices 1, 2, and 3.
• The second person goes 1 \rightarrow 5 and collects the items on Vertex 5.

It is impossible to collect 19 or more items, so we should print 18.

Sample Input 2

3 1 10
2 3
1 100 100

Sample Output 2

1