meetforever/GRPO_CL huggingface dataset:
user: Vasya commutes by train every day. There are n train stations in the city, and at the i-th station it's possible to buy only tickets to stations from i + 1 to a_{i} inclusive. No tickets are sold at the last station.

Let ρ_{i}, j be the minimum number of tickets one needs to buy in order to get from stations i to station j. As Vasya is fond of different useless statistic he asks you to compute the sum of all values ρ_{i}, j among all pairs 1 ≤ i < j ≤ n.


-----Input-----

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

The second line contains n - 1 integer a_{i} (i + 1 ≤ a_{i} ≤ n), the i-th of them means that at the i-th station one may buy tickets to each station from i + 1 to a_{i} inclusive.


-----Output-----

Print the sum of ρ_{i}, j among all pairs of 1 ≤ i < j ≤ n.


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

Output
6

Input
5
2 3 5 5

Output
17



-----Note-----

In the first sample it's possible to get from any station to any other (with greater index) using only one ticket. The total number of pairs is 6, so the answer is also 6.

Consider the second sample:   ρ_{1, 2} = 1  ρ_{1, 3} = 2  ρ_{1, 4} = 3  ρ_{1, 5} = 3  ρ_{2, 3} = 1  ρ_{2, 4} = 2  ρ_{2, 5} = 2  ρ_{3, 4} = 1  ρ_{3, 5} = 1  ρ_{4, 5} = 1 

Thus the answer equals 1 + 2 + 3 + 3 + 1 + 2 + 2 + 1 + 1 + 1 = 17.
user: As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are n planes on Earth, numbered from 1 to n, and the plane with number i likes the plane with number f_{i}, where 1 ≤ f_{i} ≤ n and f_{i} ≠ i.

We call a love triangle a situation in which plane A likes plane B, plane B likes plane C and plane C likes plane A. Find out if there is any love triangle on Earth.


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of planes.

The second line contains n integers f_1, f_2, ..., f_{n} (1 ≤ f_{i} ≤ n, f_{i} ≠ i), meaning that the i-th plane likes the f_{i}-th.


-----Output-----

Output «YES» if there is a love triangle consisting of planes on Earth. Otherwise, output «NO».

You can output any letter in lower case or in upper case.


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

Output
YES

Input
5
5 5 5 5 1

Output
NO



-----Note-----

In first example plane 2 likes plane 4, plane 4 likes plane 1, plane 1 likes plane 2 and that is a love triangle.

In second example there are no love triangles.
user: The classic programming language of Bitland is Bit++. This language is so peculiar and complicated.

The language is that peculiar as it has exactly one variable, called x. Also, there are two operations:

  Operation ++ increases the value of variable x by 1.  Operation -- decreases the value of variable x by 1. 

A statement in language Bit++ is a sequence, consisting of exactly one operation and one variable x. The statement is written without spaces, that is, it can only contain characters "+", "-", "X". Executing a statement means applying the operation it contains.

A programme in Bit++ is a sequence of statements, each of them needs to be executed. Executing a programme means executing all the statements it contains.

You're given a programme in language Bit++. The initial value of x is 0. Execute the programme and find its final value (the value of the variable when this programme is executed).


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 150) — the number of statements in the programme.

Next n lines contain a statement each. Each statement contains exactly one operation (++ or --) and exactly one variable x (denoted as letter «X»). Thus, there are no empty statements. The operation and the variable can be written in any order.


-----Output-----

Print a single integer — the final value of x.


-----Examples-----
Input
1
++X

Output
1

Input
2
X++
--X

Output
0
user: The construction of subway in Bertown is almost finished! The President of Berland will visit this city soon to look at the new subway himself.

There are n stations in the subway. It was built according to the Bertown Transport Law:

  For each station i there exists exactly one train that goes from this station. Its destination station is p_{i}, possibly p_{i} = i;  For each station i there exists exactly one station j such that p_{j} = i. 

The President will consider the convenience of subway after visiting it. The convenience is the number of ordered pairs (x, y) such that person can start at station x and, after taking some subway trains (possibly zero), arrive at station y (1 ≤ x, y ≤ n).

The mayor of Bertown thinks that if the subway is not convenient enough, then the President might consider installing a new mayor (and, of course, the current mayor doesn't want it to happen). Before President visits the city mayor has enough time to rebuild some paths of subway, thus changing the values of p_{i} for not more than two subway stations. Of course, breaking the Bertown Transport Law is really bad, so the subway must be built according to the Law even after changes.

The mayor wants to do these changes in such a way that the convenience of the subway is maximized. Help him to calculate the maximum possible convenience he can get! 


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 100000) — the number of stations.

The second line contains n integer numbers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) — the current structure of the subway. All these numbers are distinct.


-----Output-----

Print one number — the maximum possible value of convenience.


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

Output
9

Input
5
1 5 4 3 2

Output
17



-----Note-----

In the first example the mayor can change p_2 to 3 and p_3 to 1, so there will be 9 pairs: (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3).

In the second example the mayor can change p_2 to 4 and p_3 to 5.
user: One day Jeff got hold of an integer sequence a_1, a_2, ..., a_{n} of length n. The boy immediately decided to analyze the sequence. For that, he needs to find all values of x, for which these conditions hold:

  x occurs in sequence a.  Consider all positions of numbers x in the sequence a (such i, that a_{i} = x). These numbers, sorted in the increasing order, must form an arithmetic progression. 

Help Jeff, find all x that meet the problem conditions.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The next line contains integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). The numbers are separated by spaces.


-----Output-----

In the first line print integer t — the number of valid x. On each of the next t lines print two integers x and p_{x}, where x is current suitable value, p_{x} is the common difference between numbers in the progression (if x occurs exactly once in the sequence, p_{x} must equal 0). Print the pairs in the order of increasing x.


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

Output
1
2 0

Input
8
1 2 1 3 1 2 1 5

Output
4
1 2
2 4
3 0
5 0



-----Note-----

In the first test 2 occurs exactly once in the sequence, ergo p_2 = 0.
user: One tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by the number of balloons they have. It means that one's place is equal to the number of teams with more balloons, increased by 1. For example, if there are seven teams with more balloons, you get the eight place. Ties are allowed.

You should know that it's important to eat before a contest. If the number of balloons of a team is greater than the weight of this team, the team starts to float in the air together with their workstation. They eventually touch the ceiling, what is strictly forbidden by the rules. The team is then disqualified and isn't considered in the standings.

A contest has just finished. There are n teams, numbered 1 through n. The i-th team has t_{i} balloons and weight w_{i}. It's guaranteed that t_{i} doesn't exceed w_{i} so nobody floats initially.

Limak is a member of the first team. He doesn't like cheating and he would never steal balloons from other teams. Instead, he can give his balloons away to other teams, possibly making them float. Limak can give away zero or more balloons of his team. Obviously, he can't give away more balloons than his team initially has.

What is the best place Limak can get?


-----Input-----

The first line of the standard input contains one integer n (2 ≤ n ≤ 300 000) — the number of teams.

The i-th of n following lines contains two integers t_{i} and w_{i} (0 ≤ t_{i} ≤ w_{i} ≤ 10^18) — respectively the number of balloons and the weight of the i-th team. Limak is a member of the first team.


-----Output-----

Print one integer denoting the best place Limak can get.


-----Examples-----
Input
8
20 1000
32 37
40 1000
45 50
16 16
16 16
14 1000
2 1000

Output
3

Input
7
4 4
4 4
4 4
4 4
4 4
4 4
5 5

Output
2

Input
7
14000000003 1000000000000000000
81000000000 88000000000
5000000000 7000000000
15000000000 39000000000
46000000000 51000000000
0 1000000000
0 0

Output
2



-----Note-----

In the first sample, Limak has 20 balloons initially. There are three teams with more balloons (32, 40 and 45 balloons), so Limak has the fourth place initially. One optimal strategy is: Limak gives 6 balloons away to a team with 32 balloons and weight 37, which is just enough to make them fly. Unfortunately, Limak has only 14 balloons now and he would get the fifth place. Limak gives 6 balloons away to a team with 45 balloons. Now they have 51 balloons and weight 50 so they fly and get disqualified. Limak gives 1 balloon to each of two teams with 16 balloons initially. Limak has 20 - 6 - 6 - 1 - 1 = 6 balloons. There are three other teams left and their numbers of balloons are 40, 14 and 2. Limak gets the third place because there are two teams with more balloons. 

In the second sample, Limak has the second place and he can't improve it.

In the third sample, Limak has just enough balloons to get rid of teams 2, 3 and 5 (the teams with 81 000 000 000, 5 000 000 000 and 46 000 000 000 balloons respectively). With zero balloons left, he will get the second place (ex-aequo with team 6 and team 7).
user: Each month Blake gets the report containing main economic indicators of the company "Blake Technologies". There are n commodities produced by the company. For each of them there is exactly one integer in the final report, that denotes corresponding revenue. Before the report gets to Blake, it passes through the hands of m managers. Each of them may reorder the elements in some order. Namely, the i-th manager either sorts first r_{i} numbers in non-descending or non-ascending order and then passes the report to the manager i + 1, or directly to Blake (if this manager has number i = m).

Employees of the "Blake Technologies" are preparing the report right now. You know the initial sequence a_{i} of length n and the description of each manager, that is value r_{i} and his favourite order. You are asked to speed up the process and determine how the final report will look like.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200 000) — the number of commodities in the report and the number of managers, respectively.

The second line contains n integers a_{i} (|a_{i}| ≤ 10^9) — the initial report before it gets to the first manager.

Then follow m lines with the descriptions of the operations managers are going to perform. The i-th of these lines contains two integers t_{i} and r_{i} ($t_{i} \in \{1,2 \}$, 1 ≤ r_{i} ≤ n), meaning that the i-th manager sorts the first r_{i} numbers either in the non-descending (if t_{i} = 1) or non-ascending (if t_{i} = 2) order.


-----Output-----

Print n integers — the final report, which will be passed to Blake by manager number m.


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

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

Output
2 4 1 3 


-----Note-----

In the first sample, the initial report looked like: 1 2 3. After the first manager the first two numbers were transposed: 2 1 3. The report got to Blake in this form.

In the second sample the original report was like this: 1 2 4 3. After the first manager the report changed to: 4 2 1 3. After the second manager the report changed to: 2 4 1 3. This report was handed over to Blake.
user: Little Dima has two sequences of points with integer coordinates: sequence (a_1, 1), (a_2, 2), ..., (a_{n}, n) and sequence (b_1, 1), (b_2, 2), ..., (b_{n}, n).

Now Dima wants to count the number of distinct sequences of points of length 2·n that can be assembled from these sequences, such that the x-coordinates of points in the assembled sequence will not decrease. Help him with that. Note that each element of the initial sequences should be used exactly once in the assembled sequence.

Dima considers two assembled sequences (p_1, q_1), (p_2, q_2), ..., (p_{2·}n, q_{2·}n) and (x_1, y_1), (x_2, y_2), ..., (x_{2·}n, y_{2·}n) distinct, if there is such i (1 ≤ i ≤ 2·n), that (p_{i}, q_{i}) ≠ (x_{i}, y_{i}).

As the answer can be rather large, print the remainder from dividing the answer by number m.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). The third line contains n integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^9). The numbers in the lines are separated by spaces.

The last line contains integer m (2 ≤ m ≤ 10^9 + 7).


-----Output-----

In the single line print the remainder after dividing the answer to the problem by number m. 


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

Output
1

Input
2
1 2
2 3
11

Output
2



-----Note-----

In the first sample you can get only one sequence: (1, 1), (2, 1). 

In the second sample you can get such sequences : (1, 1), (2, 2), (2, 1), (3, 2); (1, 1), (2, 1), (2, 2), (3, 2). Thus, the answer is 2.
user: The Physical education teacher at SESC is a sort of mathematician too. His most favorite topic in mathematics is progressions. That is why the teacher wants the students lined up in non-decreasing height form an arithmetic progression.

To achieve the goal, the gym teacher ordered a lot of magical buns from the dining room. The magic buns come in two types: when a student eats one magic bun of the first type, his height increases by one, when the student eats one magical bun of the second type, his height decreases by one. The physical education teacher, as expected, cares about the health of his students, so he does not want them to eat a lot of buns. More precisely, he wants the maximum number of buns eaten by some student to be minimum.

Help the teacher, get the maximum number of buns that some pupils will have to eat to achieve the goal of the teacher. Also, get one of the possible ways for achieving the objective, namely, the height of the lowest student in the end and the step of the resulting progression.


-----Input-----

The single line contains integer n (2 ≤ n ≤ 10^3) — the number of students. The second line contains n space-separated integers — the heights of all students. The height of one student is an integer which absolute value doesn't exceed 10^4.


-----Output-----

In the first line print the maximum number of buns eaten by some student to achieve the teacher's aim. In the second line, print two space-separated integers — the height of the lowest student in the end and the step of the progression. Please, pay attention that the step should be non-negative.

If there are multiple possible answers, you can print any of them.


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

Output
2
-3 1

Input
5
2 -3 -1 -4 3

Output
1
-4 2



-----Note-----

Lets look at the first sample. We can proceed in the following manner:

  don't feed the 1-st student, his height will stay equal to -3;  give two buns of the first type to the 2-nd student, his height become equal to -2;  give two buns of the first type to the 3-rd student, his height become equal to 0;  give two buns of the first type to the 4-th student, his height become equal to -1;  give two buns of the second type to the 5-th student, his height become equal to 1. 

To sum it up, when the students line up in non-decreasing height it will be an arithmetic progression: -3, -2, -1, 0, 1. The height of the lowest student is equal to -3, the step of the progression is equal to 1. The maximum number of buns eaten by one student is equal to 2.
user: Shaass has decided to hunt some birds. There are n horizontal electricity wires aligned parallel to each other. Wires are numbered 1 to n from top to bottom. On each wire there are some oskols sitting next to each other. Oskol is the name of a delicious kind of birds in Shaass's territory. Supposed there are a_{i} oskols sitting on the i-th wire. $40$ 

Sometimes Shaass shots one of the birds and the bird dies (suppose that this bird sat at the i-th wire). Consequently all the birds on the i-th wire to the left of the dead bird get scared and jump up on the wire number i - 1, if there exists no upper wire they fly away. Also all the birds to the right of the dead bird jump down on wire number i + 1, if there exists no such wire they fly away. 

Shaass has shot m birds. You're given the initial number of birds on each wire, tell him how many birds are sitting on each wire after the shots.


-----Input-----

The first line of the input contains an integer n, (1 ≤ n ≤ 100). The next line contains a list of space-separated integers a_1, a_2, ..., a_{n}, (0 ≤ a_{i} ≤ 100). 

The third line contains an integer m, (0 ≤ m ≤ 100). Each of the next m lines contains two integers x_{i} and y_{i}. The integers mean that for the i-th time Shaass shoot the y_{i}-th (from left) bird on the x_{i}-th wire, (1 ≤ x_{i} ≤ n, 1 ≤ y_{i}). It's guaranteed there will be at least y_{i} birds on the x_{i}-th wire at that moment.


-----Output-----

On the i-th line of the output print the number of birds on the i-th wire.


-----Examples-----
Input
5
10 10 10 10 10
5
2 5
3 13
2 12
1 13
4 6

Output
0
12
5
0
16

Input
3
2 4 1
1
2 2

Output
3
0
3
user: Think of New York as a rectangular grid consisting of N vertical avenues numerated from 1 to N and M horizontal streets numerated 1 to M. C friends are staying at C hotels located at some street-avenue crossings. They are going to celebrate birthday of one of them in the one of H restaurants also located at some street-avenue crossings. They also want that the maximum distance covered by one of them while traveling to the restaurant to be minimum possible. Help friends choose optimal restaurant for a celebration.

Suppose that the distance between neighboring crossings are all the same equal to one kilometer.


-----Input-----

The first line contains two integers N и M — size of the city (1 ≤ N, M ≤ 10^9). In the next line there is a single integer C (1 ≤ C ≤ 10^5) — the number of hotels friends stayed at. Following C lines contain descriptions of hotels, each consisting of two coordinates x and y (1 ≤ x ≤ N, 1 ≤ y ≤ M). The next line contains an integer H — the number of restaurants (1 ≤ H ≤ 10^5). Following H lines contain descriptions of restaurants in the same format.

Several restaurants and hotels may be located near the same crossing.


-----Output-----

In the first line output the optimal distance. In the next line output index of a restaurant that produces this optimal distance. If there are several possibilities, you are allowed to output any of them.


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

Output
6
2
user: Let's denote correct match equation (we will denote it as CME) an equation $a + b = c$ there all integers $a$, $b$ and $c$ are greater than zero.

For example, equations $2 + 2 = 4$ (||+||=||||) and $1 + 2 = 3$ (|+||=|||) are CME but equations $1 + 2 = 4$ (|+||=||||), $2 + 2 = 3$ (||+||=|||), and $0 + 1 = 1$ (+|=|) are not.

Now, you have $n$ matches. You want to assemble a CME using all your matches. Unfortunately, it is possible that you can't assemble the CME using all matches. But you can buy some extra matches and then assemble CME!

For example, if $n = 2$, you can buy two matches and assemble |+|=||, and if $n = 5$ you can buy one match and assemble ||+|=|||.  [Image] 

Calculate the minimum number of matches which you have to buy for assembling CME.

Note, that you have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) — the number of queries.

The only line of each query contains one integer $n$ ($2 \le n \le 10^9$) — the number of matches.


-----Output-----

For each test case print one integer in single line — the minimum number of matches which you have to buy for assembling CME. 


-----Example-----
Input
4
2
5
8
11

Output
2
1
0
1



-----Note-----

The first and second queries are explained in the statement.

In the third query, you can assemble $1 + 3 = 4$ (|+|||=||||) without buying matches.

In the fourth query, buy one match and assemble $2 + 4 = 6$ (||+||||=||||||).
user: You are given $n$ intervals in form $[l; r]$ on a number line.

You are also given $m$ queries in form $[x; y]$. What is the minimal number of intervals you have to take so that every point (not necessarily integer) from $x$ to $y$ is covered by at least one of them? 

If you can't choose intervals so that every point from $x$ to $y$ is covered, then print -1 for that query.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of intervals and the number of queries, respectively.

Each of the next $n$ lines contains two integer numbers $l_i$ and $r_i$ ($0 \le l_i < r_i \le 5 \cdot 10^5$) — the given intervals.

Each of the next $m$ lines contains two integer numbers $x_i$ and $y_i$ ($0 \le x_i < y_i \le 5 \cdot 10^5$) — the queries.


-----Output-----

Print $m$ integer numbers. The $i$-th number should be the answer to the $i$-th query: either the minimal number of intervals you have to take so that every point (not necessarily integer) from $x_i$ to $y_i$ is covered by at least one of them or -1 if you can't choose intervals so that every point from $x_i$ to $y_i$ is covered.


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

Output
1
2
1

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

Output
1
1
-1
-1



-----Note-----

In the first example there are three queries:

  query $[1; 3]$ can be covered by interval $[1; 3]$;  query $[1; 4]$ can be covered by intervals $[1; 3]$ and $[2; 4]$. There is no way to cover $[1; 4]$ by a single interval;  query $[3; 4]$ can be covered by interval $[2; 4]$. It doesn't matter that the other points are covered besides the given query. 

In the second example there are four queries:

  query $[1; 2]$ can be covered by interval $[1; 3]$. Note that you can choose any of the two given intervals $[1; 3]$;  query $[1; 3]$ can be covered by interval $[1; 3]$;  query $[1; 4]$ can't be covered by any set of intervals;  query $[1; 5]$ can't be covered by any set of intervals. Note that intervals $[1; 3]$ and $[4; 5]$ together don't cover $[1; 5]$ because even non-integer points should be covered. Here $3.5$, for example, isn't covered.
user: Once Max found an electronic calculator from his grandfather Dovlet's chest. He noticed that the numbers were written with seven-segment indicators (https://en.wikipedia.org/wiki/Seven-segment_display). [Image] 

Max starts to type all the values from a to b. After typing each number Max resets the calculator. Find the total number of segments printed on the calculator.

For example if a = 1 and b = 3 then at first the calculator will print 2 segments, then — 5 segments and at last it will print 5 segments. So the total number of printed segments is 12.


-----Input-----

The only line contains two integers a, b (1 ≤ a ≤ b ≤ 10^6) — the first and the last number typed by Max.


-----Output-----

Print the only integer a — the total number of printed segments.


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

Output
12

Input
10 15

Output
39