meetforever/GRPO_CL huggingface dataset:
user: A railroad running from west to east in Atcoder Kingdom is now complete.
There are N stations on the railroad, numbered 1 through N from west to east.
Tomorrow, the opening ceremony of the railroad will take place.
On this railroad, for each integer i such that 1≤i≤N-1, there will be trains that run from Station i to Station i+1 in C_i seconds. No other trains will be operated.
The first train from Station i to Station i+1 will depart Station i S_i seconds after the ceremony begins. Thereafter, there will be a train that departs Station i every F_i seconds.
Here, it is guaranteed that F_i divides S_i.
That is, for each Time t satisfying S_i≤t and t％F_i=0, there will be a train that departs Station i t seconds after the ceremony begins and arrives at Station i+1 t+C_i seconds after the ceremony begins, where A％B denotes A modulo B, and there will be no other trains.
For each i, find the earliest possible time we can reach Station N if we are at Station i when the ceremony begins, ignoring the time needed to change trains.

-----Constraints-----
 - 1≤N≤500
 - 1≤C_i≤100
 - 1≤S_i≤10^5
 - 1≤F_i≤10
 - S_i％F_i=0
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
C_1 S_1 F_1
:
C_{N-1} S_{N-1} F_{N-1}

-----Output-----
Print N lines. Assuming that we are at Station i (1≤i≤N) when the ceremony begins, if the earliest possible time we can reach Station N is x seconds after the ceremony begins, the i-th line should contain x.

-----Sample Input-----
3
6 5 1
1 10 1

-----Sample Output-----
12
11
0

We will travel from Station 1 as follows:
 - 5 seconds after the beginning: take the train to Station 2.
 - 11 seconds: arrive at Station 2.
 - 11 seconds: take the train to Station 3.
 - 12 seconds: arrive at Station 3.
We will travel from Station 2 as follows:
 - 10 seconds: take the train to Station 3.
 - 11 seconds: arrive at Station 3.
Note that we should print 0 for Station 3.
user: There is an image with a height of H pixels and a width of W pixels. Each of the pixels is represented by either . or *. The character representing the pixel at the i-th row from the top and the j-th column from the left, is denoted by C_{i,j}.
Extend this image vertically so that its height is doubled. That is, print a image with a height of 2H pixels and a width of W pixels where the pixel at the i-th row and j-th column is equal to C_{(i+1)/2,j} (the result of division is rounded down).

-----Constraints-----
 - 1≦H, W≦100
 - C_{i,j} is either . or *.

-----Input-----
The input is given from Standard Input in the following format:
H W
C_{1,1}...C_{1,W}
:
C_{H,1}...C_{H,W}

-----Output-----
Print the extended image.

-----Sample Input-----
2 2
*.
.*

-----Sample Output-----
*.
*.
.*
.*
user: Given is a sequence of integers A_1, A_2, ..., A_N.
If its elements are pairwise distinct, print YES; otherwise, print NO.

-----Constraints-----
 - 2 ≤ N ≤ 200000
 - 1 ≤ A_i ≤ 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 ... A_N

-----Output-----
If the elements of the sequence are pairwise distinct, print YES; otherwise, print NO.

-----Sample Input-----
5
2 6 1 4 5

-----Sample Output-----
YES

The elements are pairwise distinct.
user: There are $n$ people who want to participate in a boat competition. The weight of the $i$-th participant is $w_i$. Only teams consisting of two people can participate in this competition. As an organizer, you think that it's fair to allow only teams with the same total weight.

So, if there are $k$ teams $(a_1, b_1)$, $(a_2, b_2)$, $\dots$, $(a_k, b_k)$, where $a_i$ is the weight of the first participant of the $i$-th team and $b_i$ is the weight of the second participant of the $i$-th team, then the condition $a_1 + b_1 = a_2 + b_2 = \dots = a_k + b_k = s$, where $s$ is the total weight of each team, should be satisfied.

Your task is to choose such $s$ that the number of teams people can create is the maximum possible. Note that each participant can be in no more than one team.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 1000$) — 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 number of participants. The second line of the test case contains $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le n$), where $w_i$ is the weight of the $i$-th participant.


-----Output-----

For each test case, print one integer $k$: the maximum number of teams people can compose with the total weight $s$, if you choose $s$ optimally.


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

Output
2
3
4
1
2



-----Note-----

In the first test case of the example, we can reach the optimal answer for $s=6$. Then the first boat is used by participants $1$ and $5$ and the second boat is used by participants $2$ and $4$ (indices are the same as weights).

In the second test case of the example, we can reach the optimal answer for $s=12$. Then first $6$ participants can form $3$ pairs.

In the third test case of the example, we can reach the optimal answer for $s=3$. The answer is $4$ because we have $4$ participants with weight $1$ and $4$ participants with weight $2$.

In the fourth test case of the example, we can reach the optimal answer for $s=4$ or $s=6$.

In the fifth test case of the example, we can reach the optimal answer for $s=3$. Note that participant with weight $3$ can't use the boat because there is no suitable pair for him in the list.
user: Vasya goes to visit his classmate Petya. Vasya knows that Petya's apartment number is $n$. 

There is only one entrance in Petya's house and the distribution of apartments is the following: the first floor contains $2$ apartments, every other floor contains $x$ apartments each. Apartments are numbered starting from one, from the first floor. I.e. apartments on the first floor have numbers $1$ and $2$, apartments on the second floor have numbers from $3$ to $(x + 2)$, apartments on the third floor have numbers from $(x + 3)$ to $(2 \cdot x + 2)$, and so on.

Your task is to find the number of floor on which Petya lives. Assume that the house is always high enough to fit at least $n$ apartments.

You have to answer $t$ independent test cases.


-----Input-----

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

The only line of the test case contains two integers $n$ and $x$ ($1 \le n, x \le 1000$) — the number of Petya's apartment and the number of apartments on each floor of the house except the first one (there are two apartments on the first floor).


-----Output-----

For each test case, print the answer: the number of floor on which Petya lives.


-----Example-----
Input
4
7 3
1 5
22 5
987 13

Output
3
1
5
77



-----Note-----

Consider the first test case of the example: the first floor contains apartments with numbers $1$ and $2$, the second one contains apartments with numbers $3$, $4$ and $5$, the third one contains apartments with numbers $6$, $7$ and $8$. Therefore, Petya lives on the third floor.

In the second test case of the example, Petya lives in the apartment $1$ which is on the first floor.
user: You want to perform the combo on your opponent in one popular fighting game. The combo is the string $s$ consisting of $n$ lowercase Latin letters. To perform the combo, you have to press all buttons in the order they appear in $s$. I.e. if $s=$"abca" then you have to press 'a', then 'b', 'c' and 'a' again.

You know that you will spend $m$ wrong tries to perform the combo and during the $i$-th try you will make a mistake right after $p_i$-th button ($1 \le p_i < n$) (i.e. you will press first $p_i$ buttons right and start performing the combo from the beginning). It is guaranteed that during the $m+1$-th try you press all buttons right and finally perform the combo.

I.e. if $s=$"abca", $m=2$ and $p = [1, 3]$ then the sequence of pressed buttons will be 'a' (here you're making a mistake and start performing the combo from the beginning), 'a', 'b', 'c', (here you're making a mistake and start performing the combo from the beginning), 'a' (note that at this point you will not perform the combo because of the mistake), 'b', 'c', 'a'.

Your task is to calculate for each button (letter) the number of times you'll press it.

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.

Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$) — the length of $s$ and the number of tries correspondingly.

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

The third line of each test case contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i < n$) — the number of characters pressed right during the $i$-th try.

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

It is guaranteed that the answer for each letter does not exceed $2 \cdot 10^9$.


-----Output-----

For each test case, print the answer — $26$ integers: the number of times you press the button 'a', the number of times you press the button 'b', $\dots$, the number of times you press the button 'z'.


-----Example-----
Input
3
4 2
abca
1 3
10 5
codeforces
2 8 3 2 9
26 10
qwertyuioplkjhgfdsazxcvbnm
20 10 1 2 3 5 10 5 9 4

Output
4 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
0 0 9 4 5 3 0 0 0 0 0 0 0 0 9 0 0 3 1 0 0 0 0 0 0 0 
2 1 1 2 9 2 2 2 5 2 2 2 1 1 5 4 11 8 2 7 5 1 10 1 5 2 



-----Note-----

The first test case is described in the problem statement. Wrong tries are "a", "abc" and the final try is "abca". The number of times you press 'a' is $4$, 'b' is $2$ and 'c' is $2$.

In the second test case, there are five wrong tries: "co", "codeforc", "cod", "co", "codeforce" and the final try is "codeforces". The number of times you press 'c' is $9$, 'd' is $4$, 'e' is $5$, 'f' is $3$, 'o' is $9$, 'r' is $3$ and 's' is $1$.
user: Three friends are going to meet each other. Initially, the first friend stays at the position $x = a$, the second friend stays at the position $x = b$ and the third friend stays at the position $x = c$ on the coordinate axis $Ox$.

In one minute each friend independently from other friends can change the position $x$ by $1$ to the left or by $1$ to the right (i.e. set $x := x - 1$ or $x := x + 1$) or even don't change it.

Let's introduce the total pairwise distance — the sum of distances between each pair of friends. Let $a'$, $b'$ and $c'$ be the final positions of the first, the second and the third friend, correspondingly. Then the total pairwise distance is $|a' - b'| + |a' - c'| + |b' - c'|$, where $|x|$ is the absolute value of $x$.

Friends are interested in the minimum total pairwise distance they can reach if they will move optimally. Each friend will move no more than once. So, more formally, they want to know the minimum total pairwise distance they can reach after one minute.

You have to answer $q$ independent test cases.


-----Input-----

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

The next $q$ lines describe test cases. The $i$-th test case is given as three integers $a, b$ and $c$ ($1 \le a, b, c \le 10^9$) — initial positions of the first, second and third friend correspondingly. The positions of friends can be equal.


-----Output-----

For each test case print the answer on it — the minimum total pairwise distance (the minimum sum of distances between each pair of friends) if friends change their positions optimally. Each friend will move no more than once. So, more formally, you have to find the minimum total pairwise distance they can reach after one minute.


-----Example-----
Input
8
3 3 4
10 20 30
5 5 5
2 4 3
1 1000000000 1000000000
1 1000000000 999999999
3 2 5
3 2 6

Output
0
36
0
0
1999999994
1999999994
2
4
user: We call two numbers $x$ and $y$ similar if they have the same parity (the same remainder when divided by $2$), or if $|x-y|=1$. For example, in each of the pairs $(2, 6)$, $(4, 3)$, $(11, 7)$, the numbers are similar to each other, and in the pairs $(1, 4)$, $(3, 12)$, they are not.

You are given an array $a$ of $n$ ($n$ is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array $a = [11, 14, 16, 12]$, there is a partition into pairs $(11, 12)$ and $(14, 16)$. The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.


-----Input-----

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

Each test case consists of two lines.

The first line contains an even positive integer $n$ ($2 \le n \le 50$) — length of array $a$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$).


-----Output-----

For each test case print:  YES if the such a partition exists,  NO otherwise. 

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


-----Example-----
Input
7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8

Output
YES
NO
YES
YES
YES
YES
NO



-----Note-----

The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.
user: You are a mayor of Berlyatov. There are $n$ districts and $m$ two-way roads between them. The $i$-th road connects districts $x_i$ and $y_i$. The cost of travelling along this road is $w_i$. There is some path between each pair of districts, so the city is connected.

There are $k$ delivery routes in Berlyatov. The $i$-th route is going from the district $a_i$ to the district $b_i$. There is one courier on each route and the courier will always choose the cheapest (minimum by total cost) path from the district $a_i$ to the district $b_i$ to deliver products.

The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).

You can make at most one road to have cost zero (i.e. you choose at most one road and change its cost with $0$).

Let $d(x, y)$ be the cheapest cost of travel between districts $x$ and $y$.

Your task is to find the minimum total courier routes cost you can achieve, if you optimally select the some road and change its cost with $0$. In other words, you have to find the minimum possible value of $\sum\limits_{i = 1}^{k} d(a_i, b_i)$ after applying the operation described above optimally.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($2 \le n \le 1000$; $n - 1 \le m \le min(1000, \frac{n(n-1)}{2})$; $1 \le k \le 1000$) — the number of districts, the number of roads and the number of courier routes.

The next $m$ lines describe roads. The $i$-th road is given as three integers $x_i$, $y_i$ and $w_i$ ($1 \le x_i, y_i \le n$; $x_i \ne y_i$; $1 \le w_i \le 1000$), where $x_i$ and $y_i$ are districts the $i$-th road connects and $w_i$ is its cost. It is guaranteed that there is some path between each pair of districts, so the city is connected. It is also guaranteed that there is at most one road between each pair of districts.

The next $k$ lines describe courier routes. The $i$-th route is given as two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the districts of the $i$-th route. The route can go from the district to itself, some couriers routes can coincide (and you have to count them independently).


-----Output-----

Print one integer — the minimum total courier routes cost you can achieve (i.e. the minimum value $\sum\limits_{i=1}^{k} d(a_i, b_i)$, where $d(x, y)$ is the cheapest cost of travel between districts $x$ and $y$) if you can make some (at most one) road cost zero.


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

Output
22

Input
5 5 4
1 2 5
2 3 4
1 4 3
4 3 7
3 5 2
1 5
1 3
3 3
1 5

Output
13



-----Note-----

The picture corresponding to the first example:

[Image]

There, you can choose either the road $(2, 4)$ or the road $(4, 6)$. Both options lead to the total cost $22$.

The picture corresponding to the second example:

$A$

There, you can choose the road $(3, 4)$. This leads to the total cost $13$.
user: The only difference between easy and hard versions is the maximum value of $n$.

You are given a positive integer number $n$. You really love good numbers so you want to find the smallest good number greater than or equal to $n$.

The positive integer is called good if it can be represented as a sum of distinct powers of $3$ (i.e. no duplicates of powers of $3$ are allowed).

For example:  $30$ is a good number: $30 = 3^3 + 3^1$,  $1$ is a good number: $1 = 3^0$,  $12$ is a good number: $12 = 3^2 + 3^1$,  but $2$ is not a good number: you can't represent it as a sum of distinct powers of $3$ ($2 = 3^0 + 3^0$),  $19$ is not a good number: you can't represent it as a sum of distinct powers of $3$ (for example, the representations $19 = 3^2 + 3^2 + 3^0 = 3^2 + 3^1 + 3^1 + 3^1 + 3^0$ are invalid),  $20$ is also not a good number: you can't represent it as a sum of distinct powers of $3$ (for example, the representation $20 = 3^2 + 3^2 + 3^0 + 3^0$ is invalid). 

Note, that there exist other representations of $19$ and $20$ as sums of powers of $3$ but none of them consists of distinct powers of $3$.

For the given positive integer $n$ find such smallest $m$ ($n \le m$) that $m$ is a good number.

You have to answer $q$ independent queries.


-----Input-----

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

The only line of the query contains one integer $n$ ($1 \le n \le 10^4$).


-----Output-----

For each query, print such smallest integer $m$ (where $n \le m$) that $m$ is a good number.


-----Example-----
Input
7
1
2
6
13
14
3620
10000

Output
1
3
9
13
27
6561
19683
user: The only difference between easy and hard versions is constraints.

There are $n$ kids, each of them is reading a unique book. At the end of any day, the $i$-th kid will give his book to the $p_i$-th kid (in case of $i = p_i$ the kid will give his book to himself). It is guaranteed that all values of $p_i$ are distinct integers from $1$ to $n$ (i.e. $p$ is a permutation). The sequence $p$ doesn't change from day to day, it is fixed.

For example, if $n=6$ and $p=[4, 6, 1, 3, 5, 2]$ then at the end of the first day the book of the $1$-st kid will belong to the $4$-th kid, the $2$-nd kid will belong to the $6$-th kid and so on. At the end of the second day the book of the $1$-st kid will belong to the $3$-th kid, the $2$-nd kid will belong to the $2$-th kid and so on.

Your task is to determine the number of the day the book of the $i$-th child is returned back to him for the first time for every $i$ from $1$ to $n$.

Consider the following example: $p = [5, 1, 2, 4, 3]$. The book of the $1$-st kid will be passed to the following kids:  after the $1$-st day it will belong to the $5$-th kid,  after the $2$-nd day it will belong to the $3$-rd kid,  after the $3$-rd day it will belong to the $2$-nd kid,  after the $4$-th day it will belong to the $1$-st kid. 

So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

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. Then $q$ queries follow.

The first line of the query contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of kids in the query. The second line of the query contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct, i.e. $p$ is a permutation), where $p_i$ is the kid which will get the book of the $i$-th kid.

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


-----Output-----

For each query, print the answer on it: $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the number of the day the book of the $i$-th child is returned back to him for the first time in this query.


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

Output
1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4
user: There are $n$ Christmas trees on an infinite number line. The $i$-th tree grows at the position $x_i$. All $x_i$ are guaranteed to be distinct.

Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be occupied by anything.

There are $m$ people who want to celebrate Christmas. Let $y_1, y_2, \dots, y_m$ be the positions of people (note that all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct and all $y_j$ should be integer). You want to find such an arrangement of people that the value $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ is the minimum possible (in other words, the sum of distances to the nearest Christmas tree for all people should be minimized).

In other words, let $d_j$ be the distance from the $j$-th human to the nearest Christmas tree ($d_j = \min\limits_{i=1}^{n} |y_j - x_i|$). Then you need to choose such positions $y_1, y_2, \dots, y_m$ that $\sum\limits_{j=1}^{m} d_j$ is the minimum possible.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of Christmas trees and the number of people.

The second line of the input contains $n$ integers $x_1, x_2, \dots, x_n$ ($-10^9 \le x_i \le 10^9$), where $x_i$ is the position of the $i$-th Christmas tree. It is guaranteed that all $x_i$ are distinct.


-----Output-----

In the first line print one integer $res$ — the minimum possible value of $\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$ (in other words, the sum of distances to the nearest Christmas tree for all people).

In the second line print $m$ integers $y_1, y_2, \dots, y_m$ ($-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$), where $y_j$ is the position of the $j$-th human. All $y_j$ should be distinct and all values $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$ should be distinct.

If there are multiple answers, print any of them.


-----Examples-----
Input
2 6
1 5

Output
8
-1 2 6 4 0 3 

Input
3 5
0 3 1

Output
7
5 -2 4 -1 2