Problem Statement

Takahashi and Aoki played N games. You are given a string S of length N, representing the results of these games. Takahashi won the i-th game if the i-th character of S is T, and Aoki won that game if it is A.

The overall winner between Takahashi and Aoki is the one who won more games than the other. If they had the same number of wins, the overall winner is the one who reached that number of wins first. Find the overall winner: Takahashi or Aoki.

Constraints

• 1\leq N \leq 100
• N is an integer.
• S is a string of length N consisting of T and A.

Sample Input 1

5
TTAAT

Sample Output 1

T

Takahashi won three games, and Aoki won two. Thus, the overall winner is Takahashi, who won more games.

Sample Input 2

6
ATTATA

Sample Output 2

T

Both Takahashi and Aoki won three games. Takahashi reached three wins in the fifth game, and Aoki in the sixth game. Thus, the overall winner is Takahashi, who reached three wins first.

Sample Input 3

1
A

Sample Output 3

A

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

1. If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
2. Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
   • If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
   • If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
3. Return to step 1.

Print the sequence when the procedure ends.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• A_i \neq A_{i+1}
• All values in the input are integers.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

• Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
• Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.

Problem Statement

A single-player card game is popular in AtCoder Inc. Each card in the game has a lowercase English letter or the symbol @ written on it. There is plenty number of cards for each kind. The game goes as follows.

1. Arrange the same number of cards in two rows.
2. Replace each card with @ with one of the following cards: a, t, c, o, d, e, r.
3. If the two rows of cards coincide, you win. Otherwise, you lose.

To win this game, you will do the following cheat.

• Freely rearrange the cards within a row whenever you want after step 1.

You are given two strings S and T, representing the two rows you have after step 1. Determine whether it is possible to win with cheating allowed.

Constraints

• S and T consist of lowercase English letters and @.
• The lengths of S and T are equal and between 1 and 2\times 10^5, inclusive.

Sample Input 1

ch@ku@ai
choku@@i

Sample Output 1

Yes

You can replace the @s so that both rows become chokudai.

Sample Input 2

ch@kud@i
akidu@ho

Sample Output 2

Yes

You can cheat and replace the @s so that both rows become chokudai.

Sample Input 3

aoki
@ok@

Sample Output 3

No

You cannot win even with cheating.

Sample Input 4

aa
bb

Sample Output 4

No

Problem Statement

You are given an integer N and a string S consisting of 0, 1, and ?. Let T be the set of values that can be obtained by replacing each ? in S with 0 or 1 and interpreting the result as a binary integer. For instance, if S= ?0?, we have T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace.

Print (as a decimal integer) the greatest value in T less than or equal to N. If T does not contain a value less than or equal to N, print -1 instead.

Constraints

• S is a string consisting of 0, 1, and ?.
• The length of S is between 1 and 60, inclusive.
• 1\leq N \leq 10^{18}
• N is an integer.

Sample Input 1

?0?
2

Sample Output 1

1

As shown in the problem statement, T=\lbrace 0,1,4,5\rbrace. Among them, 0 and 1 are less than or equal to N, so you should print the greatest of them, 1.

Sample Input 2

101
4

Sample Output 2

-1

We have T=\lbrace 5\rbrace, which does not contain a value less than or equal to N.

Sample Input 3

?0?
1000000000000000000

Sample Output 3

5

Problem Statement

We have a grid with H rows and W columns. Let (i,j) denote the square at the i-th row from the top and j-th column from the left. Each square in the grid is one of the following: the start square, the goal square, an empty square, a wall square, and a candy square. (i,j) is represented by a character A_{i,j}, and is the start square if A_{i,j}= S, the goal square if A_{i,j}= G, an empty square if A_{i,j}= ., a wall square if A_{i,j}= #, and a candy square if A_{i,j}= o. Here, it is guaranteed that there are exactly one start, exactly one goal, and at most 18 candy squares.

Takahashi is now at the start square. He can repeat moving to a vertically or horizontally adjacent non-wall square. He wants to reach the goal square in at most T moves. Determine whether it is possible. If it is possible, find the maximum number of candy squares he can visit on the way to the goal square, where he must finish. Each candy square counts only once, even if it is visited multiple times.

Constraints

• 1\leq H,W \leq 300
• 1 \leq T \leq 2\times 10^6
• H, W, and T are integers.
• A_{i,j} is one of S, G, ., #, and o.
• Exactly one pair (i,j) satisfies A_{i,j}= S.
• Exactly one pair (i,j) satisfies A_{i,j}= G.
• At most 18 pairs (i,j) satisfy A_{i,j}= o.

Sample Input 1

3 3 5
S.G
o#o
.#.

Sample Output 1

1

If he makes four moves as (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) \rightarrow (1,3), he can visit one candy square and finish at the goal square. He cannot make five or fewer moves to visit two candy squares and finish at the goal square, so the answer is 1.

Note that making five moves as (1,1) \rightarrow (2,1) \rightarrow (1,1) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (2,3) to visit two candy squares is invalid since he would not finish at the goal square.

Sample Input 2

3 3 1
S.G
.#o
o#.

Sample Output 2

-1

He cannot reach the goal square in one or fewer moves.

Sample Input 3

5 10 2000000
S.o..ooo..
..o..o.o..
..o..ooo..
..o..o.o..
..o..ooo.G

Sample Output 3

18

Problem Statement

A DDoS-type string is a string of length 4 consisting of uppercase and lowercase English letters satisfying both of the following conditions.

• The first, second, and fourth characters are uppercase English letters, and the third character is a lowercase English letter.
• The first and second characters are equal.

For instance, DDoS and AAaA are DDoS-type strings, while neither ddos nor IPoE is.

You are given a string S consisting of uppercase and lowercase English letters and ?. Let q be the number of occurrences of ? in S. There are 52^q strings that can be obtained by independently replacing each ? in S with an uppercase or lowercase English letter. Among these strings, find the number of ones that do not contain a DDoS-type string as a subsequence, modulo 998244353.

Notes

A subsequence of a string is a string obtained by removing zero or more characters from the string and concatenating the remaining characters without changing the order.
For instance, AC is a subsequence of ABC, while RE is not a subsequence of ECR.

Constraints

• S consists of uppercase English letters, lowercase English letters, and ?.
• The length of S is between 4 and 3\times 10^5, inclusive.

Sample Input 1

DD??S

Sample Output 1

676

When at least one of the ?s is replaced with a lowercase English letter, the resulting string will contain a DDoS-type string as a subsequence.

Sample Input 2

????????????????????????????????????????

Sample Output 2

858572093

Find the count modulo 998244353.

Sample Input 3

?D??S

Sample Output 3

136604

Problem Statement

There are N people in a three-dimensional space. The i-th person is at the coordinates (X_i,Y_i,Z_i).
All people are at different coordinates, and we have X_i>0 for every i.

You will choose a point p=(x,y,z) such that x<0, and take a photo in the positive x-direction.

If the point p and the positions A, B of two people are on the same line in the order p,A,B, then the person at B will not be in the photo. There are no other potential obstacles.

Find the number of people in the photo when p is chosen to minimize this number.

Constraints

• 1 \leq N \leq 50
• 0 < X_i \leq 1000
• -1000 \leq Y_i,Z_i \leq 1000
• The triples (X_i,Y_i,Z_i) are distinct.
• All values in the input are integers.

Sample Input 1

3
1 1 1
2 2 2
100 99 98

Sample Output 1

2

For instance, if you take the photo from the point (-0.5,-0.5,-0.5), it will not show the second person.

Sample Input 2

8
1 1 1
1 1 -1
1 -1 1
1 -1 -1
3 2 2
3 2 -2
3 -2 2
3 -2 -2

Sample Output 2

4

If you take the photo from the point (-1,0,0), it will show four people.

Problem Statement

We have a connected undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex U_i and vertex V_i, and has an integer weight of W_i. For 1\leq s,t \leq N,\ s\neq t, let us define d(s,t) as follows.

• For every path connecting vertex s and vertex t, consider the maximum weight of an edge along that path. d(s,t) is the minimum value of this weight.

Answer Q queries. The j-th query is as follows.

• You are given A_j,S_j,T_j. By what value will d(S_j,T_j) increase when the weight of edge A_j is increased by 1?

Note that each query does not actually change the weight of the edge.

Constraints

• 2\leq N \leq 2\times 10^5
• N-1\leq M \leq 2\times 10^5
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• 1 \leq W_i \leq M
• The given graph is connected.
• 1\leq Q \leq 2\times 10^5
• 1 \leq A_j \leq M
• 1 \leq S_j,T_j \leq N
• S_j\neq T_j
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

0
0
0
0
0
1
1

The above figure shows the edge numbers in black and the edge weights in blue.

Let us explain the first through sixth queries.

First, consider d(4,6) in the given graph. The maximum weight of an edge along the path 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 5, which is the minimum over all paths connecting vertex 4 and vertex 6, so d(4,6)=5.

Next, consider the increment of d(4,6) when the weight of edge x\ (1 \leq x \leq 6) increases by 1. When x=6, we have d(4,6)=6, and the increment is 1. On the other hand, when x \neq 6, we have d(4,6)=5, and the increment is 0. For instance, when x=3, the maximum weight of an edge along the path 4 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 6, but the maximum weight of an edge along the path 4 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 6 is 5, so d(4,6) is still 5.

Sample Input 2

2 2
1 2 1
1 2 1
1
1 1 2

Sample Output 2

0

The given graph may contain multi-edges.