meetforever/GRPO_CL huggingface dataset:
user: Kuroni is very angry at the other setters for using him as a theme! As a punishment, he forced them to solve the following problem:

You have an array $a$ consisting of $n$ positive integers. An operation consists of choosing an element and either adding $1$ to it or subtracting $1$ from it, such that the element remains positive. We say the array is good if the greatest common divisor of all its elements is not $1$. Find the minimum number of operations needed to make the array good.

Unable to match Kuroni's intellect, the setters failed to solve the problem. Help them escape from Kuroni's punishment!


-----Input-----

The first line contains an integer $n$ ($2 \le n \le 2 \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 10^{12}$)  — the elements of the array.


-----Output-----

Print a single integer  — the minimum number of operations required to make the array good.


-----Examples-----
Input
3
6 2 4

Output
0

Input
5
9 8 7 3 1

Output
4



-----Note-----

In the first example, the first array is already good, since the greatest common divisor of all the elements is $2$.

In the second example, we may apply the following operations:

  Add $1$ to the second element, making it equal to $9$.  Subtract $1$ from the third element, making it equal to $6$.  Add $1$ to the fifth element, making it equal to $2$.  Add $1$ to the fifth element again, making it equal to $3$. 

The greatest common divisor of all elements will then be equal to $3$, so the array will be good. It can be shown that no sequence of three or less operations can make the array good.
user: The string $t_1t_2 \dots t_k$ is good if each letter of this string belongs to at least one palindrome of length greater than 1.

A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.

Here are some examples of good strings:   $t$ = AABBB (letters $t_1$, $t_2$ belong to palindrome $t_1 \dots t_2$ and letters $t_3$, $t_4$, $t_5$ belong to palindrome $t_3 \dots t_5$);  $t$ = ABAA (letters $t_1$, $t_2$, $t_3$ belong to palindrome $t_1 \dots t_3$ and letter $t_4$ belongs to palindrome $t_3 \dots t_4$);  $t$ = AAAAA (all letters belong to palindrome $t_1 \dots t_5$); 

You are given a string $s$ of length $n$, consisting of only letters A and B.

You have to calculate the number of good substrings of string $s$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$) — the length of the string $s$.

The second line contains the string $s$, consisting of letters A and B.


-----Output-----

Print one integer — the number of good substrings of string $s$.


-----Examples-----
Input
5
AABBB

Output
6

Input
3
AAA

Output
3

Input
7
AAABABB

Output
15



-----Note-----

In the first test case there are six good substrings: $s_1 \dots s_2$, $s_1 \dots s_4$, $s_1 \dots s_5$, $s_3 \dots s_4$, $s_3 \dots s_5$ and $s_4 \dots s_5$.

In the second test case there are three good substrings: $s_1 \dots s_2$, $s_1 \dots s_3$ and $s_2 \dots s_3$.
user: You are given an array of $n$ integers $a_1,a_2,\dots,a_n$.

You have to create an array of $n$ integers $b_1,b_2,\dots,b_n$ such that:   The array $b$ is a rearrangement of the array $a$, that is, it contains the same values and each value appears the same number of times in the two arrays. In other words, the multisets $\{a_1,a_2,\dots,a_n\}$ and $\{b_1,b_2,\dots,b_n\}$ are equal.

For example, if $a=[1,-1,0,1]$, then $b=[-1,1,1,0]$ and $b=[0,1,-1,1]$ are rearrangements of $a$, but $b=[1,-1,-1,0]$ and $b=[1,0,2,-3]$ are not rearrangements of $a$.  For all $k=1,2,\dots,n$ the sum of the first $k$ elements of $b$ is nonzero. Formally, for all $k=1,2,\dots,n$, it must hold $$b_1+b_2+\cdots+b_k\not=0\,.$$ 

If an array $b_1,b_2,\dots, b_n$ with the required properties does not exist, you have to print NO.


-----Input-----

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

The first line of each testcase contains one integer $n$ ($1\le n\le 50$)  — the length of the array $a$.

The second line of each testcase contains $n$ integers $a_1,a_2,\dots, a_n$ ($-50\le a_i\le 50$)  — the elements of $a$.


-----Output-----

For each testcase, if there is not an array $b_1,b_2,\dots,b_n$ with the required properties, print a single line with the word NO.

Otherwise print a line with the word YES, followed by a line with the $n$ integers $b_1,b_2,\dots,b_n$. 

If there is more than one array $b_1,b_2,\dots,b_n$ satisfying the required properties, you can print any of them.


-----Example-----
Input
4
4
1 -2 3 -4
3
0 0 0
5
1 -1 1 -1 1
6
40 -31 -9 0 13 -40

Output
YES
1 -2 3 -4
NO
YES
1 1 -1 1 -1
YES
-40 13 40 0 -9 -31



-----Note-----

Explanation of the first testcase: An array with the desired properties is $b=[1,-2,3,-4]$. For this array, it holds:   The first element of $b$ is $1$.  The sum of the first two elements of $b$ is $-1$.  The sum of the first three elements of $b$ is $2$.  The sum of the first four elements of $b$ is $-2$. 

Explanation of the second testcase: Since all values in $a$ are $0$, any rearrangement $b$ of $a$ will have all elements equal to $0$ and therefore it clearly cannot satisfy the second property described in the statement (for example because $b_1=0$). Hence in this case the answer is NO.

Explanation of the third testcase: An array with the desired properties is $b=[1, 1, -1, 1, -1]$. For this array, it holds:   The first element of $b$ is $1$.  The sum of the first two elements of $b$ is $2$.  The sum of the first three elements of $b$ is $1$.  The sum of the first four elements of $b$ is $2$.  The sum of the first five elements of $b$ is $1$. 

Explanation of the fourth testcase: An array with the desired properties is $b=[-40,13,40,0,-9,-31]$. For this array, it holds:   The first element of $b$ is $-40$.  The sum of the first two elements of $b$ is $-27$.  The sum of the first three elements of $b$ is $13$.  The sum of the first four elements of $b$ is $13$.  The sum of the first five elements of $b$ is $4$.  The sum of the first six elements of $b$ is $-27$.
user: Gildong was hiking a mountain, walking by millions of trees. Inspired by them, he suddenly came up with an interesting idea for trees in data structures: What if we add another edge in a tree?

Then he found that such tree-like graphs are called 1-trees. Since Gildong was bored of solving too many tree problems, he wanted to see if similar techniques in trees can be used in 1-trees as well. Instead of solving it by himself, he's going to test you by providing queries on 1-trees.

First, he'll provide you a tree (not 1-tree) with $n$ vertices, then he will ask you $q$ queries. Each query contains $5$ integers: $x$, $y$, $a$, $b$, and $k$. This means you're asked to determine if there exists a path from vertex $a$ to $b$ that contains exactly $k$ edges after adding a bidirectional edge between vertices $x$ and $y$. A path can contain the same vertices and same edges multiple times. All queries are independent of each other; i.e. the added edge in a query is removed in the next query.


-----Input-----

The first line contains an integer $n$ ($3 \le n \le 10^5$), the number of vertices of the tree.

Next $n-1$ lines contain two integers $u$ and $v$ ($1 \le u,v \le n$, $u \ne v$) each, which means there is an edge between vertex $u$ and $v$. All edges are bidirectional and distinct.

Next line contains an integer $q$ ($1 \le q \le 10^5$), the number of queries Gildong wants to ask.

Next $q$ lines contain five integers $x$, $y$, $a$, $b$, and $k$ each ($1 \le x,y,a,b \le n$, $x \ne y$, $1 \le k \le 10^9$) – the integers explained in the description. It is guaranteed that the edge between $x$ and $y$ does not exist in the original tree.


-----Output-----

For each query, print "YES" if there exists a path that contains exactly $k$ edges from vertex $a$ to $b$ after adding an edge between vertices $x$ and $y$. Otherwise, print "NO".

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


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

Output
YES
YES
NO
YES
NO



-----Note-----

The image below describes the tree (circles and solid lines) and the added edges for each query (dotted lines). [Image] 

Possible paths for the queries with "YES" answers are:   $1$-st query: $1$ – $3$ – $2$  $2$-nd query: $1$ – $2$ – $3$  $4$-th query: $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$ – $4$ – $2$ – $3$
user: Your city has n junctions. There are m one-way roads between the junctions. As a mayor of the city, you have to ensure the security of all the junctions.

To ensure the security, you have to build some police checkposts. Checkposts can only be built in a junction. A checkpost at junction i can protect junction j if either i = j or the police patrol car can go to j from i and then come back to i.

Building checkposts costs some money. As some areas of the city are more expensive than others, building checkpost at some junctions might cost more money than other junctions.

You have to determine the minimum possible money needed to ensure the security of all the junctions. Also you have to find the number of ways to ensure the security in minimum price and in addition in minimum number of checkposts. Two ways are different if any of the junctions contains a checkpost in one of them and do not contain in the other.


-----Input-----

In the first line, you will be given an integer n, number of junctions (1 ≤ n ≤ 10^5). In the next line, n space-separated integers will be given. The i^{th} integer is the cost of building checkpost at the i^{th} junction (costs will be non-negative and will not exceed 10^9).

The next line will contain an integer m (0 ≤ m ≤ 3·10^5). And each of the next m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n; u ≠ v). A pair u_{i}, v_{i} means, that there is a one-way road which goes from u_{i} to v_{i}. There will not be more than one road between two nodes in the same direction.


-----Output-----

Print two integers separated by spaces. The first one is the minimum possible money needed to ensure the security of all the junctions. And the second one is the number of ways you can ensure the security modulo 1000000007 (10^9 + 7).


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

Output
3 1

Input
5
2 8 0 6 0
6
1 4
1 3
2 4
3 4
4 5
5 1

Output
8 2

Input
10
1 3 2 2 1 3 1 4 10 10
12
1 2
2 3
3 1
3 4
4 5
5 6
5 7
6 4
7 3
8 9
9 10
10 9

Output
15 6

Input
2
7 91
2
1 2
2 1

Output
7 1
user: Given a set of integers (it can contain equal elements).

You have to split it into two subsets $A$ and $B$ (both of them can contain equal elements or be empty). You have to maximize the value of $mex(A)+mex(B)$.

Here $mex$ of a set denotes the smallest non-negative integer that doesn't exist in the set. For example:   $mex(\{1,4,0,2,2,1\})=3$  $mex(\{3,3,2,1,3,0,0\})=4$  $mex(\varnothing)=0$ ($mex$ for empty set) 

The set is splitted into two subsets $A$ and $B$ if for any integer number $x$ the number of occurrences of $x$ into this set is equal to the sum of the number of occurrences of $x$ into $A$ and the number of occurrences of $x$ into $B$.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1\leq t\leq 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\leq n\leq 100$) — the size of the set.

The second line of each testcase contains $n$ integers $a_1,a_2,\dots a_n$ ($0\leq a_i\leq 100$) — the numbers in the set.


-----Output-----

For each test case, print the maximum value of $mex(A)+mex(B)$.


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

Output
5
3
4
0



-----Note-----

In the first test case, $A=\left\{0,1,2\right\},B=\left\{0,1,5\right\}$ is a possible choice.

In the second test case, $A=\left\{0,1,2\right\},B=\varnothing$ is a possible choice.

In the third test case, $A=\left\{0,1,2\right\},B=\left\{0\right\}$ is a possible choice.

In the fourth test case, $A=\left\{1,3,5\right\},B=\left\{2,4,6\right\}$ is a possible choice.
user: You are given an integer m, and a list of n distinct integers between 0 and m - 1.

You would like to construct a sequence satisfying the properties:  Each element is an integer between 0 and m - 1, inclusive.  All prefix products of the sequence modulo m are distinct.  No prefix product modulo m appears as an element of the input list.  The length of the sequence is maximized. 

Construct any sequence satisfying the properties above.


-----Input-----

The first line of input contains two integers n and m (0 ≤ n < m ≤ 200 000) — the number of forbidden prefix products and the modulus.

If n is non-zero, the next line of input contains n distinct integers between 0 and m - 1, the forbidden prefix products. If n is zero, this line doesn't exist.


-----Output-----

On the first line, print the number k, denoting the length of your sequence.

On the second line, print k space separated integers, denoting your sequence.


-----Examples-----
Input
0 5

Output
5
1 2 4 3 0

Input
3 10
2 9 1

Output
6
3 9 2 9 8 0



-----Note-----

For the first case, the prefix products of this sequence modulo m are [1, 2, 3, 4, 0].

For the second case, the prefix products of this sequence modulo m are [3, 7, 4, 6, 8, 0].
user: There are $n$ seats in the train's car and there is exactly one passenger occupying every seat. The seats are numbered from $1$ to $n$ from left to right. The trip is long, so each passenger will become hungry at some moment of time and will go to take boiled water for his noodles. The person at seat $i$ ($1 \leq i \leq n$) will decide to go for boiled water at minute $t_i$.

Tank with a boiled water is located to the left of the $1$-st seat. In case too many passengers will go for boiled water simultaneously, they will form a queue, since there can be only one passenger using the tank at each particular moment of time. Each passenger uses the tank for exactly $p$ minutes. We assume that the time it takes passengers to go from their seat to the tank is negligibly small. 

Nobody likes to stand in a queue. So when the passenger occupying the $i$-th seat wants to go for a boiled water, he will first take a look on all seats from $1$ to $i - 1$. In case at least one of those seats is empty, he assumes that those people are standing in a queue right now, so he would be better seating for the time being. However, at the very first moment he observes that all seats with numbers smaller than $i$ are busy, he will go to the tank.

There is an unspoken rule, that in case at some moment several people can go to the tank, than only the leftmost of them (that is, seating on the seat with smallest number) will go to the tank, while all others will wait for the next moment.

Your goal is to find for each passenger, when he will receive the boiled water for his noodles.


-----Input-----

The first line contains integers $n$ and $p$ ($1 \leq n \leq 100\,000$, $1 \leq p \leq 10^9$) — the number of people and the amount of time one person uses the tank.

The second line contains $n$ integers $t_1, t_2, \dots, t_n$ ($0 \leq t_i \leq 10^9$) — the moments when the corresponding passenger will go for the boiled water.


-----Output-----

Print $n$ integers, where $i$-th of them is the time moment the passenger on $i$-th seat will receive his boiled water.


-----Example-----
Input
5 314
0 310 942 628 0

Output
314 628 1256 942 1570 



-----Note-----

Consider the example.

At the $0$-th minute there were two passengers willing to go for a water, passenger $1$ and $5$, so the first passenger has gone first, and returned at the $314$-th minute. At this moment the passenger $2$ was already willing to go for the water, so the passenger $2$ has gone next, and so on. In the end, $5$-th passenger was last to receive the boiled water.
user: One evening Rainbow Dash and Fluttershy have come up with a game. Since the ponies are friends, they have decided not to compete in the game but to pursue a common goal. 

The game starts on a square flat grid, which initially has the outline borders built up. Rainbow Dash and Fluttershy have flat square blocks with size $1\times1$, Rainbow Dash has an infinite amount of light blue blocks, Fluttershy has an infinite amount of yellow blocks. 

The blocks are placed according to the following rule: each newly placed block must touch the built on the previous turns figure by a side (note that the outline borders of the grid are built initially). At each turn, one pony can place any number of blocks of her color according to the game rules.

Rainbow and Fluttershy have found out that they can build patterns on the grid of the game that way. They have decided to start with something simple, so they made up their mind to place the blocks to form a chess coloring. Rainbow Dash is well-known for her speed, so she is interested in the minimum number of turns she and Fluttershy need to do to get a chess coloring, covering the whole grid with blocks. Please help her find that number!

Since the ponies can play many times on different boards, Rainbow Dash asks you to find the minimum numbers of turns for several grids of the games.

The chess coloring in two colors is the one in which each square is neighbor by side only with squares of different colors.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 100$): the number of grids of the games. 

Each of the next $T$ lines contains a single integer $n$ ($1 \le n \le 10^9$): the size of the side of the grid of the game. 


-----Output-----

For each grid of the game print the minimum number of turns required to build a chess coloring pattern out of blocks on it.


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

Output
2
3



-----Note-----

For $3\times3$ grid ponies can make two following moves: [Image]
user: Given a sequence of integers a_1, ..., a_{n} and q queries x_1, ..., x_{q} on it. For each query x_{i} you have to count the number of pairs (l, r) such that 1 ≤ l ≤ r ≤ n and gcd(a_{l}, a_{l} + 1, ..., a_{r}) = x_{i}.

$\operatorname{gcd}(v_{1}, v_{2}, \ldots, v_{n})$ is a greatest common divisor of v_1, v_2, ..., v_{n}, that is equal to a largest positive integer that divides all v_{i}.


-----Input-----

The first line of the input contains integer n, (1 ≤ n ≤ 10^5), denoting the length of the sequence. The next line contains n space separated integers a_1, ..., a_{n}, (1 ≤ a_{i} ≤ 10^9).

The third line of the input contains integer q, (1 ≤ q ≤ 3 × 10^5), denoting the number of queries. Then follows q lines, each contain an integer x_{i}, (1 ≤ x_{i} ≤ 10^9).


-----Output-----

For each query print the result in a separate line.


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

Output
1
2
2
0
1

Input
7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000

Output
14
0
2
2
2
0
2
2
1
1
user: Shubham has a binary string $s$. A binary string is a string containing only characters "0" and "1".

He can perform the following operation on the string any amount of times:   Select an index of the string, and flip the character at that index. This means, if the character was "0", it becomes "1", and vice versa. 

A string is called good if it does not contain "010" or "101" as a subsequence  — for instance, "1001" contains "101" as a subsequence, hence it is not a good string, while "1000" doesn't contain neither "010" nor "101" as subsequences, so it is a good string.

What is the minimum number of operations he will have to perform, so that the string becomes good? It can be shown that with these operations we can make any string good.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters.


-----Input-----

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

Each of the next $t$ lines contains a binary string $s$ $(1 \le |s| \le 1000)$.


-----Output-----

For every string, output the minimum number of operations required to make it good.


-----Example-----
Input
7
001
100
101
010
0
1
001100

Output
0
0
1
1
0
0
2



-----Note-----

In test cases $1$, $2$, $5$, $6$ no operations are required since they are already good strings.

For the $3$rd test case: "001" can be achieved by flipping the first character  — and is one of the possible ways to get a good string.

For the $4$th test case: "000" can be achieved by flipping the second character  — and is one of the possible ways to get a good string.

For the $7$th test case: "000000" can be achieved by flipping the third and fourth characters  — and is one of the possible ways to get a good string.
user: Let $n$ be a positive integer. Let $a, b, c$ be nonnegative integers such that $a + b + c = n$.

Alice and Bob are gonna play rock-paper-scissors $n$ times. Alice knows the sequences of hands that Bob will play. However, Alice has to play rock $a$ times, paper $b$ times, and scissors $c$ times.

Alice wins if she beats Bob in at least $\lceil \frac{n}{2} \rceil$ ($\frac{n}{2}$ rounded up to the nearest integer) hands, otherwise Alice loses.

Note that in rock-paper-scissors:

  rock beats scissors;  paper beats rock;  scissors beat paper. 

The task is, given the sequence of hands that Bob will play, and the numbers $a, b, c$, determine whether or not Alice can win. And if so, find any possible sequence of hands that Alice can use to win.

If there are multiple answers, print any of them.


-----Input-----

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

Then, $t$ testcases follow, each consisting of three lines:   The first line contains a single integer $n$ ($1 \le n \le 100$).  The second line contains three integers, $a, b, c$ ($0 \le a, b, c \le n$). It is guaranteed that $a + b + c = n$.  The third line contains a string $s$ of length $n$. $s$ is made up of only 'R', 'P', and 'S'. The $i$-th character is 'R' if for his $i$-th Bob plays rock, 'P' if paper, and 'S' if scissors. 


-----Output-----

For each testcase:   If Alice cannot win, print "NO" (without the quotes).  Otherwise, print "YES" (without the quotes). Also, print a string $t$ of length $n$ made up of only 'R', 'P', and 'S' — a sequence of hands that Alice can use to win. $t$ must contain exactly $a$ 'R's, $b$ 'P's, and $c$ 'S's.  If there are multiple answers, print any of them. 

The "YES" / "NO" part of the output is case-insensitive (i.e. "yEs", "no" or "YEs" are all valid answers). Note that 'R', 'P' and 'S' are case-sensitive.


-----Example-----
Input
2
3
1 1 1
RPS
3
3 0 0
RPS

Output
YES
PSR
NO



-----Note-----

In the first testcase, in the first hand, Alice plays paper and Bob plays rock, so Alice beats Bob. In the second hand, Alice plays scissors and Bob plays paper, so Alice beats Bob. In the third hand, Alice plays rock and Bob plays scissors, so Alice beats Bob. Alice beat Bob 3 times, and $3 \ge \lceil \frac{3}{2} \rceil = 2$, so Alice wins.

In the second testcase, the only sequence of hands that Alice can play is "RRR". Alice beats Bob only in the last hand, so Alice can't win. $1 < \lceil \frac{3}{2} \rceil = 2$.