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)