Problem Statement

You are given a string S consisting of lowercase English letters and a positive integer N. The length of S is at least 2N+1.

Find the string obtained by removing N characters from the beginning and N characters from the end of S.

Constraints

• S is a string consisting of lowercase English letters.
• N is an integer.
• 2N+1 \leq |S| \leq 30
• 1 \leq N \leq 10

Sample Input 1

chemotherapy
3

Sample Output 1

mother

Removing the first three characters (che) and the last three characters (apy) from chemotherapy gives mother.

Sample Input 2

thermometer
4

Sample Output 2

mom

Sample Input 3

burger
1

Sample Output 3

urge

Problem Statement

There is a grid with H rows and W columns. The cell at the i-th row from the top and the j-th column from the left is denoted as cell (i, j).

Cells (x_1, y_1) and (x_2, y_2) are said to be edge-adjacent when |x_1 - x_2| + |y_1 - y_2| = 1.

For every cell, find the number of cells that are edge-adjacent to it.

Constraints

• 1 \leq H, W \leq 50
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

2 3 3 3 2
3 4 4 4 3
3 4 4 4 3
2 3 3 3 2

The cells edge-adjacent to cell (1, 5) are cells (1, 4), (2, 5), for a total of two cells.

The cells edge-adjacent to cell (2, 3) are cells (1, 3), (2, 2), (2, 4), (3, 3), for a total of four cells.

The cells edge-adjacent to cell (4, 2) are cells (3, 2), (4, 1), (4, 3), for a total of three cells.

Sample Input 2

1 1

Sample Output 2

0

There are no cells edge-adjacent to cell (1, 1).

Sample Input 3

12 8

Sample Output 3

2 3 3 3 3 3 3 2
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
3 4 4 4 4 4 4 3
2 3 3 3 3 3 3 2

Problem Statement

You are given a string S consisting of uppercase English letters.
Find the number of substrings (contiguous subsequences) of S that satisfy all of the following conditions.

• It consists of an odd number of characters.
• Its middle character is C. More formally, if the extracted substring consists of l characters, its ((l+1)/2)-th character is C.

Even if two substrings are identical as strings, they are counted separately if they are extracted from different positions.

Constraints

• S is a string consisting of uppercase English letters with length between 1 and 5 \times 10^5, inclusive.

Sample Input 1

ABCCA

Sample Output 1

5

In this input, S= ABCCA.
The substrings satisfying the conditions in the problem statement are the following five:

• ABCCA, extracted from the 1st to 5th characters of S
• BCC, extracted from the 2nd to 4th characters of S
• C, extracted from the 3rd to 3rd characters of S
• CCA, extracted from the 3rd to 5th characters of S
• C, extracted from the 4th to 4th characters of S

Sample Input 2

XYZ

Sample Output 2

0

Sample Input 3

SMBCPROGRAMMINGCONTEST

Sample Output 3

11

Problem Statement

There is one integer X written on a blackboard.

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

Two integers A_i and B_i are given. Write two new integers A_i and B_i on the blackboard.

Then, output the median of the 2i+1 integers written on the blackboard.

Constraints

• 1 \le X \le 10^9
• 1 \le Q \le 2 \times 10^5
• 1 \le A_i, B_i \le 10^9
• All input values are integers.

Sample Input 1

5
3
2 3
1 2
8 9

Sample Output 1

3
2
3

In the first query, the integers written on the blackboard become 5, 2, 3, and their median is 3.

In the second query, the integers written on the blackboard become 5, 2, 3, 1, 2, and their median is 2.

In the third query, the integers written on the blackboard become 5, 2, 3, 1, 2, 8, 9, and their median is 3.

Sample Input 2

1
4
2 3
4 5
6 7
8 9

Sample Output 2

2
3
4
5

Sample Input 3

278117031
7
167642909 517897721
148434323 567739597
319926999 481642530
659199879 252516557
49913403 798318034
89701408 892537201
199166668 742285869

Sample Output 3

278117031
278117031
319926999
319926999
319926999
319926999
319926999

Problem Statement

Find the number, modulo 998244353, of sequences A = (a_1, \cdots, a_{X_1 + X_2 + X_3}) of length X_1+X_2+X_3 that satisfy all of the following conditions.

• A contains exactly X_1 copies of 1, exactly X_2 copies of 2, and exactly X_3 copies of 3.
• The absolute difference between adjacent elements is at most 1. That is, for every integer i satisfying 1 \leq i \leq X_1+X_2+X_3-1, we have |a_{i+1} - a_i| \leq 1.

Constraints

• 1 \leq X_1, X_2, X_3 \leq 10^6
• All input values are integers.

Sample Input 1

2 2 1

Sample Output 1

9

The sequences satisfying the conditions are the following nine:

• (1, 1, 2, 2, 3)
• (1, 1, 2, 3, 2)
• (1, 2, 1, 2, 3)
• (1, 2, 3, 2, 1)
• (2, 1, 1, 2, 3)
• (2, 3, 2, 1, 1)
• (3, 2, 1, 1, 2)
• (3, 2, 1, 2, 1)
• (3, 2, 2, 1, 1)

Sample Input 2

5 3 4

Sample Output 2

204

Sample Input 3

998244 998353 998107

Sample Output 3

701926019

Problem Statement

You are given K strings S_i consisting of lowercase English letters.
Find the number, modulo 998244353, of strings of length N consisting of lowercase English letters that do not contain any of S_1, S_2, \dots, S_K as a substring (contiguous subsequence).

Constraints

• N is an integer between 1 and 10^9, inclusive.
• K is an integer between 1 and 10, inclusive.
• S_i is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

Sample Input 1

3 2
aa
ab

Sample Output 1

17474

• The number of strings of length 3 consisting of lowercase English letters is 26^3=17576.
• The number of strings of length 3 consisting of lowercase English letters whose first two characters are aa is 26.
• The number of strings of length 3 consisting of lowercase English letters whose last two characters are aa is 26.
• The number of strings of length 3 consisting of lowercase English letters whose first two characters are ab is 26.
• The number of strings of length 3 consisting of lowercase English letters whose last two characters are ab is 26.
• The number of strings of length 3 consisting of lowercase English letters whose entirety is aaa is 1.
• The number of strings of length 3 consisting of lowercase English letters whose entirety is aab is 1.
• Combining the above facts, it can be confirmed that the answer for this test case is 17474.

Sample Input 2

1 1
ab

Sample Output 2

26

Sample Input 3

1000000000 10
contest
tester
error
orange
angel
elegant
antitese
sextuple
pleasure
surely

Sample Output 3

698570468

Find the count modulo 998244353.

Problem Statement

There are 10^{100} kids at a game venue. Initially, no kid has any medals.

A kid leaves the venue exactly when they either drop out or escape.

The game consists of N days. On day i (1 \leq i \leq N), the following sequence of operations is performed in order.

• Collect all medals held by the kids at the venue, and let s be the total number of collected medals.
• Distribute s + A_i medals freely among the kids at the venue (if there are no kids at the venue, do nothing).
• Among the kids at the venue, those with fewer than B_i medals drop out. Those with at least B_i medals each lose B_i medals.
• Among the kids at the venue, those with at least C_i medals each choose whether to escape at this point or remain at the venue.

Kids who remain at the venue at the end of the N days drop out.

Find the maximum possible number of kids who ultimately escape.

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

Constraints

• 1 \leq T \leq 3 \times 10^5
• 1 \leq N \leq 3 \times 10^5
• 1 \leq A_i \leq 10^6
• 1 \leq B_i \leq 10^6
• 1 \leq C_i \leq 10^6
• The sum of N over all test cases is at most 3 \times 10^5.
• All input values are integers.

Sample Input 1

2
4
16 2 3
15 2 4
1 3 5
20 5 5
2
41404 1 941738
211877 205711 417821

Sample Output 1

5
0

Consider the first test case. By acting as follows, five kids can escape.

• At the start of day 1, collect s = 0 medals from 10^{100} kids. Then, proceed as follows.
  • Distribute 0 + 16 = 16 medals so that the kids' medal counts become (5, 5, 2, 2, 2, 0, \dots, 0).
  • The 10^{100} - 5 kids with no medals drop out, and the remaining 5 kids' medal counts become (3, 3, 0, 0, 0).
  • The 2 kids with 3 medals each choose to escape, and the remaining 3 kids' medal counts become (0, 0, 0).
• At the start of day 2, collect s = 0 medals from 3 kids. Then, proceed as follows.
  • Distribute 0 + 15 = 15 medals so that the kids' medal counts becomes (6, 6, 3).
  • No one drops out, and the remaining 3 kids' medal counts become (4, 4, 1).
  • 1 kid with 4 medals chooses to escape, and the remaining 2 kids' medal counts become (4, 1).
• At the start of day 3, collect s = 5 medals from 2 kids. Then, proceed as follows.
  • Distribute 5 + 1 = 6 medals so that the kids' medal counts becomes (3, 3).
  • No one drops out, and the remaining 2 kids' medal counts become (0, 0).
  • No one escapes.
• At the start of day 4, collect s = 0 medals from 2 kids. Then, proceed as follows.
  • Distribute 0 + 20 = 20 medals so that the kids' medal counts becomes (10, 10).
  • No one drops out, and the remaining 2 kids' medal counts become (5, 5).
  • The 2 kids with 5 medals each choose to escape, and the venue becomes empty.

In the second test case, not a single kid can escape.