Problem Statement

Keyence has a culture of addressing everyone with the honorific "san," regardless of their role, age, or position. Even a new employee would call the president "Nakata-san." [Translator's note: this is a bit unusual in Japan.]

You are given a person's surname and first name as strings S and T, respectively.

Print the concatenation of the surname, a space ( ), and the honorific (san) in this order.

Constraints

• Each of S and T is a string that satisfies the following conditions.
  • The length is between 1 and 10, inclusive.
  • The first character is an uppercase English letter.
  • All characters except the first one are lowercase English letters.

Sample Input 1

Takahashi Chokudai

Sample Output 1

Takahashi san

Print the concatenation of the surname (Takahashi), a space ( ), and the honorific (san) in this order.

Sample Input 2

K Eyence

Sample Output 2

K san

Problem Statement

The following five days are called the five seasonal festivals (gosekku).

• January \color{red}{\mathbf{7}}
• March 3
• May 5
• July 7
• September 9

If month M, day D is one of the five seasonal festivals, output Yes; otherwise, output No.

Constraints

• M and D are integers.
• Month M, day D is a valid date in a leap year in the Gregorian calendar.

Sample Input 1

3 3

Sample Output 1

Yes

March 3 is one of the five seasonal festivals, so output Yes.

Sample Input 2

1 1

Sample Output 2

No

January 1 is not one of the five seasonal festivals, so output No.

Sample Input 3

4 4

Sample Output 3

No

Sample Input 4

11 7

Sample Output 4

No

Problem Statement

There are N countries numbered 1 to N. For each i = 1, 2, \ldots, N, Takahashi has A_i units of the currency of country i.

Takahashi can repeat the following operation any number of times, possibly zero:

• First, choose an integer i between 1 and N-1, inclusive.
• Then, if Takahashi has at least S_i units of the currency of country i, he performs the following action once:
  • Pay S_i units of the currency of country i and gain T_i units of the currency of country (i+1).

Print the maximum possible number of units of the currency of country N that Takahashi could have in the end.

Constraints

• All input values are integers.
• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 1 \leq T_i \leq S_i \leq 10^9

Sample Input 1

4
5 7 0 3
2 2
4 3
5 2

Sample Output 1

5

In the following explanation, let the sequence A = (A_1, A_2, A_3, A_4) represent the numbers of units of the currencies of the countries Takahashi has. Initially, A = (5, 7, 0, 3).

Consider performing the operation four times as follows:

• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (5, 3, 3, 3).
• Choose i = 1, pay two units of the currency of country 1, and gain two units of the currency of country 2. Now, A = (3, 5, 3, 3).
• Choose i = 2, pay four units of the currency of country 2, and gain three units of the currency of country 3. Now, A = (3, 1, 6, 3).
• Choose i = 3, pay five units of the currency of country 3, and gain two units of the currency of country 4. Now, A = (3, 1, 1, 5).

At this point, Takahashi has five units of the currency of country 4, which is the maximum possible number.

Sample Input 2

10
32 6 46 9 37 8 33 14 31 5
5 5
3 1
4 3
2 2
3 2
3 2
4 4
3 3
3 1

Sample Output 2

45

Problem Statement

This problem shares a similar setting with Problem A. The way Takahashi chooses cookies and what you are required to find are different from Problem A.

There are N boxes arranged in a row, and some of these boxes contain cookies.

The state of these boxes is represented by a string S of length N. Specifically, the i-th box (1\leq i \leq N) from the left contains one cookie if the i-th character of S is @, and is empty if it is ..

Over the next D days, Takahashi will choose and eat one cookie per day from among the cookies in these boxes. On each day, he chooses the cookie in the rightmost box that contains a cookie at that point.

Determine, for each of the N boxes, whether it will contain a cookie after D days have passed.

It is guaranteed that S contains at least D occurrences of @.

Constraints

• 1 \leq D \leq N \leq 100
• N and D are integers.
• S is a string of length N consisting of @ and ..
• S contains at least D occurrences of @.

Sample Input 1

5 2
.@@.@

Sample Output 1

.@...

Takahashi acts as follows:

• Day 1: There are cookies in the 2nd, 3rd, and 5th boxes from the left. Among these, the rightmost is the 5th box. He eats the cookie in this box.
• Day 2: There are cookies in the 2nd and 3rd boxes. Among these, the rightmost is the 3rd box. He eats the cookie in this box.
• After two days have passed, only the 2nd box from the left contains a cookie.

Therefore, the correct output is .@....

Sample Input 2

3 3
@@@

Sample Output 2

...

Sample Input 3

10 4
@@@.@@.@@.

Sample Output 3

@@@.......

Problem Statement

There is a grid with H rows and W columns.
The cell at the i-th row from the top and j-th column from the left is painted black if S_{i,j} is #, and white if S_{i,j} is ..

Among the four-directionally connected regions consisting of white cells, find the number of those that are surrounded by black cells.

Below is a more formal statement.

We denote the cell at the i-th row from the top and j-th column from the left as cell (i, j).
Two cells (i, j) and (i', j') are said to be adjacent if and only if |i-i'|+|j-j'|=1.
A set C of white cells is said to be connected if and only if, for any two cells c and c' in C, it is possible to move from c to c' by repeatedly moving to an adjacent cell in C.
A non-empty connected set of white cells that is maximal is called a connected component of white cells.
Find the number of connected components of white cells that do not contain any cell on the outermost border of the grid (that is, in row 1, row H, column 1, or column W).

Constraints

• 3 \leq H, W \leq 10^3
• H and W are integers.
• S_{i,j} is # or ..

Sample Input 1

5 15
##########..###
#...#######.###
####....###..##
######.########
########....###

Sample Output 1

2

There are two such regions: the region consisting of the three cells in row 2 from the top and columns 2, 3, 4 from the left, and the region consisting of a total of five cells: columns 5, 6, 7, 8 from the left in row 3 from the top and column 7 from the left in row 4 from the top.

Sample Input 2

10 22
######################
####.#################
###...################
##.###.##.....########
##.....##.####.#######
.######.#......#.....#
.######.#.####.#.#####
#########.....##.#####
################.#####
################.....#

Sample Output 2

4

Problem Statement

Given an integer N, solve the following problem.

Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.

Constraints

• N is an integer.
• 1 \le N < 10^{18}

Sample Input 1

16

Sample Output 1

73

• For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
  • Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
• For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
  • Thus, we have f(10)=1,f(11)=2,...,f(16)=7.

The final answer is 73.

Sample Input 2

238

Sample Output 2

13870

Sample Input 3

999999999999999999

Sample Output 3

762062362

Be sure to find the sum modulo 998244353.

Problem Statement

Given an integer N, find the smallest integer X that satisfies all of the conditions below.

• X is greater than or equal to N.
• There is a pair of non-negative integers (a, b) such that X=a^3+a^2b+ab^2+b^3.

Constraints

• N is an integer.
• 0 \le N \le 10^{18}

Sample Input 1

9

Sample Output 1

15

For any integer X such that 9 \le X \le 14, there is no (a, b) that satisfies the condition in the statement.
For X=15, (a,b)=(2,1) satisfies the condition.

Sample Input 2

0

Sample Output 2

0

N itself may satisfy the condition.

Sample Input 3

999999999989449206

Sample Output 3

1000000000000000000

Input and output may not fit into a 32-bit integer type.

Problem Statement

You are given an integer sequence A=(A_1, A_2, \dots, A_N) of length N.

You are given Q queries, which you should process in order. Each query is in one of the following formats:

• 1 x y : Change the value of A_x to y.
• 2 l r : Find the value of \displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)).

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq Q \leq 2\times 10^5
• 0\leq A_i \leq 5\times 10^5
• For queries of the first type,
  • 1\leq x\leq N
  • 0\leq y \leq 5\times 10^5
• For queries of the second type,
  • 0\leq l,r \leq 5\times 10^5
• All inputs are integers.

Sample Input 1

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

Sample Output 1

11
12

Initially, A=(4,3,2).

• First query: Change the value of A_1 to 7. A becomes (7,3,2).
• Second query: Output \max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11.
• Third query: Change the value of A_2 to 0. A becomes (7,0,2).
• Fourth query: Output \max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12.

Sample Input 2

8 10
320 578 244 604 145 839 156 857
2 400 556
1 5 168
2 254 62
2 145 301
1 1 23
1 3 0
2 413 758
2 297 613
1 8 451
2 598 692

Sample Output 2

3824
2032
2073
4350
3596
4884

Problem Statement

There are N points equally spaced on a circle, numbered 1,2,\dots,N clockwise.

You are given Q queries of the following form; process them in order.

• Draw the line segment connecting points A_i and B_i. However, if this segment intersects a segment that has already been drawn, do not draw it.

Here, it is guaranteed that the 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are all distinct.

For each query, answer whether the segment was drawn.

Constraints

• 2 \leq N \leq 10^6
• 1 \leq Q \leq 3\times 10^5
• 1 \leq A_i < B_i \leq N
• The 2Q integers A_1,\ldots,A_Q,B_1,\ldots,B_Q are pairwise distinct.
• All input values are integers.

Sample Input 1

8 3
1 5
2 7
3 4

Sample Output 1

Yes
No
Yes

By the queries, the segments are drawn as in the figure.

• In the 1-st query, the segment connecting points 1 and 5 is drawn.
• In the 2-nd query, the segment connecting points 2 and 7 is not drawn because it intersects the segment drawn in the 1-st query.
• In the 3-rd query, the segment connecting points 3 and 4 is drawn.

Sample Input 2

999999 4
123456 987654
888888 999999
1 3
2 777777

Sample Output 2

Yes
No
Yes
No