The final match of the Berland Football Cup has been held recently. The referee has shown $$$n$$$ yellow cards throughout the match. At the beginning of the match there were $$$a_1$$$ players in the first team and $$$a_2$$$ players in the second team.
The rules of sending players off the game are a bit different in Berland football. If a player from the first team receives $$$k_1$$$ yellow cards throughout the match, he can no longer participate in the match — he's sent off. And if a player from the second team receives $$$k_2$$$ yellow cards, he's sent off. After a player leaves the match, he can no longer receive any yellow cards. Each of $$$n$$$ yellow cards was shown to exactly one player. Even if all players from one team (or even from both teams) leave the match, the game still continues.
The referee has lost his records on who has received each yellow card. Help him to determine the minimum and the maximum number of players that could have been thrown out of the game.
The first line contains one integer $$$a_1$$$ $$$(1 \le a_1 \le 1\,000)$$$ — the number of players in the first team.
The second line contains one integer $$$a_2$$$ $$$(1 \le a_2 \le 1\,000)$$$ — the number of players in the second team.
The third line contains one integer $$$k_1$$$ $$$(1 \le k_1 \le 1\,000)$$$ — the maximum number of yellow cards a player from the first team can receive (after receiving that many yellow cards, he leaves the game).
The fourth line contains one integer $$$k_2$$$ $$$(1 \le k_2 \le 1\,000)$$$ — the maximum number of yellow cards a player from the second team can receive (after receiving that many yellow cards, he leaves the game).
The fifth line contains one integer $$$n$$$ $$$(1 \le n \le a_1 \cdot k_1 + a_2 \cdot k_2)$$$ — the number of yellow cards that have been shown during the match.
Print two integers — the minimum and the maximum number of players that could have been thrown out of the game.
2 3 5 1 8
0 4
3 1 6 7 25
4 4
6 4 9 10 89
5 9
In the first example it could be possible that no player left the game, so the first number in the output is $$$0$$$. The maximum possible number of players that could have been forced to leave the game is $$$4$$$ — one player from the first team, and three players from the second.
In the second example the maximum possible number of yellow cards has been shown $$$(3 \cdot 6 + 1 \cdot 7 = 25)$$$, so in any case all players were sent off.
You are given a tree with $$$n$$$ vertices. A tree is a connected graph without any cycles. The vertices are indexed from $$$1$$$ to $$$n$$$.
$$$k$$$ vertices are colored (more specifically, the colored vertices have indices $$$a_1, a_2, \dots, a_k$$$). We can choose any uncolored vertex $$$x$$$ and root the tree at it, so we can assume that $$$x$$$ is the root of the tree. Let's analyze all the subtrees of the given tree such that the roots of these subtrees are the children of root vertex $$$x$$$. If each of these subtrees contains at least one colored vertex, then $$$x$$$ is an interesting vertex.
Your task is to find all interesting vertices in the given tree and print their indices in ascending order.
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 2 \cdot 10^{5}, 1 \le k \lt n)$$$ — the total number of vertices in the tree and the number of colored vertices, respectively.
The second line contains a sequence of distinct integers $$$a_1, a_2, \dots, a_k$$$ $$$(1 \le a_i \le n)$$$ — the indices of the colored vertices.
Next $$$n - 1$$$ lines denote the edge of the tree, each line contains two integers $$$u_j$$$ and $$$v_j$$$ $$$(1 \le u_j, v_j \le n, u_j \neq v_j)$$$ representing an edge between these two vertices. It is guaranteed that these edges form a tree.
In the first line print $$$p$$$ — the number of interesting vertices.
In the second line print $$$p$$$ distinct integers — the indices of interesting vertices. Each interesting vertex should be printed exactly once. The indices should be sorted in ascending order.
4 1 3 1 2 2 3 2 4
2 1 4
8 3 6 5 7 1 5 5 4 5 3 1 6 2 7 1 2 1 8
4 2 3 4 8
In the first example there are three uncolored vertices, and only vertex $$$2$$$ is not an interesting vertex, since it is connected to three other vertices, but only one of these vertices contains a colored vertex in its subtree.
Monocarp has arranged $$$n$$$ colored marbles in a row. The color of the $$$i$$$-th marble is $$$a_i$$$. Monocarp likes ordered things, so he wants to rearrange marbles in such a way that all marbles of the same color form a contiguos segment (and there is only one such segment for each color).
In other words, Monocarp wants to rearrange marbles so that, for every color $$$j$$$, if the leftmost marble of color $$$j$$$ is $$$l$$$-th in the row, and the rightmost marble of this color has position $$$r$$$ in the row, then every marble from $$$l$$$ to $$$r$$$ has color $$$j$$$.
To achieve his goal, Monocarp can do the following operation any number of times: choose two neighbouring marbles, and swap them.
You have to calculate the minimum number of operations Monocarp has to perform to rearrange the marbles. Note that the order of segments of marbles having equal color does not matter, it is only required that, for every color, all the marbles of this color form exactly one contiguous segment.
The first line contains one integer $$$n$$$ $$$(2 \le n \le 4 \cdot 10^5)$$$ — the number of marbles.
The second line contains an integer sequence $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le 20)$$$, where $$$a_i$$$ is the color of the $$$i$$$-th marble.
Print the minimum number of operations Monocarp has to perform to achieve his goal.
7 3 4 2 3 4 2 2
3
5 20 1 14 10 2
0
13 5 5 4 4 3 5 7 6 5 4 4 6 5
21
In the first example three operations are enough. Firstly, Monocarp should swap the third and the fourth marbles, so the sequence of colors is $$$[3, 4, 3, 2, 4, 2, 2]$$$. Then Monocarp should swap the second and the third marbles, so the sequence is $$$[3, 3, 4, 2, 4, 2, 2]$$$. And finally, Monocarp should swap the fourth and the fifth marbles, so the sequence is $$$[3, 3, 4, 4, 2, 2, 2]$$$.
In the second example there's no need to perform any operations.
Monocarp and Bicarp live in Berland, where every bus ticket consists of $$$n$$$ digits ($$$n$$$ is an even number). During the evening walk Monocarp and Bicarp found a ticket where some of the digits have been erased. The number of digits that have been erased is even.
Monocarp and Bicarp have decided to play a game with this ticket. Monocarp hates happy tickets, while Bicarp collects them. A ticket is considered happy if the sum of the first $$$\frac{n}{2}$$$ digits of this ticket is equal to the sum of the last $$$\frac{n}{2}$$$ digits.
Monocarp and Bicarp take turns (and Monocarp performs the first of them). During each turn, the current player must replace any erased digit with any digit from $$$0$$$ to $$$9$$$. The game ends when there are no erased digits in the ticket.
If the ticket is happy after all erased digits are replaced with decimal digits, then Bicarp wins. Otherwise, Monocarp wins. You have to determine who will win if both players play optimally.
The first line contains one even integer $$$n$$$ $$$(2 \le n \le 2 \cdot 10^{5})$$$ — the number of digits in the ticket.
The second line contains a string of $$$n$$$ digits and "?" characters — the ticket which Monocarp and Bicarp have found. If the $$$i$$$-th character is "?", then the $$$i$$$-th digit is erased. Note that there may be leading zeroes. The number of "?" characters is even.
If Monocarp wins, print "Monocarp" (without quotes). Otherwise print "Bicarp" (without quotes).
4 0523
Bicarp
2 ??
Bicarp
8 ?054??0?
Bicarp
6 ???00?
Monocarp
Since there is no question mark in the ticket in the first example, the winner is determined before the game even starts, and it is Bicarp.
In the second example, Bicarp also wins. After Monocarp chooses an erased digit and replaces it with a new one, Bicap can choose another position with an erased digit and replace it with the same digit, so the ticket is happy.
The fence consists of $$$n$$$ planks, arranged from left to right. Monocarp has $$$m$$$ different types of paint, and the number of planks that can be painted in color $$$i$$$ is $$$a_i$$$ (there's not enough paint to color any more planks). The total amount of paint is just enough to paint exactly $$$n$$$ planks — in other words, the sum of all $$$a_i$$$ is equal to $$$n$$$. Each plank should be painted into exactly one color.
Monocarp has to paint the fence in such a way that the length of every contiguous segment consisting of planks of the same color is not greater than $$$k$$$.
Find a suitable way to paint the fence, or say that it is impossible.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ $$$(1 \le n \le 2 \cdot 10^{5}, 1 \le m, k \le n)$$$ — the number of planks in the fence, the number of different colors of paint and the maximum length of a contiguous segment of planks with the same color, respectively.
The second line contains a sequence of integers $$$a_1, a_2, \dots, a_m$$$ $$$(1 \le a_i \le n)$$$, where $$$a_i$$$ is the number of planks that can be painted with color $$$i$$$. The sum of all values of $$$a_i$$$ is equal to $$$n$$$.
If it is impossible to paint the fence in such a way that the length of every contiguous segment consisting of planks of the same color is not greater than $$$k$$$, print $$$-1$$$.
Otherwise print $$$n$$$ integers, $$$i$$$-th of them should be equal to the index of the color of the $$$i$$$-th plank. If there are multiple possible answers, print any of them.
5 2 1 2 3
2 1 2 1 2
8 2 3 1 7
-1
10 3 2 5 2 3
1 1 3 1 1 2 3 1 2 3
In the first example the first, third and fifth planks should have color $$$2$$$, and all other planks should have color $$$1$$$.
In the second example it is impossible to paint the fence in the required way, so the answer is $$$-1$$$.
You are given a sequence $$$a_1, a_2, \dots, a_n$$$ consisting of $$$n$$$ integers.
You have to calculate three following values:
- the number of pairs of indices $$$(l, r)$$$ $$$(l \le r)$$$ such that $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ is negative;
- the number of pairs of indices $$$(l, r)$$$ $$$(l \le r)$$$ such that $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ is zero;
- the number of pairs of indices $$$(l, r)$$$ $$$(l \le r)$$$ such that $$$a_l \cdot a_{l + 1} \dots a_{r - 1} \cdot a_r$$$ is positive;
The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the number of elements in the sequence.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(-10^{9} \le a_i \le 10^{9})$$$ — the elements of the sequence.
Print three integers — the number of subsegments with negative product, the number of subsegments with product equal to zero and the number of subsegments with positive product, respectively.
5 5 -3 3 -1 0
6 5 4
10 4 0 -4 3 1 2 -4 3 0 3
12 32 11
5 -1 -2 -3 -4 -5
9 0 6
In the first example there are six subsegments having negative products: $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$, five subsegments having products equal to zero: $$$(1, 5)$$$, $$$(2, 5)$$$, $$$(3, 5)$$$, $$$(4, 5)$$$, $$$(5, 5)$$$, and four subsegments having positive products: $$$(1, 1)$$$, $$$(1, 4)$$$, $$$(2, 4)$$$, $$$(3, 3)$$$.
Monocarp has got two strings $$$s$$$ and $$$t$$$ having equal length. Both strings consist of lowercase Latin letters "a" and "b".
Monocarp wants to make these two strings $$$s$$$ and $$$t$$$ equal to each other. He can do the following operation any number of times: choose an index $$$pos_1$$$ in the string $$$s$$$, choose an index $$$pos_2$$$ in the string $$$t$$$, and swap $$$s_{pos_1}$$$ with $$$t_{pos_2}$$$.
You have to determine the minimum number of operations Monocarp has to perform to make $$$s$$$ and $$$t$$$ equal, and print any optimal sequence of operations — or say that it is impossible to make these strings equal.
The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the length of $$$s$$$ and $$$t$$$.
The second line contains one string $$$s$$$ consisting of $$$n$$$ characters "a" and "b".
The third line contains one string $$$t$$$ consisting of $$$n$$$ characters "a" and "b".
If it is impossible to make these strings equal, print $$$-1$$$.
Otherwise, in the first line print $$$k$$$ — the minimum number of operations required to make the strings equal. In each of the next $$$k$$$ lines print two integers — the index in the string $$$s$$$ and the index in the string $$$t$$$ that should be used in the corresponding swap operation.
4 abab aabb
2 3 3 3 2
1 a b
-1
8 babbaabb abababaa
3 2 6 1 3 7 8
In the first example two operations are enough. For example, you can swap the third letter in $$$s$$$ with the third letter in $$$t$$$. Then $$$s = $$$ "abbb", $$$t = $$$ "aaab". Then swap the third letter in $$$s$$$ and the second letter in $$$t$$$. Then both $$$s$$$ and $$$t$$$ are equal to "abab".
In the second example it's impossible to make two strings equal.
Bertown mayor had been receiving different complaints about insufficient lighting of the Berland Prospect — the main street of the city — for quite a while, and recently $$$n$$$ lanterns have been installed on the Prospect.
The Prospect can be represented as a segment of the coordinate line with endpoints in $$$0$$$ and $$$10^{18}$$$. Lanterns are installed in integer points of this segment; $$$i$$$-th lantern is installed in point $$$x_i$$$.
A large student festival will be held soon in Bertown, the students from all Berland are going to attend it. The mayor wants to impress them with the look of the Prospect during the night. To do so, the lighting system will be changed for only one night: some lanterns will be turned on, and all other lanterns will be turned off, so that the Prospect looks beautiful.
The mayor thinks that the Prospect will look beautiful if the following condition is met. Let's denote the indices of the lanterns that are turned on as $$$i_1$$$, $$$i_2$$$, ..., $$$i_k$$$ (in increasing order of coordinates), then the condition $$$x_{i_2} - x_{i_1} = x_{i_3} - x_{i_2} = \dots = x_{i_k} - x_{i_{k - 1}}$$$ should hold (that is, the distance between every two neighbouring working lanterns is the same). If the number of lanterns that are turned on is less than $$$3$$$, then the Prospect will look beautiful no matter where these lanterns are situated.
Of course, the better the lighting, the safer the Prospect will be. So the mayor wants to choose a set of lanterns to turn on of maximum possible size (among all sets such that the Prospect looks beautiful if all lanterns from the set are turned on). Help him to choose this set of lanterns!
The first line contains one integer $$$n$$$ ($$$3 \le n \le 3\,000$$$) — the number of lanterns.
The second line contains $$$n$$$ integers $$$x_1$$$, $$$x_2$$$, ..., $$$x_n$$$ ($$$0 \le x_1 \lt x_2 \lt \dots \lt x_n \le 10^{18}$$$) — the coordinates of the lanterns.
Print one integer — the maximum number of lanterns that can be turned on so that the Prospect looks beautiful.
3 1 2 3
3
5 1 2 4 6 7
3
10 5 10 15 20 35 60 80 85 110 120
5
In the first example it is possible to turn all the lanterns on.
In the second example it is possible to turn the lanterns having coordinates $$$1$$$, $$$4$$$, $$$7$$$ on.
In the second example it is possible to turn the lanterns having coordinates $$$10$$$, $$$35$$$, $$$60$$$, $$$85$$$, $$$110$$$ on.
In addition to complaints about lighting, a lot of complaints about insufficient radio signal covering has been received by Bertown city hall recently. $$$n$$$ complaints were sent to the mayor, all of which are suspiciosly similar to each other: in the $$$i$$$-th complaint, one of the radio fans has mentioned that the signals of two radio stations $$$x_i$$$ and $$$y_i$$$ are not covering some parts of the city, and demanded that the signal of at least one of these stations can be received in the whole city.
Of cousre, the mayor of Bertown is currently working to satisfy these complaints. A new radio tower has been installed in Bertown, it can transmit a signal with any integer power from $$$1$$$ to $$$M$$$ (let's denote the signal power as $$$f$$$). The mayor has decided that he will choose a set of radio stations and establish a contract with every chosen station. To establish a contract with the $$$i$$$-th station, the following conditions should be met:
- the signal power $$$f$$$ should be not less than $$$l_i$$$, otherwise the signal of the $$$i$$$-th station won't cover the whole city;
- the signal power $$$f$$$ should be not greater than $$$r_i$$$, otherwise the signal will be received by the residents of other towns which haven't established a contract with the $$$i$$$-th station.
All this information was already enough for the mayor to realise that choosing the stations is hard. But after consulting with specialists, he learned that some stations the signals of some stations may interfere with each other: there are $$$m$$$ pairs of stations ($$$u_i$$$, $$$v_i$$$) that use the same signal frequencies, and for each such pair it is impossible to establish contracts with both stations. If stations $$$x$$$ and $$$y$$$ use the same frequencies, and $$$y$$$ and $$$z$$$ use the same frequencies, it does not imply that $$$x$$$ and $$$z$$$ use the same frequencies.
The mayor finds it really hard to analyze this situation, so he hired you to help him. You have to choose signal power $$$f$$$ and a set of stations to establish contracts with such that:
- all complaints are satisfied (formally, for every $$$i \in [1, n]$$$ the city establishes a contract either with station $$$x_i$$$, or with station $$$y_i$$$);
- no two chosen stations interfere with each other (formally, for every $$$i \in [1, m]$$$ the city does not establish a contract either with station $$$u_i$$$, or with station $$$v_i$$$);
- for each chosen station, the conditions on signal power are met (formally, for each chosen station $$$i$$$ the condition $$$l_i \le f \le r_i$$$ is met).
The first line contains $$$4$$$ integers $$$n$$$, $$$p$$$, $$$M$$$ and $$$m$$$ ($$$2 \le n, p, M, m \le 4 \cdot 10^5$$$) — the number of complaints, the number of radio stations, maximum signal power and the number of interfering pairs, respectively.
Then $$$n$$$ lines follow, which describe the complains. Each line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \lt y_i \le p$$$) — the indices of the radio stations mentioned in the $$$i$$$-th complaint). All complaints are distinct.
Then $$$p$$$ lines follow, which describe the radio stations. Each line contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le M$$$) — the constrains on signal power that should be satisfied if the city establishes a contract with the $$$i$$$-th station.
Then $$$m$$$ lines follow, which describe the pairs of interfering radio stations. Each line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i \lt v_i \le p$$$) — the indices of interfering radio stations. All these pairs are distinct.
If it is impossible to choose signal power and a set of stations to meet all conditions, print $$$-1$$$.
Otherwise print two integers $$$k$$$ and $$$f$$$ in the first line — the number of stations in the chosen set and the chosen signal power, respectively. In the second line print $$$k$$$ distinct integers from $$$1$$$ to $$$p$$$ — the indices of stations to establish contracts with (in any order). If there are multiple answers, print any of them; you don't have to minimize/maximize the number of chosen stations, and the same applies to signal power.
2 4 4 2 1 3 2 3 1 4 1 2 3 4 1 4 1 2 3 4
2 3 1 3
2 4 4 2 1 3 2 4 1 2 1 2 3 4 3 4 1 2 3 4
-1
Monocarp is going to participate in $$$n$$$ different programming contests, and he plans to win a T-shirt in every contest. Of course, he doesn't need $$$n$$$ T-shirts — he wants to give all of them to his friends. Monocarp has a list of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ — the sizes of T-shirts that his friends want to receive. All values of $$$a_i$$$ are distinct.
To receive all $$$n$$$ T-shirts for all $$$n$$$ friends, Monocarp chooses different sizes of T-shirts while registering on different competitions — when registering on contest $$$i$$$, he specifies that he would like to receive a T-shirt of size $$$a_i$$$.
Monocarp is absolutely sure that his programming skills are enough to win a T-shirt in each contest. Unfortunately, it is possible that he will receive a T-shirt of wrong size: if he specifies that he wants a T-shirt of size $$$x$$$, then with probability $$$p$$$ he receives a T-shirt having size $$$x - 1$$$, with probability $$$q$$$ he receives a T-shirt having size $$$x + 1$$$, and with probability $$$1 - p - q$$$ he receives a T-shirt having size $$$x$$$.
After receiving all the T-shirts Monocarp starts handing them out: for each $$$a_i$$$, if he has received at least one T-shirt of size $$$a_i$$$, he gives exactly one T-shirt of this size to the friend that asked for a T-shirt of this size. Now Monocarp is interested how many friends (on average) will receive T-shirts. Help him to calculate the expected number of T-shirts he will hand out.
The first line contains three integers $$$n$$$, $$$P$$$ and $$$Q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le P \le 10^6$$$, $$$0 \le Q \le 10^6$$$, $$$P + Q \le 10^6$$$) — the number of contests and the numbers denoting the probability to receive a T-shirt of wrong size. $$$p$$$ and $$$q$$$ from the statement can be calculated the following way: $$$p = \frac{P}{10^6}$$$, $$$q = \frac{Q}{10^6}$$$.
The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the sizes of T-shirts Monocarp's friends want. All values of $$$a_i$$$ are distinct.
The expected number of T-shirts that Monocarp will hand out can be represented as an irreducible fraction $$$\frac{X}{Y}$$$, where $$$Y$$$ is not divisible by $$$998244353$$$. Print $$$(X \cdot Y^{-1})$$$ $$$mod$$$ $$$998244353$$$, where $$$Y^{-1}$$$ is the inverse of $$$Y$$$ modulo $$$998244353$$$ (a number such that $$$Y \cdot Y^{-1}$$$ is congruent to $$$1$$$ modulo $$$998244353$$$).
4 250000 250000 3 1 5 2
530317315
3 125000 750000 3 2 1
175472642
Explanations for the examples:
In the first example $$$p = \frac{1}{4}$$$, $$$q = \frac{1}{4}$$$, the answer is $$$\frac{79}{32}$$$.
In the second example $$$p = \frac{1}{8}$$$, $$$q = \frac{3}{4}$$$, the answer is $$$\frac{467}{256}$$$.
Monocarp plays a computer game called Moonbound. The main goal of this game is to save the galaxy from the invasion of alien forces using the Matter Manipulator — a very powerful artifact. Though Monocarp is not busy saving the galaxy — in fact, now he is simply building a house for his character.
Now Monocarp has to build a wall for the house. The whole world of Moonbound consists of square blocks, and the wall which Monocarp wants to build is not an exception. The wall will have the form of a square, it will consist of $$$n$$$ horizontal rows, each containing $$$n$$$ blocks ($$$n$$$ is even). Let's denote the position where the $$$j$$$-th block in the $$$i$$$-th row will be placed as ($$$i$$$, $$$j$$$).
Monocarp wants to build a wall of two types of blocks: stone bricks and sand bricks. Monocarp thinks that the wall will be beautiful if the blocks of different types are placed in chequered fashion: the left upper block should be a stone brick, the block to the right of it should be a sand brick, the block to the right of that block should be stone, and so on; the first block in the second row should be sand, the second block in the second row — stone, and so on. Formally, if $$$i + j$$$ is divisible by $$$2$$$, then the position ($$$i$$$, $$$j$$$) should contain a stone block, otherwise it should contain a sand block.
The Matter Manipulator can place blocks in two different modes, but both modes have special requirements for the positions where the blocks will be placed. Let's call an empty (not containing any block) position ($$$i$$$, $$$j$$$) free, if either it is on the border ($$$i = 1$$$, $$$i = n$$$, $$$j = 1$$$ or $$$j = n$$$), or it shares a side with at least one position that already contains a block.
The blocks can be placed in two modes — either choose any free position and place there a block of chosen type, or choose a square $$$2 \times 2$$$ which contains at least one free position, and fill all empty positions in this square with blocks of the same chosen type.
Monocarp wants to build the wall using the Matter Manipulator no more than $$$\frac{3n^2}{4}$$$ times. If he places a block in a position where a block of other type should be, then he will have to destroy a section of the wall, and it will take a lot of time — so Monocarp won't perform any action which places a block of wrong type in any position. Help him to come up with a plan of actions!
The only line contains one even integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of rows in the wall (and the number of blocks in each row).
In the first line print $$$k$$$ ($$$1 \le k \le \frac{3n^2}{4}$$$) — the number of uses of the Matter Manipulator required to build the wall. Then print the plan of actions in next $$$k$$$ lines, one action per line. Each action should be described with four integers $$$t$$$ $$$x$$$ $$$y$$$ $$$b$$$:
- $$$t$$$ is the type of the action; it is $$$1$$$ if only one position is filled, or $$$2$$$ if a square $$$2 \times 2$$$ is filled;
- $$$x$$$ $$$y$$$ are the coordinates of the position Monocarp fills. If the action has type $$$1$$$, then ($$$x$$$, $$$y$$$) is filled — and it should be free before the action; if the action has type $$$2$$$, then positions ($$$x$$$, $$$y$$$), ($$$x$$$, $$$y + 1$$$), ($$$x + 1$$$, $$$y$$$) and ($$$x + 1$$$, $$$y + 1$$$) are filled — at at least one of them should be free;
- $$$b$$$ is the type of the block that all empty positions are filled with ($$$1$$$ if it is a stone brick, or $$$2$$$ if it is a sand brick).
No action should lead to the situation where some position contains a block that doesn't belong there. When a square $$$2 \times 2$$$ is being filled, no position belonging to it should be outside the wall (so if $$$t = 2$$$, then $$$1 \le x, y \le n - 1$$$).
If there are multiple possible plans with $$$k \le \frac{3n^2}{4}$$$, print any of them. Note that the blocks of different types should be placed in chequered fashion, and the position ($$$1$$$, $$$1$$$) should contain a stone block.
2
3 1 1 1 1 1 2 2 1 2 1 1 2
The sequence of actions in the first example (white color corresponds to an empty position, dark grey — to stone block, light gray — to sand block):
A programming bootcamp will be held in Berland. The participants will play contests in a two-storey building. $$$n$$$ tables will be arranged in a row on each floor of the building. The tables on each floor are numbered from left to right, starting from one. There is a staircase which allows participants to get from one floor to another. The structure of the building is drawn in the following picture:
For each table it is known whether a team will work on this table during the contests.
The organizers have decided to install a printer, so that participants may print their solutions. To do so, they have to choose a floor where the printer will be placed, and a table on this floor. The printer should be installed on any table (it can be a free table, or a table which some team will use for participation).
Let's denote the inconvenience value for each team. For example, a team $$$i$$$ will sit on the floor $$$f_i$$$ at the table $$$a_i$$$, and the printer is installed on the floor $$$f_p$$$ at the table $$$a_p$$$. If the printer is installed on the same floor where team $$$i$$$ participates (that means, $$$f_i = f_p$$$), then the inconvenience for team $$$i$$$ is $$$|a_i - a_p|$$$. And if the printer is installed on another floor (that means, $$$f_i \neq f_p$$$), then the inconvenience for team $$$i$$$ is $$$a_i + k + a_p$$$: the team should first go to the exit from the room where they participate ($$$a_i$$$ corresponds to it), then reach the other floor using the staircase ($$$k$$$ corresponds to it), and walk to the table where the printer is installed ($$$a_p$$$ corresponds to it).
The organizers want to place the printer in such a way that the maximum inconvenience among all teams is minimized. Your task is to help them: tell them the floor and the table where the printer should be placed.
The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le n \le 1\,000, 1 \le k \le 1\,000$$$) — the number of tables on each floor and the time it takes to reach the other floor using the staircase, respectively.
The second line contains a string consisting of $$$n$$$ characters, each character is either a zero or a one. This string corresponds to the teams sitting at the tables on the second floor. If the $$$i$$$-th character is a one, then a team will sit at the $$$i$$$-th table on the second floor. Otherwise the $$$i$$$-th table will be free.
The third line contains a string consisting of $$$n$$$ characters, each character is either a zero or a one. This string corresponds to the teams sitting at the tables on the first floor. If the $$$i$$$-th character is a one, then a team will sit at the $$$i$$$-th table on the first floor. Otherwise the $$$i$$$-th table will be free.
It is guaranteed that at least one team will participate in the bootcamp (that means, at least one character in these two strings is a one).
The first line should contain one integer — the minimum possible maximum inconvenience among all teams.
The second line should contain two integers — the index of the floor and the index of the table where the printer should be placed. If there are multiple optimal answers, print any of them.
3 2 001 001
6 1 1
10 2 0001011011 1000000000
7 2 3
In the first example it is possible to place the printer on the first floor on table $$$1$$$. Then the inconvenience for the team from the second floor is $$$3 + 2 + 1 = 6$$$, and the inconvenience for the team from the first floor is $$$|1 - 3| = 2$$$. So the minimum possible maximum inconvenience is $$$6$$$.