Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

• First, choose one real number x.
• Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 0 \le A_i \le 10^9

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

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

Sample Output 2

2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7

Problem Statement

On a two-dimensional plane, Takahashi is initially at point (0, 0), and his initial health is H. M items to recover health are placed on the plane; the i-th of them is placed at (x_i,y_i).

Takahashi will make N moves. The i-th move is as follows.

1. Let (x,y) be his current coordinates. He consumes a health of 1 to move to the following point, depending on S_i, the i-th character of S:

   • (x+1,y) if S_i is R;
   • (x-1,y) if S_i is L;
   • (x,y+1) if S_i is U;
   • (x,y-1) if S_i is D.

2. If Takahashi's health has become negative, he collapses and stops moving. Otherwise, if an item is placed at the point he has moved to, and his health is strictly less than K, then he consumes the item there to make his health K.

Determine if Takahashi can complete the N moves without being stunned.

Constraints

• 1\leq N,M,H,K\leq 2\times 10^5
• S is a string of length N consisting of R, L, U, and D.
• |x_i|,|y_i| \leq 2\times 10^5
• (x_i, y_i) are pairwise distinct.
• All values in the input are integers, except for S.

Sample Input 1

4 2 3 1
RUDL
-1 -1
1 0

Sample Output 1

Yes

Initially, Takahashi's health is 3. We describe the moves below.

• 1-st move: S_i is R, so he moves to point (1,0). His health reduces to 2. Although an item is placed at point (1,0), he do not consume it because his health is no less than K=1.

• 2-nd move: S_i is U, so he moves to point (1,1). His health reduces to 1.

• 3-rd move: S_i is D, so he moves to point (1,0). His health reduces to 0. An item is placed at point (1,0), and his health is less than K=1, so he consumes the item to make his health 1.

• 4-th move: S_i is L, so he moves to point (0,0). His health reduces to 0.

Thus, he can make the 4 moves without collapsing, so Yes should be printed. Note that the health may reach 0.

Sample Input 2

5 2 1 5
LDRLD
0 0
-1 -1

Sample Output 2

No

Initially, Takahashi's health is 1. We describe the moves below.

• 1-st move: S_i is L, so he moves to point (-1,0). His health reduces to 0.

• 2-nd move: S_i is D, so he moves to point (-1,-1). His health reduces to -1. Now that the health is -1, he collapses and stops moving.

Thus, he will be stunned, so No should be printed.

Note that although there is an item at his initial point (0,0), he does not consume it before the 1-st move, because items are only consumed after a move.

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge connects vertices A_i and B_i.

Consider a tree that can be obtained by removing some (possibly zero) edges and vertices from this graph. Find the minimum number of vertices in such a tree that includes all of K specified vertices V_1,\ldots,V_K.

Constraints

• 1 \leq K \leq N \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• 1 \leq V_1 < V_2 < \ldots < V_K \leq N
• The given graph is a tree.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4

The given tree is shown on the left in the figure below. The tree with the minimum number of vertices that includes all of vertices 1,3,5 is shown on the right.

Sample Input 2

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

Sample Output 2

4

Sample Input 3

5 1
1 4
2 3
5 2
1 2
1

Sample Output 3

1

Problem Statement

Given is a positive integer N. Find the value \displaystyle\sum_{i=1}^N \left[ \frac{N}{i} \right].

Here, for a real number x, [x] denotes the largest integer not exceeding x.

Constraints

• 1 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

3

Sample Output 1

5

We have \left[ \frac{3}{1} \right]+\left[ \frac{3}{2} \right]+\left[ \frac{3}{3} \right]=3+1+1=5.

Sample Input 2

10000000000

Sample Output 2

231802823220

Note that the input and output may not fit into a 32-bit integer type.

Problem Statement

For a string S of length N and an integer i\ (0\leq i\leq N), let us define the string f_i(S) as the concatenation of:

• the first i characters of S,
• the reversal of S, and
• the last (N-i) characters of S,

in this order. For instance, if S= abc and i=2, we have f_i(S)= abcbac.

You are given a string T of length 2N. Find a pair of a string S of length N and an integer i\ (0\leq i\leq N) such that f_i(S)=T. If no such pair of S and i exists, report that fact.

Constraints

• 1\leq N \leq 10^6
• N is an integer.
• T is a string of length 2N consisting of lowercase English letters.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if S= abc and i=2, we have f_i(S)= abcbac, which equals T, so you should print abc and 2.

Sample Input 2

4
abababab

Sample Output 2

abab
1

S= abab and i=3 also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

S= agc and i=3 also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of S and i satisfies the condition, print -1.