You are preparing a poster to attract up-and-coming coders for your programming competition. Naturally, you wish to make it as flashy as possible. The poster contains a text consisting of only English alphabet letters, digits, punctuation marks and spaces.

You are preparing the poster by hand and you wish to write the text using your three color pen. The pen can write in blue, yellow and red ink. However, there is only enough ink left in the pen that you can write at most $$$b$$$ symbols in blue, $$$y$$$ symbols in yellow and $$$r$$$ symbols in red.

You've decided that the three types of symbols (letters, digits and punctuation marks) should each be colored in its own color. Determine whether it is possible to achieve this using the given pen!

This is a chess problem. A single black king is located at some position on an otherwise empty chess board. You need to choose and place the minimum number of pieces from the standard set of $$$8$$$ white main pieces (a king, a queen, two rooks, two bishops and two knights) so that the game becomes a checkmate for black. See the note below for an explanation of the relevant chess rules.

For example, if the black king is in the $$$5$$$th square of the top row, then we can place a knight in the $$$7$$$th square of the $$$6$$$th row from the bottom and the queen in the $$$5$$$th square of the $$$7$$$th row from the bottom to achieve a checkmate for black. This is also the minimum possible number of pieces. In this problem it is not necessary to use the white king. However, if the white king is placed on the board, it must not be checked by the black king.

Chess notation. To describe the positions of the chess pieces on the board, we use the so-called algebraic chess notation. The positions of the cells of the $$$8 \times 8$$$ square chess board are described by the coordinate system where the columns are labeled with letters from a to h from left to right and the rows are numbered with integers from 1 to 8 from bottom to top. Each main piece type is denoted by a single capital letter: K for king, Q for queen, R for rook, B for bishop and N for knight. A piece on the board then is described by a string of three characters: the piece letter followed by the column and row coordinates of the location cell. For example, a rook in the $$$3$$$rd square of the $$$5$$$th row from the bottom is denoted by Rc5.

You are given an $$$n \times m$$$ ($$$n, m \leq 400$$$) cell grid where each cell contains either a $$$0$$$ or a $$$1$$$. You wish to make all cells contain $$$0$$$. Initially you are located in the upper left cell of the grid and in one move you can move into an adjacent cell (one sharing a side with your current cell). When you move into a new cell, its value flips to the opposite ($$$0$$$ to $$$1$$$ and vice versa).

Find a journey of at most $$$4\cdot 10^5$$$ moves after which all grid cells contain a $$$0$$$. You can finish in any cell and you can visit each cell any number of times.

There are $$$n$$$ train stations numbered from $$$1$$$ to $$$n$$$. For each station there are two one-way outgoing railroad connections. From the $$$i$$$-th station each outgoing railroad connection can go to one of these destinations:

• the $$$1$$$-st station;
• the $$$(i + 1)$$$-th station, if $$$i \lt n$$$.

You are responsible for evaluating the route of an automated train on these railroads. During one run the automated train keeps count of how many times it has visited each station. If the train has visited the current station an odd number of times, it will use the first outgoing railroad connection, otherwise it will use the second outgoing railroad connection.

You have been given a list of $$$q$$$ possible runs of the train, for each run you have been given the start station and how many times the train goes to the next station. The train considers the start station visited for its routing. For each run you need to find the station number where the train will stop.

You are a fashion designer and you are excited about your fresh idea for a T-shirt. A T-shirt of size $$$n$$$ for your purposes is an $$$n \times n$$$ grid of unit squares. Your idea is to make such a T-shirt by sewing together T-patches. A T-patch consists of $$$3$$$ near-unit length segments connecting in a single point as shown:

Your design idea requires placing T-patches so that each side of each square of the T-shirt is covered by exactly one T-patch. Each T-patch can be rotated in any of the four orthogonal directions. For example, a T-shirt of size $$$2$$$ can be sewn as follows:

Given the size of the T-shirt $$$n$$$, find a correct way to sew it from T-patches or determine that it is impossible!

You are planning lighting in a warehouse room, which in the cross section consists of the ceiling (line $$$y=2$$$) and the floor (line $$$y=0$$$). The room is infinite and extends to left and right indefinitely. To illuminate the room, some lamps must be installed in the ceiling, where each lamp shines in all possible downwards directions.

The ceiling is ugly (you can see all of the pipes and wires), hence an aesthetic drop ceiling will be installed (at the line $$$y=1$$$). To let the lamps shine through, $$$n$$$ pinpoint holes (pinholes) were made at distinct positions. For each pinhole, each lamp will shine through in a single straight line. The result is that there are some points on the floor which light shines on.

For the desired lighting, it is necessary to illuminate $$$m$$$ distinct points on the floor (such points may be illuminated by one or multiple lamps). No other points on the floor should be illuminated. Your task is, given the list of the coordinates of $$$n$$$ pinholes and $$$m$$$ points on the floor required to be illuminated, determine whether it is possible to install some lamps in the ceiling so that the required points (and only such points) are illuminated.

Let us call a subset $$$S$$$ of $$$\{1,2,\ldots,n\}$$$ respectable with respect to $$$n$$$ if:

• there is a way to assign $$$+$$$ and $$$-$$$ signs to each element of $$$S$$$ so that the their total sum is divisible by $$$n$$$;
• no non-empty proper subset of $$$S$$$ is respectable with respect to $$$n$$$.

You are given $$$n$$$ and a subset $$$A$$$ of $$$\{1,2,\ldots,n\}$$$. Your task is to find the total number of subsets of $$$A$$$ that are respectable with respect to $$$n$$$.

For example, if $$$n = 7$$$ and $$$A = \{1,2,3,5,6\}$$$, the subset $$$\{2,3,5\}$$$ is respectable, as $$$+2+3-5 = 0$$$ is divisible by $$$7$$$. The subset $$$\{1,6\}$$$ is also respectable, as $$$+1+6=7$$$ is also divisible by $$$7$$$. On the other hand, the subset $$$\{1,2,3,6\}$$$ is not respectable, as even though $$$+1+2+3-6 = 0$$$ is divisible by $$$7$$$, it contains the proper respectable subset $$$\{1,6\}$$$.

You are given $$$n$$$ distinct lines in the plane. Each of them is either horizontal ($$$y=c$$$), vertical ($$$x=c$$$) or diagonal ($$$x+y=c$$$). You need to find the number of non-degenerate triangles such that each of their sides lies on some of the given lines. For example, there are $$$4$$$ such triangles in the following configuration:

You are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered with integers from $$$1$$$ to $$$n$$$. Each vertex $$$v$$$ is labeled with a positive integer $$$a_v$$$.

A path is a sequence of $$$\ell \geq 2$$$ distinct vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_{\ell}$$$ such that for each $$$i$$$ from $$$1$$$ to $$$\ell-1$$$ there is an edge from $$$v_i$$$ to $$$v_{i+1}$$$. The loginess of an edge from vertex $$$u$$$ to vertex $$$v$$$ is defined as $$$\log_{a_u}(a_v)$$$. The loginess of such a path is equal to the product of the loginess of the edges.

Your task is to find the maximum loginess over all possible paths in the graph!

You've recently moved to an arcology – a single megastructure city, which consists of an $$$n \times m$$$ rectangular grid of towers. The tower in the $$$i$$$-th row and the $$$j$$$-th column has height $$$h_{ij}$$$ and consists of $$$h_{ij}$$$ size $$$1 \times 1 \times 1$$$ blocks, one block at each level. But getting around in your new city has proven surprisingly challenging.

You can move in two ways:

• you can move a single block up or down in the tower you're currently in, this move costs you $$$1$$$ stress as you're afraid of elevators;
• you can walk to any block at the same level as your current one in any tower adjacent to your current one, this doesn't cause you any stress.

To plan your commute, you want to answer queries of the following form. For each query, suppose you start at the top block of the tower at the position $$$(i_a,j_a)$$$ and you need to get to the top block of the tower at $$$(i_b,j_b)$$$. Calculate the smallest possible stress of a such a journey.

In this problem you need to solve the quadroku puzzle. In quadroku, you are given a $$$4 \times 4$$$ square grid with digits between $$$1$$$ to $$$4$$$ written in some of the squares. To solve it, you need to write digits in the empty squares so that the following conditions hold:

• each row contains all the digits from $$$1$$$ to $$$4$$$;
• each column contains all the digits from $$$1$$$ to $$$4$$$;
• each $$$2 \times 2$$$ block with two sides on the sides of the grid contains all the digits from $$$1$$$ to $$$4$$$.

In this problem, you are initially given all digits in the upper left and lower right blocks such that each of those blocks contain all the digits from $$$1$$$ to $$$4$$$. Find the solution to the given quadroku or determine that it is impossible!

In this problem you need to reconstruct a convex polygon with $$$n$$$ vertices on the plane given a description of all triangles with vertices coinciding with the vertices of the polygon. The triangles can be given in a translated form, but not rotated.

For example, the following $$$4$$$ triangles can be reconstructed into the following rectangle:

The plane is partitioned into regular hexagons. A grasshopper is sitting in one of the hexagons (the origin). The grasshopper begins to jump around; at time $$$i$$$, it makes a jump covering $$$i$$$ hexagons positioned in a straight line. That is, at time $$$1$$$ it jumps $$$1$$$ cell, at time $$$2$$$ it jumps $$$2$$$ cells, at time $$$3$$$ it jumps $$$3$$$ cells and so on.

Let the distance between two hexagons be the length of the shortest path between them that consists of hexagons and where each two adjacent hexagons are connected by an edge. There are two restrictions on the jumps of the grasshopper:

• the grasshopper always jumps so that the distance from the origin after the jump is larger that before;
• the grasshopper never jumps to a cell it could also have reached with fewer jumps.

Your task, given the coordinates of a goal hexagon, is to determine whether the grasshopper can ever reach it by performing the jumping described above. The coordinate system is defined so that the first coordinate defines the column, and the second defines the north-west to south-east diagonal as in the figure.

For example, the picture shows the cells reachable in at most $$$2$$$ jumps. The red cell is the origin, the green cells are reachable with the first jump, the blue cells are reachable with the second jump, the gray cells are unreachable.