meetforever/GRPO_CL huggingface dataset:
user: Three companies decided to order a billboard with pictures of their logos. A billboard is a big square board. A logo of each company is a rectangle of a non-zero area. 

Advertisers will put up the ad only if it is possible to place all three logos on the billboard so that they do not overlap and the billboard has no empty space left. When you put a logo on the billboard, you should rotate it so that the sides were parallel to the sides of the billboard.

Your task is to determine if it is possible to put the logos of all the three companies on some square billboard without breaking any of the described rules.


-----Input-----

The first line of the input contains six positive integers x_1, y_1, x_2, y_2, x_3, y_3 (1 ≤ x_1, y_1, x_2, y_2, x_3, y_3 ≤ 100), where x_{i} and y_{i} determine the length and width of the logo of the i-th company respectively.


-----Output-----

If it is impossible to place all the three logos on a square shield, print a single integer "-1" (without the quotes).

If it is possible, print in the first line the length of a side of square n, where you can place all the three logos. Each of the next n lines should contain n uppercase English letters "A", "B" or "C". The sets of the same letters should form solid rectangles, provided that:  the sizes of the rectangle composed from letters "A" should be equal to the sizes of the logo of the first company,  the sizes of the rectangle composed from letters "B" should be equal to the sizes of the logo of the second company,  the sizes of the rectangle composed from letters "C" should be equal to the sizes of the logo of the third company, 

Note that the logos of the companies can be rotated for printing on the billboard. The billboard mustn't have any empty space. If a square billboard can be filled with the logos in multiple ways, you are allowed to print any of them.

See the samples to better understand the statement.


-----Examples-----
Input
5 1 2 5 5 2

Output
5
AAAAA
BBBBB
BBBBB
CCCCC
CCCCC

Input
4 4 2 6 4 2

Output
6
BBBBBB
BBBBBB
AAAACC
AAAACC
AAAACC
AAAACC
user: There are n cows playing poker at a table. For the current betting phase, each player's status is either "ALLIN", "IN", or "FOLDED", and does not change throughout the phase. To increase the suspense, a player whose current status is not "FOLDED" may show his/her hand to the table. However, so as not to affect any betting decisions, he/she may only do so if all other players have a status of either "ALLIN" or "FOLDED". The player's own status may be either "ALLIN" or "IN".

Find the number of cows that can currently show their hands without affecting any betting decisions.


-----Input-----

The first line contains a single integer, n (2 ≤ n ≤ 2·10^5). The second line contains n characters, each either "A", "I", or "F". The i-th character is "A" if the i-th player's status is "ALLIN", "I" if the i-th player's status is "IN", or "F" if the i-th player's status is "FOLDED".


-----Output-----

The first line should contain a single integer denoting the number of players that can currently show their hands.


-----Examples-----
Input
6
AFFAAA

Output
4

Input
3
AFI

Output
1



-----Note-----

In the first sample, cows 1, 4, 5, and 6 can show their hands. In the second sample, only cow 3 can show her hand.
user: It seems like the year of 2013 came only yesterday. Do you know a curious fact? The year of 2013 is the first year after the old 1987 with only distinct digits.

Now you are suggested to solve the following problem: given a year number, find the minimum year number which is strictly larger than the given one and has only distinct digits.


-----Input-----

The single line contains integer y (1000 ≤ y ≤ 9000) — the year number.


-----Output-----

Print a single integer — the minimum year number that is strictly larger than y and all it's digits are distinct. It is guaranteed that the answer exists.


-----Examples-----
Input
1987

Output
2013

Input
2013

Output
2014
user: Emuskald is addicted to Codeforces, and keeps refreshing the main page not to miss any changes in the "recent actions" list. He likes to read thread conversations where each thread consists of multiple messages.

Recent actions shows a list of n different threads ordered by the time of the latest message in the thread. When a new message is posted in a thread that thread jumps on the top of the list. No two messages of different threads are ever posted at the same time.

Emuskald has just finished reading all his opened threads and refreshes the main page for some more messages to feed his addiction. He notices that no new threads have appeared in the list and at the i-th place in the list there is a thread that was at the a_{i}-th place before the refresh. He doesn't want to waste any time reading old messages so he wants to open only threads with new messages.

Help Emuskald find out the number of threads that surely have new messages. A thread x surely has a new message if there is no such sequence of thread updates (posting messages) that both conditions hold:   thread x is not updated (it has no new messages);  the list order 1, 2, ..., n changes to a_1, a_2, ..., a_{n}. 


-----Input-----

The first line of input contains an integer n, the number of threads (1 ≤ n ≤ 10^5). The next line contains a list of n space-separated integers a_1, a_2, ..., a_{n} where a_{i} (1 ≤ a_{i} ≤ n) is the old position of the i-th thread in the new list. It is guaranteed that all of the a_{i} are distinct.


-----Output-----

Output a single integer — the number of threads that surely contain a new message.


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

Output
2

Input
3
1 2 3

Output
0

Input
4
4 3 2 1

Output
3



-----Note-----

In the first test case, threads 2 and 5 are placed before the thread 1, so these threads must contain new messages. Threads 1, 3 and 4 may contain no new messages, if only threads 2 and 5 have new messages.

In the second test case, there may be no new messages at all, since the thread order hasn't changed.

In the third test case, only thread 1 can contain no new messages.
user: A way to make a new task is to make it nondeterministic or probabilistic. For example, the hard task of Topcoder SRM 595, Constellation, is the probabilistic version of a convex hull.

Let's try to make a new task. Firstly we will use the following task. There are n people, sort them by their name. It is just an ordinary sorting problem, but we can make it more interesting by adding nondeterministic element. There are n people, each person will use either his/her first name or last name as a handle. Can the lexicographical order of the handles be exactly equal to the given permutation p?

More formally, if we denote the handle of the i-th person as h_{i}, then the following condition must hold: $\forall i, j(i < j) : h_{p_{i}} < h_{p_{j}}$.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of people.

The next n lines each contains two strings. The i-th line contains strings f_{i} and s_{i} (1 ≤ |f_{i}|, |s_{i}| ≤ 50) — the first name and last name of the i-th person. Each string consists only of lowercase English letters. All of the given 2n strings will be distinct.

The next line contains n distinct integers: p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n).


-----Output-----

If it is possible, output "YES", otherwise output "NO".


-----Examples-----
Input
3
gennady korotkevich
petr mitrichev
gaoyuan chen
1 2 3

Output
NO

Input
3
gennady korotkevich
petr mitrichev
gaoyuan chen
3 1 2

Output
YES

Input
2
galileo galilei
nicolaus copernicus
2 1

Output
YES

Input
10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
1 2 3 4 5 6 7 8 9 10

Output
NO

Input
10
rean schwarzer
fei claussell
alisa reinford
eliot craig
laura arseid
jusis albarea
machias regnitz
sara valestin
emma millstein
gaius worzel
2 4 9 6 5 7 1 3 8 10

Output
YES



-----Note-----

In example 1 and 2, we have 3 people: tourist, Petr and me (cgy4ever). You can see that whatever handle is chosen, I must be the first, then tourist and Petr must be the last.

In example 3, if Copernicus uses "copernicus" as his handle, everything will be alright.
user: A boy named Ayrat lives on planet AMI-1511. Each inhabitant of this planet has a talent. Specifically, Ayrat loves running, moreover, just running is not enough for him. He is dreaming of making running a real art.

First, he wants to construct the running track with coating t. On planet AMI-1511 the coating of the track is the sequence of colored blocks, where each block is denoted as the small English letter. Therefore, every coating can be treated as a string.

Unfortunately, blocks aren't freely sold to non-business customers, but Ayrat found an infinite number of coatings s. Also, he has scissors and glue. Ayrat is going to buy some coatings s, then cut out from each of them exactly one continuous piece (substring) and glue it to the end of his track coating. Moreover, he may choose to flip this block before glueing it. Ayrat want's to know the minimum number of coating s he needs to buy in order to get the coating t for his running track. Of course, he also want's to know some way to achieve the answer.


-----Input-----

First line of the input contains the string s — the coating that is present in the shop. Second line contains the string t — the coating Ayrat wants to obtain. Both strings are non-empty, consist of only small English letters and their length doesn't exceed 2100.


-----Output-----

The first line should contain the minimum needed number of coatings n or -1 if it's impossible to create the desired coating.

If the answer is not -1, then the following n lines should contain two integers x_{i} and y_{i} — numbers of ending blocks in the corresponding piece. If x_{i} ≤ y_{i} then this piece is used in the regular order, and if x_{i} > y_{i} piece is used in the reversed order. Print the pieces in the order they should be glued to get the string t.


-----Examples-----
Input
abc
cbaabc

Output
2
3 1
1 3

Input
aaabrytaaa
ayrat

Output
3
1 1
6 5
8 7

Input
ami
no

Output
-1



-----Note-----

In the first sample string "cbaabc" = "cba" + "abc".

In the second sample: "ayrat" = "a" + "yr" + "at".
user: You are given a chessboard of size 1 × n. It is guaranteed that n is even. The chessboard is painted like this: "BWBW...BW".

Some cells of the board are occupied by the chess pieces. Each cell contains no more than one chess piece. It is known that the total number of pieces equals to $\frac{n}{2}$.

In one step you can move one of the pieces one cell to the left or to the right. You cannot move pieces beyond the borders of the board. You also cannot move pieces to the cells that are already occupied.

Your task is to place all the pieces in the cells of the same color using the minimum number of moves (all the pieces must occupy only the black cells or only the white cells after all the moves are made).


-----Input-----

The first line of the input contains one integer n (2 ≤ n ≤ 100, n is even) — the size of the chessboard. 

The second line of the input contains $\frac{n}{2}$ integer numbers $p_{1}, p_{2}, \ldots, p_{\frac{n}{2}}$ (1 ≤ p_{i} ≤ n) — initial positions of the pieces. It is guaranteed that all the positions are distinct.


-----Output-----

Print one integer — the minimum number of moves you have to make to place all the pieces in the cells of the same color.


-----Examples-----
Input
6
1 2 6

Output
2

Input
10
1 2 3 4 5

Output
10



-----Note-----

In the first example the only possible strategy is to move the piece at the position 6 to the position 5 and move the piece at the position 2 to the position 3. Notice that if you decide to place the pieces in the white cells the minimum number of moves will be 3.

In the second example the possible strategy is to move $5 \rightarrow 9$ in 4 moves, then $4 \rightarrow 7$ in 3 moves, $3 \rightarrow 5$ in 2 moves and $2 \rightarrow 3$ in 1 move.
user: Kolya is going to make fresh orange juice. He has n oranges of sizes a_1, a_2, ..., a_{n}. Kolya will put them in the juicer in the fixed order, starting with orange of size a_1, then orange of size a_2 and so on. To be put in the juicer the orange must have size not exceeding b, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than d. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?


-----Input-----

The first line of the input contains three integers n, b and d (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value d, which determines the condition when the waste section should be emptied.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1 000 000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.


-----Output-----

Print one integer — the number of times Kolya will have to empty the waste section.


-----Examples-----
Input
2 7 10
5 6

Output
1

Input
1 5 10
7

Output
0

Input
3 10 10
5 7 7

Output
1

Input
1 1 1
1

Output
0



-----Note-----

In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.
user: Consider an n × m grid. Initially all the cells of the grid are colored white. Lenny has painted some of the cells (at least one) black. We call a painted grid convex if one can walk from any black cell to any another black cell using a path of side-adjacent black cells changing his direction at most once during the path. In the figure below, the left grid is convex while the right one is not convex, because there exist two cells which need more than one time to change direction in their path. [Image] 

You're given a painted grid in the input. Tell Lenny if the grid is convex or not.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 50) — the size of the grid. Each of the next n lines contains m characters "B" or "W". Character "B" denotes a black cell of the grid and "W" denotes a white cell of the grid.

It's guaranteed that the grid has at least one black cell.


-----Output-----

On the only line of the output print "YES" if the grid is convex, otherwise print "NO". Do not print quotes.


-----Examples-----
Input
3 4
WWBW
BWWW
WWWB

Output
NO

Input
3 1
B
B
W

Output
YES
user: Bob is a farmer. He has a large pasture with many sheep. Recently, he has lost some of them due to wolf attacks. He thus decided to place some shepherd dogs in such a way that all his sheep are protected.

The pasture is a rectangle consisting of R × C cells. Each cell is either empty, contains a sheep, a wolf or a dog. Sheep and dogs always stay in place, but wolves can roam freely around the pasture, by repeatedly moving to the left, right, up or down to a neighboring cell. When a wolf enters a cell with a sheep, it consumes it. However, no wolf can enter a cell with a dog.

Initially there are no dogs. Place dogs onto the pasture in such a way that no wolf can reach any sheep, or determine that it is impossible. Note that since you have many dogs, you do not need to minimize their number. 


-----Input-----

First line contains two integers R (1 ≤ R ≤ 500) and C (1 ≤ C ≤ 500), denoting the number of rows and the numbers of columns respectively.

Each of the following R lines is a string consisting of exactly C characters, representing one row of the pasture. Here, 'S' means a sheep, 'W' a wolf and '.' an empty cell.


-----Output-----

If it is impossible to protect all sheep, output a single line with the word "No".

Otherwise, output a line with the word "Yes". Then print R lines, representing the pasture after placing dogs. Again, 'S' means a sheep, 'W' a wolf, 'D' is a dog and '.' an empty space. You are not allowed to move, remove or add a sheep or a wolf.

If there are multiple solutions, you may print any of them. You don't have to minimize the number of dogs.


-----Examples-----
Input
6 6
..S...
..S.W.
.S....
..W...
...W..
......

Output
Yes
..SD..
..SDW.
.SD...
.DW...
DD.W..
......

Input
1 2
SW

Output
No

Input
5 5
.S...
...S.
S....
...S.
.S...

Output
Yes
.S...
...S.
S.D..
...S.
.S...



-----Note-----

In the first example, we can split the pasture into two halves, one containing wolves and one containing sheep. Note that the sheep at (2,1) is safe, as wolves cannot move diagonally.

In the second example, there are no empty spots to put dogs that would guard the lone sheep.

In the third example, there are no wolves, so the task is very easy. We put a dog in the center to observe the peacefulness of the meadow, but the solution would be correct even without him.
user: Okabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n. Initially there are no boxes on the stack.

Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the top of the stack, and n of which are to remove a box from the top of the stack and throw it in the trash. Okabe wants Daru to throw away the boxes in the order from 1 to n. Of course, this means that it might be impossible for Daru to perform some of Okabe's remove commands, because the required box is not on the top of the stack.

That's why Daru can decide to wait until Okabe looks away and then reorder the boxes in the stack in any way he wants. He can do it at any point of time between Okabe's commands, but he can't add or remove boxes while he does it.

Tell Daru the minimum number of times he needs to reorder the boxes so that he can successfully complete all of Okabe's commands. It is guaranteed that every box is added before it is required to be removed.


-----Input-----

The first line of input contains the integer n (1 ≤ n ≤ 3·10^5) — the number of boxes.

Each of the next 2n lines of input starts with a string "add" or "remove". If the line starts with the "add", an integer x (1 ≤ x ≤ n) follows, indicating that Daru should add the box with number x to the top of the stack. 

It is guaranteed that exactly n lines contain "add" operations, all the boxes added are distinct, and n lines contain "remove" operations. It is also guaranteed that a box is always added before it is required to be removed.


-----Output-----

Print the minimum number of times Daru needs to reorder the boxes to successfully complete all of Okabe's commands.


-----Examples-----
Input
3
add 1
remove
add 2
add 3
remove
remove

Output
1

Input
7
add 3
add 2
add 1
remove
add 4
remove
remove
remove
add 6
add 7
add 5
remove
remove
remove

Output
2



-----Note-----

In the first sample, Daru should reorder the boxes after adding box 3 to the stack.

In the second sample, Daru should reorder the boxes after adding box 4 and box 7 to the stack.
user: After the fourth season Sherlock and Moriary have realized the whole foolishness of the battle between them and decided to continue their competitions in peaceful game of Credit Cards.

Rules of this game are simple: each player bring his favourite n-digit credit card. Then both players name the digits written on their cards one by one. If two digits are not equal, then the player, whose digit is smaller gets a flick (knock in the forehead usually made with a forefinger) from the other player. For example, if n = 3, Sherlock's card is 123 and Moriarty's card has number 321, first Sherlock names 1 and Moriarty names 3 so Sherlock gets a flick. Then they both digit 2 so no one gets a flick. Finally, Sherlock names 3, while Moriarty names 1 and gets a flick.

Of course, Sherlock will play honestly naming digits one by one in the order they are given, while Moriary, as a true villain, plans to cheat. He is going to name his digits in some other order (however, he is not going to change the overall number of occurences of each digit). For example, in case above Moriarty could name 1, 2, 3 and get no flicks at all, or he can name 2, 3 and 1 to give Sherlock two flicks.

Your goal is to find out the minimum possible number of flicks Moriarty will get (no one likes flicks) and the maximum possible number of flicks Sherlock can get from Moriarty. Note, that these two goals are different and the optimal result may be obtained by using different strategies.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the number of digits in the cards Sherlock and Moriarty are going to use.

The second line contains n digits — Sherlock's credit card number.

The third line contains n digits — Moriarty's credit card number.


-----Output-----

First print the minimum possible number of flicks Moriarty will get. Then print the maximum possible number of flicks that Sherlock can get from Moriarty.


-----Examples-----
Input
3
123
321

Output
0
2

Input
2
88
00

Output
2
0



-----Note-----

First sample is elaborated in the problem statement. In the second sample, there is no way Moriarty can avoid getting two flicks.
user: You have decided to watch the best moments of some movie. There are two buttons on your player:   Watch the current minute of the movie. By pressing this button, you watch the current minute of the movie and the player automatically proceeds to the next minute of the movie.  Skip exactly x minutes of the movie (x is some fixed positive integer). If the player is now at the t-th minute of the movie, then as a result of pressing this button, it proceeds to the minute (t + x). 

Initially the movie is turned on in the player on the first minute, and you want to watch exactly n best moments of the movie, the i-th best moment starts at the l_{i}-th minute and ends at the r_{i}-th minute (more formally, the i-th best moment consists of minutes: l_{i}, l_{i} + 1, ..., r_{i}). 

Determine, what is the minimum number of minutes of the movie you have to watch if you want to watch all the best moments?


-----Input-----

The first line contains two space-separated integers n, x (1 ≤ n ≤ 50, 1 ≤ x ≤ 10^5) — the number of the best moments of the movie and the value of x for the second button.

The following n lines contain the descriptions of the best moments of the movie, the i-th line of the description contains two integers separated by a space l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^5).

It is guaranteed that for all integers i from 2 to n the following condition holds: r_{i} - 1 < l_{i}.


-----Output-----

Output a single number — the answer to the problem.


-----Examples-----
Input
2 3
5 6
10 12

Output
6

Input
1 1
1 100000

Output
100000



-----Note-----

In the first sample, the player was initially standing on the first minute. As the minutes from the 1-st to the 4-th one don't contain interesting moments, we press the second button. Now we can not press the second button and skip 3 more minutes, because some of them contain interesting moments. Therefore, we watch the movie from the 4-th to the 6-th minute, after that the current time is 7. Similarly, we again skip 3 minutes and then watch from the 10-th to the 12-th minute of the movie. In total, we watch 6 minutes of the movie.

In the second sample, the movie is very interesting, so you'll have to watch all 100000 minutes of the movie.