Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

• There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
• s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

Problem Statement

There are N people numbered 1,2,\ldots,N.

M parties were held. k_i people attended the i-th (1\leq i \leq M) party, and they were People x_{i,1},x_{i,2},\ldots,x_{i,k_i}.

Determine if every two people attended the same party at least once.

Constraints

• 2\leq N \leq 100
• 1\leq M \leq 100
• 2\leq k_i \leq N
• 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
• All values in the input are integers.

Sample Input 1

3 3
2 1 2
2 2 3
2 1 3

Sample Output 1

Yes

Both Person 1 and Person 2 attended the 1-st party.

Both Person 2 and Person 3 attended the 2-nd party.

Both Person 1 and Person 3 attended the 3-rd party.

Therefore, every two people attended the same party at least once, so the answer is Yes.

Sample Input 2

4 2
3 1 2 4
3 2 3 4

Sample Output 2

No

Person 1 and Person 3 did not attend the same party, so the answer is No.

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

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

Problem Statement

Takahashi is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

Problem Statement

Takahashi is having trouble with deciding a username for a service. Write a code to help him.

Find a string X that satisfies all of the following conditions:

• X is obtained by the following procedure:
  • Let S_1', S_2', \ldots,S_N' be a permutation of S_1, S_2, \ldots,S_N. Let X be the concatenation of S_1', (1 or more copies of _), S_2', (1 or more copies of _), \ldots, (1 or more copies of _), and S_N', in this order.
• The length of X is between 3 and 16, inclusive.
• X does not coincide with any of M strings T_1,T_2,\ldots,T_M.

If there is no X that satisfies all of the conditions, print -1 instead.

Constraints

• 1 \leq N \leq 8
• 0 \leq M \leq 10^5
• N and M are integers.
• 1 \leq |S_i| \leq 16
• N-1+\sum{|S_i|} \leq 16
• S_i \neq S_j if i \neq j.
• S_i is a string consisting of lowercase English letters.
• 3 \leq |T_i| \leq 16
• T_i \neq T_j if i \neq j.
• T_i is a string consisting of lowercase English letters and _.

Sample Input 1

1 1
chokudai
chokudai

Sample Output 1

-1

The only string that satisfies the first and second conditions is X= chokudai, but it coincides with T_1.
Thus, there is no X that satisfies all of the conditions, so -1 should be printed.

Sample Input 2

2 2
choku
dai
chokudai
choku_dai

Sample Output 2

dai_choku

Strings like choku__dai (which has two _'s between choku and dai) also satisfy all of the conditions.

Sample Input 3

2 2
chokudai
atcoder
chokudai_atcoder
atcoder_chokudai

Sample Output 3

-1

chokudai__atcoder and atcoder__chokudai (which have two _'s between chokudai and atcoder) have a length of 17, which violates the second condition.

Sample Input 4

4 4
ab
cd
ef
gh
hoge
fuga
____
_ab_cd_ef_gh_

Sample Output 4

ab__ef___cd_gh

The given T_i may contain a string that cannot be obtained by the procedure described in the first condition.