meetforever/GRPO_CL huggingface dataset:
user: Vasya is an active Internet user. One day he came across an Internet resource he liked, so he wrote its address in the notebook. We know that the address of the written resource has format: <protocol>://<domain>.ru[/<context>] 

where:  <protocol> can equal either "http" (without the quotes) or "ftp" (without the quotes),  <domain> is a non-empty string, consisting of lowercase English letters,  the /<context> part may not be present. If it is present, then <context> is a non-empty string, consisting of lowercase English letters. 

If string <context> isn't present in the address, then the additional character "/" isn't written. Thus, the address has either two characters "/" (the ones that go before the domain), or three (an extra one in front of the context).

When the boy came home, he found out that the address he wrote in his notebook had no punctuation marks. Vasya must have been in a lot of hurry and didn't write characters ":", "/", ".".

Help Vasya to restore the possible address of the recorded Internet resource.


-----Input-----

The first line contains a non-empty string that Vasya wrote out in his notebook. This line consists of lowercase English letters only. 

It is guaranteed that the given string contains at most 50 letters. It is guaranteed that the given string can be obtained from some correct Internet resource address, described above.


-----Output-----

Print a single line — the address of the Internet resource that Vasya liked. If there are several addresses that meet the problem limitations, you are allowed to print any of them.


-----Examples-----
Input
httpsunrux

Output
http://sun.ru/x

Input
ftphttprururu

Output
ftp://http.ru/ruru



-----Note-----

In the second sample there are two more possible answers: "ftp://httpruru.ru" and "ftp://httpru.ru/ru".
user: You are given an array a with n distinct integers. Construct an array b by permuting a such that for every non-empty subset of indices S = {x_1, x_2, ..., x_{k}} (1 ≤ x_{i} ≤ n, 0 < k < n) the sums of elements on that positions in a and b are different, i. e. $\sum_{i = 1}^{k} a_{x_{i}} \neq \sum_{i = 1}^{k} b_{x_{i}}$


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 22) — the size of the array.

The second line contains n space-separated distinct integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9) — the elements of the array.


-----Output-----

If there is no such array b, print -1.

Otherwise in the only line print n space-separated integers b_1, b_2, ..., b_{n}. Note that b must be a permutation of a.

If there are multiple answers, print any of them.


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

Output
2 1 

Input
4
1000 100 10 1

Output
100 1 1000 10



-----Note-----

An array x is a permutation of y, if we can shuffle elements of y such that it will coincide with x.

Note that the empty subset and the subset containing all indices are not counted.
user: As technologies develop, manufacturers are making the process of unlocking a phone as user-friendly as possible. To unlock its new phone, Arkady's pet dog Mu-mu has to bark the password once. The phone represents a password as a string of two lowercase English letters.

Mu-mu's enemy Kashtanka wants to unlock Mu-mu's phone to steal some sensible information, but it can only bark n distinct words, each of which can be represented as a string of two lowercase English letters. Kashtanka wants to bark several words (not necessarily distinct) one after another to pronounce a string containing the password as a substring. Tell if it's possible to unlock the phone in this way, or not.


-----Input-----

The first line contains two lowercase English letters — the password on the phone.

The second line contains single integer n (1 ≤ n ≤ 100) — the number of words Kashtanka knows.

The next n lines contain two lowercase English letters each, representing the words Kashtanka knows. The words are guaranteed to be distinct.


-----Output-----

Print "YES" if Kashtanka can bark several words in a line forming a string containing the password, and "NO" otherwise.

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


-----Examples-----
Input
ya
4
ah
oy
to
ha

Output
YES

Input
hp
2
ht
tp

Output
NO

Input
ah
1
ha

Output
YES



-----Note-----

In the first example the password is "ya", and Kashtanka can bark "oy" and then "ah", and then "ha" to form the string "oyahha" which contains the password. So, the answer is "YES".

In the second example Kashtanka can't produce a string containing password as a substring. Note that it can bark "ht" and then "tp" producing "http", but it doesn't contain the password "hp" as a substring.

In the third example the string "hahahaha" contains "ah" as a substring.
user: Given are integer sequence of length N, A = (A_1, A_2, \cdots, A_N), and an integer K.
For each X such that 1 \le X \le K, find the following value:
\left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X\right) \bmod 998244353

-----Constraints-----
 - All values in input are integers.
 -  2 \le N \le 2 \times 10^5
 -  1 \le K \le 300 
 -  1 \le A_i \le 10^8 

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 \cdots A_N

-----Output-----
Print K lines.
The X-th line should contain the value \left(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X \right) \bmod 998244353.

-----Sample Input-----
3 3
1 2 3

-----Sample Output-----
12
50
216

In the 1-st line, we should print (1+2)^1 + (1+3)^1 + (2+3)^1 = 3 + 4 + 5 = 12.
In the 2-nd line, we should print (1+2)^2 + (1+3)^2 + (2+3)^2 = 9 + 16 + 25 = 50.
In the 3-rd line, we should print (1+2)^3 + (1+3)^3 + (2+3)^3 = 27 + 64 + 125 = 216.
user: You are given two positive integers N and K. How many multisets of rational numbers satisfy all of the following conditions?
 - The multiset has exactly N elements and the sum of them is equal to K.
 - Each element of the multiset is one of 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots. In other words, each element can be represented as \frac{1}{2^i}\ (i = 0,1,\dots).
The answer may be large, so print it modulo 998244353.

-----Constraints-----
 - 1 \leq K \leq N \leq 3000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K

-----Output-----
Print the number of multisets of rational numbers that satisfy all of the given conditions modulo 998244353.

-----Sample Input-----
4 2

-----Sample Output-----
2

The following two multisets satisfy all of the given conditions:
 - {1, \frac{1}{2}, \frac{1}{4}, \frac{1}{4}}
 - {\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}}
user: We have a sequence A of N non-negative integers.
Compute the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i} over all sequences B of N non-negative integers whose sum is at most M, and print it modulo (10^9 + 7).
Here, \dbinom{B_i}{A_i}, the binomial coefficient, denotes the number of ways to choose A_i objects from B_i objects, and is 0 when B_i < A_i.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2000
 - 1 \leq M \leq 10^9
 - 0 \leq A_i \leq 2000

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 \ldots A_N

-----Output-----
Print the sum of \prod _{i = 1} ^N \dbinom{B_i}{A_i}, modulo (10^9 + 7).

-----Sample Input-----
3 5
1 2 1

-----Sample Output-----
8

There are four sequences B such that \prod _{i = 1} ^N \dbinom{B_i}{A_i} is at least 1:
 - B = \{1, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 1;
 - B = \{2, 2, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{2}{1} \times \dbinom{2}{2} \times \dbinom{1}{1} = 2;
 - B = \{1, 3, 1\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{3}{2} \times \dbinom{1}{1} = 3;
 - B = \{1, 2, 2\}, where \prod _{i = 1} ^N \dbinom{B_i}{A_i} = \dbinom{1}{1} \times \dbinom{2}{2} \times \dbinom{2}{1} = 2.
The sum of these is 1 + 2 + 3 + 2 = 8.
user: On the xy-plane, Snuke is going to travel from the point (x_s, y_s) to the point (x_t, y_t).
He can move in arbitrary directions with speed 1.
Here, we will consider him as a point without size.
There are N circular barriers deployed on the plane.
The center and the radius of the i-th barrier are (x_i, y_i) and r_i, respectively.
The barriers may overlap or contain each other.
A point on the plane is exposed to cosmic rays if the point is not within any of the barriers.
Snuke wants to avoid exposure to cosmic rays as much as possible during the travel.
Find the minimum possible duration of time he is exposed to cosmic rays during the travel.

-----Constraints-----
 - All input values are integers.
 - -10^9 ≤ x_s, y_s, x_t, y_t ≤ 10^9
 - (x_s, y_s) ≠ (x_t, y_t)
 - 1≤N≤1,000
 - -10^9 ≤ x_i, y_i ≤ 10^9
 - 1 ≤ r_i ≤ 10^9

-----Input-----
The input is given from Standard Input in the following format:
x_s y_s x_t y_t
N
x_1 y_1 r_1
x_2 y_2 r_2
:
x_N y_N r_N

-----Output-----
Print the minimum possible duration of time Snuke is exposed to cosmic rays during the travel.
The output is considered correct if the absolute or relative error is at most 10^{-9}.

-----Sample Input-----
-2 -2 2 2
1
0 0 1

-----Sample Output-----
3.6568542495

An optimal route is as follows:
user: Given positive integers N, K and M, solve the following problem for every integer x between 1 and N (inclusive):
 - Find the number, modulo M, of non-empty multisets containing between 0 and K (inclusive) instances of each of the integers 1, 2, 3 \cdots, N such that the average of the elements is x.

-----Constraints-----
 - 1 \leq N, K \leq 100
 - 10^8 \leq M \leq 10^9 + 9
 - M is prime.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K M

-----Output-----
Use the following format:
c_1
c_2
:
c_N

Here, c_x should be the number, modulo M, of multisets such that the average of the elements is x.

-----Sample Input-----
3 1 998244353

-----Sample Output-----
1
3
1

Consider non-empty multisets containing between 0 and 1 instance(s) of each of the integers between 1 and 3. Among them, there are:
 - one multiset such that the average of the elements is k = 1: \{1\};
 - three multisets such that the average of the elements is k = 2: \{2\}, \{1, 3\}, \{1, 2, 3\};
 - one multiset such that the average of the elements is k = 3: \{3\}.
user: You are given an array $a$ of length $n$ consisting of zeros. You perform $n$ actions with this array: during the $i$-th action, the following sequence of operations appears:  Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;  Let this segment be $[l; r]$. If $r-l+1$ is odd (not divisible by $2$) then assign (set) $a[\frac{l+r}{2}] := i$ (where $i$ is the number of the current action), otherwise (if $r-l+1$ is even) assign (set) $a[\frac{l+r-1}{2}] := i$. 

Consider the array $a$ of length $5$ (initially $a=[0, 0, 0, 0, 0]$). Then it changes as follows:  Firstly, we choose the segment $[1; 5]$ and assign $a[3] := 1$, so $a$ becomes $[0, 0, 1, 0, 0]$;  then we choose the segment $[1; 2]$ and assign $a[1] := 2$, so $a$ becomes $[2, 0, 1, 0, 0]$;  then we choose the segment $[4; 5]$ and assign $a[4] := 3$, so $a$ becomes $[2, 0, 1, 3, 0]$;  then we choose the segment $[2; 2]$ and assign $a[2] := 4$, so $a$ becomes $[2, 4, 1, 3, 0]$;  and at last we choose the segment $[5; 5]$ and assign $a[5] := 5$, so $a$ becomes $[2, 4, 1, 3, 5]$. 

Your task is to find the array $a$ of length $n$ after performing all $n$ actions. Note that the answer exists and unique.

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 only line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$.

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


-----Output-----

For each test case, print the answer — the array $a$ of length $n$ after performing $n$ actions described in the problem statement. Note that the answer exists and unique.


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

Output
1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6
user: There are $n$ athletes in front of you. Athletes are numbered from $1$ to $n$ from left to right. You know the strength of each athlete — the athlete number $i$ has the strength $s_i$.

You want to split all athletes into two teams. Each team must have at least one athlete, and each athlete must be exactly in one team.

You want the strongest athlete from the first team to differ as little as possible from the weakest athlete from the second team. Formally, you want to split the athletes into two teams $A$ and $B$ so that the value $|\max(A) - \min(B)|$ is as small as possible, where $\max(A)$ is the maximum strength of an athlete from team $A$, and $\min(B)$ is the minimum strength of an athlete from team $B$.

For example, if $n=5$ and the strength of the athletes is $s=[3, 1, 2, 6, 4]$, then one of the possible split into teams is:   first team: $A = [1, 2, 4]$,  second team: $B = [3, 6]$. 

In this case, the value $|\max(A) - \min(B)|$ will be equal to $|4-3|=1$. This example illustrates one of the ways of optimal split into two teams.

Print the minimum value $|\max(A) - \min(B)|$.


-----Input-----

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

Each test case consists of two lines. 

The first line contains positive integer $n$ ($2 \le n \le 50$) — number of athletes. 

The second line contains $n$ positive integers $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le 1000$), where $s_i$ — is the strength of the $i$-th athlete. Please note that $s$ values may not be distinct.


-----Output-----

For each test case print one integer — the minimum value of $|\max(A) - \min(B)|$ with the optimal split of all athletes into two teams. Each of the athletes must be a member of exactly one of the two teams.


-----Example-----
Input
5
5
3 1 2 6 4
6
2 1 3 2 4 3
4
7 9 3 1
2
1 1000
3
100 150 200

Output
1
0
2
999
50



-----Note-----

The first test case was explained in the statement. In the second test case, one of the optimal splits is $A=[2, 1]$, $B=[3, 2, 4, 3]$, so the answer is $|2-2|=0$.
user: You are given an undirected unweighted graph consisting of $n$ vertices and $m$ edges (which represents the map of Bertown) and the array of prices $p$ of length $m$. It is guaranteed that there is a path between each pair of vertices (districts).

Mike has planned a trip from the vertex (district) $a$ to the vertex (district) $b$ and then from the vertex (district) $b$ to the vertex (district) $c$. He can visit the same district twice or more. But there is one issue: authorities of the city want to set a price for using the road so if someone goes along the road then he should pay the price corresponding to this road (he pays each time he goes along the road). The list of prices that will be used $p$ is ready and they just want to distribute it between all roads in the town in such a way that each price from the array corresponds to exactly one road.

You are a good friend of Mike (and suddenly a mayor of Bertown) and want to help him to make his trip as cheap as possible. So, your task is to distribute prices between roads in such a way that if Mike chooses the optimal path then the price of the trip is the minimum possible. Note that you cannot rearrange prices after the start of the trip.

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 the test case contains five integers $n, m, a, b$ and $c$ ($2 \le n \le 2 \cdot 10^5$, $n-1 \le m \le min(\frac{n(n-1)}{2}, 2 \cdot 10^5)$, $1 \le a, b, c \le n$) — the number of vertices, the number of edges and districts in Mike's trip.

The second line of the test case contains $m$ integers $p_1, p_2, \dots, p_m$ ($1 \le p_i \le 10^9$), where $p_i$ is the $i$-th price from the array.

The following $m$ lines of the test case denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), which are the indices of vertices connected by the edge. There are no loops or multiple edges in the given graph, i. e. for each pair ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the array of edges, and for each pair $(v_i, u_i)$ the condition $v_i \ne u_i$ is satisfied. It is guaranteed that the given graph is connected.

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


-----Output-----

For each test case, print the answer — the minimum possible price of Mike's trip if you distribute prices between edges optimally.


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

Output
7
12



-----Note-----

One of the possible solution to the first test case of the example:

[Image]

One of the possible solution to the second test case of the example:

[Image]
user: We guessed a permutation $p$ consisting of $n$ integers. The permutation of length $n$ is the array of length $n$ where each element from $1$ to $n$ appears exactly once. This permutation is a secret for you.

For each position $r$ from $2$ to $n$ we chose some other index $l$ ($l < r$) and gave you the segment $p_l, p_{l + 1}, \dots, p_r$ in sorted order (i.e. we rearranged the elements of this segment in a way that the elements of this segment are sorted). Thus, you are given exactly $n-1$ segments of the initial permutation but elements inside each segment are sorted. The segments are given to you in random order.

For example, if the secret permutation is $p=[3, 1, 4, 6, 2, 5]$ then the possible given set of segments can be:  $[2, 5, 6]$  $[4, 6]$  $[1, 3, 4]$  $[1, 3]$  $[1, 2, 4, 6]$ 

Your task is to find any suitable permutation (i.e. any permutation corresponding to the given input data). It is guaranteed that the input data corresponds to some permutation (i.e. such permutation exists).

You have to answer $t$ independent test cases.


-----Input-----

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

The first line of the test case contains one integer $n$ ($2 \le n \le 200$) — the length of the permutation.

The next $n-1$ lines describe given segments.

The $i$-th line contains the description of the $i$-th segment. The line starts with the integer $k_i$ ($2 \le k_i \le n$) — the length of the $i$-th segment. Then $k_i$ integers follow. All integers in a line are distinct, sorted in ascending order, between $1$ and $n$, inclusive.

It is guaranteed that the required $p$ exists for each test case.

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


-----Output-----

For each test case, print the answer: $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, all $p_i$ should be distinct) — any suitable permutation (i.e. any permutation corresponding to the test case input).


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

Output
3 1 4 6 2 5 
3 2 1 4 5 
2 1 6 3 5 4 7 
1 2 
2 5 3 4 1
user: Polycarp analyzes the prices of the new berPhone. At his disposal are the prices for $n$ last days: $a_1, a_2, \dots, a_n$, where $a_i$ is the price of berPhone on the day $i$.

Polycarp considers the price on the day $i$ to be bad if later (that is, a day with a greater number) berPhone was sold at a lower price. For example, if $n=6$ and $a=[3, 9, 4, 6, 7, 5]$, then the number of days with a bad price is $3$ — these are days $2$ ($a_2=9$), $4$ ($a_4=6$) and $5$ ($a_5=7$).

Print the number of days with a bad price.

You have to answer $t$ independent data sets.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10000$) — the number of sets of input data in the test. Input data sets must be processed independently, one after another.

Each input data set consists of two lines. The first line contains an integer $n$ ($1 \le n \le 150000$) — the number of days. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$), where $a_i$ is the price on the $i$-th day.

It is guaranteed that the sum of $n$ over all data sets in the test does not exceed $150000$.


-----Output-----

Print $t$ integers, the $j$-th of which should be equal to the number of days with a bad price in the $j$-th input data set.


-----Example-----
Input
5
6
3 9 4 6 7 5
1
1000000
2
2 1
10
31 41 59 26 53 58 97 93 23 84
7
3 2 1 2 3 4 5

Output
3
0
1
8
2
user: You are given two strings $s$ and $t$ both of length $n$ and both consisting of lowercase Latin letters.

In one move, you can choose any length $len$ from $1$ to $n$ and perform the following operation:   Choose any contiguous substring of the string $s$ of length $len$ and reverse it;  at the same time choose any contiguous substring of the string $t$ of length $len$ and reverse it as well. 

Note that during one move you reverse exactly one substring of the string $s$ and exactly one substring of the string $t$.

Also note that borders of substrings you reverse in $s$ and in $t$ can be different, the only restriction is that you reverse the substrings of equal length. For example, if $len=3$ and $n=5$, you can reverse $s[1 \dots 3]$ and $t[3 \dots 5]$, $s[2 \dots 4]$ and $t[2 \dots 4]$, but not $s[1 \dots 3]$ and $t[1 \dots 2]$.

Your task is to say if it is possible to make strings $s$ and $t$ equal after some (possibly, empty) sequence of moves.

You have to answer $q$ independent test cases.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — 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 2 \cdot 10^5$) — the length of $s$ and $t$.

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

The third line of the test case contains one string $t$ consisting of $n$ lowercase Latin letters.

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


-----Output-----

For each test case, print the answer on it — "YES" (without quotes) if it is possible to make strings $s$ and $t$ equal after some (possibly, empty) sequence of moves and "NO" otherwise.


-----Example-----
Input
4
4
abcd
abdc
5
ababa
baaba
4
asdf
asdg
4
abcd
badc

Output
NO
YES
NO
YES