Problem Statement

Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.

What is the water pressure in megapascals at a depth of D meters?

Constraints

• 1 \leq D \leq 10000
• D is an integer.

Sample Input 1

1000

Sample Output 1

10

The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.

Sample Input 2

50

Sample Output 2

0.5

Sample Input 3

3141

Sample Output 3

31.41

Problem Statement

Takahashi will have N penalty kicks in a soccer match.

For the i-th penalty kick, he will fail if i is a multiple of 3, and succeed otherwise.

Print the results of his penalty kicks.

Constraints

• 1 \leq N \leq 100
• All inputs are integers.

Sample Input 1

7

Sample Output 1

ooxooxo

Takahashi fails the third and sixth penalty kicks, so the third and sixth characters will be x.

Sample Input 2

9

Sample Output 2

ooxooxoox

Problem Statement

You are given a sequence of length N consisting of integers: A=(A_1,\ldots,A_N).

Find the smallest non-negative integer not in (A_1,\ldots,A_N).

Constraints

• 1 \leq N \leq 2000
• 0 \leq A_i \leq 2000
• All values in input are integers.

Sample Input 1

8
0 3 2 6 2 1 0 0

Sample Output 1

4

The non-negative integers are 0,1,2,3,4,\ldots.
We have 0,1,2,3 in A, but not 4, so the answer is 4.

Sample Input 2

3
2000 2000 2000

Sample Output 2

0

Problem Statement

Takahashi has an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.
It is guaranteed that A is non-decreasing.

Takahashi performs M operations on this integer sequence. In the i-th operation (1\leq i\leq M), he performs the following operation:

If the sequence A contains B_i as an element, select one such element and delete it. If no such element exists, do nothing.

Note that since A is non-decreasing, the sequence after the operation is uniquely determined regardless of the choice of element, and remains non-decreasing.

Find A after performing M operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 1 \leq A_i,B_i \leq 10^9
• The integer sequence A is non-decreasing.
• All input values are integers.

Sample Input 1

8 5
1 2 2 3 3 3 5 6
2 2 7 3 2

Sample Output 1

1 3 3 5 6

Initially, A is A=(1,2,2,3,3,3,5,6).
The operations are performed as follows:

• Delete one 2 from A, and A becomes A=(1,2,3,3,3,5,6) after the operation.
• Delete one 2 from A, and A becomes A=(1,3,3,3,5,6) after the operation.
• Since A does not contain 7 as an element, do nothing. A remains A=(1,3,3,3,5,6) after the operation.
• Delete one 3 from A, and A becomes A=(1,3,3,5,6) after the operation.
• Since A does not contain 2 as an element, do nothing. A remains A=(1,3,3,5,6) after the operation.

Therefore, after all operations, A=(1,3,3,5,6), so output the elements in this order separated by spaces.

Sample Input 2

1 2
1
1 1

Sample Output 2

A becomes empty after the operations, so output nothing.

Problem Statement

There are N boxes numbered 1 to N and N items numbered 1 to N. Item i (1 \leq i \leq N) is in box A_i and has a weight of W_i.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w, the cost of the operation is w.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

• 1 \leq N \leq 10^{5}
• 1 \leq A_i \leq N (1 \leq i \leq N)
• 1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

35

With the following two moves, you can make each box contain exactly one item:

• Move item 1 from box 2 to box 1. The cost is 33.
• Move item 3 from box 3 to box 4. The cost is 2.

The total cost of these two moves is 35. It is impossible to make each box contain exactly one item with a cost less than 35, so print 35.

Sample Input 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

Sample Output 2

17254

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

• Let s and t (s \ge t) be the deliciousness of the eaten cups.
  • If the two cups have different flavors, your satisfaction is \displaystyle s+t.
  • Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

• All input values are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le F_i \le N
• 2 \le S_i \le 10^9
• S_i is even.

Sample Input 1

4
1 4
2 10
2 8
3 6

Sample Output 1

16

Consider eating the second and fourth cups.

• The second cup has a flavor of 2 and deliciousness of 10.
• The fourth cup has a flavor of 3 and deliciousness of 6.
• Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

4
4 10
3 2
2 4
4 12

Sample Output 2

17

Consider eating the first and fourth cups.

• The first cup has a flavor of 4 and deliciousness of 10.
• The fourth cup has a flavor of 4 and deliciousness of 12.
• Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and M edges, and eight pieces.

The nine vertices of the graph are called Vertex 1, Vertex 2, \ldots, Vertex 9. For each i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
The eight pieces are called Piece 1, Piece 2, \ldots, Piece 8. For each j = 1, 2, \ldots, 8, Piece j is on Vertex p_j.
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

• For each j = 1, 2, \ldots, 8, Piece j is on Vertex j.

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

• 0 \leq M \leq 36
• 1 \leq u_i, v_i \leq 9
• The given graph has no multi-edges or self-loops.
• 1 \leq p_j \leq 9
• j \neq j' \Rightarrow p_j \neq p_{j'}
• All values in input are integers.

Sample Input 1

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

Sample Output 1

5

The following procedure completes the puzzle in five operations.

1. Move Piece 2 from Vertex 9 to Vertex 1.
2. Move Piece 3 from Vertex 2 to Vertex 9.
3. Move Piece 2 from Vertex 1 to Vertex 2.
4. Move Piece 1 from Vertex 3 to Vertex 1.
5. Move Piece 3 from Vertex 9 to Vertex 3.

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print 5.
Note that the given graph may not be connected.

Sample Input 2

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

Sample Output 2

0

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is 0.

Sample Input 3

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

Sample Output 3

-1

No sequence of operations can complete the puzzle, so we should print -1.

Sample Input 4

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

Sample Output 4

16

Problem Statement

Find, modulo 998244353, the number of integers x with 1 \leq x \leq N that satisfy exactly one of the following three conditions.

• x is a multiple of 3.
• The decimal representation of x contains 3.
• Exactly three different digits are used in the decimal representation of x.

Here, the decimal representation of an integer should not have unnecessary leading 0s.

Constraints

• N is an integer.
• 1 \leq N < 10^{500}

Sample Input 1

45

Sample Output 1

19

Among the integers from 1 to 45, there are 19 integers satisfying exactly one of the conditions in the problem statement, as follows.

• There are 10 integers satisfying only the first condition: 6, 9, 12, 15, 18, 21, 24, 27, 42, 45.
• There are 9 integers satisfying only the second condition: 13, 23, 31, 32, 34, 35, 37, 38, 43.
• There are no integers satisfying only the third condition.

Sample Input 2

1013

Sample Output 2

424

Below are examples of applicable integers.

• Integers satisfying only the first condition include 555 and 1011.
• Integers satisfying only the second condition include 343 and 553.
• Integers satisfying only the third condition include 1012 and 704.

Sample Input 3

2

Sample Output 3

0

There are no applicable integers.

Sample Input 4

314159265358979323846264338327950

Sample Output 4

658111391

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

• When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
• When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of 0 and 1.
• c \in \lbrace 1, 2 \rbrace
• 1 \leq L \leq R \leq N
• N, Q, c, L, and R are all integers.

Sample Input 1

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

Sample Output 1

3
1
0
7

The queries are processed as follows.

• Initially, S= 1101110.
• For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
• For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
• For the third query, the operation changes S to 1110000.
• For the fourth query, T = 00. T does not contain 1, so the answer is 0.
• For the fifth query, the operation changes S to 1111111.
• For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.