Problem Statement

You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.

Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.

Constraints

• S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).

Sample Input 1

abc atcoder

Sample Output 1

Yes

abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.

Sample Input 2

arc agc

Sample Output 2

No

Sample Input 3

a aa

Sample Output 3

Yes

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

• Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
• S_1, S_2, and S_3 are pairwise different.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

We have a long piece of timber with a length of L meters.
For each x = 1, 2, \dots, L - 1, there is a mark called Mark x at x meters from the left end of the piece.

You are given Q queries, the i-th of which is represented as a pair of numbers (c_i, x_i).
Process the queries in ascending order of i as described below.

• If c_i = 1: cut the piece at Mark x_i into two.
• If c_i = 2: choose the piece with Mark x_i on it and print its length.

Here, for both kinds of queries c_i = 1, 2, it is guaranteed that there will have been no cut at Mark x_i when the query is to be processed.

Constraints

• 1 \leq L \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• c_i = 1, 2 (1 \leq i \leq Q)
• 1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
• For every i (1 \leq i \leq Q), the following holds: there is no j such that 1 \leq j \lt i and (c_j,x_j) = (1, x_i).
• All values in input are integers.

Sample Input 1

5 3
2 2
1 3
2 2

Sample Output 1

5
3

At the time of the first query, no cut has been made, so the piece with Mark 2 has a length of 5 meters. Thus, you should print 5.
In the second query, the piece is cut into two pieces with lengths of 3 and 2 meters.
At the time of the third query, the piece with Mark 2 has a length of 3 meters, so you should print 3.

Sample Input 2

5 3
1 2
1 4
2 3

Sample Output 2

2

Sample Input 3

100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

Sample Output 3

69
31
6
38
38

Problem Statement

We have an empty sequence A. You will be given Q queries, which should be processed in the order they are given. Each query is of one of the three kinds below:

• 1 x : Append x to the end of A.
• 2 : Print the element at the beginning of A. Then, delete that element. It is guaranteed that A will not empty when this query is given.
• 3 : Sort A in ascending order.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• 0 \leq x \leq 10^9
• A will not be empty when a query 2 is given.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 1.

• (4)
• (4, 3)
• (4, 3, 2)
• (4, 3, 2, 1)
• (1, 2, 3, 4)
• (2, 3, 4)
• (2, 3, 4, 0)
• (3, 4, 0)

Sample Input 2

9
1 5
1 5
1 3
2
3
2
1 6
3
2

Sample Output 2

5
3
5

The i-th line below shows the contents of A after the i-th query is processed in Sample Input 2.

• (5)
• (5, 5)
• (5, 5, 3)
• (5, 3)
• (3, 5)
• (5)
• (5, 6)
• (5, 6)
• (6)

Problem Statement

There are 2N students standing in a row, numbered 1, 2, \ldots, 2N from left to right. For all pairs of two students, they are on good or bad terms. Specifically, for each 1\leq i\leq M, Student A_i and Student B_i are on good terms; for the remaining pairs of two students, they are on bad terms.

The teacher is going to do the following operation N times to form N pairs of two students.

• Choose two adjacent students who are on good terms, pair them, and remove them from the row.
• If the removed students were not at an end of the row, close up the gap so that the two students who were to the left and right of the removed students are now adjacent.

Find the number, modulo 998244353, of possible ways to do the operation N times. Two ways to do the operation N times are considered different when there exists 1\leq i\leq N such that the pair of students chosen in the i-th operation is different in those two ways.

Constraints

• 1 \leq N \leq 200
• 0 \leq M \leq N(2N-1)
• 1 \leq A_i < B_i \leq 2N
• All pairs (A_i, B_i) are distinct.
• All values in input are integers.

Sample Input 1

2 3
1 2
1 4
2 3

Sample Output 1

1

The only way to complete the procedure is to choose Students 2 and 3 in the first and Students 1 and 4 in the second. If Students 1 and 2 are chosen in the first operation, Students 3 and 4 will remain, who are on bad terms and thus cannot be paired in the second operation.
Thus, you should print 1.

Sample Input 2

2 2
1 2
3 4

Sample Output 2

2

There are two ways to complete the procedure: one way is to choose Students 1 and 2 in the first operation and Students 3 and 4 in the second, and the other way is to choose Students 3 and 4 in the first operation and Students 1 and 2 in the second. Note that these two ways are distinguished.

Sample Input 3

2 2
1 3
2 4

Sample Output 3

0

Since no pair can be chosen in the first operation, there is no way to complete the procedure, so you should print 0.

Problem Statement

You are given positive integers N and M. For each k=1,\ldots,N, solve the following problem.

• Problem: We will divide N people with ID numbers 1 through N into k non-empty groups. Here, people whose ID numbers are equal modulo M cannot belong to the same group.
  How many such ways are there to divide people into groups?
  Since the answer may be enormous, find it modulo 998244353.

Here, two ways to divide people into groups are considered different when there is a pair (x, y) such that Person x and Person y belong to the same group in one way but not in the other.

Constraints

• 2 \leq N \leq 5000
• 2 \leq M \leq N
• All values in input are integers.

Sample Input 1

4 2

Sample Output 1

0
2
4
1

People whose ID numbers are equal modulo 2 cannot belong to the same group. That is, Person 1 and Person 3 cannot belong to the same group, and neither can Person 2 and Person 4.

• There is no way to divide the four into one group.
• There are two ways to divide the four into two groups: \{\{1,2\},\{3,4\}\} and \{\{1,4\},\{2,3\}\}.
• There are four ways to divide the four into three groups: \{\{1,2\},\{3\},\{4\}\}, \{\{1,4\},\{2\},\{3\}\}, \{\{1\},\{2,3\},\{4\}\}, and \{\{1\},\{2\},\{3,4\}\}.
• There is one way to divide the four into four groups: \{\{1\},\{2\},\{3\},\{4\}\}.

Sample Input 2

6 6

Sample Output 2

1
31
90
65
15
1

You can divide them as you like.

Sample Input 3

20 5

Sample Output 3

0
0
0
331776
207028224
204931064
814022582
544352515
755619435
401403040
323173195
538468102
309259764
722947327
162115584
10228144
423360
10960
160
1

Be sure to find the answer modulo 998244353.

Problem Statement

In a game called Snuketoon, developed by AtCoder, Inc., the player plays as Snuke to dodge water from water guns.

The platform consists of an infinite number line, and Snuke is at the point 0 at the beginning of the game.
Starting from the beginning of the game, Snuke can make one of the three moves in each second: move 1 in the negative direction, move 1 in the positive direction, or remain still. More formally, if Snuke's position is p at t seconds (t \geq 0, t is an integer) from the beginning of the game, his position at t+1 seconds can be p-1, p, or p+1.

Snuke takes damage from getting soaked by water guns. The water guns shoot N times, and the i-th shot is represented by T_i, D_i, and X_i as follows.

• At T_i seconds from the beginning of the game, water is shot from the left or right. Let p be Snuke's position at that time. He takes the following damage if he is in the following range.
  • When D_i = 0, he takes X_i - p points of damage if he is in the range p \lt X_i.
  • When D_i = 1, he takes p - X_i points of damage if he is in the range X_i \lt p.

Takahashi, a pro gamer, wants to minimize the total damage taken by Snuke after the end of the N-th shot, to post a tweet on this game. Find the total damage taken by Snuke when the game is played to minimize it.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq T_1 \lt T_2 \lt \dots \lt T_N \leq 10^9
• D_i (1 \leq i \leq N) is 0 or 1.
• -10^9 \leq X_i \leq 10^9 (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

3
1 0 3
3 1 0
4 0 6

Sample Output 1

7

For convenience, let t denote the number of seconds elapsed from the beginning of the game. The optimal course of movements for Snuke until all the shots are done is as follows.

• When t = 0, Snuke is at the point 0. He moves 1 in the positive direction.
• When t = 1, Snuke is at the point 1 and takes 2 points of damage from the first shot. He moves 1 in the negative direction.
• When t = 2, Snuke is at the point 0. He remains still.
• When t = 3, Snuke is at the point 0 and takes no damage from the second shot. He moves 1 in the positive direction.
• When t = 4, Snuke is at the point 1 and takes 5 points of damage from the third shot.

Here, Snuke takes a total of 7 points of damage, so you should print 7.

Sample Input 2

3
1 0 1
6 1 1
8 0 -1

Sample Output 2

0

Sample Input 3

5
1 0 1000000000
2 1 -1000000000
3 0 1000000000
4 1 -1000000000
5 0 1000000000

Sample Output 3

4999999997