Problem Statement

You are given integers a, b, c, and d. Print two lines as follows.

The first line should contain the result of calculating (a + b) \times (c - d) as an integer.
The second line should contain Takahashi, regardless of the input.

Constraints

• -100 \leq a, b, c, d \leq 100
• a, b, c, and d are integers.

Sample Input 1

1 2 5 3

Sample Output 1

6
Takahashi

We have (1 + 2) \times(5 - 3) = 3 \times 2 = 6, so the first line should contain 6.
The second line should contain Takahashi. Lowercasing the first character or incorrect spelling will not be accepted, so be careful.

Sample Input 2

10 -20 30 -40

Sample Output 2

-700
Takahashi

The input or output may contain negative numbers.

Sample Input 3

100 100 100 -100

Sample Output 3

40000
Takahashi

Problem Statement

You are given a string S of length 6. It is guaranteed that the first three characters of S are ABC and the last three characters are digits.

Determine if S is the abbreviation of a contest held and concluded on AtCoder before the start of this contest.

Here, a string T is "the abbreviation of a contest held and concluded on AtCoder before the start of this contest" if and only if it equals one of the following 348 strings:

ABC001, ABC002, \ldots, ABC314, ABC315, ABC317, ABC318, \ldots, ABC348, ABC349.

Note that ABC316 is not included.

Constraints

• S is a string of length 6 where the first three characters are ABC and the last three characters are digits.

Sample Input 1

ABC349

Sample Output 1

Yes

ABC349 is the abbreviation of a contest held and concluded on AtCoder last week.

Sample Input 2

ABC350

Sample Output 2

No

ABC350 is this contest, which has not concluded yet.

Sample Input 3

ABC316

Sample Output 3

No

ABC316 was not held on AtCoder.

Problem Statement

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

If S_{i,j} is #, the cell (i,j) is impassable; if it is ., the cell is passable and contains no house; if it is @, the cell is passable and contains a house.

Initially, Santa Claus is in cell (X,Y). He will act according to the string T as follows.

• Let |T| be the length of the string T. For i=1,2,\ldots,|T|, he moves as follows.
  • Let (x,y) be the cell he is currently in.
    • If T_i is U and cell (x-1,y) is passable, move to cell (x-1,y).
    • If T_i is D and cell (x+1,y) is passable, move to cell (x+1,y).
    • If T_i is L and cell (x,y-1) is passable, move to cell (x,y-1).
    • If T_i is R and cell (x,y+1) is passable, move to cell (x,y+1).
    • Otherwise, stay in cell (x,y).

Find the cell where he is after completing all actions, and the number of distinct houses that he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 3 \leq H,W \leq 100
• 1 \leq X \leq H
• 1 \leq Y \leq W
• All given numbers are integers.
• Each S_{i,j} is one of #, ., @.
• S_{i,1} and S_{i,W} are # for every 1 \leq i \leq H.
• S_{1,j} and S_{H,j} are # for every 1 \leq j \leq W.
• S_{X,Y}= .
• T is a string of length at least 1 and at most 10^4, consisting of U, D, L, R.

Sample Input 1

5 5 3 4
#####
#...#
#.@.#
#..@#
#####
LLLDRUU

Sample Output 1

2 3 1

Santa Claus behaves as follows:

• T_1= L, so he moves from (3,4) to (3,3). A house is passed.
• T_2= L, so he moves from (3,3) to (3,2).
• T_3= L, but cell (3,1) is impassable, so he stays at (3,2).
• T_4= D, so he moves from (3,2) to (4,2).
• T_5= R, so he moves from (4,2) to (4,3).
• T_6= U, so he moves from (4,3) to (3,3). A house is passed, but it has already been passed.
• T_7= U, so he moves from (3,3) to (2,3).

The number of houses he passed or arrived during his actions is 1.

Sample Input 2

6 13 4 6
#############
#@@@@@@@@@@@#
#@@@@@@@@@@@#
#@@@@.@@@@@@#
#@@@@@@@@@@@#
#############
UURUURLRLUUDDURDURRR

Sample Output 2

3 11 11

Sample Input 3

12 35 7 10
###################################
#.................................#
#..........@......................#
#......@................@.........#
#.............##............@.....#
#...##........##....##............#
#...##........##....##.......##...#
#....##......##......##....##.....#
#....##......##......##..##.......#
#.....#######.........###.........#
#.................................#
###################################
LRURRRUUDDULUDUUDLRLRDRRLULRRUDLDRU

Sample Output 3

4 14 1

Problem Statement

At the entrance of AtCoder Land, there is a single ticket booth where visitors line up to purchase tickets one by one. The purchasing process takes A seconds per person. Once the person at the front of the line finishes purchasing their ticket, the next person (if any) immediately starts their purchasing process.

Currently, there is no one in line at the ticket booth, and N people will come to buy tickets one after another. Specifically, the i-th person will arrive at the ticket booth T_i seconds from now. If there is already a line, they will join the end of it; if not, they will start the purchasing process immediately. Here, T_1 < T_2 < \dots < T_N.

For each i\ (1 \leq i \leq N), determine how many seconds from now the i-th person will finish purchasing their ticket.

Constraints

• 1 \leq N \leq 100
• 0 \leq T_1 < T_2 < \dots < T_N \leq 10^6
• 1 \leq A \leq 10^6
• All input values are integers.

Sample Input 1

3 4
0 2 10

Sample Output 1

4
8
14

The events proceed in the following order:

• At 0 seconds: The 1st person arrives at the ticket booth and starts the purchasing process.
• At 2 seconds: The 2nd person arrives at the ticket booth and joins the line behind the 1st person.
• At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person starts the purchasing process.
• At 8 seconds: The 2nd person finishes purchasing their ticket.
• At 10 seconds: The 3rd person arrives at the ticket booth and starts the purchasing process.
• At 14 seconds: The 3rd person finishes purchasing their ticket.

Sample Input 2

3 3
1 4 7

Sample Output 2

4
7
10

The events proceed in the following order:

• At 1 second: The 1st person arrives at the ticket booth and starts the purchasing process.
• At 4 seconds: The 1st person finishes purchasing their ticket, and the 2nd person arrives at the ticket booth and starts the purchasing process.
• At 7 seconds: The 2nd person finishes purchasing their ticket, and the 3rd person arrives at the ticket booth and starts the purchasing process.
• At 10 seconds: The 3rd person finishes purchasing their ticket.

Sample Input 3

10 50000
120190 165111 196897 456895 540000 552614 561627 743796 757613 991216

Sample Output 3

170190
220190
270190
506895
590000
640000
690000
793796
843796
1041216

Problem Statement

Takahashi is managing the number of trees in his garden. Initially, there are no trees in the garden.

Q queries are given in order. Each query is one of the following two types. Immediately after processing each query, output the number of trees currently in the garden.

• 1 h : Add one new tree of height h to the garden.
• 2 h : Remove all trees currently in the garden whose height is at most h.

Constraints

• 1 \le Q \le 3 \times 10^5
• 1 \le h \le 10^9
• All input values are integers.

Sample Input 1

5
1 5
1 7
1 8
2 7
1 3

Sample Output 1

1
2
3
1
2

The number of trees changes as follows.

• A tree of height 5 is added. The garden contains one tree of height 5.
• A tree of height 7 is added. The garden contains two trees of heights 5, 7.
• A tree of height 8 is added. The garden contains three trees of heights 5, 7, 8.
• Trees of height at most 7 are removed. The garden contains one tree of height 8.
• A tree of height 3 is added. The garden contains two trees of heights 8, 3.

Sample Input 2

12
2 256601193
1 85138616
1 202564041
2 276477192
1 55551662
1 170271057
2 754166580
1 854388209
1 772036624
2 651124113
1 301137866
2 290875185

Sample Output 2

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

Problem Statement

Among the positive integers that consist of 0's and 2's when written in base 10, find the K-th smallest integer.

Constraints

• K is an integer between 1 and 10^{18} (inclusive).

Sample Input 1

3

Sample Output 1

22

The positive integers that consist of 0's and 2's when written in base 10 are 2,20,22,\dots in ascending order.
The (K=) 3-rd of them, which is 22, should be printed.

Sample Input 2

11

Sample Output 2

2022

Sample Input 3

923423423420220108

Sample Output 3

220022020000202020002022022000002020002222002200002022002200

Note that the exact value of the answer must be printed as an integer, even if it is big.

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. Each vertex i\,(1\leq i \leq N) has a weight A_i. Each edge j\,(1\leq j \leq M) connects vertices U_j and V_j bidirectionally and has a weight B_j.

The weight of a path in this graph is defined as the sum of the weights of the vertices and edges that appear on the path.

For each i=2,3,\dots,N, solve the following problem:

• Find the minimum weight of a path from vertex 1 to vertex i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_j < V_j \leq N
• (U_i, V_i) \neq (U_j, V_j) if i \neq j.
• The graph is connected.
• 0 \leq A_i \leq 10^9
• 0 \leq B_j \leq 10^9
• All input values are integers.

Sample Input 1

3 3
1 2 3
1 2 1
1 3 6
2 3 2

Sample Output 1

4 9

Consider the paths from vertex 1 to vertex 2. The weight of the path 1 \to 2 is A_1 + B_1 + A_2 = 1 + 1 + 2 = 4, and the weight of the path 1 \to 3 \to 2 is A_1 + B_2 + A_3 + B_3 + A_2 = 1 + 6 + 3 + 2 + 2 = 14. The minimum weight is 4.

Consider the paths from vertex 1 to vertex 3. The weight of the path 1 \to 3 is A_1 + B_2 + A_3 = 1 + 6 + 3 = 10, and the weight of the path 1 \to 2 \to 3 is A_1 + B_1 + A_2 + B_3 + A_3 = 1 + 1 + 2 + 2 + 3 = 9. The minimum weight is 9.

Sample Input 2

2 1
0 1
1 2 3

Sample Output 2

4

Sample Input 3

5 8
928448202 994752369 906965437 942744902 907560126
2 5 975090662
1 2 908843627
1 5 969061140
3 4 964249326
2 3 957690728
2 4 942986477
4 5 948404113
1 3 988716403

Sample Output 3

2832044198 2824130042 4696218483 2805069468

Note that the answers may not fit in a 32-bit integer.

Problem Statement

The Republic of AtCoder has N cities, called City 1, City 2, \ldots, City N. Initially, there was a bidirectional road between every pair of different cities, but M of these roads have become unusable due to deterioration over time. More specifically, for each 1\leq i \leq M, the road connecting City U_i and City V_i has become unusable.

Takahashi will go for a K-day trip that starts and ends in City 1. Formally speaking, a K-day trip that starts and ends in City 1 is a sequence of K+1 cities (A_0, A_1, \ldots, A_K) such that A_0=A_K=1 holds and for each 0\leq i\leq K-1, A_i and A_{i+1} are different and there is still a usable road connecting City A_i and City A_{i+1}.

Print the number of different K-day trips that start and end in City 1, modulo 998244353. Here, two K-day trips (A_0, A_1, \ldots, A_K) and (B_0, B_1, \ldots, B_K) are said to be different when there exists an i such that A_i\neq B_i.

Constraints

• 2 \leq N \leq 5000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},5000 \right)
• 2 \leq K \leq 5000
• 1 \leq U_i<V_i \leq N
• All pairs (U_i, V_i) are pairwise distinct.
• All values in input are integers.

Sample Input 1

3 1 4
2 3

Sample Output 1

4

There are four different trips as follows.

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

No other trip is valid, so we should print 4.

Sample Input 2

3 3 3
1 2
1 3
2 3

Sample Output 2

0

No road remains usable, so there is no valid trip.

Sample Input 3

5 3 100
1 2
4 5
2 3

Sample Output 3

428417047

Problem Statement

There is a skating rink represented by a grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The skating rink has N obstacles. The i-th obstacle is placed at (X_i,Y_i).

In a single move, Takahashi chooses one of the four directions, up, down, left, or right, and keeps moving until he hits an obstacle.
When he hits an obstacle, he stops at the square right before the obstacle. Since the skating rink is surrounded by cliffs, it is prohibited to start a move in which he will never hit an obstacle.

Takahashi is initially at (s_x,s_y). He wants to make some number of moves to stop at (g_x,g_y).

Find the minimum number of moves required to end up at (g_x, g_y). If it is not possible, report the fact.

Constraints

• 1\leq H \leq 10^9
• 1\leq W \leq 10^9
• 1\leq N \leq 10^5
• 1\leq s_x,g_x\leq H
• 1\leq s_y,g_y\leq W
• 1\leq X_i \leq H
• 1\leq Y_i \leq W
• (s_x,s_y)\neq (g_x,g_y)
• (s_x,s_y)\neq (X_i,Y_i)
• (g_x,g_y)\neq (X_i,Y_i)
• If i\neq j, then (X_i,Y_i)\neq (X_j,Y_j).
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

In the figure, (s_x,s_y) is denoted by S and (g_x,g_y) is denoted by G.
By moving as (3,4)\rightarrow(2,4) \rightarrow(2,2) \rightarrow(5,2) \rightarrow(5,6), he can end up at (g_x,g_y) with 4 moves.

Sample Input 2

4 6 2
3 2
3 5
4 5
2 5

Sample Output 2

-1

He must stop at (g_x,g_y).
Note that just passing through (g_x,g_y) is not considered to be ending up at the goal.

Sample Input 3

1 10 1
1 5
1 1
1 7

Sample Output 3

-1

If he chooses to move to the left, Takahashi will fall down the cliff after passing through (g_x,g_y).
Note that it is prohibited to start a move in which he will never hit an obstacle, as the skating rink is surrounded by cliffs.