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

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

Takahashi has N cards in his hand. For i = 1, 2, \ldots, N, the i-th card has an non-negative integer A_i written on it.

First, Takahashi will freely choose a card from his hand and put it on a table. Then, he will repeat the following operation as many times as he wants (possibly zero).

• Let X be the integer written on the last card put on the table. If his hand contains cards with the integer X or the integer (X+1)\bmod M written on them, freely choose one of those cards and put it on the table. Here, (X+1)\bmod M denotes the remainder when (X+1) is divided by M.

Print the smallest possible sum of the integers written on the cards that end up remaining in his hand.

Constraints

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

Sample Input 1

9 7
3 0 2 5 5 3 0 6 3

Sample Output 1

11

Assume that he first puts the fourth card (5 is written) on the table and then performs the following.

• Put the fifth card (5 is written) on the table.
• Put the eighth card (6 is written) on the table.
• Put the second card (0 is written) on the table.
• Put the seventh card (0 is written) on the table.

Then, the first, third, sixth, and ninth cards will end up remaining in his hand, and the sum of the integers on those cards is 3 + 2 + 3 +3 = 11. This is the minimum possible sum of the integers written on the cards that end up remaining in his hand.

Sample Input 2

1 10
4

Sample Output 2

0

Sample Input 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

Sample Output 3

99

Problem Statement

On a coordinate plane, there are N points P_1, P_2, \ldots, P_N, where point P_i has coordinates (X_i, Y_i).
The distance \text{dist}(A, B) between two points A and B is defined as follows:

A rabbit is initially at point A.
A rabbit at position (x, y) can jump to (x+1, y+1), (x+1, y-1), (x-1, y+1), or (x-1, y-1) in one jump.
\text{dist}(A, B) is defined as the minimum number of jumps required to get from point A to point B.
If it is impossible to get from point A to point B after any number of jumps, let \text{dist}(A, B) = 0.

Calculate the sum \displaystyle\sum_{i=1}^{N-1}\displaystyle\sum_{j=i+1}^N \text{dist}(P_i, P_j).

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq X_i, Y_i \leq 10^8
• For i \neq j, (X_i, Y_i) \neq (X_j, Y_j)
• All input values are integers.

Sample Input 1

3
0 0
1 3
5 6

Sample Output 1

3

P_1, P_2, and P_3 have coordinates (0,0), (1,3), and (5,6), respectively.
The rabbit can get from P_1 to P_2 in three jumps via (0,0) \to (1,1) \to (0,2) \to (1,3), but not in two or fewer jumps,
so \text{dist}(P_1, P_2) = 3.
The rabbit cannot get from P_1 to P_3 or from P_2 to P_3, so \text{dist}(P_1, P_3) = \text{dist}(P_2, P_3) = 0.

Therefore, the answer is \displaystyle\sum_{i=1}^{2}\displaystyle\sum_{j=i+1}^3\text{dist}(P_i, P_j)=\text{dist}(P_1, P_2)+\text{dist}(P_1, P_3)+\text{dist}(P_2, P_3)=3+0+0=3.

Sample Input 2

5
0 5
1 7
2 9
3 8
4 6

Sample Output 2

11

Problem Statement

You are given an integer sequence A of length N.

For each t = 1, 2, \dots, N, determine whether A_t is included in a longest increasing subsequence of A.

Here, A_t is included in a longest increasing subsequence of A if and only if the following holds:

• Let L be the length of a longest increasing subsequence of A. There exists a strictly increasing integer sequence i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L), where each element is between 1 and N, inclusive, that satisfies all of the following conditions:

  • A_{i_1} < A_{i_2} < \dots < A_{i_L}.
  • i_k = t for some k \ (1 \leq k \leq L).

You are given T test cases; solve each of them.

Constraints

• 1 \leq T \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• The sum of N across all test cases is at most 2 \times 10^5.

Sample Input 1

1
5
2 1 4 5 3

Sample Output 1

4
1 2 3 4

One of the longest increasing subsequences is (2, 4, 5), with a length of 3. Another longest increasing subsequence is (1, 4, 5). However, no longest increasing subsequence includes A_5.

Therefore, print 1, 2, 3, 4.

Sample Input 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

Sample Output 2

5
1 3 4 5 6
2
4 5