meetforever/GRPO_CL huggingface dataset:
user: You are given a binary string $s$ consisting of $n$ zeros and ones.

Your task is to divide the given string into the minimum number of subsequences in such a way that each character of the string belongs to exactly one subsequence and each subsequence looks like "010101 ..." or "101010 ..." (i.e. the subsequence should not contain two adjacent zeros or ones).

Recall that a subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, subsequences of "1011101" are "0", "1", "11111", "0111", "101", "1001", but not "000", "101010" and "11100".

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $s$. The second line of the test case contains $n$ characters '0' and '1' — the string $s$.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer: in the first line print one integer $k$ ($1 \le k \le n$) — the minimum number of subsequences you can divide the string $s$ to. In the second line print $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the number of subsequence the $i$-th character of $s$ belongs to.

If there are several answers, you can print any.


-----Example-----
Input
4
4
0011
6
111111
5
10101
8
01010000

Output
2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4
user: You are given a garland consisting of $n$ lamps. States of the lamps are represented by the string $s$ of length $n$. The $i$-th character of the string $s_i$ equals '0' if the $i$-th lamp is turned off or '1' if the $i$-th lamp is turned on. You are also given a positive integer $k$.

In one move, you can choose one lamp and change its state (i.e. turn it on if it is turned off and vice versa).

The garland is called $k$-periodic if the distance between each pair of adjacent turned on lamps is exactly $k$. Consider the case $k=3$. Then garlands "00010010", "1001001", "00010" and "0" are good but garlands "00101001", "1000001" and "01001100" are not. Note that the garland is not cyclic, i.e. the first turned on lamp is not going after the last turned on lamp and vice versa.

Your task is to find the minimum number of moves you need to make to obtain $k$-periodic garland from the given one.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 25~ 000$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 10^6; 1 \le k \le n$) — the length of $s$ and the required period. The second line of the test case contains the string $s$ consisting of $n$ characters '0' and '1'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ ($\sum n \le 10^6$).


-----Output-----

For each test case, print the answer — the minimum number of moves you need to make to obtain $k$-periodic garland from the given one.


-----Example-----
Input
6
9 2
010001010
9 3
111100000
7 4
1111111
10 3
1001110101
1 1
1
1 1
0

Output
1
2
5
4
0
0
user: There is a frog staying to the left of the string $s = s_1 s_2 \ldots s_n$ consisting of $n$ characters (to be more precise, the frog initially stays at the cell $0$). Each character of $s$ is either 'L' or 'R'. It means that if the frog is staying at the $i$-th cell and the $i$-th character is 'L', the frog can jump only to the left. If the frog is staying at the $i$-th cell and the $i$-th character is 'R', the frog can jump only to the right. The frog can jump only to the right from the cell $0$.

Note that the frog can jump into the same cell twice and can perform as many jumps as it needs.

The frog wants to reach the $n+1$-th cell. The frog chooses some positive integer value $d$ before the first jump (and cannot change it later) and jumps by no more than $d$ cells at once. I.e. if the $i$-th character is 'L' then the frog can jump to any cell in a range $[max(0, i - d); i - 1]$, and if the $i$-th character is 'R' then the frog can jump to any cell in a range $[i + 1; min(n + 1; i + d)]$.

The frog doesn't want to jump far, so your task is to find the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it can jump by no more than $d$ cells at once. It is guaranteed that it is always possible to reach $n+1$ from $0$.

You have to answer $t$ independent test cases.


-----Input-----

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

The next $t$ lines describe test cases. The $i$-th test case is described as a string $s$ consisting of at least $1$ and at most $2 \cdot 10^5$ characters 'L' and 'R'.

It is guaranteed that the sum of lengths of strings over all test cases does not exceed $2 \cdot 10^5$ ($\sum |s| \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the minimum possible value of $d$ such that the frog can reach the cell $n+1$ from the cell $0$ if it jumps by no more than $d$ at once.


-----Example-----
Input
6
LRLRRLL
L
LLR
RRRR
LLLLLL
R

Output
3
2
3
1
7
1



-----Note-----

The picture describing the first test case of the example and one of the possible answers:

[Image]

In the second test case of the example, the frog can only jump directly from $0$ to $n+1$.

In the third test case of the example, the frog can choose $d=3$, jump to the cell $3$ from the cell $0$ and then to the cell $4$ from the cell $3$.

In the fourth test case of the example, the frog can choose $d=1$ and jump $5$ times to the right.

In the fifth test case of the example, the frog can only jump directly from $0$ to $n+1$.

In the sixth test case of the example, the frog can choose $d=1$ and jump $2$ times to the right.
user: You are given $n$ strings $a_1, a_2, \ldots, a_n$: all of them have the same length $m$. The strings consist of lowercase English letters.

Find any string $s$ of length $m$ such that each of the given $n$ strings differs from $s$ in at most one position. Formally, for each given string $a_i$, there is no more than one position $j$ such that $a_i[j] \ne s[j]$.

Note that the desired string $s$ may be equal to one of the given strings $a_i$, or it may differ from all the given strings.

For example, if you have the strings abac and zbab, then the answer to the problem might be the string abab, which differs from the first only by the last character, and from the second only by the first.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 100$) — the number of test cases. Then $t$ test cases follow.

Each test case starts with a line containing two positive integers $n$ ($1 \le n \le 10$) and $m$ ($1 \le m \le 10$) — the number of strings and their length.

Then follow $n$ strings $a_i$, one per line. Each of them has length $m$ and consists of lowercase English letters.


-----Output-----

Print $t$ answers to the test cases. Each answer (if it exists) is a string of length $m$ consisting of lowercase English letters. If there are several answers, print any of them. If the answer does not exist, print "-1" ("minus one", without quotes).


-----Example-----
Input
5
2 4
abac
zbab
2 4
aaaa
bbbb
3 3
baa
aaa
aab
2 2
ab
bb
3 1
a
b
c

Output
abab
-1
aaa
ab
z


-----Note-----

The first test case was explained in the statement.

In the second test case, the answer does not exist.
user: Find the minimum area of a square land on which you can place two identical rectangular $a \times b$ houses. The sides of the houses should be parallel to the sides of the desired square land.

Formally,   You are given two identical rectangles with side lengths $a$ and $b$ ($1 \le a, b \le 100$) — positive integers (you are given just the sizes, but not their positions).  Find the square of the minimum area that contains both given rectangles. Rectangles can be rotated (both or just one), moved, but the sides of the rectangles should be parallel to the sides of the desired square. 

Two rectangles can touch each other (side or corner), but cannot intersect. Rectangles can also touch the sides of the square but must be completely inside it. You can rotate the rectangles. Take a look at the examples for a better understanding.

 [Image] The picture shows a square that contains red and green rectangles. 


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10\,000$) —the number of test cases in the input. Then $t$ test cases follow.

Each test case is a line containing two integers $a$, $b$ ($1 \le a, b \le 100$) — side lengths of the rectangles.


-----Output-----

Print $t$ answers to the test cases. Each answer must be a single integer — minimal area of square land, that contains two rectangles with dimensions $a \times b$.


-----Example-----
Input
8
3 2
4 2
1 1
3 1
4 7
1 3
7 4
100 100

Output
16
16
4
9
64
9
64
40000



-----Note-----

Below are the answers for the first two test cases:  [Image]   [Image]
user: This is a hard version of the problem. In this version, the given array can contain equal elements and the constraints on $n$ are greater than in the easy version of the problem.

You are given an array $a$ of $n$ integers (the given array can contain equal elements). You can perform the following operations on array elements:  choose any index $i$ ($1 \le i \le n$) and move the element $a[i]$ to the begin of the array;  choose any index $i$ ($1 \le i \le n$) and move the element $a[i]$ to the end of the array. 

For example, if $n = 5$, $a = [4, 7, 2, 2, 9]$, then the following sequence of operations can be performed:   after performing the operation of the first type to the second element, the array $a$ will become $[7, 4, 2, 2, 9]$;  after performing the operation of the second type to the second element, the array $a$ will become $[7, 2, 2, 9, 4]$. 

You can perform operations of any type any number of times in any order.

Find the minimum total number of operations of the first and second type that will make the $a$ array sorted in non-decreasing order. In other words, what is the minimum number of operations must be performed so the array satisfies the inequalities $a[1] \le a[2] \le \ldots \le a[n]$.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array $a$.

Then follow $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — an array that needs to be sorted by the given operations. The given array can contain equal elements.

The sum of $n$ for all test cases in one test does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case output one integer — the minimum total number of operations of the first and second type, which will make the array sorted in non-decreasing order.


-----Example-----
Input
9
5
4 7 2 2 9
5
3 5 8 1 7
5
1 2 2 4 5
2
0 1
3
0 1 0
4
0 1 0 0
4
0 1 0 1
4
0 1 0 2
20
16 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9

Output
2
2
0
0
1
1
1
1
16



-----Note-----

In the first test case, you first need to move two 2, to the beginning of the array. Therefore, the desired sequence of operations: $[4, 7, 2, 2, 9] \rightarrow [2, 4, 7, 2, 9] \rightarrow [2, 2, 4, 7, 9]$.

In the second test case, you need to move the 1 to the beginning of the array, and the 8 — to the end. Therefore, the desired sequence of operations: $[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$.

In the third test case, the array is already sorted.
user: A permutation of length $n$ 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]$, $[0, 1]$, $[2, 2, 1, 4]$ are not.

There was a permutation $p[1 \dots n]$. It was merged with itself. In other words, let's take two instances of $p$ and insert elements of the second $p$ into the first maintaining relative order of elements. The result is a sequence of the length $2n$.

For example, if $p=[3, 1, 2]$ some possible results are: $[3, 1, 2, 3, 1, 2]$, $[3, 3, 1, 1, 2, 2]$, $[3, 1, 3, 1, 2, 2]$. The following sequences are not possible results of a merging: $[1, 3, 2, 1, 2, 3$], [$3, 1, 2, 3, 2, 1]$, $[3, 3, 1, 2, 2, 1]$.

For example, if $p=[2, 1]$ the possible results are: $[2, 2, 1, 1]$, $[2, 1, 2, 1]$. The following sequences are not possible results of a merging: $[1, 1, 2, 2$], [$2, 1, 1, 2]$, $[1, 2, 2, 1]$.

Your task is to restore the permutation $p$ by the given resulting sequence $a$. It is guaranteed that the answer exists and is unique.

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($1 \le n \le 50$) — the length of permutation. The second line of the test case contains $2n$ integers $a_1, a_2, \dots, a_{2n}$ ($1 \le a_i \le n$), where $a_i$ is the $i$-th element of $a$. It is guaranteed that the array $a$ represents the result of merging of some permutation $p$ with the same permutation $p$.


-----Output-----

For each test case, print the answer: $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), representing the initial permutation. It is guaranteed that the answer exists and is unique.


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

Output
1 2 
1 3 4 2 
1 2 3 4 5 
1 2 3 
2 3 4 1
user: Mishka wants to buy some food in the nearby shop. Initially, he has $s$ burles on his card. 

Mishka can perform the following operation any number of times (possibly, zero): choose some positive integer number $1 \le x \le s$, buy food that costs exactly $x$ burles and obtain $\lfloor\frac{x}{10}\rfloor$ burles as a cashback (in other words, Mishka spends $x$ burles and obtains $\lfloor\frac{x}{10}\rfloor$ back). The operation $\lfloor\frac{a}{b}\rfloor$ means $a$ divided by $b$ rounded down.

It is guaranteed that you can always buy some food that costs $x$ for any possible value of $x$.

Your task is to say the maximum number of burles Mishka can spend if he buys food optimally.

For example, if Mishka has $s=19$ burles then the maximum number of burles he can spend is $21$. Firstly, he can spend $x=10$ burles, obtain $1$ burle as a cashback. Now he has $s=10$ burles, so can spend $x=10$ burles, obtain $1$ burle as a cashback and spend it too.

You have to answer $t$ independent test cases.


-----Input-----

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

The next $t$ lines describe test cases. Each test case is given on a separate line and consists of one integer $s$ ($1 \le s \le 10^9$) — the number of burles Mishka initially has.


-----Output-----

For each test case print the answer on it — the maximum number of burles Mishka can spend if he buys food optimally.


-----Example-----
Input
6
1
10
19
9876
12345
1000000000

Output
1
11
21
10973
13716
1111111111
user: You are given an undirected unweighted connected graph consisting of $n$ vertices and $m$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to choose at most $\lfloor\frac{n}{2}\rfloor$ vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

You will be given multiple independent queries to answer.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of queries.

Then $t$ queries follow.

The first line of each query contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$) — the number of vertices and the number of edges, respectively.

The following $m$ lines denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), which are the indices of vertices connected by the edge.

There are no self-loops or multiple edges in the given graph, i. e. for each pair ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the list of edges, and for each pair ($v_i, u_i$) the condition $v_i \ne u_i$ is satisfied. It is guaranteed that the given graph is connected.

It is guaranteed that $\sum m \le 2 \cdot 10^5$ over all queries.


-----Output-----

For each query print two lines.

In the first line print $k$ ($1 \le \lfloor\frac{n}{2}\rfloor$) — the number of chosen vertices.

In the second line print $k$ distinct integers $c_1, c_2, \dots, c_k$ in any order, where $c_i$ is the index of the $i$-th chosen vertex.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.


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

Output
2
1 3
3
4 3 6



-----Note-----

In the first query any vertex or any pair of vertices will suffice.

 [Image] 

Note that you don't have to minimize the number of chosen vertices. In the second query two vertices can be enough (vertices $2$ and $4$) but three is also ok.

 [Image]
user: The only difference between easy and hard versions is the size of the input.

You are given a string $s$ consisting of $n$ characters, each character is 'R', 'G' or 'B'.

You are also given an integer $k$. Your task is to change the minimum number of characters in the initial string $s$ so that after the changes there will be a string of length $k$ that is a substring of $s$, and is also a substring of the infinite string "RGBRGBRGB ...".

A string $a$ is a substring of string $b$ if there exists a positive integer $i$ such that $a_1 = b_i$, $a_2 = b_{i + 1}$, $a_3 = b_{i + 2}$, ..., $a_{|a|} = b_{i + |a| - 1}$. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Then $q$ queries follow.

The first line of the query contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the length of the string $s$ and the length of the substring.

The second line of the query contains a string $s$ consisting of $n$ characters 'R', 'G' and 'B'.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each query print one integer — the minimum number of characters you need to change in the initial string $s$ so that after changing there will be a substring of length $k$ in $s$ that is also a substring of the infinite string "RGBRGBRGB ...".


-----Example-----
Input
3
5 2
BGGGG
5 3
RBRGR
5 5
BBBRR

Output
1
0
3



-----Note-----

In the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".

In the second example, the substring is "BRG".
user: This problem is actually a subproblem of problem G from the same contest.

There are $n$ candies in a candy box. The type of the $i$-th candy is $a_i$ ($1 \le a_i \le n$).

You have to prepare a gift using some of these candies with the following restriction: the numbers of candies of each type presented in a gift should be all distinct (i. e. for example, a gift having two candies of type $1$ and two candies of type $2$ is bad). 

It is possible that multiple types of candies are completely absent from the gift. It is also possible that not all candies of some types will be taken to a gift.

Your task is to find out the maximum possible size of the single gift you can prepare using the candies you have.

You have to answer $q$ independent queries.

If you are Python programmer, consider using PyPy instead of Python when you submit your code.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$) — the number of queries. Each query is represented by two lines.

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

The second line of each query contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the type of the $i$-th candy in the box.

It is guaranteed that the sum of $n$ over all queries does not exceed $2 \cdot 10^5$.


-----Output-----

For each query print one integer — the maximum possible size of the single gift you can compose using candies you got in this query with the restriction described in the problem statement.


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

Output
3
10
9



-----Note-----

In the first query, you can prepare a gift with two candies of type $8$ and one candy of type $5$, totalling to $3$ candies.

Note that this is not the only possible solution — taking two candies of type $4$ and one candy of type $6$ is also valid.
user: You are given an array $a$ consisting of $n$ integers.

In one move, you can choose some index $i$ ($1 \le i \le n - 2$) and shift the segment $[a_i, a_{i + 1}, a_{i + 2}]$ cyclically to the right (i.e. replace the segment $[a_i, a_{i + 1}, a_{i + 2}]$ with $[a_{i + 2}, a_i, a_{i + 1}]$). 

Your task is to sort the initial array by no more than $n^2$ such operations or say that it is impossible to do that.

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($3 \le n \le 500$) — the length of $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 500$), where $a_i$ is the $i$-th element $a$.

It is guaranteed that the sum of $n$ does not exceed $500$.


-----Output-----

For each test case, print the answer: -1 on the only line if it is impossible to sort the given array using operations described in the problem statement, or the number of operations $ans$ on the first line and $ans$ integers $idx_1, idx_2, \dots, idx_{ans}$ ($1 \le idx_i \le n - 2$), where $idx_i$ is the index of left border of the segment for the $i$-th operation. You should print indices in order of performing operations.


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

Output
0

6
3 1 3 2 2 3 
13
2 1 1 6 4 2 4 3 3 4 4 6 6 
-1
4
3 3 4 4
user: Polycarp is reading a book consisting of $n$ pages numbered from $1$ to $n$. Every time he finishes the page with the number divisible by $m$, he writes down the last digit of this page number. For example, if $n=15$ and $m=5$, pages divisible by $m$ are $5, 10, 15$. Their last digits are $5, 0, 5$ correspondingly, their sum is $10$.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 1000$) — the number of queries.

The following $q$ lines contain queries, one per line. Each query is given as two integers $n$ and $m$ ($1 \le n, m \le 10^{16}$) — the number of pages in the book and required divisor, respectively.


-----Output-----

For each query print the answer for it — the sum of digits written down by Polycarp.


-----Example-----
Input
7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13

Output
1
45
153
294
3359835
0
427262129093995