A - Colorful Transceivers

Time Limit: 2 sec / Memory Limit: 1024 MB

• 1 a,b,c 100
• 1 d 100
• 入力は全て整数

### 入力

a b c d


### 入力例 1

4 7 9 3


### 出力例 1

Yes


AさんとBさんは直接会話可能です。また、BさんとCさんも直接会話可能です。従って Yes を出力してください。

### 入力例 2

100 10 1 2


### 出力例 2

No


この場合は不可能です。

### 入力例 3

10 10 10 1


### 出力例 3

Yes


### 入力例 4

1 100 2 10


### 出力例 4

Yes


Score : 100 points

### Problem Statement

Three people, A, B and C, are trying to communicate using transceivers. They are standing along a number line, and the coordinates of A, B and C are a, b and c (in meters), respectively. Two people can directly communicate when the distance between them is at most d meters. Determine if A and C can communicate, either directly or indirectly. Here, A and C can indirectly communicate when A and B can directly communicate and also B and C can directly communicate.

### Constraints

• 1 a,b,c 100
• 1 d 100
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

a b c d


### Output

If A and C can communicate, print Yes; if they cannot, print No.

### Sample Input 1

4 7 9 3


### Sample Output 1

Yes


A and B can directly communicate, and also B and C can directly communicate, so we should print Yes.

### Sample Input 2

100 10 1 2


### Sample Output 2

No


They cannot communicate in this case.

### Sample Input 3

10 10 10 1


### Sample Output 3

Yes


There can be multiple people at the same position.

### Sample Input 4

1 100 2 10


### Sample Output 4

Yes

B - Exponential

Time Limit: 2 sec / Memory Limit: 1024 MB

• 1 X 1000
• X は整数

### 入力

X


### 出力

X 以下の最大のべき乗数を出力せよ。

### 入力例 1

10


### 出力例 1

9


10 以下のべき乗数は 1,4,8,94 つです。 この内最も大きい 9 を出力してください。

### 入力例 2

1


### 出力例 2

1


### 入力例 3

999


### 出力例 3

961


Score : 200 points

### Problem Statement

You are given a positive integer X. Find the largest perfect power that is at most X. Here, a perfect power is an integer that can be represented as b^p, where b is an integer not less than 1 and p is an integer not less than 2.

### Constraints

• 1 X 1000
• X is an integer.

### Input

Input is given from Standard Input in the following format:

X


### Output

Print the largest perfect power that is at most X.

### Sample Input 1

10


### Sample Output 1

9


There are four perfect powers that are at most 10: 1, 4, 8 and 9. We should print the largest among them, 9.

### Sample Input 2

1


### Sample Output 2

1


### Sample Input 3

999


### Sample Output 3

961

C - K-th Substring

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

ただし、s の substring とは、 s の空でない連続した部分を取り出してできる文字列とします。 例えば、 s = ababc とすると、 a, bab, ababcs の substring ですが、 ac, z, 空文字列 は s の substring ではありません。 また、substring が異なるとは、文字列として異なることを指します。

なお、X = x_{1}x_{2}...x_{n}, Y = y_{1}y_{2}...y_{m} を二つの異なる文字列とするとき、YX の接頭辞であるか、jx_{j} \neq y_{j} であるような最小の整数として x_{j} > y_{j} である場合、そしてその場合に限って XY より辞書順で大きいといいます。

### 制約

• 1 |s| 5000
• s は英小文字からなる
• 1 K 5
• s は異なる substring を K 個以上持つ

### 部分点

• |s| 50 を満たすデータセットに正解した場合は、部分点として 200 点が与えられる。

### 入力

s
K


### 入力例 1

aba
4


### 出力例 1

b


s の substring は a, b, ab, ba, aba5 つです。 このうち 4 番目に小さい b を出力してください。 a2 回カウントしないことに注意してください。

### 入力例 2

atcoderandatcodeer
5


### 出力例 2

andat


### 入力例 3

z
1


### 出力例 3

z


Score : 300 points

### Problem Statement

You are given a string s. Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s. For example, if s = ababc, a, bab and ababc are substrings of s, while ac, z and an empty string are not. Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

### Constraints

• 1 |s| 5000
• s consists of lowercase English letters.
• 1 K 5
• s has at least K different substrings.

### Partial Score

• 200 points will be awarded as a partial score for passing the test set satisfying |s| 50.

### Input

Input is given from Standard Input in the following format:

s
K


### Output

Print the K-th lexicographically smallest substring of K.

### Sample Input 1

aba
4


### Sample Output 1

b


s has five substrings: a, b, ab, ba and aba. Among them, we should print the fourth smallest one, b. Note that we do not count a twice.

### Sample Input 2

atcoderandatcodeer
5


### Sample Output 2

andat


### Sample Input 3

z
1


### Sample Output 3

z

D - Equals

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

1 から N までの整数を並び替えた順列 p_1, p_2, .., p_N があります。 また、 1 以上 N 以下の整数のペアが M 個与えられます。 これらは (x_1,y_1), (x_2,y_2), .., (x_M,y_M) で表されます。 シカの AtCoDeer くんは順列 p に次の操作を好きなだけ行って、 p_i = i となる i (1 i N) の数を最大にしようと考えています。

• 1 j M なる j を選び、 p_{x_j}p_{y_j} をスワップする

### 制約

• 2 N 10^5
• 1 M 10^5
• p1 から N までの整数を並び替えた順列
• 1 x_j,y_j N
• x_j y_j
• i j なら、 \{x_i,y_i\} \{x_j,y_j\}
• 入力は全て整数

### 入力

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M


### 入力例 1

5 2
5 3 1 4 2
1 3
5 4


### 出力例 1

2


j=1 を選んで操作すると、 p1 3 5 4 2 となり、これがベストなので答えは 2 です。

### 入力例 2

3 2
3 2 1
1 2
2 3


### 出力例 2

3


### 入力例 3

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


### 出力例 3

8


### 入力例 4

5 1
1 2 3 4 5
1 5


### 出力例 4

5


Score : 400 points

### Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N. We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M). AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 i N) such that p_i = i is maximized:

• Choose j such that 1 j M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

### Constraints

• 2 N 10^5
• 1 M 10^5
• p is a permutation of integers from 1 through N.
• 1 x_j,y_j N
• x_j y_j
• If i j, \{x_i,y_i\} \{x_j,y_j\}.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M


### Output

Print the maximum possible number of i such that p_i = i after operations.

### Sample Input 1

5 2
5 3 1 4 2
1 3
5 4


### Sample Output 1

2


If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

### Sample Input 2

3 2
3 2 1
1 2
2 3


### Sample Output 2

3


If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal. Note that we may choose the same j any number of times.

### Sample Input 3

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


### Sample Output 3

8


### Sample Input 4

5 1
1 2 3 4 5
1 5


### Sample Output 4

5


We do not have to perform the operation.