Problem Statement

You are given a string S of length between 1 and 25 consisting of lowercase English letters.
Output one lowercase English letter that does not appear in S.
If there are multiple such letters, you may output any one of them.

Constraints

• S is a string of length between 1 and 25 (inclusive) consisting of lowercase English letters.

Sample Input 1

a

Sample Output 1

d

S= a.
Any lowercase English letter other than a (that is, b, c, …, or z) is a correct answer.

Sample Input 2

abcdfhijklmnopqrstuvwxyz

Sample Output 2

e

The lowercase English letters not included in S are e and g.

Sample Input 3

qazplwsxokmedcijnrfvuhbgt

Sample Output 3

y

Problem Statement

You are given a three-digit integer N where each digit is an integer between 1 and 9, inclusive.

Let a, b, c be the hundreds, tens, ones digits of N, respectively. Print an integer formed by arranging b, c, a in this order, and an integer formed by arranging c, a, b in this order.

Constraints

• N is a three-digit integer where each digit is an integer between 1 and 9, inclusive.

Sample Input 1

379

Sample Output 1

793 937

The hundreds, tens, ones digits of 379 are 3, 7, 9, respectively, so print 793 and 937.

Sample Input 2

919

Sample Output 2

199 991

The hundreds, tens, ones digits of 919 are 9, 1, 9, respectively, so print 199 and 991.

Problem Statement

You are given a positive integer M. Find a positive integer N and a sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) that satisfy all of the following conditions:

• 1 \le N \le 20
• 0 \le A_i \le 10 (1 \le i \le N)
• \displaystyle \sum_{i=1}^N 3^{A_i} = M

It can be proved that under the constraints, there always exists at least one such pair of N and A satisfying the conditions.

Constraints

• 1 \le M \le 10^5

Sample Input 1

6

Sample Output 1

2
1 1

For example, with N=2 and A=(1,1), we have \displaystyle \sum_{i=1}^N 3^{A_i} = 3+3=6, satisfying all conditions.

Another example is N=4 and A=(0,0,1,0), which also satisfies the conditions.

Sample Input 2

100

Sample Output 2

4
2 0 2 4

Sample Input 3

59048

Sample Output 3

20
0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

Note the condition 1 \le N \le 20.

Problem Statement

A real number X is given to the third decimal place.

Print the real number X under the following conditions.

• The decimal part must not have trailing 0s.
• There must not be an unnecessary trailing decimal point.

Constraints

• 0 \le X < 100
• X is given to the third decimal place.

Sample Input 1

1.012

Sample Output 1

1.012

1.012 can be printed as it is.

Sample Input 2

12.340

Sample Output 2

12.34

Printing 12.340 without the trailing 0 results in 12.34.

Sample Input 3

99.900

Sample Output 3

99.9

Printing 99.900 without the trailing 0s results in 99.9.

Sample Input 4

0.000

Sample Output 4

0

Printing 0.000 without trailing 0s or an unnecessary decimal point results in 0.

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

• First, choose one real number x.
• Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 0 \le A_i \le 10^9

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

10 1
3 1 4 1 5 9 2 6 5 3

Sample Output 2

2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7

Problem Statement

In the Kingdom of AtCoder, a week consists of A+B days, with the first through A-th days being holidays and the (A+1)-th through (A+B)-th being weekdays.

Takahashi has N plans, and the i-th plan is scheduled D_i days later.

He has forgotten what day of the week it is today. Determine if it is possible for all of his N plans to be scheduled on holidays.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq A,B\leq 10^9
• 1\leq D_1<D_2<\ldots<D_N\leq 10^9

Sample Input 1

3 2 5
1 2 9

Sample Output 1

Yes

In this input, a week consists of seven days, with the first through second days being holidays and the third through seventh days being weekdays.

Let us assume today is the seventh day of the week. In this case, one day later would be the first day of the week, two days later would be the second day of the week, and nine days later would also be the second day of the week, making all plans scheduled on holidays. Therefore, it is possible for all of Takahashi's N plans to be scheduled on holidays.

Sample Input 2

2 5 10
10 15

Sample Output 2

No

Sample Input 3

4 347 347
347 700 705 710

Sample Output 3

Yes

Problem Statement

You are given a permutation P = (P_1, P_2, \dots, P_N) of (1, 2, \dots, N).

A length-K sequence of indices (i_1, i_2, \dots, i_K) is called a good index sequence if it satisfies both of the following conditions:

• 1 \leq i_1 < i_2 < \dots < i_K \leq N.
• The subsequence (P_{i_1}, P_{i_2}, \dots, P_{i_K}) can be obtained by rearranging some consecutive K integers.
  Formally, there exists an integer a such that \lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace.

Find the minimum value of i_K - i_1 among all good index sequences. It can be shown that at least one good index sequence exists under the constraints of this problem.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• P_i \neq P_j if i \neq j.
• All input values are integers.

Sample Input 1

4 2
2 3 1 4

Sample Output 1

1

The good index sequences are (1,2),(1,3),(2,4). For example, (i_1, i_2) = (1,3) is a good index sequence because 1 \leq i_1 < i_2 \leq N and (P_{i_1}, P_{i_2}) = (2,1) is a rearrangement of two consecutive integers 1, 2.

Among these good index sequences, the smallest value of i_K - i_1 is for (1,2), which is 2-1=1.

Sample Input 2

4 1
2 3 1 4

Sample Output 2

0

i_K - i_1 = i_1 - i_1 = 0 in all good index sequences.

Sample Input 3

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

Sample Output 3

5

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 is a directed graph with N vertices and N-1+M edges, with edges and vertices numbered.
For 1 \leq i \leq M, edge i is a directed edge from vertex X_i to vertex Y_i, and for 1 \leq i \leq N-1, edge M+i is a directed edge from vertex i+1 to vertex i.

There are 2^M ways to choose some (possibly zero) edges from among edges 1, 2, \dots, M. Among these ways, how many result in the graph being strongly connected after deleting the chosen edges? Find the count modulo 998244353.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq X_i < Y_i \leq N
• All input values are integers.

Sample Input 1

4 3
1 4
1 3
2 4

Sample Output 1

5

The graph is strongly connected when the set of chosen edge indices is one of \{\}, \{1\}, \{2\}, \{3\}, \{2,3\}, giving five ways.

Sample Input 2

10 11
1 4
1 4
3 9
2 5
3 4
9 10
6 9
4 10
1 3
8 10
4 7

Sample Output 2

1297

The given graph may have multi-edges.