AGM 2022, Final Round, Day 2
A. Arrow Matrix
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Two pawns found themselves stuck in an $$$N$$$ by $$$M$$$ matrix consisting of arrows (up, right, down, left), where no arrow points to the outside of the matrix. The only way they can escape is if they manage to meet in a matrix cell at the same time.

Each second, both pawns will make one move in the direction shown by the arrow from their current cell.

Your job is to make exactly one change to an arrow by orientating it to another direction than the initial one (no arrow should point to the outside of the matrix). A change is valid, if when the pawns start moving from their initial positions, they will meet in the same matrix cell at some point in time.

You need to calculate the number of different valid changes. Two changes are different, if the resulting matrices are different from each other.

Input

The first line of the input contains the integers $$$N$$$ and $$$M$$$ ($$$1 \leq N*M \leq 10^6$$$), denoting the number of lines and columns of the matrix.

The second line contains two integers $$$X_1$$$ and $$$Y_1$$$ ($$$1 \leq X_1 \leq N$$$, $$$1 \leq Y_1 \leq M$$$), denoting the initial position of the first pawn.

The third line contains two integers $$$X_2$$$ and $$$Y_2$$$ ($$$1 \leq X_2 \leq N$$$, $$$1 \leq Y_2 \leq M$$$), denoting the initial position of the second pawn.

Each of the following $$$N$$$ lines contains a string of $$$M$$$ characters, describing the configuration of the arrows of that line. Thus, the $$$j$$$-th character of the $$$i$$$-th line ($$$1 \leq i \leq N$$$, $$$1 \leq j \leq M$$$) describes the orientation of the arrow from the line $$$i$$$ and column $$$j$$$ in the matrix:

  • $$$0$$$ - the arrow is pointing up
  • $$$1$$$ - the arrow is pointing right
  • $$$2$$$ - the arrow is pointing down
  • $$$3$$$ - the arrow is pointing left

It is guaranteed that no arrow points to the outside of the matrix.

Output

Output the total number of different valid changes.

Examples
Input
2 3
1 2
2 1
222
113
Output
7
Input
5 3
2 1
1 2
222
222
222
222
113
Output
22
Note

The initial matrix of the first example is:

$$$$$$ \begin{matrix} \downarrow & \downarrow & \downarrow\\ \rightarrow & \rightarrow & \leftarrow \end{matrix} $$$$$$

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

For the sake of having a problem statement, Bob has a large collection of $$$N$$$($$$1 \leq N \leq 10^5$$$) balls of radius $$$R$$$ $$$(1 \leq R \leq 10)$$$. He wants to roll them from one side of a table to the other. You might imagine the table as an 1D axis of infinite length.

A ball will roll from a given position $$$p_i$$$ ($$$0 \leq p_i \leq 10^9)$$$ with a non-zero speed $$$s_i (-10^9 \leq s_i \leq 10^9)$$$ to the left (negative speeds) or to the right (positive speeds) edge of the table, without ever falling down (the table is magical and has infinite length!). All balls start rolling at the same point in time, 0.

Now, Bob is wondering: given these balls, and the fact that they move from left to right or from right to left, what is their position during a moment in time, $$$T$$$ $$$(0 \leq T \leq 10^9)$$$? Of course, you can consider that the collision between two balls happens instantly, without friction, hence, after a collision, the balls simply swap their speeds.

Input

The first line of input contains three integers: N($$$1 \leq N \leq 10^5$$$), R($$$1 \leq R \leq 10$$$), T($$$0\leq T \leq 10^9$$$), representing the number of balls, the radius they have and the moment in time during which you must know where the balls are.

$$$N$$$ more lines will follow. Line $$$i$$$ will contain two positive integers, $$$p_i$$$($$$0 \leq p_i \leq 10^9$$$) and $$$s_i$$$($$$0 \lt |s_i| \leq 10^9$$$), denoting the initial position and the speed of ball $$$i$$$. If a ball rolls to the left, its speed will be $$$s_i$$$, where $$$-10^9 \leq s_i \leq -1$$$. Similarly, if a ball rolls to the right, its speed will be $$$s_i$$$, with $$$1 \leq s_i \leq 10^9$$$. It is guaranteed that initially the balls do not overlap, but they can touch each other.

Output

On a line, print $$$N$$$ values $$$p_i$$$ representing the position of all balls at moment of time $$$T$$$. Note that the positions should be printed in a non-decreasing order.

Example
Input
3 1 5
3 -1
8 -2
1 3
Output
-6 -2 20

C. Battleships
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After getting sick of being defeated in Battleships by his friend, Johnny invites him to play a new game of his own design - Mega Battleships. Mega Battleships plays exactly like Battleships, but the board is a lot bigger. The board in this game is $$$10^{6}$$$ by $$$10^{6}$$$.

Because the board is so big, he needs a little help to keep track of what is going on. Given the layout of his boats and the shots his opponent took, can you output the number of boats that were sunk? As a reminder, a boat is considered sunk, if all its cells have been hit.

Input

The first line of the input consists of $$$K$$$ ($$$1 \leq K \leq 10^{6}$$$) pairs of coordinates for the battleships, $$$c_1k$$$ and $$$c_2k$$$, representing the top left corner and bottom right corner respectively. Each pair is separated by a comma. We guarantee that the ships do not overlap.

The second line of the input is the list of distinct coordinates of the shots that were performed by the second player. There are at most $$$10^{6}$$$ such coordinates. They are separated by commas.

All the coordinates are provided in row-column order, with numbers for rows and letters for columns. For example, the top left corner's coordinate is 1A, the cell to its right is 1B, and the cell underneath it is 2A. Generally, the structure of a coordinate $$$c_k$$$ is $$$n_k l_k$$$ where $$$1 \leq n_k \leq 10^{6}$$$ and $$$A \leq l_k \leq BDWGN$$$ (after Z, the next column is AA and so on (and after ZZ, AAA); BDWGN is equivalent to $$$10^{6}$$$).

Output

The output file should consist of one integer which represents the number of ships that were sunk.

Example
Input
1A 2B,3C 3C,1C 2C
1C,2C,3C
Output
2

D. Flowers
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Having a nice garden is hard, especially when you are obsessed about the $$$aesthetics$$$. Such is the life of Ionel, who wants to have the prettiest garden he ever could. He also has a quite narrow point of view - in his eyes, flowers are either ugly or pretty - no in-between.

Therefore, to establish how beautiful a garden is, Ionel has patented a beauty coefficient. This coefficient is calculated as the number of squares that a garden has, such that the squares' perimeter is filled solely by beautiful flowers. In order to figure out how pretty his garden is, Ionel has tasked you with finding this coefficient.

Formally, you are given a matrix of size $$$N \times N$$$, where $$$1 \leq N \leq 3 \times 10^3$$$. Each cell of this matrix can either have value $$$0$$$, denoting an non-aesthetically pleasing flower, or value $$$1$$$, referring to a beautiful flower.

It is asked of you to compute the beauty coefficient $$$B$$$ - the number of square submatrices in the matrix whose perimeter consists solely of the value $$$1$$$.

Input

The first line of input contains one integers $$$N$$$, denoting the length of the matrix. Note that $$$1 \leq N \leq 3 \times 10^3$$$.

The next $$$N$$$ lines will contain $$$N$$$ integers $$$a_{ij}$$$, denoting whether the flower at cell $$$(i, j)$$$ is pretty or not. Note that $$$a_{ij}$$$ may either be $$$0$$$ or $$$1$$$.

Output

On a single line, print $$$B$$$, the number of squares in the matrix whose perimeter is surrounded only by $$$1$$$s.

Example
Input
5
1 1 1 0 0
1 0 1 0 0
1 1 1 1 1
0 0 1 0 1
0 0 1 1 1
Output
17

E. Language
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Captain Nix is passionate about languages. Programming languages especially. Now there's this new cool programming language called AGM (A Great programming not Markup language) with the following rules:

A valid instruction is either of the following:

  1. ; – The null instruction which does nothing
  2. BEG; – Marks the beginning of the program. Having any instruction before this one results in an error.
  3. END; – Marks the end of the program. Having any instruction after this one results in an error.
  4. $<name>; – Declare a variable with name $<name> and default value 0; Redeclaration of a variable results in an error.
  5. $<name> := <expression>; – Variable with name $name takes the value of the evaluated expression. If the variable is not declared, the result is error.
  6. <name>; – a label is declared with name <name>. Redeclaring a label results in an error (eg. redeclaring the BEG tag).
  7. GOTO <name>; – Jumps to the instruction following the tag <name>. Trying to jump to an undeclared tag results in an error.
  8. PRINT <expression>; – Prints the result of the expression
  9. BZ (<expression>) <instruction> – If the expression evaluates to $$$0$$$ then execute the instruction. In this particular case, the instruction cannot be a label declaration. Such a case will result in an error.
  10. BG (<expression>) <instruction> – If the expression evaluates to a value strictly greater than $$$0$$$, then execute the instruction. In this particular case, the instruction cannot be a label declaration. Such a case will result in an error.

A <name> is defined as follows:

  • is a string which starts with an letter
  • the following characters are alphanumeric (letters, decimals, underscores)
  • are used for variable names and label names
  • a variable name including $ must be at most $$$32$$$ characters in length. trying to access or declare a variable with a longer name will result in an error.
  • a label name must be at most $$$32$$$ characters in length. Trying to access or declare a label with a longer name will result in an error.

An Expression (<expression>) is defined recursively as follows:

  • Expression $$$\rightarrow$$$ (Expression) OR Expression <binary_operator> Expression OR Integer (eg. ($a + 2) * 4 / -$b)
  • Integer $$$\rightarrow$$$ integer_value OR <variable> OR <unary_operator><variable> (eg. 12 or -$v_2)

An <unary_operator> is either of the characters in this set {+, -, $$$\sim$$$}. A binary operator is any of the characters in this set {+, -, *, /, %, **, ^, &, |}.

The list of operators in them of descending priority is:

  • () (paranthesis)
  • ** (the power operator)
  • + - $$$\sim$$$ (positive, negative, bitwise not)
  • * / % (multiplication, division, modulo)
  • + - (addition, subtraction)
  • & (bitwise and)
  • ^ (bitwise xor)
  • | (bitwise or)

The list of keywords: ['BEG', 'END', 'BN', 'BZ', 'GOTO', 'PRINT']

Please note that:

  • Leading and Trailing whitespaces are ignored
  • Everything after the first ; on every line is ignored (like a comment)
  • Instructions not ending in ; will result in an error
  • The BEG; and END; instructions are inherently label definitions. Thus, you can use BEG and END in the GOTO command.
  • Variable scope is global. Variables can only be used after declaration.
  • Between operands, operators and keywords any number of whitespaces can be used, as they do not affect the execution of the program.
  • Empty lines (i.e. containing only whitespaces) are ignored and are not considered instructions.
  • A nonempty line, which does not fit the definition of any of the possible instructions will result in an error.
  • The language only accepts $$$32$$$ bit signed integers. Any explicit value (integer_value field) should fall in the limits of this data type. Otherwise, the execution results in an error.
  • If any intermediary or final result or an expression overflows is off-limits (needs more than $$$32$$$ bits to be represented), the respective value will be cropped like in any other C-like language (i.e. a bitwise and (&) with $$$(2^{32} - 1)$$$ will be applied).
  • Any division by $$$0$$$ results in an error.
  • /, % represent integer division (i.e. only the whole part of the result) and remainder after integer division.
  • If the final result of an expression is non integer execution terminates with error.
  • $$$\sim$$$ is the tilde symbol.

Captain Nix has some programs written in this amazing programming language and wonders what they do. Can you help out?

Input

The input files will contain characters on at most $$$100$$$ lines, representing the source code. It is guaranteed that there will be at most $$$10^3$$$ characters in the input and there will be at most $$$10^4$$$ instructions executed.

Output

Output the result of each print instruction on a separate line if there no error of any kind in the code (syntax or runtime error). Otherwise output a single line containing the text "error" with none of the potential output.

Examples
Input
PRINT $_5a;
GOTO BEG
$b = 10 */- 7;
END;
Output
error
Input
BEG;

PRINT 100 ** 2 * (3 ^ 1);

END;
Output
20000
Input
BEG;
$a;
$b;
$c;
$a := 0;
$b := 1;
start_loop;
$c := $a + $b;
BG ($c - 100) GOTO END;
PRINT $c;
$a := $b;
$b := $c;
GOTO start_loop;
END;
Output
1
2
3
5
8
13
21
34
55
89
Note

The first example outputs fibonacci terms less than 100.

The second example outputs the result of $$$100^2 \times (3 \oplus 1)$$$.

The third example has multiple errors. Not starting with BEG, improper variable name, use of undeclared variables, jump to non-declared labels, use of the wrong assignment operator, wrong expression formatting, instruction not ending with ; .

F. Lucky Coins
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

After losing a lot of money recently, you are desperately looking for ways to earn some. Today is your lucky day! Your generous friend proposes a game: He has a bag of coins, of which $$$N$$$ are green and $$$M$$$ are red. With equal probability, you draw one coin. If it is green, you earn $$$X$$$ euros, if it is red, you lose $$$Y$$$ euros. You can play this game as long as there are coins in the bag, or you can stop whenever you want and leave with your current earnings (or losses).

Given that you play optimally (you want to earn as much as you can), what is the maximum expected value of money you can earn?

Input

The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 2000$$$), $$$M$$$ ($$$1 \leq M \leq 2000$$$), $$$X$$$ ($$$1 \leq X \leq 10^9$$$) and $$$Y$$$ ($$$1 \leq Y \leq 10^9$$$), denoting the number of green coins, the number of red coins, how much money you earn if you draw a green coin and how much money you lose if you draw a red coin.

Output

On a single line, print the maximum expected value you can get if you play optimally. Your answer will be considered correct if the absolute or relative difference between your answer and judge's answer is less than $$$10^{-7}$$$.

Example
Input
1 2 4 3
Output
1.00000000

G. Mayor
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You just moved in your new country A.G.M. Lands and the mayor already called you in to give you a task. The elections are coming and the mayor heard that you are an amazing programmer, therefore he wants you to help him build a program that will let him understand what are his chances of success. You know that the country can be represented as a tree, that initially everyone loves the mayor and would 100% vote for him, and that both the mayor and his opponent are able to send their employees out in the country to try and persuade the residents to change their vote. Formally, you are given a tree containing $$$N$$$ nodes (rooted at node $$$1$$$), where each node has an initial probability of $$$1$$$ to vote for the Mayor, and $$$Q$$$ operations of the following types:

  1. $$$1$$$ $$$x$$$ $$$y$$$ $$$p$$$ $$$q$$$ $$$(0 \le p \lt 998244353, 1 \le q \lt 998244353, p \le q)$$$ - The Mayor's opponent will send out an employee to all residents between nodes $$$x$$$ and $$$y$$$ to convince them NOT to vote with the Mayor. For each resident, he has a probability of $$$p/q$$$ to convince them.
  2. $$$2$$$ $$$x$$$ $$$y$$$ $$$p$$$ $$$q$$$ $$$(0 \le p \lt 998244353, 1 \le q \lt 998244353, p \le q)$$$ - The Mayor will send out an employee to all residents between nodes $$$x$$$ and $$$y$$$ to convince them to vote with the Mayor. For each resident, he has a probability of $$$p/q$$$ to convince them.
  3. $$$3$$$ $$$x$$$ - The Mayor asks what is the expected value of the number of residents living in the subtree of node $$$x$$$ that will vote for him in that exact moment. The answer to this question should be given modulo $$$998244353$$$. The root of the tree is node $$$1$$$.
Input

On the first line, you are given an integer $$$N$$$ ($$$1 \le N \le 10^5$$$) denoting the number of residents. On the next $$$N - 1$$$ lines, there are two integers, $$$x$$$ ($$$1 \le x \le N$$$) and $$$y$$$ ($$$1 \le y \le N$$$), representing that there is a road between resident $$$x$$$ and resident $$$y$$$. On the next line, you are given an integer $$$Q$$$ ($$$1 \le Q \le 10^5$$$) denoting the number of operations. The next $$$Q$$$ lines will each contain the description of an operation as described above. Please note that for the operations $$$1$$$ and $$$2$$$, you should also take into account what the previous probability was and update accordingly. For example, if someone had a probability of $$$1$$$ to vote for the Mayor, and operation $$$2$$$ happens, the probability would remain $$$1$$$ since that person was already voting for the Mayor, therefore persuasion work was redundant.

Output

For each question from the mayor, print the answer modulo $$$998244353$$$ on a new line.

Example
Input
6
1 2
1 3
1 4
4 5
4 6
5
3 1
1 6 5 1 3
3 1
1 3 2 2 3
3 1
Output
6
5
3

H. Minimize
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Johnny found a set of points in the euclidean plane and noticed that each of the points has a certain weight $$$w_i$$$ associated with it. Johnny likes to optimize absolutely everything! This is why today he is trying to minimize anything he possibly can.

He started thinking about connecting those points with straight lines in order to form a tree that covers the entire set such that the total sum of the lengths of the segments connecting the points is the smallest possible. On this tree, node $$$i$$$ corresponds to point $$$i$$$. Then, he came up with a strange cost function that is computed in the following way:

  • He first roots the tree at node $$$1$$$.
  • If $$$node$$$ is a leaf, then $$$c_{node}\ =\ w_{node}$$$.
  • Otherwise, let $$$x_1$$$, $$$x_2$$$, .. $$$x_k$$$ be the children of $$$node$$$. He first minimizes $$$c_{x_1}$$$, $$$c_{x_2}$$$, .. $$$c_{x_k}$$$. Then, for some ordering of the children $$$y_1$$$, $$$y_2$$$ .. $$$y_k$$$ that is a permutation of the set $$$\{1,\ 2\ ..\ k\}$$$ $$$c_{node}\ = w_{node}\ + \ c_{x_{y_1}} + \ {c_{x_{y_2}}}^2 + .. + {c_{x_{y_k}}}^k$$$. Among all such orderings, Johnny picks the one that minimizes $$$c_{node}$$$.

Johnny quickly realized that this cost functions grows very quickly and he wouldn't be able to compute it. He then remembered from his competitive programming course that when the answer to a problem is too big to be computed, he usually computed it modulo some number $$$MOD$$$. This is exactly what Johnny did! He additionally picks a new number $$$MOD$$$ and will do all calculations modulo $$$MOD$$$.

Despite having a good idea, Johnny makes a crucial mistake: instead of calculating the residue of the cost function modulo $$$MOD$$$, he instead calculates the minimum possible residue modulo $$$MOD$$$, for each of the $$$c_i$$$.

Compute a program to find the answer produced by Johnny's algorithm. Given a set of points and a number $$$MOD$$$, you are asked to do the following:

  1. Find a spanning tree with the sum of lengths of edges being the smallest possible. The length of an edge is the euclidean distance between the two points it connects. If there are multiple such trees, you may pick any.
  2. Compute the cost function modulo $$$MOD$$$, having rooted the tree in node $$$1$$$. Note that at each point of computing $$$c_i$$$, you should minimize the residue modulo $$$MOD$$$ instead of the actual cost function itself.
Input

The first line of the input contains two integers: $$$N$$$ $$$(1 \le N \le 5000)$$$ and $$$MOD$$$ $$$(1 \le MOD \le 2*10^9)$$$. The next $$$N$$$ lines each contain three integers: $$$x_i$$$, $$$y_i$$$, $$$w_i$$$ $$$(-10^9 \le x_i, y_i \le 10^9\ and\ 0 \le w_i \le 10^9)$$$, coordinates and weight of point $$$i$$$. It is guaranteed that no two points share the same coordinates.

Output

The first $$$N-1$$$ lines of the output should contain two integers $$$u$$$ and $$$v$$$, representing the edges of the tree you picked. This tree must have the total sum of lengths of its edges the minimum among all possible trees covering the entire set of points. If there are multiple such trees, you may pick any of them. The next line must contain $$$N$$$ integers $$$c_i$$$, where $$$c_i$$$ is the cost function computed for node $$$i$$$ in the tree that you previously picked.

Examples
Input
3 10
0 0 2
-1 -1 3
1 1 2
Output
1 2
1 3
3 3 2
Input
5 19
-2 -2 1
-3 -2 16
5 0 14
1 -4 18
-5 3 17
Output
2 5
1 2
4 3
1 4
1 14 14 13 17

I. Mortgages
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Recently, Max decided to become a house flipper. Because this is a hard business to start, he went to the bank to inquire about their offers.

The bank has $$$N$$$ house offers defined by the following attributes:

  • $$$t_i$$$ - the exact moment in time the offer is available (i.e. it is available only at that time). It is guaranteed that these values are distinct, and that the offers are given in a non-descending order by their availability time $$$t_i$$$.
  • $$$p_i$$$ - the initial price of the house
  • $$$d_i$$$ - the down deposit needed in order to be able to take the offer
  • $$$r_i$$$ - the monthly rate which Max will need to pay to the bank
  • $$$m_i$$$ - the number of months Max will need to pay the rate
  • $$$inc_i$$$ - the monthly increase of the house price

This means that $$$X$$$ months after Max buys a house, the house will be valued at $$$p_i + X*inc_i$$$ dollars and he will have payed the bank $$$d_i + min(X, m_i)*r_i$$$ dollars. Max starts with an infinite amount of money (so he can put any deposit needed), and a final moment $$$T$$$ when he wants to end all business. Also, he is restricted to only be able to own at most one house at a time. This means that he will be able to accept a bank offer only if he does not own any houses at that time (he can also decide to skip some of the offers).

At a moment in time, Max can decide to sell his current house (if he owns one). When a house is sold, Max will need to pay all the remaining monthly rates to the bank, so that all $$$m_i$$$ are payed. This action happens instantaneously.

Help Max find what is the maximum profit he can make using the bank offers. The profit is described as the total money he has made selling the houses subtracted by the total money used to buy the houses.

Input

The first line of input contains $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$T$$$ ($$$1 \leq T \leq 10^9$$$), denoting the number of houses and the end time.

Each of the following $$$N$$$ lines contains $$$6$$$ positive integers describing the houses:

  • $$$t_i$$$ ($$$1 \leq t_i \lt T$$$)
  • $$$p_i$$$ ($$$1 \leq p_i \leq 10^6$$$)
  • $$$d_i$$$ ($$$1 \leq d_i \leq p_i$$$)
  • $$$r_i$$$ ($$$1 \leq r_i \leq 10^6$$$)
  • $$$m_i$$$ ($$$1 \leq m_i \leq 10^6$$$)
  • $$$inc_i$$$ ($$$1 \leq inc_i \leq 10^6$$$)
Output

On a single line, print the maximum profit Max can make in the time given.

Examples
Input
9 50
1 1 1 2 1 4
10 1 1 2 2 5
12 4 1 2 5 2
21 5 4 5 1 2
22 3 2 5 5 2
28 3 2 5 1 1
31 1 1 3 1 2
39 3 3 2 1 2
49 4 1 3 2 3
Output
230
Input
4 55
2 3 2 3 1 1
3 2 2 3 1 5
5 1 1 5 3 3
48 2 1 5 5 5
Output
257
Input
10 33
1 2 1 4 4 3
2 1 1 3 4 5
5 2 1 2 4 1
8 4 4 1 4 1
13 3 2 5 2 3
16 3 3 1 2 1
19 2 2 3 3 4
21 2 2 1 5 4
24 1 1 5 2 5
26 5 3 4 4 5
Output
143

J. Spaceship
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Your mom was cleaning the house and she found your old Nintendo console back from the 90s when you were just a kid. You remember that you used to like the "Spaceship" game so much that you started playing it again.

The game is played on the 2D plane and consists of a spaceship that starts in the point $$$(X_{start}, Y_{start})$$$ and has to get to the point $$$(X_{finish}, Y_{finish})$$$. We consider the spaceship a single point in a plane with area 0. You can move the spaceship in any direction (ex: it can also curve) but only towards the right (i.e., the $$$X$$$ coordinate can never decrease). On the plane there are $$$N$$$ segments sorted from left to right. That is, $$$X_{start} \lt X^1_1 \lt X^2_1 \lt X^1_2 \lt X^2_2 \lt ... \lt X^1_N \lt X^2_N \lt X_{finish}$$$, where $$$(X^1_i, Y^1_i)$$$ and $$$(X^2_i, Y^2_i)$$$ are the ends of the $$$i^{\text{th}}$$$ segment ($$$1 \leq i \leq N$$$). Each segment is of one of the following two types:

  • Wall: The spaceship cannot pass through the interior points of this segment (i.e., it is allowed to pass through the two ends of the segment). However, the spaceship is allowed to move along the segment
  • Magic gate: If the spaceship passes through this segment (including its ends), you earn $$$P_i$$$ magic points. You can earn the $$$P_i$$$ points for this segment only once no matter how many times you pass through it

The final score of the game is the total distance traversed by the spaceship minus the total magic points accumulated. The goal of the game is to minimize the score. Because we are now in the $$$21^{\text{st}}$$$ century, you decide to write a program to compute the minimum score to move the spaceship from $$$(X_{start}, Y_{start})$$$ to $$$(X_{finish}, Y_{finish})$$$.

Input

The first line of the input contains the integer $$$N$$$ ($$$1 \leq N \leq 2000$$$), denoting the number of segments. Each of the following $$$N$$$ lines contains an integer $$$type_i$$$ ($$$0 \leq type_i \leq 1$$$). If $$$type_i = 0$$$, then this segment is a Wall. If $$$type_i = 1$$$, then this segment is a Magic gate and the next integer in the input line is $$$P_i$$$ ($$$0 \leq P_i \leq 10^9$$$), denoting the magic points corresponding to this segment. In both cases, the input line contains $$$4$$$ more integers $$$X^1_i, Y^1_i, X^2_i, Y^2_i$$$ ($$$0 \leq X^1_i, Y^1_i, X^2_i, Y^2_i \leq 10^9$$$), denoting the ends of this segment. The last line of the input contains 4 integers $$$X_{start}, Y_{start}, X_{finish}, Y_{finish}$$$ ($$$0 \leq X_{start}, Y_{start}, X_{finish}, Y_{finish} \leq 10^9$$$), denoting the start point and the finish point.

Among all the $$$2 * (N + 1)$$$ points from the input, there aren't any $$$3$$$ collinear points.

Output

On a single line, print the minimum score to move the spaceship from $$$(X_{start}, Y_{start})$$$ to $$$(X_{finish}, Y_{finish})$$$. Your answer will be considered correct if the absolute or relative difference between your answer and judge's answer is less than $$$10^{-8}$$$.

Example
Input
3
0 2 3 3 5
1 3 4 1 5 2
0 6 1 7 8
1 3 9 6
Output
8.216116701980
Note

The picture bellow corresponds to the example. The red segments are walls and the green segments are magic gates. The optimal path for the spaceship is to move in a straight line from the start point $$$(1, 3)$$$ to point $$$(6, 1)$$$, and from there in a straight line to the finish point $$$(9, 6)$$$. This path does not pass through any wall. Also, it passes through the magic gate from which we earn $$$3$$$ points. The score of the path is $$$\sqrt{29} + \sqrt{34} - 3$$$, and this is the minimum possible score.

K. Teams
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are only a few hours left before the AGM finals and still many problems to complete. Currently there are $$$N$$$ members in the jury numbered from $$$0$$$ to $$$N - 1$$$ and so far neither of them has completed any problem. In order to increase their productivity and to better keep track of the finished problems, the members of the scientific committee have decided to split into several teams.

Over the course of the night there are 2 main events that can happen:

  1. a new team, consisting of members $$$i_1$$$, $$$i_2$$$, ..., $$$i_k$$$, is formed and is responsible for completing at least $$$C$$$ problems.
  2. the member $$$i$$$ creates $$$P$$$ new problems.

After each event of the $$$2^{nd}$$$ type the jury is wondering how many of the already formed teams have finished their job.

Please note that one member of the jury can be part of multiple teams, and all the problems he develops will contribute to all the teams that he belongs to.

Input

The first line of the input contains the integers $$$N$$$ ($$$1 \leq N \leq 200.000$$$) and $$$Q$$$ ($$$1 \leq Q \leq 200.000$$$), denoting the number of members of the jury and the number of events that happen during the night. The next $$$Q$$$ lines have the following structure:

  • $$$type'$$$ $$$C'$$$ $$$k'$$$ $$$i_1'$$$, ..., $$$i_k'$$$
  • $$$type'$$$ $$$i'$$$ $$$P'$$$

In order to retrieve the actual parameters of the operation you have to xor each one of them with $$$last\_answer$$$, where $$$last\_answer$$$ is the most recent result of a query (initially $$$last\_answer$$$ is set to 0). The decoded lines will look as follows:

  • $$$1$$$ $$$C$$$ $$$k$$$ $$$i_1$$$, ..., $$$i_k$$$
  • $$$2$$$ $$$i$$$ $$$P$$$

where $$$0 \leq C, P \leq 1.000.000$$$, $$$1 \leq k \leq 3$$$ and $$$0 \leq i, i_1, .., i_k \leq N - 1$$$ ($$$i_1$$$, ..., $$$i_k$$$ are distinct)

Output

For each operation of the $$$2^{nd}$$$ type print the number of teams that finished their job.

Example
Input
3 6
1 2 2
0 1
2 0 1
2 1 1
0 4 2
1 0 3
3 3 2
0 2 3
Output
0
1
2
2
Note

Decoded version of the sample:

3 6 1 2 2 0 1 2 0 1 2 1 1 1 5 3 0 1 2 2 2 3 2 0 1

L. Windfield
time limit per test
2.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bibita found a windfield shaped like an $$$N \times N$$$ matrix. There are very strong winds in the windfield. Anything in cell $$$(i,j)$$$ ($$$0 \le i, j \lt N$$$) would move after one second to one of the adjacent cells, with a given probability. If the winds are not strong enough, it will stay in the same cell.

Bibita likes odd and even numbers. She throws an object (could be anything) in the windfield, which will fall randomly in one of the cells at second $$$0$$$. She now wonders what is the probability that after $$$K$$$ seconds, the object will be on a cell $$$(i, j)$$$ where $$$j$$$ has the same parity as $$$K$$$. Can you help her find this answer?

Bibita considers that the coordinats in the windfield are 0 indexed (eg. the first cell (0, 0) is on an even column).

Input

The first line of the input contains an integer $$$N$$$ ($$$2 \leq N \leq 500$$$), denoting the size of the windield matrix.

On each of the following $$$N \times N$$$ lines you'll be given at least $$$3$$$ and at most $$$5$$$ integers $$$a_p$$$ ($$$0 \le a_p \lt 998244353$$$), denoting the probabilities for the $$$ith$$$ cell in the matrix (numbered from top left to bottom right).

For a cell having all $$$4$$$ neighbours you will be given $$$5$$$ values $$$a_s$$$, $$$a_t$$$, $$$a_r$$$, $$$a_b$$$, $$$a_l$$$ corresponding in this order to the probability of: staying in the same cell, moving up, moving right, moving down, moving left. If the cell is a corner or an edge, the missing neighbours are omitted (eg. for the top-left corner you'll be given only $$$a_s$$$, $$$a_r$$$, $$$a_b$$$). The probability is a fraction $$$\frac{a}{b}$$$ given as $$$a \times b^{−1}$$$ (modulo $$$998244353$$$), where $$$b^{−1}$$$ is the modular inverse of $$$b$$$ modulo $$$998244353$$$.

The next line contains an integer $$$Q$$$ ($$$1 \le q \le 10^3$$$), denoting the number of testcases.

Each of the following $$$Q$$$ lines contain an integer $$$K$$$ ($$$1 \le K \le 10^9$$$).

It is guaranteed that for $$$N \gt 10$$$, $$$N^2 \times K \le 2 \times 10^6$$$

Output

You should output the result for each of the $$$Q$$$ question, modulo $$$998244353$$$, on a separate line.

Example
Input
2
489139733 389315298 119789323
768648152 109806879 119789323
658841273 559016838 778630596
958314579 708753491 329420637
2
31
19
Output
888372042
963737898