meetforever/GRPO_CL huggingface dataset:
user: You are given a tree consisting of $n$ vertices. A tree is a connected undirected graph with $n-1$ edges. Each vertex $v$ of this tree has a color assigned to it ($a_v = 1$ if the vertex $v$ is white and $0$ if the vertex $v$ is black).

You have to solve the following problem for each vertex $v$: what is the maximum difference between the number of white and the number of black vertices you can obtain if you choose some subtree of the given tree that contains the vertex $v$? The subtree of the tree is the connected subgraph of the given tree. More formally, if you choose the subtree that contains $cnt_w$ white vertices and $cnt_b$ black vertices, you have to maximize $cnt_w - cnt_b$.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1$), where $a_i$ is the color of the $i$-th vertex.

Each of the next $n-1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$, the labels of vertices it connects $(1 \le u_i, v_i \le n, u_i \ne v_i$).

It is guaranteed that the given edges form a tree.


-----Output-----

Print $n$ integers $res_1, res_2, \dots, res_n$, where $res_i$ is the maximum possible difference between the number of white and black vertices in some subtree that contains the vertex $i$.


-----Examples-----
Input
9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9

Output
2 2 2 2 2 1 1 0 2 

Input
4
0 0 1 0
1 2
1 3
1 4

Output
0 -1 1 -1 



-----Note-----

The first example is shown below:

[Image]

The black vertices have bold borders.

In the second example, the best subtree for vertices $2, 3$ and $4$ are vertices $2, 3$ and $4$ correspondingly. And the best subtree for the vertex $1$ is the subtree consisting of vertices $1$ and $3$.
user: You are given an integer $n$. In one move, you can either multiply $n$ by two or divide $n$ by $6$ (if it is divisible by $6$ without the remainder).

Your task is to find the minimum number of moves needed to obtain $1$ from $n$ or determine if it's 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 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow. 

The only line of the test case contains one integer $n$ ($1 \le n \le 10^9$).


-----Output-----

For each test case, print the answer — the minimum number of moves needed to obtain $1$ from $n$ if it's possible to do that or -1 if it's impossible to obtain $1$ from $n$.


-----Example-----
Input
7
1
2
3
12
12345
15116544
387420489

Output
0
-1
2
-1
-1
12
36



-----Note-----

Consider the sixth test case of the example. The answer can be obtained by the following sequence of moves from the given integer $15116544$:

  Divide by $6$ and get $2519424$;  divide by $6$ and get $419904$;  divide by $6$ and get $69984$;  divide by $6$ and get $11664$;  multiply by $2$ and get $23328$;  divide by $6$ and get $3888$;  divide by $6$ and get $648$;  divide by $6$ and get $108$;  multiply by $2$ and get $216$;  divide by $6$ and get $36$;  divide by $6$ and get $6$;  divide by $6$ and get $1$.
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 2000$) — 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 2000$) — 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 $2000$ ($\sum n \le 2000$).


-----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: You are given an array $a$ consisting of $n$ integers $a_1, a_2, \dots , a_n$.

In one operation you can choose two elements of the array and replace them with the element equal to their sum (it does not matter where you insert the new element). For example, from the array $[2, 1, 4]$ you can obtain the following arrays: $[3, 4]$, $[1, 6]$ and $[2, 5]$.

Your task is to find the maximum possible number of elements divisible by $3$ that are in the array after performing this operation an arbitrary (possibly, zero) number of times.

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 first line of each query contains one integer $n$ ($1 \le n \le 100$).

The second line of each query contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$). 


-----Output-----

For each query print one integer in a single line — the maximum possible number of elements divisible by $3$ that are in the array after performing described operation an arbitrary (possibly, zero) number of times.


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

Output
3
3



-----Note-----

In the first query of the example you can apply the following sequence of operations to obtain $3$ elements divisible by $3$: $[3, 1, 2, 3, 1] \rightarrow [3, 3, 3, 1]$.

In the second query you can obtain $3$ elements divisible by $3$ with the following sequence of operations: $[1, 1, 1, 1, 1, 2, 2] \rightarrow [1, 1, 1, 1, 2, 3] \rightarrow [1, 1, 1, 3, 3] \rightarrow [2, 1, 3, 3] \rightarrow [3, 3, 3]$.
user: You are given a permutation of length $n$. Recall that the permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2, 3, 1, 5, 4]$ is a permutation, but $[1, 2, 2]$ is not a permutation ($2$ appears twice in the array) and $[1, 3, 4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

You can perform at most $n-1$ operations with the given permutation (it is possible that you don't perform any operations at all). The $i$-th operation allows you to swap elements of the given permutation on positions $i$ and $i+1$. Each operation can be performed at most once. The operations can be performed in arbitrary order.

Your task is to find the lexicographically minimum possible permutation obtained by performing some of the given operations in some order.

You can see the definition of the lexicographical order in the notes section.

You have to answer $q$ independent test cases.

For example, let's consider the permutation $[5, 4, 1, 3, 2]$. The minimum possible permutation we can obtain is $[1, 5, 2, 4, 3]$ and we can do it in the following way:

  perform the second operation (swap the second and the third elements) and obtain the permutation $[5, 1, 4, 3, 2]$;  perform the fourth operation (swap the fourth and the fifth elements) and obtain the permutation $[5, 1, 4, 2, 3]$;  perform the third operation (swap the third and the fourth elements) and obtain the permutation $[5, 1, 2, 4, 3]$.  perform the first operation (swap the first and the second elements) and obtain the permutation $[1, 5, 2, 4, 3]$; 

Another example is $[1, 2, 4, 3]$. The minimum possible permutation we can obtain is $[1, 2, 3, 4]$ by performing the third operation (swap the third and the fourth elements).


-----Input-----

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

The first line of the test case contains one integer $n$ ($1 \le n \le 100$) — the number of elements in the permutation.

The second line of the test case contains $n$ distinct integers from $1$ to $n$ — the given permutation.


-----Output-----

For each test case, print the answer on it — the lexicograhically minimum possible permutation obtained by performing some of the given operations in some order.


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

Output
1 5 2 4 3 
1 2 3 4 
1 
1 4 3 2 



-----Note-----

Recall that the permutation $p$ of length $n$ is lexicographically less than the permutation $q$ of length $n$ if there is such index $i \le n$ that for all $j$ from $1$ to $i - 1$ the condition $p_j = q_j$ is satisfied, and $p_i < q_i$. For example:

  $p = [1, 3, 5, 2, 4]$ is less than $q = [1, 3, 5, 4, 2]$ (such $i=4$ exists, that $p_i < q_i$ and for each $j < i$ holds $p_j = q_j$),  $p = [1, 2]$ is less than $q = [2, 1]$ (such $i=1$ exists, that $p_i < q_i$ and for each $j < i$ holds $p_j = q_j$).
user: There are $n$ students standing in a circle in some order. The index of the $i$-th student is $p_i$. It is guaranteed that all indices of students are distinct integers from $1$ to $n$ (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student $2$ comes right after the student $1$ in clockwise order (there are no students between them), the student $3$ comes right after the student $2$ in clockwise order, and so on, and the student $n$ comes right after the student $n - 1$ in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student $i$ should be right after the student $i - 1$ in counterclockwise order (this condition should be met for every $i$ from $2$ to $n$). 

For example, if the indices of students listed in clockwise order are $[2, 3, 4, 5, 1]$, then they can start a clockwise round dance. If the students have indices $[3, 2, 1, 4]$ in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle. 

You have to answer $q$ independent queries.


-----Input-----

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

The first line of the query contains one integer $n$ ($1 \le n \le 200$) — the number of students.

The second line of the query contains a permutation of indices $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$), where $p_i$ is the index of the $i$-th student (in clockwise order). It is guaranteed that all $p_i$ are distinct integers from $1$ to $n$ (i. e. they form a permutation).


-----Output-----

For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".


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

Output
YES
YES
NO
YES
YES
user: Santa has $n$ candies and he wants to gift them to $k$ kids. He wants to divide as many candies as possible between all $k$ kids. Santa can't divide one candy into parts but he is allowed to not use some candies at all.

Suppose the kid who recieves the minimum number of candies has $a$ candies and the kid who recieves the maximum number of candies has $b$ candies. Then Santa will be satisfied, if the both conditions are met at the same time:

  $b - a \le 1$ (it means $b = a$ or $b = a + 1$);  the number of kids who has $a+1$ candies (note that $a+1$ not necessarily equals $b$) does not exceed $\lfloor\frac{k}{2}\rfloor$ (less than or equal to $\lfloor\frac{k}{2}\rfloor$). 

$\lfloor\frac{k}{2}\rfloor$ is $k$ divided by $2$ and rounded down to the nearest integer. For example, if $k=5$ then $\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$.

Your task is to find the maximum number of candies Santa can give to kids so that he will be satisfied.

You have to answer $t$ independent test cases.


-----Input-----

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

The next $t$ lines describe test cases. The $i$-th test case contains two integers $n$ and $k$ ($1 \le n, k \le 10^9$) — the number of candies and the number of kids.


-----Output-----

For each test case print the answer on it — the maximum number of candies Santa can give to kids so that he will be satisfied.


-----Example-----
Input
5
5 2
19 4
12 7
6 2
100000 50010

Output
5
18
10
6
75015



-----Note-----

In the first test case, Santa can give $3$ and $2$ candies to kids. There $a=2, b=3,a+1=3$.

In the second test case, Santa can give $5, 5, 4$ and $4$ candies. There $a=4,b=5,a+1=5$. The answer cannot be greater because then the number of kids with $5$ candies will be $3$.

In the third test case, Santa can distribute candies in the following way: $[1, 2, 2, 1, 1, 2, 1]$. There $a=1,b=2,a+1=2$. He cannot distribute two remaining candies in a way to be satisfied.

In the fourth test case, Santa can distribute candies in the following way: $[3, 3]$. There $a=3, b=3, a+1=4$. Santa distributed all $6$ candies.
user: You are given two positive integers $n$ ($1 \le n \le 10^9$) and $k$ ($1 \le k \le 100$). Represent the number $n$ as the sum of $k$ positive integers of the same parity (have the same remainder when divided by $2$).

In other words, find $a_1, a_2, \ldots, a_k$ such that all $a_i>0$, $n = a_1 + a_2 + \ldots + a_k$ and either all $a_i$ are even or all $a_i$ are odd at the same time.

If such a representation does not exist, then report it.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases in the input. Next, $t$ test cases are given, one per line.

Each test case is two positive integers $n$ ($1 \le n \le 10^9$) and $k$ ($1 \le k \le 100$).


-----Output-----

For each test case print:

  YES and the required values $a_i$, if the answer exists (if there are several answers, print any of them);  NO if the answer does not exist. 

The letters in the words YES and NO can be printed in any case.


-----Example-----
Input
8
10 3
100 4
8 7
97 2
8 8
3 10
5 3
1000000000 9

Output
YES
4 2 4
YES
55 5 5 35
NO
NO
YES
1 1 1 1 1 1 1 1
NO
YES
3 1 1
YES
111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111110 111111120
user: Alice and Bob have received three big piles of candies as a gift. Now they want to divide these candies as fair as possible. To do this, Alice takes one pile of candies, then Bob takes one of the other two piles. The last pile is split between Alice and Bob as they want: for example, it is possible that Alice takes the whole pile, and Bob gets nothing from it.

After taking the candies from the piles, if Alice has more candies than Bob, she discards some candies so that the number of candies she has is equal to the number of candies Bob has. Of course, Bob does the same if he has more candies.

Alice and Bob want to have as many candies as possible, and they plan the process of dividing candies accordingly. Please calculate the maximum number of candies Alice can have after this division process (of course, Bob will have the same number of candies).

You have to answer $q$ independent queries.

Let's see the following example: $[1, 3, 4]$. Then Alice can choose the third pile, Bob can take the second pile, and then the only candy from the first pile goes to Bob — then Alice has $4$ candies, and Bob has $4$ candies.

Another example is $[1, 10, 100]$. Then Alice can choose the second pile, Bob can choose the first pile, and candies from the third pile can be divided in such a way that Bob takes $54$ candies, and Alice takes $46$ candies. Now Bob has $55$ candies, and Alice has $56$ candies, so she has to discard one candy — and after that, she has $55$ candies too.


-----Input-----

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

The only line of the query contains three integers $a, b$ and $c$ ($1 \le a, b, c \le 10^{16}$) — the number of candies in the first, second and third piles correspondingly.


-----Output-----

Print $q$ lines. The $i$-th line should contain the answer for the $i$-th query — the maximum number of candies Alice can have after the division, if both Alice and Bob act optimally (of course, Bob will have the same number of candies).


-----Example-----
Input
4
1 3 4
1 10 100
10000000000000000 10000000000000000 10000000000000000
23 34 45

Output
4
55
15000000000000000
51
user: The store sells $n$ beads. The color of each bead is described by a lowercase letter of the English alphabet ("a"–"z"). You want to buy some beads to assemble a necklace from them.

A necklace is a set of beads connected in a circle.

For example, if the store sells beads "a", "b", "c", "a", "c", "c", then you can assemble the following necklaces (these are not all possible options): [Image] 

And the following necklaces cannot be assembled from beads sold in the store: [Image] The first necklace cannot be assembled because it has three beads "a" (of the two available). The second necklace cannot be assembled because it contains a bead "d", which is not sold in the store. 

We call a necklace $k$-beautiful if, when it is turned clockwise by $k$ beads, the necklace remains unchanged. For example, here is a sequence of three turns of a necklace.  [Image]  As you can see, this necklace is, for example, $3$-beautiful, $6$-beautiful, $9$-beautiful, and so on, but it is not $1$-beautiful or $2$-beautiful.

In particular, a necklace of length $1$ is $k$-beautiful for any integer $k$. A necklace that consists of beads of the same color is also beautiful for any $k$.

You are given the integers $n$ and $k$, and also the string $s$ containing $n$ lowercase letters of the English alphabet — each letter defines a bead in the store. You can buy any subset of beads and connect them in any order. Find the maximum length of a $k$-beautiful necklace you can assemble.


-----Input-----

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

The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 2000$).

The second line of each test case contains the string $s$ containing $n$ lowercase English letters — the beads in the store.

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


-----Output-----

Output $t$ answers to the test cases. Each answer is a positive integer — the maximum length of the $k$-beautiful necklace you can assemble.


-----Example-----
Input
6
6 3
abcbac
3 6
aaa
7 1000
abczgyo
5 4
ababa
20 10
aaebdbabdbbddaadaadc
20 5
ecbedececacbcbccbdec

Output
6
3
5
4
15
10



-----Note-----

The first test case is explained in the statement.

In the second test case, a $6$-beautiful necklace can be assembled from all the letters.

In the third test case, a $1000$-beautiful necklace can be assembled, for example, from beads "abzyo".
user: You are given an array $a$ consisting of $n$ integers $a_1, a_2, \dots, a_n$. You want to split it into exactly $k$ non-empty non-intersecting subsegments such that each subsegment has odd sum (i. e. for each subsegment, the sum of all elements that belong to this subsegment is odd). It is impossible to rearrange (shuffle) the elements of a given array. Each of the $n$ elements of the array $a$ must belong to exactly one of the $k$ subsegments.

Let's see some examples of dividing the array of length $5$ into $3$ subsegments (not necessarily with odd sums): $[1, 2, 3, 4, 5]$ is the initial array, then all possible ways to divide it into $3$ non-empty non-intersecting subsegments are described below:  $[1], [2], [3, 4, 5]$;  $[1], [2, 3], [4, 5]$;  $[1], [2, 3, 4], [5]$;  $[1, 2], [3], [4, 5]$;  $[1, 2], [3, 4], [5]$;  $[1, 2, 3], [4], [5]$. 

Of course, it can be impossible to divide the initial array into exactly $k$ subsegments in such a way that each of them will have odd sum of elements. In this case print "NO". Otherwise, print "YES" and any possible division of the array. See the output format for the detailed explanation.

You have to answer $q$ independent queries.


-----Input-----

The first line 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 number of elements in the array and the number of subsegments, respectively.

The second line of the query contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the $i$-th element of $a$.

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 the answer to it. If it is impossible to divide the initial array into exactly $k$ subsegments in such a way that each of them will have odd sum of elements, print "NO" in the first line. Otherwise, print "YES" in the first line and any possible division of the array in the second line. The division can be represented as $k$ integers $r_1$, $r_2$, ..., $r_k$ such that $1 \le r_1 < r_2 < \dots < r_k = n$, where $r_j$ is the right border of the $j$-th segment (the index of the last element that belongs to the $j$-th segment), so the array is divided into subsegments $[1; r_1], [r_1 + 1; r_2], [r_2 + 1, r_3], \dots, [r_{k - 1} + 1, n]$. Note that $r_k$ is always $n$ but you should print it anyway. 


-----Example-----
Input
3
5 3
7 18 3 14 1
5 4
1 2 3 4 5
6 2
1 2 8 4 10 2

Output
YES
1 3 5
NO
NO
user: Reverse bits of a given 32 bits unsigned integer.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.
Follow up:

If this function is called many times, how would you optimize it?

Example 1:

Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101
Output:   3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111. 

Constraints:

The input must be a binary string of length 32

Answer: {"fn_name": "reverseBits", "inputs": [[43261596], [4294967293]], "outputs": [964176192, 3221225471]}
user: Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.


In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:


Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Answer: {"fn_name": "generate", "inputs": [[5], [1]], "outputs": [[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]], [[1]]]}