meetforever/GRPO_CL huggingface dataset:
user: A new airplane SuperPuperJet has an infinite number of rows, numbered with positive integers starting with 1 from cockpit to tail. There are six seats in each row, denoted with letters from 'a' to 'f'. Seats 'a', 'b' and 'c' are located to the left of an aisle (if one looks in the direction of the cockpit), while seats 'd', 'e' and 'f' are located to the right. Seats 'a' and 'f' are located near the windows, while seats 'c' and 'd' are located near the aisle.  [Image] 

 

It's lunch time and two flight attendants have just started to serve food. They move from the first rows to the tail, always maintaining a distance of two rows from each other because of the food trolley. Thus, at the beginning the first attendant serves row 1 while the second attendant serves row 3. When both rows are done they move one row forward: the first attendant serves row 2 while the second attendant serves row 4. Then they move three rows forward and the first attendant serves row 5 while the second attendant serves row 7. Then they move one row forward again and so on.

Flight attendants work with the same speed: it takes exactly 1 second to serve one passenger and 1 second to move one row forward. Each attendant first serves the passengers on the seats to the right of the aisle and then serves passengers on the seats to the left of the aisle (if one looks in the direction of the cockpit). Moreover, they always serve passengers in order from the window to the aisle. Thus, the first passenger to receive food in each row is located in seat 'f', and the last one — in seat 'c'. Assume that all seats are occupied.

Vasya has seat s in row n and wants to know how many seconds will pass before he gets his lunch.


-----Input-----

The only line of input contains a description of Vasya's seat in the format ns, where n (1 ≤ n ≤ 10^18) is the index of the row and s is the seat in this row, denoted as letter from 'a' to 'f'. The index of the row and the seat are not separated by a space.


-----Output-----

Print one integer — the number of seconds Vasya has to wait until he gets his lunch.


-----Examples-----
Input
1f

Output
1

Input
2d

Output
10

Input
4a

Output
11

Input
5e

Output
18



-----Note-----

In the first sample, the first flight attendant serves Vasya first, so Vasya gets his lunch after 1 second.

In the second sample, the flight attendants will spend 6 seconds to serve everyone in the rows 1 and 3, then they will move one row forward in 1 second. As they first serve seats located to the right of the aisle in order from window to aisle, Vasya has to wait 3 more seconds. The total is 6 + 1 + 3 = 10.
user: After seeing the "ALL YOUR BASE ARE BELONG TO US" meme for the first time, numbers X and Y realised that they have different bases, which complicated their relations.

You're given a number X represented in base b_{x} and a number Y represented in base b_{y}. Compare those two numbers.


-----Input-----

The first line of the input contains two space-separated integers n and b_{x} (1 ≤ n ≤ 10, 2 ≤ b_{x} ≤ 40), where n is the number of digits in the b_{x}-based representation of X. 

The second line contains n space-separated integers x_1, x_2, ..., x_{n} (0 ≤ x_{i} < b_{x}) — the digits of X. They are given in the order from the most significant digit to the least significant one.

The following two lines describe Y in the same way: the third line contains two space-separated integers m and b_{y} (1 ≤ m ≤ 10, 2 ≤ b_{y} ≤ 40, b_{x} ≠ b_{y}), where m is the number of digits in the b_{y}-based representation of Y, and the fourth line contains m space-separated integers y_1, y_2, ..., y_{m} (0 ≤ y_{i} < b_{y}) — the digits of Y.

There will be no leading zeroes. Both X and Y will be positive. All digits of both numbers are given in the standard decimal numeral system.


-----Output-----

Output a single character (quotes for clarity):   '<' if X < Y  '>' if X > Y  '=' if X = Y 


-----Examples-----
Input
6 2
1 0 1 1 1 1
2 10
4 7

Output
=

Input
3 3
1 0 2
2 5
2 4

Output
<

Input
7 16
15 15 4 0 0 7 10
7 9
4 8 0 3 1 5 0

Output
>



-----Note-----

In the first sample, X = 101111_2 = 47_10 = Y.

In the second sample, X = 102_3 = 21_5 and Y = 24_5 = 112_3, thus X < Y.

In the third sample, $X = FF 4007 A_{16}$ and Y = 4803150_9. We may notice that X starts with much larger digits and b_{x} is much larger than b_{y}, so X is clearly larger than Y.
user: Since most contestants do not read this part, I have to repeat that Bitlandians are quite weird. They have their own jobs, their own working method, their own lives, their own sausages and their own games!

Since you are so curious about Bitland, I'll give you the chance of peeking at one of these games.

BitLGM and BitAryo are playing yet another of their crazy-looking genius-needed Bitlandish games. They've got a sequence of n non-negative integers a_1, a_2, ..., a_{n}. The players make moves in turns. BitLGM moves first. Each player can and must do one of the two following actions in his turn:

  Take one of the integers (we'll denote it as a_{i}). Choose integer x (1 ≤ x ≤ a_{i}). And then decrease a_{i} by x, that is, apply assignment: a_{i} = a_{i} - x.  Choose integer x $(1 \leq x \leq \operatorname{min}_{i = 1} a_{i})$. And then decrease all a_{i} by x, that is, apply assignment: a_{i} = a_{i} - x, for all i. 

The player who cannot make a move loses.

You're given the initial sequence a_1, a_2, ..., a_{n}. Determine who wins, if both players plays optimally well and if BitLGM and BitAryo start playing the described game in this sequence.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 3).

The next line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} < 300).


-----Output-----

Write the name of the winner (provided that both players play optimally well). Either "BitLGM" or "BitAryo" (without the quotes).


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

Output
BitLGM

Input
2
1 2

Output
BitAryo

Input
3
1 2 1

Output
BitLGM
user: Vova again tries to play some computer card game.

The rules of deck creation in this game are simple. Vova is given an existing deck of n cards and a magic number k. The order of the cards in the deck is fixed. Each card has a number written on it; number a_{i} is written on the i-th card in the deck.

After receiving the deck and the magic number, Vova removes x (possibly x = 0) cards from the top of the deck, y (possibly y = 0) cards from the bottom of the deck, and the rest of the deck is his new deck (Vova has to leave at least one card in the deck after removing cards). So Vova's new deck actually contains cards x + 1, x + 2, ... n - y - 1, n - y from the original deck.

Vova's new deck is considered valid iff the product of all numbers written on the cards in his new deck is divisible by k. So Vova received a deck (possibly not a valid one) and a number k, and now he wonders, how many ways are there to choose x and y so the deck he will get after removing x cards from the top and y cards from the bottom is valid?


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9).

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the numbers written on the cards.


-----Output-----

Print the number of ways to choose x and y so the resulting deck is valid.


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

Output
4

Input
3 6
9 1 14

Output
1



-----Note-----

In the first example the possible values of x and y are:

  x = 0, y = 0;  x = 1, y = 0;  x = 2, y = 0;  x = 0, y = 1.
user: One day Kefa found n baloons. For convenience, we denote color of i-th baloon as s_{i} — lowercase letter of the Latin alphabet. Also Kefa has k friends. Friend will be upset, If he get two baloons of the same color. Kefa want to give out all baloons to his friends. Help Kefa to find out, can he give out all his baloons, such that no one of his friens will be upset — print «YES», if he can, and «NO», otherwise. Note, that Kefa's friend will not upset, if he doesn't get baloons at all.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 100) — the number of baloons and friends.

Next line contains string s — colors of baloons.


-----Output-----

Answer to the task — «YES» or «NO» in a single line.

You can choose the case (lower or upper) for each letter arbitrary.


-----Examples-----
Input
4 2
aabb

Output
YES

Input
6 3
aacaab

Output
NO



-----Note-----

In the first sample Kefa can give 1-st and 3-rd baloon to the first friend, and 2-nd and 4-th to the second.

In the second sample Kefa needs to give to all his friends baloons of color a, but one baloon will stay, thats why answer is «NO».
user: You are given an array of n integer numbers a_0, a_1, ..., a_{n} - 1. Find the distance between two closest (nearest) minimums in it. It is guaranteed that in the array a minimum occurs at least two times.


-----Input-----

The first line contains positive integer n (2 ≤ n ≤ 10^5) — size of the given array. The second line contains n integers a_0, a_1, ..., a_{n} - 1 (1 ≤ a_{i} ≤ 10^9) — elements of the array. It is guaranteed that in the array a minimum occurs at least two times.


-----Output-----

Print the only number — distance between two nearest minimums in the array.


-----Examples-----
Input
2
3 3

Output
1

Input
3
5 6 5

Output
2

Input
9
2 1 3 5 4 1 2 3 1

Output
3
user: Vector Willman and Array Bolt are the two most famous athletes of Byteforces. They are going to compete in a race with a distance of L meters today.

 [Image] 

Willman and Bolt have exactly the same speed, so when they compete the result is always a tie. That is a problem for the organizers because they want a winner. 

While watching previous races the organizers have noticed that Willman can perform only steps of length equal to w meters, and Bolt can perform only steps of length equal to b meters. Organizers decided to slightly change the rules of the race. Now, at the end of the racetrack there will be an abyss, and the winner will be declared the athlete, who manages to run farther from the starting point of the the racetrack (which is not the subject to change by any of the athletes). 

Note that none of the athletes can run infinitely far, as they both will at some moment of time face the point, such that only one step further will cause them to fall in the abyss. In other words, the athlete will not fall into the abyss if the total length of all his steps will be less or equal to the chosen distance L.

Since the organizers are very fair, the are going to set the length of the racetrack as an integer chosen randomly and uniformly in range from 1 to t (both are included). What is the probability that Willman and Bolt tie again today?


-----Input-----

The first line of the input contains three integers t, w and b (1 ≤ t, w, b ≤ 5·10^18) — the maximum possible length of the racetrack, the length of Willman's steps and the length of Bolt's steps respectively.


-----Output-----

Print the answer to the problem as an irreducible fraction [Image]. Follow the format of the samples output.

The fraction [Image] (p and q are integers, and both p ≥ 0 and q > 0 holds) is called irreducible, if there is no such integer d > 1, that both p and q are divisible by d.


-----Examples-----
Input
10 3 2

Output
3/10

Input
7 1 2

Output
3/7



-----Note-----

In the first sample Willman and Bolt will tie in case 1, 6 or 7 are chosen as the length of the racetrack.
user: Nauuo is a girl who loves writing comments.

One day, she posted a comment on Codeforces, wondering whether she would get upvotes or downvotes.

It's known that there were $x$ persons who would upvote, $y$ persons who would downvote, and there were also another $z$ persons who would vote, but you don't know whether they would upvote or downvote. Note that each of the $x+y+z$ people would vote exactly one time.

There are three different results: if there are more people upvote than downvote, the result will be "+"; if there are more people downvote than upvote, the result will be "-"; otherwise the result will be "0".

Because of the $z$ unknown persons, the result may be uncertain (i.e. there are more than one possible results). More formally, the result is uncertain if and only if there exist two different situations of how the $z$ persons vote, that the results are different in the two situations.

Tell Nauuo the result or report that the result is uncertain.


-----Input-----

The only line contains three integers $x$, $y$, $z$ ($0\le x,y,z\le100$), corresponding to the number of persons who would upvote, downvote or unknown.


-----Output-----

If there is only one possible result, print the result : "+", "-" or "0".

Otherwise, print "?" to report that the result is uncertain.


-----Examples-----
Input
3 7 0

Output
-
Input
2 0 1

Output
+
Input
1 1 0

Output
0
Input
0 0 1

Output
?


-----Note-----

In the first example, Nauuo would definitely get three upvotes and seven downvotes, so the only possible result is "-".

In the second example, no matter the person unknown downvotes or upvotes, Nauuo would get more upvotes than downvotes. So the only possible result is "+".

In the third example, Nauuo would definitely get one upvote and one downvote, so the only possible result is "0".

In the fourth example, if the only one person upvoted, the result would be "+", otherwise, the result would be "-". There are two possible results, so the result is uncertain.
user: Vasya has got a robot which is situated on an infinite Cartesian plane, initially in the cell $(0, 0)$. Robot can perform the following four kinds of operations:   U — move from $(x, y)$ to $(x, y + 1)$;  D — move from $(x, y)$ to $(x, y - 1)$;  L — move from $(x, y)$ to $(x - 1, y)$;  R — move from $(x, y)$ to $(x + 1, y)$. 

Vasya also has got a sequence of $n$ operations. Vasya wants to modify this sequence so after performing it the robot will end up in $(x, y)$.

Vasya wants to change the sequence so the length of changed subsegment is minimum possible. This length can be calculated as follows: $maxID - minID + 1$, where $maxID$ is the maximum index of a changed operation, and $minID$ is the minimum index of a changed operation. For example, if Vasya changes RRRRRRR to RLRRLRL, then the operations with indices $2$, $5$ and $7$ are changed, so the length of changed subsegment is $7 - 2 + 1 = 6$. Another example: if Vasya changes DDDD to DDRD, then the length of changed subsegment is $1$. 

If there are no changes, then the length of changed subsegment is $0$. Changing an operation means replacing it with some operation (possibly the same); Vasya can't insert new operations into the sequence or remove them.

Help Vasya! Tell him the minimum length of subsegment that he needs to change so that the robot will go from $(0, 0)$ to $(x, y)$, or tell him that it's impossible.


-----Input-----

The first line contains one integer number $n~(1 \le n \le 2 \cdot 10^5)$ — the number of operations.

The second line contains the sequence of operations — a string of $n$ characters. Each character is either U, D, L or R.

The third line contains two integers $x, y~(-10^9 \le x, y \le 10^9)$ — the coordinates of the cell where the robot should end its path.


-----Output-----

Print one integer — the minimum possible length of subsegment that can be changed so the resulting sequence of operations moves the robot from $(0, 0)$ to $(x, y)$. If this change is impossible, print $-1$.


-----Examples-----
Input
5
RURUU
-2 3

Output
3

Input
4
RULR
1 1

Output
0

Input
3
UUU
100 100

Output
-1



-----Note-----

In the first example the sequence can be changed to LULUU. So the length of the changed subsegment is $3 - 1 + 1 = 3$.

In the second example the given sequence already leads the robot to $(x, y)$, so the length of the changed subsegment is $0$.

In the third example the robot can't end his path in the cell $(x, y)$.
user: You are given string $s$ of length $n$ consisting of 0-s and 1-s. You build an infinite string $t$ as a concatenation of an infinite number of strings $s$, or $t = ssss \dots$ For example, if $s =$ 10010, then $t =$ 100101001010010...

Calculate the number of prefixes of $t$ with balance equal to $x$. The balance of some string $q$ is equal to $cnt_{0, q} - cnt_{1, q}$, where $cnt_{0, q}$ is the number of occurrences of 0 in $q$, and $cnt_{1, q}$ is the number of occurrences of 1 in $q$. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string "abcd" has 5 prefixes: empty string, "a", "ab", "abc" and "abcd".


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $2T$ lines contain descriptions of test cases — two lines per test case. The first line contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $-10^9 \le x \le 10^9$) — the length of string $s$ and the desired balance, respectively.

The second line contains the binary string $s$ ($|s| = n$, $s_i \in \{\text{0}, \text{1}\}$).

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print the number of prefixes or $-1$ if there is an infinite number of such prefixes.


-----Example-----
Input
4
6 10
010010
5 3
10101
1 0
0
2 0
01

Output
3
0
1
-1



-----Note-----

In the first test case, there are 3 good prefixes of $t$: with length $28$, $30$ and $32$.
user: Polycarp is crazy about round numbers. He especially likes the numbers divisible by 10^{k}.

In the given number of n Polycarp wants to remove the least number of digits to get a number that is divisible by 10^{k}. For example, if k = 3, in the number 30020 it is enough to delete a single digit (2). In this case, the result is 3000 that is divisible by 10^3 = 1000.

Write a program that prints the minimum number of digits to be deleted from the given integer number n, so that the result is divisible by 10^{k}. The result should not start with the unnecessary leading zero (i.e., zero can start only the number 0, which is required to be written as exactly one digit).

It is guaranteed that the answer exists.


-----Input-----

The only line of the input contains two integer numbers n and k (0 ≤ n ≤ 2 000 000 000, 1 ≤ k ≤ 9).

It is guaranteed that the answer exists. All numbers in the input are written in traditional notation of integers, that is, without any extra leading zeros.


-----Output-----

Print w — the required minimal number of digits to erase. After removing the appropriate w digits from the number n, the result should have a value that is divisible by 10^{k}. The result can start with digit 0 in the single case (the result is zero and written by exactly the only digit 0).


-----Examples-----
Input
30020 3

Output
1

Input
100 9

Output
2

Input
10203049 2

Output
3



-----Note-----

In the example 2 you can remove two digits: 1 and any 0. The result is number 0 which is divisible by any number.
user: On the Literature lesson Sergei noticed an awful injustice, it seems that some students are asked more often than others.

Seating in the class looks like a rectangle, where n rows with m pupils in each. 

The teacher asks pupils in the following order: at first, she asks all pupils from the first row in the order of their seating, then she continues to ask pupils from the next row. If the teacher asked the last row, then the direction of the poll changes, it means that she asks the previous row. The order of asking the rows looks as follows: the 1-st row, the 2-nd row, ..., the n - 1-st row, the n-th row, the n - 1-st row, ..., the 2-nd row, the 1-st row, the 2-nd row, ...

The order of asking of pupils on the same row is always the same: the 1-st pupil, the 2-nd pupil, ..., the m-th pupil.

During the lesson the teacher managed to ask exactly k questions from pupils in order described above. Sergei seats on the x-th row, on the y-th place in the row. Sergei decided to prove to the teacher that pupils are asked irregularly, help him count three values:  the maximum number of questions a particular pupil is asked,  the minimum number of questions a particular pupil is asked,  how many times the teacher asked Sergei. 

If there is only one row in the class, then the teacher always asks children from this row.


-----Input-----

The first and the only line contains five integers n, m, k, x and y (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 10^18, 1 ≤ x ≤ n, 1 ≤ y ≤ m).


-----Output-----

Print three integers:  the maximum number of questions a particular pupil is asked,  the minimum number of questions a particular pupil is asked,  how many times the teacher asked Sergei. 


-----Examples-----
Input
1 3 8 1 1

Output
3 2 3
Input
4 2 9 4 2

Output
2 1 1
Input
5 5 25 4 3

Output
1 1 1
Input
100 100 1000000000000000000 100 100

Output
101010101010101 50505050505051 50505050505051


-----Note-----

The order of asking pupils in the first test:   the pupil from the first row who seats at the first table, it means it is Sergei;  the pupil from the first row who seats at the second table;  the pupil from the first row who seats at the third table;  the pupil from the first row who seats at the first table, it means it is Sergei;  the pupil from the first row who seats at the second table;  the pupil from the first row who seats at the third table;  the pupil from the first row who seats at the first table, it means it is Sergei;  the pupil from the first row who seats at the second table; 

The order of asking pupils in the second test:   the pupil from the first row who seats at the first table;  the pupil from the first row who seats at the second table;  the pupil from the second row who seats at the first table;  the pupil from the second row who seats at the second table;  the pupil from the third row who seats at the first table;  the pupil from the third row who seats at the second table;  the pupil from the fourth row who seats at the first table;  the pupil from the fourth row who seats at the second table, it means it is Sergei;  the pupil from the third row who seats at the first table;