A - BBQ Easy

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

うまく串を組み合わせたとき、N 個の串焼きに刺すことのできる具材の個数の和の最大値はいくらになるでしょうか？

• 1≦N≦100
• 1≦L_i≦100
• L_i は整数である。

### 入力

N
L_1 L_2 ... L_{2N}


### 出力

N 個の串焼きに刺すことのできる具材の個数の和の最大値を出力せよ。

### 入力例 1

2
1 3 1 2


### 出力例 1

3


1 番目と 3 番目、2 番目と 4 番目の串を組にすると、それぞれの串焼きには 1 個、 2 個の具材を刺すことができ、合計 3 個の具材を刺すことができます。

### 入力例 2

5
100 1 2 3 14 15 58 58 58 29


### 出力例 2

135


Score : 200 points

### Problem Statement

Snuke is having a barbeque party.

At the party, he will make N servings of Skewer Meal.

Example of a serving of Skewer Meal

He has a stock of 2N skewers, all of which will be used in Skewer Meal. The length of the i-th skewer is L_i. Also, he has an infinite supply of ingredients.

To make a serving of Skewer Meal, he picks 2 skewers and threads ingredients onto those skewers. Let the length of the shorter skewer be x, then the serving can hold the maximum of x ingredients.

What is the maximum total number of ingredients that his N servings of Skewer Meal can hold, if he uses the skewers optimally?

### Constraints

• 1≦N≦100
• 1≦L_i≦100
• For each i, L_i is an integer.

### Input

The input is given from Standard Input in the following format:

N
L_1 L_2 ... L_{2N}


### Output

Print the maximum total number of ingredients that Snuke's N servings of Skewer Meal can hold.

### Sample Input 1

2
1 3 1 2


### Sample Output 1

3


If he makes a serving using the first and third skewers, and another using the second and fourth skewers, each serving will hold 1 and 2 ingredients, for the total of 3.

### Sample Input 2

5
100 1 2 3 14 15 58 58 58 29


### Sample Output 2

135

B - Mysterious Light

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

このように不思議な光を発射した時、不思議な光は必ず発射した点に戻ってくることが証明できます。 このとき、光の軌跡の長さが全体でいくらになるかを求めて下さい。

### 制約

• 2≦N≦10^{12}
• 1≦X≦N-1
• NX はいずれも整数である。

### 部分点

• N≦1000 を満たすデータセットに正解した場合は、300 点が与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 200 点が与えられる。

### 入力

N X


### 入力例 1

5 2


### 出力例 1

12


Score : 500 points

### Problem Statement

Snuke is conducting an optical experiment using mirrors and his new invention, the rifle of Mysterious Light.

Three mirrors of length N are set so that they form an equilateral triangle. Let the vertices of the triangle be a, b and c.

Inside the triangle, the rifle is placed at the point p on segment ab such that ap = X. (The size of the rifle is negligible.) Now, the rifle is about to fire a ray of Mysterious Light in the direction of bc.

The ray of Mysterious Light will travel in a straight line, and will be reflected by mirrors, in the same ways as "ordinary" light. There is one major difference, though: it will be also reflected by its own trajectory as if it is a mirror! When the ray comes back to the rifle, the ray will be absorbed.

The following image shows the ray's trajectory where N = 5 and X = 2.

It can be shown that the ray eventually comes back to the rifle and is absorbed, regardless of the values of N and X. Find the total length of the ray's trajectory.

### Constraints

• 2≦N≦10^{12}
• 1≦X≦N-1
• N and X are integers.

### Partial Points

• 300 points will be awarded for passing the test set satisfying N≦1000.
• Another 200 points will be awarded for passing the test set without additional constraints.

### Input

The input is given from Standard Input in the following format:

N X


### Output

Print the total length of the ray's trajectory.

### Sample Input 1

5 2


### Sample Output 1

12


Refer to the image in the Problem Statement section. The total length of the trajectory is 2+3+2+2+1+1+1 = 12.

C - Shorten Diameter

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

N 頂点の木があり、頂点には 1 ～ N の番号がついています。N - 1 本の辺について、i (1≦i≦N-1) 本目の辺は頂点 A_i と頂点 B_i を繋いでいます。

この木の直径を K 以下にするために削除する必要のある頂点数の最小値を求めてください。 ただし、頂点を削除した後のグラフは連結になっていなければなりません。

### 制約

• 2≦N≦2000
• 1≦K≦N-1
• 1≦A_i≦N, 1≦B_i≦N
• 与えられるグラフは木である。

### 入力

N K
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}


### 入力例 1

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


### 出力例 1

2


### 入力例 2

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


### 出力例 2

0


すでに直径が K 以下なので、頂点を削除する必要はありません。

Score : 600 points

### Problem Statement

Given an undirected tree, let the distance between vertices u and v be the number of edges on the simple path from u to v. The diameter of a tree is the maximum among the distances between any two vertices. We will call a tree good if and only if its diameter is at most K.

You are given an undirected tree with N vertices numbered 1 through N. For each i (1≦i≦N-1), there is an edge connecting vertices A_i and B_i.

You want to remove zero or more vertices from the tree, so that the resulting tree is good. When a vertex is removed, all incident edges will also be removed. The resulting graph must be connected.

Find the minimum number of vertices that you need to remove in order to produce a good tree.

### Constraints

• 2≦N≦2000
• 1≦K≦N-1
• 1≦A_i≦N, 1≦B_i≦N
• The graph defined by A_i and B_i is a tree.

### Input

The input is given from Standard Input in the following format:

N K
A_1 B_1
A_2 B_2
:
A_{N-1} B_{N-1}


### Output

Print the minimum number of vertices that you need to remove in order to produce a good tree.

### Sample Input 1

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


### Sample Output 1

2


The tree is shown below. Removing vertices 5 and 6 will result in a good tree with the diameter of 2.

### Sample Input 2

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


### Sample Output 2

0


Since the given tree is already good, you do not need to remove any vertex.

D - Arrays and Palindrome

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

• 数列 a に含まれる数の総和は N である。
• 数列 b に含まれる数の総和は N である。
• 数列 a, b に含まれる数はすべて正の整数である。
• 以下の条件を 2 つとも満たす長さ N の文字列は、必ずすべての文字が同じである。
• 先頭の a_1 文字、続く a_2 文字、さらに続く a_3 文字 ... はすべて回文である。
• 先頭の b_1 文字、続く b_2 文字、さらに続く b_3 文字 ... はすべて回文である。

しかしある日、高橋君は数列 a, b を両方ともなくしてしまいました。 幸運なことに、高橋君は数列 a が長さ M の数列 A の並び替えであったことを覚えています。

### 制約

• 1≦N≦10^5
• 1≦M≦100
• 1≦A_i≦10^5
• A_i の総和は N である。

### 入力

N M
A_1 A_2 ... A_M


### 入力例 1

3 2
2 1


### 出力例 1

1 2
1
3


### 入力例 2

6 1
6


### 出力例 2

6
3
1 2 3


### 入力例 3

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


### 出力例 3

Impossible


Score : 1000 points

### Problem Statement

Snuke got a present from his mother on his birthday. The present was a pair of two sequences a and b, consisting of positive integers. They satisfied all of the following properties:

• The sum of all elements of a is N.
• The sum of all elements of b is N.
• Any string of length N that satisfies the following two conditions (1) and (2) will also satisfy the condition (3).
• (1) Any of the following forms a palindrome: the first a_1 letters, the following a_2 letters, the following a_3 letters and so on.
• (2) Any of the following forms a palindrome: the first b_1 letters, the following b_2 letters, the following b_3 letters and so on.
• (3) All N letters are the same.

He was happy, until one day he lost both of the sequences. Now, he only remembers that the sequence a was a permutation of another sequence A of length M.

To bring him happiness again, his mother has decided to give him another pair of sequences a and b that satisfies his favorite properties and is consistent with his memory.

### Constraints

• 1≦N≦10^5
• 1≦M≦100
• 1≦A_i≦10^5
• The sum of all A_i equals N.

### Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 ... A_M


### Output

If there exists a pair of sequences a and b that satisfies the properties and is consistent with Snuke's memory, print three lines. The first line must contain the sequence a, the second line must contain the length of the sequence b, and the third line must contain the sequence b.

If such a pair does not exist (because Snuke's memory is wrong or some other reason), print a single line containing the word Impossible (case-sensitive).

### Sample Input 1

3 2
2 1


### Sample Output 1

1 2
1
3


### Sample Input 2

6 1
6


### Sample Output 2

6
3
1 2 3


### Sample Input 3

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


### Sample Output 3

Impossible

E - BBQ Hard

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

セットを 2 個選び、セット 2 つに含まれる全ての具材を好きな順番で串 2 本に刺すことを考えます。 このとき、作ることの出来る串焼きは何通り考えられるでしょうか？ ただし、串どうしは区別でき、肉どうしや野菜どうしは区別できないものとします。 答えは非常に大きな数になる可能性があるので、10^9+7 で割った余りを求めてください。

### 制約

• 2≦N≦200,000
• 1≦A_i≦2000, 1≦B_i≦2000

### 入力

N
A_1 B_1
A_2 B_2
:
A_N B_N


### 入力例 1

3
1 1
1 1
2 1


### 出力例 1

26


Score : 1400 points

### Problem Statement

Snuke is having another barbeque party.

This time, he will make one serving of Skewer Meal.

He has a stock of N Skewer Meal Packs. The i-th Skewer Meal Pack contains one skewer, A_i pieces of beef and B_i pieces of green pepper. All skewers in these packs are different and distinguishable, while all pieces of beef and all pieces of green pepper are, respectively, indistinguishable.

To make a Skewer Meal, he chooses two of his Skewer Meal Packs, and takes out all of the contents from the chosen packs, that is, two skewers and some pieces of beef or green pepper. (Remaining Skewer Meal Packs will not be used.) Then, all those pieces of food are threaded onto both skewers, one by one, in any order.

(See the image in the Sample section for better understanding.)

In how many different ways can he make a Skewer Meal? Two ways of making a Skewer Meal is different if and only if the sets of the used skewers are different, or the orders of the pieces of food are different. Since this number can be extremely large, find it modulo 10^9+7.

### Constraints

• 2≦N≦200,000
• 1≦A_i≦2000, 1≦B_i≦2000

### Input

The input is given from Standard Input in the following format:

N
A_1 B_1
A_2 B_2
:
A_N B_N


### Output

Print the number of the different ways Snuke can make a serving of Skewer Meal, modulo 10^9+7.

### Sample Input 1

3
1 1
1 1
2 1


### Sample Output 1

26


The 26 ways of making a Skewer Meal are shown below. Gray bars represent skewers, each with a number denoting the Skewer Meal Set that contained the skewer. Brown and green rectangles represent pieces of beef and green pepper, respectively.

F - Wide Swap

Time Limit: 5 sec / Memory Limit: 256 MB

### 問題文

あなたはこの数列に対し、以下のような操作を何度でも行えます。

• 整数 i,j (1 ≦ i < j ≦ N) を選ぶ。
• P_iP_j の値を入れ替える。
• ただしこのとき、j - i ≧ K かつ |P_i - P_j| = 1 を満たしていなければならない。

このような操作によって作ることのできる数列のうち、辞書順最小のものを求めてください。

### 制約

• 2≦N≦500,000
• 1≦K≦N-1
• P1, 2, ..., N の順列である。

### 入力

N K
P_1 P_2 ... P_N


### 入力例 1

4 2
4 2 3 1


### 出力例 1

2
1
4
3


• 4 2 3 1
• 4 1 3 2
• 3 1 4 2
• 2 1 4 3

### 入力例 2

5 1
5 4 3 2 1


### 出力例 2

1
2
3
4
5


### 入力例 3

8 3
4 5 7 8 3 1 2 6


### 出力例 3

1
2
6
7
5
3
4
8


Score : 2000 points

### Problem Statement

You are given a permutation P_1 ... P_N of the set {1, 2, ..., N}.

You can apply the following operation to this permutation, any number of times (possibly zero):

• Choose two indices i,j (1 ≦ i < j ≦ N), such that j - i ≧ K and |P_i - P_j| = 1. Then, swap the values of P_i and P_j.

Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.

### Constraints

• 2≦N≦500,000
• 1≦K≦N-1
• P is a permutation of the set {1, 2, ..., N}.

### Input

The input is given from Standard Input in the following format:

N K
P_1 P_2 ... P_N


### Output

Print the lexicographically smallest permutation that can be obtained.

### Sample Input 1

4 2
4 2 3 1


### Sample Output 1

2
1
4
3


One possible way to obtain the lexicographically smallest permutation is shown below:

• 4 2 3 1
• 4 1 3 2
• 3 1 4 2
• 2 1 4 3

### Sample Input 2

5 1
5 4 3 2 1


### Sample Output 2

1
2
3
4
5


### Sample Input 3

8 3
4 5 7 8 3 1 2 6


### Sample Output 3

1
2
6
7
5
3
4
8