meetforever/GRPO_CL huggingface dataset:
user: Pinkie Pie has bought a bag of patty-cakes with different fillings! But it appeared that not all patty-cakes differ from one another with filling. In other words, the bag contains some patty-cakes with the same filling.

Pinkie Pie eats the patty-cakes one-by-one. She likes having fun so she decided not to simply eat the patty-cakes but to try not to eat the patty-cakes with the same filling way too often. To achieve this she wants the minimum distance between the eaten with the same filling to be the largest possible. Herein Pinkie Pie called the distance between two patty-cakes the number of eaten patty-cakes strictly between them.

Pinkie Pie can eat the patty-cakes in any order. She is impatient about eating all the patty-cakes up so she asks you to help her to count the greatest minimum distance between the eaten patty-cakes with the same filling amongst all possible orders of eating!

Pinkie Pie is going to buy more bags of patty-cakes so she asks you to solve this problem for several bags!


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$): the number of bags for which you need to solve the problem.

The first line of each bag description contains a single integer $n$ ($2 \le n \le 10^5$): the number of patty-cakes in it. The second line of the bag description contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$): the information of patty-cakes' fillings: same fillings are defined as same integers, different fillings are defined as different integers. It is guaranteed that each bag contains at least two patty-cakes with the same filling. 

It is guaranteed that the sum of $n$ over all bags does not exceed $10^5$.


-----Output-----

For each bag print in separate line one single integer: the largest minimum distance between the eaten patty-cakes with the same filling amongst all possible orders of eating for that bag.


-----Example-----
Input
4
7
1 7 1 6 4 4 6
8
1 1 4 6 4 6 4 7
3
3 3 3
6
2 5 2 3 1 4

Output
3
2
0
4



-----Note-----

For the first bag Pinkie Pie can eat the patty-cakes in the following order (by fillings): $1$, $6$, $4$, $7$, $1$, $6$, $4$ (in this way, the minimum distance is equal to $3$).

For the second bag Pinkie Pie can eat the patty-cakes in the following order (by fillings): $1$, $4$, $6$, $7$, $4$, $1$, $6$, $4$ (in this way, the minimum distance is equal to $2$).
user: Consider some positive integer $x$. Its prime factorization will be of form $x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots$

Let's call $x$ elegant if the greatest common divisor of the sequence $k_1, k_2, \dots$ is equal to $1$. For example, numbers $5 = 5^1$, $12 = 2^2 \cdot 3$, $72 = 2^3 \cdot 3^2$ are elegant and numbers $8 = 2^3$ ($GCD = 3$), $2500 = 2^2 \cdot 5^4$ ($GCD = 2$) are not.

Count the number of elegant integers from $2$ to $n$.

Each testcase contains several values of $n$, for each of them you are required to solve the problem separately.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 10^5$) — the number of values of $n$ in the testcase.

Each of the next $T$ lines contains a single integer $n_i$ ($2 \le n_i \le 10^{18}$).


-----Output-----

Print $T$ lines — the $i$-th line should contain the number of elegant numbers from $2$ to $n_i$.


-----Example-----
Input
4
4
2
72
10

Output
2
1
61
6



-----Note-----

Here is the list of non-elegant numbers up to $10$:

  $4 = 2^2, GCD = 2$;  $8 = 2^3, GCD = 3$;  $9 = 3^2, GCD = 2$. 

The rest have $GCD = 1$.
user: There are $n$ piles of stones, where the $i$-th pile has $a_i$ stones. Two people play a game, where they take alternating turns removing stones.

In a move, a player may remove a positive number of stones from the first non-empty pile (the pile with the minimal index, that has at least one stone). The first player who cannot make a move (because all piles are empty) loses the game. If both players play optimally, determine the winner of the game.


-----Input-----

The first line contains a single integer $t$ ($1\le t\le 1000$)  — the number of test cases. Next $2t$ lines contain descriptions of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 10^5$)  — the number of piles.

The second line of each test case contains $n$ integers $a_1,\ldots,a_n$ ($1\le a_i\le 10^9$)  — $a_i$ is equal to the number of stones in the $i$-th pile.

It is guaranteed that the sum of $n$ for all test cases does not exceed $10^5$.


-----Output-----

For each test case, if the player who makes the first move will win, output "First". Otherwise, output "Second".


-----Example-----
Input
7
3
2 5 4
8
1 1 1 1 1 1 1 1
6
1 2 3 4 5 6
6
1 1 2 1 2 2
1
1000000000
5
1 2 2 1 1
3
1 1 1

Output
First
Second
Second
First
First
Second
First



-----Note-----

In the first test case, the first player will win the game. His winning strategy is:   The first player should take the stones from the first pile. He will take $1$ stone. The numbers of stones in piles will be $[1, 5, 4]$.  The second player should take the stones from the first pile. He will take $1$ stone because he can't take any other number of stones. The numbers of stones in piles will be $[0, 5, 4]$.  The first player should take the stones from the second pile because the first pile is empty. He will take $4$ stones. The numbers of stones in piles will be $[0, 1, 4]$.  The second player should take the stones from the second pile because the first pile is empty. He will take $1$ stone because he can't take any other number of stones. The numbers of stones in piles will be $[0, 0, 4]$.  The first player should take the stones from the third pile because the first and second piles are empty. He will take $4$ stones. The numbers of stones in piles will be $[0, 0, 0]$.  The second player will lose the game because all piles will be empty.
user: Phoenix has decided to become a scientist! He is currently investigating the growth of bacteria.

Initially, on day $1$, there is one bacterium with mass $1$.

Every day, some number of bacteria will split (possibly zero or all). When a bacterium of mass $m$ splits, it becomes two bacteria of mass $\frac{m}{2}$ each. For example, a bacterium of mass $3$ can split into two bacteria of mass $1.5$.

Also, every night, the mass of every bacteria will increase by one.

Phoenix is wondering if it is possible for the total mass of all the bacteria to be exactly $n$. If it is possible, he is interested in the way to obtain that mass using the minimum possible number of nights. Help him become the best scientist!


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^9$) — the sum of bacteria masses that Phoenix is interested in. 


-----Output-----

For each test case, if there is no way for the bacteria to exactly achieve total mass $n$, print -1. Otherwise, print two lines.

The first line should contain an integer $d$  — the minimum number of nights needed.

The next line should contain $d$ integers, with the $i$-th integer representing the number of bacteria that should split on the $i$-th day.

If there are multiple solutions, print any.


-----Example-----
Input
3
9
11
2

Output
3
1 0 2 
3
1 1 2
1
0 


-----Note-----

In the first test case, the following process results in bacteria with total mass $9$:   Day $1$: The bacterium with mass $1$ splits. There are now two bacteria with mass $0.5$ each.  Night $1$: All bacteria's mass increases by one. There are now two bacteria with mass $1.5$.  Day $2$: None split.  Night $2$: There are now two bacteria with mass $2.5$.  Day $3$: Both bacteria split. There are now four bacteria with mass $1.25$.  Night $3$: There are now four bacteria with mass $2.25$.  The total mass is $2.25+2.25+2.25+2.25=9$. It can be proved that $3$ is the minimum number of nights needed. There are also other ways to obtain total mass 9 in 3 nights.

$ $

In the second test case, the following process results in bacteria with total mass $11$:   Day $1$: The bacterium with mass $1$ splits. There are now two bacteria with mass $0.5$.  Night $1$: There are now two bacteria with mass $1.5$.  Day $2$: One bacterium splits. There are now three bacteria with masses $0.75$, $0.75$, and $1.5$.  Night $2$: There are now three bacteria with masses $1.75$, $1.75$, and $2.5$.  Day $3$: The bacteria with mass $1.75$ and the bacteria with mass $2.5$ split. There are now five bacteria with masses $0.875$, $0.875$, $1.25$, $1.25$, and $1.75$.  Night $3$: There are now five bacteria with masses $1.875$, $1.875$, $2.25$, $2.25$, and $2.75$.  The total mass is $1.875+1.875+2.25+2.25+2.75=11$. It can be proved that $3$ is the minimum number of nights needed. There are also other ways to obtain total mass 11 in 3 nights.

$ $

In the third test case, the bacterium does not split on day $1$, and then grows to mass $2$ during night $1$.
user: The Cartesian coordinate system is set in the sky. There you can see n stars, the i-th has coordinates (x_{i}, y_{i}), a maximum brightness c, equal for all stars, and an initial brightness s_{i} (0 ≤ s_{i} ≤ c).

Over time the stars twinkle. At moment 0 the i-th star has brightness s_{i}. Let at moment t some star has brightness x. Then at moment (t + 1) this star will have brightness x + 1, if x + 1 ≤ c, and 0, otherwise.

You want to look at the sky q times. In the i-th time you will look at the moment t_{i} and you will see a rectangle with sides parallel to the coordinate axes, the lower left corner has coordinates (x_1i, y_1i) and the upper right — (x_2i, y_2i). For each view, you want to know the total brightness of the stars lying in the viewed rectangle.

A star lies in a rectangle if it lies on its border or lies strictly inside it.


-----Input-----

The first line contains three integers n, q, c (1 ≤ n, q ≤ 10^5, 1 ≤ c ≤ 10) — the number of the stars, the number of the views and the maximum brightness of the stars.

The next n lines contain the stars description. The i-th from these lines contains three integers x_{i}, y_{i}, s_{i} (1 ≤ x_{i}, y_{i} ≤ 100, 0 ≤ s_{i} ≤ c ≤ 10) — the coordinates of i-th star and its initial brightness.

The next q lines contain the views description. The i-th from these lines contains five integers t_{i}, x_1i, y_1i, x_2i, y_2i (0 ≤ t_{i} ≤ 10^9, 1 ≤ x_1i < x_2i ≤ 100, 1 ≤ y_1i < y_2i ≤ 100) — the moment of the i-th view and the coordinates of the viewed rectangle.


-----Output-----

For each view print the total brightness of the viewed stars.


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

Output
3
0
3

Input
3 4 5
1 1 2
2 3 0
3 3 1
0 1 1 100 100
1 2 2 4 4
2 2 1 4 7
1 50 50 51 51

Output
3
3
5
0



-----Note-----

Let's consider the first example.

At the first view, you can see only the first star. At moment 2 its brightness is 3, so the answer is 3.

At the second view, you can see only the second star. At moment 0 its brightness is 0, so the answer is 0.

At the third view, you can see both stars. At moment 5 brightness of the first is 2, and brightness of the second is 1, so the answer is 3.
user: A permutation is a sequence of integers from $1$ to $n$ of length $n$ containing each number exactly once. For example, $[1]$, $[4, 3, 5, 1, 2]$, $[3, 2, 1]$ — are permutations, and $[1, 1]$, $[4, 3, 1]$, $[2, 3, 4]$ — no.

Permutation $a$ is lexicographically smaller than permutation $b$ (they have the same length $n$), if in the first index $i$ in which they differ, $a[i] < b[i]$. For example, the permutation $[1, 3, 2, 4]$ is lexicographically smaller than the permutation $[1, 3, 4, 2]$, because the first two elements are equal, and the third element in the first permutation is smaller than in the second.

The next permutation for a permutation $a$ of length $n$ — is the lexicographically smallest permutation $b$ of length $n$ that lexicographically larger than $a$. For example:   for permutation $[2, 1, 4, 3]$ the next permutation is $[2, 3, 1, 4]$;  for permutation $[1, 2, 3]$ the next permutation is $[1, 3, 2]$;  for permutation $[2, 1]$ next permutation does not exist. 

You are given the number $n$ — the length of the initial permutation. The initial permutation has the form $a = [1, 2, \ldots, n]$. In other words, $a[i] = i$ ($1 \le i \le n$).

You need to process $q$ queries of two types:   $1$ $l$ $r$: query for the sum of all elements on the segment $[l, r]$. More formally, you need to find $a[l] + a[l + 1] + \ldots + a[r]$.  $2$ $x$: $x$ times replace the current permutation with the next permutation. For example, if $x=2$ and the current permutation has the form $[1, 3, 4, 2]$, then we should perform such a chain of replacements $[1, 3, 4, 2] \rightarrow [1, 4, 2, 3] \rightarrow [1, 4, 3, 2]$. 

For each query of the $1$-st type output the required sum.


-----Input-----

The first line contains two integers $n$ ($2 \le n \le 2 \cdot 10^5$) and $q$ ($1 \le q \le 2 \cdot 10^5$), where $n$ — the length of the initial permutation, and $q$ — the number of queries.

The next $q$ lines contain a single query of the $1$-st or $2$-nd type. The $1$-st type query consists of three integers $1$, $l$ and $r$ $(1 \le l \le r \le n)$, the $2$-nd type query consists of two integers $2$ and $x$ $(1 \le x \le 10^5)$.

It is guaranteed that all requests of the $2$-nd type are possible to process.


-----Output-----

For each query of the $1$-st type, output on a separate line one integer — the required sum.


-----Example-----
Input
4 4
1 2 4
2 3
1 1 2
1 3 4

Output
9
4
6



-----Note-----

Initially, the permutation has the form $[1, 2, 3, 4]$. Queries processing is as follows:   $2 + 3 + 4 = 9$;  $[1, 2, 3, 4] \rightarrow [1, 2, 4, 3] \rightarrow [1, 3, 2, 4] \rightarrow [1, 3, 4, 2]$;  $1 + 3 = 4$;  $4 + 2 = 6$
user: Gildong is playing a video game called Block Adventure. In Block Adventure, there are $n$ columns of blocks in a row, and the columns are numbered from $1$ to $n$. All blocks have equal heights. The height of the $i$-th column is represented as $h_i$, which is the number of blocks stacked in the $i$-th column.

Gildong plays the game as a character that can stand only on the top of the columns. At the beginning, the character is standing on the top of the $1$-st column. The goal of the game is to move the character to the top of the $n$-th column.

The character also has a bag that can hold infinitely many blocks. When the character is on the top of the $i$-th column, Gildong can take one of the following three actions as many times as he wants:   if there is at least one block on the column, remove one block from the top of the $i$-th column and put it in the bag;  if there is at least one block in the bag, take one block out of the bag and place it on the top of the $i$-th column;  if $i < n$ and $|h_i - h_{i+1}| \le k$, move the character to the top of the $i+1$-st column. $k$ is a non-negative integer given at the beginning of the game. Note that it is only possible to move to the next column. 

In actions of the first two types the character remains in the $i$-th column, and the value $h_i$ changes.

The character initially has $m$ blocks in the bag. Gildong wants to know if it is possible to win the game. Help Gildong find the answer to his question.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 100$, $0 \le m \le 10^6$, $0 \le k \le 10^6$) — the number of columns in the game, the number of blocks in the character's bag at the beginning, and the non-negative integer $k$ described in the statement.

The second line of each test case contains $n$ integers. The $i$-th integer is $h_i$ ($0 \le h_i \le 10^6$), the initial height of the $i$-th column.


-----Output-----

For each test case, print "YES" if it is possible to win the game. Otherwise, print "NO".

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


-----Example-----
Input
5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99

Output
YES
NO
YES
NO
YES



-----Note-----

In the first case, Gildong can take one block from the $1$-st column, move to the $2$-nd column, put the block on the $2$-nd column, then move to the $3$-rd column.

In the second case, Gildong has to put the block in his bag on the $1$-st column to get to the $2$-nd column. But it is impossible to get to the $3$-rd column because $|h_2 - h_3| = 3 > k$ and there is no way to decrease the gap.

In the fifth case, the character is already on the $n$-th column from the start so the game is won instantly.
user: The stardate is 1983, and Princess Heidi is getting better at detecting the Death Stars. This time, two Rebel spies have yet again given Heidi two maps with the possible locations of the Death Star. Since she got rid of all double agents last time, she knows that both maps are correct, and indeed show the map of the solar system that contains the Death Star. However, this time the Empire has hidden the Death Star very well, and Heidi needs to find a place that appears on both maps in order to detect the Death Star.

The first map is an N × M grid, each cell of which shows some type of cosmic object that is present in the corresponding quadrant of space. The second map is an M × N grid. Heidi needs to align those two maps in such a way that they overlap over some M × M section in which all cosmic objects are identical. Help Heidi by identifying where such an M × M section lies within both maps.


-----Input-----

The first line of the input contains two space-separated integers N and M (1 ≤ N ≤ 2000, 1 ≤ M ≤ 200, M ≤ N). The next N lines each contain M lower-case Latin characters (a-z), denoting the first map. Different characters correspond to different cosmic object types. The next M lines each contain N characters, describing the second map in the same format. 


-----Output-----

The only line of the output should contain two space-separated integers i and j, denoting that the section of size M × M in the first map that starts at the i-th row is equal to the section of the second map that starts at the j-th column. Rows and columns are numbered starting from 1.

If there are several possible ways to align the maps, Heidi will be satisfied with any of those. It is guaranteed that a solution exists.


-----Example-----
Input
10 5
somer
andom
noise
mayth
eforc
ebewi
thyou
hctwo
again
noise
somermayth
andomeforc
noiseebewi
againthyou
noisehctwo

Output
4 6



-----Note-----

The 5-by-5 grid for the first test case looks like this: 

mayth

eforc

ebewi

thyou

hctwo
user: Phoenix has a string $s$ consisting of lowercase Latin letters. He wants to distribute all the letters of his string into $k$ non-empty strings $a_1, a_2, \dots, a_k$ such that every letter of $s$ goes to exactly one of the strings $a_i$. The strings $a_i$ do not need to be substrings of $s$. Phoenix can distribute letters of $s$ and rearrange the letters within each string $a_i$ however he wants.

For example, if $s = $ baba and $k=2$, Phoenix may distribute the letters of his string in many ways, such as:   ba and ba  a and abb  ab and ab  aa and bb 

But these ways are invalid:   baa and ba  b and ba  baba and empty string ($a_i$ should be non-empty) 

Phoenix wants to distribute the letters of his string $s$ into $k$ strings $a_1, a_2, \dots, a_k$ to minimize the lexicographically maximum string among them, i. e. minimize $max(a_1, a_2, \dots, a_k)$. Help him find the optimal distribution and print the minimal possible value of $max(a_1, a_2, \dots, a_k)$.

String $x$ is lexicographically less than string $y$ if either $x$ is a prefix of $y$ and $x \ne y$, or there exists an index $i$ ($1 \le i \le min(|x|, |y|))$ such that $x_i$ < $y_i$ and for every $j$ $(1 \le j < i)$ $x_j = y_j$. Here $|x|$ denotes the length of the string $x$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. Each test case consists of two lines.

The first line of each test case consists of two integers $n$ and $k$ ($1 \le k \le n \le 10^5$) — the length of string $s$ and the number of non-empty strings, into which Phoenix wants to distribute letters of $s$, respectively.

The second line of each test case contains a string $s$ of length $n$ consisting only of lowercase Latin letters.

It is guaranteed that the sum of $n$ over all test cases is $\le 10^5$.


-----Output-----

Print $t$ answers — one per test case. The $i$-th answer should be the minimal possible value of $max(a_1, a_2, \dots, a_k)$ in the $i$-th test case.


-----Example-----
Input
6
4 2
baba
5 2
baacb
5 3
baacb
5 3
aaaaa
6 4
aaxxzz
7 1
phoenix

Output
ab
abbc
b
aa
x
ehinopx



-----Note-----

In the first test case, one optimal solution is to distribute baba into ab and ab. 

In the second test case, one optimal solution is to distribute baacb into abbc and a.

In the third test case, one optimal solution is to distribute baacb into ac, ab, and b.

In the fourth test case, one optimal solution is to distribute aaaaa into aa, aa, and a.

In the fifth test case, one optimal solution is to distribute aaxxzz into az, az, x, and x.

In the sixth test case, one optimal solution is to distribute phoenix into ehinopx.
user: You are given an array of $n$ integers $a_1, a_2, \ldots, a_n$.

You will perform $q$ operations. In the $i$-th operation, you have a symbol $s_i$ which is either "<" or ">" and a number $x_i$.

You make a new array $b$ such that $b_j = -a_j$ if $a_j s_i x_i$ and $b_j = a_j$ otherwise (i.e. if $s_i$ is '>', then all $a_j > x_i$ will be flipped). After doing all these replacements, $a$ is set to be $b$.

You want to know what your final array looks like after all operations.


-----Input-----

The first line contains two integers $n,q$ ($1 \leq n,q \leq 10^5$) — the number of integers and the number of queries.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^5 \leq a_i \leq 10^5$) — the numbers.

Each of the next $q$ lines contains a character and an integer $s_i, x_i$. ($s_i \in \{<, >\}, -10^5 \leq x_i \leq 10^5$) – the queries.


-----Output-----

Print $n$ integers $c_1, c_2, \ldots, c_n$ representing the array after all operations.


-----Examples-----
Input
11 3
-5 -4 -3 -2 -1 0 1 2 3 4 5
> 2
> -4
< 5

Output
5 4 -3 -2 -1 0 1 2 -3 4 5

Input
5 5
0 1 -2 -1 2
< -2
< -1
< 0
< 1
< 2

Output
0 -1 2 -1 2



-----Note-----

In the first example, the array goes through the following changes:   Initial: $[-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]$  $> 2$: $[-5, -4, -3, -2, -1, 0, 1, 2, -3, -4, -5]$  $> -4$: $[-5, -4, 3, 2, 1, 0, -1, -2, 3, -4, -5]$  $< 5$: $[5, 4, -3, -2, -1, 0, 1, 2, -3, 4, 5]$
user: Today at the lesson of mathematics, Petya learns about the digital root.

The digital root of a non-negative integer is the single digit value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute a digit sum. The process continues until a single-digit number is reached. 

Let's denote the digital root of $x$ as $S(x)$. Then $S(5)=5$, $S(38)=S(3+8=11)=S(1+1=2)=2$, $S(10)=S(1+0=1)=1$.

As a homework Petya got $n$ tasks of the form: find $k$-th positive number whose digital root is $x$.

Petya has already solved all the problems, but he doesn't know if it's right. Your task is to solve all $n$ tasks from Petya's homework.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^3$) — the number of tasks in Petya's homework. The next $n$ lines contain two integers $k_i$ ($1 \le k_i \le 10^{12}$) and $x_i$ ($1 \le x_i \le 9$) — $i$-th Petya's task in which you need to find a $k_i$-th positive number, the digital root of which is $x_i$.


-----Output-----

Output $n$ lines, $i$-th line should contain a single integer — the answer to the $i$-th problem.


-----Example-----
Input
3
1 5
5 2
3 1

Output
5
38
19