Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

• The length of S is 3.
• The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
• The 2-nd character is x.

Sample Input 1

3x7

Sample Output 1

21

We have 3 \times 7 = 21, which should be printed.

Sample Input 2

9x9

Sample Output 2

81

Sample Input 3

1x1

Sample Output 3

1

Problem Statement

There are 4 squares lined up horizontally.

You are given a string S of length 4 consisting of 0 and 1.
If the i-th character of S is 1, there is a person in the i-th square from the left;
if the i-th character of S is 0, there is no person in the i-th square from the left.

Now, everyone will move to the next square to the right simultaneously. By this move, the person who was originally in the rightmost square will disappear.

Determine if there will be a person in each square after the move. Print the result as a string in the same format as S. (See also Sample Input / Output for clarity.)

Constraints

• S is a string of length 4 consisting of 0 and 1.

Sample Input 1

1011

Sample Output 1

0101

After the move, the person who was originally in the 1-st square will move to the 2-nd square,
the person in the 3-rd square to the 4-th square,
and the person in the 4-th square will disappear.

Sample Input 2

0000

Sample Output 2

0000

Sample Input 3

1111

Sample Output 3

0111

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

• Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
• S_1 \neq S_2
• T_1 \neq T_2

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

Problem Statement

You are given a string S. Find the maximum length of a contiguous substring of S that is a palindrome.
Note that there is always a contiguous substring of S that is a palindrome.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase English letters.

Sample Input 1

TOYOTA

Sample Output 1

5

TOYOT, a contiguous substring of TOYOTA, is a palindrome of length 5.
TOYOTA, the only length-6 contiguous substring of TOYOTA, is not a palindrome, so print 5.

Sample Input 2

ABCDEFG

Sample Output 2

1

Every contiguous substring of length 1 is a palindrome.

Sample Input 3

AAAAAAAAAA

Sample Output 3

10

Problem Statement

There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).

You can perform the following operation any number of times (possibly zero):

• If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.

Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^{9}
• 1 \leq M \leq 2 \times 10^{5}
• M \leq N
• 1 \leq X_i \leq N (1 \leq i \leq M)
• X_i \neq X_j (1 \leq i < j \leq M)
• 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

5 2
1 4
3 2

Sample Output 1

4

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

• Move one stone from cell 1 to cell 2.
• Move one stone from cell 2 to cell 3.
• Move one stone from cell 4 to cell 5.
• Move one stone from cell 1 to cell 2.

It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.

Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

You are given a string S of length N consisting of the characters ., o, and ?. Among the strings that can be obtained by replacing every ? in S independently with either . or o, let X be the set of strings that satisfy all of the following conditions:

• The number of os is exactly K.
• No two os are adjacent.

It is guaranteed that X is non‑empty.

Print a string T of length N that satisfies the following (let T_i denote the i‑th character of T):

• If the i‑th character of every string in X is ., then T_i= ..
• If the i‑th character of every string in X is o, then T_i= o.
• If X contains both a string whose i‑th character is . and a string whose i‑th character is o, then T_i= ?.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le K
• S is a string of length N consisting of ., o, ?.
• X is non‑empty.
• All given numerical values are integers.

Sample Input 1

4 2
o???

Sample Output 1

o.??

The set X consists of the two strings o.o. and o..o.

• The 1st character of every string in X is o, so T_1 is o.
• The 2nd character of every string in X is ., so T_2 is ..
• The 3rd character of a string in X can be either . or o, so T_3 is ?.

Sample Input 2

5 2
?????

Sample Output 2

?????

Sample Input 3

7 3
.o???o.

Sample Output 3

.o.o.o.

Problem Statement

There is an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, where all elements are initially set to 0. Also, there is a set S, which is initially empty.

Perform the following Q queries in order. Find the value of each element in the sequence A after processing all Q queries. The i-th query is in the following format:

• An integer x_i is given. If the integer x_i is contained in S, remove x_i from S. Otherwise, insert x_i to S. Then, for each j=1,2,\ldots,N, add |S| to A_j if j\in S.

Here, |S| denotes the number of elements in the set S. For example, if S=\lbrace 3,4,7\rbrace, then |S|=3.

Constraints

• 1\leq N,Q\leq 2\times10^5
• 1\leq x_i\leq N
• All given numbers are integers.

Sample Input 1

3 4
1 3 3 2

Sample Output 1

6 2 2

In the first query, 1 is inserted to S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(1,0,0).

In the second query, 3 is inserted to S, making S=\lbrace 1,3\rbrace. Then, |S|=2 is added to A_1 and A_3. The sequence becomes A=(3,0,2).

In the third query, 3 is removed from S, making S=\lbrace 1\rbrace. Then, |S|=1 is added to A_1. The sequence becomes A=(4,0,2).

In the fourth query, 2 is inserted to S, making S=\lbrace 1,2\rbrace. Then, |S|=2 is added to A_1 and A_2. The sequence becomes A=(6,2,2).

Eventually, the sequence becomes A=(6,2,2).

Sample Input 2

4 6
1 2 3 2 4 2

Sample Output 2

15 9 12 7

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.