Problem Statement

You are given an integer X between 1 and 10, inclusive.

Output the string obtained by deleting only the X-th character from the string HelloWorld.

Constraints

• X is an integer between 1 and 10, inclusive.

Sample Input 1

5

Sample Output 1

HellWorld

Deleting the 5-th character of HelloWorld gives HellWorld. Thus, output HellWorld.

Sample Input 2

9

Sample Output 2

HelloWord

Sample Input 3

1

Sample Output 3

elloWorld

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

• 1 \leq a \lt b \leq 15
• a and b are integers.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

Problem Statement

Locate a piece on a chessboard.

We have a grid with 8 rows and 8 columns of squares. Each of the squares has a 2-character name determined as follows.

• The first character of the name of a square in the 1-st column from the left is a. Similarly, the first character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th column from the left is b, c, d, e, f, g, h, respectively.
• The second character of the name of a square in the 1-st row from the bottom is 1. Similarly, the second character of the name of a square in the 2-nd, 3-rd, \ldots, 8-th row from the bottom is 2, 3, 4, 5, 6, 7, 8, respectively.

For instance, the bottom-left square is named a1, the bottom-right square is named h1, and the top-right square is named h8.

You are given 8 strings S_1,\ldots,S_8, each of length 8, representing the state of the grid.
The j-th character of S_i is * if the square at the i-th row from the top and j-th column from the left has a piece on it, and . otherwise. The character * occurs exactly once among S_1,\ldots,S_8. Find the name of the square that has a piece on it.

Constraints

• S_i is a string of length 8 consisting of . and*.
• The character * occurs exactly once among S_1,\ldots,S_8.

Sample Input 1

........
........
........
........
........
........
........
*.......

Sample Output 1

a1

As explained in the problem statement, the bottom-left square is named a1.

Sample Input 2

........
........
........
........
........
.*......
........
........

Sample Output 2

b3

Problem Statement

There is a rectangular chocolate consisting of H rows and W columns of blocks.

You are given Q queries; process them in order and find the answer to each query. Each query is in one of the following formats:

• Type 1: An integer R is given. Find the number of chocolate blocks in the bottom R rows, then eat them.

• Type 2: An integer C is given. Find the number of chocolate blocks in the rightmost C columns, then eat them.

When the queries are processed in order, the chocolate remains rectangular after each query is processed, and it has at least R + 1 rows immediately before processing a type 1 query and has at least C + 1 columns immediately before processing a type 2 query.

Constraints

• 2 \leq H, W \leq 100
• 1 \leq Q \leq 100
• For type 1 queries, 1 \leq R.
• When the queries are processed in order, the chocolate has at least R + 1 rows immediately before processing a type 1 query.
• For type 2 queries, 1 \leq C.
• When the queries are processed in order, the chocolate has at least C + 1 columns immediately before processing a type 2 query.
• All input values are integers.

Sample Input 1

7 9 5
2 4
1 3
2 1
2 1
1 3

Sample Output 1

28
15
4
4
9

Initially, the chocolate is a rectangle with 7 rows and 9 columns.

For the first query, the number of chocolate blocks in the rightmost 4 columns is 28, so output 28. The chocolate becomes 7 rows and 5 columns.

For the second query, the number of chocolate blocks in the bottom 3 rows is 15, so output 15. The chocolate becomes 4 rows and 5 columns.

For the third query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 4 columns.

For the fourth query, the number of chocolate blocks in the rightmost 1 column is 4, so output 4. The chocolate becomes 4 rows and 3 columns.

For the fifth query, the number of chocolate blocks in the bottom 3 rows is 9, so output 9. The chocolate becomes 1 row and 3 columns.

Problem Statement

There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.

Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.

Constraints

• 1 \leq N,M \leq 2\times 10^5
• -10^9 \leq B_i, W_j \leq 10^9
• All input values are integers.

Sample Input 1

4 3
8 5 -1 3
3 -2 -4

Sample Output 1

19

If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.

Sample Input 2

4 3
5 -10 -2 -5
8 1 4

Sample Output 2

15

If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.

Sample Input 3

3 5
-36 -33 -31
12 12 28 24 27

Sample Output 3

0

It is possible to choose no balls.

Problem Statement

You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).

Find all positive integers L for which the following can occur:

AtCoder Inc. has released a stick-shaped snack called "AtCoderiko." A cup contains one or more AtCoderikos, each of length L. When Takahashi shook the cup, each AtCoderiko ended up in one of the following states:

• It remained as one AtCoderiko of length L.
• It broke into two AtCoderikos whose lengths sum to L. Here, the length of each AtCoderiko is a positive integer.

After shaking the cup, there were N AtCoderikos in the cup, and the length of the i-th AtCoderiko was A_i.

The given input guarantees that there exists at least one positive integer L for which this can occur.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^9
• There exists at least one L satisfying the condition.
• All input values are integers.

Sample Input 1

4
10 5 5 10

Sample Output 1

10 15

If the cup initially contained three AtCoderikos of length 10, and one of them broke into two AtCoderikos of length 5, the condition is satisfied.
If the cup initially contained two AtCoderikos of length 15, and each of them broke into two AtCoderikos of lengths 5 and 10, the condition is satisfied.
No other values of L satisfy the condition.

Sample Input 2

3
4 4 4

Sample Output 2

4

Sample Input 3

6
10 187 344 100 434 257

Sample Output 3

444

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

• 1 \le l \le r \le |S|. (|S| is the length of S.)
• The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

• S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Sample Input 1

20230322

Sample Output 1

4

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9

Problem Statement

We have a directed graph with N vertices, numbered 1, 2, \ldots, N.

Information about the edges is given by N^2 characters C_{1, 1}, C_{1, 2}, \ldots, C_{1, N}, C_{2, 1}, \ldots, C_{N, N}. Here, each C_{i, j} is either a lowercase English letter or -.

If C_{i, j} is a lowercase English letter, then there is exactly one directed edge from vertex i to vertex j labeled C_{i, j}. If C_{i, j} is -, there is no edge from vertex i to vertex j.

For each integer pair (i, j) with 1 \leq i, j \leq N, answer the following question:

• Among all (not necessarily simple) paths from vertex i to vertex j whose concatenation of labels on the edges forms a palindrome, what is the length of the shortest such path? If there is no such path, the answer is -1.

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each C_{i, j} is either a lowercase English letter or -.

Sample Input 1

4
ab--
--b-
---a
c---

Sample Output 1

0 1 2 4
-1 0 1 -1
3 -1 0 1
1 -1 -1 0

For example, consider the case (i, j) = (1, 4).
By taking the path 1 \to 1 \to 2 \to 3 \to 4, and concatenating the labels on its edges in order, we get the string abba, which is a palindrome.
There is no path of length at most 3 from vertex 1 to vertex 4 whose concatenation of labels is a palindrome. Thus, the answer for (1, 4) is 4.

Note that the empty string is also a palindrome.

Sample Input 2

5
us---
-st--
--s--
u--s-
---ts

Sample Output 2

0 1 3 -1 -1
-1 0 1 -1 -1
-1 -1 0 -1 -1
1 3 -1 0 -1
-1 -1 5 1 0

Problem Statement

We have a grid with 10^9 rows and 10^9 columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left.

For i=1,2,\ldots,N, a positive integer x_i is written on (r_i,c_i). On the other 10^{18}-N squares, 0 is written.

You choose a square (R,C) and compute the sum S of the integers written on the 2 \times 10^9 - 1 squares that share a row or column with (R,C).

Find the maximum possible value of S.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq r_i,c_i,x_i \leq 10^9
• (r_i,c_i) \neq (r_j,c_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4
1 1 2
1 2 9
2 1 8
3 2 3

Sample Output 1

20

If you choose (2,2) as (R,C), then S will be 20, which is the maximum possible value.

Sample Input 2

1
1 1000000000 1

Sample Output 2

1

Sample Input 3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

Sample Output 3

1510053068