meetforever/GRPO_CL huggingface dataset:
user: There are $n$ positive integers $a_1, a_2, \dots, a_n$. For the one move you can choose any even value $c$ and divide by two all elements that equal $c$.

For example, if $a=[6,8,12,6,3,12]$ and you choose $c=6$, and $a$ is transformed into $a=[3,8,12,3,3,12]$ after the move.

You need to find the minimal number of moves for transforming $a$ to an array of only odd integers (each element shouldn't be divisible by $2$).


-----Input-----

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

The first line of a test case contains $n$ ($1 \le n \le 2\cdot10^5$) — the number of integers in the sequence $a$. The second line contains positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The sum of $n$ for all test cases in the input doesn't exceed $2\cdot10^5$.


-----Output-----

For $t$ test cases print the answers in the order of test cases in the input. The answer for the test case is the minimal number of moves needed to make all numbers in the test case odd (i.e. not divisible by $2$).


-----Example-----
Input
4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7

Output
4
10
4
0



-----Note-----

In the first test case of the example, the optimal sequence of moves can be as follows:

  before making moves $a=[40, 6, 40, 3, 20, 1]$;  choose $c=6$;  now $a=[40, 3, 40, 3, 20, 1]$;  choose $c=40$;  now $a=[20, 3, 20, 3, 20, 1]$;  choose $c=20$;  now $a=[10, 3, 10, 3, 10, 1]$;  choose $c=10$;  now $a=[5, 3, 5, 3, 5, 1]$ — all numbers are odd. 

Thus, all numbers became odd after $4$ moves. In $3$ or fewer moves, you cannot make them all odd.
user: Acacius is studying strings theory. Today he came with the following problem.

You are given a string $s$ of length $n$ consisting of lowercase English letters and question marks. It is possible to replace question marks with lowercase English letters in such a way that a string "abacaba" occurs as a substring in a resulting string exactly once?

Each question mark should be replaced with exactly one lowercase English letter. For example, string "a?b?c" can be transformed into strings "aabbc" and "azbzc", but can't be transformed into strings "aabc", "a?bbc" and "babbc".

Occurrence of a string $t$ of length $m$ in the string $s$ of length $n$ as a substring is a index $i$ ($1 \leq i \leq n - m + 1$) such that string $s[i..i+m-1]$ consisting of $m$ consecutive symbols of $s$ starting from $i$-th equals to string $t$. For example string "ababa" has two occurrences of a string "aba" as a substring with $i = 1$ and $i = 3$, but there are no occurrences of a string "aba" in the string "acba" as a substring.

Please help Acacius to check if it is possible to replace all question marks with lowercase English letters in such a way that a string "abacaba" occurs as a substring in a resulting string exactly once.


-----Input-----

First line of input contains an integer $T$ ($1 \leq T \leq 5000$), number of test cases. $T$ pairs of lines with test case descriptions follow.

The first line of a test case description contains a single integer $n$ ($7 \leq n \leq 50$), length of a string $s$.

The second line of a test case description contains string $s$ of length $n$ consisting of lowercase English letters and question marks.


-----Output-----

For each test case output an answer for it.

In case if there is no way to replace question marks in string $s$ with a lowercase English letters in such a way that there is exactly one occurrence of a string "abacaba" in the resulting string as a substring output "No".

Otherwise output "Yes" and in the next line output a resulting string consisting of $n$ lowercase English letters. If there are multiple possible strings, output any.

You may print every letter in "Yes" and "No" in any case you want (so, for example, the strings yEs, yes, Yes, and YES will all be recognized as positive answer).


-----Example-----
Input
6
7
abacaba
7
???????
11
aba?abacaba
11
abacaba?aba
15
asdf???f???qwer
11
abacabacaba

Output
Yes
abacaba
Yes
abacaba
Yes
abadabacaba
Yes
abacabadaba
No
No



-----Note-----

In first example there is exactly one occurrence of a string "abacaba" in the string "abacaba" as a substring.

In second example seven question marks can be replaced with any seven lowercase English letters and with "abacaba" in particular.

In sixth example there are two occurrences of a string "abacaba" as a substring.
user: You are given an array $a$ consisting of $n$ integers numbered from $1$ to $n$.

Let's define the $k$-amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $k$ (recall that a subsegment of $a$ of length $k$ is a contiguous part of $a$ containing exactly $k$ elements). If there is no integer occuring in all subsegments of length $k$ for some value of $k$, then the $k$-amazing number is $-1$.

For each $k$ from $1$ to $n$ calculate the $k$-amazing number of the array $a$.


-----Input-----

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

The first line of each test case contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the number of elements in the array. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the elements of the array. 

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


-----Output-----

For each test case print $n$ integers, where the $i$-th integer is equal to the $i$-amazing number of the array.


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

Output
-1 -1 3 2 1 
-1 4 4 4 2 
-1 -1 1 1 1 1
user: You are given a string $s$ of even length $n$. String $s$ is binary, in other words, consists only of 0's and 1's.

String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones ($n$ is even).

In one operation you can reverse any substring of $s$. A substring of a string is a contiguous subsequence of that string.

What is the minimum number of operations you need to make string $s$ alternating? A string is alternating if $s_i \neq s_{i + 1}$ for all $i$. There are two types of alternating strings in general: 01010101... or 10101010...


-----Input-----

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

The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$; $n$ is even) — the length of string $s$.

The second line of each test case contains a binary string $s$ of length $n$ ($s_i \in$ {0, 1}). String $s$ has exactly $\frac{n}{2}$ zeroes and $\frac{n}{2}$ ones.

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


-----Output-----

For each test case, print the minimum number of operations to make $s$ alternating.


-----Example-----
Input
3
2
10
4
0110
8
11101000

Output
0
1
2



-----Note-----

In the first test case, string 10 is already alternating.

In the second test case, we can, for example, reverse the last two elements of $s$ and get: 0110 $\rightarrow$ 0101.

In the third test case, we can, for example, make the following two operations:   11101000 $\rightarrow$ 10101100;  10101100 $\rightarrow$ 10101010.
user: Skier rides on a snowy field. Its movements can be described by a string of characters 'S', 'N', 'W', 'E' (which correspond to $1$ meter movement in the south, north, west or east direction respectively).

It is known that if he moves along a previously unvisited segment of a path (i.e. this segment of the path is visited the first time), then the time of such movement is $5$ seconds. If he rolls along previously visited segment of a path (i.e., this segment of the path has been covered by his path before), then it takes $1$ second.

Find the skier's time to roll all the path.


-----Input-----

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

Each set is given by one nonempty string of the characters 'S', 'N', 'W', 'E'. The length of the string does not exceed $10^5$ characters.

The sum of the lengths of $t$ given lines over all test cases in the input does not exceed $10^5$.


-----Output-----

For each test case, print the desired path time in seconds.


-----Example-----
Input
5
NNN
NS
WWEN
WWEE
NWNWS

Output
15
6
16
12
25
user: Lately, Mr. Chanek frequently plays the game Arena of Greed. As the name implies, the game's goal is to find the greediest of them all, who will then be crowned king of Compfestnesia.

The game is played by two people taking turns, where Mr. Chanek takes the first turn. Initially, there is a treasure chest containing $N$ gold coins. The game ends if there are no more gold coins in the chest. In each turn, the players can make one of the following moves:  Take one gold coin from the chest.  Take half of the gold coins on the chest. This move is only available if the number of coins in the chest is even. 

Both players will try to maximize the number of coins they have. Mr. Chanek asks your help to find the maximum number of coins he can get at the end of the game if both he and the opponent plays optimally.


-----Input-----

The first line contains a single integer $T$ $(1 \le T \le 10^5)$ denotes the number of test cases.

The next $T$ lines each contain a single integer $N$ $(1 \le N \le 10^{18})$.


-----Output-----

$T$ lines, each line is the answer requested by Mr. Chanek.


-----Example-----
Input
2
5
6

Output
2
4



-----Note-----

For the first case, the game is as follows:   Mr. Chanek takes one coin.  The opponent takes two coins.  Mr. Chanek takes one coin.  The opponent takes one coin. 

For the second case, the game is as follows:   Mr. Chanek takes three coins.  The opponent takes one coin.  Mr. Chanek takes one coin.  The opponent takes one coin.
user: Numbers $1, 2, 3, \dots n$ (each integer from $1$ to $n$ once) are written on a board. In one operation you can erase any two numbers $a$ and $b$ from the board and write one integer $\frac{a + b}{2}$ rounded up instead.

You should perform the given operation $n - 1$ times and make the resulting number that will be left on the board as small as possible. 

For example, if $n = 4$, the following course of action is optimal:  choose $a = 4$ and $b = 2$, so the new number is $3$, and the whiteboard contains $[1, 3, 3]$;  choose $a = 3$ and $b = 3$, so the new number is $3$, and the whiteboard contains $[1, 3]$;  choose $a = 1$ and $b = 3$, so the new number is $2$, and the whiteboard contains $[2]$. 

It's easy to see that after $n - 1$ operations, there will be left only one number. Your goal is to minimize it.


-----Input-----

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

The only line of each test case contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of integers written on the board initially.

It's guaranteed that the total sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each test case, in the first line, print the minimum possible number left on the board after $n - 1$ operations. Each of the next $n - 1$ lines should contain two integers — numbers $a$ and $b$ chosen and erased in each operation.


-----Example-----
Input
1
4

Output
2
2 4
3 3
3 1
user: You have a large electronic screen which can display up to $998244353$ decimal digits. The digits are displayed in the same way as on different electronic alarm clocks: each place for a digit consists of $7$ segments which can be turned on and off to compose different digits. The following picture describes how you can display all $10$ decimal digits:

[Image]

As you can see, different digits may require different number of segments to be turned on. For example, if you want to display $1$, you have to turn on $2$ segments of the screen, and if you want to display $8$, all $7$ segments of some place to display a digit should be turned on.

You want to display a really large integer on the screen. Unfortunately, the screen is bugged: no more than $n$ segments can be turned on simultaneously. So now you wonder what is the greatest integer that can be displayed by turning on no more than $n$ segments.

Your program should be able to process $t$ different test cases.


-----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 of them is represented by a separate line containing one integer $n$ ($2 \le n \le 10^5$) — the maximum number of segments that can be turned on in the corresponding testcase.

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


-----Output-----

For each test case, print the greatest integer that can be displayed by turning on no more than $n$ segments of the screen. Note that the answer may not fit in the standard $32$-bit or $64$-bit integral data type.


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

Output
7
11
user: Young wilderness explorers set off to their first expedition led by senior explorer Russell. Explorers went into a forest, set up a camp and decided to split into groups to explore as much interesting locations as possible. Russell was trying to form groups, but ran into some difficulties...

Most of the young explorers are inexperienced, and sending them alone would be a mistake. Even Russell himself became senior explorer not long ago. Each of young explorers has a positive integer parameter $e_i$ — his inexperience. Russell decided that an explorer with inexperience $e$ can only join the group of $e$ or more people.

Now Russell needs to figure out how many groups he can organize. It's not necessary to include every explorer in one of the groups: some can stay in the camp. Russell is worried about this expedition, so he asked you to help him.


-----Input-----

The first line contains the number of independent test cases $T$($1 \leq T \leq 2 \cdot 10^5$). Next $2T$ lines contain description of test cases.

The first line of description of each test case contains the number of young explorers $N$ ($1 \leq N \leq 2 \cdot 10^5$).

The second line contains $N$ integers $e_1, e_2, \ldots, e_N$ ($1 \leq e_i \leq N$), where $e_i$ is the inexperience of the $i$-th explorer.

It's guaranteed that sum of all $N$ doesn't exceed $3 \cdot 10^5$.


-----Output-----

Print $T$ numbers, each number on a separate line.

In $i$-th line print the maximum number of groups Russell can form in $i$-th test case.


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

Output
3
2



-----Note-----

In the first example we can organize three groups. There will be only one explorer in each group. It's correct because inexperience of each explorer equals to $1$, so it's not less than the size of his group.

In the second example we can organize two groups. Explorers with inexperience $1$, $2$ and $3$ will form the first group, and the other two explorers with inexperience equal to $2$ will form the second group.

This solution is not unique. For example, we can form the first group using the three explorers with inexperience equal to $2$, and the second group using only one explorer with inexperience equal to $1$. In this case the young explorer with inexperience equal to $3$ will not be included in any group.
user: It is lunch time for Mole. His friend, Marmot, prepared him a nice game for lunch.

Marmot brought Mole n ordered piles of worms such that i-th pile contains a_{i} worms. He labeled all these worms with consecutive integers: worms in first pile are labeled with numbers 1 to a_1, worms in second pile are labeled with numbers a_1 + 1 to a_1 + a_2 and so on. See the example for a better understanding.

Mole can't eat all the worms (Marmot brought a lot) and, as we all know, Mole is blind, so Marmot tells him the labels of the best juicy worms. Marmot will only give Mole a worm if Mole says correctly in which pile this worm is contained.

Poor Mole asks for your help. For all juicy worms said by Marmot, tell Mole the correct answers.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5), the number of piles.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^3, a_1 + a_2 + ... + a_{n} ≤ 10^6), where a_{i} is the number of worms in the i-th pile.

The third line contains single integer m (1 ≤ m ≤ 10^5), the number of juicy worms said by Marmot.

The fourth line contains m integers q_1, q_2, ..., q_{m} (1 ≤ q_{i} ≤ a_1 + a_2 + ... + a_{n}), the labels of the juicy worms.


-----Output-----

Print m lines to the standard output. The i-th line should contain an integer, representing the number of the pile where the worm labeled with the number q_{i} is.


-----Examples-----
Input
5
2 7 3 4 9
3
1 25 11

Output
1
5
3



-----Note-----

For the sample input:

  The worms with labels from [1, 2] are in the first pile.  The worms with labels from [3, 9] are in the second pile.  The worms with labels from [10, 12] are in the third pile.  The worms with labels from [13, 16] are in the fourth pile.  The worms with labels from [17, 25] are in the fifth pile.
user: After a long party Petya decided to return home, but he turned out to be at the opposite end of the town from his home. There are $n$ crossroads in the line in the town, and there is either the bus or the tram station at each crossroad.

The crossroads are represented as a string $s$ of length $n$, where $s_i = \texttt{A}$, if there is a bus station at $i$-th crossroad, and $s_i = \texttt{B}$, if there is a tram station at $i$-th crossroad. Currently Petya is at the first crossroad (which corresponds to $s_1$) and his goal is to get to the last crossroad (which corresponds to $s_n$).

If for two crossroads $i$ and $j$ for all crossroads $i, i+1, \ldots, j-1$ there is a bus station, one can pay $a$ roubles for the bus ticket, and go from $i$-th crossroad to the $j$-th crossroad by the bus (it is not necessary to have a bus station at the $j$-th crossroad). Formally, paying $a$ roubles Petya can go from $i$ to $j$ if $s_t = \texttt{A}$ for all $i \le t < j$. 

If for two crossroads $i$ and $j$ for all crossroads $i, i+1, \ldots, j-1$ there is a tram station, one can pay $b$ roubles for the tram ticket, and go from $i$-th crossroad to the $j$-th crossroad by the tram (it is not necessary to have a tram station at the $j$-th crossroad). Formally, paying $b$ roubles Petya can go from $i$ to $j$ if $s_t = \texttt{B}$ for all $i \le t < j$.

For example, if $s$="AABBBAB", $a=4$ and $b=3$ then Petya needs:[Image]  buy one bus ticket to get from $1$ to $3$,  buy one tram ticket to get from $3$ to $6$,  buy one bus ticket to get from $6$ to $7$. 

Thus, in total he needs to spend $4+3+4=11$ roubles. Please note that the type of the stop at the last crossroad (i.e. the character $s_n$) does not affect the final expense.

Now Petya is at the first crossroad, and he wants to get to the $n$-th crossroad. After the party he has left with $p$ roubles. He's decided to go to some station on foot, and then go to home using only public transport.

Help him to choose the closest crossroad $i$ to go on foot the first, so he has enough money to get from the $i$-th crossroad to the $n$-th, using only tram and bus tickets.


-----Input-----

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

The first line of each test case consists of three integers $a, b, p$ ($1 \le a, b, p \le 10^5$) — the cost of bus ticket, the cost of tram ticket and the amount of money Petya has.

The second line of each test case consists of one string $s$, where $s_i = \texttt{A}$, if there is a bus station at $i$-th crossroad, and $s_i = \texttt{B}$, if there is a tram station at $i$-th crossroad ($2 \le |s| \le 10^5$).

It is guaranteed, that the sum of the length of strings $s$ by all test cases in one test doesn't exceed $10^5$.


-----Output-----

For each test case print one number — the minimal index $i$ of a crossroad Petya should go on foot. The rest of the path (i.e. from $i$ to $n$ he should use public transport).


-----Example-----
Input
5
2 2 1
BB
1 1 1
AB
3 2 8
AABBBBAABB
5 3 4
BBBBB
2 1 1
ABABAB

Output
2
1
3
1
6
user: You are given a sequence $a_1, a_2, \dots, a_n$, consisting of integers.

You can apply the following operation to this sequence: choose some integer $x$ and move all elements equal to $x$ either to the beginning, or to the end of $a$. Note that you have to move all these elements in one direction in one operation.

For example, if $a = [2, 1, 3, 1, 1, 3, 2]$, you can get the following sequences in one operation (for convenience, denote elements equal to $x$ as $x$-elements):   $[1, 1, 1, 2, 3, 3, 2]$ if you move all $1$-elements to the beginning;  $[2, 3, 3, 2, 1, 1, 1]$ if you move all $1$-elements to the end;  $[2, 2, 1, 3, 1, 1, 3]$ if you move all $2$-elements to the beginning;  $[1, 3, 1, 1, 3, 2, 2]$ if you move all $2$-elements to the end;  $[3, 3, 2, 1, 1, 1, 2]$ if you move all $3$-elements to the beginning;  $[2, 1, 1, 1, 2, 3, 3]$ if you move all $3$-elements to the end; 

You have to determine the minimum number of such operations so that the sequence $a$ becomes sorted in non-descending order. Non-descending order means that for all $i$ from $2$ to $n$, the condition $a_{i-1} \le a_i$ is satisfied.

Note that you have to answer $q$ independent queries.


-----Input-----

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

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

The second line of each query contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le n$) — the elements.

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


-----Output-----

For each query print one integer — the minimum number of operation for sorting sequence $a$ in non-descending order.


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

Output
2
0
1



-----Note-----

In the first query, you can move all $1$-elements to the beginning (after that sequence turn into $[1, 1, 1, 3, 6, 6, 3]$) and then move all $6$-elements to the end.

In the second query, the sequence is sorted initially, so the answer is zero.

In the third query, you have to move all $2$-elements to the beginning.
user: You are given a binary string $s$ (recall that a string is binary if each character is either $0$ or $1$).

Let $f(t)$ be the decimal representation of integer $t$ written in binary form (possibly with leading zeroes). For example $f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$ and $f(000100) = 4$.

The substring $s_{l}, s_{l+1}, \dots , s_{r}$ is good if $r - l + 1 = f(s_l \dots s_r)$.

For example string $s = 1011$ has $5$ good substrings: $s_1 \dots s_1 = 1$, $s_3 \dots s_3 = 1$, $s_4 \dots s_4 = 1$, $s_1 \dots s_2 = 10$ and $s_2 \dots s_4 = 011$. 

Your task is to calculate the number of good substrings of string $s$.

You have to answer $t$ independent queries.


-----Input-----

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

The only line of each query contains string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of only digits $0$ and $1$.

It is guaranteed that $\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$.


-----Output-----

For each query print one integer — the number of good substrings of string $s$.


-----Example-----
Input
4
0110
0101
00001000
0001000

Output
4
3
4
3