Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

• All input values are integers.
• 1 \leq L \leq R \leq N \leq 100

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

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

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

• Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

• K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

• S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

• (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
• (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

• 1 \le N \le 10
• 1 \le A_{i,j} \le 9
• All values in input are integers.

Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.

Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

Note that the answer may not fit into a 32-bit integer.

Problem Statement

You are playing a game.

There are N enemies lined up in a row, and the i-th enemy from the front has a health of H_i.

You will repeat the following action until the healths of all enemies become 0 or less, using a variable T initialized to 0.

• Increase T by 1. Then, attack the frontmost enemy with health 1 or more. If T is a multiple of 3, the enemy's health decreases by 3; otherwise, it decreases by 1.

Find the value of T when the healths of all enemies become 0 or less.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq H_i \leq 10^9
• All input values are integers.

Sample Input 1

3
6 2 2

Sample Output 1

8

The actions are performed as follows:

• T becomes 1. Attack the 1st enemy, and its health becomes 6-1=5.
• T becomes 2. Attack the 1st enemy, and its health becomes 5-1=4.
• T becomes 3. Attack the 1st enemy, and its health becomes 4-3=1.
• T becomes 4. Attack the 1st enemy, and its health becomes 1-1=0.
• T becomes 5. Attack the 2nd enemy, and its health becomes 2-1=1.
• T becomes 6. Attack the 2nd enemy, and its health becomes 1-3=-2.
• T becomes 7. Attack the 3rd enemy, and its health becomes 2-1=1.
• T becomes 8. Attack the 3rd enemy, and its health becomes 1-1=0.

Sample Input 2

9
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 2

82304529

Sample Input 3

5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

3000000000

Beware of integer overflow.

Problem Statement

You are given length-N integer sequences: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).

You are given Q queries to process in order. The i-th query (1\le i\le Q) is described as follows:

You are given a character c_i and integers X_i,V_i. If c_i= A, change A_{X_i} to V_i; if c_i= B, change B_{X_i} to V_i. Then, output \displaystyle \sum_{k=1}^N \min(A_k,B_k).

Constraints

• 1\le N,Q \le 2 \times 10^5
• 1\le A_i,B_i \le 10^9
• c_i is either A or B.
• 1\le X_i \le N
• 1\le V_i \le 10^9
• All input values are integers.

Sample Input 1

4 3
3 1 4 1
2 7 1 8
A 2 3
B 3 3
A 1 7

Sample Output 1

7
9
9

After the 1st query, A=(3,3,4,1),B=(2,7,1,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 1)+\min(1,8) = 7 on the 1st line.

After the 2nd query, A=(3,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(3,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 2nd line.

After the 3rd query, A=(7,3,4,1),B=(2,7,3,8). Therefore, output \displaystyle \min(7,2)+\min(3,7) + \min(4 , 3)+\min(1,8) = 9 on the 3rd line.

Sample Input 2

1 3
1
1000000000
A 1 1
A 1 1
A 1 1

Sample Output 2

1
1
1

Sample Input 3

5 3
100 100 100 100 100
100 100 100 100 100
A 4 21
A 2 99
B 4 57

Sample Output 3

421
420
420

Problem Statement

Let us regard an integer k as "similar to 250" if the following condition is satisfied:

• k is represented as k=p \times q^3 with primes p<q.

How many integers less than or equal to N are "similar to 250"?

Constraints

• N is an integer between 1 and 10^{18} (inclusive)

Sample Input 1

250

Sample Output 1

2

• 54 = 2 \times 3^3 is "similar to 250".
• 250 = 2 \times 5^3 is "similar to 250".

The two integers above are all the integers "similar to 250".

Sample Input 2

1

Sample Output 2

0

Sample Input 3

123456789012345

Sample Output 3

226863

Problem Statement

A country has N cities and M power plants, which we collectively call places.
The places are numbered 1,2,\dots,N+M, among which Places 1,2,\dots,N are the cities and Places N+1,N+2,\dots,N+M are the power plants.

This country has E power lines. Power Line i (1 \le i \le E) connects Place U_i and Place V_i bidirectionally.
A city is said to be electrified if one can reach at least one of the power plants from the city using some power lines.

Now, Q events will happen. In the i-th (1 \le i \le Q) event, Power Line X_i breaks, making it unusable. Once a power line breaks, it remains broken in the succeeding events.

Find the number of electrified cities right after each events.

Constraints

• All values in input are integers.
• 1 \le N,M
• N+M \le 2 \times 10^5
• 1 \le Q \le E \le 5 \times 10^5
• 1 \le U_i < V_i \le N+M
• If i \neq j, then U_i \neq U_j or V_i \neq V_j.
• 1 \le X_i \le E
• X_i are distinct.

Sample Input 1

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

Sample Output 1

4
4
2
2
2
1

Initially, all cities are electrified.

• The 1-st event breaks Power Line 3 that connects Point 5 and Point 10.
  • Now City 5 is no longer electrified, while 4 cities remain electrified.
• The 2-nd event breaks Power Line 5 that connects Point 2 and Point 9.
• The 3-rd event breaks Power Line 8 that connects Point 3 and Point 6.
  • Now Cities 2 and 3 are no longer electrified, while 2 cities remain electrified.
• The 4-th event breaks Power Line 10 that connects Point 1 and Point 8.
• The 5-th event breaks Power Line 2 that connects Point 4 and Point 10.
• The 6-th event breaks Power Line 7 that connects Point 1 and Point 7.
  • Now City 1 is no longer electrified, while 1 city remains electrified.

Problem Statement

You are given N lowercase English strings S_1,S_2,\ldots,S_N, and an integer L.

Find the number, modulo 998244353, of length-L lowercase English strings that contain all of S_1,S_2,\ldots,S_N as substrings.

Constraints

• 1\leq N\leq 8
• 1\leq L\leq 100
• N and L are integers.
• Each S_i is a string of length 1 and 10, inclusive, consisting of lowercase English letters.
• S_i\neq S_j\ (i\neq j)

Sample Input 1

2 4
ab
c

Sample Output 1

153

Some of the strings that satisfy the condition are abcz and cabc. acbd does not contain ab as a substring, so it does not satisfy the condition.

Sample Input 2

2 6
abc
cde

Sample Output 2

54

Sample Input 3

5 50
bbfogggj
zkbach
eedirhyc
ffgd
oemmswj

Sample Output 3

689020583