Problem Statement

You are given a real number X, which is representable using at most three decimal digits, with three decimal digits.
Round X to the nearest integer and print the result.

Constraints

• 0 \leq X < 100
• X is representable using at most three decimal digits.
• X has three decimal digits in input.

Sample Input 1

3.456

Sample Output 1

3

The digit in the first decimal place of 3.456 is 4, so we should round it down to 3.

Sample Input 2

99.500

Sample Output 2

100

Sample Input 3

0.000

Sample Output 3

0

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

Bowling pins are numbered 1 through 10. The following figure is a top view of the arrangement of the pins:

Let us call each part between two dotted lines in the figure a column.
For example, Pins 1 and 5 belong to the same column, and so do Pin 3 and 9.

When some of the pins are knocked down, a special situation called split may occur.
A placement of the pins is a split if both of the following conditions are satisfied:

• Pin 1 is knocked down.
• There are two different columns that satisfy both of the following conditions:
  • Each of the columns has one or more standing pins.
  • There exists a column between these columns such that all pins in the column are knocked down.

See also Sample Inputs and Outputs for examples.

Now, you are given a placement of the pins as a string S of length 10. For i = 1, \dots, 10, the i-th character of S is 0 if Pin i is knocked down, and is 1 if it is standing.
Determine if the placement of the pins represented by S is a split.

Constraints

• S is a string of length 10 consisting of 0 and 1.

Sample Input 1

0101110101

Sample Output 1

Yes

In the figure below, the knocked-down pins are painted gray, and the standing pins are painted white:

Between the column containing a standing pin 5 and the column containing a standing pin 6 is a column containing Pins 3 and 9. Since Pins 3 and 9 are both knocked down, the placement is a split.

Sample Input 2

0100101001

Sample Output 2

Yes

Sample Input 3

0000100110

Sample Output 3

No

This placement is not a split.

Sample Input 4

1101110101

Sample Output 4

No

This is not a split because Pin 1 is not knocked down.

Problem Statement

There are N players numbered 1 to N, who have played a round-robin tournament. For every match in this tournament, one player won and the other lost.

The results of the matches are given as N strings S_1,S_2,\ldots,S_N of length N each, in the following format:

• If i\neq j, the j-th character of S_i is o or x. o means that player i won against player j, and x means that player i lost to player j.

• If i=j, the j-th character of S_i is -.

The player with more wins ranks higher. If two players have the same number of wins, the player with the smaller player number ranks higher. Report the player numbers of the N players in descending order of rank.

Constraints

• 2\leq N\leq 100
• N is an integer.
• S_i is a string of length N consisting of o, x, and -.
• S_1,\ldots,S_N conform to the format described in the problem statement.

Sample Input 1

3
-xx
o-x
oo-

Sample Output 1

3 2 1

Player 1 has 0 wins, player 2 has 1 win, and player 3 has 2 wins. Thus, the player numbers in descending order of rank are 3,2,1.

Sample Input 2

7
-oxoxox
x-xxxox
oo-xoox
xoo-ooo
ooxx-ox
xxxxx-x
oooxoo-

Sample Output 2

4 7 3 1 5 2 6

Both players 4 and 7 have 5 wins, but player 4 ranks higher because their player number is smaller.

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N. For each K = 0, 1, 2, \ldots, N-1, solve the following problem.

Find the number of integers i between 1 and N (inclusive) such that:

• A contains exactly K distinct integers greater than A_i.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
2 7 1 8 2 8

Sample Output 1

2
1
2
1
0
0

For example, we will find the answer for K=2.

• Regarding A_1 = 2, A contains 2 distinct integers greater than A_1: 7 and 8.
• Regarding A_2 = 7, A contains 1 distinct integer greater than A_2: 8.
• Regarding A_3 = 1, A contains 3 distinct integers greater than A_3: 2, 7, and 8.
• Regarding A_4 = 8, A contains 0 distinct integers greater than A_4 (there is no such integer).
• Regarding A_5 = 2, A contains 2 distinct integers greater than A_5: 7 and 8.
• Regarding A_6 = 8, A contains 0 distinct integers greater than A_6 (there is no such integer).

Thus, there are two i's, i = 1 and i = 5, such that A contains exactly K = 2 distinct integers greater than A_i. Therefore, the answer for K = 2 is 2.

Sample Input 2

1
1

Sample Output 2

1

Sample Input 3

10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

Sample Output 3

2
1
2
1
2
1
1
0
0
0

Problem Statement

You are given simple undirected graphs G and H, each with N vertices: vertices 1, 2, \ldots, N. Graph G has M_G edges, and its i-th edge (1\leq i\leq M_G) connects vertices u_i and v_i. Graph H has M_H edges, and its i-th edge (1\leq i\leq M_H) connects vertices a_i and b_i.

You can perform the following operation on graph H any number of times, possibly zero.

• Choose a pair of integers (i,j) satisfying 1\leq i<j\leq N. Pay A_{i,j} yen, and if there is no edge between vertices i and j in H, add one; if there is, remove it.

Find the minimum total cost required to make G and H isomorphic.

Constraints

• 1\leq N\leq8
• 0\leq M _ G\leq\dfrac{N(N-1)}2
• 0\leq M _ H\leq\dfrac{N(N-1)}2
• 1\leq u _ i\lt v _ i\leq N\ (1\leq i\leq M _ G)
• (u _ i,v _ i)\neq(u _ j,v _ j)\ (1\leq i\lt j\leq M _ G)
• 1\leq a _ i\lt b _ i\leq N\ (1\leq i\leq M _ H)
• (a _ i,b _ i)\neq(a _ j,b _ j)\ (1\leq i\lt j\leq M _ H)
• 1\leq A _ {i,j}\leq 10 ^ 6\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

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

Sample Output 1

9

The given graphs are as follows:

For example, you can perform the following four operations on H to make it isomorphic to G at a cost of 9 yen.

• Choose (i,j)=(1,3). There is an edge between vertices 1 and 3 in H, so pay 1 yen to remove it.
• Choose (i,j)=(2,5). There is no edge between vertices 2 and 5 in H, so pay 2 yen to add it.
• Choose (i,j)=(1,5). There is an edge between vertices 1 and 5 in H, so pay 1 yen to remove it.
• Choose (i,j)=(3,5). There is no edge between vertices 3 and 5 in H, so pay 5 yen to add it.

After these operations, H becomes:

You cannot make G and H isomorphic at a cost less than 9 yen, so print 9.

Sample Input 2

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

Sample Output 2

3

For example, performing the operations (i,j)=(2,3),(2,4),(3,4) on H will make it isomorphic to G.

Sample Input 3

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

Sample Output 3

5

For example, performing the operation (i,j)=(4,5) once will make G and H isomorphic.

Sample Input 4

2
0
0
371

Sample Output 4

0

Note that G and H may have no edges.

Also, it is possible that no operations are needed.

Sample Input 5

8
13
1 8
5 7
4 6
1 5
7 8
1 6
1 2
5 8
2 6
5 6
6 7
3 7
4 8
15
3 5
1 7
4 6
3 8
7 8
1 2
5 6
1 6
1 5
1 4
2 8
2 6
2 4
4 7
1 3
7483 1694 5868 3296 9723 5299 4326
5195 4088 5871 1384 2491 6562
1149 6326 2996 9845 7557
4041 7720 1554 5060
8329 8541 3530
4652 3874
3748

Sample Output 5

21214

Problem Statement

You are given a directed graph with N vertices and M edges. The j-th directed edge goes from vertex u_j to vertex v_j and has a weight of w_j.

Find one way to write an integer between -10^{18} and 10^{18}, inclusive, to each vertex such that the following condition is satisfied.

• Let x_i be the value written on vertex i. For all edges j=1,2,\dots,M, it holds that x_{v_j} - x_{u_j} = w_j.

It is guaranteed that at least one such assignment exists for the given input.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}
• 1 \leq u_j, v_j \leq N
• u_j \neq v_j
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j) and (u_i, v_i) \neq (v_j, u_j)
• |w_j| \leq 10^9
• All input values are integers.
• There exists at least one assignment satisfying the conditions.

Sample Input 1

3 3
1 2 2
3 2 3
1 3 -1

Sample Output 1

3 5 2

By setting x = (3, 5, 2), we have x_2 - x_1 = w_1 = 2, x_2 - x_3 = w_2 = 3, x_3 - x_1 = w_3 = -1, satisfying the conditions.

For example, x = (-1, 1, -2) is also a valid answer.

Sample Input 2

4 2
2 1 5
3 4 -3

Sample Output 2

5 0 6 3

For example, x = (0, -5, 4, 1) and x = (5, 0, 4, 1) are also valid answers.

Sample Input 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

Sample Output 3

200401298 182231955 -106709603 69445364 278499365

Problem Statement

You are given N points (x_1, y_1), (x_2, y_2), \dots, (x_N, y_N) on a two-dimensional plane, and a non-negative integer D.

Find the number of integer pairs (x, y) such that \displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq D \leq 10^6
• -10^6 \leq x_i, y_i \leq 10^6
• (x_i, y_i) \neq (x_j, y_j) for i \neq j.
• All input values are integers.

Sample Input 1

2 3
0 0
1 0

Sample Output 1

8

The following figure visualizes the input and the answer for Sample 1. The blue points represent the input. The blue and red points, eight in total, satisfy the condition in the statement.

Sample Input 2

2 0
0 0
2 0

Sample Output 2

0

Sample Input 3

6 100
9 -6
10 -1
2 10
-1 7
-7 5
-1 -4

Sample Output 3

419

Problem Statement

Given are N distinct points in a two-dimensional plane. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

Let us define the distance between two points i and j be \mathrm{min} (|x_i-x_j|,|y_i-y_j|): the smaller of the difference in the x-coordinates and the difference in the y-coordinates.

Find the maximum distance between two different points.

Constraints

• 2 \leq N \leq 200000
• 0 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 3
3 1
4 10

Sample Output 1

4

The distances between Points 1 and 2, between Points 1 and 3, and between Points 2 and 3 are 2, 4, and 1, respectively, so your output should be 4.

Sample Input 2

4
0 1
0 4
0 10
0 6

Sample Output 2

0

Sample Input 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

Sample Output 3

801