Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose integers i and j with 1\leq i,j \leq N. Decrease A_i by one and increase A_j by one.

Find the minimum number of operations required to make the difference between the minimum and maximum values of A at most one.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

4
4 7 3 7

Sample Output 1

3

By the following three operations, the difference between the minimum and maximum values of A becomes at most one.

• Choose i=2 and j=3 to make A=(4,6,4,7).
• Choose i=4 and j=1 to make A=(5,6,4,6).
• Choose i=4 and j=3 to make A=(5,6,5,5).

You cannot make the difference between maximum and minimum values of A at most one by less than three operations, so the answer is 3.

Sample Input 2

1
313

Sample Output 2

0

Sample Input 3

10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993

Sample Output 3

2499999974

Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

• 1 \leq N \leq 200
• Each of S and T consists of # and ..
• Each of S and T contains at least one #.

Sample Input 1

5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

4
#...
..#.
..#.
....
#...
#...
..#.
....

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

4
#...
.##.
..#.
....
##..
#...
..#.
....

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

Problem Statement

You are given a sequence of non-negative integers A=(a_1,a_2,\ldots,a_N).

Let S be the set of non-negative integers that can be the sum of K terms in A (with distinct indices).

Find the greatest multiple of D in S. If there is no multiple of D in S, print -1 instead.

Constraints

• 1 \leq K \leq N \leq 100
• 1 \leq D \leq 100
• 0 \leq a_i \leq 10^9
• All values in the input are integers.

Sample Input 1

4 2 2
1 2 3 4

Sample Output 1

6

Here are all the ways to choose two terms in A.

• Choose a_1 and a_2, whose sum is 1+2=3.
• Choose a_1 and a_3, whose sum is 1+3=4.
• Choose a_1 and a_4, whose sum is 1+4=5.
• Choose a_2 and a_3, whose sum is 2+3=5.
• Choose a_2 and a_4, whose sum is 2+4=6.
• Choose a_3 and a_4, whose sum is 3+4=7.

Thus, we have S=\{3,4,5,6,7\}. The greatest multiple of 2 in S is 6, so you should print 6.

Sample Input 2

3 1 2
1 3 5

Sample Output 2

-1

In this example, we have S=\{1,3,5\}. Nothing in S is a multiple of 2, so you should print -1.

Problem Statement

We have a rooted tree with N vertices. The vertices are numbered 1 through N, and the root is Vertex 1.
The i-th edge connects Vertices A_i and B_i.
Vertex i has an integer X_i written on it.

You are given Q queries. For the i-th query, given a pair of integers (V_i,K_i), answer the following question.

• Question: among the integers written on the vertices in the subtree rooted at Vertex V_i, find the K_i-th largest value.

Constraints

• 2 \leq N \leq 10^5
• 0\leq X_i\leq 10^9
• 1\leq A_i,B_i\leq N
• 1\leq Q \leq 10^5
• 1\leq V_i\leq N
• 1\leq K_i\leq 20
• The given graph is a tree.
• The subtree rooted at Vertex V_i has K_i or more vertices.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4
5

The tree given in this input is shown below.

For the 1-st query, the vertices in the subtree rooted at Vertex 1 are Vertices 1, 2, 3, 4, and 5, so print the 2-nd largest value of the numbers written on these vertices, 4.
For the 2-nd query, the vertices in the subtree rooted at Vertex 2 are Vertices 2, 3, and 5, so print the 1-st largest value of the numbers written on these vertices, 5.

Sample Input 2

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

Sample Output 2

9
10

Sample Input 3

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

Sample Output 3

1
10
100
1000

Problem Statement

Given are N distinct points in a two-dimensional plane. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

Let us define the distance between two points i and j be \mathrm{min} (|x_i-x_j|,|y_i-y_j|): the smaller of the difference in the x-coordinates and the difference in the y-coordinates.

Find the maximum distance between two different points.

Constraints

• 2 \leq N \leq 200000
• 0 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 3
3 1
4 10

Sample Output 1

4

The distances between Points 1 and 2, between Points 1 and 3, and between Points 2 and 3 are 2, 4, and 1, respectively, so your output should be 4.

Sample Input 2

4
0 1
0 4
0 10
0 6

Sample Output 2

0

Sample Input 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

Sample Output 3

801