Problem Statement

A hare and a tortoise are in a race. The first to run X meters wins.

The hare runs A meters per second, and the tortoise runs B meters per second.

However, at \frac{X}{2} meters from the start, the hare stops running and sleeps for C seconds. Then, it wakes up and continues running A meters per second.

Find the winner of the race. If the two finish simultaneously, report that fact.

Constraints

• 1 \leq X \leq 10000
• 1 \leq A, B \leq 100
• 1 \leq C \leq 10000
• All values in input are integers.

Sample Input 1

100 5 3 15

Sample Output 1

Tortoise

The hare runs 50 meters in 10 seconds, sleeps for 15 seconds, and again runs 50 meters in 10 seconds, for a total of 35 seconds.

The tortoise finishes the race in \frac{100}{3} seconds.

We have \frac{100}{3} \lt 35, so the tortoise wins.

Sample Input 2

240 6 2 80

Sample Output 2

Tie

The two finish simultaneously.

Sample Input 3

10000 100 1 1000

Sample Output 3

Hare

Problem Statement

You are given a string S consisting of lowercase English letters.
Now you will write, for every integer i such that 1 \le i \le |S|-1, a two-letter string obtained by concatenating the i-th and the (i+1)-th characters of S.
Find the string that you will write the most times. If there are multiple such strings, find the lexicographically smallest one.

Constraints

• 2 \le |S| \le 2 \times 10^5
• S consists of lowercase English letters.

Sample Input 1

abcab

Sample Output 1

ab

You will write ab, bc, ca, and ab.
Among them, ab is written the most times.

Sample Input 2

zyxwv

Sample Output 2

wv

Sample Input 3

iiiiiiiiiiiiiiiiiiiiiiiiiiiiii

Sample Output 3

ii

Problem Statement

For integers N and M, let us define S_{N,M} as follows.

• S_{N,M} is a string of length M consisting of o and x.
• The k-th character from the beginning of S_{N,M} is o if N^k≤10^9 and x otherwise.

Given the integers N and M, print S_{N,M}.

Constraints

• N and M are integers.
• 1≤N≤10^9
• 1≤M≤10^5

Sample Input 1

1000 5

Sample Output 1

oooxx

S_{1000,5} is found as follows.

• The 1-st character from the beginning is o because 1000^1=10^3≤10^9.
• The 2-nd character from the beginning is o because 1000^2=10^6≤10^9.
• The 3-rd character from the beginning is o because 1000^3=10^9≤10^9.
• The 4-th character from the beginning is x because 1000^4=10^{12}>10^9.
• The 5-th character from the beginning is x because 1000^5=10^{15}>10^9.

Sample Input 2

2 30

Sample Output 2

ooooooooooooooooooooooooooooox

Sample Input 3

31622 30

Sample Output 3

ooxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Problem Statement

We have pairs of lowercase English letters (a_1,b_1),(a_2,b_2),\dots,(a_N,b_N).

Two lowercase English letters u and v are said to be similar if there exists i such that (u,v)=(a_i,b_i) or (u,v)=(b_i,a_i).

Two strings U and V with the same length are said to be similar if U and V satisfy the following condition:

• You can make U equal V by repeatedly (possibly zero times) choosing one of the characters of U and replacing it with a similar character.

Given strings S and T with the same length, determine if S and T are similar.

Constraints

• 1 \leq N \leq 325
• N is an integer.
• a_i and b_i are distinct lowercase English letters.
• If i \neq j, then (a_i,b_i) \neq (a_j,b_j) and (a_i,b_i) \neq (b_j,a_j).
• S and T are strings of length between 1 and 100, inclusive.
• S and T have the same length.

Sample Input 1

1
m n
man
nan

Sample Output 1

Yes

We can make S equal T by replacing the 1-st character of S with n, making S nan. Since m and n are similar characters, S and T satisfy the condition of similar strings.

Sample Input 2

1
m n
man
men

Sample Output 2

No

Sample Input 3

3
a b
a e
d e
abc
edc

Sample Output 3

Yes

Sample Input 4

1
a b
xyz
xyz

Sample Output 4

Yes

Problem Statement

Find the N-th term of the sequence A constructed as follows.

• Initially, A is empty.
• For every integer i from 1 through 10^{100} in ascending order, do the following.
  • If i \ge 2, append i,i-1,\dots,2 in this order to the end of A.
  • Then, append 1,2,\dots,i in this order to the end of A.

Constraints

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

Sample Input 1

10

Sample Output 1

4

We have A=(1,2,1,2,3,2,1,2,3,4,3,2,1,2,3,4,\dots), where the 10-th term is 4.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

123456789012345678

Sample Output 3

268452372

Input may not fit into a 32-bit integer.

Problem Statement

Takahashi is playing with a shooter video game. The game screen has a grid with H horizontal rows and W vertical columns. The square at the i-th (1 \leq i \leq H) row from the top and j-th (1 \leq j \leq W) column from the left in the grid is called (i, j). Each square is either an empty square or a brick square. Each brick square is painted in the color represented by a positive integer.

The state of Square (i, j) is expressed by a non-negative integer S_{i, j}. If S_{i,j} = 0, then the square is an empty square; if S_{i, j} is a positive integer, then the square is a brick square of color S_{i, j}.

Let us call a brick square in the row other than the H-th row from the top a floating brick if the adjacent square below is an empty square. Initially, there is no floating brick.

Now, Takahashi will do N operations, the i-th (1 \leq i \leq N) of which is as follows:

• Shoot Square (r_i, c_i). If the square is an empty square, nothing happens; if it is a brick square, it changes to an empty square.
• Then, all the floating bricks fall. Strictly speaking, the following operation is performed until there is no floating brick:
  • Choose one floating brick and swap that square with the adjacent square below.

Print the state of each square after the N operations have finished, in the same format as S_{i, j}.

Constraints

• 1 \leq H, W \leq 100
• 0 \leq S_{i, j} \leq 10^9 \, (1 \leq i \leq H, 1 \leq j \leq W)
• If S_{i, j} > 0, then S_{i + 1, j} > 0 \, (1 \leq i \leq H - 1, 1 \leq j \leq W).
• 1 \leq N \leq 10^3
• 1 \leq r_i \leq H \, (1 \leq i \leq N)
• 1 \leq c_i \leq W \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

0 0 0
1 1 0
3 2 4

When he shoots Square (3, 2), the grid transitions as follows:

0 1 0 \quad       0 1 0 \quad       0 1 0 \quad       0 0 0
1 2 0 \rightarrow 1 2 0 \rightarrow 1 0 0 \rightarrow 1 1 0
3 4 4 \quad       3 0 4 \quad       3 2 4 \quad       3 2 4

Sample Input 2

1 1
1
1
1 1

Sample Output 2

0

Sample Input 3

2 3
18459 0 35959
150312 573935 612940
3
2 3
1 2
1 1

Sample Output 3

0 0 0
150312 573935 35959

Problem Statement

You are given an undirected graph with N vertices and N-1 edges. The i-th (1 \leq i \leq N-1) edge connects Vertex A_i and Vertex B_i.

Determine whether the given graph is a tree.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \lt B_i \leq N
• (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
• All values in input are integers.

Sample Input 1

4
1 3
3 4
2 3

Sample Output 1

Yes

The figure below illustrates the given graph.

Sample Input 2

4
1 2
2 3
1 3

Sample Output 2

No

The figure below illustrates the given graph.

Problem Statement

Takahashi has N snacks. For i = 1, 2, \ldots, N, the i-th snack has a weight of w_i and a tastiness of v_i.

Takahashi is going to choose any number (possibly 0) of the N snacks to take on tomorrow's school trip. Takahashi has two knapsacks. Every snack he takes on the school trip should fit in one of the two knapsacks. Here, the sum of weights of snacks in the first knapsack should be at most A, and the sum of weights of snacks in the second knapsack should be at most B.

Find the maximum possible total tastiness of snacks that he can take on the school trip.

Constraints

• 1 \leq N \leq 100
• 1 \leq A, B \leq 300
• 1 \leq w_i \leq 300
• 1 \leq v_i \leq 10^9
• All values in input are integers.

Sample Input 1

6 8 9
2 6
4 1
5 9
3 1
5 3
5 8

Sample Output 1

24

He can put the 1-st and the 3-rd snacks in the first knapsack, and the 2-nd and the 6-th snacks in the second knapsack.
Then, the sum of weights of the snacks in the first knapsack is w_1 + w_3 = 2 + 5 = 7, and the sum of the snacks in the second knapsack is w_2 + w_6 = 4 + 5 = 9, which do not exceed the upper limits of the respective knapsacks, A = 8, B = 9.
The total tastiness of the snacks he will take on the school trip is v_1 + v_2 + v_3 + v_6 = 6 + 1 + 9 + 8 = 24, which is the maximum.

Sample Input 2

20 70 60
7 94
18 33
14 26
10 1
9 57
2 80
19 74
16 10
15 18
10 38
13 90
12 23
3 3
8 11
18 10
3 42
3 66
3 90
10 2
5 45

Sample Output 2

772

Problem Statement

You are given a rectangular grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and the j-th column from the left is called Sqaure (i, j).

Each square is either a "square without a wall" or a "square with a wall". The initial state of Square (i, j) is represented by S_{i,j}, which means:

• .: it is a square without a wall.
• s: it is a square without a wall, and Snuke is there.
• a: it is a square without a wall, and there is a cargo in it.
• g: it is a square without a wall, and is a destination of the cargo.
• #: it is a square with a wall, which cannot be visited.

It is guaranteed that there is exactly one cargo, one destination, and one Snuke in the grid. Snuke's objective is to carry the cargo to the destination.

Snuke can do one of the following moves any number of times:

• Move to a square, without the cargo or a wall, vertically or horizontally adjacent to Snuke's current square.
• Push the cargo in the square vertically or horizontally adjacent to Snuke's current square to the next square without a wall in the direction of the cargo from Snuke, and move to the square that the cargo was originally in.

Print the minimum number of moves required for Snuke to achieve the objective. If the objective is unachievable, print -1 instead.

Constraints

• H and W are integers between 1 and 50, inclusive.
• S_i is a string of length W consisting of ., s, a, g, and #.
• S_{i,j} contains exactly one s, one a, and one g.

Sample Input 1

3 3
s..
.a.
..g

Sample Output 1

5

He can carry the cargo with 5 moves by moving as follows:

• Move to the right.
• Push the cargo downward, and move downward.
• Move to the left.
• Move downward.
• Push the cargo to the right, and move to the right.

Sample Input 2

4 4
s...
.a#.
....
###g

Sample Output 2

13

Sample Input 3

4 4
...a
.s..
..g.
....

Sample Output 3

-1

If the objective is unachievable, print -1.

Problem Statement

You eat an apple every Saturday and Sunday. You do not eat one any other day.

Given two dates S and T in YYYY-MM-DD format, find the number of apples you eat between S and T (inclusive).

Here are some facts that may be useful.

• January 1, 2022 is Saturday.
• The year X is a leap year if and only if one of the following is satisfied.
  • X is a multiple of 4 but not a multiple of 100
  • X is a multiple of 400

Constraints

• S and T are valid dates between January 1, 2022 and December 31, 9999 (inclusive) in YYYY-MM-DD format.
• T is not earlier than S.

Sample Input 1

2022-01-01
2022-01-08

Sample Output 1

3

During the given period, you eat an apple on January 1, 2, and 8 in 2022.

Sample Input 2

2024-02-26
2024-03-02

Sample Output 2

1

Beware the leap years.

Sample Input 3

2022-01-01
9999-12-31

Sample Output 3

832544

Problem Statement

You are given two strings S and T. Find the number of strings that are subsequences of at least one of S and T, modulo 998244353.

Here, a string A is said to be a subsequence of string B when the length of A is at least 1 and A can result from removing zero or more characters from B. For example, atcoder and ac are subsequences of atcoder, while atcoderr and ca are not.

Constraints

• 1 \leq \lvert S\rvert, \lvert T\rvert \leq 1000
• S and T consist of lowercase English letters.

Sample Input 1

abc
bca

Sample Output 1

10

S= abc has seven subsequences: a, b, c, ab, ac, bc, abc, while T= bca has seven subsequences: b, c, a, bc, ba, ca, bca. Therefore, we have ten strings that are subsequences of at least one of them: a, b, c, ab, ac, ba, bc, ca, abc, bca.

Sample Input 2

aa
aaaaa

Sample Output 2

5

The sought strings are a, aa, aaa, aaaa, aaaaa.

Sample Input 3

xzyyzxxzyy
yzxyzyxzyx

Sample Output 3

758

Problem Statement

You are given strings S and T consisting of lowercase English letters. You can do the following operation between 0 and K times: choose one of the characters of S and replace it with any lowercase English letter.

What is the length of the longest possible string that is a subsequence of S after the replacements and also a subsequence of T?
Here, a string x is said to be a subsequence of a string y if x can result from removing zero or more characters from y and concatenating the remaining strings without changing the order.

Constraints

• 1 \leq |S|, |T| \leq 1000
• 1 \leq K \leq 10
• S and T consist of lowercase English letters.

Sample Input 1

strength
slang
1

Sample Output 1

4

By replacing the 3-rd character of S with l, slng becomes a subsequence of both S and T.

Since it is impossible to have a subsequence of both S and T of length 5 or longer, 4 should be printed.

Sample Input 2

asdbvaklwebjkalhakslhgweqwbq
obqweogkmawgjkoanboebeoqejkazxcnmvqse
10

Sample Output 2

19

Problem Statement

Takahashi and Aoki will play a match where the first to win N games wins. The two players are equally skilled, and each of them wins a game with probability \frac{1}{2}, independently of the outcomes of the other games. There are no draws.

A reversal is said to occur when the player with more wins changes in two games, as in going from 2-1 to 2-3 (now Aoki is in the lead).

Find the expected value of the number of reversals until one player wins the match, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is a rational number. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there uniquely exists one integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.

Constraints

• 2 \leq N \leq 10^7
• All values in input are integers.

Sample Input 1

2

Sample Output 1

748683265

There is one reversal only in the two scenarios below, and no reversal in the other scenarios.

• Takahashi wins, then Aoki wins, then Aoki wins.
• Aoki wins, then Takahashi wins, then Takahashi wins.

Each of them occurs with probability \frac{1}{8}, so the sought expected value is \frac{1}{4}.

We have 748683265 \times 4 \equiv 1\pmod{998244353}, so print 748683265.

Sample Input 2

4

Sample Output 2

405536769

Sample Input 3

621998

Sample Output 3

76706976

Problem Statement

There is a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and the j-th column from the left is called (i, j). The state of each square is either an "empty square" or a "square with a wall". Initially, every square is an empty square.

Ms. A wants to travel on the grid from (1, 1) to (H, W). When Ms. A is at (i, j), she may move to one of (i+1,j),(i,j+1),(i-1,j), and (i,j-1). She cannot go outside the grid or move to the square with a wall.

Ms. B has decided to choose some of the squares to build walls so that it is impossible for Ms. A to reach (H, W) no matter how she moves.
It costs Ms. B c_{i, j} yen (the currency in Japan) to build a wall on (i, j). She cannot build a wall on (1, 1) or (H, W).

What is the minimum cost Ms. B has to pay so that the condition is satisfied? Also, print the way of building walls to achieve the minimum cost.

Constraints

• 2 \leq H, W \leq 20
• 1 \leq c_{i,j} \leq 10^9 (1 \leq i \leq H, 1 \leq j \leq W, (i,j) \neq (1,1), (i,j) \neq (H,W))
• c_{1,1} = c_{H,W} = 0
• All values in input are integers.

Sample Input 1

2 3
0 6 4
2 3 0

Sample Output 1

7
..#
.#.

If Ms. B pays 7 yen to build walls on (1, 3) and (2, 2), Ms. A will be unable to reach (2, 3).
Since it is impossible to satisfy the condition with less cost, this is the answer.

Sample Input 2

4 3
0 9 2
9 3 9
2 3 9
3 9 0

Sample Output 2

7
..#
.#.
#..
...

Sample Input 3

2 2
0 1000000000
1000000000 0

Sample Output 3

2000000000
.#
#.

Problem Statement

There is a coordinate plane P.
Consider performing operations of plotting points in this plane and deleting them. Initially, no points are plotted in P.
Process a total of Q queries in the following forms in the given order.

+ x y

Plot a point at (x,y) in P.

- x y

Delete a point plotted at (x,y) in P.

After processing each query, answer the following question.
Consider all (unordered) pairs of points currently plotted in P; there are \frac{k(k-1)}{2} such pairs, where k is the current number of points plotted in P.
Find the sum of the following value (which is always an integer) over all those pairs modulo 998244353: the doubled area of the triangle whose vertices are the origin (the point (0,0)) and the points in the pair (if these three points lie on the same line, the area is assumed to be 0).

Constraints

• 1 \le Q \le 3 \times 10^5
• For each + query, -10^5 \le x,y \le 10^5 and (x,y) \neq (0,0).
• At each - query, at least one point is plotted at (x,y).
• All values in input are integers.

Sample Input 1

5
+ 2 3
+ -1 2
+ 1 -2
- -1 2
+ -1 -1

Sample Output 1

0
7
14
7
11

• The 1-st query plots a point at (2,3).
  • At this point, the answer to the question is 0.
• The 2-nd query plots a point at (-1,2).
  • The area of the triangle with the vertices (2,3),(-1,2),(0,0) is \frac{7}{2}.
  • At this point, the total area of the triangles is \frac{7}{2}, so the answer to the question is 7.
• The 3-rd query plots a point at (1,-2).
  • The area of the triangle with the vertices (2,3),(1,-2),(0,0) is \frac{7}{2}.
  • The area of the triangle with the vertices (-1,2),(1,-2),(0,0) is assumed to be 0 since these three points lie on the same line.
  • At this point, the total area of the triangles is 7, so the answer to the question is 14.
• The 4-th query deletes a point at (-1,2).
  • At this point, the total area of the triangles is \frac{7}{2}, so the answer to the question is 7.
• The 5-th query plots a point at (-1,-1).
  • The area of the triangle with the vertices (1,-2),(-1,-1),(0,0) is \frac{3}{2}.
  • The area of the triangle with the vertices (-1,-1),(2,3),(0,0) is \frac{1}{2}.
  • At this point, the total area of the triangles is \frac{11}{2}, so the answer to the question is 11.

Sample Input 2

10
+ 100000 100000
+ 100000 -100000
+ 100000 100000
+ 100000 -100000
+ 100000 100000
- 100000 100000
- 100000 -100000
- 100000 100000
- 100000 -100000
- 100000 100000

Sample Output 2

0
35112940
70225880
140451760
210677640
140451760
70225880
35112940
0
0

Be sure to find the sought sum modulo 998244353.
Also, multiple points may be plotted at the same coordinates.
Note that when deleting a point, just one point is deleted, not all of them at the specified coordinates.

Sample Input 3

10
+ -5010 51358
+ 95817 96893
+ 19668 -58533
- 95817 96893
- -5010 51358
+ 90155 -74912
- 90155 -74912
+ -83888 -29953
- -83888 -29953
+ 72565 37307

Sample Output 3

0
415181651
660233626
716858814
0
808940340
0
508110143
0
988223809