Problem Statement

In the xy-plane, we have N points numbered 1 through N.
Point i is at the coordinates (X_i,Y_i). Any two different points are at different positions.
Find the number of ways to choose three of these N points so that connecting the chosen points with segments results in a triangle with a positive area.

Constraints

• All values in input are integers.
• 3 \le N \le 300
• -10^9 \le X_i,Y_i \le 10^9
• (X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Sample Input 1

4
0 1
1 3
1 1
-1 -1

Sample Output 1

3

The figure below illustrates the points.

There are three ways to choose points that form a triangle: \{1,2,3\},\{1,3,4\},\{2,3,4\}.

Sample Input 2

20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

Sample Output 2

1124

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

• For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
• When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

• 0\leq S _ x\leq2\times10 ^ {16}
• 0\leq S _ y\leq2\times10 ^ {16}
• 0\leq T _ x\leq2\times10 ^ {16}
• 0\leq T _ y\leq2\times10 ^ {16}
• All input values are integers.

Sample Input 1

5 0
2 5

Sample Output 1

5

For example, Takahashi can pay a toll of 5 by moving as follows:

• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.
• Move left by 1. Pay a toll of 0.
• Move up by 3. Pay a toll of 3.
• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

0

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.

Problem Statement

A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).

Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:

• a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).

Find the number, modulo 998244353, of sequences that can be C.

Constraints

• 1 \leq N \leq 3000
• 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
• The sequences A and B are non-decreasing.
• All values in input are integers.

Sample Input 1

2
1 1
2 3

Sample Output 1

5

There are five sequences that can be C, as follows.

• (1, 1)
• (1, 2)
• (1, 3)
• (2, 2)
• (2, 3)

Note that (2, 1) does not satisfy the condition since it is not non-decreasing.

Sample Input 2

3
2 2 2
2 2 2

Sample Output 2

1

There is one sequence that can be C, as follows.

• (2, 2, 2)

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

Sample Output 3

978222082

Be sure to find the count modulo 998244353.

Problem Statement

There is an undirected graph with N vertices and 0 edges. The vertices are numbered 1 to N.

You are given Q queries to process in order. Each query is of one of the following two types:

• Type 1: Given in the format 1 u v. Add an edge between vertices u and v.
• Type 2: Given in the format 2 v k. Print the k-th largest vertex number among the vertices connected to vertex v. If there are fewer than k vertices connected to v, print -1.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• In a Type 1 query, 1 \leq u < v \leq N.
• In a Type 2 query, 1 \leq v \leq N, 1 \leq k \leq 10.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
-1
4
2
-1

• In the first query, an edge is added between vertices 1 and 2.
• In the second query, two vertices are connected to vertex 1: 1 and 2. Among them, the 1-st largest vertex number is 2, which should be printed.
• In the third query, two vertices are connected to vertex 1: 1 and 2. Among them, the 2-nd largest vertex number is 1, which should be printed.
• In the fourth query, two vertices are connected to vertex 1: 1 and 2, which is fewer than 3, so print -1.
• In the fifth query, an edge is added between vertices 1 and 3.
• In the sixth query, an edge is added between vertices 2 and 3.
• In the seventh query, an edge is added between vertices 3 and 4.
• In the eighth query, four vertices are connected to vertex 1: 1,2,3,4. Among them, the 1-st largest vertex number is 4, which should be printed.
• In the ninth query, four vertices are connected to vertex 1: 1,2,3,4. Among them, the 3-rd largest vertex number is 2, which should be printed.
• In the tenth query, four vertices are connected to vertex 1: 1,2,3,4, which is fewer than 5, so print -1.

Sample Input 2

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

Sample Output 2

1
5
-1
3
6
2
5
-1
5
3
6
4
4

Problem Statement

You are given integers N, M and a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N).

For k = 0, 1, \ldots, M-1, solve the following problem:

Define an integer sequence B = (B_1, B_2, \ldots, B_N) so that B_i is the remainder of A_i + k when divided by M. Find the inversion number in B.

Constraints

• 1 \le N,M \le 2\times 10^5
• 0 \le A_i < M
• All input values are integers.

Sample Input 1

3 3
2 1 0

Sample Output 1

3
1
1

• For k=0: B=(2, 1, 0). The inversion number is 3.
• For k=1: B=(0, 2, 1). The inversion number is 1.
• For k=2: B=(1, 0, 2). The inversion number is 1.

Sample Input 2

5 6
5 3 5 0 1

Sample Output 2

7
3
3
1
1
5

Sample Input 3

7 7
0 1 2 3 4 5 6

Sample Output 3

0
6
10
12
12
10
6