AtCoder Regular Contest 165

A - Sum equals LCM

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

正整数 N が与えられます。

2 個以上の (相異なるとは限らない) 正整数 A_1,A_2,\dots,A_n\ (2 \leq n) であって、以下の条件をすべて満たすものが存在するか判定してください。

A_1+A_2+\dots+A_n=N
A_1,A_2,\dots,A_n の最小公倍数は N

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

1 \leq T \leq 100
2 \leq N \leq 10^{9}
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

各ケースは以下の形式で与えられます。

出力

T 行出力してください。i 行目には i 番目のテストケースについて、条件を満たすものが存在する場合は Yes を、存在しない場合は No を出力してください。

入力例 1

出力例 1

Yes
No
No
Yes

1 つ目のテストケースについて、例えば 3 個の正整数 (A_1,A_2,A_3)=(1,2,3) は、 A_1+A_2+A_3=1+2+3=6 であり、 A_1,A_2,A_3 の最小公倍数は 6 であるため条件を満たしています。

2 つ目のテストケースについて、条件を満たすような 2 個以上の正整数は存在しません。

Score : 400 points

Problem Statement

You are given a positive integer N.

Determine if there are two or more (not necessarily distinct) positive integers A_1,A_2,\dots,A_n\ (2 \leq n) that satisfy all of the following conditions:

A_1+A_2+\dots+A_n=N.
The least common multiple of A_1,A_2,\dots,A_n is N.

You have T test cases to solve.

Constraints

1 \leq T \leq 100
2 \leq N \leq 10^{9}
All input values are integers.

Input

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

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

Each case is given in the following format:

Output

Print T lines. The i-th line should contain Yes if some integers satisfy the conditions for the i-th test case, and No otherwise.

Sample Input 1

Sample Output 1

Yes
No
No
Yes

For the first test case, three positive integers (A_1,A_2,A_3)=(1,2,3), for example, have A_1+A_2+A_3=1+2+3=6, and the least common multiple of A_1,A_2,A_3 is 6, satisfying the conditions.

For the second test case, no two or more positive integers satisfy the conditions.

B - Sliding Window Sort 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

1 から N までの整数からなる順列 P=(P_1,P_2,\dots,P_N) と整数 K が与えられます。

順列 P に対して以下のような操作を考えます。

1 \leq i \leq N-K+1 を満たす整数 i を 1 つ選び、 P_i,P_{i+1},\dots,P_{i+K-1} を昇順に並び替える。すなわち、P_i,P_{i+1},\dots,P_{i+K-1} を小さい方から順に並べたものを (x_1,x_2,\dots,x_K) としたとき、各 1 \leq j \leq K に対して P_{i+j-1} を x_j で置き換える。

P に対して上記の操作をちょうど 1 回行うことで得られる順列のうち、辞書式順序最大のものを求めてください。

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。ここで、|S|, |T| はそれぞれ S, T の長さを表します。

|S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。

制約

1 \leq K \leq N \leq 2 \times 10^5
1 \leq P_i \leq N
(P_1,P_2,\dots,P_N) は 1 から N までの整数からなる順列
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N K
P_1 P_2 \dots P_N

出力

P に対して操作をちょうど 1 回行うことで得られる順列のうち、辞書式順序で最大のものを空白区切りで出力してください。

入力例 1

4 3
2 1 4 3

出力例 1

2 1 3 4

i=1 として操作を行うと (P_1,P_2,P_3)=(2,1,4) であり、これを昇順に並び替えると (1,2,4) となります。よって操作によって P_1,P_2,P_3 はそれぞれ 1,2,4 に置き換えられ、 P=(1,2,4,3) となります。同様に i=2 として操作を行うと P は (2,1,3,4) となります。

これらのうち辞書式順序で大きいのは (2,1,3,4) であるため、答えは (2,1,3,4) となります。

入力例 2

5 1
3 1 4 2 5

出力例 2

3 1 4 2 5

入力例 3

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

出力例 3

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

Score : 600 points

Problem Statement

You are given a permutation P=(P_1,P_2,\dots,P_N) of integers from 1 to N and an integer K.

Consider the following operation on the permutation P.

Choose an integer i such that 1 \leq i \leq N-K+1, and sort P_i,P_{i+1},\dots,P_{i+K-1} in ascending order. That is, let (x_1,x_2,\dots,x_K) be the result of arranging P_i,P_{i+1},\dots,P_{i+K-1} in order from smallest to largest, and replace P_{i+j-1} with x_j for each 1 \leq j \leq K.

Find the lexicographically largest permutation that can be obtained by performing the above operation on P exactly once.

What is lexicographical order on sequences?

A sequence S = (S_1,S_2,\ldots,S_{|S|}) is lexicographically smaller than T = (T_1,T_2,\ldots,T_{|T|}) when 1. or 2. below holds. Here, |S| and |T| denotes the lengths of S and T, respectively.

|S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfy both of the following:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).

Constraints

1 \leq K \leq N \leq 2 \times 10^5
1 \leq P_i \leq N
(P_1,P_2,\dots,P_N) is a permutation of integers from 1 to N.
All input values are integers.

Input

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

N K
P_1 P_2 \dots P_N

Output

Print the lexicographically largest permutation that can be obtained by performing the above operation on P exactly once, with spaces in between.

Sample Input 1

4 3
2 1 4 3

Sample Output 1

2 1 3 4

If you perform the operation with i=1, we have (P_1,P_2,P_3)=(2,1,4), and sorting it in ascending order yields (1,2,4). Thus, the operation replaces P_1,P_2,P_3 with 1,2,4, respectively, resulting in P=(1,2,4,3). Similarly, if you perform the operation with i=2, P becomes (2,1,3,4).

The lexicographically greater between them is (2,1,3,4), so the answer is (2,1,3,4).

Sample Input 2

5 1
3 1 4 2 5

Sample Output 2

3 1 4 2 5

Sample Input 3

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

Sample Output 3

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

C - Social Distance on Graph

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点に 1 から N の番号が付いた N 頂点からなる単純連結無向グラフがあります。グラフには重みを持つ辺が M 本あり、i 番目の辺は頂点 A_i,B_i を結ぶ重みが W_i の辺です。また、2 頂点を結ぶ単純パスの重みを、単純パスが含む辺の重みの総和とします。

各頂点に対し赤、青のいずれかの色を塗ります。以下の条件を満たす塗り分け方が存在するような整数 X の最大値を求めてください。

同じ色で塗られた相異なる 2 頂点を結ぶどの単純パスについても、単純パスの重みは X 以上である。

単純パスとは

グラフ G 上の頂点 X,Y に対して、頂点列 v_1,v_2, \ldots, v_k であって、 v_1=X, v_k=Y かつ、1\leq i\leq k-1 に対して v_i と v_{i+1} が辺で結ばれているようなものを頂点 X から頂点 Y への ウォーク と呼びます。さらに、v_1,v_2, \ldots, v_k がすべて異なるようなものを頂点 X から頂点 Y への 単純パス (あるいは単にパス) と呼びます。

制約

3 \leq N \leq 2 \times 10^5
N-1 \leq M \leq \min(\frac{N(N-1)}{2},2 \times 10^5)
1 \leq A_i < B_i \leq N
1 \leq W_i \leq 10^9
与えられるグラフは単純連結無向グラフ
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N M
A_1 B_1 W_1
A_2 B_2 W_2
\vdots
A_M B_M W_M

出力

答えを出力してください。

入力例 1

出力例 1

X=11 としたときに条件を満たす色の塗り方が存在するか考えます。頂点 1,3 を赤、頂点 2 を青で塗った場合、同じ色の頂点を結ぶ単純パス 1-2-3 の重みが 5+6=11 となります。これが同じ色の頂点を結ぶ単純パスの重みの最小値となるのでこの塗り分け方は条件を満たしています。

X が 12 以上のとき、条件を満たす塗り分け方が存在しないことが示せます。よって答えは 11 となります。

入力例 2

10 20
7 10 982219000
3 10 968366179
2 4 992330437
5 6 984414664
2 8 897295423
7 9 155604979
6 8 958833005
2 3 973209957
3 7 985173062
6 10 963895817
2 10 986243534
4 5 721724794
1 3 657562445
1 6 566370694
1 4 988050146
1 9 967817807
4 9 796531581
5 9 983960054
1 10 964450079
8 9 959369491

出力例 2

952136560

入力例 3

10 20
5 6 871895994
8 10 873709822
3 5 454175869
6 10 980782191
2 6 901290987
1 8 298092290
4 8 693116157
4 5 947939338
7 8 934395075
7 9 759563833
5 8 779870031
4 6 919637355
2 9 822858749
4 10 855497285
3 7 954942051
1 2 950411658
4 7 665939990
3 4 634533617
5 7 908372507
1 9 591466693

出力例 3

759563833

Score : 600 points

Problem Statement

There is a simple connected undirected graph with N vertices numbered 1 to N. The graph has M weighted edges, and the i-th edge connects vertices A_i and B_i with a weight of W_i. Additionally, let the weight of a simple path connecting two vertices be the sum of the weights of the edges contained in the simple path.

Let us paint each vertex red or blue. Find the maximum value of the integer X for which there is a coloring that satisfies the following condition:

For every simple path connecting two different vertices painted in the same color, the weight of the simple path is at least X.

What is a simple path?

For vertices X and Y in a graph G, a sequence of vertices v_1,v_2, \ldots, v_k such that v_1=X, v_k=Y, and v_i and v_{i+1} are connected by an edge for each 1\leq i\leq k-1 is called a walk from vertex X to vertex Y. Furthermore, if v_1,v_2, \ldots, v_k are all different, the walk is called a simple path (or just path).

Constraints

3 \leq N \leq 2 \times 10^5
N-1 \leq M \leq \min(\frac{N(N-1)}{2},2 \times 10^5)
1 \leq A_i < B_i \leq N
1 \leq W_i \leq 10^9
The given graph is a simple connected undirected graph.
All input values are integers.

Input

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

N M
A_1 B_1 W_1
A_2 B_2 W_2
\vdots
A_M B_M W_M

Output

Print the answer.

Sample Input 1

Sample Output 1

Consider whether there is a coloring that satisfies the condition for X=11. If we paint vertices 1 and 3 red and vertex 2 blue, the simple path 1-2-3 connecting vertices of the same color has a weight of 5+6=11. This is the minimum weight of a simple path connecting vertices of the same color, so this coloring satisfies the condition.

It can be shown that no coloring satisfies the condition for X=12 or above. Thus, the answer is 11.

Sample Input 2

10 20
7 10 982219000
3 10 968366179
2 4 992330437
5 6 984414664
2 8 897295423
7 9 155604979
6 8 958833005
2 3 973209957
3 7 985173062
6 10 963895817
2 10 986243534
4 5 721724794
1 3 657562445
1 6 566370694
1 4 988050146
1 9 967817807
4 9 796531581
5 9 983960054
1 10 964450079
8 9 959369491

Sample Output 2

952136560

Sample Input 3

10 20
5 6 871895994
8 10 873709822
3 5 454175869
6 10 980782191
2 6 901290987
1 8 298092290
4 8 693116157
4 5 947939338
7 8 934395075
7 9 759563833
5 8 779870031
4 6 919637355
2 9 822858749
4 10 855497285
3 7 954942051
1 2 950411658
4 7 665939990
3 4 634533617
5 7 908372507
1 9 591466693

Sample Output 3

759563833

D - Substring Comparison

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

整数列 X=(X_1,X_2,\dots,X_n) に対し X[L,R] で整数列 (X_L,X_{L+1},\dots,X_{R}) を表します。

整数 N,M と M 個の整数の組 (A_i,B_i,C_i,D_i) が与えられます。

長さ N の整数列 X であって、すべての i=1,2,\dots,M に対して以下の条件を満たすものが存在するか判定してください。

X[A_i,B_i] は X[C_i,D_i] より辞書式順序で小さい。

数列の辞書順とは？

|S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。

制約

2 \leq N \leq 2000
1 \leq M \leq 2000
1 \leq A_i \leq B_i \leq N
1 \leq C_i \leq D_i \leq N
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N M
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_M B_M C_M D_M

出力

条件を満たす整数列が存在する場合は Yes を、存在しない場合は No を出力してください。

入力例 1

4 2
1 3 3 4
4 4 1 2

出力例 1

Yes

例えば X=(1,1,2,1) とすると条件を満たします。

入力例 2

3 2
1 2 2 3
2 2 1 1

出力例 2

No

条件を満たす整数列 X は存在しません。

入力例 3

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

出力例 3

No

Score : 700 points

Problem Statement

For an integer sequence X=(X_1,X_2,\dots,X_n), let X[L,R] denote the integer sequence (X_L,X_{L+1},\dots,X_{R}).

You are given integers N and M, and M quadruples of integers (A_i,B_i,C_i,D_i).

Determine if there is an integer sequence X of length N that satisfies the following condition for every i=1,2,\dots,M:

X[A_i,B_i] is lexicographically smaller than X[C_i,D_i].

What is lexicographical order on sequences?

|S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfy both of the following:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).

Constraints

2 \leq N \leq 2000
1 \leq M \leq 2000
1 \leq A_i \leq B_i \leq N
1 \leq C_i \leq D_i \leq N
All input values are integers.

Input

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

N M
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
\vdots
A_M B_M C_M D_M

Output

If some integer sequence satisfies the condition, print Yes; otherwise, print No.

Sample Input 1

4 2
1 3 3 4
4 4 1 2

Sample Output 1

Yes

For example, X=(1,1,2,1) satisfies the condition.

Sample Input 2

3 2
1 2 2 3
2 2 1 1

Sample Output 2

No

No integer sequence X satisfies the condition.

Sample Input 3

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

Sample Output 3

No

E - Random Isolation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

頂点に 1 から N の番号が付いた N 頂点からなる木があります。 i 番目の辺は頂点 A_i,B_i を結びます。

グラフの連結成分が含む頂点の数がそれぞれ K 以下になるまで以下の操作を行い続けます。

N 個の頂点のうち、K+1 個以上の頂点を含む連結成分に属する頂点を 1 つ一様ランダムに選ぶ。選んだ頂点を端点とする辺をすべて削除する。

操作を行う回数の期待値を \bmod 998244353 で求めてください。

期待値 \text{mod }{998244353} の定義

求める期待値は必ず有理数になることが証明できます。また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。この R を答えてください。

制約

1 \leq K < N \leq 100
1 \leq A_i,B_i \leq N
与えられるグラフは木
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

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

出力

答えを出力してください。

入力例 1

出力例 1

249561090

例えば 1 回目の操作で頂点 2 が選ばれた場合、操作によって全ての辺が削除され、操作後は各連結成分が含む頂点の数はそれぞれ 2 以下であるため操作を終了します。一方 1 回目の操作で頂点 1 が選ばれた場合、操作後頂点 2,3,4 からなる連結成分が残るため、2 回目の操作が行われます。

操作回数の期待値は \frac{7}{4} です。

入力例 2

出力例 2

181196154

Score : 700 points

Problem Statement

There is a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

Let us keep performing the following operation until each connected component of the graph has K or fewer vertices.

From the N vertices, choose one uniformly at random that belongs to a connected component with K+1 or more vertices. Delete all edges with the chosen vertex as an endpoint.

Find the expected value of the number of times the operation is performed, modulo 998244353.

How to print an expected value modulo \text{mod }{998244353}

It can be proved that the sought expected value is always a rational number. Additionally, under the constraints of this problem, it can also be proved that when that value is represented as an irreducible fraction \frac{P}{Q}, we have Q \not \equiv 0 \pmod{998244353}. Thus, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Report this R.

Constraints

1 \leq K < N \leq 100
1 \leq A_i,B_i \leq N
The given graph is a tree.
All input values are integers.

Input

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

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

Output

Print the answer.

Sample Input 1

Sample Output 1

249561090

For example, if the first operation chooses vertex 2, it deletes all edges, after which each connected component has not more than two vertices, so we finish performing the operation. On the other hand, if the first operation chooses vertex 1, there will still be a connected component with vertices 2, 3, and 4, so we perform the second operation.

The expected value of the number of operations is \frac{7}{4}.

Sample Input 2

Sample Output 2

181196154

F - Make Adjacent

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

長さ 2n の整数列 X=(X_1,X_2,\dots,X_{2n}) のうち、すべての i=1,2,\dots,n に対し X_{2i-1}=X_{2i} が成り立つものを 良い数列 と呼びます。

長さ 2N の整数列 A=(A_1,A_2,\dots,A_{2N}) があります。この整数列は各整数 i=1,2,\dots,N をちょうど 2 個ずつ含みます。

A に対して「隣接する 2 項の値を入れ替える」という操作を 0 回以上行うことで、 A を 良い数列 にしたいです。

A を 良い数列 にするのに必要な最小の操作回数を K としたとき、 A に対し操作を K 回行うことで得られる 良い数列 のうち、辞書式順序で最小のものを求めてください。

数列の辞書順とは？

|S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。

制約

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
各整数 i=1,2,\dots,N は A にちょうど 2 個ずつ含まれる
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

N
A_1 A_2 \dots A_{2N}

出力

A に対し操作を K 回行うことで得られる 良い数列 のうち、辞書式順序で最小のものを空白区切りで出力してください。

入力例 1

3
3 2 1 2 3 1

出力例 1

2 2 3 3 1 1

例えば (3,2,1,2,3,1) \rightarrow (3,2,1,3,2,1) \rightarrow (3,2,3,1,2,1) \rightarrow (3,3,2,1,2,1) \rightarrow (3,3,2,2,1,1) というように 4 回の操作で A を 良い数列 にすることができ、これが最小の操作回数です。 4 回の操作では他に A=(2,2,3,3,1,1) とすることもできるので、答えは (2,2,3,3,1,1) となります。

入力例 2

3
1 1 2 2 3 3

出力例 2

1 1 2 2 3 3

入力例 3

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

出力例 3

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

Score : 800 points

Problem Statement

An integer sequence of length 2n, X=(X_1,X_2,\dots,X_{2n}), such that X_{2i-1}=X_{2i} for every i=1,2,\dots,n is called a good sequence.

There is an integer sequence of length 2N, A=(A_1,A_2,\dots,A_{2N}), which contains each integer i=1,2,\dots,N exactly twice.

We want to make A a good sequence by performing the operation of swapping the values of two adjacent terms zero or more times.

Let K be the minimum number of operations we must perform the operation to make A a good sequence. Find the lexicographically smallest good sequence that can be obtained by performing the operations K times on A.

What is lexicographical order on sequences?

|S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfy both of the following:
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq N
A contains each integer i=1,2,\dots,N exactly twice.
All input values are integers.

Input

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

N
A_1 A_2 \dots A_{2N}

Output

Print the lexicographically smallest good sequence that can be obtained by performing the operations K times on A, with spaces in between.

Sample Input 1

3
3 2 1 2 3 1

Sample Output 1

2 2 3 3 1 1

For example, we can perform the operation four times as (3,2,1,2,3,1) \rightarrow (3,2,1,3,2,1) \rightarrow (3,2,3,1,2,1) \rightarrow (3,3,2,1,2,1) \rightarrow (3,3,2,2,1,1) to make A a good sequence. This number is the minimum needed. With four operations, we can also make A=(2,2,3,3,1,1), and the answer is (2,2,3,3,1,1).

Sample Input 2

3
1 1 2 2 3 3

Sample Output 2

1 1 2 2 3 3

Sample Input 3

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

Sample Output 3

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