meetforever/GRPO_CL huggingface dataset:
user: You are given a sequence of n integers a_1, a_2, ..., a_{n}. 

Determine a real number x such that the weakness of the sequence a_1 - x, a_2 - x, ..., a_{n} - x is as small as possible.

The weakness of a sequence is defined as the maximum value of the poorness over all segments (contiguous subsequences) of a sequence.

The poorness of a segment is defined as the absolute value of sum of the elements of segment.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 200 000), the length of a sequence.

The second line contains n integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 10 000).


-----Output-----

Output a real number denoting the minimum possible weakness of a_1 - x, a_2 - x, ..., a_{n} - x. Your answer will be considered correct if its relative or absolute error doesn't exceed 10^{ - 6}.


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

Output
1.000000000000000

Input
4
1 2 3 4

Output
2.000000000000000

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

Output
4.500000000000000



-----Note-----

For the first case, the optimal value of x is 2 so the sequence becomes  - 1, 0, 1 and the max poorness occurs at the segment "-1" or segment "1". The poorness value (answer) equals to 1 in this case. 

For the second sample the optimal value of x is 2.5 so the sequence becomes  - 1.5,  - 0.5, 0.5, 1.5 and the max poorness occurs on segment "-1.5 -0.5" or "0.5 1.5". The poorness value (answer) equals to 2 in this case.
user: An array of integers $p_{1},p_{2}, \ldots,p_{n}$ is called a permutation if it contains each number from $1$ to $n$ exactly once. For example, the following arrays are permutations: $[3,1,2], [1], [1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2], [1,1], [2,3,4]$.

There is a hidden permutation of length $n$.

For each index $i$, you are given $s_{i}$, which equals to the sum of all $p_{j}$ such that $j < i$ and $p_{j} < p_{i}$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

Your task is to restore the permutation.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the size of the permutation.

The second line contains $n$ integers $s_{1}, s_{2}, \ldots, s_{n}$ ($0 \le s_{i} \le \frac{n(n-1)}{2}$).

It is guaranteed that the array $s$ corresponds to a valid permutation of length $n$.


-----Output-----

Print $n$ integers $p_{1}, p_{2}, \ldots, p_{n}$ — the elements of the restored permutation. We can show that the answer is always unique.


-----Examples-----
Input
3
0 0 0

Output
3 2 1

Input
2
0 1

Output
1 2

Input
5
0 1 1 1 10

Output
1 4 3 2 5



-----Note-----

In the first example for each $i$ there is no index $j$ satisfying both conditions, hence $s_i$ are always $0$.

In the second example for $i = 2$ it happens that $j = 1$ satisfies the conditions, so $s_2 = p_1$.

In the third example for $i = 2, 3, 4$ only $j = 1$ satisfies the conditions, so $s_2 = s_3 = s_4 = 1$. For $i = 5$ all $j = 1, 2, 3, 4$ are possible, so $s_5 = p_1 + p_2 + p_3 + p_4 = 10$.
user: Bob has a permutation of integers from 1 to n. Denote this permutation as p. The i-th element of p will be denoted as p_{i}. For all pairs of distinct integers i, j between 1 and n, he wrote the number a_{i}, j = min(p_{i}, p_{j}). He writes a_{i}, i = 0 for all integer i from 1 to n.

Bob gave you all the values of a_{i}, j that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.


-----Input-----

The first line of the input will contain a single integer n (2 ≤ n ≤ 50).

The next n lines will contain the values of a_{i}, j. The j-th number on the i-th line will represent a_{i}, j. The i-th number on the i-th line will be 0. It's guaranteed that a_{i}, j = a_{j}, i and there is at least one solution consistent with the information given.


-----Output-----

Print n space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.


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

Output
2 1

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

Output
2 5 4 1 3



-----Note-----

In the first case, the answer can be {1, 2} or {2, 1}.

In the second case, another possible answer is {2, 4, 5, 1, 3}.
user: You are given a directed graph of $n$ vertices and $m$ edges. Vertices are numbered from $1$ to $n$. There is a token in vertex $1$.

The following actions are allowed:   Token movement. To move the token from vertex $u$ to vertex $v$ if there is an edge $u \to v$ in the graph. This action takes $1$ second.  Graph transposition. To transpose all the edges in the graph: replace each edge $u \to v$ by an edge $v \to u$. This action takes increasingly more time: $k$-th transposition takes $2^{k-1}$ seconds, i.e. the first transposition takes $1$ second, the second one takes $2$ seconds, the third one takes $4$ seconds, and so on. 

The goal is to move the token from vertex $1$ to vertex $n$ in the shortest possible time. Print this time modulo $998\,244\,353$.


-----Input-----

The first line of input contains two integers $n, m$ ($1 \le n, m \le 200\,000$).

The next $m$ lines contain two integers each: $u, v$ ($1 \le u, v \le n; u \ne v$), which represent the edges of the graph. It is guaranteed that all ordered pairs $(u, v)$ are distinct.

It is guaranteed that it is possible to move the token from vertex $1$ to vertex $n$ using the actions above.


-----Output-----

Print one integer: the minimum required time modulo $998\,244\,353$.


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

Output
2

Input
4 3
2 1
2 3
4 3

Output
10



-----Note-----

The first example can be solved by transposing the graph and moving the token to vertex $4$, taking $2$ seconds.

The best way to solve the second example is the following: transpose the graph, move the token to vertex $2$, transpose the graph again, move the token to vertex $3$, transpose the graph once more and move the token to vertex $4$.
user: Please notice the unusual memory limit of this problem.

Orac likes games. Recently he came up with the new game, "Game of Life".

You should play this game on a black and white grid with $n$ rows and $m$ columns. Each cell is either black or white.

For each iteration of the game (the initial iteration is $0$), the color of each cell will change under the following rules: If there are no adjacent cells with the same color as this cell on the current iteration, the color of it on the next iteration will be the same. Otherwise, the color of the cell on the next iteration will be different.

Two cells are adjacent if they have a mutual edge.

Now Orac has set an initial situation, and he wants to know for the cell $(i,j)$ (in $i$-th row and $j$-th column), what will be its color at the iteration $p$. He may ask you these questions several times. 


-----Input-----

The first line contains three integers $n,m,t\ (1\le n,m\le 1000, 1\le t\le 100\,000)$, representing the number of rows, columns, and the number of Orac queries.

Each of the following $n$ lines contains a binary string of length $m$, the $j$-th character in $i$-th line represents the initial color of cell $(i,j)$. '0' stands for white, '1' stands for black.

Each of the following $t$ lines contains three integers $i,j,p\ (1\le i\le n, 1\le j\le m, 1\le p\le 10^{18})$, representing a query from Orac.


-----Output-----

Print $t$ lines, in $i$-th line you should print the answer to the $i$-th query by Orac. If the color of this cell is black, you should print '1'; otherwise, you should write '0'.


-----Examples-----
Input
3 3 3
000
111
000
1 1 1
2 2 2
3 3 3

Output
1
1
1

Input
5 2 2
01
10
01
10
01
1 1 4
5 1 4

Output
0
0

Input
5 5 3
01011
10110
01101
11010
10101
1 1 4
1 2 3
5 5 3

Output
1
0
1

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

Output
0
0
0



-----Note----- [Image] 

For the first example, the picture above shows the initial situation and the color of cells at the iteration $1$, $2$, and $3$. We can see that the color of $(1,1)$ at the iteration $1$ is black, the color of $(2,2)$ at the iteration $2$ is black, and the color of $(3,3)$ at the iteration $3$ is also black.

For the second example, you can prove that the cells will never change their colors.
user: Recently, Dima met with Sasha in a philatelic store, and since then they are collecting coins together. Their favorite occupation is to sort collections of coins. Sasha likes having things in order, that is why he wants his coins to be arranged in a row in such a way that firstly come coins out of circulation, and then come coins still in circulation. 

For arranging coins Dima uses the following algorithm. One step of his algorithm looks like the following:

  He looks through all the coins from left to right;  If he sees that the i-th coin is still in circulation, and (i + 1)-th coin is already out of circulation, he exchanges these two coins and continues watching coins from (i + 1)-th.  

Dima repeats the procedure above until it happens that no two coins were exchanged during this procedure. Dima calls hardness of ordering the number of steps required for him according to the algorithm above to sort the sequence, e.g. the number of times he looks through the coins from the very beginning. For example, for the ordered sequence hardness of ordering equals one.

Today Sasha invited Dima and proposed him a game. First he puts n coins in a row, all of them are out of circulation. Then Sasha chooses one of the coins out of circulation and replaces it with a coin in circulation for n times. During this process Sasha constantly asks Dima what is the hardness of ordering of the sequence. 

The task is more complicated because Dima should not touch the coins and he should determine hardness of ordering in his mind. Help Dima with this task. 


-----Input-----

The first line contains single integer n (1 ≤ n ≤ 300 000) — number of coins that Sasha puts behind Dima.

Second line contains n distinct integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) — positions that Sasha puts coins in circulation to. At first Sasha replaces coin located at position p_1, then coin located at position p_2 and so on. Coins are numbered from left to right.


-----Output-----

Print n + 1 numbers a_0, a_1, ..., a_{n}, where a_0 is a hardness of ordering at the beginning, a_1 is a hardness of ordering after the first replacement and so on. 


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

Output
1 2 3 2 1

Input
8
6 8 3 4 7 2 1 5

Output
1 2 2 3 4 3 4 5 1



-----Note-----

Let's denote as O coin out of circulation, and as X — coin is circulation.

At the first sample, initially in row there are coins that are not in circulation, so Dima will look through them from left to right and won't make any exchanges.

After replacement of the first coin with a coin in circulation, Dima will exchange this coin with next three times and after that he will finally look through the coins and finish the process.

XOOO  →  OOOX

After replacement of the third coin, Dima's actions look this way:

XOXO  →  OXOX  →  OOXX

After replacement of the fourth coin, Dima's actions look this way:

XOXX  →  OXXX

Finally, after replacement of the second coin, row becomes consisting of coins that are in circulation and Dima will look through coins from left to right without any exchanges.
user: Polycarpus is a system administrator. There are two servers under his strict guidance — a and b. To stay informed about the servers' performance, Polycarpus executes commands "ping a" and "ping b". Each ping command sends exactly ten packets to the server specified in the argument of the command. Executing a program results in two integers x and y (x + y = 10; x, y ≥ 0). These numbers mean that x packets successfully reached the corresponding server through the network and y packets were lost.

Today Polycarpus has performed overall n ping commands during his workday. Now for each server Polycarpus wants to know whether the server is "alive" or not. Polycarpus thinks that the server is "alive", if at least half of the packets that we send to this server reached it successfully along the network.

Help Polycarpus, determine for each server, whether it is "alive" or not by the given commands and their results.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of commands Polycarpus has fulfilled. Each of the following n lines contains three integers — the description of the commands. The i-th of these lines contains three space-separated integers t_{i}, x_{i}, y_{i} (1 ≤ t_{i} ≤ 2; x_{i}, y_{i} ≥ 0; x_{i} + y_{i} = 10). If t_{i} = 1, then the i-th command is "ping a", otherwise the i-th command is "ping b". Numbers x_{i}, y_{i} represent the result of executing this command, that is, x_{i} packets reached the corresponding server successfully and y_{i} packets were lost.

It is guaranteed that the input has at least one "ping a" command and at least one "ping b" command.


-----Output-----

In the first line print string "LIVE" (without the quotes) if server a is "alive", otherwise print "DEAD" (without the quotes).

In the second line print the state of server b in the similar format.


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

Output
LIVE
LIVE

Input
3
1 0 10
2 0 10
1 10 0

Output
LIVE
DEAD



-----Note-----

Consider the first test case. There 10 packets were sent to server a, 5 of them reached it. Therefore, at least half of all packets sent to this server successfully reached it through the network. Overall there were 10 packets sent to server b, 6 of them reached it. Therefore, at least half of all packets sent to this server successfully reached it through the network.

Consider the second test case. There were overall 20 packages sent to server a, 10 of them reached it. Therefore, at least half of all packets sent to this server successfully reached it through the network. Overall 10 packets were sent to server b, 0 of them reached it. Therefore, less than half of all packets sent to this server successfully reached it through the network.
user: The legendary Farmer John is throwing a huge party, and animals from all over the world are hanging out at his house. His guests are hungry, so he instructs his cow Bessie to bring out the snacks! Moo!

There are $n$ snacks flavors, numbered with integers $1, 2, \ldots, n$. Bessie has $n$ snacks, one snack of each flavor. Every guest has exactly two favorite flavors. The procedure for eating snacks will go as follows:  First, Bessie will line up the guests in some way.  Then in this order, guests will approach the snacks one by one.  Each guest in their turn will eat all remaining snacks of their favorite flavor. In case no favorite flavors are present when a guest goes up, they become very sad.  

Help Bessie to minimize the number of sad guests by lining the guests in an optimal way.


-----Input-----

The first line contains integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le 10^5$), the number of snacks and the number of guests. 

The $i$-th of the following $k$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$, $x_i \ne y_i$), favorite snack flavors of the $i$-th guest.


-----Output-----

Output one integer, the smallest possible number of sad guests.


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

Output
1

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

Output
0



-----Note-----

In the first example, Bessie can order the guests like this: $3, 1, 2, 4$. Guest $3$ goes first and eats snacks $1$ and $4$. Then the guest $1$ goes and eats the snack $2$ only, because the snack $1$ has already been eaten. Similarly, the guest $2$ goes up and eats the snack $3$ only. All the snacks are gone, so the guest $4$ will be sad. 

In the second example, one optimal ordering is $2, 1, 3, 5, 4$. All the guests will be satisfied.
user: You have unweighted tree of $n$ vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  For every two different leaves $v_{1}$ and $v_{2}$ of this tree, bitwise XOR of weights of all edges on the simple path between $v_{1}$ and $v_{2}$ has to be equal to $0$. 

Note that you can put very large positive integers (like $10^{(10^{10})}$).

It's guaranteed that such assignment always exists under given constraints. Now let's define $f$ as the number of distinct weights in assignment.

 [Image] In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is $0$. $f$ value is $2$ here, because there are $2$ distinct edge weights($4$ and $5$).

[Image] In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex $1$ and vertex $6$ ($3, 4, 5, 4$) is not $0$. 

What are the minimum and the maximum possible values of $f$ for the given tree? Find and print both.


-----Input-----

The first line contains integer $n$ ($3 \le n \le 10^{5}$) — the number of vertices in given tree.

The $i$-th of the next $n-1$ lines contains two integers $a_{i}$ and $b_{i}$ ($1 \le a_{i} \lt b_{i} \le n$) — it means there is an edge between $a_{i}$ and $b_{i}$. It is guaranteed that given graph forms tree of $n$ vertices.


-----Output-----

Print two integers — the minimum and maximum possible value of $f$ can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.


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

Output
1 4

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

Output
3 3

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

Output
1 6



-----Note-----

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.  [Image] 

In the second example, possible assignments for each minimum and maximum are described in picture below. The $f$ value of valid assignment of this tree is always $3$.  [Image] 

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.  [Image]
user: You are given a sequence a = \{a_1, ..., a_N\} with all zeros, and a sequence b = \{b_1, ..., b_N\} consisting of 0 and 1. The length of both is N.
You can perform Q kinds of operations. The i-th operation is as follows:
 - Replace each of a_{l_i}, a_{l_i + 1}, ..., a_{r_i} with 1.
Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.

-----Constraints-----
 - 1 \leq N \leq 200,000
 - b consists of 0 and 1.
 - 1 \leq Q \leq 200,000
 - 1 \leq l_i \leq r_i \leq N
 - If i \neq j, either l_i \neq l_j or r_i \neq r_j.

-----Input-----
Input is given from Standard Input in the following format:
N
b_1 b_2 ... b_N
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

-----Output-----
Print the minimum possible hamming distance.

-----Sample Input-----
3
1 0 1
1
1 3

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

If you choose to perform the operation, a will become \{1, 1, 1\}, for a hamming distance of 1.
user: Bessie has way too many friends because she is everyone's favorite cow! Her new friend Rabbit is trying to hop over so they can play! 

More specifically, he wants to get from $(0,0)$ to $(x,0)$ by making multiple hops. He is only willing to hop from one point to another point on the 2D plane if the Euclidean distance between the endpoints of a hop is one of its $n$ favorite numbers: $a_1, a_2, \ldots, a_n$. What is the minimum number of hops Rabbit needs to get from $(0,0)$ to $(x,0)$? Rabbit may land on points with non-integer coordinates. It can be proved that Rabbit can always reach his destination.

Recall that the Euclidean distance between points $(x_i, y_i)$ and $(x_j, y_j)$ is $\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}$.

For example, if Rabbit has favorite numbers $1$ and $3$ he could hop from $(0,0)$ to $(4,0)$ in two hops as shown below. Note that there also exists other valid ways to hop to $(4,0)$ in $2$ hops (e.g. $(0,0)$ $\rightarrow$ $(2,-\sqrt{5})$ $\rightarrow$ $(4,0)$).

 $1$ Here is a graphic for the first example. Both hops have distance $3$, one of Rabbit's favorite numbers. 

In other words, each time Rabbit chooses some number $a_i$ and hops with distance equal to $a_i$ in any direction he wants. The same number can be used multiple times.


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$)  — the number of test cases. Next $2t$ lines contain test cases — two lines per test case.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 10^5$, $1 \le x \le 10^9$)  — the number of favorite numbers and the distance Rabbit wants to travel, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$)  — Rabbit's favorite numbers. It is guaranteed that the favorite numbers are distinct.

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


-----Output-----

For each test case, print a single integer — the minimum number of hops needed.


-----Example-----
Input
4
2 4
1 3
3 12
3 4 5
1 5
5
2 10
15 4

Output
2
3
1
2



-----Note-----

The first test case of the sample is shown in the picture above. Rabbit can hop to $(2,\sqrt{5})$, then to $(4,0)$ for a total of two hops. Each hop has a distance of $3$, which is one of his favorite numbers.

In the second test case of the sample, one way for Rabbit to hop $3$ times is: $(0,0)$ $\rightarrow$ $(4,0)$ $\rightarrow$ $(8,0)$ $\rightarrow$ $(12,0)$.

In the third test case of the sample, Rabbit can hop from $(0,0)$ to $(5,0)$.

In the fourth test case of the sample, Rabbit can hop: $(0,0)$ $\rightarrow$ $(5,10\sqrt{2})$ $\rightarrow$ $(10,0)$.
user: Dima is a beginner programmer. During his working process, he regularly has to repeat the following operation again and again: to remove every second element from the array. One day he has been bored with easy solutions of this problem, and he has come up with the following extravagant algorithm.

Let's consider that initially array contains n numbers from 1 to n and the number i is located in the cell with the index 2i - 1 (Indices are numbered starting from one) and other cells of the array are empty. Each step Dima selects a non-empty array cell with the maximum index and moves the number written in it to the nearest empty cell to the left of the selected one. The process continues until all n numbers will appear in the first n cells of the array. For example if n = 4, the array is changing as follows: [Image] 

You have to write a program that allows you to determine what number will be in the cell with index x (1 ≤ x ≤ n) after Dima's algorithm finishes.


-----Input-----

The first line contains two integers n and q (1 ≤ n ≤ 10^18, 1 ≤ q ≤ 200 000), the number of elements in the array and the number of queries for which it is needed to find the answer.

Next q lines contain integers x_{i} (1 ≤ x_{i} ≤ n), the indices of cells for which it is necessary to output their content after Dima's algorithm finishes.


-----Output-----

For each of q queries output one integer number, the value that will appear in the corresponding array cell after Dima's algorithm finishes.


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

Output
3
2
4

Input
13 4
10
5
4
8

Output
13
3
8
9



-----Note-----

The first example is shown in the picture.

In the second example the final array is [1, 12, 2, 8, 3, 11, 4, 9, 5, 13, 6, 10, 7].