Problem Statement

You are given the name S of a certain person. The first character of S is an uppercase English letter, and the other characters are lowercase English letters.

The name of this person's handmaid is the string obtained by converting the first letter of S to lowercase and adding Of to the beginning. Find the name of this handmaid.

Constraints

• S is a string of length between 1 and 10, inclusive.
• The first character of S is an uppercase English letter.
• The characters of S other than the first are lowercase English letters.

Sample Input 1

Glen

Sample Output 1

Ofglen

Converting the first letter of Glen to lowercase gives glen, and adding Of to the beginning gives Ofglen.

Sample Input 2

I

Sample Output 2

Ofi

Sample Input 3

Fred

Sample Output 3

Offred

Problem Statement

There is a grid with H horizontal rows and W vertical columns. Let (i,j) denote the square at the i-th row from the top and the j-th column from the left.
Find the number of squares that share a side with Square (R, C).

Here, two squares (a,b) and (c,d) are said to share a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Constraints

• All values in input are integers.
• 1 \le R \le H \le 10
• 1 \le C \le W \le 10

Sample Input 1

3 4
2 2

Sample Output 1

4

We will describe Sample Inputs/Outputs 1,2, and 3 at once below Sample Output 3.

Sample Input 2

3 4
1 3

Sample Output 2

3

Sample Input 3

3 4
3 4

Sample Output 3

2

When H=3 and W=4, the grid looks as follows.

• For Sample Input 1, there are 4 squares adjacent to Square (2,2).
• For Sample Input 2, there are 3 squares adjacent to Square (1,3).
• For Sample Input 3, there are 2 squares adjacent to Square (3,4).

Sample Input 4

1 10
1 5

Sample Output 4

2

Sample Input 5

8 1
8 1

Sample Output 5

1

Sample Input 6

1 1
1 1

Sample Output 6

0

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

• 1 \leq N \leq 100
• 1 \leq S,M,L \leq 10^4
• All input values are integers.

Sample Input 1

16 120 150 200

Sample Output 1

300

It is optimal to buy two 8-egg packs.

Sample Input 2

10 100 50 10

Sample Output 2

10

It is optimal to buy one 12-egg pack.

Sample Input 3

99 600 800 1200

Sample Output 3

10000

It is optimal to buy five 8-egg packs and five 12-egg packs.

Problem Statement

Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.

Constraints

• -10^{18} \leq X \leq 10^{18}
• X is an integer.

Sample Input 1

27

Sample Output 1

3

The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.

Sample Input 2

-13

Sample Output 2

-1

The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.

Sample Input 3

40

Sample Output 3

4

The smallest integer not less than \frac{40}{10} = 4 is 4 itself.

Sample Input 4

-20

Sample Output 4

-2

Sample Input 5

123456789123456789

Sample Output 5

12345678912345679

Problem Statement

We have a multiset of integers S, which is initially empty.

Given Q queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an x into S.

• 2 x c: Remove an x from S m times, where m = \mathrm{min}(c,( the number of x's contained in S)).

• 3 : Print ( maximum value of S)-( minimum value of S). It is guaranteed that S is not empty when this query is given.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 0 \leq x \leq 10^9
• 1 \leq c \leq Q
• When a query of type 3 is given, S is not empty.
• All values in input are integers.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset S transitions as follows.

• 1-st query: insert 3 into S. S is now \lbrace 3 \rbrace.
• 2-nd query: insert 2 into S. S is now \lbrace 2, 3 \rbrace.
• 3-rd query: the maximum value of S = \lbrace 2, 3\rbrace is 3 and its minimum value is 2, so print 3-2=1.
• 4-th query: insert 2 into S. S is now \lbrace 2,2,3 \rbrace.
• 5-th query: insert 7 into S. S is now \lbrace 2, 2,3, 7\rbrace.
• 6-th query: the maximum value of S = \lbrace 2,2,3, 7\rbrace is 7 and its minimum value is 2, so print 7-2=5.
• 7-th query: since there are two 2's in S and \mathrm{min(2,3)} = 2, remove 2 from S twice. S is now \lbrace 3, 7\rbrace.
• 8-th query: the maximum value of S = \lbrace 3, 7\rbrace is 7 and its minimum value is 3, so print 7-3=4.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type 3, nothing should be printed.

Problem Statement

Takahashi and Aoki will play the following game against each other.

Starting from Takahashi, the two alternatingly declare an integer between 1 and 2N+1 (inclusive) until the game ends. Any integer declared by either player cannot be declared by either player again. The player who is no longer able to declare an integer loses; the player who didn't lose wins.

In this game, Takahashi will always win. Your task is to actually play the game on behalf of Takahashi and win the game.

Constraints

• 1 \leq N \leq 1000
• N is an integer.

Input and Output

This task is an interactive task (in which your program and the judge program interact with each other via inputs and outputs).
Your program plays the game on behalf of Takahashi, and the judge program plays the game on behalf of Aoki.

First, your program is given a positive integer N from Standard Input. Then, the following procedures are repeated until the game ends.

1. Your program outputs an integer between 1 and 2N+1 (inclusive) to Standard Output, which defines the integer that Takahashi declares. (You cannot output an integer that is already declared by either player.)
2. The integer that Aoki declares is given by the judge program to your program from Standard Input. (No integer that is already declared by either player will be given.) If Aoki has no more integer to declare, 0 is given instead, which means that the game ended and Takahashi won.

Notes

• After each output, you must flush Standard Output. Otherwise, you may get TLE.
• After the game ended and Takahashi won, the program must be terminated immediately. Otherwise, the judge does not necessarily give AC.
• If your program outputs something that violates the rules of the game (such as an integer that has already been declared by either player), your answer is considered incorrect. In such case, the verdict is indeterminate. It does not necessarily give WA.

Sample Input and Output

Problem Statement

There are N houses at points (X_1,Y_1),\ldots,(X_N,Y_N) on a two-dimensional plane.

Initially, Santa Claus is at point (S_x,S_y). He will act according to the sequence (D_1,C_1),\ldots,(D_M,C_M) as follows:

• For i=1,2,\ldots,M in order, he moves as follows:
  • Let (x,y) be the point where he currently is.
    • If D_i is U, move in a straight line from (x,y) to (x,y+C_i).
    • If D_i is D, move in a straight line from (x,y) to (x,y-C_i).
    • If D_i is L, move in a straight line from (x,y) to (x-C_i,y).
    • If D_i is R, move in a straight line from (x,y) to (x+C_i,y).

Find the point where he is after completing all actions, and the number of distinct houses he passed through or arrived at during his actions. If the same house is passed multiple times, it is only counted once.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• -10^9 \leq X_i,Y_i \leq 10^9
• The pairs (X_i,Y_i) are distinct.
• -10^9 \leq S_x,S_y \leq 10^9
• There is no house at (S_x,S_y).
• Each D_i is one of U, D, L, R.
• 1 \leq C_i \leq 10^9
• All input numbers are integers.

Sample Input 1

3 4 3 2
2 2
3 3
2 1
L 2
D 1
R 1
U 2

Sample Output 1

2 3 2

Santa Claus behaves as follows:

• D_1= L, so he moves from (3,2) to (3-2,2) in a straight line. During this, he passes through the house at (2,2).
• D_2= D, so he moves from (1,2) to (1,2-1) in a straight line.
• D_3= R, so he moves from (1,1) to (1+1,1) in a straight line. During this, he passes through the house at (2,1).
• D_4= U, so he moves from (2,1) to (2,1+2) in a straight line. During this, he passes through the house at (2,2), but it has already been passed.

The number of houses he passed or arrived during his actions is 2.

Sample Input 2

1 3 0 0
1 1
R 1000000000
R 1000000000
R 1000000000

Sample Output 2

3000000000 0 0

Be careful with overflow.

Problem Statement

There are N items in a shop, numbered as Item 1, Item 2, \ldots, Item N.
For each i = 1, 2, \ldots, N, the regular price of Item i is A_i yen. For each item, there is only one in stock.

Takahashi wants M items: Item X_1, Item X_2, \ldots, Item X_M.

He repeats the following until he gets all items he wants.

Let r be the number of unsold items now. Choose an integer j such that 1 \leq j \leq r, and buy the item with the j-th smallest item number among the unsold items, for its regular price plus C_j yen.

Print the smallest total amount of money needed to get all items Takahashi wants.

Takahashi may also buy items other than the ones he wants.

Constraints

• 1 \leq M \leq N \leq 5000
• 1 \leq A_i \leq 10^9
• 1 \leq C_i \leq 10^9
• 1 \leq X_1 \lt X_2 \lt \cdots \lt X_M \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

17

Here is a way for Takahashi to get all items he wants with the smallest total amount of money.

• Initially, five items, Items 1, 2, 3, 4, 5, are remaining. Choose j = 5 to buy the item with the fifth smallest item number among the remaining, Item 5, for A_5 + C_5 = 5 + 3 = 8 yen.
• Then, four items, Items 1, 2, 3, 4, are remaining. Choose j = 2 to buy the item with the second smallest item number among the remaining, Item 2, for A_2 + C_2 = 1 + 2 = 3 yen.
• Then, three items, Items 1, 3, 4, are remaining. Choose j = 2 to buy the item with the second smallest item number among the remaining, Item 3, for A_3 + C_2 = 4 + 2 = 6 yen.

Now, Takahashi has all items he wants, Items 3 and 5, (along with Item 2, which is not wanted) for a total cost of 8 + 3 + 6 = 17 yen, the minimum possible.

Sample Input 2

20 8
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78 39 97 12 53 62
32 38 84 49 93 53 26 13 25 2 76 32 42 34 18 77 14 67 88 12
1 3 4 5 8 14 16 20

Sample Output 2

533

Problem Statement

You are given a tree T with N vertices. The vertices are numbered 1 to N, and the i-th edge (1 \leq i \leq N-1) connects vertices u_i and v_i bidirectionally.

Using T, define a complete graph G with N vertices as follows:

• The weight w(x,y) of the edge between vertices x and y in G is the shortest distance between vertices x and y in T.

Find one maximum weight maximum matching in G. That is, find a set of \lfloor N/2 \rfloor pairs of vertices M=\{(x_1,y_1),(x_2,y_2),\dots,(x_{\lfloor N/2 \rfloor},y_{\lfloor N/2 \rfloor})\} such that each vertex 1,2,\dots, N appears in M at most once, and \displaystyle \sum_{i=1}^{\lfloor N/2 \rfloor} w(x_i,y_i) is maximized.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq u_i < v_i \leq N
• The input graph is a tree.
• All input values are integers.

Sample Input 1

4
1 2
2 3
3 4

Sample Output 1

2 4
1 3

In T, the distance between vertices 2 and 4 is 2, and the distance between vertices 1 and 3 is 2, so the weight of the matching \{(2,4),(1,3)\} is 4. There is no matching with a weight greater than 4, so this is a maximum weight maximum matching. Other acceptable outputs include:

2 3
1 4

Sample Input 2

3
1 2
2 3

Sample Output 2

1 3

In T, the distance between vertices 1 and 3 is 2, so the weight of the matching \{(1,3)\} is 2. There is no matching with a weight greater than 2, so this is a maximum weight maximum matching. Another acceptable output is:

3 1