Problem Statement

You are given a positive integer D.

Find the minimum value of |x^2+y^2-D| for non-negative integers x and y.

Constraints

• 1\leq D \leq 2\times 10^{12}
• All input values are integers.

Sample Input 1

21

Sample Output 1

1

For x=4 and y=2, we have |x^2+y^2-D| = |16+4-21|=1.

There are no non-negative integers x and y such that |x^2+y^2-D|=0, so the answer is 1.

Sample Input 2

998244353

Sample Output 2

0

Sample Input 3

264428617

Sample Output 3

32

Problem Statement

There is a 9\times 9 grid A, where each cell contains an integer between 1 and 9, inclusive.
Specifically, the cell at the i-th row from the top and j-th column from the left contains A_{i,j}.

If A satisfies all of the following conditions, print Yes. Otherwise, print No.

• For each row of A, the nine cells in that row contain each integer from 1 to 9 exactly once.
• For each column of A, the nine cells in that column contain each integer from 1 to 9 exactly once.
• Divide the rows of A into three groups, each of three rows, from top to bottom, and similarly divide the columns into three groups, each of three columns, from left to right. Each 3\times 3 grid obtained from A in this way contains each integer from 1 to 9 exactly once.

Constraints

• 1\leq A_{i,j}\leq 9
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

The grid A is shown below.

The grid A satisfies all three conditions, so print Yes.

Sample Input 2

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

Sample Output 2

No

The grid A is shown below.

For example, if you look at the top left 3\times 3 grid, you can see that the third condition is unsatisfied, so print No.

Sample Input 3

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

Sample Output 3

No

The grid A is shown below.

For example, if you look at the leftmost column, you can see that the second condition is unsatisfied, so print No.

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

• 4 \leq N \leq 2000
• 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

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

Sample Output 3

1

Problem Statement

Given is an undirected graph with N vertices and M edges. The vertices are called Vertex 1, Vertex 2, \ldots, Vertex N, and the edges are called Edge 1, Edge 2, \ldots, Edge M. Edge i (1 \leq i \leq M) connects Vertex U_i and Vertex V_i. It is guaranteed that the graph is simple: it has no self-loops and no multi-edges.

There are 2^M ways to direct every edge in this graph. We want each vertex to have exactly one edge going from that vertex to another vertex. How many ways are there to direct the edges in that way? Since the answer may be enormous, print it modulo 998244353.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq M \leq 2\times 10^5
• 1 \leq U_i,V_i \leq N
• U_i \neq V_i
• All values in input are integers.
• The given graph is simple.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

There are two ways to direct the edges to achieve the objective:

• 1\rightarrow 2 , 2\rightarrow 3 , 1\leftarrow 3
• 1\leftarrow 2 , 2\leftarrow 3 , 1\rightarrow 3

Sample Input 2

2 1
1 2

Sample Output 2

0

It is obviously impossible to make every vertex have one edge going from that vertex.

Sample Input 3

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

Sample Output 3

4

Problem Statement

Takahashi and Aoki have N and M bottles of sugar water, respectively.
Takahashi's i-th sugar water is composed of A_i grams of sugar and B_i grams of water.
Aoki's i-th sugar water is composed of C_i grams of sugar and D_i grams of water.
There are NM ways to choose one from Takahashi's sugar waters and one from Aoki's and mix them. Among the NM sugar waters that can be obtained in this way, find the concentration of sugar in the sugar water with the K-th highest concentration of sugar.
Here, the concentration of sugar in sugar water composed of x grams of sugar and y grams of water is \dfrac{100x}{x+y} percent. We will ignore saturation.

Constraints

• 1 \leq N, M \leq 5 \times 10^4
• 1 \leq K \leq N \times M
• 1 \leq A_i, B_i, C_i, D_i \leq 10^5
• All values in the input are integers.

Sample Input 1

3 1 1
1 2
4 1
1 4
1 4

Sample Output 1

50.000000000000000

Let (i, j) denote the sugar water obtained by mixing Takahashi's i-th sugar water and Aoki's j-th.
Below are the sugar waters that can be obtained and their concentrations of sugar.

• (1, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (2 + 4)} = 25 \%
• (2, 1) : 100 \times \frac{1 + 4}{(4 + 1) + (1 + 4)} = 50 \%
• (3, 1) : 100 \times \frac{1 + 1}{(1 + 1) + (4 + 4)} = 20 \%

Among them, the sugar water with the highest concentration of sugar is (2, 1), with a concentration of 50 percent.

Sample Input 2

2 2 2
6 4
10 1
5 8
9 6

Sample Output 2

62.500000000000000

Sample Input 3

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

Sample Output 3

54.166666666666664