Problem Statement

There are 3N participants in AtCoder Group Contest. The strength of the i-th participant is represented by an integer a_i. They will form N teams, each consisting of three participants. No participant may belong to multiple teams.

The strength of a team is defined as the second largest strength among its members. For example, a team of participants of strength 1, 5, 2 has a strength 2, and a team of three participants of strength 3, 2, 3 has a strength 3.

Find the maximum possible sum of the strengths of N teams.

Constraints

• 1 ≤ N ≤ 10^5
• 1 ≤ a_i ≤ 10^{9}
• a_i are integers.

Sample Input 1

2
5 2 8 5 1 5

Sample Output 1

10

The following is one formation of teams that maximizes the sum of the strengths of teams:

• Team 1: consists of the first, fourth and fifth participants.
• Team 2: consists of the second, third and sixth participants.

Sample Input 2

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 2

10000000000

The sum of the strengths can be quite large.

Problem Statement

Squid loves painting vertices in graphs.

There is a simple undirected graph consisting of N vertices numbered 1 through N, and M edges. Initially, all the vertices are painted in color 0. The i-th edge bidirectionally connects two vertices a_i and b_i. The length of every edge is 1.

Squid performed Q operations on this graph. In the i-th operation, he repaints all the vertices within a distance of d_i from vertex v_i, in color c_i.

Find the color of each vertex after the Q operations.

Constraints

• 1 ≤ N,M,Q ≤ 10^5
• 1 ≤ a_i,b_i,v_i ≤ N
• a_i ≠ b_i
• 0 ≤ d_i ≤ 10
• 1 ≤ c_i ≤10^5
• d_i and c_i are all integers.
• There are no self-loops or multiple edges in the given graph.

Partial Score

• 200 points will be awarded for passing the testset satisfying 1 ≤ N,M,Q ≤ 2{,}000.

Sample Input 1

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

Sample Output 1

2
2
2
2
2
1
0

Initially, each vertex is painted in color 0. In the first operation, vertices 5 and 6 are repainted in color 1. In the second operation, vertices 1, 2, 3, 4 and 5 are repainted in color 2.

Sample Input 2

14 10
1 4
5 7
7 11
4 10
14 7
14 3
6 14
8 11
5 13
8 3
8
8 6 2
9 7 85
6 9 3
6 7 5
10 3 1
12 9 4
9 6 6
8 2 3

Sample Output 2

1
0
3
1
5
5
3
3
6
1
3
4
5
3

The given graph may not be connected.

Problem Statement

We will call a string x good if it satisfies the following condition:

• Condition: x can be represented as a concatenation of two copies of another string y of length at least 1.

For example, aa and bubobubo are good; an empty string, a, abcabcabc and abba are not good.

Eagle and Owl created a puzzle on good strings. Find one string s that satisfies the following conditions. It can be proved that such a string always exists under the constraints in this problem.

• 1 ≤ |s| ≤ 200
• Each character of s is one of the 100 characters represented by the integers 1 through 100.
• Among the 2^{|s|} subsequences of s, exactly N are good strings.

Constraints

• 1 ≤ N ≤ 10^{12}

Sample Input 1

7

Sample Output 1

4
1 1 1 1

There are two good strings that appear as subsequences of s: (1,1) and (1,1,1,1). There are six occurrences of (1,1) and one occurrence of (1,1,1,1), for a total of seven.

Sample Input 2

299

Sample Output 2

23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10

Problem Statement

Snuke arranged N colorful balls in a row. The i-th ball from the left has color c_i and weight w_i.

He can rearrange the balls by performing the following two operations any number of times, in any order:

• Operation 1: Select two balls with the same color. If the total weight of these balls is at most X, swap the positions of these balls.
• Operation 2: Select two balls with different colors. If the total weight of these balls is at most Y, swap the positions of these balls.

How many different sequences of colors of balls can be obtained? Find the count modulo 10^9 + 7.

Constraints

• 1 ≤ N ≤ 2 × 10^5
• 1 ≤ X, Y ≤ 10^9
• 1 ≤ c_i ≤ N
• 1 ≤ w_i ≤ 10^9
• X, Y, c_i, w_i are all integers.

Sample Input 1

4 7 3
3 2
4 3
2 1
4 4

Sample Output 1

2

• The sequence of colors (2,4,3,4) can be obtained by swapping the positions of the first and third balls by operation 2.
• It is also possible to swap the positions of the second and fourth balls by operation 1, but it does not affect the sequence of colors.

Sample Input 2

1 1 1
1 1

Sample Output 2

1

Sample Input 3

21 77 68
16 73
16 99
19 66
2 87
2 16
7 17
10 36
10 68
2 38
10 74
13 55
21 21
3 7
12 41
13 88
18 6
2 12
13 87
1 9
2 27
13 15

Sample Output 3

129729600

Problem Statement

There are N oases on a number line. The coordinate of the i-th oases from the left is x_i.

Camel hopes to visit all these oases. Initially, the volume of the hump on his back is V. When the volume of the hump is v, water of volume at most v can be stored. Water is only supplied at oases. He can get as much water as he can store at a oasis, and the same oasis can be used any number of times.

Camel can travel on the line by either walking or jumping:

• Walking over a distance of d costs water of volume d from the hump. A walk that leads to a negative amount of stored water cannot be done.
• Let v be the amount of water stored at the moment. When v>0, Camel can jump to any point on the line of his choice. After this move, the volume of the hump becomes v/2 (rounded down to the nearest integer), and the amount of stored water becomes 0.

For each of the oases, determine whether it is possible to start from that oasis and visit all the oases.

Constraints

• 2 ≤ N,V ≤ 2 × 10^5
• -10^9 ≤ x_1 < x_2 < ... < x_N ≤ 10^9
• V and x_i are all integers.

Sample Input 1

3 2
1 3 6

Sample Output 1

Possible
Possible
Possible

It is possible to start from the first oasis and visit all the oases, as follows:

• Walk from the first oasis to the second oasis. The amount of stored water becomes 0.
• Get water at the second oasis. The amount of stored water becomes 2.
• Jump from the second oasis to the third oasis. The amount of stored water becomes 0, and the volume of the hump becomes 1.

Sample Input 2

7 2
-10 -4 -2 0 2 4 10

Sample Output 2

Impossible
Possible
Possible
Possible
Possible
Possible
Impossible

A oasis may be visited any number of times.

Sample Input 3

16 19
-49 -48 -33 -30 -21 -14 0 15 19 23 44 52 80 81 82 84

Sample Output 3

Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Possible
Impossible
Impossible
Impossible
Impossible

Problem Statement

Snuke received an integer sequence a of length 2N-1.

He arbitrarily permuted the elements in a, then used it to construct a new integer sequence b of length N, as follows:

• b_1 = the median of (a_1)
• b_2 = the median of (a_1, a_2, a_3)
• b_3 = the median of (a_1, a_2, a_3, a_4, a_5)
• :
• b_N = the median of (a_1, a_2, a_3, ..., a_{2N-1})

How many different sequences can be obtained as b? Find the count modulo 10^{9} + 7.

Constraints

• 1 ≤ N ≤ 50
• 1 ≤ a_i ≤ 2N-1
• a_i are integers.

Sample Input 1

2
1 3 2

Sample Output 1

3

There are three sequences that can be obtained as b: (1,2), (2,2) and (3,2). Each of these can be constructed from (1,2,3), (2,1,3) and (3,1,2), respectively.

Sample Input 2

4
1 3 2 3 2 4 3

Sample Output 2

16

Sample Input 3

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

Sample Output 3

911828634

Print the count modulo 10^{9} + 7.