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

I begin with T and end with T, and I am full of T. What am I?

For a string t, define the filling rate as follows:

• If the first and last characters of t are both t and |t| \geq 3: Let x be the number of t in t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t.
• Otherwise: the filling rate of t is 0.

You are given a string S. Find the maximum possible filling rate of a substring of S.

Constraints

• 1 \leq |S| \leq 100
• S is a string consisting of lowercase English letters.

Sample Input 1

attitude

Sample Output 1

0.50000000000000000

ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.

There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.

Sample Input 2

ottottott

Sample Output 2

0.66666666666666667

ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.

There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.

Sample Input 3

coffeecup

Sample Output 3

0.00000000000000000

ff is a substring of S, and its filling rate is 0.

There is no substring with a filling rate greater than 0, so the answer is 0.

Problem Statement

On the poker table, there are tea bags of N different flavors. The flavors are numbered from 1 through N, and there are A_i tea bags of flavor i (1 \leq i \leq N).

You will play a game using these tea bags. The game has a parameter called difficulty between 1 and A_1 + \dots + A_N, inclusive. A game of difficulty b proceeds as follows:

1. You declare an integer x. Here, it must satisfy b \leq x \leq A_1 + \dots + A_N.
2. The dealer chooses exactly x tea bags from among those on the table and gives them to you.
3. You check the flavors of the x tea bags you received, and choose b tea bags from them.
4. If all b tea bags you chose are of the same flavor, you win. Otherwise, you lose.

The dealer will do their best to make you lose.

You are given Q queries, so answer each of them. The j-th query is as follows:

• For a game of difficulty B_j, report the minimum integer x you must declare at the start to guarantee a win. If it is impossible to win, report -1 instead.

Constraints

• 1 \leq N \leq 3 \times 10^5
• 1 \leq Q \leq 3 \times 10^5
• 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
• 1 \leq B_j \leq \min(10^6, A_1 + \dots + A_N) (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

4 5
4 1 8 4
1
8
5
2
10

Sample Output 1

1
17
14
5
-1

For the 1-st query, if you declare x=1, then no matter which 1 bag the dealer chooses, you can satisfy the winning condition by choosing appropriate 1 bag among them. Since you cannot choose an integer x less than 1, the answer is 1.

For the 2-nd query, if you declare x=17, then no matter which 17 bags the dealer chooses, you can satisfy the winning condition by choosing appropriate 8 bags among them. Conversely, if x < 17, the dealer can choose bags to prevent your victory. Thus, the answer is 17.

For the 3-rd query, if you declare x=14, then no matter which 14 bags the dealer chooses, you can satisfy the winning condition by choosing appropriate 5 bags among them. Conversely, if x < 14, the dealer can choose bags to prevent your victory. Thus, the answer is 14.

For the 4-th query, if you declare x=5, then no matter which 5 bags the dealer chooses, you can satisfy the winning condition by choosing appropriate 2 bags among them. Conversely, if x < 5, the dealer can choose bags to prevent your victory. Thus, the answer is 5.

For the 5-th query, no matter what x you declare, the dealer can choose bags to prevent your victory. Thus, print -1.

Sample Input 2

5 3
13 13 13 13 2
5
12
13

Sample Output 2

19
47
51

Problem Statement

This problem is a subproblem of Problem G.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
  1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
  2. Define an integer x as follows:
     • If S_i = 0 and S_{i+1} = 0, let x = 1.
     • If S_i = 0 and S_{i+1} = 1, let x = 0.
     • If S_i = 1 and S_{i+1} = 0, let x = 0.
     • If S_i = 1 and S_{i+1} = 1, let x = 1.
  3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
     For example, if S= 10101 and you choose i=2, the string after the operation is 1001.

You are given a string T of length N consisting of 0 and 1.
Find the number of beautiful strings that are substrings of T. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
110

Sample Output 1

3

The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1. The beautiful strings that are substrings of T are the following three strings:

• The string 1 obtained by taking the 1st character of T.
• The string 1 obtained by taking the 2nd character of T.
• The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

4

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

225

Problem Statement

There are N points on a two-dimensional plane, with the i-th point at coordinates (X_i, Y_i). It is guaranteed that no two points are at the same position, and no three points are collinear.

Among the combinations of four points from these points, how many combinations can form a trapezoid as a polygon with those four points as vertices?

Constraints

• 4 \leq N \leq 2\,000
• 0 \leq X_i, Y_i \leq 10^7 (1 \leq i \leq N)
• No two points are at the same location.
• No three points are collinear.
• All input values are integers.

Sample Input 1

5
0 2
0 5
1 0
2 1
2 4

Sample Output 1

3

The given points are arranged as shown in the figure below.

Among the combinations of four points, the following three combinations can form a trapezoid as a polygon with those points as vertices:

• The 1st, 5th, 4th, 3rd points.
• The 1st, 3rd, 4th, 2nd points.
• The 1st, 2nd, 5th, 4th points.

Note that parallelograms and rectangles are also treated as trapezoids.

Sample Input 2

8
0 1
1 3
2 3
3 1
0 2
1 0
2 0
3 2

Sample Output 2

22

Problem Statement

There are N teapots arranged in a row, numbered from 1 to N from left to right.

There is a sequence of integers (a_1, \dots, a_N), initially with values a_1 = \dots = a_N = -1.

You will fill each teapot with either tea or coffee so that the following conditions are all satisfied:

• For any two adjacent teapots, at least one of them contains tea.
• For any integer i satisfying 1 \leq i \leq N, if a_i \neq -1, then exactly a_i of teapots 1, \dots, i contain coffee.

You are given Q queries, which you should process in the given order.

The j-th query (1 \leq j \leq Q) is as follows:

• Change the value of a_{X_j} to Y_j. Then, print the number, modulo 998244353, of ways to fill the teapots satisfying the conditions.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq X_j \leq N (1 \leq j \leq Q)
• -1 \leq Y_j \leq X_j (1 \leq j \leq Q)
• All input values are integers.

Sample Input 1

5 6
1 1
4 2
1 0
4 -1
5 1
5 5

Sample Output 1

5
3
1
8
4
0

• After the operation in the first query, a = (1,\ -1,\ -1,\ -1,\ -1). The ways to fill the teapots satisfying the conditions are the following five ways:
  • Put coffee in teapot 1, and tea in the others.
  • Put coffee in teapots 1, 3, and tea in the others.
  • Put coffee in teapots 1, 3, 5, and tea in the others.
  • Put coffee in teapots 1, 4, and tea in the others.
  • Put coffee in teapots 1, 5, and tea in the others.
• After the operation in the second query, a = (1,\ -1,\ -1,\ 2,\ -1). The ways to fill the teapots satisfying the conditions are the following three ways:
  • Put coffee in teapots 1, 3, and tea in the others.
  • Put coffee in teapots 1, 3, 5, and tea in the others.
  • Put coffee in teapots 1, 4, and tea in the others.
• After the operation in the third query, a = (0,\ -1,\ -1,\ 2,\ -1). The ways to fill the teapots satisfying the conditions are the following one way:
  • Put coffee in teapots 2, 4, and tea in the others.
• After the operation in the fourth query, a = (0,\ -1,\ -1,\ -1,\ -1). The ways to fill the teapots satisfying the conditions are the following eight ways:
  • Put coffee in none of the teapots and tea in all of them.
  • Put coffee in teapot 2, and tea in the others.
  • Put coffee in teapots 2, 4, and tea in the others.
  • Put coffee in teapots 2, 5, and tea in the others.
  • Put coffee in teapot 3, and tea in the others.
  • Put coffee in teapots 3, 5, and tea in the others.
  • Put coffee in teapot 4, and tea in the others.
  • Put coffee in teapot 5, and tea in the others.
• After the operation in the fifth query, a = (0,\ -1,\ -1,\ -1,\ 1). The ways to fill the teapots satisfying the conditions are the following four ways:
  • Put coffee in teapot 2, and tea in the others.
  • Put coffee in teapot 3, and tea in the others.
  • Put coffee in teapot 4, and tea in the others.
  • Put coffee in teapot 5, and tea in the others.
• After the operation in the sixth query, a = (0,\ -1,\ -1,\ -1,\ 5). The number of ways to fill the teapots satisfying the conditions is zero.

Problem Statement

There are 16 integer tuples (A, B, C, D) satisfying A, B, C, D \in \lbrace 0, 1 \rbrace. For each of them, solve the following problem.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
  1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
  2. Define an integer x as follows:
     • If S_i = 0 and S_{i+1} = 0, let x = A.
     • If S_i = 0 and S_{i+1} = 1, let x = B.
     • If S_i = 1 and S_{i+1} = 0, let x = C.
     • If S_i = 1 and S_{i+1} = 1, let x = D.
  3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
     For example, if S= 10101 and you choose i=2, the string after the operation is 1001 if B=0, and 1101 if B=1.

You are given a string T of length N consisting of 0 and 1.

• Let L be the length of the longest beautiful string that is a substring of T (if no substring of T is a beautiful string, let L = -1),
• Let M be the number of beautiful strings that are substrings of T.

Find L and M. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
110

Sample Output 1

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

We explain the case (A,B,C,D)=(0,0,0,1).
The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1.
In the case (A,B,C,D)=(0,0,0,1), the beautiful strings that are substrings of T are the following three strings:

• The string 1 obtained by taking the 1st character of T.
• The string 1 obtained by taking the 2nd character of T.
• The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
-1 0
4 4
4 4
4 6
4 6
4 6
4 6
4 6
4 6

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

1 17
4 31
29 263
29 280
29 232
29 247
30 240
30 447
30 418
29 225
30 435
30 435
30 435
30 435
30 439
30 452