HAMMERWARS 2025
A1. Fire tower 3D (easy version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2 2 1 2
1 1
Output
11
Input
1 5 1 10
1 3
Output
53
Input
4 3 6 6
1 1
2 2
3 1
3 3
4 1
4 2
Output
83

A2. Fire tower 3D (hard version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2 2 1 2
1 1
Output
11
Input
1 5 1 10
1 3
Output
53
Input
4 3 6 6
1 1
2 2
3 1
3 3
4 1
4 2
Output
83

B. Coloring book
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Thomas has generously provided $$$n$$$ lines in a plane! The lines are in regular position! That is, no two lines are collinear and no three lines intersect at a point.

The lines divide the plane into regions. Formally, points $$$A$$$ and $$$B$$$ are in the same region if and only if the segment $$$\overline{\rm AB}$$$ doesn't intersect a line. Two regions are adjacent if their boundaries overlap on a segment.

Arvind and Zhongtang are going to play a game on the regions. First, Arvind will select a region and color it red. Then turns will proceed as follows: Zhongtang will select a region adjacent to a red region and color it blue, then Arvind will select a region adjacent to a blue region and color it red. The last person who can play wins.

You want prime betting odds. Can you predict the outcome of the game with perfect play?

Input

$$$n \\ a_1 \ b_1 \ c_1 \ d_1 \\ a_2 \ b_2 \ c_2 \ d_2 \\ \ldots \\ a_n \ b_n \ c_n \ d_n$$$

The $$$i$$$-th line passes through lattice points $$$(a_i,b_i)$$$ and $$$(c_i,d_i)$$$.

Constraints

$$$2 \le n \le 2 \cdot 10^5 \\ \max(|a_i|,|b_i|,|c_i|,|d_i|) \le 10^9$$$

Output

"Arvind" or "Zhongtang" (without quotes)

Example
Input
2
0 0 2 1
1 1 3 5
Output
Zhongtang
Note

TODO: diagram for sample

C1. Sorted subarrays (easy version)
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
5
1 9 6 9 8
Output
2 4 5
Input
20
21 13 34 1 21 7 36 24 44 31 19 46 42 45 35 21 46 16 43 45
Output
12 14 16 18 19 20

C2. Sorted subarrays (hard version)
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
5
1 9 6 9 8
Output
2 4 5
Input
20
21 13 34 1 21 7 36 24 44 31 19 46 42 45 35 21 46 16 43 45
Output
12 14 16 18 19 20

D1. Networking (easy version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
7 5 4
2 1 5
1 4 9
1 7 6
2 5 7
7 3 3
2 6 2
2 3 8
3 4 10
4 6 5
3 1 2
6 1 10
Output
0 5 2 9
5 0 7 7
2 7 0 10
9 7 10 0

D2. Networking (hard version)
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
7 5 4
2 1 5
1 4 9
1 7 6
2 5 7
7 3 3
2 6 2
2 3 8
3 4 10
4 6 5
3 1 2
6 1 10
Output
0 5 2 9
5 0 7 7
2 7 0 10
9 7 10 0

E. Research
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3 100 1 2
Output
125000001
Input
10 10 9 10
Output
60520013

F. Peter's polygon problem
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
5
4 2 9 1 4
Output
1 5
Input
10
69 42 1 2 1 46 1 2 1 10
Output
1 6

G. Positivity
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Egor has an array $$$a_1,a_2,...,a_n$$$ of integers and a permutation $$$p_1,p_2,...,p_n$$$ with $$$i \neq p_i$$$ for all $$$i$$$.

Egor is all about good vibes! He wants to make $$$a_i + a_{p_i}$$$ nonnegative for all $$$i$$$ after applying at most $$$\lfloor \frac{n}{2} \rfloor$$$ operations. In one operation, he will choose $$$x$$$ and negate both $$$a_x$$$ and $$$a_{p_x}$$$.

Help Egor choose the operation sequence!

Input

$$$n \\ a_1 \ a_2 \ \ldots \ a_n \\ p_1 \ p_2 \ \ldots \ p_n$$$

Constraints

$$$n \le 2 \cdot 10^5 \\ |a_i| \le 10^9$$$

Output

$$$x_1 \ x_2 \ \ldots \ x_n$$$

$$$x_i$$$ is the $$$i$$$-th choice of $$$x$$$

Examples
Input
4
3 -4 5 -6
2 1 4 3
Output
2
2 4
Input
6
1 -2 1 -2 1 -2
2 3 4 5 6 1
Output
3
2 3 6

H. Equivalence classes
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
2 2
Output
4
12
Input
5 5
Output
32
14880
744000
8630400
24165120

I. Complete and complement
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an undirected disconnected graph $$$G_1$$$ with $$$n$$$ vertices, conveniently labeled $$$1$$$ through $$$n$$$. You can perform the following two operations on $$$G_1$$$:

  1. Pick distinct vertices $$$x,y,z$$$, such that the edges $$$(x,y)$$$ and $$$(y,z)$$$ are in the graph, but $$$(x,z)$$$ is not in the graph. Then, add the edge $$$(x,z)$$$ to the graph.
  2. For all pairs of distinct vertices $$$x,y$$$: if the edge $$$(x,y)$$$ is in the graph, then remove it from the graph. Otherwise add it to the graph.

Now you are given a second graph $$$G_2$$$ with the same vertex set. Transform $$$G_1$$$ into $$$G_2$$$ using at most $$$n^2$$$ of the operations, or say it's impossible.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \leq t \leq 250$$$).

The first line of each test contains $$$n$$$, the number of vertices in $$$G_1$$$ and $$$G_2$$$ ($$$2 \leq n \leq 10^3$$$).

The next $$$n$$$ lines each contain strings of length $$$n$$$, consisting of 0s and 1s, which describe $$$G_1$$$. The $$$j$$$-th character of the $$$i$$$-th string (denoted $$$s_{i,j}$$$) is 1 if there is an edge between vertex $$$i$$$ and vertex $$$j$$$, and is 0 otherwise.

The next $$$n$$$ lines each contain strings of length $$$n$$$, describing $$$G_2$$$ in the same format as $$$G_1$$$.

It is guaranteed that for both graphs, and for all $$$1 \leq i, j \leq n$$$, that $$$s_{i,j} = s_{j,i}$$$ and $$$s_{i,i}=0$$$.

It is guaranteed that $$$G_1$$$ is disconnected. It is NOT guaranteed that $$$G_2$$$ is disconnected.

It is guaranteed that the sum of $$$n$$$ across all tests does not exceed $$$10^3$$$.

Output

For each test, if the goal is impossible, output -1.

Otherwise, on the first line, output $$$k$$$, the number of operations you perform ($$$0 \leq k \leq n^2$$$).

On the following $$$k$$$ lines: first output an integer $$$1 \leq type \leq 2$$$ denoting the type of move you wish to perform.

If $$$type=1$$$, then you should also output $$$3$$$ distinct integers $$$1 \leq x, y, z \leq n$$$ such that edges $$$(x,y)$$$ and $$$(y,z)$$$ exist in the graph, but $$$(x,z)$$$ does not. Note that the order in which you output these numbers matters.

If there are multiple possible answers using at most $$$n^2$$$ moves, you can output any. You do not need to minimize the number of moves. We can show that if an answer exists, there is a way to achieve the goal using at most $$$n^2$$$ moves.

Examples
Input
2
2
00
00
01
10
2
00
00
00
00
Output
1
2

2
2
2
Input
2
4
0100
1000
0001
0010
0111
1011
1101
1110
4
0100
1000
0001
0010
0100
1010
0101
0010
Output
3
2
1 4 1 3
1 2 4 1

-1
Note

In the first two sample tests, we start with a graph with $$$2$$$ vertices and no edges.

  • In the first test, $$$G_2$$$ is the complement of $$$G_1$$$, so we just need to apply operation $$$2$$$ once.
  • In the second test, $$$G_2$$$ is already equal to $$$G_1$$$, so we don't need to apply any operations. But we don't need to minimize the number of operations, so it's fine if we perform operation $$$2$$$ twice.

In the third sample test, the sequence of operations performed looks like this:

In the fourth sample test, we can show there is no answer.

J. Immense integers
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
01
00101
00010
Output
1
Input
0001101110
0011111110
00000101
Output
3
Input
0100010110110001011011101
0101101011101101101010011
0000000000000000000011
Output
17

K. Sadism
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
4
1 0 0 2
Output
2 5 2 1 0
Input
7
1 5 4 2 6 0 3
Output
16 10 0 1 0 0 0 1

L. Birthday bash
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Today is Alice's birthday! She invited you and her $$$N-2$$$ other friends to her birthday bash.

The birthday cake is a convex polygons with $$$N$$$ sides such that no two adjacent sides are parallel. Once they sing Happy Birthday, the cake is cut as follows: a point $$$P$$$ is uniformly chosen at random in the interior of the pizza; from point $$$P$$$, $$$N$$$ cuts are made to the corners cake creating $$$N$$$ triangular slices. Since you and Alice are nice, you let your $$$N-2$$$ friends first take a slice, then you take a slice, and Alice gets the last one.

If everyone greedily takes cake slices by area, what is the expected area of your slice?

Input

The first line contains a single integer $$$N$$$ ($$$3 \leq N \leq 200$$$).

The $$$i$$$-th of the following $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$: the coordinates of the $$$i$$$-th polygon vertex ($$$-10^5 \leq x_i, y_i \leq 10^5$$$). The $$$x$$$-axis runs from left to right, and the $$$y$$$-axis runs from bottom to top. The vertices are numbered in counterclockwise order.

Output

Print one real number: the expected area of your slice of cake. Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Examples
Input
4
0 0
1 0
1 1
0 1
Output
0.1666666667
Input
10
-43 33
-35 -39
32 -41
46 -12
50 30
50 34
49 38
42 49
37 49
-6 44
Output
95.7188121428