Problem Statement

There are N children, numbered 1, 2, ..., N.

Snuke has decided to distribute x sweets among them. He needs to give out all the x sweets, but some of the children may get zero sweets.

For each i (1 \leq i \leq N), Child i will be happy if he/she gets exactly a_i sweets. Snuke is trying to maximize the number of happy children by optimally distributing the sweets. Find the maximum possible number of happy children.

Constraints

• All values in input are integers.
• 2 \leq N \leq 100
• 1 \leq x \leq 10^9
• 1 \leq a_i \leq 10^9

Sample Input 1

3 70
20 30 10

Sample Output 1

2

One optimal way to distribute sweets is (20, 30, 20).

Sample Input 2

3 10
20 30 10

Sample Output 2

1

The optimal way to distribute sweets is (0, 0, 10).

Sample Input 3

4 1111
1 10 100 1000

Sample Output 3

4

The optimal way to distribute sweets is (1, 10, 100, 1000).

Sample Input 4

2 10
20 20

Sample Output 4

0

No children will be happy, no matter how the sweets are distributed.

Problem Statement

Snuke has decided to use a robot to clean his room.

There are N pieces of trash on a number line. The i-th piece from the left is at position x_i. We would like to put all of them in a trash bin at position 0.

For the positions of the pieces of trash, 0 < x_1 < x_2 < ... < x_{N} \leq 10^{9} holds.

The robot is initially at position 0. It can freely move left and right along the number line, pick up a piece of trash when it comes to the position of that piece, carry any number of pieces of trash and put them in the trash bin when it comes to position 0. It is not allowed to put pieces of trash anywhere except in the trash bin.

The robot consumes X points of energy when the robot picks up a piece of trash, or put pieces of trash in the trash bin. (Putting any number of pieces of trash in the trash bin consumes X points of energy.) Also, the robot consumes (k+1)^{2} points of energy to travel by a distance of 1 when the robot is carrying k pieces of trash.

Find the minimum amount of energy required to put all the N pieces of trash in the trash bin.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 0 < x_1 < ... < x_N \leq 10^9
• 1 \leq X \leq 10^9
• All values in input are integers.

Partial Scores

• 400 points will be awarded for passing the test set satisfying N \leq 2000.

Sample Input 1

2 100
1 10

Sample Output 1

355

• Travel to position 10 by consuming 10 points of energy.
• Pick up the piece of trash by consuming 100 points of energy.
• Travel to position 1 by consuming 36 points of energy.
• Pick up the piece of trash by consuming 100 points of energy.
• Travel to position 0 by consuming 9 points of energy.
• Put the two pieces of trash in the trash bin by consuming 100 points of energy.

This strategy consumes a total of 10+100+36+100+9+100=355 points of energy.

Sample Input 2

5 1
1 999999997 999999998 999999999 1000000000

Sample Output 2

19999999983

Sample Input 3

10 8851025
38 87 668 3175 22601 65499 90236 790604 4290609 4894746

Sample Output 3

150710136

Sample Input 4

16 10
1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408

Sample Output 4

3256017715

Problem Statement

You are given an undirected graph consisting of N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M. In addition, each vertex has a label, A or B. The label of Vertex i is s_i. Edge i bidirectionally connects vertex a_i and b_i.

The phantom thief Nusook likes to choose some vertex as the startpoint and traverse an edge zero or more times. Today, he will make a string after traveling as above, by placing the labels of the visited vertices in the order visited, beginning from the startpoint.

For example, in a graph where Vertex 1 has the label A and Vertex 2 has the label B, if Nusook travels along the path 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 2, the resulting string is ABABB.

Determine if Nusook can make all strings consisting of A and B.

Constraints

• 2 \leq N \leq 2 \times 10^{5}
• 1 \leq M \leq 2 \times 10^{5}
• |s| = N
• s_i is A or B.
• 1 \leq a_i, b_i \leq N
• The given graph may NOT be simple or connected.

Sample Input 1

2 3
AB
1 1
1 2
2 2

Sample Output 1

Yes

• Since Nusook can visit Vertex 1 and Vertex 2 in any way he likes, he can make all strings consisting of A and B.

Sample Input 2

4 3
ABAB
1 2
2 3
3 1

Sample Output 2

No

• For example, Nusook cannot make BB.
• The given graph may not be connected.

Sample Input 3

13 23
ABAAAABBBBAAB
7 1
10 6
1 11
2 10
2 8
2 11
11 12
8 3
7 12
11 2
13 13
11 9
4 1
9 7
9 6
8 13
8 6
4 10
8 7
4 3
2 1
8 12
6 9

Sample Output 3

Yes

Sample Input 4

13 17
BBABBBAABABBA
7 1
7 9
11 12
3 9
11 9
2 1
11 5
12 11
10 8
1 11
1 8
7 7
9 10
8 8
8 12
6 2
13 11

Sample Output 4

No

Problem Statement

You are given an integer N.

Construct any one N-by-N matrix a that satisfies the conditions below. It can be proved that a solution always exists under the constraints of this problem.

• 1 \leq a_{i,j} \leq 10^{15}
• a_{i,j} are pairwise distinct integers.
• There exists a positive integer m such that the following holds: Let x and y be two elements of the matrix that are vertically or horizontally adjacent. Then, {\rm max}(x,y) {\rm mod} {\rm min}(x,y) is always m.

Constraints

• 2 \leq N \leq 500

Sample Input 1

2

Sample Output 1

4 7
23 10

• For any two elements x and y that are vertically or horizontally adjacent, {\rm max}(x,y) {\rm mod} {\rm min}(x,y) is always 3.

Problem Statement

There is a string s consisting of a and b. Snuke can perform the following two kinds of operation any number of times in any order:

• Choose an occurrence of aa as a substring, and replace it with b.
• Choose an occurrence of bb as a substring, and replace it with a.

How many strings s can be obtained by this sequence of operations? Find the count modulo 10^9 + 7.

Constraints

• 1 \leq |s| \leq 10^5
• s consists of a and b.

Sample Input 1

aaaa

Sample Output 1

6

Six strings can be obtained:

• aaaa
• aab
• aba
• baa
• bb
• a

Sample Input 2

aabb

Sample Output 2

5

Five strings can be obtained:

• aabb
• aaa
• bbb
• ab
• ba

Sample Input 3

ababababa

Sample Output 3

1

Snuke cannot perform any operation.

Sample Input 4

babbabaaba

Sample Output 4

35

Problem Statement

Snuke has found two trees A and B, each with N vertices numbered 1 to N. The i-th edge of A connects Vertex a_i and b_i, and the j-th edge of B connects Vertex c_j and d_j. Also, all vertices of A are initially painted white.

Snuke would like to perform the following operation on A zero or more times so that A coincides with B:

• Choose a leaf vertex that is painted white. (Let this vertex be v.)
• Remove the edge incident to v, and add a new edge that connects v to another vertex.
• Paint v black.

Determine if A can be made to coincide with B, ignoring color. If the answer is yes, find the minimum number of operations required.

You are given T cases of this kind. Find the answer for each of them.

Constraints

• 1 \leq T \leq 20
• 3 \leq N \leq 50
• 1 \leq a_i,b_i,c_i,d_i \leq N
• All given graphs are trees.

Sample Input 1

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

Sample Output 1

1
-1

• The graph in each case is shown below.
• In case 1, A can be made to coincide with B by choosing Vertex 1, removing the edge connecting 1 and 2, and adding an edge connecting 1 and 3. Note that Vertex 2 is not a leaf vertex and thus cannot be chosen.

Sample Input 2

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

Sample Output 2

6
0
7

• A may coincide with B from the beginning.