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

There is a rectangle in the xy-plane. Each edge of this rectangle is parallel to the x- or y-axis, and its area is not zero.

Given the coordinates of three of the four vertices of this rectangle, (x_1, y_1), (x_2, y_2), and (x_3, y_3), find the coordinates of the other vertex.

Constraints

• -100 \leq x_i, y_i \leq 100
• There uniquely exists a rectangle with all of (x_1, y_1), (x_2, y_2), (x_3, y_3) as vertices, edges parallel to the x- or y-axis, and a non-zero area.
• All values in input are integers.

Sample Input 1

-1 -1
-1 2
3 2

Sample Output 1

3 -1

The other vertex of the rectangle with vertices (-1, -1), (-1, 2), (3, 2) is (3, -1).

Sample Input 2

-60 -40
-60 -80
-20 -80

Sample Output 2

-20 -40

Problem Statement

Studying Kanbun, Takahashi is having trouble figuring out the order to read words. Help him out!

There are N integers from 1 through N arranged in a line in ascending order.
Between them are M "レ" marks. The i-th "レ" mark is between the integer a_i and integer (a_i + 1).

You read each of the N integers once by the following procedure.

• Consider an undirected graph G with N vertices numbered 1 through N and M edges. The i-th edge connects vertex a_i and vertex (a_i+1).
• Repeat the following operation until there is no unread integer:
  • let x be the minimum unread integer. Choose the connected component C containing vertex x, and read all the numbers of the vertices contained in C in descending order.

For example, suppose that integers and "レ" marks are arranged in the following order:

(In this case, N = 5, M = 3, and a = (1, 3, 4).)
Then, the order to read the integers is determined to be 2, 1, 5, 4, and 3, as follows:

• At first, the minimum unread integer is 1, and the connected component of G containing vertex 1 has vertices \lbrace 1, 2 \rbrace, so 2 and 1 are read in this order.
• Then, the minimum unread integer is 3, and the connected component of G containing vertex 3 has vertices \lbrace 3, 4, 5 \rbrace, so 5, 4, and 3 are read in this order.
• Now that all integers are read, terminate the procedure.

Given N, M, and (a_1, a_2, \dots, a_M), print the order to read the N integers.

Constraints

• 1 \leq N \leq 100
• 0 \leq M \leq N - 1
• 1 \leq a_1 \lt a_2 \lt \dots \lt a_M \leq N-1
• All values in the input are integers.

Sample Input 1

5 3
1 3 4

Sample Output 1

2 1 5 4 3

As described in the Problem Statement, if integers and "レ" marks are arranged in the following order:

then the integers are read in the following order: 2, 1, 5, 4, and 3.

Sample Input 2

5 0

Sample Output 2

1 2 3 4 5

There may be no "レ" mark.

Sample Input 3

10 6
1 2 3 7 8 9

Sample Output 3

4 3 2 1 5 6 10 9 8 7

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

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

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

• a
• y
• ay
• ya
• yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54

Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

Takahashi has decided to enjoy a wired full-course meal consisting of N courses in a restaurant.
The i-th course is:

• if X_i=0, an antidotal course with a tastiness of Y_i;
• if X_i=1, a poisonous course with a tastiness of Y_i.

When Takahashi eats a course, his state changes as follows:

• Initially, Takahashi has a healthy stomach.
• When he has a healthy stomach,
  • if he eats an antidotal course, his stomach remains healthy;
  • if he eats a poisonous course, he gets an upset stomach.
• When he has an upset stomach,
  • if he eats an antidotal course, his stomach becomes healthy;
  • if he eats a poisonous course, he dies.

The meal progresses as follows.

• Repeat the following process for i = 1, \ldots, N in this order.
  • First, the i-th course is served to Takahashi.
  • Next, he chooses whether to "eat" or "skip" the course.
    • If he chooses to "eat" it, he eats the i-th course. His state also changes depending on the course he eats.
    • If he chooses to "skip" it, he does not eat the i-th course. This course cannot be served later or kept somehow.
  • Finally, (if his state changes, after the change) if he is not dead,
    • if i \neq N, he proceeds to the next course.
    • if i = N, he makes it out of the restaurant alive.

An important meeting awaits him, so he must make it out of there alive.
Find the maximum possible sum of tastiness of the courses that he eats (or 0 if he eats nothing) when he decides whether to "eat" or "skip" the courses under that condition.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• X_i \in \{0,1\}
  • In other words, X_i is either 0 or 1.
• -10^9 \le Y_i \le 10^9

Sample Input 1

5
1 100
1 300
0 -200
1 500
1 300

Sample Output 1

600

The following choices result in a total tastiness of the courses that he eats amounting to 600, which is the maximum possible.

• He skips the 1-st course. He now has a healthy stomach.
• He eats the 2-nd course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 300.
• He eats the 3-rd course. He now has a healthy stomach again, and the total tastiness of the courses that he eats amounts to 100.
• He eats the 4-th course. He now has an upset stomach, and the total tastiness of the courses that he eats amounts to 600.
• He skips the 5-th course. He now has an upset stomach.
• In the end, he is not dead, so he makes it out of the restaurant alive.

Sample Input 2

4
0 -1
1 -2
0 -3
1 -4

Sample Output 2

0

For this input, it is optimal to eat nothing, in which case the answer is 0.

Sample Input 3

15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

Sample Output 3

4100000000

The answer may not fit into a 32-bit integer type.

Problem Statement

You are given integer sequences A = (a_1,\ldots,a_N) and B = (b_1,\ldots,b_N), each of length N.

For i=1,...,Q, answer the query in the following format.

• If the set of values contained in the first x_i terms of A, (a_1,\ldots,a_{x_i}), and the set of values contained in the first y_i terms of B, (b_1,\ldots,b_{y_i}), are equal, then print Yes; otherwise, print No.

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq a_i,b_i \leq 10^9
• 1 \leq x_i,y_i \leq N
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes
Yes
No
No
Yes
No

Note that sets are a concept where it matters only whether each value is contained or not.
For the 3-rd query, the first 2 terms of A contain one 1 and one 2, while the first 3 terms of B contain one 1 and two 2's. However, the sets of values contained in the segments are both \{ 1,2 \}, which are equal.
Also, for the 6-th query, the values appear in different orders, but they are still equal as sets.

Problem Statement

Given is a sequence A of length N. You can do this operation any number of times: when the length of the sequence is at least 2, choose two adjacent values, delete them, and insert their sum where they were. How many sequences can result from zero or more operations? Find the count modulo 998244353.

Constraints

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

Sample Input 1

3
1 -1 1

Sample Output 1

4

The following four sequences can result from zero or more operations.

• {1,-1,1}
• {1,0}
• {0,1}
• {1}

Sample Input 2

10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

Sample Output 2

321