Problem Statement

You are given three integers A,B,C. Determine whether it is possible to divide these three integers into two or more groups so that these groups have equal sums.

Constraints

• 1 \leq A,B,C \leq 1000
• All input values are integers.

Sample Input 1

3 8 5

Sample Output 1

Yes

For example, by dividing into two groups (3,5) and (8), each group can have the sum 8.

Sample Input 2

2 2 2

Sample Output 2

Yes

By dividing into three groups (2),(2),(2), each group can have the sum 2.

Sample Input 3

1 2 4

Sample Output 3

No

No matter how you divide them into two or more groups, it is not possible to make the sums equal.

Problem Statement

There is a triangle ABC with positive area.
The lengths of the three sides of triangle ABC are a,b,c.

Determine whether triangle ABC is isosceles.

Constraints

• 1 \leq a,b,c \leq 10
• A triangle with side lengths a,b,c exists, and its area is positive.
• a,b,c are integers.

Sample Input 1

4 2 4

Sample Output 1

Yes

Since a=c, triangle ABC is isosceles. Thus, output Yes.

Sample Input 2

3 4 5

Sample Output 2

No

Since the three side lengths of triangle ABC are all different, it is not isosceles. Thus, output No.

Sample Input 3

10 10 10

Sample Output 3

Yes

Note that an equilateral triangle is a kind of isosceles triangle.

Problem Statement

You are given a sequence of non-negative integers A=(A_1,A_2,\dots,A_N) of length N. Find the maximum non-negative integer x that satisfies the following:

• In A, elements greater than or equal to x appear at least x times (including duplicates).

Constraints

• 1 \leq N \leq 100
• 0 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

3
1 2 1

Sample Output 1

1

In A=(1,2,1):

• Elements greater than or equal to 0 appear 3 times.
• Elements greater than or equal to 1 appear 3 times.
• Elements greater than or equal to 2 appear 1 time.
• Elements greater than or equal to 3 appear 0 times.

The maximum non-negative integer that satisfies the condition is 1.

Sample Input 2

7
1 6 2 10 2 3 2

Sample Output 2

3

Problem Statement

There are two grids S and T, each with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell of grids S and T is colored either white or black. Cell (i,j) of S is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies to T.

You may perform the following two types of operations any number of times in any order. Find the minimum number of operations required to make grid S identical to grid T.

• Choose one cell of grid S and change its color.
• Rotate the entire grid S 90 degrees clockwise.

Constraints

• 1 \le N \le 100
• N is an integer.
• Each of S_{i,j} and T_{i,j} is . or #.

Sample Input 1

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

Sample Output 1

2

You can match S to T in two operations as shown below.

Sample Input 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

Sample Output 2

5

Problem Statement

Ringo-san is trying to paint a horse with stripes to make it a zebra.

There are N squares numbered 1 to N arranged in a line.
Initially, all squares are white, and the cost of painting square i black is C_i.

Consider performing the following procedure once to paint some squares black:

• Choose a positive integer x freely.
• Paint square i black for all integers i satisfying 1 \leq i \leq N such that the remainder when (i+x) is divided by 2W is less than W.

Find the minimum total cost to perform this procedure.

You are given T test cases; solve each of them.

Constraints

• 1\leq T \leq 2\times 10^5
• 1\leq N \leq 2\times 10^5
• 1\leq W \leq 2\times 10^5
• 1\leq C_i \leq 10^9
• The sum of N over the T test cases is at most 2\times 10^5.
• The sum of W over the T test cases is at most 2\times 10^5.
• All input values are integers.

Sample Input 1

4
8 2
1 10 10 1 1 10 10 1
8 3
1 10 10 1 1 10 10 1
8 4
1 10 10 1 1 10 10 1
4 100
100000 100000 100000 100000

Sample Output 1

4
12
22
0

In the first test case, if the procedure is executed with x=4, squares 1,4,5,8 are painted black, and the total cost is 4. The total cost cannot be less than 4, so this is the minimum.

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

We have an empty sequence A.
Given Q queries, process them in order.
Each query is of one of the following three types.

• 1 x : Insert x to A.

• 2 x k : Among the elements of A that are less than or equal to x, print the k-th largest value. (k is no more than \bf{5})
  If there are less than k elements of A that are less than or equal to x, then print -1.

• 3 x k : Among the elements of A that are greater than or equal to x, print the k-th smallest value. (k is no more than \bf{5})
  If there are less than k elements of A that are greater than or equal to x, then print -1.

Constraints

• 1\leq Q \leq 2\times 10^5
• 1\leq x\leq 10^{18}
• 1\leq k\leq 5
• All values in input are integers.

Sample Input 1

11
1 20
1 10
1 30
1 20
3 15 1
3 15 2
3 15 3
3 15 4
2 100 5
1 1
2 100 5

Sample Output 1

20
20
30
-1
-1
1

After \text{query}_{1,2,3,4} have been processed, we have A=(20,10,30,20).

For \text{query}_{5,6,7}, the elements of A greater than or equal to 15 are (20,30,20).
The 1-st smallest value of them is 20; the 2-nd is 20; the 3-rd is 30.

Problem Statement

You are given integers N, M and an integer sequence A=(A_1,A_2,\ldots,A_N) of length N where each element is between 1 and M, inclusive.

The following operation is performed 10^{100} times on this integer sequence A:

• Let v be the integer between 1 and M, inclusive, with the fewest occurrences in A. If there are multiple such v, take the smallest among them. Then, append v to the end of A.

You are given Q queries. The i-th query gives an integer X_i, so find the value of A_{X_i} after performing the operation 10^{100} times.

Constraints

• 1\le N,M\le 5\times 10^5
• 1\le A_i \le M
• 1\le Q\le 2\times 10^5
• 1\le X_i \le 10^{18}
• All input values are integers.

Sample Input 1

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

Sample Output 1

1
1
2
3
2
3
1
2

Initially, A=(1,1,2). With each operation, A changes as follows:

• First operation: The counts of 1, 2, 3 in A are 2, 1, 0 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3).
• Second operation: The counts of 1, 2, 3 in A are 2, 1, 1 respectively, so v=2. Append v to the end of A, giving A=(1,1,2,3,2).
• Third operation: The counts of 1, 2, 3 in A are 2, 2, 1 respectively, so v=3. Append v to the end of A, giving A=(1,1,2,3,2,3).
• \vdots

After performing the operation 10^{100} times, A becomes A=(1,1,2,3,2,3,1,2,\ldots).

Sample Input 2

7 30
20 26 3 14 4 4 9
10
31
9
21
23
97
99
30
79
57
3

Sample Output 2

30
2
18
21
7
9
29
19
27
3

Problem Statement

Takahashi is at the origin of a number line. Takahashi wants to reach the goal at coordinate X.

Also, there are N walls and N hammers on the number line.

• At coordinates Y_1,Y_2,\dots,Y_N are walls of types 1,2,\dots,N, respectively.
  • Initially, Takahashi cannot get over the walls.
• At coordinates Z_1,Z_2,\dots,Z_N are hammers of types 1,2,\dots,N, respectively.
  • When he arrives at a coordinate with a hammer, he obtains the hammer.
  • The hammer of type i is dedicated to destroying the wall of type i. After he obtains the hammer of type i, he can destroy the wall of type i and get over it.

Determine if he can reach the goal. If he can, find the minimum distance he travels.

Constraints

• All values in the input are integers.
• 1 \le N \le 1500
• 1 \le |X|,|Y_i|,|Z_i| \le 10^9
• The (2 \times N + 1) coordinates X,Y_i and Z_i are distinct.

Sample Input 1

3 10
-2 8 -5
5 -10 3

Sample Output 1

40

Takahashi can reach the goal by traveling a distance of 40 as follows, which is the minimum possible:

• He starts at coordinate 0.
• He moves to coordinate 3 to obtain the hammer of type 3.
• He moves to coordinate 5 to obtain the hammer of type 1.
• He moves to coordinate -2 to destroy the wall of type 1.
• He moves to coordinate -5 to destroy the wall of type 3.
• He moves to coordinate -10 to obtain the hammer of type 2.
• He moves to coordinate 8 to destroy the wall of type 2.
• He moves to coordinate 10, which is the goal.

Sample Input 2

5 -1
10 -20 30 -40 50
-10 20 -30 40 -50

Sample Output 2

1

It may not be required that he obtains a hammer or destroys a wall to reach the goal.

Sample Input 3

1 100
30
60

Sample Output 3

-1

Takahashi cannot obtain the hammer of type 1, and neither can he reach the goal.

Sample Input 4

4 865942261
703164879 -531670946 -874856231 -700164975
-941120316 599462305 -649785130 665402307

Sample Output 4

4078987507