meetforever/GRPO_CL huggingface dataset:
user: There is an infinite sequence consisting of all positive integers in the increasing order: p = {1, 2, 3, ...}. We performed n swap operations with this sequence. A swap(a, b) is an operation of swapping the elements of the sequence on positions a and b. Your task is to find the number of inversions in the resulting sequence, i.e. the number of such index pairs (i, j), that i < j and p_{i} > p_{j}.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of swap operations applied to the sequence.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 10^9, a_{i} ≠ b_{i}) — the arguments of the swap operation.


-----Output-----

Print a single integer — the number of inversions in the resulting sequence.


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

Output
4

Input
3
1 6
3 4
2 5

Output
15



-----Note-----

In the first sample the sequence is being modified as follows: $\{1,2,3,4,5, \ldots \} \rightarrow \{1,4,3,2,5, \ldots \} \rightarrow \{2,4,3,1,5 \ldots \}$. It has 4 inversions formed by index pairs (1, 4), (2, 3), (2, 4) and (3, 4).
user: Amugae is in a very large round corridor. The corridor consists of two areas. The inner area is equally divided by $n$ sectors, and the outer area is equally divided by $m$ sectors. A wall exists between each pair of sectors of same area (inner or outer), but there is no wall between the inner area and the outer area. A wall always exists at the 12 o'clock position.

 $0$ 

The inner area's sectors are denoted as $(1,1), (1,2), \dots, (1,n)$ in clockwise direction. The outer area's sectors are denoted as $(2,1), (2,2), \dots, (2,m)$ in the same manner. For a clear understanding, see the example image above.

Amugae wants to know if he can move from one sector to another sector. He has $q$ questions.

For each question, check if he can move between two given sectors.


-----Input-----

The first line contains three integers $n$, $m$ and $q$ ($1 \le n, m \le 10^{18}$, $1 \le q \le 10^4$) — the number of sectors in the inner area, the number of sectors in the outer area and the number of questions.

Each of the next $q$ lines contains four integers $s_x$, $s_y$, $e_x$, $e_y$ ($1 \le s_x, e_x \le 2$; if $s_x = 1$, then $1 \le s_y \le n$, otherwise $1 \le s_y \le m$; constraints on $e_y$ are similar). Amague wants to know if it is possible to move from sector $(s_x, s_y)$ to sector $(e_x, e_y)$.


-----Output-----

For each question, print "YES" if Amugae can move from $(s_x, s_y)$ to $(e_x, e_y)$, and "NO" otherwise.

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


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

Output
YES
NO
YES



-----Note-----

Example is shown on the picture in the statement.
user: Alica and Bob are playing a game.

Initially they have a binary string $s$ consisting of only characters 0 and 1.

Alice and Bob make alternating moves: Alice makes the first move, Bob makes the second move, Alice makes the third one, and so on. During each move, the current player must choose two different adjacent characters of string $s$ and delete them. For example, if $s = 1011001$ then the following moves are possible:   delete $s_1$ and $s_2$: $\textbf{10}11001 \rightarrow 11001$;  delete $s_2$ and $s_3$: $1\textbf{01}1001 \rightarrow 11001$;  delete $s_4$ and $s_5$: $101\textbf{10}01 \rightarrow 10101$;  delete $s_6$ and $s_7$: $10110\textbf{01} \rightarrow 10110$. 

If a player can't make any move, they lose. Both players play optimally. You have to determine if Alice can win.


-----Input-----

First line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Only line of each test case contains one string $s$ ($1 \le |s| \le 100$), consisting of only characters 0 and 1.


-----Output-----

For each test case print answer in the single line.

If Alice can win print DA (YES in Russian) in any register. Otherwise print NET (NO in Russian) in any register.


-----Example-----
Input
3
01
1111
0011

Output
DA
NET
NET



-----Note-----

In the first test case after Alice's move string $s$ become empty and Bob can not make any move.

In the second test case Alice can not make any move initially.

In the third test case after Alice's move string $s$ turn into $01$. Then, after Bob's move string $s$ become empty and Alice can not make any move.
user: Inna loves sleeping very much, so she needs n alarm clocks in total to wake up. Let's suppose that Inna's room is a 100 × 100 square with the lower left corner at point (0, 0) and with the upper right corner at point (100, 100). Then the alarm clocks are points with integer coordinates in this square.

The morning has come. All n alarm clocks in Inna's room are ringing, so Inna wants to turn them off. For that Inna has come up with an amusing game:  First Inna chooses a type of segments that she will use throughout the game. The segments can be either vertical or horizontal.  Then Inna makes multiple moves. In a single move, Inna can paint a segment of any length on the plane, she chooses its type at the beginning of the game (either vertical or horizontal), then all alarm clocks that are on this segment switch off. The game ends when all the alarm clocks are switched off. 

Inna is very sleepy, so she wants to get through the alarm clocks as soon as possible. Help her, find the minimum number of moves in the game that she needs to turn off all the alarm clocks!


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 10^5) — the number of the alarm clocks. The next n lines describe the clocks: the i-th line contains two integers x_{i}, y_{i} — the coordinates of the i-th alarm clock (0 ≤ x_{i}, y_{i} ≤ 100).

Note that a single point in the room can contain any number of alarm clocks and the alarm clocks can lie on the sides of the square that represents the room.


-----Output-----

In a single line print a single integer — the minimum number of segments Inna will have to draw if she acts optimally.


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

Output
2

Input
4
0 0
0 1
1 0
1 1

Output
2

Input
4
1 1
1 2
2 3
3 3

Output
3



-----Note-----

In the first sample, Inna first chooses type "vertical segments", and then she makes segments with ends at : (0, 0), (0, 2); and, for example, (1, 0), (1, 1). If she paints horizontal segments, she will need at least 3 segments.

In the third sample it is important to note that Inna doesn't have the right to change the type of the segments during the game. That's why she will need 3 horizontal or 3 vertical segments to end the game.
user: You came to a local shop and want to buy some chocolate bars. There are $n$ bars in the shop, $i$-th of them costs $a_i$ coins (and you want to buy all of them).

You have $m$ different coupons that allow you to buy chocolate bars. $i$-th coupon allows you to buy $q_i$ chocolate bars while you have to pay only for the $q_i - 1$ most expensive ones (so, the cheapest bar of those $q_i$ bars is for free).

You can use only one coupon; if you use coupon $i$, you have to choose $q_i$ bars and buy them using the coupon, and buy all the remaining $n - q_i$ bars without any discounts.

To decide which coupon to choose, you want to know what will be the minimum total amount of money you have to pay if you use one of the coupons optimally.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 3 \cdot 10^5$) — the number of chocolate bars in the shop.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the cost of $i$-th chocolate bar.

The third line contains one integer $m$ ($1 \le m \le n - 1$) — the number of coupons you have.

The fourth line contains $m$ integers $q_1$, $q_2$, ..., $q_m$ ($2 \le q_i \le n$), where $q_i$ is the number of chocolate bars you have to buy using $i$-th coupon so that the least expensive of them will be for free. All values of $q_i$ are pairwise distinct.


-----Output-----

Print $m$ integers, $i$-th of them should be the minimum amount of money you have to pay if you buy $q_i$ bars with $i$-th coupon, and all the remaining bars one by one for their full price.


-----Example-----
Input
7
7 1 3 1 4 10 8
2
3 4

Output
27
30



-----Note-----

Consider the first example.

If we use the first coupon, we may choose chocolate bars having indices $1$, $6$ and $7$, and we pay $18$ coins for them and $9$ coins for all other bars.

If we use the second coupon, we may choose chocolate bars having indices $1$, $5$, $6$ and $7$, and we pay $25$ coins for them and $5$ coins for all other bars.
user: Given a connected undirected graph with $n$ vertices and an integer $k$, you have to either:  either find an independent set that has exactly $\lceil\frac{k}{2}\rceil$ vertices. or find a simple cycle of length at most $k$. 

An independent set is a set of vertices such that no two of them are connected by an edge. A simple cycle is a cycle that doesn't contain any vertex twice. 

I have a proof that for any input you can always solve at least one of these problems, but it's left as an exercise for the reader.


-----Input-----

The first line contains three integers $n$, $m$, and $k$ ($3 \le k \le n \le 10^5$, $n-1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges in the graph, and the parameter $k$ from the statement.

Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \le u,v \le n$) that mean there's an edge between vertices $u$ and $v$. It's guaranteed that the graph is connected and doesn't contain any self-loops or multiple edges.


-----Output-----

If you choose to solve the first problem, then on the first line print $1$, followed by a line containing $\lceil\frac{k}{2}\rceil$ distinct integers not exceeding $n$, the vertices in the desired independent set.

If you, however, choose to solve the second problem, then on the first line print $2$, followed by a line containing one integer, $c$, representing the length of the found cycle, followed by a line containing $c$ distinct integers not exceeding $n$, the vertices in the desired cycle, in the order they appear in the cycle.


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

Output
1
1 3 
Input
4 5 3
1 2
2 3
3 4
4 1
2 4

Output
2
3
2 3 4 
Input
4 6 3
1 2
2 3
3 4
4 1
1 3
2 4

Output
2
3
1 2 3 
Input
5 4 5
1 2
1 3
2 4
2 5

Output
1
1 4 5 


-----Note-----

In the first sample:

[Image]

Notice that printing the independent set $\{2,4\}$ is also OK, but printing the cycle $1-2-3-4$ isn't, because its length must be at most $3$.

In the second sample:

$N$

Notice that printing the independent set $\{1,3\}$ or printing the cycle $2-1-4$ is also OK.

In the third sample:

[Image]

In the fourth sample:

$A$
user: We often have to copy large volumes of information. Such operation can take up many computer resources. Therefore, in this problem you are advised to come up with a way to copy some part of a number array into another one, quickly.

More formally, you've got two arrays of integers a_1, a_2, ..., a_{n} and b_1, b_2, ..., b_{n} of length n. Also, you've got m queries of two types:  Copy the subsegment of array a of length k, starting from position x, into array b, starting from position y, that is, execute b_{y} + q = a_{x} + q for all integer q (0 ≤ q < k). The given operation is correct — both subsegments do not touch unexistent elements.  Determine the value in position x of array b, that is, find value b_{x}. 

For each query of the second type print the result — the value of the corresponding element of array b.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 10^5) — the number of elements in the arrays and the number of queries, correspondingly. The second line contains an array of integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 10^9). The third line contains an array of integers b_1, b_2, ..., b_{n} (|b_{i}| ≤ 10^9).

Next m lines contain the descriptions of the queries. The i-th line first contains integer t_{i} — the type of the i-th query (1 ≤ t_{i} ≤ 2). If t_{i} = 1, then the i-th query means the copying operation. If t_{i} = 2, then the i-th query means taking the value in array b. If t_{i} = 1, then the query type is followed by three integers x_{i}, y_{i}, k_{i} (1 ≤ x_{i}, y_{i}, k_{i} ≤ n) — the parameters of the copying query. If t_{i} = 2, then the query type is followed by integer x_{i} (1 ≤ x_{i} ≤ n) — the position in array b.

All numbers in the lines are separated with single spaces. It is guaranteed that all the queries are correct, that is, the copying borders fit into the borders of arrays a and b.


-----Output-----

For each second type query print the result on a single line.


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

Output
0
3
-1
3
2
3
-1
user: $n$ fishermen have just returned from a fishing vacation. The $i$-th fisherman has caught a fish of weight $a_i$.

Fishermen are going to show off the fish they caught to each other. To do so, they firstly choose an order in which they show their fish (each fisherman shows his fish exactly once, so, formally, the order of showing fish is a permutation of integers from $1$ to $n$). Then they show the fish they caught according to the chosen order. When a fisherman shows his fish, he might either become happy, become sad, or stay content.

Suppose a fisherman shows a fish of weight $x$, and the maximum weight of a previously shown fish is $y$ ($y = 0$ if that fisherman is the first to show his fish). Then:

  if $x \ge 2y$, the fisherman becomes happy;  if $2x \le y$, the fisherman becomes sad;  if none of these two conditions is met, the fisherman stays content. 

Let's call an order in which the fishermen show their fish emotional if, after all fishermen show their fish according to this order, each fisherman becomes either happy or sad. Calculate the number of emotional orders modulo $998244353$.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 5000$).

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$).


-----Output-----

Print one integer — the number of emotional orders, taken modulo $998244353$.


-----Examples-----
Input
4
1 1 4 9

Output
20

Input
4
4 3 2 1

Output
0

Input
3
4 2 1

Output
6

Input
8
42 1337 13 37 420 666 616 97

Output
19200
user: You are given several queries. In the i-th query you are given a single positive integer n_{i}. You are to represent n_{i} as a sum of maximum possible number of composite summands and print this maximum number, or print -1, if there are no such splittings.

An integer greater than 1 is composite, if it is not prime, i.e. if it has positive divisors not equal to 1 and the integer itself.


-----Input-----

The first line contains single integer q (1 ≤ q ≤ 10^5) — the number of queries.

q lines follow. The (i + 1)-th line contains single integer n_{i} (1 ≤ n_{i} ≤ 10^9) — the i-th query.


-----Output-----

For each query print the maximum possible number of summands in a valid splitting to composite summands, or -1, if there are no such splittings.


-----Examples-----
Input
1
12

Output
3

Input
2
6
8

Output
1
2

Input
3
1
2
3

Output
-1
-1
-1



-----Note-----

12 = 4 + 4 + 4 = 4 + 8 = 6 + 6 = 12, but the first splitting has the maximum possible number of summands.

8 = 4 + 4, 6 can't be split into several composite summands.

1, 2, 3 are less than any composite number, so they do not have valid splittings.
user: Santa Claus has Robot which lives on the infinite grid and can move along its lines. He can also, having a sequence of m points p_1, p_2, ..., p_{m} with integer coordinates, do the following: denote its initial location by p_0. First, the robot will move from p_0 to p_1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches p_1, it'll move to p_2, again, choosing one of the shortest ways, then to p_3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order.

While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence.


-----Input-----

The first line of input contains the only positive integer n (1 ≤ n ≤ 2·10^5) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of n letters, each being equal either L, or R, or U, or D. k-th letter stands for the direction which Robot traveled the k-th unit segment in: L means that it moved to the left, R — to the right, U — to the top and D — to the bottom. Have a look at the illustrations for better explanation.


-----Output-----

The only line of input should contain the minimum possible length of the sequence.


-----Examples-----
Input
4
RURD

Output
2

Input
6
RRULDD

Output
2

Input
26
RRRULURURUULULLLDLDDRDRDLD

Output
7

Input
3
RLL

Output
2

Input
4
LRLR

Output
4



-----Note-----

The illustrations to the first three tests are given below.

[Image] [Image] [Image]

The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.
user: There are n integers b_1, b_2, ..., b_{n} written in a row. For all i from 1 to n, values a_{i} are defined by the crows performing the following procedure:

  The crow sets a_{i} initially 0.  The crow then adds b_{i} to a_{i}, subtracts b_{i} + 1, adds the b_{i} + 2 number, and so on until the n'th number. Thus, a_{i} = b_{i} - b_{i} + 1 + b_{i} + 2 - b_{i} + 3.... 

Memory gives you the values a_1, a_2, ..., a_{n}, and he now wants you to find the initial numbers b_1, b_2, ..., b_{n} written in the row? Can you do it?


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of integers written in the row.

The next line contains n, the i'th of which is a_{i} ( - 10^9 ≤ a_{i} ≤ 10^9) — the value of the i'th number.


-----Output-----

Print n integers corresponding to the sequence b_1, b_2, ..., b_{n}. It's guaranteed that the answer is unique and fits in 32-bit integer type.


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

Output
2 4 6 1 3 

Input
5
3 -2 -1 5 6

Output
1 -3 4 11 6 



-----Note-----

In the first sample test, the crows report the numbers 6, - 4, 8, - 2, and 3 when he starts at indices 1, 2, 3, 4 and 5 respectively. It is easy to check that the sequence 2 4 6 1 3 satisfies the reports. For example, 6 = 2 - 4 + 6 - 1 + 3, and  - 4 = 4 - 6 + 1 - 3.

In the second sample test, the sequence 1,  - 3, 4, 11, 6 satisfies the reports. For example, 5 = 11 - 6 and 6 = 6.
user: A new set of desks just arrived, and it's about time! Things were getting quite cramped in the office. You've been put in charge of creating a new seating chart for the engineers. The desks are numbered, and you sent out a survey to the engineering team asking each engineer the number of the desk they currently sit at, and the number of the desk they would like to sit at (which may be the same as their current desk). Each engineer must either remain where they sit, or move to the desired seat they indicated in the survey. No two engineers currently sit at the same desk, nor may any two engineers sit at the same desk in the new seating arrangement.

How many seating arrangements can you create that meet the specified requirements? The answer may be very large, so compute it modulo 1000000007 = 10^9 + 7.


-----Input-----

Input will begin with a line containing N (1 ≤ N ≤ 100000), the number of engineers. 

N lines follow, each containing exactly two integers. The i-th line contains the number of the current desk of the i-th engineer and the number of the desk the i-th engineer wants to move to. Desks are numbered from 1 to 2·N. It is guaranteed that no two engineers sit at the same desk.


-----Output-----

Print the number of possible assignments, modulo 1000000007 = 10^9 + 7.


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

Output
6

Input
5
1 10
2 10
3 10
4 10
5 5

Output
5



-----Note-----

These are the possible assignments for the first example:   1 5 3 7  1 2 3 7  5 2 3 7  1 5 7 3  1 2 7 3  5 2 7 3
user: You are given a tree (an undirected connected graph without cycles) and an integer $s$.

Vanya wants to put weights on all edges of the tree so that all weights are non-negative real numbers and their sum is $s$. At the same time, he wants to make the diameter of the tree as small as possible.

Let's define the diameter of a weighed tree as the maximum sum of the weights of the edges lying on the path between two some vertices of the tree. In other words, the diameter of a weighed tree is the length of the longest simple path in the tree, where length of a path is equal to the sum of weights over all edges in the path.

Find the minimum possible diameter that Vanya can get.


-----Input-----

The first line contains two integer numbers $n$ and $s$ ($2 \leq n \leq 10^5$, $1 \leq s \leq 10^9$) — the number of vertices in the tree and the sum of edge weights.

Each of the following $n−1$ lines contains two space-separated integer numbers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$, $a_i \neq b_i$) — the indexes of vertices connected by an edge. The edges are undirected.

It is guaranteed that the given edges form a tree.


-----Output-----

Print the minimum diameter of the tree that Vanya can get by placing some non-negative real weights on its edges with the sum equal to $s$.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac {|a-b|} {max(1, b)} \leq 10^{-6}$.


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

Output
2.000000000000000000
Input
6 1
2 1
2 3
2 5
5 4
5 6

Output
0.500000000000000000
Input
5 5
1 2
2 3
3 4
3 5

Output
3.333333333333333333


-----Note-----

In the first example it is necessary to put weights like this: [Image] 

It is easy to see that the diameter of this tree is $2$. It can be proved that it is the minimum possible diameter.

In the second example it is necessary to put weights like this: [Image]