Problem Statement

You are given N real values A_1, A_2, \ldots, A_N. Compute the number of pairs of indices (i, j) such that i < j and the product A_i \cdot A_j is integer.

Constraints

• 2 \leq N \leq 200\,000
• 0 < A_i < 10^4
• A_i is given with at most 9 digits after the decimal.

Sample Input 1

5
7.5
2.4
17.000000001
17
16.000000000

Sample Output 1

3

There are 3 pairs with integer product:

• 7.5 \cdot 2.4 = 18
• 7.5 \cdot 16 = 120
• 17 \cdot 16 = 272

Sample Input 2

11
0.9
1
1
1.25
2.30000
5
70
0.000000001
9999.999999999
0.999999999
1.000000001

Sample Output 2

8

Problem Statement

Limak can repeatedly remove one of the first two characters of a string, for example abcxyx \rightarrow acxyx \rightarrow cxyx \rightarrow cyx.

You are given N different strings S_1, S_2, \ldots, S_N. Among N \cdot (N-1) / 2 pairs (S_i, S_j), in how many pairs could Limak obtain one string from the other?

Constraints

• 2 \leq N \leq 200\,000
• S_i consists of lowercase English letters a-z.
• S_i \neq S_j
• 1 \leq |S_i|
• |S_1| + |S_2| + \ldots + |S_N| \leq 10^6

Sample Input 1

3
abcxyx
cyx
abc

Sample Output 1

1

The only good pair is (abcxyx, cyx).

Sample Input 2

6
b
a
abc
c
d
ab

Sample Output 2

5

There are five good pairs: (b, abc), (a, abc), (abc, c), (b, ab), (a, ab).

Problem Statement

Let’s take a prime P = 200\,003. You are given N integers A_1, A_2, \ldots, A_N. Find the sum of ((A_i \cdot A_j) \bmod P) over all N \cdot (N-1) / 2 unordered pairs of elements (i < j).

Please note that the sum isn't computed modulo P.

Constraints

• 2 \leq N \leq 200\,000
• 0 \leq A_i < P = 200\,003
• All values in input are integers.

Sample Input 1

4
2019 0 2020 200002

Sample Output 1

474287

The non-zero products are:

• 2019 \cdot 2020 \bmod P = 78320
• 2019 \cdot 200002 \bmod P = 197984
• 2020 \cdot 200002 \bmod P = 197983

So the answer is 0 + 78320 + 197984 + 0 + 0 + 197983 = 474287.

Sample Input 2

5
1 1 2 2 100000

Sample Output 2

600013

Problem Statement

Inspired by the tv series Stranger Things, bear Limak is going for a walk between two mirror worlds.

There are two perfect binary trees of height H, each with the standard numeration of vertices from 1 to 2^H-1. The root is 1 and the children of x are 2 \cdot x and 2 \cdot x + 1.

Let L denote the number of leaves in a single tree, L = 2^{H-1}.

You are given a permutation P_1, P_2, \ldots, P_L of numbers 1 through L. It describes L special edges that connect leaves of the two trees. There is a special edge between vertex L+i-1 in the first tree and vertex L+P_i-1 in the second tree.

drawing for the first sample test, permutation P = (2, 3, 1, 4), special edges in green

Let's define product of a cycle as the product of numbers in its vertices. Compute the sum of products of all simple cycles that have exactly two special edges, modulo (10^9+7).

A simple cycle is a cycle of length at least 3, without repeated vertices or edges.

Constraints

• 2 \leq H \leq 18
• 1 \leq P_i \leq L where L = 2^{H-1}
• P_i \neq P_j (so this is a permutation)

Sample Input 1

3
2 3 1 4

Sample Output 1

121788

The following drawings show two valid cycles (but there are more!) with products 2 \cdot 5 \cdot 6 \cdot 3 \cdot 1 \cdot 2 \cdot 5 \cdot 4 = 7200 and 1 \cdot 3 \cdot 7 \cdot 7 \cdot 3 \cdot 1 \cdot 2 \cdot 5 \cdot 4 \cdot 2 = 35280. The third cycle is invalid because it doesn't have exactly two special edges.

Sample Input 2

2
1 2

Sample Output 2

36

The only simple cycle in the graph indeed has two special edges, and the product of vertices is 1 \cdot 3 \cdot 3 \cdot 1 \cdot 2 \cdot 2 = 36.

Sample Input 3

5
6 14 15 7 12 16 5 4 11 9 3 10 8 2 13 1

Sample Output 3

10199246

Problem Statement

This is an output-only problem. You shouldn't read anything from the input.

In short, your task is to simulate multiplication by using only comparison (x < y) and addition (x + y). There is no input in this problem, you just print a sequence of operations.

Imagine that there is a big array a[0], a[1], ..., a[N-1] of length N. The first two values are initially two non-negative integers A and B (which are unknown to you), the other elements are zeros. Your goal is to get the product A \cdot B in a[2] at the end.

You are allowed operations of two types, with the following format (where 0 \leq i, j, k < N):

• + i j k — applies operation a[k] = a[i] + a[j].
• < i j k — applies operation a[k] = a[i] < a[j]. That is, if a[i] < a[j] then a[k] becomes 1, otherwise it becomes 0.

You can use at most Q operations. Elements of a can't exceed V. Indices (i, j, k) don't have to be distinct. It's allowed to modify any element of the array (including the first two). The actual checker simulates the process for multiple pairs (A, B) within a single test. Each time, the checker chooses values A and B, creates the array a = [A, B, 0, 0, \ldots, 0], applies all your operations and ensures that a[2] = A \cdot B.

Constraints

• 0 \leq A, B \leq 10^9
• N = Q = 200\,000
• V = 10^{19} = 10\,000\,000\,000\,000\,000\,000

Partial Score

• 800 points will be awarded for passing tests that satisfy A, B \leq 10.
• Another 1000 points will be awarded for passing all tests.

Sample Input 1

Sample Output 1

4
< 0 1 8
+ 0 1 2
+ 2 8 2
+ 0 0 0

In the first sample test, the checker checks your sequence only for a pair (A, B) = (2, 3). The provided output is correct for this test:

• Initially, a[0] = 2, a[1] = 3, a[2] = a[3] = \ldots = a[N-1] = 0.
• < 0 1 8 applies a[8] = 1 because a[0] < a[1].
• + 0 1 2 applies a[2] = a[0] + a[1] = 5.
• + 2 8 2 applies a[2] = a[2] + a[8] = 6.
• + 0 0 0 applies a[0] = a[0] + a[0] = 4.
• As required, at the end we have a[2] = 6 = A \cdot B.

Problem Statement

You are given positions (X_i, Y_i) of N enemy rooks on an infinite chessboard. No two rooks attack each other (at most one rook per row or column).

You're going to replace one rook with a king and then move the king repeatedly to beat as many rooks as possible.

You can't enter a cell that is being attacked by a rook. Additionally, you can't move diagonally to an empty cell (but you can beat a rook diagonally).

(So this king moves like a superpawn that beats diagonally in 4 directions and moves horizontally/vertically in 4 directions.)

For each rook, consider replacing it with a king, and find the minimum possible number of moves needed to beat the maximum possible number of rooks.

Constraints

• 2 \leq N \leq 200\,000
• 1 \leq X_i, Y_i \leq 10^6
• X_i \neq X_j
• Y_i \neq Y_j
• All values in input are integers.

Sample Input 1

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

Sample Output 1

5
0
7
5
0
0

See the drawing below. If we replace rook 3 with a king, we can beat at most two other rooks. The red path is one of optimal sequences of moves: beat rook 1, then keep going down and right until you can beat rook 4. There are 7 steps and that's the third number in the output.

x-coordinate increases from left to right, while y increases bottom to top.

Starting from rook 2, 5 or 6, we can't beat any other rook. The optimal number of moves is 0.

Sample Input 2

5
5 5
100 100
70 20
81 70
800 1

Sample Output 2

985
985
1065
1034
0

Sample Input 3

10
2 5
4 4
13 12
12 13
14 17
17 19
22 22
16 18
19 27
25 26

Sample Output 3

2
2
9
9
3
3
24
5
0
25