Problem Statement

You are given three digits A,B,C between 1 and 9, inclusive.

Find the maximum value among all 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them.

Constraints

• A,B,C are digits between 1 and 9, inclusive.

Sample Input 1

3 2 4

Sample Output 1

432

There are six 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them: 324, 342, 234, 243, 432, 423; the maximum value among them is 432.

Sample Input 2

7 7 7

Sample Output 2

777

Only 777 can be formed.

Sample Input 3

9 1 9

Sample Output 3

991

Problem Statement

Takahashi is a teapot.
Since he is a teapot, he will gladly accept tea, but will refuse any other liquid.
Determine whether you can pour a liquid named S into him.

You are given a string S of length N consisting of lowercase English letters.
Determine whether S is a string that ends with tea.

Constraints

• 1 \leq N \leq 20
• N is an integer.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

8
greentea

Sample Output 1

Yes

greentea is a string that ends with tea.

Sample Input 2

6
coffee

Sample Output 2

No

coffee is not a string that ends with tea.

Sample Input 3

3
tea

Sample Output 3

Yes

Sample Input 4

1
t

Sample Output 4

No

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

N horses numbered 1 to N had a race.

All horses started simultaneously, and horse i took T_i seconds from the start to the goal.

Find the numbers of the horses that finished in 1st, 2nd, and 3rd places. It is guaranteed that all T_i are distinct.

Constraints

• 3\leq N \leq 32
• 1\leq T_i \leq 200
• All T_i are distinct.
• All input values are integers.

Sample Input 1

4
100 110 105 95

Sample Output 1

4 1 3

The horses finished in the order 4, 1, 3, 2. Output the numbers for 1st, 2nd, and 3rd places, which are 4, 1, 3, in this order, separated by spaces.

Sample Input 2

8
72 74 69 70 73 75 71 77

Sample Output 2

3 4 7

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

• 1 \leq i \lt j \leq N
• \min(a_i, a_j) = i
• \max(a_i, a_j) = j

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq a_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

• The length |A| is at least 4.
• A_1 < A_2.
• There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
• There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

• 4 \leq N \leq 3 \times 10^5
• P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
• All input values are integers.

Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

2

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

0

Sample Input 3

12
11 3 8 9 5 2 10 4 1 6 12 7

Sample Output 3

4

Problem Statement

There is a grid with H rows and W columns, and each cell is painted white or black.
Let us denote the cell at the i-th row from the top (1\leq i\leq H) and the j-th column from the left (1\leq j\leq W) by cell (i,j).
The state of the grid is given by H strings S_1,S_2,\ldots,S_H of length W consisting of . and #.
If the j-th character of S_i is ., then cell (i,j) is white; if it is #, then cell (i,j) is black.

By repainting some black cells (possibly zero) to white, Takahashi wants to make the grid have no 2\times 2 subgrid consisting only of black cells. More precisely, he wants to satisfy the following condition.

For any integer pair (i,j) with 1\leq i\leq H-1 and 1\leq j\leq W-1, among cells (i,j), (i,j+1), (i+1,j), and (i+1,j+1), at least one is white.

Find the minimum number of cells that need to be repainted white in order for Takahashi to achieve his goal.

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

Constraints

• 1\leq T\leq 100
• 2\leq H\leq 7
• 2\leq W\leq 7
• Each S_i is a string of length W consisting of . and #.
• T,H,W are integers.

Sample Input 1

2
5 5
####.
##.##
#####
.####
##.#.
2 2
..
..

Sample Output 1

3
0

For the first test case, the initial state of the grid is as shown in the left figure below. By repainting, for example, the three cells with numbers in the right figure below from black to white, the condition can be satisfied.

It is impossible to satisfy the condition by repainting two or fewer cells from the initial state, so output 3 on the 1-st line.

For the second test case, the grid already satisfies the condition from the beginning. Thus, output 0 on the 2-nd line.

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. The elements of A are distinct.

Process Q queries in the order they are given. Each query is of one of the following two types:

• 1 x y : Insert y immediately after the element x in A. It is guaranteed that x exists in A when this query is given.
• 2 x : Remove the element x from A. It is guaranteed that x exists in A when this query is given.

It is guaranteed that after processing each query, A will not be empty, and its elements will be distinct.

Print A after processing all the queries.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i \neq A_j
• For queries of the first type, 1 \leq x,y \leq 10^9.
• When a query of the first type is given, x exists in A.
• For queries of the second type, 1 \leq x \leq 10^9.
• When a query of the second type is given, x exists in A.
• After processing each query, A is not empty, and its elements are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4 5 1 3

The queries are processed as follows:

• Initially, A=(2,1,4,3).
• The first query removes 1, making A=(2,4,3).
• The second query inserts 5 immediately after 4, making A=(2,4,5,3).
• The third query removes 2, making A=(4,5,3).
• The fourth query inserts 1 immediately after 5, making A=(4,5,1,3).

Sample Input 2

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

Sample Output 2

5 1 7 2 3

Problem Statement

There is a circular cake divided into N pieces by cut lines. Each cut line is a line segment connecting the center of the circle to a point on the arc.

The pieces and cut lines are numbered 1, 2, \ldots, N in clockwise order, and piece i has a mass of A_i. Piece 1 is also called piece N + 1.

Cut line i is between pieces i and i + 1, and they are arranged clockwise in this order: piece 1, cut line 1, piece 2, cut line 2, \ldots, piece N, cut line N.

We want to divide this cake among K people under the following conditions. Let w_i be the sum of the masses of the pieces received by the i-th person.

• Each person receives one or more consecutive pieces.
• There are no pieces that no one receives.
• Under the above two conditions, \min(w_1, w_2, \ldots, w_K) is maximized.

Find the value of \min(w_1, w_2, \ldots, w_K) in a division that satisfies the conditions, and the number of cut lines that are never cut in the divisions that satisfy the conditions. Here, cut line i is considered cut if pieces i and i + 1 are given to different people.

Constraints

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

Sample Input 1

5 2
3 6 8 6 4

Sample Output 1

13 1

The following divisions satisfy the conditions:

• Give pieces 2, 3 to one person and pieces 4, 5, 1 to the other. Pieces 2, 3 have a total mass of 14, and pieces 4, 5, 1 have a total mass of 13.
• Give pieces 3, 4 to one person and pieces 5, 1, 2 to the other. Pieces 3, 4 have a total mass of 14, and pieces 5, 1, 2 have a total mass of 13.

The value of \min(w_1, w_2) in divisions satisfying the conditions is 13, and there is one cut line that is not cut in either division: cut line 5.

Sample Input 2

6 3
4 7 11 3 9 2

Sample Output 2

11 1

Sample Input 3

10 3
2 9 8 1 7 9 1 3 5 8

Sample Output 3

17 4