meetforever/GRPO_CL huggingface dataset:
user: You are given sequence a_1, a_2, ..., a_{n} and m queries l_{j}, r_{j} (1 ≤ l_{j} ≤ r_{j} ≤ n). For each query you need to print the minimum distance between such pair of elements a_{x} and a_{y} (x ≠ y), that:  both indexes of the elements lie within range [l_{j}, r_{j}], that is, l_{j} ≤ x, y ≤ r_{j};  the values of the elements are equal, that is a_{x} = a_{y}. 

The text above understands distance as |x - y|.


-----Input-----

The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·10^5) — the length of the sequence and the number of queries, correspondingly. 

The second line contains the sequence of integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9). 

Next m lines contain the queries, one per line. Each query is given by a pair of numbers l_{j}, r_{j} (1 ≤ l_{j} ≤ r_{j} ≤ n) — the indexes of the query range limits.


-----Output-----

Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.


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

Output
1
-1
2

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

Output
2
2
3
-1
2
user: Let $LCM(x, y)$ be the minimum positive integer that is divisible by both $x$ and $y$. For example, $LCM(13, 37) = 481$, $LCM(9, 6) = 18$.

You are given two integers $l$ and $r$. Find two integers $x$ and $y$ such that $l \le x < y \le r$ and $l \le LCM(x, y) \le r$.


-----Input-----

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

Each test case is represented by one line containing two integers $l$ and $r$ ($1 \le l < r \le 10^9$).


-----Output-----

For each test case, print two integers:

  if it is impossible to find integers $x$ and $y$ meeting the constraints in the statement, print two integers equal to $-1$;  otherwise, print the values of $x$ and $y$ (if there are multiple valid answers, you may print any of them). 


-----Example-----
Input
4
1 1337
13 69
2 4
88 89

Output
6 7
14 21
2 4
-1 -1
user: Mishka is trying really hard to avoid being kicked out of the university. In particular, he was doing absolutely nothing for the whole semester, miraculously passed some exams so that just one is left.

There were $n$ classes of that subject during the semester and on $i$-th class professor mentioned some non-negative integer $a_i$ to the students. It turned out, the exam was to tell the whole sequence back to the professor. 

Sounds easy enough for those who attended every class, doesn't it?

Obviously Mishka didn't attend any classes. However, professor left some clues on the values of $a$ to help out students like Mishka:   $a$ was sorted in non-decreasing order ($a_1 \le a_2 \le \dots \le a_n$);  $n$ was even;  the following sequence $b$, consisting of $\frac n 2$ elements, was formed and given out to students: $b_i = a_i + a_{n - i + 1}$. 

Professor also mentioned that any sequence $a$, which produces sequence $b$ with the presented technique, will be acceptable.

Help Mishka to pass that last exam. Restore any sorted sequence $a$ of non-negative integers, which produces sequence $b$ with the presented technique. It is guaranteed that there exists at least one correct sequence $a$, which produces the given sequence $b$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of sequence $a$. $n$ is always even.

The second line contains $\frac n 2$ integers $b_1, b_2, \dots, b_{\frac n 2}$ ($0 \le b_i \le 10^{18}$) — sequence $b$, where $b_i = a_i + a_{n - i + 1}$.

It is guaranteed that there exists at least one correct sequence $a$, which produces the given sequence $b$.


-----Output-----

Print $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$) in a single line.

$a_1 \le a_2 \le \dots \le a_n$ should be satisfied.

$b_i = a_i + a_{n - i + 1}$ should be satisfied for all valid $i$.


-----Examples-----
Input
4
5 6

Output
2 3 3 3

Input
6
2 1 2

Output
0 0 1 1 1 2
user: Mike wants to prepare for IMO but he doesn't know geometry, so his teacher gave him an interesting geometry problem. Let's define f([l, r]) = r - l + 1 to be the number of integer points in the segment [l, r] with l ≤ r (say that $f(\varnothing) = 0$). You are given two integers n and k and n closed intervals [l_{i}, r_{i}] on OX axis and you have to find: $\sum_{1 \leq i_{1} < i_{2} < \ldots < i_{k} \leq n} f([ l_{i_{1}}, r_{i_{1}} ] \cap [ l_{i_{2}}, r_{i_{2}} ] \cap \ldots \cap [ l_{i_{k}}, r_{i_{k}} ])$ 

In other words, you should find the sum of the number of integer points in the intersection of any k of the segments. 

As the answer may be very large, output it modulo 1000000007 (10^9 + 7).

Mike can't solve this problem so he needs your help. You will help him, won't you? 


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 200 000) — the number of segments and the number of segments in intersection groups respectively.

Then n lines follow, the i-th line contains two integers l_{i}, r_{i} ( - 10^9 ≤ l_{i} ≤ r_{i} ≤ 10^9), describing i-th segment bounds.


-----Output-----

Print one integer number — the answer to Mike's problem modulo 1000000007 (10^9 + 7) in the only line.


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

Output
5

Input
3 3
1 3
1 3
1 3

Output
3

Input
3 1
1 2
2 3
3 4

Output
6



-----Note-----

In the first example: 

$f([ 1,2 ] \cap [ 1,3 ]) = f([ 1,2 ]) = 2$;

$f([ 1,2 ] \cap [ 2,3 ]) = f([ 2,2 ]) = 1$;

$f([ 1,3 ] \cap [ 2,3 ]) = f([ 2,3 ]) = 2$.

So the answer is 2 + 1 + 2 = 5.
user: Levko loves tables that consist of n rows and n columns very much. He especially loves beautiful tables. A table is beautiful to Levko if the sum of elements in each row and column of the table equals k.

Unfortunately, he doesn't know any such table. Your task is to help him to find at least one of them. 


-----Input-----

The single line contains two integers, n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1000).


-----Output-----

Print any beautiful table. Levko doesn't like too big numbers, so all elements of the table mustn't exceed 1000 in their absolute value.

If there are multiple suitable tables, you are allowed to print any of them.


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

Output
1 3
3 1

Input
4 7

Output
2 1 0 4
4 0 2 1
1 3 3 0
0 3 2 2



-----Note-----

In the first sample the sum in the first row is 1 + 3 = 4, in the second row — 3 + 1 = 4, in the first column — 1 + 3 = 4 and in the second column — 3 + 1 = 4. There are other beautiful tables for this sample.

In the second sample the sum of elements in each row and each column equals 7. Besides, there are other tables that meet the statement requirements.
user: Anastasia loves going for a walk in Central Uzhlyandian Park. But she became uninterested in simple walking, so she began to collect Uzhlyandian pebbles. At first, she decided to collect all the pebbles she could find in the park.

She has only two pockets. She can put at most k pebbles in each pocket at the same time. There are n different pebble types in the park, and there are w_{i} pebbles of the i-th type. Anastasia is very responsible, so she never mixes pebbles of different types in same pocket. However, she can put different kinds of pebbles in different pockets at the same time. Unfortunately, she can't spend all her time collecting pebbles, so she can collect pebbles from the park only once a day.

Help her to find the minimum number of days needed to collect all the pebbles of Uzhlyandian Central Park, taking into consideration that Anastasia can't place pebbles of different types in same pocket.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 10^9) — the number of different pebble types and number of pebbles Anastasia can place in one pocket.

The second line contains n integers w_1, w_2, ..., w_{n} (1 ≤ w_{i} ≤ 10^4) — number of pebbles of each type. 


-----Output-----

The only line of output contains one integer — the minimum number of days Anastasia needs to collect all the pebbles.


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

Output
3

Input
5 4
3 1 8 9 7

Output
5



-----Note-----

In the first sample case, Anastasia can collect all pebbles of the first type on the first day, of second type — on the second day, and of third type — on the third day.

Optimal sequence of actions in the second sample case:   In the first day Anastasia collects 8 pebbles of the third type.  In the second day she collects 8 pebbles of the fourth type.  In the third day she collects 3 pebbles of the first type and 1 pebble of the fourth type.  In the fourth day she collects 7 pebbles of the fifth type.  In the fifth day she collects 1 pebble of the second type.
user: Karafs is some kind of vegetable in shape of an 1 × h rectangle. Tavaspolis people love Karafs and they use Karafs in almost any kind of food. Tavas, himself, is crazy about Karafs. [Image] 

Each Karafs has a positive integer height. Tavas has an infinite 1-based sequence of Karafses. The height of the i-th Karafs is s_{i} = A + (i - 1) × B.

For a given m, let's define an m-bite operation as decreasing the height of at most m distinct not eaten Karafses by 1. Karafs is considered as eaten when its height becomes zero.

Now SaDDas asks you n queries. In each query he gives you numbers l, t and m and you should find the largest number r such that l ≤ r and sequence s_{l}, s_{l} + 1, ..., s_{r} can be eaten by performing m-bite no more than t times or print -1 if there is no such number r.


-----Input-----

The first line of input contains three integers A, B and n (1 ≤ A, B ≤ 10^6, 1 ≤ n ≤ 10^5).

Next n lines contain information about queries. i-th line contains integers l, t, m (1 ≤ l, t, m ≤ 10^6) for i-th query.


-----Output-----

For each query, print its answer in a single line.


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

Output
4
-1
8
-1

Input
1 5 2
1 5 10
2 7 4

Output
1
2
user: You are given a complete directed graph $K_n$ with $n$ vertices: each pair of vertices $u \neq v$ in $K_n$ have both directed edges $(u, v)$ and $(v, u)$; there are no self-loops.

You should find such a cycle in $K_n$ that visits every directed edge exactly once (allowing for revisiting vertices).

We can write such cycle as a list of $n(n - 1) + 1$ vertices $v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1$ — a visiting order, where each $(v_i, v_{i + 1})$ occurs exactly once.

Find the lexicographically smallest such cycle. It's not hard to prove that the cycle always exists.

Since the answer can be too large print its $[l, r]$ segment, in other words, $v_l, v_{l + 1}, \dots, v_r$.


-----Input-----

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $T$ lines contain test cases — one per line. The first and only line of each test case contains three integers $n$, $l$ and $r$ ($2 \le n \le 10^5$, $1 \le l \le r \le n(n - 1) + 1$, $r - l + 1 \le 10^5$) — the number of vertices in $K_n$, and segment of the cycle to print.

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$ and the total sum of $r - l + 1$ doesn't exceed $10^5$.


-----Output-----

For each test case print the segment $v_l, v_{l + 1}, \dots, v_r$ of the lexicographically smallest cycle that visits every edge exactly once.


-----Example-----
Input
3
2 1 3
3 3 6
99995 9998900031 9998900031

Output
1 2 1 
1 3 2 3 
1 



-----Note-----

In the second test case, the lexicographically minimum cycle looks like: $1, 2, 1, 3, 2, 3, 1$.

In the third test case, it's quite obvious that the cycle should start and end in vertex $1$.
user: The annual college sports-ball tournament is approaching, which for trademark reasons we'll refer to as Third Month Insanity. There are a total of 2^{N} teams participating in the tournament, numbered from 1 to 2^{N}. The tournament lasts N rounds, with each round eliminating half the teams. The first round consists of 2^{N} - 1 games, numbered starting from 1. In game i, team 2·i - 1 will play against team 2·i. The loser is eliminated and the winner advances to the next round (there are no ties). Each subsequent round has half as many games as the previous round, and in game i the winner of the previous round's game 2·i - 1 will play against the winner of the previous round's game 2·i.

Every year the office has a pool to see who can create the best bracket. A bracket is a set of winner predictions for every game. For games in the first round you may predict either team to win, but for games in later rounds the winner you predict must also be predicted as a winner in the previous round. Note that the bracket is fully constructed before any games are actually played. Correct predictions in the first round are worth 1 point, and correct predictions in each subsequent round are worth twice as many points as the previous, so correct predictions in the final game are worth 2^{N} - 1 points.

For every pair of teams in the league, you have estimated the probability of each team winning if they play against each other. Now you want to construct a bracket with the maximum possible expected score.


-----Input-----

Input will begin with a line containing N (2 ≤ N ≤ 6).

2^{N} lines follow, each with 2^{N} integers. The j-th column of the i-th row indicates the percentage chance that team i will defeat team j, unless i = j, in which case the value will be 0. It is guaranteed that the i-th column of the j-th row plus the j-th column of the i-th row will add to exactly 100.


-----Output-----

Print the maximum possible expected score over all possible brackets. Your answer must be correct to within an absolute or relative error of 10^{ - 9}.

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


-----Examples-----
Input
2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0

Output
1.75

Input
3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0

Output
12

Input
2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0

Output
3.141592



-----Note-----

In the first example, you should predict teams 1 and 4 to win in round 1, and team 1 to win in round 2. Recall that the winner you predict in round 2 must also be predicted as a winner in round 1.
user: One day Dima and Alex had an argument about the price and quality of laptops. Dima thinks that the more expensive a laptop is, the better it is. Alex disagrees. Alex thinks that there are two laptops, such that the price of the first laptop is less (strictly smaller) than the price of the second laptop but the quality of the first laptop is higher (strictly greater) than the quality of the second laptop.

Please, check the guess of Alex. You are given descriptions of n laptops. Determine whether two described above laptops exist.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of laptops.

Next n lines contain two integers each, a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ n), where a_{i} is the price of the i-th laptop, and b_{i} is the number that represents the quality of the i-th laptop (the larger the number is, the higher is the quality).

All a_{i} are distinct. All b_{i} are distinct. 


-----Output-----

If Alex is correct, print "Happy Alex", otherwise print "Poor Alex" (without the quotes).


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

Output
Happy Alex
user: Misha hacked the Codeforces site. Then he decided to let all the users change their handles. A user can now change his handle any number of times. But each new handle must not be equal to any handle that is already used or that was used at some point.

Misha has a list of handle change requests. After completing the requests he wants to understand the relation between the original and the new handles of the users. Help him to do that.


-----Input-----

The first line contains integer q (1 ≤ q ≤ 1000), the number of handle change requests.

Next q lines contain the descriptions of the requests, one per line.

Each query consists of two non-empty strings old and new, separated by a space. The strings consist of lowercase and uppercase Latin letters and digits. Strings old and new are distinct. The lengths of the strings do not exceed 20.

The requests are given chronologically. In other words, by the moment of a query there is a single person with handle old, and handle new is not used and has not been used by anyone.


-----Output-----

In the first line output the integer n — the number of users that changed their handles at least once.

In the next n lines print the mapping between the old and the new handles of the users. Each of them must contain two strings, old and new, separated by a space, meaning that before the user had handle old, and after all the requests are completed, his handle is new. You may output lines in any order.

Each user who changes the handle must occur exactly once in this description.


-----Examples-----
Input
5
Misha ILoveCodeforces
Vasya Petrov
Petrov VasyaPetrov123
ILoveCodeforces MikeMirzayanov
Petya Ivanov

Output
3
Petya Ivanov
Misha MikeMirzayanov
Vasya VasyaPetrov123
user: Two famous competing companies ChemForces and TopChemist decided to show their sets of recently discovered chemical elements on an exhibition. However they know that no element should be present in the sets of both companies.

In order to avoid this representatives of both companies decided to make an agreement on the sets the companies should present. The sets should be chosen in the way that maximizes the total income of the companies.

All elements are enumerated with integers. The ChemForces company has discovered $n$ distinct chemical elements with indices $a_1, a_2, \ldots, a_n$, and will get an income of $x_i$ Berland rubles if the $i$-th element from this list is in the set of this company.

The TopChemist company discovered $m$ distinct chemical elements with indices $b_1, b_2, \ldots, b_m$, and it will get an income of $y_j$ Berland rubles for including the $j$-th element from this list to its set.

In other words, the first company can present any subset of elements from $\{a_1, a_2, \ldots, a_n\}$ (possibly empty subset), the second company can present any subset of elements from $\{b_1, b_2, \ldots, b_m\}$ (possibly empty subset). There shouldn't be equal elements in the subsets.

Help the representatives select the sets in such a way that no element is presented in both sets and the total income is the maximum possible.


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 10^5$)  — the number of elements discovered by ChemForces.

The $i$-th of the next $n$ lines contains two integers $a_i$ and $x_i$ ($1 \leq a_i \leq 10^9$, $1 \leq x_i \leq 10^9$)  — the index of the $i$-th element and the income of its usage on the exhibition. It is guaranteed that all $a_i$ are distinct.

The next line contains a single integer $m$ ($1 \leq m \leq 10^5$)  — the number of chemicals invented by TopChemist.

The $j$-th of the next $m$ lines contains two integers $b_j$ and $y_j$, ($1 \leq b_j \leq 10^9$, $1 \leq y_j \leq 10^9$)  — the index of the $j$-th element and the income of its usage on the exhibition. It is guaranteed that all $b_j$ are distinct.


-----Output-----

Print the maximum total income you can obtain by choosing the sets for both companies in such a way that no element is presented in both sets.


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

Output
24

Input
1
1000000000 239
3
14 15
92 65
35 89

Output
408



-----Note-----

In the first example ChemForces can choose the set ($3, 7$), while TopChemist can choose ($1, 2, 4$). This way the total income is $(10 + 2) + (4 + 4 + 4) = 24$.

In the second example ChemForces can choose the only element $10^9$, while TopChemist can choose ($14, 92, 35$). This way the total income is $(239) + (15 + 65 + 89) = 408$.
user: Alice's hair is growing by leaps and bounds. Maybe the cause of it is the excess of vitamins, or maybe it is some black magic...

To prevent this, Alice decided to go to the hairdresser. She wants for her hair length to be at most $l$ centimeters after haircut, where $l$ is her favorite number. Suppose, that the Alice's head is a straight line on which $n$ hairlines grow. Let's number them from $1$ to $n$. With one swing of the scissors the hairdresser can shorten all hairlines on any segment to the length $l$, given that all hairlines on that segment had length strictly greater than $l$. The hairdresser wants to complete his job as fast as possible, so he will make the least possible number of swings of scissors, since each swing of scissors takes one second.

Alice hasn't decided yet when she would go to the hairdresser, so she asked you to calculate how much time the haircut would take depending on the time she would go to the hairdresser. In particular, you need to process queries of two types:  $0$ — Alice asks how much time the haircut would take if she would go to the hairdresser now.  $1$ $p$ $d$ — $p$-th hairline grows by $d$ centimeters. 

Note, that in the request $0$ Alice is interested in hypothetical scenario of taking a haircut now, so no hairlines change their length.


-----Input-----

The first line contains three integers $n$, $m$ and $l$ ($1 \le n, m \le 100\,000$, $1 \le l \le 10^9$) — the number of hairlines, the number of requests and the favorite number of Alice.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the initial lengths of all hairlines of Alice.

Each of the following $m$ lines contains a request in the format described in the statement.

The request description starts with an integer $t_i$. If $t_i = 0$, then you need to find the time the haircut would take. Otherwise, $t_i = 1$ and in this moment one hairline grows. The rest of the line than contains two more integers: $p_i$ and $d_i$ ($1 \le p_i \le n$, $1 \le d_i \le 10^9$) — the number of the hairline and the length it grows by.


-----Output-----

For each query of type $0$ print the time the haircut would take.


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

Output
1
2
2
1



-----Note-----

Consider the first example:  Initially lengths of hairlines are equal to $1, 2, 3, 4$ and only $4$-th hairline is longer $l=3$, and hairdresser can cut it in $1$ second.  Then Alice's second hairline grows, the lengths of hairlines are now equal to $1, 5, 3, 4$  Now haircut takes two seonds: two swings are required: for the $4$-th hairline and for the $2$-nd.  Then Alice's first hairline grows, the lengths of hairlines are now equal to $4, 5, 3, 4$  The haircut still takes two seconds: with one swing hairdresser can cut $4$-th hairline and with one more swing cut the segment from $1$-st to $2$-nd hairline.  Then Alice's third hairline grows, the lengths of hairlines are now equal to $4, 5, 4, 4$  Now haircut takes only one second: with one swing it is possible to cut the segment from $1$-st hairline to the $4$-th.