meetforever/GRPO_CL huggingface dataset:
user: Stepan has n pens. Every day he uses them, and on the i-th day he uses the pen number i. On the (n + 1)-th day again he uses the pen number 1, on the (n + 2)-th — he uses the pen number 2 and so on.

On every working day (from Monday to Saturday, inclusive) Stepan spends exactly 1 milliliter of ink of the pen he uses that day. On Sunday Stepan has a day of rest, he does not stend the ink of the pen he uses that day. 

Stepan knows the current volume of ink in each of his pens. Now it's the Monday morning and Stepan is going to use the pen number 1 today. Your task is to determine which pen will run out of ink before all the rest (that is, there will be no ink left in it), if Stepan will use the pens according to the conditions described above.


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 50 000) — the number of pens Stepan has.

The second line contains the sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is equal to the number of milliliters of ink which the pen number i currently has.


-----Output-----

Print the index of the pen which will run out of ink before all (it means that there will be no ink left in it), if Stepan will use pens according to the conditions described above. 

Pens are numbered in the order they are given in input data. The numeration begins from one. 

Note that the answer is always unambiguous, since several pens can not end at the same time.


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

Output
2

Input
5
5 4 5 4 4

Output
5



-----Note-----

In the first test Stepan uses ink of pens as follows:   on the day number 1 (Monday) Stepan will use the pen number 1, after that there will be 2 milliliters of ink in it;  on the day number 2 (Tuesday) Stepan will use the pen number 2, after that there will be 2 milliliters of ink in it;  on the day number 3 (Wednesday) Stepan will use the pen number 3, after that there will be 2 milliliters of ink in it;  on the day number 4 (Thursday) Stepan will use the pen number 1, after that there will be 1 milliliters of ink in it;  on the day number 5 (Friday) Stepan will use the pen number 2, after that there will be 1 milliliters of ink in it;  on the day number 6 (Saturday) Stepan will use the pen number 3, after that there will be 1 milliliters of ink in it;  on the day number 7 (Sunday) Stepan will use the pen number 1, but it is a day of rest so he will not waste ink of this pen in it;  on the day number 8 (Monday) Stepan will use the pen number 2, after that this pen will run out of ink. 

So, the first pen which will not have ink is the pen number 2.
user: Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction $\frac{a}{b}$ is called proper iff its numerator is smaller than its denominator (a < b) and that the fraction is called irreducible if its numerator and its denominator are coprime (they do not have positive common divisors except 1).

During his free time, Petya thinks about proper irreducible fractions and converts them to decimals using the calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator that was equal to n instead of the expected decimal notation. 

Petya wanted to restore the original fraction, but soon he realized that it might not be done uniquely. That's why he decided to determine maximum possible proper irreducible fraction $\frac{a}{b}$ such that sum of its numerator and denominator equals n. Help Petya deal with this problem.

 


-----Input-----

In the only line of input there is an integer n (3 ≤ n ≤ 1000), the sum of numerator and denominator of the fraction.


-----Output-----

Output two space-separated positive integers a and b, numerator and denominator of the maximum possible proper irreducible fraction satisfying the given sum.


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

Output
1 2

Input
4

Output
1 3

Input
12

Output
5 7
user: You have a plate and you want to add some gilding to it. The plate is a rectangle that we split into $w\times h$ cells. There should be $k$ gilded rings, the first one should go along the edge of the plate, the second one — $2$ cells away from the edge and so on. Each ring has a width of $1$ cell. Formally, the $i$-th of these rings should consist of all bordering cells on the inner rectangle of size $(w - 4(i - 1))\times(h - 4(i - 1))$.

 [Image] The picture corresponds to the third example. 

Your task is to compute the number of cells to be gilded.


-----Input-----

The only line contains three integers $w$, $h$ and $k$ ($3 \le w, h \le 100$, $1 \le k \le \left\lfloor \frac{min(n, m) + 1}{4}\right\rfloor$, where $\lfloor x \rfloor$ denotes the number $x$ rounded down) — the number of rows, columns and the number of rings, respectively.


-----Output-----

Print a single positive integer — the number of cells to be gilded.


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

Output
8

Input
7 9 1

Output
28

Input
7 9 2

Output
40



-----Note-----

The first example is shown on the picture below.

 [Image] 

The second example is shown on the picture below.

 [Image] 

The third example is shown in the problem description.
user: Grigory has $n$ magic stones, conveniently numbered from $1$ to $n$. The charge of the $i$-th stone is equal to $c_i$.

Sometimes Grigory gets bored and selects some inner stone (that is, some stone with index $i$, where $2 \le i \le n - 1$), and after that synchronizes it with neighboring stones. After that, the chosen stone loses its own charge, but acquires the charges from neighboring stones. In other words, its charge $c_i$ changes to $c_i' = c_{i + 1} + c_{i - 1} - c_i$.

Andrew, Grigory's friend, also has $n$ stones with charges $t_i$. Grigory is curious, whether there exists a sequence of zero or more synchronization operations, which transforms charges of Grigory's stones into charges of corresponding Andrew's stones, that is, changes $c_i$ into $t_i$ for all $i$?


-----Input-----

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

The second line contains integers $c_1, c_2, \ldots, c_n$ ($0 \le c_i \le 2 \cdot 10^9$) — the charges of Grigory's stones.

The second line contains integers $t_1, t_2, \ldots, t_n$ ($0 \le t_i \le 2 \cdot 10^9$) — the charges of Andrew's stones.


-----Output-----

If there exists a (possibly empty) sequence of synchronization operations, which changes all charges to the required ones, print "Yes".

Otherwise, print "No".


-----Examples-----
Input
4
7 2 4 12
7 15 10 12

Output
Yes

Input
3
4 4 4
1 2 3

Output
No



-----Note-----

In the first example, we can perform the following synchronizations ($1$-indexed):  First, synchronize the third stone $[7, 2, \mathbf{4}, 12] \rightarrow [7, 2, \mathbf{10}, 12]$.  Then synchronize the second stone: $[7, \mathbf{2}, 10, 12] \rightarrow [7, \mathbf{15}, 10, 12]$. 

In the second example, any operation with the second stone will not change its charge.
user: Arkady bought an air ticket from a city A to a city C. Unfortunately, there are no direct flights, but there are a lot of flights from A to a city B, and from B to C.

There are $n$ flights from A to B, they depart at time moments $a_1$, $a_2$, $a_3$, ..., $a_n$ and arrive at B $t_a$ moments later.

There are $m$ flights from B to C, they depart at time moments $b_1$, $b_2$, $b_3$, ..., $b_m$ and arrive at C $t_b$ moments later.

The connection time is negligible, so one can use the $i$-th flight from A to B and the $j$-th flight from B to C if and only if $b_j \ge a_i + t_a$.

You can cancel at most $k$ flights. If you cancel a flight, Arkady can not use it.

Arkady wants to be in C as early as possible, while you want him to be in C as late as possible. Find the earliest time Arkady can arrive at C, if you optimally cancel $k$ flights. If you can cancel $k$ or less flights in such a way that it is not possible to reach C at all, print $-1$.


-----Input-----

The first line contains five integers $n$, $m$, $t_a$, $t_b$ and $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le n + m$, $1 \le t_a, t_b \le 10^9$) — the number of flights from A to B, the number of flights from B to C, the flight time from A to B, the flight time from B to C and the number of flights you can cancel, respectively.

The second line contains $n$ distinct integers in increasing order $a_1$, $a_2$, $a_3$, ..., $a_n$ ($1 \le a_1 < a_2 < \ldots < a_n \le 10^9$) — the times the flights from A to B depart.

The third line contains $m$ distinct integers in increasing order $b_1$, $b_2$, $b_3$, ..., $b_m$ ($1 \le b_1 < b_2 < \ldots < b_m \le 10^9$) — the times the flights from B to C depart.


-----Output-----

If you can cancel $k$ or less flights in such a way that it is not possible to reach C at all, print $-1$.

Otherwise print the earliest time Arkady can arrive at C if you cancel $k$ flights in such a way that maximizes this time.


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

Output
11

Input
2 2 4 4 2
1 10
10 20

Output
-1

Input
4 3 2 3 1
1 999999998 999999999 1000000000
3 4 1000000000

Output
1000000003



-----Note-----

Consider the first example. The flights from A to B depart at time moments $1$, $3$, $5$, and $7$ and arrive at B at time moments $2$, $4$, $6$, $8$, respectively. The flights from B to C depart at time moments $1$, $2$, $3$, $9$, and $10$ and arrive at C at time moments $2$, $3$, $4$, $10$, $11$, respectively. You can cancel at most two flights. The optimal solution is to cancel the first flight from A to B and the fourth flight from B to C. This way Arkady has to take the second flight from A to B, arrive at B at time moment $4$, and take the last flight from B to C arriving at C at time moment $11$.

In the second example you can simply cancel all flights from A to B and you're done.

In the third example you can cancel only one flight, and the optimal solution is to cancel the first flight from A to B. Note that there is still just enough time to catch the last flight from B to C.
user: You are given a permutation of integers from 1 to n. Exactly once you apply the following operation to this permutation: pick a random segment and shuffle its elements. Formally:  Pick a random segment (continuous subsequence) from l to r. All $\frac{n(n + 1)}{2}$ segments are equiprobable.  Let k = r - l + 1, i.e. the length of the chosen segment. Pick a random permutation of integers from 1 to k, p_1, p_2, ..., p_{k}. All k! permutation are equiprobable.  This permutation is applied to elements of the chosen segment, i.e. permutation a_1, a_2, ..., a_{l} - 1, a_{l}, a_{l} + 1, ..., a_{r} - 1, a_{r}, a_{r} + 1, ..., a_{n} is transformed to a_1, a_2, ..., a_{l} - 1, a_{l} - 1 + p_1, a_{l} - 1 + p_2, ..., a_{l} - 1 + p_{k} - 1, a_{l} - 1 + p_{k}, a_{r} + 1, ..., a_{n}. 

Inversion if a pair of elements (not necessary neighbouring) with the wrong relative order. In other words, the number of inversion is equal to the number of pairs (i, j) such that i < j and a_{i} > a_{j}. Find the expected number of inversions after we apply exactly one operation mentioned above.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100 000) — the length of the permutation.

The second line contains n distinct integers from 1 to n — elements of the permutation.


-----Output-----

Print one real value — the expected number of inversions. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 9}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-9}$.


-----Example-----
Input
3
2 3 1

Output
1.916666666666666666666666666667
user: Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane. 

Next n lines contain two integers each x_{i}, y_{i} ( - 100 ≤ x_{i}, y_{i} ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.


-----Output-----

In the first line print an integer — the number of triangles with the non-zero area among the painted points.


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

Output
3

Input
3
0 0
1 1
2 0

Output
1

Input
1
1 1

Output
0



-----Note-----

Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).

Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).

Note to the third sample test. A single point doesn't form a single triangle.
user: Tanya wants to go on a journey across the cities of Berland. There are $n$ cities situated along the main railroad line of Berland, and these cities are numbered from $1$ to $n$. 

Tanya plans her journey as follows. First of all, she will choose some city $c_1$ to start her journey. She will visit it, and after that go to some other city $c_2 > c_1$, then to some other city $c_3 > c_2$, and so on, until she chooses to end her journey in some city $c_k > c_{k - 1}$. So, the sequence of visited cities $[c_1, c_2, \dots, c_k]$ should be strictly increasing.

There are some additional constraints on the sequence of cities Tanya visits. Each city $i$ has a beauty value $b_i$ associated with it. If there is only one city in Tanya's journey, these beauty values imply no additional constraints. But if there are multiple cities in the sequence, then for any pair of adjacent cities $c_i$ and $c_{i + 1}$, the condition $c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}$ must hold.

For example, if $n = 8$ and $b = [3, 4, 4, 6, 6, 7, 8, 9]$, there are several three possible ways to plan a journey:  $c = [1, 2, 4]$;  $c = [3, 5, 6, 8]$;  $c = [7]$ (a journey consisting of one city is also valid). 

There are some additional ways to plan a journey that are not listed above.

Tanya wants her journey to be as beautiful as possible. The beauty value of the whole journey is the sum of beauty values over all visited cities. Can you help her to choose the optimal plan, that is, to maximize the beauty value of the journey?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of cities in Berland.

The second line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($1 \le b_i \le 4 \cdot 10^5$), where $b_i$ is the beauty value of the $i$-th city.


-----Output-----

Print one integer — the maximum beauty of a journey Tanya can choose.


-----Examples-----
Input
6
10 7 1 9 10 15

Output
26

Input
1
400000

Output
400000

Input
7
8 9 26 11 12 29 14

Output
55



-----Note-----

The optimal journey plan in the first example is $c = [2, 4, 5]$.

The optimal journey plan in the second example is $c = [1]$.

The optimal journey plan in the third example is $c = [3, 6]$.
user: Mancala is a game famous in the Middle East. It is played on a board that consists of 14 holes.  [Image] 

Initially, each hole has $a_i$ stones. When a player makes a move, he chooses a hole which contains a positive number of stones. He takes all the stones inside it and then redistributes these stones one by one in the next holes in a counter-clockwise direction.

Note that the counter-clockwise order means if the player takes the stones from hole $i$, he will put one stone in the $(i+1)$-th hole, then in the $(i+2)$-th, etc. If he puts a stone in the $14$-th hole, the next one will be put in the first hole.

After the move, the player collects all the stones from holes that contain even number of stones. The number of stones collected by player is the score, according to Resli.

Resli is a famous Mancala player. He wants to know the maximum score he can obtain after one move.


-----Input-----

The only line contains 14 integers $a_1, a_2, \ldots, a_{14}$ ($0 \leq a_i \leq 10^9$) — the number of stones in each hole.

It is guaranteed that for any $i$ ($1\leq i \leq 14$) $a_i$ is either zero or odd, and there is at least one stone in the board.


-----Output-----

Output one integer, the maximum possible score after one move.


-----Examples-----
Input
0 1 1 0 0 0 0 0 0 7 0 0 0 0

Output
4

Input
5 1 1 1 1 0 0 0 0 0 0 0 0 0

Output
8



-----Note-----

In the first test case the board after the move from the hole with $7$ stones will look like 1 2 2 0 0 0 0 0 0 0 1 1 1 1. Then the player collects the even numbers and ends up with a score equal to $4$.
user: n participants of the competition were split into m teams in some manner so that each team has at least one participant. After the competition each pair of participants from the same team became friends.

Your task is to write a program that will find the minimum and the maximum number of pairs of friends that could have formed by the end of the competition.


-----Input-----

The only line of input contains two integers n and m, separated by a single space (1 ≤ m ≤ n ≤ 10^9) — the number of participants and the number of teams respectively. 


-----Output-----

The only line of the output should contain two integers k_{min} and k_{max} — the minimum possible number of pairs of friends and the maximum possible number of pairs of friends respectively.


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

Output
10 10

Input
3 2

Output
1 1

Input
6 3

Output
3 6



-----Note-----

In the first sample all the participants get into one team, so there will be exactly ten pairs of friends.

In the second sample at any possible arrangement one team will always have two participants and the other team will always have one participant. Thus, the number of pairs of friends will always be equal to one.

In the third sample minimum number of newly formed friendships can be achieved if participants were split on teams consisting of 2 people, maximum number can be achieved if participants were split on teams of 1, 1 and 4 people.
user: George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers b. During the game, George modifies the array by using special changes. Let's mark George's current array as b_1, b_2, ..., b_{|}b| (record |b| denotes the current length of the array). Then one change is a sequence of actions:   Choose two distinct indexes i and j (1 ≤ i, j ≤ |b|; i ≠ j), such that b_{i} ≥ b_{j}.  Get number v = concat(b_{i}, b_{j}), where concat(x, y) is a number obtained by adding number y to the end of the decimal record of number x. For example, concat(500, 10) = 50010, concat(2, 2) = 22.  Add number v to the end of the array. The length of the array will increase by one.  Remove from the array numbers with indexes i and j. The length of the array will decrease by two, and elements of the array will become re-numbered from 1 to current length of the array. 

George played for a long time with his array b and received from array b an array consisting of exactly one number p. Now George wants to know: what is the maximum number of elements array b could contain originally? Help him find this number. Note that originally the array could contain only positive integers.


-----Input-----

The first line of the input contains a single integer p (1 ≤ p < 10^100000). It is guaranteed that number p doesn't contain any leading zeroes.


-----Output-----

Print an integer — the maximum number of elements array b could contain originally.


-----Examples-----
Input
9555

Output
4
Input
10000000005

Output
2
Input
800101

Output
3
Input
45

Output
1
Input
1000000000000001223300003342220044555

Output
17
Input
19992000

Output
1
Input
310200

Output
2


-----Note-----

Let's consider the test examples:   Originally array b can be equal to {5, 9, 5, 5}. The sequence of George's changes could have been: {5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}.  Originally array b could be equal to {1000000000, 5}. Please note that the array b cannot contain zeros.  Originally array b could be equal to {800, 10, 1}.  Originally array b could be equal to {45}. It cannot be equal to {4, 5}, because George can get only array {54} from this array in one operation. 

Note that the numbers can be very large.
user: User ainta is making a web site. This time he is going to make a navigation of the pages. In his site, there are n pages numbered by integers from 1 to n. Assume that somebody is on the p-th page now. The navigation will look like this: << p - k p - k + 1 ... p - 1 (p) p + 1 ... p + k - 1 p + k >> 

When someone clicks the button "<<" he is redirected to page 1, and when someone clicks the button ">>" he is redirected to page n. Of course if someone clicks on a number, he is redirected to the corresponding page.

There are some conditions in the navigation:  If page 1 is in the navigation, the button "<<" must not be printed.  If page n is in the navigation, the button ">>" must not be printed.  If the page number is smaller than 1 or greater than n, it must not be printed.   

You can see some examples of the navigations. Make a program that prints the navigation.


-----Input-----

The first and the only line contains three integers n, p, k (3 ≤ n ≤ 100; 1 ≤ p ≤ n; 1 ≤ k ≤ n)


-----Output-----

Print the proper navigation. Follow the format of the output from the test samples.


-----Examples-----
Input
17 5 2

Output
<< 3 4 (5) 6 7 >> 
Input
6 5 2

Output
<< 3 4 (5) 6 
Input
6 1 2

Output
(1) 2 3 >> 
Input
6 2 2

Output
1 (2) 3 4 >>
Input
9 6 3

Output
<< 3 4 5 (6) 7 8 9
Input
10 6 3

Output
<< 3 4 5 (6) 7 8 9 >>
Input
8 5 4

Output
1 2 3 4 (5) 6 7 8
user: In this problem, your task is to use ASCII graphics to paint a cardiogram. 

A cardiogram is a polyline with the following corners:$(0 ; 0),(a_{1} ; a_{1}),(a_{1} + a_{2} ; a_{1} - a_{2}),(a_{1} + a_{2} + a_{3} ; a_{1} - a_{2} + a_{3}), \ldots,(\sum_{i = 1}^{n} a_{i} ; \sum_{i = 1}^{n}(- 1)^{i + 1} a_{i})$

That is, a cardiogram is fully defined by a sequence of positive integers a_1, a_2, ..., a_{n}.

Your task is to paint a cardiogram by given sequence a_{i}.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 1000). The next line contains the sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000). It is guaranteed that the sum of all a_{i} doesn't exceed 1000.


-----Output-----

Print max |y_{i} - y_{j}| lines (where y_{k} is the y coordinate of the k-th point of the polyline), in each line print $\sum_{i = 1}^{n} a_{i}$ characters. Each character must equal either « / » (slash), « \ » (backslash), « » (space). The printed image must be the image of the given polyline. Please study the test samples for better understanding of how to print a cardiogram.

Note that in this problem the checker checks your answer taking spaces into consideration. Do not print any extra characters. Remember that the wrong answer to the first pretest doesn't give you a penalty.


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

Output
      / \     
   / \ /   \    
  /       \   
 /         \  
          \ / 

Input
3
1 5 1

Output
 / \     
  \    
   \   
    \  
     \ /