Problem Statement

You are given a string S of length 3 consisting of lowercase English letters.

How many different strings can be obtained by permuting the characters in S?

Constraints

• S is a string S of length 3 consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

3

By permuting the characters in S= aba, three different strings can be obtained: aab, aba, baa.

Sample Input 2

ccc

Sample Output 2

1

By permuting the characters in S= ccc, just one string can be obtained: ccc.

Sample Input 3

xyz

Sample Output 3

6

By permuting the characters in S= xyz, six different strings can be obtained: xyz, xzy, yxz, yzx, zxy, zyx.

Problem Statement

You are given a string S of length exactly 9 consisting of digits. One but all digits from 0 to 9 appear exactly once in S.

Print the only digit missing in S.

Constraints

• S is a string of length 9 consisting of digits.
• All characters in S are distinct.

Sample Input 1

023456789

Sample Output 1

1

The string 023456789 only lacks 1. Thus, 1 should be printed.

Sample Input 2

459230781

Sample Output 2

6

The string 459230781 only lacks 6. Thus, 6 should be printed.

Note that the digits in the string may not appear in increasing order.

Problem Statement

There are N points in a two-dimensional plane. The coordinates of the i-th point are (x_i,y_i).

Find the maximum length of a segment connecting two of these points.

Constraints

• 2 \leq N \leq 100
• -1000 \leq x_i,y_i \leq 1000
• (x_i,y_i) \neq (x_j,y_j)\ (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 0
0 1
1 1

Sample Output 1

1.4142135624

For the 1-st and 3-rd points, the length of the segment connecting them is \sqrt 2 = 1.41421356237\dots, which is the maximum length.

Sample Input 2

5
315 271
-2 -621
-205 -511
-952 482
165 463

Sample Output 2

1455.7159750446

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

Constraints

• S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No

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

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

There is a rectangular cake with some strawberries on the xy-plane. The cake occupies the rectangular area \lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace.

There are N strawberries on the cake, and the coordinates of the i-th strawberry are (p_i, q_i) for i = 1, 2, \ldots, N. No two strawberries have the same coordinates.

Takahashi will cut the cake into several pieces with a knife, as follows.

• First, cut the cake along A different lines parallel to the y-axis: lines x = a_1, x = a_2, \ldots, x = a_A.
• Next, cut the cake along B different lines parallel to the x-axis: lines y = b_1, y = b_2, \ldots, y = b_B.

As a result, the cake will be divided into (A+1)(B+1) rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece.

Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below.

Constraints

• 3 \leq W, H \leq 10^9
• 1 \leq N \leq 2 \times 10^5
• 0 \lt p_i \lt W
• 0 \lt q_i \lt H
• i \neq j \implies (p_i, q_i) \neq (p_j, q_j)
• 1 \leq A, B \leq 2 \times 10^5
• 0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W
• 0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H
• p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace
• q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is 0, and the maximum possible number is 2.

Sample Input 2

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

Sample Output 2

1 1

Each piece has one strawberry on it.

Problem Statement

We have N books numbered 1 to N.
Book i assumes that you have read C_i books, the j-th of which is book P_{i,j}: you must read all these C_i books before reading book i.
Here, you can read all the books in some order.

You are trying to read the minimum number of books required to read book 1.
Print the numbers of the books you must read excluding book 1 in the order they should be read. Under this condition, the set of books to read is uniquely determined.
If there are multiple reading orders that satisfy the condition, you may print any of them.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq C_i < N
• \sum_{i=1}^{N} C_i \leq 2 \times 10^5
• C_1 \geq 1
• 1 \leq P_{i,j} \leq N
• P_{i,j} \neq P_{i,k} for 1 \leq j < k \leq C_i.
• It is possible to read all the books.

Sample Input 1

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

Sample Output 1

5 3 4 2

To read book 1, you must read books 2,3,4; to read book 2, you must read books 3,5; to read book 4, you must read book 5. To read books 3,5,6, you do not have to read any other books.

For example, if you read books 5,3,4,2 in this order, you can read book 1. This is a correct answer, because you will never be able to read book 1 with three or fewer books read. As another example, reading books 3,5,4,2 in this order also allows you to read book 1 with 4 books read.

Sample Input 2

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

Sample Output 2

6 5 4 3 2

Sample Input 3

8
1 5
1 6
1 7
1 8
0
0
0
0

Sample Output 3

5

Problem Statement

We have a box, which is initially empty.
Let us perform a total of Q operations of the following two types in the order they are given in the input.

+ x

Type 1: Put into the box a ball with the integer x written on it.

- x

Type 2: Remove from the box a ball with the integer x written on it.
It is guaranteed that the box contains a ball with the integer x written on it before the operation.

For the box after each operation, solve the following problem.

Find the number, modulo 998244353, to pick up some number of balls from the box so that the integers written on them sum to K.
All balls in the box are distinguishable.

Constraints

• All input values are integers.
• 1 \le Q \le 5000
• 1 \le K \le 5000
• For each type-1 operation, 1 \le x \le 5000.
• All the operations satisfy the condition in the problem statement.

Sample Input 1

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

Sample Output 1

0
0
1
0
1
2
2
2
2
2
1
3
5
8
5

This input contains 15 operations.

After the last operation, the box contains the balls (5,10,1,3,1,7,4).
There are five ways to pick up balls for a sum of 10:

• 5+1+3+1 (the 1-st, 3-rd, 4-th, 5-th balls)
• 5+1+4 (the 1-st, 3-rd, 7-th balls)
• 5+1+4 (the 1-st, 5-th, 7-th balls)
• 10 (the 2-nd ball)
• 3+7 (the 4-th, 6-th balls)