AGI (artificial general intelligence) is around the corner, but it still cannot add two integers modulo prime. In this task, you can speed up the AGI revolution by training a one-layer perceptron model with $$$n$$$ neurons for a fixed prime $$$p$$$. This model takes two integers $$$a$$$ and $$$b$$$ as inputs and calculates $$$(a + b) \bmod p$$$. The architecture of the model is:

$$$$$$ ReLU(a_{one-hot}W_{input}+b_{one-hot}W_{input})W_{output}^{T} $$$$$$

where

$$$$$$ ReLU(x) = max(x, 0) $$$$$$

and $$$x_{one-hot}$$$ is a matrix of size $$$1 \times p$$$, which consists of all zeros and a single one in column $$$x$$$.

For example, if $$$p=4$$$, $$$0_{one-hot} = \begin{pmatrix}1 & 0 & 0 & 0\end{pmatrix}$$$, $$$2_{one-hot} = \begin{pmatrix}0 & 0 & 1 & 0\end{pmatrix}$$$.

In other words, you must choose the number of neurons $$$n$$$ and generate two real matrices $$$W_{input}$$$ and $$$W_{output}$$$ of size $$$p \times n$$$.

To add integers $$$a$$$ and $$$b$$$ three steps are executed:

1. The pointwise sum of 0-indexed rows $$$a$$$ and $$$b$$$ of the $$$W_{input}$$$ is calculated.
2. All negative numbers in this sum are replaced with zeros. Let's call the generated row $$$M$$$.
3. The score of integer $$$i$$$ is defined as the scalar product of $$$M$$$ and $$$i$$$-th row of the $$$W_{output}$$$. The integer with the highest score should equal $$$(a+b) \bmod p$$$.

See the example explanation for better understanding.

You need to generate two real matrices $$$W_{input}$$$ and $$$W_{output}$$$ that for all pairs $$$(a, b), 0 \le a, b \lt p$$$, the output produced by the model is correct.

Sofia is the best wife, and she constantly comes up with new ideas on how to spend time with her husband. Idea $$$i$$$ could be described by a segment $$$[l_i..r_i]$$$. It means Sofia wants to visit some event that starts at day $$$l_i$$$ and ends at day $$$r_i$$$. If she decides to visit an event, she fully commits to it and is there every day from $$$l_i$$$ to $$$r_i$$$ inclusive.

Sofia can't visit more than one event each day. Also, if some event ends on day $$$d$$$ and another event starts on day $$$d$$$, she can only visit one of them.

After each new idea comes to her mind, she wonders what the biggest number of events she could visit.

This is an interactive problem.

There are $$$n$$$ sets numbered $$$1$$$ to $$$n$$$, the $$$i$$$-th of them containing only the integer $$$i$$$. You need to process $$$q$$$ queries. The $$$i$$$-th query (1-indexed) is described by a pair of integers $$$(X_i, Y_i)$$$. It creates a set number $$$n + i$$$, which consists of a union of integers from sets $$$X_i$$$ and $$$Y_i$$$.

Each time you create a new set, you must report the number of different integers in this set. You don't need to report the exact result. If the correct size of the set is $$$A$$$ and you print integer $$$B$$$, it will be accepted if $$$0.5 \cdot A \le B \le 2.0 \cdot A$$$.

Flushing the output could be costly on some Judging Systems, so all queries are split into batches of size 50. Your solution should read the first 50 queries, print the answers for all of them, flush the output, read the second batch of 50 queries, print the answers for them, flush the output, and so on. The last batch could consist of less than 50 queries.

The interactor is not adaptive, which means for each test, the sequence of queries is always the same for all runs.

$$$n$$$ points $$$a_1, a_2, ..., a_n$$$ are randomly generated inside a cube of size 1.

You are given a matrix $$$d$$$ with $$$d_{i,j}=d_{j,i}=dist(a_i, a_j)+rand(-0.1..0.1)$$$ and $$$d_{i,i}=0$$$. Here $$$dist(p, q)$$$ is the distance between points $$$\sqrt{(p_x-q_x)^2+(p_y-q_y)^2+(p_z-q_z)^2}$$$ and $$$rand(-0.1..0.1)$$$ is a random shift chosen uniformly from interval $$$[-0.1..0.1]$$$. Shifts for different pairs of points are chosen independently.

You need to construct a list of points $$$b_1, b_2, ..., b_n$$$ such that $$$\forall_{i, j} |dist(b_i, b_j)-d_{i,j}| \le 0.1$$$.

This is an interactive problem.

$$$n - 1$$$ random binary strings $$$s_i$$$ of length 50 are generated. Then, one of the strings is duplicated, and all $$$n$$$ strings are shuffled. You need to find indexes of equal strings.

You can ask at most $$$25\ 000$$$ queries. Each query is a pair $$$(i, j)$$$. The answer to the query is the Hamming distance between $$$s_i$$$ and $$$s_j$$$ — the number of positions where they differ.

It is guaranteed that all strings are picked randomly from the uniform distribution. Also, the list of strings is fixed for each test — interactor is not adaptive.

First, the interactor prints one integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the total number of strings.

Then, you can ask at most $$$25\ 000$$$ queries in the format "i j" ($$$1 \le i, j \le n, i \ne j$$$). Don't forget to flush the output after each query!

For each query, you will receive one integer $$$d$$$ ($$$0 \le d \le 50$$$) — the Hamming distance between $$$s_i$$$ and $$$s_j$$$. After receiving $$$d=0$$$, your program should terminate.

You are given a tree consisting of $$$n$$$ nodes. Initially, node $$$i$$$ has the integer $$$i$$$ written on it. You need to process $$$q$$$ queries of two types:

• + a v x — add $$$x$$$ to all integers written on a simple path from node $$$a$$$ to node $$$v$$$.
• ? a v — calculate the xor of all integers written on a simple path from node $$$a$$$ to node $$$v$$$.

For a given integer $$$n$$$, you must color each cell of an $$$n \times n$$$ grid into one of $$$C = 10 + \lfloor\frac{n^2}{100}\rfloor$$$ colors. Each specific color could be used at most 150 times.

For each cell $$$(r, c)$$$, the set of colors used in cells $$$(r_i, c_i)$$$ where $$$(r - r_i)^2 + (c - c_i)^2 \le 100$$$, should contain at most 8 different colors.

There is an array $$$a$$$ with $$$a[i] = i$$$ initially. $$$m$$$ operations are performed with this array. During each operation, two random indexes $$$i$$$ and $$$j$$$ are chosen, and elements $$$a[i]$$$ and $$$a[j]$$$ are swapped.

You need to answer $$$q$$$ queries. Each query is array $$$b_1$$$, $$$b_2$$$, ..., $$$b_k$$$. You need to find the first time when $$$b$$$ was a continuous subarray of $$$a$$$.

Indexes in swap operations are guaranteed to be chosen independently from a uniform distribution.

This is an interactive problem.

You are given $$$1000\$$$$. You play a game consisting of $$$T=1000$$$ rounds.

In each round, the jury randomly picks an integer $$$b$$$ from the range $$$[1..m]$$$, where $$$m$$$ is the amount of money you currently have. Each integer in this range has an equal probability of being chosen. You can either play this round or skip it. If you play in the round, one of the outcomes is selected with equal probability:

• You need to pay $$$b$$$ dollars.
• Jury gives you $$$2b$$$ dollars.

If, at some point, you have more than $$$10\,000$$$ dollars, you win. You lose if you have 0$ or the game ended (you played or skipped all $$$T$$$ rounds).

The first line contains one integer $$$T$$$ ($$$T=1000$$$ or $$$T=5$$$) — the number of rounds. It is guaranteed that $$$T=5$$$ is used only in the sample. Your solution is considered correct on the sample if you have a positive amount of money after $$$T$$$ rounds.

Each of the $$$T$$$ rounds starts with a command "ROUND m b", where $$$m$$$ is the amount of money you currently have and $$$b$$$ is a bet chosen by the jury for this round. You should respond with either "PLAY" or "SKIP". Don't forget to flush the output after each response!

If you have more than $$$10\,000$$$ dollars after some round, you will get the word "WIN" instead of the next round. If you lose, you will get the word "LOSE". Your program should terminate immediately after receiving "WIN" or "LOSE".

The following operation is performed at most 20 times with a square piece of paper of the size $$$1 \times 1$$$. Two points inside the square are picked uniformly at random, and a line is drawn through them.

Later, the paper is cut along all of the lines into $$$n$$$ pieces. Then, pieces are randomly rotated (but not flipped), shifted, and given to you. You need to figure out the initial position of each piece.

$$$n=10^4$$$ integers $$$a_1, a_2, ..., a_n$$$ are randomly and independently generated from the range $$$[1..10^{12}]$$$.

For each integer, you need to either discard it or put it into one of the sets $$$A$$$, $$$B$$$, or $$$C$$$. The sum of the integers in the set $$$A$$$ should be equal to the sum in the set $$$B$$$ and equal to the sum in the set $$$C$$$.

Each set should contain at least one integer. If there are multiple solutions, you could print any of them. It is guaranteed that the answer always exists for all tests in the system.

You are given a graph of the London Underground with 426 stations and 505 two-way connections between them. You are also given some subset of stations. You need to count the number of ways to add more (possibly zero) stations to this set so that no two stations are directly connected.

Two ways of adding stations are considered different if some station is present in one set and not present in another.

The number of ways could be big, so you need to output it modulo $$$998\,244\,353$$$.

Teamwork is critical in programming competitions! Effective communication and solution discussion among team members is key before implementation. Sometimes, team members might choose incorrect solutions and spend excessive time coding them. Other times, someone may suggest a more straightforward and simpler approach.

A team of three members is taking part in the competition. For each team member, you are given the time it takes for them to implement each of the problems. However, they share just one computer, so they could only work on one problem at a time. The contest has a duration of $$$300$$$ minutes. Your task is to compute the maximum number of different problems the team can solve. You can neglect the time required for switching between problems — if the total time required for solving problems doesn't exceed $$$300$$$ minutes, they could do it in time.

Let's look at the sample:

• The first team member likes geometry and is most effective at implementing problems such as "3D" or "JigsawPuzzle".
• The second team member likes constructive problems and would be the best for problems like "EqualStrings", "GeoSharding" or "InteractiveCasino". Although the problem "AplusB" may not be time-intensive to implement, the solution idea is not straightforward, so other team members couldn't solve it at all. This team member codes in Java and cannot solve "FastTreeQueries" due to the strict Time Limit.
• The last team member has a good library with already implemented data structures, so they could implement problems like "TheBestWife" faster than others.