meetforever/GRPO_CL huggingface dataset:
user: You are given a binary matrix $A$ of size $n \times n$. Let's denote an $x$-compression of the given matrix as a matrix $B$ of size $\frac{n}{x} \times \frac{n}{x}$ such that for every $i \in [1, n], j \in [1, n]$ the condition $A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$ is met.

Obviously, $x$-compression is possible only if $x$ divides $n$, but this condition is not enough. For example, the following matrix of size $2 \times 2$ does not have any $2$-compression:

 $01$   $10$ 

For the given matrix $A$, find maximum $x$ such that an $x$-compression of this matrix is possible.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.


-----Input-----

The first line contains one number $n$ ($4 \le n \le 5200$) — the number of rows and columns in the matrix $A$. It is guaranteed that $n$ is divisible by $4$.

Then the representation of matrix follows. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are 1011, and if the number is $5$, then the corresponding elements are 0101.

Elements are not separated by whitespaces.


-----Output-----

Print one number: maximum $x$ such that an $x$-compression of the given matrix is possible.


-----Examples-----
Input
8
E7
E7
E7
00
00
E7
E7
E7

Output
1

Input
4
7
F
F
F

Output
1



-----Note-----

The first example corresponds to the matrix:  $11100111$   $11100111$   $11100111$   $00000000$   $00000000$   $11100111$   $11100111$   $11100111$ 

It is easy to see that the answer on this example is $1$.
user: As we all know Barney's job is "PLEASE" and he has not much to do at work. That's why he started playing "cups and key". In this game there are three identical cups arranged in a line from left to right. Initially key to Barney's heart is under the middle cup. $\left. \begin{array}{l}{\text{Rey}} \\{\text{to my}} \\{\text{heart}} \end{array} \right.$ 

Then at one turn Barney swaps the cup in the middle with any of other two cups randomly (he choses each with equal probability), so the chosen cup becomes the middle one. Game lasts n turns and Barney independently choses a cup to swap with the middle one within each turn, and the key always remains in the cup it was at the start.

After n-th turn Barney asks a girl to guess which cup contains the key. The girl points to the middle one but Barney was distracted while making turns and doesn't know if the key is under the middle cup. That's why he asked you to tell him the probability that girl guessed right.

Number n of game turns can be extremely large, that's why Barney did not give it to you. Instead he gave you an array a_1, a_2, ..., a_{k} such that  $n = \prod_{i = 1}^{k} a_{i}$ 

in other words, n is multiplication of all elements of the given array.

Because of precision difficulties, Barney asked you to tell him the answer as an irreducible fraction. In other words you need to find it as a fraction p / q such that $\operatorname{gcd}(p, q) = 1$, where $gcd$ is the greatest common divisor. Since p and q can be extremely large, you only need to find the remainders of dividing each of them by 10^9 + 7.

Please note that we want $gcd$ of p and q to be 1, not $gcd$ of their remainders after dividing by 10^9 + 7.


-----Input-----

The first line of input contains a single integer k (1 ≤ k ≤ 10^5) — the number of elements in array Barney gave you.

The second line contains k integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 10^18) — the elements of the array.


-----Output-----

In the only line of output print a single string x / y where x is the remainder of dividing p by 10^9 + 7 and y is the remainder of dividing q by 10^9 + 7.


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

Output
1/2

Input
3
1 1 1

Output
0/1
user: The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.

Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 18) — the number of participants of the Sith Tournament.

Each of the next n lines contains n real numbers, which form a matrix p_{ij} (0 ≤ p_{ij} ≤ 1). Each its element p_{ij} is the probability that the i-th participant defeats the j-th in a duel.

The elements on the main diagonal p_{ii} are equal to zero. For all different i, j the equality p_{ij} + p_{ji} = 1 holds. All probabilities are given with no more than six decimal places.

Jedi Ivan is the number 1 in the list of the participants.


-----Output-----

Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed 10^{ - 6}.


-----Examples-----
Input
3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0

Output
0.680000000000000
user: Ashish has an array $a$ of size $n$.

A subsequence of $a$ is defined as a sequence that can be obtained from $a$ by deleting some elements (possibly none), without changing the order of the remaining elements.

Consider a subsequence $s$ of $a$. He defines the cost of $s$ as the minimum between:   The maximum among all elements at odd indices of $s$.  The maximum among all elements at even indices of $s$. 

Note that the index of an element is its index in $s$, rather than its index in $a$. The positions are numbered from $1$. So, the cost of $s$ is equal to $min(max(s_1, s_3, s_5, \ldots), max(s_2, s_4, s_6, \ldots))$.

For example, the cost of $\{7, 5, 6\}$ is $min( max(7, 6), max(5) ) = min(7, 5) = 5$.

Help him find the minimum cost of a subsequence of size $k$.


-----Input-----

The first line contains two integers $n$ and $k$ ($2 \leq k \leq n \leq 2 \cdot 10^5$)  — the size of the array $a$ and the size of the subsequence.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$)  — the elements of the array $a$.


-----Output-----

Output a single integer  — the minimum cost of a subsequence of size $k$.


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

Output
1
Input
4 3
1 2 3 4

Output
2
Input
5 3
5 3 4 2 6

Output
2
Input
6 4
5 3 50 2 4 5

Output
3


-----Note-----

In the first test, consider the subsequence $s$ = $\{1, 3\}$. Here the cost is equal to $min(max(1), max(3)) = 1$.

In the second test, consider the subsequence $s$ = $\{1, 2, 4\}$. Here the cost is equal to $min(max(1, 4), max(2)) = 2$.

In the fourth test, consider the subsequence $s$ = $\{3, 50, 2, 4\}$. Here the cost is equal to $min(max(3, 2), max(50, 4)) = 3$.
user: You are given a following process. 

There is a platform with $n$ columns. $1 \times 1$ squares are appearing one after another in some columns on this platform. If there are no squares in the column, a square will occupy the bottom row. Otherwise a square will appear at the top of the highest square of this column. 

When all of the $n$ columns have at least one square in them, the bottom row is being removed. You will receive $1$ point for this, and all the squares left will fall down one row. 

You task is to calculate the amount of points you will receive.


-----Input-----

The first line of input contain 2 integer numbers $n$ and $m$ ($1 \le n, m \le 1000$) — the length of the platform and the number of the squares.

The next line contain $m$ integer numbers $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n$) — column in which $i$-th square will appear.


-----Output-----

Print one integer — the amount of points you will receive.


-----Example-----
Input
3 9
1 1 2 2 2 3 1 2 3

Output
2



-----Note-----

In the sample case the answer will be equal to $2$ because after the appearing of $6$-th square will be removed one row (counts of the squares on the platform will look like $[2~ 3~ 1]$, and after removing one row will be $[1~ 2~ 0]$).

After the appearing of $9$-th square counts will be $[2~ 3~ 1]$, and after removing one row it will look like $[1~ 2~ 0]$.

So the answer will be equal to $2$.
user: Berlanders like to eat cones after a hard day. Misha Square and Sasha Circle are local authorities of Berland. Each of them controls its points of cone trade. Misha has n points, Sasha — m. Since their subordinates constantly had conflicts with each other, they decided to build a fence in the form of a circle, so that the points of trade of one businessman are strictly inside a circle, and points of the other one are strictly outside. It doesn't matter which of the two gentlemen will have his trade points inside the circle.

Determine whether they can build a fence or not.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10000), numbers of Misha's and Sasha's trade points respectively.

The next n lines contains pairs of space-separated integers M_{x}, M_{y} ( - 10^4 ≤ M_{x}, M_{y} ≤ 10^4), coordinates of Misha's trade points.

The next m lines contains pairs of space-separated integers S_{x}, S_{y} ( - 10^4 ≤ S_{x}, S_{y} ≤ 10^4), coordinates of Sasha's trade points.

It is guaranteed that all n + m points are distinct.


-----Output-----

The only output line should contain either word "YES" without quotes in case it is possible to build a such fence or word "NO" in the other case.


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

Output
NO

Input
4 4
1 0
0 1
-1 0
0 -1
1 1
-1 1
-1 -1
1 -1

Output
YES



-----Note-----

In the first sample there is no possibility to separate points, because any circle that contains both points ( - 1, 0), (1, 0) also contains at least one point from the set (0,  - 1), (0, 1), and vice-versa: any circle that contains both points (0,  - 1), (0, 1) also contains at least one point from the set ( - 1, 0), (1, 0)

In the second sample one of the possible solution is shown below. Misha's points are marked with red colour and Sasha's are marked with blue. [Image]
user: Kilani is playing a game with his friends. This game can be represented as a grid of size $n \times m$, where each cell is either empty or blocked, and every player has one or more castles in some cells (there are no two castles in one cell).

The game is played in rounds. In each round players expand turn by turn: firstly, the first player expands, then the second player expands and so on. The expansion happens as follows: for each castle the player owns now, he tries to expand into the empty cells nearby. The player $i$ can expand from a cell with his castle to the empty cell if it's possible to reach it in at most $s_i$ (where $s_i$ is player's expansion speed) moves to the left, up, right or down without going through blocked cells or cells occupied by some other player's castle. The player examines the set of cells he can expand to and builds a castle in each of them at once. The turned is passed to the next player after that. 

The game ends when no player can make a move. You are given the game field and speed of the expansion for each player. Kilani wants to know for each player how many cells he will control (have a castle their) after the game ends.


-----Input-----

The first line contains three integers $n$, $m$ and $p$ ($1 \le n, m \le 1000$, $1 \le p \le 9$) — the size of the grid and the number of players.

The second line contains $p$ integers $s_i$ ($1 \le s \le 10^9$) — the speed of the expansion for every player.

The following $n$ lines describe the game grid. Each of them consists of $m$ symbols, where '.' denotes an empty cell, '#' denotes a blocked cell and digit $x$ ($1 \le x \le p$) denotes the castle owned by player $x$.

It is guaranteed, that each player has at least one castle on the grid.


-----Output-----

Print $p$ integers — the number of cells controlled by each player after the game ends.


-----Examples-----
Input
3 3 2
1 1
1..
...
..2

Output
6 3 

Input
3 4 4
1 1 1 1
....
#...
1234

Output
1 4 3 3 



-----Note-----

The picture below show the game before it started, the game after the first round and game after the second round in the first example:

 [Image] 

In the second example, the first player is "blocked" so he will not capture new cells for the entire game. All other player will expand up during the first two rounds and in the third round only the second player will move to the left.
user: Wilbur the pig is tinkering with arrays again. He has the array a_1, a_2, ..., a_{n} initially consisting of n zeros. At one step, he can choose any index i and either add 1 to all elements a_{i}, a_{i} + 1, ... , a_{n} or subtract 1 from all elements a_{i}, a_{i} + 1, ..., a_{n}. His goal is to end up with the array b_1, b_2, ..., b_{n}. 

Of course, Wilbur wants to achieve this goal in the minimum number of steps and asks you to compute this value.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the length of the array a_{i}. Initially a_{i} = 0 for every position i, so this array is not given in the input.

The second line of the input contains n integers b_1, b_2, ..., b_{n} ( - 10^9 ≤ b_{i} ≤ 10^9).


-----Output-----

Print the minimum number of steps that Wilbur needs to make in order to achieve a_{i} = b_{i} for all i.


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

Output
5
Input
4
1 2 2 1

Output
3


-----Note-----

In the first sample, Wilbur may successively choose indices 1, 2, 3, 4, and 5, and add 1 to corresponding suffixes.

In the second sample, Wilbur first chooses indices 1 and 2 and adds 1 to corresponding suffixes, then he chooses index 4 and subtract 1.
user: Recently Polycarp noticed that some of the buttons of his keyboard are malfunctioning. For simplicity, we assume that Polycarp's keyboard contains $26$ buttons (one for each letter of the Latin alphabet). Each button is either working fine or malfunctioning. 

To check which buttons need replacement, Polycarp pressed some buttons in sequence, and a string $s$ appeared on the screen. When Polycarp presses a button with character $c$, one of the following events happened:

  if the button was working correctly, a character $c$ appeared at the end of the string Polycarp was typing;  if the button was malfunctioning, two characters $c$ appeared at the end of the string. 

For example, suppose the buttons corresponding to characters a and c are working correctly, and the button corresponding to b is malfunctioning. If Polycarp presses the buttons in the order a, b, a, c, a, b, a, then the string he is typing changes as follows: a $\rightarrow$ abb $\rightarrow$ abba $\rightarrow$ abbac $\rightarrow$ abbaca $\rightarrow$ abbacabb $\rightarrow$ abbacabba.

You are given a string $s$ which appeared on the screen after Polycarp pressed some buttons. Help Polycarp to determine which buttons are working correctly for sure (that is, this string could not appear on the screen if any of these buttons was malfunctioning).

You may assume that the buttons don't start malfunctioning when Polycarp types the string: each button either works correctly throughout the whole process, or malfunctions throughout the whole process.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases in the input.

Then the test cases follow. Each test case is represented by one line containing a string $s$ consisting of no less than $1$ and no more than $500$ lowercase Latin letters.


-----Output-----

For each test case, print one line containing a string $res$. The string $res$ should contain all characters which correspond to buttons that work correctly in alphabetical order, without any separators or repetitions. If all buttons may malfunction, $res$ should be empty.


-----Example-----
Input
4
a
zzaaz
ccff
cbddbb

Output
a
z

bc
user: You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.


-----Input-----

The first line contains two positive integers n and m (1 ≤ n, m ≤ 10^5) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates a_{i} are given in non-decreasing order.

The third line contains a sequence of m integers b_1, b_2, ..., b_{m} ( - 10^9 ≤ b_{j} ≤ 10^9) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates b_{j} are given in non-decreasing order.


-----Output-----

Print minimal r so that each city will be covered by cellular network.


-----Examples-----
Input
3 2
-2 2 4
-3 0

Output
4

Input
5 3
1 5 10 14 17
4 11 15

Output
3
user: On his trip to Luxor and Aswan, Sagheer went to a Nubian market to buy some souvenirs for his friends and relatives. The market has some strange rules. It contains n different items numbered from 1 to n. The i-th item has base cost a_{i} Egyptian pounds. If Sagheer buys k items with indices x_1, x_2, ..., x_{k}, then the cost of item x_{j} is a_{x}_{j} + x_{j}·k for 1 ≤ j ≤ k. In other words, the cost of an item is equal to its base cost in addition to its index multiplied by the factor k.

Sagheer wants to buy as many souvenirs as possible without paying more than S Egyptian pounds. Note that he cannot buy a souvenir more than once. If there are many ways to maximize the number of souvenirs, he will choose the way that will minimize the total cost. Can you help him with this task?


-----Input-----

The first line contains two integers n and S (1 ≤ n ≤ 10^5 and 1 ≤ S ≤ 10^9) — the number of souvenirs in the market and Sagheer's budget.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5) — the base costs of the souvenirs.


-----Output-----

On a single line, print two integers k, T — the maximum number of souvenirs Sagheer can buy and the minimum total cost to buy these k souvenirs.


-----Examples-----
Input
3 11
2 3 5

Output
2 11

Input
4 100
1 2 5 6

Output
4 54

Input
1 7
7

Output
0 0



-----Note-----

In the first example, he cannot take the three items because they will cost him [5, 9, 14] with total cost 28. If he decides to take only two items, then the costs will be [4, 7, 11]. So he can afford the first and second items.

In the second example, he can buy all items as they will cost him [5, 10, 17, 22].

In the third example, there is only one souvenir in the market which will cost him 8 pounds, so he cannot buy it.
user: You will receive 3 points for solving this problem.

Manao is designing the genetic code for a new type of algae to efficiently produce fuel. Specifically, Manao is focusing on a stretch of DNA that encodes one protein. The stretch of DNA is represented by a string containing only the characters 'A', 'T', 'G' and 'C'.

Manao has determined that if the stretch of DNA contains a maximal sequence of consecutive identical nucleotides that is of even length, then the protein will be nonfunctional. For example, consider a protein described by DNA string "GTTAAAG". It contains four maximal sequences of consecutive identical nucleotides: "G", "TT", "AAA", and "G". The protein is nonfunctional because sequence "TT" has even length.

Manao is trying to obtain a functional protein from the protein he currently has. Manao can insert additional nucleotides into the DNA stretch. Each additional nucleotide is a character from the set {'A', 'T', 'G', 'C'}. Manao wants to determine the minimum number of insertions necessary to make the DNA encode a functional protein.


-----Input-----

The input consists of a single line, containing a string s of length n (1 ≤ n ≤ 100). Each character of s will be from the set {'A', 'T', 'G', 'C'}.

This problem doesn't have subproblems. You will get 3 points for the correct submission.


-----Output-----

The program should print on one line a single integer representing the minimum number of 'A', 'T', 'G', 'C' characters that are required to be inserted into the input string in order to make all runs of identical characters have odd length.


-----Examples-----
Input
GTTAAAG

Output
1

Input
AACCAACCAAAAC

Output
5



-----Note-----

In the first example, it is sufficient to insert a single nucleotide of any type between the two 'T's in the sequence to restore the functionality of the protein.
user: Andrewid the Android is a galaxy-famous detective. In his free time he likes to think about strings containing zeros and ones.

Once he thought about a string of length n consisting of zeroes and ones. Consider the following operation: we choose any two adjacent positions in the string, and if one them contains 0, and the other contains 1, then we are allowed to remove these two digits from the string, obtaining a string of length n - 2 as a result.

Now Andreid thinks about what is the minimum length of the string that can remain after applying the described operation several times (possibly, zero)? Help him to calculate this number.


-----Input-----

First line of the input contains a single integer n (1 ≤ n ≤ 2·10^5), the length of the string that Andreid has.

The second line contains the string of length n consisting only from zeros and ones.


-----Output-----

Output the minimum length of the string that may remain after applying the described operations several times.


-----Examples-----
Input
4
1100

Output
0

Input
5
01010

Output
1

Input
8
11101111

Output
6



-----Note-----

In the first sample test it is possible to change the string like the following: $1100 \rightarrow 10 \rightarrow(\text{empty})$.

In the second sample test it is possible to change the string like the following: $01010 \rightarrow 010 \rightarrow 0$.

In the third sample test it is possible to change the string like the following: $11101111 \rightarrow 111111$.