meetforever/GRPO_CL huggingface dataset:
user: There are N pinholes on the xy-plane. The i-th pinhole is located at (x_i,y_i).
We will denote the Manhattan distance between the i-th and j-th pinholes as d(i,j)(=|x_i-x_j|+|y_i-y_j|).
You have a peculiar pair of compasses, called Manhattan Compass.
This instrument always points at two of the pinholes.
The two legs of the compass are indistinguishable, thus we do not distinguish the following two states: the state where the compass points at the p-th and q-th pinholes, and the state where it points at the q-th and p-th pinholes.
When the compass points at the p-th and q-th pinholes and d(p,q)=d(p,r), one of the legs can be moved so that the compass will point at the p-th and r-th pinholes.
Initially, the compass points at the a-th and b-th pinholes.
Find the number of the pairs of pinholes that can be pointed by the compass.

-----Constraints-----
 - 2≦N≦10^5
 - 1≦x_i, y_i≦10^9
 - 1≦a < b≦N
 - When i ≠ j, (x_i, y_i) ≠ (x_j, y_j)
 - x_i and y_i are integers.

-----Input-----
The input is given from Standard Input in the following format:
N a b
x_1 y_1
:
x_N y_N

-----Output-----
Print the number of the pairs of pinholes that can be pointed by the compass.

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

-----Sample Output-----
4

Initially, the compass points at the first and second pinholes.
Since d(1,2) = d(1,3), the compass can be moved so that it will point at the first and third pinholes.
Since d(1,3) = d(3,4), the compass can also point at the third and fourth pinholes.
Since d(1,2) = d(2,5), the compass can also point at the second and fifth pinholes.
No other pairs of pinholes can be pointed by the compass, thus the answer is 4.
user: There are N towns on a line running east-west.
The towns are numbered 1 through N, in order from west to east.
Each point on the line has a one-dimensional coordinate, and a point that is farther east has a greater coordinate value.
The coordinate of town i is X_i.
You are now at town 1, and you want to visit all the other towns.
You have two ways to travel:
 - Walk on the line.
Your fatigue level increases by A each time you travel a distance of 1, regardless of direction.
 - Teleport to any location of your choice.
Your fatigue level increases by B, regardless of the distance covered.
Find the minimum possible total increase of your fatigue level when you visit all the towns in these two ways.

-----Constraints-----
 - All input values are integers.
 - 2≤N≤10^5
 - 1≤X_i≤10^9
 - For all i(1≤i≤N-1), X_i<X_{i+1}.
 - 1≤A≤10^9
 - 1≤B≤10^9

-----Input-----
The input is given from Standard Input in the following format:
N A B
X_1 X_2 ... X_N

-----Output-----
Print the minimum possible total increase of your fatigue level when you visit all the towns.

-----Sample Input-----
4 2 5
1 2 5 7

-----Sample Output-----
11

From town 1, walk a distance of 1 to town 2, then teleport to town 3, then walk a distance of 2 to town 4.
The total increase of your fatigue level in this case is 2×1+5+2×2=11, which is the minimum possible value.
user: You are given $n$ arrays that can have different sizes. You also have a table with $w$ columns and $n$ rows. The $i$-th array is placed horizontally in the $i$-th row. You can slide each array within its row as long as it occupies several consecutive cells and lies completely inside the table.

You need to find the maximum sum of the integers in the $j$-th column for each $j$ from $1$ to $w$ independently.

 [Image] Optimal placements for columns $1$, $2$ and $3$ are shown on the pictures from left to right. 

Note that you can exclude any array out of a column provided it remains in the window. In this case its value is considered to be zero.


-----Input-----

The first line contains two integers $n$ ($1 \le n \le 10^{6}$) and $w$ ($1 \le w \le 10^{6}$) — the number of arrays and the width of the table.

Each of the next $n$ lines consists of an integer $l_{i}$ ($1 \le l_{i} \le w$), the length of the $i$-th array, followed by $l_{i}$ integers $a_{i1}, a_{i2}, \ldots, a_{il_i}$ ($-10^{9} \le a_{ij} \le 10^{9}$) — the elements of the array.

The total length of the arrays does no exceed $10^{6}$.


-----Output-----

Print $w$ integers, the $i$-th of them should be the maximum sum for column $i$.


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

Output
10 15 16 

Input
2 2
2 7 8
1 -8

Output
7 8 



-----Note-----

Illustration for the first example is in the statement.
user: Masha and Grisha like studying sets of positive integers.

One day Grisha has written a set A containing n different integers a_{i} on a blackboard. Now he asks Masha to create a set B containing n different integers b_{j} such that all n^2 integers that can be obtained by summing up a_{i} and b_{j} for all possible pairs of i and j are different.

Both Masha and Grisha don't like big numbers, so all numbers in A are from 1 to 10^6, and all numbers in B must also be in the same range.

Help Masha to create the set B that satisfies Grisha's requirement.


-----Input-----

Input data contains multiple test cases. The first line contains an integer t — the number of test cases (1 ≤ t ≤ 100).

Each test case is described in the following way: the first line of the description contains one integer n — the number of elements in A (1 ≤ n ≤ 100).

The second line contains n integers a_{i} — the elements of A (1 ≤ a_{i} ≤ 10^6). 


-----Output-----

For each test first print the answer:   NO, if Masha's task is impossible to solve, there is no way to create the required set B.  YES, if there is the way to create the required set. In this case the second line must contain n different positive integers b_{j} — elements of B (1 ≤ b_{j} ≤ 10^6). If there are several possible sets, output any of them. 


-----Example-----
Input
3
3
1 10 100
1
1
2
2 4

Output
YES
1 2 3 
YES
1 
YES
1 2
user: Let us define two functions f and g on positive integer numbers.  $f(n) = \text{product of non-zero digits of} n$

$g(n) = \left\{\begin{array}{ll}{n} & {\text{if} n < 10} \\{g(f(n))} & {\text{otherwise}} \end{array} \right.$ 

You need to process Q queries. In each query, you will be given three integers l, r and k. You need to print the number of integers x between l and r inclusive, such that g(x) = k. 


-----Input-----

The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 10^5) representing the number of queries. 

Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 10^6, 1 ≤ k ≤ 9).


-----Output-----

For each query, print a single line containing the answer for that query.


-----Examples-----
Input
4
22 73 9
45 64 6
47 55 7
2 62 4

Output
1
4
0
8

Input
4
82 94 6
56 67 4
28 59 9
39 74 4

Output
3
1
1
5



-----Note-----

In the first example:  g(33) = 9 as g(33) = g(3 × 3) = g(9) = 9  g(47) = g(48) = g(60) = g(61) = 6  There are no such integers between 47 and 55.  g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4
user: Toad Pimple has an array of integers $a_1, a_2, \ldots, a_n$.

We say that $y$ is reachable from $x$ if $x<y$ and there exists an integer array $p$ such that $x = p_1 < p_2 < \ldots < p_k=y$, and $a_{p_i}\, \&\, a_{p_{i+1}} > 0$ for all integers $i$ such that $1 \leq i < k$.

Here $\&$ denotes the bitwise AND operation.

You are given $q$ pairs of indices, check reachability for each of them.


-----Input-----

The first line contains two integers $n$ and $q$ ($2 \leq n \leq 300\,000$, $1 \leq q \leq 300\,000$) — the number of integers in the array and the number of queries you need to answer.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 300\,000$) — the given array.

The next $q$ lines contain two integers each. The $i$-th of them contains two space-separated integers $x_i$ and $y_i$ ($1 \leq x_i < y_i \leq n$). You need to check if $y_i$ is reachable from $x_i$. 


-----Output-----

Output $q$ lines. In the $i$-th of them print "Shi" if $y_i$ is reachable from $x_i$, otherwise, print "Fou".


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

Output
Fou
Shi
Shi



-----Note-----

In the first example, $a_3 = 0$. You can't reach it, because AND with it is always zero. $a_2\, \&\, a_4 > 0$, so $4$ is reachable from $2$, and to go from $1$ to $4$ you can use $p = [1, 2, 4]$.
user: Kalila and Dimna are two jackals living in a huge jungle. One day they decided to join a logging factory in order to make money. 

The manager of logging factory wants them to go to the jungle and cut n trees with heights a_1, a_2, ..., a_{n}. They bought a chain saw from a shop. Each time they use the chain saw on the tree number i, they can decrease the height of this tree by one unit. Each time that Kalila and Dimna use the chain saw, they need to recharge it. Cost of charging depends on the id of the trees which have been cut completely (a tree is cut completely if its height equal to 0). If the maximum id of a tree which has been cut completely is i (the tree that have height a_{i} in the beginning), then the cost of charging the chain saw would be b_{i}. If no tree is cut completely, Kalila and Dimna cannot charge the chain saw. The chainsaw is charged in the beginning. We know that for each i < j, a_{i} < a_{j} and b_{i} > b_{j} and also b_{n} = 0 and a_1 = 1. Kalila and Dimna want to cut all the trees completely, with minimum cost. 

They want you to help them! Will you?


-----Input-----

The first line of input contains an integer n (1 ≤ n ≤ 10^5). The second line of input contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). The third line of input contains n integers b_1, b_2, ..., b_{n} (0 ≤ b_{i} ≤ 10^9).

It's guaranteed that a_1 = 1, b_{n} = 0, a_1 < a_2 < ... < a_{n} and b_1 > b_2 > ... > b_{n}.


-----Output-----

The only line of output must contain the minimum cost of cutting all the trees completely.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


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

Output
25

Input
6
1 2 3 10 20 30
6 5 4 3 2 0

Output
138
user: For an array $b$ of length $m$ we define the function $f$ as  $ f(b) = \begin{cases} b[1] & \quad \text{if } m = 1 \\ f(b[1] \oplus b[2],b[2] \oplus b[3],\dots,b[m-1] \oplus b[m]) & \quad \text{otherwise,} \end{cases} $ 

where $\oplus$ is bitwise exclusive OR.

For example, $f(1,2,4,8)=f(1\oplus2,2\oplus4,4\oplus8)=f(3,6,12)=f(3\oplus6,6\oplus12)=f(5,10)=f(5\oplus10)=f(15)=15$

You are given an array $a$ and a few queries. Each query is represented as two integers $l$ and $r$. The answer is the maximum value of $f$ on all continuous subsegments of the array $a_l, a_{l+1}, \ldots, a_r$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 5000$) — the length of $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 2^{30}-1$) — the elements of the array.

The third line contains a single integer $q$ ($1 \le q \le 100\,000$) — the number of queries.

Each of the next $q$ lines contains a query represented as two integers $l$, $r$ ($1 \le l \le r \le n$).


-----Output-----

Print $q$ lines — the answers for the queries.


-----Examples-----
Input
3
8 4 1
2
2 3
1 2

Output
5
12

Input
6
1 2 4 8 16 32
4
1 6
2 5
3 4
1 2

Output
60
30
12
3



-----Note-----

In first sample in both queries the maximum value of the function is reached on the subsegment that is equal to the whole segment.

In second sample, optimal segment for first query are $[3,6]$, for second query — $[2,5]$, for third — $[3,4]$, for fourth — $[1,2]$.
user: Vasya has written some permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, so for all $1 \leq i \leq n$ it is true that $1 \leq p_i \leq n$ and all $p_1, p_2, \ldots, p_n$ are different. After that he wrote $n$ numbers $next_1, next_2, \ldots, next_n$. The number $next_i$ is equal to the minimal index $i < j \leq n$, such that $p_j > p_i$. If there is no such $j$ let's let's define as $next_i = n + 1$.

In the evening Vasya went home from school and due to rain, his notebook got wet. Now it is impossible to read some written numbers. Permutation and some values $next_i$ are completely lost! If for some $i$ the value $next_i$ is lost, let's say that $next_i = -1$.

You are given numbers $next_1, next_2, \ldots, next_n$ (maybe some of them are equal to $-1$). Help Vasya to find such permutation $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, that he can write it to the notebook and all numbers $next_i$, which are not equal to $-1$, will be correct. 


-----Input-----

The first line contains one integer $t$ — the number of test cases ($1 \leq t \leq 100\,000$).

Next $2 \cdot t$ lines contains the description of test cases,two lines for each. The first line contains one integer $n$ — the length of the permutation, written by Vasya ($1 \leq n \leq 500\,000$). The second line contains $n$ integers $next_1, next_2, \ldots, next_n$, separated by spaces ($next_i = -1$ or $i < next_i \leq n + 1$).

It is guaranteed, that the sum of $n$ in all test cases doesn't exceed $500\,000$.

In hacks you can only use one test case, so $T = 1$.


-----Output-----

Print $T$ lines, in $i$-th of them answer to the $i$-th test case.

If there is no such permutations $p_1, p_2, \ldots, p_n$ of integers from $1$ to $n$, that Vasya could write, print the only number $-1$.

In the other case print $n$ different integers $p_1, p_2, \ldots, p_n$, separated by spaces ($1 \leq p_i \leq n$). All defined values of $next_i$ which are not equal to $-1$ should be computed correctly $p_1, p_2, \ldots, p_n$ using defenition given in the statement of the problem. If there exists more than one solution you can find any of them.


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

Output
1 2 3
2 1
2 1 3
-1
1
3 2 1 4



-----Note-----

In the first test case for permutation $p = [1, 2, 3]$ Vasya should write $next = [2, 3, 4]$, because each number in permutation is less than next. It's easy to see, that it is the only satisfying permutation.

In the third test case, any permutation can be the answer because all numbers $next_i$ are lost.

In the fourth test case, there is no satisfying permutation, so the answer is $-1$.
user: Koa the Koala and her best friend want to play a game.

The game starts with an array $a$ of length $n$ consisting of non-negative integers. Koa and her best friend move in turns and each have initially a score equal to $0$. Koa starts.

Let's describe a move in the game:  During his move, a player chooses any element of the array and removes it from this array, xor-ing it with the current score of the player.

 More formally: if the current score of the player is $x$ and the chosen element is $y$, his new score will be $x \oplus y$. Here $\oplus$ denotes bitwise XOR operation.

 Note that after a move element $y$ is removed from $a$.

  The game ends when the array is empty. 

At the end of the game the winner is the player with the maximum score. If both players have the same score then it's a draw.

If both players play optimally find out whether Koa will win, lose or draw the game.


-----Input-----

Each test contains multiple test cases. The first line contains $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains the integer $n$ ($1 \le n \le 10^5$) — the length of $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — elements of $a$.

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


-----Output-----

For each test case print:  WIN if Koa will win the game.  LOSE if Koa will lose the game.  DRAW if the game ends in a draw. 


-----Examples-----
Input
3
3
1 2 2
3
2 2 3
5
0 0 0 2 2

Output
WIN
LOSE
DRAW

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

Output
WIN
WIN
DRAW
WIN



-----Note-----

In testcase $1$ of the first sample we have:

$a = [1, 2, 2]$. Here Koa chooses $1$, other player has to choose $2$, Koa chooses another $2$. Score for Koa is $1 \oplus 2 = 3$ and score for other player is $2$ so Koa wins.
user: You have an array $a$ of length $n$. For every positive integer $x$ you are going to perform the following operation during the $x$-th second:

  Select some distinct indices $i_{1}, i_{2}, \ldots, i_{k}$ which are between $1$ and $n$ inclusive, and add $2^{x-1}$ to each corresponding position of $a$. Formally, $a_{i_{j}} := a_{i_{j}} + 2^{x-1}$ for $j = 1, 2, \ldots, k$. Note that you are allowed to not select any indices at all. 

You have to make $a$ nondecreasing as fast as possible. Find the smallest number $T$ such that you can make the array nondecreasing after at most $T$ seconds.

Array $a$ is nondecreasing if and only if $a_{1} \le a_{2} \le \ldots \le a_{n}$.

You have to answer $t$ independent test cases.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases.

The first line of each test case contains single integer $n$ ($1 \le n \le 10^{5}$) — the length of array $a$. It is guaranteed that the sum of values of $n$ over all test cases in the input does not exceed $10^{5}$.

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($-10^{9} \le a_{i} \le 10^{9}$).


-----Output-----

For each test case, print the minimum number of seconds in which you can make $a$ nondecreasing.


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

Output
2
0
3



-----Note-----

In the first test case, if you select indices $3, 4$ at the $1$-st second and $4$ at the $2$-nd second, then $a$ will become $[1, 7, 7, 8]$. There are some other possible ways to make $a$ nondecreasing in $2$ seconds, but you can't do it faster.

In the second test case, $a$ is already nondecreasing, so answer is $0$.

In the third test case, if you do nothing at first $2$ seconds and select index $2$ at the $3$-rd second, $a$ will become $[0, 0]$.
user: Leha like all kinds of strange things. Recently he liked the function F(n, k). Consider all possible k-element subsets of the set [1, 2, ..., n]. For subset find minimal element in it. F(n, k) — mathematical expectation of the minimal element among all k-element subsets.

But only function does not interest him. He wants to do interesting things with it. Mom brought him two arrays A and B, each consists of m integers. For all i, j such that 1 ≤ i, j ≤ m the condition A_{i} ≥ B_{j} holds. Help Leha rearrange the numbers in the array A so that the sum $\sum_{i = 1}^{m} F(A_{i}^{\prime}, B_{i})$ is maximally possible, where A' is already rearranged array.


-----Input-----

First line of input data contains single integer m (1 ≤ m ≤ 2·10^5) — length of arrays A and B.

Next line contains m integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^9) — array A.

Next line contains m integers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ 10^9) — array B.


-----Output-----

Output m integers a'_1, a'_2, ..., a'_{m} — array A' which is permutation of the array A.


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

Output
4 7 3 5 3

Input
7
4 6 5 8 8 2 6
2 1 2 2 1 1 2

Output
2 6 4 5 8 8 6
user: You are working for the Gryzzl company, headquartered in Pawnee, Indiana.

The new national park has been opened near Pawnee recently and you are to implement a geolocation system, so people won't get lost. The concept you developed is innovative and minimalistic. There will be $n$ antennas located somewhere in the park. When someone would like to know their current location, their Gryzzl hologram phone will communicate with antennas and obtain distances from a user's current location to all antennas.

Knowing those distances and antennas locations it should be easy to recover a user's location... Right? Well, almost. The only issue is that there is no way to distinguish antennas, so you don't know, which distance corresponds to each antenna. Your task is to find a user's location given as little as all antennas location and an unordered multiset of distances.


-----Input-----

The first line of input contains a single integer $n$ ($2 \leq n \leq 10^5$) which is the number of antennas.

The following $n$ lines contain coordinates of antennas, $i$-th line contain two integers $x_i$ and $y_i$ ($0 \leq x_i,y_i \leq 10^8$). It is guaranteed that no two antennas coincide.

The next line of input contains integer $m$ ($1 \leq n \cdot m \leq 10^5$), which is the number of queries to determine the location of the user.

Following $m$ lines contain $n$ integers $0 \leq d_1 \leq d_2 \leq \dots \leq d_n \leq 2 \cdot 10^{16}$ each. These integers form a multiset of squared distances from unknown user's location $(x;y)$ to antennas.

For all test cases except the examples it is guaranteed that all user's locations $(x;y)$ were chosen uniformly at random, independently from each other among all possible integer locations having $0 \leq x, y \leq 10^8$.


-----Output-----

For each query output $k$, the number of possible a user's locations matching the given input and then output the list of these locations in lexicographic order.

It is guaranteed that the sum of all $k$ over all points does not exceed $10^6$.


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

Output
1 1 1 

Input
4
0 0
0 1
1 0
1 1
2
0 1 1 2
2 5 5 8

Output
4 0 0 0 1 1 0 1 1 
4 -1 -1 -1 2 2 -1 2 2 



-----Note-----

As you see in the second example, although initially a user's location is picked to have non-negative coordinates, you have to output all possible integer locations.
user: There are N barbecue restaurants along a street.
The restaurants are numbered 1 through N from west to east, and the distance between restaurant i and restaurant i+1 is A_i.
Joisino has M tickets, numbered 1 through M.
Every barbecue restaurant offers barbecue meals in exchange for these tickets.
Restaurant i offers a meal of deliciousness B_{i,j} in exchange for ticket j.
Each ticket can only be used once, but any number of tickets can be used at a restaurant.
Joisino wants to have M barbecue meals by starting from a restaurant of her choice, then repeatedly traveling to another barbecue restaurant and using unused tickets at the restaurant at her current location.
Her eventual happiness is calculated by the following formula: "(The total deliciousness of the meals eaten) - (The total distance traveled)".
Find her maximum possible eventual happiness.

-----Constraints-----
 - All input values are integers.
 - 2≤N≤5×10^3
 - 1≤M≤200
 - 1≤A_i≤10^9
 - 1≤B_{i,j}≤10^9

-----Input-----
The input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_{N-1}
B_{1,1} B_{1,2} ... B_{1,M}
B_{2,1} B_{2,2} ... B_{2,M}
:
B_{N,1} B_{N,2} ... B_{N,M}

-----Output-----
Print Joisino's maximum possible eventual happiness.

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

-----Sample Output-----
11

The eventual happiness can be maximized by the following strategy: start from restaurant 1 and use tickets 1 and 3, then move to restaurant 2 and use tickets 2 and 4.