Problem Statement

You are given an integer N. Consider permuting the digits in N and separate them into two positive integers.

For example, for the integer 123, there are six ways to separate it, as follows:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

Here, the two integers after separation must not contain leading zeros. For example, it is not allowed to separate the integer 101 into 1 and 01. Additionally, since the resulting integers must be positive, it is not allowed to separate 101 into 11 and 0, either.

What is the maximum possible product of the two resulting integers, obtained by the optimal separation?

Constraints

• N is an integer between 1 and 10^9 (inclusive).
• N contains two or more digits that are not 0.

Sample Input 1

123

Sample Output 1

63

As described in Problem Statement, there are six ways to separate it:

• 12 and 3,
• 21 and 3,
• 13 and 2,
• 31 and 2,
• 23 and 1,
• 32 and 1.

The products of these pairs, in this order, are 36, 63, 26, 62, 23, 32, with 63 being the maximum.

Sample Input 2

1010

Sample Output 2

100

There are two ways to separate it:

• 100 and 1,
• 10 and 10.

In either case, the product is 100.

Sample Input 3

998244353

Sample Output 3

939337176

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x_i \leq N
• All values in input are integers.

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The states of the cells are given by N strings of length N, S_1, S_2, \dots, S_N, in the following format:

• If the j-th character of S_i is o, there is an o written in cell (i,j).
• If the j-th character of S_i is x, there is an x written in cell (i,j).

Find the number of triples of cells that satisfy all of the following conditions:

• The three cells in the triple are distinct.
• All three cells have an o written in them.
• Exactly two of the cells are in the same row.
• Exactly two of the cells are in the same column.

Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.

Constraints

• N is an integer between 2 and 2000, inclusive.
• S_i is a string of length N consisting of o and x.

Sample Input 1

3
ooo
oxx
xxo

Sample Output 1

4

The following four triples satisfy the conditions:

• (1,1),(1,2),(2,1)
• (1,1),(1,3),(2,1)
• (1,1),(1,3),(3,3)
• (1,2),(1,3),(3,3)

Sample Input 2

4
oxxx
xoxx
xxox
xxxo

Sample Output 2

0

Sample Input 3

15
xooxxooooxxxoox
oxxoxoxxxoxoxxo
oxxoxoxxxoxoxxx
ooooxooooxxoxxx
oxxoxoxxxoxoxxx
oxxoxoxxxoxoxxo
oxxoxooooxxxoox
xxxxxxxxxxxxxxx
xooxxxooxxxooox
oxxoxoxxoxoxxxo
xxxoxxxxoxoxxoo
xooxxxooxxoxoxo
xxxoxxxxoxooxxo
oxxoxoxxoxoxxxo
xooxxxooxxxooox

Sample Output 3

2960

Problem Statement

We have a number sequence A = (A_1, A_2, \dots, A_N) of length N and integers X and Y. Find the number of pairs of integers (L, R) satisfying all the conditions below.

• 1 \leq L \leq R \leq N
• The maximum value of A_L, A_{L+1}, \dots, A_R is X, and the minimum is Y.

Constraints

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

Sample Input 1

4 3 1
1 2 3 1

Sample Output 1

4

4 pairs satisfy the conditions: (L,R)=(1,3),(1,4),(2,4),(3,4).

Sample Input 2

5 2 1
1 3 2 4 1

Sample Output 2

0

No pair (L,R) satisfies the condition.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

15

It may hold that X=Y.

Sample Input 4

10 8 1
2 7 1 8 2 8 1 8 2 8

Sample Output 4

36

Problem Statement

There are apple trees lined up on a number line, and N apples fall from the trees.
Specifically, for each 1\leq i\leq N, an apple falls at coordinate X_i at time T_i.

Takahashi has a basket with durability D and length W, and he can take the following action exactly once.

Choose positive integers S and L. He sets up the basket to cover the range L-0.5\leq x\leq L+W-0.5 at time S-0.5, and retrieves it at time S+D-0.5. He gets all the apples that fell into the range covered by the basket between the time it was set up and the time it was retrieved.

He cannot move the basket once it has been set up, nor can he set it up again once it has been retrieved.
Find the maximum number of apples that he can get.

Constraints

• 1 \leq N\leq 2\times 10^5
• 1 \leq D\leq 2\times 10^5
• 1 \leq W\leq 2\times 10^5
• 1 \leq T_i\leq 2\times 10^5
• 1 \leq X_i\leq 2\times 10^5
• All pairs (T_i,X_i) are different.
• All input values are integers.

Sample Input 1

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

Sample Output 1

5

If Takahashi chooses S=3 and L=2, he will set up the basket to cover the range 1.5\leq x\leq 4.5 from time 2.5 to 6.5. Then, he gets the following five apples:

• The apple that falls at coordinate X_2=4 at time T_2=3
• The apple that falls at coordinate X_3=4 at time T_3=6
• The apple that falls at coordinate X_4=2 at time T_4=5
• The apple that falls at coordinate X_5=2 at time T_5=4
• The apple that falls at coordinate X_6=3 at time T_6=4

There is no way to get six or more apples, so print 5.