meetforever/GRPO_CL huggingface dataset:
user: City X consists of n vertical and n horizontal infinite roads, forming n × n intersections. Roads (both vertical and horizontal) are numbered from 1 to n, and the intersections are indicated by the numbers of the roads that form them.

Sand roads have long been recognized out of date, so the decision was made to asphalt them. To do this, a team of workers was hired and a schedule of work was made, according to which the intersections should be asphalted.

Road repairs are planned for n^2 days. On the i-th day of the team arrives at the i-th intersection in the list and if none of the two roads that form the intersection were already asphalted they asphalt both roads. Otherwise, the team leaves the intersection, without doing anything with the roads.

According to the schedule of road works tell in which days at least one road will be asphalted.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50) — the number of vertical and horizontal roads in the city. 

Next n^2 lines contain the order of intersections in the schedule. The i-th of them contains two numbers h_{i}, v_{i} (1 ≤ h_{i}, v_{i} ≤ n), separated by a space, and meaning that the intersection that goes i-th in the timetable is at the intersection of the h_{i}-th horizontal and v_{i}-th vertical roads. It is guaranteed that all the intersections in the timetable are distinct.


-----Output-----

In the single line print the numbers of the days when road works will be in progress in ascending order. The days are numbered starting from 1.


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

Output
1 4 

Input
1
1 1

Output
1 



-----Note-----

In the sample the brigade acts like that:  On the first day the brigade comes to the intersection of the 1-st horizontal and the 1-st vertical road. As none of them has been asphalted, the workers asphalt the 1-st vertical and the 1-st horizontal road;  On the second day the brigade of the workers comes to the intersection of the 1-st horizontal and the 2-nd vertical road. The 2-nd vertical road hasn't been asphalted, but as the 1-st horizontal road has been asphalted on the first day, the workers leave and do not asphalt anything;  On the third day the brigade of the workers come to the intersection of the 2-nd horizontal and the 1-st vertical road. The 2-nd horizontal road hasn't been asphalted but as the 1-st vertical road has been asphalted on the first day, the workers leave and do not asphalt anything;  On the fourth day the brigade come to the intersection formed by the intersection of the 2-nd horizontal and 2-nd vertical road. As none of them has been asphalted, the workers asphalt the 2-nd vertical and the 2-nd horizontal road.
user: Heidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $s$ spaceships, each with a certain attacking power $a$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $b$ bases, each with a certain defensive power $d$, and a certain amount of gold $g$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.


-----Input-----

The first line contains integers $s$ and $b$ ($1 \leq s, b \leq 10^5$), the number of spaceships and the number of bases, respectively.

The second line contains $s$ integers $a$ ($0 \leq a \leq 10^9$), the attacking power of each spaceship.

The next $b$ lines contain integers $d, g$ ($0 \leq d \leq 10^9$, $0 \leq g \leq 10^4$), the defensive power and the gold of each base, respectively.


-----Output-----

Print $s$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.


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

Output
1 9 11 9 11



-----Note-----

The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.
user: Sereja has an array a, consisting of n integers a_1, a_2, ..., a_{n}. The boy cannot sit and do nothing, he decided to study an array. Sereja took a piece of paper and wrote out m integers l_1, l_2, ..., l_{m} (1 ≤ l_{i} ≤ n). For each number l_{i} he wants to know how many distinct numbers are staying on the positions l_{i}, l_{i} + 1, ..., n. Formally, he want to find the number of distinct numbers among a_{l}_{i}, a_{l}_{i} + 1, ..., a_{n}.?

Sereja wrote out the necessary array elements but the array was so large and the boy was so pressed for time. Help him, find the answer for the described question for each l_{i}.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5) — the array elements.

Next m lines contain integers l_1, l_2, ..., l_{m}. The i-th line contains integer l_{i} (1 ≤ l_{i} ≤ n).


-----Output-----

Print m lines — on the i-th line print the answer to the number l_{i}.


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

Output
6
6
6
6
6
5
4
3
2
1
user: The Department of economic development of IT City created a model of city development till year 2100.

To prepare report about growth perspectives it is required to get growth estimates from the model.

To get the growth estimates it is required to solve a quadratic equation. Since the Department of economic development of IT City creates realistic models only, that quadratic equation has a solution, moreover there are exactly two different real roots.

The greater of these roots corresponds to the optimistic scenario, the smaller one corresponds to the pessimistic one. Help to get these estimates, first the optimistic, then the pessimistic one.


-----Input-----

The only line of the input contains three integers a, b, c ( - 1000 ≤ a, b, c ≤ 1000) — the coefficients of ax^2 + bx + c = 0 equation.


-----Output-----

In the first line output the greater of the equation roots, in the second line output the smaller one. Absolute or relative error should not be greater than 10^{ - 6}.


-----Examples-----
Input
1 30 200

Output
-10.000000000000000
-20.000000000000000
user: In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.

For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 2^0, 2^1 and 2^2 respectively.

Calculate the answer for t values of n.


-----Input-----

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.

Each of next t lines contains a single integer n (1 ≤ n ≤ 10^9).


-----Output-----

Print the requested sum for each of t integers n given in the input.


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

Output
-4
499999998352516354



-----Note-----

The answer for the first sample is explained in the statement.
user: Janusz is a businessman. He owns a company "Januszex", which produces games for teenagers. Last hit of Januszex was a cool one-person game "Make it one". The player is given a sequence of $n$ integers $a_i$.

It is allowed to select any subset of them, and the score is equal to the greatest common divisor of selected elements. The goal is to take as little elements as it is possible, getting the score $1$. Now Janusz wonders, for given sequence, how much elements should the player choose?


-----Input-----

The first line contains an only integer $n$ ($1 \le n \le 300\,000$) — the number of integers in the sequence.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 300\,000$).


-----Output-----

If there is no subset of the given sequence with gcd equal to $1$, output -1.

Otherwise, output exactly one integer — the size of the smallest subset with gcd equal to $1$.


-----Examples-----
Input
3
10 6 15

Output
3

Input
3
2 4 6

Output
-1

Input
7
30 60 21 42 70 15 30

Output
3



-----Note-----

In the first example, selecting a subset of all numbers gives a gcd of $1$ and for all smaller subsets the gcd is greater than $1$.

In the second example, for all subsets of numbers the gcd is at least $2$.
user: One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by $n$ machines, and the power of the $i$-th machine is $a_i$. 

This year 2D decided to cultivate a new culture, but what exactly he didn't say. For the successful growth of the new culture, it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer $x$, then choose one machine and reduce the power of its machine by $x$ times, and at the same time increase the power of one another machine by $x$ times (powers of all the machines must stay positive integers). Note that he may not do that if he wants. More formally, 2D can choose two such indices $i$ and $j$, and one integer $x$ such that $x$ is a divisor of $a_i$, and change powers as following: $a_i = \frac{a_i}{x}$, $a_j = a_j \cdot x$

Sasha is very curious, that's why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can't cope with computations, help him!


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 5 \cdot 10^4$) — the number of machines.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 100$) — the powers of the machines.


-----Output-----

Print one integer — minimum total power.


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

Output
14

Input
4
4 2 4 4

Output
14

Input
5
2 4 2 3 7

Output
18



-----Note-----

In the first example, the farmer can reduce the power of the $4$-th machine by $2$ times, and increase the power of the $1$-st machine by $2$ times, then the powers will be: $[2, 2, 3, 2, 5]$.

In the second example, the farmer can reduce the power of the $3$-rd machine by $2$ times, and increase the power of the $2$-nd machine by $2$ times. At the same time, the farmer can leave is be as it is and the total power won't change.

In the third example, it is optimal to leave it be as it is.
user: Scientists say a lot about the problems of global warming and cooling of the Earth. Indeed, such natural phenomena strongly influence all life on our planet.

Our hero Vasya is quite concerned about the problems. He decided to try a little experiment and observe how outside daily temperature changes. He hung out a thermometer on the balcony every morning and recorded the temperature. He had been measuring the temperature for the last n days. Thus, he got a sequence of numbers t_1, t_2, ..., t_{n}, where the i-th number is the temperature on the i-th day.

Vasya analyzed the temperature statistics in other cities, and came to the conclusion that the city has no environmental problems, if first the temperature outside is negative for some non-zero number of days, and then the temperature is positive for some non-zero number of days. More formally, there must be a positive integer k (1 ≤ k ≤ n - 1) such that t_1 < 0, t_2 < 0, ..., t_{k} < 0 and t_{k} + 1 > 0, t_{k} + 2 > 0, ..., t_{n} > 0. In particular, the temperature should never be zero. If this condition is not met, Vasya decides that his city has environmental problems, and gets upset.

You do not want to upset Vasya. Therefore, you want to select multiple values of temperature and modify them to satisfy Vasya's condition. You need to know what the least number of temperature values needs to be changed for that.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^5) — the number of days for which Vasya has been measuring the temperature. 

The second line contains a sequence of n integers t_1, t_2, ..., t_{n} (|t_{i}| ≤ 10^9) — the sequence of temperature values. Numbers t_{i} are separated by single spaces.


-----Output-----

Print a single integer — the answer to the given task.


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

Output
1

Input
5
0 -1 1 2 -5

Output
2



-----Note-----

Note to the first sample: there are two ways to change exactly one number so that the sequence met Vasya's condition. You can either replace the first number 1 by any negative number or replace the number -2 by any positive number.
user: The black king is standing on a chess field consisting of 10^9 rows and 10^9 columns. We will consider the rows of the field numbered with integers from 1 to 10^9 from top to bottom. The columns are similarly numbered with integers from 1 to 10^9 from left to right. We will denote a cell of the field that is located in the i-th row and j-th column as (i, j).

You know that some squares of the given chess field are allowed. All allowed cells of the chess field are given as n segments. Each segment is described by three integers r_{i}, a_{i}, b_{i} (a_{i} ≤ b_{i}), denoting that cells in columns from number a_{i} to number b_{i} inclusive in the r_{i}-th row are allowed.

Your task is to find the minimum number of moves the king needs to get from square (x_0, y_0) to square (x_1, y_1), provided that he only moves along the allowed cells. In other words, the king can be located only on allowed cells on his way.

Let us remind you that a chess king can move to any of the neighboring cells in one move. Two cells of a chess field are considered neighboring if they share at least one point.


-----Input-----

The first line contains four space-separated integers x_0, y_0, x_1, y_1 (1 ≤ x_0, y_0, x_1, y_1 ≤ 10^9), denoting the initial and the final positions of the king.

The second line contains a single integer n (1 ≤ n ≤ 10^5), denoting the number of segments of allowed cells. Next n lines contain the descriptions of these segments. The i-th line contains three space-separated integers r_{i}, a_{i}, b_{i} (1 ≤ r_{i}, a_{i}, b_{i} ≤ 10^9, a_{i} ≤ b_{i}), denoting that cells in columns from number a_{i} to number b_{i} inclusive in the r_{i}-th row are allowed. Note that the segments of the allowed cells can intersect and embed arbitrarily.

It is guaranteed that the king's initial and final position are allowed cells. It is guaranteed that the king's initial and the final positions do not coincide. It is guaranteed that the total length of all given segments doesn't exceed 10^5.


-----Output-----

If there is no path between the initial and final position along allowed cells, print -1.

Otherwise print a single integer — the minimum number of moves the king needs to get from the initial position to the final one.


-----Examples-----
Input
5 7 6 11
3
5 3 8
6 7 11
5 2 5

Output
4

Input
3 4 3 10
3
3 1 4
4 5 9
3 10 10

Output
6

Input
1 1 2 10
2
1 1 3
2 6 10

Output
-1
user: There are n pictures delivered for the new exhibition. The i-th painting has beauty a_{i}. We know that a visitor becomes happy every time he passes from a painting to a more beautiful one.

We are allowed to arranged pictures in any order. What is the maximum possible number of times the visitor may become happy while passing all pictures from first to last? In other words, we are allowed to rearrange elements of a in any order. What is the maximum possible number of indices i (1 ≤ i ≤ n - 1), such that a_{i} + 1 > a_{i}.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 1000) — the number of painting.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000), where a_{i} means the beauty of the i-th painting.


-----Output-----

Print one integer — the maximum possible number of neighbouring pairs, such that a_{i} + 1 > a_{i}, after the optimal rearrangement.


-----Examples-----
Input
5
20 30 10 50 40

Output
4

Input
4
200 100 100 200

Output
2



-----Note-----

In the first sample, the optimal order is: 10, 20, 30, 40, 50.

In the second sample, the optimal order is: 100, 200, 100, 200.
user: You wrote down all integers from $0$ to $10^n - 1$, padding them with leading zeroes so their lengths are exactly $n$. For example, if $n = 3$ then you wrote out 000, 001, ..., 998, 999.

A block in an integer $x$ is a consecutive segment of equal digits that cannot be extended to the left or to the right.

For example, in the integer $00027734000$ there are three blocks of length $1$, one block of length $2$ and two blocks of length $3$.

For all integers $i$ from $1$ to $n$ count the number of blocks of length $i$ among the written down integers.

Since these integers may be too large, print them modulo $998244353$.


-----Input-----

The only line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).


-----Output-----

In the only line print $n$ integers. The $i$-th integer is equal to the number of blocks of length $i$.

Since these integers may be too large, print them modulo $998244353$.


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

Output
10

Input
2

Output
180 10
user: Formula 1 officials decided to introduce new competition. Cars are replaced by space ships and number of points awarded can differ per race.

Given the current ranking in the competition and points distribution for the next race, your task is to calculate the best possible ranking for a given astronaut after the next race. It's guaranteed that given astronaut will have unique number of points before the race.


-----Input-----

The first line contains two integer numbers $N$ ($1 \leq N \leq 200000$) representing number of F1 astronauts, and current position of astronaut $D$ ($1 \leq D \leq N$) you want to calculate best ranking for (no other competitor will have the same number of points before the race).

The second line contains $N$ integer numbers $S_k$ ($0 \leq S_k \leq 10^8$, $k=1...N$), separated by a single space, representing current ranking of astronauts. Points are sorted in non-increasing order.

The third line contains $N$ integer numbers $P_k$ ($0 \leq P_k \leq 10^8$, $k=1...N$), separated by a single space, representing point awards for the next race. Points are sorted in non-increasing order, so winner of the race gets the maximum number of points.


-----Output-----

Output contains one integer number — the best possible ranking for astronaut after the race. If multiple astronauts have the same score after the race, they all share the best ranking.


-----Example-----
Input
4 3
50 30 20 10
15 10 7 3

Output
2



-----Note-----

If the third ranked astronaut wins the race, he will have 35 points. He cannot take the leading position, but he can overtake the second position if the second ranked astronaut finishes the race at the last position.
user: Ivan recently bought a detective book. The book is so interesting that each page of this book introduces some sort of a mystery, which will be explained later. The $i$-th page contains some mystery that will be explained on page $a_i$ ($a_i \ge i$).

Ivan wants to read the whole book. Each day, he reads the first page he didn't read earlier, and continues to read the following pages one by one, until all the mysteries he read about are explained and clear to him (Ivan stops if there does not exist any page $i$ such that Ivan already has read it, but hasn't read page $a_i$). After that, he closes the book and continues to read it on the following day from the next page.

How many days will it take to read the whole book?


-----Input-----

The first line contains single integer $n$ ($1 \le n \le 10^4$) — the number of pages in the book.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($i \le a_i \le n$), where $a_i$ is the number of page which contains the explanation of the mystery on page $i$.


-----Output-----

Print one integer — the number of days it will take to read the whole book.


-----Example-----
Input
9
1 3 3 6 7 6 8 8 9

Output
4



-----Note-----

Explanation of the example test:

During the first day Ivan will read only the first page. During the second day Ivan will read pages number $2$ and $3$. During the third day — pages $4$-$8$. During the fourth (and the last) day Ivan will read remaining page number $9$.
user: You have an integer $n$. Let's define following tree generation as McDic's generation:  Make a complete and full binary tree of $2^{n} - 1$ vertices. Complete and full binary tree means a tree that exactly one vertex is a root, all leaves have the same depth (distance from the root), and all non-leaf nodes have exactly two child nodes.  Select a non-root vertex $v$ from that binary tree.  Remove $v$ from tree and make new edges between $v$'s parent and $v$'s direct children. If $v$ has no children, then no new edges will be made. 

You have a tree. Determine if this tree can be made by McDic's generation. If yes, then find the parent vertex of removed vertex in tree.


-----Input-----

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

The $i$-th of the next $2^{n} - 3$ lines contains two integers $a_{i}$ and $b_{i}$ ($1 \le a_{i} \lt b_{i} \le 2^{n} - 2$) — meaning there is an edge between $a_{i}$ and $b_{i}$. It is guaranteed that the given edges form a tree.


-----Output-----

Print two lines.

In the first line, print a single integer — the number of answers. If given tree cannot be made by McDic's generation, then print $0$.

In the second line, print all possible answers in ascending order, separated by spaces. If the given tree cannot be made by McDic's generation, then don't print anything.


-----Examples-----
Input
4
1 2
1 3
2 4
2 5
3 6
3 13
3 14
4 7
4 8
5 9
5 10
6 11
6 12

Output
1
3

Input
2
1 2

Output
2
1 2

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

Output
0



-----Note-----

In the first example, $3$ is the only possible answer. $8$ 

In the second example, there are $2$ possible answers. [Image] 

In the third example, the tree can't be generated by McDic's generation.