Problem Statement

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

• 1000 \leq y \leq 9000
• 1 \leq m \leq M \leq 99
• 1 \leq d \leq D \leq 99
• All input values are integers.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

• 1 \leq N \leq 100
• 1 \leq S,M,L \leq 10^4
• All input values are integers.

Sample Input 1

16 120 150 200

Sample Output 1

300

It is optimal to buy two 8-egg packs.

Sample Input 2

10 100 50 10

Sample Output 2

10

It is optimal to buy one 12-egg pack.

Sample Input 3

99 600 800 1200

Sample Output 3

10000

It is optimal to buy five 8-egg packs and five 12-egg packs.

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

For each i=1,\ldots,N, solve the following problem.

Problem: Find the sum of all elements in A that are greater than A_i.

Constraints

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

Sample Input 1

5
1 4 1 4 2

Sample Output 1

10 0 10 0 8

• For i=1, the sum of elements greater than A_1=1 is 4+4+2=10.
• For i=2, the sum of elements greater than A_2=4 is 0.
• For i=3, the sum of elements greater than A_3=1 is 4+4+2=10.
• For i=4, the sum of elements greater than A_4=4 is 0.
• For i=5, the sum of elements greater than A_5=2 is 4+4=8.

Sample Input 2

10
31 42 59 26 53 58 97 93 23 54

Sample Output 2

456 414 190 487 361 249 0 97 513 307

Sample Input 3

50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Problem Statement

There is a grid with 10^9 by 10^9 squares. Let (i, j) denote the square at the (i + 1)-th row from the top and the (j + 1)-th column from the left (0 \leq i, j \lt 10^9). (Note the unusual index assignment.)
Each square is black or white. The color of the square (i, j) is represented by a character P[i \bmod N][j \bmod N], where B means black, and W means white. Here, a \bmod b denotes the remainder when a is divided by b.

Answer Q queries.
Each query gives you four integers A, B, C, D and asks you to find the number of black squares contained in the rectangular area with (A, B) as the top-left corner and (C, D) as the bottom-right corner.

Constraints

• 1 \leq N \leq 1000
• P[i][j] is W or B.
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq A \leq C \lt 10^9
• 0 \leq B \leq D \lt 10^9
• N, Q, A, B, C, D are all integers.

Sample Input 1

3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5

Sample Output 1

4
7

The figure below illustrates the upper left part of the grid.

For the first query, the rectangular area with (1, 2) as the top-left corner and (3, 4) as the bottom-right corner, surrounded by the red frame in the figure, contains four black squares.
For the second query, the rectangular area with (0, 3) as the top-left corner and (4, 5) as the bottom-right corner, surrounded by the blue frame in the figure, contains seven black squares.

Sample Input 2

10 5
BBBWWWBBBW
WWWWWBBBWB
BBBWBBWBBB
BBBWWBWWWW
WWWWBWBWBW
WBBWBWBBBB
WWBBBWWBWB
WBWBWWBBBB
WBWBWBBWWW
WWWBWWBWWB
5 21 21 93
35 35 70 43
55 72 61 84
36 33 46 95
0 0 999999999 999999999

Sample Output 2

621
167
44
344
500000000000000000

Problem Statement

AtCoder cafeteria sells meals consisting of a main dish and a side dish.
There are N types of main dishes, called main dish 1, main dish 2, \dots, main dish N. Main dish i costs a_i yen.
There are M types of side dishes, called side dish 1, side dish 2, \dots, side dish M. Side dish i costs b_i yen.

A set meal is composed by choosing one main dish and one side dish. The price of a set meal is the sum of the prices of the chosen main dish and side dish.
However, for L distinct pairs (c_1, d_1), \dots, (c_L, d_L), the set meal consisting of main dish c_i and side dish d_i is not offered because they do not go well together.
That is, NM - L set meals are offered. (The constraints guarantee that at least one set meal is offered.)

Find the price of the most expensive set meal offered.

Constraints

• 1 \leq N, M \leq 10^5
• 0 \leq L \leq \min(10^5, NM - 1)
• 1 \leq a_i, b_i \leq 10^9
• 1 \leq c_i \leq N
• 1 \leq d_j \leq M
• (c_i, d_i) \neq (c_j, d_j) if i \neq j.
• All input values are integers.

Sample Input 1

2 3 3
2 1
10 30 20
1 2
2 1
2 3

Sample Output 1

31

They offer three set meals, listed below, along with their prices:

• A set meal consisting of main dish 1 and side dish 1, at a price of 2 + 10 = 12 yen.
• A set meal consisting of main dish 1 and side dish 3, at a price of 2 + 20 = 22 yen.
• A set meal consisting of main dish 2 and side dish 2, at a price of 1 + 30 = 31 yen.

Among them, the most expensive is the third one. Thus, print 31.

Sample Input 2

2 1 0
1000000000 1
1000000000

Sample Output 2

2000000000

Sample Input 3

10 10 10
47718 21994 74148 76721 98917 73766 29598 59035 69293 29127
7017 46004 16086 62644 74928 57404 32168 45794 19493 71590
1 3
2 6
4 5
5 4
5 5
5 6
5 7
5 8
5 10
7 3

Sample Output 3

149076

Problem Statement

You are given a string S of length N consisting of lowercase English letters.
Process Q queries described below in the order they are given.
There are two types of queries:

• 1 x c : Change the x-th character of S to the lowercase English letter c.
• 2 L R : If the substring formed by the L-th through R-th characters of S is a palindrome, print Yes; otherwise, print No.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq x \leq N
• c is a lowercase English letter.
• 1 \leq L \leq R \leq N
• N, Q, x, L, R are integers.

Sample Input 1

7 8
abcbacb
2 1 5
2 4 7
2 2 2
1 5 c
2 1 5
2 4 7
1 4 c
2 3 6

Sample Output 1

Yes
No
Yes
No
Yes
Yes

Initially, S = abcbacb.
For the first query, the string formed by the 1-st through 5-th characters of S is abcba, which is a palindrome. Thus, print Yes.
For the second query, the string formed by the 4-th through 7-th character of S is bacb, which is not a palindrome. Thus, print No.
For the third query, the string formed by the 2-nd through 2-nd character of S is b, which is a palindrome. Thus, output Yes.
For the fourth query, change the 5-th character of S to c. S becomes abcbccb.
For the fifth query, the string formed by the 1-st through 5-th character of S is abcbc, which is not a palindrome. Thus, output No.
For the sixth query, the string formed by the 4-th through 7-th character of S is bccb, which is a palindrome. Thus, output Yes.
For the seventh query, change the 4-th character of S to c. S becomes abccccb.
For the eighth query, the string formed by the 3-rd through 6-th character of cccc, which is a palindrome. Thus, output Yes.

Problem Statement

There are N cards in a box. Each card has an integer written on it, which is between 1 and M, inclusive. For each i=1,\ldots,M, there are C_i cards with the number i written on them.

Starting with an empty notebook, you repeat the following operation:

• Randomly draw one card from the box. Write the integer on the card in the notebook, then return the card to the box.

Find the expected value, modulo 998244353, of the number of times the operation is performed until the notebook has all integers from 1 to M written at least once.

Constraints

• 1 \leq M \leq N \leq 2\times 10^5
• 1 \leq C_i
• \sum_{i=1}^{M}C_i=N
• All input values are integers.

Sample Input 1

2 2
1 1

Sample Output 1

3

The series of operations may proceed as follows:

• You draw a card with 1 written on it. The notebook now has one 1 written in it.
• You again draw a card with 1 written on it. The notebook now has two 1s written in it.
• You draw a card with 2 written on it. The notebook now has two 1s and one 2 written in it.

The sought expected value is 2\times\frac{1}{2}+3\times\frac{1}{4}+4\times\frac{1}{8}+\ldots=3.

Sample Input 2

5 2
4 1

Sample Output 2

748683270

The expected value is \frac{21}{4}, whose representation modulo 998244353 is 748683270.

Sample Input 3

50 50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

244742906

The expected value is \frac{13943237577224054960759}{61980890084919934128}.

Sample Input 4

74070 15
1 2 3 11 22 33 111 222 333 1111 2222 3333 11111 22222 33333

Sample Output 4

918012973