Problem Statement

There are N sightseeing spots on the x-axis, numbered 1, 2, ..., N. Spot i is at the point with coordinate A_i. It costs |a - b| yen (the currency of Japan) to travel from a point with coordinate a to another point with coordinate b along the axis.

You planned a trip along the axis. In this plan, you first depart from the point with coordinate 0, then visit the N spots in the order they are numbered, and finally return to the point with coordinate 0.

However, something came up just before the trip, and you no longer have enough time to visit all the N spots, so you decided to choose some i and cancel the visit to Spot i. You will visit the remaining spots as planned in the order they are numbered. You will also depart from and return to the point with coordinate 0 at the beginning and the end, as planned.

For each i = 1, 2, ..., N, find the total cost of travel during the trip when the visit to Spot i is canceled.

Constraints

• 2 \leq N \leq 10^5
• -5000 \leq A_i \leq 5000 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

3
3 5 -1

Sample Output 1

12
8
10

Spot 1, 2 and 3 are at the points with coordinates 3, 5 and -1, respectively. For each i, the course of the trip and the total cost of travel when the visit to Spot i is canceled, are as follows:

• For i = 1, the course of the trip is 0 \rightarrow 5 \rightarrow -1 \rightarrow 0 and the total cost of travel is 5 + 6 + 1 = 12 yen.
• For i = 2, the course of the trip is 0 \rightarrow 3 \rightarrow -1 \rightarrow 0 and the total cost of travel is 3 + 4 + 1 = 8 yen.
• For i = 3, the course of the trip is 0 \rightarrow 3 \rightarrow 5 \rightarrow 0 and the total cost of travel is 3 + 2 + 5 = 10 yen.

Sample Input 2

5
1 1 1 2 0

Sample Output 2

4
4
4
2
4

Sample Input 3

6
-679 -2409 -3258 3095 -3291 -4462

Sample Output 3

21630
21630
19932
8924
21630
19288

Problem Statement

You are given two integers A and B.

Print a grid where each square is painted white or black that satisfies the following conditions, in the format specified in Output section:

• Let the size of the grid be h \times w (h vertical, w horizontal). Both h and w are at most 100.
• The set of the squares painted white is divided into exactly A connected components.
• The set of the squares painted black is divided into exactly B connected components.

It can be proved that there always exist one or more solutions under the conditions specified in Constraints section. If there are multiple solutions, any of them may be printed.

Notes

Two squares painted white, c_1 and c_2, are called connected when the square c_2 can be reached from the square c_1 passing only white squares by repeatedly moving up, down, left or right to an adjacent square.

A set of squares painted white, S, forms a connected component when the following conditions are met:

• Any two squares in S are connected.
• No pair of a square painted white that is not included in S and a square included in S is connected.

A connected component of squares painted black is defined similarly.

Constraints

• 1 \leq A \leq 500
• 1 \leq B \leq 500

Sample Input 1

2 3

Sample Output 1

3 3
##.
..#
#.#

This output corresponds to the grid below:

Sample Input 2

7 8

Sample Output 2

3 5
#.#.#
.#.#.
#.#.#

Sample Input 3

1 1

Sample Output 3

4 2
..
#.
##
##

Sample Input 4

3 14

Sample Output 4

8 18
..................
..................
....##.......####.
....#.#.....#.....
...#...#....#.....
..#.###.#...#.....
.#.......#..#.....
#.........#..####.

Problem Statement

We have an undirected weighted graph with N vertices and M edges. The i-th edge in the graph connects Vertex U_i and Vertex V_i, and has a weight of W_i. Additionally, you are given an integer X.

Find the number of ways to paint each edge in this graph either white or black such that the following condition is met, modulo 10^9 + 7:

• The graph has a spanning tree that contains both an edge painted white and an edge painted black. Furthermore, among such spanning trees, the one with the smallest weight has a weight of X.

Here, the weight of a spanning tree is the sum of the weights of the edges contained in the spanning tree.

Constraints

• 1 \leq N \leq 1 000
• 1 \leq M \leq 2 000
• 1 \leq U_i, V_i \leq N (1 \leq i \leq M)
• 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
• If i \neq j, then (U_i, V_i) \neq (U_j, V_j) and (U_i, V_i) \neq (V_j, U_j).
• U_i \neq V_i (1 \leq i \leq M)
• The given graph is connected.
• 1 \leq X \leq 10^{12}
• All input values are integers.

Sample Input 1

3 3
2
1 2 1
2 3 1
3 1 1

Sample Output 1

6

Sample Input 2

3 3
3
1 2 1
2 3 1
3 1 2

Sample Output 2

2

Sample Input 3

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

Sample Output 3

0

Sample Input 4

8 10
49
4 6 10
8 4 11
5 8 9
1 8 10
3 8 128773450
7 8 10
4 2 4
3 4 1
3 1 13
5 2 2

Sample Output 4

4

Problem Statement

There are 2^N players, numbered 1, 2, ..., 2^N. They decided to hold a tournament.

The tournament proceeds as follows:

• Choose a permutation of 1, 2, ..., 2^N: p_1, p_2, ..., p_{2^N}.
• The players stand in a row in the order of Player p_1, Player p_2, ..., Player p_{2^N}.
• Repeat the following until there is only one player remaining in the row:
  • Play the following matches: the first player in the row versus the second player in the row, the third player versus the fourth player, and so on. The players who lose leave the row. The players who win stand in a row again, preserving the relative order of the players.
• The last player who remains in the row is the champion.

It is known that, the result of the match between two players can be written as follows, using M integers A_1, A_2, ..., A_M given as input:

• When y = A_i for some i, the winner of the match between Player 1 and Player y (2 \leq y \leq 2^N) will be Player y.
• When y \neq A_i for every i, the winner of the match between Player 1 and Player y (2 \leq y \leq 2^N) will be Player 1.
• When 2 \leq x < y \leq 2^N, the winner of the match between Player x and Player y will be Player x.

The champion of this tournament depends only on the permutation p_1, p_2, ..., p_{2^N} chosen at the beginning. Find the number of permutation p_1, p_2, ..., p_{2^N} chosen at the beginning of the tournament that would result in Player 1 becoming the champion, modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 16
• 0 \leq M \leq 16
• 2 \leq A_i \leq 2^N (1 \leq i \leq M)
• A_i < A_{i + 1} (1 \leq i < M)

Sample Input 1

2 1
3

Sample Output 1

8

Examples of p that satisfy the condition are: [1, 4, 2, 3] and [3, 2, 1, 4]. Examples of p that do not satisfy the condition are: [1, 2, 3, 4] and [1, 3, 2, 4].

Sample Input 2

4 3
2 4 6

Sample Output 2

0

Sample Input 3

3 0

Sample Output 3

40320

Sample Input 4

3 3
3 4 7

Sample Output 4

2688

Sample Input 5

16 16
5489 5490 5491 5492 5493 5494 5495 5497 18993 18995 18997 18999 19000 19001 19002 19003

Sample Output 5

816646464