Problem Statement

Takahashi has come to an amusement park. To get on the ride in this park, one must meet all of the following restrictions.

• Must be at least H centimeters tall.
• Must weigh at most W kilograms.

Takahashi is h centimeters tall and weighs w kilograms. Can he get on the ride?

Constraints

• 100 \leq H,h \leq 200
• 50 \leq W,w \leq 100
• All values in input are integers.

Sample Input 1

150 90
100 70

Sample Output 1

No

He does not meet the height restriction.

Sample Input 2

123 85
199 99

Sample Output 2

No

He does not meet the weight restriction.

Sample Input 3

100 100
200 50

Sample Output 3

Yes

Problem Statement

There are six kinds of coins used in Japan now: 1-yen, 5-yen, 10-yen, 50-yen, 100-yen, and 500-yen coins. Two of them, 5-yen and 50-yen coins, have holes in them.

Takahashi runs a shop somewhere in Japan. One day, N customers visited his shop. The i-th customer paid B_i yen for a product worth A_i yen, and Takahashi gave each customer the change using the minimum number of coins.

Among the coins used as the changes on that day, how many had holes in them?

Here, assume that Takahashi had enough of each kind of coin.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq B_i \leq 10^3
• All values in input are integers.

Sample Input 1

2
40 100
105 120

Sample Output 1

2

To the 1-st customer, he gives 60 yen as the change, using one 10-yen coin and one 50-yen coin to minimize the number of coins.

To the 2-nd customer, he gives 15 yen as the change, using one 5-yen coin and one 10-yen coin to minimize the number of coins.

Among these coins, 2 of them have holes in them.

Sample Input 2

6
1 2
1 6
1 11
1 51
1 101
1 501

Sample Output 2

2

Problem Statement

In some contest hold on AtCoder, there were 6 problems: A , B , C , D , E , and F, and a total of N submissions. These N submissions, which were all made at distinct times, got assigned IDs 1, 2, \ldots, N in chronological order. The verdict of every submission is AC or WA, and for every problem, there was at least one submission with the verdict AC. Specifically, the submission with ID i is a submission to Problem P_i (where P_i is A , B , C , D , E , or F), with the verdict V_i (where V_i is AC or WA).

For each problem from A through F, find the ID of the first submission that got AC on that problem, that is, find the submission with the minimum ID among the ones made to that problem that got the verdict AC.

Constraints

• 6 \leq N\leq 1000
• P_i is A , B , C , D , E , or F.
• V_i is AC or WA.
• For each problem, there is at least one submission with the verdict AC.

Sample Input 1

8
A AC
B WA
C AC
B AC
A AC
D AC
E AC
F AC

Sample Output 1

1
4
3
6
7
8

The first five submissions were made to Problems A, B, and C, as follows.

• The submission with the ID 1 got AC on Problem A, which was the first AC on this problem.
• The submission with the ID 2 was made to Problem B but got WA, so this was not the first AC on this problem.
• The submission with the ID 3 got AC on Problem C, which was the first AC on this problem.
• The submission with the ID 4 got AC on Problem B, which was the first AC on this problem.
• The submission with the ID 5 got AC on Problem A, but the submission with the ID 1 already got AC on this problem, so this was not the first AC on it.

Summing up these and the submissions to Problems D, E, F, the IDs of the first submissions that got AC on the respective problems are 1, 4, 3, 6, 7, 8.

Problem Statement

There are N students in AtCoder High School, given student IDs and called Student 1, Student 2, \ldots, Student N. One day, all of them took tests in math and English, and Student i (1 \leq i \leq N) scored A_i in math and B_i in English. In this school, the students are ranked as follows.

• A student with a higher total score in math and English ranks higher.
• When students have the same total score, a student with a higher score in math ranks higher.
• When students have both the same total score and the same score in math, a student with a smaller student ID ranks higher.

Print the student IDs of the N students in descending order of rank.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
5 10 10 12 5
10 10 5 0 10

Sample Output 1

2 3 1 5 4

The students are ranked as follows.

• The respective students' total scores in math and English are 15, 20, 15, 12, 15, so Student 2 comes 1-st, Students 1, 3, 5 come 2-nd, 3-rd, 4-th in some order, and Student 4 comes 5-th.
• Students 1, 3, 5, with the same total score in math and English, scored 5, 10, 5 in math, respectively, so Student 3 comes 2-nd, and Students 1, 5 come 3-rd, 4-th in some order.
• Since Students 1 and 5 have both the same total score and the same score in math, Student 1, with the smaller student ID, comes 3-rd, and Student 5, with the larger student ID, comes 4-th.

Therefore, the students are ranked in the order 2, 3, 1, 5, 4 from top to bottom.

Sample Input 2

2
0 1000000000
0 1000000000

Sample Output 2

2 1

Problem Statement

Takahashi will enter an integer N using a keyboard.
When entering the digits, he will use the left hand for 1, 2, 3, 4, 5, and the right hand for 6, 7, 8, 9, 0.
The time it takes for him to enter each digit is as follows.

• If the digit to enter is the top digit of the integer, it takes 500 milliseconds, regardless of what that digit is.
• Otherwise, if the digit to enter is the same as the previous digit, it takes 301 milliseconds.
• If none of the above applies, and the digit to enter is entered by the same hand as the hand used to enter the previous digit, it takes 210 milliseconds.
• If none of the above applies, it takes 100 milliseconds.

The total time to enter the integer is the sum of the times to enter the respective digits. Print the time it takes for Takahashi to enter the integer N, in milliseconds.

Constraints

• 1 \leq N < 10^{200000}
• The top digit of N is not 0.
• N is an integer.

Sample Input 1

1120

Sample Output 1

1111

• First, it takes 500 milliseconds to enter the top digit 1.
• The next digit is 1, which is the same digit as the previous, so it takes 301 milliseconds to enter it.
• The next digit is 2, which is a different digit from the previous but entered by the left hand again, so it takes 210 milliseconds to enter it.
• The last digit is 0, which is a different digit from the previous and entered by the other hand, so it takes 100 milliseconds to enter it.

Therefore, it takes a total of 500+301+210+100=1111 milliseconds to enter 1120.

Sample Input 2

8

Sample Output 2

500

N has just one digit, so the time it takes to enter it is equal to the time it takes to enter the top digit, which is 500 milliseconds.

Sample Input 3

12345678901234567890

Sample Output 3

4160

Problem Statement

We have a grid with 9 rows arranged vertically and 9 columns arranged horizontally. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

Initially, there is a piece on (A, B), and no piece on the other squares.

In one move, the piece can move to some of the squares vertically, horizontally, or diagonally adjacent to the square it is on now. The specific set of squares that the piece can move to is described by three strings S_1, S_2, S_3 of length 3 each. When the piece is on some square (x, y),

• if the j-th character of S_i is #, it can move to (x+i-2,y+j-2) in one move;
• if the j-th character of S_i is ., it cannot move to (x+i-2,y+j-2) in one move.

Here, it is not allowed to exit the grid.

Find the number of squares that the piece can reach by zero or more moves.

Constraints

• 1 \leq A,B \leq 9
• Each of S_1,S_2,S_3 is a string of length 3 consisting of # and ..
• The 2-nd character of S_2 is ..
• A,B are integers.

Sample Input 1

2 2
###
#..
...

Sample Output 1

5

The piece can reach the following five squares: (1,1), (1,2), (1,3), (2,1), and (2,2).

Sample Input 2

5 4
###
#.#
###

Sample Output 2

81

The piece can reach all squares.

Sample Input 3

9 9
...
...
..#

Sample Output 3

1

The piece cannot move from the starting square (9, 9).

Problem Statement

There is an undirected graph with N vertices. Initially, no two vertices are connected by an edge.
Process the Q queries in the order they are given.
There are two kinds of queries shown below.

• 1 u v: If there is no edge directly connecting Vertex u and Vertex v, add an undirected edge connecting them; if there is such an edge, delete it.

• 1 u v: If it is possible to get from Vertex u to Vertex v by traversing edges, print Yes; otherwise, print No.

Constraints

• 2 \leq N \leq 100
• 1 \leq Q \leq 10000
• 1 \leq u,v \leq N
• u \neq v
• There is at least one query of the second kind.
• All values in input are integers.

Sample Input 1

3 5
1 1 2
1 3 2
2 1 3
1 2 1
2 1 3

Sample Output 1

Yes
No

• Just before the 1-st query, Vertex 1 and Vertex 2 are not connected by an edge, so we add an edge.
• Just before the 2-nd query, Vertex 3 and Vertex 2 are not connected by an edge, so we add an edge.
• At the time of the 3-rd query, we can traverse the edges added in the 1-st and 2-nd queries to go Vertex 1 \to Vertex 2 \to Vertex 3, so we print Yes.
• Just before the 4-th query, Vertex 3 and Vertex 2 are directly connected by an edge, so we delete it.
• At the time of the 5-th query, only the edge connecting Vertex 1 and Vertex 2 exists, which does not enable us to get from Vertex 1 to Vertex 3, so we print No.

Problem Statement

Given are two strings S and T consisting of lowercase English letters.
Let us choose a (not necessarily contiguous) subsequence S' of S and a (not necessarily contiguous) subsequence T' of T so that |S'| = |T'|.
Here, find the maximum possible number of indices i (1 \leq i \leq |S'|) such that the i-th character of S' and the i-th character of T' are different.

Constraints

• S and T are strings consisting of lowercase English letters.
• 1 \leq |S|, |T| \leq 5000

Sample Input 1

abc
aba

Sample Output 1

2

If we choose ab as the string S' and ba as T', there are two indices i (1 \leq i \leq |S'|) such that the i-th character of S' and the i-th character of T' are different, which is the maximum possible.

Sample Input 2

aaaaaa
a

Sample Output 2

0

Sample Input 3

abra
cadabra

Sample Output 3

4

Problem Statement

There is an N-story building, with stairs and M direct elevators. (Here, the lowest floor is called the 1-st floor.)

Using stairs, it is possible to travel between the i-th and (i+1)-th floors in either direction in 1 minute, for every i \, (1 \leq i \leq N - 1).
Additionally, using the i-th elevator, it is possible to travel between the A_i-th and B_i-th floors in either direction in C_i minutes, for each i \, (1 \leq i \leq M).

Find the minimum number of minutes needed to get from the 1-st floor to the N-th floor.

Constraints

• 2 \leq N \leq 10^{18}
• 1 \leq M \leq 10^5
• 1 \leq A_i \lt B_i \leq N
• 1 \leq C_i \leq 10^{18}
• All values in input are integers.

Sample Input 1

10 2
2 5 1
4 10 3

Sample Output 1

6

The optimal way to get there is as follows.

• Use stairs to get from the 1-st floor to the 2-nd floor in 1 minute.
• Use the 1-st elevator to get from the 2-nd floor to the 5-th floor in 1 minute.
• Use stairs to get from the 5-th floor to the 4-th floor in 1 minute.
• Use the 2-nd elevator to get from the 4-th floor to the 10-th floor in 3 minutes.

Sample Input 2

1000000000000000000 1
1 1000000000000000000 1000000000000000000

Sample Output 2

999999999999999999

Problem Statement

We have a grid with N rows and N columns. Initially, all squares are painted white.

Process Q queries \text{Query}_1,\text{Query}_2,\ldots,\text{Query}_Q in the order they are given.

There are three kinds of queries, with the following input formats and specifications.

• 1 x y : If the square at the x-th row from the top and y-th column from the left is white, repaint it black; if it is black, repaint it white.

• 2 c : Rotate the whole grid 90 degrees clockwise if c is A and counter-clockwise if c is B.

• 3 c : Flip the whole grid vertically if c is A and horizontally if c is B.

Find the colors of the squares after processing all queries.

Constraints

• 1 \leq N \leq 300
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq x,y \leq N
• c is A or B.
• Each query is of one of the three kinds described in Problem Statement.

Sample Input 1

3 2
1 1 1
2 A

Sample Output 1

001
000
000

We repaint the square at the 1-st row from the top and 1-st column from the left and then rotate the whole grid 90 degrees clockwise.

Sample Input 2

3 3
1 1 1
3 A
3 B

Sample Output 2

000
000
001

Sample Input 3

4 8
2 A
1 4 2
2 A
1 2 2
3 B
3 B
3 A
1 3 1

Sample Output 3

0000
0000
0100
0000

Problem Statement

The Kingdom of Takahashi has N towns and M roads.

The towns are numbered 1,2,\ldots,N, and the i-th road (1 \leq i \leq M) connects Town u_i and Town v_i bidirectionally. It is guaranteed that one can get from every town to every town by traversing some roads.

Additionally, there are gas stations in Towns a_1,a_2,\ldots,a_K.

Answer Q queries. The i-th query (1 \leq i \leq Q) is as follows.

• Find the minimum number of times one needs to traverse a road when getting from Town s_i to Town t_i via a town with a gas station.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M,Q \leq 2 \times 10^5
• 1 \leq K \leq \min(N-1,20)
• 1 \leq a_i \leq N
• a_i \neq a_j\,(i \neq j)
• 1 \leq u_i < v_i \leq N
• (u_i,v_i) \neq (u_j,v_j) \,(i \neq j)
• 1 \leq s_i , t_i \leq N
• Nither s_i nor t_i has a gas station.
• It is possible to get from every town to every town by traversing some roads.
• All values in input are integers.

Sample Input 1

3 2 1 1
1
1 2
2 3
3 2

Sample Output 1

3

After starting in Town 3, we can go to Town 2, Town 1, Town 2 in this order to complete the trip with three moves. It is impossible to do it with fewer moves, so we print 3.

Sample Input 2

5 6 2 2
3 1
1 2
2 3
2 4
1 5
2 5
3 5
5 5
5 4

Sample Output 2

2
3

Problem Statement

N students took a test, each getting a score of a positive integer between 0 and P (inclusive). All students got different scores, and they were ranked in descending order of score.

Takahashi asked each student their score, and the student ranked i-th told him they scored A_i.
However, some of the students might have told a lie.

Find the minimum possible number of students who told a lie.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq P \leq 10^9
• 0 \leq A_i \leq P
• All values in input are integers.

Sample Input 1

5 10
7 5 10 3 2

Sample Output 1

1

If just the student ranked 3-rd told a lie when the true score was 4, the students' scores and ranks would be consistent.

If all students had told the truth, the student ranked 3-rd would have scored higher than the student ranked 2-nd, which could not happen.

Therefore, the minimum possible number of students who told a lie is 1.

Sample Input 2

5 10
9 8 7 7 5

Sample Output 2

1

Note that the true scores of the students are distinct.

Sample Input 3

11 1000000000
0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

Sample Output 3

10

Problem Statement

There are N people, with IDs from 1 to N. Initially, Person i (1 \leq i \leq N) is named S_i.

Print the name of each person after processing the following query for each i=1, 2, \ldots, Q in order.

• Make the people stand in a row in lexicographically ascending order of name (in case of the same name, ascending order of ID), and rename the X_i-th person from the front to T_i.

Constraints

• 1 \leq N,Q \leq 10^5
• S_i is a string of length between 1 and 5 (inclusive) consisting of lowercase English letters.
• 1 \leq X_i \leq N
• T_i is a string of length between 1 and 5 (inclusive) consisting of lowercase English letters.
• N, Q, and X_i are integers.

Sample Input 1

3 3
taro jiro sabro
1 taro
2 jiro
3 taro

Sample Output 1

jiro taro sabro

Initially, the N=3 people are named taro, jiro, sabro in ascending order of ID.

• In the query with i=1, when they stand in a row in lexicographically ascending order of name, they are in the order 2, 3, 1. The X_1=1-st person from the front, Person 2, is renamed to T_1. Now, the people are named taro, taro, sabro in ascending order of ID.
• In the query with i=2, when they stand in a row in lexicographically ascending order of name, they are in the order 3, 1, 2. The X_2=2-nd person from the front, Person 1, is renamed to T_2. Now, the people are named jiro, taro, sabro in ascending order of ID.
• In the query with i=3, when they stand in a row in lexicographically ascending order of name, they are in the order 1, 3, 2. The X_3=3-rd person from the front, Person 2, is renamed to T_3. Now, the people are named jiro, taro, sabro in ascending order of ID.

Note that, as seen in the query with i=3, the name of the X_i-th person may remain unchanged in a query.

Sample Input 2

10 10
yo gaaj uab y reah y dyg ix rwq p
10 tvbvr
8 ax
7 xr
9 vw
10 ky
10 wlxtw
2 guoux
10 wbct
9 zbuxx
5 gq

Sample Output 2

tvbvr gaaj ax zbuxx reah gq guoux ix wbct p

Problem Statement

Given are convex polygons S and T in a two-dimensional plane.

S has N vertices, with the coordinates (a_1, b_1), \dots, (a_N, b_N) in counter-clockwise order.
T has M vertices, with the coordinates (c_1, d_1), \dots, (c_M, d_M) in counter-clockwise order.

Find the area of the intersection of S and T.

Constraints

• 3 \leq N, M \leq 10^3
• 0 \leq a_i, b_i \leq 3 \times 10^4 \, (1 \leq i \leq N)
• 0 \leq c_i, d_i \leq 3 \times 10^4 \, (1 \leq i \leq M)
• (a_1, b_1), \dots, (a_N, b_N) are the vertices of S listed in counter-clockwise order.
• (c_1, d_1), \dots, (c_M, d_M) are the vertices of T listed in counter-clockwise order.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

2.00000000000000000000

The intersection of S and T, shown gray in the figure below, has an area of 2.

Sample Input 2

3 3
0 0
3 0
0 3
3 3
0 3
3 0

Sample Output 2

0.00000000000000000000

Sample Input 3

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

Sample Output 3

0.79166666666666662966

Problem Statement

There are N people numbered 1 to N. Person i wears an integer B_i.

There are N! ways to make them stand in a row from left to right. The score for each of these ways is defined as follows. Find the sum of all those scores, modulo 998244353.

• Let A_i denote the integer worn by the i-th person from the left. Let f(i,j) be S_{j-i} if A_j-A_i=j-i and 0 otherwise. The score is the sum of f(i,j) over all pairs (i,j) such that 1\leq i < j \leq N.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq B_i \leq 10^5
• 1 \leq S_i \leq 998244352
• All values in input are integers.

Sample Input 1

3
3 2 1
1 10 100

Sample Output 1

14

• When arranging them in the order 1, 2, 3 from left to right, we have A=(3,2,1), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 1, 3, 2 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+1=1.
• When arranging them in the order 2, 1, 3 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=1+0+0=1.
• When arranging them in the order 2, 3, 1 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 3, 1, 2 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 3, 2, 1 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=1+10+1=12.

Therefore, the answer is 0+1+1+0+0+12=14.

Sample Input 2

3
3 3 1
1 10 100

Sample Output 2

20

• When arranging them in the order 1, 2, 3 from left to right, we have A=(3,3,1), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 1, 3, 2 from left to right, we have A=(3,1,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 2, 1, 3 from left to right, we have A=(3,3,1), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 2, 3, 1 from left to right, we have A=(3,1,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
• When arranging them in the order 3, 1, 2 from left to right, we have A=(1,3,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+10+0=10.
• When arranging them in the order 3, 2, 1 from left to right, we have A=(1,3,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+10+0=10.

Therefore, the answer is 0+0+0+0+10+10=20.

Sample Input 3

9
3 1 4 15 9 2 6 5 35
1 12 123 1234 12345 123456 1234567 12345678 123456789

Sample Output 3

146471953

Be sure to find it modulo 998244353.