meetforever/GRPO_CL huggingface dataset:
user: Alice has a birthday today, so she invited home her best friend Bob. Now Bob needs to find a way to commute to the Alice's home.

In the city in which Alice and Bob live, the first metro line is being built. This metro line contains $n$ stations numbered from $1$ to $n$. Bob lives near the station with number $1$, while Alice lives near the station with number $s$. The metro line has two tracks. Trains on the first track go from the station $1$ to the station $n$ and trains on the second track go in reverse direction. Just after the train arrives to the end of its track, it goes to the depot immediately, so it is impossible to travel on it after that.

Some stations are not yet open at all and some are only partially open — for each station and for each track it is known whether the station is closed for that track or not. If a station is closed for some track, all trains going in this track's direction pass the station without stopping on it.

When the Bob got the information on opened and closed stations, he found that traveling by metro may be unexpectedly complicated. Help Bob determine whether he can travel to the Alice's home by metro or he should search for some other transport.


-----Input-----

The first line contains two integers $n$ and $s$ ($2 \le s \le n \le 1000$) — the number of stations in the metro and the number of the station where Alice's home is located. Bob lives at station $1$.

Next lines describe information about closed and open stations.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = 0$ or $a_i = 1$). If $a_i = 1$, then the $i$-th station is open on the first track (that is, in the direction of increasing station numbers). Otherwise the station is closed on the first track.

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($b_i = 0$ or $b_i = 1$). If $b_i = 1$, then the $i$-th station is open on the second track (that is, in the direction of decreasing station numbers). Otherwise the station is closed on the second track.


-----Output-----

Print "YES" (quotes for clarity) if Bob will be able to commute to the Alice's home by metro and "NO" (quotes for clarity) otherwise.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
5 3
1 1 1 1 1
1 1 1 1 1

Output
YES

Input
5 4
1 0 0 0 1
0 1 1 1 1

Output
YES

Input
5 2
0 1 1 1 1
1 1 1 1 1

Output
NO



-----Note-----

In the first example, all stations are opened, so Bob can simply travel to the station with number $3$.

In the second example, Bob should travel to the station $5$ first, switch to the second track and travel to the station $4$ then.

In the third example, Bob simply can't enter the train going in the direction of Alice's home.
user: Amr is a young coder who likes music a lot. He always wanted to learn how to play music but he was busy coding so he got an idea.

Amr has n instruments, it takes a_{i} days to learn i-th instrument. Being busy, Amr dedicated k days to learn how to play the maximum possible number of instruments.

Amr asked for your help to distribute his free days between instruments so that he can achieve his goal.


-----Input-----

The first line contains two numbers n, k (1 ≤ n ≤ 100, 0 ≤ k ≤ 10 000), the number of instruments and number of days respectively.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 100), representing number of days required to learn the i-th instrument.


-----Output-----

In the first line output one integer m representing the maximum number of instruments Amr can learn.

In the second line output m space-separated integers: the indices of instruments to be learnt. You may output indices in any order.

if there are multiple optimal solutions output any. It is not necessary to use all days for studying.


-----Examples-----
Input
4 10
4 3 1 2

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

Output
3
1 3 4
Input
1 3
4

Output
0



-----Note-----

In the first test Amr can learn all 4 instruments.

In the second test other possible solutions are: {2, 3, 5} or {3, 4, 5}.

In the third test Amr doesn't have enough time to learn the only presented instrument.
user: A camera you have accidentally left in a desert has taken an interesting photo. The photo has a resolution of n pixels width, and each column of this photo is all white or all black. Thus, we can represent the photo as a sequence of n zeros and ones, where 0 means that the corresponding column is all white, and 1 means that the corresponding column is black.

You think that this photo can contain a zebra. In this case the whole photo should consist of several (possibly, only one) alternating black and white stripes of equal width. For example, the photo [0, 0, 0, 1, 1, 1, 0, 0, 0] can be a photo of zebra, while the photo [0, 0, 0, 1, 1, 1, 1] can not, because the width of the black stripe is 3, while the width of the white stripe is 4. Can the given photo be a photo of zebra or not?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the width of the photo.

The second line contains a sequence of integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 1) — the description of the photo. If a_{i} is zero, the i-th column is all black. If a_{i} is one, then the i-th column is all white.


-----Output-----

If the photo can be a photo of zebra, print "YES" (without quotes). Otherwise, print "NO".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
9
0 0 0 1 1 1 0 0 0

Output
YES

Input
7
0 0 0 1 1 1 1

Output
NO

Input
5
1 1 1 1 1

Output
YES

Input
8
1 1 1 0 0 0 1 1

Output
NO

Input
9
1 1 0 1 1 0 1 1 0

Output
NO



-----Note-----

The first two examples are described in the statements.

In the third example all pixels are white, so the photo can be a photo of zebra.

In the fourth example the width of the first stripe is equal to three (white color), the width of the second stripe is equal to three (black), and the width of the third stripe is equal to two (white). Thus, not all stripes have equal length, so this photo is not a photo of zebra.
user: The only difference between easy and hard versions is constraints.

A session has begun at Beland State University. Many students are taking exams.

Polygraph Poligrafovich is going to examine a group of $n$ students. Students will take the exam one-by-one in order from $1$-th to $n$-th. Rules of the exam are following:  The $i$-th student randomly chooses a ticket.  if this ticket is too hard to the student, he doesn't answer and goes home immediately (this process is so fast that it's considered no time elapses). This student fails the exam.  if the student finds the ticket easy, he spends exactly $t_i$ minutes to pass the exam. After it, he immediately gets a mark and goes home. 

Students take the exam in the fixed order, one-by-one, without any interruption. At any moment of time, Polygraph Poligrafovich takes the answer from one student.

The duration of the whole exam for all students is $M$ minutes ($\max t_i \le M$), so students at the end of the list have a greater possibility to run out of time to pass the exam.

For each student $i$, you should count the minimum possible number of students who need to fail the exam so the $i$-th student has enough time to pass the exam.

For each student $i$, find the answer independently. That is, if when finding the answer for the student $i_1$ some student $j$ should leave, then while finding the answer for $i_2$ ($i_2>i_1$) the student $j$ student does not have to go home.


-----Input-----

The first line of the input contains two integers $n$ and $M$ ($1 \le n \le 100$, $1 \le M \le 100$) — the number of students and the total duration of the exam in minutes, respectively.

The second line of the input contains $n$ integers $t_i$ ($1 \le t_i \le 100$) — time in minutes that $i$-th student spends to answer to a ticket.

It's guaranteed that all values of $t_i$ are not greater than $M$.


-----Output-----

Print $n$ numbers: the $i$-th number must be equal to the minimum number of students who have to leave the exam in order to $i$-th student has enough time to pass the exam.


-----Examples-----
Input
7 15
1 2 3 4 5 6 7

Output
0 0 0 0 0 2 3 
Input
5 100
80 40 40 40 60

Output
0 1 1 2 3 


-----Note-----

The explanation for the example 1.

Please note that the sum of the first five exam times does not exceed $M=15$ (the sum is $1+2+3+4+5=15$). Thus, the first five students can pass the exam even if all the students before them also pass the exam. In other words, the first five numbers in the answer are $0$.

In order for the $6$-th student to pass the exam, it is necessary that at least $2$ students must fail it before (for example, the $3$-rd and $4$-th, then the $6$-th will finish its exam in $1+2+5+6=14$ minutes, which does not exceed $M$).

In order for the $7$-th student to pass the exam, it is necessary that at least $3$ students must fail it before (for example, the $2$-nd, $5$-th and $6$-th, then the $7$-th will finish its exam in $1+3+4+7=15$ minutes, which does not exceed $M$).
user: Dr. Evil kidnapped Mahmoud and Ehab in the evil land because of their performance in the Evil Olympiad in Informatics (EOI). He decided to give them some problems to let them go.

Dr. Evil is interested in sets, He has a set of n integers. Dr. Evil calls a set of integers evil if the MEX of it is exactly x. the MEX of a set of integers is the minimum non-negative integer that doesn't exist in it. For example, the MEX of the set {0, 2, 4} is 1 and the MEX of the set {1, 2, 3} is 0 .

Dr. Evil is going to make his set evil. To do this he can perform some operations. During each operation he can add some non-negative integer to his set or erase some element from it. What is the minimal number of operations Dr. Evil has to perform to make his set evil?


-----Input-----

The first line contains two integers n and x (1 ≤ n ≤ 100, 0 ≤ x ≤ 100) — the size of the set Dr. Evil owns, and the desired MEX.

The second line contains n distinct non-negative integers not exceeding 100 that represent the set.


-----Output-----

The only line should contain one integer — the minimal number of operations Dr. Evil should perform.


-----Examples-----
Input
5 3
0 4 5 6 7

Output
2

Input
1 0
0

Output
1

Input
5 0
1 2 3 4 5

Output
0



-----Note-----

For the first test case Dr. Evil should add 1 and 2 to the set performing 2 operations.

For the second test case Dr. Evil should erase 0 from the set. After that, the set becomes empty, so the MEX of it is 0.

In the third test case the set is already evil.
user: Two players are playing a game. First each of them writes an integer from 1 to 6, and then a dice is thrown. The player whose written number got closer to the number on the dice wins. If both payers have the same difference, it's a draw.

The first player wrote number a, the second player wrote number b. How many ways to throw a dice are there, at which the first player wins, or there is a draw, or the second player wins?


-----Input-----

The single line contains two integers a and b (1 ≤ a, b ≤ 6) — the numbers written on the paper by the first and second player, correspondingly.


-----Output-----

Print three integers: the number of ways to throw the dice at which the first player wins, the game ends with a draw or the second player wins, correspondingly.


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

Output
3 0 3

Input
2 4

Output
2 1 3



-----Note-----

The dice is a standard cube-shaped six-sided object with each side containing a number from 1 to 6, and where all numbers on all sides are distinct.

You can assume that number a is closer to number x than number b, if |a - x| < |b - x|.
user: Today is Wednesday, the third day of the week. What's more interesting is that tomorrow is the last day of the year 2015.

Limak is a little polar bear. He enjoyed this year a lot. Now, he is so eager to the coming year 2016.

Limak wants to prove how responsible a bear he is. He is going to regularly save candies for the entire year 2016! He considers various saving plans. He can save one candy either on some fixed day of the week or on some fixed day of the month.

Limak chose one particular plan. He isn't sure how many candies he will save in the 2016 with his plan. Please, calculate it and tell him.


-----Input-----

The only line of the input is in one of the following two formats:   "x of week" where x (1 ≤ x ≤ 7) denotes the day of the week. The 1-st day is Monday and the 7-th one is Sunday.  "x of month" where x (1 ≤ x ≤ 31) denotes the day of the month. 


-----Output-----

Print one integer — the number of candies Limak will save in the year 2016.


-----Examples-----
Input
4 of week

Output
52

Input
30 of month

Output
11



-----Note-----

Polar bears use the Gregorian calendar. It is the most common calendar and you likely use it too. You can read about it on Wikipedia if you want to – https://en.wikipedia.org/wiki/Gregorian_calendar. The week starts with Monday.

In the first sample Limak wants to save one candy on each Thursday (the 4-th day of the week). There are 52 Thursdays in the 2016. Thus, he will save 52 candies in total.

In the second sample Limak wants to save one candy on the 30-th day of each month. There is the 30-th day in exactly 11 months in the 2016 — all months but February. It means that Limak will save 11 candies in total.
user: Little boy Petya loves stairs very much. But he is bored from simple going up and down them — he loves jumping over several stairs at a time. As he stands on some stair, he can either jump to the next one or jump over one or two stairs at a time. But some stairs are too dirty and Petya doesn't want to step on them.

Now Petya is on the first stair of the staircase, consisting of n stairs. He also knows the numbers of the dirty stairs of this staircase. Help Petya find out if he can jump through the entire staircase and reach the last stair number n without touching a dirty stair once.

One has to note that anyway Petya should step on the first and last stairs, so if the first or the last stair is dirty, then Petya cannot choose a path with clean steps only.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 10^9, 0 ≤ m ≤ 3000) — the number of stairs in the staircase and the number of dirty stairs, correspondingly. The second line contains m different space-separated integers d_1, d_2, ..., d_{m} (1 ≤ d_{i} ≤ n) — the numbers of the dirty stairs (in an arbitrary order).


-----Output-----

Print "YES" if Petya can reach stair number n, stepping only on the clean stairs. Otherwise print "NO".


-----Examples-----
Input
10 5
2 4 8 3 6

Output
NO
Input
10 5
2 4 5 7 9

Output
YES
user: You are an experienced Codeforces user. Today you found out that during your activity on Codeforces you have made y submissions, out of which x have been successful. Thus, your current success rate on Codeforces is equal to x / y.

Your favorite rational number in the [0;1] range is p / q. Now you wonder: what is the smallest number of submissions you have to make if you want your success rate to be p / q?


-----Input-----

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

Each of the next t lines contains four integers x, y, p and q (0 ≤ x ≤ y ≤ 10^9; 0 ≤ p ≤ q ≤ 10^9; y > 0; q > 0).

It is guaranteed that p / q is an irreducible fraction.

Hacks. For hacks, an additional constraint of t ≤ 5 must be met.


-----Output-----

For each test case, output a single integer equal to the smallest number of submissions you have to make if you want your success rate to be equal to your favorite rational number, or -1 if this is impossible to achieve.


-----Example-----
Input
4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1

Output
4
10
0
-1



-----Note-----

In the first example, you have to make 4 successful submissions. Your success rate will be equal to 7 / 14, or 1 / 2.

In the second example, you have to make 2 successful and 8 unsuccessful submissions. Your success rate will be equal to 9 / 24, or 3 / 8.

In the third example, there is no need to make any new submissions. Your success rate is already equal to 20 / 70, or 2 / 7.

In the fourth example, the only unsuccessful submission breaks your hopes of having the success rate equal to 1.
user: You are given a function $f$ written in some basic language. The function accepts an integer value, which is immediately written into some variable $x$. $x$ is an integer variable and can be assigned values from $0$ to $2^{32}-1$. The function contains three types of commands:

  for $n$ — for loop;  end — every command between "for $n$" and corresponding "end" is executed $n$ times;  add — adds 1 to $x$. 

After the execution of these commands, value of $x$ is returned.

Every "for $n$" is matched with "end", thus the function is guaranteed to be valid. "for $n$" can be immediately followed by "end"."add" command can be outside of any for loops.

Notice that "add" commands might overflow the value of $x$! It means that the value of $x$ becomes greater than $2^{32}-1$ after some "add" command. 

Now you run $f(0)$ and wonder if the resulting value of $x$ is correct or some overflow made it incorrect.

If overflow happened then output "OVERFLOW!!!", otherwise print the resulting value of $x$.


-----Input-----

The first line contains a single integer $l$ ($1 \le l \le 10^5$) — the number of lines in the function.

Each of the next $l$ lines contains a single command of one of three types:

  for $n$ ($1 \le n \le 100$) — for loop;  end — every command between "for $n$" and corresponding "end" is executed $n$ times;  add — adds 1 to $x$. 


-----Output-----

If overflow happened during execution of $f(0)$, then output "OVERFLOW!!!", otherwise print the resulting value of $x$.


-----Examples-----
Input
9
add
for 43
end
for 10
for 15
add
end
add
end

Output
161

Input
2
for 62
end

Output
0

Input
11
for 100
for 100
for 100
for 100
for 100
add
end
end
end
end
end

Output
OVERFLOW!!!



-----Note-----

In the first example the first "add" is executed 1 time, the second "add" is executed 150 times and the last "add" is executed 10 times. Note that "for $n$" can be immediately followed by "end" and that "add" can be outside of any for loops.

In the second example there are no commands "add", thus the returning value is 0.

In the third example "add" command is executed too many times, which causes $x$ to go over $2^{32}-1$.
user: Your friend has n cards.

You know that each card has a lowercase English letter on one side and a digit on the other.

Currently, your friend has laid out the cards on a table so only one side of each card is visible.

You would like to know if the following statement is true for cards that your friend owns: "If a card has a vowel on one side, then it has an even digit on the other side." More specifically, a vowel is one of 'a', 'e', 'i', 'o' or 'u', and even digit is one of '0', '2', '4', '6' or '8'.

For example, if a card has 'a' on one side, and '6' on the other side, then this statement is true for it. Also, the statement is true, for example, for a card with 'b' and '4', and for a card with 'b' and '3' (since the letter is not a vowel). The statement is false, for example, for card with 'e' and '5'. You are interested if the statement is true for all cards. In particular, if no card has a vowel, the statement is true.

To determine this, you can flip over some cards to reveal the other side. You would like to know what is the minimum number of cards you need to flip in the worst case in order to verify that the statement is true.


-----Input-----

The first and only line of input will contain a string s (1 ≤ |s| ≤ 50), denoting the sides of the cards that you can see on the table currently. Each character of s is either a lowercase English letter or a digit.


-----Output-----

Print a single integer, the minimum number of cards you must turn over to verify your claim.


-----Examples-----
Input
ee

Output
2

Input
z

Output
0

Input
0ay1

Output
2



-----Note-----

In the first sample, we must turn over both cards. Note that even though both cards have the same letter, they could possibly have different numbers on the other side.

In the second sample, we don't need to turn over any cards. The statement is vacuously true, since you know your friend has no cards with a vowel on them.

In the third sample, we need to flip the second and fourth cards.
user: There are $n$ detachments on the surface, numbered from $1$ to $n$, the $i$-th detachment is placed in a point with coordinates $(x_i, y_i)$. All detachments are placed in different points.

Brimstone should visit each detachment at least once. You can choose the detachment where Brimstone starts.

To move from one detachment to another he should first choose one of four directions of movement (up, right, left or down) and then start moving with the constant speed of one unit interval in a second until he comes to a detachment. After he reaches an arbitrary detachment, he can repeat the same process.

Each $t$ seconds an orbital strike covers the whole surface, so at that moment Brimstone should be in a point where some detachment is located. He can stay with any detachment as long as needed.

Brimstone is a good commander, that's why he can create at most one detachment and place it in any empty point with integer coordinates he wants before his trip. Keep in mind that Brimstone will need to visit this detachment, too.

Help Brimstone and find such minimal $t$ that it is possible to check each detachment. If there is no such $t$ report about it.


-----Input-----

The first line contains a single integer $n$ $(2 \le n \le 1000)$ — the number of detachments.

In each of the next $n$ lines there is a pair of integers $x_i$, $y_i$ $(|x_i|, |y_i| \le 10^9)$ — the coordinates of $i$-th detachment.

It is guaranteed that all points are different.


-----Output-----

Output such minimal integer $t$ that it is possible to check all the detachments adding at most one new detachment.

If there is no such $t$, print $-1$.


-----Examples-----
Input
4
100 0
0 100
-100 0
0 -100

Output
100
Input
7
0 2
1 0
-3 0
0 -2
-1 -1
-1 -3
-2 -3

Output
-1
Input
5
0 0
0 -1
3 0
-2 0
-2 1

Output
2
Input
5
0 0
2 0
0 -1
-2 0
-2 1

Output
2


-----Note-----

In the first test it is possible to place a detachment in $(0, 0)$, so that it is possible to check all the detachments for $t = 100$. It can be proven that it is impossible to check all detachments for $t < 100$; thus the answer is $100$.

In the second test, there is no such $t$ that it is possible to check all detachments, even with adding at most one new detachment, so the answer is $-1$.

In the third test, it is possible to place a detachment in $(1, 0)$, so that Brimstone can check all the detachments for $t = 2$. It can be proven that it is the minimal such $t$.

In the fourth test, there is no need to add any detachments, because the answer will not get better ($t = 2$). It can be proven that it is the minimal such $t$.